We present a novel approach for finding multiple noisily embedded template
graphs in a very large background graph. Our method builds upon the
graph-matching-matched-filter technique proposed in Sussman et al., with the
discovery of multiple diverse matchings being achieved by iteratively
penalizing a suitable node-pair similarity matrix in the matched filter
algorithm. In addition, we propose algorithmic speed-ups that greatly enhance
the scalability of our matched-filter approach. We present theoretical
justification of our methodology in the setting of correlated Erdos-Renyi
graphs, showing its ability to sequentially discover multiple templates under
mild model conditions. We additionally demonstrate our method's utility via
extensive experiments both using simulated models and real-world dataset,
include human brain connectomes and a large transactional knowledge base.

本研究提出了一种用于在非常庞大的背景图中查找多个嵌入模板图的新方法，该方法基于 Sussman 等人提出的图匹配匹配滤波技术，通过在匹配滤波算法中迭代地对合适的节点对相似度矩阵进行惩罚，实现了多样化匹配的发现。此外，我们提出了算法速度的优化，极大地提高了我们的匹配滤波方法的可扩展性。通过在相关 Erdos-Renyi 图的设置中，理论上证明了我们方法在温和的模型条件下能够顺序地发现多个模板。我们还通过大量的实验验证了我们方法的实用性，包括使用模拟模型和真实世界数据集，如人脑连接组和大型事务知识库。