Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms

DOI10.1145/2746539.2746555MaRDI QIDQ2941566zbMATH OpenOpenAlexFDO

Authors Anand Louis

Publication date 21 August 2015

Published in Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

expansionheat dispersionspectral theory

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Hypergraphs (05C65) Approximation algorithms (68W25)

Abstract: The celebrated Cheeger's Inequality cite{am85,a86} establishes a bound on the expansion of a graph via its spectrum. This inequality is central to a rich spectral theory of graphs, based on studying the eigenvalues and eigenvectors of the adjacency matrix (and other related matrices) of graphs. It has remained open to define a suitable spectral model for hypergraphs whose spectra can be used to estimate various combinatorial properties of the hypergraph. In this paper we introduce a new hypergraph Laplacian operator (generalizing the Laplacian matrix of graphs)and study its spectra. We prove a Cheeger-type inequality for hypergraphs, relating the second smallest eigenvalue of this operator to the expansion of the hypergraph. We bound other hypergraph expansion parameters via higher eigenvalues of this operator. We give bounds on the diameter of the hypergraph as a function of the second smallest eigenvalue of the Laplacian operator. The Markov process underlying the Laplacian operator can be viewed as a dispersion process on the vertices of the hypergraph that might be of independent interest. We bound the {em Mixing-time} of this process as a function of the second smallest eigenvalue of the Laplacian operator. All these results are generalizations of the corresponding results for graphs. We show that there can be no linear operator for hypergraphs whose spectra captures hypergraph expansion in a Cheeger-like manner. For any $k$, we give a polynomial time algorithm to compute an approximation to the $k^{th}$ smallest eigenvalue of the operator. We show that this approximation factor is optimal under the SSE hypothesis (introduced by cite{rs10}) for constant values of $k$. Finally, using the factor preserving reduction from vertex expansion in graphs to hypergraph expansion, we show that all our results for hypergraphs extend to vertex expansion in graphs.

Recommendations

• Spectral properties of hypergraph Laplacian and approximation algorithms
• Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
• Eigenvalues and linear quasirandom hypergraphs
• Laplacian eigenvalues and partition problems in hypergraphs
• New Hilbert space tools for analysis of graph Laplacians and Markov processes
• On the Laplacian Eigenvalues and Metric Parameters of Hypergraphs
• Markov chains on hypercubes: Spectral representations and several majorization relations
• On the problem of approximating the eigenvalues of undirected graphs in probabilistic logspace
• The Markov chain asymptotics of random mapping graphs

Cites work

• Approximate distance oracles
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast C-K-R partitions of sparse graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On approximate distance labels and routing schemes with affine stretch
• On sparse spanners of weighted graphs
• Ramsey partitions and proximity data structures
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Shortest-path queries in static networks

Cited in

(20)

• A Cheeger cut for uniform hypergraphs
• Finding Cheeger cuts in hypergraphs via heat equation
• Polynomial-time algorithms for submodular Laplacian systems
• Diffusion operator and spectral analysis for directed hypergraph Laplacian
• Approximation algorithms for hypergraph small-set expansion and small-set vertex expansion
• Approximations for the isoperimetric and spectral profile of graphs and related parameters
• Approximation algorithms for hypergraph small set expansion and small set vertex expansion
• scientific article; zbMATH DE number 3968498 (Why is no real title available?)
• Spectral properties of hypergraph Laplacian and approximation algorithms
• Cheeger inequalities for submodular transformations
• Comparing the principal eigenvector of a hypergraph and its shadows
• Nonlinear evolution equation associated with hypergraph Laplacian
• Weak Kantorovich difference and associated Ricci curvature of hypergraphs
• Local community detection by random walk on hypergraphs
• Cheeger's inequalities for vertex expansion and reweighted eigenvalues
• Eigenvalue approach to dense clusters in hypergraphs
• Sublinear time hypergraph sparsification via cut and edge sampling queries
• Submodular hypergraph partitioning: metric relaxations and fast algorithms via an improved cut-matching game
• Expansion in matrix-weighted graphs
• Networks beyond pairwise interactions: structure and dynamics

Describes a project that uses

Uses Software

• Graphs

This page was built for publication: Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms

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