超图卷积网络(HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs)

1. 简介 (Introduction)

1.1 背景 (Backgrounds)

在许多诸如co-authorship网络，co-citation网络等现实世界的网络中，关系是复杂的并且超出了成对关联。超图（Hypergraph）提供了一种灵活而自然的建模工具来对这种复杂的关系进行建模。在许多真实的网络中，这种复杂关系普遍存在，因此激发了使用超图学习的问题。一种流行的学习方法是基于超图的半监督学习(SSL)，其目标是对超图中未标记的顶点分配标签。受图卷积网络(GCN)对于图上的半监督学习十分有效的启发，我们提出了HyperGCN，这是一种基于超图的谱论（sepctral theory）来训练用于超图上半监督学习的GCN的新方法。我们通过在真实世界的超图上进行SSL和组合优化的详细实验来证明HyperGCN的有效性，并分析它何时会比最新基准更有效。

1.2 主要贡献 (Contributions)

• 我们提出了HyperGCN，利用超图的谱理论在超图上训练GCN，并且介绍了其变体：FastHyperGCN
• 在真实世界超图上用我们的方法解决了SSL和组合优化问题。且通过实验证明了我们的算法比较高效
• 全面讨论了我们的方法与HGNN的区别与优势

2. 相关工作 (Related work)

2.1 图卷积网络(GCN)

2.2 图上半监督学习(SSL on graphs)

图/超图上半监督学习的输入为一个图(G),其中包括少量的labelled节点，大量的unlabelled节点。通过图上半监督学习，我们期望为unlabelled节点分配合适的label。这有助于我们使用大量的unlabelled数据，从而服务于下游任务。

SSL on graphs/hypergraphs 基于这样一个假设：邻域节点共享相同的label

对于SSL on graphs，q分类问题，我们可以选用交叉熵作为损失函数

2.3 图与超图常见符号对比(Summary of symbols)

3. 超图卷积网络 (HyperGCN: Hypergraph Convolutional Network)

3.1 超图拉普拉斯变换

为了实现我们的假设目标：

the hypernodes in the same hyperedge having similar representations.

我们可以使用如下隐式正则器：

[sum_{ein E}max_{i,j in e}||h_i-h_j||^2
]

这是因为，要使得该式子尽可能的小，必须满足每一条超边各个节点的label彼此接近。

然而，我们还可以使用另一种方法：超图拉普拉斯变换 来作为隐式正则器来实现这个目标。

简单图上的拉普拉斯矩阵可以视作一个线性变换，而超图的拉普拉斯却是一个非线形变换(L: R^n to R^n)。

定义：给定一个定义在超图节点上的实值信号(S in R^n)，经过超图拉普拉斯变换后的信号(L(S))计算如下：

• 首先将超图中每一条超边转化为一条简单边。方法是选择距离最远的两个节点，在这两个节点之间连接一条边，边权即为原始的超边边权。
• 然后超图就转化成了简单带权图(G_s)，我们对该简单图求标准化的拉普拉斯矩阵(L_0 = I - D^{-frac{1}{2}}A_sD^{-frac{1}{2}}) 。
• 超图拉普拉斯变换即用所得到的(L_0)左乘(S)，即(L(S) = L_0 S)

3.2 超图卷积(1-HyperGCN)

超图在拉普拉斯变换后会化为简单图(G_s)。而本文所说的超图卷积实际上就是先将超图转化为带权简单图(G_s)后，再对简单图(G_s)做GCN。如图为HyperGCN在某一个节点(v)上的单次更新操作。

3.3 带中介超图卷积(HyperGCN: Enhancing 1-HyperGCN with mediators)

上面的模型在生成简单图时将同一条边上除了选取的两个代表节点外其他节点都舍去了，这造成了信息的损失，所以这里提出了将这些点(K_e:={kin e: k neq i_e,k neq j_e})作为“中介”，将这些点分别跟(i_e,j_e)都连接起来，如下图所示。

由于Laplacian矩阵中元素是经过正则化的，所以要求每个超边中的小边权重和都要为1，而对于具有中介的图来说，在超边中每增加一个点都要多两条边，即(a_n-a_{n-1}=2:=d,a_2 = 1)求解等差数列可以得到边数量为(2|e|-3)，所以权重选择为(frac{1}{2|e|-3})。(|e|)表示该超边对应连接的节点数。

3.4 快速超图卷积(FastHyperGCN)

我们使用最初始的特征X（无权）去构造Laplacian 矩阵(有中介)，我们将这个方法叫做FastHyperGCN，因为这X无需在每一轮中进行更新，所以这个方法速度会比其他快。然而，由于(X)始终是最初始的特征，难免会在效果上不如HyperGCN。