基于随机算法求解多重线性PageRank问题

The Random Algorithm for Solving Multilinear PageRank Problem

摘要: 本文针对多重线性PageRank问题，采用随机算法求解该模型，给出收敛性定理，并通过数值实验说明随机算法求解多重线性PageRank问题的有效性。

Abstract: This paper focuses on the multilinear PageRank problem, adopts the random algorithms to solve the problem, presents the convergence theorem, and demonstrates the effectiveness of the random algorithms in solving the multilinear PageRank problem through numerical experiments.

1. 引言

Google首次提出PageRank模型来决定一个代表网页的有向图的重要节点，即网页排序问题[1]。给定一个有向图的随机行走，修正后的PageRank模型建立一个存在唯一稳定分布的马尔科夫链。由于PageRank模型的广泛成功，再根据如今实际应用中高维数据的需要，Gleich等[2]提出了高阶PageRank问题，它是一阶问题的推广。与此同时他们也发现了高阶PageRank的存储障碍[2]，之后，他们根据秩1对称近似估计，希望利用这种估计的存储量小的优势，进一步提出多重线性PageRank模型。

Gleich等[2]基于秩1近似估计技术提出多重线性PageRank问题：令$P$ 是一个$m$ 阶随机张量，概率$\alpha \in \left(0,1\right)$ ，$v$ 是一个随机向量，则多重线性PageRank问题定义如下：

$x=\alpha P{x}^{m-1}+\left(1-\alpha \right)v$ , (1)

其中，$x$ 是所求的随机向量(被称为多重线性PageRank向量)，并且

$P{x}^{m-1}={\displaystyle \sum _{i_2,i_3,\cdots ,i_m}^n{p}_{i{i}_2\dots i_m}}{x}_{i_2}\cdots x_{i_m}$ .

近年来，随着对多重线性PageRank问题研究的不断深入，诸多学者纷纷涌现出创新性的求解方法。这些方法旨在更高效地处理复杂网络中的多重线性关系、以更短的计算时间和更少的迭代次数求出多重线性PageRank值。例如，Bucci和Poloni [3]提出了一种计算多重线性PageRank的延拓方法：预测校正延拓算法。Meini和Poloni [4]利用二次向量方程理论，提出了基于perron的多重线性PageRank算法。Cipolla等人[5]通过采用重新启动形式的简化拓扑–算法，引入了不动点多重线性PageRank计算的外推方法。Boubekraoui等人[6]提出了一种利用向量Aitken外推技术计算多重线性PageRank向量的新方法。Lai等[7]将Anderson加速技术集成到现有的松弛不动点迭代中，用于计算多重线性PageRank问题。Zhou等[8]基于[1]中的不动点迭代和内外迭代，提出了一种两步迭代法(FPIO)来计算多重线性PageRank问题。然后考虑多步不动点迭代，并将其作为内外迭代的前提条件，给出了一种新方法：MFPIO算法，该方法可以看作是FPIO方法的扩展。此外，将最小多项式外推(MPE)作为不动点迭代的加速技术以加快多重线性PageRank向量的计算速度，从而提出了一种新方法：FPMPE算法。针对多重线性PageRank问题，结合松弛技术，提出了新的张量分裂算法。Bentbib等人[9]提出了一些向量外推方法，如最小多项式外推(MPE)和降秩外推(RRE)可以用来加速定点多重线性PageRank的计算。

本文的主要贡献：1) 提出了采用随机算法求解多重线性PageRank问题；2) 给出数值实验说明随机算法求解多重线性PageRank问题的有效性。

2. 预备知识

首先介绍本文用到的符号和基本知识。令$\Vert \cdot \Vert$ 表示欧氏范数，矩阵$A$ 的F范数为${\Vert A\Vert }_F=\sqrt{{\displaystyle {\sum }_{i,j}{A}_{ij}^2}}$ ，$A^{+}$ 表示矩阵$A$ 的广义逆，${\Vert A^{+}\Vert }_2=\frac{1}{{\delta }_{\min }}$ ，${\delta }_{\min }$ 为矩阵$A$ 的最小非零奇异值，$k_F\left(A\right)={\Vert A\Vert }_F{\Vert A^{+}\Vert }_2$ 。令$x\in {ℝ}^n$ ，当向量$x$ 满足$x\ge 0$ 且${\Vert x\Vert }_1=1$ 时，称$x$ 为随机向量。$P$ 是一个$m$ 阶$n$ 维张量，$P=\left(p_{i_1{i}_2\cdots i_m}\right)$ ，$\left(p_{i_1{i}_2\cdots i_m}\right)\in ℝ$ ，$i_1,i_2,\cdots ,i_m\in n$ 。

对于多重线性PageRank问题(1.1)，与它等价的另一个形式为：

$x=\alpha R\underset{m-1}{\underbrace{\left(x\otimes \cdots \otimes x\right)}}+\left(1-\alpha \right)v$ , (2)

其中$\otimes$ 为Kronecker积，$R$ 为(1.1)中张量$P$ 的模1展开。令$P$ 为一个三阶$n$ 维随机张量，即$P=\left(p_{ijk}\right)\in {ℝ}^{\left[3,n\right]}$ ，其模1展开如下：

$P_{(1)}=\left[\begin{array}{ccccccccc}{p}_{111}& \cdots & p_{1n1}& p_{112}& \cdots & p_{1n2}& p_{11n}& \cdots & p_{1nn}\\ p_{211}& \cdots & p_{2n1}& p_{212}& \cdots & p_{2n2}& p_{21n}& \cdots & p_{2nn}\\ ⋮& \ddots & ⋮& ⋮& \ddots & ⋮& ⋮& \ddots & ⋮\\ p_{n11}& \cdots & p_{nn1}& p_{n12}& \cdots & p_{nn2}& p_{n1n}& \cdots & p_{nnn}\end{array}\right]$

给定一个向量$x\in {ℝ}^n$ ，$P\in {ℝ}^{\left[m,n\right]}$ ，$P{x}^{m-1}$ 的计算结果为一个向量，即$P{x}^{m-1}\in {ℝ}^n$ ，该向量具体的项为：

${\left(P{x}^{m-1}\right)}_i={\displaystyle \sum _{i_2,\cdots ,i_m=1}^n{p}_{i{i}_1\cdots i_m}}{x}_{i_2}\cdots x_{i_m},i=1,\cdots ,n.$

$P{x}^{m-2}\in {ℝ}^{n\times n}$ 为矩阵，该矩阵定义如下；

${\left(P{x}^{m-2}\right)}_{i_1{i}_2}={\displaystyle \sum _{i_3,\cdots ,i_m=1}^n{p}_{i_1{i}_2\cdots i_m}}{x}_{i_3}\cdots x_{i_m},1\le i_1,i_2\le n.$

3. 收敛性定理

定义3：[10]若对于每个$i\in \left\{1,2,\cdots ,m\right\}$ 且$\forall x_1,x_2\in {ℝ}^n$ ，存在常数${\eta }_i\in \left[0,\eta \right)$ ，($\eta =\underset{i}{\max }{\eta }_i<\frac{1}{2}$ )，使得以下式子成立：

$\left|f_i\left(x_1\right)-f_i\left(x_2\right)-\nabla f_i\left(x_1\right)\left(x_1-x_2\right)\right|\le {\eta }_i\left|f_i\left(x_1\right)-f_i\left(x_2\right)\right|$

则称函数$f:{ℝ}^n\to {ℝ}^m$ 满足局部切向锥条件。

引理3：如果函数$f$ 满足局部切向锥条件，对于每个$1\le i\le m$ 以及$\forall x_1,x_2\in {ℝ}^n$ ，有以下式子成立：

$\frac{1}{1+{\eta }_i}\left|\nabla f_i\left(x_1\right)\left(x_1-x_2\right)\right|\le \left|f_i\left(x_1\right)-f_i\left(x_2\right)\right|$

定理3：对于非线性问题$f\left(x\right)=0$ ，函数$f:D\subseteq {ℝ}^n\to {ℝ}^m$ 的定义域$D$ 是有界闭集，并且有$x_{*}\in {ℝ}^n$ 使得$f\left(x_{*}\right)=0$ 。若函数$f$ 的偏导函数连续且对于$\forall x\in D$ ，$f^{\prime }\left(x\right)$ 均为列满秩的行下有界矩阵，对于每个$i\in \left\{1,2,\cdots ,m\right\}$ ，函数$f_i\left(x\right)$ 满足局部切向锥条件，$\eta =\underset{i}{\max }{\eta }_i$ ，($\eta <\frac{1}{2}$ )，则NRK算法依期望线性收敛

$E{\Vert x_k-x_{*}\Vert }^2\le \frac{1-2\eta }{m{\left(1+\eta \right)}^2{k}_F^2\left(f^{\prime }\left(x_{k-1}\right)\right)}E{\Vert x_{k-1}-x_{*}\Vert }^2$

4. 提出的算法

通过深入钻研求解大规模线性问题的Kaczmarz算法及其随机版本，王等[10]将Kaczmarz算法及其随机化版本的迭代思路以及随机选择概率引入到大规模非线性问题的求解中，根据所选择的随机选择投影行的概率方式的不同，提出的三种非线性Kaczmarz算法，分别是非线性Kaczmarz算法(NK)、非线性随机Kaczmarz算法(NRK)、非线性均匀随机Kaczmarz算法(NURK)。本文利用这三种非线性Kaczmarz算法求解多重线性PageRank问题，并通过数值实验验证求解的有效性。

令$x\in {ℝ}^n$ ，且$x_{+}=\max \left(x,0\right)$ 为非零向量，定义投影算子如下：

$proj\left(x\right)=\frac{x_{+}}{{\Vert x_{+}\Vert }_1}.$

易证$proj\left(x\right)$ 是随机向量。

对于多重线性PageRank问题$x=\alpha P{x}^{m-1}+\left(1-\alpha \right)v$ ，令$f\left(x\right)=x-\alpha P{x}^{m-1}-\left(1-\alpha \right)v$ ，下面给出求解多重线性PageRank问题的三种算法框架(算法1~3)：

算法1. 非线性Kaczmarz (NK)算法

1：给定$f\left(x\right)$ ，初始值$x_0$ ，停机误差$\epsilon$ ，最大迭代步数$k_{\max }$ ，$r=f\left(x\right)$ ，令$k=0$ 2：while $\Vert r\Vert >\epsilon$ & $k<k_{\max }$ 3：取$i=\mathrm{mod}\left(k,m\right)+1$ 4：梯度计算$g_i=\nabla f_i\left(x_k\right)$ 5：迭代$x_{k+1}=x_k-\frac{r\left(i\right)}{\Vert g_i\Vert }{g}_i$ 6：$k=k+1$ 7：计算残差$r=f\left(x_k\right)$ 8：end while 9：输出$x_k$

算法2. 非线性随机Kaczmarz (NRK)算法

1：给定$f\left(x\right)$ ，初始值$x_0$ ，停机误差$\epsilon$ ，最大迭代步数$k_{\max }$ ，$r=f\left(x\right)$ ，令$k=0$ 2：while $\Vert r\Vert >\epsilon$ & $k<k_{\max }$ 3：依概率$p_i=\frac{{\left|f_i\left(x\right)\right|}^2}{{\Vert f\left(x\right)\Vert }^2}$ 选择行指标$i\in \left\{1,2,\cdots ,m\right\}$ 4：梯度计算$g_i=\nabla f_i\left(x_k\right)$ 5：迭代$x_{k+1}=x_k-\frac{r\left(i\right)}{\Vert g_i\Vert }{g}_i$ 6：$k=k+1$ 7：计算残差$r=f\left(x_k\right)$ 8：end while 9：输出$x_k$

算法3. 非线性均匀随机Kaczmarz (NURK)算法

1：给定$f\left(x\right)$ ，初始值$x_0$ ，停机误差$\epsilon$ ，最大迭代步数$k_{\max }$ ，$r=f\left(x\right)$ ，令$k=0$ 2：while $\Vert r\Vert >\epsilon$ & $k<k_{\max }$ 3：依概率$p_i=unidrnd\left(m,1,1\right)$ 选择行指标$i\in \left\{1,2,\cdots ,m\right\}$ 4：梯度计算$g_i=\nabla f_i(x_k)$ 5：迭代$x_{k+1}=x_k-\frac{r\left(i\right)}{\Vert g_i\Vert }{g}_i$ 6：$k=k+1$ 7：计算残差$r=f\left(x_k\right)$ 8：end while 9：输出$x_k$

记$f\left(x\right)={\left(f_1\left(x\right),\cdots ,f_m\left(x\right)\right)}^{\text{T}}$ ，$f^{\prime }\left(x\right)$ 为在点$x$ 的偏导数矩阵。$\nabla f_i\left(x\right)$ 是偏导数矩阵$f^{\prime }\left(x\right)$ 的第$i$ 行。

5. 数值实验

基于多重线性PageRank问题，我们将通过数值实验来验证所提出算法的有效性。主要从迭代步数(IT)，以秒为单位的迭代时间(CPU)，误差(err)这三个方面来检验所提算法的效率。其中，误差err定义如下

$err=\Vert x-\alpha P{x}^{m-1}-\left(1-\alpha \right)v\Vert$ ,

停机误差为$err={10}^{-10}$ ，最大迭代步数设置为30,000，选取参数$\alpha$ 为$\alpha =0.95$ ，初始值为$x_0=\left(\frac{1}{n},\frac{1}{n},\cdots ,\frac{1}{n}\right)$ ，$n$ 为张量的维数。实验是在一台配备1.80 GHz 4核Intel (R) Core (TM) i5-8250U CPU以及8 GB 2400 MHz DDR3内存的计算机上，使用MATLAB (版本R2018a)进行的，并且我们还使用了MATLAB的Tensor Toolbox工具箱。

对于式多重线性PageRank问题(1.1)中的随机张量$P$ ，我们通过以下几种方式获取。

例1：运用MATLAB中的rand函数，生成若干个3阶$n$ 维随机张量$P$ 。在本例中，我们给出了当$n=200,400$ 两种情况，数值实验结果如下：

小结：从表1及图1可以看出，当维数$n=200$ 或$n=400$ ，$\alpha =0.95$ 时，所用的三种算法能够有效求解重线性PageRank问题。

Table 1. Experimental results of Example 1

表1. 例1实验结果

n	Method	CPU	IT	err
200	NK	12.6939	560	8.82e−11
	NRK	11.2142	500	7.41e−11
	NURK	11.8904	517	7.87e−11
400	NK	179.3317	1030	7.62e−11
	NRK	158.3353	909	4.34e−11
	NURK	143.4701	821	9.95e−11

Figure 1. The relationship between CPU and err when n = 200 (left) and n = 400 (right)

图1. n = 200 (左)及n = 400 (右)时CPU与err的关系

例2：设$t$ 表示张量零元素密度($t=0$ 或$t=1$ 时，$P$ 分别是正张量或零张量)，运用MATLAB中的randsample函数生成具有不同密度的稀疏张量$P$ 。本例中取$n=300$ ，$t=0.3$ 或$t=0.5$ ，实验结果如下：

小结：从表2及图2可以看出，当维数$n=300$ ，$t=0.3$ 或$t=0.5$ ，$\alpha =0.95$ 时，所用的三种算法能够有效求解重线性PageRank问题。

Table 2. Experimental results of Example 2

表2. 例2实验结果

n	t	Method	CPU	IT	err
300	0.3	NK	66.3524	856	9.50e−11
		NRK	60.0733	775	4.99e−11
		NURK	64.1696	829	9.05e−11
	0.5	NK	56.0994	724	5.11e−11
		NRK	55.7386	722	6.82e−11
		NURK	62.3506	805	7.25e−11

Figure 2. The relationship between CPU and err when t = 0.3 (left) and t = 0.5 (right)

图2. t = 0.3 (左)及t = 0.5 (右)时CPU与err的关系

例3：[6]令$\Gamma$ 表示具有节点集$V=\langle n\rangle =D\cup P$ 的有向图，其中$D$ 和$P$ 分别表示悬挂节点和两两连通节点的集合，$n_p$ 表示子集$P$ 中的节点数，即$P=\left\{1,2,\cdots ,n_p\right\}$ ，那么我们可以构造非负张量𝒜：

$a_{i_1{i}_2\cdots i_l}=\{\begin{array}{ll}{a}_{i_1{i}_2\cdots i_l},\hfill & i_k\ne i_{k+1},i_1,i_k,i_l\in P,k=1,\cdots ,l-1\hfill \\ 0,\hfill & i_1\ne i_2\left(i_1\in D\right),i_k\ne i_{k+1},i_k\in P,k=2,\cdots ,l-1\hfill \\ 1/n\hfill & \text{else}\hfill \end{array}$ ,

其中$a_{i_1{i}_2\cdots i_l}$ 从$\left(0,1\right)$ 之间随机选取，规范化$p_{i_1{i}_2\cdots i_l}=\frac{a_{i_1{i}_2\cdots i_l}}{{\displaystyle {\sum }_{i_1=1}^n{a}_{i_1{i}_2\cdots i_l}}}$ 得到张量$P=p_{i_1{i}_2\cdots i_l}$ 。

在本例中，我们给出了当$n=200$ ，$n_p=150$ 以及当$n=400$ ，$n_p=300$ 的情况，数值实验结果如下表。

小结：从表3及图3可以看出，当$n=200$ ，$n_p=150$ 或$n=400$ ，$n_p=300$ ，$\alpha =0.95$ 时，所用的三种算法能够有效求解重线性PageRank问题。

Table 3. Experimental results of Example 3

表3. 例3实验结果

n	$n_p$	Method	CPU	IT	err
200	150	NK	40.4712	1744	9.79e−11
		NRK	40.1985	1750	6.10e−11
		NURK	42.2552	1818	9.35e−11
400	300	NK	565.8186	3253	9.86e−11
		NRK	611.5724	3393	6.44e−11
		NURK	560.7826	3313	9.60e−11

Figure 3. The relationship between CPU and err when n = 200 (left) and n = 400 (right)

图3. n = 200 (左)及n = 400 (右)时CPU与err的关系

例4：[11]选用真实数据集Edinburgh，阶数$m=3$ ，维数$n=1645$ ，该张量中非零元素个数为4292。对于一个矩阵$B\in {ℝ}^{n\times q}$ 以及向量$e_k\in {ℝ}^k$ ，$dangling\left(B\right)$ 定义如下：

$dangling\left(B\right)=e_q^{\text{T}}-e_n^{\text{T}}B$ .

我们通过对真实数据集的整理以获得三阶随机张量$P$ 的模1展开矩阵：

$P_{\left(1\right)}=\omega \left[S+vdangling\left(S\right)\right]+\left(1-\omega \right)\left[M+vdangling\left(M\right)\right]\otimes e_n^{\text{T}}$ .

取$\omega =0.6$ ，通过验证，我们发现对于真实数据集，非线性随机Kaczmarz算法也能有效求解，如图4。因此，无论是对于虚拟数据集还是真实数据集，非线性随机Kaczmarz算法可有效求解重线性PageRank问题。

Figure 4. Edinburgh

图4. Edinburgh

6. 结语

数值实验表明，用非线性Kaczmarz方法、非线性随机Kaczmarz方法以及非线性均匀随机Kaczmarz方法求解重线性PageRank问题，整体上非线性随机Kaczmarz方法的效果要好一些，达到停止准则时所需的时间较少。实验结果证实了利用随机算法求解算多重线性PageRank问题的有效性。