On Using Graph Distances to Estimate Euclidean and Related Distances

on YouTube ↗43m

" summary

Uses graph shortest-path distances as proxies for unknown Euclidean or intrinsic (geodesic) distances and proves quantitative error bounds: when sample density epsilon is small relative to connectivity radius r the graph distance is within 1+O(epsilon/r) of the true distance and a complementary lower bound has error of order kappa r^2 (kappa = curvature). Introduces a discrete curvature-constrained polygonal curvature (inverse circumcircle radius), works on a regularized annulus graph, and gives minimax-optimal recovery from unweighted adjacency up to scale.

AI-written summary · about

" chapters (12)

1. 0:00Introduction to EDM
2. 2:17Graph embedding techniques
3. 4:46Realizability and rigidity
4. 6:46Matrix completion methods
5. 9:26Graph distance estimation
6. 12:25Manifold learning context
7. 15:30Curvature and path bounds
8. 20:37Regularized path analysis
9. 23:27Discrete curvature concepts
10. 27:21Upper bounds on paths
11. 31:27Adjacency matrix estimation
12. 38:04Discussion and Q&A

" related talks

• 49mMetric Representations: Algorithms and GeometryAnna Gilbert · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 56mTesting Thresholds for High-dimensional Sparse Random Geometric GraphsSiqi Liu · Structural Results 2023
• 01h 31mGraphons and Graph Limits 2Christian Borgs · Graph Limits and Processes on Networks: From Epidemics to Misinformation Boot Camp
• 46mSketching Techniques for Kernel Density EstimationMoses Charikar · Sketching and Algorithm Design 2023
• 48mSketching Techniques for Kernel Density Estimation or for Optimal Transport ComputationsErik Waingarten · Sketching and Algorithm Design 2023
• 01h 03mMathematical connections of some local-to-global expressivity results over geometric graphs and...Mircea Petrache · Graph Learning Meets Theoretical Computer Science 2025
• 54mExact Matching Of Random Graphs With Constant CorrelationCheng Mao · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 52mNew Algorithms For The Graph Alignment ProblemMarc Lelarge · Algorithmic Advances for Statistical Inference with Combinatorial Structure