SCAN-XP:

Parallel Structural Graph Clustering Algorithm
on Intel Xeon Phi Coprocessors

Hiroaki Shiokawa
Database Group, Division of Computational Informatics,CCS, University of Tsukuba

2017 CCS-EPCC Workshop

Graph and its applications• Graph• Node: data entities• Edge: relationships among entities
edgenode• Key applications

Roads and Trajectories

Web and SNS

Protein-protein interactions2

3

Structural Graph Clustering: SCAN

• SCAN [Xu+,2007]• SCAN identifies clusters, hubs and outliers based on density
between two nodes
21034

HUB:
Non-cluster nodes
that bridge multipleclusters
6814115137Outlier
Non member ofclusters and hubs

91012Cluster：
Densely connected
node setLarge-scale Graphs are now available

1.49 Billion Users/Month

500 Million Tweets/ Day
320 Million Users/Month

How we can efficiently find clusters
on a Large-scale Graphs?

45Our Contributions• Proposed method SCAN-XP• Scaling SCAN using Intel Xeon Phi Coprocessor• We examined its efficiency on COMA and OakforestPACS

SCAN-XPBaseline: SCAN
6

Clustering procedure of SCAN
• Cluster = Cores and its densely connected neighbors• Core: Nodes that have enough neighbors with denseconnections
Structural similarity 𝜎 𝑣, 𝑤

𝜎 𝑣, 𝑤 =Γ(𝑣) ∩ Γ(𝑤)
Γ(𝑣) Γ(𝑤)• By setting density threshold 𝝐 and minimum cluster
size 𝝁, SCAN specifies the clusters.

7

Example of SCAN (𝜀 = 0.7, 𝜇 = 2)
Step 1
Core detection
0.87

362

540corenon-core18

Example of SCAN (𝜀 = 0.7, 𝜇 = 2)
Step 2Cluster construction

Step 1
Core detection
0.87

36540corenon-core

0.87

32612

54019

Example of SCAN (𝜀 = 0.7, 𝜇 = 2)0.87360corenon-core

0.87

3254

Step 3
Hub・Outlier detection

Step 2Cluster construction

Step 1Core detection

654

1Outlier

206cluster

v

0.87

30Outlierclustercluster

2541

Hub

10v

1

Proposed Method:SCAN-XP11

12

Proposed method: SCAN-XP• Core detection and Cluster construction are bottlenecks• They require exhaustive computations…
Step 1: Core detection
0.87

36200.87

354

Step 2: Cluster construction

6541• Proposed method: SCAN-XP

201• Step1: Thread-based & SIMD-based parallelization• Step2: Thread-based parallelization using Union-Find Tree

13

Step1: Parallel Core Detection• Thread-based parallelization is trivial• The structural similarity computation 𝜎(𝑢, 𝑤) is
independent among edges J
0.87

3• Set Intersection in 𝜎(𝑢, 𝑤)
𝜎 𝑣, 𝑤 =654

Γ(𝑣) ∩ Γ(𝑤)
Γ(𝑣) Γ(𝑤)Parallelized Set Intersection is not trivial L

201

14

SIMD-based Sort Merge Join (SMJ)• SMJ is a lightweight set intersection algorithm
Γ 𝑣 = 3, 4, 10, 13, 20, … , Γ 𝑤 = {2, 3, 11, 13, 43, … }Γ 𝑣 ∩Γ 𝑤=?

Adjacent nodes of node v
3Register 1

410132033

44Equals
Register 22233
112
13343…

end

Adjacent nodes of node v
3

Counting
commonnodeend

Adjacent nodes of node w

101320…

end

compare (4>3)
advance pointer
2…

43111343…

Adjacent nodes of node w

endStep2: Parallel Cluster Construction

15• SCAN needs to expand a cluster from a set ofcores step by step L• Parallel cluster construction is not trivial• Parallel Union-Find Tree (UFT) construction• Assign threads to nodes, and construct UFT in parallel
Cluster = {2, 3, 5}

Union(3,4)

2235

30

CAS

514

Evaluations
16

17

Experimental settings• Real-world Datasets
Datasetcom-youtube
web-BerkStan
soc-Pokec
com-LiveJournal
soc-LiveJournal1
com-Orkut
webbase2001# of nodes
1,134,890
685,230
1,632,803
3,997,962
4,846,609
3,072,441
115,554,441• Experimental environment• CPU：Processor Xeon E5 1620
• KNC
：Intel Xeon Phi 7110P• KNL：Processor Xeon Phi 7250

# of edges
2,987,624
6,649,470
22,301,964
34,681,189
42,851,237
117,185,083
854,809,761

18

Execution time
SCAN-XP is up to 100 times faster than SCAN

small

N/A

# of edges

betterExecution time (ms, logarithmic)

36
secondslargePerformance comparison(CPU,KNC,KNL)

19

SCAN-XP

100000100000

10000
1000
100

CPU

KNC

KNL

101

Execution time (ms)

Execution time (ms)SCAN-XP

10000
1000
100

CPU

KNC

KNL

101

soc-LiveJournal1

com-Orkut

SCAN (Xeon,1)

SCAN-XP(Xeon,1)

SCAN-XP(Xeon,4)

SCAN-XP(Xeon,8)

SCAN-XP(KNC,57)

SCAN-XP(KNC,114)

SCAN-XP(KNC,171)

SCAN-XP(KNC,228)

SCAN-XP(KNL,68)

SCAN-XP(KNL,136)

SCAN-XP(KNL,204)

SCAN-XP(KNL,272)

Conclusion

20• Summary• We proposed SCAN-XP• SCAN-XP is 100 times faster than SCAN

T. Takahashi, H. Shiokawa, H. Kitagawa,“SCAN-XP: Parallel Structural Graph Clustering on Intel Xeon Phi Coprocessors,”
In Proc. SIGMOD 2017 Workshops on Network Data Analysis, 2017

• Future works• Employ pruning approaches into SCAN-XP• Exploit multiple Xeon Phi for significantly large graphs