2023/06/18 by Yannan Chen, Wen Li, Chen, Yannan +3
Computer Science · Mathematics · #FOS: Mathematics #Graph Theory and Algorithms #Matrix Theory and Algorithms #Optimization and Control (math.OC) #Tensor decomposition and applications
paper · pdf · doi:10.48550/arxiv.2306.10495
openalex publication_date 2023/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Motivated by the PageRank model for graph partitioning, we develop an extension of PageRank for partitioning uniform hypergraphs. Starting from adjacency tensors of uniform hypergraphs, we establish the multi-linear pseudo-PageRank (MLPPR) model, which is formulated as a multi-linear system with nonnegative constraints. The coefficient tensor of MLPPR is a kind of Laplacian tensors of uniform hypergraphs, which are almost as sparse as adjacency tensors since no dangling corrections are incorporated. Furthermore, all frontal slices of the coefficient tensor of MLPPR are M-matrices. Theoretically, MLPPR has a solution, which is unique under mild conditions. An error bound of the MLPPR solution is analyzed when the Laplacian tensor is slightly perturbed. Computationally, by exploiting the structural Laplacian tensor, we propose a tensor splitting algorithm, which converges linearly to a solution of MLPPR. Finally, numerical experiments illustrate that MLPPR is powerful and effective for hypergraph partitioning problems.