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

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.

R1: Thank you for the valuable suggestion. We will include this reference in the revised manuscript to strengthen our positioning.

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.

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:

Table I: Sensitivity analysis of PageRank teleportation parameter (α) on the Cora dataset

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.

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.

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:

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).

In addition, the highlighted colors use lighter shades to represent smaller numbers. A detailed explanation will be provided in the revised manuscript.

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].

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.

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?

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.

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.

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.

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).

Q2. Inconsistent Terminology: Terms like "automorphic equivalence" and "automorphism equivalence" are used interchangeably, risking confusion.

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.

Q3. The choice of intersection for fusing equivalences is not justified against alternatives (e.g., union). Ablation studies comparing fusion methods are missing.

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.

Table II. Ablation study results on 8 datasets. Origin represents the full model, while union represent the ablated models.

Q4. The overview figure (Figure 2) lacks a clear explanation of how the encoder interacts with equivalence constraints.

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.

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.

R1: Thank you for the helpful suggestion. We will include this reference "Community detection in graphs" in the revised version.

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.

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.

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.

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.

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."

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.

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?

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.

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.

R2: We appreciate the reviewer's suggestion. We will update the caption of Table 2 to the following:

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.

Q3. The paper would benefit from a discussion on the potential limitations of the model.

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.

Q4. Some typos: - Line 75: Change "noting" to "note". - Line 252: Change "indicates" to "indicating". - Line 308 (right column): Change "a" to "an".

R4: We thank the reviewer for pointing out these typographical errors. We will correct these typos in the revised version of the paper.

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.

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.