New Resistance Distances with Global Information on Large Graphs

Abstract
We consider the problem that on large random geometric graphs, random walk-based
distances between nodes do not carry global
information such as cluster structure. Instead, as the graphs become larger, the distances contain mainly the obsolete information of local density of the nodes. Many distances or similarity measures between nodes
on a graph have been proposed but none
are both proved to overcome this problem
or computationally feasible even for small
graphs. We propose new distance functions
between nodes for this problem. The idea
is to use electrical flows with different energyfunctions. Our proposed distances are proved
analytically to be metrics in Lp spaces, tokeep global information, avoiding the problem, and can be computed efficiently for large
graphs. Our experiments with synthetic andreal data confirmed the theoretical properties
and practical performances of our proposed
distances.

1

Introduction

The graph Laplacian is a popular tool to extract information from graphs for various purposes. It is ameans to utilize global graph topology for classification with kernels (Smola and Kondor, 2003), graph cut(Shi and Malik, 1997) and clustering (von Luxburg,
2007; Bühler and Hein, 2009). It is particularly usefulin tasks such as semi-supervised learning (Zhou et al.,
2003; Belkin et al., 2006; Chapelle et al., 2010) wheregraphs encode unlabelled data distributions in learning. It is a standard tool in manifold and high dimensional data learning (Belkin and Niyogi, 2003), where

Preliminary work. Under review by AISTATS 2016. Do
not distribute.

only nearest neighbor graphs would give reliable information of the underlining distributions. Beyond theselearning tasks, it also finds applications in other areas
such as electrical networks (Klein and Randić, 1993;
Bollobás, 1998; I. Gutman, 2004), random walks (Lovasz, 1996) and collaborative filtering (Fouss et al.,2007). The key point is that the graph Laplacians are
the information bottleneck on the way to find distributions. It is of great importance to be able to extract
the right information from the graphs to have the desired distributions.
The common problem is that, given graphs representing unknown distributions of data, the task is to recover the original distributions using graph topologies. In case that graphs encode similarity or neighborhood relationship, a continuously high density regionof the original distribution usually contains many wellconnected nodes. In order to recognize these nodes
belonging to the same region, in the framework of distance or similarity-based learning, these nodes shouldhave small distances to each others (compared to theother nodes of different regions). In graph embedding,these nodes should be close to each other in terms ofthe distances in the embedding space. Therefore, thedesirable distance should contain global information ofgraphs such as cluster structures, bottlenecks and density of the region in between nodes.
For this aim, many similarity and distance functions ongraphs use the idea from random walks (Lovasz, 1996;
Bollobás, 1998) with the intuition that nodes from thesame clusters can be reached by many paths of highprobability. However, it is found that, in large graphs,
distances based on graph Laplacians differ from the intuition, converging to some noninformative functions(Nadler et al., 2009; von Luxburg et al., 2010, 2014).
This is usually attributed to the fact that long random walks tend to forget where they start (the mixingof random walks) (Lovász and Simonovits, 1990). To
counter the effect of long random walks (Fouss et al.,2007), many methods give more weights to short walks
compared to long ones (Yen et al., 2008; Wu et al.,2012; Chebotarev, 2012). However, these methods are
not proved to overcome the problem.

Manuscript under review by AISTATS 2016

It is proved analytically for resistance distance (alsohitting and commute time distances) on random geometric graphs (Penrose, 2003) that as graphs becomelarger, the distances converge to a function of local
density (von Luxburg et al., 2010, 2014), losing global
information. This is called the global information loss
problem. This is a problem for all methods based
the graph Laplacians such as (i) the graph Laplacianbased embedding and graph kernels (Smola and Kondor, 2003), (ii) random walk-based measures (Klein
and Randić, 1993; I. Gutman, 2004; Fouss et al., 2007)
and (iii) spectral clustering (von Luxburg, 2007). Unfortunately, the only known method that provably
overcome this problem, p resistance distance (Herbster
and Lever, 2009; Alamgir and von Luxburg, 2011), is
computationally infeasible even for very small graphs.
In this work, we propose two distance functions,
named Rp and R12 distances, that (1) provably overcome the global information loss problem and (2) arecomputationally feasible for large graphs. Our proposed distances would be the first to satisfy both conditions of overcoming the problem and being practically applicable. The idea is to use electrical flows
as in resistance distance, as the flows contains all theinformation from the graph, and can be computed efficiently for all pairs of nodes altogether. To preventthe global information loss problem, different energyfunctions are proposed, giving higher weights to theglobal part of the distance functions. Global information of the graph is proved analytically to be kept
(in the same manner as p resistance distance). The
distances are also proved to be metrics, resulting inembeddings of the graphs into Lp spaces. In our experiments, our proposed distances consistently showed
the cluster structures in large graphs while resistancedistance failed.
The paper is organized as follows. In Section 2, weanalyze the problem of global information loss in random walk-based distances and show how to overcome
the problem using variants of resistance distance. We
propose the two distance functions for this problem in
Section 3 and show their useful properties. We show
experimentally the merit of these distances in simulation in Section 4 and real data in Section 5, and thenconclude the paper.

2

Problem Setting and Terminology

2.1

Distances on Random Geometric Graphs

Random Geometric Graph. Random geometric graphs are generated from a distribution in somespaces (Bollobás, 1998; Penrose, 2003). They areused to investigate whether statistical estimations ongraphs can retain properties of the distributions thatare desirable in learning processes such as cluster/classstructures. The objective is that, from the graphs,
clusters, classes, and bottlenecks should be detectedbased solely on the graphs’ topologies. Nodes of graphs
are sampled according to the distribution (Penrose,
2003). Edges between nodes are generated by connecting either  neighbors or k nearest neighbors. The
weight of an edge w(xi , xj ) determines if it is a similarity graph (e.g. conductance) or dissimilarity graph(e.g. resistance) with different weighting schemes suchas: w(xi , xj ) = 1 (unweighted), w(xi , xj ) = kxi − xj kor w(xi , xj ) = exp(kxi − xj k2 /δ 2 ).
The problem setting is that a random geometric graph
G = (X, E, A), where X = {xi }ni=1 is the node set ofn nodes drawn randomly from a smooth distributionp (Alamgir and von Luxburg, 2011), and E is the edge
set with kEk = m. Let L−1 be the pseudo-inverseof L = D − A, which is the graph Laplacian, with D
denoting the degree matrix with node degrees on the
diagonal, and A is the edge weight matrix.
Distance on Graph. A distance function d on graph
G is defined as d : (X, X) → R. For any pair of nodes(xs , xt ), some examples are:• sp(xs , xt ): shortest path distance between xs andxt .
• ht(xs , xt ): hitting time distance: the expected
time passage from xs to arrive at xt .
• ct(xs , xt ) = ht(xs , xt ) + ht(xt , xs ): commute time
distance.
1
ct(xs , xt ): resistance distance.
• res(xs , xt ) = 2m

• pres(xs , xt ): p resistance distance generalizing
resistance distance (Alamgir and von Luxburg,
2011).
Flow and Energy on Graph. Many distances andtheir properties are derived from flows from one nodeto another on a graph defined as follows.
• Y : a flow is a set of real values assigned to edgesof the graph: Y ∈ R|E| (Bollobás, 1998).
• A unit flow from xs to xt is a flow with a total
flow 1 coming in at xs and going out at xt .
• Ip (xs , xt ):p f low from xs to xt satisfying:P
Ip (xs , xt ) = arg minY e∈E re |ye |p for p ∈R, p ≥ 1 and Y = {ye }e∈E being any unit flowfrom xs to xt (Alamgir and von Luxburg, 2011;
Herbster and Lever, 2009).
defManuscript under review by AISTATS 2016

• I2 (xs , xt ): (2 flow) the electrical flow from xs to
xt .

high density region (von Luxburg et al., 2010; Alamgir
and von Luxburg, 2011):• Ep : R|E| → R: p energy function. For any flow
Y:Xdef
Ep (Y ) =re |ye |p .
(1)e∈E

p energy function is related to the distances as follows: res(xs , xt ) = E2 (I2 (xs , st )) and pres(xs , xt ) =Ep (Ip (xs , xt )) as Ip -s are unit flows (Bollobás, 1998;
Alamgir and von Luxburg, 2011). From here on, we
use energy (of unit flow) to refer to resistance distance.
We define global and local parts of energy function Ep(: R|E| → R) for later proofs as follows. For (xs , xt ):lim

E2localn→∞ E global
2

E2 (I2 (xs , xt ))= 1.
n→∞ 1/ds + 1/dt

= ∞, lim(2)

where ds and dt are the degrees of node xs and xt .
As resistance distance only contains information of local density, it has global information loss problem. A
demonstration is shown in Figure (1).

3

Rp and R12 distances• E local : the set of edges incident to either nodedef
in the pair: E local (xs , xt ) = {e}xs ∈e,e∈E ∪{e}xt ∈e,e∈E .

In this section, we propose two distance functions thatgive higher weights to the global part of total energy
to reflect global information of the graph. We thenshow their metric, embedding properties, computational analysis, and phase transition by changing parameters.

• E global :the set of remainingdef
E global (xs , xt ) = E \ E local (xs , xt ).

3.1

edges:• Eplocal : local energy function of Ep . For any q ∈ R:
def

X

Eplocal (Iq (xs , xt )) =re |Iq (xs , xt )e |p .

e∈E local (xs ,xt )• Epglobal : global energy function of Ep . For any
q ∈ R:
def

Epglobal (Iq (xs , xt )) =X

re |Iq (xs , xt )e |p .

e∈E global (xs ,xt )According to definitions of local and global set, Eplocal
and Epglobal are local and global parts of energy function Ep and Ep = Eplocal +Epglobal . Please note that thisis a slightly different version from the one defined in(von Luxburg et al., 2010; Alamgir and von Luxburg,
2011) without changing its results.
2.2

Global Information Loss problem

Global information loss problem is that distances orsimilarity measures do not contain the global information of graphs such as clusters or bottlenecks. Global
information is necessary for learning purposes such as
clustering and classification. Even though this phenomenon is known experimentally for large graphs(Nadler et al., 2009), it can be proved rigorously
only for resistance distance on large random geometricgraphs. Resistance distance does not contain the information of the area between the nodes (global information), regardless whether between them is a low orDefinition

The desideratum is that the two nodes should have along distance if they are from different clusters. Therefore, the distances should reflect not only geodesic distance (like shortest path distance), but also the densityof the space in between the two nodes. Following thesame principle as p resistance distance (Alamgir andvon Luxburg, 2011), we wish to design distances thatcan be decomposed into global and local parts. To reflect global information such as clusters, the distances
should have the global part at least of the same magnitude as the local part.
The global information loss problem on large graphs
occurs due to two issues. The first issue is that large
graphs divide a unit flow into many paths, resulting
in small flows on edges in the global part (ye > ye00for e ∈ E local , e ∈ E global ). The second
is that
P issueelectrical energy function E2 (I2 ) =re ye2 , quadratic
on flows on edges, further reduces the weights of energy
0on the global parts (re ye2 >> re ye20 ).
Our solution to the global information loss problem
of resistance distance is to address the second issue,
electrical energy function. We propose to use Ep for
p < 2 to define energies (distances)1 based on electricalflow I2 (xs , xt ) ∈ R|E| . Ep with p < 2 can give a higher
weight to the global part of the total energy. That is,0
for smaller p, the difference between re ye2 and re ye20 will
not be amplified as much as p = 2. We propose two
distances: Rp distance and R12 distance as follows.
1
For unit flows, resistance distance coincides with energy.

Manuscript under review by AISTATS 2016
E globalDefinition 3.1. (Rp distance).
def

1. For unweighted graph wij = 1: limn→∞ E1local →1∞ almost surely as n → ∞ and  → 0.

1

Rp (xs , xt ) = (Ep (I2 (xs , xt ))) pX1=(
re |I2 (xs , xt )e |p ) p .

(3)

2. For Euclidean weighted graph with wij
E1global
E1locald(xi , xj ):and  → 0.

e∈EDefinition 3.2. (R12 distance) For a given α:d(x ,x )2
exp( iδ2 j ):R12 (xs , xt ) = αR2 (xs , xt ) + (1 − α)R1 (xs , xt ) (4)
X
X
1
=α(
re |I2 (xs , xt )e |2 ) 2 + (1 − α)re |I2 (xs , xt )e |.
e∈E

e∈E

One unique feature of our distances is that, we canuse the information of I2 in the same way as sparsityinducing norms in Optimization. The distances haveparameters p and α to interpolate, containing R2 =p
E2 (I2 ) and R1 = E1 (I2 ) in their spectra. For p → 1
and α → 0, they both converge to R1 : the total flows
on all edges added together. They have interesting
properties as follows.
• Consider the case that flows between the two
nodes can be separate paths as in Figure 2. E1 (I2 )is the harmonic mean of the lengths of all paths.
It is equal to the shortest path added with theamount of flow outside of the shortest paths (theshaded region).
• Rp and R12 distances are different from p resistance distance, randomized shortest path distanceand others in the sense that they do not converge
to shortest path distance. In all spectra of theirparameters, they contain the information of connectivity in between the two nodes present in I2(taking into account all paths, instead of only theshortest path).
3.2

Dealing with Global Information Loss

Intuitively, E1 (I2 ) energy function overcomes the
problem of E2 (I2 ) by giving more weights to global
part. Any s, t min cut would contain the edges withthe total flow weight of 1, having total energy of thesame order of magnitude as that of the local part ofE1 (I2 ) (containing only one s, t min cut). Hence, theglobal part, consisting of many disjoint s, t min cuts,
dominates the local one. We prove that, in E1 (I2 ),the global energy dominates the local energy for neighborhood and knn graphs as follows.
Theorem 3.3. For connected -neighborhood random
geometric graphs constructed from a valid region X in
Rd (von Luxburg et al., 2014), the global part of E1 (I2 )(E1global (I2 )) dominates the local part (E1local (I2 )) almost surely (for any pair (xs , xt )) as n → ∞. Concretely, the following statements hold:→ ∞ almost surely as n → ∞3. For Gaussian weighted graph with wij

def

=

=

E1global
E1local→ ∞ almost surely as).
n → ∞,  → 0 and O(δ) > O( √ − ln()Theorem 3.4. For connected k-nearest neighbor (random geometric) graphs constructed from a valid region
X in Rd (von Luxburg et al., 2014), the global partof E1 (I2 ) dominates the local part almost surely as
n → ∞. Concretely, there exist constants c1 , c2 thatthe following statements hold:E global

1. For unweighted graph wij = 1: limn→∞ E1local →1∞ almost surely as n → ∞, k > log(n) and nk → 0√
with a probability of at least 1 − c1 n exp(−c2 nk)(converging to 1).
2. For Euclidean weighted graph with wijd(xi , xj ):E1global
E1local=→ ∞ almost surely as n → ∞,knk > log(n) and→ 0 with a probability of at√least 1 − c1 n exp(−c2 nk) (converging to 1).
3. For Gaussian weighted graph with wij=

E1global→ ∞ almost surely as
E1local1kn → ∞, k > log(n), n → 0 and O(δ) = ( nk ) d withda probability of at least 1−c1 n exp(−c2 k ·log( nk ) 2 )d(x ,x )2
exp( iδ2 j ):(converging to 1).
Please find the proofs in the supplementary material. The valid region definition is the same as in(von Luxburg et al., 2014), but in fact, we only require that distribution p is bounded and the graphs
are connected. Note that the conditions of parametersin these theorems cover all the conditions for hitting
times and commute distances to lose global information (von Luxburg et al., 2014). Hence, our proposed
distance can retain global information in the cases that
resistance distance cannot.
3.3

Lp Space Embedding of Graphs

We show that Rp and R12 distances are metrics in corresponding Lp spaces. Therefore, the distances naturally lead to embeddings of the graphs onto Lp spacesthat preserve global information. The idea is to utilize
the formulation of I2 from L−1 . Let ei ∈ Rn denote a
vector of all zeroes except for the i-th position having
value 1.

Manuscript under review by AISTATS 2016

10

0.9

20

0.8

30

0.7

40

0.6

300

50

0.5

400

60

0.4

100

0.5

200
0.4

0.3

500
0.2
70

0.3

80

0.2

90

0.1

600
0.1
700

100

800
20

40

60

80

100

0
100

200

300

400

500

600

700

800

Figure 1: Heatmaps of pairwise resistance distances for a twocluster distribution (details in Section 4.1) with different numbersof data points sampled: 100 points (left) and 800 points (right).
Block structures of the distance matrices, indicating cluster structures, were lost for large graphs.
Lemma 3.5. Let V (i) = L−1.i denote the i-th columnof L−1 , respectively. Then,
V (s) − V (t) = L−1 (es − et )(5)is a possible potential assignment to the nodes of the
network that makes the unit flow from xs to xt .
Proof in the supplementary file for brevity.
Theorem 3.6. (Lp space embedding) The following
embedding f of the nodes of graph G into an Lp space:f : X → R|E|(s)

xs → f (xs ) = {· · · ,

Vi

(s)

− Vj

(p−1)/prij, · · · }T(i,j)∈ E(6)makes the p-norm of the space coincide with Rp :kf (xs ) − f (xt )kp = Rp (xs , xt ).
Proof in the supplementary file for brevity.

Figure 2: Composition of E1 (I2 ) in a simple network: shortest path distance (total flow in non-shaded region) plus theamount of flow on longer paths (shaded
region).

This is different from p resistance distance, which is
obtained by solving an O(n2 ) number of optimization
problems, each with m variables and n linear equality
constraints.
3.5

The phase transition

Rp and R12 have trade-off parameters p and α respectively. When p = 1 and α = 0, the global energy
dominates the local one as both distances converge to
R1 (I2 ). When p = 2 and α = 1, the local one dominates global ones as both distances converge R2 (I2 ).
Due to the the continuity of the distances as functionsof p and α, there should be phase transition pointsp∗ and α∗ that separate the dominant sides: local or
global. The exact transition points are hard to compute (Alamgir and von Luxburg, 2011), but can be estimated roughly. For example, let β ∗ = 1 − α∗ , then,with the usual definition of local and global parts as in(Alamgir and von Luxburg, 2011), the transition point
can be characterized as follows.

Corollary 3.7. Both Rp and R12 are metrics.
O(β ∗ ) = O(

R12 is also a metric because it is a convex combinationof two metrics.
3.4

Computing Rp and R12 distances

We show that these distances can be computed efficiently for all pairs of nodes in large graphs, as opposed
to p resistance distance even in small graphs.
Theorem 3.8. Given the inverse Laplacian matrix
L−1 , the Rp and R12 distances between any pair ofnodes can be computed in O(m) time.
Proof. The formulas (5) and (6) allow us to compute
Rp and R12 distances in O(m) time complexity fromL−1 as computing the p-norm in an m dimensional
space. Therefore, the total cost of computing all pairwise distances of a graph is the time to inverse thematrix L plus O(mn2 ).

E2 (I2 )local)
E1 (I2 )global(7)

The phase transition points are necessary in the casesthat we wish to have local information having the sameor higher weight compared to global one.
3.6

Comparison with p Resistance DistanceOur proposed distances and p resistance distance aredifferent in the flows used. p resistance distance uses
Ip to address the first issue of E2 (I2 ). However, forall pairs of nodes (xs , xt ), Ip (xs , xt ) is computed independently by solving an optimization problem, making this method computationally infeasible even for asmall. On the other hand, our proposed distances use
I2 , which can be computed for all pairs of nodes altogether, are computationally efficient for large graphs.
Our proposed distances and p resistance distance areManuscript under review by AISTATS 2016

1.05

Clustering Accuracy

similar in energy function Ep to address the second issue of E2 (I2 ). For small p (< 2), Ep gives more weightto the global part of corresponding flows (I2 and Ip ),making Epglobal larger. This is key to have global information not to be dominated by local information.
Fortunately, addressing the second issue is enough toovercome the global information loss problem.

1

0.95

0.9

R2
R1

0.85

Rp
R12

Simulation

We showed simulated experiments in which graphs
were generated with known cluster structures to showthat our distances can overcome the global information
loss problem. The distances being compared were: (i)R2 (square roots of resistance distances), (ii) R1 , (iii)1
Rp with p = d+1
d , and (iv) R12 with α = 1 − k·n1/d .
These values of parameters p and α were set to bearound the transition points (these are recommended
values). Note that, p resistance distance, the only
method that provably overcome the problem, cannot
be experimented due to its high computational complexity even for very small graphs.
The distances are compared by the quality of theirclustering solutions using clustering accuracy. Clustering accuracy measures how clustering results agreewith the known labels (each label corresponds to acomponent in the distribution, expecting as a clusterin graph). To compare metric distances for clustering
purpose, in all our experiments, we used k-medoids
algorithm on these (precomputed) distances and reported the accuracy of the best assignment of clusters
to the (given) classes of data. Distances were also visualized in heat maps for intuition (supplementary file).
4.1

Two-cluster caseWe designed simulations with clear cluster structures
to show that our proposed distances take into accountglobal graph information. The experimental setup was
as follows. Mixtures of two anisotropic Gaussian components fi (x) = c · exp(− 2δ12 |x − mi |2 ), i = 1, 2, withx, mi ∈ Rd were generated, having standard deviation in any direction of δ = 1. n/2 points were sampled independently from each component, then all then points were used to construct k ≈ log(n) nearest
neighbor graphs (random geometric graphs). Data
points from the same component are expected forma cluster in graphs, stored in each half of the data
set. Distances taking global information of graphs into
account should have short distances for the pairs of
points in the same half. A demo of the global information loss problem for resistance distance is shownin Figure 1.

50

100

200

400

800

Data size

1
0.95

Clustering Accuracy

4

0.8

0.85

R2

0.75

R1
Rp

0.65

R12

0.55
5

10

15

20

Dimension

Figure 3: Clustering accuracies for the distances at(a) different data sizes (left, for dimension 7) and (b)different dimensions (right, for data size of 200) of thespaces (x axis).
4.2

Data size effect

In this simulation, we set d = 7, |m1 − m2 | = 4 (being
4 apart from each other) for different sizes of graphs:
n = 50 to 800, with the corresponding numbers ofnearest neighbors of k = 5 to 9 (namely, k ∼= log(n)).2
Clustering accuracy of the distances were shown in
Figure 3 (a). We could observe that clustering accuracy of R2 decreased as n increased. However, clustering accuracies of our proposed distances remained
stable and significantly higher than that of R2 . The
results of our proposed distances were also much morestable (low variances) compared to that of R2 . This
also confirmed the merit of our proposed distances.
4.3

Dimensional effectWe also found experimentally that as the dimensionof the space (d) increased (with a fixed data size), resistance distance also lost global information in thesame way as data size increased. We showed simulations over different dimensions d = 5, 10, 15 and 20
for n = 2002 . We showed clustering accuracy for different dimensions in Figure 3 (b). We could observed
2
The heat maps of the distances are shown in the supplementary file for intuition.

Manuscript under review by AISTATS 2016

Table 1: Clustering accuracies of the distances for different data sets.

idian
pop
spect
ecoli
iris
columnbreastionosphereuser

Clustering accuracy (in percentage)
R2
R1
Rp
R12
69.4±2.965.8±2.164.7±2.465.5±1.786.5±8.959.8±6.4
62.8±6.4
61.4±9.2
72.2±6.7
57.4±5.0
57.5±3.560.3±9.877.4±10.7 67.9±8.4
74.1±6.473.8±9.860.1±9.1 87.9±7.5 71.9±17.3 78.6±7.1
69.7±0.0 73.4±1.7
72.6±2.0 73.2±1.8
93.7±10.7 89.6±12.0 79.6±12.2
88.1±1.3
60.3±2.6 65.2±0.0
65.2±0.0 63.6±4.5
44.2±3.0 49.4±2.4
49.1±4.4 49.0±4.3

that, as the dimension became larger, our proposed
distances were still able maintained high clustering accuracies while R2 could not. Our proposed distanceswere also more stable, having much lower variances.
This also confirmed the merit of our proposed distances. However, in too high dimension spaces, nearest
neighbor distances are not reliable, making neighborhood graphs and all distances based on these graphs,
including our proposed distances, meaningless.

5

Experiments

We showed experiments on real supervised data withknown classes2 , to see whether our proposed distances
can discover cluster structures corresponding to classes
more effectively than resistance distance. We selected
data sets for classification from UCI Machine Learning repository3 with numerical attributes and the sizes
that the global information loss problem might occur(> 100 nodes). k nearest neighbor graphs were generated with k > log(n). We grouped nodes of graphs
according to their class labels to see if they formedclusters. We showed clustering accuracy for each data
set in Table 1. There were two scenarios. The first scenario was that the classes formed clear cluster structures, even when resistance distance failed to capture
the cluster structures, our distances were expected toshow them. The second scenario was that the classes
did not form cluster structures, therefore, the graphs
did not have clusters corresponding to the classes. In
this scenario, it was reasonable to expect that all the
distances failed to show cluster structures.
The clustering accuracies indicated that our proposed
distances performed well in practice. It could beobserved from Table 1 that clustering accuracies of
R2 were never significantly higher than those of our
proposed distances. Especially, clustering accuraciesof R2 were significantly lower in iris, column, iono3

http://archive.ics.uci.edu/ml/

sphere and user data sets. It is possible that our
proposed distances had higher clustering performances
than resistance distance (R2 ) because they overcame
the global information loss problem, as in the first scenario. It was also noteworthy that our proposed distances did not always guarantee performance improvements. This could be the second scenario that the data
might not suffer from global information loss problem
that we were targeting. Given that this was supervised
data and classes might not coincide with clusters, thisresult was very encouraging that our distances could
show cluster structures.
We show the heat maps of distances on real data toshow how clear cluster structures can be seen by using our proposed distances compared to resistance distance in Figure 4.

6

Conclusion

We proposed two distance functions, Rp and R12 , that
overcome the problem of global information loss inlarge graphs. Our proposed distances are proved tohave global information dominated local one if the parameters are properly set in the same manner as p
resistance distance. The distances are metrics, naturally leading to embeddings of graphs into Lp spaces.
They can be computed efficiently for large graphs. In
synthetic and real data experiments, they were shown
to be effective in capturing cluster structures while resistance distance failed even for simple cases. Future
work includes elucidating more theoretical propertiesof edge space embedding, scaling up the distances formassive data sets, transforming from distances to similarity measures such as kernels for classification andother tasks as well as applications.

Manuscript under review by AISTATS 2016

100
0.5

500
100

500

0
0.6
0.4
0.2

100

pop 300
500

500
100

100
0.6
0.4
0.2

spect 150
250

500

150

250

100

ecoli 200
300
100

300

50
0.8
0.6
0.4
0.2
0
1.2
1
0.8
0.6
0.4
0.2

50

iris 100

50

150

100

column 200
300
100

300

200
400
600
200

600

100
ionosph. 200
300

0.8
0.6
0.4
0.2
0
0.8
0.6
0.4
0.2
0

0.5

100

300

50

user 150
250

50

250

R2

0
0.6
0.4
0.2
0

250

500

100

100
50

150

100
200
300
100

300

200
400
600
600

100
200
300
100

500

0

500

50

0

250
50

300

15
10
5
0
15
10
5
0

0
15
10
5
0

500

150
250
50

250

300

100
50

100

2

100

150

0

150

50

150

6
4
2

100
200
300

200

600

0

250

8
6
4
2
0

5
100

50

50

150
2
1

200
100

10

100
200
300

150

2
1.5
1
0.5

100

300

200
400
600

300

0
4

50

250

Rp

1.5
1
0.5
0

300

300
100

0

2
1.5
1
0.5

100
200
300

4

5

R1

100

50

50

250

0.5

6

150
50

0
8
6
4
2

100
200
300

10

250

250

0

1

50
5

100

10
200

300

150

500

100

2
500

1

500

300

300

50

300
100

4

100

2

100

500

100

5

15
10
5

100
200
300

150

0
10

50

250
50

300
100

5

300

8
6
4
2

100

500

100

500

50

breast

300

500
100

150

15
10
5

100

idian 300

300

0
2

200
400
600

1
200

600

0
2.5
2
1.5
1
0.5

100
200
300
100

300

50

1

2

150

0.5

0

250
50

250

0

R12

Figure 4: Results on real datasets from UCI Machine Learning repository. The datasets were for classification.
We grouped the nodes according to their classes to see whether the distances on the generated graphs could show
cluster structures by having diagonal blocks with shorter pairwise distances. The first three datasets showed thatno distances could discover cluster structures, probably because the classes did not form clusters. For the restof the datasets, our distances could always show clear cluster structures. On the other hand, resistance distanceeither not clearly showed the cluster structures, or completely failed to show them.

Manuscript under review by AISTATS 2016

References
Morteza Alamgir and Ulrike von Luxburg. Phase transition in the family of p-resistances. In J. ShaweTaylor, R.S. Zemel, P. Bartlett, F.C.N. Pereira, and
K.Q. Weinberger, editors, Advances in Neural Information Processing Systems 24, pages 379–387, 2011.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6):1373–1396,
June 2003. ISSN 0899-7667.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani.
Manifold regularization: A geometric framework forlearning from labeled and unlabeled examples. Journal of Machine Learning Research, 7:2399–2434,
2006.
Bélla Bollobás.
Verlag, 1998.

Modern Graph Theory.

Springer-Thomas Bühler and Matthias Hein. Spectral clustering
based on the graph p-laplacian. In ICML, pages 81–
88, 2009.
Olivier Chapelle, Bernhard Schölkopf, and Alexander
Zien. Semi-Supervised Learning. The MIT Press, 1stedition, 2010. ISBN 0262514125, 9780262514125.
Pavel Chebotarev. The walk distances in graphs. Discrete Applied Mathematics, 160(10-11):1484–1500,
2012.
Francois Fouss, Alain Pirotte, Jean-Michel Renders,and Marco Saerens. Random-walk computation ofsimilarities between nodes of a graph with application to collaborative recommendation. IEEE Transactions on Knowleldge and Data Engineering, 19(3):355–369, March 2007.
Mark Herbster and Guy Lever. Predicting the labellingof a graph via minimum $p$-seminorm interpolation. In COLT, 2009.
W. Xiao I. Gutman. Generalized inverse of the laplacian matrix and some applications. Bulletin. Classedes Sciences Mathmatiques et Naturelles. Sciences
Mathmatiques, 129(29):15–23, 2004.
D. J. Klein and M. Randić. Resistance distance. Journal of Mathematical Chemistry, 12(1):81–95, December 1993.
Laszlo Lovasz. Random walks on graphs: A survey.
In Combinatorics, Paul Erdos is Eighty, volume 2,
1996.
László Lovász and Miklós Simonovits. The mixing rateof markov chains, an isoperimetric inequality, andcomputing the volume. In FOCS, pages 346–354,
1990.
Boaz Nadler, Nathan Srebro, and Xueyuan Zhou. Statistical analysis of semi-supervised learning: The

limit of infinite unlabelled data. In NIPS, pages
1330–1338, 2009.
Mathew Penrose. Random Geometric Graphs. Publisher: Oxford University Press, July 3 2003. ISBN0198506260.
Jianbo Shi and Jitendra Malik. Normalized cuts andimage segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22:888–905,
1997.
Alex J. Smola and Risi Kondor. Kernels and regularization on graphs. In COLT, pages 144–158, 2003.
Ulrike von Luxburg. A tutorial on spectral clustering.
Statistics and Computing, 17(4):395–416, 2007.
Ulrike von Luxburg, Agnes Radl, and Matthias Hein.
Getting lost in space: Large sample analysis of theresistance distance. In Advances in Neural Information Processing Systems 23, pages 2622–2630, 2010.
Ulrike von Luxburg, Agnes Radl, and Matthias Hein.
Hitting and commute times in large random neighborhood graphs. Journal of Machine Learning Research, 15(1):1751–1798, 2014.
Xiao-Ming Wu, Zhenguo Li, Anthony Man-Cho So,
John Wright, and Shih-Fu Chang. Learning withpartially absorbing random walks. In NIPS, pages
3086–3094, 2012.
Luh Yen, Marco Saerens, Amin Mantrach, andMasashi Shimbo. A family of dissimilarity measures
between nodes generalizing both the shortest-pathand the commute-time distances. In KDD, pages
785–793, 2008.
Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal,
Jason Weston, and Bernhard Schölkopf. Learningwith local and global consistency. In NIPS, 2003.