Pith. sign in

REVIEW 3 major objections 23 references

Graph Neural Networks for Scalable and Transferable Node Centrality Approximation

T0 review · 3 major / 0 minor · reviewed 2026-07-13 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Training graph neural nets on mixed random-graph families yields transferable betweenness rankings and nearly 100× faster inference than exact algorithms.

desk verdict Clean empirical GNN ranking study with real mixed-training gains on synthetic families and honest closeness limits; real-world transfer write-up is ambiguous and novelty is incremental. read the letter →

arxiv 2607.09372 v1 pith:P5I4LI5H submitted 2026-07-10 cs.LG

Samra Sana , Giorgio Mantica , Saul Imbrici This is my paper
classification cs.LG
keywords GraphNeuralNetworkscentralityapproximationnoderankingtransferlearningrepresentationcomplexbetweennesscloseness
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper treats betweenness and closeness centrality as supervised node-ranking problems for message-passing graph neural networks. Exact centrality scores label the training graphs; the models are judged by how well they recover the induced ranking (Kendall tau). On held-out Erdős–Rényi graphs the networks reach tau about 0.85 for betweenness and 0.89 for closeness; a dedicated model trained at N = 5 000 still reaches tau = 0.938. The central claim is that a single model trained on a balanced mix of Erdős–Rényi, Barabási–Albert and community-partition graphs generalizes far better across those families than an ER-only model, especially on modular graphs. Closeness remains more fragile under topology shift and transfers poorly to real networks. Inference is up to 97.7 times faster than exact betweenness, so the learned rankers can be used wherever relative node importance matters more than absolute scores.

What carries the argument

Dual-pathway message-passing network (one pathway on A, one on Aᵀ) whose layer-wise MLP scores are fused by element-wise product, trained with pairwise ranking loss and evaluated by Kendall tau.

What would settle it

Train the identical mixed-distribution architecture on the same three generators, then measure zero-shot Kendall tau on a held-out suite of real networks whose average shortest-path lengths and modularity lie well outside the synthetic range; a collapse of betweenness tau below the ER-only baseline would falsify the transfer claim.

Watch

Extended reading notes

Core claim

Message-passing GNNs can learn transferable structural representations for betweenness ranking when they are trained on a deliberately mixed distribution of random-graph families; the same mixed training does not rescue closeness, which stays highly sensitive to community structure and real-world topology.

Load-bearing premise

That the fixed-depth message-passing layers and the three chosen synthetic generators already capture enough structural variety for the learned rankings to transfer to real networks whose diameters and modularity differ markedly.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 0 minor

Summary. The paper formulates betweenness and closeness centrality approximation as supervised node-ranking with message-passing GNNs, using exact NetworkX labels and Kendall τ evaluation. On held-out ER graphs the models reach τ ≈ 0.851 (betweenness) and 0.894 (closeness); a dedicated ER model at N = 5,000 reaches τ = 0.938. Dual-pathway product fusion is proposed for betweenness. The central empirical claim is that mixed training on ER + BA + GRP improves betweenness transfer across those families (GRP τ from 0.552 ER-only to 0.861 mixed), while closeness remains topology-sensitive. Zero-shot real-world results and up to 97.7× inference speedup over exact Brandes are also reported.

Significance. If the mixed-training transfer result holds under clearer real-world controls, the work is a useful, reproducible contribution to neural algorithmic approximation of centrality rankings. Strengths include exact supervision, held-out and cross-family evaluation, dual-pathway ablation (Table 3), Brandes/degree baselines (Tables 4–5), an N = 5,000 scalability run, and public code. The practical value is a fast ranking approximator whose training diversity is shown to matter for betweenness; the paper also cleanly documents that closeness is harder to transfer. Novelty is incremental relative to prior GNN centrality work, but the controlled isolation of training-distribution diversity is a clear, citable finding for the community.

major comments (3)
  1. §4.5 / Fig. 6: The load-bearing transfer claim is mixed training (§4.4: GRP betweenness τ 0.552 → 0.861). Real-world zero-shot numbers (τ ∈ [0.603, 0.782]) only say “models trained on synthetic graphs” and never state whether they come from the mixed model or the ER-only model (Table 1 treats mixed as a separate experiment). Report ER-only vs mixed τ on the same three networks, or state explicitly which model produced Fig. 6; without that, the headline transfer result is not stress-tested where the introduction and conclusion claim it matters most.
  2. Tables 4–5: On ER graphs degree centrality already reaches τ = 0.886 (betweenness) and 0.923 (closeness), above the GNN; mixed GNN beats degree on BA/GRP but the paper still frames GNN ranking quality as the primary success. Clarify when and why a learned model is preferable to degree (e.g., under topology shift, for non-degree-correlated centrality, or for amortized multi-graph inference), and report degree on the real-world networks in §4.5 so the practical gain is measurable.
  3. §4.6 Table 6 vs §4.7: Scalability is split across settings. Table 6 reports speedups and τ for models evaluated at N up to 1,000 (with a drop to τ = 0.712 at N = 500), while the N = 5,000 result (τ = 0.938) is a separately trained ER-only model with no corresponding inference-time comparison at that size. Align the claims: either report inference time and ranking quality for the N = 5,000 model against exact Brandes, or avoid presenting 97.7× and τ = 0.938 as a single continuous scalability story.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: supervised ranking against exact NetworkX labels on held-out graphs; reported τ and speedups are out-of-sample empirical measurements, not quantities forced by construction.

full rationale

This is a standard supervised GNN ranking paper. Exact betweenness/closeness from NetworkX supply independent ground-truth labels; models are trained with pairwise MarginRankingLoss and evaluated by Kendall τ on held-out synthetic graphs, cross-family transfers, and zero-shot real networks. Hyperparameters are chosen on a validation split—routine practice that does not make test rankings tautological. Mixed-distribution training is an empirical intervention (ER+BA+GRP vs ER-only) whose effect is measured on separate test graphs, not derived from a fitted constant renamed as a prediction. Speedups compare GNN inference wall-clock to exact Brandes/NetworkX computation on the same sizes. Related-work citations (Brandes, Maurya et al., GraphSAGE/GCN, etc.) provide context and baselines; none is a self-authored uniqueness theorem that forces the architecture or the transfer claim. There is no self-definitional loop, no fitted input sold as a first-principles prediction, and no renaming of a known closed-form result. Ambiguity about whether real-world numbers use the mixed or ER-only model is an experimental-reporting gap, not circularity. Score 0 is therefore the correct finding.

Assumptions & free parameters 5 free parameters · 5 assumptions · 1 invented entities

The work is empirical ML: it rests on standard GNN message-passing, exact centrality definitions, synthetic graph generators, and a ranking loss/metric. Free parameters are the usual architecture and training knobs plus generator settings. No new physical entities; the dual-pathway product fusion is an architectural design choice evaluated by ablation.

free parameters (5)
  • message-passing depth L = 5 / 7
    Chosen as L=5 (betweenness) and L=7 (closeness) based on expected small diameters and ablation; directly controls receptive field and reported transfer.
  • hidden size, dropout, weight decay, learning rate = 40; 0.4/0.2; 0.01/0; 1e-3
    Selected by validation Kendall τ grid search (Table 2); affect capacity and regularization of the reported models.
  • ER edge probability p and N = N=200, p=0.15 (primary)
    Primary training distribution fixed at N=200, p=0.15 (and N=5000, p=0.001 for scale experiment); defines the structural regime the models fit.
  • GRP community parameters (s, v, pin, pout) = s=20, v=5, pin=0.3, pout=0.05
    Hand-chosen modular regime used both for mixed training and transfer tests; shapes the community-bridge patterns the mixed model is credited with learning.
  • pairwise ranking sample size M and margin = M=N*20, margin=1.0
    M=N×20 pairs per graph and margin=1.0 define the supervision signal for ranking loss.
assumptions (5)
  • domain assumption Standard message-passing GNN update (aggregate neighbors then combine) can encode structural features relevant to shortest-path centralities.
    Invoked throughout §2.2 and §3.2 as the learning framework; not proved, only empirically tested.
  • domain assumption Kendall’s τ on node rankings is the appropriate success criterion for centrality approximation applications.
    Stated in abstract and §4.1; exact score recovery is de-emphasized by design.
  • standard math Exact betweenness and closeness from NetworkX (Brandes-style) provide correct supervision labels.
    §3.1.1 ground-truth labels; standard definitions (Eqs. 1–2).
  • ad hoc to paper ER, BA, and GRP generators with the chosen parameters are sufficiently diverse proxies for studying topology shift and real-world transfer.
    Dataset construction §3.1 and mixed-training experiment; limitations section acknowledges incomplete coverage of real networks.
  • ad hoc to paper Element-wise product of dual directional pathway scores is a suitable fusion for betweenness (vs sum or single pathway).
    §3.2.1 and ablation Table 3; product best in-distribution, sum better on GRP.
invented entities (1)
  • Dual-pathway GNN with product fusion for betweenness ranking
    purpose: Learn complementary incoming/outgoing structural scores whose agreement is intended to reflect brokerage on shortest paths.
    Introduced in §3.2.1 and Figure 2; evaluated by ablation but not independently validated outside this training setup.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Graph Neural Networks for Scalable and Transferable Node Centrality Approximation." pith.science (2026). https://pith.science/paper/P5I4LI5H

@misc{pith2026260709372,
  author       = {Pith},
  title        = {Pith review of: Graph Neural Networks for Scalable and Transferable Node Centrality Approximation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/P5I4LI5H}},
  note         = {Machine review of arXiv:2607.09372}
}
read the original abstract

Graph Neural Networks (GNNs) provide a learning-based framework for approximating graph quantities that are expensive to compute exactly. This paper investigates GNNs for scalable approximation of betweenness and closeness centrality, formulated as a node-ranking problem. Exact centrality values are used as supervision, and ranking quality is evaluated using Kendall's tau rank correlation. We study whether message-passing GNNs can learn transferable structural representations across different graph topologies rather than only fitting the distribution used during training. On unseen Erdos renyi graphs, the proposed models achieve tau = 0.851 for betweenness and tau = 0.894 for closeness. A large-scale betweenness model trained on graphs with N = 5,000 nodes achieves tau = 0.938, demonstrating scalability. Mixed-distribution training on Erdos renyi, Barabasi-Albert, and Gaussian Random Partition graphs improves betweenness transfer across graph families. In contrast, closeness centrality remains more sensitive to community-structured graphs and shows reduced transfer to real-world topologies. Finally, GNN inference achieves up to a 97.7x speedup over exact computation. These results show that mixed-distribution training can improve structural transfer in GNN-based centrality approximation, while identifying closeness centrality's sensitivity to topology as an open challenge.

Figures

Figures reproduced from arXiv: 2607.09372 by the authors.

Figure 1
Figure 1. Goal: approximate the ranking induced by exact betweenness and closeness centrality. 2 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Dual-pathway GNN architecture for learning betweenness-based node rankings. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Betweenness centrality approximation on unseen Erdős–Rényi test graphs. (a) [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Closeness centrality approximation on unseen Erdős–Rényi test graphs. (a) [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]
Figure 5
Figure 5. Figure 5: Cross-distribution generalization across graph topologies. (a) Betweenness cen [PITH_FULL_IMAGE:figures/full_fig_p016_5.png]
Figure 6
Figure 6. Figure 6: Zero-shot transfer to real-world networks. Models trained on synthetic graphs [PITH_FULL_IMAGE:figures/full_fig_p017_6.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

23 extracted references · 1 canonical work pages

  1. [1]

    Newman, Networks: An Introduction, Oxford University Press, 2010

    M. Newman, Networks: An Introduction, Oxford University Press, 2010

    2010

  2. [2]

    L. C. Freeman, A set of measures of centrality based on betweenness, Sociom- etry 40 (1) (1977) 35–41

    1977

  3. [3]

    Sabidussi, The centrality index of a graph, Psychometrika 31 (4) (1966) 581–603

    G. Sabidussi, The centrality index of a graph, Psychometrika 31 (4) (1966) 581–603

    1966

  4. [4]

    W. L. Hamilton, R. Ying, J. Leskovec, Inductive representation learning on large graphs, in: Advances in Neural Information Processing Systems, 2017

    2017

  5. [5]

    T. N. Kipf, M. Welling, Semi-supervised classification with graph convolu- tional networks, in: International Conference on Learning Representations, 2017

    2017

  6. [6]

    S. K. Maurya, X. Liu, T. Murata, Graph neural networks for fast node ranking approximation, ACM Transactions on Knowledge Discovery from Data 15 (5) (2021) 1–32

    2021

  7. [7]

    Brandes, A faster algorithm for betweenness centrality, Journal of Mathe- matical Sociology 25 (2) (2001) 163–177

    U. Brandes, A faster algorithm for betweenness centrality, Journal of Mathe- matical Sociology 25 (2) (2001) 163–177

    2001

  8. [8]

    D. A. Bader, S. Kintali, K. Madduri, M. Mihail, Approximating betweenness centrality, in: Proceedings of the 5th International Workshop on Algorithms and Models for the Web-Graph, Springer, 2007, pp. 124–137

    2007

Show all 23 references
  1. [9]

    Riondato, E

    M. Riondato, E. M. Kornaropoulos, Fast approximation of betweenness cen- trality through sampling, in: Proceedings of the 7th ACM International Con- ference on Web Search and Data Mining, 2014, pp. 413–422

    2014

  2. [10]

    Borassi, E

    M. Borassi, E. Natale, Kadabra is an adaptive algorithm for betweenness via random approximation, ACM Journal of Experimental Algorithmics 24 (2019) 1–35. 20

    2019

  3. [11]

    P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzalez, V. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, et al., Relational inductive biases, deep learning, and graph networks, arXiv preprint arXiv:1806.01261 (2018)

    2018 arXiv

  4. [12]

    T. Fan, L. Liu, W. Wang, Learning to identify high betweenness centrality nodes from scratch, in: Proceedings of the ACM International Conference on Information and Knowledge Management, 2019, pp. 559–568

    2019

  5. [13]

    Veličković, et al., The clrs algorithmic reasoning benchmark, Proceedings of Machine Learning Research 162 (2022) 22084–22102

    P. Veličković, et al., The clrs algorithmic reasoning benchmark, Proceedings of Machine Learning Research 162 (2022) 22084–22102

    2022

  6. [14]

    Zhang, X

    M. Zhang, X. Wang, L. Jin, M. Song, Z. Li, A new approach for evaluating node importance in complex networks via deep learning methods, Neurocom- puting 497 (2022) 13–27.doi:10.1016/j.neucom.2022.05.010

    2022 doi

  7. [15]

    Y. Zou, T. Li, Z.-f. Luo, Node centrality approximation for large networks based on inductive graph neural networks, arXiv preprint arXiv:2403.04977 (2024)

    2024 arXiv

  8. [16]

    Dachille, A

    J. Dachille, A. Rossi, S. K. Maurya, F. Mallmann-Trenn, X. Liu, F. Giroire, T. Murata, E. Natale, Brava-gnn: Betweenness ranking approximation via degree mass inspired graph neural network, arXiv preprint arXiv:2602.09716 (2026)

    2026

  9. [17]

    Yehudai, E

    G. Yehudai, E. Fetaya, E. Meirom, G. Chechik, H. Maron, From local struc- tures to size generalization in graph neural networks, in: Proceedings of the 37th International Conference on Machine Learning, 2020, pp. 10975–10986

    2020

  10. [18]

    Q. Wu, H. Zhang, J. Yan, D. Wipf, Handling distribution shifts on graphs: An invariance perspective, arXiv preprint arXiv:2202.02466 (2022)

    2022 arXiv

  11. [19]

    S. Gui, X. Li, L. Wang, S. Ji, Good: A graph out-of-distribution benchmark, in: Advances in Neural Information Processing Systems, 2022

    2022

  12. [20]

    A. A. Hagberg, D. A. Schult, P. J. Swart, Exploring network structure, dy- namics, and function using networkx, in: Proceedings of the 7th Python in Science Conference, 2008, pp. 11–15

    2008

  13. [21]

    Erdős, A

    P. Erdős, A. Rényi, On random graphs i, Publicationes Mathematicae 6 (1959) 290–297

    1959

  14. [22]

    Barabási, R

    A.-L. Barabási, R. Albert, Emergence of scaling in random networks, Science 286 (5439) (1999) 509–512. 21

    1999

  15. [23]

    M. G. Kendall, A new measure of rank correlation, Biometrika 30 (1–2) (1938) 81–93. 22

    1938

Pith tools

Reviewed July 13, 2026 · model on record in the stance chip above.