February 16, 2015
Tokyo Workshop on StatisticallySound Data Mining

Multiple Testing Correction
in Graph Mining
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/40

Binary dataGraphs

ID abcd efg hij
1 001100111 0
2 1101 10111 0
3 101100111 0
4 1100 10010 15 1101 10111 0

Pattern mining

Support:P value:{a, b, e} {d, g, h, i}

30.06

4323(Statistically) Significant patterns

0.010.02(P value < 0.05)0.07 0.02

The P value is crucial for scientific discovery!
2/40

Find Subgraphs

ActiveInactive

3/40

Find Subgraphs

ActiveInactive

4/40

Find Subgraphs

ActiveInactive

5/40

Find Subgraphs

ActiveInactive

6/40

Hypothesis Test for Each Subgraph
Alternative hypothesis Null hypothesis
is trueis true
Declaredsignificant

True 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

7/40

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

Total

Occ.

Non-occ.

Total

xn–x

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

1.0x/n?

x’ / n’08/40

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

xn–xnx’n’ – x’n’

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

Probability q(x)0.3

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

xxmax= min{x + x’, n}9/40

Multiple Testing
Task: Detect all
significant subgraphs
Occur. Non-occur. Total
Active1
Inactive 03444

Total

78

1

Fisher’s exact test: P value = 1Occur. 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

We need multiple
testing correction!
Otherwise, too many
false positives:
FWER = 1 – (1 – α)mm subgraphs

Problems:– m is massive– The significance level α / min Bonferroni correction
becomes too conservative

10/40

Counting the Frequency of Subgraphs

ActiveInactive

11/40

Counting the Frequency of Subgraphs

12/40

Counting the Frequency of Subgraphs
Frequencyf() =713/40

Counting the Frequency of Subgraphs
Frequencyf() =614/40

The Minimum P Value• The minimum achievable P value
for the frequency f (H) of a subgraph H is′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
Minimum
P value

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

15/40

Testability• The minimum achievable P value
for the frequency f (H) of a subgraph H is′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 smaller 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 testable
hypotheses
16/40

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:– Find the smallest k while controlling FWER ≤ α◦ Coincides with the “root” k rt of the function m(k) − k◦ m(k) ≤ k for all k ≥ k rt and m(k) > k for all k < k rt
– Enumerate testable subgraphs whose min. P values < α/k rt

17/40

Testable Subgraphs
Frequency is large
Minimum P value

18/40

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

19/40

Testable Subgraphs
k = 9,

Frequency is largem(9) = 4

Minimum P value

Significance level

α/9

Untestable subgraphs

Testable subgraphs

20/40

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

Frequency is large

Minimum P value
Significance level

α/8

Untestable subgraphs

Testable subgraphs

21/40

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

Frequency is large

Minimum P value
Significance level

α/7

Untestable subgraphs

Testable subgraphs

22/40

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

23/40

Subgraphs Are Testable Iff Frequent• Our task:
Find k such that(# of subgraphs whose minimum P values < α/k ) = k⇓

Find σ such that(# of subgraphs whose frequency ≥ σ ) = α/ψ(σ)
Testable subgraphs = Frequent subgraphs

24/40

Use Frequent Subgraph Mining• Testable subgraphs can be enumerated byfrequent subgraph mining algorithms• Proposition:
The set of testable subgraphs τ(H) coincides withthe set of frequent subgraphs with the threshold σrt s.t.
# of subgraphs with minfreq σrt − 1 > α/ψ(σrt − 1),# of subgraphs with minfreq σrt ≤ α/ψ(σrt ),– α/ψ(σ) shows the admissible number of subgraphs at σ′◦ ψ(σ) = (σn ) / (n+n) (Minimum P value at σ )σ◦ For k rt = α/ψ(σrt ), if ψ is monotonically decreasing, m(k rt ) =∣ { H ∈ H ∣ ψ(f (H)) ≤ ψ(σrt ) } ∣ = ∣ { H ∈ H ∣ f (H) ≥ σrt } ∣25/40

How to Use Subgraph Mining# of subgraphs

Frequency

26/40

Brute-Force Search (Bonferroni)# of subgraphs

Frequency
Freq. threshold is 1

Brute-force(Bonferroni method)27/40

Decremental Search (LAMP)# of subgraphs

Frequency

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

Decremental
search28/40

Incremental Search# of subgraphs

Frequency
Terminate if # of subgraphs detected so far exceeds α / ψ(σ)
Incremental
search29/40

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
28
5748
462
482
239

18166
14267
468478255

30/40

Correction Factor
Correction factor

PTC(MR)
106

107
105

104

103

102
5

Correction factor

MUTAG

109
107
105
103

1015 Limitless
NCI1108
107
106
105
104

D&D

109
108
107
106
105

51015 Limitless
NCI16710951015 Limitless
NCI220107
Bonferroni 105
Testable
1035101551015 Limitless
51015 Limitless
Max. size of subgraph nodes Max. size of subgraph nodes Max. size of subgraph nodes

31/40

Number of significant
subgraphs

Number of Significant Subgraphs
PTC(MR)

88×10466×10444×10422×104005

Number of significant
subgraphsMUTAG

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

32/40

Running Time (second)

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

MUTAG

D&D

105

105

105

103

103

103

10101010–1

10–1
15 Limitless

10–1
1015 Limitless
NCI167510NCI15105105105103103103

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

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 × 10

4

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
frequency is usually small (∼20)

34/40

Final Minimum Frequency

DatasetMaximum size of subgraph nodes
579 11 13 15 Limitless

PTC(MR)
MUTAG
D&D
NCI1
NCI167
NCI220

98
20
17
7
10

10
1022
20
8
11

11
1122
22
913

111222
25
10
14

11
14
22
27
11
15

11—
22
29
—
16

11—
22—
—
18n181
125
691
2104
9615
290

35/40

Detected Significant Subgraphs

PTC (MR)(carcinogenicity)

NCI 220(anti-cancer activity)

36/40

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

000

0.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

37/40

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 wedecrement it38/40

Conclusion• Significant subgraphs mining with multiple testingcorrection is achieved– The first work that considers multiple testing correction ingraph mining• Efficient and effective (less false negatives) usingtestability• Future work
– Increase the FWER with keeping ≤ α◦ Currently we ignore correlations between subgraphs

39/40

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 López, F., Kasenburg, N., Borgwardt, K.M.:
Significant Subgraph Mining with Multiple Testing Correction,
SIAM SDM 2015 (http://arxiv.org/abs/1407.0316)– Code: http://git.io/N12640/40