在我们今天的生活中，图的例子包括社交网络，例如Twitter、Mastodon，以及任何链接论文和作者、分子、知识图谱的引文网络，例如UML图表、带有超链接的百科全书和网站、用语法树表示的句子、以及任何3D网格等等，可以说图表无处不在。最近，HuggingFaceResearchScientistClémentineFourrier在文章《Introduction to Graph Machine Learning》中介绍了当今无处不在的图机器学习。什么是图形？为什么要使用图表？如何最好地表示图形？人们如何在图表上学习？ClémentineFourrier指出，图是对通过关系链接的项目的描述，其中，从前神经方法到图神经网络仍然是常用的图学习方法。此外，一些研究人员最近开始考虑将Transformers应用于图。Transformer具有良好的可扩展性，可以缓解GNN的一些局限性。前景十分可观。1图是对通过关系链接的项目的描述。本质上，图形是对通过关系链接的项目的描述。图（或网络）的项目称为节点（或顶点），并由边（或链接）连接。例如，在社交网络中，节点是用户，边是用户之间的联系；在分子中，节点是原子，边缘是它们的分子键。具有类型化节点或类型化边的图称为异构图。例如，引文网络中的项目可以是论文或作者，具有类型节点，而XML图中的关系具有类型边；它不能是拓扑结构，需要额外的信息。图也可以是有向的（例如追随者网络，A跟随B并不意味着B跟随A）或无向的（例如分子、原子之间的关系是双向的）。一条边可以连接不同的节点，也可以连接一个节点与自身（self-edge），但并不是所有的节点都需要连接起来才可见，而且使用的数据首先要考虑它的最佳表示，包括同构/异构，有向/无向等..在图层面，主要任务包括：Graphgeneration，用于药物发现，生成新的合理分子图Evolution，即给定一个图，预测它会如何随时间演化，在物理学中可以用来预测演化图一个系统的层次预测、分类或回归任务来自图，例如预测分子的毒性节点层通常是节点属性的预测，例如Alphafold使用节点属性预测来预测给定分子整体图的原子的3D坐标，因此预测分子如何在3D空间中折叠是一个困难的生化问题。边缘预测包括边缘属性预测和缺失边缘预测。给定一对药物的不良副作用，边缘属性预测有助于预测药物的副作用；缺失边预测在推荐系统中用于预测图中的两个节点是否相关。在子图级别，可以进行社区检测或子图属性预测。社交网络使用社区检测来确定人们的联系方式。子图属性预测多用于出行系统，如谷歌地图，可用于预测预计到达时间。在预测特定图的演变时，转换设置工作中的所有内容，包括训练、验证和测试，都可以在同一个图上完成。但是从单个图创建训练、评估或测试数据集并不是微不足道的，很多工作是使用不同的图（单独的训练/评估/测试拆分）完成的，这称为归纳设置。有两种常见的方式来表示图形处理和操作，或者作为其所有边的集合（可能由其所有节点的集合补充），或者作为其所有节点之间的邻接矩阵。其中邻接矩阵是一个方阵（节点大小×节点大小）表示哪些节点直接连接到其他节点。请注意，由于大多数图不是密集连接的，因此具有稀疏邻接矩阵会使计算更加困难。图与ML中使用的典型对象非常不同，因为它们的拓扑结构比“序列”（如文本和音频）或“有序网格”（如图像和视频）更复杂：即使它们可以表示为列表或矩阵,但这种表示不能被视为有序对象。也就是说，如果你打乱句子中的单词，你就创建了一个新句子，如果你打乱图像并重新排列它的列，你就创建了一个新图像。图例：HuggingFacelogo和洗牌后的HuggingFacelogo是完全不同的新形象。但图的情况并非如此：如果我们洗掉图的边列表或邻接矩阵的列，它仍然是同一个图。图例：左边是一个小图，节点为黄色，边为橙色；中心图像上的邻接矩阵，列和行按节点的字母顺序排列：节点A的行（第一行）可以看到它与E和C的连接；右图打乱了邻接矩阵（列不再按字母顺序排列），这仍然是图的有效表示，即A仍然通过ML的图表示连接到E和C2处理图的正常过程使用机器学习首先为项目生成有意义的表示，其中节点、边或全图取决于特定任务要求，为目标任务训练预测器。与其他模式一样，可以限制对象的数学表示，使它们在数学上接近相似的对象。但其中，相似度在图ML中很难严格定义：例如，当两个节点具有相同的标签或相同的邻居时，它们是否更相似？如下所示，本文着重于生成节点表示。一旦节点级表示可用，就可以获得边或图级信息。对于边级信息，可以连接节点对或者做点乘；对于图级信息，您可以对所有节点级连接的张量进行全局池化，包括平均和求和。然而，它仍然平滑并丢失了关于整个图的信息——递归层次集可能更有意义，或者添加一个虚拟节点，连接到图中的所有其他节点，并将其表示为一个表达式。神经前方法简单地使用工程特征。在神经网络之前，图形及其感兴趣的项目可以以特定于任务的方式表示为特征的组合。这些特征今天仍在数据增强和半监督学习中使用，尽管存在更复杂的特征生成方法，但根据任务找到如何最好地将这些特征提供给网络至关重要。节点级特征可以提供关于重要性的信息以及基于结构的信息并将它们结合起来。节点中心度可以用来衡量图中节点的重要性，递归计算每个节点的邻居的中心度求和直到收敛，或者递归计算节点间的最短距离度量，节点度数是它拥有的直接邻居聚类系数衡量节点邻居的连接程度；Graphlets度向量计算计算有多少不同的graphlets以给定节点为根，其中graphlets可以使用给定数量的连接节点来创建所有迷你图。图注：2到5节点小图的边级特征补充了更详细的节点连通性信息，包括两个节点之间的最短距离，它们的共同邻居，以及Katz指数（指两个节点的路径数）可能在节点之间行进的特定长度-可以直接从邻接矩阵计算）。图级特征包含有关图相似性和特异性的高级信息，其中小图计数虽然计算量大，但提供有关子图形状的信息。核心方法是通过不同的“bagofnodes”方法（类似于bagofwords）来衡量图之间的相似度。基于行走的方法基于行走的方法使用随机行走中从节点i访问节点j的概率来定义相似性度量，并且这些方法结合了局部和全局信息。例如，之前的Node2Vec模拟了图节点之间的随机游走，使用skip-gram来处理这些游走，就像我们处理句子中的单词一样，以计算嵌入。这些方法也可用于加速PageRank方法的计算，该方法根据每个节点与其他节点的连接为每个节点分配重要性分数，例如通过随机游走来评估其访问频率。但是上述方法也有一定的局限性，不能获取新节点的embedding，不能很好地捕捉节点之间的结构相似性，不能利用增加的特征。3图神经网络如何处理图？神经网络可以泛化到看不见的数据。鉴于前面提到的表征约束，一个好的神经网络应该如何处理图？两种方法如下所示：是置换不变式：方程：f(P(G))=f(G)f(P(G))=f(G)，其中f是网络，P是置换函数，G是图解释：经过网络后，图的表示和排列应该是一样的。是一个置换等方差方程：P(f(G))=f(P(G))P(f(G))=f(P(G))，其中f是网络，P是置换函数，G是图解释：在将节点传递给网络之前置换节点应该等同于置换它们的表示典型的神经网络不是置换不变的，例如RNN或CNN，因此引入了一种新的架构-图神经网络（最初作为基于状态的机器）。GNN由连续的层组成。GNN层表示一个节点，该节点具有其邻居的表示以及来自前一层（消息传递）的自身组合，通常加上激活以添加一些非线性。与其他模型相比，CNN可以看作是具有固定邻居大小（通过滑动窗口）和排序（非置换等变性）的GNN；没有位置嵌入的Transformer可以看作是全连接输入图上的GNN。聚合和消息传递聚合来自节点邻居的信息有多种方法，例如求和和平均。此前，类似的聚类方法包括：GraphConvolutionalNetworks，对节点邻居的归一化表示进行平均；GraphAttentionNetworks，学习根据重要性对不同的邻居进行加权（如Transformer）；GraphSAGE，它在使用最大集通过几个步骤聚合信息之前，在不同的跃点对邻居进行采样；GraphIsomorphismNetworks，通过将MLP应用于节点邻居表示的总和来聚合表示。选择一个聚合：一些聚合技术（特别是平均/最大聚合）在创建细粒度表示以区分相似节点的不同节点邻居表示时失败；例如，通过聚合，具有4个节点邻居的表示是1,1,-1,-1，平均值为0，这与只有3个节点表示为-1,0,1的邻居没有区别。GNN形状和过度平滑问题在每个新层，节点表示由越来越多的节点组成。一个节点穿过第一层并且是它的直接邻居的聚合。通过第二层，它仍然是其直接邻居的聚合，但目前它的表示还包括他们自己的邻居（来自第一层）。在n层之后，所有节点的表示成为距离n处所有邻居的集合，因此如果其直径小于n，则为完整图的聚合。如果网络有太多层，则存在每个节点成为完整图的聚合的风险（并且节点表示收敛到所有节点的相同表示），这被称为过度平滑问题，可以通过组合来解决GNN缩放到足够小的层数，这样每个节点就不会被近似为整个网络（通过首先分析图的直径和形状）增加层的复杂性添加非消息传递层来处理消息（例如一个简单的MLP)Addhops过度连接过度平滑问题是图ML中的一个重要研究领域，因为它阻止了GNN的扩展，正如Transformers在其他模型中所展示的那样。GraphTransformers不带位置编码层的Transformers是置换不变的，Transformers也具有很好的可扩展性，因此研究人员最近开始考虑将Transformers应用到图上。大多数方法都专注于寻找最佳特征和表示图形的最佳方式，并将注意力调整到新数据上。下面展示的是一些在斯坦福的OpenGraphBenchmark:GraphTransformerforGraph-to-SequenceLearning上达到state-of-the-art或接近结果的方法，它引入了一个将节点表示为它们的嵌入和位置嵌入的图Transformer的拼接，节点关系表示两者之间的最短路径，将两者组合成一种关系——增强self-attention。RethinkingGraphTransformerswithSpectralAttention，引入SpectralAttentionNetworks(SAN)，这些将节点特征与学习到的位置编码（从拉普拉斯特征向量/值计算）结合起来用作注意力中的键和查询，注意力值是边缘特征。GRPE：RelativePositionalEncodingforGraphTransformer，介绍图相对位置编码Transformer，将图级位置编码与节点信息、边级位置编码和节点信息相结合，将两者结合attention来表示图。GlobalSelf-AttentionasaReplacementforGraphConvolution引入了EdgeAugmentedTransformer，这是一种分别嵌入节点和边缘并将它们聚合到修改后的注意力中的架构。DoTransformersReallyPerformBadlyforGraphRepresentation，介绍了Microsoft的Graphormer，它在OGB推出时获得了第一名。该体系结构使用节点特征作为注意力中的查询/键/值，并将它们的表示与注意力机制中的中心性、空间和边缘编码相结合。最近的一项研究《PureTransformersarePowerfulGraphLearners》在方法中引入了TokenGT，将输入图表示为一系列节点和边的embeddings，即使用正交节点标识符和可训练类型标识符进行增强，无需positionEmbedding，而feeding这个序列作为变形金刚的输入，这个方法很简单，同时也很有效。论文地址：https://arxiv.org/pdf/2207.02505.pdf另外，在研究“RecipeforaGeneral,Powerful,ScalableGraphTransformer”中，与其他方法不同的是，它引入的不是模型而是框架，称为GraphGPS，它允许将消息传递网络与线性（远程）Transformer相结合，轻松创建混合网络。该框架还包含几个用于计算位置和结构编码（节点、图、边缘级别）、特征增强、随机游走等的工具。论文地址：https://arxiv.org/abs/2205.12454Transformer对图的使用是很大程度上仍处于起步阶段，但就目前而言，它的前景也非常乐观，它可以缓解GNN的一些局限性，例如Scaletolargerordensegraphs，或者在不过度平滑的情况下增加模型大小。
