Research map / Graph learning / Graph self-supervised learning

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

ICML 2025 · Graph learning › Graph self-supervised learning · approach: Augmentation-free graph learning

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes GALE, a self-supervised graph learning framework that unifies automorphic and attribute equivalence into fused equivalence classes and uses an intra/inter-class loss, with linear-time PageRank-based approximations.

Problem

Existing graph self-supervised models, especially graph contrastive learning, ignore node equivalences (automorphic and attribute-based), treating each node as its own class; exact automorphism detection is NP-hard.

Approach

Fuse structural automorphic equivalence classes with attribute-equality classes into a unified equivalence partition and add an equivalence loss that pulls same-class node embeddings together and pushes different-class embeddings apart; approximate automorphic classes via PageRank scores and attribute classes via a Euclidean threshold.

Key results

• GALE reaches 85.06% on PubMed node classification, over 3.1% above the best unsupervised method SUGRL and 5.9% above supervised GCN.
• On PROTEINS graph classification GALE outperforms the best self-supervised baseline SEGA by 5.15%, and on IMDB-B it surpasses GIN by 3.96%.
• PageRank-based approximate automorphic partitions align closely with exact ones (VI 0 to 0.047 across eight datasets).

Measured effects reported in the paper

Surprising findings

• Removing graph augmentations has only a minor effect on GCL performance, while removing positive pairs substantially hurts accuracy.
• Most common positional encodings in graph transformers do not respect automorphic equivalence (large VI for LapPE and SignNet on several datasets).

Limitations

• Attribute-based equivalence uses an O(n^2) pairwise grouping and an intra-class loss that becomes imbalanced over iterations, requiring a Softplus fix.
• Approximate PageRank equivalence is not exact; VI for Cora and CiteSeer is nonzero (0.021, 0.047).

Experimental setup

Datasets: Cora CiteSeer PubMed Wiki-CS Amazon-Computers Amazon-Photo Coauthor-CS Coauthor-Physics NCI1 PROTEINS DD MUTAG

Benchmarks: Cora CiteSeer PubMed Wiki-CS Amazon-Computers Amazon-Photo Coauthor-CS Coauthor-Physics NCI1 PROTEINS DD MUTAG

Metrics: accuracy variation of information

Baselines: GCN GIN GraphCL AD-GCL JOAOv2 RGCL SimGRACE SEGA AutoGCL DGI GRACE BGRL

Builds on: graph contrastive learning PageRank nauty bliss

Closest papers by meaning

• Decoupled Self-supervised Learning for Graphs (NeurIPS 2022 · similarity 0.90)
• Automorphic Equivalence-aware Graph Neural Network (NeurIPS 2021 · similarity 0.89)
• Adaptive and Context-rich Generative Self-supervised Learning on Graphs (AAAI 2026 · similarity 0.88)
• Equivariance Everywhere All At Once: A Recipe for Graph Foundation Models (NeurIPS 2025 · similarity 0.87)
• Beyond Homophily: Graph Contrastive Learning with Macro-Micro Message Passing (AAAI 2025 · similarity 0.87)
• Self-Interpretable Graph Learning with Sufficient and Necessary Explanations (AAAI 2024 · similarity 0.87)