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

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