基于最大熵加权独立集池化的图神经网络

本文提出了一种基于最大化池化图与输入图之间互信息的新型图神经网络池化层。由于最大互信息难以直接计算，我们引入图的香农容量（Shannon capacity）作为归纳偏置，以指导我们的池化方法。具体而言，我们表明池化层的输入图可被视作一个噪声通信信道的表示。在该信道中，通过独立集（independent set）中的符号进行传输，能够实现可靠且无误差的信息传递。我们进一步证明，达到最大互信息等价于在图中寻找一个带权最大独立集，其中权重反映了熵信息的含量。从信息论的视角出发，本文为图池化问题提供了全新的建模思路：即将其视为在噪声通信信道上最大化信息传输速率的问题，该过程由图神经网络实现。我们将所提出的方法命名为最大熵加权独立集池化（Maximum Entropy Weighted Independent Set Pooling, MEWISPool），并在图分类任务以及最大独立集这一组合优化问题上进行了评估。实验结果表明，该方法在多个基准数据集上的图分类任务和最大独立集问题中均取得了当前最优或具有竞争力的性能表现。