PaperlayerView exact revision on arXiv

Source-linked AI summary

Data Augmentation for Graph Neural Networks

Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, Neil Shah

arXiv:2006.06830v2cs.LGstat.ML

TL;DR

Graph data augmentation for GNNs is limited by irregular graph connectivity and the lack of direct analogs to common vision and language transformations. GAUG uses neural edge predictors to add likely and remove unlikely edges through modified-graph or original-graph strategies, improving node classification across architectures and datasets. Reported gains reach 17% for GAUG-O and 9% for GAUG-M over non-augmented models.

  • Problem

    Graph data augmentation has limited prior study because graph connectivity is irregular and common vision and language operations do not directly apply.

  • Method

    GAUG uses neural edge predictors to learn class-homophilic structure and augment graphs through deterministic modification or stochastic training-time sampling.

  • Results

    GAUG-O and GAUG-M achieve up to 17% and 9% absolute F1 improvements across architectures and datasets.

  • Takeaways & Limitations

    Neural edge predictors can promote intra-class and demote inter-class edges to improve GNN-based node classification in two inference settings.

  • Takeaways & Limitations

    Contrived graph modifications may overfit the modified graph and perform poorly on the original graph because of a wide train-test gap.

Abstract

from arXiv · show

Data augmentation has been widely used to improve generalizability of machine learning models. However, comparatively little work studies data augmentation for graphs. This is largely due to the complex, non-Euclidean structure of graphs, which limits possible manipulation operations. Augmentation operations commonly used in vision and language have no analogs for graphs. Our work studies graph data augmentation for graph neural networks (GNNs) in the context of improving semi-supervised node-classification. We discuss practical and theoretical motivations, considerations and strategies for graph data augmentation. Our work shows that neural edge predictors can effectively encode class-homophilic structure to promote intra-class edges and demote inter-class edges in given graph structure, and our main contribution introduces the GAug graph data augmentation framework, which leverages these insights to improve performance in GNN-based node classification via edge prediction. Extensive experiments on multiple benchmarks show that augmentation via GAug improves performance across GNN architectures and datasets.

1 Introduction

Graph data augmentation is underdeveloped because graph connectivity is irregular and lacks direct analogs to common vision and language transformations. GAUG uses neural edge prediction to improve node classification across architectures and datasets.

  • Motivation: Graph augmentation has seen broad adoption elsewhere, but comparatively few strategies combine augmentation with GNNs.Prior augmentation work creates plausible variations without additional ground-truth labels and supports tasks including node classification, link prediction, and graph representation learning.
  • Challenges: Irregular node connectivity prevents direct reuse of hand-crafted CV and NLP augmentations, making edge addition and removal the most obvious graph operations.Adding nodes creates labeling and feature-imputation challenges, while removing nodes reduces available data.
  • Prior approaches: Existing approaches include random edge removal and confidence-based two-stage edge modification, but the latter relies on predicted labels and is prone to errors.DROPEDGE cannot benefit from added edges, whereas ADAEDGE adds or removes edges between nodes predicted to share or differ in labels.
  • Illustration: Random graph modification hurts GCN test micro-F1, whereas GAUG approaches improve performance and narrow the gap to class-aware modifications.The comparison uses the Zachary’s Karate Club graph under original and modified graph settings.
  • Contribution: GAUG uses neural edge predictors to learn class-homophilic structure and offers GAUG-M and GAUG-O for modified-graph and original-graph inference settings.The framework can denoise structure or mimic variability and is designed to apply flexibly across GNN architectures.
  • Results: Up to 17% and 9% absolute F1 improvements are reported for GAUG-M and GAUG-O across datasets and GNN architectures without augmentation.The same passage reports up to 16% and 9% improvements over baseline augmentation strategies.

2 Other Related Work

Related work spans graph neural networks, data augmentation outside graph learning, and meta-learning-based augmentation. The paper positions GAUG as addressing the comparatively less studied graph setting with a different network structure.

  • Graph Neural Networks: GNNs support node features, custom aggregation, and inductive operation, motivating their widespread use in graph-based machine learning.The related-work discussion contrasts GNNs with earlier embedding-lookup approaches and reviews spectral and spatial variants.
  • Data Augmentation: Data augmentation has also been studied through oversampling, undersampling, interpolation, synonym swapping, and text-variation methods.These techniques are discussed primarily in traditional classification, NLP, and computer vision contexts.
  • Data Augmentation: Meta-learning approaches in computer vision learn image transformations through an augmentation network trained with a target-network loss.The paper shares their motivation but differs fundamentally in network structure and application to graphs.

3 Graph Data Augmentation via Edge Manipulation

The paper frames graph augmentation as edge manipulation over a fixed node set, motivated by noisy observed connectivity and the need to bridge it toward task-relevant structure. It distinguishes deterministic modified-graph augmentation from stochastic original-graph augmentation.

  • Core idea: The proposed graph augmentation idea manipulates G by adding and removing edges while keeping the node set fixed.The section introduces practical and theoretical motivations and evaluation considerations for manipulated graphs.
  • Practical reasons: Observed graphs can diverge from an underlying process because of adversarial noise, partial observation, or other distortions.This motivates seeking an ideal graph whose connectivity better serves downstream node classification.
  • Practical reasons: Strategically adding intra-class edges and removing inter-class edges improves node-classification test performance and encourages smoother same-class embeddings.The Zachary’s Karate Club example achieves this benefit with one training example per class.
  • Theoretical reasons: With fully connected same-class components and no inter-class edges, a permutation-invariant GNN layer gives identical embeddings within components and distinct embeddings across components under stated conditions.This theorem provides the theoretical motivation for class-homophilic graph structure.
  • Theoretical reasons: An ideal class-homophilic graph can make training differentiation trivial, but contrived modifications may overfit and widen the train-test gap.The paper therefore approximates the ideal graph and evaluates generalization on both modified-like and original graphs.
  • Settings: Graph augmentation differs from image augmentation because node classification typically starts with one graph rather than many examples.The paper defines modified-graph augmentation for training and inference, and original-graph augmentation for training while retaining G for inference.
  • GAUG-M: GAUG-M uses an edge predictor to deterministically add high-probability non-edges and remove low-probability existing edges.Using the predicted matrix M, it adds the top i|E| non-edges and removes the j|E| existing edges with i,j∈[0,1].
  • Settings: The modified-graph setting suits unchanging graphs, whereas dynamic, latency-sensitive inference makes recalibrating graph connectivity during inference infeasible.The choice of strategy depends on whether augmentation can be applied during inference without creating a train-test gap.

4 Proposed GAUG Framework

GAUG augments graphs by predicting edge probabilities, then either modifying the graph directly or sampling differentiable graph variants for GNN training. Its two approaches use edge prediction alongside node classification to improve semi-supervised node classification across settings.

  • Framework overview: GAUG predicts which nonexistent edges should be added and which existent edges should be removed, using graph information to produce modified graphs.
  • GAUG-M: GAUG-M deterministically adds the highest-probability non-edges and removes the lowest-probability existing edges, functioning as a denoising step.The numbers of added and removed edges are controlled by i and j relative to |E|.
  • GAUG-M: On CORA, learned edge probabilities promote intra-class and demote inter-class edges more effectively than random perturbations, improving classification performance.Learned addition consistently improves micro-F1, while learned removal improves performance through approximately 20%.
  • GAUG-O: GAUG-O addresses settings where inference-time graph manipulation is unavailable by generating diverse graph variants through end-to-end edge prediction and stochastic sampling.Each training iteration exposes the node classifier to a new augmented graph variant.
  • GAUG-O: GAUG-O interpolates predicted edge probabilities with the original adjacency, samples a sparse variant using relaxed Bernoulli sampling, and uses straight-through gradients for training.The sampled adjacency is passed with node features to the GNN, while classification and edge-prediction losses are jointly optimized.

5 Evaluation

The evaluation tests GAUG-M and GAUG-O across six benchmark datasets and four GNN architectures, finding consistent improvements, especially under weak supervision. Results also show that performance depends on strategic edge manipulation and learned class-homophilic structure.

  • 5.1 Experimental Setup: Experiments cover six benchmark datasets across citation, protein-interaction, social-network, and air-traffic domains, using four GNN architectures.
  • 5.2 Experimental Results: GAUG-M and GAUG-O consistently improve GNN performance across architectures, datasets, and alternatives, with one exception for GAT on PPI.
  • 5.2 Experimental Results: GAUG-M improves average performance by 4.6% on GCN, 4.8% on GSAGE, 10.9% on GAT, and 5.7% on JK-NET.
  • 5.2 Experimental Results: GAUG-M improves performance across all six datasets, while improvements are not necessarily monotonic with edge addition or removal.
  • 5.2 Experimental Results: GAUG-O promotes intra-class edges and demotes inter-class edges, with learned denoising outperforming random edge removal.
  • 5.2 Experimental Results: Both GAUG methods are especially powerful under weak supervision, producing large F1 improvements with few labeled samples; gains shrink with more supervision.

6 Conclusion

The paper addresses graph augmentation through neural edge prediction, using class-homophilic structure to modify graphs for node classification. GAUG-M and GAUG-O improve absolute F1 performance across architectures and datasets and over augmentation baselines.

  • GAUG uses neural edge predictors to expose GNNs to likely nonexistent edges and limit exposure to unlikely existent edges.
  • The framework promotes intra-class edges and removes or suppresses inter-class edges across two inference settings.
  • GAUG-M and GAUG-O achieve up to 17% and 9% absolute F1 improvements across architectures and datasets, respectively.
  • GAUG-M and GAUG-O achieve up to 15% and 8% improvements over augmentation baselines, respectively.

Ethical Impact

The paper does not foresee ethical concerns specific to its method, while acknowledging that graph-based machine learning improvements could benefit both ethical and unethical applications.

  • The authors do not foresee ethical concerns posed by GAUG but acknowledge that its improvements may benefit ethical and unethical graph-based machine-learning applications.

A.1 Proof of Theorem 1

The proof analyzes permutation-invariant GNN aggregation on fully connected components, showing identical embeddings within components and distinct embeddings across components under stated conditions. It also establishes the equivalence of micro-F1 and accuracy for single-label classification.

  • Permutation-invariant aggregation: A permutation-invariant neighborhood aggregator is unchanged by reordering the target node and its neighbors.This defines the invariance property used in the proof.
  • Theorem 1: Theorem 1 applies to any GNN layer with a permutation-invariant neighborhood aggregator and arbitrary node-feature block vectors.The theorem assumes an undirected graph containing fully connected components.
  • Theorem 1: For nodes in the same fully connected component, normalized adjacency rows match, so a GNN layer produces identical embeddings.The proof uses equal connectivity and equal node degrees within the component.
  • Theorem 1: For nodes in different fully connected components, their normalized adjacency rows differ, yielding distinct embeddings when W is not all zeros.The components have no shared neighbors, and the proof derives different layer outputs.
  • Micro-F1 and accuracy: Micro-F1 equals accuracy when every classification example has exactly one ground-truth and one predicted class.Single-label errors contribute one false positive and one false negative across classes.

B Additional Dataset Details

The paper supplements its benchmark descriptions with dataset domains, node features, graph relations, labels, and computing resources. The datasets include citation, protein-interaction, social, and air-traffic networks.

  • Citation networks: CORA and CITESEER are citation networks whose nodes are computer-science papers, with title bag-of-word features, citation edges, and category labels.They are used as benchmarks in prior GNN work.
  • Protein-protein interaction network: PPI combines human-tissue protein-interaction networks, using gene-related features and 121 gene-ontology label sets.The original graph contains 295 connec...
  • Social networks: FLICKR represents users connected by follows, with interest tags as features and joined groups as labels.The dataset is an image and video sharing platform’s social network.
  • Air traffic network: AIR-USA is an airport traffic network in the United States.
  • Computing environment: Experiments ran on Google Cloud using 15 vCPUs, 15 GB of RAM, and one NVIDIA Tesla V100 GPU.

C.1 Notes for effectively training GAUG-O

GAUG-O training relies on pretraining and learning-rate warmup to stabilize joint optimization of the edge predictor and node classifier. Mini-batch sampling introduces a small graph discrepancy because outside-subgraph edges cannot be sampled.

  • Pretraining: Pretraining both GAUG-O components improves training stability, with edge-predictor pretraining more important empirically than classifier pretraining.Excessive classifier pretraining can cause overfitting and poor optimizer performance.
  • Learning-rate warmup: The edge predictor uses sigmoid learning-rate warmup to prevent sudden drift from node-classification loss after pretraining.The learning rate starts at zero and increases gradually.
  • Mini-batch training: Mini-batch training computes edge-prediction loss from the sampled subgraph and node-classification loss only from seed-node predictions.
  • Mini-batch limitation: Mini-batch graphs cannot sample new edges between seed nodes and target nodes outside the extended subgraph.Most sampled new edges remain within a few hops, and the authors report little training impact.
  • Implementation: The implementation includes GAUG-M and GAUG-O hyperparameter searches alongside reproduced ADAEDGE and DROPEDGE comparisons.

D.1 Ablation Study for GAUG-O

The ablation study examines graph sampling and loss design choices for GAUG-O on CORA across four GNN architectures. It highlights the role of edge-prediction loss in avoiding unrealistic graph drift and unstable training.

  • Ablation setup: GAUG-O ablations compare four GNN architectures with baseline and alternative graph-sampling and training choices on CORA.The results are reported in Table 3.
  • No sampling: The ablation evaluates whether feeding a fully dense adjacency without sampling changes GAUG-O performance.In this variant, every edge is used for convolution.
  • Additional evaluations: The supplementary tables summarize large-dataset statistics and GAUG performance under mini-batch training.
  • No edge-prediction loss: Removing the edge-prediction loss risks unrealistic graphs that arbitrarily deviate from the original graph and destabilizes training.The loss combines edge-prediction and node-classification objectives.

D.2 GAUG with Mini-batch Training

GAUG remains effective with mini-batch training and across graph settings, while edge-predictor choice and strategic augmentation materially affect performance. The framework also shows gains under weak supervision and for deeper GNNs.

  • Mini-batch training: 2.2% improvement on PUBMED is achieved with GAUG-M under mini-batch training.All three methods use the same mini-batch setting and batch size.
  • Mini-batch training: 4.8% improvement on OGBN-ARXIV is achieved with GAUG-O under mini-batch training.The reported comparison uses the same mini-batch setting and batch size across methods.
  • Edge predictors: Different edge predictors produce characteristically different GAUG-M performance heatmaps on the same dataset, showing that predictor choice is important.The comparison includes GAE, VGAE, LLHN, and JI; careless edge addition or removal can hurt performance.
  • Deeper GNNs: GAUG-M delivers stable improvements across GNN architectures and depths, including 52.4-point absolute F1 improvement for GCN and 16.4-point improvement for GSAGE at eight layers.GAUG-O improves GCN, GSAGE, and JK-NET across different depths, while most unaugmented GNNs worsen as layers increase.
  • Weak supervision: GAUG’s performance gains are larger with fewer training nodes, and 35-node GAUG training is often at least as good as baseline training with 70 nodes.This pattern is reported across GNN architectures and both GAUG-M and GAUG-O settings.
Loading 2006.06830v2…