Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose a graph autoencoder architecture using what they term as Neighborhood Wasserstein Reconstruction (NWR). They show experimentally that this reconstruction loss improves the embedding performance in structure-oriented graph mining tasks.

main_review: Strengths: Especially clear descriptive figures and writing. Experimental benefits on both toy and real world datasets and additional exploration as to why these improvements might be occurring.

Well motivated and well placed in the literature, the empirical comparisons are extensive.

The idea of NWR is seems novel and useful to me.

Weaknesses:

The notation is a bit cumbersome with many subscripts and superscripts that are difficult to keep track of.

Some of the choices in matching neighborhoods seem a bit arbitrary and not sufficiently justified (see questions below), although this is somewhat understandable as there are large number of tricks used in this paper.

Limited theoretical contribution, with some small inconsistencies.

Questions:
How much does the neighborhood Wasserstein reconstruction improve over a naive reconstruction of something like the mean of the neighborhood? Is it the Wasserstein distribution matching that is important, or just that it helps to reconstruct something about the neighborhood of each node. 

Theorem 3.1 seems a bit out of place given that you don't actually want a universally approximating network here, if you had a large enough network then the NWR loss would have no benefit right, as the FNN \psi_p^(i) could always approximate the neighborhood distribution from any initial \mu, \sigma input?

Do you use W_2^2 (as in eq. 6, Figure 3) or W_2 ( as in eq. 1)? Not that it matters much but would be good to clarify.

Small notes:
It would be slightly better to prove approximation in the W_2 metric rather than W_1 in Theorem 3.1, as this is what is used in the empirical results and the rest of the paper. This seems trivially true to me.

Theorem 3.1 You are missing a closing paren in W_1(P, u(G))
summary_of_the_review: This paper was an interesting read and provided insightful and clear justifications for the results. There remain some questions as to the theory and some particular loss choices made, but these are relatively minor points.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of graph representation learning with graph autoencoder. The paper argues that most GNNs are designed for semi-supervised learning and cannot learn task-agnostic embedding. As a result, the paper proposes a graph autoencoder architecture that trains the GNN in an unsupervised manner. The key idea is to develop a decoder to reconstruct both the node degree and feature distribution. Experimental results show that the results outperform existing autoencoder baselines in several datasets.
main_review: 
**Writing**
1. While most of the paper is well written, it can be still improved. For instance, the paper mentions that existing approaches are either structure-oriented or proximity-oriented approaches and they cannot distinguish certain node pairs. However, the concept of the structure or proximity information of a graph is not defined and introduced well at all in the introduction, making the paper hard to follow at the very beginning. 
2. Figure 1 tries to illustrate the disadvantages of existing approaches. It is unclear why there are two nodes with the same numbers (such as 5 and 4). Are they the node labels or IDs in the graph?

**Method**

  The time complexity of the proposed method looks very high. The paper briefly describes the time complexity of Eq 8. It would be good to know the overall time complexity of the proposed algorithm.


**Experiments**

1. The idea of training a graph encoder in supervised manner links to the early graph embedding and the recent self-supervised learning (SSL) for graph data. It is good to see that both random walk based approaches, as well as SSL based approaches, are compared in the experiments. But it is unclear why GraphCL and MVGRL are only compared on the real-life datasets but are missing in the synthetic datasets in Table 1.
2. The proposed algorithm is significantly worse than the SSL based approaches such as DGL and MVGRL on Cora, Citeseer, and Pubmed. These datasets are identified as *Proximity*-oriented datasets in Table 2. More detailed explanation would be expected. 
3. All datasets are relatively smaller in this paper.  It is unclear the scalability of the proposed method.
summary_of_the_review: The paper describes a new graph autoencoder approach that could encoder more information into the latent space. However, the scalability of the proposed method is questionable. Also, the proposed method did not outperform baselines on three datasets.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a novel approach to graph representation learning. In particular, a graph auto-encoder is proposed that aims to better capture the topological structure by utilising a neighbourhood reconstruction and a degree reconstruction objective. An optimal-transport based objective is proposed for the neighbourhood reconstruction that optimises the 2-Wasserstein distance between the decoded distribution and an empirical estimate of the neighbourhood distribution. An extensive experimental analysis is performed, highlighting the benefits of the proposed approach on a range of synthetic datasets to capture structure information. The experimental results also highlight its robustness across 9 different real-world graph datasets (ranging from proximity-oriented to structure-oriented datasets).
main_review: Strengths: 
1. The method is intuitive and the way that the neighbourhood information is reconstructed appears novel.
2. The empirical evaluation is extensive and highlights the models benefit across a range of different datasets when compared to several categories of baseline approaches, covering both structure-based, graph auto-encoder based and contrastive learning approaches.
3. The paper is mostly well written.

Concerns:
1. How does an increase in k affect the model?
2. Delta in the expression for P_v^(0) does not seem to be defined, which impacts the clarity of how the distribution is computed.
3. A loss is introduced to predict the degree based on the node feature, however, it is not explicitly used in the neighbourhood reconstruction process. Why not sample q according to or proportional to the degree? How is the neighbour-sampling handled when a node has less than q neighbours? 

Minor: 
- For improved clarity, I suggest to include in Table 2, the heading that indicates which datasets are structure-oriented or proximity-oriented, etc. (as is done in Table 4 in the appendix). 
- The second sentence in Section 3.2 seems to be incomplete. 
- In the second sentence of Section 4.3, you mention that DGI is the best performing model. Should it be MVGRL?
summary_of_the_review: Overall, the paper is well written and presents an interesting and efficient approach to graph representation learning. I lean towards accepting the paper if the authors address the above-mentioned concerns and questions.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new loss in graph auto-encoder (GAE) model for unsupervised learning, composing of degree prediction and Wasserstein distance, which helps to identify structure information better vs the original loss. Extensive experiments demonstrate the advantages of the proposed loss.
main_review: The appreciated side of this paper is the correctness of the method, detailed illustration of implementation and the thorough experiment comparison. The proposal to adopt degree decoder, Wasserstein distance and its approximation into GAE looks reasonable to me, and the empirical examination verifies this.

The disadvantage is on the novelty side, considering that i) enforcing awareness of the context of nodes to highlight structure information is not new in the graph field (https://arxiv.org/abs/1905.12265, etc); ii) the employment of the OT theory into networks existed in even a more fancy way (https://arxiv.org/pdf/2003.03892.pdf, https://openreview.net/pdf?id=ATUh28lnSuW, etc). The benefits of individual components were established and therefore directly combining them together further boosting is not surprising.

I would recommend digging further into either theory or ablations to strengthen this interesting work, to characterize the real "structure information" captured by the proposed method compared with literature, probably following the thought as: 1) defining structure information (SI) and its quantitative assessment metric; 2) showing the proposed method can capture certain SI but the existing methods cant; 3) showing OT can capture better.
summary_of_the_review: I am satisfied with the solidness of the paper, including the methods part and experiments, while I feel it is limited in novelty.
review_title: null

Meta-review: The paper proposes a novel approach to graph representation learning. In particular, a graph auto-encoder is proposed that aims to better capture the topological structure by utilising a neighbourhood reconstruction and a degree reconstruction objective. An optimal-transport based objective is proposed for the neighbourhood reconstruction that optimises the 2-Wasserstein distance between the decoded distribution and an empirical estimate of the neighbourhood distribution. An extensive experimental analysis is performed, highlighting the benefits of the proposed approach on a range of synthetic datasets to capture structure information. The experimental results also highlight its robustness across 9 different real-world graph datasets (ranging from proximity-oriented to structure-oriented datasets).

Strengths:
- The problem studied is well motivated and the method proposed is well placed in the literature.
- The method is intuitive and the way that the neighbourhood information is reconstructed appears novel.
- The empirical comparisons are extensive.


Weaknesses: 
- Some of the choices in matching neighborhoods seem a bit arbitrary and not sufficiently justified. 
- The scalability of the proposed method is questionable. The method has a high complexity of O(Nd^3) (where N is the number of nodes and d is the average node degree). The authors address this problem by resorting to the neighborhood sampling method (without citing the prior art), which is only very briefly discussed in the paper. 
- The reviewers have also expressed concerns about the fixed sample size q. The question of how the neighbour-sampling is handled when a node has less than q neighbours remains unanswered.
Decision: Accept (Poster)