Big Graph Live

  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...

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...

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 G Q , and identify the exact or approximate matches of G Q in a knowledge graph G using graph query models [6]–[10]. Correct a...