The emergence of Graph Convolutional Network (GCN) has greatly boosted the
progress of graph learning. However, two disturbing factors, noise and
redundancy in graph data, and lack of interpretation for prediction results,
impede further development of GCN. One solution is to recognize a predictive
yet compressed subgraph to get rid of the noise and redundancy and obtain the
interpretable part of the graph. This setting of subgraph is similar to the
information bottleneck (IB) principle, which is less studied on
graph-structured data and GCN. Inspired by the IB principle, we propose a novel
subgraph information bottleneck (SIB) framework to recognize such subgraphs,
named IB-subgraph. However, the intractability of mutual information and the
discrete nature of graph data makes the objective of SIB notoriously hard to
optimize. To this end, we introduce a bilevel optimization scheme coupled with
a mutual information estimator for irregular graphs. Moreover, we propose a
continuous relaxation for subgraph selection with a connectivity loss for
stabilization. We further theoretically prove the error bound of our estimation
scheme for mutual information and the noise-invariant nature of IB-subgraph.
Extensive experiments on graph learning and large-scale point cloud tasks
demonstrate the superior property of IB-subgraph.

通过引入信息瓶颈理论的设计，结合相似桥接原理和互信息估计式的互动，提出了一种新型的子图信息瓶颈架构来识别预测压缩的子图，成功去除了图数据中的噪音和冗余，具有高效和稳定性，得到了较好的优化结果和理论边界。