On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Model

We thank the reviewer for their feedback and interesting questions.

[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).

[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.

[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.

[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.

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.

[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.

While 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:

• If $t$ is a multiple of $3$, $G_t$ deterministically consists of $t/3$ different $3$-cycles.
• Otherwise, $G_t$ deterministically consists of a single $t$-cycle.

As before, $G_t$ is deterministically 2-regular and therefore color convergent. However, a local weak limit no longer exists.

We thank the reviewer for their insightful comments and for appreciating our work.

[W1] We acknowledge that space constraints limited our explanations. We plan to use the extra page in the final version to provide additional intuition.

[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.

[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). Generality 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.

[Q1] We thank the reviewer for noticing the typo and will fix it in the final manuscript.

[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.

[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.

[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.

We thank the reviewer for their thoughtful comments and for finding our work interesting. We address the main concerns raised by the reviewer below.

[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:

1. 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.

2. 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:

• 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].
• 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.

3. 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.

[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. 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.

[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.

[1] Baranwal, A., Fountoulakis, K., & Jagannath, A. (2023). Optimality of message-passing architectures for sparse graphs. Advances in Neural Information Processing Systems, 36.

[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.

[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.

[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.

[5] Aldous, D., & Lyons, R. (2007). Processes on unimodular random networks. Electronic Journal of Probability, 12.