Differentially Describing Groups of Graphs

Corinna Coupette, Sebastian Dalleiger, Jilles Vreeken

Abstract

This paper introduces GRAGRA, a novel framework for "graph group analysis" designed to identify statistically significant subgraphs that describe both commonalities and differences across multiple groups of graphs. By combining maximum entropy modeling with rigorous statistical testing, GRAGRA effectively distinguishes genuine structural signals from noise in complex datasets, including brain networks and international trade flows.

Introduction

In many scientific fields, data is naturally represented as a collection of graphs, such as brain connectivity networks for different patient cohorts or trade relationships between countries over time. A fundamental challenge for researchers is identifying what makes these groups similar and what sets them apart. Existing methods typically focus on either summarizing a single group or contrasting exactly two groups, often failing to capture shared structures or scale to multiple groups.

Moreover, real-world graph data is often noisy and heterogeneous; simple averaging frequently highlights random fluctuations rather than meaningful patterns. There is a critical need for a differential description—a succinct, statistically grounded summary of shared and group-specific structures that can handle the complexity of modern network data.

Methodology

The authors formalize graph group analysis as a maximum likelihood modeling problem. The GRAGRA (Graph Group Analysis) algorithm employs several key components:

  • Maximum Entropy Modeling: GRAGRA builds a probability distribution that reflects only the discovered patterns (subgraphs), avoiding arbitrary assumptions about the underlying data distribution.
  • Bayesian Information Criterion (BIC): To ensure model succinctness, BIC is used to select a non-redundant set of patterns, adding new subgraphs only if the information gain justifies the increased model complexity.
  • Vuong’s Closeness Test: This statistical test determines if an improvement in model fit is significant, acting as a critical filter against overfitting to noise.
  • The GROW Heuristic: To navigate the exponential search space of possible subgraphs, a greedy "GROW" function iteratively expands small node triples into larger, informative patterns.

Experimental Evaluation

GRAGRA was evaluated on synthetic benchmarks and diverse real-world datasets, including US Air Transportation (BTS) and International Trade (WITS). A primary focus was the Functional Brain Networks (ABIDE) dataset, consisting of resting-state fMRI data from adolescents with and without Autism Spectrum Disorder (ASD).

GRAGRA demonstrates superior precision and F1 scores compared to Contrast Subgraphs (CSG) and Signal Subgraphs (SSG) across various noise levels.

Results and Discussion

GRAGRA consistently achieved near-perfect F1 scores in recovering planted patterns in synthetic data, while baseline methods like CSG and SSG suffered significant precision drops as noise increased. The framework also demonstrated remarkable scalability, successfully handling 15 different trade groups simultaneously.

Neuroscientific Interpretability

In the ASD study, GRAGRA identified specific underconnectivity between the visual cortex and the lingual gyrus. This pattern aligns with existing neuroscientific hypotheses regarding vision and word processing in autism, demonstrating the framework's ability to provide interpretable, domain-relevant insights.

Visualization of significant subgraphs identified by GRAGRA in functional brain networks, highlighting group-specific connectivity patterns.

Noise Resilience and Pattern Discovery

By utilizing Vuong’s test, GRAGRA proved robust against random edges that other methods often mistook for group differences. Furthermore, the algorithm discovered surprisingly large patterns, identifying significant connected subgraphs containing over 100 edges in trade and brain datasets. This capability allows researchers to see the "backbone" of a system separately from its group-level variations.

Conclusion and Future Work

GRAGRA provides a powerful tool for differential graph analysis, offering a statistically grounded approach to identifying shared and specific structures. Future work includes extending the model to handle non-node-aligned graphs (e.g., molecular structures), incorporating continuous edge weights, and dynamically adjusting significance levels to better address multiple hypothesis testing.

Summary updated

Abstract

How does neural connectivity in autistic children differ from neural connectivity in healthy children or autistic youths? What patterns in global trade networks are shared across classes of goods, and how do these patterns change over time? Answering questions like these requires us to differentially describe groups of graphs: Given a set of graphs and a partition of these graphs into groups, discover what graphs in one group have in common, how they systematically differ from graphs in other groups, and how multiple groups of graphs are related. We refer to this task as graph group analysis, which seeks to describe similarities and differences between graph groups by means of statistically significant subgraphs. To perform graph group analysis, we introduce Gragra, which uses maximum entropy modeling to identify a non-redundant set of subgraphs with statistically significant associations to one or more graph groups. Through an extensive set of experiments on a wide range of synthetic and real-world graph groups, we confirm that Gragra works well in practice.
BibTeX
@inproceedings{coupette2022differentially,
  author = {Corinna Coupette and Sebastian Dalleiger and Jilles Vreeken},
  title = {{Differentially Describing Groups of Graphs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i4.20312},
}
Figure