Class-Representative Graph Summaries Through Graph Matching Networks

Abstract

Graph Neural Networks (GNNs) have emerged as a key model in the field of machine learning, due to their inherent ability to handle graph-structured data. The representation power of GNNs has led to significant advancements in diverse fields, including social network analysis, biological networks, molecular chemistry, and recommendation systems. In these domains, graph summarization plays an important role in creating compact representations of large graphs while preserving essential structural properties and information. In this context, GNNs provide a powerful framework for efficient and effective graph summarization, enabling the extraction of meaningful insights from complex and large-scale graph data. In this thesis, we will address the problem of graph summarization by exploring the representation power of Graph Matching Networks (GMNs), a specialized type of GNNs that computes similarity scores between pairs of graphs through a cross-graph attention-based matching mechanism. Specifically, given a multi-class graph dataset, we aim to extract a class-representative subgraph from each graph, that effectively represents the class to which the graph belongs. To this end, we train the GMN on a graph similarity task and propose two methodologies to identify the patterns learned by the model during training, which will inform the summary creation process. To assess the performance of our approach, we create a synthetic dataset of Geometric Shapes, enhanced with noise, which provides a controlled environment with known ground truth summaries for precise evaluation, and compare it against existing GNN architectures for graph summarization. Additionally, we experiment with the real-world MUTAG dataset, which lacks ground truth summaries, but offers ground truth prototypes, guiding our qualitative evaluation. The results, evaluated both at quantitative and qualitative level, indicate that the GMN outperforms the other models and is able to consistently and accurately identify class-representative summaries, which offer valuable insights into the patterns that the model learns during training and its decision making processes, enhancing its explainability.