Sub-graph Contrast for Scalable Self-Supervised Graph Representation Learning

Yizhu Jiao, Yun Xiong, Jiawei Zhang, Yao Zhang, Tianqi Zhang, Yangyong Zhu

Abstract

Self-supervised Graph Neural Networks (GNNs) often struggle with scalability and capturing the optimal structural context for node identity. Traditional methods like Deep Graph Infomax (DGI) and Graphical Mutual Information (GMI) either require full-graph processing or focus on overly local (1-hop) neighborhoods. We present SUBG-CON (Sub-graph Contrast), a scalable framework that leverages regional subgraphs as data augmentations. By maximizing the agreement between a central node's embedding and its regional subgraph representation via a margin triplet loss, SUBG-CON achieves state-of-the-art performance. Notably, it offers up to a 160x speedup over existing methods and significantly reduces memory overhead, enabling efficient processing of large-scale networks like Reddit.

Introduction: The Scalability and Context Gap

Graph Neural Networks (GNNs) have revolutionized relational data processing, yet they face significant hurdles when scaling to massive networks with billions of nodes. Most existing GNNs require the complete adjacency matrix as input, which is computationally prohibitive for large-scale graphs. Furthermore, high-quality labels are often scarce, necessitating self-supervised approaches.

Existing self-supervised methods like DGI and GMI suffer from two primary flaws: they often operate on the full graph structure and exhibit structural bias. They tend to focus either on the "global" graph level or very "local" (1-hop) neighborhoods, missing the critical "regional" context that defines a node's identity in a complex network.

Comparison of SUBG-CON with DGI and GMI, highlighting the focus on regional context.

Methodology: SUBG-CON

SUBG-CON addresses these limitations by treating subgraph sampling as a form of data augmentation, focusing on the "regional" sweet spot of node correlation.

Regional Subgraph Sampling

Instead of processing the entire graph, SUBG-CON uses Personalized PageRank (PPR) to identify the top-$k$ most important neighbors for a central node. This captures a regional neighborhood that is more informative than a simple 1-hop slice but far more efficient than the full graph.

Encoding and Contrastive Learning

The framework employs a standard GNN encoder (e.g., GCN) to process the sampled subgraphs. A readout function aggregates node embeddings into a single subgraph-level representation. The core objective is to maximize the agreement between a central node's embedding and its own regional subgraph's embedding (the positive pair) while distinguishing it from shuffled or "fake" subgraphs (negative pairs).

The SUBG-CON pipeline: from subgraph sampling and encoding to contrastive loss calculation.

Margin Triplet Loss and Parallelization

Unlike methods using binary cross-entropy, SUBG-CON utilizes a margin triplet loss. This approach is more realistic for large networks where subgraphs often overlap, as it avoids forcing an absolute binary separation. Furthermore, because the model learns from independent subgraphs, the workload is naturally decoupled from the full graph structure, allowing for easy parallelization across multiple GPUs.

Experimental Results

SUBG-CON was evaluated on six benchmarks, ranging from small citation networks (Cora, Citeseer, Pubmed) to large-scale networks (PPI, Flickr, Reddit).

  • Performance: On the Reddit dataset, SUBG-CON achieved a 95.2% Micro-F1 score, outperforming both supervised GCN (93.3%) and self-supervised DGI (94.0%).
  • Efficiency: The speed gains are substantial. On Reddit, SUBG-CON finished training in 25 seconds, compared to 4,071 seconds for DGI—a 160x speedup.
  • Memory Footprint: On Pubmed, SUBG-CON utilized only 975MB of memory, whereas GMI required over 12,000MB.
  • Sample Efficiency: A key finding was that peak performance can be reached with a relatively small number of sampled subgraphs (e.g., 50 subgraphs for the Reddit dataset).

Conclusion

SUBG-CON demonstrates that regional context is the "sweet spot" for self-supervised graph representation learning. By decoupling node representations from the full graph structure and focusing on regional contrast, the framework achieves superior accuracy with unprecedented efficiency and scalability. Future work may explore more sophisticated subgraph corruption strategies and the application of regional representations to tasks beyond node classification, such as link prediction.

Summary updated

BibTeX
@inproceedings{jiao2020sub,
  author = {Yizhu Jiao and Yun Xiong and Jiawei Zhang and Yao Zhang and Tianqi Zhang and Yangyong Zhu},
  title = {{Sub-graph Contrast for Scalable Self-Supervised Graph Representation Learning}},
  booktitle = {ICDM},
  year = {2020},
  doi = {10.1109/icdm50108.2020.00031},
}
Figure