PANE：可扩展且有效的属性网络嵌入阅读重点：PANE 如何处理大图PANE 面向“数千万节点、十亿级边、百万级属性”的单机大图，核心不是简单抽样，而是从算法结构上避免不可扩展的计算：不构造n×nn\times nn×n的节点相似度矩阵。它直接建模节点—属性亲和度，只处理n×dn\times dn×d的矩阵，其中ddd是属性数。不实际采样海量随机游走。APMI 用稀疏矩阵递推直接近似多跳前向/后向随机游走概率，误差由ϵ\epsilonϵ控制。用 SVD 提供高质量初始化，再用循环坐标下降细化。这显著减少了达到收敛所需的迭代轮数。面向多核 CPU 做分块并行。Par-PANE 将节点和属性均匀分块，亲和度计算采用分块稀疏矩阵乘法，SVD 采用 split-merge，坐标下降也并行化。属性过多时使用 PANE++。先把相似属性聚成κ\kappaκ个“超级属性”，将主要开销中的ddd替换为κ\kappaκ，再把超级属性嵌入还原为原属性嵌入。单线程复杂度为O((md+ndk)log(1/ϵ))O((md+ndk)\log(1/\epsilon))O((md+ndk)log(1/ϵ))，并行版本每个线程约为O(((md+ndk)/nb)log(1/ϵ))O(((md+ndk)/n_b)\log(1/\epsilon))O(((md+ndk)/nb)log(1/ϵ))。实验中，含5930 万节点、9.8 亿条边的 MAG 图，Par-PANE 用 10 个线程约11.9 小时完成，而单线程约需 5 天。摘要给定图GGG，其中每个节点都关联一组属性，属性网络嵌入（attributed network embedding，ANE）将每个节点v∈Gv\in Gv∈G映射为紧凑向量XvX_vXv，该向量可用于下游机器学习任务。理想情况下，XvX_vXv应捕获节点vvv对各个属性的亲和度；这种亲和度不仅考虑vvv自身的属性关联，还考虑沿GGG中边与其相连节点的属性关联。获得能够支持准确预测的高效用嵌入本就困难；当有效 ANE 计算扩展到拥有数百万节点的大图时，难度又上升到全新的层级。已有方法在此类图上大多失效，表现为开销不可接受、嵌入质量低，或二者兼有。本文提出 PANE，一种面向超大图、有效且可扩展的 ANE 方法。在多个基准数据集上，以属性推断、链接预测和节点分类三种常用预测任务的准确率衡量，PANE 达到了当前最佳的结果质量。PANE 通过三项主要算法设计获得高可扩展性和有效性。第一，它基于一种新的属性网络随机游走模型构造学习目标。所得优化任务在大图上仍然具有挑战。第二，PANE 为该优化问题提供了高效求解器，其关键模块是精心设计的嵌入初始化，能够显著减少收敛所需的迭代次数。最后，PANE 对求解器进行非平凡的并行化以利用多核 CPU，在保持高质量结果的同时实现可扩展性。PANE 的性能取决于输入网络中的属性数。为处理具有大量属性的大型网络，我们进一步把 PANE 扩展为 PANE++，后者使用有效的属性聚类技术。我们在 8 个真实数据集上与 10 种已有方法进行了广泛比较。实验表明，PANE 和 PANE++ 在结果质量上始终优于所有已有方法，同时速度快数个数量级。关键词：网络嵌入；属性图；随机游走；矩阵分解；可扩展性1 引言网络嵌入是图分析的一项基础任务，在学术界和工业界都受到了广泛关注。给定输入图或网络GGG，网络嵌入把每个节点v∈Gv\in Gv∈G转换成紧凑、定长的向量XvX_vXv，以捕获节点vvv周围图结构的拓扑特征。然而，现实图数据通常还带有节点属性。若把图拓扑和属性当作彼此独立的特征，就会丢失重要的节点—属性亲和度信息，即一个节点沿GGG中一条或多条边能够到达哪些属性。例如，考虑包含公司和董事会成员的网络。我们可能发现，一家公司（如 Tesla）能够经由共同董事（Elon Musk）到达另一家相关公司（如 SpaceX）的属性。为了纳入此类信息，ANE 把节点周围的拓扑信息和属性信息共同映射到嵌入向量中，从而直接或通过下游机器学习任务支持准确预测。有效的 ANE 计算极具挑战，尤其是在拥有数百万节点和数十亿条边的超大图上。每个节点vvv可能关联大量属性，对应一个高维空间；而且，vvv的每个属性不仅影响vvv自身的嵌入，还会影响其邻居、邻居的邻居以及沿多跳边到达的远端节点。已有 ANE 方法在大图上的代价非常高。某类方法显式构造并分解n×nn\times nn×n矩阵。若图有 5000 万个节点，仅以双精度数存储该矩阵就需要超过 20 PB 内存，显然不可行。另一类方法用深度神经网络从连接和属性中抽取高阶特征；大数据上的训练计算量巨大，而且通常受 GPU 显存限制。因此，目前处理超大图的实际选择往往是使用大型集群，这不仅昂贵，还可能产生显著环境成本。此外，据我们所知，已有 ANE 方法都针对无向图设计，尚不清楚如何把边方向信息（如非对称传递性）纳入嵌入。现实中的许多图是有向图，已有方法会在这些图上产生次优结果。由此产生本文的问题：能否在一台服务器上，对超大规模、带属性、有向的图计算有效嵌入？本文给出肯定答案，并提出 PANE。它包括单线程版本 Seq-PANE、面向多核 CPU 优化的并行版本 Par-PANE，以及处理大量属性的 PANE++。在拥有数千万节点、近十亿条边、数百万种不同属性以及超过十亿个节点—属性关联的 Microsoft Academic Knowledge Graph（MAG）上，PANE 是单台服务器（10 个 CPU 核、1 TB 内存）上唯一可行且能在三项任务上产生高质量嵌入的方法。PANE 的四项主要贡献为：基于新的随机游走模型，设计周密的问题表述；高效求解器；对算法进行非平凡并行化，即 Par-PANE；通过有效属性聚类处理大属性集合，即 PANE++。具体而言，PANE 以移位逐点互信息（shifted pairwise mutual information，SPMI）为指导，用节点—属性协同投影逼近归一化多跳节点—属性亲和度。给定节点—属性对的亲和度由专门适配属性网络的随机游走定义。为利用边方向，本文分别定义前向与后向亲和度、嵌入和 SPMI。即便如此，直接求解仍需联合分解两个规模为O(nd)O(nd)O(nd)的矩阵。PANE 的求解器用高效贪心算法给优化器提供初值，大幅减少收敛迭代；随后再通过并行化充分利用多核 CPU。2 问题表述2.1 符号与术语属性网络记作G=(V,EV,R,ER)G=(V,E_V,R,E_R)G=(V,EV,R,ER)，其中VVV是节点集合，EV⊆V×VE_V\subseteq V\times VEV⊆V×V是边集合，RRR是属性集合，ER⊆V×RE_R\subseteq V\times RER⊆V×R是节点—属性关联集合。令n=∣V∣n=|V|n=∣V∣、m=∣EV∣m=|E_V|m=∣EV∣、d=∣R∣d=|R|d=∣R∣。符号含义G=(V,EV,R,ER)G=(V,E_V,R,E_R)G=(V,EV,R,ER)节点、边、属性和节点—属性关联组成的图n,m,dn,m,dn,m,d节点数、边数、属性数kkk嵌入向量的空间预算A,D,P,RA,D,P,RA,D,P,R邻接矩阵、出度矩阵、随机游走矩阵和属性矩阵Rr,RcR_r,R_cRr,Rc行归一化与列归一化属性矩阵F,BF,BF,B前向与后向亲和度矩阵F′,B′F',B'F′,B′近似前向与后向亲和度矩阵Xf,Xb,YX_f,X_b,YXf,Xb,Y前向节点嵌入、后向节点嵌入和属性嵌入α\alphaα随机游走停止概率ϵ\epsilonϵ亲和度近似误差阈值nbn_bnb并行线程数κ\kappaκPANE++ 中超级属性数邻接矩阵A∈Rn×nA\in\mathbb{R}^{n\times n}A∈Rn×n满足：若(vi,vj)∈EV(v_i,v_j)\in E_V(vi,vj)∈EV，则A[vi,vj]=1A[v_i,v_j]=1A[vi,vj]=1，否则为 0。出度矩阵DDD是对角矩阵，D[vi,vi]D[v_i,v_i]D[vi,vi]等于viv_ivi的出度。随机游走转移矩阵为P=D−1AP=D^{-1}AP=D−1A。属性矩阵R∈Rn×dR\in\mathbb{R}^{n\times d}R∈Rn×d满足：若(vi,rj)∈ER(v_i,r_j)\in E_R(vi,rj)∈ER，则R[vi,rj]=1R[v_i,r_j]=1R[vi,rj]=1，否则为 0。行归一化和列归一化属性矩阵定义为Rr[vi,rj]=R[vi,rj]∑rl∈RR[vi,rl],Rc[vi,rj]=R[vi,rj]∑vl∈VR[vl,rj].(1) R_r[v_i,r_j]=\frac{R[v_i,r_j]}{\sum_{r_l\in R}R[v_i,r_l]},\qquad R_c[v_i,r_j]=\frac{R[v_i,r_j]}{\sum_{v_l\in V}R[v_l,r_j]}. \tag{1}Rr[vi,rj]=∑rl∈RR[vi,rl]R[vi,rj],Rc[v PANE: Scalable and Effective Attributed Network Embedding
PANE：可扩展且有效的属性网络嵌入阅读重点：PANE 如何处理大图PANE 面向“数千万节点、十亿级边、百万级属性”的单机大图，核心不是简单抽样，而是从算法结构上避免不可扩展的计算：不构造n×nn\times nn×n的节点相似度矩阵。它直接建模节点—属性亲和度，只处理n×dn\times dn×d的矩阵，其中ddd是属性数。不实际采样海量随机游走。APMI 用稀疏矩阵递推直接近似多跳前向/后向随机游走概率，误差由ϵ\epsilonϵ控制。用 SVD 提供高质量初始化，再用循环坐标下降细化。这显著减少了达到收敛所需的迭代轮数。面向多核 CPU 做分块并行。Par-PANE 将节点和属性均匀分块，亲和度计算采用分块稀疏矩阵乘法，SVD 采用 split-merge，坐标下降也并行化。属性过多时使用 PANE++。先把相似属性聚成κ\kappaκ个“超级属性”，将主要开销中的ddd替换为κ\kappaκ，再把超级属性嵌入还原为原属性嵌入。单线程复杂度为O((md+ndk)log(1/ϵ))O((md+ndk)\log(1/\epsilon))O((md+ndk)log(1/ϵ))，并行版本每个线程约为O(((md+ndk)/nb)log(1/ϵ))O(((md+ndk)/n_b)\log(1/\epsilon))O(((md+ndk)/nb)log(1/ϵ))。实验中，含5930 万节点、9.8 亿条边的 MAG 图，Par-PANE 用 10 个线程约11.9 小时完成，而单线程约需 5 天。摘要给定图GGG，其中每个节点都关联一组属性，属性网络嵌入（attributed network embedding，ANE）将每个节点v∈Gv\in Gv∈G映射为紧凑向量XvX_vXv，该向量可用于下游机器学习任务。理想情况下，XvX_vXv应捕获节点vvv对各个属性的亲和度；这种亲和度不仅考虑vvv自身的属性关联，还考虑沿GGG中边与其相连节点的属性关联。获得能够支持准确预测的高效用嵌入本就困难；当有效 ANE 计算扩展到拥有数百万节点的大图时，难度又上升到全新的层级。已有方法在此类图上大多失效，表现为开销不可接受、嵌入质量低，或二者兼有。本文提出 PANE，一种面向超大图、有效且可扩展的 ANE 方法。在多个基准数据集上，以属性推断、链接预测和节点分类三种常用预测任务的准确率衡量，PANE 达到了当前最佳的结果质量。PANE 通过三项主要算法设计获得高可扩展性和有效性。第一，它基于一种新的属性网络随机游走模型构造学习目标。所得优化任务在大图上仍然具有挑战。第二，PANE 为该优化问题提供了高效求解器，其关键模块是精心设计的嵌入初始化，能够显著减少收敛所需的迭代次数。最后，PANE 对求解器进行非平凡的并行化以利用多核 CPU，在保持高质量结果的同时实现可扩展性。PANE 的性能取决于输入网络中的属性数。为处理具有大量属性的大型网络，我们进一步把 PANE 扩展为 PANE++，后者使用有效的属性聚类技术。我们在 8 个真实数据集上与 10 种已有方法进行了广泛比较。实验表明，PANE 和 PANE++ 在结果质量上始终优于所有已有方法，同时速度快数个数量级。关键词：网络嵌入；属性图；随机游走；矩阵分解；可扩展性1 引言网络嵌入是图分析的一项基础任务，在学术界和工业界都受到了广泛关注。给定输入图或网络GGG，网络嵌入把每个节点v∈Gv\in Gv∈G转换成紧凑、定长的向量XvX_vXv，以捕获节点vvv周围图结构的拓扑特征。然而，现实图数据通常还带有节点属性。若把图拓扑和属性当作彼此独立的特征，就会丢失重要的节点—属性亲和度信息，即一个节点沿GGG中一条或多条边能够到达哪些属性。例如，考虑包含公司和董事会成员的网络。我们可能发现，一家公司（如 Tesla）能够经由共同董事（Elon Musk）到达另一家相关公司（如 SpaceX）的属性。为了纳入此类信息，ANE 把节点周围的拓扑信息和属性信息共同映射到嵌入向量中，从而直接或通过下游机器学习任务支持准确预测。有效的 ANE 计算极具挑战，尤其是在拥有数百万节点和数十亿条边的超大图上。每个节点vvv可能关联大量属性，对应一个高维空间；而且，vvv的每个属性不仅影响vvv自身的嵌入，还会影响其邻居、邻居的邻居以及沿多跳边到达的远端节点。已有 ANE 方法在大图上的代价非常高。某类方法显式构造并分解n×nn\times nn×n矩阵。若图有 5000 万个节点，仅以双精度数存储该矩阵就需要超过 20 PB 内存，显然不可行。另一类方法用深度神经网络从连接和属性中抽取高阶特征；大数据上的训练计算量巨大，而且通常受 GPU 显存限制。因此，目前处理超大图的实际选择往往是使用大型集群，这不仅昂贵，还可能产生显著环境成本。此外，据我们所知，已有 ANE 方法都针对无向图设计，尚不清楚如何把边方向信息（如非对称传递性）纳入嵌入。现实中的许多图是有向图，已有方法会在这些图上产生次优结果。由此产生本文的问题：能否在一台服务器上，对超大规模、带属性、有向的图计算有效嵌入？本文给出肯定答案，并提出 PANE。它包括单线程版本 Seq-PANE、面向多核 CPU 优化的并行版本 Par-PANE，以及处理大量属性的 PANE++。在拥有数千万节点、近十亿条边、数百万种不同属性以及超过十亿个节点—属性关联的 Microsoft Academic Knowledge Graph（MAG）上，PANE 是单台服务器（10 个 CPU 核、1 TB 内存）上唯一可行且能在三项任务上产生高质量嵌入的方法。PANE 的四项主要贡献为：基于新的随机游走模型，设计周密的问题表述；高效求解器；对算法进行非平凡并行化，即 Par-PANE；通过有效属性聚类处理大属性集合，即 PANE++。具体而言，PANE 以移位逐点互信息（shifted pairwise mutual information，SPMI）为指导，用节点—属性协同投影逼近归一化多跳节点—属性亲和度。给定节点—属性对的亲和度由专门适配属性网络的随机游走定义。为利用边方向，本文分别定义前向与后向亲和度、嵌入和 SPMI。即便如此，直接求解仍需联合分解两个规模为O(nd)O(nd)O(nd)的矩阵。PANE 的求解器用高效贪心算法给优化器提供初值，大幅减少收敛迭代；随后再通过并行化充分利用多核 CPU。2 问题表述2.1 符号与术语属性网络记作G=(V,EV,R,ER)G=(V,E_V,R,E_R)G=(V,EV,R,ER)，其中VVV是节点集合，EV⊆V×VE_V\subseteq V\times VEV⊆V×V是边集合，RRR是属性集合，ER⊆V×RE_R\subseteq V\times RER⊆V×R是节点—属性关联集合。令n=∣V∣n=|V|n=∣V∣、m=∣EV∣m=|E_V|m=∣EV∣、d=∣R∣d=|R|d=∣R∣。符号含义G=(V,EV,R,ER)G=(V,E_V,R,E_R)G=(V,EV,R,ER)节点、边、属性和节点—属性关联组成的图n,m,dn,m,dn,m,d节点数、边数、属性数kkk嵌入向量的空间预算A,D,P,RA,D,P,RA,D,P,R邻接矩阵、出度矩阵、随机游走矩阵和属性矩阵Rr,RcR_r,R_cRr,Rc行归一化与列归一化属性矩阵F,BF,BF,B前向与后向亲和度矩阵F′,B′F',B'F′,B′近似前向与后向亲和度矩阵Xf,Xb,YX_f,X_b,YXf,Xb,Y前向节点嵌入、后向节点嵌入和属性嵌入α\alphaα随机游走停止概率ϵ\epsilonϵ亲和度近似误差阈值nbn_bnb并行线程数κ\kappaκPANE++ 中超级属性数邻接矩阵A∈Rn×nA\in\mathbb{R}^{n\times n}A∈Rn×n满足：若(vi,vj)∈EV(v_i,v_j)\in E_V(vi,vj)∈EV，则A[vi,vj]=1A[v_i,v_j]=1A[vi,vj]=1，否则为 0。出度矩阵DDD是对角矩阵，D[vi,vi]D[v_i,v_i]D[vi,vi]等于viv_ivi的出度。随机游走转移矩阵为P=D−1AP=D^{-1}AP=D−1A。属性矩阵R∈Rn×dR\in\mathbb{R}^{n\times d}R∈Rn×d满足：若(vi,rj)∈ER(v_i,r_j)\in E_R(vi,rj)∈ER，则R[vi,rj]=1R[v_i,r_j]=1R[vi,rj]=1，否则为 0。行归一化和列归一化属性矩阵定义为Rr[vi,rj]=R[vi,rj]∑rl∈RR[vi,rl],Rc[vi,rj]=R[vi,rj]∑vl∈VR[vl,rj].(1) R_r[v_i,r_j]=\frac{R[v_i,r_j]}{\sum_{r_l\in R}R[v_i,r_l]},\qquad R_c[v_i,r_j]=\frac{R[v_i,r_j]}{\sum_{v_l\in V}R[v_l,r_j]}. \tag{1}Rr[vi,rj]=∑rl∈RR[vi,rl]R[vi,rj],Rc[v