Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper aims to learn a graph from observations/signals on data entities. They propose a new method based on Learning to Optimise (L2O) whereby they map the node data to a graph. They argue that more complex phenomena like scale-free and small-world properties cannot simply be modelled or incorporated as priors in convex regularizers that are handcrafted. Instead, they propose an unrolling of a well-known iterative primal-dual splitting algorithm designed specifically for graph learning by a neural network, namely a topological difference variational autoencoder termed TopoDiffVAE. The proposed method improves over the results by a large margin compared with the baselines (iterative solvers for graph learning) in generating graphs from synthetic random graphs and real data.
main_review: -- Strengths:
1. The paper is very well-written and easy to understand. I believe the idea is very interesting and novel and will help incorporate very interesting prior knowledge into graph learning which can represent very complex topological priors. The paper was indeed a pleasure to read and the technical details were clearly elucidated. 

2. The L20 method for learning graph structure from signal data proposed by the authors is extremely interesting and quite timely. Especially the idea of taking a well-known iterative optimization algorithm for graph learning and replacing it with an auto-encoder in the right places.

3. Improves over the results by a large margin compared with the baselines in generating graphs from synthetic random graphs and real data.

4. Clearly exhibits the ability to transfer the learnings on random graphs to real world settings


-- Weaknesses:
1. How is the T (number of iterations) in Algorithm 2 ascertained?

2. On Lines 140-142, the authors claim that finding an indicator function where the proximal operator projects onto the space of graphs sharing similar properties is hard to come up with. I would assume that the space of graphs can easily be partitioned after having run them through some kind of a graph kernel (like a WL algorithm maybe?) and then it would just be a matter of defining what a “projection operator” in this graph kernel space might mean? Can this point possibly be expanded upon in the rebuttal?

3. It would be interesting to theoretically analyze the computational complexity of the overhead in terms of the parameters introduced and needed for training in each unrolling step and the resulting scalability issues that arise due to this. I understand this has been mentioned as a future work by the authors, but I think this information would really help get a better understanding of this method.

-- Minor Typos:
Line 148: “abuse use of notation”.

Line 157: w_x repeated.

Line 160: w_x repeated.

Line 210: ...eigenvalues of 1...


limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work studies how to learn the graph topology, the algorithm is developed based on learning to optimize (L2O), which first unrolls an iterative primal-dual splitting algorithm into a neural network, and then the network is stacked with a variantional autoencoder that refines the estimated graph with structure properties. Experiments on both synthetic and real-world data demonstrate the model is more efficient different iterative algorithms.
main_review: The reviewer finds the paper clearly written and easy to follow, but the originality and significance need to be further clarified.

One major concern of the reviewer is that the model is adopting the L2O, and it is not clear whether the effectiveness is due to the  L2O or due to the modeling and regularization proposed in this work. Note that it is known that L2O provides an advantage compared with ADMM and PDS compared in this work. 

While the paper indeed compared with other L2O algorithms including [29] and [3]. But the reviewer finds the performance of these two algorithms surprisingly unsatisfactory in Table 1, with GMSE close to 1, and is significantly worse than conventional learning algorithms including ADMM and PDS. This does not seem right to the reviewer. For example, as is pointed out by the author and can be seen from Figure 2, the performance of GLAD in fact outperforms the proposed L2G if sigma^2 is selected as 1 and improves with a larger sigma value. However, Figure 2 only shows sigma^2 from 1e-6 to 1 which is a very small range. it is likely that the performance will be stable if sigma improves even more and the performance will be stable if sigma>1, which is not shown in figure 2.  Similarly Comparing deep-graph which is designed for binary graph for a weighted synthetic graph is not a fair comparison. Hence, the experiments cannot convince the reviewer the proposed algorithm indeed outperform existing L2O-based algorithms since the parameter selection and the generation of the synthetic data might favor the current scheme.

Similar concerns exist for the experiments in Table 2, as the alternative L2O-based algorithm achieves worth result than the basic primal-dual splitting algorithm (PDS) which is surprising and may be due to an unfavorable selection of parameters.

The experiments on real-datasets seem promising, but given the concerns mentioned above, the reviewer is not very convinced by the comparison.


-------

Post rebuttal: The reviewer appreciates the authors for their efforts in addressing the questions and providing more thorough and convincing numerical results. The major concerns have been addressed and the score has been raised.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors study graph structure learning. The paper's main contribution is to improve the unrolling primal-dual iterative algorithm used to solve equation 4 in the paper. The authors propose a Topological difference variational autoencoder (TopoDiffVAE), which can learn a mapping between two graph domains where one graph domain consists of richer structure information. 
main_review: Originality
I think there is a lot of novelty in the paper. Though the paper is motivated by some recent works on L2O, according to the authors, it is a very early attempt to address the difficult challenge of designing convex functions to represent complex topological priors.
 
Quality
1. The authors show superior performance on a few synthetic data sets. According to table 1 and table 2, the L2G's prediction is very much to the ground truth graph structure than other methods. However, I did not see the authors comparing with baselines on real-world applications. For figure 4, can Graphical lasso/group graphical lasso obtain something similar? 

2. According to figure 3, can we conclude that the difference between unrolling and L2G (with TopoDiffVAE) can be tiny if we use more iterations? I think simply saying L2G converges faster does not make sense, as the computation price is much higher than the unrolling per iteration.

3. I also have a slight concern about the scalability of the methods. Can the technique be applied to modeling a much larger graph (e.g., >=1000 nodes)?

4. What are the tao values (introduced in equation 8) and your beta value (KL divergence term weight) in your experiments?
 



Clarity

a. Line 157, typo, w_x, and w_x.

b. Actually, I am a bit confused about what is w_x and w_y. 
According to line 5 of Algorithm 2, TopoDiffVAE takes r_1^{t} as input. According to lines 177-178, it seems w_x is r_1^{t} after the gradient descent step, which is line 3 in algorithm 2.

c. For w_y, is there a real ground truth w_y?
Or, according to lines 177-178, it seems w_y takes the form of p_1^{t}? Should it be p_1^{t-1}? Or should it be p_1^{t} in line 5 of algorithm 1?

d. Is there only one pair of w_x and w_y used to train the autoencoder in every of the T steps? I am not sure how the proposed approach would work, given a much larger graph.


Significance
Modeling graph structure is with sufficient interest in both the machine learning community and real-life application.
Though I have a few concerns (it could be I missed something), but the idea of this paper seems to be interesting.

Post rebuttal:  I read the authors's response. The authors have answered all my questions, clarified some small typos and addressed my concerns. Score increased.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents a novel method to estimate a graph topology between nodes directly from observations on nodes. In the field of graph signal processing and graphical models, it has been shown that we can estimate the graph topology from data observations at nodes when we can assume that data values at nodes vary smoothly over a graph, in other words when data values observed at node A would be statistically close to the data values observed at node B if node A and B are located in close positions at the entire graph.  

This assumption enables us to formulate the graph topology estimation as an optimization problem over the space of graph candidates. In this formulation, the objective function often is defined as a convex function having a form of "graph-data fidelity term" + "structural regularization term", which is then optimized by many iterative algorithms such as proximal gradient descent.

This paper aims to write these handcrafted convex regularizers by a differentiable module, and perform end-to-end learning in a more expressive and flexible manner. This can relax the strong assumption required for each specific regularization (such as L1 or L2 penalty), and extend the same framework flexibly to a wider range of graphs, scale-free graphs, or small-world graphs, which is usually difficult to explicitly write out the corresponding relevant regularization. 

A very interesting technical point is, the paper's approach is different from just replacing the regularizer with a neural network module, rather enroll the optimization steps of proximal gradient descent as an iterative procedure, and only critical parts are redesigned by neural networks. By doing this, the method can leverage the effective inductive bias developed in the field not to over-reformulate that target problem.

The experimental evaluations on both synthetic and real datasets demonstrate that this idea actually worked nicely, also showing clear superiority over existing approaches such as GLAD and DeepGraph.
main_review: This paper presents a very interesting and principled way to the network topology estimation from data on nodes as an optimization form of eq (1). Usually, we need to design the regularization term, Omega(L), in eq(1) by domain knowledge, but because we need to mathematically solve this optimization as convex optimization, and the options for any possible forms for Omega can be limited. Thus, the idea of enrolling the iterative procedure of optimization, and redesign some critical parts by a flexible neural network sounds quite interesting and promising. Also, it was nice to empirically see that this idea worked in their experimental evaluations.

Overall I liked the idea, and but here are some questions and comments.

- It is quite interesting that in the original enrolled description of proximal-dual splitting at Algorithm 1, only the proximal projection for the primal variable (line 5, Algorithm 1) was replaced by a VAE. The paper explained this motivation as "We do not consider a trainable function to replace the proximal operator in Step 6 of Algorithm 1, as it projects dual variables that do not have a direct connection to graph structures."  
However, if the dual variables correspond to the node degree, it should be also highly relevant to the graph structure. Did you actually try also replacing the dual variable with some NN and saw a poor performance or this is just an assumption?  
Originally both Omega_1 for primal and Omega_2 for dual come from the "handcrafted structural priors" as in line 112. So relaxing both of them sounds more natural at the first glance, given the purpose of the paper explained. The current form is a kind of hybrid mixture of "handcrafted" + "neural", and I'd like to understand this point more in detail. What does it really mean this leaving 2nd regularizer as it is? If we go neural for both of them, the behavior as a proximal gradient descent became chaotic...?

- In Algorithm 1, why line 5 is gamma-free but line 6 is not? I suppose that line 5 should also come with gamma (somewhere around in "max{0,r_1(t)}"), but either way, we replace it a VAE, and doesn't matter...?

- Related to the question above, I'd like to ask the scope of the proposed approach. We see that it worked for synthetic cases of many variations of random graphs such as BA, ER, SBM, and WS including many model forms of real-world graphs. But, the current form should be affected by "the restriction" of leaving the 2nd regularizer as is. How can this design policy affect the applicable scope of the proposed method? Either way, we need to have some assumptions for the relationship between graph topology and observations on nodes, and is there some guideline on what kinds of graphs can be estimated from observations on nodes by this proposed method?

limitations_and_societal_impact: It is appreciated to describe the limitations on the applicable scope of this proposed method.
review_title: null

Meta-review: The paper contains much novelty in the formulation of topological constraints and the method of enrolling the iterative procedure of optimization and demonstrates favorable empirical results.  Some reviewers raised unclear points in the paper, but the authors' feedbacks clarified them in detail.  We judge the paper is acceptable in NeurIPS, but we hope the feedback will be reflected in the final version. 
Decision: Accept (Poster)