Optimal embeddings improve graph cuts and expansion approximations

Optimal Average Distortion for Non-Expansive Embeddings of Euclidean Metrics into the Line: With applications to cut-matching games and vertex expansion

Data Structures and AlgorithmsComputational Geometry

Summary

The paper deals with a way to represent distances between points in a space using just a line, without stretching the distances too much on average. The authors find the best possible way to do this for points in ordinary Euclidean space, matching what was previously known as a minimum limit. They then show how this finding helps create better strategies to split networks into parts efficiently and to estimate how connected nodes are in complex graphs.

What this means in practice

  • For network algorithm designers: Use the improved embeddings to design cut-player strategies ensuring optimal spectral properties for refining network partitions.
  • For graph analytics engineers: Apply the spectral approximation technique to better estimate vertex expansion in graphs with many connections, improving analysis of complex networks.

Authors

Jack Spalding-Jamieson

Abstract

We show that any $n$-point Euclidean metric admits a non-expansive embedding into the line with average distortion at most $O\left(\sqrt{\frac{\log n}{\log\log n}}\right)$, matching a known lower bound. We also present two applications of this result. First, we give a cut-player strategy with an optimal spectral guarantee for the undirected cut-matching game. Second, we give an improved spectral approximation for vertex expansion in high-degree graphs.