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
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-nnvaaiin 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( = Vj. Σ, 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 (eae, 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
coimuutaiion-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 Barabasi- 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": "vB8k7By211W", "reviewer": "Reviewer_bsmb", "summary": "This work proposes a new graph autoencoder approach, which is claimed to have invariant graph embedding. The work claims to solve the permutation matching challenge during the decoding stage.", "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": "Originality:\nThe idea of graph auto-encoder is not new, but I agree that decoding graph structures from an invariant graph representations is challenging. However, the proposed method does not actually solve the problem. Though the work is claimed to learn invariant embedding, the decoding procedure is actually generated from some non-invariant embedding (m_{ij}, i,j>0), which traditional GAE also does. \n\nQuality:\nThe claim seems to mismatch the method proposed. Specifically, the decoding procedure leverages much information that are not in the invariant embedding z (say using m_{ij}, i,j>0), which essentially implies that the so-called embedding z is not the graph embedding, while the entire matrix M (which is not invariant) is the graph embedding. Note that the proposed method also does not match the diagram in figure 1 because in Eq.13, the edges are generated from m_{ij}, i,j>0, i \\noteq j, which is not reflected by figure 1. Therefore, the proposed method does not match the claim and I lean to reject this work. \n\nBecause of this issue, I do not carefully check the experiments.\n\nClarity:\nIt is not hard to follow though the mismatching claims as explained above are kind of confusing. \n\nSignificance:\nBecause of the technical issues of this work, the significance of this work cannot be fairly evaluated. It seems that the authors try to do extensive experiments to show the advantages of their model, which should be appreciated. But the technical problem severely hurts the significance of this work. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The work has adequately addressed the limitations and potential negative impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "fQfsh7GaYmj", "reviewer": "Reviewer_oyaX", "summary": "This paper proposes a variational auto-encoder (VAE) to learn an imputation-invariant representation of a graph, which can be also used to reconstruct graph. In other words, a VAE model is proposed for unsupervised graph-level representation learning and reconstruction. In fact, graph-level representation learning using VAEs is challenging because of the non-unique representations of the graphs (n! possible node orderings) and complicated node matching in the reconstruction loss.  This is addressed in this paper mainly by introducing a permuter model, which learns how to permute the canonical ordering of the decoder according to the given input ordering.\n\nThe main contributions are as follows.\n* Permutation-Invariant encoding of the graph, which can be also used to reconstruct the graph. The main novelty here is the permuter model to match node ordering of input and output graph.\n* The model can also solve the graph isomorphism problem at least for the graphs it can reconstruct. If two graphs are isomorphic, the representation will be identical. But, the representation may be also identical for two non-isomorphic graph (if the decoder cannot perfectly reconstruct both graphs).\n* Various experimental studies for graph reconstruction, graph generation, and evaluation of the learned representations using qualitative analysis, distance calculation, isomorphism test, and some supervised downstream tasks.", "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": "### Pros\n* I appreciate the author’s great effort to include diverse experimental studies.\n* As the authors claim (and to my knowledge), this is the first approach for non-contrastive graph-level representation learning, where the resulting representation vector can be also used for graph reconstruction/generation. But, I will expand on this below.\n* I think the main novelty is in the imputer model and using position embedding to reconstruct the graph nodes from the single representation vector. Using the self-attention on directed messages for encoding/decoding is incrementally novel.\n    * I think using the imputer model to match node orderings of the input and output graph, and using the position embedding to inject information about the position of the nodes for decoding can give a general framework for having permutation-invariant graph representation learning models. This general framework can be like this: \n       * Use any of the existing permutation-invariant graph models for graph encoding (If the model is for node-level encoding, the node representations can be aggregated using simple pooling or more complicated permutation-invariant pooling such as Pooling by Multi-head Attention used in Set Transformer paper).\n       * Use the permuter to find the permutation matrix.\n       * Add position encoding (according to the permutation matrix) to the graph representation to find initial node embeddings for decoder.\n       * Use any existing equivariant decoding model for graph reconstruction.\n\n### Cons\n* In the abstract and introduction, it is written that graph-level unsupervised learning has not received much attention. I think this is not a correct statement to make. I think as the authors explained, any graph generation model or permutation-invariant node-representation learning model (with pooling) can be categorized under graph-level unsupervised learning.  I think the right statement is that using unsupervised learning for single-vector graph-level representation which can be also used for reconstruction/generation has not been explored much. \n    * But, I think one of the main reasons why this has not been investigated much is that it is not necessarily required to have a permutation-invariant single-vector representation to solve the downstream tasks. For example, any of the models which gives equivariant node-level representations may be used to solve the problems explored in this paper. For the problems such as graph classification/regression/similarity which needs single-vector graph representation, the node-level representations can be aggregated using simple pooling or more complicated permutation-invariant pooling such as Pooling by Multi-head Attention used in Set Transformer paper. On the other hand, for graph generation/reconstruction tasks, they can use their node-level encodings.\n    * In recent years, there have been various permutation-invarinat models which tries to give equivariant node representations. In addition to the ones cited in the paper (e.g. [21]), I recommend to discuss the following papers in Section 3 (Related works):\n        * Tony Duan and Juho Lee, Graph Embedding VAE: A Permutation Invariant Model of Graph Structure.\n        * Jenny Liu, et al. Towards Permutation-Invariant Graph Generation\n        * Chenhao Niu, et al. Permutation Invariant Graph Generation via Score-Based Generative Modeling\n\n    * It may be also good to cite these papers\n        * Juho Lee, et al. \"Set transformer: A framework for attention-based permutation-invariant neural networks.\" International Conference on Machine Learning. PMLR, 2019.\n        * Rex Ying, et al. \"Hierarchical graph representation learning with differentiable pooling.\" arXiv preprint arXiv:1806.08804 (2018).\n\n* Sometimes the formulation is not neat.\n    * For example, P is the permutation matrix. But, it has been also used as a transformation on G in Eq (4) and Eq(5), which is not neat.\n    * I am not sure Eq (5) is correct. Since G does not have any ordering ($\\pi$), does it makes sense to apply P? Also, I am not sure using $g_{\\psi}(P|G)$ for taking the expectation is correct. P might be a deterministic function of G.\n\n### Minor Comments\n* I did not understand how an additional node and edge \"type\" is added in the following line:\n    * Line 152:  \"To distinguish the embedding node from other nodes, we add an additional node and edge type to represent this node and edges to and from this node.\"\n\n* Line 152, it is written \"To distinguish the embedding node from other nodes, we add an additional node and edge type to represent this node and edges to and from this node.\"\n    * I did not understand how an additional node and edge \"type\" is added\n\n* In line 168, it is written \"We add to each entry in the message matrix $m_{i, j}$ the concatenated position embeddings [PE(i)||PE(j)].\"\n    * Is $\\mathbf{z}$ also used in $m_{i, j}$?\n\n### Final Thought\nIn overall, although this paper has some limitations (computational complexity and the points explained above), but I think it is an interesting paper for the community which can shed light on future works. In fact, because of the factorial growth of node orderings, it is intractable to learn the complete distribution of the graphs without having significant reduction in the permutations during representation learning.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not think that this work has any potential negative societal impact.\n\nThe authors explained the computational complexity of $O(n^3)$ as one of the limitations.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12 hours"}, "extra_text": {}}, {"review_id": "GjzYY0YskU7", "reviewer": "Reviewer_gusa", "summary": "This paper proposes a graph generative model based on VAE. The model differs from previous methods in that it has a permutation invariant encoder that learns the same representation for isomorphic input graphs. Then, a question is how to measure the reconstruction error. In principle, all n! possible generations (only differ in node permutations) should have equal reconstruction error to the input graph. Previous works usually use a graph matching process which is computationally inefficient. Some other works make the decoder generate a graph with exactly the same node order as the input graph, which makes the encoder permutation variant. This paper cleverly solves this problem by decoupling the encoder into two parts: a permutation invariant encoder that learns order-invariant graph representations, and a permutation sensitive \"permuter\" encoder which learns a permutation matrix to align the decoded graph's node order to the input graph. In this way, it can both learn permutation invariant graph representations as well as avoiding the expensive graph matching process.", "questions": "", "limitations": "", "rating": 8, "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": "Originality: The proposed permuter is novel and reasonable to me. The task of training a permutation-invariant graph encoder through a VAE framework is also desired.\n\nQuality: The proposed model is technically sound. The experiments cover a range of unsupervised graph representation learning tasks.\n\nClarity: The paper is well written in general. However, some parts can be written better. For example, the discussion on solving the graph isomorphism problem can be made more clear. Why \"if the decoder can perfectly reconstruct both graphs, two non-isomorphic graphs must have a different representation z\"? Also, Section 2.3 puts the overall architecture to a later part, while the previous architecture designs are hard to understand without the overall architecture. I suggest re-organizing this section by introducing the overall architecture first.\n\nSignificance: I have some doubt on the significance of the results. If we only want a permutation invariant encoder, we have many ways to achieve this as stated in the related work (e.g., not relying on reconstructing the input graph). If we want a generative model, we also do not need to care about the node ordering as long as the the generative model learns the training graph distribution correctly (e.g., always generates graphs with canonical node ordering). In this sense, this work seems to simply combine a permutation invariant encoder (for graph representation learning) and a permutation dependent \"permuter\"+decoder (for generating the graph with the input node order). It does not really invent a permutation invariant decoder/generator---the generated graph's ordering still has to be dependent on the input graph.\n\n---------After rebuttal-----------\nI thank the authors for the nice discussion. Now I am aware that the training of the proposed model is also invariant to the input node ordering, essentially solving the marginalization (over all node permutations) problem raised in [35]. Therefore, the significance is high. I have raised my score by 2, and I encourage the authors to include our discussed points into the revised paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors state in the related works that GAE-like approaches construct graph representations by concatenating node embeddings, thus is not permutation invariant. But why can't we sum/average the node embeddings like in graph pooling layers?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "Ee2PvGF14eP", "reviewer": "Reviewer_2ehV", "summary": "In this work authors propose a new Graph Autoencoder architecture which is a method graph-level unsupervised learning. Authors aim to learn effective permutation invarient graph representation but also learn to reconstruct a graph from a latent representation. The high representation complexity of graphs due to permutable Adjacency matrices poses a problem for graph level unsupervised learning. Most of the existing works by design are not invarient of input graph node order. This poses a problem in training an effective autoencoder because of the misalignment issues caused while calculating reconstruction loss (due to permutations).\n\nThe proposed method solves this problem by designing a permutation invarient autoencoder architecture which with the help of a *permuter* model learns to map input graph node ordering with the node ordering of the reconstructed graph. This permuter model is trained along with the autoencoder. Authors show the effectiveness of the model for various tasks including graph reconstruction and generation and also evaluate the model's expressive power by using extracted representations for downstream graph-level classification and regression tasks (molecular property prediction, graph classification). ", "questions": "", "limitations": "", "rating": 8, "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": "- To the best of my knowledge, authors propose a new variational autoencoder architecture to solve graph-level representation learning problem. Proposed method predicts the relation between input and output graph ordering in order to make the resulting model permutation invarient. \n- The problem tackled in the paper is important to the graph representation learning community and this work can inspire various future works in this domain. \n- Authors show the effectiveness of the method for several tasks including molecular graph reconstruction and generation, molecular property prediction. \n- The paper is written clearly and is easy to follow. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Questions and Comments:\n- Although experimentation is done on variety of tasks, in my opinion experimentation on graph property prediction (graph classification) tasks is lacking. It would really help if you could present the results on several open graph benchmark datasets. \n- The diagonal elements of input message matrix to the decoder are initiated with the summation of positional embeddings and latent representation *z*. How are the off diagonal messages initialized? ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposed a new variational encoder for unsupervised graph representation learning. The main contribution is the permutation invariance, which is missing in most existing works on graph generative modeling. After the rebuttal, the reviewers found that most of the concerns have been properly addressed, and during the committee discussion we all agree that the paper can be accepted. Despite that the are still challenges in this direction, this work has made a nontrivial contribution. The authors are encouraged to refine the paper according to the reviewers' comments in the final version.
Decision: Accept (Poster)