Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain

Jain, Vishesh; Pham, Huy; Vuong, Thuy-Duong

Comptes Rendus. Mathématique, Tome 361 (2023) no. G5, pp. 869-876

Let $G=(V,E)$ be an undirected graph with maximum degree $\Delta$ and vertex conductance ${\Psi }^{*}\left(G\right)$. We show that there exists a symmetric, stochastic matrix $P$, with off-diagonal entries supported on $E$, whose spectral gap ${\gamma }^{*}\left(P\right)$ satisfies

$${\Psi }^{*}{\left(G\right)}^2/log\Delta \lesssim {\gamma }^{*}\left(P\right)\lesssim {\Psi }^{*}\left(G\right).$$

Our bound is optimal under the Small Set Expansion Hypothesis, and answers a question of Olesker-Taylor and Zanetti, who obtained such a result with $log\Delta$ replaced by $log\left|V\right|$.

In order to obtain our result, we show how to embed a negative-type semi-metric $d$ defined on $V$ into a negative-type semi-metric $d^{\prime }$ supported in ${ℝ}^{O(log\Delta )}$, such that the (fractional) matching number of the weighted graph $(V,E,d)$ is approximately equal to that of $(V,E,d^{\prime })$.

[1] Bartal, Yair; Recht, Ben; Schulman, Leonard J. Dimensionality reduction: beyond the Johnson-Lindenstrauss bound, Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, SIAM (2011), pp. 868-887 | DOI | Zbl

[2] Boyd, Stephen; Diaconis, Persi; Parrilo, Pablo; Xiao, Lin Fastest mixing Markov chain on graphs with symmetries, SIAM J. Optim., Volume 20 (2009) no. 2, pp. 792-819 | DOI | Zbl

[3] Boyd, Stephen; Diaconis, Persi; Xiao, Lin Fastest mixing Markov chain on a graph, SIAM Rev., Volume 46 (2004) no. 4, pp. 667-689 | DOI | Zbl

[4] Charikar, Moses; Waingarten, Erik The Johnson–Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction (2022) (https://arxiv.org/abs/2205.00371)

[5] Deza, Michel Marie; Laurent, Monique Geometry of cuts and metrics, Algorithms and Combinatorics, 15, Springer, 1997 | DOI

[6] Goemans, Michel X. Semidefinite programming in combinatorial optimization, Math. Program., Volume 79 (1997) no. 1, pp. 143-161 | DOI | Zbl

[7] Kwok, Tsz Chiu; Lau, Lap Chi; Tung, Kam Chuen Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues (2022) (https://arxiv.org/abs/2203.06168)

[8] Larsen, Kasper Green; Nelson, Jelani Optimality of the Johnson-Lindenstrauss lemma, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE (2017), pp. 633-638 | DOI

[9] Louis, Anand; Raghavendra, Prasad; Vempala, Santosh The complexity of approximating vertex expansion, 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, IEEE (2013), pp. 360-369 | DOI

[10] Makarychev, Konstantin; Makarychev, Yury; Razenshteyn, Ilya Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (2019), pp. 1027-1038 | Zbl | DOI

[11] Olesker-Taylor, Sam; Zanetti, Luca Geometric Bounds on the Fastest Mixing Markov Chain, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2022)

[12] Raghavendra, Prasad; Steurer, David Graph expansion and the unique games conjecture, Proceedings of the forty-second ACM symposium on Theory of computing (2010), pp. 755-764 | DOI | Zbl

[13] Roch, Sébastien Bounding fastest mixing, Electron. Commun. Probab., Volume 10 (2005), pp. 282-296 | Zbl