Message passing neural networks (MPNNs) have emerged as the most popular framework of graph neural networks (GNNs) in recent years. However, their expressive power is limited by the 1-dimensional Weisfeiler-Lehman (1-WL) test. Some works are inspired by $k$-WL/FWL (Folklore WL) and design the corresponding neural versions. Despite the high expressive power, there are serious limitations in this line of research. In particular, (1) $k$-WL/FWL requires at least $O(n^k)$ space complexity, which is impractical for large graphs even when $k=3$; (2) The design space of $k$-WL/FWL is rigid, with the only adjustable hyper-parameter being $k$. To tackle the first limitation, we propose an extension, $(k,t)$-FWL. We theoretically prove that even if we fix the space complexity to $O(n^k)$ (for any $k\geq 2$) in $(k,t)$-FWL, we can construct an expressiveness hierarchy up to solving the graph isomorphism problem. To tackle the second problem, we propose $k$-FWL+, which considers any equivariant set as neighbors instead of all nodes, thereby greatly expanding the design space of $k$-FWL. Combining these two modifications results in a flexible and powerful framework $(k,t)$-FWL+. We demonstrate $(k,t)$-FWL+ can implement most existing models with matching expressiveness. We then introduce an instance of $(k,t)$-FWL+ called Neighborhood$^2$-FWL (N$^2$-FWL), which is practically and theoretically sound. We prove that N$^2$-FWL is no less powerful than 3-WL, and can encode many substructures while only requiring $O(n^2)$ space. Finally, we design its neural version named N$^2$-GNN and evaluate its performance on various tasks. N$^2$-GNN achieves record-breaking results on ZINC-Subset (0.059), outperforming previous SOTA results by 10.6%. Moreover, N$^2$-GNN achieves new SOTA results on the BREC dataset (71.8%) among all existing high-expressive GNN methods.
Paper
Similar papers
Peer review
Summary
The paper builds an extension to the $k$-FWL isomorphism test algorithms called $(k,t)$-FWL+. The proposed extended family subsumes the existing $k$-FWL and adds finer variants to the expressivity landscape of isomorphism testing algorithms. The $(k,t)$-FWL+ algorithm is a combination of two modified schemes to the original $k$-FWL algorithm. The first one, called $(k,t)$-FWL, which also colors $k$ tuples, and draws insparation from the tuple based aggregation of the $k$-FWL algorithm vs. $k$-WL. The proposed algorithm changes the construction of neighborhood multi-stets used in the encoding step of the $k$-FWL algorithm. Briefly explained, instead of consisting of $n$ tuples of size $k$ , $(k,t)$-FWL aggregates a multi-sets consisting of $n^t$ tuples of size $\sum_{i=0}^{\min (k,t)}{ k \choose i} {t \choose i}$. Where each tuple in the new proposed algorithm holds more information than in the original $k$-FWL algorithm. The authors prove that for a fixed $k$, increasing $t$ induces a strict hierarchy where there exist a large enough $t$ for which the algorithm solves the isomorphism problem. The second modification, called $k$-FWL+, unifies many previously introduced approaches, and suggests modifying the neighborhoods of tuples to be equivariant sets of nodes instead of the entire node set of the graph. Which can reduce time complexity of the algorithm. The main contributions of the paper are (i) introducing a novel finer hierarchy of isomorphism testing algorithms; (ii) showing that it is possible to construct a strict hierarchy at fixed memory complexity that can achieve solving the isomorphism problem; (iii) coming up with a practical neural instantiation; and (iv) achieving state of the art results on common benchmarks.
Strengths
- The paper is well written and successfully introduces the limitations of the $k$-WL hierarchy for the evaluation and design of more expressive GNNs. It is part of a body of works that refine the WL hierarchy aiming for more efficient algorithms with higher expressive power. - The paper introduces a general framework that is also shown to unify several recent approaches and can provide a canonical design space for previous and future GNNs. - The construction of the $(k,t)$-FWL hierarchy naturally arises from the original $k$-FWL algorithms and elegantly shifts memory complexity to runtime complexity in the fixed $k$ scenario. - The experimental evaluation is extensive and the proposed method seems to achieve SOTA performance.
Weaknesses
- The paper does not properly discuss the "no free lunch" that hides in the proposed method. Indeed, the authors came up with a fixed space complexity hierarchy which, for large enough parameter $t$, can solve the isomorphism problem. But, this comes at the cost of time complexity - having to aggregate an exponentially growing number of tuples ($O(n^t)$). The authors deferred most of this discussion to the appendix, while I believe it should be placed in the main body of the paper. - A valuable ablation study lacking in the paper is an experiment showing the performance of several variants of the new proposed hierarchy on the substructure counting benchmark. Since it is unclear what each variant gains in expressiveness, I believe such an evaluation will contribute to the paper's intuition and wholeness. - Questionable results in the QM9 dataset. See the questions section.
Questions
- A neural counterpart is suggested only for a single instance in the hierarchy. An interesting realm to explore would be to find a neural analog to the proposed hierarchy (similar to [1]) - There seems to be a mismatch in the units for the QM9 experiment between your code and the code in the $I^2$-GNN repository [2]. They seem to convert back to previously used units to be consistent with previous works while your code uses the new conversion. Can the authors please clarify this issue? To my understanding, for example, the value that should be reported for $\tilde{U}_0=U_0/0.04336414=0.5744$, where $U_0$ is the value reported in this paper. - Can the authors report runtimes of their GNN training and how it compares to other approaches? Since their approach trades space complexity for runtime complexity, I think it is necessary to show that the method remains scalable where the authors hinted that runtimes might increase when graphs are dense. - In the appendix, the authors say (l1094): "...we observe it some time hard to optimize 1095 the model to achieve its theoretical power by using fewer embedding". Can the authors clarify this statement? [1] Provably Powerful Graph Neural Networks. Maron et. al. (NuerIPS 2019) [2] [$I^2$-GNN GitHub](https://github.com/GraphPKU/I2GNN/blob/master/run_qm9.py#L37)
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
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
3 good
Contribution
3 good
Limitations
- The authors describe the limitations of the method mainly in the appendix, I think some of the discussion should be moved to the main body (see questions section) **General comment:** I lean towards raising my score upon clarification of the experimental results. I think the proposed framework is a natural extension of the $k$-FWL family that elegantly formulates the trade-off between time and space complexity.
Summary
The Weisfeiler-Leman algorithm has been established as the formal tool of choice for measuring the expressivity of GNNs. The paper tackles the problem of designing "higher-order" GNNs, which has been previously considered by several papers. The authors propose and combine two new ideas to supplement k-WL: (1) add in further subgraph information in a space-efficient manner via a hyperparameter $t$, and (2) allow neighbor selection in folklore-k-WL from any equivariant fashion, instead of the standard sets such as the set of all vertices or the set of all neighbors. Combining these two ideas yields the (k,t)-FWL+ algorithm. The version for k=2 and t=2, i.e. (2,2)-FWL+, is thoroughly evaluated on several datasets, and it yields very good experimental results, esp. on the ZINC dataset.
Strengths
1) The (2,2)-FWL+ performs very well on several datasets. On the ZINC datasets, they report 10.6% and 40.9% improvement over the second-best methods. 2) The authors identify the problem of space limitations for higher-order GNNs and they seek to address them in their model.
Weaknesses
1) The proposed algorithm lacks novelty: the claimed theoretical contributions are superficial. Graph Isomorphism can be obviously solved in quadratic space, if we were to allow iteration over all possible mappings between the two vertex sets. Such an algorithm might be space-efficient on paper but does not indicate any tractability since it brute-force tries all possible mappings. The proofs outlining the power and limitations of (k,t)-FWL are mild generalizations of known results, and lack any novel insights. 2) Allowing equivariant sets for vertex choice in k-FWL is a reasonable idea: however, I would expect the authors to compare several "equivariant set strategies" and demonstrate the relative gains over non-classic equivariant sets such as V(G) or N(v,G), keeping other things equal (an ablation study). Overall, I feel that the paper is not much different from a multitude of papers on designing higher order GNNs using subgraph enhancement. Given the work that had already been done on this problem, the proposed model is incremental.
Questions
-
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
Yes.
Summary
The authors propose generalizations of k-WL and k-FWL to (k, t)-FWL, and k-FWL+, which when combined, is notated as (k, t)-FWL+. They argue that (k, t)-FWL+ allow a more "flexible and fine-grained" space for exploring the graph expressiveness hierarchy, which is helpful in designing new GNN architectures. As a practical application, the authors propose Neighborhood^2-GNN which is based off a version of (2, 2)-FWL+, and outperforms state-of-the-art models on standard and synthetic tasks alike.
Strengths
The paper's strengths lie in the authors' extensions of FWL, Neighborhood^2-FWL (N^2-FWL), and its strong empirical performance with regards to baselines. The new formulation of (k, t)-FWL+ allows researchers to easily derive new extensions of FWL algorithms (and lead to new GNN models as a result). N^2-FWL is an empirical demonstration of the power of (k, t)-FWL+, showing that even with O(n^2) space complexity, these algorithms can be highly expressive, which is supported with multiple experiments.
Weaknesses
The paper's weaknesses lie in its lack of clarity. Especially as a rather technical paper, there seems to be a lack of intuition-based explanations and motivations for a large portion of the paper, which makes it hard to follow at points. More figures may help as well. In addition, the authors' do not mention any details about time in the main paper (only in the Appendix), with a time complexity of $O(nd^{h+2})$, which they claim to be practical for real-world tasks. It would be nice to see empirical run-time, as well as memory consumption charts/tables which would help solidify the empirical contribution. Typo on line 181.
Questions
1. How was N^2-FWL motivated? Why was it chosen over other possible (k, t)-WFL+ configurations? It seems as if it is not the only configuration that gives such properties. 2. How does the runtime and memory consumption compare to node-based GNN models? And to traditional edge-based subgraph models?
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
4 excellent
Presentation
3 good
Contribution
3 good
Limitations
Some limitations are addressed, but only in the Appendix. Most points are addressed in the section in the appendix, but would prefer if it were in the main paper. No potential negative societal impact.
Summary
The paper deals with supervised learning on graphs. Specifically, it proposes a more fine-grained version of the (folklore) k-WL (k-FWL) hierarchy. In turn, these variants are neuralized via standard techniques. Specifically, the authors propose the $(k,t)$-FWL, which extends the $k$-FWL by the parameter $t$, which controls which tuples are used for refining the color of a tuple. That is, following Eq. (6), the authors consider $t$-tuples to control the cardinality of the neighborhood of a given $k$-tuple. Subsequently, building on **standard constructions** from the $k$-WL literature, they investigate how, for a fixed $k$, varying $t$ controls the expressivity in terms of distinguishing non-isomorphic graphs (Prop. 3.1 to 3.3). They further propose a simple extension of the above, the $k$-FWL, which uses a relaxed version of the neighborhood between a given $k$-tuple and a vertex in the underlying graph. Furthermore, they show that some recent GNN enhancements are subsumed by their framework. The theory is complemented by an experimental study showing that the neuralized variants exhibit SOTA predictive performance on two common benchmark datasets.
Strengths
- The authors report good experimental results on established benchmark datasets. The experimental protocol looks meaningful.
Weaknesses
- The paper lacks clarity. For example, the exact definition of $Q^F_w(v)$ (line 136ff) is unclear. It is a central concept introduced in the paper, and it should be properly formalized. Moreover, the definitions in Section 3.3 are not entirely clear and make it hard to verify the formal proofs. - The authors seem to **oversell their contribution**, e.g., - The discussion on the benefits of the k-FWL over the k-WL (lines 119 to 135) is folklore. There is no new insight. This also **holds for the quadratic complexity of their algorithm** (e.g., lines 60 to 67). Note that big O notation is wrongly used here. Big Omega should be appropriate here. - Subsection 3.1 just contains a simple extension of established ideas, e.g., from [8,12]. - Results in Section 4.2 are obvious by standard results from the GNN literature - ... - The running time and memory complexity of the algorithms are **not formally proved**. This seems crucial for the present work. Also the authors seem to confuse big O with big Omega notation. - Relevant related work such as https://arxiv.org/abs/2203.13913 seems missing. Comments: - It is not correct saying that the $k$-WL requires $\mathcal{O}(n^k)$ space, it is a **lower** bound not an upper bound.
Questions
- What is the definition of "hierarchical multiset" (line 145)? - Can you quantify the h in Theorem 4.1? - What is required h for the statement of Theorem 4.3
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
2 fair
Presentation
2 fair
Contribution
2 fair
Limitations
See weaknesses.
Summary
The authors start by considering the k-dim Weisfeiler-Lehman test (WL). To solve the well-known problems of k-WL/FWL (high space complexity $O(n^k)$ and rigid design space), the authors propose two extensions of the k-FWL, named (k, t)-FWL and k-FWL+. The first extension is based on the simple observation that k-WL aggregates each color separately while k-FWL aggregates the tuple of colors. Expressive results of (k,t)-FWL are provided (3.1 - 3.3). The second extension is based on the simple modification of k-FWL; instead of considering the whole vertex set, consider only a particular neighbor. These two extensions are then combined to (k, t)-FWL+, of which expressiveness results are provided compared to the previous gallery of GNN/WL models (3.5 - 3.9). Lastly, the authors then propose N2-GNN, an implementation of (2, 2)-FWL+ as well as empirical results showing the efficacy of N2-GNN.
Strengths
- Despite the complex nature of the concepts, the exposition of their main algorithm and the conceptual design was very well done (especially Figure 1) - I very much appreciate the simplicity of the idea that leads to space-efficient variants of (F)WL tests which are still quite powerful. - Although I did not check the proofs in detail, the authors provide an impressive list of theoretical results regarding their proposed (k, t)-FWL+, all of which provide solid theoretical superiority over previous works. - The experimental results seem promising.
Weaknesses
- Although the concepts are well delivered, all technical details, especially the proofs, are entirely relegated to the Appendix. Are there any notable technical novelties in the proofs of the myriad of theoretical results, or are they somewhat standard? - It is expected that the expressive power of (k, t)-FWL+ depends heavily on the definition of ES, which the authors addressed via a myriad of propositions (3.4 - 3.9) for specific instances. However, if possible, it would be great to have some intuitions on the interplay of the choices of (k, t) and ES. Maybe the authors could choose a single proposition and try to explain the intuition behind it further (e.g., Proposition 3.4) via additional figures or discussions. - Some of the references are in poor condition (e.g., [11], [12], [16]).
Questions
1. It states on pg. 4 lines 159-160, that "size of Q_wF(w) will grow exponentially with an increase in the size of t". Then does that mean that requiring O(n^2) is equivalent to confining t=2 (or at least small t)? Also, throughout the paper, the only time t is not 2 is in the theories when the authors prove a hierarchy w.r.t. t. Are there situations in which t should be set to 3 or higher? 2. Is there any way of comparing the expressiveness of (k, t)-FWL and (k', t')-FWL with k+t = k'+t'? For instance, can one compare the expressiveness of (2, 3)-FWL and (3, 2)-FWL? 3. Before combining (k,t)-FWL and FWL+, is it possible to also obtain expressiveness hierarchy results on FLW+ depending on the choice of ES? For instance, with fixed t=1 and k=2, can you say anything about the expressiveness across the choices of ES(v) as considered in Proposition 3.4 - 3.9? 4. It is mentioned in the conclusions that the practical complexity of N2-GNN can still be unbearable, especially for dense graphs. Thus I'm curious about the running times of all the algorithms in comparison. Is there a trade-off if one sets the training budget approximately the same for all the algorithms? 5. There was a mention of Puny et al. [43] that performs O(n^2) space 3-WL via graph polynomial features. Although the authors mentioned that they suffer from overfitting, I'm still curious. Are there any theoretical results (e.g., expressiveness hierarchy) or empirical results that compare [43] to (k, t)-FWL+? (minor suggestion: it would be nice to have a table of contents, maybe at the start of the appendix, to make it easier to navigate)
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
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
3 good
Contribution
4 excellent
Limitations
Although this work needs not address any societal impact, the work has no mention of its limitations and possible future works. I would like to ask the authors to include some of the possible limitations of their work (possibly with possible solutions, but I won't be negative if there are none for now, which by the way is also quite natural in my eyes.)
I thank the authors for providing detailed responses to my questions and comments. I'm satisfied with the responses and intend to keep my score.
Answer to rebutall.
I am very well aware of the definition of the big Omega. There does not exist proof that the $k$-WL runs in $\mathcal{O}(n^k)$. Simply iterating over all possible $k$-tuples already takes $\Omega(n^k)$ time; note that does not include the aggregation over neighboring $k$-tuples. I do not believe that the work in its current form is ready for publication. I also strongly agree with the points mentioned by Reviewer eNLB. The only merit of this work is its strong empirical performance.
Follow-up discussion
Thanks for your follow-up comments. We further clarify them as follows. > Big O vs Big Omega **Answer:** First, we rewrite the update function of $k$-WL here: $ \mathcal{C}^{l-1}(\mathbf{v}) = \text{HASH}( \mathcal{C}^{l-1}(\mathbf{v}), ( \\{\\!\\!\\{ \mathcal{C}^{l-1}( \mathbf{u}) | \mathbf{u} \in Q_j(\mathbf{v})\\}\\!\\!\\} |\ j \in [k] )) $, where $Q_j(\mathbf{v})= \\{\mathbf{v}_{w/j}|w \in V(G)\\}$ and $ \mathbf{v}_{w/j} $= $\left(v_{1}, \ldots, v_{j-1}, w, v_{j+1}, \ldots, v_{k} \right)$. In our paper, we state that the $k$-WL has a space complexity of $O(n^k)$ and time complexity of $O(n^{k+1})$ (line 33-34). Now, we show there exists an implementation of $k$-WL that satisifies the above complexity. First, since the number of $k$-tuples in an $n$-node graph is $n^k$, to save the initial color of each $k$-tuple, we need $n^k$ space. At each iteration, to update the color of each $k$-tuple $\mathbf{v}$: (1) We first create a new space to save all the updated colors. This results in another $n^k$ space. (2) Then, $\forall i \in [k]$, $(v_{1}, \ldots, v_{i-1}, v_{i+1}, \ldots, v_{k}) \in V^{k-1}(G)$, we compute the result color of the aggregated multiset $\\{\\!\\!\\{\mathcal{C}^{l-1}(v_{1}, \ldots, v_{i-1}, u, v_{i+1}, \ldots, v_{k})| u \in V(G) \\}\\!\\!\\}$ and save it to a new space as an intermediate result. Since there are in total $kn^{k-1}$ different multisets and each multiset requires $n$ time to compute result, this step requires another $kn^{k-1}$ space and $kn^k$ time complexity. (3) Next, we update the color of each tuple $\mathbf{v}$. Since the color of each multiset is already computed and saved in step (2), we could use the saved result to directly update the color of each tuple $\mathbf{v}$, and save it to the space we created in step (1). This results in another $k+1$ time complexity (as there are $k$ multisets per tuple plus the tuple itself). Thus, the total time complexity in this step is $(k+1)n^k \leq (n+1) n^{k} = O(n^{k+1})$. (4) Finally, we delete all the saved colors except for the updated color for each tuple. In summary, for space complexity, we have $n^k$ (saving old color) + $n^k$ (saving new color) + $kn^{k-1}$ (intermidiate results) = $O(n^k)$. For time complexity, we have $kn^k$ (compute all possible multisets) + $O(n^{k+1})$ (update color for each $k$-tuple) = $O(n^{k+1})$. We are aware that the running time of $k$-WL can be more tightly bounded by $O(kn^k)$. However, the $O(n^{k+1})$ stated in the paper still holds. In the "Comments" of your review, you stated "It is not correct saying that the $k$-WL requires $\mathcal{O}(n^k)$ space, it is a lower bound not an upper bound." So we assume your main concern is on space complexity. Now we have proved that the $\mathcal{O}(n^k)$ space complexity is indeed feasible. Therefore, the big Omega notation need not be used. > Strongly agree with the points mentioned by Reviewer eNLB. **Answer:** We admit that the criteria for novelty can be subjective. In the general response point 1, we further clarified the main contributions of our paper. We kindly ask the reviewer to go through the response and inform us which points you are concerned about. We are more than glad to explain them further. > The only merit of this work is its strong empirical performance. **Answer**: We believe the strong empirical performance of $N^2$-GNN further proves that our proposed $(k, t)$-FWL+ framework has great potential for designing new expressive GNN variants, as evidenced by the two new SOTA results on ZINC and ZINC-full (general response point 1, contribution (4)). We strongly believe $(k, t)$-FWL+ can inspire more novel and expressive GNNs and broaden the design space of current high-expressiveness GNNs.
Answer
Thank you for the clarification, I will have another detailed look at the paper.
Answer
I did reread the paper, and I do believe that the work is interesting and the empirical results are promising. However, I agree with Reviewer eNLB that the quadratic complexity result is oversold and that the main contribution lies in the subgraph enhancement, which makes the novel contribution of the work less clear. Moreover, I still believe that the paper lacks clarity. I would encourage the authors to restructure their work and clarify where the architecture is novel over the large literature on subgraph-enhanced GNNs.
Follow-up discussion 2
Thank you for your follow-up discussion. We are happy to further clarify your concern. > I do believe that the work is interesting and the empirical results are promising. **Answer:** Thanks for the positive feedback! > However, I agree with Reviewer eNLB that the quadratic complexity result is oversold and that the main contribution lies in the subgraph enhancement, which makes the novel contribution of the work less clear. **Answer:** We thanks reviewer for the comment. We kindly refer the reviewer to our reply to the reviewer eNLB where we further clarfied the "oversold contribution" and "subgraph enhancement". Please let us know if you have any further concerns. > Moreover, I still believe that the paper lacks clarity. **Answer:** We do apology for any lack of clarity. We will try our best to make the paper more readable in the future version by providing additional figures/examples.
Dear reviewer 3qR2: We would like to sincerely thank you again for the time and effort spent reviewing our work and providing valuable comments. As the discussion period ends soon, could we kindly know if the responses have addressed your concerns and if further explanations or clarifications are needed? To make it easy for you, we kindly refer the reviewer to our response to reviewer eNLB for the detailed discussion on subgraph enhancement (point 5), additional ablation study on algorithms with different space complexity (point 6), and oversold contribution (point 7). If there is no further concern, we kindly hope that the reviewer could consider re-evaluating our work. Thank you again. Authors.
Answer
Thank you, I will keep my score. I strongly believe that the work needs a major revision in terms of clarity and in terms of clarifying its actual main contribution. I also strongly support the additional detailed answers of Reviewer eNLB.
I thank the authors for addressing my questions. My main problem with the paper is: I am not convinced that the "quadratic space" perspective is a significant contribution which deserves to be the centerpiece of this paper. My reasons stand as follows. The presented work (the “t”-extenstion and the “+”-extension) is more in the nature of feature extraction, rather than something which yields actual insights into how and why WL learns on graphs. The claimed premise that “quadratic-space WL is the right inductive bias that unifies several existing architectures” is too strong a statement which requires much better evidence that what is presented. Theoretically, the main results (Proposition 3.1, Theorem 3.2 and Proposition 3.3) and their proofs are either trivial or comprise trivial modifications to existing literature. Yes, indeed, the paper points out one could re-parameterize Weisfeiler-Leman from $k$ to $(k,t)$ to obtain a finer hierarchy. Yet, in my opinion, the main contribution of this re-parameterization is the following: the (k,t)-FWL algorithm performs "subgraph enhancement using subgraphs of size $t$" in "quadratic space" instead of "potentially $n^t$ space". Hence, the proposed re-parameterization is more of a \emph{subgraph enhancement} GNN which works in quadratic space. It is in this context that I find the novelty lacking, given the plethora of existing "subgraph enhancement" GNNs already. Experimentally, the most promising results are for the case k=2 and t=2. The "2-tuple" regime is also heavily researched with a fairly big crowd of similar architectures for aggregating information for 2-tuples: It is not clear at all if the empirical success of (2,2)-FWL+ can be attributed solely to the "quadratic space" inductive bias, or something else. It seems to me that the empirical success can be attributed mainly to the "+"-extension (i.e. choosing equivariant sets) rather than the "t"-extension (i.e. using small space). It would be much better if the authors had built this paper around their solid contribution, namely the (2,2)-FWL+ algorithm, which speaks for itself with its strong performance on the ZINC dataset. Instead the authors have chosen to focus on the quadratic space perspective, which is not very insightful, at least to me, and forms an artificial framework that I find hard to justify. In its current form, the paper does not meet the NeurIPS bar in my opinion.
Follow-up discussion part 1
We thank the reviewer for the follow-up discussion. We are happy to further clarify them all. > 1. The presented work (the “t”-extenstion and the “+”-extension) is more in the nature of feature extraction, rather than something which yields actual insights into how and why WL learns on graphs. **Answer:** Why WL can learn on graphs is a complex question. In $k$-WL/FWL, the isomorphism type of each $k$-tuple ($k$-subgraph) is encoded as the initial color. As long as the $k$ increases, $k$-WL/FWL can naturally encode higher-order subgraph information about the graph and learn more fine-grained information through the message passing. However, in order to keep permutation invariant, $k$-WL/FWL **needs to encode all possible $k$-tuples**, which is why $k$-WL/FWL has the **concurrent growth of both the time and space complexity**. Our $(k, t)$-FWL is motivated exactly by this limitation as well as the difference between $k$-WL and $k$-FWL: $k$-FWL could infer higher-order structure information through the **tuple-style** aggregation using the same space complexity as $k$-WL. Then, the $(k, t)$-FWL is designed to extend this **insight** to encode arbitrary higher-order structures (controlled by $t$) with fixed-length tuples (controlled by $k$). Through theoretical results (Proposition 3.1, 3.3, Theorem 3.2), we show that $(k, t)$-FWL constructs **a full expressiveness hierarchy with any fixed-length tuples**. The $(k, t)$-FWL+ further extends the design space by allowing arbitrary equivariant sets to define neighbor tuples. Therefore, our work **at least provides the following insights** into WL: 1) The space complexity need not grow with the time complexity to define a full hierarchy, and 2) $k$-WL/FWL has a much broader design space than originally thought by extending it to $(k, t)$-FWL+. Our work is not in the nature of feature extraction, but rather a general new framework for designing arbitrarily expressive GNNs. > 2. The claimed premise that “quadratic-space WL is the right inductive bias that unifies several existing architectures” is too strong a statement which requires much better evidence that what is presented. **Answer:** we never stated that “quadratic-space WL is the right inductive bias that unifies several existing architectures”. Instead, $(k, t)$-FWL is a framework that not only works on quadratic space, but can construct an expressiveness hierarchy given any fixed space complexity ($O(n^k), k \geq 2$). That is also one of the key reasons why $(k, t)$-FWL+ is very flexible and can unify several existing architectures. So far, we support our claim with a series of theoretical results (**Proposition 3.4-3.9**), which already cover most of the existing works discussed in our related works (Section 5). In fact, there might be a misunderstanding on the "$O(n^2)$ Space" in our title. We emphasize the "$O(n^2)$ Space" mainly to deliver a message that the space complexity can be fixed instead of growing with time for defining a WL hierarchy. We did not mean that the $O(n^2)$ space should be the right or only inductive bias. Instead, $O(n^3), O(n^4)$ may work even better for different problems, as long as we can afford the memory cost. > 3. Theoretically, the main results (Proposition 3.1, Theorem 3.2 and Proposition 3.3) and their proofs are either trivial or comprise trivial modifications to existing literature. **Answer:** Although our proof leverages some existing techniques used in the previous works [1-2], we do want to highlight that the core part of our proof is how to represent high-dimensional tuples using low-dimensional tuples, which, to our best knowledge, does not exist in any previous work and is nontrivial to do. Furthermore, our main contributions stand on the design of the $(k, t)$-FWL+ framework with a theoretical guarantee instead of proposing novel proof strategies. > 4. the main contribution of this re-parameterization is the following: the (k,t)-FWL algorithm performs "subgraph enhancement using subgraphs of size $t$ in "quadratic space" instead of "potentially $n^t$ space". **Answer:** To clarify, $(k, t)$-FWL can encode subgraphs of size $k+t$ with $O(n^k)$ space instead of $O(n^{k+t})$ space for $(k+t)$-WL. Only when $k=2$, we can have a quadratic space complexity. The idea of encoding subgraphs of size $k+t$ with $O(n^k)$ space never shows in any previous works and is a novel contribution of our work. We kindly refer reviewer to discussion part 2 for further clarification.
Follow-up discussion part 2
> 5. Hence, the proposed re-parameterization is more of a **subgraph enhancement** GNN which works in quadratic space. It is in this context that I find the novelty lacking, given the plethora of existing "subgraph enhancement" GNNs already. **Answer:** In our Related works (Section 5), we provide a comprehensive discussion on existing subgraph enhancement GNNs. Here we give a more detailed discussion of the difference between theirs and ours. **Subgraph + MPNN[2-13]:** This type of method designs different subgraph extraction strategies and then runs MPNN on these subgraphs and aggregates them together to get final results. The difference between them and ours is that: (1) All of them require copying and separately running the model on all subgraphs. Suppose there are $s$ subgraphs, the space complexity is $O(sn)$, which results in $O(n^2)$ for node-based strategies; $O(nm)$ for edge-based strategies; $O(n^{k+1})$ for $k$-tuple based strategies. However, $(k, t)$-FWL can be implemented in any fixed space complexity. (2) All of them use MPNN as the base encoder. In [2], authors show that the advantage of the tuple-based aggregation is theoretically more expressive than local node aggregation used in MPNN. In the follow-up discussion to point 6, we will further support it from the empirical side. **Subgraph + $k$-WL[14]:** [14] propose $k, l$-WL, which run $k$-WL on all $l$-tuples' subgraphs. As we discussed in lines 164-165, they also require $O(n^{k+l})$ space complexity to achieve a comparable expressive power to $(k +l)$-WL. **Injecting subgraph features [15-20]:** This type of method tries to inject high-order subgraph features that cannot be learned by MPNN into the model to improve the expressive power of the MPNN. The difference between them and ours is that: (1) They need to explicitly design what type of subgraph features to encode into the model, which requires additional domain knowledge and is hard to generalize. Instead, $(k, t)$-FWL relies on the aggregation to automatically learn such patterns. (2) Further, injecting features into the model mostly works on the synthetic datasets but becomes easy to overfit on real-world datasets and the results are sub-optimal (e.g. performance on ZINC-subset/ZINC-full). Instead, our method has a better ability to integrate structure information and feature information to achieve SOTA results on real-world tasks. **High-order message-passing scheme [21-23]:** This type of method designs different message-passing schemes on high-order substructures like cycles or paths. The main differences between them and ours are: (1) the substructure and the message passing scheme need to be pre-designed, which requires additional domain knowledge and is hard to extend. (2) The space complexity depends on the message passing scheme and could still be high given the different choices of substructure/message-passing scheme. Instead, $(k, t)$-FWL can construct an expressiveness hierarchy within a fixed space complexity. We kindly refer the reviewer to discussion part 3 for the further clarification.
Follow-up discussion part 3
> 6. Experimentally, the most promising results are for the case k=2 and t=2. The "2-tuple" regime is also heavily researched with a fairly big crowd of similar architectures for aggregating information for 2-tuples: It is not clear at all if the empirical success of (2,2)-FWL+ can be attributed solely to the "quadratic space" inductive bias, or something else. It seems to me that the empirical success can be attributed mainly to the "+"-extension (i.e. choosing equivariant sets) rather than the "t"-extension (i.e. using small space). **Answer:** Thanks for your comments. Theoretically, we already proved that the $t$ extension helps to increase the expressive power of the $N^2$-FWL (surpass both node-based subgraph GNNs and edge-based subgraph GNN) within $O(n^2)$ space. To further verify the effectiveness of each component in our framework, we provide an additional ablation study on ZINC-subset. | Model | Space complexity | ZINC-subset. | |:---:|:---:|:---:| |SSWL+ [2]|$O(n^2)$|0.070 $\pm$ 0.005| |I$^2$-GNN [13]| $O(nm)$ |$0.083 \pm 0.001$| |3-IDMPNN [14]| $O(n^4)$ | $0.085 \pm 0.003$| |$t=1, k=2$, $ES$ is the one-hop neighbors of $v_1$| $O(n^2)$ |0.065 $\pm$ 0.003| |$t=1, k=2$, $ES$ is the one-hop neighbors of either $v_1$ or $v_2$| $O(n^2)$ |0.065 $\pm$ 0.004| |t=2, k=2, **N$^2$-GNN**| $O(n^2)$ |**0.059 $\pm$ 0.002**| The results of SSWL+, I$^2$-GNN, and 3-IDMPNN are reported from their papers and the results for last three rows are reported on an average of 10 runs with a similar model architecture and parameter size. The $ES$ in the N$^2$-GNN is the product of the one-hop neighbors of $v_1$ and the one-hop neighbors of $v_2$. From the results, we have the following conclusions: (1) I$^2$-GNN and 3-IDMPNN require higher space complexity than $O(n^2)$ theoretically but achieve sub-optimal results compared to methods in $O(n^2)$. This shows that a small space might indeed bring benefits to real-world tasks. Nevertheless, 3-IDMPNN subsamples the subgraphs, so a fair comprison to full $O(n^4)$ models is lacking. (2) Increasing $t$ from 1 to 2 also contributes hugely to the final result (by comparing the second/third to last row and the last row). This further verifies our design principle---increasing the expressive power by increasing $t$ successfully improves the results on real-world tasks. (3) The second to the last row can be viewed as a tuple-style aggregation version of SSWL+ (using MPNN as the base encoder). The performance gain empirically verified the superiority of tuple-style aggregation used in $(k, t)$-FWL+ compared to MPNN used in most of the existing subgraph-enhancement GNN. To conclude, the ablation study supports all of our claims and further verifies the effectiveness of the quadratic space and each component in the $(k, t)$-FWL+. > 7. It would be much better if the authors had built this paper around their solid contribution, namely the (2,2)-FWL+ algorithm, which speaks for itself with its strong performance on the ZINC dataset. Instead the authors have chosen to focus on the quadratic space perspective, which is not very insightful, at least to me, and forms an artificial framework that I find hard to justify. In its current form, the paper does not meet the NeurIPS bar in my opinion. **Answer:** Thanks for the suggestion. We do admit that our title "Towards Arbitrarily Expressive GNNs in $O(n^2)$ Space by Rethinking Folklore Weisfeiler-Lehman" may make the reviewers confused about our contributions. Here we would like to emphasize: (1) Indeed, solving graph isomorphism problem in $O(n^2)$ space is not new and has already been explored in previous literature like relational pooling [24]. However, the main contribution of $(k, t)$-FWL is not to solve graph isomorphism problem in quadratic space but to construct **an expressiveness hierarchy** like $k$-FWL/WL but **only within a fixed space complexity $O(n^k)$** for any $k \geq 2$. This idea never appears in previous works. (2) In this work, we not only aim to propose a new model N$^2$-GNN but also mean to introduce a new flexible framework, $(k, t)$-FWL+. Therefore, we believe limiting the discussion to $(2, 2)$-FWL+ is not appropriate and might compromise our overall contributions. Nevertheless, we appreciate the reviewer's acknowledgement on N$^2$-GNN's strong empirical performance. (3) In the revision, we will further improve our work by 1) making a better clarification on the main contributions of our proposed frameworks and 2) giving a detailed discussion on the limitations of all the proposed methods mentioned by all the reviewers. We kindly refer the reviewer to discussion part 4 for all references mentions in the follow-up discussion.
Follow-up discussion part 4
**References:** [1] Morris et al., Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings, NeurIPS20. [2] Zhang et al., A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests, ICML23. [3] Zhang and Li. Nested graph neural networks, Neurips21. [4] Zhao et al., From stars to subgraphs: Uplifting any GNN with local structure awareness, ICLR22. [5] Sandfelder et al., Ego-gnns: Exploiting ego structures in graph neural network, ICASSP21. [6] Frasca et al., Understanding and extending subgraph GNNs by rethinking their symmetries, Neurips22. [7] You et al., Identity-aware graph neural networks, AAAI21. [8] Li et al., Distance encoding: Design provably more powerful neural networks for graph representation learning, Neurips20. [9] Papp et al., DropGNN: Random dropouts increase the expressiveness of graph neural networks, Neurips21. [10] Cotta et al., Reconstruction for powerful graph representations Neurips21. [11] Bevilacqua et al., Equivariant subgraph aggregation networks, ICLR22. [12] Qian et al., Ordered subgraph aggregation networks, Neurips22. [13] Huang et al., Boosting the cycle counting power of graph neural networks with i$^2$-GNNs. ICLR22. [14] Zhou et al., From relational pooling to subgraph gnns: A universal framework for more expressive graph neural networks, ICML23. [15] Bouritsas, et al., Improving graph neural network expressivity via subgraph isomorphism counting, Arxiv, 2020. [16] Wijesinghe and Wang, A new perspective on ”how graph neural networks go beyond weisfeiler-lehman?" ICLR22. [17] Feng, et al., How powerful are k-hop message passing graph nerual networks, Neurips22. [18] Kong et al., Geodesic graph neural network for efficient graph representation learning, Neurips22. [19] Yan et al., Efficiently counting substructures by subgraph gnns without running gnn on subgraphs, Arxiv, 2023. [20] Puny et al., Equivariant polynomials for graph neural networks, ICML23. [21] Bodnar et al., Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks, LCML21. [22] Bodnar et al., Weisfeiler and lehman go cellular: CW networks. Neurips21. [23] Thiede et al., Autobahn: Automorphism-based Graph Neural Nets, Neurips21. [24] Murphy et al., Relational pooling for graph representations, ICML19.
Dear reviewer eNLB: We would like to sincerely thank you again for your efforts and constructive comments on our work. As the discussion period ends soon, could we kindly know if the responses have addressed your concerns and if further explanations or clarifications are needed? We provide a detailed follow-up discussion on (1) comparing different subgraph enhancement methods (point 5), (2) additional ablation study on methods with different space complexity (point 6), and (3) further clarification of our work (points 1-4, 7). If there is no further concern, we kindly hope that the reviewer could consider re-evaluating our work. Thank you again. Authors.
Thanks for your detailed comments. I will respond to only some of these comments, which I believe are the most relevant to the discussion. Point 1: "Therefore, our work at least provides the following insights into WL: 1) The space complexity need not grow with the time complexity to define a full hierarchy, and 2) k-WL/FWL has a much broader design space than originally thought by extending it to k-FWL+. Our work is not in the nature of feature extraction, but rather a general new framework for designing arbitrarily expressive GNNs." As I mentioned before, Graph Isomorphism can be trivially solved in quadratic space if we are ready to brute-force try all permutations between two graphs. To be more precise, the (k,t)-FWL algorithm yields a full hierarchy because for a graph on $n$ vertices, one can always make $t$ large enough to satisfy $k+t > n$, at which point the algorithm is essentially no better than brute-force trying all $O(t!)$ mappings between graphs. That "one can save space by resorting to brute-force enumeration" is hardly any valuable insight into WL-type hierarchies. Just the fact that "there exists a WL-hierarchy solving Graph Isomorphism which uses bounded space" is not a solid enough contribution in my opinion. Of course, it does not help that the accompanying proofs have no solid theoretical insights/contributions. Point 6: “Increasing $t$ from 1 to 2 also contributes hugely to the final result (by comparing the second/third to last row and the last row). This further verifies our design principle---increasing the expressive power by increasing $t$ successfully improves the results on real-world tasks.” I would argue that among the three experimental observations (1), (2) and (3) in Point (6), the above-stated observation (2) needs to be strongest, since this is supposed to substantiate the main hypothesis of the paper, namely using “small-space WL" as inductive bias. Let us examine the (k,t)-FWL design for $k=2, t=2$, without the plus extension. In this case, the (2,2)-FWL aggregates information for a tuple $(x,y) \in V(G)^2$ using each 2-tuple $(u,v) \in V(G)^2$, thereby utilizing the current states for the 2-tuples $(u,y)$, $(x,v)$ and $(u,v)$. The plus extension essentially ensures that the chosen tuples $(u,v)$ have something to do with the tuple $(x,y)$. This is in a similar spirit to the myriad of subgraph enhancement algorithms, existing in literature. Of course, it is not exactly same as any of them, but it is not radically different in design either. This is merely due to the fact that the computationally efficient regime for WL style architectures is fairly small, and has already been heavily explored. On the other hand, the (2,1)-FWL aggregates information for a tuple $(x,y) \in V(G)^2$ using each vertex $u \in V(G)$, thus utilizing the current states of the 2-tuples $(x,u)$ and $(u,y)$: this is simply the 2-WL algorithm. The plus extensions of (2,1)-FWL have been already studied in literature, as local 2-WL algorithms or shortest-path-based neural architectures. Does the standalone fact that “(2,2)-FWL+ performs much better than 2-WL and its standard variants” adequately demonstrate the design principle of “increasing $t$” and justify the entire "small-space WL hierarchy"? I do not think so. The computationally feasible regime for WL and subgraph enhancement is fairly limited and highly special: The provided experiments are not sufficient to adequately demonstrate the main hypothesis of the paper (i.e. “bounded-space WL hierarchy”), in my opinion. At the most, the paper can claim the contribution for space-efficiency improvements. My final reviewer assessment is as follows: The strong performance on standard datasets such as ZINC **does not adequately justify** the "small-space WL hierarchy" hypothesis. Conversely, the "small-space WL hierarchy" **does not adequately explain** this performance on standard datasets. My final decision remains the same: The paper needs substantial revision. Ideally, (2,2)-FWL+ should be the center of the paper, the theoretical contribution should be the space-efficiency improvements, and the experimental contribution should be the solid results on datasets such as ZINC. In its current form, the paper does not meet the NeurIPS threshold, in my humble opinion.
> Just the fact that "there exists a WL-hierarchy solving Graph Isomorphism which uses bounded space" is not a solid enough contribution in my opinion. We would like to clarify again that we are not trying to solve the graph isomorphism problem. The contribution of $(k, t)$-FWL is: $(k, t)$-FWL construct **an expressiveness hierarchy** like $k$-FWL/WL but **only within a fixed space complexity $O(n^k)$** for any $k \geq 2$, different from concurrently growth of both space and time complexity in $k$-FWL/WL. To our best knowledge, there is no similar proof or even discussion in previous work. We admit that the criteria for novelty can be subjective. But we would kindly ask the reviewer to provide related works you think are relevant so that we can further clarify it for you. > The plus extension essentially ensures that the chosen tuples $(u, v)$ have something to do with the tuple $(x, y)$. This is in a similar spirit to the myriad of subgraph enhancement algorithms, existing in literature. Of course, it is not exactly same as any of them, but it is not radically different in design either.. In your previous discussion, you stated that "Hence, the proposed re-parameterization in $(k, t)$-FWL is more of a subgraph enhancement GNN" (**follow-up discussion point (4)**). So we believe your main concern is in the **t**-extension instead of **+** extension. In the follow-up discussion point (5), we give a comprehensive discussion on almost all existing subgraph-based methods. None of them possess the similar idea of us. Here, your concern suddently changes to the **+** extension. Although we feel confused, we are glad to further clarify it. First, the **+**-extension states that we can use **any equivariant set** as the neighbor set, instead of only the subgraph-based aggregation. We choose a subgraph-based equivariant set in N$^2$-GNN mainly because of its provably strong substructure counting power (Theorem 4.3). However, N$^2$-GNN is only one instance designed based on our $(k, t)$-FWL+ framework. In the general response point 3, we also evaluate **different equivariant sets like $\mathcal{SP}(v_1, v_2)$, which is totally different from subgraph based methods** and it also works well in tasks like distinguishing strong-regular graphs. This further demonstrates that the **+**-extension and $(k, t)$-FWL+ is not a subgraph enhancement algorithm but a general framework for designing expressive GNN. We admit that the criteria for novelty can be subjective. But we would kindly ask the reviewer to provide related works you think are relevant so that we can further clarify it for you. > The "small-space WL hierarchy" hypothesis We think most of your concerns may be derived from the so-called "small-space" WL. Although we already clarify it several times, we would like to underscore again that our contribution is never only the "small-space" WL. Our main contributions are (1) $(k, t)$-FWL: a theoretical-guaranteed expressive hierarchy with a fixed space complexity $O(n^k)$ for any $k\geq2$; (2) $k$-FWL+: a generalized aggregation scheme to extend WL based algorithm; (3) $(k, t)$-FWL+: a flexible and power framework to design different expressive GNN with different space/time budget; (4) N$^2$-GNN: a practical design of $(k, t)$-FWL+ that achieve SOTA results on most of benchmark datasets. We believe they are all valuable insights to the community and it is not appropriate to limit our discussion to only a subset of all points.
Thank you for your answers. At the moment, there does not seem to be sufficient new information to increase or decrease my score, so I am inclined to keep it.
We thank the reviewer for diligently reading our responses and giving valuable suggestions. We will try our best to further improve the clarity of the paper in the future version by providing additional examples/figures.
I thank the authors for their answers and clarification of the experimental results. I agree with the other reviewers on the overselling (or the 'no free lunch') of the memory complexity O(n^2). However, I think this paper presents a general framework, whether one decides to frame it as a WL-hierarchy of a subgraph enhancement approach, that introduces flexibility in the design of algorithms and unifies existing ones.
Thanks again for your efforts in reviewing our work and providing insightful suggestions to improve our work. We will try our best to incorporate all of your comments in the revision.
Decision
Accept (poster)