File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/3178123
- Scopus: eid_2-s2.0-85043497054
- WOS: WOS:000433477000004
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Spectral Properties of Hypergraph Laplacian and Approximation Algorithms
Title | Spectral Properties of Hypergraph Laplacian and Approximation Algorithms |
---|---|
Authors | |
Keywords | Approximation algorithms Hypergraph Laplacian |
Issue Date | 2018 |
Publisher | Association for Computing Machinery. The Journal's web site is located at http://jacm.acm.org/ |
Citation | Journal of the ACM, 2018, v. 65 n. 3, p. article no. 15 How to Cite? |
Abstract | 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 fromvertices having maximum weightedmeasure 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 expansionwith 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 fromvertex expansion in graphs to hypergraph expansion, we show that all our results for hypergraphs extend to vertex expansion in graphs. © 2018 ACM. |
Persistent Identifier | http://hdl.handle.net/10722/291052 |
ISSN | |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, TH | - |
dc.contributor.author | Louis, A | - |
dc.contributor.author | TANG, Z | - |
dc.contributor.author | ZHANG, C | - |
dc.date.accessioned | 2020-11-02T05:50:53Z | - |
dc.date.available | 2020-11-02T05:50:53Z | - |
dc.date.issued | 2018 | - |
dc.identifier.citation | Journal of the ACM, 2018, v. 65 n. 3, p. article no. 15 | - |
dc.identifier.issn | 1535-9921 | - |
dc.identifier.uri | http://hdl.handle.net/10722/291052 | - |
dc.description.abstract | 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 fromvertices having maximum weightedmeasure 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 expansionwith 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 fromvertex expansion in graphs to hypergraph expansion, we show that all our results for hypergraphs extend to vertex expansion in graphs. © 2018 ACM. | - |
dc.language | eng | - |
dc.publisher | Association for Computing Machinery. The Journal's web site is located at http://jacm.acm.org/ | - |
dc.relation.ispartof | Journal of the ACM | - |
dc.rights | Journal of the ACM. Copyright © Association for Computing Machinery. | - |
dc.rights | ©ACM, YYYY. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in PUBLICATION, {VOL#, ISS#, (DATE)} http://doi.acm.org/10.1145/nnnnnn.nnnnnn | - |
dc.subject | Approximation algorithms | - |
dc.subject | Hypergraph Laplacian | - |
dc.title | Spectral Properties of Hypergraph Laplacian and Approximation Algorithms | - |
dc.type | Article | - |
dc.identifier.email | Chan, TH: hubert@cs.hku.hk | - |
dc.identifier.authority | Chan, TH=rp01312 | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1145/3178123 | - |
dc.identifier.scopus | eid_2-s2.0-85043497054 | - |
dc.identifier.hkuros | 318360 | - |
dc.identifier.volume | 65 | - |
dc.identifier.issue | 3 | - |
dc.identifier.spage | article no. 15 | - |
dc.identifier.epage | article no. 15 | - |
dc.identifier.isi | WOS:000433477000004 | - |
dc.publisher.place | United States | - |