A Sampling Theory Perspective of Graph-Based Semi-Supervised Learning

• Published in: IEEE transactions on information theory 2019-04, Vol.65 (4), p.2322-2342
• Main Authors: Anis, Aamir, El Gamal, Aly, Avestimehr, A. Salman, Ortega, Antonio
• Format: Article
• Language: English
• Subjects: Analytical models; Bandwidth; Complexity theory; Data models; Data points; Eigenvectors; Geometry; Graph sampling theory; graph signal processing; Laplace equations; Sampling; Semi-supervised learning; Semisupervised learning; Smoothness
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2018.2879897

Graph-based methods have been quite successful in solving unsupervised and semi-supervised learning problems, as they provide a means to capture the underlying geometry of the dataset. It is often desirable for the constructed graph to satisfy two properties: first, data points that are similar in the feature space should be strongly connected on the graph, and second, the class label information should vary smoothly with respect to the graph, where smoothness is measured using the spectral properties of the graph Laplacian matrix. Recent works have justified some of these smoothness conditions by showing that they are strongly linked to the semi-supervised smoothness assumption and its variants. In this work, we reinforce this connection by viewing the problem from a graph sampling theoretic perspective, where class indicator functions are treated as bandlimited graph signals (in the eigenvector basis of the graph Laplacian) and label prediction as a bandlimited reconstruction problem. Our approach involves analyzing the bandwidth of class indicator signals generated from statistical data models with separable and nonseparable classes. These models are quite general and mimic the nature of most real-world datasets. Our results show that in the asymptotic limit, the bandwidth of any class indicator is also closely related to the geometry of the dataset. This allows one to theoretically justify the assumption of bandlimitedness of class indicator signals, thereby providing a sampling theoretic interpretation of graph-based semi-supervised classification.