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

Loading...
Thumbnail Image

URL

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