Subgraph recognition aims at discovering a compressed substructure of a graph
that is most informative to the graph property. It can be formulated by
optimizing Graph Information Bottleneck (GIB) with a mutual information
estimator. However, GIB suffers from training instability and degenerated
results due to its intrinsic optimization process. To tackle these issues, we
reformulate the subgraph recognition problem into two steps: graph perturbation
and subgraph selection, leading to a novel Variational Graph Information
Bottleneck (VGIB) framework. VGIB first employs the noise injection to modulate
the information flow from the input graph to the perturbed graph. Then, the
perturbed graph is encouraged to be informative to the graph property. VGIB
further obtains the desired subgraph by filtering out the noise in the
perturbed graph. With the customized noise prior for each input, the VGIB
objective is endowed with a tractable variational upper bound, leading to a
superior empirical performance as well as theoretical properties. Extensive
experiments on graph interpretation, explainability of Graph Neural Networks,
and graph classification show that VGIB finds better subgraphs than existing
methods. Code is avaliable at this https URL

该研究提出了一种名为 Variational Graph Information Bottleneck (VGIB) 的框架，用于识别图形中最具信息量的压缩子结构，VGIB 通过对图形施加噪声注入的方式，再通过过滤噪声来获得所需的子图，并在图解释、图神经网络的可解释性和图分类等方面进行了广泛实验。

利用变分图信息瓶颈改进子图识别

Improving Subgraph Recognition with Variational Graph Information  Bottleneck

Given the input graph and its label/property, several key problems of graph
learning, such as finding interpretable subgraphs, graph denoising and graph
compression, can be attributed to the fundamental problem of recognizing a
subgraph of the original one. This subgraph shall be as informative as
possible, yet contains less redundant and noisy structure. This problem setting
is closely related to the well-known information bottleneck (IB) principle,
which, however, has less been studied for the irregular graph data and graph
neural networks (GNNs). In this paper, we propose a framework of Graph
Information Bottleneck (GIB) for the subgraph recognition problem in deep graph
learning. Under this framework, one can recognize the maximally informative yet
compressive subgraph, named IB-subgraph. However, the GIB objective is
notoriously hard to optimize, mostly due to the intractability of the mutual
information of irregular graph data and the unstable optimization process. In
order to tackle these challenges, we propose: i) a GIB objective based-on a
mutual information estimator for the irregular graph data; ii) a bi-level
optimization scheme to maximize the GIB objective; iii) a connectivity loss to
stabilize the optimization process. We evaluate the properties of the
IB-subgraph in three application scenarios: improvement of graph
classification, graph interpretation and graph denoising. Extensive experiments
demonstrate that the information-theoretic IB-subgraph enjoys superior graph
properties.

本文提出了图信息瓶颈（GIB）框架，解决了深度图学习中子图识别问题，并在三种应用场景下评估 IB 子图的性能。