Contrastive Adaptive Propagation Graph Neural Networks for Efficient Graph Learning

Jun Hu, Shengsheng Qian, Quan Fang, Changsheng XuarXiv 2021 · arXiv

Introduction

Graph Neural Networks (GNNs) have revolutionized the processing of graph-structured data by aggregating information from local neighborhoods. However, capturing high-order information—neighbors multiple hops away—remains a challenge. Traditional approaches often rely on stacking multiple layers, which can lead to over-smoothing, where node representations become indistinguishable. While methods like Personalized PageRank (PPR) allow for deeper propagation without stacking, they typically use fixed, hand-tuned coefficients that do not adapt to specific dataset characteristics.

To address these limitations, the authors introduce Contrastive Adaptive Propagation Graph Neural Networks (CAPGNN). This framework makes high-order neighbor propagation both learnable and efficient by combining an attention-based coefficient model with a self-supervised, "negative-free" contrastive loss.

Methodology

The CAPGNN framework is built upon three primary technical pillars designed to balance computational efficiency with model adaptability:

  1. Adaptive Extended Propagation: Unlike models with fixed propagation schemes, CAPGNN utilizes a coefficient-attention model. While it initializes weights based on PPR, it allows the network to learn and dynamically adjust the influence of local versus high-order neighbors during the training process.
  2. Efficient Power Iterations: To maintain scalability, propagation is implemented as a series of sparse matrix-vector multiplications (power iterations). This approach avoids the memory overhead of dense matrix operations while enabling the model to reach distant neighbors (e.g., $K=10$ hops).
  3. Negative-free Entropy-aware Contrastive Loss: To leverage unlabeled data, CAPGNN employs self-supervised learning. It generates two augmented views of the graph via dropout and encourages representation consistency across them. This "negative-free" approach eliminates the need for large memory banks of negative samples and includes a sharpening technique to promote confident, low-entropy predictions.
The CAPGNN architecture featuring adaptive propagation and contrastive loss.

The authors offer two variants: CAPGCN, which utilizes static graph structures, and CAPGAT, which incorporates dynamic, attention-based structures.

Key Results and Insights

CAPGNN was evaluated on standard benchmarks, including citation networks (Cora, CiteSeer, Pubmed) and e-commerce networks (Amazon-Computers, Amazon-Photo). The model consistently matched or outperformed state-of-the-art baselines such as GCN, GAT, APPNP, and GRAND.

Performance comparison of CAPGNN variants against baselines across three citation datasets.

Beyond Fixed Heuristics

A central finding is that learnable coefficients allow the model to discover optimal propagation patterns for different graphs. For instance, visualization of learned coefficients showed that while traditional methods like APPNP may over-weight distant hops, CAPGNN learns a smoother, decaying distribution tailored to the data. This adaptability is key to its superior performance.

Efficiency and Robustness

By decomposing the propagation polynomial into power iterations, CAPGNN achieves the representational power of deep GNNs with the computational footprint of shallow ones. Furthermore, the model demonstrated steady performance once the number of iterations $K$ reached 10, indicating lower sensitivity to hyperparameter tuning compared to stacked-layer architectures.

Conclusion

CAPGNN demonstrates that making propagation schemes learnable and adaptive significantly enhances GNN performance without sacrificing efficiency. While the low-entropy assumption for unlabeled data may vary in effectiveness across datasets (e.g., requiring tuning on Pubmed), the framework provides a robust foundation for high-order graph learning. Future research will explore applying this adaptive propagation to recommendation systems and large-scale social network analysis.

Summary updated

Abstract

Graph Neural Networks (GNNs) have achieved great success in processing graph data by extracting and propagating structure-aware features. Existing GNN research designs various propagation schemes to guide the aggregation of neighbor information. Recently the field has advanced from local propagation schemes that focus on local neighbors towards extended propagation schemes that can directly deal with extended neighbors consisting of both local and high-order neighbors. Despite the impressive performance, existing approaches are still insufficient to build an efficient and learnable extended propagation scheme that can adaptively adjust the influence of local and high-order neighbors. This paper proposes an efficient yet effective end-to-end framework, namely Contrastive Adaptive Propagation Graph Neural Networks (CAPGNN), to address these issues by combining Personalized PageRank and attention techniques. CAPGNN models the learnable extended propagation scheme with a polynomial of a sparse local affinity matrix, where the polynomial relies on Personalized PageRank to provide superior initial coefficients. In order to adaptively adjust the influence of both local and high-order neighbors, a coefficient-attention model is introduced to learn to adjust the coefficients of the polynomial. In addition, we leverage self-supervised learning techniques and design a negative-free entropy-aware contrastive loss to explicitly take advantage of unlabeled data for training. We implement CAPGNN as two different versions named CAPGCN and CAPGAT, which use static and dynamic sparse local affinity matrices, respectively. Experiments on graph benchmark datasets suggest that CAPGNN can consistently outperform or match state-of-the-art baselines. The source code is publicly available at https://github.com/hujunxianligong/CAPGNN.
BibTeX
@misc{hu2021contrastive,
  author = {Jun Hu and Shengsheng Qian and Quan Fang and Changsheng Xu},
  title = {{Contrastive Adaptive Propagation Graph Neural Networks for Efficient Graph Learning}},
  year = {2021},
  eprint = {2112.01110},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.01110},
}
Figure