Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides theoretical bounds on the stability properties of graph convolutional networks. It does so at multiple levels: input signal perturbations, edge perturbations, and structural perturbations. Input stability refers to the output of the network not changing much if we change the input signal. Similarly, we can consider the change in output if we change the edge weights (edge perturbation) as well as if we collapse nodes connected by strong edges (structural perturbation). Numerical analysis is provided to support some of the claims.
strength_and_weaknesses: ___Strengths____
    - I found the stability to structural perturbations very interesting and relevant for the community. 
    - The analysis is very self-contained and complete at multiple levels, from introducing all the necessary concepts, to analyzing a wide variety of perturbations one may face in practice.
    - Although I didn't check the proofs in detail, the arguments and statements of the bounds are solid.
___Weakness____
    - The paper could do better to first motivate the "Why" (why do we care about what we are going to be presented). 
    - Similarly, it is lacking a "So What" on the bounds provided, which are often just left there as final statements, without an analysis that explains whether 1) they are (likely to be) tight and 2) what this implies for practitioners.
    - Although well-written, the paper felt quite dense, even compared to other pure-math ML papers. More examples such as Figure 2 would help.
    - As far as I understood, the assumption on the non-linearities discards the sigmoid and the softmax, which are popular non-linearities. It would be good to acknowledge this directly by name.
clarity,_quality,_novelty_and_reproducibility: ___Clarity___
- The paper could reach the TLDR of their goal much faster. The first paragraph can be cut down substantially and then the particular contribution of this paper should be emphasized at most in the second paragraph. RIght now the Introduction feels too much like a (good) Related work section, bugging the reader with detailed literature that only people searching for related work would care about. Instead, I would use the introduction to make it very clear what the work is and why we care, closer to the very last paragraph. Furthermore, all these references could have profited from coming after "preliminaries and framework".
- In section 2 we need intuition on why we care about each new concept, and how things are going to be used. 
- Minor details
    - First paragraph page 2 "In ?? stability"
    - Typo "whic" in first paragraph section 3
- Labels in figure 3 are too small. Consider putting less numbers but larger.

__Quality___
    - Although I didn't check the proofs in detail, the analysis seems thorough and the goals non-trivial.
    - The numerical analysis was a bit shallow and the connection to the theoretical bounds could have been explained better.

___Novelty___ although I'm not an expert in theoretical analysis of GNNs this felt novel to me, particularly section 5.

___Reproducibility__ this is mostly math and proofs where in the appendix so it seems pretty reproducible.
summary_of_the_review: I believe the paper could have been clearer and motivated the problem better. Similarly, the empirical analysis could have been more thorough. However, I believe the problem is important and the theoretical contributions is (AFAIK) novel and note-worthy. Therefore, I recommend to accept the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work establishes rigorous, novel and widely applicable stability guarantees and transferability bounds for general graph convolutional networks – without reference to any underlying limit object or statistical distribution. Theoretical results are supported by corresponding numerical investigations.
strength_and_weaknesses: Strength: The paper has a solid theoretical analysis and numerical investigations, numeric results are used to validate the claim.
Weaknesses: Although the theoretical evidence is strong, practical experiments on real applications are missed. How to validate the practicability of the proposed theory？
clarity,_quality,_novelty_and_reproducibility: The theory of this paper is rigorous and the proofs are also sufficient.
summary_of_the_review: Except for the lack of practical experimental verification, this is a good theory paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides a holistic theoretical framework to evaluate stability and transferability of graph convolutional networks (GCN). As expected, the various theoretical results provide bounds on the changes in GCN outputs in terms of perturbations to the input signal or the structure. A novel perspective on the transferability of GCNs is presented, where transferability is established between GCNs operating on graphs under the assumption that one graph is a collapsed version of the other. Limited numerical results that validate the proposed theory are also provided. 
strength_and_weaknesses: Strengths:

1. The presented theory is generalizable to generic utilized filters, graph shift operators as well as non-linearities.
2. The paper provides a fresh perspective to the transferability of GCNs for graphs with strongly connected edges.

Weaknesses:
1. While the study of stability and transferability of GCNs is a well motivated research problem, the paper does not provide significantly novel insights into the stability of GCNs. Transferability results are interesting, however, the paper lacks a convincing argument on widespread applicability of these results beyond a narrowly defined category of graphs. 
2. Experiments consider fully connected, small graphs (size = 8) and therefore, provide limited insight.
3. Paper clarity can be improved (elaborated in the Clarity, Quality, Novelty And Reproducibility section). 

clarity,_quality,_novelty_and_reproducibility: As mentioned above, the study of stability and transferability of GCNs is well-motivated. The paper provides novel insights into the transferability of GCNs for graphs with strong edges. However, I am not convinced that these results are sufficiently significant. I encourage authors to comment on the motivation behind studying this category of graphs.

I do not agree with the author's assessment that existing works that leverage the theory of graph limits are not applicable for non-asymptomatic settings as such insights can be drawn using triangle inequality. For instance, if a GCN defined on a graph with $n_1$ nodes approaches in some limit to a GCN defined on a limit object, the conditions on transferability between GCNs on $n_1$ and $n_2$ nodes in the non-asymptotic setting can be recovered via triangle inequality.  If the graphs with strong edges lie outside of the scope of theory of such limit objects, it will provide a much more convincing argument for the significance of the transferability results in this paper. 


Clarity:

I have the following remarks, addressing which will help improve the clarity of the paper.

a. Please provide the definition of a normal operator. 

b. Is $a_{\mu\nu}$ in Defintion 2.1 a scalar?  

c. The difference term $JT - {\tilde T} J$ is not properly motivated. Please explain what this difference represents.


summary_of_the_review: This paper provides some interesting and novel ideas on transferability. However, a major revision is needed to expand on the motivation, significance, and applicability of these results. More comprehensive experimental evaluations will also improve the paper considerably. 


**After Author Rebuttal**
I thank the authors for their detailed response and a significant overhaul of the paper, which help address my concerns to some extent and help improve the paper significantly. The authors have also significantly extended the supplementary material with technical and empirical content, however, I did not go through this carefully.  The contributions of the paper in the domain of stability are now better elucidated. The authors provide additional experiments for larger graphs. Furthermore, the authors added an example to the section on transferability that relates their theory to the existing theory of transferability that relies on limit objects. After considering these aspects, I have raised my score to 6.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This submission provides new stability guarantees and transferability bounds for general graph convolutional networks. The analysis framework can be applied to both directed and undirected graphs based on recent advanced tools. Specifically, node-level and edge-level perturbations with some new properties are presented and discussed. These theoretical results are supported by numerical results.
strength_and_weaknesses: Strengths:

1. The submission provides new theoretical stability aspects of graph convolutional neural networks. The stability analysis is quite general and hence can potentially be applied to other problem settings of graph learning problems.

2. The theoretical results are verified numerically.

3. In terms of theoretical novelty, this submission develops a general theory of stability for GCNs.

Weakness:
1. It would be nice to list notations so that these theoretical results are more accessible to a general audience.
clarity,_quality,_novelty_and_reproducibility: The paper presents new theoretical results of the stability of GCNs. Overall, the technical novelty is very solid.
summary_of_the_review: This submission provides new stability guarantees and transferability bounds for general graph convolutional networks. The analysis framework can be applied to both directed and undirected graphs based on recent advanced tools. Specifically, node-level and edge-level perturbations with some new properties are presented and discussed. These theoretical results are supported by numerical results.

Overall, the authors present new theoretical results on the stability of GCNs models using some new tools. I didn't check the correctness of these proofs line by line. However, these theorems are quite solid works.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper studies the problem of stability of Graph Convolutional Networks. In a Euclidean setting, stability refers to exploring the sensitivity of the output of an algorithm to small (trivial) changes in the input. In the graph setting, this sensitivity has to be investigated with respect to both perturbation of the node feature and the adjacency matrix (the latter is sometimes known as “transferability”). Existing analyses are limited (a) in the type of filters that they use and (b) in that they hold asymptotically and not in the finite sample regime. This paper aims to fill that go, and provide a series of results on the stability of GCN to signal, edge and adjacency matrix perturbations. More specifically, the authors use the comparison of GCN to graph filters to derive bounds that do not require the filters to be normal.

The feedback for this paper was good. Overall, the reviewers all agreed on the relevance of the paper, and on the significance of the contributions: the results are nice and generalize some existing analyses. Most of the initial concerns of the reviewers focused on the clarity of the paper --- more specifically, the density of the paper and the presentation of the results. In the initial presentation, the introduction was deemed too dense, and the bounds not appropriately commented upon. The authors were prompt to take this feedback into account and modified their exposition to shorten the introduction, increase the experimental result part and comment on their bounds. The rebuttal seems to have been successful in improving the clarity of the exposition.

justification_for_why_not_higher_score: This paper is a (noteworthy)  generalization of existing stability analyses of GCNs --- the analysis however might not necessarily be novel enough to warrant a spotlight. 
justification_for_why_not_lower_score: The paper brings substantial contributions to the analysis of the stability of GCNs. The results are novel enough to warrant publication.
Decision: Accept: poster