- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper utilized the extended concept of edge-level automorphism to improve both theoretical analyses (with WL-induced edge orbit) and algorithmic techniques (with D1: automorphism-aware dropout and D2: subgraph orbit-biased aggregation) in GNNs. Experiments showed the relatedness between the edge automorphism ratio and GNN performence, and validated the effectiveness of D1 and D2.
Critical strengths
- Technical soundness. The theoretical concepts are well rooted and rigorously developed. For example, on how node-level autoporphism is adapted to edge-level automorphism. Besides, the techniques are effective with improvements on main-stream GNN baselines and datasets.
- Presentation Clarity. The clarity can further improved if the calculation process of WL-induced edge orbit are showcased by specific examples. For example, it can be explained in detail how the left picture in Figure 3 is plotted using the definition. Besides, the concept of WL test should be explained considering readers not familiar in this field.
Critical weaknesses
- No broader significance. This paper is more suited to domain-specific conference such as LoG (Learning on Graph Conference) with its current demonstration.
- No deeper insight. The developed contributions are solid but well expected and too normal for the top AI conference of ICLR.
Questions for authors
- On broader significance. Why is edge-level automorphism significant ? The significance does not naturally comes from its mathematical analogy to node-level automorphism. Instead, it should be thoroughly investigated on what specific real-world network types exhibit these properties and sharply analyzed on how it relates to the link prediction problem.
- On deeper insight. Is edge-level automorphism complementary to node-level automorphism ? If so, this conclusion should not stay at the shallow surface of definition similarity. Instead, it can be theoretically analyzed on how the combination of edge-level automorphism and node-level automorphism contributes to some complete expressiveness. Besides, the exclusivity between these two automorphisms may also inspire deeper theretical conclusions.
I will consider raising my score only when the above points are addressed satisfactorily.
We thank the reviewer for the constructive feedback and for acknowledging the soundness of our theory. We address each point below.
Significance of edge-level: The fundamental importance of edge-level automorphism lies in its ability to detect failures that node-level analysis cannot detect. For instance, all nodes of the triangular prism are equivalent from the node perspective; however, from the edge perspective, the triangle edges and the rung edges are structurally entirely different. Any analysis derived from the node level cannot preserve edge-level problems. From the task perspective, there is likewise no proven strong correlation between node classification and link prediction. We consider this to be the core reason why edge-level research requires an independent theoretical framework and measure to move forward.
Relationship with node-level: We believe node- and edge-level automorphisms are complementary and logically independent, i.e., neither level of symmetry can be derived from the other. We use two simple counterexamples to show this.
The first is the triangular prism discussed above. So all vertices being structurally identical at the node level does not imply that everything is the same at the edge level.
The second example goes in the opposite direction. In the complete bipartite graph K2,3, all edges are equivalent (the graph is edge-transitive), but the nodes on the two sides are not, as they do not even have the same degree. Here, the edges are indistinguishable while the nodes are not.
Taken together, we argue that vertex-transitivity and edge-transitivity are independent properties. We believe this further supports the need to study edge-level tasks in their own right.
We thank the reviewer for raising this important question again.