Graph Scale-Space Theory for Distributed Peak and Pit Identification


Graph filters are a recent and powerful tool to process in- formation in graphs. Yet despite their advantages, graph filters are limited. The limitation is exposed in a filtering task that is common, but not fully solved in sensor networks: the identification of a signal’s peaks and pits. Choosing the correct filter necessitates a-priori information about the sig- nal and the network topology. Furthermore, in sparse and irregular networks graph filters introduce distortion, effectively rendering identification inaccurate, even when signal-specific information is available. Motivated by the need for a multi-scale approach, this paper extends classical results on scale-space analysis to graphs. We derive the family of scale-space kernels (or filters) that are suitable for graphs and show how these can be used to observe a signal at all possible scales: from fine to coarse. The gathered information is then used to distributedly identify the signal’s peaks and pits. Our graph scale-space approach diminishes the need for a-priori knowledge, and reduces the effects caused by noise, sparse and irregular topologies, exhibiting: (i) superior resilience to noise than the state-of-the-art, and (ii) at least 20% higher precision than the best graph filter, when evaluated on our testbed.

ACM Digital Library | Paper

AuthorsAndreas Loukas and Marco Cattani and Marco A. Zuniga and Jie Gao
Research group: Embedded Software group, Delft University of Technology, Delft, Netherlands and Stony Brook University, Stony Brook, New York
Conference14th Int. Conf. on Information Processing in Sensor Networks (IPSN)
Year: 2015