PaperlayerView exact revision on arXiv

Source-linked AI summary

Shift-Robust GNNs: Overcoming the Limitations of Localized Graph Training Data

Qi Zhu, Natalia Ponomareva, Jiawei Han, Bryan Perozzi

arXiv:2108.01099v2cs.LG

TL;DR

GNN semi-supervised learning commonly assumes IID labeled nodes, although practical labeling is expensive and biased, causing training–inference distribution differences. SR-GNN adapts biased labeled samples toward the graph-wide distribution across deep and linearized GNNs, recovering at least 40% of performance lost under biased training. The authors conclude that biased data is common and that further domain-specific regularization remains needed.

  • Problem

    GNN semi-supervised learning often assumes IID labeled nodes, despite practical labeling processes being expensive and biased.

  • Method

    SR-GNN adapts biased labeled nodes toward the distributional characteristics of an IID graph sample for both deep and linearized GNNs.

  • Results

    SR-GNN recovers at least 40% of the performance lost when a GCN is trained on the same biased input.

  • Takeaways & Limitations

    The framework reduces the influence of biased training data across multiple GNN types and benchmark experiments.

  • Takeaways & Limitations

    Further work is needed for domain-specific shift regularization and fairness constraints with imbalanced training data.

Abstract

from arXiv · show

There has been a recent surge of interest in designing Graph Neural Networks (GNNs) for semi-supervised learning tasks. Unfortunately this work has assumed that the nodes labeled for use in training were selected uniformly at random (i.e. are an IID sample). However in many real world scenarios gathering labels for graph nodes is both expensive and inherently biased -- so this assumption can not be met. GNNs can suffer poor generalization when this occurs, by overfitting to superfluous regularities present in the training data. In this work we present a method, Shift-Robust GNN (SR-GNN), designed to account for distributional differences between biased training data and the graph's true inference distribution. SR-GNN adapts GNN models for the presence of distributional shifts between the nodes which have had labels provided for training and the rest of the dataset. We illustrate the effectiveness of SR-GNN in a variety of experiments with biased training datasets on common GNN benchmark datasets for semi-supervised learning, where we see that SR-GNN outperforms other GNN baselines by accuracy, eliminating at least (~40%) of the negative effects introduced by biased training data. On the largest dataset we consider, ogb-arxiv, we observe an 2% absolute improvement over the baseline and reduce 30% of the negative effects.

1 Introduction

GNN semi-supervised learning often assumes IID labeled nodes, but real labeling is costly and biased, creating training–inference distribution shifts. SR-GNN frames this as transfer learning and adapts both deep and linearized GNNs to mitigate the resulting performance loss.

  • Motivation: Biased node selection can make training and inference distributions differ, causing GNN classifiers to overfit labeling irregularities and generalize poorly.This issue is especially relevant when only a subset of large graphs can be labeled or when heuristics, human choices, or delayed labels shape selection.
  • Motivation: Most prior GNN semi-supervised learning work assumes IID training labels, leaving distributional shift largely unaddressed.The paper identifies this assumption in both existing methods and recent GNN benchmarks.
  • Method: SR-GNN treats localized training data as transfer learning and adapts biased labeled nodes toward the graph-wide distribution.The framework addresses bias in both deeper GNNs and linearized shallow models.
  • Results: SR-GNN recovers at least 40% of performance lost by a GCN trained on the same biased input.The authors evaluate this using an experimental framework that simulates localized discovery through biased train/test splits.
  • Contributions: The paper contributes a focused GNN distribution-shift treatment, a general framework, a bias-controlled experimental setup, and extensive mitigation experiments.These contributions establish both the problem’s relevance and the proposed framework’s empirical scope.

2 Related Work

The related work connects distribution-shift correction to domain adaptation, discrepancy regularization, and importance reweighting, while positioning GNNs as models that combine node features with graph structure.

  • Distributional shift and domain adaptation: Domain adaptation transfers knowledge from a labeled source distribution to a target inference distribution, often using distance-based reweighting or joint source–target training.This provides the conceptual transfer-learning context for localized GNN training data.
  • Distributional shift and domain adaptation: MMD measures distribution differences in a kernel space, whereas CMD matches means and higher-order moments directly in the original feature space.The paper notes that CMD can offer stronger practical behavior than adversarial alternatives in related regularization settings.
  • Distributional shift and domain adaptation: Importance reweighting is commonly used for linear or nondifferentiable models, with kernel mean matching selecting weights by minimizing distribution discrepancy.This complements hidden-layer discrepancy regularization used with nonlinear networks.
  • GNNs: A GNN operates on node features and graph connectivity, producing node representations for unsupervised or semi-supervised learning.Its graph structure supplies an inductive bias alongside the feature inputs.
  • GNNs: GNN layers mix node representations through a normalized adjacency matrix and learnable transformations, with nonlinear activation applied at each layer.The generic layer form is Hk = σ(ÃHk−1θk), starting from H0 = X.

3 Distributional shift in GNNs

The paper defines GNN distributional shift as a mismatch between training and inference representations, emphasizing that graph propagation can amplify bias. Empirically, larger shift is associated with lower node-classification performance.

  • Distributional shift in GNNs: Training and inference mismatch undermines the usual cross-entropy guarantee, which assumes Prtrain(X,Y) = Prtest(X,Y).Under that assumption, optimizing training loss supports calibration on the testing distribution; mismatch breaks the premise.
  • Data shift as representation shift: The paper focuses on representation shift, where Prtrain(Z,Y) ≠ Prtest(Z,Y) and consequently Prtrain(Z) ≠ Prtest(Z), measured using MMD or CMD.CMD is selected as the efficient discrepancy metric for the paper’s experiments.
  • Empirical motivation: Higher CMD shift corresponds to lower GCN node-classification performance across three benchmark datasets.Figure 1 plots F1 against CMD for 100 biased training-set samples per dataset and motivates explicit shift mitigation.
  • Data shift as representation shift: Graph message passing can create additional representation shift because normalized adjacency multiplication changes hidden-state distributions through the graph inductive bias.Thus biased node sampling combines ordinary feature-distribution shift with graph-induced effects.
  • Framework overview: SR-GNN is introduced as a framework intended to reduce both differentiable and graph-induced distribution shifts across traditional and linearized GNNs.Figure 2 compares a traditional GNN, a linearized GNN, and SR-GNN.

4 Shift-Robust Graph Neural Networks

SR-GNN reduces distributional shift in GNNs by combining hidden-layer discrepancy regularization with instance reweighting for graph-induced bias. The framework applies to both traditional differentiable GNNs and linearized models.

  • 4.3 Shift-Robust GNN Framework: SR-GNN jointly reduces shifts from differentiable hidden layers and non-differentiable graph inductive bias through regularization and instance reweighting.The framework is designed to address both sources simultaneously across different GNN architectures.
  • 4.1 Scenario 1: Traditional GNN models: Traditional GNNs model graph structure through learnable layers, enabling a discrepancy regularizer between biased training and unbiased IID representations.The regularizer is added to cross-entropy loss, and central moment discrepancy is used as the shift metric.
  • 4.2 Scenario 2: Linearized GNN Models: Linearized GNNs require instance weighting because graph propagation is introduced through a fixed linear stage without learnable layers for direct distributional regularization.The method matches graph-induced features between training and testing samples using kernel mean matching, with bounded weights and class-balance constraints.
  • 4.3 Shift-Robust GNN Framework: In APPNP, SR-GNN combines feature encoding with personalized PageRank propagation and applies instance weighting to graph bias plus discrepancy regularization to encoded features.The framework is also applied to GCN and DGI, using regularized loss for GCN and instance reweighting for DGI.

5 Experiments

The experiments create biased graph-training samples, evaluate SR-GNN across benchmark datasets and baselines, and test its scalability, model portability, domain-invariant alternatives, and parameter sensitivity. SR-GNN consistently reduces performance losses caused by distributional shift, with combined discrepancy regularization and instance reweighting outperforming either correction alone.

  • 5.3 Experiment results: SR-GNN reduces biased-training performance drops by at least 40% relative to a biased GCN on three citation benchmarks.The experiments report Micro-F1, Macro-F1, and performance drop relative to an unbiased GCN; all methods lose performance under biased sampling.
  • 5.3 Experiment results: Combining discrepancy regularization with instance reweighting performs better than either bias correction alone in the reported ablations.The method is evaluated using APPNP as its base model, with separate ablations for the two shift-robust techniques.
  • 5.3 Experiment results: On ogb-arxiv and Reddit, SR-GNN mitigates 30% of the negative effect relative to an unbiased GCN, and 5% labeling further narrows the gap.The biased-sample loss remains significant on both large benchmarks, although it is smaller than on the citation datasets.
  • 5.3 Experiment results: The shift-robust framework improves performance when applied to GCN and DGI, supporting use across traditional, linearized, and representation-learning GNN settings.For GCN, regularized loss is applied to final node representations; for DGI, instance reweighting is used for logistic regression over pretrained embeddings.
  • 5.4 Comparison with other domain invariant learning methods: Compared with DANN, discrepancy-based regularization generally performs better and is less sensitive to the regularizer weight in the semi-supervised setting.The comparison uses GCN and APPNP architectures, with CMD as the SR-GNN ablation.
  • 5.5 Parameter sensitivity of SR-GNN: SR-GNN remains ahead of APPNP as sampler α varies from 0.05 to 0.3, while one CMD moment can work with a reasonable penalty and smaller instance-weight bounds perform better.The parameter studies attribute dataset-specific α patterns to changing PPR-neighbor topology and state that larger lower bounds restrict expressive range.

6 Conclusion

The paper concludes that biased training data harms GNN performance and presents SR-GNN as a framework for mitigating these effects across GNN architectures. It also identifies domain-specific regularization and fairness under imbalanced data as important directions for future work.

  • 6 Conclusion: SR-GNN outperforms other GNN baselines on biased data and eliminates 30–50% of the negative effects introduced by biased GCN training data.The experiments demonstrate both GNN susceptibility to biased data and SR-GNN’s mitigation of performance drops.
  • 6 Conclusion: SR-GNN applies to both deeper GNNs and newer linearized, shallow GNN models.The framework is presented as general across these two model families.
  • 6 Conclusion: Future work should develop domain-specific regularizations for shifts such as spam and abuse detection and preserve constraints such as fairness with imbalanced training data.The paper explicitly identifies these as remaining areas of work.

A.1 Data Statistics

This section provides overall dataset statistics and notes that the graph nodes are anonymized without personally identifiable data.

  • A.1 Data Statistics: Graph nodes are anonymized.
  • A.1 Data Statistics: The nodes do not contain personally identifiable data.
  • A.1 Data Statistics: The section includes an overall dataset statistics table.

A.2 Scalable biased sampler details

The scalable personalized PageRank sampler constructs biased training sets by selecting high-scoring neighbors of sampled seed nodes. A Cora visualization shows the resulting biased samples, seeds, and PPR scores.

  • A.2 Scalable biased sampler details: Figure 5 presents a biased sample for one Cora class together with the initial seed and its PPR-score visualization.
  • A.2 Scalable biased sampler details: The sampler computes a personalized PageRank vector for a randomly selected node and adds its top-γ PPR neighbors to the training set when enough nonzero neighbors exist.The implementation uses ϵ = 0.005 and γ = 20.
  • A.2 Scalable biased sampler details: For the illustrated Cora example, training samples are colored orange and PPR scores relative to the seed node are shown in red.

A.3.1 Performance of SR-GNN in deeper models

SR-GNN improves robustness over standard GNNs as model depth or width varies, while reducing distribution shifts. Its tuned variants also narrow the gap to IID-trained performance.

  • A.3.1 Performance of SR-GNN in deeper models: SR-GCN generally outperforms GCN with smaller variance across the deeper-model settings studied.On PubMed, GCN performance increases with fewer than four hidden layers.
  • A.3.1 Performance of SR-GNN in deeper models: SR-GCN consistently improves GCN performance while reducing distribution shifts under matched parameters.
  • A.3.1 Performance of SR-GNN in deeper models: SR-GAT provides robust improvements across different numbers of attention heads as model width increases.More attention heads generally improve performance and reduce distribution shifts.
  • A.3.1 Performance of SR-GNN in deeper models: Both SR-GNN and its ablated variants improve performance and further minimize the gap with the IID-trained model after parameter tuning.The study tunes the distribution-discrepancy regularizer and instance weighting.
Loading 2108.01099v2…