Boosting the Cycle Counting Power of Graph Neural Networks with I$^2$-GNNs
Authors: Yinan Huang
Xingang Peng
Jianzhu Ma
Muhan Zhang
Venue: ICLR 2023 poster (2023)
Keywords: Graph neural networks

Abstract: Message Passing Neural Networks (MPNNs) are a widely used class of Graph Neural Networks (GNNs). The limited representational power of MPNNs inspires the study of provably powerful GNN architectures. However, knowing one model is more powerful than another gives little insight about what functions they can or cannot express. It is still unclear whether these models are able to approximate specific functions such as counting certain graph substructures, which is essential for applications in biology, chemistry and social network analysis. Motivated by this, we propose to study the counting power of Subgraph MPNNs, a recent and popular class of powerful GNN models that extract rooted subgraphs for each node, assign the root node a unique identifier and encode the root node's representation within its rooted subgraph. Specifically, we prove that Subgraph MPNNs fail to count more-than-4-cycles at node level, implying that node representations cannot correctly encode the surrounding substructures like ring systems with more than four atoms. To overcome this limitation, we propose I$^2$-GNNs to extend Subgraph MPNNs by assigning different identifiers for the root node and its neighbors in each subgraph. I$^2$-GNNs' discriminative power is shown to be strictly stronger than Subgraph MPNNs and partially stronger than the 3-WL test. More importantly, I$^2$-GNNs are proven capable of counting all 3, 4, 5 and 6-cycles, covering common substructures like benzene rings in organic chemistry, while still keeping linear complexity. To the best of our knowledge, it is the first linear-time GNN model that can count 6-cycles with theoretical guarantees. We validate its counting power in cycle counting tasks and demonstrate its competitive performance in molecular prediction benchmarks.

Published as a conference paper at ICLR 2023
BOOSTING THE CYCLE COUNTING POWER OF GRAPH NEURAL NETWORKS WITH I2-GNNS
Yinan Huang', Xingang Pengl.2 Jianzhu Ma², Jianzuu Muhan Zhang'
"Inttitute for Artificial Intelligence, Peking University
Schooo of Intelligence Science and Techology. Peking University Institute for AI Industry Research, Tsinghua University {yinan8 8144, x xingang. peng) gmmai)ggmmm......mmmm.mm emmal. ma majianzuu@t singhus edu. cn, muhan@pku. edu cn
ABSTRACT
Message Passing Neural Networks (MPNNs) are a widely used class of Graph Neural Networks (GNNs). The limited representational power of MPNNs inspires the study of provably powerful GNN architectures. However, knowing one model is more powerful than another gives little insight about what functions they can or cannot express. It is still unclear whether these models are able to approximate specific functions such as counting certain graph substructures, which essen- tial for applications in biology, chemistry and social network analysis. Motivated by this, we propose to study the counting power of Subgraph MPNNs, a recent and popular class of powerful GNN models that extract rooted subgraphs for each node, assign the root node a unique identifier and encode the root node' ' represen- tation within its rooted subgraph. Specifically, we prove that Subgraph MPNNs fail to count thon--than---cylee at node level, implying that node representations cannot correctly encode the surrounding substructures like ring systems with more than four atoms. To overcome this limitation, we propose 12-GNNs to extend Sub- graph MPNNs by assigning different identifiers for the root node and its neighbors in each subgraph. I2-GNNs' discriminative power is shown to be strictly stronger than Subgraph MPNNs and partially stronger than the 3-W 3-WL test. More impor- tantly, 12-GNNs are proven capable of counting all 3, 4, 5 and 6-cycles, covering common substructures like benzene rings in organic chemistry, while still keeping linear complexity. To the best of our knowledge, it is the first linear-time GNN model that can count 6-cycles with theoretical guarantees. We validate its count- ing power in cycle counting tasks and demonstrate its competitive performance in molecular prediction benchmarks.
INTRODUCTION
Relational and structured data are usually represented by graphs. Representation learning over graphs with Graph Neural Networks (GNNs) has achieved remarkable results in drug discovery. computational chemistry, combinatorial optimization and social network analysis (Bronstein al.
2017 Duvenaud et al.] | Khalil et al. Kipf & Welling 2016 Stokes et al. 2020 You et al.
2018 Zhang & Chen 2018). Among various GNNs, Message Passing Neural Network (MPNN)
one of the most commonly used GNNs (hoou et al. 20200 Veličković et al. 2017, Scarselli et al., 2008
However, the representational power of MPNNs is shown be limited by the Weisfeiler- Lehman (WL.) test (Xu et al., 2018 Morris et al., 2019), a classical algorithm for graph isomorphism test. MPNNs cannot recognize even some simple substructures like cycles (Chen et al. 2020).. leads to increasing attention studying the representational power of different GNNs and designing more powerful GNN models.
The representational power of GNN model can be evaluated from two perspectives. One is the ability to distinguish pair of non-isomorphic graphs, i.e., discriminative power. Chen et al. (2019) show the equivalence between distinguishing all pairs of non-isomorphic graphs and approximating all permutation invariant functions (universal approximation). Though the discriminative power provides way compare different models, for most GNN models without universal approximation

---

Published as a conference paper at ICLR 2023
property, it fails to tell what functions these models can cannot express. Another perspective is to characterize the function classes expressed by GNN model. In this regard, Chen et al. (2020) discusses the WL test's power of counting general graph substructures. Graph substructures are important as they are closely related to tasks in chemistry (Deshpande et al. 2002 Jin et al. 2018 Murray & Rees, (200)), biology (Koyutürk et al.. 2004) and social network analysis (Jiang et al, 2010). Particularly, cycles play an essential role in organic chemistry. Different types of rings impact the compounds' stability, aromaticity and other chemical properties. Therefore, studying the approximating power of counting substructures, especially cycles, provides fine- tieeggrinned and intuitive description of models' representational power and gives insight real-world practices.
Nevertheless, the difficulty of counting cycles is usually underestimated. Although claim that ID-GNNs can count arbitrary cycles at node level, the proof turns out to incorrect, since it confuses walks with paths (a cycle is a closed path without repeated nodes while walks allow repeated nodes). In fact, even powerful 2-FWI, test with cubic complexity can only count up to 7-cycles (Fürer 2017: Arvind et al. 2020). The difficulty makes question whether existing powerful models, such as ID-GNNs, can count cycles properly.
You et al. (2021)
ID-GNNs can be categorized into new class of GNNs named Subgraph GNNs (Cotta et al. 2021
Bevilacqua et al. 2021 Zhang & Li 2021 You et al. 2021; Zhao et al. 2021 Papp et al. 2021).
The core idea is decompose a graph into bag of subgraphs and encode the graph by aggregat-
ing subgraph representations, though the strategy of extracting subgraphs varies. See Frasca et al.) (2022); Papp & Wattenhofer (2022) for detailed discussions. Subgraph GNNs have demonstrated their impressive performance by achieving state-of-the-art results on multiple open benchmarks. Theoretically, the discriminative power of existing Subgraph GNNs known to be strictly stronger than WL test and weaker than 3-WL test (Frasca et al. 2022). However, it is fair to say we still do not know the approximation power of Subgraph GNNs in terms of counting substructures.
Main contributions. In our work, we propose to study the representational power of Subgraph GNNs via the ability count a specific class of substructures--cykee and paths, because they are the bases to represent some important substructures such as ring systems in chemistry. We focus on Subgraph MPNNs, subclass of Subgraph GNNs covering Cotta al. (2021) Zhang & Li (20TT); You et al. 2021). Our main contribution include
We prove that Subgraph MPNNs can count 3-cycles and 4-cycles, but cannot count 5-cycle or any longer cycles at node level. This result is unsatisfying because only a small portion of ring systems are 4-cycles. It also negates the previous proposition that ID-GNNs can use node representations to count arbitrary cycles You et al. [021].
To overcome the limitation, we propose 12-GNNs that extend Subgraph MPNNs by using mul- tiple node identifiers. The main idea is to tie each subgraph with a node pair, including a root node and one of its neighbors. For each resulting subgraph we label the node pair with unique identifiers, which is the key to increasing the representational power.
Theoretically, we prove that 1 GNNNN are strictly more powerful than WL test and Subgraph MPNNs, and partially more powerful than 3-WL test. Importantly, we prove I2-GNNs can count all cycles with length less than 7, covering important ring systems like benzene rings in chemistry. Given bounded node degree, 12-GNNs have linear space and time complexity w.r.t the number of nodes, making very scalable in real-world applications. To our best knowledge, I--GNN is the first linear-time GNN model that can count 6-cycles with rigorous theoretical guarantees. Finally, we validate the counting power of 12-NNNs on both synthetic and real- world datasets. We demonstrate the highly competitive results of I2-GNNs multiple open benchmarks compared to other state-of-the-art models.
PRELIMINARIES
Let G = EV be simple and undirected graph where V 31., is the node set and E C V x V is the edge set. We use z; to denote attributes of node i and eij to denote attributes of edge (i.j). We denote the neighbors of node i by N(i) & {i E Vi(ij) E E). A subgraph Gs = (Vs, Es) of G is a graph with V C V and Eg E.
In this paper, we focus counting paths and cycles. A (simple) L-path is sequence of edges [(i, 12). (1z, 1n), .... (iz, d such that all nodes are distinct: in * in # ... # i1411 A (simple) L- cycle is an T.-path except that in it+1. Obviously, we have T. 2 for any cycle. Two paths/cycles
2

---

Published as a conference paper at ICLR 2023
considered equivalent if their sets of edges are equal. The count of substructure S (L-cycle or L-path) of a graph G, denoted by CSS, G), is the total number of inequivalent substructures occurred as subgraphs of the graph. The count of substructures S of a node i, denoted by C(S, i, G), is the total number of inequivalent substructures involving node i. Specifically, we define Cicycle, i, G) by number of cycles containing node i, and C(path, i, G) by the number of paths starting from i.
Below we formally define the counting task at both graph and node level via distinguishing power. The definitions are similar the approximation of counting functions (Chen et al.) (020).
Definition 2.1 (Graph-level counting). Let & be the set of all graphs and Fraaph be a function class over graphs, i.e., f G + IR for f E Fgraph. We say FF Fengh can count a substructure S graph level, for all pairs of graphs G1, G2 E 9 satisfying C(S, G1) & C(S, G2), there exists a model Frapph such that f(1) + f(G2))
Definition 2.2 (Node-level counting). Let 9 be the set of all graphs, V be the space of nodes, and Frode be a function class over node-graph tuples, i.e., f: VVg + foorr f E FFodee We say Frode can count a substructure S at node level, for all pairs of node-graph tuples (i,, G1), (iz. G2) satisfying C(S, $1, G1) + C(S, iz, G2), there exists a model f E Fnode such that f(i1. G1) + f(1z, G2).
is worth noticing that node-level counting requires stronger approximation power than graph-level counting. This is because the number of substructures of graph is determined by the number of substructures of nodes, e.g.. C(3-cycle, G) Evev C(3-cycle, i, G) and C(3-path, G) Eiev (33-path, i, G). Therefore, being able to count substructure at node level implies the same power at graph level, but the opposite is not true.
COUNTING POWER OF MPNNs AND SUBGRAPH MPNNS
3.1 COUNTING POWER OF MPNNS
Message passing Neural Networks (MPNNs) are class of GNNs that updates node representations by iteratively aggregating information from neighbors (Gilmer al. 2017). Concretely, let h,") be the representation of node at iteration t. MPNNs update node representations using
ViEV, V,
1 ((+1) U.
(t) 1
Σ
mis
where mi,j MM Mr (ng
nn ev,s
(I)
.JE(()
Here U, and M, are two learnable functions shared across nodes. Node representations are initialized by node attributes: 12(0) Fz, or when no node attributes are available. After T iterations, the final node representations h, A h (T) are passed into readout function to obtain graph representation:
hGg
Rgraph (th,li E VJ).
(2)
It is known that MPNNs' power of counting substructures is poor: MPNNs cannot count any cycles or paths longer than 2.
Remark 3.1. MPNNs cannot count any cycles at graph level (using he), and cannot count more- than-2-patle at graph level (using hg). This can be easily seen by considering two graphs: G1 is two unconnected L-cycles and G2 is a 2L-cycle. Any MPNN cannot distinguish them, but G1 and G2 have different numbers of L-cycles and L-paths. See Appendix for detailed discussions.
3.2 COUNTING POWER OF SUBGRAPH MPNNS
Subgraph GNNs to factorize graph into subgraphs by some pre-defined strategies and aggregate subgraph representations into graph representations. Particularly, node-based strategy means each subgraph G; = (V,, E.) is tied with a corresponding node i. The subgraph G; is usually called the rooted subgraph of root node i. The initial node features of node j in rooted subgraph G, is Jiy _ 2, 22y. where @ denotes concatenation, Z, denotes the raw node attributes and 24,j are some hand-crafted node labeling. We formally define Subgraph MPNNs, a concrete implementation of Subgraph GNNs, including several popular node-based strategies.
Definition 3.1 (Subgraph MPNNs), Subgraph MPNNs are a subset of Subgraph GNNs which use a combination of node-based strategies listed below:
3

---

Published as a conference paper at ICLR 2023
Subgraph extraction: node deletion (V, E,) (VV,), EXG,)) E N())) or K-hop ego-
network (V, Ei) Ei) = (V, where EGO,(i, E) the subgraph induced by nodes within & hops from i;
Node labeling: identity labeling ži.j li-j or shortest path distance =i. spd(i, and use MPNNs as base GNNs to encode subgraph representations (see Equation 3 Here is used to denote indicator function.
Concretely, let (1 be the representation of node j in subgraph at iteration t. Subgraph MPNNs follow message passing scheme on each subgraph:
WE WEV.Vj
((+1) = U. 11
(t)
Σ
mijik
where mig.k = M2 ( (ikk
REN.U)
(3)
Here N.()) (.,,)) } represents node j's neighbors in subgraph Gj, and Uz, M, are shared learnable functions. After iterations, the final representations hes - h (T) node readout function obtain node representations h4:
will be passed
1.j
Vi E V, h2 Rnode ( ( E V.J).
(4)
Then {hi]: are further passed to graph readout function to obtain the graph representation la:
hg Rymph ((asli E V)).
Note that Subgraph MPNNs defined in Definition 3.1 and Equations 3
4
cover previous
methods such as (N - -e-onssnstrtution GNNs (Cotta et al. 2021), ID-GNNs YYuu et al. 2021),
DS-GNNs (Bevilacqua et al., (02T)) and Nested GNNs (Zhang & Li (021),
though there exists other
variants of Subgraph GNNs (Zhao et al.] 2202]] [evilacqua et al.)
2021 Frasca et al.] 2022 Qian
al. 2022) that do not fit into Subgraph MPNNs. Subgraph MPNNS are strictly more powerful than MPNNs, because (1) Subgraph MPNNS reduce to l'ylayer MPNNs by taking 7 7'-hop ego-network without any node labeling, performing T T'llyees of message passing and using root node pooling
h; = h and (2) Subgraph MPNNs can distinguish pairs of regular graphs which MPNNs cannot distinguish (e.g., graphs in Figure 2)
Although Subgraph MPNNs are more expressive than MPNNs. is still unclear if Subgraph MPNNs can count eycles and paths. Note that the proof in You et (202T) confuses paths with walks; see Appendix C Here we give an upper bound for Subgraph MPNNs counting power at graph level.
Proposition 3.1. Subgraph MPNNs cannot count 8-cycles and 8-paths at graph level. This can be seen by a pair of strongly regular graphs, the 4x4 Rook's graph and the Shrikhande graph. These two graphs have different numbers of 8-cycles and 8-paths (Fürer 2017 Arvind et al.) 2220). but Subgraph MPNNs fail distinguish them (see Appendix D.I). The counter-exanple also supports the conclusion that Subgraph MPNNs are weaker than 3- WL test (Frasca et al. (2022).
Further, we give a complete characterization of Subgraph MPNNs' cycle counting power at node level, shown the following theorems.
Theorem 3.1. Subgraph MPNNs can count 3-cycles, 4-cycles, 2-paths and 3-paths at node level.
Theorem 3.2. Subgraph MPNNs cannot count more-than-4-cylles and more-than-3-paths at node level.
We include the proof's in Appendix D Theorems 3. and indicate that although Subgraph MPNNs bring improvement over MPNNs, they still can only count up to 4-cycles. This far from expectation to count important substructures like benzene rings.
4 P-GNNS
The limitation of Subgraph MPNNs motivates design model with stronger counting power. A key observation is that assigning the root node a unique identifier can already express all node- based strategies listed in Definition 3.1 See Lemma D.I Therefore, conjecture that assigning
4

---

Published as a conference paper at ICLR 2023
Extract subgraphs
Label the neighbors of root node
Graph convolution and subgraph pooling
Graph pooling
Shared
Subgraph pooling
Set paoling
Raw graph
GNN
Subgraph pooling
{h2,2 n2a
Set pooling :
Set pooling
Subgraph pooling
(Ma
Set pooling
GNN
Figure 1: Architecture of F--NN. It extracts a K K-hop ego-network for each root node and iteratively assigns unique identifiers to both the root node (blue) and each of its neighbors (green).
more than one node identifier simultaneously can further lift the representational power. However, naively labeling all pairs of nodes may suffer from poor scalability due to the square complexity, like notice that substructures like cycles and paths are highly
other high-order GNNs. Fortunately, localized. For instance, a 6-cycle must exist the 3-hop ego-network of the root node. This implies that local labeling method might be sufficient to boost the counting power.
Given these observations, we adopt localized identity labeling strategy and propose I-GNNS: except for the unique identifier of root node i, we further assign another unique identifier to one of the neighbors of the root node, called branching node j. To preserve the permutation equivariance, the branching node should iterate over all neighbors of the root node. The resulting model essentially associates each connected 2-tuple (i.j) with subgraph G.g. in which i.j are labeled with the corresponding identifiers. Compared to Subgraph MPNNs, only increases the complexity by factor of node degree. See Figure 1 for an illustration of the graph encoding process of 12-GNNs.
Formally, for each root node E V. we first extract its K-hop ego-network with identity labeling. Then for every branching node j (i). we further copy the subgraph and assign an additional identifier for j. This results subgraph Gi.j = (V,, E,) tied with (i,j), where node attributes are augmented with two identifiers: Tigi. Th + 1 θ l==j- Let ((()) be the representation of node in subgraph Gr, iteration f. 12-GNNs use MPNNs in each subgraph:
Vi E V,Yj E N(I), V,,
h (++1) j.j
U.
(1)
Aig.tt
Σ
mi.gk
where mi.jkkJ Me
( 110
(6)
LEN((R)
After T iterations we obtain final representations hi.j. A (T) We use an edge readout function: Migk k. V,Vjj N(),, ha. = Rodgo (fhaj,ak Vi)),
node readout function:
Vi V, h4 Rnode (Chr,si E N())),
(8)
and finally graph readout function:
hG = Ryraph EV))
Intuitively, I-GNNS improve the representational power by breaking the symmetry of the neigh- bors of root nodes. In the rooted subgraph Gt the root node treats the messages from distinct branching nodes j differently. The following discussion demonstrates that I2-GNNs do have stronger discriminative power over MPNNs and Subgraph MPNNs.
Proposition 4.1. P-GNNS are strictly more powerful than Subgraph MPNNs. This can be seen via: (1) F-GNNs can reduce to Subgraph MPNNs by ignoring the branching node identifier. (2) 1-- GNNs can distinguish the 4x4 Rook's 's graph and the Shrikhande graph, while Subgraph MPNNs and 3-WL test cannot. This also suggests that P--NNS are partially stronger than the 3-WL test. See Appendix E. more details. Moreover, F-NNNS discriminative power is bounded by the 4-WL test as they can be implemented by 4-IGNs, which analogous to the relation between Subgraph
MPNNs and 3-IGNs (Frasca al. 2022
5

---

Published as a conference paper at ICLR 2023
One may ask if the additional identifier of I F--GNNs brings stronger counting power. The answer is yes. We note that in I--NNNs, the root node i is aware of the first edge (i.j) in each path it is counting, ie.. (i=rj+>... ...), while for Subgraph MPNNS the first edge in paths is always anonymous, i.e,, (..) As the first edge is determined, the counting of I-paths from i is transformed into an easier the counting of (T. 1)-paths from j. Since cycles are essentially special kind of paths, the cycle counting power is boosted too. However, naively applying this argument only shows that I2-GNNs can count up to 5-cycles (one more than Subgraph MPNNs). Our main theorem below indicates that 1 12-Gsss cycle counting power is actually boosted to at least 6-cycles.
Theorem 4.1. P-GNNs can count 3. 4, 5 and 6-cycles at node level.
provides a lower bound of I2-GNNs' cycle counting power. Recall that the cycle counting power of the 3-WL test is upper bounded by 7- cycles, while the linear-tims I2-GNNs can already approach that. The significance of Theorem 4.1 is that it indicates the feasibility of using local and scalable model to encode cycle substructures, rather than applying global algorithms such as k- WL test or relational pooling with exponential cost.
We include all proof' in Appendix Theorem 4.1
Below we also show some positive results of counting other substructures with 12-GNNs.
Theorem 4.2. P-GNNs can count 3 and 4-paths at node level.
Theorem 4.3. R-GNNs can count all connected graphlets with size or at node level.
See the definition of node-level graphlets counting in Appendix Figure 6 Note that connected graphlets with size 4 includes 4-cliques, a substructure that even 3-WL. test cannot count (Fürer 2017). This again verifies I2-GNNs' partially stronger power than 3-WI..
RELATED WORKS
WL-based GNNs. Xu et al. 2018) and Morris et al. (211 showed that MPNNS are at most as pow- erful as the WL test in terms of distinguishing non-isomorphic graphs, which motivates researchers to propose provably more powerful GNN models. One line of research is to extend MPNNs to simulate high-dimensional WL test by performing computations on k-tuples. On one hand, Morris et al. (2019) proposes k-dimensional GNNs called k-GNNs, which apply message passing between k-tuples and can be seen as local and neural variant of k-WL test. MMoris et al. (2020b) further extend i-GNNNs by aggregating only from local neighbors, obtaining a scalable and strictly more powerful model. Despite the good scalability due to the localized nature, it is still unclear if these models can achieve the discriminative power of the 3-WL. test. On the other hand, Maron et al. (2019)) proposed tensor-based model that is provably as powerful as the 3-WI. test. The downside is its cubic complexity.
Permutational invariant and equivariant GNNs. There is a line of research studying GNNs from the perspective of equivariance to permutation group. this regard, Maron et al. (2018) proposed Invariant Graph Networks (IGNs), which apply permutational equivariant linear layers with point- wise nonlincarity to the input adjacency matrix. k-IGNs (using at most k-order tensors) are shown to have equivalent discriminative power k-WL. test (Maron et al. 2019a Geerts 2020 Azizian & Lelarge 2020). With sufficiently large k k-IGNs can reach universal approximation to any invariant functions on graphs (Maron et al.) 2019b Azizian & Lelarge 2020 Relational pooling (Murphy ct al. 2019)) utilizes the Reynold operator, a linear map that projects arbitrary functions to the in- variant function space by averaging over the permutation group. Relational pooling is shown to be universal approximator for invariant functions, but it does not scale as the size of the permutation group grows factorially with graph size.
Subgraph GNNs. Another line of research aims at breaking the limit of MPNNs by encoding node representations from subgraphs rather than subtrees. In this respect, A-u-Ea-Haija et al. (2019); Tahmasebi et al. (2020); (Sandfelder et al. (202)): NNikolentoos et al. (2020) study convolutions on K-hop neighbors instead of only 1-hop neighbors. See Feng et al. (022) for an analysis of their power. Wijesinghe & Wang 22021) weights the message passing based on the subgraph overlap. On the other hand, a recent and popular class of GNNs dubbed Subgraph GNNs views a graph as
bag of subgraphs. Subgraph extraction policies vary among these works, with possible options
including node and/or edge deletion (Cotta et al. 202 Bevilacqua et al. 2021 Papp et al. 202I),
node identity augmentation Youu al. 2021 and ego-network extraction (Zhang & [i 2021 Zhao

---

Published as a conference paper at ICLR 2023
et al. 2021). The base GNNs are also flexible, varying from MPNNS to relational pooling (Chen et al. 2020). contemporary work (Frasca et al. 2022) further explores the theoretical upper bound of the representational power of Subgraph MPNNs, showing that all existing Subgraph MPNNS can be implemented by 3-IGNs and thus are weaker than the 3-WL. test. Labeling trick (Zhang et al,, multi-node labeling for muti-node task, but it cannot directly generate equivariant single-node/graph representation.
2021 Zhang & Chen 2018)
Feature-augmented GNNs. Some works improve expressiveness by augmenting node features.
Bouritsas et al. 2022); Barceló et al. (2021) ) augment the initial node features with hand-crafted
structural information encoded in the surrounding subgraphs, and Dwivedi et al. (202T) adopts posi- tional encoding and devises message passing for positional embedding, Loukas (2019) (2019/2020) 2020) instead
study the representational power in case where all nodes have uniquely identified features.
GNNs' power of counting graph substructures. The ability to count graph substructures is another perspective of studying GNNs' representational power. Many previous works characterized the power to count substructures for the WL test and variants of GNNs. [ürer (2017); Arvind et al.] 2020) give a complete description of 1-WL combinatorial invariants (i.e., all substructures that can be counted by the 1-WL test) and a partial result for 2-FWL. Particularly, the power of counting cycles and paths the 2-FWL test is fully understood: the 2-FWL test can and only can count up to 7-cycles and 7-paths. Chen et al. (2020) study the counting power of induced subgraph counting and give general results of WL test, but the bound is loose. Tahmasebi et al. (2020) study the counting power of Recursive Neighborhood Pooling GNNs and give the complexity lower bound of counting substructures for generic algorithms.
EXPERIMENTS
This section aims validate our theoretical results and study G2-GNNs empirical performance Particularly, we focus on the following questions:
Q1: Does the discriminative power of 12-GNNs increase compared to Subgraph MPNNs?
Q2: Can I2-GNNs reach their theoretical counting power?
Q3: How do [2-GNNs perform compared to MPNNs, Subgraph MPNNs and other state-of-the-ar
GNN models on open benchmarks for graphs?
Note that in the experiments, shortest path distance (SPD) labeling Li al. 2020) is uniformly used as alternative to identity labeling in I2-GNNs. SPD labeling is also used in Nested GNNs (Zhang
& Li 202I) and GNNAK (Zhao et al.) 202I). Theoretically SPD labeling has the same representa- tional power identity labeling. We study the effects of SPD labeling in Appendix I0
6.1 DISCRIMINATING NON- -UN-ISOMOPPHIC GRAPHS
Datasets. To answer QI, we study the discriminative power on two synthetic datasets: (1) EXP (Ab- boud et al. 2020), containing 600 pairs of non- non-isomorphic graphs that cannot be distinguished by the 1-WL/2-WL WL test; (2) SR25 (Balcilar et al. 2021), containing 150 pairs of non-isomorphic strongly regular graphs that 3- 3- fails to distinguish. We follow the evaluation process in (Balcilar et al. 2021 that compares the graph representations and reports successful distinguishing cases.
Table 1: Accuracy on EXP/SR25.
Models. Adopting GIN (Xu al. 2018) as the base GNN, we compare 1--NNNs to ID-GNN, YYuu et al. 2021), Nested GNNs (NGNNs) (Zhang Lij 2021) and GNNAK + (Zhao et al. 202T). These Subgraph GNNs are known be strictly stronger than I-WL but weaker than 3-WL. We also consider PPGN (Maron et al., 2019a) known to be powerful as 3-WL.
Method
EXP
SR25
Base GNN
0%
0%
ID-GNN
100%
0%
NGNN
100%
0%
Results. Table shows that all models except 12_GNN fail the SR25 dataset with 0% accuracy. In contrast, 12-GNN achieves
GNNAK+
100%
0%
PPGN
100%
0%
a 100% accuracy. It supports Proposition 4.1 that 12-GNNs is strictly stronger than Subgraph MPNNs and partially stronger than the 3-WL test.
G-GNN
100%
100 %
7

---

Published as a conference paper at ICLR 2023
Table 2: Normalized MAE results of counting cycles at node level on synthetic and ChEMBL dataset. The colored cell means an error less than 0.01 (synthetic) or 0.001 (ChEMBL).
Synthetic (norm. MAE)
ChEMBL (norm. MAE)
Method
3-Cyele
4-Cycle
5-Cycle
6-Cycle
3-Cycle
4-Cycle
5-Cycle
6-Cycle
Base GNN
0.3515
0.2742
0.2088
0.1555
0.1326
0.0780
0.4307
0.4268
ID-GNN
0.0006
0.0022
0.0490
0.0495
0,0001
0.0008
0.0006
0.0024
NGNN
0.0003
0.0013
0.0402
0.0439
0.0001
0.0005
0.0003
0.0053
GNNAK+
0.0004
0.0041
0.0133
0.0238
0.0001
0.0011
0.0002
0.0006
PPGN
0.0003
0.0009
0.0036
0.0071
0.0001
0.0169
0.0001
0.0007
P-GNN
0.0003
0.0016
0.0028
0.0082
0.0001
0.0005
0.0001
0.0003
Table Normalized MAE results of counting graphlets at node level on synthetic dataset.
Synthetic (norm. MAE)
Method
Tailed Triangle
Chordal Cycle
4-Clique
4-Path
Shangle-Rectangle
Base GNN
0.3631
0.3114
0.1645
0.1592
0.2979
ID-GNN
0,1053
0.0454
0.0026
0.0273
0.0628
NGNN
0.1044
0.0392
0.0045
0.0244
0.0729
GNNAK
0.0043
0.0112
0.0049
0.0075
0.1311
PPGN
0.0026
0,0015
0,1646
0,0041
0,0144
P-GNN
0.0011
0,0010
0.0003
0.0041
0.0013
6.2 GRAPH SUBSTRUCTURE COUNTING
Datasets. To answer Q2, we adopt the synthetic dataset from Zhao et al.] (2021) and a bioac- tive molecules dataset named ChEMBL (Gaulton al.] 2012) to perform node-level counting tasks. The synthetic dataset contains 5,000 graphs generated from different distributions. The training/validationneess spliting 0.3/0.2/0.5. The ChEMBL dataset is filtered contain 16,200 molecules with low fingerprint similarity. The task is to perform node-level regression on the num- ber of 3-cycles, 4-cycles, 5-cycles, 6-cycles, tailed triangles, chordal cycles, 4-cliques, 4-paths and triangle-rectangles respectively (continuous outputs to approximate discrete labels). See Appendix F. for more details about definitions of these graphlets, dataset preprocessing. model implementa- tion and experiment setup.
Models. We compare with other Subgraph GNNs, including ID-GNNs, NGNNs and GNNAK+ Besides, PPGNs, which theoretically can count up to 7-cycles, are also included for comparison. We use a 4-layer GatedGNN (Li et al., 2013) as the base GNN to build ID-GNNs, NGNNs and I--GNNs GNNAK+ is implemented using 4-layer GNNAK+ layers with 1-layer GatedGCNs as inner base GNNs. PPGNs are realized with 4 blocks of PPGN layers.
Results. We run the experiments with three different random seeds and report the average normal- ized test MAE (i.e. test MAE divided by label standard deviation) in Table[ and 3 On both datasets, Subgraph MPNNs (NGNNs and ID-GNNs) and I2-GNNs attain a relatively low error (< 0.01) for counting of 3, 4-cycles, which is consistent with Theorems 3.1 and 4.1 On the synthetic dataset, if we compare 5-cycles, 6-cycles to 3-cycles, 4-cycles. The MAE of Subgraph MPNNs get nearly 30 times greater. It supports Theorem 3.2 that Subgraph MPNNs fail count 5-cycles and 6-cycles node level. GNNAK+, though not belonging to Subgraph MPNNs, also gets a 3~66 times greater MAE. In comparison, PPGN and I2-GNNs still keep stable MAE less than 0.01. On the ChEMBL dataset, the 6-cycle MAE of Subgraph MPNNs also amplifies by 5 times compared to 4-cycles MAE. In contrast, 12-GNNs MAE almost remains the same. These observations support Theorem 4.1
Ablation study. We study the impact of the key element- the additional identifier, on 1 counting power. The results can be found in Appendix 10
6.3 MOLECULAR PROPERTIES PREDICTION
Datasets. To answer Q3, we adopt three popular molecular graphs dataset- QM9, ZINC and ogbg- molhiv. QM9 contains 130k small molecules, and the task is regression twelve targets such as energy. The training/validaaionneest splitting ratio is 100... ZINC (Dwivedi et al.) 2020). in- cluding ZINC-small (10k graphs) and ZINC-large (250k graphs), is free database of commercially-
8

---

Published as a conference paper at ICLR 2023
Table 4: MAE results on QM9 (smaller the better).
Target
L-GNN
1-2-3-GNN
DINN
Deep LRP
PPGN
NGNN
P-GNN
0.493
0.476
0.244
0.361
0.231
0.428
0.428
a
0.78
0.27
0.95
0.298
0.382
0.29
0.230
Chomo
0.00321
0.00337
0,00388
0.00254
0.00276
0.00265
0.00261
Eluno
0.00355
0.00351
0.00512
0.00277
0.00287
0.00297
0.00267
A
0.0049
0.0048
0.0112
0,00353
0,00406
0,0038
0,0038
34,1
22.9
17.0
19.3
16.07
20.5
18.64
ZPVE
0.00124
0,00019
0,00172
0.00055
0.0064
0.0002
0.00014
Up
2.32
0.0427
2.43
0.413
0.234
0.295
0.211
U
2.08
0.111
2.43
0.413
0.234
0.361
0,206
H
2.23
0.0419
2.43
0.413
0.229
0.305
0.269
G 1.94
0.0469
2.43
0.413
0.238
0.489
0.261
C.
0.27
0.0944
2.43
0.129
0.184
0.174
0.0730
Table 5: Four-runs MAE results ZINC (smaller the better) and ten-runs AUC results ogbg- molhiv (larger the better). The indicates the model uses virtual node on ogbg-molhiv.
Method
ZINC-12K (MAE)
ZINC-250K (MAE)
ogbg-molhiv (AUC)
GIN
0.163
0.058-0.002
77.07 L.49
PNA
0.188
1.30
DGN
0.008
79.7
HIMP
0.101
0.006
78.80
GSN
0.115++0.012
80.39
Deep LRP
77.19+1.40
CIN-small
0.094
0.044=0.003
80.05
CIN
0.079 + 006
0.022=00002
00.57
Nested GIN
0..1000.003
0.009
78.34
GNNAK+
0.080 001
79.61 1.19
SUN (EGO)
0.0831000003
80.03 0.55
1--GNN
0.083+00.001
78.68+00.88
available chemical compounds, and the task is graph regression. The ogbg-molhiv dataset contains 41k molecules for graph classification. The original release provides the splitting of both ZINC and ogbg-molhiv.
Models. For QM9, we adopt baselines including 1-GNN, 1-2-3-GNN (Morris et al., 2019),
DTNN (Wu et al.) 2018)) Deep LRP (Chen et al.) 2020). PPGN and NGNN. The baseline results are from Zhang & Li (202I). Note that we omit methods (Klicpera et al. 2020; Anderson et al.
2019 Qiao et al. 2020 Liu et al. 202T) that utilize additional geometric features or quantum me- chanics theory, since our goal is to compare the models' graph representation power. We choose our base GNN to construct IN-GNN For ZINC and ogbg-molhiv, we use GIN as the based GNN. We make comparisons to baselines such as GNNAK+, PNA (Corso
NNConv (Gilmer et al. 2017
al. 2020), DGN (Beaini et al.) 2021). HIMP (Fey al. 2020), GSN (Bouritsas et al. 2022). Deep
LRP Chen et al. 2020). SUN (Faacaa et al. 2022) and CIN (Bonnar et al. 2021). 1). See more details
Appendix F.2
Results. On QM9, Table shows that I2-GNN outperforms NGNN over most targets, with an average 21.6% improvement. Particularly, 12 I2-GNN attains the best results on four targets out of twelve. On ZINC, I2-GNN brings 25% and 18% performance gains to Nested GIN on ZINC-126 and ZINC-250k respectively. Moreover, despite being a model targeting on cycle counting. I2-GNN approaches the SOTA results of CIN. On ogbg-molhiv, I2-GNN improves the AUC of Nested GIN by 0.3%. These results suggest that 12-NNNs also bring improvement to general graph regres- sion/classification tasks.
7 CONCLUSION
We propose to study the representational power of Subgraph MPNNs via the ability to count cycles and paths. We prove that Subgraph MPNNs fail to count more-than-4ccyeles at node level, which limits their power to encode surrounding ring systems with more than four atoms. Inspired by the localized nature of cycles, we extend Subgraph MPNNs by assigning an additional identifier to the neighbors of the root node to boost the counting power. The resulting model named 12- turns out to be able to count at least 6-cycles linear time with theoretical guarantee. Meanwhile, 12-GNNs maintain excellent performance on general graph tasks.

---

Published as a conference paper at ICLR 2023
8
ACKNOWLEDGE
This project is supported in part by the National Key Research and Development Program China (No. 2021ZD01 14702).
REFERENCES
Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. arXiv preprint arXiv:2010.01179, 2020.
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learn- ing. pp. 21-29. PMLR, 2019.
Brandon Anderson, Truong Son Hy, and Risi Kondor. Cormorant: Covariant molecular neural networks. Advances in neural information processing systems, 32, 2019.
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. weisfeiler-leman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sci- ences, 113:42-59, 2020.
Waiss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural net- works. arXiv preprint arXiv:2006. 212220006..66,,... 2020.
Muhammet Balcilar, Pierre Héroux, Benoit Gauzere, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In International Con- ference Machine Learning, pp. 599-608. PMLR, 2021.
Pablo Barceló, Floris Geerts, Juan Reutter, and Maksimilian Ryschkow. Graph neural networks with local graph parameters. Advances in Neural Information Processing Systems, 34:25280-25293, 2021.
Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In International Conference on Machine Learning, pp. 748- 758. PMLR, 2021.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation net- works. arXiv preprint 10.00211 2021.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang. Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. Advances in Neural Infor- mation Processing Systems, 34:2625-2640, 2021.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions Pattern Analysis and Machine Intelligence, 2022.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geomet- ric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18 42, 2017.
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-400, 1992.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 32, 2019.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 13:10383-10395 2020.
10

---

Published as a conference paper at ICLR 2023
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličkovié. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:13260-13211 2020.
Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph repre- sentations. Advances in Neural Information Processing Systems, 34:1713-1726, 2021.
Mukund Deshpande, Michihiro Kuramochi, and George Karypis. Automated approaches for clas- sifying structures. Technical report, MINNESOTA UNIV MINNEAPOLIS DEPT OF COM- PUTER SCIENCE, 2002.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks graphs for learning molecular fingerprints. Advances in neural information processing systems, 28, 2015.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982, 2020.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. arXiv preprint arXiv:21 10.07875, 2021.
Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang. How powerful are k-hop message passing graph neural networks. arXiv preprint arXiv:2205. 13328, 2022.
Matthias Fey, Jan-Gin Yuen, and Frank Weichert. Hierarchical inter-message passing for learning on molecular graphs. Xiviv preprint 122179 2020.
Fabrizio Frasca, Beatrice Bevilacqua, Michael M Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. arXiv preprint arXiv:2206.//140 2022.
Martin Fürer. On the combinatorial power of the weisfeiler-lehman algorithm. In International Conference on Algorithms and Complexity, pp. 260-271. Springer, 2017.
Anna Gaulton, Louisa J Bellis, Patricia Bento, Jon Chambers, Mark Davies, Anne Hersey, Yvonne
Light, Shaun McGlinchey, David Michalovich, Bissan Al-Lazikani, et al. Chembl: a large-scale bioactivity database for drug discovery. Nucleic acids research,
2012.
Floris Geerts. The expressive power of kth-order invariant graph networks arXiv preprint arXiv:2007. /2035, 2020.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning. pp- 1263-1272. PMLR, 2017.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. arXiv preprint arXiv: 1905. 12265, 2019.
Ningyuan Teresa Huang and Soledad Villar. A short tutorial on the weisfeiler-lehman test and its variants. In ICASSP 2021-202. IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 8533-8838000 8537. IEEE, 2021.
Chuntao Jiang, Frans Coenen, and Michele Zito. Finding frequent subgraphs in longitudinal social network data using weighted graph mining approach. International Conference on Advanced Data Mining and Applications, pp. 405-416. Springer, 2010.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International conference on machine learning, pp. 2323-2332. PMLR. 2018.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial opti- mization algorithms over graphs. Advances in neural information processing systems, 30, 2017.

---

Published as a conference paper at ICLR 2023
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint
2016.
Johannes Klicpera, Janek GroB, and Stephan Günnemann. Directional message passing for molec- ular graphs. arXiv preprint arXiv:2003.084 03123, 2020.
Mehmet Koyutürk, Ananth Grama, and Wojciech Szpankowski. An efficient algorithm for detecting frequent subgraphs in biological networks. Bioinformatics, (o(suppl_)):100-p000 2004.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovee. Distance encoding- design provably more powerful gnns for structural representation learning. arXiv preprint arXiv:2009.00) 00142, 2020.
Weizhong Li and Adam Godzik. Cd-hit: a fast program for clustering and comparing large sets of protein or nucleotide sequences. Bioinformatics, 22(13):1658-165) 2006.
Yujia Li, Daniel Tarlow, Mare Broekschmidr, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint arXiv:1511.05449 2015.
Yi Liu, Limei Wang, Meng Liu, Xuan Zhang, Bora Oztekin, and Shuiwang Ji. Spherical message passing for 3d graph networks. arXiv preprint 1xXi:2202.00013.. 2021.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. arXiv preprint arXiv:1907.03199 2019.
Andreas Loukas. How hard to distinguish graphs with graph neural networks? Advances in neural information processing systems, 33:3465-3476, 2020.
Linyuan Lü and Tao Zhou. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications, 190(6))1100-1100) 2011.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. arXiv preprint arXiv: 18/2.09902, 2018.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019a.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In International conference on machine learning, pp. 4363 4371. PMLR, 2019b.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on 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. arXiv preprint arXiv:2007.08663 2020a.
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable oigeer-order graph embeddings. Advances in Neural Information Processing Systems, 33:21824-218400, 2020b.
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,
Christopher W Murray and David C Rees. The rise of fragment-based drug discovery. Nature chemistry, 1(3):177-92,, 2009.
Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. k-hop graph neural networks. Neural Networks, 130: 190:199-2055 2020.
Pâl András Papp and Roger Wattenhofer. A theoretical comparison of graph neural network exten- sions. arXiv preprint arXiv:2201. /2884, 2022.
12

---

Published as a conference paper at ICLR 2023
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-22000 2021.
Chendi Qian, Gaurav Rattan, Floris Geerts, Christopher Morris, and Mathias Niepert. Ordered subgraph aggregation networks. arXiv preprint arXiv:2206. 168, 2022.
Zhuoran Qiao, Matthew Welborn, Animashree Anandkumar, Frederick R Manby, and Thomas Miller III. Orbnet: Deep learning for quantum chemistry using symmetry-adapted atomic-orbital features. The Journal of chemical physics, 153(12)124111, 2020.
Dylan Sandfelder, Priyesh Vijayan, and William L Hamilton. Ego-gnns: Exploiting ego structures in graph neural networks. ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). pp. 8523 8527. IEEE, 2021.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.
The graph neural network model. IEEE transactions on neural networks, 20(1):61-80) 2008
Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M Donghia, Craig R MacNair, Shawn French, Lindsey A Carfrae, Zohar Bloom-Ackermann, et al. A deep learning approach to antibiotic discovery. Cell, 180(4):688-702, 2020.
Behrooz Tahmasebi, Derek Lim, and Stefanie Jegelka. Counting substructures with higher-order graph neural networks: Possibility and impossibility results. arXiv preprint urXiv:2012.03174, 2020.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks, arXiv preprint arXiv:1710.10900 2017.
Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. NTI, Series, 2(9):12-16, 1968.
Asiri Wijesinghe and Qing Wang. A new perspective on" how graph neural networks go beyond weisfeiler-lhhman?. In International Conference on Learning Representations, 2021.
Zhengin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learn- ing. Chemical science, 9(2):513-530) 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.0082 2018.
Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay Pande, and Jure Leskovec. Graph convolutional policy network for ooal-directed molecular graph generation. Advances in neural information processing systems, 31, 2018.
Jiaxuan You, Jonathan M Gomes Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-awan graph neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 10737-10745, 2021.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018.
Muhan Zhang and Pan Li. Nested graph neural networks. Advances in Neural Information Process- ing Systems, 34:15734-157477 2021.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems, 14:9061-90733 2021.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah, From stars to subgraphs: Uplifting any gnn with local structure awareness. arXiv preprint 1rXiv:2/10.0375: 2021.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changeheng Li, and Maosong Sun. Graph neural networks: A review of methods and applica- tions. AI Open, 1:57-81, 2020.
13

---

Published as a conference paper at ICLR 2023
A WEISFEILER-LEHMAN TEST
The Weisfeiler-Lehmnn (WL) Test (Weisfeiler & Leman 1968) is heuristic algorithm for the graph isomorphism test. Initially, the WL test assigns nodes the same color, and then it follows an iterative color refinement scheme to update node colors: for each node, the new color is obtained by applying a hash function to old color and the multiset of its neighbors' old colors. Formally, each iteration can be written
((+1) Hash (G (
(10)
(9) is the color of node i at iteration I, and {-} should be understood as multiset. The where Cf
algorithm terminates the number of colors does not change after one iteration. Two graphs are determined to be non non-isomorphic if the histogram of colors differs. The k-dimensional Weisfeiler- Lehman (k-WL) Test with & 2 2 is a generalized version of WL test that performs color refinement on k-tuples. For l 2 2, the discriminative power of the k-WL test is shown increase constantly as increases (Cai et al. 1992 Maron et al. 2019a). See Morris et al. (2019): Huang Villar (2021) for more information.
B COUNTING POWER OF MPNNS
Table 6: Node-level cycle and path counting power of GNN models.
Substructures
2-Path
3-Path
4-Path
3-Cycle
4-Cycle
5-Cycle
6-Cycle
MPNNs
X
Subgraph MPNNs
X
X
X
P-GNNS
V
In this section we formally prove the counting power of MPNNs. We first give positive result, that
MPNNs can count 2- 2-paths node level (thus graph level).
Theorem B.1. MPNNs can count 2-paths at node level.
Proof. To count 2-paths starting from i, one can consider the 2-layer message passing function h4 Ejen(y (d, 1) (degree d, is learned in the first layer). Then h4 equals the number of 2-path with being the endpoint.
Next we give the negative results at graph level (thus node level).
Theorem B.2. MPNNs cannot count paths with length greater than 2 at graph level, and cannot count any cycles at graph level.
Proof. Let L be any positive integer greater than equal to 3. Let G₁ be two L-cycle and G2 be 2L-cyl.. All nodes has a degree of 2, and thus the graph representations are indistinguishable. We that G1 has two L-cycles while G2 does not. Moreover, G2 has L-paths while G₁ does not. Therefore we finish the proof.
Figure 2: A pair of regular graphs that MPNNs cannot distinguish.
14

---

Published as a conference paper at ICLR 2023
C DISCUSSION ON PROPOSITION 2 IN YOU ET AL. (202 1
In You et al. 2021), the Proposition claims that an L-layer ID-GNN can use node representations to express the number of cycles involving the node. In the proof, they use induction: they assume for arbitrary nodes j. the representations h4 cquals to the number of L-paths from i to j. and they try to prove the case of (L + 1) -paths using additional layer of ID-GNN. The basic logic they use is that if there exists an L-path from to k, and & adjacent to j. then there must exist an (L + 1))path from already. The induction holds for walks only. In conclusion, the proof actually shows ID-GNNs can count walks, but the number of walks cannot determine the number of cycles.
j. However, it is not true because the L-path from i to k might contain
D COUNTING POWER OF SUBGRAPH MPNNS
In this section we give formal proofs of Proposition 3.1 Theorem with, we prove some useful lemmas.
3.1 and Theorem 3.2 To begin
Lemma D.1 (Identity labeling is the most powerful strategy). Stategy of augmenting root nodes with unique identifiers, iee. (V,, E,) = (V, E) and ri = 24 @ 1l i=j can express all strategies in 3.1
Proof. For simplicity, assume 10 = 1, l We discuss the listed strategies one by one.
Node deletion: we can recognize the root node by its identifier and "mask out" the root node from the subgraph.
Ego-networks: to mimic K K-hop ego-networks extraction, we can apply K-layers MPNNs mark nodes in the K-hop ego-networks. Concretely, K iterations of the following message passing layer label all involving nodes as while others are 0.
maj =
Σ kENU)
(0) 2,00
(1+1) jij
110 mm 20 + 1 M
(11)
Then we mask out nodes with zero labels, implementing K-hop ego-networks extraction. Shortest path distances: similar to labeling nodes in the K-hop ego-netwroks, can construct the following message passing layer
mii
Σ
(++1) h
= (t+ (t+1)1 -y= - +1, 100+0
(12)
KEN()
In the following discussions, refer Subgraph MPNNs to this specific model: Subgraph MPNNs with identity node labeling. We assume the identifier of root node is always available in subgraph G; throughout.
Lemma D.2. Subgraph MPNNs can count 2-paths and 3-paths that starts from node i and ends at node j using hij-
Proof. We can construct the following MPNNs to count 2-path between the root node i and another node j:
h1 = Σ 1
(13a)
kEN())
h(2)
1,f1
(13b)
KENG)
15

---

Published as a conference paper at ICLR 2023
Figure 3: The 4x4 Rook's graph and the Shrikhande graph (some edges are dashed just ensure readability). The figure is modified from Arvind et al. 2020).
One can easily see that h equals to number of 2-paths from é to j. Similarly, we construct the following MPNNs to count 3-paths between node i and j:
1 = Σ
1k=s.
(14a)
kEN
(2)
iii Σ
Mi,k
(1)
(14b)
kEN(j)
h
Lizi
Σ
(2)
(14c)
kEN()
To see why this is true, note that [ marks the neighbors of and h marks the 2-hop neighbors
of i. One one hand, if node is not the neighbor of i, then Eke N()) h
is exactly the number of 3-
paths from to j. On the other hand, if j is the neighbor of i, then EKENG) Mi,k will additionally get
d,- 1 times unexpected counts. Thus by subtraction,
EkENG) A JEN() 1)
E EKENGY (h(3 h())) correctly counts 3-paths from
D.1 PROOF OF PROPOSITION 3.1
Consider the 4x4 Rook's graph and the Shrikhande graph shown in Figure 3 that Subgraph MPNNs cannot distinguish them. We choose the node in top left coner as the root node. We use matrix to denote the colors of nodes in this 4x4 grid. Initially, both graphs let the root node's s color be 1, and other nodes are 0:
We are going to show
1.
(0) Rook
(0) Shrik
0
(15)
0
In the first iteration, let the hash function be Hash (1, (0. 10.0.0,0,0,0)
2,,
Hash(O, (1,0,0,0.0.0)) = and Hash(O, 00,0000000.0 = 0. Then the new colors be-
come:
(2
1
1
2
1
0
1 Rook
(1)
1
0
A
(I)
1
1
0
(16)
1
0
0
0
0
0
0
1
0
0
1
In the second iteration, the hash function be Hash(2, 11,1,,,,,,11,11
2,
Hash(1, (2, 1,, 1,000,,
and Hash(O, 0,,000,,,0,0).. We that the refinement
16

---

Published as a conference paper at ICLR 2023
process converges. Thus, both the top left corner node's representations
bRook
hihhikk ( 111t1111111111100000000000011111
(17)
Thus Subgraph MPNNS cannot distinguish these nodes. This true regardless of which root node we choose. Therefore Subgraph MPNNs cannot distinguish the 4x4 Rook's graph and the Shirkhande graph.
D.2 PROOF OF THEOREM 3.1
Concretely, let haj be the number of 2-paths from node node j, then h4 EjEN(E) Bag is the number of 3-cycles involving node and h4 = Ejev hisj is the number of 2-paths starting from node i. Similarly, let h.. be the number of 3- 3-paths from node to node j. then h; 2 EjEN(s) big is the number of 4-cycles involving node i, and h; EjeN()) he is the number of 3-paths starting from node Note that summation the neighbor of which can be implemented by marking the neighbor of
Using Lemma D.2 we can easily prove Theorem 3.1
D.3 PROOF OF THEOREM 3.2
To prove Theorem consider the counter-example shown in figure 4
Figure 4: The two blue nodes in graphs not been distinguished by subgraph MPNNs. The left one is in six 5-cycles and six 4-paths while the right one is not.
Note that any Subgraph MPNNs get exactly the same representations for the two blue nodes. The left blue node involves in six 5-cycles and six 4-paths while the right one does not. Actually, one can construct similar counter-exampler
one graph is 2L-cycle (white nodes) with all nodes con- nected to an additional node (blue node), another graph two L-cycle (white nodes) with all nodes connected to additional node (blue node). The first blue node involves in (T. 2)-cycles and (L + 1) -atths while the second one does not.
E COUNTING POWER OF 12-GNNS
In this section we prove Proposition 4.1 Theorems
4.2 and 4.3
We first prove Lemma E.
which is further used to prove Theorem 4.2 and part Theorem
For recap, F-GNNS assign two identifiers to root node and one of its neighbors j: hijj. 1 1k=j We assume the identity of and j are always available in subgraph Gi.j-
Lemma E.1. P-GNNs can count 4-paths in forms of (i + j + - k) using hig.
Proof sketch. The core idea stems from Lemma D.2 that using one unique identifier can count 3- paths. Recall that 12 I2-GNNs two unique identifiers for two adjacent nodes and j. therefore one can show that can count number of 3-paths to another without passing node i. Equivalently, this exactly the number of 4-paths from node to node & while passing node j in the first walk. IT
17

---

Published as a conference paper at ICLR 2023
Proof. Consider the following message passing functions:
1igh Liti
Σ
Li=j
(18a)
(EN(K)
Σ
(18b)
IEN(K)
h (1)) Ixyi
Σ
(1) (.j.k
(18c)
Lig.t
IEN(A)
One can see that h i.jk is the number of 3-paths from j to k without passing i. Given that i.j are adjacent, I b.y,k is equivalent to the number of 4-paths from to while passing j in the first walk.
E. PROOF OF PROPOSITION
In this subsection Shrinkhande graph shown in Figure 3 Suppose we adopt I-hop ego-network. then we find that for every root node of 4x4 Rook's graph, ego-net G; the left graph shown in Figure 4 (i is the blue node), and for every root node i of Shrikhande graph, ego-net G; is the right graph shown in Figure 4 (i is the blue node). Let j be one of the neighbors of Now let construct message passing function to distinguish them. For instance, in the first layer we mark the common neighbors of and j. and in the second layer we determine the connectivity of these common neighbors.
going show I2-GNNs can distinguish the 4x4 Rook's graph and the
L1=1
= INyilRA
Σ
(1=1)>
(19a)
IEN(K)
NigA M
(1)
Σ
(1) (1)
(19b)
(EN(R)
Then we can see in h-hop ego-net of the 4x4 Rook's graph, the node representations h (2) In contrast, in I-hop ego-net of the Shrikhande graph, the representations of common neighbors of i and j are 1. Therefore, I2-GNNs can distinguish the 4x4 Rook's graph and the Shrikhande graph.
i.j.A are all
E.2 PROOF THEOREM
P--NNs can count 2- 2-paths and 3-paths, since we have Theorem 3.1 and I2-GNNs are more powerful than Subgraph MPNNs. Concerning 4-paths, according to Lemma E. we let he... be number of 4-paths in forms of (i j - kt). Then one that h; JEN(s) Σ kev h4j.e equals to number of 4-paths involving
E.3 PROOF OF THEOREM
P--NNs can count 3-cycles and 4-cycles since we have Theorem 3.1 and P-GNNS are more pow- erful than Subgraph MPNNs. Also, given Lemma E.I] we can let higi & be the number of 4-paths in forms of (i + + + k). Then one can show that his Σ EENN()) hij. equals to the num- ber of 5-cycles involving edge (i.j). Thus h; EjEN()) h4,5 is exactly the number of 5-cycles involving node
Now 1et us prove that 1-- GNN can count 6-cycles. We note that necessary condition of a 6-cycle is that there exist a 4-path and 2-path from node simultaneously, as shown in left-most pattern in Figure 5 Thus let us consider the following function:
#o(1)
Pa(i,A) Ps(ikk),
(20)
KEV
where Pa(i, kt,, (1 k) are number of 2-paths and 4-paths from i to k. However, #o(1) is not equal to the number of G-cyeles: the right three patterns in Figure 5 also contribute to #o()). In fact, let
18

---

Published as a conference paper at ICLR 2023
(i)
(t
(1(
#4(1)
Figure 5: The first four patterns satisfy: there exist a 4-path and a 2-path from node to ls simulta- neously.
#1)) #2(1), #t(1) be the number of these three patterns that involves node i, then we have the following relation (Fürer 2017):
Co(i) #o(i) - #1 #i) #a(().
(21)
We now prove that I2-GNNs can express #o to #3. which consequently proves that 12-GNNs can count 6-cycles.
Case O. Using Lemmal E. we can let h4.5. P - k), i.c. the number 4-paths in forms of (i - - ... k). Besides, can let h Po k), since counting 2-paths does not require identifier of j. Then we have
+
Σ JEN(() REV
Σ
E E -k) KEV
P2),k(
Σ Pa(i-j- +.. Pz(i,k)
(22)
REV
JEN(()
Σ ((,,,) = = #o(1).
KEV
Case 1. To count #i)), notice that the 4-paths and 2-paths from to k share the same second last node. This equivalent to number of 4- 4-paths with second last node being the neighbor of Therefore, construct message passing functions follows:
1 1ifi
Σ
LE=)
(23a)
1
IEN(K)
(22
(I)
i.j.k
(23b)
IEN(K)
(8)
Σ
(1)
(2)
h (1)
(23c)
JEN(K)
Here 2, is an indicator that labels the neighbor of i. Only the neighbor of i can pass messages in the last step. Thus f.j equals the number of 4-paths in forms of (i - - - k) with the second last node being the neighbor of i. One can then that ΣjENO) Σtev high #1(1).
Case 2. It is relatively difficult to count #2(1). We first derive the following equation:
#2(1) Σ Σ (Ca(i.) ((ME)) (Cali,)) ((.,)EE)) 2 #4(1),
(24)
KEV JEN(S)NN(M)
where Cs(i,j), Cs(j.k) k) number of triangles that involve (i,j) and (j, k) edges, and # #((1) the number of the rightest pattern shown in Figure 5 Let us explain why true. The term Σtev ΣjENGnNa) Cs(i.))Cs(i counts the cases where and it are both in triangles that
19

---

Published as a conference paper at ICLR 2023
shares common node. However, it is not equal to #2(1), since (1) if i, adjacent, then it contributes an additional triangles to each iterating node j in the summation; (2) If rightest patterns in Figure 5 appears, it contributes two unexcepted counts. Thus by substracting these redundant counts, we obtain equation (24).
Now let prove that I2-GNNs can express #2(i) through equation 24 We first transform the first term into:
E E - ((,))))) (Cs(i,)) k) 1 (1,))E)
REV JEN()NNN())
Σ
Σ
IAEE (Ca(i.)) ((AA)E)) (Cs(i, k) (6,))E)
REV JEN()
Σ Σ
CU..EE (C)(i.)) 11 ((ME)) 1 GAAEE (
(LMEE (Cs(j,k) ((AEE))
keV JEN())
E Cali,))
Σ kEV
KENO) (Cali,)) k) 1AEN()) Σ 1KENGONG)) (Ca(i,k) - 1IEEN())
JEN(S)
JEN(
(25)
We then use P-GNNS to encode ha.j. as follows:
hij, (1))))()) 1ENN)) Cs(j,))) T
(26)
Note that these encodings are easily to expressed by message passing. Now we can finally express equation (25) using high.i
Σ Ca(i,j) Σ
TRENC) (Cz(i,)) 1IEN())
Σ
IREN()NNG) (Ca(j, TRE(())
JEN())
JENO.
KCV
Σ JEN())
Σ KEV
has hes.ahhise
Σ KEV
2 hess.))
Σ
Σ
h.
hi..ka)..
JEN(S) KEV
(27)
Next let us prove that I--NNNs can count #i()). Image we label the neighbor of i j. then this pattern occurs if and only if there exists a node V fi such that: (1) is the neighbor of j; (2) & is the neighbor of the nodes in ((1) (().. Thus we can write down the following message
passing functions:
Mig h (
= 1 INiIIKK
Σ
(1=:)
11=)
(28a)
(EN(K)
1igh
(2)
I M...K. (EN(R)
Σ
i (1) 131.2"
(28b)
The resulting &/2 EjEN() Etev (2) equals to #4(1).
Case 3. Note that #1( equals to the multiplication the number 4-paths and 2-paths that share the same second node, i.e. - + defined as follows:
*) and (i - x). Consider the message passing
h 1i.k = 1ifi Σ 1
(29a)
(EN(K)
1xxi Kej
Σ
(1)
(29b)
Light
(EN(K)
Σ
( - k(3
-h
(29c)
(K)
20

---

Published as a conference paper at ICLR 2023
4-clique
Chordal cycle
4-cycle
Tailed triangle
3-star
3- 3-path
4-path
Triangle-Rectangle
Figure 6: Some of the connected Graphlets with size 4 and 5. We define the node-level counting (graphlet, i, G) be the number of graphlets involving at the position shown in the figure.
Then #s(1) ESEN() Exey (3) Rig.k
Since can express #o(1), (1), #2(1), #3()), we able express number of 6-cycles involv- ing node i using Co #o(1) #1 - #2(1) - #s(1).
E.4 PROOF THEOREM 4.3
All connected graphlets with size 3 include 2-paths and 3-cycles, which have been proven before. Now let us consider all connected graphlets with size 4, shown by the first six graphs in Figure 6
4-Cliques. The definition of 4-clique is equivalent additional node. Thus if i are the root node and one of its neighbors, then number of 4-cliques equals number of triangles that involve but not and whose nodes connected Based this observation, we design the following message passing:
triangle with all nodes connected to an
h (1)
(
in Rish Σ
||=j
l=t
(30a)
IEN(K)
(2(2)
Ri 1 Tegg iij,,, i.
Σ
(1) Paaa,
(30b)
LEN())
Then can find that &8 E)E()) ΣnEV h 1.j.k equals to the number of 4-clique involving node i.
Chordal cycles. We first mark all the common neighbors of i,j by one layer of message passing, represented by (1 (eN(() KENU)- Then the key is find number of triangles that involves both the common neighbors and j. We therefore construct the second layer message passing as:
(2) iij.A
InyelaAj
Σ
h 1
(31)
(EN(())
Then one should see that Eiev EjeN() EXENGY (2) equals to the number of chordal cycles in the graph.
Tailed triangles. Let be the node that connects tailed node j. Then let has be number of triangles involving i but not j. One can see that Eiev EjeN()) his is the number of tailed triangles.
4-cycles and 3-paths. By theorems and 4.2
E.5 SOME OTHER GRAPHLETS
4-paths. By theorem 4.2
21

---

Published as a conference paper at ICLR 2023
Triangle-RRetangleer Let i be the node that is in the triangle but not in the rectangle. Let j be the neighbor of i. Recall that we can use the labeling of j to mark the 3-hop nodes. Then by determining if these nodes are the common neighbors of i, J. we can count the number of triangle-rectangle.
F ADDITIONAL DETAILS OF THE NUMERICAL EXPERIMENTS
Table 7: Statistics the synthetic, ChEMBL. QM9, ZINC and OGB datasets.
Dataset
#Graphs
Avg. #Nodes
Avg. #Edges
Task type
Synthetic
5,000
18.8
31.3
Node regression
ChEMBL.
16,200
21.5
22.9
Node regression
QM9
130,831
18.0
18.7
Graph regression
ZINC-12K
12,000
23.2
24.9
Graph regression
ZINC-250K
249,456
23.1
24.9
Graph regression
ogbg-molhiv
41,127
25.5
27.5
Graph classification
F.1 GRAPH STRUCTURES COUNTING
Dataset. The synthetic dataset is provided by open-source code of GNNAK on github The real- world dataset ChEMBL (httss//www.ebi.ac.uu
contains bioactive molecules with drug- like properties. We filter the dataset by the following process: compute the average number of 4,5,6-cycles per atom for each molecule, add uniform noises (U(-0.05, 0.05)) and sort the molecules based on the average number of cycles per node. We then apply CD-HIT (Li & Godzik, 2006). a clustering algorithm, to cluster the molecules with similarity measured by their fingerprints. We screen 16,200 cluster centers such that each pair of them has similarity less than 0.4. These 16,200 centers (molecules) are used to build our final dataset. The ground-truth labels are obtained by www.orkkalggrritmms.ssoooom isomorphism package.
Models. For ID-GNNs, Nested GNNs and 1--NNNs, we uniformly adopt 5-layer GatedGNNs Li al., 2015) as base GNNs. For GNNAK+, we use 5 GNNAK+ layers, each of which is 1-layer GatedGNN. The embedding size of mentioned models above is 64. The subgraph height is 1, 2, 2, 3 for 3, 4, 5 and 6-cycles respectively. The initial features are augmented with shortest path distances except ID-GNNs. For PPGNs, use 4 PPGN layers with blocks and embedding size 300. The subgraph height is 1,2,2,3,2,2,11,44 1,2 for 3-cycles, 4-cycles, 5-cycles, 6-cycles, tailed triangles, chordal cycles, 4-cliques, 4-paths and triangle- respectively, so that the subgraph can include the graphlet.
Training details. The training/validatiioneess splitting ratio is 0.3/0.2/0.5 on synthetic dataset, and 0.6/0.2/0.2 on ChEMBL. dataset. We uniformly use Mean Absolute Error as loss function except 3-cycle. In the 3-cyele case we use Mean Square Error instead, as some training loss get stuck. We use Adam optimizer with initial learning rate 0,001, and use plateau scheduler with patience 10 and decay factor 0.9. We train 2,000 epochs for each models. The batch size is 256.
F.2 MOLECULAR PROPERTIES PREDICTION
F.2.1
QM9
Dataset. The QM9 dataset is provided by pytorch geometric.
Models. We delopt--layee NNConv (Gilmer et al. 2017) as base GNNs of 12-GNNs. The embedding size is 64, and the subgraph height is 3. The initial features are augmented with shortest path distances and resistance distances (Lü & Zhou 201T).
Training details. The raaiiingvvlidatioonnes splitting ratio is 1.0.. We use Adam optimizer with initial learning rate 0.001, and use plateau scheduler with patience 10 and decay factor 0.95. We train 400 epochs with batch size 64 for each target separately.
F.2.2 ZINC
Dataset. We use the dataset provided by Dwivedi et al. (2020). contains ZINC-12k and a ZINC-
250k.
22

---

Published as a conference paper at ICLR 2023
base GNNs of I-GNNNs. The embedding size 64, and the subgraph height 3. The initial features are augmented with shortest path distances and resistance distances. To further improve the empirical performance, concatenate the pooled node embedding h& to the corresponding node hi.j.k at each layer: hij. < hs..j 4 hg-
Models. We adopt 5-layer GINE (Hu et al. 2019)
Training details. The training/validatiioneess splitting is given by the dataset. We Adam opti- mizer with initial learning rate 0.001, and use plateau scheduler with patience and decay factor 0.95. We train 1, 1,000 epochs with batch size 256 Zine- Rinc and train 800 epochs with batch size 256 on 250k.
F.2.3 OGB
Dataset. The ogbg- molhiv dataset provided by Open Graph Benchmark (OGB).
Models. We adopt 5-layer GINE as base GNNs of P-GNNs/ The embdding size is 300, and the subgraph height is 4. The initial node features are augmented with shortest path distances and resistance distances.
Training details. The training/validationnesst splitting is given by the dataset. We use Adam opti- mizer with initial learning rate 0.001, and use step scheduler with step size 20 and decay factor 0.5. We train 50 epochs with batch size 64.
G CYCLES STATISTICS ON DATASETS
We demonstrate the the average number of cycles on different datasets. We can see that 5-cycles and 6-cycles dominant compared 3-cycles and 4-cycles. It reflects the importance of counting to 6-cycles.
Table 8: Average number of cycles per graph the synthetic, ZINC and OGB datasets.
Dataset
Avg. # 3-Cycles
Avg. # 4-Cylles
Avg. # 5-Cycles
Avg. 6-Cycles
Synthetic
5.04
10.60
21.67
41.6
ChEMBL
0.06
0.03
1.72 0.69
ZINC-12K
0.06
0.02
0.85
1.80
ogbg-molhiv
0.03
0.04
0.70
2.28
H MORE ABOUT COUNTING EXPERIMENTS
H.1 COUNTING ERROR VERSUS NUMBER OF CYCLES
In addition, we try to understand the performance of I2-GNNs by further analysis and visualization. subfigures (a,c) in Figure we visualize the label distribution of 5-cycles and 6-cycles on synthetic dataset, i.e. nodes with different number of cycles. We see that the number of nodes with increasing cycles decays exponentially. Thus implies the difficulty to generalize to nodes with more cycles. In the subfigures (b.d) in Figure 7 we show the corresponding prediction average MAE nodes with different number of cycles. we can see that the MAE of Subgraph GNNs increases dramatically as the number of cycles become larger. In contrast, 12-GNNs have almost flatten curve, implying it fits the real counting function well and thus generalizes better.
H.2 RESULTS OF COUNTING AT GRAPH LEVEL
Using the same setup in node-level counting, we also conduct counting experiments at graph level. Note that I2-GNNs can count 6-cycles at graph level with theoretical guarantees (by Theorem 4.1 while other Subgraph GNNs are unclear. Interestingly, the experimental results in Table show that all Subgraph GNNs attain comparable performance with respect to I2 I--GNNs and PPGNs. It may be because: (1) they capture some statistical biases that are highly correlated to graph-level counting functions; (2) they can count up to 6-cycles at graph level theoretically. The graph-level counting power of Subgraph GNNs is unclear from 5-cycles to 7-cycles and worthy exploring the future research.
23

---

Published as a conference paper at ICLR 2023
12000
1.2
10000
1.0
Number nodes
8000
Counting MAE
0.8
0.6
4000
0.4
2000
0.0
0
5
10
15
20
25
30
0
5
10
15
20
25
30
Nodes with # 5-cycles
Nodes with 5-cycles
(a)
(b)
2.0
6000
Number of nodes
5000
Counting MAE
1.5
3000
2000
0.5
0.0
0
10
20
30
40
50
60
0
10
20
30
40
50
60
Nodes with 6-cycles
Nodes with 6-cycles
(c)
(d)
Figure 7: Left column: distribution of number of cycles nodes. Right column: prediction MAE conditioning nodes with certain number of cycles.
Table Normalized MAE results with errors of counting substructures at graph level. The reported uncertainty is one times standard deviation.
Synthetic (norm. MAE)
Method
3-Cycle
4-Cycle
5-Cycle
6-Cycle
GatedGCN
0.3545=0000577
0.248140.0010
0.1849:0.0014
0.1500+0.0036
ID-GNN
0.0064110.001 0.0005
0.0070:10.0110
0.0182+0.0010
NGNN
0.0009+0.0002 0.0054+1000005
0.0077#0.0026
0.0249+0.0010
GNNAK+
0.002110.0004 0.0177+10.0026
0.0233+0.0022
0.041240.0025
PPGN
0.0013+0.0007 0.0050+10.0005
0.0123+0.0013
0.015910.0015
F-GNN
0.0010=100001
0.0066110.0011
0.009810.0005
0.023740.0011
I ABLATION STUDY
In ablation study, we focus studying the impact of the key element of 12-GNNs: the additional identifiers. Concretely, let i be the root node and j be the branching node (neighbor i), we drop all the node labeling concerning j in the subgraph Gi It results in model denoted I2-GNNs (single) with only one identifier and all other hyper-paranee parameerssestrrs unchanged. In additional, we also study identity labeling. We implement I2-GNNs (id), where
the effect of the shortest path labeling the shortest path labelings 2.j.k = spd(i, k) e spd(j, k) are replaced with the identity labeling that performance drops greatly for 5, G-cycles,
Zijjk 1 i= 1 jj=k- From Table T0
24

---

Published as a conference paper at ICLR 2023
Table 10: Ablation study on single node labeling and identity labeling. The reported uncertainty is one times standard deviation.
Dataset/Task
P-GNNs
P-GNNS (single)
I'.GNNs (id)
3-Cycle
0.0003:10.0000
0.00041100002
0.0003=0.0001
4-Cycle
0.0015+:0.001
0.0021
0.0015=0.0001
5-Cycle
0.0028#000001
0.0426:#0.0005
0.0034=0.0000
6-Cycle
0.007
0.0465:10.0009
0.0103=0.0021
4-Clqiue
0.0003++000001
0.0604++0.000
0.0012
4-Path
0.0040
0.0241#0.0007
0.0019=0.0001
Triangle-Rectangee
0.0026 0.0002
0.0566=10.0015
0.0017=0.0001
4-cliques, 4-paths and triangle-rectangll after removing the additional identifiers. This is consistent to our claim that the additional identifiers boost the counting power. In the comparison between shortest path labeling and identity labeling, see that they do not dominate each other. This because they have the same representational power and thus the results should depend on the inductive bias of the task.
DISCUSSION ON COMPLEXITY
J.1 COMPARISON TO OTHER GNN MODELS
I2-GNNs increase the representational power by extending Subgraph MPNNs (single identifier) to pair of identifiers. the language of equivariant lensors, I-GNNs lift the original graph (adjacency matrix, 2-order tensor) to 4-order tensor (first two indices for the two identifiers, last two indices for adjacency), and perform message passing on this 4-order tensor. Thus one should expect I2-NNNs' power be upper bounded by 4-IGN/4-WI. plexity, suppose a graph has N nodes with average node degree d, and the maximum subgraph size s. One layer message passing takes (d) time for one node. By leveraging the sparsity of graphs, I2-GNNs reach a linear time complexity ((Nsc) w.r.t. node number N. Specifically, counting 6-cycles only requires extracting 3-hop rooted subgraphs, resulting in ((Nd)) complex- ity. Note that in molecule datasets the node degree is usually small (e.g., QM9 has an average node degree 2.1), which makes the computation feasible. This in contrast to the least O(N3) com- plexity of those high-order GNNs such as PPGNs (Maron et al. (019a) and k-IGNs (Maron et al.) 2018). Some works also try to design localized high-order GNNs. For example, k-GNNs (Morris) al. 2019) and 8-K-LGNNs (Morris et al.) (0220b reduce the time complexity to linear by straining the k-tuples to be connected and aggregating messages from neighbors only. Compared to them, 12-GNNs have exclusive advantage: the initial features Zij.k can be augmented with some three-tuple attributes, such as Ti.j.- = (spd(i, k), spd(j. k)) or other structural/possitoon encod- ings. Besides, I2-GNNs have provable substructure counting power. Local relational pooling (Chen) et al. 2020) is universal approximator for permutation invariant functions over subgraphs, but the O(Ns)) s!) complexity is almost infeasible. A contemporary work (Qian et al.] (022) also discusses the possibility of high-order Subgraph GNNs: they propose to tie each subgraph with k-tuple. However, their main focus is the theoretical comparison with WL test. Besides, the complexity of their original model grows exponentially.
implied in Frasca al. (2022). Regarding the com-
Table 11: Space and time complexity of different GNN models.
Model
MPNN O(N)
Subgraph MPNN
ICGGNN O(Nsd) (NNsd))
PPGN
1-2-3 GNN
Space complexity
O(Ns) O(Nsd)
O(22)
O(Nd))
Time complexity
O(Nd)
((N3)
O(Nd3)
J.2 EMPIRICAL COMPLEXITY EVALUATION
We empirically compare the models' complexity through: (1) number of parameters (#Parm)); (2) Maximal GPU memory usage (Max. memory usage) and (3) inference time. We adopt node-level counting task. The model implementation is exactly the same in F. except that PPGN's embed-
25

---

Published as a conference paper at ICLR 2023
Table 12: Empirical evaluation of complexity of 12 -NNNN, Subgraph GNNs and PsGNs.
Model
MPNN
ID-GNN
NGNN
GNNAK+
F-GNN
PPGN
# Parms
27k
102k
127k
25Tk
143k
96k
Memory usage (GB)
1.88
2.35
2.34
2.35
3.59
2.30
Inference time (ms)
2.10
5.73
6.03
16.07
20.62
35.33
ding size adjusted to 64 for fair comparison. Batch size 256, and we run 10 epochs compute the average inference time per batch and the maximal memoery usage during inference. We use thop package estimate the number of parameters. Note that in the realizations of listed Subgraph GNNs and -NNN,, the subgraph extraction is preprocessed and thus the forward computation is in parallel. This causes greater memory usage but a faster speed of training/inferenee.
From the Table 12 we can see that the inference time of I2-GNNs is feasible, since the average node degree of counting dataset is approximately 3.3.
K SCALING UP: BRANCH NODE SAMPLING
Like Subgraph MPNNs, the extracted K hooo ego-networks size in 12 IN-GNNs is Odd)), ). In addition, compared to Subgraph MPNNs, I2-GNNs further increase the complexity by a factor of node degree d. In case where average node degree is large the node degree distribution is heavy-tailed, the computational cost might still be unfordable.
Table 13: Statistics of the selected datasets from TUD benchmark.
Dataset
#Graphs
Avg. #Nodes
Avg. #Edges
ENZYMES
600
32.6
62.1
IMDB-BINAS BINARY
1,000
19.8
96.5
One can apply any subgraph sampling strategy address the growing subgraph size problem, as the one in ZZhao et al. (2021). Here we focus on alleviate the growing branch node problem. We provide simple but effective sampling strategy: randomly sample fixed number of branch nodes to bound the additional factor by a constant. The sampling are only applied to training process, and thus permutational equivariance still holds during test.
Table 14: Test accuracy (%) with one standard deviation on TUD benchmark. I--GNN-smpple refers to 12-GNNs that randomly choose and fix two branch nodes to label before training.
Datasets ENZYMES
Base GNN
Nested GNN
I-GGNN
s--NNl
27.347.8
31.743.7
35.8+7.1
33.8+5.9
70.2+5.1
71.4+5.9
73.5+3.0
72.7+3.9
Table 15: #parameters / training time per 200 epochs (s) / inference time per epoch (ms) on TUD benchmark. Training/inference time are estimated on full dataset.
Datasets ENZYMES 24k/19 45559.009 .009 24k/31.19/88.00
Basc GNN
Nested GNN 25k/30.31/107.40 .4 25K/65.28/238.9
FN-NNN
I 12-sampleGGNN 34k/45 68/213.03 34k/100.33/1270.62
44K/62.822/13..4 34K/355.98/123330
IMDB-BINARY
Formally, let N(i) be the neighbor of root node i. An Ie-sample-GNN has the same architecture with PNGNNN during training, except that
in equation (6). the branch node j iterates over Sample (N)()) instead of N(1, where Sample a sampling function that randomly chooses elements from the multiset.
in equation ( the node read-out function becomes
ViEV. h; a Rmose (1h,, (amp)e;(N(()))),
(32)
where a; = 4 if R is additive to node degree d, (such as sum pooling), and a; = 1 if
Ronde is independent of node degree d, (such as average pooling).
26

---

Published as a conference paper at ICLR 2023
On the other hand, sampling is disabled when doing inference in order to assure permutational equivariance, i.c. ---sample-GNe use the exactly same architecture with I2-NNN during inference. Note that because of the stochastic branch node sampling, (--sampleGGNY would not be able to learn exact counting function. Instead approximates the counting function in an expectational meaning.
To test the effectiveness of branch node sampling, we choose some high-node-derree datasets from TUD benchmark (Morris al., 2020a). Table [3 above shows the dataset statics. We randomly choose and fix two branch nodes for each root node before training. The sampling does not apply testing. We compare performance of I -GNNs with branch node sampling that of original 12. GNNs, base GNN (4-layer GraphConv) and Nested GNN. The subgraph depth is 3 for ENZYMES and 2 for
We train each model for 200 epochs, with initial learning rate 0.002 and decay rate 0.5 per 50 epochs. We report the 10-fold cross validation results in Table 14 It demonstrates that P--GNNs with even simple branch node sampling still can bring improvements to baselines and achieve competitive performance to original I2-GNNs.
Moreover, we compare the number of parameters, the training/test time these models, as shown in Table 15 As we expected, |--sample-GNi can significantly reduce the training time, especially for high-nodc-degree dataset MDB-BINARY
27


Reviews:
[{"review_id": "wpaHfhnh1T", "reviewer": "Reviewer_Mx4a", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors of this paper propose a new Subgraph MPNN architecture, called $I^2$-GNNs, that can count up to 6-cycles in contrast to other Subgraph MPNNs which cannot count such long cycles. For each rooted subgraph centered at node $i$, they construct d(i) subgraphs, where d(i) is the degree of the center node, defining a mapping between the generated subgraphs and the neighbors of the root node. Then, they assign a unique identifier to the center node $i$, and another unique identifier to one of the neighbors of the center node, for each generated subgraph. They use MPNNs in each subgraph to construct the graph's final representation, followed by a readout layer. They evaluate their model in cycle counting tasks as well as in molecular property prediction benchmarks, achieving competitive performance.\n", "summary_of_the_review": "The proposed method is technically sound, well written, and leads to performance gains on some molecular property prediction datasets. However, I think that the main idea of incorporating identity node features has been studied in the past thoroughly and the paper does not discuss these methods in details. Specifically, I would suggest the authors do the following:\n- Discuss more and extend the related work with other similar approaches that incorporate extra node features/identifiers and explain why the current approach is more suitable than the others.\n- Compare with more baselines and evaluate the model in more benchmarks (see above).\n- Explain how the current approach can be applied to dense graphs, where the average node degree is high, probably by employing some sampling strategies.\n\nI would be happy to increase my score if my concerns are well addressed. \n", "strength_and_weaknesses": "Strengths: \n- The authors of the paper present some new theoretical results regarding Subgraph MPNNs. Specifically, they prove that the proposed models can count 3-cycles and 4-cycles, but cannot count 5-cycles or any longer cycles.\n\n- The authors also present a new Subgraph MPNN architecture that is more powerful than existing Subgraph MPNNs. They also prove that it can count all cycles with length less than 7 which is important for real-world applications (e.g., identifying benzene rings).\n\n- The proposed models achieve competitive performance in graph classification and regressions tasks (QM9, ZINC and ogbg-molhiv) and demonstrate increased expressiveness in discriminating non-isomorphic graphs and in substructure counting.\n\nWeaknesses: \n- My main concern with this paper is with regards to the novelty of the work, as in essence, it proposes to add an extra identifier for each pair of nodes. There are many works that add unique node identifiers in GNNs to increase the expressive power of the models [1,2] and in the current paper, a proper discussion of these approaches is missing. Also, a comparison with [3,4] would be interesting, as they also build more expressive GNNs with extra node features.\n\n- The proposed model generates a new subgraph for each edge in the original graph, and therefore the computational complexity is higher than that of other subgraph MPNNs. As the authors mentioned, the proposed model is evaluated only on graphs with a small average node degree. I would suggest the authors discuss how the proposed approach can be applied to graphs with high average node degree and also evaluate their model on such graphs, for example, in the TUD benchmark [5]. \n\n[1] Andreas Loukas. How hard is to distinguish graphs with graph neural networks? In Advances in Neural Information and Processing Systems (NeurIPS), 2020.\\\n[2] Andreas Loukas. What graph neural networks cannot learn: depth vs width. In ICLR, 2020.\\\n[3] Dwivedi, Vijay Prakash, et al. \"Graph neural networks with learnable structural and positional representations.\" arXiv preprint arXiv:2110.07875 (2021).\\\n[4] Wijesinghe, Asiri, and Qing Wang. \"A New Perspective on\" How Graph Neural Networks Go Beyond Weisfeiler-Lehman?\".\" International Conference on Learning Representations. 2021.\\\n[5] Morris, Christopher, et al. \"Tudataset: A collection of benchmark datasets for learning with graphs.\" arXiv preprint arXiv:2007.08663 (2020).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "loGbWpN_jFO", "reviewer": "Reviewer_FzhU", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work studies the counting ability of subgraph MPNN models, and present I^2-GNN to increase the counting ability of subgraph MPNNs. The proposed I^2-GNN is able to discriminate 6-cycles in theory and achieves good performance in molecular property prediction.", "summary_of_the_review": "Overall, this work proposes a novel method in enhancing the representation ability and counting power and of graph neural networks. Both the theorical and experimental contributions of this work are strong. I vote for accepting this work.", "strength_and_weaknesses": "Strengths:  \n(+) This work makes very solid and novel contributions to developing more expressive graph neural network models. The idea of improving the subgraph counting ability by assigning different identifiers to the root node is interesting and elegant.  \n(+) Comprehensive theoretical analysis and empirical studies are presented to show the effectiveness of the proposed I^2-GNN model.  \n(+) The writing of this paper is very clear and well-organized.  \n\nWeaknesses:  \n(-) Some experimental settings are unclear to me in graph substructure counting. For experiments in section 6.2, the prediction targets are cycle or graphlet counts, which are discrete numbers. Do GNN models output continuous numbers to approximate discrete targets and the MAE is evaluated between them?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "Sr9PkPjeou", "reviewer": "Reviewer_GzCp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new Graph Neural Network architecture enhancing the standard message passing architectures (MPNN). The main idea is to run various MPNNs on rooted subgraphs of the original graph. The authors show that their architecture I2-GNN is more powerful than previous MPNN. They show theoretical results where I2-GNN is able to count longer cycles (3,4, 5 or 6-cycles) and paths (3 or 4-paths). They also show some theoretical limits of I2-GNN. In their last section, they conduct experiments to substantiate their claims.", "summary_of_the_review": "The paper presents interesting theoretical results but experimental results are weak.", "strength_and_weaknesses": "The theoretical analysis made in this paper is rather convincing.\nThe main weakness is the special focus on counting (short) cycles and paths. The expressive power of MPNN can be improved by adding extra-features like it is done in this paper but it is not clear that focusing on cycles and paths is actually the best use of resources. Indeed, the experimental results on real datasets are quite disappointing in this respect as CIN seems to outperform the I2-GNN on ZINC and ogbg-molhiv.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AhWvKP2-2sY", "reviewer": "Reviewer_Yf1m", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Message-passing neural networks (MPNNs) and their extensions (Subgraph MPNNs) have inspired state-of-the-art models for graph data; however, their counting power is still limited and it is known that Subgraph GNNs cannot count cycles with more than $4$ nodes.\n\nTo boost the counting power, this paper extends the idea of having a single root node identifier in Subgraph GNNs to two identifiers for a (root node, neighbour) pair resulting in the proposed I$^2$-GNN model.\n\nI$^2$-GNN has the following properties:\n1. It can count all cycles of length at most $6$,\n2. It has linear space and time complexity provided the node degree is bounded,\n3. It achieves competitive results on open benchmarks compared to existing models.\n\n___", "summary_of_the_review": "While the paper is well-motivated and the claims are well-supported with theory and experiments, positioning with respect to relevant prior work can further strengthen the contributions.\n___", "strength_and_weaknesses": "\\\n**Strengths**\n\n\\+ The paper is well-organised, well-written, and the problem of counting power is well-motivated.\n\n\\+ The proposed method is potentially scalable to large-scale real-world data and potentially useful for real-world chemical data involving cycles of length at most $6$ (e.g., benzene rings).\n\n\\+ Under certain conditions (e.g., bounded node degree), the proposed model is the first linear-time GNN model to count $6$-cycles.\n\n\n**Weakness**  \n\nThe only major weakness of the paper is the lack of positioning/comparison of the idea of using multiple identifiers for node pairs (of edges) with labelling tricks [1] (used in the context of link prediction)\n\n[1] Labelling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning, In NeurIPS'21\n\n___", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-hvSqGrUVy", "reviewer": "Reviewer_YNBY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Message Passing Neural Network (MPNN) is a simple yet efficient class of Graph Neural Networks (GNNs), which have been widely adopted in many previous works. However, it is also known that MPNN has limited representational power due to its simple structure. This paper, in particular, considers subgraph methods. The authors first show that Subgraph MPNNs can count 3-cycles and 4-cycles, but cannot count 5-cycle or any longer cycles at the node level. The cycle counting is important to understand structure since cycles are the basic elements constructing some important substructures. Then, they propose I^2-GNN that can count cycles with lengths less than 7. Based on this, I^2-GNN has a stronger discriminative power than subgraph MPNNs. I^2-GNN outperforms baselines in molecular prediction benchmarks.", "summary_of_the_review": "This paper has a novel method and its theoretical motivation. However, the experiment section is weak.", "strength_and_weaknesses": "Strengths\n\n- The proposed algorithm $I^2$-GNN theoretically guarantees the power of counting 6-cycles. This is the first algorithm that can guarantee such power. \n\n- The algorithm's empirical performances support the theoretical results.\n\n\nWeakness\n\n- The computational complexity of $I^2$-GNN is proportional to the degree of the graph. So, when the degree follows a power law (a heavy tail distribution), the complexity could be much higher than before.\n\n- The empirical study considers QM9 and ZINC. This could be a limited set. It would nice to consider node OGB data set and classification tasks with cora, citeceer, pubmed. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster