Matched filters for noisy induced subgraph detection
Files
First author draft
Date
DOI
Authors
Sussman, Daniel
Lyzinski, Vince
Park, Youngser
Priebe, Carey E.
Version
OA Version
Citation
Daniel Sussman, Vince Lyzinski, Youngser Park, Carey E Priebe. "Matched Filters for Noisy Induced Subgraph Detection." IEEE Transactions on Pattern Analysis and Machine Intelligence,
Abstract
We consider the problem of finding the vertex correspondence between two graphs with different number of vertices where the smaller graph is still potentially large. We propose a solution to this problem via a graph matching matched filter: padding the smaller graph in different ways and then using graph matching methods to align it to the larger network. Under a statistical model for correlated pairs of graphs, which yields a noisy copy of the small graph within the larger graph, the resulting optimization problem can be guaranteed to recover the true vertex correspondence between the networks, though there are currently no efficient algorithms for solving this problem. We consider an approach that exploits a partially known correspondence and show via varied simulations and applications to the Drosophila connectome that in practice this approach can achieve good performance.
Description
First author draft