【作者】 杨天宇；

【导师】 车翔玖；

【作者基本信息】 吉林大学 ， 计算机科学与技术， 2025， 硕士

【摘要】 现实世界中的图结构数据复杂多样,蕴含大量可挖掘信息,包括化合物分子、引文网络、蛋白质分子、交通网络等。图数据挖掘的核心目标是揭示图拓扑结构、节点特征以及边特征的关联性,已经在节点分类、链接预测等任务中取得了巨大成功。随着深度学习研究的普及,许多图神经网络(Graph Neural Network,GNN)展现出卓越的表达能力,推进了图表示学习任务。然而基于图神经网络的方法大多假设节点特征和图结构信息是已知的,并且默认节点特征表示与标签相互独立。在现实世界应用场景中,输入数据和预测结果之间往往存在复杂的依赖关系,图神经网络中的独立性假设可能会限制模型的表达能力。相比之下,概率图模型(Probabilistic Graph Model,PGM)在数学和统计上具有可解释性,能够表达随机变量之间的条件依赖结构。这使得一些研究人员将概率图模型与图神经网络进行结合,提高图神经网络的结构化学习预测能力,增强复杂图神经网络的可解释性。基于以上背景,本文主要工作如下:(1)现有图神经网络大多关注加强图中节点表示和局部结构,而对相似关系特征提取不充分。针对该问题,本文提出了一种基于分层条件随机场的图神经网络节点分类方法。为了提升模型对全局信息的捕捉能力,该框架采用多层粗化结构,将结构相似的节点聚合为超节点,每个超节点代表原始图的一个局部结构,从而更有效地获取全图的结构信息。尽管已有许多方法能够较好地表示原始图数据并整合信息,但它们往往无法保证图数据中的隐藏特征仍能保持相似关系。为此,本文提出了一种改进的条件随机场,对传播过程中的节点表示进行相似性关系建模,以此规范隐藏层特征。最后通过细化操作恢复原始图的拓扑结构,并加入跳跃连接以确保层级模型的稳定性。本文提出的模型在Cora、Citeseer、Pubm ed三个公开数据集上进行半监督节点分类实验,准确率分别达到84.6%、73.3%、82.9%,优于多数对比方法,例如相较于GAT基准模型,在三个数据集上的准确率分别提升1.6%、0.8%和3.9%。这说明层级粗化框架能够很好提取图结构特征,并且条件随机场约束能够保持节点间的相似关系,验证了本文方法的有效性。(2)本文进一步研究了深度图神经网络在模型层数增加时出现的性能退化问题,从理论角度深入分析了过平滑现象的原因,并提出了一种基于概率图模型的统一解释框架。该框架从马尔可夫随机场的变分推断出发,推导出图神经网络特征传播的迭代解,并结合高阶泰勒公式展开将多种现有深度图神经网络模型纳入统一的理论范式。基于该理论范式,本文设计了一种耦合深度图卷积网络,通过改进信息传播机制有效缓解了过平滑现象,使模型在较深层次仍能保持较强的分类性能。此外,该模型还提出了一种混合邻接矩阵,结合空间方法和谱方法来增强模型提取节点特征的能力。本文进行了广泛实验。半监督节点分类实验结果表明,本文模型在Cora、Citeseer、Pubmed上的准确率分别达到86.2%、74.1%、81.9%,相较于GCN基准模型,三个数据集上的准确率分别提升4.7%、3.8%和2.9%。此外,在全监督节点分类实验中,模型在Cornell、Texas、Wisconsin网页数据集上的准确率达到81.09%、78.41%、82.37%,高于其他基线方法,在引文网络数据集中也达到了较优结果。大量实验结果表明,本文提出的统一解释范式具有合理性和正确性,同时混合邻接矩阵能够更有效的提取节点特征,验证了其有效性。更多还原

【Abstract】 Graph-structured data in the real world is diverse and complex,containing a wealth of valuable information that can be explored,including molecular compounds,citation networks,protein molecules,and transportation networks.The core objective of graph data mining is to uncover the relationships between graph topology,node features,and edge features,which has achieved significant success in tasks like node classification and link prediction.With the widespread adoption of deep learning research,many graph neural networks(GNNs)have demonstrated exceptional expressive power,advancing graph representation learning tasks.However,most GNN-based methods assume that node features and graph structure information are known and that node feature representations are independent of labels.In real-world applications,there are often complex dependencies between input data and prediction outcomes,and the independence assumptions in GNNs may limit their expressive capabilities.In contrast,probabilistic graphical models(PGMs)offer mathematical and statistical interpretability,enabling the representation of conditional dependency structures among random variables.This has led some researchers to integrate PGMs with GNNs to enhance the structured learning and predictive capabilities of GNNs,as well as to improve the interpretability of complex GNNs.Based on the above background,the main contributions of this paper are as follows:(1)Existing GNNs primarily focus on enhancing node representations and local structures within graphs,but do not sufficiently extract nodes similar relationship features.To address this issue,this paper proposes a hierarchical conditional random field(CRF)-based GNN method for node classification.To improve the model’s ability to capture global information,the framework employs a multi-layer coarsening structure,aggregating structurally similar nodes into hyper-nodes,where each hyper-node represents a local structure of the original graph,thereby more effectively capturing the global structural information.Although many existing methods can effectively represent and integrate information from the original graph data,they often fail to ensure that the hidden features in the graph data maintain similarity relationships.To this end,this paper proposes an improved CRF to model similarity relationships during the propagation of node representations,thereby regularizing hidden layer features.Finally,the original graph topology is restored through a refinement operation,and skip connections are added to ensure the stability of the hierarchical model.The proposed model achieves semi-supervised node classification accuracies of 84.6%,73.3%,and 82.9%on the Cora,Citeseer,and Pubmed datasets,respectively,significantly outperforming most comparative methods.For instance,compared to the GAT model,our approach achieves relative improvements of 1.6%,0.8%and3.9%.This demonstrates that the hierarchical coarsening framework effectively extracts graph structural features,and the CRF constraints maintain similarity relationships between nodes,validating the effectiveness of the proposed design.(2)This paper further investigates the performance degradation issue in deep GNNs as the number of layers increases,providing a theoretical analysis of the over-smoothing phenomenon and proposing a unified PGM-based explanation framework.This framework derives an iterative solution for feature propagation in GNNs from the perspective of variational inference in Markov random fields,and incorporates high-order Taylor expansions to unify various existing deep GNN models under a single theoretical paradigm.Based on this paradigm,the paper designs a coupled deep graph convolutional network that effectively mitigates over-smoothing by improving the information propagation mechanism,allowing the model to maintain strong classification performance even at deeper layers.Additionally,the model introduces a hybrid adjacency matrix that combines spatial and spectral methods to enhance the model’s ability to extract node features.Extensive experiments were conducted,and the results show that the proposed model achieves accuracies of 86.2%,74.1%,and 81.9%on the Cora,Citeseer,and Pubmed datasets,with relative improvements of 4.7%,3.8%and 2.9%over the GCN baseline,in semi-supervised node classification tasks.Furthermore,in fully supervised node classification experiments,the model achieves accuracies of 81.09%,78.41%,and 82.37%on the Cornell,Texas,and Wisconsin web datasets,significantly outperforming other baseline methods and achieving state-of-the-art or near-optimal results on citation network datasets.The experimental results demonstrate the rationality and correctness of the proposed unified explanation framework,while the hybrid adjacency matrix effectively enhances node feature extraction,validating its effectiveness.更多还原