Big Graph Live

  Graph Classification with Minimum DFS Code:  Improving Graph Neural Network Expressivity A summary of the IEEE BigData  2021 research  paper   by  Jhalak Gupta and Arijit Khan  [presented in Machine Learning on Big Data (MLBD 2021), special session of IEEE BigData 2021]. Background: Graph Classification Given a set of graphs with different structures and sizes, the graph classification problem predicts the class labels of unseen graphs [1, 2, 3]. Developing machine learning tools for classifying graphs can be found in cheminformatics [1, 4] and bioinformatics [6], malware detection [7], telecommunication networks, internet-of-things [8], trajectories and social networks [9]. This is challenging because network data contain graphs with different numbers of nodes and edges, and a generic node order is often not available. Graphs do not have regular grid structures, since the neighborhood size of each node differs. The lack of ordered vector represent...

Multi-relation Graph Summarization A summary of the  ACM Transactions on Knowledge Discovery from Data (TKDD) Journal  2021 research  paper   by  Xiangyu Ke, Arijit Khan, and Francesco Bonchi Background: Multi-relation Graphs Multi-relation networks (also known as multi-layer, multiplex, or multi-dimensional networks) are graphs where multiple edges of different types may exist between any pair of nodes [7]. Multi-relation graphs are an expressive model of real-world activities, in which a relation can be a topic in social networks, an interaction type in genetic networks, or a snapshot in temporal graphs. For instance, BioGRID (thebiogrid.org) describes seven different types of genetic interactions between genes in Homo Sapiens. STRING (string-db.org) models protein-to-protein interactions with six types of correlations statistically learned from existing protein databases, revealing that most protein interactions are associated with at least two types of cor...

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