Learning Robust Graph Neural Networks with Limited Supervision

Abdullah Alchihabi, Yuhong GuoAISTATS 2023 · OpenReview

Abstract

Graph Neural Networks (GNNs) typically require a substantial number of labeled nodes and a reliable graph connectivity structure to achieve optimal performance in semi-supervised node classification. However, real-world datasets often suffer from label scarcity and structural noise, such as missing or adversarial edges. This paper proposes the Dual GNN framework, an end-to-end learning approach that enhances GNN robustness by incorporating an auxiliary module for graph reconstruction. By leveraging fine-grained spectral clustering to rebuild the graph topology, the framework maintains high classification accuracy even when structural information is severely degraded or labels are extremely limited.

Introduction

While Graph Neural Networks have revolutionized the analysis of non-Euclidean data, they remain sensitive to the quality and quantity of their inputs. Standard GNNs rely on a "message passing" mechanism that propagates information across edges; when these edges are noisy or missing, the mechanism falters. Furthermore, in scenarios with very few labels, GNNs tend to overfit to the immediate neighborhoods of known nodes. This research addresses these vulnerabilities by introducing a dual-learning paradigm that dynamically refines the graph structure during training.

The Dual GNN Framework

The core of the proposed solution is a dual-module architecture designed to mitigate the impact of noisy data.

The Dual GNN learning framework architecture, featuring primary and auxiliary modules with graph reconstruction.

As illustrated in Figure 1, the framework consists of:

  1. Primary Module: A standard GNN (e.g., GCN or GAT) that processes the original, potentially corrupted input graph to generate initial node embeddings.
  2. Auxiliary Module: This module performs fine-grained spectral clustering on the embeddings. Unlike traditional clustering, it uses a Multi-Layer Perceptron (MLP) to assign nodes to a large number of clusters ($K$), capturing global geometric patterns.
  3. Graph Reconstruction: A new adjacency matrix is constructed based on the Pearson correlation of these cluster assignments. This reconstructed graph serves as a denoised version of the original, filling in missing links and filtering out noise.
  4. Joint Optimization: The system is trained end-to-end by minimizing a total loss function that combines classification losses from both modules with a spectral clustering loss. This allows the primary GNN to benefit from the cleaner, reconstructed topology of the auxiliary module.

Experimental Evaluation

The framework was evaluated on standard benchmarks, including the Cora and CiteSeer citation networks and the Chameleon Wikipedia dataset. To simulate challenging real-world conditions, the researchers tested the model under extreme label scarcity (as few as 2 labels per class) and severe structural corruption (up to 95% edge deletion).

Key Results and Robustness

The Dual GNN framework consistently outperformed state-of-the-art robust GNN methods across various noise levels.

Performance of Dual GCN compared to baselines under varying levels of edge deletion on Cora and CiteSeer datasets.

As shown in Figure 6, the model exhibits remarkable resilience to structural degradation. For instance, on the CiteSeer dataset, even when 95% of edges were deleted, the Dual GCN maintained an accuracy of 61.4%, significantly higher than the standard GCN's 54.9%.

In scenarios of extreme label scarcity, the benefits were equally pronounced. On the Cora dataset with only 2 labels per class, the Dual GCN achieved 71.1% accuracy, a 7.6% improvement over the baseline GCN. This suggests that the auxiliary graph provides essential "shortcuts" that allow label information to propagate more effectively across the entire network, preventing the local overfitting common in traditional models.

Conclusion

The Dual GNN framework offers a robust solution for node classification in imperfect data environments. By using spectral clustering as a denoising and reconstruction tool, it effectively re-engineers graph topology to support better message passing. While the framework introduces some computational overhead and hyperparameter sensitivity regarding cluster counts, its model-agnostic nature allows it to enhance a wide variety of existing GNN architectures. Future work will focus on improving the scalability of the spectral clustering component for massive-scale graphs.

Summary updated

Abstract

Graph Neural Networks (GNNs) require a relatively large number of labeled nodes and a reliable/uncorrupted graph connectivity structure to obtain good performance on the semi-supervised node classi...
BibTeX
@inproceedings{alchihabi2023learning,
  author = {Abdullah Alchihabi and Yuhong Guo},
  title = {{Learning Robust Graph Neural Networks with Limited Supervision}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=PneL_9A0-fQ},
}
Figure