Almost Surely Asymptotically Constant Graph Neural Networks

Summary

This paper theoretically analyze the phenomenon that GNN-based probabilistic classifiers almost surely converge to a constant. A formal approach based on term language is proposed. It provides a unified framework to study different GNN models.

Strengths

1. The paper is well-organized. 2. The theoretical study is solid. 3. The main finding is interesting.

Weaknesses

1. The use of ``term language'' is abstract and can be difficult to understand. It is preferable the authors can explain more and provide simple (numerical) examples, e.g, on an explicit small graph. 2. The paper discusses an interesting asymptotic behavior of GNNs as classifiers. However, its impact on GNN real applications is not fully discussed. 3. I do not find a thorough discussion if features are not i.i.d.

Questions

1. Can the authors give an explicit (rigorous) definition of "probabilistic classifier"? 2. In the discussion of almost sure convergence (3.1), what is $\bar{\mu}$? 3. From the definition of ``term language'' (Definition 4.1), it seems that it is a high-level summary of components in GNN architectures. I do not see what the essential properties are that lead to key results such as Theorem 5.1. Can authors elaborate on this? 4. For Theorem 5.1, is the almost sure limit a single (deterministic) vector? 5. I interpret the main findings of the paper as: large graphs (from one of the discussed models) are not distinguishable. Is this correct? Is there any way that the GNN architecture can be modified to overcome such a limitation? 6. Node features are assumed to be i.i.d. (3.1). In applications, this is usually not the case. How will non i.i.d. features affect the results?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

N.A.

Summary

The paper presents a theoretical study on the expressive power of some popular GNNs (MPNNs with the mean aggregator, GAT, and GPS+RW) as multi-class classifiers with random featured graphs. It shows that their output converges a.a.s. to a constant function from various random graph models, including Erdős-Rényi, stochastic block model, and Barabási-Albert model. The study includes empirical studies on synthetic and real graphs, confirming the theoretical findings.

Strengths

- The paper presents a formal language that is designed to describe compositions of operators and functions applied to graphs. This language captures the operations of GNNs in the architectures. This can be further applied to other theoretical work on GNNs related to their expressiveness and generalization capabilities. - The paper empirically validates the theoretical results of both synthetic and real graph datasets.

Weaknesses

- *Unclear Contribution to Expressiveness Analysis.* The expressiveness power is usually used to describe the GNN’s ability to approximate functions, which is essentially to derive generalization bounds or sample complexity. It is not clear how the type of results given in this paper can enable generalization performance analysis. - *Difference between [a] and the current paper.* [a] presents the output of MPNNs and GCNs as binary classifiers on the ER graph model that will converge to a constant as the graph size increases. This paper proposed that the output of some popular GNNs as multiclass classifiers on several graph models will converge to a constant function as the graph size increases. The current paper can be seen as an extension of [a]. It would be better to discuss the differences between them. Specifically, - What is the difference in the proof techniques between lemma 5.4 in this paper and lemma 4.7 in [a]? - If we set the number of classes as 2, then will the convergence results of this paper reduce to the results in [a]? [a] Adam-Day, S. and Ceylan, I., 2024. Zero-one laws of graph neural networks. Advances in Neural Information Processing Systems, 36. - The experimental results are supported by std (which is good) but without p-value analysis or confidence interval. The statistical significance is not entirely clear. - Some minors: - The authors assume that the node features are in domain [0, 1]^d, and it would be helpful to explain more about the reason for using this assumption in the proof, e.g., how critical is this assumption for the convergence results? - Instead of using randomly initialized weights in the experiments, it would be interesting to use learned weights. - Line 130, what is the meaning of “A MEANGNN is one where…”.

Questions

Please see the weakness part.

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

The authors discuss the limitation that their proposed theory results are only applicable to the examined graph models and GNN structures employing a mean aggregator, which is adequate. I do not see any negative social impact.

Summary

In this paper, the authors show that GNNs for graph classification applied to several classes of random graphs (with any node features) converges asymptotically almost surely to a constant. This is similar to several recent results in the literature on graphon-like graphs, but with a potentially stronger notion of asymptotic convergence, and with a seemingly very different proofs based on language terms and associated notions.

Strengths

- a very original approach to GNNs on random graphs compared to the literature - the handling of barabasi-albert graphs, which are very different from the results in the literature which treated of graphons, random geometric graphs, and so on.

Weaknesses

- the presentation of language, terms, and all associated notions is very cryptic for the reader unfamiliar with this specific field (which would be most readers in Neurips). It is very hard to parse the notations and vocabulary, and to relate it to more familiar notions (vectorss, functions, etc.). Some notations seem (?) a bit unconsistent; $x$ sometimes refer to nodes, sometimes to "free variable" (?) and nodes become $u$, and so on. Other notions ("graph-type", "edge negation", "feature controller"...) are very hard to digest - it is not clear how the authors handle the notion of "class", the figure 1 seems to suggest that there are several classes and that converging to a constant is a limitation, but surely if all the graphs are drawn from the same distribution they should be all in the same class? Or are the labels related to something else? Other works (eg by Levie) precisely look at the ability of GNNs to distinguish between graphs drawn from different distributions - this work is not the only one to do so, but it mixes two worlds that do not collide in practice: that of graph classification and of asymptotically large graphs. In practice, graph classification tasks are done on small-ish graphs, while large graphs are almost always for node classification.

Questions

- the fact that GNNs converge to a limit object on random graphs has been proved several times before (possibly for less general architectures and distribution of graphs), even with strong non-asymptotic results, in which way an asymptotic convergence is "stronger" as claimed by the authors? - the authors mention at the end the treatment of max aggregation which may be different; it is indeed treated specifically in their reference [9], could similar technique be employed?

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

NA

Summary

This paper introduces a term language to express many common GNN architectures as probabilistic classifiers. Using this term language, the authors provide asymptotically almost sure convergence results for dense and sparse random graph models (Erdos-Renyi variants, Barabasi-Albert, Stochastic Block Model). They perform experiments for these graph models as well as one real-world dataset with several different GNN architectures expressible in their term language. Their empirical results align with the presented theory and they can indeed observe convergence to a class distribution as the size of the graphs increases.

Strengths

This contribution seems novel, useful and of interest to the broader graph learning community. Overall, the paper is well-written and, despite its technical nature, relatively easy to follow. The introduction of the term language, which allows for proving asymptotic almost sure convergence in a systematic manner, is very elegant, and the results apply to a broad number of random graph models (dense and sparse) and several state-of the art GNNs.

Weaknesses

The term language is not explained in sufficient detail. E.g., are there any specific assumptions that $\pi$ and $\tau$ need to satisfy? Could you clarify what is expressible within your term language and what is not? Please find some additional minor remarks below. * l. 14: ML -> please introduce abbreviation first * l. 64: what does "import" mean here? (should it be "impact"?) * l. 127, 132: neighbor vs. neighbour * l. 137: What is $\mathbf{W}_V$ (in comparison to just $\mathbf{W}$ in GAT)? * l. 143: dot in sentence (after [12]) * l. 163: What is $k$? The number of nodes? * l. 165: Consider re-writing this sentence as it is difficult to understand * Def. 4.3: Missing $G$ subscript? * l. 233: Sentence seems to be missing something: "Then for every AGG[...] term converges a.a.s. with respect to $(\mu_n)$" * l. 236: regardless of "the" input graph * l. 294: "this phenomenon" or "these phenomena"

Questions

1. What happens if we use different (but Lipschitz continuous or smooth) activation functions? E.g., the sine function (while perhaps a peculiar choice) is smooth, but not eventually constant. Is it expressible in your term language? 2. On a related note, could you state more explicitly or provide some intuition on what assumptions are needed for, e.g., activation functions to be expressible in your term language (beyond the discussion, where it is mentioned that we need mean aggregation and activation functions need to be smooth)? 3. Could you say more about the rate of convergence?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

As briefly mentioned in the **Weaknesses**, the limitations of what can be expressed in the term language are not explicitly stated. While the authors state that the term language is applicable to a wide set of GNN architectures, this is only shown for a subset of them (and for, e.g., GCN, the term language needed to be extended accordingly).