Equivalence is All: A Unified View for Self-supervised Graph Learning
Authors: Yejiang Wang
Yuhai Zhao
Zhengkui Wang
Ling Li
Jiapu Wang
Fangting Li
Miaomiao Huang
Shirui Pan
Xingwei Wang
Venue: ICML 2025 oral (2025)
Keywords: Graph Self-Supervised Learning
Graph Neural Networks
Primary area: deep_learning->graph_neural_networks
TL;DR: we introduce a self-supervised graph learning framework from an equivalence perspective, unifying and enforcing node equivalence principles to representation learning.

Abstract: 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.

Equivalence is All: A Unified View for Self-supervised Graph Learning
Yejiang Wang" 12
Yuhai Zhao
Zhengkui Wang Ling Li Jiapu Wang* Fangting ! Shirui Pan Xingwei Wang'
Miaomiao Huang 1.
Abstract
2
Node equivalence is common in graphs, such as computing networks, encompassing automorphic equivalence (preserving adjacency under node per- mutations) and attribute equivalence (nodes with identical attributes). Despite their importance for learning node representations, these equiva- lences are largely ignored by existing graph mod- cls. 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 automor- phic and attribute equivalence into single equiva- Ience 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- harddnessss of exact automorphism detection and handle node- feature variation; 4) analyze existing graph en- coders, noting limitations in message passing neu- ral networks and graph transformers regarding equivalence constraints; 5) show that graph con- trastive learning are a degenerate form of equiva- lence constraint; and 6) demonstrate that GALE achieves superior performance over baselines.
6
G 2.30
6
5
Figure 1. An example of automorphic equivalence. Hollow double arrows indicate node permutations in graph G, shown in cycle notation (c.g., (1, 2, 3) means 2-+1 3-+, 1-+3).
edges. In terms of graph structure, automorphic equivalence represents strict form of equivalence: there exists a global permutation that maps nodes within the same equivalence class to each other (Cameron & Mary, 2004). As shown in Figure I, we perform permutations on the nodes of the original graph G. Here, ((.......)) represents a permuted graph under the cycle notation of permutation, For instance, ((12233) means nodes 1, 2, and 3 are eyclically permuted (node 2 is mapped to node 1, node 3 to node 2, and node to node 3). We can observe that G = G = ((122,3) indicating that these nodes are structurally equivalent with respect to the graph topology. In contrast, nodes 4 and 5 are not equivalent, as swapping them would not preserve their adjacency relations.
1. Introduction
Node equivalence (Lorrain & White, 1971; Bafai, 1977) is common in real-world graphs such as computing networks, where resources form nodes, and their dependencies form
Automorphic equivalence (AE) is fundamental concept in various scientific domains such as chemistry and network analysis (Faulon, 1998; Friedkin & Johnsen, 1997). For in- stance, AE is key indicator of similarity in social status and behavior in social networks (Everett, 1985). Furthermore, for graphs with node attributes, another type equivalence can be defined based on attribute similarity. Specifically, new equivalence class be constructed by measuring the distance between attribute vectors: nodes with a close distance are grouped into the same equivalence class.
SScoool of Computer Seience and Engincering, Northeast- em University, China "Key Laboratory of Intelligent Comput- ing Medical Image Ministry Education, Northeastern University, China "InfoComm Technology Cluster, Singapore Institute of Technology. SIT X NVIDIA AI Centre, Singapore "Shanxi University, China 'Hefei University of Technology, China 'Griffith University, Australia. Correspondence Yuhai Zhao <zhaoyuhai @
Naturally, we would expect graph representation models to preserve and reflect these node equivalences in their encoded node representations. However, we find that few studies ex-
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Equivalence is All: A Unified View for Self-supervised Graph Learning
plicitly consider these equivalences in graph representation learning, particularly in the widely studied paradigm of self-supervised graph learning, such as graph contrastive learning (Thakoor et al., 2022; Liu et al., 2024a; Wan et al., 2024). This method typically augments the original graph (e.g., by randomly removing edges) to generate two con- trasting views. Contrastive constraints are then applied to encourage the representations of the same node (positive views) in both augmented graphs to be as similar possi- ble, while ensuring that representations of different nodes (negative views) become dissimilar. However, this paradigm overlooks the equivalence relations in terms of graph struc- ture and node attributes. Existing methods focus solely on aligning the representations of the same node across aug- mented views, pushing apart those of different nodes, while often neglecting the fact that nodes similar given node not limited to that node alone. Consequently, certain similarities between different nodes are frequently ignored.
nodes sharing identical connectivity patterns occupy equiv- alent roles, forming the basis for role discovery in net- works. However, its strict definition limits its applicability in complex networks. A broader concept of equivalence, automorphic equivalence (AE) (Lauri & Scapellato, 2016), 6), emerged from graph automorphism theory, where two nodes are equivalent if there exists a permutation of the graph's 's vertices such that adjacency relations are preserved (Bafai, 1977). AE has proven fundamental across scientific do- mains, e.g., in social networks, AE identifies individuals with identical social statuses or influence patterns (Everett, 1985; Friedkin & Johnsen, 1997). In chemistry, symmetric atoms in molecules (e.g., carbon atoms in benzene rings) are automorphically equivalent, explaining their identical chemical properties (Faulon, 1998).
Self-supervised Graph Learning. Graph learning has at- tracted significant attention in recent years (Koh et al., 2024; Wang et al., 2024a;b; Liu et al., 2024b; Wang et al., 2024c.. Graph self-supervised learning has emerged as a dominant paradigm for learning representations from unlabeled graph data (Wang et al., 2023; Zhao et al., 2025). Early approaches focused on preserving structural proximities through matrix factorization (Belkin & Niyogi, 2001), random walk objec- tives (Grover & Leskovec, 2016), deep autoencoders (Cao et al., 2016). The recent surge in graph contrastive learning (GCL) methods (Cai et al., 2023; Li et al., 2022: Thakoor et al., 2022) has centered around maximizing agreement between positive views of the same node while repelling negative samples. Contrastive loss encourages similar rep- resentations for the same node across augmented views, while separating different nodes. However, it treats each node only equivalent to itself, overlooking structural or attribute-based equivalence.
To address these issues, we propose a novel equivalence- based self-supervised graph representation learning frame- work (GALE) grounded in the equivalence principle: node representations within the same equivalence class should be more similar, while those in different equivalence classes should be as dissimilar possible. Specifically, 1) we de- fine two equivalence relations automorphic equivalence based on graph structure and attribute equivalence based on node attributes -nd combine them into a unified equiva- Ience class; 2) Then we enforce the equivalence principle, ensuring the node representations within the same equiva- lence class are similar, while those in different classes are dissimilar; 3) We introduce approximate equivalence classes with linear time complexity to address the NP-hard nature of exact automorphism detection and handle practical chal- lenges such as attribute noise or slight variations that still indicate similarity, which make strict equivalence impracti- cal in world graphs; 4) We note that message passing neural networks (MPNNs) make equivalent nodes similar but risk over-similarity for non-equivalent nodes, while most position encoding methods in graph transformers fail to in- corporate the automorphic equivalence constraint: 5) From the equivalence perspective, we show that the current graph contrastive learning paradigm is a degenerate form of equiva- lence constraint, where each equivalence class is limited to a single node; 6) We demonstrate that GALE surpasses SOTA algorithms through experiments on benchmark datasets.
3. Background
Notations. Let G - -V, E) be graph with nodes and m edges, where V denotes the set of nodes and E' represents the set of edges. If node attributes are available, we denote the node feature matrix as X E Raxd where represents the dimension of the node attributes.
Problem Formulation. In this work, we focus on learning the representation zu E R for each node in an unsuper- vised manner, where g denotes the output dimension.
Equivalence Relation and Equivalence Class. Let S be non-empty set (in this paper, the set of interest is the node set V), and let R be relation on S. We say that Rt is an equivalence relation on S if and only if R satisfies the following properties: 1) Reflexivity: Every element is related to itself under R (i.e., x = x for all x E S). 2) Symmetry: x E S is related to y E under R, then y is related to under R (i.e., R y + y RR x). 3)
2. Related Work
Equivalence in Graphs. The concept of node equivalence traces its roots to structural sociology and algebraic graph theory (Wasserman & Faust, 1994). In social network anal- ysis. Lorrain and White's s structural equivalence (Lorrain & White, 1971; Fortunato, 2010) formalized the idea that
2

---

Equivalence is All: A Unified View for Seff-supervised Graph Learning
branch involves graph encoder, which encodes the graph to obtain node representations; we a graph neural net- work (GNN) for this purpose. The other branch focuses on inducing sedivalence-class partitions of the node set. Based on the equivalence principle-nodes within the same equiv- alence class are considered similar, while nodes in different classes are considered dissimilar-we impose regularization constraints on the node representations and optimize the en- coder with an equivalence loss. In our work, we construct two types of equivalence-class partitions: 1) Group I: Calcu- lated based on the graph is adjacency information, capturing the graph's 's structural automorphism. 2) Group II: Calcu- lated based on the attribute information of nodes, capturing feature equality. We fuse these partitions into unified node constraint network, ensuring the learned representations capture both structural and attribute-based equivalences.
Regularizo
Group
Encerd
Group
Representation
Graph
Portitions
Finel Portition
Figure 2. Overview of GALE, combining an encoder and equiv- alence constraints from structural and attribute- based partitions. The constraints regularize the encoder's 's node representations.
Transitivity: x E S is related to y E S and y is related to = E S under R. then x is related to 2 under R (i.e., =R y Ay =R= + x RR 2). For example, the identity relation (=) on set S is an equivalence relation. For each E S, the equivalence class of determined by R. denoted as [z:], is defined as [x]] {y E S x =R y).
4.1. Automorphic Equivalence from Structure
A graph typically encompasses two components: the rela- tionships between nodes (edges) and the properties asso- ciated with each node. We establish equivalence relations and their corresponding partitions on both of these aspects. First, we focus on adjacency. As discussed earlier, auto- morphic equivalence represents a strict node equivalence relation based on the graph's structure. Indeed, real-world graph data often exhibits substantial number of nodes with automorphic equivalence.
Partition and Induced Partition. Let P be a family of subsets of S. We say that P is a partition of S if and only the following conditions are satisfied: 1) If X P. then X A Ø (i.e., no subset in the partition is empty); 2) If X E P and Y P, then either X Y or X n Y Ø (i.e., subsets in the partition are pairwise disjoint); 3) UXEPX x= S (i.e., the union of all subsets in the partition covers the entire set 9). It can be proven that the equivalence classes determined by any equivalence relation on a set form a partition of that set. This partition is referred to as the induced partition from the equivalence relation.
To verify this, we present statistics on the proportion of nodes/graphs with automorphic equivalence in 3 bench- mark network datasets (Kipf & Welling, 2017) and 3 graph datasets (Morris et al., 2020). For network data (single graph), we calculate the ratio of nodes in non non-singleton orbits (the number of nodes is greater than one) to the to- tal number of nodes. For graph datasets (multiple graphs), we compute the ratio of graphs with non-trivial automor- phisms. The results, shown in Table 1, demonstrate that a significant proportion of nodes/graphs exhibit non-trivial automorphic equivalence, highlighting its prevalence in real- world datasets.
Automorphism and Orbit. A permutation π set V rearranges its elements as V= = {v*)) We use cycle no- tation to represent permutations. All permutations of V form a symmetric group S.. A graph automorphism of a graph G a permutation π E Sn that preserves the edge relations of G, i.e., F = F,, - [[u7, Uz) (u,v) E F.). Every graph has a trivial automorphism, the so-called iden- rity automorphism,, which maps each vertex to itself. The set of all automorphisms of a graph forms group, called the automorphism group of the graph, denoted as Aut(G). The elements (permutations) in the automorphism group of a graph define an equivalence relation on the node set V:
Table I. Proportions of automorphically equivalent nodes (left three) and graphs (right four) in network and graph-level datasets.
Catto U 3m E AG), Ur =
(1)
Data
Cora
Citesoor
PubMed
MUTAG
DD
IMDB-B
COLLAB
Ratio
18.4%
46.2%
45.7%
100%
96.3%
100%
99.9%
This equivalence relation, also known as a symmetry rela- tion, partitions the node set V into non-overlgpping equiva- lence classes called orbits.
To compute the exact automorphisms of a graph, we adopt classical algorithms such as bliss or nauty (Junttila & Kaski, 2011; McKay & Piperno, 2014). For example, bliss is an efficient method for computing the automorphism group of real-world graphs by leveraging symmetry- brreakig and backtracking search. Once the automorphism orbits are ob- tained, we construct the automorphic equivalence partition Pauto (Ci), where C represents an orbit.
4. Learning with Equivalence Classes
In this Section, we introduce a novel equivalence-basee self- supervised graph learning framework (GALE), as shown in Figure 2. GALE consists of dual-branch structure. One
3

---

Equivalence is All: A Unified View for Self-supervised Graph Learning
4.2. Attribute Equivalence from Nodes
equivalence classes have dissimilar representations, we define loss function based the similarity between node embeddings.
To construct a partition of the graph based on node attributes, define equivalence relation among nodes such that nodes with identical attributes are grouped into the same
Intra-class Loss. Let Pruse {Fi} represent the fused equivalence partition, and let zu denote the embedding of node u. The intra-class loss is defined to encourage the embeddings of nodes within the same equivalence class F, to be similar:
equivalence class:
Cattr - x,= X Vu,u E V
(2)
which ensures that the partition reflects the inherent equation of nodes in terms of their attributes. This equivalence rela- tion induces a partition Pater = { where each subset Dj C V contains all nodes with the same attribute values.
Cintr Σ EER -D(zu: Zu)
(4)
M,DEF,
where D
R. x R + R is a discriminator that maps two views to agreement score. In this work, standard inner product D (2,, 2g) 2 n.j
4.3. Fusion of Equivalences
the
With the two partitions established, we aim to create a re- fined node partition by fusion. Generally, both the structural role and the attributes of node are equally important for its characterization. For example, consider citation network (where nodes represent papers and edges represent cita- tions): two papers might be cited by similar papers (graph structure), yet their topics (attributes) could be different. Therefore, we seek a refined partition that preserves the equivalence relationships from both perspectives. To accom- plish this, we construct the fused partition by intersecting the structure-based and attribute-based partition:
Inter-class Loss. The inter-class loss is designed to ensure that embeddings of nodes from different equivalence classes are dissimilar. For nodes 8 E F; and f E F3 with i * j. we penalize high similarity between their embeddings. The inter-class loss is defined as:
Linter Σ Σ
D(zs, 2:) $$ SEF.NEF,
(5)
Finally, the equivalence loss is defined as:
Lequiv Lintra Cimer
(6)
Prose {C n Dy C, E Pamoo Dj E Patt: C. CDD
(3) inherits characteristics from both partitions, ensuring con- sistency with both graph structure and node attributes. Each fused equivalence class F C2 O Dj contains nodes that equivalent under both graph automorphisms and node attribute equivalence. The resulting partition satisfies: 1) UFEP F V; Fs Fi = @ for k + I. We now prove that the relation Luse, which induces the fused partition Prusion. satisfies the properties of an equivalence relation. Theorem 4.1. The fusion relation defined Juse is an equivalence relation.
5. Approximate Equivalence Classes
In real-world graphs, strict equivalence relationships, such as automorphic or exact attribute- -bsed equivalence, are of- ten impractical due to the computational cost of determining exact automorphisms and the rarity of complete attribute cquality caused by noise or data variations. To overcome the challenges, we introduce approximate equivalence classes, which relax the strict requirements of exact equivalence.
5.1. Approximate Automorphie Equivalence
Determining the exact automorphism group of a graph is computationally intractable, as it the NP-hard problem. To overcome this, we propose an efficient approximation using PageRank vectors, which leverage their inherent relationship to approximate automorphic equivalence effectively.
Proof. To show that "fuse is an equivalence relation, we verify the three properties: 1) Reflexivity: For any node E V. we have u Sauto u (since automorphic equivalence reflexive) and u ~arr (since attribute equivalence is reflexive), Therefore, u fuse u, satisfying reflexivity. 2) Symmetry: If u ruuee U, then aatoo and u aat By the symmetry of Sauto and Satrr we have Eauio and v Sair u. proving symmetry. 3) Transitivity: If u fuse V and V ruse w, then u antto U. V aauto w. and u Zaur v, U aatr w. By the transitivity of auto and aater we have u aanto w and u Satr w. Hence, transitivity is established.
The PageRank algorithm (Langville & Meyer, 2004) as- signs a score to each node in a graph, measuring its relative importance based on the graph structure. Let P x= denote the Markov transition matrix of the graph, where P. 1/deg(i) if (i,j) E, and P.j 0 otherwise, with deg(i) representing the degree of node i. The PageRank vector r E 1 is the stationary distribution of random walk with teleportation, based on the transition probabilities P. computed as:
4.4. Equivalence Loss
To encourage nodes within the same fused equivalence class to have similar representations and nodes from different
r= oP r
TT (1 o)v

---

Equivalence is All: A Unified View for Self-supervised Graph Learning
where a E (0, 1) is the teleportation probability, v E I is personalization vector (typically uniform). The PageRank vector assigns score Tú to each node i E V, reflecting its importance based on local connectivity and global graph structure. The following lemma establishes the relationship between automorphisms and PageRank.
nodes with sufficiently similar attributes be grouped into the same equivalence class. For nodes u, v E V, we define the approximate attribute equivalence relation aut as:
U ~ attr U
X - xx <
(9)
where c 2 0 is a small positive threshold that controls the degree of similarity required for nodes to be considered equivalent. The relaxed partition allows nodes with similar attributes (within the threshold e) to be grouped together, even if their attributes are not exactly identical. Clearly, when = 0, it reduces to strict equivalence. When > O, it is not a strict equivalence, though the resulting node sets may be called similarity groups.
Lemma 5.1 (Ghorbani et al. (2021)). If two vertices U E V are automorphically equivalent in G, then u and v have the same PageRank score:
U - auto V
Fu-- To
(8)
We leverage this property to approximate automorphic equivalence by grouping nodes with similar PageRank scores. While nodes with equal PageRank scores are not nec- essarily automorphically equivalent, they often exhibit struc- tural similarity in terms of their importance within the graph, providing an efficient approximation. To verify this, we conduct experiments on 8 benchmark datasets: Cora, Cite- seer, Pubmed (Kipf& & Welling, 2017), Wiki-CS, Amazon- Computers, Amazon-Photc Coauthor-CS, and Coauthor- Physics (Shchur et al., 2018). Empirical results show the alignment between the true and approximate equivalence partitions, measured by the Variation of Information (Meilä, 2007) (with values closer to 0 indicating better alignment and 0 indicating perfect alignment). The detailed results are presented in Table 2, where we find that for all the data, the approximate partitions closely match the true ones, validat- ing the effectiveness of our approximation. Here, we use a = 0.85; for an analysis of different parameter settings, please refer to the Appendix.
5.3. Complexity Analysis
The time complexity of the GALE involves four compo- nents: 1) Automorphic equivalence can be approximated using PageRank, which runs in ((m); 2) Attribute- based equivalence requires grouping nodes by attributes, with a complexity of O(n²): 3) Fusion of equivalences involves intersecting equivalence classes, scaling as O(n) in practice due to the typically small number and size of partitions. 4) Equivalence loss computation with worst-case complexity of (n²). Overall, the dominant term is O(n² + m))
6. Equivalence and Graph Encoders
In this section, we discuss how mainstream graph encoders, message passing neural networks (MPNNs) and graph trans- formers, interact with the concept of equivalence.
6.1. MPNNs and Automorphic Equivalence
Table Variation of Information (VI) for alignment between equivalences aato and zPR on eight benchmark data, Lower VI
MPNNs (Wu et al., 2020) and their variants, such Graph Convolutional Networks (GCNs), rely on the principle of neighborhood aggregation to learn node representations.
values (0 indicating perfect alignment) are shaded in darker green.
Data
Cam
CheSeer PubMed WHtcs
Amr-Comp
Amr- Photo
Co-CS Co-Phy,
Vic.
0021
0,47
0.004
0,001
The neighborhood aggregation mechanism of MPNNs in- herently aligns with the goal of making automorphically equivalent nodes have similar representations. For example, consider two automorphically equivalent nodes and and their adjacency structures are identical. During the message- passing process, and will aggregate similar information from their neighbors. This property ensures that MPNNs can naturally preserve the similarity of node representations within the same equivalence class.
Computing PageRank has a time complexity of ((m) for graphs, where m denotes the number of edges, which is significantly more efficient than exact automorphism com- putation (Kondaveeti al., 2024).
5.2. Approximate Attribute Equivalence
In real-world networks, nodes often exhibit attributes that are not perfectly identical but are instead only slightly differ- ent. Strictly enforcing exact equality of node attributes when defining equivalence classes can lead to overly fragmented partitions, as even minor differences in attributes result in nodes being classified into different equivalence classes. To address this issue, we propose relaxing the equivalence constraint by using a similarity threshold based on the Eu- clidean distance between node attribute vectors. This allows
However, MPNNs cannot guarantee that dissimilarity be- tween different equivalence classes remains valid. As the number of layers increases, the representations of all nodes in the graph tend to converge, leading to the over-smoothing problem. This phenomenon reduces the discriminative power of the learned node embeddings. Common over- smoothing mitigations, like residual connections or dynamic neighborhoods, typically overlook node equivalence.
5

---

Equivalence is All: A Unified View for Self-supervised Graph Learning
To address this, explicit constraints based on equivalence classes can be incorporated into MPNN models. These con- straints enforce inter-class dissimilarity while preserving intra-class similarity, helping to alleviate the over-smoothing problem. To demonstrate this, Figure 3 shows the classi- fication results of GCN and GALE with increasing depth on the Cora and CiteSeer dataset. GCN's performance de- clines sharply with more layers, but GALE with equivalence constraints significantly mitigates the over-smoothing issue.
we conduct experiments on 8 benchmark graph datasets using PE methods: Laplace positional encoding (LapPE) (Kreuzer et al., 2021), Random walk positional encoding (RWSE) (Dwivedi et al.. 2022), SignNet (Lim et al., 2023), ElstatieSE, and SK (Rampášek et al., 2022). We compute the Variation of Information (VI) (Meilä, 2007), and the results are shown in Table 3. Our findings indi- cate that most existing PE methods do not truly adhere to automorphic equivalence, and in some cases, deviate signif- icantly. This may be because these methods focus primarily on ensuring that neighboring nodes are assigned similar po- sitions (locally), while neglecting the global equivalences within the graph.
GALE
IN GALE GCN
20
BGNN
ADCURMCY
ACCURACC
60
Table 3. Variation of Information between automorphic and posi- ancoding-based based equivalence (lower is better, 0 is perfect).
tional encoding-
7
5P
Methods
Cora
CleeSeer
PobMed
WBICS
Ams-Comp.
Amz Phodo
Co:CS
Co-Ply
(a) Cora
(b)
Citesoer
Tapit:
01147
0.035
Figure 3. Accuracy of GCN and GALE with increasing depth.
Sinneee
3.547
5:06
3,500
01H8
BlaaKSE
0.096
0.764
0.483
0.882
0.044
6.2. Graph Transformers and Equivalence
7. Equivalence in Graph Contrastive
Graph transformers (Min et al., 2022) take a fundamentally different approach to learning node representations com- pared to MPNNs. Instead of relying on neighborhood ag- gregation based on adjacency structure, graph transformers use node positional embeddings to inject structural infor- mation and infer relationships between nodes through their positions and attributes. The node representations are then updated using a fully-connected self-attention mechanism.
In this section, we analyze how equivalence classes play a role in graph contrastive learning (GCL).
7.1. Analysis of Graph Contrastive Learning
GCL starts by creating two views of the original graph G through small perturbations, such as edge deletion, resulting in an augmented graph G2- These two views, G1 and G2, are assumed to have minimal differences and preserve label invariance. For each node i, the goal of the contrastive loss is to make the node's representations across the two views z! (from G1) ) and z? (from G2)) more similar (positive pairs), while ensuring that the representations of different nodes z} (from G1, j * i) and z² (from G2) are as dissimilar as possible (negative pairs). The contrastive loss can be formulated as follows:
While graph transformers can capture global relationships, they do not inherently ensure that automorphically equiva- lent nodes are represented similarly. The effectiveness of capturing automorphic equivalence depends on the qual- ity of the positional embeddings, which may not always align with the graph's 's symmetries. Moreover, the global nature of the attention mechanism, which lacks local con- straints, means that nodes within the same equivalence class might not remain sufficiently similar, and there's no in- herent mechanism to ensure dissimilarity between nodes in different equivalence classes. As result, while graph transformers excel at encoding global structures, they may struggle to consistently respect automorphic equivalence without additional constraints or interventions.
n Coon = log exp(sim(z). ,22)/)
(10)
ΣJ= exp(sim (z), 23)/T)
where sim(-.) ) is similarity function, 7 is temperature.
From the perspective of equivalence classes, current GCL methods implicitly assume a trivial equivalence class struc- ture, where each node is treated as its own equivalence class. Specifically, the contrastive loss enforces that each node's 's representation remains consistent across views (within the same trivial equivalence class) while being distinct from the representations of all other nodes (across different classes).
Positional Encoding and AE. Therefore, node positional embeddings, which are solely based on the graph's 's struc- ture, are essential for reflecting the equivalence relationships within that structure. To evaluate whether common posi- tional encoding (PE) methods align with automorphic equiv- alence, we propose a validation procedure that compares the ground truth automorphic equivalence with those de- rived from positional embeddings, using a distance threshold 'pe 10-4 to construct equivalence classes. Specifically,
Clearly, the assumption of trivial equivalence classes limits the ability of GCL to capture richer graph structures. Treat-
6

---

Equivalence is All: A Unified View for Seff-supervised Graph Learning
ing each node separate equivalence class ignores simi- larities between nodes, such automorphic equivalence or attribute-based similarity.
ing methods, including GCN (Kipf & Welling, 2017) and GIN (Xu et al., 2018); 2) four kernel-based methods, including SP (Borgwardt & Kriegel, 2005), GK (Sher- vashidze et al., 2009), WL (Shervashidze et al., 2011), DGK (Yanardag & Vishwanathan, 2015); 3) three unsuper- vised methods, including NODE2VEC (Grover & Leskovec, 2016), SUB2VEC (Adhikari et al., 2018), GRAPHIVEEC (Narayanan et al., 2017); 4) five self-supervised graph con- trastive learning, including INFOGRAPH (Sun et al., 2020), GRAPUCL (You et al., 2020), AD-GCL (Suresh et al., 2021), JOAOv2 (You et al., 2021), RGCL (Li et al., 2022), SIM- GRACE (Xia et al., 2022), SEGA (Wu et al., 2023), and AUTOGCL (Yin et al., 2022); For node-level tasks: 1) Su- pervised learning methods, including MLP and GCN (Kipf & Welling, 2017): 2) Graph embedding methods, including DEEPWALK (Perozzi et al., 2014) and NODE2VEC (Grover & Leskovec, 2016); 3) Graph contrastive learning methods, including VGAF (Kipf& & Welling, 2016). DGI (Velickovic et al., 2019), GMI (Peng et al., 2020), MvGRL (Hassani & Khasahmadi, 2020), GRACE (Zhu et al., 2020), GCA (Zhu et al., 2021). BGRL (Thakoor et al., 2022), CCA-SSG (Zhang et al., 2021) and SUGRI(Mo et al., 2022).
7.2. Role of Augmentation and Contrastive
GCL primarily relies on two mechanisms: graph augmen- tation and a contrastive loss that implicitly enforces equiv- alence class constraints. To disentangle their respective contributions, we conduct ablation studies on the loss in Eq. (10) using five benchmark datasets (Kipf & Welling, 2017). In the first ablation (w/o aug), we remove graph aug- mentations and perform contrastive learning on two iden- tical views of the graph (i.e., G1 G2), using single shared encoder (instead of two). This design isolates the effect of augmentation by ensuring there is no variation in the contrastive loss other than the inherent randomness in training. In the second ablation (w/o Pos), we modify the contrastive loss by removing positive pairs-iee., the term encouraging the similarity of | and zndand negative sample term. This effectively disrupts the equiv- alence class constraint, as nodes are no longer required to maintain consistent representations across views. Table 4 presents the corresponding results.
and retain only the
Protocol. We follow the standard evaluation protocol of pre- vious state-of-the-ar supervupee learning methods. For node classification, we report the mean accuracy on the test set after 50 runs of training. Pretrained node embeddings are used to train a linear neural network for classification. The dataset is split into 10%/10%/80% for training, vali- dation, and testing, respectively. For graph classification, we evaluate the learned graph representations using linear SVM classifier. We report the mean 10-fold validaiai accuracy across 5 runs. For each training fold, the linear SVM is tuned using validtttn, and the best mean accuracy is reported. The dataset is split into 80%/10%//10% for training, validation, and testing, respectively.
Table 4. Node classification accuracy (%) without augmentation.
Dataset
Cora
Citeseer
PubMed
Amz-Comp.
Con-CS.
Ang-Pos
83.26 0.56
73.20
+ 0.37
81
0.58
88.85 + 0.30
92.71 + 0.33
w/o Aug
82
0.60
72.79
1.211
8086
1.72
88.42 1 0.44
92.22
0.29
w/o Pos
70.10 0.39
61.47
0,48
80.37
0.51
86.27 0.21
89.38 0.36
The results in the table show that removing graph augmen- tations has minor impact on performance, indicating that augmentations are not the primary driver of GCL's effec- tiveness. In contrast, removing positive pairs significantly reduces performance across most data, highlighting the im- portance of equivalence constraints in the contrastive loss.
Implementation Details. We implement both GALE and its variant GALE-APR using PyTorch Geometrie. The key difference is that GALE uses Nauty (McKay & Piperno, 2014) for exact automorphisms, while GALFE-APR em- ploys PageRank equivalence with a = 0.85. For node attributes, both rely on ~ with cE "o.,,...,101] We adopt the Adam optimizer, tuning learning rates {0.0001, 0.001, 0.013, batch sizes {16, 64, 256, 512]. As iterations increase, Intra-class loss (4) dominates, caus- ing the total loss (6) to become imbalanced and too small. We can add Softplus after the discriminator to mitigate this.
8. Comparison with the SOTA Methods
8.1. Experimental Setup
Datasets. We evaluate the proposed model on both node classification and graph classification tasks. For node classification, we use 8 benchmark datasets: Cora, Cite- seer, Pubmed (Kipf& & Welling, 2017). Wiki-CS, Amazon- Computers, Amazon-Photo, Coauthor-CS, and Coauthor- Physies (Shchur et al., 2018). For graph classification, we evaluate on 8 datasets from the TUDataset benchmark (Mor- ris et al., 2020), including NCI1, PROTEINS, DD, MUTAG, COLLAB, RDT-B, RDT-M5K, and IMDB-B.
8.2. Results and Analysis
Performance on Graph-level Tasks. We evaluate whether GALE and its variant GALF--PP can outperform state-of- the-art methods on multiple graph-level benchmarks. Table 5 summarizes the results for both supervised and unsuper- vised baselines. Overall, GALE achieves top-tier perfor-
Baselines. We compare our method against a wide range of baseline methods across both nove-level and graph- level tasks. For level task: 1) two supervised learn-
7

---

Equivalence is All: A Unified View for Self-supervised Graph Learning
Table Supervised and unsupervised classification accuracy (%) on TU datasets. The highest unsupervised performance shaded
green, and the second-highest performance is shaded in light green. "-' means that the results are unavailable.
Model
NCI1
PROTEINS
DD
MUTAG
COLLAB
RDT-B
RDT-M5K
IMDB-B
GCN
80.20 1 0.14
74,92 1 0.33
76.24 L.14
85.63 0.24
79.01 1 0.18
50.00 0.10
20.00
0.10
70.45 1 0.37
GIN
82.75 + 0.19
76.28 + 0.28
78.91
0.13
89.47 0.16
80.23 + 0.19
92.44 0.25
56.50
0.24
73.70 + 0.60
SP
73.53 1: 0.16
75.07 1 0.54
>ld
85.25 0.24
64.13 1 0.04
39.64
0.02
55.62 1 0.02
GK
66.06 0.12
71.67 = 0.55
78.53 + 0.03
81.71 +
71.81 + 0.31
77.32 = 0.02
41.06
65.93 + 0.10
WL
80.01 + 0.50
72.92 + 0.56
79.78 0.36
80.76 00.76:10.33
69.30 + 0.42
68.82 + 0.41
0.21 46.06
72.30 + 0.44
DGK
79.98 0.36
73.21 + 0.61
74.79 + 0.32
87.51 0.65
64.43 + 0.48
78.35 0.43
0.32 41.49
67.09 + 0.37
NODE2VEC
54,93 0.16
$7.58 1 0.36
72.62 1 1.02
56.12 1 0.02
50.25 1 0.09
SUB2VEC
53.06 0.15 0.56
54.33 0.24
61.17 + 1.59
55.26 + 0.15
71.48 + 0.42
36.68 1 0.42
55.34 + 0.15
GRAPHZVEC
73.33 0.21 0.12
79.32 + 0.29
83.28 0.93
71.10 + 0.54
75.78 + 0.96
46.86
71.16 + 0.05
INFOGRAPH
76.33 1.79
74,27 1 0.43
73.02 1 1.31
88.65 1. 1.09
70.41 1 0.34
83.06 1 0.82
1.10 55.85
53.45
72.97 1 0.49
GRAPHCL.
+.34
74.41 + 0.35
78.49 0.36
86.62 + 1.23
71.28 + 1.16
89,50 + 0.73
0.33
71.29 + 0.38
AD-GCL
73.33 0.62
75.74
88.70 1.66
72.01 + 0.53
90.04 0.76
0.400
7U.35 1 0.59
JOAOV2
0.53 74.02 0.22
77.36
87.23 1.12
69.05 + 0.22
86.36 = 0.30
0.30
70.12 0.27
0.25
ROCL
78.14
75.11 1.55
78.77 1.552
87.62 1 1.16
70.85 1 0.63
90.27 0.54
56.39
0.37
71.67 1 0.76
SIMGRACE
75.26 0.24
77.13
89.23 1.25
71.26 + 0.51
89.41 0.33
55.91
0.23
71.22 + 0.30
SEGA
19.15
76,00 0.68
78.81 0.33
90.23 1 0.89
74.10 + 0.62
90.12 + 0.46
56.08 0008800 0.40
73.60 + 0.33
AUTOGEL
78.39 0.58
69.80 1 0.38
75.76 1 0.93
85.22 1: 1.43
71.40 1 0.26
86.56 1 1.31
55.68 + 0.23
72.26 1 0.34
GALE
80,04 = 0.43
81,15 = 0.31
80.63
0.78
91.12 + 0.93
75.95 + 0.21
90.10 + 0.49
56.56 0.40
77.66 + 0.11
GALE-APR
79.07 100::000 0.30
81.11 + 0.55
80.04 + 0.48
90.52 + 1.20
75.11 + 0.29
90.03 + 0.78
55.89 0.29
76.78 + 0.27
Table Mean node classification accuracy for supervised and unsupervised models. The highest unsupervised performance is shaded green, and the second- -hiohdt performance is shaded in light green. OOM indicates Out-Or-Memory on 24GB GPU.
Model
Cora
CiteSeer
PubMed
WikiCS
Amz-Comp.
Amz-Photo
Coauthor-CS
Coauthor-Phi
MLP
47.92 + 0.41
49.31 + 0.26
69.14 + 0.34
71,98 + 0.42
73.81 0.21
78.53 0.32
90.37 + 0.19
93.58 0.41
GCN
81.54 1 0.68
70.73 1 0.65
79.16 1 0.25
93.02 1 0.11
86.51 1 0.54
92.42 1. 0.22
93.03 1 0.31
95.65 1 0.16
DEEPWALK
70.72 : 0.63
51.39 1 0.41
73.27 1 0.86
74.42 + 0.13
85.68 + 0.07
89.40 0.11
84.61 +: 0.22
91.77 1 0.15
NODE2VEC
71.08 + 0.91
47.34 + 0.84
66.23 + 0.95
71.76 + 0.14
84.41 0.14
89.68 0.19
85. + 0.04
91.23 0.07
VGAE
77.27 1 0.86
67.46 1 0.20
76.02 1 0.52
75.55 1 0.22
86.40 0.30
92.13 0.12
92.10 1 0.31
94,43 1 0.20
DGI
82.24 - 0.63
71.82
1 0.61
76.80 1 0.30
75.42 1 0.17
84.05 0.42
0.37 91.62
92.14 0.55
94.54 1 0.52
GMI
82.40 0.57
71.74
0.12
79.28 + 0.94
0.16 74.79
90.81
00M
OOM
MVGRL
83.37 1 0.65
73.29
0.36
80.33
0.61
77.55 0.06
87.45
91.77 0.21
92.24 0.31
95.30 1 0.13
GRACE
81.88 = 0.84
71.13 0.42
80.83 + 0.13
79.37 0.24
86.48 0.24
92.20
92,90 0.27
95,25 + 0.26
GCA
82.41 = 0.55
71.56
1 0.19
80.73
78.26
+
$7.92
92.35
92.65 + 0.32
95,52 0.21
BGRL
81.86 = 0.32
72.10
+ 0.31
80.65 - 0.42
79.28
= 0.45
8921
0.47
92.28
+
92.73 0.41
95.31 = 0.26
SUGRL
83.29 0.38
73.11
1 0.22
81.96 1 0.49
78.88
1 0.35
88.98 1 0.20
92.87
0.19
92.84 1 0.24
94.80 1 0.24
CCA-SSG
84.17 = 0.44
73.27
1 0.30
81.91
1 0.41
77.67
1 0.29
88.85
0.22
93.14 4: 0.43
93.23 1 0.16
95.29 1 0.11
GALE
85.36 = 0.15
74.58
+ 0.18
85.06 + 0.27
82,15 + 0.22
90.60 = 0.19
94.51 + 0.34
93,46 = 0.28
95,91 = 0.38
GALE-APR
85.14 1 0.26
75.35
1 0.10
84.57 1 0.11
82.07 1 0.36
90.27 1 0.20
94.38 1 0.46
93.45 1 0.32
95.86 1 0.23
mance: for instance, on PROTEINS it outperforms the best self-supervised baseline SEGA by 5.15%, and on IMDB-B it surpasses GIN by 3.96%. Meanwhile, GALE-APR ex- hibits a similar pattern, slightly underperforming GALE on few datasets but still outperforming most baselines. In summary, both GALE and GALE--PRR demonstrate superior performance across a wide range of graph-level tasks.
9. Conclusion
This paper proposes a unified self-supervised graph rep- resentation framework, GALE, which integrates structural automorphism and attribute equivalence to construct joint equivalence classes Such combined equivalences are fre- quently encountered in real-world scenarios, including com- puting networks. To address computational bottlenecks and noise interference, we design an efficient approxima- tion strategy with linear complexity. GALE preserves the similarity of equivalent nodes while enforcing separation between representations of non-equivalent nodes. Analysis reveals the inherent limitations of mainstream graph mod- els, including over-smoothing in MPNNs, failure to respect automorphism constraints in Transformer positional encod- ings, and the degeneration of graph contrastive learning into single-node equivalence. Experimental results demonstrate the superiority of GALE.
Performance under Node-level. Table 6 summarizes our results on eight node-level benchmarks, showing that both GALE and GALE-APR not only outperform the strongest unsupervised models but also exceed the supervised base- line GCN across most datasets. For instance, on PubMed, GALE achieves 85.06%, surpassing the best unsupervised method SUGRL by over 3.1% % and supervised method GCN by 5.9%. Mcanwhile, GALE-APR stays highly competitive, for example on Coauthor-CS it closely matching GALEE, thus confirming the effectiveness of our approach.
8

---

Equivalence is All: A Unified View for Self-supervised Graph Learning
Acknowledgments and Disclosure of Funding
Friedkin, N. E. and Johnsen, E. C. Social positions in influ- ence networks. Social networks, (9(3):209-222 1997.
This project was in part supported by the following projects: the National Natural Science Foundation of China (No.62432003, No. 92262266.
Ghorbani, M., Dehmer, M., Lotfi, A., Amraei, N., Mow- showitz, A., and Sanmert-Streib, F. On the relationship between pagerank and automorphisms of graph. Infor- mation Sciences, 579:401-4111 2021.
Impact Statement
This paper aims to advance Graph Learning, with potential societal impacts that don't 't require specific highlighting here.
Grover, A. and Leskovec, J. Node2vec: Scalable fea- ture learning for networks. In Proceedings of the ACM SIGKDD International Conference on Knowledge Dis- covery and Data Mining, pp. 855-864, 2016.
References
Hassani, K. and Khasahmadi, A. H. Contrastive multi-view representation learning on graphs. In Proceedings of the International Conference on Machine Learning, pp. 4116-4120 PMLR, 2020.
Adhikari, B., Zhang. Y., Ramakrishnan, N., and Prakash, B. A. Sub2vec: Feature learning for subgraphs. In Pacific- Asia Conference on KDDM, pp. 170-182. Springer, 2018.
Bafai, L.
Isomorphism problem for a class of point- symmetric structures. Acta Mathematica Hungarica, 29 (3-4):329-333 1977.
Junttila, T. and Kaski, P. Conflict propagation and com- ponent recursion for canonical labeling. In Theory and Practice of Algorithms in (Computer) Systems, volume 6595, pp. 151-162. Springer, 2011.
Belkin, M. and Niyogi, P. Laplacian eigenmaps and spectral techniques for embedding and clustering. Advances in Neural Information Processing Systems, 14, 2001.
Kipf, T. and Welling, M. Variational graph auto-encoders. Bayesian Deep Learning, NIPS 2016 Workshop, 2016.
Borgwardt, M. and Kriegel, H.-P. Shortest-pati kernels on graphs. International Conference on Data Mining, pp. pp.-. IEEE, 2005.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. International Conference on Learning Representations, 2017.
Cai, X., Huang, C., Xia, L., and Ren, X. LightGCL: Simple yet effective graph contrastive learning for recommenda- tion. In International Conference on Learning Represen- tations, 2023.
Koh, H. Y. Nguyen, A. T., Pan, S., May, L. T., and Webb, G. I. Physicochemical graph neural network for learn- ing protein-ligand interaction fingerprints from sequence data. Nature Machine Intelligence, 6(6):673-687, 2024.
Cameron, J. and Mary, Q. Automorphisms of graphs. Topics in algebraic graph theory, 102:137-155, 2004.
Kondaveeti, D., Inampudi, R. K., and Kurkute, M. V. Time complexity analysis of graph algorithms in big data: Eval- uating the performance of pagerank and shortest path algorithms for large-scale networks. Journal of Science and Technology, 5(4): Aug. 2024.
Cao, S., Lu, W., and Xu. Q. Deep neural networks for learning graph representations. In Proceedings of the AAAI Conference Artificial Intelligence, number 1, 2016.
Kondor, R. and Trivedi, S. On the generalization of equivari- ance and convolution in neural networks to the action of compact groups. In Proceedings of the International Con- ference on Machine Learning, pp. 2747-2755. PMLR, 2018.
Dwivedi, P., Luu, A. T., Laurent, T., Bengio, Y., and Bres- son, X. Graph neural networks with learnable structural and positional representations. In International Confer- ence on Learning Representations, 2022.
Kreuzer, D., Beaini, D., Hamilton, W., Létourneau, V., and Tossou, P. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34:21618-2162 2021.
Everett, M. G. Role similarity and complexity in social networks. Social Networks, 7(4):353-359, 1985.
Faulon. J.-L. Isomorphism, automorphism partitioning, and canonical labeling can be solved in polynomial-time for molecular graphs. Journal of Chemical Information and Computer Sciences, 38(3):432-444 444, 1998.
Langville, A. N. and Meyer, C. D. Deeper inside pagerank. Internet Mathematics, 1(3):335-380 2004.
Lauri, J. and Scapellato, R. Topics in graph automorphisms and reconstruction, volume 432, Cambridge University Press, 2016.
Fortunato, S. Community detection in graphs. Physics reports, 486(3-5):75-177, 2010.

---

Equivalence is All: A Unified View for Self-supervised Graph Learning
Li, S., Wang, X., Zhang, A., Wu, Y., He, X., and Chua, T.-S. Let invariant rationale discovery inspire graph contrastive learning. In Proceedings of the International Conference on Machine Learning. pp. 13052-13065, 2022.
Peng, Z., Huang. W., Luo, M., Zheng, Q. Rong, Y., Xu, T., and Huang. J. Graph representation learning via graphical mutual information maximization. In The Web Confer- ence, pp. 259-270 2020.
Lim, D., Robinson, J. D., Zhao, L.,, Smidt, T., Sra, S., Maron, H., and Jegelka, S. Sign and basis invariant networks for spectral graph representation learning. International Conference on Learning Representations, 2023.
Perozzi, B., AI-Rfou, R., and Skiena, Deepwalk: Online
learning of social representations. In Proceedings of the ACM SIGKDD International Conference Knowledge Discovery and Data Mining. Pp. 701-710, 2014.
Liu, J., Tang, H., and Liu, Y. Perfect alignment may be poisonous to graph contrastive learning. In Proceedings of the International Conference on Machine Learning, 2024a.
Rampášek, L.., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. Recipe for general, powerful, scal- able graph transformer. In Advances in Neural Informa- tion Processing Systems, 2022.
Liu, Y., Li, S., Zheng, Y., Chen, Q.. Zhang, C., and Pan, S. Are: A generalist graph anomaly detector with in-context learning. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomczak, J., and Zhang, C. (eds.), Advances in Neural Information Processing Systems, vol- ume 37, pp. 50772-50804, 2024b.
Rand, W. M. Objective criteria for the evaluation of cluster- ing methods. Journal of the American Statistical associa- tion, (6(336):846-8855 1971.
Shchur, O., Mumme, M., Bojchevski, A., and Günnemann, S. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurIPS, 2018.
Lorrain, F. and White, H. C. Structural equivalence indi- viduals in social networks. The Journal of mathematical sociology, 1(1):49-80, 1971.
Shervashidze, N., Vishwanathan, S., Petri, T., Mehlhorn, K., and Borgwardt, K. Efficient graphlet kernels for large graph comparison. In Artificial Intelligence and Statistics, pp. 488-495. PMLR, 2009.
McKay, B. D. and Piperno, A. Practical graph isomorphism, ii Journal of Symbolic Computation, 60:94-115 112, 2014.
Shervashidze, N., Schweitzer, P., Van Leeuwen, E. J., Mehlhorn, K., and Borgwardt, K. M. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Meilä, M. Comparing clusterings-an information based distance. J. Multivar. Anal., (8(5))873-89)) 2007.
Min, F., Chen, R., Bian, Y., Xu, T., Zhao, K., Huang, W., Zhao, P., Huang, J., Ananiadou, S., and Rong, Y. Trans- former for graphs: An overview from architecture per- spective. arXiv preprini arXiv:2202.084553 2022.
Sun, F.Y Hoffman, J., Verma, V., and Tang. J. Infograph: Unsupervised and semi-supervised graph-level represen- tation learning via mutual information maximization. In International Conference on Learning Representations, 2020.
Mo. Y., Peng, L., Xu, J., Shi, X., and Zhu, X. Simple unsupervised graph representation learning. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 36. pp. 7797-7805, 2022.
Suresh, S., Li, P., Hao, C., and Neville, J. Adversarial graph augmentation to improve graph contrastive learning. Advances in Neural Information Processing Systems, 34: 2021.
Morris, C., Kriege, N. M., Bause, F., Kersting, K., Mutzel, P., and Neumann, M. Tudataset: A collection of bench- mark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond, 2020.
Thakoor, S., Tallec, C., Azar, M. G., Azabou, M., Dyer, E. L., Munos, R., Veličković, P., and Valko, M. Large- scale representation learning on graphs via bootstrapping. In International Conference on Learning Representations, 2022.
Narayanan, A., Chandramohan, M., Venkatesan, R., Chen, L., Liu, Y., and Jaiswal, S. Graph2vee: Learning dis- tributed representations of graphs. 1077v:1707.05005, 2017.
Thiede, E., Zhou, W., and Kondor, R. Autobahn: Automorphism- graph neural nets. Advances in Neu- ral Information Processing Systems, 34:29922-29934, 2021.
SearceCruup. E. and Knottenbelt, W. J. Graph automor- phism group equivariant neural networks. In Proceedings of the International Conference on Machine Learning. JMg,. 2024.
Velickovic, P., Fedus, W., Hamilton, W. L.L., Lid, P., Bengio, Y., and Hjelm, R. D. Deep graph infomax. In Interna- tional Conference on Learning Representations, 2019.
10

---

Equivalence is All: A Unified View for Self-supervised Graph Learning
Wan, G., Tian, Y., Huang, W., Chawla, N. V., and Ye, M. S3GCL: Spectral, swift, spatial graph contrastive learn- ing. In Proceedings of the International Conference Machine Learning, 2024.
Yin, Y., Wang, Q., Huang, S., Xiong, H., and Zhang, X. Au- togel: Automated graph contrastive learning via learnable view generators. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 8892-8999 29000 2022.
Wang. J., Cui, Z., Wang, B., Pan, S., Gao, J., Yin, B., and Gao, W. Ime: Integrating multi-curvature shared and specific emhedding for temporal knowledge graph completion. In Proceedings of the ACM Web Conference 2024, pp. 1954-1962. 2024a.
You, Y., Chen, T., Sui, Y., Chen, T., Wang. Z., and Shen, Y. Graph contrastive learning with augmentations. Ad- vances in Neural Information Processing Systems, 33: 5812-58233 2020.
You, Y., Chen, T., Shen, Y., and Wang, Z. Graph con- trastive learning automated. In Proceedings of the Inter- national Conference Machine Learning, pp. 12121 12132, 2021.
Wang. J., Kai, S., Luo, L., Wei, W., Hu, Y., Liew, A. W.- C., Pan, S., and Yin, B. Large language godded dynamic adaptation for temporal knowledge graph reason- ing. Advances in Neural Information Processing Systems, 37:8384-8410, 2024b.
Zhang, H., Wu, Q. Yan, J., Wipf, D., and Yu, P. S. From canonical correlation analysis to self-supervised graph neural networks. Advances in Neural Information Pro- cessing Systems, 34:76-89 89, 2021.
Wang, J., Wang. B., Gao, J., Pan, S., Liu, T., Yin, B., and Gao, W. Made: Multicurvature adaptive embedding for temporal knowledge graph completion. IEEE Transac- tions on Cybernetics, 2024c.
Zhao, Y., Wang, Y., Wang. Z., Shan. W., Huang, M.. and Wang, X. Graph contrastive learning with progressive augmentations, In Proceedings of ACM SIGKDD Con- ference on Knowledge Discovery and Data Mining, pp. 2079-2088, 2025.
Wang, Y., Zhao, Y., Wang, D. Z., and Li, L. Galopa: Graph transport learning with optimal plan alignment. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 9117-9130, 2023.
Zhu, Y.. Xu, Y., Yu, F. Liu, Q. Wu, S., and Wang. L. Deep graph contrastive representation learning. WxXiv:2006.443/1 2020.
Wasserman, S. and Faust, K. Social network analysis: Meth- ods and applications. 1994.
Zhu, Y., Xu, Y. Yu, F., Liu, Q., Wu, S., and Wang, L. Graph contrastive learning with adaptive augmentation. In The Web Conference, pp. 2069-2080 2021.
Wu, J., Chen, X., Shi, B., Li, S., and Xu, K. SEGA: Struc- tural entropy guided anchor view for graph contrastive learning. In Proceedings of the International Conference on Machine Learning, volume 202, pp. 37293-37311 2023.
Wu, Z., Pan, S., Chen, F,, Long, G., Zhang, C., and Philip, S. Y. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4-24 2020.
Xia, J., Wu, I.., Chen, J., Hu, B., and Li, S. Z. Simgrace: A simple framework for graph contrastive learning without data augmentation. In Proceedings of the ACM Web Conference 2022, pp. 1070-1079, 2022.
Xu, F., Yao, Q., Hui, P., and Li, Y. Automorphic equivalence- aware graph neural network. Advances in Neural Infor- mation Processing Systems,
2021.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2018.
Yanardag, P. and Vishwanathan, S. Deep graph kernels. In Proceedings of the ACM SIGKDD International Con- ference on Knowledge Discovery and Data Mining, pp. 1365-1374 2015.

---

Equivalence is All: A Unified View for Self-supervised Graph Learning
A. Impact of a on PageRank Equivalence
To analyze the impact of different a values in PageRank on the resulting equivalence classes, we conduct experiments on four benchmark datasets: Cora, Citeseer, Amz-Photo, and Coauthor-CS. The a values range from 0.1 0.9 with an increment of 0.1, and for each dataset, we compute the Variation of Information (VI) (Meilä, 2007) between equivalence partitions obtained under different settings. This results in x 9 heatmaps for each data, which are visualized in Figure 4.
Our findings reveal that the differences between equivalence classes under varying values are minimal across all datasets. For instance, in the Cora dataset, the VI values are consistently in the range of 0.001, indicating negligible variation. Similarly, in the Photo dataset, we observe 33 perfect matches (VI= 0) across different parameter pairs, further demonstrating the robustness of PageRank equivalence classes to changes a.
These results suggest that the choice of has little effect on the overall structure of the equivalence classes derived from PageRank scores. This stability highlights the reliability of using PageRank for approximating equivalence relations in graphs, regardless of the specific damping factor chosen.
c1611
0.3
0.3
02
0.3
0181 022
8-3
D5
06
5.9
a10'1 02
0.92200
5.354
5:03
0.00
C.001
0.30
0
1022
BO0G 0,002
3
0001
600
6.00
5.00
0:03
902
0.055 0503
5.04
3.01
0.00 0:00
OCE3 8000
0002
5.00 0.00
0021 0.221
3001
5,022
5902
0.01
BJ0G 0,02
0001
0.00
5.30
5000
0.022
0:00
0.02
0.000
8.01
0:00
0.00
0/01
0:21
0.022
E912
0000
C:0
800
B004 Gu00
6:022 0:80 0002
0000
0.000
5:3M
8006
5:00
6:08
0:00
0196
0 9.000 5.000
5:14
8.00
5000 0.00
0,00 6:22
0.01 0101 8.5
5.300
0.00
0990
0202
0.000
8:90
9000
2391
0.00
0:30
0.02
5.99
CMM
1004 0.00-
0.000
0.00
0004
8:004
2000
0.004
2009
0.000
2:01 131 0.00
2.144 2009 5.000
9
0.00
6
0.02
0.011 0221 3.50
C.001
(a) Cora
(b) Citeseer
(c) Amz-Photo
(d) Coauthor- CS
Figure 4. Heatmaps showing the Variation of Information (VT) values between PageRank equivalence classes obtained under different values, for four datasets. Lighter colors indicate lower VI values, signifying greater similarity between equivalence partitions.
B. Related [ork[Extended]
Equivalence in Graphs Neural Networks. There have been recent advancements in incorporating automorphic equivalence (AE) (Kondor& & Trivedi, 2018) into graph neural networks (GNNs), GRAPE (Xu et al., 2021) introduces ego-centered automorphic equivalence to differentiate nodes within localized neighborhoods using subgraph template, while Autobahn (Thiede et al., 2021) performs local equivariant convolutions over subgraph automorphism groups, improving adaptability for tasks like molecular property prediction. Pearce-Crump& & Knottenbelt (2024) primarily focuses on the theoretical analysis and generalization of neural network design by characterizing learnable, linear, Aut(G))-quivariian neural layers, leveraging bilabelled graphs to compute representations. In contrast, our work introduces a self-supervised learning framework that not only considers structural equivalence but also incorporates node attribute information, enabling the joint learning of structural roles and attribute semantics to offer a comprehensive perspective.
C. Ablation Study
C.1. Contribution of Automorphic and Feature Equivalence
To evaluate the importance of incorporating both automorphic and node attributes equivalence in our framework, we conduct ablation experiments on eight benchmark datasets: Cora, Citeseer, Pubmed, Wikics, Computers, Photo, CS, and Physics. We compare the performance of the full model (origin) with two variants: 1) w/o auto: This variant removes automorphic equivalence information, relying solely on node attributes for equivalence class partitioning. 2) w/o feat: This variant removes node attribute equivalence, relying only automorphic equivalence for equivalence class partitioning.
The results, summarized in Table 7, show that excluding either automorphic or node attributes equivalence leads to performance degradation across all datasets. The experimental results reveal the following key observations. 1) Effect of removing automorphic equivalence (w/o auto): When automorphic equivalence is excluded, the performance consistently declines across all datasets. This is because solely relying on node attributes ignores the structural information that helps
12

---

Equivalence is All: A Unified View for Seff-supervised Graph Learning
distinguish nodes with similar attributes but different structural roles in the graph. For example, in social network, two users may both have similar attributes, such as age, profession, or location, but one might be central influencer (hub node) while the other is a peripheral user with few connections. Ignoring automorphic equivalence would fail to capture the distinct structural importance of these users. 2) Effect of removing feature equivalence(w/o feat): Excluding attributes equivalence also leads to a performance drop, sometimes more significant than w/o auto, particularly in datasets like Citeseer. Without feature equivalence, nodes with very different characteristics may be grouped together solely based on automorphic equivalence, reducing the model's discriminative power. For instance, social network, nodes with high structural similarity (e.g.. both being part of tightly connected communities) but vastly different attributes (e.g.. different professions) could be inappropriately treated equivalent.
These findings underscore the importance of integrating both automorphic equivalence and node attribute information. The combination of structural and attribute-based perspectives ensures a more comprchensive representation of node equivalence, effectively capturing both the roles and features of nodes in the graph.
Table 7. Ablation study results on 8 datasets. origin represents the full model. while w/o auto and w/o feat represent the ablated models.
Methods
Cora
CiteSeer
PubMed
WikiCS
Amz-Comp.
Amz-Photo
Co-CS
Co-Phy
origin
85.36 + 0.15
74.58 = 0.18
85.06 + 0.27
82,15 + 0.22
90.60 + 0.19
94.51 + 0.34
93,46 + 0.28
95.91 + 0.38
w/o auto
82.25 0.09
72.44 0.12
83.63 + 0.30
81.03 + 0.34
88.30 + 0.28
93.07 + 0.36
92.37 0.41
94.46 0.13
w/o feat
80.42 0.24
64.72 0.30
83.22 + 0.21
80.87 + 0.27
88.84 + 0.16
94.50 + 0.29
91.98 + 0.17
93.19 0.44
C.2. Evaluation of Equivalence Fusion Operator
This section presents an ablation study to empirically evaluate and justify our choice of using the intersection operator for fusing node equivalences in our proposed model (referred to as origin). An alternative fusion strategy, based on the union operator, was implemented and compared. The primary goal is to assess how these different fusion methods impact overall model performance, particularly in capturing meaningful node similarities derived from diverse equivalence criteria (c.g.. those based on automorphic properties and node attributes).
Table 8 summarizes the performance results on the eight benchmark datasets when employing either the intersection- (origin) umion-based (union) fusion approach. The experimental results presented in Table 8 demonstrate that the proposed model, which employs intersection fusion, consistently outperforms the union fusion approach. This is largely because emphasizing one equivalence type (either automorphic equivalence or node attributes) by using the union tends to neglect the contributions from the other. In contrast, the intersection method ensures that both types of equivalences jointly contribute, leading to a more robust and comprehensive representation of node similarity. These findings justify our choice of the intersection method for fusing equivalences.
Table 8. Ablation study results comparing intersection (origin model) and union (union model) for fusing equivalences on 8 datasets.
Methods
Cora
CiteSeer
PubMed
WikiCS
Amz-Comp.
Amz-Photo
Co-CS
Co-Phy
origin
85.36 1 0.15
74,58 0.18
85.06 + 0.27
82.15 + 0.22
90.60 : 0.19
94.51 + 0.34
93.46 + 0.28
95.91 + 0.38
union
77.21 + 0.22
64.37 0.12
83.22 + 0.19
80.96 + 0.34
87.86 = 0.25
93.59 + 0.28
91.55 + 0.15
94.93 + 0.36
D. Rand Index Results
In the main body of the paper, we evaluated the alignment between true automorphic equivalence classes (=aun)) and our PageRank- based approximation (<ip) using the Variation of Information (VI) metric (detailed in Table 2). To provide a more comprehensive validation of this alignment, in this section we presents supplementary results using the Rand Index (RI) (Rand, 1971). The RI is another widely recognized metric for comparing the similarity between two data partitions.
The Rand Index assesses agreement by considering all possible pairs of elements and checking if each pair is consistently placed (i.e., either together in both partitions or separated in both partitions). It produces score ranging from 0 to 1, where 1 signifies perfect agreement between the two partitions, and values closer to I indicate high degree of similarity. Table 9 reports the RI scores for the alignment between Eatoo and PPR across the same eight benchmark datasets analysed in the main text. The consistently high RI values, approaching for nearly all datasets, strongly corroborate the findings obtained with the VI metric.
13

---

Equivalence is All: A Unified View for Self-supervised Graph Learning
Table Rand Index (RT) for alignment between equivalences Satto and 2yR eight benchmark datasets (higher is better, perfect).
Data
Cora
CiteSeer
PubMed
WikiCS
Amz-Comp.
Amz-Photo
Co-CS
Co-Phy
(t) 0.99948
0.99687
0.99999
0.99999
0.99999
0.99998
0.99999
0.99999
E. Sensitivity Analysis of PageRank Teleportation
To evaluate the impact of hyperparameter choices on model performance, conducted sensitivity analysis on the Cora dataset with respect to the PageRank teleportation parameter (a). The parameter was varied from 0.1 to 0.9, and the corresponding model performance is reported in Table 10.
Table 10. Sensitivity analysis of the PageRank teleportation parameter (a) on the Cora dataset.
Dataset
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Cora
85.33 + 0.19 85.35 + 0.15
85,27
0,20
85,38 d: 0.12
85,23 + 0.19
85,36 +: 0.17 85,30 : 0.09
85.35
0.15
85.29
+: 0.24
As shown in Table 10, the model's accuracy remains stable across wide range of values, indicating that the performance not sensitive the choice of this hyperparameter.
F. Limitation and Futrue Work
While our core contribution focuses on static homogeneous graphs, we acknowledge two related limitations. First, GALE currently assumes static graph setting, meaning that for dynamic graphs with evolving structures or features, the equivalence classes may change over time, necessitating incremental updates partitions challenge common to equivalence- methods. Second, our present work targets homogeneous graphs; extending our equivalence definitions heterogeneous graphs (e.g., those with multi-typed nodes/edges) would require additional design considerations, such type-specific automorphism constraints. We consider these aspects as important directions for our future work.
14


Reviews:
[{"review_id": "hyHwF4ZQW7", "reviewer": "Reviewer_nMZa", "summary": "The paper introduces GALE, a self-supervised graph learning framework that unifies automorphic and attribute equivalence into a single node equivalence concept, enforcing intra-class similarity and inter-class dissimilarity through a novel loss function. The paper claims that by explicitly modeling and enforcing node equivalence, the proposed framework provides a more principled approach to self-supervised graph learning that improves upon traditional contrastive methods.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1. Using PageRank to approximate automorphic equivalence is an efficient approach, but nodes with similar PageRank scores are not necessarily structurally symmetric. Could this have impact on the model's performance?**\n\n>R1: We acknowledge that similar PageRank scores do not strictly guarantee structural symmetry. However, our experiments (see Table 2 in the paper) demonstrate that the approximate equivalence obtained via PageRank aligns almost perfectly with exact automorphic equivalence—indicated by Variation of Information (VI) values that are nearly zero (with 0 representing perfect alignment). This empirical evidence shows that instances where similar PageRank scores do not correspond to true structural symmetry are extremely rare in practice. Consequently, the impact on the overall model's performance is negligible, validating the effectiveness of our approximation approach.\n \n**Q2. The experimental tables (e.g., color-coded cells) may not fully convey information through text descriptions alone. It is recommended to add textual explanations in the paper, such as clarifying the meaning of \"VI\" values and specifying threshold ranges.**\n\n>R2: We appreciate the reviewer's suggestion. We will update the caption of Table 2 to the following:\n\n> _Table 2. Variation of Information (VI) between automorphic equivalence ($\\simeq_{\\text{auto}}$) and PageRank-based approximate equivalence ($\\simeq_{\\text{PR}}$) over eight benchmark datasets. Lower VI values (with 0 indicating perfect alignment) are shown in lighter colors._\n   \n**Q3. The paper would benefit from a discussion on the potential limitations of the model.**\n\n>R3: We thank the reviewer for recommending a discussion on potential limitations. While our core contribution focuses on static homogeneous graphs, we acknowledge two related limitations. First, GALE currently assumes a static graph setting, meaning that for dynamic graphs with evolving structures or features, the equivalence classes may change over time, necessitating incremental updates to partitions—a challenge common to equivalence-based methods. Second, our present work targets homogeneous graphs; extending our equivalence definitions to heterogeneous graphs (e.g., those with multi-typed nodes/edges) would require additional design considerations, such as type-specific automorphism constraints. We consider these aspects as important directions for our future work.\n\n**Q4. Some typos: - Line 75: Change \"noting\" to \"note\". - Line 252: Change \"indicates\" to \"indicating\". - Line 308 (right column): Change \"a\" to \"an\".**\n\n>R4: We thank the reviewer for pointing out these typographical errors. We will correct these typos in the revised version of the paper.\n\n**Q5. The definition of approximate attribute equivalence does not appear to satisfy transitivity (i.e., u≃v and v≃w do not necessarily imply u≃w). Does this mean it does not form a strict equivalence relation? If so, it is recommended to use \"similarity groups\" instead.**\n\n>R5: We thank the reviewer for this valuable observation. We acknowledge that the current definition of approximate attribute equivalence does not satisfy transitivity—meaning it does not form a strict equivalence relation. In light of this, we agree that referring to these groups as \"similarity groups\" may be more appropriate and accurately reflects their nature. We will make the necessary modifications in subsequent revisions of the paper.", "claims_and_evidence": "The paper’s claims are generally well supported by a combination of theoretical exposition, algorithmic design, and extensive empirical results.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I have checked the theoretical claim (Theorem 4.1) and the proof process appears to be correct.", "experimental_designs_or_analyses": "I have reviewed the Node and Graph Classification Experiments, Ablation Studies, Evaluation of Equivalence Alignment and the Over-smoothing Analysis. The experimental designs and analyses are sound.", "relation_to_broader_scientific_literature": "The paper interweaves classical graph theory with self-supervised learning techniques and deep neural architectures. \n\n- The paper extends traditional self-supervised graph learning methods, particularly graph contrastive learning (e.g., GRACE) by challenging the standard paradigm that treats each node as an isolated equivalence class.\n- The idea of automorphic equivalence has long been studied in graph theory, with foundational works focusing on graph isomorphism and symmetry detection (e.g., using algorithms like Nauty and Bliss).", "essential_references_not_discussed": "To my best knowledge, all the core references are cited correctly.", "other_strengths_and_weaknesses": "**Strengths.**\n\n1. The paper offers a new approach by unifying automorphic and attribute equivalence into a single framework, which is a very interesting perspective in self-supervised graph learning.\n\n2. The paper provides new insights from an equivalence-class perspective, such as over-smoothing in MPNNs and limitations in current positional encoding schemes in Graph Transformers.\n\n3. The paper is well-written.\n\n4. Extensive experiments demonstrate the advantages of the proposed approach.\n\n**Weaknesses.**\n\n1. Using PageRank to approximate automorphic equivalence is an efficient approach, but nodes with similar PageRank scores are not necessarily structurally symmetric. Could this have impact on the model's performance?\n\n2. The experimental tables (e.g., color-coded cells) may not fully convey information through text descriptions alone. It is recommended to add textual explanations in the paper, such as clarifying the meaning of \"VI\" values and specifying threshold ranges.\n\n3. The paper would benefit from a discussion on the potential limitations of the model.", "other_comments_or_suggestions": "Some typos:\n- Line 75: Change \"noting\" to \"note\".\n- Line 252: Change \"indicates\" to \"indicating\".\n- Line 308 (right column): Change \"a\" to \"an\".", "questions_for_authors": "1. The definition of approximate attribute equivalence does not appear to satisfy transitivity (i.e.,  $u \\simeq v$ and $v \\simeq w$ do not necessarily imply $u \\simeq w$). Does this mean it does not form a strict equivalence relation? If so, it is recommended to use \"similarity groups\" instead.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FNTD5ZTraF", "reviewer": "Reviewer_LJki", "summary": "This paper presents a novel framework for self-supervised graph representation learning that emphasizes the importance of node equivalence. The authors propose GALE, which unifies automorphic equivalence (based on graph structure) and attribute equivalence (based on node attributes) into a single equivalence class. The framework enforces the equivalence principle, ensuring that node representations within the same equivalence class are similar while those in different classes are dissimilar. Key contributions include the introduction of approximate equivalence classes with linear time complexity to address computational challenges, an analysis of existing graph encoders' limitations regarding equivalence constraints, and the demonstration that graph contrastive learning paradigms are a degenerate form of equivalence constraints. The paper also shows that GALE outperforms state-of-the-art baselines through extensive experiments on benchmark datasets. The authors provide a comprehensive analysis of the connections between equivalence classes and existing techniques, highlighting the potential of their approach to improve the performance and effectiveness of graph representation learning models.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1. The paper mentions connections to other fields such as social network analysis. However, it does not cite recent work that could provide additional context. For example, the paper by Santo Fortunato titled \"Community detection in graphs\" provides a comprehensive review of community detection methods in graphs.**\n\n>R1: Thank you for the helpful suggestion. We will include this reference \"Community detection in graphs\" in the revised version.\n\n**Q2. The paper only discusses the over-smoothing issue in MPNNs but does not mention existing mitigation techniques (e.g., residual connections). It would be helpful to discuss the relationship between equivalence constraints and these techniques.** \n\n>R2: Thank you for the suggestion. While residual connections help with gradient propagation, they do not explicitly distinguish between equivalent and non-equivalent nodes. Similarly, some methods dynamically alter neighbors in deeper GCNs to alleviate over-smoothing, but they also lack an explicit mechanism to differentiate between nodes and often require careful tuning. In contrast, our GALE approach explicitly enforces this distinction, making representations semantically meaningful. We will add this discussion to clarify the relationship between equivalence constraints and existing techniques in the revised version.\n\n**Q3. Although the introduction of approximate equivalence classes aims to address the computational complexity, a more in-depth discussion of the trade-offs between accuracy and efficiency would be valuable.**\n\n>R3: Thank you for the feedback. Our experimental results (see Tables 5 and 6) show that the approximate method may incur a slight precision drop compared to the exact method. However, it consistently outperforms current state-of-the-art methods, and in some datasets, it even surpasses the exact algorithm. This demonstrates that the efficiency gains come with only minimal trade-offs in accuracy, underscoring the effectiveness of our approach.\n\n**Q4. In the introduction, when referring to automorphic equivalence, the paper states that “permuting all nodes within the same equivalence class preserves the graph’s edge relations” However, strict graph automorphism involves a global permutation (an isomorphic mapping of the entire graph), rather than only permuting nodes within an equivalence class. This should be corrected to: \"There exists a global permutation that maps nodes within the same equivalence class to each other.\"**\n\n>R4: Thank you for the insightful comment. We appreciate your insight and will incorporate this change in the revised version of the paper. Thanks again.", "claims_and_evidence": "The claims made in this submission are generally well-supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria in this paper are appropriate for the problem of self-supervised graph representation learning.", "theoretical_claims": "The theoretical claims made in the paper are logically sound.", "experimental_designs_or_analyses": "The experimental designs and analyses in this paper are generally sound and well-executed.", "relation_to_broader_scientific_literature": "The paper is related to prior work on graph representation learning, social network analysis and self-supervised learning.", "essential_references_not_discussed": "The paper mentions connections to other fields such as social network analysis. However, it does not cite recent work that could provide additional context. For example, the paper by Santo Fortunato titled \"Community detection in graphs\" provides a comprehensive review of community detection methods in graphs.", "other_strengths_and_weaknesses": "Pros:\n\n1.The paper presents an unified framework for incorporating node equivalence into self-supervised graph representation learning. This combination of automorphic and attribute equivalence offers a interesting perspective on improving graph representation learning.\n2.The proposed framework addresses a gap in existing graph representation learning methods by explicitly considering node equivalence. This is a contribution to the field.\n3.The paper is well-written and well-structured, making it easy to follow the authors' reasoning and methodology.\n4.The experiment is capable of validating its conclusion.\n\nCons:\n\n1.The paper only discusses the over-smoothing issue in MPNNs but does not mention existing mitigation techniques (e.g., residual connections). It would be helpful to discuss the relationship between equivalence constraints and these techniques.\n2.Although the introduction of approximate equivalence classes aims to address the computational complexity, a more in-depth discussion of the trade-offs between accuracy and efficiency would be valuable.", "other_comments_or_suggestions": "In the introduction, when referring to automorphic equivalence, the paper states that “permuting all nodes within the same equivalence class preserves the graph’s edge relations” However, strict graph automorphism involves a global permutation (an isomorphic mapping of the entire graph), rather than only permuting nodes within an equivalence class. This should be corrected to: \"There exists a global permutation that maps nodes within the same equivalence class to each other.\"", "questions_for_authors": "1.The paper only discusses the over-smoothing issue in MPNNs but does not mention existing mitigation techniques (e.g., residual connections). It would be helpful to discuss the relationship between equivalence constraints and these techniques.\n2. Although the introduction of approximate equivalence classes aims to address the computational complexity, a more in-depth discussion of the trade-offs between accuracy and efficiency would be valuable.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JCOnavNlp2", "reviewer": "Reviewer_jbhi", "summary": "This paper introduces a self-supervised graph learning framework that unifies automorphic equivalence (structural symmetry) and attribute equivalence (node feature similarity) into a cohesive representation learning paradigm. The work bridges structural and feature-based node similarities, offering a principled approach to self-supervised graph learning while addressing scalability and practicality challenges.\n\nThanks to the author for the reply, this solved most of my problems, I will keep my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1. I have reviewed most of the experimental design and analysis, which appear comprehensive and reasonable. For the equivalence class matching evaluation, I recommend adding other classic metrics, such as the Rand Index.**\n\n>R1: Thank you for the valuable feedback. We have added a table below that includes the Rand Index results for our algorithm. The Rand Index is a well-established metric for evaluating matching performance, where values closer to 1 indicate a perfect match. Our results show that across nearly all datasets, the Rand Index is almost equal to 1, which further validates the performance and effectiveness of our approximate method.\n\n*Table I: Rand Index (RI) for alignment between equivalences $\\simeq_{\\text{auto}}$ and $\\simeq_{\\text{PR}}$ on eight benchmark datasets (higher is better, 1 is perfect).*\n\n|  **Data**  | **Cora** | **CiteSeer** | **PubMed** | **WikiCS** | **Amz-Comp.** | **Amz-Photo** | **Co-CS** | **Co-Phy.** |\n| :--------: | :------: | :----------: | :--------: | :--------: | :-----------: | :-----------: | :-------: | :---------: |\n| **RI (↑)** | 0.99948  |   0.99687    |  0.99999   |  0.99999   |    0.99999    |    0.99998    |  0.99999  |   0.99999   |\n\n**Q2. Inconsistent Terminology: Terms like \"automorphic equivalence\" and \"automorphism equivalence\" are used interchangeably, risking confusion.**\n\n>R2: Thank you for highlighting the inconsistency in terminology. In the revised manuscript, we will standardize the terminology by uniformly using \"automorphic equivalence\" throughout the paper to ensure clarity and consistency.\n\n**Q3. The choice of intersection for fusing equivalences is not justified against alternatives (e.g., union). Ablation studies comparing fusion methods are missing.**\n\n>R3: Thank you for the insightful suggestion. We have added a table below that presents performance results on our datasets using the union method as an alternative for fusing equivalences. Our experiments indicate that the union approach performs markedly worse compared to the intersection method. This is largely because, as detailed in the ablation study in the appendix, emphasizing one equivalence type (either automorphic equivalence or node attributes) by using the union tends to neglect the contributions from the other. In contrast, the intersection method ensures that both types of equivalences jointly contribute, leading to a more robust and comprehensive representation of node similarity. These findings justify our choice of the intersection method for fusing equivalences.\n\n*Table II. Ablation study results on 8 datasets. Origin represents the full model, while union represent the ablated models.*\n\n| Model  |     Cora     |   Citeseer   |    Pubmed    |    Wikics    |  Computers   |    Photo     |      CS      |    Physics    |\n| :----: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :-----------: |\n| origin | 85.36 ± 0.15 | 74.58 ± 0.18 | 85.06 ± 0.27 | 82.15 ± 0.22 | 90.60 ± 0.19 | 94.51 ± 0.34 | 93.46 ± 0.28 | 95.91 ± 0.38  |\n| union  | 77.21 ± 0.22 | 64.37 ± 0.12 | 83.22 ± 0.19 | 80.96 ± 0.34 | 87.86 ± 0.25 | 93.59 ± 0.28 | 91.55 ± 0.15 | 94.93  ± 0.36 |\n\n**Q4. The overview figure (Figure 2) lacks a clear explanation of how the encoder interacts with equivalence constraints.**\n\n>R4: Thank you for your valuable comment. In our approach, the encoder is designed to output a representation for each node in the graph. We then apply equivalence constraints to these representations to ensure that nodes which are equivalent (according to our defined criteria) are embedded in a consistent manner. This process helps the model to better capture both structural and attribute similarities. We will update the caption of Figure 2 in the revised manuscript to include a clear explanation of how the encoder interacts with the equivalence constraints.", "claims_and_evidence": "Yes, I believe that the majority of the claims are well-supported by evidence.", "methods_and_evaluation_criteria": "Yes, the proposed methods are well-suited to the problem.", "theoretical_claims": "Yes, I have checked the correctness of the proofs for the theoretical claims.", "experimental_designs_or_analyses": "I have reviewed most of the experimental design and analysis, which appear comprehensive and reasonable. For the equivalence class matching evaluation, I recommend adding other classic metrics, such as the Rand Index.", "relation_to_broader_scientific_literature": "The paper bridges graph theory, contrastive learning, and self-supervised paradiam design, offering a fresh perspective on equivalence-driven representation learning.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "Strengths\n\n1. Originality:  \n   - The unification of automorphic equivalence and attribute equivalence into a single framework is novel and addresses a gap in graph representation learning.  \n   - The critique of graph contrastive learning as a \"degenerate\" equivalence constraint offers a fresh perspective.  \n\n2. Significance:  \n   - The work bridges graph theory and modern deep learning, providing a principled approach to self-supervised learning that aligns with real-world graph properties (e.g., social roles, molecular symmetries).  \n   - Experiments demonstrate consistent performance gains.  \n\n3. Clarity of Writing:  \n   - The paper is generally well-structured, with clear definitions of equivalence relations and a logical flow from motivation to experiments.  \n   - Figures and tables enhance readability.  \n\nWeaknesses  \n\n1. Writing and Presentation:  \n   - Inconsistent Terminology: Terms like \"automorphic equivalence\" and \"automorphism equivalence\" are used interchangeably, risking confusion. \n\n2. Ablation:  \n   - The choice of intersection for fusing equivalences is not justified against alternatives (e.g., union). Ablation studies comparing fusion methods are missing.\n\n3. Minor Issues:   \n   - The overview figure (Figure 2) lacks a clear explanation of how the encoder interacts with equivalence constraints.", "other_comments_or_suggestions": "Terms like \"automorphic equivalence\" and \"automorphism equivalence\" are used interchangeably, risking confusion.", "questions_for_authors": "See in Other Strengths And Weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kiQz1LXK71", "reviewer": "Reviewer_Smmv", "summary": "This paper proposes a novel self-supervised graph learning framework grounded in the principle of node equivalence, which unifies structural (automorphic) and attribute-based equivalence classes to learn robust node representations. The work is well-motivated, offering a principled unification of structural and attribute-based node relationships, backed by theoretical insights, scalable approximations, and comprehensive empirical validation.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1. The paper makes valuable contributions but omits some reference, such as [1] formalizes equivalence (e.g., group-equivariant networks) in convolution neural networks. Citing these would strengthen the paper’s positioning. Refs: [1] Kondor, R., & Trivedi, S. On the generalization of equivariance and convolution in neural networks to the action of compact groups. ICML 2018.**\n\n>R1: Thank you for the valuable suggestion. We will include this reference in the revised manuscript to strengthen our positioning.\n\n**Q2. The impact of hyperparameter choices (e.g., PageRank teleportation parameter) on model performance is not sufficiently discussed. A sensitivity analysis of these parameters would strengthen the empirical section.**\n\n>R2: Thank you for your insightful comment. As requested, we have performed a sensitivity analysis on the Cora dataset with respect to the PageRank teleportation parameter ($\\alpha$). We varied $\\alpha$ from 0.1 to 0.9 and recorded the performance of our model. The results are shown in the table below:\n\n*Table I: Sensitivity analysis of PageRank teleportation parameter (α) on the Cora dataset*\n\n| $\\alpha$ |     0.1      |     0.2      |     0.3      |     0.4      |     0.5      |     0.6      |     0.7      |     0.8      |     0.9      |\n| :------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |\n|   Cora   | 85.33 ± 0.19 | 85.35 ± 0.15 | 85.27 ± 0.20 | 85.38 ± 0.12 | 85.23 ± 0.19 | 85.36 ± 0.17 | 85.30 ± 0.09 | 85.35 ± 0.15 | 85.29 ± 0.24 |\n\n>From the table, it is evident that our algorithm’s performance is not sensitive to the choice of $\\alpha$; the accuracy remains almost consistent across all values. We will include these details in the updated empirical section of the manuscript.\n\n**Q3. Incomplete figure and table explanations. For example, the cycle notation in Figure 1 is not explained in the caption, making it difficult for non-expert readers to understand. In the tables, the highlighted colors (e.g., shades of green) lack a legend, leaving their meaning unclear.**\n\n>R3: Thank you for your suggestion. We will revise the caption for Figure 1 to provide a clearer explanation. The updated caption is as follows:\n\n>_Figure 1. An example of an automorphic equivalence. The hollow double arrows indicate the permutation of nodes in graph $\\mathcal{G}$. The permutation is expressed in cycle notation (e.g., (1 2 3) indicates that node 1 maps to node 2, node 2 to node 3, and node 3 back to node 1)._\n\n>In addition, the highlighted colors use lighter shades to represent smaller numbers. A detailed explanation will be provided in the revised manuscript.\n\n**Q4. The main text inconsistently uses \"automorphism equivalence\" and \"automorphic equivalence\" (e.g., in the third paragraph of the introduction). It is recommended to standardize the terminology throughout the paper. Additionally, citing classic references such as [1].**\n\n>R4: Thank you for your valuable suggestion. We will standardize the terminology throughout the paper by consistently using \"automorphic equivalence.\" Additionally, we will include reference [1] in the revised manuscript.\n\n**Q5. The magnitude difference between Intra-class Loss and Inter-class Loss may cause optimization bias (e.g., Intra-class Loss dominates). Would it be better to introduce a temperature coefficient or weight adjustment to balance them?**\n\n>R5: Thank you for the insightful comment. Rather than introducing additional hyperparameters like a temperature coefficient or weight adjustments, we address the imbalance by applying a Softplus activation after the discriminator. This approach is also described in the Implementation Details section of the manuscript. Once again, thank you for your thoughtful feedback.", "claims_and_evidence": "The claims are well-motivated and largely supported by theoretical and empirical evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate and well-aligned with the paper’s goals. The core innovations, unified equivalence classes, scalable approximations, are tested on standard benchmarks.", "theoretical_claims": "I reviewed the theoretical claims, including proofs in the main paper.", "experimental_designs_or_analyses": "The experimental designs and results are largely sound.", "relation_to_broader_scientific_literature": "The paper sits at the intersection of graph theory and SSL, advancing these areas by providing a unified equivalence framework that subsumes existing SSL methods; introducing scalable approximations to bridge classical graph isomorphism concepts with modern deep learning; and offering actionable insights to improve GNNs and transformers via symmetry preservation.\n\nThis work aligns with the broader trend toward principled graph SSL (e.g., invariance theories in GCL) but stands out by rigorously formalizing equivalence as a first-class citizen in representation learning.", "essential_references_not_discussed": "The paper makes valuable contributions but omits some reference, such as [1] formalizes equivalence (e.g., group-equivariant networks) in convolution neural networks. Citing these would strengthen the paper’s positioning.\nRefs:\n[1] Kondor, R., & Trivedi, S. On the generalization of equivariance and convolution in neural networks to the action of compact groups. ICML 2018.", "other_strengths_and_weaknesses": "Strength:\n\nS1: The paper is well-written and easy to understand. I appreciate the ambition behind unifying structural and attribute equivalence. It bridges graph-theoretic principles with modern representation learning, offering a fresh lens to rethink graph SSL.  \n\nS2: The method’s design is well-founded—approximating automorphic equivalence via PageRank and relaxing attribute constraints strike a pragmatic balance between rigor and scalability.\n\nS3: The experiment is well-conducted and validates its performance.\n\nWeakness:\nW1: The impact of hyperparameter choices (e.g., PageRank teleportation parameter) on model performance is not sufficiently discussed. A sensitivity analysis of these parameters would strengthen the empirical section.\n\nW2: Incomplete figure and table explanations. For example, the cycle notation in Figure 1 is not explained in the caption, making it difficult for non-expert readers to understand. In the tables, the highlighted colors (e.g., shades of green) lack a legend, leaving their meaning unclear.", "other_comments_or_suggestions": "The main text inconsistently uses \"automorphism equivalence\" and \"automorphic equivalence\" (e.g., in the third paragraph of the introduction). It is recommended to standardize the terminology throughout the paper.\nAdditionally, citing classic references such as [1].", "questions_for_authors": "1. The magnitude difference between Intra-class Loss and Inter-class Loss may cause optimization bias (e.g., Intra-class Loss dominates). Would it be better to introduce a temperature coefficient or weight adjustment to balance them?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper advocates for self supervised graph learning methods to encourages similar representations for automorphic nodes. The reviewers were very positive on the novelty and overall contribution of the method, hence I recommend acceptance.
Decision: Accept (oral)