基于多粒度的异质图表示

芮品德 ，赵桓幜 ，赵姝 *，张燕平

（1.计算与信号处理教育部重点实验室，安徽 合肥 230601；2.安徽大学 计算机科学与技术学院，安徽 合肥 230601；3.安徽省信息材料与智能传感重点实验室，安徽 合肥 230601）

0 引言

如今，随着生产生活造就的“大数据”时代，“大数据”通常与多种类型的对象和关系相关联，利用同质图来抽象这些复杂的交互关系较为困难，而异质图［1］可以有效建模这样的复杂系统。因此，挖掘异质图潜在的价值具有重要的现实意义。异质图表示学习［2-3］是挖掘异质图的重要工具之一，其目标是将异质图中的节点投影到一个潜在的低维空间中，从而保留图中蕴含的丰富的结构和语义信息，同时这些表示可以较好地服务于下游任务如节点分类［4］、网络可视化［5-6］和社区发现［7-8］等。

异质图包含多种类型的节点和多种类型的关系。目前的异质图表示方法［9-14］主要根据元路径［1］、元图［15-17］和网络模式［18］所代表的语义信息进行采样，将异质图转化为给定语义下的节点序列或子图。元路径是定义在节点之间的关系序列，元图则是一种多条元路径非线性组合的更复杂的关系序列。不同于元路径和元图，网络模式是异质图中所有的关系类型的不重复集合。早期的异质图表示学习方法通过基于元路径、元图的随机游走序列采样，并利用浅层模型学习节点间的局部结构信息。而后，基于深度图神经网络的方法则是利用元路径、网络模式对异质图采样以得到不同语义下的同质子图，并通过深度神经网络建模以学习同类型节点在同质子图上的局部信息。这些方法主要关注于异质图中同类型节点的局部相似度，而现实世界的异质图中往往存在着层次结构，并且该层次结构对于学习图的表示起重要作用。

以学校中的学生和课程构建的异质图为例，在图1中，随着粒度由细到粗，每个粒度上的节点都存在着共性。从最细粒度开始（学生），每个学生都是独立的个体。在更粗的一个粒度上（专业），每个专业有各自必修的课程。如软件工程专业的学生必修软件设计课程，网络工程专业的学生必修网络安全课程等。在更粗的一个粒度上（院系），每个院系有各自的专业基础课，如计算机系学习计算机导论，化学系学习有机化学等。在最粗粒度（学校）上，所有学生会统一学习毛概课程。从多粒度视角来看，异质图中包含着层次结构信息，并且随着粒度由细变粗，不同类型的节点间依旧保持着拓扑上的关联关系。因此，如何在异质图表示中保留层次结构信息是本文待解决的问题。

为解决上述问题，我们引入商空间理论［19］中多粒度的思想。该思想的核心是在不同粒度下对问题进行分析和探究，并综合问题在不同粒度中的解来获得原问题的解的过程，在求解问题的同时也保留了不同粒层的信息。基于该思想，我们将寻求最优的异质图表示作为原问题，构建多个多粒度子网络，并在学习图的表示的过程中量化节点在各个粒度内的潜在关联关系，以保留异质图的层次结构信息。具体来说，我们首先基于不同的元路径将异质图采样成多个同质子图以处理异质性，再对同质子图进行社团划分以逐层粗化，最终形成多个多粒度子网络以保留层次结构。其次，对于每个多粒度子网络，在其最粗层通过现有的图表示学习方法得到最粗图的表示，再将最粗层图的表示利用不同粒度间的转换关系逐层细化，以得到异质图中的节点在该多粒度子网络下的表示。最后，利用注意力机制学习不同元路径的权重，以对不同元路径对应的多粒度子网络下的表示进行融合，并得到节点的最终表示。本文贡献点如下：

1） 针对目前的异质图表示学习未考虑图中的层次结构信息这一问题，提出基于多粒度的异质图表示学习方法。基于多粒度思想，在异质图表示过程中保留层次结构信息，以获得更有效的节点表示。

2） 提出基于多粒度的异质图表示学习方法（Heterogeneous Graph Representations Based on Multi-granularity， HeMug）。通过元路径构建多个同质子图，利用社团划分将同质子图形成多粒度子网络来保留层次结构信息。

3） 本文在 ACM（Association for Computing Machinery）、DBLP（DataBase systems and Logic Programming）、Aminer（Academic Research Net⁃work Miner）和Freebase四个数据集上进行实验，实验结果表明了所提方法HeMug的有效性。

1 相关工作

多粒度思想是从不同角度和多个层次对问题进行求解，并综合多个侧面理解来获得原问题的解。粒计算方法是针对多粒度数据的研究方法，目前已有许多研究工作。如，商空间理论［19-21］将复杂问题表示成不同的粒度空间，研究粒层之间的转换关系，综合不同粒度空间的解来组合原问题的解。粗糙集理论［22-23］是利用不可分辨关系建立近似空间，基于已知的局部知识的融合得到更全面的知识。三支决策［24］将复杂问题映射到三个不同域中，对不同的部分分别进行分析求解。

在异质图表示学习中，目前的方法可大致分为两类：浅层的异质图表示和深层的异质图表示。基于浅层模型的方法主要通过基于元路径和元图的随机游走来将异质图分解为多个节点序列，然后利用浅层神经网络对节点序列中节点的局部信息进行建模，以得到节点的表示。Metapath2vec（Scalable Representation Learning for Heterogeneous Networks）［25］利用单条元路径指导的随机游走来获取图的局部结构，并通过异质的skip-gram模型来学习节点的表示。HHNE（Hyperbolic Hetero⁃geneous Information Network Embedding）［26］引入双曲空间中的黎曼流形来学习基于单条元路径随机游走序列中节点间的相似性。HERec（Hetero⁃geneous Information Network Embedding for Rec⁃ommendation）［27］则是通过在多条元路径指导的随机游走序列中提取相同类型的节点，以构造同类型节点间的游走序列来学习同类型节点间的局部结 构 。 Metagraph2vec（Complex Semantic Path Augmented Heterogeneous Network Embedding）［28］提出基于元图随机游走来处理异质图的异质性并利用skip-gram模型学习局部相似度。Mg2vec（Learning Relationship-preserving Heterogeneous Graph Representations via Metagraph Embedding）［29］将元图映射到与节点相同的表示空间中，即联合学习元图和节点的表示。

基于深层模型的方法主要基于元路径和网络模式采样多个同质子图，然后利用深度神经网络来学习节点间非线性的关系。如，HAN（Heterogeneous Graph Attention Network）［30］通过不同的对称元路径构建多个同质子图，并设计注意力机制学习同类型节点在各个同质子图内的局部结构信息。MAGNN（Metapath Aggre⁃gated Graph Neural Network for Heterogeneous Graph Embedding）［31］在 HAN 的基础上保留同质子图内节点的局部结构信息时，量化了不同类型节点的影响。NSHE（Network Schema Pre⁃serving Heterogeneous Information Network Em⁃bedding）［18］提出一种以网络模式采样的方法来抽取子图，然后构建多任务学习来学习节点的表 示 。 HeCo（Self-supervised Heterogeneous Graph Neural Network with Co-contrastive Learn⁃ing）［32］提出一种新的混合神经网络协同对比学习机制，利用元路径和网络模式两种视角进行对比以融合同类型节点之间和不同类型节点之间的局部结构信息。

综上，浅层的异质图表示侧重于捕获异质图中的局部结构，虽然基于skip-gram（Efficient estimation of word representations in vector space）的方法可以通过增大滑动窗口的方式捕获全局信息，但会导致模型过平滑的问题，并且该类方法缺乏对于层次结构的保留。深层的异质图表示利用深度神经网络保留各个元路径、网络模式采样的同质子图内的局部信息，相比于浅层模型获得了更强的表示，但模型依旧缺乏对于层次结构的保留。为了在异质图表示学习中有效地保留图中的层次结构，我们根据多粒度，提出在异质图中基于元路径构建多粒度子网络，并利用注意力机制融合不同多粒度子网络信息的方法。

2 相关定义

本节中，将给出异质图、异质图表示、同质子图和多粒度子网络的相关定义。

定义1 异质图：给定异质图G=(V，E，T，ϕ，φ)，其中 V 和 E 分别表示节点集和边集。每个点v∈V存在点类型映射函数ϕ：V→TV。每条边e∈E存在边类型映射函数ϕ：E→TE，其中TV和TE分别表示节点和边的类型集合，并且|TV|>=1且| |TE>=1。

定义2 异质图表示：对于异质图G中的节点v∈V，通过学习映射f：v→Rd将其投影到低维空间，其中d≪| |V。

定义3 同质子图：给定异质图G中的任一节点类型ε∈ϕ(V)和元路径Pt，存在同质子图GPt=(V′，E′，A′)，V′中的节点需满足属于同一节点类型，形式化为 ∀v∈V′， ϕ(v)= ε，A′是加权邻接矩阵， 权重值是节点间的相似度。

定义4 多粒度子网络：给定一个同质子图GPt=(V′，E′，A′)，使，一系列在不同粒度下的网络构成的集合称为多粒度子网络。≻表示更细的，代表相比于来自于更细的粒度。随着粒度变粗，粗粒度下的节点集合是由细粒度下′的节点构造而成的，且存在

3 基于多粒度的异质图表示

本文提出的基于多粒度的异质图表示模型HeMug如图2所示，HeMug共分为三个部分。（1）基于同质子图构建多粒度子网络。通过多条元路径将异质图划分为多个同质子图以处理异质性，接着利用社团划分的方法将多个同质子图粗化为不同的多粒度子网络。（2）多粒度子网络表示。对于每个多粒度子网络，利用现有的表示学习方法在最粗层学习获得最粗层节点的表示，然后再逐层细化得到节点在该多粒度子网络下的表示。（3）融合不同元路径下的多粒度子网络表示。利用注意力机制融合不同元路径下多粒度子网络的节点表示。

3.1 基于同质子图构建多粒度子网络

元路径是异质图中一种能够表达语义的结构，它被普遍地用于衡量节点间的相似度。例如 ，Pathsim（Meta Pathbased Top-k Similarity Search in Heterogeneous Information Networks）［1］是一种基于对称元路径的测量同类型节点间相似度的方法，节点vx和vy之间的相似度由这两个节点基于给定元路径Pt的路径实例数的归一化来表示的，其公式如下：

其中，INSPt(a，b)是从点a出发到点b的满足元路径Pt的所有节点序列条数，该公式可以看出点vx和点vy之间基于元路径Pt的相似度取决于两点之间满足Pt的节点序列条数以及从两点出发再返回两点的满足Pt的节点序列条数。节点间的相似性代表着节点间相关的重要程度，因此我们将节点之间的相似性视为边权重，并利用同类型节点对应的相似性矩阵来构建加权的同质子图。每条元路径只能从一个侧面反映异质图的语义信息，为了在图表示中更全面地保留异质图的信息，利用不同的元路径来构建多个同质子图是必要的。给定一个 包含 T 个对称元路径集合 P={P1，P2，…，PT}，基于每条元路径Pt∈P构建一个同质子图。同质子图集包含同种类型节点间的不同语义信息，其中每个同质子图GPt内的节点是相同的。

对于每个同质子图GPt，基于多粒度的粗化思想来构建一个多粒度子网络。具体来说，将同质子图GPt作为多粒度子网络的最细粒度，即网络的第一层。接着，根据网络中节点的聚集特性，构造第二层以此类推，再由，层数L设为超参数。在本文中，采用基于模块度的 Louvain（Fast Unfolding of Communities in Large Networks）［33］算法 ，该算法能利用拓扑结构有效地捕获同质子图中节点的聚集倾向。具体来说，将细粒度l层内的每个社团内的点合并作为超点，并保留至更粗粒度l+1层，超点之间的连边则由l层内社团间的连边所构建。

3.2 多粒度子网络表示

本文选用被广泛应用的Node2vec（Scal⁃able Feature Learning for Networks）［34］作 为Emb(⋅)函数的表示算法，该算法通过随机游走采样图中节点序列，得以有效地运用图中的拓扑信息。

接着，基于多粒度细化的思想，从粗粒度L层到细粒度层逐层细化进行跨粒度学习，以得到同质子图GPt的表示，该表示通过多粒度细化中的信息传递，保留了同质子图的层次信息。在本文中，我们利用图卷积神经网络GCN（Semi-Supervised classification with graph convolu⁃tional networks）［35］实现细化过程中粒层内的信息保留和粒层间的信息传递。具体的，多粒度子网络的第l层，图首先通过图卷积实现粒度内的信息保留，定义如下：

其中，θl表示多粒度子网络第l层的图卷积网络GCN 的超参数，σ(⋅)是激活函数，是图的度矩阵，表示图的节点集合，是控制添加自循环的超参数，在本文中设置λ为0.05，则表示图的邻接矩阵。是图卷积神经网络的可训练参数矩阵。表示节点在第l层的特征矩阵，由更粗粒度的l+1层超点的特征传递得来，定义为：

在多粒度子网络最粗层L层，我们利用邻接矩阵降维作为L层节点的初始化特征，并将任意表示学习方法学到的表示作为最顶层图卷积网络的监督信息以训练图卷积网络参数θL，形式化描述为：

其中PCA(⋅)表示降维函数。为了实现多粒度子网络中不同粒度间的信息传递，我们只在最粗层L层训练图卷积模型，而后利用参数共 享 实 现 细 化 ，存 在 θL=θL−1=…=θ1，

通过上述公式（5）（6）逐层细化操作，我们得到最细粒度上的图表示最为节点在该多粒度子网络下的表示。在多个元路径对应的多粒度子网络上执行上述操作，最终获得在给定的多条元路径下对应的多粒度子网络中最细层节点的表示集合

3.3 融合不同元路径下的多粒度子网络表示

基于给定的一条元路径获得的多粒度子网络下的节点表示仅能够表达异质图中的一种语义下的层次结构信息。为了在嵌入中更好地融合多个侧面的语义信息，本文利用注意力机制来学习异质网络中不同语义的重要性。由于通过元路径采样的同质子图代表了异质图上的同类型节点间的高阶信息，为了兼顾不同类型节点间的局部信息，首先利用现有的同质图表示学习方法获得节点的表示，并将其与不同语义下的多粒度子网络表示得以保留，使图中的高阶信息与低阶信息合并，对于同质子图GPt中的节点vx的多粒度表示，其融合后的向量表示如下：

其中，σ表示激活函数，⊕表示拼接操作，WPt和分别表示在元路径Pt下可学习的参数矩阵和偏移向量。表示节点vx在异质图G上的节点表示，。通过以上步骤，对于节点vx，基于每条元路径Pt，我们可获得一个节点表示的集合。然后，利用自注意力机制来学习该条元路径的重要性βPt，具体如下：

其中，W是权重矩阵，b是偏移向量，q是语义级注意力向量，分别是可学习的参数。最后，根据元路径的权重将表示向量进行融合获得节点vx的向量Zvx。具体如下：

在获得最终的节点向量Zvx后，采用正负采样策略，与现有的工作HeCo［5］类似，如果两个节点之间存在多条元路径，则为正边，否则视为负边，损失函数L如下：

其中，E和E−分别表示正采样和负采样的节点对，cos(⋅)表示余弦相似度，α 是超参数。

4 实验结果与分析

4.1 数据集

本文实验采用四个数据集。数据集ACM［18］是一个论文网络，包含三种节点类型（论文、作者和科目）和两种类型边（论文-作者和论文-科目）。数据集DBLP［31］是一个计算机科学书目网络，其包含四种类型节点（作者、论文、会议和术语）和三种类型的边（作者-论文、论文-术语、论文-会议）。数据集Aminer［36］是一个学术网络，其包含三种类型的节点（论文、作者和参考文献）和两种类型的边（论文-作者和论文-参考文献）。数据集Freebase［37］是一个电影网络，其包含四种类型节点（电影、演员、导演和作家）和两种类型的边（电影-演员，电影-导演，电影-作家）。更具体的数据集信息见表1。

4.2 对比算法

本文与七个图表示学习算法进行比较，包括经典的传统同质图表示算法：Node2vec，基于浅层模型的异质图表示学习算法：Metapath2vec（MP2vec）、HERec、MetaGraph2vec（MG2vec），基于深层模型的异质图表示学习算法：HAN、NSHE、HeCo。

嵌入维度设置为128维，对于Node2vec，设置窗口大小为10，随机游走长度为80，游走数量为10，参数p和q为1。对于MP2vec、HERec和HAN，设置随机游走长度为10，窗口大小为10，学习率为0.001，其中HAN使用的节点特征是图的领接矩阵。对于NSHE，使用的节点特征是应用deepwalk获得的节点向量，对于参数α和β在数据集ACM、DBLP、Freebase和Amin⁃er分 别 为（0.001，0.135）、（0.008，0.905）、（0.008，0.05）和（0.008，0.05）。对于HeCo，所有的参数是其论文中原有的设置。

4.3 节点分类

分别在4个数据集进行了节点分类的实验。在通过本文模型获得节点的表示向量之后，训练有标签的节点表示在20%、40%、60%和80%的线性支持向量机（SVM）上，并测试未被训练的有标签节点，通过Micro-F1和Macro-F1进行结果评估。所有的实验结果都是10次实验的平均结果。表2、表3、表4和表5分别是在数据集ACM、DBLP、Aminer和Freebase上节点分类的实验结果。从实验结果来看，Node2vec的性能优于传统异质模型，而使用分层的多粒度模型，不论层数、结果均优于Node2vec，这表明异质图中的多粒度结构对于表示质量的提高是有帮助的。相较于使用了节点特征的深层模型（HAN、NSHE和HeCo），本文方法依然在大部分情况获得更好的结果。从结果中还可以发现，在ACM和DBLP上，本文模型都在第一层的结果最优，这与图的规模有关。对于较小的图，层数增加对应的信息损失越多。相较于ACM和DBLP，Aminer和Free⁃base规模更大，在非第一层也有最优的结果。

4.4 节点聚类

对于聚类任务，使用K-means算法来分类节点的表示并通过NMI进行评估结果。聚类实验结果如表6所示。从结果来看，在DBLP和Aminer上，本文结果要优于其他对比算法。在ACM上，除了HeCo，本文结果是最优的。在Freebase上，可以看出传统的异质方法略过于其他算法。从本文方法的不同层次来看，依然在相对较小的数据集上粗化一次取得最好的结果，在相对较大的数据集上粗化多次可以取得更好的效果。

4.5 HeMug层次结构分析

HeMug模型基于多粒度思想在异质图中构建了层次结构，并在表示学习过程中保留了层次结构信息。在4.3节点分类和4.4节点聚类的实验中，本文结果基本优于对比算法。为了说明层次结构信息对实验结果的提升起到了重要作用，在数据集ACM和Freebase上进行层次结构的分析实验。设计了不同层次的对比实验，分别有无层次结构（k=0）、有层次结构（k=1，2，3）。使用的实验指标是与节点分类实验相同。从表6中可以看出，在HeMug中粗化同质子图并构建了层次结构的实验结果要明显优于无层次结构的结果，这表明HeMug图表示过程保留的层次结构信息是有效的。

4.6 时间对比

本文将对比算法和HeMug在数据集ACM和Freebase上实验的时间进行对比，结果如表8所示。从表中可以看出，HeMug在ACM数据上耗时最短，在Freebase数据上仅次于MP2vec。MP2vec由于其稀疏的随机游走采样，以较少的时间开销完成图表示学习，但也损失了部分网络结构信息，导致在分类、聚类实验中的效果低于HeMug。

5 结论与展望

本文基于多粒度的粗化、细化思想在异质图表示学习中保留图中的层次结构信息，提出基于多粒度的异质图表示学习方法HeMug。该方法首先为了保留图中的层次结构信息，将异质图通过不同的元路径划分成多个同质子图，再粗化形成多个多粒度子网络。其次通过细化学习每个多粒度子网络的节点表示。最后为了获得异质图中更全面的节点表示，利用注意力机制融合不同元路径下的多粒度子网络表示。通过在四个真实的数据集上进行了实验，实验结果表明，HeMug可以获得更高质量的异质图表示。