# BCDR: BETWEENNESS CENTRALITY-BASED DIS## TANCE RESAMPLING FOR GRAPH SHORTEST DIS- TANCE EMBEDDING

**Anonymous authors**
Paper under double-blind review

ABSTRACT

Along with unprecedented development in network analysis such as biomedical
structure prediction and social relationship analysis, Shortest Distance Queries
(SDQs) in graphs receive an increasing attention. Approximate algorithms of
SDQs with reduced complexity are of vital importance to complex graph applications. Among different approaches, embedding-based distance prediction has
made a breakthrough in both efficiency and accuracy, ascribing to the significant
performance of Graph Representation Learning (GRL). Embedding-based distance prediction usually leverages truncated random walk followed by Pointwise
Mutual Information (PMI)-based optimization to embed local structural features
into a dense vector on each node and integrates with a subsequent predictor for
global extraction of nodes’ mutual shortest distance. It has several shortcomings.
Random walk as an unstrained node sequence possesses a limited distance exploration, failing to take into account remote nodes under graph’s shortest distance
metric, while the PMI-based maximum likelihood optimization of node embeddings reflects excessively versatile local similarity, which incurs an adverse impact on the preservation of the exact shortest distance relation during the mapping
from the original graph space to the embedded vector space.
To address these shortcomings, we propose in this paper a novel graph shortest
distance embedding method called Betweenness Centrality-based Distance Resampling (BCDR). First, we prove in a statistical perspective that Betweenness
Centrality(BC)-based random walk can occupy a wider distance range measured
by the intrinsic metric in the graph domain due to its awareness of the path structure. Second, we perform Distance Resampling (DR) from original walk paths before maximum likelihood optimization instead of the PMI-based optimization and
prove that this strategy preserves distance relation with respect to any calibrated
node via steering optimization objective to reconstruct a global distance matrix.
Our proposed method possesses a strong theoretical background and shows much
better performance than existing methods when evaluated on a broad class of realworld graph datasets with large diameters in SDQ problems.

1 INTRODUCTION

Shortest Distance Queries (SDQs) in graphs focus on determining the minimum distance between
arbitrary node pairs, defined as sum of related edge weights. Despite the fact that Shortest Path
Queries (SPQs) (Wei, 2012; Sommer, 2014; Wang et al., 2021) are already renowned in graph structure exploration, SDQs play an essential role in increasing applications, such as social relationship
analysis (Carlton, 2020; Melkonian et al., 2021; Chen et al., 2021; Zaki et al., 2021; Parveen &
Varma, 2021), biomedical structure prediction (Yue et al., 2019; Galoviˇcov´a et al., 2021; Sokolowski
& Wasserman, 2021), learning theory (Yang et al., 2021; Yuan et al., 2021), optimization (Melkonian
et al., 2021; Rahmad Syah et al., 2021; Jiang et al., 2021), etc. The key challenge in the SDQ problem is the prohibitive complexity in very large graphs. e.g., for an undirected dense graph with N
nodes and k queries, the time complexity of A*(Hart et al., 1968) and Dijkstra Algorithm(Thorup &
Zwick, 2004) are up to O(kN [2]) and O(kN log N ) for unweighted and weighted graph, respectively.


-----

Table 1: Overall comparison of approaches to shortest distance query.

Accuracy loss of approximate methods are evaluated on facebook(A.7.2) by mRE(2). N -number of
nodes, T -walk length, K-window size, l-number of landmarks, d-dimension of embedding space,
_α, β, c-constant independent of N_ .

Objective Method Model Off-Line Time Space Time Accuracy Loss

Exact Compress -  _O(N_ [3]) _O(N_ [2]) _O(kN_ ) 0
Exact Index -  _O(N_ [2] log N ) _O(N_ [2]) _O(kN log N_ ) 0
Approximate OracleExact Cache -- _O−(αN_ [1+][ 1]α ) _OO((αNN_ ) [1+][ 1]α ) OO((kαN )) ∼ _O(N_ [2]) 02(α − 1)

Approximate Landmark - _O(lN log N + lN_ ) _O(lN_ ) _O(kl)_ 0.523
Approximate Embedding Orion _O(αN log N + cN_ ) _O(dN_ ) _O(kd)_ 0.688
Rigel _O(αN log N + cN_ ) _O(dN_ ) _O(kd)_ 0.369
DeepWalk _O(TKN log N + (T + c)N_ ) _O(dN_ ) _O(kd)_ 0.329
Node2Vec _O(TKN log N + (T + c)N_ ) _O(dN_ ) _O(kd)_ 0.299
DADL _O(TKN log N + (T + c)N_ ) _O(dN_ ) _O(kd)_ 0.228
BCDR(ours.) O(αTKN log N + (βT + c)N ) O(dN ) _O(kd)_ **0.177**


(a) (b) (c) (d)

Figure 1: Distance confusion of a conventional model in embedding. (a) random walks rooted at
_va have much difficulty in exploring beyond current community to vc. (b): Weight decay on walks_
causes instability of shortest distance since walks rooted at va have large probability to steer clear
of vb for starters and back to vb as the end, which results in a extremely weak correlation between
_va and vb despite the fact that they have an immediate edge. (c): A sufficient number of 2-hop links_
between vc and va induce a shorter distance in embedding space than that of vb and va. (d): vb
and vc sharing substantial connection deserve to be mapped closed to each other even if they have a
large shortest distance gap, while the divergence of distance between vb, vc and va is also plagued
with extraction.

To address this issue, a surging number of approximate algorithms in a wide range of fields have been
proposed in the past a few years. They can be categorized into oracle-based (Thorup & Zwick, 2004;
Baswana & Kavitha, 2006), landmark-based (Sarma et al., 2010; Gubichev et al., 2010), embeddingbased distance prediction methods (Xiaohan et al., 2010; 2011; Rizi et al., 2018). Among these
categories, embedding-based methods are of high accuracy with significantly reduced complexity
(see Table1), owing much to rapid advances of representation learning in graphs (Perozzi et al.,
2014; Grover & Leskovec, 2016). Embedding-based methods tackle the SDQ problem with two
stages. First, they embed local structural features into a dense vector on each node, which preserves
the essential information for indicating where the node is. Then, for arbitrary node pairs in the
training set, subsequent predictor extracts mutual shortest distance globally via their embedding
tuples and minimizes the mean of square loss between a predicted value and the real one. As
predictors serve as a non-linear metric in the embedding space, the performance of embeddingbased models depends highly on the first stage. These methods usually embed graph structures by
leveraging truncated random walk to serialize node’s neighborhood in a statistical perspective and
maximize co-occurrence likelihood of nodes in one walk path to reflect their correlation, which is
also proved to implicitly factorize a Pointwise Mutual Information (PMI) matrix (Levy & Goldberg,
2014; Shaosheng et al., 2015).

Although existing embedding-based methods have achieved a great success, they have several shortcomings. On one side, random walk is an unstrained node sequence from the root, possessing a
limited distance exploration. This is because each transition on nodes is not implied for a specific
direction to move towards or beyond the root, especially after several walk steps, which is backbreaking to accommodate correlation with remote nodes under graph’s shortest distance metric (see
Figure 1a). On the other side, the PMI-based optimization reflects excessively versatile local sim

-----

ilarity, which is not guaranteed for shortest distance-preserved mapping from the original graph
space to the embedded vector space. As a matter of fact, it exerts a too-general metric over nodes’
correlation, wherein the more links or paths exist between two nodes, the stronger correlation they
share. That means we have many ways to claim a shorter distance for two nodes (e.g., by adding
mutual edges, deleting links to other nodes) even if some of the operations do not change their actual
shortest path distance (see Figures 1c and 1d).

In this paper, we address the above shortcomings by proposing a novel graph shortest distance embedding method called Betweenness Centrality-based Distance Resampling (BCDR). Here, random
walk paths are simulated by considering nodes’ betweenness centrality on each transition for covering a wider distance range of nodes. Then, a sampling process of nodes based on their mutual
shortest distances is performed before optimization of co-occurrence likelihood to preserve pairwise distance relation during the mapping from graph to the embedding space.

We summarize our major contributions as follows.

_• We propose a Betweenness Centrality (BC)-based random walk for accommodating_
**correlation with nodes of wider distance range under the intrinsic graph metric (see**
Section 3.1). To the best of our knowledge, there is no existing method that combines
betweenness centrality and random walk for the graph representation. We prove in a statistical perspective that the transition driven by nodes’ BC value tends to explore high order
proximity of the root due to the awareness of local path structure.

_• We propose a Distance Resampling (DR) strategy to preserve nodes‘ mutual shortest dis-_
**tance during the mapping from graph to the embedding space (see Section 3.2). We prove**
that by sampling node sequences from original walk paths before maximum likelihood optimization instead of PMI-based optimization, the objective can be steered to reconstruct a
global distance matrix, and for any calibrated node, it strictly preserves the shortest distance
relation to other nodes on the graph.

_• We evaluate BCDR and compare it with existing embedding-based methods with a broad_
class of real-world graph datasets with divergent diameters. BCDR shows a much bet**ter empirical performance in solving the SDQ problem than existing embedding-based**
methods (see Section 4).

2 NOTATION & PROBLEM DEFINITION

2.1 NOTATION

_G = (V, E) denotes an undirected graph, with V = {v1, v2, ..., v|V |} being the set of nodes and E_
being the set of edges. An edge eij = (vi, vj) represents an undirected edge between nodes vi and
_vj. A node vi’s neighborhood Ni is a set of nodes with an edge with vi, i.e., Ni = {vj|(vi, vj) ∈_
_E_ . We use Z _V_ _d to represent an embedding matrix, where d is the embedding size. For any_
_}_ _|_ _|×_
matrix B, the symbol Bi represents the i-th row of B, and Bij represents the element at i-th row
and j-th column. A truncated random walk Wi rooted at node vi of length l is a random vector
of ⟨Wi[1][,][ W]i[2][,][ · · ·][,][ W]i[l][⟩][, where][ W]i[k] [is a node chosen from the neighborhood of node][ W]i[k][−][1] for
_k = 1, ..., l, with Wi[0]_ [:=][ v][i][.][ P][i][ is a finite set of walk paths sampled from][ W][i][, and][ W][i][ is the multiset]
of nodes on the walk paths in Pi.

2.2 PROBLEM DEFINITION

An arbitrary path p of length l ∈ N on graph G is an ordered sequence of nodes (v1, v2, ...vl+1),
where each node except the last one has an edge with the subsequent node, i.e., (vi, vi+1) _E for_
_∈_
1 ≤ _i ≤_ _l. The shortest path ˚pij is one of the paths with the minimum length_ [˚]l between two nodes
_vi and vj, with the shortest distance Dij defined as the length of ˚pij. The global distance matrix D_
comprises _Dij_ .
_{_ _}_

An embedding-based model learns two mappings F and G for structure embedding and mutual
distance extraction, respectively, as follows.

_F : G →_ R[d], _G : ⟨R[d], R[d]⟩→_ R (1)


-----

A shortest distance query Q can be simply defined as a set of node pairs, i.e., Q =
_{(v11, v12), (v21, v22), ..., (v|Q|,1, v|Q|,2)}. For each node pair (vi, vj), the model intends to find_
out approximation _D[ˆ]_ _ij = G(F(vi), F(vj)) nearest to real Dij. The commonly used metrics of ap-_
proximation quality are mean of Relative Error (mRE) and mean of Absolute Error (mAE). mRE is
defined as the relative loss of the prediction value with respect to the real value, while mAE measures
the absolute gap between the prediction value and the real value, i.e.,


_D[ˆ]_ _ij_ _Dij_
_|_ _−_ _|_ _,_ mAE :=

_Dij_


_D[ˆ]_ _ij_ _Dij_
(vi,vXj )∈Q _|_ _−_ _|_ (2)


mRE :=

METHOD


_|Q|_


_|Q|_


(vi,vj )∈Q


Random walk as a serialization strategy of similarity measurement has been widely used in
many graph representation and learning methods, aiming to model long-range dependency of
nodes (Grover & Leskovec, 2016; Zhuang & Ma, 2018). The optimization of maximizing cooccurrence likelihood of nodes on walk paths also yields an impressive performance in networkstructure extraction via approximating PMI matrix (Levy & Goldberg, 2014). But in terms of the
shortest distance representation of a graph, we contend that this intuitive approach has several limitations on the performance. Consider a walk path p = (va, va1 _, va2_ _, · · ·, val_ ) ∈ _Pa sampled from_
a general random walk Wa from root node va. As an unstrained sequence of nodes, the distance
measured along the walk path p is not consistent with that on the graph (see Figure 1b), i.e., for
_vai_ _, vaj_ _p,_
_∈_ _i ≤_ _j ⇎_ _Daai ≤_ _Daaj_ (3)
where i and j are indexes of node vai and vaj on p and 1 ≤ _i, j ≤_ _l._

Using the aforementioned unstrained walk paths for maximizing co-occurrence likelihood incurs
two problems.

1. Problem 1: Limited exploration range of walks. Each transition on walks only considers
a local structure of the current node, causing agnostic tendency to move towards or beyond
the root node under the graph’s shortest-distance metric after a few steps (see Figure 1a).

2. Problem 2: Intractability of shortest distance on paths. Distance measured on walk
paths may not actually reflect the graph’s shortest distance because of the unbalanced number of links between different nodes (see Figure 1c and 1d).

In this section, we describe in detail our proposed method, which is a decent way of encoding
shortest distances using BC-based random walk plus a distance resampling strategy, and present a
theoretical analysis for its interpretability and efficiency. More specifically, we first present BCbased random walks and distance resampling, and then an algorithm to integrate them. We provide
an intuitive complexity explanation. Additionally, we discuss the connection to Multidimensional
Scaling (MDS) and graph structure decomposition in Appendix A.1 and A.2, respectively.

3.1 BC-BASED RANDOM WALK

**Definition 1. (Betweenness Centrality) Define G = (V, E) as undirected graph. vi, vs, vt are**
_arbitrary nodes in the node set V . σst(vi) represents the number of shortest paths between vs and_
_vt that pass vi, and σst is the total number of shortest paths between vs and vt. Then we say that_
_BC of vi is_

_σst(vi)_

BC(vi) = (4)

_σst_

_sX≠_ _i≠_ _t_

To address Problem 1, we propose a BC-based random walk. As defined in Definition 1, BC(vi)
determines the probability of vi located on shortest paths of arbitrary node pairs. Thus, we consider
a node with large BC value vitally significant to drive the walk to move away from root node, since


-----

it reveals a easy way of traveling to some nodes with minimal cost. And to leverage this property, in
BC-based random walk Wa = ⟨Wa[1][,][ W]a[2][, ...][W]a[j][, ...][⟩] [on node][ v][a][, we prefer choosing nodes with the]
largest BC values among their neighborhoods when simulating walk paths, i.e.,

BC( _a[)]_
_p(Wa[j][|W]a[j][−][1]_ = vj−1) = _vk∈Nj−W1_ [BC(][j] _[v][k][)]_ _[,][ W]a[j]_ _[∈N][j][−][1]_ (5)

where _i is the neighborhood of vi._ P
_N_

The following theorem, proved in Appendix A.3, indicates that a BC-based random walk tends to
transit from _a[(][h][)]_ to _a[(][h][+1)], leading to a deeper exploration measured by the intrinsic graph’s_
_N_ _N_
shortest distance. It also reveals that our method performs better when the number of final nodes
_fh(va) is larger or there are more links between final nodes fh(va) to connective nodes eh(va) at_
any h-order neighborhood of va.

**Theorem 1. Define Na[(][h][)]** = {vj|Daj = h} as a set of nodes that are h-hops away from va and
_Nh(va) =_ _a[(][h][)]_ _as the number of nodes in the set. Let the number of the nodes that have con-_
_|N_ _|_
_nection with nodes in_ _a[(][h][+1)]_ _(called connective nodes) be eh(va) and the number of other nodes_
_N_
_(called final nodes) be fh(va). The BC we use is an approximate value by considering only the_
_shortest path of nodes within a range of k-hops locally. Let pR(Nh(va)_ _Nh+1(va)) repre-_
_→_
_sent the probability to transit from nodes of Nh(va) to Nh+1(va) by a general random walk, and_
_pB(Nh(va)_ _Nh+1(va)) represent that by a BC-based random walk. Let PR(fh(va)_ _eh(va))_
_→_ _→_
_be a transition from fh(va) nodes to eh(va). Then, for any node va in graph G and any h > 1,_
_pB(Nh(va)_ _Nh+1(va))_
_→_ (6)
_pR(Nh(va)_ _Nh+1(va)) [= 1 +][ B][(][k][) +][ C]_
_→_

lim + C > 0
_k→E(va)−1−h_ _[B][(][k][) +][ C][ =][ A][2]A[ −]1_ [1]

(7)

1

_A1 =_ _[e][h][(][v][a][)]_ _A2 =_

_fh(va)_ _[,]_ _pR(fh(va)_ _eh(va))_ _[.]_

_→_

_where C_ 0, and (va) is the eccentricity of va, (va) = maxvb _G Dab._
_≥_ _E_ _E_ _∈_

3.2 DISTANCE RESAMPLING

To address Problem 2, we propose a Distance Resampling (DR) strategy, which is inspired by
Sampling-Importance-Resampling (SIR) method (Smith & Gelfand, 1992). Let vx(v1, v2) be a
random vector of the node tuple. Define p(vx) as the joint distribution reflecting the real shortest
distance of v1, v2 on the graph. We have

max Evx _p[f_ ] = _f_ (v1, v2)p(v1, v2)
_f_ _∼_ (8)

_v1X,v2∈V_

as a probabilistic objective for representing the shortest distance D12, where f is a normalized
learnable density function determined by nodes’ mutual distance in the embedding space. According
to the rearrangement inequality, the above equation arrives at the maximum when f (v1, v2) varies
consistent with p(v1, v2), which means f indicates the shortest distance metric on the graph with
respect to any v1, v2 as p does. Therefore, the critical issue is to extract accurate p(v1, v2) in a graph.
Let q(va) be the joint distribution reflecting distance relation on sampled walks. We try to leverage
_q on walk paths to approximate p. Here, we adopt a simple but effective resampling by considering_
both their mutual distance D12 as well as BC values.

Without loss of generality, let vi represent the root node of walks and vj be the j-th node on a walk
path (i.e., sampled fromvector _W[˚]i = ⟨W[˚]i[1][,][ ˚]Wi[2][, ...,] W[ ˚]Wi[j][). Our objective is thus to sample from][˚]il[⟩]_ [of length] [˚]l. Then, each node vj sampled from[ W][i][ to generate a new random]W[˚]i[j] [can be described]
as a weighted resampling in original walk paths Wi based on Dij and BC(vj), i.e.,

Evj _p(vj_ _vi)[f_ _vi] =_ _f_ (vi, vj)p(vj _vi) =_ _f_ (vi, vj)q(vj _vi)_ _[p][(][v][j][|][v][i][)]_
_∼_ _|_ _|_ _|_ _|_ _q(vj_ _vi)_

_vi,vXj_ _∈V_ _vi,vXj_ _∈V_ _|_ (9)

_α[D][ij]_ BC(vj)
_f_ (vi, vj)q(vj _vi)_

_≈_ _vXi∈V_ _vjX∈Wi_ _|_ _vk∈Wi_ _[α][D][ik]_ [BC(][v][k][)]

P


-----

where α is a hyper-parameter of the weight decay coefficient on paths.

Reminiscent of previous discussions on relating maximizing co-occurrence likelihood with matrix
factorization, we demonstrate the connection between the above intuitive design and graph shortest
distance metric. As we perform distance resampling for walk paths, the objective to learn an optimal
node embedding is therefore interpreted as

arg max Evx _p[f_ (Zi, Zj)]
**Z** _∼_

(10)

= _p(vi)Evj_ _p( ˚i)[[][p][(][v][j][|][v][i][)(log][ σ][(][Z][i][Z]j[T]_ [) +][ λ][E]vk _pN_ (vk _vi)[[log][ σ][(][−][Z][i][Z][T]k_ [)])]]

_∼_ _W_ _∼_ _|_
_vXi∈V_

Thereinto, f (Zi, Zj) = log σ(ZiZ[T]j [)][,][ p][N] [(][v][k][|][v][i][)][ is the distribution of negative sampling. In our]
algorithm, pN can be specified as a weighted random sampling over all occurred nodes in Wi (simulated based on Equation 5) by occurrence frequency, i.e.,

_pN_ (vk _vi) = [#(][v][k][ occurs in][ W][i][)]_ (11)
_|_ #(Wi)

where #(·) is a counting function indicating the number of occurrence times of specified nodes, i.e.,
the cardinality of a sampled set.
**Proposition 1. Define G = (V, E) as an undirected graph.** _Z_ _V_ _d is the embedding matrix_
_|_ _|×_
_of V corresponding to maximizing likelihood objective Evx_ _p[f_ (Zi, Zj)] defined in Equation 10.
_∼_
_pN_ (vb|va) is the negative sampling distribution of vb from Wa simulated by Equation 11. Let the
_weight decay coefficient in distance resampling be α, 0 < α < 1. Then, the inner product of em-_
_bedding matrix corresponds to a global distance matrix, i.e. ZZ_ _[T]_ = D[ˆ] _. For any va and any vb_
_that is n-hops away from va, the distance between them in the embedding space varies linearly with_
_respect to distance n, namely,_
_Dˆ_ _ab = n log α −_ log A (12)
_where A is a constant independent of vb._

Proposition 1 is proved in Appendix A.4.

Proposition 1 indicates that optimization of Equation 10 conforms to reconstruct a global distance
matrix where nodes far away from each other in the graph under shortest distance metric(i.e., large
_Dab) should be mapped with large distance in the embedding space(i.e., large_ _D[ˆ]_ _ab). We can also_
conclude that _D[ˆ]_ _ab varies linearly with respect to the distance n between two nodes, while A is a_
constant independent of vb but related to va, which means when we fix the source (or destination)
node as va, any destination (or source) node vb’s distance with va could be compared with each
other (we call that distance is measurable with respect to calibrated node va).

Consider the preservation of shortest distance relation. Some studies on metric learning (Hermans
et al., 2017; Zeng et al., 2020) have revealed that a tuple of samples (va, vb, vc) being easy to learn
means if vb shares strong correlation with va, the distance between vb and va in the embedding space
should be shorter than that of vc and va. With this property, we have the following theorem, which
indicates that our method is consistent with distance relation under intrinsic graph metric. This will
be used in the prediction task described next.
**Theorem 2. Each symbol here follows the definition in Proposition 1. Let D be a global distance**
_matrix defined on graph G and Dab be graph’s shortest distance between node va and vb. Then for_
_any nodes va, vb, vc_ _G,_
_∈_ (Dab _Dac)(_ _D[ˆ]_ _ab_ _D[ˆ]_ _ac_ ) 0 (13)
_−_ _|_ _| −|_ _|_ _≥_

The proof is presented in Appendix A.5.

3.3 ALGORITHM

Our BCDR algorithm is presented in Algorithm 1. It contains three steps. First, pre-computation of
the BC value (line 21) is required for each node on the graph. Second, for each node vi, we sample
a batch of walk paths Pi guided by the BC value according to Section 3.1 (line 1 to 20). Meanwhile,


-----

Table 2: Statistics of graph datasets and their train & validation & test sets.

|RoBC-ran|nge of BC, mBC-mean of BC, L-landmark nodes, T|-train set, V-validation set, E-test set|
|---|---|---|
|||V | |E| |E|/|V | Diameter RoBC mBC||L| |T | |V| |E||
|Cora Facebook GrQc|2, 708 10, 787 3.9834 21 375.20 2.7174 4, 039 176, 437 21.846 8 1, 306.9 0.89931 5, 242 30, 042 5.7310 17 148.43 2.7219|100 100 × |V | 800 × 30 1, 600 × 10 100 100 × |V | 800 × 50 1, 600 × 20 100 200 × |V | 800 × 70 1, 600 × 30|



distance relation of each node with vi is also recorded for subsequent resampling. Third, for each
node vi, we resample nodes in Wi by their distances with vi and BC values to formulate _P[˚]i (line_
25 to 34), which is optimized by maximizing pair-wise co-occurrence likelihood (line 37). This
embedding algorithm takes O(woutlout[2] _[|][V][ |][ log][ |][V][ |][+(][w][in][l][in]_ [+][w][out][l][out][)][|][V][ |][)][ of time complexity and]
_O((winlin + woutlout)|V |) of space complexity for any sparse graph (detailed analysis is presented_
in Appendix A.6). The above result reveals a feasible way of reducing time complexity by just
taking larger winlin and smaller woutlout in BCDR. This practice is applied in our experiments.

**Algorithm 1: BCDR Embedding Algorithm**
**Input: input graph G = (V, E), embedding size d, input sample size win, output sample size wout, input walk length lin, output walk length lout, distance weight decay α, use**
smoothed normalization τ .

**12 Def BC Walk(for walk k fromG, v 0i, toDi w, winin do, lin, τ** ): **2221 Walk path set pre-compute BC of each node P** _vi as γi ←_ BC(vi).


**for walk k from 0 to win do** **22 Walk path set P**

**whilevisit sign setifelseendN τ cc[k] is Trueinormalizenormalize < l[:=][ {]in S[v][j] doi then[|] :=[v][j] p p[∈N] {cc→→vijj}[c] ← ←, current node[∧]** _[v]softmax(P[j]_ _vm∈[/]_ _S∈Nγji}c[k]_ _[γ]γ[m] vj + 1)[, v]c :=[j][ ∈N] v, vi, lengthj ∈Ni[ k]_ _c[k] ci := 0, real length c[r]i_ [:= 0] **2326252430272829 for vdistance mapDfori ini ← velseif Gj τ ∈BC Walk is True dopγ(jD[′]v[←]ji.keys|v D[softmax(]i then) :=i := ( doG, v α {[D]vii[i], D[γ] : 0[[][v][j][j][ + 1)][]]i}, w· γinj[′]** _, lin, τ_ )

sample nextifelse vnDcD ∈[r]i _ii[= min][[vvDnni] = min] = then v c[{]n[D] from[r]i_ [+ 1][i][[]{[v]D[n] N[]]i[ −][vc[k]n[1][by]][, c], c[ p]i[r][r]i[}][c][+ 1][→][j] _[}]_ **3334353231** **endsample walk pathsappendp(vendxj** _| Pvpi(i)v into, vj|vxij P) := ∈_ _PD αii =[D].keys[i][[] {[v][j]([]]v for·i γ, vj wx1out, vx times.2_ _, · · ·, vxj_ _, · · · )}of length lout by_

**end** **36 end**

_vc_ _vn, Si_ _vn, ci_ _ci + 1, c[r]i_ _i_ [+ 1] **37 maximize Equation 10 by P** .

**end** _←_ _←_ _←_ _[←]_ _[c][r]_ **38 return Z**

**end**


4 EXPERIMENTAL EVALUATION

In this section, we evaluate our model’s performance with several graph datasets and compare it with
conventional embedding-based methods for SDQ tasks.

4.1 DATASETS

We test our model using three real-world graph datasets as well as some simulated datasets. As
this paper focuses on the shortest distance prediction of connected and undirected graphs, we make
a trivial change for some directed graphs by simply eliminating the direction of each edge. For
graphs with multiple connected components, we repeatedly add one edge between two unconnected
components until the whole graph is connected. The graphs we use are of complex inner connections
and divergent diameters. The basic information of these datasets is outlined in Table 2 (columns 2
to 7). The detailed information is presented in Appendix A.7.

We define T, V, and E as datasets for train, validation, and test, respectively. Each of them is
composed of (vi, vj, Dij). As simulations of the above sets in huge graphs have to be of O( _V_ ) or
_|_ _|_
less complexity, in our experiments, we initially select a group S of nodes as sources, and for each
source vi, a destination set with their shortest distances to the source is randomly collected.
Then, _∈S_ _i_ input node pairs are simulated. The detailed setup for each dataset is presented in D
_|S| × |D_ _|_
Table 2 (columns 8 to 11).

4.2 PARAMETER SETUP

We compare our method with conventional graph embedding models based on random walk as well
as matrix factorization (see Appendix A.8). We simulate 40 walks on each node for random walkbased methods, and each walk is truncated at a length of 40. Sliding window size and negative
sampling size are fixed at 20 and 5, respectively, for each dataset. Node2Vec takes hyper-parameter


-----

Table 3: Performance comparison of embedding-based models

|Col1|Cora|Col3|Facebook|Col5|GrQc|Col7|
|---|---|---|---|---|---|---|
||mAE|mRE|mAE|mRE|mAE|mRE|
|LLE GF LE DeepWalk Node2Vec DADL|5.6265 ± 0.0490 5.6249 ± 0.0876 5.6393 ± 0.0782 1.5183 ± 0.0654 1.3072 ± 0.0236 1.1349 ± 0.0180|0.8445 ± 0.0096 0.8440 ± 0.0142 0.8455 ± 0.0132 0.2425 ± 0.0101 0.2115 ± 0.0038 0.1790 ± 0.0031|1.9921 ± 0.0731 1.8743 ± 0.0717 2.0312 ± 0.0625 0.9323 ± 0.0272 0.8541 ± 0.0436 0.6150 ± 0.0325|0.6841 ± 0.0029 0.6383 ± 0.0284 0.6998 ± 0.0248 0.3289 ± 0.0137 0.2993 ± 0.0166 0.2279 ± 0.0135|4.8849 ± 0.1034 4.8562 ± 0.0516 5.0046 ± 0.0242 2.8002 ± 0.1479 1.5156 ± 0.0691 1.3624 ± 0.1366|0.7105 ± 0.0165 0.7125 ± 0.0084 0.7366 ± 0.0044 0.4169 ± 0.0227 0.2278 ± 0.0087 0.2033 ± 0.0183|
|BCDR|0.9768 ± 0.0245|0.1605 ± 0.0043|0.4804 ± 0.0406|0.1770 ± 0.0156|1.0490 ± 0.0634|0.1684 ± 0.0058|



_p = q = 1. Regularization r of GF is set to 1.0. DADL takes the Hadamard operator for embedding_
aggregation. Like previous research (Zhuang & Ma, 2018), linear regression is utilized as a predictor
for general graph embedding models.

For our model, we take the same configuration as previous random walk-based models using input
walk length lin = 40 and input sample size win = 40. In order to keep complexity of parameters
equal to or even less than that of baselines, the multiplication of output length lout and output sample
size wout is fixed at 40, with lout = 10, wout = 160 for Cora and GrQc and lout = 40, wout = 40
for Facebook. Meanwhile, the weight decay coefficient α is set to 0.1 for Cora and GrQc datasets
and 0.98 for Facebook. To avoid dramatically unbalanced values of BC, we also take smoothed
normalization (τ = True) in all datasets except Facebook. Finally, all of the above models use the
Adam optimizer with a learning rate ϵr = 1e − 4 for training, and embedding dimension d is fixed
at 16 for every dataset.

4.3 PERFORMANCE OF PREDICTION ACCURACY

To compare embedding-based methods, we train each model on each dataset up to 500 iterations and
save the results every 10 epochs. The best models are selected by their mAE and mRE scores on
validation set V. Each model is evaluated 5 times independently on each dataset, and their average
performance is recorded. The resulting mAE and mRE are reported in Table 3. Some comparisons
with the latest GRL methods and further discussion are presented in Appendix A.9, and run-time
test compared with general random walk is reported in Appendix A.10. We can see from the table
that our model outperforms previous models significantly for all three datasets.

4.4 RESULT OF EXPLORATION DISTANCE

As stated in Section 3.1, exploration distance under intrinsic graph metric plays an indispensable
role in modeling a wider range of node correlation. Here, we compare our BC-based random walk
with existing renowned walk strategies, including DeepWalk (Perozzi et al., 2014; Zhuang & Ma,
2018), Node2Vec (Grover & Leskovec, 2016), and Random Surfing (Cao et al., 2016). We use
_TG(20, 1, 3, 10) as a test graph of large diameters. We randomly sample 20 root nodes and, for each_
root, simulate 10 walks with length 10 to show how many nodes in different order proximity are
visited. The ideal situation for a batch of walk paths with length l is to cover up to nodes l − _hop_
away from the current root. The results are shown in Figure 2. From the figure, we can see that our
BC-based walk is much more competitive regarding exploration distance. A further illustration of
diverse graph structures is presented in Appendix A.11.

4.5 PRESERVATION OF DISTANCE RELATION

We have also evaluated the property of shortest distance preservation during the mapping from the
original graph space into embedded vector space. First, we test distance variation in the embedding
space when adjusting the shortest distance between nodes on the graph, taking the same configuration of simulation dataset as TG(20, 1, 3, 10). Distance in the embedding space is measured by
inner product ZiZ[T]j [for any node][ v][i][ and][ v][j][. We initially train embedding vectors using walks sim-]
ulated by each model and randomly sample 20 source nodes with 100 destinations for each source.
The results are shown in Figure 3, which indicates that our model has a better tendency to maintain
a linear distance relation for the mapping.


-----

10 10 10 10

8 8 8 8

6 6 6 6

4 4 4 4

Probability of Explored Distance 2 Probability of Explored Distance 2 Probability of Explored Distance 2 Probability of Explored Distance 2

0 0 2 Walk length4 6 8 0 0 2 Walk length4 6 8 0 0 2 Walk length4 6 8 0 0 2 Walk length4 6 8


(a)


(b)


(c)


(d)


Figure 2: Exploration distance of different random walk strategies tested on graph TG(20, 1, 3, 10).
**(a): general random walk in DeepWalk. (b): Node2Vec. (c): Random Surfing. (d): BC-based**
random walk(ours.).


14 14 14 14

12 12 12 12

10 10 10 10

8 8 8 8

6 6 6 6

4 4 4 4

distance measured on the embedding space 2 distance measured on the embedding space 2 distance measured on the embedding space 2 distance measured on the embedding space 2

0 0 shortest distance between nodes on the graph5 10 15 20 0 0 shortest distance between nodes on the graph5 10 15 20 0 0 shortest distance between nodes on the graph5 10 15 20 0 0 shortest distance between nodes on the graph5 10 15 20


(a)


(b)


(c)


(d)


Figure 3: Distance relation during mappings when taking different random walk strategies. (a):
general random walk in DeepWalk. (b): Node2Vec. (c): Random Surfing. (d): BCDR(ours.).

Second, we try to find out how much the probability distance relation is violated in the embedding
space. We randomly take 10000 node triple (va, vb, vc), and record if they violate Equation 13.
The results are shown in Figure 4. The figure confirms that our model is much more satisfactory in
preserving distance relation during mappings.


5025 violatedpreserved 25 violatedpreserved 5025 violatedpreserved 200 violatedpreserved

0 0 0 -20

-25-50-75 -25-50 -25-50 -40-60

-100 -75 -75 -80

value of distance expression -125 value of distance expression -100 value of distance expression -100 value of distance expression -100

-150 -125 -125 -120

0 2000 sampled node triples4000 6000 8000 10000 0 2000 sampled node triples4000 6000 8000 10000 -150 0 2000 sampled node triples4000 6000 8000 10000 0 2000 sampled node triples4000 6000 8000 10000


(a)


(b)


(c)


(d)


Figure 4: Distance preservation in the embedding spaces of different models. (a): general random
walk in DeepWalk. (b): Node2Vec. (c): Random Surfing. (d): BCDR(ours.).

5 CONCLUSION

In this paper, we propose a novel graph shortest distance embedding method called Betweenness
Centrality-based Distance Resampling (BCDR). It improves the graph embedding for the shortest
distance representation with two components we propose in this paper. The first is Betweenness
Centrality-based random walk to accommodate long-distance correlation on graphs by covering a
wider range of nodes under the intrinsic graph metric. The second is a distance resampling strategy
to preserve shortest distances during the mapping from graph to the embedding space via reconstructing a global distance matrix. The experimental evaluation indicates that BCDR possesses a
better capacity than existing graph embedding methods to extract distance structure from original
graphs. BCDR can be integrated into graph-based learning models (especially in graph neural networks), which should improve their performance on graph structure recognition. This will be our
future work.


-----

REFERENCES

_Principal Component Analysis and Factor Analysis, pp. 150–166. Springer New York, New York,_
[NY, 2002. ISBN 978-0-387-22440-4. doi: 10.1007/0-387-22440-8 7. URL https://doi.](https://doi.org/10.1007/0-387-22440-8_7)
[org/10.1007/0-387-22440-8_7.](https://doi.org/10.1007/0-387-22440-8_7)

A. Ahmed, N. Shervashidze, S. Narayanamurthy, V. Josifovski, and A. J. Smola. Distributed largescale natural graph factorization. In Proceedings of the 22nd international conference on World
_Wide Web, pp. 37–48, 2013._

S. Baswana and T. Kavitha. Faster algorithms for approximate distance oracles and all-pairs small
stretch paths. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science
_(FOCS’06), pp. 591–602, Oct 2006. doi: 10.1109/FOCS.2006.29._

David M Blei, Andrew Y Ng, and Michael I Jordan. Latent dirichlet allocation. the Journal of
_machine Learning research, 3:993–1022, 2003._

Ulrik Brandes and Christian Pich. Centrality Estimation in Large Networks. International Journal
_of Bifurcation and Chaos, 17(7):2303, January 2007. doi: 10.1142/S0218127407018403._

Shaosheng Cao, Wei Lu, and Qiongkai Xu. Deep neural networks for learning graph representations.
In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.

Jason Carlton. The shortest distance between two people is a story: Storytelling best practices in
digital and social media marketing. Journal of Digital & Social Media Marketing, 8(2):108–115,
2020.

Sudhanshu Chanpuriya, Cameron Musco, Konstantinos Sotiropoulos, and Charalampos
Tsourakakis. Node embeddings and exact low-rank representations of complex networks. Ad_vances in Neural Information Processing Systems, 33, 2020._

Yu Chen, Hanchao Ku, and Mingwu Zhang. Pp-ocq: A distributed privacy-preserving optimal
closeness query scheme for social networks. Computer Standards & Interfaces, 74:103484, 2021.

M´aria Ercsey-Ravasz and Zolt´an Toroczkai. Centrality scaling in large networks. Physical review
_letters, 105(3):038701, 2010._

Robert W Floyd. Algorithm 97: shortest path. Communications of the ACM, 5(6):345, 1962.

Lucia Galoviˇcov´a, Petra Borotov´a, Veronika Valkov´a, Nenad L Vukovic, Milena Vukic, Jana
Stef´ˇ anikov´a, Hana D´ˇ uranov´a, Przemysław Łukasz Kowalczewski, Nat´alia Cmikov´[ˇ] a, and
Miroslava Kaˇc´aniov´a. Thymus vulgaris essential oil and its biological activity. Plants, 10(9):
1959, 2021.

Rainer Gemulla, Erik Nijkamp, Peter J Haas, and Yannis Sismanis. Large-scale matrix factorization
with distributed stochastic gradient descent. In Proceedings of the 17th ACM SIGKDD interna_tional conference on Knowledge discovery and data mining, pp. 69–77, 2011._

A. Grover and J. Leskovec. node2vec: Scalable feature learning for networks. In the 22nd ACM
_SIGKDD International Conference, 2016._

A. Gubichev, S. Bedathur, S. Seufert, and G. Weikum. Fast and accurate estimation of shortest paths
in large graphs. In Proceedings of the 19th ACM Conference on Information and Knowledge
_Management, CIKM 2010, Toronto, Ontario, Canada, October 26-30, 2010, 2010._

Peter E Hart, Nils J Nilsson, and Bertram Raphael. A formal basis for the heuristic determination
of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2):100–107,
1968.

Alexander Hermans, Lucas Beyer, and Bastian Leibe. In defense of the triplet loss for person reidentification. arXiv preprint arXiv:1703.07737, 2017.

Shijie Jiang, Yang Wang, Guang Lu, and Chuanwen Li. Dlsm: Distance label based subgraph
matching on gpu. In Asia-Pacific Web (APWeb) and Web-Age Information Management (WAIM)
_Joint International Conference on Web and Big Data, pp. 194–200. Springer, 2021._


-----

[Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http:](http://snap.stanford.edu/data)
[//snap.stanford.edu/data, June 2014.](http://snap.stanford.edu/data)

Omer Levy and Yoav Goldberg. Neural word embedding as implicit matrix factorization. Advances
_in neural information processing systems, 27:2177–2185, 2014._

Vardges Melkonian et al. Mathematical models for a social partitioning problem. American Journal
_of Computational Mathematics, 11(01):1, 2021._

Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781, 2013a.

Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in neural information pro_cessing systems, pp. 3111–3119, 2013b._

Ruksar Parveen and N Sandeep Varma. Friend’s recommendation on social media using different
algorithms of machine learning. Global Transitions Proceedings, 2021.

B. Perozzi, R. Al-Rfou, and S. Skiena. Deepwalk: Online learning of social representations. Pro_ceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Min-_
_ing, 03 2014. doi: 10.1145/2623330.2623732._

Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as
matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the eleventh
_ACM international conference on web search and data mining, pp. 459–467, 2018._

Bayu Rahmad Syah, Mahyuddin Nasution, Erna Nababan, and Syahril Efendi. Sensitivity of
shortest distance search in the ant colony algorithm with varying normalized distance formulas. TELKOMNIKA Indonesian Journal of Electrical Engineering, 19:1251–1259, 08 2021. doi:
10.12928/TELKOMNIKA.v19i4.18872.

Fatemeh Salehi Rizi, Joerg Schloetterer, and Michael Granitzer. Shortest path distance approximation using deep learning techniques. In 2018 IEEE/ACM International Conference on Advances
_in Social Networks Analysis and Mining (ASONAM), pp. 1007–1014. IEEE, 2018._

S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding.
_science, 290(5500):2323–2326, 2000._

A. D. Sarma, S. Gollapudi, M. Najork, and R. Panigrahy. A sketch-based distance oracle for webscale graphs. In Proceedings of the Third International Conference on Web Search and Web Data
_Mining, WSDM 2010, New York, NY, USA, February 4-6, 2010, 2010._

C. Shaosheng, L. Wei, and X. Qiongkai. Grarep: Learning graph representations with global structural information. In Proceedings of the 24th ACM international on conference on information
_and knowledge management, pp. 891–900, 2015._

A. F. M. Smith and A. E. Gelfand. Bayesian statistics without tears: A sampling–resampling perspective. The American Statistician, 46(2):84–88, 1992. doi: 10.1080/00031305.1992.10475856.
[URL https://doi.org/10.1080/00031305.1992.10475856.](https://doi.org/10.1080/00031305.1992.10475856)

Marcus Sokolowski and Danuta Wasserman. A candidate biological network formed by genes from
genomic and hypothesis-free scans of suicide. Preventive Medicine, 152:106604, 2021.

Christian Sommer. Shortest-path queries in static networks. ACM Computing Surveys (CSUR), 46
(4):1–31, 2014.

J. B. Tenenbaum, V. De Silva, and J. C. Langford. A global geometric framework for nonlinear
dimensionality reduction. science, 290(5500):2319–2323, 2000.

M. Thorup and U. Zwick. Approximate distance oracles. Journal of the Acm, 52(1), 2004.

Anton Tsitsulin, Davide Mottin, Panagiotis Karras, and Emmanuel M¨uller. Verse: Versatile graph
embeddings from similarity measures. In Proceedings of the 2018 World Wide Web Conference,
pp. 539–548, 2018.


-----

Ye Wang, Qing Wang, Henning Koehler, and Yu Lin. Query-by-sketch: Scaling shortest path graph
queries on very large networks. In Proceedings of the 2021 International Conference on Manage_ment of Data, pp. 1946–1958, 2021._

Fang Wei. Tedi: efficient shortest path query answering on graphs. In Graph Data Management:
_Techniques and Applications, pp. 214–238. IGI global, 2012._

Z. Xiaohan, A. Sala, C. Wilson, Z. Haitao, and Z. Ben Y. Orion: Shortest path estimation for large
social graphs. In Proceedings of the 3rd Wonference on Online Social Networks, WOSN’10, pp.
9, USA, 2010. USENIX Association.

Z. Xiaohan, A. Sala, Z. Haitao, and Z. Ben. Fast and scalable analysis of massive social graphs.
_CoPR, 07 2011._

Yiding Yang, Xinchao Wang, Mingli Song, Junsong Yuan, and Dacheng Tao. Spagan: Shortest path
graph attention network. arXiv preprint arXiv:2101.03464, 2021.

Huilin Yuan, Jianlu Hu, Yufan Song, Yanke Li, and Jie Du. A new exact algorithm for the shortest
path problem: An optimized shortest distance matrix. Computers & Industrial Engineering, 158:
107407, 2021.

Xiang Yue, Zhen Wang, Jingong Huang, Srinivasan Parthasarathy, Soheil Moosavinasab, Yungui
Huang, Simon M Lin, Wen Zhang, Ping Zhang, and Huan Sun. Graph embedding on biomedical
networks: methods, applications and evaluations. Bioinformatics, 36(4):1241–1251, 10 2019.
[ISSN 1367-4803. doi: 10.1093/bioinformatics/btz718. URL https://doi.org/10.1093/](https://doi.org/10.1093/bioinformatics/btz718)
[bioinformatics/btz718.](https://doi.org/10.1093/bioinformatics/btz718)

Abeer A Zaki, Nesma A Saleh, and Mahmoud A Mahmoud. Performance comparison of some
centrality measures used in detecting anomalies in directed social networks. Communications in
_Statistics-Simulation and Computation, pp. 1–15, 2021._

Kaiwei Zeng, Munan Ning, Yaohua Wang, and Yang Guo. Hierarchical clustering with hard-batch
triplet loss for person re-identification. In Proceedings of the IEEE/CVF Conference on Computer
_Vision and Pattern Recognition, pp. 13657–13665, 2020._

Chenyi Zhuang and Qiang Ma. Dual graph convolutional networks for graph-based semi-supervised
classification. In Proceedings of the 2018 World Wide Web Conference, pp. 499–508, 2018.

A APPENDIX

A.1 CONNECTIONS TO MDS

Our algorithm also shares some connection with conventional MDS methods in global distance metric. Take a view of original MDS. Input data X distributes in agnostic high-dimensional euclidean
space and mutual distance between samples is extractable as a global distance matrix D[X] . A approximate distance matrix D[Y] calculated by embedding matrix Y endeavor to be optimized closest
to D[X] by Frobenius norm, i.e.,

min _F_ [=][ ∥][D][X][ −] _[Y Y][ T][ ∥]F[2]_ (14)
_Y_

_[∥][D][X][ −]_ _[D][Y][ ∥][2]_

Here, we suppose D[X] and Y have been double-centered for stability, and finally, Y could be deduced as the group of top-d leading eigenvectors in D[X] . Then, as a non-linear version of MDS,
Isomap (Tenenbaum et al., 2000) generalizes D[X] as distribution on a manifold and utilizes short
hops to measure the mutual distance between samples. Deriving from the above idea, we regard the
global distance matrix D[X] as a canonical metric on graphs and exert embedding matrix Z _V_ _d to_
_|_ _|×_
reconstruct it. Different from previous work, we encounter prohibitive complexity to acquire all elements in D[X] and leverage an iterative process to approximately minimize the accuracy loss between
_D[Z]_ and D[X] .


-----

Cora 1.0 Cora

15 Facebook Facebook

GrQc GrQc

0.8

10

5 0.6

log of loss 0 0.4

frob norm error

-5 0.2

-10

0.0

0 250 500 750 1000 1250 1500 1750 2000 0 250 500 750 1000 1250 1500 1750 2000

iteration iteration


(a)


(b)


Figure 5: Converge analysis of LPCA on different datasets (a): LPCA loss. (b): Frobenius norm
error.

Table 4: Converge time and Accuracy Comparison between LPCA and BCDR(ours.).

|Col1|Cora Facebo|Col3|ok GrQc|
|---|---|---|---|
||Time|mRE Time|mRE Time mRE|
|LPCA (Chanpuriya et al., 2020) BCDR(ours.)|82.60s 113.7s|0.3445 2587s 0 0.1576 774.0s 0|.8272 1163s 0.3952 .1599 264.8s 0.1603|



A.2 CONNECTIONS TO GRAPH STRUCTURE DECOMPOSITION

A newly published work (Chanpuriya et al., 2020) provides an exciting perspective to embed complex sparse graphs perfectly into low-rank representations, which is helpful for downstream ML
tasks. Nevertheless, we need to address the limitation of LPCA in shortest distance prediction as
follows.

First and most importantly, it should be clarified that a perfect representation of graph structure is
not equal to that of graph shortest path structure, since they have a large calculation gap. According
to Floyd-Warshall algorithm (Floyd, 1962), even if each node is aware of all related path structures,
inference of the exact shortest path structure also needs up to O(N [3]) complexity. Second, LPCA
has poor embedding performance on some relatively dense graphs, despite converging fast on sparse
graphs. We test this method on the three real-world datasets used in this paper, and illustrate the
converge curve in Figure 5. The converge time is reported in Table 4. The results show LPCA meets
a bottleneck on the relative-dense graph (Facebook) and consumes a long time to converge.

Compared to the above method, the motivation of this paper is to directly embed graph shortest
distance matrix with sub-linear time complexity for fast and accurate online queries of shortest
distance. To the best of our knowledge, there is no existing embedding method that could directly
and perfectly represent shortest path structures in linear time. Moreover, our method takes a more
flexible objective to represent shortest distances, since only high-level restrictions are implicitly
exerted on the embedding space by Equation 12 and 13.

A.3 PROOF OF THEOREM 1

_Proof. We simplify symbols Nh(va), eh(va), fh(va) as Nh, eh, fh for short._


min{E(va),h+k−1}

_N→ h = #(_ _vj_ _vj_ _a[(][i][)]_

_i=h_ _{_ _|_ _∈N_ _[}][)]_

[

_h_

_N← h = #(_ _vj_ _vj_ _a[(][i][)]_

_i=max{[0,h−k+1}{_ _|_ _∈N_ _[}][)]_


(15)


-----

According to definition in the theorem, we have Nh = eh+fh. Since only eh nodes could travel from
_Nh to Nh+1, We firstly consider PR(eh →_ _eh+1|eh →_ _Nh+1) and PB(eh →_ _eh+1|eh →_ _Nh+1)._

For general random walk, the choice of destination is based on uniform sampling, thus causing

_PR(eh_ _eh+1_ _eh_ _Nh+1) =_ _[e][h][+1]_ (16)
_→_ _|_ _→_ _Nh+1_

For BC-based random walk, we need calculate BC value of eh+1 and fh+1 nodes for starters. Let
BC(eh+1) and BC(fh+1) represent the BC value of nodes in eh+1 and fh+1 respectively, and the

_←_ _→_ _←_
correspond legal shortest path counts comes from 4 sources as→ _{N h →_ _N h+2}, {N h →_ _Nh+1},_

_{specified source, thenNh+1 →_ _N h+2} and {Nh+1 →_ _Nh+1}. And we use BC({· →·}) as the BC gain from the_


_←_ _→_ _←_ _→_
BC({N h → _N h+2}) =_ _N hN h+2_

_←_ _←_
BC({N h → _Nh+1}) =_ _N h(fh+1 · 0 + eh+1βe[(1)][)]_

_→_ _→_
BC({Nh+1 → _N h+2}) =_ _N h+2(fh+1 · 1 + eh+1βe[(1)][)]_

BC({Nh+1 → _Nh+1}) = Nh[2]+1[β]e[(2)]_


(17)


_→_
where βe[(1)] means average BC gain between nodes in eh+1 and _N h+2, and βe[(2)]_ means average BC
gain between nodes both in eh+1, which are constantly related with G. Therefore, we have

BC(eh+1) = _N← hN→ h+2 + (N← h +_ _N→ h+2)eh+1βe[(1)]_ + _N→ h+2fh+1 + N[ 2]h+1[β]e[(2)]_ (18)

Likewise, we calculate

BC(fh+1) =N← hN→ h+2 0 + _N← h(fh+1βf[(1)]_ + eh+1 0) + _N→ h+2(fβf[(1)]_ + eh+1 0) + Nh[2]+1[β]e[(2)]
_·_ _·_ _·_

=(N← h + _N→ h+2)βf[(1)]_ + Nh[2]+1[β]f[(2)]
(19)
To compare the above BC(eh+1) and BC(fh+1),


BC(fh+1) (N← h + _N→ h+2)βf[(1)]_ + Nh[2]+1[β]f[(2)] (20)
BC(eh+1) [=] _N← hN→ h+2 + (N← h +_ _N→ h+2)eh+1βe[(1)]_ + _N→ h+2fh+1 + N[ 2]h+1[β]e[(2)]_

_→_ _←_ _→_
note that for any Nj and N(x,y) = _N 0 −_ _N x −_ _N y where j, x, y ∈{0, E(va)},_

_Nj_
lim = lim (21)
_k→E(va)−1−h_ _N(x,y)_ _k→E(va)−1−h_ _[ϵ][(][k][) = 0]_


Equation 19 is reduced to

BC(fh+1) 2ϵ(k)βf[(1)] + ϵ(k[2])βf[(2)] = 2βf[(1)][ϵ][(][k][)] (22)
BC(eh+1) [=] 1 + 2ϵ(k)neh+1βe[(1)] + ϵ(k)fh+1 + ϵ(k[2])βe[(2)]

Then, we perform weighted random sampling based on BC and get


_eh+1_
_pB(eh →_ _eh+1|eh →_ _Nh+1) =_ _eh+1 + 2fh+1βf[(1)][ϵ][(][k][)]_ (23)


-----

Now, we consider the relation between PR(Nh _eh+1_ _Nh_ _Nh+1) and PB(Nh_ _eh+1_ _Nh_
_Nh+1)._ _→_ _|_ _→_ _→_ _|_ _→_
_pB(Nh_ _Nh+1)_
_→_
_pR(Nh_ _Nh+1) [=][ p]p[B]R[(]([e]e[h]h[)])[p]pR[B]([(]e[e]h[h][ →]_ _N[N]h[h]+1[+1])[)]_
_→_ _→_

= _[p][B][(][N][h][−][1][ →]_ _[e][h][) +][ p][B][(][N][h][−][1][ →]_ _[f][h][)][p][B][(][f][h][ →]_ _[e][h][)]_

_pR(Nh−1 →_ _eh) + pR(Nh−1 →_ _fh)pR(fh →_ _eh)_

= 1 + [[][p][B][(][N][h][−][1][ →] _[e][h][)][ −]_ _[p][R][(][N][h][−][1][ →]_ _[e][h][)] [1][ −]_ _[p][R][(][f][h][ →]_ _[e][h][)]]_

_pR(Nh−1 →_ _eh) + pR(Nh−1 →_ _fh)pR(fh →_ _eh)_

_pR(fh_ _eh)ϵ_ (24)
+ _→_

_pR(Nh−1 →_ _eh) + pR(Nh−1 →_ _fh)pR(fh →_ _eh)_

= 1 + _fh[1 −_ 2fhβf[(1)][ϵ][(][k][)][1][ −] _[p][R][(][f][h][ →]_ _[e][h][)]]_

(1 + _[f]eh[h]_ [)[][e][h][ + 2][f][h][β]f[(1)][ϵ][(][k][)]][p][R][(][f][h][ →] _[e][h][)]_

_pR(fh_ _eh)ϵ_
+ _→_

_pR(Nh−1 →_ _eh) + pR(Nh−1 →_ _fh)pR(fh →_ _eh)_

Let C = _pR(Nh−1→eh)+pRpR(f(hN→h−eh1→)ϵ_ _fh)pR(fh→eh)_ [,][ B][(][k][) =] (1+fh[1fheh−[)[]2f[e]h[h]β[+2]f[(1)][f][h]ϵ([β]kf[(1)])][1ϵ(−kp)]Rp(Rf(hf→h→ehe)]h) [. Since]

_C is a non-negative value independent of k, finally we get_


_pB(Nh →_ _Nh+1)_ (25)
_pR(Nh_ _Nh+1) [= 1 +][ B][(][k][) +][ C]_
_→_

lim + C. (26)
_k→E(va)−1−h_ _[B][(][k][) +][ C][ =][ A][2]A[ −]1_ [1]


where


A.4 PROOF OF PROPOSITION 1

_Proof. Initially, we rewrite the negative sampling item of Equation 10 as_


Evk _pN_ (vk _vi)[log σ(_ **ZiZ[T]k** [)]) =]
_∼_ _|_ _−_


_pN_ (vk|vi)[log σ(−ZiZ[T]k [)]]
_vkX∈Wi_ (27)

_pN_ (vk|vi)[log σ(−ZiZ[T]k [)]]
_vk∈WXi\{vj_ _}_


= pN (vj|vi)[log σ(−ZiZ[T]j [)] +]


Then, for each pair of vi _V and vj_ _Wi, we get independent objective by combing similar items_
in overall likelihood expression ∈ Evx _∈p[f_ (Zi, Zj)], and get
_∼_

Evx _p[f_ (Zi, Zj)] = (vi, vj)
_∼_ _L_

_vXi∈V_ _vjX∈Wi_ (28)

_L(vi, vj) = p(vi, vj) log σ(−ZiZ[T]j_ [) +][ λp][(][v][i][)][p][N] [(][v][j][|][v][i][) log][ σ][(][−][Z][i][Z]j[T] [)]

Let _D[ˆ] = ZZ_ _[T]_, for each node pair (va, vb) with mutual shortest distance _D[ˆ]_ _ab, consider_

_Dˆ_ _ab = ZaZ[T]b_ [= arg max] (29)
**Za,Zb**

_[L][(][v][a][, v][b][)]_

Suppose vb is n-hops away from va, and denote BC(vb) by γb, according to Equation 5,

_p(va, vb) = p(va)_ _p(vb_ _va) = p(va)_ _α[n]γb_ (30)
_·_ _|_ _·_

Note that pN (vb _va) is a negative sampling in walk set Wa(Equation 11) which is selected by BC-_
_|_
based random walk locally restricted to va according to Equation 5, we have

_pN_ (vb _va) = κ(va)γb_ (31)
_|_


-----

where κ(va) is related with the neighbor structure of va. Then, Equation 29 could be described as

_Dˆ_ _ab = arg maxDˆ_ _ab_ _p(va)α[n]γb log σ( D[ˆ]_ _ab) + λp(va)κ(va)γb log σ(−D[ˆ]_ _ab)_ (32)

Solve the above problem by just let _[∂][L][(][v][a][,v][b][)]_ be equal to zero, i.e.,

_∂D[ˆ]_ _ab_


_∂_ (va, vb)
_L_ = _p(va)α[n]γbσ(1_ _Dab)_ _λp(va)κ(va)γbσ(1 + D[ˆ]_ _ab) = 0_ (33)

_∂D[ˆ]_ _ab_ _−_ [ˆ] _−_

After some simplification, we get

_Dˆ_ _ab = n log α −_ log λκ(va) (34)

Let A = _λκ(va) and there holds_
_−_

_Dˆ_ _ab = n log α −_ log A (35)

A.5 PROOF OF THEOREM 2

_Proof. Let vb and vc in graph be n and m-hops away from va respectively. In terms of node pair_
(va, vb), as proved in Proposition 1, their mutual distance Dab in the embedding space varies linear
with respect to the graph shortest distance n, i.e.,

_D[ˆ]_ _ab_ = _n log α_ log A = _n log α + log A_ (36)
_|_ _|_ _|_ _−_ _|_ _−_

Likewise, we have for (va, vc)

_D[ˆ]_ _ac_ = _m log α_ log A = _m log α + log A_ (37)
_|_ _|_ _|_ _−_ _|_ _−_

where 0 < α < 1 and A is independent of vb and vc. Then, consider the distance relation of va, vb
and vc, there holds

(Dab _Dbc)(_ _D[ˆ]_ _ab_ _D[ˆ]_ _bc_ ) = (n _m)(m_ _n) log α =_ log α (n _m)[2]_ 0 (38)
_−_ _|_ _| −|_ _|_ _−_ _−_ _−_ _·_ _−_ _≥_

A.6 COMPLEXITY ANALYSIS OF BCDR EMBEDDING ALGORITHM

We analyze the complexity of Algorithm 1 as follows.

The first step depends on the algorithm used for BC calculation, wherein some approximation methods could reduce complexity to O(|V |) or O(|V | log |V |)(Brandes & Pich, 2007; Ercsey-Ravasz
& Toroczkai, 2010). Then, in the second step, for each walk rooted at each node vi(line 23),
we use a loop(line 2 to 20) up to win times for generating nodes on the walk. Normalization of
_pi_ _j(line 5 to 18) is calculated for lin times for each node, and summation of γ is up to O(_ _E_ )
_→_ _|_ _|_
during the whole routine. Therefore, it takes totally O(winlin _V_ + _E_ ) time complexity. Fi_|_ _|_ _|_ _|_
nally, as for the third step, line 26 to 33 re-weights explored area of every node vi which need
loops up to winlin|V | times. For the sake of resampling woutlout nodes, line 34 also requires normalization by O(woutlout _V_ ). Line 37 use a maximum likelihood optimization which occupies
_|_ _|_
_O(woutlout[2]_ _[|][V][ |][ log][ |][V][ |][ +][ w][out][l][out][|][V][ |][ +][ |][E][|][)][ time complexity(Mikolov et al., 2013a). As for space]_
complexity, distance map Di and p(vj|vi) are stored temporarily up to O(winlin), while visit sign
set Si is up to O(win). For dumped and resampled walk paths, O((winlin + woutlin)|V |) space is
required. Finally, our embedding algorithm takes O(woutlout[2] _[|][V][ |][ log][ |][V][ |][+(][w][in][l][in]_ [+][w][out][l][out][)][|][V][ |][+]
_E_ ) time complexity and O((winlin +woutlout) _V_ ) space complexity. Especially, for sparse graph,
_|_ _|_ _|_ _|_
time complexity is reduced to O(woutlout[2] _[|][V][ |][ log][ |][V][ |][ + (][w][in][l][in]_ [+][ w][out][l][out][)][|][V][ |][)][.]

A.7 COMPLEMENTARY INFORMATION OF DATASETS

This part provides detailed information about graph datasets we used, and presents some visualization result in Figure 6.


-----

(a) (b) (c)

(d) (e) (f)

Figure 6: Visualization of graph datasets. (a): Cora. (b): Facebook. (c): GrQc. (d), (e), (f):
TG(20, 1, 3, 10).

A.7.1 CORA

Cora graph dataset describes the citation relationship of papers, which contains 2708 nodes and
10556 directed edges among them. Each node also has a predefined feature with 1433 dimensions.

A.7.2 FACEBOOK

Facebook dataset(Leskovec & Krevl, 2014) describes the relationship among Facebook users by
their social circles(or friend lists), which is collected from a group of test users. Facebook has also
encoded each user with a reindexed user ID to protect their privacy.

A.7.3 GRQC

Arxiv GR-QC (General Relativity and Quantum Cosmology) collaboration network(Leskovec &
Krevl, 2014) is recorded from the e-print arXiv in the period from January 1993 to April 2003,
which used to represent co-author relationship based on their submission. We suppose an undirected
edge (vi, vj) if an author vi co-authored a paper with another author vj. If one paper is owned by k
authors, a complete graph of k nodes is generated correspondingly.

A.7.4 TEST GRAPH (TG)

We define TG(cls, c, r, n) as a parameterized graph simulation for SDQ tasks. cls is the number
of sub-graphs to represent communities, and n is the number of nodes in each community. c and
_r determine the inner and outer connectivity of each community, respectively. TG is guaranteed to_
be an undirected and connected graph in our experiment, which is also expected to be sparse and of
large diameter. Some simulation results of TG(20, 1, 3, 10) that we used in Section 4.4 and 4.5 are
presented in Figure 6 (d), (e), (f).

A.7.5 OTHER GRAPHS

We also use some other graphs with diverse structures in this paper. The visualization of these graphs
is shown in Figure 7. We describe each graph as follows.


-----

(a) (b) (c)

(d) (e) (f)

Figure 7: Visualization of some synthetic graphs with diverse structure. (a): circle graph. (b):
triangle graph. (c): tri-circle graph. (d): tree graph. (e): spiral graph. (f): net graph.

_• Circle Graph: a graph that contains several circles of different sizes. The simulation of_
circle graphs takes an iterative process where for each newly introduced circle, there are a
limited number of nodes (called exit nodes) connected to the previous node set.

_• Triangle Graph: a graph possessing several cliques which are linearly connected mutually._

_• Tri-circle Graph: a graph that combines the properties of circle graphs and triangle graphs._
Here, each circle is simulated by connecting triangle sub-graphs end to end.

_• Tree Graph: a graph that is generated from one root to several leaves recursively. There is_
no cycle in tree graphs. To control the tree structure, we define a splitting probability that
is decayed exponentially with current depth.

_• Spiral Graph: a graph shaped like a spiral line. We first simulate a line graph and add edges_
between nodes with exponentially increased distances by their indices on the line.

_• Net Graph: a graph containing grid-like connections between nodes. We define a small_
probability to drop those edges stochastically.

A.8 BASELINE ALGORITHM

We outline all of the baseline models used in performance comparison as follows.

A.8.1 LLE

Locally Linear Embedding(LLE)(Roweis & Saul, 2000) is an effective method of dimensional reduction that preserves the local linear combination property of nodes. In contrast with previous
PCA(Jol, 2002) and LDA(Blei et al., 2003) which are guaranteed to discover an optimal reduction
in euclidean space, LLE that addresses local distance relation gives a more compact representation
for non-linear manifolds.

A.8.2 LE

Analog to Laplace-Beltrami operator on manifolds, Laplacian Eigenmap(LE)(Roweis & Saul, 2000)
leverages graph Laplacian matrix to generate embedding vectors. The objective of LE is to minimize


-----

Table 5: Performance comparison with other GRL techniques

|Col1|Cora|Col3|Facebook|Col5|GrQc|Col7|
|---|---|---|---|---|---|---|
||mAE|mRE|mAE|mRE|mAE|mRE|
|GraRep (Shaosheng et al., 2015) NetMF (Qiu et al., 2018) VERSE (Tsitsulin et al., 2018) LPCA (Chanpuriya et al., 2020)|2.4036 4.1388 2.9453 2.3739|0.3444 0.5988 0.4140 0.3445|2.7975 1.5179 1.1553 2.0306|1.0000 0.5477 0.3939 0.8272|4.2263 4.10134 3.3925 2.7971|0.6083 0.6037 0.4761 0.3952|
|BCDR(ours.)|0.9768 ± 0.0245|0.1605 ± 0.0043|0.4804 ± 0.0406|0.1770 ± 0.0156|1.0490 ± 0.0634|0.1684 ± 0.0058|



mutual distance on edges by L2 loss, which maps nodes with more first-order links closer to each
other.

A.8.3 GF

Graph Factorization(GF)(Ahmed et al., 2013) utilize matrix factorization methods(Gemulla et al.,
2011) to deal with graph structure exploration. By approximating the graph adjacency matrix on a
bundle of random nodes, GF is of high efficiency for large graphs.

A.8.4 DEEPWALK

DeepWalk(Perozzi et al., 2014) is a random walk-based embedding method of sub-linear complexity
to represent graph structure. This method derives from skip-gram(Mikolov et al., 2013a) and negative sampling(Mikolov et al., 2013b) to learn each node representation by predicting its context.

A.8.5 NODE2VEC

Node2Vec(Grover & Leskovec, 2016) improves DeepWalk by performing a parametrized random
walk. For each transition, Node2Vec considers second-order proximity to decide the next node be
near or far from the previous node, which allows exploration both in local and global scopes.

A.8.6 DADL

DADL(Rizi et al., 2018) leverages conventional GRL methods to embed local structure on each
node, which implies some similarities between the current node and its neighbors. Then, by considering different binary operations over node embeddings in deep learning techniques, this method
outperforms conventional ones in the shortest distance prediction task.

A.9 FURTHER COMPARISON IN ACCURACY

We also evaluate our embedding method with the latest GRL techniques. Parameter setup takes the
same configuration as stated in Section 4.2 except for some trivial modification to match the embedding dimension d = 16. All compared models take default parameters. We list out the comparison
among these methods in Table 5. Moreover, we further illustrate the relation between prediction
accuracy and path length for each method on both sparse graph (GrQc) and relatively-dense graph
(Facebook). The sampling frequency of different path lengths in each dataset is presented in Figure
8. Length-level prediction accuracy is presented in Figure 9.

The experimental results show our method outperforms others mainly benefited by decent representations of node pair’s similarity in a large range of shortest distance. On the one hand, BC-based
walk occupies a wider range of shortest paths on each node, making remote nodes available before
embedding. On the other hand, the distance resampling strategy discerns nodes by different order
proximity to preserve their mutual shortest distance.

A.10 RUN TIME OF BCDR AND GENERAL RANDOM WALK

As is stated in Section 4.2, the time complexity of BCDR could be adjusted by sampling parameters
_win, wout, lin, lout. To keep the capacity of accomodating large shortest distance, win and lin are_
_wfixed as the previous. Defineout is thus adapted for inputs, i.e., β as the compressing coefficient of path length, and use wout =_ _linloutwin_ = 40β [. The comparasion between BCDR] lout = 40 × β.


-----

0.4 0.20

0.3 0.15

0.2 0.10

sample frequency sample frequency

0.1 0.05

0.0 0.00

0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 0 2 4 6 8 10 12 14 16

path length path length


(a)


(b)


Figure 8: Sampling frequency of different path lengths. (a): Facebook dataset. (b): GrQc dataset.


2.00 2.00

lle, mRE lle, mRE
le, mRE le, mRE

1.75 gf, mRE 1.75 gf, mRE

dw, mRE dw, mRE

1.50 n2v, mRE 1.50 n2v, mRE

dadl, mRE dadl, mRE
bcdr, mRE bcdr, mRE

1.25 lpca, mRE 1.25 lpca, mRE

netmf, mRE netmf, mRE

1.00 grp, mRE 1.00 grp, mRE

mRE score vs, mRE mRE score vs, mRE

0.75 0.75

0.50 0.50

0.25 0.25

0.00 0.00

1.0 1.5 2.0 2.5 3.0 3.5 4.0 2 4 6 8 10 12 14 16

path length path length


(a)


(b)


Figure 9: Length-level prediction accuracy (a): Facebook dataset. (b): GrQc dataset.

and general random walk method is provided in Figure 10 and 11 for run time and corresponding
accuracy, respectively.

The experimental results reveal that our method could reduce time complexity with high accuracy
to keep pace with general random walk in sparse graphs, but for relatively-dense graphs(like Facebook), there is some room for further optimization.

A.11 FURTHER DISCUSSION ON WALKING PATTERNS

We test the performance of BC-based walk and other walking patterns on six synthetic graphs. The
statistics of these graphs we simulated are listed in Table 6. To address the aspect of getting out of
local cliques or circles, we provide another BFS-like searching pattern where each transition tends
to choose the edges that could get out of the local clique by considering up to second-order proximity (with probability pout 0.901). Properties and visualization of these graphs are presented in
Appendix A.7.5. And traversal results are illustrated in Figure 12 to Figure 17. The fluctuation of ≈
BC value on each graph is illustrated in Figure 18

The results are analyzed as follows.

_• For circle graphs and tri-circle graphs, BC-based walk tends to choose the exit nodes of_
each circle since they share a large BC gain by locating on the shortest path between inner
nodes and outer nodes.


-----

200 BCDRGeneral RW

180

160

millisecond of run time 140

120

0.0 0.2 0.4 0.6 0.8

beta


BCDR

900 General RW

800

700

600

500

millisecond of run time

400

300

0.0 0.2 0.4 0.6 0.8

beta


BCDR

400 General RW

375

350

325

300

millisecond of run time 275

250

225

0.0 0.2 0.4 0.6 0.8

beta


(a)


(b)


(c)


Figure 10: Comparison of run time between BCDR and general random walk. (a): Cora dataset (b):
Facebook dataset. (c): GrQc dataset.


0.24

0.22

mRE 0.20 BCDRGeneral RW

0.18

0.16

0.0 0.2 0.4 0.6 0.8

beta


0.325

0.300

0.275

mRE 0.250

0.225

0.200

0.175

BCDR

0.150 General RW

0.0 0.2 0.4 0.6 0.8

beta


0.40

0.35

mRE 0.30 BCDRGeneral RW

0.25

0.20

0.15

0.0 0.2 0.4 0.6 0.8

beta


(a)


(b)


(c)


Figure 11: Comparison of accuracy correpsonding to run time presented in Figure 10. (a): Cora
dataset (b): Facebook dataset. (c): GrQc dataset.

_• For triangle graphs, transitions on every triangle clique tend to move forward since the num-_
ber of nodes beyond the current clique is often larger than that of inner nodes, contributing
to more shortest paths.

_• For tree graphs, each transition appears to move forward from the root to the leaves, and all_
walking patterns show a similar exploration.

_• For spiral graphs, although some exit nodes are located on the circle, BC gains on exit_
nodes and inner nodes on circles are usually on par, which misleads the direction choice of
the next transition. Thus, BC-based walk only performs slightly better than others.

_• For net graphs, all walking patterns are limited on exploration distance, since BC values on_
different nodes do not change considerably.

To conclude, the above results show that BC-based walk possesses a better all-around performance
to capture remote nodes with large shortest distances.


-----

Table 6: Statistics of six synthetic graphs

|Col1|Circle Triangle Tri-circle Tree Spiral Net|
|---|---|
|V | | E | | E /V | | | | avg. Degree diameter|262 352 234 207 550 100 281 853 559 206 585 178 1.0725 2.4233 2.3889 0.9952 1.0636 1.78 2.1412 4.8438 4.7735 1.9855 2.1255 3.55 32 100 26 18 101 18|


25 25 25 25 25

20 20 20 20 20

15 15 15 15 15

10 10 10 10 10

Probability of Explored Distance 5 Probability of Explored Distance 5 Probability of Explored Distance 5 Probability of Explored Distance 5 Probability of Explored Distance 5

0 0 5 10Walk length 15 20 25 0 0 5 10Walk length 15 20 25 0 0 5 10Walk length 15 20 25 0 0 5 10Walk length 15 20 25 0 0 5 10Walk length 15 20 25


(a)


(b)


(c)


(d)


(e)


Figure 12: Exploration distance of different random walk strategies tested on circle graph. (a):
General random walk (b): Node2Vec. (c): Random Surfing. (d): BFS-like search. (e): BC-based
random walk(ours.).


80 80 80 80 80

70 70 70 70 70

60 60 60 60 60

50 50 50 50 50

40 40 40 40 40

30 30 30 30 30

Probability of Explored Distance 20 Probability of Explored Distance 20 Probability of Explored Distance 20 Probability of Explored Distance 20 Probability of Explored Distance 20

10 10 10 10 10

0 0 10 20 30 Walk length40 50 60 70 80 0 0 10 20 Walk length30 40 50 60 0 0 10 20 Walk length30 40 50 60 70 0 0 10 20 30 Walk length40 50 60 70 80 0 0 10 20 30 Walk length40 50 60 70 80


(a)


(b)


(c)


(d)


(e)


Figure 13: Exploration distance of different random walk strategies tested on triangle graph. (a):
General random walk (b): Node2Vec. (c): Random Surfing. (d): BFS-like search. (e): BC-based
random walk(ours.).


20.0 20.0 20.0 20.0 20.0

17.5 17.5 17.5 17.5 17.5

15.0 15.0 15.0 15.0 15.0

12.5 12.5 12.5 12.5 12.5

10.0 10.0 10.0 10.0 10.0

7.5 7.5 7.5 7.5 7.5

Probability of Explored Distance 5.0 Probability of Explored Distance 5.0 Probability of Explored Distance 5.0 Probability of Explored Distance 5.0 Probability of Explored Distance 5.0

2.5 2.5 2.5 2.5 2.5

0.0 0.0 2.5 5.0 7.5Walk length10.0 12.5 15.0 17.5 0.0 0.0 2.5 5.0 7.5Walk length10.0 12.5 15.0 17.5 0.0 0.0 2.5 5.0 7.5Walk length10.0 12.5 15.0 17.5 0.0 0.0 2.5 5.0 7.5Walk length10.0 12.5 15.0 17.5 0.0 0.0 2.5 5.0 7.5Walk length10.0 12.5 15.0 17.5


(a)


(b)


(c)


(d)


(e)


Figure 14: Exploration distance of different random walk strategies tested on tri-circle graph. (a):
General random walk (b): Node2Vec. (c): Random Surfing. (d): BFS-like search. (e): BC-based
random walk(ours.).


10 10 10 10 10

8 8 8 8 8

6 6 6 6 6

4 4 4 4 4

Probability of Explored Distance 2 Probability of Explored Distance 2 Probability of Explored Distance 2 Probability of Explored Distance 2 Probability of Explored Distance 2

0 0 2 Walk length4 6 8 0 0 2 Walk length4 6 8 0 0 2 Walk length4 6 8 0 0 2 Walk length4 6 8 0 0 2 Walk length4 6 8


(a)


(b)


(c)


(d)


(e)


Figure 15: Exploration distance of different random walk strategies tested on tree graph. (a): General random walk (b): Node2Vec. (c): Random Surfing. (d): BFS-like search. (e): BC-based
random walk(ours.).


-----

50 50 50 50 50

40 40 40 40 40

30 30 30 30 30

20 20 20 20 20

Probability of Explored Distance 10 Probability of Explored Distance 10 Probability of Explored Distance 10 Probability of Explored Distance 10 Probability of Explored Distance 10

0 0 10 20Walk length 30 40 50 0 0 10 20Walk length 30 40 50 0 0 10 20Walk length 30 40 50 0 0 10 20Walk length 30 40 50 0 0 10 20Walk length 30 40 50


(a)


(b)


(c)


(d)


(e)


Figure 16: Exploration distance of different random walk strategies tested on spiral graph. (a):
General random walk (b): Node2Vec. (c): Random Surfing. (d): BFS-like search. (e): BC-based
random walk(ours.).


14 14 14 14 14

12 12 12 12 12

10 10 10 10 10

8 8 8 8 8

6 6 6 6 6

Probability of Explored Distance 4 Probability of Explored Distance 4 Probability of Explored Distance 4 Probability of Explored Distance 4 Probability of Explored Distance 4

2 2 2 2 2

0 0 2 4 Walk length6 8 10 12 14 0 0 2 4 Walk length6 8 10 12 14 0 0 2 4 Walk length6 8 10 12 14 0 0 2 4 Walk length6 8 10 12 14 0 0 2 4 Walk length6 8 10 12 14


(a)


(b)


(c)


(d)


(e)


Figure 17: Exploration distance of different random walk strategies tested on net graph. (a): General
random walk (b): Node2Vec. (c): Random Surfing. (d): BFS-like search. (e): BC-based random
walk(ours.).


G_Circle

0.7

0.6

0.5

0.4

0.3

BC value of nodes

0.2

0.1

0.0 0 50 100 150 200 250

nodes


G_Triangle

0.5

0.4

0.3

BC value of nodes 0.2

0.1

0.0 0 50 100 150 200 250 300 350

nodes


G_Tri-circle

0.5

0.4

0.3

BC value of nodes 0.2

0.1

0.0 0 50 100 150 200

nodes


(a)

0.7 G_Tree

0.6

0.5

0.4

0.3

BC value of nodes

0.2

0.1

0.0 0 50 100 150 200

nodes


(d)


(b)

G_Spiral

0.4

0.3

0.2

BC value of nodes

0.1

0.0 0 100 200 300 400 500

nodes


(e)


(c)

G_Net

0.30

0.25

0.20

0.15

BC value of nodes

0.10

0.05

0.00 0 20 40 60 80 100

nodes


(f)


Figure 18: Fluctuation of BC value on each graph. (a): circle graph. (b): triangle graph. (c):
tri-circle graph. (d): tree graph. (e): spiral graph. (f): net graph.


-----

