Subgraph Generation for Generalizing on Out-of-Distribution Links

Jay Revolinsky, Harry Shomer, Jiliang TangSubmission to ICLR 2026 · Rejected

TL;DR

Graph Neural Networks (GNNs) notoriously struggle with link prediction when test edges differ structurally from training edges (e.g., changes in common neighbor counts). This paper introduces FLEX, a data-augmentation framework that uses a semi-implicit graph generative model (GGM) to synthesize structural counterfactual subgraphs. By fine-tuning GNNs on these structurally extrapolated samples, FLEX significantly improves out-of-distribution (OOD) link prediction performance across both synthetic and real-world benchmarks.

What Problem Does This Paper Address?

While GNNs excel at link prediction (LP) in standard in-distribution settings, their performance degrades sharply under distribution shifts. Unlike standard computer vision or NLP tasks, graph distribution shifts often manifest as changes in topological properties—such as the number of common neighbors, preferential attachment scores, or shortest paths.

Existing domain generalization methods (e.g., Invariant Risk Minimization, GroupDRO) and heuristic counterfactual link generators (like CFLP) struggle in LP: invariant methods fail to capture topological shifts, while search-based counterfactual generators suffer from extreme computational overhead and scalability bottlenecks. The authors ask: Can we learn to generate topologically diverse, counterfactual subgraphs efficiently to help GNNs generalize to unseen structural distributions?

Methods

The authors propose FLEX (Framework for Learning to EXtrapolate Structures in Link Prediction):

  • Semi-Implicit Graph Generative Model (SIG-VAE): Instead of generating the entire global graph, FLEX extracts local $k$-hop enclosed subgraphs conditioned on a target edge using the zero-one labeling trick. It uses a Semi-Implicit Variational Autoencoder to balance expressiveness and scalability when generating complex topological distributions.
  • Adversarial Co-Training: FLEX pre-trains the GNN and the generative model independently, then co-trains them: $$\min_{\text{LP}} \max_{\text{GEN}} \mathcal{L}_{\text{Flex}} = \alpha \mathcal{L}_{\text{LP}} + \mathcal{L}_{\text{GEN}}$$ The generator maximizes the distance between the posterior and prior distributions to produce structurally novel links, bounded by a quadratic penalty $( \dots - \tau )^2$ to keep generated graphs coherent rather than collapsing into random noise.

  • Degree Bias Mitigation: Standard GNN-based decoders tend to over-connect nodes. FLEX introduces a threshold indicator function $\tilde{p}(u,v) = p(u,v) \cdot \mathbb{I}[p(u,v) \ge \gamma]$ to prune low-confidence edges and enforce realistic sparsity.

  • Theoretical Grounding: The authors frame structural counterfactuals via set theory, proving that structurally perturbed subgraphs expand the training support's measure over the OOD test region, yielding a strictly tighter upper bound on OOD risk.
+---------------+        1-hop Enclosed Subgraph         +--------------------------+
| Training Link | -------------------------------------> | GGM (SIG-VAE + Labels)   |
+---------------+                                        +--------------------------+
       |                                                               | Maximize KL
       | Keep Node Features,                                           | (Quadratic Penalty)
       | Vary Topology                                                 v
       |                                                 +--------------------------+
       +-----------------------------------------------> | Counterfactual Subgraph  |
                                                         +--------------------------+
                                                                       |
                                                                       | Fine-Tuning
                                                                       v
                                                         +--------------------------+
                                                         | GNN Link Predictor       |
                                                         +--------------------------+

Datasets

The framework is evaluated across several synthetic and real-world OOD configurations:

  • LPShift Benchmark: Evaluates structural shifts across Common Neighbors (CN), Preferential Attachment (PA), and Shortest Path (SP) under both Forward (sparser $\to$ denser) and Backward (denser $\to$ sparser) directions on five base citation and collaboration networks: Cora, CiteSeer, PubMed, Collab, and PPA.
  • Real-World Temporal Shift: The ogbl-collab benchmark from the Open Graph Benchmark (OGB), evaluated using Hits@50.
  • Cross-Domain Transfer: Cross-dataset transfer between Amazon Photos and Amazon Computers, evaluated using AUC.

Key Insights and Ideas

  • Generating structural counterfactuals without target domain access: FLEX aligns generated samples with the test topology (e.g., matching the common neighbor distribution of test splits to within 0.17 CNs on CiteSeer Backward) purely by expanding the generative boundary, without peeking at validation or test distributions.
  • Counterfactuals must preserve node features: Structural changes must stay conditioned on original node features; randomly altering graph structure or perturbing features introduces spurious correlations that harm downstream link predictors.
  • Density filtering is critical: Without thresholding ($\gamma$), graph decoders suffer severe degree bias, creating hyper-dense subgraphs whose common neighbor count scales linearly with node count, ruining performance on sparse target graphs.

Key Results

  • Consistent Generalization Gains: FLEX improved standard GCN performance in 28 out of 29 LPShift/real scenarios (an average relative gain of +4.41%), and boosted the state-of-the-art NCN (Neural Common Neighbor) across 100% of tested scenarios (average relative gain of +9.56%, with raw table relative gains reaching up to +28.36%).
  • Outperforming Invariance Baselines: Standard OOD methods (CORAL, DANN, GroupDRO, VREx, IRM) yielded negative relative performance deltas (between -0.02% and -28.84%), illustrating that standard domain adaptation often damages structural link prediction.
  • Scalability Over Existing Counterfactuals: The prior counterfactual baseline, CFLP, timed out or ran out of memory (OOM/OOT) on PubMed, ogbl-collab, and ogbl-ppa. On CiteSeer, CFLP preprocessing took hundreds of seconds, whereas FLEX took fractions of a second per epoch.

Limitations and Future Work

  • Prone to Dataset Drift: The authors note that FLEX fine-tuning is sensitive: while early epochs boost performance, training too long can cause monotonic performance degradation as generations drift too far.
  • Hyperparameter Sensitivity: Performance is sensitive to learning rates and the indicator threshold $\gamma$, requiring careful validation tuning.
  • High-Density Graph Scalability: Although more scalable than heuristic baselines, the enclosed subgraph extraction and SIG-VAE still triggered OOM on extremely dense graphs like ogbl-ppa unless mini-batch sizes were throttled to very small sizes (e.g., batch size 4).

Summary updated

Abstract

Graphs Neural Networks (GNNs) demonstrate high-performance on link prediction (LP) datasets, especially when the distribution of testing samples falls within the dataset’s training distribution. However, GNNs suffer decreased performance when evaluated on samples from outside their training distribution. In addition, graph generative models (GGMs) show a pronounced ability to generate novel output graphs. Despite this, the application of GGMs remains largely limited to domain-specific tasks. To bridge this gap, we propose leveraging GGMs to produce synthetic samples which extrapolate between training and testing distributions. These synthetic samples are then used for fine-tuning GNNs to improve link prediction performance in out-of-distribution (OOD) scenarios. We introduce a theoretical perspective on this phenomena which is further verified empirically via increased performance across synthetic and real-world OOD settings. We conduct further analysis to investigate how inducing structural change within training samples improves OOD performance, indicating promising new developments in graph data augmentation on link structures.
BibTeX
@misc{revolinsky2025subgraph,
  author = {Jay Revolinsky and Harry Shomer and Jiliang Tang},
  title = {{Subgraph Generation for Generalizing on Out-of-Distribution Links}},
  year = {2025},
  eprint = {2507.11710},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.11710},
}
Figure