# BRAVA-GNN: Betweenness Ranking Approximation Via Degree MAss Inspired Graph Neural Network

Justin Dachille, Aurora Rossi, Sunil Kumar Maurya, Frederik Mallman-Trenn, Xin Liu, Frédéric Giroire, Tsuyoshi Murata, Emanuele Natale

<figure><img src="image_1.png" /></figure>

To cite this version:

Justin Dachille, Aurora Rossi, Sunil Kumar Maurya, Frederik Mallman-Trenn, Xin Liu, et al. BRAVA-GNN: Betweenness Ranking Approximation Via Degree MAss Inspired Graph Neural Network. 2026. [https://arxiv.org/abs/2005.05028](https://arxiv.org/abs/2005.05028)

HAL Id: hal-05502800

https://inria.hal.science/hal-05502800v1

Preprint submitted on 10 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# BRAVA-GNN: Betweenness Ranking Approximation Via Degree MAss Inspired Graph Neural Network

Justin Dachille*

justin.dachille@kcl.ac.uk
King's College London
London, United Kingdom

Aurora Rossi*

arossi@uni-bonn.de
University of Bonn and Lamarr
Institute
Bonn, Germany

Sunil Kumar Maurya

sunil.maurya@weblab.t.u-tokyo.ac.jp
University of Tokyo
Tokyo, Japan

Frederik Mallman-Trenn

frederik.mallmann-trenn@kcl.ac.uk
King's College London
London, United Kingdom

Xin Liu

xin.liu@aist.go.jp
National Institute of Advanced
Industrial Science and Technology
Tokyo, Japan

Frédéric Giroire

frederic.giroire@inria.fr
Université Côte d'Azur, CNRS, Inria,
I3S
Sophia Antipolis, France

Tsuyoshi Murata

murata@comp.isct.ac.jp
Institute of Science Tokyo
Tokyo, Japan

Emanuele Natale

emanuele.natale@cnrs.fr
Université Côte d'Azur, CNRS, Inria,
I3S
Sophia Antipolis, France

## Abstract

Computing node importance in networks is a long-standing fundamental problem that has driven extensive study of various centrality measures. A particularly well-known centrality measure is betweenness centrality, which becomes computationally prohibitive on large-scale networks. Graph Neural Network (GNN) models have thus been proposed to predict node rankings according to their relative betweenness centrality. However, state-of-the-art methods fail to generalize to high-diameter graphs such as road networks. We propose BRAVA-GNN, a lightweight GNN architecture that leverages the empirically observed correlation linking betweenness centrality to degree-based quantities, in particular multi-hop degree mass. This correlation motivates the use of degree masses as size-invariant node features and synthetic training graphs that closely match the degree distributions of real networks. Furthermore, while previous work relies on scale-free synthetic graphs, we leverage the hyperbolic random graph model, which reproduces power-law exponents outside the scale-free regime, better capturing the structure of real-world graphs like road networks. This design enables BRAVA-GNN to generalize across diverse graph families while using 54× fewer parameters than the most lightweight existing GNN baseline. Extensive experiments on 19 real-world networks, spanning social, web, email, and road graphs, show that

BRAVA-GNN achieves up to 214% improvement in Kendall-Tau correlation and up to 70× speedup in inference time over state-of-the-art GNN-based approaches, particularly on challenging road networks.

## CCS Concepts

* **Computing methodologies** → *Machine learning*; *Learning to rank*; *Neural networks*; *Learning paradigms*; *Supervised learning*; *Machine learning approaches*; 
* **Mathematics of computing** → *Discrete mathematics*.

## Keywords

graph neural network, betweenness centrality, large-scale graph analysis, hyperbolic graph model, degree mass

## ACM Reference Format:

Justin Dachille, Aurora Rossi, Sunil Kumar Maurya, Frederik Mallman-Trenn, Xin Liu, Frédéric Giroire, Tsuyoshi Murata, and Emanuele Natale. 2026. BRAVA-GNN: Betweenness Ranking Approximation Via Degree MAss Inspired Graph Neural Network. In *Proceedings of Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining (Submitted to KDD '26)*. ACM, New York, NY, USA, 19 pages. https://doi.org/XXXXXXX.XXXXXXX

## 1 Introduction

Identifying important nodes in networks is a crucial task in many applications. For instance, in social networks, influential individuals can significantly impact information dissemination, while in transportation networks, critical junctions can affect traffic flow and connectivity [22, 23, 34]. Centrality measures formalise this concept; specifically, betweenness centrality is particularly effective at capturing the impact of nodes that act as bridges or bottlenecks, as it quantifies a node's importance based on its position in the network by counting the number of shortest paths that pass through it

<footnote>*Both authors contributed equally to this research.</footnote>

<footnote>Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.</footnote>

<footnote>Submitted to KDD '26, Jeju, Korea</footnote>

<footnote>© 2026 Copyright held by the owner/author(s). Publication rights licensed to ACM.</footnote>

<footnote>ACM ISBN 978-1-4503-XXXXX-X/26/08</footnote>

<footnote>https://doi.org/XXXXXXX.XXXXXXX</footnote>
<figure><img src="image_3.png" /><figcaption>Figure 1: Visual comparison on the Jeju Island road network. The predicted rankings (a) closely align with the ground-truth topology (b), demonstrating the model's capability to capture structural importance in high-diameter graphs.</figcaption></figure>

[11]. Despite its utility, computing betweenness centrality exactly is computationally expensive, following Brandes' algorithm with a complexity of $O(|V||E|)$, making it impractical for large-scale real-world applications [7]. This has motivated the investigation of approximation methods, including sampling-based algorithms, parallel and distributed computing, and, more recently, machine learning techniques such as Graph Neural Networks (GNNs). GNNs are employed to learn node representations that enable efficient ranking according to centrality measures, rather than absolute scores [10, 27, 30]. However, while GNNs have shown promising results in capturing complex graph structures, current state-of-the-art methods struggle to generalize to high-diameter graphs, such as road networks.

We propose BRAVA-GNN (Betweenness Ranking Approximation Via Degree MAss GNN)<fnref n="1" />, a lightweight architecture designed to enhance the accuracy, efficiency, and generalization of GNNs for approximating betweenness centrality rankings. Furthermore, while previous work relies on scale-free synthetic graphs, we introduce training on the hyperbolic random graph model. This approach allows us to reproduce power-law exponents and clustering properties that better reflect the structure of real-world networks, such as road systems. This design allows BRAVA-GNN to achieve significant performance gains, particularly on challenging topologies. In particular:

* We demonstrate that existing GNN-based methods fail to generalize on road networks and show that our proposed method significantly improves performance on these high-diameter graphs.

* We propose a novel GNN architecture that leverages degree mass for the node feature embedding, reducing parameter count by a factor of 54 compared to the state-of-the-art.

* We introduce training on hyperbolic random graph models, which reproduce real network properties with greater flexibility and enhances generalization across diverse graph structures.

* We evaluate our architecture on a comprehensive set of 19 real-world datasets, including social, web, email, and road networks. BRAVA-GNN achieves up to a 214% improvement

in Kendall-Tau correlation and up to a 70× speedup in inference time compared to state-of-the-art GNN approaches.

The source code will be available on GitHub upon acceptance.

## 2 Related Work

The exact computation of betweenness centrality relies on Brandes' algorithm [6], which becomes prohibitive for large-scale graphs due to its time complexity of $O(|V||E|)$ for unweighted networks and $O(|V||E| + |V|^2 \log(|V|))$ for weighted networks. Under the Strong Exponential Time Hypothesis [20], no truly subquadratic algorithm exists for computing betweenness centrality, as this would imply a subquadratic solver for $k$-SAT* [4]. Consequently, there is considerable interest in distributed computing approaches and approximation algorithms.

### 2.1 Unsupervised Approximation Algorithms

Geisberger et al. [14] generalize the approximation algorithm of Brandes and Pich [7] by introducing linear and bisection scaling—simple multipliers that rescale centrality estimates, together with correction terms to reduce overestimation for nodes that happen to be close to the randomly chosen pivots. Rionato and Kornaropoulos [35] propose a sampling-based approach that leverages the concept of VC-dimension to determine the number of shortest paths required to achieve a desired level of accuracy. Borassi and Natale [5] combine a balanced bidirectional BFS with adaptive sampling, achieving speed-ups of over 100× in the approximation of betweenness centrality. Mahmoody et al. [26] address the centrality maximization problem via a randomized algorithm based on shortest-path sampling that provides theoretical approximation guarantees. Yoshida [43] use hypergraph sketches to compute adaptive betweenness centrality, updating scores as nodes are selected in almost linear time. Leveraging network topology, Wang et al. [42] propose a community-based greedy algorithm to efficiently identify top-k influential nodes in mobile social networks. Regarding centrality variants, Zhang et al. [44] combine deterministic graph traversals with random walk sampling to approximate spanning centrality, while Brunelli et al. [8] introduce polynomial-time algorithms for computing betweenness in temporal graphs under various path optimality and waiting constraints.

<footnote n="1">¹Brava means "good" or "excellent" in Italian, alluding to the model's performance.</footnote>
## 2.2 Parallel and Distributed Algorithms

AlGhamdi et al. [1] compute the exact betweenness centrality by implementing a parallel version of Brandes' algorithm, executed on up to 96,000 CPU cores across multiple supercomputing systems. Bernaschi et al. [2] addressed the exact computation on multi-GPU systems by proposing a two-dimensional graph decomposition strategy. This line of research was subsequently extended by Vella et al. [40], who introduced the Dynamic Merging of Frontiers technique. This approach optimizes graph traversal by unifying exploration frontiers during Breadth-First Search (BFS) visits to avoid redundant computations, thereby improving performance on heterogeneous architectures. In parallel, within the context of large-scale distributed systems, Solomonik et al. [38] reformulated betweenness computation using linear algebra primitives, presenting an algorithm based on communication-efficient Sparse Matrix Multiplication. Hua et al. [19] were the first to propose a nearly optimal distributed algorithm for betweenness centrality under the CONGEST model, a standard message-passing abstraction where communication is restricted by limiting the size of messages sent across each edge to $O(\log n)$ bits per round. Hoang et al. [18] further improve this approach by enhancing round efficiency within the CONGEST model that computes betweenness centrality and all-pairs shortest paths in $O(n)$ rounds.

## 2.3 Graph Neural Networks

Graph neural networks (GNNs) have enabled the development of several deep learning-based methods for approximating centrality measures. Among the first contemporary GNNs presented at the same conference were those of Maurya et al. [27] and Fan et al. [10]. Maurya et al. [27] introduced a GNN-based method to approximate betweenness centrality, notably by pruning nodes from the adjacency matrix that lie on no shortest paths and by using graph convolutional layers while excluding the node's own feature vector during aggregation. This approach was later extended to closeness centrality in the journal version of the paper [28]. Fan et al. [10] proposed a GNN combined with a gated recurrent unit (GRU). This work was further improved by Mirakyan [30], who combined deep graph convolutional layers with a regularization scheme that progressively drops random edges in each convolutional block. This reduces the number of parameters while achieving better performance in both ranking betweenness centralities and identifying the top-k nodes. Notably, this latter work did not compare with Maurya et al. [27].

# 3 Preliminaries

This section introduces the mathematical definition of betweenness centrality and degree mass, defines the core prediction task, and describes the hyperbolic random graph model.

## 3.1 Betweenness Centrality

Given a graph $G = (V, E)$, where $V$ is the set of nodes and $E$ is the set of edges, the betweenness centrality $C_B(v)$ of a node $v \in V$ is defined as:

$$C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}} \qquad (1)$$

where $\sigma_{st}$ is the total number of shortest paths from node $s$ to node $t$, and $\sigma_{st}(v)$ is the number of those paths that pass through node $v$.

## 3.2 Problem Definition

Given an unweighted graph $G = (V, E)$ (which can be either directed or undirected), our goal is to learn a function $f: V \to \mathbb{R}$ that assigns each node $v \in V$ a real-valued score $f(v)$ such that the ranking induced by these scores closely approximates the ranking based on the true betweenness centrality values $C_B(v)$. Following standard practice in machine learning, this task is formulated as a ranking problem rather than a regression problem. The objective is not to accurately predict the absolute betweenness centrality values, but to preserve the relative ordering of nodes induced by $C_B(v)$. This formulation better reflects the use of betweenness centrality in many downstream applications, where the relative importance of nodes is more relevant than their exact centrality scores.

## 3.3 Multi-hop Degree Mass

The m-th order degree mass of a node in a graph $G = (V, E)$ captures the cumulative connectivity of nodes within m hops from that node. Originally introduced by Li et al. [25], the m-th order degree mass is formally defined as:

$$d^{(m)} = \left( \sum_{k=0}^{m} A^k \right) d. \qquad (2)$$

where $A$ is the adjacency matrix of the graph and $d$ is the vector of node degrees. Li et al. [25] empirically demonstrate a strong correlation between higher-order degree masses and betweenness centrality in real-world networks.

## 3.4 Hyperbolic Random Graph Model

The hyperbolic random graph model was first introduced by Krioukov et al. [21]. The graph is constructed by placing $N$ nodes quasi-uniformly within a disk of radius $R$ in a hyperbolic plane of negative curvature $K = -\zeta^2$. Writing node positions in polar coordinates $(r, \theta)$, where $r \in [0, R]$ and $\theta \in [0, 2\pi]$, the angular density is $\rho(\theta) = \frac{1}{2\pi}$ and the radial coordinate density is:

$$\rho(r) = \alpha \frac{\sinh(ar)}{\cosh(\alpha R) - 1}. \qquad (3)$$

The parameter $\alpha$ controls the nodes' positions: if $\alpha = \zeta$, the points follow a uniform distribution; if $\alpha > \zeta$, the points are more likely to be near the disk's border, otherwise, they tend to cluster near the center. Two nodes $u$ and $v$ are connected if they are at a hyperbolic distance $d_H$ less than $R$, where, considering the polar coordinates $u = (r_u, \theta_u)$ and $v = (r_v, \theta_v)$, $d_H$ is defined as:

$$d_H((r_u, \theta_u), (r_v, \theta_v)) = \frac{1}{\zeta} \mathrm{acosh} \left( \cosh(\zeta r_u) \cosh(\zeta r_v) - \sinh(\zeta r_u) \sinh(\zeta r_v) \cos(\pi - |\pi - |\theta_u - \theta_v||) \right). \quad (4)$$

Krioukov et al. [21] proved that the resulting degree distribution follows a power law $P(k) \sim k^{-\gamma}$, where the exponent $\gamma$ is a function of the curvature and the node distribution parameters:

$$\gamma = \frac{2\alpha}{\zeta} + 1 > 2. \qquad (5)$$
We use the generator of hyperbolic random graphs proposed by von Looz and Meyerhenke [41] which is parameterized according to four parameters: the number of nodes N, the temperature T controlling clustering, the average degree $\bar{k}$, and the exponent $\gamma$ of the power-law degree distribution. Equation 5 relates $\gamma$ to the parameters used by Krioukov et al. [21]. For the full analytical derivations and the parameter relationships, we refer the reader to the original work [21].

Recent literature has demonstrated that hyperbolic geometry provides an optimal embedding space for real-world datasets due to its inherent ability to encode hierarchical structures. For example, Boguñá et al. [3] show that the Internet's topology can be mapped to a hyperbolic disk to effectively discover and encode community structure. In the context of machine learning, Nickel and Kiela [32] and Ganea et al. [13] showed that hyperbolic embeddings significantly outperform Euclidean approaches in representing taxonomic and hierarchical data.

# 4 Technical Contributions

We propose BRAVA-GNN, a lightweight framework designed to approximate the ranking induced by betweenness centrality in large-scale directed and undirected graphs. Our approach is based on a preprocessing step designed to remove nodes that do not contribute to any shortest paths and a message passing GNN that leverages higher-order degree mass features.

## 4.1 Preprocessing

We adopt the preprocessing heuristic introduced in Maurya et al. [28], which removes nodes that are guaranteed not to lie on any shortest path. In particular, nodes satisfying either of the following two conditions are removed:

(1) **Isolated or Leaf Nodes:** Any node with fewer than two neighbors has zero centrality, as betweenness is strictly defined for intermediate points.

(2) **Clique Neighborhoods:** If a node's neighbors form a clique, any shortest path between them will favor the direct edge (length 1) over a path through the node (length 2).

Observe that, while such nodes have zero betweenness centrality, removing them impacts the betweenness of the remaining node. Such impact appears however negligible in practice, compared to the obtained simplification of the graph topology.

## 4.2 Architecture

The core of BRAVA-GNN is a message-passing architecture. Since betweenness centrality in directed graphs depends on the number of directed shortest paths, our model processes flow from both incoming and outgoing directions independently before fusing them. For complete details on hyperparameters, we refer to Section 5.2. The complete procedure is summarized in Algorithm 2 and illustrated in Figure 2.

### 4.2.1 Input Features.
We employ structural features specifically, the higher-order degree masses introduced in Section 3.3. This is motivated by findings that node degree [29] and higher-order degree masses [25] are highly correlated with betweenness centrality in real-world networks. Consequently, we employ as initial feature

### Algorithm 1 DegreeMassEmbedding.

1: **Input:** Matrix A, Weight matrix W, $d^{(i)}$ i-order degree mass

2: **Output:** Initial embedding h.

3: $h \leftarrow [d^{(1)}, d^{(2)}, d^{(3)}, d^{(4)}, d^{(5)}, d^{(6)}]$

4: $h = \text{ReLU}(W_{6 \to 12}(h))$

5: **return** h

### Algorithm 2 BRAVA-GNN.

1: **Input:** Adjacency Matrix A, Transpose Adjacency Matrix $A^T$, Weight Matrix $W^{(l)}$ at layer $l$.

2: **Output:** Betweenness score y.

3: $H_{in} \leftarrow \text{DegreeMassEmbedding}(A)$

4: $H_{out} \leftarrow \text{DegreeMassEmbedding}(A^T)$

5: $y_{in} \leftarrow 0$

6: $y_{out} \leftarrow 0$

7: **for** each layer $l = 0 \dots 1$ **do**

8: $H_{in}^{(l+1)} \leftarrow \text{ReLU}(A \cdot H_{in}^{(l)} \cdot W^{(l)})$

9: $H_{out}^{(l+1)} \leftarrow \text{ReLU}(A^T \cdot H_{out}^{(l)} \cdot W^{(l)})$

10: $y_{in} \leftarrow y_{in} + \text{MLP}(H_{in}^{(l+1)})$

11: $y_{out} \leftarrow y_{out} + \text{MLP}(H_{out}^{(l+1)})$

12: **end for**

13: **return** $y_{in} * y_{out}$

vector for a node a concatenation of degree masses up to the 6-th order degree mass, which are processed through a dense layer with ReLU activation as detailed in Algorithm 1.

### 4.2.2 Dual Message Passing.
To capture information from both incoming and outgoing edges, we apply two parallel GNN encoders sharing the same weights but operating on the original adjacency matrix A of the input graph and its transpose $A^T$. The encoder consists of two message-passing layers, where each node aggregates features from its k-hop neighbors without incorporating its own features. At each layer, the aggregated features are processed through a shared multi-layer perceptron (MLP) to produce intermediate node scores.

### 4.2.3 Score Fusion.
After 2 layers, the hidden states from all layers are passed through a shared Multi-Layer Perceptron (MLP) to project them to scalars $y_{in}(v)$ and $y_{out}(v)$. The final node scores are obtained by multiplying the resulting embeddings $y_{in}$ and $y_{out}(v)$ of both directions.

# 5 Experimental Setup

In this section, we describe the experimental environment, the architectural configurations, and the evaluation framework used to validate our model's ability to approximate betweenness centrality rankings.

## 5.1 Software

Our proposed model is implemented in PyTorch [33], while NetworkX [17] is used for graph generation and data processing, and NetworkKit [39] is employed to compute exact betweenness centrality values.
<figure><img src="image_4.png" /><figcaption>Figure 2: BRAVA-GNN Architecture Overview. The model utilizes 6-th order degree mass as input features, followed by two message-passing layers with ReLU activation and shared MLPs.</figcaption></figure>

## 5.2 Implementation Details

We train the model for 10 epochs using the Adam optimizer with a learning rate of $5 \times 10^{-3}$. The entire training process is highly efficient, requiring approximately 10 minutes on a single Nvidia GPU.

Hyperparameters were selected via ablation studies balancing accuracy and parameter efficiency (Appendix 8.1). The hidden dimension $d = 12$ was chosen as it achieves near-peak Kendall-tau correlation ($\tau_b = 0.7899$) while keeping the model lightweight vs. larger dimensions like 128 (Table 9). The MLP uses three linear layers $[12 \to 24 \to 24 \to 12 \to 1]$ with ReLU activations and dropout $p = 0.3$, which yields optimal performance across tested rates 0.1-0.7 (Table 10).

We apply $L_2$ normalization post-activation per layer for stability. Ablations confirm 2 GNN layers strike the best expressiveness-efficiency tradeoff (Tables 6, 7), while 6-hop degree mass outperforms lower orders, especially on road networks (Tables 4, 5). Hyperbolic training substantially boosts generalization to high-diameter graphs (Table 8).

To evaluate statistical robustness, we repeat the training process with 5 different random seeds and report the mean performance and standard deviation across these independent runs.

## 5.3 Baselines

To establish a rigorous benchmark, we compare BRAVA-GNN against two state-of-the-art GNN-based methods: GNN-Bet [28] and ABCDE [30].

We select GNN-Bet as our primary baseline, as it represents a foundational GNN architecture for betweenness centrality approximation. We additionally include ABCDE to capture recent advancements in the field. Notably, ABCDE has been extensively validated against a wide spectrum of prior techniques, including sampling-based algorithms (e.g., ABRA [36], RK [35], KADABRA [5]) and learning-based approaches (e.g., Node2Vec [15], DrBC [10]). Consequently, by comparing against ABCDE, we implicitly benchmark our method against this broader family of approaches.

Since ABCDE was not originally evaluated against GNN-Bet, including both models ensures a comprehensive assessment of the current landscape of GNN-based approximation algorithms.

### 5.3.1 GNN-Bet
While our framework incorporates the effective preprocessing heuristics and the bi-directional message passing scheme introduced by Maurya et al. [28], our core learning paradigm diverges. The architecture of GNN-Bet relies on learnable node-specific embeddings, which inherently tie model complexity to input graph size. This design necessitates padding graphs to the size of the largest graph in the dataset, resulting in a parameter-heavy model (requiring over 58M parameters in our experiments). In contrast, BRAVA-GNN replaces these high-dimensional embeddings with size-invariant degree-mass features. This shift allows our model to process graphs of arbitrary size natively without padding, reducing the parameter count by orders of magnitude (to $\approx 1.3k$) and enabling true inductive generalization across disparate topologies.

### 5.3.2 ABCDE
ABCDE [30] represents a significant step towards parameter-efficient centrality approximation. The model employs a deep Graph Convolutional Network architecture combined with a specialized regularization technique, *DropEdge*, which randomly removes a fraction of edges during each training iteration to mitigate overfitting and over-smoothing. Regarding input features, ABCDE utilizes the aggregated degrees of first-order neighbors. While this design drastically reduces the parameter count compared to GNN-Bet (down to $\approx 72k$), it remains significantly heavier than our proposed approach ($\approx 1.3k$) and relies on strictly local (1-hop) structural information, whereas BRAVA-GNN integrates higher-order degree masses to capture longer-range dependencies.

## 5.4 Loss Function

Since the absolute values of betweenness centrality can span several orders of magnitude and vary significantly across different graph topologies, optimizing directly for exact values is often unstable. Instead, we use the formulation which set the learning objective as a pairwise ranking problem to preserve the relative importance of nodes. Specifically, we employ a *Margin Ranking Loss* to enforce the correct ordering of nodes based on their centrality scores. Given two nodes $u$ and $v$, the loss is defined as:

$$ \mathcal{L}(s_u, s_v, y) = \max(0, 1 - y \cdot (s_u - s_v)), \quad (6) $$
where $s_u$ and $s_v$ are the predicted scores generated by the model for nodes u and v, respectively. The label $y \in \{1, -1\}$ serves as the ranking indicator: we set $y = 1$ if u is expected to be ranked higher than v, and $y = -1$ otherwise. This formulation aligns with the pairwise hinge loss used in Learning to Rank frameworks [9].

## 5.5 Evaluation Metric

To evaluate the performance of our model in the node ranking task, we employ the Kendall Tau ($\tau$) correlation coefficient. This metric measures the ordinal association between the predicted and the ground-truth rankings. In particular, we adopt the $\tau_b$ variant of the Kendall Tau coefficient, which explicitly accounts for ties in the rankings. This is particularly relevant for betweenness centrality, where large subsets of nodes (e.g., peripheral nodes or symmetric structures) often share identical scores. Formally, the Kendall $\tau_b$ coefficient is defined as:

$$ \tau_b = \frac{C - D}{\sqrt{(C + D + T)(C + D + U)}}, \quad (7) $$

where C denotes the number of *concordant pairs* (pairs of nodes (i, j) whose ranks agree in both the predicted and true rankings), D denotes the number of * discordant pairs* (pairs whose ranks are reversed), T is the number of ties only in the predicted ranking, and U is the number of ties only in the true ranking. The coefficient of $\tau_b$ ranges from -1 (perfect disagreement) to 1 (perfect agreement), where a higher score indicates that the model has successfully learned to preserve the topological hierarchy of the network.

## 5.6 Datasets

In this section we describe the datasets used in this paper for both training and evaluation.

### 5.6.1 Training set.
To ensure robust generalization across diverse network topologies, we construct a hybrid synthetic dataset comprising both scale-free and hyperbolic random graphs.

While we retain scale-free graphs as a baseline following the protocol of Maurya et al. [28], we argue that they alone are insufficient to represent the complex geometry of many real-world systems (e.g., road networks). To bridge this gap, we add to our training set the hyperbolic random graphs, described in Section 3.4. Hyperbolic random graphs are particularly effective at reproducing key structural properties observed in real networks, including high clustering coefficients, power-law degree distributions [16], and small-world characteristics [12, 31]. Instead of choosing arbitrary generation parameters, we employ a data-driven initialization strategy. We analyzed a reference dataset of 15 real-world networks, ranging from social media to road networks [24, 37], to estimate the empirical distributions of the average degree $\bar{k}$ and the power-law exponent $\gamma$ (see Table 1). Our final training set consists of 20 synthetic graphs, each with $N = 100,000$ nodes:

* **10 Scale-Free Graphs:** Generated using the configuration detailed in Maurya et al. [28].

* **10 Hyperbolic Random Graphs:** Generated by sampling the temperature $T$ uniformly from (0, 0.5), while $\bar{k}$ and $\gamma$ are drawn directly from the empirically observed distributions.

<table><caption>Table 1: Real World graphs for $\gamma$ and $\bar{k}$ distribution estimation, including $\rho$ degree-betweenness Pearson correlation coefficient.</caption><thead><tr><th>Graph</th><th>#Nodes</th><th>#Edges</th><th>k&#773;</th><th>&gamma;</th><th>&rho;</th></tr></thead><tbody><tr><td colspan="6"><strong>Road Networks</strong></td></tr><tr><td>road-euroroad</td><td>1,174</td><td>1,417</td><td>2.4140</td><td>6.9798</td><td>0.4545</td></tr><tr><td>road-usroads-48</td><td>126,146</td><td>161,950</td><td>2.5677</td><td>2.9640</td><td>0.0960</td></tr><tr><td>road-usroads</td><td>129,164</td><td>464,708</td><td>7.1955</td><td>2.5423</td><td>0.8358</td></tr><tr><td>roadNet-TX</td><td>1,379,917</td><td>1,921,660</td><td>2.7852</td><td>6.8398</td><td>0.0541</td></tr><tr><td>road-italy-osm</td><td>6,686,487</td><td>7,013,978</td><td>2.0980</td><td>7.9782</td><td>-</td></tr><tr><td colspan="6"><strong>Social and Web Networks</strong></td></tr><tr><td>p2p-Gnutella30</td><td>36,682</td><td>88,328</td><td>4.8159</td><td>7.0192</td><td>0.7277</td></tr><tr><td>email-Enron</td><td>36,692</td><td>183,831</td><td>10.0202</td><td>2.3982</td><td>0.8157</td></tr><tr><td>musae-github</td><td>37,700</td><td>289,003</td><td>15.3317</td><td>2.5023</td><td>0.8358</td></tr><tr><td>soc-Slashdot0811</td><td>77,360</td><td>905,468</td><td>12.1298</td><td>2.2056</td><td>0.8442</td></tr><tr><td>gemsec-Facebook</td><td>134,833</td><td>1,380,293</td><td>32.4296</td><td>2.4494</td><td>0.7353</td></tr><tr><td>twitch-gamers</td><td>168,114</td><td>6,797,557</td><td>80.8684</td><td>2.1334</td><td>0.2514</td></tr><tr><td>com-DBLP</td><td>317,080</td><td>1,049,866</td><td>6.6221</td><td>3.5380</td><td>0.5985</td></tr><tr><td>web-NotreDame</td><td>325,729</td><td>1,497,134</td><td>6.6933</td><td>2.4715</td><td>0.2897</td></tr><tr><td>web-BerkStan</td><td>685,230</td><td>7,600,595</td><td>19.4080</td><td>2.6299</td><td>0.4503</td></tr><tr><td>com-Orkut</td><td>3,072,441</td><td>117,185,083</td><td>76.2814</td><td>2.2849</td><td>-</td></tr></tbody></table>

### 5.6.2 Test set.
For evaluation, we employ a comprehensive benchmark suite of 19 real-world networks sourced from the Network Data Repository [37] and the SNAP dataset [24]. This collection spans diverse domains such as social media, web structure, citation networks and road networks. The datasets also exhibit significant variance in scale, ranging from smaller peer-to-peer networks to massive graphs with millions of edges. Crucially, to ensure a rigorous and fair comparison with the state-of-the-art, our test set acts as a superset of the evaluation protocols used in prior works. We incorporate the graphs utilized by Maurya et al. [28], as well as the specific subset (com-youtube, amazon, dblp, cit-Patents, and com-lj) employed by Mirakyan [30]. Detailed statistics regarding the node and edge counts for all 19 datasets are provided in Table 11 of the Appendix.

# 6 Results

In this section, we evaluate the performance of our model through a combination of qualitative and quantitative analyses.

## 6.1 Benchmark

Table 2 presents a comprehensive comparison between BRAVA-GNN and the state-of-the-art baselines, GNN-Bet [28] and ABCDE [30]. We evaluate performance along two axes: ranking accuracy (Kendall Tau $\tau_b$) and computational efficiency (Inference Time).

## 6.2 Accuracy and Generalization.

BRAVA-GNN establishes a new state-of-the-art on the majority of the datasets, demonstrating superior generalization capabilities. The performance gap is most evident in road networks, which
<table><caption>Table 2: Comparison of Kendall Tau Correlation (↑) and Inference Time (↓). We report Mean ± Std. Dev. Best results are bolded, second best underlined. The % Imp. column shows the percentage improvement of BRAVA-GNN over the best baseline.</caption><thead><tr><th rowspan="2"></th><th colspan="4">Accuracy (Kendall Tau τ<sub>b</sub> ↑)</th><th colspan="4">Inference Time (Seconds ↓)</th></tr><tr><th>GNN-Bet</th><th>ABCDE</th><th>BRAVA-GNN</th><th>% Imp.</th><th>GNN-Bet</th><th>ABCDE</th><th>BRAVA-GNN</th><th>Speedup</th></tr></thead><tbody><tr><td colspan="9"><strong>Road Networks</strong></td></tr><tr><td>road-luxembourg-osm</td><td><u>0.2075 ± 0.0662</u></td><td>-0.1772 ± 0.0381</td><td><strong>0.6518 ± 0.0354</strong></td><td>+214.2%</td><td>1.6385 ± 0.7001</td><td><u>0.8369 ± 0.1632</u></td><td><strong>0.0125 ± 0.0036</strong></td><td>67.2x</td></tr><tr><td>road-roadNet-PA</td><td><u>0.6447 ± 0.0595</u></td><td>0.1128 ± 0.0132</td><td><strong>0.8162 ± 0.0081</strong></td><td>+26.6%</td><td><u>2.9166 ± 1.1177</u></td><td>8.0003 ± 0.5212</td><td><strong>0.1091 ± 0.0392</strong></td><td>26.7x</td></tr><tr><td>road-belgium-osm</td><td><u>0.2714 ± 0.0751</u></td><td>-0.1911 ± 0.0183</td><td><strong>0.7127 ± 0.0215</strong></td><td>+162.6%</td><td><u>3.1364 ± 1.1891</u></td><td>9.4258 ± 0.6430</td><td><strong>0.1340 ± 0.0469</strong></td><td>23.4x</td></tr><tr><td>road-roadNet-CA</td><td><u>0.6263 ± 0.0575</u></td><td>0.1283 ± 0.0162</td><td><strong>0.8024 ± 0.0090</strong></td><td>+28.1%</td><td><u>4.0574 ± 1.4663</u></td><td>13.6887 ± 1.1890</td><td><strong>0.1962 ± 0.0709</strong></td><td>20.7x</td></tr><tr><td>road-netherlands-osm</td><td><u>0.4645 ± 0.0878</u></td><td>-0.1428 ± 0.0334</td><td><strong>0.8645 ± 0.0074</strong></td><td>+86.1%</td><td><u>3.8864 ± 1.3631</u></td><td>14.2407 ± 1.4655</td><td><strong>0.1806 ± 0.0853</strong></td><td>21.5x</td></tr><tr><td colspan="9"><strong>Social and Web Networks</strong></td></tr><tr><td>p2p-Gnutella31</td><td><u>0.9305 ± 0.0013</u></td><td>0.2222 ± 0.0015</td><td><u>0.9029 ± 0.0037</u></td><td>-3.0%</td><td>1.5584 ± 0.6445</td><td><u>0.5922 ± 0.1016</u></td><td><strong>0.0101 ± 0.0029</strong></td><td>58.5x</td></tr><tr><td>soc-Epinions1</td><td><u>0.8807 ± 0.0013</u></td><td>0.3408 ± 0.0103</td><td><u>0.8685 ± 0.0922</u></td><td>-1.4%</td><td>1.6228 ± 0.6482</td><td><u>1.2110 ± 0.0915</u></td><td><strong>0.1185 ± 0.2352</strong></td><td>10.2x</td></tr><tr><td>soc-Slashdot0902</td><td><u>0.8141 ± 0.0038</u></td><td>0.6006 ± 0.0160</td><td><strong>0.8485 ± 0.0251</strong></td><td>+4.2%</td><td>1.7200 ± 0.6321</td><td><u>1.7025 ± 0.1236</u></td><td><strong>1.0422 ± 2.4623</strong></td><td>1.6x</td></tr><tr><td>email-EuAll</td><td><u>0.9892 ± 0.0002</u></td><td>0.3005 ± 0.0093</td><td><u>0.9887 ± 0.0011</u></td><td>-0.0%</td><td><u>1.7370 ± 0.7193</u></td><td>2.1331 ± 0.1533</td><td><strong>0.0245 ± 0.0092</strong></td><td>70.8x</td></tr><tr><td>web-Google</td><td><u>0.7775 ± 0.0029</u></td><td>0.2458 ± 0.0179</td><td><u>0.7775 ± 0.0412</u></td><td>-0.0%</td><td><u>3.9327 ± 1.5136</u></td><td>13.3756 ± 1.7921</td><td><strong>0.2085 ± 0.0746</strong></td><td>18.9x</td></tr><tr><td>com-youtube</td><td><u>0.7641 ± 0.0028</u></td><td>0.5764 ± 0.0123</td><td><strong>0.7724 ± 0.0010</strong></td><td>+1.1%</td><td><u>2.7419 ± 0.9938</u></td><td>19.2217 ± 1.7787</td><td><strong>0.1494 ± 0.0482</strong></td><td>18.4x</td></tr><tr><td>soc-Pokec</td><td><u>0.7601 ± 0.0041</u></td><td>0.4889 ± 0.0139</td><td><strong>0.8118 ± 0.0051</strong></td><td>+6.8%</td><td><u>23.1818 ± 7.2399</u></td><td>57.0848 ± 6.3802</td><td><strong>1.3335 ± 0.4920</strong></td><td>17.4x</td></tr><tr><td>wiki-topcats</td><td><u>0.5835 ± 0.0127</u></td><td>0.4405 ± 0.0078</td><td><strong>0.6045 ± 0.0058</strong></td><td>+3.6%</td><td><u>12.9090 ± 3.2590</u></td><td>53.2733 ± 2.6697</td><td><strong>1.2009 ± 0.3934</strong></td><td>10.7x</td></tr><tr><td>amazon</td><td><u>0.6895 ± 0.0078</u></td><td>0.6680 ± 0.0119</td><td><u>0.6840 ± 0.0036</u></td><td>-0.8%</td><td><u>5.3748 ± 1.8741</u></td><td>37.1710 ± 1.2494</td><td><strong>0.2871 ± 0.1228</strong></td><td>18.7x</td></tr><tr><td>wiki-Talk</td><td><u>0.9876 ± 0.0035</u></td><td>0.1690 ± 0.0025</td><td><strong>0.9905 ± 0.0007</strong></td><td>+0.3%</td><td><u>4.1343 ± 1.4032</u></td><td>18.9765 ± 2.0965</td><td><strong>0.2408 ± 0.1093</strong></td><td>17.2x</td></tr><tr><td>cit-Patents</td><td><u>0.5792 ± 0.0051</u></td><td><strong>0.6665 ± 0.0174</strong></td><td><u>0.6023 ± 0.0026</u></td><td>-9.6%</td><td><u>15.5281 ± 5.0716</u></td><td>74.4391 ± 4.1812</td><td><strong>0.8037 ± 0.3527</strong></td><td>19.3x</td></tr><tr><td>com-lj</td><td><u>0.6896 ± 0.0043</u></td><td>0.6597 ± 0.0191</td><td><strong>0.7114 ± 0.0020</strong></td><td>+3.2%</td><td><u>20.1064 ± 5.4268</u></td><td>148.2834 ± 21.9651</td><td><strong>1.5127 ± 0.5638</strong></td><td>13.3x</td></tr><tr><td>dblp</td><td><u>0.7601 ± 0.0138</u></td><td>0.7865 ± 0.0071</td><td><strong>0.7340 ± 0.0076</strong></td><td>-6.7%</td><td><u>7.7996 ± 1.7888</u></td><td>53.1173 ± 3.4795</td><td><strong>0.4818 ± 0.1982</strong></td><td>16.2x</td></tr><tr><td>soc-LiveJournal1</td><td><u>0.7595 ± 0.0031</u></td><td>0.4912 ± 0.0274</td><td><strong>0.8084 ± 0.0026</strong></td><td>+6.4%</td><td><u>44.1835 ± 10.9084</u></td><td>144.1625 ± 14.8407</td><td><strong>3.1099 ± 1.0781</strong></td><td>14.2x</td></tr></tbody></table>

are characterized by high diameters and long-range dependencies—structures where traditional GNNs typically struggle. For instance, on the road-luxembourg-osm graph, BRAVA-GNN achieves a correlation of $\tau_b = 0.6518$, representing a +214.2% improvement over GNN-Bet ($\tau_b = 0.2075$) and completely outclassing ABCDE, which fails to capture the ranking structure ($\tau_b = -0.1772$). Similar trends are observed in road-belgium-osm (+162.6%) and road-netherlands-osm (+86.1%). While our model occasionally trades marginal accuracy for speed on specific topologies (e.g., cit-Patents or p2p-Gnutella31), it remains highly competitive, consistently ranking as the best or strong second-best method while using orders of magnitude fewer parameters.

### 6.2.1 Computational Efficiency.
In terms of inference latency, BRAVA-GNN consistently records the lowest execution times across all 19 datasets. The speedup is particularly notable on larger graphs: for the web-Google network, our model completes inference in just 0.2085s, compared to 3.9327s for GNN-Bet (18.9x speedup) and 13.3765s for ABCDE. On email-EuAll, we achieve a peak speedup of 70.8x. This efficiency is further analyzed in Figure 3, which illustrates the scaling of inference time with respect to the number of edges. BRAVA-GNN exhibits a significantly lower intercept

## 6.3 Qualitative Assessment

In this section, we provide a qualitative assessment of our model's performance in predicting betweenness centrality through different visualizations, including rank-rank scatter plots, node-wise errors on small graph, and a visualization of the betweenness centrality on the road network of the island hosting the conference, Jeju Island.

<figure><img src="image_5.png" /><figcaption>Figure 3: Inference Time vs Number of Edges for BRAVA-GNN, GNN-Bet, and ABCDE. BRAVA-GNN demonstrates significantly lower inference times across varying graph sizes.</figcaption></figure>

### 6.3.1 Rank-rank plots.
These visualizations compare the predicted rankings against the ground-truth rankings obtained from exact betweenness centrality computations. Rankings are derived from the corresponding centrality scores; to handle ties, we adopt the *minimum ranking* scheme (values [10, 20, 20, 40] are assigned the ranks [1, 2, 2, 4]). Figure 4 reports the rank-rank plots for Wiki-Vote (a), amazon (b), and road-belgium-osm (c). In all cases, the dashed diagonal represents perfect agreement between predicted and ground-truth rankings.
<figure><img src="image_6.png" /><figcaption>Figure 4: Rank-rank plots. Comparison between true betweenness rank (x-axis) and predicted betweenness rank (y-axis). The red dashed line represents the ideal y = x prediction.</figcaption></figure>

<table><caption>**Table 3:** Number of learnable parameters. GNN-Bet [28] scales with graph size (|V|), while ABCDE [30] and our model are size-invariant. Notably, our model requires ~ 54× fewer parameters than ABCDE.</caption><thead><tr><td>Model</td><td># Parameters</td></tr></thead><tbody><tr><td>GNN-Bet</td><td>58,172,425</td></tr><tr><td>ABCDE</td><td>72,477</td></tr><tr><td>BRAVA-GNN</td><td>1,333</td></tr></tbody></table>

For Wiki-Vote (Fig. 4a), the predicted ranks align almost perfectly with the diagonal across the entire range, indicating an excellent agreement between predictions and exact betweenness centrality values. This behaviour is consistent with the very high Kendall's $\tau_b$ = 0.99 correlation observed on this dataset.

In the amazon network (Fig. 4b), predictions closely follow the diagonal for low and intermediate ranks, corresponding to nodes with higher betweenness centrality. However, for larger rank values (low-betweenness nodes), the plot exhibits a pronounced horizontal plateau. This effect reflects the large number of nodes sharing identical or near-identical betweenness values, which results in extensive ties when using the minimum ranking scheme. In this regime, the model assigns similar predicted scores to many nodes, leading to a saturation of predicted ranks despite increasing ground-truth ranks.

The road-belgium-osm network (Fig. 4c) displays a characteristic step-like structure, with alternating diagonal segments and horizontal bands. This pattern is expected for spatial road networks, where betweenness centrality takes a limited number of discrete values due to strong structural regularities and symmetry. As a consequence, small variations in predicted scores can produce visible rank jumps, even when predictions remain close to the ground truth in terms of absolute centrality values. The overall alignment along the diagonal nevertheless indicates that the model successfully captures the global ranking structure of the network.

### 6.3.2 Node-wise Error Visualization.
Figure 5 illustrates the model's performance on the Ca-NetScience co-authorship network, which consists of 379 nodes and 914 edges. In this visualization, node sizes are proportional to the ground-truth betweenness centrality values,

while node colors encode the rank difference $\Delta$ between predicted and true rankings.

Blue nodes correspond to overestimated ranks, red nodes to underestimated ranks, and white nodes indicate exact rank predictions. Overall, the model achieves a Kendall's $\tau_b$ correlation of 0.8688 on this graph, indicating a strong agreement between predicted and ground-truth rankings.

### 6.3.3 Jeju Island.
To further stress-test the model's inductive generalization, we evaluate BRAVA-GNN on the road network of the KDD'26 conference location, Jeju Island in South Korea. Unlike continental road networks often used in training, this dataset represents a closed system with distinct boundary conditions and finite

<figure><img src="image_7.png" /><figcaption>Figure 5: Prediction error on the Ca-NetScience network ($\tau_b$ = 0.8688), where color indicates the rank delta $\Delta$ between predicted and true rankings.</figcaption></figure>
topology. We extract the largest strongly connected component from OpenStreetMap (OSM) data, adhering method used to generate the other OSM datasets in our study. Despite the structural shift from the training distribution, BRAVA-GNN achieves a strong Kendall Tau correlation of $\tau_b = 0.7708$. As visualized in Figure 1, the predicted ranking (a) closely mirrors the ground-truth structure (b). This result suggests that the model has successfully learned the fundamental physical properties of betweenness centrality, specifically the flow dynamics constrained by geometry, rather than merely memorizing specific graph features or overfitting to continental patterns.

# 7 Conclusion

In this work, we presented BRAVA-GNN, a lightweight and scalable framework for approximating betweenness centrality. By shifting the learning paradigm from node-specific embeddings to size-invariant degree-mass features, our architecture achieves a drastic reduction in parameter count, requiring 54× fewer parameters than the most efficient baseline, while maintaining superior expressiveness.

A key innovation of our approach is the integration of hyperbolic random graphs into the training set. We demonstrated that this strategy equips the model with the necessary inductive bias to generalize to high-diameter topologies, solving a persistent limitation of prior GNN-based methods on road networks. Extensive experiments on 19 real-world datasets confirm that BRAVA-GNN establishes a new state-of-the-art, delivering up to 214% improvement in ranking accuracy and up to 70× inference speedup.

Future work will extend this topological learning framework to other path-based centrality measures, such as closeness centrality, and adapt the architecture for centrality ranking in temporal graphs.

# Acknowledgments

Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr). This work has been supported the French government National Research Agency (ANR) through the UCA JEDI (ANR-15-IDEX-01) and EUR DS4H (ANR-17-EURE-004), under the France 2030 programs "PEPR Networks of the Future" (ANR-22-PEFT-0002), through the 3IA Cote d'Azur Investments in the project with the reference number ANR-23-IACL-0001, and by SmartNet.
## References

[1] Ziyad AlGhamdi, Fuad Jamour, Spiros Skiadopoulos, and Panos Kalnis. 2017. A Benchmark for Betweenness Centrality Approximation Algorithms on Large Graphs. In *Proceedings of the 29th International Conference on Scientific and Statistical Database Management* (Chicago, IL, USA) (SSDBM '17). Association for Computing Machinery, New York, NY, USA, Article 6, 12 pages. doi:10.1145/3085504.3085510

[2] Massimo Bernaschi, Giancarlo Carbone, and Flavio Vella. 2016. Scalable betweenness centrality on multi-GPU systems. In *Proceedings of the ACM International Conference on Computing Frontiers* (Como, Italy) (CF '16). Association for Computing Machinery, New York, NY, USA, 29–36. doi:10.1145/2903150.2903153

[3] Marián Bogúná, Fragkiskos Papadopoulos, and Dmitri Krioukov. 2010. Sustaining the Internet with hyperbolic mapping. *Nature Communications* 1, 1 (2010), 62. doi:10.1038/ncomms1063

[4] Michele Borassi, Pierluigi Crescenzi, and Michel Habib. 2016. Into the Square: On the Complexity of Some Quadratic-time Solvable Problems. *Electronic Notes in Theoretical Computer Science* 322 (2016), 51–67. doi:10.1016/j.jentsc.2016.03.005 Proceedings of ICTCS 2015, the 16th Italian Conference on Theoretical Computer Science.

[5] Michele Borassi and Emanuele Natale. 2019. KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation. *ACM J. Exp. Algorithmics* 24, Article 1.2 (Feb. 2019), 35 pages. doi:10.1145/3284359

[6] Ulrik Brandes. 2001. A faster algorithm for betweenness centrality. *The Journal of Mathematical Sociology* 25, 2 (2001), 163–177. doi:10.1080/0022250X.2001.9990249

[7] Ulrik Brandes and Christian Pich. 2007. Centrality estimation in large networks. *International Journal of Bifurcation and Chaos* 17, 07 (2007), 2303–2318.

[8] Filippo Brunelli, Pierluigi Crescenzi, and Laurent Viennot. 2024. Making Temporal Betweenness Computation Faster and Restless. In *Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining* (Barcelona, Spain) (KDD '24). Association for Computing Machinery, New York, NY, USA, 163–174. doi:10.1145/3637528.3671825

[9] Wei Chen, Tie-yan Liu, Yanyan Lan, Zhi-ming Ma, and Hang Li. 2009. Ranking Measures and Loss Functions in Learning to Rank. In *Advances in Neural Information Processing Systems*, Y. Bengio, D. Schuurmans, J. Lafferty, C. Williams, and A. Culotta (Eds.), Vol. 22. Curran Associates, Inc. https://proceedings.neurips.cc/paper_files/paper/2009/file/2f55707d4193dc27118a0f19a1985716-Paper.pdf

[10] Changjun Fan, Li Zeng, Yuhui Ding, Muhao Chen, Yizhou Sun, and Zhong Liu. 2019. Learning to Identify High Betweenness Centrality Nodes from Scratch: A Novel Graph Neural Network Approach. In *Proceedings of the 28th ACM International Conference on Information and Knowledge Management* (Beijing, China) (CIKM '19). Association for Computing Machinery, New York, NY, USA, 559–568. doi:10.1145/3357384.3357979

[11] Linton C. Freeman. 1977. A Set of Measures of Centrality Based on Betweenness. *Sociometry* 40, 1 (March 1977), 35. doi:10.2307/3033543

[12] Tobias Friedrich and Anton Krohmer. 2018. On the Diameter of Hyperbolic Random Graphs. *SIAM Journal on Discrete Mathematics* 32, 2 (2018), 1314–1334. arXiv:https://doi.org/10.1137/17M1123961 doi:10.1137/17M1123961

[13] Octavian Ganea, Gary Becigneul, and Thomas Hofmann. 2018. Hyperbolic En-
tailment Cones for Learning Hierarchical Embeddings. In *Proceedings of the 35th
International Conference on Machine Learning* (Proceedings of Machine Learning
Research, Vol. 80), Jennifer Dy and Andreas Krause (Eds.). PMLR, 1646–1655.
https://proceedings.mlr.press/v80/ganea18a.html

[14] Robert Geisberger, Peter Sanders, and Dominik Schultes. 2008. *Better Approximation of Betweenness Centrality*. 90–100. doi:10.1137/1.9781611972887.9

[15] Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. In *Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining* (San Francisco, California, USA) (KDD '16). Association for Computing Machinery, New York, NY, USA, 855–864. doi:10.1145/2939672.2939754

[16] Luca Gugelmann, Konstantinos Panagiotou, and Ueli Peter. 2012. Random Hyperbolic Graphs: Degree Sequence and Clustering. In *Automata, Languages, and Programming*, Artur Czumaj, Kurt Mehlhorn, Andrew Pitts, and Roger Wattenhofer (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 573–585.

[17] Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. 2008. Exploring Network Structure, Dynamics, and Function using NetworkX. In *Proceedings of the 7th Python in Science Conference*, Gaël Varoquaux, Travis Vaught, and Jarrod Millman (Eds.). Pasadena, CA USA, 11 – 15.

[18] Loc Hoang, Matteo Pontecorvi, Roshan Dathathri, Gurbinder Gill, Bozhi You, Keshav Pingali, and Vijaya Ramachandran. 2019. A round-efficient distributed betweenness centrality algorithm. In *Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming* (Washington, District of Columbia) (PPOPP '19). Association for Computing Machinery, New York, NY, USA, 272–286. doi:10.1145/3293883.3295729

[19] Qiang-Sheng Hua, Haoqiang Fan, Ming Ai, Lixiang Qian, Yangyang Li, Xuanhua Shi, and Hai Jin. 2016. Nearly Optimal Distributed Algorithm for Computing Betweenness Centrality. In *2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS)*. 271–280. doi:10.1109/ICDCS.2016.89

[20] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001. Which Problems Have Strongly Exponential Complexity? *J. Comput. System Sci.* 63, 4 (2001), 512–530. doi:10.1006/jcss.2001.1774

[21] Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Bogúná. 2010. Hyperbolic geometry of complex networks. *Phys. Rev. E* 82 (Sep 2010), 036106. Issue 3. doi:10.1103/PhysRev.E.82.036106

[22] Ranjan Kumar Behera, Santanu Kumar Rath, Sanjay Misra, Robertas Damaševičius, and Rytis Maskeliūnas. 2019. Distributed Centrality Analysis of Social Network Data Using MapReduce. *Algorithms* 12, 8 (2019). doi:10.3390/a12080161

[23] J. Lee, Y. Lee, S. M. Oh, and B. Kahng. 2021. Betweenness centrality of teams in social networks. *Chaos: An Interdisciplinary Journal of Nonlinear Science* 31, 6 (2021), 061108. doi:10.1063/5.0054127

[24] Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data.

[25] Cong Li, Qian Li, Piet Mieghem, H. Stanley, and Huijuan Wang. 2014. Correlation between centrality metrics and their application to the opinion model. *The European Physical Journal B* 88 (09 2014). doi:10.1140/epjb/2015-50671-y

[26] Ahmad Mahmody, Charalampos E. Tsourakakis, and Eli Upfal. 2016. Scalable Betweenness Centrality Maximization via Sampling. In *Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining* (San Francisco, California, USA) (KDD '16). Association for Computing Machinery, New York, NY, USA, 1765–1773. doi:10.1145/2939672.2939869

[27] Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata. 2019. Fast Approximations of Betweenness Centrality with Graph Neural Networks. In *Proceedings of the 28th ACM International Conference on Information and Knowledge Management* (Beijing, China) (CIKM '19). Association for Computing Machinery, New York, NY, USA, 2149–2152. doi:10.1145/3357384.3358080

[28] Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata. 2019. Graph Neural Networks for Fast Node Ranking Approximation. *ACM Trans. Knowl. Discov. Data* 15, 5, Article 78 (May 2021), 32 pages. doi:10.1145/3446217

[29] Natarajan Mohananathan and Xiaojia He. 2016. Correlation and Regression Analysis for Node Betweenness Centrality. *International Journal in Foundations of Computer Science and Technology* 6, 6 (Nov. 2016), 01–20. doi:10.5212/ijfest.2016.6601

[30] Martin Mirakyan. 2021. ABCDE: Approximating Betweenness-Centrality ranking with progressive-DropEdge. *PeerJ Computer Science* 7 (2021), e699.

[31] Tobias Müller and Merlijn Staps. 2019. The diameter of KPKVB random graphs. *Advances in Applied Probability* 51, 2 (2019), 358–377. http://www.jstor.org/stable/45277962

[32] Maximillian Nickel and Douwe Kiela. 2017. Poincaré Embeddings for Learning Hierarchical Representations. In *Advances in Neural Information Processing Systems*, I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc. https://proceedings.neurips.cc/paper_files/paper/2017/file/59dfa2df42d9e3d41f5b02bcf32229dd-Paper.pdf

[33] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. PyTorch: An Imperative Style, High-Performance Deep Learning Library. (dec 2019). doi:10.48550/arXiv.1912.01703

[34] Rami Puzis, Yaniv Altshuler, Yuval Elovici, Shlomo Bekhor, Yoram Shiftan, and Alex (Sandy) Pentland. 2013. Augmented Betweenness Centrality for Environmentally Aware Traffic Monitoring in Transportation Networks. *Journal of Intelligent Transportation Systems* 17, 1 (2013), 91–105. doi:10.1080/15472450.2012.716663

[35] Matteo Riondato and Evgenios M. Kornaropoulos. 2014. Fast approximation of betweenness centrality through sampling. In *Proceedings of the 7th ACM International Conference on Web Search and Data Mining* (New York, New York, USA) (WSDM '14). Association for Computing Machinery, New York, NY, USA, 413–422. doi:10.1145/2556195.2556224

[36] Matteo Riondato and Eli Upfal. 2018. ABRA: Approximating Betweenness Centrality in Static and Dynamic Graphs with Rademacher Averages. *ACM Trans. Knowl. Discov. Data* 12, 5, Article 61 (July 2018), 38 pages. doi:10.1145/3208351

[37] Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. In *AAAI* https://networkrepository.com

[38] Edgar Solomonik, Maciej Besta, Flavio Vella, and Torsten Hoefler. 2017. Scaling betweenness centrality using communication-efficient sparse matrix multiplication. In *Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (Denver, Colorado) (SC '17)*. Association for Computing Machinery, New York, NY, USA, 14 pages. doi:10.1145/3126908.3126971

[39] Christian L. Staudt, Aleksejs Sazonovs, and Henning Meyerhenke. 2015. NetworkKit: A Tool Suite for Large-scale Complex Network Analysis. arXiv:1403.3005 (Nov. 2015). doi:10.48550/arXiv.1403.3005 arXiv:1403.3005

[40] Flavio Vella, Massimo Bernaschi, and Giancarlo Carbone. 2018. Dynamic Merging of Frontiers for Accelerating the Evaluation of Betweenness Centrality. *ACM J. Exp. Algorithmics* 23, Article 1.4 (March 2018), 19 pages. doi:10.1145/3182656
[41] Moritz von Looz and Henning Meyerhenke. 2016. Querying Probabilistic Neighborhoods in Spatial Data Sets Efficiently. In *Combinatorial Algorithms*, Veli Mäkinen, Simon J. Puglisi, and Leena Salmela (Eds.). Springer International Publishing, Cham, 449–460.

[42] Yu Wang, Gao Cong, Guojie Song, and Kunqing Xie. 2010. Community-based greedy algorithm for mining top-K influential nodes in mobile social networks. In *Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining* (Washington, DC, USA) (KDD '10). Association for Computing Machinery, New York, NY, USA, 1039–1048. doi:10.1145/1835804.1835935

[43] Yuichi Yoshida. 2014. Almost linear-time algorithms for adaptive betweenness centrality using hypergraph sketches. In *Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining* (New York, New York, USA) (KDD '14). Association for Computing Machinery, New York, NY, USA, 1416–1425. doi:10.1145/2623330.2623626

[44] Shiqi Zhang, Renchi Yang, Jing Tang, Xiaokui Xiao, and Bo Tang. 2023. Efficient Approximation Algorithms for Spanning Centrality. In *Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining* (KDD '23). Association for Computing Machinery, New York, NY, USA, 3386–3395. doi:10.1145/3580305.3599323

# 8 Appendix

## 8.1 Ablation Study

To assess the impact of different components and hyperparameters of our proposed model, we conduct an ablation study focusing on the choice of initial node features, the number of layers, the training dataset composition, the hidden dimension, and dropout rate. All results reported in this section display the average Kendall Tau $\tau_b$ correlation across five random seeds. Regarding the selection criteria, for hyperparameters that directly influence the number of learnable parameters (e.g., hidden dimension, number of layers), we chose the configuration that strikes the best balance between performance and parameter efficiency. Conversely, for hyperparameters that do not affect model size (e.g., dropout rate), we selected the values that achieved the highest correlation. The selected hyperparameter for the final model is indicated with a † symbol.

### 8.1.1 Initial Node Features.
We evaluate the effect of using different initial node features on the model's performance. We evaluate the model's performance using m-th order degree mass features, where m ranges from 1 (simple degree) to 12. The results, summarized in Table 4 and 5, show that simple degree features (D1) provide a strong baseline ($\tau = 0.7485$). Next, incorporating higher-order degree features enhances the model's ability to approximate betweenness centrality rankings. This suggests that capturing more extensive local connectivity information is beneficial for the task. Interestingly, performance does not increase monotonically with neighborhood hop count: adding 2-hop features slightly degrades performance in Kendall's $\tau_b$ (0.7485→0.7477), while 3-hop features provide a substantial improvement (0.7477→0.7737). These large gains are mainly observed in high-diameter road networks, for instance, road-luxembourg-osm sees Kendall's $\tau_b$ increase from 0.42 (D2) to 0.55 (D3). This finding suggests that 3-hop neighborhoods capture structural patterns relevant to betweenness that 2-hop neighborhoods cannot. However, this trend does not persist uniformly as we scale to 12-hop neighborhoods.

### 8.1.2 Number of Layers.
We investigate the impact of the number of GNN layers on model performance. We experiment with configurations ranging from 0 to 10 layers. The 0-layer configuration represents a baseline where the initial features are passed directly through the MLP without neighborhood aggregation. The

results in Tables 6 and 7 demonstrate that message passing is important as the 0-layer model underperforms. While deeper networks show marginal improvement, the 2-layer configuration strikes the best balance between model parameters and performance, able to sufficiently capture neighborhood information.

#### 8.1.3 Training Dataset Composition.
To evaluate the effect of training dataset composition, we compare models trained solely on scale-free graphs against those trained on hyperbolic graphs and the combination of both. The results, shown in Table 8, demonstrate that including hyperbolic graphs in the training set substantially improves generalization to real-world datasets, particularly road networks.

#### 8.1.4 Hidden Dimension.
Table 9 compares hidden dimensions ranging from 8 to 128. While 128 hidden dimension yields marginally higher accuracy ($\tau = 0.7904$ vs. $\tau = 0.7899$ for dim 12), this improvement is well within the standard deviation of $\pm 0.0095$ and significantly increases parameter count. Thus, we select a dimension of 12 to maintain a lightweight model.

#### 8.1.5 Dropout.
We vary the dropout rate from 0.1 to 0.7 in Table 10. We observe peak performance at a rate of 0.3.

## 8.2 Additional information on datasets

In Table 11 are listed the number of nodes and edges for all the graphs in the test set. In histogram of Figure 6 we show the distribution of the gamma across 15 graphs.
<table><caption>Table 4: Ablation: Node Features (Kendall Tau ↑) (Part 1/2)</caption><thead><tr><th>Graph</th><th>Degree (D1)</th><th>2-hop (D2)</th><th>3-hop (D3)</th><th>4-hop (D4)</th><th>5-hop (D5)</th><th>6-hop (D6)†</th></tr></thead><tbody><tr><td colspan="7"><strong>Road Networks</strong></td></tr><tr><td>road-luxembourg-osm</td><td>0.4395 ± 0.1207</td><td>0.4249 ± 0.1172</td><td>0.5552 ± 0.0982</td><td>0.5577 ± 0.0716</td><td>0.5228 ± 0.1848</td><td>0.6271 ± 0.0375†</td></tr><tr><td>road-roadNet-PA</td><td>0.6853 ± 0.0960</td><td>0.7057 ± 0.0735</td><td>0.7564 ± 0.0266</td><td>0.7864 ± 0.0407</td><td>0.7593 ± 0.0644</td><td><u>0.8045 ± 0.0309</u>†</td></tr><tr><td>road-belgium-osm</td><td>0.4999 ± 0.1165</td><td>0.4947 ± 0.0985</td><td>0.6107 ± 0.0823</td><td>0.6182 ± 0.0681</td><td>0.5851 ± 0.1613</td><td>0.6810 ± 0.0382†</td></tr><tr><td>road-roadNet-CA</td><td>0.6739 ± 0.0928</td><td>0.6922 ± 0.0710</td><td>0.7399 ± 0.0278</td><td>0.7719 ± 0.0431</td><td>0.7448 ± 0.0625</td><td><u>0.7907 ± 0.0311</u>†</td></tr><tr><td>road-netherlands-osm</td><td>0.6817 ± 0.1371</td><td>0.6888 ± 0.0738</td><td>0.7765 ± 0.0690</td><td>0.7760 ± 0.0831</td><td>0.7602 ± 0.1217</td><td>0.8290 ± 0.0359†</td></tr><tr><td colspan="7"><strong>Social and Web Networks</strong></td></tr><tr><td>p2p-Gnutella31</td><td><strong>0.9136 ± 0.0068</strong></td><td>0.9044 ± 0.0093</td><td>0.9073 ± 0.0043</td><td>0.9033 ± 0.0045</td><td>0.9063 ± 0.0091</td><td>0.9049 ± 0.0032†</td></tr><tr><td>soc-Epinions1</td><td>0.9051 ± 0.0028</td><td>0.9045 ± 0.0035</td><td>0.9095 ± 0.0018</td><td><strong>0.9103 ± 0.0033</strong></td><td>0.9065 ± 0.0040</td><td>0.9095 ± 0.0027†</td></tr><tr><td>soc-Slashdot0902</td><td>0.8558 ± 0.0149</td><td>0.8566 ± 0.0194</td><td>0.8680 ± 0.0032</td><td><u>0.8716 ± 0.0070</u></td><td>0.8645 ± 0.0081</td><td>0.8677 ± 0.0062†</td></tr><tr><td>email-EuAll</td><td>0.9898 ± 0.0014</td><td>0.9893 ± 0.0025</td><td><u>0.9904 ± 0.0011</u></td><td>0.9899 ± 0.0013</td><td>0.9901 ± 0.0008</td><td>0.9896 ± 0.0006†</td></tr><tr><td>web-Google</td><td>0.7867 ± 0.0022</td><td>0.7879 ± 0.0035</td><td>0.7890 ± 0.0029</td><td>0.7888 ± 0.0035</td><td>0.7883 ± 0.0050</td><td><strong>0.7927 ± 0.0027</strong>†</td></tr><tr><td>com-youtube</td><td>0.7758 ± 0.0045</td><td>0.7761 ± 0.0035</td><td>0.7764 ± 0.0013</td><td>0.7732 ± 0.0041</td><td>0.7753 ± 0.0021</td><td><u>0.7765 ± 0.0026</u>†</td></tr><tr><td>soc-Pokec</td><td>0.7948 ± 0.0089</td><td>0.7922 ± 0.0039</td><td><u>0.8066 ± 0.0031</u></td><td><strong>0.8076 ± 0.0106</strong></td><td>0.7967 ± 0.0121</td><td>0.8053 ± 0.0044†</td></tr><tr><td>wiki-topcats</td><td>0.6091 ± 0.0053</td><td>0.5988 ± 0.0293</td><td>0.6051 ± 0.0112</td><td>0.6103 ± 0.0159</td><td>0.6021 ± 0.0171</td><td>0.6166 ± 0.0052†</td></tr><tr><td>amazon</td><td>0.6977 ± 0.0074</td><td>0.6928 ± 0.0104</td><td>0.6970 ± 0.0049</td><td>0.6944 ± 0.0054</td><td>0.6986 ± 0.0052</td><td>0.6985 ± 0.0054†</td></tr><tr><td>wiki-Talk</td><td>0.9913 ± 0.0008</td><td>0.9914 ± 0.0014</td><td><strong>0.9922 ± 0.0007</strong></td><td>0.9920 ± 0.0011</td><td>0.9918 ± 0.0005</td><td>0.9913 ± 0.0005†</td></tr><tr><td>cit-Patents</td><td><strong>0.6363 ± 0.0079</strong></td><td><u>0.6345 ± 0.0122</u></td><td>0.6317 ± 0.0072</td><td>0.6296 ± 0.0069</td><td>0.6229 ± 0.0092</td><td>0.6308 ± 0.0055†</td></tr><tr><td>com-lj</td><td>0.7188 ± 0.0028</td><td>0.7189 ± 0.0013</td><td>0.7172 ± 0.0033</td><td>0.7150 ± 0.0064</td><td>0.7168 ± 0.0022</td><td><u>0.7190 ± 0.0022</u>†</td></tr><tr><td>dblp</td><td><strong>0.7723 ± 0.0129</strong></td><td>0.7569 ± 0.0177</td><td>0.7690 ± 0.0112</td><td>0.7685 ± 0.0120</td><td>0.7630 ± 0.0108</td><td>0.7683 ± 0.0080†</td></tr><tr><td>soc-LiveJournal1</td><td>0.7948 ± 0.0063</td><td>0.7957 ± 0.0054</td><td>0.8017 ± 0.0026</td><td>0.8030 ± 0.0089</td><td>0.7966 ± 0.0086</td><td><u>0.8043 ± 0.0047</u>†</td></tr><tr><td><strong>AVG</strong></td><td>0.7485 ± 0.0341</td><td>0.7477 ± 0.0293</td><td>0.7737 ± 0.0191</td><td>0.7772 ± 0.0209</td><td>0.7680 ± 0.0363</td><td><u>0.7899 ± 0.0120</u>†</td></tr></tbody></table>

<figure><img src="image_8.png" /><figcaption>Figure 6: γ distribution of dataset of Table 1</figcaption></figure>
<table><caption>Table 5: Ablation: Node Features (Kendall Tau ↑) (Part 2/2)</caption><thead><tr><th>Graph</th><th>7-hop (D7)</th><th>8-hop (D8)</th><th>9-hop (D9)</th><th>10-hop (D10)</th><th>11-hop (D11)</th><th>12-hop (D12)</th></tr></thead><tbody><tr><td colspan="7"><strong>Road Networks</strong></td></tr><tr><td>road-luxembourg-osm</td><td>0.4517 ± 0.1794</td><td>0.5894 ± 0.1040</td><td>0.6381 ± 0.0511</td><td>0.5763 ± 0.1871</td><td><u>0.6454 ± 0.0759</u></td><td><u>0.6665 ± 0.0601</u></td></tr><tr><td>road-roadNet-PA</td><td>0.7216 ± 0.0973</td><td>0.7770 ± 0.0655</td><td><strong>0.8110 ± 0.0173</strong></td><td>0.7418 ± 0.1411</td><td>0.7865 ± 0.0522</td><td>0.7894 ± 0.0409</td></tr><tr><td>road-belgium-osm</td><td>0.5247 ± 0.1867</td><td>0.6480 ± 0.1001</td><td>0.7004 ± 0.0474</td><td>0.6309 ± 0.1971</td><td><u>0.7010 ± 0.0776</u></td><td><u>0.7109 ± 0.0673</u></td></tr><tr><td>road-roadNet-CA</td><td>0.7057 ± 0.1006</td><td>0.7627 ± 0.0661</td><td><strong>0.7978 ± 0.0173</strong></td><td>0.7291 ± 0.1417</td><td>0.7741 ± 0.0525</td><td>0.7764 ± 0.0431</td></tr><tr><td>road-netherlands-osm</td><td>0.6706 ± 0.2246</td><td>0.7828 ± 0.1061</td><td><strong>0.8375 ± 0.0363</strong></td><td>0.7578 ± 0.1817</td><td><u>0.8300 ± 0.0494</u></td><td>0.8045 ± 0.0878</td></tr><tr><td colspan="7"><strong>Social and Web Networks</strong></td></tr><tr><td>p2p-Gnutella31</td><td>0.9059 ± 0.0050</td><td>0.9087 ± 0.0042</td><td>0.9112 ± 0.0023</td><td>0.9079 ± 0.0058</td><td>0.9034 ± 0.0110</td><td><u>0.9118 ± 0.0064</u></td></tr><tr><td>soc-Epinions1</td><td><u>0.9102 ± 0.0046</u></td><td>0.9084 ± 0.0035</td><td>0.9100 ± 0.0021</td><td>0.9079 ± 0.0049</td><td>0.9093 ± 0.0017</td><td>0.9091 ± 0.0021</td></tr><tr><td>soc-Slashdot0902</td><td>0.8673 ± 0.0100</td><td><strong>0.8721 ± 0.0053</strong></td><td>0.8658 ± 0.0084</td><td>0.8636 ± 0.0126</td><td>0.8642 ± 0.0106</td><td>0.8657 ± 0.0120</td></tr><tr><td>email-EuAll</td><td>0.9900 ± 0.0005</td><td><strong>0.9906 ± 0.0005</strong></td><td>0.9890 ± 0.0007</td><td>0.9892 ± 0.0013</td><td>0.9888 ± 0.0017</td><td>0.9890 ± 0.0015</td></tr><tr><td>web-Google</td><td>0.7887 ± 0.0054</td><td>0.7867 ± 0.0026</td><td><u>0.7915 ± 0.0016</u></td><td>0.7894 ± 0.0024</td><td>0.7910 ± 0.0017</td><td>0.7892 ± 0.0026</td></tr><tr><td>com-youtube</td><td>0.7755 ± 0.0022</td><td>0.7746 ± 0.0054</td><td>0.7743 ± 0.0021</td><td>0.7749 ± 0.0054</td><td><strong>0.7771 ± 0.0038</strong></td><td>0.7736 ± 0.0037</td></tr><tr><td>soc-Pokec</td><td>0.8019 ± 0.0079</td><td>0.8014 ± 0.0048</td><td>0.8043 ± 0.0021</td><td>0.7933 ± 0.0214</td><td>0.8018 ± 0.0038</td><td>0.7987 ± 0.0060</td></tr><tr><td>wiki-topcats</td><td>0.6101 ± 0.0167</td><td>0.6191 ± 0.0072</td><td><strong>0.6238 ± 0.0038</strong></td><td>0.6036 ± 0.0286</td><td><u>0.6203 ± 0.0060</u></td><td>0.6176 ± 0.0050</td></tr><tr><td>amazon</td><td><strong>0.7022 ± 0.0049</strong></td><td><u>0.7006 ± 0.0055</u></td><td>0.6957 ± 0.0048</td><td>0.6987 ± 0.0090</td><td>0.6986 ± 0.0044</td><td>0.6970 ± 0.0026</td></tr><tr><td>wiki-Talk</td><td>0.9919 ± 0.0006</td><td><u>0.9921 ± 0.0004</u></td><td>0.9913 ± 0.0006</td><td>0.9915 ± 0.0008</td><td>0.9911 ± 0.0010</td><td>0.9911 ± 0.0010</td></tr><tr><td>cit-Patents</td><td>0.6312 ± 0.0099</td><td>0.6286 ± 0.0138</td><td>0.6256 ± 0.0050</td><td>0.6212 ± 0.0052</td><td>0.6280 ± 0.0096</td><td>0.6279 ± 0.0121</td></tr><tr><td>com-lj</td><td>0.7181 ± 0.0038</td><td>0.7154 ± 0.0045</td><td>0.7187 ± 0.0018</td><td>0.7172 ± 0.0042</td><td><strong>0.7198 ± 0.0029</strong></td><td>0.7171 ± 0.0038</td></tr><tr><td>dblp</td><td>0.7685 ± 0.0098</td><td>0.7651 ± 0.0084</td><td><u>0.7709 ± 0.0051</u></td><td>0.7654 ± 0.0092</td><td>0.7660 ± 0.0037</td><td>0.7694 ± 0.0030</td></tr><tr><td>soc-LiveJournal1</td><td>0.8009 ± 0.0088</td><td>0.7972 ± 0.0064</td><td><strong>0.8046 ± 0.0023</strong></td><td>0.7967 ± 0.0162</td><td>0.8024 ± 0.0040</td><td>0.7996 ± 0.0036</td></tr><tr><td><strong>AVG</strong></td><td>0.7546 ± 0.0462</td><td>0.7800 ± 0.0271</td><td><strong>0.7927 ± 0.0112</strong></td><td>0.7714 ± 0.0513</td><td>0.7894 ± 0.0197</td><td>0.7897 ± 0.0192</td></tr></tbody></table>
<table><caption>Table 6: Ablation: Network Depth (Kendall Tau ↑) (Part 1/2)</caption><thead><tr><th>Graph</th><th>0 Layers (MLP)</th><th>1 Layers</th><th>2 Layers<sup>†</sup></th><th>3 Layers</th><th>4 Layers</th><th>5 Layers</th></tr></thead><tbody><tr><td><strong>Road Networks</strong></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>road-luxembourg-osm</td><td>0.5195 ± 0.0089</td><td>0.5363 ± 0.0487</td><td>0.5552 ± 0.0982<sup>†</sup></td><td>0.5299 ± 0.1102</td><td>0.4746 ± 0.1158</td><td><u>0.5691 ± 0.0935</u></td></tr><tr><td>road-roadNet-PA</td><td>0.7333 ± 0.0190</td><td><strong>0.7805 ± 0.0161</strong></td><td><u>0.7564 ± 0.0266<sup>†</sup></u></td><td>0.7367 ± 0.0458</td><td>0.7300 ± 0.0338</td><td>0.7311 ± 0.0373</td></tr><tr><td>road-belgium-osm</td><td>0.5787 ± 0.0082</td><td>0.6004 ± 0.0479</td><td>0.6107 ± 0.0823<sup>†</sup></td><td>0.5822 ± 0.0911</td><td>0.5392 ± 0.0951</td><td>0.6173 ± 0.0787</td></tr><tr><td>road-roadNet-CA</td><td>0.7153 ± 0.0199</td><td><strong>0.7626 ± 0.0196</strong></td><td><u>0.7399 ± 0.0278<sup>†</sup></u></td><td>0.7208 ± 0.0434</td><td>0.7148 ± 0.0366</td><td>0.7163 ± 0.0363</td></tr><tr><td>road-netherlands-osm</td><td>0.7738 ± 0.0061</td><td>0.7903 ± 0.0439</td><td>0.7765 ± 0.0690<sup>†</sup></td><td>0.7486 ± 0.0766</td><td>0.7300 ± 0.0658</td><td>0.7814 ± 0.0686</td></tr><tr><td><strong>Social and Web Networks</strong></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>p2p-Gnutella31</td><td>0.8955 ± 0.0062</td><td>0.9029 ± 0.0100</td><td>0.9073 ± 0.0043<sup>†</sup></td><td>0.9051 ± 0.0074</td><td><strong>0.9113 ± 0.0036</strong></td><td>0.9063 ± 0.0032</td></tr><tr><td>soc-Epinions1</td><td>0.8859 ± 0.0075</td><td>0.9070 ± 0.0064</td><td>0.9095 ± 0.0018<sup>†</sup></td><td>0.9123 ± 0.0043</td><td>0.9178 ± 0.0061</td><td>0.9160 ± 0.0024</td></tr><tr><td>soc-Slashdot0902</td><td>0.8146 ± 0.0256</td><td>0.8619 ± 0.0158</td><td>0.8680 ± 0.0032<sup>†</sup></td><td>0.8730 ± 0.0107</td><td>0.8800 ± 0.0136</td><td>0.8800 ± 0.0037</td></tr><tr><td>email-EuAll</td><td>0.9893 ± 0.0015</td><td><strong>0.9907 ± 0.0003</strong></td><td>0.9904 ± 0.0011<sup>†</sup></td><td>0.9899 ± 0.0014</td><td>0.9893 ± 0.0011</td><td><u>0.9906 ± 0.0004</u></td></tr><tr><td>web-Google</td><td>0.7847 ± 0.0021</td><td><u>0.7910 ± 0.0020</u></td><td>0.7890 ± 0.0029<sup>†</sup></td><td>0.7903 ± 0.0008</td><td><strong>0.7917 ± 0.0033</strong></td><td>0.7900 ± 0.0022</td></tr><tr><td>com-youtube</td><td>0.7705 ± 0.0022</td><td>0.7733 ± 0.0053</td><td><u>0.7764 ± 0.0013<sup>†</sup></u></td><td>0.7742 ± 0.0034</td><td>0.7740 ± 0.0020</td><td>0.7743 ± 0.0024</td></tr><tr><td>soc-Pokec</td><td>0.7786 ± 0.0032</td><td>0.8042 ± 0.0089</td><td>0.8066 ± 0.0031<sup>†</sup></td><td>0.8065 ± 0.0052</td><td>0.8066 ± 0.0062</td><td><u>0.8095 ± 0.0118</u></td></tr><tr><td>wiki-topcats</td><td>0.5154 ± 0.0324</td><td>0.5841 ± 0.0307</td><td>0.6051 ± 0.0112<sup>†</sup></td><td>0.6004 ± 0.0271</td><td>0.5955 ± 0.0167</td><td>0.6061 ± 0.0092</td></tr><tr><td>amazon</td><td>0.6834 ± 0.0053</td><td>0.6870 ± 0.0106</td><td><u>0.6970 ± 0.0049<sup>†</sup></u></td><td>0.6948 ± 0.0073</td><td>0.6936 ± 0.0031</td><td>0.6936 ± 0.0037</td></tr><tr><td>wiki-Talk</td><td>0.9892 ± 0.0025</td><td>0.9915 ± 0.0006</td><td><strong>0.9922 ± 0.0007<sup>†</sup></strong></td><td>0.9916 ± 0.0010</td><td>0.9917 ± 0.0008</td><td>0.9921 ± 0.0004</td></tr><tr><td>cit-Patents</td><td><u>0.6279 ± 0.0071</u></td><td>0.6193 ± 0.0069</td><td><strong>0.6317 ± 0.0072<sup>†</sup></strong></td><td>0.6232 ± 0.0091</td><td>0.6220 ± 0.0082</td><td>0.6245 ± 0.0109</td></tr><tr><td>com-lj</td><td>0.7088 ± 0.0012</td><td>0.7148 ± 0.0029</td><td><u>0.7172 ± 0.0033<sup>†</sup></u></td><td>0.7160 ± 0.0046</td><td>0.7162 ± 0.0027</td><td>0.7151 ± 0.0040</td></tr><tr><td>dblp</td><td>0.7336 ± 0.0151</td><td>0.7517 ± 0.0160</td><td><strong>0.7690 ± 0.0112<sup>†</sup></strong></td><td>0.7633 ± 0.0152</td><td>0.7642 ± 0.0142</td><td>0.7646 ± 0.0093</td></tr><tr><td>soc-LiveJournal1</td><td>0.7769 ± 0.0036</td><td>0.8032 ± 0.0078</td><td>0.8017 ± 0.0026<sup>†</sup></td><td>0.8073 ± 0.0032</td><td><u>0.8192 ± 0.0090</u></td><td>0.8137 ± 0.0047</td></tr><tr><td><strong>AVG</strong></td><td>0.7513 ± 0.0093</td><td>0.7712 ± 0.0158</td><td>0.7737 ± 0.0191<sup>†</sup></td><td>0.7666 ± 0.0246</td><td>0.7611 ± 0.0230</td><td>0.7732 ± 0.0201</td></tr></tbody></table>
<table><caption>Table 7: Ablation: Network Depth (Kendall Tau ↑) (Part 2/2)</caption><thead><tr><th>Graph</th><th>6 Layers</th><th>7 Layers</th><th>8 Layers</th><th>9 Layers</th><th>10 Layers</th></tr></thead><tbody><tr><td colspan="6"><strong>Road Networks</strong></td></tr><tr><td>road-luxembourg-osm</td><td>0.4865 ± 0.1436</td><td><strong>0.6046 ± 0.0607</strong></td><td>0.5326 ± 0.0926</td><td>0.5530 ± 0.0543</td><td>0.5664 ± 0.1714</td></tr><tr><td>road-roadNet-PA</td><td>0.7210 ± 0.0395</td><td>0.7530 ± 0.0311</td><td>0.7362 ± 0.0223</td><td>0.7463 ± 0.0189</td><td>0.7422 ± 0.0436</td></tr><tr><td>road-belgium-osm</td><td>0.5457 ± 0.1210</td><td><strong>0.6456 ± 0.0575</strong></td><td>0.5899 ± 0.0758</td><td><u>0.6255 ± 0.0371</u></td><td>0.6166 ± 0.1444</td></tr><tr><td>road-roadNet-CA</td><td>0.7049 ± 0.0413</td><td>0.7379 ± 0.0311</td><td>0.7188 ± 0.0236</td><td>0.7317 ± 0.0195</td><td>0.7257 ± 0.0458</td></tr><tr><td>road-netherlands-osm</td><td>0.7375 ± 0.0867</td><td><u>0.7908 ± 0.0613</u></td><td>0.7630 ± 0.0953</td><td><strong>0.7951 ± 0.0206</strong></td><td>0.7725 ± 0.1211</td></tr><tr><td colspan="6"><strong>Social and Web Networks</strong></td></tr><tr><td>p2p-Gnutella31</td><td><u>0.9099 ± 0.0045</u></td><td>0.9079 ± 0.0059</td><td>0.9062 ± 0.0047</td><td>0.9095 ± 0.0028</td><td>0.9092 ± 0.0037</td></tr><tr><td>soc-Epinions1</td><td>0.9175 ± 0.0029</td><td>0.9176 ± 0.0023</td><td>0.9180 ± 0.0028</td><td><strong>0.9207 ± 0.0022</strong></td><td><u>0.9203 ± 0.0028</u></td></tr><tr><td>soc-Slashdot0902</td><td><u>0.8847 ± 0.0034</u></td><td>0.8820 ± 0.0064</td><td>0.8803 ± 0.0044</td><td>0.8840 ± 0.0064</td><td><strong>0.8861 ± 0.0071</strong></td></tr><tr><td>email-EuAll</td><td>0.9903 ± 0.0007</td><td>0.9895 ± 0.0008</td><td>0.9893 ± 0.0008</td><td>0.9893 ± 0.0010</td><td>0.9898 ± 0.0006</td></tr><tr><td>web-Google</td><td>0.7886 ± 0.0016</td><td>0.7883 ± 0.0025</td><td>0.7892 ± 0.0028</td><td>0.7889 ± 0.0039</td><td>0.7887 ± 0.0041</td></tr><tr><td>com-youtube</td><td>0.7728 ± 0.0026</td><td><strong>0.7779 ± 0.0014</strong></td><td>0.7749 ± 0.0029</td><td>0.7745 ± 0.0014</td><td>0.7757 ± 0.0014</td></tr><tr><td>soc-Pokec</td><td>0.8069 ± 0.0056</td><td>0.8029 ± 0.0107</td><td>0.8005 ± 0.0105</td><td><strong>0.8117 ± 0.0068</strong></td><td>0.8012 ± 0.0115</td></tr><tr><td>wiki-topcats</td><td>0.6048 ± 0.0101</td><td><strong>0.6113 ± 0.0086</strong></td><td><u>0.6112 ± 0.0067</u></td><td>0.6098 ± 0.0063</td><td>0.6042 ± 0.0074</td></tr><tr><td>amazon</td><td>0.6933 ± 0.0027</td><td><strong>0.6972 ± 0.0040</strong></td><td>0.6928 ± 0.0039</td><td>0.6920 ± 0.0050</td><td>0.6955 ± 0.0021</td></tr><tr><td>wiki-Talk</td><td>0.9921 ± 0.0002</td><td>0.9919 ± 0.0004</td><td>0.9918 ± 0.0005</td><td>0.9920 ± 0.0003</td><td><u>0.9921 ± 0.0005</u></td></tr><tr><td>cit-Patents</td><td>0.6175 ± 0.0046</td><td>0.6154 ± 0.0030</td><td>0.6139 ± 0.0108</td><td>0.6170 ± 0.0105</td><td>0.6128 ± 0.0066</td></tr><tr><td>com-lj</td><td>0.7129 ± 0.0033</td><td><strong>0.7175 ± 0.0029</strong></td><td>0.7152 ± 0.0057</td><td>0.7084 ± 0.0085</td><td>0.7133 ± 0.0033</td></tr><tr><td>dblp</td><td>0.7666 ± 0.0053</td><td>0.7642 ± 0.0114</td><td>0.7614 ± 0.0116</td><td><strong>0.7686 ± 0.0054</strong></td><td>0.7641 ± 0.0082</td></tr><tr><td>soc-LiveJournal1</td><td>0.8155 ± 0.0039</td><td>0.8142 ± 0.0047</td><td>0.8168 ± 0.0053</td><td><strong>0.8193 ± 0.0043</strong></td><td>0.8180 ± 0.0062</td></tr><tr><td><strong>AVG</strong></td><td>0.7615 ± 0.0254</td><td><strong>0.7795 ± 0.0161</strong></td><td>0.7685 ± 0.0202</td><td><u>0.7756 ± 0.0113</u></td><td>0.7734 ± 0.0312</td></tr></tbody></table>
<table><caption>Table 8: Ablation: Training Distribution (Kendall Tau ↑)</caption><thead><tr><th>Graph</th><th>SF Only</th><th>HY Only</th><th>SF+HY (Mix)†</th></tr></thead><tbody><tr><td><strong>Road Networks</strong></td><td></td><td></td><td></td></tr><tr><td>road-luxembourg-osm</td><td>0.4337 ± 0.1910</td><td><u>0.5232 ± 0.0768</u></td><td><u>0.5552 ± 0.0982</u>†</td></tr><tr><td>road-roadNet-PA</td><td><u>0.7902 ± 0.0381</u></td><td><u>0.7800 ± 0.0241</u></td><td>0.7564 ± 0.0266†</td></tr><tr><td>road-belgium-osm</td><td>0.5037 ± 0.1789</td><td><u>0.5875 ± 0.0724</u></td><td><u>0.6107 ± 0.0823</u>†</td></tr><tr><td>road-roadNet-CA</td><td><u>0.7742 ± 0.0420</u></td><td><u>0.7642 ± 0.0255</u></td><td>0.7399 ± 0.0278†</td></tr><tr><td>road-netherlands-osm</td><td>0.6707 ± 0.1645</td><td><u>0.7877 ± 0.0459</u></td><td><u>0.7765 ± 0.0690</u>†</td></tr><tr><td><strong>Social and Web Networks</strong></td><td></td><td></td><td></td></tr><tr><td>p2p-Gnutella31</td><td><u>0.9391 ± 0.0026</u></td><td>0.9044 ± 0.0048</td><td><u>0.9073 ± 0.0043</u>†</td></tr><tr><td>soc-Epinions1</td><td>0.8832 ± 0.0029</td><td><u>0.9133 ± 0.0042</u></td><td><u>0.9095 ± 0.0018</u>†</td></tr><tr><td>soc-Slashdot0902</td><td>0.8350 ± 0.0055</td><td><u>0.8714 ± 0.0094</u></td><td><u>0.8680 ± 0.0032</u>†</td></tr><tr><td>email-EuAll</td><td><u>0.9907 ± 0.0002</u></td><td>0.9902 ± 0.0007</td><td><u>0.9904 ± 0.0011</u>†</td></tr><tr><td>web-Google</td><td>0.7791 ± 0.0017</td><td><u>0.7908 ± 0.0028</u></td><td><u>0.7890 ± 0.0029</u>†</td></tr><tr><td>com-youtube</td><td>0.7719 ± 0.0006</td><td><u>0.7748 ± 0.0026</u></td><td><u>0.7764 ± 0.0013</u>†</td></tr><tr><td>soc-Pokec</td><td>0.7725 ± 0.0042</td><td><u>0.8088 ± 0.0065</u></td><td><u>0.8066 ± 0.0031</u>†</td></tr><tr><td>wiki-topcats</td><td><u>0.6134 ± 0.0048</u></td><td>0.5994 ± 0.0137</td><td><u>0.6051 ± 0.0112</u>†</td></tr><tr><td>amazon</td><td><u>0.6994 ± 0.0026</u></td><td>0.6939 ± 0.0029</td><td><u>0.6970 ± 0.0049</u>†</td></tr><tr><td>wiki-Talk</td><td>0.9911 ± 0.0003</td><td><u>0.9919 ± 0.0005</u></td><td><u>0.9922 ± 0.0007</u>†</td></tr><tr><td>cit-Patents</td><td>0.6012 ± 0.0068</td><td><u>0.6263 ± 0.0085</u></td><td><u>0.6317 ± 0.0072</u>†</td></tr><tr><td>com-lj</td><td>0.7101 ± 0.0027</td><td><u>0.7158 ± 0.0026</u></td><td><u>0.7172 ± 0.0033</u>†</td></tr><tr><td>dblp</td><td><u>0.7736 ± 0.0070</u></td><td>0.7625 ± 0.0086</td><td><u>0.7690 ± 0.0112</u>†</td></tr><tr><td>soc-LiveJournal1</td><td>0.7656 ± 0.0055</td><td><u>0.8092 ± 0.0054</u></td><td><u>0.8017 ± 0.0026</u>†</td></tr><tr><td><strong>AVG</strong></td><td>0.7525 ± 0.0348</td><td><u>0.7734 ± 0.0167</u></td><td><u>0.7737 ± 0.0191</u>†</td></tr></tbody></table>
<table><caption>Table 9: Ablation: Hidden Dimension (Kendall Tau ↑)</caption><thead><tr><th>Graph</th><th>Hidden 8</th><th>Hidden 12<sup>†</sup></th><th>Hidden 16</th><th>Hidden 24</th><th>Hidden 32</th><th>Hidden 64</th><th>Hidden 128</th></tr></thead><tbody><tr><td colspan="8"><strong>Road Networks</strong></td></tr><tr><td>road-luxembourg-osm</td><td>0.5621 ± 0.0672</td><td>0.6271 ± 0.0375<sup>†</sup></td><td>0.6058 ± 0.0462</td><td>0.6139 ± 0.0429</td><td>0.6297 ± 0.0150</td><td><u>0.6596 ± 0.0106</u></td><td><u>0.6633 ± 0.0114</u></td></tr><tr><td>road-roadNet-PA</td><td>0.7131 ± 0.0723</td><td><u>0.8045 ± 0.0309<sup>†</sup></u></td><td>0.7864 ± 0.0426</td><td>0.7997 ± 0.0217</td><td><u>0.8057 ± 0.0083</u></td><td>0.7854 ± 0.0092</td><td>0.7938 ± 0.0195</td></tr><tr><td>road-belgium-osm</td><td>0.6067 ± 0.0720</td><td>0.6810 ± 0.0382<sup>†</sup></td><td>0.6658 ± 0.0476</td><td>0.6824 ± 0.0209</td><td>0.6912 ± 0.0082</td><td><u>0.7078 ± 0.0084</u></td><td><u>0.7172 ± 0.0102</u></td></tr><tr><td>road-roadNet-CA</td><td>0.7031 ± 0.0703</td><td><u>0.7907 ± 0.0311<sup>†</sup></u></td><td>0.7721 ± 0.0439</td><td>0.7849 ± 0.0218</td><td><u>0.7909 ± 0.0092</u></td><td>0.7688 ± 0.0100</td><td>0.7784 ± 0.0199</td></tr><tr><td>road-netherlands-osm</td><td>0.7198 ± 0.0893</td><td>0.8290 ± 0.0359<sup>†</sup></td><td>0.8090 ± 0.0642</td><td>0.8463 ± 0.0113</td><td><u>0.8523 ± 0.0063</u></td><td>0.8492 ± 0.0129</td><td><u>0.8538 ± 0.0202</u></td></tr><tr><td colspan="8"><strong>Social and Web Networks</strong></td></tr><tr><td>p2p-Gnutella31</td><td>0.9067 ± 0.0054</td><td>0.9049 ± 0.0032<sup>†</sup></td><td><u>0.9098 ± 0.0028</u></td><td>0.9051 ± 0.0046</td><td><u>0.9096 ± 0.0037</u></td><td>0.9022 ± 0.0044</td><td>0.9026 ± 0.0053</td></tr><tr><td>soc-Epinions1</td><td><u>0.9118 ± 0.0044</u></td><td>0.9095 ± 0.0027<sup>†</sup></td><td>0.9086 ± 0.0026</td><td>0.9049 ± 0.0012</td><td>0.9065 ± 0.0019</td><td>0.9101 ± 0.0035</td><td><u>0.9137 ± 0.0045</u></td></tr><tr><td>soc-Slashdot0902</td><td><u>0.8710 ± 0.0047</u></td><td>0.8677 ± 0.0062<sup>†</sup></td><td>0.8668 ± 0.0054</td><td>0.8591 ± 0.0065</td><td>0.8633 ± 0.0038</td><td>0.8656 ± 0.0014</td><td><u>0.8695 ± 0.0064</u></td></tr><tr><td>email-EuAll</td><td><u>0.9903 ± 0.0003</u></td><td><u>0.9896 ± 0.0006<sup>†</sup></u></td><td>0.9896 ± 0.0012</td><td>0.9889 ± 0.0008</td><td>0.9887 ± 0.0013</td><td>0.9885 ± 0.0003</td><td>0.9880 ± 0.0007</td></tr><tr><td>web-Google</td><td>0.7872 ± 0.0030</td><td>0.7927 ± 0.0027<sup>†</sup></td><td>0.7886 ± 0.0045</td><td>0.7913 ± 0.0028</td><td>0.7906 ± 0.0037</td><td><u>0.7936 ± 0.0011</u></td><td><u>0.7981 ± 0.0025</u></td></tr><tr><td>com-youtube</td><td><u>0.7778 ± 0.0017</u></td><td><u>0.7765 ± 0.0026<sup>†</sup></u></td><td>0.7744 ± 0.0016</td><td>0.7719 ± 0.0025</td><td>0.7723 ± 0.0014</td><td>0.7705 ± 0.0025</td><td>0.7718 ± 0.0027</td></tr><tr><td>soc-Pokec</td><td>0.8001 ± 0.0048</td><td>0.8053 ± 0.0044<sup>†</sup></td><td>0.8009 ± 0.0072</td><td><u>0.8118 ± 0.0018</u></td><td>0.8088 ± 0.0042</td><td>0.8103 ± 0.0044</td><td><u>0.8186 ± 0.0081</u></td></tr><tr><td>wiki-topcats</td><td>0.6093 ± 0.0084</td><td><u>0.6166 ± 0.0052<sup>†</sup></u></td><td>0.6138 ± 0.0142</td><td>0.6031 ± 0.0117</td><td>0.6063 ± 0.0025</td><td>0.6024 ± 0.0056</td><td><u>0.6144 ± 0.0157</u></td></tr><tr><td>amazon</td><td><u>0.7062 ± 0.0033</u></td><td><u>0.6985 ± 0.0054<sup>†</sup></u></td><td>0.6970 ± 0.0047</td><td>0.6850 ± 0.0041</td><td>0.6862 ± 0.0052</td><td>0.6808 ± 0.0039</td><td>0.6824 ± 0.0090</td></tr><tr><td>wiki-Talk</td><td><u>0.9921 ± 0.0004</u></td><td>0.9913 ± 0.0005<sup>†</sup></td><td><u>0.9916 ± 0.0008</u></td><td>0.9906 ± 0.0007</td><td>0.9910 ± 0.0006</td><td>0.9904 ± 0.0003</td><td>0.9905 ± 0.0008</td></tr><tr><td>cit-Patents</td><td><u>0.6374 ± 0.0105</u></td><td><u>0.6308 ± 0.0055<sup>†</sup></u></td><td>0.6182 ± 0.0056</td><td>0.5975 ± 0.0142</td><td>0.5985 ± 0.0056</td><td>0.5926 ± 0.0100</td><td>0.5981 ± 0.0148</td></tr><tr><td>com-lj</td><td><u>0.7177 ± 0.0052</u></td><td><u>0.7190 ± 0.0022<sup>†</sup></u></td><td>0.7159 ± 0.0028</td><td>0.7110 ± 0.0034</td><td>0.7117 ± 0.0022</td><td>0.7085 ± 0.0027</td><td>0.7105 ± 0.0045</td></tr><tr><td>dblp</td><td><u>0.7751 ± 0.0096</u></td><td><u>0.7683 ± 0.0080<sup>†</sup></u></td><td>0.7650 ± 0.0097</td><td>0.7369 ± 0.0111</td><td>0.7440 ± 0.0079</td><td>0.7318 ± 0.0083</td><td>0.7337 ± 0.0172</td></tr><tr><td>soc-LiveJournal1</td><td>0.8006 ± 0.0073</td><td>0.8043 ± 0.0047<sup>†</sup></td><td>0.7997 ± 0.0074</td><td>0.8035 ± 0.0036</td><td>0.8052 ± 0.0071</td><td><u>0.8122 ± 0.0069</u></td><td><u>0.8184 ± 0.0063</u></td></tr><tr><td><strong>AVG</strong></td><td>0.7678 ± 0.0232</td><td><u>0.7899 ± 0.0120<sup>†</sup></u></td><td>0.7831 ± 0.0166</td><td>0.7836 ± 0.0099</td><td>0.7870 ± 0.0052</td><td>0.7858 ± 0.0056</td><td><u>0.7904 ± 0.0095</u></td></tr></tbody></table>
<table><caption>Table 10: Ablation: Dropout (Kendall Tau ↑)</caption><thead><tr><th>Graph</th><th>Drop 0.1</th><th>Drop 0.2</th><th>Drop 0.3<sup>†</sup></th><th>Drop 0.4</th><th>Drop 0.5</th><th>Drop 0.6</th><th>Drop 0.7</th></tr></thead><tbody><tr><td colspan="8"><strong>Road Networks</strong></td></tr><tr><td>road-luxembourg-osm</td><td><strong>0.6544 ± 0.0168</strong></td><td>0.6443 ± 0.0473</td><td><u>0.6518 ± 0.0354<sup>†</sup></u></td><td>0.6369 ± 0.0296</td><td>0.6153 ± 0.0366</td><td>0.6271 ± 0.0375</td><td>0.5814 ± 0.0526</td></tr><tr><td>road-roadNet-PA</td><td>0.8160 ± 0.0078</td><td>0.8117 ± 0.0136</td><td><u>0.8162 ± 0.0081<sup>†</sup></u></td><td><strong>0.8171 ± 0.0043</strong></td><td>0.7983 ± 0.0146</td><td>0.8045 ± 0.0309</td><td>0.7515 ± 0.0372</td></tr><tr><td>road-belgium-osm</td><td><u>0.7116 ± 0.0116</u></td><td>0.7017 ± 0.0348</td><td><strong>0.7127 ± 0.0215<sup>†</sup></strong></td><td>0.6984 ± 0.0221</td><td>0.6851 ± 0.0225</td><td>0.6810 ± 0.0382</td><td>0.6271 ± 0.0590</td></tr><tr><td>road-roadNet-CA</td><td>0.8010 ± 0.0083</td><td>0.7958 ± 0.0147</td><td><u>0.8024 ± 0.0090<sup>†</sup></u></td><td><strong>0.8026 ± 0.0041</strong></td><td>0.7860 ± 0.0144</td><td>0.7907 ± 0.0311</td><td>0.7359 ± 0.0399</td></tr><tr><td>road-netherlands-osm</td><td><u>0.8630 ± 0.0040</u></td><td>0.8578 ± 0.0174</td><td><strong>0.8645 ± 0.0074<sup>†</sup></strong></td><td>0.8569 ± 0.0055</td><td>0.8451 ± 0.0049</td><td>0.8290 ± 0.0359</td><td>0.7294 ± 0.0775</td></tr><tr><td colspan="8"><strong>Social and Web Networks</strong></td></tr><tr><td>p2p-Gnutella31</td><td>0.8978 ± 0.0063</td><td><u>0.9052 ± 0.0047</u></td><td>0.9029 ± 0.0037<sup>†</sup></td><td>0.9031 ± 0.0046</td><td><strong>0.9092 ± 0.0040</strong></td><td>0.9049 ± 0.0032</td><td>0.9041 ± 0.0024</td></tr><tr><td>soc-Epinions1</td><td>0.9069 ± 0.0017</td><td>0.9046 ± 0.0023</td><td>0.8685 ± 0.0922<sup>†</sup></td><td>0.9066 ± 0.0025</td><td>0.9065 ± 0.0035</td><td><u>0.9095 ± 0.0027</u></td><td><strong>0.9114 ± 0.0022</strong></td></tr><tr><td>soc-Slashdot0902</td><td>0.8584 ± 0.0022</td><td>0.8568 ± 0.0050</td><td>0.8485 ± 0.0251<sup>†</sup></td><td>0.8550 ± 0.0042</td><td>0.8626 ± 0.0097</td><td><u>0.8677 ± 0.0062</u></td><td><strong>0.8728 ± 0.0043</strong></td></tr><tr><td>email-EuAll</td><td>0.9889 ± 0.0013</td><td>0.9887 ± 0.0010</td><td>0.9887 ± 0.0011<sup>†</sup></td><td>0.9887 ± 0.0015</td><td><u>0.9897 ± 0.0011</u></td><td>0.9896 ± 0.0006</td><td><strong>0.9905 ± 0.0002</strong></td></tr><tr><td>web-Google</td><td><strong>0.7980 ± 0.0045</strong></td><td><u>0.7961 ± 0.0029</u></td><td>0.7775 ± 0.0412<sup>†</sup></td><td>0.7934 ± 0.0036</td><td>0.7893 ± 0.0008</td><td>0.7927 ± 0.0027</td><td>0.7873 ± 0.0020</td></tr><tr><td>com-youtube</td><td>0.7691 ± 0.0018</td><td>0.7695 ± 0.0018</td><td>0.7724 ± 0.0010<sup>†</sup></td><td>0.7728 ± 0.0025</td><td>0.7749 ± 0.0022</td><td><u>0.7765 ± 0.0026</u></td><td><strong>0.7770 ± 0.0014</strong></td></tr><tr><td>soc-Pokec</td><td><strong>0.8129 ± 0.0056</strong></td><td>0.8113 ± 0.0049</td><td><u>0.8118 ± 0.0051<sup>†</sup></u></td><td>0.8116 ± 0.0053</td><td>0.8053 ± 0.0051</td><td>0.8053 ± 0.0044</td><td>0.8026 ± 0.0075</td></tr><tr><td>wiki-topcats</td><td>0.5933 ± 0.0101</td><td>0.5930 ± 0.0130</td><td>0.6045 ± 0.0058<sup>†</sup></td><td>0.6018 ± 0.0077</td><td>0.6113 ± 0.0093</td><td><strong>0.6166 ± 0.0052</strong></td><td><u>0.6131 ± 0.0074</u></td></tr><tr><td>amazon</td><td>0.6746 ± 0.0030</td><td>0.6773 ± 0.0032</td><td>0.6840 ± 0.0036<sup>†</sup></td><td>0.6856 ± 0.0060</td><td>0.6940 ± 0.0052</td><td><u>0.6985 ± 0.0054</u></td><td><strong>0.7068 ± 0.0036</strong></td></tr><tr><td>wiki-Talk</td><td>0.9901 ± 0.0004</td><td>0.9901 ± 0.0007</td><td>0.9905 ± 0.0007<sup>†</sup></td><td>0.9907 ± 0.0008</td><td><u>0.9914 ± 0.0007</u></td><td>0.9913 ± 0.0005</td><td><strong>0.9924 ± 0.0004</strong></td></tr><tr><td>cit-Patents</td><td>0.5998 ± 0.0052</td><td>0.6004 ± 0.0044</td><td>0.6023 ± 0.0026<sup>†</sup></td><td>0.6070 ± 0.0067</td><td>0.6170 ± 0.0097</td><td><u>0.6308 ± 0.0055</u></td><td><strong>0.6423 ± 0.0056</strong></td></tr><tr><td>com-lj</td><td>0.7106 ± 0.0022</td><td>0.7106 ± 0.0017</td><td>0.7114 ± 0.0020<sup>†</sup></td><td>0.7142 ± 0.0009</td><td>0.7148 ± 0.0027</td><td><strong>0.7190 ± 0.0022</strong></td><td><u>0.7189 ± 0.0037</u></td></tr><tr><td>dblp</td><td>0.7216 ± 0.0046</td><td>0.7243 ± 0.0047</td><td>0.7340 ± 0.0076<sup>†</sup></td><td>0.7392 ± 0.0097</td><td>0.7571 ± 0.0113</td><td><u>0.7683 ± 0.0080</u></td><td><strong>0.7839 ± 0.0069</strong></td></tr><tr><td>soc-LiveJournal1</td><td><strong>0.8126 ± 0.0067</strong></td><td><u>0.8093 ± 0.0042</u></td><td>0.8084 ± 0.0026<sup>†</sup></td><td>0.8074 ± 0.0076</td><td>0.8013 ± 0.0053</td><td>0.8043 ± 0.0047</td><td>0.8003 ± 0.0055</td></tr><tr><td><strong>AVG</strong></td><td>0.7885 ± 0.0055</td><td>0.7868 ± 0.0096</td><td>0.7870 ± 0.0145<sup>†</sup></td><td><u>0.7889 ± 0.0068</u></td><td>0.7871 ± 0.0086</td><td><strong>0.7899 ± 0.0120</strong></td><td>0.7752 ± 0.0168</td></tr></tbody></table>
<table><caption>Table 11: Test set.</caption><thead><tr><th>Graph</th><th>#Nodes</th><th>#Edges</th></tr></thead><tbody><tr><td colspan="3"><strong>Road Networks</strong></td></tr><tr><td>road-luxembourg-osm</td><td>114,599</td><td>119,666</td></tr><tr><td>road-roadNet-PA</td><td>1,087,562</td><td>1,541,514</td></tr><tr><td>road-belgium-osm</td><td>1,441,295</td><td>1,549,970</td></tr><tr><td>road-roadNet-CA</td><td>1,957,027</td><td>2,760,388</td></tr><tr><td>road-netherlands-osm</td><td>2,216,688</td><td>2,441,238</td></tr><tr><td colspan="3"><strong>Social and Web Networks</strong></td></tr><tr><td>p2p-Gnutella31</td><td>62,586</td><td>147,892</td></tr><tr><td>soc-Epinions1</td><td>75,879</td><td>508,837</td></tr><tr><td>soc-Slashdot0902</td><td>82,168</td><td>948,464</td></tr><tr><td>email-EuAll</td><td>265,214</td><td>420,045</td></tr><tr><td>web-Google</td><td>875,713</td><td>5,105,039</td></tr><tr><td>com-youtube</td><td>1,134,890</td><td>2,987,624</td></tr><tr><td>soc-Pokec</td><td>1,632,803</td><td>30,622,564</td></tr><tr><td>wiki-topcats</td><td>1,791,489</td><td>28,511,807</td></tr><tr><td>amazon</td><td>2,146,057</td><td>5,743,146</td></tr><tr><td>wiki-Talk</td><td>2,394,385</td><td>5,021,410</td></tr><tr><td>cit-Patents</td><td>3,764,117</td><td>16,511,741</td></tr><tr><td>com-lj</td><td>3,997,962</td><td>34,681,189</td></tr><tr><td>dblp</td><td>4,000,148</td><td>8,649,011</td></tr><tr><td>soc-LiveJournal1</td><td>4,847,571</td><td>68,993,773</td></tr></tbody></table>