SubStAnce: Efficient Mining of Statistically Significant Subgraphs with Few-Shot Resampling

Pattern Mining is a fundamental problem in the field of Data Mining, due to its very central role in many areas. In this work, we focus on discovering subgraphs that are associated with the value of a specific feature called target. The goal is to find patterns that are associated with the target not only in the analyzed dataset, but also in the overall process that generates it, since the dataset is just a representation of it. We achieve this by performing statistical significance tests in an efficient way, returning significant patterns with solid guarantees on the probability of false discoveries, exploiting the Few-Shot Resampling framework, recently introduced for different types of patterns. We present SubStAnce, a tool for efficiently mining statistically significant subgraphs, for which we perform an extensive experimental evaluation that shows the validity of the tool and how different hyperparameters’ values affect performances.