{"id":"1924f3fc-c2b7-4ba9-8b44-c6130663023c","arxiv_id":"2412.00241","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"MEGA-GNN adds a parallel-edge aggregation stage inside each message passing layer, giving multigraph GNNs permutation equivariance and, when edge features are totally ordered, universality, with up to 13 percentage point F1 gains on money laundering detection.","lead":"Multigraphs are networks where the same two nodes can be connected by several edges, such as repeated bank transfers between two accounts. MEGA-GNN is a graph neural network that first summarizes parallel edges and then combines messages from distinct neighbors, and it matches or beats current methods on financial fraud detection benchmarks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Universality proof in Appendix A.3 is a sketch that omits how the two-stage layers simulate the BFS active/finished sets; if that transfer requires any mechanism beyond Eqs. (4)–(6), Theorem 3.2 is unproven.","rationale":"The paper's central contributions are the two-stage message-passing framework, its permutation equivariance (Theorem 3.1), and its universality under a strict total edge ordering (Theorem 3.2). Theorem 3.1 is straightforward and likely correct: the composition of permutation-invariant EdgeAgg and AGG with shared-weight message and update functions yields equivariance. The empirical results are plausible and supported by public code, though significance tests would strengthen them. The load-bearing weakness is the proof of Theorem 3.2 via Lemma 3.1. The appendix defers to Egressy et al.'s BFS-to-GNN simulation and only lists differences. The missing piece is nontrivial: the BFS algorithm has explicit control flow (active set, finished set) that is not present in the message-passing equations. In a standard GNN layer, all nodes send every round and all received messages are aggregated. Without an explicit construction showing how to make inactive nodes send a sentinel and assigned nodes ignore updates, the min-aggregation scheme would fail because the zero feature of unvisited nodes would dominate the min. This is fixable—one can use an active bit, a large sentinel, and a first-wins update rule—but the paper does not provide that derivation. The reader's weakest assumption identifies this same transfer as unverified, and I agree: the concern is not that the theorem is false, but that the current proof does not establish it. Because this is a gap in presentation rather than a demonstrated error, a conditional acceptance asking for a complete derivation (or an explicit assumption that the transfer holds) is appropriate. I do not see a reason to change the reader's verdict, so I recommend UNCHANGED.","tokens_in":88,"tokens_out":22033,"duration_ms":229941,"concrete_test":"Write out the explicit layer-1 and layer-2 constructions for a small connected multigraph (e.g., root r with two parallel edges to u with labels 1 and 2, plus an edge u->w with label 3, under a strict total order). Instantiate MEGA-GNN with EdgeAgg=min, AGG=min, and concrete MLPs for f and g. Check that after D layers the node features are unique and match Algorithm 1. In particular, verify that unvisited nodes either do not send or send a value larger than all valid IDs, and that assigned nodes do not overwrite their IDs. If this construction requires any operation not expressible in Eqs. (4)–(6)—for example, suppressing messages from non-active nodes based on a global round counter—then the BFS-to-GNN transfer is not exact and Theorem 3.2 is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The weakest link is Theorem 3.2/Lemma 3.1. Appendix A.3 explicitly says 'We are not going to reiterate the entire setup' and only sketches the differences from Egressy et al. (2024). A concrete gap exists: Algorithm 1 sends messages only from active nodes (lines 5–8) and freezes finished nodes (line 10). The MEGA-GNN layer in Eqs. (4)–(6) has no active/finished set: every node sends messages in every layer, and an unvisited node with feature vector 0 would send a 0-prefixed message that, under min-aggregation, beats every valid node ID. To make the simulation work, the proof must add an explicit mechanism whereby inactive nodes send a large sentinel and already-assigned nodes ignore further updates. The sketch does not state this, nor does it specify how a layer of the form h_ij = EdgeAgg({e_ijp}), a_j = AGG({f(x_i,h_ij)}), x_j = g(x_j,a_j) implements a conditional that depends on whether a node has been assigned in a previous round. If that conditional cannot be expressed by the two-stage layer as written, the transfer from Egressy et al. is not exact and Theorem 3.2 fails. Ties in real edge features are not the core issue—the theorem assumes a strict total order—but the proof itself is incomplete as presented.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes MEGA-GNN, a message-passing framework for attributed directed multigraphs in which each layer first aggregates parallel edges at artificial nodes (Eq. 4), then aggregates messages from distinct neighbors (Eq. 5), with optional bi-directional message passing (Section 3.4) and per-edge updates (Eq. 6). The main theoretical claims are permutation equivariance (Theorem 3.1) and universality under a strict total edge ordering (Theorem 3.2, via a BFS-based node-ID construction in Lemma 3.1). Empirically, the authors report minority-class F1 gains of up to about 13 percentage points over Multi-GNN and GFP baselines on four AML transaction datasets, comparable or slightly better F1 on the ETH phishing dataset, an ablation study, and a throughput comparison.","tokens_in":19041,"tokens_out":10492,"duration_ms":91426,"significance":"If the theoretical claims can be made rigorous, the paper would be a useful contribution to the relatively sparse literature on GNNs for multigraphs: it proposes a simple and natural two-stage aggregation, identifies a genuine limitation of prior work (loss of permutation equivariance in Multi-GNN's port numbering), and demonstrates substantial gains on financial transaction tasks. The authors ship code and use public datasets, and the ablations help isolate the contribution of bi-directional message passing and Ego-IDs. However, the current proofs of both central theorems are sketches, and the empirical significance testing is incomplete, so the contribution is not yet fully substantiated.","major_comments":[{"comment":"The proof of Theorem 3.1 misstates the defining property of a permutation-invariant function: it asserts ψ(ρ·E)=ρ·ψ(E) and similarly for φ, but for invariant functions the right-hand side should be ψ(E), not ρ·ψ(E). The theorem is nevertheless plausibly correct, but the proof needs to be rewritten as an equivariance argument for the two-stage layer, showing that h_{π(i)π(j)}, a_{π(j)}, and the updated edge features transform correctly under node and edge permutations. As written, the proof is not valid.","section":"A.2, Theorem 3.1"},{"comment":"The proof of Lemma 3.1 is a sketch that defers to Egressy et al. and does not establish that the two-stage layer defined by Eqs. (4)-(6) can simulate Algorithm 1. In particular, Algorithm 1 sends messages only from active nodes and prevents finished nodes from being updated, whereas the MEGA-GNN layer has no such conditional: all nodes send messages in every layer, and a node with initial feature 0 would send a 0-prefixed message that dominates min-aggregation. The proof needs to specify an explicit encoding (e.g., a sentinel for inactive nodes and a masking mechanism for finished nodes) and show that the layer functions f, g, and EdgeAgg can implement it. Without this, Theorem 3.2 is not established.","section":"A.3, Lemma 3.1 / Theorem 3.2"},{"comment":"Lemma 3.1 is stated only for connected multigraphs with a chosen root, but Theorem 3.2 claims universality without these qualifications. The proof does not explain how the root r is selected in the GNN or how disconnected graphs are handled. Please either add the connectedness and root assumptions to Theorem 3.2 or extend the proof to disconnected graphs (e.g., per-component BFS with component identifiers).","section":"Lemma 3.1 and Theorem 3.2"},{"comment":"The empirical claims of 'significantly outperforms' and 'surpassing' are not supported by statistical tests. On ETH (Table 3), MEGA-PNA (64.84±1.73) is within one standard deviation of Multi-PNA (64.61±1.40), yet Section 4.2 states that MEGA-PNA 'surpasses' Multi-PNA and 'achieves the highest F1 score'. The abstract more cautiously says 'on par' for ETH. Please add significance tests (e.g., paired tests across seeds) and make the claims in Sections 4.2 and 6 consistent with the abstract.","section":"Tables 2-3, Section 4.2"}],"minor_comments":[{"comment":"The ETH result is described as 'on par' in the abstract, 'surpassing' in Section 4.2, and 'slightly improving' in the conclusion; please use consistent wording.","section":"Abstract vs. Section 4.2/Conclusion"},{"comment":"The sentence defining the strict total order on edges via 'e(0)_ijp < e(0)_{i'j'p'}' is incomplete; it should specify how feature vectors are compared (e.g., lexicographic order) and should state that all edges have distinct feature vectors.","section":"Definition 3.1"},{"comment":"The claim 'first message-passing framework explicitly designed for multigraphs' overlooks Multi-GNN and ADAMM; the intended novelty is the two-stage aggregation within message passing, so please rephrase.","section":"Section 6"},{"comment":"The displayed chain 'X(l) = f(G(X,p) ≠ f(G(X,pσ)) = X̂(l)' is malformed; fix the parentheses and the equality chain.","section":"Appendix A.1, Eq. (14)"},{"comment":"GenAgg is applied to a SUM in the displayed formula, which is inconsistent with the text describing GenAgg as a scalar-valued aggregator; clarify whether the intended input is the multiset of edge features.","section":"Appendix B.2, Eq. (21)"},{"comment":"Tables 6 and 7 use commas as decimal separators (e.g., '43,66±0.54') while the main tables use periods; standardize the decimal separator.","section":"Tables 6-7"}],"recommendation":"major_revision","confidential_remarks":"The paper has a solid empirical contribution on AML and a clean architectural idea, but the two main theoretical proofs (Theorem 3.1 and especially Theorem 3.2 via Lemma 3.1) are not yet rigorous. The universality proof is a sketch that omits the active/finished-set mechanism needed for the BFS simulation, and the permutation-equivariance proof contains a formal error. The ETH claims also need statistical support and consistency. These gaps appear fixable within the manuscript's scope, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear Colleague,\n\nI read MEGA-GNN with a mixed verdict. The two-stage aggregation—parallel edges first, node-level second, via artificial nodes inside each message-passing layer—is a genuine architectural contribution. It fixes a real limitation of Multi-GNN (node-level aggregation only with port numbers) and ADAMM (collapsing parallel edges before message passing), and it preserves per-edge features, which is what enables the strong edge-classification results on AML. The bi-directional extension with reverse artificial nodes is a natural add-on, and the empirical gains on four AML datasets are consistent and large (e.g., MEGA-PNA 78.26 vs Multi-PNA 66.48 on Medium HI), with public code. The motivating sum-of-max vs max-of-sums example is clear and well-chosen.\n\nThe soft spots are real, and one is load-bearing. The universality theorem (Theorem 3.2) is not proven as written. Appendix A.3 says 'We are not going to reiterate the entire setup' and only lists differences from Egressy et al.'s BFS simulation. But the BFS algorithm they copy (Algorithm 1) maintains active and finished node sets; the MEGA-GNN layer in Eqs. (4)–(6) has no such state. A node that hasn't been assigned an ID yet still sends a message in every layer, and with min-aggregation a zero feature vector would dominate a legitimate ID. Making the simulation work requires an explicit sentinel or masking mechanism that the proof neither states nor shows the layer can compute. The theorem may be patchable, but as presented it does not follow. This is a serious gap for a headline claim. The reliance on Egressy et al. is legitimate, but the transfer is not demonstrated.\n\nOther issues are minor. The abstract says 'on par' for ETH while the body and conclusion say 'slight improvement'; the conclusion calls the framework 'first' for multigraphs, which is false because Multi-GNN and ADAMM came earlier; and 'significantly outperforms' in the abstract isn't backed by significance tests, only five-seed means and stds (though the AML gaps are large enough that I'd expect significance). The permutation equivariance proof in A.2 is sketchy but the argument is plausible.\n\nBottom line: the architecture, experiments, and writing are solid enough to warrant peer review. The paper would benefit from a revised proof (or a downgraded claim) for universality, plus cleanup of the inconsistencies. I'd send it to review with a request for major revision on the theory.","headline":"Genuinely new two-stage multigraph architecture with strong AML results, but the universality theorem rests on a proof sketch that omits the active/finished set mechanism.","tokens_in":19539,"tokens_out":6107,"would_cite":true,"duration_ms":50605,"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":"By aggregating parallel edges before combining neighbors, MEGA-GNN keeps permutation equivariance, gains universality under a strict total edge order, and improves minority-class F1 by up to 13.31 percentage points on financial…","keywords":["multigraph neural networks","multi-edge aggregation","message passing","permutation equivariance","universality","financial transaction graphs","anti-money laundering","edge classification"],"falsifier":"Run the proof's node-identification algorithm on a connected multigraph in which two parallel edges have identical feature vectors; with no strict total order the 'minimum edge label' step cannot separate proposals from the same neighbor, so duplicate node IDs become possible, and a universal approximation claim on that input would fail.","tokens_in":18557,"feed_emoji":"🔗","tokens_out":7779,"duration_ms":66736,"temperature":0.7,"pith_summary":"Most graph neural networks assume at most one edge between two nodes, and the two multigraph-specific models proposed so far each sacrifice something: one depends on an arbitrary edge-port numbering that breaks permutation equivariance, while the other flattens parallel edges into a single edge and loses per-edge predictions. MEGA-GNN instead performs a two-stage aggregation in every message-passing layer: parallel edges between the same pair of nodes are aggregated first, and messages from distinct neighbors are combined second, with a symmetric pass over reversed edges for directed graphs. The paper proves that this framework is permutation equivariant whenever both aggregators are permutation invariant, and universal when the edges admit a strict total ordering such as timestamps. If the proofs hold, this closes the gap between expressivity and symmetry for multigraph networks, and the reported experiments show up to 13.31 percentage-point improvements in minority-class F1 over prior state-of-the-art on anti-money-laundering transaction classification while matching it on phishing-account detection.","feed_headline":"Two-stage multigraph GNN gains up to 13.31 F1 points","feed_subtitle":"Aggregating parallel edges before neighbors yields permutation equivariance and, with ordered edges, universality.","key_machinery":"The load-bearing object is the artificial node placed on every directed pair that supports at least one edge, together with the two-stage layer built around it. Stage one aggregates the multiset of parallel edge features at the artificial node; stage two aggregates the resulting per-neighbor embeddings at the destination node; reverse edges get their own artificial nodes for bi-directional message passing. This construction does two jobs at once: because both aggregation functions are permutation invariant, the layer is equivariant by composition, and because the first stage can compute a minimum over edge labels, a strict total ordering on edges can drive a BFS-style unique node ID assignment, which is the step that upgrades the framework from equivariant to universal.","core_discovery":"The central claim is that placing an artificial node between each ordered pair of nodes that has at least one edge turns a multigraph's parallel edges into a well-behaved intermediate aggregation level. In each layer the model first computes one embedding per such pair by a permutation-invariant aggregation over the parallel-edge features, then aggregates these per-neighbor embeddings at the receiving node, and updates the original edge features individually, so no edge-level information is discarded. The paper states this two-stage scheme is permutation equivariant even without any edge ordering, and that with a strict total ordering of edges it is also universal: the first-stage aggregation can select the minimum edge label, which lets the network mimic a breadth-first search that assigns unique node identities, satisfying the known sufficient conditions for universal approximation of graph functions. Empirically, the framework instantiated with GIN, PNA, or GenAgg aggregators outperforms the prior port-numbered and collapsed-edge methods on minority-class F1 for illicit transaction detection, and matches the best prior method on phishing account detection.","pith_inferences":["A consequence the paper leaves implicit is that rounding or hashing edge features so parallel edges tie should erode the universality guarantee, and the size of that empirical drop would quantify how much of the AML gain comes from the strict-ordering assumption versus the two-stage structure itself.","The artificial-node construction is a general hierarchical aggregation pattern, so the same two-stage idea could transfer to hypergraphs or to graphs with grouped edge relationships, though the paper only draws that analogy in passing.","Because the asymptotic cost remains O(|E|d), equal to single-stage messaging, the added expressivity is not bought with extra asymptotic compute; this makes the framework a natural drop-in candidate for large transaction graphs.","The paper reports that Ego-IDs help edge classification but hurt node classification on the Ethereum data, suggesting that external identifier features and structural aggregation interact differently across tasks and deserve a dedicated study."],"forward_implications":["Multigraph edge classification becomes a first-class task: each original edge keeps its own latent features and can be labelled directly, instead of being collapsed before message passing.","Permutation equivariance and universality are not mutually exclusive: a strict total edge order such as a timestamp gives universality without breaking equivariance.","The same framework covers node, edge, and graph classification because every layer updates both node and edge representations, with a permutation-invariant readout for graph-level outputs.","On the four AML datasets the two-stage models raise minority-class F1 by 9.25 percentage points on average on the high-illicit sets and 13.31 on the low-illicit sets relative to the strongest prior method, and on the ETH phishing dataset they match the best prior model while clearly exceeding the collapsed-edge baseline."],"supporting_citations":[{"why":"Supplies the prior port-numbered multigraph method and the BFS-to-GNN simulation whose assumptions the universality proof transfers.","marker":"Egressy et al. (2024)"},{"why":"The collapsed-edge multigraph method that MEGA-GNN contrasts with, and a baseline in the ETH node classification experiments.","marker":"Sotiropoulos et al. (2023)"},{"why":"Gives the depth, width, and expressiveness conditions under which the paper derives universality in Theorem 3.2.","marker":"Loukas (2020)"},{"why":"Universal approximation theorem for MLPs used to avoid explicit construction of the layers in the node-ID proof.","marker":"Hornik et al. (1989)"},{"why":"Ego-IDs adopted in the edge classification experiments to strengthen node identification.","marker":"You et al. (2021)"},{"why":"GIN aggregation used as a base aggregator in both stages and as a simple-graph baseline.","marker":"Xu et al. (2019)"},{"why":"PNA aggregation used as both node-level and multi-edge aggregator and as a baseline.","marker":"Corso et al. (2020)"},{"why":"Releases the four synthetic AML datasets on which the edge classification gains are measured.","marker":"Altman et al. (2023)"},{"why":"Provides the Ethereum transaction dataset used for phishing node classification.","marker":"Chen et al. (2021)"}],"fun_headline_variants":["Multigraph GNN with two-stage aggregation beats SOTA by up to 13%","MEGA-GNN: Parallel edges first, then neighbors, wins","Two-stage multigraph message passing: up to 13% better F1","Permutation-equivariant multigraph GNN shows up to 13% gain","New two-stage GNN for multigraphs: up to 13% better"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The universality proof assumes that edges can be put in a strict total order by their features, so no two parallel edges tie, and that the earlier search-based node-identification construction carries over unchanged when the old port numbers are replaced by that ordering.","fun_headline_variants_meta":{"raw":{"variants":["Multigraph GNN with two-stage aggregation beats SOTA by up to 13%","MEGA-GNN: Parallel edges first, then neighbors, wins","Two-stage multigraph message passing: up to 13% better F1","Permutation-equivariant multigraph GNN shows up to 13% gain","New two-stage GNN for multigraphs: up to 13% better"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000912,"raw_usage":{"total_tokens":3944,"prompt_tokens":997,"completion_tokens":2947,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":613,"completion_tokens_details":{"reasoning_tokens":2845}},"tokens_in":613,"tokens_out":2947,"duration_ms":19579,"temperature":1.0,"reasoning_tokens":2845,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:34:47.494020+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the proof's node-identification algorithm on a connected multigraph in which two parallel edges have identical feature vectors; with no strict total order the 'minimum edge label' step cannot separate proposals from the same neighbor, so duplicate node IDs become possible, and a universal approximation claim on that input would fail.","supporting_citations":[{"cited_title":"Provably powerful graph neural networks for directed multigraphs","cited_arxiv_id":null,"evidence_quote":"Supplies the prior port-numbered multigraph method and the BFS-to-GNN simulation whose assumptions the universality proof transfers."},{"cited_title":"What graph neural networks cannot learn: depth vs width","cited_arxiv_id":null,"evidence_quote":"Gives the depth, width, and expressiveness conditions under which the paper derives universality in Theorem 3.2."},{"cited_title":"Identity-aware graph neural networks","cited_arxiv_id":null,"evidence_quote":"Ego-IDs adopted in the edge classification experiments to strengthen node identification."},{"cited_title":"Principal neighbourhood aggregation for graph nets","cited_arxiv_id":null,"evidence_quote":"PNA aggregation used as both node-level and multi-edge aggregator and as a baseline."},{"cited_title":"Realistic synthetic financial transactions for anti-money laundering models","cited_arxiv_id":null,"evidence_quote":"Releases the four synthetic AML datasets on which the edge classification gains are measured."}],"review_version":1}