Scale Invariance of Graph Neural Network for Node Classification

Thank you for your feedback.

(1) Not a linear model In Theorems 4.1, we explicitly mentioned "layer-wise propagation." As noted in our rebuttal, a GNN layer can include propagation, normalization, and non-linearity. For simplicity, we focused on the linear components in the subsequent discussions.

We appreciate your feedback on Claim 3 regarding the universal approximation theorem (UAT). To clarify, our model does include non-linear activation functions. In our UAT proof, we stated: ``For a 2-layer GCN, omitting the non-linear activation for simplicity, the propagation outputs are..." This omission was for ease of expression in the derivation, not to suggest a lack of non-linearity. We will revise the text to explicitly state "for simplicity of expression" to avoid any misunderstanding.

(2) UAT

Thanks to the UAT, if we remove the inner non-linearities and retain only the final activation, the revised model is equivalent in approximation power to the original one. should be:

$\sigma \left( A \left( \sigma \left( AXW_1 \right) W_2 \right) \right) \approx \sigma \left( AAXW_1W_2 \right)$ (a)

As we stated "omitting the non-linear activation for simplicity", it correctly becomes:

$A(AXW_1)W_2 \approx AAXW_1W_2$ (b)

*If you don't agree with equation(a), here is the explanation:

This step follows directly from standard function approximation principles under UAT, which states that a sufficiently expressive neural network can approximate any continuous function. The simplification of nested activations into a single activation over a transformed input is a well-established result in the literature [1–3].

A similar application of UAT in Graph Neural Networks (GNNs) has been explored in prior work [4], further supporting our approach. Additionally, empirical studies have confirmed the effectiveness of removing nested non-linearities in GNN architectures [5].

References [1] Hanin, B., & Sellke, M. (2017). Approximating continuous functions by ReLU nets of minimal width. arXiv preprint arXiv:1710.11278. [2] Lu, Z., Pu, H., Wang, F., Hu, Z., & Wang, L. (2017). The expressive power of neural networks: A view from the width. NeurIPS. [3] Hornik, K., Stinchcombe, M., & White, H. (1989). Multilayer feedforward networks are universal approximators. Neural Networks, 2(5), 359–366. [4] Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2019). How Powerful are Graph Neural Networks? ICLR. [5] Wu, F., Souza, A., Zhang, T., Fifty, C., Yu, T., & Weinberger, K. Q. (2019). Simplifying Graph Convolutional Networks. ICML.

*If you agree with Equation (a) but not Equation (b), we acknowledge that our expression may have been overly simplified, which might have made the transition appear abrupt. We apologize for this and will revise the text to improve clarity and ensure a smoother logical flow.

(3) Notation misunderstanding

In our rebuttal, we explicitly stated:

``$X_I$ consists of all nodes that can be reached from $X$ within 1 step of scaled-edge $I$ (in-edge)."

Thus, $\sum X_I$ represents the sum of features of all 1-step in-neighbors of $X$. Your suggestion of using $AX$ corresponds to all 1-step out-neighbors of $X$, which should instead be denoted as $\sum X_O$.

Additionally, we defined the adjacency matrix as:

``An adjacency matrix $A \in \{0,1\}^{n \times n}$, where $A_{ij} = 1$ indicates the presence of a directed edge from node $i$ to node $j$." This definition is clearer than explicitly defining separate adjacency matrices for in- and out-edges, which might be like:

``$A_{ij} = 1$ means an out-edge for node $i$ and an in-edge for node $j$."

(4) Baseline and large graph

The Citeseer dataset in our Table 4 is a directed graph. The 70% accuracy you mentioned refers to the undirected version, where even MLP achieves 71% and GCN reaches 74%. The directed Citeseer graph consists of 3312 nodes, while the undirected version has 3327 nodes. They differ in several aspects, including node count, edges and their train/validation/test splits, which results in a variation in performance. You can verify this using our code: use "citeseer/" for the directed graph and "CiteSeer" for the undirected one.

About scalability, please refer our rebuttal to Reviewer YrK7(first point).

(5) Related work Thank you for bringing up "Universal Invariant and Equivariant Graph Neural Networks." As discussed in Related Work in Appendix A, our review of existing research on graph invariance has primarily focused on permutation invariance, and your reference aligns with this discussion. However, we appreciate your suggestion and will be happy to include your reference in this category.

Finally, thank you very much for taking the time to read our paper and rebuttal. This is a complex work, and condensing multiple ideas into a limited space is inherently challenging, so we understand that misunderstandings can arise. We truly appreciate your time and consideration.

Best Regards, Authors

Dear Reviewer YrK7,

We would like to thank you for your thoughtful feedback. Below, we address the raised concerns in detail:

1. Datasets: The 12 datasets used in our experiments are listed in Table 2. These datasets primarily illustrate the unnecessary computation in Random Walk methods, such as the popular DiG(ib) model, include digraph and undirected graph. The main results for directed graphs are presented in Table 4, which highlights our contribution of SOTA performance.

2. Scale Invariance Definition: We have provided a formal and rigorous definition of Scale Invariance in Definition 3.7, followed by theoretical justification, empirical validation, and practical application of scale invariance of node classification in graph. We answered similar rebuttal to Reviewer 7DTZ, for your convinience, I'll paste part of it as follows:

   "(1) Preliminary

In Section 3.1, we begin by defining the scaled ego-graph, motivated by the fact that node classification is the classification of the center node’s ego-graph.

(2) Definition of Scale Invariance in Graphs

In Section 3.2, we begin by extending the concept of scale invariance from image classification to node classification in graphs, and conclude the section by formally presenting Definition 3.7:

For a node classification task on a graph , we say the task exhibits scale invariance if the classification of a node remains invariant across different scales of its ego-graphs.

This definition captures precisely what we mean by scale invariance in the graph context and we also gave its mathematical expression in math.

(3) Theoretical Justification of Scale Invariance( For Node classification in GNN)

In Section 4, we provide a theoretical proof that certain GNNs can exhibit scale invariance in node classification tasks. We further support this with an empirical demonstration referenced at the end of the section, directing readers to Appendix C.5.

(4) Empirical Evidence of Scale Invariance

In Appendix C.5, we present Table A4, which empirically demonstrates that the classification performance remains stable when using individual scaled ego-graphs. This shows that meaningful class-relevant information can be extracted from ego-graphs at different scales.

(5) Combine multiple Scale to achieve better performance: ScaleNet

Finally, in Section 5, we propose ScaleNet, which combines multiple scaled ego-graphs to improve performance. As shown in Table 4, this approach achieves state-of-the-art (SOTA) results on several benchmark datasets."

3. Undirected Graphs: As noted at the end of Section 4, undirected graphs can be treated as a special case of directed graphs. This paper focuses primarily on directed graphs (digraphs), and the results and analyses are framed within that context. We appreciate the opportunity to clarify this point for the reader.

4. Runtime and Complexity Analysis: Our paper primarily addresses scale invariance rather than scalability. For further clarification, we refer to our rebuttal to Reviewer YrK7 (first point), where we explain this in more detail.

In addition, we argue that our 1iG(ib) method outperforms the DiG(ib) model in terms of scalability. This improvement is due to the removal of the eigenvalue decomposition part of the algorithm, while the rest of the method remains unchanged. Therefore, a detailed runtime and complexity analysis is not necessary, as the simplification inherently leads to better scalability.

1. We sincerely apologize for the misunderstanding regarding the submission guidelines---we mistakenly included our appendix as supplementary material. While this was an oversight on our part, we believe it should not warrant rejection of our paper, as the appendix contains supporting material that directly substantiates key claims made in the main text.

2. Clarification on the Definition and Justification of Scale Invariance in Graphs:

The reviewer asked: "Can you formally show that CNNs are scale-invariant?" While this is an interesting question, we would like to emphasize that our paper does not aim to establish scale invariance in CNNs. A rigorous treatment of that topic would require substantial theoretical and empirical work—likely constituting a separate study within the domain of computer vision. In contrast, our work is focused entirely on graph neural networks, for which we do provide a complete and self-contained definition, theoretical analysis, and empirical validation of scale invariance. In addition, although it's possible to write a paper on scale invariance of CNN from pixel-wise operation, such as pooling, pyramid feature extract, we doubt anyone would actually do that as it is widely utilized in image classification. While no one ever tried to apply utilize scale invariance in GNN, thus our paper makes a fundamental contribution in GNN.

To summarize the structure of our self-contained argument:

(1) Preliminary

In Section 3.1, we begin by defining the scaled ego-graph, motivated by the fact that node classification is the classification of the center node’s ego-graph.

(2) Definition of Scale Invariance in Graphs

In Section 3.2, we begin by extending the concept of scale invariance from image classification to node classification in graphs, and conclude the section by formally presenting Definition 3.7:

For a node classification task on a graph $G$, we say the task exhibits scale invariance if the classification of a node $v$ remains invariant across different scales of its ego-graphs.

This definition captures precisely what we mean by scale invariance in the graph context and we also gave its mathematical expression in math.

(3) Theoretical Justification of Scale Invariance( For Node classification in GNN)

In Section 4, we provide a theoretical proof that certain GNNs can exhibit scale invariance in node classification tasks. We further support this with an empirical demonstration referenced at the end of the section, directing readers to Appendix C.5.

(4) Empirical Evidence of Scale Invariance

In Appendix C.5, we present Table A4, which empirically demonstrates that the classification performance remains stable when using individual scaled ego-graphs. This shows that meaningful class-relevant information can be extracted from ego-graphs at different scales.

(5) Combine multiple Scale to achieve better performance: ScaleNet

Finally, in Section 5, we propose ScaleNet, which combines multiple scaled ego-graphs to improve performance. As shown in Table 4, this approach achieves state-of-the-art (SOTA) results on several benchmark datasets.

In conclusion, our paper presents a rigorous and comprehensive study of scale invariance in graph neural networks, including a formal definition, theoretical analysis, empirical validation, and practical application.

While there is no existing formal definition of scale invariance in CNNs, the concept is widely invoked in image classification as a desirable property, often operationalized through techniques like zoom-based data augmentation and pooling. Extending this concept to GNNs is both natural and well-supported. A request for a formal CNN-specific definition reflects the reviewer's individual interest—one we are willing to address in a camera-ready version—but it is not a valid reason for rejection, especially given our clear focus on graphs and the completeness of our treatment.

Among the three main categories of models for directed graphs, our approach demystifies the core mechanisms of two, removes redundancy, and improves the third through scale invariance—offering a streamlined, theoretically grounded alternative with superior performance.

While we are disappointed that the reviewer did not fully appreciate the structure and scope of our contributions, we recognize that the breadth of our work may have contributed to this. We respectfully ask that the reviewer reconsider the paper based on the provided outline. Accepting our work could help the community avoid unnecessary complexity and adopt a more principled, scale-aware view of GNNs.

Thank you for your comment and for carefully reading the "Supplementary Material," which we initially thought was the correct place to include the appendix.

We now understand that supplementary material is considered separate from the main submission and that key sections—such as Related Work—should appear within the main paper or as an appendix included in the same PDF. Due to space constraints, we were unable to include a Related Work section in the main text, but we provided a detailed discussion in what we intended as an appendix. If permitted, we will include this appendix within the main submission file in the camera-ready version to ensure it is properly considered part of the paper. We appreciate your feedback and the opportunity to clarify this misunderstanding.