PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Random Neural Network for Semi-Supervised Learning on Graphs

Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, Jie Tang

arXiv:2005.11079v4cs.LGcs.SIstat.ML

TL;DR

Semi-supervised graph learning is difficult when labels are scarce because existing GNNs can over-smooth, lack robustness, and generalize weakly. GRAND uses random propagation to generate graph augmentations and consistency regularization across them, achieving strong benchmark performance while mitigating these issues.

  • Problem

    Existing GNNs for semi-supervised graph learning can suffer from over-smoothing, non-robustness, and weak generalization when labeled nodes are scarce.

  • Method

    GRAND randomly propagates perturbed node features to generate multiple graph augmentations, then applies consistency regularization to predictions across them.

  • Results

    GRAND consistently outperforms fourteen state-of-the-art GNN baselines on benchmark datasets and shows advantages in robustness and resistance to over-smoothing.

  • Takeaways & Limitations

    Random propagation and consistency regularization improve GRAND’s generalization while mitigating non-robustness and over-smoothing.

  • Takeaways & Limitations

    GRAND relies on the homophily assumption and may not succeed on graphs with less homophily.

Abstract

from arXiv · show

We study the problem of semi-supervised learning on graphs, for which graph neural networks (GNNs) have been extensively explored. However, most existing GNNs inherently suffer from the limitations of over-smoothing, non-robustness, and weak-generalization when labeled nodes are scarce. In this paper, we propose a simple yet effective framework -- GRAPH RANDOM NEURAL NETWORKS (GRAND) -- to address these issues. In GRAND, we first design a random propagation strategy to perform graph data augmentation. Then we leverage consistency regularization to optimize the prediction consistency of unlabeled nodes across different data augmentations. Extensive experiments on graph benchmark datasets suggest that GRAND significantly outperforms state-of-the-art GNN baselines on semi-supervised node classification. Finally, we show that GRAND mitigates the issues of over-smoothing and non-robustness, exhibiting better generalization behavior than existing GNNs. The source code of GRAND is publicly available at https://github.com/Grand20/grand.

1 Introduction

The paper targets semi-supervised graph learning with scarce labels, where GNNs face over-smoothing, non-robustness, and overfitting. GRAND combines random graph propagation with consistency regularization and achieves strong benchmark performance while improving robustness and generalization.

  • Semi-supervised graph learning predicts unlabeled node categories from a graph with only a small proportion of labeled nodes.
  • Deterministic GNN propagation can cause over-smoothing, make nodes vulnerable to graph attacks, and increase dependence on potentially noisy multi-hop neighborhoods.
  • Scarce label information can lead standard GNN training to overfit, motivating augmentation and consistency-regularization strategies for using unlabeled data.
  • GRAND randomly propagates perturbed node features to create graph augmentations, separating propagation from transformation and reducing reliance on specific neighborhoods.
  • Random propagation and consistency regularization enforce consistency across multi-hop neighborhoods and empirically improve generalization, robustness, and resistance to over-smoothing.
  • Extensive experiments report state-of-the-art semi-supervised learning results on GNN benchmark datasets.

2 Problem and Related Work

This section defines semi-supervised graph learning and deterministic GNN propagation, then situates GRAND among graph augmentation and regularization methods. It also records a limitation: sampling-based propagation’s semi-supervised effects remain under-studied.

  • Problem formulation: A graph consists of nodes V and edges E, with adjacency matrix A indicating whether node pairs are connected.
  • Problem formulation: In semi-supervised graph classification, m ≪ n nodes have observed labels, and the objective is to infer labels for the remaining n − m nodes.
  • Graph Neural Networks: GNNs use graph propagation to transmit information from nodes to their neighborhoods through deterministic rules; GCN uses normalized adjacency, nonlinear activation, and learned weights.
  • Related work: Sampling-based propagation methods can serve as graph augmentation, but their effects in semi-supervised settings have not been well studied.
  • GRAND: GRAND generates multiple augmentations through random propagation and applies consistency-regularized training to improve generalization in semi-supervised learning.
  • Related work: Related GNN regularization methods include virtual adversarial training, MixUp, and edge dropping, while GRAND uses random propagation for its augmentation strategy.

3 GRAPH RANDOM NEURAL NETWORKS

GRAND combines random propagation for graph data augmentation with consistency-regularized training. Its separated propagation and transformation steps support multi-hop information use while targeting robustness, over-smoothing, and generalization.

  • 3.1 Random Propagation for Graph Data Augmentation: GRAND generates multiple graph augmentations by randomly perturbing node features, propagating each perturbed matrix, and training predictions across these variants.Dropout removes feature elements, while DropNode can remove entire node feature vectors before propagation.
  • 3.1 Random Propagation for Graph Data Augmentation: DropNode reduces dependence on particular neighbors by allowing each node to aggregate information from only a subset of its multi-hop neighbors.During training, node masks are sampled from Bernoulli(1 −δ); inference uses the original feature matrix.
  • 3.1 Random Propagation for Graph Data Augmentation: Mixed-order propagation averages powers of the normalized adjacency from order 0 through K, incorporating local information while reducing the risk of over-smoothing relative to using ˆA^K directly.The implementation computes this iteratively with sparse matrix products rather than forming the dense propagation matrix.
  • 3.1 Random Propagation for Graph Data Augmentation: GRAND separates feature propagation from nonlinear transformation, enabling higher-order propagation without repeatedly applying nonlinear transformations.The classification model is a two-layer MLP, although GCN and GAT can replace it.
  • 3.2 Consistency Regularized Training: Consistency-regularized training combines supervised classification on labeled nodes with prediction-consistency optimization across augmentations for unlabeled nodes.The training loop perturbs the input, propagates each augmentation, predicts with the model, and applies both losses.
  • Limitations: GRAND is grounded in homophily and may not succeed on graphs with less homophily.The limitation follows from relying on adjacent nodes having similar features and labels.
  • 3.3 Theoretical Analysis: Theoretical analysis links consistency regularization to a neighborhood-aware regularizer, while DropNode adds an extra regularization loss and dropout yields adaptive L2 regularization.The neighborhood terms weight classification uncertainty, which is highest near prediction probability 0.5.

4 Experiments

Experiments on benchmark graphs compare GRAND with diverse GNN baselines and ablations, then evaluate generalization, robustness, and over-smoothing. GRAND consistently outperforms baselines while showing stronger robustness and resistance to over-smoothing.

  • Experimental Setup: Experiments use Cora, Citeseer, and Pubmed, comparing GRAND with 14 GNN baselines and four GRAND variants.The baselines span graph convolutions, sampling-based GNNs, and regularization-based GNNs.
  • Overall Results: GRAND improves upon GCN by 3.9%, 5.1%, and 3.7% on Cora, Citeseer, and Pubmed, respectively.The improvements over baselines are reported as statistically significant, with p-value ≪0.01 by a t-test.
  • Overall Results: GRAND_dropout and GRAND_DropEdge outperform most baselines but remain below GRAND, indicating DropNode is the strongest tested augmentation.Detailed comparisons of DropNode and dropout under different propagation steps are reported in Appendix C.4.
  • Ablation Study: Removing consistency regularization, multiple DropNode, sharpening, or both consistency regularization and DropNode causes clear performance drops versus the full model.The ablation study attributes GRAND’s performance to the combined contribution of its designed components.
  • Robustness Analysis: With 10% new random edges, GRAND’s classification accuracy drops 7%, compared with 12% for GCN and 37% for GAT.GRAND consistently outperforms GCN and GAT across perturbation rates for both Random Attack and Metattack.
  • Over-Smoothing Analysis: As propagation increases, GCN and GAT accuracy drops from 0.75 to 0.2, whereas GRAND’s performance and MADGap improve.MADGap decreases from ∼0.5 to 0 for GCN and GAT, indicating more severe over-smoothing, while GRAND behaves differently.

5 Conclusions

The paper concludes that GRAND combines random propagation with consistency regularization for semi-supervised graph learning. It reports consistent superiority over 14 GNN baselines, alongside robustness and resistance to over-smoothing, while identifying scalability as future work.

  • Conclusions: GRAND stochastically generates multiple graph augmentations through random propagation and uses consistency regularization to improve generalization on unlabeled data.The paper presents this combination as its central framework for semi-supervised learning on graphs.
  • Conclusions: GRAND consistently outperforms fourteen state-of-the-art GNN baselines on benchmark datasets.The conclusion summarizes the reported benchmark performance across the evaluated tasks.
  • Conclusions: The paper reports advantages over conventional GNNs in robustness and resistance to over-smoothing.These advantages are supported by theoretical analysis and empirical demonstrations.
  • Conclusions: Future work aims to improve GRAND’s scalability with sampling methods.

Broader Impact

The paper frames GRAND as an alternative to increasingly complex GNN architectures, using simple machine-learning techniques to address common semi-supervised graph-learning issues. Its results support considering simple propagation and regularization designs alongside complex architectures.

  • Broader Impact: The paper examines whether simple traditional machine-learning techniques can address over-smoothing, non-robustness, and weak generalization in GNNs.
  • Broader Impact: GRAND uses dropout, linear feature propagation, and consistency regularization instead of nonlinear feature transformations and advanced neural techniques such as attention.The paper reports consistent and significant outperformance over 14 state-of-the-art GNN baselines.
  • Broader Impact: The authors suggest investing in simple traditional graph techniques under regularization frameworks alongside designing complex GNN architectures.

A.1 Datasets Details

The study evaluates GRAND on three standard benchmark graphs using established features and data splits, with extensive repeated trials for reliable results.

  • Experiments use the benchmark graphs Cora, Citeseer, and Pubmed with the same features and data splits as prior literature.Results on these datasets are averaged across 100 trials with 100 random seeds.
  • Table 2 summarizes the dataset statistics for Cora, Citeseer, and Pubmed.

A.2 Implementation Details

GRAND is implemented with sparse-dense propagation and evaluated using specified optimization, architecture, and hyperparameter settings, including systematic searches for key GRAND parameters.

  • Implementation: Random propagation is implemented efficiently with sparse-dense matrix multiplication, while GCN and GAT use referenced PyTorch and PyTorch-Geometric implementations.
  • Hyperparameter search: GRAND introduces five additional hyperparameters controlling node dropping, propagation depth, augmentation count, sharpening, and consistency-loss weighting.The parameters are δ, K, S, T, and λ.
  • Hyperparameter search: The DropNode probability δ is fixed at 0.5, while K, S, T, and λ are selected through sequential validation-set searches.Each hyperparameter configuration is evaluated with 20 random seeds.
  • Hyperparameter search: Table 3 reports the best GRAND hyperparameters used for the Table 1 results.
  • Robustness settings: Robustness experiments search propagation depth K from {5,6,7,8} for each perturbation rate because GRAND is sensitive to K under different perturbations.
  • Experiment settings: Other experiments reuse Table 3 settings with one or two changes, while baseline GCN and GAT receive separately specified training settings.

B Theorem Proofs

The proofs analyze the expected consistency loss and its regularization effect through Taylor approximations of perturbed and unperturbed predictions.

  • The proof begins by expressing the expectation of the consistency loss Lcon.
  • For each node, zi and z̃i are defined as sigmoid predictions from the original and perturbed feature matrices, respectively.
  • A first-order Taylor expansion approximates z̃i−zi using zi(1−zi), the propagation difference, and the classifier weights.
  • The proof rewrites the original loss Lorg by expanding the logistic function, then expresses the expected perturbed classification loss.
  • The resulting term R(W) acts as a regularizer on W and is analyzed with a second-order Taylor expansion around AiX·W.
  • Applying the quadratic approximation yields a quadratic form for R(W).

C.1 Results on Large Datasets

The large-dataset evaluation covers six public or constructed graph datasets and reports results showing GRAND significantly outperforms GCN and GAT across the evaluated datasets.

  • Datasets: The large-dataset study includes Cora-Full, Coauthor CS, Coauthor Physics, Amazon Computers, Amazon Photo, and Aminer CS.Table 4 provides statistics for these datasets.
  • Datasets: Aminer CS is built from a DBLP citation network with 18 manually categorized publication topics and averaged GLOVE-100 abstract vectors as node features.
  • Datasets: Table 5 lists the publication-venue topics used as classes for Aminer CS.
  • Evaluation protocol: Each trial uses 20 training samples, 30 validation samples, and the remaining samples for testing, with 100 splits and 20 initializations per split.This produces 2000 runs per dataset.
  • Results: GRAND significantly outperforms GCN and GAT on all evaluated large datasets.
  • Results: Table 6 presents the large-dataset results.

C.2 Efficiency Analysis

GRAND’s efficiency and effectiveness depend on propagation steps K and augmentation times S, with larger values improving accuracy but reducing training efficiency. Additional analyses examine hyperparameter sensitivity, augmentation choice, over-smoothing, and performance across label rates.

  • Efficiency analysis: With K = 2 and S = 1, GRAND outperforms GCN and GAT in both efficiency and effectiveness.The comparison fixes training epochs, learning rate, and hidden-layer size across models.
  • Efficiency analysis: Increasing K or S significantly improves classification accuracy at the cost of training efficiency.The authors suggest adjusting K and S to balance performance and efficiency.
  • Hyperparameter sensitivity: GRAND’s performance increases as the consistency-regularization coefficient λ grows, while GRAND and its variants peak at DropNode probability δ = 0.5.The paper attributes the δ result to more stochastic random-propagation augmentations that improve generalization.
  • Augmentation comparison: GRAND consistently outperforms GRAND_dropout across propagation-step values on Cora, Citeseer, and Pubmed.This comparison suggests DropNode is more suitable than GRAND_dropout for graph data augmentation.
  • Over-smoothing analysis: GRAND achieves better performance than GRAND_GCN and GRAND_GAT, while its MADGap and classification accuracy increase across propagation steps.The analysis links the variants’ weaker performance to GCN and GAT performing worse than MLP within GRAND’s framework.
  • Label-rate robustness: GRAND consistently outperforms GCN and GAT across all tested label rates on three benchmark datasets.Each label-rate setting uses 10 random data splits and 10 random-initialization trials per split.
Loading 2005.11079v4…