  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 https://github.com/Samyu0304/VGIB
