Your Neighbors Are Communicating: Towards Powerful and Scalable Graph Neural Networks
Authors: Meng Liu
Haiyang Yu
Shuiwang Ji
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph neural networks
expressiveness
graph isomorphism test

Abstract: Message passing graph neural networks (GNNs) are known to have their expressiveness upper-bounded by 1-dimensional Weisfeiler-Lehman (1-WL) algorithm. To achieve more powerful GNNs, existing attempts either require ad hoc features, or involve operations that incur high time and space complexities. In this work, we propose a general and provably powerful GNN framework that preserves the scalability of message passing scheme. In particular, we first propose to empower 1-WL for graph isomorphism test by considering edges among neighbors, giving rise to NC-1-WL. The expressiveness of NC-1-WL is shown to be strictly above 1-WL and below 3-WL theoretically. Further, we propose the NC-GNN framework as a differentiable neural version of NC-1-WL. Our simple implementation of NC-GNN is provably as powerful as NC-1-WL. Experiments demonstrate that our NC-GNN achieves remarkable performance on various benchmarks.

Under review as a conference paper at ICLR 2023
YOUR NEIGHBORS ARE COMMUNICATING: TOWARDS POWERFUL AND SCALABLE GRAPH NEURAL NET- WORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Message passing graph neural networks (GNNs) are known to have their expres- siveness upper-bounded by I-dimensional Weisfeiler-Lchme (1-WL) algorithm. To achieve more powerful GNNs, existing attempts either require ad hoc features, or involve operations that incur high time and space complexities. In this work, we propose general and provably powerful GNN framework that preserves the scalability of message passing scheme. In particular, we first propose to empower 1-WL for graph isomorphism test by considering edges among neighbors, giving rise to NC-1-WL. The expressiveness of NC- 1- 1-L- is shown to be strictly above 1-WL and below 3-WL theoretically. Further, we propose the NC-GNN framework differentiable neural version of NC-1-WL. Our simple implementation of NC-GNN is provably as powerful as NC-1-W WL. Experiments demonstrate that our NC-GNN achieves remarkable performance on various benchmarks.
INTRODUCTION
Graph Neural Networks (GNNs) (Gori et al., 2005; Scarselli al., 2008) have been demonstrated to be effective for various graph tasks. In general, modern GNNs employ a message passing mechanism where the representation of each node is recursively updated by aggregating representations from its neighbors (Atwood & Towsley, 2016; Li et al., 6; Kipf & Welling, 2017; Hamilton et al., 2017; Veličković et al., 2018; Xu et al., 2019; Gilmer et al., 2017). Such message passing GNNs, however, have been shown to be at most as powerful as the 1 1-dimensional Weisfeiler-Lehman (1-WL) algorithm (Weisfeiler Lehman, 1968) in distinguishing non-isomorphic graphs (Xu et al., 2019; Morris et al., 2019). Thus, message passing GNNs cannot distinguish some simple graphs and cannot detect certain important structural concepts (Chen et al., 2020; Arvind et al., 2020).
Recently, lot of efforts have been made to improve the expressiveness of message passing GNNs by considering high-dimennt digh-dimensional WL algorithms (e.g., Morris et al. (2019); Maron et al. (2019)). exploiting subgraph information (e.g., Bodnar al. (2021a); Zhang & Li (2021)), adding more distinguishable features (e.g., Murphy et al. (2:19); Bouritsas et al. (2022)). As thoroughly discussed in Section 5, these existing methods either rely on secrraacd/prddeeieee//dmmaannnnn -ppeciii features. or require high computational cost and memory budget. In contrast, our goal in this work is to develop a general GNN framework with provably expressive power, while maintaining the scalability of the message passing scheme.
Specifically, we first propose an extension of the 1-WL algorithm, namely NC-1-WL, by considering the edges among neighbors. In other words, we incorporate the information of which two neighbors are communicating (i.e., connected) into the graph isomorphism test algorithm. To achieve this, we mathematically model the edges among neighbors is represented as a multiset of two elements. We theoretically show that the expressiveness of our NC-1-WL in distinguishing non-isomorphic graphs is stricly above 1-WL and below 3-WL. Further, based on NC- W-W, we propose a general GNN framework. known as NC-GNN, which can be considered differentiable neural version of NC-1-WL. We provide simple implementation of NC-GNN that is proved to be as powerful as 1-WI- Compared to existing expressive GNNs, our NC-GNN is general, provably powerful and, more importantly, scalable framework.
multiset of multisets, in which each edge

---

Under review as a conference paper at ICLR 2023
The main question addressed in work is how to make best use of information in the one-hop neighborhood to improve expressive power while preserving scalability. In the one-hop neighborhood of each node, the local patterns we can consider are (A) what are the neighbors and (B) how the neighbors are connected to each other. The previous message passing GNNs only consider (A). We move a significant step forward to consider (B) by modeling edges among neighbors as a multiset of multisets, thereby leading to provably expressive power and preserved scalability. From this perspective, our method is fundamentally different from existing methods that encode triangle features, such as MotifNet (Monti et al., 2018) and SIGN (Rossi et al., 2020). Specifically, these methods employ triangle-relatee related motif-induced adjacency matrices in their convolution and diffusion operators, respectively. The edge weight in motif-induced adjacency matrix is obtained by multiplying the original edge weight with the frequency that each edge participates triangle motifs. Compared to this hand-crafted way, our method is general framework to encode how the neighhors are connected to each other, and the expressiveness of our framework can be rigorously characterized.
We perform experiments on graph classification and node classification to evaluate NC-GNN compre- hensively. Our NC-GNN consistently outperforms GIN, which as powerful as I-WL, by significant margins on various tasks. Remarkably, NC-GNN outperforms GIN by absolute margin over 12.0 on CLUSTER term of test accuracy. In addition, NC-GNN performs competitively, often achieves better results, compared existing expressive GNNs, while being much more efficient.
2 PRELIMINARIES
We start by introducing notations. We represent an undirected graph as 9 = EV, X), where V the set of nodes and E S V V denotes the set of edges. We represent an edge {v, u} E by (c. u) or (u, v) for simplicity. X = [æ1..... x.,l" E R is the node feature matrix, where the number of nodes and a, E IRd represents the d-dimensional feature of node v. N. = (u E VI(,,u) u) E E} is the set of neighboring nodes of node v. A multiset is denoted as Hf K....). }} and formally defined as follows.
n = |V|
Definition 1 (Multiset). A multiset is generalized concept of set allowing repeating elements. A multiset X can be formally represented by a 2-tuple as X = (5x. mx). where Sx is the underlying set formed by the distinct elements in the multiset and mxx Sx + Z gives the multiplicity (i.e., the number of occurrences) of the elements. the elements in the multiset are generally drawn from set X (i.e,, Sx S X), then X is the universe of X and we denote it X C X for ease of notation.
Message passing GNNs. Modern GNNs usually follow a message passing scheme to learn node representations in graphs (Gilmer et al., 20. To be specific, the representation of each node is updated iteratively by aggregating the multiset of representations formed by its neighbors. In general, the E-th layer of message passing GNN can be expressed as
! = f aagreegae (9) (((h! E.E....
(.) = fupdate (2) (n. .a.".
(I)
aggregate (C) and Supaate are the parameterized functions of the l-th layer. h is the representation of node v at the l-th layer and ( can be initialized as E.. After employing L such layers, the final representation 1e!") can be used for prediction tasks each node v. For graph-level problems,
graph representation he can be obtained by applying a readout function as,
hg f reatoou (H |v E vT).
(2)
Definition 2 (Isomorphism). Two graphs 9
(V, E, X) and H (,, are isomorphic, denoted as G ~ H. if there exists a bijective mapping 9 V + P such that x. Dg(e), Vu E V and (v. u) E E iff ((()),g())) E F. Graph isomorphism is still an open problem without a known polynomial-tims solution.
Weisfeiler-Lehhmall algorithm. The Weisfeiler- algorithm (Weisfeiler & Lehman, 1968) provides a hierarchy for graph isomorphism testing problem. Its I-dimensional form (a.k.a,, 1-WL or color refinement) is heuristic method that can efficiently distinguish a broad class of non-isomorphic
graphs (Babai & Kucera, 1979). 1-WL assigns color e to each node according its initial label
2

---

Under review as a conference paper at ICLR 2023
(8)
vs.
vS.
1-WL
HASI ,
NC-1-WL
HASe
(b)
(o, Hf }
HASa
|f
D, fiff
333
Figure 1: (a) Several example pairs of non-isomorphic graphs, partially adapted from Sato (2020), that cannot be distinguished by I-WL. Colors represent initial node labels or features. Our NC-1-WL can distinguish them. (b) A comparison between the executions of 1-WL and NC-1-WL on two non-isomorphic graphs.
(or feature)' and then iteratively refines the colors until convergence. Convergence means that the subsets of nodes with the same colors can not be further split different color groups. particular, at each iteration E, it aggregates the colors of nodes and their neighborhoods, which are represented as multisets, and hashes the aggregated results into unique new colors (i.e., injectively). Formally,
E HASH ch (8-1), Hf (f 1/u N.
(3)
1-WL. decides two graphs to be non-isomorphic once the colorings between these two graphs differ some iteration. Instead of coloring each node, k-WL generalizes 1-WL by coloring each k-tuple of nodes and thus needs to refine the colors for n tuples. The details of k-WL are provided in Algorithm Appendix A.2. is known that 1-WL is as powerful 2-WL in terms of distinguishing non-isomorphic graphs (Cai et al., 1992; Grohe & Otto, 2015; Grohe, 2017). Moreover, for le 2 2, (k + 1L is strictly more powerful than &- 3L (Grohe Otto, 2015). More details of the WL algorithms are given in Cai et al. (1992); Grohe (2017); Sato (2020); Morris et al. (2021).
Given the similarity between message passing GNNs 1-WL. algorithm (i.e. Eq. (1) vs. Eq. (3)), message passing GNNs can be viewed as differentiable neural version of 1-WI. In fact, it has been shown that message passing GNNs are at most as powerful as 1-WL in distinguishing non-isomorphic graphs (Xu et al., 2019; Morris et al., 2019). Further, Xu et al. (2019) proves that message passing GNNs can achieve the same expressiveness as I-WL the aggregate, update, and readout functions injective, thereby developing the GIN model (Xu et al., 2019). Thus. the expressive power of message passing GÑNs is upper bounded by 1- WL. In other words, two non-isomorphic graphs cannot be distinguished by 1-WI, then message passing GNNs must yield the for them. Importantly, such expressive power is not sufficient to distinguish some common graphs and cannot capture certain basic structural information such as triangles (Chen al., 2020; Arvind et al., 2020), which play significant roles in certain tasks, such as tasks over social networks. Several examples that cannot distinguished by 1-WL or message passing GNNs are shown in Figure I (a).
embedding
3 THE NC-I-WL AL.GORITHM
In this section, we introduce the proposed NC-I-WL algorithm, which extends the 1-WL algorithm by taking the edges among neighbors into consideration. With such simple but non-trivial extension. NC-1-WL is proved to be strictly more powerful than 1-WL and less powerful than 3-WL, while preserving the efficiency of 1-WL.
II' there "There are two families of WL algorithms; they are k-WL and k-FWL (Folklore WL). They both consider coloring k-tuples and their difference lies in how to aggregate colors from neighboring k-tuples It is known that (k: FW- is as powerful as k-WL for & 2 (Grohe & Otto, 2015; Grohe, 2017; Maron al., 2019). To avoid ambiguity, in this work, only involve k-
initial features labels, 1-WL assigns the color to all the nodes in the graph.

---

gives the Under review as a conference paper at ICLR 2023
Algorithm 1 NC-1-WL 1-WL for graph isomorphism test
Input: Two graphs G = (V, E, X) and = (P...))
HASH( Vu E
- HASH(y)), Vp
repeat (6=1,22 1,2,, ...
if (fe: 1:c0-110
| E VB + f(dk-1)/
1p e P]] then
return 9 z2
end if
for V do
(1) - HASH @ (f-1) (fco-11/ E ([((oor)) (t-1) ,0z M un, u2 E Nos (u1, E E}]
end for
for p P do
d - HASH de-") ((dd Np)),, (lldd dgg d "Mn, 92 E EN,, (2n 92) F))
end for until convergence return G H.
As shown in Eq. (3) and (1), 1-WL and message passing GNNs consider neighbors of each node as a multiset of representations. Here, we move one step forward by further treating edges among neighbors as multiset, where each element is also multiset corresponding to edge. We formally define a multiset of multisets as follows.
Definition 3 (Multiset of multisets). A multiset of multisets, denoted by W, is multiset where each element also a multiset. In this work, we only need to consider that each element W is multiset formed by 2 elements. Following our definition of multiset, if these elements are generally drawn from a set X, the universe of W is the set W = [f(wi, w2 Hum, w2 E X).. We can formally represent W (Sw, mw), where the underlying set Sw S W and mw Sw multiplicity. Similarly, we have W C W.
Particularly, our NC-1-WL considers modeling edges among neighbors as multiset of multisets and extends 1-WL (i.e., Eq. (3)) to
HASH c (L-1), (lolf-)) N.
[[l()) 1), (0-1) Hun, u2 E No, (ui, u2) E E}}
mulliset of multisets
(4)
As I-WL, our NC-I-WL determines two graphs to be non-isomorphic as long as the colorings of these two graphs are different at some iteration. We summarize the overall process of NC-1-WL in Algorithm 1, where the difference with 1-WL is underlined.
Importantly, NC-1-WL is more powerful than 1-WL in distinguishing non- non-isomorphic graphs. Several examples that cannot be distinguished by 1-WL are shown in Figure I (a). Our NCL distinguish them easily. An example of executions is demonstrated in Figure (b). We rigorously characterize the expressiveness of NC-1-WL by the following theorems. The proofs are given in Appendix A.I and A.2.
Theorem 1. NC-I-WL is strictly more powerful than 1-WL in distinguishing non-isomorphic graphs.
Theorem 2. NC-I-WL is strictly less powerful than 3-WL in distinguishing non-isomorphic graphs.
Although NC-1-WL less powerful than 3- 3-W,, it is much more efficient. 3-WL has to refine the color of each 3-tuple, resulting in n² refinement steps in each iteration. In contrast, 1-WL, NC-1-WL only needs to color each node, which corresponds to n refinement steps in each iteration. Thus, the superiority of NC-1-WL. lies in improving the expressiveness 1-WL, while being efficient as 1-WL.
Note that our NC-1-WL differs from the concept Subgraph-I-V (Zhao al., 2022), which ideally generalizes I-WL from mapping the neighborhood to mapping the subgraph rooted at each node. Specifically, the refinement step in Subgraph-1-WI. (!) HASH (G(N))), where G[N]]]
4

---

Under review as a conference paper at ICLR 2023
is the subgraph induced by the k-hop neighbors of node However, it requires an injective hash function for subgraphs, which is essentially as hard as the graph isomorphism problem and cannot be achieved. In contrast, our NC-1-WL does not aim injectively map the neighborhood subgraph. Instead, we enhance 1-WI. by mathematically modeling the edges among neighbors as a multiset of multisets. Then, injectively mapping such multiset of multisets in NC-1-WL is naturally satisfied.
4 THE NC-GNN FRAMEWORK
In this section, we propose the NC-GNN framework as differentiable neural version of NC-1- WL. Further, we establish an instance of NC-GNN that is provably as powerful as NC-1-WL in distinguishing non-isomorphic graphs.
Differing from previous message passing GNNs as Eq. (I), NC-GNN further considers the edges among neighbors as NC-1-WL. One layer of the NC-GNN framework can be formulated as
(9)
(1-1 Bug, u2 E NN. (u1, u2) E EH):
commuumictee
S Iugregstee
(c) ((n((-1/ue E
(5)
h fupdate
(8) ( )
communnicate (8) is the parameterized function operating on multisets of multisets. The following theorem establishes the conditions under which our NC-GNN can be as powerful as NC-1-WL.
Theorem 3. Let M 9 - TRd be an NC-GNN model with a sufficient number of layers following Eq. (5). M is as powerful NC-1-WL in distinguishing non-isomorphic graphs if the following conditions hold: At each layer f, f commmnicatee (2), faggregate (e), and f update (8) are injective. (2) The final readout function f readona is injective.
The proof is provided in Appendix A.3. One may wonder what advantages NC-GNN has over NC-1- WL. Note that NC-1-WL only yields different colors to distinguish nodes according their neighbors and edges among neighbors. These colors, however, do not represent any similarity information and are essentially one-hot encodings. In contrast, NC-GNN, a neural generalization of NC-1-WL, aims at representing nodes in the embedding space. Thus, an NC-GNN model satisfying Theorem 3 can not only distinguish nodes according to their neighbors and edges among neighbors, but also learn to map nodes with certain structural similarities to similar embeddings, based on the supervision from the on-hand task. This has the same philosophy as the relationship between message passing GNN and 1-WL (Xu et al., 2019).
There could exist many ways to implement the communicate, aggregate, and update functions in the NC-GNN framework. Here, following the NC-GNN framework, we provide simple architecture, that provably satisfies Theorem and thus has the same expressive power as NC-1-WL. To achieve this, we generalize the prior results of parameterizing universal functions over sets (Zaheer et al., 2017) and multisets (Xu et al., 2019) to consider both multisets and multisets of multisets. Such non- trivial generalization is formalized in the following lemmas. The proofs are available in Appendix A.4 and A.5. As Xu et al. (2019), we assume that the node feature space is countable.
Lemma 4. Assume X is countable. There exist two functions Si and f2 so that 1((,, W)
ExEx Jr (x) + (ww (w1) + fi (122) is unique for any distinct pair of (X, W), where X C X is multiset with a bounded cardinality and W C = W- =(ll- w2 w23i HWi, W2 E X3 a multiset of multisets with a bounded cardinality. Moreover, any function g on (X, W) can
be decomposed as g(X, ((X,W)) = (Exex f1(x) + EHirr J2(Ji(u1) + f((w)))) for some function d.
Lemma 5. Assume X is countable. There exist two functions fi and fa so that for infinitely many choices of e, including all irrational numbers, hic, X,, W) = (1 (c) + ExEx f1(2) E Monye fz(fi(w) (w:)= + fi (w2)) is unique for any distinct 3-tuple of (c, (c,X,, W), where c E X. X C X is a multiset with a bounded cardinality, and W C W [([w], w2 [1 Wy E X3 is a multiset of multisets with bounded cardinality. Moreover, any function g on (c, X, W) can be decomposed as g(c, X, W) = + (1+c) E E wxwe f2(fi (wi) )) f f(w2)) for some function sp
5

---

Under review as a conference paper at ICLR 2023
Table 1: Comparison of expressive GNNs. d is the maximum degree of nodes. T is the number of triangles in the graph. t is the maximum #MessageNc of nodes. is the maximum number of nodes in the neighborhood subgraphs, which grows exponentially with the subgraph depth. It unknown how the expressiveness upper bound of Nested GNN compares to 3-WL
Method
Memory
Time
Expressiveness upper bound
Scale to large graphs
GIN
O(n)
(ndd)
1-WL
1-2-3-GNN
O(n
O(n))
1-WL 3-WL 3-WL.
PPGN
O(n²)
((a))
Nested GNN
((n))
((nds)
I-WL ~ Unknown
NC-GNN (ours) On + min(m, 3T))
O(n(d +
1-WL ~ 3-WL
/
As Xu et al. (2019), can use multi-layer perceptrons (MLPs) to model and learn fi, ʃ2, and yp in Lemma 5, since MLPs are universal approximators (Hornik et al., 1989; Hornik, 1991). To be specific, we
MLP to model the compositional function f( (f++1) (p(() and another MLP to model //²) for l = 1, I.. At the first layer, we do not need f(()) the input features are one-hot encodings, since there exists function 12 that can preserve the injectivity (See Appendix A.5 for details). Overall, one layer of our architecture can be formulated as
h MIP ((1 + +e 1 (0) (1-11
Σ h
(c-1)+
Σ BI, (W1,82)E
MIP
( (h(t-1) 2
((-11)) 12
(6)
WEN,
The difference with GIN
where e(t) is learnable scalar parameter. According to Lemma 5 and Theorem 3, this simple architecture, plus an injective readout function, has the same expressive power as NC-1-WL. Note that this architecture follows the GIN model (Xu et al., 2019) closely. The fundamental difference between our model and GIN is highlighted in Eq. (6), which is also our key contribution. Note that graph, the third term in Eq. (6) will be zero for all nodes, and the model will reduce to the GIN model.
there does not exist any edges among neighbors for all nodes
Complexity. Suppose a graph has n nodes and m edges. Message passing GNNs, such as GIN, require (n) memory and have O(nd) time complexity, where is the maximum degree of nodes. For each node, we define #Message as the number of edges existing among neighbors of the node, An NC-GNN model as Eq (6) has O(n(d + t)) time complexity. where t denotes the maximum #MessageNc of nodes. Suppose there are totally T triangles in the graph, in addition to n node representations, we need to further store 37 representations can alternatively store (hu. + h2,)) for each edge (u1, U2) E E. Thus, the memory complexity is On + min (m, 3T').. Hence, compared to message passing GNNs, our NC-GNI has bounded memory increasement and preserves the linear time complexity with a constant factor. We compare with several existing expressive GNNs in Table 1. Our NC-GNN has much better scalability. More discussions with related works are in Section 5.
the input of MLP2- If 3T > m, we
RELATED WORK
The most straightforward idea to enhance the expressiveness of message passing GNNs is to mimic the k- GL (k > 3) algorithms (Morris et al., 2019; 2020b; Maron et al., 2019; Chen et al., 2019). For example, Morris et al. (2019) proposes 1-2-3-GNN according the set-based 3-WL, which is more powerful than I-WL. and less powerful than the tuple-based 3-WI.. It requires O memory since representations corresponding to all sets of 3 nodes needs be stored. Moreover, without considering the sparsity of the graph. it has (n²) time complexity since each set aggregates messages from neighboring sets. Maron et al. (2019) develops PPGN based on high order invariant GNNs (Maron et al., 2018) 8) and 2-FWL, which has the same power as 3-WL. Thereby, PPGN achieves the same power as 3- with (n²) memory and Onn²) time complexity. Nonetheless, the computational and memory cost of these expressive models are still too high to scale to large graphs
Another line of research for improving GNNs is to exploit subgraph information (Frasca et al., 2022). Bodnar et al. (2021b;a) perform message passing high-order substructures of graphs, such

---

Under review as a conference paper at ICLR 2023
as simplicial and cellular complexes. Its preprocessing and message passing step are computationally expensive. Also, domain knowledge is usually required to predefine the substructure bank, while is often unavailable in general tasks. GraphSNN (Wijesinghe & Wang, 2022) defines the overlaps between the subgraphs of each node and its neighbors, and then incorporates such overlap information into message passing scheme by using handcrafted structural coefficients. ESAN (Bevilaequa et al., 2022) employs an equivariant framework to learn from a bag of subgraphs of the graph and further proposes a subgraph selection strategy to reduce the high computational cost. Zeng et al. (2021); Sandfelder et al. (2021); Zhang & Li (2021); Zhao et al. (2022) apply GNNs to the neighborhood subgraph of each node. For example, Nested GNN (Zhang Li, 2021) first applies a base GNN to encode the neighborhood subgraph information of each node and then employs another GNN on the subgraph-encoder representations. Since message passing is performed on n neighborhood subgraphs, the memory complexity is (nn)) and the time complexity is ((dds), where is the maximum number of nodes in a neighborhood subgraph. Note that 8 grows exponentially with the depths of the neighborhood subgraph, thus limiting the scalability. The recently proposed KP- GNN (Feng et al., 2022) focuses on formulating the K-hop message passing framework and analyzing its expressive power. In contrast, we dedicate to the consideration of edges among neighbors, leading to the powerful and efficient NC-1-WL and NC-GNN with a different proof of expressivity.
Due to the high memory and time complexity, most of the above methods usually evaluated on graph-level tasks over small graphs, such as molecular graphs, and can be hardly applied to large graphs like social networks. Compared to these works, our approach differs fundamentally by proposing a general (i.e., without ad hoc features) and provably powerful GNN framework, while preserving the scalability in terms of computational time and memory requirement. We compare our NC-GNN with several existing expressive GNNs in Table 1.
There are several other heuristic methods proposed to strengthen GNNs by adding identity aware information (Murphy et al., 2019; Vignac et al., 2020; You et al.. 2021), random features (Abboud et al., 2021; Dasoulas et al., 2021; Sato et al., 2021), predefined structural features (Li et al., 2020; Bouritsas et al., 2022) to nodes, or randomly drop node (Papp et al., 2021). Another direction is to improve GNNs in terms of the generalization ability (Puny et al., 2020). These works improve GNNs from perspectives orthogonal to ours, and thus could be used techniques to further augment our NC-GNN. In addition, PNA (Corso et al., 2020) applies multiple aggregators to enhance the GNN performance. Most recently, Morris et al. (2022) proposes new hierarchy, which is more fine-graines than the WL hierarchy, for graph isomorphism problem. For deeper understanding of expressive GNNs, we recommend referring to the recent surveys (Sato, 2020; Morris et al., 2021; Jegelka, 2022).
6 EXPERIMENTS
In this section, we perform extensive experiments to evaluate the effectiveness of the proposed NC-GNN model on real benchmarks. In particular, consider widely used datasets from TU- Datasets (Morris et al., 2020a). Open Graph Benchmark (OGB) (Hu et al., 2020), and GNN Bench- mark (Dwivedi et al., 2020). These datasets are from various domains and cover different tasks over graphs, including graph classification and node classification. Thus, they can provide a comprehensive evaluation of our method. Note that certain datasets, such as REDDIT-BINARE and ogbg-molhiv, do not have many edges among neighbors (i.e., Avg. #MessageNc < 0.2). In this case, our NC-GNN model will almost reduce to the GIN model and thus perform nearly the same as GIN. Hence, we omit such datasets in our results. All the used datasets and their statistics, including Avg. #Messagene- are summarized in Table 7, Appendix B. Our implementation based on the PyG library (Fey & I Lenssen, 2019). The detailed model configurations and training hyperparameters of NC-GNN on each dataset are summarized in Table 8, Appendix B.2.
Baselines. As shown in Eq. (6). the fundamental difference between our NC-GNN model and GIN is that we further consider modeling edges among neighbors, as highlighted in Eq. (6). Hence, compar- ing to GIN can directly demonstrate the effectiveness of including such information in our NC-GNN, which is the core contribution of our theoretical result. Therefore, in the following experimental results, we highlight our results if they are better than GIN, and analyze the improvements over GIN. We also consider the WL subtree kernel (Shervashidze et al., 2011) and several typical message passing GNNs as baseline; those are DCNN (Atwood & Towsley, 2016), DGCNN (Zhang et al.,
7

---

Under review as a conference paper at ICLR 2023
Table Results (%) on TUDatasets. The top three results on each dataset are highlighted as first,
second, and third, We also highlight the cells of NC-GNN results if they are better than GIN.
Dataset
WL subtree
DCNN
DGCNN
GIN
PPGN
SIN
CIN
GNN-AK
GraphSNN
NC-GNN (ours)
IMDB-B
73.8+9.9
19.1+1.4
70.0+0.9
75.1-6.1
73.0a5.
75.6
75.6+87
75.0+4.
77.9=a.
75.2=4.5
IMDB-M
50.911.
33.511.4
47.8:0.9
52.3-2a
50.5aam
52.5.a0
52.7.81
NIA
N/A
52.5+3.
COLLAB
78.9+19
52.1+0.7
73.8+0.5
80.2-19
81,414
N/A
N/A
NIA
N/A
82.5=12
PROTEINS
75.0133
61.3116
75.5.n.
76.2.28
77.2
76.5a34
77.0
77.1g3
76.8125
76.5:44
2018), GCN (Kipf& & Welling, 2017), and GraphSAGE (Hamilton al., 2017). In addition, further include the following recent methods that improve GNN expressiveness as baselines. Specifically, SIN (Bodnar al., 2021b). CIN (Bodnar al., 2021a), GNN-AK (Zhao et al., 2022), GraphSNN (Wi- jesinghe & Wang. 2022) improve the expressive power of GNNs by using the subgraph information.
RingGNN (Chen et al., 2019) and PPGN (Maron al., 2019) are models based on 3-WL.
TUDataset.. Following GIN (Xu et al., 2019), we first conduct experiments on four graph classifi- cation datasets from TUDatasets (Morris al., 2020a); those are COLLAB, and PROTEINS. Note that we omit other datasets used by GIN since they do not have many edges among neighbors. We employ the same number of layers as GIN. We report the 10-fold cross validation accuracy following the protocol as (Xu et al., 2019) for fair comparison. The results of baselines are directly obtained from the literature.
As presented in Table 2, we can observe that our NC-GNN outperforms GIN on all datasets con- sistently. Moreover, NC-GNN performs competitively with other methods aiming at improving the GNN expressiveness. The consistent improvements over GIN can show that modeling edges among neighbors in NC-GNN is practically effective. Notably, NC-GNN achieves an obvious improvement margin of 2.3 on COLLAB. This is intuitively reasonable since the Avg. #MessageNc COLLAB is much larger than other datasets, as provided in Table 7, Appendix B. In this case, NC-GNN can use such informative edges existing among neighbors to boost the performance.
Open Graph Benchmark. We also perform experiments on the large-scale dataset ogbg-ppa (Hu al., 2020), which has over 150K graphs and known more convincing testbed. The graphs in ogbg-ppa are extracted from the protein-proter protein association networks of different species. It formulates graph classification task and the data are split based on species. Differing from TUDatasets, the graphs in ogbg-ppa have edge features representing the type of protein-protein association. In order to apply NC-GNN to these graphs, we further define a variant of our NC-GNN by incorporating edge features into the NC-GNN framework, inspired by the GIN model with edge features introduced by Hu et al. (2019). The details of the resulting model is given in Appendix B.3.
Since we have one more MLP than GIN at each layer, one may wonder if our improvements are brought by the larger number of learnable parameters, instead of our claimed expressiveness. Thus, here compare with GIN under the same parameter budget. Specifically, we the same number of layers as GIN to ensure the same receptive field, and tune the hidden dimension to obtain an NC-GNN model that has the similar number of learnable parameters as GIN. Following (Hu et al., 2020), we compare the best validation accuracy and the test accuracy at the best validation epoch. We also include the training accuracy at the best validation epoch for reference. Results over 10 random runs are reported. The results of GIN are obtained from the official benchmark leaderboard.
As reported in Table 3, NC-GNN consistently achieves better results in terms of validation accuracy and test accuracy. Specifically, our NC-GNN model outperforms GIN on the test set by an obvious absolute margin of 3.02. Note that the only difference between NC-GNN and GIN is that edges among neighbors modeled and considered in NC-GNN. Thus, the obvious improvements over GIN can demonstrate the practical effectiveness of incorporating such information. Therefore, combining with the previous experiments TUDatasets, we can conclude that our NC-GNN not only has theoretically provable expressiveness, but also achieves good empirical performance real-world tasks.
Table 3: Results (%) on ogbg-ppo -pe. All models this table consider edge features. We highlight the cells of NC-GNN results if they are better than GIN.
Model
Param
Training Acc.
Validation Acc.
Test Acc.
GIN
1836942
97.55+0.ta
65.62-1.07 07
68.92=1.4
NC-GNN (ours)
1754445
99.37...16
66.82 0.67
71.94_0 0.
8

---

Under review as a conference paper at ICLR 2023
GNN Benchmark. In addition to graph classification tasks, we further experiment with node classification tasks on two datasets, PATTERN and CLUSTER, from GNN Benchmark (Dwivedi et al., 2020). PATTERN and CLUSTER respectively contain 14K and 12K graphs generated from Stochastic Block Models (Abbe, 2017), a widely used mathematical modeling method for studying communities in social networks. The tasks these two datasets it to classify nodes in each graph. To be specific, on PATTERN, the goal is to determine if a node belongs to specific predetermined subgraph patterns. On CLUSTER, we aim at categorizing each node to its belonging community. The details of the construction of these datasets are available in (Dwivedi et al., 2020).
We compare with typical message passing GNNs, including GIN, and two methods that mimic 3- 3-WL; those are PPGN and RingGNN. To ensure fair comparison, we follow Dwivedi et al. (2020) to compare different methods under two budgets of learnable parameters, 100K and 500K, by tuning the number of layers and the hidden dimensions. Average results over 4 random runs are reported in Table 4, where the results of baselines are obtained from (Dwivedi al., 2020). On each dataset, we also present the absolute improvement margin of our NC-GNN over GIN, denoted as A by comparing their corresponding best result.
We observe that our NC-GNN obtains significant improvements over GIN. To be specific, NC-GNN remarkably out- performs GIN by an absolute margin of 1.142 and 12.002 on PATTERN and CLUSTER, respectively. This further strongly demonstrates the effective- ness of modeling the information of edges among neighbors, which aligns with our theoretical results. Notably, NC-GNN obtains outstanding perfor- mance on CLUSTER. Since the task on CLUSTER is to identify commu- nities, we reasonably conjecture that considering which neighbors are con- nected is essential for inferring com- munities. Thus, we believe that our NC-GNN can be strong basic method for tasks over social network graphs.
Table 4: Results (%) on GNN Benchmark. The top three results on each dataset are highlighted as first, second, and third. We also highlight the cells of NC-GNN results if they are better than GIN.
PATTERN
CLUSTER
Model
Layers
Param
Acc.
Parum
Test Acc.
GCN
4
100921
85.498.1c.om c0.045
101655
47.828 1
5001621
85.614#0.012
501687
69.026e1.972
GraphSAGE
4
101739
60.51661c.00
102187
50.45410.15
16
502842
50. 50.492
503350
:3.841:0.110
GIN
100884
85.500 u..
103544
508574 16
85.387 1.0
517570
64.716:1.888
RingGNN
105206
86.245
104746
22.000
2
501766
86 86,211+0.00 025
52/2022
22. 3 10000000
505749
Diverged
514380
Diverged
PPGN
103572
85, 85.661+ $0.5
105552
57. 67.130
3
502872
85 86.341+0.00 207
507252
G5. 1o.48977.00
581716
Diverged
386788
Diverged
NC-GNN (ours)
4
106756
86.627 20.777
107320
63.335
506512
86.732+0..
508-128
69.83840.08
16
506512
86.607 20.107700.110
308-128
76.718eaum
A (over GIN)
1.142
12,002
Moreover, NC-GNN achieves much better empirical performance than RingGNN and PPGN, although they theoretically mimic 3-WL. It is observed that these 3-WL based methods are difficult to train and thus having fluctuating performance (Dwivedi et al., 2020). In contrast, our NC-GNN is easier to train since it preserves the locality of message passing, thereby being more practically effective.
Time analysis. In
Table 5: Comparison of real training time.
Table 5, we compare the real training time
dataset Aug. #Messagose
IMDB-B
PATTERN 3440.1
CLUSTER 1301.5
50.5
of models with 100K
Model
Apc.
Timelepoch
Acc.
Timelepoch
Acc.
Timelepach
learnable parame- ters on IMDB-B. PATTERN,
GIN
75.1
1.075s
55.500.m.o0
7.431s
58.00 58.384.0222
6.180s
PPGN
73.0
4 4.580s
65.661 20
147.063<
57.
130
144. 106s
NC.GNN (ouns)
75.2
1.252s
36.627.0.00
44.882s
10
28.505s
and
CLUSTER. We can observe that our NC-GNN is much more efficient than PPGN, since our NC-GNN preserves the linear time complexity w.r. number of nodes as GIN, according to the analysis in Table 1. Compared GIN, the increasement of the real running time of our NC-GNN depends on the number of edges among neighbors. For example, the time consumption of NC-GNN is similar to GIN on IMDB-B, since the Avg. #MessageNc is considerably smaller than that in PATTERN and CLUSTER. Overall, our NC-GNN is shown to be more powerful than GIN theoretically and empirically, while maintaining the scalability with reasonable overhead.
Thorough comparison with subgraph GNNs. We further perform a comprehensive empirical comparison with subgraph GNNs. Specifically, we compare to GIN-AK (Zhao et al., 2022), a representative method in the subgraph GNN family, on test accuracy, training time per epoch, total training time for convergence, GPU memory usage, MACS, and inference time. For each experiment,
9

---

Under review as a conference paper at ICLR 2023
Table 6: The thorough comparison between NCGNN and GIN-AK on PATTERN and CLUSTER.
Datasets
Methods
Layers
# Param
Test Acc.
Timelepoch'
Total Time!
GPU Memory"
MACS
Inference Time
PATTERN
GIN-AK+
001 134
86.86 2007
77.500s
0.667h
3143JMB
176.445G
32.1884
NC-GNN (ouns)
652274
42.517%
0.555)
15625MB
1.142i
12,05:
CLUSTER
GIN-AK'
002588
70. n.
148.9831 1839
1.1206
521
110.518G
27. 27.163s
NC-GNN (ouns)
10
562948
76.992.2001
48,869s
0.679%
22386MB
0.841G
5.1763:
we run it four times and report the average results for test accuracy, training time per epoch, total time consumed to achieve the best epoch, and GPU memory consumption while keeping the same batch size. In order to compare the computational cost, FLOPP is commonly used as the number of floating operations for the model & Le, 2019). Here use a similar metric MACS to operations for each graph in the test set. Note that each
calculate the average multiply-accumulle multiply-accumull operation includes two float operations. The results are summarized in Table 6. Our NC-GNN achieves competitive accuracies as GIN-AK", while being more efficient in training, including training time per epoch and total training time. In addition, we use less GPU memory since we do not have to consider updating node representations for all the nodes in the expanded subgraphs as GIN-AK More importantly, the MACS overhead of GIN-AK is 100x more than our NC-GNN. Since our NC-GNN calculates each node representation from the original graph instead of the expanded subgraphs, it can save huge MACS overhead during the forward procedure. To further show the advantage of fewer MACS overhead, we provide the inference time comparison and our NC-GNN takes less time during inference. Overall, NC-GNN reaches a sweet spot between expressivity and scalability, from both theoretical and practical observations.
CONCLUSIONS AND OUTLOOKS
In this work, based on our proposed NC-1-WL, we present NC-GNN, a general, provably powerful, and scalable framework for graph representation learning. In addition to the theoretical expressive- ness, we empirically demonstrate that NC-GNN achieves outstanding performance on various real benchmarks. Thus, we anticipate that NC-GNN will become important base model for learning from graphs, especially social network graphs. To further improve the expressiveness of NC-GNN, in future work, we may consider how to effectively and efficiently model the interactions between two edges that exist among neighbors.
REFERENCES
Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):6446 65316665312222 2017.
Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In IJCAI, 2021.
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On weisfeiler-leman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sciences, 1 113:42-59) 09.42259.00 2020.
James Atwood and Don Towsley. Diffusion-convolutionaal neural networks. Advances in neural information processing systems, 29, 2016.
László Babai and Ludik Kucera. Canonical labelling of graphs in linear average time. In 20th Anmual Symposium Foundations of Computer Science (sfes 1979), pp. 39 46. IEEE, 1979.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2022.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. Advances in Neural Information Processing Systemx, 34:2625-2644 2021a.
10

---

Under review as a conference paper at ICLR 2023
Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montufar, Pietro Lio, and Michael Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. In International Conference on Machine Learning, pp. 1026-1037, PMLR, 2021b.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou,, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions Puttern Analysis and Machine Intelligence, 2022.
Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 32, 2019.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 33:10383-10395 2020.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liö, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances Neural Information Processing Systems, 33:13260-1322 13271, 2020.
George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pp. 2132,2132, 2021.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982 2020.
Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang. How powerful are k-hop message passing graph neural networks. Advances in Neural Information Processing Systems, 2022.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with Py Geometric. In ICLR Workshop Representation Learning on Graphs and Manifolds, 2019.
Fabrizio Frasca, Beatrice Bevilacqua, Michael M Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. Advances in Neural Information Processing Systems, 2022.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th international conference on machine learning. pp. 1263-1272. 2017.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume pp. 729-734. IEFF, 2005.
Martin Grohe. Descriptive complexity, canonisation, and definable graph structure theory, volume 47, Cambridge University Press, 2017.
Martin Grohe and Martin Otto. Pebble games and linear equations. The Journal of Symbolic Logic, 80(3):797-844, 2015.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems. pp. 1024-1034, 2017.
Kurt Horiik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2): 251-2571 1991.
Kurt Homik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359-366, 1989.

---

Under review as a conference paper at ICLR 2023
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In International Conference on Learning Representations, 2019.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in Neural Information Processing Systems, 2020.
Stefanie Jegelka. Theory of graph neural networks: Representation and learning. arXiv preprint arXiv:2204.07697, 2022.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465-44777 2020.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations, 2016.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representutions, 2018.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
Federico Monti, Karl Otness, and Michael M Bronstein. Motifnet: a motif-based graph convolutional network for directed graphs. In 2018 IEEE Data Science Workshop (DSW), pp. 225-228. IEEE, 2018.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference artificial intelligence, volume 33, pp. 4602-4609, 2019.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020a. URL www. www.grraplleaiiinn io.
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Advances in Neural Information Processing Systems, 33: 21824-21840, 2020b.
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. arXiv preprint arXiv:21 12.0999,,, 2021.
Christopher Morris, Gaurav Rattan, Sandra Kiefer, and Siamak Ravanbakhsh. Speqnets: Sparsity- aware permutation equivvrrann graph networks. arXiv preprint arXiv:2203.13913, 2022.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pp. 4663-4673, PMLR, 2019.
Pál András Papp. Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. DropGNN: random dropouts increase the expressiveness of graph neural networks. Advances in Neural Information Processing Systems, 21221199722009 2021.
Omri Puny, Heli Ben-Hamu, and Yaron Lipman. Global attention improves graph networks general- ization. arXiv preprint arXiv:2006.077 078406 2020.
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004. // 2020.
12

---

Under review as a conference paper at ICLR 2023
Dylan Sandfelder, Priyesh Vijayan, and William L Hamilton. Ego-gnns: Exploiting ego structures in graph neural networks. In ICASSP 2021-2021 IEEE Interaational Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8523-8521 IEEE, 2021.
Ryoma Sato. survey on the expressive power of graph neural networks. arXiv preprint arXiv:2003.04079, 2020.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 333-341. SIAM, 2021.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mchlhorn, and Karsten M Borgwardt. Weisfeiler-lemman graph kernels. Journal of Machine Learning Research, 12(9). 2011.
Mingxing Tan and Quoe Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In International conference machine learning, pp. 6105-61 14. PMLR, 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representation, 2018.
Clement Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-passing. Advances in Neural Information Processing Systems, 33: 13:14441144155 2020.
Boris Weisfeiler and Andrei A Lehman. A reduction of a graph to canonical form and an algebra arising during this reduction. Mauchno-Technichessayy Informatsia, 2(9):12-16, 1968.
Asiri Wijesinghe and Qing Wang. A new perspective on" how graph neural networks go beyond weisfeiler-lehman?" In International Conference on Learning Representations, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural
networks? In International Conference on Learning Representations, 2019.
Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10737-10745, 2021.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor Prasanna, Long Jin, and Ren Chen. Decoupling the depth and scope of graph neural networks. Advances in Neural Information Processing Systems, 34, 2021.
Muhan Zhang and Pan Li. Nested graph neural networks. Advances in Neural Information Processing Systems, 34, 2021.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. In International Conference on Learning Representations, 2022.
13

---

Under review as a conference paper at ICLR 2023
A PROOFS OF THEOREMS AND LEMMAS
A.1 PROOF OF THEOREM 1
Theorem 1. NC-I-WLik is strictly more powerful than 1-WL in distinguishing non-isomorphic graphs.
Proof. To prove that NC-1-WL is strictly more powerful than 1-WL, prove the correctness of the following two statements. (1) If two graphs are determined to be isomorphic by NC-I-WL, then they must be indistinguishable by 1-WL as well. (2) There exist at least two non-isomorphic graphs that cannot be distinguished by 1- ILL but can be distinguished by NC-1-WL.
(I) Assume two graphs G
EV, and H (P, Y) cannot be distinguished by NC-1-WL. Then, according to Algorithm I, at any iteration E = 1,2, we have
( HHch Hell-")/e e N.ND ffffccl"").
(ll-1))) lun, u2 E No. (u1, u2) EE [oev]]
ll
Cus
((d (dt-)) Hfd 10 Ig E Np (l dup
" Bla., 92 E EN (21. E F}] |p P]
This
naturally implies that,
any iteration
1,2,
have This
((((5-) Hel-"1/u E EN.B) [ev]] = {{(d) f(-1) al 19 e NgB)
10 | P]]
indicates that 1-WL cannot distinguish graph G and graph H as well.
(2) In Figure 1 (a), we provide several pairs as example to show that there exist such non-isomorphic graphs that can be distinguished by NC-I-WI. but cannot be distinguished by 1-WI..
A.2 PROOF OF THEOREM 2
Theorem 2. NC-/-WL. is strictly less powerful than 3-WL in distinguishing non-isomorphic graphs.
Proof. To prove that NC-1-WL is strictly less powerful than 3-WL, we prove the correctness of the following two statements. (1) If two graphs are determined to be isomorphic by 3-WL, then they must be indistinguishable by NC-1-WI. as well. (2) There exist at least non-isomorphic graphs that cannot be distinguished by NC-1 NC-1-WL but can be distinguished by 3-WL.
We first describe the details of kL in Algorithm 2, following Sato (2020). k- WL aims at coloring each k-tuple of nodes, denoted as E Vkk The i-th neighborhood of each tuple v = (V), U2 Uk) defined as No.; (VV), ............................... 14-1- 1, 8, 11+ uk)ss E V). Similarly, The i-th neighborhood of each tuple = (P1.Pz, ... Plk) is defined as N,.: (P1. PP-1, t. Ps+1, . PP)]tt P). The initial color of each tuple e determined by the isomorphic type of the subgraph induced by the tuple, i.e., [[v]. (See Sato (2020) for details). Note that the nodes in G[u] are ordered based on their orders in the tuple v. Thus, (ASH(G(w) = (P(p))(()) iff (a) Fe, = Up; for 1,2, & and (b) (vi, nz) E iff (p:, E F.
(1) Assume two graphs 9 = EV, X) and H = (P.F,Y) are determined to be isomorphic by E, 3-WL. G and H have the same number of nodes", denoted as n. Then, according to Algorithm 2, we have (fc(o) v E V*]] ((4 p p*]] There always exists an injective mapping g : V + P such that Co d00 (i.e., HASH(glo)) = HAsH(?[[(()]]) Vo E V Here, we directly apply g tuple v for ease of notation, which means g(v) = ((v1), 02, va)) (g(v1), ((2)), ((v)).. Without losing generality, we assume maps By to p, for j = 1,2, ... Then, we can obtain the following results.
(a) We can consider the tuples v = (15, E V. Given (0) = o(v)> we can derive
Fuy Up Vu, E V.
(b) We further consider the tuples v = (U), Uj, Ur), E V. According to (0) = d(0)
a(D)' we have
Ce. yp. We can also have Pr E NN, iff u, E No, (Otherwise, c00) * (0)
)
Tww graphs with different numbers of nodes can be easily distinguished by comparing the multisets of node colors, given that the cardinalities of the two multisets different.
14

---

Under review as a conference paper at ICLR 2023
Algorithm 2 k-WL for graph isomorphism test
Input: Two graphs G = (V, E; X) and H. = (P,E))
HASH(G ())) Vo E Vk
- HAs Vp E pk
repeat (6 (6=1, 1,2, )))
if ffco 1/c0-110 | VK + (i "/e P*] then
return 9 H
end if
for v
E V do
0s = (1ch--))
u E No, for = 1, ... ... ,
(E) t HASH (f-1) -..1. " Co.
end for
for p p do
d
ps (ad
q E Np.iel. for 1,2,
+ HASH de
( (0) d16 (1)
p.1 p,2
end for until convergence return G H
VS.
Figure 2: Two graphs, adapted from Sato (2020), that cannot be distinguished by NC-1-WL but can be distinguished by 3-WL.
(c) At last, we consider the tuples (Ug, Ur, Uw)), Vuy V. Similarly, based d (U) can obtain Zv, Ypp and Fe Yp... Also, we can have Pr. Pw E N2, iff Ur, Uia E Nays and (Pr,Po) E F iff (wr) E.
g(v)"
Var)
Now, we consider performing NC-I-WI. (Algorithm 1) on these two graphs = (V, X) and H = (P, F.Y to color each node v E V and p P. We have the same injective mapping g : + P as above. Based on (a), we have æ. = Vy(u)) Vo E V. which indicates (0)
d Vu V in the NC-1-WL coloring process. Similarly, according (b) and (c), have a(u)>
(e (0) 1 E N. = ((d,) e No Yo E V and (ff(co) (0) Juu uy E No. (u1, u2) E E}} 4 Bor. 92 No (1).)) E F}), Ve E V. respectively. Therefore, with initial colors satisfying such conditions, NC-1-WL cannot distinguish G and H since o (1-1) -du-1) Ve V
"s(")
(f 1/ VD = H(df-"1pp E PT] always holds always holds for 1,2. ... In other words, ffc! matter how many iterations (i.e., () we apply.
(2) In Figure 2, we provide two non-isomorphic graphs that can be distinguished by 3-WL. but cannot be distinguished by NC-1-WL. For these two graphs, NC-1-WL reduces to 1-WL since there does not exist any neighbors that are communicating.
A.3 PROOF OF THROREMS 3
Theorem 3. Let M: 9 Rdd be an NC-GNN model with a sufficient number of layers following Eq. (5). M is as powerful conditions hold: (1) At each layer E, communicaae
NC-I-WL in distinguishing non-isomorphic graphs if the following (t) (2), aagmegan (E), and upddate" (e) are injective. (2) The
final readout function J readon is injective.
15

---

Under review as a conference paper at ICLR 2023
Proof. We prove the theorem by showing that an NC-GNN model that satisfies the conditions can yield different embeddings for any two graphs that are determined to be non-isomorphie by NC-1-WL. We denote such model MM. Assume two graphs G = (Vi E1, X1) and 9/ E X2) are determined to be non-isomorphic by NC-1-WI. at iteration Given that fradont of M can injectively map different multisets of node features into different embeddings, we only need to demonstrate that M, with a sufficient number of layers, can map 91 and 22 to different multisets of node features.
To achieve this, following Xu al. (2019), we show that, for any iteration E, there always exists an injective function such that h = c(c))), where h is the node representation given by the model M and ci is the color produced by NC-1-WL. We will show this by induction. Note that here represents a general node that can be a node in G1 or G2.
Let Φ denote the injective hash function used in NC-1-WL. For é = O, we have de = ((z.) and h E.. Thus, ip could be Φ-1 for
Suppose there exists an injective function yp such that he 1) 1) = p(ce () Ve E V1 U V22 we show that there also exists such an injective function for iteration f. According to Eq. (5), we have
hg (6) f Sudaate (5) (n! (n(e-1), (e Ingeregae (6)
(Hh E NN.33)
f /communicate" (0) (H ((-"") un, u2 E No. Nu,, u2) E E})
According to h (f-1) = (((ol-1) we further have
h fupdate (6) (p(clt-))) Ingoreanc (0)
(Ho(ld--))e E NoHl).
(8)
(H1f p(clt--)) u1, u2 E No. (u1, u2) E E]})
f fcommunicaso"
where fcomuunicats" (6), faggregan (8), fupdane (9, and are all injective functions. Since the composition of injective functions also injective, there must exist some injective function s such that
h
(4 ((--"), Ml 1c IuE NGHH Hlldd"" cht
(t-1)) u1, u2 No, (u1, (u1, u2) E EB))
(9)
Then, can obtain
(0))) = &b (5-1)) (0 clt
(e--1) ((ale- N.H. Alldd"") " de-11) u1, U2 E (u,, U2) E E}]
= vb 3 cl
(10)
Then, 4 = 1b a o- 1 is an injective function such that 0 = p(c Vu e V1
Therefore, it is proved that for any iteration E, there always exists injective function &p such that h =p(cl)) Since NC-1-WL determines 91 and G2 to be non-isomorphic at iteration L, we have H1cl (D) lo E ViB + (1l lv E V2)). As proved above, we also have ((A!") |v E Vi
(D)
Ho(())) EV)). (1 V/} (((((c(")) v E V2]), and y injective. Hence, the multisets (1)) of node features produced by M for Gi and G2 are also different, ie.., ((he) | E ViJ * ((h V2 which indicates that the NC-GNN model M can also distinguish 91 and G2.
A.4 PROOF OF LEMMA 4
Lemma 4. Assume X is countable. There exist two functions Ji and J2 so that 1((X, W)
ExEx Jr (x) + EHmr WurrwwHew wewlew [2()( + (1(2)) is unique for any distinct pair of (X, W), where X C X is multiset with a bounded cardinality and W CW= =[lW,, (at0,,wa)i Myl, W2 E X} multiset of multisets with a bounded cardinality. Moreover, any function g on (X, W) can
be decomposed as g(X, W) <(Exx + EH fe(f(()) fi(2))) for some function d.
Proof. To prove this Lemma, we need the following fact, which is also used by Xu et al. (2019).
16

---

Under review as a conference paper at ICLR 2023
Fact 1. Assume X' is countable. h(x) = Σ xxx N N->(>) is unique for any multiset X S X' of bounded cardinality, where the mapping Z : + N is an injection from 2 E X' to natural numbers and N E I satisfies N > [X] for all X.
To prove the correctness of this fact, we show that X can be uniquely obtained from the value of h(X). Following the notations in our main texts, we formally denote X = (5x, mx), where Sx is the un- derlying set of X and mx Sx - Z gives the multiplicity of the elements in Sx- Hence, we need to uniquely determine the elements in Sx and their corresponding multiplicities, using the value of h()). Let {-1, T2, .. , J J denote the countable set X' (n could go infinitely). Without losing gener- ality, we assume Z maps 21 + 0, 22 + L, etc.. Then we can compute (q.r) h(X) divmod N N where q the quotient and r is the remainder. If q = O, we can conclude 21 is not in Sx. If > then 21 is in Sx and q gives the multiplicity of z1. Afterwards, we use the remainder r to replace h(X) and compute (g.r) h(X) divmod N and the results can be used infer if z2 is in Sx and its multiplicity. We can do this recursively until r O. Note that X has a bounded cardinality and N E I satisfies N > |X] for all X. Otherwise, Fact 1 will not hold. Here we provide an example to show the correctness of Fact 1. Let a multiset X = {[x11 T3, B and Z injectively maps the elements in X to natural numbers, thus obtaining a multiset 2,0,2,2), Let N = 4. We have ((X) =
E N ((a) N=Z(") = 4-0 + 4-2 4-2 = 9/8. Next, following our description above, we show how we can infer X by the value of (x).. First, according to 9/8 divmod 4-0 = (1, 1/8), we can conclude that there is one 21 in X. Then, with 1/8 divmod 4 = (0. 1/8), we can infer that 22 is not in X. Finally, we have 1/8 divmod 4-2 = (2, 0), which indicates that there are two I3 in X. We can stop the process since the remainder reaches 0.
Let us go back the proof of Lemma 4. Since X' is countable, W [(1 w2 waBBle wi, we E x) is also countable. Because both X and W have bounded cardinalities, we can find an number N e N such that N > max [ + (W],2) for all (X,W) pairs. Let Z1- X' + Nodd be an injection from x E X' to odd natural numbers. We consider fi N (z), For ease of notation, we let vi (iffer, w2ll) H1) = f1 (ww) + fi (w22). According to Fact 1, v (o(f(u (fw1.. w2 H1) is unique for any Hf ww w2]l E W. We define the set y = f W1, W2 [wz, Wy E X}. Thus, ) is also countable as W. We consider Z2 y + Newen be an injection from y E ) to even natural numbers and fo = NN=NN2a0 -22www) Then, the resulting (6XXWW)
ΣxEx fi()) ((m ([wI. fe (f is an injective function on (X, W). In other words, can uniquely determine (X, W) from the value of h(X, W). To be specific, from the value of h(X, W), we can infer the histograms of natural numbers as show in Fact 1. Then, we can uniquely obtain X (i.e., its underlying set S₂ and multiplicities.) based on the odd natural numbers. According to the even natural numbers, we can infer ((v(((s u2 H(W, w2]) WB. Further, since wi w1, w2]3) is injective, we can uniquely obtain W.
For any function g on (X, W)) we can construct a function e such that ((((XW)) = 9XX, W). This is always achievable since h(X, W) is injective.
A.5 PROOF OF LEMMA 5
Lemma 5. Assume X is countable. There exist two functions fi and f2 so that for infinitely
many choices cf including all irrational numbers, h(c, X, W) = (1+ + (c) + E fi(x) + E WeW fe(fi (w1) + fi (w2)) is unique for any distinct 3-tuple of (c, X, W). where c E X. X X is a multiset with a bounded cardinality, and W C WW [((w,, w2) Wwi W2 E X3 is a multiset of multisets with a bounded cardinality. Moreover, any function g on (c,X, W) can be decomposed as g(c, X, W) = x (1++))((0)+ Erex for some function sp
f2(Fi (w1) ff (w2)))
Proof. We consider the same functions fi = (z)x and f2 = N-2( as in our proof for Lemma 4. We prove this lemma by showing that, if is an irrational number, h(c, X, W) A h(d,X', W') holds for any X, W) + (d,X', W'). We need to consider the following two cases.
(1) If c d' but (X, + (X',"), according to Lemma 4, we have Evex fi(z)= + El fe(fi(w)) (w)))+)(((() + ExEx +xx)+E Euwwen wa New ( Thus, can obtain h(c, X, W)+ #
17

---

Under review as a conference paper at ICLR 2023
(2) If # d, we show h(c, X,W) # h(c, X', W we have
by contradiction. Assume h(c, X,W)
(1+ [++0((+++
Σ f
Σ
fe(f(w)) + f1(w=)) =
DEX
(11)
(1 (1+08(c)+ E
fi(x)
Σ
(2( + fi(w2))
zeX'
This can be rewritten
<(f((c) - (f(())-f(c))) = (fi(d)
Σ
fi(2) +
E fe(f fi(())))
TEX!
(Dn.wa WaWe
(12)
- -(i(ot+ Σ fi))+
E
(w)) + f(
BEX
H2
Since fi(c) - fi(e') * and it is rational, given 6 is irrational, we can conclude that L.H.S. of Eq. (12) is irrational. R.H.S. of Eq. (12), however, is rational. This reaches contradiction. Thus, if + é', we have h(c, X, W) &
For any function on (c, X, W). we can construct a function yp such that y (h((c, = g(e, X, W). This always achievable since h(c, X, W) injective.
Further justification for the first layer. If the input features x E X' are one-hot encodings, f1 is necessary and thus can be removed. In other words, we can show as follows that there exists an f2 such that h (c, X, W) (1 E)c Erex x ((vr,, ((rr) eww S2(wi + w2) is unique for any distinct 3-tuple of (c, X, W) Note that Exex x is injective input features one-hot encodings, and the value of Exex must be composed of integers. In addition, (fffr,, w2l)) w1 w2 is also injective. Similarly, We define the set )" = {+' [+ w2 (2)))// W2 E X}. We consider Z- y" + N be an injection from E 3 to natural numbers and f2 = N- (2)22) where N > [W] for all W. Then h1,c, X, W) = (I+e)c+)) >,Ex x Σ (( ((#1,"=)) f2 [w] + w2) is injective, since [(wreee)) f2(w1 + w22) is unique for any W and is a number E (0, 1), thus differing from the integer-valued Σxex This is why we do not need another MI.P to model f(()) in Eq. (6).
B EXPERIMENTAL DETAILS
B.1 DATASET STATISTICS
Table 7: Dataset Statistics. Avg. #MessageNc denotes the average #MessageNe node,
Dataset
Task
Domain
*Graphs
Avg. WNndes
Avg. Afdges
Avg. #Messagewe
IMDB-B
Graph classification
Social network
1000
19.7
96.5
IMDR-M
Graph classification
Social network
1500
13
131.8
70.6
COLLAB
Graph classification
Social network
5000
74.5
4915.6
5016.2
PROTEINS
Graph classification
Bioinformatics network
1113
39.1
145.6
2.1
oghg-ppa
Graph classification
Rioinformaics network
78200
100/34800
243.4
2206.1
179.3
PATTERN
Node classification
Social network 20000/2000/2200
118.9
6079.8
3110.1
CLUSTER
Node classification
Social network 10000/1000/1000
117.2
4303.8
1301.5
B.2 MODEL CONFIGURATIONS AND TRAINING HYPERPARAMETERS
For efficiency, we do not tune the model configurations and training hyperparameters for NC-GNN extensively. Since our NC-GNN model is natural extension of GIN, usually use the model configurations and tuned hyperparameters GIN from the comminity as the start point for NC-GNN and then tune them little bit according to the validation results.
For the model architecture, we tune the following configurations; those are (1) the number of layers, (2) the number of hidden dimensions, (3) using jumping knowledge (JK) technique not, and (4) using residual connection or not. To ensure fair comparison, we only consider employing techniques (3) and (4) the datasets where the baseline GIN model also use them.
18

---

Under review as a conference paper at ICLR 2023
In terms of training, consider tuning the following hyperparameters. those are (1) the initial learning rate, (2) the step size of learning rate decay, (3) the multiplicative factor learning rate decay, (4) the batch size, (5) the dropout rate, and (6) the total number of epochs.
The selected model configurations and training hyperparameters for all datasets are summarized in Table 8. For each dataset from GNN Benchmark, have several NC-GNN models under different parameter budgets, as described in Section 6. Accordingly, we list the configurations and hyperparameters for all of these models for reprodueibility.
Table 8: The selected model configurations and training hyperparameters of NC-GNN all datasets.
Dataset
IMDB-B
IMDB-M
COLLAB
PROTEINS
ogbg-ppa
CLUSTER 70/154/78
PATTERN
Layers
5
5
5
5
5
4/4/16
4/4/16 70/154/78
Hidden Dim.
64
64
64
32
300
JK
/
/
/
/
Residual Con.
Initial LR
0.001
0.005
0.005
0.001
0.01
0.001
0.001
Step size of LR
50
50
20
50
30
20
20
Mul. fac. of I.R
0.5
0.5
0.5
0.5
0.1
0.5
0.5
Batch size
32
128
256
32
32
32
32
Dropout rate
0.5
01.5
0.5
0
0.5
0/0.1
0/0/0.5
Epochs
200
300
100
100
80
100/140/140
100/100/200
B.3 THE NC-GNN MODEL FOR GRAPHS WITH EDGE FEATURES
The layer-wise formulation of our NC-GNN model with considering edge features is
h = ( (1++(0))n(
(t-1)) Σ
(E (6-1) +ew))
Σ M1L (M1,N9)ER
MLP (h(4-1) + (6-1) + Cuy
WEN.
which is natural extension of Eq. (6) by including edge features. Cav is the edge feature associated with edge (u, v). practice, we usually apply an embedding layer to input edge features such that they have the same dimension as the node representations.
For reference, the GIN model with considering edge features (Hu et al., 2019) can be formulated as
h ( ((1 (
((-1))
Σ wEN.
RELU(N + Can)
19


Reviews:
[{"review_id": "z2bFyPl8o7E", "reviewer": "Reviewer_xnLi", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of improving the expressiveness of graph neural networks. In particular, the paper proposes NC-GNN, a GNN training method that incorporates edges among neighbors as additional information for improving the accuracy of GNN. The work also provides some theoretical justification on why the proposed method is more expressive than existing work such as the 1-dimensional WL algorithm, in terms of identifying non-isomorphic graphs. Evaluations of several data sets show that the proposed method can achieve higher accuracy than existing methods such as GCN, GraphSAGE, and GIN.", "summary_of_the_review": "Despite there being some unanswered questions such as whether the improvement is at the cost of an increased training budget, the reviewer is overall positive about the work given the theoretical justification of its method and the promising accuracy results.\n\n\n==============================\nPost-rebuttal comments:\n\nThe reviewer has read the other reviewers' comments and the authors' responses. The reviewer appreciates the authors for adding additional evaluation results to show the benefits of reduced training time and memory usage than existing work such as GIN-AK+. From that result, the improvement indeed looks quite promising and large. On the other hand, the concerns raised by the reviewer Agxt and other reviewers, such as limited theoretical contribution and the evaluation methodology (e.g., metrics and missing datasets), also seem to be valid. That said, the reviewer finds this work exposes opportunities for further scaling GNN training, so I will keep my score positive. ", "strength_and_weaknesses": "Strengths:\n- It is an interesting idea to explore how edges among neighbor nodes would affect the effectiveness of GNN. \n- The proposed method is guided by theoretical analysis and the end results demonstrate promising accuracy improvements over existing methods. \n\nWeaknesses:\n- While getting promising accuracy results, the proposed method appears to have a higher memory complexity than existing ones. Therefore, it is less clear why the proposed method is more scalable than existing methods.\n - While getting higher accuracy under a similar amount of trainable parameters, the training time cost of NC-GNN is significantly higher than baseline methods such as GIN. For example, on Pattern and Cluster, NC-GNN incurs 4-6x longer training time, raising the question of whether the improved accuracy is at a cost of a much higher training budget. Also, notably, when the training budget is about the same (e.g., IMDB-B), the accuracy difference is minimal (with no statistical significance). This raises questions on whether the improvement can be achieved by simply training with a larger training budget and some hyperparameter tuning (e.g., learning rate schedules). Without this question answered, one cannot definitely say that considering neighbor node connections is the mere factor for the observed accuracy. Unfortunately, the paper makes no attempt to demonstrate whether that's the case. To be more convincing, it would be better for the authors to compare the proposed method with existing methods under the same training budget (not just the same amount of parameters but also a similar training time) with detailed hyperparameter setups. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "nrcINoNv5G2", "reviewer": "Reviewer_Agxt", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a simple extension to current message passing based GNN, inspired from recent subgraph GNNs. Although being less powerful than subgraph GNNs, the proposed method is efficient with limited computation overhead comparing with message passing GNNs. The author demonstrates its improvements over many real-world datasets.", "summary_of_the_review": "The author proposes a simple add-on to the current message passing based GNN with the same intuition mentioned in [Zhao et al. 2021] but more much efficient implementation (with being less powerful), however this efficient implementation is also covered by a recent paper [Feng et al. 2022] . Given all these existing works, I can hardly find enough contribution in this paper. (If this paper is designed 1-year eariler it's possible to be novel, however currently I really cannot find novelty.)\n\n\n\n\n[Zhao et al. 2021] From stars to subgraphs: Uplifting any GNN with local structure awareness.   \n[Feng et al. 2022] How Powerful are K-hop Message Passing Graph Neural Networks\n", "strength_and_weaknesses": "**Strength**:\n1. Simple, and fast. \n2. Effective in several real-world datasets. \n\n**Weakness**:\n1. Not novel. The design is too incremental comparing with these Subgraph GNNs. Although being simple and fast. \n2. It is just a special case of recently neurips 2022 paper [How Powerful are K-hop Message Passing Graph\nNeural Networks], with K=1. The NeurIPS paper is general and with extensive theoretical analysis. In this paper I can only find the simplicity as a contribution. The incremental design doesn't help the research area. \n3. All theorems are mentioned in existing papers. The 3-WL bound is inside [Understanding and extending subgraph gnns by rethinking their symmetries]. \n4. Experimental evaluation misses too many baselines. First, we all know that TUDataset is not good for evaluating expressivity. Second, widely used ZINC is missing. Third, performance of NestedGNN, GNN-AK, ESAN are not inside the paper. Of course the performance shouldn't be higher than them, but the author should include and also include run-time comparison. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "ZtxW3bg9pq", "reviewer": "Reviewer_zieR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, based on message-passing frameworks, the authors propose a new graph neural network with expressiveness upper-bounded by 3-WL theoretically. Instead of aggregating the 1-hop neighbours, NC-GNN considers the edge between 1-hop neighbours. More importantly, the implementation is very efficient and thus is able to run in large-scale datasets. Experiments demonstrate that the proposed NC-GNN achieves good performance on various benchmarks.", "summary_of_the_review": "As I'm not an expert in the field, I can't give an opinion at this stage as I don't see any hard points. I therefore prefer to refer to other reviewers' comments.", "strength_and_weaknesses": "Strength:\n1. This method is simple and efficient.  The superiority of our NC-1-WL lies in improving the expressiveness over 1-WL, while being\nefficient as 1-WL.\n\n2. NC-GNN is provably as powerful as NC-1-WL in distinguishing non-isomorphic graphs.\n\nWeakness:\nAlthough this paper mainly focuses on a GNN for the large-scale dataset. I think a comprehensive comparison is necessary even if the NC-GNN‘s performance is not as good as others. GraphSNN is only mentioned in this paper but do not compare in the experiment.  Comparison of real training time also needs to add other methods. In general, I felt that the experimentation was rather inadequate and seemed to deliberately avoid certain methods. This, therefore, reduces the convincing of the experiment.\n\nIn fact and I'm curious as to why NC-GNN didn't try it on the node classification task. In my opinion, ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "W7Hl3FL0XR", "reviewer": "Reviewer_nYWZ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper tackles the challenging goal: developing a general GNN framework with provably expressive power while maintaining the scalability of the message-passing scheme. The authors first model the edges among neighbors as a multiset of multisets and formulate the NC-1-WL graph isomorphism. They show that the expressiveness of NC-1-WL in distinguishing non-isomorphic graphs is strictly above 1-WL and below 3-WL. But based on NC-1-WL, they can propose a differentiable version called NC-GNN, which is intrinsically more scalable than the algorithms that mimic the WL graph isomorphism test. Experimental results on not only graph classification but also node classification tasks show that NC-GNN can consistently outperform GIN by significant margins on various tasks and achieve competitive performance as existing expressive GNNs while being much more efficient.", "summary_of_the_review": "Overall for the current manuscript, I recommend weak rejection. I like the idea of the proposed NC-1-WL test and the corresponding NC-GNN algorithm. However, since recently there have been many papers on provably powerful while scalable GNNs, the current insufficient experimental comparison to those work, including subgraph-based GNNs, on larger graphs, and in terms of efficiency, cannot support the claimed contributions of NC-GNN well.", "strength_and_weaknesses": "#### Strengths\n1. To the best knowledge, I think the construction of this modified graph isomorphism test, NC-1-WL is novel. And I like the idea of further modeling the \"edge coloring\" as multisets of multisets, which seems naturally extend the WL-test algorithm. It is not hard to understand its superiority to the standard 1-WL test, while it still only relies on only local operations, in contrast to 3-WL.\n2. The experimental results compared with GIN demonstrate that this added embedding from pairs of neighbors is effective for real-world datasets and not only graph classification but also node classification tasks.\n3. The paper writing is very polished and clear.\n#### Weaknesses\n1. I think the experimental comparison to subgraph-based GNNs is very insufficient in the current manuscript. The authors only show the performance comparison to subgraph-based GNNs on the TUDatasets, which are mostly small graphs and are gradually replaced by OGB (Hu et al., 2020) and GNN Benchmark (Dwivedi et al., 2020). Thus it would be interesting and important to see more comparisons to subgraph-based baselines on those datasets. More importantly, one major advantage of the proposed NC-GNN is the scalability/efficiency. So the authors should expand Table 5. to compare with subgraph-based GNNs in terms of the epoch-time, memory usage, convergence speed, etc.\n2. I think the related work section needs some expansion to discuss more prior papers (apart from subgraph-based GNNs) which (1) propose more powerful GNNs, maybe not in the sense that strictly better than 1-WL, while maintaining the scalability (e.g., [1]) or (2) follow the WL-hierarchy and are probably better than 1-WL, while being much more efficient than mimicking the k-WL test algorithm (e.g. [2]). Recently there have been many papers trying to tackle these two directions, and I hope the authors could do a more careful literature review of those papers.\n\n#### Minor Issues\n1. I suggest the authors color the reference links.\n\n##### References\n- [1] Papp, P. A., Martinkus, K., Faber, L., & Wattenhofer, R. (2021). Dropgnn: random dropouts increase the expressiveness of graph neural networks. Advances in Neural Information Processing Systems, 34, 21997-22009.\n- [2] Puny, O., Ben-Hamu, H., & Lipman, Y. (2020). Global attention improves graph networks generalization. arXiv preprint arXiv:2006.07846.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject