Efficient Minimax Signal Detection on Graphs
This work addresses detection challenges in graph-based applications like security and health, offering a method that is computationally efficient but incremental in its approach.
The paper tackles the problem of detecting novel observations on unknown connected subgraphs in graphs, such as for network intrusion or disease outbreaks, by formulating it as an optimization problem and embedding connectivity constraints into linear matrix inequalities to achieve computationally efficient tests, proving minimax optimality for exponential distributions on lattices with concrete results tied to internal conductance.
Several problems such as network intrusion, community detection, and disease outbreak can be described by observations attributed to nodes or edges of a graph. In these applications presence of intrusion, community or disease outbreak is characterized by novel observations on some unknown connected subgraph. These problems can be formulated in terms of optimization of suitable objectives on connected subgraphs, a problem which is generally computationally difficult. We overcome the combinatorics of connectivity by embedding connected subgraphs into linear matrix inequalities (LMI). Computationally efficient tests are then realized by optimizing convex objective functions subject to these LMI constraints. We prove, by means of a novel Euclidean embedding argument, that our tests are minimax optimal for exponential family of distributions on 1-D and 2-D lattices. We show that internal conductance of the connected subgraph family plays a fundamental role in characterizing detectability.