{"id":"81ab2e6c-a1cd-4ff8-aa30-8b0d7e2e872b","arxiv_id":"2505.11346","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Localized MIMO graph convolutions (LMGCs) generalize many linear message-passing GNNs and are provably injective and produce linearly independent representations for almost every edge weight choice.","lead":"This paper derives graph convolutions for multi-channel node features and proposes a localized layer family, LMGC, that generalizes many existing graph neural networks. The authors prove that, for almost any choice of edge weights, these layers can distinguish distinct neighbor feature multisets and produce independent node representations.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 3 is false as stated: zero feature vectors make LMGC non-injective for every coefficient choice, so the a.e. expressivity claim needs an explicit 0 not-in-X assumption.","rationale":"I read the paper as trying to establish that the linear LMGC framework inherits both expressivity and anti-collapse properties from generic edge-weight coefficients. The MIMO-GC derivation and the unification of GCN, GAT, FAGCN, and ACM are genuine contributions, and the experiments are suggestive, if not decisive. The load-bearing defect is in the theoretical core: Proposition 3, as stated, is false when the countable feature set X contains the zero vector. Because LMGC is linear in node features, zero features are invisible to the aggregation, so multisets of zero vectors cannot be distinguished for any coefficients, contradicting 'almost every choice.' The appendix proof fails exactly at the linear-algebra step where it assumes the concatenated feature matrix has a proper kernel. This is a missing-hypothesis error, not a fundamental invalidation of the framework: excluding 0 from X, requiring output dimension c >= 2 for Proposition 4, and repairing the invalid reduction from weighted to unweighted sums would likely restore the claims. I therefore keep the reader's CONDITIONAL verdict rather than moving to REJECT. I disagree with the reader's weakest_assumption because it located the problem in the transfer of a.e. guarantees to the neural-network instantiation; the more basic problem is that one of the a.e. theorems is false as stated.","tokens_in":19279,"tokens_out":12263,"duration_ms":131831,"concrete_test":"Construct the counterexample: set X = {0} subset R^d with K = 1, and evaluate f(0, {0}) and f(0, {0, 0}) for any alpha and W; both outputs are identically zero, contradicting Proposition 3. If the authors instead intend 0 not-in X, add that hypothesis explicitly and re-derive the proof of Proposition 3, and separately check whether Proposition 4 holds for c >= 2 without the invalid reduction from weighted to unweighted sums.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's headline guarantee is that any LMGC with K > 0 is injective on multisets for almost every choice of coefficients. Proposition 3 is stated for an arbitrary countable set X. If 0 is in X, take the element x_p = 0 and the two multisets X1 = {0}, X2 = {0, 0}. For every choice of alpha and every W, the LMGC outputs are f(0, {0}) = 0 and f(0, {0, 0}) = 0, so injectivity fails. This is not a measure-zero artifact; it holds for all coefficients, because the update is linear in the node feature x_j and any edge message W_(i,j) * 0 is zero. The appendix proof of Proposition 3 reduces injectivity to having X_s alpha_k nonzero for a.e. alpha_k, but when X_s is the all-zero matrix, its kernel is the full space. The theorem can be repaired by assuming 0 not-in X and, for Proposition 4, by assuming c >= 2 with a repaired proof; as written, the abstract's injectivity claim is false.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper derives the multi-input multi-output graph convolution (MIMO-GC) from the convolution theorem, observes that its key structural feature is the use of multiple computational graphs (equivalently, distinct linear feature transformations between node pairs), and introduces the localized MIMO graph convolution (LMGC) as a unified framework that subsumes several linear message-passing networks. The main theoretical claims are that, for almost every choice of edge-weight coefficients, an LMGC with one computational graph is injective on finite multisets (Proposition 3), and that with more than one computational graph the resulting node representations are linearly independent (Proposition 4). The paper also presents an LMGC instantiation based on a GATv2/FAGCN-style coefficient function and reports experiments on a synthetic universality task, the ZINC/ZINC12k graph regression benchmark, and six heterophilic node-classification datasets.","tokens_in":19471,"tokens_out":14537,"duration_ms":151909,"significance":"If the theoretical results are repaired, the paper makes a useful conceptual contribution: the spectral derivation of the MIMO-GC is self-contained and the LMGC framework gives a clean unifying perspective on GCN, GAT, gating mechanisms, and neural sheaf diffusion. The experimental study is thorough and includes a reproducible implementation, competitive benchmark results, and a direct universality comparison. However, the current statements of Propositions 3 and 4 are not correct as written, and the benchmarked instantiation is not covered by the almost-everywhere guarantees. These issues are repairable, but they affect the paper's headline theoretical claims, so the manuscript needs substantial revision before publication.","major_comments":[{"comment":"Proposition 3 is false as stated. If the countable set X contains the zero vector, take the multisets X1={0} and X2={0,0} with the same center element 0; then f(0,{0}) = W(0) = 0 and f(0,{0,0}) = 0 + 0 = 0 for every choice of coefficients and every W, so injectivity fails for all parameters. If the empty multiset is allowed, then f(x,∅)=0 for every x, which also breaks injectivity unless X has at most one element. The proof via X_s α_k ≠ 0 fails exactly when X_s is the zero matrix, because then ker(X_s) is the whole space. The theorem must assume 0∉X and restrict to nonempty multisets (or otherwise explicitly exclude the empty-neighborhood case). As written, the abstract's claim that LMGCs with K>0 are 'injective for almost every choice of edge weights' is not true.","section":"Section 4, Proposition 3; Appendix B.2"},{"comment":"Proposition 4 is missing necessary hypotheses and its proof is not rigorous. It must require output dimension c≥2: in R^1 no two nonzero vectors are linearly independent, so the statement is vacuous or false when c=1. It also inherits the zero-vector and empty-multiset problems from Proposition 3. More importantly, the proof's step 'there exists ... c(1,2) such that Eq. (23) holds for all k' is not a consequence of the assumed linear dependence of the two output vectors; the correct object is the algebraic set of parameters (α,W) for which f1∧f2=0, which needs to be shown to be a proper algebraic set of measure zero. The norm-based argument around Eq. (25) does not handle the uncountable family of scalar multipliers c, and the notation c is used inconsistently (output dimension vs. scalar multiplier, with 'c∈N'). A careful rewrite of both the statement and the proof is needed.","section":"Section 4, Proposition 4; Appendix B.2"},{"comment":"The almost-everywhere results are proved for independently varying coefficients α^(i,j)_k. In the benchmarked instantiation, however, these coefficients are produced by Eq. (14) from shared matrices W^(k), vectors v^(k), and input features. The image of this map is typically a measure-zero subset of the full coefficient space, so Propositions 3 and 4 do not automatically transfer to the architecture actually trained in Section 6. The paper notes that softmax attention violates the genericity condition but does not verify that its own Eq. (14) satisfies it. The sentence 'A neural network can then approximate such a function' is not sufficient; the manuscript should either prove a suitable genericity property for Eq. (14), state an explicit assumption under which the transfer holds, or present the experimental instantiation as a heuristic whose theoretical guarantees are open.","section":"Section 6, Eq. (14)"}],"minor_comments":[{"comment":"The notation W(i,j) X_{j,:} is dimensionally inconsistent if X_{j,:} is a row vector; please clarify whether X_{j,:} denotes a column vector or transpose the product.","section":"Section 3, Eq. (7b)"},{"comment":"The displayed formula for the entries of W^(k) appears to have a typo: solving a^(k) W^(k)=b^(k) requires a denominator involving the input dimension d (or a similar normalization), not the output dimension c as written. Please check and correct.","section":"Appendix B.1, proof of Proposition 1"},{"comment":"The coefficient superscripts in Eq. (18) and Eq. (19) are not consistently matched with the generic x_p,x_q notation used in the lemma; please make the pairing of coefficients with the two multisets explicit.","section":"Appendix B.2, Lemma 2"},{"comment":"The phrase 'injective on multisets' should be defined precisely: is the map over pairs (element, multiset) or over multisets only, are empty multisets allowed, and are repeated elements in a multiset permitted? These choices directly affect the validity of Proposition 3.","section":"Section 4"},{"comment":"The cross-references in the hyperparameter tables are inconsistent: Table 6's caption refers to 'Table 3' but the entries correspond to Table 2, and Table 7's caption refers to 'Table 4' but the entries correspond to Table 3.","section":"Appendix C.2"},{"comment":"There is a typo in the affiliation: 'Lamarr Insitute' should be 'Lamarr Institute'.","section":"Title page"}],"recommendation":"major_revision","confidential_remarks":"The main weakness is the theoretical section: Proposition 3 is false as stated and Proposition 4 has a non-rigorous proof with missing hypotheses. These are repairable with added assumptions and a corrected genericity argument, so I do not recommend rejection. The experimental part is solid, but the benchmarked instantiation is not covered by the theorems; the authors should either prove the needed transfer or explicitly soften the paper's claims. I would also advise the editor that the abstract should be revised to reflect the repaired statements before acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things before anything else. The LMGC framing is a genuinely useful way to see a lot of linear message passing as one object, and the paper is honest that the MIMO-GC itself is just the Bruna et al. extension written in tensor form. But the headline theorems are not correct as stated: Proposition 3 fails when 0 is in X, because the multisets {0} and {0,0} both map to zero for every choice of α and W, so the \"almost every\" claim is empty. Proposition 4 similarly needs c≥2 and its appendix proof contains an unjustified step from coefficient-weighted sums to plain sums (Eq. 24). Both are fixable — assume 0∉X and c≥2, repair the proof — but the abstract currently overclaims.\n\nWhat the paper does well: the spectral derivation is clean, the multi-computational-graph interpretation is illuminating, and the experiments are thorough and consistently run across methods. The universality result (Table 1) is striking, though it is a single linear layer with more expressive capacity than the baselines. On ZINC and the heterophilic node tasks, LMGC is best or near-best across the board, so the empirical story is credible even if some gaps are within noise. The code is public.\n\nThe other soft spot is the gap between the a.e. guarantees and the actual instantiation. Propositions 3 and 4 treat the α coefficients as free continuous variables; the benchmarked LMGC computes α from a low-dimensional neural network (Eq. 14), whose image could be measure zero. The paper asserts that many φ_k satisfy the genericity condition and that a neural net can approximate them, but it does not prove the particular one does. This is a real limitation, though not fatal — it means the theory does not yet cover the exact architecture that was tested.\n\nBottom line: this is a synthesis worth reading, with a couple of broken but repairable theorems. If I were the editor, I would send it to review and ask for the fixes plus a sharper statement of what the theory does and does not cover. A good referee would be doing the authors a favor by catching the zero-vector case before publication.","headline":"Useful unifying framework for linear MPNNs, but the headline injectivity and independence theorems are false as stated and need repair before they support the abstract's claims.","tokens_in":20019,"tokens_out":2919,"would_cite":true,"duration_ms":29796,"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":"The paper derives the MIMO graph convolution directly from the convolution theorem and proves its localized form is injective on multisets for almost every edge-weight choice.","keywords":["graph neural networks","MIMO graph convolution","localized message passing","injectivity on multisets","linear independence","rank collapse","graph convolution theorem","heterophilic node classification"],"falsifier":"Compute the Jacobian rank of the coefficient map in Eq. (14) at random parameter initializations on a fixed small graph; if the map's image is contained in a measure-zero set, train the same instantiation to separate neighborhoods $\\{\\{x\\}\\}$ and $\\{\\{x,x\\}\\}$ and check whether the proof's generic injectivity actually survives under the shared-parameter coefficient map.","tokens_in":19017,"feed_emoji":"🕸️","tokens_out":14518,"duration_ms":128460,"temperature":0.7,"pith_summary":"Most graph neural networks build on a single-input, single-output graph convolution and extend it to multiple channels by applying the same filter channel by channel. This paper derives the multi-input, multi-output graph convolution directly from the convolution theorem and argues that the property that makes it general is operating on multiple computational graphs at once, equivalently giving each pair of nodes its own linear feature transformation. The authors localize that operation into a framework they call LMGC, which contains GCN, GAT, FAGCN, and similar message-passing layers as special cases. For almost every choice of edge weights, they prove an LMGC with one computational graph is injective on multisets, and with more than one computational graph the output representations are linearly independent. If the proofs carry over to training, a purely linear message-passing layer can match the multiset-discrimination power usually attributed to nonlinear networks like GIN while avoiding rank collapse from a single shared filter.","feed_headline":"Linear message passing is injective for almost any edge weights","feed_subtitle":"A localized MIMO convolution distinguishes multisets, keeps representations independent, and outperforms GNN baselines.","key_machinery":"The load-bearing object is the decomposition of the graph convolution into a sum over computational graphs. In the exact MIMO-GC, the graphs are the rank-one matrices $A^{(k)} = u_k u_k^\\top$ formed from Fourier eigenvectors; in the LMGC, they are arbitrary $K$ edge-weight matrices $\\tilde{A}^{(k)}$ with entries $\\alpha^{(i,j)}_k$, combined with shared channel-mixing matrices $W^{(k)}$. The expressivity proofs work by generic linear algebra: for any two distinct multisets, the difference of their LMGC updates is a linear combination of coefficient vectors, and the bad coefficient choices form kernels of fixed matrices, which are measure-zero sets. This almost-everywhere-in-coefficient-space mechanism lets the paper transfer multiset-injectivity and linear independence from nonlinear architectures to linear message passing.","core_discovery":"The paper's central claim is that the MIMO graph convolution has the form $\\Theta * X = \\sum_{k=1}^{n} A^{(k)} X W^{(k)}$, where $A^{(k)} = u_k u_k^\\top$ is a rank-one graph built from the $k$-th Fourier basis vector and $W^{(k)}$ is the corresponding channel-mixing matrix; equivalently, each ordered pair of nodes $(i,j)$ receives its own linear transformation $W^{(i,j)}$. Localizing the sum to neighbors yields the LMGC $x'_i = \\sum_{v_j \\in \\mathcal{N}_i} W^{(i,j)} x_j = \\sum_{k \\in [K]} \\tilde{A}^{(k)} X W^{(k)}$, with freely chosen edge weights $\\alpha^{(i,j)}_k$. The paper proves that for almost every choice of these coefficients and feature matrices, an LMGC with $K \\ge 1$ is injective on finite multisets, and with $K > 1$ the resulting representations are pairwise linearly independent. It further shows that polynomial filters and the GCN are MIMO-GCs with constrained filters, and that softmax-normalized attention scores form a measure-zero exception to the injectivity guarantee.","pith_inferences":["An implication the paper leaves implicit is that its own Eq. (14) instantiation may not inherit the almost-everywhere guarantees: because the coefficients are produced by a shared low-dimensional network, their image can be a measure-zero set, so the trained model's injectivity is an empirical rather than a proven property.","A concrete design rule follows from the paper's argument: choose coefficient maps with open image in $\\mathbb{R}^K$ (e.g., tanh or unconstrained outputs rather than softmax) so that the generic injectivity and independence results apply to the learned parameters.","The MIMO-GC universality result, which says any target output can be produced from any generic input on a fixed graph, suggests LMGCs could serve as a general-purpose node-wise transformation layer; a testable extension is to benchmark them on tasks requiring arbitrary node-to-node feature maps, with regularization to control the added flexibility."],"forward_implications":["A single linear LMGC layer can distinguish node-neighborhood multisets for almost every edge-weight choice, matching the multiset expressivity that was previously thought to require nonlinear feature transformations as in GIN.","Using $K > 1$ computational graphs yields pairwise linearly independent representations for almost every edge-weight choice, directly counteracting the shared component amplification that leads to over-smoothing and rank collapse.","Because LMGC contains GCN, GAT, FAGCN, and ACM as special cases, any improvement proven for LMGCs applies to all of these models whenever their particular coefficient maps satisfy the genericity condition.","Approximating the convolution directly in the MIMO case gives one architecture that, in the paper's experiments, reaches the lowest error on a universality task, ZINC graph regression, and six heterophilic node-classification datasets."],"supporting_citations":[{"why":"Supplies the spectral graph convolution and its polynomial localization, which the paper re-derives in the MIMO case.","marker":"[Hammond et al., 2011]"},{"why":"Establishes the standard per-channel-pair extension from SISO to MIMO spectral networks, the route the paper contrasts with its direct MIMO derivation.","marker":"[Bruna et al., 2014]"},{"why":"Defines the GCN as a first-order localization; the paper shows GCN is a single-computational-graph MIMO-GC and a special case of LMGC.","marker":"[Kipf and Welling, 2017]"},{"why":"Extends Chebyshev polynomial filters to the MIMO case with per-channel parameters, a precursor that the LMGC generalizes.","marker":"[Defferrard et al., 2016]"},{"why":"Defines GAT, which the paper identifies as an LMGC whose attention scores are constrained by the softmax normalization.","marker":"[Velickovic et al., 2018]"},{"why":"Establishes GIN and the Weisfeiler-Leman test as the standard for multiset injectivity, the property the paper proves for linear LMGCs.","marker":"[Xu et al., 2019]"},{"why":"Introduces FAGCN with tanh edge weights, a coefficient choice that avoids the softmax measure-zero set and serves as a heterophilic baseline.","marker":"[Bo et al., 2021]"},{"why":"Introduces GATv2, the paper's main attention baseline and the concrete example of softmax-normalized scores lying in a measure-zero set.","marker":"[Brody et al., 2022]"},{"why":"Supplies the rank-collapse analysis that the paper connects to shared component amplification across feature channels.","marker":"[Roth and Liebig, 2023]"},{"why":"Provides the earlier result that multiple computational graphs can ensure linearly independent representations, which the paper's Proposition 4 extends to almost every edge-weight choice.","marker":"[Roth et al., 2024]"}],"fun_headline_variants":["Almost any edge weights yield injective graph convolutions","MIMO graph convolution: per-pair filters, injective by default","Localized MIMO convolution gives independent representations","Each node pair gets its own filter: MIMO graph convolution","Graph nets with per-pair filters are almost always injective"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The almost-everywhere guarantees hold when edge-weight coefficients and feature-matrix entries vary as independent continuous parameters, the feature universe is countable, and the output dimension is at least two; the paper's own benchmarked instantiation (Eq. 14) computes its edge weights from a shared low-dimensional network whose image can be a measure-zero set, so the guarantees do not automatically transfer to the architecture actually trained in Section 6.","fun_headline_variants_meta":{"raw":{"variants":["Almost any edge weights yield injective graph convolutions","MIMO graph convolution: per-pair filters, injective by default","Localized MIMO convolution gives independent representations","Each node pair gets its own filter: MIMO graph convolution","Graph nets with per-pair filters are almost always injective"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001117,"raw_usage":{"total_tokens":4667,"prompt_tokens":977,"completion_tokens":3690,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":593,"completion_tokens_details":{"reasoning_tokens":3608}},"tokens_in":593,"tokens_out":3690,"duration_ms":27796,"temperature":1.0,"reasoning_tokens":3608,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:55:27.180773+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the Jacobian rank of the coefficient map in Eq. (14) at random parameter initializations on a fixed small graph; if the map's image is contained in a measure-zero set, train the same instantiation to separate neighborhoods $\\{\\{x\\}\\}$ and $\\{\\{x,x\\}\\}$ and check whether the proof's generic injectivity actually survives under the shared-parameter coefficient map.","supporting_citations":[{"cited_title":"Wavelets on graphs via spectral graph theory","cited_arxiv_id":null,"evidence_quote":"Supplies the spectral graph convolution and its polynomial localization, which the paper re-derives in the MIMO case."},{"cited_title":"Spectral networks and locally connected networks on graphs","cited_arxiv_id":null,"evidence_quote":"Establishes the standard per-channel-pair extension from SISO to MIMO spectral networks, the route the paper contrasts with its direct MIMO derivation."},{"cited_title":"Kipf and Max Welling","cited_arxiv_id":null,"evidence_quote":"Defines the GCN as a first-order localization; the paper shows GCN is a single-computational-graph MIMO-GC and a special case of LMGC."},{"cited_title":"Convolutional neural networks on graphs with fast localized spectral filtering","cited_arxiv_id":null,"evidence_quote":"Extends Chebyshev polynomial filters to the MIMO case with per-channel parameters, a precursor that the LMGC generalizes."},{"cited_title":"Graph attention networks","cited_arxiv_id":null,"evidence_quote":"Defines GAT, which the paper identifies as an LMGC whose attention scores are constrained by the softmax normalization."},{"cited_title":"How attentive are graph attention networks? In The Tenth International Conference on Learning Representa- tions, Virtual Event, April 25-29,","cited_arxiv_id":null,"evidence_quote":"Introduces GATv2, the paper's main attention baseline and the concrete example of softmax-normalized scores lying in a measure-zero set."},{"cited_title":"Rank collapse causes over-smoothing and over-correlation in graph neural networks","cited_arxiv_id":null,"evidence_quote":"Supplies the rank-collapse analysis that the paper connects to shared component amplification across feature channels."}],"review_version":1}