Scalable Anomaly Ranking of Attributed Neighborhoods
Bryan Perozzi
Leman Akoglu
Stony Brook University
Department of Computer Science{bperozzi, leman}@cs.stonybrook.edu
Abstract
Given a graph with node attributes, what neighborhoods1 areanomalous? To answer this question, one needs a quality
score that utilizes both structure and attributes. Popular
existing measures either quantify the structure only andignore the attributes (e.g., conductance), or only consider
the connectedness of the nodes inside the neighborhood andignore the cross-edges at the boundary (e.g., density).
In this work we propose normality, a new quality
measure for attributed neighborhoods. Normality utilizes
structure and attributes together to quantify both internalconsistency and external separability. It exhibits two key advantages over other measures: (1) It allows many boundaryedges as long as they can be “exonerated”; i.e., either (i)are expected under a null model, and/or (ii) the boundary
nodes do not exhibit the subset of attributes shared by theneighborhood members. Existing measures, in contrast, penalize boundary edges irrespectively. (2) Normality canbe efficiently maximized to automatically infer the shared attribute subspace (and respective weights) that characterize aneighborhood. This efficient optimization allows us to process graphs with millions of attributes.
We capitalize on our measure to present a novel
approach for Anomaly Mining of Entity Neighborhoods(AMEN). Experiments on real-world attributed graphs illustrate the effectiveness of our measure at anomaly detection, outperforming popular approaches including conductance, density, OddBall, and SODA. In addition to anomaly
detection, our qualitative analysis demonstrates the utility ofnormality as a powerful tool to contrast the correlation
between structure and attributes across different graphs.

DBLP
Twitter
L1 = 0.979, L2 = 2.17 L1 = 0.724, L2 = 1.10

Google+L1 = L2 = 0.124

LastFM
L1 = L2 = -0.427

Citeseer
L1 = L2 = -0.956

Facebook
L1 = L2 = -0.730

Figure 1: Example neighborhoods (inner circles)
and their boundaries (outer circles) in our realworld graphs from high (top-left) to low (bottomright) normality scores. Colors depict presence (red)or absence (white) of the attribute that maximizes
normality for each neighborhood. Dashed edges are“exonerated”. Results discussed further in Section 5.1.

The essence of graph anomaly detection lies in determining an appropriate anomaly score, which effectively
characterizes the quality of each neighborhood. Quantifying
the quality of graph neighborhoods has long been a researcharea of interest on its own, where it finds additional applications in network community detection and graph partitioning. Most of the existing approaches focus on unattributed
1 Introduction
or plain graphs and hence only utilize structure.
Graph anomaly detection [2] is a problem of pressing conThese structural approaches can be divided by whether
cern, with broad applications including network security,
they focus on the internal characterizations of a neighborspam/fraud detection (in social networks, financial networks,
hood, its separability from its boundary, or a combination ofetc.), database integrity, and more.
both. Measures which solely use internal information judge
quality on intra-group connectivity statistics (e.g. average de1 A neighborhood is used as a general term throughout text andgree, edge density) and have been used for dense subgraphrefers to any connected subgraph; such as a cluster, community, mining [5, 17] and anomaly detection [1]. In contrast to insocial circle, ego network, etc.
ternal measures, boundary-centric measures (e.g. expansion,cut-ratio) define a neighborhood’s quality only in terms of
how separable it is from the rest of the graph. Perhaps themost popular measures are those which characterize a neighborhood by both its internal characteristics and its boundary(e.g. modularity [15] and conductance [4]).
In contrast to numerous measures that focus solely on
structural quality, there exist only a few attempts that alsoutilize attributes. For example, several methods aim to findcommunities in attributed graphs that not only are dense but
also exhibit attribute coherence [3, 8, 10]. Most recently,
others also quantify the connectivity at the boundary to findoutlier nodes or subgraphs in attributed graphs [11, 16].
In this work, we propose a novel approach to detecting anomalous neighborhoods in attributed graphs. We define a neighborhood to be high quality when its nodes are(1) internally well connected and similar to each other ona specific attribute subspace (we call these shared attributes
the neighborhood focus), as well as (2) externally well separated from and/or dissimilar to the nodes at the boundary.
Based on this definition, we introduce a new measure called
normality to quantify the quality of attributed neighborhoods, which carefully utilizes both structure and attributes
together to quantify their internal consistency within, as well
as external separability at the boundary. (See Figure 1 forexamples of high-to-low normality neighborhoods fromvarious real-world graphs.) We note that the focus attributesof the neighborhoods may be latent and unknown a priori,
especially in high dimensions. Our method AMEN (forAnomaly Mining of Entity Neighborhoods) automaticallyinfers the focus attributes and their respective weights, so as
to maximize the normality score of a neighborhood. Neighborhoods with low normality scores, i.e., for which a focus
that yields high normality cannot be found, are considered low quality or anomalous. The main contributions of
our work are summarized as follows:• Neighborhood Quality Score:
We propose
normality, a new measure to quantify the quality ofthe structure (topology) as well as the focus (attributes)
of neighborhoods in attributed graphs. Intuitively,
normality quantifies the extent which a neighborhood is “coherent”; i.e., (i) internally consistent and(ii) externally separated from its boundary.
• Neighborhood Anomaly Mining: We formulate andsolve a novel anomaly mining task for attributed graphs.
Our proposed method, AMEN, discovers a givenneighborhood’s latent focus through the unsupervised
maximization of its normality. Those neighborhoods for which a proper focus cannot be identified receive low score, and are deemed as anomalous.
• Scalable Optimization: Our proposed measure lends
itself to an efficient convex optimization procedure.
This allows us to analyze real-world graphs with millions of attributes.

Experiments on real-world attributed graphs show theeffectiveness of our approach. Specifically, we show theutility of our measure in spotting anomalies in attributedgraphs, where AMEN outperforms existing approaches including conductance, density, OddBall [1], and SODA [11]by 16%-25% mean precision. Furthermore, we qualitatively
analyze the high and low normality neighborhoods, andshow how our method can effectively contrast differences incorrelation between structure and attributes across graphs.
2

Problem Statement

We consider the ranking problem of entity neighborhoods ina graph with node attributes by quality. More formally, let
G = (V, E, A) denote an attributed graph with |V| = n
nodes, |E| = m edges, and |A| = d node attributes (orfeatures). A neighborhood of G is defined as a set of nodes
C ✓ V and the edges among them, (i, j) 2 E, {i, j} 2 C.
We denote by B ✓ V the set of boundary nodes that areoutside the neighborhood but have at least one edge to somenode in the neighborhood, i.e., (c, b) 2 E, c 2 C, b 2
B, C \ B = ;.
We consider a neighborhood to be of high quality basedon two criteria: (i) internal consistency, and (ii) external
separability. Intuitively, a good neighborhood has many
internal edges among its members where they share a set of
attributes with similar values. In other words, a common set
of focus attributes makes the neighborhood members highly
similar. In addition, a good neighborhood has either only a
few edges at its boundary or many of the cross-edges canbe “exonerated”, that is, the focus attributes that make theneighborhood members similar to one another also makethem dissimilar to or separated from their boundary nodes.
In summary, the Anomaly Mining of Entity Neighborhoods (AMEN) problem is given as follows:
Given a set of neighborhoods C = {C1 , . . . , Ck } from agraph G = (V, E, A) with node attributes;
Define a measure to quantify the quality of Ci ’s based oninternal connectivity, boundary Bi , and attributes A,
Find the neighborhoods of lowest quality.
3

Neighborhood Quality in Attributed Graphs

In this work we propose normality, a new measure ofneighborhood quality based on a combination of internal
connectivity, external separability, and attributes. Our measure is motivated by two properties of real world networks:(i) that there are no good cuts in real world graphs [12], and(ii) that most user-defined social circles overlap with eachother [13]. Together, these imply the existence of (many)cross-edges between neighborhoods and at their boundary.
Figure 2 illustrates two specific scenarios that could drive
the emergence of many cross-edges at the boundary of highquality neighborhoods in real-world attributed graphs.

3.1 Proposed Measure Next we formally introduce
normality, our new measure to quantify the quality of
attributed neighborhoods. Normality is inspired by Newman’s modularity and assortativity [15, 14] (See AppendixA) but exhibits key differences. First, normality utilizes
both structure and attributes together. Second, its formulation generalizes to graphs with multiple node attributes (asopposed to assortativity which is defined only for a single(a) “Hub node” effect(b) Neighborhood overlap
node attribute). Our measure is built upon two intuitive criteria that define a high quality attributed neighborhood, (1)Figure 2: High-quality neighborhoods can have bad cuts
internal consistency and (2) external separability.
(i.e., many boundary-edges) due to (a) hub nodes or(b) neighborhood overlap. Our normality measure 3.1.1 Internal consistency: To quantify the internal concarefully utilizes a null model in (a) and node attributes sistency of a neighborhood, we propose to generalize scalarin (b) to exonerate such edges (dashed lines).
assortativity (Eq. (A.3)) which is defined over a graph with asingle attribute to a set of nodes with multiple attributes. The
The first scenario is where the cross-edges are due to internal consistency I of a neighborhood C is then written as
hub nodes in real graphs. Consider Figure 2 (a) as an
◆
|A| ✓
X
X
example, which shows a well structured neighborhood and
ki kj
Aij
xi (f )xj (f )a hub node in the host graph. Notice that the hub node I = cov(xi , xj ) =2m
i2C,j2Cf=1
connects to a considerable fraction of the nodes in the|A|neighborhood, creating many cross-edges at its boundary.
X
ki kj X=Aijxi (f )xj (f )These edges, however, are not surprising. In fact, they are2m
i2C,j2C
f =1
expected—as hub nodes by definition connect to a largeXki kj
body of nodes in a graph. While the quality of such a
(3.1)
=
Aij
xi · xj
neighborhood is diminished e.g., based on conductance,2m
i2C,j2C
our measure exonerates those edges as unsurprising undera null model, and does not penalize the neighborhood’s where A is the adjacency matrix of graph G, ki denotes node
i’s degree, and xi is the vector of attributes that node i is
normality score.
Another scenario where good neighborhoods have many associated with.
We remark that xi · xj translates to the dot-product simcross-edges at their boundary is when the neighborhoods
overlap. An example is given in Figure 2 (b) where two ilarity between the attribute vectors of neighborhood memoverlapping neighborhoods are shown. Good neighborhoods bers. However, it treats all of the attributes as equally imporhave many internal edges among their nodes, which implies tant in quantifying the similarity among nodes. In general,that overlap nodes have many edges to non-overlap nodes in it is more reasonable to assume that the neighborhood memboth neighborhoods. This in turn creates many cross-edges bers come together around a few common attributes (e.g.,
for both neighborhoods at their boundary. These edges, how- same school and same hobby). This is expected especiallyever, are driven by the internal density and should not affect in very high dimensions. We refer to those attributes upon
their (external) quality. Provided that overlapping neighbor- which neighborhood members agree, i.e. have similar valhoods have sufficiently different focus that makes them sep- ues, as the focus (attributes) of a neighborhood.
Therefore, we modify the internal consistency score byarable (e.g., football vs. chess group), normality exonerates such cross-edges based on the attribute dissimilarity introducing a non-negative weight vector w to compute theof boundary nodes to internal nodes. In contrast, measures weighted node similarities as
Xthat ignore attributes (e.g., cut-ratio, conductance, etc.) peki kjI=Aijs(xi , xj |w) ,nalize these cross-edges irrespectively. Those measures are (3.2)
2m
i2C,j2C
expected to perform poorly for graphs with many overlapping communities such as social networks.
for similarity s(xi , xj |w) = wT · (xi xj ), where denotes
These scenarios illustrate that using both structure and the Hadamard (element-wise) product, and w is a vector
attributes is meaningful and necessary to quantify the quality with the attribute weights. This corresponds to weighted dotof neighborhoods in real graphs. Our normality measure product similarity, (w1/2 xi )T ·(w1/2 xj ). We expect w tois unique in its notion of “exoneration” of edges at the bound- be sparse, in which only a few attributes corresponding to theary, which none of the existing measures exhibit. Rather, neighborhood focus have large values and zero elsewhere.
they either completely ignore the boundary or equally penalNote that each neighborhood C is associated with its
own weight vector wC , i.e. focus, which is potentiallyize all the boundary edges irrespective of context.

different across neighborhoods. Moreover, the attributeweights are often latent. For defining our quality criteria we
can assume w is known. Later in Section 4 we will show that
thanks to our formulation, we can infer this weight vector so
as to make a given neighborhood as internally consistent andexternally well-separated as possible. In the following we
discuss the properties captured by Eq. (3.2).
First, notice that the internal consistency is decreased
by missing edges inside a neighborhood, as Aij = 0 for(i, j) 2/ E. Second, the existence of an edge is rewarded
ki kj
as much as the “surprise” of the edge. Specifically, 2m
denotes the probability that two nodes of degrees ki and kj
are connected to each other by chance in a random networkwith the same degree distribution as the original graph [15].
As such, we define the surprise of an edge (i, j) 2 E aski k jki kj(12m ). The smaller 2m is for an existing edge insidea neighborhood, the more surprising it is and the more it
contributes to the quality of the neighborhood.
These two properties quantify the structure of the neighborhood. On the other hand, the similarity function quantifies the attribute coherence. As a result, the more similar theneighborhood nodes can be made by some choice of w, thehigher I becomes. If no such weights can be found, internal consistency reduces even if the community is a completegraph with no missing edges.
Overall, a neighborhood with (1) many existing and (2)“surprising” internal edges among its members where (3) (asubset of) attributes make them highly similar receives a highinternal consistency score.

boundary node of a cross-edge may not share the same focus attributes with the internal node; in which case the terms(xi , xb |w) becomes small or ideally zero (recall Fig. 2 (b)scenario). The higher the number of cross-edges that can beexonerated, the larger E (note the negative sign) and hence
the quality of a neighborhood becomes.
Note that good neighborhoods by normality differ
from quasi-cliques for which only internal quality measures,such as density [17] or average degree [5], are defined.
Different from those and besides internal consistency, we
also quantify the quality of the boundary of a neighborhood.
Normality is also different from popular measures thatdo quantify the boundary, such as cut-ratio [7], modularity[15] or conductance [4], for which good neighborhoods are
expected to have only a few cross-edges. In contrast, ourformulation allows for many cross-edges as long as they are
either (i) unsurprising (under the null model) or if surprising,(ii) can be exonerated by the neighborhood focus. Theseadvantages arise as we utilize both structure and attributes ina systematic and intuitive way to define our measure.

3.1.2 External separability: Besides being internallyconsistent, we consider a neighborhood to be of high quality
if it is also well-separated from its boundary. In particular, awell-separated neighborhood either has (1) few cross-edges
at its boundary, or (2) many cross-edges that can be “exonerated”. A cross-edge (i, b) 2 E (i 2 C, b 2 B) is exonerated either when it is unsurprising (i.e., expected under thenull model) or when internal node i is dissimilar to boundary
node b based on the focus attribute weights. The latter criterion ensures that what makes the neighborhood members
similar to one another does not also make them similar to theboundary nodes, but rather differentiates them. The external
separability E of a neighborhood C is then
(3.3)
X
ki kb
) s(xi , xb |w)  0 .
E=
1 min(1,2m
i2C,b2B,(3.4)

3.2 Normality Having defined the two criteria for thequality of a neighborhood, normality (N ) is written as
the sum of the two quantities I and E, where high quality
neighborhoods are expected to have both high internal consistency and high external separability.
X
ki kj
N =I +E =Aijs(xi , xj |w)
2m
i2C,j2C

X

i2C,b2B(i,b)2E

1

min(1,ki kb) s(xi , xb |w)
2m

For a neighborhood with the highest normality, all
the possible internal edges exist and are also surprising forwhich pairwise similarities are high. These ensure that thefirst term is maximized. Moreover, the neighborhood either
has no cross-edges or the similarity or surprise of existing
cross-edges to the boundary nodes are near zero, such thatthe second term vanishes. Neighborhoods of a graph forwhich the normality takes negative values are of lesser
quality and deemed as anomalous.
Choice of similarity function: To this end, we considered
the node attributes to be scalar variables where s(xi , xj |w)
is the weighted dot-product similarity. If the attributes are
categorical (e.g., location, occupation, etc.), one can instead
use the Kronecker delta function (·) that takes the value 1 if(i,b)2E
two nodes exhibit the same value for a categorical attribute
External separability considers only the boundary edges and 0 otherwise.
and quantifies the degree that these cross-edges can be exonThe choice of the similarity function is especially imerated. As discussed earlier, cross-edges are exonerated in portant for binary attributes (e.g., likes-biking, has-job, etc.).
two possible ways. First, a cross-edge may be unsurprising; While those can be thought of as categorical variables taki kb
in which case the term (1 min(1, k2m)) becomes small ing the values {0, 1}, using Kronecker becomes undesiror ideally zero (recall Fig. 2 (a) scenario). Second, the able for nodes inside a neighborhood. The reason is, inter-nal consistency by the function is the same both when all
the neighborhood nodes exhibit a particular binary attribute(all 1) and when none does (all 0). However, one may notwant to characterize a neighborhood based on attributes thatits members do not exhibit even if the agreement is large.
Therefore, we propose to use dot-product for computing internal consistency and Kronecker for computing external
separability for binary-attributed graphs.
4 Anomaly Mining of Entity Neighborhoods
As presented so far, when given a neighborhood C of an
attributed graph and vector w of attribute weights, we candirectly compute its normality using Eq. (3.4). However,for the task of anomaly mining, the focus of a neighborhood
is latent and hard to guess without any prior knowledge. Thisis especially true in high dimensions where most attributes
are irrelevant, making a uniform attribute weight vector
impractical. Moreover, even if the neighborhood focus is
known a priori, it is hard to assign weights to those attributes
beyond that of binary relevance.
In this section, we propose an optimization approach toautomatically infer the attribute weight vector for a givenneighborhood, as the vector that maximizes its normality
score. That is, we aim to identify a subspace that would
make the neighborhood’s normality as high as possible.
All neighborhoods can then be ranked based on their (bestpossible) normality scores, and those with lowest scores canbe deemed anomalous. This allows us to restate our original
problem in Section 2 as follows:
Given a set of neighborhoods C and normality N ;Find the attribute weight vector wCi which maximizes
N (Ci ) for each neighborhood Ci 2 C,
Rank neighborhoods C by normality score,
Find the neighborhoods of lowest quality.
4.1 Neighborhood Focus Extraction Our goal is to findan attribute weight vector (hereafter called wC ) for a neighborhood C, which makes its normality as high as possible, such that connected nodes in the neighborhood are very
similar and the nodes at the boundary are dissimilar. To thisend, we leverage our normality to formulate an objectivefunction parameterized by the attribute weights. This objective also has the nice property of quantifying structure, by
penalizing non-existing in-edges and surprising cross-edges.
Our formulation for focus extraction is then maxwC N (C),which by reorganizing the terms that do not depend on wC ,can be rewritten (based on Eq. (3.4)) as
 X
ki kj
max
wC T ·Aijs(xi , xj )wC2m
i2C,j2C

X

i2C,b2B(i,b)2E

1

min(1,ki kb) s(xi , xb )
2m

(4.5)

max
wC

wC T · (xI + xE )where xI and xE are vectors that respectively denote thefirst and the second summation terms. Note that these canbe directly computed from data. Moreover, the similarity
function s(xi , xj ) can be replaced by either (xi xj ) or
(xi , xj ) depending on the type of the node attributes.
4.2 Size-invariant Scoring The normality score in Eq.
(4.5) grows in magnitude with the size of the neighborhood
C being considered. Normalization is desirable then, inorder to compare across differences in both neighborhoodand boundary size.
We note that I is the maximum in the case of a fully
connected neighborhood the members of which all agree
upon the focus attributes. Therefore, Imax = |C|2 , where
smax (xi , xj ) = 1 provided that the attributes xi (f ) arenormalized to [0, 1] for each node i. On the other hand theminimum is negative, when there exists no internal edges
and pairwise similarities are maximum. That is, Imin =P
ki k j
i2C,j2C
2m . To normalize the internal consistency
I, we subtract Imin and divide by Imax Imin , which isequivalent to a weighted version of edge density.
To normalize external separability, we derive a measure similar to conductance [4], i.e., ratio of boundary or
cut edges to the total volume (sum of the degrees of theneighborhood nodes). The difference is that each edge
is weighted based on its surprise and the similarityof itsP
i2C,j2C
end nodes. In particular, we define xI˜ =1(i,j)2E

ki k jmin(1, 2m) s(xi , xj ). Note that similar to E, I˜ considers
only the existing edges in the graph. Therefore, I˜ E canbe seen as the total weighted volume of the neighborhood.
Overall, we scale our measure as follows, where thedivision of the vectors in the second term is element-wise.
As such, x̂I (f ) 2 [0, 1] and x̂E (f ) 2 [ 1, 0].

N̂ = wC T (x̂I + x̂E ) = wC T (xI IminxE+)
Imax IminxI˜ xE

4.3 Objective Optimization The normalized objectivefunction can be written as
(4.6)
max
wC T · (x̂I + x̂E )
wC

s.t.

kwC kp = 1, wC (f )0, 8f = 1 . . . d

Note that we introduce a set of constraints on wC
to fully formulate the objective. In particular, we require
the attribute weights to be non-negative and that wC isnormalized (or regularized) to its p-norm. These constraints
also facilitate the interpretation of the weights. In thefollowing we let x = (x̂I + x̂E ), where x(f ) 2 [ 1, 1].
There are various ways to choose p, yielding different
interpretations. If one uses kwC kp=1 , a.k.a. the L1 norm,Table 1: Real-world graphs used in this work. ⇤ depicts datasets with ground truth circles. n: number of nodes, m:number of edges, d: number of attributes, |C|: number of circles, |S|: average circle size.
Name⇤
Facebook⇤
Twitter⇤
Google+DBLP
Citeseer
LastFMn = |V|
4,039
81,306
107,614108,030
294,104
272,412m = |E|88,234
1,768,149
13,673,453
276,658
782,147
350,239d = |A|
42-576
1-2,271
1-4,122
23,285
206,430
3,929,101

|C|
193
4,869
479
n/a
n/a
n/a

|S|
21.93
12.51
134.75n/an/an/a

the solution picks as the neighborhood focus the single
attribute with the largest x entry. That is, wC (f ) = 1
where max(x) = x(f ) and 0 otherwise. One can interpret
this as the most important attribute that characterizes theneighborhood. Note that x may contain only negative
entries, in which case the largest negative entry is selected.
This implies that there exists no attribute that can make thenormality positive, and hence such a neighborhood is
considered anomalous. Note that when p = 1, N̂ 2 [ 1, 1].
If there are multiple attributes with positive x entries, we
can also select all of them as the neighborhood focus. The
weights of these attributes, however, should be proportional
to the magnitude of their x values. This is exactly what
kwC kp=2 , or the L2 norm yields. In particular, we canshow that wC (f ) = pP x(f ) x(i)2 , for x(f ) > 0 and

nodes
users
users
users
authors
articles
users

edges
friendships
follow relations
friendships
co-authorships
citationsfriendships

attributes
user profile information
hashtags and user mentions
user profile information
title words used in articles
abstract words used in articles
music pieces listened tothe complexity is O(|C|2 d + |EB |d) for computing x andO(d) for finding the maximum entry (for L1 regularization)or positive entries (for L2 regularization), where EB is thenumber of cross-edges which is upper-bounded by |C||B|.
Therefore, the complexity is quadratic w.r.t. the neighborhood size |C| ⌧ n, and linear in the number of attributes d,while it is independent of the size of the entire graph.
5

Experiments

Through experiments, we (1) evaluate AMEN’s performance 2 in anomaly detection, (2) perform case studies
that analyze the type of anomalies we find, and (3) utilize
normality as an exploratory tool to study the correlation
between structure and attributes across different graphs.
Datasets. A detailed description of real-world graphs usedx(i)>030 otherwise, where wC is unit-normalized. Then, the in this work is given in Table 1. Facebook, Twitter, andGoogle+eachconsistsofacollectionof ground-truth social
normality score of the neighborhood becomes
circles.
For
thesegraphs,weconsiderthese circles as theirN = wC T · x
entityneighborhoods.
For
the
other
graphs,we consider the
s X
X
x(f )
egonets(subgraphs
induced
on
each
node
and
its neighbors)qP=x(f ) =
x(i)2 = kx+ k2
astheir
entityneighborhoods.
2x(f )>0x(i)>0x(i)>0 x(i)Baselines. We compare AMEN’s performance in anomaly
i.e., the L2 -norm of x induced on the positive entries. As detection against existing measures and methods: Averagesuch, when there are multiple attributes that can make the Degree [5], Cut-Ratio [7], Conductance [4], Flake-ODF [6],normality positive, L2 formulation produces an objec- OddBall [1], SODA [11], and Attribute-Weighted Normalized
tive value that is higher than that of the L1 formulation. This Cut (AW-NCut) [10] (See Appendix B for definitions).
agrees with intuition; the larger the number of attributes with 5.1 Anomaly Detection Our evaluation of AMEN’s
positive x entries, the more attribute-coherence the neighbor- anomaly detection performance is two-fold. First, we perhood exhibits, and the higher the normality gets incre- form quantitative evaluation; we inject anomalies into DBLP,
mentally. On the other hand, if there are no positive entries Citeseer, and LastFM and compare detection performancein x, the L2 optimization selects the single attribute with the of different approaches. Second, we perform a qualitalargest negative entry, and we consider the neighborhood as tive case study of ground-truth neighborhoods with low
anomalous. In all, N̂ 2 [ 1, kx+ k2 ] when p = 2.
normality score from Facebook, Twitter, and Google+.
While L1 and L2 are the two most commonly used
Quantitative Evaluation. To create ground truth anomanorms, one can also enforce wC (f )  k1 , for each f , tolies, we use the egonets from DBLP, Citeseer, and LastFM
obtain the largest k entries of x that can be interpreted aswhich we perturb to obtain anomalous neighborhoods. Perthe top-k most relevant attributes for the neighborhood (noteturbations involve disruptions in (1) structure, (2) attributes,
that those may involve both positive and negative entries). In
principle, x provides a systematic and intuitive way to rank
the attributes by their relevance to a neighborhood.
2 AMENavailable at http://www.perozzi.net/
Computational complexity: Notice that the solution to the projects/amen
3 Datasets available from http://snap.stanford.edu/
optimization is quite straightforward where the complexity
mainly revolves around computing the x vector. Specifically, data/ and https://code.google.com/p/scpm/.

DBLP Structure Perturbation

DBLP Attribute Perturbation

0.25

DBLP Structure & Attribute Perturbation

0.2

0.22
0.2

AMEN
SODA
Attributed-NCut
Conductance
Cut Ratio
Flake-ODF
Avg. Degree
OddBall

0.1

0.05

0
0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.16
AMEN
SODA
Attributed-NCut
Conductance
Cut Ratio
Flake-ODF
Avg. Degree
OddBall

0.14
0.12
0.1
0.08
0.06
0.04
0.05

0.5

0.16
0.14
0.12

0.06

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.02
0.05

0.5

Citeseer Attribute Perturbation

0.5
0.4
AMEN
SODA
Attributed-NCut
Conductance
Cut Ratio
Flake-ODF
Avg. Degree
OddBall
0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.3
0.2
0.1
0
0.05

0.5

0.25

0.3

0.35

0.15

0.2

0.25

0.3

0.35

0.45

0.5

0.6
0.5
0.4
AMEN
SODA
Attributed-NCut
Conductance
Cut Ratio
Flake-ODF
Avg. Degree
OddBall

0.3
0.2
0.1

0.1

0.4

0.4

0.45

0
0.05

0.5

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5

Perturbation Level

Perturbation Level

LastFM Structure Perturbation

LastFM Attribute Perturbation

LastFM Structure and Attribute Perturbation

0.25
0.2
AMEN
SODA
Attributed-NCut
Conductance
Cut Ratio
Flake-ODF
Avg. Degree
OddBall

0.15
0.1
0.05

0.15

0.2

0.25

0.3

0.35

Perturbation Level

0.4

0.45

0.5

Average Precision AUC

0.3

0.3

0.1

0.2

Perturbation Level
0.35

0
0.05

AMEN
SODA
Attributed-NCut
Conductance
Cut Ratio
Flake-ODF
Avg. Degree
OddBall

0.4

0.35

0.25

0.2

0.15

AMEN
SODA
Attributed-NCut
Conductance
Cut Ratio
Flake-ODF
Avg. Degree
OddBall

0.1

0.05

0
0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

Perturbation Leveland (3) both. We start by choosing “good” neighborhoods;
specifically, small egonets (of size 30-100) that we expect
to have low conductance cuts [9]. From these egonets, wechoose 5% of them as anomalous, i.e., to be perturbed. To
perturb structure, we rewire inside edges to random outside
nodes with rewiring probability p. To perturb attributes, we
replace the attributes of inside nodes with the corresponding
attributes of randomly picked outside nodes with probabilityq (note that this “inheritance” only affects the egonet, andkeeps the outside nodes unchanged). For structure and attribute perturbation, we vary p or q from 0.05 to 0.50. To perturb both, we vary them simultaneously. The larger the perturbation intensities p and q, the more disrupted the egonet.
We expect this process to create anomalous (ground truth)
egonets, that are structurally poor, for which it is hard to findshared focus attributes.
We evaluate our measure in its ability to rank the disrupted ground truth anomalies high. Specifically, we rank
the neighborhoods by their normality and report the AUC(i.e., average precision) of the precision-recall plots for eachp and/or q perturbation intensity in Figure 3. We find that
AMEN consistently outperforms all other measures andmethods, especially at low perturbation intensities where thetask is harder—hence the gradual increase in performanceby intensity. When structure perturbation is involved (Seefigures on (left) and (right)), conductance and Flake-ODF
also appear to do well. When attributes are perturbed, on
the other hand, AMEN is superior, where SODA, the second best, is significantly worse than AMEN. Across perturbation strategies and datasets, on average AMEN outperforms Flake-ODF by 16%, conductance by 18%, AW-NCutby 20%, SODA by 23%, average degree by 24%, cut ratio

0.45

0.5

Average Precision AUC

0
0.05

0.5

Average Precision AUC

0.7

Average Precision AUC

0.8

0.6

0.1

0.15

Citeseer Structure & Attribute Perturbation

0.7

0.6

0.2

0.1

Perturbation Level

0.7

0.3

AMEN
SODA
Attributed-NCut
Conductance
Cut Ratio
Flake-ODF
Avg. Degree
OddBall

0.1
0.08

Perturbation Level

Citeseer Structure Perturbation

Average Precision AUC

0.18

0.04
0.1

Perturbation Level

Average Precision AUC

Average Precision AUC

0.15

Average Precision AUC

Average Precision AUC

0.18
0.2

0.3
0.25
0.2
AMEN
SODA
Attributed-NCut
Conductance
Cut Ratio
Flake-ODF
Avg. Degree
OddBall

0.15
0.1
0.05
0
0.05

0.1

0.15

0.2

0.25

0.3

0.35

Perturbation Level

0.4

0.45

0.5

Figure 3:
Anomalydetection results(mean precision
vs. perturbation
intensity) for
structure only
(left), attributeonly (center),and structure &attribute (right)
anomalies on
DBLP (top),
Citeseer(middle), and
LastFM(bottom).
AMEN issuperior,
especially when
attribute
perturbations
are involved.

by 24%, and OddBall by 25%.
Case Studies. We begin our case studies by returning to
Figure 1, which illustrated several examples of neighborhoods sorted by their normality (from high to low) fromvarious graphs. We see that the highest quality neighborhood shown (from DBLP) has good internal structure, andattributes which allow the complete exoneration of edges at
its boundary. As we progress through neighborhoods in order of quality, we see that internal structure weakens, andboundaries become larger. The lowest quality neighborhood
shown (from Citeseer) has almost no internal structure, andno attributes which exonerate its large boundary.
Next, we examine some of the most anomalous groundtruth circles from Facebook, Twitter, and Google+. Figure
4 shows that the circles with the lowest normality haveboth weak internal connectivity and poor boundary separation. None of the available attributes is able to meaningfully improve their score. We find these ground-truth neighborhoods to be particularly interesting, as they are real circles manually defined by social network users (hence groundtruth) which do not, however, exhibit characteristics of what
‘good’ communities in graphs look like.
Finally, we examine the difference between
normality and conductance, a popular structural
measure, in Figure 5. As expected, normality gets lower
for neighborhoods with increasingly high (bad) conductance(results are for DBLP and Google+, others are similar).
However, notice the many neighborhoods in DBLP withhigh normality scores even if they have very high (inrange (0.9, 1.0]) conductance (several others in other graphs,
and even one in Google+). These are exactly the type ofneighborhoods that are considered low quality by solely

1

1

0.9

0.9

0.7
0.6
0.5
0.4

0.8

Empirical CCDF

Empirical CDF

Facebook
Twitter
Google+DBLP
Citeseer
LastFM

DBLP

0.8

LastFM

0.3
0.2

Facebook
L1 = L2 = -0.995

Twitter
L1 = L2 = -0.993

Google+L1 = L2 = -0.873

Figure 4: Low normality ground truth neighborhoods
from Facebook, Twitter, and Google+.
DBLP

Google+0.4

Normality Score, L2

Normality Score, L2

3
2.5
2
1.5

0.5

0.3

0.1
1

10

2

10

3

10

4

10

Number of Positive Terms in x

5

10

0

Google+Facebook
Twitter
Google+DBLP
Citeseer
LastFM

0.4

0

0.2

0.4

0.6

0.8

1

Fraction of Nodes with Chosen L1 Feature

Figure 7: Distribution of neighborhoods w.r.t. (a) count of
positive terms in x (cdf), (b) fraction of nodes exhibiting
the L1 -selected attribute (ccdf).
structure and attributes in a graph. In this section, we
compare the distribution of neighborhood scores across allgraphs. Using normality as a lens, we see that:

0.6
4
3.5

Twitter

0.6

0.2

0.1
0
0
10

0.7

0.2
0
−0.2

• Different graphs display distinct distributional fingerprints, indicating very diverse correlation patterns between structure and attributes.
• In all graphs, the biggest gains in normality comeFigure 5: Box plots depicting L2 -normality score vs.
only from a few attributes—suggesting that a neighborconductance for (a) DBLP and (b) Google+.
hood focus is often sparse.
First, to examine the influence of attributes upon eachneighborhood, we turn to x = (x̂I + x̂E ) (Eq. (4.6)). For
each neighborhood, we count the number of positive entriesof x, #(x(i) > 0), and present their distribution in Figure7(a). As expected, only a small number of attributes are relevant for most communities, so a sparse w is obtained by
L2 . We see that both LastFM and DBLP have many posiL2 -normality: 2.55
L2 -normality: 2.63
tive attributes for each neighborhood, followed by Facebook,
Focus: {telescopic, multidecade, cascode} {reciprocal, split, reverse}
Citeseer, and Twitter. The worst neighborhoods are found in
Figure 6: Example high (poor) conductance but high Google+, where 99% of the circles do not have any attributethat characterizes them (i.e., non-positive x). Figure 7(b)normality neighborhoods from DBLP.
shows the fraction of nodes in each neighborhood which exstructural measures such as conductance, but achieve high hibit the attribute that would be chosen by L1 maximization.
score when attributes and surprise are carefully accounted Again, DBLP and LastFM have the most agreement insideeach neighborhood, followed closely by Facebook and Citefor under the notion of “exoneration”.
For example, consider the two neighborhoods with poor seer, while Twitter and Google+ neighborhoods are the mostconductance but high normality from DBLP as shown noisy in exhibiting the highest ranked attribute.
Figure 8 shows the distribution of normality scoresin Figure 6. The left drawing depicts the egonet of ‘Milind
acrossneighborhoods for both L1 (a) and L2 (b) maximizaS. Sawant’ (ego)—a co-authorship circle of four researcherstion.
We
see that 89% of DBLP and 95% of LastFM neighfrom electrical engineering—as well as their boundary (otherborhoods
have positive normality, while with the excepcollaborators). We notice that the other nodes in the egonet,
tion
of
a
few
very good neighborhoods, the rest are mostly
i.e. the neighbors of the ego, have considerably larger
negative.
L
2 optimization does not dramatically change
set of collaborators. This creates numerous cross-edges,
where
the
bulk
of the distribution is. Majority of DBLP
yielding poor conductance. However, this circle is wellneighborhoods
gain
additional score, and 10% of LastFM
defined and “focused”; these four authors exclusively workneighborhoods
gaina
lot of score. In others we see a small
together on ‘telescopic op-amps’; notice the listed focus
improvement,
where
Google+presents neighborhoods withattributes (words). Similarly, the ego ‘Saad Bouguezel’
lowestnormality(its
best
circlescore by L2 is ⇡ 0.6).
of the right neighborhood is much less connected than his
Thecontribution
from
each
positive
attribute to thecollaborators, creating excessive cross-edges. Those edges
neighborhood
score
for
DBLP
and
LastFMisshown in Figare exonerated by normality, due to their discriminating
ure
9.
We
see
that
relevance
drops
fast,
and
essentiallyzefocus on ‘reciprocal transforms’ and ‘split-radix FFTs’.
roes out after around 20 attributes. An interesting differ5.2 Graph Analysis with Normality Normality also ence occurs between the two graphs, which have both many
serves as a powerful tool for analyzing the correlation of good neighborhoods, but achieve them in different ways. In
1

0.5
0

−0.4
−0.6
−0.8

−0.5

−1

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1.0

Conductance

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1.0

Conductance

M. N. Shanmukha Swamy

Jaime Ramírez-Angulo

Milind S. Sawant

Ramón González Carvajal

Antonio J. López-Martín

Saad Bouguezel

M. Omair Ahmad

1

1

DBLP

normality = 0

0.8

Empirical CCDF

0.8
0.7

Empirical CCDF

Facebook
Twitter
Google+DBLP
Citeseer
LastFM

0.9

0.9

0.6

LastFM

0.5
0.4

Facebook
Twitter
Google+DBLP
Citeseer
LastFM

0.3
0.2
0.1
0
−1

DBLP

0.7
0.6

Acknowledgments

0.5

normality = 0

0.4
0.3

LastFM

0.2
0.1

−0.5

0

0.5

0
−1

1

0

1

2

3

4

5

6

7

Normality Score, L2

Normality Score, L1

Figure 8:
Distribution of neighborhoods w.r.t.
normality(ccdf); w constraint by (a) L1 , (b) L2 .
LastFM

DBLP
1

0.8

0.9

0.7

Normality Score

Normality Score

0.8
0.7
0.6
0.5
0.4
0.3
0.2

0.6
0.5
0.4
0.3
0.2
0.1

0.1
0

0
1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20

k−th positive feature

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20

k−th positive feature

Figure 9: Normality of neighborhoods based on k-th
most positive attribute with highest x entry.
DBLP, the first few positive attributes are all about equally
good, but then they degrade quickly. On the other hand,
LastFM attributes are usually not as good, but many of them
can add up to achieve a neighborhood with a high score (andhence the long tail in Figure 8(b)).
6

The authors thank the anonymous reviewers for their usefulcomments. This material is based upon work supported by
the ARO Young Investigator Program under Contract No.
W911NF-14-1-0029, NSF CAREER 1452425, IIS 1408287
and IIP1069147, DARPA Transparent Computing Program
under Contract No. FA8650-15-C-7561, a Facebook Faculty
Gift, a R&D grant from Northrop Grumman Aerospace
Systems, the Institute for Advanced Computational Scienceat Stony Brook University, and the Stony Brook University
Office of Vice President for Research. Any conclusions
expressed in this material are of the authors’ and do notnecessarily reflect the views, either expressed or implied, ofthe funding parties.

Conclusion

In this work, we considered the problem of discovering
anomalous neighborhoods in attributed graphs. We proposed
normality, a new quality measure that evaluates neighborhoods both Internally and Externally. Intuitively, a highquality neighborhood has members with (I1) many surprising edges connecting them that (I2) share similar values in aparticular attribute subspace, called the neighborhood focus.
Moreover, it has either (E1) a few edges at the boundary,or (E2) many cross-edges which can be exonerated as unsurprising under the null graph model and/or dissimilar withrespect to the focus attributes.
We utilized normality within an objective formulation for anomaly mining and provided solutions to maximize
it, which automatically identify the latent focus attributes
as well as their respective weights. Our formulation yields
a scalable optimization that is only quadratic w.r.t. (often
small) neighborhood size and linear in attribute size. Overall, normality is unique in its (i) exoneration of crossedges, and (ii) automatic inference of focus attributes undera scalable convex optimization.
Experiments on real-world graphs demonstrate the utility of our measure in ranking neighborhoods by quality,
where we outperform well-established measures and methods. Normality also provides a powerful tool for studying
the correlation between structure and attributes for graphs.
Our work enables a number of future directions, including
utilizing normality for community detection at large andfor user profiling, i.e., recovering missing node attributes.

References[1] L. Akoglu, M. McGlohon, and C. Faloutsos. Oddball: Spotting anomalies in weighted graphs. In PAKDD, 2010.
[2] L. Akoglu, H. Tong, and D. Koutra. Graph-based anomaly
detection and description: A survey. DAMI, 28(4), 2014.
[3] 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.
[4] R. Andersen, F. Chung, and K. Lang. Local graph partitioning
using pagerank vectors. In FOCS, 2006.
[5] M. Charikar. Greedy approximation algorithms for finding
dense components in a graph. In APPROX, 2000.
[6] G. W. Flake, S. Lawrence, and C. L. Giles. Efficient identification of web communities. In KDD, 2000.
[7] S. Fortunato. Community detection in graphs. Physics
Reports, 486(3):75–174, 2010.
[8] E. Galbrun, A. Gionis, and N. Tatti. Overlapping community
detection in labeled graphs. DAMI, 28(5), 2014.
[9] D. F. Gleich and C. Seshadhri. Vertex neighborhoods, low
conductance cuts, and good seeds for local community methods. In KDD, pages 597–605, 2012.
[10] S. Gunnemann, I. Farber, S. Raubach, and T. Seidl. Spectralsubspace clustering for graphs with feature vectors. In ICDM,
pages 231–240, 2013.
[11] M. Gupta, A. Mallya, S. Roy, J. H. D. Cho, and J. Han. Local
learning for mining outlier subgraphs from network datasets.
In SIAM SDM, pages 73–81, 2014.
[12] J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney.
Statistical properties of community structure in large social
and information networks. In WWW, pages 695–704, 2008.
[13] J. J. McAuley and J. Leskovec. Discovering social circles in
ego networks. TKDD, 8(1):4, 2014.
[14] M. E. J. Newman. Assortative mixing in networks. PhysicalReview Letters, 89(20), 2002.
[15] M. E. J. Newman. Modularity and community structure in
networks. PNAS, 103(23):8577–8582, 2006.
[16] B. Perozzi, L. Akoglu, P. Iglesias Sánchez, and E. Müller.
Focused clustering and outlier detection in large attributedgraphs. In KDD, pages 1346–1355, 2014.
[17] C. E. Tsourakakis, F. Bonchi, A. Gionis, F. Gullo, and M. A.
Tsiarli. Denser than the densest subgraph: extracting optimal
quasi-cliques with quality guarantees. In KDD, 2013.