GNN 2021(十) GRAPH EDIT NETWORKS，ICLR

本篇快速浏览，在阅读过程中发现其中一些定理的证明过程可在原文中找到依据。经过34页内容的系统学习后，读者能够深刻理解其核心思想

INTRODUCTION

尽管图神经网络在节点分类或图分类任务方面已获得广泛的研究然而到目前为止仍鲜有方法能够将图结构输入转换为相应的图结构输出。由于在图上执行时间序列预测通常需要生成对应的下个时间步的图结构。

Graph Edits

属性图构成一个三元组G=\{V,E,X\}的形式存在。graph edit则被视为一种将图形转换为目标图形的映射操作：\delta:G_1→G_2。这种映射关系主要用于刻画两个图形之间的差异（通过特定的操作获得），而所谓的"编辑"则指的是对节点或边进行添加、删除或修改等操作。其中，在编辑过程中会涉及到以下几种基本操作：删除某个节点i（由del_i决定），设置节点i的属性值为x（用rep_{i,x}表示），插入一个新的属性值为x的节点（以ins_x来表示），移除两个节点之间存在的边（由(edel_{i,j})来实现），以及添加新的连接两个节点之间边的操作（用(eins_{i,j})来表示）。而整个图形的edit脚本\bar{\delta}=\{\delta_1,...,\delta_T\}则是一系列图形编辑操作的集合。通过这一脚本序列的应用可以使初始图形逐步转变为目标图形，在本文的研究中我们正是要学习如何生成这样一个有效的edit脚本序列。

GRAPH EDIT NETWORKS

整体的思路还是比较简单，看图：

首先，我们使用一些图神经网络来计算节点嵌入矩阵：

虽然表达方式与常规有所不同, 但仍然能够理解.接着, 在这一过程中,
我们采用了线性层来计算数值编辑分数,
用于标识哪些节点和边应当被删除、插入或重新标记.
其后,
我们利用算法1将这些分数转化为edit script \bar{\delta},
将其应用至输入图中得到输出图,
即 G_{t+1} = \bar{\delta}(G_t).

GRAPH EDIT NETWORK LAYER

本研究中提出了一种图形编辑网络(GEN)，它是一种线性层。该层通过计算编辑分数来决定应删除、插入或重新标记哪些节点和边。其输入为GNN输出Φ∈R^{N×n}；该层通过训练node edit scores v∈R^N以及两个edge filter scores e^+∈RN和e^-∈RN（其中e^+和e-分别对应出边与入边），并引入一个用于替换的节点属性Y来进行操作。对于满足e^+>0与e->0的情况，在接收Φ∈R^{N×n}后会计算每条边(i,j)的具体得分ε_{i,j}：具体而言，在接收节点i与j各自的两个特征φ_i与φ_j后（φ_i, φ_j ∈ R^{n），利用内积φ_i}T·φ_j作为输入来计算每条边(i,j)对应的得分ε_{i,j}：若需插入新连接，则ε应为正；反之则需删除相应节点；同理若需添加边(i,j)，则ε应为正；反之则应删除该边。

From scores to edits

通过将上述计算得到的得分映射到具体的edits操作...

TRAINING

在训练过程中定义损失函数时（原文：训练的时候为了定义损失函数），通常需要一组teaching-based signal (\hat{v}, \hat{Y}, \hat{e}^+, \hat{e}^-, \hat{E})（原文：为了定义损失函数(\dots)）。然而（原文：但是），这种基于单一阶段的教学信号往往难以满足复杂需求（原文：这种一步式的教学信号有时是不够的）。例如（原文：比如），在以下场景中（原文：以下这种情况）：

由于每次只能插入一个新节点，在单步更新中无法完成两个图之间的转换。但是/尽管如此，则可设立分阶段的教学反馈机制：

定理2阐述了这样一个过程：任何输入图Gt都能通过K + 1个步骤成功转换为对应的输出图G_{t+1}。具体而言，在前K个步骤中仅进行插入操作，在最终一个步骤中完成所有其余的操作。

基于一组预设的教学信号（ground truth），我们可以定义一个复杂的损失函数L。该损失函数由多个子项构成：第一部分是用于衡量预测属性与预期属性之间差异的程度；第二部分则针对那些未被删除的节点计算其关联属性间的差异性损耗。对于图中的出边与入边而言，则需分别计算\hat{e}^+与\hat{e}^-预测值与真实值之间的一致性程度（本质上是二分类差异损失）。此外，在每一步训练过程中还需加入对边状态变化相关的额外损耗项——这些损耗由\epsilon_{i,j}来量化计算。所有这些不同类型的损耗最终都会被整合到单个图对的总训练损耗中。

INFERENCE

推理的时候遵从以下步骤：

1. 将整个网络的所有节点标记为红色。
2. 若当前网络中没有被标记为红色的节点，则执行第4步；否则依次处理每一个被标记为红色的点。
3. 按照算法所述的方式进行边的操作：首先添加新的红点；然后对那些满足条件v_i <= ½ 的点进行蓝点标记。
4. 计算网络中各点及其相关属性的数据参数Φ、Y、e⁺、e⁻ 和 E，并将那些满足 v_i >½ 的部分数值设为零。

实验

在实验中采用了与以往所见的不同的图神经网络任务进行了说明。

感觉这几个任务的节点数量都比较少，准确率也都蛮好的：