On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Model
Authors: Alexander Pluska
SAGAR MALHOTRA
Venue: NeurIPS 2025 poster ()
Keywords: Random Graphs
Sparse Random Graphs
Graph Neural Networks
Primary area: theory
TL;DR: A novel notion of local convergence, color convergence,  that characterizes the random graphs on which MPNNs can be learned. A new random graph model that  is universal wrt color convergence.

Abstract: Local convergence has emerged as a fundamental tool for analyzing sparse random graph models. We introduce a new notion of local convergence, _color convergence_, based on the Weisfeiler–Leman algorithm. Color convergence fully characterizes the class of random graphs that are well-behaved in the limit for message-passing graph neural networks. Building on this, we propose the _Refined Configuration Model_ (RCM), a random graph model that generalizes the configuration model. The RCM is universal with respect to local convergence among locally tree-like random graph models, including Erdős–Rényi, stochastic block and configuration models. Finally, this framework enables a complete characterization of the random trees that arise as local limits of such graphs.

On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Model
Alexander Pluska Sagar Malhotra
Department of Computer Science
TU Wien Vienna, Austria
Abstract
Local convergence has emerged fundamental tool for analyzing sparse random graph models. We introduce a new notion of local convergence, color convergence, based on the Weisfeiler-Leman algorithm. Color convergence fully characterizes the class of random graphs that are well-behaved in the limit for message message-passing graph neural networks. Building this, propose the Refined Configuration Model (RCM), a random graph model that generalizes the configuration model. The RCM is universal with respect to local convergence among locally tree-like random graph models, including Frdōs-Rényi, stochastic block and configuration models. Finally, this framework enables complete characterization of the random trees that arise as local limits such graphs.
Introduction
Understanding the local structure of random graphs is important for analyzing algorithms in network
science and machine learning (Van Der Hofstad| 2024 Lovász 2012 Borgs et al. 2019 2021
Gamarnik & Sudan 2014). Local convergence characterizes the structure around a randomly chosen
node in the large graph limit (Benjamini & Schramm 2011). However, this level of detail exceeds
what can exploited by color refinement (Weisfeiler Leman 1968 Babai et al. 1980 Huang & Villar 2021a) Neural Networks (MPNNs) (Gori et al.) 2005 Scarselli et al., 2009. Xu al., 2019 Morris et al.. 2019). In this paper introduce novel notion of local convergence, namely color convergence, that is closely aligned with color refinement, and facilitates the analysis MPNNs through the framework of local convergence. We show that color convergence completely characterizes general notion of learnability for MPNNs. We then show that the class of color convergent random graphs subsumes widely investigated locally like-like models (Van Der Hofstad 2014 2024) including sparse variants of Erdös-Rényi, stochastic block (Abbe et al. 2014), and configuration models (Bollobás) 1980). Finally, devise random graph model, called the refined configuration model (RCM), that is universal with respect to color convergence.
prominent algorithm that bounds the expressivity of Message Passing Graph
Related Work
Our work makes key contributions the areas of graph limits, generalization analysis of MPNNs, and random graph models. In the following, we briefly discuss the related work in these areas.
Graph limits. Our work expands the general investigation of random graph limits (Lovász 2012 Limits for dense random graphs are charecterized by graphons (Lovasz & Szegedy] (204).. In the
sparse setting, local convergance has emerged as important tool for analyzing the limit behavior
of random graphs (Benjamini & Schramm 2011 Aldous & Steele 2004 Aldous & Lyons 2007
Hatami et al. 2014 Milewska et al. 2025 Dort & Jacob 2024) In this paper, introduce novel
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

relaxation of local convergence, that characterizes the structure around a randomly chosen node in terms of the color refinement algorithm (Weisteiler & Leman 1968 Huang & Villar 2021a).
MPNN Generalization. Our work advances the analysis of generalization behavior of MPNNs.
Previous works have investigated generalization behavior of MPNNs, e.g., via VC dimension,
Rademacher complexity or PAC-Bayesian analysis (Liao et al., [022] Oono & Suzuki 2020 Maskey
al. 2022 Li et al. 2022 Tang & Liu 2023 Rauchwerger et 2025 Morris et al. 2023). Most
of these works fix a class of random graphs as data distribution and are largely restricted to the dense
graph setting. We especially focus on generalization behavior of MPNNS for the node classification task on sparse random graphs (Baranwal et al., 2023). However, instead of making assumptions on the data distributions, we give complete characterization of random graphs on which MPNNs can be learned. We use general notion of learnability, which is closely related to the notion of uniform convergence in learning theory SShalev-Swwarte et al. 2010). In particular, we show that MPNNs fail to learn on dense random graphs, extending asymptotic analysis of MPNNs in this setting (Adam-Day et al.
2024 Yehudai et al., 2021].
Random Graph Models. All dense random graph models admit a universal limit object (Aldous 1981 Bloem-Reddy & Teh 2020; Lovasz& & Szegedy 20044
Lloyd et al. 2012). However, no such universal limit is known in the sparse setting (Lovász 2012). This has led to a fragmented landscape of sparse random graph models such as the sparse Erdös-Rénge configuration and preferential attachment model. Despite their differences, unifying property of many models is their local converge Galton-Wann Watton trees (GWT) [Janson| 2012), a family of random trees arising from branching processes (Harris 1963). These trees capture the typical local structure around uniformly chosen node and serve as canonical, though not universal, object in the study of local limits.
Contributions
We introduce a generalization of local convergence, color convergence, based on the color refinement algorithm. Color convergence defines sparse random graph limits based the color of random node after fimitely many iterations of the color refinement algorithm. We present systematic investigation of color convergence. Specifically,
We show that color convergence completely characterizes the class of random graphs on which MPNNs achieve probabilistic consistency of empirical risk for node classification tasks. That is, color convergent random graphs are exactly the random graphs for which the empirical risk converges to the true risk with high probability for all possible MPNNs.
We introduce the refined configuration model, a generalization of the configuration model. Leveraging color convergence, we show that it captures the limit behavior of MPNNs on random graphs and is universal with respect local convergence to Galton-Watson trees. In the limit, it subsumes many widely-invesstiated sparse random graph models, including Erdös-Rényi, stochastic block and configuration models.
2 Background
We use [n]] to denote the set {O..... n 1} and 1 to denote the indicator function of a set A.
An undirected multigraph G consists of set of nodes V and set of edges E, possibly containing loops and multi-edges. We use N(v) to denote the multiset of neighbors of a node v and d, to denote its degree. In this paper, graphs are always finite, undirected multigraphs. Sometimes the nodes u attributed with a feature Ty. We always assume that the space of features is countable and discrete.
A rooted graph B is graph with designated root node. The depth of node is its distance to the root. The depth of a rooted graph B is defined as the maximum depth of its nodes. We denote by B₁ the set of isomorphism classes of rooted graphs of depth at most k. Given a graph G' and node the ball Bx) is the graph rooted at v. spanned by vertices w with d(v, w) < k. If f is a function defined nodes and B is rooted graph with root r, then we may write (B) instead of f(r), e.g.. we may write (B) for the neighbors and d for the degree of the root. An isomorphism between rooted graphs is graph isomorphism that also maps the root of one graph to the root of the other.
free is a connected acyelic graph. A rooted tree a rooted graph whose underlying graph a tree. We denote by Th the set of isomorphism classes of rooted graphs of depth k. We write T'k to denote
2

---

the rooted subtree of T containing only nodes of depth at most k. Each node in rooted tree, except the root node, has unique parent node, which is the only adjacent node that has a smaller depth. The children of node are the nodes adjacent to it with larger depth. A leaf node is a node without children. The sub-tree T()) induced by node e the maximal sub-tree of T containing the node but not its parent.
All probability spaces considered in this paper are countable and discrete. A probabiliyy mass mass function (PMF) μ4 is function that assigns a probability to each outcome. A random element is a function whose domain random PMF is a random element whose codomain is the set of PMFs over fixed space. We say that sequence of random PMFs μ4 converges in probability
probability space. A stochastic process is a sequence of random elements. A
PMF μ if, for all outcomes and >
P((u(()) - u(x) 2 E) +
(1)
as / + co. In the context of random graphs the notion of local convergence in probability is more powerful and useful than, for instance, local weak convergence (Van Der Hofstad 2024 p.58).
2.1 Random Graphs
A random graph G2 is stochastic process {Go heN such that G, is distributed graphs t vertices. This formulation of a random graph as a stochastic process indexed by graph size naturally aligns with the framework of graph limits.
Of special interest to us are the configuration model and the bipartite configuration model. Since we only interested in the limit,
consider version with i..d. degrees. (Van Der Hofstad [014 7.6)
Definition 2.1. Let j be a PMF over N with finite mean. The configuration model CM2(H) is defined on the vertex set (e as follows:
Each vertex U2 is independently assigned degree dę μ..
Each vertex is given de stubs. The stubs are paired uniformly random to form edges, allowing loops and multi-edges, until there are or stub(s) left.
Definition 2.2. Let PLL MR PMFs over with finite means. The bipartite configuration model BCM, (R) is defined on the vertex set (ushe follows:
Partition the nodes into left nodes T. and right nodes R by assigning each node independently
with probability ]pu]+tMpn
B[ga] to L and otherwise to R.
Each vertex i E U is independently assigned degree d; mu for U E {L, R3.
Each vertex is given d, stubs. The stubs in L are matched uniformly at random with stubs in form edges, allowing multi-edges, until there are no more stubs left in
2.2 Watton Trees
Another important graph-valued random process, with applications in population genetics, computer science, and beyond, is the Galton-Watson tree. See for instance (Van Der Hofstad 2024 3.4).
Definition 2.3. A multi-rype Galton-Wautse Watson tree (GWT) W, stochastic process (W,) IeN, where W, is a random rooted tree of depth t. It is parameterized by:
a finite or countable set of types S, with a type-to-feature mapping 8 r> Fgs
an initial PMF μ4 over S,
for each s E S, a PMF μ4 over MultiSet(S)), the set of finite multisets of types.
The process is defined inductively:
Wo consists of root node with type 8, no and feature x,, Ta.
Given W.. generate W441 by extending each leaf node e at depth t:
3

---

For each node sample multiset {si..... Sn ~ Ma.-
For each type s; in the multiset, attach child with type 8; and feature Tz.-
Example 2.4. Suppose $ and I3 Let W be parametrized as follows:
A
A = {
(8(
(A)
A
1 (A)
A (1
otherwise
otherwise
Then W1 has the support and probability distribution depicted in figure
To
Ti
T2
T3
P
To
T1
T2
T3
W1
2/5
1/5
1/6
1/6
Figure I: Support and distribution of W1-
2.3 Local Convergence
We focus on local convergence in probability, which most conveniently defined as the convergence of sequence of random PMFs (Van Der Hoistad 2024 Remark 2.13).
Definition 2.5. For random graph G2 and t N we define the random PMF 2y, B& by
b (B) = -- Ky E V(G.) Bx(v) = BH-
If r converges in probability as t - co, we denote its limit with b4,00- If bk is defined, we call G, BBe-oonvegeett. G, is Bx-convergent for all we call Gg locally tree-like if, for all > 0, as - co,
call G, locally convergent. Furthermore,
PP 1o V(G.) BB( contains cycle)| | 2 E) 0.
Example 2.6. Let G, be random graph that, with probability 1/2, is either set of isolated vertices or cycle on vertices. Then G, does not converge locally:
For every k E N and t 2k + 2. the random PMF by.e on B3 is, with probability 1/2, either 1x, , or 1 where K₁ denotes the singleton graph and P24+1 denotes the path graph of length 2k 1. That is, for any PMF μ on B₁, we have
P(bb..(K)) (K 1/2) 2 1/2 or P((ba,((Patt1) pM(2x 1)1 1/2) 2 1/2.
Theorem 2.7 (Van Der Hofstad (2024)). Let G, CMr(u). Then G. converges locally to GWT. That is, there exists a GWT W. such that for all k E N and B E B₁ (B) = P(W, B).
Remark 2.8. Many important families of random graphs converge locally to Galton -atson trees such as inhomogeneous random graphs, including sparse version of Erdōs-Rényí and stochastic block models. (Van Der Hofstad, 2024, 3.14)
central property of any locally convergent random graph unimodularity (Aldous Lyons 2007), equivalently involution invariance (Hatami et al. 2014). Intuitively, in captures the idea that, statistically, the local limit looks the same from the root as from anywhere else. Whether unimodularity of limit object is sufficient for the existence of random graph with said limit is open in general (Aldous & Lyons 2007] 10.1). For certain classes of limit objects, including versions of Galton Calton-Watson trees, this implication is known (Adous & Lyons 2007 Benjamini et al. 2015).
2.4 Message Passing Graph Neural Networks
Message passing graph neural networks (MPNNs) are class of deep learning models that operate on graphs. MPNNs iteratively combine the feature vector every node with the multiset of feature vectors of its neighbors. Formally, let aggæ and comb; for & [[] be aggregation and combination

---

functions. We assume that each node has associated initial feature vector d. = =x An MPNN computes vector / for every node via the following recursive formula
F (k+11 comb (2 (
EN(o)))).
(2)
where k: E [0]. We call [()) := x the ouiput of the MPNN. Note that, in our setting, MPNNs do not include global readout mechanism. Equation (2) subsumes classical MPNN architectures such as GraphSAGE (Hamilton et al.] (017). GCN (Kipf & Welling 2017), and GIN (Xu et al. 2019). as
well as more abstract valuation mechanisms.
2.5 Color Refinement
The color refinement algorithm (Weisfeiler Leman component of modern graph isomorphism test procedures. Starting with an initial coloring, the algorithm repeatedly updates the color of each vertex by aggregating the colors of its neighbors.
1968 Huang Villar (202b) is an important
Definition 2.9. Given graph G we inductively define sequence of rooted-tree-valued vertex colorings cry:
* cru(v) simply consists of a single root node with feature vector Te.
cr (v) comprises a root node with feature vector 2y and, for each neighbor w of v, the tree crk (w) connected via its root.
For given graph G, color refinement eventuuly stabilizes. That is, there exists kn E N such that
Cr (v) = cr (w) + cra cr+(v) (w:)
for all & 2 ko and e, E V. Cr known the stable coloring of G. Isomorphic graphs have the same stable coloring, although the converse does not necessarily hold.
Example 2.10. Consider the graph G' below. crg(vs) yields the illustrated rooted tree.
1/
cr3(v3)
G
Importantly, color refinement bounds the expressivity of graph neural networks:
Theorem 2.11 (Xu et al. 2019); Morris et al. (2019). For all v, E V and k E N the following are equivalent:
For all k-layer MPNNs f we have f(u) = fww).
(v) crr(w).
2.6 Learning and Data Generation Model
Existing work investigates specific parameterizations of sparse random graphs (Baranwal et al. 2023 fixed graph size distributions (Maskey et al. (2022), or restricted classes MPNNs on dense random graphs -Adam-Day et al. 2024), whereas aim for general characterization of learnability for large graphs. We assume that a large graph G with nodes is sampled from a random graph model Gr, followed by uniform sampling of nodes, which a node classification task is performed, This setting reflects real-world scenarios such as social, biological, and epidemiological networks, where a single large network emerges from underlying random process, and the MPNNs used for node classification.
Our goal is to characterize distributions where learning an MPNN from single, large graph can achieve reliable generalization for node classification tasks. We formalize this by defining probabilis- tic consistency of the empirical risk:
5

---

Definition 2.12. Let G5 be random graph and let fa be an arbitrary node labeling function expressible by (k-layer) MPNN. We say that G, admits probabilistic consistency of the empirical risk with respect to (k-layer) MPNNs if the generalization gap goes to zero with high probability in the large graph limit. That is, for every & > 0 and any (k-layer) MPNN f, we have that
Remp (f, G₂) R(() 2 e) - as + 00,
where the empirical risk and true risk are defined by
Bemp G+) = - Kr G. f(v) + f.(U)),: R() = lim E[ G.)]. t-000
Notably, all locally convergent random graphs admit probabilistic consistency of empirical risk. However, local convergence is not necessary condition. In section 3 we define completely equivalent limit notion, color convergence.
Color Convergence
We aim to characterize and examine the class of random graphs that satisfy probabilistic consisteney of empirical risk with respect to MPNNs. To this end, we reconcile ideas from color refinement and local convergence, and introduce the notion of color convergence. Unlike local convergence, which is defined via distributions over rooted graphs, color convergence is defined via distributions over the set of rooted trees colors given in Definition 2.9
Definition 3.1. The set C2 C Ty of refinement colors of depth A: comprises the isomorphism classes of rooted trees T Tk that occur as the result of color refinement. That trees T such that T cr (v) for some graph G' and vertex v E VG)..
There is convenient structural characterization of the elements of Ct.
Proposition 3.2. A rooted tree T Th belongs to Ck if and only if every node E V(T) that is neither the root nor depth k. there exists child of such that T(c) = T(p)la, where p the parent of u and d is the depth of the subtree (c)).
Example 3.3. The tree T belongs to Cz. Every node at depth has a child e such that T(c) = Tl and every node at depth 2 has child with the same color its parent. T" does not belong to C3: the nodes at depth 7" lack a child e satisfying the condition T(c) T(p)la- Note that cry(T") = T.
T
7
Figure 2: Example demonstrating Proposition 3.2
We can now give analogue to local convergence based on refinement colors: Definition 3.4. For any random graph G, and E N we define the random PMF ck, on Cg by
CK.+ = 1[ e V(G)) cr&(v) - T-
If C converges in probability as t t- co, we denote its limit with Ck If ck,co is defined, we call Ge Ci-convergent. If G2 is Ca-convergent for all i E N we call G3 color convergent.
3.1 Color Convergence and Generalization Gap in MPNNs
In the following example we show that learning MPNNs on random graphs that do not admit color convergence can lead to pathological generalization behavior.
Example 3.5. Recall Example 2.6 where G2 is, with probability 1/2, either a set of t isolated vertices or cycle t vertices. Consider the node label (u) 1 (d,=0), which classifies isolated nodes.
Let denote the constant 0 classifier. Then IP (Rempl (f, Gt) = 0) 1/2 for t N but R(f) 1/2.

---

Example (3.3 shows that there exists data distributions (expressed by the random graph G2 in the example) for which an arbitrarily large sample (measured in graph size) can still lead to a constant non-zero generalization gap. In the following theorem we show that such pathological behavior can not occur for color convergent random graphs, i.e., any MPNN we learn on color convergent random graph generalizes well in the limit with high probability. In fact, we show that for distributions that are not color convergent there always an MPNN for which the generalization gap does not vanish.
Theorem 3.6. Let Ge be a random graph. The following are equivalent:
G is Ce-convergent.
G. satisfies probabilistic consistency of empirical risk with respect to k-layer MPNNs.
The key insight behind the proof of Theorem 3.6 is that color refinement corresponds to maximally discriminative MPNN: If a k-layer MPNN has a non-zero generalization gap we can identify a distinct refinement color which this discrepancy arises. In such cases, Cktt cannot converge in probability. Corollary 3.7. Let Ge be random graph. The following equivalent:
G3 is color convergent.
* Gt satisfies probabilistic consistency of empirical risk with respect to MPNNs.
Corollary 3.7] separates random graph models in terms of MPNN learnability. Sparse SBM, pref- erential attachment models, and inhomogencous random graphs satisfy color convergence, while dense random graphs (like SBM and Erdös-Ree Rényí) with growing average degree are incompatible with MPNN learning.
Example 3.8. Consider node classifier f. which expresses the parity of degree, i.e. f.(e) = 0 d, even, and f- f.( otherwise, and let G, be an Erdós Erdōs-Rényi graph with edge probability * 0. For t E N let ft denote the following node labeling function:
fe(v) - [ (v( (1-A(r)
if d, < otherwise
By construction, Remp (1i, Gt) = with probability 1 for all E N. Since almost all nodes have degree greater than in the limit, have R(fi) 1. This is impossible for color convergent Gy-
3.2 Properties of Color Convergent Random Graphs
Color convergence is a strict relaxation of local convergence:
Proposition 3.9. Let G2 be Byyconvergent random graph. Then G2 is Cy-convergent.
Remark 3.10. There are random graphs which are color convergent but not locally convergent: Suppose G, deterministically, i.c. with probability 1, consists of:
t/3 cycles of length 3, if is multiple of 3,
single t-cylce, otherwise.
cr&(v) is the perfect binary tree BT, of depth & for all & E N, U E G.. Therefore, G₁ is color convergent. On the other hand, G, is not -o-convergent: bı,t Ic, when / a multiple of 3 and 1,, otherwise, where C3 denotes the 3-cycle and Pa denotes the 3-node path.
In the case of tree-like random graphs, however, both notions are equivalent.
Proposition 3.11. Suppose Ge is locally tree-like and Cs Conveenegg Then G2 is Be-convergent and, for E TE, we have
bg,c0 (T) = Cx (Cr=
From a learning perspective, the distribution 6k completely captures the limit behavior of GNNs on given random graph G,. However, not all distributions on Cs can arise such limit. Definition 3.12. A PMF μ C₁ is sofic if there exists random graph G, such that μ Ck
7

---

In the case of local convergence, involution invariance is an important property of sofic PMFs. We define an analogous notion for color convergence. It is going play an important role in the motivation and analysis of our random graph model in Section
Definition 3.13. Let je be PMF Cj and define
dp =
Σ dr (TT).
TEC
dz < oc, we define the edge-type marginal Jl, a PMF on Ch-1: as
p(To: = d
Σ
e N(T) T(c) = -iiHl +T().
TEC
Tlk-1=1o
If d2 < oc and is symmetric call μ involution invariant with finite degree.
We can interpret dy as the average degree and ji as PMF over the pair vertex colors of uniformly chosen pair of connected vertices: their edge-type. Symmetry expresses that the probability of a given edge-type (To. Ti equals that of the inverse edge type (Ti, To). Analogous to local convergence, our notion of involution invariance with finite degree is necessary condition for soficity.
Theorem 3.14. Let 2, p. a sofic PMF on Ck. Then μ involution invariant with finite degree.
Note that E |F(G,)] I. de,, and dı,t - d1,s0 < 0o as 1 oc. That is, Theorem 3.14 immediately implies that color convergent random graphs must be sparse.
Corollary 3.15. Let and suppose G, convergeg Then E E|] e O(t).
4 Refined Configuration Model
We are now ready to introduce our generalization of the configuration model. We show its universality with regard to color convergence, local convergence GWTss and limit behavior of MPNNs.
Definition 4.1. The refined configuration model RCM,(p) is parametrized by:
a finite or countable set of types S, with a type-to-feature mapping 8 -> Ts.
a PMF over S x Multiset(S), the product types and finite multisets of types.
RCM, (1) is defined on {v: {#i)eeq as follows:
For each node v; assign type-multiset pair (8;, A.) js independently at random. 8; determines the type of while A; determines the types of nodes e; may be connected to. Let U. == (va 8; = $} denote the set of nodes which are assigned type s E S.
For each type S, independently generate configuration model U.:
Each vertex with s; is given stub for each occurrence of in A,. The stubs paired uniformly at random to form edges, until there are or stubs left.
For each pair of distinct types 85, * sn. we independently generate a bipartite configuration model between Us, and USR
Each v, E Us2 is given stub for each occurrence of sæ in A,. Each e; E Uap is given a stub for each occurrence of sy in A, Then the stubs U. are matched uniformly at random with the stubs in Us, to form edges, until there are no more stubs left in U., or Usn-
and v. Consider vertices (es 3) and, without specifying the exact distribution, suppose μ assigns type-multiset pairs as illustrated in Figure 3 The generation process occurs in independent steps:
Example 4.2. Let -
Steps & 2: Configuration models are generated nodes of type and respectively.
Step 3: A bipartite configuration model is generated between nodes of type and
The possible results are given Gg and G1. which occur with probability 2/3 and 1/3, respectively.

---

8;
A
0
2
4
Go
G1
Figure 3: From left to right, we have: table containing the assigned types, stubs occurring in steps
and 3, and possible outputs Go and G of the RCM algorithm.
For general distributions μa, (JM, may be poorly behaved. For instance, type could occur with probability 0 as a node type s; but multiple times in A, with high probability. In this case would suggest very different neighborhoods from those observed empirically. We give condition which guarantees local convergence to the distribution that would lead you to expect. Definition 4.3. Let ya be PMF on MultiSet(S) (S) and define
dy
IAI (),
#ES AEMuluSax(S)
If dg < oc, define the edge-type marginal ji, PMF S as
A(so, $1) If du < oc and is symmetric we call involution invariant with finite degree.
1
Σ
Ha A:aeA:a=sa =1 u(so, A).
dy
(EMuhiSen(S)
Given E S, the subgraph of RCM((u) spanned by Ua is simply the configuration model (Mus,((). where
v(n)
Σ
p(s, A)
7,
Σ
(ss A)
Z.
AEMuliSa(S)) (<'EA:s=s)==
AEMuliSeu(S)
Given distinct types SL # sg. involution invariance with finite degree of μ ensures that the bipartite subgraph of (CM,(H) between Us, and Uan the bipartite configuration model BCM (C, H (PL: VR) with
Mp (n) Zan.
1
Σ (EMultSe((S) (E'EA's' d'EAi''=aRB=n =sæ
p(sL,
(R(n)
1
Σ AEMultSa(SS)
p(SR. A)
Zan
(s' =
It follows that (CM,(u) converges locally to the following Maaton-Waatoonn tree:
Theorem 4.4. Suppose G2 = (CM,(H) parametrized by types So. rype-to-feature mapping s -> Is and p. is involution invariant with finite degree. Then Gt converges locally the GWT W. parametrized by rype set S = ({1} So) x So, type-to-feature mapping (8o, 81) + Fs and
po(1, 3) = Z.
po(so, $1) =0
(3)
2, u(s, (l: (p.g) E AB)
7(p.)) E A:p=s
(1.e
(4)
otherwise
!sE A: (5i, 50) M1,01 (A)
Psa.s1 (A)
(5)
Σ (EMutiiSe((S)
{s B: (81, Sp) H ML... (B)
for all so. 81 Sp.
Intuitively, the state-pair (So. $1) each node is aware of its own state $1 E Sy, but also its parent's
state Su E Sg. Root nodes have parent B3). Given root (A) is given by uuss A) conditioned
on = r, and requiring each element (p. q) of A to come with the correct parent type = (4)
Finally, Ma... simply / 1,5 conditioned there being neighbor of type 80
With this, we can construct a refined configuration model that color convergent to any sofic PMF on Cg, and obtain universality of the refined configuration model with respect to MPNN learnability.

---

Corollary 4.5. Suppose y is sofic distribution over Ck. Let S = Cx-1 and consider the PMF on MultiSer(S)) defined as follows:
p(s, A) (T) if there exists T E Ck such that Tkk-1 = and
otherwise.
Then is involution invariant with finite degree and for G. = (CM,(H) we have Ck,oc V. Corollary 4.6. Let Gt be a random graph. The following are equivalent:
G2 satisfies probabilistic consistency of empirical risk with respect to k-layer MPNNs
There exists an involution invariant PMF y with finite degree such that (CM((u) equiva-
lent to Gt in probability for all k-layer MPNNs f. fo. That is, for all 0, as & oc,
P( Bemp (CM, Remp (f, G.) 2 +0
Note that this holds only for fixed k. There may be deep dependencies which model can not capture. However, for Galton- Watson trees we show that this is not the case:
Theorem 4.7. The following are equivalent:
We is the local limit of (RM,(()) for some involution invariant PMF P with finite degree.
W. is a GWT that arises as the local limil of some random graph.
Remark 4.8. Analogously to the configuration and bipartite configuration model, the refined configu- ration model can be sampled in time proportional to the expected number stubs. If dy, < oc, we can sample (CM,(u) in linear time O()) with high probability.
5 Discussion, Limitations and Broader Impact
We have introduced color convergence and shown that characterizes learnability by MPNNs the large graph limit. We have investigated connections between color convergence, local convergence, and Galton-Watson trees. We have introduced the refined sonfiguration model - tractable random graph model which is universally expressive with respect to local limit behavior of MPNNs.
Limitations and Future Work. Although our results fill significant gap the understanding of MPNNs on sparse random graphs they are inherently limited by the expressivity of color refinement and cannot represent features used by more expressive machine learning architectures, such as higher-order graph neural networks (Maron et al. 2019) or models leveraging subgraph informa- tion (Bouritsas et al., 2022). These limitations could, for instance, be addressed by considering graph limits with respect to higher-dimensional versions of the Weisfeiler-Leman algorithm. Furthermore, while we have established a criterion for the learnability MPNNs, we have not established formal guarantees regarding convergence rates enror bounds. This limits our ability to rigorously quantify approximation quality or sample complexity of learning in this setting. A natural direction for future work is to investigate under what conditions this framework guarantces. The refined configuration model defines a generative model for structured random graphs. Its practical utility algorithms tailored to its structure? Additionally, it is worth exploring whether specific restrictions on its parametrization give rise to interesting subclasses.
yield stronger Iearnability
data model requires further investigation: Does it admit natural learning
Broader Impact. Understanding the theoretical foundations of graph neural networks is essential for ensuring their robust and transparent use in high-stakes domains such as drug discovery, recommender systems, and social network analysis. Our framework aims to contribute to the development of principled, interpretable, and responsible machine learning graphs.
6 Acknowledgements
AP acknowledges the support the project VASSAL: "Verification and Analysis for Safety and Security of Applications in Life" funded by the European Union under Horizon Europe WIDERA Coordination and Support Action/Grant Agreement No. 101160022. SM acknowledges the support of FWF and ANR project NanOX-ML (6728)
10

---

References
Abbe, E., Bandcira, A. S., and Hall, G. Exact recovery in the stochastic block model, 2014. URL https://arxiv.orge wttp://og//bbb/aaaa/ae aalaabsssb000 3267
Adam-Day, S., Benedikt, M., Ceylan, I., and Finkelshtein, B. Almost surely asymptotically constant
graph neural networks. Advances in Neural Information Processing Systems, 37:124843-124886, 2024.
Aldous, D. and Lyons, R. Processes on unimodular random networks. 2007.
Aldous, D. and Steele, J. M. The objective method: probabilistic combinatorial optimization and local weak convergence. In Probability on discrete structures, pp. 1-72. Springer, 2004.
Aldous, D. J. Representations for partially exchangeable arrays of random variables. Journal of Multivariate Analysis, 1 11(4):581-59) 1981. ISSN 0047-259X. doi: https::/doi.org/10..000 0047-259X 990099-3. URL hwwp://wwww.siieeeerreetttttt com//sciencee//tticllleeeee 0047259X81900993
Babai, L., Erdos, P., and Selkow, S. M. Random graph isomorphism. SlaM Journal on computing, (3):628-635, 1980.
Baranwal, A., Fountoulakis, K., and Jagannath, A. Optimality of message-passing architectures for sparse graphs. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
URL htw.:http///ee
Benjamini, I. and Schramm, O. Recurrence of distributional limits of finite planar graphs. Selected Works of Oded Schramm, pp. 533-545, 2011.
Benjamini, I., Lyons, R., and Schramm, O. Unimodular random trees. Ergodic Theory and Dynamical Systems, 35(2):359 -33.99333330003 2015.
Bloem-Reddy, B. and Teh, Y. W. Probabilistic symmetries and invariant neural networks. J. Mach. Learn. Res., 21(1), January 2020. ISSN 1532-4435.
Bollobás, A probabilistic proof of an asymptotic formula for the number labelled regular graphs European Jourmal of Combinatorics, 1(4):311-316 1980. ISSN 0195-6698. doi: https://doi. org/ 10. 1016/500195-6698888888000000 pi1/S001566698888003088
URL httpstts:/ wwtp://wwwwwweeeerreeetooo com/ wwcciiineeaatiiiiii
Borgs, C., Chayes, J. T., Dhara, S., and Sen, S. Limits of sparse configuration models and beyond: Graphexes and multi guati-graphexes, 2019. URL httttstt/rriiiii org http//bs/19990 http:/9997..01111
Borgs, C., Chayes, J. T., Dhara, S., and Sen, S. Limits of sparse configuration models and beyond. The Annals of Probability, 49(6) 2873, 2021.
Bouritsas, G., Frasca, F., Zafeiriou, S., and Bronstein, M. M. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):657-668, 2022.
Dort, L. and Jacob, E. Local weak limit of dynamical inhomogeneous random graphs, 2024. URL https://arxiv. org abs/ /2003. 17437
Gamarnik, and Sudan, M. Limits of local algorithms over sparse random graphs. Proceedings of the 5th Conference Innovations in Theoretical Computer Science, ITCS 14, pp. 369-376, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 978 1450326988, doi: 10. 111145/2554777255583111 URL wtw.https:// / http://ooooorg///////// /111//1547/99 2554831
Gori, M., Monfardini, G., and Scarselli, F. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pp. 729-734 vol. 2, 2005, doi: 10. L1100//I.N...00....... 1555942.
Hamilton, W., Ying, Z.., and I. Leskovee, Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.

---

Harris, T. E. The theory of branching processes. Die Grundlehren der Mathematischen Wis- senschaften, Bd. 119. Springer-Veree Berlin, 1963.
Hatami, H., Lovász, L., and Szegedy, B. Limits of bocally-globally convergent graph sequences. Geometric and Functional Analysis, 24(1):269-29) 2014.
Huang, N. T. and Villar, S. A short tutorial on the weisfeiler-Ichmas test and its variants. In ICASSP 2021 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8533-8537. IEEE, June 2021a. doi: 10.1 10w.///cssp377222222199111 http://dx. doi httpooooo....11///AA/5555500
URL
2021 2t...9222....... 9413523
Huang, N. T. and Villar, S. A short tutorial on the weisteiler-Ichman test and its variants. In ICASSP 2021-2021 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 8533-8333880 8537. IEEE, 2021b.
Janson, S. Simply generated trees, conditioned Kalton-Watson trees, random allocations and condensation. Probability Surveys, 9none): 103 252, 2012. doi: 10.1214/1--PS188, URL /tttp::/doo..rr// 10. 1214/11-PS188
Kipf, T. and Welling, M. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Li, H., Wang, M., Liu, S., Chen, P.-Y,, and Xiong, J. Generalization guarantee of training graph convolutional networks with graph topology sampling. In Chaudhuri, K.. Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato. S. (eds.). Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 13014-13051. PMLR, 17-23 Jul 2022. URL https: h/tp:c//e/opo.....//moo mlr www..prrsee wwwpppeeseee//eieeeeeeeeee
htmll
Liao, R., Urtasun, R., and Zemel, R. A {pac)- -bayesinn approach to generalization bounds for graph neural networks. In International Conference on Learning Representations, 2021. URL
https://openreevex. wwwpanrrweeeeeeeeeeeeeeee -i- 222242
Lloyd, J., Orbanz, P., Ghahramani, Z., and Roy, D. M. Random function priors for exchangeable arrays with applications to graphs and relational data. In Pereira, F., Burges, C., Bottou, L., and Weinberger, K. (eds.). Advances in Neural Information Processing Systems, volume 25, Curran As- sociates, Inc., 2012. URL https:ttps:t.. //poceeddi////oeiinggg/ wtw.eeeddiiinnnnnennn.eeee 24bf ee Paper pddf
File/dffcc77562234cc00001111 1444
Lovasz, L. and Szegedy, B. Limits of dense graph sequences, 2004. URL https:t/arxii...... abs/ bbs/math/0408873
Lovász, L. Large Networks and Graph Limits., volume 60 of Colloquium Publications. American Mathematical Society, 2012. ISBN 111-0008218-005-11
Maron, H., Ben-Hamu, H., Serviansky, H., and Lipman, Y. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
Maskey, S., Levie, R., Lee, Y., and Kutyniok, G. Generalization analysis of message passing neural networks on large random graphs In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, 2022. URL https::/ net/ 1arum/idd-991__1weer
Milewska, M., van der Hofstad, R., and Zwart, B. Sir on locally converging dynamic random graphs, 2025. URL pitettss//arxiiee org/ abaa httas//201..00 09623
Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 4602-4600 2019.
Morris, C., Geerts, F., Tönshoff, J., and Grohe, M. WI meet vc. Proceedings of the 40th International Conference Machine Learning, ICML'23. JMLR.org, 2023.
12

---

Oono, K. and Suzuki, T. Optimization and generalization analysis of transduction through gradient boosting and application to multi-scale graph neural networks. Proceedings of the 34th Interna- tional Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829527
Rauchwerger, L., Jegelka, S., and Levie R. Generalization, expressivity, and universality of graph neural networks attributed graphs. In The Thirteenth International Conference on Learning Representations, 2025. URL
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2009, doi: 10.1 109/ 2005605.
Shalev-Shwartz, S., Shamir, O., Srebro, N., and Sridharan, K. Learnability, stability and uniform convergence. Journal of Machine Learning Research, 11(90))2635 2670, 2010. URL http 7/jmlr. arg/papers.a patpers//ii/ssaaseee shaalrezlss html
Tang, H. and Liu, Y. Towards understanding generalization of graph neural networks. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 13674-33719 PMLR, 23-29 Jul 2023. URL https::/ppooceednngs
mlr. (/osss/202/tang222 html
Van Der Hofstad, R. Random graphs and complex networks, volume 1. Cambridge university press, 2014.
Van Der Hofstad, R. Random graphs and complex networks, volume 2. Cambridge university press, 2024.
Weisfeiler, B. and Leman, The reduction of graph to canonical form and the algebra which appears therein. nti, Series, 2(9):12-16, 1968.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful graph neural networks? In International Conference on Learning Representations (ICLR), 2019.
Yehudai, G., Fetaya, E., Meirom, E., Chechik, G., and Maron, H. From local structures to size generalization in graph neural networks. In International Conference Machine Learning, pp. 11975-11986. PMLR, 2021.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our key contribution is the introduction new notion of local convergence and novel random graph model, which are clearly and adequately highlighted in the abstract. The contributions are explicitly summarized in the introduction and substantiated in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss limitations in the discussion section at the end of the paper. In particular, we reflect on assumptions and applicability of our quite theoretical results.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
14

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Proofs of all statements are provided in the appendix. Known results are cited.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [NA]
Justification: There experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
15

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
There is no data or code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
7 //nips. hwcp//blccggudeeeeeeeeeeeeeeeeee
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
There is no training.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
There are no experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
16

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
There are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We read and agree to NeurIPS code ethics.
Guidelines: Both authors have read and agreed to the ethics code.
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss broader impact in the conclusion section at the end of the paper. Since our work is purely theoretical, direct societal impact is limited.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
17

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not with any artifacts.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We do any external assets such code, datasets, models in this paper. All referenced papers are properly cited.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
18

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta
datasets.papersstt
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
We do not release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/cooeemmodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No crowdsourcing or research involving human subjects was conducted in the creation of this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (TRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country or institution) were obtained?
Answer: [NA].
Justification: No crowdsourcing or research involving human subjects was conducted in the creation of this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
19

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer[[NA]
Justification: LLMs were only used for grammar and style checking.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should not be described.
20

---

A Color Convergence Proofs
Definition A.1. The set C2 S Ta of refinement colors of depth & comprises the isomorphism classes of rooted trees T E Th that occur the result of color refinement. That is, trees T such that = (v) for some graph G and vertex U E V(G).
There convenient structural characterization of the elements of Ck.
Proposition A.2. A rooted tree T E Th belongs to Ck if and only for every node (T)) that is neither the root nor at depth k. there exists child of v such that T(c) = T(p)la, where is the parent of v and d the depth of the subtree Tc)).
Proof. We proceed by induction k.
The base case is clear: We have cr cr1 (T) T for all T E Tı, so C1 TT. On the other hand, the condition in Proposition A.2 becomes trivial since every node is the root or of depth 1.
Let's do the induction step in both directions:
Let T Ck+I, that is, T cr (ra) ) for some graph and vertex ra E (G). By construction, we have T(c) E C. for all E (rT)), where rT denotes the root of T. That is, by induction hypothesis all vertices at depth 2 have child as desired. Let ur be vertex at depth 1 in T. By definition of color refinement, there is vertex vg N(rr) such that cr& (vg) = T(er). Since eg and TG are adjacent, vT has a child such that c = T(c). That is, T(c) = T k-1 as desired.
In the other direction, suppose 7' E Tk+1 with all non-root vertices at depth less than k: + having child satisfying (c) = T()) We show that there rooted
T" satisfying cr (T") T.
Each child of the root has a child G, such that (c..) -I For each N(T) consider the subtree T, (w)) where (c,,) has been removed. By induction hypothesis there exists rooted tree TV such that cr (TT) T, Now construct the tree T by taking root node with अ, = 2T and
connecting to the tree Tn via its root for each N(T). Then we have Cr (T") = =
Definition A.3. For any random graph G, and t define the random PMF CK on C2 by
Cr. (T) = 1 E V(G.) cr TH
If C converges in probability as G2 Co-convergent. If G& Cy-convergent for all is E N we call G2 color convergent.
denote its limit with CR If ck is defined, we call
A.1 Color Convergence and Generalization Gap in MPNNs
Example A.4. G2 is, with probability 1/2, either a set of isolated vertices or a cycle on vertices. Consider the node label f. (v) 1 =0) which classifies isolated nodes. Let f denote the constant 0 classifier. Then IP (Reemp (f, G.) 0) = 1/2 for e N but R(f) = 1/2.
Theorem A.5. Let G2 be random graph. The following are equivalent:
Ge is Cy-convergent.
GG satisfies probabilistic consistency of empirical risk with respect to k-layer MPNNs.
We divide the proof into Lemma A.6 which covers the forward implication, and Lemma A.7 and Lemma A.8. completing the equivalence.
Lemma A.6. Suppose G, is C₁ -c-covvergent. G, satisfies probabilistic consistency of empirical risk with respect to k-layer MPNNs.
Proof. Since G, is Ck Co-onveerg, for every T Ct there exists or E [0, 1] such that for all have
(((C,,(T)) - cel s $) +1
as + 00. Let
D = ( Ca f(T) # f(()))
21

---

denote the disagreement set. Then, for every > 0, we have
IP
Σ
(C),(()
Cr) Se -1
TED
and thus
Remp (J, = Σ (T)(T)
R() = Σ CT
TED
TED
and the empirical risk converges.
In the other direction we distinguish two ways in which G2 can fail to be Cg-convergent:
Lemma A.7 captures the random graph failing to be sufficiently deterministic the limit, as in Example A.4
The other mode of failure captures some probability mass escaping to infinity, covered by Lemma(AX This happens for example in dense random graphs. "Tracking" the mass as it escapes infinity with the empirical risk turns out to be more technically involved.
Lemma A.7. Let Gg be a random graph that. Suppose Ck.t does not converge pointwise. That is, such that
there exists T E Ck such that for all [0, 1] there exists
(((c,,(T)) - cl s) 4
as t + Then G2 is does satisfy probabilistic consistency of empirical risk with respect k-layer GNNs.
Proof. Let f be constant 0 and
f.(v) - fi cra(v)= =
else
Then Remp (f, - (T), which, by assumption, does converge.
Lemma A.8. Let G2 be a random graph. Suppose Cg.t does not converge in probability, but converges pointwise. That is, for every T E C2 there exists such that for every > 0
P((ck,((T) - S =)) +1
as t + oc. Then Gt is does not satisfy probabilistic consistency of empirical risk with respect to k-layee GNNs.
Proof. Since C&,t converges point-wise to er [0, but does not converge in probability, the mapping + cr can not define a PMF That is, there exists Eo > such that
Σ TECx
cT
E0-
Let An C Cs denote the set of refinement colors containing no node with more than n children. Define
an,t Σ CT.)(T).
TEAM
and
0,,00 = lim an,t Σ CT.
t-300
TEA
Note that for all N. > 0 have
P( an,ool 5s))
as 00, a2 + Eg + co, and therefore
F(Jan,c (1 Eo))) - <)
22

---

as n - oc, t + oo. Furthermore, for each t E N, choose K; E N, such that
P(aK, 2 1 0.1Ea) 2 0.9.
The key idea now is construct sets Ab.. such that Abn+z \ Abn "tracks" the mass at time bn+1 as is escaping to infinity.
Let N, lo E N such that for all f 2 to we have P (laN, - (1 -o01 & 0.16g) 2 0.9.
Construct the sequence 6; over NN follows:
Let bo = -Kto
For i 1, take b, b such that
P(aks, de OK. 2 0.860) 2 0.8.
Note that choosing such by is always possible since
P(ak.
0.9Ea) 0
as + oO.
Let be the constant ( function and define f. as follows:
(
In N: cru(v) E Abzur1
Abin
[+(v)
else
The disagreement set D is
D U nEN
(Abauti Abza).
Then we have
P(I (f, Gbz )1 2 0.85p)
2 P(aknzuts A2n41 O.Kggn -2n-1
2 0..80) 2 0.8
P(]Remp (f, 2b) S 0.35g)
2 P(NN ban
(aKozn b2242
aKoznu b2nt2) 2 0.3Eg)
P(aN
2 1.180 A a (202
GKKon+t bantz 2 0.85p)
2 P(aN.ban-
2 1.1.o) + P(aK 12.22122
OK b2n42 2 0.8Eo) 1
0.7
n E That is, the empirical risk does not converge.
Corollary A.9 follows immediately from the definitions.
Corollary A.9. Let G2 be a random graph. Then the following are equivalent:
Ge is color convergent.
G. satisfies probabilistic consistency of empirical risk with respect to MPNNs.
A.2 Properties of Color Convergent Random Graphs
Proposition A.10. Let Gt be By-convergent random graph. Then G. is Ce-convergent.
Proof. For Cg define Ar == (B E Be (B) = =T] and
cT Σ bx.o
BEAT
Then T + er defines PMF and, for every
> O, have
(((G,,(T) orl <e)= (1 Σ (br,(()
be,00 (B)) Se
BEAr
as t D0.
23

---

Proposition A.11. Suppose G₁ is a localty tree-like and -ccooverrgnnt Then G. is co-cereentnnt for TE. we have
bk, (7) Ck200 (crl:)))
Proof. Let 2 O. Since G. is locally tree-like, there exists Nire such that for 2 Nuce we have
P (( K G, (v) contains cycle) e/2) 2 5/2. Let T E Cp. Since G. is Cs convergent, there exists N such that for 2 N we have
IP ((ex,((cr((T)) ct.co (T)) & e/2) 2 1 8/2.
Let t 2 max(N (Nrr N). Then we have
(cr, (T)) S 6) 2 - P([[_) H E G2 (r)( = crx(T)) A (B(r) is a tree}} Ck (crk
Since cr (v) = (T)) together with Bx (v) being tree implies B&(v) = we are done.
Definition A.12. A PMF μ on Cg is sofic there exists random graph G3 such that μ Ck, Definition A.13. Let be PMF C2 and define
dn =
Σ
dr p(T).
TECx
d2 < oo, we define the edge-type marginal p, a PMF on Ch as
(TTo.TT)
Σ
e N(T) T(c) = -
dp
TEC
Tlk-1=To
d2 < and j symmetric we call μ involution invariant with finite degree.
Theorem A.14. Let k 2 2, a sofic PMF Ck. Then μ is involution invariant with finite degree.
Proof. Consider a random graph G. such that Cj,oe = p-.
Define the excess bre the PMF on Ca-1 of the following sampling process:
Sample ~ Ck.t-
Uniformly at random chose a node c among the children of the root.
Return T(c).
By construction, (T) is proportional to dr Ck (T)) More concretely, we have
dea, (T) = dr (k)),
for all E Ck-1- Furthermore, 6,00 well-defined PMF and we have ch,((T) - c2 (T) as
I It follows that
do (T) = dr (T)
for all T E Ck-1- That is, d, = dee co.
The symmetry of y then follows from the symmetry of Ck,s, the convergence of Cr.t to and the bound
He N(T) T(c) Till < dr.
for T' E C. with T| =To
Corollary A.15. Let 2 2 and suppose G2 is Ce-convergent. Then B]E[(G:))
Proof. We have (G.)] des and dena E 0(1).
24

---

B Refined Configuration Model Proofs
Definition B.I. The refined configuration model (CM((p) is parametrized by:
a finite or countable set of types S, with a type-to-feature mapping $ > Tea
PMF over S x Multiset(S), the product of types and finite multisets of types.
RCM, (J) is defined on {or hejq as follows:
For each node v assign a type-multiset pair (8;, A.) lr independently at random. 8; determines the type of vi while A, determines the types of nodes v, may be connected to.
For each type S, we independently generate configuration model the vertices of type
-Each vertex with 8; is given stub for each occurrence of in A, The stubs are paired uniformly at random to form edges, until there are or stubs left.
For distinct types s * SR. we independently generate a bipartite configuration model on the vertices of type SL and sgi
Each vertex v; with 8; = sr. assigned to the set L of left nodes. Each vertex vs with 8; sR is assigned to the R if right nodes.
Each 2 E L is given a stub for each occurrence sR in A, Each Us E R is given stub for each occurrence of sz in A,. Then the left stubs matched uniformly at random with the right stubs to form edges, until there are no more stubs left in or R.
Our model is essentially not more complex than combination of configuration and bipartite configu- ration models, which are well-behaved under the conditions given in Definition B.2
Definition B.2. Let μ be a PMF on S x MultiSet(S) and define
dy Σ Σ
|A| (1,
#ES (EMultSe((S)
d, < oo, we define the edge-type marginal μi, a PMF on $2, as
M(so, 81) = d,
Σ A:=
ulso, A).
AEMuhiSa(S))
du < oo and is symmetric we call μ involution invariant with finite degree.
Definition B.2 ensures that, for involution invariant i with finite degree, the subgraph of RCM, (1)) spanned by the nodes U, of given type s E S is equal to CM(v), where
v(n) Z.
Σ
1(s,A) A)
2,
Σ
1(s, A)
AEMultiat(S) {s' =:::'=====
AeMuliSa(S))
and the bipartite subgraph of (CM,(H) between nodes Us, and USR for distinct types 8L, 8n is equal to BCM(vz, vn) with
vr (n)
Σ (EMuliSe((S) (s'EAss' sg 3
p(21, A)
un(n) =
1
Σ
M(sn, A)
Z.r.
Zun
(EMuliSe(SS)
(s'E Ass' =s =n
Given the corresponding results for these models given e.g. in Van Der Hofstad (2024), and due to the independence of the edge sampling procedures, follows that RCM, converges locally the following Galton- Watson tree:
25

---

Theorem B.3. Suppose G2 = (CM((p) parametrized by rypes So. type-to-feature mapping - Is and is involution invariant μ with finite degree. Then G. converges locally the GWT W. parametrized by lype set S = ({1) U So) So, lype-to-feature mapping (80, 81) 2a and
M)(1, Z
Po $1)
(6)
(1.)(A) 2, (ss [g: (p.g) E AB)
((p E A A:pp =
(7)
otherwise
MsS A: A:s= (0) (A)
Ma (A)
(8)
H B: (0),
80) H le s1 (B)
BEMuhiSer(S)
for all so. So.
Intuitively, the state-pair (so, $1) of each node is aware of its state 31 So. but also its parent's state Su E Sg. Root nodes have no parent (6). Given a root r. (A) is given by juss A) conditioned with the correct parent node p
on =, and each element (p. 9) of A has to Mso..; is simply JLL.,, conditioned on there being a neighbor type su (8). For a more detailed intuition refer to Definition B.7 In fact, we shall in Theorem that every GWT that arises as the local limit of a random graph can be represented in this way.
(7). Finally,
Corollary B.4 is direct consequences of Theorem
B.3
Corollary B.4. Let G, (k), S = X and degree,
If p. is involution invariant with finite
G. locally tree-like.
(T),o(T) = p(rT, : UEE ((T) for all Ct.
Proof. Ge being tree-like is clear. Furthermore, we have
(T) = (o(L, Mi,er ((TT, xe) v e -(T)))= [ UUE N(T)))
for T' E C₁.
Corollary B.5. Suppose is sofic distribution over Ck. Then there is a refined configuration model
G, ( with rypes S Ck-1 such that Ck,ce
Proof. Let
((s, A) = (TT) if there exists T Cs such that T = s and (T(c) ((T))) = otherwise
By Corollary B.4 for every > O, we have
(t 1/ E (G.)) Keu 1y E N(;))) } = A:)1 2 - +1
as t + co. Setting the type-to-feature mapping - Fss we obtain
P Pt He V(Gi) ((rk-1(U,)) uy E N(.)) A,) 2 1 - s) +1
as co. It follows that 0k v.
Corollary B.6. Let G2 be random graph. The The following are equivalent:
Gt satisfies probabilistic consistency of empirical risk with respect to k-layer MPNNs
There exists an involution invariant PMF μ with finite degree such that (CM((u) equiva- lent to Ge in probability for all k-layer MPNNs f. That is, for all > 0, as t + oc,
P( Pee (f, (CM,(()
Remp Go) 2 =)
26

---

Proof. Suppose G; satisfies probabilistic consistency of empirical risk with respect to k-layer MPNNs. By Theorem A.3 exists PMF v over C₃ such that Ck,oc. v. By (yyAA.14hh this PMF is involution invariant with finite degree. By Corollary th5 exists an involution invariant distribution l with finite degree such that setting G₁ (CM((() yields CR,oc = 2,00 Let f. fa be any k-layer GNN and define
D = (TTEC f(T) & f((T))
the disagreement set. Since C1200 = 2,00 we have
(e RCM,(() - Remp (J, G.) 2 2))=1 PP Σ
(C),(T) - Cx,((T)) 28 40
TED
as oo.
Suppose on the other hand there exists an involution invariant ju with finite degree and G² = ( such that for all > O and k-layer MPNNs f,
P( Pomp (f, RCM.(u)) - Remp (f, 2s) IP E
(dc,(()) -x,,))))).((()) 2 +
IED
as + co. Then, in particular, this is true for constant 0 and fx the indicator function of T. That is, for all T Ck and
O, have
P (((),,(T)) Cx 2 e) +
as + co. Since G² = ( is color convergent, C,, converges in probability to 6,,00*
For the final result we need show that every GWT can represented as in Theorem B.3 Definition B.7. A simplified unimodular GWT W is GWT parametrized by S,Ho {uy)Ses such that
there is base type So such that S= ({1) So) x So, that is, each node's type records its own base type and its parent's 's base type (1. in the case of the root).
The root distribution Ho is supported on nodes type (L, s). ie., (o $1) = 0 if su * T.
For all so, 81 E So, the offssring distribution Mso..s is supported only on multisets of children of the form (((1), g:) 1 meaning every child has parent type s
Ma (A)
(p, with p + 81.
Additionally, the following two conditions hold:
(Root-to-child consistency) For all 8o * 1., the pmf Mlso.sy coincides with the conditional offspring distribution root with type (1) and conditioned on having a child of type (s1, so), that is
H E A A:s So) M.L.,, (A)
Mag (A)
Hs E B: (81, 8p) H p1.. (B)
BEMaltiSe((S))
(Edge-type symmetry) Let the expected degree of the tree
dw = Σ ΣΣ14 |A| (o(1.)) (A).
sESp A
and define the edge-type marginal
A(su, $1) = dw Σ IlaaA:a== si Ho(d, 11 aBaEA).
Then we require that jú symmetric:
p(so, $1) pi(s1, 8o).
27

---

Note that Su, fo. {ar .s) Jees, completely determine simplified unimodular GWT. The GWT Theorem[B.3 an simplified unimodular GWT edge-type symmetry a direct consequence of involution invariance with finite degree.
Lemma B.8. Suppose μ is involution invariant with finite degree. Then (CM converges locally simplified unimodular Galton-Watson tree.
In fact, Definition B.7 exaatly captures the local limits of refined configuration models. Lemma B.9. Suppose W, is simplified unimodular GWT determined by So- Po- (s)
Then We the local limit of RCM+(H) where μ is involution invariant with finite degree.
Proof. Define the distribution μr So MultiSet(S))
u(s, A) = #o( s) Mat.s (s) A)).
Involution invariance with finite degree of follows directly from edge-type symmetry of W Applying Theorem B.3 we recover Wt the local limit of RCM(())).
All that's left is to show that every sofic GWT equivalent to simplified, unimodular GWT.
Lemma B.10. Suppose W is a Galton Watson tree that is the local limit of a random graph. There exists simplified unimodular Galton Watson tree We that defines the same random process.
Proof. Suppose W is parametrized by S', M/- (pabees and feeetto- mapping s + x',, and is the local limit of G2. Define
So = Es 16(s) > 0),
the set of vertices which appear with positive probability at the root.
Due to unimodularity Aldous Lyons 2007)) the nodes that appear as the neighbors of the root with non-zero probability, must themselves appear as the root with non-zero probability well. Therefore this set of types is sufficient. Let us make this more formal:
Let μ4 denote the PMF of the conditional distribution of W given that the root has state Fix an total order 3 on Sg- For every E Su, there a distribution D over MultiSet(Su) such that, for every & E N, sampling T p4 equivalent to the following process:
Consider singleton graph comprising the root with feature z, 2.
Sample multiset s0 ... 8n v²,
Sample Bp...., Bn p Us of B, such that Tey = Zr and all the balls agreeing on the neighborhood of u, that is, BB-2(v,) 22-2(1)) for i E + 1].
1 conditioned the existence of neighbor
Connect the graphs B, to the and return the resulting tree.
via the neighbor whose existence conditioned on,
Setting po(1,, = (s) and
M1.s (A)) { v (p::((:0)
(p.9) AB) V(p.g) A:p=
otherwise
for s E So we obtain the desired simplified unimodular GWT.
Theorem B.11 now follows directly from Lemma B.8 Lemma B.9 and Lemma B.10
Theorem B.11. The following are equivalent:
W. is the local limit of RCM,(u) for some involution invariant PMF p with finite degree.
W, is a GWT that arises as the local limit of some random graph.
28


Reviews:
[{"review_id": "hHsXohnfQs", "reviewer": "Reviewer_1zSd", "summary": "The paper introduces a notion of \"local convergence\" that they call \"color convergence\" and also proposes what the authors call the \"refined configuration model\", which is a variant of the configuration model used in random graphs. This can be motivated as follows to an ML audience: one is often interested in understanding if a local aggregation algorithm, such as a graph neural network based on message passing, ends up \"performing well\" on a graph drawn from a probabilistic model. Here, one can ask if there is a general characterization under which the \"recovery\" up to an \\epsilon error in the loss objective occurs with high probability. For procedures that fall under the umbrella of the Weisfeiler-Leman algorithm (including GNNs), the authors show that \"color convergence\" provides such a characterization.\n\nColor convergence is a local-convergence style property that is based on the distribution of trees obtained via a color refinement algorithm. The main result is then that if a random graph family is color convergent, then with high probability, an MPNN procedure on a graph drawn from the family achieves a small generalization gap (difference between the true risk and the empirical risk).", "questions": "Please comment on each of the points in the weaknesses section. Also, could you discuss more on the significance of some of the results like 3.13 and the definitions around it?", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- The problem of achieving small generalization gap via GNN type procedures on classes of random graphs is an important one, as it gives insights into when one can expect these methods to work well on real graphs.\n- The results obtained are quite interesting, assuming they can be motivated appropriately to an ML audience.\n- The variant of the configuration model seems interesting as well.\n\nWeaknesses:\n\n- The biggest concerns about the paper are about the writing and how it does not make the case for \"fit\" for an ML conference like NeurIPS. Right now, the paper reads like one that is of interest to the graph limits community, but perhaps not much beyond.\n\n- Even though the paper gives a few concrete examples of random graph models, color refinement, etc., the writing is far from clear. Suppose we focus on applications of Theorem 3.6, are there specific graph classes on which GNN approaches were not known to be consistent but the new result sheds light? (I imagine there are, but it would be good to see examples.)\n\n- The authors should also say if there are any convergence guarantees. The literature on recovery in SBMs, for example, gives concrete bounds on the recovery error (~ \\sqrt{t} misclassifications, for example). Are such results possible in the general case?\n\nOverall, I feel the paper needs a much more accessible exposition for a NeurIPS audience. But this said, the results do seem interesting if presented in the right way.", "was_revised": true, "final_justification": "I have read the authors' rebuttal, and while they acknowledge and address the concerns to a certain extent, there are still gaps that require significant re-writing imo. I prefer to keep my score.", "rebuttal": "We thank the reviewer for their thoughtful comments and for finding our work interesting. We address the main concerns raised by the reviewer below.\n\n**[W1&2] We will highlight relevance and improve accessibility to ML community.** We agree with the reviewer that our contributions to the ML community, i.e., **a complete characterization of MPNN learnability**, should be further highlighted to make the paper more appealing and accessible. We propose the following changes to this end:\n\n1. **We will highlight the broader context to our characterization of MPNN learnability**. In the introduction and Section 2.6, we will clearly position our work within the context of commonly used random graph models for MPNN analysis. Existing work investigates specific parameterizations of sparse random graphs [1], or fixed graph size distributions [3], or restricted classes of MPNNs on dense random graphs [4], whereas **our work gives a general and complete characterization of random graph models on which fully expressive MPNNs can be learnt**.\n\n2. **We will discuss that Theorem 3.6 generalizes and contextualizes existing machine learning results** like [1], [2] and [4]. In particular, we will highlight that Theorem 3.6 separates the following widely investigated random graph models in terms of MPNN learnability:\n+ **Learnable.** Sparse SBM, preferential attachment models, inhomogeneous random graphs, and RCM parametrizations satisfy color convergence. Our results provide consistency guarantees for these random graph families, significantly generalizing previous results [1].\n+ **Not Learnable.** Dense random graphs (like SBM and Erdős-Rényi) with growing average degree are incompatible with MPNN learning. This result expands on the impossibility of size generalization [2], previously only identified for specific random graphs, and adds a broader context to results on limit behavior of MPNNs [4] for such random graphs.\n\n3. We will expand Section 3.1 with a natural example (such as dense Erdős–Rényi or SBM) on how **MPNN learning fails on random graphs with growing expected degree**. \n\n\n**[W3] Convergence Rates.** The generality of our results critically relies on taking a non-parametric approach (note that $\\mu$ in Definition 4.1 is an arbitrary distribution with infinite domain). However, this approach precludes using standard parametric techniques, such as those for community recovery in SBMs. \n**The RCM can encode diverse limit behaviors**, e.g. sparse SBM if $\\mu$ is multivariate Poisson, bipartite configuration model if there are 2 types and $\\mu(s, A) = 0$ for $s\\in A$, and so on. **This flexibility naturally leads to different convergence phenomena, which can exhibit considerable complexity,** for example when the distribution $\\mu$ has heavy tails. Analysing convergence rates in general and for specific parameterizations constitutes interesting future work. \n\n**[Q1]** Regarding Theorem 3.13, **involution invariance and finite expected degree are fundamental to local convergence theory [5]. We extend their validity to the weaker setting of color convergence.** Furthermore, Corollary 3.14 provides a convenient criterion for color convergence. We will add a remark highlighting this fact.\n\n[1] Baranwal, A., Fountoulakis, K., & Jagannath, A. (2023). Optimality of message-passing architectures for sparse graphs. *Advances in Neural Information Processing Systems, 36.*\n\n[2] Yehudai, G., Fetaya, E., Meirom, E., Chechik, G., & Maron, H. (2021). From local structures to size generalization in graph neural networks. *38th International Conference on Machine Learning.*\n\n[3] Maskey, S., Levie, R., Lee, Y., & Kutyniok, G. (2022). Generalization analysis of message passing neural networks on large random graphs. *Advances in neural information processing systems, 35.*\n\n[4] Adam-Day, S., Benedikt, M., Ceylan, I., & Finkelshtein, B. (2024). Almost surely asymptotically constant graph neural networks. *Advances in Neural Information Processing Systems, 37.*\n\n[5] Aldous, D., & Lyons, R. (2007). Processes on unimodular random networks. *Electronic Journal of Probability, 12.*"}, {"review_id": "iPl4vV6V4U", "reviewer": "Reviewer_X2fm", "summary": "Local convergence characterizes the neighbourhood distribution around a randomly chosen node in the large‑graph limit, providing several structural details. This is exploited by the Weisfeiler–Leman (WL) color‑refinement algorithm that bounds the expressive power of Message Passing Graph Neural Networks (MPNNs). Using this observation, they propose color convergence, a refinement that facilitates the analysis of MPNNs through the framework of local convergence. \n\nThey prove that a random graph sequence is color-convergent if and only if it satisfies probabilistic consistency of empirical risk with respect to k-layer MPNNs. They then designed the Refined Configuration Model (RCM) that is universal with respect to color convergence. It is a type-labelled extension of the classical configuration model. This framework helps them develop structural results for locally tree-like graphs. Through this framework they show that colour-convergent sequences correspond precisely to local limits given by Galton–Watson trees.", "questions": "Typo: not is written twice in Remark 2.9\n\nA line before Corollary 3.14 explaining it would be nice. Took me a while to see.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- Bridging WL-based expressivity analysis of GNNs with graph-limit theory is new and interesting. The idea of using Color convergence for this is a good balance. It is weaker than local convergence but captures learnability by MPNNs.\n- The writing is clean. Related work is covered well and defintions are clearly stated with examples. \n\n\nWeakness:\n- They do not give intutions for their proofs.\n- No formal guarantees regarding convergence rates or error bounds. \n- Given that colour convergence is a new framework they are proposing aimed at explaining MPNN behaviour, even a small controlled simulation would greatly strengthen the paper.", "was_revised": true, "final_justification": "I am updating my score as the issues I raised were addressed in the rebuttal.", "rebuttal": "We thank the reviewer for their insightful comments and for appreciating our work. \n\n**[W1]** We acknowledge that space constraints limited our explanations. We plan to use the extra page in the final version to provide additional intuition.\n\n**[W2]** Please see reply to reviewer 1zSd, W3. **Color-convergence and RCMs are  very general and broad frameworks which can potentially encode very diverse convergence phenomena**. Analyzing convergence rates and error bounds for different parameterizations and in general will form interesting future work.  \n\n**[W3]** **Empirical evidence for the impossibility of learning on random graphs that are not color convergent exists in literature for restricted cases [2, 4]**. We will highlight existing empirical evidence for Theorem 3.6 (also see reply to Reviewer 1zSd). \nGenerality of our results critically relies on taking a non-parametric approach. Any simulation would ultimately require arbitrary parametric choices, which may not be representative of our more general results.\n\n**[Q1]** We thank the reviewer for noticing the typo and will fix it in the final manuscript.\n\n**[Q2]** We thank the reviewer for directing our attention to this. We will add a sentence before Corollary 3.14 connecting the finiteness of $d_\\mu$ to the boundedness of average degree, and thus to the linear growth of edge count.\n\n[2] Yehudai, G., Fetaya, E., Meirom, E., Chechik, G., & Maron, H. (2021). From local structures to size generalization in graph neural networks. *38th International Conference on Machine Learning.*\n\n[4] Adam-Day, S., Benedikt, M., Ceylan, I., & Finkelshtein, B. (2024). Almost surely asymptotically constant graph neural networks. *Advances in Neural Information Processing Systems, 37.*"}, {"review_id": "SCTBksglAa", "reviewer": "Reviewer_HKEY", "summary": "This paper studies the local limits of sparse random graphs, proposes a notion of local convergence, and also a random graph model. The proposed color convergence generalizes the local convergence and draws a strong relation to the learnability of Message Passing Graph Neural Networks (MPNN). Color convergence is defined based on the classic color refinement algorithm by Weisfeiler and Leman. The proposed Refined Configuration Model (RCM) generalizes the configuration model and it is universal with respect to coloar convergence and local convergence to Galton-Watson trees.", "questions": "I am curious about is there any arguments about weak local limits we can make using the proposed framework? By weak local limit, I am referring to the Definition 2.1 in [1] for example.\n\n\n[1] Berger, Noam, et al. \"Asymptotic behavior and distributional limits of preferential attachment graphs.\" The Annals of Probability (2014): 1-40.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "1. This paper is well-organized and easy to follow. Key concepts are defined and delivered clearly. There are also quite a few figures that enhance the understandability.\n2. The proposed color convergence notion exactly capture the learnability of MPNN in the sense that there is a necessary and sufficient condition on whether a random graph satisfies probabilistic consistency of empirical risk with respect to $k$-layer MPNNs. Although this is not a very strong consistency guarantee, it opens up future directions on deriving stronger guarantees such as specific error bounds.\n3. RCM generalizes the commonly studied configuration model. It has potential to be studied in many follow-up works that concern with MPNNs or need a more general random graph with a nice local limit structure.", "was_revised": true, "final_justification": "My opinion on this paper is very positive and the rebuttal of the authors to my question is satisfactory. I keep my score as it is.", "rebuttal": "We appreciate the reviewer for finding our work well-organized and easy to follow, and thank them for highlighting its key features in the review. \n\n**[Q1]** Note that color refinement $\\mathsf{cr}\\_k$ defines a one-to-one mapping between the set $\\mathcal{T}\\_k$ of rooted trees of depth $k$, and the set $\\mathcal{C}\\_k$ of refinement colors of depth $k$. Hence, for each color convergent random graph $G\\_t$ its limit distributions of refinement colors $c_{k, \\infty}$ give rise to a unique random rooted tree $W_k$, such that the probability $c_{k, t}(T)$ converges to $P(\\mathsf{cr}\\_k(W_k) = T)$ as $t\\to\\infty$ for every refinement color $T\\in\\mathcal{C}_k$. This is the strongest possible characterization: Since non-isomorphic neighborhoods can share the same refinement color, **a local weak limit in terms of isomorphic neighborhoods may not exist**.\n\nWhile the example in Remark 3.9 fails to converge locally according to our definition (i.e. convergence in probability), a local weak limit (i.e. convergence in distribution) still exists. We thank the reviewer for directing our attention to this. **We will strengthen Remark 3.9 to also address local weak convergence** by redefining the random graph $G_t$ as follows:\n\n+ If $t$ is a multiple of $3$, $G_t$ deterministically consists of $t/3$ different $3$-cycles.\n+ Otherwise, $G_t$ deterministically consists of a single $t$-cycle.\n\nAs before, $G_t$ is deterministically 2-regular and therefore color convergent. However, a local weak limit no longer exists."}, {"review_id": "8aKDvA9hPx", "reviewer": "Reviewer_wyHK", "summary": "The paper proposes color convergence, a new graph-limit notion aligned with 1-WL color refinement, and shows it is equivalent to uniform generalization of every $k$-layer MPNN on node-classification tasks. To generate all such limits, the authors introduce the Refined Configuration Model, a type-augmented configuration model that subsumes E-R, SBM, and classical configuration graphs while remaining locally tree-like.", "questions": "Apart from the comments in the weakness section, I have the following questions:\n1. The framework focuses on node classification. Could the framework be extended to provide insights into other graph learning tasks?\n2. How do the authors expect one would fit the parameters (e.g., the PMF $\\mu$) from an observed real-world sparse graph? Are there consistent estimators, perhaps leveraging methods of moments on refinement-color counts, that could be used in practice?\n3. Why only 2 colors in this work? Could the authors extend their framework to multiple colors?", "limitations": "Yes.", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. First limit concept tied to MPNNs with bridge between graph limits and GNN learning theory.\n2. Proofs of equivalence, universality, and involution-invariance look reasonable, although I did not check the proofs carefully.\n\nWeaknesses:\n1. Applications of this work are unclear to me.\n2. The contribution is purely theoretical; no empirical or synthetic experiments are provided.", "was_revised": true, "final_justification": "The authors' response cleared my doubts, and I now understand the potential applications of this work. Therefore, I raised my score to 4.", "rebuttal": "We thank the reviewer for their feedback and interesting questions.\n\n**[W1&2]** A major contribution of **our work is furthering the understanding of (learnable) graph data models in the context of MPNNs**. This required taking an abstract, non-parametric approach. Concrete experiments would ultimately require arbitrary parametrization choices, which may not be representative of our more general results. We will highlight the relevance of our work to the machine learning community (see reply to reviewer 1zSd, W2) and point out existing empirical evidence for our results (see reply to reviewer X2fm, W3).\n\n**[Q1]** Many approaches to tasks such as graph classification and link prediction utilize message-passing layers within their architectures, and **our theoretical results apply to any such message-passing components**. Extending our results to end-to-end analysis of such composite architectures is an interesting direction for future work. \n\n**[Q2]** The RCM exhibits very diverse behavior depending on the parametrization (e.g. sparse SBM if $\\mu$ is multivariate Poisson, bipartite configuration mode if there are 2 types and $\\mu(s, A) = 0$ for $s\\in A$, etc.). In our view, the choice of parametrization should be informed by the application domain. Molecular structures may benefit from discrete distributions reflecting their rigid topology. Citation networks and other growing graphs suggest counting distributions, though whether Poisson or alternatives like power-law distributions are optimal remains context-dependent. Some applications may require infinite type spaces or mixed approaches. Investigating specific parametrizations and their properties, e.g. existence of consistent estimators, represents important future work.\n\n**[Q3]** The two-color examples in the paper were chosen only for illustrative purposes. **All results are stated for finite or countably infinite color spaces**."}]

Author rebuttal:

Meta-review: The paper introduces a variant of Benjamini-Schramm convergence of sparse graphs, and relates it to node classification behavior of message passing graph neural networks.

This is an interesting idea and the paper is well-written. There are some minor weaknesses; in particular, there is no experimental valuation, which is not a strict requirement for NeurIPS, but as mentioned in the reports, this paper may have benefited from including it. Overall, however, this is interesting work and the reviews and scores support publication.
Decision: Accept (poster)