summaries: This paper proposed a new graph shortest distance embedding method. This method uses a betweenness centrality based random walk to sample paths in the graph and distance resampling step before optimization. They show that the estimated distance after embedding has a linear dependence with the original distance in the graph They also show that this embedding method preserves the shortest distance relation between points. In experimental results, they show that this algorithm achieves better accuracy than previous algorithms.   This paper proposes a method to construct graph embeddings that are well-tuned for answering shortest-distance queries (SDQs), based on betweennes centrality distance sampling. The main idea appears to be that the betweenness centrality measures helps identify nodes that could serve as landmarks for distance calculations, hence an distance-oriented embedding anchored on betweenness centrality is bound to perform well. Distance are resampled from walk paths, and a step of other methods based on pointwise mutual information (PMI) optimization is abandoned. In this work the author(s) proposed a framework for node embeddings that captures better shortest path distances for undirected graphs. Specifically, the authors propose a new random walk framework based on betweenness centralities, and a distance resampling strategy that uses the shortest path distances, and the betweenness centrality scores and is shown to capture well shortest path distances (Proposition 1).  The authors also evaluate their framework experimentally, verifying that compared to other popular node embedding methods, it can be used to represent shortest path distances faithfully.  This paper presents a new Shortest Distance Query technique, namely, the Betweenness Centrality-based Distance Re- sampling (BCDR). The objective of this technique is overcome some drawbacks of traditional embedding-based distance prediction methods based on truncated random walks and point-wise Mutual Information (PMI). These drawbacks are a limited distance exploration and the lack of preservation of the shortest distance relation due to local optima. BCDR uses betweenness centrality to create a random walk that occupies a wider distance and uses Distance Resampling (DR) instead of PMI to preserve the relationship of distances. The paper presents theoretical guarantees of performance to address the exploration range and the intractability of shortest distance on paths. The experiments on three real datasets and simulated datasets show the performance evaluation with respect to baselines, exploration distance, and preservation of distance relation (and violation of the probability distance relation)
abstractText: 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.
authors.name: TANCE RESAMPLING
references.authors: A. Ahmed N. Shervashidze S. Narayanamurthy V. Josifovski A.J. Smola
references.title: Distributed largescale natural graph factorization
references.venue: In Proceedings of the 22nd international conference on World Wide Web,
references.authors: S. Baswana T. Kavitha
references.title: Faster algorithms for approximate distance oracles and all-pairs small stretch paths
references.venue: 47th Annual IEEE Symposium on Foundations of Computer Science
references.authors: David M Blei Andrew Y Ng Michael I Jordan
references.title: Latent dirichlet allocation
references.venue: Journal of machine Learning research,
references.authors: Ulrik Brandes Christian Pich
references.title: Centrality Estimation in Large Networks
references.venue: International Journal of Bifurcation and Chaos,
references.authors: Shaosheng Cao Wei Lu Qiongkai Xu
references.title: Deep neural networks for learning graph representations
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Jason Carlton
references.title: The shortest distance between two people is a story: Storytelling best practices in digital and social media marketing
references.venue: Journal of Digital & Social Media Marketing,
references.authors: Sudhanshu Chanpuriya Cameron Musco Konstantinos Sotiropoulos Charalampos Tsourakakis
references.title: Node embeddings and exact low-rank representations of complex networks
references.venue: Advances in Neural Information Processing Systems,
references.authors: Yu Chen Hanchao Ku Mingwu Zhang
references.title: Pp-ocq: A distributed privacy-preserving optimal closeness query scheme for social networks
references.venue: Computer Standards & Interfaces,
references.authors: Mária Ercsey-Ravasz Zoltán Toroczkai
references.title: Centrality scaling in large networks
references.venue: Physical review letters,
references.authors: Robert W Floyd
references.title: Algorithm 97: shortest path
references.venue: Communications of the ACM,
references.authors: Lucia Galovičová Petra Borotová Veronika Valková Nenad L Vukovic Milena Vukic Jana Štefániková Hana Ďúranová Przemysław Łukasz Kowalczewski Natália Čmiková Miroslava Kačániová
references.title: Thymus vulgaris essential oil and its biological activity
references.authors: Rainer Gemulla Erik Nijkamp Peter J Haas Yannis Sismanis
references.title: Large-scale matrix factorization with distributed stochastic gradient descent
references.venue: In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining,
references.authors: A. Grover J. Leskovec
references.title: node2vec: Scalable feature learning for networks
references.venue: In the 22nd ACM SIGKDD International Conference,
references.authors: A. Gubichev S. Bedathur S. Seufert G. Weikum
references.title: Fast and accurate estimation of shortest paths in large graphs
references.venue: In Proceedings of the 19th ACM Conference on Information and Knowledge Management,
references.authors: Peter E Hart Nils J Nilsson Bertram Raphael
references.title: A formal basis for the heuristic determination of minimum cost paths
references.venue: IEEE transactions on Systems Science and Cybernetics,
references.authors: Alexander Hermans Lucas Beyer Bastian Leibe
references.title: In defense of the triplet loss for person reidentification
references.venue: arXiv preprint arXiv:1703.07737,
references.authors: Shijie Jiang Yang Wang Guang Lu Chuanwen Li
references.title: Dlsm: Distance label based subgraph matching on gpu. In Asia-Pacific Web (APWeb) and Web-Age Information Management (WAIM
references.venue: Joint International Conference on Web and Big Data,
references.authors: Jure Leskovec Andrej
references.title: Krevl. SNAP Datasets: Stanford large network dataset collection
references.venue: http: //snap.stanford.edu/data,
references.authors: Omer Levy Yoav Goldberg
references.title: Neural word embedding as implicit matrix factorization
references.venue: Advances in neural information processing systems,
references.authors: Vardges Melkonian
references.title: Mathematical models for a social partitioning problem
references.venue: American Journal of Computational Mathematics,
references.authors: Tomas Mikolov Kai Chen Greg Corrado Jeffrey Dean
references.title: Efficient estimation of word representations in vector space
references.venue: arXiv preprint arXiv:1301.3781,
references.authors: Tomas Mikolov Ilya Sutskever Kai Chen Greg S Corrado Jeff Dean
references.title: Distributed representations of words and phrases and their compositionality
references.venue: In Advances in neural information processing systems,
references.authors: Ruksar Parveen N Sandeep Varma
references.title: Friend’s recommendation on social media using different algorithms of machine learning
references.venue: Global Transitions Proceedings,
references.authors: B. Perozzi R. Al-Rfou S. Skiena
references.title: Deepwalk: Online learning of social representations
references.venue: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,
references.authors: Jiezhong Qiu Yuxiao Dong Hao Ma Jian Li Kuansan Wang Jie Tang
references.title: Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec
references.venue: In Proceedings of the eleventh ACM international conference on web search and data mining,
references.authors: Bayu Rahmad Syah Mahyuddin Nasution Erna Nababan Syahril Efendi
references.title: Sensitivity of shortest distance search in the ant colony algorithm with varying normalized distance formulas
references.venue: TELKOMNIKA Indonesian Journal of Electrical Engineering,
references.authors: Fatemeh Salehi Rizi Joerg Schloetterer Michael Granitzer
references.title: Shortest path distance approximation using deep learning techniques
references.venue: IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM),
references.authors: S.T. Roweis L.K. Saul
references.title: Nonlinear dimensionality reduction by locally linear embedding
references.authors: A.D. Sarma S. Gollapudi M. Najork R. Panigrahy
references.title: A sketch-based distance oracle for webscale graphs
references.venue: In Proceedings of the Third International Conference on Web Search and Web Data Mining,
references.authors: C. Shaosheng L. Wei X. Qiongkai
references.title: Grarep: Learning graph representations with global structural information
references.venue: In Proceedings of the 24th ACM international on conference on information and knowledge management,
references.authors: A.F.M. Smith A.E. Gelfand
references.title: Bayesian statistics without tears: A sampling–resampling perspective
references.venue: The American Statistician,
references.authors: Marcus Sokolowski Danuta Wasserman
references.title: A candidate biological network formed by genes from genomic and hypothesis-free scans of suicide
references.venue: Preventive Medicine,
references.authors: Christian Sommer
references.title: Shortest-path queries in static networks
references.venue: ACM Computing Surveys (CSUR),
references.authors: J.B. Tenenbaum V. De Silva J.C. Langford
references.title: A global geometric framework for nonlinear dimensionality reduction
references.authors: M. Thorup U. Zwick
references.title: Approximate distance oracles
references.venue: Journal of the Acm,
references.authors: Anton Tsitsulin Davide Mottin Panagiotis Karras Emmanuel Müller
references.title: Verse: Versatile graph embeddings from similarity measures
references.venue: In Proceedings of the 2018 World Wide Web Conference,
references.authors: Ye Wang Qing Wang Henning Koehler Yu Lin
references.title: Query-by-sketch: Scaling shortest path graph queries on very large networks
references.venue: In Proceedings of the 2021 International Conference on Management of Data,
references.authors: Fang Wei
references.title: Tedi: efficient shortest path query answering on graphs. In Graph Data Management: Techniques and Applications, pp. 214–238
references.venue: IGI global,
references.authors: Z. Xiaohan A. Sala C. Wilson Z. Haitao Z. Ben Y
references.title: Orion: Shortest path estimation for large social graphs
references.venue: In Proceedings of the 3rd Wonference on Online Social Networks,
references.authors: Z. Xiaohan A. Sala Z. Haitao Z. Ben
references.title: Fast and scalable analysis of massive social
references.venue: graphs. CoPR,
references.authors: Yiding Yang Xinchao Wang Mingli Song Junsong Yuan Dacheng Tao
references.title: Spagan: Shortest path graph attention network
references.venue: arXiv preprint arXiv:2101.03464,
references.authors: Huilin Yuan Jianlu Hu Yufan Song Yanke Li Jie Du
references.title: A new exact algorithm for the shortest path problem: An optimized shortest distance matrix
references.venue: Computers & Industrial Engineering,
references.authors: Xiang Yue Zhen Wang Jingong Huang Srinivasan Parthasarathy Soheil Moosavinasab Yungui Huang Simon M Lin Wen Zhang Ping Zhang Huan Sun
references.title: Graph embedding on biomedical networks: methods, applications and evaluations
references.venue: Bioinformatics, 36(4):1241–1251,
references.authors: Abeer A Zaki Nesma A Saleh Mahmoud A Mahmoud
references.title: Performance comparison of some centrality measures used in detecting anomalies in directed social networks
references.venue: Communications in Statistics-Simulation and Computation,
references.authors: Kaiwei Zeng Munan Ning Yaohua Wang Yang Guo
references.title: Hierarchical clustering with hard-batch triplet loss for person re-identification
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Chenyi Zhuang Qiang Ma
references.title: Dual graph convolutional networks for graph-based semi-supervised classification
references.venue: In Proceedings of the 2018 World Wide Web Conference,
sections.text: 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.
sections.heading: 1 INTRODUCTION
sections.text: 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; Galovičová 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 toO(kN2) andO(kN logN) 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(N3) O(N2) O(kN) 0 Exact Index - O(N2 logN) O(N2) O(kN logN) 0 Exact Cache - − O(N) O(N) ∼ O(N2) 0 Approximate Oracle - O(αN1+ 1 α ) O(αN1+ 1 α )O(kα) 2(α− 1) Approximate Landmark - O(lN logN + lN) O(lN) O(kl) 0.523 Approximate Embedding Orion O(αN logN + cN) O(dN) O(kd) 0.688
  Rigel O(αN logN + cN) O(dN) O(kd) 0.369 DeepWalk O(TKN logN + (T + c)N) O(dN) O(kd) 0.329 Node2Vec O(TKN logN + (T + c)N) O(dN) O(kd) 0.299 DADL O(TKN logN + (T + c)N) O(dN) O(kd) 0.228 BCDR(ours.) O(αTKN logN + (βT + c)N)O(dN) O(kd) 0.177
  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 distance 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 better empirical performance in solving the SDQ problem than existing embedding-based methods (see Section 4).
sections.heading: 2 NOTATION & PROBLEM DEFINITION
sections.heading: 2.1 NOTATION
sections.text: 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 〈W1i ,W2i , · · · ,W li〉, where Wki is a node chosen from the neighborhood of node W k−1 i for k = 1, ..., l, withW0i := vi. Pi is a finite set of walk paths sampled fromWi, and Wi is the multiset of nodes on the walk paths in Pi.
sections.heading: 2.2 PROBLEM DEFINITION
sections.text: 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 p̊ij 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 p̊ij . 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→ Rd, G : 〈Rd,Rd〉 → 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 approximation 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.,
  mRE := 1 |Q| ∑
  (vi,vj)∈Q
  |D̂ij −Dij | Dij , mAE := 1 |Q| ∑
  (vi,vj)∈Q
  |D̂ij −Dij | (2)
sections.heading: 3 METHOD
sections.text: 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.
sections.heading: 3.1 BC-BASED RANDOM WALK
sections.text: 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
  BC(vi) = ∑ s6=i 6=t σst(vi) σst (4)
  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 walkWa = 〈W1a ,W2a , ...Wja, ...〉 on node va, we prefer choosing nodes with the largest BC values among their neighborhoods when simulating walk paths, i.e.,
  p(Wja|Wj−1a = vj−1) = BC(Wja)∑
  vk∈Nj−1 BC(vk) , Wja ∈ Nj−1 (5)
  where Ni is the neighborhood of vi. The following theorem, proved in Appendix A.3, indicates that a BC-based random walk tends to transit from N (h)a to N (h+1)a , leading to a deeper exploration measured by the intrinsic graph’s 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 N (h)a = {vj |Daj = h} as a set of nodes that are h-hops away from va and Nh(va) = |N (h)a | as the number of nodes in the set. Let the number of the nodes that have connection with nodes in N (h+1)a (called connective nodes) be eh(va) and the number of other nodes (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)) represent 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)) pR(Nh(va)→ Nh+1(va)) = 1 +B(k) + C (6)
  lim k→E(va)−1−h B(k) + C = A2 − 1 A1 + C > 0
  A1 = eh(va)
  fh(va) , A2 =
  1
  pR(fh(va)→ eh(va)) .
  (7)
  where C ≥ 0, and E(va) is the eccentricity of va, E(va) = maxvb∈GDab.
sections.heading: 3.2 DISTANCE RESAMPLING
sections.text: 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 f
  Evx∼p[f ] = ∑
  v1,v2∈V f(v1, v2)p(v1, v2) (8)
  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 fromWji ). Our objective is thus to sample fromWi to generate a new random vector W̊i = 〈W̊1i , W̊2i , ..., W̊ l̊i〉 of length l̊. Then, each node vj sampled from W̊ j i can be described as a weighted resampling in original walk pathsWi based on Dij and BC(vj), i.e.,
  Evj∼p(vj |vi)[f |vi] = ∑
  vi,vj∈V f(vi, vj)p(vj |vi) = ∑ vi,vj∈V f(vi, vj)q(vj |vi) p(vj |vi) q(vj |vi)
  ≈ ∑ vi∈V ∑ vj∈Wi f(vi, vj)q(vj |vi) αDijBC(vj)∑ vk∈Wi α DikBC(vk)
  (9)
  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 Z Evx∼p[f(Zi,Zj)] = ∑ vi∈V p(vi)Evj∼p(W̊i)[p(vj |vi)(log σ(ZiZ T j ) + λEvk∼pN (vk|vi)[log σ(−ZiZ T k )])]
  (10)
  Thereinto, f(Zi,Zj) = log σ(ZiZTj ), pN (vk|vi) 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) = #(vk occurs in Wi)
  #(Wi) (11)
  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 embedding matrix corresponds to a global distance matrix, i.e. ZZT = 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α− logA (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.
sections.heading: 3.3 ALGORITHM
sections.text: 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,
  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 takesO(woutl2out|V | log |V |+(winlin+woutlout)|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 τ . 1 Def BC Walk(G, vi,Di, win, lin, τ): 2 for walk k from 0 to win do 3 visit sign set Si := {vi}, current node vc := vi, length ci := 0, real length cri := 0 4 while ci < lin do 5 N kc := {vj |vj ∈ Nc ∧ vj /∈ Si} 6 if τ is True then 7 normalize pc→j ← softmax(γj + 1), vj ∈ N kc 8 else 9 normalize pc→j ← γj∑
  vm∈Nkc γm , vj ∈ N ki
  10 end 11 sample next vn from N kc by pc→j 12 if vn ∈ Di then 13 Di[vn] = min{Di[vn], cri + 1} 14 cri = min{Di[vn]− 1, cri } 15 else 16 Di[vn] = c r i + 1 17 end 18 vc ← vn, Si ← vn, ci ← ci + 1, cri ← cri + 1 19 end 20 end
  21 pre-compute BC of each node vi as γi ← BC(vi). 22 Walk path set P 23 for vi in G do 24 distance map Di := {vi : 0} 25 Di ← BC Walk (G, vi, Di, win, lin, τ) 26 for vj ∈ Di.keys do 27 if τ is True then 28 γ′j ← softmax(γj + 1) 29 p(vj |vi) := αDi[vj ] · γ′j 30 else 31 p(vj |vi) := αDi[vj ] · γj 32 end 33 end 34 sample walk paths Pi = {(vi, vx1 , vx2 , · · · , vxj , · · · )}of length lout by
  p(vxj |vi), vxj ∈ Di.keys for wout times. 35 append Pi into P 36 end 37 maximize Equation 10 by P . 38 return Z
sections.heading: 4 EXPERIMENTAL EVALUATION
sections.text: In this section, we evaluate our model’s performance with several graph datasets and compare it with conventional embedding-based methods for SDQ tasks.
sections.heading: 4.1 DATASETS
sections.text: 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 ∈ S, a destination set D with their shortest distances to the source is randomly collected. Then, |S| × |Di| input node pairs are simulated. The detailed setup for each dataset is presented in Table 2 (columns 8 to 11).
sections.heading: 4.2 PARAMETER SETUP
sections.text: 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
  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.
sections.heading: 4.3 PERFORMANCE OF PREDICTION ACCURACY
sections.text: 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.
sections.heading: 4.4 RESULT OF EXPLORATION DISTANCE
sections.text: 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.
sections.heading: 4.5 PRESERVATION OF DISTANCE RELATION
sections.text: 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 ZiZTj for any node vi and vj . We initially train embedding vectors using walks simulated 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.
  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.
sections.heading: 5 CONCLUSION
sections.text: 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.
sections.heading: A APPENDIX
sections.heading: A.1 CONNECTIONS TO MDS
sections.text: 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 DX . A approximate distance matrix DY calculated by embedding matrix Y endeavor to be optimized closest to DX by Frobenius norm, i.e.,
  min Y ‖DX −DY ‖2F = ‖DX − Y Y T ‖2F (14)
  Here, we suppose DX and Y have been double-centered for stability, and finally, Y could be deduced as the group of top-d leading eigenvectors in DX . Then, as a non-linear version of MDS, Isomap (Tenenbaum et al., 2000) generalizes DX 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 DX 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 inDX and leverage an iterative process to approximately minimize the accuracy loss between DZ and DX .
sections.heading: A.2 CONNECTIONS TO GRAPH STRUCTURE DECOMPOSITION
sections.text: 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(N3) 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.
sections.heading: A.3 PROOF OF THEOREM 1
sections.text: Proof. We simplify symbols Nh(va), eh(va), fh(va) as Nh, eh, fh for short.
  → Nh = #( min{E(va),h+k−1}⋃ i=h {vj |vj ∈ N (i)a })
  ← Nh = #( h⋃ i=max{0,h−k+1} {vj |vj ∈ N (i)a })
  (15)
  According to definition in the theorem, we haveNh = 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) = eh+1 Nh+1
  (16)
  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 { ← Nh → → Nh+2}, { ← Nh → Nh+1}, {Nh+1 → → Nh+2} and {Nh+1 → Nh+1}. And we use BC({· → ·}) as the BC gain from the specified source, then
  BC({ ← Nh → → Nh+2}) = ← Nh → Nh+2 BC({ ← Nh → Nh+1}) = ← Nh(fh+1 · 0 + eh+1β(1)e ) BC({Nh+1 → → Nh+2}) = → Nh+2(fh+1 · 1 + eh+1β(1)e )
  BC({Nh+1 → Nh+1}) = N2h+1β(2)e
  (17)
  where β(1)e means average BC gain between nodes in eh+1 and → Nh+2, and β (2) e means average BC gain between nodes both in eh+1, which are constantly related with G. Therefore, we have
  BC(eh+1) = ← Nh → Nh+2 + ( ← Nh + → Nh+2)eh+1β (1) e + → Nh+2fh+1 +N 2 h+1β (2) e
  (18)
  Likewise, we calculate
  BC(fh+1) = ← Nh → Nh+2 · 0 + ← Nh(fh+1β (1) f + eh+1 · 0) + → Nh+2(fβ (1) f + eh+1 · 0) +N 2 h+1β (2) e
  =( ← Nh + → Nh+2)β (1) f +N 2 h+1β (2) f
  (19) To compare the above BC(eh+1) and BC(fh+1),
  BC(fh+1) BC(eh+1) =
  ( ← Nh + → Nh+2)β (1) f +N 2 h+1β (2) f
  ← Nh → Nh+2 + ( ← Nh + → Nh+2)eh+1β (1) e + → Nh+2fh+1 +N2h+1β (2) e
  (20)
  note that for any Nj and N(x,y) = → N0 − ← Nx − → Ny where j, x, y ∈ {0, E(va)},
  lim k→E(va)−1−h Nj N(x,y) = lim k→E(va)−1−h (k) = 0 (21)
  Equation 19 is reduced to
  BC(fh+1) BC(eh+1) =
  2 (k)β (1) f + (k 2)β (2) f
  1 + 2 (k)neh+1β (1) e + (k)fh+1 + (k2)β (2) e
  = 2β (1) f (k) (22)
  Then, we perform weighted random sampling based on BC and get
  pB(eh → eh+1|eh → Nh+1) = eh+1
  eh+1 + 2fh+1β (1) f (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) = pB(eh)pB(eh → Nh+1) pR(eh)pR(eh → Nh+1)
  = pB(Nh−1 → eh) + pB(Nh−1 → fh)pB(fh → eh) pR(Nh−1 → eh) + pR(Nh−1 → fh)pR(fh → eh)
  = 1 + [pB(Nh−1 → eh)− pR(Nh−1 → eh)] [1− pR(fh → eh)]
  pR(Nh−1 → eh) + pR(Nh−1 → fh)pR(fh → eh)
  + pR(fh → eh)
  pR(Nh−1 → eh) + pR(Nh−1 → fh)pR(fh → eh)
  = 1 + fh[1− 2fhβ(1)f (k)][1− pR(fh → eh)]
  (1 + fheh )[eh + 2fhβ (1) f (k)]pR(fh → eh)
  + pR(fh → eh)
  pR(Nh−1 → eh) + pR(Nh−1 → fh)pR(fh → eh)
  (24)
  Let C = pR(fh→eh) pR(Nh−1→eh)+pR(Nh−1→fh)pR(fh→eh) , B(k) = fh[1−2fhβ(1)f (k)][1−pR(fh→eh)]
  (1+ fh eh )[eh+2fhβ (1) f (k)]pR(fh→eh)
  . Since
  C is a non-negative value independent of k, finally we get
  pB(Nh → Nh+1) pR(Nh → Nh+1) = 1 +B(k) + C (25)
  where
  lim k→E(va)−1−h B(k) + C = A2 − 1 A1 + C. (26)
sections.heading: A.4 PROOF OF PROPOSITION 1
sections.text: Proof. Initially, we rewrite the negative sampling item of Equation 10 as
  Evk∼pN (vk|vi)[log σ(−ZiZ T k )]) = ∑ vk∈Wi pN (vk|vi)[log σ(−ZiZTk )]
  = pN (vj |vi)[log σ(−ZiZTj )] + ∑
  vk∈Wi\{vj}
  pN (vk|vi)[log σ(−ZiZTk )] (27)
  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∈V ∑ vj∈Wi L(vi, vj)
  L(vi, vj) = p(vi, vj) log σ(−ZiZTj ) + λp(vi)pN (vj |vi) log σ(−ZiZTj ) (28)
  Let D̂ = ZZT , for each node pair (va, vb) with mutual shortest distance D̂ab, consider
  D̂ab = ZaZ T b = arg max Za,Zb L(va, vb) (29)
  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 BCbased 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 max D̂ab
  p(va)α nγb log σ(D̂ab) + λp(va)κ(va)γb log σ(−D̂ab) (32)
  Solve the above problem by just let ∂L(va,vb) ∂D̂ab be equal to zero, i.e.,
  ∂L(va, vb) ∂D̂ab = p(va)α nγbσ(1− D̂ab)− λp(va)κ(va)γbσ(1 + D̂ab) = 0 (33)
  After some simplification, we get
  D̂ab = n logα− log λκ(va) (34)
  Let A = −λκ(va) and there holds
  D̂ab = n logα− logA (35)
sections.heading: A.5 PROOF OF THEOREM 2
sections.text: 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α− logA| = −n logα+ logA (36)
  Likewise, we have for (va, vc)
  |D̂ac| = |m logα− logA| = −m logα+ logA (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)
sections.heading: A.6 COMPLEXITY ANALYSIS OF BCDR EMBEDDING ALGORITHM
sections.text: 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. Finally, 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(woutl 2 out|V | log |V | + woutlout|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 takesO(woutl2out|V | log |V |+(winlin+woutlout)|V |+ |E|) time complexity andO((winlin+woutlout)|V |) space complexity. Especially, for sparse graph, time complexity is reduced to O(woutl2out|V | log |V |+ (winlin + woutlout)|V |).
sections.heading: A.7 COMPLEMENTARY INFORMATION OF DATASETS
sections.text: This part provides detailed information about graph datasets we used, and presents some visualization result in Figure 6.
  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.
sections.heading: A.7.2 FACEBOOK
sections.text: 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).
sections.heading: A.7.5 OTHER GRAPHS
sections.text: 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.
  • 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.
sections.heading: A.8 BASELINE ALGORITHM
sections.text: 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
  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.
sections.heading: A.8.4 DEEPWALK
sections.text: 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.
sections.heading: A.8.5 NODE2VEC
sections.text: 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.
sections.heading: A.9 FURTHER COMPARISON IN ACCURACY
sections.text: 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.
sections.heading: A.10 RUN TIME OF BCDR AND GENERAL RANDOM WALK
sections.text: 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 fixed as the previous. Define β as the compressing coefficient of path length, and use lout = 40×β. wout is thus adapted for inputs, i.e., wout = linwinlout = 40 β . The comparasion between BCDR
  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.
sections.heading: A.11 FURTHER DISCUSSION ON WALKING PATTERNS
sections.text: 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.
  • For triangle graphs, transitions on every triangle clique tend to move forward since the number 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.
title: BCDR: BETWEENNESS CENTRALITY-BASED DIS-