当前, 各种在线社交网络应用的快速发展累积了大量的图数据.图数据由节点和边组成, 且节点之间往往存在复杂的连接关系, 通常缺少显式的全序结构, 使得图排序(graph ranking)成为图数据挖掘、分析的重要手段^[1].

PageRank^[2]是图中节点重要性度量的常用方法, 其基本思想是:节点重要性由其邻接节点重要性决定, 被重要节点连接的节点, 重要性越高.一般来说, PageRank值度量了图中节点的全局重要性或权威度, 但PageRank值却不能很好地度量图上节点间的相似性.为此, 研究者进一步提出了个性化PageRank(personalized PageRank, 简称PPR)^[3].但如文献[4, 5]指出:在使用PPR方法进行相似性查询时, 其返回的top-k结果只考虑查询相关性(relevance)而忽略了多样性(diversity).然而在实际图排序应用环境中, 用户的查询意图很难准确描述, 往往具有不确定性、模糊性以及多义性.因此, PPR方法仍不能很好地满足图排序应用的要求.

当用户真实的查询意图难以准确获取时, 对查询结果进行多样性处理, 是信息检索系统解决此难题的有效方法^[6].为提供高质量的查询结果, 提高用户查询的满意度, 提出能够有效折中相关性和多样性的图排序算法, 是图数据挖掘、分析领域面临的研究挑战.为此, 近年来许多学者提出了一系列的多样性图排序方法^{[4, 5, 7-10]}.

目前, 已有的多样性图排序方法主要分为以下两类.

(1) 基于优化的方法^[7-9].

这一类方法通过建立目标函数来刻画相关性和多样性, 并将问题建模为该目标函数的优化问题, 进而提出相应的优化算法.代表性工作有:Tong等人^[7]提出一个目标函数, 可以在考虑节点中心度和多样性的条件下综合评价集合的质量, 但是该目标函数没有考虑图数据固有的拓扑结构特征, 不能很好地解决多样性图排序的评价问题.Li等人^[8]将多样性图排序建模为一个双目标优化问题, 其中, 用排序结果集的PPR值之和作为相关性度量, 并提出扩展率(expansion ratio)来度量排序结果的多样性.Kucuktunc等人^[9]改进了文献[8]的工作, 将相关性和扩展率进行融合, 进一步提出了扩展相关性(expansion relevance)来度量排序结果的多样性.上述方法多样性度量指标不尽相同, 但最终的目标函数均证明为非负、单调的子模函数(submodular function).因此, 虽然多样性图排序问题是NP-hard的, 但采用贪心算法可在多项式时间近似求解该问题;

(2) 基于随机游动的方法^{[4, 5, 10]}.

随机游动是度量图上节点重要性的有效方法, 然而常规的随机游动方法未考虑节点之间的连接关系, 因此排序结果多样性差.为此, 相关学者提出了改进的随机游动方法来增强排序结果的多样性.代表性的研究工作有DivRank^[4]、GSparse^[5]、GrassHopper^[10].这类方法在随机游动过程中充分考虑了节点间的连接关系, 通过引入节点间的竞争机制, 让彼此相连的节点相互竞争, 实现排序结果的多样性.然而, 这类方法要么计算效率低, 难以适用于大规模网络, 要么缺少明确的优化目标, 不具备可解释性^[1].

综上, 面对大规模图数据的多样性图排序工作, 在优化目标、计算效率方面仍存在研究挑战.具体地:

首先, 多样性度量指标是多样性图排序建模的核心问题.文献[8]提出了扩展率度量多样性, 文献[9]将相关性和多样性进行融合, 进一步提出扩展相关性.实际上, 扩展相关性就是一种以节点PPR值为权重的带权扩展率.采用扩展率或者扩展相关性对多样性进行建模的基本思想是:任意两个节点的共同邻居越少, 两个节点越不相似.节点集中, 节点间不相似程度越高, 则节点集的扩展率或者扩展相似性越大.然而, 扩展率和扩展相关性的定义并非直接基于结点间的不相似性来描述节点集的多样性.换言之, 具有高扩展率或高扩展相关性的节点集, 其内部节点间的不相似性未必高.

下面举例说明此问题.先给出扩展率的形式化描述^[8].令G= < V, E > 是一个图, 其中, V是节点集, E边集.令S⊆V是图上的任意节点集.N(S)是S的扩展集, 即N(S)=S∪{v∈(V-S)|$\exists $u∈S, (u, v)∈E}, 那么S的扩展率定义为er(S)=|N(S)|/|V|.如图 1所示:图 1(a)、图 1(b)子图中, 节点集S={1, 2}的扩展集均为N(S)={1, 2}∪{3, 4, 5, 6}, 由扩展率定义可知, 两个子图中S的扩展率均为er(S)=|N(S)={1, 2, 3, 4, 5, 6}|/|V={1, 2, 3, 4, 5, 6}|=1.然而, 图 1(a)中节点1与节点2具有相同邻居, 节点1和节点2应具有高度相似性.图 1(b)中的节点1与节点2无共同邻居, 应不相似.因此, 扩展率或者扩展相关性无法有效度量图 1所示情形中节点之间的不相似性, 进而无法有效度量结点集的多样性.

其次, 已有的基于优化的方法均将多样性图排序建模为一个基数约束下的非负、单调子模函数最大化问题.该问题是NP-hard的, 可采用贪心算法近似求解^[11].算法从空的解集开始, 每次迭代时, 选取具有最大边际贡献的节点加入到当前解集中.对于含m个节点的查询相关集来说, 为获取top-k排序结果, 需要进行O(mk)次边际贡献评估.当对大规模图数据进行多样性图排序时, 计算代价高, 算法的可扩展性成为很大的挑战.此外, 由于贪心算法的执行过程是一个串行迭代过程, 已有方法很难充分利用诸如Spark GraphX^[12]等图数据计算平台进行高效并行计算.

于是, 对于多样性图排序研究, 本文提出两个问题:能否提出基于节点间不相似性的节点集多样性度量指标?基于此度量指标提出的多样性图排序问题能否得到高效求解?

针对这两个问题, 首先, 提出了一种基于节点邻接信息的节点间不相似性的度量指标, 并证明了该度量是节点间的一种距离度量(distance metric), 即该度量满足非负、对称以及三角不等式等性质.基于该距离度量, 将多样性图排序建模为一种带权完全图上的组合优化问题.具体地, 以PPR查询节点构成节点集, 以节点间的距离度量作为边权重构造带权完全图.求解top-k多样性图排序结果归结为求解该带权完全图的含k个结点的最大权子图.尽管该问题被证明是NP-hard的, 得益于边权重满足距离度量性质, 提出了多项式时间的2-近似算法求解该问题.此外, 由于带权图上不同节点对的距离度量计算是相互独立的, 进而提出了基于GraphX的并行化算法.最后, 在真实图数据集上, 将本文方法与已有方法在算法执行时间、相关性以及多样性上进行了对比测试, 实验结果验证了本文提出方法的有效性.

本文第1节给出节点间不相似性的距离度量定义, 进而给出基于此距离度量定义的多样性图排序问题模型.第2节给出多样性图排序的(并行化)求解算法.第3节给出实验结果.第4节总结全文并展望将来的工作.

1 问题建模

本节中, 先建立节点间不相似性的距离度量.基于此距离度量, 将多样性图排序问题建模为一种带权完全图上的组合优化问题.

1.1 节点间的距离度量

节点间不相似性的度量标准是多样性图排序的基本问题.本文所讨论的多样性图排序问题不涉及图或边的属性信息, 因此, 节点的邻居节点集成为定义节点间不相似性的重要依据.直观地, 两个节点的非共同邻居越多, 则节点间的不相似程度越高.如果考虑到节点的PPR值, 那么节点间非共同邻居的PPR值之和越大, 则节点之间越不相似.基于上述观察, 节点的非共同邻居集可作为节点间不相似性的度量基础.于是, 令f是定义在节点集上的函数, 基于f可建立图G上任意两节点v, u之间的不相似度d_f(v, u).

定义1.  令G= < V, E > 是一个图, N(v)是节点v的邻居集.∀v, u∈V, 基于函数f的不相似度记为d_f(v, u), 并定义:

$ {d_f}\left( {v, u} \right) = f(N\left( v \right) \oplus N\left( u \right)) $

(1)

其中, ⊕是集合间对称差运算, 具体含义为:给定任意2个集合A, B, A⊕B=(A-B)∪(B-A).

在进一步讨论d_f(v, u)前, 先给出v, u之间距离度量的定义.

定义2.  令d_f(v, u)是v, u间的不相似度若d_f(v, u)满足下面3条性质, 则称d_f(v, u)为v, u间的一种距离度量^[13].

(a)    d_f(v, u)满足非负性, 即d_f(v, u)≥0;

(b)    d_f(v, u)满足对称性, 即d_f(v, u)=d_f(u, v);

(c)    d_f(v, u)满足三角不等式, 即∀v, a, u⊆V, d_f(v, u)≤d_f(v, a)+d_f(a, u).

由上述定义可知, d_f(v, u)的含义和性质决定于函数f.下面证明:如果f是节点集上的权重和函数, 则由f决定的d_f(v, u)是v, u间的一种距离度量.

定理1.令A⊆V是任意节点集, w(v)∈$\mathcal{R}$⁺是节点的非负权重.令f是节点权重和函数, 即$f(A)=\sum\limits_{v\in A}{w(v)}$ , 并记$W=\sum\limits_{v\in V}{w(v)}$ .那么由f决定的不相似度是v, u间的一种距离度量.

$ {d_f}(v, u) = f(N(v) \oplus N(u)) = \sum\nolimits_{v \in N(v) \oplus N(u)} {(w(v)/W)} $

(2)

证明:设v, a, u是V集中任意3个节点, 对于任意节点v, 其邻居节点集记为N(v).为简化记号, 设N(v)=X, N(a)=Y以及N(u)=Z.按照定义2, 从以下3个方面分别进行证明.

(a) d_f(v, u)满足非负性, 即d_f(v, u)≥0.由定义1可知, d_f(v, u)=f(X⊕Z).由于f是节点集上的非负权重和函数, 故f(X⊕Z)≥0, 于是d_f(v, u)≥0;

(b) d_f(v, u)满足对称性, 即d_f(v, u)=d_f(u, v).d_f(v, u)=f(X⊕Y), 且d_f(u, v)=f(Y⊕X).⊕满足运算交换性, 因此, f(X⊕Y)= f(Y⊕X).于是, d_f(v, u)=d_f(u, v);

(c) d_f(v, u)满足三角不等式.

要证明d_f(v, u)≤d_f(v, a)+d_f(a, u), 等价于证明f(X⊕Z)≤f(X⊕Y)+f(Y⊕Z).因为X⊕Z⊆(X⊕Y)∪(Y⊕Z), 且f是单调非递减函数, 我们有:

$ f(X \oplus Z) \leqslant f((X \oplus Y) \cup (Y \oplus Z)) $

(3)

又因为f是非负权重和函数, 因此对于任意节点集A, B, C, 均有f(A∪B)≤f(A)+f(B).于是:

$ f((X \oplus Y) \cup (Y \oplus Z)) \leqslant f(X \oplus Y) + f(Y \oplus Z) $

(4)

综合式(3)、式(4)可得:

$ f(X \oplus Z) \leqslant f(X \oplus Y) + f(Y \oplus Z) $

(5)

于是, d_f(v, u)≤d_f(v, a)+d_f(a, u).

综上情形(a)~情形(c), d_f(v, u)是节点间的一种距离度量.

基于定义1、定理1的结论, 定义图上节点之间的距离度量如下.

定义3.  令r是个性化PageRank的排序值向量, r(v)∈$\mathcal{R}$⁺是v的PPR值, $f(A) = \sum\limits_{v \in A} {\boldsymbol{r}(v)} $为节点集A的PPR值之和, 并记R=f(V), 则可定义节点v, u之间的距离度量d_f(v, u)如下:

$ {d_f}(v, u) = f(N(v) \oplus N(u)) = \sum\limits_{v \in N(v) \oplus N(u)} {(\boldsymbol{r}(v)/R)} $

(6)

下面给出d_f(v, u)的示例.图 2给出一个节点带权有向图, 设节点权值为PPR值, 由公式(6)可得:

$ {d_f}(2, 5) = \sum\limits_{v \in N(2) \oplus N(5)} {(\boldsymbol{r}(v)/R)} = \sum\limits_{\{ 2, 4, 5, 6, 7, 10, 11\} } {(\boldsymbol{r}(v)/R)} = 0.574. $

图 2还给出了有向图上距离值最大的前5对节点及其距离值.

1.2 问题模型

多样性图排序问题需要定义相关性、多样性度量.先讨论相关性度量, 然后基于第1.1节间节点的距离度量定义多样性度量, 最后将多样性图排序建模为带权完全图上的优化问题.

首先讨论相关性度量.个性化PageRank是图数据上实现相关性查询的有效方法^[3].具体地, 令G是一个包含n个节点的图.节点的个性化PageRank排序向量可由如下迭代公式计算:

$ \mathit{\boldsymbol{r}} = \alpha \mathit{\boldsymbol{A'r}} + (1 - \alpha )\mathit{\boldsymbol{q}} $

(7)

其中, α(0 < α < 1)为阻尼因子; A是一个行规范化的图邻接矩阵, 即$\sum\nolimits_{j = 1}^n {\boldsymbol{A}(i, j)} = 1, i = 1, 2, ..., n$.给定查询向量q(n×1的列向量$\boldsymbol{q}(i) \geqslant 0, \sum\nolimits_{i = 1}^n {\boldsymbol{q}(i)} = 1$), 公式(7)会收敛到节点集V上的一个平稳分布, 此分布即为排序值向量r.对于任意结点v∈V, r(v)度量了v与q的相似性.于是, 给定一个排序结果S, 可用S的排序值之和, 即$rel(S)=\sum\nolimits_{v\in S}{\boldsymbol{r}(v)}$度量相关性.

其次, 如第1.1节讨论, d_f(v, u)给出了节点v, u间的一种距离度量.

于是, 可用S中节点间的距离度量和$div(S)=\sum\nolimits_{v, u\in S}{{{d}_{f}}(v, u)}$度量其多样性.

给定查询向量q, 令Q⊆ V是查询相关节点集, 即∀v∈Q, 有r(v) > 0.定义优化目标函数F(S)如下:

$ F(S)=rel(S)+\lambda div(S)=\sum\limits_{v\in S}{\boldsymbol{r}(v)}+\lambda \sum\limits_{v, u\in S}{{{d}_{f}}(v, u)} $

(8)

其中, λ(0 < λ < 1)是折中因子, 用来折中相关性和多样性.如果|S|=k, 注意到:公式(8)中, rel(S)为k项r(v)之和.同时, div(S)为k(k-1)/2之和.为平衡rel(S)与div(S), 分别与不同的因子相乘, 于是改写F(S)为下面的公式(9):

$ F(S) = (k - 1)\sum\limits_{v \in S} {\boldsymbol{r}(v)} + 2\lambda \sum\limits_{v, u \in S} {{d_f}(v, u)} $

(9)

于是, Topk多样性图排序问题(TopkDRG)可定义为

$ {S^*} \leftarrow \arg {\max _{S \subseteq Q \subseteq V, |S| = k}}F(S) $

(10)

下面证明由公式(10)定义的TopkDRG是NP-hard的.

定理2.  令G= < V, E > 是一个图, 则图G上的TopkDRG问题是NP-hard的.

证明:在图G上给定查询向量q, Q是q的查询相关节点集.引入如下融合节点相关性和不相似性的距离度量, 记为${d'_f}(v, u).$

$ {d'_f}(v, u) = \boldsymbol{r}(v) + \boldsymbol{r}(u) + 2\lambda {d_f}(v, u) $

(11)

不难验证, ${d'_f}(v, u)$仍然满足定义2中所述距离度量的非负、对称、三角不等式3条性质.

令${D'_f}(S) = \sum\nolimits_{v, u \in S} {{{d'}_f}(v, u)} $为节点集S中所有节点对的度量距离和, 由公式(11)可知:

$ {D'_f}(S) = \sum\limits_{v, u \in S} {{{d'}_f}(v, u)} = (k - 1)\sum\limits_{v \in S} {\mathit{\boldsymbol{r}}(v)} + 2\lambda \sum\limits_{v, u \in S} {{d_f}(v, u)} = F(S). $

也就是说, TopkDRG的目标函数F(S)等于节点集S中节点对的${d'_f}(v, u)$度量距离之和, 即TopkDRG可描述为

$ {S^*} \leftarrow \arg {\max _{S \subseteq Q \subseteq V, |S| = k}}F(S) = \arg {\max _{S \subseteq Q \subseteq V, |S| = k}}{D'_f}(S) $

(12)

至此, 以Q集为节点集、以${d'_f}(v, u)$为Q中节点v, u之间的边权重构造了带权完全图C(Q).由公式(12)可知, TopkDRG等价于在带权完全图C(Q)上求解包含k个节点的最大边权和子图问题.该问题就是组合优化中的max-sum k-dispersion问题(简写为MSkD)^[13].MSkD被证明是NP-hard的^[14].因此, TopkDRG是NP-hard的.

由定理2结论可知, TopkDRG是NP-hard的.因此, 设计多项式时间近似算法成为本文后续要讨论的内容.

2 多样性图排序算法

首先给出TopkDRG的多项式时间求解算法, 并分析该算法的近似性能.鉴于不同节点对的度量距离计算是相互独立的, 进一步提出并行化的多样性图排序算法, 并介绍算法在Apache Spark的并行图计算平台GraphX上的实现技术.

2.1 基于匹配的多样性图排序算法

由第1.2节可知, TopkDRG归结为求解带权完全图C(Q)上包含k个节点的最大权完全子图问题.虽然TopkDRG是NP-hard的, 得益于C(Q)中边权重满足距离度量性质, 本节基于求解C(Q)上最大权k/2-匹配, 提出一种TopkDRG的多项式时间近似算法.

算法的基本思想是:给定查询向量q, 在图G上执行个性化PageRank获得查询相关节点集Q.以Q为节点集, 以${d'_f}(v, u)$为边e(v, u)的边权重构造带权完全图C(Q).调用函数MWM求解C(Q)的最大权k/2-匹配, 记为M^* (M^*=k/2), M^*中所有边连接的k个节点即为多样性图排序的top-k排序结果.其中, 函数MWM执行$\left\lfloor k/2 \right\rfloor$次迭代, 每次迭代时, 选择C(Q)中当前最大权重边加入到解集中, 并删除该边的端点以及这些端点关联的边.下面, 算法1以及函数MWM给出了上述过程的完整描述.

算法1.   MA(基于匹配的多样性图排序算法).

输入:图G= < V, E > , k, 查询向量q, 阻尼因子α, PPR精度ε, 折中因子λ, 抽样概率p;

输出:排序结果集S.

(1) 给定查询向量q, 执行个性化PageRank算法, 获得查询相关节点集Q:

$ Q \leftarrow personalizedPageRank(G, \mathit{\boldsymbol{q}}, \alpha, e); $

(2) 以节点PPR值为权重, 以p(0 < p≤1)作为抽样率, 对Q进行随机抽样, 得到随机子集:

$ {Q_p} \leftarrow ppr\_biased\_sampling\left( {Q, p} \right); $

(3) 以Q_p为节点集, 构造带权完全图k/2, 其中, 任意边e(v, u)的权重置为${d'_f}(v, u)$;

(4) S←Ø;

(5) 调用MWM函数求解C(Q_p)的最大权k/2-匹配, 即:M^*←MWM(C(Q_p), k);

(6) S←包含在M^*中所有边的端点;

(7) RETURN S

先分析算法1的时间复杂度.具体地, 设G= < V, E > .算法1中第(1)行执行个性化PageRank, 其复杂度为O(|E|)^[8].第(3)行是算法1中计算代价最高的部分, 代价主要由两部分构成:首先, 收集节点的邻居节点信息, 最坏情况下需要访问G中所有节点, 代价为2|E|; 其次, 构造C(Q_p), 最坏情况下的时间复杂度为O(|V|²).MWM函数需要对所有节点对按距离度量值进行1次排序, 其最坏情况下的复杂度为O(|V|²log(|V|²)).于是, 算法1的时间复杂度为O(|E|+|V|²log(|V|²)).

需要说明的是:算法1中的第2行, 得到查询相关节点集Q后, 以Q中节点PPR值为权重, p(0 < p≤1)作为抽样率, 对Q进行随机抽样得到随机子集Q_p, 进而构造C(Q_p), 并在其上进行求解.如果p=1.0, 即Q_p=Q, 如果p < 1, 则在Q的一个随机子团(randomsub-clique)上进行求解.下面先分析p=1.0的情况下, 算法1求解TopkDRG的理论近似性能.对于p < 1的情况, 本文第3节将通过实验验证在稍微降低求解质量的情况下, 算法的效率将得到很大提高.

函数1. MWM(求解C(Q_p)的最大权k/2-匹配).

Input:C(Q_p), k;

Output:最大权k/2-匹配M^*(|M^*|=k/2).

(1) M←Ø;

(2) FOR i←1 to $\left\lfloor k/2 \right\rfloor$ DO

(3)  $(v, u) \leftarrow \arg {\max _{x, y \in {Q_p}}}{d'_f}(x, y)$;

(4)  M←M∪e(v, u);

(5)  删除C(Q_p)中与v, u节点关联的边, 删除v, u;

(6) END FOR

(7) RETURN M

为分析算法1的近似性能, 先证明一个基于匹配方法求解带权图的最大权重和k子图的一般性结论, 即定理3.首先引入相关数学记号, 令Q是任意节点集, C(Q)= < Q, E_Q>是Q上任意边权重满足距离度量性质的带权完全图, 其任意一条边e(v, u)∈E_Q的权重为某一距离度量dis(v, u).给定任意节点集A⊆Q, $D(A) = \sum\nolimits_{v, u \in A \subseteq Q} {dis(v, u)} $为A集中节点对的边权重和.类似地, $D(E) = \sum\nolimits_{e(v, u) \in E \subseteq {E_Q}} {dis(v, u)} $为边集E中所有边的权重和.令A^*(|A^*|=k)是C(Q)的含k个节点的最大权重和子图的节点集.M^*是A^*决定的子图的最大权和k/2匹配边集.M^OPT是C(Q)的最大权重和k/2匹配边集.M^OPT是M^OPT中的边决定的节点集.记$\tilde M$是M^OPT的α-近似解.$\tilde A$是$\tilde M$决定的节点集.

定理3描述了这样一个事实:通过求解C(Q)的最大权重和k/2匹配的α-近似解$\tilde M$, $\tilde A$是$\tilde M$决定的含k个节点的节点集, 那么对于边权重和这一度量标准而言, $\tilde A$是A^*的2α-近似解.换句话说, 定理3给出了基于匹配方法求解带权图上含k个节点的最大权重和子图的一般性近似结论.

定理3.  对于任意一个边权重满足距离度量性质的带权完全图C(Q), 总有$D({A^*}) \leqslant 2\alpha D(\tilde A).$

证明:

首先, 令A(|A|=k > 2)是任意节点集, M表示A决定的带权完全子图C(A)上的最大权和k/2匹配边集, D(A)表示C(A)中边的平均权重值, D(M)表示匹配边集M的平均权重值.根据文献[13]可知:

$ \bar D(A) \leqslant \bar D(M) \Leftrightarrow D(A) \leqslant (k - 1)D(M) $

(13)

其次, 由于$\bar D({A^*}) \leqslant \bar D({M^*})$, 进而有:

$ \frac{{D({A^*})}}{{k(k - 1)/2}} \leqslant \frac{{D({M^*})}}{{k/2}} \Leftrightarrow D({A^*}) \leqslant (k - 1)D({M^*}) $

(14)

此外, 由于M^OPT是C(Q)上的最大权重和k/2匹配边集, 因此D(M^*)≤D(M^OPT), 进而基于公式(14)的结论, 有:

$ D({A^*}) \leqslant (k - 1)D({M^*}) \leqslant (k - 1)D({M^{OPT}}) $

(15)

于是, 根据文献[13]可知:

$ \frac{{\bar D(M)}}{2} < \bar D(A) \Leftrightarrow \frac{{D(M)}}{{k/2}} < \frac{{D(A)}}{{k(k - 1)/2}} \Leftrightarrow D(M) < (2/k - 1)D(A) $

(16)

因为$D(\tilde M) < (2/k - 1)D(\tilde A)$, 同时, $\tilde M$是M^OPT的α-近似解, 即$D({M^{OPT}}) \leqslant \alpha D(\tilde M)$, 综合公式(13)~公式(16)的结果可知:

$ D({A^*}) \leqslant (k - 1)D({M^*}) \leqslant (k - 1)D({M^{OPT}}) \leqslant (k - 1)\alpha D(\tilde M) \leqslant 2\alpha D(\tilde A) $

(17)

证毕.

基于定理3给出的结论, 可分析算法1求解TopkDRG问题的近似性能.在算法1中, 对于p=1.0的情况, 我们采用函数MWM求解C(Q)的最大权k/2匹配边集.由文献[15]的结论可知, 基于MWM可得到α=1-近似的C(Q)的最大权k/2匹配边集.于是, 作为定理3结论的一个推论, 推论1给出了算法1求解TopkDRG问题的近似性能:

推论1.  当p=1.0时, 如果算法1采用MWM求解C(Q)的最大权k/2匹配边集, 那么基于定理3的结论, 算法1可得到TopkDRG问题的2α(α=1)-近似解.

2.2 并行化的多样性图排序算法

构造C(Q)是算法1计算代价最高的部分, 其关键在于计算Q中节点对的度量距离值.幸运的是, 不同节点对的距离计算是相互独立的.基于此, 提出并行化的多样性图排序算法PMA.PMA与MA最大的不同在于:PMA采用MapReduce编程模型完成C(Q)上O(|Q|²)的节点对度量距离计算, 从而提高了多样性图排序算法的效率.由于PMA与MA其余部分相同, 不再给出PMA的算法描述.

从以下3个方面介绍基于MapReduce编程模型^[16]构造C(Q)具体方法.

(1) 键值对(key-value pairs)生成

设由个性化PageRank获得查询相关节点集Q, 其中, v∈Q, v.ppr > 0为节点v的PPR值.基于Spark GraphX中的aggregateMessages函数, 并行化地收集Q所有节点的邻居信息.对任意节点v, 其邻居集信息为v.Nbrs.由此生成节点RDD, 内容格式:(v, v.ppr, v.Nbrs).对此, RDD做cartesian运算(笛卡尔积), 生成键值对集, 其中, 任意键值对为

$ \mathit{\boldsymbol{key}}:(v, u), \mathit{\boldsymbol{value}}:(v.ppr, u.ppr, v.Nbrs, u.Nbrs) $

(18)

(2) Map函数

实现v, u节点邻居集的对称差运算, 即, 将公式(18)所示键值对映射为如下键值对:

$ \mathit{\boldsymbol{key}}:(v, u), \mathit{\boldsymbol{value}}:(v.ppr, u.ppr, v.Nbrs \oplus u.Nbrs) $

(19)

(3) Reduce函数

对每个键值对, 根据公式(6)完成v, u之间的距离计算.

基于上述MapReduce编程模型, 可并行计算Q上节点对的距离度量计算, 从而C(Q)构造.然后, 调用MWM函数即可输出top-k排序结果.

本文基于Apache Spark^[12]的并行化图数据计算组件GraphX实现了PMA算法.弹性分布式数据集(resilient distributed dataset, 简称RDD)是Spark上分布式数据的基本抽象.在Spark平台上, 图数据也以RDD的方式进行存储.基于GraphX的PMA算法也是通过对图RDD数据的一系列变换(transformation)以及行动(action)而得以实现的.

图 4给出了图 3所示基于GraphX的PMA算法实现所涉及到的RDD以及施加在这些RDD上的一系列的变换和行动, 其中, PPR查询的输入节点为节点1.从步骤1~步骤5完成节点对的度量距离计算.步骤6的循环过程求解Topk多样性排序节点集.

3 实验 3.1 实验环境设置

(1) 实验图数据集

在表 1所示4个真实的、不同类型的图数据集(均下载自 http://snap.stanford.edu/ )上测试了本文算法.其中, ca-AstroPh是论文作者合作关系网络, soc-Epinions1是社交网站Epinions.com内用户之间的信任关系网络, amazon0601是Amazon商品共购关系网, Web-Google是来自Google的Web页面关系网.

(2) 度量标准

采用文献[8]定义的查询相关性(relevance)作为查询相关性度量标准, 记为rel并定义如下:

$ rel(S) = \frac{{\sum\nolimits_{v \in S} {\mathit{\boldsymbol{r}}(v)} }}{{\sum\nolimits_{v \in A} {\mathit{\boldsymbol{r}}(v)} }} $

(20)

其中, r(v)是节点v的PPR值, S是PMA算法返回的top-k排序结果, A是个性化PageRank算法返回的top-k排序结果.可见, rel(S)值越大, S的查询相关性越高.

至今, 排序结果多样性没有统一度量标准.为便于对比, 本文采用文献[9]提出的扩展相关性(expansion relevance)作为多样性度量标准, 记为epRel并定义如下.

定义4^[9].  令S是任意节点集, N_l(S)是S的l-步邻居节点集, 即:

$ {N_l}(S) = S \cup \{ v \in (V - S)|\exists u \in S, d(u, v) \leqslant l\} . $

则S的l-扩展相关性定义为

$ epRe{l_l}(S) = \sum\nolimits_{v \in {N_l}(S)} {\mathit{\boldsymbol{r}}(v)} $

(21)

epRel融合了S的查询相关性和扩展率, epRel越大, 则在此度量标准下的排序结果多样性程度越高.

此外, 本文通过定义节点间距离来度量节点间的不相似性, 因此引入了2种新的多样性度量标准, 定义如下.

定义5.  令S是包含k个节点的节点集, d_f(v, u)是本文定义的节点v, u之间的距离度量, 那么, S的平均距离度量定义为

$ aveDis(S)=\sum\limits_{v,u\in S}{{{d}_{f}}(v,u)}\text{ /}(k(k-1)/2) $

(22)

不难看出:aveDis越大, S内部节点之间的差异度越大, S多样性程度越高.

定义6.  令S是包含k个节点的节点集, d_f(v, u)是本文定义的节点v, u之间的距离度量, 那么, S中节点间的最小距离度量记为

$ \min Dis(S) = {\min _{v, u \in S}}{d_f}(v, u) $

(23)

易知:minDis(S)越大, S内部节点之间的差异度越大, S多样性程度越高.

(3) 参与对比的其他图排序算法

第1种算法是PPR, 即个性化PageRank算法.本文个性化PageRank采用Apache GraphX提供的API实现.

第2种是文献[9]提出的基于子模函数优化epRel的算法, 记为SM.根据文献[9]的结论, epRel是以节点PPR值为权重的带权扩展率, 由于epRel融合了查询相关性和扩展率, 对于排序结果的多样性度量更具优越性^[9].因此, 本文与文献[9]提出的算法进行实验对比.SM是一种子模目标函数的贪心算法, 我们采用文献[17]提出的CELF方法对贪心过程进行加速以提高算法执行效率.

(4) 实验环境

PMA, SM算法均采用scala语言实现.所有实验在一台32G内存, 2×12核(2个Intel Xeon 2.66 GHz CPU)的Linux 14.4服务器上完成.Apache Spark采用2.0版本.

3.2 参数对算法性能的影响

通过实验验证算法1中的参数对PMA算法性能的影响.具体包括以下方面.

(1) λ因子对PMA算法的影响

由公式(8), λ用来折中优化目标中相关性和多样性.实验验证不同的l对于PMA算法性能的影响.通过调整个性化PageRank中的ε参数, 使得|Q|制在2000~3000之间.每次实验时, 随机给定查对询节点, 分别针对λ=0.1, 0.3, 0.5, 0.7, 1.0这5种情况查询top-k=30排序结果.最终结果是50次实验的平均值.

图 5给出了在4个测试数据集上, PMA算法的rel, epRel, aveDis, minDis这4个度量标准与λ参数的关系图.如图 5(a)所示:随着λ值的增大, 进行距离计算时, 多样性部分的权重增大, 而相关性权重降低, 因此, rel逐渐降低, 而其他多样性指标得到增强.图 5(b)~图 5(d)给出的实验结果验证了这一事实, epRel, aveDis, minDis这3个多样性指标随λ提高而增大.由于λ大于0.5后rel显著降低, 因此在后续的算法对比实验中, PMA算法的λ均设为0.5.

(2) 抽样率p对PMA算法的影响

如第2.1节所述, PMA算法可以对查询相关节点集Q以PPR值为权重进行随机抽样得到随机节点子集Q_p, 进而在Q_p形成的子团上执行PMA算法求解.实验验证不同的p对于PMA算法性能的影响.为有效检验参数p的影响, 进一步降低了个性化PageRank算法中的ε参数, 提高了查询相关集的节点数, 使得|Q|在4000~ 5000之间.每次实验时, 随机给定查询节点, 分别对p=0.1, 0.3, 0.5, 0.7, 1.0这5种情况查询多样性图排序top-k=30排序结果.最终结果是50次实验的平均值.

图 6给出了抽样率p对PMA算法影响的实验结果.

如图 6(a)所示:随着p的增加, Q_p节点数也随之增加, 构造C(Q_p)子团所需的计算距离对数目大幅增加(需O(|Q_p|²)距离计算), PMA算法时间也随之上升.从图 6(b)可见:当p < 0.5时, 由于按节点的PPR值为权重进行抽样, 高相关性节点得以高概率选中进入Q_p集, 最终排序结果具有高相关性.随着p的增加, 可在更大范围内选择节点, 因此rel降低.但与此同时, 距离度量值更大的节点对会进入最终的排序结果, 因此如图 6(c)、图 6(d)所示, epRel和aveDis这两个多样性指标也随p的增大而增加.同时注意到:当p > 0.5后, 除web-Google外, 在其余几个数据集上, epRel, aveDis指标增长趋势减缓.这意味着增加Q的节点数并不能显著提升多样性指标.

从实验结果可知:采取对查询相关节点集进行随机抽样时, 在保证排序结果的查询相关性和多样性的前提下, 可大幅降低算法的执行时间.这一特性使得PMA算法能够高效完成大规模图数据的多样性图排序任务.

(3) CPU核数对PMA执行之间的影响

PMA算法基于ApacheSpark的并行图计算平台GraphX实现, 可通过设置Spark的并行核数来调整PMA算法的效率.Q_p中节点对的距离计算是PMA算法中计算密集部分, 恰好也是适于并行计算的部分.实验验证了核数分别在4, 8, 12, 16, 20, 24的情况下, PMA算法查询top-k=30的执行时间.实验结果如图 7所示.

由实验结果可知:随着核数的增加, PMA算法的执行时间减少.这一结果也验证了距离计算的可并行性.后续的算法对比实验中, PMA的CPU核数均设为24.

3.3 算法对比实验结果

我们比较了PPR, SM, PMA, rPMA(以PPR权重进行节点随机抽样的PMA算法)这4种算法的执行时间、相关性以及多样性指标.实验参数设置为:|Q|=2000~3000, λ=0.5, p=0.5.每次实验随机给定查询节点, 分别得到k=10, 20, 30, 50, 100的top-k排序结果.最终结果是50次重复实验的平均值.

表 2给出了SM, PMA, rPMA这3种算法的执行时间比较结果.

●首先, PMA和rPMA执行时间明显优于SM.特别地, 在完成同样的top-k排序时, rPMA比SM快5倍~10倍, 且数据集越大, 速度优势越明显;

●其次, 由于SM算法是迭代过程, 随着k值增加, 其执行时间也显著增加.PMA与rPMA中无计算密集的迭代过程, 其执行时间随k值增加趋势平缓.

表 3是SM、PMA以及rPMA在rel指标上的比较结果.

由于rPMA以PPR权重进行节点随机抽样构造子团, 高PPR值的节点被高概率选入Q_p集, 其rel指标优于SM, PMA.在所有测试数据集上, PMA的rel指标稍优于SM.

表 4是epRel指标的比较结果.

SM, PMA以及rPMA增强了排序结果的多样性, 这3种算法的epRel指标明显优于PPR.值得注意的是:虽然PMA算法并非直接优化epRel, 但在参与测试的ca-AstroPh, socEp以及web-Google这3个图数据上, 其epRel指标仍优于以epRel为优化目标的SM.此外, 由于PMA和rPMA直接优化aveDis, 由表 5、表 6的实验结果可见, PMA和rPMA算法在aveDis、minDis指标下明显优于PPR和SM.

综上, 在进行多样性图排序时, PMA和rPMA在保证查询结果的相关性和多样性的前提下, 通过并行计算和随机抽样, 大幅提高了算法的执行效率.相较于SM, 在查询质量和查询效率上均有优势.

4 总结

在用户真实的查询意图难以准确获取的情况下, 为提供高质量的图排序结果并提高用户查询的满意度, 能够有效折中相关性和多样性的图排序算法是图数据检索面临的研究挑战.

针对已有的研究工作在排序结果多样性建模和算法效率这两方面存在的不足之处, 本文提出了一种描述节点间不相似度的的距离度量, 以此为基础, 建立了新的多样性度量标准, 并将多样性图排序建模为一种带权完全图上的组合优化问题.给出了求解此问题的2-近似算法以及该算法在MapReduce编程模型上的并行化实现方法.在真实的图数据上测试了本文方法, 实验结果表明, 本文方法在算法执行时间、查询相关性和多样性指标上均优于已有方法.

本文方法并未涉及节点或边的信息, 在很多实际的图数据检索应用中, 节点和边往往带有丰富的属性信息^[18], 如何将本文方法拓展到面向属性图(attributed graph)的多样性图排序中, 这是我们下一步可研究的工作.