Cheeger inequalities for submodular transformations

DOI10.1137/1.9781611975482.160MaRDI QIDQ5236350zbMATH OpenOpenAlexFDO

Authors Yuichi Yoshida

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.08781

zbMATH Keywords

spectral graph theorysubmodular transformation

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Hypergraphs (05C65) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Abstract: The Cheeger inequality for undirected graphs, which relates the conductance of an undirected graph and the second smallest eigenvalue of its normalized Laplacian, is a cornerstone of spectral graph theory. The Cheeger inequality has been extended to directed graphs and hypergraphs using normalized Laplacians for those, that are no longer linear but piecewise linear transformations. In this paper, we introduce the notion of a submodular transformation $F:{0,1}^{n}omathbb{R}^m$, which applies $m$ submodular functions to the $n$-dimensional input vector, and then introduce the notions of its Laplacian and normalized Laplacian. With these notions, we unify and generalize the existing Cheeger inequalities by showing a Cheeger inequality for submodular transformations, which relates the conductance of a submodular transformation and the smallest non-trivial eigenvalue of its normalized Laplacian. This result recovers the Cheeger inequalities for undirected graphs, directed graphs, and hypergraphs, and derives novel Cheeger inequalities for mutual information and directed information. Computing the smallest non-trivial eigenvalue of a normalized Laplacian of a submodular transformation is NP-hard under the small set expansion hypothesis. In this paper, we present a polynomial-time $O(logn)$-approximation algorithm for the symmetric case, which is tight, and a polynomial-time $O(lo{g}^{2}n+logncdotlogm)$-approximation algorithm for the general case. We expect the algebra concerned with submodular transformations, or emph{submodular algebra}, to be useful in the future not only for generalizing spectral graph theory but also for analyzing other problems that involve piecewise linear transformations, e.g., deep learning.

Recommendations

• Diffusion operator and spectral analysis for directed hypergraph Laplacian
• Spectral properties of hypergraph Laplacian and approximation algorithms
• Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
• A Cheeger cut for uniform hypergraphs
• Laplacians and the Cheeger inequality for directed graphs

Cited in

(21)

• Private non-monotone submodular maximization
• Measured continuous greedy with differential privacy
• A new transport distance and its associated Ricci curvature of hypergraphs
• Finding Cheeger cuts in hypergraphs via heat equation
• Geometric and spectral properties of directed graphs under a lower Ricci curvature bound
• Polynomial-time algorithms for submodular Laplacian systems
• Diffusion operator and spectral analysis for directed hypergraph Laplacian
• Inequalities on submodular functions via term rewriting
• Quadratic decomposable submodular function minimization: theory and practice
• Core-Periphery Detection in Hypergraphs
• Generalizing p-Laplacian: spectral hypergraph theory and a partitioning algorithm
• Cheng's maximal diameter theorem for hypergraphs
• Nonlinear evolution equation associated with hypergraph Laplacian
• Heat equation on the hypergraph containing vertices with given data
• Weak Kantorovich difference and associated Ricci curvature of hypergraphs
• Local community detection by random walk on hypergraphs
• Sparse cuts in hypergraphs from random walks on simplicial complexes
• Optimal control problem of evolution equation governed by hypergraph Laplacian
• Sublinear time hypergraph sparsification via cut and edge sampling queries
• Submodular hypergraph partitioning: metric relaxations and fast algorithms via an improved cut-matching game
• On the spectral expansion of monotone subsets of the hypercube

This page was built for publication: Cheeger inequalities for submodular transformations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236350)