Learning Networks from Random Walk-Based Node Similarities
Jeremy G. Hoskins∗

Cameron Musco†

Christopher Musco‡

Charalampos E. Tsourakakis§

arXiv:1801.07386v1 [cs.SI] 23 Jan 2018

January 24, 2018

Abstract
Digital presence in the world of online social media entails signiﬁcant privacy risks [6, 10,
33, 58, 34]. In this work we consider a privacy threat to a social network in which an attacker
has access to a subset of random walk-based node similarities, such as eﬀective resistances (i.e.,
commute times) or personalized PageRank scores. Using these similarities, the attacker’s goal is
to infer as much information as possible about the underlying network, including any remaining
unknown pairwise node similarities and edges.
For the eﬀective resistance metric, we show that with just a small subset of measurements,
the attacker can learn a large fraction of edges in a social network (and in some cases all edges),
even when the measurements are noisy. We also show that it is possible to learn a graph
which accurately matches the underlying network on all other effective resistances. This second
observation is interesting from a data mining perspective, since it can be expensive to accurately
compute all eﬀective resistances or other random walk-based similarities. As an alternative, our
graphs learned from just a subset of approximate eﬀective resistances can be used as surrogates
in a wide range of applications that use eﬀective resistances to probe graph structure, including
for graph clustering, node centrality evaluation, and anomaly detection.
We obtain our results by formalizing the graph learning objective mathematically, using
two optimization problems. One formulation is convex and can be solved provably in polynomial time. The other is not, but we solve it eﬃciently with projected gradient and coordinate
descent. We demonstrate the eﬀectiveness of these methods on a number of social networks
obtained from Facebook. We also discuss how our methods can be generalized to other random walk-based similarities, such as personalized PageRank scores. Our code is available at
https://github.com/cnmusco/graph-similarity-learning.

∗

Yale University. jeremy.hoskins@yale.edu
Massachusetts Institute of Technology. cnmusco@mit.edu
‡
Massachusetts Institute of Technology. cpmusco@mit.edu
§
Boston University & Harvard University. ctsourak@bu.edu
†

1

1

Introduction

In graph mining and social network science, a variety of measures are used to quantify the similarity
between nodes in a graph, including the shortest path distance, Jaccard’s coeﬃcient between node
neighborhoods, the Adamic-Adar coeﬃcient [2], and hub-authority-based metrics [32, 11]. An important family of similarity measures are based on random walks, including SimRank [25], random
walks with restarts [52], commute times [20], personalized PageRank [42, 26, 7], and DeepWalk embeddings [43]. These measures capture both local and global graph structure and hence are widely
used in graph clustering and community detection [4, 46], anomaly detection [44], collaborative
ﬁltering [20, 47, 57], link prediction [38], and many other applications (including outside of network
science, such as in computer vision [22]).
In this work we focus on these random walk-based similarity metrics. We initiate the study of
a fundamental question:
How much information about a network can be learned given access to a subset of
potentially noisy estimates of pairwise node similarities?
This question is important from a privacy perspective. A common privacy breach is social link
disclosure [58], in which an attacker attempts to learn potentially sensitive links between nodes
in a network. Such attacks are very common; fake accounts with engineered proﬁles are used to
inﬁltrate and spy on social groups, potential employers may want to inspect the social network of
a job candidate, and advertisers may wish to probe the demographic and interest information of a
user to oﬀer targeted ads. Thus, characterizing the ability of an attacker to reveal link information
using pairwise node similarities is important in understanding the privacy implications of releasing
such similarities, or information which can be used to compute them.
From a data mining perspective, computing all pairwise node similarities can be infeasible
for large networks since the number of similarities grows quadratically in the number of nodes.
Additionally, when the network cannot be accessed in full but can only be probed via crawling
with random walks (e.g., a by third party studying a social network [30]), we may only have
access to estimates of pairwise similarities rather than their exact values. Thus, understanding
what information can still be learned from a partial, potentially noisy, set of node similarities is
important when using these metrics in large scale graph mining.

1.1

Learning from Effective Resistances

In this paper, we focus on commute times, which are one of the most widely used random walkbased similarities. Commute times are a scaled version of effective resistances, they form a metric,
and have major algorithmic applications, such as spectral graph sparsiﬁcation [49]. Our ideas can
be extended to related similarity measures, such as personalized PageRank, which we discuss in
Section 4.4. It was shown in the seminal work of Liben-Nowell and Kleinberg [38] that eﬀective
resistances can be used to predict a signiﬁcant fraction of future links appearing in networks from
existing links, typically ranging from 5% up to 33%.
A diﬃculty associated with this task is that, in contrast to local similarity measures such as the
number of common neighbors or the Adamic-Adar coeﬃcient [2], node similarity under the eﬀective
resistance metric does not necessarily imply local connectivity. For example, two nodes connected
by many long paths may be more similar than two nodes directly connected by a single edge.
Furthermore, in certain cases, the eﬀective resistance between two nodes u, v tends to correlate
1
1
+ d(v)
) [39, 54, 55], and it
well with a simple function of the degree sequence (speciﬁcally, d(u)
2

Figure 1: Grid graph learned from small, randomly selected fractions of eﬀective resistance pairs
using our proposed method. Edge thickness is proportional to edge weight.
is known that there are many graphs with the same degree sequence but very diﬀerent global
structures. Nevertheless, considered in aggregate, eﬀective resistances encode global structure in a
very strong way. For any graph, given all pairs eﬀective resistances, it is possible to provably recover
the full graph in polynomial time [48, 56]! This contrasts with purely local similarity metrics, which
can be used heuristically for link prediction, but do not give network reconstruction in general. For
instance, all-pairwise counts of common neighbors in any triangle free graph equal 0. Thus, these
counts reveal no information about graph structure.
While the full information case is well understood, when all exact eﬀective resistances are not
available, little is known about what graph information can be learned. Some work considers
reconstruction of trees based on a subset of eﬀective resistances [17, 8, 50]. However outside of this
special case, essentially nothing is known.

1.2

Our Contributions

We study in depth what can be learned about a graph given a subset of potentially noisy eﬀective
resistance estimates, from both a theoretical and empirical viewpoint. Our main contributions are:
Mathematical formulation. We provide an optimization-based formulation of the problem of
learning a graph from eﬀective resistances. Speciﬁcally, given a set of eﬀective resistance measurements, we consider the problem of ﬁnding a graph whose eﬀective resistances match the given
resistances as closely as possible.
In general, there may be many diﬀerent graphs which match any subset of all pairs eﬀective
resistances, and hence many minimizers to our optimization problem. If the resistances additionally
have some noise, there may be no graph which matches them exactly but many which match them
approximately. Nevertheless, as we show empirically, the graph obtained via our optimization
approach typically recovers signiﬁcant information about the underlying graph, including a large
fraction of its edges, its global structure, and good approximations to all of its eﬀective resistances.
Algorithms. We prove that, in some cases, the optimization problem we present can be solved
exactly, in polynomial time. However, in general, the problem is non-convex and does not admit
an obvious polynomial time solution. We give expressions for its gradient and Hessian, and show
that it can be solved eﬃciently via iterative methods. In particular, we employ projected gradient
and coordinate descent, as well as a powerful initialization strategy which allows us to ﬁnd high
quality solutions in most instances.
We also show that the problem can be relaxed to a convex formulation. Instead of searching for a
3

graph that matches all given eﬀective resistance measurements, we just ﬁnd a graph whose eﬀective
resistances are upper bounded by those given and which has minimum total edge weight. This
modiﬁed problem is convex and can be solved in polynomial time via semideﬁnite programming.
Experimental Results. We evaluate our algorithms on several synthetic graphs and real Facebook
ego networks, which contain all nodes in the social circle of a user. We demonstrate that given
a small randomly selected fraction of all eﬀective resistance pairs (10%-25%) we can learn a large
fraction of a network – typically between 20% and 60% of edges. We show that this recovery is
robust to adding Gaussian noise to the given eﬀective resistances. A visual sample of our results
is included in Figure 1 for a simple grid graph. We observe that using a small fraction of noisy
pairwise similarities we can extract a lot of structural information about the graph. Here, noise
is distributed for each edge independently as a Gaussian random variable with zero mean, and
variance σ 2 = 0.1. We observe that as the size of the fraction of revealed similarities increases, an
attacker can recover most of the graph.
We also demonstrate that by ﬁnding a graph which closely matches the given set of eﬀective
resistances (via our optimization approach), we in fact ﬁnd a graph which closely matches the
underlying network on all eﬀective resistance pairs. This indicates that a signiﬁcant amount of the
information contained in all pairs eﬀective resistances can be learned from just a small subset of
these pairs, even when they are corrupted by noise.

2

Related Work

Link prediction and privacy in social networks. The link prediction problem was popularized
by Liben-Nowell and Kleinberg [38]. The goal of link prediction is to infer which edges are likely to
appear in the near-future, given a snapshot of the network. In [38] various node similarity measures
are used to predict a non-trivial fraction of future interactions. Other works focus on predicting
positive or negative links [35, 53]. For an extensive survey, see [3].
While closely related, link prediction diﬀers from the problem we consider since, typically, one
is given full access to a network snapshot (and in particular, could compute exact pairwise node
similarities for this network) and seeks to make predictions about future evolutions of the network.
In our setting, we are given partial information about a network (via a partial set of noisy similarity
measures) and seek to learn existing links,
While link prediction is useful in applications ranging from understanding network evolution,
to link recommendation, and predicting interactions between terrorists, it entails privacy risks.
For instance, a malicious attacker can use link prediction to disclose information about sensitive
connections in a sexual contact graph [33, 58]. Private link prediction is not adequately explored
in the literature. Abebe and Nakos suggest a possible formalization [1].
Learning graphs. Learning graphs from data is central to many disciplines including machine
learning [27], network tomography [13], bioinformatics [18], and phylogenetics [19]. The general
framework is that there exists a hidden graph that we wish to discover by exploiting some kind of
data, e.g., answers from a blackbox oracle returning certain (possibly noisy) graph measurements.
Theoretical work in this area has focused on worst case query complexity. Two representative
examples include Angluin’s et al. work on learning graphs using edge detecting queries [5], and the
recent work of Kannan, Mathieu, and Zhou using distance queries [28]. A number of works also
consider learning graph parameters such as node count and mixing time by examining random walks

4

traces [30, 16, 9]. Experimental work has focused on recovering graphs from noisy measurements
such as GPS traces [15], and distances between cell populations based on genetic diﬀerences [19, 18].
Learning trees. While a tree is special type of a graph, the case of learning trees deserves
special mention since signiﬁcant work on learning graphs from data has focused on trees. Distancebased reconstruction of
 trees aims to reconstruct a phylogenetic tree whose leaves correspond to n
species, given their n2 pairwise distances [19]. Note that on a tree, pairwise distances are identical
to pairwise
eﬀective resistanes. Batagelj et al. study tree realizability assuming access to fewer
n
than 2 leaves’ pairwise distances [8]. A spectral method has been proposed by Stone and Griﬃng
[50]. Culberson and Rudnicki [17] consider the problem of reconstructing a degree restricted tree
given its distance matrix, see also [45].

3
3.1

Proposed Method
Notation and Preliminaries

For an undirected, weighted graph G = (V, E, w) with n nodes, we let A be the n × n adjacency
matrix. L denotes the (unnormalized) graph Laplacian: L = D − A, where D is a diagonal
matrix with Di,i equal to the weighted degree of node i. For an integer n > 0, [n] denotes the set
{1, 2, ..., n}. ei denotes the ith standard basis vector. For a matrix M , Mi,j denotes the entry in its
ith row and j th column.
Commute time and effective resistance. For two nodes u, v ∈ V , the hitting time hG (u, v)
is the expected time it takes a random walk to travel from u to v. The commute time is its
symmetrized version cG (u, v) = hG (u, v) + hG (v, u), i.e., the time to move from u to v and then
back to u. For connected graphs, the eﬀective
P resistance between u, v is a scaling of the commute
cG (u,v)
time: rG (u, v) = vol(G) where vol(G) = 2 e∈E we . Eﬀective resistance has a natural electrical
interpretation. When G is viewed as an electrical network on n nodes where each edge e corresponds
to a link of conductance we (equivalently to a resistor of resistance w1e ), the eﬀective resistance is the
voltage diﬀerence that appears across u, v when a unit current source is applied to them. Eﬀective
resistances (and hence commute times) always form a metric [31].
Letting χu,v = eu − ev , the eﬀective resistance between nodes u and v in a graph G with
Laplacian matrix L can be computed as:
rG (u, v) = χTu,v L+ χu,v .

(1)

Here L+ denotes the Moore-Penrose pseudoinverse of L.

3.2

Problem Definition

We begin by providing a mathematic formulation of the problem introduced in Section 1 – that of
learning the structure of a graph from partial and possibly noisy measurements of pairwise eﬀective
resistances. An analogous problem can be deﬁned for other random walk-based similarities, such
as personalized PageRank. We discuss initial results in this direction in Section 4.4.

5

Problem 1 (Graph Reconstruction From Eﬀective Resistances). Reconstruct an unknown
graph G given a set of noisy effective resistance measurements,
r̄(u, v) = rG (u, v) + nuv
for each (u, v) ∈ S, where S ⊆ [n] × [n] is a set of node pairs and nuv is a potentially random
noise term.
We focus on three interesting cases of Problem 1:
Problem 1.1 S = [n] × [n] and nuv = 0 for all (u, v) ∈ S. This is the full information recovery
problem.
Problem 1.2 S is a subset of [n] × [n] and nuv = 0 for all (u, v) ∈ S. In this setting we must learn
G from a limited number of exact eﬀective resistances.
Problem 1.3 S is a subset of [n] × [n] and nuv is a random term, e.g. a mean 0 normal random
variable with variance σ 2 : nuv ∼ N (0, σ 2 ).
It is known that there in a unique graph consistent with any full set of eﬀective resistance measurements (see e.g., [48] or the related problem in [56]). Additionally, this graph can be computed
by solving a fully determined linear system. So, we can solve Problem 1.1 exactly in polynomial
time. We illustrate this in Section 4.1.
From a privacy and data mining perspective, the limited information settings of Problems 1.2
and 1.3 are more interesting. In Section 4.1 we demonstrate that, when G is a tree, exact recovery
is possible for Problem 1.2 whenever S is a superset of G’s edges. However, in general, there is no
simple closed form solution to these problems, and exact recovery of G is typically impossible. In
particular, several graphs may be consistent with the measurements given. Thus, we address these
cases by reposing Problem 1 as an optimization problem, in which we attempt to recover a graph
matching the given eﬀective resistances as best as possible.

3.3

Optimization Formulation

A natural formalization of Problem 1 is as a least squares problem.
Problem 2. Given a set of vertex pairs S ⊆ [n] × [n] and a target effective resistance r̄(u, v)
for each (u, v) ∈ S:
def

minimize F (H) =
graph H

X

[rH (u, v) − r̄(u, v)]2 .

(2)

(u,v)∈S

Using formula (1) for eﬀective resistances, Problem 2 can equivalently be viewed as an opti2

P
mization problem over the set of graph Laplacians: we minimize (u,v)∈S χTu,v L+ χu,v − r̄(u, v) .
While this set is convex, the objective function is not and thus it is unclear if it can be minimized
provably in polynomial time. Nevertheless, we demonstrate that it is possible to solve the problem
approximately using iterative methods. In Section 4.2 we derive projected gradient and coordinate
6

descent algorithms for the problem. Combined with a powerful initialization heuristic, our experiments show that these methods quickly converge to near global minimums of the objective function
for many networks.
For Problem 1.2, where r̄(u, v) comprise a subset of the exact eﬀective resistances for some
graph G, minH F (H) = 0. This minimum may be achieved by multiple graphs (including G itself)
if S does not contain all eﬀective resistance pairs. Nevertheless, we demonstrate experimentally in
Section 5 that even when S contains a small fraction of these pairs, an approximate solution to
Problem 2 often recovers signiﬁcant information about G, including a large fraction of its edges.
Interestingly, we ﬁnd that, while Problem 2 only minimizes over the subset S, the recovered graph
typically matches G on all eﬀective resistances, explaining why it contains so much structural
information about G. For Problem 1.3, if S = [n] × [n] and the noise terms nuv are distributed as
i.i.d. Gaussians, it is not hard to see that Problem 2 gives the maximum likelihood estimator for
G. We again show that an approximate solution can recover a large fraction of G’s edges.
We note that while we can solve Problem 2 quickly via iterative methods, we leave open provable
polynomial time algorithms for solving this problem in the settings of both Problems 1.2 and 1.3.
Convex relaxation. As an alternative to Problem 2, we introduce an optimization formulation of
Problem 1 that is convex. It is convenient here to optimize over the convex set of graph Laplacians.
Problem 3. Let L be the convex set of n × n graph Laplacians. Given a set of vertex pairs
S ⊆ [n] × [n] and a target effective resistance r̄(u,v) for every (u, v) ∈ S,
minimize

Tr(L)

L∈L

subject to

χTu,v L+ χu,v ≤ r̄(u, v)

∀(u, v) ∈ S

Observe that we can trivially ﬁnd a feasible solution for Problem 3 by setting L to be a large
complete graph, in which case all eﬀective resistances will be close to 0. By Rayleigh’s monotonicity
law, decreasing the weight on edges in L increases eﬀective resistances. Tr(L) is equal to the total
degree of the graph corresponding to L, so the problem asks us to ﬁnd a graph with as little total
edge weight as possible that still satisﬁes the eﬀective resistance constraints.
The disadvantage of this formulation is that it only encodes the target resistances r̄(u, v) as
upper bounds on the resistances of L. The advantage is that we can solve Problem 3 provably in
polynomial time via semideﬁnite programming (see Section 4.3). In practice, we ﬁnd that it can
sometimes eﬀectively learn graph edges and structure from limited measurements.
Problem 3 is related to work on convex methods for minimizing total eﬀective resistance or
relatedly, mixing time in graphs [12, 51, 21, 21]. However, prior work does not consider pairwise
resistance constraints and so is not suited to the graph learning problem.

4
4.1

Analytical Results and Algorithms
Full Graph Reconstruction – Problem 1

Problem 1 can be solved exactly in polynomial time when S contains all resistance pairs of some
graph G (i.e. Problem 1.1). In this case, there is a closed form solution for G’s Laplacian L and the
solution is unique. This was pointed out in [48], however we include our own proof for completeness.
7

Theorem 1. If there is a feasible solution to Problem 1.1 then it is unique and can be found in
O(n3 ) time. Specifically, the Laplacian L of the unique solution G is given by
 


J +
J
(3)
R I−
−2 · I −
n
n
where R is the matrix with Ru,v = rG (u, v) for all u, v ∈ [n], I is the n × n identity matrix , and J
is the n × n all ones matrix.

Proof. For an n node graph, the number of possible edges is m = n2 . Let B ∈ Rm×n be the vertex
edge incidence matrix of the complete graph with a row equal to χu,v = eu − ev for every (u, v).
The Laplacian of any n vertex graph can be written as L = B T W B, for some W ∈ Rm×m which
is a nonnegative diagonal matrix with entries corresponding to the edge weights.
We can rewrite the eﬀective resistance formula in (1) as:
+
+
+
+
rL (u, v) = χ⊤
u,v L χu,v = (L )u,u + (L )v,v − 2(L )u,v .

(4)

Since L+ is symmetric we need only determine n(n+1)
unknown entries to determine the full
2
matrix. Moreover, since the all ones vector is in the null space of L and therefore L+ , we see that:
X
L+
L+
(5)
u,u = −
u,v ,
v6=u

and hence we can rewrite (4) as:
ru,v = −

X

v′ 6=v,u

X

(L+ )u,v′ −

(L+ )u′ ,v − 4(L+ )u,v .

(6)

u′ 6=u,v

Let M be the m × m matrix with rows and columns indexed by pairs u, v ∈ [n] with u 6= v and
(u1 , v1 ), (u2 , v2 ) entry given by:


−4 if u1 = u2 and v1 = v2
M(u1 ,v1 ),(u2 ,v2 ) = −1 if u1 = u2 or v1 = v2


0 otherwise.

Let r ∈ Rm contain each eﬀective resistance rG (u, v). We can see from (6) that if we solve the
linear system M x = −r, as long as M is full rank and so the solution is unique, the entries of x will
give us each (L+ )u,v with u 6= v. We can then use these entries to recover the remaining diagonal
entries of L+ using (5).
We can verify that M is in fact always full rank by writing M = −|B||B|T − 2I, where |B|
denotes the matrix formed from B by taking the absolute value of each of its entries. We note
that the non-zero eigenvalues of |B||B|T are equal to the non-zero eigenvalues of |B T ||B| which
is the n × n matrix M = (n − 2)I + J. M has eigenvalues 2n − 2 with multiplicity 1 and n − 2
with multiplicity n − 1. The remaining m − n eigenvalues of |B||B|T are zero. Consequently, the
eigenvalues of M are −2n with multiplicity 1, −n with multiplicity n − 1 and −2 with multiplicity
m − n. Thus M is full rank, proving that the eﬀective resistances fully determine L+ and thus L.
Solving for L via the linear system M x = −r would require O(n6 ) time, however, the closed
form solution (3) given in Lemma 9.4.1 of [48] allows us to solve this problem in O(n3 ) time.
8

Reconstruction from hitting times. The above immediately generalizes to graph reconstruction
from hitting times since, as discussed, for connected G, the eﬀective resistance between u, v can
G (v,u)
G (u,v)
= hG (u,v)+h
. Thus, by Theorem 1, we can recover G up to a
be written as rG (u, v) = cvol(G)
vol(G)
scaling from all pairs hitting times. This recovers a result in [56]. Note that if we scale all edge
weights in G by a ﬁxed factor, the hitting times do not change. Thus recovery up to a scaling is
the best we can hope for in this setting.
Reconstruction from other similarity measures. An analogous result to Theorem 1 holds for
graph recovery from all pairs personalized PageRank scores, and for related measures such as Katz
similarity scores [29]. We discuss this direction in Section 4.4.
Are all pairs always necessary for perfect reconstruction?
For general graphs, Problem

1 can only be solved exactly when S contains all n2 true eﬀective resistances. However, given
additional constraints on G, recovery is possible with much less information. In particular, when
G is a tree, we can recover it (i.e., solve Problem 1.2) whenever S is a superset of its edge set.
Roughly, since G is a tree, the eﬀective resistance rG (u, v) is equal to the length of the unique
path connecting u and v. As long as S includes all edges in G, it fully determines all path lengths
and hence the eﬀective resistances for all pairs u, v. We can thus recover G via Theorem 1. Formally:
Theorem 2. If G is a tree and a feasible solution to Problem 1.2 with edge set E ⊆ S then G is
unique and can be found in O(n3 ) time.
Proof. Let Puv be the unique path between u, v in G. It is well known [14] that:
X
1/we .
rG (u, v) =

(7)

e∈Puv

For (u, v) ∈ S set r̄(u, v) = rG (u, v). Let G be an undirected graph with an edge for each (u, v) ∈ S
with length rG (u, v). For all (u, v) ∈
/ S, set r̄(u, v) to the shortest path distance between u and v
in G.
Claim. r̄(u, v) = rG (u, v) for all (u, v) ∈ [n] × [n].
For any pair (u, v), we have r̄(u, v) ≤ rG (u, v). The length of shortest path between u, v in G is
certainly
at mostPthe length of Puv , which is contained P
in G since E ⊆ S. Puv ’s length in G is:
P
e∈Puv 1/we = rG (u, v), again using (7).
e∈Puv 1/we using (7). Thus, r̄(u, v) ≤
e∈Puv rG (e) =
Further, Puv is in fact a shortest path between u, v in G, giving that r̄(u, v) = rG (u, v). This is
because the length of every edge (u, v) ∈ S that is not in E just equals the length of path Puv in G
(i.e., rG (u, v)) and so removing this edge from G does not change any shortest path distance. So
we can assume that G just contains the edges in E, and so Puv is the unique path between u, v.
Given the above claim, the theorem follows since we can compute each r̄(u, v) from the eﬀective
resistances of the edges in S and can then compute G from these resistances by Theorem 1.
The problem of recovering trees from pairwise distance measurements is a central problem in
phylogenetics. There are other cases when just a subset of eﬀective resistances is known to allow
full recovery, for example when the eﬀective resistances between any pair of leaves is known [50, 48].
Also related to our analysis for trees lies is the work of Mathieu and Zhou [40], which reconstructs
graphs with bounded degree from pairwise distance measurements.

9

4.2

Graph Learning via Least Squares Minimization – Problem 2

When Problem 1 cannot be solved exactly, e.g. in the settings of Problems 1.2 and 1.3, an eﬀective
surrogate is to solve Problem 2 to ﬁnd a graph with eﬀective resistances close to the given target
resistances. As we demonstrate experimentally in Section 5, this yields good solutions to Problems
1.2 and 1.3 in many cases. Problem 2 is non-convex, however we show that a good solution can
often be found eﬃciently via projected gradient descent.

Optimizing over edge weights. Let m = n2 . We write the Laplacian of the graph H as
def

L(w) = B T diag(w)B, where w ∈ Rm is a non-negative vector whose entries correspond to the edge
weights in H, diag(w) is the m × m matrix with w as its diagonal, and B ∈ Rm×n is the vertex
edge incidence matrix with a row equal to χu,v = eu − ev for every possible edge (u, v) ∈ [n] × [n].
Optimizing the objective function F (H) in Problem 2 is equivalent to optimizing F (w) over
def

the edge weight vector w, where we deﬁne F (w) = F (H) for the unique H with Laplacian equal
to L(w).
We restrict wi ≥ 0 for all i and project to this constraint after each gradient step simply by
setting wi := max(wi , 0). The gradient of F (w) can be computed in closed form. We ﬁrst deﬁne
an auxiliary variable, R(w) ∈ Rm×m , whose diagonal contains all pairwise eﬀective resistances of
H with weight vector w:
Definition 1. For w ∈ Rm with wi ≥ 0 for all i, define
R(w) = BL(w)+ B T .
Using R(w) we can compute the gradient of F (w) by:
Proposition 1. Let ◦ denote the Hadamard (entrywise) product for matrices. Define the error
vector ∆(w) ∈ Rm as having ∆(w)i = r̄(i) − [R(w)]i,i for all i ∈ S and 0s elsewhere. We have:
∇F (w) = 2 (R ◦ R) ∆(w)
Proof. We begin by observing that, letting ei be the ith standard basis vector in Rm , for any weight
vector w, the graph Laplacian corresponding to the weight vector w + ǫei , is L(w) + ǫbi bTi . The
Sherman-Morrison formula for the matrix pseudoinverse yields:
(L(w) + ǫbi bTi )+ = L(w)+ − ǫ

L(w)+ bi bTi L(w)+
,
1 + ǫbTi L(w)+ bi

and, hence thinking of L(w)+ as a matrix-valued function of w,


∂L(w)+
1
L(w)+ bi bTi L(w)+
+
+
− L(w)
= lim
L(w) − ǫ
ǫ→0 ǫ
∂wi
1 + ǫbTi L(w)+ bi
= −L(w)+ bi bTi L(w)+ .
Let Ri denote the ith column of R(w) = BL(w)+ B T . By linearity:

∂R
= −B L(w)+ bi bTi L(w)+ B T = −Ri RiT .
∂wi
10

Thus,

X
∂F
=2
(r̄(j) − [R(w)]j,j ) · [R(w)]2i,j ,
∂wi
j∈S

and so we obtain that the gradient equals ∇F (w) = 2 (R ◦ R) ∆(w).
While gradient descent works well in our experiments, one may also apply second order methods,
which require F (w)’s Hessian. Using similar computations to those in Proposition 1 we obtain:
Proposition 2. Let IS ∈ Rm×m be the diagonal matrix with a 1 at each entry corresponding to
i ∈ S and 0s elsewhere and ∆(w) be as defined in Proposition 1. The Hessian matrix of F (w) is:
HF (w) = −4 [R diag(∆(w))R] ◦ R + 2(R ◦ R)IS (R ◦ R).
Acceleration via coordinate descent. Naively computing the gradient ∇F (w) via Proposition 1
requires computing the full m × m matrix R(w), which can be prohibitively expensive for large
graphs – recall that m = n2 = O(n2 ). Note however, that the error vector ∆(w) only has nonzero
entries at positions corresponding to the node pairs in S. Thus, it suﬃces to compute just |S|
columns of R corresponding to these pairs, which can give a signiﬁcant savings.
We obtain further savings using block coordinate descent. At each step we restrict our updates
to a subset of edges B ⊆ [n] × [n]. Let IB be the matrix with a 1 at diagonal entries corresponding
to elements of B and 0’s elsewhere. We step in the direction of IB ∇F (w). Computing this step
only requires forming the rows of R corresponding to edges in B. A typical way to choose B is at
random. See Section 5.1 for the actual implementation details.
Initialization. A good initialization for gradient descent can signiﬁcantly accelerate the solution
of Problem 2. We use a strategy based on the exact solution to Problem 1.1 in Theorem 1.
Since eﬀective resistances form a metric, by triangle inequality, for any u, v, w ∈ [n], rH (u, v) ≤
rH (u, w) + rH (w, v). Guided by this fact, given target resistances r̄(u, v) for (u, v) ∈ S, we ﬁrst
“ﬁll in” the constraint set. For (w, z) ∈
/ S, we set r̄(w, z) equal to the shortest path distance in the
graph Ḡ which has an edge for each pair in S with length r̄(u, v).
We thus obtain a full set of target eﬀective resistances. We can form R with Ru,v = r̄(u, v) and
initialize the Laplacian of H using the formula given in (3) in Theorem 1. However, this formula is
quite unstable and generally yields an output which is far from a graph Laplacian even when R is
corrupted by a small amount of noise. So we instead compute a regularized estimate,
 

+

J
J
R I−
+ λI ,
L̃ = −2 · I −
n
n
where λ > 0 can be chosen e.g. by line search. Generally, L̃ will not be a valid graph Laplacian,
but by removing negative edge weights, we typically obtain a good initialization for Problem 2.

4.3

Graph Learning via Convex Optimization – Problem 3

We ﬁnally discuss how to eﬃciently solve our convex formulation, Problem 3. We express this
problem as a semideﬁnite program (SDP) which can be solved via a number of available packages.
We can re-express our eﬀective resistance constraint as a positive semideﬁnite constraint using
the Schur complement condition:


L
χu,v
T
+
χu,v L χu,v ≤ r̄(u, v) iﬀ
 0 and L  0.
χTu,v r̄(u, v)
11

Doing so yields the following program:
Problem 4 (SDP Form of Problem 3). Given vertex pairs S ⊆ [n] × [n], and target effective
resistance r̄(u, v) for every (u, v) ∈ S,
minimize Tr(L)
L∈L

subject to
L  0 and ∀ (u, v) ∈ S,




L
χu,v
0
χTu,v r̄(u, v)

We require L to be a valid graph Laplacian (i.e., constrain L ∈ L) by adding linear constraints of
the form:
X
∀ i, Li,i = −
Li,j and ∀ i 6= j, Li,j ≤ 0.
j6=i

4.4

Extensions to Other Similarity Measures

As discussed, our results generalize to random walk-based node similarities beyond eﬀective resistances, such as personalized PageRank scores. Given localization parameter α ≥ 0, the personalized
PageRank score pαG (u, v) is the probability that a lazy random walk on graph G which jumps back
to u with probability α in each step is at node v in its stationary distribution [42, 24, 4].
Letting W = 12 (I + AD −1 ) be the lazy random walk matrix, pαG (u, v) is the v th entry of the
personalized PageRank vector:
pαG (u) = α(I − (1 − α)W )−1 eu .

(8)

This vector gives the stationary distribution for the random walk on G and thus the personalized
PageRank pαG (u, v) is its v th entry.
It is not hard to show an analogous result to Theorem 1, that given a full set of exact personalized
PageRank scores, full recovery of G is possible. Roughly, if we let P be the matrix with pαG (u) as
its uth column, we have P = α(I − (1 − α)W )−1 and can thus solve for the random walk matrix
W , and the graph G. This gives:
Theorem 3. For any connected graph G, given personalized PageRank score pαG (u, v) for each
(u, v) ∈ [n] × [n], there is algorithm returning G (up to a scaling of its edge weights) in O(n3 ) time.
Further, it is possible to formulate a problem analogous to Problem 2 and solve for a graph
matching a subset of personalized PageRank measurements as closely as possible. As shown in
Figure 2, personalized PageRank often gives a stronger signal of global graph structure than eﬀective
resistance. To create the plot, nodes are sorted by their value in the Laplacian Fielder vector, which
corresponds roughly to residence in diﬀerent clusters. In an extended version of our work, we will
provide detailed empirical results with personalized PageRank, and other random walk measures.

5

Empirical results

In this section we present an in depth experimental study of how well our methods can learn a graph
given a set of (noisy) eﬀective resistance measurements. We seek to answer two key questions:
12

Figure 2: Personalized PageRank correlates better than commute times with the cluster structure
in the FB Small C network (see Table 1). Heatmaps are shown in log scale.
1. Given a set of eﬀective resistance measurements, can we ﬁnd a graph matching these measurements via the optimization formulations posed in Problems 2 and 3 and the corresponding
algorithms discussed in Sections 4.2 and 4.3?
2. What structure does the graph we learn via our optimization approach share with the underlying network that produced the resistance measurements? Can it be used to predict links in
the network? Does it approximately match the network on eﬀective resistances outside the
given set of measurements, or share other global structure?
We address these questions by examining a variety of synthetic, and social network graphs.

5.1

Experimental Setup

Table 1 lists the networks analyzed in our experiments. These include two synthetic examples: an
8 × 8 two dimensional grid graph and a k-nearest neighbor graph constructed for vectors drawn
from a Gaussian mixture model with two clusters. The other networks are Facebook ‘ego networks’
obtained from the Stanford Network Analysis Project (SNAP) collection [36, 37]. Each of these
networks is formed by taking the largest connected component in the social circle of a speciﬁc user
(whose nodeId is shown in Table 1).
For all experiments, we provide
our algorithms with eﬀective resistances that are uniformly

def
× 100% of
sampled from the set of all n2 eﬀective resistances. We sample a ﬁxed fraction f = |S|
(n2 )
all possible measurements. We typically use f ∈ {10, 25, 50, 100}%. In some cases, these resistances
are corrupted with i.i.d. Gaussian noise η ∼ N (0, σ 2 ). We experiment with diﬀerent values of
variance σ 2 .
For Problem 2 we implemented gradient decent based on the closed-from gradient calculation
in Section 4.2. Line search was used to optimize step size at each iteration since it signiﬁcantly
outperformed implementations with ﬁxed step sizes. For larger problems, block coordinate descent
was used as described in Section 4.2, with the coordinate set chosen uniformly at random in each
iteration. We set the block size |B| = 5000. For Problem 3 we used MOSEK convex optimization
software, accessed through the CVX interface [41, 23]. All experiments were run on a computer
with a 2.6 GHz Intel Core i7 processor and 16 GB of main memory.
13

Name
Grid (synthetic)
k-nn (synthetic)
FB Small A (nodeId 698)
FB Small B (nodeId 3980)
FB Small C (nodeId 414)
FB Small D (nodeId 686)
FB Medium A (nodeId 348)
FB Medium B (nodeId 0)
FB Large A (nodeId 3437)
FB Large B (nodeId 1912)

# of nodes, n
64
80
40
44
148
168
224
324
532
795

# of edges, m
224
560
220
138
1692
1656
3192
2514
4812
30023

Table 1: Datasets for experiments. FB denotes “Facebook”.

Figure 3: Graphs learned by solving Problem 2 with gradient descent run to convergence for
uniformly sampled eﬀective resistances with varying levels of Gaussian noise. Edge width is proportional to edge weight in the plots.

5.2

Learning Synthetic Graphs

We ﬁrst evaluate our graph learning algorithms on Grid and k-nn, which are simple synthetic
graphs with clear structure.
Least squares formulation. We ﬁrst observe that gradient descent eﬀectively minimizes the
objective function of Problem 2 on the Grid and k-nn graphs. We consider the normalized
objective for a constraint set S and output graph H:
P
2
(u,v)∈S [rH (u, v) − r̄(u, v)]
P
Fb (H) =
.
(9)
2
(u,v)∈S r̄(u, v)

For noise variance 0, minH Fb(H) = 0 and in Figure 4 we see that for Grid we in fact ﬁnd H with
Fb(H) ≈ 0 for varying sizes of S. Convergence is notably faster when 100% of eﬀective resistances
are included in S, but otherwise does not correlate strongly with the number of constraints.
14

10

0

10

0

10

-2

10

-2

10

-4

10

-4

10 -6

10 -6

10 -8

10 -8

10 -10

10 -10

10

-12

10

-14

10

0

2000

4000

6000

8000

10000

0

10

-12

10

-14

10

10 -1

10 -2

10 -2

10 -3

10 -3

0

2000

4000

6000

8000

10 -4

10000

2000

4000

6000

8000

10000

0

2000

4000

6000

8000

10000

0

10 -1

10 -4

0

Figure 4: Objective error and generalization error for Problem 2, as deﬁned in (10) for Grid. For
details, see Section 5.2.
In Figure 4 we also plot the generalization error :
P
2
(u,v)∈[n]×[n] [rH (u, v) − rG (u, v)]
P
,
Fgen (H) =
2
(u,v)∈[n]×[n] rG (u, v)

(10)

where rG (u, v) is the true eﬀective resistance, uncorrupted by noise. Fgen (H) measures how well the
graph obtained by solving Problem 2 matches all eﬀective resistances of the original network. We
conﬁrm that generalization decreases with improved objective function performance, indicating that
optimizing Problem 2 eﬀectively extracts network structure from a small set of eﬀective resistances.
We observe that the generalization error is small even when f = 10%, and becomes negligible as
we increase the fraction f of measurements, even in the presence of noise.
We repeat the same experiments with Gaussian noise added to each resistance measurement.
The variance of the noise, σ 2 , is scaled relatively to the mean eﬀective resistance in the graph, i.e.,
we set r̄(u, v) = rG (u, v) + N (0, σ̄ 2 ) where:
X
σ2
σ̄ 2 = n ·
rG (u, v).
(11)
2

(u,v)∈[n]×[n]

While generally minH Fb(H) > 0 when r̄(u, v) is noisy (it is likely that there is no graph consistent
with these noisy measurements), we see that the objective value still decreases steadily with a larger
number of iterations. Generalization error also decreases as desired.
15

10

0

10

10 -1

10

0

10 -1

-2

10

-2

10 -3
10 -3

10 -4

0

10

2000

4000

6000

8000

10

10000

0

-4

10

10 -1

10 -2

10 -2

10 -3

10 -3

0

2000

4000

6000

8000

10 -4

10000

2000

4000

6000

8000

10000

0

2000

4000

6000

8000

10000

0

10 -1

10 -4

0

Figure 5: Objective error and generalization error for Problem 2, as deﬁned in (10) for k-nn.
Objective function error decreases steadily, leading to improved generalization error.
We obtain similar results by applying Problem 2 to a k-nearest neighbor graph with two clear
clusters of data points. Again, it is apparent in Figure 5 that gradient descent converges easily for
a variety of noise levels and constraint sets. Convergence on the least squares objective leads to
improved generalization error.
Figure 3 shows the graphs obtained from solving the problem for varying σ 2 and f . For both
graphs, when σ 2 = 0 and f = 100%, the original network is recovered exactly. Reconstruction
accuracy decreases with increasing noise and a decreasing number of constraints. For Grid, even
with 25% of constraints, nearly full recovery is possible for σ 2 = 0 and recovery of approximately
half of true edges is possible for σ 2 = 0.1. For k-nn, for σ 2 = 0 and σ 2 = 0.1 we observe that
cluster structure is recovered. Detailed quantitative results for both networks are given in Table 3.
Convex formulation. We next evaluate the performance graph learning via the convex relaxation
in Problem 3. In this case, we do not focus on convergence as we solve the problem directly using a
semideﬁnite programming (SDP) routine. Unlike for Problem 2, solving Problem 3 does not recover
the exact input graph, even in the noiseless all pairs eﬀective resistance case. This is because the
input graph does not necessarily minimize the objective of Problem 3 since there can be other
graphs with smaller total edge weight and lower eﬀective resistances.
However, the learned graphs do capture information about edges in the original: their heaviest
edges typically align with true edges in the target graph. This property is captured in the quantitative results of Table 3. Qualitatively, it is very apparent for Grid: in Figure 6 we mark the 224
16

Grid, 64 nodes
# of constraints Time (min.)
202
238.8
504
761.6
1008
1309.5
2016
2183.7

k-nn, 80 nodes
# of constraints Time (min.)
316
1216.0
790
3673.2
1580
8008.5
3160
16192.1

Table 2: Semideﬁnite program (SDP) optimization for Problem 3. Runtime is averaged over noise
levels σ 2 = 0, 0.1, 1.
heaviest edges in the learned graph in red and note that this set converges exactly on the grid.
The convex formulation never signiﬁcantly outperforms the least squares formulation, and signiﬁcantly underperforms for small constraint sets. Additionally, the semideﬁnite program scales
poorly with the number of nodes and eﬀective resistance constraints. Sample runtimes are included
in Table 2. Due to these considerations, we use the least squares formulation of Problem 2 instead
of the convex formulation in our experiments on real social networks. However, we believe there is
further opportunity for exploring Problem 3, especially given its provable runtime guarantees.

Figure 6: Graphs learned from solving the convex program in Problem 3 for uniformly sampled
eﬀective resistances from Grid with varying f, σ 2 . Heaviest edges marked in red.

5.3

Learning Social Network Graphs

We conclude by demonstrating the eﬀectiveness of the least squares formulation of Problem 2 in
learning Facebook ego networks from limited eﬀective resistance measurements. We consider three
metrics of performance, shown in Table 3 for a number of networks learned from randomly sampled
subsets of eﬀective resistances, corrupting with varying levels of noise.
17

2

Network

Algorithm

σ

Grid

GD
GD
SDP
SDP
GD
GD
SDP
SDP
GD
GD
GD
GD
GD
GD
GD
GD
GD
CD
CD
CD
CD
CD

0
.1
0
.1
0
.1
0
.1
0
.1
0
.1
0
.1
0
.1
0
0
.1
0
0
.1

k-nn

FB Small A
FB Small B
FB Small C
FB Small D
FB Medium A
FB Medium B
FB Large A
FB Large B

Objective
function error
f = 10% f = 25%
.00001
.00001
.00090
.00514
na
na
na
na
.00001
.00002
.00197
.00447
na
na
na
na
.01345
.00001
.00017
.00204
.00002
.00003
.00032
.00206
.00162
.00166
.00532
.00644
.00335
.00434
.00610
.18384
.00447
.00665
.00224
.01255
.01174
.03182
.00516
.00796
.00524
.00440
.12745
.34646

Effect. resistance
generalization error
f = 10% f = 25%
.06559
.00099
.08129
.01336
.08758
.07422
.09549
.09343
.01122
.00117
.05536
.00709
.09314
.10399
.11899
.14097
.21097
.00984
.07964
.01687
.01515
.00623
.02229
.01291
.00217
.00203
.01542
.00218
.00821
.00830
.00923
.21426
.02910
.01713
.00862
.01471
.01687
.03295
.00682
.00862
.00635
.00580
.14532
.36095

% Edges
learned
baseline
5.56

11.58

28.20
14.59
15.55
11.80
12.78
4.80
3.41
9.51

% Edges
learned
f = 10% f = 25%
20.54
88.39
25.89
50.00
16.07
25.00
12.50
26.79
44.54
72.68
25.96
41.53
27.05
48.36
24.32
39.89
44.54
75.00
53.64
60.00
42.75
48.55
36.23
43.48
57.03
59.51
52.66
57.51
21.92
24.52
21.38
21.20
23.50
25.59
18.97
22.15
17.50
16.03
10.52
12.45
20.26
24.95
19.43
16.97

Table 3: Graph recovery results. All results use a randomly sampled subset of f = 10% or f = 25%
of all eﬀective resistances. For “Algorithm”, GD denotes gradient descent and CD denotes block
coordinate descent with random batches of size 5000. “Noise level, σ 2 ” indicates that the target
resistances were set to r̄(u, v) = rG (u, v) + N (0, σ 2 · meanu,v (rG (u, v))). “% Edges baseline”, is
the edge density of the underlying network, equivalent to the expected edge prediction accuracy
achieved with random guessing.
1. Objective Function Value: the value of the objective function of Problem 2, normalized as
described in (9).
2. Generalization Error: the error in reconstructing the full set of eﬀective resistances of the
true graph, as deﬁned in (10).
3. Edges Learned: the rate of recovery for edges in the true graph. We utilize a standard metric
from the link prediction literature [32]: given underlying graph G with m edges and learned
graph H, we consider the m heaviest edges of H and compute the percentage of G’s edges
contained in this set.
Results. We ﬁnd that as for the synthetic Grid and k-nn graphs, we can eﬀectively minimize the
objective function of Problem 2 for the Facebook ego networks. Moreover, this minimization leads
to very good generalization error in nearly all cases. i.e., we can eﬀectively learn a graph matching
our input on all eﬀective resistances, even when we consider just a small subset.
For all graphs, we are able to recover a signiﬁcant fraction of edges, even when just considering
10% or 25% of eﬀective resistance pairs. We obtain the best recovery for small graphs, learning
over half of the true edges in FB Small A and FB Small C. Even for larger graphs, we can
typically recover over 20% of the true edges.
18

Typically, the number of edges learned increases as we increase the number of constraints and
decrease the noise variance. However, occasionally, considering fewer eﬀective resistances in fact
improves learning, possibly because we more eﬀectively solve the underlying optimization problem.

6

Conclusion

In this work, we show that a small subset of noisy eﬀective resistances can be used to learn signiﬁcant
information about a network, including predicting a large percentage of edges and recovering global
structure, such as accurate approximations to all pairwise eﬀective resistances. From a privacy
standpoint, our results raise major concerns about releasing random walk-based pairwise node
similarity information as it entails signiﬁcant privacy risk. From a data mining perspective, our
methods can be used for graph mining, even when computing all eﬀective resistances exactly is
infeasible.
Our work leaves a number of future research directions open, including giving a provable polynomial time algorithm for the least squares formulation (Problem 2), extending our work to other
similarity metrics, and scaling our methods to larger social networks.

References
[1] R. Abebe and V. Nakos. Private link prediction in social networks. 2014.
[2] L. A. Adamic and E. Adar. Friends and neighbors on the web. Social Networks, 25(3):211–230,
2003.
[3] M. Al Hasan and M. J. Zaki. A survey of link prediction in social networks. In Social Network
Data Analytics, pages 243–275. Springer, 2011.
[4] R. Andersen, F. Chung, and K. Lang. Local graph partitioning using PageRank vectors. In
47th Annual IEEE Symposium on Foundations of Computer Science, pages 475–486, 2006.
[5] D. Angluin and J. Chen. Learning a hidden graph using o(logn) queries per edge. Journal of
Computer and System Sciences, 74(4):546–556, 2008.
[6] L. Backstrom, C. Dwork, and J. Kleinberg. Wherefore art thou?: Anonymized social networks,
hidden patterns, and structural steganography. In Proceedings of the 16th International Conference on World Wide Web, pages 181–190. ACM, 2007.
[7] B. Bahmani, A. Chowdhury, and A. Goel. Fast incremental and personalized PageRank.
Proceedings of the VLDB Endowment, 4(3):173–184, 2010.
[8] V. Batagelj, T. Pisanski, and J. M. S. S. os Pereira. An algorithm for tree-realizability of
distance matrices. International Journal of Computer Mathematics, 34(3-4):171–176, 1990.
[9] A. Ben-Hamou, R. I. Oliveira, and Y. Peres. Estimating graph parameters via random walks
with restarts. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2018.
[10] S. Bhagat, G. Cormode, B. Krishnamurthy, and D. Srivastava. Class-based graph anonymization for social network data. Proceedings of the VLDB Endowment, 2(1):766–777, 2009.
19

[11] V. D. Blondel, A. Gajardo, M. Heymans, P. Senellart, and P. Van Dooren. A measure of
similarity between graph vertices: Applications to synonym extraction and web searching.
SIAM Review, 46(4):647–666, 2004.
[12] S. Boyd, P. Diaconis, and L. Xiao. Fastest mixing Markov chain on a graph. SIAM Review,
46(4):667–689, 2004.
[13] R. Castro, M. Coates, G. Liang, R. Nowak, and B. Yu. Network tomography: Recent developments. Statistical Science, pages 499–517, 2004.
[14] A. K. Chandra, P. Raghavan, W. L. Ruzzo, R. Smolensky, and P. Tiwari. The electrical resistance of a graph captures its commute and cover times. Computational Complexity, 6(4):312–
340, 1996.
[15] D. Chen, L. J. Guibas, J. Hershberger, and J. Sun. Road network reconstruction for organizing paths. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete
Algorithms, pages 1309–1320. Society for Industrial and Applied Mathematics, 2010.
[16] C. Cooper, T. Radzik, and Y. Siantos. Estimating network parameters using random walks.
Social Network Analysis and Mining, 4(1):168, 2014.
[17] J. C. Culberson and P. Rudnicki. A fast algorithm for constructing trees from distance matrices.
Information Processing Letters, 30(4):215 – 220, 1989.
[18] R. Desper, F. Jiang, O.-P. Kallioniemi, H. Moch, C. H. Papadimitriou, and A. A. Schäﬀer.
Inferring tree models for oncogenesis from comparative genome hybridization data. Journal of
Computational Biology, 6(1):37–51, 1999.
[19] J. Felsenstein. Conﬁdence limits on phylogenies: an approach using the bootstrap. Evolution,
39(4):783–791, 1985.
[20] F. Fouss, A. Pirotte, J.-M. Renders, and M. Saerens. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. IEEE
Transactions on Knowledge and Data Engineering, 19(3):355–369, 2007.
[21] A. Ghosh, S. Boyd, and A. Saberi. Minimizing eﬀective resistance of a graph. SIAM Review,
50(1):37–66, 2008.
[22] L. Grady. Random walks for image segmentation. IEEE Transactions on Pattern Analysis
and Machine Intelligence, 28(11):1768–1783, 2006.
[23] M. Grant and S. Boyd. CVX: Matlab software for disciplined convex programming, version
2.1. http://cvxr.com/cvx, Mar. 2014.
[24] T. H. Haveliwala. Topic-sensitive PageRank: A context-sensitive ranking algorithm for web
search. IEEE Transactions on Knowledge and Data Engineering, 15(4):784–796, 2003.
[25] G. Jeh and J. Widom. Simrank: a measure of structural-context similarity. In Proceedings
of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data
Mining, pages 538–543. ACM, 2002.
20

[26] G. Jeh and J. Widom. Scaling personalized web search. In Proceedings of the 12th International
Conference on World Wide Web, pages 271–279. ACM, 2003.
[27] V. Kalofolias. How to learn a graph from smooth signals. In The 19th International Conference on Artificial Intelligence and Statistics (AISTATS 2016). Journal of Machine Learning
Research (JMLR), 2016.
[28] S. Kannan, C. Mathieu, and H. Zhou. Near-linear query complexity for graph inference. In
International Colloquium on Automata, Languages, and Programming. Springer, 2015.
[29] L. Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39–43,
1953.
[30] L. Katzir, E. Liberty, and O. Somekh. Estimating sizes of social networks via biased sampling.
In Proceedings of the 20th International Conference on World Wide Web. ACM, 2011.
[31] D. J. Klein and M. Randić. Resistance distance. Journal of Mathematical Chemistry, 12(1):81–
95, 1993.
[32] J. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. The web as a graph:
measurements, models, and methods. Computing and Combinatorics, pages 1–17, 1999.
[33] A. Korolova, R. Motwani, S. U. Nabar, and Y. Xu. Link privacy in social networks. In
Proceedings of the 17th ACM Conference on Information and Knowledge Management, pages
289–298. ACM, 2008.
[34] N. Korula and S. Lattanzi. An eﬃcient reconciliation algorithm for social networks. Proceedings
of the VLDB Endowment, 7(5):377–388, 2014.
[35] J. Leskovec, D. Huttenlocher, and J. Kleinberg. Predicting positive and negative links in
online social networks. In Proceedings of the 19th International Conference on World Wide
Web (WWW), pages 641–650. ACM, 2010.
[36] J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection.
http://snap.stanford.edu/data, June 2014.
[37] J. Leskovec and J. J. Mcauley. Learning to discover social circles in ego networks. In Advances
in Neural Information Processing Systems, pages 539–547, 2012.
[38] D. Liben-Nowell and J. Kleinberg. The link-prediction problem for social networks. Journal
of the Association for Information Science and Technology, 58(7):1019–1031, 2007.
[39] U. V. Luxburg, A. Radl, and M. Hein. Getting lost in space: Large sample analysis of the
resistance distance. In Advances in Neural Information Processing Systems, 2010.
[40] C. Mathieu and H. Zhou. Graph reconstruction via distance oracles. In International Colloquium on Automata, Languages, and Programming, pages 733–744. Springer, 2013.
[41] MOSEK ApS. The MOSEK Optimization Suite, 2017.
[42] L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing
order to the web. Technical report, Stanford InfoLab, 1999.
21

[43] B. Perozzi, R. Al-Rfou, and S. Skiena. DeepWalk: Online learning of social representations.
In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery
and Data Mining, pages 701–710. ACM, 2014.
[44] M. J. Rattigan and D. Jensen. The case for anomalous link discovery. ACM SIGKDD Explorations Newsletter, 7(2):41–47, 2005.
[45] L. Reyzin and N. Srivastava. On the longest path algorithm for reconstructing trees from
distance matrices. Information Processing Letters, 101(3):98–100, 2007.
[46] M. Saerens, F. Fouss, L. Yen, and P. Dupont. The principal components analysis of a graph,
and its relationships to spectral clustering. In ECML, volume 3201, pages 371–383, 2004.
[47] P. Sarkar and A. Moore. A tractable approach to ﬁnding closest truncated-commute-time
neighbors in large graphs. In Proceedings of the Twenty-Third Conference Annual Conference
on Uncertainty in Artificial Intelligence (UAI-07), pages 335–343, 2007.
[48] D. A. Spielman. Trees and distances. University Lecture, 2012.
[49] D. A. Spielman and N. Srivastava. Graph sparsiﬁcation by eﬀective resistances. SIAM Journal
on Computing, 40(6):1913–1926, 2011.
[50] E. A. Stone and A. R. Griﬃng. On the Fiedler vectors of graphs that arise from trees by Schur
complementation of the Laplacian. Linear Algebra and its Applications, 431(10):1869 – 1880,
2009.
[51] J. Sun, S. Boyd, L. Xiao, and P. Diaconis. The fastest mixing Markov process on a graph and
a connection to a maximum variance unfolding problem. SIAM Review, 48(4):681–699, 2006.
[52] H. Tong, C. Faloutsos, and J.-Y. Pan. Fast random walk with restart and its applications.
2006.
[53] C. E. Tsourakakis, M. Mitzenmacher, J. Blasiok, B. Lawson, P. Nakkiran, and V. Nakos.
Predicting positive and negative links with noisy queries: Theory & practice. arXiv preprint
arXiv:1709.07308, 2017.
[54] U. Von Luxburg, A. Radl, and M. Hein. Hitting and commute times in large graphs are often
misleading. arXiv preprint arXiv:1003.1266, 2010.
[55] U. Von Luxburg, A. Radl, and M. Hein. Hitting and commute times in large random neighborhood graphs. Journal of Machine Learning Research, 15(1):1751–1798, 2014.
[56] D. M. Wittmann, D. Schmidl, F. Blöchl, and F. J. Theis. Reconstruction of graphs based on
random walks. Theoretical Computer Science, 410(38):3826 – 3838, 2009.
[57] L. Yen, F. Fouss, C. Decaestecker, P. Francq, and M. Saerens. Graph nodes clustering based
on the commute-time kernel. Advances in Knowledge Discovery and Data Mining, 2007.
[58] E. Zheleva, E. Terzi, and L. Getoor. Privacy in social networks. Synthesis Lectures on Data
Mining and Knowledge Discovery, 3(1):1–85, 2012.

22

