  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 (GSP). We assume that the graph signals measured over the
vertices of the network can be represented as white noise that has been
filtered on the graph topology by a smooth graph filter. We develop the
likelihood ratio test (LRT) to detect a specific set of edge disconnections.
Then, we provide the maximum likelihood (ML) decision rule for identifying
general scenarios of edge disconnections in the network. It is shown that the
sufficient statistics of the LRT and ML decision rule are the graph frequency
energy levels in the graph spectral domain. 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, which is based solely on the measurements at neighboring
vertices. Simulation results demonstrate that the proposed methods outperform
existing detection and identification methods.
