Gotta match 'em all: Solution diversification in graph matching matched filters
This incremental work addresses the need for efficient and diverse graph matching in applications such as neuroscience and data mining.
The paper tackles the problem of finding multiple noisily embedded template graphs in a large background graph by extending the graph-matching-matched-filter technique with iterative penalization for diversity and algorithmic speed-ups, achieving scalability and demonstrating utility in simulated and real-world datasets like brain connectomes and knowledge bases.
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.