点击上方 蓝字关注我们
本文作者Gongxu Luo（北航）
Jianxin Li（北航）
Hao Peng（北航）
Carl Yang（Emory University）
Lichao Sun（Lehigh University）
Philip S. Yu(UIC)
Lifang He (Lehigh University)
https://arxiv.org/pdf/2105.03178.pdf
Graph Entropy Guided Node Embedding Dimension Selection for Graph Neural Networks
图表示学习在许多领域取得了巨大的成功，包括电子商务、化学、生物学等。然而，为给定的图选择合适的节点嵌入维度的基本问题仍未解决。基于网格搜索或经验知识的节点嵌入维度选择 (NEDS) 的常用策略存在计算量大和模型性能差的问题。
在本文中，作者从最小熵原理的角度重新审视 NEDS。随后，提出了一种基于最小图熵 (MinGE) 的算法去找最优嵌入维度。具体来说，MinGE 考虑了图上的特征熵和结构熵。特征熵假设相邻节点的嵌入相似。结构熵以归一化的度为基本单位，进一步衡量图的高阶结构。
基于它们，作者设计了MinGE来计算图上的嵌入维度。最后，在基准数据集上使用最近的图神经网络 (GNN) 进行实验表明提出的 MinGE 的有效性和通用性。
特征熵
特征熵的定义可以用下面的公式进行表示
其中Z=\sum_{i,j}exp(v_i, v_j), i和j是任意的两个点。上面的公式可以作进一步的简化
进一步
但是难算，同时观察到每一维度绝对值的分布是均匀分布，那不妨归一化一下，认为他的长度为: sqrt(n),也就是说这些节点生活在半径为\sqrt(n)的超球上，这样的话=n*cos(\theta)，这样也方便将嵌入的维度n和熵结合在一起。
接下来，需要两个随机向量之间的角度 θ 的概率分布以n 作为唯一变量。由于各向同性，只需要考虑单位向量。此外，只需要固定其中一个向量，并考虑另一个向量的随机变化。比如说将x定义成（x_1,x_2,...x_n）另一个向量y定义成（1, 0, 0..., 0）
通过上面的方式定义一个n维的向量，那么x跟y的夹角是phi_1
小于theta的概率为
从而计算特征熵是这样的
结构熵
定义A^2是一个二阶的adj mat, A^2_r是一个normalized 二阶adj mat
进一步，定义normalized degree vector D_r
那么结构熵这样表示
整体上
整体的算法流程是这样的
作者在NC和LP上进行了测试，在已有的模型上都有相对的提升
在本文中，作者从最小熵原理的角度重新审视了图数据的节点嵌入维度选择（NEDS）。提出了 MinGE，这是一种结合精心设计的特征熵和结构熵的新算法，用于指导 GNN 的 NEDS，并解决了如何直接为图数据选择合适的节点嵌入维度的挑战。MinGE通过使用最小熵原理为适当的 NEDS 最大化节点信息和结构信息。
小编有个问题：这怎么优化的？维度根据熵提前算好，然后施加到已经有的模型上吗？思考中...
