Graph Neural Networks for Scalable and Transferable Node Centrality Approximation Samra Sanaa,b,∗, Giorgio Manticaa , Saul Imbricia
arXiv:2607.09372v1 [cs.LG] 10 Jul 2026
a
Center for Nonlinear and Complex Systems, Università degli Studi dell’Insubria, Como, Italy b Data Science Institute, Hasselt University, Hasselt, Belgium
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 τ 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 Erdős– Rényi graphs, the proposed models achieve τ = 0.851 for betweenness and τ = 0.894 for closeness. A large-scale betweenness model trained on graphs with N = 5,000 nodes achieves τ = 0.938, demonstrating scalability. Mixeddistribution training on Erdős–Rényi, Barabási–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.7× 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. Keywords: Graph Neural Networks, centrality approximation, node ranking, transfer learning, graph representation learning, complex networks
∗
Corresponding author Email address: [email protected] (Samra Sana)
1. Introduction Graph Neural Networks (GNNs) have become an important class of learning systems for graph-structured data. By combining local message passing with trainable nonlinear transformations, GNNs can learn node representations that support tasks such as node classification, link prediction, graph classification, and ranking. Beyond standard prediction tasks, GNNs are increasingly used as neural approximators for graph algorithms, where the objective is to learn graph quantities that are expensive to compute exactly. Node centrality approximation is a natural and challenging problem in this setting. Centrality measures quantify the structural importance of nodes in a graph and are widely used in social, biological, transportation, communication, and recommendation networks [1]. Among them, betweenness centrality measures how often a node lies on shortest paths between other nodes and is associated with brokerage or control of information flow [2]. Closeness centrality measures how efficiently a node can reach the rest of the network [3, 1]. However, exact computation of these measures becomes expensive for large graphs, especially for betweenness centrality, which requires repeated shortest-path computations. This computational cost motivates learning-based approximation methods that can preserve centrality-induced node rankings while reducing inference time. In this work, we formulate betweenness and closeness centrality approximation as supervised node-ranking problems. Instead of reproducing exact centrality values, the goal is to learn the ranking induced by exact centrality measures, as illustrated in Figure 1. This formulation is suitable for many applications in which the relative importance of nodes is more relevant than the exact numerical centrality score.
Figure 1: Goal: approximate the ranking induced by exact betweenness and closeness centrality.
2
Message-passing GNNs provide a data-driven framework for learning such rankings directly from graph topology [4, 5]. Previous studies have shown that GNNs can approximate centrality measures efficiently [6]. However, an important question remains insufficiently understood: do GNNs learn transferable structural representations for centrality approximation, or do they mainly exploit properties of the graph distribution used during training? This question is particularly important because real-world networks often differ substantially from the synthetic graph families used for training. A model trained on homogeneous random graphs may not generalize to scalefree, community-structured, spatial, or biological networks. This paper investigates the scalability and transferability of GNN-based centrality approximation across synthetic graph families and real-world networks. We evaluate whether models trained on one graph distribution can generalize to structurally different networks, and whether mixed-distribution training improves robustness. The study considers Erdős–Rényi, Barabási– Albert, and Gaussian Random Partition graphs, together with zero-shot evaluation on real-world networks including the C. Elegans neural network, Email-Eu-Core, and the Western US power grid. The main contributions of this paper are as follows: 1. We formulate betweenness and closeness centrality approximation as supervised node-ranking problems using Graph Neural Networks. 2. We design and evaluate message-passing GNN models for learning centralitybased node rankings directly from graph topology. 3. We study cross-topology generalization across Erdős–Rényi, Barabási– Albert, and Gaussian Random Partition graphs. 4. We show that mixed-distribution training improves betweenness transfer, suggesting that structural diversity supports more robust graph representation learning. 5. We evaluate zero-shot transfer on real-world networks, including the C. Elegans neural network, Email-Eu-Core, and the Western US power grid. 6. We quantify the computational advantage of GNN-based approximation, showing up to a 97.7× inference speedup over exact betweenness computation.
3
2. Background and Related Work 2.1. Network Centrality Measures A network is represented as a graph G = (N , E), where N is the set of nodes and E is the set of edges connecting them. Centrality assigns a score to each node that reflects its structural importance. However, importance may correspond to different roles depending on the network and the application. Betweenness centrality measures how often a node lies on shortest paths between other nodes. For node i, it is defined as bi =
X σjk (i) j̸=k
σjk
,
(1)
where σjk is the total number of shortest paths between nodes j and k, and σjk (i) counts only those passing through node i [2]. A node with high betweenness acts as a broker; removing it can make many shortest paths longer or disconnect them entirely. Closeness centrality measures how efficiently a node can reach the rest of the network: N −1 ci = P min , (2) j dij where dmin ij is the shortest-path distance from node i to node j [1, 3]. A node with high closeness is located near the structural center of the network. Both measures depend on shortest-path computations across the graph and become computationally demanding as network size increases. Although efficient exact algorithms exist, their runtime remains a bottleneck for largescale networks in biology, infrastructure, communication, and social systems. This motivates approximation methods that preserve centrality-induced rankings while reducing computational cost. In this paper, centrality approximation is treated as a learning problem in which a neural model predicts the relative importance of nodes directly from graph topology. 2.2. Graph Neural Networks Graph Neural Networks extend neural-network learning to graph-structured data [4, 5]. Unlike multilayer perceptrons, which process input features independently, GNNs explicitly model relationships between nodes through
4
message-passing operations: (k) (k−1) : u ∈ N (v) , a(k) v = AGGREGATE ! hu (k) (k−1) , , , a(k) h(k) v v = COMBINE ! hv
(3) (4)
(k)
where hv is the representation of node v at layer k, and N (v) denotes the (L) neighbours of v. After L layers, the representation hv contains information from the L-hop neighbourhood of node v. Thus, increasing the number of layers enlarges the receptive field, allowing the model to encode broader structural information. Modern GNNs are commonly formulated within the Message Passing Neural Network framework, where node representations are iteratively updated through neighbourhood aggregation. Prominent examples include Graph Convolutional Networks, which use spectral-inspired aggregation operators, and GraphSAGE, which supports inductive learning through neighbourhood sampling. These architectures have shown strong performance in node classification, link prediction, graph representation learning, and ranking tasks. More recently, they have also been studied as neural approximators for graph algorithms, where the objective is to learn computationally expensive graph quantities from examples. This makes GNNs a suitable framework for approximating centrality-based node rankings. 2.3. Related Work Centrality approximation has traditionally been addressed using exact graph algorithms and sampling-based methods. Brandes algorithm remains the standard exact method for betweenness centrality [7], while later approximation approaches reduce computational cost by sampling source nodes, shortest paths, or graph substructures [8, 9, 10]. These methods provide theoretical or empirical efficiency gains, but their accuracy depends on the sampling budget and on the structural properties of the graph. A second line of work studies neural and graph-learning approaches for graph-theoretic and algorithmic problems. GNNs provide a natural framework for learning structural representations through message passing [5, 4, 11]. Prior work has shown that neural models can learn to identify highly central nodes [12], and Maurya et al. [6] proposed GNN models for fast approximation of betweenness and closeness centrality. More broadly, neural algorithmic reasoning investigates whether neural networks can learn algorithmic procedures such as shortest paths, sorting, and dynamic program5
ming [13]. This perspective is closely related to centrality approximation, since both betweenness and closeness depend on shortest-path structure. Recent work has further extended learning-based centrality approximation. Zhang et al. [14] proposed a deep-learning approach for evaluating node importance in complex networks, confirming the relevance of neural models for node-importance estimation. Zou et al. [15] proposed CNCA-IGE, an inductive encoder–decoder model for approximating closeness and betweenness centrality rankings using GraphSAGE, a variational graph autoencoder, and an MLP-Mixer decoder. Their approach emphasizes inductive representation learning across synthetic and real-world networks. Dachille et al. [16] introduced BRAVA-GNN, a recent betweenness-ranking model based on multihop degree-mass features and synthetic training graphs designed to improve generalization to high-diameter real-world networks. A third relevant direction concerns transferability and distribution shift in graph learning. GNNs are often trained and tested on graphs drawn from similar distributions, but their performance can degrade when graph topology changes [17, 18, 19]. This issue is particularly important for centrality approximation, because the structural meaning of node importance depends on global network topology. Recent centrality-approximation studies have addressed inductive learning and generalization, but the role of trainingdistribution diversity itself remains less explicitly isolated. In contrast to prior work, the present study focuses on training-distribution diversity as a factor governing transfer. We compare single-topology training with mixed-topology training across Erdős–Rényi, Barabási–Albert, and Gaussian Random Partition graphs, and show a quantified improvement in betweenness transfer on community-structured graphs. We also evaluate both betweenness and closeness centrality, showing that closeness is substantially more sensitive to topology shift. This indicates that transfer behaviour depends not only on the GNN architecture, but also on the centrality measure and the structural diversity of the training distribution. 2.4. Approximate Centrality Baselines The most widely used exact framework for betweenness computation is Brandes’ algorithm [7]. A common approximation strategy samples k pivot nodes and builds shortest-path trees only from those pivots, reducing the cost to approximately O(k · N · E). At small k, this approach is fast but less accurate; at larger k, its accuracy improves but its cost approaches that of exact computation. The performance of sampling-based methods therefore 6
depends strongly on the number and selection of sampled nodes. In practice, choosing an appropriate sampling budget requires balancing computational cost against ranking accuracy, and the optimal choice may vary substantially across network types. A much simpler baseline is degree centrality, which counts the number of edges incident to each node and can be computed very efficiently. On Erdős– Rényi graphs, degree centrality can be surprisingly competitive because highdegree nodes often lie on many shortest paths and tend to be close to other nodes. We include degree centrality as a baseline because it is computationally cheap and provides a useful reference point for learned approximation methods. We compare both sampling-based Brandes approximation and degree centrality against the proposed GNN models in Section 4.3. 3. GNN Architecture and Training This section presents the proposed GNN-based learning framework for centrality approximation, including dataset construction, model architecture, training procedure, and ranking-based supervision. 3.1. Dataset Construction All graphs are generated synthetically using NetworkX [20]. We consider three graph families that represent distinct structural regimes: homogeneous random connectivity, hub-dominated connectivity, and modular community structure. Erdős–Rényi (ER) graphs are generated with N nodes and edge probability p, where each possible edge is included independently with probability p [21]. ER graphs serve as the primary training distribution. In the main experiments, we use N = 200 and p = 0.15, giving an expected average degree of 29.9. ER graphs are generated as directed for betweenness centrality and undirected for closeness centrality. Barabási–Albert (BA) graphs are generated by preferential attachment with m = max(1, ⌊pN/2⌋) edges added per new node [22]. This produces scale-free networks with heterogeneous degree distributions and dominant hub nodes. Gaussian Random Partition (GRP) graphs are generated with mean community size s = 20, variance v = 5, intra-community edge probability pin = 0.3, and inter-community edge probability pout = 0.05. These graphs represent modular networks with explicit community structure. 7
These synthetic graph families allow controlled evaluation of how GNNlearned node representations transfer across structurally different network topologies. For the mixed betweenness experiment, we use a balanced dataset containing 533 ER graphs, 533 BA graphs, and 533 GRP graphs, for a total of 1,599 graphs. 3.1.1. Ground-Truth Labels For each graph, exact betweenness and closeness centrality values are computed using NetworkX and used as supervision for learning centralityinduced node rankings, with betweenness_centrality(normalized=True) and closeness_centrality. All labels for the primary N = 200 experiments are exact. A separate scalability experiment is also performed on graphs with N = 5,000 nodes. 3.1.2. Dataset Sizes and Splits All datasets are divided into training, validation, and test sets using a 70%–10%–20% split. The validation set is used for hyperparameter selection, while the test set is used only for final evaluation. Experiment
Graph types
Betweenness (primary) ER only Closeness (primary) ER only Betweenness (mixed) ER + BA + GRP (533 each) Betweenness (N = 5000) ER only
Total
Train
Val
Test
2000 5000 1599 300
1400 3500 1120 210
200 500 159 30
400 1000 320 60
Table 1: Dataset summary for all experiments. Primary experiments use N = 200 and p = 0.15.
The primary experiments use N = 200 because exact centrality labels can be computed efficiently for many graphs, enabling controlled training and evaluation. To assess scalability beyond this setting, we additionally train and evaluate a largescale betweenness model on graphs with N = 5,000 nodes.
3.2. Model Architecture The proposed models treat centrality approximation as a supervised graph representation learning problem for node ranking. For betweenness centrality, we use a dual-pathway GNN architecture that learns complementary representations
8
from outgoing and incoming graph structure, since shortest-path flow depends on directional connectivity. For closeness centrality, a single pathway is used because the model is trained on undirected graphs. The number of message-passing layers controls the receptive field of the learned node representations. In the primary ER setting with N = 200 and p = 0.15, shortest-path distances are typically small, and the graph diameter is expected to be only a few hops. Therefore, L = 5 provides sufficient neighborhood coverage for betweenness centrality while limiting oversmoothing. For closeness centrality, we use a slightly deeper model with L = 7, since closeness depends on aggregate distances from each node to the rest of the graph and can benefit from broader neighborhood aggregation. The ablation results in Section 4.2 show that increasing depth does not monotonically improve performance, indicating that L must balance receptive-field size, optimization stability, and robustness under topology shift.
Figure 2: Dual-pathway GNN architecture for learning betweenness-based node rankings. The first pathway processes the adjacency matrix A, while the second pathway processes the transpose AT . Each pathway produces an MLP score, and the final prediction is obtained by an element-wise product. For closeness centrality, only a single pathway is used.
3.2.1. Betweenness Centrality GNN Given a graph G = (N , E) with adjacency matrix A, the betweenness GNN processes both A and AT to learn direction-aware node representations as shown in Figure 2. The two pathways capture complementary information about outgoing
9
and incoming geodesic flow. The model uses L = 5 message-passing layers. At layer k, node representations are updated as X (k) h(k−1) + b(k) . (5) h(k) u v = normalize ReLU W u∈N (v) (1)
(2)
Each pathway produces layer-wise MLP scores, denoted by sk and sk . The final predicted centrality score for node i is computed as ! ! L L X X (1) (2) ŷi = sk ⊙ sk , (6) k=1
k=1
where ⊙ denotes element-wise multiplication. The element-wise product is used as a directional gating mechanism between the two pathways. Betweenness centrality depends on whether a node can simultaneously receive and forward shortest-path flow. A high score should therefore require agreement between incoming and outgoing structural representations. In contrast, summation can assign a high score even when only one pathway is active. The product encourages agreement between the two directional views and is evaluated against alternative fusion choices in the ablation study reported in Table 3.
3.2.2. Closeness Centrality GNN The closeness model uses a single pathway with L = 7 layers. Its final node score is obtained by summing the layer-wise MLP scores: ŷi =
7 X
sk .
(7)
k=1
The input includes a degree-normalized adjacency matrix Amod = D−1 A, which provides scale-normalized local connectivity and avoids zero feature vectors during training. Closeness is evaluated on undirected graphs to avoid degenerate rankings caused by unreachable nodes in sparse directed graphs.
3.3. Hyperparameter Selection Hyperparameters are selected by grid search on the validation set using mean Kendall τ as the selection criterion. The search includes learning rate, dropout, hidden size, and weight decay. The best configuration is then retrained and evaluated on the held-out test set.
10
Parameter
Betweenness
Closeness
Learning rate Dropout Hidden size Weight decay Epochs Batch size Train graphs Val graphs Test graphs
10−3 0.4 40 0.01 100 16 1,400 200 400
10−3 0.2 40 0.00 50 16 3,500 500 1,000
Table 2: Final training hyperparameters selected by validation performance.
The best validation performance is obtained with learning rate 10−3 and hidden size 40 for both models. Betweenness uses stronger regularization with dropout 0.4 and weight decay 0.01, whereas closeness performs best with dropout 0.2 and no weight decay.
3.4. Loss Function Both models are trained using a pairwise ranking loss rather than mean squared error, because the learning objective is to preserve the centrality-induced ordering of nodes. For each graph, M = N × 20 node pairs are sampled. The loss is M
1 X L= max(0, −rm (ŷim − ŷjm ) + margin) , M
(8)
m=1
where rm ∈ {−1, +1} indicates the true ordering between nodes im and jm . We use MarginRankingLoss with a margin equal to 1.0.
4. Experimental Results 4.1. Training Convergence and Rank Preservation The quality of the learned node rankings is evaluated using Kendall’s τ rank correlation [23]. We use Kendall’s τ rather than mean squared error because the objective is to preserve the relative ordering of nodes according to centrality, rather than to predict exact numerical centrality values. Figure 3 shows the training behaviour of the betweenness model. The training and test losses decrease steadily over 100 epochs and remain close throughout
11
training, with a final relative difference of 0.006. This indicates stable convergence without clear signs of overfitting. On a representative unseen test graph, the betweenness model achieves Kendall τ = 0.852. The mean performance is τ = 0.851 ± 0.011 on unseen Erdős–Rényi graphs. Figure 4 shows the corresponding results for closeness centrality. The closeness model converges rapidly within the first few epochs, and the training and test losses remain nearly identical at convergence, with a final relative difference of −0.012. The model achieves τ = 0.894±0.011, confirming that the learned ranking is highly consistent with exact closeness centrality on unseen test graphs. Together, these results show that both models preserve node rankings effectively while maintaining small train–test gaps. The comparison with exact NetworkX centrality values further confirms that the models capture the full ranking structure, not only the most central nodes.
Figure 3: Betweenness centrality approximation on unseen Erdős–Rényi test graphs. (a) Comparison between exact NetworkX betweenness centrality and GNN predictions on a representative test graph, with Kendall τ = 0.852. (b) Training and test loss over 100 epochs, showing stable convergence and a small generalization gap. (c) Kendall rank correlation during training, reaching a final test performance of τ = 0.851 ± 0.011.
12
Figure 4: Closeness centrality approximation on unseen Erdős–Rényi test graphs. (a) Comparison between exact NetworkX closeness centrality and GNN predictions on a representative test graph. (b) Training and test loss over 50 epochs, showing rapid convergence and nearly identical train–test behaviour. (c) Kendall rank correlation during training, reaching a final test performance of τ = 0.894 ± 0.011.
4.2. Ablation Study To assess the contribution of the main architectural choices, we perform a compact ablation study for betweenness centrality. The variants are trained under the same reduced setting using N = 200 Erdős–Rényi graphs and are evaluated on both ER and GRP test graphs.
ER τ
Variant
Architecture and fusion ablation, L = 5 Single pathway, L = 5 0.471 ± 0.031 Dual pathway + sum, L = 5 0.827 ± 0.012 Dual pathway + product, L = 5 0.846 ± 0.012
GRP τ 0.390 ± 0.046 0.679 ± 0.025 0.493 ± 0.039
Depth ablation using dual-pathway sum fusion Dual pathway + sum, L = 3 0.781 ± 0.018 0.477 ± 0.033 Dual pathway + sum, L = 5 0.798 ± 0.014 0.351 ± 0.040 Dual pathway + sum, L = 7 0.722 ± 0.020 0.488 ± 0.034 Table 3: Ablation study for the betweenness GNN. The first block compares pathway and fusion choices at fixed depth L = 5, while the second block evaluates message-passing depth using dual-pathway sum fusion.
The ablation results show that the dual-pathway design is essential: The singlepathway model performs substantially worse on both ER and GRP graphs. Product fusion gives the best in-distribution ER performance, while sum fusion transfers better to GRP graphs. The depth ablation shows that increasing depth does not
13
monotonically improve performance, suggesting that message-passing depth interacts with topology shift.
4.3. Baseline Comparison We compare the proposed GNN models against random ranking, degree centrality, and sampling-based Brandes approximation. Random ranking gives τ ≈ 0, confirming that the evaluation metric behaves as expected. Degree centrality is a strong inexpensive baseline, while Brandes sampling provides a standard approximation baseline for betweenness centrality. Since Brandes sampling is defined for betweenness approximation, it is not reported for closeness centrality. Table 4 reports the baseline comparison on ER graphs. Degree centrality performs strongly on ER graphs, achieving τ = 0.886 for betweenness and τ = 0.923 for closeness. This is expected because ER graphs are relatively homogeneous, and degree is already highly correlated with shortest-path-based centrality. The GNN models achieve comparable ranking accuracy, with τ = 0.851 ± 0.011 for betweenness and τ = 0.894 ± 0.011 for closeness, while avoiding explicit shortest-path computation at inference time.
Method
Betweenness τ
Closeness τ
Time (ms)
Random Ranking Degree Centrality Brandes k = 10 Brandes k = 20 Brandes k = 50 GNN (ours)
−0.001 ± 0.050 0.886 ± 0.010 0.286 ± 0.044 0.378 ± 0.038 0.552 ± 0.032 0.851 ± 0.011
−0.002 ± 0.052 0.923 ± 0.010 — — — 0.894 ± 0.011
0 0.07 7.9 15.5 35.2 23.8 / 9.7
Table 4: Baseline comparison on Erdős–Rényi test graphs with N = 200. Brandes sampling is reported only for betweenness centrality.
To address whether the Brandes baseline behaves similarly under topology shift, we also evaluate sampling-based betweenness approximation on BA and GRP graphs. Table 5 shows that Brandes performance improves with the number of sampled pivots on all graph families, but remains below the mixed-trained GNN on BA and GRP graphs. At k = 50, Brandes reaches τ = 0.747 on BA and τ = 0.629 on GRP, whereas the mixed-trained GNN achieves τ = 0.920 and τ = 0.861, respectively.
14
Method Random Ranking Degree Centrality Brandes k = 10 Brandes k = 20 Brandes k = 50 Mixed GNN (ours)
ER τ
BA τ
0.003 ± 0.050 0.869 ± 0.012 0.201 ± 0.043 0.274 ± 0.044 0.434 ± 0.036 0.878
GRP τ
0.002 ± 0.048 0.002 ± 0.046 0.865 ± 0.011 0.868 ± 0.015 0.514 ± 0.031 0.380 ± 0.037 0.606 ± 0.023 0.456 ± 0.031 0.747 ± 0.017 0.629 ± 0.026 0.920 0.861
Table 5: Betweenness baseline comparison across graph families. Brandes sampling improves with larger sampling budgets, but the mixed-trained GNN achieves stronger ranking accuracy on all three graph families.
These results show that degree centrality is a competitive baseline on homogeneous and synthetic graph families, but it is not a learned approximation method and does not provide a trainable representation for transfer. Brandes sampling improves as the number of pivots increases, especially on BA graphs, but still remains below the mixed-trained GNN. Overall, the results support the use of structurally diverse training for learning transferable betweenness representations, while closeness centrality remains more sensitive to topology shift.
4.4. Cross-Distribution Generalization A central question of this study is whether GNN-based learning systems acquire transferable representations of node importance or simply adapt to the graph family used during training. To examine this, we evaluate models trained on Erdős–Rényi (ER) graphs on structurally different Barabási–Albert (BA) and Gaussian Random Partition (GRP) networks. As shown in Figure 5, the ER-trained betweenness model transfers reasonably well to BA graphs, with Kendall correlation decreasing from τ = 0.861 on ER graphs to τ = 0.811 on BA graphs. However, performance drops substantially on GRP graphs, reaching only τ = 0.552. This indicates a strong topology-shift effect, particularly for community-structured networks where inter-community bridge nodes play an important role in shortest-path routing. Mixed-distribution training substantially improves this behavior. A single model trained on ER, BA, and GRP graphs achieves τ = 0.878 on ER, τ = 0.920 on BA, and τ = 0.861 on GRP networks without retraining. The largest improvement occurs on GRP graphs, where performance increases from τ = 0.552 to τ = 0.861. This suggests that exposure to diverse graph structures helps the model learn more general centrality patterns rather than topology-specific shortcuts.
15
The closeness model shows stronger sensitivity to topology shift. While the ER-trained closeness model performs well on ER graphs (τ = 0.880) and reasonably on BA graphs (τ = 0.802), it drops sharply on GRP graphs (τ = 0.285). This indicates that closeness centrality is more affected by community-level reachability patterns and may require greater structural diversity during training to achieve robust transfer. The stronger degradation of closeness centrality can be explained by its dependence on global distance structure. In ER graphs, shortest-path distances are relatively homogeneous, and local connectivity often provides a useful proxy for closeness. In contrast, GRP and power-grid networks exhibit modular or spatial structure, larger effective diameters, and more heterogeneous distance distributions. Nodes with similar local neighborhoods may therefore have very different average distances to the rest of the graph depending on their position within or between communities. This makes closeness more sensitive to topology shift than betweenness in the present experiments.
Figure 5: Cross-distribution generalization across graph topologies. (a) Betweenness centrality transfer across ER, BA, and GRP graphs. (b) Closeness centrality is more sensitive to topology shift, especially on GRP graphs. (c) Heatmap summary showing that mixeddistribution training improves betweenness transfer.
4.5. Transfer to Real-World Networks To evaluate whether the learned GNN representations transfer beyond synthetic graph families, the trained models were tested on three real-world networks without retraining: the C. Elegans neural network, Email-Eu-Core, and the Western United States power grid. As shown in Figure 6, betweenness centrality transfers moderately well across all three networks, with Kendall correlations ranging from τ = 0.603 to τ = 0.782. In contrast, closeness centrality is much more sensitive to topology shift, with performance ranging from τ = 0.108 to τ = 0.703. These results indicate that GNNs trained on synthetic graphs can learn reasonably transferable representations for betweenness-based node ranking, whereas closeness-based ranking remains more difficult to generalize to real-world networks. This pattern
16
is consistent with the synthetic generalization results in Section 4.4, where closeness centrality also showed substantially greater sensitivity to changes in graph topology. The especially low closeness performance on the power-grid network is consistent with this interpretation, since power-grid graphs are spatially embedded and typically contain long paths and sparse connectivity.
Figure 6: Zero-shot transfer to real-world networks. Models trained on synthetic graphs were evaluated directly on three real-world networks without retraining. Betweenness centrality transfers more reliably across datasets, whereas closeness centrality is substantially more sensitive to topology shift.
4.6. Scalability and Computational Efficiency We evaluate computational efficiency by comparing the inference time of the learned GNN approximator with exact NetworkX betweenness computation. The reported speedups refer only to inference time; training is performed once and its cost is amortized when the trained model is applied to many graphs. As shown in Table 6, the advantage of GNN inference increases with graph size. At N = 200, the GNN is 14× faster than exact computation, while at N = 1000 the speedup reaches 97.7× (149.5 ms versus 14605.4 ms). Importantly, the model also preserves high ranking accuracy at this scale, achieving Kendall τ = 0.821 ± 0.004 on the N = 1000 test graphs.
17
N
NetworkX (ms)
GNN (ms)
Speedup
Kendall τ
50 100 200 500 1000
5.2 ± 0.9 30.5 ± 9.4 139.3 ± 5.0 1828.7 ± 58.2 14605.4 ± 431.7
2.6 ± 0.4 3.7 ± 0.4 9.8 ± 1.8 27.2 ± 4.5 149.5 ± 7.7
2× 8× 14× 67× 97.7×
0.845 ± 0.029 0.844 ± 0.021 0.851 ± 0.011 0.712 ± 0.012 0.821 ± 0.004
Table 6: Scalability comparison between exact NetworkX betweenness computation and GNN inference. All times are mean ± standard deviation. Kendall τ at N = 1000 is evaluated on a reduced test set due to the higher cost of exact ground-truth computation.
For N = 1000, we repeated the timing experiment after model warm-up and report stabilized inference times, which substantially reduces the variance observed in preliminary measurements.
4.7. Training at N = 5,000 To assess scalability beyond the primary N = 200 setting, we trained a dedicated betweenness GNN on Erdős–Rényi graphs with N = 5,000 nodes and edge probability p = 0.001. Exact betweenness labels were generated for 300 graphs using an NVIDIA A100 GPU. Label generation required 6.65 hours in total, while model training completed in 8 minutes over 50 epochs. The dataset was split into 210 training, 30 validation, and 60 test graphs. The same architecture and hyperparameters selected at N = 200 were used without modification. The best model achieved a validation Kendall correlation of τ = 0.9385 ± 0.0012 and a test correlation of τ = 0.9380 ± 0.0011. These results show that the proposed GNN architecture remains effective at substantially larger graph sizes and that the learned approximation framework scales beyond the primary N = 200 setting.
5. Conclusion This study investigated Graph Neural Networks as scalable neural approximators for centrality-based node ranking across different network topologies. The proposed models achieve mean Kendall correlations of τ = 0.851 ± 0.011 for betweenness and τ = 0.894 ± 0.011 for closeness on unseen Erdős–Rényi graphs. A dedicated large-scale betweenness model trained on graphs with N = 5,000 nodes further achieves τ = 0.938, while GNN inference provides up to a 97.7× speedup over exact computation. The main finding is that training diversity improves transferability. Models trained only on Erdős–Rényi graphs degrade under
18
topology shift, especially on community-structured networks. In contrast, mixeddistribution training on Erdős–Rényi, Barabási–Albert, and Gaussian Random Partition graphs produces more robust betweenness representations across graph families. This suggests that structural diversity acts as an implicit regularizer, reducing reliance on topology-specific shortcuts. Zero-shot validation on real-world networks further shows that synthetic training can yield transferable representations for betweenness centrality, although closeness centrality remains more sensitive to topology shift. Overall, the results support GNN-based centrality approximation as a scalable learning-based approach for node ranking in large-scale graph-structured data.
6. Limitations and Future Work Several limitations of the proposed learning-based approximation framework should be noted. First, closeness centrality is more sensitive to topology shift than betweenness centrality, with substantial degradation on community-structured and some real-world networks. This suggests that closeness may require greater structural diversity during training or topology-aware model design. Second, although synthetic graph families allow controlled experimentation and exact supervision, they do not fully capture the complexity of real-world networks. Finally, scalability was evaluated up to N = 5,000 nodes; experiments on larger and more heterogeneous networks would provide a more complete assessment of computational performance. Future work should therefore focus on improving transfer from synthetic to real-world networks. Promising directions include mixed-distribution training for closeness centrality, incorporating real network data during training, domain adaptation, and topology-aware pretraining. More broadly, graph foundation models and pretraining strategies may offer useful directions for learning transferable centrality representations across heterogeneous graph domains.
Generative AI Use Disclosure During the preparation of this manuscript, the authors used AI-assisted tools, including Grammarly, for grammatical proofreading and sentence-level language refinement, and Claude AI by Anthropic for Latex formatting assistance and figurecode organization. After using these tools, the authors reviewed, edited, and validated all content, and take full responsibility for the final manuscript.
Data Availability All code, training scripts, and experiment pipelines used in this study are publicly available at: https://github.com/Samra771/graph_ranking-samra_dev.
19
Declaration of Competing Interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
References [1] M. Newman, Networks: An Introduction, Oxford University Press, 2010. [2] L. C. Freeman, A set of measures of centrality based on betweenness, Sociometry 40 (1) (1977) 35–41. [3] G. Sabidussi, The centrality index of a graph, Psychometrika 31 (4) (1966) 581–603. [4] W. L. Hamilton, R. Ying, J. Leskovec, Inductive representation learning on large graphs, in: Advances in Neural Information Processing Systems, 2017. [5] T. N. Kipf, M. Welling, Semi-supervised classification with graph convolutional networks, in: International Conference on Learning Representations, 2017. [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. [7] U. Brandes, A faster algorithm for betweenness centrality, Journal of Mathematical Sociology 25 (2) (2001) 163–177. [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. [9] M. Riondato, E. M. Kornaropoulos, Fast approximation of betweenness centrality through sampling, in: Proceedings of the 7th ACM International Conference on Web Search and Data Mining, 2014, pp. 413–422. [10] M. Borassi, E. Natale, Kadabra is an adaptive algorithm for betweenness via random approximation, ACM Journal of Experimental Algorithmics 24 (2019) 1–35.
20
[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). [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. [13] P. Veličković, et al., The clrs algorithmic reasoning benchmark, Proceedings of Machine Learning Research 162 (2022) 22084–22102. [14] M. Zhang, X. Wang, L. Jin, M. Song, Z. Li, A new approach for evaluating node importance in complex networks via deep learning methods, Neurocomputing 497 (2022) 13–27. doi:10.1016/j.neucom.2022.05.010. [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). [16] 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). [17] G. Yehudai, E. Fetaya, E. Meirom, G. Chechik, H. Maron, From local structures to size generalization in graph neural networks, in: Proceedings of the 37th International Conference on Machine Learning, 2020, pp. 10975–10986. [18] Q. Wu, H. Zhang, J. Yan, D. Wipf, Handling distribution shifts on graphs: An invariance perspective, arXiv preprint arXiv:2202.02466 (2022). [19] S. Gui, X. Li, L. Wang, S. Ji, Good: A graph out-of-distribution benchmark, in: Advances in Neural Information Processing Systems, 2022. [20] A. A. Hagberg, D. A. Schult, P. J. Swart, Exploring network structure, dynamics, and function using networkx, in: Proceedings of the 7th Python in Science Conference, 2008, pp. 11–15. [21] P. Erdős, A. Rényi, On random graphs i, Publicationes Mathematicae 6 (1959) 290–297. [22] A.-L. Barabási, R. Albert, Emergence of scaling in random networks, Science 286 (5439) (1999) 509–512.
21
[23] M. G. Kendall, A new measure of rank correlation, Biometrika 30 (1–2) (1938) 81–93.
22