The fiedler vector of a laplacian tensor for hypergraph partitioning

Yannan Chen, Liqun Qi, Xiaoyan Zhang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

12 Citations (Scopus)

Abstract

Based on recent advances in spectral hypergraph theory [L. Qi and Z. Luo, Tensor Anaysis: Spectral Theory and Special Tensors, SIAM, Philadelphia, 2017], we explore the Fiedler vector of an even-uniform hypergraph, which is the Z-eigenvector associated with the second smallest Z-eigenvalue of a normalized Laplacian tensor arising from the hypergraph. Then, we develop a novel tensor-based spectral method for partitioning vertices of the hypergraph. For this purpose, we extend the normalized Laplacian matrix of a simple graph to the normalized Laplacian tensor of an even-uniform hypergraph. The corresponding Fiedler vector is related to the Cheeger constant of the hypergraph. Then, we establish a feasible optimization algorithm to compute the Fiedler vector according to the normalized Laplacian tensor. The convergence of the proposed algorithm and the probability of obtaining the Fiedler vector of the hypergraph are analyzed theoretically. Finally, preliminary numerical experiments illustrate that the new approach based on a hypergraph-based Fiedler vector is effective and promising for some combinatorial optimization problems arising from subspace partitioning and face clustering.
Original languageEnglish
Pages (from-to)A2508-A2537
JournalSIAM Journal on Scientific Computing
Volume39
Issue number6
DOIs
Publication statusPublished - 1 Jan 2017

Keywords

  • Eigenvalue
  • Eigenvector
  • Face clustering
  • Fiedler vector
  • Hypergraph partitioning
  • Laplacian tensor
  • Optimization

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics

Cite this