Matched Filters for Noisy Induced Subgraph Detection

Daniel L. Sussman, Youngser Park, Carey E. Priebe, Vince LyzinskiIEEE TPAMI 2020 · DOI

TL;DR

This paper introduces a novel "matched filter" approach for finding a smaller graph (subgraph) within a larger, noisy graph, even when the graphs have different numbers of vertices. This is crucial for applications like analyzing brain networks or social interactions where direct comparison is difficult. The authors propose padding techniques and demonstrate their method's effectiveness in synthetic and real-world scenarios.

What Problem Does This Paper Address?

The core challenge this paper tackles is noisy induced subgraph detection. Imagine you have two networks (graphs): a large one representing, say, a whole brain's connections, and a smaller one representing a specific functional circuit. The problem is to find where that specific circuit exists within the larger network, even if the data is noisy, incomplete, or the networks have different numbers of "nodes" (e.g., different numbers of neurons or users).

Traditional graph matching methods often assume graphs of equal size. When sizes differ, or when the subgraph isn't an exact match but a "noisy" version, these methods struggle. This is particularly relevant in fields like neuroscience, where comparing brain connectomes across individuals or even within the same individual over time is essential but complicated by data noise and varying resolutions. The authors frame this as a graph matching problem, but one that requires specialized techniques to handle the size mismatch and noise.

Methods

The paper's key innovation is the development of "matched filters" for subgraph detection. This involves transforming the subgraph detection problem into a graph matching problem that can be solved using existing graph matching machinery. The core ideas are:

  • Padding Schemes: To align graphs of different sizes, the smaller graph's adjacency matrix is "padded" with extra rows and columns to match the dimensions of the larger graph. The paper explores three schemes:
  • Naive Padding: A basic approach that can lead to incorrect matches.
  • Centered Padding: A more sophisticated method that centers the adjacency matrices, improving performance.
  • Oracle Padding: An ideal but often inaccessible scheme that assumes perfect knowledge of the underlying graph structure.
  • Graph Matching Machinery: The padded matrices are then fed into graph matching algorithms. The paper utilizes a Fast Approximate Quadratic Programming (FAQ) algorithm [15] which relaxes the problem to doubly stochastic matrices and uses gradient descent.
  • Soft Seeding: To improve accuracy, the algorithm can incorporate "seeds" – a small set of known vertex correspondences between the two graphs. This helps guide the optimization process.
  • Statistical Modeling: The authors analyze their approach under a correlated heterogeneous Erdős-Rényi (CorrER) model, which provides a theoretical framework for understanding how correlations and edge probabilities affect subgraph detection.

Datasets

The paper uses both synthetic and real-world datasets for evaluation:

  • Synthetic Data:
    • Correlated Homogeneous Erdős-Rényi (CorrER) graphs: Used to test performance under varying correlation levels and with different numbers of seeds.
  • Planted Partition Model: A scenario where the larger graph contains a denser subgraph, testing the ability to find this structure.
  • Random Dot Product Graph (RDPG) model: Used to evaluate performance under heterogeneous graph models, exploring different sampling strategies for the subgraph.
  • Real-World Data:
    • Drosophila Connectomes: Analyzing the brain networks of fruit flies to find induced subgraphs of Kenyon cells.
  • Human DTMRI Graphs: Large-scale diffusion tensor magnetic resonance imaging data from human brains to test scalability and performance on real connectome data.

Key Insights and Ideas

  • Padding is Key: The choice of padding scheme significantly impacts the success of subgraph detection, with centered padding generally outperforming naive padding.
  • Correlation Matters: Higher correlation between the graphs dramatically improves the ability to find the correct subgraph correspondence.
  • The "Gap" Phenomenon: A crucial observation is the presence of a "gap" in the objective function value. A significant jump in the objective function often indicates that a correct or near-correct match has been found, providing a potential stopping criterion for random restarts.
  • Seeds Help, But Not Always: While seeds generally improve performance, their impact can vary, and sometimes the best matches don't strictly maintain the initial seeds.
  • Scalability is Achievable: The methods demonstrate a promising ability to scale to very large graphs (tens of thousands of nodes), which is critical for real-world applications like connectomics.

Key Results

  • Theoretical Guarantees: Under specific statistical models (CorrER), centered and oracle padding schemes are theoretically guaranteed to recover the true vertex correspondence under mild conditions, especially when the subgraph size grows logarithmically with the larger graph size.
  • Synthetic Performance: Experiments show that with sufficient seeds and high correlation, the centered padding scheme can achieve near-perfect recovery of the subgraph. The "gap" phenomenon in the objective function is consistently observed, aiding in identifying good matches.
  • Real-World Application: The method successfully identified subgraphs in Drosophila and human connectomes, demonstrating its practical applicability. For instance, in the Drosophila connectome, they were able to find a significant number of K-cells.
  • Runtime: The algorithm is computationally feasible, with experiments showing that 200 restarts can be performed in under 10 minutes on a standard laptop, and performance generally improves with better algorithmic efficiency.

Limitations and Future Work

  • Oracle Inaccessibility: The "oracle padding" scheme, while theoretically optimal, is generally inaccessible in practice as it requires perfect knowledge of the true subgraph.
  • Local Optima: The gradient ascent approach used for optimization is not guaranteed to find the global optimum, meaning it might converge to a local minimum that isn't the best match.
  • Gap Prediction: While the gap phenomenon is observed, rigorous theoretical results for its expected size in correlated Erdős-Rényi models are still unknown.
  • Negative Correlation: The proofs and methods assume positive correlation; allowing for negative correlations would require different approaches.
  • Future Work: The authors suggest exploring adaptive stopping criteria based on the objective function gap, investigating the reasons behind the performance of rank-2 centering, and further theoretical work on the general question of graph "matchability." They also note that the problem of finding which pairs of graphs are matchable remains open.

Summary updated

BibTeX
@article{sussman2020matched,
  author = {Daniel L. Sussman and Youngser Park and Carey E. Priebe and Vince Lyzinski},
  title = {{Matched Filters for Noisy Induced Subgraph Detection}},
  journal = {IEEE TPAMI},
  year = {2020},
  doi = {10.1109/tpami.2019.2914651},
}
Figure