Posts

Mining Top-k Pairs of Correlated Subgraphs in a Large Network

Image
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 that while CCCH and O form a frequently …

Reliability Maximization in Uncertain Graphs

Image
Reliability Maximization in Uncertain Graphs
A summary of the IEEE TKDE 2020 research paper by Xiangyu Ke, Arijit Khan, Mohammad Al Hasan, and Rojin Rezvansangsari

[Background]Rich expressiveness of probabilistic graphs and their utility to model the inherent uncertainty in a wide range of applications have prompted a large number of research works on probabilistic graphs by the data management research communities [1]. In an uncertain graph setting, Network Reliability is a well-studied problem [2], [3], which requires to measure the probability that a target node is reachable from a source node. Reliability has been widely studied in device networks, i.e., networks whose nodes are electronic devices and the (physical) links between such devices have a probability of failure [4]. More recently, the attention has been shifted to social, communication, transportation, genomic, and logistic networks [5]–[7]. 
Figure 1: Reliability in a sensor network: the probabilities of successful packag…

Semantic Guided and Response Times Bounded Top-k Similarity Search over Knowledge Graphs

Image
Semantic Guided and Response Times Bounded Top-k Similarity Search over Knowledge Graphs

A summary of the IEEE ICDE 2020 research paper by Yuxiang Wang, Arijit Khan, Tianxing Wu, Jiahui Jin, and Haijiang Yan.
Background: Knowledge graphs (such as DBpedia [1], Yago [2], and Freebase [3]) have been constructed in recent years, managing large-scale and real-world facts as a graph [4]. In such graphs, each node represents an entity with attributes, and each edge denotes a relationship between two entities. 
Answering Graph Query on Knowledge Graphs: Querying knowledge graphs is essential for a wide range of applications, e.g., question answering and semantic search [5]. For example, consider that a user wants to find all cars produced in Germany. One can come up with a reasonable graph representation of this query as a query graph GQ, and identify the exact or approximate matches of GQ in a knowledge graph G using graph query models [6]–[10]. Correct answers can be returned, such as <BMW …

Measurements, Analyses, and Insights on the Entire Ethereum Blockchain Network

Image
Measurements, Analyses, and Insights on the Entire Ethereum Blockchain Network

A summary of the WebConf 2020 (formerly WWW) research paper by Xi Tong Lee, Arijit Khan, Sourav Sen Gupta, Yu Hann Ong, and Xuan Liu.

Background of the Ethereum Blockchain: It has been more than ten years since Bitcoin [1] introduced the era of decentralized community-controlled currency. Since then, several cryptocurrency variants like Litecoin, Namecoin, Dash, Zcash, have been introduced. Blockchains are increasingly becoming popular due to the prevalence of such cryptocurrencies and decentralized applications. Decentralized applications are written on the framework of numerous blockchain networks like Hyperledger, Corda, Ripple, Stellar, EOS, NEO, IOTA, and many more. Among them, Ethereum [2] is a distributed public blockchain network that focuses on running code (smart contracts) for decentralized applications. More simply, it is a platform for sharing information in a global state that cannot be manipula…