ICML 2022
《G-Mixup: Graph Data Augmentation for Graph Classification》

把mixup这种插值方法应用到graph augmentation中。首先回忆mixup：
image.png
于是作者有了一个idea：
image.png
想对graph做mixup比较困难，首先每个图节点数量不一样，没办法找一对匹配的点，不同的图拓扑也是不同的。
具体做法作者简单说了说，核心思想是通过mixup graphon来进行graph的mixup。graphon是一个generator，可以看作一个概率矩阵W，每一个entry代表点i和点j之间有连边的概率。
主要贡献就包括mixup方法，其真的产生了mixture的证明，以及实验好。
走基本概念。

Preliminaries

除了常规的graph定义，还有graph set，每个graph set都有label，一共有C个label，也就是说有C种graph。此外还有motif，指频繁出现的子图。每一个graph set还有个graphon。确定graphon和节点的数量可以生成一个随机图。
接下来是一个有点难理解的新概念，graph homomorphism，图同态，一开始误会成图同构了。作者举了点例子方便理解。
image.png
有点排列组合的知识。定义同态密度：
image.png
接下来是graphon。目前把它想成 一个二维矩阵，每个entry W_ij是i和j连边的概率就够了。
最后就是图分类和GNN相关，不加赘述。

Methodology

G-mixup是class-level的图增强方法。过程：
image.png
注意这里英文字母是花体的，代表是拥有同标签的graph set。
image.png

implementation

一些实现细节。比较让人在意的首先就是那个graphon是怎么生成的。作者说用step function，阶梯函数。首先明确W是一个K乘K的矩阵，每个元素是w_kk’，取值范围在0到1之间，后面会有公式用到。
下面那段话也很重要。回忆一下graphon一个graph set产生的，假设一个set有m个graph，首先会对节点做一个排序对齐，譬如按照节点的度排序，再通过对齐后的邻接矩阵来对W进行计算。
image.png
接下来就是这个step function的设定，想了很久输入的x和y是什么，应该是邻接矩阵对应的值，因为我们想填满一个K乘K的矩阵，要求输入两个介于0到1的值，可以举例子，比如我们给W在（1，2）位置赋值，那么就取每个邻接矩阵在（1，2）的值，两个两个放进去。作者说的话太少了，可以参照另一个参考文献。哈哈，走了。
image.png
下一个实现细节就是合成图的步骤，也就是mixup。上一步已知要合成的图有几个节点K，以及其graphon W_I。
image.png
Bern指伯努利分布。image.png。首先从均匀分布中取kK个点，然后代入左边这个式子，粗体W就是上一节的step function。第二个步骤就是生成合成图的邻接矩阵，因为step function有这个能力。
还有一个时间复杂度分析：
image.png
理论分析直接放弃，嘿嘿。
实验等讲组会再看。