HyperGCN（2019-NIPS）

HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs

• 动机
• 贡献
• 模型：
• • HyperGCN
  • 超图拉普拉斯
  • 1-HyperGCN
  • HyperGCN: Enhancing 1-HyperGCN with mediators
  • FastHyperGCN
• 实验
• • 数据集
  • baselines
  • HyperGCN比HGNN的优势
  • 组合优化问题： densest k -subhypergraph problem（NP-hard）
  • 局限
• HyperGCN算法：
• • FastHyperGCN
  • 1-HyperGCN

论文：https://papers.nips.cc/paper/8430-hypergcn-a-new-method-for-training-graph-convolutional-networks-on-hypergraphs

code:https://github.com/malllabiisc/HyperGCN

动机

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

贡献

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

我们方法的动机是基于节点相似度，而且我们发现我们方法可被用于超图编码不相似情况下的组合优化。

模型：

hypergraph 与 graph的符号对应

1.图卷积

两层的简单图卷积

其中：

• A ˉ = D ~ − 1 2 D ~ A ~ − 1 2 ,   A ~ = A + I \bar A=\tilde{D}^{-\frac{1}{2}}\tilde{D}\tilde{A}^{-\frac{1}{2}},\ \tilde{A}=A+I Aˉ=D~−21​D~A~−21​, A~=A+I,即标准化后的邻接阵。

  2.半监督训练：

  

  这里是多分类问题，有 q 类，最小化标签集 V L V_L VL​交叉熵。卷积层权重训练使用梯度下降。

HyperGCN

预备：

• H = ( V , E ) \mathcal{H}=(V,E) H=(V,E)表示无向图
• ∣ V ∣ = n , ∣ E ∣ = m |V|=n,|E|=m ∣V∣=n,∣E∣=m
• 有标签集 V L V_L VL​

• 特征矩阵： X ∈ R n × p X \in \mathbb{R}^{n \times p} X∈Rn×p , 每个顶点 v ∈ V = { 1 , . . . , n } v\in V = \{1,...,n\} v∈V={1,...,n}

  任务：预测所有无标签顶点，即， V V V \ V L V_L VL​

  原则：在相同的边的节点是相似的，即具有相同的标签。

  用 { h v : v ∈ V } \{h_v:v\in V\} {hv​:v∈V}表示V中的节点一些表示，最后显示正则化目标为

  ∑ e ∈ E m a x i , j ∈ e ∣ ∣ h i − h j ∣ ∣ 2 \sum_{e\in E}max_{i,j\in e}||h_i-h_j||^2 e∈E∑​maxi,j∈e​∣∣hi​−hj​∣∣2

  然而我们采用了隐式正则化，即通过使用一个适当定义的GCN超图的拉普拉斯变换，实现相同边上的节点具有相似的表达。

超图拉普拉斯

graph上的laplacian矩阵可以视作一个线性变换，而超图的Laplacian却是一个非线性变换： L : R n → R n \mathbb{L}:\mathbb{R}^n\rightarrow \mathbb R^n L:Rn→Rn

定义：超图拉普拉斯

给定一个定义在超图节点上的实值信号 S ∈ R n S\in \mathbb R^n S∈Rn， L ( S ) \mathbb{L}(S) L(S)计算如下：

1. 对图上任意边 e ∈ E e\in E e∈E,令 ( i e , j e ) : = a r g m a x i , j ∈ e ∣ S i − S j ∣ (i_e,j_e):=argmax_{i,j\in e}|S_i-S_j| (ie​,je​):=argmaxi,j∈e​∣Si​−Sj​∣,breaking ties randomly,即同一条边上距离最远的两个顶点的编号表示为 ( i e , j e ) (i_e,j_e) (ie​,je​).
2. 顶点集V上的定义的权重图 G S G_S GS​, 通过在边 { { i e , j e } : e ∈ E } \{\{i_e,j_e\}:e\in E\} {{ie​,je​}:e∈E}上加上权重 w ( i e , j e ) : = w ( e ) w({i_e,j_e}):=w(e) w(ie​,je​):=w(e),这里 w ( e ) w(e) w(e)是超图e的权重。 A S A_S AS​表示 G S G_S GS​的带权邻接阵。实际上这里相当于将超图变成了普通的简单带权图 G S G_S GS​。

3. 对称正则化的超图拉普拉斯变换表示为： L ( S ) : = ( I − D − 1 2 A S D − 1 2 ) \mathbb L(S):=(I-D^{-\frac{1}{2}}A_SD^{-\frac{1}{2}}) L(S):=(I−D−21​AS​D−21​)

   用上面的定义，给出一个超图节点上的信号S就可以计算出其Laplacian变换后的值 L ( S ) \mathbb L(S) L(S)了。

1-HyperGCN

我们将简单图 G S G_S GS​的正则化带权邻接阵表示为 A ˉ S \bar{A}_S AˉS​,然后再图 G S G_S GS​上使用GCN,(公式1), 在神经信息传播框架中我们将超节点v的信息更新表示为：

h v τ + 1 = σ ( ( Θ ( τ ) ) T ∑ u ∈ N ( v ) ( [ A ˉ s ( τ ) ] u , v ⋅ h u ( τ ) ) ) h_v^{\tau+1}=\sigma((\Theta^{(\tau)})^T \sum_{u \in \mathcal{N}(v)}([\bar{A}_s^{(\tau)}]_{u,v}\cdot h_u^{(\tau)})) hvτ+1​=σ((Θ(τ))Tu∈N(v)∑​([Aˉs(τ)​]u,v​⋅hu(τ)​))

其中

• τ \tau τ是epoch数
• h v τ + 1 h_v^{\tau+1} hvτ+1​是节点 v v v新的隐含层节点表示。
• N ( v ) \mathcal{N}(v) N(v)是v 的邻域
• [ A ˉ s ( τ ) ] u , v [\bar{A}_s^{(\tau)}]_{u,v} [Aˉs(τ)​]u,v​是正则化后边 { v , u } \{v,u\} {v,u} 的权重
• h u ( τ ) h_u^{(\tau)} hu(τ)​是前一阶段邻域节点的隐含表示，

  

  上图中超点v有5个超边与其连接，然后用简单边去代替超边，即在第 τ \tau τepoch时，边为 ( i e , j e ) = a r g m a x i , j ∈ e ∣ ∣ ( Θ ( τ ) ) T ( h i ( τ ) − h j ( τ ) ) ∣ ∣ 2 (i_e,j_e)=argmax_{i,j\in e}||(\Theta^{(\tau)})^T(h_i^{(\tau)}-h_j^{(\tau)})||_2 (ie​,je​)=argmaxi,j∈e​∣∣(Θ(τ))T(hi(τ)​−hj(τ)​)∣∣2​

  得到第 τ \tau τ轮的简单图之后，我们在简单图上实现GCN，训练到收敛。

  这里使用的隐式正则化不仅可以将超图结利用到SSL中节点分类，还可以通过这个GCN将节点的特征信息也包含进来，比如：文本属性等。

HyperGCN: Enhancing 1-HyperGCN with mediators

上面的模型在生成简单图时将同一条边上除了选取的两个代表节点外其他节点都舍去了，这造成了信息的损失，所以这里提出了将这些点 K e : = { k ∈ e : k ≠ i e , k ≠ j e } K_e:=\{k\in e:k\ne i_e,k\ne j_e\} Ke​:={k∈e:k​=ie​,k​=je​}作为“中介”，将这些点分别跟 i e , j e i_e,j_e ie​,je​都连接起来。

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

FastHyperGCN

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

实验

数据集

Table 3: Real-world hypergraph datasets used in our work. Distribution of hyperedge sizes is not

symmetric either side of the mean and has a strong positive skewness.

baselines

• Hypergraph neural networks (HGNN)
• Multi-layer perceptron (MLP)
• Multi-layer perceptron + explicit hypergraph Laplacian

• Confidence Interval-based method (CI)

  训练次数200epochs，100次不同的训练测试集划分，测试结构

  

  结果显示1-HyperGCN效果最差，这是很显然是因为其只在超边中选取了两个点，而其他两个模型则把所有点的信息都融合进去了。

HyperGCN比HGNN的优势

我们在训练集中加入噪声，我们超边所有连接的点都是同一类节点的称为纯的，而超边不是全是同一类的称为有噪声的，我们将训练集中的一部分取样成纯的，另一部分取成有噪声的，两者的比例记为 η \eta η,从0.75到0.5,（纯到不纯），得到表5结果，发现加入越多噪声对我们HpyerGCN越有利，这是因为HGCN其连接的是更多相似的节点。

组合优化问题： densest k -subhypergraph problem（NP-hard）

即在超图G中选出k 个顶点，使得其对应的子超图涵盖了G中最多的超边。

局限

模型的结果的好坏对权重的初始化依赖性很大。

HyperGCN算法：

先选距离远点的两个核心点，其他点再跟他相连（也就是在邻接阵中分配权重），然后成为加权普通图。每层，每个epoch进行更新。

FastHyperGCN

将核心点和同一个超边中的其他点先连好，然后作为新的普通图，使用GCN学习。

1-HyperGCN

只连接核心点，同一个超边中的其他点都直接丢弃（也就是drop edge）。每个epoch 每层进行更新。