Focused Clustering and Outlier Detectionin Large Attributed Graphs
Bryan Perozzi  , Leman Akoglu Stony Brook University
Department of Computer Science

Patricia Iglesias Sánchez ◦ , Emmanuel Müller ◦ •◦{bperozzi, leman}@cs.stonybrook.edu•
Karlsruhe Institute of Technology, University of Antwerp
Department of Computer Science{patricia.iglesias, emmanuel.mueller}@kit.edu

ABSTRACT
Graph clustering and graph outlier detection have been studied extensively on plain graphs, with various applications.
Recently, algorithms have been extended to graphs with attributes as often observed in the real-world. However, all ofthese techniques fail to incorporate the user preference into
graph mining, and thus, lack the ability to steer algorithms
to more interesting parts of the attributed graph.
In this work, we overcome this limitation and introduce anovel user-oriented approach for mining attributed graphs.
The key aspect of our approach is to infer user preference by
the so-called focus attributes through a set of user-provided
exemplar nodes. In this new problem setting, clusters andoutliers are then simultaneously mined according to thisuser preference. Specifically, our FocusCO algorithm identifies the focus, extracts focused clusters and detects outliers.
Moreover, FocusCO scales well with graph size, since weperform a local clustering of interest to the user rather thanglobal partitioning of the entire graph. We show the effectiveness and scalability of our method on synthetic and realworld graphs, as compared to both existing graph clusteringand outlier detection approaches.

Categories and Subject Descriptors
H.2.8 [Database Applications]: Data mining; I.5.3 [Pattern
Recognition]: Clustering

Keywords
focused graph mining; infer user preference; attributed graphs;
clustering; outlier mining; distance metric learning

1.

INTRODUCTION

Many real-world graphs have attributes associated with
the nodes, in addition to their connectivity information.
For example, social networks contain both the friendshiprelations as well as user attributes such as interests and demographics. A protein-protein interaction network may not
Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others thanACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from permissions@acm.org.
KDD’14, August 24–27, 2014, New York, NY, USA.
Copyright 2014 ACM 978-1-4503-2956-9/14/08 ...$15.00.
http://dx.doi.org/10.1145/2623330.2623682

Figure 1: Example graph with two focused clusters
and one focused outlier.
only have the interaction relations but the gene expressions
associated with the proteins. Both types of information canbe described by a graph in which nodes represent the objects,
edges represent the relations between them, and feature vectors associated with the nodes represent the attributes. Suchgraph data is often referred to as an attributed graph.
For attributed graphs, we see major challenges that remain unsolved by traditional graph mining techniques [4, 10,
19, 24, 31], which consider plain graphs (without attributes).
Recent methods have been proposed for attributed graphs,
however, they either use all the given attributes [2, 14, 20,34] or they perform an unsupervised feature selection [16, 18,
22, 26]. In contrast to all of these graph mining paradigms(cf. Table 1), we consider a user-oriented setting where theusers can control the relevance of attributes and as a consequence, the graph mining results.
In particular, we consider cluster and outlier detection
based on user preference. This focused clustering is of particular interest in attributed graphs, where users might not
be concerned with all but a few available attributes. As different attributes induce different clusterings of the graph,the user should be able to steer the clustering accordingly.
As such, the user controls the clustering by providing a set of
exemplar nodes (perceived similar by the user) from which
we infer attribute weights of relevance that capture the userperceived similarity. The essence of user preference is captured by those attributes with large weights. We call thesethe focus attributes, which form the basis of our approachfor discovering focused clusters and outliers.
To elaborate on this new terminology, we give a toy example in Figure 1. The graph represents the friendship relations
and the node attributes denote degree, location, mothertongue, and work. There are two focused clusters: On theProperty

Table 1: Comparison of related work.
rs
rs
ste
phs
ste
ace
n
g
clu
gra
u
p
n
l
i
s
tio
d
c
r
d
g
rre
tec
sub
ste ibute
n
y
e
i
e
u
f
e
l
p
d
c
r
p
re
ilit
ut
r
att
r-p
rib
lab
tlie
erla
aph
e
t
a
r
n
v
u
s
t
c
G
O
A
U
O
O
S
METIS [19], Spectral [24], Co-clustering [10]
X
X
X
X
X
Autopart, Cross-associations [7]PageRank-Nibble [3], [30], BigClam [33]X
X
X
Spectral Relational [20], SA-Cluster [34]
X
X
X
X
X
X
CoPaM [22], Gamer [16]PICS [2]
X
X
X
X
X
X
CODA [14]GOutRank [23], ConSub [18]X
X
X
X
FocusCO [this paper]
X
X
X
X
X
X
X
left, people know each other due to their degrees and locations. On the right, a similarity in work induces the second
cluster. As such, different user interest in subsets of theattributes may induce different clusters. In case a user is interested in degree and location, focused clustering should
only find the left cluster and not the right one. Analogously,
the example outlier is deviating with a college degree among
all others having PhDs, where degree is a focus attribute.
While our example is on a toy graph, our problem setting has several practical applications in the real-world. For
instance, a marketing manager interested in selling cosmetics could aim to find communities in a large social networkwith its members being of a certain age, gender, and incomelevel. S/he could then offer deals to a few members fromeach community, and expect the news to propagate by theword-of-mouth. A scientist could aim to identify clusters
of sky-objects that are all in close-distance to one another(assuming a graph is constructed among sky-objects by distance in space) and share certain characteristics of interest(e.g., helium level, temperature, light, etc.).
Such user-preferred clusters are likely a handful in thegraph, and thus an algorithm should be able to (i) effectively
identify user preference, (ii) efficiently “chop out” relevant
clusters locally without necessarily partitioning the wholegraph, and additionally (iii) spot outliers if any. In thispaper, we offer the following contributions:• Focused Graph Mining: We propose a new usercentric problem setting that exploits the user interest
for focused mining in attributed graphs.
• Steered Search by User Preference: We infer user
preference and steer the graph clustering and outlier
detection accordingly.
• Scaling to Large Graphs: Our proposed method
has near-linear time complexity, and with appropriate
initialization can run in time sub-linear w.r.t. the sizeof the input graph.
In our evaluation we demonstrate the effectiveness andscalability of our method on synthetic and real-world graphs,
compared to existing graph clustering and outlier detection
methods. Our experiments show that existing approaches
are not suitable for the new focused graph mining setting.

2.

RELATED WORK

We show the highlights of related work in Table 1. The
two key differences of our work are summarized as follows:(1) we introduce a new user-oriented problem setting for
attributed graphs, in which we aim to find focused clusters
and outliers based on user preference, and (2) we propose
an algorithm that simultaneously extracts relevant clusters
and outliers from large graphs. In the following, we discuss
related work in three areas; traditional plain graph mining,
attributed graph mining, and semi-supervised data mining.

Graph mining on plain graphs.
Graph partitioning has been well studied in the literature.
Widely used methods include METIS [19] and spectral clustering [11, 24], which aim to find a k-way partitioning of
the graph. Different from partitioning, community detection methods [12] cluster the graph into variable size communities. Autopart, cross-associations [7], and informationtheoretic co-clustering [10] are parameter-free examples tograph clustering methods. Several methods [3, 30, 33] also
allow clusters to overlap as observed in real-world social andcommunication networks. Works that aim to spot structural
outliers in plain graphs include [1, 28]. However, all of thesemethods are limited to plain graphs (without attributes).

Graph mining on attributed graphs.
Compared to the wide range of work on plain graph mining, there has been much less work on attributed graphs.
The representative methods [2, 14, 17, 20, 27, 34] aim to partition the given graph into structurally dense and attributewise homogeneous clusters, detect deviations from frequent
subgraphs [25], or search for community outliers in attributedgraphs [14]. These methods, however, enforce attribute homogeneity in all attributes. Recently some methods loosen
this constraint by unsupervised feature selection [26], subspace clustering [16, 22] and subspace outlier detection [18,23] and extract cohesive subgraphs with homogeneity in a
subset of attributes. However, all of these methods either
do not perform a selection of attributes or do not allow foruser preference to steer the algorithm.

Semi-supervised methods.
A broad variety of methods for semi-supervised clustering
consider user-given constraints like ‘must-link’ and ‘cannotlink’ referred to as constraint-based clustering [5]. Therealso exist methods for semi-supervised outlier mining [13].
However, these methods are based on vector data and further, not applicable to graphs with attributes.
Methods on seeded community mining [3, 8, 15, 30] findcommunities around (user-given) seed nodes. However, thosemethods find structural communities on plain graphs andneither apply to attributed graphs, nor enable user preference on attributes. Moreover, they do not provide outlier
detection. In contrast, we use user-given exemplar nodes
to automatically infer user preference on attributes. To thebest of our knowledge this problem setting is new and we
propose the first focused graph mining approach for simultaneous clustering and outlier detection in attributed graphs.

3.

METHOD FocusCO

In this section we first introduce the notation and pose thefocused clustering and outlier detection problem formally.
Next, we discuss the main components of our approach andwalk through the details of our algorithm. Lastly, we analyze
the computational complexity of FocusCO.

3.1

Problem Formulation

In this paper we introduce the novel problem of focusedclustering and outlier detection in attributed graphs, defined
as follows: Given a large attributed graph G(V, E, F ) with
|V | = n nodes and |E| = m edges, where each node is associated with |F | = d attributes (features), extract from G
only the (type of) clusters pertaining to a user u’s interest(rather than partitioning the whole graph). To do so, theuser provides a small set Cex of exemplar nodes that s/heconsiders to be similar to the type of nodes the clusters of
his/her interest should contain. Assuming that the nodes
in a cluster “unite” or “knit up” around a few defining attributes, we then aim to infer the implicit weights βu (i.e.,
relevance) of attributes that “define” the nodes in Cex , i.e.,
the weights of attributes that make them as similar as possible. Thus, βu is expected to be a sparse vector with large
weights for only a few attributes (e.g., degree and locationin Figure 1), which we call the focus attributes.
Having inferred the attribute weights βu from user u, ourfirst goal is to extract focused clusters C from G that are(1) structurally dense and well separated from the rest of
the graph, as well as (2) consistent on the focus attributeswith large weights. The focused clusters can be overlapping,
sharing several of their nodes, as observed in real-world social and communication networks. Moreover, the set C isa subset of all the clusters in G since different sets of clusters are expected to unite around different attributes andwe aim to extract only those that are specifically similar to
the type of clusters user u is interested in. Besides focusedclustering, our second goal is to also perform outlier detection. Outliers O are those nodes that structurally belong
to a focused cluster (i.e., have many cluster neighbors), butdeviate from its members in some focus attributes. In summary, the focused clustering and outlier detection problem
in attributed graphs is given as follows:
Given a large graph G(V, E, F ) with node attributes, anda set of exemplar nodes Cex of user u’s interest;
Infer attribute weights βu of relevance/importance,
Extract focused clusters C that are (1) dense in graphstructure, and (2) coherent in heavy focus attributes,
Detect focused outliers O, i.e. nodes that deviate fromtheir cluster members in some focus attributes.

3.2

Approach and Algorithm Details

Next we present the details of the three main components
of FocusCO: (1) inferring attribute weights, (2) extracting
focused clusters, and (3) outlier detection.

3.2.1

Inferring Attribute RelevanceOur focused clustering setting is a user-oriented one, where
each user is interested in extracting certain kind of clusters
from a given graph. The user steers the clustering by providing a small set of exemplar nodes that are similar to one
another as well as similar to the type of nodes the clusters of his/her interest should contain. Our first goal thenis to identify the relevance weights of node attributes thatmake the exemplar nodes similar to each other. This kindof weighted similarity is often captured by the (inverse) Mahalanobis distance: the distance between two nodes withfeature vectors fi and fj is (fi − fj )T A(fi − fj ). Setting
A as the identity matrix yields Euclidean distance, otherwise the features/dimensions are weighted accordingly.
Given the exemplar nodes, how can we learn an A suchthat they end up having small distance to each other? Thisis known as the distance metric learning problem [29]. We
adopt the optimization objective by [32]:Xmin(fi − fj )T A(fi − fj )(1)A(i,j)∈PS
− γ logXp(fi − fj )T A(fi − fj )(i,j)∈PD

which is convex and enables efficient, local-minima-free algorithms to solve it, especially for a diagonal solution.
We give the details of inferring attribute weights in Procedure P1. PS and PD are two sets of similar and dissimilarpairs of nodes, respectively (P1 Line 1). In our setting, allpairs of exemplar nodes constitute PS (P1 Line 2). We create PD by randomly drawing pairs of nodes that do notbelong to the exemplar set (P1 Lines 3-7).
We remark that in creating PD , we may also obtain samples similar to those in PS since these draws are random.
To alleviate the affect of such draws, we keep the size of PD
sufficiently large. This assumes that the number of dissimilar pairs is substantially larger than the number of similarpairs in the original distribution. This a suitable assumption, given that the number of “focused” clusters for any
particular user-preference is likely small. Thus, we makethe size of PD be |F | times larger than that of PS (P1 Line7). This also ensures that the data size exceeds dimension
size, and that the learning task is feasible.
Moreover, in inferring attribute weights we learn a diagonal A matrix (P1 Line 9). The reason for this choice is twofold. First, individual weights for attributes provide ease ofinterpretation. Second, learning a diagonal A is computationally much more tractable (especially in high dimensions)than learning a full one, since the latter requires solving a
program with a semi-definite constraint. Of course if desired,
one can instead learn a full matrix (in low dimensions).

3.2.2

Focused Cluster Extraction

Having determined attribute weights β, we extract thefocused clusters of interest. The main idea in “chopping out”
focused clusters from G is to first identify good candidate
nodes that potentially belong to such clusters, and then to
expand around those candidate nodes to find the clusters.
Details are given in Algorithm A1, which we describe below.
The process of finding good candidate sets to expand is detailed in Procedure P2. Intuitively, nodes in focused clusters
have high weighted similarity to their neighbors. Therefore,
we first re-weigh the edges E by the weighted similarity ofProcedure P1 InferAttributeWeights
Input: exemplar set of nodes Cex
Output: attribute weights vector β// generate similar and dissimilar node pairs
1: Similar pairs PS = ∅, Dissimilar pairs PD = ∅2: for u ∈ Cex , v ∈ Cex do PS = PS ∪ (u, v) end for
3: repeat
4:
Random sample u from set V \Cex
5:
Random sample v from set V \Cex6:
PD = PD ∪ (u, v)
7: until d|PS | dissimilar pairs are generated, d = |F |8: Oversample from PS such that PS = PD
9: Solve objective function in Equ. (1) for diagonal A
10: return β = diag(A)their end nodes (P2 Lines 2-4), induce G on the edges withnotably large weights1 (P2 Line 5), and consider the nodes in
the resulting connected components as our candidate nodes(P2 Lines 6-7). We call each such component a core set.
Next, we expand around each core by carefully choosing
new nodes to include in the cluster and continue expanding
until there exist no more nodes that increase the quality of
the cluster. There exist several measures of cluster quality
including modularity and cut size [24]. In this work, we use
conductance [3] as it accounts for both the cut size as wellas the total volume/density retained within the cluster. The
weighted conductance φ(w) (C, G) of a set of nodes C ⊂ V
in graph G(V, E, F ) is defined asP

φ(w) (C, G) =w(i, j)(i,j)∈E,i∈C,j∈V \C
Wcut (C)PP=
W V ol(C)w(i, j)i∈C j,(i,j)∈E

where W V ol(C) is the total weighted degree of nodes in C.
The lower the conductance of a cluster, the better its quality
is with few cross-cut edges and large within-density.
The expansion operation is presented in Procedure P3.
First, we enlist all their non-member neighbors as the candidate set (P3 Line 4). For each candidate node n, we com(w)pute the difference ∆φn in cluster conductance if n was
to be added to C (P3 Lines 6-16). If there exist any nodewith negative ∆ (i.e., node improves conductance), we pickthe best n with the minimum (i.e., largest absolute drop in
conductance) (P3 Lines 17-23). We continue iterating until
no candidate node yields negative ∆φ(w) .
The node additions are based on a best-improving searchstrategy. While being cautious in which node to add (thebest one at every step), our decisions are greedy. Thus, inthe following step of our algorithm we adopt a retrospective
strategy and check if there exist any nodes in C whose removal would drop conductance, presented in Procedure P4.
We repeat the node addition and removal iterations untilconvergence, that is, when the conductance stops changing(A1 Lines 7-12).
We remark that our algorithm is guaranteed to converge;as the (weighted) conductance of a cluster is lower-bounded
1
To identify such edges, we use hypothesis testing. We first findthe top few most weighted edges, and bootstrap a Normal distribution. We then progressively subject the remaining edges to amembership-test and consider only those that pass the test. Every time an edge passes the test, model parameters are updated.

Algorithm A1 FocusCO: Focused Clusters&Outliers
Input: attributed graph G(V, E, F ), exemplar nodes Cex
Output: focused clusters C and outliers O
1: Cores ← FindCoreSets(G(V, E, F ), Cex )2: C = ∅, O = ∅3: for each core i ∈ Cores do
4:
C ← Seeds(i).getN odes()5:
BSN = ∅ // holds all Best Structural Nodes to add(w)
6:
φcurr ← φ(w) (C, G)
7:
repeat(w)(w)
8:
φinit ← φcurr
(w)
(w)
9:
(C, BSN, φcurr ) ← Expand(G, C, BSN, φcurr )
(w)
(w)
10:
(C, φcurr ) ← Contract(G, C, φcurr )11:
BSN ← BSN \C
(w)
(w)
12:
until φinit = φcurr
13:
C ← C ∪ C,O ← O ∪ BSN
14: end forProcedure P2 FindCoreSets
Input: attributed graph G(V, E, F ), exemplar nodes Cex
Output: seed sets to expand as focused clusters
1: β ← InferAttributeWeights(Cex )// (re)-weigh edges by feature similarity of end-nodes
2: for each (i, j) ∈ Epdo
3:w(i, j) = 1/(1 + (fi − fj )T diag(β)(fi − fj ))4: end for
5: w0 ← maxw0 w0 ∈/ distributionf ({w| w ≥ w0 })6: Build induced subgraph g(V 0 , E 0 , F ) s.t.
∀u, v ∈ V 0 , (u, v) ∈ E, w(u, v) ≥ w0 iff (u, v) ∈ E 0
7: return ConnectedComponents(g(V 0 , E 0 , F ))by 0 and we improve (i.e., decrease) the weighted conductance in every iteration (P3 Line 8, P4 Line 5).2
We omit the details of the ∆ conductance computation forbrevity, but remark that it is an efficient operation. Specifically, the operation of a node u to be added to or to be
removed from a cluster S has complexity proportional tothe degree of u, i.e. O(d(u)). In addition, the total volume
of S is simply increased/decreased by the weighted degree
w(u) of u, when it is added/removed, which takes O(1).

3.2.3

Focused Outlier Detection

Our algorithm also identifies outlier nodes in each focusedcluster along with finding the clusters in a unified fashion.
Our definition of a focused cluster outlier is quite intuitive:a node that belongs to a focused cluster structurally (having many edges to its members), but that deviates from its
members in some focus attributes significantly is an outlier.
To quantify this definition, the main idea is to identify thebest structural nodes BSN s (best in terms of unweighted
conductance) during the course of expansion (P3 Lines 3,
14, 22) and later check if there exist any BSN s which were
not included in the resulting focused cluster (A1 Line 11).
In order to identify the best structural node for a clusterin each iteration, we need to also track its unweighted conductance. An advantage of our proposed approach is thatthe overhead of computing the unweighted ∆φ of a node,in addition to its weighted ∆φ(w) , is negligible. The reason
2
P4 Line 5 removes a node even if conductance remains the same,
however, the number of such steps is also bounded by cluster size.

Procedure P3 Expand
Input: attributed graph G(V, E, F ), focused cluster C, set(w)
BSN , current conductance φcurr
Output: a focused cluster C, its best structural nodes(w)
BSN , and its conductance φcurr
1: repeat2:
bestN ode = N U LL,
3:
bestStructureN ode = N U LL
4:candidateN odes ← neighbors(C)(w)
5:∆φbest = 0, ∆φbest = 0
6:
for each node n in candidateN odes do(w)
7:∆φn , ∆φn ← Get∆Conductance(G, C, n,add)
(w)
(w)
8:
if ∆φn < ∆φbest then
(w)
(w)
9:
∆φbest = ∆φn10:
bestN ode ← n
11:
end if12:
if ∆φn < ∆φbest then13:
∆φbest = ∆φn
14:
bestStructureN ode ← n
15:
end if16:
end for17:
if bestN ode 6= N U LL then18:
C ← C ∪ bestN ode
(w)
(w)
(w)
19:
φcurr = φcurr + ∆φbest
20:
end if21:
if bestStructureN ode 6= N U LL then22:
BSN ← BSN ∪ bestStructureN ode
23:
end if
24: until bestN ode = N U LL(w)
25: return C, BSN, φcurr
is that, to compute ∆φ, we simply count the total number,instead of the total weight, of those same edges that are
involved in the computation of ∆φ(w) . As such, both conductances can be computed efficiently at the same time andthe best structural node and the best focused cluster node
can be identified simultaneously.

3.2.4

Complexity analysis

Given an attributed graph G(V, E, F ) and the exemplar
nodes Cex , we first create similar and dissimilar node pairs
which we use to infer the attribute weights. As the optimization objective we adopt is convex and as we aim fora diagonal solution, local-optima-free gradient descent techniques will take O( d2 ) for an -approximate answer [6].
To determine good core sets to expand clusters around, we
re-weigh the graph edges by the weight vector β with complexity O(dm). Assuming β is sparse with only a few nonzero entries for focus attributes, the multiplicative factor
becomes effectively constant yielding a complexity of O(m).
Next, we identify the top-k edges with largest weights on
which we induce G to find the core sets (k  m). To do so,
we use a min-heap to maintain this top set while making asingle pass over the edges. This requires O(m log k) in theworst case, assuming each edge triggers an insertion into theheap. Using these top-k edges we estimate the parametersof a Normal distribution, which takes O(k). Next we makeanother pass over the edge set and subject each to a membership test against the Normal model in O(m). We induce
the graph on all the edges that pass the test, the connectedcomponents of which yield the core sets. Overall complexity
for finding the core sets is thus O(m log k).

Procedure P4 Contract
Input: attributed graph G(V, E, F ), focused cluster C, cur(w)rent conductance φcurr(w)
Output: a focused cluster C and its conductance φcurr
1: repeat2:
removed ← f alse3:for each node n in C do(w)
4:∆φn ← Get∆Conductance(G, C, n,remove)(w)
5:
if ∆φn ≤ 0 then6:
C ← C\n
(w)
(w)
(w)
7:
φcurr = φcurr + ∆φn8:removed ← true9:
end if
10:
end for11: until removed = f alse(w)
12: return C, φcurr
For expanding a focused cluster, we enlist all the nonmember neighbors as the candidate set C and evaluate theirweighted P∆ conductance. As discussed in §3.2.2, the complexity is n∈C d(n). Since C ⊆ V , it is equivalently O(m).
As we add one node at each iteration, the total complexity
becomes O(|S|m) where |S| is the size of the focused cluster, and |S|  n. Also note that focused clusters can beextracted around each core set in parallel.
We remark that scanning candidate set C for picking thebest node takes O(m) in the worst case. Assuming smallrounded focused clusters, one can expect that not all edgesof G are “touched” by C’s neighbors. This implies sub-linear
performance for expanding a single cluster in practice.3

3.2.5

Variants of FocusCO
We conclude this section by briefly discussing a couple ofvariants of our problem setting and how we can adapt our
proposed algorithm to handle these variants.
In one variant of the problem, the user might explicitly
ask for the exemplar nodes s/he provided to be included in
the focused clusters. While it is highly likely that most of
the exemplar nodes will indeed be part of the focused clusters found in Algorithm 1, inclusion of all is not guaranteed.
To handle this setting, we can include the connected components induced on the exemplar nodes as additional core
sets (in P2 Line 7) and later never allow the removal of any
exemplar node in extracting the clusters (in P4 Lines 5-9).
Another variant involves the user asking for a sparser representation of the focus attributes. In other words, it may
be practical to define the similarity among the exemplar
nodes using as few attributes as possible, especially in highdimensions. In such a case, we can tune the regularization
constant γ that we introduced in Equation (1) for learning
the weight vector β. Specifically, a large γ drives the second
term in the objective to become large. To make the pairs
in PD as dissimilar as possible, a dense β is learned. The
smaller the γ gets, the less the emphasis on the dissimilarpairs becomes, and a sparser weight vector is learned.4
In other settings, the user may choose to explicitly provide
the set of dissimilar nodes or the attribute relevances (i.e.,
the β vector) directly, which can be incorporated trivially.
3
Different ways of choosing the core sets (e.g., only using userprovided nodes) can remove the dependence on processing theentire graph, and allow FocusCO to run in sublinear time.
4
For γ = 0, constraint on PD is completely waived and β is zero.

Effectpofpincreasingpattributepspacepsize

EVALUATIONIn this section we thoroughly evaluate our method5 onclustering quality, outlier detection performance, and runtime on synthetic and real-world networks. None of the existing methods address the focused clustering and outlier
detection problem we pose in this paper. Nevertheless, we
compare to two representative techniques, CODA [14] andMETIS [19]. CODA is a graph clustering and outlier detection algorithm on attributed graphs, and treats all attributes
equally. The clustering is not steered by user-preference, assuch, it clusters the whole graph. METIS is a graph partitioning algorithm and does not provide outlier detection.
Both methods expect the number of clusters as input.
To evaluate focused clustering quality, we use the Normalized Mutual Information (NMI), a widely used metricfor computing clustering accuracy of a method against thedesired ground truth [21]. The ground truth in our caseis the true focused clusters that are relevant to a particularuser’s interest. The best NMI score is 1. We evaluate outlier
detection performance by the F1-score; the harmonic meanof precision and recall for a known set of outliers.

4.1
4.1.1

Results on Synthetic Graphs
Data generation

To study the behavior of our algorithm compared to otherapproaches on graphs with ground truth (focused) clusters
and outliers, we generated synthetic graphs with various
number of clusters focusing on different subsets of the attribute space, containing various number of clusters, andwith varying size ranges. Our generative algorithm is basedon the planted partitions model [9].
Simply put, given the desired number of nodes in eachcluster we split the adjacency matrix into blocks defined by
the partitioning. For each block Bij , we choose a probability pij . Using a random draw process we assign a 1, i.e. anedge, for each possible entry in the block, and 0 otherwise. In
other words, pij specifies the density of each block. The diagonal blocks constitute the actual clusters and off-diagonal
entries yield the cross edges. Unless otherwise noted, we set
pii = 0.35 and 0.10 ≤ pij ≤ 0.25, i 6= j.
We assign the graph clusters generated, either to one of
two focus attribute sets (i.e. focus-1 or focus-2) or as unfocused. Please note that in real-world graphs, we expect
to see more than two focuses on a variety of attribute subspaces. For each focused cluster, one of the two subsets(focus-1 or focus-2) is chosen as focus attributes. For each
attribute i in this subset the attribute values are drawn froma Normal distribution N (µi , σ) with uniform random meanµi ∈ [0, 1] and a variance σ = 0.001. The variance is specifically chosen to be small such that the clustered nodes “agree”
on their focus attributes. The rest of the attributes, on
the other hand, are drawn from a Normal distribution withmuch larger variance; N (0, 1). In contrast, all of the attribute values of nodes in unfocused clusters are drawn fromlarge-variance Normals.
Focused outliers are generated by randomly choosing members from each focused cluster and “deflating” (depending on
the setting) one or more of their focus attributes i; by replacing them by a value drawn from N (µi , σ = 1).
5
A FocusCO implementation is available at
http://bit.ly/focusedclustering

1
0.9
0.8
0.7
0.6

NMI

4.

0.5

FocusCOFocusCO:puniformpβ
CODA:p0.5
CODA:p0.1
CODA:p0.05
METISpSw(
METISpSuw(

0.4
0.3
0.2
0.1
0
10

20

40

NumberpofpAttributes

80

100

Figure 2: NMI vs. attribute size |F |. Results averaged over 100 runs, bars depict 25-75%.

4.1.2

Clustering quality

To study the clustering performance, we generated graphswith 3 focused clusters that are coherent in focus-1 attributes,
3 focused clusters that are coherent in focus-2 attributes,
and 3 unfocused clusters, for a total of 9 clusters. The task
is to extract the focus-1 clusters with the respective user
preference.
For comparison we use CODA and METIS, which do not
perform focused cluster extraction. They both partition theentire graph, and thus, we explicitly need to select the 3best clusters that these methods returned, by measuring theoverlap among the clusters they produced to the groundtruth clusters. Since both methods require the number ofclusters to be provided as input, we asked for the correct
number of (9) clusters, i.e. best performance, although inpractice this number is hard to choose as the number ofhidden clusters is unknown, especially for large graphs.
METIS is a graph partitioning algorithm that does nothandle attributes. In one version of METIS, we ignore theattributes and use only the graph structure. In a second
version, we incorporate attribute information by weighing
the edges of the graph (using β) by the attribute similarityof their end nodes. We call these two versions as weighted
METIS (w) and unweighted METIS (uw). While CODA canperform clustering for attributed graphs, a main challengewith it is to carefully choose a λ parameter that controls thetrade-off between structural and attribute similarity of thenodes. In our experiments we report results using 3 different
λ settings, 0.05, 0.1, and 0.5, for CODA.
Figure 2 shows the clustering performance (mean NMI
over 100 independent runs) of the methods when we increase
the number of attributes while retaining the same numberof (5) focus attributes for the focused clusters. We observethat FocusCO remains superior to all the other approaches
in the face of irrelevant attributes for the clustering task.
To illustrate the importance of weight learning, we also
study the performance of a variant of our FocusCO, inwhich we use a uniform attribute weight vector β, i.e., we
bypass weight learning and directly perform cluster extraction. We observe that the performance of this version of ouralgorithm drops quickly with increasing attribute size. Our
analysis suggests that this occurs due to the edge weights
having a more and more uniform distribution when weighted
by using a uniform β, which yields an inferior collection ofEffectEofEunfocusedEclusters

EffectfoffdifferentfclusterfsizesfinfG
1

0.9

0)9

0.9

0.8

0)8

0.8

0.7

0)7

0.7

0.6

0)6

0.6

FocusCOCODA:A0.5
CODA:A0.1
CODA:A0.05
METISA(w)METISA(uw)

0.5
0.4
0.3
0.2

0)5

0)3
0)2
0)1

0

0

10 20

40

FocusCOCODA:f0)5
CODA:f0)1
CODA:f0)05
METISfAw:
METISfAuw:

0)4

0.1

80

ClusterAsize(a) NMI vs. cluster size

160

NMI

1

NMI

NMI

EffectAofAclusterAsize
1

FocusCOCODA:E0.5
CODA:E0.1
CODA:E0.05
METISESww
METISESuww

0.5
0.4
0.3
0.2
0.1
0

[10(10] [10(20][10(40]Clusterfsizefrange[10(80]

0ES6w 4ES10w[10(100]

9ES15w 14ES20w

24ES30w

34ES40w

44ES50w

NumberEofEunfocusedEStotalwEclusters(b) NMI vs. variable cluster size(c) NMI vs. number of unfocused clusters

Figure 3: NMI clustering quality results on synthetic graphs, for FocusCO, CODA with three different λparameter settings, and METIS on un/weighted graphs; (a) for changing cluster sizes (all clusters have thesame size), (b) for changing cluster size variance (graph has variable size clusters), and (c) for increasing
number of unfocused clusters. FocusCO performs the best in all scenarios across a wide range of settings.
Symbols depict the mean over 100 runs, bars depict 25-75%.

6

To ensure sparsity of the growing graphs, we set pij = 0.02.

suggests that CODA is more suitable for attributed graphswith uniform graph clusters and would suffer when the graphcontains many heterogeneous focused clusters (with multiple
focuses) as we would expect to see in real networks.
EffectsMofMfocusMattributesMoverlapping
1
0.9
0.8
0.7
0.6

NMI

core sets around which we find clusters. Thus, we proceedwith studying the performance of our original FocusCO.
Next in Figure 3 we show the clustering performance ofthe methods under various other settings. In (a), we increase
the cluster size where we create clusters of the same size inthe graph. In (b), we allow the graph to contain variable
size clusters and increase the variance of the cluster sizes,
by randomly drawing them from increasing ranges. Finallyin (c), we increase the number of unfocused clusters in thegraph, while keeping the number of focused clusters fixed.6
Notice that recovering a few focused clusters of interest in
the existence of more unfocused clusters is an increasingly
challenging problem.
From all these setups, we observe that FocusCO outperforms the competing methods and their variants in all
scenarios. Weighted METIS seems to achieve slightly better
performance than the unweighted version, although the differences are not significant. CODA’s accuracy is the lowest,
as the homophily assumption it is making does not hold in
the full attribute space. We note that in (c), one parameterization of CODA (λ = 0.5) achieves as high accuracy
as METIS for small number of clusters. Its accuracy, however, quickly drops when many more unfocused clusters thanfocused ones are introduced. Other two parameterizations
give low accuracy, pointing out the sensitivity of CODA tothe choice of its parameter.
Finally, we study the clustering performance when focus1 and focus-2 clusters share common focus attributes. We
create 20 node attributes out of which the first 10 are assigned as focus-1 attributes and the next 10 are assigned as
focus-2 attributes to the respective clusters. Then, we gradually overlap the focus attributes until they are the same setof 10 for all the focused clusters. Figure 4 shows that theperformance of FocusCO remains stable and high across all
overlaps. The accuracy of METIS (w) is also quite stable
and stays around 0.6 (METIS (uw) is not expected to beaffected in this setup). We also notice that CODA’s performance starts increasing after more than 50% of the focus
attributes overlap. At 100%, there is essentially only a single
focus in the graph, where CODA’s performance peaks. This

0.5

FocusCOCODA:M0.5
CODA:M0.1
CODA:M0.05
METISM:wT
METISM:uwT

0.4
0.3
0.2
0.1
0
0OM

10OM 20OM 30OM 40OM 50OM 60OM

70OM 80OM 90OM 100OM

PercentMofMoverlappingMfocusMattributes

Figure 4: Clustering performance by increasing
overlap on focus attributes of different focused clusters. (mean NMI over 100 runs, bars: 25-75%).
These results show the robustness of FocusCO, where its
performance remains quite stable across different settings.
They also illustrate that the general graph clustering methods are not suitable for our focused clustering problem, as
their performance is (i) sensitive to the (parameter) setting,and (ii) lower than that of FocusCO at all settings.

4.1.3

Outlier detection

Next we evaluate outlier detection performance. Since
METIS does not detect outliers, we compare to CODA. In
addition to its λ parameter, CODA expects a parameter rthat controls the top percentage of nodes to be returned
as outliers. We report experiments for the cross-product of
λ = {0.05, 0.1, 0.5} and r = {1%, 5%}.
In the first setup, we study the performance with respect
to the severity of outliers. If an outlier deviates in a larger
number of focus attributes from its cluster members, it becomes more severe in outlierness, but easier to detect. To
create outlier nodes with higher outlierness, we gradually in-CODA:y0.5,y1A

0.9

CODA:y0.5,y5A
CODA:y0.1,y1A

0.8

CODA:y0.1,y5A

F1Precision

1

5

2

3

4

Numberyofyfocusyattributesydeflated(a) F1-score

5(b) precision

Figure 5: Outlier detection performance by increasing number of deflated focus attributes.
We further analyze the outlier detection accuracy with respect to the attribute space size. In Figure 6 we observe that
CODA’s performance starts dropping after a certain numberof attributes, where identifying descriptive focus attributes
becomes more and more crucial to accurately spot the outliers that are hidden in different community structures. The
performance of FocusCO on the other hand remains quite
stable and superior to CODA.
1

FocusCOCODA:F0.5,F1:
CODA:F0.5,F5:
CODA:F0.1,F1:
CODA:F0.1,F5:
CODA:F0.05,F1:
CODA:F0.05,F5:

0.9
0.8
0.7

0.2

FocusCOCODA::0.5,:1%
CODA::0.5,:5%
CODA::0.1,:1%
CODA::0.1,:5%
CODA::0.05,:1%
CODA::0.05,:5%Precision

F1

0.3

TimeC9secF

100

50

5
0
0

0w5

2

NumberDofDedgesD|E|

2w5

3

3w5
5

0

10

xD10

20

30

40

50

NumberCofCattributes

60

0.5
0.4

0.1

Dataset description

|V |
124
362
27199
30599
77381

|E|
333
1288
66832
146647367151

|F |
28
44839
4
18
30087

Running time (sec)0.0017 ± 0.0022 (8.3)
0.0040 ± 0.0052 (2.8)
0.0052 ± 0.0018 (3390.9)
0.2868 ± 0.0630 (761.4)
2.9643 ± 0.7201 (257.4)

0

10

20

30

Total:number:of:attributes(a) F1-score

40

50

10

20

30

TotalFnumberFofFattributes

4050(b) precision

Figure 6: Outlier detection performance by increasing number of attributes |F |.
Finally, we note that the precision of FocusCO is often
higher than its recall, while both being superior to CODA’s.

4.1.4

70

(b) time vs. #attributes

Results on Real-world Graphs

DatasetDisney
PolBlogs
4Area
DBLP
YouTube

0.6

0.2

0

1w5

We use several attributed networks obtained from realworld data to evaluate our approach. Disney is an Amazon co-purchase graph of Disney movies.7 Each movie has
28 attributes such as price, rating, number of reviews, etc.
PolBlogs is the citation network among a collection of online blogs that discuss political issues. Attributes are the
keywords in their text. DBLP and 4Area are two different
co-authorship networks of computer science authors. The
attributes reflect the conferences which an author has published in broadly (DBLP), or just in databases, data mining, information retrieval, and machine learning (4Area).
Finally, we have the friendship relations of YouTube users
and the attributes depict their group memberships. Dataset
statistics are given in Table 2.

0.3

0.1

1

Table 2: Real-world datasets used in this work. Average running time in seconds per cluster ± std (avg.
number of clusters extracted).

EffectFofFincreasingFnumberFofFdimensions

Effect:of:increasing:number:of:dimensions
0.5

0.4

150

10

4.2.1

0

NumberAofAfocusAattributesAdeflated

15

200

0.4

0
4

20

4.2

0.5

0.1

3

25

0.6

0.2

2

250

30

Figure 7: Running time scalability w.r.t. (a) number of edges |E| and (b) number of attributes |F |.

0.3

0.1

300

CODA:y0.05,y5A

0.7

FocusCOCODA:A0.5,A1%
CODA:A0.5,A5%
CODA:A0.1,A1%
CODA:A0.1,A5%
CODA:A0.05,A1%
CODA:A0.05,A5%

135(a) time vs. #edges

CODA:y0.05,y1A

0.2

40

CODAMCλ=0S5Mk=9
FocusCOC9totalF
FocusCOC9/clusterF
METISC9uwFMCk=9

FocusCO

1

0.5

0.4

EffectCofCattributeCsizeCgrowthConCruntime

350

CODA:Dλ=0w5Ik=9
FocusCODatotall
FocusCODa/clusterl
METISDauwlIDk=945

OutlieryDetectionybyySeverityyofyOutlier

OutlierADetectionAbyASeverityAofAOutlier

0.3

EffectDofDedgesDonDruntime
50

TimeDasecl

crease their number of focus attributes that we deflate. Figure 5 shows the F1-score and precision (averaged over 100runs). We observe that FocusCO achieves superior performance to CODA in both metrics. We can also notice theincrease in detection accuracy of FocusCO with increasing number of deflated focus attributes (i.e., increasing easein spotting outliers), as we expected, while the same trend
is not apparent for CODA potentially because it does notcalibrate to attribute subspaces.

Scalability

Finally we study the scalability of the methods. Figure
7 shows the running times with increasing number of edges
and attributes. CODA’s inference techniques are computationally demanding, and thus, its running time is muchhigher than other methods. METIS on the other hand uses
an extremely efficient heuristic and achieves low runningtimes. We report the average cluster extraction time for
FocusCO in addition to total running time, as each cluster
extraction can be performed in parallel. In fact, we noticethat while its total running time increases by graph size, average time to extract a single cluster remains stable and low.
In such a case, FocusCO is also comparable to METIS.

4.2.2

Running time

Our real datasets come from various domains and havedifferent node, edge, and attribute counts. Here we reportrunning time experiments to demonstrate the efficiency of
our method on these real graphs.
We setup 10 runs of our method on each graph, each witha randomly sampled 1% of the attributes as the focus attributes. Each run returns a different number of clusters,
thus we report the running time per cluster averaged overthe 10 runs and their standard deviations in Table 2. Noticethat similar to Figure 7, the running times are quite low.
In particular, the average time to extract a cluster in ourlargest graph YouTube takes around 3 seconds.

4.2.3

Case Studies

The first case study we consider is finding two types offocused clusters in Disney. In one instance, a user wants
to understand how the popularity of a movie influences its
7

http://www.ipd.kit.edu/~muellere/consub/

Figure 8: Two sets of focused clusters in Disney. Left clusters focus on attributes related to popularity (salesrank, number of reviews, etc.) Nodes in right clusters share similar ratings. Outliers are marked with red
and illustrated. See text for discussion. (best viewed in color)eRipostecommunity in a co-purchase network. The user decides
that the product’s popularity is related to the features Number_of_reviews and Sales_rank, and so chooses a few products which have similar values in those attributes. FocusCO then uses this exemplar set Cex to learn an attributeweighting βu . This βu reflects the user’s intent, and has
also captured another dimension correlated with those attributes; Number_of_different_authors.
Several extracted focused clusters for this task are shownon the left in Figure 8. In general, the discovered clusters
consist of movies of similar age and acclaim. The first focused cluster (blue) reflects traditional Disney classics suchas Robinhood. Its outlier is a sequel (An Extremely Goofy
Movie) that is much less popular than the other classics inthe cluster. The second community (green) focuses on popular older Disney movies, and has outliers such as American
Legends and again the Goofy sequel, that are much lesspopular. The third cluster (orange) overlaps with the first
focused cluster. It is a subset of the classic Disney moviesof the larger cluster that were predominantly starred by animals (e.g., The Rescuers). Its cluster outlier is The Black
Caldron, which although of similar vintage, starred a humanprotagonist and was much less popular.
In the next instance, a user wants to examine how thedifferences in the distribution of consumer ratings affect theDisney clustering. In this case, the focused clusters represent collections of movies that are similarly rated (e.g., Pixar
films or animated Disney classics). The outliers represent
movies which are rated differently from the movies they arepurchased with, and reflect consumer opinion. The results
are shown in the right of Figure 8. The first focused cluster (purple) represents traditional Disney classics. Its outlier(which was included in the previous focused popularity cluster) is the movie A Goofy Movie which although reasonably
popular, is not as high rated. The second cluster (green) is
the Pixar community, featuring high-rated movies like Toy
Story. Its focused outlier is the live action version of 101
Dalmatians, a movie which is rated quite differently thanmost Pixar films. The third cluster consists of renowned
Disney films such as Fantasia. It also contains an outlier,the Spanish version of Beauty and the Beast.
We consider a second case study on PolBlogs, where auser seeks to understand the difference between blog content

Waas

peacenikwarandpiece.com

prospect.org/weblog

simbaud.blogspot.com
scottcsmith.net markarkleiman.com

indcjournal.com

washingtonmonthly.com

freedomofthought.com

stevegilliard.blogspot.com

digbysblog.blogspot.com

rising-hegemon.blogspot.com

toteota.blogspot.com

imao.usrhymeswithright.mu.nu
davidsirota.com alternateworlds.blogspot.com
capitolbuzz.blogspot.com

Figure 9: A focused cluster of liberal blogs in PolBlogs with a focus on Iraq war debate. Outlier David
Sirota does not mention Waas in his posts.
written by different liberal bloggers during the height of the
Iraq war controversy in 2005. Using several liberal blogs
as an example set, the user learns a βu which represents
the focus of the bloggers (as shown in the top of Figure
9, text size of features proportional to weight). It contains
words such as eriposte, an active liberal blogger, peacenik,a term for an anti-war activist, and most strongly Waas.
Murray Waas was an independent journalist praised for his
investigative journalism of the Bush administration.8 The
focused community outlier for this group is David Sirota, awell-connected liberal blogger who did not explicitly mention
Waas in the dataset.
The third case study we consider is on the 4Area
dataset. Here a user wants to understand who the outliers are in the data mining co-authorship network. S/helearns a βu using {Christos Faloutsos, Jiawei Han, Jon
M. Kleinberg, Jure Leskovec, Andrew Tomkins} as input, who focus primarily on data mining. One of the focusedclusters found is around data mining researchers mostly inindustry, as shown in Figure 10. The outlier is Cameron
Marlow, the former head of Facebook’s data science team,
who collaborated with the researchers in the data mining
community but published on information retrieval.
8
http://www.huffingtonpost.com/jay-rosen/
murray-waas-is-the-woodwa_b_18875.html

DataBMining

SujuBRajan

DavidBLiben-Nowell
PratapBKhedkar
JeffreyBGoh

AnantBJhingran

JasmineBNovak

JasonBY.BZien

PavelBA.BDmitriev

Cameron Marlow

DanielBGruhl RaviBKumar
RamanathanBV.BGuha BoBPang
StephenBDillDavidBGibson
TapasBKanungo

NadavBEiron

KunalBPunera
LarsBBackstrom

AndrewBTomkins

SridharBRajagopalan

RaviBSundaram

SreenivasBGollapudi

D.BSivakumar
KevinBS.BMcCurley

JohnBA.BTomlinDavidBP.BWilliamson

JennyBEdwards

Figure 10: A focused cluster of data mining researchers in 4Area. Outlier Cameron Marlow closely
publishes with them, but on information retrieval.

5.

CONCLUSION

In this work we introduce a new problem of finding focusedclusters and outliers in large attributed graphs.
Given a set of exemplar nodes that capture the user interest, our goal is two-fold: 1) “chop out” clusters of similar
nodes that are densely connected and exhibit coherence in a
subset of their attributes, called the focus attributes, and 2)
identify focused outliers, i.e. nodes that belong to a focusedcluster in network structure but show deviance in some focus
attribute(s). We propose an efficient algorithm that infers
the focus attributes of interest to the user, and that both
extracts focused clusters and spots outliers simultaneously.
Experiments on synthetic and real-world graphs show theeffectiveness and scalability of our approach and that theexisting graph clustering and outlier detection techniques
are not suitable to handle the newly posed problem.

Acknowledgments
The authors thank the anonymous reviewers for their helpful comments. This material is based upon work supportedby the ARO Young Investigator Program grant with Contract No. W911NF-14-1-0029, an ONR SBIR grant underContract No. N00014-14-P-1155, NSF Grant IIS-1017181,
the Stony Brook University Office of Vice President for Research, the Young Investigator Group program of KIT aspart of the German Excellence Initiative, and by a postdoctoral fellowship by the Flanders research foundation(FWO). Any findings and conclusions expressed in this material are those of the author(s) and do not necessarily reflect
the views of the funding parties.

6.

REFERENCES[1] L. Akoglu, M. McGlohon, and C. Faloutsos. OddBall:
Spotting anomalies in weighted graphs. In PAKDD, 2010.
[2] L. Akoglu, H. Tong, B. Meeder, and C. Faloutsos. PICS:
Parameter-free identification of cohesive subgroups in large
attributed graphs. In SIAM SDM, pages 439–450, 2012.
[3] R. Andersen, F. Chung, and K. Lang. Local graphpartitioning using pagerank vectors. In FOCS, 2006.
[4] A. Banerjee, S. Basu, and S. Merugu. Multi-way clustering
on relation graphs. In SIAM SDM, 2007.
[5] S. Basu, I. Davidson, and K. Wagstaff. Clustering with
Constraints: Algorithms, Applications and Theory. 2008.
[6] S. Boyd and L. Vandenberghe. Convex Optimization.
Cambridge University Press, NY, USA, 2004.
[7] D. Chakrabarti, S. Papadimitriou, D. S. Modha, andC. Faloutsos. Fully automatic cross-associations. In KDD,
pages 79–88, 2004.

[8] A. Clauset. Finding local community structure in networks.
Physical Review E, 72(2):026132, 2005.
[9] A. Condon and R. M. Karp. Algorithms for graphpartitioning on the planted partition model. Random
Struct. Algorithms, 18(2):116–140, 2001.
[10] I. Dhillon, S. Mallela, and D. Modha. Information-theoretic
co-clustering. In KDD, 2003.
[11] C. H. Q. Ding, X. He, H. Zha, M. Gu, and H. D. Simon. A
min-max cut algorithm for graph partitioning and dataclustering. In ICDM, 2001.
[12] G. W. Flake, S. Lawrence, and C. L. Giles. Efficient
identification of web communities. In KDD. 2000.
[13] J. Gao, H. Cheng, and P.-N. Tan. Semi-supervised outlier
detection. In ACM Symp. on Appl. Comp., 2006.
[14] J. Gao, F. Liang, W. Fan, C. Wang, Y. Sun, and J. Han.
On community outliers and their efficient detection in
information networks. In KDD, pages 813–822, 2010.
[15] D. F. Gleich and C. Seshadhri. Vertex neighborhoods, low
conductance cuts, and good seeds for local community
methods. In KDD, pages 597–605, 2012.
[16] S. Günnemann, I. Färber, B. Boden, and T. Seidl.
Subspace clustering meets dense subgraph mining: A
synthesis of two paradigms. In ICDM, 2010.
[17] D. Hanisch, A. Zien, R. Zimmer, and T. Lengauer.
Co-clustering of biological networks and gene expression
data. In ISMB, pages 145–154, 2002.
[18] P. Iglesias, E. Müller, F. Laforet, F. Keller, and K. Böhm.
Statistical selection of congruent subspaces for outlier
detection on attributed graphs. In ICDM, 2013.
[19] G. Karypis and V. Kumar. Multilevel algorithms for
multi-constraint graph partitioning. In Proc. ofSupercomputing, pages 1–13, 1998.
[20] B. Long, Z. Zhang, X. Wu, and P. S. Yu. Spectralclustering for multi-type relational data. In ICML, 2006.
[21] C. D. Manning, P. Raghavan, and H. Schtze. Intro to
Information Retrieval. Cambridge University Press, 2008.
[22] F. Moser, R. Colak, A. Rafiey, and M. Ester. Mining
cohesive patterns from graphs with feature vectors. In
SDM, 2009.
[23] E. Müller, P. I. Sanchez, Y. Mülle, and K. Böhm. Ranking
outlier nodes in subspaces of attributed graphs. In ICDE
Workshops, pages 216–222, 2013.
[24] A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectralclustering: Analysis and an algorithm. In NIPS, 2001.
[25] C. C. Noble and D. J. Cook. Graph-based anomaly
detection. In KDD, pages 631–636, 2003.
[26] J. Tang and H. Liu. Unsupervised feature selection for
linked social media data. In KDD, pages 904–912, 2012.
[27] Y. Tian, R. A. Hankins, and J. M. Patel. Efficient
aggregation for graph summarization. In SIGMOD, 2008.
[28] H. Tong and C.-Y. Lin. Non-negative residual matrix
factorization with application to graph anomaly detection.
In SIAM SDM, pages 143–153, 2011.
[29] F. Wang and J. Sun. Distance metric learning in data
mining. In SIAM SDM. Tutorials, 2012.
[30] J. Whang, D. Gleich, and I. Dhillon. Overlapping
community detection using seed set expansion. In CIKM,
pages 2099–2108, 2013.
[31] S. White and P. Smyth. A spectral clustering approach tofinding communities in graph. In SDM, 2005.
[32] E. P. Xing, A. Y. Ng, M. I. Jordan, and S. J. Russell.
Distance metric learning with application to clustering withside-information. In NIPS, pages 505–512, 2002.
[33] J. Yang and J. Leskovec. Overlapping community detection
at scale: a nonnegative matrix factorization approach. In
WSDM, pages 587–596, 2013.
[34] Y. Zhou, H. Cheng, and J. X. Yu. Graph clustering basedon structural/attribute similarities. PVLDB, 2(1):718–729,
2009.