Graph Powering
summary
Proposes graph powering: form a new graph by adding edges between nodes within graph distance ≤ R, using the adjacency of walks thresholded to 0/1, then run spectral methods. Proves and empirically shows this regularizes spectra, absorbs low-degree tails and suppresses dense tangles better than raw adjacency or non-backtracking on mixed models. Uses belief‑propagation linearization, spectral analysis and experiments up to 300k nodes; R scales like a small fraction of graph diameter (or polylog N for practical sparsified versions). Results are work in progress.
AI-written summary · about
chapters (24)
- 0:00Intro
- 1:11Unsupervised learning from interactions
- 2:52Examples
- 5:29except none of these really work as such
- 7:42Block models with 2 clusters
- 11:20Figure of merits
- 13:55Regimes
- 15:27How to find the clusters: pick the most likely?
- 18:34Spectral relaxation of min-bisection
- 24:22But in the sparse regime...
- 25:17How to mitigate high-degree nodes?
- 26:03but this brings back the problem of tales
- 30:56Switch from ML to Bayes
- 33:57Iterating this gives Belief Propagation
- 36:52NB matrix and spectral redemption
- 39:22How long of a redemption?
- 40:18What works better on the GBM?
- 41:10Graph powering: add shot-cut edges between close enough vertices
- 43:00Intuition: 'diffuse tangles' and 'absorb tales'
- 45:08Graph powering on SBM and GBM
- 46:55Graph powering on HBM
- 47:20Graph powering and spectral resurrection
- 55:05Powered Laplacian
- 57:26More on powering
related talks
45mRandom Walks on Directed Graphs
01h 04mNonparametric Bayesian Methods: Models, Algorithms, and Applications IV
47mMultiscale Analysis on and of Graphs
01h 41mGraph Intelligence: Enhance Reasoning and Retrieval Using Graph Analytics
49mRobust Spectral Diffusions for Data Applications
31mGraph Mining with Deep Learning: challenges and pitfalls
30mScalable Graph-Parallel Inference Algorithms and Systems
01h 28mBoot camp on graphons for graph learning