2015 UsingLocalSpectralMethodstoRobu

• (Gleich & Mahoney, 2015) ⇒ David F. Gleich, and Michael W. Mahoney. (2015). “Using Local Spectral Methods to Robustify Graph-Based Learning Algorithms.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783376

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Using+Local+Spectral+Methods+to+Robustify+Graph-Based+Learning+Algorithms
• http://dl.acm.org/citation.cfm?id=2783258.2783376&preflayout=flat#citedby

Quotes

Author Keywords

• Clustering; diffusions; graph algorithms; robustifying; semi-supervised learning

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.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 UsingLocalSpectralMethodstoRobu	Michael W. Mahoney David F. Gleich			Using Local Spectral Methods to Robustify Graph-Based Learning Algorithms				10.1145/2783258.2783376		2015