# Gotta match 'em all: Solution diversification in graph matching matched filters

arXiv: https://arxiv.org/abs/2308.13451 · HTML: https://mlsanity.com/paper/2308.13451/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 52 references that are in the map.
- First posted on arXiv 25 Aug 2023.

## Builds on (most cited first, 13 of 13)

- [Implicit Gradient Regularization](https://mlsanity.com/paper/2009.11162/) (2020)
- [Penalizing Gradient Norm for Efficiently Improving Generalization in Deep Learning](https://mlsanity.com/paper/2202.03599/) (2022)
- [Settling the Sharp Reconstruction Thresholds of Random Graph Matching](https://mlsanity.com/paper/2102.00082/) (2021)
- [Exact alignment recovery for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1711.06783/) (2017)
- [Improved Achievability and Converse Bounds for ErdHos-R'enyi Graph Matching](https://mlsanity.com/paper/1602.01042/) (2016)
- [Seeded Graph Matching via Large Neighborhood Statistics](https://mlsanity.com/paper/1807.10262/) (2018)
- [Random graph matching at Otter's threshold via counting chandeliers](https://mlsanity.com/paper/2209.12313/) (2022)
- [Information Recovery in Shuffled Graphs via Graph Matching](https://mlsanity.com/paper/1605.02315/) (2016)
- [Matched Filters for Noisy Induced Subgraph Detection](https://mlsanity.com/paper/1803.02423/) (2018)
- [Seeded Graph Matching Via Joint Optimization of Fidelity and Commensurability](https://mlsanity.com/paper/1401.3813/) (2014)
- [Multiplex graph matching matched filters](https://mlsanity.com/paper/1908.02572/) (2019)
- [Clustered Graph Matching for Label Recovery and Graph Classification](https://mlsanity.com/paper/2205.03486/) (2022)
- [Structural Equivalence in Subgraph Matching](https://mlsanity.com/paper/2301.03161/) (2023)

## Built on by (most cited first, 1 of 1)

- [Detection of Model-based Planted Pseudo-cliques in Random Dot Product Graphs by the Adjacency Spectral Embedding and the Graph Encoder Embedding](https://mlsanity.com/paper/2312.11054/) (2023)

## Abstract (arXiv)

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.