{"id":"10e51695-8977-4571-a957-937082aa34bd","arxiv_id":"2502.00140","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":3.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper claims a k-layer message-passing network is equivalent to a single layer on the k-th power of the adjacency matrix, with deep-network failures on sparse graphs blamed on gradients.","lead":"This paper argues that message-passing neural networks are essentially an efficient way to multiply the graph's adjacency matrix many times. It also claims that when deep graph networks fail on sparse graphs, the cause is usually training problems, not over-smoothing.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The UAT step in Lemma 2.7/2.8 is invalid: dropping the inner nonlinearity is not licensed by universal approximation, and a simple two-layer ReLU example contradicts the claimed A^k representation.","rationale":"The reader's verdict and weakest_assumption identify exactly the load-bearing flaw: the induction in Appendix A.2 (and A.3/A.4) removes the inner activation sigma via UAT. My independent check confirms this is not a minor presentation issue. The claimed algebraic representation H^(k)=sigma((W⊙A)^k X W^(k)) is false for standard ReLU GCNs on signed inputs; the two-layer and single-layer-on-A^k functions differ as functions, not merely at one point. Since Section 2 is the theoretical foundation for the paper's title and abstract claims ('message passing as merely efficient matrix multiplication'), the central claim is unsupported. The empirical comparisons in Sections 3-4 may still be informative, but they do not establish the equivalence. I therefore agree with REJECT and recommend no change to the reader's verdict. I did not find an additional independent objection that would change the outcome; the loop-density analysis and the structure-only experiments are separable empirical contributions that could survive even if the central equivalence is withdrawn.","tokens_in":16560,"tokens_out":7871,"duration_ms":81724,"concrete_test":"Run exact float or symbolic evaluation for k=2 on the 6-node directed graph 1→4, 2→4, 3→5, 4→6, 5→6, with ReLU, identity weights, no self-loops, and feature vector X=[1,1,-1,0,0,0]^T. The 2-layer output at node 6 is ReLU(ReLU(x1+x2)+ReLU(x3)) = 2, while the claimed single-layer output on A^2 is ReLU(x1+x2+x3) = 1. If this reproduces, Lemma 2.7 is false as stated; repeating over the cube [-1,1]^3 shows the mismatch is functional, not a single-point artifact.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central equivalence rests on Appendix A.2, Eq. 5 to Eq. 6, and the parallel step in A.3: in the induction, sigma(W⊙A · sigma((W⊙A)^k X W^(k)) · W^(k+1)) is replaced by sigma((W⊙A)^(k+1) X W^(k+1)), justified only by saying 'Thanks to the Universal Approximation Theorem... This simplification does not affect the network's ability to approximate the target function.' This is not a valid use of UAT. UAT asserts that some sufficiently wide MLP can approximate a continuous function; it does not license deleting a fixed nonlinearity from a fixed compositional network, nor does it imply that the composition is representable as sigma((W⊙A)^(k+1) X W') for a single weight matrix W'. For nonnegative matrices and nonnegative inputs the identity can hold accidentally, but with signed features, signed weights, or normalized adjacency matrices it fails. Example: graph 1→4, 2→4, 3→5, 4→6, 5→6, with X=[1,1,-1,0,0,0]^T, identity weights, and ReLU. A 2-layer GCN without self-loops gives output 2 at node 6; a 1-layer GCN on A^2 gives ReLU(1)=1. As functions, the 2-layer output is ReLU(ReLU(x1+x2)+ReLU(x3)), while the single-layer output is ReLU(x1+x2+x3); these differ on an open set. Hence the A^k equivalence, and with it the 'efficient matrix multiplication' interpretation, is unsupported for nonlinear MPNNs.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper aims to provide a theoretical account of message-passing neural networks (MPNNs), claiming three main results: (1) a k-layer MPNN operating on adjacency matrix A is approximately equivalent to a single-layer MPNN operating on A^k, so that message passing is essentially a memory-efficient way to compute powers of the adjacency matrix; (2) different loop structures (self-loops, two-node loops, longer cycles) cause hop coexistence and thereby contribute to over-smoothing; and (3) node classification tasks can be split into structure-feature hybrid and structure-only types, with the latter reducible to degree-based feature prediction. The theoretical core is Lemma 2.7 (and Lemmas 2.8, 2.9), whose proofs in Appendix A rely on removing the inner nonlinearity via the Universal Approximation Theorem. The empirical sections compare deep GCNs, single-layer GCNs on k-hop neighborhoods, and hybrid architectures on citation and web graphs, and they study normalization schemes with uniform features.","tokens_in":16976,"tokens_out":7362,"duration_ms":75265,"significance":"If the central equivalence were valid, the paper would provide a clean and useful interpretation of deep GNNs as iterative matrix-power computation, and it would connect loop structure to over-smoothing through hop coexistence. The empirical comparison of depth growth versus k-hop neighborhood growth on directed sparse graphs is a useful experiment, and the observation that row normalization with uniform features destroys degree information is sound. The paper also provides a code link and reports standard deviations over multiple splits. However, the main theoretical claim is not established: the proof of the key lemmas uses an invalid application of the Universal Approximation Theorem, and a concrete ReLU counterexample shows that the claimed A^k equivalence is false as stated. The paper's central theoretical contribution is therefore unsupported, even though some of its empirical observations may be of independent interest.","major_comments":[{"comment":"The induction step is not a proof. After substituting the induction hypothesis, the expression σ(W⊙(A+I) σ((W⊙(A+I))^k X W^(k)) W^(k+1)) is replaced by σ((W⊙(A+I))^(k+1) X W^(k+1)) with the sole justification 'Thanks to the Universal Approximation Theorem'. UAT asserts that some sufficiently wide network can approximate a continuous function; it does not license deleting a fixed nonlinearity from a fixed compositional expression, nor does it imply that the composition is exactly representable as σ(M X W') for a single matrix M. The same unjustified step is used in Appendix A.3 for Lemma 2.7 and in Appendix A.4, Eqs. (9)-(10), for Lemma 2.9. Since this step is the load-bearing part of the paper's central claim, the proof is invalid.","section":"Appendix A.2, Eqs. (5)-(6)"},{"comment":"The claimed identity is false for standard ReLU GCNs. Consider the directed graph with edges 1→4, 2→4, 3→5, 4→6, and 5→6, using the paper's convention A_{ij}=1 for an edge i→j, node feature vector X=[1,1,-1,0,0,0]^T, identity weight matrices, and ReLU activation. The 2-layer GCN without self-loops gives output 2 at node 6, while the single-layer GCN on A^2 gives ReLU(1)=1 at node 6. As functions, the two-layer output is ReLU(ReLU(x1+x2)+ReLU(x3)) and the single-layer output is ReLU(x1+x2+x3), which differ on an open set. Thus the A^k equivalence, and with it the 'efficient matrix multiplication' interpretation, is unsupported for nonlinear MPNNs.","section":"Section 2.2, Lemma 2.7"},{"comment":"The paper's advertised result is that a k-layer MPNN on adjacency matrix A is approximately equivalent to a single-layer MPNN on A^k, but Lemma 2.7 actually states H^(k)=σ((W⊙A)^k X W^(k)), where W⊙A is the normalization-mask form of the adjacency matrix introduced in Appendix E.1, Eq. (12). For a symmetrically normalized GCN, (D^{-1/2}AD^{-1/2})^k is not A^k, and the distinction affects both the neighborhood interpretation and the experiments in Section 4, which use powers of the original adjacency matrix. The formal statement of the paper's own lemma therefore does not match the headline claim.","section":"Introduction and Section 2.3"},{"comment":"The proof of Lemma 2.9 repeats the same invalid UAT step: Eq. (9) contains inner σ terms applied to sums of powers of (W⊙A), and Eq. (10) removes those σ terms with no justification other than the same UAT sentence. In addition, the conclusion line of the proof states H^(n)=σ((W⊙(A+I))^n X W^(n)), which is the GCN-with-self-loop formula rather than the GraphSAGE expression claimed in Lemma 2.9. Since the derivation is central to the paper's treatment of GraphSAGE, this lemma is also unsupported.","section":"Appendix A.4, Lemma 2.9"}],"minor_comments":[{"comment":"The lemma uses 'kth order node feature' but the statement is about p-hop neighbors; the variables p and k should be made consistent.","section":"Lemma 2.3"},{"comment":"The expression cW^(k+1) contains an unexplained symbol c; this appears to be a typo.","section":"Equation (6)"},{"comment":"The symbol W is overloaded: W⊙A denotes a fixed normalization mask, while W^(l) denotes learnable feature-transformation matrices. These should be distinguished by different symbols, especially in Lemmas 2.7-2.9.","section":"Notation throughout"},{"comment":"The statement that row normalization with homogeneous features makes 'all nodes get identical representations' assumes zero biases and identical initial features; the conditions should be stated explicitly.","section":"Section 4.2.1"},{"comment":"The citation 'Rossi et al. (?)' is incomplete and should be filled in.","section":"Appendix C.2.1"},{"comment":"The density of the k-hop adjacency matrix is used to support the over-smoothing discussion, but the definition is not precise about whether density counts nonzero entries or path counts, nor about how normalization affects the reported values.","section":"Table 1 and Figures 4-5"}],"recommendation":"reject","confidential_remarks":"The central theoretical claim is invalid in its current form: the UAT-based proof step in Appendix A is not a valid equality argument, and the ReLU counterexample shows that the A^k equivalence is false for a standard GCN. A revision that restricts the claim to linear MPNNs or to special nonnegative feature/weight settings could salvage a version of the matrix-power interpretation, but that would change the paper's scope and weaken the advertised message. The empirical material on sparse directed graphs, depth versus k-hop growth, and normalization may be publishable as a separate empirical study, but it does not rescue the theoretical contribution as stated."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper's central theoretical result is not proven. The step in Appendix A.2 (Eq. 5 to Eq. 6) where they drop the inner nonlinearity 'thanks to UAT' is invalid, and a simple two-layer ReLU GCN does not match the claimed A^k representation. So the 'message passing is merely efficient matrix multiplication' framing, at least as an equivalence, does not hold for nonlinear MPNNs.\n\nThat said, the paper does some things well. The experimental design in Figure 4 (growing layers vs growing k vs k-hop plus linear layers) is a genuinely useful way to separate gradient degradation from oversmoothing, and the result that a directed GCN without self-loops stays stable up to 50 layers on Chameleon/Squirrel is a real observation worth explaining. The loop-coexistence lemmas (self-loops extend k-hop to k+1, undirected edges extend to k+2) are elementary but correct, and they do clarify when repeated powers of A create dense connectivity. The structure-only analysis—uniform features reduce to degree counting, row normalization destroys degree information—is correct and cleanly explained.\n\nThe soft spots are serious but located. The proof of Lemma 2.7/2.8 is the load-bearing wall. UAT does not license removing a fixed nonlinearity from a fixed compositional network; it says some network of sufficient width can approximate a target function. The stress-test counterexample (a specific 6-node graph where 2-layer GCN output at node 6 is 2 but the A^2 single-layer is 1) is a clean demonstration. Also, the notation (W ⊙ A)^k requires either weight sharing across layers or an unjustified absorption of per-layer weights; as written it is not the adjacency matrix power. The paper also occasionally conflates 'approximation' with 'exact equivalence.' The experiments are interesting but they are used to support the flawed theory, so the interpretation of Figures 4-6 needs to be re-framed once the theory is corrected.\n\nMinor: Appendix A.4's conclusion line for GraphSAGE accidentally writes the GCN-with-self-loop formula, which is a typo but symptomatic of haste.\n\nBottom line: this paper is a mix of a failed central proof and some genuinely useful empirical/observational work. Researchers working on GNN depth and oversmoothing will find the experiments thought-provoking, but they should not rely on the theoretical equivalence. A serious reviewer could help the authors fix or drastically weaken the theoretical claims and keep the experiments. I'd send it to review, not desk-reject, because the experimental contribution and the loop analysis are worth engaging with. I wouldn't cite the equivalence, but I might cite the Figure 4 methodology or the directed no-self-loop stability finding if the authors re-scope the paper.","headline":"The central A^k equivalence is unsupported (invalid UAT step, concrete counterexample), but the empirical depth-vs-neighborhood decomposition and loop analysis deserve referee time.","tokens_in":17447,"tokens_out":3816,"would_cite":false,"duration_ms":33736,"reading_group":"maybe","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 is just efficient matrix multiplication","keywords":["graph neural networks","message passing","adjacency matrix powers","k-hop neighborhoods","over-smoothing","node degree","universal approximation","node classification"],"falsifier":"Train a $k$-layer GCN without self-loops and, in parallel, a single-layer GCN whose adjacency matrix is $A^k$, using the same weight initialization and training budget on a small graph; if the two models' outputs or test accuracies differ substantially (beyond what function-approximation error would allow), the claimed equivalence is falsified, because the closed form predicts they should be interchangeable.","tokens_in":16393,"feed_emoji":"🧮","tokens_out":8401,"duration_ms":66879,"temperature":0.7,"pith_summary":"This paper argues that message passing in graph neural networks is fundamentally repeated matrix multiplication by the adjacency matrix. The central claim is that a $k$-layer GCN without self-loops aggregates only the $k$-hop neighborhood, not a cumulative 1-through-$k$ neighborhood, and behaves approximately like a single-layer GCN on the matrix power $A^k$. This reframing makes message passing a memory-efficient way to compute $A^k$ times the feature matrix, and it has direct consequences: adding self-loops or symmetrizing graphs mixes hops and drives over-smoothing, while in sparse directed graphs deep-network failures can come from gradients instead. The paper also shows that with uniform node features, degree becomes the effective feature, making structure-only tasks a special case of hybrid tasks.","feed_headline":"Message passing is just efficient matrix multiplication","feed_subtitle":"A k-layer GNN uses exactly the k-hop neighborhood and matches a single layer on A^k.","key_machinery":"The load-bearing object is the $k$-th power of the adjacency matrix, $A^k$, whose nonzero entries count directed paths of length exactly $k$. The identity $H^{(k)} = \\sigma((W \\odot A)^k X W^{(k)})$ carries the argument: it says depth in an MPNN computes powers of the normalized adjacency matrix. The proof's enabling step is the binomial expansion $(A+I)^k = \\sum_{i=0}^k \\binom{k}{i} A^i$, which converts the self-loop formula into a sum of $k$-hop features. The path-counting interpretation of matrix powers, proved by induction in Lemma 2.5, connects algebraic powers to graph-theoretic neighborhoods.","core_discovery":"The paper's central discovery is the closed-form equivalence expressed in Lemma 2.7: for a $k$-layer GCN without self-loops, $H^{(k)} = \\sigma((W \\odot A)^k X W^{(k)})$, where $W$ is the normalization weight matrix. The proof proceeds by induction and uses the Universal Approximation Theorem to justify dropping the activation inside each layer. For a GCN with self-loops, the analogous formula gives $\\sigma((W \\odot (A+I))^k X W^{(k)})$, which by the binomial theorem is a linear combination of all powers $A^0$ through $A^k$; GraphSAGE produces a similar combination through its separate self-feature path. The paper also proves loop-driven inheritance rules (self-loops add one hop, undirected edges add two, $m$-cycles add $m$) and uses them to explain over-smoothing and to identify gradient-related degradation in sparse graphs. For uniform features, it shows a $(k+1)$-layer network equals a $k$-layer network using node degrees as features.","pith_inferences":["If the central equivalence is accepted, then tuning depth is effectively tuning the power of the adjacency matrix; this suggests that layer count and neighborhood radius are interchangeable up to memory constraints, and that residual or normalization tricks that preserve the linear form may be more effective than architectural modifications aimed at over-smoothing.","The paper's distinction between density-driven over-smoothing (loops, undirected edges) and gradient-driven degradation (sparse directed graphs) could be turned into a diagnostic: compare the $k$-layer model's accuracy with the single-layer $A^k$ model's accuracy; a large gap with comparable neighborhoods points to gradient or optimization issues rather than over-smoothing.","A testable extension: on graphs where adding self-loops hurts, the theory predicts the harm scales with the density of $(A+I)^k$ versus $A^k$; this can be checked by ablating self-loops on a range of homophily and heterophily datasets."],"forward_implications":["A $k$-layer GCN without self-loops uses exactly the $k$-hop neighbors of each node, not a cumulative aggregation of all shorter hops.","Because $(A+I)^k$ expands into all powers of $A$, adding self-loops (or working on undirected graphs) makes $k$-hop neighborhoods contain shorter-hop neighbors, which the paper identifies as a mechanism for over-smoothing.","Deep GCNs can maintain accuracy up to 50 layers on sparse directed graphs when self-loops and undirected symmetrization are removed, indicating gradient problems rather than over-smoothing are the main failure mode there.","With uniform node features, node degree becomes the effective feature: a $(k+1)$-layer MPNN with constant features is equivalent to a $k$-layer MPNN using degree as the only feature.","Message passing is a memory-efficient alternative to explicitly forming $A^k$ and multiplying it with $X$, since iterative multiplication avoids storing the dense power matrix."],"supporting_citations":[{"why":"Supplies the Universal Approximation Theorem used to justify dropping the nonlinear activation inside each layer during the proof of Lemma 2.7 and Lemma 2.8.","marker":"Hornik et al., 1989"},{"why":"Provides the approximation-capability result also invoked at the same activation-dropping step in the induction proofs.","marker":"Hornik"},{"why":"Defines the GCN layer with self-loops and symmetric normalization that the paper analyzes in Lemmas 2.7 and 2.8.","marker":"Kipf & Welling, 2016"},{"why":"Defines GraphSAGE, whose separate self-feature path is the subject of Lemma 2.9.","marker":"Hamilton et al., 2017"},{"why":"Provides the standard observation that GCNs over-smooth within a few layers, which the paper challenges for sparse directed graphs.","marker":"Li et al., 2018"},{"why":"The over-smoothing survey whose explanation the paper argues is incomplete, motivating the gradient-based alternative.","marker":"Rusch et al., 2023"},{"why":"Provides the Dir-GNN model and directed normalization scheme used in the structure-only experiments and normalization analysis.","marker":"Rossi et al., 2024"}],"fun_headline_variants":["Message passing is just matrix multiplication","k-layer GNNs equal one layer on A^k","Demystifying GNNs: it's all matrix multiplication","GNNs revealed: message passing is matrix multiplication"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof that a $k$-layer network equals a single layer on $A^k$ assumes that removing the nonlinear activation inside each layer, justified by the Universal Approximation Theorem, does not change the network's behavior; the theorem only guarantees that some network can approximate a function, not that deleting this specific activation is harmless.","fun_headline_variants_meta":{"raw":{"variants":["Message passing is just matrix multiplication","k-layer GNNs equal one layer on A^k","Demystifying GNNs: it's all matrix multiplication","GNNs revealed: message passing is matrix multiplication"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000693,"raw_usage":{"total_tokens":3116,"prompt_tokens":906,"completion_tokens":2210,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":522,"completion_tokens_details":{"reasoning_tokens":2148}},"tokens_in":522,"tokens_out":2210,"duration_ms":16060,"temperature":1.0,"reasoning_tokens":2148,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T20:01:09.540278+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train a $k$-layer GCN without self-loops and, in parallel, a single-layer GCN whose adjacency matrix is $A^k$, using the same weight initialization and training budget on a small graph; if the two models' outputs or test accuracies differ substantially (beyond what function-approximation error would allow), the claimed equivalence is falsified, because the closed form predicts they should be interchangeable.","supporting_citations":[{"cited_title":"Multilayer feedforward networks are universal approximators","cited_arxiv_id":null,"evidence_quote":"Supplies the Universal Approximation Theorem used to justify dropping the nonlinear activation inside each layer during the proof of Lemma 2.7 and Lemma 2.8."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Dir-GNN model and directed normalization scheme used in the structure-only experiments and normalization analysis."}],"review_version":1}