Abstract
Graph contrastive learning has gained significant progress recently. However, existing works have rarely explored non-aligned node-node contrasting. In this paper, we propose a novel graph contrastive learning method named RoSA that focuses on utilizing non-aligned augmented views for node-level representation learning. First, we leverage the earth mover's distance to model the minimum effort to transform the distribution of one view to the other as our contrastive objective, which does not require alignment between views. Then we introduce adversarial training as an auxiliary method to increase sampling diversity and enhance the robustness of our model. Experimental results show that RoSA outperforms a series of graph contrastive learning frameworks on homophilous, non-homophilous and dynamic graphs, which validates the effectiveness of our work. To the best of our awareness, RoSA is the first work focuses on the non-aligned node-node graph contrastive learning problem.
Introduction: The Alignment Constraint in Graph Contrastive Learning
Graph Contrastive Learning (GCL) has emerged as a powerful paradigm for unsupervised representation learning on graphs. The standard approach involves generating two augmented views of a graph and maximizing the agreement between representations of the same instance (positive pairs) while minimizing it for different instances (negative pairs).
However, a significant bottleneck in current node-level GCL methods is the requirement for alignment. In traditional frameworks, a positive pair must consist of views containing the exact same set of nodes to allow for one-to-one comparison. This constraint limits the flexibility of data augmentation, as subgraphs of different sizes or compositions cannot be directly contrasted. Furthermore, in dynamic graphs where nodes frequently appear or disappear, strict alignment is often impossible to maintain.
The RoSA Framework
To overcome these limitations, we introduce RoSA (Robust Self-Aligned framework), the first method designed specifically for non-aligned node-node graph contrastive learning. RoSA enables the comparison of subgraphs with differing node sets by reimagining the contrastive objective through the lens of optimal transport.
1. Non-Aligned Sub-Sampling
RoSA utilizes Random Walk with Restart (RWR) to sample local neighborhoods (subgraphs) centered around a target node. Unlike previous methods, two different RWR samples from the same center node are treated as a positive pair, even if their node sets are entirely disjoint or of different sizes. This provides a much richer and more varied set of "views" for the model to learn from.
2. Graph-based Earth Mover's Distance (g-EMD)
Because the sampled views are non-aligned, traditional similarity metrics like cosine similarity or Jensen-Shannon divergence cannot be applied directly. RoSA treats the node embeddings within each view as a discrete probability distribution. We then employ the Earth Mover's Distance (EMD)—a metric from optimal transport—to calculate the minimum cost required to transform the distribution of one view into the other.
To ensure the model respects the graph's underlying geometry, we introduce a Rectified Cost Matrix. The cost of "moving" mass between two nodes is weighted by their topological distance (shortest path hop count). This ensures that structural proximity is preserved in the learned embedding space.
3. Unsupervised Adversarial Training
To further enhance robustness and generalization, RoSA incorporates an unsupervised adversarial training (AT) component. By introducing small, calculated perturbations to the node features during the encoding process, we create "harder" contrastive tasks. This min-max optimization forces the encoder to capture more resilient structural features that are invariant to noise.
Experimental Evaluation
We evaluated RoSA across ten benchmark datasets spanning homophilous, heterophilous, and dynamic graph structures.
- Homophilous Graphs: On datasets like Cora and Pubmed, RoSA consistently outperformed state-of-the-art GCL baselines such as GRACE and GCA, achieving up to 87.1% accuracy on Pubmed.
- Heterophilous Graphs: RoSA showed significant gains on non-homophilous datasets (e.g., Wisconsin, Texas), where traditional GNNs often struggle. By focusing on local neighborhood distributions rather than strict node alignment, RoSA captures structural patterns more effectively.
- Dynamic Graphs: In scenarios simulating evolving networks (CIAW*), where nodes appear and disappear, RoSA maintained high performance (73.2% accuracy) while traditional aligned methods failed to adapt.
Conclusion
RoSA represents a paradigm shift in graph contrastive learning by breaking the alignment constraint. By combining non-aligned sub-sampling with a g-EMD objective and adversarial training, RoSA provides a robust and flexible framework for node-level representation learning. Future work will explore the integration of temporal encoders to further enhance performance on rapidly evolving dynamic graphs.
Summary updated