RoSA: A Robust Self-Aligned Framework for Node-Node Graph Contrastive Learning

Yun Zhu, Jianhao Guo, Fei Wu, Siliang Tang

Introduction

Graph Contrastive Learning (GCL) has emerged as a dominant paradigm for unsupervised representation learning on graphs. By maximizing the agreement between different augmented "views" of the same graph, GCL models learn to capture essential structural and semantic features. However, a significant limitation persists in current methodologies: the requirement for aligned views. Most existing frameworks assume that the set of nodes in one view must be identical to the set of nodes in the other. This assumption fails in real-world scenarios where graphs are dynamic, or when computational constraints necessitate comparing local subgraphs sampled independently.

To address this, we present RoSA (Robust Self-Aligned framework), a novel approach that enables node-node contrastive learning across non-aligned views. By leveraging the Earth Mover’s Distance (EMD) and unsupervised adversarial training, RoSA achieves state-of-the-art performance across diverse graph types, including homophilous, non-homophilous, and dynamic structures.

The Challenge of Non-Alignment

In standard GCL, similarity is typically measured using one-to-one metrics like cosine similarity. This works only if node $i$ in View A corresponds exactly to node $i$ in View B. In practice, this restriction limits the diversity of augmentations. For instance, if we sample two different local neighborhoods via random walks, the resulting subgraphs may have overlapping but non-identical node sets. Standard GCL cannot effectively process these "unaligned" views because there is no direct correspondence between nodes to optimize. RoSA bridges this gap by treating node sets as distributions rather than fixed sequences.

The RoSA Framework

RoSA introduces three core innovations to facilitate robust, non-aligned learning:

1. Non-Aligned Sub-sampling

Rather than augmenting the entire graph, RoSA employs "Random Walk with Restart" (RWR) to sample subgraphs around central nodes. This strategy naturally generates views with varying node sets and local structural contexts. By exposing the model to these diverse, non-aligned perspectives, RoSA forces the encoder to learn more generalized features that are not dependent on a specific global node indexing.

2. Graph-based Earth Mover’s Distance (g-EMD)

The mathematical heart of RoSA is the g-EMD. Earth Mover’s Distance is a metric that calculates the minimum cost to transform one distribution into another. RoSA treats the node embeddings within two different views as discrete distributions.

Crucially, RoSA incorporates topology distance (the number of hops between nodes) into the EMD cost matrix. This ensures that the "self-alignment" process considers both feature similarity and structural positioning. By minimizing the g-EMD, the model learns to align nodes that are semantically and structurally similar, even without a predefined one-to-one mapping.

3. Unsupervised Adversarial Training (AT)

To further enhance robustness, RoSA incorporates an adversarial training step. During the training process, the framework calculates small, "worst-case" perturbations to node features designed to maximize the contrastive loss. By training the encoder to remain invariant to these adversarial attacks, RoSA develops representations that are highly resilient to noise and structural variations.

Experimental Results

RoSA was evaluated against ten public benchmarks, spanning various graph characteristics:

  • Homophilous Graphs (Cora, Citeseer, Pubmed, DBLP): RoSA consistently outperformed established GCL methods. Notably, on the Cora dataset, RoSA achieved 84.5% accuracy, surpassing not only other unsupervised methods but also supervised Graph Convolutional Networks (GCNs), which reached 82.8%.
  • Non-homophilous Graphs (Texas, Wisconsin, Cornell): On the Texas dataset, RoSA achieved 71.1% accuracy using an MLP encoder, outperforming GRACE (69.8%), demonstrating its ability to handle graphs where connected nodes often share different labels.
  • Dynamic and Inductive Graphs: In the CIAW scenario—a dynamic graph environment specifically modified to test non-alignment (where nodes are added or deleted over time)—RoSA achieved 73.2%* accuracy. Many traditional GCL methods are fundamentally unable to operate in this setting due to their reliance on strict node alignment.

Discussion and Future Work

RoSA represents a significant shift in GCL by removing the necessity for aligned views, thereby unlocking the ability to process dynamic and partially observed graphs more effectively.

However, the use of EMD introduces higher computational complexity compared to simple cosine similarity. While the Sinkhorn algorithm provides an efficient approximation, scaling RoSA to trillion-edge graphs remains a challenge for future optimization. Additionally, while RoSA currently uses a static GNN encoder, future iterations could integrate temporal GNNs to better capture time-series data in dynamic environments.

In conclusion, RoSA’s ability to "self-align" through g-EMD and its resilience via adversarial training set a new benchmark for robust, flexible graph representation learning.

Summary updated

BibTeX
@inproceedings{zhu2022rosa,
  author = {Yun Zhu and Jianhao Guo and Fei Wu and Siliang Tang},
  title = {{RoSA: A Robust Self-Aligned Framework for Node-Node Graph Contrastive Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=yJOS7t8Nug},
}
Figure