Supplementary Notes for
Significant Subgraph Mining with Multiple Testing Correction
Mahito Sugiyama∗†‡

Felipe Llinares López§

Niklas Kasenburg¶

Karsten M. Borgwardt§

A Additional Information about Datasets
are the full sets retrieved from the oﬃcial website3 .
The PTC (Predictive Toxicology Challenge) dataset1
contains data of 601 chemical compounds in total (in- Referencescluding training and test sets), which is originally de[1] Borgwardt, K.M., Ong, C.S., Schönauer, S., Vishsigned for a prediction challenge of carcinogenic eﬀects.
wanathan, S.V.N., Smola, A.J., Kriegel, H.P.: Protein
Graphs are classified according to their carcinogenicity
function prediction via graph kernels. Bioinformatics
assayed on rats and mice. We assume that graphs la21(suppl 1), i47–i56 (2005)
beled as CE, SE, or P as positive, and those of NE or N
[2] Debnath, A.K., Lopez de Compadre, R.L., Debnath,as negative, the same setting as in [4, 9]. The dataset isG., Shusterman, A.J., Hansch, C.: Structure-activity
divided into four overlapping subsets according to theirrelationship of mutagenic aromatic and heteroaromaticanimal models: male rats (MR), female rats (FR), malenitro compounds. correlation with molecular orbital enmice (MM), and female mice (FM). We used only MRergies and hydrophobicity. Journal of Medicinal Chemsince the properties of other datasets are similar.
istry 34(2), 786–797 (1991)
MUTAG [2] is a dataset of 188 mutagenic aromatic[3] Dobson, P.D., Doig, A.J.: Distinguishing enzyme strucand heteroaromatic nitro compounds, which are classitures from non-enzymes without alignments. Journal ofMolecular Biology 330(4), 771–783 (2003)fied into two classes of mutagenically active or inactive[4] Kong, X., Yu, P.S.: Semi-supervised feature selection
on the bacterium Salmonella typhimurium.
for graph classification. In: KDD. pp. 793–802 (2010)
ENZYMES is a dataset of protein tertiary struc[5]Li, G., Semerci, M., Yener, B., Zaki, M.J.: Eﬀectivetures used in [1], which consists of 600 enzymes, exgraph classification based on topological and label
tracted from the BRENDA database [6]. Each enzyme
attributes. Statistical Analysis and Data Mining 5(4),is classified into one of six Enzyme Commission top level
265–283 (2012)
enzyme classes (EC1 to EC6). We classified enzymes[6] Schomburg, I., Chang, A., Ebeling, C., Gremse, M.,from EC1 to EC3 to one class, and from EC4 to EC6
Heldt, C., Huhn, G., Schomburg, D.: BRENDA, theto the other for our binary classification problem.
enzyme database: updates and major new developD&D is a dataset of 1178 protein structures createdments. Nucleic Acids Research 32(suppl 1), D431–D433
by Dobson and Doig [3], and they are classified into(2004)[7] Shervashidze, N., Schweitzer, P., van Leeuwen, E.J.,
enzymes and non-enzymes. As we can see in Table 1,Mehlhorn, K., Borgwardt, K.M.: Weisfeiler-Lehman
the size of each graph in this dataset is relatively large
graph kernels. JMLR 12, 2359–2561 (2011)
compared to the other datasets2 .
[8]Wale, N., Watson, I.A., Karypis, G.: Comparison
NCI (National Cancer Institute) datasets containof descriptor spaces for chemical compound retrieval
data of chemical compounds that are classified accordand classification. Knowledge and Information Systems
ing to their anti-cancer activity [8]. Datasets are num14(3), 347–375 (2008)
bered by their bioassay IDs. NCI1 is balanced subsets,[9] Zhao, Y., Kong, X., Yu, P.S.: Positive and unlabeledwhich is often used in the literature [5, 7], and the others
learning for graph classification. In: ICDM. pp. 962–971 (2011)∗ ISIR, Osaka University† JST, PRESTO‡ Contact: mahito@ar.sanken.osaka-u.ac.jp§ D-BSSE, ETH Zürich¶ Department of Computer Science, University of Copenhagen
1 http://www.predictive-toxicology.org/ptc/
2 MUTAG,ENZYMES, and D&D are obtainedhttp://mlcb.is.tuebingen.mpg.de/Mitarbeiter/Nino/Graphkernels/data.zip

from
3 https://pubchem.ncbi.nlm.nih.gov/

Table S1: Notation.
G, HV (G)E(G)
H⊑G
G, G ′
H|X|n (resp. n′ )x (resp. x′ )
q(x)
f (H)
σψ(σ)
H
αkm(k)
krt
τ (H)
σrt

Graph
The set of vertices of G
The set of edges of G
H is a subgraph of G
A set of graphs
The set of subgraphs in G ∪ G ′ : H = {H ⊑ G | G ∈ G ∪ G ′ }Cardinality of X
Cardinality of G (resp. G ′ ): n = |G| and n′ = |G ′ |Frequency of H in G (resp. G ′ ): x = | { G ∈ G | H ⊑ G } |( )( ′ ) (′)
Probability nx nx′ / n+nx+x′
Frequency of H in G ∪ G ′ : f (H) = x + x′ = | { G ∈ G ∪ G ′ | H ⊑ G } |Frequency( ) (′)
Minimum P value of frequency σ: ψ(σ) = nσ / n+nσ
The set of subgraphs in G ∪ G ′ , |H| is the Bonferroni correction factor
Significance level
Natural numberThe value | { H ∈ H | ψ ◦ f (H) ≤ α/k } |(Rounded) Root of m(k) − k: m(krt − 1) > krt − 1, m(krt ) ≤ krt
The set of testable subgraphs: τ (H) = { H ∈ H | ψ ◦ f (H) ≤ α/krt }(Rounded) Root frequency such that| { H ∈ H | f (H) ≥ (σrt − 1) } | > α/ψ(σrt − 1) and| { H ∈ H | f (H) ≥ σrt } | ≤ α/ψ(σrt )The minimum possible frequency σmin satisfying ψ(σmin ) < αThe maximum possible frequency nThe set of significant subgraphs
The eﬀective number of tests within the testable subgraphs

σminσmaxs(H)meﬀTable S2: Root frequencies σrt for each dataset and each maximum size of subgraph nodes. “—” means thatcomputation did not finished and the root frequency is not confirmed.
Dataset4567Maximum size of subgraph nodes
89 10 11 12 13 14 15

16

LimitlessPTC(MR)MUTAG
ENZYMES
D&D
NCI1
NCI41
NCI167
NCI220

98
11
17
16
5
6
9

98
1420
17
5710

10915
21
196711

1010
17
22
20
68
11111019
22
21681211——2230——
1611——
22———
1811112222
22
7913111224
2224
7913111227
2225
710141113—
2226810141114—
2227
8111511——22288—
1511——
2229——
16

Algorithm 1 One-pass search
Input: Datasets G, G ′ and significance level α
Output: All significant subgraphs
σmin ← 1
while ψ(σmin ) > α do
σmin ← σmin + 1
end while// σmin is the minimum possible frequency
H(σmin ) ← {H ∈ H | f (H) ≥ σmin }// This set is obtained by running an FSM// algorithm with the threshold σmin
σrt ← σminwhile | { H ∈ H | f (H) ≥ σrt } | > α/ψ(σrt ) doσrt ← σrt + 1
end while// σrt is the root frequency
τ (H) ← { H ∈ H | f (H) ≥ σrt }// Testable hypothesess(H) ← { H ∈ τ (H) | P value of H < α/|τ (H)| }Output s(H)Algorithm 3 Incremental search
Input: Datasets G, G ′ and significance level α
Output: All significant subgraphs
σrt ← 1
while ψ(σrt ) > α doσrt ← σrt + 1
end while// This is the minimum possible frequency
repeatRun an FSM algorithm with the threshold σrtwith monitoring the number m of frequent subgraphs
if m > α/ψ(σrt ) while the process thenTerminate the mining processelse
H(σrt ) ← {H ∈ H | f (H) ≥ σrt }// This set is obtained by running an FSM// algorithm with the threshold σrt
end ifσrt ← σrt + 1
until the mining process is not terminatedσrt ← σrt − 1 // σrt is the root frequency
τ (H) ← { H ∈ H | f (H) ≥ σrt }// Testable hypothesess(H) ← { H ∈ τ (H) | P value of H < α/|τ (H)| }Output s(H)Algorithm 2 Decremental search (LAMP search)
Input: Datasets G, G ′ and significance level α
Output: All significant subgraphs
σrt ← n // the maximum possible frequency
repeatH(σrt ) ← {H ∈ H | f (H) ≥ σrt }// This set is obtained by running an FSM// algorithm with the threshold σrtσrt ← σrt − 1
until |H(σrt )| > α/ψ(σrt )σrt ← σrt + 2 // σrt is the root frequency
τ (H) ← { H ∈ H | f (H) ≥ σrt }// Testable hypothesess(H) ← { H ∈ τ (H) | P value of H < α/|τ (H)| }Output s(H)Algorithm 4 Bisection search (LEAP search)
Input: Datasets G, G ′ and significance level α
Output: All significant subgraphs
σmin ← 1
while ψ(σmin ) > α do
σmin ← σmin + 1
end while
σmax ← n // the maximum possible frequency
σrt ← ⌊(σmin + σmax )/2⌋
repeatRun an FSM algorithm with the threshold σrtwith monitoring the number m of frequent subgraphs
if m > α/ψ(σrt ) while the process thenTerminate the mining processelse
H(σrt ) ← {H ∈ H | f (H) ≥ σrt }end ifif the mining process is terminated thenσmin ← σrtelseσmax ← σrtend ifσrt ← ⌊(σmin + σmax )/2⌋
until σmax − σmin = 1
if the last mining process was terminated thenσrt ← σmax // σrt is the root frequency
end if
τ (H) ← { H ∈ H | f (H) ≥ σrt }// Testable hypothesess(H) ← { H ∈ τ (H) | P value of H < α/|τ (H)| }Output s(H)PTC (MR)(carcinogenicity)

NCI 220(anti-cancer activity)

Figure S1: Four examples of significant subgraphs on PTC(MR) (left) and NCI220 (right) that are detected byour method using the testability but are missed by the standard Bonferroni factor. Diﬀerent colors (resp. shapes)of vertices (resp. edges) mean diﬀerent labels of them.