论文部分内容阅读
现实世界中,不同领域的复杂系统和结构,例如物流学中交通运输系统、社会科学中的社交系统、信息预测与推荐系统、认知科学中的知识图谱、生物学中的蛋白质交互结构、化学中的分子结构等都可以抽象为一种复杂网络(或图)结构化的数据形式进行表达。网络数据中的节点和连接节点之间的边分别代表了相应的实体和实体之间的联系。对网络数据的结构分析和特征表示研究具有非常高的学术价值和潜在的应用价值。其中,复杂网络中的一个最基本且最重要的模式结构是社区结构,这种模式结构在网络中表现为社区内部连接紧密而社区之间连接稀疏。对复杂网络进行有效地社区模块性分析能够有助于理解、分析复杂系统的行为特性。除了社区结构,鲁棒性是另一个研究复杂网络功能性的重要属性,网络的鲁棒性强弱能够反映复杂系统的功能模块在遭受随机失效、恶意攻击时的稳定性和完整性。因此,研究网络鲁棒性对于分析复杂系统的功能模块的安全性和对抗攻击能力有着重要的意义。而近年来,随着机器学习技术的发展,学习网络中的节点或者整个网络的特征表示已经成为了一项新兴的研究方向。网络表示学习(也称为网络嵌入)旨在将网络中的节点或者整个网络映射到一个低维、稠密的向量表示空间。这样学习到的特征表示可以送入到后续的机器学习模型中用于相应的任务,如节点分类、链路预测、图聚类、图分类、推荐系统等,具有非常重要的应用价值。本博士论文主要针对复杂网络中的社区模式结构检测、网络结构鲁棒性分析与优化、网络表示学习、图神经网络等领域面临的挑战和相关工作的不足展开研究,采用计算智能领域相关的方法(启发式进化算法和深度学习方法)来解决相关问题。具体而言,本博士论文所展开的研究工作概括如下:1)社区结构是复杂网络的自然和固有属性,可以反映其潜在的功能。本文针对目前的研究仅考虑增强网络微观的节点或者边的鲁棒性而忽略了对宏观社区结构分析的问题,模拟了一种多层恶意攻击模式,并提出了一种具有两层学习策略的Memetic算法。该算法能够在保持原始网络的节点度分布和社区结构的同时,提高网络的社区鲁棒性。本文提出的Memetic算法是一种混合的全局-局部启发式搜索方法,其采用遗传算法作为全局搜索,并采用两级学习策略作为局部搜索。基于网络的节点结构和社区结构的潜在特征设计了二级学习策略,旨在缓解多层恶意攻击。在合成的无标度网络以及真实世界网络上与几种最新算法相比,都证明了该算法的有效性和稳定性。2)多层网络是一种更好地模拟现实复杂系统的一种网络结构,共享社区是对多层网络的各层通用的一种社区模式结构。传统的社区检测方法在单层网络上虽然很有效,但是不能对多层网络共享社区进行很好地检测。针对该问题,本文将多层网络中的共享社区发现问题建模为一个多目标优化问题,并设计了一种增强的多进化算法来优化目标,实现多层网络中的共享社区检测。本文提出的多目标优化算法基于经典的NSGA-II框架进行了改进,采用基于字符串的个体编码方式,综合了遗传运算和局部搜索以进行个体改良。为了证明算法的有效性,本文在两个真实世界网络上的实验结果都证明了提出的多目标优化算法在多层网络中检测社区结构的能力和效率。3)网络嵌入(网络表示学习)已广泛应用于解决网络分析问题,但现有方法主要集中在具有单层同构或异构网络的网络上。但是,许多真实世界的复杂系统更适合用多层网络来建模,多层网络是一种具有多种关系类型的异构网络。如何捕获和利用丰富的多关系类型的交互信息成为了多层网络嵌入的重大挑战。面向这一挑战性问题,本文提出了一种快速且可扩展的多层网络嵌入模型,以有效地将多种类型的关系信息保存和学习到一个统一的嵌入空间中。本文研究了一种面向多层网络的启发式三维交互游走技术,该技术可以利用不同层之间的丰富的交互信息,并能有效地捕获分层结构中包含的重要信息。在两个节点级的下游分析应用上评估了我们提出的模型:节点分类和链接预测。在七个社会领域和生物领域多层网络数据集上的实验结果表明,该模型在性能和复杂度方面优于现有对比算法。4)神经网络近些年受到了越来越多的关注,传统的神经网络设计针对于规则的欧式数据(如视觉图像),但无法处理不规则的非欧式数据(如网络、图)。图神经网络是用于处理图数据结构的深度学习网络,而图卷积网络无疑是图神经网络的主要类别。图卷积网络通常是通过设计各种卷积运算和读出模块来利用图上的常见局部和全局结构模式。近些年,很多研究者开发了许多基于图卷积网络的方法用于图级表示学习和分类应用。但是,当前的图卷积网络方法无法有效地保留图的局部性—这限制了在图分类任务上的性能,因为图分类目标是根据其学习的图级表示来区分各种图结构。为了解决该问题,本文提出了一种基于局部保留稠密图卷积网络架构。具体而言,该模型构造了一个额外的局部节点特征重构损失,以帮助将初始节点特征保留到节点表示中。重构模块通过设计一种简单但有效的编解码器机制来实现。此外,为了灵活地利用来自不同局部的邻域信息,本文探索了一种稠密的连接模式,该模式将每个卷积层及其对网络的读出模块与所有前面的卷积层连接起来。在实验方面,本文对六个基准图数据集的分析和实验评估都证明了模型的有效性。5)为了丰富节点表示和图级表示中蕴含的信息,在4)中提出的模型基础上,本文提出了一种全局上下文感知的自注意图卷积神经网络架构。通过构造一种全局上下文感知的连接模式,使得每个节点表示形式都能融合全局的上下文信息,以形成一个全局上下文感知节点表示形式,从而丰富了节点表示蕴含的信息而且提高了模型整体的泛化能力。其次,为了有效地提取不同层次的全局信息,本文引入了一种自注意力机制来汇总模型的逐层图级表示,从而丰富了最终的图级表示。在实验方面,本文通过对六个基准数据集的分析和实验评估表明,与最新对比算法相比,该模型可显著提高图分类任务的准确性。