Focused Clustering and Outlier Detectionin Large Attributed Graphs
ACM SIG-KDD
August 26, 2014

Bryan Perozzi, Leman Akoglu
Stony Brook University

Patricia Iglesias Sánchez*, Emmanuel Müller*†*Karlsruhe Institute of Technology†University of Antwerp

Attributed Graphs
 Attributed graph:each node has
1+ properties
 Examples:Age School Relationship Status


Bryan Perozzi

Focused Clustering and Outlier Detection in Large Attributed Graphs

2

Focused Mining of Attributed Graphs
 Numerous attributes (ex: Facebook profiles)

 Many irrelevant for most queriesEx: When trying to sell mortgages
 Useful: Income, Credit Score, Employer
 Not Useful: Hair Color, # Apps Installed Ex: When trying to sell make up
 Useful: Hair Color, Skin Tone, Gender Not Useful: Shoe Size Focus FocusUsers have a Focus  Algorithms need a Focus too!
Bryan Perozzi

Focused Clustering and Outlier Detection in Large Attributed Graphs3Adding Focus to Algorithms
 Users provide examples of the kind ofsimilarity they are interested in.
 We infer the similarity function that matters tothem.
!
examplesfocus

Taskuserinfer focus
attributes

Bryan Perozzi

Focused Clustering and Outlier Detection in Large Attributed Graphs4Outline Introduction

 New Problem:

Focused Clustering & Outliers Our Approach: FocusCO
 Evaluation
 Conclusion

Bryan Perozzi

Focused Clustering and Outlier Detection in Large Attributed Graphs

5Focused Clusters and Outliers: Problem
Given1) a graph w/ node attributes,2) exemplar nodes by the user

Infer attribute weights/relevance
Extract focused clusters:
1) dense in structure,2) coherent in “heavy” attributes(called the “focus”)
Detect focused outliers:*) nodes deviating in focus attribute values

Bryan Perozzi

Focused Clustering and Outlier Detection in Large Attributed Graphs

6

An ExampleUsers provide examples ofnodes they considersimilar.


Ex: ‘Yann LeCun’ and‘Foster Provost’

We learn a focus
Education Level Location
We extract clusterswhich agree with the focus

We detect outlierswhich don’t agree with focus

Bryan Perozzi

Focused Clustering and Outlier Detection in Large Attributed Graphs

7

Related Work
GraphClustering

METIS,Spectral✓

Parallel
Nibble,BigClam✓

CoPaM,GamerCODA✓✓

GOutRank,ConSubFocusCO
Bryan Perozzi✓

AttributedGraphs

AttributeUser
Subspace Preference✓✓✓✓✓✓✓

OutlierDetection

✓✓

✓

✓

Focused Clustering and Outlier Detection in Large Attributed Graphs

8FocusCO: sketch

1

2

examples4

detectfocusedclusters &outliers3…

…

age gender location
Bryan Perozzi

infer“focus”
attribute(s)Focused Clustering and Outlier Detection in Large Attributed Graphs

9Focus attribute inference
Input: Set of similar nodes, Cex
1. Construct a set of similar pairs, PS
Pair user
examplestogetherCex

2. Construct a set of dissimilar pairs, PD
Randomly samplepairs (u,v)

3. Learn a distance metric between PS and PD
Bryan Perozzi

Focused Clustering and Outlier Detection in Large Attributed Graphs

10Distance Metric Learning[Xing, et al 2002]

attributes

nodes

PS and PD intermixed

Feature Matrix

attributes

FocusedAttribute Vector
Bryan Perozzi

nodes
PS closer together
Focused Clustering and Outlier Detection in Large Attributed Graphs

11

FocusCO: sketch

12examples4

detectfocusedclusters &outliers3…

…

age gender location
Bryan Perozzi

infer“focus”
attribute(s)Focused Clustering and Outlier Detection in Large Attributed Graphs

12FocusCO: Cluster Extraction
 Local clustering algorithm
Not cluster whole graph Expands a cluster arounda starting set
 Two procedures:
1.

Finding good candidatesets to start at

2.

Growing clusters

Bryan Perozzi

Focused Clustering and Outlier Detection in Large Attributed Graphs

13Finding nodes to cluster around
1.) We reweigh the graph using the focus

2.) We keep only highly weighted edges3.) The connected components are our seeds

A seed set
Bryan Perozzi

Focused Clustering and Outlier Detection in Large Attributed Graphs

14

Growing a Focused Cluster
Cluster Member

1. Clustering objective: conductanceweighted by focus

2. At each step in cluster expansion:
2.1 - Examine boundary nodes
2.2 - Add node with best ∆2.3 - Record best structural node

Focused Outlier

Bryan Perozzi

3. Focused Outliers:
left out best structural nodes

Focused Clustering and Outlier Detection in Large Attributed Graphs

15Experiment set up
Synthetic and Real World Graphs
 Performance measures:
Cluster quality: NMI
 Outlier accuracy: precision, F1Compared to:
CODA [Gao+’10]
 METIS (no outlier detection) [Karypis+’98]Bryan Perozzi

Focused Clustering and Outlier Detection in Large Attributed Graphs

16

Focused clustering performance

9 clusters (3 focus1 + 3 focus2 +3 unfocused). 5 focus attributes.
Bryan Perozzi

Focused Clustering and Outlier Detection in Large Attributed Graphs

17Focused clustering performance

Bryan Perozzi

Focused Clustering and Outlier Detection in Large Attributed Graphs

18Outlier detection performance# deflated focus attributes increased (easier) from left to rightBryan Perozzi

Focused Clustering and Outlier Detection in Large Attributed Graphs

19

Disney: Amazon co-purchase graph

Images are Focused Outliers
Bryan Perozzi

Focused Clustering and Outlier Detection in Large Attributed Graphs

20

DBLP co-authorship graph
Focused Outlier
publishes in IR

Bryan Perozzi

Focused Clustering and Outlier Detection in Large Attributed Graphs

21

Political blogs citation graph

Focused Outlier did
not mention Waas.
Bryan Perozzi

Focused Clustering and Outlier Detection in Large Attributed Graphs

22Summary
A new graph mining paradigm
where the focus steers graph mining
according to user preference.
A new problem formulation
Focused Clustering & Outlier detection!
examplesuserfocus

Clustering

infer focus attributes

Thanks! Any questions?
Bryan Perozzi (bperozzi@cs.stonybrook.edu)
Bryan Perozzi

Focused Clustering and Outlier Detection in Large Attributed Graphs23