TY - JOUR
AU - Chen, Yannan
AU - Li, Wen
AU - Chang, Jingya
PY - 2024
DA - 2024/02/26
TI - Multi-Linear Pseudo-PageRank for Hypergraph Partitioning
JO - Journal of Scientific Computing
SP - 7
VL - 99
IS - 1
AB - 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 effective and efficient for hypergraph partitioning problems.
SN - 1573-7691
UR - https://doi.org/10.1007/s10915-024-02460-1
DO - 10.1007/s10915-024-02460-1
ID - Chen2024
ER -