Significant subgraph mining with multiple testing correction

TY - GEN

T1 - Significant subgraph mining with multiple testing correction

AU - Sugiyama, Mahito

AU - López, Felipe Llinares

AU - Kasenburg, Niklas

AU - Borgwardt, Karsten M.

PY - 2015

Y1 - 2015

N2 - The problem of finding itemsets that are statistically significantly enriched in a class of transactions is complicated by the need to correct for multiple hypothesis testing. Pruning untestable hypotheses was recently proposed as a strategy for this task of significant item-set mining. It was shown to lead to greater statistical power, the discovery of more truly significant itemsets, than the standard Bonferroni correction on real-world dataseis. An open question, however, is whether this strategy of excluding untestable hypotheses also leads to greater statistical power in subgraph mining, in which the number of hypotheses is much larger than in item-set mining. Here we answer this question by an empirical investigation on eight popular graph benchmark datasets. We propose a new efficient search strategy, which always returns the same solution as the state-of-the-art approach and is approximately two orders of magnitude faster. Moreover, we exploit the dependence between subgraphs by considering the effective number of tests and thereby further increase the statistical power.

AB - The problem of finding itemsets that are statistically significantly enriched in a class of transactions is complicated by the need to correct for multiple hypothesis testing. Pruning untestable hypotheses was recently proposed as a strategy for this task of significant item-set mining. It was shown to lead to greater statistical power, the discovery of more truly significant itemsets, than the standard Bonferroni correction on real-world dataseis. An open question, however, is whether this strategy of excluding untestable hypotheses also leads to greater statistical power in subgraph mining, in which the number of hypotheses is much larger than in item-set mining. Here we answer this question by an empirical investigation on eight popular graph benchmark datasets. We propose a new efficient search strategy, which always returns the same solution as the state-of-the-art approach and is approximately two orders of magnitude faster. Moreover, we exploit the dependence between subgraphs by considering the effective number of tests and thereby further increase the statistical power.

U2 - 10.1137/1.9781611974010.5

DO - 10.1137/1.9781611974010.5

M3 - Konferencebidrag i proceedings

SP - 37

EP - 45

BT - Proceedings of the 2015 SIAM International Conference on Data Mining

PB - Society for Industrial and Applied Mathematics

T2 - SIAM International Conference on Data Mining 2015

Y2 - 30 April 2015 through 2 May 2015

ER -