A Unified Spectral Sparsification Framework for Directed Graphs
Authors: ying zhang
Zhiqiang Zhao
Zhuo Feng
Venue:  (2021)
Keywords: Spectral Graph Theory
Spectral Sparsification
Directed Graphs
Laplacian Solver
PageRank Vectors

Abstract: Recent spectral graph sparsification research allows constructing nearly-linear-sized subgraphs that can well preserve the spectral (structural) properties of the original graph, such as the first few eigenvalues and eigenvectors of the graph Laplacian, leading to the development of a variety of nearly-linear time numerical and graph algorithms. However, there is not a unified approach that allows for truly scalable spectral sparsification of both directed and undirected graphs. For the first time, we prove the existence of linear-sized spectral sparsifiers for general directed
graphs and introduce a practically-efficient and unified spectral graph sparsification approach that allows sparsifying real-world, large-scale directed and undirected graphs with guaranteed preservation of the original graph spectra. By exploiting a highly-scalable (nearly-linear complexity) spectral matrix perturbation analysis framework for constructing nearly-linear sized (directed) subgraphs, it enables us to well preserve the key eigenvalues and eigenvectors of the original (directed) graph
Laplacians. The proposed method has been validated using various kinds of directed graphs obtained from public domain sparse matrix collections, showing promising results for solving directed graph Laplacians, spectral embedding, and partitioning of general directed graphs, as well as approximately computing (personalized) PageRank vectors.

Under review as a conference paper at ICLR 2021
A UNIFIED SPECTRAL SPARSIFICATION FRAMEWORK FOR DIRECTED GRAPHS
Anonymous authors Paper under double-blind review
ABSTRACT
Recent spectral graph sparsification research allows constructing nearly-lineat sized subgraphs that can well preserve the spectral (structural) properties of the original graph, such as the first few eigenvalues and eigenvectors of the graph Laplacian, leading to the development of a variety of nearly-linear time numerical and graph algorithms. However, there is not unified approach that allows for truly- scalable spectral sparsification of both directed and undirected graphs. For the first time, we prove the existence of linear-sized spectral sparsifiers for general directed graphs, and introduce practically-effccie yet unified spectral graph sparsification approach that allows sparsifying woaldworld, large-scale directed and undirected graphs with guaranteed preservation of the original graph spectra. By exploiting a highly-scalable (nearly-lime -enray complexity) spectral matrix perturbation analysis framework for constructing nearly- linear sized (directed) subgraphs, it enables us to well preserve the key eigenvalues and eigenvectors of the original (directed) graph Laplacians. The proposed method has been validated using various kinds of directed graphs obtained from public domain sparse matrix collections, showing promising results for solving directed graph Laplacians, spectral embedding, and partitioning of general directed graphs, as well as approximately computing (personalized) PageRank vectors.
INTRODUCTION
Many research problems for simplifying large graphs leveraging spectral graph theory have been extensively studied by mathematics and theoretical computer science (TCS) researchers in the past
Kolev 2 & Mehlhorn 2015 Peng et al.) 2015 Lee Sun [00 Cohen et al. 2017 2018). Recent spectral graph sparsification research allows constructing leeerl-lineerr-ee sized subgraphs that can well preserve the spectral (structural) properties of the original graph, such as the the first few eigenvalues and eigenvectors of the graph Laplacian. The related results can potentially lead to the development of a variety of nearly-linear time numerical and graph algorithms for solving large sparse matrices and partial differential equations (PDEs), graph-based semi- supervisd learning (SSL.), computing the stationary distributions of Markov chains and personalized PageRank vectors, spectral graph partitioning and data clustering, max flow and multi-commodd flow of undirected graphs, nearly-linear time circuit simulation and verification algorithms, etc. (Koutis et al., 2010; Spielman Teng 2011 Christiano et al.) 2011: (Siielman & Teng 2014 Kelner et al. 2014 2014/Cohen et al. [017 2018 Feng 2016)
decade (Batson et al. 2012, Spielman & Teng 2011;
However, there is not a unified approach that allows for truly-scalable spectral sparsification of both directed and undirected graphs. For example, the state-of-the-ar sampling based methods for spectral sparsification are only applicable undirected graphs (Spielman & Srivastava [011;: Koutis et al. 2010; SSpielman & Teng 2014): the latest algorithmic breakthrough in spectral sparsification of directed graphs (Cohen al. 2017 2018) can only handle strongly-connecte which inevitably limits its applications when confronting real-world graphs, since many directed graphs may not be strongly connected, such as the graphs used in chip design automation (e.g., timing analysis) tasks as well as the graphs used in machine learning and data mining tasks.
directed graphs
A strongly connected directed graph is a directed graph in which any node can be reached from any other node along with direction.

---

Under review as a conference paper at ICLR 2021
Consequently, there is still pressing need for the development of highly-robust (theoretically- rigorous) and truly-scalable (nearly-linear complexity) algorithms for reducing real-world large-scale (undirected and directed) graphs while preserving key graph spectral (structural) properties. In summary, we make the following contributions:
We, for the first time, prove the existence of linear-sized spectral sparsifiers for general directed graphs, and introduces a practically-effcceent yet unified spectral sparsification approach that allows simplifying real-world, large-scale directed and undirected graphs with guaranteed preservation of the original graph spectra.
We exploit a highly-scalable (nearly-linear complexity) spectral matrix perturbation analysis framework for constructing ultra-sparse (directed) subgraphs that well preserve the key eigenvalues and eigenvectors of the original graph Laplacians. Unlike the prior state-of- the-art methods that are only suitable for handling specific types of graphs (e.g., undirected or strongly-connece the proposed approach is more general and thus will allow for truly-scalable spectral sparsification of a much wider range of real-world complex graphs.
directed graphs (Spielman & Srivastava [201 Cohen et al. (017)))
Through extensive experiments on real-world directed graphs, we show how the proposed directed graph spectral sparsification method can be exploited for computing PageRank vectors, directed graph clustering and developing directed graph Laplacian solvers.
The ppectrally-sparsifiee directed graphs constructed by the proposed approach will potentially lead to the development of much faster numerical and graph-related algorithms. For example, spectrally- sparsified social (data) networks allow for more efficient modeling and analysis of large social (data) networks; spectrally -ppasssif- neural networks allow for more scalable model training and processing in emerging machine learning tasks; spectrally-spariinne computations of personalized PageRank vectors; spectrally- spectrally-ppariffeed integrated circuit networks will lead to more efficient partitioning, modeling, simulation, optimization and verification of large chip designs, etc.
web-graphs allow for much faster
2 RELATED WORKS
Directed graph symmetrization. When dealing with the directed graph sparsification, it's natural apply symmetrization methods for converting asymmetric directed graphs into symmetric undi- rected graphs, so that we can apply the existing spectral graph theories for directed graphs after symmetrization. In the following, given directed graph or its corresponding adjacency matrix A we will review the most popular graph symmetrization methods:
A + AT symmetrization simply ignores the edges' directions, which is the simplest and most efficient way for directed graph symmetrization. However, edge directions may play an important role in directed graphs. As shown Figure ! edges (8, 1) and (4, 5) seem to have the equal importance in the symmetrized undirected graph A AT. However, in the original directed graph, edge (8, 1) is much more important than edge (4, 5), since removing edge (8, 1) will lead to the loss of more connections in the directed graph. For example, removing edge (4, 5) will only affect the walks from node 4 to any other nodes and walks from any other nodes to node 5. However, if we remove edge (8. 1) in the directed graph, it will not only affect walks from node to any other nodes and walks from any other nodes to node 1, there will be also no access from node 5 ,6, and any of nodes 1, 2, 3 and 4.
. Bibliographic symmetrization (Satuluri & Parthasarathy 2011 adopts AAT + +ATA A as the adjacency matrix after symmetrization to take the in-going and out-going edges into consideration. However, it cannot be scaled to large-scale graphs since it will create much denser undirected graphs after symmetrization. Also, disconnected graphs can be created due to the AAT + A A symmetrization, as shown in Figure]
Random-walk symmetrization (Chung. 2005) is based on random walks and allows normalized cut to be preserved after symmetrization. This is also the symmetrization approach used in recent work for spectral sparsification of directed graphs (Cohen et al. 2017). However, it only works
cronnglycoonecttdd aperiodic directed graphs. For
The concept the adjacency matrix for the directed graph will be further introduced Section 3.1
2

---

Under review as a conference paper at ICLR 2021
Co
(1)
(II)
(III)
(IV)
Figure I: Converting directed graph G' in (I) into undirected graphs using A + A shown in (II),
AA + +AA as shown (III), and the proposed LGLE symmetrization as shown in (IV).
Table I: Summary of symbols used in this paper
Before symmetrization
After symmetrization
G (V. Eg, Wo): directed (undirected) graph
G. (V, EG.. Wo,): undirected graph
= (V, Es, Wg): sparsifier of graph G
S, = (V, Es, ws.): sparsifier of graph G2
Lg: Laplacian matrix of graph G
Lo.: Laplacian matrix of graph G,,
Lg: Laplacian matrix of sparsifier
Ls,: Laplacian matrix of sparsifier S,
example, we can not apply the random-walk based symmetrization for the directed graph shown in Figure since it's periodic directed graph.
Cheeger's inequality for directed graphs. In undirected graph problems, Cheeger's inequality plays a significant role in spectral analysis of undirected graphs, which connects Cheeger constant (conductance) with spectral properties (eigenvalues of the graph Laplacian matrix) of graph. In (Chung, 2005) the Cheeger's s inequality has been extended to directed graphs based on the random- walk Laplacian symmetrization scheme, smallest eigenvalue of the directed graph Laplacian. However, the related theoretical results can only be applied to strongly cronneyycoonecttd and aperiodic directed graphs, which rare in real-world applications.
mentioned earlier. It also provides the bound for the
Spectral sparsification of directed graphs. The latest algorithmic breakthrough in spectral sparsification for strongly-connected aperiodic graphs has been introduced based on the results in CCungg 2005), which proposes convert dtoogly-comnecter graphs into Eulerian graphs via Eulerian scaling, and subsequently sparsify the undirected graphs (obtained via directed graph symmetrization (Chung 2005)) leveraging existing undirected graph spectral sparsification methods (Cohen et al.. 2017). It has been shown that such an approach can potentially lead to the development of almost- linear-time algorithms for solving asymmetric linear systems, computing the stationary distribution of a Markov chain and computing expected commute times in a directed graph, etc (Cohen et al.
2017 2018).
A THEORETICAL FRAMEWORK FOR UNIFIED SPECTRAL SPARSIFICATION
3.1 LAPLACIANS FOR DIRECTED AND UNDIRECTED GRAPHS
Consider directed graph G (V, EGg, wa) with V denoting the set of vertices, Eg representing the set of directed edges, and WG denoting the associated edge weights. Let n = [V] , m = FEg be the size of node and edge set. the following, we denote the diagonal matrix by DG with (o(i, i) being equal to the (weighted) outdegree of node i, as well as the adjacency matrix of G by Ag:
Ac(i,j) - ( (i, if (i..) E Fie -
otherwise
Then the directed Laplacian matrix can be constructed as follows (Cohen et al. 2017
Le DG A For better illustration, we have summarized symbols used our paper Table
can be shown that any directed (undirected) graph Laplacian constructed using (3.1 will satisfy the following properties: I) Each column (and row) sum is equal zero: II) All off-diagonal elements
are non-positive; III) The Laplacian matrix asymmetric (symmetric) and indefinite (positive semidefinite).
3

---

Under review as a conference paper at ICLR 2021
3.2 SPECTRAL SPARSIFICATION OF (UN)DIRECTED GRAPHS
Graph sparsification aims to find a subgraph (sparsifier) S = (V, wg) that has the same set of vertices but much fewer edges than the original graph G. There are two types of sparsification methods: the cut sparsification methods preserve cuts in the original graph through random sampling of edges (Benczúr & Karger 1996), whereas spectral sparsification methods preserve the graph spectral (structural) properties, such as distances between vertices, effective resistances, cuts in the graph, well as the stationary distributions of Markov chains (Cohen et al. 2017]] 2018) (Spielman & Teng 2011). Therefore, spectral graph sparsification is a much stronger notion than cut sparsification.
For undirected graphs, spectral sparsification aims to find ultra- subgraph proxy that is seectrally-similas to the original one. G and S are said to be o-spectrally similar if the following condition holds for all real vectors RV:
x Lgx
I x LGX I ox Lgx,
(2)
where LG and Lg denote the symmetric diagonally dominant (SDD) Laplacian matrices of graphs G and S, respectively. Relative condition number can be defined as K[LG, Lg) S o², implying that smaller relative condition number or o² corresponds to a higher (better) spectral similarity between two graphs.
For directed graphs greectrum-preservinng LG LG symmetrization the subgraph S can be con- sidered spectrally similar to the original graph G if the condition number the ratio between the largest and smallest singular values of Lş LG is close to (Cohen et al. 2017: 2018). where Lg de- notes the Moore-Penrose pseudoinverse of Lg. Spectral sparsifcation of directed graphs is equivalent
to finding an ultra-sparse subgraph S such that the condition number of (Lg LG) (Lş LG) is small enough. Since the singular values of Lğ LG are the square roots of eigenvalues of LG) (Lğ
LL).
While (L LG) T (Lg (L&L5) )+ (L L.). They do share the same eigenvalues under special conditions according to the following theorem (Horn & Johnson 2012
LG) can be written into LE (L LG. LG (LوLğ) L
LG is not equal to
Theorem 3.1. Suppose that matrices X E Rmm'n and Y E IR'''' with m' S n'. Then the n' eigenvalues of YX are the m'' eigenvalues of XY together with -m' zerves; that is pvx (t) = pm'-m' Pxy (t). mn' = n'' and at least one of X or Y is nonsingular, then XY and YX are similar.
Based on Therorem 3.1 (L$L))) *LL and (L ( share the same eigenvalues when a small value is added on each diagonal of LG. Under this condition, spectral sparsification of directed graphs is equivalent to finding an ultra-sparse subgraph S such that the condition number of (IsLg) )+ (LG LG) ) is small enough. Theorem 3.2 shows both LGLG and LsLg are the Laplacian matrices for some undirected graphs.
Theorem 3.2. For any directed graph G = (V, FG) and its directed Laplacian LG, its sym- metrized undirected graph G = (V, F.G,; wG..) can be obtained via Laplacian symmetrization LG. LG LG LG., is positive semi-definite (PSD) and will have the all-one vector its null space, while the corresponding undirected graph may include negative edge weights.
The proof is in the Appendix. If we can prove that there exists an ultra-sparse subgraph S such that its corresponding undirected graph S., (with Ls,, = LgLg) ) is the spectral sparsifier of G (with LG., LGLG) then the directed subgraph S becomes the spectral sparsifier of G More detailed proofs are shown in the Appendix. The core idea of our approach is to leverage novel -eierrrvinn Laplacian symmetrization procedure convert directed graphs into undirected ones that may have -eeghtee edges (as shown in Figure I Such a Laplacian symmetrization scheme will immediately allow us exploit existing methods for spectral sparsification.
A PRACTICAL FRAMEWORK FOR UNIFIED SPECTRAL SPARSIFICATION
To apply our theoretical results to deal with real-world directed graphs, the following concerns should be addressed in advance:
The undirected graph LaLE may become too dense to compute and thus may impose high cost during spectral sparsification.
4

---

Under review as a conference paper at ICLR 2021
It can be quite challenging to convert the sparsified undirected graph to its corresponding directed sparsifier Lg, even when Ls,, is available.
To address the above concerns for unified spectral graph sparsification, propose practically- efficient framework with following desired features: 1) our approach dose not require to explicitly compute LG but only the matrix- multiplications; 2) approach can effectively identify the most spectrally-critenn though our approach requires compute L the Ls., matrix density can be effectively controlled by carefully pruning spectrally-similar edges through the proposed edge similarity checking scheme.
edges for dramatically decreasing the relative condition number, 3) al-
4.1 INITIAL SUBGRAPH SPARSIFIER CONSTRUCTION
Motivated by the recent research low-stretch spanning trees Elkin al. 2008 Abraham &
Neiman 2012) and spectral perturbation analysis (Feng, 2016 2018) for nearly-linear- innar--iiee spectral sparsification of undirected graphs, we propose practically-effic general directed graphs by first constructing the initial subgraph sparsifiers of directed graphs with the following procedure:
algorithm for sparsifying
Compute D- (AA + +G) as a new adjacency matrix, where denotes the diagonal matrix with each element equal to the row (column) sum of (Ag + AG). Recent research shows such split transformations effectively reduce graph irregularity while preserving critical graph connectivity, distance between node pairs, the minimal edge weight in the path, as well as outdegrees and indegrees when using push-based and pull-based vertex-centric programming (Nodchi Sabet et al. 2018).
Construct a maximum spanning tree (MST) based on D (AA + AT). which allows us to effectively control the number of outgoing edges for each node so that the resultant undirected graph after Laplacian symmetrization will not be too dense.
Recover the direction of each edge in the MST and make sure each node of its sparsifier has at least one outgoing edge if there are more than one in the original graph for achieving stronger connectivity in the initial directed sparsifier.
4.2 SPECTRAL SPARSIFICATION VIA RIEMANNIAN DISTANCE MINIMIZATION
The Riemannian distance d2 between positive definite (PSD) matrices is arguably the most natural and useful distance the positive definite cone S [Bonnabel & Sepulchre 2010), which can be computed by (Lim et al. 2
1/
ST R+ and (2 LG.)
Σ log X
where Amax = A1 2 ... 2 An 2 12 2... denote the descending eigenvalues of L LG,, and V1, V2, ... Vn denote the corresponding eigenvectors. Since both S, and G, are PSD matrices, we have 2 0, which leads to the following inequality:
Xa
1 X
(2 LG.)
log A
log
max(n log d n log
The Courant-Fischer theorem allows computing generalized eigenvalues and cigenvectors by:
I
LG.
An min x LG_
\ max
x 00
x5 Ls
00, x T.L_,
1=0
1=0
where 1 E IR" denotes the all-one vector. Assigning each node in the graph with an integer value either or 1, the corresponding Laplacian quadratic form measures the boundary size (cut) of node set. For example, if node set Q is defined as subset when its nodes are all assigned with an integer value while other nodes are assigned with value 0, then node set Q and its boundary dG (Q) can be represented as
Q {p V x -} and (Q) (p..) E P.peQ.qe Q. Q).
(6)
5

---

Under review as a conference paper at ICLR 2021
Since the number of outgoing edges crossing the boundary can be computed by x² La. |d.. (Q)), the following holds:
x L...
x: LGG.
[Q).(Q)1 [as. (Q))
A1
max
max l A4, ((p)
(7)
20, I
Ls
x LT
1=0
which implies that the maximum mismatch between G2 and S, will be bounded by A Leveraging the dominant generalized eigenvectors will allow us identify the edges crossing the maximally- mismatched boundary 0c. (Q). Including such crossing edges into S, will dramatically decrease
the maximum mismatch (A1), thereby improving spectral approximation of the sparsifier. Conse-
quently, the following problem formulation for spectral graph sparsification is proposed:
2 LG L. x
min
max
+ B1
(8)
which allows effectively minimizing the largest generalized eigenvalue (upper bound of mismatch) and the Riemaninan distance (62) by including the minimum amount of edges into the subgraph Su.
4.3 A UNIFIED SPECTRAL PERTURBATION ANALYSIS FRAMEWORK
As aforementioned, spectral sparsification of (un)directed graphs can be effectively achieved by solv- ing B To this end, we will exploit the following spectral perturbation analysis framework. Given the generalized eigenvalue problem LG. Vi \ with i = 1, R, let matrix V = [Vi,"** Vnl. Then V; and X can be computed satisfy the following orthogonality requirement:
LG.. Vj = Axp i= and v. Ls Vj (0
1, i=j
0,
i #
i i
Consider the following first-order generalized eigenvalue perturbation problem:
LG (vi + dvs) (A1 + (Ls) + .oss)) 8vv),
(10)
where a small perturbation LLg in Ls.. is introduced, leading to the perturbed generalized eigenval- and eigenvectors X; + 5A; and vi 8v; By only keeping the first-order terms, 10 becomes:
LG. ōv: = \ ov; + AjoLs. vi + d'ILs. Vi.
(11)
Let ōv: Ej Disyi, then can be expressed as:
Σ LhiLL VJ = \sL.s E (llr)) + ALoLs vi + d'ILs.
(12)
Based on the orthogonality properties in multiplying to both sides of 12 results in
XpoLs vi + 8AL = O.
(13)
Then the task of spectral sparsification of general (un)directed graphs will require to recover few as possible extra edges to the initial directed subgraph S such that the largest eigenvalues, or the condition number of L5, LG, can be dramatically mitigated. Expanding (3) will simply lead to:
5A; A
vv; ÖLs Vi.
(14)
Expand ØLs, with only the first-order terms as ILs, SL LsōLg, where ōLs wo(p, Cp for (p.q) EG Es. Op E R" denotes the vector with only the p-th element being 1 and others being 0, and Cp.q Cp Cq. The spectral sensitivity for each off-subgraph edge (p, 9) can be expressed as:
Sp.9 v; (ōLgL3 + LLSLL)
(15)
is obvious that (5) can be leveraged to rank the spectral importance of each edge. Consequently, spectral sparsification of general graphs can be achieved by only recovering few dissimilar edges

---

Under review as a conference paper at ICLR 2021
with large sensitivity values. In this work, the following method based on t-step power iterations is proposed to achieve efficient computation dominant generalized eigenvectors
V1 h. (Lg LG.)"h
(16)
where ho denotes random vector. When the number of power iterations is small (e.g.. f I 3), ha will be a linear combination of the first few dominant generalized eigenvectors corresponding to the largest few eigenvalues. Then the spectral sensitivity for the off-subgraph edge (p, can be approximately computed by
Sp.9 = h (ōLgLS + Lg hnp
(17)
The computation of h, through power iterations requires solving the linear system equations Ls, x = b for / times. We note that only Ls, need to be explicitly computed for generalized power iterations. The latest Lean Algebraic Multigrid (LAMG) solver has been leveraged for computing hr which can handle undirected graphs with negative edge weights and achieve ((m) runtime complexity for solving large graph Laplacian matrices (Livne Brandt 2012).
4.4 EDGE SPECTRAL SIMILARITIES
To avoid recovering redundant edges into the subgraph, it is indispensable to check spectral similarities between candidate subgrahg edges. In other words, only the subgrahh edges that are spectrally critical (have higher spectral sensitivity scores) but not spectrally-simile to each other will be recovered to the initial subgraph. To this end, we exploit the following spectral embedding of off-subgraph edges using approximate dominant generalized eigenvectors h, computed by (16):
Tp.q = h, e he,
(18)
which will help estimate spectral similarities among different ofb-sabgraph edges. To improve the accuracy, we can always compute r Ollog n) approximate dominant generalized eigenvectors
h ..... "',,..,,", hn
obtain r-dimensional spectral embedding vector Tp.g for each edge (p. q). The edge spectral similarity between two edges (pi, 9:) and (pj, 9ÿ) is defined as follows:
P., = T |Tpp.q Py ll [ll//xx(|| p. (
(19)
If (1-1-31 Br,)) o for given constant p. edge (pi, qi) is considered spectrally dissimilar with edge 4j).
4.5 ALGORITHM FLOW AND COMPLEXITY
Algorithm Algorithm Flow for Directed Graph Sparsification
Input: LG, Lg, douts itermax: Atimit+ O,, @
1: Calculate largest generalized eigenvector hr, largest generalized eigenvalue Amax and let iter
2: while Amax < Atmitt iter < iter do
3: Calculate the spectral sensitivities Sp.g for each off-subgraph edges (p. 9) E Egysi
4: Sort spectral sensitivities in descending order and obtain the top a% off-subgraph edges into
edge list Ens = [p1, 41), (p2, ?2)....;
5:
Do Eaddlia Edge_Sineg Similaritiiss Checking( Emsa LG, Lg dout 0)
6:
Update Snew = + Extalist and calculate largest generalized eigenvector htnws, largest gener-
alized eigenvalue Amaxnew based LG and Lsnew
7:
if Xmaaxnew < Amax then
8:
Update S Snew, h4 htnews Amax Amaxnew
9:
end if
10: iter iter + 1;
11:
end while
12: Return graph S and Lg.
Algorithm|| Srrrithhm[shoeee shows the algorithm flow for directed graph sparsification, where LG is the Laplacian matrix for original graph, Lg is the Laplacian matrix of initial spanning tree, d is the user-defined outgoing degree for nodes, itermax the maximum number of iterations, and Atimit is the desired maximum generalized eigenvalue. Ex Edge_Sime SiimilaitiessChhckkiii Eliss LG, Ls, dont, @) is introduced in the Appendix. The complexity has been summarized follows:
7

---

Under review as a conference paper at ICLR 2021
Table 2: Results of directed graph spectral sparsification
Test Cases
Vel
|Eal
time (8)
gre
II3
1.IE2
4.2E2
0.46
0.71
0.05
8.284X
gre 183
L8E2
1.0E3
0.33
0.46
0.14
9.8E3X
harvard500
0.5E3
2.6E3
0.31
0.40
0.64
1.2E3X
celli
0.7E4
3.0E4
0.31
0.57
3.10
1.0ESX
pesa
1.2E4
8,054
0.27
0.51
8.80
5.3E8X
big
1,3E4
0,9E5
0.27
0.49
12.86
4,1ETIX
gre__10 1107
1,1E3
5.6E3
0.26
0.39
0.24
58X
wordnet3
0.8E5
1,3E5
0.64
0.84
50.00
12X
12p-Gnutella3'
0.6E5
1,5E5
0.35
0.43
11.90
6X
p2p- 0D--Gnnutell005
8.8E3
3,2E4
0.23
0.65
27.59
35X
mathworks100
1.0E2
5,5E2
0.20
0.50
0.04
30X
0.04
15
10
0.08
THE 18
0.00
0.06
0.00
0.04
0.01
0.02
(8%)
| Re
Figure 2: Runtime scalability for 110_ (left), big (middle), gre_115 115 (right)
(a) Generate an initial subgraph S from the original directed graph in O(m log or O(m n log n) time;
(b) Compute the approximate dominant cigenvector h, and the spectral sensitivity of each off-subgraph edge (m) time;
(c) Recover a small amount of spectrally-dissinn dissimilar off-suhgraph edges into the latest subgraph S according to their spectral sensitivities and similarities in ((m) time;
(d) Repeat steps (b) and (c) until the desired condition number or spectral similarity is achieved.
EXPERIMENTAL RESULTS
The proposed algorithm for spectral sparsification of directed graphs has been implemented using MATLAB and C++. Extensive experiments have been conducted evaluate the proposed method with various types of directed graphs obtained from public-domain data sets (Davis & Hu 2011).
Table shows comprehensive results on directed graph spectral sparsification for a variety of real- world directed graphs using the proposed method, where [[al( denotes the number of nodes (edges) for the original directed graph G; Eg and EE| denote the numbers edges in the initial subgraph 5 and final spectral sparsifier S. Notice that we will directly apply the Matlab's "eigs" function if the size of the graph is relatively small ([Ego) < 1E4); otherwise we will switch to the LAMG solver for better efficiency when calculating the approximate generalized eigenvector h,. We report the total runtime for the eigsolver using either the LAMG solver or "eigs" function. A As,fin
denotes the reduction rate of the largest generalized eigenvalue of L LG..
Figure 2 shows the runtime scalability regarding to the number of off-subgraph edges (Fadded added the final sparsifier for graph gre_1107 (left), big (middle) and gre_115 see, the runtime scales linearly with the added number of edges for all three graphs.
115 (right). As we can
Since there our proposed method with the existing undirected graph sparsification solver GRASS (Feng 2016 2018). To make the directed graphs graphs into undirected ones (G',) using A + AT symmetrization. Then undirected graph sparsifiers S will be generated by GRASS. Finally, the final directed graph sparsifiers be formed by adding the edge directions to the obtained undirected sparsifiers S The experimental results are shown in Table 3. where represents the relative condition number between the original graph and its final
other existing directed graph sparsification methods to be compared, compare
be applied to the GRASS, first convert the directed
8

---

Under review as a conference paper at ICLR 2021
Table Comparison of spectral sparsification results between the proposed method and GRASS.
GRASS
Our method
Test cases Egg
LL
Ls
Es
((LL Ls)
Es
(LG, Ls)
[Eg
Ed
gre_113 115
0.92
28
0.44
3760
0,43
522
gre_18 -85
0.67
25
0,40
1140
0,41
170
1107
0.86
9
0.43
2790
0,43
147
harvard500
0.36
13
0.39
5.22F5
0.36
2.40E4
SBp-GnutellaOSS
0.56
6
0.57
3,90ES
0.54
1.90E5
1 big 0.60
0.68
3
0.68
1.0E5
0.68
8.20F4
7
0.60
8803
0.60
270
wordnet3
0.78
8
0.79
3.06E4
0.78
2.74E3
Table 4: Comparison of GMRES results.
No preconditioner
ILU preconditioner
Spar. preconditioner
Test
relres
iter
der
Tunl
dter
K K[LG, Ls)
gre 115
IE-7
64
22
536
17
336
16
gre 185
185_185
1E-7
53
27
1,190
23
768
19
gre 1107
1B-7
118
24
6,771
22
4,327
18
harvard500
1E-7
80
25
3,563
18
2,527
20
big
1E-7
356
163
104,674
64
72,509
108
peta
1B-7
NC
241
91,304
85
67,007
28
sparsifier. By keeping the similar number of edges in the sparsifiers, observe that our method can achieve much better sparsifiers than GRASS does.
More results regarding the directed graph sparsification are shown in Appendix.
The directed graph sparsifier can also be directly utilized the preconditioner for directed Laplacian solver when solving the linear system equation Lx b with iterative solvers such as generalized minimal residual method (GMRES) (Saad Schultz 1986). Table Isoows comprehensive results for GMRES iterations when no preconditioner is applied, Incomplete LU factorization (ILU) as the preconditioner is applied, and the directed sparsifier Laplacian Ls as the preconditioner applied. The MATLAB functions gmres and ilu with default setting are applied in our experiments. "relres" is the relative residual be achieve for three methods, "iter" is GMRES iteration number, "nnz" is the number of non-zeros in the preconditioner, and "NC" represents it did not converge when reaching maximum number of iterations (which is 500 in the experiments). We can conclude that GMRES with directed graph sparsifier the preconditioner has better convergence rate when comparing to the other two methods. Meanwhile, the sparsifier has much fewer number of non-zeros than ILU preconditioner. More results directed graph Laplacian solver can be found in Appendix.
In the end, we also demonstrate the applications of our proposed directed graph sparsification in solving directed graph Laplacians using both direct method and iterative method, as well as the applications in computing (Personalized) PageRank vectors and directed graph partitioning in Appendix.
CONCLUSIONS
For the first time, this paper proves the existence of linear-sized spectral sparsifiers for general directed graphs, and proposes a practically-effccien yet unified spectral graph sparsification framework. Such novel spectral sparsification approach allows sparsifying real-world, large-scale directed and undirected graphs with guaranteed preservation of the original graph spectral properties. By exploiting highly- sccllabe (nearly-linee) complexity) spectral matrix perturbation analysis framework for constructing nearly-lineat sized (directed) subgraphs, enables us to well preserve the key eigenvalues and eigenvectors of the original (directed) graph Laplacians. The proposed method has been validated using various kinds of directed graphs obtained from public domain sparse matrix collections, showing promising spectral sparsification and partitioning results for general directed graphs.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Ittai Abraham and Ofer Neiman. Using petal-decompositions to build a low stretch spanning tree. In Proceedings of the forty-fourth annual ACM symposium Theory of computing (STOC), pp- 395-406. ACM, 2012.
Joshua Batson, Daniel Spielman, and Nikhil Srivastava. Twice-Ramanujan Sparsifiers. SIAM Journal on Computing, ( 700-112111 2012.
András A Benczúr and David R Karger. Approximating minimum cuts in ő (n 2) time. In Proceedings of the twnnty-eighth annual ACM symposium on Theory of computing (STOC), pp. 47-55. ACM, 1996.
Silvere Bonnabel and Rodolphe Sepulchre. Riemannian metric and geometrie mean for positive semidefinite matrices of fixed rank. SIAM Journal on Matrix Analysis and Applications, 31(3): 1055-1070, 2010.
W. Briggs. A multigrid tutorial. SIAM Press, 1987.
Christiano, J. Kelner, Madry, D. Spielman, and Teng. Electrical flows, laplacian systems. and faster approximation of maximum flow in undirected graphs. In Proc. ACM STOC, pp. 273-282, 2011.
Fan Chung. Laplacians and the cheeger inequality for directed graphs. Annals of Combinatorics, (1):1-19, 2005.
Michael B Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B Rao, Aaron Sidford, and Adrian Vladu. Almost-linear-timg algorithms for markov chains and new spectral primitives for directed graphs. In Proceedings of the 49th Anmual ACM SIGACT Symposium on Theory of Computing, pp. 410-410-41 419.419. ACM, 2017.
Michael B. Cohen, Jonathan Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup Rao, and Aaron Sidford. Solving Directed Laplacian Systems in Nearly-Lineal Time through Sparse LU Factorizations. In Foundations of Computer Science (FOCS), 2018 59st Annual IEEE Symposium on, pp. 898-909, IEEE, 2018.
T. Davis and Y. Hu. The university of florida sparse matrix collection. ACM Trans. on Math. Soft. (TOMS), 11,1),1,22 2011.
Michael Elkin, Yuval Emek, Daniel Spielman, and Shang-Hua Teng. Lower-stretch spanning trees. SIAM Journal on Computing, 38(2):608-628) 2008
Zhuo Feng. Spectral graph sparsification in wearly-linear time leveraging efficient spectral perturbation analysis. In Proceedings of the 53rd Annual Design Automation Conference, pp. 57. ACM, 2016.
Zhuo Feng. Similarity-awand spectral sparsification by edge filtering. In Design Automation Confer- ence (DAC), 2018 55nd ACM/EDAC/ΣEE. IEEE, 2018.
Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
Jonathan A Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. An commost-linnare time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In Proceedings of the twenty-fitth annual ACM-SIAN symposium Discrete algorithms, pp. 217-226 SIAM, 2014.
Pavel Kolev and Kurt Mehlhorn. note on spectral clustering. arXiv preprint arXiv: 150909980 2015.
I. Koutis, G. Miller, and R. Peng. Approaching Optimality for Solving SDD Linear Systems. In Proc. IEEE FOCS, pp. 235-244, 2010.
Yin Tat Lee and He Sun. An SDP-based Algorithm for Linear-sized Spectral Sparsification. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pp. 678-687, New York, NY, USA, 2017. ACM. ISBN 978-1 3055477. URL http: //tt:://do http:////....oocooooo.....///...
doi: 10.1 145/3055399
10

---

Under review as a conference paper at ICLR 2021
Lek-Heng Lim, Rodolphe Sepulchre, and Ke Ye. Geometric distance between positive definite matrices of different dimensions. IEEE Transactions on Information Theory, 65()):5401-5505. 2019.
O. Livne and A. Brandt. Lean algebraic multigrid (LAMG)): Fast graph Laplacian linear solver. SIAM Journal on Scientific Computing, 34(4):B499-BB --22- 2012.
Fragkiskos D Malliaros and Michalis Vazirgiannis. Clustering and community detection in directed networks: survey, Physics Reports, 533(4))95-142,, 2013.
Giovanni De Micheli. Synthesis and optimization of digital circuits. McGraw-Hill Higher Education, 1994.
Amir Hossein Nodehi Sabet, Junqiao Qiu, and Zhijia Zhao. Tigr: Transforming irregular graphs for gpu spu-friendly graph processing. In Proceedings of the Twenty- Third International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 622-62226666 636. ACM, 2018.
Richard Peng, He Sun, and Luca Zanetti. Partitioning well-clustered graphs: Spectral clustering works. In Proceedings of The 28th Conference on Learning Theory (COLT), pp. 1423-1455, 2015.
Youcef Saad and Martin H Schultz. Gmres: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM Journal on scientific and statistical computing, 7(3):856-866 869, 1986.
Venu Satuluri and Srinivasan Parthasarathy. Symmetrizations for clustering directed graphs. In Proceedings of the 14th International Conference on Extending Database Technology, pp. 343-354. ACM, 2011.
D. Spielman and S. Teng. Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM Journal on Matrix Analysis and Applications, 35(3): 835-885, 2014.
D. Spielman and Shanghua Teng. Spectral partitioning works: Planar graphs and finite element meshes. In Foundations of Computer Science (FOCS), 1996. Proceedings. 37th Annual Symposium on, pp. 96-105. IEEE, 1996.
Daniel Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 10(6):193311266, 2011.
Daniel Spielman and ShangHua Teng. Spectral sparsification of graphs. SIAM Journal Computing, 1014), 2011.

---

Under review as a conference paper at ICLR 2021
e1
e2
Figure 3: Edge coupling during directed Laplacian symmetrization.
APPENDIX
7.1 PROOF OF THEOREM
Proof. Each element (i.j) in LG,, can be written as follows:
- LG, (1.5) = Ex (-A((t;))A((tt.) + Ac(k:)) Da(k
i= (20)
i i
It can be shown that the following is always true:
LG. (1.1)+ + Σ Lo.((.)) (..)))) Σ Loli,)) >E
3852
(21)
Lol(ik Lolink) +
koliik) O, 3.59
which indicates the all-one vector is the null space of LG.. For directed graphs, can be shown that if a node has more than one outgoing edge, in the worst case the neighboring nodes pointed by such outgoing edges will form clique possibly with negative edge weights in the corresponding undirected graph after symmetrization.
As example shown in Figure when edge e2 is added into the initial graph G' that includes single edge e1, an extra edge (shown in red dashed line) coupling with el will be created in the resultant undirected graph Gui similarly, when an edge e3 is further added, two extra edges coupling with el and e2 will be created in G.. When the last edge e4 added, forms clique. Also, it can be shown that G2 will contain negative edge weights under the following condition:
(AAc(k:)DDo(k:))) Do(i,) Acc(k.))Ac(k..))
(22)
In some cases, there may exist no clique even though all outgoing edges according to one node are added into subgraph only because the weights of these edges satisfy
[AAG(t,))Dc(t.))) De(i,))
Σ Ak, (A)(k)))))))))))
(23)
7.2 EXISTENCE OF LINEAR-SIZER SPECTRAL SPARSIFIER FOR DIRECTED GRAPHS
Existing spectral sparsification methods for undirected graphs (pielman & Teng 2011 Batson et al. 2012 Feng 2016 not handle undirected graphs with negative-weighht edges. So have to first prove the existence of spectral sparsifier for undirected graph with -eeative-weighted edges, or the existence of linear-sized spectral sparsifier for directed graphs
12

---

Under review as a conference paper at ICLR 2021
e1
3
0
-11
B
0
-1
C=
0
-1
1
e2,
0
1
-1
0
-1
-1
1
0
--1
0
2
0 1
0
07
1 -1
0
0
0
W
LG B WC- =
0
2 -1
0
-1
0
0
0
1
Figure 4: Forming a directed Laplacian with B and C matrices.
Theorem 7.1. For given directed graph G and its undirected graph G., (V, EG WG.) obtained via Laplacian symmetrization, there exists (1 + e)-spectral sparsifter S with (n//²) edges such that its undirected graph Su (V, Fis., wss) after symmetrization satisfies the following condition for any x E R
(1 (1-c)x- LG,x x S(1 + c)x LG.X.
(24)
Before proving Theorem 7.1 for symmetrized undirected graph G. with negative edge weight, need to introduce the following lemma 7.2 Batson et al. 2012).
Lemma 7.2. Let d > O, and u1, U2.... um denote a set of vectors in R2 that allow expressing the identity decomposition
Σ 1sism
inn = idgn,
(25)
where id E Raxx denotes the identity matrix. Then there exists series of nonnooneeeee men-atttive coefficients [t.) with li: + 0l S dn so that
x idgux Σ lix "nu x 5(1 + e)x idzex. Vx E R
(26)
Proof. Lemma (72
proves the existence of the sparsifier for an undirected graph with positive
weight edges. We have to extend the above lemma to prove the existence of the sparsifier for
symmetrized undirected graph with negative weight edges. The key of our approach is construct
set of vectors U1 um in R" such that can be expressed as identity decomposition 225
To construct ug the Laplacian of undirected graph be written LG B T WTB (Spielman & Srivastava 201 where B B,x the signed edge-vertex incidence matrix:
if is i-th edge's head B(i,u) { if i-th edge's tail otherwise
(27)
W Wmxm is the diagonal matrix with W ( i) = w;. The Laplacian matrix of a directed graph can be written as LG =B -WC, where Caxo injection matrix defined as:
1 if is i-th edge's head
C(i
0 if is i-th edge's tail otherwise.
(28)
13

---

Under review as a conference paper at ICLR 2021
Figure 4 shows example for constructing directed Laplacian matrix based B and C matrices.
the following, we show how to construct the vectors uj The undirected Laplacian after symmetriza- tion can be written LG. = B WoB with W. = WCC W. Since LG., and its Pseudoinverse
LG., can be written as
LG. = Σ
Xujuf
LG = -
(29)
jm1
j-1
it can be shown that LG., L. = Ej= ujuj = idLa, where idLa, is the identity on im (L..) ker(Le.)". Consequently, U Unx matrix with u for i 1, m its column vectors can be constructed as
Unxm [u Um
L G.
BTW
(30)
can be shown that Un Unxm will satisfy the following equation:
Unxm Unxm T = Σ iiui = LG. +/2B W.BLG. +
(31)
LG. LL LG..
+T/2 idLo.
According to Lemma 7.2, can always construct diagonal matrix T Rmxm with its i-th diagonal element. Then there will be at most O(n/e²) positive diagonal elements in T, which allows constructing Ls., B TwT that corresponds the directed subgraph S for achieving (1+ + e)-spectral approximation of G' as required by (24). It can be shown that each un with nonzero & coefficient corresponds the outgoing edges pointed by the same node. Consequently, for directed graphs with bounded degrees, there will be O(n/E)) 2²) total number of directed edges in the + -sppecraal sparsifier S.
7.3 ALGORITHM FLOW
Algorithm 2 Edge Similarities_ SimilaritissCChckinng
Input: Ess, LG, Ls. dous, 0
1: Perform I-step power iterations with r (log n) initial random vectors bb..... 11 compute
approximate dominant generalized eigenvectors ((2) ...,, h("),
2: Compute a r-dimensional embedding vector Tp..: E IR" for V(p,, q:) E Eist
3: let Faatiis ((pı;:));;
4: for i=2: Fisse] do
5: Calculate the spectral similarity score Br, between (p., and every edge (pjs q3) in Examat
6: if B1., 0, for ((ps, 9j) E Enaman then
7: Eusais = [Enddiss (pr, 2:)];
8: end
9:
end for
10:
Return Eusiiiee
7.4 RESULTS OF DIRECTED GRAPH SPARSIFICATION
Figure 5 shows the spectral sensitivities of all the off-subgraph edges (c2 to e19 represented with blue color) both directed and undirected graphs calculated using MATLAB's s "eigs" function and the proposed method based (17p using the LAMG solver, respectively. Meanwhile, the spectral sensitivities all the off-subgraph edges (c2 to e19) with respect to the dominant eigenvalues (Amaz or X1) in both directed and undirected graphs are plotted. We observe that spectral sensitivities for directed and undirected graphs are drastically different from each other. The reason is that the spectral sensitivities for off-subgraph edges in the directed graph depend the edge directions. It is also observed that the approximate spectral sensitivities calculated by the proposed I-step power iterations with the LAMG solver match the true solution very well for both directed and undirected graphs.
14

---

Under review as a conference paper at ICLR 2021
40
39
88
22
21
40
39
38
23
22
21
018
619
e18
2
18
19
20
19
20
Spectral sensibiity score
10
Spectral sensitivity soore
MATLAB eige sovier
LAMG solver
MATLAB eigs sovier
LAMG solver
15
Edge Index
Edge Index
Figure 5: The spectral sensitivity scores of off-subgraph edges (e2 e19 in blue) for the undirected (left) and directed graph (right).
107
Mmax reduction rate
102
Hmax reduction rate
10
10
100
0
0.1|Eal
0.2|EG
0.3/Eg1 0.4|Egl
0.05|E 0.1|Eg1 0.15|Egl 0.2|Eg 0.25|E,
Added off-subgraph edges
Added off-subgraph edges
Figure 6: Largest generalized eigenvalue reduction rates for "gre_115" 115" (left) and "pesa" (right).
We plot the detailed reduction rates of the largest generalized eigenvalue when adding different number of off- off-subgraph edges to the sparsifiers of graph "gre_1 11s_ and "peta" in Figure 6 It shows that the largest generalized eigenvalue can be effectively reduced if sufficient off-subgraph edges are included into the sparsifier.
7.5 APPLICATIONS IN DEVELOPING DIRECTED LAPLACIAN SOLVER
Consider the solution of the following linear systems of equations:
Lx
(32)
Recent research has been focused on more efficiently solving the above problem when is Laplacian matrix of undirected graph (Kelner et al.) 2014 Koutis et al., 2010). In this work, we will mainly focus on solving nonsymmetric Laplacian matrices that correspond to directed graphs.
7.5.1 DIRECT METHOD FOR DIRECTED LAPLACIAN SOLVER
Lemma 7.3. When solving 32g, the right preconditioning system applied, leading to the following alternative linear system of equations:
LG.Y= =
(33)
where vector b will lie in the left singular vector space. When the solution of 33 is obtained, the solution of 32 is given by L
is obvious that solving the above equation is equivalent solving the problem of LG In addition, LG,, is Laplacian matrix of an undirected graph that can be much denser than LG- Therefore, we propose solve the linear system of Ls. b instead to effectively approximate 33 since Gs,, is sparser than GG. and more efficient to solve in practice.
b.
We analyze the solution errors based on the generalized eignvalue problem of LGp and Lsu- We have VLG. V = \ and VLs, V where V [V1, V2, vv.),, is the diagonal matrix with
15

---

Under review as a conference paper at ICLR 2021
10
10a
No precorditioner
precondioone
Relatie resituall
10
ILU preconditoner (nn2=91.300
Soar. pecondttoonr (n12267 (07)
Relative residual
10
Spar. preconditoner (nnz-72,509
precondiioner (nn7 -nn--104,674)
1
10
10
10
10
10
10000
10:30
50
100
150
200
250
300
350
400
450
500
0
50
100
150
200
250 300 350 400 450 500
Number of Iterations
Number of Iterations
(a)
(b)
Figure 7: GMRES convergence results for graphs of (a) pesa and (b) big
its generalized eigenvalues 2 on its diagonal. Since the errors can be calculated from the following procedure:
LGVY - L = LGU (y - y) + (LGu Ls 0,
(34)
write the term follows:
(y y) = LGG (LGu - Lsu)d.
(35)
Since y = Ei Vi the error can be further expressed as
(y y)= Σ
a
V4.
(36)
A
Therefore, the error term 336 can be generally considered a combination of high- sighffreuency errors (generalized eigenvectors with respect to high generalized eigenvalues) and low- low-frequency errors (generalized cigenvectors with respect low generalized eigenvalues). After applying GS relaxations, the high-frequeney етrоr terms can be efficiently removed (smoothed), while the low wow-frequency errors tend become zero if the generalized eigenvalues approach 1 considering approaching zero. As result, the error can be effectively eliminated using the above solution smoothing procedure.
x tends to be
In summary, the proposed directed Laplacian solver, the following steps are needed:
(a) We will first extract a spectral sparsifier Lg of a given (un)directed graph Lg Then, is pos- sible to compute an approximate solution by exploiting its spectral sparsifier Ls., = Ls via solving ý S. b instead.
(b) Then we improve the approximate solution ý by getting rid of the high-frequency errors via applying few steps of GS iterations (Briges 1987).
(C) The final solution is obtained from LTy.
Table 5: Relative errors between exact and approximate solutions of LGx = b w/ or w/o smoothing
Test Cases
gre_ 115
gre
gre_185|
185
celli
pesa
big
gre 1107
gr0_
wordnet3/
w/o smooth.
0.41
0.42
0.44
B.
4.3E-3
0.6
0.72
w/ smooth.
0.04
0.12
0.07
8.0B-9
1.1E-4
0.10
0.07
Table 5 shows the results of the directed Laplacian solver on different directed graphs. It reports relative errors between the exact solution and the solution calculated by the proposed solver with and without smoothing. It shows that errors can be dramatically reduced after smoothing, and our proposed solver can well approximate the true solution of Lçx = b
16

---

Under review as a conference paper at ICLR 2021
0.6
for sparsitiar S
sparatier
PR sparsiteer
0.4
0.2
0.2
0.1
0.2
0.2
graph
for graph G
PR for graph G
Figure 8: The correlation of PageRank between itself and its sparsifier for graph ibm_32 (left),
mathworks 100 (middle) and gre_1107 (right) after smoothing
7.5.2 ITERATIVE METHOD FOR DIRECTED LAPLACIAN SOLVER
Figure 7 shows the relative residual plot (versus GMRES iteration number) when no preconditioner is applied, Incomplete LU factorization (ILU) as the preconditioner is applied, and the directed sparsifier Laplacian Ls as the preconditioner applied for graph pesa and big. can conclude that GMRES with directed sparsifiers as preconditioners has faster convergence rate than the other two methods. is also observed that the number of nonzeros (nnz) preconditioner matrix created by the directed sparsifier is the lowest.
7.6 APPLICATIONS IN COMPUTING (PERSONALIZED) PAGERANK VECTORS
The idea of PageRank is to give a measurement of the importance for each web page. For example, PageRank algorithm aims to find the most popular web pages, while the personalized PageRank algorithm aims to find the pages that users will most likely to visit. To state it mathematically, the PageRank vector p satisfies the following equation:
p ADDEPP
(37)
where p is also the eigenvector D that corresponds to the eigenvalue equal to Meanwhile, represents the stable distribution of random walks on graph G. However, D can not be defined if there exists nodes that have no outgoing edges. To deal with such situation, self-loop with small edge weight can be added for each node.
The stable distributions of (un)directed graphs may not be unique. For example, the undirected graphs that have multiple coongly-connected components, or the directed graphs that have nodes without any outgoing edges, may have non-unique distributions. In addition, it may take very long time for random walk to converge to a stable distribution on a given (un)directed graph.
To avoid such situation in PageRank, jumping factor that describes the possibility jump to a uniform vector can added, which is shown as follows:
p - (1 (
1.
(38)
n
- (1-(1-1 AG D
(39)
where a E [0, 1] is a jumping constant. After applying Taylor expansions, we can obtain that
p Σ ((1 ((1-))A
(40)
By setting the proper value a (e.g., a = 0.15), the term (1 - a) will be quickly reduced with increasing Instead of starting with uniform vector 11, nonuniform personalization vector pr can be applied:
p = - a. al-a)AAD222 apr.
(41)
Figure 8 shows the application of the proposed directed graph sparsification for computing PageRank vectors, where the correlation of PageRank results using the original graphs (x-axis) and sparsifiers (y-axis) plotted for graph ibm (left), mathworks_ 100 (middle) and gre_ 1107 (right). Note
17

---

Under review as a conference paper at ICLR 2021
0.6
PPR for sparaiter S
PPR for sparsiior
sparsifer
0.2
PPR for graph
PPR for graph G
PPR for graph G
Figure 9: The correlation of personalized PageRank between itself and its sparsifier for graph ibm_32 (left), mathworks_ 100 (middle) and gre_ 1107 (right) after smoothing
1
10
Figure 10: Spectral partitioning of directed (left) and undirected graphs (right). The nodes within the same cluster are assigned the same color.
that a few steps of Gauss-Seidel smoothing have been applied to remove the high-frreuency errors to obtain the smoothed PageRank vectors when using the sparsified graphs. We observe that the PageRank vectors obtained from sparsifiers can well approximate the results computed with the original graphs.
Similar to the results PageRank in Figure 8 shows the application the proposed directed graph sparsification the personalized PageRank, where the correlations of personalized PageRank results using the original graphs (x-axis) and sparsifiers (y-axis) are plotted for graph ibm 32 (left), mathworks 100 (middle) and gre 1107 (right). Gauss-Seidel smoothing are also applied when using the sparsified graphs. We can observe that personalized PageRank vectors from sparsifiers match very well with the ones generated from original graphs, which demonstrates the effectiveness of the sparsifiers on the Personalized PageRank application.
7.7 APPLICATIONS DIRECTED GRAPH PARTITIONING
It has been shown that partitioning and clustering of directed graphs play very significant roles in a variety of applications related to machine learning (Mallarrs & Vazirgiannis (013),, data mining and circuit synthesis and optimization (Micheli, (199),, etc. However, the efficiency of existing methods for partitioning directed graphs strongly depends on the complexity of the underlying graphs (Maliaros & Vazirgiannis 2013).
Ag As As
Àg A10
2
À
A
Figure 11: Eigenvalues distribution of LGg, for the directed graph in Figure 10
In this work, we propose a spectral method for directed graph partitioning problems. For an undirected graph, the eigenvectors corresponding the first few smallest eigenvalues can be utilized for the spectral partitioning purpose (Spielman & Teng 1996). For directed graph G on the other hand, the left singular vectors of Laplacian LG will be required for directed graph partitioning. The
18

---

Under review as a conference paper at ICLR 2021
eigen-decompositton of its symmetrization LG, can be wirtten
LGo = E'vii
(42)
where 0 == A1 < ...Ag and V1, Vk. with k S. denote the Laplacian eigenvalues and cigenvectors, respectively. There may be n eigenvalues when there are some nodes without any outgoing edges. In addition, the spectral properties of LGu are more complicated since the eigenvalues always have multiplicity (either algebraic or geometric multiplicities). For example, the eigenvalues according to the symmetrization of the directed graph in Figure 10 have few multipiicities: X2 = Xa.
\ >3 As '7, Ay A1g. as shown in Figure
Therefore. we propose to exploit the cigenvectors (left singular vectors of directed Laplacian) corresponding the first few different eigenvalues (singular values of directed Laplacian) for directed graph partitioning. For example, the partitioning result of the directed graph in Figure will depend on the eigenvectors of V1, V2, V4, Va that correspond eigenvalues of Y1, A2. A4, Ag. As shown in Figure [O) the spectral partitioning results can be quite different between the directed and undirected graph with the same set of nodes and edges.
In general, it is possible to first extract a spectrally-similar directed graph before any of the prior partitioning algorithms applied. Since the proposed spectral sparsification algorithm well preserve the structural (global) properties of the original graphs, the partitioning results obtained from the sparsified graphs will be very similar to the original ones.
Figure 12 shows the spectral graph partitioning results on the symmetrized graph G. of original directed graph and its symmetrized sparsifier S., As observed, very similar partitioning results have been obtained, indicating well preserved spectral properties within the graph.
directed
05
26
30
22
61
Figure 12: The partitioning results between G,, (left) and its sparsifier S, (right) for the 'ibm32.mtx' graph.
19


Reviews:
[{"review_id": "PJd1UmXFIbm", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces new notions of producing small approximations of directed graphs. These notions are based on measuring importances of edges with respect to quadratic forms of symmetrizations of the Laplacian. The algorithm is implemented, and some experimental results for the effectiveness of the sparse approximation as preconditioners are shown.\n\nI feel the contributions of the paper are more in the numerical analysis / linear systems solving setting. The new notion introduced appears fundamentally similar to the error-after-symmetrizatzion approaches taken in previous works. The experimental results don't involve end-to-end uses of directed Laplacians / directed random walks for learning tasks, but are more about approximations for solutions of linear systems / pagerank produced. Furthermore, I'm unfamiliar with uses of methods such as GMRES in learning tasks. So given such concerns, I'm unsure how relevant this paper is to ICLR.", "extra_scores": {}, "extra_text": {}}, {"review_id": "NskMaRlksK5", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers the problem of sparsifying directed graphs, a timely task of importance in many applications. The main contribution is the proposal of a unified approach for spectral sparsification of such directed graphs.\n\nThe proposed eigenvalue perturbation pipeline is interesting in its own right, and similarly that of ranking edges in terms of spectral importance from Section 5.2.  One of the main advantages of the approach is that it does not require the underlying directed graphs to be strongly connected and aperiodic, unlike recent work from the literature. Their proposed approach is fairly straightforward, but yet appears to be very efficient. The authors do a good job of placing their work in the relevant context, highlighting drawbacks of existing symmetrization techniques. The authors rightfully point out that naive symmetrization schemes from the literature may damage the structural properties of the graph. The proposed a Laplacian symmetrization approach which enjoys theoretical guarantees while remaining computationally scalable. The authors also mention other properties of interest that one could preserve during the sparsification process. \n\nThe authors also evaluate the embedding given by the proposed symmetrized Laplacian in the context of clustering directed graphs, where the majority of existing spectral methods tend to underperform. Clustering directed graphs is an important timely problem, less studied, and the present work makes also a nice contribution in that regard. The application to computing the (Personalized) PageRank is also nice (the sparsification appears to perform well in the PageRank computation), but perhaps less impactful since since this can be computed fast via a number of other methods. \n\nThe authors could further provide more intuition linking Theorem 4.3 on the existence of the sparsifier, and Section 5, in particular the pipeline in Section 5.2  The authors could also consider testing on synthetic data sets, also to assess the behaviour of the proposed method on graphs with increasing density. What about comparison with other approaches? The authors claim strong performance in their numerical results, but it would be good to have some baselines to compare against.", "extra_scores": {}, "extra_text": {}}, {"review_id": "JFkP19mi0Gj", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n========\nThe paper studies a certain notion of spectral sparsification of directed graphs. It claims the existence of nearly linear sized sparsifiers under this notion, and suggests empirical methods to produce such sparsifiers in nearly linear time.\n\nComments\n=========\n\nSection 4: I am not sure what is the downstream justification for the notion of spectral approximation studied here (relative condition number) in the context of directed graphs, and it would help if the authors could elaborate on this. For example, the notion defined in Cohen et al. (2017) enables fast approximate solution of linear equations, which is a primitive in various algorithmic tasks on directed graphs. The notion in this paper does not rigorously lead to such consequences (or at least none are presented), which leaves the question why one should be interested in an existence result like Theorem 4.3. (The appendix contains some experimental results for linear system solving, but no rigorous claims.)\n\nAbout the proof Theorem 4.3: Could you please clarify how does the approximating matrix $L_{S_u} = B^T W_o^{1/2} T W_o^{1/2} B$ (defined in the end of section 8.2) give rise to a directed subgraph? How does one construct $S$ (or in other words, why can $L_{S_u}$ be written as $L_SL_S^T$ for $L_S$ of the form in eq (18))\n\nSection 5: I am generally not able to follow the derivations in section 5.2, and it may be needed to be written more clearly. Specific comments/questions:\n1. How come $\\lambda_n>0$ if the matrix $L_{S_u}^+L_{G_u}$  has non-full rank?\n2. You define v_i once as the eigenvectors of $L_{S_u}^+L_{G_u}$ in the first sentence sentence as then as scaled eigenvalues of $L_{S_u}$ between eq (5) and (6), which one is it? Or are they supposed to be denoted differently?\n3. Could you elaborate on how you arrive at eq (5)?\n\nSection 6: The experiments in the main text concentrate on measuring the relative condition number of the sparsifier w.r.t the original graph as per the sparsification notion studied in this paper, but as written above it is not clear what do we actually get out of the sparsifier. In general I have doubts about fit to the venue; while ICLR scope is broad and inclusive and spectral sparsification has certain potential connections to ML, this paper does not highlight any of them, and it is not entirely clear what it is attempting to achieve.\n\nConclusion:\n=========\nPros: Spectral sparsification of directed graphs is a relatively new field, so far with initial results that invite further research and improvements. The paper implements an algorithm which seems to improve over baselines under certain metrics.\nCons: It is not clear what ML task the paper is trying to solve or improve upon, and what improvement is achieved. Viewed as a theoretical submission, the analysis is unclear to me in many parts, and at present I am unable to confirm its soundness. The algorithm implemented in the experimental section seems rather detached from the preceding theoretical definitions, whose purpose remains somewhat unclear. \n\nPost-discussion update: I thank the authors for their participation in the discussion. Unfortunately I find it mostly has not cleared the numerous question marks I have regarding the paper. I recommend putting more effort into clarifying the mathematical derivations and into positioning the paper correctly w.r.t. prior work on the topic.", "extra_scores": {}, "extra_text": {}}, {"review_id": "GGknSfjO4O", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Authors propose a novel method to approximate a given directed graph with a´nother one (the sparsifier) which has fewer edges. The proposed method seems promising. however, the paper needs significant improvement in clarity and contextualizing the results. \n\n1. The main algorithmic result, Algorithm 1 should be placed in the main sectino of the paper and not an appendix. \n2. The main numerfic results, e.g., applying the sparsifier to linear solvers should be put in the main section of the paper and not hidden in the appendix. \n3. The comparision for the linear solver application should also inclucde the spcial case of undirected graphs. how does your sparsifier compare then with Spielmen et.al. mehtods. Also, for the general case of directed graphs which are not strongly connected, you should compare with existing sparsifiers for directed graphs but whose analysis requires them to be strongly connected. Maybe in practice those existing sparsifiers work fine. \n4. Pls also evaluate the sparsifier on machine learning applications, e.g., federated and mulit-task learning over networks:\n\nA. Jung and N. Tran, \"Localized Linear Regression in Networked Data,\" in IEEE Signal Processing Letters, vol. 26, no. 7, pp. 1090-1094, July 2019, doi: 10.1109/LSP.2019.2918933. \n\nminor issues: \n- \"..in which any node can be reached from any other node along with direction.\"\n- \"...will have the all-one vector as its null space,...\"  --> the null space consists of more than one single vector \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a fast, nearly-linear time, algorithm for finding a sparsifier for general directed and undirected graphs that approximately preserves the spectral properties of the original graph. The reviewers appreciated the main contribution of the paper, but they were concerned about the correctness and clarity of the paper, as well as the relevance of the contribution to machine learning. Following the discussion with the authors, the reviewers still felt that these concerns had not been fully addressed by the authors' responses and the subsequent revision of the paper. After taking these concerns into account as well as evaluating the paper relative to other ICLR submissions, I recommend reject.
Decision: Reject