Using Local Spectral Methods to Robustify Graph-Based Learning Algorithms
Title | Using Local Spectral Methods to Robustify Graph-Based Learning Algorithms |
Publication Type | Conference Paper |
Year of Publication | 2015 |
Authors | Gleich, D., & Mahoney M. W. |
Published in | Proceedings of the 21st Annual SIGKDD |
Abstract | Graph-based learning methods have a variety of names including semi-supervised and transductive learning. They typically use a diffusion to propagate labels from a small set of nodes with known class labels to the remaining nodes of the graph. While popular, these algorithms, when implemented in a straightforward fashion, are extremely sensitive to the details of the graph construction. Here, we provide four procedures to help make them more robust: recognizing implicit regularization in the diffusion, using a scalable push method to evaluate the diffusion, using rank-based rounding, and densifying the graph through a matrix polynomial. We study robustness with respect to the details of graph constructions, errors in node labeling, degree variability, and a variety of other real-world heterogeneities, studying these methods through a precise relationship with mincut problems. For instance, the densification strategy explicitly adds new weighted edges to a sparse graph. We find that this simple densification creates a graph where multiple diffusion methods are robust to several types of errors. This is demonstrated by a study with predicting product categories from an Amazon co-purchasing network. |
Acknowledgment | Gleich is supported by NSF CAREER CF-1149756; Mahoney is partially supported from the Army Research Office and the DARPA GRAPHS program |
URL | http://www.stat.berkeley.edu/~mmahoney/pubs/robustifying-kdd15.pdf |
ICSI Research Group | Big Data |