基于Anderson加速分裂迭代算法求解多重线性PageRank问题

Solving Multilinear PageRank Problem Based on Anderson Accelerated Splitting Iteration Algorithm

摘要: 本文针对多重线性PageRank问题，结合松弛技术，提出了一般形式的张量分裂迭代算法，并给出了相应的收敛性分析。进一步，结合Anderson加速技术，提出了新的张量分裂算法。

Abstract: In this paper, combining relaxation techniques, a general form of tensor splitting iterative algorithm is proposed for the multilinear PageRank problem, and the corresponding convergence analysis is given. Furthermore, a new tensor splitting algorithm is proposed by incorporating Anderson acceleration techniques.

1. 引言

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

令$ℝ$ 为实数域，${ℝ}^n$ 、${ℝ}^{k\times n}$ 、${ℝ}^{\left[m,n\right]}$ 分别为$n$ 维向量、$k\times n$ 维矩阵、$m$ 阶$n$ 维张量。称向量$s=\left(s_i\right)\in {ℝ}^n$ 为随机向量，即对于所有$i\in n$ ，有$s_i\ge 0$ 并且${\displaystyle {\sum }_{i=1}^n{s}_i}=1$ ，其中$n=\left\{1,\cdots ,n\right\}$ 。是一个$m$ 阶$n$ 维张量，具体为：

$p_{i_1{i}_2\cdots i_m}\ge 0,{\displaystyle \sum }_{i_1=1}^n{p}_{i_1{i}_2\cdots i_m}=1,\forall i_2\cdots i_m\in n.$

Gleich等[6]基于秩-1近似估计技术[7]提出多重线性PageRank问题：

, (1.1)

并且

,

其中，$\alpha \in \left(0,1\right)$ 、$v\in {ℝ}^n$ 是随机向量，$x\in {ℝ}^n$ 为特求的PageRank向量。

近年来，多重线性PageRank问题引起了研究人员的极大关注。许多用于求解方程(1.1)的理论分析[8]-[11]和相关算法[12]-[17]。在现有的研究中，多重线性PageRank问题的算法大致为基于梯度的相关算法和不涉及梯度计算的算法。对于基于梯度的相关算法，在[6]中开发了一种Newton方法。Meini等[12]和Guo等[13]分别研究了Perron-Newton法和多步牛顿法。对于非梯度法，在[6]中给出定点法、移位定点法、内–外方法和反幂方法。众所周知，梯度计算的难度可能导致高计算成本，而非梯度算法在处理非对称张量模型时，在计算效率方面具有天然的优势。分裂算法是张量计算中的一种经典非梯度算法。Li等[14]和Liu等[18]研究了用于求解张量方程的张量分裂算法。

分裂算法在张量计算中有着重要应用，并且分裂算法属于非梯度算法，Anderson加速技术[17]也是一种通用且有用的技术，用于加速矩阵情况下不动点问题的迭代非常成功，本文将探索分裂迭代的Anderson加速，用于求解基于(1.1)的多重线性PageRank问题。

本文的主要贡献如下：1) 我们提出求解多重线性PageRank问题的分裂方法的一般形式，并对所提出的方法进行了收敛分析；2) 我们提出了Anderson加速张量分裂迭代方法来解决多重线性PageRank问题。

2. 预备知识

首先介绍我们文中用到的符号和基本知识。令${\mathbb{S}}_1=\left\{x\in {ℝ}^n:x\ge 0,{\Vert x\Vert }_1=1\right\}$ 。$\mathcal{A}$ 是一个$m$ 阶$n$ 维张量，$\mathcal{A}=\left(a_{i_1{i}_2\cdots i_m}\right),a_{i_1{i}_2\cdots i_m}\in ℝ,i_1,i_2,\cdots ,i_m\in n$ 。

一个$n$ 维张量$\mathcal{A}=\left(a_{ijk}\right)\in {ℝ}^{\left[3,n\right]}$ 的模-1展开如下：

${\mathcal{A}}_{(1)}=\left[\begin{array}{cccccccccc}{a}_{111}& \dots & a_{1n1}& a_{112}& \dots & a_{1n2}& \dots & a_{11n}& \dots & a_{1nn}\\ a_{211}& \dots & a_{2n1}& a_{212}& \dots & a_{2n2}& \dots & a_{21n}& \dots & a_{2nn}\\ ⋮& \ddots & ⋮& ⋮& \ddots & ⋮& \dots & ⋮& \ddots & ⋮\\ a_{n11}& \dots & a_{nn1}& a_{n12}& \dots & a_{nn2}& \dots & a_{n1n}& \dots & a_{nnn}\end{array}\right].$

在本文中，我们对张量切片作为分裂对象，对每片切片采用同一种分裂方式。接下来，我们分别介绍对角面张量、下三角张量、严格下三角张量、上三角张量和严格上三角张量的定义，这将在下文中使用。

定义1：[14]令张量$\mathcal{D}\in {ℝ}^{\left[m,n\right]}$ ，$m\ge 3$ 为一个对角面张量，其中

$a_{ij{i}_3{i}_4\cdots i_m}=0,i\ne j$ .

张量$L\left(L^{\prime }\right)\in {ℝ}^{\left[m,n\right]}$ 为(严格)下三角张量，其中

$a_{i_1{i}_2\cdots i_m}=0,i_1\le i_2\left(i_1<i_2\right).$

张量$\mathcal{U}\left({\mathcal{U}}^{\prime }\right)\in {ℝ}^{\left[m,n\right]}$ 为(严格)上三角张量，其中

$a_{i_1{i}_2\cdots i_m}=0,i_1\ge i_2\left(i_1>i_2\right).$

注1：令$\mathcal{D}$ 、$ℒ$ 、${ℒ}^{\prime }$ 、$\mathcal{U}$ 和${\mathcal{U}}^{\prime }$ 为张量$\mathcal{A}$ 的对角面部分、下三角部分、严格下三角部分、上三角部分、严格上三角部分。对任意$x\in {ℝ}^n$ ，不难检验得出$\mathcal{D}{x}^{m-2}$ 、$ℒx^{m-2}$ 、${ℒ}^{\prime }{x}^{m-2}$ 、$\mathcal{U}{x}^{m-2}$ 和${\mathcal{U}}^{\prime }{x}^{m-2}$ 为$\mathcal{A}{x}^{m-2}$ 的对角部分、下三角部分、严格下三角部分、上三角部分、严格上三角部分。

多重线性PageRank问题解的唯一性一直是许多学者关注的问题[6] [8]-[11]。本文将基于[11]中的唯一性条件给出收敛性分析。现引入高阶遍历性系数定义。

定义2：令高阶遍历系数的定义如下：

具体的计算公式为：

.

进一步，若为随机张量，容易得出，

对于随机张量，有，，和。

定义3：令，若是非奇异矩阵，我们称为矩阵的分裂，分裂形式具体为：1) 正则分裂，若；2) 弱正则分裂，若。

3. 提出的算法及收敛性分析

令含有正元素的向量。我们定义投影算子。结合松弛技术[15]，我们设计出张量分裂迭代算法如下：

算法1 张量分裂迭代

输入：给定随机向量，，最大迭代步数，停机误差，松弛因子，初始向量。令 输出： 1：当 2：， ， 3：若$\Vert x_k-x_{k-1}\Vert <\varsigma$ 则终止并且输出$x_k$ 4：$k\leftarrow k+1$ ，返回步骤1

注2：若$x_k\in {\mathbb{S}}_1$ ，则是列随机矩阵，且$0<\alpha <1$ 时，是非奇异的M-矩阵。

我们对提出的算法1进行收敛性分析，本文基于Fasino等[11]给出的3阶多重线性PageRank问题解的唯一性条件。首先给出以下引理。

引理1：若，则多重线性PageRank问题(1.1)有唯一解。

引理2：令为随机张量。对于任意的$x,y,z\in {\mathbb{S}}_1$ ，以下不等式成立：

其中，。

引理3：令是(弱)正则分裂，则${\Vert M_x^{-1}\Vert }_1\le \frac{1}{1-\alpha }$ 。

证明：由，得，结合$M_x{}^{-1}\ge 0,M_x{}^{-1}{N}_x\ge 0$ ，我们得

到，因此${\Vert M_x^{-1}\Vert }_1\le \frac{1}{1-\alpha }$ ，证毕。

定理1：令$\widetilde{ℳ}$ ，是随机张量，，且，$x$ 为(1.1)的解，则对于任意初始随机向量$x_1$ ，由算法1生成的向量序列$\left\{x_k\right\}$ 收敛，并且

${\Vert x_{k+1}-x\Vert }_1\le {\theta }^k{\Vert x_0-x\Vert }_1.$

其中，$\theta =\left(1+\alpha \right)\varsigma ,$ 并且。

证明：由算法1的迭代格式可知

得出

由，结合引理1我们得到

，故$x$ 是式子的唯一解，得到

令${\widehat{e}}_{k+1}={\widehat{x}}_{k+1}-x,e_{k+1}=x_{k+1}-x$ ，得

对$ℳ$ 进行单位随机化，我们定义${\widetilde{ℳ}}^{+}=full\left(ℳ\right)$ ，函数$full()$ 的功能为对自变量矩阵(张量)中为0的

元素进行随机赋值，赋值范围为$\left(0,1\right)$ 。令${\widetilde{ℳ}}_{ijk}=\frac{{\widetilde{ℳ}}_{ijk}^{+}}{{{\displaystyle \sum }}_{i=1}^n{\widetilde{ℳ}}_{ijk}^{+}}$ ，从而得到随机张量$\widetilde{ℳ}$ ，并且有$ℳ\le \widetilde{ℳ}$ 。

从而得到

结合引理2，得

记。

即

因为为随机向量，结合得到

假设，当迭代次数达到时，有

由已知条件易证，故收敛与，证毕。

接下来，我们将使用Anderson加速技术来提高算法1的收敛性能。Anderson加速(AA) [19]最初由Anderson在1965年提出，AA是一种序列方法已被广泛用于提高固定点迭代的收敛速度。定义残差为，则求解不动点问题等价求解残差方程。AA方法的主要思想是通过前步迭代计算结果来表示最新的迭代结果，即这个组合向量系数通过极小化每一步相应的残差的组合得到。Anderson加速方法是针对不动点迭代进行加速的一类算法，我们考虑以下一般定点问题

并且，其中且。

根据参考文献[20]中的假设2.1，当满足

或，

其中，是的一个控制参数时，我们不必执行Anderson加速步骤。

我们新提出的张量分裂迭代算法的安德森加速度如下所示：

算法2 Anderson加速张量分裂迭代

输入：给定随机向量，，，常数，最大迭代步数，停机误差，松弛因子，初始向量。令 输出： 1：while do 2： 3： 4： 5：令，其中 6：计算，得 7：if or ，then 8： 9：else 10： 11：end if 12： 13：if then 14：则终止并且输出 15：end if

16： 17：end while

注3：如参考文献[20]所述，在实现Anderson加速时，算法参数的适当选择很重要。如果太小，则利用迭代步骤中的信息可能太有限，无法实现快速收敛。如果很大，则最小二乘问题可能是病态的。在大多数应用中，或是可行且有效的选择。同时，作为的控制参数，太小的很容易导致跳过Anderson加速步骤。因此，设置较大的是合适的。在数值测试中，我们取较为合适。

4. 结语

本文基于[15]提出的求解高阶马尔科夫链和多重线性PageRank问题的松弛算法基础上，结合张量分裂方法，提出求解多重线性PageRank的分裂算法，并进行相应的收敛性分析，进一步引入Anderson加速技术[17]，给出Anderson加速张量分裂迭代的算法流程并对使用的参数进行了一定的说明。