Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithm
Authors: Meng Liu
Haiyang Yu
Shuiwang Ji
Venue: Accepted by TMLR ()

Abstract: Message passing graph neural networks (GNNs) are known to have their expressiveness upper-bounded by 1-dimensional Weisfeiler-Leman (1-WL) algorithm. To achieve more powerful GNNs, existing attempts either require \emph{ad hoc} features, or involve operations that incur high time and space complexities. In this work, we propose a \textit{general} and \textit{provably powerful} GNN framework that preserves the \textit{scalability} of the 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 performs effectively and efficiently on various benchmarks.

Published in Transactions on Machine Learning Research (01/2024)
Empowering GNNs via Edge-Aware Weisfeiler-Leman Algo- rithm
Meng Liu
menglinstamuucck edu
Deportment of Computer Science & Engineering Teaas ABM University
Haiyang Yu
haiyang Stama edu
Department of Computer Science & Engineering Texas ABM University
Shuiwang Ji
sji edu
Department of Computer Science & Engineering Texas ABM University
Reviewed on OpenReview: /ttp::///pprreetee net/ forum? id- VDy6LgErFM
Abstract
Mcssage passing graph neural networks (GNNs) are known have their expressiveness upper-bounded by 1-dimensional Miisfeiler-eemar (I-WL) algorithm. To achieve more powerful GNNs, existing attempts either require ad hoc features, involve operations that incur high time and space complexities. In this work, propose general and provably powerful GNN framework that preserves the scalability of the message passing scheme. In particular, we first. propose lo empower 1-WL. for graph isomorphism test. by considering edges among neighbors, giving rise to NC-1-WL. The expressiveness of NC-1-WL shown to be strictly above 1-WL and below 3-WL thcorctically. 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 NC-1-WL. Experiments demonstrate that our NC-GNN performs effectively and efficiently various benchmarks.
1 Introduction
Scarselli al.] 2008) have been demonstrated to be effective for various graph tasks. In general, modern GNNs employ message passing paradigm where the representation of each node is recursively updated by aggregating representations from its neighbors (Awwood
Graph Neural Networks (GNNs) Gori al.) 2005
& Towsley 2016; Li et al. 2016 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 I-dimensional Weisfeiler-Leman (1-WL) algorithm (Weisfeiler Lehman 1968) in distinguishing
non-isomorphic graphs (Xu al.
2019 Morris et al. 2019). Thus, message passing GNNs cannot distinguish
some simple graphs and detect certain important structural concepts (Chen al. 2020
Arvind
2020
The recent efforts improve the expressiveness of message passing Graph Neural Networks (GNNs) have
been focused high-dimensional WL algorithms (e.g., Morris et al. (2019): Maron et al. (2019) ) exploiting
subgraph information (e.g., Bodnar et al. (2021a): Zhang & Li (2021)). or adding more distinguishable features (e.g., Murphy et al. (2019); Bouritsas el al. (2022)). As thoroughly discussed in Section and
Appendix B these existing methods either rely on handcrafted/preee /predeeinedd domain-speciffi features, or require high computational cost and memory budget. In contrast, this work aims to develop general GNN framework with provably expressive power, while maintaining the scalability of the message passing scheme.

---

Published in Transactions on Machine Learning Research (01/2024)
In particular, we first propose extension of the 1-WL algorithm, namely NC-1-WL, where NC stands for neighbor communication. To be more specific, 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 as a multiset of multisets, in which each edge is represented as a multiset of two elements. We show theoretically that the expressiveness of our NC-1-WI. in distinguishing non-isomorphic graphs strictly above 1-WL, and below 3-WL. Further, based on NC-1-WL, we introduce the NC-GNN framework, a general and differentiable neural version of NC-1-WL. We provide a simple implementation of NC-GNN that is proved to be as powerful as NC-1-WL. Compared to existing expressive GNNs, our NC-GNN is a general, provably powerful, and, more importantly, scalable framework.
We thoroughly evaluate the performance of our NC-GNN on graph classification and node classification tasks. Our NC-GNN consistently outperforms GIN, which is as powerful as 1-WL, by significant margins on various benchmarks. Remarkably, NC-GNN achieves an impressive absolute margin of 12.0 over GIN in terms of test accuracy on the CLUSTER datasct. Furthermore, NC-GNN performs competitively and often achieves better results, compared to existing expressive GNNs, while being more efficient.
2 Preliminaries
We start by introducing notations. We represent undirected graph as 9 (V, F, X), where V is the set of nodes and E' C V x V denotes the set of edges. We represent an edge {r, u] E E' by (v, u) or (u, for simplicity. X = [x1,-.. "0,,"" E Rnnd is the node feature matrix, where = [V] is the number of nodes and a. E Rd represents the d-dimensional feature of node v. .., = {u E Vi u) E F} is the set of neighboring nodes of node v. multiset is denoted as (l...). } and formally defined as follows.
Definition 1 (Multiset). A multiset is a generalized concept of set allowing repeating elements. multiset X can be formally represented by 2-tuple X = (Sx, mx); where Sx is the underlying set formed by the distinct elements in the multisct and mx : Sx - Z+ gives the multiplicity (Le., the number of occurrences) of the elements. If the elements in the multiset are generally drawn from set X (L... Sx C X),, then X is the universe of X and we denote it as X S X for ease of notation.
Mcssage passing GNNs. Modern GNNs usually follow a message passing scheme to learn node representa- tions in graphs (Gilmer el al. 2017). To be specific, the representation of each node is updated iteratively by aggregating the multiset of representations formed by its neighbors. In general, the f-th layer of a message passing GNN can be expressed as
(2) = I neggregate (0) ((N(-")/uEN.))) h( = Supdato (0) (n!!-)) ,a!!))
(1)
I laggregate (0) and Supdate (9) are the parameterized functions of the f-th layer. h is the representation of node v at the b-th layer and (0) can be initialized as T.. After employing L such layers, the final representation ( can be used for prediction tasks on cach node v. For graph-level problems, graph reproscntation he
can be obtained by applying readout function as,
hg = fredoout (en))))
(2)
Definition 2 (Isomorphism). Two graphs = (V, and H. (P. are isomorphic, denoted G = H. if there exists a bijective mapping g V - P such that D. = Ug(e), Vo E V and (v,u) E E iff (o(v),glu)) e F. Graph isomorphism is still an open problem without a known polynomial time solution.
Weisfeiler-Leman algorithm. The Weisfeiler-Leman algorithm WWisfeiler & Lehman 1968 provides a hierarchy for the graph isomorphism testing problem. Its 1-dimensional form (a.k.a,, 1-WL or color refinement) is a heuristic method that can efficiently distinguish a broad class of non-isomorphic graphs (Babai & Kucera 1979.. 1-WL assigns a color & to each node according to its initial label (or feature 1 and then iteratively refines the colors until convergence, where the subsets of nodes with the same colors can not be further
IT there are initial features or labels, 1-WL. assigns the same color to all the nodes the graph.
2

---

Published in Transactions on Machine Learning Research (01/2024)
(a)
VS.
1-WL
HASH
NC-1-WL
HASH
(b)
HASH
HASH
Figure 1: (a) Several example pairs of non-isomorphic graphs, partially adapted from Sato 2020 that cannot be distinguished by 1-WL. Colors represent initial node labels or features. Our NC-1-WT, can distinguish them. (b) A comparison between the executions of 1-WL and NC-1-WL on two non-isomorphic graphs
split different color groups. In particular, at each iteration &, it aggregales the colors nodes and their neighborhoods, which are represented as multisets, and hashes the aggregated results into unique new colors (i.e., injectively). Formally,
HASH de-1),
1/ E
(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-WT. 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 2 Appendix A.2 It
is known that 1- is as powerful as 2-WL in terms of distinguishing non-isomorphic graphs (Cai ct al.
1992
Grohe & Otto 2015 Grohe 2017). Moreover, for k 2 2, (k: + 1)-WL is strictly more powerful than
W-
Grohe & Otto 2015). More details of the WL algorithms are given in Cai et al. 1992]; Grohe 201
Sato
2020);
Morris et al. (2021).
Given the similarity between message passing GNNs and 1-WL (i.e. Eq. I us. Eq.
message passing
GNNs can be viewed as differentiable neural version of 1-WL. In fact, the expressiveness of message passing
Graph Neural Networks (GNNs) is known to be upper-bounded by 1-WL (Xu et al. 2019 Morris et al. 2019), and message passing GNNs can achieve the same expressiveness as 1-WL L if the aggregate, update, and readout functions are injective, which corresponds to the GIN model (Xu et al.
2019 In other words, if two
non-isomorphic graphs cannot be distinguished by 1-WL, then message passing GNNs must yield the same embedding for them. Importantly, such expressive power not sufficient to distinguish some common graphs and cannot capture certain basic structural information such as triangles (Chen et al. 2020 Arvind al.) 2020), which play significant roles in certain tasks, such tasks social networks. Several examples that cannot be distinguished by 1-WL message passing GNNs are shown in Figure 1 (a).
3 The NC-1-WL Algorithm
In this section, we propose the NC-1-WL algorithm, which extends the 1-WL algorithm by taking the edges among neighbors into considcration. With such simple but non-trivial extension, NC-1-WL proved be strictly more powerful than 1-WL and less powerful than 3-WL, while preserving the efficiency of 1-WL.
As shown in Eq. (3 and [ 1-WL and message passing GNNs consider neighbors of each node multiset of representations. Here, we move one step forward by further treating edges among neighbors as multisct,
2There families of WL algorithms; they &-WL and k-FWL (Folklore WL). They both consider coloring k-tuples and their difference lies in how aggregate colors from neighhoring k-tuples. known that (k 1W-FWL powerful & WT. for (Grohe & Otto 2015 Grohe 2017 Maron al. 2019). To avoid ambiguity, this work, we only involve k-WT.
3

---

Published in Transactions on Machine Learning Research (01/2024)
Algorithm 1 NC-1-WL us. 1-WL for graph isomorphism test
Input: Two graphs g = (V, E, X) and H FYY
(0) + HAsH(a.), Vu E V
HASH(yp): V
repeat (L- ..2.....
if Uh
1660-1110 | [VE + Hidy (
"p E PJ
then
return 9 2 H
end if
for NEV do
& + HASH co ((-1) Hohh-1) E No.),, (1llo ,uz De lun, u2 No. (u1, u2) F]]
(t-1)
end for
for P P
do
10 - HASH (1-1) 1aa6-""1a NND)). ((((a)-))) dee Blen, E NNr, (91,2)) E F))
up
end for until convergence return G -
where each element is also a multiset corresponding to an edge. We formally define a multiset of multisets follows.
Definition 3 (Multiset of multisets). A multiset of multisets, denoted by W, is multiset where each element is also a multiset. Tn this work, we only need to consider that each element in W is a multiset formed by elements. Following our definition of multisct, these clements are generally drawn from a set X, the universe of W is the set W = (ff,, w2 Bl w1, w2 E X}. We can formally represent W = (Sw, mw), where the underlying set Sw W and mw Sw + z gives the multiplicity. Similarly, we have W C W.
Particularly, our NC-1-WL considers modeling edges among neighbors multiset of multiscts and extends 1-WL (f.e., Eq.
3 to
c < HASH c (E-1),
((of-")/u NoH), (((C c0 Ae-"Mau u2 E No, (u1, u2) E E}
A multisct of multiscts
As 1- 1-WL, our NC-1-WL determines two graphs to be non-isomorphic as long as the colorings of these two graphs are different some iteration. We summarize the overall process of NC-1-WL in Algorithm [ where the difference with 1-WL is underlined.
Importantly, our NC-1-WL is more powerful than 1-WL in distinguishing non-isomorphic graphs. Several examples that cannot be distinguished by 1-WL are shown in Figure (a). Our NC-1-WL can distinguish
them casily. An example of exccutions 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.l and A.2
Theorem 1. NC-1-WL is strictly more powerful than J-WL in distinguishing non-isomorphiic graphs.
Theorem 2. NC-1-WL is strictly less powerful than 3- WL in distinguishing non-isomorphic graphs.
Although NC-1-WT. is less powerful than 3-WL, 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, as 1-WL, NC-1-WL only needs to color each node, which corresponds to n refinement steps in each iteration. Thus, the superiority of our NC-1-WL. lies improving the expressiveness over 1-WL, while being efficient as 1-WT.
Note that our NC-1-WL differs from the concept of Subgraph-1-WL (Zhao et al. 2022), which ideally generalizes 1-WL from mapping the neighborhood to mapping the subgraph rooted at each node. Specifically, the refinement step in Subgraph-1-WL (!)) <- HASH (G[N?)), where g[V)) is the subgraph induced by the k- h-hop neighbors node v. However, it requires an injective hash function for subgraphs, which is essentially
hard the graph isomorphism problem and cannot. be achieved. In contrast, our NC-1-WT. does not aim
4

---

Published in Transactions on Machine Learning Research (01/2024)
to injectively map the neighborhood subgraph. Instead, we enhance 1-WL by mathematically modeling the edges among neighbors as 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 a 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. (L) NC-GNN further considers the edges among neighbors as NC-1-WL. One layer of the NC-GNN framework can be formulated as
c = ccommunicate" (0)
[[ " ((-11) u2 E No, (u1, u2) E EH),
(()1))
a = Inggregate (4) (1 (1 N..).,
(5)
h
(8) fupdate (8)
h (1-1)) (1) d.)
f commmunicate" (0) is the parameterized function operating multisets of multiscts. The following theorem establishes the conditions under which our NC-GNN can be as powerful as NC-1-WL.
Theorem 3. Let = - Rdd be an NC-GNN model with sufficient wumber of layers following Eq- 5 M
is powerful NC-1-WL in distinguishing non-isomorphic graphs if the following conditions hold: (1) At each layer E, f communicate (f) aggregate (8), and f update" (?) are injective. (2) The final readout function fradout is injective.
The proof is provided in Appendix A.3 One may wonder what advantages NO-GNN has over NC-1- WL. Note that NC-1-WL only yields different colors to distinguish nodes according to 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-WT, aims at representing nodes in the embedding space. Thus, an NC-GNN model satisfying Theorem 3 can not only distinguish nodes 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 communicale, aggregale, and update functions in the NC-GNN framework. Here, following the NC-GNN framework, we provide a simple architecture, that provably satisfies Theorem 3 and thus has the same expressive power as NC-1-WL. To achieve this, we generalize the prior results parameterizing universal functions over sels (Zaheer el al. (017)) and mullisels (Xu et al. 2019) to consider both multisets and multisets of multisets. Such non-trivial generalization 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 fi and f2 so that h(X, W) = Exex + Etw,, New f2(fi (w1) (ww2) is unique for any distinct pair of (X, W), where X S X multiset with a bounded cardinality and W C = ([w, wz (illw,, u2 E X3 is a multiset of multisels with a bounded cardinality, Moreover, any function g on (X, W) can be decomposed as g(X, W) = ( fi(x) + E HeW (2([((w)) + fi(w))) for some function 6.
Lemma 5. Assume X countable. There erist two functions S1 and f2 so that for infinitely many choices of including all irrational numberrs h(c, X, W) (1+e)fi(c) + ExEx fi(x) + E (w fa(f((wi) + fi(w2)) is unique for any distincl 3-luple of (c, X, W), where E X, X C X is a mulliset with bounded cardinality, and W C W {ffrr w2 (1i, W2 X) is multiset of multisets with a bounded cardinality- Moreover, any function g on (c, X, W) can be decomposed g(c,X, X, W) = ((1 +e)((()) + Exex fi(x) +
Σ Ce J2(fi (w1) + fi (w2))) for some function 4p
5

---

Published in Transactions on Machine Learning Research (01/2024)
We can use multi-layer perceptrons (MLPs) to model and learn fi, f2, and yp in Lemma 5 since MLPs are universal approximators (Hornik et al. 1989 Hornik 1991). p. To be specific, we use an MLP to model the compositional function fi f((+1) o ep(0) and another MLP to model f/") for t 1.2. L. At the first layer, we do not need f1") if the input features are onc-hot encodings, since there cxists function f2 that can preserve the injectivity (See Appendix A.5 for details). Overall, one layer of our architecture can be formulated as
h M MLP(O((I+ (1)+ ((-1)) Σ h
((-1)) +
Σ MI.U (W1,02)ER
( + 1)
(6)
MeN.
The difference with GIN
where (0) is a learnable scalar parameter. According to Lemma 5 and Theorem 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 GTN is highlighted in Eq. (6), which is also our key contribution. Note that if there do not exist any edges among neighbors for all nodes in graph (i.e, no triangles), the third term in Eq. 6 will be zero for all nodes, and the model will reduce to the GIN model.
Complexity. Supposc a graph has n nodes and m edges. Message passing GNNs, such as GIN, require O(n) memory and have ((nd) time complexity, where d is the maximum degree of nodes. For each node, we define #MessageNC 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 & denotes the maximum #MessogeNc of nodes. Suppose there totally T triangles in the graph, in addition to node representations, 37 representations as the input of MLP2. Tf 37 > m, we can alternatively store (h., + hug) ) for each edge (ul,w)) E E. Thus, the memory complexity is O(n + min(m,,3)) GNNs, our NC-GNN has a bounded memory overhead and preserves the time efficiency. Note that in typical sparse or moderately dense graphs, which are common in many real-world datasets, t is generally small. However, in the worst-case scenario of increasingly dense graphs, d is approaching n. Thus, in the worst case, NC-GNN has a higher order of time complexity compared to GIN. Despite this, it is crucial to emphasize that even in this worst-case scenario, NC-GNN maintains better efficiency than other high-expressivity GNN models, such as subgraph GNNs. More detailed comparisons are in Section 5 and Appendix B Overall, compared to many existing expressive GNNs, NC-GNN offers a more lavorable balance between expressiveness and scalability.
need to further store
Hence, compared to message passing
possible that t approaching n², while
5 Related Work
The most straightforward idea to enhance the expressiveness of message passing GNNs is to mimic the k-WL (k 3) algorithms (Morris et al. 2019 2020b Maron et al., 2019 Chen et al. 2019 For example, Morris et al. (209)) proposes 1-2-3-GNN according to the sct-based 3-WL, which is powerful than 1-WL and less powerful than the tuple-based 3- BLL It requires O(n²) memory since representations corresponding to all sets of 3 nodes need to be stored. Moreover, without considering the sparsity of the graph, it has O(n)) time complexity since each set aggregates messages from n neighboring sets. Maron et al. (2019) develops PPGN based on high order invariant GNNs (Maron et al., 2018) and 2-FWL, which has the same power as 3-W.. Thereby, PPGN achieves the same power as 3- WT. with ((n2) memory and (nn)) time complexity. Nonetheless, the computational and memory costs of these expressive models are still too high to scale large graphs.
Another relevant line of research for improving GNNs is to exploit subgraph information (Frasca et al. 2022 Bodnar et al. (2021 a) perform mossage passing on high-order substructures of graphs, such as simplicial and cellular complexes. Its preprocessing and message passing step are computationally expensive. GraphSNN (Wijesinghe & Wang, 2022) defines the overlaps between the subgraphs of each node and its neighbors, and then incorporates such overlap information into the message passing schome by using handcrafted structural coefficients. ESAN (Bevilacqua al. 2022) employs an equivariant framework learn from bag of subgraphs of the graph. Subgraph GNNs Zeng et al. (2021); Sandfelder et al. (2021)
6

---

Published in Transactions on Machine Learning Research (01/2024)
: Zhao et al. (2022) apply GNNs to the neighborhood subgraph of each node. For 2022) first apply a base GNN to encode the neighborhood subgraph information of each node and then employ another GNN on the subgraph-encoded representations. Besides, the rocently proposed KP-GNN (Feng ct al. 2022 focuses on aggregating information from K-hop neighbors of nodes and analyzing its expressive power. is worth noting that many expressive GNNs, including our proposed NC-GNN, GraphSNN, subgraph GNNs, and KP-GNN, share a common observation that considering more informative structures, i.e., subgraphs, than rooted subtree would enhance the expressive power. Importantly, the key difference lies in how such advanced structures are effectively and efficiently incorporated into deep learning operations. More detailed comparisons to GraphSNN, subgraph GNNs, and KP-GNN are included in Appendix B
Zhang & Li (2021):
example, NGNN (Zhang & Lij 2021 and GNN-AK (Zhao et al.,
Due to the high memory and time complexity, most of the above methods are usually evaluated on graph-level tasks over small graphs, such as molecular graphs, and can hardly be applied to large graphs like social networks. Comparod to these works, our approach differs fundamentally by proposing a general (í.e., without ad hoe features) and provably powerful GNN framework that preserves the scalability of regular message passing in terms of computational time and memory requirement. Overall, NC-GNN achieves sweet spot between expressivity and scalability.
There are several other heuristic methods proposed to strengthen GNNs by adding identity-aware infor-
mation (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. 2002)), predefined structural features (Monti et al.) 2018 Li et al.
2020
Rossi 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 as techniques to further augmentt our
NC-GNN. In addition, PNA (Corso et al. 2020) applies multiple aggregators to enhance the performance of
GNN. Most recently, Morris et al. 22022; Qian et al. (2022); "hhang et al. (0023);; Wang et al. (0023;; Zhang 2023a) propose several new hicrarchics, which are more finc-grained than the WL hicrarchy, for the
ct al.
GNN expressivily problem. For a deeper underslanding of expressive GNNs, we recommend referring to the
recent surveys (Sato 2020 Morris et al. 2021 Jegelka 2022).
6 Experiments
In this section, we evaluate the effectiveness of the proposed NC-GNN model on real benchmarks. In particular, we consider widely used datasets from TUDatasets (Morris et al. 2020a), Open Graph Benchmark (OGB) (Hu et al., 2020), and GNN Benchmark (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 cortain datasots in these benchmarks, such as MUTAG, PTC, and NCT1, 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 GLN model and thus perform nearly the same GIN, as shown in Appendix [..] Hence, we omit such datasets in our main section. All the used datasets and their statistics, including Avg. #MessageNc, are summarized in Table Appendix C.2 Our implementation is based on the PyG library (Fey & Lenssen 2019). The detailed model configurations and training hyperparameters of NC-GNN on each dataset are summarized in Table g Appendix C.3
Baselines. We mainly compare NC-GNN with the following three lines of baselines. (1) GIN. As highlighted in Eq. 6 NC-GNN closely follows the GIN model and the fundamental difference is that NC-GNN further considers modeling edges among neighbors. Hence, comparing to GIN can directly demonstrate the effectiveness of including such information in our NC-GNN, which is the core contribution of our theoretical result. We highlight our results if they achieve improvements over GIN. (2) Subgraph-bassed GNNs. As described in Section 5 our NC-GNN and subgraph-based GNNs share the idea of exploiting subgraph information but differ in how to effectively and efficiently incorporate such structures. Thus, we consider GNNs, including GraphSNN (Wijesinghe & Wang 2022) and GNN-AK (Zhao (3) Other expressive GNNs. We further include several other expressive GNNs, including SIN [Bodnar et al. 2021b), CIN (Bodnar al. (001a)), RingGNN (Chen et al. 2019) and PPGN MMaron et al. 2019.. While our goal is to provide a comprehensive comparison, it is challenging to
two recent subgraph-basse ct al. ), into comparison.
7

---

Published in Transactions on Machine Learning Research (01/2024)
Table 1: Results (%) on TUDatasets. The top three results on each dataset are highlighted as first, second, and third. We also highlight the colls of NC-GNN results if they are better than GIN.
Dataset
GIN
GraphSNN GNN-AK
SIN
CIN
PPGN
NC-GNN
COLLAB
80.2#19
81.4#1.4
82.5+12
PROTEINS
76.2+2.8
76.8225
77.1
76.5+34
77.0:4.
77.2=4.7
76.5+4.4
IMDB-B
75.1
77.9
75.0+42
75.6+a.2
75.613.7
73.0
75.244.5
IMDB-M
52.3+2.
52.5#3.0
52.7#3.1
50.5
52.543.2
include all basclines every datasct. Additionally, cortain basclines may encounter scalability issues when applied to large datasets.
TUDatasets. Following GIN (Xu et al. 2019 we conduct experiments on four graph classification datasets
where graphs have many edges among neighbors from TUDatasets (Morris et al. (2200a). We use the same number of layers as GIN and report the f0-fold cross validatoon accuracy following the protocol as (Xu et al. 2019 for a fair comparison.
As presented in Table D we can observe that our NC-GNN outperforms GIN on all datasets consistently. Moreover, NC-GNN performs competitively with other methods that aim to improve the expressiveness of GNN. The consistent improvements over GIN 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 result, can be intuitively justified by observing the considerably larger Avg. #MessageNc on COLLAB compared to other datasets, as shown in Table S Appendix C.2 In this case, NC-GNN can use such informative edges existing among neighbors to boost the performance.
Open Graph Benchmark. We further perform exper- iments the large-scale dataset ogbg-ppa -pppppa (Hu et al.] 2020), which has over 150K graphs and is known as a more convincing bestbed than TUDatasets. The graphs in ogbg-ppa are extracted from the protein-protein asso- ciation networks of different species. 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, instend of our claimed eapressiveness. Thus, here compare with GIN under the same paramcter budget. Specifically, use the same number of layers as GIN to ensure the same receptive field and tune the hidden dimension to oblain an NC-GNN model that has a similar number of learnable parameters as GIN. More detailed setups are included in Appendix C.4 In addition to GIN, we further construct a bascline which is a GIN model with 3-cycle counts included as additional node features. We also include GraphSNN in the comparison. Results over 10 random runs are reported. Note that other subgraph GNN models cannot scale to such a large-scale dataset. For example, NGNN (Zhang & Li. 2021), pointed out in its paper, does not scale to such a dataset with a large average node degrec due to copying rooted subgraph for each node to the GPU memory.
Table 2: Results (%) on ogbg-ppa. ppa.
Model
Param
Test Acc.
GIN
1830942
68.92
GIN + 3-cycle count feature
70.5810..6 64
GraphSNN NC-GNN
70.66=1.0r 06
1754445
71.94.0..
As reported in Table 2 our NC-GNN model outperforms GIN by an obvious absolute margin of 3.02. Note that the only difference between NC-GNN and GIN is that edges among neighbors are modeled and considered in NC-GNN. Thus, the obvious improvements over GIN can demonstrate that our NC-GNN not only has theoretically provable expressiveness but also achieves good empirical performance on real-world tasks. Furthermore, NC-GNN performs better than using 3-cycle count as fcatures and GraphSNN, which demonstrates that, as detailed in Appendix [B. and B.2 is effective in NC-GNN to model edges among neighbors by feature interactions, instead of simply counting 3-cycles features or using predefined coefficients as GraphSNN.
GNN Benchmark. In addition to graph classification lasks, 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 (Abbo 2017), a widely used mathematical modeling method for studying communities in social networks. The task these two datasets is classify nodes in each graph. To be specific, on PATTERN, the goal is to determine
8

---

Published in Transactions on Machine Learning Research (01/2024)
Table Results (%) on GNN Benchmark.
PATTERN
CLUSTER
Model
# Layers
# Param
Test Acc.
# Param
Test Acc.
GIN
4
100884
85.590+0.011
103544
58.384
16
508574
85.387110.36
517570
61..16611.669
RingGNN
105206
86.245510.013
104746
120000
2
504766
86.244+0.088
524202
22.340
505749
Diverged
514380
Diverged
PPGN
103572
85.661
105552
57.130
3
502872
85.341
507252
55.489
581716
Diverged
586788
Diverged
NC-GNN
106756
86.627
107320
19.335=0.00
4 506512
86.732
508428
69.83822.10
16
506512
86.607+0.10
508428
76.718 10.001
At
1.142
12.002 1
Table 4: Comparison of real training time per epoch.
Dataset
PROTEINS
IMDR-M COLLAB IMDR-B
PATTERN
CLUSTER
Avg. #MessageNC
2.1
5016.2
59.5
70.6
3440.1
1301.5
GIN
1.0x
1.0x
1.0x
1.0x
1.0x
PPGN
8.9x
1.1x
4.3x
4.6x
19.8x
23.3x
NC-GNN
1.4x
1.3x
1.2x
1.2x
6.0x
4.6x
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 Dwiveddi et al. 2020 We compare with GIN, and two methods that mimic 3-WL; those are PPGN and RingGNN. The comparison with subgraph GNNs on these datasets will be presented later a more comprehensive To ensure fair comparison, we follow Dwivedi et al. (2020) to compare different methods under two budgets of lcarnable paramcters, 100K and 500K, by tuning the number of layers and the hidden dimensions. Average results over 4 random runs are reported in Table 3 On each dataset, we also present the absolute improvement margin of our NC-GNN over GIN, denoted as 1 by comparing their corresponding best result.
Table 5
We observe that our NC-GNN obtains significant improvements over GIN. To be specific, NC-GNN remarkably oulperforms GIN by an absolute margin of 1.142 and 12.002 on PATTERN and CLUSTER, respectively. This further strongly demonstrates the effectiveness of modeling the information of edges among neighbors, which aligns with theoretical results. Notably, NC-GNN obtains outstanding performance CLUSTER. Since the task of CLUSTER is to identify communities, reasonably justify that considering which neighbors are connected is significant. for inferring communities. Thus, we believe that our NC-GNN can serve as robust. foundational method for tasks involving social network graphs. Moreover, NC-GNN achieves much better empirical performance than RingGNN and PPGN, although they theoretically mimic 3-WL. It observed that these 3- based methods are difficult train and thus have fluctuating performance (Dwivedi et al., 2020 In contrast, our NC-GNN is casier train since preserves the locality of message passing, thereby being more practically effective.
Time analysis. In Table 4 compare the real training time of models various datasets, including PROTEINS, COLLAB, IMDB-B, IMDB-M, PATTERN, and CLUSTER. Specifically, we show the increased training time of NC-GNN and PGNN, compared to the training time of GIN. We can observe that our NC-GNN is indeed more efficient than PPGN. Compared to GIN, the increment of the real running time of NC-GNN largely depends on the number of odges among neighbors. For example, the time consumption of NC-GNN is similar GIN on PROTEINS and IMDB-B, since the Avg. #Messagene is considerably smaller than that. in PATTERN and CLUSTER. Overall, this comparison demonstrates that, compared to GIN, the
9

---

Published in Transactions on Machine Learning Research (01/2024)
Table 5: A thorough comparison between NC-GNN and GIN-AK+ on PATTERN and CLUSTER.
Datasets
Methods
# Layers
# Param
Test Acc.?
Time/spochi
Total Time!
GPU Memory!
MACS
Inference Time'
GIN-AK!
601134
56.836
77.50s
0.67h
31434MB
176.45G
32.19s
PATTERN
K-subgrrph SAT
4
633586
16.845
40.73s
1.66h
1770MBB
0.03G
5.91s
NC-GNN
4
5521966
86, (6.777740.000
42.52s
0.55h
15625MB
1.14G
12.03s
CLUSTER
GIN-AK+
16
602586
76.502
148.98s
1.42h
32142MBB
110.52G
27.16s
K-anhgraph SAT
555718
74.00s
3.69h
2169
0.02G
4.75s
NC-GNN
16
562948
76.982 2o008s
48.87s
0.68h
22386MB
0.84G
5.18s
scaling behavior of NC-GNN remains within a reasonable range, particularly when considering the additional expressiveness it provides.
Thorough comparison with subgraph GNNs and subgraph-aware transformer. Given that subgraph GNNs are also exploiting neighborhood subgraph information, we further perform comprehensive empirical comparison with subgraph GNNs, specifically, GIN-AK+ (Zhao et al. 2022). a representative subgraph GNN model. In addition, include graph transformer method into comparison, which can position our work within the broader landscape of recent ad in the field. We acknowledge it is hard to compare with various graph transformers (Dwivedi & Bresson 2020 Kreuzer et al. 2021 Ying et al. 2021 Chen et al., 2022: Hussain et al. 2022 Ma ct al. 2023) due to different architectures and various techniques, such as positional encodings. Here, we include the K-subgraph SAT model (Chen et al. 2022) into our comparison, which can utilize message passing GNN for subgraph encoding before applying global attention modules. This method aligns with our emphasis on exploiting subgraph information and allows us to compare NC-GNN run it four times and report the
with state-of-the-art graph transformer method. For each experiment, average results for lest 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, we use a metric MACS to calculate the average mulliply-accummlate operations for each graph in the test set. Lower MACS value typically indicates faster inference. The results are summarized in Table 5 Three models achieve comparable accuracies. Overall, compared to GIN-AK+, NC-GNN more efficient training, including training time per epoch and total training time. In addition, we use less GPU memory since we do not have to update node representations for all the nodes in the expanded subgraphs. More importantly, the MACS overhead of GIN-AK+ is 100x more than our NC-GNN. Since 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. Thus, NC-GNN takes less time during inference. In comparison with K-subgraph SAT, NC-GNN demonstrates a reduced training time. Note that graph transformer models, like K-subgraph SAT, often require an additional warm-up stage to reach optimal performance levels. This aspect contributes to the overall longer training duration for such models. NC-GNN has similar memory consumption as K-subgraph SAT since there are many edges among neighbors in these two datasets, as shown in Table 8 Appendix C.2 K-subgraph SAT exhibits slightly better efficiency during inference. This could be due to the inherent architectural differences and optimization techniques employed in graph transformer models.
To further compare to subgraph-based GNNs, we experiment on the graph substructure counting task since it is not only an intuitive measurement for expressive power (Chen et al. 2020) but also is quite relevant to practical tasks in biology and social networks. On counting triangles, our NC-GNN outperforms GIN-AK+ with a lower MAE of 0.0081 as opposed to 0.0123. Details are in Appendix C.5
7 Conclusions
In this work, we first present NC-1-WL as a more powerful graph isomorphism test algorithm than 1-WL, by considering the edges among neighbors. Built on our proposed NC-1-WL, we develop NC-GNN, a general, provably powerful, and scalable framework for graph representation learning. In addition to theoretical expressiveness, we empirically demonstrate that NC-GNN achieves outstanding performance on various real benchmarks. Given its simplicity, efficiency, and effectiveness, we anticipate that NC-GNN will become an important base model for learning from graphs, especially social network graphs
10

---

Published in Transactions on Machine Learning Research (01/2024)
Acknowledgments
This work was supported in part by National Science Foundation grant IIS-2006861 and National Institutes of Health grant U01AG070112.
References
Emnanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):6446-634) 2017.
Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In IJCAL, 2021.
Vikraman Arvind, Frank Fuhlbrücc, Johannes Köbler, and Oleg Verbitsky. On weisfeiler-leman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sciences, 113:42-59, 2020.
James Atwood and Don Towsley. Diffusionnconnvlutiinna neural networks. Advances in newral informalion processing systems, 29, 2016.
Tászló Babai and Ludik Kucera. Canonical labelling of graphs in linear average time. In 20th Annual Symposium on Poundations of Computer Science (sfes 1979), pp. 39 46. IEEE, 1979.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Bal- amurugan, Michael M. Bronstcin, and Haggai Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Regresentations, 2022.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. Advances in Newrul Information Processing Systems, 34:2625 2640, 2021a.
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 Zafeirion, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389 410, 1992.
Dexiong Chen, Leslic O'Bray, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. In International Conference on Machine Learning, pp. 3469 3489. PMIRR 2022.
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, Pictro Liò, and Petar Veličkovié. Principal neighbourhood aggregation for graph nets. Advances in Newral Information Processing Systems, 33: 13260 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 International Joint Conferences on Artificial Intelligence, pp. 2126 2132, 2021.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint 2rXiv:2012.0900 2020.
11

---

Published in Transactions on Machine Learning Research (01/2024)
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Bench- marking graph neural networks. Xiv preprint arXi::2003.0098: 2020.
Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang, How powerful are k-hop message passing graph neural networks. Advances in Newral Information. Processing Systems, 2022.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Leurning on Graphs and Manifolds, 2019.
Fabrizio Frasca, Beatrice Bevilaequa, Michael M Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. Advances in Newral Information Processing Systems, 2022.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th international conference machine learning, pp. 1263-126221 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 Neurol Networks, 2005., volume 2, pp. 729 729-734.
IEEE, 2005.
Martin Grohe. Descriptive complerity, cononisation, and definable graph structure theory, volume 47.
Cambridge University Press, 2017.
Martin Grohe and Martin Otto. Pebble games and lincar 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-10344 2017.
Kurt Hornik. Approximation capabilities multilayer feedforward networks. Newral networks, 4(2):251-25)) 1991.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 255):359-388 366, 1989.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovee. Strategies for pre-training graph neural networks. In International Conference 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 Newral Information Processing Systems, 2020.
Md Shamim Hussain, Mohammed J Zaki, and Dharmashankar Subramanian. Global self-attention as a replacement for graph convolution. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Dala Mining, pp. 655 665, 2022.
Stefanic Jogelka. Theory of graph neural networks: Representation and learning. arXiv:220,007691 2022.
arXiv preprint
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létournean, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34: 21618 21629, 2021.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovee. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465 33:4465-4448, 2020.
12

---

Published in Transactions on Machine Learning Research (01/2024)
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations, 2016.
Liheng Ma, Chen Lin, Derek Lim, Adriana Romero-Soriano, Puncet Dokania, Mark Coates, Philip Torr, and Ser-Nam Lim. Graph inductive biases in transformers without. message passing. ar preprint arXiv:2305.1 2023.
Haggai Maron, Heli Ben- Nen-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2018.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neurol informalion 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 Dala Science Workshop (DSW), pp.
IEFE, 2018.
Christopher Morris, Martin Ritzert, Malthias Fey, William Hamilton, Jan Eric Lenssen, Gauray 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. ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020a. URL www. www.grrppleerrinnggo i1
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Advances in Newral Information Processing Systems, 33:21824-2188 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 2021.
Christopher Morris, Gaurav Rattan, Sandra Kiefer, and Siamak Ravanbakhsh. Speqnets: Sparsity-aware permutation--qquivrrian graph networks. arXiv preprint arXin: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.
Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. k-hop graph neural networks. Newral Networks, 130:195-205, 2020.
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, 34:21997-22009, 2021.
Omri Puny, Heli Ben-Hamu, and Yaron Lipman. Global attention improves graph networks generalization. arXiv preprint arXix:2006.075: 2020.
Chendi Qian, Gaurav Rattan, Floris Geerts, Mathias Niepert, and Christopher Morris. Ordered subgraph aggregation networks. Advances in Neural Information Processing Systems, 35:21030- 030-21045,, 2022.
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Federico Monti. Sign: Scalable incoption graph neural networks. arXio preprint arXiu:2004.11198, 2020.
Dylan Sandfelder, Priyesh Vijayan, and William L. Hamilton. Ego-gnns: Exploiting ego structures in graph neural networks. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5523-8527 IEEE, 2021.
Ryoma Sato. survey on the expressive power of graph neural networks. arXio preprint arXi:20033.04078 2020.
13

---

Published in Transactions on Machine Learning Research (01/2024)
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Dala Mining (SDM), pp- 333-341. STAM, 2021.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural nebworks, 20(1):61-80) 2008.
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 messagepassing. Advances in Neural Information Processing Systems, 33: 14143 14155, 2020.
Qing Wang, Dillon Ze Chen, Asiri Wijesinghe, Shouheng Li, and Muhammad Farhan. N-WL: A new hierarchy of expressivity for graph neural worksrks In The Fleventh International Conference on Learning Representations, 2023.
Boris Weisfeiler and Andrei A Lehman. reduction of graph a canonical form and an algebra arising during this reduction. Nauchno-Tedie Technicheskaya Informatsia, 2(9):12-16, 1968.
Asiri Wijesinghe and Qing Wang. 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 Stefanic Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di Hc, Yanming Shen, and Tic- Yan Liu. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34:28877-28888, 2021.
Jiaxuan You, Jonathan M Gomes Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. In Proceedings of the AAAT Conference Artificial Intelligence, volume 35, pp. 10737-10745, 2021.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J 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.
Bohang Zhang, Guhao Feng, Yiheng Du, Di He, and Liwei Wang. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests. arXie preprint arXi::2302.00000 2023a.
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of guns via graph biconnectivity. In The Eleventh International Conference on Learning Representations, 2023b.
Muhan Zhang and Pan Li. Nested graph neural networks. Advances in Neural Information Processing Systems, 34, 2021.
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.
14

---

Published in Transactions on Machine Learning Research (01/2024)
A Proofs of Theorems and Lemmas
A.1 Proof of Theorem 1
Theorem 1. NC-1-W2 WL 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, we prove the correctness of the following two statements. (1) If two graphs are determined to be isomorphic by NC-1-WT, 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-WL but can be distinguished by NC-1-WL.
(1) Assume two graphs 9
(P.F,Y) cannot be distinguished by NC-1-WL. Then, according to Algorithm [ at any itcration
(V, X) and H
(l-1)) ENN. ((ffomm (L-1) ,oz de-1) Bu,,, E (u, u2) E EB)) lo [ovv]] 1.2. we ((d5") ((ale!)) Ig (Hth (e-1) dd "M-""M/ 22 E Np (2), E FB) lp Ie [EPP]]
have {((0
((-1)
This naturally implies that, at any iteration L 1,2, we have {{((5 c (e-1) (lell-")u Jue E N..) lo | vve
Hl ((dr", (4 e NpH)) lo e p]] This indicates that 1-WL cannot distinguish graph and graph H as well.
(2) In Figure (a), we provide several pairs as examples to show that there exist such non-isomorphic graphs that can be distinguished by NC-1-WL but cannot be distinguished by 1-WL.
A.2 Proof of Theorem 2
Theorem 2. WL is strictly less powerful than 3- WL in distinguishing non-isomorphic graphs.
Proof. To prove that NC-1-WLis is strictly less powerful than 3- 3-WL, we prove the correctness of the following two statements. (1) If two graphs determined to be isomorphic by 3-WL, then they must be indistinguishable by NC-1-WL as well. (2) There exist at least two non-isomorphic graphs that cannot be distinguished by NC-1-WL but can be distinguished by 3-LL.
We first describe the details of kL in Algorithm 2 following Sato 2020). k- &- aims at coloring each k-tuple of nodes, denoted as v E Vk The i-th neighborhood each tuple v = (01, ".. .4) is defined as No.: = {(v1,..., U1-1, 8, 0141, rk]ls V}. Similarly, The i-th neighborhood of each tuple p (Pi, P2. .pk) is defined as Np. {(I).... .Pi-1, (Pp+,,,...PPk)) .Pk)lt E P}. The initial color of each tuple is determined by the isomorphic type of the subgraph induced by the tuple, i.e., G[v]. (See Sato (2020) for details). Note that the nodes in G[v) are ordered based on their orders in the tuple v. Thus, ([oH)G(o)) = HAsH(H(p)) iff (a) Fo. Pp. for = 1,2, A and (b) (12,2)) E E iff (p:.P;) E F.
(1) Assume two graphs G = (V, E,E and H. = (P.F,Y) are determined to be isomorphic by 3-WL G and H have the same number of node: denoted as n. Then, according to Algorithm 2 we have ((c (0) I0 E V&n = ((ap)) e p*]]. There always exists an injective mapping g V + P such that cp = d s(e) (L..,, H[su()(u)) = Hasn(H[g(v))),, Ye E v* Here, we directly apply to a tuple v for ease of notation, which means g(e) = =((01, 02, v3)) = (g(v1).g(v2) ((v)))g((s)) Without losing generality, we assume g maps by Pj for 1, 2...... .n. Then, we can obtain the following results.
(a) We can consider the tuples v = (v,, Uy By), Veg E V. Given & = do) we can derive Lú, yy,, Vu, E V.
(b) We further consider the tuples v (1y, U.), Vuz E V. According to do = d(0) "(()" we have De, yp We can also have p, E Np, iff u, e No, (Otherwise, ( & d00))
Two graphs with different numbers of nodes can easily distinguished by comparing the multisets node colors, given that the cardinalities of the two multisets are different.
15

---

Published in Transactions on Machine Learning Research (01/2024)
Algorithm k-WL for graph isomorphism test
Input: Two graphs g = (V, X) and H = (P..
(0) - ( Ve E vk
HAsH(H(p)), vp pk
repeat (L- 1,2,
if Uo (/c0-11000 return 7 H.
- V* + lidp
11 E P*B then
end if
for v E V do
u E No,i)) for ,,
Co + HASH co v,1 0,2 0.2. co.k)
(f-1) (1)
end for
for p E pk do
(0)
p. ((uq 11- E Npit), for 1,,,
dp + HASH dp ((-1) (0) d.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-WT. but can be distinguished by 3-WL.
(c) At last, we consider the tuples v = (Uzr fr, Uw.) Veg V. Similarly, based on ( =000 "[w) we can obtain Ze = Up. and Te... Yp.. Also, we can have Pr.Pw Pw E Nop iff Ur, ENy, and (pr. F iff (Ur: Uw) E E. Now, we consider performing NC-1-WL (Algorithm 1 on these two graphs G = (V, X) and H (P, to color each node o V and p E P. We have the same injective mapping g: V - P as above. Based on (a), we have Mo(v): Ve E V, which indicates co = d Ve E in the NC-1-WI. coloring process. Similarly, according to (b) and (c), we have He E N. (dd la E Ng Vu v and [[(cc ( Bu, ug e No, (u1, U2) E E}} (H d M11, 92 E N (2),2) FH), Ve V, respectively. Therefore, with initial colors satisfying such conditions, NC-1-WI. cannot distinguish g and H since co (l-1) = d(l")) Ve E V always holds for ( 1,2, In other words, (1of-1) v E V)] = ( Ip iterations (i.e., E) we apply.
P}] always holds no matter how many
(2) Tn 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, our NC-1-WL reduces to 1-WL since there do not exist any neighbors that are communicating.
A.3 Proof of Theorem 3
Theorem 3. Let M: 9 + Rd be an NC-GNN model with a sufficient number of layers following Eq. 5 M is as powerful as NC-1-WL distinguishing non-isomorphic graphs if the following conditions hold: (1) each layer E, communsicate" (1) eggregate (f), and f uuddate (1) are injective. (2) The final reodout function readout is injective.
16

---

Published in Transactions on Machine Learning Research (01/2024)
Proof. We prove the theorem by showing that NC-GNN model that satisfies the conditions yield different embeddings for any two graphs that are determined to be non-isomorphic by NC-1-WT. We denote such model as M. Assume two graphs G1 = (V1, X1) and G2 = (V2, E2, are determined to be non-isomorphic by NC-1-WL at itcration L. Given that feadout of M can injectively map different multisets of node features into different embeddings, we only need demonstrate that M, with sulficient number of layers, can map 91 and 92 different multisets of node features.
To achieve this, following Xu et al. (2019), we show that, for any iteration there always exists injective function such that h = ((c)) ) where h the node representation given by the model M and e is the color produced by NC-1-WL. We will show this by induction. Note that here o represents a general node that can be a node in 91 or G2.
Let denote the injective hash function used in NC-1-WL. For e 0, we have c 6(x,) and h Ee. Thus, could be ø for = 0. Suppose there exists an injective function şo such that h ( p (t 1) Yu E V1 U V2, we show that there also exists such an injective function for iteration According to Eq. we have
! f Juddate" (8) (n
f Saggregate ( (H N..l).
fcommunicate" (0) (H 1 u2 E No, (u1, u2) E E})))
According to h (f-1) = c(c ((c(t-1)) we further have
h0 fudatee (0) (p(c((t))), faggregate (6) (H(p(ch-)) (llecef-))luENNN.))) NoH)).
(8)
Scommunicate (H(Hpp((h"")) ((d ( E No, (21, E EB
where coommuniaate" (0) f Iggregate (0), f Jupdato (8) and & are all injective functions. Since the composition of injective functions is also injective, there must exist some injective function v such that
h0 = + c 1)-1), ((alt-1) 1/ E NoTh (lllfhh-" 1) oo---111 u1, U2 E No, (u1, uz) E EH)
(9)
Then, we can obtain
h (5-) (0
(1-1) (Hc(-")) E N.B.. (HHH))) oz (le11) u2 No. (u1, (2) (EH))
c
(10)
Then, 40 +o 0 -1 1 is an injective function such that h = (o(c Vi V...
Therefore, it is proved that for any ileration f, there always exists an injective function such that h = s((ee) (0)
). Since NC-1-WL determines 9i and G2 to be non-isomorphic at iteration L, we have also have ((h!'lo E Vi} ((((c!)) E Vil,, (1 W E 132}} = ((((d)) EV),, and &o is injective. Hence, the multisets of node features produced by M for Gi and G2 are also different, i.e., (11"")o Vi]] o 41001/0 E V2Jl, which indicates that the NC-GNN model M can also distinguish G1 and G2-
((c!)) w ViBl # (1 / V2]]. As proved above,
A.4 Proof of Lemma 4
Lemma 4. Assume X is countable. There exist two functions fi and f2 so that h(X, W) EiEx
E WeW fe(f((w1)+ + fi(w2)) is unique for any distinct pair of (X, W), where X S X is multiset with bounded cardinality and W C W {f( wi, W2)) [w, u2 E X3 is a multiset of multisets with bownded cardinality, Moreover, any function g on (X, W) con be decomposed 9(X, W) = +(Enxx f1(x) + E Ce New f2(F((w1) (1(2))) for some function db
17

---

Published in Transactions on Machine Learning Research (01/2024)
Proof. To prove this Lemma, we need the following fact, which is also used by Xu et al (2019)
Fact 1. Assume X' is countable. ((X) = Ezex N N-2(x) is unique for any multiset X S d' of bounded cardinality, where the mapping Z ::4 X + N is an injection from I E X to natural numbers and N E NN 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 = (Sx, mx); where Sx is the underlying set of X and mx Sx + Zz gives the multiplicity of the elements in Sx. Hence, need to uniquely determine the elements in Sx and their corresponding multiplicities, using the value of h(X). Let f21, F denote the countable set X' (n could go infinitely). Without losing generality, we assume Z maps x1 + O, 22 + 1, elc.. Then we can compule (g,r) = h(X) diomod N- where q is the quolient and r is the remainder. If q = O, we can conclude ø1 is not in 5x. If q > O, then #1 is in Sx and q gives the multiplicity of x1. Afterwards, we use the remainder r to replace h(X) and compute (q.r)= = h(X) divmod N-1, and the results can be used to infer if 22 is in Sx and its multiplicity. We can do this recursively until = 0. Note that X has bounded cardinality and N e N 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 multiset X = {(z11 23, æall and Z injectively maps the elements in X to natural numbers, thus obtaining a multiset ({0, 2B}. Let N = 4. We have ((X)= = -Ezex N- = 4-0 + 4-2 + 4-2 = 9/8. Next, following our description above, we show how we can infer X by the value of h(X). First, according to 9/8 divmod 4 = (1, we can conclude that there is one In in X. Then, with 1/8 divmod 4-1 1/8), we can infer that 22 is not in X. Finally, we have 1/8 divmod 4-2 = (2, which indicates that there are two 23 in X. We can stop the process since the remainder reaches O.
Let us go back to the proof of Lemma 4. Since X' is countable, W = [fl w2 Me w2 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[ XX| + ( for all (X, W) pairs. Let Z1 : X' + Noda be an injection from X E X' to odd natural numbers. We consider fi = N -1rr),,, For ease of notation, we let (HHr, wzHl) = fww) fi f(w)). According to Fact 1, v0 (1 w,, w2){) is unique for any Hwi, w2]) E W. We define the set y = (W w2 w2)) [w), W2 E X). Thus, y is also countable as W. We consider Z2 : y + Neven be an injection from y E ) to even natural numbers and f2 - Then, the resulting h(X, W) = =Exex [1 + Eit Ho New f2(F1 (w1) ) + fi (wx)) is an injective function on (X, W). In other words, we 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 we show in Fact 1. Then, we can uniquely obtain X (f..., its underlying set Sa and multiplicities)) based on the odd natural numbers. According to the even natural numbers, we can infer (V((Ww, (2)))[((,, wz)) E WJ.. Further, since (((w), W2))) }}) is injective, we can uniquely obtain W.
For any function g on (X, W), we can construct a function & such that ((h(X, = g(X,W). This is always achievable since h(X, W) is injective.
]
A.5 Proof of Lemma 5
Lemma 5. Assume X is countable. There erist two functions fi and fa so that for infinitely many choices of e, including all irrational numbers, h(c, X. W) (1+ (cf((c)+++++ ExEx fi(x) + E(w,, WBW fe(fi(w1) + fi fi(w2) is unique for any distinct 3-tuple of (c, X, W), where c X, cardinality, and W C W = [ffw, w2 Hol, W2 E X} 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) = p((1 + +ff((()) + +ZEX fi(x) +
X C X is a multiset with bounded
Σ Bew fa(Fi(w:) + fi (w2)) for some function sp
Proof. We consider the same functions f1 = N Zi() and f2 Zz(z) as our proof for Lemma 4. We prove this lemma by showing that, if e is an irrational nunber, l[c, X, W) + h(c, W') holds for any (c,X, # X', W'). We need to consider the following two cases.
(1) cf = é' but (X, W)+ + (X', W"), according to Lemma 4, we have ELEx f1 + [1(w2)) # Exex fi (a) + + Eumnwweeww f2(fi(u)) (ww)+/fr +1(w))) Thus, we can obtain h(c, X, W) # h(c', X', W').
Eq wes EHeweeee New fe(fi +
18

---

Published in Transactions on Machine Learning Research (01/2024)
(2) If of d', we show h(c, W) * h(c',',
by contradiction. Assume h(c, X, W) = h(d,X', ,W),, we
have
(1+c)/i(e) + Σ f1(x)
E
[(S((w)) + [1(w))) =
sE
(11)
(1+e)fi(c) + Σ
fi(x)
+
E
(2ff(w])) + fi(w2))
zEX'
This can be rewritten
= (fi(c)+ + Σ
f1(2+ +
Σ
f2(fi(w1) + fi (((2))
TEX'
(12)
- -(i(o)+ E +
Σ
+ f((z))
TEX
WeW
Since fi(c)- - fi (c') # and it is rational, given e 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 a contradiction. Thus, if e * d' we have h(c, X, () + ,''''',W X',W). W").
For any function g on (c, X, W), we can construct a function such that (0(((e, X, W)) = g(c, x, W). This is always achievable since h(c, X, W) is injective.
Further justification for the first layer. If the input features X are one-hot encodings, fi is not necessary and thus can be removed. In other words, we can show as follows that there exists an f2 such that N'(c, X, W) = (1 c)o Exex x + Hewe,, f2(w) w2) is unique for any distinct 3-tuple of Xc, W). Note that Σxex is injective if input features are one-hot encodings, and the value of Exex Z must be composed of integers. In addition, e/ ([((w), w2))) wi + u2 is also injective. Similarly, We define the set Y" ( (f, W2 Bu),, wy X). We consider Zz )" - N be an injection from y E )" to natural numbers and /22 = N- N-22(1), where N >> |W] for all W. Then (ec,, X, W) = (1+c)c+ (++e)c+Erex+ E+ (o2,, L2 (2 +w2) is injective, since E [((m1,2)) fa(wi + w2) is unique for any W and is number (0, 1), thus differing from the integer-valus valued Exex This is why we do not need another MLP to model f(() in Eq. 66
B More Comparisons with Related Work
B.1 NC-GNN vs. Counting 3-Cycles
Since our NC-GNN depends on the existence of 3-cycles in the graph, a natural question is how our NC-GNN compores to the abilily count I-cycles. Here, we theoretically prove that NC-GNN has the ability to count. 3-cycles, but not limited (not just equivalent) to that. To achieve this, we show that our NC-GNN (1) has the ability to count 3-cycles and (2) goes beyond just counting 3-cycles (i.c., has the ability to capture patterns that 3-cycles counting cannot). Let's first prove (1). According the conclusion from Theorem 3 and Lemma 5 the Scommunicate in our implemented NC-GNN (Eq. (6) is injective, thus different W (the multiset of multisets used to denote the edges among neighbors), will lead to distinct outputs. Given that the number of 3-cycles in corresponds to the cardinality of W, the 3-cycle counting ability can be included since different cardinalities can be captured by NC-GNN due to the proven injectivity. To prove (2), we can give an example that NC-GNN can differentiate but 3-cyele counting cannot. Assume node has four neighbors i, P, q, and two cases Wi = ((((,, vy]), {fv,, 1p)) and W fll(,, myJ), (ty, Dg))). . By solely relying on 3-cycle counting, both scenarios appear identical as both contribute two 3-cycles. In comparison, NC-GNN can differentiate them thanks to the injectivity. Essentially, NC-GNN not only captures the cardinality of W (which is equivalent to counting 3-cycles), but also capture the interaction among neighbors (iee., the elements in the multiset. W). More importantly, during training, such interactions are captured via feature interactions in the embedding space and can be learned according to the supervised task at hand.
We empirically verify this in Section 6 As shown in Table 2 NC-GNN exhibits an obvious performance improvement over simple 3-cycle counting.
19

---

Published in Transactions on Machine Learning Research (01/2024)
B.2 NC-GNN vs. GraphSNN
NC-GNN incorporates edges among neighbors in a more general and flcxible way, enabling it to capture and model the interactions associated with these odges based on the learning task. To be specific, in GraphSNN, handerafted structural coefficients are defined to encode overlap subgraphs between neighbors. As defined in Eq. (4) in the GraphSNN paper, the structural coefficient for a specific overlap subgraph is determined by the number of nodes and edges in the overlap subgraph. Such coefficients are handcrafted. Moreover, two different overlap subgraphs with the same mumber of nodes and edges would have the same structural coefficients, which is less discriminative. In comparison, we mathematically model the edges among neighbors as a multiset of multisets, and such interactions are modeled by feature interactions in the embedding space and can be learned according to the supervised task on hand. Therefore, our model more general and flexible.
Compared to GraphSNN (Wijesinghe & Wang 2022)
We note that many other expressive GNNs, as well our NC-GNN, are proved to have expressive power between 1-WL and 3-WL in terms of distinguishing non-isomorphic graphs, but what exact additional power they obtain and how they compare to each other remains unclear and challenging in the community. Having said this, here, we can informally prove that our NC-GNN is more powerful (or not weaker) than GraphSNN.
GraphSNN proposes that overlap-isonorphissn lies in between neighborhood subgraph isomorphismn and neighborhood subtree isomorphism. However, GraphSNN does not fully solve the local ivoropp-isomorphism problem. Instcad, GraphSNN encodes the overlap subgraph between neighbors with handcrafted structural coefficients. As defined in Eq. (4) in the GraphSNN paper, the structural coefficient for specific overlap subgraph is determined by the number of nodes and edges in the overlap subgraph. This will lead to the situation that two different overlap subgraphs with the same number of nodes and edges would have the same structural coefficients. In this case, GraphSNN will produce the same structural coefficients. In contrast, our NC-GNN can disferentiate these two different overlap subgraphs by capturing the fact that the edges are connecting different nodes in the two overlap subgraphs. This because of our proved injectivity in Lemma $ and 5 Because of such injectivity, NC-GNN can tell from the representation which two neighbors are connected (i.e., feommunicate in Eq. (5) is injective).
B.3 NC-GNN vs. Subgraph GNNs
Compared to subgraph GNNs such as NGNN (Zhang & Li 2021 and GNN-AK (Zhao et al., 2022 y our NC-GNN is more efficient in terms of time and memory complexity. Subgraph GNNs use base GNN to encode the neighborhood subgraph of each node and then employ outer GNN on the subgraph-encoded representations. They need to perform message passing for all nodes in subgraphs. Note that it is also needed to store many more node representations than regular message passing since the same node in different neighborhood subgraphs has different representations. Thus, the memory complexity is O(ns) and the time complexity is ((nds), where 8 the maximum number of nodes in the considered k-hop neighborhood subgraph. Note that grows exponentially with the depths of the neighborhood subgraph, thus limiting the scalability. In contrast, our NC-GNN proserves the locality of regular message passing. We still update representations for n nodes in the original graph as regular message passing, instead of all nodes in n. subgraphs.
Since the structure considered in NC-GNN for each node form a one- hop subgraph, we further compare our NC-GNN to subgraph GNNs when using the one-hop ego network as the subgraph to encode. Here, we describe the eract time and memory consuming (without big O notations) to explain further why NC-GNN is more efficient than subgraph GNNs in time and memory even when only one-hop subgraphs are used in subgraph GNNs. Let us take NGNN with one-hop ego networks an example.
Time.
Let us consider the computational time for obtaining only one node representation. Suppose the node has d neighbors, and there are l edges among the d neighbors. Hence, in the one-hop ego subgraph of this node, there are (d +d+t) edges in total. Let us only consider the time consumed by the inner GNN module of NGNN and suppose the inner GNN has only one layer of message passing. (This is the simplest NGNN model and the practical model could have more layers of message passing.) Note that the message passing in the inner GNN is performed for all (d + 1) nodes. In other words, each edge in the one-hop ego subgraph
20

---

Published in Transactions on Machine Learning Research (01/2024)
corresponds to two message-passing computations (for the two ending nodes connected by the edge). Hence, the exact time complexity is 2(d + t) for NGNN to obtain the representation for this node.
For our NC-GNN, the message passing is only performed for the center node. We aggregate the messages from d neighbors and t edges among neighbors. So the exact time is (d + t). Hence, our NC-GNN only needs half of the time required by (the most efficient version of) NGNN.
Memory. For graph, NC-GNN needs to store (n + min(m, 37') representations, where m is the number of edges and T is the total number of triangles in the graph. We have multiplier 3 because each triangle has three edges and their corresponding representations need to be saved for MLPp as in Eq. (). If 37 > m, we can alternatively save all (h + hw) for any edge (v, u). This is why our additional memory requirement compared to regular message GNN is min(m,37) 37).
In comparison, addition to n node representations, NGNN needs save 2m additional representations. To be specific, for each edge (v, u), has save the representation of node u v's subgraph and the representation of node in u's subgraph. Hence, NGNN needs to store (n+ + 2m) representations totally.
Therefore, NGNN need to save ((n 2m) (n + min(m, 37))), which is m, more representations than our NC-GNN. The number of edges m is usually larger than n, which accounts for a large proportion of the total memory cost.
B.4 NC-GNN vs. KP-GNN
NC-GNN and KP-GNN passing share the insight of exploiting subgraph information. However, NC-GNN is distinct from such k-hop message passing (Nikolentzos et al., 2020 Feng et al. 2022). The key differences are following. First, the KP-GNN work mainly focuses on formulating the k-hop message passing framework and analyzing its expressive power. In rost, we dedicate to the consideration of edges among neighbors, leading to the effective and efficient NC-GNN. Second, the KP-GNN model considers the subgraph information by encoding the number of periphoral edges, while we are modcling the communication among neighbors. other words, we incorporate feature interaction among neighbors (i.e., the 3rd term in Eq. (G). With our dedicatedly designed model, our proof of expressivity totally different from this existing work. Last, addition the neural models, we also propose the NC-1-WL a deterministic algorithm for the graph isomorphism problem, which has not been considered by this existing work.
B.5 Time Complexity Comparison with Related Work
We compare our NC-GNN with several representative expressive GNNs in Table Our NC-GNN achieves a better balance between expressivity and scalability.
Table 6: Comparison of expressive GNNs. d is the maximum degree of nodes. T is the number of triangles in the graph. l 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 NGNN compares to WL.
Method
Memory
Time
Expressiveness upper bound Scale to large graphs
GIN
((n)
(nd)
1-WL 1-WL 3-L
1-2-3-GNN
O(13)
Onn))
PPGN
O(n²)
O(n3)
3-L
NGNN
(ns)
O(nds)
1-WL Unknown
NC-GNN (ours)
O(n (in 37))
O(n(d + +t)
1-WL 3WL
/
21

---

Published in Transactions on Machine Learning Research (01/2024)
Table 7: Results (%) on MUTAG, PTC, and NCT1.
Dstaset
Avg. #Messagene
GIN
NC-GNN
MUTAG
89.415..6
90.615.6
PTC
0.005
64.6.7.0
64.415..
NCII
0.005
82.7.1.7
82.511.
C Experimental Details
C.1 Comparison MUTAG, PTC, and NCI1
Graphs in certain datasets do not have many odges among neighbors (í.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. Here, in Table we provide the empirical results MUTAG, PTC, and NCI1 as examples. As anticipated, the results confirm that NC-GNN performs similarly (with statistical variance) as GIN in scenarios where graphs have sparse connections among neighbors. This is aligned with the theoretical expectations, given that the key innovation of NC-GNN, i.e,, the modeling of edges among neighbors, does not have much opportunity to contribute to expressiveness such graphs
C.2 Dataset Statistics
The dataset statistics shown in Table g
Table 8: Dataset Statistics. Avg. #MessageNc denotes the average #MessggeNc per node.
Dataset
Task
Domain
#Graphs
Avg. #Nodes
Avg. #Edges
Avg. #MessageNe
COLLAB
Graph clessification
Social network
5000
74.5
4915.6
5016.2
PROTEINS
Graph classification
Bioinformaties network
1113
39.1
145.6
2.1
IMDB-B
Graph clessifiration
Social network
1000
19.7
96.5
58.5
IMDB-M
Graph classification
Social network
1500
13
131.8
70.6
ogbg-pps ppa
Graph clessifiattinn
Bioinformaiis network
78200/45100/34800
243.4
2266.1
179.3
PATTERN
Node classification
Social network 10000/2000/201
118.9
6079.8
3440.1
CLUSTER
Node classification
Social network 10000/1000/100
117.2
4303.8
1301.5
C.3 Model Configurations and Training Hyperparameters
For efficiency, we do not tune the model configurations and training hyperparameters for NC-GNN extensively. Since NC-GNN model is natural extension of GIN, we usually use the model configurations and tuned hyperparameters of GIN from the community as the starting point for NC-GNN and then perform grid search for the following hyperparameters 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 the jumping knowledge (JK) technique or not, and (4) using a residual connection or not. To ensure fair comparison, we only consider employing techniques (3) and (4)
the datasets where the baseline GIN model also uses them.
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 of 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 g For each datasct from GNN Benchmark, we have several NC-GNN models under different parameter budgets, as described in Section Accordingly, we list the configurations and hyperparameters for all of these models for reprodueibility.
22

---

Published in Transactions on Machine Learning Research (01/2024)
Table The selected model configurations and training hyperparameters of NC-GNN on all datasets.
Dataset
COLLAB
PROTEINS
IMDB-B
IMDB-M
ogbg-ppa
PATTERN
CLUSTER
# Layers
5
5
5
5
4/4/16 70/ 70/154/78
4/4/16
# Hidden Dim.
64
64
64
32
300
70/154/78
/
/
/
Residual Con.
Initial LR
0.005
0.001
0.001
0.005
0.01
0.001
0.001
Step size of LR
20
50
50
50
30
20
20
Mul. fac. LR
0.5
0.5
0.5
0.5
0.1
0.5
0.5
Batch size
256
32
128
32
32
32
Dropout rate
0.5
0
0.5
0.5
0.5
0/0.1
0/0/0.5
# Epochs
100
100
200
300
80
100/140/140
100/100/200
C.4
Experimental Setup on ogbg-ppa
Differing from TUDatasets, the graphs in ogbg-ppa have edge features representing the type of prolein-protein association. In order to apply NC-GNN to these graphs, further define 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. (019)) The layer-wise formulation of our NC-GNN model with considering edge features is
1/0 M (1++)))
E RELU(H ((-11) (t-1) +ewr)+ MEN.
Σ 11,, (21,a2)EE
((-1) + Gu: wa) MLP (h((-1) + uug 1
which is natural extension of Eq. by including edge features. eav is the edge feature associated with edge (u,v). v). In practice, usually apply embedding layer to input edge features such that they have the same dimension the node representations.
For reference, the GIN model with considering edge features Hu et al. 2019 can be formulated as
h MLP ( (11+e0))
Σ meN.
RELU(h ((-1) + e..)).
C.5
Experiments on Counting Triangles
Specifically, following prior work (Chen al. 2020 Zhao al. 2022), we use the synthetic dataset from Chen
al. 2020 evaluate the ability count triangles in graph. There are 5000 graphs in total. As (Chen
ct al. 2020 Zhao et al. 2022). use the same 2166//%%/555 (training/validationn /aa///aaaaiannteeeeeeeeeeeeeeeee (etsoo) split. We perform
2 random runs and the comparison of average MAE is shown below.
Table 10: Results (%) on counting triangles.
Model
Test MAE
GIN
0.3569
GIN-AK
0.0934
GIN-AK+
0.0123
NC-GNN
0.0081#0.000
We compare NC-GNN GIN and GNN-AK (with GIN the base model). Our NC-GNN achieves the lowest MAE of 0.0081, outperforming GIN and GIN-AK by large margin and reducing the MAE by over 90%. We also include the result of GIN-AK+ which incorporates additional strategies such distance encoding
23

---

Published in Transactions on Machine Learning Research (01/2024)
and context encoding to enhance performance. Despite these improvements, vanilla NC-GNN model still putperorms GIN-AK+ in counting triangles. According to the results of the above experiment and the results in Table 5 our NC-GNN is more time- and memory-efficiet compared to subgraph-based GNNs while achieving practically good performance.
24


Reviews:
[{"review_id": "j1DHow8S6Y", "reviewer": "Reviewer_15SL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. In Table 1, the results show the proposed method is better than GIN but not so good compared with other methods.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "1. This paper proposes a provable and powerful GNN that is overall better than GIN. \n2. This paper provides good theoretical support.\n3. The experiments are comprehensive to me, including performance and efficiency.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I am not an expert in graph theory and am not very familiar with prior works in terms of the expressive power of GNN. Here are my suggestions.\n1. It seems that the performance/efficiency on graph classification tasks is not so impressive and significant (compared to GIN), at least not as significant as the performance/efficiency on node classification tasks. Could you please give some explanation or discussion?\n2. From my understanding, the authors mention that there are GNNs that mimic 3-WL (PPGN, RingGNN) and are more powerful than the proposed methods. It is better to summarize the comparison between these methods and NC-GNN.", "broader_impact_concerns": "No such concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "0zIZE4ewLN", "reviewer": "Reviewer_uBSo", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\nS1. The paper proposes a novel extension of the WL algorithm and show that it is more expressive than 1-WL. In contrast to most of the other similar proposals, the additional computational burden does not appear to be excessive. \n\nS2. Building on this contribution, the paper proposes a novel GNN and shows theoretically that it is as powerful as the proposed WL extension. \n\nS3. The paper reports on numerical experiments for multiple datasets that provide evidence that the proposed technique is efficient and can scale to larger datasets.\n\nS4. The paper is well written and provides a clear description of the proposed method and the experiments that support the claims. \n\nWeaknesses\n\nW1. The paper provides theoretical results demonstrating that the algorithm achieves expressiveness between 1-WL and 3-WL. This is similar to what is achieved by multiple algorithms at this stage. The theoretical results do not provide any further refinement. The proof approaches for Theorems 1 and 2 are relatively standard and straightforward. The proofs of Theorems 3 and Lemmas 4 and 5 are not trivial extensions of the approach in Xu et al. (2019), but they do follow similar ideas. The paper would be considerably stronger if it could provide a richer characterization of the expressiveness achieved by the proposed method. Perhaps connecting it to some of the alternative hierarchies cited in Section 5 would be useful in this regard. For example, is there a connection to the N-WL work of Wang et al. (2023)?\n\nW2. Given that the theoretical characterization of the proposed method does not establish greater expressiveness than multiple other GNNs, the paper relies on empirical results to establish that it achieves similar (or better) performance with less computational overhead. \nAs a result, we need to rely on the empirical performance to demonstrate that the algorithm offers something beyond existing methods. At one point the paper claims that the proposed method “preserves the scalability of regular message passing in terms of computational time and memory requirement”. The experimental analysis of computation time is limited, with a comparison to only two other algorithms, one being GIN, with experiments still over relatively small datasets. The scaling behaviour is not obvious because already with PATTERN, the proposed algorithm takes approximately 6 times as long as GIN per epoch. The results don't really support the claim that the algorithm \"maintains scalability with reasonable overhead\" or that it “preserves the scalability of regular message passing”, given that PATTERN and CLUSTER only have an average of approximately 120 nodes per graph.   \n\nW3. There is no comparison to other state-of-the-art GNNs such as graph transformers. While it is reasonable to focus on GNNs of a similar class, there should be some comparison with at least some reference GNNs that achieve state-of-the-art performance (including some comparison of computational time and memory overhead). For example, K-Subgraph SAT (Chen et al. 2022 “Structure-Aware Transformer for Graph Representation Learning”), EGT (Hussain et al. 2022, “Self-Attention as a Replacement…”) or GRIT (Ma et al. 2023, “Graph Inductive Biases in Transformers without Message Passing”) offer superior performance for some of the studied datasets. These algorithms may indeed come at a much heavier computational cost or a much larger parameter count, but the paper should provide an indication of this, or a better explanation of why the techniques are not comparable. Some of these papers offer theoretical characterizations, e.g., generalizing WL as in Zhang et al. 2023, as the authors discuss very briefly in Section 5. Given that there is provable expressiveness of some form, it’s not clear why techniques that focus on hierarchies that are “more fine-grained than the WL hierarchy” should be excluded from experimental comparison.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes an extension to the Weisfeiler-Leman algorithm (NC-1-WL) that takes into accounts edges between neighbouring nodes. Theory is provided to show that the proposed algorithm has expressiveness between 1-WL and 3-WL. Based on this algorithm, the paper proposes NC-GNN, a graph neural network that is a differentiable neural version, and show that it is as powerful as NC-1-WL. Numerical experiments are provided to show that the proposed approach is effective and efficient.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. [Critical] Please include results that more effectively demonstrate the computational requirements and scaling behaviour of the proposed method. There are strong and important claims in the paper that the proposed method offers a balance between efficiency and power and that it preserves the scalability of message passing. I don't consider that this is supported by the experimental results currently. Even with relatively small graphs, the training time is a factor of 6 greater than GIN. In much larger graphs, where nodes have an average degree of 50, for example, and there is relatively strong clustering behaviour, it seems that the number of edges between neighbours could be high, leading to a relatively dramatic increase in the computational cost.\n\n2. [Critical] Please include some other baseline results that represent the state-of-the-art for the various tasks. This would provide a better indication of how close the proposed method is to achieving state-of-the-art performance. In particular, graph transformers, mixer architectures, or gated networks often tend to be the most effective for the analyzed tasks. \n\n3. [Non-critical] Please include a more in-depth discussion concerning the k-hop GNNs. Currently it is very brief. These would seem to offer similar computational overhead (but I may be wrong on this) and have the same theoretical guarantees. At the moment, there doesn't seem to be a clear experimental comparison and the discussion in the appendix is very brief and vague.\n\n4. [Non-critical] Please expand the discussion on recently proposed alternative hierarchies of expressiveness and, if possible, connect the proposed method to one or more of these hierarchies. In particular the N-WL work seems to me to have connections to the methodology proposed in this paper.\n\n5. [Minor] For reproducibility purposes, it would be helpful to have a more concrete description of the hyperparameter tuning process. It is not possible to reproduce the experimental process of \"tune them a little bit according to the validation results.\"", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fZaO8zDq4K", "reviewer": "Reviewer_8JPs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n1. The paper is well-written and easy to follow. \n2. I am not actively tracking the advance in GNNs; however, I believe this is significant work in GNN if the algorithm is new.\n\n## Weaknesses\n1. In Section 4 -- Complexity, the time complexity analysis involves $t$, the number of edges existing among neighbours of the nodes. I do not think this parameter is sufficiently natural and authors may discuss its relationship with $d$ and $n$.\n2. In Section 6, the performance on datasets with few edges among neighbours is omitted. While the authors mentioned that the performance of NC-GNN will be similar to GIN, it would be more appropriate to include them for completeness and discuss whether we should instead adopt GIN or other architectures in this situation.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces an innovative test for determining graph isomorphism. In comparison to the 1-WL test, the proposed test also takes into account the edges connecting the neighbours of the central node in the hash operation. They prove that this new test is strictly more powerful than the 1-WL test without incurring much memory and computational overheads. Motivated by this new algorithm, they devised the corresponding message passing GNNs and empirically showed its superior performance compared to GIN. The paper also highlights that the new algorithm frequently matches or exceeds the test performance of existing more expressive GNNs while benefiting from significantly lower time and memory complexities.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I am not aware of any critical issues. Authors may refer to the Weaknesses for suggestions to strengthen their work.", "broader_impact_concerns": "There aren't any major ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors proposed a variant of graph neural networks whose expressive power lies between 1-WL and 3-WL, while claiming similar computational costs as graph message passing. The authors performed thorough theoretical analysis and reasonable experimental comparisons against many existing approaches. The reviewers found the paper well-written, and the authors' response sufficiently addressed most of the initial concerns. While the proposed method does not necessarily have more expressive power than some existing methods, the reviewers nevertheless concluded that the proposed method is novel and the results are of interest to the community. All reviewers recommended acceptance.  

One minor comment: Was the full name of NC in NC-1-WL given somewhere?
Decision: Accept (poster)