Multiscale Analysis on and of Graphs

on YouTube ↗47m

" summary

Claim: a large sparse weighted graph is compressible into a sequence of much smaller graphs that preserve diffusion up to a user epsilon. Method uses the random-walk matrix T, repeatedly applies powers T^{2^J}, selects localized basis columns via rank-revealing QR (modified Gram‑Schmidt, later sparse multifrontal QR plus multiscale partitioning), and forms compressed graph TJ whose one-step walk approximates T^{2^J}. Guarantee is an L2 consistency guarantee (error ~≤ J·epsilon); prototypes handle circles, manifolds, text and evolving networks and give strong speedups, with open questions on stochasticity, complexity and directed probabilistic variants.

AI-written summary · about

" chapters (22)

1. 0:00Intro
2. 0:52Why Multiscale?
3. 1:38Examples
4. 2:27Large graphs and networks Interested in developing quantitative methods for studying large graphs and networks Key problems
5. 4:49Random walks on graphs and data
6. 8:31Some basic properties of r.w.'s
7. 9:32Multiscale random walks
8. 12:30Diffusion Multi-Resolution Analysis
9. 19:19Scheme for DMRA
10. 23:21Consistency of multiscale r.w.'s
11. 28:25Some scaling functions/wavelets
12. 29:22Spectral localization
13. 30:31Compression of T
14. 31:54Example: Text documents
15. 32:43Functions on data
16. 33:05Compression step, QR
17. 34:27Combine with Multiscale Partitions
18. 39:18Multiscale graph Visualization
19. 40:02Comparisons
20. 42:13Dynamic Graphs
21. 44:02A Simple Example
22. 45:52Take-home ideas

" related talks

• 44mScalable Algorithmic Primitives for Data ScienceRichard Peng · Randomized Numerical Linear Algebra and Applications 2018
• 01h 02mGraph PoweringEmmanuel Abbe · Optimization, Statistics and Uncertainty
• 01h 37mGraphons and Graph Limits 3Jennifer Chayes · Graph Limits and Processes on Networks: From Epidemics to Misinformation Boot Camp
• 42mDimensionality Reduction Via Sparse MatricesJelani Nelson · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 30mPreconditioning In Sparse Linear Regression Using Graphical StructureFrederic Koehler · Algorithmic Aspects of Causal Inference 2022
• 32mFrom Sparse Matrices to Graphs and Back AgainJohn Gilbert · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 01h 03mMathematical connections of some local-to-global expressivity results over geometric graphs and...Mircea Petrache · Graph Learning Meets Theoretical Computer Science 2025
• 01h 03mSketching as a Tool for Numerical Linear AlgebraDavid P. Woodruff · Fast Algorithms via Spectral Methods 2014