Graph Information Bottleneck for Subgraph Recognition
Authors: Junchi Yu
Tingyang Xu
Yu Rong
Yatao Bian
Junzhou Huang
Ran He
Venue: ICLR 2021 Poster (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 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. 

Published as a conference paper at ICLR 2021
GRAPH INFORMATION BOTTLENECK FOR SUBGRAPH RECOGNITION
Junchi Tun.gya Xu², Yu Rong?, Yatao Bian", Junzhou Huang .ann Hel &NLPR&CRIPA,, Institute of Automation, Chinese Academy of Sciences, China University of Chinese Academy of Sciences, China
Tencent AI LAB, China
*Center for Excellence in Brain Science and Intelligence Technology, CAS, China yu yujunchi20199 98 ac. , en, wanggangguuttene yatao. bi bian@ gmai 1 com, jzhuang@ute edu, rheên pr. i ac.cn
com, yu wong@hotmail. com
ABSTRACT
Given the input graph and its label/property, several key problems of graph learn- ing, such as finding interpretable subgraphs, graph denoising and graph compres- sion, can be attributed to the fundamental problem of recognizing subgraph of the original one. This subgraph shall be as informative as possible, yet contains less redundant and noisy structure. This problem setting 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 unsta- ble optimization process. In order to tackle these challenges, we propose: i) a GIB objective based-on mutual information estimator for the irregular graph data; ii) a bi-level optimization scheme to maximize the GIB objective; iii) connectiv- ity 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 ieformation-theoretiic (B-suagraph enjoys superior graph properties.
INTRODUCTION
Classifying the underlying labels or properties of graphs is 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 chem- ical 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. [018]]Lee et al. 2019 Bianchi et al. 2020). In graph attack and defense, it
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
"Tiis work was done when Junchi Yu was a research intern at Tencent Al LAB.
Corresponding Author

---

Published as a conference paper at ICLR 2021
leads to a novel challenge as subgraph recognition: How can we recognize compressed subgraph with minimum information loss in terms of predicting the graph labels/properties?
Recalling the above challenge, there is similar problem setting in information theory called infor- mation 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 properties. Enhanced with deep learning, IB can learn informative representation from regular data in the fields of computer vision (Peng al. 2019 Alemi al., 2017; Luo al. 2019), reinforcement learning (Goyal al.) 2019 g et al. 2019) and natural language precessing (Wang el al.) 2020). However, current IB methods, like VIB (Alemi et al., 2017), is still incapable for irregular graph data. is still challeng- ing for IB to compress irregular graph data, like a subgraph from an original graph, with minimum information loss.
Hence, we advance the IB principle for irregular graph data to resolve the proposed subgraph recog- nition 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 hid- den 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 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 novel connectivity loss assist GIB effectively discover the maxi- mally 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-theerrtiec IB-subgraph enjoys superior graph properties compared to the subgraphs found by SOTA baselines.
2 RELATED WORK
Graph Classification. In recent literature, there is surge of interest in adopting graph neural net- works (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 (Kipl & Welling 2017 Xu et al. 2019). which is to average or sum up the node embeddings. An alternative way is to lever- age 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 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 al. [019 Igl et al. 2019), natural language processing (Wang et al. (020)) and speech and acous- tics (Qian 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 fre- quent 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
2

---

Published as a conference paper at ICLR 2021
via the attention mechanism (Velickovic et al. 2017 Lee et al., 2019 Knyazev al. 2019) Ying
iet al. (2019) further identifies the important computational graph for node classification. Alsentzer et al. 2020) discovers subgraph representations with specific topology given subgraph-level anno- tation. Recently, it is popular to select a neighborhood subgraph of a central node to do message passing in node representation learning. DropEdge (Rong al. (020) relieves the over-smoothing phenomenon in deep GCNs by randomly dropping a portion of edges in graph data. Similar to DropEdge, DropNooe (Chen al. 2018 Hamilton et al. 2017 Huang al. 2018) principle is also widely adopted in node representation learning. FastGCN (Chen et al. 2018) and ASGCN (Huang al. 2018) accelerate GCN training via node sampling. GraphSAGE (Hamilton et al. 2017) lever- ages neighborhood sampling for inductive node representation learning. NeuralSparse (Zheng et al.) 2020) select Top-K (K hyper-parameter) task-relevant 1-hop neighbors of central node for robust node classification. Similarly, researchers discover the vital substructure at node level via the
attention mechanism (Velickovic et al. 20177 Lee et al. 2019 Knyazev et al., 2019).
NOTATIONS AND PRELIMINARIES
Let {(),, Yi),..., (Gv, YN)} be a set of N graphs with their real value properties or categories, where Gn refers to the n-th graph and Y, refers to the corresponding properties labels. We denote by In = (V,E. A, X) the n-th graph of size M,, with node set V {Vili = 1, 1...., M, J. edge set E {(V,, Vi
j; V2, Vj connected), adjacent matrix A E {0, M0.1),,.M.. and feature matrix X E RRM, xd of V with d dimensions, respectively. Denote the neighborhood of V; as (V)) = (Vg1(V, Vi) E E]. We use Grub as a specific subgraph and Grut as the complementary structure of Goub G. Let f G + R/(0, 1, 1,... n|] be the mapping from graphs to the real value property or category, Y, G is the domain of the input graphs. 1(X, Y) refers to the Shannon mutual information of two random variables.
3.1 GRAPH CONVOLUTIONAL NETWORK
Graph convolutional network (GCN) is widely adopted to graph classification. Given 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, W) ReLU(D AD- XW),
(1)
where D refers to the diagonal matrix with nodes' degrees and W refers the model parameters.
One can simply sum up the node embeddings to get fixed length graph embeddings (Xu et al. 2019). Recently, researchers attempt exploit hierarchical structure of graphs, which leads to various graph pooling methods eLi al.] 2019: Gao Jil 2019 Lee et al., 2019 Dichl 2019 Zhang al. 2018 Ranjan al., 2020 Ying al. 2018). Li 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:
= Att(X')= = softmax( @2tanh( {b X (
where 1 and 4, refers to the model parameters of self-attention.
3.2 OPTIMIZING INFORMATION BOTTLENECK OBJECTIVE
Given the input signal X and the label Y, the objective of IB is maximized to find the the internal code Z: maxz [2, Y) [3( Z), where refers to a ness and compression. Optimizing this objective will lead to compact but informative Z. Alemi et al. (2017) optimize a tractable lower bound of the IB objective:
trading off informative-
1 N LVIB= N m p(zlax) log (zilz)dd (KL(p()())))r())
Σ
(3)
where (v(l)) 22) is the variational approximation to p=())22) and r(2) is the prior distribution of Z. However, hard to estimate the mutual information high dimensional space when the distribution forms inaccessible, especially for irregular graph data.
3

---

Published as a conference paper at ICLR 2021
T-step inner optimization
CMI
Aggregate
LuI
Aggrogate
GNN
q
Select
guu
"ootllnncc""
1.0
L
0.1
MLP
Leon
Iushrahaphh
02
0.1
Outer optimization
Figure 1: Illustration of the proposed graph information bottleneck (GIB) framework. We employ bi-level optimization scheme to optimize the GIB objective and thus yielding the IB-subgraph. In the inner optimization phase, we estimate T(G, snuh) by optimizing the statistics network of the HONSKER-VARADHAL representation (Donsker
Varadhan 1983). Given good estimation of [( rab)), in the outer optimization phase, we maximize the GIB objective by optimizing the mutual information, the classification loss Less and connectivity loss Leon.
4 OPTIMIZING THE GRAPH INFORMATION BOTTLENECK OBJECTIVE FOR SUBGRAPH RECOGNITION
In this section, 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 effec- tively find the IB-subgraph. We further propose bi-level optimization scheme and graph mutual information estimator for GIB optimization. Moreover, we do a continuous relaxation to the gener- ation of subgraph, and propose a novel loss stabilize the training process.
4.1 GRAPH INFORMATION BOTTLENECK
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 graph G and its label Y, the GIB seeks for the most informative yet compressed representation Z by optimizing the following objective:
max I(Y, Z) s.t. I(G, Z) S Ic.
(4)
Z
where Le is the information constraint between G and Z. By introducing Lagrange multiplier / to Eq. we reach its unconstrained form:
max (Y, /I(G,
(5)
Eq. 5 gives general formulation of GIB. Here, in subgraph recognition, we focus subgraph which is compressed with minimum information loss in terms of graph properties.
Definition 4.2 (IB-subgraph). For graph G, its maximally informative yet compressed subgraph, namely IB-subgraph can obtained by optimizing the following objective:
max Geud Guus
I(Y, G - (9,
(6)
where Geub indicates the set of all subgraphs G.
IB-subgraph enjoys various pleasant properties and can be applied multiple graph learning tasks such as improvement 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 infor-
mation and the discrete nature of irregular graph data. We then introduce approaches on how to optimize such objective and derive the IB- (B-subgraph.
4

---

Published as a conference paper at ICLR 2021
4.2 BI-LEVEL OPTIMIZATION FOR THE GIB OBJECTIVE
The GIB objective in Eq. consisss of two parts. We examine the first term I(Y, Genb) in Eq. 6 first. This term measures the relevance between Goub and Y. We expand I(Y, gsub)
I(Y, Goub) = / Grub) log plyl dy su + H(Y).
(Y) is the entropy of Y and thus can be ignored. In practice, we approximate p(y, Goub) with an empirical distribution p(y, (ru6) x 1 to sample training data. Gaud, and yi are the output subgraph and graph label corresponding to
N Ei=1 (y(4)) (Guut where 6() is the Dirac function
i-th training data. By substituting the true posterior p(y (u with a variational approximation do (y]lsub), we obtain tractable lower bound of the first term in Eq. 6
/ p(u, Goub) log to, (1/ GGub)dy dGsub
I(Y, Guub)) 2
(8)
log qo, (Vil9aut.)
=: -Lels (219 Mgt),
where Vgt is the ground truth label of the graph. Eq. 8 indicates that maximizing I(Y, 9sub) is achieved by the minimization of the classification loss between Y and Gsub as Luts- Intuitively, minimizing Cots encourages the subgraph to be predictive of the graph label. In practice, we choose the cross entropy loss for categorical and the mean squared loss for continuous Y, respectively. For more details of deriving Eq. 7 and Eq. (8 please refer to Appendix A.
Then, we consider the minimization of (G, Guub) which is the second term of Eq Remind that Alemi al. (211)) introduces a tractable prior distribution r(2 r(2) in Eq. 3 and thus results in vari- ational 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 representa- tion. Thus we go for another route. Directly applying the HONSKER-VARADHAN representation (Donsker & Varadhan
1983) of the KL-divergenne,, we have:
I(9. Goub)
sup f0g GxG-R
Be....ssp(0 (9, Gaub) log B.E (G.0.))
where loz is the statistics network that maps from the graph set to the set of real numbers. In order to approximate I(G, Goub) using Eq. 9 we design a statistics network based on modern GNN architectures as shown by Figure [ first we use GNN extract embeddings from both and Goub (parameter shared with the subgraph generator, which will be elaborated in Section 4.3), then concatenate G and Goud embeddings and feed them into a MIP, which finally produces the real number. In conjunction with the sampling method to approximate p(G, Goub), p(9) and p(Gsub), we reach the following optimization problem to approximate (G, Goud):
N
N
max
(x2( Goub)
Σ
foz Sonts)
log
(
(10)
N
N
1= 1,5
With the approximation to the MI in graph data, we combine Eq. 6 Eq. g and Eq. and formulate the optimization process of GIB as a tractable bi-level optimization problem:
min
[( Φ1, Φi) Less (u/Gsub), Ugt) + Gaa Goub)
(11)
Gzub.
s.t.
0 = arg max CMI (02, Geut).
(12)
Φ2
We first derive a sub-optimal d2 notated as Φ by optimizing Eq. 12 for T steps as inner loops. After the T-step optimization of the inner-loop ends, Eq. [0 proxy for MI minimization for the GIB objective as an outer loop. Then, the parameter Φi and the subgraph Goub are optimized to yield IB-subgraph. However, in the outer loop, the discrete nature of & and Gous hinders applying the gradient-based method to optimize the bi-level objective and find the IB-subgraph.
Notice that the MINE estimator Belghazi et al. 2018 straightforwardly uses the DONSKER- VARADHAN representation to derive an MI estimator between the regular input data and its vectorized repre- sentation/encodingg It cannot be applied to estimate the mutual information between G and Goub since both of and Goub are irregular graph data.
5

---

Published as a conference paper at ICLR 2021
Table 1: Classification accuracy. The pooling methods yield pooling aggregation while the back- bones yield mean aggregation. The proposed GIB method with backbones yields subgraph embed- ding by aggregating the nodes in subgraphs.
Method
MUTAG
PROTEINS
IMDB-BINARY
DD
SortPool
0.844 + 0.141
0.747
0.044
0.712 0.047
0.732 + 0.087
ASAPool
0.743 + 0.077
0.721 + 0.043
0.715
0.717 = 0.037
DifiPool
0.839 = 0.097
0.727 + 0.046
0.709 0.053
0.778 = 0.030
EdgePool
0.759 + 0.077
0.723 0.044
0.728 + 0.044
0.736 + 0.040
AttPool
0.721 +: 0.086
0.728 + 0.041
0.722 + 0.047
0.711 + 0.055
GCN
0.743
0.719
0.707 = 0.037
0.725 = 0,046
GraphSAGE
0.743+00.07
0.721 0.042
0.709 + 0.041
0.729 + 0.041
GIN
0.825+0.068
0.707 + 0.056
0.732 + 0.048
0.730 0.033
GAT
0.738 + 0.074
0.714
0.713 0.042
0.695 = 0.045
GAT + DropEdge
0.743100081
0.711#0.043
0.710=0.041
0.717=0.035
GCN+GIB
0.776 + 0.075
0.748 0.046
0.722 = 0.039
0.765 = 0.050
GraphSAGE+GID
0,760 + 0.074
0.734 + 0.043
0.719 = 0.052
0.781 + 0.042
GIN+GIB
0.839 + 0.064
0.749 + 0.051
0.737 0.070
0.747 + 0.039
GAT+GIB
0.749 + 0.097
0.737 + 0.044
0.729 = 0.046
0.769 = 0.040
GAT+GIB-DropEdge
0.754
0.737
0.731
0.776100033
Table 2: The mean and standard deviation of absolute property bias between the graphs and the corresponding subgraphs.
Method
QED
DRD2
HLM-CLint
MLM-CLint
GCN+Aut05
0.48 0.07
0,20 0.13
0.90 0.89
0.92= 0.61
GCN+At107
0,41 0.07
0.16
1.18 0.60
1.69 0.88
GCN+GIB
0.38 0.12
0.06 0.09
0.37 0.30
0.72 0.55
4.3 THE SUBGRAPH GENERATOR AND CONNECTIVITY LOSS
To alleviate the discreteness Eq, we propose the continuous relaxation to the subgraph recog- nition 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 Goub Goub. Then, introduce continuous relaxation to the node assignment with the probability nodes belonging to the Gsus or Subb For example, the i-th row of S is 2-dimensional vector [p(V; V,), p(V, s.)l] We first an l-yer GNN to obtain the node embedding and employ a multi-layer perceptron (MLP) to output S
X GNN(A,, x 01), s = =SoftmarMMP((X' 82)).
(13)
S is matrix, where n is the number of nodes. We add row-wise Softmax 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(: 0) with 0 == (2), When S is well-learned, the assignment of nodes is supposed to saturate to 0/1. The representation of Goud, which is employed for predicting the graph label, can be obtained by taking the first row of S'XX! X!.
Connectivity loss: However, poor initialization will cause p(V: Gaus/V) and p(V; E &Sun to be close. This will either lead the model to assign all nodes to Ganb / Guub. 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 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:
Loon | ST AS) I2l[F,
(14)
where Norm(-) is the wise normalization, || is the Frobenius norm, and I, is x 2 identity matrix. Coon not only leads to distinguishable node assignment, but also encourage the subgraph to be compact. Take (ST AS) for example, denote 011, a12 the element 1,1 and the element 1,2 of

---

Published as a conference paper at ICLR 2021
Table 3: Ablation study on foom and Lasr. Note that we try several initiations for GIB w/o Leon and Last to get the current results due to the instability of optimization process.
Method
QED
DRD2
HLM-CLint
MLM-CLint
GIB w/o Lcon
0,46 0.07
0.15 0.12
0,45 0.37
1,58 0.86
GIB w/o LMI
0.43 0.15
0.21 0.13
0.48 0.34
1.20 0.97
GIB
0.38# 0.12
0.06 0.09
0.37 0.30
0.72 0.55
ST AS.
Σ AApp(V E VoVVVV) E Ioub Vsub
= Σ Aup(V E geud VenllV E (enblVy)
411 =
(15)
Minimizing Lcon results in an an15 - 1. This occurs if V is in Gsub, the elements of (V;)) have a high probability in 9sub. Minimizing Ccon also encourages a11+a12 f12_ - O. This encourages
211
p(V E Vi) - 0/1 and less cuts between Gsub and subb- This also holds for aud when analyzing 221 and d22-
In word, feom encourages distinetive S to stabilize the training process and compact topology in the subgraph. Therefore, the overall loss is:
min (10,01 02) = Lota (go, (g(9; 0)), Uot) + aCCon (o(G: + (CMI Gsub) 6,01
(16)
s.t.
2 = arg max LMI (#2, Gubb)-
&2
We provide the pseudo code in the Appendix to better illustrate how to optimize the above objective.
5 EXPERIMENTS
In this section, we evaluate the proposed GIB method on three scenarios, including improvement of graph classification, graph interpretation and graph denoising.
5.1 BASELINES AND SETTINGS
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 ag-
gregation (Kipf & Welling 2017]] Velickovc et al.) 2017: Hamilton et al., 2017 Xu 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, GAT+DropEdge. which randomly drop 30% edges in message- paasssing at neve-level. Similarly, we
apply Drophige (Rong et al. 2020) GAT, namely
apply GIB Gro+eeop resulting in Diropie- 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 al. 2019). That is, we atten- tively aggregate the node information for graph prediction. The interpretable subgraph is generated by choosing the nodes with top 50% and 70% attention scores, namely Au05 and At17. 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 in- terpretation. Similarly, for fare comparisons, all the backbones for different methods consist of the same 2-layer GNN with 16 hidden-size.
and use GIB and attention to !) infer the real structure of graph, 2) classify the permuted graph via the inferred structure. We further compare the performance of GCN and DiftPool on the permuted graphs.
Graph denoising: We translate the permuted graph into the
7

---

Published as a conference paper at ICLR 2021
Table 4: Quantitative results on graph denoising. We report the classification accuracy (Acc), num- ber of real edges over total real edges (Recall) and number of real edges over total edges in subgraphs (Precision) on the test set
Method
GCN
DifiPool
GCN+A105
GCN+Au07
GCN+GIB
Recall
0.226=0.007
0.324 0.049
0.493 0.035 0.692 +0.061
Precision
0.638 0.141
0.675 0.104
Acc
0.617
0.658
0.649
0.667
0.684
HLM-CLint
MLM-CLint
0000000
8 8 gocr
8
2.12
1.90
1.28
2,12
2,06
1,90
1.01
2.18
X
2.55
8x
1.38
2.28
2.34
1,69
-188
2.44
2.35
1.33
1.40
2.27
2.39
0.31
-0.5
2.26
2.03
0.85
2.16
2.97
GCN-MM05
GCN-Am07
GCN+GIB
DON-AM00
GON-A1977
G0.+GB
Figure 2: The molecules with their interpretable subgraphs discovered by different methods. These subgraphs exhibit similar chemical properties compared to the molecules on the left.
5.2 DATASETS
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. The statistics of the datasets are available in Table of Appendix.
Graph interpretation: We construct the datasets for graph interpretation four molecule prop- erties 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 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 sta- bility (base 10 logrithm of ml ml/mm//g) We sample the molecules with QED > 0.85, DRD2 2 0.50, HLM-CLint 2 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 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.
5.3 RESULTS
Improvement of Graph Classification: In Table I comprehensively evaluate the proposed method and baselines on improvement of graph classification. We train GIB on various back- bones and aggregate the graph representations only from the subgraphs. We compare the perfor- mance 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 inter- pretation (IB (IB-subgraph), as the substruc- tures found by GIB has the most similar property to the input molecules. In Fig. 2 GIB generates more compact and reason- able interpretation the property of molecules confirmed by chemical experts. More results
Table 5: Average number of disconnected substruc- tures per graph selected by different methods
Method
QED
DRD2
HLM
MLM
GCN+Au05
3.38
1.94
3.11
5.16
GCN+A107
2.04
1.76
2.75
3.00
GCN+GIB
1.57
1.08
2.29
2.06
We follow the protocol in https://gttuhh.commruusy s/pytorcch gomerficcme/mmatc///cccaae/eeeee
8

---

Published as a conference paper at ICLR 2021
Table 6: The influence of the hyper-parameter a of Lcon to the size of subgraphs.
1
3
10
All Max 0.387=0.173
0.483++0113
0.496++0.155 150
0.444
0.466++0.150
0.413 169
0.411=0.169
0.391=0.172
provided in the Appendix. In Table 5 we compare the average number disconnected substruc- tures per graph since a compact subgraph should preserve more topological information. GIB gen- erates more compact subgraphs to better interpret the graph property. Moreover, compared to the baselines, GIB does require a thyper-paramete adaptive to different tasks. Please refer to Table and Table of Appendix for details. The training dynamic shown Fig. We provide results with other MI estimators in Table 11 Appendix.
control the sizes of subgraphs, thus being more
Table 4 shows the performance of different methods on noisy graph classifica- tion. GIB outperforms the baselines on classification accuracy by a large margin due to the superior property of IB -ubbuggaa.. Moreover, GIB is able to better reveal the real structure of permuted graphs terms of precision and recall rate of true edges.
Graph denoising:
5.4 ABLATION STUDY
To further understand the rolls of Leon and LMS, we derive two variants of our method by deleting Lcon and CMI, namely GIB w/o Loon 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 = Subb We evaluate the variants with 2-layer GCN and 16 hidden size graph interpretation. In practice, we find that the training process of GIB w/o Loon is unstable as discussed in Section 4.3. Moreover, we find that GIB w/o LMI is very likely to output Gsub = G. as does not consider compression. Therefore, we try several initiations for GIB w/o Leon and L 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.
5.5 MORE DISCUSSION ON CONNECTIVITY LOSS
Leon 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-suggraph. Therefore, we show the influence of different typer-parameters of Leon to the sizes of the chosen IB- subsuagra.h. We implement the experiments with a varies {1, 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 we observe that different a result in similar sizes of IB-subgraph. Therefore, its influence on the size of chosen subgraphs is weak.
CONCLUSION
In this paper, we have studied subgraph recognition problem to infer a maximally informative yet compressed subgraph. We define such subgraph as IB-subgraph and propose the graph in- formation bottleneck (GIB) framework for effectively discovering an IB-subgraph. We derive the GIB objective from mutual information estimator for irregular graph data, which optimized by a bi-level learning scheme. A connectivity loss is further used to stabilize the learning process. We evaluate our GIB framework the improvement of graph classification, graph interpretation and graph denoising. Experimental results verify the superior properties of IB- IB-subgraphs.
ACKNOWLEDGGMMENT
This work is partially funded by Beijing Natural Science Foundation (Grant No. JQ18017) and Youth Innovation Promotion Association CAS (Grant No. Y201929).

---

Published as a conference paper at ICLR 2021
REFERENCES
Alexander A. Alemi, Ian Fischer, Joshua V. Dillon, and Kevin Murphy. Deep variational information bottleneck. In The International Conference on Representation Learning. 2017.
Emily Alsentzer, Samuel G Finlayson, Michelle M Li, and Marinka Zitnik. Subgraph neural net- works. arXiv preprint arXiv:2006.10536, 2020.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeswar, Sherjil Ozair, Yoshua Bengio, R. De- von Hjelm, and Aaron C. Courville. Mutual information neural estimation. In International Conference on Machine Learming, volume 80 of Proceedings of Machine Learning Research, pp. 530-539, 2018.
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In Proceedings of the 37th International Conference Machine Learning, 2020.
Karsten M. Borgwardt, Cheng Soon Ong, Stefan Schanauer, S. V. N. Vishwanathan, Alexander J. Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. In ISMB (Supple- ment of Bioinformatics), pp. 47-56, 2005.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv: 1801. 2018.
Frederik Diehl. Edge contraction pooling for graph neural networks. CoRR, abs/1905, 10990, 2019.
M. D. Donsker and S. R. S. Varadhan. Asymptotic evaluation of certain markov process expectations for large time. Communications on Pure and Applied Mathematics, 36(2):183 183-212, 1983.
Yixiang Fang, Kaiqiang Yu, Reynold Cheng, Laks V. S. Lakshmanan, and Xuemin Lin. Efficient algorithms for densest subgraph discovery. Proceedings of VLDB Endowment, 12(11):1719- 1732, 2019.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In ICML, volume 97 Proceedings of Machine Learning Research, pp. 1972-1982. PMLR, 2019.
Hongyang Gao and Shuiwang Ji. Graph u-nets. In ICMI, volume 97 of Proceedings of Machine Learning Research, pp. 2083-2092, PMLR, 2019.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. Proceedings of the 34th International Conference Machine Learning, 70:1263-1272, 2017.
Aristides Gionis and Charalampos E. Tsourakakis. Dense subgraph discovery: Kdd 2015 tutorial.
In Knowledge Discovery and Data Mining, pp. 2313-2314, ACM, 2015.
Anirudh Goyal, Riashat Islam, Daniel Strouse, Zafarali Ahmed, Matthew Botvinick, Hugo Larochelle, Yoshua Bengio, and Sergey Levine. Infobot: Transfer and exploration via the in- formation bottleneck. In The International Conference Representation Learning, 2019.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pp- 1024-1034, 2017.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. arXiv preprint arXiv: 11t.::53800003333.. 2018.
Maximilian Igl, Kamil Ciosek, Yingzhen Li, Sebastian Tschiatschek, Cheng Zhang, Sam Devlin, and Katja Hofmann. Generalization in reinforcement learning with selective noise injection and information bottleneck. In Advances in neural information processing systems, 2019.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. CoRR, abs/2005. 10203, 2020a.
10

---

Published as a conference paper at ICLR 2021
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Multi-ojjective molecule generation using interpretable substructures. In International Conference on Machine Learning, 2020b.
Nikhil Ketkar, Lawrence Bruce Holder, and Diane Cook. Subdue: compression-aase frequent
pattern discovery in graph data. In Knowledge Discovery and Data Mining, 2005.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In The International Conference on Representation Learning, 2017.
Boris Knyazev, Graham W. Taylor, and Mohamed R. Amer. Understanding attention and general- ization in graph neural networks. In NewrlPS, pp. 4204-4214, 2019.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Jia Li, Yu Rong, Hong Cheng, Helen Meng, Wenbing Huang, and Junzhou Huang. Semi-supervised graph classification: A hierarchical graph perspective. In The World Wide Wed Conference, 2019.
Yawei Luo, Ping Liu, Tao Guan, Junqing Yu, and Yi Yang. Significance-aware information bottle- neck for domain adaptive semantic segmentation. In ICCV, pp. 6777-6786. IEEE, 2019.
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: Training generative neural samplers using variational divergence minimization. In NeurIPS, 2016.
XueBin Peng, Angjoo Kanazawa, Sam Toyer, Pieter Abbeel, and Sergey Levine. Variational dis- criminator bottleneck: Improving imitation learning, inverse rl, and gans by constraining infor- mation flow. In The International Conference Representation Learning, 2019.
Kaizhi Qian, Yang Zhang, Shiyu Chang. David Cox, and Mark Hasegawa-Johnson. Unsupervised
speech decomposition via triple information bottleneck, In Proceedings of the 37th International Conference Machine Learning, 2020.
Ekagra Ranjan, Soumya Sanyal, and Partha Pratim Talukdar. Asap: Adaptive structure aware pool- ing for learning hierarchical graph representations. AAAI, 2020.
Yu Rong, Wenbing Huang. Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph
convolutional networks node classification. In International Conference Learning Repre- sentations, 2020. URL https: /ttpfittsss//ppeereiieieeeeeeeee
net
Ryan Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015.
Matthias Rupp, Alexandre Tkatchenko, Klaus-Robert Muller, and O. Anatole von Lilienfeld. Fast and accurate modeling of molecular atomization energies with machine learning. Phys. Rev. Lett., 108(5):058301, January 2012.
Fan-Yun Yun Sun, Jordan Hoffman, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization. Interna- tional Conference on Learning Representations, 2019.
Naftali Tishby, Fernando C. Pereira, and William Bialek. The information bottleneck method. In Proceedings of the 37-th Annual Allerton Conference on Communication, Control and Comput- ing, pp. 368-377, 1999.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lia, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representation, 2017.
Rundong Wang. Xu He. Runsheng Yu, Wei Qiu, Bo An, and Zinovi Rabinovich. Learning efficient multi-agent communication: An information bottleneck approach. In Proceedings of the 37th International Conference Machine Learning, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks? In Proceedings of the 7th International Conference on Learning Representations, ICLR 19, pp. 1-17, 2019.
11

---

Published as a conference paper at ICLR 2021
Xifeng Yan and Jiawei Yan. gspan: graph-based substructure pattern mining. In IEEE International Conference on Data Mining, pp. 721-724, 2002.
Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in neural information processing systems, 2018.
Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Gen- erating explanations for graph neural networks. Advances neural information processing systems, 2019.
Donghan Yu, Ruohong Zhang, Zhengbao Jiang, Yuexin Wu, and Yiming Yang. convolutional network. CoRR, abs/1911.07123, 2019.
Graph-revised
Mohammed Javeed Zaki. Efficiently mining frequent embedded unordered trees. Fundamenta Information, 66( 66(1-2):33-5, 2005.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirly-Second AAAI Conference on Artificial Intelligence, 2018
Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In International Conference on Machine Learning, pp. 11458-1 1468. PMLR, 2020.
12

---

Published as a conference paper at ICLR 2021
A
APPENDIX
A.1 MORE DETAILS ABOUT EQ. 7
AND EQ.
8
Here we provide more details about how to yield Eq. 7 and Eq.
/ ply. Goud) log poglll) dy dgeub / p(y. Goub) log ply)dy dg
(sub)
/ ply, Gmub) log (wub) dy dg + H(Y)
/ plu, Guub) log qo, (y19sub)dy dg + (T.(p(yl9swo) (u()))))
(17)
/ ply, Gentt log qo
dg
N
4s (Hil9sub,)
Lets (or (y19sub), Mgt)
A.2 CASE STUDY
To understand the bi-level objective to MI minimization in Eq. II we provide a case study which we optimize the parameters of distribution to reduce the mutual information between two variables. Consider p(x) = (N0 1)). =N x, 2-5 The distribution of Y is:
p(y) / plulz)p(z)dz
Σ r(llla)p(a))
(18)
plula = - 1)) 0.5(N + o
We optimize the parameter o² to reduce the mutual information between X and Y. For each epoch, we sample 20000 data points from each distribution, denoted as X {z1 [2, ... 220000 ) {y1, 32,- 320000 }. The inner-step is set to be 150. After the inner optimization ends, the model yields a good mutual information approximator and optimize x² reduce the mutual information by minimizing LMI- We compute the mutual information with the traditional method and compare with Lar:
I(X,Y) fDL v) log p(u(z) p(v)
p(x,
drdy
(19)
log p(u x:)
20000
p(v:)
As is shown in Fig the mutual information decreases Lasr descends. The advantage of such bi-level objective to MI minimization in Eq. T1 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:
We the toy dataset from http://ggiaaa.ccmmmmngubiiMin
13

---

Published as a conference paper at ICLR 2021
0.5
0.4
Mutual
0.3
0.2
10
20
30
40
50
60
Epochs
Figure 3: We use the bi-level objective to minimize the mutual information of two distributions. The MI is consistent with the loss as Zas declines.
Algorithm Optimizing the graph information bottleneck.
Input: Graph = {A, X ), graph label Y, inner-step T, outer-step N.
Output: Subgraph Guub
function GIB(C (A, X..YYTT,N
2:
- 00 01 f Φ
3:
for i = N do
4:
Φ2 + σ
5:
for t 1+1 t Φ + 111 V of CrI
> do
6:
7:
end for
8:
Bi+1 (- 8r 122 V L( $1 03)
9:
si+1 of
n2 #; L 0f 05)
end for
11: Goud g(9; ON)
return Ssub
13:
end function
A.4 MORE RESULTS ON GRAPH INTERPRETATION
In Fig. 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. 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 pro- posed method four datasets, including MUTAG, PROTEINS, IMDB-BINARY and DD. The
14

---

Published as a conference paper at ICLR 2021
Clrrs
Oura
AB:07
250
AZD
200
number
150
100
100
50-
HUM-clint
MLM.clint
400
A1105
Anos
A1D7
AUO7
500
300
600
namber
150
200
50
bies
Figure 4: The histgram of absolute bias between the property of graphs and subgraphs.
0.912
D.911
0.987
2.24
2,56
09188
0.81
0.929
0.964
2,17
222
227
243
0.999
2.28
0.901
2664
0.856
0.819
0.960
0.999
2.35
2,27
2.35
2.18
QED
DRDZ
HLMM-Lint
MLM-CLime
Figure 5: The molecules with its interpretation found by GIB. These subgraphs exhibit similar chemical properties compared to the molecules the left.
statistics of these datasets are shown in Table 7 For graph interpretation, we preprocess the ZINC dataset and obtain four datasets, namely QED, DRD2, HLM-CI. and ULM-CLint The details of these datasets are shown in Table The synthetic dataset for graph denoising is basically generated from MUTAG dataset, please refer to Section 5.2 details.
*The statistics of datasets in graph classification collected from http://netwworkrppssiiry.ccmm
15

---

Published as a conference paper at ICLR 2021
miss:1 wrong
miss: wrong?2
mises22 wrong
miset2 wrongg2
miss4 wrong:2
mise:3 wrong.
miss wrong:1
miss; wrong:1
wrong?
wrong:2
wrong:3
wrong?2 GCN+Att07
Permuted
Line Graph
GCN+GIB
GCN+ArtO5
Figure 6: We show the blindly denoising results on permuted graphs. Each method operates on the Line-graphs and tries to recover the true topology by removing the redundant edges. Columns 4,5,6 shows results obtained by different methods, where "miss: and there are n wrong edges the output graph. GIB always recognizes more similar structure to the ground truth (not provided in the training process) than other methods.
wrong: n" means missing edges
Table 7: Statistics of datasets in improvement of graph classification.
MUTAG PROTEINS IMDB-BINARY
DD
Nodes
97.9K
43.5K
19.8K
334.9K
Edges
202.5K
162.1K
386.1K
1.7M
Density
4.2 x x
1.7 x10
2.0 x10-3
3.0
10
Maximum degree
50
540
38
Minimum degree
2
4
Average degree
7
39
10
Number of triangles
2.8K
366K
18.8M
7.1M
Average number of triangles
8
951
21
Maximum number of triangles
136
17.8K
160
Average clustering coefficient Fraction of closed triangles
0.001965 0.003160
0.316645
0.831934
0.413379
0,315106
0.803561
0.410832
Maximum k-core
9
117
15
Lower bound of Maximum Clique
5
18
A.7 SIZES THE CHOSEN SUBGRAPHS GRAPH INTERPRETATION
In the graph interpretation task, the asper-parameter Leons a, 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 I0] 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 contrast, HLM-CLint measures vitro human micro-
almost the whole structure of a molecule. some metabolic stability, which is greatly influenced by small motifs. As shown in Table and Table 10, GCN+GIB can recognize the subgraphs with adaptive sizes on different tasks, leading to better performance. However, in GCN+At105 and AtN7 the size of subgraphs is explic- itly controlled by the hyper-parameter (preserve top 50% or 70 % nodes with the highest attention scores). Therefore, the performances of these methods are limited.
16

---

Published as a conference paper at ICLR 2021
Table 8: Statistics of datasets in graph interpretation.
QED
DRD2
HLM-CLint
MLM-CLint
Number of graphs
35000
3000
25850
16666
Maximum number nodes
29
66
37
37
Minimum number of nodes
12
13
9
7
Average number of nodes
21.82
27.43
25.14
22.44
Maximum number of edges
34
74
42
42
Minimum number of edges
12
14
9
7
Average number of edges
23.43
30.24
22.23
24.19
Dimension of node features
9
8
9
9
Las
0.8
Les
0.6
Losa
0.4
0.2
0.0
200
400
600
800
1000
200
400
600
800
1000
heeraions
Meeations
(a)
Last
0.5
0.4
0.2
6.1
0.00
800
1000
1000
Rerations
(c)
(d)
Figure 7: From (a) (d), show the loss in the training process QED, DRD2, HLM-CLine and MLM-CLint respectively.
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. the mutual information. Here provide the results of GCN+GIB with Jensen-Shanner Divergence (JSD) and x2 Divergence (x2) on graph classification in Table [1 Experiment results show that our model can also employ other mutual information estimators for bilevel optimization.
2019 Nowozin et al. 2016), the f-divergence family can also approximate
17

---

Published as a conference paper at ICLR 2021
Table 9: Size of the chosen subgraphs four datasets in percent.
Method
QED
DRD2
HLM-CLint
MLM-CLint
GCN+
43.5=5.4
46,8:3.1
48.1=4.1
45.1
GCN+At177
65.8=3.4
66.7+3.0
65.8=5.7
67.6+5.5
GCN+GIB
49.6+15.0
94.8++5.3
47.7++3.7
54.7+17.2
Table 10: Size of largest connected parts used for graph interpretation in percent.
Method
QED
DRD2
HLM-CLint
MLM-CLint
GCN+Att05
22.5+:9.5
34.7#994
23.5
29.7=
GCN+At107
43.3+11.8
54.2=13.0
45,0=15.2
41.2=884
GCN+GIB
41.34+16.9
92.8+10.4
10.1
36.9++16.2
A. INFLUENCE OF INITIALIZATION
As the initialization of our model may potentially influence the final chosen subgraphs, we rerum our model five times on the QED dataset for graph interpretation task. Then, we employ the inter- section over union (ToU) to measure the overlap between the subgraphs in 5 different runs and the results reported in Table 2 Similarly, we compute the ToU between the chosen subgraphs and their largest connected parts separately, which refer to IoUas and mauna We finally report the mean and standard deviation of LoUan, IoU the testing set in Table 12 We notice that different initialization has limited influence on the chosen subgraphs, as all the results five additional runs have high portions of common nodes with the initial run.
18

---

Published as a conference paper at ICLR 2021
Table 11: Classification accuracy on graph classification. We implement the mutual information estimator with Jensen-Shannon Divergence (JSD) and x2 Divergence (x²)
Method
QED
DRD2
HLM-CLint
MLM-CLint
GCN
0.743 0.110
0.719 0.041
0.707+ 0.037
0.725= 0.046
GCN+GIB(DV)
0.776 0.075
0.748 0.046
0.722 0.039
0.765 0.050
GCN+GIB(ISD)
0.758 0.087
0.741 0.040
0.718 0.044
0.759 0.057
GCN+GIB(X²)
0.756 0.097
0.746 0.057
0.721 0.033
0.755 0.049
Table 12: The overlap between the chosen subgraphs with different initialization.
Run
1
2
5
ToU
0.848 0.739+0.330
0.765 106
0.784110.12 0.742--0.33
0.829-10.166 0.757++0.335
0.813:10.188 186
ToU maz
0.696-10.310
0.762-+0.304
19


Reviews:
[{"review_id": "4z-ItitYkIz", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nI 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. \n\nReason for the Score:\n\nYet, I think the authors could improve on the related work coverage. For example, I found a paper published in last year's ICLR that seems quite related but not cited or compared in this paper. I hope the authors could spend a bit more time to add the relevant methods and possibly compare against them.\n\nPro:\n- Quite interesting information theoretic objective functions that actually work on multiple graph learning tasks.\n- Figure 1 is quite helpful for understanding the story quickly.\n- Relatively well written and easy to follow the ideas.\n\nCon / Questions:\n- In Eq.13. Given that $\\textbf{$\\textit{S}$}$ are probability values, did the authors add a non-linearity such as sigmoid after the MLP ?\n- The proposed method seems quite related to last year's ICLR paper $\\textit{InfoGraph}$ which I think the authors should probably cite and maybe compare and contrast as well. For example, your proposed Eq.11 seems quite similar to $\\textit{InfoGraph}$'s Eq.6. (https://openreview.net/pdf?id=r1lfF2NYvH)\n\n\n-----------------------------------------------------------------\nPost Rebuttal:\n\nMany thanks for the authors to update their original paper addressing my questions and concerns.\nI have now updated the score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "4g8t-dZMv_", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Authors propose to apply information bottleneck to network structured data which is represented by graphs whose nodes are assigned features. \nThe idea seems promising but the authors need to improve their manuscript considerably. In particular, the probabilistic model underlying the IB framework needs to be made clear right from the start. Which random graphs do you consider ? \n\n- \"... GCN outputs the node embeddings X from the following process:... \" what does that mean ? \n- \"...the GIB seeks for the most informative yet compressed representation Z by optimizing the following objective .. \" what is the domain of the optimization problem here ? and what do you mean precisely by \"compresse representation\" ", "extra_scores": {}, "extra_text": {}}, {"review_id": "0dRHy969zy", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The submission proposed to use Graph Information Bottleneck (GIB) for the subgraph recognition problem in deep graph learning. Basically, it makes use of bi-level optimization to find a subgraph that well encode the information for graph classification task. The major claim is that the resulting subgraph is more robust for the learning. \n\n1). My major concern is on the novelty part. The submission is lack of novelty. First, the Graph Information Bottleneck (GIB) is used to learn a robust GNN against adverbial attack in the paper accepted in this year NeurIPS.\nGraph Information Bottleneck\nTailin Wu · Hongyu Ren · Pan Li · Jure Leskovec\nNeurIPS 2020.\nThe only difference is the submission uses the GIB principal to learn a subgraph. As for the subgraph selection, much work can be found. Basically, the edge dropping or node dropping  is popularly studied recently. By simple search, we can find DropEdge in ICLR’20, NeuralSparse in ICML’20, DropNode in NeurIPS’20. The only difference is they are modeling general GNN, while this submission is only focusing on graph classification. As for the subgraph selection, is there any superiority of the proposed methods over NeuralSparse which uses gumbel-softmax?\n\nDropEdge: DropEdge: Towards Deep Graph Convolutional Networks on Node Classification \nICLR’20.\n\nNeuralSparse: Robust Graph Representation Learning via Neural Sparsification.\nICML’20.\n\nDropNode: A Flexible Generative Framework for Graph-based Semi-supervised Learning\nNeurIPS’20.\n\n\n\n2). The submission is not well presented. Many notations are not defined before use. For example, in 4.2,\nδyi (y)δ(Gsub,i), what is meaning of δ? What is the meaning of G_sub, i ?\n\n\n3). The experiments are not sufficient. The list methods are most famous GNNs but not SOTAs for graph classification task. Graph neural tangent kernel (GNTK), End-to-end graph classification (DCGNN) , Convolutional network for graphs (PATCHY-SAN). Besides, the graph kernel methods, like Graphlet kernel (GK), Weisfeiler-Lehman Graph Kernels (WLGK), and Propagation kernel (PK) are not compared.\n\nDCGNN: Zhang, Muhan, Cui, Zhicheng, Neumann, Marion, & Chen, Yixin. 2018. An End-to-End Deep Learning Architecture for Graph Classification. In: The Thirty-Second AAAI Conference on Artificial Intelligence\n\n4). The results reported seems much worse than results reported in other paper. For example, in the paper below. We can easily see the best result in MUTAG is 93.28±3.36, while the submission gives only 0.844 ± 0.141, in Proteins, best result is 77.47±4.34 while the submission gives only 0.749 ± 0.051. Similar case shows in DD dataset.\n\nStructural Landmarking and Interaction Modelling: on Resolution Dilemmas in Graph Classification,\nhttps://arxiv.org/pdf/2006.15763.pdf\n\n5). Typos:\nIn 4.1, “a informative representation”==>”an informative representation”\nIn 4.3, “S is 2-dimensional vector”==>”S is a 2-dimensional vector”\n\n\n6). The authors does not report or discuss the running time complexity of the algorithm. Since the framework needs bi-level optimization, it is supposed to discuss how fast the algorithm will converge.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0J7VemrR9ze", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary \nThe 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: \n\n(a) optimizing the mutual information loss $L_{cls}$ between the subgraph representation $G_{sub}$ and the graph label $Y$ using the backbone GNN followed by aggregation of subgraph node embeddings $X_{sub}$ and cross-entropy loss when comparing to graph labels. \n\n(b) approximates the mutual information $L_{MI}$ between the original graph and a subgraph $I(G, G_{sub})$ using statistics network $f_{\\phi}$ which uses the backbone GNN to obtain graph embeddings (using mean/sum or pooling over node embeddings) followed by MLP over concatenated embeddings of $G$ and $G_{sub}$. \n\nThe procedure retrains the graph-subgraph mutual information estimator in the inner loop for each step (eqn. 10) before updating the parameters of the backbone GNN and the subgraph selection MLP and finally updating the subgraph-label MI estimator ($L_{cls}$). In order to obtain compact subgraphs, the paper introduces a regularization term $L_{con}$ closely related to graph cut. \n\nThe papers shows empirically on downstream task of graph classification that adding the GIP objective improves classification accuracy. Further, on graph interpretation task, the authors show that the GIP objective improves the similarity of the retrieved subgraphs using domain-specific metrics. The authors also evaluate on graph denoising on the MUTAG dataset.\n\n# Recommendation \nI vote for a strong accept. This paper is well-written, makes a clear theoretical contribution to the field as well as provides sufficient empirical evaluation. \n\n# Questions to the authors \n- I would have liked to see in the supplementary material an example of the algorithm on a toy graph example (similar to case study A). \n\n- I wonder does the initialization have an influence on the final chosen subgraph nodes. Does $S$ (node-assignment) (always/almost always?) saturate  as mentioned on page 5? \n\n- What is the influence of the ${\\cal L}_{con}$ on the size of the final chosen subgraph. A table showing the size of final subgraphs (in term of output of MLP $\\theta_2$ in Figure 1) might be helpful, though this is partially addressed in Table 4. \n\n- For completeness, it would be good to provide in the supplementary material the properties of the datasets used e.g., number of graphs, mean/max/min number of nodes, edges, dimension of node features, dimension of edge features (if any), etc. \n\n- It would have been good to see plots showing the convergence of the different losses as part of the bi-level optimization iterations. \n\n- [optional] On the graph denoising experiment, it might be good to add more concrete evaluation both on larger graphs e.g. on graph families such as Power-Law, SBM as well as non-uniform edge addition. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a graph information bottleneck (GIB) framework for subgraph recognition, including the proposal of a MI objective as well as a bi-level optimization scheme for minimizing said objective. The paper receive mixed reviews, with two reviewers in favor of acceptance and two reviewers in favor of rejection. 

One negative reviewer was too short to judge and had low-confidence. I think most of the concerns arise from lack of understanding of the work and the authors adequately address this on the rebuttal. The authors are encouraged to make minor modifications for clarity. In particular, classical IB considers random variables x, z, y, and learns latent representation z that is maximally informative about output y and sufficiently informative about input x. Therefore, it is natural to expect that the input to GIB is a random graph. 

The other negative reviewer finds the paper lacks novelty and points to multiple references. The positive reviewers also ask about the connection with additional references. Im my opinion, the authors do an excellent job at clarifying the differences with all prior work mentioned by the reviewers, including the closest one, a GIB paper in NerurIPS 2020. In my view, the present submission contains sufficient novelty relative to prior work, specifically as it focuses on a different problem (sub-graph) and proposes a different optimization method. That being said, I think it is absolutely essential that the author responses be added to the paper. In other words, the final version must add citations to the relevant work mentioned by the reviewers and clarify the differences.

All other comments from the two remaining reviewers are very positive: the reviewers find the paper contributes with "quite interesting information theoretic objective functions that actually work on multiple graph learning tasks" and "makes a clear theoretical contribution to the field as well as provides sufficient empirical evaluation." I share the views of the positive reviewers and recommend acceptance, subject to the authors incorporating their responses to the reviewers' comments.
Decision: Accept (Poster)