Graph Pooling by Edge Cut
Authors: Alexis Galland
marc lelarge
Venue:  (2021)
Keywords: graph
deep
learning
pooling

Abstract: Graph neural networks (GNNs) are very efficient at solving several tasks in graphs such as node classification or graph classification. They come from an adaptation of convolutional neural networks on images to graph structured data. These models are very effective at finding patterns in images that can discriminate images from each others. Another aspect leading to their success is their ability to uncover hierarchical structures. This comes from the pooling operation that produces different versions of the input image at different scales. The same way, we want to identify patterns at different scales in graphs in order to improve the classification accuracy. Compared to the case of images, it is not trivial to develop a pooling layer on graphs. This is mainly due to the fact that in graphs nodes are not ordered and have irregular neighborhoods. To aleviate this issue, we propose a pooling layer based on edge cuts in graphs. This pooling layer works by computing edge scores that correspond to the importance of edges in the process of information propagation of the GNN. Moreover, we define a regularization function that aims at producing edge scores that minimize the minCUT problem. Finally, through extensive experiments we show that this architecture can compete with state-of- the-art methods.

Under review as a conference paper at ICLR 2021
GRAPH NEURAL NETOWRK POOLING BY EDGE CUT
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph neural networks (GNNs) are very efficient at solving several tasks in graphs such as node classification graph classification. They come from an adaptation of convolutional neural networks on images to graph structured data. These models are very effective finding patterns in images that can discriminate images from each others. Another aspect leading to their success is their ability to uncover hierarchical structures. This comes from the pooling operation that produces different versions of the input image at different scales. The same way, we want to identify patterns at different scales in graphs in order to improve the classification accuracy. Compared to the case of images, it is not trivial to develop a pooling layer on graphs. This is mainly due to the fact that in graphs nodes are not ordered and have irregular neighborhoods. To aleviate this issue, we propose pooling layer based on edge cuts in graphs. This pooling layer works by computing edge scores that correspond to the importance of edges in the process of information propagation of the GNN. Moreover, we define a regularization function that aims at producing edge scores that minimize the minCUT problem. Finally, through extensive experiments we show that this architecture can compete with state-of- the-art methods.
INTRODUCTION
Convolution neural networks (LeCun et al. (995) have been proven to be very efficient at learning meaningful patterns for many articificial intelligence tasks. They convey the ability to learn hier- archical informations in data with Euclidean grid-like structures such images and textual data. Convolutional Neural Networks (CNNs) have rapidly become sfate-of-the-art methods the fields of computer vision (Russakovsky et al. 2015) and natural language processing (Devlin et al. 2018).
However in many scientific fields, studied data have an underlying graph or manifold structure such as communication networks (whether social or technical) or knowledge graphs. Recently there have been many attempts to extend convolution to such non-Euclidean structured data (Hammond et al.. 2011 Kipf & Welling 2016; Defferrard et al., 2016). In these approaches, the authors propose to compute node embeddings in a semi-supervised fashion in order to perform node classification. Those node embeddings can also be used for link prediction by computing distances between each node of the graph (Hammond et al., 2011: Kipf & Welling 2016).
An image can be seen as a special case of graph that lies on a 2D grid and where nodes are pixels and edges are weighted according to the difference of intensity and to the distance between two pixels (Zhang et al. 2015 Achanta & Susstrunk 2017 Van den Bergh et al. 2012; Stutz al. 2018). In the emerging field of graph analysis based on convolutions and deep neural networks, it is appealing to try apply models that worked best in the field of computer vision. In this effort, several ways
to perform convolutions in graphs have been proposed (Hammond et al. 2011 Kipf & Welling 2016 Defferrard et al., [016 Gilmer et al., 2017 Veličković et al., 2017 Xu et al. Battaglia al. 2016; Kearnes et al. 2016). Moreover, when dealing with image classification, pooling an important step (Gao & Ji 2019 Ying et al., 2018 Defferrard et al. 2016; Dichl 2019). It allows us to extract hierarchical features in images in order to make the classinictiinn more accuracte. While it is easy to apply coarsening to an image, isn't 't obvious how to coarsen a graph since nodes in graphs not ordered like pixels in images. In this work present novel pooling layer based on edge scoring and related to the minCUT problem.
The main contributions of this work summarized below:

---

Under review as a conference paper at ICLR 2021
1. Learned pooling layer. A differentiable pooling layer that learns how aggregate nodes in clusters to produce a pooled graph of reduced size.
2. A novel approach based on edge cuts. We develop a novel pooling layer. Most coarsening strategies are based on nodes, either by finding clusters by deleting nodes that carry less information of the graph structure. In our approach, we focus on edges to uncover communities of topologically close nodes in graphs.
3. The definition of regularization that aims at approximating the problem of minCUT. We regularize our problem by a term that corresponds to the problem of Neut in order to learn edge scores and clusters that are consistent with the topology of the graph. We show that by computing an edge score matrix, we can easily compute this regularization term.
4. Experimental results. Our method achieves state-of -f---e---ttt------ art results on benchmark datasets. We compare with kernel methods and state-of satte-of-theaar the--ar message passing algorithms that use pooling layers as aggregation processes.
2 RELATED WORK
Recently there has been rich line of research, inspired by deep models in images, that aims redefining neural networks in graphs and in particular convolutional neural networks (Defferrard al. 2016: Kipf & Welling 2016; Veličković al. 2017 Hamilton et al.) 2017 Bronstein et al. 2017 Bruna et al. 2013; Scarselli et al. 2009). Those convolutions can be viewed as message passing algorithms that are composed of two phases Gilmer et al. (2017). They find their success in their ability to uncover meaningful patterss in graphs by propagating information from nodes to their neighbors. Moreover, many works on graph neural networks also focus on redefining pooling in graphs. The pooling operation allows to obtain different versions of the input graph at different scales. In graphs. the pooling step isn't It trivial because of the nature the data. Nodes can have different numbers of neighbors and graphs can have different sizes. To cope with these issues, different pooling strategies have been proposed:
Top-k: Like Gao & Jil (2019), the objective to score nodes according to their importance in the graph and then to keep only nodes with the top-k scores. By removing nodes we can remove important connections in the graph and produce disconnected graphs. step to increase connectivity is necessary. This is done by adding edges at 2-hops from the input graph.
Cluster identification: This is usually done by projecting node features on a learned weight obtain assignment matrix. Nodes that have close embeddings are projected on the same cluster. After having obtained the assignment matrix, super nodes at the coarsened level can be computed by aggregating all nodes that belong to the same cluster (Ying et al.) 2018)
Edge based pooling: An edge contraction pooling layer has recently been proposed by Dichl (2019). They compute edge scores in order to successively contract pairs of nodes, which means that they successively merge pairs of nodes that are linked by edges of the highest scores.
Deterministic coarsening strategies: Finally, a way to perform pooling graphs can simply be to apply a deterministic clustering algorithm in order to identify clusters of nodes that will represent super nodes in the coarsened level (Defferrard et al. 2016 Ying et al. 2018). The main drawback of it is that the strategy isn't 't learned and thus may not be suited to the graph classification task.
In this work we define a new pooling layer that is based on edge cuts. Like Diehl (019)) we focus our pooling method on edges instead of nodes. In their work, [iehl (2019) calculate scores on edges to perform contraction pooling. This means that at each pooling step, they merge pairs of nodes that are associated with the highest edge scores, without merging nodes that were already involved in contracted edge. This method results in pooled graphs of size divided by 2 compared to the input graph.
The main similarity with our work is that we compute edge scores to characterize edge importance inspired by Graph Attention Transform (Veličković et al. 2017). There are several differences with
2

---

Under review as a conference paper at ICLR 2021
the pooling layer that propose in this work. We want our pooling layer not to be constrained by number of communities or by a predefined size of pooled graph. Moreover, our pooling layer works by edge cuts and the goal is to remove edges that minimize the minCUT problem (Stoer & Wagner 1997). Once edges are cut, the graph is no longer connected and is composed of several connected components. These connected components correspond super nodes in the coarsened level. In this work, we will first introduce the pooling architecture based on edge scoring in section 3.1 We will then relate this pooling layer to the minCUT problem in section 3.2 We will finally compare this pooling layer to state-of-the -hrt methods on benchmark datasets on graph classification task and node classification task in section
POOLING ARCHITECTURE
When designing pooling layer, most algorithms need number of classes for the pooling layer that is usually set as a hyperparameter. This is very restrictive especially when working on graphs of different sizes. Indeed, the pooling layer should cluster nodes according to the topology of the graph without being constrained by a number of classes. In this section we present our pooling layer that is based on edge cutting and that does not necessitate any a priori on the number of classes that needs to be found.
3.1 GNNS
Let G XX) be a graph composed of set of nodes V, a set of edges E and node feature matrix X E fo where fo is the dimensionality of node features. We denote by A the adjacency matrix.
Graph neural networks. We build our work upon graph neural networks (GNNs). There are several architectures of graph neural networks that have been proposed by Defferrard et al. (2016): Kipt & Welling (2016); Veličkovié et al. (2017) or Bruna & Li (2017). Those graph neural network models are all based on propagation mechanisms of node features that follow a general neural message passing architecture (Ying et al. 2018 Gilmer et al. 2017):
z(+1) MPA, 20, W())
where 2(0 Raxf: are node embeddings computed after steps of MP, Z X, and MP is the message propagation function, which depends on the adjacency matrix. ( is trainable weight matrix that depends on layer and fi is the dimensionality of node embeddings.
The pooling layer that we introduce next be used with any neural message passing algorithm that follows the propagation rule In all the following of our work we denote by M the algorithm. For the experiments, we consider the Graph Convolutional Network (GCN) defined by (Kipf & Welling 2016). This model is based on an approximation of convolutions on graphs defined by (Defferrard al. 2016) and that use spectral decompositions of the Laplacian. is very popular because is very efficient computationally and obtains state-of-thed of-the-art results on benchmark datasets. This layer propagates node features 1-hop neighbors. Its propagation rule the following:
zu+1) MPMA,, 20); w()) GCN 20) p -
(2)
Where p is a non-linear function (a ReLU in our case), À = A + I,, is the adjacency matrix with added self-loops and D; = Σ3 Aij is the degree diagonal matrix associated with adjaceney matrix Á.
Scoring edges. After layer I, each node in the graph has an embedding n To simplify notations, consider all matrices be associated to layer l and we do not keep the exponant l. For example, we write feature node i at layer 1, Z; and its dimensionality is denoted by f- Based on these embeddings, we develop scoring function that characterizes the importance of each edge of the graph. The input of our scoring algorithm is a set of node features, {21,.., Zn} E Rnxs, The scoring function produces a matrix S ux* associated with layer i, Si, = ((,))R # Sty where sij the score of edge (i,
3

---

Under review as a conference paper at ICLR 2021
In order to compute the score of each edge of the graph, apply shared linear transformation, parametrized by a weight matrix Wooot E I xd. to each node of the graph, d being the output size of the linear transformation. We then perform self-attention on nodes, used in the Graph Attention Network (GAT) (Veličkovié et al. 2017). by applying a shared weight a R x R + to obtain a score edge (f,J)= E::
Sij (all poot Wi|lW
poot 2y))
(3)
Where a is the sigmoid function, W poot and a are trainable matrices associated with layer / and [oooo poost 2,0 R2d a vector that is the concatenation of W Wpoot Z; and W Zo Let's note that this scoring function isn't symmetric and depends the order of nodes. We can symmetrize this function by computing
Sij (o(a pool Zill poot 2,)) + (a pool poot Zyll pool Zi)))
By applying the sigmoid function to the attention mechanism we compute an importance of edges. The goal is to obtain a distribution on edges for whose nodes that are close topologically have an edge which value is close to 1. In the opposite case, we would like an edge to have weight close to if links two nodes that do not lie the same community. By doing so we would like to solve the minimum cut problem in graphs.
After having computed the edge score matrix, we keep ratio of edges that correspond to edges with the r% higher scores. We obtain a threshold Sthreshold that corresponds to the n percentile of the distribution of edge scores. This way, cut edges which scores close to 0 in the graph. Edges with the smallest scores represent edges that link nodes that aren't 't in the same community and thus by cutting those edges, separate the graph into several clusters. We denote by Seut the score matrix with values under Sthreshold truncated to O. Each row is renormalized by the number of positive components. This renormalization is useful in the following compute node features in the coarsened level.
v(i,j) 22, Seutij
Sij 1 29threshold
18; 2ehreshhald JEN(1)
Σ
We then extract the connected components of the new graph with cutted edges. Those connected components represent super nodes in the pooled graph. We obtain cluster assignment matrix C' Taaxe being a free parameter that isn't fixed and that can vary during the training of the algorithm. After layer the pooled adjacency matrix and the pooled feature matrix are thus:
A0+1) = -1)
Pool poot = CO1 19C00
z(++1 = poot C(O
(()) cul 2
Remark. The multiplication by Seut 7 makes the weights W poot and a trainable by back-propagation. Otherwise it wouldn't be the case because the function that outputs the matrix C' by finding connected components from matrix Sout is not differentiable. Moreover, this multiplication weights the importance of each node feature in the super node of the coarsened level. In order to compute the feature Z₁ of cluster (or super node) k. we compute node importance score Scuti at layer for each node of the graph:
Σ
Scuti
Σ
1
Scutij
(s
Seutty (EN(
The feature Z& of cluster l is then weighted mean of the features of nodes that belong to cluster k:
Z₁=
Σ
Seut
Moreover, for edge scores to be consistent with the minCUT algorithm, we add a regularization term that we define in the next section.
4

---

Under review as a conference paper at ICLR 2021
977
oa
0. 0.9
(a)
(b)
Figure 1: figure la scores are computed and edges with the smallest scores (in red) are cut. After having cut edges, identify connected components in (bblckk lines edges mean that those edges have been removed). We finally merge nodes that belong to the same cluster and reconstruct the edges between clusters as shown in figure Ic
3.2
MIN CUTS
Graph Cuts. In community detection, the min cut problem aims at finding the separation, between disjoint subsets, that minimizes the cut. For two disjoint subsets V1, V/2 C. V we define
cut (Vi 1/2)
Aij REV.
Σ
Given a similarity graph with adjacency matrix the simplest and most direct way to construct partition is to solve the mincut problem. This consists of choosing the partition Vi..., V. of V which minimizes
(V Vo) = Σ Cuu(Vi, Vi))
When solving this problem, the solution often boils down to separating one indivual vertex from the rest of the graph. In order to circumvent this problem, other objective functions can be defined such as RatioCut (Hagen & Kahngl 1992) or the normalized cut (NCut) (Shi & Malik 2000). Those objective functions defined as follow:
RatioCut(Vi... Vo)
cut(Ve.Vo) V.) V
Neut(V Vo)
eue(Vi Vg. Vi2. vol Vv)
Where |Va| is the number of vertices in V/ and vol
Σ d, These objectives tend ieVi
to produce balanced communities, in terms of number of edges in terms of weights inside the communities.
It can be proved that solving these objectives is equivalent to solving optimization problems derived
5

---

Under review as a conference paper at ICLR 2021
from spectral decompositions of graphs (Von Luxburg al. 2008). An approximation of the Ratio Cut can be obtained by the minimazation the following problem:
min Tr(H" LH) s.t. H =
HER
An approximation of the Normalized Cut can be obtained by minimizing the following problem:
min
Dr(U"D-V/'LD- s.t. UT-=
(5)
UERaxe
In their work, Bianchi et al. (2199) develop a pooling layer that aims at minimizing the minCUT problem. By calculating an assignment matrix C' as in (Ying et al. 2018) based the projection of node embeddings on a cluster matrix, they are able to minimize problem by adding regularization term that depends on the assignation matrix C.
In our work, the assignment matrix C does not include the information of learnable parameters since it is computed by looking at the connected components of the graph after having cut the less informative edges. But the Normalized Cut of the partition of the graph can be computed easily from the edge score matrix S. If we compute the matrix Ment C SC E Rexe, we obtain the super node matrix in which each diagonal parameter represents the sum of the edge weights inside each
cluster (super node). Moreover, Σ Meutis Lige represents the sum of the weights between cluster
and the rest of the graph. With those matrices, we easily compute Neut(Vi, Ve) layer / for a graph G. We thus add a regularization term equal to:
Meutiy Lidj
Lreg Neut(VV, Vc) = Σ
(6)
Meutit
1=1
EXPERIMENTS
4.1
GRAPH CLASSIFICATION
We choose a wide variety of benchmark datasets for graph classification to evaluate our model. The datasets can be separated two types. 2 bioinformatics datasets: PROTEINS and D&D; and social network dataset: COLLAB. In the bioinformatics datasets, graphs represent chemical compounds. Nodes are atoms and edges represent connections between two atoms. D&D and PROTEINS contain two classes of molecules that represent the fact the molecule can be either active or inactive against a certain type of cancer. The aim is to classify the molecules according to their anti-cancer activity. COLLAB is composed of ego-networks. Graphs' labels are the nature of the entity from which we have generated the ego-network. More details can be found in (Yanardag & Vishwanathan 2015).
Datasets:
We perform 10-fold cross validation split which gives 10 sets of train, validation and test data indices in the ratio 8:1:1. We use stratified sampling to ensure that the class distribution remains the same across splits. We fine tune hyperparameters fi and de the dimensions of features in each layer, r the cut ratio, Ir the learning rate respectively chosen from the sets (256, 512, 1024), {32, 64, 128), (10% 30%, 50%, 70%, 90%) and {0.01, 0.001). We do set maximum number of epochs but we perform early stopping to stop the training which means that we stop the training when the validation loss has not improved for 50 epochs. We report the mean accuracy and the standard deviation over the 10 folds on the test set. We compare our method with kernel methods and with graph neural networks that use pooling layers (Ying et al. 20188] Gao Ji 2019). We should note that kernels methods do not node features that available bioinformatics datasets.
Experimental setup:
Results: From the results of Table I we can observe that our pooling layer is challenging with state-of-the-art methods. Indeed, on most datasets, the score of our model is very close to those obtained by Gao & Ji (2019) and our model outperforms Ying al. (208)) these datasets. From

---

Under review as a conference paper at ICLR 2021
Table 1
EdgeCut competes with all algorithms COLLAB.
Dataset
D&D
PROTEINS
COLLAB
Max
5748
620
492
Avg
284.32
39.06
74.49
#Graphs
1178
1113
5000
Graphlet
74.85
72.91
64.66
Shortest-Path
78.86
76.43
59.10
1-WL
74.02
73.76
78.61
WL-OA
79.04
75.26
80.74
GraphSage
Hamilton et al.
2017)
75.42
70.48
68.25
DGCNN
Zhang et al. 2018
79.37
76.26
73.76
DIFFPOOL.
Ying et al. 2018)
80.64
76.25
75.48
U-U-Nets Gao & Ji 2019
82.43
77.68
77.56
EdgeCut
80.33 + 0.05
76.42 + 0.23
77.23 0.11
Table Classification accuracy on bioinformatics datasets
4.2 NODE CLASSIHICATION
Datasets: For node classification conduct experiments three real-world datasets, Cora, citeseer and Pubmed. They are three citations networks where nodes are articles that are linked together by edge if there exists citation between them. All datasets contain attributes nodes that are extracted from the title and the abstract. Attributes represent sparse bag-of bag-of-word vectors.
Dataset
Nodes
Features
Classes
Training
Validation
Testing
Degree
Cora
2708
1433
140
500
1000
4
Citeseer
3327
3703
120
500
1000
5
Pubmed
19717
500
60
500
1000
Table Statistics on node classification datasets. The classification is made with nodes per class in the training set.
Experimental setup: We split the edges into a training, a test and a validation set according to the splits used by Kipf & Welling (016). We fine tune hyperparameters and d, the dimensions of features in each layer, r the eut ratio, Ir the learning rate respectively chosen from the sets (256, 512, 1024), {32, 64, 128]. (10% 30%, 50%, 70%, 90%) and {0.01, 0.001}. We do a maximum number of epochs but we perform early stopping to stop the training which means that stop the training when the validation loss has not improved for 50 epochs. We report the mean accuracy and the standard deviation after several iterations of the algorithm on each set of hyperparameters. We compare our method with graph neural networks that uses pooling layers and with other graph neural networks referenced in table
We denote by EdgeCut without regularization the version of our algorithm that isn't regularized by the minCUT term introduced in equation 6 We denote by EdgeCut the version regularized. We conduct an ablation study and we show results in table to show the effects of the regularization term.
Architecture for node classification: In order to perform node classification with a pooling archi- tecture Graph U-Net model proposed by Gao & Jil (2019) and inspired by the works of (Ronneberger et al. 2013). Considering that images can seen as special cases of graphs that lie regular 2D lattices, have correspondance between image segmentation and node

---

Under review as a conference paper at ICLR 2021
Graph U-Nets
GCN
GCN
Inputs
PPol
Uuppool
Network Embedding
piipool
GCN
Figure 2: Graph U-Net model from (Gao & 2019). is composed of successive convolution and pooling layers. After this encoder part, the decoder is composed of convolutions and unpooling layers. Unpooling layers reconstruct the graph and mirror the pooling layers of the encoder.
classification in graphs. By using graph convolutional layers, node information is propagated in order to identify clusters of nodes that topologically close and that are pooled together during the training of the algorithm. During the encoder part, we store the successive pooled graphs in order to perform unpooling during the decoder part. The unpooling layer is just a mirror of the pooled graph at the corresponding level in the encoder part as illustrated in figure
Models
Cora
Citeseer
Pubmed
DeepWalk Perozzi al.
2014
67.2%
43.2%
65.3%
Planetoid
Yang et al.
2016
75.7%
64.7%
77.2%
Defferrard Chebyshev
et al.
2016
81.2%
69.8%
74.4%
GCN
Kipf Welling
2016
81.5%
70.3%
79.0%
GAT
Veličković al.
2017
83.0 d: 0.7%
72.5 = 0.7%
79.0 + 0.3%
EdgeCut without regulazization
81.9 +: 0.8%
69.8 + 0.7%
78.7 + 0.3%
EdgeCut
82.3 + 0.6%
70.9 + 0.5%
+ 0.4%
Table 3: Classification accuracy on node classification datasets.
CONCLUSION
In this work we developed novel pooling layer based edge cuts in graphs. This approach is novel because focuses on edges to coarsen the graph. We proposed a method to compute edge scores in order to evaluate edge importance in graphs. By cutting the less informative edges, we are able to split the graph into several connected components that represent our super nodes in the coarsened level. The process of removing edges is directly linked to the problem of minCUT. By adding regularization term that corresponds to the problem of Normalized Cut we give more consistence to the of edges and cut edges that allow to split the graph into communities that relevant to the problem of minCUT. We finally showed through extensive experiments that this novel approach competes with state-of-the-an methods.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Radhakrishna Achanta and Sabine Susstrunk. Superpixels and polygons using simple non-iterative clustering. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4651-4660, 2017.
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. In Advances in neural information processing systems, pp. +502-4510 2016.
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Mincut pooling in graph neural networks. arXiv preprini 1907:00977 2019.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-44 2017.
Joan Bruna and Xiang Li. Community detection with graph neural networks. arXiv preprint 1rXivv170S.08415, 2017.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv: 1312.6233 2013.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, pp. 3844-3852 2016.
Jacob Devlin, Ming-Was Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint I 1000048 2018.
Frederik Diehl, Edge contraction pooling for graph neural networks. arXiv preprint arXiv: 1905. 109900 2019.
Hongyang Gao and Shuiwang Ji. Graph u-nets. arXiv preprint arXiv:9005.05178 2019.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference Machine KtarningVVolume 70, 1263-1272. JMLR. org, 2017.
Lars Hagen and Andrew Kahng. New spectral methods for ratio cut partitioning and clustering. IEEE transactions on computer-aided design of integrated circuits and systems, 1074 1992.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs In Advances in neural information processing systems, pp. 1024-1034, 2017.
David K Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129-150) 2011.
Steven Kearnes, Kevin McCloskey, Mare Berndl, Vijay Pande, and Patrick Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of computer-aided molecular design, 30(8): 595-608, 2016.
Thomas N Kipf and Max Welling. Semi semi--uperviied classification with graph convolutional networks. arXiv preprint arXiv: 1609.0000000 029077 2016
Yann LeCun, Yoshua Bengio. et al. Convolutional networks for images, speech, and time series. The handbook of bruin theory and neural networks, (10) 1995.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.

---

Under review as a conference paper at ICLR 2021
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In International Conference on Medical image computing and computer- assisted intervention, pp. 234-241 Springer. 2015.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):211-255 252,, 2015.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions Neural Networks, 20(1):61-80, 2009.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions pattern analysis and machine intelligence, 22(8):888-99) -008889-5,-00 2000.
Mechthild Stoer and Frank Wagner. A simple min-cut algorithm. Journal of the ACM (JACM), 44(4): 585-591, 1997.
David Stutz, Alexander Hermans, and Bastian Leibe. Superpixels: evaluation the state-of-the- art. Computer Vision and Image Understanding, 166:1-27, 2018.
Michael Van den Bergh, Xavier Boix, Gemma Roig, Benjamin de Capitani, and Luc Van Gool. Seeds: Superpixels extracted via meigeyddriven sampling. European conference on computer vision, pp. 13 Springer, 2012.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
Ulrike Von Luxburg, Mikhail Belkin, and Olivier Bousquet. Consistency of spectral clustering, The Annals of Statistics, pp. 555-586, 2008.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 1rXiv:1810.00826 2018.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374. ACM, 2015.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp. 40-48. PMLR, 2016.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems, pp. 4800-4810, 2018.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Xuewen Zhang, Selene E Chew, Zhenlin Xu, and Nathan Cahill. Slic superpixels for efficient graph-based dimensionality reduction of hyperspectral imagery. In Algorithms and Technologies for Multispectral, Hyperspectral, and Ultraspectral Imagery XXI, volume 9472, pp. 947209. International Society for Optics and Photonics, 2015.
10


Reviews:
[{"review_id": "zg4YDOBqtkj", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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 paper proposes a novel pooling layer for graph neural networks. Pooling in GNNs amounts to merging nodes that are very similar through the layers. Specifically, the paper proposes to merge nodes whose edges have a high score according to the edge cuts. The edge score in practice is computed in each layer using an attention mechanism on the concatenated representations of the edge’s nodes from that layer. The authors then choose a fixed ratio r of the top edges to keep, in an effort to remove edges of nodes from distant communities. The edge score matrix which is n x n stores all the scores and is truncated based on the aforementioned threshold, renormalized, and used to extract the connected components simply from disconnected areas of the matrix. In the following layer, the clusters form super-nodes and their representations are a weighted combination of each individual node’s representation.\n\nStrong points:\n\n--- The overall idea is very interesting as it is utilizing the minCUT algorithm in the context of GNN, and coarsening could indeed be a promising approach to better GNN’s accuracy.\n\n--- The paper is well-written and the different concepts are clearly presented.\n\nConcerns:\n\n--- There are several concerns, the main being about the novelty of the approach since the minCUT problem has been addressed already in a previous work (as the authors also mention). In this case, the authors should describe in detail how Eq. 6 and the computation of S and C result in minimizing the graph cut to underline the difference from the previous work and show that this work is not derivative.\n\n--- The second problem adheres to the experimental section. The authors utilize very few datasets for evaluation. There is a plethora of graph classification and node semi-supervised learning datasets, ranging from OGB (https://ogb.stanford.edu/) to the Dortmunt repository (https://ls11-www.cs.tu-dortmund.de/staff/morris/graphkerneldatasets).  It is also sensible to test the model in larger networks as the coarsening may be less effective due to giant components and the distribution of edges\n\n--- Moreover, the results do not surpass the benchmarks, even seminal ones like GAT, which calls into question the usefulness of the approach. Is there any justification for that?\n\n--- Finally, there is a hyperparameter r which needs at least a strategy to choose it from and a sensitivity analysis to understand its effect on the final outcome.", "extra_scores": {}, "extra_text": {}}, {"review_id": "vlqTqWqjcaq", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Summarization\n\nThe authors propose a novel pooling layer based on edge cuts in graph, where a regularization function is introduced to produce edge scores via minimizing the minCUT problem. Through extensive experiments, the authors have proved the proposed EdgeCut pooling structure can achieve comparable performance in various graph analysis tasks.\n\nStrong points\n\n1) The paper is good writing and easy to understood. As far as I know, the proposed EdgeCut is a novel pooling layer based on edge cutting, which is reasonable and can explore hierarchical graph structures.\n2) The authors have provided code in supplement and the experimental results are easy to follow.\n\nWeak points\n\nThe main weakness could be the model performance and there are not enough experiments to prove the efficiency of the proposed EdgeCut.\n\n1) For graph classification in Table.1, any thought about the reason why the proposed EdgeCut is worse than g-U-Nets.  And there is no detailed experimental analysis in Section 4.1\n\n2) Similar question, for node classification in Table.3, the performance of EdgeCut is still worse than GAT in two of three datasets, and even only obtains a slight improvement compared to the most basic GCN in Table 3. Notably, the performance of EdgeCut without regulazization is even worse than GCN in both Citeseer and Pubmed datasets. The authors should provide more comprehensive experimental analysis and explain the reason why the performance improvement is so slight and even worse than the basic GCN.\n\n3) There are only two quantitative experiments in this paper, additional qualitative experiments like the visualizations of graphs after pooling should also be included to prove the model efficiency, even making use of toy data.\n\nQuestions:\n\nMy questions have been included in Weak points part\n\nAdditional Feedback:\n\n1) Can you provide time complexity comparisons for the proposed EdgeCut and other baselines", "extra_scores": {}, "extra_text": {}}, {"review_id": "M5RLQ1eMDJV", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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 manuscript proposes a new pooling layer in Graph Neural Networks (GNN). By computing certain scores on edges which indicate the importance of edges in the process of information propagation, top r% edges are selected and a pooled graph is constructed by considering the connected components to be super nodes. The authors tried to explain some connection between their pooled graph and the normalized cut problem, which is not clearly stated in the manuscript. Even though the manuscript explores an interesting and timely topic, their approach is not technically appealing and the explanations are not enough to thoroughly understand the authors' ideas. My main concerns and major questions are as follows:\n\n#1. In Section 3.1 (page 4), how $W_{pool}$ and $a$ can be considered as trainable variables and how these variables are actually trained are not clear. \n\n#2. Even though the authors argue that the number of clusters needs not be specified in advance, one should determine $r$ in their method instead.  In the experiments, the authors just tried several values for this $r$ value. There should be some rules to appropriately set this $r$ value. I'm wondering if it is possible to look at the distributions of edge scores and determine an appropriate $r$ value.\n\n#3. The descriptions about the relationship between their clustering approach (i.e., forming super nodes by taking the connected components) described in Section 3.1 and the graph normalized cut problem described in Section 3.2 are not clear. Where and how $L_{reg}$ is used in their proposed method?\n\n#4. Experimental results do not support that the proposed method is better than existing methods. Given this limited empirical contributions, I'm wondering if the proposed method has any theoretical benefits over existing methods.", "extra_scores": {}, "extra_text": {}}, {"review_id": "K58H8p9iIec", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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\nThis paper presents a graph pooling operator by first predicting scores on edges, then performing min-cut to separate subgraphs, and finally construct coarsened graphs. Authors perform experiments on several small datasets to verify their claims.\n\nPros:\n\n1, The problem of defining pooling operators on graphs is important. The proposed idea is straightforward and easy to follow.\n\n2, The writing of the paper is smooth.\n\nCons & Questions & Suggestions:\n\n1, The idea is not novel. Normalized cut type of methods for graph coarsening have been investigated by quite a few works, e.g., [2]. The proposed pooling operator is not fully differentiable since the gradient through the min-cut optimization is not exploited. Therefore, it is less appealing compared to methods like diff-pool. Moreover, the empirical performance is only comparable to diff-pool on few datasets. I am further concerned about the efficiency of the proposed method since min-cut on large-scale graphs is slow which would significantly slow down the inference of GNNs. However, this part is not discussed or empirically investigated.\n\n2, The experiment section is not that convincing. First, the performances are worse compared to other baselines. For example, the numbers in Table 1 are worse than g-U-nets consistently (I do not know why authors bold their results which are clearly not the best). Second, authors should include more graph pooling baselines, e.g., the ones with similar min-cut objectives like [2]. At last, it would be great to extensively test the proposed method on a wider range of datasets since the ones used for now are small-scale and many baselines achieve similar performances anyway.\n\n3, I think it is necessary to discuss or at least mention the original GNN paper [1] in the literature review. \n\n[1] Scarselli, F., Gori, M., Tsoi, A.C., Hagenbuchner, M. and Monfardini, G., 2008. The graph neural network model. IEEE Transactions on Neural Networks, 20(1), pp.61-80.\n\n[2] Defferrard, M., Bresson, X. and Vandergheynst, P., 2016. Convolutional neural networks on graphs with fast localized spectral filtering. In NeurIPS.\n\nConclusion: Overall, I do not think the paper is ready for being published.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a graph pooling mechanism based on adaptive edge scores that are then fed into a min-cut procedure. 
Reviewers acknowledged that this is an important topic of study, but all agreed that the current manuscript does not provide enough evidence about the significance and novelty of their proposed approach. 
The AC recommends rejection at this time, and encourages the authors to build from the reviewers feedback to improve upon their current work. 
Decision: Reject