文章插图
图3：图表示学习的分类和代表性方法 。2.1 基本定义许多现实世界的系统可以抽象地表示为不同级别的信息图，这些信息图侧重于组件以及这些组件之间的关联 。图表示学习方法旨在解决泛化图嵌入的问题 。在这一部分中，我们首先定义了与图表示学习相关的重要概念，包括不同类型的图，以及不同的图嵌入算法所依赖的图邻近度 。为了便于介绍和分析，首先介绍了符号的形式定义 。
假设\(G=(V,E)\)表示由一组顶点(也称为节点)\(V=\{v_1,v_2,\cdots,v_{|V|}\}\)和一组链接(也称为边)\(E=\{e_{i,j}\} \in \mathbb{R}^{V \times V}\)组成的图，其中\(|V|\)表示顶点数 。图\(G\)的邻接矩阵\(W\)保持与每条边相关联的非负权重 ， 如果\(v_i\)与\(v_j\)相连，那么\(w_{i,j}>0\)，反之\(w_{i,j}=0\) 。对于无向图，邻接矩阵是对称的，即\(w_{i,j}=w_{j,i},?i,j∈[v]\) 。我们也设计了节点类型映射函数\(φ:V→T\)和链接类型映射函数\(ψ:E→R\) 。\(T\)和\(R\)分别是预定义的节点类型和链接类型的集合 。
2.1.1 定义1：同构图和异构图给定一个信息图\(G\)，根据它的图拓扑结构和属性性质(有或没有节点属性) ， 可以将其分为不同类型的图 。如果节点类型\(|T|>1\)或链路类型为\(|R|>1\)，即\(|T|+|R|>2\)，则该图是异构图 。否则，它是同构图(\(|T|=1\)且\(|R|=1\)) 。同构图只有一种类型的节点和唯一的链接类型，而异构图包含多种类型的、相互连接的对象，例如"药物-目标-疾病"图 。同时，多重图是异构图的一种特殊类型 。多重图也称为多视图或多维图 ， 它只有一种类型的节点但有多种类型的边 。它可以看作是一类特殊类型的异构图，其中\(|T|=1\)但\(|R|>1\) 。
2.1.2 定义2：属性图信息图中的抽象顶点通常有其固有的性质 。一个属性图可以形式化地定义为\(G=(V,E,A)\)，其中\(A\)是一个属性表示矩阵 。对于每个节点\(v_i∈V\) ， 都有一个对应的特征向量\(a_i∈A\)隶属于它，其中\(A=\{a_i|v_i∈V\}\)是所有节点的节点属性特征集 。\(a_i\)是属于节点\(v_i\)的属性矩阵的第\(i\)行 。
2.1.3 定义3：元路径对于异构图，元路径\(\mathrm{P}=\mathrm{T}_1 \stackrel{R_1}{\rightarrow} \mathrm{T}_2 \stackrel{R_2}{\rightarrow} \mathrm{T}_3 \rightarrow \ldots \stackrel{R_1}{\rightarrow} \mathrm{T}_{l+1}\)定义在网络模式\(τ(G)=(T,R)\)上，它由节点类型\(T_1\)和节点类型\(T_{l+1}\)之间的复合关系\(R=R_1?R_2?R_3?···?R_l\)组成，其中\(l\)表示路径的长度(\(l≥1\)) ， \(?\)表示关系上的复合算子 。元路径可以有效地处理语义信息 ， 例如，一条路径 \(\text{药物}_a \stackrel{\text{靶标}}{\longrightarrow} \text{蛋白质}_b \stackrel{\text{相互作用}}{\longrightarrow} \text{疾病}_c\)在生物医学图中注明了一种疾病的治疗机制 。
2.1.4 定义4：一阶邻近度一阶邻近度反映了两个直接相邻节点之间的局部成对相似度 。如果两个顶点之间有连接，则这两个节点相似，否则不相似 。形式上，两个节点\(V_m\)和\(V_n\)的一阶邻近度用\(S_{m,n}\)来度量 。如果节点对\(v_m,v_n \notin E\) ， 则\(S_{m,n}>0\)；反之\(S_{m,n}=0\) 。
2.1.5 定义5：高阶邻近度高阶邻近度捕获了节点之间的\(k\)跳(\(k≥2\))邻域 。而二阶邻近度是高阶邻近度(\(k=2\))的特例，它由中间节点连接的邻居节点的数目决定 。通过从\(v_m\)到\(v_n\)的\(k\)跳转移概率来衡量两个节点\(v_m\)和\(v_n\)的高阶邻近度，即\(S_{m,n}=\hat{E}+\hat{E}^2+\hat{E}^3+\cdots+\hat{E}^k\)，其中\(\hat{E}\)表示第一跳的转移概率 。高阶邻近度捕捉到了全局邻近度 。
2.1.6 定义6：语义邻近通过两个节点的属性特征向量\(a_m\)和\(a_n\)的相似度来获得两个节点\(v_m\)和\(v_n\)的语义邻近度 。常用的相似度度量包括余弦相似度、皮尔逊相关系数、杰卡德相似度系数和高斯交互轮廓(GIP)核相似度
2.2 同构图嵌入图嵌入的第一类是同构图嵌入，也称为网络嵌入或非属性图嵌入 。它是最早发展起来的最简单的图表示学习方法 。在学习顶点的低维表示时，同构图嵌入方法通常旨在保持图的拓扑 。根据它们的技术细节，我们将这些同构图嵌入方法分为三大类：基于矩阵分解的方法、基于随机游动的方法和基于传统深度学习的方法 。
2.2.1 基于矩阵分解的方法矩阵分解旨在将矩阵分解为低维矩阵，同时保持原矩阵的潜在流形结构和拓扑性质 。有一些开创性的工作(例如IsoMap、局部线性嵌入、拉普拉斯特征映射和图因式分解)将节点之间的关系表示为图邻接矩阵、拉普拉斯矩阵或相似矩阵，然后采用矩阵因式分解来获得嵌入 。这些方法的不同之处在于它们基于不同的一阶矩阵来捕捉图的结构，并且它们通常获得节点的浅嵌入 。
