Estimating the Cheeger constant using machine learning
In this paper, we use machine learning to show that the Cheeger constant of a connected regular graph has a predominant linear dependence on the largest two eigenvalues of the graph spectrum. We also show that a trained deep neural network on graphs of smaller sizes can be used as an effective estimator in estimating the Cheeger constant of larger graphs.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningSimilar Papers 제목 키워드 기반
From graph cuts to isoperimetric inequalities: Convergence rates of Cheeger cuts on data clouds
In this work we study statistical properties of graph-based clustering algorithms that rely on the optimization of balanced graph cuts, the main example being the optimization of Cheeger cuts. We consider proximity graph…
ClusteringCheeger--Hodge Contrastive Learning for Structurally Robust Graph Representation Learning
Graph Contrastive Learning (GCL) has emerged as a prominent framework for unsupervised graph representation learning. However, relying on augmentation design alone to define the invariances learned by GCL can be brittle …
Graph Representation LearningContrastive LearningCheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues
We derive Cheeger inequalities for directed graphs and hypergraphs using the reweighted eigenvalue approach that was recently developed for vertex expansion in undirected graphs [OZ22,KLT22,JPV22]. The goal is to develop…
Spectral Graph Theoretic Methods for Enhancing Network Robustness in Robot Localization
This paper addresses the optimization of edge-weighted networks by maximizing algebraic connectivity to enhance network robustness. Motivated by the need for precise robot position estimation in cooperative localization …
Simultaneous Localization and MappingvalidWeighted Cheeger and Buser Inequalities, with Applications to Clustering and Cutting Probability Densities
In this paper, we show how sparse or isoperimetric cuts of a probability density function relate to Cheeger cuts of its principal eigenfunction, for appropriate definitions of `sparse cut' and `principal eigenfunction'. …
Clustering