Multi-linear pseudo-PageRank for hypergraph partitioning

DOI10.1007/S10915-024-02460-1MaRDI QIDQ6123354zbMATH OpenOpenAlexFDO

Authors Yannan Chen, Wen Li, Jingya Chang

Publication date 4 March 2024

Published in Journal of Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2306.10495

zbMATH Keywords

convergenceexistencehypergraphhypergraph partitioningLaplacian tensormulti-linear systemnetwork analysisPageRankperturbation analysissplitting algorithmuniqueness

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Multilinear algebra, tensor calculus (15A69) Numerical analysis or methods applied to Markov chains (65C40) Iterative numerical methods for linear systems (65F10) Computational methods for sparse matrices (65F50) Numerical computation of solutions to systems of equations (65H10) Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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.

Recommendations

• Multilinear PageRank
• Scalable tensor methods for nonuniform hypergraphs
• Vector Aitken extrapolation method for multilinear PageRank computations
• Multilinear PageRank: uniqueness, error bound and perturbation analysis
• The Fiedler vector of a Laplacian tensor for hypergraph partitioning

Cites work

• A continuum limit for the PageRank algorithm
• A note on certain ergodicity coefficients
• A Reordering for the PageRank Problem
• Convergence of the fixed‐point iteration for multilinear PageRank
• Empirical Analysis of an Evolving Social Network
• Ergodicity Coefficients for Higher-Order Stochastic Processes
• Extrapolation methods for fixed‐point multilinear PageRank computations
• Google's PageRank and beyond. The science of search engine rankings
• Laplacians and the Cheeger inequality for directed graphs
• Local Partitioning for Directed Graphs Using PageRank
• Multilinear PageRank
• Multilinear PageRank: uniqueness, error bound and perturbation analysis
• Newton-noda iteration for finding the Perron pair of a weakly irreducible nonnegative tensor
• Non-backtracking PageRank
• On the limiting probability distribution of a transition probability tensor
• On the uniqueness and non-uniqueness of the positive \(\mathcal Z\)-eigenvector for transition probability tensors
• PageRank beyond the web
• PageRank Computation, with Special Attention to Dangling Nodes
• Perron-based algorithms for the multilinear PageRank
• Relaxation methods for solving the tensor equation arising from the higher‐order Markov chains
• Some bounds for the spectral radius of nonnegative tensors
• Spectra of uniform hypergraphs
• Spectral radius on linear \(r\)-graphs without expanded \(K_{r+1}\)
• Tensor analysis. Spectral theory and special tensors
• The $25,000,000,000 Eigenvector: The Linear Algebra behind Google
• The Fiedler vector of a Laplacian tensor for hypergraph partitioning
• The perturbation bound for the Perron vector of a transition probability tensor.
• The Spacey Random Walk: A Stochastic Process for Higher-Order Data
• The uniqueness of multilinear PageRank vectors.
• Three hypergraph eigenvector centralities
• Truncated and sparse power methods with partially updating for large and sparse higher-order PageRank problems
• Using PageRank to Locally Partition a Graph

This page was built for publication: Multi-linear pseudo-PageRank for hypergraph partitioning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6123354)