异质信息网络分析与应用综述

石川, 王睿嘉, 王啸. 异质信息网络分析与应用综述. 软件学报, 2022, 33(2): 598–621. http://www.jos.org.cn /1000-9825/6357.html

摘要

• 什么是信息网络？
  现实生活中形形色色的系统, 通常由大量类型各异、彼此交互的组件构成, 例如生物、社交和计算机系统等。 在这些系统中, 相互作用的组件可以抽象为信息网络

---

• 什么是同质网络？
  网络中仅包含相同类型的对象和链接, 例如作者合作网和朋友圈等。同质网络建模方法往往只抽取了实际交互系统中的部分信息, 或者没有区分对象及其之间关系的异质性。
  【网络中包含不相同类型的对象和链接则为异质网络】

---

• 同质网络存在的问题：
  目前, 大多数工作将这些交互系统建模为同质信息网络, 并未考虑不同类型对象的复杂异质交互关系, 因而造成大量信息损失。
  .
  近年来, 越来越多的研究者将这些交互数据建模为由不同类型节点和边构成的异质信息网络, 从而利用网络中全面的结构信息和丰富的语义信息进行更精准的知识发现。

---

• 异质网络的好处：
  (1)异质网络是融合信息的有效工具, 不仅可以自然融合不同类型的对象及其交互, 而且可以融合异构数据源的信息。
  .
  (2)异质网络中多类型对象和关系共存, 包含丰富的结构和语义信息, 从而为发现隐含模式提供了精准可解释的新途径。

---

异质网络基础知识

基本概念

• 信息网络：
  信息网络是对现实世界的抽象, 重点关注于对象及其之间的交互。
  .
  定义：
  信息网络定义为一个具有对象类型映射函数$\phi :V\to A$和关系类型映射函数$\psi :E\to R$的有向图$G=(V,E,\phi ,\psi )$。其中, 每个对象$v\in V$属于对象类型集合$A:\phi (v)\in A$中的一个特定对象类型, 每条链接e∈E属于关系类型集合$R:\psi (e)\in R$中的一个特定关系类型。

个人理解：

• 信息网络存在两个揭示网络信息的函数：$\phi$和$\psi$。
• 网络中的节点都通能过函数$\phi$映射到到某个类型集合，类似聚类。
• 每个节点的边都能通过$\psi$映射到某个关系，就像揭示节点间的关系。

---

• 异质/同质网络：
  与社会网络分析不同, 信息网络明确区分网络中的对象和关系类型, 就产生了异质/同质网络的概念。
  .
  定义：
  若信息网络的对象类型数$|A|>1$或者关系类型数$|R|>1$, 则称其为异质网络; 否则, 称为同质网络.

---

• 网络模式：
  为了更好地理解异质网络中复杂的对象和关系类型, 网络模式的概念被提了出来, 从而在元层次(即模式层次)上对网络进行描述。
  .
  定义：
  网络模式记为$T_G=(A,R)$, 是带有对象类型映射$\phi :V\to A$和关系类型映射$\psi :E\to R$的信息网络$G=(V,E,\phi ,\psi )$的元模式。具体地, 网络模式是定义在对象类型集合$A$上的有向图, 并以$R$上的关系为边。
  具体地, 网络模式是定义在对象类型集合$A$上的有向图, 并以$R$上的关系为边。

---

语义探索方法

异质网络中两对象可以通过不同类型定义的路径连接, 而这些路径隐含不同的语义。

• 元路径：
  元路径$P$是在网络模式$T_G=(A,R)$上定义的路径, 记为$A_1\stackrel{R_1}{\to }{A}_2\stackrel{R_2}{\to }\cdots \stackrel{R_l}{\to }{A}_{l+1}$
  .
  定义对象类型$A_1,A_2,\dots ,A_{l+1}$间的复合关系$R=R_1\circ R_2\circ \dots \circ R_l$, 其中, $\circ$表示关系上的合成运算符
  .
  若相同对象类型间没有多种关系类型, 则可以利用对象类型来表示元路径: $P=(A_1,A_2,\dots ,A_{l+1})$。此外，对象$a_1$和$a_{l+1}$间的具体路径$p=(a_1{a}_2\dots a_{l+1})$是路径 P 的路径实例。

以电影推荐异质网络为例，用户可以通过元路径相连：

• UMU路径表示用户(User)对同一电影的评分(Rate)，U和U之间是共同评分关系
  $$U\stackrel{rate}{\to }M\stackrel{rat{e}^{-1}}{\to }U$$

• UMDMU路径表示用户对统一导演的电影作品打分
  $$U\stackrel{rate}{\to }M\stackrel{direc{t}^{-1}}{\to }D\stackrel{direc{t}^1}{\to }M\stackrel{rat{e}^{-1}}{\to }U$$

• 元路径的缺点：
  元路径本质上抽取了异质网络的子结构,但是由于其结构简单, 在捕捉更精确或复杂的语义时往往受到限制。例如, UMU 路径无法刻画精确到某些类型电影的共同评分关系。
  .
  因此, 受限元路径应运而生。

---

• 受限元路径：
  受限元路径是基于某种特定约束的元路径, 可以表示为$CP=P|C$。
  其中,$P=(A_1,A_2,\dots ,A_l)$表示元路径,$C$表示对元路径$P$中对象的约束。

• $UMU|M.T=“Comedy”$：
  该路径表示用户对于喜剧电影的共同评分
• $UMDMU|M.T=“Comedy”\&\&D=“AngLee”$:
  表示用户对李安所导演的喜剧电影的共同评分关系

• 受限元路径缺点：
  未考虑链接上的属性, 如用户对于电影的评分信息, 从而使得路径实例间链接的属性差异诱发较大的语义差异。
  .
  因而, 加权元路径的概念被提出, 以进一步约束链接属性信息。

---

• 加权元路径：
  加权元路径是对关系属性值有所约束的一种扩展元路径, 可以表示为：
  $$A_1\stackrel{{\delta }_1(R_1)}{\to }{A}_2\stackrel{{\delta }_2(R_2)}{\to }\cdots \stackrel{{\delta }_l(R_l)}{\to }{A}_{l+1}|C$$
  , 也记作:
  $$A_1({\delta }_1(R_1))A_2({\delta }_2(R_2))\dots ({\delta }_l(R_l))A_{l+1}|C$$

• 加权元路径:$U\stackrel{1}{\to }M$：
  $U(1)M$路径表示用户对电影的评分为1，即不喜欢该电影
• 加权元路径:$U\stackrel{1,2}{\to }M\stackrel{1,2}{\to }U$：
  表示用户和目标用户不喜欢相同的电影

• 加权元路径的缺点：
  普通元路径$UMU$只能反映两用户对相同电影有评分, 无法刻画其对电影的具体喜爱程度。另外, 元路径只能表示两对象间的简单关系。
  .
  而元结构/元图可以融合多条元路径, 方便地表达复杂语义。

---

• 元结构/元图：
  元路径是定义在元模式$T_G=(A,R)$上的线性序列, 而元结构/元图$M$可看作多条有公共节点的元路径组合而成的有向无环图。
  【即在结点之间多整几条路径】

例如：
对于元路径$UMDMU$和$UMAMU$，只能分别描述两用户对同一导演的电影打分或已打分电影中出现相同演员。
而利用元结构/原图可以描述该语义，如下图：

---

结构划分异质网络

• 多关系网
  该网络常存在于社交网络中，如Facebook和人人网。
  如下图：
  

该网络只包含用户这一类对象, 而用户间可以通过通话、浏览和聊天等不同类型的方式连接;

• 二分网络
  二分网络被广泛用于构建两种类型对象之间的交互，例如文档-单词。
  其主要特点为只含两种类型对象, 且是二分图结构, 即交互只存在于不同类型对象间, 同类对象间没有交互。
  如下图，文档-单词二分网络的网络模式：
  

• 星型网络
  星型网络的网络模式中存在中心节点, 其余非中心节点都与中心节点存在交互。
  如下图，文献信息网络是典型的星型模式异质网络，其包含不同对象(例如论文、会议、作者和术语)以及它们间的关系)
  

• 多中心网络
  星型模式的扩展, 一些网络针对不同节点子集拥有不同的中心节点, 其结构更为复杂。
  该网络广泛存在于生物信息学数据中，如下图：包含基因和化合物两个中心点。
  

• 属性网络
  属性网络进一步整合了节点和边的属性信息, 将拓扑结构和属性特征相结合, 从而更好地建模实际场景, 显著提升语义挖掘性能。
  如互联网金融中的套现用户检测，通过将支付宝的交互场景建模为异质网络, 来辨别是否有信用欺诈嫌疑的用户，如下图；
  

• 无模式/丰富模式网络
  许多实际交互系统中的节点和链接类型繁多且复杂, 从而不能被建模为简单网络模式的异质网络。

---

异质网络的分析和挖掘仍存在的挑战

• 某些真实数据过于复杂, 无法建模为有意义的异质网络。
• 即使可以将某些网络化数据建模为异质网络, 其分析挖掘仍然受限于目前的语义探索方法。

---

基于元路径的数据挖掘

相似性度量

相似性度研究方法可大致分为两类：

• 基于特征：
  利用对象特征来度量相似性。 如计算余弦相似性和欧几里德距离等；
• 基于链接:
  基于图中对象的链接结构来度量相似性， 如Personalized PageRank。

---

与同质网络上的相似性度量不同, 在异质网络上衡量对象间的结构相似性时, 需要考虑连接两对象的元路径种类。 因为不同元路径包含的语义不同, 基于不同语义可能产生不同的相似性结果。

例如在文献异质网络寻找作者小明的最相似的作者
通过APA路径找到的是小明的学生
通过APCPA路径找到的是知名的研究者
所以，异质网络的相似性度量往往受元路径约束

---

基于元路径的相似性度量方法缺陷：

1. 元路径仅适用于计算两个邻近(连接)实体的相似性。
2. 元路径的选择往往依赖于领域知识。
3. 元路径可以较有效地捕获源对象和目标对象间的单一关系, 但往往无法衡量实际问题中的复杂相似性

相关论文：

• 针对缺陷1：
  【Wang C, Song Y, Li H, et al. Distant meta-path similarities for text-based heterogeneous information networks. In: Proc. of the 2017 ACM on Conf. on Information and Knowledge Management. 2017. 1629-1638.】
  【Liu Z, Zheng VW, Zhao Z, et al. Semantic proximity search on heterogeneous graph by proximity embedding. Proc. of the AAAI Conf. on Artificial Intelligence, 2017, 31(1).】
• 针对缺陷2：
  【Wang C, Song Y, Li H, et al. Unsupervised meta-path selection for text similarity measure based on heterogeneous information networks. Data Mining and Knowledge Discovery, 2018, 32(6): 1735-1767.】
  【Yang C, Liu M, He F, et al. Similarity modeling on heterogeneous networks via automatic path discovery. In: Proc. of the Joint European Conf. on Machine Learning and Knowledge Discovery in Databases. Cham: Springer-Verlag, 2018. 37-54.】
• 针对缺陷3：
  【Fang Y, Lin W, Zheng VW, et al. Semantic proximity search on graphs with metagraph-based learning. In: Proc. of the 32nd IEEE Int’l Conf. on Data Engineering (ICDE). IEEE, 2016. 277-288.】
  【Liu Z, Zheng V, Zhao Z, et al. Distance-aware dag embedding for proximity search on heterogeneous graphs. Proc. of the AAAI Conf. on Artificial Intelligence, 2018, 32(1). 】
  【Liu Z, Zheng VW, Zhao Z, et al. Interactive paths embedding for semantic proximity search on heterogeneous graphs. In: Proc. of the 24th ACM SIGKDD Int’l Conf. on Knowledge Discovery & Data Mining. 2018. 1860-1869.】

---

推荐

以下图的电影推荐系统构建的异质网络为例，, 该网络不仅包含不同类型的对象(如用户和电影), 而且描述了对象间的各种关系, 如观影记录、社交关系和属性信息等。基于UMU路径寻找相似用户, 将倾向于推荐与目标用户具有相同观影记录的用户看过的电影, 这本质上对应于协同过滤模型。

其余元路径对应的推荐模型如下表：

• 随着网络表示学习的兴起, 越来越多的异质网络推荐方法利用异质网络表示学习技术学习用户和物品的特征表示用于推荐
• 伴随着图神经网络的兴起, 异质图神经网络在推荐任务上展现出优越性能。
• 许多方法利用异质网络融合除用户-物品交互外的信息辅助推荐, 典型代表是基于用户好友信息的社会化推荐

其他任务

异质网络研究的分类问题具有一些新的特点：

1. 异质网络中包含的对象是不同类型的, 这意味着标签是通过不同类型对象间的各种链接传播的；
2. 异质网络中的非目标类型对象也可能提供对目标类型对象分类有益的信息。【元路径作为对象间链接的元模式描述, 可以反映给定语义并刻画高阶结构。】

---

与同质网络相比：

1. 异质网络中共存的多类型对象使得传统的聚类方法无法直接应用, 因此许多工作将传统谱聚类方法扩展到包含不同类型对象的异质网络中。
2. 异质网络中包含的丰富语义使得聚类过程利用额外信息更加方便。

---

元路径选择

元路径选择困境：

1. 元路径的选择很大程度上依赖于领域知识。 对于不熟悉或很复杂的异质网络, 难以依靠领域知识选择合适的元路径集合。 并且, 随着元路径长度的增加, 路径数量呈指数增长, 使得路径搜索过程非常昂贵;
2. 简单拼接各种元路径的信息反而会引入噪音, 影响性能表现。而为各元路径学习合适的权重, 又常常需要监督信息。

---

解决困境的方法：

1. 自动生成元路径；
   自动生成元路径的算法往往基于网络模式搜寻可能连接实例对的元路径集合
2. 不利用元路径进行数据挖掘。
   一些工作不采用元路径, 而是以关系为出发点进行数据挖掘

---

异质网络的表示学习

早期处理网络化数据的工作大部分基于高维稀疏向量进行矩阵分析。然而, 现实中网络的稀疏性及其不断增长的规模, 对此类方法产生了严峻挑战。

更有效的方式是:
将网络节点映射到低维向量空间中, 用低维稠密向量来表示网络中的任意节点, 从而更加灵活地应用于不同数据挖掘任务中, 即信息网络的表示学习。

信息网络的表示学习论文：
Zhang Y, Ai Q, Chen X, et al. Joint representation learning for top-n recommendation with heterogeneous information sources. In: Proc. of the 2017 ACM on Conf. on Information and Knowledge Management. 2017. 1449-1458.

---

同质网络的表示学习方法并不能直接应用于异质网络, 主要存在两点挑战：

• 节点和边的异质性。
  不同类型的节点和边代表不同的语义, 因此, 异质网络的表示学习需要将不同类型的对象映射到不同的空间中。此外, 如何保存每个节点的异质邻居及如何处理异质的节点序列, 也是值得探究的问题;
• 异质网络中的丰富信息所带来的表示融合。
  异质网络从多个维度刻画节点的语义, 如何有效抽取和利用多维度信息并融合得到全面的节点表示, 也是巨大的挑战。

---

异质网络表示学习树状分类图：

---

浅层模型

部分浅层模型将其分解为较简单的网络, 分别对这些网络进行表示学习, 然后再将信息融合起来, 达到“分而治之”的效果。

先拆解再融合的两步框架作为同质网络向异质网络的过渡产物, 常运用于异质网络表示学习的早期工作中。然而从异质网络抽取同质子图的过程中, 会不可逆地损失异质邻居所带有的信息。

解决策略：

• 先出现了许多基于随机游走的方法, 以更好地刻画异质网络中的丰富语义。
• 从异质网络中不同的关系类型及其特点出发, 在规避元路径选择的同时学习节点嵌入表示。

---

深层模型

相对于浅层模型, 深度模型可以更好地捕捉非线性关系, 从而抽取节点所蕴含的复杂语义信息。

大致将深层模型分成4类：

• 基于自动编码器
  基于自动编码器的模型, 旨在利用神经网络构建编码器学习节点属性表示的同时保持网络结构特性。
• 基于生成对抗网络
  基于生成对抗网络方法的核心是, 利用生成器和鉴别器间的博弈得到鲁棒节点表示。
  在同质网络中, 基于对抗思想的方法往往只考虑结构信息；而异质网络中的生成对抗模型需要生成器和鉴别器考虑关系异质性以捕获语义信息。
• 基于强化学习
  基于深度强化学习的深层模型则主要针对元路径选择困境, 将下游任务性能作为奖励来优化整体框架, 从而在规避元路径选择的同时学得节点表示。
• 基于图神经网络
  其核心思想是消息传递机制, 即, 将邻域信息聚合并作为消息传递给邻居节点。
  图神经网络在同质图表示学习上所展现出的强劲性能, 促使越来越多的研究者探索异质图神经网络；与同质图神经网络类似, 异质图神经网络的关键在于如何设计合适的聚合函数, 以捕获邻域所包含的语义。

---

浅层模型和深层模型的比较：

• 浅层模型主要针对异质网络的结构, 而很少利用属性等额外信息。

• 浅层模型不易描述额外信息与结构信息的关系, 从而使得同时建模两者较为困难。而深层模型的学习能力更能够支持这种复杂的建模方式。

• 浅层模型缺乏非线性表示能力, 但高效且易于并行。

• 深层模型有更强的表示能力, 但也容易拟合噪音且时空复杂度较高

---

应用

• 推荐
  传统的推荐算法基于协同过滤, 仅考虑用户和物品的交互信息. 然而实际的推荐系统中, 用户与商品、店铺和朋友等存在大量的交互, 利用异质网络建模这些信息, 能够更精确地形成用户画像来提升推荐性能。
• 套现用户检测
  信用支付场景中, 套现用户具有极高的贷款违约率, 可能引起金融风险。常规方法是基于统计特征训练分类器, 很少充分利用用户间的交互信息, 而实际信用支付中的丰富交互关系从多方面反映了套现用户的特征。
• 恶意软件检测
• 恶意账户检测
• 异常事件发现
• 至疾病诊断
• 基因分析

---

未来发展方向

虽然异质网络已经应用于许多数据挖掘任务和实际场景, 但它仍然是一个年轻的、正在快速发展的研究方向。未来值得关注的方向如下：

• 面向多模态数据的异质网络构建与分析方法：
  异质网络可以通过融合丰富信息解决大数据的“多样性”挑战。现有工作主要致力于对关系数据库类的结构化数据建模, 而文本、图像和多媒体等模态数据是否也可以采用异质网络建模与分析?目前, 已有部分工作开始将异质网络用于文本挖掘中。
• 面向复杂网络数据的异质网络分析方法：
  实际应用中的异质网络具有动态变化、规模巨大、模式丰富等特点, 需要研究真实复杂网络数据的异质网络分析方法。
• 面向深度计算的异质网络表示学习：
  网络表示学习已成为当今的热点, 而图神经网络作为优美、有效的表示学习算法, 可以扩展至异质网络中。虽然已有部分工作提出了异质图神经网络, 但与同质网络相比, 仍有许多方面亟待研究。