TY - GEN
T1 - Graph scale-space theory for distributed peak and pit identification
AU - Loukas, Andreas
AU - Cattani, Marco
AU - Zuniga, Marco
AU - Gao, Jie
N1 - Funding Information: Andreas Loukas and Marco Zuniga were supported by the Dutch Technology Foundation STW and the Technology Program of the Ministry of Economic Affairs, Agriculture and Innovation (D2S2 project). Jie Gao would acknowledge the federal government support through NSF DMS-1418255, NSF DMS-1221339, NSF CNS-1217823, and AFOSR FA9550-14-1-0193. Last, we would like to thank the anonymous reviewers and our shepherd Urbashi Mitra for providing us valuable feedback.
PY - 2015/4/13
Y1 - 2015/4/13
N2 - Graph filters are a recent and powerful tool to process information 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 signal 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.
AB - Graph filters are a recent and powerful tool to process information 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 signal 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.
UR - https://www.scopus.com/pages/publications/84954184547
UR - https://www.scopus.com/pages/publications/84954184547#tab=citedBy
U2 - 10.1145/2737095.2737101
DO - 10.1145/2737095.2737101
M3 - Conference contribution
T3 - IPSN 2015 - Proceedings of the 14th International Symposium on Information Processing in Sensor Networks (Part of CPS Week)
SP - 118
EP - 129
BT - IPSN 2015 - Proceedings of the 14th International Symposium on Information Processing in Sensor Networks (Part of CPS Week)
PB - Association for Computing Machinery, Inc
T2 - 14th International Symposium on Information Processing in Sensor Networks, IPSN 2015
Y2 - 13 April 2015 through 16 April 2015
ER -