Zero-One Laws of Graph Neural Networks

Summary

The authors analyze standard GNN binary classifiers on Erdos-Renyi graphs, and conclude that the output satisfies a zero-one law. To be more precise, this means that an Erdos-Renyi graph with the number of nodes tending to infinity and random node features will be classified as 1 with probability tending towards either 0 or 1. Of course, this comes with some assumptions, which the authors claim are mild and reasonable to assume. The authors also provide empirical data that suggests n does not need to be incredibly large (on the order of 1,000 or 10,000) for this effect to take hold.

Strengths

The strengths of this paper lie in the novelty of the authors' result. The result is interesting and significant to the field of investigating the theoretical upper and lower bound of expressivity in GNNs, which will inspire other readers to expand upon the investigation, particularly in zero-one laws. Experiments done are also convincing in supporting the practicality of their argument and to give readers a visual indication of the authors' result.

Weaknesses

The paper's main weakness lies in their dismissal of assumptions. Although the result is interesting, its overall current practicality may be somewhat overstated. For example, in line 173 authors claim sub-Gaussian random vectors "encompass all practical setups." This may be quite a bold statement, as many real-world examples are known to follow common distributions such as the exponential or Pareto distributions, and are fitting for further investigation. In addition, the same can be said about the ER random graph model; it is useful as an analytical tool, but fits to real graph topologies rather poorly. Perhaps more theoretical work or empirical investigation can be done on both fronts. (I acknowledge that there are empirical results on the Barabási-Albert model, which is helpful.) If treated as a purely theoretical result/paper though, these addressed weaknesses may be taken lightly. Also, would it be possible to add confidence bounds for the graphs in this case?

Questions

1. Do the proofs extend easily to different random graph structures and/or wider families of distributions? 2. Why was it not possible to run the Figure 1 plot for larger graphs? SUMGNN T=3 seems like it may converge, but it would be nice to see it visually.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

Limitations address key points, although could be elaborated upon more. The current version may be toning down the limitations as addressed above in the weakness section. No potential negative societal impact.

Summary

This paper is primarily a theory paper - proposing a proof that, as the number of nodes in a graph drawn from the ER graph distribution increases, a class of GNNs binary classifiers converges to either 1 or 0. This observation is backed up with a small set of empirical experiments of GCNs and variants, but no additional experiments on more advanced GNNs.

Strengths

I thought the paper was well written, and the mathematics was clearly presented. The observations in the text were illuminating and intution was added at appropriate points. I felt that the exposition was not overly confusing, as can be the case with a number of theory papers, and the results put in context. Overall, I really enjoyed reading this, which is a rarity for theory heavy papers.

Weaknesses

I don't think it can be argued that it is a weakness that the paper's experimental results are for a class of models that isn't very commonly used any more - GCNs as they are presented in this work have been superseded by any number of architectural innovations. There are not, for example, experiments or proofs on the impact of residual layers or skip connections, or GNNs with edge MLPs. As such, I think while it's a very nice result, the impact of the paper is likely to be low. It wasn't clear to me - and I think this is because the math would be impossible to do for every architecture - how this result depends upon the scale seen in a number of graph neural networks, or how it changes if you add an attention mechanism. It could be that, in practice, this effect is only relevant if you have a very underpowered network, or you have a very very large graph. Both of which are not hugely practical examples.

Questions

How would an attention aggregation change the analysis? For me, that would hugely improve the impact of the paper because you're heading towards transformers at that point and so a far wider audience.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Limitations have been expressed above.

Summary

This paper introduces the zero-one laws pertaining to graph neural networks. More specifically, the authors utilize concentration analysis on Erdos-Renyi graphs to demonstrate that the likelihood of GNN classifiers producing either zero or one as output approaches 1. These findings are further expanded to encompass three different methods of aggregation and normalization in GNNs. Additionally, the authors present uniform approximation results for graph invariants that adhere to the zero-one law.

Strengths

+ The primary assertion is intriguing and offers a fresh perspective for evaluating the expressive capabilities of graphs. + This paper presents valid theoretical contributions, establishing the first asymptotic analysis of GNN behavior as the number of nodes approaches infinity. This analysis yields negative outcomes regarding GNN expressiveness, which may prompt reconsideration of new GNN architecture designs. + Despite its theoretical soundness, the paper also conducts well-designed experiments to substantiate its claims.

Weaknesses

- Certain theoretical definitions and arguments lack intuitive explanations, making it challenging to justify the assumptions. (See Questions) - To the best of my knowledge, global readout typically occurs only in the last layer. However, it appears that both MeanGNN and SumGNN incorporate it in each layer. Although this may not necessarily complicate the analysis, it may deviate from practical usage. - Are the arguments limited to ER graphs and sub-gaussian features? Does the concentration primarily stem from the assumptions regarding ER graphs and sub-gaussian features, rather than establishing a unique zero-one law specific to GNNs? (See Questions)

Questions

1. I still lack access to the specific paper mentioned, so I can offer only general suggestions for rephrasing the paragraph based on the information provided: I find it challenging to fully comprehend the correct interpretation of Definition 4.9, "synchronously saturating." In addition to presenting reasonable concentration results in the proof, it would be beneficial if the authors could provide a more straightforward explanation. Furthermore, I would appreciate further justification for the claim made: (Ln 242-243) In fact, assuming that µ, σ−∞ and σ∞ are non-zero, the the set of weights which yield a non-synchronously-saturating model has measure zero? 2. If I understand correctly, Section 5 primarily argues that the zero-one law is not always disadvantageous, as it enables uniform approximation. However, I'm curious why approximating a function with a fixed output (either 0 or 1) is considered desirable? 3. The paper uncovers an intriguing zero-one law emerging in GNNs. However, I would like to inquire whether the ER graph and sub-gaussian feature assumptions are the primary factors contributing to this phenomenon. It seems that the concentration is not a result of any specific components within GNNs, but rather an outcome of the assumed input. 4. Could the authors shed light on how the asymptotics correspond to the number of layers? Do additional layers lead to faster or slower concentration?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

The paper addresses certain limitations, and in addition to those already discussed, I recommend that the authors include a discussion on the strict assumptions made. Examining the impact of removing either the ER graph assumption or the sub-gaussian condition could potentially yield more substantial results.

Summary

This paper proves that for Erdos-Renyi random graphs, the hidden representations of nodes for GNNs, as well as the graph-level representation, will converge to a constant. In Theorem 4.6, which is the main result for GCN and binary graph classification, they prove that the binary output is always zero or one (the zero-one law). This means that the classifier will eventually become trivial. Its proof is based on Lemma 4.7, which shows the concentration of hidden representations on nodes. They then extend their theory in Theorem 4.10 to SumGNNs and show (in Theorem 5.2) that indeed zero-one laws imply uniform approximation by SumGNNs, which can be thought of as a converse to their zero-one law results. The paper is concluded with supporting experiments.

Strengths

- nice theoretical results - citing previous works

Weaknesses

- the results are restricted to ER graphs, which are not what we have in practice. Also, their model is restricted to dense graphs. - the paper is generally well-written, but some parts are long and could be more concise (like the meaning of the zero-one law and its motivation); they could've used the space better

Questions

I believe this is an interesting result. But unfortunately, it is far from practical models for GNNs. Here I list my comments: Major comments: (0) One major problem regarding the writing of the paper is that many paragraphs try to deliver the simple concept of the zero-one law for GNNs and its importance/motivation, which was too long for me. The paper is not concise. (1) In the paper, it is mentioned that this is a well-known result: "any graph invariant which can be expressed by a first-order formula satisfies a zero-one law" How does this relate to your result? Are you claiming that non-first-order formulas are satisfying the zero-one law? Otherwise, it falls in that category and it's not a new result. If not, an extensive explanation is required for how your proof is different and how those results are connected in each other. (2) line 209: "we expect.." This is indeed an important problem that is left unanswered. The rate of convergence shows when GNNs are not useful, so it may be exponentially slow in the number of nodes. (3) Many results in the paper are conditional on excluding an unknown zero-measure set of parameters. However, optimization algorithms (like SGD) trajectory is also a set of measure zero. The local minima of the objective may fall in those sets. (4) In Lemma 4.11, it is proved that the hidden representations of nodes, for any iteration, will converge to a fixed value. This is highly restricted by the assumption that the non-linearity saturates. As a result, it will not directly apply to ReLU networks. (5) The results are highly restricted. Random initial features are drawn based on the same distribution across different nodes. They cannot depend on the graph. The ER model is itself not realistic because we hope GNNs can extract hidden features from the graph data, while random ER graphs don't have any meaningful "feature." ER graphs are dense, while in practice, sparse graphs (like grids) also appear. Besides that, the paper proofs apply after using the concentration inequalities for a large number of nodes. It thus looks reasonable to expect those zero-one laws to happen. Minor comments: (0) line 67 - are the initial features and the random graph independently drawn? Or they can depend on each other? (it is later mentioned in Definition 4.2) Also, it is unclear whether the random initial features of different nodes are independent. (1) line 73 - can the functions $\psi$ and $\phi$ depend on the iteration index $t$? This is not clearly mentioned there. (2) line 263: typo: "every node $u$" -> "every node $v$"

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

N/A

Response

I acknowledge the response provided by the authors. However, I still disagree with the authors on the use of ER model (and other assumptions) for the theoretical analysis of GNNs. Unfortunately, I believe that the model, while being nice for theoretical analysis, is not appropriate for the study of GNNs. I decided to keep my score unchanged.

Thanks for rebuttal!

I appreciate authors' reply which addresses all my concerns. I value the topics and conclusions drawn in this paper and agree with authors that ER graphs are good examples to investigate, aligned with classic results. In the meanwhile, the discussion on this assumption has already been clarified in the limitation section (Sec. 7), which I do not think can be used to overturn this work itself. In summary, I'm lean toward acceptance.