Multi-Level Graph Contrastive Learning

Pengpeng Shao, Tong Liu, Dawei Zhang, Jianhua Tao, Feihu Che, Guohua Yang

TL;DR

Multi-Level Graph Contrastive Learning (MLGCL) is a new self-supervised framework that learns robust graph representations without requiring expensive human labels. By contrasting a graph's original topology with a feature-derived $k$-Nearest Neighbor ($k$NN) graph across both node and graph levels, MLGCL effectively captures high-order proximity and mitigates structural noise, outperforming state-of-the-art methods on multiple benchmarks.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) have become the go-to solution for analyzing graph-structured data. However, most powerful GNNs rely heavily on supervised learning, which demands massive amounts of labeled data. In specialized fields like biology or academic citation networks, acquiring these labels requires expensive domain expertise.

Self-supervised contrastive learning has emerged as a viable alternative, but existing approaches have a major flaw: they rely on simple data augmentations like randomly dropping nodes, perturbing edges, or masking attributes.

Figure 1: Four data augmentations for graphs. The last one is the the proposed data augmentation scheme in

As shown in Figure 1, traditional methods (1, 2, 3) modify the graph blindly. Because real-world graphs are already noisy and often contain erroneous connections (disassortativity), these standard perturbations can destroy vital semantic information. The authors set out to create an augmentation strategy that preserves intrinsic high-order structures without destroying the graph's underlying meaning.

Methods

The authors introduce MLGCL, a framework built on two core innovations: Feature-Topology Space Views and a Multi-Level Contrastive Loss.

Figure 2: The framework of multi-level graph contrastive learning.

1. Feature-Topology Space Views

Instead of randomly altering the input graph, MLGCL feeds the data into two distinct structural pathways:

  • Topology View: The original graph structure, representing first-order approximations and immediate connections.
  • Feature Space View ($k$NN Graph): The model uses a shared GNN encoder to extract node features, calculates their cosine similarity, and constructs a $k$-Nearest Neighbor ($k$NN) graph. This view captures high-order proximity and groups semantically similar nodes together, even if they aren't directly connected in the raw data.

2. Multi-Level Contrastive Mode

Once the two views are established, the framework applies a joint contrastive loss function at two distinct granularities:

  • Node-level contrast ($\mathcal{L}_{node}$): Maximizes the agreement between the embeddings of the same node across the topology and $k$NN views.
  • Graph-level contrast ($\mathcal{L}_{graph}$): Maximizes the agreement between the global graph representations of the two views, using a pooling layer and shuffling techniques to generate negative samples.

The final objective function balances both local similarity and global semantic consistency: $$\mathcal{L} = \mathcal{L}_{node} + \lambda\mathcal{L}_{graph}$$

Datasets

The framework was evaluated on seven diverse, well-established graph benchmarks:

  • Citation Networks: Cora, Citeseer, and PubMed (where nodes are papers and edges are citations).
  • Hyperlink Network: WikiCS (articles and their hyperlinks).
  • Coauthor Network: CoauthorCS (authors connected by co-authorship).
  • Web Pages Network: Cornell (webpages and hyperlinks).
  • Co-occurrence Network: Actor (actors appearing on the same Wikipedia page).

Key Insights and Ideas

  • The $k$NN Graph as a Denoising Tool: Real-world graphs often connect nodes of different classes by mistake. By dynamically generating a $k$NN graph from encoded features, MLGCL uncovers latent community structures that the raw, noisy topology completely misses.
  • Local and Global Synergy: The ablation studies reveal that optimizing for node-level similarity or graph-level similarity alone yields sub-optimal results. Local and global contrastive modes complement each other, forcing the GNN encoder to learn representations that are robust at both micro and macro scales.

Key Results

MLGCL was tested against a wide array of unsupervised, self-supervised, and fully supervised baselines on a node classification task.

  • Outperforming Self-Supervised State-of-the-Art: MLGCL consistently outperformed top-tier self-supervised models. For example, it beat GCA and GMI by 4% and 1.4% respectively on the Cora dataset. On the Cornell dataset, it outperformed MVGRL by 4.7% and GCA by 13.4%.
  • Beating Supervised Models: Remarkably, despite receiving zero label information during training, MLGCL frequently achieved higher classification accuracy than fully supervised counterparts like standard GCNs and GATs across multiple datasets.

Limitations and Future Work

While the paper demonstrates impressive empirical results, it leaves a few practical questions open:

  • Computational Complexity: Constructing a $k$NN graph requires calculating pairwise similarities between node features. For massive graphs with millions of nodes, this operation can become a computational bottleneck ($O(N^2)$), a challenge the authors do not explicitly address.
  • Hyperparameter Sensitivity: The performance relies on tuning the number of neighbors ($k$) and the loss balancing coefficient ($\lambda$), which may vary significantly depending on the graph's density and domain.

Future research could look into scaling this feature-space contrastive approach to large-scale industrial graphs using approximate nearest neighbor search algorithms.

Summary updated

Abstract

Graph representation learning has attracted a surge of interest recently, whose target at learning discriminant embedding for each node in the graph. Most of these representation methods focus on supervised learning and heavily depend on label information. However, annotating graphs are expensive to obtain in the real world, especially in specialized domains (i.e. biology), as it needs the annotator to have the domain knowledge to label the graph. To approach this problem, self-supervised learning provides a feasible solution for graph representation learning. In this paper, we propose a Multi-Level Graph Contrastive Learning (MLGCL) framework for learning robust representation of graph data by contrasting space views of graphs. Specifically, we introduce a novel contrastive view - topological and feature space views. The original graph is first-order approximation structure and contains uncertainty or error, while the $k$NN graph generated by encoding features preserves high-order proximity. Thus $k$NN graph generated by encoding features not only provide a complementary view, but is more suitable to GNN encoder to extract discriminant representation. Furthermore, we develop a multi-level contrastive mode to preserve the local similarity and semantic similarity of graph-structured data simultaneously. Extensive experiments indicate MLGCL achieves promising results compared with the existing state-of-the-art graph representation learning methods on seven datasets.
BibTeX
@inproceedings{shao2021multi,
  author = {Pengpeng Shao and Tong Liu and Dawei Zhang and Jianhua Tao and Feihu Che and Guohua Yang},
  title = {{Multi-Level Graph Contrastive Learning}},
  booktitle = {Neurocomputing},
  year = {2021},
  doi = {10.1016/j.neucom.2023.127101},
}
Figure