Matched Filters for Noisy Induced Subgraph Detection.

Area of Science:

• Graph theory
• Network analysis
• Computational neuroscience

Background:

• Finding vertex correspondence between noisy graphs is vital for analyzing complex networks.
• Applications span social networks, neuroscience, and computer vision.
• Existing methods struggle with large graphs and differing numbers of vertices.

Purpose of the Study:

• To develop a robust graph matching technique for identifying vertex correspondence.
• To address the challenge of aligning smaller graphs within larger, noisy networks.
• To enable accurate analysis of structural similarities in complex systems.

Main Methods:

• A graph matching matched filter approach is proposed.
• Involves centering and padding the smaller adjacency matrix.
• Graph matching algorithms are applied to align matrices.
• The method is compatible with various adjacency matrix-based matching algorithms.

Main Results:

• The proposed method can recover true vertex correspondence under a statistical model of correlated graphs.
• Demonstrated good performance on simulations and real-world data (Drosophila and human connectomes).
• Highlights the potential for accurate graph alignment even with noise and vertex differences.

Conclusions:

• The graph matching matched filter offers a promising solution for vertex correspondence in large, noisy graphs.
• The technique shows efficacy in applications like connectome analysis.
• Further development of efficient algorithms is needed for broader application.