CASIA OpenIR  > 毕业生  > 博士学位论文
图神经网络表示学习方法研究
叶雪
2023-06
Pages122
Subtype博士
Abstract

在交通运输、社会计算、生物化学等领域,大量数据具有天然的图结构。比如,在城市交通网络中,地铁站点间存在客流关系;在社交网络中,用户之间存在内容转发和关注关系;在分子生物学中,原子间存在化学键连接关系,等等。近年来,得益于大数据时代和计算机算力的提升,深度学习方法得到快速发展和广泛应用。深度学习与图数据的结合催生出图神经网络这一新的研究方向。
其中,又以图卷积网络的研究最为丰富。尽管目前的图卷积网络方法已能处理非欧图数据的局部拓扑结构异构性,图数据的多样性和复杂性仍为图神经网络表示学习带来诸多挑战。一方面,在实际应用中,图数据往往关联着时间因素。时空图数据同时呈现时空关联性。如何利用节点特征及环境信息以自适应地建模时空关联,是一个具有挑战性的研究问题。另一方面,图的拓扑结构与图的功能密切相关,而现有方法大多受限于邻域节点间的信息传递框架,无法有效或显式地提取这部分信息。如何在无向图或有向图上提取拓扑结构信息以提升图神经网络表征能力,也是一个值得研究的问题。为此,本论文开展图神经网络表示学习方法研究。具体地,针对如何提升图神经网络表示学习能力这一目标,引入注意力机制、元学习方法和拓扑数据分析方法开展图神经网络模型构建、模型求解和模型验证等相关研究工作。本文的主要工作和创新点归纳如下:

1. 提出一种基于注意力机制和元学习的时空图预测方法。该方法的核心思想是将元学习集成到注意力机制当中,以捕捉数据中的时空异质性。整个框架采用一种编码器--解码器结构。其中,编码器将历史时空数据编码为一个中间表示,解码器则以自回归的方式预测未来时空图状态。具体地,所构建的框架包含时间自注意力、空间自注意力和时间编码解码注意力三种机制。时间自注意力和空间自注意力分别关注输入特征的时间相关性和空间相关性,时间编码解码注意力关注未来特征与历史特征在时间维度上的相关性。在该框架中,外部时空属性被作为元知识与三种注意力进行结合,以提升特征学习的时空异质性感知能力;同时,基于领域知识构建的多图结构被用于刻画不同类型的空间关系,增强对远距离空间关联的建模能力。在真实的地铁出行数据和高速公路交通图数据集的对比实验验证了所提方法的有效性。

2. 提出一种即插即用的拓扑神经网络层设计方法,并将其应用于面向无向图的图神经网络结构设计之中。该方法的核心思想是引入拓扑学中的“扩展持续同调(Extended Persistent Homology)”概念来提升图神经网络的特征学习能力。给定图结构和节点特征,首先学习图上多个“滤函数”,并基于每个“滤函数”构建一个从空集到一系列嵌套子图再到全图的图生长过程。然后,对每个生长过程,构建基于“扩展持续同调”的扩展持续图表。最后,通过对扩展持续图表进行参数化表征,实现图节点的特征聚合。所构建的拓扑神经网络层可插入到任意图神经网络的任意位置,并支持端到端学习。得益于“扩展持续同调”的合理应用,理论分析表明,所提方法比基于经典持续同调的方法具有更强的表达力,而后者的表达力严格优于基于信息传递的图神经网络。在公开的图分类数据集上的对比实验验证了所提方法的有效性。

3. 提出了一种基于“持续特征(Persistence Signature)”的有向图神经网络表示学习方法。其核心思想是基于连通性信息构造节点邻域的“持续特征”,并在此基础上实现图神经网络信息传递的参数化重加权。对于有向图上给定的“滤函数”,记录其对应的有向图结构生长过程中连通性、强连通性和环路的演变,并将其融合为一种多维度拓扑特征,称为“持续特征”。在构造“持续特征”的过程中,探索了一种有机结合“强连通性”和“连通性”信息的方式,称为“持续档案”。理论分析表明,“持续档案”比简单地组合“连通性”和“强连通性”的持续图表更具表达能力。所提方法从信息传播和聚合的角度出发,将现有的大多数图卷积方法统一在同一个框架之中。在此基础上,为该框架中节点间传播的信息基于节点邻域的“持续特征”作参数化的重加权。基于这一机制,本文将有向图的局部拓扑结构信息有机地融合到特征学习之中,从而提高现有图表征学习方法对有向图拓扑结构信息的利用效率。最后,在公开数据集上的对比实验结果验证了所提模型的有效性。

Other Abstract

In fields such as transportation, computational sociology, and biochemistry, a large amount of data can be naturally formatted with various forms of graph structures. For example, in urban transportation networks, there are passenger flow relationships between subway stations; in social networks, there are content forwarding and following relationships between users; in molecular biology, there are chemical bond connections between atoms, and so on. Thanks to the big data era and the rapid improvement of computing power, deep learning methods have been used widely. Technically, the combination of deep learning and graph data has given birth to a new research area called graph neural networks. 
Among them, the research on graph convolutional networks is the most abundant. Although current graph convolutional networks can deal with the heterogeneity of the local topological structure in non-Euclidean graph data, the diversity and complexity of it still bring many challenges to the graph neural network representation learning. On the one hand, in practical applications, graph data often has a temporal dimension. Spatial-temporal graph data presents both spatial and temporal correlations. How to use node features and environmental factors to adaptively model spatial-temporal correlations is a challenging research problem. On the other hand, the topological structure of a graph is closely related to its function, yet most of the existing methods are limited by the message-passing framework between neighborhood nodes, and cannot effectively or explicitly extract this part of the information. How to extract topological structure information on undirected or directed graphs to improve the representation ability of graph neural networks is also a problem worth studying. 
To this end, this dissertation conducts research on graph neural network representation learning methods. Specifically, to improve the power of graph neural network representation learning, the methodologies including attention mechanism, meta-learning and topological data analysis are introduced together to carry out the research works in this dissertation, which are practiced along the line of model construction, model solution, and model verification. The main contributions and innovations in this dissertation are summarized as follows:

1. A novel approach for spatial-temporal graph prediction with attention mechanism and meta-learning is presented. The core idea behind our method is to integrate meta-learning into the attention mechanism to capture the spatial-temporal heterogeneity in the data. The framework adopts an encoder-decoder structure, where the encoder encodes the historical spatial-temporal data into an intermediate representation, and the decoder predicts the future spatial-temporal graph states in an autoregressive manner. Specifically, the framework includes three attention mechanisms: temporal self-attention, spatial self-attention, and temporal encoder-decoder attention. The temporal self-attention and spatial self-attention focus on the temporal and spatial correlations of input features, respectively, while the temporal encoder-decoder attention focuses on the temporal correlations between future and historical features. In this framework, external spatial-temporal attributes are integrated with the three attention mechanisms as meta-knowledge to enhance the spatial-temporal heterogeneity awareness of the model. Moreover, a multi-graph structure based on domain knowledge is constructed to describe different types of spatial relationships, further improving the model's ability to model long-distance spatial correlations. The effectiveness of the proposed method is verified through comparative experiments on the real subway and highway traffic datasets.

2. A plug-in topological neural network layer for graph neural networks on undirected graphs is proposed. The core idea behind our method is to introduce the concept of ``Extended Persistent Homology'' in topology to enhance the feature learning ability of graph neural networks. Given the graph structure and node features, the method first learns multiple ``filter functions'' on the graph and for each of them constructs a graph growing process from the empty set to a series of nested subgraphs and then to the full graph. Then, for each growing process, “Extended Persistent Homology” in topology is employed to calculate the corresponding extended persistence diagrams, which record the ``birth'' and ``death'' of non-trivial topological features during the process. Finally, feature aggregation for graph nodes is achieved with the parameterized vectorization of these extended persistence diagrams. In practice, the topological neural network layer constructed in our work can be inserted into any position of any graph neural network, which supports end-to-end learning. Thanks to the reasonable application of ``Extended Persistent Homology'', the theoretical analysis also shows that the proposed method has stronger expressive power than those based on the classical persistent homology, and also renders strictly better expressive power than message passing-based graph neural networks. Comparative experiments on publicly available graph classification datasets validate the effectiveness of the proposed method.

3. An approach based on ``persistence signature'' is proposed to enhance the representation capability of directed graph neural networks. The core idea is to construct the ``persistence signature'' of the neighborhood of a node in terms of graph connectivity. Technically, ``persistence signature'' offers a parameterized way to reweight the information propagation in graph neural networks. For a given ``filter function'' on a directed graph, the evolution of connectivity, strong connectivity, and cycles during the corresponding directed graph structure growing process is recorded, which are further fused together into the multi-dimensional topological feature, namely, the so-called ``persistence signature''.  Furthermore, in the construction of the ``persistence signature'', a way of organic combination of ``strong connectivity'' and ``connectivity'' information, called the ``persistence profiles'', is explored. The ``persistence profiles'' are more expressive than the simple combination of the ``connectivity'' and ``strong connectivity'' persistence diagrams. Most existing graph convolution methods are unified in a single framework from the perspective of information propagation and aggregation. In this way, information propagation between nodes can be reweighted with the ``persistence signature'' in the node neighborhoods. As a result, most existing graph convolutional operations can be performed in a unified way. Based on this mechanism, this dissertation organically integrates local topological structure information of directed graphs into feature learning, thereby improving the ability of existing graph representation learning methods in utilizing directed graph topology. Finally, comparative experiments have been conducted on publicly available datasets to validate the effectiveness of the proposed model.

Keyword深度学习 图神经网络 注意力机制 元学习 拓扑数据分析
Indexed By其他
Language中文
Sub direction classification人工智能基础理论
planning direction of the national heavy laboratory人工智能基础前沿理论
Paper associated data
Document Type学位论文
Identifierhttp://ir.ia.ac.cn/handle/173211/52030
Collection毕业生_博士学位论文
Recommended Citation
GB/T 7714
叶雪. 图神经网络表示学习方法研究[D],2023.
Files in This Item:
File Name/Size DocType Version Access License
叶雪的博士学位论文.pdf(25235KB)学位论文 限制开放CC BY-NC-SA
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[叶雪]'s Articles
Baidu academic
Similar articles in Baidu academic
[叶雪]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[叶雪]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.