Significant Subgraph Mining with Multiple Testing Correction
Significant Subgraph Mining with Multiple Testing Correction
复制标题
DOI：
10.1137/1.9781611974010.5
复制
发表时间：
2014-07
期刊：
影响因子：
--
通讯作者：
M. Sugiyama;F. Llinares-López;Niklas Kasenburg;Karsten M. Borgwardt
中科院分区：
文献类型：
--
作者：
M. Sugiyama;F. Llinares-López;Niklas Kasenburg;Karsten M. Borgwardt
在一类事务中发现统计上显著丰富的项集的问题由于需要校正多个假设检验而变得复杂。修剪不可测试的假设最近被提出作为一种策略，这项任务的重要项集挖掘。它被证明可以带来更大的统计能力，发现更多真正重要的项集，而不是对真实世界数据集的标准Bonferroni校正。然而，一个悬而未决的问题是，这种排除不可检验的假设的策略是否也会导致子图挖掘中更大的统计能力，其中假设的数量远远大于项集挖掘。在这里，我们回答这个问题的实证调查8个流行的图基准数据集。我们提出了一种新的高效的搜索策略，它总是返回相同的解决方案，作为国家的最先进的方法，大约是两个数量级的速度。此外，我们利用子图之间的依赖性，考虑有效的测试次数，从而进一步提高统计能力。
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 itemset 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 datasets. 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 itemset 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.