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

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

Speakers: Yejiang Wang, Yuhai Zhao, Zhengkui Wang, Ling Li, Jiapu Wang, Fangting Li, Miaomiao Huang, Shirui Pan, Xingwei Wang

Conference: ICML 2025

YouTube: https://slideslive.com/39044063

Overview

This talk introduces GALE (Graph Automorphic Equivalence Learning), a novel self-supervised learning framework for graph-structured data that unifies and leverages the fundamental concept of node equivalence. Presented by one of the co-authors on behalf of the first author, Yejiang Wang, due to unforeseen circumstances, the work highlights that real-world networks inherently possess various forms of node equivalence—from perfect structural symmetries in molecules to shared functional roles in social or biological networks. GALE posits that an ideal graph representation model should learn embeddings that reflect these equivalences, pushing equivalent nodes closer in the embedding space while separating non-equivalent ones.

The core contribution of GALE is its dual-branch architecture, which explicitly identifies node equivalence partitions based on both graph structure and node attributes. These partitions then guide a standard Graph Neural Network (GNN) encoder through a novel equivalence loss, regularizing the learning process to produce representations that inherently respect these underlying symmetries. Recognizing the computational challenges of exact equivalence detection in large, noisy graphs, GALE also proposes efficient approximate methods, making the framework scalable and practical. This unified perspective not only yields state-of-the-art performance across various graph learning tasks but also offers profound insights into the working mechanisms and limitations of existing models like Message Passing Neural Networks (MPNNs), Graph Transformers, and Graph Contrastive Learning (GCL).

The significance of GALE lies in its principled approach to self-supervised graph learning. By grounding representation learning in the intrinsic properties of graph equivalence, it moves beyond heuristic augmentation strategies often seen in GCL, providing a more theoretically sound and empirically effective method. The framework's ability to reduce oversmoothing in MPNNs, diagnose limitations in transformer positional encodings, and reveal the true drivers of GCL success underscores its analytical power and potential to reshape the landscape of graph representation learning.

Background

▶ Watch: Node equivalence: fundamental property and examples (0:30)

The problem of learning effective representations for nodes and graphs is central to many machine learning tasks, from drug discovery to social network analysis. Graph Neural Networks (GNNs) have emerged as powerful tools for this, but their performance often hinges on the quality of node embeddings, especially in self-supervised settings where labeled data is scarce. A foundational, yet often overlooked, property in many real-world networks is node equivalence. This concept formalizes the idea that certain nodes in a graph play identical or highly similar roles, either structurally or functionally.

Two primary forms of equivalence are highlighted:

1. Automorphic Equivalence: This is a structural concept where two nodes are considered automorphically equivalent if the graph's adjacency structure remains unchanged after permuting their labels. In essence, these nodes are indistinguishable purely based on their connectivity patterns. Examples include the six carbon atoms in a benzene ring or nodes with identical interaction patterns in a protein-protein interaction network. Identifying exact automorphic equivalence is computationally challenging, belonging to the class of NP-hard problems, making it impractical for large-scale graphs. Established tools like Bliss or Nauty exist for this but are not scalable to real-world graphs.
2. Attribute Equivalence: This refers to nodes sharing identical or very similar feature vectors. For instance, atoms of the same type in a molecule, components with the same role in a power grid, or papers belonging to the same field in a citation network. While conceptually simpler, strict attribute equality can be too rigid in noisy real-world data, where minor variations might incorrectly differentiate truly equivalent nodes.

Traditional graph learning models often struggle to explicitly capture and leverage these equivalences. Message Passing Neural Networks (MPNNs), while inherently prone to making equivalent nodes similar due to their neighborhood aggregation mechanism, suffer from oversmoothing. As layers deepen, node representations converge, making it difficult to distinguish even non-equivalent nodes, leading to performance degradation. Graph Transformers rely on positional encodings (PEs) to inject structural information, but the effectiveness of these PEs in capturing structural equivalence has been a subject of scrutiny. If PEs themselves do not respect automorphic equivalence, the transformer's ability to learn such symmetries is fundamentally limited.

Graph Contrastive Learning (GCL), a popular self-supervised paradigm, operates by pulling representations of augmented views of the same node closer while pushing representations of different nodes apart. While successful, the underlying mechanism driving GCL's performance has been debated, particularly the relative importance of graph augmentations versus the implicit equivalence constraint (where each node is essentially considered equivalent to itself across views). This talk aims to provide a unified framework that directly addresses these limitations by making node equivalence a first-class citizen in the self-supervised learning process.

Key Findings

▶ Watch: GALE framework: dual-branch self-supervised learning (3:15)

The research presented in "Equivalence is All" introduces several key findings and contributions that collectively advance the field of self-supervised graph learning:

1. The Equivalence Principle as a Unified Foundation: The talk establishes node equivalence (both structural and attribute-based) as a fundamental principle for effective graph representation learning. It posits that an ideal graph model should learn embeddings where equivalent nodes are proximate and non-equivalent nodes are distant in the embedding space.
2. GALE: A Novel Self-Supervised Framework: The proposed GALE framework successfully operationalizes this principle through a dual-branch architecture. One branch explicitly computes node equivalence partitions, while the other is a standard GNN encoder. A novel equivalence loss then regularizes the encoder, guiding it to produce representations that adhere to the identified equivalence classes.
3. Practical Approximate Equivalence Detection: Recognizing the NP-hard nature of exact automorphic equivalence and the strictness of exact attribute matching, GALE introduces efficient approximate methods. PageRank scores are shown to be a highly effective and efficient proxy for structural similarity, while grouping nodes by the proximity of their attribute vectors (instead of exact equality) addresses noise in attribute data. This practical approximation, dubbed GALE-APR, achieves performance comparable to the exact method while being significantly more scalable.
4. Insights into Existing Models:

• MPNNs: GALE's equivalence loss directly addresses the oversmoothing problem in MPNNs by explicitly enforcing dissimilarity between nodes from different equivalence classes, thus maintaining distinct representations.
• Graph Transformers: Analysis reveals that most common positional encodings (PEs) used in graph transformers are poorly aligned with true automorphic equivalence (indicated by high Red values), highlighting a fundamental limitation in their ability to capture structural symmetries.
• Graph Contrastive Learning (GCL): GALE reframes GCL as a "degenerate" form of equivalence learning, where each node is its own class. An ablation study conclusively demonstrates that the "positive pairing" (the equivalence constraint) in GCL is far more critical for performance than the data augmentations themselves, suggesting that the equivalence principle is the true engine behind GCL's success.

1. State-of-the-Art Performance: GALE consistently achieves new state-of-the-art results on both graph and node classification tasks across a wide range of popular benchmark datasets. Notably, GALE-APR, the efficient approximate version, also delivers top-tier performance, confirming the effectiveness and scalability of the proposed approximations. For node classification, GALE even surpasses the performance of fully supervised GCNs on most datasets, demonstrating the power of its self-supervised approach.

Technical Deep Dive

▶ Watch: Practical challenges and approximate equivalence solutions (5:00)

At its core, GALE is built upon the equivalence principle, which states that an ideal graph representation model should map nodes belonging to the same equivalence class to similar points in the embedding space, while mapping nodes from different classes to dissimilar points. This principle guides the design of GALE's dual-branch architecture and its specialized loss function.

GALE Architecture

The GALE framework comprises two main components operating in parallel: an Equivalence Partition Module (EPM) and a standard GNN Encoder.

1. Equivalence Partition Module (EPM):

• Goal: To explicitly identify sets of equivalent nodes within the input graph.
• Automorphic Equivalence: For exact structural equivalence, GALE leverages established graph isomorphism solvers such as Bliss or Nauty. These algorithms identify permutations of node labels that preserve the graph's adjacency structure, thereby partitioning nodes into automorphic equivalence classes. The talk highlights that even standard benchmarks exhibit a surprisingly high degree of non-trivial symmetries.
• Attribute Equivalence: This is initially defined by grouping nodes that possess identical feature vectors. This creates partitions based purely on node attributes.
• Fused Partition: To capture a more refined and comprehensive notion of equivalence, GALE takes the intersection of the automorphic and attribute equivalence partitions. This means nodes in a fused class are equivalent in both their structural role and their intrinsic attributes. This fused partition P_fused serves as the ground truth for the self-supervised learning task.

1. GNN Encoder:

• Goal: To learn effective node representations h_i for each node i in the graph.
• Mechanism: This can be any standard GNN architecture (e.g., GCN, GAT, GraphSAGE). It takes the graph structure and node features as input and outputs node embeddings.

Equivalence Loss

The crucial link between the EPM and the GNN Encoder is the novel equivalence loss. This loss function regularizes the GNN encoder, guiding it to produce embeddings that respect the P_fused partitions identified by the EPM. The loss comprises two simple yet effective components:

1. Intraclass Term: This term aims to maximize the similarity between the representations of nodes that belong to the same equivalence class within P_fused. For any two nodes i and j in the same class C_k, their embeddings h_i and h_j should be pulled closer. This can be formulated using a similarity function (e.g., cosine similarity) and a positive pairing objective.
2. Interclass Term: This term aims to minimize the similarity between the representations of nodes that belong to different equivalence classes. For any two nodes i from class C_k and j from class C_l (where k != l), their embeddings h_i and h_j should be pushed apart. This can be achieved through techniques like negative sampling or margin-based losses.

The combined equivalence loss ensures that the learned embeddings are both discriminative (distinguishing between different classes) and coherent (grouping similar nodes within the same class).

Approximate Equivalence (GALE-APR)

Recognizing the computational intractability of exact automorphic equivalence for large, real-world graphs and the fragility of strict attribute equality in noisy data, GALE introduces efficient approximations: GALE-APR.

1. Approximate Structural Equivalence:

• Challenge: Finding exact automorphisms is NP-hard.
• Solution: GALE leverages the property that equivalent nodes must have the same PageRank score. While the reverse is not always true (nodes with the same PageRank are not necessarily equivalent), grouping nodes by their PageRank scores serves as a highly effective and efficient proxy for structural similarity. The talk presents empirical evidence showing that partitions generated this way are "very closely aligned with the true one," indicated by "near-zero variation of information" scores. This method significantly reduces computational overhead.

1. Approximate Attribute Equivalence:

• Challenge: Exact attribute equality is too strict for noisy real-world data; even minor noise can separate truly similar nodes.
• Solution: Instead of strict equality, nodes are grouped if their attribute vectors are "close" in the embedding space. This can be implemented using clustering algorithms (e.g., K-means, DBSCAN) or by defining a similarity threshold. This allows for capturing attribute similarity in a more robust and practical manner.

Relationship to Existing Models: A New Lens

GALE provides a unified lens through which to analyze and understand existing graph learning models:

• MPNNs and Oversmoothing: MPNNs inherently make equivalent nodes similar due to neighborhood aggregation. However, this leads to oversmoothing where all node representations become indistinguishable after many layers. GALE's equivalence loss directly addresses this by explicitly enforcing dissimilarity between nodes across different equivalence classes, thus preventing all representations from collapsing into a single point. The talk visually demonstrates how GCN performance drops with more layers, and GALE's approach effectively mitigates this.
• Graph Transformers and Positional Encodings (PEs): Graph transformers rely heavily on PEs to inject structural information. For a transformer to understand structural equivalence, its PE must also respect this property. GALE rigorously tests this, finding that "most common PEs are poorly aligned with the true automorphic equivalence," evidenced by "high Red values." This reveals a key limitation in current graph transformer designs, suggesting that PEs need to be designed with equivalence in mind.
• Graph Contrastive Learning (GCL): GALE reinterprets GCL as a "degenerate" form of equivalence learning, where each node is treated as its own equivalence class (positive pairs are just augmentations of the same node). An ablation study definitively shows that removing augmentations has only a minor impact on GCL performance, whereas removing the "positive pairing" (the core equivalence constraint) causes performance to "drop sharply." This compellingly argues that the equivalence principle, not merely augmentation, is the "true engine behind GCL success."

Experimental Setup & Results

▶ Watch: Experimental results: GALE's superior performance (8:50)

To validate the effectiveness of the GALE framework, extensive experiments were conducted on a wide range of popular benchmark datasets for both graph-level and node-level classification tasks. The evaluation aimed to demonstrate GALE's superior performance against strong baselines and to confirm the efficacy of its approximate equivalence detection methods.

Tasks Evaluated:

• Graph Classification: Classifying entire graphs based on their structure and node attributes.
• Node Classification: Classifying individual nodes within a graph.

Datasets: The talk mentions the use of "a wide range of popular benchmark datasets" without enumerating specific names. This implies standard datasets commonly used in graph learning research (e.g., MUTAG, PROTEINS, Cora, Citeseer, PubMed, etc.).

Baselines: GALE was benchmarked against:

• Strong Graph Contrastive Learning (GCL) baselines: These include prominent self-supervised graph learning methods.
• Full supervised GCN: For node classification, GALE's self-supervised performance was even compared against a GCN trained with full access to labels, providing a very high bar for comparison.

Metrics: While not explicitly stated, the context of "state-of-the-art results" and "outperforming baselines" implies standard classification metrics such as accuracy, F1-score, or AUC, depending on the specific task and dataset characteristics.

Headline Results:

1. Graph Classification:

• GALE achieved new state-of-the-art results, consistently outperforming strong GCL baselines across most datasets.
• Crucially, GALE-APR, the efficient approximate version, also achieved "top-tier performance," confirming its effectiveness and scalability for practical applications. This demonstrates that the approximations do not significantly compromise performance.

1. Node Classification:

• GALE again set a new state-of-the-art among all unsupervised baselines.
• More impressively, GALE even surpassed the performance of the full supervised GCN on most datasets. This is a significant finding, showcasing the power of self-supervised learning guided by the equivalence principle to extract highly discriminative features, potentially even outperforming models with full label supervision.

Ablation Studies:

A key ablation study was performed to dissect the mechanisms of Graph Contrastive Learning (GCL) through the lens of equivalence.

• Experiment: The study investigated the impact of removing augmentations versus removing the "positive pairing" (i.e., the equivalence constraint where views of the same node are pulled together) in GCL.
• Finding: Removing augmentations had only a "minor impact" on performance. However, removing the positive pairing caused performance to "drop sharply." This provides strong evidence that the underlying equivalence constraint, rather than the specific augmentation strategies, is the primary driver of GCL's success.

The experimental results robustly support the central hypothesis that explicitly leveraging node equivalence, even through efficient approximations, leads to superior graph representations and significant performance gains across diverse graph learning tasks.

Practical Implications

▶ Watch: Conclusion and key contributions of GALE (10:00)

The GALE framework and its underlying equivalence principle offer several significant practical implications for practitioners, infrastructure teams, and model builders in the AI/ML community working with graph-structured data.

1. Improved Model Performance and Robustness: For practitioners deploying graph learning models, GALE provides a principled method to achieve state-of-the-art performance in self-supervised settings, often outperforming existing GCL methods and even rivaling fully supervised approaches. By learning embeddings that inherently respect graph symmetries, GALE can lead to more robust and generalizable models, especially in scenarios with limited labeled data.

1. Scalability for Large Graphs: The introduction of GALE-APR (Approximate Equivalence) is a game-changer for infrastructure teams and model builders dealing with large-scale real-world graphs. Exact automorphic equivalence detection is computationally prohibitive (NP-hard). GALE-APR's use of PageRank scores for structural similarity and proximity-based grouping for attributes provides an efficient and effective proxy, making the benefits of equivalence-aware learning accessible even for graphs with millions or billions of nodes. This mitigates the computational bottleneck, allowing for deployment in production environments.

1. Deeper Understanding of Existing Models: GALE offers a powerful analytical lens:

• MPNN Users: The framework provides a direct solution to the notorious oversmoothing problem in MPNNs by enforcing inter-class dissimilarity. Practitioners can potentially integrate GALE's loss into their MPNN training pipelines to maintain discriminative power even with deeper architectures.
• Graph Transformer Developers: The finding that many common positional encodings (PEs) are poorly aligned with true structural equivalence highlights a critical area for improvement in transformer design. Future PE development should explicitly consider how to encode and respect automorphic equivalence for better performance.
• GCL Researchers/Implementers: The ablation study's revelation that the "equivalence constraint" is more vital than augmentations in GCL redirects research focus. Instead of solely seeking novel augmentation strategies, efforts could be concentrated on designing more sophisticated and explicit equivalence constraints or positive pairing mechanisms.

1. Principled Self-Supervised Learning: GALE moves beyond heuristic augmentation strategies, offering a more theoretically grounded approach to self-supervised graph learning. By identifying intrinsic properties of the graph (equivalences) and using them to guide representation learning, it provides a powerful alternative to traditional pre-training methods.

Tradeoffs and Limitations:

• Computational Cost of Exact Equivalence: While GALE-APR addresses scalability, relying on exact automorphic equivalence (e.g., using Bliss or Nauty) for highly precise partitions remains computationally intensive and impractical for very large graphs. This necessitates the use of approximations, which, while effective, are still heuristics and might not capture every subtle nuance of equivalence.
• Sensitivity of Approximations: The effectiveness of approximate equivalence methods (e.g., PageRank, attribute proximity thresholds) might depend on the specific graph properties and attribute distributions. Careful tuning or adaptive strategies might be required for optimal performance across diverse datasets.
• Definition of "Closeness" for Attributes: For approximate attribute equivalence, defining what constitutes "close" attribute vectors (e.g., choice of distance metric, threshold, or clustering algorithm) can introduce hyperparameter sensitivity.

Despite these considerations, GALE represents a significant step forward, providing a unified, principled, and practically scalable framework for self-supervised graph representation learning that leverages the fundamental concept of node equivalence.

Key Takeaways

• Node equivalence is a fundamental property in real-world networks (structural and attribute-based) that should be explicitly leveraged for effective graph representation learning.
• GALE is a novel self-supervised framework that unifies and operationalizes the equivalence principle through a dual-branch architecture and a specialized equivalence loss.
• Efficient approximate methods (GALE-APR), using PageRank for structural similarity and attribute proximity, make the framework scalable and practical for large, noisy graphs without sacrificing significant performance.
• GALE offers critical insights into existing models: it alleviates oversmoothing in MPNNs, exposes limitations in positional encodings for graph transformers, and reveals that the equivalence constraint is the true driver of success in Graph Contrastive Learning.
• GALE achieves state-of-the-art performance in both graph and node classification tasks, often surpassing strong self-supervised baselines and even outperforming fully supervised GCNs in node classification.
• The work suggests a shift in focus for GCL research, emphasizing the design of more effective equivalence constraints rather than solely on novel augmentation strategies.

About the Speaker(s)

The talk "Equivalence is All: A Unified View for Self-supervised Graph Learning" was a collaborative effort by a team of researchers including Yejiang Wang, Yuhai Zhao, Zhengkui Wang, Ling Li, Jiapu Wang, Fangting Li, Miaomiao Huang, Shirui Pan, and Xingwei Wang. The presentation at ICML 2025 was delivered by one of the co-authors on behalf of the first author, Yejiang Wang, who was unfortunately unable to attend due to visa issues. The research reflects a deep understanding of graph theory, machine learning, and self-supervised learning paradigms, contributing a principled and effective new framework to the field.