Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a novel solution to infer the graph structure. It starts with the unrolling algorithm for graph structure inference problem, and then adopt the proximal gradient iterative solutions. The expressiveness is augmented by parameterized with deep neural network, called Graph Deconvolution Network (GDN).

main_review: Strengths:
The problem on graph structure inference is not novel, yet the authors provided an interesting aspect by formulating it with unrolling algorithm, which is then solved using truncated proximal projection. Some important tricks are also introduced to enhance the performance of GDN.
Weaknesses:
(1) Some claims and descriptions are confusing, as listed below:
1. In abstract, ... assuming the knowledge of said graphs may be untenable in practice .... This claim is too bold. There are quite a lot of well-explored tasks have reasonable good graph structure, like molecular graph[1].
2. In Sec 4.1, why PG iterations (Eq 4) is sufficient to solve Eq 3? Though it can be implied from the equation, where $k$ denotes the iterations; the authors may explicitly add intuitions here, especially for audience not familiar with the optimization methods.
3. In Sec 4.2, why can authors drop all higher-order terms for simplicity? This may benefit for computation, yet how about the approximation error? The community has acknowledged the Taylor expansion with higher-order truncation, but I'm not sure how this would affect the Eq 5. Maybe some previous work (if exists) or some textual explanations can be added here.

(2) The role of prior knowledge in GDN. The initial selection of A[0] seems to have an important effect on the performance. In Sec 4.2, it says ... we can select to incorporate prior information ..., and Sec 4.3 lists some special cases. However, there does not seem to be an universal optimal solution. I would expect the authors to have an ablation to test what's the effect of different priors on A[0], and cases with K=0.
(3) About empirical results. I'm not familiar with the literature, so cannot judge if there are key baselines missing or if the empirical performance gain is substantial. But according to this paper:
1. In Sec 1, related work part, the authors also introduce more recent works, like [2,3] and more, but they are not included in Sec 5. Even though they have some drawbacks (lack of robustness, scalability issue, etc) as stated in the paper, including them can better support the effectiveness of GDN. Any idea why they are excluded?
2. In Sec 5, there's only one real dataset. Is this sufficient to prove the effectiveness of GDN in the general setting?

-----
[1] Wu, Zhenqin, et al. "MoleculeNet: a benchmark for molecular machine learning." Chemical science 9.2 (2018): 513-530.
[2] Xiaowen Dong, Dorina Thanou, Michael Rabbat, and Pascal Frossard. Learning graphs from data: A signal representation perspective. IEEE Signal Process. Mag., 36(3):44–63, 2019.
[3] Bastien Pasdeloup, Vincent Gripon, Gregoire Mercier, Dominique Pastor, and Michael G. Rabbat. Characterization and inference of graph diffusion processes from observations of stationary signals. IEEE Trans. Signal Inf. Process. Netw., 4(3):481–496, 2018.

summary_of_the_review: The proposed algorithm in this paper sounds technically interesting. However, I have some concerns on some of the descriptions, model designs, and empirical results. Thus, for the current version, I would rate it as borderline paper, and I will consider raising the score if the main concerns are properly solved during the discussion period.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes an approach to estimate a latent graph $A_L$ given an observed graph $A_O$ (e.g., the covariance matrix of signals generated through a graph diffusion process). The authors posit a polynomial model and unroll proximal gradient iterations to estimate a variant of the model. The authors conduct experiments on synthetic datasets with supervised $(A_O, A_L)$ pairs as well as a neuroimaging dataset, where $A_O$ denotes the functional connectivity graph and $A_L$ denotes the structural connectivity graph. The proposed approach performs better than several baseline approaches.
main_review: **Strengths:**

This work formulates the graph structure learning problem as an inverse problem. Such a formulation is interesting and it differs from many of the latest formulations based on deep learning.

**Weaknesses:**

However, there are multiple concerns on the modeling, the setting, and the evaluation.

**Model and misnomer of naming.** The authors posit a polynomial model $x = H(A_L , h) w$, where $H$ is a polynomial of $A_L$, and name the overall approach a "graph deconvolution network" (GDN). Such a naming allures a reader to draw direct analogy with graph convolutional networks (GCN). However, there is a critical difference between GCN and GDN, which brings more confusion than appreciation. If we consider $x = H(A_L , h) w$ a graph convolution, then a key of GCN is the learnable transformation on each component of the input signal $w$, lacking in GDN. A graph convolution, either interpreted as a filter or as a neighborhood aggregator, has a limited capability in generating output signals, without such learnable transformations. This is not to say that the authors' polynomial model is wrong; the model is just limited and calling the approach GDN causes big confusion.

**Setting.** It is a bit unclear if the assumption of known $(A_O, A_L)$ pairs is reasonable. This assumption, of course, allows supervised learning and it also appears to be supported by the neuroimaging application the authors demonstrate. On the other hand, the point of the application may need more articulation to be convincing. The sole purpose appears to learn brain structural connectivity, but what is the point of learning it? The authors have not given clues on the use of the structure or insights obtained therein. Moreover, is the structural connectivity manually annotated or algorithmically annotated? If the latter, why machine learning?

Going beyond, the paper may benefit from suggesting more applications of inferring $A_L$ from $A_O$, where supervised data are available. The reviewer is a bit skeptical that the supervised setting has very limited use.

**Evaluation.** There is a straightforward baseline and the authors are encouraged to compare with it, too. One may use the training data to estimate the coefficients $h$ of the polynomial $H(A,h)$. Once these coefficients are obtained, one can estimate $A_L$ for any given $A_O$. The first step is simply a least squares problem and the second step can be solved by using proximal gradient. Both are easy to solve. Furthermore, one may let $h$ have $N$ entries and use a regularization to estimate them, leading to again a proximal gradient solution.

**Minor comments:**

- Section 4.2. The loss is an important piece of information. Currently the main text is a bit cryptic and the details are deferred to the appendix. The authors should at least describe the losses (if not giving formulas) in the main text.

- If the authors draw connections between an RNN and the GDN, then the initial $A[0]$ serves a similar role to the initial input to RNN. An additional approach is to treat it a learnable parameter.

---

**After rebuttal**

This paper has technical merits and the revisions done during the rebuttal period solidify the work. In many aspects, the authors successfully convince me of the value of the setting and the applications, although the naming of the model as "graph deconvolution network" will likely confuse researchers and practitioners in the field of graph neural networks. I encourage the authors to complete the remaining experimental evaluations. The added Facebook experiment provides a good application and I feel it may be even more intuitive than the brain structure application the authors originally focus on, depending on the background of the readers.

summary_of_the_review: This work formulates the graph structure learning problem as an inverse problem. Such a formulation is interesting. However, there are multiple concerns on the modeling, the setting, and the evaluation, which leave ample room for improvement before the paper can be published.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors tries to recover the underlying graph structures from observed symmetric adjacency matrix. The key assumption of the paper is that the observed adjacency matrix can be represented as a polynomial of the adjacency matrix of the true underlying graph, which is reasonable. The experiments show that the proposed model can recover graph structures on provided dataset.
main_review: While the overall idea and the algorithm part of the paper seems to be ok. There is a  fundamental question that need to be addressed. In (1), there is no constraints on alphas and As, in this case, is the solution A in (1) unique? If it is unique, then we can conclude that the problem the author are trying to attack is identifiable. 

Or if there are multiple A that satisfies (1) with a given A_O, is the skeleton of A unique? i.e. regardless of the weight, just consider the unweighted version of A. If this uniqueness can be established, then the identifiable can also be established.


summary_of_the_review: One fundamental question about the paper is not clearly stated.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose the graph deconvolutional network (GDN), which is a novel approach to graph structure recovery from noisy observed graph structures. It is based on an assumption that the observed adjacency matrix is polynomial in the true graph adjacency, and uses a proximal gradient computation to iteratively optimise for this structure. Experiments on both synthetic and brain imaging graph recovery tasks indicate the outperformance of the proposed method against several baselines.
main_review: I found the paper to be well-written and easy to follow. The central ideas of the paper made sense to me and the experiments appear to validate the utility of the idea, both synthetically and in datasets with real world relevance.

Unfortunately the paper is outside my main area of expertise and therefore I am unable to make strong comments on the quality of the baseline approaches used. I will defer to the other reviewers for advice on this. But for now I'd give authors the benefit of the doubt and suggest (weak) acceptance. My understanding is that the proposed layer does not operate over node features, and as such it is not appropriate to compare it to methods like DGCNN (Wang et al., 2018), DGM (Kazi et al., 2020), NRI (Kipf, Fetaya et al., ICML'18) or PGN (Veličković et al., NeurIPS'20). Most of the above are already correctly cited in the paper.

The main concern I would have with the method as-is is that it seems to rely on an "observed" adjacency matrix ${\bf A}_O$. In many cases of interest, ${\bf A}_O$ would either not be given, or would be a result of a very crude heuristic. Would the authors' method still work if ${\bf A}_O$ were not explicitly given? If not, how could we modify the proposal to (approximately) support this? I saw no obvious discussion of this in the paper, but it is possible that I have missed something.
summary_of_the_review: I recommend weak acceptance because I feel like this paper presents an interesting, novel and well-grounded idea, with a decent level of evidence towards empirically ascertaining its contributions. However my confidence score is low as I lack expertise in this particular domain -- it is very much possible that I am unaware of all of the relevant baselines.
review_title: null

Meta-review: The paper addresses the problem of recovering a graph structure from empirical observations. The proposed approach consists of formulating the problem as an inverse problem, and then unrolling a proximal gradient descent algorithm to generate a solution. 

Whereas the paper has definitely some merit, it received borderline reviews, with three borderline rejects and one borderline accept. The reviewers have appreciated the clarifications and discussions provided by the rebuttal, and one reviewer went up from reject to borderline reject. More precisely, this reviewer agrees that the paper has become stronger, but he/she believes that the paper requires additional experimental work (see section "After rebuttal" from his/her review). Another active reviewer during the rebuttal/discussion stage was not convinced by the rebuttal, after raising issues about identifiability. The area chair agrees that solving the identifiability issue is not a key requirement for this paper; however, this raises legitimate questions about the guarantees/properties of the returned solutions.

Overall, this is a borderline paper, which introduces an interesting idea, but which requires additional experimental work and discussions about the properties of the solutions. Unfortunately, the area chair agrees with the majority of the reviewers and follows their recommendation. The two previous points should be addressed if the paper is resubmitted elsewhere.
Decision: Reject