Fine-grained Expressivity of Graph Neural Networks

Summary

With graphon theory, this work quantifies which distance MPNNs induce and thus provides a deeper understanding of MPNNs’ capacity to capture graph structure, precisely determining when they can and when they cannot assign similar and dissimilar vectorial representations to graphs.

Strengths

1. Strong universality results on graphon. 2. The iterated degree measure is intuitive and insightful.

Weaknesses

1. Graphon focus on graph limit. While in real world settings like graph classfication, the graph is small and MPNN still lacks expressivity. 2. Only the sum aggregation is analyzed. While in application, max and mean aggregation are also important.

Questions

Can you generalize the theory to max and mean aggregation?

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

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Yes

Summary

This work aims at a fine-gined metric to characterize representation differences from MPNNs. Specifically, they first generalize MPNN to iterative degree measures and prove that Prokhorov metric and unbalanced Wasserstein metric can be used to bound the node/graph representation difference. This relation is validated in their experiments on random graphs.

Strengths

- [significance] This work builds a connection between the GNN representations and the graph similarity, and makes a solid theoretical contribution to understand GNN expressivity. - Empirical results well support the theory.

Weaknesses

- The motivation and the conclusion of untrained GNNs experiments are not very clear to me. How is "an untrained GNN can outperform trained GNN" related to the previous conclusions and what message does this part try to convey? - Besides, TUDataset could be too small to faithfully evaluate the performance. Results on other datasets such as ZINC or OGB may further improve the evaluation.

Questions

- Could you provide an intuitive explanation for Theorem 4, the universal theorem? Does it essentially mean that MPNNs have the same separation power as 1-WL on graphons?

Rating

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

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

N/A

Summary

The paper considers the continuous variant of the 1-WL test and leverages it to characterize the expressive power of MPNNs on graphons. The authors show that if two graphons have similar MPNN outputs then they are close in their metric, extending the existing result proving the opposite implication (graphons similar in their metric have similar MPNN outputs). They establish a connection between the continuous variant of the 1-WL test and MPNNs to tree distance and tree homomorphism densities, where equivalences were only known to hold on a discrete level. Empirically, they show that untrained MPNNs (paired with a trained final classifier) obtain competitive performances on graph-level tasks. Finally, they experimentally compare different models in their ability to preserve graph distances.

Strengths

1. The paper refines existing results on metrics and MPNNs outputs. 2. The paper aims at closing the gap between results that were known to hold on a discrete level (where graphs are exactly isomorphic), but that were under explored at the continuous level.

Weaknesses

1. The paper is hard to read, as it introduces a lot of existing concepts and builds on them. Maybe it is inevitable due to intrinsic theoretical nature of the paper. However, I believe some extra effort is needed to remind the reader that a concept or theorem that is going to be introduced is, in simpler words, what has been presented in the introduction as a contribution. 2. I am unsure of the implications of this work. The theory is beautiful, but I am left unsure of what we can do with this gained knowledge. I don't see how this can help experimentally, or in real world cases.

Questions

1. Can you discuss the implications of this work? While I understand that the theoretical claims hold, what can we do knowing that they hold? 2. Similarly to the above question, what is the take-home message of the experimental evaluation? I am unsure of the relevance of the questions you set to answer.

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

3 good

Presentation

2 fair

Contribution

3 good

Limitations

NA

Summary

The paper studies the classes of MPNNs on graphons, ultimately showing that the MPNN representations are sufficiently close (up to constants depending on Lipschitz regularity and layers) _if and only if_ the graphons are close according to several metric distances, mainly the Prokhorov metric and the unbalanced Wasserstein metric.

Strengths

- The paper addresses a direction of research which is quite relevant, namely studying the response of GNNs and their dependence on properties of the input. In fact, the widely studied and adopted WL test is often a blunt yardstick for measuring the sensitivity of GNNs and investigating their dependence on metric functions defined on the space of graphs is worth looking into. - The exposition of the paper and overview of the related works is well executed. The setup is clear. - On a mathematical level, the works extends the results of [26] in several non-trivial ways and expands the efforts to understand GNNs through graphons in meaningful directions.

Weaknesses

- The fact that MPNNs exhibit a Lipschitz property compared to distances on graphons does not seem surprising to me (i.e. Lemma 3) given their regularity. The converse statement (Theorem 6) is perhaps less obvious, although I fail to see how can this be used in practice? In fact, it is not the qualitative $\epsilon-\delta$ statements that are that interesting in my opinion, but rather the quantitative bounds which seem though to be lacking any significant insight? For example in Lemma 3 the constant depends on the fact that the features "have to" be bounded on a compact metric space, which is ultimately not enlightening. More generally, it would be interesting not to prove some Lipschitz property of MPNNs, but perhaps how some more transparent properties of the graph structure translate _quantitatively_ into the Lipschitz bounds. - The analysis focuses on the case where graph(ons) are taken without features, which can be limiting although this setup is often conventional in the literature on expressivity of GNNs. - There is an impractical cost for computing the distances which should be explicitly reported in the main text -- as it stands, mentioning the polynomial running time in Theorem 2 is a little too vague. While this is probably minor compared to the other points, it also contributes to reducing the impact of the submission. - The experimental part is a little confusing. First, experiments on untrained MPNNs should be much better motivated, as it stands one can mainly guess what are you are trying to accomplish here. Second, validating that MPNNs can separate better with increased hidden dimension, is not surprising; besides, where is the role of the hidden dimension been discussed before? The fact that you can be competitive on some TUdataset "without" training over the layers is again not that surprising. These datasets are quite sensitive to hyperparameter tuning and I suspect that even removing the weights from the layer altogether and only train for the encoder and or decoder would be quite competitive. Maybe using different datasets -- more structural ones -- such as ZINC could be a little more indicative for a comparison.

Questions

- As far as I understand, extending these type of results to GNNs that do not follow the 1-WL paradigm of summing over the neighbours is possibly non-trivial right? I think that it would be interesting in general to see how quantitative $\delta$-bounds depend on different paradigms for using the graph information (from structural encoding, to Graph-Transformers). - I find that restricting to the feature-less case is a little detrimental to the overall message and I wonder in fact how challenging is extending this formalism to graphons with signals? I am not expecting a revision but am curious to hear comments here to gauge if this direction is actually pursuable or not. - In the experiments you claim that your results support Corollary 4? What is Corollary 4 and where in the manuscript you have mentioned the role of the hidden dimension? Besides, is it in general really surprising that MPNNs with more hidden dimension may be better at separating graphs? I think the paper has technical merits despite some mild concerns on the overall impact to the broader GNN community, and the score reflects this. The results are, on a qualitative level, intuitive, while on a quantitative level it is hard to extract some insight. The experimental section needs some revision as per my previous comments ---evaluating over a more structural-oriented task such as ZINC is perhaps a plus but not a must. Disclaimer: I have not checked the mathematical proofs in the appendix.

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

4 excellent

Contribution

2 fair

Limitations

Yes, limitations have been discussed and no societal impact can be foreseen.

Summary

The authors propose a novel way to generalize the expressivity of graph neural networks (and other general message passing algorithms) to the graphon case. Furthermore, they identify metrics on graphons (and, consequently graphs) which allow to bound the distance of any MPNN representation of the graphons.

Strengths

The paper provides an important step towards a more realistic analysis of MPNN expressivity. This paper goes beyond both common approaches to measure expressivity of MPNNs, presenting an epsilon delta result for two metrics on graph(on)s and MPNNs with Lipschitz constant and fixed number of layers. This properly generalizes the discrete setting and has potentially high impact sparking further research.

Weaknesses

It seems to me that the definition of GNNs in Line 212 1/2 is a rather severe deviation from most MPNN formulations, as it requires activations to grow linearly with the graph size to offset the normalization $\frac{1}{|V(G)|}$. This seems to be generally only possible for dense graphs when e.g. a fixed set of (one hot encoded) categorical labels is present.

Questions

I wonder if you can give some insights regarding the issue mentioned above? Also, it is not clear to me how the discussion of Q2 in the experiments is connected to the theory in the previous sections. I might have missed the connection, but to me it is unintuitive why the Lipschitz-arguments should imply that larger $L$ should result in more similar outputs. Minor Issues: l 299: 'in an MPNNs' p7 and p8 mention in relatively close distance two 'elegant' proofs. That struck me as a bit odd.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed 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

3 good

Presentation

4 excellent

Contribution

4 excellent

Limitations

The authors discuss technical limitations such as the current restriction to discretely labeled graphs and 1-WL. I don't see immediate negative societal impact of this work.