Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes a differentiable graph-generator that builds the graph topology on the fly.

strength_and_weaknesses: Strength:
- The paper is clearly written.
- The approach is technically sound.

Weakness:
- The idea of learning the graph structure for GNN is not novel. I have read several papers with similar ideas, for example, http://proceedings.mlr.press/v97/franceschi19a/franceschi19a.pdf
- The proposed method is only evaluated with basic GNN models - the reported number is far below the state-of-the-art performance, on the classic benchmark datasets being used.
- The approach is clearly not going to scale to large graphs. And I did not find discussions regarding the scalability of the method.
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written. The font of the submission is not standard, though. 
summary_of_the_review: Overall, this paper proposes yet another method for applying Graph Neural Networks to datasets without explicitly relational structure through inferring latent graphs. While the proposed method is technically sound, it lacks technical novelty. Also, the empirical performance is weak, and the method is not scalable.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this paper, a joint topology and graph representation learning framework is proposed to tackle the adjacency matrix missing scenarios. The method could also be applied to the given graph topology to improve the emirical performance. The distinguishing point is the incorporation of adapative number of neighbors k which could be differentiably learnt via a Gumbel-softmax trick. However, the paper lacks more detailed discussion and experiment with recent graph structure learning models.
strength_and_weaknesses: Strengths:

1. The paper aims to optimize a graph model that jointly learns the topology and graph representation in an end-to-end differentiable manner. The cases where adjacency matrix is not provided are supported, as well as refine the given adjacency to improve the topology for better performance

2. A framework is proposed that can plugs in a wide range of existing GNN methods

3. An insight of this work is that it considers the variable number of neighbors in the graph topology learning. The differentiablity is implemented by a combination of degree estimator and top-k neighbor selector.


Weaknesses:

1. An important line of related works are missing. The paper claims that it is the first to consider differentiable end-to-end learning of graph topology, and however, it is wrong. Differentiable graph structure learning has been explored by quite a few existing studies, e.g. [1-5]. In particular, [1] uses bi-level optimization for learning structures/representations as the outer/inner loop, [2, 3] harnesses variational inference for joint learning topology and node representations, [4] considers iterative learning of the two things and [5] proposes a scalable model that learns optimal topology with Gumbel trick in each representation layer. A detailed comparison with these works are needed to illuminate the differences and novelty.

2. The experiment only compares with the methods which drops edges from the orignal graph, instead of the more related and strong competitors that learn the graph structure, especially the works that involve graph topology and representation joint learning, e.g. the above-mentioned models.

3. The proposed method seems to have O(N^2) complexity w.r.t. node numbers and not scalable enough for large datasets. The experiments are only conducted on small datasets, instead of the larger ones, e.g., from OGB. 

4. The paper claims that the framework fits with any “graph convolutional networks”, are there any reasons that other spatial GNNs based on message passing do not fit here?

5. The paper uses Gumbel-softmax for edge probabilty estimation. However, the pairwise edge probability is estimated independently of each other. Under this assumption, the dependencies among edges are not taken into account. Are there some jusfitication of this assumption?

[1] Learning Discrete Structures for Graph Neural Networks, ICML19

[2] Variational Inference for Graph Convolutional Networks in the Absence of Graph Data and Adversarial Settings, NeurIPS20

[3] Variational Inference for Training Graph Neural Networks in Low-Data Regime through Joint Structure-Label Estimation, KDD22

[4] Iterative Deep Graph Learning for Graph Neural Networks - Better and Robust Node Embeddings, NeurIPS21

[5] NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification, NeurIPS22
clarity,_quality,_novelty_and_reproducibility: Clarity:
The paper in general is well organized and easy to follow.

Quality:
The paper is of fair quality in general.

Novelty:
The focused technical aspect of this paper is not novel. There are a few existing works that have already studied joint and differentiable learning of graph topology and node representations (see weakness part for details). Also the proposed method is a combination of techniques that have already been explored by a few existing works (see weakness part for details). In contrast, the differentialable learning of adaptive number of neighbors is somewhat novel.
summary_of_the_review: This paper studies an important problem. However, the proposed method lacks enough novelty, especially quite a few proposed components have already been explored by prior art in the same direction. Also, an important line of related works are missing without any comparison, which makes the technical contributions of this work not convincing.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper introduces a method for learning a graph topology that can be integrated in any GNN framework. The proposed probabilistic method is built on a differentiable graph operator that is able to decide the size of the neighbourhood of each node (i.e., degree of each node), as well as the corresponding edges. Experimental results on i) different GNN architectures and ii) a wide set of datasets are provided. 
strength_and_weaknesses: Strength: The topic is of interest to the (graph) machine learning community. Updating/learning/rewiring graphs for a final end-task is an open problem with some approaches already proposed. This work builds on those approaches and improves some of those aspects. The paper is very clearly written and easy to follow. 

Weaknesses:  I don't see a strong weaknesses of the paper expect from the fact that is it incremental in comparison to the existing literature. 
clarity,_quality,_novelty_and_reproducibility: The paper is clear, and of relatively high quality. The approach is relatively novel, and adequate details are provided to reproduce the results. I believe that once the authors release the code the work can be easily accessible. 
summary_of_the_review: Overall, this is a well-written paper addressing an interesting topic. Although there is quite a lot of work in learning the connectivity matrix in a GNN framework, this paper brings one additional solution to the problem. Thus, the problem itself is not novel, but the proposed solution is valid. 

Some additional comments that could hopefully help the authors are the following:

1) In Eq. (8), the dimensionality of $z_i$ and $h_i$ does not seem to be the same. The former is $d$ and the later is 1. Could you please explain and clarify?
2) Can you discuss on the type of edges that you learn? If I understand correctly the learned graph is directed. Is it possible to extend it to an undirected graph, which might be more suitable for some applications?
3) In the training details, the authors mention that "to speed up training, we add an intermediate loss...". Can you please elaborate on that? It seems that the loss promotes a specific class of graphs that consists of community structures. Is that correct? Please clarify. 
4) Related to the previous comment, it would be useful to understand more the properties of the learned graph. Can the method be extended to unsupervised settings?

Some examples typos that should be fixed: 
- p.7: 'fixe k': remove e 
- p.12: 'signle': single
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes an end-to-end differentiable graph generator that builds the graph topology simultaneously as learning for a downstream task. The proposed idea extends the applicability of GNNs to cases where a graph topology is not readily available. The experimental results show that the proposed model improves the performance of node classification ad trajectory prediction tasks.
strength_and_weaknesses: 
**Strengths**

The proposed method helps create a similarity graph with a learnable node degree for each node in the graph.

**Weaknesses**

The proposed method does not discuss or compare with a large body of related work for learning a graph topology on the fly (e.g., [1, 2, and 3]). Without comparing with the existing works, the contribution of the proposed method is not measurable.

The time complexity of the proposed approach is not discussed. For the edge ranking step, the similarity of each pair of nodes should be computed and later used in the Gumbel-Softmax. This means O(n**2) time complexity with n as the number of nodes in the graph. 

The datasets used in this paper are relatively small compared to the current benchmarks (e.g., OGB graphs [4])

[1] Learning discrete structures for graph neural networks, ICML 2019.

[2] Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings, NeurIPS 2020.

[3] SLAPS: Self-supervision improves structure learning for graph neural networks, NeurIPS 2021.

[4] Open graph benchmark: Datasets for machine learning on graphs, NeurIPS 2020.


clarity,_quality,_novelty_and_reproducibility: The paper is well-written. 

The code and details on training the model is not provided.

summary_of_the_review: **Questions**

Table 2: It is not clear to me what is used as input to DGG for this experiment. Is the original graph structure for Cora, Citeseer, ... used in this experiment? Also, as mentioned earlier, many baselines are missing here.


The intermediate loss: Why adding the intermediate loss can help? Why doesn't the downstream task loss do the same thing as encouraging nodes in the same class to be connected and nodes in a different class to be disconnected?
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a differentiable graph-generator that builds the graph topology on the fly. To this end, a joint topology and graph representation learning framework is proposed to tackle the adjacency matrix missing scenarios. The method could also be applied to the given graph topology to improve the empirical performance. The distinguishing point is the incorporation of adaptive number of neighbors k which could be differentiably learnt via a Gumbel-softmax trick. Experimental results on several GNN architectures and multiple datasets are provided and show that the proposed model improves the performance of node classification ad trajectory prediction tasks. Reviewers raised several concerns including limited novelty, issues of scalability to larger graphs, lacking more detailed discussion and experiment with recent graph structure learning models, and consideration of dependencies among edges. The authors’ responses addressed only some of these concerns. Overall, there still seems to be a lack of enough enthusiasm among the reviewers after the author responses.
justification_for_why_not_higher_score: Reviewers raised several concerns including limited novelty, issues of scalability to larger graphs, lacking more detailed discussion and experiment with recent graph structure learning models, and consideration of dependencies among edges. The authors’ responses addressed only some of these concerns. Overall, there still seems to be a lack of enough enthusiasm among the reviewers after the author responses.
Decision: Reject