Big Graph Live

Online Updates of Knowledge Graph Embedding A summary of the COMPLEX NETWORKS 2021 research  paper   by  Luo Fei, Tianxing Wu, and Arijit Khan [Background: Knowledge Graphs and Embedding] Knowledge graph is a data model for complex networks to manage large-scale and real-world facts [1, 2]. Examples include DBpedia [3], YAGO [4], Freebase [5], NELL [6], personalized health knowledge graphs [7], etc., where a node represents an entity, and an edge denotes a relationship between two entities. Knowledge graph embedding [8, 9] is increasingly becoming popular, which aims to represent each relation and entity in a knowledge graph G as a d-dimensional vector, such that the original structure and relations in G are approximately preserved in this semantic space. KG embeddings are used in downstream applications, e.g., link prediction [10, 11, 12], entity classification [13], question answering [1, 14], KG completion [15], and recommender systems [16]. [Our Problem: Dynamic...

Shortest Paths and Centrality in Uncertain Networks A summary of the PVLDB 2021 research  paper   by  Arkaprava Saha, Ruben Brokkelkamp, Yllka Velaj, Arijit Khan, and Francesco Bonchi [Background: Uncertain Graph and Shortest Path]  Uncertain networks, i.e., graphs where each edge is associated with a probability of existence, have received a great deal of attention thanks to their expressivity and applicability in many real world contexts. Uncertainty in a network might arise due to noisy measurements [2], edge imputation using inference and prediction models [1, 3], and explicit manipulation of edges, e.g., for privacy purposes [4]. Researchers have studied 𝑘-nearest neighbor queries [5, 6], reachability queries [7], clustering [8], sampling [9], network design [10], and embedding [11], just to mention a few. Shortest-path queries [12, 13, 14], on the other hand, are one of the fundamental graph primitives with a plethora of applications, e.g.,...

  Temporal Analysis of the Entire Ethereum Blockchain Network A summary of the Web Conference 2021 research paper by Lin Zhao, Sourav Sen Gupta, Arijit Khan, and Robby Luo Background: With over USD 42 Billion market capitalization (October 2020), Ethereum is the largest public blockchain that supports smart contracts [1]. Ethereum is a transaction-based state-transition machine, where the state is made up of accounts. Transfer of asset and information between accounts, recorded in the blockchain, cause transitions in the Ethereum ‘world state’. There are two types of accounts in Ethereum – users and contracts. Transactions in Ethereum are initiated by user accounts, signed with their private keys, while internal messages in Ethereum can be generated by contract accounts. Ether is the primary asset (currency) for Ethereum blockchain. In addition to ether, Ethereum blockchain allows creation of Tokens, an abstraction of digital assets, via relevant methods implemented through sma...

  An Evaluation of Backpropagation Interpretability for Graph Classification with Deep Learning   A summary of the IEEE BigData 2020 research  paper  by  Kenneth Teo Tian Shun, Eko Edita Limanta, and Arijit Khan   [Graph Classification] Graph data are ubiquitous in many domains, such as social networks, knowledge graphs, biological networks, geo-spatial road networks, and internet-of-things. There are plenty of interest and applications in developing high-quality machine learning techniques for classifying graph objects, including cheminformatics (e.g., compounds that are active or inactive for some target) [1], [2] and bioinformatics (e.g., classifying proteins into different families) [3], malware detection and classification with call graphs [18]. There are two research directions for classification tasks on graphs: (1) Given a single large graph, infer labels of individual nodes (the node classification problem) [4], [5]; and (2) given a set of...

Mining Top-k Pairs of Correlated Subgraphs in a Large Network A summary of the VLDB 2020 research  paper  by  Arneish Prateek, Arijit Khan, Akshit Goyal, and Sayan Ranu [Background and Problem]   A large body of work exists on mining recurring structural patterns among a group of nodes in the form of frequent subgraphs [1, 2]. However, can we mine recurring patterns among the frequent subgraphs themselves ? In this paper, we explored this question by mining correlated pairs of frequent subgraphs. Correlated subgraphs are different from frequent subgraphs due to the flexibility in connections between constituent subgraph instances. To elaborate, in Figure 1, we highlight three regions inside the chemical structure of Taxol, an anti-cancer drug, where CCCH and O occur closely albeit connected in different ways in all three instances. For simplicity, we do not consider the edge types (i.e., single or double bonds) in this example. This figure illustrates th...