Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 

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.

**Comments and questions**

* 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.

* 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.   

* 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?  
 
* 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. 

* 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.

* Regarding literature coverage, the authors miss some works on normalizing flows for graphs (e.g., [1] and [2])

[1]: Graph Normalizing Flows, NeurIPS 2019 

[2]: MoFlow: An Invertible Flow Model for Generating Molecular Graphs, KDD 2020
limitations_and_societal_impact: The authors properly discuss the limitations and the societal impacts.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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).

Relationship 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). 

Potential 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.

Contribution:
The 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.
main_review: Pros:
- 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.

Cons:
- 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.
- I am more concerned in the potential of the experiments to show for the performance and relative superiority of the model over existing methods:
      - 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.
      - 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?) 
     - 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.
     - 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...


To 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.
    
limitations_and_societal_impact: None --- except global warming because of potentially intensive computational costs.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.
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. 

First, 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. 

Furthermore, 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.  

Finally, 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. 


[1] An efficient algorithm for graph edit distance computation, Chen et. al, 2019
[2] Generative Adversarial Set Transformers, Stelzner et. al, 2020
[3] Deep Set Prediction Networks,  Zhang et. al, 2020
limitations_and_societal_impact: See my main review for limitations of this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

Overall, 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.
main_review: I have a few questions/concerns about the work that I would like clarity on:

What 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.

Herein 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).

One 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. 

In general, VAEs can suffer from an issue known as latent variable collapse (or KL loss vanishing), where the posterior
collapses 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?

limitations_and_societal_impact: N/A
review_title: null

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)