Provable Training for Graph Contrastive Learning

Yue Yu, Xiao Wang, Mengmei Zhang, Nian Liu, Chuan Shi

Introduction

Graph Contrastive Learning (GCL) has emerged as a dominant paradigm for self-supervised node representation learning. By maximizing the similarity between different augmented views of the same node (positive pairs) and minimizing it against other nodes (negative pairs), GCL models learn robust embeddings without manual labels. However, a significant hurdle remains: imbalanced training. Real-world graphs are heterogeneous, and standard GCL often fails to treat all nodes equally. Some nodes are "easy" to learn, while others are highly sensitive to the specific random augmentations applied, leading to inconsistent performance across the graph.

The Challenge of Imbalanced GCL

The core issue lies in the variance of the contrastive loss across different nodes. In popular frameworks like GRACE, GCA, and ProGCL, the InfoNCE loss distribution often exhibits high variance and a long tail. This indicates that a subset of nodes consistently violates the contrastive principle, resulting in poor embedding quality for those specific nodes.

Distribution of InfoNCE loss across nodes for popular GCL methods, highlighting training imbalance.

Current methods typically treat all nodes with equal weight during training. This "one-size-fits-all" approach ignores the fact that nodes with different structural properties (like degree) react differently to graph perturbations such as edge dropping or feature masking.

Methodology: PrOvable Training (POT)

To address this, the authors propose PrOvable Training (POT). The framework introduces a novel metric called node compactness, which quantifies the "worst-case" performance of a node across all possible augmentations within a predefined range.

Bound Propagation

Calculating the exact worst-case performance is computationally intractable. POT overcomes this by leveraging bound propagation, a technique originally developed for neural network verification. The process involves:

  1. Continuous Relaxation: The discrete space of graph augmentations (e.g., edge presence/absence) is relaxed into a continuous space to enable gradient-based optimization.
  2. Linear Relaxation: Non-linearities within the Graph Neural Network (GNN) encoder, such as ReLU activations, are approximated using linear upper and lower bounds.
  3. Provable Regularization: These derived bounds are integrated into the training objective as a regularization term. This forces the model to minimize the worst-case loss, ensuring that even under the most challenging allowed perturbations, the node embeddings remain "compact"—close to their positives and far from their negatives.

Experimental Evaluation

The POT framework was tested as a plugin for several state-of-the-art GCL models across eight benchmark datasets, including citation networks (Cora, CiteSeer), social networks (Flickr, BlogCatalog), and e-commerce graphs (Amazon Computers).

Key Results

The addition of POT consistently yielded performance improvements. For instance, on the BlogCatalog dataset, POT boosted the Micro-F1 score of GRACE from 70.5% to 72.4%. Beyond raw accuracy, POT significantly improved the stability of the learning process.

Comparison of node compactness over training epochs between standard COSTA and COSTA-POT.

As shown in the training dynamics, models equipped with POT achieve higher and more stable node compactness compared to their standard counterparts. This suggests that the provable regularization effectively guides the model toward more robust representations early in the training process.

Discussion and Insights

A key insight from the study is the relationship between node degree and training sensitivity. In uniform augmentation strategies, higher-degree nodes tend to be more robust. However, adaptive strategies like GCA, which drop edges more aggressively for high-degree nodes, can inadvertently make these nodes harder to train. POT acts as a balancing force, managing these trade-offs by enforcing a minimum level of compactness for all nodes regardless of their local topology.

Conclusion and Future Work

POT provides a theoretically grounded solution to the imbalance problem in GCL. By optimizing for the worst-case scenario through bound propagation, it ensures that all nodes are robustly trained.

Future research directions include extending the theoretical framework to handle feature-based augmentations and adapting the bound propagation rules for more advanced architectures like Graph Transformers. Additionally, exploring the optimal tuning of the regularization hyperparameter across different graph domains remains an open area for optimization.

Summary updated

Abstract

Graph Contrastive Learning (GCL) has emerged as a popular training approach for learning node embeddings from augmented graphs without labels. Despite the key principle that maximizing the similarity between positive node pairs while minimizing it between negative node pairs is well established, some fundamental problems are still unclear. Considering the complex graph structure, are some nodes consistently well-trained and following this principle even with different graph augmentations? Or are there some nodes more likely to be untrained across graph augmentations and violate the principle? How to distinguish these nodes and further guide the training of GCL? To answer these questions, we first present experimental evidence showing that the training of GCL is indeed imbalanced across all nodes. To address this problem, we propose the metric "node compactness", which is the lower bound of how a node follows the GCL principle related to the range of augmentations. We further derive the form of node compactness theoretically through bound propagation, which can be integrated into binary cross-entropy as a regularization. To this end, we propose the PrOvable Training (POT) for GCL, which regularizes the training of GCL to encode node embeddings that follows the GCL principle better. Through extensive experiments on various benchmarks, POT consistently improves the existing GCL approaches, serving as a friendly plugin.
BibTeX
@inproceedings{yu2023provable,
  author = {Yue Yu and Xiao Wang and Mengmei Zhang and Nian Liu and Chuan Shi},
  title = {{Provable Training for Graph Contrastive Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=Xasl21tSOf},
}
Figure