April 30, 2015
SDM15

MLCB

Significant Subgraph Mining
with Multiple Testing Correction
Mahito Sugiyama (Osaka University, JST PRESTO)
Joint work with Felipe Llinares López1 , Niklas Kasenburg2 ,Karsten Borgwardt1 (1 ETH Zürich, 2 Univ. Copenhagen)
1/21

Summary• Problem: Given a collection of graphs with class labels,
find all subgraphs whose occurrences aresignificantly enriched in a particular class– A central step for deep understanding• Difficulty: The number of subgraphs is massive(often more than a billion!)– Computationally expensive– Need of multiple testing correction
to control false positive rate

• Solution: Only examining testable subgraphs– The number of candidate subgraphs dramatically reduced– Rigorous multiple testing correction
2/21

Find Associated Subgraphs

ActiveInactive

3/21

Find Associated Subgraphs

ActiveInactive

3/21

Find Associated Subgraphs

ActiveInactive

3/21

Find Associated Subgraphs

ActiveInactive

3/21

Multiple Testing

Occur. Non-occur. Total
Active4
Inactive 00444

Total

484

Fisher’s exact test: P value = 0.029

4/21

Multiple Testing

Occur. Non-occur. Total
Active31Total
Occur. Non-occur.
Inactive 04Active4043 454
InactiveTotal
0448Total Fisher’s
4 exact4test: P value
8 = 0.143
Fisher’s exact test: P value = 0.029

4/21

Multiple Testing

Occur. Non-occur. Total
Active04Total
4Occur. Non-occur.
Inactive 314Active
31Total
4Occur. Non-occur.
3 4548InactiveTotal
0Active404
3 4 exact5test:
8 = 0.143
InactiveTotal
0 Fisher’s
4 P value
Total Fisher’s
4 exact4test: P value
8 = 0.143
Fisher’s exact test: P value = 0.029

4/21

Multiple Testing

Occur. Non-occur. Total
Active1
Inactive 03444Total

781

Fisher’s exact test: P value = 1Occur. Non-occur. Total
Active04Total
4Occur. Non-occur.
Inactive 3
14
Active31Total
4Occur. Non-occur.
3 4548InactiveTotal
0
Active404
3 4 exact5test:
8 = 0.143
InactiveTotal
0 Fisher’s
4 P value
Total Fisher’s
4 exact4test: P value
8 = 0.143
Fisher’s exact test: P value = 0.029

4/21

Multiple Testing

Occur. Non-occur. Total
Active1
Inactive 03444Total

781Task: Detect allsignificant subgraphs

Fisher’s exact test: P value = 1Occur. Non-occur. Total
Active04Total
4Occur. Non-occur.
Inactive 3
14Active
31Total
4Occur. Non-occur.
3 4548InactiveTotal
0Active404
3 4 exact5test:
8 = 0.143
InactiveTotal
0 Fisher’s
4 P value

massive subgraphs!

Total Fisher’s
4 exact4test: P value
8 = 0.143
Fisher’s exact test: P value = 0.029

4/21

Multiple Testing Correction• If we test m subgraphs, αm subgraphs are false positives– α : Significance level (predetermined by the user)• FWER: Probability of having more than one false positives
among all subgraphs– FWER = Pr(FP > 0)
◦ FP: Number of false positives• To achieve FWER = α , change the significance levelfor each test from α to δ– δ : corrected significance level– δ≤α∗◦ Bonferroni correction is popular: δBon = α/m
5/21Counting the Frequency of Subgraphs
Frequencyf() =76/21

Counting the Frequency of Subgraphs
Frequencyf() =67/21

The Minimum P Value• The minimum achievable P value
is determined from the frequency f (H) of a subgraph H:′nn+nPmin = ()/()f (H)
f (H)
Occ.

Non-occ.

Total

Activef(H)n – f(H)nInactive

0n’

Total

f(H)

n’
(n – f(H))+ n’

Most biased case (f(H) < n)n + n’

Probability q(X)0.3
MinimumP value

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

8/21Testability• The minimum achievable P value
is determined from the frequency f (H) of a subgraph H:′nn+nPmin = ()/()f (H)f (H)• Tarone (1990) pointed out (and Terada et al. (2013) revisited):
For a hypothesis H, if its minimum P value is larger than
the significance threshold, this is untestable andwe can ignore it– Untestable hypotheses (subgraphs) do not increase the FWER
– The Bonferroni factor reduces to the number of testablehypotheses
9/21

Finding the Optimal Correction Factor• m(k): # of subgraphs whose minimum P values < α/k– k : the correction factor, α/k : the corrected significance level• For each k , FWER is controlled as (Tarone 1990):
α m(k)
αFWER ≤ m(k) =kk• Our task is to optimize k :∗k = argmax m(k) s.t. m(k) ≤ kk– Enumerate testable subgraphs whose min. P values < α/k ∗∗δBon = α/(# of all subgraphs)∗δTar = α/(# of testable subgraphs)

10/21

Subgraphs Are Testable Iff Frequent• Our task:∗k = argmax m(k)s.t. m(k) ≤ kk

– m(k) = # of subgraphs whose minimum P values < α/k

11/21

Subgraphs Are Testable Iff Frequent• Our task:∗k = argmax m(k)s.t. m(k) ≤ kk⇓∗′σ = argmax m (σ)σ′

s.t. m (σ) ≤ α/ψ(σ)– m(k) = # of subgraphs whose minimum P values < α/k– m′ (σ): # of subgraphs whose frequency ≥ σ◦ # of “frequent subgraphs”′)– ψ(σ): the minimum P value at σ , ψ(σ) = (σn ) / (n+nσ11/21Subgraphs Are Testable Iff Frequent• Our task:∗k = argmax m(k)s.t. m(k) ≤ kk⇓∗′σ = argmax m (σ)σ′s.t. m (σ) ≤ α/ψ(σ)– m(k) = # of subgraphs whose minimum P values < α/k– m′ (σ): # of subgraphs whose frequency ≥ σ◦ # of “frequent subgraphs”′)– ψ(σ): the minimum P value at σ , ψ(σ) = (σn ) / (n+nσTestable subgraphs = Frequent subgraphs
11/21

How to Use Subgraph Mining# of subgraphs

Frequency

12/21

Decremental Search (LAMP)# of subgraphs

Frequency

Terminate if # of subgraphs is larger than α / (Pmin at σ)

Decremental
search13/21

Incremental Search# of subgraphs

Frequency
Terminate if # of subgraphs detected so far exceeds α / (Pmin at σ)
Incremental
search14/21

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.59
715.66
62.72
41.05
48.52

181
285748
462
482
239

181
66
14267
468
478
255

15/21

Correction Factor
Correction factor

PTC(MR)
106

107
105

104

103

102
5Correction factor

MUTAG

109
107
105
103

1015 Limitless
NCI1
108
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

16/21

Number of significant
subgraphs

Number of Significant Subgraphs
PTC(MR)

88×10466×10444×10422×104005

Number of significant
subgraphs

MUTAG

2×107

1.5×107107
5×106
01015 Limitless
NCI1
106
8×105
6×105
4×105
2×105
05D&D

8×104
7×104
6×104
5×104
4×104
3×104
2×104
1015 Limitless
NCI167251015 Limitless
NCI220

1Bonferroni
Testable

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

17/21

Running Time (second)

Running time (s)Running time (s)PTC(MR)

MUTAG

D&D

105105105103103

103

101010

10–1

10–1
15 Limitless

10–11015 Limitless
NCI167510NCI15105

105105103103

103

51015 Limitless
NCI220Brute-force
Decremental 10
Incremental––10 110 1
10–1
51015 Limitless
51015 Limitless
51015Max. size of subgraph nodes Max. size of subgraph nodes Max. size of subgraphnodes
Limitless
101018/21

Running Time Summary• RMSD (root mean square deviation) of running time (seconds)
to the best (fastest) running time on all datasets
Brute-force
6.994 × 10

4Decremental (LAMP)
2.410 × 104

Incremental
1.230 × 10

2

• Incremental search is the fastest– More than two orders of magnitude faster than brute-force– Much faster than decremental (LAMP) as the final minimum
support is usually small (∼20)

19/21

Final Minimum Frequencies

DatasetMaximum size of subgraph nodes
57
9 11 13 15 Limitless

PTC(MR)
MUTAG
D&D
NCI1
NCI167
NCI220

98
20
17
7
10

10
1022
20
8
11

11
11
22
22
9
13

11
12
22
25
10
14

11
14
22
27
11
15

11
—
22
29
—
1611—
22—
—
18n181125691
2104
9615
290

20/21

Conclusion• We achieved to enumerate all significant subgraphs– The first work that considers multiple testing correction ingraph mining• Efficient and more powerful (less false negatives)using testability and frequent subgraph mining• Pattern mining, a classical yet central topic in data mining,can be enriched by introducing statistical assessment– Can be applied in scientific fields such as biology

21/21

Appendix

A-1/A-16

Papers about Testability• Tarone, R.E.:
A modified Bonferroni method for discrete data
Biometrics (1990)• Terada, A., Okada-Hatakeyama, M., Tsuda, K., Sese, J.:
Statistical significance of combinatorial regulations,
Proc. Natl. Acad. Sci. USA (2013).
• Minato, S., Uno, T., Tsuda, K., Terada, A., Sese, J.:
Fast Statistical Assessment for Combinatorial Hypotheses
Based on Frequent Itemset Mining
ECML PKDD 2014
• Sugiyama, M., Llinares, F., Kasenburg, N., Borgwardt, K.:
Significant Subgraph Mining with Multiple Testing Correction,
SIAM SDM 2015 (http://arxiv.org/abs/1407.0316)– Code: http://git.io/N126
A-2/A-16

Hypothesis Test for Each Subgraph
Alternative hypothesis Null hypothesis
is trueis true
DeclaredsignificantTrue Positive

False Positive(Type I Error)

Declared
non-significant

False Negative(Type II Error)

True Negative

Null hypothesis:

The occurence of the subgraph isindependent from the activity
Alternative hypothesis: The occurence of the subgraph isassociated with the activity

A-3/A-16

Testing the Independence of Subgraph• Given two sets of graphs G and G ′– ∣G ∣ = n , ∣G ′ ∣ = n ′ ( n ≤ n ′ )′• The P value of each subgraph H ⊑ G with G ∈ G ∪ G isdetermined by the Fisher’s exact test

TotalOcc.

Non-occ.

Total

xn–x

nx’

n’ – x’n’x + x’

(n – x)+ (n’ – x’)n + n’

1.0x/n?

x’ / n’0

A-4/A-16

Fisher’s Exact Test• The probability q(x) of obtaining x and x ′ is given by thehypergeometric distribution:′′n+nn nq(x) = ( x )( x ′ )/( x + x ′ )

Total

Occ.

Non-occ.

Total

x

n–x

nx’

n’ – x’n’x + x’(n – x)+ (n’ – x’)n + n’

Probability q(x)0.3

P value0xmin= max{0, x + x’ - n’}

xxmax= min{x + x’, n}A-5/A-16

Testable Subgraphs
Frequency is large
Minimum P value

A-6/A-16

Testable Subgraphs
k = 10, m(10) = 1 (this k is the Bonferroni factor)

Frequency is large

Minimum P value

Significance levelα / 10

Untestable subgraphs

Testable subgraphs

A-7/A-16

Testable Subgraphs
k = 9,

Frequency is largem(9) = 4

Minimum P value

Significance level

α/9

Untestable subgraphs

Testable subgraphs

A-8/A-16

Testable Subgraphs
k = 8,m(8) = 6

Frequency is large

Minimum P value
Significance level

α/8

Untestable subgraphs

Testable subgraphs

A-9/A-16

Testable Subgraphs
k = 7,m(7) = 8

Frequency is large

Minimum P value
Significance level

α/7

Untestable subgraphs

Testable subgraphs

A-10/A-16

Testable Subgraphs
k = 8,m(8) = 6

The reduced Bonferroni factor

Frequency is large

Minimum P value
Significance level

α/8

Untestable subgraphs

Testable subgraphs
Compute the (exact) P values of these
testable subgraphs

A-11/A-16

Effective Number of Tests• Many subgraphs are expected to be highly correlated
due to subgraph-supergraph relationships• Use the effective number of tests to exploit thedependence between subgraphs and increase the power• In the Šidák correction, the significance level′1/m

α = 1 − (1 − α)for m independent tests• Only meff < m tests are effective for controlling the FWERlog(1 − α)meff ∶=log(1 − α ′ )A-12/A-16

Estimation of Effective Number• We directly estimate the level α ′by random permutations of class labels– Optimal estimation of meff in theory– The drawback is the high computational cost O(mh)◦ m: # of subgraphs, h : # of iterations• Overcome by considering only testable subgraphs– We apply the above permutation-based estimation to only
testable subgraphs– The complexity is O(τ(m)h) (τ(m): # of testable subgraphs)• Moskvina, V. and Schmidt, K. M. On multiple-testing correction in
genome-wide association studies. Genetic epidemiology,32(6):567–573, 2008.

A-13/A-16

Detected Significant Subgraphs

PTC (MR)(carcinogenicity)

NCI 220(anti-cancer activity)

A-14/A-16

Frequent Subgraph Miners• [AGM] Inokuchi, A. and Washio, T. and Motoda, H.:
An Apriori-Based Algorithm for Mining Frequent
Substructures from Graph Data, PKDD 2000
• [gSpan] Yan, X. and Han, J.:
gSpan: Graph-based substructure pattern mining,
ICDM 2002• [GASTON] Nijssen, S. and Kok, J. N.:
A Quickstart in Frequent Structure Mining Can Make aDifference, KDD 2004
• (comparison) Wörlein, M. and Meinl, T. and Fischer, I. andPhilippsen, M.
A Quantitative Comparison of the Subgraph Miners MoFa,
gSpan, FFSM, and Gaston, PKDD 2005
– We used GASTON as it is the fastest
A-15/A-16

Related work: LAMP version 2• Minato et al. proposed a faster version of LAMP
in itemset mining– Minato, S., Uno, T., Tsuda, K., Terada, A. and Sese, J.:
Fast Statistical Assessment for Combinatorial Hypotheses
Based on Frequent Itemset Mining
ECML PKDD 2014

• The idea is almost the same with our incremental search– Start from σ = 1, every time an item is added,
the condition ∣I (σ)∣ ≤ α/ψ(σ) is checked◦ I (σ): the set of itemsets found so far with the frequency ≥ σ– As soon as ∣I (σ)∣ > α/ψ(σ), the current σ is too large and we
decrement it
A-16/A-16