# Effective and Efficient PageRank-based Positioning for Graph Visualization

[Technical Report]

Shiqi Zhang  National University of SingaporeSingapore Southern University of
Science and TechnologyChina<EMAIL_ADDRESS>,  Renchi Yang  Hong Kong
Baptist UniversityChina<EMAIL_ADDRESS>,  Xiaokui Xiao  National
University of SingaporeSingapore<EMAIL_ADDRESS>,  Xiao Yan
<EMAIL_ADDRESS>and  Bo Tang<EMAIL_ADDRESS>Southern University of
Science and TechnologyChina

###### Abstract.

Graph visualization is a vital component in many real-world applications
(e.g., social network analysis, web mining, and bioinformatics) that enables
users to unearth crucial insights from complex data. Lying in the core of
graph visualization is the node distance measure, which determines how the
nodes are placed on the screen. A favorable node distance measure should be
informative in reflecting the full structural information between nodes and
effective in optimizing visual aesthetics. However, existing node distance
measures yield sub-par visualization quality as they fall short of these
requirements. Moreover, most existing measures are computationally
inefficient, incurring a long response time when visualizing large graphs. To
overcome such deficiencies, we propose a new node distance measure,
$\mathsf{PDist}$, geared towards graph visualization by exploiting a well-
known node proximity measure, personalized PageRank. Moreover, we propose an
efficient algorithm $\mathsf{Tau}$-$\mathsf{Push}$ for estimating
$\mathsf{PDist}$ under both single- and multi-level visualization settings.
With several carefully-designed techniques, $\mathsf{Tau}$-$\mathsf{Push}$
offers non-trivial theoretical guarantees for estimation accuracy and
computation complexity. Extensive experiments show that our proposal
significantly outperforms 13 state-of-the-art graph visualization solutions on
12 real-world graphs in terms of both efficiency and effectiveness (including
aesthetic criteria and user feedback). In particular, our proposal can
interactively produce satisfactory visualizations within one second for
billion-edge graphs.

Graph Visualization; Personalized PageRank; Approximate Algorithm

††conference: Proceedings of the 2023 International Conference on Management
of Data; June 18-23, 2023; Seattle, USA††booktitle: Proceedings of the 2023
International Conference on Management of Data (SIGMOD ’23), June 18-23,
2023††price: 15.00††isbn: 978-1-4503-XXXX-X/18/06††ccs: Human-centered
computing Graph drawings††ccs: Theory of computation Graph algorithms
analysis††ccs: Theory of computation Random walks and Markov chains

##  1\. Introduction

Graph visualization is an effective way to help users comprehend and analyze
complex relational data (e.g., social and biological networks). It has been
identified as one of the most popular and challenging graph processing tasks
in graph database systems and graph libraries (Sahu et al., 2017). In
practice, graph visualization finds extensive applications, such as analyzing
protein interactions in the organism (Agapito et al., 2013), studying
scholars’ co-authoring behaviors (Rodrigues et al., 2015), and capturing the
massive hyperlinks among web pages (Bikakis et al., 2016). This motivates a
plethora of graph visualization solutions (Eades, 1984; Fruchterman and
Reingold, 1991; Noack, 2005; Martin et al., 2011; Jacomy et al., 2014;
Torgerson, 1952; Kamada et al., 1989; Gansner et al., 2004; Brandes and Pich,
2006; Gansner et al., 2012; Meyerhenke et al., 2017; Rodrigues et al., 2015;
Abello et al., 2006; Archambault et al., 2008; Hu, 2005) and softwares
(Bastian et al., 2009; Auber, 2004; De Nooy et al., 2018; Shannon et al.,
2003).

A central problem in graph visualization is calculating an effective layout,
i.e., the coordinate of each node on the screen, which seeks to place closely-
related nodes close and unrelated nodes far apart based on a node distance
measure calculated from the graph. In most existing solutions, classic node
distance measures, including the shortest distance (Torgerson, 1952; Kamada et
al., 1989; Gansner et al., 2004; Brandes and Pich, 2006; Gansner et al., 2012;
Meyerhenke et al., 2017; Shi et al., 2009) and the direct linkage (Eades,
1984; Fruchterman and Reingold, 1991; Noack, 2005; Martin et al., 2011; Jacomy
et al., 2014; Archambault et al., 2008; Abello et al., 2006), are widely used.
However, such distance measures overlook the high-order structure information
of the graph and fail to optimize some critical visual features, leading to
sub-par visualizations (e.g., node overlapping and edge distortion). For
example, the classic stress method (Gansner et al., 2004) determines node
positions by employing unrecognizable shortest distances, resulting in severe
node overlapping.

Another long-standing challenge is visualizing large graphs. When handling
large graphs, most existing solutions (Meyerhenke et al., 2017; Martin et al.,
2011; Rodrigues et al., 2015; Shi et al., 2009; Abello et al., 2006;
Archambault et al., 2008; Hu, 2005) adopt the multi-level scheme to avoid the
poor readability and prohibitive overhead caused by visualizing all nodes in a
single-level fashion. Specifically, the multi-level strategy organizes the
nodes of the input graph $G$ into a tree $\mathcal{H}$, such that (i) each
leaf in $\mathcal{H}$ is a node in $G$, and (ii) each non-leaf node in
$\mathcal{H}$, referred to as a supernode, has only a small number of
children. The user can navigate through $\mathcal{H}$ and visualize any set
$\mathcal{S}$ of nodes or supernodes that have the same parent. Utilizing the
multi-level scheme, existing solutions still struggle to cope with large
graphs as they entail significant overheads to compute the node distances. The
reason is that these methods (e.g., (Meyerhenke et al., 2017; Martin et al.,
2011)) require calculating all pairwise distances (e.g., shortest distance)
for the leaf nodes in the subtrees of two supernodes $\mathcal{V}_{i}$ and
$\mathcal{V}_{j}$ before determining the distance between $\mathcal{V}_{i}$
and $\mathcal{V}_{j}$; otherwise, the visualization of supernodes will be
uninformative in reflecting the underlying graph structure, which results in
poor visualization quality.

To address the aforementioned challenges in effectiveness and efficiency, we
propose a new graph-theoretic node distance measure dedicated to enhancing
visualization quality, referred to as $\mathsf{PDist}$. $\mathsf{PDist}$ takes
inspiration from personalized PageRank (PPR) (Page et al., 1999), a proximity
measure quantifying the connectivity from a source node to a target node via
random walks in a graph. Considering the requirements of graph visualization,
$\mathsf{PDist}$ incorporates degree and symmetry information into PPR, and
ameliorates PPR with transformation and truncation. Through such
optimizations, $\mathsf{PDist}$ circumvents the visual issues (e.g., node
overlapping and edge distortion) that may be caused by PPR, while accurately
preserving the graph structure (e.g., degree and high-order proximity
information). Notably, our analysis shows that $\mathsf{PDist}$ offers non-
trivial visualization quality guarantees in terms of two widely-used aesthetic
criteria.

Unfortunately, computing $\mathsf{PDist}$ for supernodes is challenging as it
involves a multitude of leaf nodes underlying the supernodes. There are a
plethora of approaches for PPR computation in the literature (Page et al.,
1999; Wang et al., 2017b; Lin et al., 2020; Wang et al., 2019), but they focus
on single-source or top-$k$ PPR queries rather than arduous all-pair queries
in the case of $\mathsf{PDist}$. As a result, these approaches are inefficient
when adopted for $\mathsf{PDist}$ computation due to redundant graph traversal
operations and random walk simulations. To this end, we propose
$\mathsf{Tau}$-$\mathsf{Push}$, an efficient solution for computing
approximate $\mathsf{PDist}$. Compared to the PPR computation methods,
$\mathsf{Tau}$-$\mathsf{Push}$ achieves superior time complexity and empirical
efficiency, while retaining strong accuracy guarantees. Under the hood,
$\mathsf{Tau}$-$\mathsf{Push}$ adopts a filter-refinement paradigm
accommodating three carefully-designed techniques. First,
$\mathsf{Tau}$-$\mathsf{Push}$ computes a rough estimation of each
$\mathsf{PDist}$ by grouped forward graph traversal. Next,
$\mathsf{Tau}$-$\mathsf{Push}$ identifies a set of failed target nodes
$\mathcal{T}$ by leveraging the global PageRank of the graph. Finally,
$\mathsf{Tau}$-$\mathsf{Push}$ refines the $\mathsf{PDist}$ estimation of such
nodes by performing a handful of graph traversal operations backward from
$\mathcal{T}$. Note that our $\mathsf{PDist}$ and its computation algorithm
$\mathsf{Tau}$-$\mathsf{Push}$ are not limited to single- and multi-level
graph visualizations, and could underpin other scenarios, including graph
query result visualization (Bhowmick et al., 2020) and incremental graph
exploration (Herman et al., 2000).

Based on $\mathsf{PDist}$ and $\mathsf{Tau}$-$\mathsf{Push}$, we create our
graph visualization solution $\mathsf{PPRviz}$ and experimentally evaluate
$\mathsf{PPRviz}$ against 13 state-of-the-art methods using 12 real-world
graphs. Our empirical results demonstrate that $\mathsf{PPRviz}$ outperforms
the competitors in both effectiveness and efficiency. First and foremost,
$\mathsf{PPRviz}$ obtains considerably better visualization quality in terms
of aesthetic metrics and user satisfaction than the competitors. Moreover,
$\mathsf{PPRviz}$ runs at a fraction of the computational cost of the
competing methods for both pre-processing and online visualization. For
instance, $\mathsf{PPRviz}$ takes only 1 second to visualize the (super) node
sets from a graph with 3 billion edges, whereas none of the competitors can
produce a visualization within 1000 seconds.

To summarize, this paper makes the following contributions:

  * •

We propose $\mathsf{PDist}$, a new node distance measure that not only fully
captures the structural information of the input graph but also optimizes the
aesthetic metrics.

  * •

We devise $\mathsf{Tau}$-$\mathsf{Push}$, an algorithm for efficient
$\mathsf{PDist}$ computation with three tailored techniques, which enables
responsive visualizations even on billion-edge graphs.

  * •

We conduct extensive experiments to demonstrate the superiority of
$\mathsf{PDist}$ and $\mathsf{Tau}$-$\mathsf{Push}$ over the state-of-the-art
graph visualization methods in both effectiveness and efficiency.

##  2\. Preliminaries

In this section, we first elaborate on the procedure of graph visualization
and then introduce the multi-level mechanism for visualizing large graphs.
Finally, we discuss how to assess the visualization quality. Table 1 lists the
frequently used notations in our paper.

Table 1. Frequently used notations. Notation |  Description
---|---
$G$=$(V,E)$ |  A graph $G$ with node set $V$ and edge set $E$.
$n,m$ |  The numbers of nodes and edges in $G$, respectively.
$d(v_{i})$ |  The out-degree of node $v_{i}$ in $G$.
$\mathbf{X}$ |  The position matrix of nodes in $G$.
$\mathcal{S},k$ |  The level-($\ell$+1) supernode, the number of level-$\ell$ children in $\mathcal{S}$.
$\mathcal{V}_{i},F(\mathcal{V}_{i})$ |  The level-$\ell$ supernode, the set of leaf nodes in $\mathcal{V}_{i}$.
$\pi,\alpha$ |  The PPR value, the restart probability in the random walk.
$\boldsymbol{\Delta}[i,j]$ |  The $\mathsf{PDist}$ value of node pair $(v_{i},v_{j})$ defined in Eq. (1).
$\pi_{d}(v_{i},v_{j})$ |  The $\mathsf{DPPR}$ value of node $v_{j}$ w.r.t. node $v_{i}$ defined in Eq. (1).
$\pi_{d}(\mathcal{V}_{i},\mathcal{V}_{j})$ |  The $\mathsf{DPPR}$ value of supernode pair $(\mathcal{V}_{i},\mathcal{V}_{j})$ defined in Eq. (2).
$\hat{\pi}_{d}(v_{i},v_{j})$ |  The approximate $\mathsf{DPPR}$ of node $v_{j}$ w.r.t. node $v_{i}$ (see Eq. (3)).
$r(v_{i},v_{j})$ |  The residue of node $v_{j}$ w.r.t. node $v_{i}$ (see Eq. (3)).
$r_{max},r^{b}_{max}$ |  The forward and backward residue thresholds, respectively.
$\epsilon,\delta$ |  The approximation parameters in Definition 3.5.
$\tau_{i}$ |  The $\mathsf{DPR}$ of level-$\ell$ supernode $\mathcal{V}_{i}$ in Eq.(4).

###  2.1. Graph Visualization

Let $G=(V,E)$ be a graph, where $V$ is a set of $n$ nodes and $E$ is a set of
$m$ edges. We assume that $G$ is a directed and homogeneous graph, where the
nodes and edges have no labels/attributes. We consider the task of visualizing
the input graph $G$ on the two-dimensional Euclidean space, where the graph
$G$ is laid out based on a position matrix $\mathbf{X}\in\mathbb{R}^{n\times
2}$ and $\mathbf{X}[i]\in\mathbb{R}^{2}$ (i.e., the $i$-th row of
$\mathbf{X}$) records the coordinate of node $v_{i}\in V$ on the screen.
Following prior visualization methods (Eades, 1984; Fruchterman and Reingold,
1991; Martin et al., 2011; Jacomy et al., 2014; Kamada et al., 1989; Gansner
et al., 2004; Brandes and Pich, 2006; Gansner et al., 2012), we represent each
node with a circle by placing the center of the circle on the coordinate of
the node, and draw each directed edge using a straight arrowhead line. For
undirected edges, we omit the arrowhead to avoid a cluttered display. Thus,
$\|\mathbf{X}[i]-\mathbf{X}[j]\|$ is the distance between node $v_{i}$ and
$v_{j}$ on the screen and $l(v_{i},v_{j})=\|\mathbf{X}[i]-\mathbf{X}[j]\|$ is
the length of edge $(v_{i},v_{j})\in E$.

Given an input graph $G$, graph visualization typically consists of two
phases: (i) distance matrix computation and (ii) position matrix embedding. In
the first phase, a specific node distance matrix
$\mathbf{D}\in\mathbb{R}^{n\times n}$ is computed, in which $\mathbf{D}[i,j]$
reflects the graph-theoretic distance between nodes $v_{i}$ and $v_{j}$. For
example, (Fruchterman and Reingold, 1991; Noack, 2005; Jacomy et al., 2014)
directly employ the adjacent matrix as $\mathbf{D}$ and (Kamada et al., 1989;
Gansner et al., 2004, 2012) use the all-pair shortest distances as
$\mathbf{D}$. In the second phase, the distance matrix $\mathbf{D}$ is
converted to a position matrix $\mathbf{X}$, such that the on-screen distance
$\|\mathbf{X}[i]-\mathbf{X}[j]\|$ of node pair $(v_{i},v_{j})$ is close to
$\mathbf{D}[i,j]$ for all node pairs $(v_{i},v_{j})\in V\times V$. In
literature, there exist several optimization techniques that transform the
distance matrix into the position matrix, e.g., gradient descent (Gansner et
al., 2012), simulated annealing (Davidson and Harel, 1996), and stress
majorization (Gansner et al., 2004).

###  2.2. Multi-level Mechanism

Directly visualizing all nodes in a large graph usually results in a giant
hairball with little discernible structure information, due to the sheer
numbers of nodes and edges in the layout (Gibson et al., 2013). Thus, most
existing methods (Rodrigues et al., 2015; Shi et al., 2009; Abello et al.,
2006; Archambault et al., 2008) and softwares (Auber, 2004; De Nooy et al.,
2018; Shannon et al., 2003) visualize large graphs in an interactive and
multi-level manner, so as to cut down the number of nodes in each drawing. As
surveyed in (Herman et al., 2000; Von Landesberger et al., 2011), multi-level
methods consist of two phases: (i) preprocessing and (ii) interactive
visualization. In the preprocessing phase, a supergraph hierarchy is
constructed such that nodes of the graph $G$ are organized into a tree
$\mathcal{H}$, where (i) each leaf is a node in $G$, and (ii) each non-leaf
node, referred to as a supernode, contains $k$ children. For convenience, we
say that each leaf node is at level-0, and that each supernode
$\mathcal{V}_{i}$ is at level-$(\ell+1)$ if its children are at level-$\ell$
($\ell\geq 0$). In the interactive visualization phase, users can select any
supernode $\mathcal{S}$ at level-$(\ell+1)$, and ask for a visualization of
the $k$ children of $\mathcal{S}$, where the corresponding position matrix
$\mathbf{X}\in\mathbb{R}^{k\times 2}$ is derived following the visualization
procedure described in the preceding section. For example, if $\mathcal{S}$
consists of leaf children, then multi-level methods visualize the subgraph of
$G$ induced by the nodes in $\mathcal{S}$. On the other hand, if $\mathcal{S}$
consists of supernode children, then they visualize a high-level graph where
(i) each node represents a supernode $\mathcal{V}_{i}$ in $\mathcal{S}$ and
(ii) each edge connects from supernode $\mathcal{V}_{i}$ to supernode
$\mathcal{V}_{j}$ if $G$ contains an edge from a leaf node in the sub-tree of
$\mathcal{V}_{i}$ to another leaf node in the sub-tree of $\mathcal{V}_{j}$.
Notice that the size constraint $k$ is conducive to curtailing visual clutter
(Duncan et al., 1998) and can be configured by users according to their needs.
Throughout this paper, we refer to visualizing the entire graph on one single
layout (resp. multiple levels of layouts) as single-level (resp. multi-level)
visualization.

Although the supergraph hierarchy can be constructed offline and the time
complexity of position matrix embedding is reduced to $O(k^{3})$ (Gansner et
al., 2004) for the children of $\mathcal{S}$, existing multi-level methods
still incur high costs for the distance matrix computation of the children in
$\mathcal{S}$, especially on graphs with many nodes and edges. A keen reader
may propose to directly compute the distances of the children in $\mathcal{S}$
by treating $\mathcal{S}$ as a stand-alone graph. However, doing so overlooks
the underlying structures of $\mathcal{S}$, and thus impairs visualization
quality as pinpointed in (Martin et al., 2011; Meyerhenke et al., 2017).
Instead, a canonical approach adopted by existing methods (Meyerhenke et al.,
2017; Sokal, 1958; Martin et al., 2011) is to measure the distance between two
supernodes $\mathcal{V}_{i}$ and $\mathcal{V}_{j}$ based on the average
distance between every node pair $v_{i}$ and $v_{j}$, where $v_{i}$ (resp.
$v_{j}$) is a leaf node in $\mathcal{V}_{i}$ (resp. $\mathcal{V}_{j}$). In
other words, this approach requires computing $k^{\ell}\times k^{\ell}$ pairs
of distances for two level-$\ell$ supernodes, which poses a challenge in terms
of computation efficiency.

###  2.3. Visualization Quality Assessment

Intuitively, a high-quality graph visualization should not only reflect the
topological information of the input graph but also have good readability
(Gibson et al., 2013; Battista et al., 1998). In other words, the position
matrix $\mathbf{X}$ in the Euclidean space should accurately reflect the
structure of $G$, in the sense that well-connected nodes (resp. poorly-
connected nodes) should be placed close (resp. far apart) to each other. As
for good readability, it means that the layout should avoid negative visual
artifacts such as nodes overlapping with each other or edges with drastically
different lengths. In relation to this, there exist several aesthetic criteria
in the literature that quantify the readability of graph layouts. In this
paper, we adopt the two most commonly-used aesthetic metrics (Noack, 2007;
Klammler et al., 2018; Purchase, 2002; Taylor and Rodgers, 2005; Purchase et
al., 2002; Bennett et al., 2007), i.e., node distribution (ND) and uniform
length coefficient variance (ULCV), defined as follows.

###### Definition 2.1 (ND).

For a position matrix $\mathbf{X}$, the node distribution is
ND$\textstyle(\mathbf{X})=\sum\limits_{i<j}\frac{1}{||\mathbf{X}[i]-\mathbf{X}[j]||^{2}}$.

###### Definition 2.2 (ULCV).

For a position matrix $\mathbf{X}$, let $l_{\sigma}$ (resp. $l_{\mu}$) be the
standard deviation (resp. mean) of the edge lengths. The uniform length
coefficient variance is ULCV$(\mathbf{X})=l_{\sigma}/l_{\mu}$.

ND is the summation of the reciprocals of the squared distance between node
pairs in the graph layout. A large ND score indicates the existence of visual
clutter in the layout. In particular, overlapping nodes (occupying the same
node positions) lead to an infinite ND score. ULCV measures the skewness of
edge lengths. A large ULCV indicates that some edges are considerably longer
or shorter than others, in which case the layout tends to look distorted.

##  3\. PPR-based Node Distance

This section presents our node distance measure $\mathsf{PDist}$ for graph
visualization. We first formally define $\mathsf{PDist}$ for the case of
single-level visualization and then extend it to multi-level visualization.

###  3.1. Single-level $\boldsymbol{\mathsf{PDist}}$

Definition. $\mathsf{PDist}$ is formulated based on personalized PageRank
(PPR), a node proximity measure defined as follows. Given a directed graph
$G=(V,E)$, two nodes $v_{i},v_{j}\in V$, and a restart probability $\alpha$,
the PPR $\pi(v_{i},v_{j})$ from $v_{i}$ to $v_{j}$ is defined as the
probability that a random walk with restart (RWR) (Tong et al., 2006)
originating from $v_{i}$ would end at $v_{j}$. Specifically, an RWR starts
from $v_{i}$, and at each step, it either (i) terminates at the current node
with probability $\alpha$, or (ii) with the remaining $1-\alpha$ probability,
navigates to a random out-neighbor of the current node. Intuitively, a large
PPR $\pi(v_{i},v_{j})$ indicates that numerous paths exist from $v_{i}$ to
$v_{j}$; in other words, $v_{i}$ is well connected to $v_{j}$. Based on PPR,
we define $\mathsf{PDist}$ as follows.

###### Definition 3.1 ($\mathsf{PDist}$).

Let $\boldsymbol{\Delta}\in\mathbb{R}^{n\times n}$ be the $\mathsf{PDist}$
matrix for all node pairs in a graph $G$ and $\boldsymbol{\Delta}[i,j]$ be the
$\mathsf{PDist}$ between nodes $v_{i}$ and $v_{j}$. We define
$\boldsymbol{\Delta}[i,j]$ as

(1)
$\boldsymbol{\Delta}[i,j]=\min{\Big{(}\max\Big{(}1-\log{\left(\pi_{d}(v_{i},v_{j})+\pi_{d}(v_{j},v_{i})\right)},2\Big{)},2\log{n}\Big{)}},$

where $\pi_{d}(v_{i},v_{j})=\pi(v_{i},v_{j})\cdot d(v_{i})$ denotes the
degree-normalized PPR ($\mathsf{DPPR}$) from $v_{i}$ to $v_{j}$, and
$d(v_{i})$ is the out-degree of $v_{i}$.

The intuition behind $\mathsf{PDist}$ is that if node pair $(v_{i},v_{j})$ has
a high PPR value $\pi(v_{i},v_{j})$, then its $\mathsf{PDist}$ $\Delta[i,j]$
should be small. As such, $\mathsf{PDist}$ ensures that well-connected nodes
are placed closely in a visualization. Moreover, $\mathsf{PDist}$ also
accounts for the out-degrees of $v_{i}$ and $v_{j}$ in its definition to
overcome the inherent limitation of PPR for visualization. To explain, we
consider the example in Fig. 1, which shows a graph with nodes
$v_{0}\textrm{--}v_{9}$, as well as the PPR and $\mathsf{PDist}$ values for
node pairs $(v_{0},v_{8})$, $(v_{2},v_{0})$, and $(v_{6},v_{9})$. Observe that
$\pi(v_{2},v_{0})=0.11<\pi(v_{6},v_{9})=0.44$, even though node pairs
$(v_{2},v_{0})$ and $(v_{6},v_{9})$ are both directly connected via an edge.
This indicates that for adjacent node pairs in a graph, their PPR values could
vary considerably. As a consequence, directly transforming PPR values into
node distances would bring about a large variance in edge lengths in the
visualization. To alleviate this issue, in our formulation of
$\mathsf{PDist}$, we scale each $\pi(v_{i},v_{j})$ by multiplying it with the
out-degree of the source node $v_{i}$. It has been shown in previous work
(Yang et al., 2020) that such a scaling contributes to an accurate measure of
the strength of connections between nodes. In Fig. 1, the $\mathsf{PDist}$ of
$(v_{2},v_{0})$ is relatively close to that of $(v_{6},v_{9})$, which is more
consistent with the fact that $v_{2}$ and $v_{6}$ are direct neighbors of
$v_{0}$ and $v_{9}$, respectively. Moreover, the $\mathsf{PDist}$ of
$(v_{0},v_{8})$ is large, reflecting the fact that $v_{0}$ is far away from
$v_{8}$ in the input graph.

| PPR | $\mathsf{PDist}$
---|---|---
$(v_{0},v_{8})$ | 0.01 | 3.73
$(v_{2},v_{0})$ | 0.11 | 0.92
$(v_{6},v_{9})$ | 0.44 | 1.12

Figure 1. PPR and $\boldsymbol{\mathsf{PDist}}$ in a toy graph.

To make the node distance symmetric, we formulate $\mathsf{PDist}$ based on
$\pi_{d}(v_{i},v_{j})+\pi_{d}(v_{j},v_{i})$, since
$\pi_{d}(v_{i},v_{j})\neq\pi_{d}(v_{j},v_{i})$ in general. Furthermore,
$\mathsf{PDist}$ takes the inverse of the natural logarithm of $\mathsf{DPPR}$
$\pi_{d}(v_{i},v_{j})+\pi_{d}(v_{j},v_{i})$ and imposes an empirical
truncation to narrow down the distance variance, thereby ensuring the
distances between nodes lie in a reasonable range that can be well fitted into
a canvas. In particular, the lower and upper bounds of $\mathsf{PDist}$ are
set to 2 and $2\log{n}$ for precluding node overlapping and blank space
issues, respectively. The rationale of choosing $2\log{n}$ as the upper bound
is that the average PPR value between a node pair in a graph with $n$ nodes is
$1/n$ (Wang et al., 2017b; Shi et al., 2019) and $\mathsf{PDist}$ should focus
on reflecting the proximity information of node pairs with above-average PPR
values (i.e., relatively high relevance).

Bounds for aesthetic criteria. The following two theorems111We refer
interested readers to Appendix A for all proofs. establish the worst-case
upper bounds in terms of both ND and ULCV (see Definitions 2.1–2.2), when
utilizing $\mathsf{PDist}$ for visualization.

###### Theorem 3.2.

Given the $\mathsf{PDist}$ matrix $\boldsymbol{\Delta}$ of a graph $G$,
suppose that $||\mathbf{X}[i]-\mathbf{X}[j]||=\boldsymbol{\Delta}[i,j]$
$\forall{v_{i},v_{j}}\in V$, then ND$(\mathbf{X})\leq 0.215e\cdot
m+0.0175n^{2}$, where $e$ is the Euler constant.

###### Theorem 3.3.

Given the $\mathsf{PDist}$ matrix $\boldsymbol{\Delta}$ of a graph $G$,
suppose that $||\mathbf{X}[i]-\mathbf{X}[j]||=\boldsymbol{\Delta}[i,j]$
$\forall{v_{i},v_{j}}\in V$ and the restart probability
$\textstyle\alpha\leq\tfrac{1}{2}-\sqrt{\tfrac{1}{4}-\tfrac{1}{2e}}$, then
ULCV$\textstyle(\mathbf{X})\leq\tfrac{\left(\log{\tfrac{1}{{2\alpha(1-\alpha)}}}-1\right)}{4}$.

Note that the upper bound of the restart probability $\alpha$ in Theorem 3.3
(which is approximately 0.243) is not restrictive, as $\alpha$ is usually set
to 0.15 or 0.2 (Wang et al., 2020; Wu et al., 2021; Wang et al., 2016b;
Lofgren et al., 2016).

A case study. To verify the effectiveness of $\mathsf{PDist}$, we use
$\mathsf{PDist}$ and two classic node distance measures (i.e., the shortest
distance and $\mathsf{SimRank}$-based distance) to visualize the graph FbEgo
via the same position matrix embedding algorithm (Gansner et al., 2004). Note
that the $\mathsf{SimRank}$-based distance is obtained by plugging
$\mathsf{SimRank}$ (Jeh and Widom, 2002) into Eq. (1). Fig. 2 displays the
visualization results of the three distance measures. It can be observed that
$\mathsf{PDist}$ yields a high-quality visualization result, which organizes
the graph into a well-connected cluster and three cliques. In comparison, the
widely-used shortest distance measure (Gansner et al., 2004, 2012; Brandes and
Pich, 2006; Meyerhenke et al., 2017) suffers from severe node overlapping and
edge distortion issues. Regarding the visualization derived from
$\mathsf{SimRank}$-based distances, the edges of the cliques are distorted, as
$\mathsf{SimRank}$ assigns node pairs within the large connected component
high similarity scores but $0$ similarity scores to the 2-cliques. Besides the
qualitative results, we also report ND and ULCV scores in Fig. 2, and we can
find that $\mathsf{PDist}$ considerably outperforms the shortest distance and
the $\mathsf{SimRank}$-based distance in terms of both metrics, validating the
superior aesthetic performance of $\mathsf{PDist}$ as proved in Theorem 3.2
and Theorem 3.3.

|  |
---|---|---
ND=2.4E+03, ULCV=0.39 | ND=2.0E+04, ULCV=0.46 | ND=6.2E+03, ULCV=0.75
(a) $\mathsf{PDist}$ |  (b) Shortest distance (Gansner et al., 2004) |  (c) $\mathsf{SimRank}$ (Jeh and Widom, 2002)
Figure 2. Visualization results of $\boldsymbol{\mathsf{PDist}}$ and two other
node distances measures on the FbEgo graph. Smaller aesthetic scores indicate
better quality.

###  3.2. Multi-level $\boldsymbol{\mathsf{PDist}}$

Definition. Given a user-specified level-$(\ell+1)$ supernode $\mathcal{S}$,
multi-level visualization requires calculating the level-$\ell$
$\mathsf{PDist}$ between the $k$ level-$\ell$ children supernodes of
$\mathcal{S}$. Recall from Definition 3.1 that a linchpin functioned in
single-level $\mathsf{PDist}$ is the $\mathsf{DPPR}$ between two nodes. Thus,
we extend the $\mathsf{DPPR}$ in Definition 3.1 to level-$\ell$
$\mathsf{DPPR}$ (Definition 3.4), and level-$\ell$ $\mathsf{PDist}$ can be
derived accordingly by plugging Eq. (2) into Eq. (1).

###### Definition 3.4 (Level-$\ell$ $\mathsf{DPPR}$).

For two level-$\ell$ supernodes $\mathcal{V}_{i}$ and $\mathcal{V}_{j}$,
denote the set of leaf nodes in $\mathcal{V}_{i}$ as $F(\mathcal{V}_{i})$, the
level-$\ell$ $\mathsf{DPPR}$ $\pi_{d}(\mathcal{V}_{i},\mathcal{V}_{j})$ of
$\mathcal{V}_{j}$ w.r.t. $\mathcal{V}_{i}$ is defined as

(2) $\pi_{d}(\mathcal{V}_{i},\mathcal{V}_{j})=\frac{\sum\limits_{v_{s}\in
F(\mathcal{V}_{i}),v_{t}\in
F(\mathcal{V}_{j})}\pi_{d}(v_{s},v_{t})}{|F(\mathcal{V}_{i})|\cdot|F(\mathcal{V}_{j})|},$

where $\pi_{d}(v_{s},v_{t})$ is $\mathsf{DPPR}$ of $v_{t}$ w.r.t. $v_{s}$.

Intuitively, the level-$\ell$ $\mathsf{DPPR}$ measures the connectivity from
supernode $\mathcal{V}_{i}$ to $\mathcal{V}_{j}$ by taking the average of the
$\mathsf{DPPR}$ values from the leaf nodes in $\mathcal{V}_{i}$ to those in
$\mathcal{V}_{j}$. The idea of measuring the proximity between two supernodes
by summarizing the structure of the underlying leaf nodes is also adopted in
(Van der Maaten and Hinton, 2008; Martin et al., 2011; Sokal, 1958). In
particular, (Martin et al., 2011; Sokal, 1958) also consider the average of
all pairwise distances of the leaf nodes.

Compared with our level-$\ell$ $\mathsf{DPPR}$, a simple and straightforward
way is to take the level-$\ell$ children of supernode $\mathcal{S}$ as a
weighted graph and compute the $\mathsf{DPPR}$ on it (called
W-$\mathsf{DPPR}$). More precisely, the graph is constructed by treating each
supernode $\mathcal{V}_{i}\in\mathcal{S}$ as a node and merging the edges
between supernodes $\mathcal{V}_{i}$ and $\mathcal{V}_{j}$ in $\mathcal{S}$ as
a weighted edge. Although W-$\mathsf{DPPR}$ can be computed very efficiently
as it requires only an $O(k^{2})$ cost, it ignores the micro-structures of
each supernode and the paths containing nodes outside $\mathcal{S}$, resulting
in sub-par visualization quality. To exemplify, we consider Fig. 3, which
shows a graph with nodes $v_{0}\textrm{--}v_{5}$ and a level-2 supernode
$\mathcal{S}$ with level-1 supernodes
$\mathcal{V}_{0},\mathcal{V}_{1},\mathcal{V}_{2}$, as well as the level-$\ell$
$\mathsf{DPPR}$ ($\ell$-$\mathsf{DPPR}$ in short) and W-$\mathsf{DPPR}$ values
for supernode pairs $(\mathcal{V}_{1},\mathcal{V}_{0})$,
$(\mathcal{V}_{2},\mathcal{V}_{0})$, and $(\mathcal{V}_{2},\mathcal{V}_{1})$.
Intuitively, for the source supernode $\mathcal{V}_{2}$, $\mathcal{V}_{1}$ has
better connectivity to it than $\mathcal{V}_{0}$ as the children of
$\mathcal{V}_{2}$ and $\mathcal{V}_{0}$ share one common neighbor $v_{2}$,
whereas the children of $\mathcal{V}_{2}$ and $\mathcal{V}_{1}$ have two
common neighbors $v_{3}$ and $v_{4}$. From the table in Fig. 3, we observe
that the W-$\mathsf{DPPR}$ values of $(\mathcal{V}_{2},\mathcal{V}_{0})$ and
$(\mathcal{V}_{2},\mathcal{V}_{1})$ are the same, which is counter-intuitive.
In contrast, level-$\ell$ $\mathsf{DPPR}$ addresses this issue and accurately
captures the structure of the original graph.

|  $\ell$-$\mathsf{DPPR}$ |  W-$\mathsf{DPPR}$
---|---|---
$(\mathcal{V}_{1},\mathcal{V}_{0})$ | 0.56 | 0.74
$(\mathcal{V}_{2},\mathcal{V}_{0})$ | 0.39 | 0.69
$(\mathcal{V}_{2},\mathcal{V}_{1})$ | 0.50 | 0.69

Figure 3. A toy example of level-$\boldsymbol{\ell}$
$\boldsymbol{\mathsf{DPPR}}$.

###  3.3. Efficiency Challenges

As per Eq.(1) and Eq.(2), the level-$\ell$ $\mathsf{PDist}$ between
$\mathcal{V}_{i}$ and $\mathcal{V}_{j}$ requires computing the exact PPR
values for all pairs of leaf nodes in $F(\mathcal{V}_{i})\times
F(\mathcal{V}_{j})$, where $F(\mathcal{V}_{i})$ (resp. $F(\mathcal{V}_{j})$)
signifies the set of leaf nodes of $\mathcal{V}_{i}$ (resp.
$\mathcal{V}_{j}$). As pointed out in prior work (Yang et al., 2020), exact
PPR computation is prohibitive as it entails summing up an infinite series. An
option is to compute the near-exact result by performing power iterations
($\mathsf{PI}$) (Page et al., 1999) until the absolute error of PPR is less
than $10^{-9}$ (the precision of float). That said, we still need to invoke
$\mathsf{PI}$ for each of the $O(k^{\ell+1})$ leaf nodes in the specified
level-$(\ell+1)$ supernode $\mathcal{S}$, where each invocation has $O(m)$
time complexity (Page et al., 1999). As a result, the near-exact computation
of the level-$\ell$ $\mathsf{PDist}$ matrix incurs a high cost of
$O(k^{\ell+1}m)$, which may be $O(mn)$ in the worst case (i.e., for the
highest level supergraph).

To alleviate the above-said efficiency issue, we resort to computing
approximate level-$\ell$ $\mathsf{PDist}$. Towards this end, we define the
concept of $(\epsilon,\delta)-$approximate level-$\ell$ $\mathsf{DPPR}$.

###### Definition 3.5 ($(\epsilon,\delta)-$approximate level-$\ell$
$\mathsf{DPPR}$).

Let $\epsilon$ and $\delta$ be two constants, for any two supernodes
$\mathcal{V}_{i},\mathcal{V}_{j}\in\mathcal{S}$ and
$\mathcal{V}_{i}\neq\mathcal{V}_{j}$,
$\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})$ is an
$(\epsilon,\delta)-$approximation of level-$\ell$ $\mathsf{DPPR}$
$\pi_{d}(\mathcal{V}_{i},\mathcal{V}_{j})$ if it satisfies the following
conditions.

  * •

If $\pi_{d}(\mathcal{V}_{i},\mathcal{V}_{j})<\delta$,
$|\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})-\pi_{d}(\mathcal{V}_{i},\mathcal{V}_{j})|\leq\epsilon\cdot\delta$.

  * •

If $\pi_{d}(\mathcal{V}_{i},\mathcal{V}_{j})\geq\delta$,
$|\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})-\pi_{d}(\mathcal{V}_{i},\mathcal{V}_{j})|\leq\epsilon\cdot\pi_{d}(\mathcal{V}_{i},\mathcal{V}_{j})$.

The following Lemma 3.6 shows that we can convert the
$(\epsilon,\delta)$-approximate level-$\ell$ $\mathsf{DPPR}$ into an
approximate level-$\ell$ $\mathsf{PDist}$. Accordingly, we focus on computing
$(\epsilon,\delta)-$approximate level-$\ell$ $\mathsf{DPPR}$ in the rest of
the paper.

###### Lemma 3.6.

Given constants $\theta$ and $\sigma$, by setting
$\delta=\frac{e^{1-\sigma}}{2}$ and
$\epsilon=1-\left(\frac{1}{e^{2}}\right)^{\theta}$,
$(\epsilon,\delta)$-approximate level-$\ell$ $\mathsf{DPPR}$ results in an
approximate level-$\ell$ $\mathsf{PDist}$ $\widehat{\boldsymbol{\Delta}}[i,j]$
satisfying

  * •

If $\boldsymbol{\Delta}[i,j]<\sigma$,
$|\boldsymbol{\Delta}[i,j]-\widehat{\boldsymbol{\Delta}}[i,j]|\leq\theta\cdot{\boldsymbol{\Delta}[i,j]}$,

  * •

If $\boldsymbol{\Delta}[i,j]\geq\sigma$,
$|\boldsymbol{\Delta}[i,j]-\widehat{\boldsymbol{\Delta}}[i,j]|\leq\theta\cdot\sigma$
.

To compute $(\epsilon,\delta)-$approximate level-$\ell$ $\mathsf{DPPR}$ values
w.r.t. a source supernode $\mathcal{V}_{i}$, a straightforward approach is to
utilize existing single source PPR (SSPPR) approximation methods (Fogaras et
al., 2005; Andersen et al., 2006; Wang et al., 2017b; Wu et al., 2021; Hou et
al., 2021; Shi et al., 2019). Specifically, the state-of-the-art methods (Wang
et al., 2017b; Shi et al., 2019; Wang et al., 2019; Lin et al., 2020; Luo et
al., 2019; Wu et al., 2021) are built upon $\mathsf{Forward}$-$\mathsf{Push}$
(Andersen et al., 2006). Given a source leaf node $v_{i}$,
$\mathsf{Forward}$-$\mathsf{Push}$ maintains an estimated $\mathsf{DPPR}$
$\widehat{\pi}_{d}(v_{i},v_{j})$ and a residue value $r(v_{i},v_{j})$ for each
node $v_{j}$, where $r(v_{i},v_{i})$ is set to $d(v_{i})$ and all
$\widehat{\pi}_{d}(v_{i},v_{j})$ and other residue $r(v_{i},v_{j})$ are set to
0 initially. Then, $\mathsf{Forward}$-$\mathsf{Push}$ starts a deterministic
graph traversal from source node $v_{i}$, and at each step converts $\alpha$
portion of the residue of current node $v_{j}$ (i.e., $r(v_{i},v_{j})$) into
its estimated $\mathsf{DPPR}$ value $\widehat{\pi}_{d}(v_{i},v_{j})$ and
distributes the remaining $1-\alpha$ part to $v_{j}$’s out-neighbors evenly.
For convenience, we refer to the operation of distributing a fraction of node
$v_{j}$’s residue to one of its out-neighbors as a push operation.

Figure 4. An example of
$\boldsymbol{\mathsf{Forward}}$-$\boldsymbol{\mathsf{Push}}$.

A running example. To exemplify, suppose that the restart probability
$\alpha=0.1$ and $\mathsf{Forward}$-$\mathsf{Push}$ is performed starting from
node $v_{0}$ in Fig. 4. Correspondingly, $v_{0}$ first converts $\alpha=0.1$
fraction of initial residue $r(v_{0},v_{0})=d(v_{0})=3.0$ to
$\widehat{\pi}(v_{0},v_{0})=0.3$, and then evenly pushes the remaining residue
(i.e., $2.7$) to each of its out-neighbors, resulting in
$r(v_{0},v_{1})=r(v_{0},v_{2})=r(v_{0},v_{3})=0.9$. After that, nodes
$v_{1},v_{2}$, and $v_{3}$ continue such push operations and lead to
$r(v_{0},v_{4})=r(v_{0},v_{6})=0.81$ for nodes $v_{4},v_{6}$ and
$r(v_{0},v_{5})=r(v_{0},v_{7})=0.405$ for nodes $v_{5},v_{7}$.

In particular, the following invariant (Andersen et al., 2006) holds during
the course of push operations:

(3) $\pi_{d}(v_{i},v_{j})=\widehat{\pi}_{d}(v_{i},v_{j})+\sum_{v_{k}\in
V}\frac{1}{d(v_{k})}\cdot r(v_{i},v_{k})\cdot\pi_{d}(v_{k},v_{j}),$

where $\widehat{\pi}_{d}(v_{i},v_{j})$ is an estimation of
$\pi_{d}(v_{i},v_{j})$ and the other term $\textstyle\sum_{v_{k}\in
V}{\frac{1}{d(v_{k})}\cdot r(v_{i},v_{k})\cdot\pi_{d}(v_{k},v_{j})}$ can be
regarded as the estimation error. Intuitively, an exact $\mathsf{DPPR}$ can be
obtained when the residue of each node is eventually depleted, i.e.,
$r(v_{i},v_{k})=0$ for all ${v_{k}}\in V$. In practice,
$\mathsf{Forward}$-$\mathsf{Push}$ computes approximate $\mathsf{DPPR}$ by
conducting pushes until every residue value is less than a given threshold
$r_{max}$, referred to as the forward residue threshold. When $r_{max}$ is
small, $\mathsf{Forward}$-$\mathsf{Push}$ incurs significant computational
overhead, as a large number of push operations are required to deplete
residues. To address this issue, most of the state-of-the-art methods (Wang et
al., 2017b; Shi et al., 2019; Wang et al., 2019; Lin et al., 2020; Luo et al.,
2019) follow the two-phase paradigm proposed in $\mathsf{FORA}$ (Wang et al.,
2017b). In particular, they first invoke $\mathsf{Forward}$-$\mathsf{Push}$
(Andersen et al., 2006) with early termination conditions to derive rough
approximations of $\mathsf{DPPR}$ values, and then refine results by
exploiting random walk samplings (Fogaras et al., 2005) to estimate the error
term in Eq. (3). To illustrate, consider the r.h.s. graph in Fig. 4. Instead
of always using pushes, $\mathsf{FORA}$-based methods would terminate at nodes
$v_{4}$–$v_{7}$ and simulate random walks from $v_{4}$–$v_{7}$ as per their
residues to probe the far-reaching nodes.

Unfortunately, $\mathsf{FORA}$-based solutions still entail considerable
computational overheads if applied directly to $\mathsf{DPPR}$ approximation
for two reasons. First, although SSPPR approximation solutions can improve the
efficiency of single-source $\mathsf{DPPR}$ computation, we need
$O(k^{\ell+1})$ (up to $n$ in the worst case) single-source $\mathsf{DPPR}$
queries for $O(k^{\ell+1})$ leaf nodes in the specified level-$(\ell+1)$
supernode $\mathcal{S}$, which is costly when $\ell$ is large. Second, most
push operations or random walk samples in such methods are futile in the
context of $\mathsf{DPPR}$ computation. This is due to the fact that these
methods aim to obtain accurate $\mathsf{DPPR}$ estimates of all nodes w.r.t.
the source. However, the majority of visited nodes by such operations are not
in the supernode $\mathcal{S}$ that we are interested in visualizing. Notably,
at level-1, roughly $\frac{n-k}{n}$ of nodes located outside $\mathcal{S}$,
where $k$ is a small integer (e.g., 25) and $n$ can be up to millions. To
illustrate, consider the example in Fig. 5. For simplicity, we assume that
supernode $\mathcal{S}$ is at level-1, and it contains 12 leaf nodes
$v_{0}$–$v_{11}$. As shown in the l.h.s. graph in Fig. 5,
$\mathsf{Forward}$-$\mathsf{Push}$ iteratively performs push operations until
the estimated $\mathsf{DPPR}$ values of all nodes, including $88$ nodes
$v_{12}$–$v_{99}$ outside $\mathcal{S}$, satisfied the desired approximation.

Figure 5.  Bidirectional push in
$\boldsymbol{\mathsf{Tau}}$-$\boldsymbol{\mathsf{Push}}$.

##  4\. $\boldsymbol{\mathsf{Tau}}$-$\boldsymbol{\mathsf{Push}}$ Algorithm

In this section, we present $\mathsf{Tau}$-$\mathsf{Push}$, the efficient
algorithm for estimating level-$\ell$ $\mathsf{PDist}$ via computing
$(\epsilon,\delta)-$approximate level-$\ell$ $\mathsf{DPPR}$. At a high level,
$\mathsf{Tau}$-$\mathsf{Push}$ overcomes the limitations of
$\mathsf{FORA}$-based methods through (i) a filter-refinement paradigm, which
eliminates redundant push operations or random walks without affecting the
accuracy guarantee, and (ii) a grouped push strategy, which reduces the number
of leaf-level invocations from $O(k^{\ell+1})$ to $O(k)$. In what follows, we
first illustrate the main idea of $\mathsf{Tau}$-$\mathsf{Push}$ in Section
4.1, followed by the algorithmic details of two subroutines of
$\mathsf{Tau}$-$\mathsf{Push}$ in Section 4.2. We further provide theoretical
results of $\mathsf{Tau}$-$\mathsf{Push}$ in Section 4.3.

###  4.1. Main Idea and Algorithm

$\mathsf{Tau}$-$\mathsf{Push}$ estimates level-$\ell$ $\mathsf{DPPR}$ values
by pushing in a bidirectional fashion. In particular,
$\mathsf{Tau}$-$\mathsf{Push}$ first performs a small number of forward push
operations from the source $\mathcal{V}_{i}$ to derive an accurate
$\mathsf{DPPR}$ for each target node in the vicinity of $\mathcal{V}_{i}$.
Next, it conducts a handful of pushes reversely along in-neighbors, referred
to as backward push operations, from the rest of target nodes in $\mathcal{S}$
(i.e., the nodes far-reaching from $\mathcal{V}_{i}$), to obtain their
approximate $\mathsf{DPPR}$ values. To explain the backward push, we consider
the r.h.s. graph in Fig. 5. Given $\alpha=0.1$ and node $v_{10}$ with initial
residue $r(v_{10},v_{10})=1$, we will convert $0.1$ fraction of
$r(v_{10},v_{10})$ to its estimated $\mathsf{DPPR}$ and propagate the
remaining $0.9$ to its in-neighbors $v_{5}$ and $v_{6}$, which receive
$\frac{0.9}{d(v_{5})}=0.45$ and $\frac{0.9}{d(v_{6})}=0.9$, respectively. By
combining forward and backward pushes, we can avoid the issue of “pushing too
deeply” mentioned in Section 3.3, and hence, prune excessive pushes/samples
for nodes outside $\mathcal{S}$, e.g., nodes $v_{12}$–$v_{99}$ in Fig. 5. In
other words, $\mathsf{Tau}$-$\mathsf{Push}$ filters out the majority of nodes
whose approximate $\mathsf{DPPR}$ values obtained by
$\mathsf{Forward}$-$\mathsf{Push}$ are sufficiently accurate, and only refines
the $\mathsf{DPPR}$ estimation for each remaining node using backward pushes.

Figure 6. The distributions of $\boldsymbol{\mathsf{DPR}}$ on Youtube.

The linchpin to enabling the aforementioned filter-refinement optimization is
the identification of nodes that requires backward pushes. In relation to
this, we introduce the notion of degree-normalized PageRank ($\mathsf{DPR}$).
For each supernode $\mathcal{V}_{j}$, its $\mathsf{DPR}$ is defined as

(4) $\tau_{j}=\frac{1}{m\cdot|F(\mathcal{V}_{j})|}{\sum_{v_{t}\in
F(\mathcal{V}_{j})}\sum_{v_{k}\in V}{\pi_{d}(v_{k},v_{t})}},$

where $\pi_{d}(v_{k},v_{j})$ is the $\mathsf{DPPR}$ of $v_{j}$ w.r.t. $v_{k}$
and $F(\mathcal{V}_{j})$ signifies the set of leaf nodes in $\mathcal{V}_{j}$.
In particular, when $\mathcal{V}_{j}$ is a leaf node $v_{j}$ (i.e.,
$F(\mathcal{V}_{j})=v_{j}$), its $\mathsf{DPR}$ $\tau_{j}$ is the summation of
$\mathsf{DPPR}$ values pertinent to $v_{j}$, which indicates the global
importance of $v_{j}$ in the entire graph. Building on our theoretical
analysis, if the residue threshold $r_{max}$ used in
$\mathsf{Forward}$-$\mathsf{Push}$ is set properly, the approximate
$\mathsf{DPPR}$ values of nodes $v_{j}$ with $\tau_{j}$ less than the given
$\mathsf{DPR}$ threshold $\tau$ are guaranteed to be
$(\epsilon,\delta)$-approximate (see Lemma 4.1). For example, the r.h.s. graph
in Fig. 5 shows that, given $\tau=0.05$, nodes $v_{1}$–$v_{8}$ and $v_{11}$
can be filtered out as their $\mathsf{DPR}$ values are less than $\tau$, and
hence, we only need to conduct backward pushes from $v_{9}$ and $v_{10}$. We
observe that $\mathsf{DPR}$ values of real-world graphs often follow the power
law distribution, where only a few nodes have large values and the remaining
nodes have nominal values. For instance, as shown in Fig. 6, the
$\mathsf{DPR}$ values of over $99.98\%$ of nodes on the well-known Youtube
graph are less than $0.001$, while the largest $\mathsf{DPR}$ is about
$0.005$. Hence, by checking $\mathsf{DPR}$ and choosing a proper $\tau$, we
can exclude the great majority of nodes in $\mathcal{S}$ for further
refinement, thereby reducing the computational cost. It is worth mentioning
that the $\mathsf{DPR}$ of each leaf node can be efficiently calculated in the
preprocessing stage and used as the input to $\mathsf{Tau}$-$\mathsf{Push}$.

Notice that the supernode $\mathcal{S}$ considered above is a level-$1$
supernode with $k$ leaf nodes. As for any level-$(\ell+1)$ supernode
$\mathcal{S}$ containing $O(k^{\ell+1})$ leaf nodes, we need to invoke
$\mathsf{Forward}$-$\mathsf{Push}$ $O(k^{\ell+1})$ times for the computation
of all-pair level-$\ell$ $\mathsf{DPPR}$ values in $\mathcal{S}$, which is
rather time-consuming when $\ell$ is large. To alleviate this issue, we design
Group Forward-Push (GFP), an improved and optimized
$\mathsf{Forward}$-$\mathsf{Push}$ equipped with a grouped push strategy: it
starts push operations from all leaf nodes in the level-$\ell$ supernode
simultaneously instead of separately. Analogously, we also propose Group
Backward-Push (GBP) for accelerating backward push operations in level-$\ell$
supernodes.

Algorithm. Algorithm 1 shows the pseudo-code of
$\mathsf{Tau}$-$\mathsf{Push}$, which consists of two main phases: GFP and
GBP. Specifically, given a supernode $\mathcal{S}$ and constant $k$,
$\mathsf{Tau}$-$\mathsf{Push}$ starts by setting $\mathsf{DPR}$ threshold
$\tau$ as ${1}/{\sqrt{k\cdot n}}$ and forward residue threshold as

(5) $r_{max}=\frac{\epsilon\cdot\delta}{m\cdot\tau}$

at Lines 1-2. The setting of $\tau$ strikes a good balance between forward and
backward phases, leading to an optimized worst-case time complexity (as
analyzed later in Section 4.3). Next, for each supernode
$\mathcal{V}_{i}\in\mathcal{S}$, $\mathsf{Tau}$-$\mathsf{Push}$ invokes GFP
with residue threshold $r_{max}$ from $\mathcal{V}_{i}$ to derive
$\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})$, a rough estimation of
$\mathsf{DPPR}$ for each supernode $\mathcal{V}_{j}\in\mathcal{S}$ (Lines
3-4). Subsequently, $\mathsf{Tau}$-$\mathsf{Push}$ calculates the residue
threshold $r^{b}_{max}$ used in GBP as per the following equation (Line 5):

(6)
$r^{b}_{max}=\frac{\epsilon\cdot\delta}{\max_{\mathcal{V}_{i}\in\mathcal{S}\backslash\mathcal{V}_{j}}\frac{\sum_{v_{s}\in
F(\mathcal{V}_{i})}{d(v_{s})}}{|F(\mathcal{V}_{i})|}},$

where the denominator signifies the maximum average degree of leaf nodes in
each supernode $\mathcal{V}_{i}$ of $\mathcal{S}$.
$\mathsf{Tau}$-$\mathsf{Push}$ identifies all supernodes $\mathcal{V}_{j}$
satisfying $\mathsf{DPR}$ $\tau_{j}>\tau$ and utilizes GBP with residue
threshold $r^{b}_{max}$ to refine the approximate $\mathsf{DPPR}$ value of
every supernode pair $\mathcal{V}_{i},\mathcal{V}_{j}$ in $\mathcal{S}$ (Lines
6-7). Eventually, for each supernode pair
$\mathcal{V}_{i},\mathcal{V}_{j}\in\mathcal{S}$, the level-$\ell$ approximate
$\mathsf{DPPR}$ is converted to the desired level-$\ell$ approximate
$\mathsf{PDist}$ (Lines 8-9).

Input: Graph $G$, supernode $\mathcal{S}$ and constant $k$.

Output: Estimated $\widehat{\boldsymbol{\Delta}}[i,j],$
$\forall{\mathcal{V}_{i},\mathcal{V}_{j}}\in\mathcal{S}$.

1 Set $\mathsf{DPR}$ threshold $\tau\leftarrow{1}/{\sqrt{k\cdot n}}$;

2 Set forward residue threshold $r_{max}$ by Eq. (5);

3 for  _each supernode $\mathcal{V}_{i}\in\mathcal{S}$_ do

4 $\forall{\mathcal{V}_{j}\in\mathcal{S}},\
\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})\leftarrow$GFP
$(G,\mathcal{S},\mathcal{V}_{i},r_{max})$;

5

6Set backward residue threshold $r^{b}_{max}$ according to Eq. (6);

7 for  _each supernode $\mathcal{V}_{j}\in\mathcal{S}$ such that
$\tau_{j}>\tau$_ do

8 $\forall{\mathcal{V}_{i}\in\mathcal{S}},\
\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})\leftarrow$GBP
$(G,\mathcal{S},\mathcal{V}_{j},r^{b}_{max})$;

9

10for  _each supernode pair $\mathcal{V}_{i},\mathcal{V}_{j}\in\mathcal{S}$_
do

11 Convert $\mathsf{DPPR}$
$\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})$ to $\mathsf{PDist}$
$\widehat{\boldsymbol{\Delta}}[i,j]$ by Eq.(1);

12

Algorithm 1 $\mathsf{Tau}$-$\mathsf{Push}$

Input: Graph $G$, supernode $\mathcal{S}$, source $\mathcal{V}_{i}$, threshold
$r_{max}$.

Output: Estimated $\mathsf{DPPR}$
$\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j}),$
$\forall{\mathcal{V}_{j}}\in\mathcal{S}$.

1 Initialize approximate $\mathsf{DPPR}$
$\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})\leftarrow 0$
$\forall{\mathcal{V}_{j}}\in\mathcal{S}$;

2 Initialize residues
$r(\mathcal{V}_{i},v_{j})\leftarrow\frac{d(v_{j})}{|F(\mathcal{V}_{i})|}$
$\forall{v_{j}}\in F(\mathcal{V}_{i})$;

3 while  _$\exists v_{k}\in V\ \textrm{such that}\ r(\mathcal{V}_{i},v_{k})
>d(v_{k})\cdot r_{max}$_ do

4 if  _$v_{k}$ is in any supernode $\mathcal{V}_{j}\in\mathcal{S}$_ then

5
$\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})\leftarrow\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})+\frac{\alpha\cdot
r(\mathcal{V}_{i},v_{k})}{|F(\mathcal{V}_{j})|}$;

6

7 for  _each out-neighbor ${v_{j}}$ of $v_{k}$_ do

8 $r(\mathcal{V}_{i},v_{j})\leftarrow
r(\mathcal{V}_{i},v_{j})+(1-\alpha)\cdot\frac{r(\mathcal{V}_{i},v_{k})}{d(v_{k})}$;

9

10 $r(\mathcal{V}_{i},v_{k})\leftarrow 0$;

11

Algorithm 2 GFP

###  4.2. GFP and GBP

In the following, we elaborate on the algorithmic details of GFP and GBP used
in $\mathsf{Tau}$-$\mathsf{Push}$.

GFP. Algorithm 2 shows the pseudo-code of GFP. Akin to
$\mathsf{Forward}$-$\mathsf{Push}$, GFP maintains two lists of variables in
the course of pushes from source supernode $\mathcal{V}_{i}$: (i) the
estimated $\mathsf{DPPR}$
$\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})$,
$\forall{\mathcal{V}_{j}}\in\mathcal{S}$, and (ii) the residue
$r(\mathcal{V}_{i},v_{k})$, $\forall{v_{k}}\in V$. Initially, all variables
are set to 0 except that $r(\mathcal{V}_{i},v_{j})$ is set to
$\frac{d(v_{j})}{|F(\mathcal{V}_{i})|}$ for each node $v_{j}$ in the leaf node
set $F(\mathcal{V}_{i})$ of $\mathcal{V}_{i}$ (Lines 1-2). After that, GFP
starts an iterative process to traverse $G$ from nodes with non-zero residues,
i.e., nodes in $F(\mathcal{V}_{i})$. In particular, in each iteration, it
inspects the residue of each node in $V$ to identify a node $v_{k}$ whose
residue is greater than $d(v_{k})\cdot r_{max}$. If such a node $v_{k}$
exists, GFP first adds $\frac{\alpha\cdot
r(\mathcal{V}_{i},v_{k})}{|F(\mathcal{V}_{j})|}$ to the approximate
$\mathsf{DPPR}$ $\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})$, where
$\mathcal{V}_{j}$ is the supernode containing $v_{k}$ (Lines 4-5). Then, it
evenly distributes the remaining $(1-\alpha)$ fraction of residue to the out-
neighbors of $v_{k}$ (Lines 6-7). Afterwards, GFP resets the residue
$r(\mathcal{V}_{i},v_{k})$ to $0$ (Line 8) and proceeds to next iteration.
Lemma 4.1 indicates the correctness of Algorithm 2.

###### Lemma 4.1.

Given a source supernode $\mathcal{V}_{i}\in\mathcal{S}$ and a $\mathsf{DPR}$
threshold $\tau$, by setting $\textstyle{r_{max}}$ as in Eq. (5), GFP returns
$(\epsilon,\delta)-$approximate level-$\ell$ $\mathsf{DPPR}$
$\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})$ for
$\mathcal{V}_{j}\in\mathcal{S}$ with $\mathsf{DPR}$ $\tau_{j}\leq\tau$.

GBP. GBP can be regarded as the backward counterpart of GFP. As shown in
Algorithm 3, GBP initializes residue value $r(v_{i},\mathcal{V}_{j})$ of each
leaf node $v_{i}$ in target supernode $\mathcal{V}_{j}$ to
${1}/{|F(\mathcal{V}_{j})|}$ (Line 2). Distinct from
$\mathsf{Forward}$-$\mathsf{Push}$, GBP conducts the graph traversal from the
target supernode $\mathcal{V}_{j}$, following the incoming edges of each node.
To be more precise, GBP evenly pushes $(1-\alpha)$ fraction of residue
$r(v_{k},\mathcal{V}_{j})$ to the in-neighbors of current node $v_{k}$ (Lines
6-7), rather than out-neighbors in GFP. In addition, another two minor
differences are: (i) the residue threshold $r^{b}_{max}$ is defined as Eq. (6)
(Line 3), and (ii) in each iteration, GBP increases the estimated
$\mathsf{DPPR}$ $\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})$ by
$\frac{\alpha\cdot d(v_{k})\cdot
r(v_{k},\mathcal{V}_{j})}{|F(\mathcal{V}_{i})|}$, where $\mathcal{V}_{i}$ is
the supernode consisting of current node $v_{k}$ (Lines 4-5). Lemma 4.2 proves
the correctness of GBP.

###### Lemma 4.2.

Given a target supernode $\mathcal{V}_{j}\in\mathcal{S}$ and a threshold
$\textstyle{r^{b}_{max}}$ in Eq. (6), GBP returns the
$(\epsilon,\delta)$-approximate level-$\ell$ $\mathsf{DPPR}$
$\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})$ for each source supernode
$\mathcal{V}_{i}\in\mathcal{S}$ and $\mathcal{V}_{i}\neq\mathcal{V}_{j}$.

###  4.3. Theoretical Results

Input: Graph $G$, supernode $\mathcal{S}$, target $\mathcal{V}_{j}$, threshold
$r^{b}_{max}$.

Output: Estimated $\mathsf{DPPR}$
$\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j}),$
$\forall{\mathcal{V}_{i}}\in\mathcal{S}$.

1 Initialize approximate $\mathsf{DPPR}$
$\widehat{\pi}(\mathcal{V}_{i},\mathcal{V}_{j})\leftarrow 0$
$\forall{\mathcal{V}_{i}}\in\mathcal{S}$;

2 Initialize residues
$r(v_{i},\mathcal{V}_{j})\leftarrow{1}/{|F(\mathcal{V}_{j})|},$
$\forall{v_{i}}\in F(\mathcal{V}_{j})$;

3 while  _$\exists v_{k}\in V\ \textrm{such that}\ r(v_{k},\mathcal{V}_{j})
>r^{b}_{max}$_ do

4 if  _$v_{k}$ is in any supernode $\mathcal{V}_{i}\in\mathcal{S}$_ then

5
$\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})\leftarrow\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})+\frac{\alpha\cdot
d(v_{k})\cdot r(v_{k},\mathcal{V}_{j})}{|F(\mathcal{V}_{i})|}$;

6

7 for  _each in-neighbor $v_{i}$ of $v_{k}$_ do

8 $r(v_{i},\mathcal{V}_{j})\leftarrow
r(v_{i},\mathcal{V}_{j})+(1-\alpha)\cdot\frac{r(v_{k},\mathcal{V}_{j})}{d(v_{i})}$;

9

10 $r(v_{k},\mathcal{V}_{j})\leftarrow 0$;

11

Algorithm 3 GBP

Correctness. Combining Lemmata 4.1 and 4.2 leads to Theorem 4.3, which
establishes the correctness of $\mathsf{Tau}$-$\mathsf{Push}$ (Algorithm 1).

###### Theorem 4.3.

For any user-selected supernode $\mathcal{S}$ and threshold $\tau$, by setting
$r_{max}$ and $r^{b}_{max}$ as in Algorithm 1, respectively, Algorithm 1
returns $(\epsilon,\delta)-$approximate level-$\ell$ $\mathsf{DPPR}$
$\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})$ for
$\mathcal{V}_{i},\mathcal{V}_{j}\in\mathcal{S}$ and
$\mathcal{V}_{i}\neq\mathcal{V}_{j}$.

Time complexity. The worst-case time complexity of
$\mathsf{Tau}$-$\mathsf{Push}$ is $\textstyle{O\left(\frac{k\cdot n\cdot
m\cdot\tau}{\epsilon\cdot\delta}+\frac{m}{\tau\cdot\epsilon\cdot\delta}\right)}$.
By setting $\textstyle\tau={1}/{\sqrt{k\cdot n}}$, the above complexity is
minimized to $\textstyle O\left(\frac{k\cdot m}{\epsilon}\cdot\sqrt{k\cdot
n}\right)$. By employing GFP only, the worst-case complexity is
$O\left(\frac{k^{2}\cdot n\cdot m}{\epsilon}\right)$, which is $\sqrt{k\cdot
n}$ times slower than $\mathsf{Tau}$-$\mathsf{Push}$. The expected complexity
of $\mathsf{Tau}$-$\mathsf{Push}$ for a randomly selected supernode
$\mathcal{S}$ is
$O\left(\textstyle\sum_{\mathcal{V}_{i}\in\mathcal{S}}\frac{d(\mathcal{V}_{i})}{|F(\mathcal{V}_{i})|}\cdot\frac{k\cdot
m}{\epsilon\cdot\delta\cdot n}\right)$.

Indexing scheme. We first store $O(n)$ $\mathsf{DPR}$ values as the index,
which can be efficiently pre-computed in a similar way to global PageRank by
setting the $k$-th entry in the initial global PageRank as
$\frac{d(v_{k})}{m}$. Notice that GBP is only conducted from target
$\mathcal{V}_{j}$ with $\tau_{j}>\tau={1}/{\sqrt{k\cdot n}}$ and is
independent of the query supernode $\mathcal{S}$. Hence, the index space is
$O\left(k\cdot\sqrt{k\cdot n}\right)$ since GBP estimates $\mathsf{DPPR}$ of
$O\left(\sqrt{k\cdot n}\right)$ target nodes w.r.t. $O(k)$ source supernodes
in $\mathcal{S}$. Overall, the index space of $\mathsf{Tau}$-$\mathsf{Push}$
is $O\left(n+k\cdot\sqrt{k\cdot n}\right)$.

$\boldsymbol{\mathsf{Tau}}$-$\boldsymbol{\mathsf{Push}}$ vs.
$\boldsymbol{\mathsf{FORA}}$. We compare $\mathsf{Tau}$-$\mathsf{Push}$ with
$\mathsf{FORA}$ in terms of time complexity and index space for a randomly
selected supernode $\mathcal{S}$. As summarized in Table 2,
$\mathsf{Tau}$-$\mathsf{Push}$ improves the time complexity of $\mathsf{FORA}$
by $\frac{n\cdot\sqrt{k\cdot m}}{k^{3}\cdot\log{n}}$, where $k$ is the number
of supernodes/nodes to be visualized and is usually small as discussed in
Section 2.2. For example, $\mathsf{Tau}$-$\mathsf{Push}$ is about four orders
of magnitude faster than $\mathsf{FORA}$ on the Youtube graph with 1 million
nodes and 3 million edges. Besides that, we observe that the indexing space of
$\mathsf{FORA}$ is usually $3$–$5\times$ larger than that of
$\mathsf{Tau}$-$\mathsf{Push}$ in the experiments.

Table 2. Index space and time complexity of methods for approximate level-$\boldsymbol{\ell}$ $\boldsymbol{\mathsf{PDist}}$ computation. | $\mathsf{FORA}$ |  $\mathsf{Tau}$-$\mathsf{Push}$
---|---|---
Indexing space | $O\left(\frac{\log{n}\cdot\sqrt{k\cdot m}}{\epsilon}\right)$ | $O\left(n+k\cdot\sqrt{n\cdot k}\right)$
Time complexity | $O\left(\frac{m\cdot\sqrt{k\cdot m}}{\epsilon}\right)$ | ${O\left(\frac{k^{3}\cdot(\log{n})^{2}}{\epsilon}\right)}$
Figure 7. Procedure of $\boldsymbol{\mathsf{PPRviz}}$.

##  5\. $\boldsymbol{\mathsf{PPRviz}}$

This section presents $\mathsf{PPRviz}$, our framework for static graph
visualization. Fig. 7 illustrates the procedure of $\mathsf{PPRviz}$, which
consists of two phases, i.e., (i) preprocessing and (ii) interactive
visualization. In the preprocessing phase, it first constructs a supergraph
hierarchy for the given graph $G$, then builds the index for the proposed
$\mathsf{Tau}$-$\mathsf{Push}$. It is worth noting that the preprocessing
phase is conducted only once for any queries on the given $G$. In the
interactive visualization phase, $\mathsf{PPRviz}$ contains two stages, namely
$\mathsf{PDist}$ matrix computation and position matrix embedding. As the
index schema of $\mathsf{Tau}$-$\mathsf{Push}$ has been explained in Section
4.3, we focus on illustrating the remaining stages as follows.

  * •

Supergraph hierarchy construction: $\mathsf{PPRviz}$ first constructs a
supergraph hierarchy of the input graph in the preprocessing step (Abello et
al., 2006; Shi et al., 2009; Archambault et al., 2008). Take Fig. 7(a) as an
example. The bottom layer is the input graph, whose non-overlapping node
partitions are organized as level-1 supernodes in the middle layer. Similarly,
the clustering procedure is repeated to generate the top layer. We employ the
$\mathsf{Louvain}$ algorithm (Blondel et al., 2008) to construct the
supergraph hierarchy. Specifically, $\mathsf{Louvain}$ first treats all
level-$\ell$ supernodes and their relationships as a new graph and assigns
each supernode to a stand-alone partition. After that, it builds the
partitions of level-$\ell$ supernodes (i.e., supernodes at level-$(\ell+1)$)
by iteratively moving each supernode to the neighbor’s partition with maximum
modularity improvement, where the moduarlity (Newman, 2006) measures the
density of links inside partitions as compared to links between partitions.
Following the size requirement in Section 2.2, we adapt $\mathsf{Louvain}$
under the constraint that each supernode $\mathcal{S}$ (resp. the coarsest
supergraph) should have at most $k$ children (resp. supernodes) and call this
adaption $\mathsf{Louvain+}$. Note that $k$ can be configured by users
according to their needs.

  * •

$\boldsymbol{\mathsf{PDist}}$ matrix computation: During interactive
visualization, a user can select a level-$(\ell+1)$ supernode $\mathcal{S}$
(marked by an arrow in Fig. 7(b)). To visualize the intra-structure of
$\mathcal{S}$, i.e., the shaded area in the middle layer, $\mathsf{PPRviz}$
leverages $\mathsf{Tau}$-$\mathsf{Push}$ in Algorithm 1 to calculate the
$\mathsf{PDist}$ matrix $\boldsymbol{\Delta}\in\mathbb{R}^{k\times k}$ for the
$k$ children of $S$ (Fig. 7(c)), which reflects the theoretical graph distance
between the children by utilizing information of the related nodes in the
input graph, i.e., the shaded area in the bottom layer of Fig. 7(b).

  * •

Position matrix embedding: Given the $\mathsf{PDist}$ matrix
$\boldsymbol{\Delta}\in\mathbb{R}^{k\times k}$, $\mathsf{PPRviz}$ converts it
into a position matrix $\mathbf{X}\in\mathbb{R}^{k\times 2}$ (see Fig. 7(d)),
where $\mathbf{X}[i]\in\mathbb{R}^{2}$ represents the two-dimensional
coordinate of the $i$-th child node on the screen. In particular, the position
matrix embedding step solves the following optimization problem (Gansner et
al., 2004):

(7) $\arg\min\limits_{\mathbf{X}}\
L(\mathbf{X}|\boldsymbol{\Delta})=\sum\limits_{i<j}\left(1-\frac{||\mathbf{X}[i]-\mathbf{X}[j]||}{\boldsymbol{\Delta}[i,j]}\right)^{2}.$

Intuitively, it aims to ensure that the Euclidean distance
$||\mathbf{X}[i]-\mathbf{X}[j]||$ derived from the position matrix
$\mathbf{X}$ is close to the $\mathsf{PDist}$ $\boldsymbol{\Delta}[i,j]$.
Towards this end, $\mathsf{PPRviz}$ employs the standard method for solving
Eq. (7), namely, the stress majorization technique (Gansner et al., 2004). The
time complexity of this method is $O(k^{3})$ (Gansner et al., 2004), which is
insignificant as $k$ is usually small to avoid visual clutter (Huang et al.,
2009).

Applications and future works. The proposed framework $\mathsf{PPRviz}$ is not
limited to multi-level visualization and is applicable for visualizing static
homogeneous graphs in other scenarios. For example, $\mathsf{PPRviz}$ can
visualize the entire graph or the subgraph returned by the graph query in a
single-level fashion (Bhowmick et al., 2020), where $\mathsf{PPRviz}$ skips
the supergraph hierarchy construction stage and sets $k=n$ for the
visualization phase. Furthermore, $\mathsf{PPRviz}$ can be employed for
incremental exploration (Herman et al., 2000), where users can move a focal
area over the entire graph to explore the subgraph they are interested in.
Notice that $\mathsf{PPRviz}$ can easily cope with the small dynamic graphs
(including subgraphs, motifs, etc.) returned by database queries because our
proposed $\mathsf{Tau}$-$\mathsf{Push}$ algorithm is highly efficient and can
be real-time responsive when a new visualization request is made. Regarding
the scenarios on large dynamic or attributed graphs, even though existing
solutions (Zhuang et al., 2019; Wang et al., 2017a) are applicable for the
supergraph hierarchy construction and position embedding stages of
$\mathsf{PPRviz}$, the proposed $\mathsf{PDist}$ or corresponding estimation
algorithm $\mathsf{Tau}$-$\mathsf{Push}$ fails to extend to these scenarios
trivially. In particular, under the dynamic setting, it is still unclear how
to efficiently estimate the proposed $\mathsf{PDist}$ with a rigorous
theoretical accuracy guarantee. In addition, $\mathsf{PPRviz}$ can be extended
to visualize attributed or knowledge graphs by treating node/edge attributes
as additional nodes (Xu et al., 2009). However, such a method requires a new
distance measure considering both topologies and attributes. These challenges
motivate us to design new approaches in future works.

##  6\. Related Work

Graph visualization. Conventional single-level graph visualization methods
have been extensively studied (Hu and Shi, 2015; Gibson et al., 2013; Von
Landesberger et al., 2011; Herman et al., 2000) and can be classified into two
main categories: (i) _force-directed methods_ , e.g., $\mathsf{FR}$
(Fruchterman and Reingold, 1991), $\mathsf{LinLog}$ (Noack, 2005),
$\mathsf{ForceAtlas}$ (Jacomy et al., 2014) and others (Eades, 1984; Martin et
al., 2011; Jacomy et al., 2014; Chung and Tsiatas, 2012); and (ii) _stress
methods_ , e.g., $\mathsf{CMDS}$ (Gansner et al., 2004), $\mathsf{PMDS}$
(Brandes and Pich, 2006) and others (Torgerson, 1952; Kamada et al., 1989;
Gansner et al., 2012; Meyerhenke et al., 2017). In particular, force-directed
methods model a graph as a force system, where adjacent nodes attract each
other and all nodes repulse each other. The position matrix is derived by
minimizing the composite forces in the entire system. Stress methods utilize
the shortest distance as the node distance to guide node placement. They embed
the shortest distance matrix into a position matrix by optimization
techniques, e.g., gradient descent (Gansner et al., 2012) and stress
majorization (Gansner et al., 2004). To boost efficiency, many optimizations
are incorporated, e.g., grid-based partitioning (Fruchterman and Reingold,
1991; Martin et al., 2011), quad-tree (Noack, 2005; Jacomy et al., 2014), and
dimensionality reduction (Brandes and Pich, 2006). Moreover, as surveyed by
(Goyal and Ferrara, 2018), graph embedding methods, e.g., $\mathsf{GFactor}$
(Ahmed et al., 2013), $\mathsf{SDNE}$ (Wang et al., 2016a), $\mathsf{LapEig}$
(Belkin and Niyogi, 2003), $\mathsf{LLE}$ (Roweis and Saul, 2000) and
$\mathsf{Node2vec}$ (Grover and Leskovec, 2016), can also be applied for
visualization by treating the embedding matrix with dimension being 2 as the
position matrix (Perozzi et al., 2014; Tang et al., 2015; Goyal and Ferrara,
2018). Multi-level methods (Meyerhenke et al., 2017; Martin et al., 2011;
Rodrigues et al., 2015; Shi et al., 2009; Abello et al., 2006; Archambault et
al., 2008; Hu, 2005) mainly focus on designing graph clustering algorithms,
and the single-level methods are directly employed to layout each cluster. For
example, $\mathsf{OpenOrd}$ (Martin et al., 2011) clusters nodes based on
their Euclidean distances in the graph layout and uses $\mathsf{FR}$ for
visualization; $\mathsf{KDraw}$ (Meyerhenke et al., 2017) applies label
propagation for clustering and uses (Gansner et al., 2012) for visualization;
GrouseFlocks (Archambault et al., 2008) groups nodes based on certain graph
structures. Compared with our $\mathsf{PDist}$ distance matrix, the distance
measures employed in existing methods fail to preserve the topological
information comprehensively and hence dampen visualization quality.
Specifically, force-directed methods only consider the direct links in the
graph. Stress methods consider the shortest path from the source node to the
target node but ignore other intricate paths. A related work (Chung and
Tsiatas, 2012) uses the force-directed method for visualization after
determining the edge weights by PPR; however, this method is still inherently
a force-directed method, hence suffering from the corresponding limitations.

PPR computation. The efficient computation of PPR has been extensively studied
(Fogaras et al., 2005; Andersen et al., 2006; Wang et al., 2017b; Jung et al.,
2017; Wang et al., 2016b; Lofgren et al., 2016; Lofgren and Goel, 2013; Shin
et al., 2015; Wu et al., 2021; Shi et al., 2019; Yang et al., 2020; Wang et
al., 2020; Yoon et al., 2018; Hou et al., 2021; Lin et al., 2020; Wang et al.,
2019). Among these works, BEAR (Shin et al., 2015) and BePI (Jung et al.,
2017) improve the power iteration method (Page et al., 1999) and achieve high
efficiency by indexing several large matrices. However, the index space limits
their applicability to large graphs. BiPPR (Lofgren et al., 2016) and HubPPR
(Wang et al., 2016b) combine random walks (Fogaras et al., 2005) with
$\mathsf{Backward}$-$\mathsf{Push}$ (Lofgren and Goel, 2013), and are
subsequently improved by $\mathsf{FORA}$ (Wang et al., 2017b). However,
$\mathsf{FORA}$ and its improved solutions (Hou et al., 2021; Wu et al., 2021;
Wang et al., 2019; Lin et al., 2020) suffer from numerous push operations and
ineffective sample problems as illustrated in Section 3.2. This is because our
level-$\ell$ $\mathsf{PDist}$ computation aims at the aggregated PPRs between
two clusters, which is essentially different from PPR computation for a single
source node. Another line of work computes PPR using the idea of particle
filtering (Gallo et al., 2020), which performs a deterministic graph traversal
from a set of source nodes. Nevertheless, it is non-trivial to determine the
initial particle distribution for level-$\ell$ $\mathsf{DPPR}$, and it does
not offer quality guarantees. In contrast, $\mathsf{Tau}$-$\mathsf{Push}$ can
significantly outperform existing visualization and PPR solutions in
efficiency with quality guarantees.

##  7\. Experiment Evaluation

We introduce the experiment settings in Section 7.1. Section 7.2 evaluates the
visualization quality of our $\mathsf{PDist}$ and the competing methods.
Sections 7.3 and 7.4 compare the efficiency of $\mathsf{Tau}$-$\mathsf{Push}$
against the visualization and PPR-based solutions. Interested readers are
referred to Appendix A for additional results and analysis on visualization
and $\mathsf{Tau}$-$\mathsf{Push}$’s variants.

###  7.1. Experiment Settings

Competitors and parameter settings. We compare $\mathsf{PPRviz}$ with 13
representative graph visualization methods from different categories: (i) 3
single-level force-directed methods: $\mathsf{FR}$ (Fruchterman and Reingold,
1991), $\mathsf{LinLog}$ (Noack, 2005), $\mathsf{ForceAtlas}$ (Jacomy et al.,
2014); (ii) 2 single-level stress methods: $\mathsf{CMDS}$ (Gansner et al.,
2004), $\mathsf{PMDS}$ (Brandes and Pich, 2006); (iii) 5 single-level graph
embedding methods: $\mathsf{GFactor}$ (Ahmed et al., 2013), $\mathsf{SDNE}$
(Wang et al., 2016a), $\mathsf{LapEig}$ (Belkin and Niyogi, 2003),
$\mathsf{LLE}$ (Roweis and Saul, 2000), $\mathsf{Node2vec}$ (Grover and
Leskovec, 2016); (iv) an SimRank-based adaptation mentioned in Section 3.1;
(v) 2 multi-level methods: $\mathsf{OpenOrd}$ (Martin et al., 2011) and
$\mathsf{KDraw}$ (Meyerhenke et al., 2017). We follow the parameter settings
of all competitors as recommended in their respective papers. For
$\mathsf{PPRviz}$, we set the maximum number of nodes in a cluster to 25
(i.e., $k=25$) as suggested in (Huang et al., 2009). For a fair comparison, we
follow (Archambault et al., 2008; Rodrigues et al., 2015) and modify
$\mathsf{OpenOrd}$ and $\mathsf{KDraw}$ such that only the partial view of the
clusters $\mathcal{S}$ in the zoom-in path is visualized. Since
$\mathsf{OpenOrd}$ does not allow cluster size constraint and $\mathsf{KDraw}$
employs a complicated method to determine cluster size, we set the maximum
number of supernodes in the coarsest supergraph (instead of all levels) to
$k$. We observe that $\mathsf{PPRviz}$ usually shows more nodes than
$\mathsf{OpenOrd}$ and $\mathsf{KDraw}$ in a visualization, and hence the
efficiency of $\mathsf{PPRviz}$ is not caused by processing fewer nodes.
Additionally, we compare our proposed $\mathsf{Tau}$-$\mathsf{Push}$ against 4
PPR approximation solutions $\mathsf{PI}$ (Page et al., 1999), $\mathsf{FORA}$
(Wang et al., 2017b), $\mathsf{FORA+}$ (Wang et al., 2019) and
$\mathsf{ResAcc}$ (Lin et al., 2020). For all methods, we set $\epsilon=1-1/e$
and $\delta=1/(10k)$ by default. For $\mathsf{FORA}$-based competitors
$\mathsf{FORA}$, $\mathsf{FORA+}$, and $\mathsf{ResAcc}$, we set the initial
residue $r(v_{i},v_{i})=d(v_{i})$ for the source each $v_{i}$ and follow the
settings of other parameters as suggested in the original papers, where the
correctness of $\mathsf{PDist}$ estimation is still satisfied. The experiment
source code and the implementation of $\mathsf{PPRviz}$ are available at
https://github.com/jeremyzhangsq/PPRviz-reproducibility/.

Table 3. Dataset statistics (${K\\!=\\!10^{3},M\\!=\\!10^{6},B\\!=\\!10^{9}}$) Dataset | $n$ | $m$ | Description
---|---|---|---
TwEgo | 23 | 52 |  Ego network(Leskovec and Krevl, 2014)
FbEgo | 52 | 146 |  Ego network(Leskovec and Krevl, 2014)
Wiki-ii | 186 | 632 |  Authorship network(Kunegis, 2013)
Physician | 241 | 1.8K |  Social network(Kunegis, 2013)
FilmTrust | 874 | 2.6K |  User trust network(Kunegis, 2013)
SciNet | 1.5K | 5.4K |  Collaboration network(Kunegis, 2013)
Amazon | 334.9K | 1.9M |  Product network (Leskovec and Krevl, 2014)
Youtube | 1.1M | 6.0M |  Social network (Leskovec and Krevl, 2014)
Orkut | 3.1M | 234.4M |  Social network (Leskovec and Krevl, 2014)
DBLP | 5.4M | 17.2M |  Collaboration network (Kunegis, 2013)
It-2004 | 41.3M | 2.3B |  Crawled network (Boldi and Vigna, 2004)
Twitter | 41.7M | 3.0B |  Social network (Kwak et al., 2010)

Datasets and performance metrics. We use the 12 real-world graphs in Table 3
for the experiments. We generate visualizations in a single-level fashion on 6
smaller graphs, and use ND and ULCV to evaluate the visualization quality of
$\mathsf{PPRviz}$ and the competitors. For a fair comparison, we follow
NetworkX (Hagberg et al., 2008) and normalize each layout to the same scale.
The 6 larger graphs are used to evaluate visualization efficiency, on which we
report the response time and total preprocessing time. For the single-level
methods, the response time is the time to visualize the entire graph. For
$\mathsf{PPRviz}$ and the multi-level methods, the response time is the
average visualization time for the children of each supernode over 100 random
zoom-in paths. Each path starts with the supergraph on the highest level
(corresponds to the entire graph) and randomly selects a supernode in each
level until reaching level-$0$ (i.e., the original graph) to simulate
interactive exploration. The preprocessing time is the time taken before
visualization. We terminate a method if its response time (resp. preprocessing
time) exceeds 1000 seconds (resp. 12 hours). All experiments are conducted on
a Linux machine with Intel Xeon(R) Gold<EMAIL_ADDRESS>CPU and 80GB RAM in
single-thread mode. Note that the memory utilized by $\mathsf{PPRviz}$ is
comparable to that used by storing the input graph.

Table 4. ND of $\boldsymbol{\mathsf{PPRviz}}$ and the baselines, the best in
bold and the second best in italic, $\boldsymbol{\infty}$ indicates infinity.

| $\mathsf{PPRviz}$ |  $\mathsf{OpenOrd}$/$\mathsf{FR}$ | $\mathsf{LinLog}$ | $\mathsf{ForceAtlas}$ | $\mathsf{CMDS}$ | $\mathsf{PMDS}$ | $\mathsf{GFactor}$ | $\mathsf{SDNE}$ | $\mathsf{LapEig}$ | $\mathsf{LLE}$ | $\mathsf{Node2vec}$ | $\mathsf{SimRank}$
---|---|---|---|---|---|---|---|---|---|---|---|---
TwEgo | 2.1E+02 | 1.2E+02 | 1.1E+03 | 1.8E+03 | 1.2E+03 | $\infty$ | 3.1E+08 | $\infty$ | $\infty$ | 4.6E+02 | 1.1E+04 | 5.2E+02
FbEgo | 2.4E+03 | 1.1E+03 | 9.5E+03 | 1.3E+04 | 2.0E+04 | $\infty$ | 3.6E+12 | $\infty$ | $\infty$ | 3.9E+07 | 1.2E+05 | 6.2E+03
Wiki-ii | 2.7E+04 | 2.7E+04 | 1.4E+05 | 8.1E+04 | 4.9E+04 | $\infty$ | 9.2E+11 | $\infty$ | $\infty$ | 7.5E+29 | 2.5E+06 | 2.7E+04
Physician | 6.7E+04 | 8.7E+04 | 7.6E+05 | 8.2E+05 | 1.5E+05 | $\infty$ | 2.5E+10 | $\infty$ | $\infty$ | 4.0E+09 | 9.4E+07 | 1.1E+05
FilmTrust | 9.1E+05 | 7.1E+06 | 3.2E+08 | 1.4E+07 | $\infty$ | $\infty$ | 1.2E+17 | $\infty$ | $\infty$ | 1.4E+10 | 9.6E+07 | 2.9E+06
SciNet | 2.0E+06 | 6.5E+12 | 2.3E+09 | 1.9E+08 | 9.9E+12 | $\infty$ | 1.1E+17 | $\infty$ | $\infty$ | $\infty$ | 6.6E+07 | 2.2E+06

Table 5. ULCV of $\boldsymbol{\mathsf{PPRviz}}$ and the baselines, the best in
bold and the second best in italic, “-” indicates undefined.

| $\mathsf{PPRviz}$ |  $\mathsf{OpenOrd}$/$\mathsf{FR}$ | $\mathsf{LinLog}$ | $\mathsf{ForceAtlas}$ | $\mathsf{CMDS}$ | $\mathsf{PMDS}$ | $\mathsf{GFactor}$ | $\mathsf{SDNE}$ | $\mathsf{LapEig}$ | $\mathsf{LLE}$ | $\mathsf{Node2vec}$ | $\mathsf{SimRank}$
---|---|---|---|---|---|---|---|---|---|---|---|---
TwEgo | 0.22 | 0.35 | 0.57 | 0.37 | 0.40 | 0.23 | 0.45 | 1.96 | 1.15 | 0.46 | 0.80 | 0.84
FbEgo | 0.39 | 0.42 | 0.67 | 0.49 | 0.46 | 0.45 | 0.91 | 0.94 | 0.98 | 0.77 | 0.96 | 0.75
Wiki-ii | 0.35 | 0.41 | 1.09 | 0.64 | 0.62 | 0.78 | 0.62 | 0.94 | 1.04 | 1.27 | 0.86 | 0.53
Physician | 0.45 | 0.53 | 0.90 | 0.55 | 0.80 | 0.47 | 0.95 | 1.67 | 1.02 | 0.77 | 1.41 | 0.53
FilmTrust | 0.48 | 0.54 | 1.99 | 0.96 | 1.05 | 0.69 | 0.64 | 1.31 | 1.70 | 0.87 | 0.89 | 1.78
SciNet | 0.34 | 0.77 | 4.70 | 1.52 | 1.74 | 0.74 | 0.86 | 1.72 | 1.26 | - | 1.32 | 1.98

###  7.2. Visualization Quality

We evaluate the visualization quality of $\mathsf{PPRviz}$ and the competitors
quantitatively via two popular aesthetic metrics, and qualitatively via a user
study and a case study on 6 smaller graphs.

####  7.2.1. Aesthetic Metrics

We report the ND and ULCV scores of all approaches in Table 4 and Table 5,
respectively. Since $\mathsf{OpenOrd}$ applies $\mathsf{FR}$ to visualize each
supergraph, we treat them as one method and report their results in one
column. The results of $\mathsf{KDraw}$ are omitted as it fails to process
graphs with multiple connected components. We use “-” and $\infty$ to indicate
undefined and infinity scores, respectively. Table 4 shows that
$\mathsf{PPRviz}$ consistently outperforms the competitors in ND on all graphs
except TwEgo and FbEgo, where $\mathsf{PPRviz}$ has comparable performance to
the best method $\mathsf{FR}$. Note that $\mathsf{FR}$ achieves the smallest
ND scores on TwEgo and FbEgo because it places nodes of the largest connected
component far apart from each other, which causes the edge distortion issue.
In particular, the ND scores of $\mathsf{ForceAtlas}$, $\mathsf{FR}$ and
$\mathsf{LinLog}$ are 5, 2, and 3 orders of magnitude larger than
$\mathsf{PPRviz}$ on SciNet, respectively. Regarding stress methods, we find
that $\mathsf{CMDS}$ and $\mathsf{PMDS}$ yield infinite ND scores, indicating
severe node overlapping issues. This is because they use the shortest distance
between two nodes as the node distance, which only takes a few discrete values
and thus fails to distinguish from different node pairs. Furthermore,
$\mathsf{PMDS}$ computes the position of a non-pivot node as the weighted
combination of its connected pivot nodes. Thus, degree-one non-pivot nodes
connected to the same pivot will share the same position. The graph embedding
methods, especially $\mathsf{SDNE}$ and $\mathsf{LapEig}$, have worse ND
scores than $\mathsf{PPRviz}$ and other competitors, as embedding-based
methods are specially designed for machine learning tasks without considering
visualization quality. From Table 5, we can see that $\mathsf{PPRviz}$ always
performs the best in ULCV. For instance, on SciNet, $\mathsf{PPRviz}$ is
14$\times$ better than $\mathsf{LinLog}$. The superior performance of
$\mathsf{PPRviz}$ is attributed to our carefully designed $\mathsf{PDist}$.

$\mathsf{PPRviz}$$\mathsf{CMDS}$$\mathsf{FR}$$\mathsf{Node2vec}$$\mathsf{SimRank}$

$1$$2$$3$$4$$5$$10^{0}$$10^{1}$$10^{2}$rankfrequency (a)

$1$$2$$3$$4$$5$$10^{0}$$10^{1}$$10^{2}$rankfrequency (b)

Figure 8. Results of T1 and T2, frequency of selected ranking. Table 6. Results of T3, frequency of being selected. |  $\mathsf{Tau}$-$\mathsf{Push}$ | $\mathsf{PI}$ | No difference
---|---|---|---
Frequency | 54 | 43 | 83
|  |  |  |  |
---|---|---|---|---|---
(a) $\mathsf{PPRviz}$ (Ours) |  (b) $\blacklozenge$ $\mathsf{ForceAtlas}$ (Jacomy et al., 2014) |  (c) $\blacklozenge$ $\mathsf{LinLog}$ (Noack, 2005) |  (d) $\blacklozenge$ $\mathsf{FR}$ (Fruchterman and Reingold, 1991) |  (e) $\blacktriangle$ $\mathsf{CMDS}$ (Gansner et al., 2004) |  (f) $\blacktriangle$ $\mathsf{PMDS}$ (Brandes and Pich, 2006)
|  |  |  |  |
(g) $\star$ $\mathsf{GFactor}$ (Ahmed et al., 2013) |  (h) $\star$ $\mathsf{SDNE}$ (Wang et al., 2016a) |  (i) $\star$ $\mathsf{LapEig}$ (Belkin and Niyogi, 2003) |  (j) $\star$ $\mathsf{LLE}$ (Roweis and Saul, 2000) |  (k) $\star$ $\mathsf{Node2vec}$ (Grover and Leskovec, 2016) |  (l) $\mathsf{SimRank}$ (Jeh and Widom, 2002)
Figure 9. Visualization results and aesthetic metrics for the TwEgo graph: force-directed methods are marked with $\blacklozenge$; stress methods are marked with $\blacktriangle$; graph embedding methods are marked with $\star$. |
---|---
(a) $\mathsf{PPRviz}$ (Ours) |  (b) $\blacklozenge$ $\mathsf{FR}$ (Fruchterman and Reingold, 1991)
Figure 10. Visualization of $\boldsymbol{\mathsf{PPRviz}}$ and $\boldsymbol{\mathsf{FR}}$ on Wiki-ii. |
---|---
(a) $\mathsf{PPRviz}$ (Ours) |  (b) $\blacklozenge$ $\mathsf{FR}$ (Fruchterman and Reingold, 1991)
Figure 11. Visualization of $\boldsymbol{\mathsf{PPRviz}}$ and
$\boldsymbol{\mathsf{FR}}$ on FilmTrust.

$\mathsf{PPRviz}$$\mathsf{OpenOrd}$$\mathsf{KDraw}$$\mathsf{PMDS}$$\mathsf{Node2vec}$

$10^{-2}$$10^{0}$$10^{3}$time (sec) (a)

$10^{-2}$$10^{0}$$10^{3}$time (sec) (b)

$10^{-2}$$10^{0}$$10^{3}$time (sec) (c)

$10^{-2}$$10^{0}$$10^{3}$time (sec) (d)

$10^{-2}$$10^{0}$$10^{3}$time (sec)$\boldsymbol{\star}$ (e)

$10^{-2}$$10^{0}$$10^{3}$time (sec)$\boldsymbol{\star}$$\boldsymbol{\star}$
(f)

Figure 12. Response time of selected methods ($\star$ indicates failure to
finish preprocessing within 12 hours).

$10^{-2}$$10^{0}$$10^{3}$$12h$time (sec) (g)

$10^{-2}$$10^{0}$$10^{3}$$12h$time (sec) (h)

$10^{-2}$$10^{0}$$10^{3}$$12h$time (sec) (i)

$10^{-2}$$10^{0}$$10^{3}$$12h$time (sec) (j)

$10^{-2}$$10^{0}$$10^{3}$$12h$time (sec) (k)

$10^{-2}$$10^{0}$$10^{3}$$12h$time (sec) (l)

Figure 13. Preprocessing time of the multi-level methods:
$\boldsymbol{\mathsf{PPRviz}}$, $\boldsymbol{\mathsf{OpenOrd}}$ and
$\boldsymbol{\mathsf{KDraw}}$.

####  7.2.2. User Study

In the second set of experiments, we conduct a user study to evaluate the
visualization quality of $\mathsf{PPRviz}$. This study aims to answer two
questions: (i) does $\mathsf{PPRviz}$ output better visualization results than
the competitors, and (ii) does the approximate level-$\ell$ $\mathsf{PDist}$
computation in $\mathsf{PPRviz}$ affect visualization quality from the
perspective of human observers? We recruited 30 participants with 6 females
and 24 males, among which 28 individuals are aged 20 to 30 and 2 individuals
are aged 30 to 40.

To answer the first question, we generate 6 groups of visualizations, each of
which is obtained on one of the 6 small graphs using $\mathsf{PPRviz}$ and 4
representative competitors, including $\mathsf{FR}$, $\mathsf{CMDS}$,
$\mathsf{Node2vec}$, and $\mathsf{SimRank}$, that achieve relatively good
performance in Section 7.2.1. In each group, the 5 visualizations generated by
different methods are randomly shuffled before presenting to the participants.
Following the assessment paradigm in graph drawing (Lee et al., 2006; Du et
al., 2017; Wu et al., 2016), the participants are asked to rank the
visualizations in terms of readability and cluster structure, which are
identified as two paramount tasks by (Gibson et al., 2013; Battista et al.,
1998) and are described as follows.

  * •

Task 1 (T1): rank the 5 visualizations in each group from the highest (1) to
the lowest readability (5), where high readability means that the graph
elements are well displayed.

  * •

Task 2 (T2): rank the 5 visualizations in each group from the best (1) to the
worst (5) in terms of the structure layout, where a good layout means that
clusters and strongly connected nodes can be clearly observed.

To answer the second question, we compare the visualizations generated by
employing $\mathsf{Tau}$-$\mathsf{Push}$ in $\mathsf{PPRviz}$ with those by
employing the near-exact solution $\mathsf{PI}$ in $\mathsf{PPRviz}$. Since
$\mathsf{PI}$ does not scale to large graphs, we consider two small graphs:
FilmTrust and SciNet. For both methods, we vary $k$ in $\\{15,20,25\\}$. For
each supergraph, we generate 2 visualizations using
$\mathsf{Tau}$-$\mathsf{Push}$ and $\mathsf{PI}$ and organize them as a group.
The visualizations in each group are displayed to the participants without
telling them the methods, and the participants are asked to conduct the
following task.

  * •

Task 3 (T3): for the 2 visualizations in a group, select the one with superior
visualization quality.

Note that for each task, we collected 180 instances (30 participants $\times$
6 groups). Fig. 8(a) (resp. Fig. 8(b)) reports the ranking frequency of the
visualization generated by each approach in T1 (resp. T2). In particular, the
rankings of $\mathsf{PPRviz}$ are concentrated on top-1 and top-2 for both
tasks. This result demonstrates $\mathsf{PPRviz}$’s sound quality in terms of
readability and cluster inspection, which is consistent with our ND and ULCV
results reported in Section 7.2.1. Regarding the results of T3, we find in
Table 6 that the participants cannot tell the quality difference between the
visualizations generated by $\mathsf{Tau}$-$\mathsf{Push}$ and $\mathsf{PI}$
in most cases, and the times the two methods are selected as the best are
comparable, demonstrating that the approximate level-$\ell$ $\mathsf{PDist}$
computation in $\mathsf{PPRviz}$ does not affect its visualization quality.

####  7.2.3. Case Study

At last, we conduct a case study to compare the visualizations of
$\mathsf{PPRviz}$ and other competitors. In Fig. 9, we report the results of
$\mathsf{PPRviz}$ and all competitors on TwEgo. Besides that, we also compare
the results of $\mathsf{PPRviz}$ and the best competitor $\mathsf{FR}$ on two
large graphs Wiki-ii and FilmTrust, which are shown in Fig. 10 and Fig. 11,
respectively. We find that the comparison results of visualization are
consistent with those of metrics in Section 7.2.1. More concrete,
$\mathsf{PPRviz}$ yields a high-quality visualization, which clearly organizes
the graph into a well-connected cluster and several cliques. In contrast, the
competitors suffer from issues such as node overlapping and edge distortion.
Furthermore, as shown in Fig. 9(d) and Fig. 11(b), the structures of small-
size clusters yielded by the best competitor $\mathsf{FR}$ are hard to
recognize. This is because nodes in the small-size clusters are more likely to
be affected by the repulsive force from the large cluster, making all of them
huddle together.

###  7.3. Visualization Efficiency

Response time. Fig. 13 shows the response time on the 6 larger graphs,
including Amazon, Youtube, Orkut, DBLP, It-2004, and Twitter. We only report
the results of $\mathsf{PPRviz}$, $\mathsf{OpenOrd}$, $\mathsf{KDraw}$,
$\mathsf{PMDS}$, and $\mathsf{Node2vec}$, and omit the rest of the competitors
as they fail to terminate within 1000 seconds for all datasets. We can observe
that $\mathsf{PPRviz}$ consistently outperforms all competitors in terms of
response time. Specifically, $\mathsf{PPRviz}$ outputs the visualization
result within 1 second on all datasets. For example, $\mathsf{PPRviz}$ costs
0.63 seconds on the Twitter graph 3 billion edges, while all competing methods
take more than 1000 seconds. Regarding the competitors, $\mathsf{PMDS}$ only
computes the positions of several pivot nodes and determines the positions of
other nodes by linear combinations of the pivot nodes. However, it can only
visualize the entire Amazon graph in 45 seconds. In addition,
$\mathsf{Node2vec}$ incurs costly random walk simulations, rendering it rather
inefficient on large graphs and can only return the visualization for Amazon
in 845 seconds. The two multi-level methods, i.e., $\mathsf{KDraw}$ and
$\mathsf{OpenOrd}$, have comparable performance to $\mathsf{PPRviz}$ on
Amazon, i.e., the smallest one among the 6 graphs, but turn to be markedly
inferior to $\mathsf{PPRviz}$ when graph size increases. The reason is that
$\mathsf{KDraw}$ requires computing the forces between the leaf nodes inside a
supernode which is rather costly for high-level supergraphs, and
$\mathsf{OpenOrd}$ takes many iterations to determine the layout in its five-
stage design.

Preprocessing time. Fig. 13 plots the preprocessing time of the multi-level
methods, i.e., $\mathsf{PPRviz}$, $\mathsf{OpenOrd}$, and $\mathsf{KDraw}$, as
the single-level methods do not have the preprocessing phase. All three
methods conduct hierarchical clustering for the input graph. However,
$\mathsf{PPRviz}$ also computes the $\mathsf{DPR}$ vector and some single-
target $\mathsf{PDist}$ scores. The results show that the processing time of
$\mathsf{PPRviz}$ is two to three orders of magnitude faster than
$\mathsf{OpenOrd}$ and one order of magnitude faster than $\mathsf{KDraw}$.
Moreover, both $\mathsf{OpenOrd}$ and $\mathsf{KDraw}$ cannot finish
preprocessing for the largest Twitter graph within 12 hours while
$\mathsf{PPRviz}$ takes only 33 minutes. This is because $\mathsf{OpenOrd}$
computes the layout of the entire graph first and then conducts hierarchical
clustering on the two-dimensional layout. For $\mathsf{KDraw}$, its clustering
algorithm (Meyerhenke et al., 2014) is more expensive than $\mathsf{Louvain+}$
in $\mathsf{PPRviz}$.

Vary cluster size. Table 7 reports the preprocessing time and response time of
$\mathsf{PPRviz}$ by varying the maximum number of nodes (i.e., the cluster
size limit $k$) on the largest test graph Twitter. We exclude $\mathsf{KDraw}$
and $\mathsf{OpenOrd}$ from this experiment because configuring $k$ is
difficult for them, as discussed in Section 7.1. $\mathsf{PPRviz}$’s
preprocessing time drops when $k$ increases because $\mathsf{Louvain+}$
organizes more nodes into a supernode with larger $k$, resulting in fewer
supernodes in each level-$\ell$ supergraph and fewer levels of the supergraph
hierarchy. For interactive visualization, $\mathsf{PPRviz}$’s response time
increases with $k$, and the main reason is that more pairwise $\mathsf{PDist}$
are computed with more nodes in each visualization. Furthermore, the response
time of $\mathsf{PPRviz}$ is only 2.10 seconds even with $k=100$, above which
the intra-structure of a supernode becomes dense and overburdens human
perception (Huang et al., 2009).

Table 7. Time of $\boldsymbol{\mathsf{PPRviz}}$ on Twitter by varying $k$ (in seconds). $k$ | 5 | 10 | 25 | 50 | 100
---|---|---|---|---|---
Preprocessing | 2267.65 | 2114.39 | 1934.48 | 1842.45 | 1796.87
Response | 0.28 | 0.43 | 0.63 | 1.56 | 2.10

###  7.4. $\boldsymbol{\mathsf{Tau}}$-$\boldsymbol{\mathsf{Push}}$ Performance

Comparing with other solutions. To validate the efficiency of the
$\mathsf{Tau}$-$\mathsf{Push}$ algorithm for $\mathsf{PDist}$ computation, we
replace $\mathsf{Tau}$-$\mathsf{Push}$ with 4 alternative solutions as
mentioned in Section 7.1, and then compare $\mathsf{PPRviz}$ against these
variants in terms of response time, preprocessing time, and index size on the
4 largest graphs including Youtube, Orkut, It-2004, and Twitter. In terms of
response time, we use “-” to indicate that an approach fails to terminate
within 1000 seconds. Table 8 shows that all $\mathsf{PPRviz}$ variants incur
more than 1000 seconds on all tested graphs. This is because they need to
compute $\mathsf{PDist}$ from $O(n)$ leaf nodes for the top-level supergraph.
As shown in Table 9, all methods achieve comparable performance regarding the
preprocessing time, since supergraph hierarchy construction dominates
preprocessing cost. The two $\mathsf{PPRviz}$ variants using $\mathsf{PI}$ and
$\mathsf{ResAcc}$ have slightly shorter preprocessing time as they only need
to construct the supergraph hierarchies. For the same reason, they require
much less space to store the indices as shown in Table 10. In contrast,
$\mathsf{FORA}$ (resp. $\mathsf{Tau}$-$\mathsf{Push}$) precomputes random walk
samples (resp. $\mathsf{DPR}$ values and results for GBP) as indices. Compared
with $\mathsf{FORA}$, our $\mathsf{Tau}$-$\mathsf{Push}$ costs less space for
indices because $\mathsf{Tau}$-$\mathsf{Push}$ eliminates the need to store
random walks by precomputing $\mathsf{DPR}$ to guide the termination of push
operations. Specifically, besides $O(n)$ supernode partitions,
$\mathsf{PPRviz}$ only requires storing $n$ $\mathsf{DPR}$ values and
$O(k\cdot\sqrt{n\cdot k})$ extra $\mathsf{PDist}$ values, which in total are
insignificant compared with the size of the input graph.

Ablation study. In this set of experiments, we verify the effectiveness of the
three techniques in $\mathsf{Tau}$-$\mathsf{Push}$, i.e., the grouped push
strategy, $\mathsf{DPR}$-guided termination trick, and the filter-refinement
optimization delineated in Section 4.1. First, to demonstrate the
effectiveness of the grouped push strategy, we replace
$\mathsf{Forward}$-$\mathsf{Push}$ in $\mathsf{FORA}$ with GFP and call this
variant $\mathsf{GFRA}$. In particular, for each level-$\ell$ supernode,
$\mathsf{GFRA}$ first invokes GFP to roughly estimate level-$\ell$
$\mathsf{DPPR}$ values w.r.t. the given source supernode and then refines the
under-estimations by random walk samplings. After conducting a theoretical
analysis, we generate a sufficient amount of random walks to ensure the
correctness and optimize the time complexity by balancing the overhead of two
stages for a fair comparison. Akin to the analysis in Table 2, we can show
that the time complexity of $\mathsf{GFRA}$ to compute all pairwise
approximate level-$\ell$ $\mathsf{PDist}$ in a supernode $\mathcal{S}$ is
$O\left(\frac{k\cdot\log{n}\cdot\sqrt{m}}{\epsilon}\right)$, which improves
the time complexity of $\mathsf{FORA}$ by ${n}/{\sqrt{k}}$. As shown in Table
8, the response time of $\mathsf{GFRA}$ is at least four orders of magnitude
faster than $\mathsf{FORA}$ by adopting the grouped push strategy in our
$\mathsf{Tau}$-$\mathsf{Push}$.

Table 8. Response time of $\boldsymbol{\mathsf{PPRviz}}$ variants (in
seconds).

| $\mathsf{PI}$ | $\mathsf{FORA}$ | $\mathsf{FORA+}$ | $\mathsf{ResAcc}$ |  $\mathsf{Tau}$-$\mathsf{Push}$ | $\mathsf{GFRA}$ |  GFP ($\tau_{max}$)
---|---|---|---|---|---|---|---
Youtube | - | - | - | - | 0.06 | 0.07 | 0.06
Orkut | - | - | - | - | 0.12 | 0.36 | 0.12
It-2004 | - | - | - | - | 0.32 | 0.73 | 0.33
Twitter | - | - | - | - | 0.63 | 2.76 | 0.66

Table 9. Preprocessing time of $\boldsymbol{\mathsf{PPRviz}}$ variants (in
seconds).

| $\mathsf{PI}$ | $\mathsf{FORA}$ | $\mathsf{FORA+}$ | $\mathsf{ResAcc}$ |  $\mathsf{Tau}$-$\mathsf{Push}$ | $\mathsf{GFRA}$ |  GFP ($\tau_{max}$)
---|---|---|---|---|---|---|---
Youtube | 2.46 | 3.35 | 3.17 | 2.46 | 4.04 | 5.1 | 3.99
Orkut | 72.61 | 79.89 | 78.75 | 72.61 | 94.56 | 104.94 | 94.53
It-2004 | 169.27 | 223.99 | 200.21 | 169.27 | 312.33 | 308.3 | 69.18
Twitter | 1296.17 | 1364.04 | 1360.08 | 1296.17 | 1984.73 | 1485.64 | 1914.92

Table 10. Index size of $\boldsymbol{\mathsf{PPRviz}}$ variants (in MiB).

| $\mathsf{PI}$ | $\mathsf{FORA}$ | $\mathsf{FORA+}$ | $\mathsf{ResAcc}$ |  $\mathsf{Tau}$-$\mathsf{Push}$ | $\mathsf{GFRA}$ |  GFP ($\tau_{max}$)
---|---|---|---|---|---|---|---
Youtube | 5 | 51 | 30 | 5 | 9 | 51 | 9
Orkut | 13 | 237 | 95 | 13 | 25 | 237 | 25
It-2004 | 172 | 1520 | 1022 | 172 | 330 | 1520 | 330
Twitter | 177 | 1610 | 1052 | 177 | 338 | 1610 | 335

$\mathsf{Tau}$-$\mathsf{Push}$GFP ($\tau_{\max}$)

12345$10^{-3}$$10^{-1}$$10^{1}$response time (sec)

(a)

12345$10^{-3}$$10^{-1}$$10^{1}$response time (sec)

(b)

12345$10^{-3}$$10^{-1}$$10^{1}$response time (sec)

(c)

12345$10^{-3}$$10^{-1}$$10^{1}$response time (sec)

(d)

Figure 14. Comparison of
$\boldsymbol{\mathsf{Tau}}$-$\boldsymbol{\mathsf{Push}}$ and GFP
($\boldsymbol{\tau_{\max}}$)

Note that if we set
$\tau=\max_{\mathcal{V}_{j}\in\mathcal{S}\backslash\mathcal{V}_{i}}{\tau_{j}}$
for Eq.(5), all values returned by GFP are $(\epsilon,\delta)-$approximate
level-$\ell$ $\mathsf{DPPR}$. Here, we call this variant GFP ($\tau_{max}$)
and compare $\mathsf{GFRA}$ against it. We find in Table 8 that GFP
($\tau_{max}$) improves $\mathsf{GFRA}$ on the Orkut, It-2004, and Twitter
graphs that have massive edges, with 3$\times$, 2.3$\times$, and 4$\times$
speedups, respectively. Furthermore, as shown in Table 10, GFP ($\tau_{max}$)
incurs much less space overhead for index storage. The reason is that on such
graphs, $\mathsf{GFRA}$ requires a multitude of excessive random walks, while
GFP ($\tau_{max}$) eliminates random walks and enables early termination by
leveraging $\mathsf{DPR}$ as described in Section 4.1.

Finally, we evaluate the filter-refinement optimization by comparing
$\mathsf{Tau}$-$\mathsf{Push}$ with the initial solution GFP ($\tau_{max}$).
Fig. 14 shows that $\mathsf{Tau}$-$\mathsf{Push}$ significantly reduces the
response time of GFP when the cluster contains nodes with large $\mathsf{DPR}$
values by employing GBP. The speedup of $\mathsf{Tau}$-$\mathsf{Push}$ varies
since the skewness of $\mathsf{DPR}$ value is different on each graph. For the
first cluster on Youtube, the largest $\mathsf{DPR}$ value is 3 orders of
magnitude larger than the others, and thus $\mathsf{Tau}$-$\mathsf{Push}$
speeds up GFP by about $300\times$ by avoiding many rounds of push operations.
For a similar reason, $\mathsf{Tau}$-$\mathsf{Push}$ is over $1000\times$
faster than GFP in the second cluster in Twitter. The speedup of
$\mathsf{Tau}$-$\mathsf{Push}$ is less significant on Orkut and It-2004 graphs
but can still reach 9$\times$ and 24$\times$, respectively.

##  8\. Conclusions

This paper proposes a PPR-based node distance $\mathsf{PDist}$ and its fast
computation algorithm $\mathsf{Tau}$-$\mathsf{Push}$ for massive graph
visualization, whose performance is extensively evaluated by comparing with 13
competitors on 12 real-world graphs. The results show that our proposal
achieves high effectiveness and efficiency. Regarding future works, we plan to
extend $\mathsf{PDist}$ and $\mathsf{Tau}$-$\mathsf{Push}$ to support dynamic
or attributed graph visualization.

## References

  * (1)
  * Abello et al. (2006) James Abello, Frank Van Ham, and Neeraj Krishnan. 2006\.  Ask-graphview: A large scale graph visualization system.  _TVCG_ 12, 5 (2006), 669–676.
  * Agapito et al. (2013) Giuseppe Agapito, Pietro Hiram Guzzi, and Mario Cannataro. 2013.  Visualization of protein interaction networks: problems and solutions.  _BMC_ 14, 1 (2013), 1–30.
  * Ahmed et al. (2013) Amr Ahmed, Nino Shervashidze, Shravan Narayanamurthy, Vanja Josifovski, and Alexander J Smola. 2013.  Distributed large-scale natural graph factorization. In _WWW_. 37–48.
  * Andersen et al. (2006) Reid Andersen, Fan Chung, and Kevin Lang. 2006.  Local graph partitioning using pagerank vectors. In _FOCS_. 475–486.
  * Archambault et al. (2008) Daniel Archambault, Tamara Munzner, and David Auber. 2008\.  GrouseFlocks: Steerable exploration of graph hierarchy space.  _TVCG_ 14, 4 (2008), 900–913.
  * Auber (2004) David Auber. 2004\.  Tulip—A huge graph visualization framework.  In _GDS_. 105–126.
  * Bastian et al. (2009) Mathieu Bastian, Sebastien Heymann, and Mathieu Jacomy. 2009\.  Gephi: an open source software for exploring and manipulating networks. In _ICWSM_.
  * Battista et al. (1998) Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G Tollis. 1998.  _Graph drawing: algorithms for the visualization of graphs_.
  * Belkin and Niyogi (2003) Mikhail Belkin and Partha Niyogi. 2003.  Laplacian eigenmaps for dimensionality reduction and data representation.  _Neural Comput._ 15, 6 (2003), 1373–1396.
  * Bennett et al. (2007) Chris Bennett, Jody Ryall, Leo Spalteholz, and Amy Gooch. 2007\.  The aesthetics of graph visualization.  _CAe_ (2007), 57–64.
  * Bhowmick et al. (2020) Sourav S Bhowmick, Kai Huang, Huey Eng Chua, Zifeng Yuan, Byron Choi, and Shuigeng Zhou. 2020\.  AURORA: Data-driven construction of visual graph query interfaces for graph databases. In _SIGMOD_. 2689–2692.
  * Bikakis et al. (2016) Nikos Bikakis, John Liagouris, Maria Krommyda, George Papastefanatos, and Timos Sellis. 2016\.  GraphVizdb: A scalable platform for interactive large graph visualization. In _ICDE_. 1342–1345.
  * Blondel et al. (2008) Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008.  Fast unfolding of communities in large networks.  _J. Stat. Mech. Theory Exp._ 2008, 10 (2008), P10008.
  * Boldi and Vigna (2004) Paolo Boldi and Sebastiano Vigna. 2004.  The WebGraph Framework I: Compression Techniques. In _WWW_. 595–602.
  * Brandes and Pich (2006) Ulrik Brandes and Christian Pich. 2006.  Eigensolver methods for progressive multidimensional scaling of large data. In _GD_. 42–53.
  * Chung and Lu (2006) Fan Chung and Linyuan Lu. 2006.  Concentration inequalities and martingale inequalities: a survey.  _Internet Math._ 3, 1 (2006), 79–127.
  * Chung and Tsiatas (2012) Fan Chung and Alexander Tsiatas. 2012.  Finding and visualizing graph clusters using PageRank optimization.  _Internet Math._ (2012), 86–97.
  * Cohen et al. (2001) Reuven Cohen, Keren Erez, Daniel Ben-Avraham, and Shlomo Havlin. 2001\.  Breakdown of the internet under intentional attack.  _Phys. Rev. Lett._ 86, 16 (2001), 3682.
  * Davidson and Harel (1996) Ron Davidson and David Harel. 1996.  Drawing graphs nicely using simulated annealing.  _TOG_ 15, 4 (1996), 301–331.
  * De Nooy et al. (2018) Wouter De Nooy, Andrej Mrvar, and Vladimir Batagelj. 2018\.  _Exploratory social network analysis with Pajek: Revised and expanded edition for updated software_. Vol. 46.  Cambridge university press.
  * Du et al. (2017) Fan Du, Nan Cao, Yu-Ru Lin, Panpan Xu, and Hanghang Tong. 2017.  isphere: Focus+ context sphere visualization for interactive large graph exploration. In _CHI_.
  * Duncan et al. (1998) Christian A Duncan, Michael T Goodrich, and Stephen G Kobourov. 1998.  Balanced aspect ratio trees and their use for drawing very large graphs. In _GD_. 111–124.
  * Eades (1984) Peter Eades. 1984\.  A heuristic for graph drawing.  _Congr. Numer._ 42 (1984), 149–160.
  * Fogaras et al. (2005) Dániel Fogaras, Balázs Rácz, Károly Csalogány, and Tamás Sarlós. 2005\.  Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments.  _Internet Math._ 2, 3 (2005), 333–358.
  * Fruchterman and Reingold (1991) Thomas MJ Fruchterman and Edward M Reingold. 1991.  Graph drawing by force-directed placement.  _SP &E_ 21, 11 (1991), 1129–1164.
  * Gallo et al. (2020) Denis Gallo, Matteo Lissandrini, and Yannis Velegrakis. 2020\.  Personalized page rank on knowledge graphs: Particle Filtering is all you need!. In _EDBT_. 447–450.
  * Gansner et al. (2012) Emden R Gansner, Yifan Hu, and Stephen North. 2012.  A maxent-stress model for graph layout.  _TVCG_ 19, 6 (2012), 927–940.
  * Gansner et al. (2004) Emden R Gansner, Yehuda Koren, and Stephen North. 2004\.  Graph drawing by stress majorization. In _GD_. 239–250.
  * Gibson et al. (2013) Helen Gibson, Joe Faith, and Paul Vickers. 2013.  A survey of two-dimensional graph layout techniques for information visualisation.  _Inf. Vis._ 12, 3-4 (2013), 324–357.
  * Goyal and Ferrara (2018) Palash Goyal and Emilio Ferrara. 2018.  Graph embedding techniques, applications, and performance: A survey.  _Knowl.-Based Syst._ 151 (2018), 78–94.
  * Grover and Leskovec (2016) Aditya Grover and Jure Leskovec. 2016.  node2vec: Scalable feature learning for networks. In _SIGKDD_. 855–864.
  * Hagberg et al. (2008) Aric Hagberg, Pieter Swart, and Daniel S Chult. 2008\.  _Exploring network structure, dynamics, and function using NetworkX_.  Technical Report. Los Alamos National Lab.(LANL), Los Alamos, NM (United States).
  * Herman et al. (2000) Ivan Herman, Guy Melançon, and M Scott Marshall. 2000\.  Graph visualization and navigation in information visualization: A survey.  _TVCG_ 6, 1 (2000), 24–43.
  * Hou et al. (2021) Guanhao Hou, Xingguang Chen, Sibo Wang, and Zhewei Wei. 2021\.  Massively parallel algorithms for personalized PageRank.  _PVLDB_ 14, 9 (2021), 1668–1680.
  * Hu (2005) Yifan Hu. 2005.  Efficient, high-quality force-directed graph drawing.  _Mathematica_ 10, 1 (2005), 37–71.
  * Hu and Shi (2015) Yifan Hu and Lei Shi. 2015\.  Visualizing large graphs.  _Wiley Interdiscip. Rev. Comput. Stat._ 7, 2 (2015), 115–136.
  * Huang et al. (2009) Weidong Huang, Peter Eades, and Seok-Hee Hong. 2009\.  Measuring effectiveness of graph visualizations: A cognitive load perspective.  _Inf. Vis._ 8, 3 (2009), 139–152.
  * Jacomy et al. (2014) Mathieu Jacomy, Tommaso Venturini, Sebastien Heymann, and Mathieu Bastian. 2014.  ForceAtlas2, a continuous graph layout algorithm for handy network visualization designed for the Gephi software.  _PloS one_ 9, 6 (2014), e98679.
  * Jeh and Widom (2002) Glen Jeh and Jennifer Widom. 2002.  Simrank: a measure of structural-context similarity. In _SIGKDD_. 538–543.
  * Jung et al. (2017) Jinhong Jung, Namyong Park, Sael Lee, and U Kang. 2017\.  Bepi: Fast and memory-efficient method for billion-scale random walk with restart. In _SIGMOD_. 789–804.
  * Kamada et al. (1989) Tomihisa Kamada, Satoru Kawai, et al. 1989\.  An algorithm for drawing general undirected graphs.  _Inform. Process. Lett._ 31, 1 (1989), 7–15.
  * Klammler et al. (2018) Moritz Klammler, Tamara Mchedlidze, and Alexey Pak. 2018\.  Aesthetic discrimination of graph layouts. In _GD_. 169–184.
  * Kunegis (2013) Jérôme Kunegis. 2013\.  KONECT – The Koblenz Network Collection. In _WWW_.
  * Kwak et al. (2010) Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. 2010\.  What is Twitter, a social network or a news media?. In _WWW_. 591–600.
  * Lee et al. (2006) Bongshin Lee, Catherine Plaisant, Cynthia Sims Parr, Jean-Daniel Fekete, and Nathalie Henry. 2006\.  Task taxonomy for graph visualization. In _BELIV_.
  * Leskovec and Krevl (2014) Jure Leskovec and Andrej Krevl. 2014.  SNAP Datasets: Stanford Large Network Dataset Collection.  http://snap.stanford.edu/data.
  * Lin et al. (2020) Dandan Lin, Raymond Chi-Wing Wong, Min Xie, and Victor Junqiu Wei. 2020.  Index-free approach with theoretical guarantee for efficient random walk with restart query. In _ICDE_. 913–924.
  * Litvak et al. (2007) Nelly Litvak, Werner RW Scheinhardt, and Yana Volkovich. 2007\.  In-degree and PageRank: why do they follow similar power laws?  _Internet Math._ 4, 2-3 (2007), 175–198.
  * Lofgren et al. (2016) Peter Lofgren, Siddhartha Banerjee, and Ashish Goel. 2016\.  Personalized pagerank estimation and search: A bidirectional approach. In _WSDM_. 163–172.
  * Lofgren and Goel (2013) Peter Lofgren and Ashish Goel. 2013.  Personalized pagerank to a target node.  _arXiv_ (2013).
  * Luo et al. (2019) Siqiang Luo, Xiaokui Xiao, Wenqing Lin, and Ben Kao. 2019\.  Baton: Batch one-hop personalized pageranks with efficiency and accuracy.  _TKDE_ 32, 10 (2019), 1897–1908.
  * Martin et al. (2011) Shawn Martin, W Michael Brown, Richard Klavans, and Kevin W Boyack. 2011.  OpenOrd: an open-source toolbox for large graph layout. In _VDA_ , Vol. 7868. 786806\.
  * Meyerhenke et al. (2017) Henning Meyerhenke, Martin Nöllenburg, and Christian Schulz. 2017\.  Drawing large graphs by multilevel maxent-stress optimization.  _TVCG_ 24, 5 (2017), 1814–1827.
  * Meyerhenke et al. (2014) Henning Meyerhenke, Peter Sanders, and Christian Schulz. 2014\.  Partitioning complex networks via size-constrained clustering. In _SEA_. 351–363.
  * Newman (2006) Mark EJ Newman. 2006\.  Modularity and community structure in networks.  _PNAS_ 103, 23 (2006), 8577–8582.
  * Niculescu and Persson (2006) Constantin Niculescu and Lars-Erik Persson. 2006.  _Convex functions and their applications_.  Springer.
  * Noack (2005) Andreas Noack. 2005\.  Energy-based clustering of graphs with nonuniform degrees. In _GD_. 309–320.
  * Noack (2007) Andreas Noack. 2007\.  Unified quality measures for clusterings, layouts, and orderings of graphs, and their application as software design criteria.  (2007).
  * Page et al. (1999) Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999.  _The PageRank citation ranking: Bringing order to the web._ Technical Report. Stanford InfoLab.
  * Perozzi et al. (2014) Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014\.  Deepwalk: Online learning of social representations. In _SIGKDD_. 701–710.
  * Purchase (2002) Helen C Purchase. 2002\.  Metrics for graph drawing aesthetics.  _JVLC_ 13, 5 (2002), 501–516.
  * Purchase et al. (2002) Helen C Purchase, David Carrington, and Jo-Anne Allder. 2002\.  Empirical evaluation of aesthetics-based graph layout.  _Empir. Softw. Eng._ 7, 3 (2002), 233–255.
  * Rodrigues et al. (2015) Jose Rodrigues, Hanghang Tong, Agma Traina, Christos Faloutsos, and Jure Leskovec. 2015.  Gmine: a system for scalable, interactive graph visualization and mining.  _PVLDB_ 4 (2015), 1195–1198.
  * Roweis and Saul (2000) Sam T Roweis and Lawrence K Saul. 2000.  Nonlinear dimensionality reduction by locally linear embedding.  _Science_ 290, 5500 (2000), 2323–2326.
  * Sahu et al. (2017) Siddhartha Sahu, Amine Mhedhbi, Semih Salihoglu, Jimmy Lin, and M Tamer Özsu. 2017.  The ubiquity of large graphs and surprising challenges of graph processing.  _PVLDB_ 11, 4 (2017), 420–431.
  * Shannon et al. (2003) Paul Shannon, Andrew Markiel, Owen Ozier, Nitin S Baliga, Jonathan T Wang, Daniel Ramage, Nada Amin, Benno Schwikowski, and Trey Ideker. 2003.  Cytoscape: a software environment for integrated models of biomolecular interaction networks.  _Genome research_ 13, 11 (2003), 2498–2504.
  * Shi et al. (2019) Jieming Shi, Renchi Yang, Tianyuan Jin, Xiaokui Xiao, and Yin Yang. 2019.  Realtime top-k personalized pagerank over large graphs on gpus.  _PVLDB_ 13, 1 (2019), 15–28.
  * Shi et al. (2009) Lei Shi, Nan Cao, Shixia Liu, Weihong Qian, Li Tan, Guodong Wang, Jimeng Sun, and Ching-Yung Lin. 2009\.  HiMap: Adaptive visualization of large-scale online social networks. In _PacificVis_. 41–48.
  * Shin et al. (2015) Kijung Shin, Jinhong Jung, Sael Lee, and U Kang. 2015\.  Bear: Block elimination approach for random walk with restart on large graphs. In _SIGMOD_. 1571–1585.
  * Sokal (1958) Robert R Sokal. 1958\.  A statistical method for evaluating systematic relationships.  _Univ. Kansas, Sci. Bull._ 38 (1958), 1409–1438.
  * Tang et al. (2015) Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015\.  Line: Large-scale information network embedding. In _WWW_. 1067–1077.
  * Taylor and Rodgers (2005) Martyn Taylor and Peter Rodgers. 2005.  Applying graphical design techniques to graph visualisation. In _Inf. Vis._ 651–656.
  * Tong et al. (2006) Hanghang Tong, Christos Faloutsos, and Jia-Yu Pan. 2006\.  Fast random walk with restart and its applications. In _ICDM_. 613–622.
  * Torgerson (1952) Warren S Torgerson. 1952\.  Multidimensional scaling: I. Theory and method.  _Psychometrika_ 17, 4 (1952), 401–419.
  * Van der Maaten and Hinton (2008) Laurens Van der Maaten and Geoffrey Hinton. 2008.  Visualizing data using t-SNE.  _JMLR_ 9 (2008), 2579–2605.
  * Von Landesberger et al. (2011) Tatiana Von Landesberger, Arjan Kuijper, Tobias Schreck, Jörn Kohlhammer, Jarke J van Wijk, J-D Fekete, and Dieter W Fellner. 2011\.  Visual analysis of large graphs: state-of-the-art and future research challenges. In _CGF_ , Vol. 30. 1719–1749.
  * Wang et al. (2016a) Daixin Wang, Peng Cui, and Wenwu Zhu. 2016a.  Structural deep network embedding. In _SIGKDD_. 1225–1234.
  * Wang et al. (2020) Hanzhi Wang, Zhewei Wei, Junhao Gan, Sibo Wang, and Zengfeng Huang. 2020.  Personalized PageRank to a Target Node, Revisited. In _SIGKDD_. 657–667.
  * Wang et al. (2016b) Sibo Wang, Youze Tang, Xiaokui Xiao, Yin Yang, and Zengxiang Li. 2016b.  HubPPR: effective indexing for approximate personalized pagerank.  _PVLDB_ 10, 3 (2016), 205–216.
  * Wang et al. (2019) Sibo Wang, Renchi Yang, Runhui Wang, Xiaokui Xiao, Zhewei Wei, Wenqing Lin, Yin Yang, and Nan Tang. 2019\.  Efficient algorithms for approximate single-source personalized pagerank queries.  _TODS_ 44, 4 (2019), 1–37.
  * Wang et al. (2017b) Sibo Wang, Renchi Yang, Xiaokui Xiao, Zhewei Wei, and Yin Yang. 2017b.  FORA: simple and effective approximate single-source personalized pagerank. In _SIGKDD_. 505–514.
  * Wang et al. (2017a) Yunhai Wang, Yanyan Wang, Yinqi Sun, Lifeng Zhu, Kecheng Lu, Chi-Wing Fu, Michael Sedlmair, Oliver Deussen, and Baoquan Chen. 2017a.  Revisiting stress majorization as a unified framework for interactive constrained graph visualization.  _TVCG_ (2017).
  * Wu et al. (2021) Hao Wu, Junhao Gan, Zhewei Wei, and Rui Zhang. 2021\.  Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push. In _SIGMOD_. 1996–2008.
  * Wu et al. (2016) Yanhong Wu, Nan Cao, Daniel Archambault, Qiaomu Shen, Huamin Qu, and Weiwei Cui. 2016\.  Evaluation of graph sampling: A visualization perspective.  _TVCG_ (2016).
  * Xu et al. (2009) Kai Xu, Rohan Williams, Seok-Hee Hong, Qing Liu, and Ji Zhang. 2009.  Semi-bipartite graph visualization for gene ontology networks. In _GD_.
  * Yang et al. (2020) Renchi Yang, Jieming Shi, Xiaokui Xiao, Yin Yang, and Sourav S Bhowmick. 2020.  Homogeneous network embedding for massive graphs via reweighted personalized PageRank.  _PVLDB_ 13, 5 (2020), 670–683.
  * Yoon et al. (2018) Minji Yoon, Jinhong Jung, and U Kang. 2018.  Tpa: Fast, scalable, and accurate method for approximate random walk with restart on billion scale graphs. In _ICDE_. 1132–1143.
  * Zhuang et al. (2019) Di Zhuang, J Morris Chang, and Mingchen Li. 2019\.  DynaMo: Dynamic community detection by incrementally maximizing modularity.  _TKDE_ (2019).

##  Appendix A Appendix

###  A.1. Algorithmic Details

$\boldsymbol{\mathsf{Louvain+}}$. To construct supergraph hierarchy, a
solution is directly using multilevel community detection algorithms such as
$\mathsf{Louvain}$ (Blondel et al., 2008), which merges well-connected nodes
based on modularity optimization (Newman, 2006). However, $\mathsf{Louvain}$
boils down to two defects for visualization: (i) the number of communities
(supernodes) in the highest level is too large as there is no merge that
increases the modularity after some point, which causes visual clutter; (ii)
the number of nodes in the communities are imbalanced. Specifically, low-level
supernodes tend to contain many children, which leads to visual cluster while
high-level supernodes usually contain only a few children and thus provide
very limited structural information about the graph. To fix these, we extend
$\mathsf{Louvain}$ to $\mathsf{Louvain+}$. Here we ignore the direction in the
raw graph and take the undirected graph as the input for community detection.
To generate a level-$(\ell+1)$ supergraph $G_{\ell+1}$, the detailed
clustering strategy is that either (i) directly merge supernode $\mathcal{S}$
to its neighboring supernode $\mathcal{T}$ if $\mathcal{T}$ is the only
neighbor; or (ii) merge $\mathcal{S}$ to its neighboring supernode
$\mathcal{T}$ with the largest modularity gain
$\widehat{Q}(\mathcal{S},\mathcal{T})$ if the size of $\mathcal{T}$ after this
merge is less than $k$. The modularity gain
$\widehat{Q}(\mathcal{S},\mathcal{T})$ after merging level-$(\ell+1)$
supernodes $\mathcal{S}$ and $\mathcal{T}$ is defined as

$\widehat{Q}(\mathcal{S},\mathcal{T})=\sum_{\mathcal{V}_{i}\in\mathcal{S}}q(\mathcal{V}_{i},\mathcal{T}).$

Note that $q(\mathcal{V}_{i},\mathcal{T})$ is the modularity change of
$G_{\ell}$ after moving a node $\mathcal{V}_{i}$ into supernode $\mathcal{T}$,
which is defined by

$\begin{split}q(\mathcal{V}_{i},\mathcal{T})=&\left[\frac{w(\mathcal{T})+w_{cr}(\mathcal{V}_{i},\mathcal{T})}{2m}-\left(\frac{w_{in}(\mathcal{T})+w_{in}(\mathcal{V}_{i})}{2m}\right)^{2}\right]\\\
-&\left[\frac{w(\mathcal{T})}{2m}-\left(\frac{w_{in}(\mathcal{T})}{2m}\right)^{2}-\left(\frac{w_{in}(\mathcal{V}_{i})}{2m}\right)^{2}\right],\end{split}$

where $w(\mathcal{T})$ is the number of leaf edges with both endpoints within
$\mathcal{T}$, $w_{cr}(\mathcal{V}_{i},\mathcal{T})$ is the number of leaf
edges crossing supernodes $\mathcal{V}_{i}$ and $\mathcal{T}$, and
$w_{in}(\mathcal{T})$ is the number of leaf edges incident to $\mathcal{T}$.

Stress Majorization. Stress majorization (Gansner et al., 2004) is adapted to
enable efficient optimization, Particularly, Eq. (7) is transformed via the
following steps. First, the expansion of Eq. (7) is rewritten as follows:

(8)
$Loss(\mathbf{X}|\boldsymbol{\Delta})=\sum\limits_{i<j}1+\sum\limits_{i<j}\frac{||\mathbf{X}[i]-\mathbf{X}[j]||^{2}}{\boldsymbol{\Delta}[i,j]^{2}}-2\sum\limits_{i<j}\frac{||\mathbf{X}[i]-\mathbf{X}[j]||}{\boldsymbol{\Delta}[i,j]}.$

In Eq. (8), the first term is a constant and the second term can be
represented by $\textrm{trace}(\mathbf{X}^{T}\mathbf{L}^{w}\mathbf{X})$, where
$\mathbf{L}^{w}$ is the weighted Laplacian matrix and defined as

$\mathbf{L}^{w}[i,j]=\begin{cases}-\frac{1}{\boldsymbol{\Delta}[i,j]^{2}}&\text{if
$i\neq j$}\\\ \sum_{k\neq i}\frac{1}{\boldsymbol{\Delta}[i,k]^{2}}&\text{if
$i=j$}\end{cases}.$

According to the Cauchy-Schwartz inequality, we know that for any position
matrix $\mathbf{Y}$,
$||\mathbf{X}[i]-\mathbf{X}[j]||||\mathbf{Y}[i]-\mathbf{Y}[j]||\geq(\mathbf{X}[i]-\mathbf{X}[j])^{T}(\mathbf{Y}[i]-\mathbf{Y}[j])$
holds. Hence, the third term can be bounded by

$-2\sum\limits_{i<j}\frac{||\mathbf{X}[i]-\mathbf{X}[j]||}{\boldsymbol{\Delta}[i,j]}\leq-2\sum\limits_{i<j}\frac{(\mathbf{X}[i]-\mathbf{X}[j])^{T}(\mathbf{Y}[i]-\mathbf{Y}[j])}{\boldsymbol{\Delta}[i,j]||\mathbf{Y}[i]-\mathbf{Y}[j]||}.$

Then the third term can be written as
$-\textrm{trace}(2\mathbf{X}^{T}\mathbf{L}^{Y}\mathbf{Y})$, where the matrix
$\mathbf{L}^{Y}$ is defined as

$\mathbf{L}^{Y}[i,j]=\begin{cases}-\frac{1}{\boldsymbol{\Delta}[i,j]||\mathbf{Y}[i]-\mathbf{Y}[j]||}&\text{if
$i\neq j$ and $\mathbf{Y}[i]\neq\mathbf{Y}[j]$}\\\ -\sum_{k\neq
i}\mathbf{L}^{Y}[i,k]&\text{if $i=j$}\\\ 0&\text{otherwise}\end{cases}.$

Hence, the loss function in Eq. (7) can be bounded by

(9)
$\sum\limits_{i<j}1+\textrm{trace}(\mathbf{X}^{T}\mathbf{L}^{w}\mathbf{X})-\textrm{trace}(2\mathbf{X}^{T}\mathbf{L}^{Y}\mathbf{Y}).$

To optimize Eq. (9), let $\mathbf{Y}$ be the position matrix from the previous
iteration and $\mathbf{X}$ be the position matrix to be optimized in the
current iteration. By setting the derivative of Eq. (9) to zero with respect
to $\mathbf{X}$, the minimizer of the loss function satisfies

(10) $\mathbf{X}=(\mathbf{L}^{w})^{-1}\mathbf{L}^{Y}\mathbf{Y},$

by which position matrix $\mathbf{X}$ is iteratively optimized and finally
returned for visualization.

###  A.2. $\boldsymbol{\mathsf{FORA}}$ and $\boldsymbol{\mathsf{GFRA}}$

$\boldsymbol{\mathsf{FORA}}$. Wang et al. (2017b) propose to invoke
$\mathsf{FORA}$ from each leaf node $v_{s}\in\mathcal{V}_{i}$. In particular,
$\mathsf{FORA}$ first utilizes $\mathsf{Forward}$-$\mathsf{Push}$ (Andersen et
al., 2006) to derive rough approximations of the $\mathsf{DPPR}$ values, and
then estimates the error term in Eq. (3) by exploiting random walk samplings
(Fogaras et al., 2005). Adapting the conclusions in (Wang et al., 2017b), we
can show that $\mathsf{FORA}$ yields approximate $\mathsf{DPPR}$ for each
$v_{s}\in\mathcal{V}_{i}$. In particular, given a source $v_{s}\in V$, by
setting the initial residue value as $r(v_{s},v_{s})=d(v_{s})$ and performing
$r_{sum}\cdot W$ random walks, $\mathsf{FORA}$ returns
$(\epsilon,\delta)-$approximate $\mathsf{DPPR}$
$\widehat{\pi}_{d}(v_{s},v_{t})$ with probability at least $1-p_{f}$, where
$r_{sum}=\sum_{v_{j}\in V}r(v_{s},v_{j})$ and
$W=\frac{(2+2\epsilon/3)\cdot\log{(1/p_{f})}}{\epsilon^{2}\delta}$.
Accordingly, plugging the approximate $\mathsf{DPPR}$ into Eq. (2) yields
$(\epsilon,\delta)-$approximate level-$\ell$ $\mathsf{DPPR}$. However,
$\mathsf{FORA}$ has high computation complexity. Specifically, the
$\mathsf{Forward}$-$\mathsf{Push}$ phase costs $O(d(v_{s})/r_{max})$ (Andersen
et al., 2006), and the random walk phase costs $O(\omega)=O(m\cdot
r_{max}\cdot W)$ as $r_{sum}\leq m\cdot r_{max}$ when push phase finishes.
Following (Wang et al., 2017b), we set ${r_{max}=\sqrt{{d(v_{s})/(m\cdot
W)}}}$ to balance the time complexities of two phases. Thus, $\mathsf{FORA}$
costs $O\left(\sqrt{d(v_{s})\cdot m\cdot W}\right)$ for a source leaf node
$v_{s}\in\mathcal{V}_{i}$. By summarizing the time complexities for each
$v_{s}\in\mathcal{V}_{i}$ and $\mathcal{V}_{i}\in\mathcal{S}$, the time
complexity for computing all pairwise approximate level-$\ell$ $\mathsf{DPPR}$
in a supernode $\mathcal{S}$ is
${O\left(\sum_{\mathcal{V}_{i}\in\mathcal{S}}\sum_{v_{s}\in
F(\mathcal{V}_{i})}\sqrt{d(v_{s})\cdot m\cdot W}\right)}$, which is
prohibitively high, as a high-level supernode $\mathcal{V}_{i}$ can contain
many leaf nodes.

Input: Graph $G$, supernode $\mathcal{S}$, constants $r_{max}$, $\omega$.

Output: Estimated $\widehat{\boldsymbol{\Delta}}[i,j],$
$\forall{\mathcal{V}_{i},\mathcal{V}_{j}}\in\mathcal{S}$.

1

2for  _each supernode $\mathcal{V}_{i}\in\mathcal{S}$_ do

3 $\forall{\mathcal{V}_{j}\in\mathcal{S}},\
\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})\leftarrow$GFP
$(G,\mathcal{S},\mathcal{V}_{i},r_{max})$;

4 $r_{sum}\leftarrow\sum_{v_{j}\in V}r(\mathcal{V}_{i},v_{j})$;

5 repeat

6 Perform a random walk from a node $v_{k}$ with probability
$\frac{r(\mathcal{V}_{i},v_{k})}{r_{sum}}$. Let $v_{t}$ be the ending node of
the random walk;

7 $\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})$ increases by
$\frac{r_{sum}}{\omega\cdot|F(\mathcal{V}_{j})|}$ for $v_{t}\in
F(\mathcal{V}_{j})$;

8

9 until  _$\omega$ times_;

10Lines 8-9 in Algorithm 1;

Algorithm 4 $\mathsf{GFRA}$

$\boldsymbol{\mathsf{GFRA}}$. To improve the efficiency of the above
$\mathsf{FORA}$ adaptation, we propose $\mathsf{GFRA}$, which conducts push
and sampling from the perspective of supernodes. The pseudo-code of
$\mathsf{GFRA}$ is illustrated in Algorithm 4. Particularly, $\mathsf{GFRA}$
first performs GFP of $\mathsf{Tau}$-$\mathsf{Push}$, which returns the
estimated value $\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})$ for each
$\mathcal{V}_{j}\in\mathcal{S}$ and the residue value
$r(\mathcal{V}_{i},v_{k})$ for each $v_{k}\in V$ (Lines 2-3). After that,
$\omega$ times of random walk samplings are invoked. For each sampling, it
starts from node $v_{k}$, where $v_{k}$ is selected based on its residue
$r(\mathcal{V}_{i},v_{k})$ (Line 5). Suppose that the sampling stops at
$v_{t}\in F(\mathcal{V}_{j})$, then the estimated value
$\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})$ is increased by
$\frac{r_{sum}}{\omega\cdot|F(\mathcal{V}_{j})|}$ (Line 6). Given a single
source supernode $\mathcal{V}_{i}$, $\mathsf{GFRA}$ reduces
$O(F(\mathcal{V}_{i}))$ times of calls of vanilla $\mathsf{FORA}$ to only once
by utilizing GFP. Based on Lemma A.2, the following theorem establishes the
correctness of $\mathsf{GFRA}$.

###### Theorem A.1.

For any user-selected supernode $\mathcal{S}$, by performing
$\omega=\frac{r_{sum}}{\gamma}\cdot W$ random walks where
$\gamma=\min_{\mathcal{V}_{i}\in\mathcal{S}}|F(\mathcal{V}_{i})|$ and
$W=\frac{(2+2\epsilon/3)\cdot\log{(1/p_{f})}}{\epsilon^{2}\delta}$, Algorithm
4 returns $(\epsilon,\delta)-$approximate level-$\ell$ $\mathsf{DPPR}$
$\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})$ for
$\mathcal{V}_{i},\mathcal{V}_{j}\in\mathcal{S}$ with probability at least
$1-p_{f}$.

Following the time complexity analysis of vanilla $\mathsf{FORA}$, we can show
that $\mathsf{GFRA}$ costs
$O\left(\sum_{\mathcal{V}_{i}\in\mathcal{S}}\frac{d(\mathcal{V}_{i})}{|F(\mathcal{V}_{i})|\cdot
r_{max}}+\frac{m\cdot r_{max}}{\gamma}\cdot W\right)$ to approximate all-pair
level-$\ell$ $\mathsf{DPPR}$ in $\mathcal{S}$. For the setting of $r_{max}$,
we balance the complexity of $\mathsf{Tau}$-$\mathsf{Push}$ from all source
nodes $\mathcal{V}_{i}\in\mathcal{S}$ with that of the random walk phase.
Thus, we have
${r_{max}=\sqrt{\gamma\cdot\sum_{\mathcal{V}_{i}\in\mathcal{S}}{d(\mathcal{V}_{i})}/{|F(\mathcal{V}_{i})|}/(m\cdot
W)}}$, and the time complexity becomes
${O\left(\sqrt{\sum_{\mathcal{V}_{i}\in\mathcal{S}}{(d(\mathcal{V}_{i})}/{|F(\mathcal{V}_{i})|})\cdot({m\cdot
W}/{\gamma})}\right)}$.

###  A.3. Proofs

Proof of Theorem 3.2. We use $z_{ij}$ to denote
$\pi_{d}(v_{i},v_{j})+\pi_{d}(v_{j},v_{i})$. Thus,

$\displaystyle\sum_{v_{i},v_{j}\in V}{z_{ij}}$
$\displaystyle={{\sum_{v_{i},v_{j}\in
V}{\pi_{d}(v_{i},v_{j})}+\sum_{v_{i},v_{j}\in
V}{\pi_{d}(v_{j},v_{i})}}}=2\sum_{v_{i},v_{j}\in V}{\pi_{d}(v_{i},v_{j})}$
(11) $\displaystyle=2\sum_{v_{i}\in V}{d(v_{i})\cdot\sum_{v_{j}\in
V}{\pi(v_{i},v_{j})}}=2m.$

Define function $f(z)$ as $f(z)=\frac{1}{\min(\max(2,1-\log{(z)}),2\log
n)^{2}}$. It is easy to show that $f(z)$ is monotonically increasing when
$z\in[2,2\log n]$ and is always smaller than function $h(z)=0.215e\cdot
z+0.035$. By Eq. (1), we have
$\boldsymbol{\Delta}[i,j]=\min(\max(2,1-\log{(z_{ij})}),2\log n)$. As we
assume that $\boldsymbol{\Delta}[i,j]=||X[i]-X[j]||$, we can obtain

$\displaystyle\textrm{ND}(\mathbf{X})$
$\displaystyle=\sum_{i<j}{\frac{1}{\boldsymbol{\Delta}[i,j]^{2}}}=\sum_{i<j}{f(z_{ij})}\leq\frac{1}{2}\sum_{1\leq
i,j\leq n}{f(z_{ij})}$ $\displaystyle\leq\frac{1}{2}\sum_{1\leq i,j\leq
n}{h(z_{ij})}=\frac{1}{2}\left(0.215e\sum_{v_{i},v_{j}\in
V}{z_{ij}}+0.035n^{2}\right).$

Plugging Eq. (11) into the above inequality gives ND$(\mathbf{X})\leq
0.215e\cdot m+0.0175n^{2}$, which completes the proof.

Proof of Theorem 3.3. For any random walk starting from $v_{i}$, the
probability that the walk moves to a certain one-hop neighbor $v_{j}$ is
$(1-\alpha)/d(v_{i})$. Since the walk stops at $v_{j}$ with probability
$\alpha$, then the PPR value of a neighbor is bounded by
$\pi(v_{i},v_{j})\geq\frac{\alpha(1-\alpha)}{d(v_{i})}.$ As we assume that
$\boldsymbol{\Delta}[i,j]=||X[i]-X[j]||$, by Definition 3.1, the length of any
edge $l(v_{i},v_{j})$ is bounded by

$l(v_{i},v_{j})=\boldsymbol{\Delta}[i,j]\leq
1-\log{\left(2\alpha(1-\alpha)\right)}.$

Based on the range of $\mathsf{PDist}$, the edge length is in the range of
$[2,1-\log{2\alpha(1-\alpha)}]$, where
$\textstyle\alpha\leq\tfrac{1}{2}-\sqrt{\tfrac{1}{4}-\frac{1}{2e}}$. According
to Popoviciu’s inequality (Niculescu and Persson, 2006),

$\textrm{ULCV}(\mathbf{X})=\frac{l_{\sigma}}{l_{\mu}}\leq\frac{{\left(\log{\tfrac{1}{{2\alpha(1-\alpha)}}}-1\right)}/{2}}{2}=\frac{\left(\log{\tfrac{1}{{2\alpha(1-\alpha)}}}-1\right)}{4}.$

Proof of Lemma 3.6. We call the approximate $\mathsf{PDist}$ mentioned in
Lemma 3.6 $(\theta,\sigma)$-approximate $\mathsf{PDist}$. We first focus on
the relative error part in Lemma 3.6. Denote
$c=\left(\frac{\pi_{d}(\mathcal{V}_{i},\mathcal{V}_{j})+\pi_{d}(\mathcal{V}_{j},\mathcal{V}_{i})}{e}\right)^{\theta}$.
There exist the following two cases.

  * •

To ensure
$\widehat{\boldsymbol{\Delta}}[i,j]-\boldsymbol{\Delta}[i,j]\leq\theta\cdot\boldsymbol{\Delta}[i,j]$,
the following approximation should be satisfied

$\pi_{d}(\mathcal{V}_{i},\mathcal{V}_{j})-\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})\leq(1-c)\cdot\pi_{d}(\mathcal{V}_{i},\mathcal{V}_{j}).$

  * •

To ensure
$\boldsymbol{\Delta}[i,j]-\widehat{\boldsymbol{\Delta}}[i,j]\leq\theta\cdot\boldsymbol{\Delta}[i,j]$,
the following approximation should be satisfied

$\widehat{\pi}_{d}(\mathcal{V}_{i},\mathcal{V}_{j})-\pi_{d}(\mathcal{V}_{i},\mathcal{V}_{j})\leq(\frac{1}{c}-1)\cdot\pi_{d}(\mathcal{V}_{i},\mathcal{V}_{j}).$

Since $\frac{1}{c}-1\geq 1-c$ and each $\Delta[i,j]$ is in range
$[2,2\log{n}]$ by definition, by setting