GNN 相关资料记录；GCN 与 graph embedding 相关调研；社区发现算法相关；异构信息网络相关；

时间：2023-03-08 16:00:30

最近做了一些和gnn相关的工作，经常听到GCN 和 embedding 相关技术，感觉很是困惑，所以写下此博客，对相关知识进行索引和记录：

参考链接：

阅读总结：

  • 传统方法：手工特征-分类器-输出；
  • 深度学习：深度神经网络-输出；
  • 深度学习减少了手工提取特征或规则的步骤，从原始数据中自动学习特征这种学习方式称为端到端的学习（end-to-end）
  • 欧几里得空间，现实生活中不具备这种空间；
  • 发射，接收，变换；
  • 图卷积神经网络具有卷积神经网络的以下性质：
    • 局部参数共享，算子是适用于每个节点，处处共享；
    • 感受域正比于层数，最开始的时候，每个节点包含了直接邻居的信息，再计算第二层时，就能把邻居的邻居的信息包含进来；这样参与运算的信息就更多更充分。层数越多，感受域就更广，参与运算的信息就更多；
  • GCN 模型具备深度学习的三种性质：
    • 层级结构（特征一层一层抽取，一层比一层更抽象，更高级）；
    • 非线性变换（增加模型的表达能力）
    • 端到端的训练（不需要再去定义任何规则，只需要给图的节点一个标记，让模型自己学习，融合特征信息和结构信息。）
  • GCN 的四个特征：
    • GCN 是卷积神经网络再graph domain 上的自然推广；
    • 它能够同时对节点特征信息与结构信息进行端到端的学习，是目前对图数据学习任务的最佳选择；
    • 图卷积适用性较广，适用于任意拓扑结构的节点与图；
    • 在节点分类与边预测等任务上，在公开数据集上效果要远远优于其他方法；
  • 图数据的优势：
    • 给定一个节点，顺着其边的信息，能快速找到它的邻居节点；
    • 图的传播性强，邻居的邻居也和自己关系紧密；相互之间联系紧密的节点可以构成一个子图或者子团；
    • 一般在图中寻找子团的任务为社群检测（Community Detection）或者叫作高密子图挖掘（Dense Subgraph Mining）；
  • 图传播算法的一般范式：经验假设-无参量化-更新函数f；
  • pagerank算法；
  • HITS 引入 Authority 和 hub值来 进行指导更新，推导出节点权重，然后使用Authority 返回给用户。hub 作为中间指标，来指导authority值的精确计算；
  • 如果研究的数据有大量的标记集，可以让图卷积等基于learning 的方法去进行监督学习；
  • 社区检测（Community Detection）和 高密子图挖掘（Dense Subgraph Mining）；
  • 我们在进行社区检测的时候，节点都是同态的，类型都是一样的；
  • 模块度：同很多无监督的据类算法一样，衡量指标是一个至关重要的因素，很多时候，我们只需要定义好这个指标，然后选择启发式的更新方法去不断优化这个值；一个算法的骨架就形成了；
  • louvain 算法，LPA算法和Infomap算法；
  • louvain 算法就是不断优化模块度指标，进行最大化模块度评价函数；并且可以进行分层；当新的社区形成的时候，社区可以抽象为一个新的节点，然后在新的节点图的基础上进一步进行社区发现；从而更好得划分社区；
  • lpa 算法，lap 算法是一个极为简单的图传播算法，其经验假设是以节点为中心；统计每个节点邻居的社区，将出现最多次的社区赋给该节点，如果出现最多次的社区有多个则随机选择一个社区赋给该节点；由于该算法存在随机选择的情况，所以会出现震荡的现象；如果结合带权重的图，基于权重的排序，重新考虑基于权重排序的选择方法；则会有很好的效果；
  • infomap 结合信息熵的概念，重新考虑转移情况；并引出转移概率和到达概率的概念，引出一个进入一个社区的概率，社区内节点转移的概率，从某个社区中出来的概率，并结合信息熵公式，引出平均比特计算的概念；
  • 假设图被划分为m个社区，那么每走一步就可能是以下三种事件中的一种情况：进入某个社区，从某个社区中出来，在社区内部节点之间转移；
  • louvain 和 Infomap 算法都是基于一个合理的全局衡量指标对社区的划分不断进行启发式的优化。
  • 如果通过据聚类的角度去看待社区检测，那么一个基本的范式就是首先得到每个节点的特征表达，然后基于各种聚类算法进行聚类；从而得到社区的划分；
  • Dense Subgraph Mining 高密子图挖掘；
  • HIN (Heterogeneous information Network) 异构信息网络，为数据挖掘领域的前沿方向；
  • 异构图与同构图的定义：
    • Information network信息网络被定义为一个带有对象类型映射φ: V → A 和链接类型映射 ψ: E → R 的有向图 G=(V,E) 。每个对象 v∈V 属于某一个特定对象类型 φ（v）∈A，且每个链接 e∈E 属于关系类型集合R：ψ（e）∈R 中的特定关系类型。如果两个链接属于相同的关系类型，这两个链接共享相同的起始对象类型以及结束对象类型。
    • Heterogeneous / Homogeneous information network如果一个信息网络中，对象的类型总数 | A | > 1 或者链接的类型总数  | R | > 1，则称这样的网络为异构信息网络 Heterogeneous Information Network；否则为同构信息网络Homogeneous information network。
  • 异构图中的关键概念：
    • Network schema 网络模式；网络模式是定义在对象类型和关系类型上的一个有向图，是信息网络的描述模板。网络模式全面地描述了HIN中的结构模式；
    • Meta path 元路径；元路径是定义在网络模式上链接两类对象的一条路径；是整个HIN体系的核心，不同的元路径，刻画了对象之间不同的语义关系，这种语义关系的挖掘，是后续各类任务的基石；
  • 相似度计算时数据挖掘领域的首要任务之一，它有益于后续最邻近搜索，聚类，分类等相关任务；基于元路径的相似度计算有以下几个相关的方法：PathSim（对称元路径），HeteSim（非对称元路径）方法和AvgSim(针对非堆成元路径的两端对象的单向可达概率的均值)；
  • 针对异构图现有很多有效的算法，真正的挑战还是工程实现上所面临的数据体量的问题；
  • 基于元路径可以初步完成数据相似度关系的挖掘，然而随着更深层次的数据挖掘，更加细分的社群检测或者更个性化的推荐等任务都需要对语义相似性有着更加深刻的挖掘；而基于元结构MetaStructure的相似度定义的方法，就可以满足这样的场景的任务需求。
  • 基于元结构的有structcount 方法（结构计数）和SCSE-Structure Constrained Subgraph Expansion （分层随机游走计算概率）来通过元接结构来进行挖掘异构信息网络的信息；另外还有 Meta Graph 这种相似度定义方式来使用特定的数据结构进行加速计算；
  • 异构信息网络的一个核心应用为推荐系统发向；相较于传统的基于User-Item矩阵之上的方法，由于融合了更多的Side Information 以及以MetaPath为核心的计算体系，使得基于HIN的推荐系统不管是在效果上还是在可解释性以及多样性上，都能达到非常高的指标；
  • HIN的基本方法摘录：分析具体场景所要考虑的关系-融合所有关系构建HIN-基于元路径或元结构计算相似度-先特征融合再进行分类器学习或者先学习分类器再进行集成，其中的难点在于关系的梳理和相似度计算所依赖的大规模矩阵运算的能力；
  • 神经网络应该可以叫作可求导编程。神经网络，机器学习，深度学习就是利用微积分，梯度下降法，利用大量数据拟合出一个函数；这个函数可以用来做分类预测等功能；需要大量的计算，而本身gpu，tpu的出现等，就是为了加速运算的进行；

转载请注明本文链接地址：https://www.cnblogs.com/xuyaowen/p/graph-embedding-gnns.html

保持更新，资源来源自网络；更多内容请关注 cnblogs.com/xuyaowen,了解更多内容；如果对您有帮助，欢迎点击推荐按钮进行推荐！