The celebrated Cheeger's Inequality (Alon and Milman 1985; Alon 1986) establishes a bound on the edge 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 article, we introduce a new hypergraph Laplacian operator generalizing the Laplacian matrix of graphs. In particular, the operator is induced by a diffusion process on the hypergraph, such that within each hyperedge, measure flows from vertices having maximum weighted measure to those having minimum. Since the operator is nonlinear, we have to exploit other properties of the diffusion process to recover the Cheeger's Inequality that relates hyperedge expansion with the "second eigenvalue" of the resulting Laplacian. However, we show that higher-order spectral properties cannot hold in general using the current framework. Since higher-order spectral properties do not hold for the Laplacian operator, we instead use the concept of procedural minimizers to consider higher-order Cheeger-like inequalities. For any k ∈ N, we give a polynomial-time algorithm to compute an O (log r )-approximation to the kth procedural minimizer, where r is the maximum cardinality of a hyperedge. We show that this approximation factor is optimal under the SSE hypothesis (introduced by Raghavendra and Steurer (2010)) for constant values of k. Moreover, 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. Spectral Properties of Hypergraph Laplacian and Approximation Algorithms This tensor form and its minor variants have been explored in the literature (see Section 1.1 for a brief survey) but have not been understood very well. Optimizing over tensors is NP-hard (Hillar and Lim 2013); even getting good approximations might be intractable (Brubaker and Vempala 2009). Moreover, the spectral properties of tensors seem to be unrelated to combinatorial properties of hypergraphs (see Chan et al. (2016, Appendix A)). Another way to study a hypergraph, say, H = (V , E), is to replace each hyperedge e ∈ E by a complete 2-graph or a low-degree expander on the vertices of e to obtain a 2-graph G = (V , E ). If we let r denote the size of the largest hyperedge in E, then it is easy to see that the combinatorial properties of G and H , like min-cut and sparsest-cut, among others, could be separated by a factor of Ω(r ). Therefore, this approach will not be useful when r is large. In general, one cannot hope to have a linear operator for hypergraphs whose spectra capture hypergraph expansion in a Cheeger-like manner. This is because the existence of such an operator will imply the existence of a polynomial-time algorithm obtaining an O( √ OPT) bound on hypergraph expansion, but we rule this out by giving a lower bound of Ω( OPT log r ) for computing hypergraph expansion, where r is the size of the largest hyperedge (Theorem 3.10). Our main contribution is the definition of a new Laplacian operator for hypergraphs, obtained by generalizing the random-walk operator on graphs. Our operator does not require the hypergraph to be uniform (i.e., does not require all the hyperedges to have the same size). We describe this operator in Section 4 (see also Figure 1 ). We present our main results about this hypergraph operator in Section 4 and Section 5. Most of our results are independent of r (the size of the hyperedges), some of our bounds have a logarithmic dependence on r , and none of our bounds have a polynomial dependence on r . All our bounds are generalizations of the corresponding bounds for 2-graphs. Friedman and Wigderson (1995) studied the canonical tensors of hypergraphs. They bounded the second eigenvalue of such tensors for hypergraphs drawn randomly from various distributions and showed their connections to randomness dispersers. Rodriguez (2009) studied the eigenvalues of a graph obtained by replacing each hyperedge by a clique (note that this step incurs a loss of O(r 2 ), where r is the size of the hyperedge). Cooper and Dutle (2012) studied the roots of the characteristic polynomial of hypergraphs and related it to its chromatic number. Qi (2014, 2015) also studied the canonical tensor form of the hypergraph and related its eigenvectors to some configured components of that hypergraph. Lenz and Mubayi (2012 , 2015 related the eigenvector corresponding to the second-largest eigenvalue of the canonical tensor to hypergraph quasi-randomness. Chung (1993) defined a notion of Laplacian for hypergraphs and studied the relationship between its eigenvalues and a very different notion of hypergraph cuts and homologies. , , Parzanchevski (2013), Kaufman et al. (2014), and Steenbergen et al. (2014) studied the relation of simplicial complexes with rather different notions of Laplacian forms and considered isoperimetric inequalities, homologies, and mixing times. Ene and Nguyen (2014) studied the hypergraph multiway partition problem (generalizing the graph multiway partition problem) and gave a 4 3 -approximation algorithm for 3-uniform hypergraphs. Furthermore, Louis and Makarychev (2014b) gave approximation algorithms for hypergraph expansion and, more generally, hypergraph small-set expansion; they gave anÕ(k log n)-approximation algorithm and anÕ(k OPT log r ) approximation bound for the problem of computing the set of vertices of size at most |V |/k in a hypergraph H = (V , E), having the least expansion. Bobkov et al. (2000) defined a Poincairé-type functional graph parameter called λ ∞ and showed that it relates to the vertex expansion of a graph in a Cheeger-like manner; i.e., it satisfies 1 2 f = x, we have R w ( f ) = R (x ). Given a set S of vectors in the normalized space, Π S is the orthogonal projection operator onto the subspace spanned by S. The orthogonal projection operator Π w S can also be defined for the weighted space. A major contribution of this article is to define a hypergraph Laplacian operator L whose spectral properties are related to the expansion properties of the underlying hypergraph.
This embedding was also used to achieve O( √ log n log r · log log n)-approximation for the general demands case in undirected hypergraphs REF , where r is the maximum cardinality of an hyperedge.
Spectral Properties of Hypergraph Laplacian and Approximation Algorithms
JACM
Computer Science Mathematics