《Edge Entropy as an Indicator of the Effectiveness of GNNs over CNNs for Node Classification》论文解读

论文传送门：click here

论文动机

这是CMU在2021 Asilomar Conference上的一篇工作。

GNN与CNN的区别在于，GNN引入了图的结构信息。从实验结果来看，有效的图结构训练结果要远好于简单的单位阵或随机矩阵当做图结构的结果：

那么结构信息对GNN有了什么样的帮助呢，这篇文章基于此提出两个问题：

• 如何评估图结构对GNN的有效性？
• 如何评估图结构的有效性？

本文以边缘熵的思想来对如上问题进行解答。

方法论

直观而言

• (a) 每一个团都只有一类，那么知道其邻居的颜色自身颜色就知道了。但是 (b) 不行
• intra-class ration能够代表一定信息，如 (c) 邻居与本身类别一致比例是0，能够提供信息
• clustering coefficient能够作为一个指标，比如 (d) 完全图的聚类系数为1，基本不提供信息

如何找到一个通用的评判方法？——Edge Entropy。

Edge Entropy

设图 $G$ 有 $M$ 类别，对于任意类别 $l$ 当前类别的熵为：

计算方式如下：
$$
H(l):=-\sum_{m\in\{1,\dots,M\}}p_{lm}(n)\log_M(p_{lm}(n))
$$
其中：
$$
p_{lm}:=\frac{|{\text{edge }w:\text{start}(w)\in\mathcal V_l\wedge\text{end}(w)\in\mathcal V_m}|}{|{\text{edge }w:\text{start}(w)\in\mathcal V_l}|}
$$
最终整个图的Edge Entropy就可以计算为：
$$
\hat H=-\sum_{m\in\{1,\dots,M\}} H(m)w_m
$$
$w_m$ 就是第 $m$ 类节点个数的占比。

接下来就是实验部分——这个特征如何刻画efficiency。

实验设置与结果

在自建图上的实验

文章生成具有特定边缘熵的合成数据集。$r_i$ 代表第 $i$ 类节点数量，同时有 $\sum r_i=N$。

为了具有特定的边缘熵，生成的连通图必须在每个类的节点之间有一定数量的边。通过创建一个具有所需边缘熵的 $M \times M$ 矩阵 $T$，其中 $T_{i,j}$ 是将类 $i$ 节点连接到类 $j$ 节点的边数。我们对 $T$ 的每一行进行归一化以产生概率矩阵 $P$ （实际上每一元素就是 $p_{l,m}$）。同时设置了一个变量 $\rho$。

具体图构建方法为：从 $N$ 个孤立节点开始。每个节点都有一个自循环和随机特征。根据类 $r_i$ 的节点分布，为每个节点分配一个标签。然后我们考虑每对节点 $v_i, v_j$ ，对于每对节点，我们以 $\rho P_{l,m}$ 的概率从 $v_i$ 到 $v_j$ 创建一个有向边，其中 $l$ 是 $v_i$ 的类，$m$ 是 $v_j$ 的类。

设置参数 $N=3000,M=300,r_1=r_2=r_3=1/3,\rho_1=0.1,\rho_2=0.5$，同时设置低熵 $\hat H_{low} \approx 0.52$ 和高熵 $\hat H_{low} \approx 0.97$ 对应的概率矩阵：
$$
P_{\text{low}}=\begin{bmatrix}0.8&0.05&0.15\\0.05&0.9&0.05\\0.27&0.03&0.7\end{bmatrix}, P_{\text{high}}=\begin{bmatrix}0.4&0.26&0.34\\0.2&0.5&0.3\\0.33&0.31&0.37\end{bmatrix}
$$
简单来说：$\rho$ 代表在相对比率不变的情况下控制边生成的比例，$P$ 控制边的相对生成比例。

根据如上参数构建四个数据集：

• dense_low：$\rho_2,P_{low}$
• sparse_low：$\rho_1,P_{low}$
• dense_high：$\rho_2,P_{high}$
• sparse_high：$\rho_1,P_{high}$

实验结果为：

即低熵更好。（为什么不对dense和sparse再进行一下对比）

此外坐着还用了一些真实的数据集来证明这个结论，这里不做展示。

核心就是，Edge Entropy能够代表图结构的作用，并且结论是低熵better。

一些想法

从边缘上进行熵的计算是一种不错的思路。与经典的图熵不同，边缘能够考虑相邻两个节点的关系以及本身的结构关系，是一种更加合理的结构原子（一个点的度终究核心还是一个节点，结构信息可能不够全面）。

整篇论文读下来感觉很有道理，但仔细想想似乎也没有什么意料之外的内容，毕竟我们很容易有意识到边的链接以及图的复杂性会影响GNN表现能力。

但是能够借鉴的，或许可以通过label计算出当前边缘的分布概率，换句话来说可以从大的结构上来计算某一区域structure的分布，计算熵（这才是我觉得合理的结构熵，而非还是着眼于小的点）。

此外根据label计算structure能够有效的将feature与structure进行结合，更加对图结构的信息进行统一刻画。