Identification of Edge Disconnections in Networks Based on Graph Filter Outputs

Graphs are fundamental mathematical structures used in various fields to model statistical and physical relationships between data, signals, and processes. In some applications, such as data processing in graphs that represent physical networks, the initial network topology is known. However, disconnections of edges in the network change the topology and may affect the signals and processes over the network. In this paper, we consider the problem of edge disconnection identification in networks by using concepts from graph signal processing. By representing the graph signals measured over the network's vertices as white noise that has been filtered on the graph topology by a smooth graph filter. We develop the likelihood ratio test to detect a specific set of edge disconnections and provide the maximum likelihood decision rule for identifying general scenarios of edge disconnections in the network. However, the ML decision rule leads to a high-complexity exhaustive search over the edges in the network and is practically infeasible. Thus, we propose a low-complexity greedy method that identifies a single disconnected edge at each iteration. Moreover, by using the smoothness of the considered graph filter, we suggest a local implementation of the decision rule based solely on the measurements at neighboring vertices.