《Graph Entropy Guided Node Embedding Dimension Selection for Graph Neural Networks》论文解读

论文传送门：click here

论文动机

本篇论文是2021IJCAI上的论文。

在Node Embedding Dimension Selection (NEDS)问题中，对于编码维度的设置，常使用梯度搜索或者经验知识的方法来进行选择，但这种方法面临着庞大的计算量和较差的模型表现等问题。

而本文受到维度选择工作的启发，以最小熵原理（minimum entropy principle）重新审视这个问题，提出了Minimum Graph Entropy 算法，特别的，从两方面来考虑熵：

• 从feature层面上
• 从structure层面上

结果也证明了这种方法的有效性

注：这篇论文是设计了一种算法找到最优的编码维度空间大小，而非设计了一种深度学习方法。

方法论

定义图熵为：
$$
H_g=H_f+\lambda H_s
$$
其中 $H_f$ 是feature熵， $H_s$ 是structure熵。通过设置 $H_g=0$ 我们能够得到合适的embedding维度 $n$。

Feature Entropy

说道熵就一定要提到概率分布，那么这里的概率分布如何定义的呢？
$$
P(v_i,v_j)=\frac{e^{\langle v_i,v_j\rangle}}{\sum_{i,j}e^{\langle v_i,v_j\rangle}},
$$
其中 $\langle v_i,v_j\rangle$ 代表两个节点的embedding向量的点乘。至于点乘越大概率越大是否合理、是否有意义呢

简单的化简过后，我们便能够得到熵的表达式：
$$
H_f=logZ-\frac{1}{Z}\sum_{ij}e^{\langle v_i,v_j\rangle}\langle v_i,v_j\rangle, \quad Z=\sum_{i,j}e^{\langle v_i,v_j\rangle}
$$
接下来用样本的均值来代替分布的期望：
$$
Z=\sum_{ij}e^{\langle v_{i},v_{j}\rangle}=N^{2}\frac{1}{N^{2}}\sum_{ij}e^{\langle v_{i},v_{j}\rangle}\approx N^{2}E_{v_{i},v_{j}}(e^{\langle v_{i},v_{j}\rangle})
$$

$$
\sum_{ij}e^{\langle v_{i},v_{j}\rangle}\langle v_{i},v_{j}\rangle=N^{2}\frac{1}{N^{2}}\sum_{ij}e^{\langle v_{i},v_{j}\rangle}\langle v_{i},v_{j}\rangle\approx N^{2}E_{v_{i},v_{j}}(e^{\langle v_{i},v_{j}\rangle}\langle v_{i},v_{j}\rangle)
$$

从而代回熵的计算公式，我们有：
$$
H_f=logN^2+logE_{v_i,v_j}(e^{\langle v_i,v_j\rangle})-\frac{E_{v_i,v_j}(e^{\langle v_i,v_j\rangle}\langle v_i,v_j\rangle)}{E_{v_i,v_j}(e^{\langle v_i,v_j\rangle})}
$$
接下来遇到的问题就是，点乘并不好计算，因为我不知道编码后向量的具体数值。此处作者采用的方式为：将embedding映射到半径为 $\sqrt n$ 的 $n$ 维超球体上。此时有 $\langle v_i,v_j\rangle=n\cdot\cos(\theta)$。

为了方便计算，将一个向量固定为 $y=(1, 0,\cdots,0)$，这样能够的得到 $\cos \theta=\varphi_1$

根据文献，能够知道角度的概率密度函数（这是怎么找到的）：
$$
P_n(\theta)=\frac{\Gamma(\frac{n}{2})}{\Gamma(\frac{n-1}{2})\sqrt{\pi}}sin^{n-2}\theta.
$$
最终计算点乘的期望巧妙地转换为计算角度的期望：
$$
E(e^{ncos\theta}ncos\theta)=\int_0^\pi e^{ncos\theta}ncos\theta P_n(\theta)d_\theta
$$

$$
E(e^{ncos\theta})=\int_0^\pi e^{ncos\theta}P_n(\theta)d_\theta
$$

结构熵

结构熵考虑的是two-hop邻居。

根据邻接矩阵的特点，两跳邻居便可以通过 $A^2=A^TA$ 来进行刻画。进一步得到能够描述度信息的向量 $D_r$：
$$
D_r=D^TA_r^2, \quad A_r^2[i,j]=\frac{A^2[i,j]}{\sum_jA^2[i,j]}
$$
从而有：
$$
H_s=-\sum_i^NP_ilogP_i=-\sum_i\frac{D_r[i]}{\sum_iD_r[i]}log(\frac{D_r[i]}{\sum_iD_r[i]}),
$$
有一些问题：

• 邻接矩阵平方后得到的是二跳邻居的连接信息，此时没有一跳邻居的信息。
• $D_r$ 的意义解释是什么。

总结来看

最终我们目标为求解 $H_g=0$ 时候的 $n$。
$$
H_{g}=H_f+\lambda H_s =logN^2+log\int_0^\pi e^{ncos\theta}P_n(\theta)d_\theta - \frac{\int_0^\pi e^{ncos\theta}ncos\theta P_n(\theta)d_\theta}{\int_0^\pi e^{ncos\theta}P_n(\theta)d_\theta}
-\lambda\sum_{i}\frac{D_{r}[i]}{\sum_{i}D_{r}[i]}log(\frac{D_{r}[i]}{\sum_{i}D_{r}[i]})
$$
整体过程也比较清晰，重复：设计的是算法，不是模型：

能否将其结合到图网络中，形成端到端的模型？

实验设置与结果

文中进行了节点分类与链路预测任务。从结果上看，在算法得到的维度数量上的实验结果，为最优或接近最优的效果，证明了有效性。

这段话也表现了此方法的优越性：

另外文中还分析了时间复杂度等问题，说明了其在时间上的消耗是可接受的。