模式识别与数据挖掘 课件 第12章-结构模式识别

第十二章

结构模式识别主讲人：某某某PatternRecognitionandDataMining模式识别与数据挖掘目录Contents结构模式识别的起源与发展历程结构模式识别相关定义概述DefinitionsinStructuralPatternRecognition图结构嵌入GraphEmbedding图核函数GraphKernels01020304图神经网络05OriginandDevelopmentofStructuralPatternRecognitionGraphNeuralNetworks结构模式识别的起源与发展历程01OriginandDevelopmentofStructuralPatternRecognition统计模式识别结构模式识别的起源现实生活中存在的数据，不总是整齐的向量数据5251.5870.982932.1480.988965.76130.514752.7150.49…………基于特征向量表示，适用于规则数据结构模式识别基于结构化描述，适用于关系数据？传统算法无法直接处理图数据节点数不固定结构不规则社交网络分子结构交通网络结构模式识别的发展历程20世纪80年代2000年左右2015年左右相似度≈0.85√图结构嵌入（GraphEmbedding）图核函数（GraphKernels）图神经网络（GraphNeuralNetworks）核心思想：将图数据由高维结构空间映射至低维向量空间目标：让传统算法能处理图数据核心思想：无需显式映射，直接在高维希尔伯特空间计算图的相似度目标：避免嵌入过程中的信息损失核心思想：将深度学习推广至图数据，让模型自动学习特征目标：构建端到端的统一学习框架结构模式识别相关定义概述02DefinitionsinStructuralPatternRecognition图结构数据形式化定义图G(V,E)V是节点集合（实体：如人、原子、城市）E是边集合（关系：如朋友、化学键、航线）

常见分类按节点分类：属性图（带属性的节点）非属性图（不带属性的节点）按边分类：有向图（边有方向）无向图（边无方向）按边的特征：带权图（边上有权重）无权图（边无权重）

图上的学习任务根据节点的属性、边的信息以及已知的节点标签，预测未知标签节点的类别例如：遗传交互网络中发现功能模块、在金融交易网络中发现欺诈用户组有毒无毒节点分类社团检测例如：社交网络中，通过用户的社交关系和属性信息来预测用户的兴趣或行为发现图中紧密连接的节点群组，是对图结构的无监督聚类图分类预测整个图的属性，目标是使用一组带标签的训练数据来学习从图结构数据到标签的映射例如：利用分子图结构来预测分子的抗癌活性、溶解性或毒性图结构嵌入03GraphEmbedding图结构嵌入图结构数据向量空间

映射函数

核心挑战传统模式识别算法主要针对欧氏空间中维度固定的规则向量数据设计图结构数据的节点数量不固定，节点间缺乏直接的对应关系传统模式识别算法无法直接用于图数据图嵌入将高维稀疏图数据转化为低维稠密向量捕获图的拓扑结构和节点关系经典算法基于原型选择的不相似度嵌入算法基于代数图理论提出的多项式图嵌入算法基于深层次信息的熵嵌入算法基于不相似度的图嵌入方法

计算图嵌入示例基于深层次信息的熵嵌入算法核心挑战原型图的选择与编辑距离的计算需要复杂的优化过程，难以处理大型图或图集合核心步骤计算中心节点：选择具有最小最短路径长度方差的顶点得到扩展子图：由中心节点出发，扩展一定层级基于深层次信息的熵嵌入将图分解为不同层次的子图结构，并计算这些子结构的熵信息

图核函数04GraphKernels图核函数核心挑战图嵌入方法将图结构由高维结构空间映射到低维空间时，可能会损失关键结构信息，导致线性不可分问题图核方法在高维空间中直接分析与处理图结构数据的解决方案能直接体现图结构数据在高维希尔伯特空间中的结构信息

相似度分数0.87经典核方法

图核函数R卷积理论（R-convolutionFramework，Haussler，1999）将图分解为子结构，通过计算两个图之间共享的同构子结构来定义图核函数①将图分解为子结构②判断子结构是否同构

③计算同构子结构对数共享的子结构越多，图就越相似图核函数

基于游走（walk）的图核函数基于路径（path）的图核函数基于子树（subtree）或子图（subgraph）的图核函数Weisfeiler-Lehman图核（WL图核）WL图核基于不相似度的图嵌入(dissimilaritygraphembedding)在迭代过程中不断地为每个根节点聚合其邻近节点的标签信息,进而为该根节点生成更高层次的抽象表示核心步骤多集标签确定：为图中的每一个节点确定一个多集标签。该多集由节点的邻域中所有节点的标签组成对多集进行排序:将多集中的元素按升序排序，并将它们连接成一个字符串。在字符串前加上节点本身的标签作为前缀标签压缩:使用哈希函数将每个字符串映射到一个压缩标签得到新标签:为图中的所有节点设置新的标签经过多轮迭代后，通过计算任意两个图结构间共享的相同节点标签对数，进而得到WL图核图神经网络04GraphNeuralNetworks图神经网络核心挑战：克服图核方法的局限性计算开销大：图核方法需要计算和存储一个N×N的核矩阵，难以扩展到大规模数据集非端到端学习：特征提取（核矩阵的计算）与下游任务（SVM分类）是分离的，无法协同优化解决方案：图神经网络核心思想：将深度学习（特别是卷积神经网络CNN）从欧式空间数据推广到非欧式的图结构数据CNN：在规则的像素网格上，用一个卷积核来聚合邻域像素信息，提取局部特征GNN：在不规则的图数据上，每个节点通过聚合其邻居节点的信息来更新自己的特征表示谱域图卷积神经网络空域图卷积神经网络谱域图卷积神经网络核心思路利用图信号处理理论，将图信号变换到谱域，在谱域中进行卷积操作，再逆变换到原始空间

2.计算简化（切比雪夫多项式网络）方法：使用切比雪夫多项式来近似谱域中的滤波器，避免了直接进行特征分解

3.再次简化（图卷积网络，GCN）方法：进一步简化，将切比雪夫多项式限制在一阶，并使用重归一化技巧意义：奠定了现代图卷积网络的基础，高效且易于实现

谱域方法通过一系列数学简化，从理论走向实用，其演化逐渐接近直接在空域上操作的空域方法空域图卷积神经网络基于空间策略的图卷积神经网络（DGCNN）排序池化(sortpooling)层，将无序的节点特征转换为固定大小的有序表示，使得传统的CNN能够应用于图分类任务利用图卷积层提取节点的局部子结构特征利用SortPooling层,根据局部子结构特征对节点进行排序,将无序的节点特征转换为固定大小的有序表示应用传统的1D卷积和全连接层进行图分类空域图卷积神经网络低回溯空间对齐图卷积神经网络（BASGNN）将任意大小的图转换为固定大小的无回溯对齐网格结构,并在此网格结构上定义新的空域图卷积操作核心步骤低回溯网格结构构造/输入层：通过该层将每个任意大小的图转换为固定大小的低回溯对齐网格结构低回溯空间图卷积层：该层由两个并行的堆叠图卷积网络组成，In-BASGNN网络和Out-BASGNN网络，分别关注和聚合入邻接顶点和出邻接顶点的特征传统一维CNN层：接收低回溯空间图卷积层的输出，并在这些对齐的网格结构上执行传统的一维卷积操作

减少了信息丢失，并在理论上弥合了传统CNN与空域GNN之间的差距小结与讨论图嵌入（GraphEmbedding）图核函数（GraphKernels）图神经网络（GraphNeuralNetworks）核心思想将图映射为低维向量直接在高维空间度量图相似度直接在图结构上进行端到端学习信息损失存在信息损失理论上无损失，但依赖子结构选择可学习，表达能力强计算范式两阶段两阶段端到端特征工程手动设计嵌入方法手动设计子结构自动学习特征适用场景中小型图，结合传统机器学习算法中小型图，适用于结构信息比较关键的图各类规模的图小结与讨论本章探讨了结构模式识别的核心——图数据分析我们沿着历史的足迹，见证了解决这一问题的三次重要尝试：图嵌入(GraphEmbedding)：一座连接图与传统机器学习的桥梁，但代价是信息损失图核函数(GraphKernels)：一种在结构空间直接比较图的精巧工具，但扩展性差，依赖手动设计图神经网络(GraphNeural