{"id":"0df25561-efcd-43f4-a2b7-3b9d92b165d2","arxiv_id":"2508.20597","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"Local Virtual Nodes placed at high-centrality regions, with shared trainable embeddings, alleviate over-squashing and improve GNN classification performance.","lead":"This paper introduces Local Virtual Nodes, small groups of trainable helper nodes added around high-centrality nodes in a graph, to give graph neural networks extra pathways around bottlenecks. The method improves accuracy on several graph and node classification benchmarks and reduces effective resistance between non-central nodes.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Centrality-based placement is never ablated; LVN gains may come from added capacity rather than bottleneck targeting.","rationale":"The reader's weakest assumption was that centrality reliably identifies bottleneck regions. My concern is adjacent but more operationally precise: even if centrality does identify bottlenecks, the paper provides no ablation showing that centrality-based selection matters. The same experimental machinery can resolve this by randomizing the selection while holding all other factors fixed. If the method performs equally well with random placement, then the 'local bottleneck targeting' framing is unsupported, though the method could still be useful as a general virtual-node augmentation. This does not overturn the paper's core empirical finding, but it changes what the paper has actually demonstrated. Other issues noted by the reader (missing hyperparameter grid, lack of error bars for structural metrics, overstated topology preservation) are real but secondary; the centrality ablation is the single most load-bearing missing control because it tests whether the proposed placement mechanism contributes anything beyond added model capacity. The paper's own conclusion admits the centrality step is 'crucial' and earmarks it for future work, which strengthens the need for this check. The verdict remains CONDITIONAL: the paper should be accepted only if the authors add this selection ablation or explicitly soften the bottleneck-placement claim.","tokens_in":19106,"tokens_out":4880,"duration_ms":62189,"concrete_test":"Using the released repository, reproduce the Table III/IV configurations and add one controlled arm: replace top-centrality selection with uniform random selection of ns nodes, keeping the same ns, nc, directed/undirected strategy, embedding sharing, training splits, early stopping, and evaluation protocol. Run this on REDDIT-BINARY and IMDB-BINARY, where LVN gains are largest, across the same 50 splits. If random placement matches the reported mean accuracy within the published 95% confidence intervals, the centrality/bottleneck story is not load-bearing. If random placement is significantly worse, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that LVNs placed by centrality measures target bottleneck regions and thereby improve connectivity and task performance. The load-bearing link is that the choice of which nodes receive LVN groups is what drives the gains. This link is never directly tested: every experiment compares centrality-selected LVNs against non-augmented GCNs and rewiring baselines, but there is no control with random node selection or with low-centrality selection at the same ns, nc, and trainable-embedding budget. Because LVNs add ns×nc trainable virtual nodes and shared embeddings, standard GCN/rewiring baselines do not control for added capacity. The structural analyses in Sections V-E and V-F also only use centrality-based placement, so they cannot distinguish 'LVNs help anywhere' from 'LVNs help specifically at bottlenecks'. The paper itself flags this limitation in Section VI: 'determining the set of nodes to replace with virtual node groups is a crucial part of our algorithm ... In future work, we aim to replace this step with learnable modules ... rather than centrality-based heuristics.' Thus the centrality heuristic is load-bearing and unvalidated by the presented experiments. A secondary, similarly unablated mechanism is the trainable shared embedding: without comparing against fixed random embeddings, the claim that shared trainable embeddings enable long-range communication remains an interpretation, not a demonstrated effect.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This manuscript proposes Local Virtual Nodes (LVNs), an augmentation that replaces a set of high-centrality nodes with groups of virtual nodes. Each LVN inherits the edges of the original central node, and LVNs receive trainable embeddings shared across different groups. The authors argue that this creates local pathways around bottlenecks and enables long-range communication via shared embeddings without global rewiring. They evaluate with a GCN backbone on six graph classification and six node classification datasets, compare against rewiring baselines (DIGL, SDRF, FoSR, BORF, LASER), PANDA, and Last Layer FA, and report total effective resistance and path-count improvements. The central empirical claim is that LVNs improve structural connectivity and downstream accuracy relative to these baselines.","tokens_in":19454,"tokens_out":5588,"duration_ms":62938,"significance":"The idea is simple and attractive: instead of rewiring globally or adding a complete-graph supernode, one can expand capacity at a small number of bottleneck candidate regions and keep the original topology otherwise intact. The paper includes useful structural analyses (effective resistance, path counts), reports 50-split confidence intervals, and releases code. If the mechanism were validated, this would be a practical, architecture-agnostic remedy for over-squashing. However, the two main mechanisms—centrality-based placement and shared trainable embeddings—are not isolated by ablations, so the current evidence does not establish that bottleneck targeting and trainable sharing are what drive the observed gains. The conclusion in Section VI itself identifies the centrality heuristic as crucial and unresolved, which strengthens the need for direct experimental control.","major_comments":[{"comment":"The paper's central claim is that placing LVNs at high-centrality nodes targets bottlenecks. This is never tested directly. All experiments compare centrality-selected LVNs against non-augmented GCNs or rewiring baselines; there is no control with random node selection or low-centrality selection at the same ns, nc, embedding budget, and training setup. Because LVNs add trainable parameters, the observed gains could arise from added capacity alone rather than from bottleneck targeting. The paper itself states in Section VI that 'determining the set of nodes to replace with virtual node groups is a crucial part of our algorithm' and proposes future learnable selection. I request an ablation with random, low-centrality, and (if feasible) uniform node selection under identical resource budgets, showing that centrality placement outperforms these controls.","section":"IV.A, V, VI"},{"comment":"The second mechanism, shared trainable LVN embeddings, is also not isolated. No comparison is made against fixed random embeddings, per-group non-shared embeddings, or LVNs initialized with copied central-node features. The embedding analyses in Section V.G show only that embeddings change during training and that task-supervised embeddings improve an MLP on the same train/test splits; they do not demonstrate that sharing or trainability per se enables long-range communication. To support the abstract's claim that 'trainable LVN embeddings shared across selected central regions facilitate communication,' please add ablations: (a) fixed random embeddings, (b) non-shared trainable embeddings, and (c) shared trainable embeddings, all with the same ns and nc.","section":"IV.C, V.G, VI"},{"comment":"The reported hyperparameters are incomplete. The manuscript never states the selected ns, nc, centrality function, replace/add mode, or edge strategy for any dataset, although the captions of Figures 6-7 note that the number of LVNs is tuned. Without these values and the search procedure, the experiments are not reproducible, and it is impossible to judge whether the comparison is fair—for example, whether LVN's good results rely on more extensive tuning than the baselines. Please add a table with per-dataset configurations and the tuning protocol.","section":"V.C, Tables III-IV"},{"comment":"Some headline comparisons are not supported by the reported intervals. For example, on MUTAG, LVN (Directed) is 84.778 ± 2.902 versus PANDA 83.000 ± 1.876; on COLLAB, LVN (Undirected) is 71.520 ± 0.661 versus LASER 71.880 ± 0.567. These error bars overlap substantially. The text states that the method 'outperforms ... by a large margin' and 'significantly improve performance'; please either provide paired statistical tests across the 50 splits or temper the claims to the datasets where the intervals are separated. The current wording overstates the evidence.","section":"Tables III-IV"}],"minor_comments":[{"comment":"The notation [N] is defined as {0, 1, 2, ..., N}, which is non-standard and inconsistent with the later use of [ns] and [nc] as index sets. Please use a consistent convention (e.g., {1, ..., N}).","section":"III"},{"comment":"The second union in Eq. (8) connects all pairs of LVNs between adjacent central nodes, creating a complete bipartite subgraph between the two groups. Please clarify whether this is intended and how the directed edge distribution strategy modifies this formalization.","section":"IV.B, Eq. (8)"},{"comment":"The mutual-similarity analysis concludes that embeddings are distinct 'not due to random initialization.' However, random vectors in high dimension also tend to have near-zero cosine similarity; this analysis does not distinguish learned diversity from initialization. A comparison against the initial embedding distribution would be more informative.","section":"V.G.2"},{"comment":"The discriminative-power experiment uses task-supervised LVN embeddings as MLP inputs and trains the MLP on the same labels. This makes the improvement over raw input features difficult to interpret as 'structural information.' Please include a baseline with random pre-trained embeddings and with embeddings from a non-augmented GCN trained under the same protocol.","section":"V.G.3, Table V"},{"comment":"Reference [40] has an incomplete author name ('U. B. and'); please correct the citation.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The manuscript has a useful empirical proposal and releases code, but the main interpretation depends on two unablated ingredients: centrality-based placement and shared trainable embeddings. The authors themselves flag the centrality heuristic as crucial future work. I would require the ablations described in the major comments before acceptance, along with a complete hyperparameter table. The statistical overstatement around overlapping confidence intervals should also be corrected."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper does one genuinely new thing: it builds local virtual nodes as per-central-node groups with trainable embeddings shared across groups, plus a directed edge distribution and central-node removal. That construction isn't in the cited prior work, and it integrates with any GNN without modifying message passing. The empirical work is solid in scope: 50 random splits, 95% confidence intervals, multiple benchmarks, and structural analyses via effective resistance and walk counts. Code is released. The authors also flag the centrality limitation themselves in the conclusion, which is a good sign of honesty. If you work on over-squashing, this is worth reading as a practical, architecture-agnostic candidate remedy.\n\nBut the paper's central claim is that centrality-based placement is what makes LVNs work. That link is never tested. Every experiment compares centrality-selected LVNs against non-augmented baselines, so the gains could just come from added capacity, not from targeting bottlenecks. A control with random or low-centrality selection at the same node/edge budget would settle it. The trainable embeddings are similarly unablated: without comparing to fixed random embeddings, the claim that they enable long-range communication remains interpretation. The paper itself concedes the centrality step is crucial and imperfect, so the flaw is admitted—but it still means the causal story is unproven. Also, per-dataset hyperparameter values and tuning procedures are omitted, which hurts reproducibility, and the structural metrics in Figures 4–5 have no error bars. The 'global topology preserved' claim is also a bit overstated, since central nodes are removed and dense edges between LVN groups are added.\n\nThe soft spots are real but not fatal. The method may well work; the paper just doesn't isolate the mechanism. I'd want to see the ablations before trusting the interpretation, but the raw results are plausible and the construction is novel enough to merit referee time. It's a conditional accept, not a reject.\n\nThis paper is for GNN researchers specifically interested in over-squashing and practical structural modifications. It deserves a serious referee, but the referee should insist on centrality and embedding ablations, full hyperparameter reporting, and variance estimates for the connectivity metrics. If those come back, the contribution would be considerably stronger.","headline":"Useful new LVN construction with honest empirical work, but the centrality-placement mechanism is unablated and the causal claim remains unsupported.","tokens_in":19913,"tokens_out":1510,"would_cite":false,"duration_ms":17182,"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":"Local virtual nodes relieve GNN over-squashing without rewiring","keywords":["graph neural networks","over-squashing","local virtual nodes","message passing","graph rewiring","node centrality","effective resistance","long-range dependencies"],"falsifier":"Run the same LVN pipeline on graphs where true bottleneck regions are identified by curvature or effective resistance, with three placements: centrality, oracle bottlenecks, and random nodes. If random or oracle placements match or beat centrality, the centrality heuristic is not carrying the reported benefit; if centrality matches oracle, the method's placement assumption is confirmed.","tokens_in":19012,"feed_emoji":"🕸️","tokens_out":5210,"duration_ms":52472,"temperature":0.7,"pith_summary":"The paper claims that a lightweight preprocessing step—replacing a handful of high-centrality nodes with small groups of virtual nodes, each with a trainable embedding—reduces over-squashing in message-passing GNNs. The virtual nodes inherit the edges of the central node they replace, adding extra pathways exactly where bottlenecks are likely; shared trainable embeddings let distant central regions exchange information without adding layers. On graph and node classification benchmarks, the authors report that this approach outperforms graph-rewiring baselines and a width-expansion baseline while leaving original edges and global topology intact. If correct, it offers a plug-in remedy for long-range tasks that works with any GNN architecture.","feed_headline":"Local virtual nodes ease GNN over-squashing without rewiring","feed_subtitle":"Trainable virtual hubs at central nodes create new paths and bridge distant regions, beating rewiring baselines on benchmarks.","key_machinery":"The central object is the LVN group: for each of ns centrality-selected nodes, the original node is replaced by nc virtual nodes, each connected to the original node's neighbors (undirected strategy) or receiving all neighbor messages while sending to only a subset (directed strategy). The graph fed to the GNN is the induced subgraph after removing the central nodes, so no original edges are deleted. Each LVN is initialized with one row of a shared trainable embedding matrix P^{nc × D}; sharing across groups is what enables cross-region communication. The load-bearing formal identity is the augmented edge set, which merges the original edge set with copied central-node edges and, when two ce","core_discovery":"The central claim is that augmenting a graph with Local Virtual Nodes (LVNs) at central regions, then training GNNs with shared embeddings for those virtual nodes, mitigates over-squashing both structurally and representationally. Structurally, each selected central node is replaced by a group of nc virtual nodes that copy its connections, increasing the number of paths through bottleneck regions and lowering total effective resistance among non-central nodes. Representationally, each LVN starts from one of nc trainable embeddings shared across all central regions; because those embeddings update from feedback in multiple graph regions, they carry long-range information independent of layer","pith_inferences":["The placement heuristic—degree, PageRank, or label-propagation centrality—is doing causal work the paper credits to bottlenecks. Comparing LVN placement against oracle bottleneck locations would separate the heuristic's contribution from the mechanism itself.","Shared trainable embeddings act as a small distributed memory at selected hubs; this suggests LVNs could be combined with rewiring methods that intervene on different resources, such as adding edges elsewhere.","The smaller gains on node classification hint that over-smoothing, not over-squashing, dominates those local tasks; a principled LVN variant might need to suppress redundant messages within a group to avoid adding smoothing pressure.","The 'add' mode is structurally similar to additive positional encodings in transformers; a testable extension is to condition the shared embeddings on node features or graph structure rather than keeping them globally shared."],"forward_implications":["Any message-passing GNN can be augmented with LVNs as a preprocessing step plus an embedding table; no changes to the aggregation or update functions are required.","Graphs with community-like bottlenecks, such as social networks, stand to gain the most; datasets without node features still benefit because the trainable embeddings supply learnable signals.","The structural benefit is measurable before training: LVNs reduce total effective resistance and increase the number of walks between non-central nodes.","Because original edges are never removed, the method avoids the edge-level ambiguity that graph rewiring can create, making it safer for tasks where edge semantics matter.","Long-range information no longer has to travel layer by layer; shared LVN embeddings provide a shortcut that behaves like extra receptive field at constant depth."],"supporting_citations":[{"why":"Defines over-squashing and supplies the Last Layer FA baseline that motivates the work.","marker":"[7]"},{"why":"Provides the theoretical bound showing over-squashing depends on width and topology, justifying capacity-and-connectivity interventions.","marker":"[23]"},{"why":"The width-expansion baseline whose centrality-based node selection the method adapts.","marker":"[24]"},{"why":"SDRF, a curvature-based rewiring baseline the method is compared against.","marker":"[16]"},{"why":"FoSR, a spectral-gap rewiring baseline and source of the graph-classification experimental setup.","marker":"[17]"},{"why":"Supplies effective-resistance analysis of over-squashing and the GTR rewiring baseline used for structural evaluation.","marker":"[19]"},{"why":"Analyzes global virtual nodes through commute time and motivates the local alternative.","marker":"[34]"},{"why":"PageRank centrality, one of the three node-selection criteria.","marker":"[45]"},{"why":"Label-propagation centrality, the community-based node-selection criterion.","marker":"[46]"},{"why":"TUDataset benchmarks used for graph classification.","marker":"[48]"}],"fun_headline_variants":["Local virtual nodes ease GNN over-squashing at bottlenecks","Virtual hubs at central nodes ease GNN over-squashing","LVNs: local virtual nodes reduce GNN bottlenecks","No rewiring: local virtual nodes ease GNN over-squashing"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"Centrality scores reliably mark the regions where bottlenecks actually form, so placing LVNs at the most central nodes is assumed to be the right placement.","fun_headline_variants_meta":{"raw":{"variants":["Local virtual nodes ease GNN over-squashing at bottlenecks","Virtual hubs at central nodes ease GNN over-squashing","LVNs: local virtual nodes reduce GNN bottlenecks","No rewiring: local virtual nodes ease GNN over-squashing"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000899,"raw_usage":{"total_tokens":3719,"prompt_tokens":763,"completion_tokens":2956,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":507,"completion_tokens_details":{"reasoning_tokens":2897}},"tokens_in":507,"tokens_out":2956,"duration_ms":24309,"temperature":1.0,"reasoning_tokens":2897,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T14:57:45.502066+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the same LVN pipeline on graphs where true bottleneck regions are identified by curvature or effective resistance, with three placements: centrality, oracle bottlenecks, and random nodes. If random or oracle placements match or beat centrality, the centrality heuristic is not carrying the reported benefit; if centrality matches oracle, the method's placement assumption is confirmed.","supporting_citations":[{"cited_title":"On the bottleneck of graph neural networks and its practical implications,","cited_arxiv_id":null,"evidence_quote":"Defines over-squashing and supplies the Last Layer FA baseline that motivates the work."},{"cited_title":"On over-squashing in message passing neural networks: the impact of width, depth, and topology,","cited_arxiv_id":null,"evidence_quote":"Provides the theoretical bound showing over-squashing depends on width and topology, justifying capacity-and-connectivity interventions."},{"cited_title":"Panda: expanded width-aware message passing beyond rewiring,","cited_arxiv_id":null,"evidence_quote":"The width-expansion baseline whose centrality-based node selection the method adapts."},{"cited_title":"Understanding over-squashing and bottlenecks on graphs via curvature,","cited_arxiv_id":null,"evidence_quote":"SDRF, a curvature-based rewiring baseline the method is compared against."},{"cited_title":"FoSR: First-order spec- tral rewiring for addressing oversquashing in GNNs,","cited_arxiv_id":null,"evidence_quote":"FoSR, a spectral-gap rewiring baseline and source of the graph-classification experimental setup."},{"cited_title":"Understanding over- squashing in gnns through the lens of effective resistance,","cited_arxiv_id":null,"evidence_quote":"Supplies effective-resistance analysis of over-squashing and the GTR rewiring baseline used for structural evaluation."},{"cited_title":"Un- derstanding virtual nodes: Oversquashing and node heterogeneity,","cited_arxiv_id":null,"evidence_quote":"Analyzes global virtual nodes through commute time and motivates the local alternative."},{"cited_title":"The pagerank citation ranking: Bringing order to the web","cited_arxiv_id":null,"evidence_quote":"PageRank centrality, one of the three node-selection criteria."},{"cited_title":"Near linear time algorithm to detect community structures in large-scale networks,","cited_arxiv_id":null,"evidence_quote":"Label-propagation centrality, the community-based node-selection criterion."},{"cited_title":"Tudataset: A collection of benchmark datasets for learning with graphs,","cited_arxiv_id":null,"evidence_quote":"TUDataset benchmarks used for graph classification."}],"review_version":1}