GRAPH INFORMATION BOTTLENECK FOR SUBGRAPH RECOGNITION
Year: 2021

Abstract:
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 IBsubgraph. 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.

heading: 1 INTRODUCTION
text: Classifying the underlying labels or properties of graphs is a fundamental problem in deep graph learning with applications across many fields, such as biochemistry and social network analysis. However, real world graphs are likely to contain redundant even noisy information (Franceschi et al., 2019; Yu et al., 2019), which poses a huge negative impact for graph classification. This triggers an interesting problem of recognizing an informative yet compressed subgraph from the original graph. For example, in drug discovery, when viewing molecules as graphs with atoms as nodes and chemical bonds as edges, biochemists are interested in identifying the subgraphs that mostly represent certain properties of the molecules, namely the functional groups (Jin et al., 2020b; Gilmer et al., 2017). In graph representation learning, the predictive subgraph highlights the vital substructure for graph classification, and provides an alternative way for yielding graph representation besides mean/sum aggregation (Kipf & Welling, 2017; Velickovic et al., 2017; Xu et al., 2019) and pooling aggregation (Ying et al., 2018; Lee et al., 2019; Bianchi et al., 2020). In graph attack and defense, it is vital to purify a perturbed graph and mine the robust structures for classification (Jin et al., 2020a).
Recently, the mechanism of self-attentive aggregation (Li et al., 2019) somehow discovers a vital substructure at node level with a well-selected threshold. However, this method only identifies isolated important nodes but ignores the topological information at subgraph level. Consequently, it ∗This work was done when Junchi Yu was a research intern at Tencent AI LAB. †Corresponding Author
leads to a novel challenge as subgraph recognition: How can we recognize a compressed subgraph with minimum information loss in terms of predicting the graph labels/properties?
Recalling the above challenge, there is a similar problem setting in information theory called information bottleneck (IB) principle (Tishby et al., 1999), which aims to juice out a compressed data from the original data that keeps most predictive information of labels or properties. Enhanced with deep learning, IB can learn informative representation from regular data in the fields of computer vision (Peng et al., 2019; Alemi et al., 2017; Luo et al., 2019), reinforcement learning (Goyal et al., 2019; Igl et al., 2019) and natural language precessing (Wang et al., 2020). However, current IB methods, like VIB (Alemi et al., 2017), is still incapable for irregular graph data. It is still challenging for IB to compress irregular graph data, like a subgraph from an original graph, with a minimum information loss.
Hence, we advance the IB principle for irregular graph data to resolve the proposed subgraph recognition problem, which leads to a novel principle, Graph Information Bottleneck (GIB). Different from prior researches in IB that aims to learn an optimal representation of the input data in the hidden space, GIB directly reveals the vital substructure in the subgraph level. We first i) leverage the mutual information estimator from Deep Variational Information Bottleneck (VIB) (Alemi et al., 2017) for irregular graph data as the GIB objective. However, VIB is intractable to compute the mutual information without knowing the distribution forms, especially on graph data. To tackle this issue, ii) we adopt a bi-level optimization scheme to maximize the GIB objective. Meanwhile, the continuous relaxation that we adopt to approach the discrete selection of subgraph will lead to unstable optimization process. To further stabilize the training process and encourage a compact subgraph, iii) we propose a novel connectivity loss to assist GIB to effectively discover the maximally informative but compressed subgraph, which is defined as IB-subgraph. By optimizing the above GIB objective and connectivity loss, one can recognize the IB-subgraph without any explicit subgraph annotation. On the other hand, iv) GIB is model-agnostic and can be easily plugged into various Graph Neural Networks (GNNs).
We evaluate the properties of the IB-subgraph in three application scenarios: improvement of graph classification, graph interpretation, and graph denoising. Extensive experiments on both synthetic and real world datasets demonstrate that the information-theoretic IB-subgraph enjoys superior graph properties compared to the subgraphs found by SOTA baselines.

heading: 2 RELATED WORK
text: Graph Classification. In recent literature, there is a surge of interest in adopting graph neural networks (GNN) in graph classification. The core idea is to aggregate all the node information for graph representation. A typical implementation is the mean/sum aggregation (Kipf & Welling, 2017; Xu et al., 2019), which is to average or sum up the node embeddings. An alternative way is to leverage the hierarchical structure of graphs, which leads to the pooling aggregation (Ying et al., 2018; Zhang et al., 2018; Lee et al., 2019; Bianchi et al., 2020). When tackling with the redundant and noisy graphs, these approaches will likely to result in sub-optimal graph representation. Recently, InfoGraph (Sun et al., 2019) maximize the mutual information between graph representations and multi-level local representations to obtain more informative global representations.
Information Bottleneck. Information bottleneck (IB), originally proposed for signal processing, attempts to find a short code of the input signal but preserve maximum information of the code (Tishby et al., 1999). (Alemi et al., 2017) firstly bridges the gap between IB and the deep learning, and proposed variational information bottleneck (VIB). Nowadays, IB and VIB have been wildly employed in computer vision (Peng et al., 2019; Luo et al., 2019), reinforcement learning (Goyal et al., 2019; Igl et al., 2019), natural language processing (Wang et al., 2020) and speech and acoustics (Qian et al., 2020) due to the capability of learning compact and meaningful representations. However, IB is less researched on irregular graphs due to the intractability of mutual information.
Subgraph Discovery. Traditional subgraph discovery includes dense subgraph discovery and frequent subgraph mining. Dense subgraph discovery aims to find the subgraph with the highest density (e.g. the number of edges over the number of nodes (Fang et al., 2019; Gionis & Tsourakakis, 2015)). Frequent subgraph mining is to look for the most common substructure among graphs (Yan & Yan, 2002; Ketkar et al., 2005; Zaki, 2005). At node-level, researchers discover the vital substructure
via the attention mechanism (Velickovic et al., 2017; Lee et al., 2019; Knyazev et al., 2019). Ying et al. (2019) further identifies the important computational graph for node classification. Alsentzer et al. (2020) discovers subgraph representations with specific topology given subgraph-level annotation. Recently, it is popular to select a neighborhood subgraph of a central node to do message passing in node representation learning. DropEdge (Rong et al., 2020) relieves the over-smoothing phenomenon in deep GCNs by randomly dropping a portion of edges in graph data. Similar to DropEdge, DropNode (Chen et al., 2018; Hamilton et al., 2017; Huang et al., 2018) principle is also widely adopted in node representation learning. FastGCN (Chen et al., 2018) and ASGCN (Huang et al., 2018) accelerate GCN training via node sampling. GraphSAGE (Hamilton et al., 2017) leverages neighborhood sampling for inductive node representation learning. NeuralSparse (Zheng et al., 2020) select Top-K (K is a hyper-parameter) task-relevant 1-hop neighbors of a central node for robust node classification. Similarly, researchers discover the vital substructure at node level via the attention mechanism (Velickovic et al., 2017; Lee et al., 2019; Knyazev et al., 2019).

heading: 3 NOTATIONS AND PRELIMINARIES
text: Let {(G1, Y1), . . . , (GN , YN )} be a set of N graphs with their real value properties or categories, where Gn refers to the n-th graph and Yn refers to the corresponding properties or labels. We denote by Gn = (V,E,A,X) the n-th graph of size Mn with node set V = {Vi|i = 1, . . . ,Mn}, edge set E = {(Vi, Vj)|i > j;Vi, Vj is connected}, adjacent matrix A ∈ {0, 1}Mn×Mn , and feature matrix X ∈ RMn×d of V with d dimensions, respectively. Denote the neighborhood of Vi as N (Vi) = {Vj |(Vi, Vj) ∈ E}. We use Gsub as a specific subgraph and Gsub as the complementary structure of Gsub in G. Let f : G → R/[0, 1, · · · , n] be the mapping from graphs to the real value property or category, Y , G is the domain of the input graphs. I(X,Y ) refers to the Shannon mutual information of two random variables.

heading: 3.1 GRAPH CONVOLUTIONAL NETWORK
text: Graph convolutional network (GCN) is widely adopted to graph classification. Given a graph G = (V,E) with node feature X and adjacent matrix A, GCN outputs the node embeddings X ′ from the following process:
X ′ = GCN(A,X;W ) = ReLU(D− 1 2 ÂD− 1 2XW ), (1)
where D refers to the diagonal matrix with nodes’ degrees and W refers to the model parameters.
One can simply sum up the node embeddings to get a fixed length graph embeddings (Xu et al., 2019). Recently, researchers attempt to exploit hierarchical structure of graphs, which leads to various graph pooling methods (Li et al., 2019; Gao & Ji, 2019; Lee et al., 2019; Diehl, 2019; Zhang et al., 2018; Ranjan et al., 2020; Ying et al., 2018). Li et al. (2019) enhances the graph pooling with self-attention mechanism to leverage the importance of different nodes contributing to the results. Finally, the graph embedding is obtained by multiplying the node embeddings with the normalized attention scores:
E = Att(X ′ ) = softmax(Φ2tanh(Φ1X ′T ))X ′ , (2)
where Φ1 and Φ2 refers to the model parameters of self-attention.

heading: 3.2 OPTIMIZING INFORMATION BOTTLENECK OBJECTIVE
text: Given the input signal X and the label Y , the objective of IB is maximized to find the the internal code Z: maxZ I(Z, Y )− βI(X,Z), where β refers to a hyper-parameter trading off informativeness and compression. Optimizing this objective will lead to a compact but informative Z. Alemi et al. (2017) optimize a tractable lower bound of the IB objective:
LV IB = 1
N ∑N i=1 ∫ p(z|xi) log qφ(yi|z)dz − βKL(p(z|xi)|r(z)), (3)
where qφ(yi|z) is the variational approximation to pφ(yi|z) and r(z) is the prior distribution of Z. However, it is hard to estimate the mutual information in high dimensional space when the distribution forms are inaccessible, especially for irregular graph data.

heading: 4 OPTIMIZING THE GRAPH INFORMATION BOTTLENECK OBJECTIVE FOR SUBGRAPH RECOGNITION
text: In this section, we will elaborate the proposed method in details. We first formally define the graph information bottleneck and IB-subgraph. Then, we introduce a novel framework for GIB to effectively find the IB-subgraph. We further propose a bi-level optimization scheme and a graph mutual information estimator for GIB optimization. Moreover, we do a continuous relaxation to the generation of subgraph, and propose a novel loss to stabilize the training process.

heading: 4.1 GRAPH INFORMATION BOTTLENECK
text: We generalize the information bottleneck principle to learn an informative representation of irregular graphs, which leads to the graph information bottleneck (GIB) principle. Definition 4.1 (Graph Information Bottleneck). Given a graph G and its label Y , the GIB seeks for the most informative yet compressed representation Z by optimizing the following objective:
max Z I(Y,Z) s.t. I(G, Z) ≤ Ic. (4)
where Ic is the information constraint between G and Z. By introducing a Lagrange multiplier β to Eq. 4, we reach its unconstrained form:
max Z I(Y, Z)− βI(G, Z). (5)
Eq. 5 gives a general formulation of GIB. Here, in subgraph recognition, we focus on a subgraph which is compressed with minimum information loss in terms of graph properties. Definition 4.2 (IB-subgraph). For a graph G, its maximally informative yet compressed subgraph, namely IB-subgraph can be obtained by optimizing the following objective:
max Gsub∈Gsub I(Y,Gsub)− βI(G,Gsub). (6)
where Gsub indicates the set of all subgraphs of G.
IB-subgraph enjoys various pleasant properties and can be applied to multiple graph learning tasks such as improvement of graph classification, graph interpretation, and graph denoising. However, the GIB objective in Eq. 6 is notoriously hard to optimize due to the intractability of mutual information and the discrete nature of irregular graph data. We then introduce approaches on how to optimize such objective and derive the IB-subgraph.

heading: 4.2 BI-LEVEL OPTIMIZATION FOR THE GIB OBJECTIVE
text: The GIB objective in Eq. 6 consists of two parts. We examine the first term I(Y,Gsub) in Eq. 6, first. This term measures the relevance between Gsub and Y . We expand I(Y,Gsub) as:
I(Y,Gsub) = ∫ p(y,Gsub) log p(y|Gsub)dy dGsub + H(Y ). (7)
H(Y ) is the entropy of Y and thus can be ignored. In practice, we approximate p(y,Gsub) with an empirical distribution p(y,Gsub) ≈ 1N ∑N i=1 δy(yi)δGsub(Gsubi), where δ() is the Dirac function to sample training data. Gsubi and yi are the output subgraph and graph label corresponding to i-th training data. By substituting the true posterior p(y|Gsub) with a variational approximation qφ1(y|Gsub), we obtain a tractable lower bound of the first term in Eq. 6:
I(Y,Gsub) ≥ ∫ p(y,Gsub) log qφ1(y|Gsub)dy dGsub
≈ 1 N N∑ i=1 log qφ1(yi|Gsubi) =: −Lcls(qφ1(y|Gsub), ygt), (8)
where ygt is the ground truth label of the graph. Eq. 8 indicates that maximizing I(Y,Gsub) is achieved by the minimization of the classification loss between Y and Gsub as Lcls. Intuitively, minimizing Lcls encourages the subgraph to be predictive of the graph label. In practice, we choose the cross entropy loss for categorical Y and the mean squared loss for continuous Y , respectively. For more details of deriving Eq. 7 and Eq. 8, please refer to Appendix A.1.
Then, we consider the minimization of I(G,Gsub) which is the second term of Eq. 6. Remind that Alemi et al. (2017) introduces a tractable prior distribution r(Z) in Eq. 3, and thus results in a variational upper bound. However, this setting is troublesome as it is hard to find a reasonable prior distribution for p(Gsub), which is the distribution of graph substructures instead of latent representation. Thus we go for another route. Directly applying the DONSKER-VARADHAN representation (Donsker & Varadhan, 1983) of the KL-divergence, we have:
I(G,Gsub) = sup fφ2 :G×G→R EG,Gsub∈p(G,Gsub)fφ2(G,Gsub)− logEG∈p(G),Gsub∈p(Gsub)e fφ2 (G,Gsub),
(9) where fφ2 is the statistics network that maps from the graph set to the set of real numbers. In order to approximate I(G,Gsub) using Eq. 9, we design a statistics network based on modern GNN architectures as shown by Figure 1: first we use a GNN to extract embeddings from both G and Gsub (parameter shared with the subgraph generator, which will be elaborated in Section 4.3), then concatenate G and Gsub embeddings and feed them into a MLP, which finally produces the real number. In conjunction with the sampling method to approximate p(G,Gsub), p(G) and p(Gsub), we reach the following optimization problem to approximate1 I(G,Gsub):
max φ2
LMI(φ2,Gsub) = 1
N N∑ i=1 fφ2(Gi,Gsubi)− log 1 N N∑ i=1,j 6=i efφ2 (Gi,Gsubj ). (10)
With the approximation to the MI in graph data, we combine Eq. 6 , Eq. 8 and Eq. 10 and formulate the optimization process of GIB as a tractable bi-level optimization problem:
min Gsub,φ1
L(Gsub, φ1, φ∗2) = Lcls(qφ1(y|Gsub), ygt) + βLMI(φ∗2,Gsub) (11)
s.t. φ∗2 = arg max φ2 LMI(φ2,Gsub). (12)
We first derive a sub-optimal φ2 notated as φ∗2 by optimizing Eq. 12 for T steps as inner loops. After the T-step optimization of the inner-loop ends, Eq. 10 is a proxy for MI minimization for the GIB objective as an outer loop. Then, the parameter φ1 and the subgraph Gsub are optimized to yield IB-subgraph. However, in the outer loop, the discrete nature of G and Gsub hinders applying the gradient-based method to optimize the bi-level objective and find the IB-subgraph.
1Notice that the MINE estimator (Belghazi et al., 2018) straightforwardly uses the DONSKERVARADHAN representation to derive an MI estimator between the regular input data and its vectorized representation/encoding. It cannot be applied to estimate the mutual information between G and Gsub since both of G and Gsub are irregular graph data.

heading: 4.3 THE SUBGRAPH GENERATOR AND CONNECTIVITY LOSS
text: To alleviate the discreteness in Eq. 11, we propose the continuous relaxation to the subgraph recognition and propose a loss to stabilize the training process.
Subgraph generator: For the input graph G, we generate its IB-subgraph with the node assignment S which indicates the node is in Gsub or Gsub. Then, we introduce a continuous relaxation to the node assignment with the probability of nodes belonging to the Gsub or Gsub. For example, the i-th row of S is a 2-dimensional vector [p(Vi ∈ Gsub|Vi), p(Vi ∈ Gsub|Vi)]. We first use an l-layer GNN to obtain the node embedding and employ a multi-layer perceptron (MLP) to output S :
X l = GNN(A,X l−1; θ1), S = Softmax(MLP(X l; θ2)). (13)
S is a n × 2 matrix, where n is the number of nodes. We add row-wise Softmax to the output of MLP to ensure the nodes are either in or out of the subgraph. For simplicity, we compile the above modules as the subgraph generator, denoted as g(; θ) with θ := (θ1, θ2). When S is well-learned, the assignment of nodes is supposed to saturate to 0/1. The representation of Gsub, which is employed for predicting the graph label, can be obtained by taking the first row of STX l.
Connectivity loss: However, poor initialization will cause p(Vi ∈ Gsub|Vi) and p(Vi ∈ Gsub|Vi) to be close. This will either lead the model to assign all nodes to Gsub / Gsub, or result that the representations of Gsub contain much information from the redundant nodes. These two scenarios will cause the training process to be unstable. On the other hand, we suppose our model to have an inductive bias to better leverage the topological information while S outputs the subgraph at a node-level. Therefore, we propose the following connectivity loss:
Lcon = ||Norm(STAS)− I2||F , (14)
where Norm(·) is the row-wise normalization, ||·||F is the Frobenius norm, and I2 is a 2×2 identity matrix. Lcon not only leads to distinguishable node assignment, but also encourage the subgraph to be compact. Take (STAS)1: for example, denote a11, a12 the element 1,1 and the element 1,2 of
STAS, a11 = ∑ i,j Aijp(Vi ∈ Gsub|Vi)p(Vj ∈ Gsub|Vj), a12 = ∑ i,j Aijp(Vi ∈ Gsub|Vi)p(Vj ∈ Gsub|Vj). (15) Minimizing Lcon results in a11a11+a12 → 1. This occurs if Vi is in Gsub, the elements of N (Vi) have a high probability in Gsub. Minimizing Lcon also encourages a12a11+a12 → 0. This encourages p(Vi ∈ Gsub|Vi) → 0/1 and less cuts between Gsub and Gsub. This also holds for Gsub when analyzing a21 and a22.
In a word, Lcon encourages distinctive S to stabilize the training process and a compact topology in the subgraph. Therefore, the overall loss is:
min θ,φ1
L(θ, φ1, φ∗2) = Lcls(qφ1(g(G; θ)), ygt) + αLcon(g(G; θ)) + βLMI(φ∗2,Gsub)
s.t. φ∗2 = arg max φ2
LMI(φ2,Gsub). (16)
We provide the pseudo code in the Appendix to better illustrate how to optimize the above objective.

heading: 5 EXPERIMENTS
text: In this section, we evaluate the proposed GIB method on three scenarios, including improvement of graph classification, graph interpretation and graph denoising.

heading: 5.1 BASELINES AND SETTINGS
text: Improvement of graph classification: For improvement of graph classification, GIB generates graph representation by aggregating the subgraph information. We plug GIB into various backbones including GCN (Kipf & Welling, 2017), GAT (Velickovic et al., 2017), GIN (Xu et al., 2019) and GraphSAGE (Hamilton et al., 2017). We compare the proposed method with the mean/sum aggregation (Kipf & Welling, 2017; Velickovic et al., 2017; Hamilton et al., 2017; Xu et al., 2019) and pooling aggregation (Zhang et al., 2018; Ranjan et al., 2020; Ying et al., 2018; Diehl, 2019) in terms of classification accuracy. Moreover, we apply DropEdge (Rong et al., 2020) to GAT, namely GAT+DropEdge, which randomly drop 30% edges in message-passing at node-level. Similarly, we apply GIB to GAT+DropEdge, resulting in GAT+GIB+DropEdge. For fare comparisions, all the backbones for different methods consist of the same 2-layer GNN with 16 hidden-size.
Graph interpretation: The goal of graph interpretation is to find the substructure which shares the most similar property to the molecule. If the substructure is disconnected, we evaluate its largest connected part. We compare GIB with the attention mechanism (Li et al., 2019). That is, we attentively aggregate the node information for graph prediction. The interpretable subgraph is generated by choosing the nodes with top 50% and 70% attention scores, namely Att05 and Att07. GIB outputs the interpretation with the IB-subgraph. Then, we evaluate the absolute property bias (the absolute value of the difference between the property of graph and subgraph) between the graph and its interpretation. Similarly, for fare comparisons, all the backbones for different methods consist of the same 2-layer GNN with 16 hidden-size.
Graph denoising: We translate the permuted graph into the line-graph and use GIB and attention to 1) infer the real structure of graph, 2) classify the permuted graph via the inferred structure. We further compare the performance of GCN and DiffPool on the permuted graphs.

heading: 5.2 DATASETS
text: Improvement of graph classification: We evaluate different methods on the datasets of MUTAG (Rupp et al., 2012), PROTEINS (Borgwardt et al., 2005), IMDB-BINARY and DD (Rossi & Ahmed, 2015) datasets. 2. The statistics of the datasets are available in Table 7 of Appendix.
Graph interpretation: We construct the datasets for graph interpretation on four molecule properties based on ZINC dataset, which contains 250K molecules. QED measures the drug likeness of a molecule, which is bounded within the range (0, 1.0). DRD2 measures the probability that a molecule is active against dopamine type 2 receptor, which is bounded with (0, 1.0). HLM-CLint and MLM-CLint are estimated values of in vitro human and mouse liver microsome metabolic stability (base 10 logrithm of mL/min/g). We sample the molecules with QED ≥ 0.85, DRD2 ≥ 0.50, HLM-CLint ≥ 2, MLM-CLint ≥ 2 for each task. We use 85% of these molecules for training, 5% for validating and 10% for testing. The statistics of the datasets are available in Table 8 of Appendix.
Graph denoising: We generate a synthetic dataset by adding 30% redundant edges for each graph in MUTAG dataset. We use 70% of these graphs for training, 5% for validating and 25% for testing.

heading: 5.3 RESULTS
text: Improvement of Graph Classification: In Table 1, we comprehensively evaluate the proposed method and baselines on improvement of graph classification. We train GIB on various backbones and aggregate the graph representations only from the subgraphs. We compare the performance of our framework with the mean/sum aggregation and pooling aggregation. This shows that GIB improves the graph classification by reducing the redundancies in the graph structure.
Graph interpretation: Table 2 shows the quantitative performance of different methods on the graph interpretation task. GIB is able to generate precise graph interpretation (IB-subgraph), as the substructures found by GIB has the most similar property to the input molecules. In Fig. 2, GIB generates more compact and reason-
able interpretation to the property of molecules confirmed by chemical experts. More results are
2We follow the protocol in https://github.com/rusty1s/pytorch geometric/tree/master/benchmark/kernel
provided in the Appendix. In Table 5, we compare the average number of disconnected substructures per graph since a compact subgraph should preserve more topological information. GIB generates more compact subgraphs to better interpret the graph property. Moreover, compared to the baselines, GIB does not require a hyper-parameter to control the sizes of subgraphs, thus being more adaptive to different tasks. Please refer to Table 9 and Table 10 of Appendix for details. The training dynamic is shown in Fig. 7. We provide results with other MI estimators in Table 11 in Appendix.
Graph denoising: Table 4 shows the performance of different methods on noisy graph classification. GIB outperforms the baselines on classification accuracy by a large margin due to the superior property of IB-subgraph. Moreover, GIB is able to better reveal the real structure of permuted graphs in terms of precision and recall rate of true edges.

heading: 5.4 ABLATION STUDY
text: To further understand the rolls of Lcon and LMI , we derive two variants of our method by deleting Lcon and LMI , namely GIB w/o Lcon and GIB w/o LMI . Note that GIB w/o LMI is similar to InfoGraph (Sun et al., 2019) and GNNExplainer (Ying et al., 2019), as they only consider to maximize MI between latent embedding and global summarization and ignore compression. When adapted to sub graph recognition, it is likely to be G = Gsub. We evaluate the variants with 2-layer GCN and 16 hidden size on graph interpretation. In practice, we find that the training process of GIB w/o Lcon is unstable as discussed in Section 4.3. Moreover, we find that GIB w/o LMI is very likely to output Gsub = G, as it does not consider compression. Therefore, we try several initiations for GIB w/o Lcon and LMI to get the current results. As shown in Table 3, GIB also outperforms the variants, and thus indicates that every part of our model does contribute to the improvement of performance.

heading: 5.5 MORE DISCUSSION ON CONNECTIVITY LOSS
text: Lcon is proposed for stabilizing the training process and resulting in compact subgraphs. As it poses regularization for the subgraph generation, we are interested in its potential influence on the sizes of the chosen IB-subgraph. Therefore, we show the influence of different hyper-parameters of Lcon to the sizes of the chosen IB-subgraph. We implement the experiments with α varies in {1, 3, 5, 10} on QED dataset and compute the mean and standard deviation of the sizes of IB-subgraph (All) and their largest connected parts (Max). As shown in Table 6, we observe that different α result in similar sizes of IB-subgraph. Therefore, its influence on the size of chosen subgraphs is weak.

heading: 6 CONCLUSION
text: In this paper, we have studied a subgraph recognition problem to infer a maximally informative yet compressed subgraph. We define such a subgraph as IB-subgraph and propose the graph information bottleneck (GIB) framework for effectively discovering an IB-subgraph. We derive the GIB objective from a mutual information estimator for irregular graph data, which is optimized by a bi-level learning scheme. A connectivity loss is further used to stabilize the learning process. We evaluate our GIB framework in the improvement of graph classification, graph interpretation and graph denoising. Experimental results verify the superior properties of IB-subgraphs.

heading: ACKNOWLEDGEMENTS
text: This work is partially funded by Beijing Natural Science Foundation (Grant No. JQ18017) and Youth Innovation Promotion Association CAS (Grant No. Y201929).

heading: A APPENDIX
text: A.1 MORE DETAILS ABOUT EQ. 7 AND EQ. 8
Here we provide more details about how to yield Eq. 7 and Eq. 8. I(Y,Gsub) = ∫ p(y,Gsub) log p(y|Gsub)dy dGsub − ∫ p(y,Gsub) log p(y)dy dGsub
= ∫ p(y,Gsub) log p(y|Gsub)dy dGsub + H(Y )
≥ ∫ p(y,Gsub) log qφ1(y|Gsub)dy dGsub + KL(p(y|Gsub)|qφ1(y|Gsub))
≥ ∫ p(y,Gsub) log qφ1(y|Gsub)dy dGsub
≈ 1 N N∑ i=1 qφ1(yi|Gsubi)
= −Lcls(qφ1(y|Gsub), ygt)
(17)
A.2 CASE STUDY
To understand the bi-level objective to MI minimization in Eq. 11, we provide a case study in which we optimize the parameters of distribution to reduce the mutual information between two variables. Consider p(x) = sign(N (0, 1)), p(y|x) = N (y;x, σ2)3. The distribution of Y is:
p(y) = ∫ p(y|x)p(x)dx
= ∑ i p(y|xi)p(xi)
= p(y|x = 1)p(x = 1) + p(y|x = −1)p(x = −1) = 0.5(N (y; 1, σ2) +N (y;−1, σ2))
(18)
We optimize the parameter σ2 to reduce the mutual information between X and Y . For each epoch, we sample 20000 data points from each distribution, denoted as X = {x1, x2, · · · , x20000}, Y = {y1, y2, · · · , y20000}. The inner-step is set to be 150. After the inner optimization ends, the model yields a good mutual information approximator and optimize σ2 to reduce the mutual information by minimizing LMI . We compute the mutual information with the traditional method and compare it with LMI :
I(X,Y ) = ∫ p(x, y) log
p(y|x) p(y) dxdy
≈ 1 20000 20000∑ i=1 log p(yi|xi) p(yi)
(19)
As is shown in Fig .9, the mutual information decreases as LMI descends. The advantage of such bi-level objective to MI minimization in Eq. 11 is that it only requires samples instead of forms of distribution. Moreover, it needs no tractable prior distribution for variational approximation. The drawback is that it needs additional computation in the inner loop.
A.3 ALGORITHM
The algorithm is shown as following:
3We use the toy dataset from https://github.com/mzgubic/MINE
Algorithm 1 Optimizing the graph information bottleneck. Input: Graph G = {A,X}, graph label Y , inner-step T , outer-step N . Output: Subgraph Gsub
1: function GIB(G = {A,X}, Y, T,N ) 2: θ ← θ0, φ1 ← φ01 3: for i = 0→ N do 4: φ2 ← φ02 5: for t = 0→ T do 6: φt+12 ← φt2 + η1∇φt2LMI 7: end for 8: θi+1 ← θi − η2∇θiL(θi, φi1, φT2 ) 9: φi+11 ← φi1 − η2∇φi1L(θ i, φi1, φ T 2 )
10: end for 11: Gsub ← g(G; θN ) 12: return Gsub 13: end function
A.4 MORE RESULTS ON GRAPH INTERPRETATION
In Fig. 4, we show the distribution of absolute bias between the property of graphs and subgraphs. GIB is able to generate such subgraphs with more similar properties to the original graphs.
In Fig. 5, we provide more results of four properties on graph interpretation.
A.5 MORE RESULTS ON NOISY GRAPH CLASSIFICATION
We provide qualitative results on noisy graph classification in Fig. 6.
A.6 DETAILS OF DATASETS
We provide the statistics of datasets in experiments. For graph classification, we evaluate the proposed method on four datasets, including MUTAG, PROTEINS, IMDB-BINARY and DD. The
statistics of these datasets are shown in Table 7 4. For graph interpretation, we preprocess the ZINC dataset and obtain four datasets, namely QED, DRD2, HLM-CLint and MLM-CLint. The details of these datasets are shown in Table 8. The synthetic dataset for graph denoising is basically generated from MUTAG dataset, please refer to Section 5.2 for details.
4The statistics of datasets in graph classification are collected from http://networkrepository.com
A.7 SIZES OF THE CHOSEN SUBGRAPHS IN GRAPH INTERPRETATION
In the graph interpretation task, the hyper-parameter of Lcon, α, is set to be 5 on four datasets. We show the mean and standard deviation of the sizes of subgraphs in percent in Table 9 and Table 10. Note that the sizes of chosen subgraphs mainly depend on task relevant information. For example, as DRD2 measures the probability of being active against dopamine type 2 receptor, it depends on almost the whole structure of a molecule. In contrast, HLM-CLint measures vitro human microsome metabolic stability, which is greatly influenced by small motifs. As shown in Table 9 and Table 10, GCN+GIB can recognize the subgraphs with adaptive sizes on different tasks, leading to better performance. However, in GCN+Att05 and GCN+Att07, the size of subgraphs is explicitly controlled by the hyper-parameter (preserve top 50% or 70 % nodes with the highest attention scores). Therefore, the performances of these methods are limited.
A.8 THE TRAINING DYNAMIC
We show the loss in the training process in Figure. 7.
A.9 IMPLEMENTATION WITH OTHER MUTUAL INFORMATION ESTIMATORS
As shown in (Sun et al., 2019; Nowozin et al., 2016), the f-divergence family can also approximate the mutual information. Here we provide the results of GCN+GIB with Jensen-Shannon Divergence (JSD) and χ2 Divergence (χ2) on graph classification in Table 11. Experiment results show that our model can also employ other mutual information estimators for bilevel optimization.
A.10 INFLUENCE OF INITIALIZATION
As the initialization of our model may potentially influence the final chosen subgraphs, we rerun our model five times on the QED dataset for graph interpretation task. Then, we employ the intersection over union (IoU ) to measure the overlap between the subgraphs in 5 different runs and the results reported in Table 2. Similarly, we compute the IoU between the chosen subgraphs and their largest connected parts separately, which refer to IoUall and IoUmax. We finally report the mean and standard deviation of IoUall, IoUmax on the testing set in Table 12. We notice that different initialization has limited influence on the chosen subgraphs, as all the results of five additional runs have high portions of common nodes with the initial run.

Review summaries:
I think this is a nice paper that successfully used information theoretic objective functions for graph representation learning. The authors leveraged the DONSKER approximation of mutual information for a global information bottleneck loss used on the input-space instead of learned latent-space. To help stabilise optimisation, the authors also use bi-level optimisation with more iterations on the inner $I(G, G_{sub})$ as well as automatic masks learning through their $L_{con}$ loss. The authors also showed many experiments on graph classification, denoising, and interpretation tasks. 

The paper introduces the Graph Information Bottleneck (GIB) which aims to learn the most-informative compressed representation $Z$ given graph $G$ with associated label $Y$. Further, it defines GIB-Subgraph which aims to learn the compressed representation as the subgraph $G_{sub}$ which maximizes the mutual information within the family of subgraphs ${\cal G}_sub$ of $G$. The paper introduces bi-level optimization objective which has the following parts: