June 20–23, 2017
MCP 2017

Significant Pattern Mining
on Graphs

Mahito Sugiyama (NII, PRESTO)

Literature• Sugiyama, M., Llinares-López, F., Kasenburg, N.,
Borgwardt, K.:
Significant Subgraph Mining with Multiple Testing
Correction,
SIAM SDM 2015
• Llinares-López, F., Sugiyama, M., Papaxanthos, L.,
Borgwardt, K.:
Fast and Memory-Efficient Significant Pattern Mining
via Permutation Testing,
ACM SIGKDD 2015

1/22

Subgraph Mining• Find interesting subgraphs from graph databases
Database

2/22

Subgraph Mining• Find interesting subgraphs from graph databases
Database
Subgraph

Support: 4

Support: 2

2/22

Discriminative Subgraph Mining• Find discriminative subgraphs from supervised data
(e.g. Drug discovery)

Negative

Positive

Database

3/22

Discriminative Subgraph Mining• Find discriminative subgraphs from supervised data
(e.g. Drug discovery)

Positive

Database
Discriminative
Subgraph

Negative

Support: (4, 0)

Support: (0, 2)

3/22

Challenges and Solutions• In discriminative subgraph mining:
1. How to measure the discriminability of subgraphs?
2. How to enumerate all discriminative subgraphs?

4/22

Challenges and Solutions• In discriminative subgraph mining:
1. How to measure the discriminability of subgraphs?
2. How to enumerate all discriminative subgraphs?
• Answer to 1:– Compute the p-value via statistical hypothesis testing– Discriminative subgraph ⟺(Statistically) Significant subgraph• Answer to 2:– Integrate evaluation of discriminability andenumeration of subgraphs

4/22

Computing p-value of Subgraph• Given positive and negative sets of graphs G , G ′– ∣G ∣ = n, ∣G ′ ∣ = n′ (n ≤ n′ )• The p-value of each subgraph H is determined by
the Fisher’s exact test
– x = ∣{ G ∈ G ∣ H ⊑ G }∣𝒢 (Pos.)

Occ.

Non-occ.

Total

xn–xnn’ – x’𝒢’ (Neg.) x’x + x’ (n – x)
Total
=σ+ (n’ – x’)
Supportn’?

1.0x/nx’ / n’n + n’0𝒢
Pos.

𝒢’Neg.

5/22

Multiple Testing

Occ. Non-occ. Total
Positive 4
Negative 20244Total

286

Fisher’s exact test: p-value = 0.429

6/22

Multiple Testing

Occ. Non-occ. Total
PositiveOcc. 3Non-occ.1 Total 4Negative 1
Positive40 3 4 4Total 2 4 2 4 4 8
Negative
TotalFisher’s6 exact test:
2 p-value
8 = 0.486
Fisher’s exact test: p-value = 0.429

6/22

Multiple Testing

Occ. Non-occ. Total
Positive
Occ. 2Non-occ.2 Total 4
Negative 224
Positive
Occ. 3Non-occ.1 Total 4Total 1 4 3 4 4 8
Negative
Positive 404

TotalFisher’s
4 p-value
Negative
2 4 exact
2 test:
4 8 = 1.0
TotalFisher’s6 exact test:
2 p-value8 = 0.486
Fisher’s exact test: p-value = 0.429

6/22

Multiple Testing

Occ. Non-occ. Total
Positive

404

Negative 314Total

487

Fisher’s exact test: p-value = 1.0
Non-occ.
Occ.
Total
Positive
Occ. 2Non-occ.2 Total 4
Negative 224
Positive
Occ. 3Non-occ.1 Total 4Total 1 4 3 4 4 8
Negative
Positive 404

TotalFisher’s
4 p-value
Negative
2 4 exact
2 test:
4 8 = 1.0
TotalFisher’s6 exact test:
2 p-value
8 = 0.486
Fisher’s exact test: p-value = 0.429

6/22

Multiple Testing

Occ. Non-occ. Total
Positive

404

Negative 314Total

487

Task: Enumerate allsignificant subgraphs
while controlling theFWER

Fisher’s exact test: p-value = 1.0
Non-occ.
Occ.
Total
Positive
Occ. 2Non-occ.2 Total 4
Negative 224
Positive
Occ. 3Non-occ.1 Total 4Total 1 4 3 4 4 8
Negative
Positive 404

TotalFisher’s
4 p-value
Negative
2 4 exact
2 test:
4 8 = 1.0
TotalFisher’s6 exact test:2 p-value
8 = 0.486
Fisher’s exact test: p-value = 0.429

Massive number of(infinitely many) subgraphs(Combinatorial explosion!)
6/22

Minimum Achievable p-value Ψ(σ)• Consider the minimum achievable p-value Ψ(σ) ofa subgraph H for its support σ = ∣{ X ∈ X ∪ X ′ ∣ H ⊆ X }∣– Ψ(σ) = min{ p(x) ∣ x min ≤ x ≤ x max }′◦ x min = max{0, σ − n }, x max = min{σ, n}𝒢 (Pos.)Occ.

Non-occ.

Totalxn–x

nn’ – x’𝒢’ (Neg.) x’x + x’ (n – x)
Total
=σ+ (n’ – x’)
Supportn’n + n’

Probability q(X)0.3
Minimumachievablep-value

0xmin= max{0, f(H) – n’}xxmax= min{f(H), n}

7/22

Computing Ψ(σ)• Consider the minimum achievable p-value Ψ(σ) ofa subgraph H for its support σ = ∣{ X ∈ X ∪ X ′ ∣ H ⊆ X }∣′nn+nΨ(σ) = (σ ) / ( σ )Occ.

Non-occ.

Total

σn–σn𝒢’ (Neg.) 0n’n’σ(n – σ)+ n’n + n’

𝒢 (Pos.)
Total

Most biased case (σ < n)Probability q(X)0.3
Minimumachievablep-value

0xmin= max{0, f(H) – n’}xxmax= min{f(H), n}

8/22

Testability• Consider the minimum achievable p-value Ψ(σ) ofa subgraph H for its support σ = ∣{ X ∈ X ∪ X ′ ∣ H ⊆ X }∣′nn+nΨ(σ) = (σ ) / ( σ )• Tarone (1990) pointed out (and Terada et al. (2013) revisited):
For a subgraph H with its support σ , if the minimum
achievable p-value Ψ(σ) is larger than the significancethreshold, this is untestable and we can ignore it– Significance threshold = α / [# testable subgraphs]– Untestable subgraphs can never be significant
9/22

Number of subgraphs
whose support is σ

Finding Testable Subgraphs

Support σΨ(σ) decreases
10/22

Number of subgraphs
whose support is σ

Finding Testable Subgraphs<α?

Ψ(σ1) ·Testable
subgraphs?

σ1

Support σΨ(σ) decreases
10/22

Number of subgraphs
whose support is σ

Finding Testable Subgraphs<α?

Ψ(σ2) ·Testable
subgraphs?

σ2Support σΨ(σ) decreases
10/22

Number of subgraphs
whose support is σ

Finding Testable Subgraphs

Ψ(σ3) ·<α?

Testablesubgraphs?

σ3

Support σΨ(σ) decreases
10/22

Number of subgraphs
whose support is σ

How to Find Testable Subgraphs?

Ψ(σ3) ·<α?

TestableComputing this area issubgraphs? possible by “frequentsubgraph mining”

σ3

Support σΨ(σ) decreases
11/22

Datasets

DatasetSize#positiveavg.∣V ∣avg.∣E∣max∣V ∣max∣E∣

PTC (MR)
MUTAG
D&D
NCI1
NCI167
NCI220

584
188
1178
4208
80581
900

181
125
691
2104
9615
290

31.96
17.93
284.32
60.12
39.70
46.87

32.71
39.59715.66
62.72
41.05
48.52

181
285748462482
239

18166
14267
468
478
255

12/22

# Testable Subgraphs
Correction factor

PTC(MR)
107

106

105

104

103

102
5Correction factor

MUTAG

109

1015 Limitless
NCI1
108

107
105
103

107
106
105
104

D&D

109
108
107
106
105

51015 Limitless
NCI16710951015 Limitless
NCI220107
Bonferroni 105
Testable
103

51015
51015 Limitless
51015 Limitless
Max. size of subgraph nodes Max. size of subgraph nodes Max. size of subgraph nodes

from [Sugiyama et al. SDM2015]13/22

FWER Is Still Too Low!

Empirical FWER

Empirical FWER

PTC(MR)

MUTAG

0.03

0.015

0.02

0.010

0.01

0.005

000.0351015 Limitless
NCI1

5D&D

0.05
0.04
0.03
0.02
0.01
01015 Limitless
NCI167

0.04

0.04

0.03

0.01

0.01

0.03
Bonferroni
0.02
Testable
0.01

00

00.02

0.02

51015 Limitless
NCI22051015 Limitless
51015 Limitless
51015 Limitless
Max. size of subgraph nodes Max. size of subgraph nodes Max. size of subgraph nodes

from [Sugiyama et al. SDM2015]

14/22

Take Dependencies into Account• Problem: Dependencies between subgraphs are notconsidered• Solution: Permutation test
– Repeat random permutation of class labels (103 ∼ 104 times)– Get the null distribution of p-values– The optimal correction factor can be obtained

15/22

Westfall-Young Permutation
1. Randomly permute class labels
2. Compute p-values for all subgraphs
using the permuted class labels
3. Find the minimum p-value p min among them
– Number of false positives > 0 ⟺ p min < δh
4. Repeat steps 1 to 3 h times and obtain p1min , p2min , . . . , p mini≤ δ }∣ / h– FWER(δ) ≈ ∣{ i ∶ p min

5. δ

∗

12
his the α -quantile of p min , p min , . . . , p min

16/22

Westfall-Young Permutation

p12
p22
p32

p13
p23
p33

...
...
...

p1m
p2m
p3m

...

...

...

...

Permutation
...

hp11
p21
p31

...

12
3

Sort andfind α-quantileα
p1min

...

Subgraphs (Hypotheses)
H1
H2
H3 ...
Hm

ph1

ph2

ph3

...

phm

phmin

p2min
p3min

17/22

Using Support for Estimating FWER

p22
p32

p23
p33

...
...

p2m
p3m

p2min
p3min

...

...

...

...

...

Permutation
...

hp21
p31

...

123

Subgraphs (Hypotheses) Support
H1H2H3 ...
HmSort andσ1 ≤ σ2 ≤ σ3 ≤ ... ≤ σmfind α-quantile
αp11 p12 p13 ... p1m
p1min

ph1

ph2

ph3...

phmphmin18/22

Estimating FWER

p12
p22
p32

p13
p23
p33

...
...
...

p1m
p2m
p3m

p1min
p2min
p3min

...

...

...

...

Permutation...

hp11p21
p31...

123...

Subgraphs (Hypotheses) Support
H1H2
H3 ...
Hm
σσ1 ≤ σ2 ≤ σ3 ≤ ... ≤ σm

ph1

ph2

ph3...

phmphminΨ(σ)

Estimator of FWER = |{i : pimin ≤ Ψ(σ)}| / h
19/22

“Westfall-Young light” [Llinares-López et al. KDD’15]
i• Precompute h permuted labels; σ ← 1; p min←1• Westfall-Young light does the following whenevera miner (like Gaston) finds a new frequent subgraph H:– for i ← 1 to h do:i◦ p ← the p-value of H for i th permutationiii◦ p min ← min{p min , p }i≤ Ψ(σ) }∣ / h// current FWER estimate– FWER ← ∣{ i ∶ p min– while FWER > α do:◦ σ ← σ+1// σ is the minimum support for miningi◦ FWER ← ∣{ i ∶ p min ≤ Ψ(σ) }∣ / h– Go children of H
20/22

FWER in Subgraph Mining
ENZYMES

NCI220from [Llinares-López et al. KDD2015]

21/22

Conclusion• Significant subgraph mining is introduced– Find statistically significant subgraphs
while controlling the FWER
– pattern mining (data mining) + MCP (statistics)◦ Sugiyama, M., Llinares-López, F., Kasenburg, N., Borgwardt, K.:
Significant Subgraph Mining with Multiple Testing
Correction, SIAM SDM 2015
◦ Llinares-López, F., Sugiyama, M., Papaxanthos, L., Borgwardt, K.:
Fast and Memory-Efficient Significant Pattern Mining via
Permutation Testing, ACM SIGKDD 2015

• Ongoing projects:– Find significant subgraphs on a single massive graph– Find significant subtrees on a tree

22/22