Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper combines the self-supervised learning with graph structure learning. A model named SLAPS is proposed to alleviate the "supervision starvation" problem of structure learning methods by denoising features using generated graph. Extensive experiments are conducted to show the effectiveness of the model.
main_review: The major strong points are:

S1. The idea of combining SSL to GSL is interesting. To my knowledge, it might be the first work that combines GSL with self-supervised learning.

S2. A model SLAPS is proposed, and appears to be effective under certain settings.

Nevertheless, there are also several weak points:

W1. Arguable claims: The major argument of supervision starvation is arguably wrong. In fact, the so-called "starved edges" can be optimized by most graph structure learning methods based on metric learning. Specifically, the classifier, i.e. GNN_C in the paper, is a function of \tilde{A}, as the graph learning module models the \tilde{A} using graph learning parameters, it can be optimized.
Moreover, many graph structure learning models apply graph regularization terms. For example, a feature smoothness loss [Chen et al., 2020] can be somehow viewed as a self-supervised term that regularizes the model by homophily assumption, which also provides self-supervision for "starved_edges". Besides, other graph regularization terms introduced in [Wei et al., 2020] can also somehow provide supervision for all the potential edges.

W2. Model design: The defined graph structure learning is solely based on the input feature, which overlooks the adjacency matrix. Actually, the optimal adjacency matrix is mostly a shift [Zhao et al., 2021] from the original adjacency matrix. Neglecting the graph structure and generate it via features only apparently hampers the performance.

W3. Experiments: The experimental setting is problematic. For models requiring an initial graph structure, the adjacency model is completely abandoned and instead replaced by a kNN graph. This setting is quite unfair to models that take both adjacency matrix and node features. For example, on Cora, IDGL should be around 84.5; however, with kNN graph as input, the reported results are around 70.9. 

Besides, the IDGL model actually is able to scale to OGB-Arxiv with a scalable version IDGL-Anch in the NIPS version [Chen et al., 2020] (The authors seem to be unaware of the NIPS version and cites the AAAI workshop version).

W4. Other minor issues: 
- Grale [Halcrow et al., 2020], which also takes the features as input only, should also be compared. It is also interesting to compare Grale with SLAPS since Grale does not consider self-supervision. However, it is understandable since the code for Grale is unavailable.

- References require revision: Some conference papers are cited with their arxiv version. NIPS version of IDGL should be cited.
[Wei et al., 2020] Graph Structure Learning for Robust Graph Neural Networks. In KDD, 2020.
[Chen et al., 2020] Iterative Deep Graph Learning for Graph Neural Networks- Better and Robust Node Embeddings. In NIPS, 2020.
[Zhao et al., 2021] Data Augmentation for Graph Neural Networks. In AAAI, 2021.
[Halcrow et al., 2020] Grale: Designing networks for graph learning. In KDD, 2020.

limitations_and_societal_impact: Limitations are discussed in the supplementary materials.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors propose SLAPS, a methodology for deriving latent k-NN graphs for usage as edges of a GNN. They argue theoretically and empirically that it is important to combine self-supervised learning with graph structure learning, to avoid the prevalent edge starvation problem. They validate an approach consisting of a denoising self-supervised objective and various graph derivation strategies against relevant latent graph inference benchmarks, achieving impressive results.
main_review: I found the paper well-written, easy to follow and full of useful intuition.

The authors re-use a familiar construct for latent graph inference (the k-NN graph), and argue well for addition of a self-supervised loss when inferring it. This combination is novel in principle, and the obtained results appear significant. 

The impact for GNN practitioners is clear. In many cases the GNN datasets will contain suboptimal graphs---or complete lack thereof---and different stages of processing may require a different graph. Besides the obvious applicability for relational reasoning, there is potential for spillover into set-structured tasks, or even sequence-style tasks, making the work relevant to a wider community. 

Further, I really appreciate that the authors hadn't merely 'stitched' a self-supervised loss to the architecture without any justification. This choice was substantiated with clear theoretical arguments (edge starvation) as well as a workable hypothesis for denoising to be used. The qualitative analysis (e.g. on homophily properties) is also a nice touch. I recommend acceptance.

I have some suggestions for follow-up experiments that may strengthen the paper further:
- The theoretical expected ratio of starved edges is currently provided only for Erdős-Rényi graphs, which are purely uniformly distributed and may not be very naturalistic. I recommend the authors also expand their analysis to Barabási-Albert graphs, which might be more appropriate for many complex naturalistic phenomena.
- Could the authors also include a fully-connected graph baseline (i.e. where all nodes are mutually connected), using a model such as GAT or MPNN? I find such baselines to always be insightful about the impact of graph inference.
- The investigated latent graph inference baselines could be expanded to also include the Differentiable Graph Module (Kazi et al.), which attacks the "added supervision" problem via reinforcement learning-style objectives.

==== Post-rebuttal update: I thank the authors for responding to my comments carefully and faithfully. The theoretical result on Barabási-Albert graphs will surely improve the paper. I have upgraded my score as a result. Well done!
limitations_and_societal_impact: No concerns.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper first identifies a starved edge problem in latent graph learning. That is, nodes that are far from labeled nodes may receive insufficient supervision signal during learning. To address this issue, the paper then proposes to leverage a self-supervision signal, which comes from denoising the node features of the graph. Through taking both the noisy node features and the currently learned adjacency matrix as input, the feature denoising process acts as a regularizer to the learning of the adjacency matrix. Experiments on benchmark tasks show that the proposed strategy outperforms several comparison baseline models with or without adjacency matrices given. 

The identification of the starved edge problem in latent graph learning is interesting. The proposed solution that introduces inductive bias in adjacency matrix learning through leveraging node features makes sense to me. Nevertheless, I found that the impact of the starved edge problem to a graph model’s predictive performance could be better justified with stronger evidence and the empirical studies in its current form could be further improved.

main_review: The paper is well written and easy to follow. The related work section is informative and concise; the ablation studies provided in Sections 5.2-5.4 are beneficial.  

Graph learning in data where graph structure is not readily available is an interesting and important research problem. Also, leveraging node features to regularize the learning of the adjacency matrix seems novel and makes sense to me. Nevertheless, I have the following two main concerns regarding the paper.

1.  Stronger comparison baselines may be beneficial. The proposed model has a larger number of parameters than that of other comparison baseline models. In this sense, I am not sure where is the predictive improvement really coming from. That is, how much the accuracy improvement benefits from extra model freedoms/parameters? For example, the current baseline MLP is a very simple approach. To make the comparison more convincing, a stronger baseline may be useful, such as a Transformer Encoder (with attention) as a non-graph structure baseline for comparison. 

2.  I did not see a direct connection between the predictive improvement and addressing the supervision starvation problem (i.e., starved edges). It is useful to identify and show the existence of the starved edges problem in common graph datasets. But the importance of this issue, in terms of its impact on the predictive performance of the trained model, is not clear to me. I think it would be useful to show the importance of the starved edges directly since this is one of the main contribution claims of the paper. This is particularly relevant since as stated in Lines 297-298 that adding AdaEdge does not help. The paper suggests that such non-improvement may due to the proposed method has already learned a good graph structure. On the other hand, I think this might also indicate that some graph structures are just not important to the predictive targets at all. 

Minor comments:

1.  Lines 188-189: for real-world graphs, how the percentage of starved edges was calculated is not clear to me.
2.  Line 390: the statement of “learning the graph structure of the nodes simultaneously based on self-supervision” is a bit ambiguous to me. The self-supervision here is more like an extra task and just act as a model regularizer. It would be useful to make the statement more precise.

==== post-rebuttal update ====

I thank the authors for their response to my reviews; really appreciate that!
I do not have any major concerns regarding the paper, and hope some of the experiments/analyses from the rebuttal can be added to the main text of the paper in revision.


limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies graph structure learning. Given a dataset with latent but unobserved graph structure, the goal is to infer the graph structure and help downstream tasks. The authors specifically design a feature reconstruction task as self-supervision to improve the structure learning.
main_review: Overall I think the direction of using self-supervised learning for learning latent graph structure is very promising, especially for the cases that the authors point out, when the training signal is sparse and cannot propagate to many edges via a local GNN. The feature reconstruction is obviously a good starting point and reasonable choice.

For the experiments, I have several questions and concerns:

(1) For experiment 5.3, the authors say they add noisy graph as input. But I think the assumption of structure learning is we don't observe any graph. Is this experiment aimed at testing how well the SLAPS can correct the perturbed edges? If so, I think it would be more fair to compare with the other graph structure learning baselines. 

(2) Experiment 5.4.1 is very interesting and shows that SLAPS could recover the ground-truth graph structure. However the experiment is conducted in that edges is randomly removed or added. A more realistic setting is that we have a set of nodes without any link to it, which is more close to your analysis about (starved edges). It would be more convincing if the authors could conduct such experiments (for example, randomly select K nodes and delete all the internal edges, or first run a cluster algorithm and pick one cluster to delete, or if you have timestamps, just pick the node after a particular timestamp). Also, it would be intersting to see some visualization results.

(3) For experiment, I think it would be better to also include "Graph Structure Learning for Robust Graph Neural Networks" as a baseline (their regularization could also be regarded as a self-supervised task). Also, it would be better to add a GCN results with groundtruth graph structure for comparison (as upper bound)

(4) The authors mainly show the results for node classification, where similar nodes will have tendency to be connected. What about other dataset, such as molecules? Is the feature reconstruction also beneficial to reconstruct a molecule structure? It would be interesting to also test it.

(5) The notation is a little bit confusing to me in Table 1 (I previously thought self-training is L_DAE). It would be better to also include an ablation that remove the feature reconstruction (L_DAE) in the main table to support your hypothesis. 

Overall, I think the paper is well written and a good starting point in this research direction.
limitations_and_societal_impact: Would be better to add more experiments to support the effectiveness of feature reconstruction task as I described above.
review_title: null

Meta-review: This paper proposed an approach for simultaneously inferring graph structure and GNN parameters. In particular, the authors pointed out the problem of edge starvation when learning on graphs with limited number of labels and proposed a self-supervised approach to alleviate such an approach. Experimental results prove the effectiveness of the proposed approach on existing latent graph inference benchmarks.

Overall, the reviewers like the simplicity of the proposed approach with good intuitions by pointing out the edge starvation problem. The authors addressed most of the concerns raised by the reviewers. 
Decision: Accept (Poster)