The Fiedler Vector of a Laplacian Tensor for Hypergraph Partitioning

Authors:
  • YCYannan Chen
    Yannan Chen
  • LQLiqun Qi
    Liqun Qi
  • XZXiaoyan Zhang
    Xiaoyan Zhang
Publisher website
Google Scholar
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 a...
Funding Information
  • Qinglan Project of Jiangsu Province of China
  • National Natural Science Foundation of China (11401539, 11471003, 11771405)
  • Research Grants Council, University Grants Committee (501212, 501913, 15302114, 15300715)
  • Zhengzhou University (1421315070)

This publication has 54 references indexed in Scilit: