Robust Spectral Diffusions for Data Applications
summary
Shows that PageRank is a spectral relaxation of an s–t min‑cut construction and that the push algorithm exactly solves a one-norm regularized two-norm problem, producing highly localized vectors (on an 800k‑node Flickr graph there are about 15 significant entries). Push runs in roughly O(1/(epsilon beta)) work and scales to billions of edges on a laptop. For semi‑supervised labeling, mild regularization helps sparse graphs and using rank-based rounding (not raw values) fixes the dominant‑class failure and yields correct labels.
AI-written summary · about
chapters (14)
- 0:00Intro
- 3:16Practical graph diffusions
- 6:32Two types of localization
- 9:35The PageRank problem & the Laplacian on undirected graphs
- 12:08The s-t min-cut problem
- 13:22The localized cut graph
- 19:10The Push Algorithm for PageRank
- 22:34Gauss-Seidel and Gauss-Southwell
- 24:29PageRank Pull and Push for Gauss-Southwell/Seidel
- 26:46Almost "the push" method
- 33:21Vanilla SSL algorithms have a problem
- 35:34This problem is worse on real data
- 36:26Unifying theory and practice
- 42:45Semi-supervised Learning on Graphs
related talks
01h 02mGraph Powering
01h 05mFirst-Order Optimization and Online Learning Techniques in the Design of Fast Spectral Algorithms
47mLearning Probabilistic Models for Graph Partitioning in the Presence of Noise
47mCrowdsourcing for Clustering: Algorithms and Information-Theoretic Lower Bounds
47mPhase Transitions in Semidefinite Relaxations (A Fast & Robust Algorithm for Community Detection)
46mSpectral Partitioning for Metrics (And NNs Too)
45mCommunity Detection with the Non-Backtracking Operator
01h 02mTheory and Big Data