Finding Diverse and Predictable Subgraphs for Graph Domain Generalization

Junchi Yu, Jian Liang, Ran HearXiv 2022 · DOI · arXiv

Introduction

Graph Neural Networks (GNNs) have demonstrated remarkable success in modeling structured data. However, their performance often degrades significantly when the testing data distribution shifts from the training distribution—a common occurrence in real-world applications like social network analysis or financial fraud detection. While Domain Generalization (DG) aims to address this by identifying invariant features across multiple source domains, many practical scenarios provide only a single, limited dataset. This "domain scarcity" renders traditional DG methods ineffective.

The DPS Framework

To overcome the lack of diverse training environments, we introduce Diverse and Predictable Subgraphs (DPS). DPS is a model-agnostic framework that synthetically generates multiple diverse domains from a single source graph by exploiting the inherent redundancy in graph data.

Overview of the DPS framework showing the generation of diverse and predictable subgraphs.

Methodology

The framework consists of two primary components:

  1. Predictable Subgraph Generators: A set of $K$ generators identifies subgraphs that are individually sufficient to predict the target label. This ensures that each synthetic domain retains the core semantic information of the original graph.
  2. Diversity via Energy-Based Regularization: To prevent generators from collapsing onto the same "easy" features, an energy-based loss function ($L_{dist}$) is employed. This forces the distributions of the generated subgraphs to be distinct, effectively creating a diverse set of augmented environments.

The training process follows a bi-level optimization (min-max game). The generators strive to produce diverse and predictable subgraphs, while the GNN predictor is trained to be "equi-predictive" across all generated domains. This pressure forces the model to ignore spurious correlations and focus on invariant patterns that persist across all synthetic environments.

Experimental Evaluation

The DPS framework was evaluated across various tasks, including graph-level classification (Spurious-Motif, MUTAG) and node-level generalization under spatial and temporal shifts (Twitch, Facebook-100, ELLIPTIC).

Performance Gains

On the synthetic Spurious-Motif dataset, DPS improved accuracy by 12-17% over standard Empirical Risk Minimization (ERM), demonstrating its ability to filter out misleading features. In real-world financial applications, specifically the ELLIPTIC dataset for illicit activity detection, DPS showed significant resilience to temporal distribution shifts.

Performance comparison (Test F1-Score) on the ELLIPTIC dataset using the GCNII backbone across different time steps.

As shown in the figure above, DPS consistently outperforms ERM and EERM across various time steps, maintaining a higher F1-score even as the distribution shifts further from the initial training data. This confirms that the framework successfully captures invariant semantics rather than transient noise.

Conclusion

DPS provides a robust solution for graph domain generalization under domain scarcity. By treating graph redundancy as a source for synthetic diversity, it enables GNNs to learn more generalizable representations. Future work will focus on more complex structural transformations and reducing the computational overhead of the bi-level optimization process.

Summary updated

Abstract

This paper focuses on out-of-distribution generalization on graphs where performance drops due to the unseen distribution shift. Previous graph domain generalization works always resort to learning an invariant predictor among different source domains. However, they assume sufficient source domains are available during training, posing huge challenges for realistic applications. By contrast, we propose a new graph domain generalization framework, dubbed as DPS, by constructing multiple populations from the source domains. Specifically, DPS aims to discover multiple \textbf{D}iverse and \textbf{P}redictable \textbf{S}ubgraphs with a set of generators, namely, subgraphs are different from each other but all the them share the same semantics with the input graph. These generated source domains are exploited to learn an \textit{equi-predictive} graph neural network (GNN) across domains, which is expected to generalize well to unseen target domains. Generally, DPS is model-agnostic that can be incorporated with various GNN backbones. Extensive experiments on both node-level and graph-level benchmarks shows that the proposed DPS achieves impressive performance for various graph domain generalization tasks.
BibTeX
@misc{yu2022finding,
  author = {Junchi Yu and Jian Liang and Ran He},
  title = {{Finding Diverse and Predictable Subgraphs for Graph Domain Generalization}},
  year = {2022},
  eprint = {2206.09345},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2206.09345},
}
Figure