{"id":"fbe3e341-b090-4121-89c4-04b6972007bb","arxiv_id":"2501.03113","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Ranking nodes with subgraph centrality and using those scores as structural features lets subgraph GNNs match full-bag performance with one or two marked subgraphs.","lead":"HyMN lets subgraph-based graph neural networks run on much larger graphs by marking only the few nodes ranked highest by subgraph centrality instead of marking every node. The same centrality numbers are fed into the network as extra node features, and the combination matches or beats much slower methods on several molecular and large-graph benchmarks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"SC-based sampling is load-bearing but its justification is only empirical: Eq. (3)'s perturbation bound uses row-sum walk counts, while Subgraph Centrality ranks closed-walk diagonals, leaving the top-k selection rule without a direct theoretical guarantee on real benchmarks.","rationale":"Agree with the reader's weakest_assumption. Observation 1 is an upper bound; upper bounds cannot justify choosing nodes that maximize a different quantity. The paper's own text concedes this ('only suggests, but does not necessarily entail') and supplies only synthetic correlations. The central empirical claim (HyMN is competitive with full-bag at a fraction of runtime) is well supported by the tables and released code; the concern is not about wrong numbers but about which component of the method deserves credit. Theorems 4.1-4.2 show separation examples, but not that SC ranking is necessary or sufficient for downstream performance. The proposed test would settle whether the SC-specific choice matters; if it does not, the method should be described as a centrality-based heuristic with CSEs doing much of the work, rather than a theoretically grounded synthesis. Verdict remains CONDITIONAL: the paper is strong empirically but should either prove or empirically verify the SC-to-perturbation link on real benchmarks.","tokens_in":34465,"tokens_out":18618,"duration_ms":190997,"concrete_test":"Keep the rest of HyMN fixed (CSE order K, T=2, same backbone) on MOLHIV and Peptides-Func, and re-run with three selection rules: (i) top-2 SC, (ii) top-2 by the Eq. (3) row-sum walk-count term Σ_j (A^{l-1})_{v,j} for l up to the network depth, and (iii) top-2 Katz. In addition, on a held-out sample of these datasets, compute the Spearman correlation between SC and the actual perturbation ||f(S_v)-f(G)|| for the trained GIN backbone. If (ii) or (iii) matches (i) in test ROC-AUC/AP, or if the SC-perturbation rank correlation is weak, the SC-specific closed-walk justification is not the operative mechanism and the central sampling rationale reduces to heuristic.","verdict_should_be":"UNCHANGED","load_bearing_attack":"HyMN's contribution is the claim that top-k Subgraph Centrality marking selects subgraphs that best approximate full-bag behavior. The theoretical anchor, Observation 1/Eq. (3), upper-bounds the marking-induced perturbation |y_G - y_Sv| by Σ_l λ_l Σ_j (A^{l-1})_{v,j} — the number of all walks leaving v. Subgraph Centrality in Eq. (1), however, is Σ_k β^k/k! (A^k)_{vv}, i.e. closed walks that return to v. An upper bound governed by outgoing walk counts does not imply that nodes with many closed walks induce the largest perturbations, and the paper says so explicitly in Section 3.2, bridging the gap with correlations in Table 1 on 100 synthetic ER graphs and an untrained GIN. The load-bearing step is therefore the assumption that high-SC nodes are precisely those whose marking produces perturbations aligned with task-relevant substructure counts on real molecular and social graphs. Nothing in the paper establishes this: no rank-correlation analysis on real test graphs, no comparison against the row-sum quantity in Eq. (3), and the ablation in Table 14 shows Katz Index (a row-sum centrality) performing nearly identically to SC, which is consistent with the closed-walk choice being incidental rather than essential. The synthetic counting experiment and OGB results support the usefulness of centrality-based sampling, but they do not single out SC as the mechanism claimed. If the selection rule is not actually carrying the improvement, the central 'walk-based centrality sampling' claim is an empirical heuristic, not a justified synthesis.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes HyMN, a method for scaling Subgraph GNNs by sampling a small number of node-marked subgraphs according to walk-based centrality, specifically Subgraph Centrality (SC), and by augmenting node features with Centrality-based Structural Encodings (CSE). The authors provide a perturbation analysis (Observation 1, Eq. (3)) linking marking-induced representation changes to walk counts, two expressiveness results (Theorems 4.1 and 4.2) on the non-comparability of CSE-augmented MPNNs and subsampled Subgraph GNNs, and a broad experimental evaluation on synthetic substructure-counting tasks, OGB molecular benchmarks, Peptides, MalNet-Tiny, Reddit-Binary, and ZINC. The experiments show that HyMN matches or exceeds the performance of full-bag Subgraph GNNs and learnable sampling policies while using only one or two marked subgraphs, at substantially reduced runtime.","tokens_in":34798,"tokens_out":10105,"duration_ms":95715,"significance":"If the claims hold, HyMN addresses a central scalability bottleneck of Subgraph GNNs, whose bag size grows linearly with graph size, and demonstrates that a simple, non-learnable preprocessing step can match or outperform learned sampling policies. The empirical work is a clear strength: the paper includes reproducible code, timing comparisons across multiple datasets, ablations on the effect of CSEs, comparisons with several centrality measures, and evaluations on graphs with up to thousands of nodes. The theoretical results, however, currently contain a serious defect in the proof of Theorem 4.1 that undermines one of the two expressiveness arguments, and the evidence for the specific choice of SC over other walk-based centralities is weaker than the text suggests. With the proof repaired and the centrality claims appropriately calibrated, the paper would be a solid contribution to efficient and expressive graph learning.","major_comments":[{"comment":"The proof of Theorem 4.1 contains two invalid steps. First, it states that the graphs Qt15 and Qt19, being 4-regular and of the same size, are 1-WL indistinguishable. This implication is false in general, and no specific justification is given for this particular pair. Second, the proof claims that 'the degree histogram in the 1-hop neighborhood of any node differs between the two graphs'; this is also incorrect because both graphs are 4-regular and vertex-transitive, so every node in both graphs has degree 4 and all its neighbors have degree 4, making these histograms identical. Consequently, the proof does not establish the theorem. Since Theorem 4.1 is one of the two non-comparability results used to motivate the hybrid combination of CSEs and subsampled marking, this is a load-bearing flaw. The authors should either provide a correct proof with a rigorously verified pair of graphs (including a demonstration of 1-WL indistinguishability and a valid distinguishing mechanism for the marked Subgraph GNN) or remove/restate the theorem with an appropriate caveat.","section":"Section 4.2 / Appendix D (Theorem D.2, proof of Theorem 4.1)"},{"comment":"The theoretical anchor for choosing Subgraph Centrality is Observation 1 / Eq. (3), which upper-bounds the marking-induced perturbation by the row-sum walk count S_l = Σ_j (A^{l-1})_{v,j}. Subgraph Centrality, however, is defined in Eq. (1) via the closed-walk diagonal entries (A^k)_{vv}. The paper explicitly acknowledges this gap in Section 3.2 and bridges it with empirical correlations in Table 1 on 100 synthetic ER graphs. The real-world evidence, however, does not single out SC: Table 14 shows that the Katz Index (a row-sum centrality) performs within one standard deviation of SC on MolHIV, Peptides-Func, and Peptides-Struct, and Table 12 shows that all three walk-based centralities (Katz, Communicability, SC) induce nearly identical average perturbations on MUTAG and NCI1. The statements in Section 3.2 that 'the walk-based SC stands out as a particularly promising candidate' and that SC 'performed as the best one' are therefore overstated. The evidence supports the broader family of walk-based centralities rather than the specific closed-walk form. The authors should temper the SC-specific claims, report significance tests or effect sizes for the Table 14 differences, and discuss the interchangeability of walk-based centralities, or provide a direct theoretical reason for preferring closed-walk counts over row-sum counts.","section":"Section 3.2, Eq. (3), Tables 12 and 14"}],"minor_comments":[{"comment":"The final sentence of Section 1 contains a typo: 'empirirical run-times' should be 'empirical run-times'.","section":"Section 1 (Introduction)"},{"comment":"There is a mismatch between the statement of Theorem 4.1 in the main text, which says 'top-1 Subgraph Centrality policy', and the appendix Theorem D.2, which says 'top-k Subgraph Centrality policy'. The proof appears to address only the top-1 case; if a top-k version is claimed, its proof should be given explicitly, or the theorem statement should be aligned.","section":"Section 4.2 / Appendix D (Theorem D.2)"},{"comment":"The convergence condition for Subgraph Centrality is not made precise. The text writes '0 < α < 1/λ1, β > 0' but does not state the corresponding condition for β (for the exponential series with β=1, convergence holds for all finite graphs; a clarifying sentence would help).","section":"Equation (1)"},{"comment":"The algorithm computes CSE and estimates SC using a truncated sum over K terms, but the paper does not analyze the effect of the truncation on the top-k selection. A brief comment or sensitivity experiment on K would strengthen the presentation.","section":"Algorithm 1"}],"recommendation":"major_revision","confidential_remarks":"The empirical contribution of this paper is substantial and well-executed, and the method is clearly useful. However, the proof of Theorem 4.1 is demonstrably incorrect as written, and the paper overclaims the specificity of Subgraph Centrality relative to other walk-based centralities. Both issues are fixable within the manuscript's scope: the theorem can be repaired or removed, and the centrality claims can be calibrated to the evidence. I recommend major revision rather than rejection, given the strength and breadth of the experimental validation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a useful empirical paper. The idea is to use subgraph centrality to sample a small bag of node-marked subgraphs and to feed the same centrality as node features. With one or two marked subgraphs, the method beats full-bag subgraph GNNs and learned sampling policies on several OGB datasets, at a fraction of the runtime. The empirical work is broad and careful: code, timings, ablations, multiple backbones, and synthetic counting tasks.\n\nThe genuinely new pieces are the perturbation-based motivation and the two expressiveness theorems showing that centrality-based marking and centrality-based structural encodings are incomparable, so combining them is justified. The theorems are correct as far as I can see. The proof of Theorem 4.1 uses the fact that 4-regular same-size graphs are 1-WL indistinguishable; that is true, because on a regular graph the 1-WL colors never refine, so the reader's worry about an invalid general claim is unfounded.\n\nThe main soft spot is the gap between the perturbation bound and subgraph centrality specifically. Observation 1 bounds the marking-induced change by the number of walks leaving the marked node, while subgraph centrality sums closed walks that return to it. The paper acknowledges this gap and bridges it with empirical correlations on synthetic graphs and an untrained GIN. That is reasonable, but the load-bearing ranking rule is therefore an empirical heuristic, not something the theory pins down. It would be stronger to do the same correlation analysis on the real benchmarks. Also, the ablation in Table 14 shows Katz Index, a row-sum centrality, performing almost identically to subgraph centrality on real datasets, which suggests the closed-walk choice is not essential. The method still works; the story is a bit overclaimed in the title.\n\nThe paper is honest about its limitations. It does not hide the perturbation/SC gap. The empirical claims are supported by the tables. This deserves peer review. I would recommend acceptance with minor revisions to tone down the theoretical claims and to add a correlation check on real graphs.","headline":"A practical, well-tested subsampling scheme for Subgraph GNNs whose core intuition is supported empirically; the theoretical story is thinner than the abstract suggests, and the specific choice of Subgraph Centrality is not fully pinned down.","tokens_in":35324,"tokens_out":5913,"would_cite":true,"duration_ms":57347,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"Marking only the one or two most walk-central nodes makes Subgraph GNNs match — and sometimes beat — full-bag models and stronger baselines at a small fraction of the runtime.","keywords":["Subgraph GNNs","Subgraph Centrality","walk-based centrality","subgraph sampling","structural encodings","graph expressiveness","node marking","scalable graph learning"],"falsifier":"A concrete test: construct a graph pair in which the highest-SC node is a task-irrelevant universal hub and the distinguishing substructure lies entirely on low-SC nodes. If HyMN with $T=1$ cannot separate the pair while random marking averaged over seeds can, then the SC ranking — not the marking paradigm — is the load-bearing component; likewise, across real datasets, HyMN's gain over random sampling of equal bag size should track the rank correlation between SC-induced perturbations and task-relevant substructure counts, and a dataset where gain persists at near-zero correlation would refute the stated mechanism.","tokens_in":34300,"feed_emoji":"⚡","tokens_out":12661,"duration_ms":95200,"temperature":0.7,"pith_summary":"Subgraph GNNs gain expressive power over plain message passing by processing one subgraph per node, but the bag grows linearly in node count, making the model quadratic in cost. This paper argues that the whole bag is unnecessary: marking only the top-ranked nodes by Subgraph Centrality — a walk-based score counting closed walks through each node — leaves one or two marked subgraphs able to match, and sometimes beat, a full-bag Subgraph GNN on real-world benchmarks. The same walk counts, fed in as per-node structural encodings, recover discriminative power the marking alone does not provide. The strategy is supported by a perturbation bound showing marking shifts a message-passing representation in proportion to the number of walks leaving the marked node, and by experiments showing high-centrality marking produces the largest perturbations and the ones most correlated with substructure counts. If the claim is right, the main obstacle to Subgraph GNNs on large graphs — their quadratic cost — is removable with a cheap preprocessing step and no learned sampling.","feed_headline":"Mark the most central nodes and cut Subgraph GNN cost to a fraction","feed_subtitle":"Ranking by closed walks, one or two marked subgraphs match full-bag models and Transformers at a fraction of the runtime.","key_machinery":"The central object is Subgraph Centrality, $\\mathrm{SC}_v=\\sum_{k\\ge 0}(A^k)_{vv}/k!$, the discounted number of closed walks of every length through node $v$. It carries the argument twice over: as the sampling score, the top-$T$ nodes it ranks are the ones marked, with the paper's bound tying marking-induced perturbation to the number of walks leaving the marked node; and as the structural encoding, its addenda $(A^k)_{vv}/k!$ (proportional to degree at $k=2$, incident triangles at $k=3$) are concatenated onto node features as the CSE. The connection between a bound that counts all walks and a score that counts only closed walks is bridged empirically in Section 3.2. The engineering trick that makes the method cheap is that the bag of subgraphs is never materialized: marks live in a feature tensor processed by a custom equivariant message function, so memory and runtime scale with $T$, not $N$.","core_discovery":"HyMN's central claim is that Subgraph Centrality, $\\mathrm{SC}_v=\\sum_{k\\ge 0}(A^k)_{vv}/k!$, identifies the subgraphs whose inclusion in a node-marking bag matters most, so the bag can be cut from $N$ subgraphs to a fixed small number $T$ by marking the $T$ highest-scoring nodes. The paper justifies the choice in two steps: a perturbation bound (Observation 1) shows that adding a marked subgraph changes an MPNN's output by at most a quantity growing with the total number of walks from the marked node, and experiments on MUTAG, NCI1, and random graphs show that max-SC marking yields the largest representation changes, with perturbation magnitudes most correlated with triangle, 4-cycle, path, and star counts (Pearson correlations around 0.95). Because Subgraph Centrality itself counts only closed walks while the bound counts all walks, the paper treats the alignment as an empirical finding. On the architectural side, HyMN augments node features with Centrality-based Structural Encodings, the power-series addenda $(A^k)_{vv}/k!$, and proves via two incomparability theorems that CSE-enhanced MPNNs and top-SC-subsampled Subgraph GNNs each separate graph pairs the other cannot, so the hybrid strictly extends both. Empirically, HyMN with $T=1$ or $2$ matches or beats full-bag Subgraph GNNs, the learned Policy-Learn policy, and several Graph Transformer baselines on OGB, ZINC, Peptides, MalNet-Tiny, and Reddit-Binary, at a fraction of their runtime.","pith_inferences":["Editorial extension: the paper's results suggest the expressive content of a node-marking bag concentrates in a few diagnostic nodes, so similar top-$k$ selection with other cheap scores (motif counts, spectral centrality) could transfer to subgraph architectures beyond node marking.","Editorial extension: Observation 1 bounds perturbation by total walks leaving the marked node, while Subgraph Centrality counts only closed walks; a Katz-style total-walk score matching the bound exactly could outperform SC precisely on graphs where open and closed walk counts diverge.","Editorial extension: since CSEs are closed-walk counts up to length $K$, task sensitivity to long cycles should track the required $K$; tuning $K$ per dataset instead of fixing it could open a further accuracy-efficiency trade-off.","Editorial extension: HyMN's fixed bag is deterministic, which removes variance at the cost of exploration; a natural variant would mark top-SC nodes deterministically and add a few random marks when the centrality ranking is flat, since the paper notes that ties in centrality must sometimes be broken arbitrarily."],"forward_implications":["Subgraph GNNs become applicable to graphs tens to hundreds of times larger than full-bag methods can process, because runtime and memory now scale with a fixed bag size ($T=1$ or $2$) instead of the node count.","On the OGB molecular benchmarks the method beats the full-bag Subgraph GNN and the learned Policy-Learn policy at equal bag size — MOLHIV reaches 81.01 ROC-AUC with $T=2$ — and matches Policy-Learn even without the centrality encodings.","On Peptides, MalNet-Tiny, and Reddit-Binary, HyMN ties or beats Graph Transformers and higher-order GNN baselines while being about six times faster in wall-clock training and inference on MalNet-Tiny.","Because CSE-augmented MPNNs and top-SC-subsampled Subgraph GNNs are provably incomparable in expressive power (Theorems 4.1 and 4.2), the hybrid strictly extends what either ingredient delivers alone.","In substructure-counting tasks, sampling the top-SC subgraphs reaches near-zero test error on triangles with far fewer subgraphs than random or min-centrality sampling."],"supporting_citations":[{"why":"Defines Subgraph Centrality, the closed-walk score HyMN uses both to rank marking candidates and to build its structural encodings.","marker":"(Estrada & Rodriguez-Velazquez, 2005)"},{"why":"Provides the Tree Mover's Distance stability bound that Observation 1 turns into the walk-count perturbation bound justifying high-centrality marking.","marker":"(Chuang & Jegelka, 2022)"},{"why":"Establishes the equivariant subgraph aggregation (DSS-GNN) architecture and node-marking bag construction that HyMN subsamples.","marker":"(Bevilacqua et al., 2021)"},{"why":"Introduces Policy-Learn, the learned sampling baseline HyMN must match without any learned selection.","marker":"(Bevilacqua et al., 2024)"},{"why":"Characterizes node-marking Subgraph GNNs and their expressiveness, the setting this paper scales.","marker":"(Papp & Wattenhofer, 2022)"},{"why":"Unifies walk-based centralities as discounted power series of the adjacency matrix, the family Subgraph Centrality belongs to.","marker":"(Benzi & Klymko, 2014)"},{"why":"Supplies the co-spectral vertex-transitive graphs used to prove that CSE-augmented MPNNs cannot subsume top-SC Subgraph GNNs (Theorem 4.1).","marker":"(Brouwer & Spence, 2009)"},{"why":"Frames structural encodings as a route to expressiveness beyond 1-WL, the role CSEs play in HyMN.","marker":"(Bouritsas et al., 2022)"}],"fun_headline_variants":["Walk-based centrality cuts Subgraph GNN cost to a fraction","HyMN: Match full-bag Subgraph GNNs with just 2 subgraphs","Few central subgraphs match full-bag GNNs and Transformers","One or two marked subgraphs rival full-bag Subgraph GNNs","Centrality sampling slashes Subgraph GNN runtime dramatically"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method load-bears on the assumption that the nodes with the most closed walks are exactly the nodes whose marking perturbs message-passing representations in ways aligned with task-relevant substructure counts — an alignment demonstrated empirically on synthetic and small real graphs, but not proven for the larger real benchmarks.","fun_headline_variants_meta":{"raw":{"variants":["Walk-based centrality cuts Subgraph GNN cost to a fraction","HyMN: Match full-bag Subgraph GNNs with just 2 subgraphs","Few central subgraphs match full-bag GNNs and Transformers","One or two marked subgraphs rival full-bag Subgraph GNNs","Centrality sampling slashes Subgraph GNN runtime dramatically"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000701,"raw_usage":{"total_tokens":3256,"prompt_tokens":1126,"completion_tokens":2130,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":742,"completion_tokens_details":{"reasoning_tokens":2044}},"tokens_in":742,"tokens_out":2130,"duration_ms":56411,"temperature":1.0,"reasoning_tokens":2044,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:53:06.451790+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete test: construct a graph pair in which the highest-SC node is a task-irrelevant universal hub and the distinguishing substructure lies entirely on low-SC nodes. If HyMN with $T=1$ cannot separate the pair while random marking averaged over seeds can, then the SC ranking — not the marking paradigm — is the load-bearing component; likewise, across real datasets, HyMN's gain over random sampling of equal bag size should track the rank correlation between SC-induced perturbations and task-relevant substructure counts, and a dataset where gain persists at near-zero correlation would refute the stated mechanism.","supporting_citations":[{"cited_title":"and Rodriguez-Velazquez, J","cited_arxiv_id":null,"evidence_quote":"Defines Subgraph Centrality, the closed-walk score HyMN uses both to rank marking candidates and to build its structural encodings."},{"cited_title":"and Jegelka, S","cited_arxiv_id":null,"evidence_quote":"Provides the Tree Mover's Distance stability bound that Observation 1 turns into the walk-count perturbation bound justifying high-centrality marking."},{"cited_title":"M., and Maron, H","cited_arxiv_id":null,"evidence_quote":"Establishes the equivariant subgraph aggregation (DSS-GNN) architecture and node-marking bag construction that HyMN subsamples."},{"cited_title":"Efficient subgraph gnns by learning effective selection policies","cited_arxiv_id":null,"evidence_quote":"Introduces Policy-Learn, the learned sampling baseline HyMN must match without any learned selection."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Characterizes node-marking Subgraph GNNs and their expressiveness, the setting this paper scales."},{"cited_title":"On the limiting behavior of parameter-dependent network centrality measures","cited_arxiv_id":"1312.6722","evidence_quote":"Unifies walk-based centralities as discounted power series of the adjacency matrix, the family Subgraph Centrality belongs to."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the co-spectral vertex-transitive graphs used to prove that CSE-augmented MPNNs cannot subsume top-SC Subgraph GNNs (Theorem 4.1)."},{"cited_title":"P., and Bronstein, M","cited_arxiv_id":null,"evidence_quote":"Frames structural encodings as a route to expressiveness beyond 1-WL, the role CSEs play in HyMN."}],"review_version":1}