Learning Graph Structure from Convolutional Mixtures
Authors: Max Wasserman
Saurabh Sihag
Gonzalo Mateos
Alejandro Ribeiro
Venue: ICLR 2022 Submitted (2022)
Keywords: Graph Neural Network
Graph Signal Processing
Graph Learning
Topology Inference
Algorithm Unrolling

Abstract: Machine learning frameworks such as graph neural networks typically rely on a given, fixed graph to exploit relational inductive biases and thus effectively learn from network data. However, assuming the knowledge of said graphs may be untenable in practice, which motivates the problem of inferring graph structure from data. In this paper, we postulate a graph convolutional relationship between the observed and latent graphs, and formulate the graph learning task as a network inverse (deconvolution) problem. In lieu of eigendecomposition-based spectral methods or iterative optimization solutions, we unroll and truncate proximal gradient iterations to arrive at a parameterized neural network architecture that we call a Graph Deconvolution Network (GDN). GDNs can learn a distribution of graphs in a supervised fashion, and perform link-prediction or edge-weight regression tasks by adapting the loss function. Since layers directly operate on, combine, and refine graph objects (instead of node features), GDNs are inherently inductive and can generalize to larger-sized graphs after training.
Algorithm unrolling offers an explicit handle on computational complexity; we trade-off training time in return for quick approximations to the inverse problem solution, obtained via a forward pass through the learnt model. We corroborate GDN's superior graph recovery performance using synthetic data in supervised settings, as well as its ability to generalize to graphs orders of magnitude larger that those seen in training. Using the Human Connectome Project-Young Adult neuroimaging dataset, we demonstrate the robustness and representation power of our model by inferring structural brain networks from functional connectivity estimated using fMRI signals.

Under review as a conference paper at ICLR 2022
LEARNING GRAPH STRUCTURE FROM CONVOLUTIONAL MIXTURES
Anonymous authors
Paper under double-blind review
ABSTRACT
Machine learning frameworks such as graph neural networks typically rely on a given, fixed graph to exploit relational inductive biases and thus effectively learn from network data. However, when said graphs are (partially) unobserved, noisy, dynamic, the problem of inferring graph structure from data becomes rele- vant. In this paper, we postulate a graph convolutional relationship between the observed and latent graphs, and formulate the graph learning task as network inverse (deconvolution) problem. In lieu of sigendecomposition-buee methods iterative optimization solutions, we unroll and truncate proximal gra- dient iterations to arrive at parameterized neural network architecture that we call Graph Deconvolution Network (GDN). GDNs can learn distribution of graphs in supervised fashion, and perform link prediction or edge-weight regression tasks by adapting the loss function. Since layers directly operate on, combine, and refine graph objects (instead of node features). GDNs are inherently inductive and can generalize to larger-sized graphs after training. We corroborate GDN's superior graph recovery performance using synthetic data in supervised settings, as well as its ability to generalize to graphs orders of magnitude larger that those seen in training. Using the Human Connectome Project- Young Adult neuroimag- ing dataset, we demonstrate the robustness and representation power of our model by inferring structural brain networks from functional connectivity.
spectral
INTRODUCTION
Inferring graphs from data to uncover latent complex information structure is a timely challenge for geometric deep learning (Bronstein al. 2017) and graph signal processing (Ortega et al. 2018) But it is also an opportunity, since network topology inference advances (Dong et al. 2019 Mateos al., 2019) could facilitate adoption of graph neural networks (GNNs) even when no input graph available (Hamilton) 2020). The problem is also relevant when given graph is too noisy or per- turbed beyond what stable (possibly pre-trained) GNN architectures can effectively handle (Gamal et al. 2020a). Early empirical evidence suggests that even when a graph is available. the structure could be further optimized for a downstream task (Kazi et al. 20200 Feizi et al.) (013), or else spar- sified boost computational efficiency and model interpretability (Spielman & Srivastava] 2011).
In this paper, we posit a convolutional model relating observed and latent undirected graphs and for- mulate the graph learning task as supervised network inverse problem; see Section 2 for formal problem statement. This fairly general model is motivated by various practical domains outlined in Section 3 such as identifying the structure of network diffusion processes (Segarra al.) 2017 Pas- deloup et al. 2018), as well as network deconvolution and demoising (Feizi et al. 2013). We propose a parameterized neural network model, termed graph deconvolution network (GDN), which we train in supervised fashion to learn the distribution of latent graphs. The architecture is derived from the principle of algorithm unrolling used learn fast approximate solutions to inverse problems (Cre-) gor & LeCun, 2010; (Sprechmann et al., 2015) Monga et al. (002)) an idea that is yet to be explored in the context of graph structure identification. Since layers directly operate on, combine, and re- fine graph objects (instead of nodal features), GDNs are inherently inductive and can generalize to graphs of different size. This allows the transfer of learning on small graphs to unseen larger graphs which has significant implications in domains like social networks and molccular biology (Yehudai jet al. (202T) Our experiments demonstrate that GDNs are versatile to accommodate link prediction or edge-weight regression aspects of learning the graph structure, and achieve superior performance

---

Under review as a conference paper at ICLR 2022
over various competing alternatives. Building recent models of functional activity in the brain as a diffusion process over the underlying anatomical pathways (Abdelnour et al. 2014: Liang & Wang 2017), show the applicability of GDNs to infer brain structural connectivity from functional net- works obtained from the Human Connectome Project- Young Adult (HCP-YA) dataset. We also use
GDNs to predict Facebook ties from user co-location data, outperforming relevant baselines.
Related work. Network topology inference has a long history in statistics (Dempster. 1972), with noteworthy contributions for probabilistic graphical model selection; see e.g. (Kolaczyk) [009]
Friedman et al. 2008; [Dtton & Maathuis, 2017)) Recent advances were propelled by graph sig- nal processing insights through the lens of signal representation (Dong et al., 2019 Mateos et al.,
2019), exploiting models of network diffusion (Daneshmand et al. 2014), or else leveraging cardinal
properties of network data such as smoothness (Dong et 2016 Kalofolias 2016) and graph sta- tionarity (Segarra et al. 2017 Pasdeloup et a (018). These works formulate (convex) optimization problems one has to solve for different graphs, and can lack robustness to signal model misspecifi- cations. Scalability is issue for the spectral-based network deconvolution approaches in (Segarra) ct al. 2017| Feizi et al. 2013), that require computationally-cxeeniiii eigendecompositions of the input graph for each problem instance. Moreover, none of these methods advocate supervised learning paradigm to learn distributions over adjacency matrices. When it comes to this latter objec- tive, deep generative models (Liao et al. 2019 Waang al.] 2018 Li al. 2018) are typically trained in an unsupervised fashion, with the different goal of sampling from the learnt distribution. Most of these approaches learn node embeddings and are inherently transductive. Recently so-termed latent graph learning has been shown effective in obtaining better task daskenriven representations of relational data for machine learning (ML) applications (Wang et al., 2019; Kazi et al. 2020 Veličkovć al., 2020). or to learn interactions among coupled dynamical systems (Kipf et al. 2018))
Summary of contributions. We introduce GDNs, a supervised learning model capable of recover- ing latent graph structure from observations of its convolutional mixtures, i.e., related graphs con- taining spurious, indirect relationships. Our experiments on synthetic and real datasets demonstrate the effectiveness of GDNs for said task. They also showcase the model's sss versatility to incorporate domain-specitn topology information about the sought graphs. On synthetic data, GDNs outperform comparable methods on link prediction and edge-weight regression tasks across different random- graph ensembles, while incurring a markedly lower (post-training) computational cost and inference time. GDNs are inductive and learnt models transfer across graphs of different sizes. We verify they exhibit minimal performance degradation even when tested on graphs 60x larger. Finally, using GDNs we propose novel ML pipeline to learn whole brain structural connectivity (SC) from func- tional connectivity (FC), a challenging and timely problem in network neuroscience. Results on the high-quality HCP-YA YA imaging dataset show that GDN performs well on specific brain subnetworks that are known to be relatively less correlated with the corresponding FC due to ageing-relate ef- fects- - testament to the model's robustness and expressive power. Overall, results here support the promising prospect of using graph representation learning to integrate brain structure and function.
2 PROBLEM FORMULATION
In this work we study the following network inverse problem involving undirected and weighted graphs G(V, E), where V = {1, [I.....N} is the set of nodes (henceforth common to all graphs), and E C V x V collects the edges. We get to observe graph with symmetric adjacency matrix Ao E N that is related a latent sparse, graph A E R R.NN of interest via the model
Ao = aot + ta + A22A2 + - A
(I)
where I denotes the N N identity matrix. The analytic graph mapping in 1 is polyno- mial in Ar. of possibly infinite degree, yet the Cayley- theorem asserts it can always be equivalently reparameterized as a polynomial of degree smaller than N. Said matrix polynomials
H (A; h) := >K A+, K < N 1, with coefficients h = [/o..... .a....,,ue, lg]] T E + are known as shift-invariant graph convolutional filters; see e.g.. OOrtega et al. 2018 Gama et al.) 2020b). Going back to the model ( we postulate that Ao = H h) for some filter order K and its associated coefficients h. such that we can think of the observed network as generated via graph convolutional process acting on A,. More pragmatically Ao may correspond to noisy observation of H [A h), and this will be clear from the context when e.g., estimate Ao from data.
2

---

Under review as a conference paper at ICLR 2022
Recovery of the latent graph As is challenging endeavour since we do not know H (A h), namely the parameters K or h; see Appendix A.I for issues of model identifiability. Suppose that Ar. is realization drawn from some distribution of sparse graphs, say, for e.g., random geometric graphs or structural brain networks from a homogeneous dataset. Then given independent training samples T := (4 A adhering to (1) our goal is to learn judicious parametrie mapping that predicts the graph adjacency matrix A = (Aoo: b) by minimizing a loss function
L( = T
Σ ( ( 0)). iET
(2)
The loss chosen to accommodate the task at hand hinge loss for link prediction or mean- squared/absolute error for the more challenging edge-weight regression problem; see Appendix A.4
3 MOTIVATING APPLICATION DOMAINS
Here we outline several graph inference tasks that can be cast as the network inverse problem
Latent graph structure identification from diffused signals. Our initial focus here on identify- ing graphs that explain the structure of a class of network diffusion processes, Formally, let æ E R be a graph signal (i.e., a vector of nodal features) supported on latent graph 9 with adjacency Ar, Further, let to be a zero-mean white signal with covariance matrix Σn.. = E F/ww" ] I. We say that A, represents the structure of the signal ær there exists a linear network diffusion process in G that generates the signal æ from namely æ Ee A; w H(A, h)) h)w. This is fairly common generative model for random network processes (Barrat et al. 2008 DeGroot 1974). We think of the edges of G as direct (one-hop) relations between the elements of the signal The diffusion de- scribed by (AL. h) generates indirect relations. In this context, the latent graph learning problem to recover a sparse AG from a set X' = { of P samples of æ (Segarra et al. 2017). Inter- estingly, from the model for it follows that the signal covariance matrix Σg E also a polynomial in A, (we used En, I, and wrote H <- H(Ar, h) for notational simplicity). The connection with (T) should now be apparent with the identification Ao = Σg. In practice, given the signals in X' one would estimate the covariance matrix, e.g. via the sample covariance Σ,, and then aim to recover the graph A by tackling the aforementioned network inverse problem. In this paper, we propose a fresh learning-basee solution using training examples T := (Σ6) AA
H is
(4) y 1
Network deconvolution and denoising. The network deconvolution problem is to identify sparse adjacency matrix A that encodes direct dependencies, when given an adjacency matrix Ao of in- direct relationships. The problem broadens the scope of e.g., signal deconvolution to networks and can be tackled by attempting to invert the mapping Ao = AL (I AL) >x solution proposed in (Feizi al., 2013) assumes a polynomial relationship in but for the particular case of a single-pole, single-zero graph filter with very specific filter coefficients [ef. ( with og- = 0 and a; = 1, 2 1]. This way, the indirect dependencies observed in Ao arise due to the higher-order convolutive mixture terms A + A + superimposed to the direct interactions in AL we wish recover. Our idea in this paper to adopt a more general, data-driven learning approach in assuming that Ao can be written as polynomial in AL, but being agnostic to the form of the filter. Unlike the problem outlined before, here Ao need not be covariance matrix. Indeed, Ao could be corrupted graph we wish to denoise, obtained via an upstream graph learning method.
11 A'. This
Potential application domains for which supervised data T == { AWy 1 is available include bioinformatics [infer protein contact structure from mutual information graphs of the covariation of amino acid residues (Feizi et al., 2013]], social and information networks [e.g., learn to sparsify graphs (Spielman & Srivastava] 201 1h to unveil the most relevant collaborations in a social network encoding co-authorship information (Segarra et al. 2017 J. and epidemiology (such as contact trac- ing by deconvolving the graphs that model observed discase spread in a population). In Section 5.2 we experiment with social networks and the network neuroscience problem described next.
Inferring structural brain networks from functional MRI (IMRI) signals. Brain connectomes encompass networks of brain regions connected by (statistical) functional associations (FC) or by anatomical white matter fiber pathways (SC). The latter can be extracted from time- consuminn trac- tography algorithms applied to diffusion MRI (dMRI), which are particularly fraught due to quality issues in the data (Yeh al. 2021). FC represents pairwise correlation structure between blood-
3

---

Under review as a conference paper at ICLR 2022
Jyygenlevel-dependenn (BOLD) signals measured by fMRL. Deciphering the relationship between SC and FC is a very active area of research (Abdelnour et al. 2014 Honey et al.
2009 and also relevant in studying neurological disorders, since it known to vary with respect to healthy subjects in pathological contexts (Gu et al. 2021). Traditional approaches go all the way from correlation studies (Greicius et al. 2008) to large-scale simulations of nonlinear cortical activity models (Honey) iet al. 2009). More aligned with the problem addressed here, recent studies have shown that linear diffusion dynamics can reasonably model the FC-SC coupling (Abdelnour et al.) 2014] /urampudi et al. 2018). Using our notation, the findings in (Abdelnour et al. 20144 suggest that the covariance Ao Σn of the functional signals (i.e., the FC) is related to the the sparse SC graph As via the model in ① Similarly, Liang & Wang (2017) contend the estimated FC can be represented as weighted sum of the powers of the SC matrix, consisting of both direct and indirect effects along varying paths. There is evidence that FC links tend to exist where there is no or little structural connection (Damoiscaux & Greicius 2009). a charactcristic naturally captured by ( These con- siderations motivate adopting the proposed graph learning method to infer SC patterns from fMRI signals (Section 5.2), a significant problem for several reasons. The ability to collect only FC and get informative estimates of SC open the door to large scale studies, previously constrained by the logistical, cost, and computational resources needed to acquire both modalities.
4 GRAPH DECONVOLUTION NETWORK
Here we present the proposed GDN model, a parameterized neural network architecture that we train in a supervised fashion to recover latent graph structure via network deconvolution. In the sequel, we obtain conceptual iterations to tackle an optimization formulation of the network inverse problem (Section 4. unroll these iterations to arrive at the GDN model we train using graph data (Section 4.2) and describe architectural customizations to improve performance (Section 4.3)
4.1 MOTIVATION VIA ITERATIVE OPTIMIZATION
Going back to the inverse problem of recovering sparse adjacency matrix A from the mixture Ao in (I. if the graph convolutional filter (A;; h) were known we could attempt to solve
> Ao - h()
Ås E arg min AEA
||
+ 2
where the regularization parameter À >> 0 trades off sparsity for reconstruction error. The convex set A == {A E EN dia 0, Au = Aij 2 0, Vi, E [I,...,NV' ]]} encodes the admissibility constraints on the adjacency matrix of an undirected graph: hollow diagonal, symmetric, with non- negative edge weights. The & norm encourages sparsity in the solution, being a convex surrogate of the edge-carde aige-caadinality function that counts the number of non-zero entries in A. Since Ao is often a noisy observation or estimate of the polynomial H (Ar h), is prudent to relax the equality (1) and minimize the squared residual errors instead.
The composite cost in 33 is a weighted sum of a non-smooth function ||Al| and continously
differentiable function g ((A) := Al H (A; h)]l? Notice though that g(A) is non-convex and its gradient is only locally Lipschitz continuous due to the graph filter H (A; h);; except when K = 1, but the affine case is not interesting since Ao is just scaled version of Az. By virtue of the polynomial structure of the non-convexity, provably convergent iterations can be derived using e.g., the Bregman proximal gradient method (Bolte et al., 2018) for judiciously chosen kernel generating distance; see also (Zhang & Hong 2020). But our end goal here is not to solve (3) iteratively, recall cannot even formulate the problem because H (A: h) is unknown. To retain the essence of the problem structure and motivate parametric model to learn approximate solutions, it suffices to settle with conceptual proximal gradient (PG) iterations (k henceforth denote iterations, A A)
Alk + 1] = ReLUU [k]] (V)(A - - k == 2==0,,22 0,1,2.....
(4)
where T is a step-size parameter in which we have absorbed X. These iterations implement a gra- dient descent step g followed by the é norm's proximal operator: for more on PG algorithms see (Parikh& & Boyd/ 2014). Due to the non-negativity constraints in A, the l norm's 's proximal op- erator takes the form of 7-shifted ReLU on the off- off-diagonal entries of its matrix argument. Also, the operator sets diag( A + 1)) = O. In the next section, we unroll and truncate these iterations to arrive at the trainable GDN parametric model ((Ao; θ)
4

---

Under review as a conference paper at ICLR 2022
[[
Single layer
aA + (0 A
Alk
ReLU
Ao
A
A
Av
GDN
Layer 1
Layer
Layer D
oo
Figure 1: Schematic diagram of the GDN architecture obtained via algorithm unrolling.
4.2 LEARNING TO INFER GRAPHS VIA ALGORITIM UNROLLING
The idea of algorithm unrolling can be traced back the seminal work of (Gregor & LeCun 2010)
In the context of sparse coding, they advocated identifying ilerations of PG algorithms with layers deep network of fixed depth that can be trained from examples using backpropagation. One can view this process effectively truncating the iterations of asymptotically convergent procedure, to yield a template architecture that learns to approximate solutions with substantial computational savings relative to the optimization algorithm. Beyond parsimonious signal modeling, there has been a surge in popularity of unrolled deep networks for a wide variety of applications; see e.g., (Monga et al. 202T) for recent tutorial treatment focused signal and image processing. However, the best of our knowledge this approach is yet to be explored for latent graph learning.
Building the algorithm unrolling paradigm, our idea is design non-linear, parameterized, feed-forward architecture that can be trained predict the latent graph År (Ao; θ) To this end, we approximate the gradient Vg(A) by retaining only linear terms in A. and build deep network by composing layer-wise linear filters and point-wise nonlinearites to capture higher- order interactions in the generative process H (A: := Σk= A. In more detail, we start by simplifying (A) (derived in Appendix A.6 by dropping all higher-order terms in A, namely
K
k-
Vo(A) = Σ
hk
A
AoA
+ 2
V Tr (A::H))
k=1
+=0
~ - h1 Ao
(22A AAo) + (2hgh2 + 12)
(5)
Notice that A Tr (A:( is a polynomial of degree 2K - 1. Hence, we keep the linear term adjacency
in A but drop the constant offset that is proportional I, which is inconsequential matrix updates with null diagonal. An affine approximation will lead to more benign optimization landscapes when it comes to training the resulting GDN model. All in all, the PG iterations become
A +|+ ReLU(a + 3(Ao + A[k] Ao) + A - -11
(6)
where A E A and we defined a := (1 - 2Th TAî), 3 = Th2, and 7 == 7h, The
latter parameter triplet encapsulates filter (i.e., mixture) coefficients and the X-dependent algorithm step-size, all of which are unknown in practice.
The GDN architecture is thus obtained by unrolling the algorithm (6) into a deep neural network; see Figure [ This entails mapping each individual iteration into layer and stacking prescribed number 1) of layers together to form (AAo; +). The unknown filter coefficients are treated as learnable parameters O == {a, 3, 7, r}, which are shared across layers as in recurrent neural net- works (RNNs). The reduced number of parameters relative to most typical neural networks is a characteristic of unrolled networks (Monga al., 2021p. In the next section, will explore a few customizations to the architecture in order to broaden the model's expressive power. Given a training
set T (A (6) A ( yT= Iearning is accomplished by using mini-batch stochastic gradient descent to minimize the task-dependent loss function L(O) in (2). We adopt a hinge loss for link prediction and rean-squared/absolute error for the edge-weight regression task. For link prediction, leamn threshold E R, to binarize the estimated edge weights and declare presence or absence of edges; Appendix A.4 for all maining-related details including those concerning loss functions.
also
The iterative refinement principle of optimization algorithms naturally carries over to our GDN model during inference. Indeed, we start with initial estimate A A E A and use cascade of
5

---

We present experiments on link prediction and edge-weight regression tasks using synthetic data (Section 5.1). as well as real HCP-YA neuroimgaging and social network data (Section (.2). In the link- prec-prrdittion task, performance is evaluated using error := incorrectly prodicsed odges For regres- Under review as a conference paper at ICLR 2022
D linear filters and point-wise non-linearities to refine it to an output ÅL (AAo; @). Matrix [o] is a hyperparameter we can select to incorporate prior information on the sought latent graph, or it could be learned; see Section 4.3 The input graph Ao to deconvolve is directly fed to all layers as in a residual neural network, and its role is also noteworthy. First, the constant matrix yAo r1 defines non-uniform soft thresholds to effectively sparsify the filter output per layer. Second, one can interpret a + ((A AAo) as a first-order graph filter defined on Ao. which used to process A - here viewed as a (graph) signal with N features per node invoke this graph signal processing insight. In its simplest rendition, the GDN architecture brings together elements of RNNs, ResNets and graph convolutional networks (GCNs) (Kipf & Welling 2017).
4.3 GDN ARCHITECTURE ADAPTATIONS
Here we outline several customizations and enhancements to the vainilla GDN architecture of the previous section, which we have empirically found to improve graph learning performance.
Incorporating prior information via algorithm initialization. By viewing our method as an iter- ative refinement of an initial graph [0). one can think of [ best initial guess, prior, over Ar. A simple strategy to incorporate prior information about some edge (i.j). encoded in Ai that view random variable, would be to set A
[.]. This technique is adopted when training on the HCP-Y: YA dataset in Section 5.2. by taking the prior A to be the sample mean of all latent (i.e., SC) graphs in the training set. This encodes our prior knowledge that there are strong similarities in the structure of the human brain across the population of healthy young adults. When Ag is expected to be reasonably sparse, we can A [0] O. which is effective as we show in Table Recalling the connections drawn between GDNs and RNNs, then the prior A plays a similar role to the initial RNN input and thus it could be learned. In any case, the ability to seamlessly in- corporate prior information to the model is an attractive feature of GDNs, and differentiates it from other methods trying to solve the network inverse problem.
Multi-Input Multi-Output (MIMO) filters. So far, in each layer we have a single learned filter, which takes an N x N matrix as input and returns another N x N matrix at the output. After going through the shifted ReLU nonlinearity, this refined output adjacency matrix is fed to the input to the next layer; a process that repeats D times. More generally, we can allow for multiple input channels (i.c., a tensor), as well as multiple channels at the output, by using the familiar convolutional neural network (CNN) methodology. This way, each output channel has its own filter parameters associated with every input channel. The j-th output channel applies its linear filters to all input channels, aggregating the results with a reduction operation (e.g., mean or sum), and applies a point-wise nonlinearity (here a shifted ReLU) to the output. This allows the GDN model to learn many different filters, providing richer learned representations. We denote this more expressive architecture as GDN-share-C C, emphasizing the MIMO filter with C' imput and output channels and whose parameters are shared across layers. Full details of MIMO filters are given in Appendix (A.5
Decoupling layer parameters. Thus far, we have respected the parameter sharing constraint im- posed by the unrolled PG iterations. We now allow each layer to learn decoupled MIMO filter, with its own set of parameters mapping from Ch input channels to Ck output channels. As the notation suggests, C/k. and Ck need not be equal. By decoupling the layer structure, allow GDNs to compose different learned filters to create more abstract features (as with CNNs or GCNs). Accordingly, it opens up the architectural design space to broader exploration, e.g., wider layers early and skinnier layers at the end. Exploring this architectural space is beyond the scope of this paper and is left as future work. subsequent experiments, the GDN model for which intermediate layers & E ( D
1} have C' Chk Cl i.e., flat architecture, is denoted as GDN-C.
EXPERIMENTS
total possible edges sion, we adopt the mean-squared-erroo (MSE) mean-absooltee-rrru (MAE) as figures of merit. In the synthetic data experiments we consider three test cases whereby the latent graphs are respec- tively drawn from ensembles of Frdōs-Rényi (ER), random geometric (RG), and Barahási-Alhert

---

Under review as a conference paper at ICLR 2022
Table 1: Mean and standard error of the test performance across both tasks (Top: link-prediction, edge-weight regression) on each graph domain. Bold denotes best performance.
Bottom:
Models
RG
ER
BA
SC
GDN-8
4.624.561
41 11-11
27.5 1.
8.921
GDN-share-8
5.512.4e1
20.2:1
27.648.0e4
9,412.1e1
Error (%)
GLASSO
8,826,5e2
2.22
34.919.8e3
20.013.8e2
ND
9.4+3.164
43.9#1.46-2
34.1
21.3+t
SpecTemp
11.1+3.2e-
44.422
30.2
30.0+1.3-1
LSSOtt
24. 24.224.8e0
42.5+2.8e1
28.0
31.5325.8e4
Threshold
12.0
42.928.3e1
32.321.000
21.7=221e-1
GDN-8
4.2c-2 #4.3
2.3e-1
#2.26
1.8e-1
#22.4-43
5.3e-3 #6.7es5
GDN-share-8
6.0e-2 #2.4e-1
2.3e-1
+2.1e3
2.7c-1
41.6e/2
6.5e-3 +-4.0e-5
MSE
GLASSO
2.0e-1 12.663
2.8e-1
22.002
2.6e-1
11.622
4.4e-2 13.365
ND
1.8e-1 #1.5e3
2.4e-1
45.004
2.2e-1
+1.003
5.6e-2 26.866
SpecTemp LSOpt
5.1e-2 13.3e
5.3e-1
18.9e5
3.3e-1
11.855
1.5e-1 14.263
9.9e-2 11.7e1
2.5e-1 11.5e3
2.0e-1
12.5e3
6.1e-0 15.8c4
(BA) random graph models. We study an additional scenario where use SCs from IICP-YA (re- ferred to as the 'pseudo-synthetic" case because the latent graphs are real structural brain networks). We compare GDNs against several relevant baselines: Network Deconvolution (ND) which uses spectral approach to directly invert a very specific convolutive mixture (Feizi et al,, 2013); Spec- tral Templates (SpecTempp that advocates convex optimization approach to recover sparse graphs from noisy estimates of Ao 's eigenvectors (Segarra et al. 2017); Graphical LASSO (GLASSO), a
regularized MLE of the precision matrix for Gaussian graphical model selection (Friedman al.,
2008); least-squares fitting of h followed by non-convex optimization to solve
(3) (LSOpt;; and Hard Thresholding (Threshold) to assess how well simple cutoff rule can perform. Unless other- wise stated, in all the results that follow we use GDN(-share) models with D layers and train using the Adam optimizer (Kingma & Bal 2015) with learning rate of 0.01 and batch size of 200.
5.1 LATENT GRAPH STRUCTURE AATETTRRIDEEEEIIIN IDENTIFICATION FROM DIFFUSED SIGNALS
set of latent graphs are either sampled from RG, ER, or the BA model, or taken as the SCs from the HCP- YA dataset. In attempt to make the latent graphs somewhat comparable, across all models we let = 68 (as constrained by the regions of interest in the adopted brain atlas), we force connectivity, and edge sparsity levels in the range (0.5, 0.6] when feasible (these are also typical SC
values). To generate each observation
(6) we simulated P = 50 standard Normal, white signals diffused over A (5); from which we form the sample covariance Σ. in Section We let K 2, and sample the filter coefficients h E 3R3 in (A, h) uniformly from the unit sphere. To examine robustness to the realizations of h. we repeat this data generation process three times (resampling the filter coefficients). We thus create three different datasets for each graph domain (12 total). For the sizes of the training/valiin viaiingg/aiidaaion/tees splits, the pseudo-synthetic domain uses 913/50/100 and the synthetic domains use 913/500/500. All models on synthetics are trained using A0) 0, while models on the SCs take their prior as the edge-wise mean across all SCs in the training split.
Table D tabulates the results for synthetic and exhibit localized connectivity patterns (RG and SC), GDNs significantly outperform the baselines on both tasks. For the SC test case, GDN (GDN-share) reduces error relative the mean prior by 27.48 + 1.73% (23.02 + 1.73%) and MSE by 37.34 + 0.79% (23.23 + 0.48%). Both GDN architectures show the ability to learn such local patterns, with the extra representational power of GDNs (over GDN-share) providing additional boost in performance. All models struggle BA and ER with GDNs showing better performance even for these cases.
experiments. For graph models that
Size generalization: Deploying larger graphs. Unlike CNNs and GNNs, GDNs learn the parameters of graph convolutions for the processing of graphs, not the signals supported on them. GDNs inductive and allow to deploy the learnt model larger graph size domains. To test
7

---

Under review as a conference paper at ICLR 2022
10
GDN-1
GDN-8
GDN-share-8
8-
GDN-share-1
error (%)
500 number of vertices scale)
200
1000
4000
1.6 3.2
4.8
6.4
8
Figure 2: Left: After training on RG graphs of size N = 68, GDNs are capable of maintaining performance on RG graphs orders of magnitude larger. Missing data at N 4000 corresponds to overwhelmed our memory resources. The simplest model GDN-share-1 improves performance with increasing graph size. Right: Reduction in MAE (%) over mean prior of SCs for different lobes. Most significant improvements are concentrated in temporal and frontal lobes.
the extent which GDNs generalize when N grows, train four GDN models (GDN-share-1 1, GDN-share-8, GDN-1, GDN-8) on RG graphs with size N = 68, and tested them on RG graphs of size N [68, 75, 100, 200, 500, 1000, 2000, 4000), with 200 graphs of each size. As graph sizes increase. we require more samples in the estimation of the sample covariance to maintain constant signal-to-noise ratio. To simplify the experiment and its interpretation, estimation and directly use the ensemble covariance Ao = Σ, observation. As before, we take training/validation split of 913/50 500. Figure shows all GDN models effectively generalize to graphs orders of magnitude larger than they were trained on, giving up only modest levels of performance as size increases. For
disregard
4000, but one GDN models performed better than any baseline did on the original 68 node graphs. The GDN-share models maintain their top performance, with GDN-share-1 even further reducing error as the domain gets larger. This suggests that the GDNs without parameter sharing may be using their extra representational power to pick up finite-size effects, which may disappear as increases. The shared layer constraint in GDN-share models acts regularization: avoid over-fitting on given size domain to better generalize larger graphs.
Ablation studies. The choice of prior can influence model performance, as well as reduce training time and the number of parameters needed. When run stochastic block model (SBM) graphs with N = 21 nodes and 3 equally-sized communities (within block connection probability of 0.6, and 0.1 across blocks), for the link link-prediction task GDNs attain error of 16.8 2.7e-%% 1 2.1e2%% 14.5 + 1.0e-2%, 14.3 8.8c-2% using zeros, ones, block diagonal, and learned prior, respectively. The performance improves when GDNs are given an informative prior (here a block diagonal matrix matching the graph communities), with further gains when GDNs are allowed to learn (0).
We also study the effect of gradient truncation, To derive GDNs we approximate the gradient (g(A) by dropping all higher-order terms in A (K = 1). The case of K
corresponds to further dropping the terms linear in A, leading to PG iterations Alk + 1] = ReLU(A(k] + +oAo - -111 lef. (6). We run this simplified model with D 8 layers and 8 channels per layer on the same RG graphs presented in Table Lacking the linear term that facilitates information aggregation in the graph, the model is not expressive enough and yields higher error (MSE) of 25.72 + 1.3e-2% (1.7e-1 4.74-4 for the link- iine-creiittion (edge weight regression) task. Models with 2 result in unstable training, which motivates our choice of K in GDNs.
5.2 REAL DATA
HCP-YA neuroimaging dataset. HCP represents unifying paradigm to acquire high quality roimaging data across studies that enabled unprecedented quality of macro-scale human brain con- nectomes for analyses in different domains (Glasser et al. 2016). We use the dMRI and resting state
8

---

Under review as a conference paper at ICLR 2022
fMRI data from the HCP-YA dataset (Van Essen et al. 2013), consisting of 1200 healthy, young adults (ages: 22-36 years). The SC and FC are projected on a common brain atlas, which is a group-
ing of cortical structures in the brain to distinct regions. We interpret these regions nodes in brain graph. For our experiments, we use the standard Desikan-Killans atlas (Desikan et al. 2006)
with N = 68 cortical brain regions. The SC-FC coupling on this dataset is known be the strongest in occipital lobe and vary with age, sex and cognitive health in other subnetworks (Gu et al. 2021). Under the consideration of the variability in SC-FC coupling across the brain regions, we further group the cortical regions into 4 larger regions called 'lobes': frontal, parietal, temporal, and occip- ital (the locations of these lobes in the brain are included in Fig. in Appendix [A.7]. We aim to predict SC, derived from dMRI, using FC, constructed using BOLD signals acquired with fMRI.
From this data, we extracted a dataset of 1063 FC-SC pairs, T = {FC SSC,, He1 and use a siantnn//aliddaiionness split of 913 913/50/100 50/100. Taking the prior A[0] as the edgewise mean over all SCs in the training split Tirasn: A[0]ss = mean {SC() ..... sC( [.
and using it directly as a predictor on the test set (tuning threshold with validation data). we achieve strong performance on link- lunk-rediction and edge-weight regression tasks on the whole brain (error = 12.25%, MAE 0.0615). At the lobe level, the prior achieves relatively higher accuracy in occipital (error- 98.71% % MAE = 0.056) and parietal (error = 93.63% MAE 0.065) lobes as compared to temporal (error = 36., MAE- = 0.05) and frontal (error = 89.55%, MAE = 0.059) lobes; behavior which is unsurprising as SC in temporal and frontal lobes are affected by ageing and gender related variability in the dataset (Zimmermann et al. 2016). GDNs reduced MAE by 7.62%. 7.07%. 1.58%, and 1.29% in the temporal, frontal, parietal, and occipital networks respectively and 7.95% over the entire brain network, all relative to the already strong mean prior. The four lobe reductions visualized in Figure 2 Clearly, there smaller room for improvement in performance over occipital and frontal lobes. We observed the most significant gains over temporal and frontal lobes.
In summary, our pseudo-synthetic experiments in Section 5.1 show that SCs are amenable to learning with GDNs when the SC-FC relationship satisfies ( a reasonable model given the findings of (Abdelnour al., 2014). In general, SC-FC coupling can vary widely across both the population and within the sub-regions of an individuals brain for healthy subjects and in pathological contexts. Therefore, our results on HCP-YA YA dataset could potentially serve as baselines that characterize healthy subjects, and expanding our work to study the deviations in findings on similar data in a pathological context would be of future interest. When trained on the YA dataset, the GDN model exhibits robust performance over such regions with high variability in SC-FC coupling.
Friendship recommendation from physical co-location networks. Here we use GDNs to predict Facebook ties given human co-location data. GDNs are well suited for this deconvolution problem since one can view friendships as direct ties, whereas co-location edges include indirect relationships due to casual encounters in addition to face-to-face contacts with friends. A trained model could then be useful to augment friendship recommendation engines given co-location (bchavioral) data. The Thiers 13 dataset (Génois & Barrat 2018) monitored high school students, recording (i) physical co-location interactions with wearable sensors over 5 days; and (ii) social network information via survey. From this we construct dataset T of graph pairs, each with N 120 nodes, where Ao are co-location networks, i.e., weighted graphs where the weight of edge (i represents the number of times student i and j came into physical proximity, and Ag is the Facebook subgraph between the same students; further details are in Appendix A.7 We trained GDN-11, without MIMO filters, with learned [ using a waapii///vlliatoo/eesss split of 5000/1000/ 1000. We achieved test error of 8.9 + 1. 1.5e-2%, 1 12.98% reduction over next best performing baseline (results in Appendix A.7
6 CONCLUSIONS
In this work we proposed the GDN, an inductive model capable of recovering latent graph struc- ture from observations of its convolutional mixtures. By minimizing a task-dependent loss function, GDNs learn filters to refine initial estimates of the sought latent graphs layer by layer. The un- rolled architecture can seamlessly integrate domain-specine
prior information about the unknown graph distribution. Moreover, because GDNs: (i) are differentiable functions with respect to their parameters as well as their graph input; and (ii) offer explicit control on complexity (leading to fast inference times); one can envision GDNs valuable components in larger (even online) end-to- end graph representation learning systems. This way, while our focus here has been exclusively on network topology identification, the impact of GDNs can permeate to broader graph inference tasks.
9

---

Under review as a conference paper at ICLR 2022
Reproducibility statement. Code for running these experiments has been included in zipped directory with the submission and contains instructions for configuring a system to run experiments presented above. When randomness is involved, is the case when constructing the synthetic datasets, sampling white signals for diffusion, constructing a random split of the HCP-YA data, or initializing the parameters of our model before training, we random seed, allowing others to reproduce the results presented. For the derivation of the model, we provide further details in Appendix A.6 to supplement those shown in the main paper body (Section 4.1 In Appendix A.7 we refer the readers to the HCP website, where one can download the HCP- YA data, as well as references to the processing pipelines used construct the FCs and SCs used in this paper. The processed brain data was too large include with the code, but is available upon request.
consistent and clearly defined
REFERENCES
F. Abdelnour, H. U. Voss, and A. Raj. Network diffusion accurately models the relationship between structural and functional brain connectivity networks. Neuroimage, 90:335-344 Apr. 2014.
Alain Barrat, Mare Barthelemy, and Alessandr Vespignani. Dynamical Processes on Complex Net- works. Cambridge University Press, New York, NY, 2008.
Jérôme Bolte, Shoham Sabach, Mare Teboulle, and Yakov Vaisbourd. First order methods beyond gradient continuity with applications to quadratic inverse problems. SIAM
convexity and gradiett J. Optim., 283):2131-221111 2018.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geo- metric deep learning: going beyond euclidean data. IEEE Signal Process. Mag., 34(4):18-42, 2017.
Jessica S Damoiseaux and Michael D Greicius. Greater than the sum of its parts: A review of studies combining structural connectivity and resting-state functional connectivity. Brain Struct. Func., 213(6):525-55) 5333, 2009.
Hadi Daneshmand, Manuel Godez-Rodriguez, Le Song, and Bernhard Schoelkopf. Estimating diffusion network structures: Recovery conditions, sample complexity & soft-thresholding algo- rithm. In International Conference on Machine Learning, pp. 793-801. PMLR, 2014.
Morris H. DeGroot, Reaching a consensus. J Am Stat Assoc., 69:1 1e-118-121, 1974.
Arthur P Dempster. Covariance selection. Biometrics, pp. 157-175, 1972.
Rahul S Desikan, Florent Ségonne, Bruce Fischl, Brian T Quinn, Bradford C Dickerson, Deborah Blacker, Randy L Buckner, Anders M Dale, R Paul Maguire, Bradley T Hyman, et al. An auto- mated labeling system for subdividing the human cerebral cortex on mri scans into gyral based regions of interest. Neuroimage, (1):): 9800990,00 2006.
Xiaowen Dong, Dorina Thanou, Pascal Frossard, and Pierre Vandergheynst. Learning laplacian matrix in smooth graph signal representations. IEEE Trans. Signal Process., 64(23):6160-617) 2016.
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.
Mathias Drton and Marloes H Maathuis. Structure learning in graphical modeling. Annu. Rev. Stuf. Appl, 4:365-393, 2017.
Soheil Feizi, Daniel Marbach, Muriel Medard, and Manolis Kellis. Network deconvolution general method to distinguish direct dependencies networks. Nat. Biotechnol, 3 31(8):726-733, 2013.
Friedman, T. Hastie, and R. Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 93):432-441, 2008.
10

---

Under review as a conference paper at ICLR 2022
Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability properties of graph neural networks. IEEE Trans. Signal Process., 68:5680-550 5695, 2020a.
Fernando Gama, Elvin Isufi, Geert Leus, and Alejandro Ribeiro. Graphs, convolutions, and neural networks: From graph filters graph neural networks. IEEE Signal Process. Mag., 37(6):128- 138, 2020b.
Mathieu Génois and Alain Barrat. Can co-location be used as proxy for face-to-face con- tacts? EPJ Data Science, 7(1):11, May 2018. URL /ttthht:////ot: http:////.....00001111//////////
S 113688-18-0144--
Matthew F Glasser, Stephen M Smith, Daniel S Marcus, Jesper LR Andersson, Edward J Auerbach, Timothy EJ Behrens, Timothy S Coalson, Michael Harms, Mark Jenkinson, Steen Moeller, et al. The human connectome project's neuroimaging approach. Nature neuroscience, 19(9): 1175-1187, 2016.
Karol Gregor and Yann LeCun. Learning fast approximations of sparse coding. In International Conference on Machine Learning, pp. 399-406, 2010.
Michael Greicius, Kaustubh Supekar, Vinod Menon, and Robert Dougherty, Resting-state functional connectivity reflects structural connectivity in the default mode network. Cereb Cortex, 19:72-8, 12 2008.
Zijin Gu, Keith Wakefield Jamison, Mert Rory Sabuncu, and Amy Kuceyeski. Heritability and interindividual variability of regional structure-function coupling. Nat. Commun, 12(1):1-12, 2021.
William L. Hamilton. Graph representation learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 1459) 2020.
C. Honey, O. Sporns, L. Cammoun, X. Gigandet, J. Thiran, R. Meuli, and Hagmann. Predicting human resting-state functional connectivity from structural connectivity. Proc. Natl. Acad. Sci. U.S.A, 106:2035 2040, 2009.
Vassilis Kalofolias. How to learn a graph from smooth signals. In Artificial Intelligence and Statis- fics, pp. 920-929, 2016.
Ances Kazi, Luca Cosmo, Nassir Navab, and Michael M. Bronstein. Differentiable graph mod- ule (DGM) for graph convolutional networks. CoRR, abs/2002.04999, 2020. URL https: wttrxxi..rr//ab//// 04999
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In ICLR (Poster), 2015.
Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, and Richard Zemel. Neural relational inference for interacting systems. In International Conference on Machine Learning, volume 80, pp. 2688-2697, (0-15 Jul 2018.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017.
E. D. Kolaczyk. Statistical Analysis of Network Data: Methods and Models. Springer, New York, NY, 2009.
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning gemerattiv 2018. URL
models of graphs. CoRR,
03324
Hualou Liang and Hongbin Wang. Structure-funetiio network mapping and its assessment via persistent homology. PLOS Comput. Biol, 13(c1005325):119, Jan. 2017.
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Charlie Nash, William L. Hamilton, David Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. In Advances in Neural Information Processing Systems, 2019.

---

Under review as a conference paper at ICLR 2022
Gonzalo Mateos, Santiago Segarra, Antonio G. Marques, and Alejandro Ribeiro. Connecting the dots: Identifying network structure via graph signal processing. IEEE Signal Process. Mag., 36 (3):16-43, May 2019.
Vishal Monga, Yuelong Li, and Yonina C. Eldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. IEEE Signal Process. Mag., 38(2):18-44, 2021.
Antonio Ortega, Pascal Frossard, Jelena Kovačević, José M. F. Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proc. IEEE, 106(5):808-88)) 828, 2018.
Neal Parikh and Stephen Boyd. Proximal algorithms. Foundations and Trends in Optimization, (3):127-239, 2014.
Bastien Pasdeloup, Vincent Gripon, Grégoire Mercier, Dominique Pastor, and Michael G. Rabbat. Characterization and inference of graph diffusion processes from observations of stationary sig- nals. IEEE Trans. Signal Inf. Process. Netw., 4(3):481 1498,,49,,660 2018.
Santiago Segaraa, Antonio G. Marques, Gonzalo Mateos, and Alejandro Ribeiro. Network topology inference from spectral templates. IEEE Trans. Signal Inf. Process. Nenw, 3(3):467-483, August 2017.
Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM J. Comput.,
December 2011.
Sprechmann, A. M. Bronstein, and G. Sapiro. Learning efficient sparse and low rank models. IEEE Trans. Pattern Anal. Mach. Intell., (7(())1822-18))) 1833, 2015.
Sriniwas Govinda Surampudi, Shruti Naik, Raju Bapi Surampudi, Viktor K Jirsa, Avinash Sharma, and Dipanjan Roy. Multiple kemnel learning model for relating structural and functional connec- tivity in the brain. Scientific reports, 8(1):1-14, 2018.
David C Van Essen, Stephen Smith, Deanna M Barch, Timothy EJ Behrens, Essa Yacoub, Kamil Ugurbil, Wu-Minn HCP Consortium, et al. The WU-Minn Human Connectome Project: An overview. Neuroimage, 80:62-79, 2013.
Petar Veličković, Lars Buesing, Matthew C. Overlan, Razvan Pascanu, Oriol Vinyals, and Charles Blundell. Pointer graph networks. In Advances in Neural Information Processing Systems, 2020.
Hongwei Wang, Jia Wang, Jialin Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Xing Xie, and Minyi Guo. GraphGAN: Graph representation learning with generative adversarial nets. In AAAI Conference on Artificial Intelligence, pp. 2508-2515, 2018.
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M. Bronstein, and Justin M. Solomon. Dynamic graph CNN for learning on point clouds. ACM Trans. Graph., 38(5), Oc- tober 2019.
C. H. Yeh, D. K. Jones, X. Liang, M. Descoteaux, and A. Connelly. Mapping structural connectivity using diffusion mri: Challenges and opportunities. J. Magn. Reson., 1366))1666-16888 2021.
Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, and Haggai Maron. From local structures size generalization in graph neural networks. In International Conference on Machine Learning, pp. 11975-11986, PMLR, 2021.
Ming Yuan and Yi Lin. Model selection and estimation in the Gaussian graphical model. Biometrika, 94( 14(1)119-35 2007.
Junyu Zhang and Mingyi Hong. First-order algorithms without Lipschitz gradient: A sequential local optimization approach. CoRR, abs/2010.03194, 2020. URI. htttts://taxiv..///
abs /2010.00.000 03194
Joelle Zimmermann, Petra Ritter, Kelly Shen, Simon Rothmeier, Michael Schimer, and Anthony R McIntosh. Structural architecture supports functional organization in the human aging brain at a regionwise and network level. Hum. Brain Mapp, 37(7):264522611 2016.
12

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1 MODEL IDENTIFIABILITY
Without any constraints on h and Ag. the problem of recovering A from Ao ((A h) as in (T) is clearly non-identifiable Indeed, if the desired solution is A& (with associated polynomial coefficients h), there is always at least another solution Ao corresponding to the identity polynomial mapping. This is why adding structural constraints like sparsity on r. will aid model identifiability, especially when devoid of training examples.
is worth mentioning that ① implies the eigenvectors of As and Ao coincide. So the eigen- vectors of the sought latent graph are given once we observe Ao, what is left determine are the eigenvalues. We have in practice observed that for several families of sparse, weighted graphs, the cigenvector information along with the constraint A E A are sufficient to uniquely specify the graph. Interestingly, this implies that many random weighted graphs can be uniquely determined from their eigenvectors. This strong uniqueness result does not render our problem vacuous, since seldomly in practice one gets to observe Ao (and hence its eigenvectors) error free.
If one were to formally study identifiability of ① (say under some structural assumptions on A, and/or the polynomial mapping), then one has to recognize the problem suffers from an in- herent scaling ambiguity. Indeed, if given Ao = H(Ar;)) h) which means the pair A,, and h = [ho, .i,..., hx] is a solution, then for any positive scalar one has that aA,, and [ho, ht/a...... hx/ (a K TTT is another solution. Accordingly, uniqueness claims can only be mcan- ingful modulo this unavoidable scaling ambiguity. But this ambiguity is lifted once we tackle the problem in a supervised learning fashion - our approach in this paper. The training samples in D
T (A0 (6) A Ji= fix the scaling, and accordingly the GDN can learn the mechanism map- ping of interest Ao + AL. Hence, an attractive feature of the GDN approach is that by using data, some of the inherent ambiguities in ( are naturally overcome. In particular, the SpecTemp approach in (Segarra et al.] (017)) relies on convex optimization and suffers from this scaling ambi- guity, so it requires extra (rather arbitrary) constraint to fix the scale. The network deconvolution approach in (Feizi et al. 2013) relies on a fixed, known polynomial mapping, and while it does not suffer from these ambiguities it is limited in the graph convolutions it can model.
(0)
All in all, the inverse problem associated to [ is just our starting point to motivate a trainable parametrized architecture AL = 4 (Ao: +), that introduces valuable inductive biases to generate graph predictions. The problem we end up solving different (recall the formal statement in Section 2) because we rely on supervision using graph examples, thus rendering many of these challenging uniqueness questions less relevant.
A.2 GRAPH CONVOLUTIONAL MODEL IN CONTEXT
To further elaborate the relevance and breadth of applicability of the graph convolutional (or network diffusion) signal model æ = H(A,, 1.; h wu, we would like to elucidate connections with related work for graph structure identification. Note that while we used the diffusion-based gen- erative model for our derivations in Section 3 we do not need it as an actual mechanistic process. Indeed, like in (T) the only thing we ask is for the data covariance Ao Eg to be some ana- lytic function of The latent graph At. This is not extraneous to workhorse statistical methods for topology inference, which (implicitly) make specific choices for these mappings, e.g. (i) correlation networks (Kolaczyk] 2009) Ch. 7) rely on the identity mapping Σ, = AL; (ii) Gaussian graphical model selection methods, such as graphical lasso in (Yuan Lin 2007 Friedman et al.) 2008), adopt Σ2 A and (iii) undirected structural equation models x: Ar. + w which implies
E. (I AL)- Mateos et al. 2019). Accordingly, these models are subsumed by the general framework we put forth here.
A.3 INCORPORATING PRIOR INFORMATION
In Section 4.3 introduce the concept of using prior information in the training of GDNs. We do
so by encoding information we may have about the unknown latent graph A,, into A(O], the starting matrix which GDNs iteratively refine. If the A i repeated instances of graph with fixed nodes,
13

---

Under review as a conference paper at ICLR 2022
as is the case with the SCs with respect to the 68 fixed brain regions, simple strategy to incorporate prior information about some edge AL... now viewed as a random variable, would be Ao.. <- E| But there is more that can be done. We also use during the training of a GDN, for example taking Ao., < N ((E[A Var(Ar,,,) )), or even simpler, using resampling technique and taking Ao,,; to be a random sample in the training set. By doing so, we force the GDN to take into account the distribution and uncertainty in the data, possibly leading to richer learned representations and better performance. It also would act form of regularization, not allowing the model to converge on the naive solution of outputting the simple expectation prior, a likely local minimum in training space.
estimate the variance Var(A r... ). and
A.4 TRAINING
Training of the GDN model will be performed using stochastic (mini-batch) gradient descent to minimize a task-dependent loss function L( as in ( The loss is defined either as (i) the edgewise
squared/absolute error between the predicted graph and the true graph for regression tasks, or (ii)
hinge loss with parameter 7 2 0, both averaged over a training set T (A0 A (0)
1== namely
[ ((40)
(8) + /hinge Σ
($ 11)
0: θ )i. 7)+
An. 0
(-0(AA) O). +1 7)+
ALt >
( (
(0)
( θ) Jse
1 4(40:
E(A (A4): 4) maa = | - (A)
(9) (1)
L(
1 Σ (4
( ((4) ()).
u E (hinge, mse, mae).
iET
Link prediction with GDNs and unbiased estimates of generalization. the edge-weight re- gression task, GDNs only use their validation data to determine when training has converged. When performing fink-prediction, GDNs have an additional use for this data: to choose the cutoff thresh- old t E R4, determining which raw outputs (which are continuous) should be considered positive edge predictions, at the end of training.
We use the training set learn the parameters (via gradient descent) and to tune t. During the validation step, when then use this muin-set-tunede on the validation data, giving an estimate of generalization error. This is then used for carly-stopping, determining the best model learned after training, etc. We do not use the validation data to tune f during training. Only after training has completed, do tune / with validation data. We train handful of models this way, and the model which produces the best validation score (in this case lowest error) is the tested with the validation- tuned-t, thus providing an unbiased estimate of generalization.
A.5
MIMO MODEL ARCHITECTURE
MIMO filters. Formally, the more expressive GDN architecture with MIMO (Multi-Input Multi- Output) filters is constructed as follows. At layer le of the neural network, we take three-way tensor A CC and produce A++1 E RCxNNN where C' is the common number of input and output channels. The assumption of having common number of input and output channels can be relaxed, as we argue below. By defining multiplication between tensors T, B E Nx as batched matrix multiplication: (TB] j.::: T B j.... and tensor-vector addition and multiplication as T+v = T1 11 and [uT],.. Uy j.:: respectively for a E RC, all operations extend naturally.
Using these definitions, the j-th output slice of layer ls is
A ReLUia. As + B., (AoA: + A₂ + Yo -T,11",
(7)
where ... represents the mean reduction ax B, E gCxC T E RCC We now take e := {a. 3, 7, T} for a total of C' x (3C + 1) trainable parameters.
the filtered input channels and the parameters
14

---

Under review as a conference paper at ICLR 2022
We typically have single prior matrix A [0] and are interested in predicting single adjacency matrix Ag. Accordingly, we construct new tensor prior A(0 == A[]]] E cCxNVN and (arbitrarilly designate the first output channel as our prediction A, A(Ao; θ = [A++]]
We can also allow each layer to learn a decoupled MIMO filter, with its own set of parameters mapping from C input channels C output channels. the notation suggests, C and Cut need not be equal. Layer & now has its own set of parameters @ (a Bh 7x, T"), where
a ",,8,, > E RR x and Th E R_"" for total of C (3C 1) trainable parameters. The tensor operations mapping inputs to outputs remains basically unchanged with respect to (7) except that the filter coefficients will depend on
Layer k
1
j
C
in
MIMO filter
A
k+1
[A
[A
Figure 3: MIMO Filter: Layer è takes a tensor A NNN and outputs tensor A C XNNN The i-th slice (As]ar called the input channel and (Asti]iaa is called the j-th output channel.
Processing at generic layer k is depicted in Figure Output channel j will use at B Yi E CC and r R4 to filter all input channels E {1. C.....-Chh C..., which are collected in the input tensor A E R xNxN This produces a tensor stacked filtered input channels E R x xNx After setting the diagonal elements of all matrix slices in this tensor 0, then perform mean reduction edgewise (over the first mode/dimension) of this tensor, producing single N x N matrix. We then apply two pointwise/elementtiss operations on this matrix: (i) subtract 7 (this would be the 'bias' term in CNNs); and (ii) apply point-wise nonlinearity (ReLU), This produces an N x N activation stored in the j-th output channel. Doing so for all output channels j {1, ,.k.".
produces a tensor A E RC NNxN
Layer output normalization and zeroing diagonal. The steps not shown in the main text are the normalization steps, a practical issue, and the setting of the diagonal elements to be 0, a projection onto the set A of allowable adjacency matrices. Define U = A& + +
RNNN the j-th slice in the intermediate tensor U R C...... N used in the filtering of Ag- Normalization is performed by dividing each ma- trix slice of U by by the maximum magnitude element in that respective slice: U / max U....--
t A + 3.
Multiple normalization metries were tried on the denominator, including the 99th percentile of all values in U.... the Frobenius norm || Ir, among others. None seemed to work as well as the maximum magnitude element, which has the additional advantage of guaranteeing entries to be in [0, 1] (after ReLU), which matches nicely with: (i) adjacency matrices of unweighted graphs; and (ii) makes it easy normalize edge weights of dataset of adjacencies: simply scale them to (0, 1).
15

---

Under review as a conference paper at ICLR 2022
In summary, the full procedure to produce [As+1]sa;; is as follows:
J = e Ak + 3 (AoAr
+ A,Ao) + +7 A5
JA: U Jap (11 -
force diagonal elements
3 U Ban/ max( U Bma))
normalize entries per slice to be in [-1, 1]
[Ast1jja ReLU(U, 7/))
By normalizing in this way, guarantee the intermediate matrix U f : has entries [-1, 1] (before the ReLU). This plays two important roles. The first one has to do with training stability and to appreciate this point consider what could happen no normalization of J,,,: are orders of magnitude larger than entries of Ul...- This can cause the model to push Ty >> 7f. leading training instabilities and/or lack of convergence. The second point relates to interpretability of т. Indeed, the proposed normalization allows us to interpret the learned values -k R on similar scale. All the tresholds must be in [0. 1] because: (i) anything above will make the output all 0; and (ii) we constrain it to be non-negative. In fact we can now plot all values (from all layers) against one another, and using the same scale ((0, 1) interpret if particular is promoting lot of sparsity in the output (r close to 1) or not (7 close to 0), by examining its magnitude.
used. Suppose the entries
A.6 GRADIENT USED IN PROXIMAL GRADIENT ITERATIONS
Here give mathematical details in the calculation of the gradient (A) of the component func- in the objective function of. Let A, Ao be symmetric N N matrices and recall the graph filter ((A) the notation). Then
tion g(A) = 111 Ao
EK A (we drop the dependency in simply
1 V VA, Ao Ao
1 V
H(A)II
V Tr ( AoH(A) H(A)Ao (A)) + 1
TA
( (A
Σ hR
A
AoA (T
k-1
= Σ hi
1 A Ak-r-1Aok AoA' +
1 +AH((A)
k=
1=0
= [h, Ao + h2 (AA0 + AoA) + h2 Ao + (0oA+AAA)) +...]
+ (A),
where in arriving the second equality we relied on the eyclic property of the trace, and (A) matrix polynomial of order 2K- - 1.
Note that in the context of the GDN model, powers of A will lead to complex optimization land- scapes, and thus unstable training. We thus opt to drop the higher-order terms and work with first-order approximation of Vg, namely
(g(A) R A1 h2 + AAo) + (2hgh2 + A2)
A.7 NOTES ON THE EXPERIMENTAL SETUP
Synthetic graphs. For the experiments presented in Table 1 the synthetic graphs of size N 68 are drawn from random graph models with the following parameters
Random geometric graphs (RG): d 2, r 0.56.
Erdös-Rényi (ER): p .56.
16

---

Under review as a conference paper at ICLR 2022
Barabási-Alber (BA): m 15
When sampling graphs construct the datasets, we reject any samples which are not connected or have sparsity outside of a given range. For RG and ER, that range is [0.5, 0.6], while in BA the range [0.3, 0.4]. This is an attempt to make the RG and ER graphs similar to the brain SC graphs, which have an average sparsity of 0.56, and all SCs are in sparsity range [0.5, 0.6). Due to the sampling procedure of BA, is not possible to produce graph in this sparsity range, so we lowered the range sightly. We thus take SCs to be an SBM-like ensemble and avoid repetitive experiment with randomly drawn SBM graphs.
Note that the sparsity ranges define the performance of the most naive of predictors: all ones/zeros. In the RG/BA/SC, an all ones predictor achieves an average error of 44% = 1-(average graph sparsity). In the BAs, naive all zeros predictor achieves 35% 1 laverre graph sparsity). This is useful to keep in mind when interpreting the results in Table
Pseudo-syntheties. The Pyetho-Synthetic datasets are those in which we diffuse synthetic signals over SCs from the HCP-YA YA dataset. This is an ideal setting to test the GDN models: we have weighted graphs to perform edge-regression that are true to our modeling assumptions. Note that SCs have a strong community- structure, corresponding dominantly to the left and right hemispheres as well as subnetworks which have high degree of connection, e.g. the Occipital Lobe which has 0.96 sparsity- almost fully connected while the full brain network has sparsity of 0.56.
(the others unweighted). while having Ao's
Error and MSE of the baselines in [ The edge weights returned by the baselines can be very small/large in magnitude and perform poorly when used directly in the regression task. We thus also provide scaling parameter, tuned during the hyperparameter search, which provides approximately an order of magnitude improvement in MSE in GLASSO and halved the MSE in Spectral Templates and Network Deconvolution. In link- ankerredctiion we also tune hard thresholding parameter on top of each method to clean up noisy outputs from the baseline, only it improved their performance (it does). For complete details on the baseline implementation, see A.8
Size generalization. Something to note is that we do not tune the threshold (found during training on the small N = 68 graphs) on the larger graphs. We go straight from training to testing on the larger domains. Tuning the threshold using a validation set (of larger graphs) would represent an easier problem. The model domains for any form of training/tuning.
point, or in any way, is introduced to the data in the larger size
We decide to use the covariance matrix in this experiment, opposed to the sample covariance matrix, as our Ao's. This is for the simple reason that it would he difficult to control the snr with respect to generalization error and would be secondary the main thrust of the experiment. When run with number of signals proportional to graph size, we see quite a similar trend, but due to time constraints, these results are not presented herein, but is apt for follow up work.
HCP data. HCP-YA provides up to 4 resting state fMRI scanning sessions for each subject, each lasting 15 minutes. We use the fMRI data which has been processed by the minimal processing pipeline Van Essen et al., 2013). For every subject, after pre- pre-processing the time series data to be zero mean, we concatenate all available time-series together and compute the sample covariance matrix (which is what as used are Ao in the brain data experiment 5.2).
Due to expected homogeneity in SCs across healthy population, information about the SC in the test set could be leveraged from the SCs in the training set. In plainer terms, the average SC in the training set is an effective predictor of SCs in the test set. In our experiments, we take random split of the 1063 SCs into 913/50/100 training/validationnesst sets, and report how much we improve upon this predictor.
Raw data available from http://wwwww..a.c....o.omoo whw.aaccwoccccocc.....accctttyyp hwwp://ppyyyyogaaaaddidlvvveeeer
Co-location and social networks among high school students. The Thiers dataset (Génois & Barrat 2018) followed students in a French high school in 2013 for 5 days, recording their inter- actions based on physical proximity (co-location) using wearable sensors as well as investigating social networks between students via survey. The co-location study traced 327 students, while subset of such students filled out the surveys (156). We thus only consider the 156 students who have participated in both studies. The co-location data is sequence of time intervals, each interval
17

---

Under review as a conference paper at ICLR 2022
Parietal
Frontal
Occipital
Temporal
Unspecified
Figure 4: The four lobes in the brains cortex.
lists which students were within a physical proximity to one another such interval. To construct the co-location network, we let vertices represent students and assign the weight on edge between student and student j to represent the (possibly 0) number of times over the 5 day period the two such students were in close proximity with one another. The social network is the Facebook graph between students: vertex and vertex j have an unweighted edge between them in the social network student and student j have are friends in Facebook. Thus we now have co-location network to.t and a social network A /.total- To construct dataset of graph pairs T {Ao (4) Ar, (9) 7000 li=1
we draw random subsets of N = 120 vertices (students). For each vertex subset, we construct a sin- gle graph pair by restricting the vertex set in each network to the sampled vertices, and removing all edges which attach to any node not in the subset. If either of the resulting graph pairs not connected, the sample is not included.
The performance of the baselines on such dataset is follows: Threshold (10.2 + 1.8e-2%) ND (10.6 = 1.9e-2%), GLASSO (NA could not converge for any of the a values tested), SpecTemps (10.7 + 6.9c-2%)
A.8 BASELINES
In the broad context of network topology identification, recent latent graph inference approaches such as DGCNN (Wang al. 2019), DGM (Kazi et al. 2020 NRI (Kipf et al.] 2018). or PGN (Veličković et al. 2020 have been shown effective in obtaining better task-driven represen- tations of relational data for machine learning applications, to learn interactions among coupled dynamical systems. However, because the proposed GDN layer does not operate over node features, none of these state-of-the-art methods are appropriate for tackling the novel network deconvolution problem we are dealing with here. Hence, for the numerical evaluation of GDNs we chose the most relevant baseline models that we outline in Section and further describe in the sequel.
We were as fair as possible in the comparison of GDNs to baseline models. All baselines were optimized minimize generalization error, which is what presented in Table T Many baseline methods aim to predict sparse graphs on their own, yet many fail to bring edge values fully to zero. We thus provide a threshold, tuned for generalization error using a validation set, on top of each method only if it improved the performance of the method in link-prediction. The edge weights returned by the baselines can be very small/large in magnitude and perform poorly when used directly in the the regression task. We thus also provide scaling parameter, tuned during the hyperparameter search, which provides approximately an order of magnitude improvement MSE for GLASSO and halved the MSE for Spectral Templates and Network Deconvolution.
18

---

Under review as a conference paper at ICLR 2022
Hard Thresholding (Threshold). The hard thresholding model consists of single parameter T, and generates graph predictions as follows
A - [[Ao
where [[-)} is an indicator function, and i denotes entry-wise inequality. For the synthetic exper- iments carried out in Section 5.1 to learn the structure of signals generated via network diffusion, Ao is either a covariance matrix or a correlation matrix. We tried both choices in our experiments, and reported the one that performed best in Table [
Graphical Lasso (GLASSO). GLASSO is approach for Gaussian graphical model selec- tion (Yuan Lin 2007| Friedman et al, 2008). In the context of the first application domain in Section 3 we will henceforth assume zero-mean graph signal æ (0, Ex). The goal is to estimate (conditional independence) graph structure encoded in the entries of the precision matrix
+ = Σn' To this end, given an empirical covariance matrix Ao := Σn estimated from ob- served signal realizations, GLASSO regularizes the maximum-likelihood estimator of O with the sparsity-promoting & norm, yielding the convex problem
① E arg max { log det θ trace E - 0111 0
(8)
We found that taking the entry-wiss absolute value of the GLASSO estimator improved its perfor- mance, and so we include that in the model before passing it through a bard-thresholding operator
ÅL - = }
One has to tune the hyperparameters a and r for link auk-prediction (and third, the scaling parameter described below, for edge- regression).
We used the sklearn GLASSO implementation found here: httpss:/eeiktttlearrz org/
.htll It is important to note that we not use the typical cross- validation procedure seen with GLASSO. Typically, GLASSO is used in unsupervised applications with only one graph being predicted from 8 observations. In our application, we are predicting many graphs, each with s observations. Thus the typical procedure of choosing using the log- likelihood [the non-regularized part of the GLASSO objective in (8)] over splits of the observed signals, not splits of the training set, results in worse performance (and different a for each graph). This is not surprising: exposing the training procedure to labeled data allows it to optimize for generalization. We are judging the models on their ability generalize to unseen graphs, and thus the typical procedure would provide unfair advantage to our model. While we tried both sample covariance and sample correlation matrices as Ao. we found that we needed the normalization that the sample correlation provides, along with an additional scaling by the maximum magnitude eigenvalue, in order to achieve numerical stability. GLASSO can take a good amount of time run, and so we limited the validaiton and test set sizes to even 100/100 split. With only 2 to 3 hyperparameters to tune, we found this was sufficient (no significant differences between validation and test performance in all runs, and when testing on larger graph sizes, difference in generalization performance).
stable/moduless www.eateeereeeeee sklearn. covar ance, www.gaaaaahhhaapaee
Network Deconvolution (ND). The Network Deconvolution approach is "a general method for inferring direct effects from an observed correlation matrix containing both direct and indirect ef- fects" (Feizi et al.] 2013). Network Deconvolution follows three steps: linear scaling to ensure all eigenvalues X; of Ao fall in the interval X; [-1, digenddccomposition of the scaled Ao Vdiag(A)V and deconvolution by applying f())) - to all eigenvalues. We then
construct our prediction as A, := V Vdiag(((A)))V In (Feizi et al. 2013), it is recommended a Pearson correlation matrix be constructed, which we followed. We applied an extra hard thresh- olding on the output, tuned for best generalization error, further increase performance. For each result shown 500 graphs were used in the hyperparameter search and 500 were used for testing.
Spectral Templates (SpecTemp). The SpecTemp method consists of a two-step process whereby one: (i) first leverages the model [ to estimate the graph eigenvectors V from those of Ao (the cigenvectors of A, and Ao coincide); and (ii) combine V with priori information about G (here sparsity) and feasibility constraints on A to obtain the optimal eigenvalues of A, = VT..
19

---

Under review as a conference paper at ICLR 2022
The second step entails solving the convex optimization problem
A (c) == argmin ||A||
{A.X]
s. A Vdiag(A) 11 <, A1 = 1, SEA
We first perform binary search on E R+ over the interval [0 to find Cmin. which is the smallest value which allows a feasible solution to ( With Emin hand, we now run an iteratively (I henceforth denotes iterations) re- re-weighted mn-or minimization problem with the aim of further pushing small edge weights to 0 (thus refining the graph estimate). Defining the weight matrix 211"
W. : A 17-1/+8111 E I where 7, d R4 appropriately chosen positive constants and A = A' (4mmn), we solve sequence / = 1,..., of weighted -norrm minimization problems
4 argmin W A| (A.A]
(10)
s. to | Vdiag( V min: A1 A A
If any of these problems is infeasible, then A; is returned where E {0,1,...,TT) is the last
successfully obtained solution.
Finally, threshold is chosen with a validation set map the output binary decision over edges, namely
A. 2
We solve the aforementioned optimization problems using MOSEK solvers in CVXPY. Solving such convex optimization problems can very computationally expensive/slow, and because there only two hyperparameters, 100 graphs were used in the validation set, and 100 in the test set.
Least Squares plus Non-convex Optimization (LSOpt). LSOpt consists of first estimating the polynomial coefficients in ( via least-squares (LS) regression, and then using the found coefficients in the optimization of B to recover the graph Az. Due the collinearity between higher order matrix powers, ridge regression can be used in the estimation of the polynomial coefficients. If the true order K of the polynomial is not known ahead of time, one can allow h R and add an additional é fo-m regularization for the sake of model-order selection. With h in hand, optimize 3), non-convex problem due to the higher order powers of A, using Adam with a learning rate of 0.01 and validation set of size 50 to tune A.
We start with the most favorable setup, using the true in the optimization of (3). skipping the LS estimation step. Even in such a favorable setup the results were not in general competitive with GDN predictions, and so instead of further degrading performance by estimating h, we report these optimistic estimates of generalization eтror.
A.9 SOURCE CODE AND CONFIGURATION
Code has been made available in a zipped directory with the submission. Refer to the README for instructions configuring system
the code. We rely PyTorch heavily and use Conda to make our system as hardwarre-nndeenddaa as possible. GPUs were used to train the larger GDNs, which available to use for free Google Colab. Development was done Mac and Linux (Ubuntu) systems, and not tested on Windows machines. The processed brain data was too large to include with the code, but is available upon request.
20


Reviews:
[{"review_id": "ydmAnfBj5nC", "reviewer": "Reviewer_CCxm", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths:**\n\nThis 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.\n\n**Weaknesses:**\n\nHowever, there are multiple concerns on the modeling, the setting, and the evaluation.\n\n**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.\n\n**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?\n\nGoing 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.\n\n**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.\n\n**Minor comments:**\n\n- 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.\n\n- 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.\n\n---\n\n**After rebuttal**\n\nThis 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.\n", "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.", "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.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "htxUOPum08J", "reviewer": "Reviewer_ADij", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nThe 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.\nWeaknesses:\n(1) Some claims and descriptions are confusing, as listed below:\n1. 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].\n2. 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.\n3. 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.\n\n(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.\n(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:\n1. 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?\n2. In Sec 5, there's only one real dataset. Is this sufficient to prove the effectiveness of GDN in the general setting?\n\n-----\n[1] Wu, Zhenqin, et al. \"MoleculeNet: a benchmark for molecular machine learning.\" Chemical science 9.2 (2018): 513-530.\n[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.\n[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.\n", "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).\n", "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.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "WfNNNJ0-n_X", "reviewer": "Reviewer_9UsD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nUnfortunately 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.\n\nThe 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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "4Aa2u56u1x", "reviewer": "Reviewer_XnFE", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nOr 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.\n\n", "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.", "summary_of_the_review": "One fundamental question about the paper is not clearly stated.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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