Mincut Pooling in Graph Neural Networks
Authors: Filippo Maria Bianchi
Daniele Grattarola
Cesare Alippi
Venue:  (2020)
Keywords: Graph Neural Networks
Pooling
Graph Cuts
Spectral Clustering

Abstract: The advance of node pooling operations in Graph Neural Networks (GNNs) has lagged behind the feverish design of new message-passing techniques, and pooling remains an important and challenging endeavor for the design of deep architectures.
In this paper, we propose a pooling operation for GNNs that leverages a differentiable unsupervised loss based on the minCut optimization objective.
For each node, our method learns a soft cluster assignment vector that depends on the node features, the target inference task (e.g., a graph classification loss), and, thanks to the minCut objective, also on the connectivity structure of the graph.
Graph pooling is obtained by applying the matrix of assignment vectors to the adjacency matrix and the node features.
We validate the effectiveness of the proposed pooling method on a variety of supervised and unsupervised tasks.

Under review as a conference paper at ICLR 2020
MINCUT POOLING IN GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
The advance of node pooling operations in Graph Neural Networks (GNNs) has lagged behind the feverish design of new message-passing techniques, and pool- ing remains an important and challenging endeavor for the design of deep archi- tectures. In this paper, we propose pooling operation for GNNs that leverages a differentiable unsupervised loss based on the minCUT optimization objective. For each node, our method learns soft cluster assignment vector that depends on the node features, the target inference task (e.g., a graph classification loss), and, thanks to the mincuT objective, also on the connectivity structure of the graph. Graph pooling is obtained by applying the matrix of assignment vectors to the ad- jacency matrix and the node features. The proposed method can also be used as a stand-alone module to cluster vertexes in annotated graphs and solve unsupervised problems. We validate the effectiveness of the proposed pooling method on down- stream tasks, including supervised graph classification and a set of unsupervised tasks, which reveal the limitations of existing GNN pooling approaches.
INTRODUCTION
fundamental component deep convolutional neural networks the pooling operation, which places the output of convolutions with local summaries of nearby points and is usually implemented by maximum average operations (Lee et al. 2016). State-of-the-ar architectures alternate convo- lutions, which extrapolate local patterns irrespective of the specific location on the input signal, and pooling, which lets the ensuing convolutions capture aggregated patterns. Pooling allows learn abstract representations in deeper layers of the network by discarding information that is superflu- ous for the task, and keeps model complexity under control by limiting the growth of intermediate features.
Graph Neural Networks (GNNs) extend the convolution operation from regular domains, such as images time series, to data with arbitrary topologies and unordered structures described by graphs (Battaglia et al. 2018). The development of pooling strategies for GNNs, however, has lagged behind the design of newer and more effective cessage-passingg (MP) operations (Gilmer jet al., 2017), such as graph convolutions, mainly due to the difficulty of defining an aggregated version of the original graph that supports the pooled signal.
naive pooling strategy in GNNs is to average all nodes features (Li et al., 2016), but it has lim- ited flexibility since does not extract local summaries the graph structure, and no further MP operations can be applied afterwards. An altermative approach consists in pre-computing coarsened versions of the original graph and then fit the data these deterministic structures (Bruna al. 2013). While this aggregation accounts for the connectivity of the graph, it ignores task-specifi objectives well as the node features.
In this paper, we propose differentiable pooling operation implemented as neural network layer, which can be seamlessly combined with other MP layers (see Fig. [T. The parameters the pool- ing layer are learned by combining the task-specific loss with an unsupervised regularization term, which optimizes a continuous relaxation of the normalized ninT objective. The mincUT iden- tifies dense graph components, where the nodes features become locally homogeneous after the message- message-passing. By gradually aggregating these components, the GNN learns to distil global prop- erties from the graph. The proposed minCUT pooling operator (minCUTpool) yields partitions that 1) cluster together nodes which have similar features and are strongly connected on the graph, and 2) take into account the objective of the downstream task.

---

Under review as a conference paper at ICLR 2020
Message-passee
minCUT Pooling
Message-passing
Figure 1: A deep GNN architecture where message- saaesage-pssinggga is followed by minCUT pooling.
2 BACKGROUND
2.1 MINCUT AND SPECTRAL CLUSTERING
Given graph G [V.E). VI= = N, and the associated adjacency matrix A NNNN the K-way normalized minCUT (simply referred to minCuT) aims at partitioning V in K disjoint subsets by removing minimum volume edges. The problem is equivalent to maximizing
K
links (Vx) 1
K Eieen Eij
Σ k=1
(1)
K
degree (V:) K
EiEn. Eij
where the numerator counts the edge volume within each cluster, and the denominator counts the edges between the nodes in a cluster and the rest of the graph (Shi & Malik (000). Let C E Nx be a cluster assignment matrix, so that Cr = if node belongs to cluster j. and otherwise. The mi mincuT problem be expressed as
K Cf Σ DC
1
maximize
s.t. Ce (0,1) C1 = 1I,,
where diag( A 1In) is the degree matrix (Dhillon al. 2004). Since problem ? NP-hard, it is usually recast in relaxed formulation that can be solved in polynomial time and guarantees near-optimal solution (Yu Shi 2003)::
K
arg max QERN
QEQ 1=1
s.t. Q = DC) Q² lk.
(3)
K
While the optimization problem 3 is still non-convex, there exists an optimal solution UxO where UK E N contains the eigenvectors of A corresponding the K largest eigenvalues, and O e k is an orthogonal transformation (Ikebe et al. 1987).
Since the elements of Q" real values rather than binary cluster indicators, the spectral clustering (SC) approach can be used to find discrete cluster assignments. In SC, the rows of Q" are treated node representations embedded in the eigenspace of the Laplacian, and are clustered together with standard algorithms such as k-means (Von Luxburg 2007). One of the main limitations of SC memory complexity of O(N2) and
lies in the computation of the spectrum of A, which computational complexity of O(N3). This prevents its applicability to large datasets.
To deal with such scalability issues, the constrained optimization in 3 can be solved by gradient descent algorithms that refine the solution by iterating operations whose individual complexity is ONN2), or even O(N) (Han Filippone 2011)). Those algorithms search the solution on the manifold induced by the orthogonality constraint the columns of Q, by performing gradient updates along the geodesics (Wen & Yin 2013) Collins et al.) 2014). Alternative approaches rely on the QR factorization to constrain the space of feasible solutions (Damle et al. 2016). and alleviate the cost 3( of the factorization by ensuring that orthogonality holds only on one minibatch at time (Shaham al. 2018).
2

---

Under review as a conference paper at ICLR 2020
Other works based on neural networks include an autoencoder trained to map the ith row of the Laplacian to the ith components of the first K eigenvectors, to avoid the spectral decomposi- tion (Tian et al. 2014). Yi et al. (2017) use soft orthogonality constraint to learn spectral em- beddings as a volumetric reparametrization of a precomputed Laplacian eigenhase. [Shaham et al. (ammpiinamt al. (2019) propose differentiable loss functions to partition generic data and process out-of-sample data at inference time. Nazi et al. (2019) generate balanced node partitions with GNN, but adopt an optimization that does encourage cluster assignments to orthogonal.
2.2 GRAPH NEURAL NETWORKS
Many approaches have been proposed to process graphs with neural networks, including recurrent architectures (Scarselli et al. 2009 Li et al. 2016) or convolutional operations inspired by filters used in graph signal processing (Defferrard et al. 2016, Bianchi et al., 2019). Since our focus is on graph pooling, base GNN implementation the features of each node with its 1st-order neighbors. To account for the initial node features, is possible to introduce self-loops by adding a (scaled) identity matrix to the diagonal of A (Kipf & Welling. 2017). Since our pooling will modify the structure of the adjacency matrix, we prefer a MP implementation that leaves the original unaltered and accounts for the initial node features by means of skip connections.
a simple MP operation, which combines
Let A = D AD à the matrix containing the node features. The output of the MP layer
E RNNN be the symmetrically normalized adjacency matrix and X E RNF
(++1) = ( Á) ReRRU W, + X W.))
(4)
where MM W m: W. are the trainable weights relative to the mixing and skip component of the layer, respectively.
3 PROPOSED METHOD
The minCUT pooling strategy computes cluster assignment matrix S NxK by means of multi-layer perceptron, which maps each node feature x; into the ith row of S:
S = (eLL W2),
(5)
where Pool = (W1 E R W2 " are trainable parameters. The softmax function guarantees that 8t.j E [0, 1] and enforces the constraints S1 x = 1x inherited from the optimization problem in (2). The parameters @MP and θ Poot are jointly optimized by minimizing the usual task-specific loss, as well as an unsupervised loss Luv, which is composed of two terms
Tr(STAS AS)
I STS S F
= L.
TS(
K
L.
where || || indicates the Frobenius norm.
The cut loss term, L., evaluates the minCUT given by the cluster assignment S, and is bounded by -1 < L. < O. Minimizing L. encourages strongly connected nodes to be clustered together, since the inner product (s,, $5) increases when رر large. Le has a single maximum, reached when the numerator Tr(ST AS) = K Σ ASS = O. This occurs if, for each pair of connected nodes (i.e., ă..j >> 0), the cluster assignments orthogonal (i.e., (s;, s;) 0). L. reaches its minimum, -1, when Tr(ST AS) = Tr(STDS). This occurs when ponents the cluster assignments are equal for all the nodes in the same component and orthogonal to the cluster assignments of nodes in different components. However, L, is a non-convex func- tion and its minimization can lead to local minima degenerate solutions. For example, given connected graph, a trivial optimal solution the one that assigns all nodes to the same cluster. As consequence of the continuous relaxation, another degenerate minimum occurs when the cluster assignments are all uniform, that is, all nodes are equally assigned to all clusters. This problem is exacerbated by prior message-passiin operations, which make the node features uniform.
graph with K disconnected com-
3

---

Under review as a conference paper at ICLR 2020
The orthogonality loss term, Lor penalizes the degenerate minima of Le by encouraging the cluster assignments to be orthogonal and the clusters to
similar size. Since the two matrices in Co that 0 - C. s 2. Therefore. L. does not dominate over C, and
have unitary norm it is easy the two terms can be safely summed directly (see Fig. 4 for an example). I can be interpreted as a (rescaled) clustering matrix Ix- = S where S assigns exactly N/K points to each cluster. The value of the Frobenius norm between clustering matrices is not dominated by the performance on the largest clusters (Law et al. 2017) and, thus, can be used to optimize intra-cluster variance.
Contrarily to SC methods that search for feasible solutions only within the space of orthogonal matrices, Co only introduces a soft constraint that could be violated during the learning procedure. Since f. is non-convex, the violation compromises the theoretical guarantee of convergence to the optimum of (3). However, we note that:
1. the cluster assignments are well initialized: after the MP operation, the features of the connected vertices become similar and, since the MLP is smooth function (Nelles) 2013 it yields similar cluster assignments for those vertices;
2. in the GNN architecture, the minCUT objective is a regularization term and, therefore, solution which is sub-optimal for (3) could instead be adequate for the specific objective of the downstream task;
3. optimizing the task- loss helps the GNN avoid the degenerate minima of Le-
3.1 COARSENING
The coarsened version of the adjacency matrix and the graph signal are computed as
poot = S ÄS; X = s X.
(7)
where the entry pooo in X kxF is the weighted average value of feature j among the elements in cluster Apool E KX is symmetric matrix, whose entries aooo are the total number of edges between the nodes in the cluster i, while a is the number of edges between cluster and j. Since A pool corresponds to the numerator of L. in (7). the trace maximization yields clusters with many internal connections and weakly connected to each other. Hence, A pool will be a diagonal-dominate matrix, which describes a graph with self-loops much stronger than any other connection. Because self-loops hamper the propagation across adjacent nodes in the MP operations following the pooling layer, compute the new adjacency matrix A by zeroing the diagonal and by applying the degree normalization
= A pool
I diag( A pool):
pool = DD 1 ADAD
(8)
where (-ag(-) returns the matrix diagonal.
3.2 DISCUSSION AND RELATIONSHIP WITH SPECTRAL CLUSTERING
The proposed method is straightforward to implement: the cluster assignments, the loss, graph coarsening, and feature pooling are all computed with standard linear algebra operations.
There are several differences between minCUTTool and classic SC methods. SC partitions the graph based on the Laplacian, but does not account for the node features. Instead, the cluster assignments found by minCUTTpoo depend on x,, which works well if connected nodes have similar features. This is a reasonable assumption in GNNs since, even in disassortative graphs (i.e., networks where dissimilar nodes are likely to be connected (Newman) 2003)), the features tend to become similar due to the MP operations.
Another difference is that SC handles single graph and is not conceived for tasks with multiple graphs to be partitioned independently. Instead, thanks to the independence of the model parameters from the number of nodes N and from the graph spectrum, minCUTTool can generalize to out- of samle data. This feature is fundamental in problems such as graph classification, where each sample is graph with a different structure, and allows to train the model small graphs and process larger ones at inference time. Finally, minCUTpool directly uses the soft cluster assignments rather than performing k-means afterwards.
4

---

Under review as a conference paper at ICLR 2020
4 RELATED WORK ON POOLING IN GNNS
Trainable pooling methods. Similarly to our method, these approaches learn how to generate coarsened version of the graph through differentiable functions, which take as input the nodes fea- tures X and are parametrized by weights optimized on the task at hand.
Diffpool (Ying et al., 2018) is pooling module that includes two parallel MP layers: one to compute the new node features ((++) and another to generate the cluster assignments S. Diff- pool implements an unsupervised loss that consists of two terms. First, the link prediction term | F minimizes the Frobenius norm of the difference between the adjacency and the Gram matrix of the cluster assignments, encouraging nearby nodes to be clustered together. The sec- ond term N Σx= i= ((,)) minimizes the entropy of the cluster assignments to make them alike to one-hot vectors. Like minCUTpool, Diffipol clusters the vertices of annotated graphs, but yields completely different partitions, since it computes differently the clustering assignments, the coars- ened adjacency matrix and, most importantly, the unsupervised loss. In Diffpool, such a loss shows pathological behaviors that are discussed later in the experiments.
The approach dubbed Top-K pooling (Hongyang Gao 2019 Lee et al. 2019). learns a projection vector that is applied to each node feature obtain score. The nodes with the K highest scores are retained, the others are dropped. Since the top-K selection is not differentiable, the scores are also used as gate/attention for the node features, letting the projection vector to be trained with backpropagation. T is memory efficient as it avoids generating cluster assignments, To prevent A from becoming disconnected after nodes removal, Top-K drops the rows and the columns from A and uses it as the new adjacency matrix. However, computing A costs O(N2) and it is inefficient implement with sparse operations.
Topological pooling methods. These methods pre-compute a pyramid of coarsened graphs, only taking into account the topology (A), but not the node features (X). During training, the node features are pooled with standard procedures and are fit into these deterministic graph structures. These methods are less flexible, but provide a stronger bias that can prevent degenerate solutions coarsened graphs collapsing in a single node).
The approach proposed by Bruna et al. (2013). which has been adopted also in other GNN ar- chitectures (Defferrard et al.] [016]] Fey al., 2018). exploits GRACLUS (Dhillon et al.) 2004). hierarchical algorithm based on SC. At each pooling level I, GRACLUS indetifies the pairs of max- imally similar nodes i and ji to be clustered together into a new vertex k((-)-- At inference phase, max-pooling is used to determine which node in the pair is kept. Fake vertices are added so that the number nodes can be halved each time, but this injects noisy information in the graph.
Node decimation is a method originally proposed in graph signal processing literature (Shuman cet al.) (2166). which as been adapted also for GNNs (Simonovsky & Komodakis 2017). The nodes partitioned in two sets, according to the signs of the Laplacian eigenvector associated to the largest eigenvalue. One of the two sets is dropped, reducing the number of nodes each time approx- imately by half. Kron reduction is used compute a pyramid of coarsened Laplacians from the remaining nodes.
A procedure proposed in Gama et al. (2018) diffuses signal from designated nodes the graph and stores the observed sequence of diffused components. The resulting stream of information is interpreted time signal, where standard CNN pooling is applied. We also mention a pooling operation for coarsening binary unweighted graphs by aggregating maximal cliques (Luzhnica et al.) 2019). Nodes assigned to the same clique are summarized by max or average pooling and become new node in the coarsened graph.
5 EXPERIMENTS
We consider both supervised and unsupervised tasks, and compare minCUTpool with other GNN pooling strategies. The Appendix provides further details on the experiments and a schematic de- piction of the architectures used in each task. In addition, the Appendix reports two additional experiments: i) graph reconstruction by means of an Auto Encoder with bottleneck, implemented with pooling and un-pooling layers, ii) architecture with pooling for graph regression.
5

---

Under review as a conference paper at ICLR 2020
5.1 CLUSTERING THE GRAPH NODES
To study the effectiveness of the proposed loss, we perform different node clustering tasks with simple GNN composed of single MP layer followed by a pooling layer. The GNN is trained by minimizing C, only, so that its effect is evaluated without the "interference" of a supervised loss.
Clustering synthetic networks We consider two simple graphs: the first is a network with communities and the second is regular grid. The adjacency matrix A is binary and the features X are the 2-D node coordinates. Fig. depiccs the node partitions generated by SC (a, d), Diffpool (b, e), and minCUTpool (c, f). Cluster indexes for Diffpool and minCUTTool are obtained by taking argmax of row-wise. Compared to SC, Diffpool and minCUTpool leverage the information contained in X. minCUTTool generates very accurate and balanced partitions, demonstrating that the cluster assignment matrix S is well formed. On the other hand, Diffpool assigns some nodes to the wrong community in the first example, and produces imbalanced partition of the grid.
(a) SC
(b) Diftpool
(c) minCUTpool
SC
(c) Diffpool
(f) minCUTpool
Figure 2: Node clustering community network (K=6) and on grid graph (K=5).
Given an image, we build a Region Adjacency Graph (Témeau Colan- toni 2000) using as nodes the regions generated by an oversegmentation procedure (Felzenszwalb & Huttenlocher 2004). The SC technique used this example is the recursive normalized cut (Shi & Malik[ 2000). which recursively clusters the nodes until convergence. For Diffpool and min- CUTpool, we include node features consisting of the average and total color in each oversegmented region. We set the number of desired clusters to K 4. The results in Fig. shoow that minCUT pool yields a more precise segmentation. On the other hand, SC and Diffpool aggregate wrong regions and, in addition, SC finds too many segments.
Image segmentation
Clustering on citation networks We cluster the nodes of three popular citation networks: Cora, Citeseer, and Pubmed. The nodes are documents represented by sparse bag-of- sords feature vectors stored in X and the binary undirected edges in A indicate citation links between documents. Each node is labeled with the document class y;. Once the training is over, to the quality of the partitions generated by each method we check the agreement between the cluster assignments and the true class labels. Tab. reports the Completeness Score CS y)
H(Slx) and Normalized H(S)
H())-#(()))) where H-)) is the entropy. Mutual Information NMI(y.y) = ( H
The GNN architecture configured with minCUTpool achieves higher NMI score than SC, which does not account for the node features X when generating the partitions. Our pooling operation

---

Under review as a conference paper at ICLR 2020
(a) Original image
(b) Oversegmentation
(c) Region Adjacency Graph
(d) SC.
(c) Diffpool (K = 4)
(f) minCUTTpoo (K = 4)
Figure 3: Image segmentation by clustering the nodes of the Region Adjacency Graph.
loss
0.4
Tot
Le
398.3
0.3
Lo
398.2
398.1
0.2
0.0
398.0
0.1
-0.5
5000 Iteration
10000
5000 Iteration
10000
5000
10000
5000
10000
Iteration
Iteration
(a) Diffpool
(b) minCUTTpool
Figure 4: Unsupervised losses and NMI of Diffpool and minCUTpool on Cora.
outperforms also Diffpool, since the minimization of the unsupervised loss in Diffpool yields de- generate solutions. The pathological behavior is shown in Fig. 4 which depicts the evolution of the NMI scores the unsupervised losses in Diffpool and minCUTpool minimized in training.
Table 1: NMI and CS obtained by clustering the nodes on citation networks over 10 different runs. The number of clusters K is equal to the number of node classes.
Dataset
Spectral clustering
Diffpool
MinCUTppol
NMI
CS
NMI
CS
NMI
CS
Cora
0.025
0.044
0.126
0042
0,315
0.005
0.309
0.005
0.404
4 oo1s
0.392 = 0.018
Citeseer
0.014
n.0
0.033
0000
0.139
0.016
0.153
+ 0,000
0.287
4 0o0r
0.283
0.046
Pubmed
3
0.182
0.000
0.261 0000
0.079
0.001
0.085
0.001
0.200 0020
0.197 0.019
5.2 SUPERVISED GRAPH CLASSIFICATION
In this task, the i-th datum is a graph with N; nodes represented by a pair (A,, X,) and must be as- sociated to the correct label y.. We test the models on different graph classification datasets. For fea- tureless graphs, we used the node degree information and the clustering coefficient as surrogate node features. We evaluate model performance with 10-fold train/test split, using 10% of the training set each fold as validation for early stopping. We adopt a fixed network architecture, MP(32)-pool. MP(32) (ryss)))poolMMP((3)))llllllll Globallvggoooo
where MP is the message-passing operation in (4)

---

Under review as a conference paper at ICLR 2020
with 32 hidden units. The pooling module is implemented either by Graclus, Decimation pooling, Top-K, SAGPool (Lee et al. 2019), Diftpool, or the proposed minCUTTool. Each pooling method configured to drop half of the nodes in graph (K N/2 in Top-K, Diffpool. and minCUTpool), (WI.) graph kernel (Shervashidze et al., 2011 network with only MP layers (Flat), and fully connected network (Dense).
As baselines, we consider the popular Weisfeiler-Lehhe
Table 2: Graph classification accuracy. Significantly better results (p 0.05) are in bold.
Dataset
WI
Dense
Flat
Graclus
Decim.
Diffpool
Top-K
SAGpool
minCUT
Bench-easy
92.6
29.3=aa
98.5
97.5
97.9=0s
98.6204
82.4
84.2423
99.0=a.
Bench-hard
60.0
29.4
67.6 07.6128
69.0215
72.6209
69.9219
42.7
37.7
73.821.
Mutagenicity
81.7=111
68 28.
78.0
74,4
77.8=23
77.6=27
71.9=11
72.4224
79.922.1
Proteins
71.2+26
68.7+33
72.6448
68.6
73.3
72.7+38
69.6+35
70.5+22
76.5++2
DD
78.6+27
70.6#32
76,8+15
70.5
72.0+3a
79.3+24
69.4
71.5455
80.8
COLLAB
74.8+13
79.3
82.1+18
77.1
79.1
81.8+14
79.3
79.2+22
83,4
Reddit- -innary
68.2211
48.5=26
80.3126
79.2204
84.3224
86.8
74.7245
73.9
91.4
Tab. 2 reports the classification results, highlighting those that significantly better (p-value < 0.05 w.r.t. the method with the highest mean accuracy). The comparison with Flat helps to understand if pooling operation is useful not. The results of Dense, instead, help quantify how much additional information is brought by the graph structure, with respect to the node features alone. can be seen that minCUTTpoo obtains always equal better results with respect to every other GNN architecture. On the other hand, some pooling procedures do not always improve the performance compared the Flat baseline, making them not advisable to use some cases. The WI. kernel generally performs worse than the GNNs, except for the Mutagenicity dataset. This is probably because Mutagenicity has smaller graphs than the other datasets, and the adopted GNN architecture is overparametrized for this task. Interestingly, in some dataset such Proteins and COLLAB is possible to obtain fairly good classification accuracy with the Dense architecture, meaning that the graph structure only adds limited information.
Sec eppcch
Figure 5: Average duration of one epoch using the same GNN with different pooling operations. Times were computed with an Nvidia GeForce GTX 1050, on the DD dataset with batch size of
TopK
DiffPool
minCUT
Graclus
Decim.
Fig. 5 reports a comparison of the execution time per training epoch for each pooling algorithm. Graclus and Decimation are understandably the fastest methods, since the coarsened graphs are pre- computed. Among the differentiable pooling methods, minCUTTpool is faster than Diffpool, which uses slower MP layer rather than a MLP to compute cluster assignments, and than Top-K, which computes the square of A at every forward pass.
CONCLUSIONS
We proposed pooling layer for GNNs that coarsens graph by taking into account both the the connectivity structure and the node features. The layer optimizes regularization term based on the minCUT objective, which minimized in conjunction with the task-specific loss to produce node partitions that are optimal for the task at hand.
We tested the effectiveness of our pooling strategy unsupervised node clustering tasks, by op- timizing only the unsupervised clustering loss, as well as supervised graph classification tasks on several popular benchmark datasets. Results show that minCUTpool performs significantly better than existing pooling strategies for GNNs.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzake Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 1106:x:800.012220 2018.
Filippo Maria Bianchi, Daniele Grattarola, L Livi, and C Alippi. Graph neural networks with con- volutional arma filters. arXiv preprint 1rXiv:1901.01333 2019.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. arXiv preprint arXiv: 2013.
Maxwell D Collins, Ji Liu, Jia Xu, Lopamudra Mukherjee, and Vikas Singh. Spectral clustering with convex regularizer millions of images. In European Conference Computer Vision, pp. 282-298. Springer, 2014.
Anil Damle, Victor Minden, and Lexing Ying. Robust and efficient multi-way spectral clustering. arXiv preprint 1609.v:6090.06 2016.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances Neural Information Processing Systems, pp. 3844-3844400 -352, 2016.
Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis. Kernel k-means: spectral clustering and nor- malized cuts. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 551-556. ACM, 2004.
Pedro Felzenszwalb and Daniel P Huttenlocher. Efficient graph- based image segmentation. Inter- national journal of computer vision, 59(2):167-181, 2004.
Matthias Fey, Erie Lenssen, Frank Weichert, and Heinrich Müller. Splinecnn: Fast geomet- ric deep learning with continuous b-spline kernels. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 869-877, 2018.
Fernando Gama, Antonio G Marques, Geert Leus, and Alejandro Ribeiro. Convolutional neural network architectures for signals supported on graphs. IEEE Transactions on Signal Processing. 6734):1034-1000 2018.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning-Volle Volume 70, pp. 1263-1272. JMLR. org, 2017.
Yufei Han and Maurizio Filippone. Mini-batch spectral clustering. In 2017 International Joint Conference Neural Networks (IJCNN) pp. 3888-388888 3895. IEEF, 2017.
Shuiwang Ji Hongyang Gao. Graph u-nets. In Proceedings of the 36th International conference on Machine learning (ICML), 2019.
Yasuhiko Ikebe, Toshiyuki Inagaki, and Sadaaki Miyamoto. The monotonicity theorem, cauchy's interlace theorem, and the courant-fischer theorem. The American Mathematical Monthly, 94(4): 352-354, 1987.
Michael Kampffmeyer, Sigurd Løkse, Filippo M. Bianchi, Lorenzo Livi, Arnt-Borre Salberg, and Robert Jenssen. Deep divergence-basse approach to clustering. Neural Networks, 113:91 101, 2019.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. International Conference of Learning Representations (ICLR), 2017.
Mare T Law, Raquel Urtasum, and Richard S Zemel. Deep spectral clustering learning. In Pro- ceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1985-1994. JMLR. org, 2017.

---

Under review as a conference paper at ICLR 2020
Chen- Yu Lee, Patrick W Gallagher, and Zhuowen Tu. Generalizing pooling functions in convo- lutional neural networks: Mixed, gated, and tree. In Artificial Intelligence and Statistics, pp- 464-472, 2016.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In Proceedings of the 36th International conference on Machine learning (ICML-19), 2019.
Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. International Conference of Learning Representations (ICLR), 2016.
Enxhell Luzhnica, Ben Day, and Pictro Lio. Clique pooling for graph classification. International Conference Learning Representations (ICLR) Representation Learning on Graphs and Man- ifolds workshop, 2019.
Azade Nazi, Will Hang, Anna Goldie, Sujith Ravi, and Azalia Mirhoseini. Gap: Generalizable approximate graph partitioning framework. arXiv preprint arXiv:1903.0066 2019.
Oliver Nelles. Nonlinear system identification: from classical approaches neural networks and fuzzy models. Springer Science & Business Media, 2013.
Mark EJ Newman, Mixing patterns in networks. Physical Review E, 67 2003.
2003.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2009.
Uri Shaham, Kelly Stanton, Henry Li, Boaz Nadler, Ronen Basri, and Yuval Kluger. Spectrainet: Spectral clustering using deep neural networks. arXiv preprint #rXiv:180.001586 2018.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borg- wardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(Sep):2539- 2561, 2011.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. Departmental Papers (CIS), pp. 107, 2000.
David Shuman, Mohammad Javad Faraji, and Pierre Vandergheynst. A multiscale pyramid trans- form for graph signals. IEEE Transactions on Signal Processing, 64(8):2119-2134, 2016.
Martin Simonovsky and Nikos Komodakis. Dynamic edgeconditioned filters in convolutional neural networks on graphs. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2017.
Fei Tian, Bin Gao, Qing Cui, Enhong Chen, and Tic- Yan Liu. Learning deep representations for graph clustering. In AAAI, pp. 1293-1299, 2014.
Alain Trémeau and Philippe Colantoni. Regions adjacency graph applied to color image segmenta- tion. IEEE Transactions on image processing. 94):735-744, 2000.
Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395-41 416, 2007.
Zaiwen Wen and Wotao Yin. A feasible method for optimization with orthogonality constraints. Mathematical Programming, 142(1-2):397-434, 2013.
Li Yi, Hao Su, Xingwen Guo, and Leonidas Guibas. Synespecenn: Synchronized spectral cnn for 3d shape segmentation. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 2282-2290, 2017.
Zhitao Ying. Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical graph representation learning with differentiable pooling. In Advances Neural Infor- mation P Processing Systems, pp. 4810-4810, 2018
Yu and Shi. Multiclass spectral clustering. In Proceedings Ninth IEEE International Conference Computer Vision, pp. 313-319 vol.1, Oct 2003.
10

---

Under review as a conference paper at ICLR 2020
APPENDIX
A ADDITIONAL EXPERIMENTS
A.I GNN AUTOENCODER
To compare the amount of information retained by the pooling layers in the coarsened graphs, we train an autoencoder (AE) to reconstruct a imput graph signal X from its pooled version. The AE architecture is -MP(3))-MP(322PPP
and is trained by minimizing the mean squared error between the original and the reconstructed graph signal, || X All the pooling operations are configured to retain 25% of the original nodes.
In Diffpool and minCUTppool, the unpool step simply implemented by transposing the original pooling operations
0 SXpool A SS
Top-K does not generate a cluster assignment matrix, but returns binary mask m {0, 1]
that indicates the nodes to drop (0) to retain (I). Therefore, an upsamplig matrix U built by dropping the columns of the identity matrix Iy that correspond to in U [Iv] -==-- The
unpooling operation is performed by replacing with in (9), and the resulting upscaled graph is version of the original graph with zeroes in correspondence of the dropped nodes.
(a) Original
(b) Top-K
(c) Diffpool
(d) minCUTpool
Figure 6: AE reconstruction of ring graph
Original
(b) Top-K
(c) Diffpool
(d) minCUTpool
Figure 7: AE reconstruction of grid graph
Fig. 6 and 7 report the original graph signal X (the node features are the 2-D coordinates of the nodes) and the reconstruction X obtained by using the different pooling methods, for ring graph and regular grid graph. The reconstruction produced by Diffpool is worse for the ring graph, but almost perfect for the grid graph, while minCUTpool yields good results in both cases. On the other hand, Top-K clearly fails in generating coarsened representation that maintains enough information from the original graph.
This experiment highlights major issue in Top-K pooling, which retains the nodes associated to the highest K values a score vector s, computed by projecting the node features onto train- able vector p: Xp. Nodes that connected the graph usually share similar features, and

---

Under review as a conference paper at ICLR 2020
their similarity further increases after the MP operations, which combine the features of neighbor- ing nodes. Retaining the nodes associated to the top K scores in $ corresponds to keeping those nodes that alike and highly connected, as it can be seen in Fig. 7 entire portions of the graphs, which might contain important information. This explains why Top-K fails to recover the original graph signal when used bottleneck for the AE, and yields the worse performance among all GNN methods in the graph classification task.
Therefore, Top-K discards
A.2 GRAPH REGRESSION OF MOLECULAR PROPERTIES ON QM9
The QM9 chemical database is collection of R: 135k small organic molecules, associated to con- tinuous labels describing several geometric, energetic, electronic, and thermodynamic propertie Each molecule in the dataset is represented nodes, and edges represent chemical bonds. The atomic number of each atom (one-hot encoded; C, N, F, O) is taken node feature and the type of bond (one-hot encoded; single, double, triple, aromatic) can be used as edge attribute. In this experiment, we ignore the edge attributes in order to use all pooling algorithms without modifications.
graph {A, ). where atoms associated to
The purpose of this experiment is to compare the trainable pooling methods also on graph re- gression task, but it must be intended a proof of concept. In fact, the graphs in this dataset are extremely small (the average number of nodes is 8) and, therefore, a pooling operation is arguably (ooo--MP(32)--loobdlll
necessary. We consider GNN with architecture where pool is implemented by Top-K, Diffpool, or minCUTpool. The network is trained to predict a given chemical property from the input molecular graphs. Performance evaluated with 10-fold cross- cross-validation using 10% of the training set for validation in each split. The GNNs are trained for 50 epochs, using Adam with learning rate 5e-4, batch size 32, and ReLU activations. We use the mean squared error (MSE) as supervised loss.
Dense,
The MSE obtained on the prediction of each property for different pooling methods is reported in Tab. As expected, the flat baseline with no pooling operation (MP(32)-MPP332)-CH) Gloobaalll GlobalAvgPoolt Dense) yields a lower error in most cases. Contrarily to the graph classification and the AE task, 'op-K' achieves better results than Diffpool in average. Once again, minCUTpool significantly outperforms the other methods on each regression task and, in one case, also the flat baseline.
Property Top-K
Diffpool
minCUTTpol
Flat baseline
mu
0.600=o.o85
0..066
0.538
0.559
alpha
0.197=0.Ds9
0.1 1..10000001
0.078
0.065
homo
0.698 102
0.712.10.01 01.0
0.5261
0.435 0..013
lumo
0..00
(646-10.013
0.5401.0.005
0,515 0.00
gap
0.630
11.9881..00 0.004
0.584:100000
0.552 0 008
r2
0.452 087
0.440
0.261 00-006
0.204
zpve
0.402=a.00 032
0.410 0004
0.:28
0.284=0 005
atom
0.308 o55
0.245 006
0.193
0.163=0.000 (6.000000) 0010
cv
0,291 10.118
0.337+0.01s
0.148 +o.000
0.127 00.002
Table MSE on the graph regression task. The best results with statistical significance of 0.05 are highlighted: the best overall are in bold, the best among pooling methods are underlined.
B EXPERIMENTAL DETAILS
For the WL. kernel, used the implementation provided in the GraKel. library The pooling strategy based on Graclus, is taken from the ChebyNets repository?
htte:://quattummmmmcii......
Tttra://ysiia.iithbbbo///ra https///gthibb.commmefff///ooo
12

---

Under review as a conference paper at ICLR 2020
B.1 CLUSTERING CITATION NETWORKS
Diffpool and pinCUTTool are configured with 16 hidden neurons with linear activations in the MLP and MP layer, respectively used compute the cluster assignment matrix S. The MP layer used to compute the propagated node features X uses ELU activation in both architectures. The learning rate for Adam is 5e-4, and the models are trained for 10000 iterations. The details of the citation networks dataset are reported in Tab. 4
Table 4: Details of the citation networks datasets
Dataset
Nodes
Edges
Node features
Node classes
Cora
2708
5429
1433
Citeseer
3327
9228
3703
Pubmed
19717
88651
500
B.2 GRAPH CLASSIFICATION
We train the GNN architectures with Adam, an L2 penalty loss with weight Ic-4, and 16 hidden units (H) both the MLP of minCUTpool and in the internal MP of Diffpool. Mutagenicity, Proteins, DD, COLLAB, and Reddit-2k are datasets representing real-world graphs and are taken from the repository of benchmark datasets for graph kernel Bench-easy and Bench-hard are datasets where the node features X and the adjacency matrix A are completely uninformative if considered alone. Hence, algorithms that account only for the node features or the graph structure will fail to classify the graphs. Since Bench-easy and Bench-hard come with train/validation/test split, the 10-fold split is not necessary to evaluate the performance. The statistics of all the datasets reported in Tab. 5
Table 5: Summary of statistics of the graph classification datasets
Dataset
samples
classes
avg. nodes
avg. edges
node attr.
node labels
Bench-easy
1800
3
147.82
922.66
yes
Bench-hard
1800
148.32
572.32
yes
Mutagenicity
4337
2
30.32
30.77
yes
Proteins
1113
2
39.06
72.82
DD
1178
2
284.32
715.66
yes
COLLAB
5000
74.49
2457.78
Reddit- -2K
2000
2
429.63
497.75
no
C ARCHITECTURES SCHEMATA
Fig. reports the schematic representation of the minCUTpool layer, Fig. 9 the GNN architecture used the clustering and segmentation tasks; Fig. T0 GNN architecture used in the graph clas- sification task; Fig. 12 the GNN architecture used the graph regression task; Fig. TT the graph autoencoder used in the graph signal reconstruction task.
htte:///lwww...s..rttr..eeeeeaaa lassification wtc.b/.oooFF1111
httee:///ithhbb..o/////gggggaaan for_graph_____
13

---

Under review as a conference paper at ICLR 2020
X
X
pool
X
(
MLP
MP
|
Apool
minCUTpool
Figure 8: Schema of the minCUTpool layer.
X
s
MP
Pool
A
Figure 9: Architecture for clustering/segmentationn
X
Global Pool
Dense (softmax)
MP
Pool
MP
Pool
MP
A
Figure 10: Architecture for graph classification.
X
MP (linear)
X
MP
MP
Pool
Unpool
MP
MP
Figure 11: Architecture for the autoencoder.
X
Global pool
Dense (linear)
MP
Pool
MP
A
Figure 12: Architecture for graph regression.
14


Reviews:
[{"review_id": "Hyey1w5AtS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "This paper proposes a solution to the important problem of pooling in graph neural networks. The method relies on minimizing a surrogate function inside the standard SGD loop and in conjunction with the optimization of the model parameters - such loss function aiming at optimizing the minCut on the graph. By that it aims to effective achieve a soft clustering of nodes that are both well connected and that have similar embeddings. This in an elegant choice, somewhat resembling the DiffPool method since it's also end-to-end trainable. However it adds the local graph connectivity information due to the minCut loss (and related orthogonality penalty to achieve non trivial solutions on the relaxed minCut continuous problem). Such local graph connectivity is indeed important information to consider when carrying out pooling.\nResults show good performance improvement on different tasks of graph clustering, node and whole graph classification. The paper is well written and clear to read. The math is solid and the concept is well substantiated by results.\nI found no mention about code release and I would solicit the authors to release the code to reproduce the experiments.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "H1gU4xse9B", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 authors propose a differentiable pooling method for graph data, known as minCUTpool. It learns a clustering assignment matrix using MLPs and then add regularization terms to encourage the clustering results close to the minCUT. The experimental results show that the regularization terms can help improve the performance.\n\nCons:\n1. The novelty is limited. Compared with existing work DiffPool, the proposed method is improving the Diffpool by adding two regularization terms. In addition, the main regularization $L_c$ is already proposed in previous studies. \n2. The motivation is not clear. Why should we apply minCut for graph pooling? Intuitively, how is the minCUT related to graph representation learning? The minCut can identify dense graph components but why these dense components should be different clusters in graph pooling? In addition, the author claim “cluster together nodes which have similar features”. How could minCut terms lead to such conclusion? \n3.  Important baselines are missing, such as Sortpool (Zhang et al, An end-to-end deep learning architecture for graph classification, AAAI 2018), Self-attention pool (Lee et al, Self-Attention Graph Pooling, ICML 2019). \n4. The graph classification results are not convincing enough. In the original Top-K paper (Gao et al , Graph U-Net, ICML2019), the reported results for Proteins and DD datasets are 77.68%, 82.43%, which are significantly better than the results reported in this paper. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "BJgfMuCt5S", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "This paper proposes a graph pooling method by utilizing the Mincut regularization loss. It is an interesting idea and performs well in a number of tasks. However, due to the limitation of novelty and poor organizations, this paper cannot meet the standard of ICLR. The detailed reasons why I give a weak reject are listed as follows:\n\n1. Even though the proposed minCUT pool is interesting, the contribution is not enough to get published in the ICLR. If I understand correctly, the only difference is the unsupervised loss, compared with the previous work, Diffpool [1].\n \n2. The paper needs to be reorganized to demonstrate its contribution. The proposed method section only has around 1.5 pages, making it difficult to understand the proposed method clearly. Therefore, more details and analyses about the proposed method should be included to support and clarify the idea.\n \n3. The paper needs to be improved for its theoretical derivations and proof. For example, it is not clear why Equation (6) is correct, which is the main contribution of this paper. The authors provide intuitive thoughts but there are not theoretical derivations and proof. The term $L_c$ comes from Equation (2) but why is it correct to only compute the trace?\n \n4. Some experiments cannot support the claim very well.  For example, the graph clustering experiments are not convincing. The goal of graph pooling is to learn high-level graph embeddings but not perform graph clustering. It is not proper to evaluate the graph pooling method using graph clustering tasks. Or, the author should clarify the motivation to do this experiment. If the model is trained for graph classification or node classification, then why should the node clusters lead to high NMI or CS scores?\n\n[1]. Ying et al., Hierarchical Graph Representation Learning with Differentiable Pooling, NIPS 2018\n\n\n==========Update===========\n\nI have read authors response and other reviews. While the authors address some of my concerns, I still believe the contribution/novelty is limited. I am sticking to my score.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Two reviewers are negative on this paper while the other reviewer is positive. Overall, the paper does not make the bar of ICLR. A reject is recommended.
Decision: Reject