Knowledge Distillation Improves Graph Structure Augmentation for Graph Neural Networks

Lirong Wu, Haitao Lin, Yufei Huang, Stan Z. LiNeurIPS 2022 · OpenReview

TL;DR

Graph structure augmentation is a powerful tool for training robust Graph Neural Networks (GNNs), but it often suffers from "negative augmentation"—where the gap between training on perturbed graphs and testing on the original graph hurts performance. This paper introduces KDGA (Knowledge Distillation for Graph Augmentation), a framework that uses a teacher-student setup to transfer insights from augmented structures back to the original graph, consistently boosting accuracy by over 4% across various benchmarks.

What Problem Does This Paper Address?

In the world of Graph Neural Networks, data is scarce. To help models generalize better, researchers often use graph structure augmentation—essentially "shaking up" the graph by adding or removing edges during training. Think of it like image rotation or cropping in computer vision, but for social networks or chemical molecules.

However, there is a catch: distribution shift. If you change the graph structure too much during training, the model learns to navigate a "fake" world that looks nothing like the original graph it will encounter during testing.

Distribution shift caused by graph augmentation

The authors identify this as the negative augmentation problem. If the training graph becomes too different from the test graph (measured by properties like homophily—the tendency of similar nodes to connect), the model’s performance can actually drop compared to a model trained with no augmentation at all.

Methods

To tackle this, the authors propose a novel framework called Knowledge Distillation for Graph Augmentation (KDGA). Instead of just training a single model on augmented graphs, they use a two-part system:

Comparison of standard graph learning paradigms and the proposed KDGA framework
  1. The Teacher Model: This GNN is trained on the augmented (perturbed) graphs. It learns to capture the rich, diverse contextual information created by the structural changes.
  2. The Student Model: This model is tested on the original graph. Crucially, it doesn't just learn from the labels; it "listens" to the teacher. Through a process called Knowledge Distillation, the student tries to mimic the teacher’s output distributions.

Key Innovations: * Parameter Sharing: Unlike standard distillation where the teacher and student are separate, KDGA uses a partially parameter-shared architecture. The teacher and student share the same GNN backbone but have independent "prediction heads." This prevents the student from simply overfitting to the original graph while still benefiting from the teacher's "augmented" wisdom. * GraphAug Instantiation: While KDGA works with many augmentation methods (like GAUG or MH-Aug), the authors also introduce GraphAug, a generative approach that uses a shared neural network to learn the best way to perturb the graph structure.

Datasets

The researchers evaluated KDGA on eight diverse graph datasets, categorized by their homophily levels:

  • High Homophily (Citation networks): Cora and Citeseer.
  • Low Homophily/Heterophily (Webpages and social networks): Cornell, Texas, Wisconsin, Actor, Chameleon, and Squirrel.

These datasets are standard benchmarks, but the inclusion of six heterophily datasets is significant because distribution shifts are often more volatile and damaging in these non-assortative structures.

Key Insights and Ideas

  • The Homophily "Compass": The authors found that distribution shift isn't just random noise; it moves the graph's homophily ratio. In heterophily graphs (where different types of nodes connect), augmentation often accidentally pushes the graph toward homophily, confusing a model that expects the original structure.
  • Distillation as a Bridge: KDGA acts as a bridge. It allows the model to "see" the diverse possibilities of the augmented graphs (via the teacher) while remaining "grounded" in the reality of the original graph (via the student).
  • Shared Weights Matter: The paper demonstrates that sharing weights between the teacher and student is superior to having two independent models. This suggests that the "features" learned from augmented graphs are fundamentally useful, even if the "predictions" need to be adjusted for the original structure.

Key Results

The results are impressively consistent across different GNN architectures (GCN, GraphSAGE, and GAT):

  • Accuracy Boost: On average, KDGA improved the performance of existing augmentation methods (GAUG, MH-Aug, and GraphAug) by 4.2% to 4.6% across all eight datasets.
  • Fixing "Negative Augmentation": In cases where standard augmentation actually hurt performance (e.g., GAUG on the Texas dataset), adding the KDGA framework turned those losses into significant gains.
  • State-of-the-Art Performance: The combination of their new GraphAug method with the KDGA framework achieved the best results on nearly every tested benchmark, particularly on difficult heterophily datasets like Squirrel and Actor.

Limitations and Future Work

While KDGA is a powerful "plug-and-play" framework, the authors note a few limitations:

  • Initial Structure Dependency: KDGA still requires an initial raw graph structure to perform augmentation. It cannot currently be applied to "structure-unknown" scenarios where you only have node features.
  • Computational Overhead: Training both a teacher and a student (even with shared parameters) is naturally more computationally expensive than training a single vanilla GNN.
  • Future Directions: The authors suggest exploring how this distillation approach could be adapted for unsupervised or self-supervised graph learning, where labels aren't available to guide the process.

Summary updated

Abstract

Graph (structure) augmentation aims to perturb the graph structure through heuristic or probabilistic rules, enabling the nodes to capture richer contextual information and thus improving generalization performance. While there have been a few graph structure augmentation methods proposed recently, none of them are aware of a potential negative augmentation problem, which may be caused by overly severe distribution shifts between the original and augmented graphs. In this paper, we take an important graph property, namely graph homophily, to analyze the distribution shifts between the two graphs and thus measure the severity of an augmentation algorithm suffering from negative augmentation. To tackle this problem, we propose a novel Knowledge Distillation for Graph Augmentation (KDGA) framework, which helps to reduce the potential negative effects of distribution shifts, i.e., negative augmentation problem. Specifically, KDGA extracts the knowledge of any GNN teacher model trained on the augmented graphs and injects it into a partially parameter-shared student model that is tested on the original graph. As a simple but efficient framework, KDGA is applicable to a variety of existing graph augmentation methods and can significantly improve the performance of various GNN architectures. For three popular graph augmentation methods, namely GAUG, MH-Aug, and GraphAug, the experimental results show that the learned student models outperform their vanilla implementations by an average accuracy of 4.6% (GAUG), 4.2% (MH-Aug), and 4.6% (GraphAug) on eight graph datasets.
BibTeX
@inproceedings{wu2022knowledge,
  author = {Lirong Wu and Haitao Lin and Yufei Huang and Stan Z. Li},
  title = {{Knowledge Distillation Improves Graph Structure Augmentation for Graph Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=hxKvyGEAM1},
}
Figure