Improved hidden clique detection by optimal linear fusion of multiple adjacency matrices
- Resource Type
- Conference
- Authors
- Nayar, Himanshu; Miller, Benjamin A.; Geyer, Kelly; Caceres, Rajmonda S.; Smith, Steven T.; Nadakuditi, Raj Rao
- Source
- 2015 49th Asilomar Conference on Signals, Systems and Computers Signals, Systems and Computers, 2015 49th Asilomar Conference on. :1520-1524 Nov, 2015
- Subject
- Bioengineering
Communication, Networking and Broadcast Technologies
Computing and Processing
Signal Processing and Analysis
Symmetric matrices
Context
Eigenvalues and eigenfunctions
Image edge detection
Algorithm design and analysis
Computer science
Analytical models
- Language
- ISSN
- 1058-6393
Graph fusion has emerged as a promising research area for addressing challenges associated with noisy, uncertain, multi-source data. While many ad-hoc graph fusion techniques exist in the current literature, an analytical approach for analyzing the fundamentals of the graph fusion problem is lacking. We consider the setting where we are given multiple Erdős-Rényi modeled adjacency matrices containing a common hidden or planted clique. The objective is to combine them linearly so that the principal eigenvectors of the resulting matrix best reveal the vertices associated with the clique. We utilize recent results from random matrix theory to derive the optimal weighting coefficients and use these insights to develop a data-driven fusion algorithm. We demonstrate the improved performance of the algorithm relative to other simple heuristics.