{"id":"6d439b3c-7387-4b71-9ba3-aa52b9eb0d88","arxiv_id":"2502.03703","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Under a k-separability condition for k greater than 1, k-hop subgraph GNNs are universal approximators on connected graphs with no cycle longer than 2k+1; k-hop GNNs without subgraph structure get a similar 2k-1 bound.","lead":"This paper proves that k-hop subgraph graph neural networks can approximate any continuous graph function on graphs whose longest cycle is about 2k+1, provided an extra separability condition holds for k larger than 1. It matters because it gives a design rule: choose the aggregation radius k based on the largest cycle you need to resolve.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.5's induction extension may not preserve edges at distance k−1; the proof asserts this without ruling out duplicate colors inside the ball, leaving the central separation theorem unverified.","rationale":"The central claim is the universal approximation of k-hop subgraph GNNs on bounded-cycle graphs; it rests entirely on the separation theorem (Theorem 3.5). The k=1 case has a complete induction proof, but for k≥2 the proof's key extension step is compressed and, as written, does not rule out a neighbor of w2 of the same color inside the ball, which would break the isomorphism. This is a correctness risk distinct from the scope concern about k-separability. The proposed exhaustive check is decisive for small k and would quickly reveal a counterexample if one exists. Regardless of the outcome, the paper should provide a detailed proof of the induction step or a formalization, and should temper the claim that the extension is 'immediate'. The experimental results are not load-bearing for the theorem, and the authors' own limitation note about k-separability is honest but does not address this gap. Verdict remains CONDITIONAL: the paper should be revised with a complete proof or a computational verification of Theorem 3.5 before the central claim can be accepted.","tokens_in":18030,"tokens_out":34886,"duration_ms":288477,"concrete_test":"Exhaustively enumerate all connected simple graphs on n ≤ 7 vertices with no cycle longer than 5; for each, compute the stable coloring of the 2-hop subgraph WL test (Algorithm 1 with k=2, collision-free hashing, iterated to a fixed point) and check the 2-separability condition (Definition 3.3). Then test whether any two non-isomorphic 2-separable graphs in this class yield the same final color multiset. If such a pair exists, Theorem 3.5 (and hence Theorem 3.4 for k=2) is false. If none exists, the theorem is computationally supported for k=2, n≤7, but a rigorous proof of the edge-preservation step is still required.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Central to Theorem 3.4 is Theorem 3.5: k-separable connected graphs with no cycles longer than 2k+1 are distinguished by the k-hop subgraph WL test. The proof in Appendix B extends an isomorphism f : Nk(S1) → Nk(S2) to Nk(v1) ∪ Nk(S1) by matching vertices in T1 = Nk(v1) \\ Nk(S1) to T2 = Nk(v2) \\ Nk(S2) by color. This matching is unique on T1 and T2 because every vertex there is at distance exactly k from v1/v2 and k-separability forces distinct colors there. The unproven step is edge preservation. For w1 ∈ Nk(v1) with d(w1, v1) = k−1 (Case 2), the proof argues that the multisets of neighbor colors of w1 and w2 = f(w1) are equal, and that this plus k-separability implies u1w1 is an edge iff u2w2 is an edge. But multiset equality only shows w2 has some neighbor of u1's color. A neighbor at distance < k from v2 is not covered by k-separability, so it need not be u2. The same issue occurs in Case 1 when w1 ∈ Nk(S1) ∩ Nk(v1) at distance k: the rooted isomorphism Nk(v1) ≅ Nk(v2) may not coincide with f on vertices of color that repeat inside the ball, and the proof does not establish coincidence. If the extension is not an isomorphism, the induction fails and the WL test might not distinguish the graphs. The paper's limitation note does not mention this proof gap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies k-hop subgraph GNNs, which update a vertex representation from the subgraph induced by all vertices within distance k, together with an associated k-hop subgraph WL test. The main theoretical claim is that, under a k-separability condition (Definition 3.3), k-hop subgraph GNNs can approximate any permutation-invariant or permutation-equivariant continuous function on connected graphs whose cycles all have length at most 2k+1 (Theorems 3.4 and 3.5), with an unconditional version for k=1 (Theorems 3.1 and 3.2). An analogous result is stated for k-hop GNNs that do not use the subgraph structure, under a stronger k-strong separability condition and the bound 2k-1 on cycle length (Theorems 3.8 and 3.9). The proofs proceed by Stone-Weierstrass separation arguments and by inductively constructing isomorphisms from WL color equivalence. The paper also reports ZINC experiments with a k-hop Graphormer, observing improved MAE as k increases to about 3, which the authors interpret as confirming the predicted relation between aggregation distance and cycle length.","tokens_in":18389,"tokens_out":10125,"duration_ms":97795,"significance":"If the main theorems were fully established, the paper would give a clean design heuristic: the aggregation radius k controls the longest cycle that a subgraph GNN can resolve. This would generalize the known tree result of Bamberger (2022) to bounded-cycle graphs and would provide a nontrivial universal approximation theorem for a widely used class of architectures. The paper is careful to state assumptions and to acknowledge that k-separability might not be removable. The inductive separation proofs in the appendices do real work beyond a direct citation of the tree result. However, the significance is substantially tempered by three issues: the k-separability and k-strong separability assumptions are ad hoc and exclude many graphs that satisfy the cycle bound; the central equivalence theorem (Theorem 2.5) is stated without proof; and the proof of the key separation theorem for k>=2 (Theorem 3.5) has a gap in the edge-preservation argument. The ZINC experiments are suggestive but do not test the k-separability assumptions, so the abstract's claim that the experiments validate the theory is stronger than what the evidence supports.","major_comments":[{"comment":"The inductive extension of f is not established. The proof asserts that f takes Nk(S1) ∩ Nk(v1) to Nk(S2) ∩ Nk(v2), and in Case 2 it claims that equality of the multisets of neighbor colors of w1 and w2, combined with k-separability, implies that u1w1 is an edge iff u2w2 is an edge. This inference is invalid as written: multiset equality only gives a neighbor x2 of w2 whose color equals that of u1, and x2 may have distance less than k from v2, where k-separability imposes no uniqueness. Nothing in the paragraph rules out x2 ≠ u2. The assertion about the image of the intersection is also in need of proof, because the rooted isomorphism Nk(v1) ≅ Nk(v2) need not agree with the color-based extension f on vertices whose colors repeat inside the ball. Since Theorem 3.5 is the load-bearing step for Theorem 3.4, this gap must be repaired, either by strengthening the induction hypothesis or by supplying the missing uniqueness argument.","section":"Appendix B, proof of Theorem 3.5"},{"comment":"Theorem 2.5, which equates the separation power of k-hop subgraph GNNs with that of the k-hop subgraph WL test, is stated without proof and is used at every Stone-Weierstrass step, including the proofs of Theorems 3.1(i), 3.1(ii), and, through Theorem 3.5, Theorem 3.4. The statement that the proof follows the lines of Theorem 4.2 of Chen et al. (2023) is not a substitute for a proof or a precise derivation, since the update in (4) is a rooted-subgraph WL refinement rather than the setting of that reference. This is a central equivalence: it is exactly what converts WL indistinguishability into GNN separation for the Stone-Weierstrass argument. Please include a full proof in an appendix or provide an exact statement of the cited theorem together with a detailed adaptation.","section":"Section 2.3, Theorem 2.5"},{"comment":"The k-separability and k-strong separability conditions are not implied by the bounded-cycle hypothesis and exclude many graphs that satisfy the cycle bound. For example, a path with constant initial features is not k-separable for any k>=2, and a symmetric cycle is not k-strongly separable. The limitation paragraph in Section 5 does acknowledge that removal of k-separability is open, but the abstract and introduction phrase the result as applying to graphs with bounded cycles. The paper should state the scope precisely in the abstract and should quantify how restrictive k-separability is; otherwise the phrase 'under appropriate assumptions' does not convey that the main theorem may have very limited applicability. The k-strong separability condition for Theorem 3.8 is even more restrictive, since all pairs of vertices within distance 2k must have distinct stabilized colors.","section":"Definitions 3.3 and 3.7; Theorems 3.4 and 3.8"},{"comment":"The experiments are presented as validating the theory, but the ZINC graphs are not shown to satisfy k-separability or k-strong separability, and the k-hop Graphormer is not shown to realize the separation power of the k-hop subgraph WL test used in Theorems 3.4 and 3.5. The observed MAE improvement around k=3 is consistent with the heuristic that the receptive field should cover the longest observed cycles, but it does not test the theorems' assumptions or their quantitative predictions. Please temper the claim of validation in the abstract and Section 4.3, or add synthetic experiments designed to satisfy and to violate k-separability under controlled cycle lengths.","section":"Section 4, experiments"}],"minor_comments":[{"comment":"The phrase 'without cycles of length greater than 2k+1' is correct but can be read as excluding the value 2k+1; consider writing 'all cycles of length at most 2k+1' for readability.","section":"Abstract and Section 1"},{"comment":"The loop is written 'while l = 1,2,...,L' but should be 'for l = 1,2,...,L'; also, the iteration limit L in Algorithm 1 is not explicitly identified with the quantifier 'for any L>0' in Definition 2.4.","section":"Algorithm 1"},{"comment":"The definition of k-separability refers to 'when the k-hop subgraph WL test terminates with stabilized colors and without hash collisions'; this should be formalized, since termination and stabilization depend on the hash function and the initial features.","section":"Definition 3.3"},{"comment":"The text says the 1-hop Graphormer has MAE 'similar in scale' to traditional 1-hop GNNs, but Table 1 reports 0.459 for the former versus 0.088 for GIN; the difference is a factor of about five, so the wording should be adjusted.","section":"Table 1 and Section 4.3"},{"comment":"The notation Nk(S) is defined in Appendix B but is used in the main text only informally; moving this definition to Section 2 would improve readability.","section":"Appendix B, notation"}],"recommendation":"major_revision","confidential_remarks":"The main theoretical claim is interesting and likely repairable, but the manuscript currently has two load-bearing gaps: Theorem 2.5 is unproved and the induction in Theorem 3.5 has an unverified edge-preservation step. I would ask the authors for a complete proof of Theorem 2.5, a repaired or strengthened induction argument for Theorem 3.5, and a careful statement of the scope of the k-separability assumptions, including a discussion of whether the assumptions are satisfied by any infinite family of graphs beyond the k=1 case. The ZINC experiments should be reframed as a heuristic illustration rather than a validation of the theorems."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The k=1 result is real; the k≥2 extension has a genuine proof gap in Theorem 3.5, so the main universal approximation claim for k≥2 is not established as written. I'd still send this to a referee, but the authors need to repair or weaken the proof.\n\nWhat's new and good: Theorem 3.2 extends Bamberger's tree separation result to graphs with no cycles longer than 3, and the inductive proof is mostly clean. The Stone-Weierstrass passage from separation to universal approximation is standard but correctly applied, and the paper is honest about what it does and doesn't cover. The related-work discussion around Feng et al. and Huang et al. is fair.\n\nThe soft spot is Theorem 3.5. The stress-test concern is on target. In Case 2 of the induction, knowing that w1 and w2 have the same multiset of neighbor colors plus k-separability does not force the neighbor of w2 that has u1's color to be u2. That neighbor could sit at distance < k from v2, where k-separability imposes no constraints, or it could be a vertex in Nk(S2) with the same color as u1. More basic: the proof asserts d(w1,v1)=d(w2,v2) for images under the existing isomorphism f, but f is only an isomorphism on Nk(S1), and there is no reason it should preserve distance to the new root v1/v2. So the edge-preservation step is not justified. The paper's limitation note mentions only the k-separability assumption, not this gap.\n\nThe k-separability condition itself is restrictive—it fails for paths and many symmetric bounded-cycle graphs, so Theorem 3.4 excludes graphs that satisfy the cycle bound. That limitation is disclosed, but it substantially lowers the significance of the k≥2 generalization. Also Theorem 2.5, the GNN/WL equivalence for the k-hop subgraph setting, is stated without proof; likely true, but it is load-bearing and the reader has to trust the adaptation.\n\nThe experiments use a k-hop Graphormer, which is not a subgraph GNN, and the theory for that architecture (Theorem 3.8) gives bound 2k−1, so for k=3 it covers cycles up to 5, while ZINC's dominant cycles are length 6. The performance boost around k=3 is consistent with the theory but not a clean test.\n\nWho is this for? People working on GNN expressiveness. The k=1 theorem is a concrete, citable contribution. The k≥2 part needs a fixed proof or a weaker statement. I'd send it to peer review, with a clear message to the authors about the Theorem 3.5 gap.","headline":"The k=1 separation theorem is a genuine contribution; the k≥2 extension has a real proof gap in Theorem 3.5, so the main universal approximation claim for k≥2 is not established as written.","tokens_in":18923,"tokens_out":11689,"would_cite":true,"duration_ms":97216,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","05C60","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"k-hop subgraph GNNs can approximate any continuous invariant or equivariant function on graphs whose cycles are no longer than 2k+1.","keywords":["subgraph graph neural networks","Weisfeiler-Lehman test","universal approximation","graph isomorphism","bounded cycles","k-hop aggregation","permutation equivariance"],"falsifier":"Enumerate small connected graphs and look for two non-isomorphic graphs that both have no cycle longer than 2k+1 and are k-separable but receive identical color multisets from the k-hop subgraph WL test; the theorem asserts no such pair exists, so finding one would refute it directly. A softer empirical check is to train a k-hop subgraph GNN on graphs whose longest cycle is L and see whether accuracy on a cycle-sensitive function saturates exactly once 2k+1 >= L.","tokens_in":1714,"feed_emoji":"🔗","tokens_out":3503,"duration_ms":112474,"temperature":0.7,"pith_summary":"Subgraph GNNs that read each vertex's k-hop neighborhood are known to beat ordinary message-passing GNNs, but exactly what they can represent has been unclear. This paper claims a precise threshold: under a technical k-separability condition, a k-hop subgraph GNN can approximate any continuous, permutation-invariant or permutation-equivariant function on connected graphs with no cycle longer than 2k+1, with the k=1 case holding unconditionally. If correct, the aggregation radius k becomes a design parameter tied to the data's longest cycle, and it explains why performance on molecular benchmarks saturates once k reaches about half the longest cycle. The paper also shows that k-hop GNNs that skip the subgraph structure retain the guarantee on graphs with no cycle longer than 2k-1, at the price of a stronger separability assumption.","feed_headline":"k-hop GNNs can learn any continuous graph function up to cycle 2k+1","feed_subtitle":"Proof ties aggregation radius to longest resolvable cycle, making k a design choice.","key_machinery":"The machinery is the k-hop subgraph Weisfeiler-Lehman test, which recolors each vertex by the isomorphism type of the rooted subgraph spanned by all vertices within distance k of it. Theorem 2.5 equates its separation power with that of k-hop subgraph GNNs, so proving universal approximation reduces to proving that the test distinguishes all graphs in the class. The proof of that separation statement works by induction: start with two matched vertices of equal stabilized color, extend the partial isomorphism one vertex at a time using the rooted subgraphs of matched boundary vertices, and use Lemma B.1 to rule out hidden edges connecting the new k-hop neighborhood to the previously matched part. The k-separability condition is what makes boundary vertices uniquely identifiable by color during this extension.","core_discovery":"The paper's central claim is that k-hop subgraph GNNs are universal approximators on connected graphs with bounded cycle length: under the k-separability condition, for any continuous permutation-invariant (graph-level) or permutation-equivariant (vertex-level) function and any tolerances epsilon and delta, there is a k-hop subgraph GNN whose output differs from the target by more than delta only on a set of probability less than epsilon, provided the graphs have no cycles longer than 2k+1. For k=1 the result is unconditional and covers every connected graph whose only cycles are triangles. The separating statement underneath is Theorem 3.5: two connected, k-separable graphs with no cycles longer than 2k+1 that are indistinguishable by the k-hop subgraph WL test must be isomorphic. An analogous theorem for plain k-hop GNNs without subgraph structure gives the same approximation guarantee under k-strong separability for graphs with no cycles longer than 2k-1.","pith_inferences":["The open k-separability question likely has a softer resolution: instead of all distance-k vertices having distinct colors, a condition on the stabilizer of the color partition (for example, a regular color-class structure) may suffice for the inductive extension, which would bring paths and other symmetric graphs back under the theorem.","The cycle bound suggests a cheap practical diagnostic for any graph dataset: compute the longest cycle, set k to the smallest value satisfying 2k+1 >= L (or 2k-1 >= L for plain k-hop GNNs), and stop increasing k there; the ZINC experiments are consistent with this plateau behavior.","The same radius-versus-diameter logic should transfer to distance-aware transformers and other architectures that mask attention to a k-hop neighborhood, predicting a similar performance cliff when the mask radius falls below half the longest cycle."],"forward_implications":["Choose k as the smallest integer with 2k+1 at least the longest cycle in the data: a k-hop subgraph GNN then has, in principle, enough expressive power to approximate any continuous invariant or equivariant property of those graphs.","A 1-hop subgraph GNN is already universal on connected graphs whose only cycles are triangles, with no k-separability assumption.","Dropping subgraph structure costs one hop: a plain k-hop GNN reaches the same universal approximation guarantee only for graphs whose cycles are at most 2k-1, and needs a stronger strong-separability condition.","Graph-level and vertex-level functions are covered together: both the permutation-invariant and permutation-equivariant approximation statements hold under the same cycle bound.","In the ZINC experiments, performance rises as k increases to about half the dominant cycle length and saturates beyond it, with k=infinity slightly worse, matching the theoretical prediction that extra aggregation distance adds no expressive benefit once the cycle bound is met."],"supporting_citations":[{"why":"Defines the color-refinement algorithm whose separation power is the baseline that subgraph GNNs are shown to exceed.","marker":"Weisfeiler & Leman, 1968"},{"why":"Gives the equivalence between message-passing GNN separation and WL separation, the starting point for the analogous equivalence in Theorem 2.5.","marker":"Xu et al., 2018"},{"why":"Provides the generalized Stone-Weierstrass theorem used to convert separation of points into universal approximation for invariant and equivariant functions.","marker":"Azizian & Lelarge, 2021"},{"why":"Proves that classic WL distinguishes trees, the k=1 base case that Theorem 3.2 extends to graphs without long cycles.","marker":"Bamberger, 2022"},{"why":"Its proof of the WL-versus-GNN equivalence for a related architecture is the template for Theorem 2.5.","marker":"Chen et al., 2023"}],"fun_headline_variants":["k-hop subgraph GNNs universal on graphs with cycles ≤2k+1","Cycle bound 2k+1 makes k-hop GNNs universal approximators","For graphs without cycles >2k+1, k-hop GNNs express all continuous functions","k-hop GNNs: universal approximation for bounded-cycle graphs","New proof: k-hop GNNs cover all functions on graphs with cycles up to 2k+1"],"cache_read_input_tokens":20992,"weakest_assumption_plain":"The argument depends on k-separability, meaning that every vertex at distance exactly k from a common root receives a distinct stabilized color in the k-hop subgraph WL test, which fails for symmetric graphs like paths; the authors state they do not know whether this condition can be removed, and the unconditional k=1 result does not generalize automatically.","fun_headline_variants_meta":{"raw":{"variants":["k-hop subgraph GNNs universal on graphs with cycles ≤2k+1","Cycle bound 2k+1 makes k-hop GNNs universal approximators","For graphs without cycles >2k+1, k-hop GNNs express all continuous functions","k-hop GNNs: universal approximation for bounded-cycle graphs","New proof: k-hop GNNs cover all functions on graphs with cycles up to 2k+1"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000732,"raw_usage":{"total_tokens":3256,"prompt_tokens":910,"completion_tokens":2346,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":526,"completion_tokens_details":{"reasoning_tokens":2248}},"tokens_in":526,"tokens_out":2346,"duration_ms":13801,"temperature":1.0,"reasoning_tokens":2248,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T04:05:20.058332+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate small connected graphs and look for two non-isomorphic graphs that both have no cycle longer than 2k+1 and are k-separable but receive identical color multisets from the k-hop subgraph WL test; the theorem asserts no such pair exists, so finding one would refute it directly. A softer empirical check is to train a k-hop subgraph GNN on graphs whose longest cycle is L and see whether accuracy on a cycle-sensitive function saturates exactly once 2k+1 >= L.","supporting_citations":[{"cited_title":"and Leman, A","cited_arxiv_id":null,"evidence_quote":"Defines the color-refinement algorithm whose separation power is the baseline that subgraph GNNs are shown to exceed."},{"cited_title":"and Lelarge, M","cited_arxiv_id":null,"evidence_quote":"Provides the generalized Stone-Weierstrass theorem used to convert separation of points into universal approximation for invariant and equivariant functions."},{"cited_title":"A topological characterisation of Weisfeiler-Leman equivalence classes","cited_arxiv_id":null,"evidence_quote":"Proves that classic WL distinguishes trees, the k=1 base case that Theorem 3.2 extends to graphs without long cycles."},{"cited_title":"On representing linear programs by graph neural networks","cited_arxiv_id":null,"evidence_quote":"Its proof of the WL-versus-GNN equivalence for a related architecture is the template for Theorem 2.5."}],"review_version":1}