近年来, 以Internet为代表的信息技术的发展, 已使我们处于由无处不在的网络构成的世界中.此外, 网络结构数据分布在各种相关领域数据中, 包括分子结构网络、生物蛋白质交互网络、推荐系统、社交网络、引文网络等等.这些数据结构都可以通过网络来描述实体及实体之间的交互关系, 网络结构数据是我们生产、生活中常见的一种数据形式.其中, 复杂网络是一类具有幂率度分布、强聚类、小世界特性的网络.对复杂网络的分析有利于网络数据结构的潜在信息挖掘, 这将促进一系列应用, 如节点分类、社区发现、链路预测等[1-6].例如, 可以通过“推特、微博”用户关注所形成的社交网络进行“朋友推荐”, 通过生物蛋白质代谢网络发现潜在的蛋白质功能. 复杂网络的分析具有极强的现实意义, 但直接对大规模、稀疏的邻接矩阵进行分析需要较高的时间复杂度和空间复杂度, 难以进行并行计算[2].另一方面, 在机器学习浪潮下, 复杂网络学科与机器学习的结合成为当下热点研究问题, 很多机器学习算法试图将网络结构数据引入作为特征输入.该输入数据一般可以被表示为包含特征信息的向量形式, 传统方法使用网络的统计参数、核函数或通过精心设计的特征来描述邻居结构信息, 但这些设计代价昂贵且不能自适应学习过程[6]. 为了解决这些困难和挑战, 大量研究使用表征学习来编码网络结构信息.网络表征学习通过假设网络节点位于低维空间, 在该空间中学习网络节点的低维向量表示, 低维向量将进一步用于处理后续任务.表征学习的目标是通过优化网络节点的向量表示来实现保留网络结构信息的降维表达, 向量空间中节点的位置和节点间距离可以表征网络的高阶拓扑信息.如图 1所示, GCN[7]是一种用于网络结构数据的神经网络架构, 随机初始化的3层GCN也可以生成网络中节点的邻近特征表征. Fig. 1 Example of embeddings obtained from an untrained 3-layer GCN model with random weights applied to the Zachary's karate club network[7] 图 1 使用未训练的3层GCN嵌入Zachary’s Karate Club网络示例[7] 大部分的网络表征学习针对的是图数据, 通过图计算形式实现降维表达.而复杂网络的表征学习针对具有幂率度分布、强聚类、小世界特性的网络, 其研究有利于降低网络数据维度, 使网络数据可以与机器学习相结合, 更好地分析网络节点间联系, 为各种后续实际应用提供解决方案.近年来, 在网络表征学习领域涌现出大量的研究成果, 其中一些研究表明, 双曲空间可以很好地描述具有近似树状层次结构的复杂网络.双曲空间具有负常数曲率, 是树状图的连续近似空间, 无限树在双曲空间中也有近乎等距的嵌入[8].复杂网络的双曲几何模型嵌入理论将复杂网络几何化, 同时又不损失复杂网络中的无标度、小世界等特性, 是一种可以解释复杂网络拓扑特征和生长机制的新型模型.为了更好地分析与应用该类模型, 本文围绕复杂网络的双曲空间表征学习方法展开系统性介绍和总结, 以供后续研究参考. 本文第1节对网络表征学习及其分类进行总结, 将网络表征学习分为矩阵分解、随机游走、深度自编码机和图神经网络的方法.第2节在介绍双曲空间的基础上, 对已有的复杂网络双曲空间生成模型和嵌入方法进行总结.第3节从复杂网络双曲空间表征学习的应用出发, 结合双曲空间特征, 概括了其主要应用场景.第4节给出不同的双曲空间表征学习方法性能评估结果.第5节总结全文, 指出复杂网络的双曲空间表征学习的特征优势, 并对未来研究方向做出展望. 1 网络表征学习 1.1 网络表征学习定义 网络表征学习是一个降维表达的过程, 将高维的网络结构数据转换为低维的节点向量表示, 向量可作为节点特征用于后续网络应用.表 1给出了本文所用符号的含义, 网络表征学习的目标是:对网络G中每个节点vi, 学习一个实值向量表示$ {{z}_{i}}\in {{\mathbb{R}}^{d}}\left( d\ll \left| V \right| \right) $.部分方法会用到节点属性或连边属性, 如m维节点属性可通过$ X\in {{\mathbb{R}}^{\left| V \right|\times m}} $的实值矩阵来表示.通过网络表征学习形成保留网络结构信息的低维实值向量, 可以用于重构出原网络、有效支撑网络推断和提高后续应用算法执行效率. Table 1 Notations used in this paper 表 1 本文所用符号 1.2 网络表征学习分类及特征 网络表征学习方法众多, 按照不同的分类标准, 可得到不同的结果.本文根据不同方法的技术特点, 把网络表征学习分为基于矩阵分解、随机游走、深度自编码机、图神经网络的方法:矩阵分解的方法将网络信息使用矩阵表示, 然后通过分解该矩阵获取节点向量表示[9-11]; 随机游走方法将网络信息通过采样一系列随机游走的路径表示, 然后将深度学习方法应用到采样路径中进行图嵌入, 以保持路径所携带的图属性[1, 12]; 深度自编码机将网络信息编码到表征空间, 然后译码重构, 使得重构误差最小化; 图神经网络通过在图上定义近似卷积等操作, 将神经网络应用于图信息处理.表 2对每种方法的特征及适用性进行描述[13-28]. Table 2 Comparison of network representation learning methods 表 2 网络表征学习方法比较 基于矩阵分解、随机游走、深度自编码机和图神经网络的网络表征学习方法的相关研究层出不穷, 它们一般都是通过某种策略将实体对象嵌入到低维欧氏向量空间中, 该策略的目标是捕获语义信息, 如节点近似度或节点间最短路径等信息.但是, 欧几里德对称模型不能很好地反映复杂的数据模式, 比如分类数据中潜在的层次结构[29].为了解决这一问题, 非欧几里德流形表示学习成为新的发展趋势.实际上, 许多复杂网络都呈现出幂率度分布和潜在的树状结构, 该结构的存在通常可以追溯到层次结构.为了利用这种结构特性来学习更有效的表示, 许多研究建议不在欧几里德空间中计算嵌入, 而是在双曲空间中计算嵌入[30-32], 即曲率为负常数的空间. 关于网络表征学习, 已有大量综述文献[1-6, 9, 11, 12], 但描述的方法大多以网络特征提取和表示为目标, 将网络嵌入到低维欧氏空间中.本文主要聚焦于双曲空间中的复杂网络表征学习, 亦属于网络表征学习中的一类, 但该类方法来源于对复杂网络形成过程和规律的研究, 所表征的节点向量具有独特的物理含义.该类方法认为:双曲空间是复杂网络潜在的几何度量空间, 将双曲空间几何性质与复杂网络的特征相结合, 形成复杂网络的生成模型, 而相应的表征学习则是对原始坐标的逆向推断.下一节将介绍双曲空间基本性质、双曲空间适合表达近似树状结构的复杂网络的原因、从双曲空间到实际网络的生成过程以及从实际网络到双曲空间的嵌入方法. 2 复杂网络的双曲空间表征学习 2.1 双曲空间概述 非欧几何的诞生, 源自于对欧几里德第五公设的讨论与研究.双曲几何是非欧几何的一种特例, 在双曲几何中, 前4条公设保留, 第5公设修改为“过已知直线外一点至少可以作两条直线与已知直线平行”.双曲空间由于具有负常数的曲率, 无法等度量地嵌入到欧氏空间中, 难以直观表达.有研究学者为此建立了很多等价模型, 这里我们介绍常用的3种模型:双曲面模型、克莱因模型和庞加莱球模型.图 2(b)和图 2(c)所示为克莱因模型和庞加莱圆盘模型(二维庞加莱球模型)中的过给定点的平行线. Fig. 2 Examples of hyperbolic geometric models 图 2 双曲几何模型示例 2.1.1 双曲空间表达模型 (1) 双曲面模型 双曲面模型将n维双曲空间视为n+1维闵可夫斯基空间中的伪球面, n+1维闵可夫斯基空间是内积为公式(1)的实值空间: ${\langle \boldsymbol{u}, \boldsymbol{v}\rangle _{n:1}} = \sum\nolimits_{i = 1}^n {{u_i}{v_i}} - {u_{n + 1}}{v_{n + 1}}$ (1) n维双曲面模型中的点可由n+1维闵可夫斯基空间中的点表示, 如公式(2)所示: $ {{\mathbb{L}}^{n}}=\left\{ \boldsymbol{u}\in {{\mathbb{R}}^{n:1}}{{\left\langle \boldsymbol{u}, \boldsymbol{u} \right\rangle }_{n:1}}=-1, {{x}_{n+1}}>0 \right\} $ (2) 如图 2(a)所示, 双曲面模型中的每一条测地线都是$ {{\mathbb{L}}^{n}} $和过原点的平面的交线, 两点间的测地距离如公式(3)所示: ${d_{{\mathbb{L}^n}}}(\boldsymbol{u}, \boldsymbol{v}) = \arccos {\rm{h}}( - {\langle {\boldsymbol{u}, \boldsymbol{v}}\rangle _{n:1}}),{\boldsymbol{u}, \boldsymbol{v}} \in {\mathbb{L}^n}$ (3) (2) 克莱因模型 如图 2(a)所示, 将$ {{\mathbb{L}}^{n}} $中的每个点通过原点发散出的射线映射到xn+1=1的超平面上, 可得克莱因模型: $ {{\mathbb{K}}^{n}}=\left\{ \boldsymbol{x}\in {{\mathbb{R}}^{n}}\left| \left\| \boldsymbol{x} \right\|<1 \right. \right\} $ (4) 即:该过原点的平面与$ {{\mathbb{L}}^{n}} $相交形成双曲面模型中的测地线, 与xn+1=1的超平面相交形成克莱因模型中的测地线.克莱因模型和双曲面模型互为映射: ${\rho _{\mathbb{L} \to \mathbb{K}}}{(\boldsymbol{x})_i} = \frac{{{x_i}}}{{{x_{n + 1}}}}, {\rho _{\mathbb{K} \to \mathbb{L}}}(\boldsymbol{x}) = \frac{1}{{\sqrt {1 -