Rethinking Graph Contrastive Learning through Relative Similarity Preservation
This addresses a fundamental limitation in graph representation learning for researchers and practitioners working with graph-structured data.
The paper tackles the problem that graph contrastive learning (GCL) faces fundamental challenges when applying computer vision paradigms to graphs, due to their discrete, non-Euclidean nature. The authors discovered a universal pattern of label consistency decay with structural distance across 11 real-world graphs, proposed RELGCL to preserve relative similarity patterns, and demonstrated consistent outperformance over 20 existing approaches across both homophily and heterophily graphs.
Graph contrastive learning (GCL) has achieved remarkable success by following the computer vision paradigm of preserving absolute similarity between augmented views. However, this approach faces fundamental challenges in graphs due to their discrete, non-Euclidean nature -- view generation often breaks semantic validity and similarity verification becomes unreliable. Through analyzing 11 real-world graphs, we discover a universal pattern transcending the homophily-heterophily dichotomy: label consistency systematically diminishes as structural distance increases, manifesting as smooth decay in homophily graphs and oscillatory decay in heterophily graphs. We establish theoretical guarantees for this pattern through random walk theory, proving label distribution convergence and characterizing the mechanisms behind different decay behaviors. This discovery reveals that graphs naturally encode relative similarity patterns, where structurally closer nodes exhibit collectively stronger semantic relationships. Leveraging this insight, we propose RELGCL, a novel GCL framework with complementary pairwise and listwise implementations that preserve these inherent patterns through collective similarity objectives. Extensive experiments demonstrate that our method consistently outperforms 20 existing approaches across both homophily and heterophily graphs, validating the effectiveness of leveraging natural relative similarity over artificial absolute similarity.