《Residual Entropy-based Graph Generative Algorithms》论文解读

2024-08-18

字数统计: 1.2k | 阅读时长≈ 4 分钟

论文传送门：click here

论文动机

本文是AAMAS 2022中的一篇工作。

本篇文章的核心工作为：设计了一种通过原图构造防御图的算法（非神经网络）。其意义在于通过对原始graph进行加边处理使得其结构信息更加显著，从而帮助模型更好的学习到structure信息。

文章通过1-dimensional structure entropy和2-dimensional structure entropy定义出残差熵（Residual Entropy），这个熵反映了图结构所携带的信息——本文希望最大化这个量。

文章通过残差熵的定义推导出使得残差熵增大的条件，进而根据这个条件对图进行加边处理，旨在提高图的残差熵，从而得到防御图。

我之前看的论文大多是基于1-dimensional structure entropy，在架构上进行大大小小的改动。而这边文章从底层使用了一种不同的度量方法，因此我还是简单总结一下这篇文章的主要内容。

这篇文章中从定义推导方法的过程值得借鉴，尽管我感觉有些不够严谨，但这个思路是能够将一个工作顺下来的。

补：后来发现残差熵这个概念在REM: From Structural Entropy To Community Structure Deception中提出，且部分结论在这里面也有。

方法论

残差熵

先介绍本文提出残差熵用到的两个熵计算方法：

1-dimensional structure entropy: 1-dimensional structure entropy is defined by the average codeword length of all interactions from nodes in $V$。
$$
\mathcal H(G)=-\sum_{v_i\in V}\frac{d_i}{2|E|}\log_2\frac{d_i}{2|E|}
$$
其中 $d_i$ 是节点 $v_i$ 的度，$E$ 是总边数。这个度量方式没有假设任何社区结构。
2-dimensional structure entropy: 2-dimensional structure entropy is defined by the average encode length of all calls with community partition $P$。
$$
\mathcal H_P(G)=\sum_{j=1}^L\left(-\frac{\nu_j}{2|E|}\mathcal H(G|X_j)-\frac{g_j}{2|E|}\log_2\frac{\nu_j}{2|E|}\right)
$$
$P=\{X_1,\dots,X_L\}$ 是对节点的一个分割。 $\mathcal H(G|X_j) = -\sum_{v_i\in X_j} \frac{d_i}{v_j}\log_2\frac{d_i}{v_j}$，$v_i$ 代表第 $i$ 个分割团 $X_i$ 的度之和；$g_i$ 代表只有一个端点在 $X_i$ 内的边数（其实就是连向外面的边数）。这个结构熵反映了一直社区机构后的信息熵。

接下来便可以引出残差熵（已normalized）了：
$$
\rho p:=R_{P}/\mathcal H(G), \quad R_P=\mathcal H(G)-\mathcal H_P(G)=\frac{v_j-g_j}{2|E|}\log_2\frac{v_j}{2|E|}
$$
残差熵表示有关图社区结构的信息量。一个相对高的残差熵表示分区 $P$ 包含更多的信息。