acceptodds
Under review as a conference paper at ICLR 2027

Walk Counts and the Depth of Graph Neural Networks

Abstract

Message-passing neural networks distinguish vertices exactly as far as color refinement does, layer for layer, so on graphs whose stable coloring has classes they can need layers. Global filters, such as spectral, diffusion and Katz filters, let every layer see the whole graph, and how much of this depth they remove has been open. We prove that they halve it: with any filters that are polynomials in the adjacency matrix, arbitrary update functions and unbounded width, exactly layers are needed in the worst case. The layers that remain are spent on naming, since a linear filter can separate color classes without producing their indicator vectors and only a nonlinearity supplies them. The depth that full expressive power costs thus counts nonlinear layers, however far each layer sees.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
color refinement, Weisfeiler-Leman, graph neural networks, message-passing neural networks, expressive power, depth

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_jxwbOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

Color refinement separates vertices whenever their numbers of neighbors differ in a class of the current coloring. Message-passing neural networks have the same distinguishing power as color refinement: with t layers, they can distinguish only vertices that are also distinguished after t refinement rounds. Hence, they may require m-1 layers on graphs with m stable coloring classes. With global filters, each layer has access to information from the entire graph. It has been open to which extent global filters reduce the number of layers. This paper proves that they halve it. More precisely, the authors proof that floor(m/2) is an exact worst-case bound.for filters given by polynomials in the adjacency matrix. They further prove that a single fixed Katz filter kept across each layer suffices to reach this bound. They also show that adding layers does not increase the distinguishing power of linear networks with arbitrary polynomial filters. Likewise, after a single global filtering stage, further layers that process vertex features separately cannot add distinguishing power. The authors also prove lower bounds on the number of alternations between filtering and nonlinear operations needed to obtain the full distinguishing power of color refinement.

Critical strengths

The main result is interesting because it contradicts the intuition that global information should remove the need for depth and the explanation through deficiency is elegant. Moreover, the bound is the exact worst-case, (not merely an asymptotic bound), together with a matching lower-bound construction. The lower bound’s strength is that it survives arbitrary polynomial filters, unrestricted width and arbitrary updates. So it identifies a limitation beyond locality.

Critical weaknesses

The paper is well-presented and seems to be sound. There is one minor error in the appendix: On p. 16, lines 819–821, the paper says that on the disjoint union of a triangle and a hexagon the distance-two matrix is J-I-A and is a polynomial in A. Since both statements are fasle, the claim most likely is intended to refer back to the earlier seven vertex graph.

Questions for authors

none

1 comment
AuthorsOpenReview ↗

Response to Reviewer jxwb

Thank you for your careful review and for the sharp eye that caught the slip in Appendix B.1. As you suspected, the sentence on page 16, lines 819–821, was meant to refer to the seven-vertex graph introduced earlier in the same paragraph. On that graph the distance-two matrix equals J−I−AJ-I-A, because the graph has diameter two, and J−I−AJ-I-A is a polynomial in AA, because the graph is connected and regular.

On the disjoint union of a triangle and a hexagon neither statement holds, as you point out. The corrected passage (page 17, lines 889–894 of the revised paper) now uses this graph to show that the distance-two matrix of a graph need not be a polynomial in AA. Indeed, the indicator vectors of the triangle and of the hexagon are eigenvectors of AA for the same eigenvalue 22, so every polynomial in AA multiplies both by the same number, whereas the distance-two matrix of this graph sends the first to zero and doubles the second. The passage belongs to the discussion of the scope of the model, and the error affects no result or proof in the paper.

Your review also noted that the bound is the exact worst case, with a matching construction. In the revised paper we show that the bound for filters from the degree algebra D\mathcal D, to which the degree-normalized filters belong, is exact as well (Theorem 1(b) and the new Proposition C.3).

We hope that the correction settles the point you raised, and we would be glad to answer any further questions. Thank you again for the effort and expertise that you have devoted to our work in this review. Your comment has made it a better paper.

Reviewer_Jh2mOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the depth required for graph neural networks with global polynomial filters to achieve the distinguishing power of one-dimensional Weisfeiler-Leman (1-WL) refinement. The authors introduce an iterative walk-refinement framework that uses global walk counts to progressively distinguish vertex classes and establish that the minimum network depth corresponds to the number of walk-refinement stages. They prove that, for graphs whose stable 1-WL coloring contains mm classes, networks with arbitrary adjacency-polynomial filters and unrestricted update functions require exactly ⌊m/2⌋\lfloor m/2\rfloor layers in the worst case, compared with m−1m-1 layers for conventional message passing. This bound is shown to be tight through an explicit construction of graphs exhibiting the maximum walk-refinement depth. The paper further examines degree-normalized filters, linear and decoupled architectures, and the role of nonlinear operations in representing color classes. Finally, the authors introduce a multiplicative depth characterization that relates alternating filtering and nonlinear operations to graph distinguishability, providing theoretical insights into why global propagation alone cannot eliminate the depth required to attain full 1-WL expressivity.

Critical strengths
  1. The paper addresses an important question about how global graph propagation affects the depth required to achieve the expressive power of 1-WL. While the expressivity limitations of message-passing GNNs are well understood, considerably less is known about the minimum depth required when each layer can access global structural information. Establishing an exact worst-case depth of ⌊m/2⌋\lfloor m/2\rfloor for adjacency-polynomial filters is a potentially significant theoretical result. The distinction between separating vertex classes and explicitly representing their indicators provides an interesting explanation for why global propagation cannot completely eliminate network depth.

  2. The paper develops a clear connection between graph refinement, matrix algebras, walk counts, and the depth of neural computation. The proposed walk-refinement framework provides a principled way to characterize the information available to polynomial-filter networks at each layer. I particularly appreciate the use of deficiency to quantify the difference between separating classes and representing their indicator vectors. The resulting accounting argument gives an elegant explanation for the upper bound, while the paired-tail construction establishes tightness rather than relying only on an asymptotic lower bound.

  3. An interesting aspect of the work is that the theoretical framework covers a broad class of global filters, including polynomial, diffusion, and resolvent-based operators. The analysis of linear and decoupled networks further clarifies why repeated linear propagation alone does not necessarily improve distinguishing power. The discussion of degree-normalized filters and multiplicative depth also provides useful insights into the respective roles of global propagation and nonlinear operations.

  4. The main theoretical contributions are presented in a reasonably clear order, starting with the network model and walk refinement, followed by the exact depth characterization, tight constructions, and architectural implications. Figure 1 provides a useful explanation of the difference between message-passing depth and global-filter depth. The appendices contain detailed proofs of the supporting propositions, quotient constructions, normalized-filter results, and multiplicative-depth characterization, which strengthens the mathematical presentation.

Critical weaknesses
  1. The exact-depth characterization relies on a highly permissive network model. The exact worst-case depth of ⌊m/2⌋\lfloor m/2\rfloor is established under assumptions that allow arbitrary update functions, unbounded feature widths, and graph-dependent filters (Definition 1). These assumptions are stronger than those of practical GNNs, which typically use shared parameters, fixed widths, and restricted nonlinearities. In particular, the upper bound relies on producing exact class-indicator vectors, which may require additional capacity in standard neural architectures. It is therefore unclear whether the same depth guarantee can be achieved by practical spectral or polynomial-filter GNNs without substantially increasing their complexity.

  2. Numerical stability of exact walk refinement remains unclear. Proposition 2 shows that a suitably chosen Katz filter can reproduce an entire walk-refinement stage. However, this relies on exact distinctions between weighted walk counts and an injective update function that maps distinct representations to class indicators. The proposed attenuation parameter (ζG=1/(Δn+Δ+1))(\zeta_G=1/(\Delta^n+\Delta+1)) decreases as graph size or maximum degree increases, potentially making contributions from longer walks extremely small. Since practical implementations use finite-precision arithmetic, it is unclear how reliably these distinctions can be recovered. An analysis of numerical separation margins and precision requirements would strengthen the practical interpretation of the result.

  3. The worst-case lower-bound construction has limited demonstrated generality. The tightness result relies on a specially designed paired-tail quotient matrix, which is realized as a connected simple graph with (2m2+2m2m^2+2m) vertices (Proposition C.1). Although this construction establishes the theoretical worst-case bound, it is unclear whether similar depth requirements arise in more common graph families, particularly sparse, bounded-degree, or irregular graphs. The smaller bounded-entry examples in the appendix cover only specific values of mm. Further analysis of the structural properties responsible for near-extremal refinement depth would help establish the broader relevance of the lower bound.

  4. The computational cost of global filtering is not reflected in the depth comparison. The paper shows that global polynomial filters reduce the worst-case number of layers from m−1m-1 to ⌊m/2⌋\lfloor m/2\rfloor. However, a global filtering layer can be considerably more expensive than local message passing, particularly when computing high-degree matrix polynomials or evaluating the Katz resolvent (I−ζA)−1(I-\zeta A)^{-1}. Therefore, fewer layers do not necessarily translate into lower overall runtime or memory requirements. A comparison that accounts for filter computation, nonlinear updates, and total computational complexity would help clarify the practical efficiency of the proposed depth reduction.

  5. The depth characterization does not directly reflect downstream graph learning requirements. The main results concern the minimum depth needed to recover the complete stable 1-WL coloring from constant initial features. While this is a well-defined theoretical objective, practical graph learning tasks may require only a subset of these structural distinctions or depend on node attributes and information beyond 1-WL. Consequently, the depth required to reproduce the full stable coloring may differ considerably from that needed for graph classification, regression, or node-level prediction. A discussion of task-specific depth requirements would help clarify how the theoretical findings should inform practical GNN architecture design.

Questions for authors
  1. Assumptions underlying the exact-depth guarantee (Section 2, Definition 1; Theorem 1). The network model allows arbitrary update functions, unbounded width, and parameters that may depend on the input graph. While these assumptions are useful for establishing an expressivity limit, it is unclear how closely the resulting depth characterization applies to standard GNN architectures with fixed parameters and restricted nonlinearities. Can the authors clarify which assumptions are essential to achieving the upper bound of ⌊m/2⌋\lfloor m/2\rfloor ? In particular, does the same guarantee hold for graph-independent polynomial filters and shared-parameter networks of bounded width, or would additional depth be required?

  2. Numerical reliability of the Katz-filter construction (Section 2, Proposition 2; Appendix B). Proposition 2 establishes that a single faithful Katz filter can reproduce one complete stage of walk refinement. However, the construction relies on exact numerical distinctions between filtered walk counts. How does the minimum separation between the resulting vertex representations scale with graph size, maximum degree, and the number of stable color classes? Could the authors provide a precision or stability bound showing when these distinctions can be recovered using finite-precision computations?

  3. Generality of the paired-tail lower-bound construction (Section 3.2; Appendix C). The matching lower bound is established through a specially constructed paired-tail quotient, which is then realized as a connected simple graph. Can the authors characterize the structural properties that make these graphs require the maximum number of walk-refinement stages? In particular, are there similar lower bounds for bounded-degree or naturally occurring sparse graph families? It would be useful to understand whether the worst-case behavior is specific to this construction or reflects a broader phenomenon.

  4. Computational cost vs. reduction in network depth (Sections 2-3). The paper shows that global polynomial filters can reduce the worst-case depth relative to message passing, but a single global filtering layer may require substantially more computation than a local aggregation layer. How does the overall computational complexity compare when the cost of applying polynomial filters, evaluating Katz resolvents, and constructing new class representations is included? Could the authors provide a comparison in terms of total computational work rather than only the number of nonlinear layers?

  5. Tightness of the normalized-filter bounds for odd mm (Theorem 1(b); Appendix C.4). The depth bounds for the degree algebra coincide for even mm, but leave a gap of one layer for odd mm. Is this gap a consequence of the current proof technique, or are there structural reasons why the exact worst-case depth may differ between odd and even numbers of stable classes? Could the authors provide explicit examples attaining the upper bound for odd mm, or clarify whether obtaining an exact characterization remains an open problem?

4 comments
AuthorsOpenReview ↗

Response to Reviewer Jh2m (1/4)

Thank you for your careful and thorough review and for your positive assessment of our results. Your questions led us to strengthen several of them. The main changes are marked in red in the revised paper.

Q1 and W1. Assumptions underlying the exact-depth guarantee. No additional depth is required. We prove in this response that a single network of depth ⌊m/2⌋\lfloor m/2\rfloor computes the 1-WL coloring of all graphs with at most mm classes. Its polynomial filters do not depend on the graph, its weights are shared across vertices and across graphs, its feature width is mm, and its update functions are polynomials. With ReLU update functions the same holds on every finite family of such graphs.

The generality of Definition 1 only strengthens the lower bound. On the graphs of our construction no network with filters that are polynomials in the adjacency matrix (polynomial filters, for short) computes the 1-WL coloring from constant features in fewer than ⌊m/2⌋\lfloor m/2\rfloor layers, whatever its update functions and its width, and this includes networks designed for that one graph. Every restriction of the model inherits this bound.

The upper bound needs little of this generality. On every graph the least depth is attained with the same Katz filter in every layer and with update functions that are ReLU networks with one hidden layer of width at most mm, applied identically at every vertex (Section 2 and the new Appendix B.5). In this construction the weights of the update functions are chosen for the graph, as in the standard construction for message passing (Morris et al., 2019, Theorem 2).

Filters and weights can also be chosen once for all graphs. Let m≥3m\ge3 and L=⌊m/2⌋L=\lfloor m/2\rfloor. Consider the network of depth LL in which every layer has the filters I,A,…,Am−1I,A,\dots,A^{m-1} and layer tt applies the update x↦(1,s,s2,…,sm−1)x\mapsto(1,s,s^2,\dots,s^{m-1}) with s=⟨θt,x⟩s=\langle\theta_t,x\rangle. Here xx lists the m2m^2 filtered features at the vertex (mm in the first layer), and θt\theta_t is a weight vector of the same length, so every layer returns mm features at each vertex. For almost every choice of the weights θ0,…,θL−1\theta_0,\dots,\theta_{L-1}, this single network computes, from the constant feature 11, the 1-WL coloring of every graph whose stable coloring has at most mm classes. On each such graph GG its features induce the 1-WL coloring from layer τ(G)\tau(G) on, and τ(G)\tau(G) is the least depth of any network with polynomial filters on GG (Theorem 1(a)). The depth LL of this network cannot be reduced either, since these graphs include the graphs of our lower-bound construction with mm classes. The proof is in the last part of this response. Its idea is that ss takes distinct values on the classes that a layer separates, so that the powers of ss span the indicators of these classes.

The polynomial update functions can be replaced by ReLU networks on every finite family of graphs with at most mm classes each. Let NN be the total number of 1-WL classes of the graphs of the family, and fix weights as above. On each of these graphs the arguments of a layer correspond to the classes that the layer separates (see the proof), so at most NN distinct arguments occur at each layer. A ReLU network with one hidden layer of NN units can take any prescribed values at NN points (the construction of Appendix B.5, followed by a linear map). Replacing every update by such a network that agrees with it at these arguments therefore changes no feature on the graphs of the family. The resulting network has ReLU update functions with one hidden layer of at most NN units, and its feature width is still mm.

In the experiments of the new Appendix F, trained networks attain the predicted depths as well. There, networks with polynomial or Katz filters and ReLU layers of width 6464, trained to predict the 1-WL class of every vertex, reach at every tested depth exactly the accuracy that the corresponding number of stages of walk refinement allows.

AuthorsOpenReview ↗

Response to Reviewer Jh2m (2/4)

Q2 and W2. Numerical reliability of the Katz-filter construction. The separation that we guarantee does not depend on the number of vertices. You are right that the attenuation of the submitted version decreased with this number, and the attenuation in Theorem 1(a) and Proposition 2 is now 1/(Δm+Δ+1)1/(\Delta^m+\Delta+1), with Δ\Delta the maximum degree.

Proposition B.1 now gives this guarantee one stage at a time, with a margin. Consider a stage of walk refinement, and let kk be the least number such that the vectors of walk counts of lengths 0,…,k0,\dots,k into the current classes span those of all lengths. Then k≤m−1k\le m-1 (Appendix B.2). The Katz filter (I−ζA)−1(I-\zeta A)^{-1} performs the stage whenever ζ>0\zeta\gt0 and ζ(Δk+1+Δ)<1\zeta(\Delta^{k+1}+\Delta)\lt1, and the attenuation of the theorem satisfies this condition at every stage. When ζ(Δk+1+Δ)≤1/2\zeta(\Delta^{k+1}+\Delta)\le1/2, all entries of the filtered class indicators lie in [0,2][0,2], and the rows of two vertices that the stage separates differ by at least ζk/2\zeta^k/2 in some entry. If every entry is computed with an absolute error below ζk/8\zeta^k/8, each computed row is still closest, in the maximum norm, to its own exact row, so an update that assigns to each computed row the class of the nearest exact row performs the stage (Appendix B.5).

In terms of your three parameters, the guaranteed margin is thus independent of the graph size and involves only Δ\Delta and k≤m−1k\le m-1. On a graph with maximum degree Δ\Delta and mm classes, the single attenuation ζ=1/(2Δm+2Δ)\zeta=1/(2\Delta^m+2\Delta) serves every stage with margin at least ζm−1/2\zeta^{m-1}/2. This margin is the guarantee for the largest possible kk, and it is much larger when kk is small. On the graphs of Section 3.2, k=1k=1 at every stage, so the attenuation ζ=1/(2Δ2+2Δ)\zeta=1/(2\Delta^2+2\Delta) serves all stages with margin ζ/2\zeta/2. At a stage with large kk, the filters I,A,…,AkI,A,\dots,A^k can take the place of the Katz filter. Their outputs are walk counts, so the stage is then exact in integer arithmetic with ⌈log⁡2(Δk+1)⌉\lceil\log_2(\Delta^k+1)\rceil bits per entry, and no attenuation enters.

In our experiments a much larger attenuation suffices. In double precision, with the attenuation 1/(2λmax⁡)1/(2\lambda_{\max}) on graphs of our two lower-bound constructions with up to 312312 vertices, the rows of two vertices that a stage separates differ by at least 4.0⋅10−34.0\cdot10^{-3} in some entry, and rows that are equal in exact arithmetic differ by at most 3.4⋅10−153.4\cdot10^{-15} (Appendix F). The smallest gap between separated rows is thus at least 101210^{12} times the largest discrepancy between equal rows, so double precision recovers every distinction.

Q3 and W3. Generality of the lower-bound construction. The worst case is not tied to the particular graphs of our construction, since it is a property of their quotient matrix. Every graph that has an equitable partition with this quotient matrix needs ⌊m/2⌋\lfloor m/2\rfloor layers with polynomial filters, because walk refinement on a graph can be computed from its quotient matrix (Section 3.2 and Appendix C.2). For each mm there are such graphs on arbitrarily many vertices, all of maximum degree m2+mm^2+m. Other quotient matrices are extremal as well. Those of order 66 and 88 in Remark C.1 are realized on 2424 and 3232 vertices by irregular graphs of maximum degree 55, so the worst case also occurs on irregular graphs of small degree.

As for the structural property that makes a graph extremal, Proposition 4 now characterizes it exactly. By the identity of Proposition 3, a stage of walk refinement gains one class for each dimension that filtering adds, plus the deficiency of the filtered space. Every stage adds at least one dimension, and every stage but the last has deficiency at least one. A graph with an even number mm of classes needs m/2m/2 stages if and only if these numbers are as small as possible throughout, that is, every stage adds exactly one dimension, every stage but the last has deficiency exactly one, and the last has deficiency zero. For odd mm the condition is the same except that exactly one of these numbers is larger by one.

The mechanism behind the lower bound is therefore general. Positive deficiency means that the filtered features separate classes without containing all of their indicators, and this happens at every stage but the last on every graph. The extremal depth ⌊m/2⌋\lfloor m/2\rfloor itself requires the conditions of Proposition 4, and on common sparse graphs we find the opposite extreme. On paths one layer with polynomial filters suffices (Proposition A.2), where message passing needs m−1m-1 layers, and the same holds on each of 100100 further sparse graphs with up to 4040 vertices (grids, caterpillars, random trees, sparse Erdős–Rényi and Barabási–Albert graphs), where message passing needs between two and nine layers. On these graphs the depth of message passing beyond the first layer comes from locality, and global filters remove it.

AuthorsOpenReview ↗

Response to Reviewer Jh2m (3/4)

Q4 and W4. Total computational work. In the worst case over graphs with mm classes, a network of least depth with global filters needs at most as many multiplications by AA as message passing, only ⌊m/2⌋\lfloor m/2\rfloor updates where message passing needs m−1m-1, and no resolvent. To see this, note that a stage that adds rr dimensions to the span of the current class indicators is performed by the filters I,A,…,AkI,A,\dots,A^k for some k≤rk\le r. The stages gain m−1m-1 classes in all, and every stage but the last gains at least one class beyond the dimensions that it adds, so these dimensions total at most (m−1)−(τ(G)−1)=m−τ(G)(m-1)-(\tau(G)-1)=m-\tau(G). Hence some network of least depth τ(G)\tau(G) multiplies its features by AA at most m−τ(G)m-\tau(G) times in all (Section 3.3 and Appendix B.5). A Katz filter can replace the powers of a layer, and applying it amounts to solving one sparse linear system with at most mm right-hand sides.

This network can now be compared with message passing by counting products and updates. A layer with the filters I,A,…,AkI,A,\dots,A^k takes kk products of the sparse matrix AA with a feature matrix of at most mm columns, each in O(m(n+∣E∣))O(m(n+\lvert E\rvert)) operations on a graph with nn vertices and edge set EE, followed at every vertex by an update that reads the k+1k+1 filtered feature rows and is a ReLU network with at most mm hidden units. A message-passing layer, implemented with the filter AA, is the case k=1k=1. Message passing needs up to m−1m-1 layers, hence up to m−1m-1 products and m−1m-1 updates. For m≥3m\ge3 the network above needs at most m−τ(G)≤m−1m-\tau(G)\le m-1 products and at most ⌊m/2⌋\lfloor m/2\rfloor updates. Paths and the graphs of Section 3.2 are the two extremes. On paths with at least three vertices both networks use m−1m-1 products, and the network with global filters applies one update where message passing applies m−1m-1. On the graphs of Section 3.2 both use ⌊m/2⌋\lfloor m/2\rfloor layers with one product each.

W5. Downstream tasks. For a node-level task that needs only some of the distinctions of the 1-WL coloring, we determine the least depth in the new Remark B.1. From constant nonzero features, networks with polynomial filters stay within 1-WL (Proposition 1), so the targets that they can compute are those that are constant on the 1-WL classes. A target that distinguishes vertices inside a class is out of their reach at any depth, as it is for message passing. For a target that is constant on the classes, the least depth is the number of stages of walk refinement after which all vertices with different target values are separated. A task with two labels can still need the full depth. On the graphs of Section 3.2, deciding whether a vertex belongs to the last class of the construction is a binary node classification task that needs ⌊m/2⌋\lfloor m/2\rfloor layers (Section 3 and Remark B.1).

Node attributes enter as input colors (Proposition C.4). If the input features one-hot encode cc colors and the stable coloring that refines these colors has m≥c+2m\ge c+2 classes, at most ⌊(m−c+1)/2⌋\lfloor(m-c+1)/2\rfloor layers are needed with polynomial filters, and this bound is attained. For a graph-level task, a network whose filters and updates do not depend on the graph computes on two graphs the same vertex features as on their disjoint union. By Proposition 1, from constant features the features after tt layers are constant on the classes that tt stages of walk refinement produce on the union. A readout over the final vertex features therefore cannot tell the two graphs apart unless these stages give them different numbers of vertices in some class.

Q5. Tightness of the bounds for odd mm. Theorem 1(b) now answers this question with an exact value. Over the degree algebra D\mathcal D the worst case is ⌊(m−1)/2⌋\lfloor(m-1)/2\rfloor for every m≥3m\ge3. The upper bound of the submitted version was the right value, so the gap in the theorem came from the lower bound, and the new Proposition C.3 provides explicit extremal graphs for every odd m≥5m\ge5. We obtain their quotient matrix from that of our construction of order m−1m-1 by adding one class in such a way that the original classes all have the same degree. The degree matrix then differs from a multiple of the identity only at the new class. The first stage of walk refinement produces the indicator of this class in any case, so multiplying by degrees adds nothing to the filtered features at any stage, and the degree algebra needs as many layers as polynomials in the adjacency matrix do. In the worst case, passing from polynomials in the adjacency matrix to the degree algebra thus saves one layer when m≥4m\ge4 is even and none when mm is odd. This difference between even and odd mm is structural, since both values are exact.

AuthorsOpenReview ↗

Response to Reviewer Jh2m (4/4)

Proof that a single network serves all graphs with at most mm classes (Q1). Let m≥3m\ge3 and L=⌊m/2⌋L=\lfloor m/2\rfloor. Every layer of the network has the filters I,A,…,Am−1I,A,\dots,A^{m-1} and layer tt applies the update x↦(1,s,…,sm−1)x\mapsto(1,s,\dots,s^{m-1}) with s=⟨θt,x⟩s=\langle\theta_t,x\rangle. Let GG be a graph with adjacency matrix AA. For a partition π\pi of the vertices, K(π)\mathcal K(\pi) is the space of vectors that are constant on the classes of π\pi. Walk refinement sends π\pi to the partition ρ(π)\rho(\pi) in which two vertices lie together exactly when all vectors of ∑l≥0AlK(π)\sum_{l\ge0}A^l\mathcal K(\pi) agree at them. The partition after tt stages from the one-class partition is π(t)\pi^{(t)}, WW is the 1-WL coloring, and τ(G)\tau(G) is the least tt with π(t)=W\pi^{(t)}=W. The features after tt layers form the matrix H(t)H^{(t)}, with H(0)=1H^{(0)}=\mathbf 1. The argument xx of the update of layer tt at a vertex is the concatenation of the rows of H(t),AH(t),…,Am−1H(t)H^{(t)},AH^{(t)},\dots,A^{m-1}H^{(t)} at that vertex, one block for each power. It has mm entries for t=0t=0 and m2m^2 afterwards, as does θt\theta_t.

Call a choice of the weights generic if no nonzero polynomial with integer coefficients vanishes at the entries of θ0,…,θL−1\theta_0,\dots,\theta_{L-1}. Almost every choice is generic, because there are countably many such polynomials and each of them vanishes on a set of measure zero. We show that for generic weights, on every graph GG with at most mm stable classes and for every t≤Lt\le L, the columns of H(t)H^{(t)} span K(π(t))\mathcal K(\pi^{(t)}), so that the features after tt layers induce π(t)\pi^{(t)}. The statement follows, because π(t)=W\pi^{(t)}=W for all t≥τ(G)t\ge\tau(G) and τ(G)≤L\tau(G)\le L. For a graph with at least three classes the latter inequality is Proposition 4 applied to its quotient, and a graph with at most two classes needs at most one stage, since every stage that changes the partition adds a class.

We first show that one layer performs one stage of walk refinement when its weight vector separates the arguments. Let GG have at most mm stable classes, let π\pi be a partition coarser than WW, and let the columns of HH span K(π)\mathcal K(\pi). The columns of H,AH,…,Am−1HH,AH,\dots,A^{m-1}H then span ∑l<mAlK(π)\sum_{l\lt m}A^l\mathcal K(\pi), and this space equals ∑l≥0AlK(π)\sum_{l\ge0}A^l\mathcal K(\pi) because π\pi is coarser than an equitable partition with at most mm classes (Appendix B.2). The rows of a matrix at two vertices agree exactly when all vectors of its column space agree there, so two vertices have the same argument exactly when they lie in the same class of ρ(π)\rho(\pi). Let x1,…,xpx_1,\dots,x_p be the distinct arguments, one for each class of ρ(π)\rho(\pi). Then p≤mp\le m, since ρ(π)\rho(\pi) is coarser than WW (Lemma A.1). Call θ\theta separating if ⟨θ,xi−xj⟩≠0\langle\theta,x_i-x_j\rangle\ne0 for all i≠ji\ne j, that is, if the numbers si=⟨θ,xi⟩s_i=\langle\theta,x_i\rangle are distinct. For a separating θ\theta the new features are the entrywise powers with exponents 0,…,m−10,\dots,m-1 of the vector that equals sis_i on the ii-th class of ρ(π)\rho(\pi). They lie in K(ρ(π))\mathcal K(\rho(\pi)), and those with exponents 0,…,p−10,\dots,p-1 are linearly independent, because their values on the pp classes form the matrix (sij)(s_i^{j}) with 1≤i≤p1\le i\le p and 0≤j≤p−10\le j\le p-1, a Vandermonde matrix with distinct nodes. Hence the new features span K(ρ(π))\mathcal K(\rho(\pi)), whose dimension is pp.

It remains to show that generic weights are separating at every layer. Fix generic weights and a graph GG with at most mm stable classes. We prove the claim about H(t)H^{(t)} by induction on tt. It holds for t=0t=0, since H(0)=1H^{(0)}=\mathbf 1 spans K(π(0))\mathcal K(\pi^{(0)}). Suppose that it holds for some t<Lt\lt L. Every entry of an argument of layer tt is the value of a polynomial with integer coefficients in the entries of θ0,…,θt−1\theta_0,\dots,\theta_{t-1}. Indeed, H(0)=1H^{(0)}=\mathbf 1, the filters multiply by the integer matrices AlA^l, and an update forms sums and products of its inputs and of the entries of its weight vector. Let xix_i and xjx_j be two distinct arguments of layer tt, let dcd_c be such a polynomial for entry cc of xi−xjx_i-x_j, and let θt,c\theta_{t,c} be entry cc of θt\theta_t. Since xi−xjx_i-x_j has a nonzero entry, some dcd_c is not the zero polynomial. As the entries of θt\theta_t do not occur in the polynomials dcd_c, the sum ∑cθt,cdc\sum_c\theta_{t,c}d_c is then a nonzero polynomial with integer coefficients in the entries of θ0,…,θt\theta_0,\dots,\theta_t. Its value is ⟨θt,xi−xj⟩\langle\theta_t,x_i-x_j\rangle, which is not zero because the weights are generic. So θt\theta_t is separating. Since π(t)\pi^{(t)} is coarser than WW, the first part shows that the columns of H(t+1)H^{(t+1)} span K(ρ(π(t)))=K(π(t+1))\mathcal K(\rho(\pi^{(t)}))=\mathcal K(\pi^{(t+1)}).

We hope that these answers address your questions, and we would be glad to answer any further ones. Thank you again for the effort and expertise that you have devoted to our work in this review. Your questions have made the paper stronger.

Reviewer_8uDdOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies how many layers a graph neural network needs to compute the 1-WL coloring when each layer may also apply global filters. It shows that one layer performs at most one stage of "walk refinement," which separates vertices by their walk counts of every length into each current color class, so the minimum depth equals the number of walk-refinement stages. Over graphs whose stable coloring has mm classes, the worst case is m−1m - 1 layers for message passing and exactly ⌊m/2⌋\lfloor m/2 \rfloor with polynomial filters. The remaining depth is needed because only nonlinearities produce the indicator vectors of newly separated classes. The paper also derives consequences for architectures and bounds the number of alternations between filtering and entrywise multiplication.

Overall the work presents a piece of solid result, but it is not very surprising either.

Critical strengths
  1. The paper has given the worst case of the depth ⌊m/2⌋\lfloor m/2 \rfloor for networks that include global filtering. The result is solid. I am not super familiar with the literature.
  2. All results are proved, and the constructions are explicit.
  3. The theoretical result has real consequences for architecture design.
Critical weaknesses

My main concerns are the presentation, which makes the paper hard to follow, and how the headline claim is framed.

  1. In the core question, "Do global filters remove the depth that message passing needs, or does part of it survive every filter?", what does "it" refer to? The question should be stated precisely.

  2. In line 177, what does it mean for Kπ\mathbb{K}^\pi to be invariant under AA? I later see that A is used to perform a matrix operation. Can you explicitly explain the operation with A and other matrices somewhere?

  3. Line 196, it states that with M={A}\mathcal{M} = \{A\}, Definition 1 is "message passing in its most permissive form." This is easy to misread as saying that {A}\{A\} is the most permissive filter set, whereas it is the smallest one considered; the generality comes from the arbitrary update functions.

  4. The proof of Theorem 1 is spread across Section 2, Section 3, and Appendices A–C without a roadmap. A short paragraph mapping each claim to its proof would help.

  5. There is no experiments to check the empirical consequences of the work.

Questions for authors

Please check weaknesses.

4 comments
AuthorsOpenReview ↗

Response to Reviewer 8uDd (1/2)

Thank you for your careful review and for pointing to the specific places where the paper was hard to follow. Reading the paper again as a first-time reader would, we found similar difficulties beyond the places you named, most of all in the explanation of why layers are still needed when every layer sees the whole graph. We have therefore revised the exposition of the main text, in particular the introduction and Sections 2 and 3, and used the additional page allowed in the discussion period to add the explanations that a first-time reader needs. The main changes are marked in red in the revised paper. The main result, the exact worst-case depth ⌊m/2⌋\lfloor m/2\rfloor, is unchanged.

The core question and the headline claim (W1). In the question of the submitted version, "it" stood for the depth that message passing needs. We have replaced this question by one that asks directly for the number of layers: How many layers does a network with global filters need to compute the 1-WL coloring, in the worst case over graphs whose coloring has mm classes? The next paragraph gives the answer, exactly ⌊m/2⌋\lfloor m/2\rfloor for filters that are polynomials in the adjacency matrix, where message passing needs m−1m-1.

Since a global filter lets every layer see the whole graph, one might expect such filters to remove the need for depth, or at least to make the depth grow more slowly than linearly in mm. On paths, the worst case for message passing, a single layer indeed suffices. Yet some graphs still need ⌊m/2⌋\lfloor m/2\rfloor layers, whatever polynomials in the adjacency matrix are used as filters and whatever the update functions and the width. In a new paragraph of the introduction we explain where these layers come from. The filters of a layer are applied before its update and act linearly, and their outputs can tell classes of vertices apart without spanning the indicator vectors of these classes. For example, an output with the values 11, −1-1 and 00 on three classes separates them, but together with the constant input feature it spans only two dimensions, too few to contain the three indicators. An indicator that no filter produces is not produced by filtering twice either, because two polynomials in the adjacency matrix applied in succession act as a single one. The update can supply the missing dimension, here by appending the square of the output, with the values 11, 11 and 00. The features then span all three indicators, but only the next layer can filter them. Applying AlA^l to the indicator of a class counts the walks of length ll from each vertex into that class, and with such counts the next layer can separate further classes. On the graphs of Section 3.2 the first tt layers separate at most 2t+12t+1 classes, so reaching all mm classes takes ⌊m/2⌋\lfloor m/2\rfloor layers. The depth that remains is thus set by the nonlinear updates, however far each layer sees.

AuthorsOpenReview ↗

Response to Reviewer 8uDd (2/2)

Matrix operations and invariance under AA (W2). The space at line 177 consists of the vectors that are constant on the classes of a partition. It is invariant under AA when AA maps it into itself, that is, when AxAx is again constant on the classes for every vector xx of the space. As stated at line 177, this is the case exactly when the partition is equitable. Section 2 now states the meaning of invariance explicitly, and before that it explains how a matrix acts on vectors indexed by the vertices, as you asked. The entry of AxAx at a vertex uu is the sum of the entries of xx at the neighbors of uu, so applying AlA^l to the indicator vector of a set counts, at each vertex uu, the walks of length ll from uu that end in the set. The filters that we study are built from AA, and the normalized ones also from the degree matrix, so the outputs of a filter are combinations of such walk counts, weighted by degrees in the case of normalized filters.

"Most permissive form" (W3). As you say, {A}\lbrace A\rbrace is the smallest filter set we consider, and the generality comes from the arbitrary update functions. The sentence after Definition 1 (line 196 of the submitted version) now begins "With M={A}\mathcal M=\lbrace A\rbrace, the smallest filter set we consider, this is message passing with arbitrary update functions", and the phrase "most permissive" no longer appears in the paper.

Roadmap for the proof of Theorem 1 (W4). A paragraph after Theorem 1 now outlines the proof and says where each claim is proved. For part (a), a layer whose filters are polynomials in the adjacency matrix separates no more than one stage of walk refinement does (Definition 2 and Proposition 1), and one layer with a Katz filter separates exactly that much (Proposition 2), so the least depth with such filters is the number of stages of the graph (Appendix B.4). For part (b), every stage but the last gains at least two classes, so this number is at most ⌊m/2⌋\lfloor m/2\rfloor (Proposition 4), and the graphs of Section 3.2 attain this bound. Part (b) also covers message passing, where paths attain the bound m−1m-1 (Proposition A.1), and filters built from the adjacency and degree matrices, for which the bound ⌊(m−1)/2⌋\lfloor(m-1)/2\rfloor and the graphs that attain it are in Propositions C.2 and C.3.

Experiments (W5). The new Appendix F reports experiments on trained networks, with the code in the supplementary material. We trained message-passing networks and networks with global filters, on paths and on the graphs of our lower-bound constructions, to predict the 1-WL class of every vertex. For each architecture and each depth, our results bound which vertices a network can tell apart and hence the accuracy that it can reach, and in all 965965 runs the accuracy reached equals this bound exactly. In particular, on paths message passing needs m−1m-1 layers to classify every vertex correctly and a network with polynomial filters needs one (Figure 2), whereas on the graphs of our main construction (Section 3.2) both need the same ⌊m/2⌋\lfloor m/2\rfloor layers, so on these graphs none of the depth is due to locality. In the same experiments, linear networks, and decoupled networks that filter once and then apply a vertex-wise predictor, do not improve with depth, as our results predict.

We hope that the revised paper addresses your concerns, and we would be glad to answer any further questions. Thank you again for the effort and expertise that you have devoted to our work in this review. Your comments on the presentation have made the paper clearer.

Reviewer_8uDdOpenReview ↗

Thank you for your clarification

I have checked your responses. I will keep my rating.

We will go through the discussion again before it closes and would be glad to answer any further questions.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the Revision

We thank the reviewers for their careful reading and their questions. We have uploaded a revised paper, with the main changes marked in red, and the code for the new experiments as supplementary material. In response to the comments of Reviewer 8uDd on the presentation, we have revised the exposition of the main text, in particular the introduction and Sections 2 and 3, to make it clearer and easier to follow. The main result, that the worst-case depth is exactly ⌊m/2⌋\lfloor m/2\rfloor for filters that are polynomials in the adjacency matrix, is unchanged. In response to the questions of Reviewer Jh2m, we have strengthened several other results.

Presentation (Reviewer 8uDd). The core question of the introduction has been restated. It now asks directly how many layers a network with global filters needs to compute the 1-WL coloring, in the worst case over graphs whose coloring has mm classes, and the next paragraph gives the answer. To explain why layers are still needed when every layer sees the whole graph, we have added a paragraph in which we use a small example to go through the order of operations inside a layer. Section 2 now explains how a matrix acts on vectors indexed by the vertices and explicitly defines what it means for a space to be invariant under AA. In the same section, the sentence on the “most permissive form” has been reworded. A paragraph after Theorem 1 now outlines the proof and says where each claim is proved. Several terms that lacked a clear definition have been given one where they are first used. The opening of Section 3.1 has been rewritten to explain why walk refinement on a graph can be computed from its quotient matrix.

Strengthened results (Reviewer Jh2m). Theorem 1(b) now gives the exact worst case over the degree algebra D\mathcal D for every m≥3m\ge3. This worst case is attained by the graphs of our construction for even mm and for m=3m=3, and by those of the new Proposition C.3 for odd m≥5m\ge5. The attenuation of the Katz filter in Theorem 1(a) and Proposition 2 depends only on the maximum degree and on mm and no longer on the number of vertices. Proposition B.1 gives a lower bound on the margin by which a Katz filter with a sufficiently small attenuation separates two vertices, and this bound is independent of the number of vertices as well. The new Appendix B.5 addresses the computational cost and the size of the networks that attain the least depth with filters that are polynomials in the adjacency matrix. Fewer than mm multiplications by the adjacency matrix suffice in all, and the update functions can be ReLU networks with one hidden layer of width at most mm. Section 3.2 and Appendix C.2 show that every graph with the same quotient matrix as the graphs of our construction needs ⌊m/2⌋\lfloor m/2\rfloor layers with such filters. Proposition 4 now characterizes exactly when this many layers are needed. For node-level targets other than the full coloring, the new Remark B.1 gives the least depth, and Section 3 notes that on the graphs of our construction a binary node classification task already needs ⌊m/2⌋\lfloor m/2\rfloor layers with such filters.

Experiments (Reviewer 8uDd). The new Appendix F reports experiments in which we train message-passing networks, networks with polynomial, Katz and normalized filters, and linear and decoupled networks to predict the 1-WL class of every vertex. At every tested depth and in every run, the trained network reaches exactly the accuracy that our results predict for that depth.

Following Reviewer jxwb, we have corrected the sentence about the distance-two matrix in Appendix B.1. The remaining changes are smaller ones that mainly keep the rest of the paper consistent with these revisions or polish the presentation to improve clarity and avoid ambiguity.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.