Distributed Graph Filters

We have recently seen a surge of research focusing on the processing of graph data. The emerging field of signal processing on graphs focuses on the extension of classical discrete signal processing techniques to the graph setting. Arguably, the greatest breakthrough of the field has been the extension of the Fourier transform from time signals and images to graph signals, i. e., signals defined on the nodes of irregular graphs. Analogously to how the Fourier transform allows us to decompose complex signals in terms of their fundamental frequencies, the spectral transform describes signals in terms of their relation to the underlying graph. The rigorous examination of the relation between signal and graph has lead to the design of distributed graph filters, graph analogues of classical filters. Graph filters enable us to observe graph data at different scales, effectively separating fine details from inherent signal trends. For instance, a low-pass graph filter controls the size of observable signal structures, attenuating structures of small size, such as those attributed to noise. Beyond noise removal, graph filters are useful for revealing communities (low-pass), identifying event-regions (band-pass), and detecting anomalies (high-pass). Yet, despite their interesting properties, current distributed graph filters have so far been limited. To begin with, it is currently assumed that all data remain static for the duration of computation. When the signal is time-varying and the graph topology dynamic, the computation becomes challenging. Even further, filtering efficiency depends on the correct choice of scale—roughly the number of hops a filter takes into account. To choose the scale correctly however, one must have a-priori information about the observed phenomenon, as well as of the instrument of observation—in our case, the graph topology; information which is rarely available and often changes over time. The main contribution of this thesis is tackling the above limitations. First, we relax the computational assumptions posed by current graph filters. We propose distributed graph filters that converge fast, even in the presence of dynamics. Our filters are shown robust to message loss, and able to track time-varying signals and graphs. Second, we set the foundations of distributed scale-invariant analysis of graph signals. According to classical scale-space theory, if no a-priori information about a signal is known, one must observe it at all possible scales. In an analogous way, we show that the scale-invariant observation of a graph signal entails filtering it with a small family of graph filters. Scale-space analysis is therefore possible on graphs, and incurs an overhead equivalent to that of a distributed graph filter. We demonstrate the usefulness of our algorithms by applying them to a number of important information processing problems in sensor networks. Among others, our filters are shown to expand the scope of potential-field search methods, to enhance the detection accuracy of spatial event regions and boundaries, and to improve the identification of signal peaks and pits. Simulations and experiments, demonstrate that our algorithms are robust to the difficult conditions posed by wireless communications (such as asymmetric links, phantom effects, message loss, and asynchrony), and that they scale to very large networks.