A Comparative Analysis of Graph Signal Recovery Methods for Big Data Networks

Abstract

Graph signal processing, signal recovery, semi-supervised learning, traGraph-based signal recovery (GSR) techniques have been successfully used in different domains for labelling complete graphs from partial subsets of given labels. Much research has been devoted to finding new efficient approaches for solving this learning problem. However, we have identified a lack of research in empirically comparing different GSR methods on big data graphs. In this work, we implement highly scalable versions of five state-of-the-art methods, which we benchmark under identical conditions on a number of real and synthetic datasets. We perform a comprehensive evaluation of these methods in terms of accuracy, scalability, robustness to noise and graph topology as well as sampling set selection. We find that recently proposed methods based on TV minimization outperform more classical approaches that measure the graphs smoothness through the quadratic form. We draw other interesting conclusions and discuss merits and faults of each of the methods studied.