Accurate Learning of Graph Representations with Graph Multiset Pooling
Authors: Jinheon Baek
Minki Kang
Sung Ju Hwang
Venue: ICLR 2021 Poster (2021)
Keywords: Graph representation learning
Graph pooling

Abstract: Graph neural networks have been widely used on modeling graph data, achieving impressive results on node classification and link prediction tasks. Yet, obtaining an accurate representation for a graph further requires a pooling function that maps a set of node representations into a compact form. A simple sum or average over all node representations considers all node features equally without consideration of their task relevance, and any structural dependencies among them. Recently proposed hierarchical graph pooling methods, on the other hand, may yield the same representation for two different graphs that are distinguished by the Weisfeiler-Lehman test, as they suboptimally preserve information from the node features. To tackle these limitations of existing graph pooling methods, we first formulate the graph pooling problem as a multiset encoding problem with auxiliary information about the graph structure, and propose a Graph Multiset Transformer (GMT) which is a multi-head attention based global pooling layer that captures the interaction between nodes according to their structural dependencies. We show that GMT satisfies both injectiveness and permutation invariance, such that it is at most as powerful as the Weisfeiler-Lehman graph isomorphism test. Moreover, our methods can be easily extended to the previous node clustering approaches for hierarchical graph pooling. Our experimental results show that GMT significantly outperforms state-of-the-art graph pooling methods on graph classification benchmarks with high memory and time efficiency, and obtains even larger performance gain on graph reconstruction and generation tasks.

Published as a conference paper at ICLR 2021
ACCURATE LEARNING OF GRAPH REPRESENTATIONS WITH GRAPH MULTISET POOLING
Jinheon Baek Minki Kang': ;
Sung Ju Hwang!
KAIST", AITRICS", South Korea
[jinheon. baek, 2zxc1133, sjhwangg2)ekaiss.acc
ABSTRACT
Graph neural networks have been widely used on modeling graph data, achiev- ing impressive results on node classification and link prediction tasks. Yet, ob- taining an accurate representation for a graph further requires a pooling function that maps set of node representations into compact form. A simple sum average over all node representations considers all node features equally with- out consideration of their task relevance, and any structural dependencies among them. Recently proposed hierarchical graph pooling methods, on the other hand, may yield the same representation for two different graphs that are distinguished by the Weisfeiler-Lehman test, as they suboptimally preserve information from the node features. To tackle these limitations of existing graph pooling meth- ods, we first formulate the graph pooling problem as a multiset encoding problem with auxiliary information about the graph structure, and propose a Graph Multi- set Transformer (GMT) which is a multi-head attention based global pooling layer that captures the interaction between nodes according to their structural dependen- cies. We show that GMT satisfies both injectiveness and permutation invariance, such that at most as powerful as the Weisfeiler-Lehman graph isomorphism test. Moreover, our methods can be easily extended to the previous node cluster- ing approaches for hierarchical graph pooling. Our experimental results show that GMT significantly outperforms state-of-the-art graph pooling methods graph classification benchmarks with high memory and time efficiency, and obtains even larger performance gain on graph reconstruction and generation tasks
INTRODUCTION
Graph neural networks (GNNs) (Zhou et al. 2018 Wu et al. 2019), which work with graph struc- tured data, have recently attracted considerable attention, as they can learn expressive representations for various graph-related tasks such as node classification, link prediction, and graph classification. While the majority the existing works on GNNs focus on the message passing strategies for neigh- borhood aggregation (Kipf & Welling [017 Hamilton et al.] (017). which aims to encode the nodes in a graph accurately, graph pooling Zhang et al. 2018;) Ying et al., 2018) that maps the set of nodes into a compact representation is crucial in capturing meaningful structure of an entire graph.
As a simplest approach for graph pooling, we can average or sum all node features in the given graph (Atwood & Towsley 2016 Xu et al. 2019) (Figure I (B)). However, since such simple ag- gregation schemes treat all nodes equally without considering their relative importance on the given tasks, they can not generate meaningful graph representation in task-specific manner. Their flat architecture designs also restrict their capability toward the hierarchical pooling or graph compres- sion into few nodes. To tackle these limitations, several differentiable pooling operations have been proposed to condense the given graph. There are two dominant approaches to pooling a graph. Node drop methods (Zhang et al.) 22018] Lee et al. (019b)) [Figure[[(C)) obtain score of each node using information from graph convolutional layers, and then drop unnecessary nodes with lower scores at each pooling step. Node clustering methods (Ying et al. 2018 Bianchi et al., 2019) (Figure [ (D)), on the other hand, cluster similar nodes into single node by exploiting their hierarchical structure.
"Equal contribution
Code available http://giitab.com///nhennaeeeeee

---

Published as a conference paper at ICLR 2021
A. Ours;
B. Simple; (GIN)
Original Graph
Graph Representation
Graph
Representation
Pooling
Readout
Multiset Encoding
Readout
C. Node Drop; (TopXPool, SAGPool)
D. Node Clustering: (DiffPool, MinCutPool)
Readout
Readout
Set B. Multiset Multiset
Graph
Message Passing
denotes the method that can as powerful as the W. test.
Concepts (Left); Conceptual comparison of graph pooling methods. Grey box indicates the readout layer, which is compatible with our method. Also, green check icon indicates the model that can be as powerful as the WL. test. (Right): An illustration of set, multiset, and graph multiset encoding for graph representation.
Figure 1:
Both graph pooling approaches have obvious drawbacks. First, node drop methods unnecessarily drop some nodes at every pooling step, leading to information loss on those discarded nodes. On the other hand, node clustering methods compute the dense cluster assignment matrix with an adjacency matrix. This prevents them from exploiting sparsity in the graph topology, leading to excessively high computational complexity (Lee et al. 2019b). Furthermore, to accurately represent the graph, the GNNs should obtain a representation that is as powerful as the Ceisfeiler-Lehmeee (WL) graph isomorphism test (Weisfeiler & Leman 1968), such that it can map two different graphs onto two distinct embeddings. While recent message-passee paasiggg-pasnnggggg operations satisfy this constraint (Morris et al.) 2019 Xu et al. 2019). most deep graph pooling works (Ying al. 2018 [ee et al.] [019b] Gao & 2019 Bianchi et al. 2019) overlook graph isomorphism except for a few (Zhang et (0118).
To obtain accurate representations of graphs, need graph pooling function that is powerful as the WL test in distinguishing two different graphs. To this end, we first focus on that the graph representation learning can be regarded as a multisel encoding problem, which allows for possibly repeating elements, since a graph may have redundant node representations (See Figure I right). However, since graph more than a multiset due to its structural constraint, we further define the problem as graph multiset encoding, whose goal is to encode two different graphs, given as multisets of node features with auxiliary structural dependencies among them (See Figure [ right), into two unique embeddings. We tackle this problem by utilizing graph-structured attention unit. By leveraging this unit as a fundamental building block, we propose the Graph Multiset Transformer (GMT), pooling mechanism that condenses the given graph into the set of representative nodes, and then further encodes relationships between them to enhance the representation power of a graph. We theoretically analyze the connection between pooling operations and WL test, and further show that our graph multiset pooling function can be easily extended to node clustering methods.
We then experimentally validate the graph classification performance of GMT on 10 benchmark datasets from biochemical and social domains, on which it significantly outperforms existing meth- ods on most of them. However, since graph classification tasks only require discriminative informa- tion, to better quantify the amount of information about the graph in condensed nodes after pooling, we further validate it on graph reconstruction of synthetic and molecule graphs, and also on two graph generation tasks, namely molecule generation and retrosynthesis. Notably, GMT outper- forms baselines with even larger performance gap on graph reconstruction, which demonstrates that it learns meaningful information without forgetting original graph structure. Finally, it improves the graph generation performance on two tasks, which shows that GMT can be well coupled with other GNNs for graph representation learning. In sum, our main contributions are summarized as follows:
We treat a graph pooling problem as a multiset encoding problem, under which we consider relationships among nodes in a set with several attention units, to make a compact representation of an entire graph only with one global function, without additional pessagg-passing operations.
We show that existing GNN with our parametric pooling operation can be as powerful the WL test, and also be easily extended to the node clustering approaches with learnalee clusters.
We extensively validate GMT for graph classification, reconstruction, and generation tasks on synthetic and real-world graphs, which it largely outperforms most graph pooling baselines.
2

---

Published as a conference paper at ICLR 2021
2 RELATED WORK
Graph Neural Network Existing graph neural network (GNN) models generally encode the nodes by aggregating the features from the neighbors (Kipf & Welling 2017: Hamilton al. 2017 Velickovic et al.) 2018: You et al., 2019), and have achieved a large success on node classification and link prediction tasks. Recently, there also exist transformer-basee GNNs (Nguyen et al. 2019 Rong et al. 2020) that further consider the relatedness between nodes in learning the node embed- dings. However, accurately representing the given graph as a whole remains challenging. While using mean or max over the node embeddings allow to represent the entire graph for graph clas- sification (Duvenaud et al. 2015; Dai et al. 2016), they are mostly suboptimal, and may output the same representation for two different graphs. To resolve this problem, recent GNN models (Xu ett al. M019iMorris et al. 2019) aim to make the GNNs to be as powerful as the Weisfeiler-Lehmen test (Weisfeiler& & Leman 1968) in distinguishing graph structures. Yet, they also rely on simple operations, and we need a more sophisticated method to represent the entire graph.
Graph pooling methods play an essential role of representing the entire graph While averaging all node features is directly used as simplest pooling methods (Atwood & Towsley 2016 Simonovsky & Komodakis 2017). they result in a loss of information since they consider all node information equally without considering key features for graphs. To overcome this limitation, there have been recent studies on graph pooling to compress the given graph in a task specific manner. Node drop methods use learnable scoring functions to drop nodes with lower scores (Zhang) jt al. 2018 Gao & Jil 2019 Lee et al., 2019b).. Moreover, node clustering methods cast the graph pooling problem into the node clustering problem map the nodes into set of clusters (Ying) et al., 2018: Ma et al., 2019 WWng et al. 2019, [Biachii et al.) 2019 Yuan & Ji 2020). Some methods combine these approaches by first locally clustering the neighboring nodes, and then dropping unimportant clusters (Kanjan et al. 2020). Meanwhile, edge clustering gradually merges nodes by contracting high-scoring edges between them (Dichl 2019). In addition, AAhmadi et al. (2020) model the memory layer to aggregate nodes without utilizing message-passingg
Graph Pooling
after pooling. Finally, there exists a semi cumi-supervieed pooling method (Li et al. 2019) that scores nodes with an attention scheme (Bahdanau et al. 2015), to weight more on the important nodes on pooling.
(Multi-)Set Representation Learning Note that a set of nodes in a graph forms a multiset (X et al. 2019); set that allows possibly repeating elements. Therefore, contrary to the previous set- encoding methods, which mainly consider non- non-graph problems (Qi et al., 2017a; Yi et al.] 2019) Snell al. 2017), we regard the graph representation learning Mathematically. Zaheer et al.] (2017) () Qi et al. (2017b) provide the theoretical grounds on permuta- tion invariant functions for the set encoding. Further, Lee et al. (2019a) propose Set Transformer, which uses attention mechanism on the set encoding. Building on top of these theoretical grounds on set, we propose the multiset encoding function that explicitly considers the graph structures.
multi-set encoding problem.
3 GRAPH MULTISET POOLING
We posit the graph representation learning problem as a multiset encoding problem, and then utilize the graph-structured attention consider the global graph structure when encoding the given graph.
3.1 PRELIMINARIES
We begin with the general descriptions of graph neural network, and graph pooling.
Graph Neural Network A graph G can be represented by its adjacency matrix A E (0, 1] ax and the node set V with [V] n nodes, along with the dimensional node features X E R Graph Neural Networks (GNNs) learn feature representation for different nodes using neighborhood aggregation schemes, which are formalized the following Message-Passingg function:
(I+)) = (PDATE(() ( (GGREGATE())
( Ve E N(w))))
(1)
where H (1+1= E na di is the node features computed after I-steps of the GNN simplified as follows: ((++) = @ ()) A UPDATE and AGGREGATE are arbitrary differentiable functions,
(u) denotes set of neighboring nodes of u, and (! is initialized as the input node features X,.-
3

---

Published as a conference paper at ICLR 2021
Graph Pooling While message- paasssggg functions can produce set of node representations, need an additional READOUT function to obtain an entire graph representation hG E R' as follows:
hG = READOUT ((H, , E V)).
(2)
As READOUT function, we can simply use the average or sum over all node features H., Vu E V from the given graph (Atwood & Towsley] 2016; Xu et al. 2019). However, since such aggrega- tion schemes take all node information equally without considering the graph structures, they lose structural information that is necessary for accurately representing a graph. To tackle this limitation, Node Drop methods (Gao & Jil 2019 Lee al. 2019b) select the high scored nodes g(++1) E R with learnable score function at layer 7, to drop the unnecessary nodes, denoted as follows:
(3) where function s depends on specific implementations, and top; function samples the top k nodes by dropping nodes with low scores y E "R. Whereas Node Clustering methods (Ying et al., 2018 Bianchi et al. 2019) learn a cluster assignment matrix (( E [ with node features H E R2x to coarsen the nodes and the adjacency matrix (1) E 1R" at layer as follows:
y (1) = s ((H (1) A ())
j(++1) = topp ()),
H(+ = C() HO;; A (1+1) U A C())
(4)
where generating an assignment matrix C( depends on specific implementations. While these two approaches obtain decent performances on graph classification tasks. they are suboptimal since node drop methods unnecessarily drop arbitrary nodes, and node clustering methods have limited scalability to large graphs (Cangea et al. 2018 Lee al. 2019b). Therefore, we need a sophisticated graph pooling layer that coarsens the graph with sparse implementation without discarding nodes.
3.2 GRAPH MULTISET TRANSFORMER
We now describe the Graph Multiset Transformer (GMT) architecture, which can accurately rep- resent the entire graph, given a multiset of node features. We first introduce a multiset encoding scheme that allows embed two different graphs into distinct embeddings, and then describe the graph multi-head attention that reflects the graph topology in the attention- based multiset encoding.
Multiset Encoding The input of the graph pooling function READOUT consists of nodes in a graph, and they form multiset (i.e. set that allows for repeating elements) since different nodes can have identical feature vectors. To design a graph pooling function that is as powerful as the test, it needs to satisfy the permutation invariance and injectiveness over the multiset, since two non-isomorphic graphs should be embedded differently through the injective function. While the simple sum pooling satisfies the injectiveness over a multiset (Xu al. 2019). may treat all node embeddings equally without consideration of their relevance to the task. To resolve this issue, we consider attention mechanism on the multiset pooling function to capture structural dependencies among nodes within a graph, in which we can provably enjoy the expressive power of the WL test.
Graph Multi-head Attention To overcome the inability of simple pooling methods (e.g. sum) the attention mechanism the main component in our
on distinguishing important nodes, pooling scheme. Assume that we have n node vectors, and the input of the attention function (Att) consists of query Q E Xdx, key K [R and value V E gnxd. where ny is the number of query vectors, n is the number of imput nodes, de is the dimensionlity of the key vector, and d, is the dimensionality of the value vector. Then we compute the dot product of the query with all keys, to put more weights on the relevant values, namely nodes, as follows: Att K, V) = w "o(Q""") where w is an activation function. Instead of computing a single attention, we can further use a multi-head attention /Vaswani et al., (207)). by linearly projecting the query Q key K, and value V h times respectively to yield h different representation subspaces. The output of the multi-head attention function (MH) then can be denoted as follows:
(5) where the operations for h parallel projections are parameter matrices Wo E Rdde W. E Rdd x and W. E x4,, Also, the output projection matrix is oo E ggdd, where dmodes is the output dimensionality for the multi-head attention (MH) function.
MH K, V) = [0,,.., On] W O, = Au( K.WK VW.),
While multi-head attention is superior to trivial pooling methods such as sum or mean as it considers global dependencies among nodes, the MH function suboptimally generates the key K and value
4

---

Published as a conference paper at ICLR 2021
Import Graph
GMPool
SelfAtt
GMPool O
Seed Vectors S
Message Passing
Graph Aepressntation
Graph Attendion
4
Node Space that reflects graph structures
Trinnlle Graph,
3-Path Graph
Figure 2: Graph Multiset Transformer. Given graph passed through several message passing layers, we attention-based pooling block (GMPool) and self-attention black (SelfAtt) compress the nodes into few important nodes and consider the interaction among them respectively. within a multiset framework.
V for Att, since it linearly projects the obtained node embeddings H from equation I further obtain the key and value pairs. To tackle this limitation, we newly define a novel graph multi-head attention block (GMH). Formally, given node features H E Rnxd with their adjacency information A, we construct the key and value using GNNs, to explicitly leverage the graph structure as follows:
GMH(Q, H, A) = .o., Or) W O = At( ( GNN (H, A), GNN! (H, A)), (6) where the output of GNN; contains neighboring information of the graph, compared to the linearly projected node embeddings K W.K and V V!! in equation 5 for key and value matrices in Att.
Graph Multiset Pooling with Graph Multi-head Attention Using the ingredients above, we now propose a graph pooling function that satisfies the injectiveness and permutation invariance, such that the overall architecture can be at most powerful as the WL test, while taking the graph structure into account. Given node features H E Rx from GNNs, we define a Graph Multiset Pooling (GMPool), which is inspired by the Transformer (Vaswani al. a 2017 et al. 2019a), to compress the n nodes into the & typical nodes, with a parameterized seed matrix $ E I k for the pooling operation that is directly optimized in an end-to-end fashion, as follows (Figure 2 GMPool):
GMPoolg H, A) = IN(Z + rFF(()) [)); Z LN(S + GMH(S, H, A)),
(7)
where rFF is any row-wise feedforward layer that processes each individual row independently and identically, and LN is a layer normalization (Ba et al., 2016). Note that the GMH function in equation 77 considers interactions between & seed vectors (queries) in S and n nodes (keys) in H, to compress n nodes into & clusters with their attention similarities between queries and keys. Also, to extend the pooling scheme from set to multiset, we simply consider redundant node representations.
Self-Attention for Inter-node Relationship While previously described GMPool condenses en- tire nodes into k representative nodes, major drawback of this scheme is that it does not consider relationships between nodes. To tackle this limitation, one should further consider the interactions among n or condensed &: different nodes. To this end, we propose a Self-Altention function (SelfAtt), inspired by the Transformer (Vaswani et al. 2017 Lee et al. 2019a), as follows (Figure 2 SelfAu):
SelfAu(HH) LN(Z + rFF Z));
= H + MH(H, H, H)):
(8)
where, compared to GMH equation 7 that considers interactions between & vectors and n nodes, SelfAtt captures interreelationships among nodes by putting node embeddings H on both query and key locations in MH of equation X To satisfy the injectiveness property of SelfAtt, it might not consider interactions among nodes, which we discuss in Proposition 3 of Appendix A.
Overall Architecture We now describe the full structure of Graph Multiset Transformer (GMT) consisting of GNN and pooling layers using ingredients above (See Figure 2). For graph G with node features X and an adjacency matrix A, the Encoder: : G + H E RRnx is denoted as follows:
Encoder(X. X, A) GNN2 (GNN, (X, A),
(9)
where we can stack several GNNs to construct the deep structures. After obtaining a set of node features H from an encoder, the pooling layer aggregates the features into single vector form; Pooling: H, A + he Rdd To deal with a large number of nodes, we first condense the entire graph into h representative nodes with Graph Multiset Pooling (GMPool), which is also adaptable to the varying size of nodes, and then utilize the interaction among them with Self-Aitention Block (SelfAtt). Finally, we get the entire graph representation by using GMPool with k = 1 as follows: Pooling H, A) GMPool, (SelfAu(GMPool) (H)
(10)
where A' E & is the identity or coarsened adjacency matrix since adjacency information should be adjusted after compressing the nodes from to k with GMPoolg (See Appendix B for detail).
5

---

Published as a conference paper at ICLR 2021
3.3 CONNECTION WITH WEISFEILER- LEHMAAN GRAPH ISOMORPHISM TEST
Ceisfeiler-ehhmrr (WL) test (Weisfeiler & Leman 1968) is known for its ability to efficiently distinguish two different graphs. Recent studies (Morris al. 2019 Xu al. 2019) show that GNNs can be made to be as powerful as the WL test, by using an injective function over a multiset map two different graphs into distinct spaces. Building on previous powerful GNNs, if our graph pooling function is injective, then our overall architecture can be at most as powerful as the WL test. To do so, we first recount the theorem from Xu et al. (2019), as formalized in Theorem 1.
Theorem (Non-isomorphic Graphs to Different Embeddings), Let A : I& be a GNN, and Weisfeiler-Lehmaan test decides two graphs G₁ and G E G as non-isomorphic. Then, A maps two different graphs G1 and G2 to distinct vectors if node aggregation and update functions are injective, and graph-level readout which operates on a multiset of node features {H:), is injective.
Since we focus on the representation of graphs through pooling, we deal with the injectiveness of the READOUT function. Our next Lemma states that GMPool can represent the injective function.
Lemma 2 (Injectiveness on Graph Multiset Pooling). Assume the input feature space H. is
countable set. Then the output of GMPool (H, A) with GM,(S H, A) for seed vector S; can be unique for each multiset H C. HH of bounded size. Further, the output of full GMPooly (H, A) constructs a multiset with k elements, which are also unique on the input multiset H.
All proofs for the WL test are provided in Appendix A.1 Based upon the injectiveness of GM- Pool, we show injectiveness of SelfAtt, to make an overall architecture (sequence of GMPool and SelfAtt with GNNs) as powerful as the WI. test, formalized in Proposition To satisfy the injective- ness of SelfAtt, we might not care about interactions among multiset elements (See Appendix A.I1
Proposition 3 (Injectiveness on Pooling Function). The overall Graph Multiset Transformer with multiple GMPool and SelfAnt can map two different graphs G1 and G2 to distinct embedding spaces, such that the resulting GNN with proposed pooling functions can be as powerful as the WL test.
3.4 CONNECTION WITH NODE CLUSTERING APPROACIESS
Node clustering is widely used for coarsening graph in hierarchical manner, as described in the equation ! However, since they require to store and even multiply the adjacency matrix A with the soft assignment matrix C: A (1+1)= = c(." A ( ((), they need quadratic space O(n?) for nodes, which is problematic for large graphs. Meanwhile, our GMPool does not compute a coarsened adjacency matrix A0+1), such that graph pooling is possible only with a sparse implementation, as formalized in Theorem 4. All proofs regarding node clustering are provided in Appendix (A.2
Theorem (Space Complexity of Graph Multiset Pooling). Graph Multiset Pooling condsense a graph with n nodes to k nodes in (nk) space complexity, which can be further optimized to (n)).
In spite of this huge strength on space complexity, our GMPool can be further approximated to the node clustering methods by manipulating an adjacency matrix, formalized in Proposition 5.
Proposition 5 (Approximation to Node Clustering). Graph Multiset Pooling GMPooly can per-
form hierarchical node clustering with learnable k cluster centroids by Seed Vector S in equation] 7
Note that, contrary to previous node clusterings (Ying et al. 2018 Bianchi et al. 2019), GMPool leams data dependent & cluster centroids that might be more meaningful to capture graph structures.
EXPERIMENT
To validate the proposed Graph Multiset Transformer (GMT) for graph representation learning, we evaluate it on classification, reconstruction and generation tasks of synthetic and real-world graphs.
4.1 GRAPH CLASSIFICATION
Objective The goal of graph classification is to predict a label y: E y of a given graph G3 E g. with mapping function f: g + y. To this end, used to classify a label f(G) = ÿ. We then learn f with cross-entropy loss, to minimize the negative log likelihood as follows: min Σ -ys log ý:-
set of node representations ( (H, / V)
to obtain an entire graph representation hG that is

---

Published as a conference paper at ICLR 2021
Table 1: Graph classification results on test sets. The reported results are mean and standard deviation over 10 different rums. Best performance and its comparable results (p > 0.05) from the t-test are marked bold. Hyphen (-) denotes out-of-resources that take more than 10 days (See Figure 4 for the time efficiency analysis).
Bischemical Donain
Social Domain
Signifieance
D&D
PROTEINS
MUTAG
IIL
Tox21
TosCast
BEUP
IMDB-B
IMDD-M
COLLAD
4 prophe
1.178
1,113
188
41,127
78811
8,526
2,099
1,000
1,500
5,00
4 chooss
2
2
12
617
2
Aug A modes
264.52
39.06
17:93
25.51
18.57
15.75
24.06
19.77
13.00
74.40
GCN
72.05 a. 0.55
75.24
0.73
69.50
= 1.78
76,81
1.01
75.04
2.
0.90
60.63
0.51
65.47
1.73
73.26
0.46
50,39
0.41
80.59
1. 0.27
3/10
GIN
70.79 4. 1.17
71.46
1.65
$1.39
= 1.53
13.95
1.35
73.27
0.554
60.83
1
0.45
67.65
3.00
72.78
0.36
48.13
1.36
78.19
1 0.63
2/10
Sett8ee
71.94
0.556
0.85
69.30
1444
90
66
1.05
72.90
79.55
10
SectPPoo
75.58 0.77
73.17
0.88
71:04-
3.55
00.54
58,00-1
65.08
1.20
72.12
48.
0.83
77.87
10
Ditleal
77.56
73.03
79.22
1.02
75.64
74.83
68.25
0.96
73.14
51.31
0.72
78.63
(10
71.54
72.02
76.78
2.12
11.10
1,06
65.16
193
72.16
49.47
0.56
78,85
0.56
31
SAGPool(E)
74.72
71.56
73.67
09:11
1.75
63.94
2.59
72.55
50.23
0.44
78.03
110
TopKPoct
73.63
70.48
67.11
09.39
2
65.19
2.30
48.59
0.72
77.58
30
MinCutPool
76.23
79.17
164
11
05.97
1.13
51.04
SmactPool
78.45
19.50
67.01
266
72.06
77.27
ASAP
78.58
EdgePool
75.85
73.71
0.57
GMT (Qur) 78772 75,09 0.59 1.35
77.30
68.31 162
50,66 0.52 W0.74 0.544
10/10
Model
D&D PROTEINS BRBP
# Memory (Mibb
100n
ToptPod
Dogareel
OMT 1000)
GMT
75.09
68.31
1.0
Time (sec)
w/o message passing
78.06
25.07
65.26
20*
0.5
wio graph attention
78.08
74.50
66.21
w/o self-attention
74.22
0.0
mean pooling
72,05
73.24
65:47
2 Nodes
200
400
600
800
1000
1st
# Nodes
Ablation Study of GMT on the D&D, PROTEINS, and BBBP datasets for graph classification.
Table 2:
Figure 3: Memory efficiency of GMT compared with baselines.
Figure 4:
Time efficiency of
GMT compared with baselines.
X indicates out-of out-of-memory error.
X indicates out-of out-of-memory error.
Among TU datasets (Morris et al. 2020), we select 6 datasets including 3 datasets (D&D, PROTEINS, and MUTAG) on Biochemical domain, and datasets (IMDB-B, IMDB-M, and COL- LAB) on Social domain with accuracy for evaluation metric. Also, we use 4 molecule datasets (HIV, Tox21, ToxCast, BBBP) from the OGB datasets (Hu et al. 2020) with ROC-AUC for evaluation metric. Statistics are reported in the Table I and more details are described in the Appendix C.2
Datasets
Models 1) GCN. 2) GIN. GNNs with mean or sum pooling (Kipf & Welling, 2017 Xu et al.
2019). 3) Set2Set. Set pooling baseline (Vinyals et al. 2016). 4) SortPool. 5) SAGPool. 6) TopkPool. 7) ASAP. The methods (Zhang et al. 2018:] Lee et al. 2019b] Gao & Jil 2019 Ranjan
cet al. 2020) that use the node drop. by dropping nodes (or clusters) with lower scores using scoring
functions. 8) DiffPool. 9) MinCutPool. 10) HaarPool. 11) StructPool. The methods (Ying al.
2018 Bianchi el al. 2019 Wang et al. 2019: Yuan & Ji, 2020) that use the node clustering, by grouping a set of nodes into a set of clusters using a cluster assignment matrix. 12) EdgePool. The method (Diehl 2019) that gradually merges two adjacent nodes that have a high score edge. 13) GMT. The proposed Graph Multiset Transformer (See Appendix Cp. for detailed descriptions).
Implementation Details For a fair comparison of pooling baselines [Lee et al. 2019b), we fix the GCN (Kipf & Welling 2017) message passing layer. We evaluate the model performance TU datasets for 10-fold cross validation (Zhang et al. 2018 Xu et al.) 2019) with LIBSVM (Chang & Lin 201T). Also, we use the initial node features following the fair comparison setup (Errica et al. 2020). We evaluate the performance on OGB datasets with their original feature extraction
and data split settings (Hu et al. 2020). Experimental details are described in the Appendix C.2
Classification Results Table D shows that our GMT outperforms most baselines, or achieves com- parable performance to the best bascline results. These results demonstrate that our method is simple yet powerful as it only performs single global operation at the final layer, unlike several baselines that use multiple pooling with a sequence of message passing (See Figure for for the detailed model architectures). Note that, since graph classification tasks mostly require the discriminative informa- tion to predict the labels of graph, GNN baselines without parametric pooling, such as GCN and GIN, sometimes outperform pooling baselines on some datasets. In addition, recent work (Mesquita let al., 2020), which reveals that message- message-passing layers are dominant in the graph classification, supports this phenomenon. Therefore, we conduct experiments on graph reconstruction to directly quantify the amount of retained information after pooling, which we describe in the next subsection.
7

---

Published as a conference paper at ICLR 2021
GCN
DifPool
GMPcd
StructPool
TopkPool
MinCusPool
GMPcol we Graple Aseeton
<Valldity [%]]
<Fxact Match (8))
100
<AAccuracy (%)
80
90
60
25
40
80
() Original (b) TopkPed (c DifPodl (6) MinCatPool GMPool
Compression Rario (K4
Compressiin Rario (36)
Comp Compression resiionsionn Racia (K)
Figure 5: Reconstruction results of ring and grid synthetic graphs, compared to node drop and clus- tering methods. See Figure 10 for high resolution.
Figure Reconstruction results on the ZINC molecule dataset by varying the compression ratio. Solid lines de- note the mean, and shaded areas denote the variance.
Ablation Study To see where the performance improvement comes from, we conduct an ablation study on GMT by removing graph attention, self attention, and message-passing operations. Table shows that using graph attention with self-attention helps significantly improve the performances from the mean pooling. Further, performances of the GMT without pesssag--assingg layers indicate that our pooling layer well captures the graph multiset structure only with pooling without GNNs.
Efficiency While node clustering methods achieve decent performances in Table they are known to suffer from large memory usage since they cannot work with sparse graph implementations. To compare the GPU Memory Efficiency of GMT with baseline models, we test it on the Erdos-Renyi graphs (Erdös& & Rényi 1960) (See Appendix C.2 for detail setup). Figure 3 shows that our GMT is highly efficient in terms of memory thanks to its compatibility with sparse graphs, making it more practical over memory-havvy pooling baselines. In addition to this, we measure the Time Efficiency to further validate the practicality of GMT terms of time complexity. We validate it with the same Erdos Erdos-Renyi Renyi graphs (See Appendix C.2 for detail setup). Figure 4 shows that GMT takes less than (or nearly about) a second even for large graphs, compared to the slowly working models such as HaarPool and EdgePool. This result further confirms that our GMT is practically efficient.
4.2 GRAPH RECONSTRUCTION
Graph classification does not directly measure the expressiveness of GNNs since identifying dis- criminative features may be more important than accurately representing graphs. Mcanwhile, graph reconstruction directly quantifies the graph information retained by condensed nodes after pooling.
Objective For graph reconstruction, we train an autoencoder reconstruct the input node features X E TR from their pooled representations Xoool E R The learning objective to minimize the discrepancy between the original graph X and the reconstructed graph X with a cluster assignment matrix C' E Ra*k is denoted as follows: min|| - XreelJ, where Xree = C pool
Experimental Setup We first experiment with Synthetic Graph, such as ring and grid (Bianchi et al., 2019). that can be represented in a 2-D Euclidean space, where the goal is to restore the location of each node from pooled features, with an adjacency matrix. We further experiment with real-world Molecule Graph, namely ZINC datasets (Irwin et al. 2012), which consists of 12K molecular graphs. See Appendix C.3 for the experimental details including model descriptions.
Reconstruction Results Figure 5 the original and the reconstructed graphs for Synthetic Graph of ring and grid structures. The noisy results of baselines indicate that the con- densed node features do not fully capture the original graph structure. Whereas our GMPool yields almost perfect re- construction, which demonstrates that our pooling operation learns meaningful representation without discarding the orig- inal graph information. We further validate the reconstruc- tion performance of the proposed GMPool on the real-world Molecule Graph, namely ZINC, by varying the compression ratio. Figure reconstruction results on the molecule graph, on which GMPool largely outper- forms all compared baselines in terms of validity, exact match, and accuracy (High score indicates the better, and see Appendix C.3 for the detailed description of evaluation metrics). With given re- sults, we demonstrate that our GMPool can be easily extended to the node clustering schemes, while is powerful enough to encode meaningful information to reconstruct the graph.
(A.1) A. Mitharooa
(A.2)
(R.1) GMT
(R
(1) Grann Irath Clanaas (2) Prodlcedd (O: fallmr)
Figure 7: Reconstruction example with assigned clusters as colors on left and reconstructed molecules on right.
8

---

Published as a conference paper at ICLR 2021
% of Valid Nolecules
100
Top & accuracy:
5
20
50
Average Poning MinCuPoul
Reaction GLN
51.41
67.55
74.92
83,48
88.6
92.37
Class
MinCutPool
51.17
67.47
75.59
83,68
89.31
92.31
Unknown
GMT (Ours)
51.83 68.20
75.17
83.20
89.33
92.47
40
Reaction GLN
63.53 78.27
84.32
89.51
92.17
20
Class
MinCutPool
63.91
79.19
84.76
89.69
92. 13
93.23
(Ours) 64.17
79.61 85.32
92.31
93.25
Discriminator Iteration
1el
Figure 8: Validity curve for molecule generation on QM9 datasct from MolGAN. Solid lines denote the mean and shaded areas denote the variance.
Table 3: Top-k accuracy for Retrosynthesis experiment on USPTO-50K data, for cases where the reaction class given as prior information (Bottom) and not given (Top).
Qualitative Analysis We visualize the reconstruction examples from ZINC in Figure where colors in the left figure indicate the assigned clusters each atoms, and red dashed circles indicate the incorrectly predicted atoms on the reconstructed molecule. As shown in Figure GMPool yields more calibrated clustering than MinCutPool, capturing the detailed substructures, which results in the successful reconstruction (See Figure 11 in Appendix D for more reconstruction examples).
4.3 GRAPH GENERATION
Objective Graph generation is used to generate a valid graph that satisfies the desired properties, in which graph encoding is used to improve the generation performances. Formally, given graph G with graph encoding function f. the goal here is to generate a valid graph G E G of desired property with graph decoding function g follows: min d( G', where G g(f(G)) d is a distance metric between the generated graph and desired properties, to guarantee that the graph has them.
Experimental Setup To evaluate the applicability of our model, we experiment on Molecule Gen- eration to stably generate the valid molecules with MolGAN (Cao & Kipf (018). and Retrosynthe- sis to empower the synthesis performances with Graph Logic Network (GLN) (Dai et al.) [2019). by replacing their graph embedding function f(G) to ours. In both experiments, we replace the average pooling to either the MinCutPool or GMT. See Appendix Cenddix(C.4ee for more experimental details.
Generation Results The power of a discriminator distinguishing whether a molecule real or fake is highly important to create a valid molecule in MolGAN. Figure[]shove the validity curve on the early stage of MolGAN training for Molecule Generation, and the representation power of GMT significantly leads to the stabilized generation of valid molecules than baselines. Further, Table 3 shows Retrosynthesis results, where we use the GLN as backbone architecture. Similar to the molecule generation, retrosynthesis with GMT further improves the performances, which suggests that GMT can replace existing pooling methods for improved performances on diverse graph tasks.
CONCLUSION
In this work, we pointed out that existing graph pooling approaches either do not consider the task relevance of each node (sum or mean) may not satisfy the injectiveness (node drop and clustering methods). To overcome such limitations, we proposed a novel graph pooling method, Graph Mul- tiset Transformer (GMT), which not only encodes the given set of node embeddings to uniquely embed two different graphs into two distinct embeddings, but also considers both the global structure of the graph and their task relevance in compressing the node features. We theoreti- cally justified that the proposed pooling function is as powerful as the WL test, and can be extended to the node clustering schemes. We validated the proposed GMT on 10 graph classification datasets, and our method outperformed state-of-the-at graph pooling models on most of them. We further showed that our method is superior to the existing graph pooling approaches on graph reconstruction and generation tasks, which require more accurate representations of the graph than classification tasks. We strongly believe that the proposed pooling method will bring substantial practical impact, as it is generally applicable many graph-learning tasks that are becoming increasingly important.
multiset
ACKNOWLEDGMENTS
This work was supported by Institute of Information & communications Technology Planning & Evaluation (ITPP) grant funded by the Korea government (MSIT) No.2001-0-000075. Artificial In- telligence Graduate School Program (KAIST)), and the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (NRF-2018R A5A 1059921).

---

Published as a conference paper at ICLR 2021
REFERENCES
Amir Hosein Khas Ahmadi, Kaveh Hassani, Parsa Moradi, Leo Lee, and Quaid Morris. Memory- based graph networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
James Atwood and Don Towsley. Diffusion-convolutionaal neural networks. In Advances in Neu- ral Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. 1993-2001, 2016.
Lei Jimmy Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization. arXiv preprint, 2016.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling, arXiv preprint, utXiv:1907.0048.1 2019.
Catalina Cangea, Petar Velickovie, Nikola Jovanovic, Thomas Kipf, and Pietro Liò. Towards sparse hierarchical graph classifiers. arXiv preprint,
2018.
Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs. arXiv preprint, arXiv:1805, 1997,, 2018.
Chin-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Truns. Intell. Syst. Technol., 2(3):27:1-2::27, 2011.
Hanjun Dai, Bo Dai, and Le Song. Discriminative embeddings of latent variable models for struc- tured data. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 2702-2711. 2016.
Hanjun Dai, Chengtao Li, Connor W. Coley, Bo Dai, and Le Song. Retrosynthesis prediction with conditional graph logic network. In Advances in Neural Information Processing Systems 32: An- nual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 8870-8880, 2019.
Frederik Diehl. arXhv:1905.10990 2019.
Edge contraction pooling for graph neural networks.
arXiv preprint
David Duvenaud, Dougal Maclaurin, Jorge thy Hirzel, Alán Aspuru-Guus Guzik, and Ryan P. Adams. Convolutional networks on graphs for leam- ing molecular fingerprints. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 2224-2232, 2015.
Rafael Gómez-Bommarele Bombarelli. Timo-
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint, 2xXi::2003300082, 2020.
P. Erdös and A Rényi. On the evolution of random graphs. In PUBLICATION OF THE MATHE- MATICAL INSTITUTE OF THE HUNGARIAN ACADEMY OF SCIENCES, pp. 17-61, 1960.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. fair comparison of graph neural networks for graph classification. In 8th International Conference on Learning Represen- tations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
Hongyang Gao and Shuiwang Ji. Graph u-nets. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of PMLR, 2019.
Proceedings of Machine Learning Research, pp.
10

---

Published as a conference paper at ICLR 2021
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in Neural Information Processing Systems 30: Anmual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 1024- 1034, 2017.
Kurt Hornik, Maxwell B. Stinchcombe, and Halbert White. Multilayer feedforward networks universal approximators. Neural Networks, 2(5):359-366 1989.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint, arXiv:2005.00687 2020.
John J. Irwin, Teague Sterling, Michael M. Mysinger, Erin S. Bolstad, and Ryan G. Coleman. ZINC: A free tool to discover chemistry for biology. J. Chem. Inf. Model., 52(7): 2012.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint, 2014.
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional net- works. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Juho Lee, Yoonho Lee, Jungtaek Kim, Adam R. Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: framework for attention-based permutation-invariint neural networks. In Pro- ceedings the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, Califormia, USA, pp. 3744-3753, 2019a.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California. USA, volume 97 of Proceedings of Machine Learning Research, pp. 3734- 3743. PMLR, 2019b.
Jia Li, Yu Rong, Hong Cheng, Helen Meng, Wen-bing Huang, and Junzhou Huang. Semi-supervised graph classification: hierarchical graph perspective. In The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019, pp. 972-982. ACM, 2019.
Yao Ma, Suhang Wang, Charu C. Aggarwal, and Jiliang Tang. Graph convolutional networks with cigenpooling. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pp. 723-731. ACM, 2019.
Diego P. P. Mesquita, Amauri H. Souza Jr., and Samuel Kaski. Rethinking pooling in graph neural networks. arXiv preprint arXi::2010.11418 2020.
Christopher Morris, Martin Ritzert, Matthias Fey, William L.. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In The Whirty-Third AAAI Conference Artificial Intelligence, AAAI 2019, The Thirty-First Inno- vative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, pp. 4602-4609. AAAI Press, 2019.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint, arXiv:2007.08663. 2020.
Dai Quoc Nguyen, Tu Dinh Nguyen, and Dinh Phung. Unsupervised universal self-attention net- work for graph classification. arXiv preprint veXiv:/909, 1855, 2019.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs In Proceedings of the 33nd International Conference Machine Learning, ICML 2016. New York City, NY. USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 2014-2023. JMLR.org, 2016.
11

---

Published as a conference paper at ICLR 2021
Charles Ruizhongtai Qi, Hao Su, Kaichun Mo, and Leonidas J. Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017, pp- 77-85. IEEE Computer Society, 2017a
Charles Ruizhongtai Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017, pp. 77-85. IEEE Computer Society, 2017b.
R. Ramakrishnan, Pavlo O. Dral, Matthias Rupp, and O. A. von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific Data, 1, 2014.
Ekagra Ranjan, Soumya Sanyal, and Partha P. Talukdar. ASAP: adaptive structure aware pooling for learning hierarchical graph representations. In The Thirty-Fourth AAAI Conference Artifi- cial Intelligence, AAAI 2020, The Thirly-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial In- telligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp. 5470-5477. AAAI Press, 2020.
Yu Rong. Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. GROVER: self-supervised message passing transformer on large-scale molecular data. arXiv preprint arXiv:2007.02833. 2020.
Martin Simonovsky and Nikos Komodakis. Dynamic edge-conditioned filters in convolutional neu- ral networks on graphs. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017, pp. 29-38. IEEE Computer Society, 2017.
Jake Snell, Kevin Swersky, and Richard S. Zemel. Prototypical networks for few-shot learning. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Infor- mation Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 4077-4087, 2017.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems 30: Anmual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 5998-69989999 000-6600,222 2017.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018.
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence sequence for sets. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
Edward Wagstaff, Fabian Fuchs, Martin Engelcke, Ingmar Posner, and Michael A. Osborne. On the limitations of representing functions sets. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9- 15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 6487-6494, PMLR, 2019.
Yu Guang Wang, Ming Li, Zheng Ma, Guido Montúfar, Xiaosheng Zhuang, and Yanan Fan. Haar- pooling: Graph pooling with compressive haar basis. arXiv preprint arXiv: 1909. 19999//1580 15800 2019.
B. Yu. Weisfeiler and A. A. Leman. Reduction a graph to a canonical form and an algebra arising during this reduction. 1968.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey graph neural networks. arXiv preprint arXiv: 00596, 2019.
12

---

Published as a conference paper at ICLR 2021
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmüssan, Stock- holm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp- 1449-5455 PMLR, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural net- works? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Li Yi, Wang Zhao, He Wang, Minhyuk Sung, and Leonidas J. Guibas. GSPN: generative shape proposal network for 3d instance segmentation in point cloud. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, pp. 3947- 3956. Computer Vision Foundation TEEE, 2019.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural In- formation Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada, pp. 4805-4815 2018
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In Proceedings of the 36th International Conference on Machine Learning. ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 7134- 7143. PMLR, 2019.
Hao Yuan and Shuiwang Ji. Structpool: Structured graph pooling via conditional random fields. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander J. Smola. Deep sets. Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 3391-3401, 2017.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI- 18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pp. 0938-4445. AAAI Press, 2018.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Graph neural networks: review of methods and applications. urXiv preprint, arXiv: 1821182222 812.08434, 2018
13

---

Published as a conference paper at ICLR 2021
A PROOFS
A. PROOFS REGARDING WEISFEILER-LEIMAN TEST
We first recount the theorem Xu et al. (0199) to define a GNN that is injective over a multiset (Theorem 1). We then prove that the proposed Graph Multiset Pooling (GMPool) can map two different graphs to distinct spaces (Lemma 2). Finally, we show that our overall architecture Gruph Multiset Transformer (GMT) with sequence of proposed Graph Multiset Pooling (GMPool) and Self-Artention (SelfAtt) can represent the injective function over the imput multiset (Proposition 3).
isomophic Graphs to Different Embeddings). Let A - Rd be a GNN, and Weisfeiler-Lehmaee test decides two graphs G₁ E 9 and G2 E G as non-isomorphic. Then, A maps two different graphs G1 and G2 distinct vectors if node aggregation and update functions are injective, and graph-level readout, which operates on a multiset of node features ) is injective.
Theorem 1 (Non-isomore
Proof. To map two non-isomorphic graphs to distinct embedding spaces with GNNs, we recount the theorem on Graph Isomorphism Network. See Appendix B of al. 2019) for details.
Lemma (Uniqueness on Graph Multiset Pooling). Assume the imput feature space H. is count- able set. Then the output of the GMPool, (H, A) with GMH(S,, (S,, H, A) for a seed vector S can be unique for each multiset H C H of bounded size. Further, the oulput of the full GMPooly (H, A) constructs a multiset with k elements, which are also unique on the imput multiset H.
Proof. We first state that the GNNs of the Graph Multi-head Attention (GMH) in a GMPool can represent the injective function over the multiset H with an adjacency information A, by se- lecting proper message-passing functions that satisfy the WL test (Xu al.) 2019; Morris et al.] 2019), denoted as follows: H' GNN(H, A), where H' C H. Then, given enough ele- ments, a GMPool (, A) can express the sum pooling over the multiset H' defined as follows: p( f(h)), where f and p are mapping functions (see the proof of PMA in Lee et al. (2019a))
Since H is countable set, there is mapping from the elements to prime numbers denoted by p(h) : H + F. If we let ((h) = -log((h) then ΣnEHr [h) = log II p(h) which constitutes an unique mapping for every multiset H' C H. (see Wagstaff et al. (2019)) In other words, ΣnEHr f(h) is injective. Also, we can easily construct a function p. such that GMPool, [H, A) = p(EnEH: f(h)) p(log IhEH p(t))
) is the injective function for every mul- tiset H C H. where H' is derived from the GNN component in the GMPool; H' GNN(H, A).
Furthermore, since a GMPool considers multiset elements without any order, it satisfies the permu- tation invariance condition for the multiset function.
Finally, each GMPool block has components such that the output of it consists of l elements as follows: GMPool {GMPool) (H, A)) which allows multiple instances for its elements. Then, since each GMPool [H A) is unique on the input multiset H, the output of the GMPool that consists of outputs also unique on the input multiset H.
Thanks to the universal approximation theorem (Hornik et al. 1989). we can construct such func- tions p and p using multi-layer perceptrons (MLPs).
Proposition 3 (Injectiveness on Pooling Function). The overall Graph Multiset Transformer with multiple GMPool and SelfAtt can map two different graphs G1 and G2 to distinct embedding spaces, such that the resulting GNN with proposed pooling functions can be as powerful as the WL test.
Proof. By Lemma 2. we know that a Graph Multiset Pooling (GMPool) can represent the injective function over the input multiset H C H. If we can also show that a Self-Attention (SelfAtt) can represent the injective function over the multiset, then the sequence of the GMPool and SelfAtt blocks can satisfy the injectiveness.
Let WO be a zero matrix in SelfAtt function. (elfAt(H)) then can be approximated to the any instance- wise feed-forward network denoted as follows: SelfAtt(F (H) rFF()). Therefore, this
14

---

Published as a conference paper at ICLR 2021
IFF is suitable transformation o R + Rd that can be easily constructed over the multiset elements h E H. to satisfy the injectiveness.
To maximize the discriminative power of the Graph Multiset Transformer (GMT) by satisfying the WL test, we assume that SelfAtt does not consider the interactions among multiset elements, namely nodes. While proper GNNs with the proposed pooling function can be at most as powerful as the WL test with this assumption, our experimental results with the ablation study show that the interaction among nodes is significantly important to distinguish the broad classes of graphs (See Table 2
A.2 PROOFS REGRADING NODE CLUSTERING
We first prove that the space complexity of the Graph Multiset Pooling (GMPool) without GNNs can be approximated to the (n) with n nodes (Theorem 4). After that, we show that the GMPool can be extended to the node clustering approaches with learnable cluster centroids (Proposition 5).
Theorem (Space Complexity of Graph Multiset Pooling). Graph Multiset Pooling condsense a
graph with n nodes to k nodes in (nk) space complexity, which can be further optimized to (n)).
Proof. Assume that we have key K E Raxds and value V E Raxd, matrices in the Att function of Graph Multi-head Attention (GMH) for the simplicity, which is described in the equation 6 Also, Q is defined as a seed vector S E Rex in the GMPool function of the equation 7 To obtain the weights on the values V. we multiply the query Q with key K: QK". This matrix multiplication then maps a set of n nodes into set of l nodes, such that it requires (nk)) space complexity. Also, we can further drop the constant term k: (n)), by properly setting the small values; k & n.
The multiplication of the attention weights QK" with value V also takes the same complexity, such that the overall space complexity of GMPool is ((k)), which can further optimized to (n). O
The space complexity of GNNs with sparse implementation requires O(n m) space complexity, where n is the number of nodes, and m is the number of edges in a graph. Therefore, multiple GNNs followed by our GMPool require the total space complexity of O + m) due to the space complexity of the GNN operations. However, GNNs with our GMPool are more efficient than node clustering methods, since node clustering approaches need (n²) space complexity.
Proposition 5 (Approximation to Node Clustering). Graph Multiset Pooling GMPools can per- form hierarchical node clustering with learnable cluster centroids by Seed Vector S in equation 7
Proof. Node clustering approaches are widely used to coarsen a given large graph in hierarchical manner with several message-passingg functions. The core part of the node clustering schemes is to generate cluster assignment matrix C, to coarsen nodes and adjacency matrix in equation 4 Therefore, if our Graph Multiset Pooling (GMPool) can generate a cluster assignment matrix C, then the proposed GMPool can be directly approximated the node clustering approaches.
In the proposed GMPool, query Q is generated from a learnable set of k seed vectors S, and key K and value V are generated from node features H with GNNs in the Graph Multi-head Atten- tion (GMH) block, as in an equation 6 In this function, if we decompose the attention function Aut Q, K, V) w( (KT)V into the dot products of the query with all keys, and the correspond- ing weighted sum of values, then the first dot product term inherently generates a soft assignment matrix as follows: C = w(QKT). Therefore, the proposed GMPool can be easily extended the node clustering schemes, with the inherently generated cluster assignment matrix; C' = w w(QKT), where one of the proper choices for the activation function w is the softmax function follows:
cxp(Q exp(Q:K?))
w ((QQK K 1i
(11)
1= exp (?..
Furthermore, through the learnable seed vectors S for the query Q, we can learn data dependent different cluster centroids in an end-to-end fashion.
Note that, as shown in the section 4.2 of the main paper. the proposed GMPool significantly out-
performs the previous node clustering approaches (Ying et al. 2018 Bianchi et al. 2019). This
15

---

Published as a conference paper at ICLR 2021
is because, contrary to them, the proposed GMPool can explicitly learn data dependent k cluster centroids by learnable seed vectors S.
B DETAILS FOR GRAPH MULTISET TRANSFORMER COMPONENTS
In this section, we describe the Graph Multiset Pooling (GMPool) and Self-Attention (SelfAtt), which are the components of the proposed Graph Multiset Transformer, in detail.
Graph Multiset Pooling The core components of the Graph Multiset Pooling (GMPool) is the Graph Multi-head Attention (GMH) that considers the graph structure into account, by constructing the key K and value V using GNNs, as described in the equation As shown in the Table 2f the main paper, this graph multi-head attention significantly outperforms the naive multi-head attention (MH in equation [5)- However, after compressing the n nodes into the k nodes with GMPoolk. we can not directly perform further GNNs since the original adjacency information useless after pooling. To tackle this limitation, we can generate the new adjacency matrix A' for the compressed nodes, by performing node clustering as described in Proposition 5 of the main paper as follows:
GMPool, (GMPool, (H, A)); A' A²=
(12)
where C' is the generated cluster assignment matrix, and A' is the coarsened adjacency matrix as described in the equation 4 However, this approach is well known for their scalability issues (Lee et al. 2019b: Cangea et al. 2018), since they require quadratic space On²)) to store and even muluply the adjacency matrix A with the soft assignment matrix C. Therefore, as future work, and use the following trick. By replacing the adjacency matrix A with the identity matrix I in the GMPool except for the first block, we can easily perform multiple GMPools without any constraints, which is approximated to the GMPool with MH in the equation 5 rather than GMH in the equation 6 as follows:
leave doing this
GMPool, (GMPool, (H, A), =
(13)
Self-Attention The Self-Attention (SelfAtt) function can consider the inter- mnter-relaionsshiss between nodes in a set, which helps the network to take the global graph structure into account. Because of this advantage, the self-attention function significantly improves the proposed model performance on the graph classification tasks, as shown in the Table of the main paper. From different perspec- tive, we can regard the Self-Attention function as a graph neural network (GNN) with a complete graph. Specifically, given ht nodes from the previous layer, the Multi-head Attention (MH) of the Self-Attention function first constructs the adjacency matrix among all nodes with their similarities, through the matrix multiplication of the query with key: QKT, and then computes the outputs with the sum of the obtained weights on the value. In other words, the self-attention function can be considered as one message passing function with soft adjacency matrix, which might be further connected to the Graph Attention Network /Velickovic et al. 2018).
C EXPERIMENTAL SETUP
In this section, we first introduce the baselines and our model, and then describe the experimental details about graph classification, reconstruction, and generation tasks respectively.
C. BASELINES AND OUR MODEL
1) GCN. This method Kipp & Welling 2017) is the mean pooling baseline with Graph Convolu- tional Network (GCN) message passing layer.
2) GIN. This method et al. 2019) is the sum pooling baseline with Graph Isomorphism Network (GIN) message passing layer.
3) Set2Set. This method /Vinyals et al. 2016 is the set pooling baseline that uses a recurrent neural network to encode set of all nodes, with content-based attention over them.
4) SortPool This method (Zhang et al. 2018) is the node drop baseline that drops unimportant nodes by sorting their representations, which are directly generated from the previous GNN layers.
16

---

Published as a conference paper at ICLR 2021
X
Global Pooling
Dense
MP
MP
MP
y
Softmax
A
X
MP
Pool
MP
Pool
MP
Global Pooling
Dense Softmax
y
A
X
MP
MP
Pool
Unpool
MP
MP
MP (Linear)
X
A
Figure 9: Illustration of High-level Model Architectures. (Top): Global Graph Classification: GCN, GIN,
Set2Set, SortPool, SAGPool(G), StructPool, GMT. (Middle:) Hierarchical Graph Classification: DiflPPool, SAG,ool(HD, TopKPool, MinCutPool, ASAP, EdgePool, HaarPool. (Bottom:) Graph Reconstruction; Diff- Pool, TopkPool, MinCutPool, GMT. MP denotes the message passing layer.
5) SAGPool. This method (Lee al. 2019b) is the node drop baseline that selects the important nodes, by dropping unimportant nodes with lower scores that are generated by the another graph convolutional layer, instead of using scores from the previously passed layers. Particularly, this method has two variants. 6.1) SAGPool(G)) is the global node drop method that drops unimportant nodes time at the end of their architecture. 6.2) SAGPool(H) is the hierarchical node drop method that drops unimportant nodes sequentially with multiple graph convolutional layers.
6) TopkPool. This method (Gao & Ji 2019) is the node drop baseline that selects the top-ranked nodes using a learnable scoring function.
7) ASAP. This method (Ranjan et al. 2020) is the node drop bascline that first locally generates the clusters with neighboring nodes, and then drops the lower score clusters using scoring function.
8) DiffPool. This method (Ying et al. 2018) is the node clustering baseline that produces the hier- archical representation of the graphs in an end-to-end fashion, by clustering similar nodes into the few nodes through graph convolutional layers.
9) MinCutPool. This method (Bianchi et al. 2019) is the node clustering baseline that applies the spectral clustering with GNNs, coarsen the nodes and the adjacency matrix of graph.
10) HaarPool. This method (Wang et al. 2019 is the spectral- based pooling baseline that com- presses the node features with a nonlinear transformation in Haar wavelet domain. Since it directly uses the spectral clustering to generate a coarsened matrix, the time complexity cost is relatively higher than other pooling methods.
11) StructPool. This method (Yuan & Ji 2020) is the node clustering baseline that integrates the concept the conditional random field into the graph pooling, While this method can be used with hierarchical scheme, we use it with a global scheme following their original implementation, which similar the SortPool (Zhang al. 2018).
12) EdgePool. This method Diihl 2019) is the edge clustering baseline that gradually merges the nodes, by contracting the high score edge between two adjacent nodes.
13) GMT. Our Graph Multiset Transformer that first condenses all nodes into the important nodes by GMPool, and then considers interactions between nodes in a set. Since it operates on the global READOUT layer, it can be coupled with hierarchical pooling methods by replacing their last layer.
C.2 GRAPH CLASSIFICATION
Dataset Among TU datasets Mooris et al. 2020 we select the datasets including datasets (D&D, PROTEINS, and MUTAG) Biochemical domain, and 3 datasets (IMDB-B, IMDB-M, and COLLAB) on Social domain. We use the classification accuracy as an evaluation metric. As suggested by Errica et al. (2020) for fair comparison, use the one-hot encoding of their atom
17

---

Published as a conference paper at ICLR 2021
types initial node features in the bio-chemical datasets, and the one-hot encoding of node degrees as initial node features in the social datasets. Moreover, we use the recently suggested 4 molecule graphs (HIV, Tox21, ToxCast, BBBP) from the OGB datasets (Hu et al., 2020). We use the ROC- AUC for an evaluation metric, and use the additional atom and bond features, as suggested by Hu al. (2020). Dataset statistics are reported in the Table [o the main paper.
Implementation Details on Classification Experiments For all experiments on TU datasets, we evaluate the model performance with a 10-fold cross validation setting, where the dataset split is based on the conventionally used training/test splits (Niepert et al. 2016) Zhang et al. 2018 Xu al. 2019). with LIBSVM (Chang Lin 201T). In addition, we use the 10 percent of the training data as validation data following the fair comparison setup (Errica et al. 2020). For all experiments on OGB datasets, we evaluate the model performance following the original siining/validation/ess dataset splits (Hu et al.] 2020). We use the early stopping criterion, where we stop the training there is no further improvement on the validation loss during 50 epochs, for the TU datasets. Further, the maximum number of epochs is set to 500. We then report the average performances on the validation and test sets, by performing overall experiments 10 times with different seeds.
For all experiments TU datasets except the D&D, the learning rate is set 5 10-1, hidden size is set to 128, batch size is set to 128, weight decay is set to 1 x 10-1, and dropout rate is set to 0.5. Since the D&D dataset has large number of nodes (See Table ii the main paper), node clustering methods can not perform clustering operations on large graphs with large batch sizes, such that the hidden size is
32, and batch size is set 10 on the D&D dataset. For all experiments on OGB datasets except the HIV, the learning rate is set to X 10-3, hidden size is set to 128, batch size is set to 128, weight decay is set to 1 10 and dropout rate is set to 0.5. Since the HIV dataset contains a large number of graphs compared to others (See Table [ in the main paper), the batch size is set to 512 for fast training. Then we optimize the network with Adam optimizer (Kingma & Bal 20144) For fair comparison of baselines (Lee et al. (019b), use the three GCN layers (Kipf & Welling 2017) as a message passing function for all models with jumping knowledge strategies (Xu et al, 2018 and only change the pooling architecture throughout all models, illustrated in Figure Also, we set the pooling ratio as 25% in each pooling layer for both baselines and our models.
Implementation Details Efficiency Experiments To compare the GPU memory efficiency of GMT against baseline models including node drop and node clustering methods, we first generate the Erdos-Renyi graphs (Erdös & Rényi 1960) by varying the number of nodes n, where the edge size m is twice the number of nodes: = 2n. For all models, we compress the given n nodes into the 1: = 4 nodes at the first pooling function.
To compare the time efficiency of GMT against baseline models, we first generate the Erdos-Renyi graphs (Erdōs Rényi, 1960) by varying the number of nodes n with m = n²2/10 /10 edges, following the setting of HaarPool (Wang et al. (2019). For all models, we set the pooling ratio as 25% except for HaarPool, since it compresses the nodes according to the coarse- coarse-graines grained chain of a graph. We measure the forward time, including CPU and GPU, for all models with 50 graphs over one batch.
C.3 GRAPH RECONSTRUCTION
Dataset We first experiment with synthetic graphs represented in a 2-D Fuclidean space, such as ring and grid structures. The node features of graph consist of their location in a 2-D coordinate space, and the adjacency matrix indicates the connectivity pattern of nodes. The goal here is to restore all node locations from compressed features after pooling, with the intact adjacency matrix.
While synthetic graphs are appropriate choices for the qualitative analysis, we further do the quan- titative evaluation of models with real-world molecular graphs Specifically,, we use the sub- set (Dwivedi et al. 2020) of the ZINC dataset (Irwin et al. 2012). which consists of 12K rorl-world molecular graphs, to further conduct a graph reconstruction on the large number of various graphs. The goal of the molecule reconstruction task is to restore the exact atom types of all nodes in the given graph, from the compressed representations after pooling.
Common Implementation Details Following Bianchi et al. (2019), use the two message pass- ing layers both right before the pooling operation and right after the unpooling operation. Also, both pooling and unpooling operations are performed once and sequentially connected, as illustrated in
18

---

Published as a conference paper at ICLR 2021
(a) Original
(b) Top-K
(c) DiftPool
(d) MinCutPool
GMPool
Figure 10: High resolution images for synthetic graph reconstruction results Figure
the Figure We compare our methods against both the node drop (TopKPool (Gao & Ji 2019)
and node clustering (DiffPool (Ying et al., 2018) and MinCutPool (Bianchi et al. 2019) methods. For the node drop method, we use the unpooling operation proposed in the graph U-net (Gao & Jil 2019). For the node clustering methods, we use the graph coarsening schemes described in the generating
assignment matrix. For our pro- posed method, we only use the one Graph Multiset Pooling (GMPool) without SelfAtt, where we follow the node clustering approaches assignment matrix with one head h = in the multi-head attention function. For experiments of both synthetic and molecule reconstructions, the learning is 5 x 10-3, and hidden size is set to 32. We then optimize the network with Adam optimizer (Kingma Ba 2014).
equation with their specific implementations
described in the subsection 3.4 by generating single soft
Implementation Details on Synthetic Graph We set the pooling ratio of all models as 25%. For the loss function, we use the Mean Squared Error (MSE) train models. We use the early stopping criterion, where we stop the training if there is no further improvement on the training loss during 1,000 epochs. Further, the maximum number of epochs is set to 10,000. Note that, there is no other available graphs for validation of the synthetic graph, such that we train and test the models only with the given graph in the Figure IO
The baseline results are adopted from Bianchi et al. (2019).
Implementation Details on Molecule Graph We set the pooling ratio of all models as 5%, 10%, 15%, and 25%, and plot all results in the Figure 6 of the main paper. Note that, in the case of molecule graph reconstruction, a softmax layer is appended at the last layer of the model architecture classify the original atom types of all nodes. For the loss function, to train models. We use the early stopping criterion, where we stop the training if there is no further improvement on the validation loss during 50 epochs. Further, the maximum number of epochs is set to 500, and batch size is set to 128. Note that, in the case of molecule graph reconstruction on the ZINC dataset, we strictly separate the training, validation and test sets, as suggested by Dwivedi] ee al. (2020). We perform all experiments 5 times with 5 different random seeds, and then report averaged result with the standard deviation. Note that, in addition to baselines mentioned the common implementation details paragraph, compare two more basclines: GCN with random assignment matrix for pooling, which is adopted from Mesquita et al. (2020). and StructPool Yuaan & Ji 2020 for the real-world molecule graph reconstruction.
use the cross entropy loss
Evaluation Metrics for Molecule Reconstruction For quantitative evaluations, metrics as follows: 1) validity indicates the number of reconstructed molecules that are chemically valid, 2) exact match indicates the number of reconstructed molecules that are exactly same as the original molecules, and 3) accuracy indicates the classification accuracy of atom types of all nodes.
the three
C.4 GRAPH GENERATION
Common Implementation Details In the graph generation experiments, replace the graph embedding function (G) from existing graph generation models to the proposed Graph Multiset Transformer (GMT), to evaluate the applicability of model generation tasks, described
19

---

Published as a conference paper at ICLR 2021
Table 4: Graph classification results validation sets with standard deviations. All results are averaged over 10 different runs. Best performance and comparable results (p > 0.05) from the t-test are marked blnd. Hyphen (-) denotes out-of-resources that take more than 10 days (See Figure 4 for the time efficiency analysis).
Blochemical Domain
Social Domain
D&D
PROTEINS
MUTAG
HIV
Tox21
ToxCast
BBBP
IMDB-B
IMDB-M
COLLAB
graphs
1,178
1,113
41,127
7,831
8,576
2,039
1,000
1,500
5,000
clisses
2
2
2
12
617
2
3
Avg 4 nodes
281.32
39.05
17.93
25.51
18.57
18.78
24.06
19.77
13,00
74,49
GCN
-6.17-0.55
77.13
0,44
76.56 4 1,75
81.27
0.99
78.80 1: 0.40
65,66
0.40
93.35 1 1,08
77.93
0.26
56,29 1 0.23
83.06
0.13
GIN
0.61
78.43
0.52
52.10
0.45
66.29
0.36
78.38
62.19
Ser2Ser
76.32
77.64
2.40
80007
0.75
66.39
91.89
1.48
78.13
0.19
82.34
SortPol
80.68 = 0.59 77.92 044 81.33 = 3.00
81.17
= 2.30
75.97
+ 0.76
64.26
1.17
94.21
+ 1.04
77,46
+ 0.60
52.95
+ 0.62
80.58
+ 0.25
DidPool
$1.33 = 0.33 79.09 0.36 $7.94
= 199
83.16
2: 0.44
80.02
0.38
69.73
1 0.79
96.32
1 0.36
77.86
1 0.39
54.77
4 0.19
81.69
0.31
SAGProl(()
76.73 - 0.50 77.01 (158 88.11
1.21 80.55
1.89
77.03
+ 0.76
65.51
0.91
95.59
1.22
78.09
+ 0.58
53.73
+ 0:42
81.91
0.45
SAGPoel(H)
79.56 0.67 77.24
86.06
2407 79.21
1.50
75.36
265
64.05
95.05
3.00
77.11
53.49
0.65
80.55
TooKPool
78.54 0.73 75.47
2.12 79.24
64.56
76.12
52.75
0.58
79,94
MinCuiPool
81,96 = 0.39 79:23 0.66
57.22
1 1.72 83.12
1.27
81.10
0.42
69.09
1.12
95.99
0.47
77.26
0.36
54.94
0.19
83.37
0.18
StraciPool
82:56 0.37 80.00 0.27
91.5
1 0.55
$1.09
1.26
79.6
0.70
66.49
1 1.59
95.18
0.59
77.14
1 0.31
54.13
0.39
79.
0.18
ASAP
81.58 = 0.38 78:71
= 0.45
91.33
0.65
79.
1.88
71.33
1.34
63.82
0.75
92.96
4 1.09
77.89
4 0.51
55.17
4 0.33
82.11
0.33
EdgePool
80.32
0.44 79.61
= 0.25
$7.28 1.18 81.84
1.32
78.92
0.29
66.21
0.64
94,98
0.62
77.50
0.25
54,69
0:40
0.58
76.72
53.03
0.14
GMT (Qurs) -0.0 80.01 -021 91.00
0.82 83.54
0.78 80.91 0.41 69.77 0.67 95.14
0.48 78.43
0.22
55.14
0.25 83.37
in the subsection 4.3 of the main paper. As baselines, we first use the original models with their implementations. Specifically, we use the MolGAN (Coo & Kipf 2018) for molecule generation, and Graph Logic Network (GLN (Dai et al. 2019) for retrosynthesis. For both experiments, we directly follow the experimental details of original papers (Cao & Kipi 2018 Dai et al,) (211)) for fair comparison. Furthermore, to compare our models with another strong pooling method, use the MinCutPool (Bianchi et al., 2019) as an additional baseline for generation tasks, since it shows the best performance among baselines in the previous two classification and reconstruction tasks.
(Dai
For MinCutPool, since it cannot directly compress the all n nodes into the cluster to represent the entire graph,
the following trick to replace the simple pooling operation (e.g. sum or mean) with it. We first condense the graph into the k clusters (k- = 4) using one MinCutPool layer, and then average the condensed nodes to get a single representation of the given graph. However, our proposed Graph Multiset Transformer (GMT) can directly compress the all n nodes into the node with one learnable seed vector, by using the single GMPool, block. In other words, we use the one GMPool, to represent the entire graph by replacing their simple pooling (c.g. sum or mean), in which we use the following softmax activation function for computing attention weights:
e
w QQQQQ Ka
(14)
E== exp( Q,KY)
Implementation Details on Molecule Generation For the molecule generation experiment with the MolGAN, we replace the average pooling in the discriminator with GMPool,. We use the QM9 dataset (Ramakrishnan et al.] 2014) following the original MolGAN paper (Cao & Kipi, 2018). To evaluate the models, we report the validity of 13,319 generated molecules at the early stage of the MolGAN training, over 4 different runs. As depicted in Figure the main paper, each solid curve indicates the average validity of each model with 4 different runs, and the shaded area indicates the half of the standard deviation for 4 different runs.
Implementation Details on Retrosynthesis For the retrosynthesis experiment with the Graph Logic Network (GLN), we replace the average pooling in the template and subgraph encoding func- tions with GMPool, We use the USPTO-50k dataset following the original paper (Dai al. 2019). For an evaluation metric, we use the Top-k accuracy for both reaction class is not given and given cases, following the original paper (Dai et al., 2019). We reproduce all results in Table with published codes from the original paper.
D ADDITIONAL EXPERIMENTAL RESULTS
Validation Results on Graph Classification We additionally provide the graph classification re- the proposed GMT outperforms most baselines, or
sults on validation sets. As shown in Table 4
20

---

Published as a conference paper at ICLR 2021
Table 6: Quantitative results of the graph reconstruction task on reconstructing the node features and the adjacency matrix for synthetic graphs, with two different minimization objectives and error calculation metries: X X and A A rea * indicates the model without using adjacency normalization.
Grid Grugh
Ring Graph
Objective:
min X
X
min (4
|
mini|
X
X
min||4 A
Erro Caleulation:
X|X X |
||A A
X x
A A
X
X
14 A
X x
|| A
DifiPool
0.0833
12110194
0.2908
0.0856
0.0032
617.7706
0.0948
MinCutPool
0.0001
0.0092
1,2883
0.0051
0.0005
0.0121
0,5026
0.0128
MinCutPood*
0.0002
201.7619
2.0261
0,0616
0,0003
68.25
0.5211
0.0725
GMT (Ours)
0.0001
0.0102
0.2353
0.0084
0,000
0.0331
0.5475
0,0324
achieves comparable performances to the best baseline results even in the validation sets. While val- idation results can not directly measure the generalization performance of the model for unseen data, these results further confirm that our method is powerful enough, compared to baselines. Regarding the results of test sets on the graph classification task, please see Table in the main paper.
Leaderboard Results on Graph Classification For fair comparison, we experiment with all baselines and our models in the same setting. as described in the implemen- tation details of Appendix C.2, Specifically, we average the results over 10 different runs with the same hidden di- mension (128, while leaderboard uses 300), and the same number of message- passeegpssnngggg layers (3, while leaderboard uses 5) with 10 different seeds for all models. Therefore, the reproduced results can be slightly different from the leaderboard results, as shown in Table 5 since the leaderboard uses different hyper-past ppper-prrseeterss with different random seeds (See Hu et al. (2020) for more details). However, our reproduction results are almost the same as the leaderboard results, and sometimes outperform the leaderboard results (See the GCN results for the HIV dataset in Table 5). Therefore, while we conduct all experiments under the same setting for a fair compari- son, where specific hyperparameter choices are slightly different from the leaderboard setting, these results indicate that there is no significant difference between reproduced and Icaderboard results.
Table 5: Graph classification results for OGB test datasets with standard deviations,
Model
HIV
Tox21
Leuderbourd
GCN
76.06 # 0.97 75.29
0.69 74.91
GIN
75.58 = 1.40
0.51
Reproduced
GCN
76.81 + 1.01
75.04 0.80
GIN
75.95
1.35
73.27
0.84
Ours GMT 77.56 1.25 77.30 0.59
Quantitative Results on Graph Reconstruction for Synthetic Graphs While we conduct ex- periments on reconstructing node features on the given graph, to quantify the retained information on the condensed nodes after pooling (See Section 4.2 experiments on the graph reconstruction task), we further reconstruct the adjacency matrix to if the pooling layer can also condense the adjacency structure without loss of information. The learning objective to minimize the discrepancy between the original adjacency matrix A and the reconstructed adjacency matrix ree with cluster assignment matrix C' E Ra is defined as follows: min| A Areel where A rec = C'A pool CT.
Then we design the following two experiments. First, pooling layers trained to minimize the objective in Section 4.2 min| X - X After that, we measure the discrepancy between the original and the reconstructed node features: ||X rreel,, and also measure the discrepancy be- tween the original and the reconstructed adjacency matrix: A - Ae Second, pooling layers are trained minimize the objective described in the previous paragraph: min| A we measure the aforementioned two discrepancies in the same way.
A ree and then
We experiment with synthetic grid and ring graphs, illustrated in Figure 10 Table o shows that the
error is large when the objective and the error metric are different, which indicates that there is high discrepancy between the required information for condensing node and the required information for condensing adjacency matrix. In other words, the compression for node and the compression for adjacency matrix might be differently performed to reconstruct the whole graph information.
Also, Table 6 shows that there are some cases where there is no significant difference in the cal- culated adjacency error A||A- - A rel)), when minimizing nodes discrepancies and minimizing ad- jacency discrepancies (See 0.0331 1 and 0.0324 for the proposed GMT on the Ring Graph). Fur- thermore, calculated errors for the adjacency matrix when minimizing adjacency discrepancies are generally larger than the calculated errors for node features when minimizing nodes discrepancies. These results indicate that the adjacency matrix is difficult to reconstruct after pooling. This might be because the reconstructed adjacency matrix should be further transformed from continuous values
21

---

Published as a conference paper at ICLR 2021
to discrete values (0 or I for the undirected simple graph), while the reconstructed node features be directly represented as continuous values. We leave further reconstructing adjacency matrices and visualizing them future work.
Additional Examples for Molecule Reconstruction We visualize the additional examples for molecule reconstruction on the ZINC dataset in Figure II Molecules on the left side indicate the original molecule, where the transparent color denotes the assigned cluster for each node, which is obtained by the cluster assignment matrix C' with node (atom) representations in a graph (molecule) (See Proposition 5 for more detail generating the cluster assignment matrix). Also, molecules on the right side indicate the reconstructed molecules with failure cases denoted as red dotted circle.
As visualized in Figure 11 we can see that the same atom or the similarly connected atoms obtain the same cluster (color). For example, the atom type O mostly obtains the yellow cluster, and the atom type F obtains the green cluster. Furthermore, ring-shaped substructures that do not contain O or N mostly receive the blue cluster, whereas snagss substructures that contain O and receive the green and yellow clusters respectively.
NH
Figure 11: Molecule Reconstruction Examples (Left):: Original molecules with the assigned clus- ter on each node represented as color, where cluster is generated from Graph Multiset Pooling (GM- Pool). (Right): Reconstructed molecules. Red dotted circle indicates the incorrect atom prediction.
22


Reviews:
[{"review_id": "sMNCmJ0NIL", "reviewer": "AnonReviewer3", "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": "This work proposes a Graph Multiset Transformer (GMT) that uses a multi-head attention-based approach to capture potential interactions between nodes when pooling nodes to produce a graph representation. Multi-head attention mechanism is used to group nodes into clusters, each of which produces a representation. Self-attention is then used to pool representations of clusters into the representation of a graph.\n\nPros: \nThe proposed pooling is more reasonable than a simple sum or average pooling as the multi-head attention mechanism can potentially capture dependencies between nodes. \n\nCons: Several parts of the manuscript need more explanations. Additional experimental results (see below for details) are needed.\n(1) It is not clear what multi-head attention achieve semantically (as claimed: better capture structure information). \n(2) Figures are neither self-explained nor well explained in the main text.\n(3) The std of cross validation in each experiment should be reported. The mean performance alone is not enough to say a method performs better or not. It will be better to provide a p-value (e.g., t-test) to show if a method is statistically significantly better.\n(4) Four datasets from the Open Graph Benchmark were used. The authors should refer to the leaderboard for the performance of some baseline methods. For example, the leaderboard of HIV dataset reports that GIN has 0.7654 rather than 0.7595 listed in this manuscript. \n(5) The abstract points out that without considering task relevance is a weakness of the previous pooling method. However, it is not clear how the proposed approach make improvement(s) on this. \n(6) The proposed method does not necessary pass graph isomorphism as the nodes in the manuscript have attributes but the proof does not consider node attributes.\n(7) In appendix, examples in Figure 10 are confusing. More explanations are needed. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "cg9jTtrFgY", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 work studies the graph pooling operation for graph neural networks. It proposes the Graph Multiset Pooling which treats the graph pooling as a multiset encoding problem and can capture the graph structural information. It first employs multi-head attention to learn node features, where the query Q is a learnable matrix contains k vectors. Then a GMPool operation is performed and finally, the self-attention is used for learning inter-node relationships. Experimental results show the effectiveness of the proposed method.\n\nStrengths:\n+ This work studies an important problem, graph pooling. Graph pooling can learn high-level graph representations but is still less explored.\n+ The proposed method is interesting. By using a learnable query matrix, the method can reduce the n-node input to k-node output. The self-attention used after GMPool can learn the relationships between high-level embeddings.\n+ The experimental results are promising. The proposed method outperforms other compared methods.\n\nWeaknesses:\n- Even though the method is called Multiset Pooling, its method is not related to Multiset. The proposed method is mainly based on attention and self-attention mechanism. Then claiming the proposed method as Multiset Pooling is not convincing.\n- The experimental settings are not fair enough. The pooling operation is defined as reducing n-node input to k-node output. For all other methods, the pooling layer is connected with the global sum/average. However, in the proposed GMT, the GMPool is connected with a self-attention layer. It is not clear whether the proposed GMPool or the self-attention layer leads to the performance gain? A careful ablation study is needed.\n- I think the proposed method can be regarded as using SAGPool in the clustering-based pooling. The main difference is the multi-head attention and the learnable matrix S. Please comment if I missed something. \n- The use of graph structures is not very convincing. The GNN(H, A) is the simple message passing of GNNs. Then the graph structural information A is already incorporated in H since H is obtained by GNNs.\n- Several baselines are missing, such as Structpool and Edge Pooling. They should be discussed and compared.\n\nQuestions:\n1. If the query Q is obtained from the learnable matrix S, which is k*d dimensions. Then the output of  Att(Q; K; V ) should also have k*d’ dimension, which means the output is already reduced from n vectors to k vectors. Why do we still need the GMPool operation? The GMPool does not “compress the n nodes into the k typical nodes”.\n\n\n=====Update after rebuttal=====\n\nI have read the authors' rebuttal. Most of my concerns are addressed properly, and hence I am willing to increase my score from 4 to 6. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "_-aLkjo6bOu", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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 paper proposes a Transformer-like model: Graph Multiset Transformer to perform the graph pool/aggregation. Overall, the technique part is concrete and clear and the experimental evaluations are comprehensive. The authors also prove the expressive power regarding WL-test. However, several points need to be clarified or addressed.\n1.\tThe idea to utilize the Transformer-like architecture to model the graph neural network (GNN) is not new. Some existing works[1,2] have employed the transformer to enhance the expressive power of GNN. It’s better to add more discussions between GTM and the existing works to highlight its contribution. Meanwhile, several studies [3,4,5,6,7] about graph pooling / self-attention are missing. It’s better to make discussions in the related works. Moreover, if possible, I suggest making the comparison with these methods, especially the recent studies to make the whole experimental results more convincing, e.g. HaarPool, EigenPool, etc.\n \n1.\tAbout the experimental settings. 1) In Section 4.1, the authors state that the 4 molecule datasets are obtained from OGB dataset. However, in OGB dataset, it only contains HIV, while Tox21, Toxcast, BBBP is not included. Maybe there is a mistake. 2) For the molecular dataset, the data splitting is very curial for the final results. Meanwhile, the atom/bond feature extraction process for the molecular datasets is unclear. The authors need to clarify the data splitting (random/scaffold) and feature extraction process to ensure the reproducibility of experiments.\n \nMinor:\n\nIn Equation 6, what is the QW_i^Q ?\n\nIn Equation 8, why we need MH(H, H, H)? How about directly applying H into SelfAtt block, i.e., Z=H?\n\nIn the experiments, this paper only evaluates the memory efficiency of GMT. I would like to see the evaluation about the time efficiency of GMT with other baselines.\n \nOverall, this paper is well written and the experiments look solid. Considering the novelty issue, I think this is a borderline paper. I recommend “Marginally below acceptance threshold ” and would like to see the author's response.\n\n[1] Rong, Yu, et al. \"GROVER: Self-supervised Message Passing Transformer on Large-scale Molecular Data.\" arXiv preprint arXiv:2007.02835 (2020).\n\n[2] Chithrananda, Seyone, Gabe Grand, and Bharath Ramsundar. \"ChemBERTa: Large-Scale Self-Supervised Pretraining for Molecular Property Prediction.\" arXiv preprint arXiv:2010.09885 (2020).\n\n[3] Wang, Yu Guang, et al. \"Haar graph pooling.\" arXiv (2019): arXiv-1909.\n\n[4] Ma, Yao, et al. \"Graph convolutional networks with eigenpooling.\" Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019.\n\n[5] Bianchi, Filippo Maria, Daniele Grattarola, and Cesare Alippi. \"Spectral clustering with graph neural networks for graph pooling.\" (2020).\n\n[6] Ranjan, Ekagra, Soumya Sanyal, and Partha P. Talukdar. \"ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations.\" AAAI. 2020.\n\n[7] Li, Jia, et al. \"Semi-supervised graph classification: A hierarchical graph perspective.\" The World Wide Web Conference. 2019.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "VP1SqY-am0d", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "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 work extends the set transformer to obtain a method for multi-head attention pooling on multisets with connectivity (graphs). The authors show that the approach is as expressive as the WL isomorphism test and has better space complexity than existing node clustering networks. The method achieves state-of-the-art results on graph classification and strong results on graph reconstruction and generation.\n\nStrengths:\n- The paper is very well written and polished. \n- The figures complement the text well. \n- The work is technically and mathematically sound.\n- The method shows good results and is scalable, making it a valuable addition to the set of existing GNN operators.\n- The authors make an effort to substantiate their statements about expressivity and scalability with proofs.\n- The experiments are well chosen and show where improvements come from.\n\nWeaknesses:\n- The proven expressiveness is not a very strong statement, since most pooling approaches adhere to this property. It is nice to have the theoretical analysis though.\n- The method itself is an incremental variation of set transformers (Lee et al.), although adapted for a different type of input data.\n- Using the identity matrix as adjacency (as described in Appendix B, to work around the scalability issue of node clustering methods) seems to make the approach identical to the set transformer in all layers except the first, which dampens the contribution.\n\nThere is some potential for improvement in clarity of presentation:\n- In abstract: \"may yield representations that do not pass the graph isomorphism test\", in introduction, page 2: \"accurate representations of given graphs that can pass the WL-test\". Those sentences are confusing as it is not about representations passing the WL test, is it? It is about two graphs which are distinguished by WL get different representations (as correctly stated elsewhere in the work).\n- Regarding page 4, paragraph \"Graph Multi-head Attention\" and the following ones:\n\t- On the one hand, they are extremely close to Vaswani et al. and Lee et al. (sometimes even nearly the same sentences).\n\t- On the other hand, some things are left out, which are crucial for understanding, such as definitions of symbols for dimensionalities (n_q, d_k, d_v, d_model) and the origin of some matrices, see next point. \n\t- Where do the seeds S come from (for the non self attention operator)? It probably is a parameter matrix that is directly optimized but it is not completely clear (\"learnable\" is ambiguous, can also be the output of a network)\n\t- Suggestion: maybe the description of the pooling method becomes more clear when described in a top-down manner: Eq 7 -> Eq 6 -> Eq 5 -> Att\n\n\nExperiments:\n- Variances of graph classification results over the cross validation would be greatly appreciated (since there seems to be a space issue, they can go into the appendix)\n- The reconstruction architecture does not reconstruct adjacency. It might be interesting to see how well the method can do that (for the synthetic graphs for example)\n\nRelated work:\n- The work [1] should be mentioned and discussed in related work and compared against in experiments. It is also a pooling method with attention but seems to follow a different approach.\n\nTypos:\n- Figure 2 caption: \"to compress the all nodes\" -all\n- Proof of Theorem 4: \"but it is highly efficient than node clustering methods\"\n- Proof of Proposition 5: \"then the first them inherently generates\"\n\nAll in all, I think this paper has a valuable contribution, even if the method is incremental. Therefore, I tend to vote for accepting the paper but encourage the authors to improve on the mentioned issues in experiments, related work and presentation.\n\n[1] Ranjan et al.: ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations, AAAI 2020", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper addresses a very important issue in GNN, the definition of a well-defined pooling function for node aggregation. The proposed Graph Multiset Transformer, although not entirely new, seems to be useful in practice. Issues related to experimental results, as well as problems with presentation, have been solved by the authors's rebuttal, that presented solid experimental results and analysis.
Concerns about the real expressivity of the proposed approach when compared to Weisfeiler-Lehman graph isomorphism test do not affect the contribution delivered by the paper, that seems, at this point, significant. 
Decision: Accept (Poster)