图机器学习无处不在，用 Transformer 可缓解 GNN 限制( 二 ) 作者|ClémentineFourrier编译|黄楠

文章图片
图注：HuggingFace标志和被打乱的HuggingFace标志，是完全不同的新形象但图的情况并非如此：如果我们洗掉图的边缘列表或邻接矩阵的列，它仍然是同一个图。

文章图片
图注：左边是一个小图，黄色表示节点，橙色表示边；中心图片上的邻接矩阵，列和行按节点字母顺序排列：节点A的行（第一行）可以看到其连接到E和C；右边图片打乱邻接矩阵（列不再按字母顺序排序），其仍为图形的有效表示，即A仍连接到E和C
2通过ML的图形表示使用机器学习处理图的常规过程，是首先为项目生成有意义的表示，其中，节点、边或完整图取决于具体任务需求，为目标任务训练预测器。与其他模式一样，可以通过限制对象的数学表示，以便在数学上与相似对象接近。但在此之中，相似性在图ML中很难严格定义：例如，当两个节点具有相同的标签或相同的邻居时，它们是否更相似？
如下面所示，本篇文章重点关注的是生成节点表示，一旦有了节点级的表示，就有可能获得边或图级的信息。对边级信息，可以将节点对的连接起来，或者做点乘；在图级信息中，可以对所有节点级表示的串联张量进行全局池化，包括平均、求和等。但是，它仍然会使整个图的信息变得平滑和丢失——递归的分层集合可能更有意义，或者增加一个虚拟节点，与图中的所有其他节点相连，并将其表示作为整个图的表示。
前神经方法简单地使用工程特性
在神经网络之前，图形及其感兴趣的项目可以通过特定任务的方式表示为特征的组合。在今天，这些特征仍用于数据增强和半监督学习，尽管存在更复杂的特征生成方法，但根据任务找到如何最好地将这些特征提供给到网络至关重要。
节点级特征可以提供关于重要性的信息以及基于结构的信息，并对其进行组合。
节点中心性可用于衡量图中节点的重要性，通过对每个节点邻居中心性求和直到收敛来递归计算，或是通过节点间的最短距离度量来递归计算，节点度是其拥有的直接邻居的数量；聚类系数衡量节点邻居的连接程度；Graphlets度向量计算则可计算有多少不同的graphlets以给定节点为根，其中， graphlets可使用给定数量的连接节点来创建的所有迷你图。

文章图片
图注：2到5节点小图
边级特征用关于节点连通性的更详细信息补充表示，其中就包括了两个节点之间的最短距离、它们的共同相邻点以及Katz指数（指两个节点之间可能走过的一定长度的路径的数量——其可以直接从邻接矩阵中计算出来）。
图级特征包含关于图相似性和特殊性的高级信息，其中，小图计数，尽管计算成本很高，但提供了关于子图形状的信息。核心方法通过不同的"节点袋"方法（类似于词袋）来衡量图之间的相似性。
基于行走的方法基于行走的方法使用随机行走中从节点i访问节点j的概率来定义相似性度量，这些方法结合了局部和全局信息。例如，此前Node2Vec模拟图形节点之间的随机游走，使用skip-gram处理这些游走，就像我们处理句子中的单词一样，以计算嵌入。
这些方法还可用于加速PageRank方法的计算，该方法给每个节点分配一个重要性分数，基于它与其他节点的连接，例如通过随机行走来评估其访问频率。但上述方法也存在一定的局限性，它们不能获得新节点的嵌入，不能很好地捕捉节点之间的结构相似性，不能使用添加的特征。