{"id":"e5bfad50-94fa-41fb-a57d-6f6e7cd54106","arxiv_id":"2505.23185","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"IM-MPNN coarsens a graph into multiple scales, runs message passing on each scale in parallel, and interleaves information between scales, improving long-range information flow in MPNNs.","lead":"This paper introduces IM-MPNN, a graph neural network design that passes messages on several coarsened copies of the graph at once, letting information travel long distances without many layers. The method improves accuracy on long-range graph benchmarks and works as a drop-in wrapper around existing message-passing models.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 4.1's factor-four coarsened-Laplacian scaling is unproven for non-grid graphs, but it is a motivation gap, not a fatal flaw; the empirical central claim survives.","rationale":"The reader's weakest-assumption analysis points at the same Section 4.1 scaling claim, and I agree that it is the weakest link in the paper's theoretical motivation. The binomial analysis in Section 3.1 and the diffusion analogy in Eq. (12) are also heuristic and slightly mislabel Gaussian decay as exponential, but those do not threaten the architecture. The empirical evidence is extensive and consistent: the graph-transfer task in Figure 7 provides a direct, controlled demonstration that adding scales extends the distance over which IM-GCN can propagate information, and the LRGB, City-Networks, and heterophilic results show substantial gains across backbones. The complexity claim, while assuming ideal halving of nodes and edges, is empirically reflected in linear runtimes with moderate constants. The Section 4.1 issue is therefore best handled as a required revision: either prove the scaling relation for the specific coarsening, or replace it with the simpler and sufficient observation that a coarse hop shortens graph distances. Since the reader already made acceptance conditional on fixing the theoretical framing and I do not see a reason to move the verdict, the correct recommendation is unchanged.","tokens_in":22170,"tokens_out":10356,"duration_ms":113802,"concrete_test":"On the actual benchmark graphs (LRGB, City-Networks, and graph-transfer distributions), apply the exact unweighted Graclus coarsening used in the paper, and for a sample of node pairs measure the contraction ratio of shortest-path distances between G_s and G_{s+1}. Separately, estimate the effective diffusivity ratio by fitting the variance of one-step graph heat-kernel spreading at adjacent scales. If the distance contraction is approximately 2 and the diffusivity ratio is close to 4 only on grid-like graphs but not on the non-grid benchmarks, Section 4.1 should be rewritten as a qualitative distance-contraction argument rather than a factor-four Laplacian equivalence.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing weakness is in Section 4.1. To explain why coarsening expands the ERF, the paper claims that a factor-two coarsening of a graph corresponds to discretizing the continuous Laplacian on a step-2h grid, so the diffusion constant kappa in Eq. (12) multiplies by four. The only support is the 2D four-neighbor grid kernel in Eq. (13). For the arbitrary graphs processed by unweighted Graclus in the implemented method, this equivalence is not established: quotient graphs have variable degrees, non-uniform effective edge lengths, and no consistent coordinate step h, so the graph Laplacians at different scales are not simply scaled versions of one continuous operator with a global kappa. Thus the theoretical motivation for the specific factor four is unsupported. This is a real gap in the paper's explanatory claim. It is not, however, fatal to the central empirical claim: hierarchical coarsening shortens graph distances even without the factor-four story, and the graph-transfer experiments (Figure 7) and LRGB/City-Networks results directly demonstrate improved long-range information propagation. The concern warrants a qualification or a proof for the coarsening procedure used, not rejection.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the effective receptive field (ERF) of message-passing neural networks (MPNNs). It argues that the contribution of a node to a distant target decays rapidly, characterizes this through a linear-graph binomial analysis and a continuous diffusion analogy, and proposes IM-MPNN, an architecture that runs message passing on several coarsened graphs and interleaves information between scales. The method is evaluated on the Long-Range Graph Benchmark, a graph transfer task, City-Networks, and heterophilic node-classification benchmarks, with several MPNN backbones, controlled parameter budgets, and multiple random seeds. The results show consistent improvements over the corresponding single-scale baselines, especially on long-range tasks, while maintaining linear complexity.","tokens_in":22379,"tokens_out":6550,"duration_ms":66158,"significance":"If the empirical results hold, IM-MPNN is a simple, general, and practical enhancement for MPNNs on long-range tasks: it requires no change to the backbone aside from adding coarsening and scale-mixing, it respects parameter budgets, and the reported gains on PascalVOC-SP, COCO-SP, City-Networks, and graph transfer are substantial. The paper ships code, reports standard deviations over multiple seeds, and controls for parameter count, which strengthens the empirical contribution. The theoretical part is weaker: the claimed 'exponential' decay is actually Gaussian in distance for the linear-graph model, and the factor-four coarsening argument in Section 4.1 is only proven for regular grids, not for the unweighted Graclus coarsening used in practice. These issues affect the paper's explanatory narrative but do not invalidate the central empirical claim.","major_comments":[{"comment":"The claim that the relative contribution of nodes decreases 'exponentially with their distance' is not supported by the binomial analysis. For a fixed depth ℓ, the binomial coefficient at displacement d from the center behaves like (2/(πℓ))^{1/2} exp(−d^2/(2ℓ)), which is a Gaussian, not an exponential, decay in distance. Hoeffding's inequality in Eq. (8) bounds a cumulative tail for k = αℓ, so it decays exponentially in ℓ, not per-node exponentially in d. The qualitative conclusion that the ERF is much smaller than the theoretical receptive field remains valid, since the standard deviation grows only as √ℓ, but the abstract, Section 3, and conclusion should be corrected from 'exponential' to 'Gaussian/squared-exponential' decay.","section":"Section 3.1, Eqs. (5)-(8)"},{"comment":"The argument that factor-two coarsening multiplies the diffusion constant κ by four rests on the 2D four-neighbor grid kernel with uniform step h, and is not established for the unweighted Graclus coarsening used in the implementation. Quotient graphs have variable degrees and no global coordinate step, so the graph Laplacians at different scales are not simply scaled versions of one continuous operator with a global κ. Since this factor-four scaling is the paper's stated mechanism for why coarsening expands the ERF, the authors should either prove the scaling for the actual coarsening procedure or explicitly downgrade it to heuristic motivation and rely instead on the direct observation that coarsening shortens graph distances. The empirical results do not depend on this argument, but the theoretical explanation in Section 4.1 does.","section":"Section 4.1, Eq. (13)"}],"minor_comments":[{"comment":"The condition for E′ should read ∃ vi ∈ v′q, vj ∈ v′p, (vi, vj) ∈ E; as written, both vertices are drawn from the same component v′q, which contradicts the surrounding text.","section":"Eq. (15)"},{"comment":"The phrase 'which we present in Section 4' is self-referential; it should be 'Section 4.2'.","section":"Section 4.1"},{"comment":"The boundary cases s = 0 and s = S are not specified; please state explicitly that the lower-to-higher or higher-to-lower terms are omitted at the finest and coarsest scales.","section":"Eq. (20)"},{"comment":"The text says 'up to 41% relative improvement on both PascalVOC-SP and COCO-SP', but COCO-SP improves from 0.1338 to 0.1960, which is about 46.5% relative; please make the reported number consistent.","section":"Section 5.1"},{"comment":"The procedure used to measure the node contributions is not described; please add a short description (or an appendix entry) so that the ERF visualization is reproducible.","section":"Figure 1"},{"comment":"There are two typos: 'V onessen' in Section 2 before the reference should be 'Vonessen', and 'ORGB Arxiv' in Table 10 should be 'OGBN Arxiv'.","section":"Typos"},{"comment":"The selected number of scales for each dataset and seed is not reported; please include this hyperparameter setting in the appendix.","section":"Appendix C.4"}],"recommendation":"major_revision","confidential_remarks":"The empirical core is solid and the architecture is simple enough to be widely useful. The main risk is overclaiming in the theory: the claimed exponential decay is actually Gaussian, and the factor-four coarsening argument is only established for regular grids. Neither issue sinks the empirical contribution, but both need to be fixed before publication. The novelty relative to existing hierarchical MPNNs is incremental, but the systematic LRGB evaluation and the parameter-budget control justify publication after revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a look: the IM-MPNN architecture is a genuinely useful drop-in enhancement for MPNNs on long-range tasks. The idea is simple and sensible: coarsen the graph hierarchically, run the same backbone on every scale, and interleave the scales so information moves both up and down. It keeps linear complexity (the 2x constant is fine) and the empirical work is honest and extensive: LRGB, City-Networks, heterophilic benchmarks, graph transfer, with parameter budgets controlled and multiple seeds. The City-Networks gains are striking (+10 to +16 points over GCN). The comparison against Graph U-Net and DRew is also a nice check that the multiscale scheme is doing real work, not just adding capacity. Code is available and runtimes are reported. This deserves serious peer review.\n\nThe soft spots are all on the theory side. Section 3.1 calls the decay 'exponential,' but the linear-graph analysis gives a binomial distribution; the tail is sub-Gaussian, not exponential. That is a mischaracterization, and it appears again in the abstract's claim of 'exponentially decaying ERF.' It should be fixed to 'Gaussian' or 'sub-Gaussian' and the prose should be qualified accordingly. The heavier weakness is Section 4.1: the factor-four scaling of the diffusion constant is argued from a regular 2D grid kernel. For arbitrary graphs coarsened with unweighted Graclus—variable degrees, non-uniform effective edge lengths—there is no reason the coarsened Laplacian behaves like a step-2h discretization. The stress-test note got this right: it is a motivation gap, not a fatal flaw. The architecture shortens graph distances regardless of the factor-four story, and the graph-transfer experiments demonstrate that directly. Still, the paper should either prove or explicitly weaken that claim.\n\nOne thing I checked: the self-citation to Finder et al. (2024) is only inspirational context; the actual design here is distinct. The theoretical analysis is independent of the proposed method, so there is no circularity. The number of scales S is tuned by validation, which is standard.\n\nBottom line: a solid empirical contribution with a theory section that needs honest revision. Send it to review, with the expectation of minor-to-moderate revision. I would cite the architecture and the City-Networks results.","headline":"Solid multiscale architecture with strong experiments; the theory overclaims exponential decay and leans on an unproven grid analogy, but the core contribution survives.","tokens_in":22928,"tokens_out":2519,"would_cite":true,"duration_ms":24734,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Message-passing networks lose influence with hop distance; the IM-MPNN multiscale wrapper extends their effective receptive field at linear cost.","keywords":["effective receptive field","message-passing neural networks","graph neural networks","multiscale graph coarsening","over-squashing","long-range dependencies","graph diffusion","heterophilic node classification"],"falsifier":"Measure per-scale effective diffusion constants on non-grid graphs by fitting the Gaussian of Eq. (12) to empirically measured node-contribution profiles (as in Figure 1): if halving the node count does not roughly quadruple $\\kappa$, the theoretical justification for the multiscale design is refuted, even though the architecture might still work empirically.","tokens_in":21980,"feed_emoji":"🌐","tokens_out":12769,"duration_ms":114567,"temperature":0.7,"pith_summary":"The paper sets out to show that message-passing neural networks (MPNNs) suffer from a limited effective receptive field (ERF): the influence of a node on a distant node's output decays exponentially with hop distance, so long-range dependencies are poorly captured even when the network is deep enough in principle to reach them. It formalizes this by analyzing uniform-weight convolution on a line graph, where node contributions follow Pascal's triangle and thus a binomial distribution with exponentially small tails, and by viewing MPNN layers as a discretization of a diffusion equation whose heat-kernel solution spreads only slowly in space. To remedy this, it proposes IM-MPNN, which coarsens the graph several times, runs the same message-passing scheme on every scale, and interleaves scales with learned mixing operations, so that one step on a coarse graph reaches roughly the region that several steps reach on the original graph. The authors report that this drop-in wrapper keeps the linear O(|V|+|E|) complexity of standard MPNNs and raises accuracy on long-range benchmarks, graph-transfer tasks, and heterophilic node classification.","feed_headline":"Coarsened graphs give message-passing nets a longer reach","feed_subtitle":"A graph net that also passes messages on coarsened copies beats plain MPNNs on long-range tasks at linear cost.","key_machinery":"The load-bearing mechanism is the diffusion-equation picture of message passing. The paper reads a stack of MPNN layers as a discretization of $\\partial x/\\partial t = -Lx$, a heat equation on the graph's latent geometry, so that the influence of a source spreads like the heat kernel of Eq. (12). The key identity is the grid-mesh relation of Eq. (13): coarsening a 2D grid from step size $h$ to $2h$ divides the discretized Laplacian $\\Delta_h$ by four, so the effective diffusion constant $\\kappa$ in the coarser representation multiplies by four and the Gaussian spread of Eq. (12) grows faster. That is why a single message-passing step on scale $s$ behaves like several steps on the original graph. The architecture built on this is IM-MPNN: after Graclus coarsening creates scales $G_0,\\dots,G_S$, each scale runs its own MPNN with separate weights, and scale-mix layers (Eq. 20) fuse each node's features with those of its parent in the coarser graph and its children in the finer graph, so high-frequency detail stays in the fine scale while the coarse scales deliver long-range information.","core_discovery":"The paper's central claim is that MPNNs have a limited effective receptive field in the same sense as CNNs: the relative contribution of a node to the output of another node decays exponentially with the graph distance between them. On a linear graph, $\\ell$ uniform convolution steps yield binomial coefficients, and Hoeffding's inequality bounds the total contribution of a block of far-away nodes by $\\exp(-2(1/2-k/\\ell)^2 \\ell)$; in the diffusion picture, the point-source solution $x(p,t)=(4\\kappa\\pi t)^{-d/2}\\exp(-\\lVert p-p_0\\rVert^2/(4\\kappa t))$ spreads only as a Gaussian whose variance grows linearly with the number of layers. Because this spread is slow, stacking layers is an inefficient route to long-range reach. IM-MPNN counters this by coarsening the graph $S$ times with Graclus pooling, running the chosen MPNN backbone on each of the $S+1$ scales, and interleaving the scales with learned mixing so each node receives features from its parent and children nodes. With width reduced to match the parameter budget of the baseline, IM-MPNN reports up to 41% relative improvement on PascalVOC-SP and COCO-SP, near-perfect transfer of a label across 37 hops on CliquePath where a standard GCN fails near 7 hops, and accuracy gains of 10 to 16.5 points on City-Networks, while keeping the total cost linear in graph size.","pith_inferences":["Testable extension (ours): compare IM-MPNN against a single-scale MPNN given the same parameter budget and against one augmented with distance or random-walk encodings; if the multiscale wrapper still wins clearly, the ERF mechanism is doing real work rather than merely adding capacity.","Editorial reading: the learned scale-mix weights $W_{l2h}$ and $W_{h2l}$ act as per-scale diffusion constants; monitoring their magnitudes during training could reveal whether the model genuinely channels long-range information through the coarse scales.","The paper uses Graclus pooling, but its own coarsening-agnostic design implies that any pairing scheme that roughly halves graph distances — spectral or learned pooling, for instance — should extend the ERF similarly, making the gains track the distance-reduction factor of the pooling.","A natural next step the authors leave implicit is composing IM-MPNN with graph rewiring or graph-transformer layers: the coarse scales supply a cheap global channel that could complement attention rather than compete with it."],"forward_implications":["One message-passing step on the $s$-th coarsened scale reaches about $2^s$ hops of the original graph, so far fewer layers are needed to move information across a large graph.","Any linear-complexity MPNN backbone can be wrapped by IM-MPNN while keeping total complexity linear, because the work across all scales sums to $O(2(|V|+|E|))$.","Deepening a plain MPNN is a comparatively inefficient way to gain receptive field, since long-range contributions decay exponentially; multiscale processing reuses the same parameters more effectively.","The reported gains — up to 41% relative on PascalVOC-SP and COCO-SP, 10–16.5 accuracy points on City-Networks, and 100% label-transfer at 37 hops where GCN fails at 7 — indicate that many long-range failures of MPNNs stem from the limited ERF rather than from insufficient expressivity.","The number of scales is a tunable hyperparameter, and adding scales returns diminishing gains once the coarsest graph is reached or when the graph is highly homophilic."],"supporting_citations":[{"why":"Supplies the CNN effective-receptive-field concept and the exponential-decay analysis that the paper transfers to MPNNs.","marker":"(Luo et al., 2016)"},{"why":"Provides the point-source heat-equation solution used to characterize the ERF on graphs.","marker":"(Pattle, 1959)"},{"why":"Supplies the Graclus coarsening algorithm used to build the multiscale graph representations.","marker":"(Dhillon et al., 2007)"},{"why":"Defines the graph-transfer task and the distance-based over-squashing analysis that motivates the evaluation.","marker":"(Di Giovanni et al., 2023)"},{"why":"Provides the Long-Range Graph Benchmark datasets and protocol used in the main experiments.","marker":"(Dwivedi et al., 2022)"},{"why":"The CNN multiscale ERF-augmentation work from which the interleaved multiscale design draws inspiration.","marker":"(Finder et al., 2024)"},{"why":"Supplies the improved LRGB evaluation setup adopted for the experimental comparisons.","marker":"(Tönshoff et al., 2023)"},{"why":"Provides the heterophilic node-classification datasets and baselines used for evaluation.","marker":"(Platonov et al., 2023)"}],"fun_headline_variants":["Multiscale graphs extend message-passing nets' reach","Graph coarsening widens effective receptive field","Passing messages across scales beats deep stacking","Interleaved multiscale messages fix squashed signals"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The claim that coarser scales widen the receptive field depends on treating a coarsened graph as a factor-two-coarser discretization of the same continuous Laplacian, so that the diffusion constant $\\kappa$ quadruples — an analogy proven for regular grid-like meshes but not established for arbitrary graphs.","fun_headline_variants_meta":{"raw":{"variants":["Multiscale graphs extend message-passing nets' reach","Graph coarsening widens effective receptive field","Passing messages across scales beats deep stacking","Interleaved multiscale messages fix squashed signals"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000527,"raw_usage":{"total_tokens":2601,"prompt_tokens":1059,"completion_tokens":1542,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":675,"completion_tokens_details":{"reasoning_tokens":1480}},"tokens_in":675,"tokens_out":1542,"duration_ms":11365,"temperature":1.0,"reasoning_tokens":1480,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:51:00.365930+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Measure per-scale effective diffusion constants on non-grid graphs by fitting the Gaussian of Eq. (12) to empirically measured node-contribution profiles (as in Figure 1): if halving the node count does not roughly quadruple $\\kappa$, the theoretical justification for the multiscale design is refuted, even though the architecture might still work empirically.","supporting_citations":[{"cited_title":"Understanding the effective receptive field in deep convolutional neural networks","cited_arxiv_id":null,"evidence_quote":"Supplies the CNN effective-receptive-field concept and the exponential-decay analysis that the paper transfers to MPNNs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the point-source heat-equation solution used to characterize the ERF on graphs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the graph-transfer task and the distance-based over-squashing analysis that motivates the evaluation."},{"cited_title":"P., Ramp \\'a s ek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A","cited_arxiv_id":null,"evidence_quote":"Provides the Long-Range Graph Benchmark datasets and protocol used in the main experiments."},{"cited_title":"A critical look at the evaluation of GNN s under heterophily: Are we really making progress? In The Eleventh International Conference on Learning Representations, 2023","cited_arxiv_id":null,"evidence_quote":"Provides the heterophilic node-classification datasets and baselines used for evaluation."}],"review_version":1}