Permutation-Invariant Variational Autoencoder for Graph-Level Representation Learning
Authors: Robin Winter
Frank Noe
Djork-Arne Clevert
Venue: NeurIPS 2021 Poster (2021)
Keywords: variational autoencoder
permutation invariance
graph
self-attention
representation learning
graph autoencoder

Abstract: Recently, there has been great success in applying deep neural networks on graph structured data. Most work, however, focuses on either node- or graph-level supervised learning, such as node, link or graph classification or node-level unsupervised learning (e.g. node clustering). Despite its wide range of possible applications, graph-level unsupervised learning has not received much attention yet. This might be mainly attributed to the high representation complexity of graphs, which can be represented by $n!$ equivalent adjacency matrices, where $n$ is the number of nodes.
In this work we address this issue by proposing a permutation-invariant variational autoencoder for graph structured data. Our proposed model indirectly learns to match the node ordering of input and output graph, without imposing a particular node ordering or performing expensive graph matching. We demonstrate the effectiveness of our proposed model for graph reconstruction, generation and interpolation and evaluate the expressive power of extracted representations for downstream graph-level classification and regression. 

Permutation-Invarian Variational Autoencoder for Graph-Level Representation Learning
Robin Winter
Frank Noé Freie Universität Berlin frank. www.oooeereeennn....mm
Bayer AG
Freie Universität Berlin
robin. winter@bayer.co com
Djork-Arné Clevert
Bayer AG
djork- www.emm.cccleeettbaerr.ooo
Abstract
Recently, there has been great success in applying deep neural networks on graph structured data. Most work, however, focuses on either node- or graph-level supervised learning, such node, link graph classification supervised learning (e.g., node clustering). Despite its wide range of possible applications, graph-level unsupervised representation learning has not received much attention yet. This might be mainly attributed to the high representation complexity of graphs, which can be represented by n! equivalent adjacency ma- trices, where n is the number of nodes. In this work we address this issue by proposing a permutation invaariant variational autoencoder for graph structured data. Our proposed model indirectly learns to match the node order of input and output graph, without imposing a particular node order or performing expensive graph matching. We demonstrate the effectiveness of our proposed model for graph reconstruction, generation and interpolation and evaluate the expressive power of extracted representations for downstream graph-level classification and regression.
node-level un-
Introduction
Graphs are an universal data structure that can be used to describe vast variety of systems from social networks to quantum mechanics ( Driven by the success of Deep Learning in fields such as Computer Vision and Natural Language Processing, there has been an increasing interest in applying deep neural networks on non-Euclidean, graph structured data as well 3] Most notably, generalizing Convolutional Neural Networks and Recurrent Neural Networks to arbitrarily structured graphs for supervised learning has lead significant advances on task such as molecular property prediction 4 or question-answering 5 Research on unsupervised learning on graphs mainly focused on node-level representation learning, which aims at embedding the local graph structure Usually, this is achieved by adopting an autoencoder framework where the encoder utilizes e.g., graph convolutional layers to aggregate local information at node level and the decoder is used to reconstruct the graph structure from the node embeddings. Graph-level representations are usually extracted by aggregating node-level features into a single vector, which common practice in supervised learning graph-level labels (4)
into latent node representations 6
9 10
Unsupervised learning of graph-level representations, however, has not yet received much attention, despite its wide range of possible applications, such as feature extraction, pre- pre-training for graph-level glassffcationnregrrssion tasks, graph matching or similarity ranking. This might be mainly attributed
to the high representation complexity of graphs arising from their inherent invariance with respect
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Input Graph
Per Nurmutation
Postoon Embeddingg
Output Graph
4
Soft-Sort
(0.3. 0.9, 0.5, 0.2, 9.6,0
scone
Self Attention
messages
Soft Atterson
(Agg(A v=== (one Soug, Mica Migs Mi m
Mrllec 6
entract messages
rectreet
sample emberiding
0'0
soge features
Figure I: Network architecture of the proposed model. Input graph is depicted as fully connected graph (dashed lines for not direct neighbours) with the additional embedding node up and edges (black color). Different node and edge types are represented by different colors and real edges by solid lines between nodes. Transformations parameterized by neural network represented by block arrows.
to the order of nodes within the graph. In general, a graph with n nodes, can be represented by n! equivalent adjacency matrices, each corresponding to a different node order. Since the general structure of a graph is invariant to the order of their individual nodes, graph-level representation should not depend on the order of the nodes in the input representation of graph, i.e. two isomorphic graphs should always be mapped to the same representation. This poses problem for most neural network architectures which are by design not invariant to the order of their inputs. Even carefully designed in permutation invariant way (e.g., Graph Neural Networks with final node aggregation step). there is no straight-forse forward way to train an autoencoder network, due to the ambiguous reconstruction objective, requiring the same discrete order of input and output graphs to compute the reconstruction loss.
How can learn a cottmmttation-nnvaainn graph-level representation utilizing permutation-vaite variant reconstruction objective? architecture that is by design invariant to the order of nodes in graph. We address the order ambiguity issue by training alongside the encoder and decoder model an additional permuter model that assigns to each input graph permutation matrix to align the input graph node order with the node order of the reconstructed graph.
this work we tackle this question proposing a graph autoencoder
Method
2.1 Notations and Problem Definition
An undirected Graph G EV,E) is defined by the set of n nodes V = fui...., and edges 3 {(, 1y)lu,, 2 V}. We can represent a graph matrix form by its node features X,, E Rexd, and adjacency matrix A, E {0.1)*M in the node order π E II. where II is the set of all n! permutations over V. We define the permutation matrix that reorders nodes from order order o' as P Pー = (ptz) (0, 1) 1 with Pij if n (i) a' x'(i) and Pij = O everywhere else. Since Graphs are invariant to the order of their nodes, note that
Gxr 9(X, Aa) = G(P X, P A PT = G(X Axt) Gz':
(1)
where T is the transpose operator. Let us now consider dataset of graphs G like to represented in a low-dimensional continuous space. We can adopt a latent variable approach and assume that the data is generate by process po po(G]z), involving an unobserved continuous random variable z. Following the work of Kingma and Welling [T]. we approximate the intractable posterior by go (G1z)) zs po 2) and minimize the lower bound on the marginal likelihood of graph G(O)
N we would
log Pe (g()) 2 L(0, 0() = -KL [ (2022)))))lpo0(() + E Eaoceggr [Io Cogro(Ga (g (1))
(2)

---

where the Bullback-Leibbe (KL) divergence term regularizes the encoded latent codes of graphs ( and the second term enforces high similarity of decoded graphs to their encoded counterparts. As graphs can be completely described in matrix form by their node features and adjacency matrix, we can parameterize qu and pe in Eq. by neural networks that encode and decode node features X and adjacency matrices (1) of graphs gl However, as graphs are invariant under arbitrary node re-ordering, the latent code z should be invariant to the node order x:
(z 9m) = (2(2)r)) for all π,, x' E II.
This can be achieved by parameterizing the encoder model qo by a permutation invariant function. However, if the latent code does not encode the input node order input graph G, and decoded graph 9.. no longer necessarily in the same order, as the decoder model has no information about the node order of the input graph. Hence, the second term in Eq. (2) cannot be optimized anymore by minimizing the reconstruction loss between encoded graph Gr and decoded graph &x' in straight-forward way. They need to be brought in the same node order first. We can rewrite the expectation in Eq. (2) using Eq. (
E (=((s)))))
[log po (o 12] = 2o(x)s!")) =E) [Log
Po (P+-+
(4)
Since the ordering of the decoded graph x' is subject to the learning process of the decoder and thus unknown in advance, finding Pa is not trivial. In [12]. the authors propose to use ap- proximate graph matching to find the permutation matrix P Pa- that maximizes the similarity s(Xa', P ( - Agii b,,,,xx P Ag n.), which involves up to O(n*) re-ordering operations at each training step in the worst case 13
2.2 Permutation-Invarte
Variational Graph Autoencoder
In this work we propose to solve the reordering problem in Eq. implicitly by inferring the permutation matrix P from the input graph 9. by model ge (Gm) that is trained to bring input and output graph in the same node order and used by the decoder model to permute the output graph. We train this permuter model jointly with the encoder model (z(2).n) and decoder model po( |z, -x)) optimizing:
C(ø, A ui: (
KL (o
go go) Po(!! z, go (g()))
(5)
Intuitively, the permuter model has to learn how the ordering of nodes in the graph generated by the decoder model will differ from a specific node order present in the input graph. During the learning process, the decoder will learn its canonical ordering that, given latent code 2, it will always reconstruct a graph in. The permuter learns to transform/permute this canonical order to a given input node order. For this, the permuter predicts for each node i of the input graph score s; corresponding to its probability to have low node index in the decoded graph. By sorting the input nodes indices by their assigned scores matrix P P = (Piz) E (0, 1]mxn, with
infer the output node order and construct the respective permutation
f1, 0. else
if = arrgoror(()))
Pij
to align input and output node order. Since the argsort operation is not differentiable, we utilizes the continuous relaxation of the argsort operator proposed in [5]:
P softmax d(sort (s)1 1s
T
where the softmax operator is applied row-wise, d(z, y) is the Lo-m and 7 E R4, a temperature- parameter. By utilizing this continuous relaxation of the argsort operator, can train the permuter model S6 in Eq. (5) alongside the encoder and decoder model with stochastic gradient descent. In order to push the relaxed permutation matrix towards a real permutation matrix (only one in every row and column), we add to Eq. (5) a row- and column- wiie entropy term as additional penalty term:
(P ) Σ H HP C(P) HH(P
(8)
3
3

---

with Shannon entropy (x) = = Es By log(I;) and normalized probabilities Pt.. E, pi.
P
Propositions 1. A square matrix P is real permutation matrix if and only C(P) = 0 and the doubly stochastic constraint Paj (), Σ,p( = V.. Σ, Poj = Vi holds.
Proof. See Appendix A.
By enforcing P - P. we ensure that no information about the graph structure is encoded in P and decoder model py ( zz, P) can generate valid graphs during inference, without providing a specific I and decode the learned canonical node order). At this
permutation matrix P (e.g., one can set point it should also be noted, that our proposed framework can easily be generalized to arbitrary sets of elements, although we focus this work primarily on sets of nodes and edges defining a graph.
Graph Isomorphism Problem. Equation (5) gives us means to train an autoencoder framework with a permutation invariant encoder that maps graph f 9 - 2 in an efficient manner. Such an encoder will always map two topologically identical graphs (even with different node order) to the same representation z. Consequently, the question arises, if we can decide for pair of graphs whether they are topologically identical. This is the well-studied graph isomorphism problem for which no polynomial oolynomial-time algorithm known yet [66 [7. As mentioned above, in our framework, two isomorphic graphs will always be encoded to the same representation. Still, it might be that two non-isomorphie graphs will be mapped to the same point (non-injectivee. However, if the decoder able to perfectly reconstruct both graphs (which is easy to check since the permuter can be used to bring the decoded graph in the input node order), two non-isomorphic graphs must have a different representation z. If two graphs have the same representation and the reconstruction fails, the graphs might still be isomorphic but with no guarantees. Hence, our proposed model can solve the graph isomorphism problem at least for all graphs it can reconstruct.
2.3 Details of the Model Architecture
In this work we parameterize the encoder, decoder and permuter model Eq. (5) by neural networks utilizing the self-attention framework proposed by Vaswani et al. [8]] on directed messages represent- ing a graph. Figure [I, visualizes the architecture of the proposed permutation-invariat autoencoder. In the following, we describe the different parts of the model in detail)
variational
Graph Representation by Directional Messages. In general, most graph neural networks can be thought of as so called Message Passing Neural Networks (MPNN) [9]. The key idea of MPNNs is the aggregation of neighbourhood information by passing and receiving messages of each node to and from neighbouring nodes in a graph. We adopt this view and represent graphs by its messages between nodes. We represent a graph gXX, E), with node features X E Rexds and edge features E E Rexxxxd, by its message matrix M (m:y) E RRuxnxdm;
mij = a [[x|||x]] ||x||ess] W +b,
with non-linearity a, concatenation operator and trainable parameters W and b. Note, that nodes in this view are represented by self-messages diag(M), messages between non-connected nodes exists, although the presence or absence of a connection might be encoded in eij. and if M is not symmetric, edges have an inherent direction.
Self-Attention Directed Messages. We follow the idea of aggregating messages from neigh- bours in MPNNs, but utilize the self-attention framework proposed by Vaswani et al. [18 for sequential data. Our proposed model comprises multiple layers of multi-headed scaled-dot product attention. One attention head is defined by:
QK
Attention (Q, K. V) = softmax
V
(10)
with queries Q = M keys K = MW* K and values V = VW and trainable weights Wo Rd... xd,, W E Rd xd and W E gdd..dd, For multi-headed self-attention we concatenate multiple attention heads together and feed them to a linear layer with d,, output features. Since the message matrix M of graph with n nodes comprises n² messages, attention of all messages to all messages would lead to O(n*) complexity. We address this problem by letting messages
Code available https: /ttp//ggtttttttt

---

maj only attend on incoming messages mki reducing the complexity to On²²). ). We achieve this by representing Q as (m X n X d) tensor and K and V by a transposed (n x m d) tensor, resulting into a (m x v)) attention tensor, with number of nodes m = n and number of features d. That way, we can efficiently utilize batched matrix multiplications in Eq. (TOp, in contrast to computing the whole (12 n²) attention matrix and masking attention on not incoming messages out.
Encoder To encode graph into fixed-sized, permutation- germutation-ivaariant, continuous latent represen- tation, we add to input graphs a dummy node to, acting as an embedding node. To distinguish the embedding node from other nodes, add an additional node and edge type represent this node and edges to and from this node. After encoding this graph into a message matrix M as defined in Eq. ( we apply L iterations of self-attention to update M 4), accumulating the (enc, f.) Following (.]. graph structure in the embedding node, represented by the self-message m0 we utilize the reparameterization trick and sample the latent representation z of a graph by sampling from a multivariate normal distribution:
Z ~ (m,oo fenc, 1),, (m (enc, 4) D)).
(11)
with fe mo.o + ja Rdd and fo mo,0 E Rd: parameterized by a linear layer.
Permuter To predict how re-order the nodes in the output graph to match the order of nodes in the input graph, we first extract node embeddings represented by self-messages on the main diagonal of the encoded message matrix m (enc; (.) diag (M ()) for i >> O. We score these messages by function fa mi, Eq. retrieve the permutation matrix P.
IR, parameterized by a linear layer and apply the soft-sort operator (see
Decoder We initialize the message matrix for the decoder models input with the latent representa- tion z at each entry. To break symmetry and inject information about the relative position/order of nodes to each other, we follow [8] and define position embeddings in dimension &
sinii/100002x/44 ) for even k cos(1/10000 /dd)), /d.), for odd l:
PE(1)
(12)
It follows for the initial decoder message matrix M (dec 0):
mij (dec, 0) ([z + (PE PE(J)]] W + b),
(13)
Since the self-attention based decoder model is permutation equivariant, we can move the permutation operation in Eq. (5) in front of the decoder model and directly apply it to the position embedding
sequence (see Figure []. After iterations of self-attention on the message matrix M, we extract node features x, X and edge features ei. E E by a final linear layer:
x; m., W +b"
C.jj 0.5 (m, + m,,) W + bb,
(14)
with learnable parameters W E Rdmxdd W E Rdm.dd, b" Rd and be E Rd.
Overall Architecture We now describe the full structure of our proposed method using the in- gredients above (see Figure []. Initially, the input graph is represented by the directed message matrix (mne, 0) including an additional graph embedding node uo. The encoder model performs L. iterations of self-attention on incoming messages. Next, diagonal entries of the resulting message (eae, L) representing embedding node vo. is used to matrix (eac, L) are extracted. Message m
condition the normal distribution, graph representation is sampled from. The other diagonal entries (ene, L) are transformed into scores and sorted by the Soft-Sort operator to retrieve the permutation mi,
matrix P. Next, position embeddings (in Figure | represented by single digits) are re-ordered by applying P and added by the sampled graph embedding z. The resulting node embeddings are used initialize message matrix M 0) and fed into the decoding model. After L iterations of self-attention, diagonal entries are transformed to node features X and off off-diagonal entries to edge features to generate the output graph. In order to train and infer on graphs of different size, we pad all graphs in a batch with empty nodes to match the number of nodes of the largest graph. Attention on empty nodes is masked out at all time. To generate graphs of variable size, we train alongside the variational autoencoder an additional multi-layer perceptron to predict the number of atoms of graph from its latent representation z. During inference, this model informs the decoder on how many nodes to attend to.
5

---

Table 1: Negative log likelihood (NLL) and area under the receiver operating characteristics curve (ROC-AUC) for reconstruction the adjacency matrix of graphs from different families. We compare our proposed method (PIGAE) with Graph Autoencoder (GAE) ( and results of Graphite and Graph Autoencoder (GAE*) reported in [20]. PIGAE" utilize topological distances of nodes in a graph as edge feature.
MODELS
ERDOS-RENT
BARABASI-ALBER
EGO
NLL
ROC-AUC
NLL
ROC-AUC
NLL
ROC-AUC
PIGAE
20.5 + 0.9
0.1
27.2 0.9
9.2
23.4 0.5
97.8 + 0.3
PIGAE"
19.5 1 0.8
99.4 0.1
15.2 0.8
99.5
22.4 0.5
98.8 1 0.3
GAE
186 3
5.1
199 3
5..41..1
59.1 0.1
GAE*
222 8
236 1 15
197 12
GRAPHITE
196 =
192 +
183 =1
Key Architectural Properties Since no position embeddings are added to the input of the encoders
self-attention layers, accumulated information in the single embedding node vi (Mooo) is invariant
to permutations of the imput node order. Hence, the resulting graph embedding is permutation invariant as well. This encode whole graphs effectively by concatenating all node embeddings, resulting in a graph-leve representation that is different for isomorphic graphs, as the sequence of node embeddings permutes equivalently with the input node order. As no information about the node order is encoded in the graph embedding z, the decoder learns its own (canonical) node order, distinct graphs are deterministically decoded in. The input node order does not influence this decoded node order. As the decoder is based on permutation equivariant self-attention layers, this canonical order is solely defined with respect to the sequence of position embeddings used to initialize the decoders input. If the sequence of position embeddings permuted, the decoded node order permutes equivalently. Thus, by predicting the right permutation matrix, input and output order can be aligned to correctly calculate the reconstruction loss. Input to the permuter model [m 1..1...... ........ 1m+1,n+] is equivariant to permutations in the input node order (due to the equivariant self-attention layers in the encoder). Since the permuter model itself (i.e., the scoring function) is also permutation equivariant (node-wise linear layer), resulting permutation matrices P are equivariant permutations in the input node order. Consequently. if the model can correctly reconstruct a graph in a certain node order, it can do it for all n! input node orders, and the learning process of the whole model is independent to the node order of graphs in the training set.
stark contrast to classical graph autoencoder frameworks [8] 20 21. that
3 Related Works
Most existing research unsupervised graph representation learning focuses node-level represen- tation learning and can be broadly categorized in either shallow methods based on matrix factorization
25] or random walks (26 27], and deep methods based on Graph Neural Networks (GNN) Kipf and Welling [8] proposed a graph autoencoder (GAE), reconstructing the adjacency matrix by taking the dot product between the latent node embeddings encoded by GNN. Grover et al.
22 23
24
2 3.
20 build on top of the GAE framework by parameterizing the decoder with additional GNNs, further refining the decoding process. Although graph-level representations in GAB-like approaches can be constructed by concatenating all node-level representations, note, that as a consequence they are only permutation equivariant and not permutation invariant. Permutation invariant representations could be extracted only after training by aggregating node embeddings into a single-vector representation. However, such representation might miss important global graph structure. Samanta et al. [21) proposed a GAE-like approach, which parameters are trained in permutation invariant way, fol- lowing (2 utilizing
with randomized tie breaking during the child-selection step. However, graph-level representations are still constructed by concatenation of node-level embeddings, this method still encodes graphs only
coimuutation-qqivaiiaa way. A different line of work utilized Normalizing Flows [29] to address variational inference on graph structured data
based on node-level latent variables 33 31 32]
Research gruph-level representations has mainly focused on supervised learning, e.g., graph-level classification by applying a GNN followed by global node feature aggregation step (e.g., mean or max pooling) 4 or a jointly learned aggregation scheme 33). Research graph-level unsupervised

---

b)
mncee p-0.0 meaeeiid s0t5, wid
a) Euclidean distance over graph editing distance, averaged over 1000 Barabasi-Alber graphs with m 2. b) t-SNE projection of representations from ten different graph families with different parameters. Example graphs are shown for some the clusters. c) Legend of t-SNE plot explaining colours and symbols. Graph family abbreviations: Binomial (B), Binomial Ego (BE), Barabasi-A (BA), Geometric (G), Regular (R), Powerlaw Tree (PT), Watts-Strogatz (WA), Extended Barabasi-Albert (EBA), Newman-Watts-Sree Sttts-Strogatzz (NWA), Dual-Barabasi-Alle (DBA).
Figure 2:
representation learning has not yet received much attention and existing work is mainly based on contrastive learning approaches. Narayanan al. (34 adapted the doc2vec method from the field of natural language processing to represent whole graphs by a fixed size embedding, training a skipgram method on rooted subgraphs (graph2vec). Bai al. (35] proposed a Siamese network architecture, trained on minimizing the difference between the Euclidean distance of two encoded graphs and their graph editing distance. Recently, Sun al. (36], adapted the Deep InfoMax architecture [37] to graphs, training on maximizing the mutual information between graph-level representations and rep- resentations of sub-graphs different granularity (InfoGraph). Although those contrastive learning approaches can be designed to encode graphs in permutation invariant way, they cannot be used to reconstruct or generate graphs from such representations.
Another line of related work concerns itself with generative models for graphs. Besides methods based on variational autocncoders 88 20 [2] and Normalizing Flows [30) 31 32), graph generative
models have also been recently proposed based generative adversarial neural networks [38 39)
and deep auto-regressive models [40] 28 4. Moreover, due to its high practical value for drug dis-
covery, many graph generating methods have been proposed for molecular graphs 42 43
Although graph generative models can be trained permutation invariant way 42 models not be used extract permutation invariant graph-level representations.
21
those
Recently, Yang et al. [46) proposed a GAE-like architecture with a node-feature aggregation step to extract permutation invariant graph-level representations that also be used for graph generation. They tackle the discussed ordering issue of GAFs in the reconstruction by training alongside the GAE Generative Adversarial Neural Network, which's permutation invariant discriminator network is used to embed input and output graph into a latent space. That way, a permutation invariant reconstruction loss can be defined as a distance in this space. However, as this procedure involves adversarial training of the reconstruction metric, this only approximates the exact reconstruction loss used in our work and might lead to undesirable graph-level representations.
4 Experimental Evaluation
We perform experiments on synthetically generated graphs and molecular graphs from the pub- lic datasets QM9 and PubChem. At evaluation time, predicted permutation matrices are always discretized to ensure their validity. For more details training, see Appendix C.
7

---

Table 2: Classification Accuracy of our method (PIGAE), classical GAE, InfoGraph (IG), Shortest Path Kernel (SP) and Weisheiler-Lehman Sub-tree Kernel (WL) on graph class prediction.
PIGAE
GAB
IG
SP
WL
0.83 1 0.01
0.65 1 0.01
0.75 + 0.02
0.50 + 0.02
0.73 1 0.01
4.1 Synthetic Data
Graph Reconstruction In the first experiment we evaluate our proposed method on the reconstruc- tion performance of graphs from graph families with a well-defined generation process. Namely, Erdos-Renyi graphs [47], with an edge probability of p = 0.5, Barabasi-Alber graphs [48], with m = 4 edges preferentially attached to nodes with high degree and Ego graphs. For each family we uniformly sample graphs with 12-20 nodes. The graph generation parameters match the ones reported in (0), enabling to directly compare Graphite. As additional baseline compare against the Graph Autoencoder (GAE) proposed by Kipf and Welling [8]. As Grover et al. [20] only report negative log-likelihood estimates for their method Graphite and baseline GAE we also reevaluate GAE and report both negative log-likelihood (NLL) estimates for GAE to make better comparison Graphite possible (accounting for differences in implantation or the graph generation process). In Table I family. On all four graph datasets our proposed model significantly outperforms the baseline methods, reducing the NLL error in three of the four datasets by approximately one magnitude. Utilizing the topological distance instead of just the connectivity as edge feature (compare further improves the reconstruction performance.
we show the evaluation metrics on a fixed test set of 25000 graphs for each graph
Qualitative Evaluation To evaluate the representations learned by our proposed model, we trained model on a dataset of randomly generated graphs with variable number of nodes from ten different graph families with different ranges of parameters (see Appendix for details). Next, we generated a test set of graphs with a fixed number of nodes from these ten different families and with different fixed parameters. In total we generated graphs in 29 distinct settings. In Figure [ we visualized the t-SNE projection [50] of the graph embeddings, representing different families by colour and different parameters within each family by different symbols. In this 2-D projection, we can make out distinct clusters for the different graph sets. Moreover, clusters of similar graph sets tend to cluster closer together. For example, Erdos- Renls graphs form for each edge probability setting (0.25, 0.35, 0.5) distinct cluster, while clustering in close proximity. As some graph families with certain parameters result in similar graphs, some clusters are less separated or tend to overlap. For example, the Baraaasi--lbberr graph family, which attaches nodes with either my or m2 other nodes, naturally clusters in between the two Barabasi-Alber graph clusters with m1 and m m2.
Graph Editing Distance A classical way of measuring graph similarity is the so called graph editing distance (GED) (5I). The GED between two graphs measures the minimum number of graph editing operations to transform one graph into the other. The set of operations typically includes inclusion, deletion and substitution of nodes or edges. To evaluate the correlation between similarity in graph representation and graph editing distance, we generated set of 1000 Barabasi-A Abbett (m 3) graphs with 20 nodes. For each graph we successively substitute randomly an existing edge by new one, creating a set of graphs with increasing GED with respect to the original graph. In Figure 2 we plot the mean Euclidean distance between the root graphs and their 20 derived graphs with increasing GED. We see strong correlation between GED and Euclidean distance of the learned representations. In contrast to classical GAEs, random permutations of the edited graphs have no effect on this correlation (see Appendix D for comparison).
Graph Isomorphism and Permutation Matrix To empirical analyse if our proposed method detects isomorphic graphs, we generated for 10000 Barabasi-Albert graphs with up to 28 nodes a randomly permuted version and a variation only one graph editing step apart. For all graphs the Euclidean distance between original graph and edited graph was at least greater than 0.3. The randomly permuted version always had the same embedding. Even for graphs out of training domain (geometric graphs with 128 nodes) all isomrrphic and non-isomorphic graphs could be detected. Additionally, we investigated how well the permuter model can assign a permutation matrix to graph.
8

---

Start
End
Figure 3: Linear interpolation between two graphs in the embedding space. Start graph's edges are colored red. End graph's edges are colored blue. Edges present in both graphs colored black. Thick lines are present in decoded graph, thin lines are absent.
As the high reconstruction performance in Table I suggest, most of the time, correct permutation matrices are assigned (See Appendix E for a more detailed analysis). We find that permutation matrices equivalently permute with the permutation of the input graph (See Appendix E).
Graph Classification order to quantitatively evaluate how meaningful the Iearned represen- tations are, evaluate the classification performance of a Support Vector Machine (SVM) predicting the correct graph set label (29 classes as defined above) from the graph embedding. As baseline we compare against SVMs based
classical graph kernel methods, namely Shortest
Path Kernel (SP) [52) and Weisfeiler-Lehman Sub-tree Kernel (WL) (53) as well as embeddings extracted by the recently proposed contrastive learning model InfoGraph (IG) (36) and averaged node embeddings extracted by a classical GAE. Our model, IG and GAE where trained on the same synthetic dataset. In Table
report the accuracy for each model and find the SVM based on representations from our proposed model to significantly outperform all baseline models. Notably, representations extracted from a classical GAE model, by aggregating (averaging) node-level em- beddings into a graph-level embedding, perform significantly worse compared to representations extracted by our method. This finding is consistent with our hypothesis that aggregation of unsuper- vised learned node-level (local) features might miss important global features, motivating our work on graph-level unsupervised representation learning.
Graph Interpolation The permutation invariance property of graph-level representations also enables the interpolation between two graphs in a ttraight-forwat way. With classical GAEs such interpolations cannot be done in meaningful way, interpolations between permutation dependent graph embeddings would affect both graph structure as well as node order. Figure we show how successive linear interpolation between the two graphs in the embedding space results in smooth transition in the decoded graphs, successively deleting edges from the start graph (red) and adding edges from the end graph (blue). To the best of our knowledge, such graph interpolations have not been report in previous work yet and might show similar impact the graph generation community as interpolation of latent spaces did in the field of Natural Language Processing and Computer Vision.
4.2 Molecular Graphs
Next, we evaluate our proposed model on molecular graphs from the QM9 dataset 54 55 This datasets contains about 134 thousand organic molecules with up to 9 heavy atoms (up to 29 atoms/nodes including Hydrogen). Graphs have 5 different atom types (C, N, O. F and H), different formal charge types (-1, 0 and 1) and 5 differ bond types (no-, single- double-, triple- and aromatic bond). Moreover, the dataset contains an energetically favorable conformation for each molecule in form of Cartesian Coordinates for each atom. We transform these coordinates to an rrotatio-iinvaiian Euclidean distance matrix and include the distance information as additional edge feature to the graph representation (More details in Appendix F).
Graph Reconstruction and Generation We define holdout set of 10,000 molecules and train the model on the rest. Up on convergence, we achieve the hold out set balanced accuracy of 99.93% for element type prediction, 99.99% for formal charge type prediction and 99 25% for edge type prediction (includs prediction of non-existence of edges). Distances between atoms reconstructed with root mean squared error of 0.33A and coefficient of determination of R² 0.94.

---

Originll
Sangled
encode query Dataset PIGAE (ours)
ECFP
Classification (ROC-AUC
BACE
0.824 + 0.005
0.82 = 0.02 0.78 0.03
BBBP
0.81 + 0.04
Regression (MSE) !)
ESOL
0.10 + 0.01
0.25 = 0.02 0.39 0.02
LIPO
0.34 + 0.02
Table 3: Downstream performance for molecular property prediction tasks.
Figure Example Molecular conformations sam- pled around original graph representation.
In the field of computational chemistry and drug discovery, the generation of energetically reasonable conformations for molecules is topic of great interest (56). Since model is trained approxi- mating the data generating process for molecules and their conformations, we can utilize the trained model to sample molecular conformations. To retrieve set of conformations, molecule into its latent representation and randomly sample around this point by adding a small noise and decode the resulting representations. We utilize Multidimennsonal Scaling (MDS) [57] to transform decoded distance matrix back to Cartesian Coordinates. In Figure H of molecular conformations sampled from the trained model. Under visual inspection, we find that sampled conformations differ from encoded conformations, while still being energetically reasonable (e.g., rotation along rotatable bonds while avoiding clashes between atoms).
we show examples
Molecular Property Prediction Finally, we evaluate the learned representations for molecular property prediction. In order to accurately represent molecular graphs from different parts of the chemical space, we train our proposed model on larger dataset retrieved from the public PubChem database (88) We extracted organic molecules with up 32 heavy atoms, resulting into set of approximately 67 million compounds (more details in Appendix F). We evaluate the representations of the trained model based on the predictive performance of SVM on two classification and two regression tasks from the MoleculeNet benchmark (59). compare representations derived from our pre-trained model with the state-of-thes
Extended Connectivity Fingerprint molecular descriptors (radius=3, 2048 dim) [60]. For each task and descriptor, the hyperparameter of the SVM was tuned in nested cross validation. The results presented in Table Deseriptors derived from pre- pre-trained model seem to represent molecular graphs in a meaningful way as they outperform the
baseline average in three out of four tasks.
Conclusion, Limitations and Future Work
In this work we proposed a permutation invariant autoencoder for graph-level representation learning. By predicting the relation (permutation matrix) between input and output graph order, our proposed model can directly be trained on node and edge feature reconstruction, while being invariant to a distinct node order. This poses, the best of our knowledge, the first method for non-contrastive and non-adversarial learning of permutation invariant graph-level representations that can also be used for graph generation and might be an important step towards more powerful representation learning methods on graph structured data or sets in general. We demonstrate the effectiveness of our method in encoding graphs into meaningful representations and evaluate its competitive performance in various experiments. Although we propose way of reducing the computational complexity by only attending on incoming messages in our directed message self-attention framework, in its current state, our proposed model is limited in the number of nodes graph can consist of. However, recently, much work has been done on more efficient and sparse self-attention frameworks 61
62 63). In
future work, we aim at building up on this work to scale our proposed method to larger graphs. Moreover, we will investigate further into the generative performance the proposed model, as this work was mainly concerned with its representation learning capability.
10

---

Funding Disclosures
D.A.C. received financial support from European Commission grant numbers 963845 and 956832 under the Horizon2020 Framework Program for Research and Innovation. F.N. acknowledges funding from the European Commission (ERC CoG 772230 "ScaleCell") and MATH+ (AAl-6), F.N. is advisor for Relay Therapeutics and scientific advisory board member of lqbit and Redesign Science.
References
[1] William L Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and upplications. arXiv preprint arXiv:/709.05550 2017.
[2] Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34 (4):18-42, 2017.
[3] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 2020.
[4] David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks graphs for learning molecular fingerprints. Advances in neural information processing systems, 28:2224 2232, 2015.
[5] Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint 15 1.1.:499,, 2015.
[6] Shaosheng Cao, Wei Lu, and Qiongkai Xu. Deep neural networks for learning graph rep- resentations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
[7] Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1225-1234, 2016.
[8] Thomas Kipf and Max Welling. Variational 16Xiv:1611.073000 2016.
graph auto-encoders. arXiv preprint
[9] Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the eleventh ACM international conference on web search and data mining, pages 459-467, 2018.
[10] Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang. Adversarially regularized graph autoencoder for graph embedding. arXiv preprint
2018.
[11] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint arXiv:1312.611 14, 2013.
[12] Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In International Conference on Artificial Neural Networks, pages 412-422. Springer, 2018.
[13] Minsu Cho, Jian Sun, Olivier Duchenne, and Jean Ponce. Finding matches in a haystack: max-pooling strategy for graph matching in the presence of outliers. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2083-2090, 2014.
[14] Sebastian Prillo and Julian Fisenschlos. Softsort: A continuous relaxation for the argsort operator. In International Conference Machine Learning, pages 7793-7802. PMLR, 2020.
[15] Aditya Grover, Erie Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations, arXiv preprint
2019.

---

[16] Michael R Garey. A guide to the theory of up-completeness. Computers and intractability, 1979.
[17] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprini
2018.
[18] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998 6008,, 2017.
[19] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. arXiv preprint arXiv: 2017.
[20] Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs. In International conference on machine learning, pages 2434-2444. PMLR, 2019.
[21] Bidisha Samanta, Abir De, Gourhari Jana, Vicenç Gómez, Pratim Kumar Chattaraj, Niloy Ganguly, and Manuel Gomez-Rodriguez. Nevae: A deep generative model for molecular graphs. Journal of machine learning research. 2020 Apr: 21 (114): 1-33, 2020.
[22] Amr Ahmed, Nino Shervashidze, Shravan Narayanamurthy, Vanja Josifovski, and Alexan- der J Smola. Distributed large-scale natural graph factorization. In Proceedings of the 22nd international conference World Wide Web, pages 37-48, 2013.
[23] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Nips, volume 14, pages 585-591, 2001.
[24] Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. In Proceedings of the 24th ACM international on conference on information and knowledge management, pages 891-900, 2015.
[25] Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity pre- serving graph embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1105-1114, 2016.
[26] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710, 2014.
[27] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855-864, 2016.
[28] Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrnn: Generat- ing realistic graphs with deep auto-regressive models. In International Conference on Machine Learning, pages 5708-5717. PMLR, 2018
[29] Danilo Rezende and Shakir Mohamed. Variational inference with normalizing flows. In International conference on machine learning, pages 1530-1538, PMLR, 2015.
[30] Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows. arXiv preprint arXiv:/90k 13/77, 2019.
[31] Chengxi Zang and Fei Wang. Moflow: an invertible flow model for generating molecular graphs. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 617-626, 2020.
[32] Tony Duan and Juho Lee. Graph embedding vae: A permutation invariant model of graph structure. arXiv preprint arXiv: 1xXx::991000807, 2019.
[33] Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. arXiv preprint arXiv:1806.08804 2018.
12

---

[34] Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. graph2vec: Learning distributed representations of graphs. arXiv preprint urXiv:/707.000
2017.
[35] Yunsheng Bai, Hao Ding, Yang Qiao, Agustin Marinovic, Ken Gu, Ting Chen, Yizhou Sun, and Wei Wang. Unsupervised inductive graph-level representation learning via graph-grane proximity, arXiv preprint arXiv::904 994.01098, 2019.
[36] Fan- Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. arXiv preprint arXiv: 1908. 01000, 2019.
[37] Devon Hjelm, Alex Fedorov, Samuel Marchl-Ma Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint arXiv: 066700 2018.
[38] Hongwei Wang. Jia Wang, Jialin Wang. Miao Zhao, Weinan Zhang, Fuzheng Zhang, Xing Xie, and Minyi Guo. Graphgan: Graph representation learning with generative adversarial nets, In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018
[39] Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs. arXiv preprint arXiv: /973, 2018.
[40] Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint arXiv:/803.03322 2018.
[41] Chenhao NIu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling. In International Conference Artificial Intelligence and Statistics, pages 4474-4484. PMLR, 2020.
[42] Jiaxuan You, Bowen Liu, Rex Ying, Vijay Pande, and Jure Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. arXiv preprint arXiv:1806.0244 02473, 2018.
[43] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International Conference on Machine Learning, pages 2323 2332. PMLR, 2018
[44] Rafael G.ómez-Bomareee Jennifer N Wei, David Duvenaud, José Miguel Hernández-Lobate Benjamín Sánchez-Lengeling Dennis Sheberla, Jorge Aguilera-Iparraguirre, Timothy D Hirzel, Ryan Adams, and Alán Aspuru-Guzik. Automatic chemical design using a data-driven continuous representation of molecules. ACS central science, 4(2):268-276 2018.
[45] Rocío Mercado, Tobias Rastemo, Edvard Lindelöf, Günter Klambauer, Ola Engkvist, Hongming Chen, and Esben Jannik Bjerrum. Graph networks for molecular design. Machine Learning: Science and Technology. 2020.
[46] Carl Yang, Peiye Zhuang, Wenhan Shi, Alan Luu, and Pan Li. Conditional structure generation through graph variational generative adversarial nets. In NeurlPS, pages 1338-1349, 2019.
[47] Paul Erdós and Alfréd Rényi. On the evolution of random graphs.
[48] Albert-Lász16 Barabási and Réka Albert. Emergence of scaling in random networks. science, 286(5439):509-512 1999.
[49] Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. arXiv preprint arXiv:2009.00142,, 2020.
[50] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, (11). 2008
[51] Alberto Sanfeliu and King-Sun Fu. A distance measure between attributed relational graphs for pattern recognition. IEEE transactions systems, man, and cybernetics, (3):353-362, 1983.
13

---

[52] Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-pand kernels on graphs. In Fifth IEEE international conference on data mining (ICDM'03) 005), pages 8-pp. IEEE, 2005.
[53] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
[54] Lars Ruddigkeit, Ruud Van Deursen, Lorenz Blum, and Jean-Louis Reymond. Enumeration of 166 billion organic small molecules in the chemical universe database gdb- 17. Journal of chemical information and modeling, 52(1 (011))286422877 2012.
[55] Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):1-7, 2014.
[56] Paul CD Hawkins. Conformation generation: the state of the art. Journal of Chemical Information and Modeling, 1777:177771 2017.
[57] Joseph B Kruskal. Multtidimensional scaling. Number 11. Sage, 1978.
[58] Sunghwan Kim, Paul A Thiessen, Evan Bolton, Jie Chen, Gang Fu, Asta Gindulyte, Lianyi Han, Jane He, Siqian He, Benjamin A Shoemaker, et al. Pubchem substance and compound databases. Nucleic acids research, 240D1):D122--D1213, 2016.
[59] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9(2):113 530, 2018.
[60] David Rogers and Mathew Hahn. Extended-coonectiige fingerprints. Journal of chemical information and modeling, 50(5):742-754, 2010.
[61] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv:1904. 10509, 2019.
[62] Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention-based permutation-invarian neural networks. In International Conference Machine Learning, pages 3744-3753. PMLR, 2019.
[63] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv preprint
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section S
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] See Section 2.1
(b) Did you include complete proofs of all theoretical results? (es)] See Appendix A
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes] See Appendix
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "ofK3QHDt76Y", "reviewer": "Reviewer_1wGW", "summary": "This work proposes PIGAE, a graph-level VAE with a permutation-invariant reconstruction loss (expected likelihood). To achieve permutation-invariance, the authors propose learning a (relaxed) permutation as a function of the encoded (input) graph. The paper demonstrates the performance of PIGAE on synthetic benchmarks, and real-world molecular graphs. \n", "questions": "", "limitations": "", "rating": 6, "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": "In general, the reconstruction loss for graph-level VAEs is not invariant to permutations. As a consequence, the decoders can overfit to specific node orderings observed during training. Previous works end up using (sometimes costly) heuristics to tackle this issue. To overcome this limitation, the authors learn the permutation as a function of the encoded graph. Then, the authors use this learned permutation to make their loss permutation invariant. The results on graph reconstruction are particularly impressive. Overall, the authors touch on an important problem, and the work is novel. Notably, the authors fail to clearly flesh out the challenge in training graph-level VAEs (neither in the abstract nor introduction). As a result, the text may be difficult to follow for a general audience.\n\n**Comments and questions**\n\n* For any graph, the mean $\\mu$ and the variance $\\sigma$ of the latent $z$ are linear functions of $m_{0,0}$ (a scalar). This implies that the mean of $z$'s for all encoded graphs lies in the same line. The same applies to $\\sigma$'s. This seems to be a strong restriction.\n\n* To evaluate the generation of PIGAE, the authors perturb the latent of an existing graph and decode it back (Figure 3). This explores only a small part of the support of the prior. Consequently, I believe the experiment does properly evaluate the quality of PIGAE samples. To assess the generation quality of PIGAE, the authors should simply decode samples from the prior. Overall, the paper lacks examples of graphs generated by PIGAE for different problems/datasets.   \n\n* To sample from VAEs, we draw a sample from the prior and propagate it through the decoder. In this work, the decoder requires a permutation. How does PIGAE work during sampling? Is the permutation set to some default value?  \n \n* Proposition 1 seems equivalent to stating 'permutation matrices have columns and lines with entropy equal to zero'. This seems rather trivial, and I'm not sure if a proposition is needed here. \n\n* After proposition 1, the authors discuss graph isomorphism and state that PIGAE \"can solve the graph isomorphism problem at least for all graphs it can reconstruct\". Since there is no characterization of 'graphs it can reconstruct', this sentence looks vague.\n\n* Regarding literature coverage, the authors miss some works on normalizing flows for graphs (e.g., [1] and [2])\n\n[1]: Graph Normalizing Flows, NeurIPS 2019 \n\n[2]: MoFlow: An Invertible Flow Model for Generating Molecular Graphs, KDD 2020", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors properly discuss the limitations and the societal impacts.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "c-Nid4qaIXi", "reviewer": "Reviewer_V8HM", "summary": "This paper focuses on unsupervised learning of graph-level representations --- achieved here through a VAE. One of the main hurdles in this problem is to ensure the permutation invariance of the graph: the order in which the nodes appear in the network should not influence the graph embedding, which typically creates issues in minimizing a reconstruction loss between encoded and decoded graph. This paper tackles the problem by proposing a graph autoencoder architecture that is invariant to the ordering of nodes in a graph and that learns a permutation  along side the graph embedding --- thereby simplifying the problem of optimizing the reconstruction loss. The encoder/decoder parts of the algorithms use a message passing scheme to learn messages across each edge (concatenation of node features and edge features) with attention mechanisms. This is however quite an expensive procedure --- complexity of O(n^3).\n\nRelationship to other works: Other works have tried to use approximate graph matching technique using the permutation matrix that maximizes the similarity, with is O(n4) --- expensive. Previous approaches have also already tried to deploy generative models for graphs, but they only achieve permutation equivariance (and not permutation invariance). \n\nPotential Impact: This is an interesting problem, since, as the authors highlight, the main focus of the recent literature has been on supervised learning at the node or graph-level. Unsupervised methods for graphs and generative models have the potential to unlock many possibilities in generating new graph samples, new chemical compounds, etc.\n\nContribution:\nThe pipeline is a concatenation of tricks developed in other settings: VAE + permutation matrix + message passing with attention. The way the authors learn the permutation matrix is new though.", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n- This is an interesting and difficult problem, which hasn't been as much in the limelight of the community, and the authors do contribute to the discussion by proposing a new method --- although the main contribution here seems to be the learning of the permutation matrix.\n\nCons:\n- The method is extremely computationally expensive. That could be fine --- there is not so much done in the literature, so it is important to  start somewhere and the authors were indeed able to generate new molecules on 32 nodes or so.\n- I am more concerned in the potential of the experiments to show for the performance and relative superiority of the model over existing methods:\n      - It is important to sum up what the complexity of the method should be (total cost). It would have been interesting to also show the running time for all the experiments, (a) for comparison with other methods, and (b) because it is an expensive method and that any user trying their luck with it could really benefit from insights into how much time they should expect the computations to run.\n      - The complexity of the method is extremely high: the authors are fitting a learned encoder/decoder with attention (so many many parameters), a permutation method, and they are additionally learning how many nodes to generate. This creates concerns regarding the convergence of the method (this seems to be very highly non convex, so how sure are we that the convergence will be well behaved?) \n     - It would have been interesting to compare this set of methods against more classical alternatives; The classification task seems quite good to evaluate the performance of the method, so it might have been interesting (on top of methods looking at distances between original input graphs) to see what the other GAE+Graphite methods yield, as well as using more traditional statistical methods (ie, ERGMS) for completeness of comparison.\n     - Since the method is so complex, I am not sure that the negative log-likelihood is a fair comparison between all the different methods. Negative LL is typically used in a bayesian setting to compare models with the same complexity --- which is not the case here. What should perhaps be computed instead is either an DIC/AIC/BIC, or  better yet, since this is a non linear model, taking inspiration from the Bayesian literature, and computing  Posterior Predictive ordinates or Conditional Predictive Ordinates...\n\n\nTo sum up, this could be a potential interesting avenue of research, but considering the complexity of the method, I am not sure that the current experiments draw a convincing enough picture to show that the costs are worth the effort.\n    ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None --- except global warming because of potentially intensive computational costs.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2h30"}, "extra_text": {}}, {"review_id": "VJx7mtV3xlj", "reviewer": "Reviewer_394F", "summary": "This paper proposes a new graph variational auto-encoder that is invariant to permutation of node orders. The authors design a permuter model that can predict a permutation of node orders in order to better measure the distance of reconstructed graph and input graph in a permutation-invariant manner. To verify the approach, extensive experiments are conducted on both synthetic and real-world molecular graph datasets.", "questions": "", "limitations": "", "rating": 4, "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": "The paper is well motivated. Endowing the representation/generative model for graph-structured data with permutation-invariant property is interesting and significant. However, the proposed method lacks enough novelty and theoretical soundness. \n\nFirst, the technical contribution of  this work is not clear. There are quite a few existing works having considered permutation-invariant property for graph/set representation learning and proposing effective solutions, e.g. [1-3]. Therefore, the authors' claim \"This is the first to consider permutation invariance in graph-level representation\" is not true. \n\nFurthermore, given this fact, the seemingly novel part of this work lies in the permuter model that is trained to predict a permutation of node orders. However, this method is quite straightforward but lacks enough theoretical justification. With the permuter output P, the orignal ELBO objective would be changed and it is not clear what distribution of P is considered in this work and how its variance of sampling would impact the output. Also, the learning objective cannot guarantee that the learned P is a desired one. Here are two concerns: 1) since the learning for P and learning for decoder are coupled and there are no ground-truth information for P, the learning of two modules would possibly interfered with each other and lead to undesirable solution; 2) the learned P would possibly degenerate to trivial solutions, e.g. P becomes an identity matrix which makes no difference for learning permutation invariance.  \n\nFinally, the comparison with existing models is not sufficient. There are quite a few existing works on graph edit distance and permutation-invariant representation learning and they are not discussed and compared by the authors. Also, the experiment on molecular property prediction is not convincing with no comparison with other GNN-based models. \n\n\n[1] An efficient algorithm for graph edit distance computation, Chen et. al, 2019\n[2] Generative Adversarial Set Transformers, Stelzner et. al, 2020\n[3] Deep Set Prediction Networks,  Zhang et. al, 2020", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See my main review for limitations of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "F7IuZqeDOaY", "reviewer": "Reviewer_d88Y", "summary": "The authors proposed a permutation-invariant VAE for graph-structured data. The proposed model indirectly learns to match the node ordering of the input/output graph. The authors demonstrated the effectiveness of the model on graph reconstruction/generation tasks.\n\nOverall, I found the paper both interesting and well-written. The contributions of this work are to show that The proposed work proposed permutation-invariant graph-level representation learning which can be used for graph generating modeling.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I have a few questions/concerns about the work that I would like clarity on:\n\nWhat is the computational limitation in the number of nodes in the graph? It would be interesting to add computational complexity with varying the number of nodes and comparison between the proposed model and other approaches.\n\nHerein the authors adopt the idea of MPNN and represent graphs by its messages between nodes. How does the proposed approach handle self-loop (i.e., an edge connects a vertex to itself).\n\nOne of the key properties of the proposed work is that the enoder self-attention layers are invariant to permutations of the input node order. As the decoder is also based on permutation equivalant self-attention layers, this canonical order is completely defined and thus correctly calculates the reconstruction loss. This might be related to improve training stability compared to the other approach. It would be helpful if the authors can address this. \n\nIn general, VAEs can suffer from an issue known as latent variable collapse (or KL loss vanishing), where the posterior\ncollapses to the prior, and the model will ignore the latent codes in generative tasks. In the graph-level representation learning task, does the proposed approach have any issue related to latent variable collapse?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Two reviewers recommend rejecting the submission and two recommending accepting the submission. Reviewer 394F, who recommends rejecting the submission, appears to have misunderstood key aspects of the article (i.e., why the permutation matrix P will not become the identity). Therefore, I am not basing my recommendation of that reviewer’s rating. My main concern about this submission is the comprehensiveness of the experimental results. It’s not clear from them whether/when the proposed method will outperform similar methods like GAE and Graphite. In the authors’ response some additional comparisons to GAE have been provided, which seem encouraging, but are not comprehensive.
Decision: Accept (Poster)