Gotta match 'em all: Solution diversification in graph matching matched filters
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910513478238208 |
|---|---|
| author | Li, Zhirui Johnson, Ben Sussman, Daniel L. Priebe, Carey E. Lyzinski, Vince |
| author_facet | Li, Zhirui Johnson, Ben Sussman, Daniel L. Priebe, Carey E. Lyzinski, Vince |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_13451 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Gotta match 'em all: Solution diversification in graph matching matched filters Li, Zhirui Johnson, Ben Sussman, Daniel L. Priebe, Carey E. Lyzinski, Vince Machine Learning Combinatorics Applications Methodology 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. |
| title | Gotta match 'em all: Solution diversification in graph matching matched filters |
| topic | Machine Learning Combinatorics Applications Methodology |
| url | https://arxiv.org/abs/2308.13451 |