Equivalence is All: A Unified View for Self-supervised Graph Learning

Node equivalence is common in graphs, such as computing networks, encompassing automorphic equivalence (preserving adjacency under node permutations) and attribute equivalence (nodes with identical attributes). Despite their importance for learning node representations, these equivalences are largely ignored by existing graph models. To bridge this gap, we propose a GrAph self-supervised Learning framework with Equivalence (GALE) and analyze its connections to existing techniques. Specifically, we: 1) unify automorphic and attribute equivalence into a single equivalence class; 2) enforce the equivalence principle to make representations within the same class more similar while separating those across classes; 3) introduce approximate equivalence classes with linear time complexity to address the NP-hardness of exact automorphism detection and handle node-feature variation; 4) analyze existing graph encoders, noting limitations in message passing neural networks and graph transformers regarding equivalence constraints; 5) show that graph contrastive learning are a degenerate form of equivalence constraint; and 6) demonstrate that GALE achieves superior performance over baselines.

In many networks, like social circles, some "nodes" (or points) are essentially interchangeable. They might have identical connection patterns to their neighbors or share the same characteristics. However, current AI methods for learning from these networks often overlook these crucial similarities, treating most distinct nodes as entirely different, even if they play very similar roles. This is like not recognizing that two identical tools should be treated similarly just because they are separate objects.We've developed a new AI learning approach called GALE that embraces this idea of "node equivalence." GALE first identifies groups of nodes that are effectively the same, considering both their structural position in the network and their individual features. To handle real-world complexities where perfect sameness is rare or hard to find, it cleverly uses efficient approximations. GALE then teaches the AI that nodes within the same "equivalence group" should be understood as being very similar, while nodes in different groups should remain distinct.This approach allows AI to learn more accurate and meaningful information from network data. By recognizing and using these fundamental equivalences, GALE helps AI understand the underlying structure and function of networks much better, outperforming existing methods in our tests.