图神经网络（十一）-5.4.2 注入随机属性（5.4 比1-WL测试更强大的图神经网络架构）

系列文章目录图神经网络目录文章目录目录前言5.4.2.1 关系池化-GNN（RP-GNN）5.4.2.2 随机图同构网络（rGIN）5.4.2.3 位置感知 GNN（PGNN）5.4.2.4 随机矩阵分解总结前言以下内容来自学习笔记，主要按照《图神经网络-基础、前沿与应用》这本书进行学习。MP-GNN 的表达能力受限制的主要原因是 MP-GNN 不跟踪节点的身份。然而，具有相同属性的不同节点将以相同的向量表征进行初始化。除非它们的邻居节点传播不同的节点表征，否则这一条件将被保持。提高 MP-GNN 表达能力的一种方法是为每个节点注入一个独特的属性。给定一个 GRL 实例，。(5.9)其中，表示串联，是单位矩阵，这给了每个节点唯一的独热编码，并得到一个新的有属性图。复合模型​增强了表达能力，因为节点的身份已被附加到消息上，距离信息和环信息可以通过足够的信息传递技术来学习。然而，上述框架的局限性在于其并不是排列不变的（见定义 5.4）：给定两个同构的 GRL 实例，则和可能不再是同构的。因此，复合模型可能不等于。得到的模型由于失去了图表征学习的基本归纳偏置，因此很难被泛化。1. 什么是排列不变性？在图表示学习中，排列不变性的意思是：如果两个图是同构的（即节点编号不同、但结构完全相同），那么模型对这两个图的输出应该相同。比如下面两个图，只是节点 1 和 2 互换了标签，但结构和连接关系完全一样：图 A：节点 1 连接节点 2图 B：节点 2 连接节点 1一个具有排列不变性的模型，对图 A 和图 B 会给出完全一样的预测结果。2.方法做了什么？​方法给每个节点注入一个唯一的属性（比如用单位矩阵的一行作为独热编码）。这样，原来没有身份信息的节点（只有属性相同）现在变成了每个节点有唯一标识。例如：原来：节点 1 和节点 2 的属性都是[0,0][0,0]注入后：节点 1 的属性是[0,0,1,0][0,0,1,0]，节点 2 的属性是[0,0,0,1][0,0,0,1]3. 为什么会破坏排列不变性？因为注入的唯一属性依赖于节点的原始编号。对图 A 注入属性时：节点 1 拿到第 1 行的独热码，节点 2 拿到第 2 行的独热码。对同构的图 B 注入属性时：节点 2 可能拿到第 1 行的独热码，节点 1 拿到第 2 行的独热码。结果：图 A 注入后：节点 1 独热码 =[1,0,...]，节点 2 =[0,1,...]图 B 注入后：节点 1 独热码 =[0,1,...]，节点 2 =[1,0,...]这两个结果不再是同构的（因为节点属性完全错位了）。因此，即使图 A 和图 B 原始结构相同，经过处理后变成了不同的带属性图，模型可能会给出不同的输出。4. 这个限制为什么严重？因为图表示学习的一个核心归纳偏置就是：图的结构决定语义，节点的编号顺序不影响结果。一旦失去排列不变性：模型会对同一个图的不同编号方式学到不同的结果无法泛化到未见过的节点编号违背了图数据的基本对称性原文中说“很难被泛化”，就是这个意思。5. 一个直观的例子假设有两个同构的社交网络图，只是成员 ID 编号不同：网络 1：用户 A 关注用户 B网络 2：用户 X 关注用户 Y注入唯一属性后：网络 1 中 A 的独热码是[1,0]，B 是[0,1]网络 2 中 X 的独热码是[1,0]，Y 是[0,1]但注意：在原始结构中，A 和 B 的关系与 X 和 Y 的关系完全一样。然而因为独热码是按节点位置顺序赋予的，在重新排列节点后，A 可能拿到 X 的码，B 可能拿到 Y 的码，这没问题；但问题在于：如果你只是交换节点编号，独热码分配方式固定，就会导致原本同构的图在注入后不再同构。因此模型无法保证对这两个本质上相同的图输出相同的结果。注记 5.6其他一些方法可能与存在相同的限制，例如使用邻接矩阵A（A的每一行代表节点属性）的方法。然而，Srinivasan and Ribeiro (2020a) 认为，通过矩阵分解得到的节点嵌入，如 DeepWalk (Perozzi et al., 2014) 和 node2vec (Grover and Leskovec, 2016)，可以保持所需的不变性，因此仍然是可泛化的。将在 5.4.2.4 节中探讨这个概念。为了克服上述限制，人们最近已经提出了不同的模型。这些模型的共同策略是：首先设计一些额外的随机节点属性Z，并用它们来参数化原始数据集；然后在增强的数据集上学习一个 GNN 模型（见图 5.12）。随机属性类型位置信息模型和引用随机排列否RP-GNN (Murphy et al., 2019)（几乎均匀）离散的随机变量否rGIN (Sato et al., 2020)与随机属性节点的距离是PGNN (You et al., 2019)图卷积的高斯随机变量是CGNN (Srinivasan Ribeiro, 2020)随机签名的拉普拉斯特征映射是LE-GNN (Dwivedi et al., 2020)图 5.12通过注入随机节点属性可以提高 GNN 的表达能力。不同的研究采用了不同类型的随机节点属性，一些随机节点属性包含节点位置信息（即一个节点相对于图中其他节点的位置）这样得到的模型将更具表达能力，因为随机节点属性可以被看作区分节点的唯一节点身份。然而，如果模型只是基于由这些随机属性增强的单个 GRL 实例进行训练，则模型并不能像上面讨论的那样保持不变。作为替代，模型需要通过多个独立注入的随机属性增强的 GRL 实例来训练。新的增强后的 GRL 实例与产生它们的原始 GRL 实例具有相同的目标。通过在增强的实例上训练模型，基本上可以使模型的排列方差近似化，使它们的行为几乎“排列不变”。1. 为什么加随机属性能让模型变强？原来：如果两个节点属性相同，模型一开始会认为它们一样。加了随机属性后：每个节点有一个独一无二的标记（虽然随机）。结果：模型能区分每个节点，表达能力增强了。就像给班里每个学生发一个随机编号，老师就能区分他们了。2. 但这样会带来什么问题？图学习的核心要求：两个结构完全相同的图，输出必须一样。加固定随机属性后：同一个图换个节点编号顺序，随机属性会错位，模型可能给出不同结果。这就是前面说的失去排列不变性。好比两个一模一样的学生名单，只是名字顺序换了，但模型却认为不一样。3. 那怎么办？不能只用一个随机属性版本，而是：对同一个原始图，生成很多个不同随机属性版本。每个版本都输入模型，模型看到的是多个“长得不同但结构相同”的图。模型要学的是：不管随机属性怎么变，输出应该一样（因为原始图相同）。就像让模型看很多次同一张图、但每次给节点换不同的随机编号，逼它忽略编号、只看结构。4. 结果是什么？模型不再是严格数学上的排列不变，而是近似排列不变：对同一个图的不同随机属性版本，输出几乎一样。对同构的不同图，输出也几乎一样。原文说的“使模型的排列方差近似化”就是这个意思：让模型对排列的变化不那么敏感，近似做到不变。5. 一句话总结不能只用一个随机属性版本训练模型（那样会破坏排列不变性）。必须对同一个图生成多个不同随机属性的版本，让模型在这些版本上学会忽略随机属性、只看结构，从而近似保持排列不变性。这些随机属性的注入方法有多种，但其中一种最直接的方法是将Z附加到X上，即给定一个图结构的数据(X,S)，其中，其中且。注意，对于每个实现Z，复合模型​不是排列不变的。作为替代，所有这些方法旨在使得排列不变，并希望模型保持期望不变性。为了匹配这种期望不变性，这些方法必须满足以下命题。命题 5.1为了通过注入随机属性Z建立一个模型，需要具备以下两个前提条件。在训练阶段就应该对足够数量的Z进行抽样，以便在模型中能够确实捕捉到期望不变性。Z的随机性应该与原始节点身份无关。为了满足第一个前提条件，有研究表明，在训练阶段，当针对每一个前向传递计算​时，一个Z应该被重新抽样一次或多次，以获得足够的数据进行论证。为了满足第二个前提条件，人们已经提出了 4 种不同类型的随机属性Z，具体描述如下。5.4.2.1 关系池化-GNN（RP-GNN）Murphy et al. (2019a) 考虑将节点的随机分配顺序作为其额外属性，并提出了关系池化-GNN（RP-GNN）模型。他们使用​来表示 RP-GNN 中使用的额外节点属性Z。假设图G有n个节点，并且​是从所有可能的排列矩阵中均匀抽样的。也就是说，随机选取一个双射（排列）