arXiv:1803.05084v1 [cs.SI] 14 Mar 2018

Local Partition in Rich Graphs
Scott Freitas

Hanghang Tong

Arizona State University
Tempe, Arizona
scott.freitas@asu.edu

Arizona State University
Tempe, Arizona
hanghang.tong@asu.edu

Nan Cao

Yinglong Xia

Tongji University
Shanghai, China
nan.cao@gmail.com

Huawei
Santa Clara, California
yinglong.xia@huawei.com

ABSTRACT
Local graph partitioning is a key graph mining tool that allows
researchers to identify small groups of interrelated nodes (e.g. people) and their connective edges (e.g. interactions). Because local
graph partitioning is primarily focused on the network structure
of the graph (vertices and edges), it often fails to consider the additional information contained in the attributes. In this paper we
propose—(i) a scalable algorithm to improve local graph partitioning by taking into account both the network structure of the graph
and the attribute data and (ii) an application of the proposed local
graph partitioning algorithm (AttriPart) to predict the evolution
of local communities (LocalForecasting). Experimental results
show that our proposed AttriPart algorithm finds up to 1.6×
denser local partitions, while running approximately 43× faster
than traditional local partitioning techniques (PageRank-Nibble
[1]). In addition, our LocalForecasting algorithm shows a significant improvement in the number of nodes and edges correctly
predicted over baseline methods.
ACM Reference Format:
Scott Freitas, Hanghang Tong, Nan Cao, and Yinglong Xia. 2018. Local
Partition in Rich Graphs. In Proceedings of ACM KDD (KDD’18). ACM, New
York, NY, USA, Article 4, 9 pages. https://doi.org/10.475/123_4

1

INTRODUCTION

Motivation. With the rise of the big data era an exponential amount
of network data is being generated at an unprecedented rate across
many disciplines. One of the critical challenges before us is the
translation of this large-scale network data into meaningful information. A key task in this translation is the identification of local
communities with respect to a given seed node 1 . In practical terms,
the information discovered in these local communities can be utilized in a wide range of high-impact areas—from the micro (protein
interaction networks [13] [26]) to the macro (social [21] [4] and
transportation networks).
1 we

interchangeably refer to local community as a local partition

Permission to make digital or hard copies of part or all of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed
for profit or commercial advantage and that copies bear this notice and the full citation
on the first page. Copyrights for third-party components of this work must be honored.
For all other uses, contact the owner/author(s).
KDD’18, August 2018, London, United Kingdom
© 2018 Copyright held by the owner/author(s).
ACM ISBN 123-4567-24-567/08/06. . . $15.00
https://doi.org/10.475/123_4

Problem Overview. How can we quickly determine the local
graph partition around a given seed node? This problem is traditionally solved using an algorithm like Nibble [19], which identifies
a small cluster in time proportional to the size of the cluster, or
PageRank-Nibble, [1] which improves the running time and approximation ratio of Nibble with a smaller polylog time complexity.
While both of these methods provide powerful techniques in the
analysis of network structure, they fail to take into account the
attribute information contained in many real-world graphs. Other
techniques to find improved rank vectors, such as attributed PageRank [10], lack a generalized conductance metric for measuring
cluster "goodness" containing attribute information. In this paper,
we propose a novel method that combines the network structure
and attribute information contained in graphs—to better identify
local partitions using a generalized conductance metric.
Applications. Local graph partition plays a central role in many
application scenarios. For example, a common problem in recommender systems is that of social media networks and determining
how a local community will evolve over time. The proposed LocalForecasting algorithm can be used to determine the evolution of
local communities, which can then assist in user recommendations.
Another example utilizing social media networks is ego-centric
network identification, where the goal is to identify the locally important neighbors relative to a given person. To this end, we can use
our AttriPart algorithm to identify better ego-centric networks
using the graph’s network structure and attribute information. Finally, newly arrived nodes (i.e., cold-start nodes) often contain few
connections to their surrounding neighbors, making it difficult to
ascertain their grouping to various communities. The proposed
LocalForecasting algorithm mitigates this problem by introducing additional attribute edges (link prediction), which can assist in
determining which local partitions the cold start nodes will belong
to in the future.
Contributions. Our primary contributions are three-fold:
• The formulation of a graph model and generalized conductance metric that incorporates both attribute and network
structure edges.
• The design and analysis of local clustering algorithm AttriPart and local community prediction algorithm LocalForecasting. Both algorithms utilize the proposed graph
model, modified conductance metric and novel subgraph
identification technique.

KDD’18, August 2018, London, United Kingdom
• The evaluation of the proposed algorithms on three realworld datasets—demonstrating the ability to rapidly identify
denser local partitions compared to traditional techniques.
Deployment. The local partitioning algorithm AttriPart is
currently deployed to the PathFinder [7] web platform (www.
path-finder.io), with the goal of assisting users in mining local network connectivity from large networks. The design and deployment
challenges were wide ranging, including—(i) the integration of four
different programming languages, (ii) obtaining real-time performance with low cost hardware and (iii) implementation of a visually
appealing and easy to use interface. We note that the AttriPart
algorithm, deployed to the web platform, has performance nearly
identical to the results presented in section 4.

S. Freitas et al.
Having outlined the notation, we define the problem of local
partitioning in rich graphs as follows:
Problem 1. Local Partitioning in Rich Graphs
Given: (1) an undirected, unweighted graph G = (V , E), (2) a seed
node q ∈ V and (3) attribute information for each node v ∈ V
containing a k-dimensional attribute vector x i —with an attribute
matrix X = [x 1, x 2, ..., x n ] ∈ Rk ×n representing the attribute vector
for each node v.
Output: a subset of vertices S ⊂ V such that S best represents the
local partition around seed node q in graph B.
Table 1: Symbols and Definition
Symbol
G, A, B
n, m
me
p, mp

Definition

s, q, ϕo
W
S
ϵ, ϵt
tm , n s
αn , αr

preference vector, seed node & target conductance
lazy random walk transition matrix
set of vertices representing local partition
rank truncation and iteration thresholds
rank vector iterations; number of vertices to sweep
AttriPart & LocalProximity teleport values

t s , nw
T ; D, L
µ(L), σ (L)

subgraph relevance threshold & number of walks
subgraph of B; walk count dictionary & list
mean and standard deviation of L

te

network, attribute & combined graphs
number of nodes & edges in graphs G, A, B
number of edges in B after LocalForecasting
number of nodes & edges in T

edge addition threshold

Figure 1: Close-up of the AttriPart algorithm on the
PathFinder web platform.

3
This paper is organized as follows—Section 2 defines the problem of local partitioning in rich graphs; Section 3 introduces our
proposed model and algorithms; Section 4 presents our experimental results on multiple real-world datasets; Section 5 reviews the
related literature; and Section 6 concludes the paper.

2

METHODOLOGY

This section first describes the preliminaries for our proposed algorithms, including the graph model and modified conductance metric.
Next, we introduce each proposed algorithm—(1) LocalProximity,
(2) AttriPart and (3) LocalForecasting. Finally, we provide an
analysis of the proposed algorithms in terms of effectiveness and
efficiency.

PROBLEM DEFINITION

In this paper we consider three graphs—(1) an undirected, unweighted structure graph G = (V , E), (2) an undirected, weighted
attribute graph A = (V , E) and (3) a combined graph consisting
of both G and A that is undirected and weighted B = (V , E). In
each graph, V is the set of vertices, E is the set of edges, n is the
number of vertices and m is the number of edges (i.e. G, H and B
contain the same number of vertices and edges by default). In order
to denote the degree centrality we say δ (v) is the degree of vertex
v. We use bold uppercase letters to denote matrices (e.g. G) and
bold lowercase letters to denote vectors (e.g. v).
For the ease of description, we define terms that are interchangeably used throughout the literature and this paper—(a) we refer to
network as a graph, (b) node is synonymous with vertex, (c) local
partition is referred to as a local cluster, (d) seed node is equivalent
to query and start vertex, (e) topological edges of the graph refers
to the network structure of the graph, (f) a rich graph is a graph
with attributes on the nodes and or edges.

3.1

Preliminaries

Graph Model. Topological network G represents the network
structure of the graph and is formally defined in Eq. (1). Attribute
network A represents the attribute structure of the graph and is
computed based on the similarity for every edge (u, v) ∈ E in G.
In order to determine the similarity between the two nodes, we
use Jaccard Similarity J (u, v). A is formally defined in Eq. (2) where
0.05 is the default attribute similarity between an edge (u, v) ∈ E in
G if J (xu , xv ) = 0. In addition, te is the similarity threshold for the
addition of edges not in G where 0 < te ≤ 1. Combined Network B
represents the combined graph of G and A and is formally defined
in Eq. (3).
Formally, we define each of the three graph models G, A and B in
Eq. (1), Eq. (2) and Eq. (3). Figure 2 presents an illustrative example.
(
1, if (u, v) ∈ E and u,v
G(u, v) =
(1)
0, otherwise

Local Partition in Rich Graphs

KDD’18, August 2018, London, United Kingdom
By definition, B can be split into its representative components,
G and A. We also note a few key properties of the parallel cut metric
below:

Figure 2: Example of the three graph models: (a) graph G is
the network structure with nodes {1, 2, 3, 4} and corresponding attribute set {x 1, x 2, x 3, x 4 } given as input. (b) Graph A is
the attribute network with the same set of edges as G with
each edge (u, v) assigned a positive similarity weight suv . (c)
Graph B is a linear combination of the each respective edge
(u, v) from G and A.

if (u, v) ∈ E, u,v and J (u, v) > 0
if (u, v) ∈ E, u,v and J (u, v) = 0
A(u, v) =

J(u,v),
if
(u, v) < E, u,v and J (u, v) > te



 0,
otherwise


(2)



1+A(u,v), if (u, v) ∈ E and (u, v) ∈ A



B(u, v) = A(u,v),
if (u, v) < E and (u, v) ∈ A


 0,
otherwise


(3)


J(u,v),




 0.05,


(1) Parallel_cut = 1 means that the vertices in S have connec¯
tions of equal weighting between S and S.
(2) Parallel_cut < 1 means that the vertices in S have only a
¯
few strong connections to S.
(3) Parallel_cut > 1 means that the vertices in S are more
strongly connected to S¯ than S.
Eq. (6) uses the cut as defined in Eq. (5) and the volume as defined
above with the modification that δ (v) is a sum of it’s components
in G and A.
parallel_cut(S)
(6)
vol(S)
We note that the parallel conductance metric has a different scale
compared to the traditional conductance metric. For example, a
conductance of 0.3 in the traditional conductance doesn’t have the
same meaning as a conductance of 0.3 in the parallel definition. We
also bound the volume of S to vol(S) < 1/2vol(B). This allows us
¯ computation to vol(S).
to reduce the min(vol(S), vol(S))
ϕ(S) =

Conductance. Conductance is a standard metric for determining how tight knit a set of vertices are in a graph [12]. The traditional
conductance metric is defined in Eq. (4), where S is the set of vertices representing the local partition. The lower the conductance
value ϕ(S), where 0 ≤ ϕ(S) ≤ 1, the more likely S represents a good
partition of the graph.
ϕ(S) =

cut(S)
¯
min(vol(S), vol(S))

(4)

Where the cut is Cut(S) = {(u, v) ∈ E|u ∈ S, v < S }, and the volume
Í
is vol(S) =
δ (v).
v ∈S

This definition of conductance will serve as the benchmark to
compare the results of our parallel conductance metric.
Parallel Conductance. We propose a parallel conductance metric
which takes into account both the attribute and topological edges
in the graph. Instead of simply adding the cut of each vertex v ∈ S,
we want to determine whether v is more similar to the vertices in
¯ The new cut and conductance metric is formally defined in
S or S.
Eq. (5) and Eq. (6), respectively. The key idea behind the parallel
conductance metric is to determine whether each vertex in S is
more similar to S or S¯ using the additional information provided
by the attribute links.
Í
parallel_cut(S) =

Õ j̸ϵ S
Í
iϵ S jϵ S

B(i, j)
B(i, j)


Í 
A(i, j) + G(i, j)

=

Õ j̸ϵ S

Í 
A(i, j) + G(i, j)
iϵ S
jϵ S

(5)

Figure 3: A toy example calculating the parallel cut and conductance with local partition S containing vertices {1, 2, 3, 4}.
Parallel cut(V1 ) = 1.05/2.1 = 0.5, parallel cut(V2 ) = 0, parallel cut(V3 ) = 1.05/2.2 = 0.477, parallel cut(V4 ) = 0, parallel
cut(Total) = 0.5 + 0.477 = 0.977. Volume(S) = 12. Parallel
conductance(S) = 0.977/12 = 0.0814.

3.2

Algorithms

We propose three algorithms in this subsection, including (1) LocalProximity (2) AttriPart and (3) LocalForecasting. First, we
introduce the LocalProximity algorithm as a key building block
for speeding-up the AttriPart and LocalForecasting algorithms
by finding a subgraph containing only the nodes and edges relevant to the given seed node. Based on LocalProximity, we further
propose the AttriPart algorithm to find a local partition around a
seed node by minimizing the parallel conductance metric. Finally,
we propose the LocalForecasting algorithm, which builds upon
AttriPart, to predict a local community’s evolution.

KDD’18, August 2018, London, United Kingdom
LocalProximity. There are two primary purposes for the LocalProximity algorithm—(i) the requisite computations for the
LocalForecasting algorithm require a pairwise similarity calculation of all nodes, which is intractable for large graphs due to
the quadratic run time. To make this computation feasible, we use
the LocalProximity algorithm to determine a small subgraph of
relevant vertices around a given seed node q. (ii) We experimentally
found that the PageRank vector utilized in the AttriPart algorithm is significantly faster to compute after running the proposed
LocalProximity algorithm.
Algorithm Details. The goal is to find a subgraph T around seed
node q, such that T contains only nodes and edges likely to be
reached in nw trials of random walk with restart. We base the importance of a vertex v ∈ V on the theory that random walks can
measure the importance of nodes and edges in a graph [5][17]. This
is done by defining node relevance proportional to the frequency
of times a random walk with restart walks on a vertex in nw trials (nodes walked on more than once in a walk will still count as
one). Instead of using a simple threshold parameter to determine
node/edge relevance as in [5], we utilize the mean and standard
deviation of the walk distribution in order for the results to remain
insensitive of nw given that nw is sufficiently large. In conjunction
with the mean and standard deviation, we introduce ts as a relevance threshold parameter to determine the size of the resulting
subgraph T . See section 3.3 for more details.
Algorithm Description. The LocalProximity algorithm takes a
graph B, a seed node q ∈ B, a teleport value α r , the number of walks
to simulate nw , a relevance threshold ts —and returns a subgraph T
containing the relevant vertices in relation to q. This algorithm can
be viewed in three major steps:
(1) Compute the walk distribution around seed node q in graph
B using random walk with restart (line 2). We omit the Random Walk algorithm due to space constraints, however, the
technique is described above.
(2) Determine the number of vertices to include in the subgraph
T based on the relevance threshold parameter ts , mean of
the walk distribution list µ(L) and the standard deviation of
the walk distribution list σ (L) (lines 4-6).
(3) Create a subgraph based on the included vertices (line 8).

Algorithm 1: Local Proximity
Input: Graph B, seed node q, teleport value α r , number of
walks to simulate nw , relevance threshold ts
Result: Subgraph T
1 subgraph_nodes = [];
2 D = RandomWalk(q, α r , nw , B);
3 L = D.values;
4 for vertex u in B do
5
if D[u] > µ(L) + σ (L) / ts then
6
subgraph_nodes.append(u);
7 end
8 T = B.subgraph(subgraph_nodes);
9 return T ;

S. Freitas et al.
AttriPart. Armed with the LocalProximity algorithm, we
further propose an algorithm AttriPart, which takes into account
the network structure and attribute information contained in graph
to find denser local partitions than can be found using the network structure alone. The foundation of this algorithm is based
on [19][1][30] with subtle modifications on lines 1, 4 and 9. These
modifications incorporate the addition of a combined graph model,
approximate PageRank computation using the LocalProximity
algorithm, and the parallel cut and conductance metric. In addition,
AttriPart doesn’t depend on reaching a target conductance in
order to return a local partition—instead it returns the best local
partition found within sweeping ns vertices of the sorted PageRank
vector.
Algorithm Description. Given a graph B, seed node q ∈ V , target conductance ϕo , rank truncation threshold ϵ, the number of
iterations to compute the rank vector tl ast , teleport value α n , rank
iteration threshold ϵt and number of nodes to sweep ns —AttriPart
will find a local partition S around q within ns iterations of sweeping. This algorithm can be viewed in five steps:
(1) Set values for ϵ and tl ast as seen in Eq. (7) and Eq. (9) respec1+loд(m)
tively. We experimentally set b =
and ϵt to 0.01.
2
For additional detail on parameters ϵ, tl ast and b see [19].
For all other parameter values see Section 4.
(2) Run LocalProximity around seed node q in order to reduce
the run time of the PageRank computations (line 1).
(3) Compute the PageRank vector using a lazy random transition with personalized restart—with preference vector s
containing all the probability on seed node q. At each iteration truncate a vertex’s rank if it’s degree normalized
PageRank score is less than ϵ (lines 2-7).
(4) Divide each vertex in the PageRank vector by its corresponding degree centrality and order the rank vector in descending
order (line 8).
(5) Sweep over the PageRank vector for the first ns vertices,
returning the best local partition S found (lines 9-10). The
sweep works by taking the re-organized rank vector and
creating a set of vertices S by iterating through each vertex
in the rank vector one at a time, each time adding the next
vertex in the rank vector to S and computing ϕ(S).
ϵ = 1/(1800(l + 2)tl ast 2b )

(7)

l = ⌈loд2 (2m/2)⌉

(8)

p
2
tl ast = (l + 1)⌈ 2 ln(c 1 (l + 2) 2m/2)⌉
(9)
ϕ
LocalForecasting. As a natural application of the AttriPart
algorithm, we introduce a method to predict how local communities
will evolve over time. This method is based on the AttriPart
algorithm with two significant modifications—(i) required use of the
LocalProximity algorithm to create a subgraph around the seed
node and (ii) the use of the ExpandedNeighborhood algorithm
to predict links between nodes in the subgraph. The idea behind
using the ExpandedNeighborhood algorithm is that nodes are
often missing many connections they will make in the future, which
in turn affects the grouping of nodes into communities. To aid in

Local Partition in Rich Graphs
Algorithm 2: AttriPart
Input: Graph B, seed node q, target conductance ϕo ,
truncation threshold ϵ, iterations tl ast , teleport value
α n , iteration threshold ϵt , vertices to sweep ns
Result: Local partition S
1 T = Local_Proximity(B, q, α r , nw , t s );
2 D i,i = δ (v i );
1
−1
3 W = (I + D T );
2
4 for t = 1 to tl ast and sum(q t ) - sum(q t −1 ) < ϵt do
5
qt = (1 − α)qt −1W + αs;
6
r t (i) = qt (i) if qt (i)/d(i) > ϵ, else 0;
7 end
8 Order i from large to small based on r t (i)/d(i);
9 Sweep Parallel_Conductance ϕ(S {i = 1..j}) while i < n s ;
10 If there is j : ϕ(S j ) < ϕ o , return S;

predicting future edge connections we use Jaccard Similarity [14] to
predict the likelihood of each vertex connecting to the others—with
edges added if the similarity between two nodes is greater than
threshold te .
Algorithm Description. Given a graph B, a seed node q ∈ V , a
target conductance ϕo , a rank truncation threshold ϵ, the number
of iterations to compute the rank vector tl ast , a teleport value α n ,
rank iteration threshold ϵt , similarity threshold te and number
of nodes to sweep ns —this algorithm will find a predicted local
partition around q within ns iterations of sweeping. As the LocalForecasting algorithm is similar to AttriPart, we highlight the
three primary steps:
(1) Determine the subgraph around a given seed node using the
LocalProximity algorithm (line 1).
(2) Determine the pairwise similarity between all nodes in the
subgraph using Jaccard Similarity, adding edges that are
above a given similarity threshold (line 2).
(3) Run the AttriPart algorithm to find the predicted local
partition around the seed node (line 3).
Algorithm 3: Local Forecasting
Input: Graph B, seed node q, target conductance ϕo ,
truncation threshold ϵ, iterations tl ast , teleport value
α n , iteration threshold ϵt , similarity threshold te ,
vertices to sweep ns
Result: Predicted local partition S
1 T = Local_Proximity(B, q);
2 T = Expanded_Neighborhood(T , t e ) ;
3 S = AttriPart(T , q, ϕ o , ϵ, tl ast , α n , ϵt , n s ) ;
4 return S ;

KDD’18, August 2018, London, United Kingdom
Algorithm 4: Expanded Neighborhood
Input: Subgraph T , edge addition threshold te
Result: Subgraph T with predicted edges
1 for u in T do
2
for v in T and v not u do
3
u_attr = T [u]; v_attr = T [v];
4
similarity_score = JaccardSimilarity(u_attr, v_attr);
5
if similarity_score > te and not T [u][v] then
6
T [u][v] = similarity_score;
7
end
8 end
9 return T ;

few links while a handful encompasses the majority. In Figure 4,
we found that after running nw trials of random walk with restart,
a scale-free like distribution formed—with a large majority of the
nodes containing a small number of ‘hits’, while a few nodes constituted the bulk.
As the number of random walks nw is increased, the scale-free
like distribution is maintained since each node
is proportionally walked
with the same distribution. We therefore need
only some minimum value
for nw , which we set
to 10,000. We use this
skewed scale-free like
Figure 4: Random walk w/
distribution in combinarestart—distribution of node
tion with Eq. (10) below
walk counts. nw = 10,000, α r =
to ensure the extraction
0.15; dataset: wikipedia, start
of relevant nodes in relavertex: ‘ewok’, y-axis: right;
tion to a query vertex.
dataset: Aminer, start vertex:
Mathematically we de364298, y-axis: left. We omit
fine node relevance based
nodes walked zero times in the
on Eq. (10), where D is a
graph, however, they’re used in
dictionary containing the
calculating µ(L), σ (L).
walk count of each vertex
and D(v) represents the
number of times vertex v is walked in nw trials of the random walk
with restart. L is a list of each node’s walk count in the graph, µ(L)
is the average number of times all of the nodes in the graph are
walked and σ (L) is the standard deviation of the number of times
all of the nodes in the graph are walked. In section 4 we discuss
values of ts that have been shown to be empirically effective.
D(v) > µ(L) + σ (L)/ts

3.3

Analysis

Effectiveness. LocalProximity (Algorithm 1). The objective is
to ensure that all relevant nodes in proximity to seed node q are
included. We use the fact that many real-world graphs follow a
scale-free distribution [3] [6], with many nodes containing only a

(10)

After determining the relevant nodes we create a subgraph T
from a portion of the long-tail curve as defined by threshold parameter ts in conjunction with µ(L) and σ (L). We say that subgraph
T contains p ≪ n nodes—with p increasing nearly independently
of the graph size (depending on threshold ts ). As seen in Figure 4

KDD’18, August 2018, London, United Kingdom
the number of nodes with r walks converges independent of graph
size.
Efficiency. All algorithms use the same data structure for storing the graph information. If a compressed sparse row (CSR) format
is used, the space complexity is O(2m + n + 1). Alternatively, we
note that with minor modification to the algorithms above we can
use an adjacency list format with O(n + m) space.
Lemma 3.1 (Time Complexity). LocalProximity has a time complexity of O(n + mp + nw ) while AttriPart has a time complexity of
O(p 2 + pmp + n + nw ) and LocalForecasting a time complexity of
O(p 2 + pme + n + nw ).
Proof. LocalProximity: There are three major components
to this algorithm: (1) nw random walks with walk length l for a
time complexity of O(nw ) (line 2). (2) Linear iteration through the
number of nodes taking O(n) (lines 4-7). (3) Subgraph T creation
based on the number of included vertices p with node set Vt —
requiring iteration through every edge of node v ∈ Vt for mp total
edges. Iterating through every edge is linear in the number of edges
for a time complexity of O(mp ) (line 8). This leads to a total time
complexity of O(n + mp + nw )
AttriPart: There are six major steps to this algorithm: (1) calling
LocalProximity which returns a subgraph T containing p nodes
and mp edges for a time complexity of O(n + mp + nw ) (line 1).
(2) Creating a diagonal degree matrix by iterating through each
node in T with time complexity O(p) (line 2). (3) Creating the lazy
random walk transition matrix W , which requires O(mp ) from
multiplying the corresponding matrix entries (line 3). (4) In lines
4-7 we iterate for tl ast iterations, with each iteration (i) updating
the rank vector by multiplying the corresponding edges in the
transition matrix W , with the rank vector q for a time complexity
of O(mp ) and (ii) truncating every vertex with rank qt (i)/d(i) ≤ ϵ
for a time complexity linear in the number of nodes in the rank
vector O(p). (5) Sort the rank vector which will be upper bounded
by O(ploдp) (line 8). (6) Compute the parallel conductance, which
takes O(p 2 + pmp ) time (lines 9-10). Combining each step leads to
a total time complexity of O(p 2 + pmp + n + nw ).
LocalForecasting: This algorithm has three major steps: (1)
run the LocalProximity algorithm, which has a time complexity
of O(n + mp + nw ). (2) Perform the ExpandedNeighborhood algorithm, which densifies T by adding predicted edges for a total of me
edges in T . This algorithm has a time complexity of O(p 2 ) due to
the nested for loops. (3) Run the AttriPart algorithm, which has
a time complexity of O(p 2 + pme + n + nw ) with the modification
of mp to me for the additional edges. This leads to an overall time
complexity of O(p 2 + pme + n + nw ).
□
While AttriPart and LocalForecasting both scale quadratically with respect to p, we note that in practice these algorithms
are very fast since p ≪ n and p scales nearly independent of graph
size as shown in section 3.3.

4

EXPERIMENTS

In this section, we demonstrate the effectiveness and efficiency of
the proposed algorithms on three real-world network datasets of
varying scale.

S. Freitas et al.

4.1

Experiment setup

Datasets. We evaluate the performance of the proposed algorithms
on three datasets—(1) the Aminer co-authorship network [27],
(2) a Musician network mined from DBpedia and (3) a subset of
Wikipedia entries in DBpedia containing both abstracts and links.
All three networks are undirected with detailed information on
each below:
• Aminer. Nodes represents an author, with each author containing a set of topic keywords, and an edge representing
a co-authorship. To form the attribute network, we compute attribute edges based on the similarity between two
authors for every network edge, using Jaccard Similarity on
the corresponding authors’s topic set.
• Musician. Nodes represent a Musician, with each Musician
containing a set of music genres, and an edge representing
two Musicians who have played in the same band. To form
the attribute network, we compute attribute edges based
on the similarity between two Musicians for every network
edge, using Jaccard Similarity on the corresponding artist’s
music genre set.
• Wikipedia. Nodes represent an entity, place or concept
from Wikipedia which we will jointly refer to as an item.
Each item contains a set of defining key words; with edges
representing a link between the two items. The dataset originates from DBpedia as a directed graph with links between
Wikipedia entries. We modify the graph to be undirected for
use with our algorithms—which we believe to be a reasonable
as each edge denotes a relationship between two items. In
addition, this dataset uses only a portion of the Wikipedia entries containing both abstracts and links to other Wikipedia
pages found in DBpedia. To form the attribute network, we
compute attribute edges based on the similarity between
two items for every network edge using Jaccard Similarity
on the corresponding item’s key word set.
Category

Network

Nodes

Edges

Aminer
Musician
Wikipedia

Co-Author
Co-Musician
Link

1,560,640
6,006
237,588

4,258,946
8,690
1,130,846

Table 2: Network Statistics

Metrics. (1) To benchmark the LocalProximity algorithm’s
effectiveness and efficiency, we compare (i) the difference between
local partition created with and without the LocalProximity algorithm on AttriPartand (ii) the run time and difference between
the top 20 PageRank vector entries with and without the LocalProximity algorithm. (2) To benchmark the AttriPart algorithm’s
effectiveness and efficiency we compare the triangle count, node
count, local partition density and run time to PageRank-Nibble.
Normally, PageRank-Nibble does not return a local partition if the
target conductance is not met, however, we modify it to return
the best local partition found—even if the target conductance is
not met. This modification allows for more comparable results to
AttriPart. (3) To provide a baseline for the LocalForecasting

Local Partition in Rich Graphs

KDD’18, August 2018, London, United Kingdom

algorithm’s effectiveness, we compare the local partition results to
AttriPart on two graph missing 15% of their edges.
Repeatability. All data and source code used in this research
will be made publicly available. The Aminer co-authorship network can be found on the Aminer website 2 ; the Musician and
Wikipedia datasets used in the experiments will be released on the
author’s website. All algorithms and experiments were conducted
in a Windows environment using Python.

4.2

Effectiveness

LocalProximity. In Figure 5 parts (a)-(c), we can see that the proposed LocalProximity algorithm significantly reduces the computational run time, while maintaining high levels of accuracy across
both metrics. Parts (a)-(b) demonstrate to what extent the accuracy
of the results are dependent upon the parameter values. In particular, a low value of α r (random walk alpha) and a high value of ts
(relevance threshold) are critical to providing high accuracy results.
In Figure 5 part (a), we measure accuracy as the number of
vertices that differ between the local partitions w/ and w/o the
LocalProximity algorithm on AttriPart. A small partition difference indicates that the LocalProximity algorithm finds a relevant
subgraph around the given seed node and that the full graph is
unnecessary for accurate results. In part (b), we define the accuracy
of the results to be the difference between the set of top 20 entries
in the PageRank vectors for the full graph and subgraph using the
LocalProximity algorithm. Overall, the results from part (b) correlate well to (a)—showing that for low values of α r (random walk
alpha) and high values of ts (relevance threshold), their is negligible
difference between the results computed on the full graph and the
subgraph found using the LocalProximity algorithm.
AttriPart. In Figure 6, we see that AttriPart finds significantly denser local partitions than PageRank-Nibble—with local
partition densities approximately 1.6×, 1.3× and 1.1× higher in AttriPart than PageRank-Nibble in the Aminer, Wikipedia and Mu2m where
sician datasets respectively. Density is measured as n(n−1)
m is the number of edges and n is the number of nodes.
In Figure 6, we observe that the triangle count of the AttriPart algorithm is lower than PageRank-Nibble in the Musician and
Aminer datasets. We attribute this to the fact that AttriPart is
finding smaller partitions (as measured by node count) and, therefore, there are less possible triangles. We also note that each triangle
is counted three times, once for each node in the triangle. While no
sweeps across algorithm parameters were performed, we believe
that the gathered results provide an effective baseline for parameter
selection.
LocalForecasting. In order to measure the effectiveness of
the LocalForecasting algorithm we setup the following experiment with three local partition calculations: (1) calculate the local
partition using AttriPart, (2) calculate the local partition using AttriPart with 15% of the edges randomly removed from the graph
and (3) calculate the local partition using the LocalForecasting
algorithm with 15% of the edges randomly removed from the graph.
We treat (1) as the baseline local community and want to test if
(3) finds better local partitions than (2). The idea behind randomly
removing 15% of the edges in the graph is to simulate the evolution
2 https://Aminer.org/data

(a) Y-axis represents the difference in vertices between the local partition calculated w/ and w/o the LocalProximity algorithm.

(b) Y-axis represents the # of vertices differing between the top 20
rank vector entries w/ and w/o the LocalProximity algorithm.

(c) Y-axis represents the difference in run time between the PageRank calculation w/ and w/o the LocalProximity algorithm.

Figure 5: Each data point averages 10 randomly sampled vertices in both the Aminer and Musician datasets. Default parameters (unless sweeped across): α n = 0.2, α r = 0.15, ϕo = 0.2,
ts = 2, nw = 10,000, ns = 200. Parameter ranges: α r , α n and ϕo
[0.1-0.7] in 0.1 intervals; ts [1-5] in 0.5 intervals.

of the graph over time and test if the LocalForecasting algorithm
can predict better local communities in the future. Ideally, we would
have ground-truth local community data for a rich graph with time
series snapshots, however, in its absence we use the above method.
In Figure 7, each data point is generated in three steps—(i) taking the difference between the set of vertices and edges in local
partitions (1) and (3), (ii) taking the difference between the set of
vertices and edges in local partitions (1) and (2) and (iii) by taking
the difference between (ii) and (i). Step (i) tells us how far off the
LocalForecasting algorithm is from the baseline, step (ii) tells
us how far off the local partition would be from the baseline if no
prediction techniques were used and step (iii) tells us the difference
between the local partitions with and without the LocalForecasting algorithm (which is what we see graphed in Figure 7).

KDD’18, August 2018, London, United Kingdom

(a) Scalability: Each data point represents the Aminer dataset in
1/10th intervals, with each point averaged over 3 randomly sampled
vertices. Parameters: α n = 0.2, α r = 0.15, ϕo = 0.2, t s = 2, nw = 10,000,
n s = 200.

S. Freitas et al.

Figure 7: Each data point averages 20 randomly sampled vertices in the Aminer and Musician datasets. Default parameters (unless sweeped across): α n = 0.2, α r = 0.15, ϕo = 0.2, ts =
5, te = 0.7, nw = 10,000, ns = 200. Parameter ranges: te [0.1-0.9]
in 0.1 intervals, ϕo [0.1-0.6] in 0.1 intervals.

LocalForecasting. This algorithm has an expected run time
nearly identical to AttriPart, we therefore refer the reader to
Figure 6 for run time results.

5
(b)

Figure 6: Effectiveness: results are averaged over 20 and 100
randomly sampled vertices in the Aminer/Wikipedia and
Musician datasets, respectively. Parameters: α n = 0.2, α r =
0.15, ϕo = 0.05, ts = 2, nw = 10,000, ns = 200.

In Figure 7, we see that the local partition prediction accuracy, for
both the edges and vertices, is above the baseline calculations in the
Aminer dataset for a majority of edge similarity threshold values
(te ). The best results were obtained when te is 0.6, with an average
of 1.4 vertices and 2.75 edges predicted over the baseline using
the LocalForecasting algorithm. This number, while relatively
small, is an average of 20 randomly sampled vertices—with one
result reaching up to 14 vertices and 26 edges over baseline. In
addition, we can see that the Musician dataset does not perform
as well as the Aminer dataset, with most of the prediction results
performing worse than the baseline (as indicated by the negative
difference). We believe that this result on the Musician dataset is
due to the different nature of each dataset’s network structure—
with the Musician dataset being significantly more sparse (no giant
connected component) than the Aminer dataset.

4.3

Efficiency

For both the proposed and baseline algorithms, the efficiency results represent only the time taken to run the algorithm (e.g. not
including loading data into memory). LocalProximity. Across a
majority of the parameters the run time for the full graph PageRank computation is approximately 450 seconds longer compared
to computing the PageRank vector based on the LocalProximity
sugraph. AttriPart. In Figure 6, we see that the AttriPart algorithm finds local partitions 43× faster than PageRank-Nibble.

RELATED WORK

We provide a high level review of both local and global community
detection methods, with a focus on the research that pertains to
the algorithms we propose in this paper.
A - Local Community Detection. Given an undirected graph,
start vertex and a target conductance—the goal of Nibble is to find
a subset of vertices that has conductance less than the target conductance [19]. This algorithm has strong theoretical properties
with a run time of O(2b (loд6m)/ϕ 4 ), where b is a user defined constant, ϕ is the target conductance and m is the number of edges.
PageRank-Nibble builds on the work of Nibble by introducing the
use of personalized PageRank [9, 22], in addition to an algorithm
for the computation of approximate PageRank vectors [1]. Since
PageRank-Nibble and Nibble run on undirected graphs, they use
truncated random walks in order to prevent the stationary distribution from becoming proportional to the degree centrality of each
node [8]. There are also many alternative techniques for local community detection. To name a few, the paper by Bagrow and Bollt [2]
introduces a method of local community identification that utilizes
an l-shell spreading outward from a start vertex. However, their
algorithm requires knowledge of the entire graph and is therefore
not truly local. The research by J. Chen et. al. [4] proposes a method
for local community identification in social networks that avoids
the use of hard to obtain parameters and improves the accuracy of
identified communities by introducing a new metric. In addition,
the work by [29] and [25] introduces two methods of local community identification that take into account high-order network
structure information. In [29], the authors provide mathematical
guarantees of the optimality and scalability of their algorithms, in
addition to the generalization of it to various network types (e.g.
signed and multi-partite networks).
B - Global Community Detection. The basic idea behind the
Walktrap algorithm is that random walks on a graph tend to get
"trapped" in densely connected parts that correspond to communities [18]. Utilizing the properties of random walks on graphs, they
define a measurement of structural similarity between vertices and

Local Partition in Rich Graphs
between communities, creating a distance metric. The algorithm
itself has an upper bound of O(mn2 ). Another popular choice for
global community detection is spectral analysis. In the paper by M.
Newman [15] it is shown that the problems of community detection
by modularity maximization, community detection by statistical
inference and normalized-cut graph partitioning when tackled using spectral methods, are in fact, the same problem. The work by S.
White et. al. in [24] attempts to find communities in graphs using
spectral clustering. They achieve this by using an objective function for graph clustering [16] and reformulating it as a spectral
relaxation problem, for which they propose two algorithms to solve
it. A systematic introduction to spectral clustering techniques can
be found in [23]. There also exists many alternative techniques
for global community detection. Among others, two interesting
techniques relevant to this work are [11] [20]. In [11], the authors
propose a community detection algorithm that uses the information
in both the network structure and the node attributes, while in [20]
the authors use network feature extraction to predict the evolution
of communities. A detailed review of various community detection
algorithms can be found in [28].

6

CONCLUSION

This paper proposes new algorithms for attributed graphs, with
the goal of (i) computing denser local graph partitions and (ii) predicting the evolution of local communities. We believe that the
proposed algorithms will be of particular interest to data mining
researchers given the computational speed-up and enhanced dense
local partition identification. The proposed local partitioning algorithm AttriPart has already deployed to the web platform
PathFinder (www.path-finder.io) [7] and allow users to interactively explore all three datasets presented in the paper. In addition,
the source code and datasets will be made publicly available by the
conference date.

REFERENCES
[1] R. Andersen, F. Chung, and K. Lang. 2006. Local Graph Partitioning using PageRank Vectors. In 2006 47th Annual IEEE Symposium on Foundations of Computer
Science (FOCS’06). 475–486. https://doi.org/10.1109/FOCS.2006.44
[2] James P. Bagrow and Erik M. Bollt. 2005. Local method for detecting communities.
Phys. Rev. E 72 (Oct 2005), 046108. Issue 4. https://doi.org/10.1103/PhysRevE.72.
046108
[3] Albert-László Barabási and Réka Albert. 1999. Emergence of Scaling in Random
Networks. Science 286, 5439 (1999), 509–512. https://doi.org/10.1126/science.286.
5439.509 arXiv:http://science.sciencemag.org/content/286/5439/509.full.pdf
[4] J. Chen, O. ZaÃŕane, and R. Goebel. 2009. Local Community Identification in
Social Networks. In 2009 International Conference on Advances in Social Network
Analysis and Mining. 237–242. https://doi.org/10.1109/ASONAM.2009.14
[5] Pierre Dupont, J Callut, G Dooms, J N. Monette, and Yves Deville. 2017. Relevant
subgraph extraction from random walks in a graph. (12 2017).
[6] Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. 1999. On Power-law
Relationships of the Internet Topology. In Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication
(SIGCOMM ’99). ACM, New York, NY, USA, 251–262. https://doi.org/10.1145/
316188.316229
[7] Scott Freitas, Hanghang Tong, Nan Cao, and Yinglong Xia. 2017. Rapid Analysis
of Network Connectivity. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management (CIKM ’17). ACM, New York, NY, USA,
2463–2466. https://doi.org/10.1145/3132847.3133170
[8] Vince Grolmusz. 2015. A Note on the PageRank of Undirected Graphs. Inf. Process.
Lett. 115, 6 (June 2015), 633–634. https://doi.org/10.1016/j.ipl.2015.02.015
[9] T. H. Haveliwala. 2003. Topic-sensitive PageRank: a context-sensitive ranking
algorithm for Web search. IEEE Transactions on Knowledge and Data Engineering
15, 4 (July 2003), 784–796. https://doi.org/10.1109/TKDE.2003.1208999

KDD’18, August 2018, London, United Kingdom
[10] Chin-Chi Hsu, Yi-An Lai, Wen-Hao Chen, Ming-Han Feng, and Shou-De Lin.
2017. Unsupervised Ranking Using Graph Structures and Node Attributes. In
Proceedings of the Tenth ACM International Conference on Web Search and Data
Mining (WSDM ’17). ACM, New York, NY, USA, 771–779. https://doi.org/10.1145/
3018661.3018668
[11] Jure Leskovec Jaewon yang, Julian McAuley. 2013. Community Detection in
Networks with Node Attributes. ICDM (2013).
[12] Ravi Kannan, Santosh Vempala, and Adrian Vetta. 2004. On Clusterings: Good,
Bad and Spectral. J. ACM 51, 3 (May 2004), 497–515. https://doi.org/10.1145/
990308.990313
[13] Songsong Liu Lazaros G. Papageorgiou Sophia Tsoka Laura Bennett, Aristotelis Kittas. 2014. Community Structure Detection for Overlapping Modules
through Mathematical Programming in Protein Interaction Networks. PLOS ONE
(2014). https://doi.org/10.1371/journal.pone.0112821
[14] David Liben-Nowell and Jon Kleinberg. 2007. The Link-prediction Problem
for Social Networks. J. Am. Soc. Inf. Sci. Technol. 58, 7 (May 2007), 1019–1031.
https://doi.org/10.1002/asi.v58:7
[15] Mark E. J. Newman. 2013. Spectral methods for network community detection
and graph partitioning. CoRR abs/1307.7729 (2013).
[16] M. E. J. Newman and M. Girvan. 2004. Finding and evaluating community
structure in networks. Physical Review E 69, 026113 (2004).
[17] M.E. J. Newman. 2005. A measure of betweenness centrality based on random
walks. Social Networks 27, 1 (2005), 39 – 54. https://doi.org/10.1016/j.socnet.2004.
11.009
[18] Pascal Pons and Matthieu Latapy. 2005. Computing Communities in Large Networks Using Random Walks. In Proceedings of the 20th International Conference on
Computer and Information Sciences (ISCIS’05). Springer-Verlag, Berlin, Heidelberg,
284–293. https://doi.org/10.1007/11569596_31
[19] Daniel A. Spielman and Shang-Hua Teng. 2013. A Local Clustering Algorithm
for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning. SIAM J. Comput. 42, 1 (2013), 1–26. https://doi.org/10.1137/080744888
arXiv:https://doi.org/10.1137/080744888
[20] M. Takaffoli, R. Rabbany, and O. R. ZaÃŕane. 2014. Community evolution prediction in dynamic social networks. In 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2014). 9–16.
https://doi.org/10.1109/ASONAM.2014.6921553
[21] Chayant Tantipathananandh, Tanya Berger-Wolf, and David Kempe. 2007. A
Framework for Community Identification in Dynamic Social Networks. In
Proceedings of the 13th ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining (KDD ’07). ACM, New York, NY, USA, 717–726.
https://doi.org/10.1145/1281192.1281269
[22] Hanghang Tong, Jingrui He, Mingjing Li, Wei-Ying Ma, Hong-Jiang Zhang, and
Changshui Zhang. 2006. Manifold-Ranking-Based Keyword Propagation for
Image Retrieval. EURASIP Journal on Applied Signal Processing 2006 (2006),
Article ID 79412, 10 pages. doi:10.1155/ASP/2006/79412.
[23] Ulrike von Luxburg. 2007. A tutorial on spectral clustering. Statistics and Computing 17, 4 (01 Dec 2007), 395–416. https://doi.org/10.1007/s11222-007-9033-z
[24] Scott White and Padhraic Smyth. [n. d.]. A Spectral Clustering Approach To Finding
Communities in Graphs. 274–285. https://doi.org/10.1137/1.9781611972757.25
arXiv:http://epubs.siam.org/doi/pdf/10.1137/1.9781611972757.25
[25] Hao Yin, Austin R. Benson, Jure Leskovec, and David F. Gleich. 2017. Local HigherOrder Graph Clustering. In Proceedings of the 23rd ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining (KDD ’17). ACM, New York,
NY, USA, 555–564. https://doi.org/10.1145/3097983.3098069
[26] Sune Lehmann Yong-Yeol Ahn, James P. Bagrow. 2010. Link communities reveal
multiscale complexity in networks. Nature (August 2010), 761–764. https://doi.
org/doi:10.1038/nature09182
[27] Jing Zhang, Jie Tang, Cong Ma, Hanghang Tong, Yu Jing, Juanzi Li, Walter Luyten,
and Marie-Francine Moens. 2017. Fast and Flexible Top-k Similarity Search on
Large Networks. ACM Trans. Inf. Syst. 36, 2, Article 13 (Aug. 2017), 30 pages.
https://doi.org/10.1145/3086695
[28] Claudio J. Tessone Zhao Yang, RenÃľ Algesheimer. 2016. A Comparative Analysis
of Community Detection Algorithms on Artificial Networks. Scientific Reports
(2016). https://doi.org/doi:10.1038/srep30750
[29] Dawei Zhou, Si Zhang, Mehmet Yigit Yildirim, Scott Alcorn, Hanghang Tong,
Hasan Davulcu, and Jingrui He. 2017. A Local Algorithm for Structure-Preserving
Graph Cut. In Proceedings of the 23rd ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining (KDD ’17). ACM, New York, NY, USA,
655–664. https://doi.org/10.1145/3097983.3098015
[30] Leonid Zhukov. [n. d.].
Structural Analysis and Visualization of Networks. ([n. d.]). https://www.youtube.com/watch?v=jIS5pZ8doH8&list=
PLriUvS7IljvkBLqU4nPOZtAkp7rgpxjg1&index=11

