1 Title
HNHN: Hypergraph Networks with Hyperedge Neurons(Yihe Dong、Will Sawin、Yoshua Bengio、Mila)[ICML 2020]
2 Conclusion
This study proposes a novel framework, HNHN, for hypergraph representation learning. HNHN is a hypergraph convolution network with nonlinear activation functions applied to both hypernodes and hyperedges, combined with a normalization scheme that can flexibly adjust the importance of high-cardinality hyperedges and highdegree vertices depending on the dataset
3 Good Sentences
1、For vertices i and j, the entry Aij can be defined as a sum over hyperedges containing both i and j of a weight function, that may depend on the number of vertices in the hyperedge. However, these approaches do not fully utilize the hypergraph structure(The problems of the way that defining an appropriate hypergraph analogue of the adjacency matrix A)
2、This produces large values for vertices of high degrees but small values for vertices of low degrees. Normalization ensures numerical stability during training. Different options exist for normalization, depending on how we weight the different vertices (as a function of their degrees)(The reason why hypergraphes and graphes need normalization)
3、To apply graph convolution to hypergraph problems, we must build a graph G from our hypergraph H. There are two main approaches to this in the literature.(Relationship with clique and star expansions)
4、The clique expansion is a problematic approach to studying any hypergraph problem because it involves a loss of information - i.e. there can be two distinct hypergraphs on the same vertex set with the same clique expansion.(The shortcomings of clique expension when compared with HNHN)
HNHN是一个超图卷积网络,具有应用于超节点和超边的非线性激活函数,并结合了一个归一化方案,可以根据数据集灵活调整高基数超边和高度顶点的重要性。
Hyperedge nonlinearity:
本文用表示超节点和表示超边,并使用它们来训练网络。然后,可以将超节点-超边关联矩阵用于卷积步骤。然后,非线性函数σ作用于超节点和超边。通过以上这些操作,可以使得网络学习单个超边的非线性行为。
Normalization:
图形卷积中的归一化是必需的,因为训练过程需要维持稳定性。
对称归一化拉普拉斯公式:
Model architecture and analysis
其中,σ是非线性激活函数,W是权重矩阵,b是偏差矩阵。
用表示节点的边领域矩阵,其中,同时用表示超边的节点领域,同样
Relationship with clique and star expansions
本文方法与原始图卷积方法的关系:如果去除非线性激活函数就等于团展开,如果,那么就相当于星展开。
如图,c是团展开,d是星展开。
团展开的缺点是涉及信息的丢失-即在相同的顶点集上可能有两个不同的具有相同团扩展的超图
比如这个,团展开无法分辨这两个超图。
星展开的缺点是它对超节点和超边都一样,但是实际场景了超节点和超边往往是不同的,所以应该有不同的权重。
Weight simplification:
设为图G*的邻接矩阵,
如果在更新规则中设置和,则对于所有有
将定义为与 m × d 的零矩阵的串联,是 n × d 的零矩阵与的串联,那么:
Linear simplification:
为了将Gc上的图卷积与超图卷积联系起来,我们首先将Gc的邻接矩阵与关联矩阵a联系起来
定理1:设C是Gc的邻接矩阵。那么。
定理2:如果,那么。
Hypergraph normalization:
一种常见的消息传递方法是在消息池化后根据邻域的基数来规范化消息。在将消息从超边传递到超节点的情况下,这可以表示为,其中
根据实际参数α,通过其度数的幂对每个超边的贡献进行加权:
如果α = 0,那么就是单位矩阵,=,这推广了上面的归一化。
,当α>0时,超边的贡献增加,而如果α<0,则超边的贡献减少。那可以将α视为针对给定数据集进行优化的超参数。
同理,也可以通过超参数β给超节点附加权重