What Do GNNs Actually Learn? Towards Understanding their Representations

1. Analysis in 4.1 adopts a strong and unrealistic assumption that all nodes share the same feature. I do not fully understand why this setting is of theoretical interest or is relevant to practice, as it is perhaps obvious that GNNs will not perform good if nodes are identical and there exist trivial solutions such as adding one hot encodings. The conclusion about DGCNN and GAT might also have been overgeneralized, since this is not the case for other node features.
2. The bounds for both theorems do not seem tight and deteriorate with more layers. The proof circumvents nonlinearities and weights by simply resorting to an unknown Lipschitz constant for each layer, which could be arbitrarily bad in the worst case. PS, it is perhaps imprecise to term those representations as “learned representations” since no learning procedure is involved in the analysis (and thus the title “WHAT DO GNNS ACTUALLY LEARN” is also ambiguous.)
3. It is unclear what unexplained phenomenon can be explained by your analysis or how the analysis may help practice. While one could it a motivation to develop new models for improving representations of GNNs (just like those works in WL tests did), regrettably it is not the focus of this paper. Stronger theoretical results have already been established in research for oversmoothing (e.g. see [1] that is 4 year ago and many other follow-up works); while I understand the setting might be different and more variants are considered, results can still be adapted from those works.
4. For experiments, the phenomenon in figure 1 is based on restricted settings while the phenomenon in figure 2 is only reported on a single synthetic dataset. Additionally, the theorem seems infeasible to explain the strong correlation between node representation distances and number of walks reported in figure 1, as there is only upper bound but no lower bound given in the theorem.

Minors:
In theorem 4.2, h \mathbb R -> h \in \mathbb R
you might want to use $|\cdot|$ for scalar rather than l2 norm

[1] Graph Neural Networks Exponentially Lose Expressive Power for Node Classification, in ICLR 2020

1. The novelty and the contributions of the paper are quite limited compared to existing work on the representation power of GNNs. Prior research, as indicated in references [1, 5, 6], has delved deeply into discerning the structural properties that GNNs can efficiently capture or fail to address. The idea of studying the representation of GNNs from the view of random walks or paths on graphs is also not new. [1] has studied the representation power of GCN through the looking glass of graph moments, a key property of graph topology encoding paths of various lengths. [6] has proved several important graph properties that rely entirely on local information, such as longest or shortest cycle, diameter, or clique information, cannot be computed by GNNs.

2. Some important related works that also studied the representation powers of GNNs are missing, particularly [1], [2], [3], [4], [5], and [6], which raises concerns regarding the comprehensiveness and thoroughness of the literature review.

3. The claim that DGCNN and GAT do not capture structural properties of the neighborhood of nodes might be NOT true. The proof A.1 and A.2 simply ignore the Training Dynamics of DGCNN and GAT. Given a subset of labeled nodes which are used for training GNN models, the error will backpropagate differently depending on the loss at these labeled nodes. This can lead to different learned representations for nodes close to the labeled ones versus those farther away, even if all initial features are identical. Therefore, this claim might not be true.

4. The assumptions of the Lipschitz constants associated with the fully connected layer of the k-th neighborhood aggregation layer of GNN or MLP are too strong. Since this assumption is not a general Lipschitz assumption in GNN literature, it is not clear if such Lipchitz constants exist for all GNN layers. There is also no discussion on the validation of their Lipschitz assumptions.

5. The assumed Lipschitz constants may inherently embed some graph information since it is associated with the aggregation layer. This association suggests the possibility of the Lipschitz constants encapsulating information from intermediate nodes along a walk. Therefore, the claims following Theorem 4.2 that the representations of all models learned at the k-th neighborhood aggregation layer depend only on the nodes that can be reached in exactly k steps and not on the intermediate nodes along each walk might NOT be true.

6. The tightness of the Lipschitz bounds is unknown, which presents a significant concern. If these Lipschitz constants are substantially large, the cumulative effect from the product of all the constants across the k layers can lead to bounds that are exceedingly broad. Such expansive bounds might render them trivial or even ineffective in constraining the behavior of the GNNs as intended. Therefore, the theoretical results of the paper might not hold.

7. The paper only focuses on DGCNN, GAT, GCN, and GIN, not sure if the results can be generalized to other types of GNNs, such as massage pass neural networks, APPNP, and GPRGNN.

Overall, the novelty and the contributions of the paper are quite limited compared to existing work on the representation power of GNNs, where existing works have shown some graph structural properties that GNNs can or cannot learn. Some Claims of the paper might not be true due to the proof either ignoring the training dynamics of GNNs or making strong Lipschitz assumptions. Given these concerns, the reviewer recommends rejection.

Reference

[1] Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology, NeurIPS 2019.

[2] What Can Neural Networks Reason About? ICLR 2020.

[3] Graph Neural Networks Exponentially Loss Expressive Power for Node Representation, ICLR 2020.

[4] How hard is to distinguish graphs with graph neural networks? NeurIPS 2020.

[5] Can Graph Neural Networks Count Substructures? NeurIPS 2020.

[6] Generalization and Representational Limits of Graph Neural Networks, NeurIPS 2020.

1. The clarity is not so good for me, especially in Section 4.2. Please refer to "Questions" for details.
2. I am not so sure about the practical significance of this work. This work provides some new insights and understanding. It is better to generate new techniques from the insights to improve the model or mitigate the over-squashing.

I believe that the analysis is quite limited in terms of the overall contribution to the theoretical understanding of GNNs. Since the analysis only focuses on four of the numerous GNN architectures proposed in the literature over the past few years, it is unclear if and how it extends to other types of message-passing operations. Even for the GIN architecture that is among the ones analyzed in this work, there are several assumptions, such as $\epsilon = 0$ and the absence of the bias (it is unclear why the inequality $\\|\mathbf{b}\\| \ll \\|\mathbf{W}\mathbf{x}\\|$, mentioned after Assumption A.1, should hold in practice for any given $\mathbf{x}$). Also, the statement that "the representations learned at the $k$-th layer of the models are related to the initial features of nodes that can be reached in exactly $k$ steps." is trivial following the very definition of MPNNs on page 3, and should not be claimed as a contribution of the paper.