Multi-Linear Pseudo-PageRank for Hypergraph Partitioning

PageRank is the first and best-known method developed by Google to evaluate the importance of web-pages via their inherent graph and network structures BP'98 ; BL'06 . There are three advantages of PageRank: existence and uniqueness of the PageRank solution, fast algorithms for finding the PageRank solution, and a built-in regularization Gl'15 . Thus, PageRank and its generalizations have been extensively used in network analysis, image sciences, sports, biology, chemistry, mathematical systems, and so on Gl'15 ; LM'06 . Hypergraphs have the capability of modeling connections among objects according to their inherent multiwise similarity and affinity. Recently, higher-order organization of complex networks at the level of small network subgraphs becomes an active research area BGL16 ; BGL'17 ; KW06 ; RELWL14 . The set of small network subgraphs with common connectivity patterns in a complex network could be modeled by a uniform hypergraph. A natural question is how can we generalize the PageRank idea from graphs to uniform hypergraphs.

PageRank was originally interpreted as a special Markov chain LM'06 , where the transition probability matrix is a columnwise-stochastic matrix. Many algorithms, e.g., power methods, were employed to find the dominant eigenvector of the PageRank eigensystem IS08 . Alternatively, PageRank could be represented as a linear system with an M-matrix, which has favorable theoretical character F15 and good numerical performance LM06 . In the context of PageRank for partitioning a graph, although a Laplacian matrix of the graph is an M-matrix, an adjacency matrix of the graph is not necessarily columnwise-stochastic, when the graph has dangling vertices Ch'05 . Some traditional approaches ACL'07 ; ACL'08 ; Gl'15 ; LM06 incorporated a rank-one correction into a graph adjacency matrix and thus produced a columnwise-stochastic matrix. Using this columnwise-stochastic matrix, PageRank generates the stochastic solution. However, the rank-one correction of the graph adjacency matrix has no graphic meaning. Alternatively, following the framework of M-linear systems, Gleich Gl'15 used the graph Laplacian matrix, which is only columnwise-substochastic, to construct a pseudo-PageRank model. The pseudo-PageRank model outputs the nonnegative solution, which is normalized to obtain the stochastic solution if necessary. Pseudo-PageRank comes from a graph Laplacian matrix directly and is more suitable for practical applications LM06 ; Gl'15 . Moreover, the pseudo-PageRank model is potentially true of the multi-linear cases. This is the primary motivation of this paper.

To explore higher-order extensions of classical Markov chain and PageRank for large-scale practical problems, on one hand, Li and Ng LN'14 used a rank-one array to approximate the limiting probability distribution array of a higher-order Markov chain. The vector for generating the rank-one array is called the limiting probability distribution vector of the higher-order Markov chain. On the other hand, Benson et al. BGL'17 studied the spacey random surfer, which remembers bits and pieces of history and is influenced by this information. Motivated by the spacey random surfer, Gleich et al. GLY'15 developed the multi-linear PageRank (MPR) model, of which the stochastic solution is called a multi-linear PageRank vector. Indeed, the multi-linear PageRank vector could be viewed as a limiting probability distribution vector of a special higher-order Markov chain.

According to the Brouwer fixed-point theorem, a stochastic solution of MPR always exists GLY'15 . The uniqueness of MPR solutions and related problems are more complicated than that of the classical PageRank. Many researchers gave various sufficient conditions CZ'13 ; FT'20 ; GLY'15 ; LLNV'17 ; LLVX'20 ; LN'14 . Dynamical systems of MPR were studied in BGL'17 . The perturbation analysis and error bounds of MPR solutions were presented in LCN'13 ; LLVX'20 . The ergodicity coefficient to a stochastic tensor was addressed in FT'20 . Interestingly, Benson B'19 studied three eigenvector centralities corresponding to tensors arising from hypergraphs. Tensor eigenvectors determine MPR vectors of these stochastic processes and capture some important higher-order network substructures BGL'15 ; BGL'17 .

For solving MPR and associated higher-order Markon chains, Li and Ng LN'14 proposed a fixed-point iteration, which converges linearly when a sufficient condition for uniqueness holds. Gleich et al. GLY'15 studied five numerical methods: a fixed-point iteration, a shifted fixed-point iteration, a nonlinear inner-outer iteration, an inverse iteration, and a Newton iteration. Meini and Poloni MP'18 solved a sequence of PageRank subproblems for Perron vectors to approximate the MPR solution. Furthermore, Huang and Wu HW'21 analyzed this Perron-based algorithm. Liu et al. LLV'19 designed and analyzed several relaxation algorithms for solving MPR. Cipolla et al. CRT'20 introduced extrapolation-based accelerations for a shifted fixed-point method and an inner-outer iteration. Hence, it is an active research area to compute MPR vectors arising from practical problems.

Before starting, we introduce our notations and definitions. We denote scalars, vectors, matrices, and tensors by lower case ($a$), bold lower case ($\mathbf{a}$), capital case ($A$), and calligraphic script ($\mathcal{A}$), respectively. Let $\mathbb{R}^{[k,n]}$ be the space of $k$th order $n$ dimensional real tensors and let $\mathbb{R}^{[k,n]}_{+}$ be the set of nonnegative tensors in $\mathbb{R}^{[k,n]}$. A tensor $\mathcal{P}\in\mathbb{R}^{[k,n]}$ is called semi-symmetric if all of its elements $p_{i_{1}i_{2}\dots i_{k}}$ are invariant for any permutations of the second to the last indices $i_{2},\dots,i_{k}$.

For $s\in\{1,\dots,k\}$, the $s$-mode product of $\mathcal{P}\in\mathbb{R}^{[k,n]}$ and $\mathbf{x}\in\mathbb{R}^{n}$ produces a $(k-1)$th order $n$ dimensional tensor $\mathcal{P}\bar{\times}_{s}\mathbf{x}$ of which elements are defined by

For convenience, we define $\mathcal{P}\mathbf{x}^{k-s}:=\mathcal{P}\bar{\times}_{s+1}\mathbf{x}\cdots\bar{\times}_{k}\mathbf{x}$. Particularly, $\mathcal{P}\mathbf{x}^{k-1}$ and $\mathcal{P}\mathbf{x}^{k-2}$ are a vector and a matrix, respectively. For a $k$th order tensor $\mathcal{X}$ and an $\ell$th order tensor $\mathcal{Y}$, the tensor outer product $\mathcal{X}\circ\mathcal{Y}$ is a $(k+\ell)$th order tensor, of which elements are

Particularly, when $k=\ell=1$, the outer product of two vectors $\mathbf{x}$ and $\mathbf{y}$ is a rank-one matrix $\mathbf{x}\circ\mathbf{y}=\mathbf{x}\mathbf{y}^{T}$.

Let $\mathbf{e}_{n}:=(1,1,\dots,1)^{T}\in\mathbb{R}^{n}$ be an all-one vector. For convenience, we denote $\mathbf{e}=\mathbf{e}_{n}$. If $\mathbf{v}\in\mathbb{R}^{n}_{+}$ satisfies $\mathbf{e}^{T}\mathbf{v}=1$, $\mathbf{v}$ is called a stochastic vector. The $1$-mode unfolding of a tensor $\mathcal{P}\in\mathbb{R}^{[k,n]}$ is an $n$-by-$n^{k-1}$ matrix $\mathbf{R}(\mathcal{P})$ of which elements are

Each column of $\mathbf{R}(\mathcal{P})$ is called a mode-1 (column) fiber of the tensor $\mathcal{P}$. If all of column fibers of $\mathcal{P}$ are stochastic, i.e., $\mathcal{P}\in\mathbb{R}^{[k,n]}_{+}$ and $\mathbf{e}^{T}\mathbf{R}(\mathcal{P})=\mathbf{e}^{T}_{n^{k-1}}$, $\mathcal{P}$ is called a columnwise-stochastic tensor. $\mathcal{P}$ is said to be a columnwise-substochastic tensor if $\mathcal{P}\in\mathbb{R}^{[k,n]}_{+}$ and $\mathbf{e}^{T}\mathbf{R}(\mathcal{P})\leq\mathbf{e}^{T}_{n^{k-1}}$. Obviously, a columnwise-stochastic tensor is columnwise-substochastic and not conversely. In the remainder of this paper, a fiber refers to a mode-1 (column) fiber. For given indices $i_{3},\dots,i_{k}$, an $n\times n$ matrix $(p_{iji_{3}\dots i_{k}})_{i,j=1,\dots,n}$ is called a frontal slice of a tensor $\mathcal{P}\in\mathbb{R}^{[k,n]}$.

Next, we briefly review PageRank for directed graphs. A directed graph $G=(V,\vec{E},\mathbf{w})$ contains a vertex set $V:=\{1,2,\dots,n\}$, an arc set $\vec{E}:=\{\vec{e}_{1},\vec{e}_{2},\dots,\vec{e}_{m}\}$, and a weight vector $\mathbf{w}\in\mathbb{R}^{m}_{+}$. A component $w_{\ell}$ of $\mathbf{w}$ stands for the weight of an arc $\vec{e}_{\ell}$ for $\ell=1,\dots,m$. An arc $\vec{e}=(j,i)\in\vec{E}$ means an directed edge $(j,i)$ from vertex $j$ to vertex $i$, where $j$ has an out-neighbor $i$ and $i$ has an in-neighbor $j$. The out-degree $d^{\mathrm{out}}_{j}$ of $j\in V$ is defined by the sum of weights of arcs that depart from $j$:

If $d^{\mathrm{out}}_{j}=0$, vertex $j$ is called a dangling vertex. Let the out-degree vector be $\mathbf{d}:=(d^{\mathrm{out}}_{j})\in\mathbb{R}^{n}_{+}$. The adjacency matrix $A=[a_{ij}]\in\mathbb{R}^{n\times n}$ of $G$ is defined with elements

Clearly, it holds that $\mathbf{d}^{T}=\mathbf{e}^{T}A$. Vertex $j\in V$ is dangling if and only if the $j$th column of the adjacency matrix $A$ is a dangling (zero) vector.

Let us consider the random walk (stochastic process) $\{X(t):t=0,1,2,\dots\}$ on the vertex set $V=\{1,2,\dots,n\}$ of a directed graph $G$. The random walk takes a step according to the transition probability (columnwise-stochastic) matrix $P=(p_{ij})\in\mathbb{R}^{n\times n}_{+}$ with probability $\alpha\in[0,1)$ and jumps randomly to a fixed distribution $\mathbf{v}=(v_{i})\in\mathbb{R}^{n}_{+}$ with probability $1-\alpha$, i.e.,

where $p_{ij}$ denotes the probability of a walk from vertex $j$ to vertex $i$. Here, $p_{ij}>0$ if and only if $(j,i)$ is an arc of $G$. If the out-degree vector $\mathbf{d}$ is positive, the normalized adjacency matrix $AD^{+}$ of $G$ is columnwise-stochastic, where $D:=\mathrm{diag}(\mathbf{d})$ and $(\cdot)^{+}$ stands for the Moore-Penrose pseudo-inverse. However, when the graph contains dangling vertices, the normalized adjacency matrix $AD^{+}$ is columnwise-substochastic but not columnwise-stochastic. Researchers Gl'15 ; LM06 incorporated a rank-one correction (named a dangling correction) into the columnwise-substochastic matrix to produce a columnwise-stochastic matrix:

where $\mathbf{u}\in\mathbb{R}^{n}$ is a stochastic vector, $\mathbf{c}^{T}:=\mathbf{e}^{T}-\mathbf{e}^{T}AD^{+}$ is an indicator vector of dangling columns of $A$ and thus $\mathbf{c}\in\{0,1\}^{n}$ is an indicator vector of dangling vertices in $V$. Here, $c_{j}=1$ if the $j$th column of $A$ is a zero vector and $j\in V$ is a dangling vertex, $c_{j}=0$ otherwise.

Let a stochastic vector $\mathbf{x}$ be a limiting probability distribution of the random walk $\{X(t)\}$. The random walk (1) could be represented as a classical PageRank:

It is well-known that the solution $\mathbf{x}$ of PageRank (2) could be interpreted as the Perron vector (the eigenvector corresponding to the dominant eigenvalue) of a nonnegative matrix, $(\alpha P+(1-\alpha)\mathbf{v}\mathbf{e}^{T})\mathbf{x}=\mathbf{x}$, or the solution of a linear system with its coefficient matrix being an M-matrix, $(I-\alpha P)\mathbf{x}=(1-\alpha)\mathbf{v}$, where $I\in\mathbb{R}^{n\times n}$ is the identity matrix. The linear system $(I-\alpha P)\mathbf{x}=(1-\alpha)\mathbf{v}$ with $\mathbf{u}=\mathbf{v}$ and $P=AD^{+}+\mathbf{u}\mathbf{c}^{T}$ for the graph PageRank could be simplified by finding the solution $\mathbf{y}\in\mathbb{R}^{n}_{+}$ of another structural linear system

and then normalizing solution $\mathbf{y}$ to obtain a stochastic vector $\mathbf{x}=\mathbf{y}/(\mathbf{e}^{T}\mathbf{y})$ Gl'15 . In fact, the system (3) is called a pseudo-PageRank problem. The coefficient matrix $I-\alpha AD^{+}$ is both an M-matrix and a Laplacian matrix of the graph YCO'21 , enjoying good properties from linear algebra and graph theory. It is interesting to note that the pseudo-PageRank model doesn’t need to do any dangling corrections. Indeed, dangling cases are inevitable for hypergraphs.

Spectral hypergraph theory made great progress in the past decade BP'13 ; CD'12 ; QL17book ; GCH22 . Let $G=(V,E,\mathbf{w})$ be a weighted undirected $k$-uniform hypergraph, where $V:=\{1,2,\dots,n\}$ is the vertex set, $E:=\{e_{j}\subseteq V:~{}\lvert e_{j}\rvert=k\text{ for }j=1,2,\dots,m\}$ is the edge set, and $\mathbf{w}=(w_{j})\in\mathbb{R}^{m}_{+}$ is a positive vector whose component $w_{j}$ denotes the weight of an edge $e_{j}\in E$. Here, $\lvert\cdot\rvert$ means the cardinality of a set. Cooper and Dutle CD'12 defined adjacency tensors of uniform hypergraphs.

Our MLPPR model could be applied in a weighted directed $k$-uniform hypergraph $G=(V,\vec{E},\mathbf{w})$ with a vertex set $V=\{1,2,\dots,n\}$, an arc set $\vec{E}:=\{\vec{e}_{1},\vec{e}_{2},\dots,\vec{e}_{m}\}$, and weights of arcs $\mathbf{w}\in\mathbb{R}^{m}_{+}$. An arc $\vec{e}_{j}\in\vec{E}$ is an ordered subset $\vec{e}_{j}:=(i_{j,1},i_{j,2},\dots,$ $i_{j,k})$ of $V$ for $j=1,2,\dots,m$. Here, vertices $i_{j,1},\dots,i_{j,k-1}$ are called tails of the arc $\vec{e}_{j}$ and the order among them are irrelevant. The last vertex $i_{j,k}$ is coined the head of the arc $\vec{e}_{j}$. Each arc $\vec{e}_{j}$ has a positive weight $w_{j}$ for $j=1,2,\dots,m$. Similarly, we define an adjacency tensor for the directed $k$-uniform hypergraph $G$ as follows.

Clearly, an adjacency tensor $\mathcal{A}$ of $G$ is semi-symmetric. We note that an edge $\{i_{1},\dots,i_{k}\}$ of an undirected hypergraph could be viewed as $k$ varieties of arcs: $(\sigma(i_{1},\dots,i_{k-1}),i_{k}),(\sigma(i_{k},i_{1},\dots,i_{k-2}),i_{k-1}),\dots,(\sigma(i_{2},\dots,i_{k}),i_{1})$ of a directed hypergraph. In this sense, Definitions 3.2 and 3.1 are consistent.

Next, we consider dangling fibers of an adjacency tensor arising from a uniform hypergraph. There are two kinds of dangling cases. (i) The structural dangling fibers are due to the definition of adjacency tensors of uniform hypergraphs. For example, since the 3-uniform hypergraph does not have edges/arcs with repeating vertices, elements $a_{ijj}$ of the associated adjacency tensor $\mathcal{A}$ are zeros for all $i$ and $j$. Hence, there are structural dangling fibers in adjacency tensors of any $k$-uniform hypergraphs with $k\geq 3$. We note that a graph has no structural dangling fibers. (ii) The sparse dangling fibers are generated by the sparsity of a certain uniform hypergraph. For a set of tail vertices $\{i_{1},\dots,i_{k-1}\}\subset V$, if there is no head vertex $i_{k}\in V$ such that $(\sigma(i_{1},\dots,i_{k-1}),i_{k})\in\vec{E}$, there exist sparse dangling fibers. Particularly, there are amount of dangling fibers in adjacency tensors of large-scale sparse hypergraphs. A complete hypergraph does not have any sparse dangling fibers but has structural dangling fibers.

To get rid of these dangling fibers that lead to a gap between Laplacian tensors of uniform hypergraphs and columnwise-stochastic tensors for higher-order extensions of PageRank, we are going to develop a novel MLPPR model. Following the spirit of the pseudo-PageRank model for graphs, we normalize all nonzero fibers of the adjacency tensor $\mathcal{A}$ of a uniform hypergraph $G$ to produce a columnwise-substochastic tensor $\bar{\mathcal{P}}=(\bar{p}_{i_{1}\dots i_{k}})\in\mathbb{R}^{[k,n]}_{+}$, of which elements are defined by

That is to say, we have $\mathbf{R}(\bar{\mathcal{P}})=\mathbf{R}(\mathcal{A})D^{+}\in\mathbb{R}^{n\times n^{k-1}}_{+}$, where $D:=\mathrm{diag}(\mathbf{e}^{T}\mathbf{R}(\mathcal{A}))$. Both an adjacency tensor $\mathcal{A}$ and its normalization $\bar{\mathcal{P}}$ are nonnegative tensors, which have interesting theoretical results LN15 .

As an analogue of the Laplacian matrix of a graph YCO'21 , we call

a Laplacian tensor of a $k$-uniform hypergraph $G$ with $n$ vertices, where $\alpha\in[0,1)$ is a probability and $\mathbf{e}^{\circ(k-2)}$ is the outer produce of $k-2$ copies of $\mathbf{e}$. Obviously, each frontal slice of this Laplacian tensor is an M-matrix. Now, we are ready to present the multi-linear pseudo-PageRank model.

Next, we show some properties of the multi-linear system of MLPPR.

On the other hand, From $\mathbf{y}_{*}=\Phi(\mathbf{y}_{*})$ we can derive

Then the equality (10) reduces to

which is equivalent to MLPPR (7).

The following theorem reveals the existence of nonnegative solutions of MLPPR.

According to the Brouwer fixed point theorem, there exists $\mathbf{y}_{*}\in\Delta$ such that $\Phi(\mathbf{y}_{*})=\mathbf{y}_{*}$. By Lemma 3.6, $\mathbf{y}_{*}$ is also a nonnegative solution of MLPPR.

On the uniqueness of MLPPR solution, we have theoretical results under some conditions. To move on, the following two lemmas are helpful.

For any $\mathbf{a},\mathbf{b}\in\Xi$, without loss of generality, we suppose $\mathbf{e}^{T}\mathbf{a}\geq\mathbf{e}^{T}\mathbf{b}\geq 1$. Then, we have

where the second and the third inequalities hold owing to (11) and (12), respectively.

For the special case of the pseudo-PageRank model for graphs, we know $k=2$. Then the condition $\varsigma<1$ reduces to a trivial condition $\alpha<1$. When $k=3$, the condition $\varsigma<1$ reduces to $\alpha<\frac{\sqrt{37}-1}{18}\approx 0.28$. Furthermore, the uniqueness of MLPPR solution follows this contraction theorem.

Whereafter, we will consider how perturbations in the columnwise-substochastic tensor $\bar{\mathcal{P}}$ and the stochastic vector $\mathbf{v}$ affect the MLPPR solution $\mathbf{y}$. Numerical verifications of this theorem will be illustrated in Subsection 5.1.