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

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu | Master's thesis
Date
2017-10-23
Department
Major/Subject
Machine Learning and Data Mining
Mcode
SCI3044
Degree programme
Master’s Programme in Computer, Communication and Information Sciences
Language
en
Pages
45+6
Series
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.
Description
Supervisor
Jung, Alexander
Thesis advisor
Jung, Alexander
Keywords
graph signal recovery, semi-supervised learning, benchmark, graphs
Other note
Citation