Graph Neural Networks Can (Often) Count Substructures
Authors: Paolo Pellizzoni
Till Hendrik Schulz
Karsten Borgwardt
Venue: ICLR 2025 Spotlight (2025)
Keywords: graph neural networks
subgraphs
expressivity
Primary area: learning on graphs and other geometries & topologies
TL;DR: We provide a theoretical analysis of the subgraph-counting capabilities of graph neural networks beyond the worst case.

Abstract: Message passing graph neural networks (GNNs) are known to have limited expressive power in their ability to distinguish some non-isomorphic graphs.
Because of this, it is well known that they are unable to detect or count arbitrary graph substructures (i.e., solving the subgraph isomorphism problem), a task that is of great importance for several types of graph-structured data. 
However, we observe that GNNs are in fact able to count graph patterns quite accurately across several real-world graph datasets.
Motivated by this observation, we provide an analysis of the subgraph-counting capabilities of GNNs beyond the worst case, deriving several sufficient conditions for GNNs to be able to count subgraphs and, more importantly, to be able to sample-efficiently learn to count subgraphs. 
Moreover, we develop novel dynamic programming algorithms for solving the subgraph isomorphism problem on restricted classes of pattern and target graphs, and show that message-passing GNNs can efficiently simulate these dynamic programs. 
Finally, we empirically validate that our sufficient conditions for GNNs to count subgraphs hold on many real-world datasets, providing a theoretically-grounded explanation to our motivating observations.

Published as a conference paper at ICLR 2025
GRAPH NEURAL NETWORKS CAN (OFTEN) COUNT SUBSTRUCTURES
Paolo Pellizzoni, Till Hendrik Schulz, Karsten Borgwardt Max Planck Institute of Biochemistry, Martinsried, Germany (pel ppellizzoni, tschulz, borgwardt] (erdddt)bbbooooe (wwpeebb...mmmo............ de
ABSTRACT
Message passing graph neural networks (GNNs) are known to have limited ex- pressive power in their ability to distinguish some non-isomorphic graphs. Be- cause of this, it is well known that they are unable to detect or count arbitrary graph substructures (i.e., solving the subgraph isomorphism problem), task that is of great importance for several types of graph-structured data. However, we observe that GNNs are in fact able count graph patterns quite accurately across several real-world graph datasets. Motivated by this observation, we provide an analysis of the aubgraph-counting capabilities of GNNs beyond the worst case, deriving several sufficient conditions for GNNs to be able to count subgraphs and, more importantly, to be able to sample-efficiently learn to count subgraphs. More- over, we develop novel dynamic programming algorithms for solving the subgraph isomorphism problem on restricted classes of pattern and target graphs, and show that message- messagg--pssing GNNs can efficiently simulate these dynamic programs. Fi- nally, we empirically validate that our sufficient conditions for GNNs to count subgraphs hold many real-world datasets, providing theoretically-groundee explanation to our motivating observations.
INTRODUCTION
Graph neural networks (GNNs) have emerged as powerful tools for learning on graph-strume graph-structured data, achieving significant empirical success across diverse domains including computational chem-
istry, bioinformatics, and social network analysis. However, the expressivity of these models in the context of graph classification, i.e., their ability to distinguish non-isomorphic graphs, is intrinsically limited by the capabilities of the Weisfeiler-Lemaa (I-WL) algorithm (Weisfeiler Leman 1968),
a heuristic used for the graph isomorphism problem (Morris et al. 2019: Xu et al. [2018). WLL known to fail to distinguish certain classes of graphs, such as regular& graphs (Arvind et al. 2017
As consequence of this, in the seminal work "Can Graph Neural Networks Count Substruc- tures?" (Chen al. 2020), it shown that GNNs are unable to count arbitrary subgraphs, capability that is crucial for many real-world applications. The ability to detect and count substructures in graphs is of particular impor- tance in fields such as chemistry and biology, where specific molecular substructures often determine functional properties.
Table 1:
Test set results for subgraph counting with GNN on molecular graphs. Reported: AU- ROC for multi-class classification and normalized mean avg. error of the prediction (see Sect. D.I.
Pattem
C-O O
Dataset
Metric
C-O-O
C-OFO
Mutagenicity
aMAE
AUC
0.074
0.870
0.043
0.910
0.949
0.161
0.926
0.167
MCF-7
iMAE
AUC
0.019
0.941
0.859
0.013
0.031
0.955
0.011
0.925
The limited expressivity of GNNs has moti- vated the development of more expressive ar- chitectures, including higher-order GNNs that operate on k-tuples of nodes (Morris et al. 2019 Maron et al.] 2019). subgraph GNNs, which transform the original graph into set of modified subgraphs before applying GNN models (Cotta al. 202T Bevilacqua et al.
ZINC
mMAE
AUC
0.029
0.957
0.009
0.963
1.000
0.009
0.995
ogbg-molhiv
MMAE
AUC
0.001
0.923
0.004
0.915
0.011
0.917
0.002
0.972
ogog-molpcha
mMAE
AUC
0.000)
0.945
0.000
0.944
0.952
0.000
0.962
Peptides-fune
RMAE
AUC
0.029
0.977
0.001
0.936
0.000
0.940
0.882
0.001
POQM Contact
aMAE
AUC
0.006
0.948
0.000
0.987
0.002
0.986
0.001
0.999

---

Published as a conference paper at ICLR 2025
2021 Chen al.) 2020 Papp & Wattenhofer 2022), and models that incorporate unique node identifiers (Sato et al. 2021 Pellizzoni et al. 2024). However, these approaches often come at a sig- nificant computational cost, limiting their practical applicability, can show poor generalizability.
Interestingly, despite these theoretical limitations, we observe that standard GNNs are often able to count graph patterns with surprising accuracy across variety of real-world datasets. For example, Table reports the test set performance of a simple GNN model (Section A.II for the subgraph counting task, for several patterns (Section D.I]. across several widely used molecular datasets, us- ing only atom types as node labels. This shows a surprisingly good performance for task that in principle unsolvable. While these experimental findings are somewhat limited in scope, they suggest that GNNs possess the capacity to approximate subgraph counts, at least for certain patterns and certain classes of target graphs. This apparent contradiction between theory and practice moti- vates our work to better understand the subgraph-countis capabilities of GNNs beyond worst-case scenarios, via more nuanced analysis. Our contributions are the following:
(1) we provide conditions under which GNNs can efficiently realize functions on graphs that depend only on local substructures around the nodes (Theorem 2 including subgraph counting:
(2) we propose novel dynamic programming algorithms for restricted variants of subtree isomor- phism (Theorem 4) and show that GNNs can efficiently simulate them (Theorem 5
(3) we show that, in practice, many real-world graph datasets satisfy the sufficient conditions of point (1), and experimentally validate the claims of point (2) above.
Our work seeks to provide a theoretically-gronddee explanation for the observed ability of GNNs in subgraph counting, bridging the gap between theoretical limitations and practical performance.
1.1 RELATED WORK
Graph Neural Networks Expressivity Following the influential papers Morris et (2019 Xu
et al. (018) that exposed the constraints of GNNs due to their expressiveness being limited by the
1-WL test (Weisfeiler & Leman 1968). there has been surge in research aimed at developing more capable GNNs. A notable strategy has been to create GNNs that simulate higher-order WL Grohe 2017] or Folklore-WI. (Cai al. 1992) tests, as demonstrated by k-GNNs (Morris et al., 2019) and k-FGNNsp (Maron et al.) 2019). However, their computational and memory requirements are often impractical. Some of the subsequent approaches exploited graph locality and sparsity (Morris et al.
2022
Zhang et al. 2023
2022). An additional research direction involves subgraph Frasca et al.
GNNs (Cotta et al. 2021 Qian et al.
2022 Bevilacqua et al., 2021). Finally, individualization
schemes (Pellizzoni et al. [224 Bechler-Speiche
(2244) have been proposed by several works (Murphy et al.) [019]] Dasoulas et al. [2020] Franks et al.] (021) to enhance the expressivity of
GNNs and obtain universal function approximators (Abboud al. 202T). Sato (2020); Morris
ct al. 2223b) offer more comprehensive overview. Xu et al. (2020) demonstrated that GNNs can
learn to mimic classical graph algorithms, and provided a framework for studying the complexity of
simulating combinatorial algorithms with different architectures. For comprehensive overview of GNNs' capabilities in algorithmic tasks, readers are referred to Cappart et al. (2023).
Combinatorial subgraph counting Subgraph (both induced and not) isomorphism. and the re- lated counting tasks, are NP-hard (Alon et al., 1995). Due to the practical relevance of the tasks, several efficient search algorithms have been developed (Carletti et al. 2017 McCreesh et al., 2020) M017)MMCreesh
Another line of research, called color-coding, uses a dynamic programming approach (Alon et al.) 1995 2008 Arvind & Raman 2002). For the task of finding all frequent subgraphs in a dataset, there exist specialized al algorithms Nijssen & Kok 2005 Kuramochi & Karypis 2004).
Subgraph counting and GNNs Chen (2020) showed that GNNs are unable to count arbitrary subgraphs, and et al. (2024) obtain a full characterization of the subgraphs that can be counted on arbitrary graphs, i.e., considering the worst-case scenario. The subgraph counting problem has also been addressed on arbitrary graphs with ad-hoc architectures (Chen et al., 2020: Tahmasebi et al., 2023 Huang al. 2023b Paolino et al., (2224), with positional encodings (Huang et al.) 2023a) or with random node features (Kanatsoulis & Ribeiro 20244.. In this work, we instead focus standard message-passing GNNs. Subgraphs have also been used to improve the expressivity of
2

---

Published as a conference paper at ICLR 2025
GNNs by using subgraph counts as features (Bouritsas et al. 2022 by extending message-passiingg to subgraphs (Wang et al. 2023).
2 PRELIMINARIES
In what follows, we define a graph as a tuple G= (Va, EG, Ii)), with VG a finite set of nodes, and Ea S (u, u & v E Vc) set of undirected edges. We define the vertex-label function as Ti VG + E, with a finite set of labels Σ. For the sake of simplicity, we consider edges to be unlabeled. We define the neighborhood of node as (u) that two graphs G and H are isomorphic, denoted as G H, there exists a bijective mapping π VG - VHn, called isomorphism, such that Lạ(u)= = L (T))) Ve E Va and (=( (())} E En if and only if {u, o} E Eg. The isomorphism relation induces equivalence classes, which we call, with abuse of notation, graphs. The group of isomorphisms from G to itself is called the automorphism group Aul GG). A subgraph isomorphism from G into H is an injective mapping π VG + VH s.t. {T( m(t)} E Ey for every (u, E EG and (v( = LH( (T()),,, Ve E Vg. We call it an induced subgraph isomorphism if furthermore for all pairs v E G. if (π(w), E En then {u, v) Eg. With counting, we denote the task of counting such maps from a pattern P.
{w E VG {u, w) Ec}. We say
We denote sets of graphs by G. Moreover, given a graph G and nodes belong to the same orbit if 3x E Aut(G) such that T(u) v, and denote it with (G, u) ~ (G.v). We denote the set of orbits on set of graphs g with Vg = {(G, u) G E 9, E Vol/z. Given two nodes u, v E Va, we define with da(u, v) their shortest-path distance in G. A tree is graph with no cycles. We denote with T, the tree rooted in E VT, and define recursively children(r) = (r) and if g E children(p) then children(g) = N(4)) {p}. We define the height of the tree as maXpEV, dr (r,pp) and the truncated tree Tş as the subgraph of T, induced by the nodes p such that dr(r,p) p) S l. An egonet EGO (G) of node u E Va is defined as the induced subgraph of G on {2 E VG do(u, v) I k), with u marked with dedicated "root" label.
E VG. we say that they
The Leisne algorithm The color refinement algorithm, also known as 1- Weisfeiler-Leman (denoted as WL), is a heuristic algorithm for the graph isomorphism problem. Let (G, v) = Lo(v)= E N be the initial color of node v E Vg. Then the algorithm updates vertex colors as WL'(G, = HASH WWI"-((G,, v), | (WLL'I(G, w) w ( E N, with HASH an injective map, at iteration >> Two graphs are deemed ε-hop WL-isomorphic, denoted as G =wL, H, if { WG'(G,v) v E VG B (WL (H, (H,u): VE Vn B. and WL-isomorphic if it holds for f = [VG) denoted as G mWL H. Note that G ~ H = G ww H, but the converse is not true. We call graph G WL-amenable if HA such that G + 7/L H.
Coverings of graphs For graphs H and G, the mapping 6 VH + Vo is called a homomorphism preserves all edges and labels, i.e., if {d(u), Φ(v)} E Eg for all {u, 0} E EH and L(v) = L(((v)) for all v E Vn. A homomorphism is called locally locally injective or bijective if for every node e E VH, the mapping &. (N(w) - (((()) is injective, respectively bijective. If there exists locally bijective homomorphism from a graph H to graph G. say that H covers G. The universal cover (Angluin 1980) of G given a node u E VG is a (possibly infinite) tree, denoted (G),, that covers any graph which covers G. It holds that (G) (H) if and only if WL (G, u) WL (H, v) (Krebs & Verbitsky 2015). An illustration can be found in Figure |
Graph neural networks Message passing graph neural networks (GNNs), given a graph G, iter- atively produce for each node VG. at each level é I,..., L. the embeddings h E gd by taking into account messages coming from its neighbors (u). More formally, the embedding of node e is updated as Mr. = Jupa (K--1, Sage. ( u E N (v)))) B)) where Sagg and fupd are the aggregate and the update operations, respectively. The first layer of the GNN is fed with the initial node embeddings h.. c.g. one-hot encodings of the node labels. Finally. one can get a graph-level readout && by aggregating the output node embeddings via a function fout. In Xu et al. 2018)) was shown that there exist injective functions fagg. Supd and fout yielding GNNS that are provably as expressive as color refinement. We denote as GNN metric node-level functions formed by such a model with é message passing layers. Moreover, let GNN, (G + 1(g) be the class of parametric graph-level functions.
{(G, v) hτ) the class of para-
3

---

Published as a conference paper at ICLR 2025
G2
(.()))
Ug(Gs)
ULiG))
Figure/ 1: Three graphs and their universal covers rooted in node Since G1 is tree, its universal cover is G1 itself. The graphs G2 and G3 have isomorphic (infinite) universal covers. In fact, G3 is covering of G2-
UNIVERSALITY ON WL-DISTINGUISHABLE GRAPHS
The classical negative result of Chen et al. (2020 Theorem 3.3) based on pairs of WL- indistinguishable graphs such that, for pattern P. one contains it induced subgraph while the other one does not. This result, however, requires that the set of graphs at hand features specific WL-indistinguishable graphs, scenario that is unrealistic to happen in practice (e.g., see Table 2
To overcome this limitation, we restrict to studying the ability of GNNs to solve the subgraph count- ing tasks (for fixed pattern graph P) on specific problem (Even et al.) 1984). In fact, if the graphs at hand can all be distinguished by WL., we have the following positive result, which follows directly from Morris al. (2023a).
of graphs G, phrasing the task promise
Proposition 1. Let g be set of graphs such that VG1, G2 E G. G1 SWL G2 and [VG| n, VG G. Let G + R. be any function. Then, there exists a function class GNNz realized by a GNN model such that GNN
In particular, if the function f is the (possibly induced) subgraph counting function. GNNs count subgraphs on G. In fact, if the set is composed of WL-amenable graphs, the proposition always holds. Therefore, for several classes of graphs, such trees and forests, which are known to be amenable (Arvind et al.] (017). as well as random graphs, which are known to be amenable with high probability (Babai et al.)
| 1980), GNNs are indeed able count subgraphs. This result, although it is the first step beyond the worst-case analysis Chen et al. (2020), has several limitations.
First, the proof of universality of GNNs on WL-distinguishable graphs relies on model with an impractical number of layers, that is able to distinguish all graphs and remember by heart the value of the function for each graph. Therefore, the size of the MLP after the graph-level pooling of the node embeddings must be (at least) linear in [ In particular, |G] can in general grow exponentially with the maximum graph size n. Thus, the results hold only for sets of bounded-size graphs.
Secondly, and relatedly to the first problem, the model used in the proof of the proposition has high sample complexity. Informally speaking, the sample complexity of model class is the number of training samples needed for the model to generalize well to unseen data, and is usually proportional to the number of parameters in the model. For real-valued function classes, one can characterize their sample complexity via the aseudo-dimension (Anthony & Bartlett 1999] Mohri et. 2018). as lower recuudodimmession implies lower sample complexity. See Section A.2 for formal definitions. Indeed, this model has pseudo-dimension Pdim(GNN, 2023ab), implying that the model is in general incapable of generalizing to unseen data.
[ (see Lemma and Morris et al.
Therefore, while such model count subgraphs the training set, it's hard argue that it is able to learn to count subgraphs. In the next sections, we address this issue.
4 UNIVERSALITY FOR LOCAL FUNCTIONS
The loose results of the previous section are partly due to the fact that treat subgraph counting as an arbitrarily complex function. In fact, we can exploit the fact that subgraph counting depends only local substructures around each node.
4

---

Published as a conference paper at ICLR 2025
Oogh
Figure 2: The set of graphs the left is not (2, 1) i-ideentifi,bl, while the one the right is.
Definition 1. We define a function f : G - R to be node-decomposable into g if it can be written as f(G) = =ueeve g(G, u), for some function g Vg - R. Moreover, 9 is said to be k-local if & u(G,,
g(G,, v) implies F.GO (G1) # FGO* With some abuse of notation, we say that
a function f that is dece-secoepe into k-local functions is also k-local.
Subgraph counting and induced subgraph counting, i.e., counting the number of (induced) subgraph isomorphisms é from P to G. are indeed node-decomposable into rooted (induced) subgraph count- ing, which only counts, for node u E Vg. the number of (induced) subgraph isomorphisms such that <(p) u for some fixed exists a node p E Vp such that eV de(p, q) S k. ie.. the pattern has radius at most k, then these functions are k-local. Indeed, if is (induced) subgraph isomorphism from P to subgraph of G' such that <p)) = u, we have that ((g) E VEGOO(G)) Vq E Vp.
Vp (Lemma 2. Moreover, if P is the pattern at hand and there
This gives hope for GNN model that relies only on local structures around nodes to correctly solve the subgraph counting tasks, thus having number of parameters independent of n, the maximum graph size. Nonetheless, the following impossibility result shows that message passing GNNs are not able to represent all functions functions are all distinguishable by WI.. Indeed, if two non-isomorphic graphs have isomorphic universal covers, such as G2 and G3 in Figure [ then there exist nodes that are not distinguishable by a GNN. In fact, GNNs are unable to perform rooted subgraph counting on these graphs.
node orbits, even when the graphs of the domain of such
Theorem 1. There exists set of graphs G such that VG G2 E G, GL XWL. G2 and a function f: Va + R for which there exists no function class GNNpode realized by GNN model such that f E GNNaode, VL.
In fact, having no two graphs that have isomorphic universal covers is not only necessary condition for GNNs to represent any function on node orbits, but also sufficient one (Krebs & Verbitsky 2015). Nonetheless, the model might require a number of parameters that is exponential in the maximum graph size n to distinguish all node orbits. In the next section, we discuss finer grained sufficient condition for node orbits to be distinguished by GNN model with number of layers and number of parameters independent of n, and show that it allows these models to learn sample efficiently the subgraph counting tasks.
4.1 FINE-GRAINED DISTINGUISHABILLTY OF NODES
Since the subgraph counting tasks are kllocal, we do not need GNNs to be able distinguish any two node orbits, but rather to distinguish ego-nets of radius k. In general, one might need é > k message passing layers to so. Then, we can characterize the functions that can be realized by a GNN with layers via the notion of (e, ki)-identiiiaaiiitty.
Definition 2. Let G be a set of graphs. We say that Vo is (L, -.de-idieiie if u), (G2, v) (G2) implies that EGO,, say that G is (e, k)-identifiable.
Vg. (M( U
EGO,, (G2). Vg (e, k))identtifable, we also
Figure gives visual representation of set of graphs that is not (2, 1) -ddenttiifia,,, two non- isomorphic ego-nets of radius I have the same truncated universal covers of depth 2, and thus the same WL color. It also depicts a set of graphs that is (2, -)ideentifiable Interestingly, both sets are (3, -iddenttieeabe. Indeed, as experimentally shown in Section 6 graph sets that are not (E, k)- identifiable are rare in practice. We define Ni..e = ((U : (u, G) E Vo)/=/, the number of truncated universal covers in G. We then have the following results.
5

---

Published as a conference paper at ICLR 2025
Let G be (e, iideeiiiieeee set of graphs. Consider any k-local function f Vg - R. Then, there exists a function class GNNaode realized by GNN model with Oniig E) parameters and E layers such that f E G
Theorem 2.
Corollary 1. Let G be a (f, -ddentttie set of graphs. Let GNN e be a function class realized by GNN model with zum-aggregattnn fout ( hh u E Vall)= = Enevo hyg Then GNN, can perform both subgraph counting and induced subgraph counting of patterns of radius at most k.
Notably, the GNN model that realizes Corollary 1 has number of parameters that is independent of the maximum graph size n, depending only on E and TiS.e, and has a simple readout function. This allows not only to count arbitrary (small) subgraphs on sets of graphs with unrestricted maximum graph size, but also to learn such tasks sample efficiently, i.c., with fewer training samples.
Theorem 3. The function class GNN, of Cor. | has pseudo-dimension Pdlm(GNN, S 7/ + 1.
As implied by the previous theorem, the sample complexity of the simple model that realizes Corol- lary 1 can be bounded based solely the number of local structures around nodes, and indepen- dently on global properties of the graphs.
5 ALGORITHMICALLY--LIOOO
GNNS FOR TREE PATTERNS
The positive results in previous sections solve subgraph counting by recognizing entire graphs or ego-nets around nodes. This approach could solve tasks beyond subgraph counting, potentially pro- ducing unnecessarily large models. We now explore the ability of GNNs to simulate combinatorial algorithms for subgraph counting-related related tasks, as it has been noted in the literature that GNNs align well with dynamic programming (DP) algorithms (Xu et al. 2020: Nerem et al.) (025). We develop novel algorithms solving the (non-induced) subgraph isomorphism problem on restricted pattern and target graph classes, We demonstrate GNNs can efficiently simulate these algorithms, situating the resulting models within the algorithmic alignment framework (Xu al., 2020).
Our algorithms are inspired by the color coding algorithm (Alon et al. 1995 2008), which finds subgraph isomorphisms & from the pattern tree T to the target graph G such that c((()) of c(o(g)), Vp * q E Vr, where c(u) represents a color assigned to node u. Enforcing that the images of the pattern graph's 's nodes have different colors ensures injectivity. In the original algo- rithm, this condition is enforced by assigning random colors to the nodes of G, and repeating the procedure multiple times to boost the success probability. This assignment of random colors is how- ever impossible to simulate with message passing. Therefore, we will color the target nodes based on WL colors, which can be obtained with message passing layers. This however requires to modify the color coding algorithm to relax the condition the target graphs' colors, it is unrealistic to assume that any subgraph in G matching the pattern has all nodes belonging to different WL. classes.
5.1 A DYNAMIC PROGRAM FOR COLORFUL SUBTREE ISOMORPHISM
We tackle the subgraph isomorphism problem from tree patterns. Say that the tree pattern at hand is T, rooted in and with nodes endowed with labels L : Vr + Σ. We denote with Tp the subtree of T, rooted in p Vr, i.c. the subgraph induced by the descendants of p. The nodes of the target graph G are endowed with labels L VG + Σ and colors c VG + Ω such that L(u) + [(u) = c(u) # c(v).
Our dynamic program TREE-COLSI determines if a subgraph isomorphism ó from T₂ to G exists, where <(p) u, for nodes p E Vr and u E Vg. For leaf p. we check if has the same label. For internal with matching label to u, we build & by mapping p to u and its children to distinct neighbors of u, using inductively gathered information from Mu).. Indeed, there exist subgraph isomorphisms 6g from all the subtrees Tg. for E children(p), mapping each q to distinct neighbors of u, one can create a homomorphism from TT to G by mapping p to u and the nodes in the Ty 's to their images in Φg-
High-level deseription:
However, the resulting map could be not injective. Indeed, it could happen, e.g, that in the maps &q &gz child of 91 and a child of q2 are mapped to the same target graph's 's node. To avoid this, for each discovered map o, from T,, to with (g) = v, we store a colorset C,2, with the colors of the images of the descendants of q in set Co.g- Then, when we create the map such that p(p) by
6

---

Published as a conference paper at ICLR 2025
G
P:
Figure 3: A graph and a tree pattern P. The copies of on the right have colors (right half of the nodes) obtained from one WL iteration. The subgraph isomorphism from P to the red- pod-highlighted subgraph of G is not quite-colorful, while the one the green heen--igglighted subgraph of G is.
merging the maps Oy from all the nodes q children(p)) to distinct neighbors of u, we require that the images of any two pattern graph's nodes that could be mapped to the same target graph's node have different colors. This will allow to obtain injectivity.
Formal description: Let h be the height of the tree T, and Th {r]. Let T {q children(p) E Th 1....,h. h. Clearly, To consists of only leaves of the tree. The dy- namic program proceeds layers, processing at the same time all the pattern graph's nodes in 7 Therefore, the output of TREE-COL.SL, E) will be dictionary mapping nodes p E T to sets Cu.p. particular, for nodes u E Vg, p E Vr, Cu.p set of colorsets C 2 We have that Cs Cu.p. then there exists subgraph isomorphism from I, to G mapping p to
Algorithm 1: TREE TREE-COLS COLSI,
Algorithm 2: MERGE( (C))...,CC)
let Cu.e be empty dictionary i 0
flag (c(u) C., Vi)
flag flag and (c(et) & C, Vi j)
for u ((u) do
flag flag and (C; nC, = Vi + j)
Cv,e-1 = TREE-COLSI,(M,E--
if flag = false: return
Cu. = Co.e-llg 4g children(p), vp ET for E T" do do
let C. C. U (c(w)))
let = U, return
if children(p) == 0
if L()) * L(): [p. else: C..e(p) (0)
The dynamic program TREE-COLSI, ap- plied with colors c, is described in Algo- rithm [ takes as input a target graph node u and level nary mapping from pattern graph nodes to sets of colorsets. Lines 2-5 gather infor- mation from the neighbors of u by recur- sively calling the procedure on the nodes in T if > O. The for-loop of line 6 iterates over the nodes p T to compute the sets Cu.p. Lines 7-10 handle the case when p is leaf. For an internal node p, L(p) L(u), the for-loop on line 13 tries all possible assignments the nodes in children(p) to the nodes in Au) The loop on line 16 tries, for each such assignment, all the combinations of colorsets belonging the sets C.,, .............. C.. For one such sequence CI...., Cs. the algorithm checks with MERGE if the recursivel--ohaiied sub-maps can be merged to create map mapping p u, by checking injectivity via the colors of the image of the map. A dummy value is used to signal that the map cannot be created. If the map can be created, the algorithm builds a colorset C(e,,....aa .eh......)...........))) associated with the map, which inserted in Cu.p-- One would call the algorithm with TREE-COLSI, h), with the height of the tree pattern, and would obtain the dictionary Cu, One can then access Cu.r, with r the root of the tree, as C [r]. An example of the execution of the algorithm can be found in Section A.4
10
continue
if L(u)) * L(p): set (p. 0 and continue
12
let Cu.p 0 and (gı,..., 95) children(p)
returns dictio-
13
for seq. of distinct nodes (#i...., U5) from (()) do if 3i: :r,.a = 0: continue let (Cris
14
15
I,.... IC Cu..q
for seq. of colorsets (Co Osy do MERGE( (Crrsir...., Cugis)
17
18
ifC #C
Cr,p Cu.p U {C}
20
(p.
Cu.
return Cu.e
Due to the "non-allowed colors" strategy for enforcing injectivity, the dynamic program will not detect the subgraph isomorphisms from T to G where some specific pairs of pattern graph nodes are mapped to target graph nodes with the same color. We now formally characterize the family of maps that can be recognized.

---

Published as a conference paper at ICLR 2025
Definition 3. Let T, be tree, G be a graph whose nodes are endowed with colors e : VG Ω and Φ : Vr, - VG a map. We say 6 is quite-colorful (w.E. c) if (i) Vp E Vr,, Vq E children(p) and vt E children(q) it holds that c(o(p)) # c(o(t)), and (ii) vp,q E VT, such that dr, (p. 9) it holds that c(p(p)) # c()()))-
Theorem 4. Let Tr be a tree of height h, G be a graph whose nodes are endowed with colors e: Va S2 Then, TREE-COLSI [))r) # 0 if and only if there is a quite-colorfid subgraph isomorphism & from T, to G such that ((r) = u.
A visual representation for a subgraph isomrrphism map that is not quite-colorful and for one that is quite-colorful can be found in Figure 3 A simple sufficient (but not necessary) condition to ensure that the algorithm solves subgraph isomorphism is that labels of the pattern graph itself respect the conditions for quite-colorfulness, i.e., Vp E VI, Vg E children(p) and Vt E children(g) it holds that [((x)) * [(((()), and Vy, q E Vr, such that dr, (p, q) 2 3 it holds that L(ø(p)) & L(((a)). as the map will be guaranteed to be parent-colorful. We call these quite-colorful patterns.
The algorithm is designed, rather than to minimize the computational complexity (Section A.3) to align with message passing, as mapping p to u only requires information from u's neighbors. This allows GNNs to simulate the algorithm, as we show in the next section.
5.2 GRAPH NEURAL NETWORKS CAN SIMULATE TREE-COLSI
We show that a GNN model can simulate the execution of TREE-COLSI,, with the colors e of the target nodes being WL colors, i.e., such that c(u) c(t) iff (G) ~ (G) Note that such WL colors can be obtained by message passing on both labeled and unlabeled graphs.
The structure of the dynamic program is, by design, aligned with the message passing framework used by GNNs. Indeed, in the dynamic program, the computation of a set Cu,e depends uniquely on the sets C,,e-1 e-1 for all E M(u), as well the colors e(v) for v E -N(u) U {u}. Indeed, while also the labels [uu) are used, these are uniquely identified by the colors e(u) by construction.
Therefore, one can encode the information (Ca,8-1, in the node embedding h and com- municate this information to the neighbors of v. Special care needs to be taken in order for Sagg. (f : v E (N) B) to uniquely represent the multiset ((C)))),,((v)) : o E N())): B- The function mapping (Cu,e-1, cu)).. ((()) o e N(u)] } (()) can then be realized by a MLP in the fupd function, which therefore only simulates lines 6-21 of the dynamic program. Because of this, the GNN algorithmically aligns (Xu et al. 2020 Definition 3.4) with the execution of the dynamic program, which can lead to better generalization (Xu et al.] 2020 Theorem 3.6). Moreover, the MLP will have a number of parameters that depends on the maximum number of distinct elements (Cu,e-1, c(u)), & ((C)) v E N(u) over all u E Vi and l = I,..., h, which we call G. Then, we have that GNN can efficiently simulate the DP, and therefore we can apply to GNNs the results of Theorem
Theorem 5. Let G be a set of gruphs of bounded degree, T, be tree of height h. Let [(G) = if 3u E VG TREE-COLSI (u,h)) [r] + @ and O otherwise. Then, there exists a function class (O
GNN realized by a GNN model with I + layers and O Ons.s S.TT h) parameters such that f E GNN
We prove in Lemma 5 that the quantity SI,T,G, which plays crucial role in the complexity of the model, can be upper bounded by mith. recovering a dependency similar to the result of Theorem We show there that the quantity can also be bounded based on the maximum degree of the graph A, the size of the pattern k and the number of used colors Vlg. as 01 (alasl2((++))))) 2(A+1)n../(-1I) However, when in practice there are few distinct elements (Cu,e-1, c(u)), El (C.,,e1,, c(v)) : v
(u B. e.g. if the subtrees of appear rarely in the data or appear on target nodes with few distinct colors, we get better model size bounds, which then leads better sample complexity.
Comparison with previous work The result of Theorem 4 yieldss a generalization of Chen et al. 2000 Theorem 3.5), as maps from stars are always quite-colortee Theorem 4.5) proves that GNNs can count subgraphs (on general graphs) if and only if the spasm of the pattern at hand is composed of only trees. Indeed, the spasm of a quite-colorful tree is composed of only trees. On the other hand, if tree pattern has two nodes distance at least 3 with the same
Moreover, Zhang et al. (2024)
8

---

G/owa, Published as a conference paper at ICLR 2025
Table 2: Number g of WL isomorphism classes after & iterations and number |g/=| of actual isomorphism classes common molecular datasets. Ratio between the two in brackets.
Dateset
60/cl
f
f 2
f=3
F'
Mutagenicity. Kensing
3634
MCK-7 Kershhy 2016
22552
27538
ZINC (Gomey fromiarrei et al 2M18
11988 rere
11994 cer)
11994 (1:00
11994 11:1391
11994 (1:39))
11994
ogbg aithit [Hu al. 2021
WD eral
2018
38765
40942
41082
41102
41122
41122
oghg molemmmlpphhheueeee
202
Waree
2018
375291
426220
429584
429730
429802
429802
Peptides-func [Dw]vedr
Stnglt
14854 (0.03))
PCQM Contact [LIWiveur o.
2012
428356 yn a3R)
521598 0900
522786 (0.
522836 (1.000)
522837
(1.029)
522837
color, and thus is not quite-colorful, it will have cyclic graph in its spasm, and cannot therefore be counted by a GNN on general target graphs. Our Theorem[4]hern therefore helps understand the results of Zhang al. (2024 Theorem 4.5), by providing upper bounds on the number of layers, the parameter count and the sample complexity of a GNN that is indeed able to count such substructures.
Our results however, go beyond this. Indeed, even when the pattern hand is not colte-colorful (e.g., for an unlabeled pattern), the algorithm can exploit the colors of the target graph to elude the worst- case analysis of Zhang et al. 2024. Theorem 4.5). Indeed, given that the target graphs have enough asymmetries, the colors с obtained by iterations of color refinement (or GNN message passing layers) are enough make the subgraph isomorphism maps quite-colorful. This, as we observe in Section 6 indeed holds in practice on several real-world datasets. Note that, on adversarial examples like regular graphs, colof-colo cannot be obtained for any value of
5.3 EXTENSIONS
We obtained a message-passing from tree patterns. However, the quite-colorful condition can be too restrictive in some scenar- ios. A similar problem the locally injective homomorphism problem from tree patterns. this relaxation of the subgraph isomorphism problem, the map is required to be injective only the neighborhood of each pattern graph's 's node. In Section B.I we propose TREE- TREE-COLLIHE a slightly modified algorithm that solves the locally injective homomorphism problem under weaker condi- tion with respect to quite-colorfulnee
dynamic program for quite-colorful subgraph isomorphism
The algorithms described in the previous sections, the original algorithms (Alon et al. 1995), can only deal with tree patterns. This is necessary due to the fact that the maps built on different subtrees can be merged recursively without conflicts. In fact, in Section B.2 we discuss how extend the approach, which can still be simulated by GNN, to cyclic patterns.
Moreover, our algorithms described in the decision problem variant. As argued in follow-up to the original color-coding algorithm Alon et al. (2008), one can modify the dynamic program, and the associated GNNs, count maps. We describe how to do in Section
EXPERIMENTAL EVALUATION
6.1 THE CONDITIONS FOR SUBGRAPH COUNTING HOLD IN PRACTICE
We study whether the sufficient conditions for subgraph counting that we have identified hold in practice. As in [ we focus on molecular graphs, where subgraph counting has been the focus of extensive research, due to the relevance of subgraphs corresponding to functional groups. Table reports the number [g/=wI., of WI. isomorphism classes after = 2,2,3, 4, Do iterations. If one compares this figure to the number | / of actual isomorphism classes, it is immediate see that the number of WL-innistinguuisabbl graphs is negligible in practice, as observed in Zopf (2022).
Moreover, Table 3 reports the fraction of the nodes in the dataset that are (e, -ididntti,,,,l,, namely such that their universal cover of depth uniquely identifies their ego-net of radius k. We also report the fraction of graphs for which all nodes are (E, -idiinetti... We can observe that already for = lo + 2, more than 97% of the ego-nets centered around nodes can be identified by the WL color of the node after l iterations. This result justifies the real-world applicability of Theorem 2

---

Published as a conference paper at ICLR 2025
Table Fraction of nodes in the dataset that are (f. kjiieentifiable brackets, fraction of graphs in the dataset for which all nodes are (E, iidentiiiie.
Datasct
1
A
A=
A ==3
2
3
3
F-
F-D
1-3
Mutagenicity
0,880
0.978
0.997
0.999
0.647
0.945
0.992
0.997
0.663
0.952
0.994
0,997
MCF-7
0.389
0.951
0.996
0.999
0.323
0.913
0.995
0.999
0.615
0.953
0.996
0.999
ZINC
(6.10)
10.0000
00.31
06 06390
00.291
00.000
0.900
ogbg-molhiv
0.734
0.961
0.998
1,000
0.477
0.952
0.996
0,999
0.739
0.968
0.996
0,999
oghg-molpeha
0.750
0.959
0.992
0.999
0.504
0.933
0.999
1.998
0.674
0.948
0.988
0.998
Peptides fune
0.999
16:000
37
1807
1600
01 23331
PCQM-Com
0.699
0.943
0.991
0.997
0.351
0.854
0.973
0.90 995
0.39
8,848
0.975
0.998
MORZ
332
388
6966
822
Figure 4: Ratio of the number IQ] of subgraph isomorphisms that are quite-colorful to the total number [S] of subgraph isomorphisms, reported for increasing numbers of WL iterations I and for several (non quite-colorful) patterns.
Finally, Figure reports the proportion of subgraph isomorphisms that are quite-colorful, for in- creasing numbers of WL iterations and for several (non quite-colorful) patterns. Full results are reported Section [D.3] The results show that for real-world datasets, such as MCF-7 and ZINC, node-colored
quite-colorful, already when target graphs using only / iterations of color refinement. In general, we notice that, for the vast majority of the patterns, most subgraph isomorphism maps indeed quite-colorful already for I = 2. There specific patterns for which not all maps are quite-colorful, no matter the choice Understanding the mechanisms for which these patterns can be counted, least approximately, remains open question for future work.
nearly all subgraph isomorphisms
6.2 ADDITIONAL EXPERIMENT IMENTALL RESULTS
In Section D we report additional experimental results. particular, we report an extended version of [aTable[[ with several more tree and cyclic patterns, showing that indeed GNNs can count quite well several substructures. Moreover, we validate the ability GNNs to count quite-colorful patterns on challenging synthetic datasets, further proving the results of Section
7 DISCUSSION AND CONCLUSIONS
Our work provides theoretically-grout passing graph neural networks (GNNs) in subgraph counting tasks, bridging the gap between theo- retical limitations and practical performance. Indeed, by moving beyond worst-case scenarios, we provide a more nuanced analysis of the subgraph-countee abilities of GNNs.
explanation for the observed effectiveness of message
In particular, we derived sufficient conditions under which GNNs can efficiently realize functions on graphs that depend only on local substructures around nodes, such as subgraph counting, and we have shown that they often hold in practice. Moreover, we developed novel algorithms for subtree isomorphism and demonstrated that GNNs can efficiently simulate them, providing new perspective the computational capabilities of GNNs in relation to classical graph algorithms.
Finally, we show that, in practice, more expressivity in GNN architectures is almost never needed, as in many graph datasets there are pairs of non-isomorphic graphs that cannot be distinguished by GNNs. Therefore, having ruled out expressivity, an interesting research avenue is to investigate the true reasons (e.g. lower sample complexity, more in the optimization) why several GNN architectures designed to go beyond the limitations the 1-WL test (Morris et al. 2019) often show better performance than their simpler counterparts in several prediction tasks.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Ralph Abboud, Ismail ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proceedings of the Joint Conference on Artificial Intelligence (IJCAI), 2021.
Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, July 1995.
ISSN 0004-5411.
Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and S Cenk Sahinalp. Biomolecular network motif counting and discovery by color coding. Bioinformaties, 24(13): 1241-9, July 2008.
Dana Angluin. Local and global properties in networks of processors. In Proceedings of the ACM Symposium on Theory of Computing (STOC), STOC '80, pp. 82-93, 1980.
Martin Anthony and Peter Bartlett. Neural network learning: Theoretical foundations. Cambridge University Press, 1999.
Vikraman Arvind and Venkatesh Raman. Approximation algorithms for some parameterized count- ing problems. In ISAAC, pp. 453-464. Springer, 2002.
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, and Oleg Verbitsky, Graph isomorphism, color refinement, and compactness. Computational Complexity, 26:627 685, 2017.
László Babai, Paul Erdo"s s, and Stanley M. Selkow. Random graph isomorphism. SIAM Journal on Computing, 9()::22-6335, 1980.
Maya Bechler-Speicher, Moshe Eliasof, Aisola-Bibiane Schönlieb, Ran Bachhahhc and Amir Globerson. On the utilization of unique node identifiers graph neural networks. arXiv preprint arXiv:2411.02271, 2024.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation net- works. In International Conference on Learning Representations (ICLR), 2021.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6557666566 2022.
Jin-Yi Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-411 1992.
Quentin Cappart, Didier Chételat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research (JMLR), 24(130):1-61, 2023.
Vincenzo Carletti, Pasquale Foggia, Alessia Saggese, and Mario Vento. Challenging the time com- plexity of exact subgraph isomorphism for huge and dense graphs with vf3. IEEE transactions on pattern analysis and machine intelligence, 40(4):804-8) -8800088888111081 2017.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pp. 10383-10395, 2020.
Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph repre- sentations. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
George Dasoulas. Ludovie Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation. In Proceedings of the Joint Conference on Artificial Intelli- gence (ICCAI), 2020.
Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
11

---

Published as a conference paper at ICLR 2025
Shimon Even, Alan L. Selman, and Yacov Yacobi. The complexity of promise problems with applications to public-key cryptography. Information and Control, 61(2):159-173, 1984. ISSN 0019-9958.
Billy Joe Franks, Markus Anders, Marius Kloft, and Pascal Schweitzer. systematic approach to random data augmentation graph neural networks. arXiv preprint arXiv:21 2021.
Fabrizio Frasca, Beatrice Bevilacqua, Michael Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Martin Grohe. Descriptive complexity, canonisation, and definable graph structure theory, vol-
47, Cambridge University Press, 2017.
Rafael Gómez-Bombarelli, Jennifer N. Wei, David Duvenaud, José Miguel Hernández-Lobato, Benjamín Sánchez-Lengeling Dennis Sheberla, Jorge Aguilera-Iparrauuire. Timothy D. Hirzel, Ryan P. Adams, and Alán Aspuru-Guzik. Automatic chemical design using data-driven contin- uous representation of molecules. ACS Central Science, 4(2):268-22 276, 2018.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs, 2021.
Yinan Huang, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanie Jegelka, and Pan Li. On the stability of expressive positional encodings for graph neural networks. arXiv preprint arXiv:2310.02579, 2023a.
Yinan Huang, Xingang Peng, Jianzhu Ma, and Muhan Zhang. Boosting the cycle counting power of graph neural networks with i2-GNNs. In International Conference Learning Representations (ICLR), 2023b.
Charilaos Kanatsoulis and Alejandro Ribeiro. Counting graph substructures with graph neural net- works. In International Conference on Learning Representations (ICLR), 2024.
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Bench- mark data sets for graph kernels, 2016. http:://graphkereelll www.:aassss.....t..oeeeeeo.eooee tu-tuuuudrrrutsr de
es
Andreas Krebs and Oleg Verbitsky. Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth. In ACM/EEEE Symposium Logic in Computer Science, pp. 689-700, 2015.
Michihiro Kuramochi and George Karypis. An efficient algorithm for discovering frequent sub- graphs. IEEE transactions on Knowledge and Data Engineering, 16(9):1038-10511 2004.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances Neural Information Processing Systems (NeurIPS), volume 32, 2019.
Ciaran McCreesh, Patrick Prosser, and James Trimble. The glasgow subgraph solver: using con- straint programming to tackle hard subgraph isomorphism problem variants. In International Conference on Graph Transformation, pp. 316-324. Springer, 2020.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
Christopher Morris, Gauray Rattan, Sandra Kiefer, and Siamak Ravanbakhsh. Speqnets: Sparsity- aware ceaimnutatioo-eqivvriiiin graph networks. In International Conference on Machine Learning (ICML). 2022.
Christopher Morris, Floris Geerts, Jan Tönshoff, and Martin Grohe. WL meet VC. In International Conference Machine Learning (ICML), 2023a.
12

---

Published as a conference paper at ICLR 2025
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. The Journal of Machine Learning Research, 24(1):1565--1522, 2023b.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. International Conference on Machine Learning (ICML), pp. 4663- 4673. PMLR. 2019.
Robert R. Nerem, Samantha Chen, Sanjoy Dasgupta, and Yusu Wang. Graph neural networks ex- trapolate out-of-distribution for shortest paths, 2025,
Siegfried Nijssen and Joost N Kok. The gaston tool for frequent subgraph mining. Electronic Notes in Theoretical Computer Science, 127(1):77-87, 2005.
Raffaele Paolino, Sohir Maskey, Pascal Welke, and Gitta Kutyniok. Weisfeiler and leman go loopy:
A new hierarchy for graph representational learning. In Advances Neural Information Process- ing Systems (NeurIPS), 2024.
Pál András Papp and Roger Wattenhofer. A theoretical comparison of graph neural network exten- sions. International Conference on Machine Learning (ICML), 2022.
Paolo Pellizzoni, Till Schulz, Dexiong Chen, and Karsten Borgwardt. On the expressivity and sam- ple complexity of node-individualized graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
Chendi Qian, Gaurav Rattan, Floris Geerts, Mathias Niepert, and Christopher Morris. Ordered sub- graph aggregation networks. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Ryoma Sato. A survey on the expressive power of graph neural networks arXiv preprint arXiv:2003.04078, 2020.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the SIAM International Conference Data Mining (SDM), pp. 333-341. SIAM, 2021.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
Sandeep Singh, Kumardeep Chaudhary, Sandeep Kumar Dhanda, Sherry Bhalla, Salman Sadullah Usmani, Ankur Gautam, Abhishek Tuknait, Piyush Agrawal, Deepika Mathur, and Gajendra P Raghava. SATPdb: database of structurally annotated therapeutic peptides. Nucleic Acids Res, 44(D1):D1119-26, November 2015.
Behrooz Tahmasebi, Derek Lim, and Stefanie Jegelka. The power of recursion in graph neural networks for counting substructures. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2023.
Qing Wang, Dillon Ze Chen, Asiri Wijesinghe, Shouheng Li, and Muhammad Farhan. N-WL: A new hierarchy of expressivity for graph neural networks. In International Conference on Learning Representations (ICLR), 2023.
Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. Nauchno-Teche Technicheskaya Informatsia, 1968.
Zhenqin WU, Bharath Ramsundar, Evan N. Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S. Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learn- ing. Chem. Sci., 9:513-530, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations (ICLR), 2018.
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? In International Conference on Learning Representa- fions (ICLR), 2020.
13

---

Published as a conference paper at ICLR 2025
Bohang Zhang, Guhao Feng, Yiheng Du, Di He, and Liwei Wang. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests. International Conference Machine Learning (ICML), 2023.
Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang. Beyond weisfeiler- lehman: A quantitative framework for gon expressiveness. In International Conference on Learn- ing Representations (ICLR), 2024.
Markus Zopf. 1-wl expressiveness is (almost) all you need. In International Joint Conference on Neural Networks (IJCNN), 2022.
14

---

Published as a conference paper at ICLR 2025
A ADDITIONAL DETAILS
A.1 EXPRESSIVE GRAPH NEURAL NETWORKS
An example of functions farez fund and fout that leads to models that are provably expressive as as concatenation,
color refinement (Morris et al. 2019), denoting ||
hy mlp 1
Σ
ki-)) Rdd
h mlp Σ Σ ho. ER.
(E)((o)
vEVe
A.2 SAMPLE COMPLEXITY AND PSEUDO-DIMENSII
Let ((f(z)) y) be a loss. Learning theory (Mohri et al. 2018 Shalev-Swwarzz & Ben- Ben-David 2014) is concerned with the task to bound the difference between the true risk R(f) and the empiniaal risk R(f):
m Re( = (x.g)) ((( and Ro.(ff) = Σ (f(x))))))
where D { v1) ~ D represents a training dataset of size m sampled i.id. from the data generating distribution D.
In particular, given a class of functions F, we say that it has the uniform convergence property (Shalev-Shwartz & Ben-Davis 2014) if there exists function my(e, 6) such that, for every e, [0, and every distribution D, drawing a dataset D of m 2 mz(e, 8) i.dd samples from yields that, with probability at least 1 - 8 over the choices of the samples, sup (RD,e(f) Re(f) S The function m=r(e, 6) is called the sample complexity of the function class.
In general, model class that has low sample complexity needs fewer training samples in order to generalize to unseen data. For models outputting real values, their sample complexity can be characterizes via the pscudo dimension (Anthony & Bartleti 1999, Mohri al. 2018).
Definition 4. Let X be a set and C f X > R class of real-valued functions. say that FF pseudo-shatters a set S (21...., if (sign(( (xz))(((=1)))))
(ig ..1.....21............ 21s)) with witnesses (FI....,7(s)) E RISI 2|51, Then, we define the pseudo- dimension of F), denoted Pdim(X,F), the size of the largest set S that be pseudo- shattered by F. If sets of arbitrary size can be pseuto-shattered, we say Ftim(X,F)=+ta)
ff
Analogous to the VC dimension for binary classification, the pseudo-dimension provides upper bounds on the number of samples required to learn function from the class with high probability and low error. Specifically, for a given error and confidence 6, the sample complexity of for F is Ō(E- -(e=22(e (Pdim((X, + log 1)) (Mohri et al. 2018 Theorem 19.2).
A.3 COMPUTATIONAL COMPLEXITY
As discussed in Section 5.1 the algorithm TREE-COLSI is designed, rather than to minimize the computational complexity, align with message passing and to allow to detect quite-colorful maps.
The algorithm, for fixed node u and level É, considers [ pattern graph's 's nodes. For each such nodes, it tries D(AAr) sequences of nodes line 13, where A is upper bound the degree of any node in G and Ar is an upper bound to the number of children of any node in the pattern tree. A set Cu.q can contain in the worst case Q Σ Vrl (!!!)) colorsets on |St| colors. Then, for each se- quence of nodes (Vi,..., vs), the algorithm tries O(QÂT) sequences of colorsets line 14. There- fore, summing over all E VG and é E O,...,h, h, we obtain a total of O (Σ/.o, [T*]| Ar)
=
=0 (Va ()))* Ar) calls to MERGE.
In contrast, the original color coding algorithm (Alon et al, 2008 would have a complexity of 0 (FFll - Q) = O (VVol[V] AQQ).
15

---

Published as a conference paper at ICLR 2025
(01
DP
(1001-30
10 181
(4)
(1000--0000 100-0000000011
(4)
(10091- 11900--001-111 D000-
DIV
1101
DIY
11000000
In
Figure 5: A simplified example of the execution of TREE-COLSI for pattern P and graph G.
A.4 AN EXAMPLE OF THE EXECUTION OF TREE-COLSI
Figure reports a (simplified) example of the execution of TREE-COLSI for a pattern /' and target graph G. The nodes of G are endowed with labels (depicted the left half of the node) and colors (depicted on the right half of the node) obtained by one iteration of color refinement. The original graph can be seen Figure
At level O, the algorithm returns for each node VG dictionary from the three leaves of P to sets of colorsets. We report as an example four such u's. For nodes with black label, the algorithm keeps track of the colors of the images of the pattern graph's nodes (in fact, in the algorithm, these colors are maintained implicitly). For nodes u with other labels, the algorithm returns an empty set since the sub-patterns don't match.
At level 1, the algorithm returns dictionaries from the two sub-patterns height of to sets of colorsets. For example, consider the first node W1 we report (i.e., with red label and white color). Here, the sub-pattern rooted at the red-labeled node matches the red label of u1, and the colorsets received from the two neighbors of μj both allow for the construction of subgraph isomorphism map. Then, the algorithm keeps track the sets of colors of the images of the pattern graph's 's nodes for the two maps. In particular, it keeps track of set containing white and pink color, and of set containing white and purple color.
Finally, level 2, the algorithm returns dictionaries from the entire pattern P sets of colorsets. The first node иı we report (black label and green color), receives from its black-labeled neighbor empty sets. Therefore, also returns an empty set. The second node u2 we report (black label and purple color) receives from both its two neighbors some colorsets. Here, one such combination of colorsets valid, which is then returned that there exists subgraph isomorphism from the tree pattern to G rooted at 12z The third node ug we report (black label and purple color) also receives from both its two neighbors some colorsets. However, in all such combinations of colorsets, some colors collide. Therefore, it returns an empty set. Indeed, even though there is subgraph isomorphism rooted at ug. is not quite-colorful.
valid colorset. Since is the height of the tree, means
B EXTENSIONS TO THE DYNAMIC PROGRAMMING ALGORITHM
B. A DYNAMIC PROGRAM FOR COLORFUL SUBTREE ISOMORPHISM
In Section 5.1
we obtained a message- -aassagg---sinn---ae like dynamic program for quite-colorful subgraph isomorphism from tree patterns. However, the quite-colorful condition can be too restrictive in some scenarios. In this section, we tackle the locally injective homomorphism problem from tree patterns. In this relaxation of the subgraph isomorphism problem, the map from the pattern the
16

---

Published as a conference paper at ICLR 2025
target is required to be injective only on the neighborhood of each pattern graph's node. We then pro- pose TREE- CREE-C,LLIH, a slightly modified algorithm that solves the locally injective homomorphism problem under weaker condition with respect to cotte-colorfulness.
Inspired by the color coding technique, as done in Section 5.T enforce local in- jectivity by making sure that the colors of the images of specific pairs of pattern nodes are distinct. In particular, we now
Algorithm 3: PARENTMERGE PARENTMERGF((C C2))
if Ei c(u) E C₁: return return fc(r)), i 1,
require only that for each node p. the image of the parent of its parent has different color from the image of This condition is enforced by substituting the MERGE procedure of the dynamic program TREE-COL reported in Algorithm|] [ with PARENTMERGE. In particular, the dynamic program still returns, for nodes u E VG. p E Vr, set Cu.p of colorsets C E {0, 1 If there is no locally injective homomorphism from Tp to G mapping to u the set is empty. If C E Cu.p. then there exists (at least) one associated map from T, to
We now formally characterize the family of maps that can be recognized by the dynamic program.
Definition 5. Let T, be tree, G be a graph whose nodes are endowed with colors e : VG Q and Φ Vr_-- + Vg map. We say o is parent-colorful (w.r.t c) if E VT,, Aq E children(p) and VI childre((g) it holds that c(é(p)) + c(ő(1)).
Theorem 6. Let Т, be a tree of height h, G be a graph whose nodes are endowed with colors e: Va - S2. Then, TREE-COLLIH, h)]rr] + if and only if there is a parent-colorful locally injective homomorphism & from T, to G such that ((r) = u.
A simple sufficient (but not necessary) condition to ensure that the algorithm solves the locally in- jective homomorphism problem that the parent of the parent of any pattern node must have a different label from the node itself, the map will be parent-colorful. Moreover, if the discov- ered homomorphism is (globally) injective, the dynamic problem solves the subgraph isomorphism problem. A sufficient condition for this is that the cycles in the target graph are long enough.
Corollary 2. Let T, be a tree of height h, G be a graph whose nodes are endowed with colors VG + S. Let T be such that Vp VT. Vq E children(p) and Vt children(g) it holds that L(p) * L(l). Let also G be such that the minimum cycle length is at least 2h + 1. Then, (RRE-COLLLI,,(V, h)[r] + 0 if and only if there is a subgraph isomorphism from T to G such that ((r) u.
In particular, if we restrict ourselves to tree patterns with no node such that the parent of its parent has its same label, the dynamic program solves the subgraph isomorphism problem if the target graphs trees. Moreover, in many molecular graphs from organic chemistry, the minimum cycle length is 5. Therefore, on these graphs the dynamic program correctly solves the subgraph isomorphism problem for (parent-colorful) tree patterns of height at most 2.
B.2 DEALING WITH CYCLIC PATTERNS
The algorithms described in the previous sections, as the original algorithms (Alon et al. 1995), can only deal with tree patterns. This is necessary due to the fact that the maps built on different subtrees can be merged recursively without conflicts.
One can deal with cyclic patterns, although with weaker guarantees, by using as a pattern the trun- cated universal cover of the pattern. Let P be the pattern at hand and u E Vp, then one would use p' U (P) as the new pattem, with I 2 max,, d v). Then, using obtain a positive answer if P is subgraph of G. as indeed there exists a locally injective homomor- phism from (P) to for each l. However, there could false positives. For S.,S., one would need to enrich the colorsets to ensure that tree nodes p, q E Viz(() that correspond to the same node in P are enforced to have images with the same color, and that tree nodes that correspond to different nodes in P are enforced have different colors.
one would
B.3 FROM SUBGRAPH DETECTION TO COUNTING
As argued in a follow-up to the original color-coding algorithm Alon et al. (008)), modifying the dynamic program to count maps rather than solve the decision problem is relatively straightforward,
17

---

Published as a conference paper at ICLR 2025
and can be applied to all the presented versions of the algorithm. Indeed, endow colorsets with a counter ent that keeps track of the number of maps associated with the colorset. Then, when building the set Cu.p consider choice of vertices ....... Us and sequence of colorsets C1..... C with associated counters cnti,- cnt,, which each representing the number of maps from Tg to G mapping di to ee. Let then the resulting merged colorset be C # c. The number of maps from Tр to G mapping to u is then cnt = II; cut;. If C' already belongs to Cu.p with associated counter ente, we update the counter as ente ente + cut. Otherwise, we insert C' in Cu.p with ente ent. In this variant of the algorithm there would be an increase in the size of the MLP for GNN, to store the counters, to be able simulate the algorithm.
C PROOFS
C.1 SECTION
Proposition 1. Let G be set of graphs such that VG G2 G. G1 FWL G2 and [Vel S VG E G. Let f g - R be any function. Then, there exists a function class GNNe=n realized by a GNN model such that f GNN
Proof. Since VG1. G2 E GG G1 ZWL G2, by Morris et al. (2023a, Proposition 9) the GNN model can realize a one-hot encoding ha for each graph G. Then, by appending linear layer the model such that Whe S(G), we can realize J.
Lemma 1. The function class GNN; of Prop. has pseudo-dimension Pdim(G, GNN,) = G
Proof. We have Pd GNN)) < | by definition. Morcover, by Morris et al. (202aa Proposi- tion 9) and the fact that two graphs are WL-isomorphie, the GNN model can realize any binary function on g. Then, taking as witnesses a vector of -1/2, we obtain the lower bound.
C.2 SECTION
Theorem 1. There exists a set of graphs 9 such that VG1, G2 E G, G1 øWI. G2 and a function f: Vi + for which there exists no function class GNNpodo realized by GNN model such that ʃ GNNaode, Vl.
Proof. The theorem is proven by the two graphs G2, G3 in Figure 1 and f(G, u) the rooted sub- graph isomorphism function, with as pattern the triangle K3 rooted in any of its nodes. Clearly [(22, u) and J(G3, u) 0. These two graphs have isomorphic universal covers. In particular, rooting the universal covers at u E VG,, and Ve, yields U (G2 ~ (G)))). We then have that (G. u) = WL' (G3, u), by (Krebs & Verbitsky 2015). Then, the GNN cannot assign different outputs to (G2, u) and (Ga, u) (Morris et 20199 Theorem 1).
Lemma 2. Subgraph counting and induced subgraph counting are decoopeccope into rooted subgraph counting and rooted induced subgraph counting, respectively.
Proof. Let P be a graph and E Vp any node. The (induced) subgraph counting function fG) maps graph G to (&c), where &6 is the set of (induced) subgraph isomorphisms & from P to G. We let g(G, u) be the rooted subgraph counting function (resp. the rooted induced subgraph counting function), that is g u) & with &G... the set of (induced) subgraph isomorphisms é from P to G such that @(p) = u. We show that f(G) Σneve g(G, u).
We have that any ò 2a. is a (induced) subgraph isomorphism, so E &g. Conversely, if & E LG. then Φ E (GGe(t) by definition. Therefore &G = Uveva 4G.,. It then suffices to show that the sets aG are disjoint. Indeed, let á PG,,. then d(p) = Therefore, o & &G for any # u. since d(p) #
Note that alternative and equally valid definition of the (induced) subgraph counting function counts the number of (induced) subgraph isomorphisms up to automorphisms of the pattern graph. In this case, the function (G) maps graph to (V C VG exists (induced) subgraph isomorphism
18

---

Published as a conference paper at ICLR 2025
from P to G such that 6(Vp) VJJ. Note that ('(G) f(G)/Aut(P). Also this function is nude-decomposable, as f =[G)=_uvva I d'(Gu) u) with g u(),)))ugGuutttttt/ u)/Aut(P).
Theorem 2. Let G be (l, -identiiie set of graphs. Consider any k-local function f Vg R. Then, there exists function class GNNaode realized by GNN model with O parameters and & layers such that f GNN
Proof. Let hy be a one-hot encoding of node labels. Then, we apply (Morris et al. 2019 Theorem 2, Lemma 11) to graph G' composed by the disjoint union of the graphs in g. In particular, the GNN layers require the dimensionality of the node embeddings be ne,g. Therefore, after layers with O(ni.g parameters each, we have that the embeddings hr. outputted by the L-th layer are such that h iC iff (G) = (?) Moreover, h E (-1,1)maa Let UI....: : arbitrary enumeration of the truncated universal covers in G, and h h An. the corresponding embeddings.
Un be an
Let W E Rm..e with W hT. Let b R with b, - + 1. We let hy (eLL + b), then hi E I is one-hot encoding for (T) Therefore, by ap- pending linear layer we can assign any real value to (G).
If, for any two (G,,u), (G2, v) Vg. it holds that (G.) z (G2). then we have that (11) & (22) by (t, diittiidniif,,iilityyy and therefore the GNN model can assign different values to these two ego-nets. In particular, since f is k-local, we can realize f.
Finally, the number of parameters of the model is O -)).
( Corollary 1. Let G be a k) ii-inniiiiable set of graphs. Let GNN, e be a function class realized by Vall)= Enevo hy Then GNN, can perform
GNN model with aon-aggregation fou ( both subgraph counting and induced subgraph counting of patterns of radius at most k.
Proof. Both the rooted subgraph counting and rooted induced subgraph counting of patterns of radius at most k are k-local functions, and we can apply Theorem 2 Then, the sum aggregation computes the subgraph counting and induced subgraph counting functions at the graph level. O
Theorem 3. The function class GNN, of Cor. 7 has pseudo-dimensoe Pdim(GNN:) S neS + 1.
Proof. Consider function f E GNN,, and the associated function g E GNN that produces the node-level opuputs that are then aggregated via fout to produce f. We show f(G) can written as [(G) w zg. with sa Ro.s the multiplicity vector of the truncated universal covers of height f rooted at the nodes of G. In particular, let UI,..., Un.s an enumeration of the truncated universal covers. Then, the i-th entry of zg will be k iff there are k nodes u E VG such that (G) Note that æG, = -Gz if and only if Gi ZWI, G2. Therefore, we can set the i-th entry of the vector w to the output of the model gG, u) GNNpode on a node u that has rooted universal cover Ug. Then, f(G) Eneva ((G, u)
TG.
By Anthony & Bartlett 1999 Theorem 11.6), the pseudo-dimension of a linear function on Rd is d + 1. Then, by Anthony & Bartlett (1999 Corollary 11.5), we have that Pdim (GNN,) leg +1
C.3 SECTION 5.1
Lemma 3. Let G be a graph, T, be tree of height h. Let nodes VG be endowed with colors c. Let be quite-colorful subgraph isomorphism from T to G. Then Colr), + 0.
Proof. Given a node p E Vr, we call T, the subtree of T, rooted at p. We show inductively that the colorset (c(((g)) q E Vr, {p}} belongs to Caty).-
We first address the base case the dynamic program, p is leaf. For each leaf p E Vr, we have that Co(p).p = (0), since I(O(p))= I(p).
19

---

Published as a conference paper at ICLR 2025
Let now p be non-leaf. Then, there exists a sequence Ui...... Us of distinct neighbors of Φ(p) such that v = =(q)) qi E children(p) and, for each q. @ @lvr, is a quite colorful subgraph isomorphism from T. to G. We then have inductively that Cg == {c(d(w)) w E VT, \ {4)} E Cola). Vq E children(p).
Since L(o(p)) L(p), the algorithm starts creating the set Colp).p in line 12. In particular, it will try on line 13 the correct sequence of nodes (vI...., Us) (Ø(9)), ..... o(gs) )) and for that sequence the algorithm will try on line 16 the sequence of colorsets Cg..... C.s. For any two distinct gı, 92, and Vt, E Vr,, \ ( 22 E VI,, \ 192), we have that d2 (f,, 12) > 3. Since & is quite-colorful, the third flag condition is true. Morcover, dr(91,t2) 2 3, and the second flag condition is true. Finally, either dp (2) 2 3 or = parent(pparent (parent((2)) (12)), and the first flag condition is true. Therefore, all three conditions for flag are true and the algorithm inserts in Co(p).p the colorset C= Ugechildrentp) (C, U ((((())) = {c(((g)) q V1, \ {p]).
Then, we have inductively that C, Coir),rs and we have the claim.
Lemma 4. Let G be graph, T, be a tree of height h. Let nodes Ve be endowed with colors If Cu. r * O, then there exists quite-colorful subgraph isomorphism e from T G such that Φ(r)= = u.
Proof. Given a node p E VT, we call T the subtree of T, rooted at p. We show inductively that if C E Cu.p. then there exists quite-colorful subgraph isomorphism & from Tp to G such that <(p) = u and (c(o(g)) q g Vr, \ {p)} C.
We first address the base case of the dynamic program, p is leaf. For each leaf p E Vr, we have that Cu.p = [0] + 0 iff L(u) = L(p), that is p + u is a (quite-colorful) subgraph isomorphism.
Let now C E Cupp for some non-leaf p. Then, there exists sequence of distinct nodes (Vi...., 1s) from (u) such that C' was obtained by a sequence of color sets (C1...., C8), with C. E C Vi I,....6,, 6, such that all three conditions for flag are true.
Then, we have inductively that there exists an isomorphism Φ; from Ta to G such that @; : qi + 2/ and (t( t Vr, \ {4)))} = C, for each 9: E children(p). The domains of such isomorphisms are all distinct, since the sets Vr, q E children(p) are pairwise disjoint. We can therefore define a new map & Vr, + Ve as ølvr., = Φ; and & P + u. This map is a homomorphism. Indeed, each di is an homomorphism and therefore maps adjacent nodes in Vr, to adjacent nodes in Ve. Moreover, each q: E children(p) is mapped to a node E (u).
To show that Φ is subgraph isomorphism, we just need to show injectivity by showing that the co-domains H,= {Ø(w): w E Vr } of the Φ; and the set {u} are all pairwise disjoint. We show first that H, n H1 0. In particular, by flag condition (3) we have that C, = 0, and therefore 2 & {Ø(w): : w E Vr., { for each 2 E {Ø(w): : w E VT,, \.   {g.3). Moreover, c(v;) & C2 by flag condition (2), and therefore p(q.) = v, & (Ō(w): w WET VT., Mg;1}. Also by flag condition (2), c(u,) & Ct, so d(q,) = 1y #(((w) w Vr,, \ (q.). Finally, ((g)) = o * By ((q;). Thus, H = D. We now show that u & H3, Vi. First, we have by flag condition (1) that c(u) g C, Vi and therefore & {ø(w): w E Vr, (g. Moreover, u + e p(g.). Therefore, 6 is injective and is a subgraph isomorphism.
Moreover, we have (c(o(g)) q Vr, \ (p)) = ((((())( : LE Vr, \ (a)) U (c(}())) C. Finally, since the colors of the images of the nodes in T, respect the flag conditions, is quite- colorful.
Then, we have inductively that if C E Cu.r. there exist a quite-colorfie subgraph isomorphism ø from T to G such that @(r)= = u, and we have the claim.
Theorem 4. Let Tr be tree of height h G be a graph whose nodes are endowed with colors C: Va + Q. Then, TREE- TREE-COLSI,(EE []]r]] + 0 if and only if there is a quite-colorful subgraph isomorphism & from T, to G such that o(r) u.
20

---

Published as a conference paper at ICLR 2025
Proof. If there is quite-colorful subgraph isomorphism Φ from T, to G such that d(r) = then by Lemma 3 we have that Co(r).r * 0. Moreover, by Lemma 4 if Ca.r # 0, then there exists a quite-colortul subgraph isomorphism & from T, to G such that (()) = u.
C.4 SECTION
Theorem 5. Let 9 be of graphs of bounded degree, T, be tree of height h. Let f(G) if 3u E Vo TREE-COLSI h)]r] # 0 and O otherwise. Then, there exists a function class GNN realized by a GNN model with + h layers and 0 (12. I+ SI.T.g. .h) parameters such that| f E GNN1+h.
Proof. We simulate the DP algorithm with a GNN. We first use I layers to obtain colors. Then, we use h layers to simulate the recursive calls of the DP. Let the graphs be such that Vu e VG, [W()] A.
Color construction We consider the GNNs of Section A.1 Let i. be a one-hot encoding of node labels. Then, we use (Morris et al.) 2019 Theorem 2, Lemma 11) applied to a graph G composed by the disjoint union of the graphs in G. In particular, the GNN layers require the dimensionality of the embeddings to be T/1.g- Thereefore, after layers with O parameters each, we have that the embeddings hi, outputted by the I-th layer are such that h4 h4 iff (G) U (G). Moreover, h1, E {-1,1] We take these embeddings as the colors e used by the dynamic program, and let hi,.... ..mm be an enumeration of them.
Let CI....,Cp be an enumeration of the possible elements (Cu,,, c(u)), i.e., for each possible u and l. We suppose, without loss of generality, that if node u has color c(u) ) = hT then (Cu,t=o, c(u)) = C,, for each -.l............. -. This is valid since Cu,e=o is uniquely determined by c(u).
Let (11) Rmm.omm with W.,- NT. Let b E R with by -M + 1. Then ReLU(W +
b) is the one-hot encoding for the color of u. We take W E I xx.ss, with w(O = A and let
h1 (222) ReLU(WW + b) E TR. This is obtained by appending two-layer ML. to the MLP that outputs 1/. We then have that h A i-1 if and only if (C.,,=o, c(u) = C₁.
Message aggregation Then, the following h GNN layers have to simulate the dynamic program. Suppose that h hi(t-1 A if and only if (C,, C, This is true by construction for = Then we have that i = u (hi+e-1, EveN(u)) h(te-1) E TR22 is pair of integers, obtained via the aug-aggreg of the messages from (wu), that is a unique identifier for the element ((Cu,e-1, c(u)), & (C,,,-1,,(V) : E N(u) H). Let E.y...,E,.r, be an enumeration of the possible elements E, and let hi...., ......,,h.. han.. E 122 be the associated vectors.
Mapping aggregated messages to DP states Not that, in the dynamic program, the computa- tion of set C,.E depends uniquely on the sets Cr,t-1 for all c(v) for E (u)) U [u]. Indeed, while also the labels L(u) are used, these are uniquely identi- fied by the colors e(u) by construction. We then show that we can simulate the function mapping (CC,,-1,<(u)) ((C,,e-,,c(v))
Nuu). as well as the colors
N()) B) to (Cu,t, c(v)) using MLP.
Note that the map fitte [ARt,,,, 11ii4e E R is injective. Let then W()) RR..,..022 with w!T) = [Anr,.,, 1] and E I& with b, = -IAA 1] h. Then tri(W + b) is one-hot encoding for ((Cu,e-,,((u), (oo(:)))),((C._____ ((C,,e-1, : :ee:::eeNea (()
Let then (2)) I II with w - such that C, the output of one iteration of the dynamic program (i.e., lines 6 to 21) when it receives as input E, Then hite (r)tti((()) ( b) is equal to A 4-1 if and only if (C.,s, = C. Then, by induction on É, we have that h l is a unique identifier for (Cu,b; c(u)).
21

---

Published as a conference paper at ICLR 2025
Output layer In fact, we modify the last layer MLP by choosing W(2) with W if the output of one iteration of the dynamic program when it receives input is an element (C c(u)) with C.,A [r] + 0. and 0 otherwise. Then 4 1 if and only if Cv [r] + 0. Note that we obtained valid simulation of the dynamic program by using / GNN layers as defined in Section A.I at the node level. Finally, if we take as fout ( h model realizes the function f(G)
V& Isig Σ EugVa h4th,, we have that the zu VG TREE-COLSI u, [r] * and otherwise.
We observe that the MLPs use either an triangle function tri or linearized sigmoid Isig function. Both can be simulated using ReLU as follows.
Let x E R. Then tri(x) [1,0, -1] IR3 and ((I) (1,-2,11 Rix3
ReLUU x + b) with W 11 R b
Let R. Then Isig(x) W + 6) with w()) = [1,1]T x b = [0, -0TT R² and ( [1, I 1x
Moreover, in the proof, some parameters require non-constant number bits. We argue that such parameters can be replaced by more parameters with constant number of bits. Indeed, it is enough to maintain the invariant that h h E RGr,, is an one-hot encoding for C, rather than A In this case, the number of parameters for each MLP grows from O(G,T,,.)) to (G....g)
Lemma 5. Let 9 be set of graphs such that Vu E Vo, W(n) < A. Let tree with [Vr k. The number Sur. of distinct elements ((Cu,f-1,c(u)) $ u (u)))) satisfies
S.r. E O min (nthS 20.1 2//////(AA+))))))) 244+
Proof. There are k nodes in the pattern, and ne.1 distinct colors. Therefore, there are Q S E ("(1)) = Ontū,/kk) possible colorsets C.
Then, we have at most 2 sets of colorsets Cu.p and 2 sets of colorsets Cu,e. In turn, there can be at most D 1g..1 2n elements (Cu,e, c(u)). Therefore, have D O(ng. i/ Then, A-1
there are at most (.T.G = O(DA/AI D) = 0
2 (1a+1))../(--1)) elements E.
Moreover, the element & ((Cu,e-1, c(u)), ((C,,e-,,(u)) : u N() is fully characterized by UL+t(()) for any & I,..., h, so we also have G.T. S m+h.g.
C.5 SECTION B.1
Lemma 6. Let G be graph, T, be tree of height h. Let nodes VG be endowed with colors c. Let & be a parent- carent-coloruul locally injective homomorphism from to G. Then Ca(r), # 0.
Proof. Given node Vi, we call Tp the subtree of T rooted at Let ø be parent-colorful locally injective homomorphism from T, to G. We show inductively that e Ca(p). with (c(ő(g)) q E children(p)).
We first address the base case of the dynamic program, p is leaf. For each leaf p E Vr, we have that Co(p). = {0). since L(ő(p)) = L(p).
Let now p be non-leaf. Then, there exists a sequence Ui...., us of distinct neighbors of d(p) such that σ(4)) = 4i E children(p) and, for each ølv;, is still a parent-colorful locally injective homomorphism from T, to G. We have inductively that C, E Cotg). with C, the colorset associated with Φ0 Vr,- i.e, (c(((()) : i children(g)).
Since L(((p)) = L(p). the algorithm starts creating the set Colp).P in line 12. In particular, it will try on line 13 the correct sequence of nodes (V),... Ug) = (ő(q)).... o(qs)) and for that sequence the algorithm will try line 16 the sequence of colorsets Cg.:... ...,, Cgp. Since is corent-colorful,
22

---

Published as a conference paper at ICLR 2025
for each q and t children(g) we have that c(o(p)) # c(o(t)). Then, inductively, c(o(p)) C. for each q. Therefore, the set Cp = {c(g)= q E children(p)) } is inserted in Colp)..-
Then we have inductively that C, Co(r),r+ and have the claim.
Lemma 7. Let G be a graph, T, be a tree of height h. Let nodes VG be endowed with colors c. If Cu.r + 0, then there exists a parent-colofuul locally injective homomorphism &b from T to G such that ((r) = u.
Proof. Given node p E Vr, we call Tp the subtree of T rooted at p. We show inductively that if C' E Cu.p. then there exists a parent-colorful locally injective homomorphism é from Tp to G such that <(p) and {c()(1)) &q E children(p)) C.
Let be a leaf. Then we have that Cu.p = {0) iff L(u)= = L(v), that is p + u is a (parent-colorful) locally injective homomorphism.
Let now C E Cu.p for some non-leaf' p. Then, there exists sequence of distinct nodes (U1...., (6) from (u)) such that C was obtained by sequence of color sets (CI...., Cs). with C₁ E Co.oo. such that c(u) & C. Vi.
Then, we have inductively that, for each q E children(p), there exists a locally injective homo- morphism Φ; from Ty, to G such that (;(9:) = and there is no node t E children(q:) with c(u))
The domains of such maps are all distinct, since the sets Vr, :q E children(p) are pairwise disjoint. We can therefore define a new map o Vi, VG as ølvr,, = Φs and Φ(p) = u. This is a homomorphism as children of p are mapped to neighbors of u.
We show that o is locally injective for each node q E Vr,, Note that, for each i, for nodes in VT,, \ { the connectivity is the same as the one given by di, and the claim therefore is true inductively. Moreover, since the nodes U2,...,2' = o(g))..... ((g))......((.. (ggs) are all distinct, & is locally injective on p.
Moreover, for gi. Vi, we have that N(a:) = children (q:) U (p]. Clearly d(4)) * 6(12), Vh,, l2 E (g)ldren(g)) since @ is locally injective on Vr,,- Finally, Φ(t) * ø(p) u Vt E children(g:) since there is no node i children(g:) with c(é(t)) c(u). Because of this, the map & parent-colorful. Moreover, we have that {c(((g)) q E children(p))- CC
Theorem 6. Let G be a graph, T, a tree of height h. Let nodes VG be endowed with colors c. Then, (REE-COLLIH,,u, h)[r] Cu.r # 0 if and only if there is a parent-colorful locally injective homomorphism & from T, to G such that Φ(r) =
Proof. If there is parent-colorful locally injective homomorphism o from T, to G such that Φ(r) u, then by Lemmal 6 we have that Co(r).r , * Ó. Moreover, by Lemma 7 if Cu, * V. then there exists a locally injective homomorphism & from T, to G such that ((r)
Let T a tree of height h, G be a graph whose nodes are endowed with colors c. Let T be such that Vp E Vr, Aq E children(p) and vt E children(q) it holds that L(p) & L(t). Let also G be such that the minimum cycle length at least 2h + Then, TREE-COLLIH, (u, h)(r]] + if and only if there is a subgraph isomorphism & from T to G such that Φ(r) = u.
Corollary 2.
Proof. Let the colors of nodes G be their labels. Then, any locally injective homomorphism é from T to G such that ((r) Vt E children(g) it holds that L(p) o L(t) and therefore c(p(p)) * c(o(t)).
is parent-colorful since Vp E Vr, Vg E children(p) and
We apply Theorem 6 We then obtain that Cu,r + 0 if and only if there is locally injective homomorphism o from T to G such that Φ(r) = u. We need to show injectivity. Suppose by contradiction that d(q1)
o((2) for some Q1 # 92 E Vr. Let be the lowest common ancestor of q
and 92. Let (p. ti..,.... th, = :1) and (p, S1........ S/2 = 42) be the paths connecting p to respectively
qi and Q2. Since h1 h2 E h. we have by +h2 & 2h, for any q q2. Then, (Φ(p), ((1))...., ((h,)) =
23

---

Published as a conference paper at ICLR 2025
(( .................... ((s1). ((p)) is cycle of length at most 2h. This is contradiction the minimum cycle length is at least 2h + 1.
D ADDITIONAL EXPERIMENTAL RESULTS
In this section, we provide further experimental results and supplement the experimental sec- tion in the main paper. Our code and data are available github.com www.oob.cooo//oggaaaaaaaaa Borgwardb.aab/
D.1 COUNTING IN REAL-WORLD DATASETS
In order to showcase the subgraph counting capabilities of GNNs, we selected a subset of molecular datasets. We focus on molecular benchmark datasets since subgraph mining and counting in molec- ular data have been the focus of extensive research, due to the relevance of subgraphs corresponding to functional groups. Such subgraphs play an essential role in generating molecular fingerprints.
Statistical properties of all considered datasets can be found in Table 5 We note that some datasets include node attribute vectors encoding subgraph information (e.g., the 6-cycle). To mitigate such biases, we retain only the atom type as node feature in the datasets ogbg-molhig oghg-molpcba, Peptides-func, and PCQM-Contact, also ensuring consistency with other datasets. All experiments and statistics provided in this work are based on such reduced node features.
To identify a set of suitable pattern graphs, we used the subgraph miner FSG (Kuramochi Karypis 2004), to mine all patterns that occur with frequency of at least 25% across all considered datasets. We include all such tree patterns of size and as well as cyclic patterns of size 6 and 7. The condi- tion on the frequency was implemented to ensure that subgraph counts are non-zero in a substantial number of cases. To complement the set of patterns with an additional cyclic graph, we furthermore include the (non-frequent) 5-cycle, which is often of particular interest in molecular structures. Since node attributes vary between the considered datasets, in Table 4 we depict a pattern graph H with node colors such that in each dataset the corresponding pattern obtained by replacing the colors of H with specific node attributes.
We use the GNN k architecture as described in Section A. with K = 4 MLP-layer-basee message passing layers. As some datasets include edge attributes, we modified the model to aggregate and append edge attributes to the node features during the message passing process. The dimensionality of the GNN embeddings is fixed at 512. We used the Adam optimizer with a variable learning rate and batch size of 12 128. The data is split into 80% for training and 20% for testing. Finally, we train for 300 epochs and report the mean as well as the standard deviations over at total of 5 such runs.
We framed the learning problem as a classification task, where the classes correspond to discrete count values ranging from zero to the maximum count observed in the training set. As evaluation
Table 4: Test set results for subgraph counting with a GNN on molecular graphs. Node colors visualize different atom types. Reported: Normalized Mean Absolute Error (nMAE, see Def. in Sect. D.I and Area Under the Curve (AUC) for the multi-class classification problem.
Partern
Dicaset
Metric
0-0-6
0-0-5
0-0-0
0-0-0
0-0
0-0-0
8...
8.8
0-0-0
6.050
8-
iMAR
0,071
0.046
0,074
0.048
0,073
0.066
0,057
0.073
0,043
0.071
0.007
0.16]
0.167
0,102
Mutugenicity
AUC
0,887
0.936
0,670
0.938
0.912
0,910
0.943
0.898
0.910
0.935
0,889
0,949
0.926
0.7%6
iMAR
0,008
0,19
0.012
0017
0017
0.013
0,03
0.011
0,015
0,03]
0,01
MCF-7
20
27:41
AUC
16/02
11.04
MMAE
0.012
0.018
0,029
0.012
0.020
0.019
0.018
0.013
0.009
0.111
0.005
0.025
0,09
0.14
ZINC
AUC
0,904
0.966
0.957
0.967
0.940
0.965
0.974
0.06
0.980
0.091
1,000
0.995
0,972
RMAE
0,002
0.001
0
0.017
0.005
0.021
0.002
0,003
0.004
0.002
0.004
0,011
0,002
0.00
ogbg molhiv
AUC
0.919
0.958
0.925
0.919
0914
0.928
0.975
0,80
0.915
0.923
0.961
0.973
0,902
oghg-molpchh
IMAR
0,000
2000
2012
22
0.000
22
2009
0.000
0.000
0,000
0.000
AUC
0.098
10.07
MMAE
0.016
0,099
0,017
0.008
0
0
0.002
0.000
0
Poptides-fune fune
AUC
0,355
0.987
0.77
0.930
0.920
0.941
0,997
0.82
0.936
0.940
0,882
0.944
RMAE
0.000
0.003
0,006
0.000
0.001
0.000
0.000
0,000
0.000
0.000
0.003
0,002
0.001
0.001
PCQM Contact
AUC
0.998
0.963
0 1968
0.968
0.946
0.941
0,987
0.991
0 0.990
0 0.986
0.999
1,000
24

---

Published as a conference paper at ICLR 2025
Table 5: Statistical properties of real-world molecular datasets. We report the number of graphs, as well as the average number of nodes and edges. All datasets are endowed with node and edge labels.
Name
# Graphs
Avg. nodes
Avg. # edges
Mutagenicity (Kersting ct al.
2016
30.32
30.77
MCF-7 (Kersting al., 2016
27770
26.40)
28.53
ZINC (Gömez- Bombarelli el al. 2018
12000
23.16
24.92
ogbg-molhy (Hu ci al., 2021: Wu al.
2018
41127
25.51
27.47
bahg-molpcba (Hu al. 2021 Wü of
2018
437929
25.97
28.
Peptides-fun func (Dwivedi et al. (202
Singh al.
2015
15535
150,94
153.65
PCQM-Contace (Dwivedi al. 2022
529434
30.14
30.54
metrics, used Area Under the Curve (AUC) as well normalized Mean Absolute Error (nMAE). For AUC, we employed the One-vs-One approach to evaluate the model's performance across mul- tiple classes. The nMAE defined as the mean average error normalized by the true values. More formally, for true and predicted values y; and is with [N], given by Σ i=1 max (.b6) where the max function is used to avoid divisions by zero.
18--9
Table the predictive performance across wide range of dataset and pattern graph combi- nations. The results clearly demonstrate that subgraph counting on real-world molecular graphs can be done quite accurately.
D.2 NUMBER OF TRUNCATED UNIVERSAL COVERS
In Table 6 we provide the numbers of distinct WL node labels for E [], or equivalently, the numbers non-isomorphic truncated universal covers T/ over given dataset We observe that, the Peptides-fure func dataset has low values of Ne,9, wich suggests the applicability of the results of Section
These values, as well as the values reported in Table 2 and Table are obtained by taking into account edge label information. Moreover, as discussed in the previous section, we retain only the atom type node features.
Table 6: Number of node and edge labels of common molecular datasets (where we restrict node labels to atom types only), and number Tkg of non non-isomorppic truncated universal covers.
node labels
edge labels
Datasct
t=
f=
f=
Mutagenicity
14
3
334
4997
21118
43750
63568
76920
MCF-7
46
668
18163
112803
229231
328616
409294
ZINC
21
499
13006
70302
144592
198159
229065
ogbg-molhiv
55
7
1923
37286
169766
319986
A46262
547678
ogbg-molhiv
44
11
1185
44190
314139
915519
1857547
3040681
Peptides-fune
6
76
411
1308
4704
18248
68392
PCQM-Contact
1745
97914
913960
2812873
5249611
7492474
D.3 QUITE- DUITE-COLORFULNESS IN MOLECULAR DATASETS
We now experimentally evaluate the assessment made in Section 5.2 on the quite-colorfulness of subgraph isomorphisms in cases where the pattern at hand not quite-colourful itself. Figure/Jree ports the proportion of quite-colorful subgraph isomorphisms from non-quite-colorful tree patterns. Specifically, for given dataset, we iterate over all subgraph isomorphisms from the pattern to the disjoint union of dataset graphs, and check each subgraph isomorphism for whether it is quite colour- ful. We report the ratio [Q]/[S] of quite-colorfut subgraph isomorphisms [Q] to the total number of subgraph isomorphisms |S| for increasing numbers of WI. iterations
25

---

Published as a conference paper at ICLR 2025
Motapminity
6.75
033
10008
0.50
0.00
WL,
MCP-7
Peytides Tune
6.70
0.15
102.01
1.00
0.80
WL Hiratiaa
XINC
POggd
1.00
6.75
WT. Aeations
WT. Nt..eee
ogbi
1.00
100005
0.0
0.0
0.0
6.0
000
0-0
0
0-0
9-0.0
0-0
Figure 6: Proportion of subgraph isomorphisms that are quite colourful, reported for colors ob- tained by increasing numbers of color refinement iterations l. The proportion is given [Q|/|S), where [Q] is the number of quite colourful subgraph isomorphisms from the pattern to the dataset graphs, and |S] is the total number of subgraph isomorphisms.
The results show that for several real-world datasets, such as MCF-7, Mutagenicity, and ZINC, nearly all subgraph isomorphisms are quite colourful when target graphs are node-colored using iterations of color refinement. Naturally, the patterns themselves are not quite-colorful, none of the subgraph isomorphisms are quite-coloriie when target graphs are not node-colored with color refinement (case = 0). Notably, an interesting case arises the Peptides-fumt dataset, where for one of the tree patterns none of the subgraph isomorphisms are quite colourful, regardless of the value of kt
D.4 RULING OUT STAR PATTERNS
We now empirically validate Corollary specifically, we demonstrate that (non-induced) subgraph counting can done in practice for sce- narios fulfilling parent-colorfulness (see Def. (5) and colof-colorfulness (see Def. (3). Recall that while Chen al. (2020) show that subgraph counting cannot be done by GNNs in general, (non- induced) counting of star-shaped patterns nonetheless remains possible. To rule out the possibility that a model is leveraging this information in the following experiments, we specifically construct datasets where every graph has the same multiset of star-shaped patterns.
2 and Theorem 5 on challenging synthetic datasets. More
In all experiments, we used a 4-layer GNN, as specified by the functions in Section A. with a hidden dimension of 512, batch size of 128, and the Adam optimizer. The data was split into 80% for training and 20% for testing. We report the predictive performance after 1,000 epochs.
To verify the claim in Corollary 2 randomly generated 2,000 graphs, each with 32 nodes and 39 edges, ensuring that the minimum cycle length was Node labels were assigned based on node degree to guarantee that the mappings from the patterns parent-colorful. More precisely, first
26

---

Published as a conference paper at ICLR 2025
generated trees of size 32 using fixed node degree sequence, then added 8 edges while ensuring that the resulting graphs have the same node degree set and contained no cycles of length or less.
Table 7 (left) shows the predictive performance for several pattern graphs. In accordance with Corol- lary the results show near perfect predictive performance on the test set on all pattern graphs
We furthermore investigate the case where pattern mappings quite-colorful. For this, gener- ated more challenging dataset of 2,000 randomly generated graphs with 96 nodes and 120 edges each, with constraints the graphs using fixed node degree sequence. Node labels were assigned based on node degree. We consider patterns that ensure mappings learns to count very accurately. Note that the predictive performance increases for larger patterns, which might be due to the usually large and diverse subgraph counts of small patterns.
the minimum cycle length. More precisely,
randomly generated
quite-colorful. Table 7 (right) shows that the model
Table 7: Predictive performance for non-induced subgraph counting in scenarios where pattern matching is parent-colorful (left) and quite-colorful (right).
Metric
Metric
MAE
0.000
0.020
0.090
0.015
MAE
0.128 0.966
0.138
0.015 0.986
0.000
0.000 1.000
AUC
1.000
0.980
1.000
0.959
0.968
AUC
1.000
27


Reviews:
[{"review_id": "jxjlkskO4Y", "reviewer": "Reviewer_4XuU", "summary": "In the submitted manuscript, the authors study the ability of Graph Neural Networks (GNNs) to count substructures. So far a negative result, showing that not all substructures can always be counted by GNNs has been proven. The authors significantly extend our knowledge of this area by proving under what conditions all substructures in a graph can be counted by GNNs. They identify several drawbacks in this general result. They then make use of the fact that subgraph counting is an inherently local task and refine the conditions on the dataset to in turn improve upon their result. Furthermore, two dynamic programs are presented for subgraph counting in trees and graphs without short cycles, and it is shown that GNNs can simulate both these algorithms to successfully count subgraphs. Finally, the authors present empirical properties of real-world datasets, validating the applicability of their theoretical results, and study the predictive performance of a GNN on simulated data.", "questions": "1] On several occasions in the empirical analysis you are imprecise on what GNN you use to investigate your hypotheses. I think the clarity of the paper would be improved if you stated more precisely what GNN you used. I am in particular referring the Line 59 and the discussion/caption of Table 1, as well as the experiments in Section 6.2, e.g., Line 479.\n\n2] The paper you presented is one that the reader really has to work through. It is dense and complex. More patient explanation and more frequent examples would make for more pleasant reading. Examples would aid especially in the more advanced concepts in the preliminaries and in Section 5. \n\n3] In your list of limitations of the result of Proposition 1, it would be appropriate to add that you require an impractically deep GNN, where the number of layers $\\ell$ appears to be equal to the maximal number of nodes $n$ in any given graph in the dataset.\n\n4] Your experiments could be improved and extended in a variety of ways.\n\n4.1] In the main paper it is completely unclear how your synthetic dataset is constructed. The appendix also does not add much further detail on this. I believe you must be more precise on how you construct your synthetic dataset. \n\n4.2] I do not understand why you do not provide empirical results for GNNs counting substructures on real-world datasets. It seems incomplete to me to provide details about the $(\\ell,k)$-identifiability of real-world datasets and to then only validate your theory on simulated datasets.\n\n4.3] Since the width, i.e., hidden dimension, of the GNN's readout function and the number of required message passing layers play a role in your theoretical results, it would be nice to complement your theory with an empirical ablation study on the impact of these parameters in practice. \n\n4.4] It would be better if you referred to the appendices on the empirical aspects of your work, i.e., the ones accompanying Section 6 in the main paper. In general more details on the experimental setting, i.e., more discussion in Appendix A.6, and possibly also the required code to reproduce the experiments would be nice. \n\n5] Minor comments:\n\n5.1] Since your write-up is of such high quality, I want to suggest a few minor reformulations to aid in perfecting it. Please feel free to reject any of these suggested edits. Line 67: \" conditions for which\" -> \"conditions under which\"; Line 233 \"such function are\" -> \"such functions are\"; Line 469 \"table 3\" -> \"Table 3\"\n\n5.2] In Line 121 I think you may have a typo in the definition of a rooted tree. Specifically, in the following: \"$\\text{children}(q) = \\q$\" I think it may be correct to consider \"$\\mathcal{N}(q)$\" here. \n\n5.3] The algorithm name \"$\\text{TREE-LIH}_c(u,h)[r]$\" is never formally introduced in the text and the argument in angular brackets $r$ is only mentioned in Theorem 4. It may be nicer to introduce this algorithm name and to more consistently and explicitly define the arguments the algorithm takes. \n\n5.4] The notation in the algorithms are not always defined, e.g., \"return $\\epsilon$\", is never explicitly defined. It may be nicer to add a brief explanation of this. I furthermore noticed that Algorithm 3 is never explicitly mentioned in the text and it would be nicer to draw the reader's attention to it at some point by pointing it out. \n\n5.5] The model that you define in Appendix A.1 appears to be similar to the GraphSage model [1] to me. Did I miss an important difference? If not then it may be nice to cite their work. \n\n[1] Hamilton, W., Ying, Z. and Leskovec, J., 2017. Inductive representation learning on large graphs. Advances in neural information processing systems, 30.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The paper is very well-written and clear. \n- The theoretical results are of clear importance to the field and present significant progress.", "weaknesses": "Please find further detail on my listed weaknesses in my questions below.\n\n- A clear area for potential improvement of this work is the empirical analysis. Your results could be more broadly validated empirically. But I appreciate that not all papers need both a substantial theoretical and empirical contribution and the theoretical contribution here is very strong. \n\n- In parts the writing is a bit dense and difficult to follow. Some examples may help to make the text more accessible. \n\n- You should state more explicitly what GNN you used in your experiments.", "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": "", "extra_scores": {}}, {"review_id": "asMZxPf7Sd", "reviewer": "Reviewer_oWTR", "summary": "In this paper, the authors argue that graph neural networks (GNNs) can often count graph patterns across various real-world datasets. They provide conditions under which GNNs can count subgraphs, based on local substructures around nodes. The authors also propose novel dynamic programming algorithms to solve the subgraph isomorphism problem for specific classes of pattern and target graphs and demonstrate that GNNs can efficiently simulate these algorithms.", "questions": "See the questions in \"Weaknesses\".\n\nBelow are some additional questions:\n\n(1) The abstract mentions \"sample-efficiently learn to count subgraphs.\" It is unclear what \"sample-efficiently learn\" means in this context. Can the authors provide a precise definition of \"sample-efficiently learn\" in this context, including any relevant metrics or benchmarks they use to measure sample efficiency?\n\n(2) In Table 1, which GNN model is used? Appendix A.5 does not specify the GNN architecture. Also, what are the classes, and how is AUROC  calculated for induced subgraph counting in the multi-class classification setting? A statistical description of the datasets (e.g., number of graphs and classes) along with relevant citations would also be helpful.\n\n(3) Regarding \"the classical negative result of Chen et al.\" mentioned in the first paragraph of Section 3, can the authors specify which theorem in their paper this refers to?  In my review of the paper, it appears that Chen et al. just use counterexamples (a pair of graphs that have different induced-subgraph-counts of the pattern but cannot be distinguished from each other by 2-WL) to prove their results. I don't understand the claim \"This result, however, requires that the set of graphs at hand features specific WL-indistinguishable graphs, which is unrealistic in practice\". Can the authors clarify this claim?\n\n(4) Assigning random colors to nodes in a graph would result in different colors for nodes within the same orbit. Detecting nodes in the same orbit is non-trivial and requires the computation of graph automorphisms. How would the work of color coding address this issue?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "**Originality**\n\nThe paper introduces several original ideas, including conditions under which GNNs can perform subgraph counting on specific class of graphs, dynamic programming algorithms for specific subgraph isomorphism problems, and an analysis of their connections with GNNs.\n\n**Quality**\n\nI have some concerns/questions regarding the quality of the paper (see \"weaknesses\").\n\n**Clarity**\n\nThe paper is not easy to follow, primarily due to issues in presentation. For instance, some of the notations (e.g., Tree-LINc(u,h)[r]) are overly complex, lacking intuitive explanation, and certain concepts (e.g., pattern node, pseudo-dimension, etc.) are not clearly defined. The motivations for studying specific variants of the subgraph counting problem are not well-articulated, making it difficult to understand the significance of these variants within the broader context of the research.\n\n\n**Significance**\n\nThe research area of graph neural networks and subgraph counting explored in this work is significant. However, the paper primarily focuses on WL-distinguishable graphs and tree patterns for its dynamic programming algorithms.  The contributions have a limited impact on the field.", "weaknesses": "(W1) The paper lacks technical depth and rigor.\n\nProposition 1 is limited to graphs that are distinguishable by the 1-WL test. Since 1-WL can distinguish only certain types of graphs, the results do not apply broadly to general subgraph counting functions. Rather than interpreting that GNNs can count all subgraphs within a class of 1-WL-distinguishable graphs, it would be more natural to explore whether GNNs can count specific classes of subgraphs, such as trees and forests (i.e., graphs with treewidth 1), within general graphs. If the class of graphs is restricted to those distinguishable by 1-WL, the results appear trivial.\n\nThe statement, *\"It is immediate to see that subgraph counting and induced subgraph counting (i.e., counting the number of (induced) subgraph isomorphisms $\\phi$ from $P$ to $G$) are node-decomposable,\"* is central to the paper. However, if this is intended as a general statement, I have doubts about its correctness. I was unable to find a proof in either the main paper or the appendix. Since local neighborhood counts can lead to overcounting or miss global structures, they may not yield exact counts for general subgraph counting. Can the authors clarify this statement by formalizing it in the context of subgraph counting and providing either a formal proof or relevant citations? Please explain why this statement holds or does not hold for general subgraph counting.\n\nThe proof of Theorem 1 relies solely on node-level functions. However, if graph-level functions were considered, these two graphs could be easily distinguished, as they differ in the number of nodes and edges.\n\n(W2) The significance of this work is unclear and appears to be limited.\n\nRegarding the statement, \"We develop novel algorithms solving the (non-induced) graph isomorphism problem on restricted pattern or target graph classes,\" can you clarify what is meant by the (non-induced) graph isomorphism problem? Generally, graph isomorphism is a different problem from subgraph isomorphism. Moreover, for restricted pattern or target graph classes, such as trees and forests, it is known that the expressivity of MPNN (and 1-WL) is upper bounded by homomorphism counts of forest [2]. Given this, why is there a need to develop dynamic programming algorithms to tackle the locally injective homomorphism problem specifically for tree patterns and to use a GNN model to simulate this? It would be helpful if the authors can explain how their approach differs from or improves upon existing methods for counting homomorphisms in trees and forests, and clarify the specific advantages or novel insights gained from their dynamic programming algorithms and GNN simulations compared to known results about MPNN expressivity.\n\n\n(W3) Missing related work\n\nThe paper [2] specifically discuss how the expressivity of GNNs can be measured in a hierarchy of subgraph counting. \n\n\nReferences:\n\n[1] Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness, Zhang, et al., ICLR 2024\n\n[2] N-WL: A New Hierarchy of Expressivity for Graph Neural Networks, Wang, et al., ICLR 2023", "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": "", "extra_scores": {}}, {"review_id": "7CxWkxeZW2", "reviewer": "Reviewer_m1EJ", "summary": "This paper explores the capability of GNNs to detect and count substructures in real-world datasets, despite known theoretical limitations in their expressive power. The authors challenge established assumptions by demonstrating that GNNs can perform subgraph counting tasks with surprising accuracy, even when conventional GNNs struggle to distinguish certain non-isomorphic graphs. The main contributions include deriving conditions under which GNNs can effectively count subgraphs by leveraging local structures, designing dynamic programming algorithms for solving subgraph isomorphism in restricted graph classes that GNNs can simulate, and empirically validating these theoretical findings across various datasets. By introducing the concept of $(l, k)$-identifiability, the paper bridges the gap between theory and practice, providing a framework that explains the unexpectedly robust subgraph-counting abilities of GNNs and highlighting their practical utility beyond theoretical constraints.", "questions": "1. Can the authors provide more specific examples or scenarios where the condition of $(l, k)$-identifiability fails?  This could help clarify the limitations of their proposed framework.\n\n2. How do the authors justify the reliance on WL classes in determining graph indistinguishability? Are there potential edge cases where this might not hold true, particularly in practical applications?\n\n3. The paper mentions that the GNN may require up to $2^{(n-1)}$ message passing layers in the worst case. What are the empirical implications of this for large graphs? Are there any optimizations or heuristics that could be discussed to mitigate this?\n\n4. If feasible, providing access to the code developed would enable others to replicate your experiments and potentially extend your work.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces novel concepts regarding the identifiability of graphs through message passing, which builds on the existing theoretical framework of GNNs. The exploration of $(l, k)$-identifiability offers a fresh perspective on subgraph counting tasks.\n\n2. The writing is generally clear and structured, with a logical progression from theory to application. Key concepts are well-defined, making the paper accessible to a broad audience within the machine learning and graph theory communities.\n\n3. The findings contribute to the ongoing discourse around the capabilities and limitations of GNNs in solving graph-related problems. By demonstrating that GNNs can efficiently solve subgraph counting under specific conditions, the work is likely to influence future research directions in both theoretical and applied settings.", "weaknesses": "1. While the method is shown to work for subgraph counting, there is minimal discussion of its computational complexity, particularly for larger graphs or deeper GNN layers. Insight into time complexity would make the approach more practical.\n\n2. This work mentions WL limitations but does not analyze upper bounds or scenarios where the proposed method may struggle with expressivity. A comparative analysis with existing expressive GNN models would provide a clearer understanding of when this approach is suitable.\n\n3. Adding visual representations of key concepts, such as the identification of $(l, k)$-identifiable nodes could enhance reader understanding and engagement.\n\n4. Missing references: \n\n[1] C. I. Kanatsoulis and A. Ribeiro, Counting Graph Substructures with Graph Neural Networks, ICLR 2024.\n\n[2] Huang et al. Boosting the Cycle Counting Power of GNNs with I²-GNNs, ICLR 2023.\n\n[3] Raffaele et al. Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning, ICLR 2024 Workshop.\n\n[4] Wang et al. *N*-WL: A New Hierarchy of Expressivity for Graph Neural Networks, ICLR 2023.\n\nTheir inclusion could offer a more comprehensive view of how this method stands against similar research in GNN perspective.", "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": "", "extra_scores": {}}, {"review_id": "xc98A4iUWf", "reviewer": "Reviewer_oojv", "summary": "This work studies whether and under which conditions graph neural networks (GNNs) can sample-efficiently count substructures. This is motivated by the observation that GNNs can count graph patterns with good accuracy on real-world datasets, despite the known poor subgraph counting ability at worst case. By leveraging the fact that counting patterns is local and node-decomposable, the authors prove that GNNs can perform subgraph counting with number of parameters independent of graph size, under the condition that nodes' ego-nets can be distinguished by WL test.  Furthermore, GNNs are shown to be algorithmically-aligned with a tree counting algorithm that finds locally injective homomorphism. Experiments demonstrate the effectiveness of subgraph counting on real-world molecular graphs.", "questions": "1. Though Table 3 shows the high identifiable ratio of Mutagenicity dataset, I wonder why the counting performance (MAE) is poor  in Table 1.\n2. To let the subgraph counting algorithm 1 work, it requires the graph to have some inherent node colors to satisfy parent-colorful. Does that mean the algorithm (and thus GNNs) cannot perform such counting if the graph has no node attributes?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. A theoratical justification of subgraph counting power beyond worst case is provided.\n2. Sample efficiency: the number of parameters is shown to be bounded, and an alignment to a subtree counting algorithm is also demonstrated. These provides clues for possible good generalization of GNNs for subgraph counting.\n3. The paper is well-structured and easy to follow.", "weaknesses": "1. In Table 1, only results of four graph patterns are shown. It makes the evaluation stronger if more results of common substructures can be provided, or an explanation of why the current chosen ones are important to consider. For example, 5-cycle is also a common substructure in molecules.  \n2. The algorithm alignment is largely restricted to tree patterns, which is less interesting especially for molecular graphs.", "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": "", "extra_scores": {}}, {"review_id": "SIm7K0hBP9", "reviewer": "Reviewer_gZ4p", "summary": "This paper presents a solid theoretical framework on GNNs ability in subgraph counting, bridging the gap between their theoretical limitations and real-world performance. One of the key contributions is the identification of specific conditions under which GNNs can efficiently compute functions on graphs based solely on local substructures around the nodes. Additionally, the authors introduce a novel dynamic programming algorithm for problems related to subgraph isomorphism, showing that GNNs can effectively simulate this approach. They also back up their claims with experimental results, which adds to the paper's credibility.\n\nOverall, I found the paper to be quite interesting. However, my current rating is a 5. I would be willing to raise my score if the authors address the weaknesses I’ve pointed out.", "questions": "I refer the authors to the weaknesses.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written and effectively motivates the problem it tackles. The authors provide a solid background that helps readers understand the context and importance of their work. Additionally, the authors use various synthetic and empirical datasets to strengthen their analysis and showcase the practical relevance.", "weaknesses": "Here are some weaknesses I noticed in the paper that I would like the authors to address:\n\n- The authors did not reference important works in the field, such as \"Counting Graph Substructures with Graph Neural Networks\" by Kanatsoulis and Ribeiro, and \"Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting\" by Bouritsas et al. A more thorough literature review is needed.\n\n- Additionally, the paper lacks comparisons with other methods and does not discuss how existing methods could be adapted for their task. \n\n- Finally, the absence of code limits the reproducibility of their results. I appreciate the provided pseudocode, as it makes the paper easier to follow.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)