Learning to Learn Graph Topologies
Authors: Xingyue Pu
Tianyue Cao
Xiaoyun Zhang
Xiaowen Dong
Siheng Chen
Venue: NeurIPS 2021 Poster (2021)
Keywords: topology inference
graph learning
algorithm unrolling
learning to optimise

Abstract: Learning a graph topology to reveal the underlying relationship between data entities plays an important role in various machine learning and data analysis tasks. Under the assumption that structured data vary smoothly over a graph, the problem can be formulated as a regularised convex optimisation over a positive semidefinite cone and solved by iterative algorithms. Classic methods require an explicit convex function to reflect generic topological priors, e.g. the $\ell_1$ penalty for enforcing sparsity, which limits the flexibility and expressiveness in learning rich topological structures. We propose to learn a mapping from node data to the graph structure based on the idea of learning to optimise (L2O). Specifically, our model first unrolls an iterative primal-dual splitting algorithm into a neural network. The key structural proximal projection is replaced with a variational autoencoder that refines the estimated graph with enhanced topological properties. The model is trained in an end-to-end fashion with pairs of node data and graph samples. Experiments on both synthetic and real-world data demonstrate that our model is more efficient than classic iterative algorithms in learning a graph with specific topological properties. 

Learning to Learn Graph Topologies
Xingyue Pu University of Oxford xpuêrobots. ac uk
Tianyue Cao Xiaoyun Zhang
Shanghai Jiao Tong University
{vanessa xiaoyun zhang) Os tu, edu.
Xiaowen Dong University of Oxford xdong@robots.om ox. ac uk
Siheng Chen"
Shanghai Jiao Tong University
sihenge@s jt.. edu.
Abstract
Learning graph topology reveal the underlying relationship between data entities plays important role in various machine learning and data analysis tasks. Under the assumption that structured data vary smoothly over a graph, the problem can be formulated as a regularised convex optimisation over a positive semidefinite cone and solved by iterative algorithms. Classic methods require explicit convex function reflect generie topological priors, e-g. the & penalty for enforcing sparsity, which limits the flexibility and expressiveness in learning rich topological structures. We propose to learn mapping from node data to the graph structure based on the idea of lcarning optimise (L20). Specifically, model first unrolls iterative primal-dual splitting algorithm into neural network. The key structural proximal projection is replaced with variational autoencoder that refines the estimated graph with enhanced topological properties. The model is trained in an end-to-end fashion with pairs of node data and graph samples. Experiments both synthetic and real-world data demonstrate that model is more efficient classic iterative algorithms learning a graph with specific topological properties.
1 Introduction
Graphs are an effective modelling language for revealing relational structure in high-diment digeediiensional complex domains and may assist in variety of machine learning tasks. However, in many practical scenarios an explicit graph structure may not be readily available or easy define. Graph learning aims at learning graph topology from observation on data entities and therefore an important problem studied in the literature.
Model-based graph lcarning from the perspectives of probabilistic graphical models [24] or graph signal processing 32
solves optimisation problem over the space of graph candidates whose objective function reflects the inductive graph-data interactions. The data are referred as to the obscrvations on nodes, node features or graph signals in litcrature. The convex objective function often contains graph-data fidelity term and structural regulariser. For example, by assuming that data follow multivariate Gaussian distribution, the graphical Lasso [2] maximises the regularised log likeliioood of the precision matrix which corresponds a conditional independence graph. Based on the convex formulation, the problem of learning an optimal graph can be solved by many iterative algorithms, such as proximal gradient descent [15] with convergence guarantees.
30 28
These classical graph learning approaches, despite being effective, share several common limita- tions. Firstly, handcrafted convex regularisers may not he expressive enough for representing the
"Correspondin author
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

(9) Unrolligg algorithm
(b) Tupological differmnce (TopaDiIVAEE)
Iterative Algorithm
Inittalisation: 10
Groaedtnch
for 1.... do Ial0 wff)
KL
7V (w (
sample
structure encoder
decoder
unvoling
destem
concat
hil
win
NITO
Figure 1: An illustration of the proposed framework.
rich topological and structural priors. In the literature, only a limited number of graph structural properties can be modelled explicitly using convex regularisers, e.g. the é penalty for enforcing sparsity. More complex structures such scale-free and small-world properties have been largely overlooked due to difficulty in imposing them via simple convex optimisation. Secondly, graph structural regularisers might not be differentiable despite being convex, which perplexed the design of optimisation algorithms. Thirdly, iterative algorithms might take long to converge, as the search space grows quadratically with the graph size. Fourthly, tuning penalty parameters in front of structural regularisers and the step size itcrative algorithms are laborious.
To address the above limitations, we propose novel functional learning framework to learn a mapping from node observations to the underlying graph topology with desired structural property. Our framework is inspired by the emerging field of learning to optimise (L20) [8 26). Specifically, shown in Figure [ we first unroll iterative algorithm for solving the aforementioned regularised graph learning objective.
further increase the flexibility and expressiveness, we design a topological
difference variational autoencoder (TopoDiftVAE) to replace the proximal projector of structural regularisation functions in the original iterative steps. We train the model in an end-to-end fashion with pairs of data and graphs that share the same structural properties. Once trained, the model be deployed to learn a graph topology that exhibits such structural properties.
The proposed method learns topological priors from graph samples, which are more expressive in learning structured graphs compared to traditional methods using analytic regularisers. Compared to deep neural networks, unrolling an iterative algorithm that is originally designed for graph learning problem introduces sensible inductive bias that makes model highly interpretable. We test the effectiveness and robustness of the proposed method in learning graphs with diverse topological structures on both synthetic and real-world data.
The main contributions are as follows. Firstly, we propose a novel and highly interpretable neural networks to Iearn a data-to-graph mapping based on algorithmic unrolling. Secondly, we propose effective TipoDif module that replaces the proximal operators of structural regularisers. To the best of knowledge, this constitutes the first attempt in addressing the difficult challenge of designing convex functions to represent complex topological priors, which in turn allows for improved ficxibility and expressiveness. Finally, the proposed method improves the accuracy of graph learning by 80% compared to traditional itcrative solvers.
2 Problem Formulation
Model-based graph learning Let = (V,E, E, W) be an undirected weighted graph, where V the node set with [V] m, E is the edge set and W is the weighted adjacency matrix whose ij-th entry embodies the similarity between node i and node j. The combinatorial graph Laplacian matrix defined as D W, where = diag(" (W1) a diagonal matrix of node degrees. In many scenarios, we have access to a structured data matrix, which is denoted as X = [x1, X2.... X.m] RmxP, where each column x, be considered signal on the graph G. The goal of graph learning infer such graph G that is fully represented by W from X. Specifically, we solve a generic optimisation problem
min tr TIXXXLXX LX) (LL).
2

---

where the first term is the so-called Laplacian quadratic form, measuring the variation of X on the graph, and (2(L) is convex regulariser on L to reflect structural priors Since W is symmetric, we introduce the vector of edge weights w E (R and reparameterise Eq. based on - E. Way x;llă = 2w Ty, y, where y E RT R. 1imm211/2,, is the haff-vcctorisation of the Euclidean distance matrix. Now, we optimise the objective w.t such that
min 2w y [[220) + 52 (w) + (2(WW).
where I is an indicator function such that Ie(w) 0 if C and Ie(w) = co otherwisc, and DD is a lincar operator that transforms w into the vector of node degrocs such that Dw = W1. The reparamcterisation reduees the dimension of scarch space by half and we do not need to take extra care of the positive semi semi-definiteness of L.
In 2. the regularisers 92 is split into f2 and 92 on edge weights and node degrees respectively. Both formulations can be connected to many previous works, where regularisers are mathematically handcrafted to reflect specific graph topologies. For example, the E fi-regularised likelikeldhood maximisation of the precision matrix with Laplacian constraints 2 [2] can be seen as a special case of E. where (2( = log det (L o² + A Eizz [Lyl-- The & norm on edge weights enforces the learned conditional independence graph to be sparse. The author in [16] considers the log- barrier on node degrees, i.e. (D2()) = -1 (og(Dw), ). to prevent the learned graph with isolated nodes.
Furthermore, 9 (w) = ||w|| is often added force the edge weights to be smooth [1]
Learning to learn graph topologies In many real- weal-world applications, the matheemaicaally-dsiieee topological priors in the above works might not be expressive enough. For one thing, many interesting priors are too complex to be abstracted as an explicit convex function, e.g. the small-world property [36]. Moreover, those constraints added prevent trivial solutions might conflict with the underlying structure. For example, the aforementioned log barrier may encourage many nodes with a large degree, which contradicts the power-law assumption in scale-free graphs. The penalty parameters, treated as part of regularisation, are manually appointed or tuned from inadequately granularity, which may exacerbate the lack of topological expressiveness. These motivate to directly learn the topological priors from graphs.
Formally, we aim at learning neural network Fo(-) that maps the data term y to a graph represen- tation w that share the same topological properties and hence belong to the same graph family g. With training pairs ((y,, w; we consider a supervised learning framework to obtain optimal Fō such that
0" arg argmin Bw w)),
(3)
where L(W, w) is loss surrogate between the estimation w Fy and the groundtruth. Onee trained, the optimal (-) implicitly carries topological priors and can be applicd to estimate graphs from new observations. Therefore, our framework promotes learning to learn a graph topology. In the next section, we claborate on the architecture of F- and the design of L(.,-).
3 Unrolled Networks with Topological Enhancement
In summary, the data-to-gran graph mapping Fo(() is modelled with unrolling layers (Section 3.1 inher-
ited from primal-dual splitting algorithm that originally proposed to solve the model-based graph
learning. We replace the proximal operator with a trainable variational autoencoder (i.e. TopoD- iffVAE) that refines the graph estimation with structural enhancement in Section 3.2 The overall network is trained in an end-to-end fashion with the loss function introduced in Section 3,3
3.1 Unrolling primal-dual iterative algorithm
Our model leverages the inductive bias from model- graph learning. Specifically, we consider special case the formulation in Eq. 2 such that
min 2w y + I (w220) (w) al log(Dw) + 3|
(4)
3

---

where (1( = 5] 2 and (2(W = -a1 [ow( both of which are mathematically handcrafted topological priors. To solve this optimisation problem, we consider a forward-backwatt forward primal-dual splitting algorithm (PDS) in Algorithm[[ [ The algorithm is specifically derived [[6]. In Algorithm [I] Step 3, and update the primal variable that corresponds to w, while Step 4, 6 and 8 update the dual variable in relation to node degrees. The forward steps are equivalent to gradient descent the primal variable (Step 3 and 7) and gradient ascent on the the dual variable (Step 4 and 8), both of which are derived from the differentiable terms 4 The hackward steps (Step and 6) are proximal projections that correspond to two non-differentiable topological regularisers, i.e. the non-negative constraints w and the log barrier on node degrees in Eg D. The detailed derivations are attached Appendix A.2 It should be note that norm that promotes sparsity is implicitly included, i.e. 2w y 2w yy A/2) + >/|w|| given w 2 0. We choose to unroll PDS as the main network architecture of Fo(-), since the separate update steps of primal and dual variables allow us to replace
from Algorithm 6 in [2n by the authors
of proximal operators that are derived from other priors.
Algorithm 1 PDS
Algorithm 2 Unrolling Net (1.2G)
Input: y. a and B.
Input: y. T, enhancement E [TREE, FALSE)
1: Initialisation: w()) = 0, v())= =
I: Initialisation: w( = 0, v =
2: while /w(t) w((-1)] > do
2: for = 0, 1,..,. ......T do
3: r(() =w(() (2/8w(t))++ +.y DT v(t))
(t) = w() 7 (2,3(0 (()) +2y +DDv(())
3:
4: rg -v(0) + 4Dw((1
4:
r2
(t) ((0 + Dw00
5: pl = prox,,,, (I(1)) = max(0,r( +
5: if enhancement (1) TRUE,
else.
Pi = prox, 7, (r(")) = max (0. r (
6: P2 = prox,,,,, (r, where
6:
P2 = prox,,.... .u (r22) where
(0)
(prox,,oon,, (12)); 22. 4407
(prox, (12));
2
7:
q = =pp - (2ppp + +2y + D P2
(1)
7:
q Pi
(t) (2)
1 2y + (TP!!)
8: q = P2 +DDp)
(t) (t)
(t)
8:
q = P2
(6) +110Dp("
9: ((+1) w(f) r(()) (8)
+ 41 (9)
9:
w [++1] = w (1) -r + qi
(1)
10: v(+1)- v(1) 12 + 92
(0
10: ((11)) = (()) r2 92
(8)
11: end while
11: end for
12: return w (T)
12: return (1)), (2)
The proposed unrolling network is summarised in Algorithm which unrolls the updating rules of Algorithn[]for for T times and is hypothetically equivalent to running the iteration steps for T times. In Algorithm 2 we consider two major substitutions to enable more flexible and expressive learning.
Firstly, we replace the hyperparameters a, 3 and the step size y in the PDS by layer wise trainable parameters (highlighted in blue in Algorithm 2 which can be updated through backpropagation. Note that we consider independent trainable parameters in each unrolling layer, we found it enhance the representation capacity and boost the performance compared to the shared unrolling scheme [14 (26).
Secondly, we provide a layer-wise optional replacement for the primal proximal operator in Step 5. When learning complex topological priors, trainable neural network, i.e. the TipoVA (highlighted in red in Algorithm 2) takes the place to enhance the learning ability. VopoDiffVAE will be defined in Section 3.2 It should be noted that such a replacement at every unrolling layer might lead to overly complex model that is hard to train and might suffer from overfitting. which depends on the graph size and number of training samples. Empirical results suggest TopoDiftVAE takes effects mostly on the last few layers. Comprehensibly. at first several layers, L2G quickly search near-optimal solution with the complete inductive bias from PDS, which provides a good initialisation for Tifo that further promotes the topological properties. In addition, we do not consider a trainable function to replace the proximal operator in Step 6 of Algorithm [ as it
4

---

projects dual variables that are associated to node degrees but do not draw a direct equality. It is thus difficult to find loss surrogate and network architecture to approximate such an association.
3.2 Topological difference variational autoencoder (TopoDittVAE)
The proximal operator in Step of Algorithm follows from $2 (w) in Eq. Intuitively, ideal regulariser Eq. + would be an indicator function 12 = (-)),, where G a space of graph sharing same topological properties. The consequent proximal operator projects w onto G. However, it is difficult to find such oracle function. To adaptively learn topological priors from graph samples and thus achieve better expressiveness in graph learning, we design a topological difference variational autoencoder (TopoDiffVAF) to replace the handcrafted proximal operators Step 5 of Algorithm
Intuitively, the goal is to learn a mapping between two graph domains X and y. The graph estimate after gradient descent step ri C X lacks topological properties while the graph estimate after this mapping p E y is enhanced with the topological properties that are embodied in the groundtruth w. e.g. graphs without and with the scale-free property. We thus consider conditional VAE such that P (r(") - w, where the latent variable z has implication of the topological difference
(1) and In Algorithm 2 Pi the estimate of the groundtruth w from P. When talk about the topological difference, we mainly refer to binary structure. This because edge weights might conflict with the topological structure, e.g. an extremely large edge weight of a node with only one neighbour in scale-free network. We want to find a continuous representation z for such discrete and combinatorial information that allows the backpropagration flow. A straightforward solution embed both graph structures with graph convolutions networks and compute the differences in the embedding space. Specifically, the encoder and decoder of the TopoDiftVAE P are designed as follows.
between ri
(9)
Encoder: Wc extract the binary adjacency matrix of r1 and w by setting the edge weights less than 1 to zero and those above 7) onc. Empirically, 1) is small value to exclude the noisy edge weights, c.g. 7 = 10-4, The binary adjacency matrix are denoted as A, and A.. respectively, Following [19, the approximate posterior qo (0(2))1 (e) w) modelled as Gaussian distribution whose mean μu and covariance Σ- = I are transformed from the topological difference between the embedding of A, and A such that
8 = fembl femb(( femb (A,) 2|r(") w ~ o2
(5a)
/A meam (8).
a= (0).
(5b)
where fmean and feo two multilayer perceptrons (MLPs). The embedding function fanb is 2-layer graph convolutional network followed by readout layer frentout that averages the node representation to obtain a graph representation, that is,
f femb () freadout (Au((d))) HH))
where A refers to either A, and A bg and H, are learnable parameters at the first and second convolution layer that are as the same in embedding A, and A 10 is the non-linear activation function. Node degrees d = A1 are taken as an input feature. This architecture is flexible to incorporate additional node features by simply replacing d with feature matrix F.
Latent variable sampling. We use Gaussian reparameterisation trick [19 to sample z such that z le + @ where e (O0 I). We also restrict to be a low-dimensional vector to prevent the model from ignoring the original input in the decoding step and degenerating into auto-encoder. Mcanwhile, the prior distribution of the latent variable is regularised to be close to a Gaussian prior z ~ AO, I) to avoid overfitting. We minimisc the KullbackLLeible divergence between go (z(r (t) w) and the prior p(z) during training as shown in Eq. 18.
Decoder: The decoder is trained to reconstruct the groundtruth graph representations w (the estimate is p(")) given the input (") and the latent code z that represents topological differences. Formally, we obtain an augmented graph estimation by concatenating r(0) and z and then feeding it into 2-layer
5

---

MLP Sdee such that
p = (CONCAT)) .2)).
3.3
An end-to-end training scheme
By stacking the unrolling module and TopoDiffVAE, we propose end-to-end training scheme to learn effective data-to-grape mapping Jo that minimises the loss from both modules such that
min Ew
|w(t) Ww
w
BLL (ao((laa w ( (V
(8)
where w(1) is the output of the t-th unrolling layer and (6) is the output of Step 3 in Algorithm 2 E (0, 1] is loss-discuunting factor added to reduce the contribution of the normalised mean squared error of the estimates from the first few layers. This similar the discounted cumulative loss introduced in [31]. The first term represents the graph reconstruction loss, while the second term is the KL regularisation term in the TopoDiffVAE modulc. When the tradc-off
3KL. 1, the VAE framework reduces to 8- VAE 77] that encourages disentanglement of latent factors z. The trainable parameters in the overall unrolling network Fo are
umrol), 0 DogoDEAV j. where Ounroll = (a ..... a (T)),, 1) 7,00) ...... g ,,10, .....: -1)] and O RopoliinvA includes the parameters in femb- Jmem- Soov and fax- The optimal mapping Já further used to learn graph topologies that are assumed to have the same structural properties as training graphs.
4 Related Works
Graph Learning. Broadly speaking there are two approaches to the problem of graph learning in the literature: model-based and learning- baand approaches. The model -based methods solve an regularised convex optimisation whose objective function reflects the inductive graph data interactions
and regularisation that enforces embody structural priors 2 25
13 23
33 [2
10, 16 51
They often rely on iterative algorithms which require specific designs, including proximal gradient descent [15], alternating direction method of multiplier (ADMM) 66. -corrdiate decent
methods [ and primal- splitting [16]. Our model unrolls primal-dual splitting as an inductive bias, and allows for regularisation on both the edge weights and node degrees.
Recently, learning-based methods have been proposed to introduce more flexibility to model structural priors in graph learning. GLAD 33 unrolls an alternating minimisation algorithm for solving an & regularised log-likel maximisation of the precision matrix. It also allows the hyperparameters of the & penalty term differ element- wisely, which further enhances the representation capacity. Our work differs from GLAD in that (1) we optimise over the space of weighted adjaceney matrices that contain non-negative constraints than over the space of precision matrices; (2) we unroll primal-dual splitting algorithm where the whole proximal projection step is replaced with TopoDifVVAE, while GLAD adds step of learning element-win wise hyperparameters. Furthermore, GLAD assumes that the precision matrices have a smallest cigenvalue of 1, which affects its accuracy on certain datascts. Deep-Graph [4] uses a CNN architecture to learn mapping from empirical covariance matrices to the binary graph structure. We will show in later scctions that lack of task-specifie inductive bias lcads an inferior performance in recovering structured graphs
Learning to optimise. Learning to optimisc (L20) combines the flexible data-driven lcarning procedure and interprctable rulc-based optimisation [8]. Algorithmic unrolling one main approach of L20 (6). Early development of unrolling was proposed to solve sparse and low-rank regularised problems and the main goal is to reduce the laborious itcrations of hand enginecring [44] [T] Another approach is Play and Plug that plugs pre-trained neural networks in replacement of certain update steps an itcrative algorithm 37j. Our framework is largely inspired by both approaches, and constitutes a first attempt in utilising L20 for the problem of graph learning.
5 Experiments
General settings. Random graphs are drawn from the Barabási-Albert (BA), Erdös-Rényi (ER), stochastic block model (SBM) and Sttts-Strogatz (WS) model to have scale-free, random,

---

Table 1: GMSE" in graph reconstruction
model/graph type
Scale-free (BA)
Random sparse (ER)
Community (SBM)
Small-world (WS)
Iterative algorithm:
ADMM
0.4094 + .0120
0.3547 = .01 2120
0.3168 + .0266
0.2214 + .0151
PDS
0.4033 + .0072
0.3799 = .0085
0.3111 + .0147
0,2180 + .0117
Learned to optimise:
GLADEL (NMSE)
1.1230 + .1756
1.1365 = .1549
1,4231 + .2625
0,9999 = .0001
Deep-graph
H
0.8423 + .0026
0,8179 = .2669
0.8931 + .0103
0.8498 + .0017
Proposed:
Recurrent Unrolling
0,3018 + .0080
0.2885 = .0755
0.2658 + .0108
0.2007 + .0081
Unrolling
0.1079 1 .0477
0.0898
.067
0.1199 1 .0064
0.1028 1 0073
L2G
0.0594 1 .0044
0.0746
.0042
0.0735 1 .0051
0.0513 1 .0060
For GL.AD, we report NMSE instead of GMSE
follow their original setting in 3T
GLAD sensitive to the choice of a² when generating samples (see Figure 2
GMSE may not favour Deep-graph as learns binary structures only (sce AUC in Table 2
community-lic and small-world structural properties respectively. The parameters of each network
model are chosen to yield an edge density in [0.05, 0.1]. Edge weights are drawn from a log-normal
distribution log( Way ~ (0, 0.1). The weighted adjacency matrix is set as W = (W + W) /2 enforce symmetry. We then generate graph-structured Gaussian samples (similar to 23) with
X NO K
1), K L + I'I, where o = 0.01.
The out-of-sample normalised mean squared error for graph recovery (GMSE) and area under the curve (AUC) are reported to evaluate the prediction of edge weights and the recovery of the binary graph structure. Specifically, GMSE = 1 >i= llw; w. //, interval are calculated from 64 test samples.
1.2 The mean and 95% confidence
We include the following baselines in the comparison: 1) primal-dual splitting algorithm [16] 21 that unrolled into neural network in our model; the iterative algorithm of ADMM (details in Appendix). For PDS and ADMM, we tune the hyperparameters on training set via grid scarch based on GMSE. For the statc-of-the of-thc--rt models that share the idca of learning to optimisc, we compare against 3) GLAD (31 and 4) Deep-graph 4 that are previously introduced in Section 4 Besides the proposed 5) learning to learn graph topologies (L2G) framework that minimiscs the objective in Eq. to obtain a data-to-graph mapping, we also evaluate the performance of ablation models without VipoVif in replacement of the proximal operator. This model is cquivalent to unrolling PDS dircetly while allowing parameters varying across the layers, which is referred to 6) Unrolling the following sections. We also consider 7) Recurrent Unrolling with shared parameters across
B(T-1) and (0)) -(1)-- (T-), The loss function for Unrolling and Recurrent Unrolling reduces the first term in Eq.(8). i.e. without
the layers, i.e (0) = (1) = ... (T)), 3300 = ((1)
the KL divergence term of DifVVAE More implementation details, e.g. model configurations and training settings, can be found in Appendix. We also release the code for implementation i
Ability to recover graph topologies with specific structures. We evaluate the accuracy of recov- cring groundtruth graphs of diffcrent structural propertics from synthetic data, We train an L2G for cach set of graph samples that are generated from one particular random graph modcl, and report GMSE between the groundtruth graphs and the graph estimates on test data in Table [
The proposed L2G reduces the GMSE by over 70% from the iterative baseline PDS on all types of graphs. Significant drops from PDS to Recurrent Unrolling and to Unrolling are witnessed. The scenario of recovering the scale-free networks sees biggest improvement on GMSE, as they are relatively hard to learn with handcrafted iterative rules. As shown in Figure 9 in Appendix, the power-law degree distribution associated with such networks is preserved in graph estimates from L22,, while PDS and Unrolling have difficulties to recognise small-degree nodes and nodes that are connected to many other nodes, respectivcly. PDS and Deep-Graph also fail the KS test, which
7

---

Table 2: Structural Metrics of recovered binary graph structure
metric/ model
groundrruth
PDS
Deep-Graph 4
Unrolling
L2G
Scale-free (BA):
AUC
0.934++0099 65.63%
0,513++0017 59.38%
0.993++.001
0,99::1.00 95.31 %
KS test score"
95.31%
93.75%
Community (SBM):
AUC
0.926
0.586:.021
0.989=t0022
0,9
community score
0,463#+002
+.02
0.343:+0006
0.458+0001
0,469=1003
Small-world (WS):
AUC
0,913 007
0.10
0,9844.005
0.991=.000
average shortest path
2.334:1.08
2.65611.200
1.136 008
2.328:1040
2.331 .041
clustering coefficient
0.5141.033 0.32311018
0.906 004
0,433:10116
0.382.1.014
KS score is the percentage of graphs whose degree sequence passes the Kolmogorov -Smirnov test for goodness of fit of power-law distribution, i... p-value 0.05.
measures how close the degrees of graph estimates follow power-law distribution (see a p-value less than 0.05 rejects the null hypothesis that the degrees follow a power-law distribution). We also test the models on SBM and WS graphs. Please see Appendix C.2 for analysis.
Comparisons with SOTA. GLAD and Deep-graph|f 4 are the few state-of-the- learning- based methods worth comparing to, but there are notable differences in their settings that affect experimental results. As discussed in Section the objective of GLAD[3I] is to learn the precision matrix where the diagonal entries are considered. The output of Deep-graph[[] is an undirected and unweighted (i.e. binary) graph structure. By comparison, the product of generic graph learning adopted in our work is a weighted adjacency matrix, where the diagonal entries are zeros due to no-self-loop convention.
For fair comparison, provide the following remarks. Firstly, we stick to their original loss function NMSE for training GLAD and reporting the performance on test data in Table The difference between GMSE and NMSE is that the latter considers the f2 loss on diagonal entrics of the precision matrix θ in GLAD Note that GMSE cquals NMSE when applicd to adjacency matrices which are the focus of the present paper. The experimental results show far inferior performance of GLAD if their NMSE is replaced with our GMSE
W will3 Wi
GMSE
NMSE (GLAD 31
(10)
71
Secondly, a potential limitation of GLAD 31 is that typ ically requires good conditioning of the precision matrix, i.c large 2² in Eq. Dp. On the other hand, in the graph signal processing and graph learning literature [I] [6]. smooth graph signals follow a Gaussian distribution where the precision matrix is taken as the graph Laplacian matrix, which is singular matrix with least one eigenvalue. large o² more likely to destroy the graph topological structure behind the data. Given that our objective is to learn a graph topology with non-negative edge weights we report results in Table Jusing small a = 0.01. In Fig- 2 we see that GLAD[BT] performs badly with small diagonal perturbation o², while our L2G method performs stably with different o². Admittedly, GLAD outper-
2.02
GLID (TP90)
120 JAMSST MMSF)
2.00
GMSE
233
235
1443 1954
1606
diagonel perturbation. of
Figure 2: GMSE v.s. o² for L2G/GLADD
forms L2G in terms of GMSE/NMSE under S o² S 10 in Figure 2 However, this could be due the fact that during training GLAD makes use of the groundtruth precision matrix which contains information of o², while L2G does not require and hence is not made aware of this information.
Thirdly, we generate another synthetic dataset with binary groundtruth graphs to have a fairer comparison with Deep-graph[4] [ and report the experimental results in Ta Appendix [C.T We follow the original setting in the paper for training and inference. For both binary graphs or weighted
8

---

Prrnd hukting
Loliiing pre
Lene ling propoct
2014 92220
Levoline yn
Unrouinng 200
548
Hi
Rerobiona furnslling
Hereitona Fureolling
Bervtions/ senolking
(0) compared with baselines
(b) different uncoll layers
(c) learning graphs with different sizes
Figure Convergence of number of iterations
graphs, posp-grap[[4 44 has achieved inferior performance, showing that CNN has less expressiveness than the inductive bias introduced by model-based graph learning.
Analysis of model behaviour. Figure Ba shows the proposed models require far less iterations to achieve big improvement on accuracy than the baseline models. Here, the number of iterations referred to as the number of unrolling layers
Algorithm 2 This means the proposed models can be used to learn a graph from data with significant saving in computation time once trained. In Figure 3bb we vary T in both L,G and Unrolling. With the same T, L2G with TopoDif replacing the proximal operator in Unrolling achieves lower GMSE each layer. This suggests that DifoVAA can help the unrolling algorithm to converge faster to a good solution (in this case a graph with desired structural properties).
In Figure 3c we train L2G and Unrolling on different sizes of graphs, where m is the number of nodes. A larger graph requires more iterations to converge in both models. but the requirement is less for L2G than for Unrolling. One advantage of applying Unrolling is that can be more easily transferred learn graph topology of different size. This is because the parameters Icarned in Unrolling are not size-dependent. Figure Be shows that with a large number of iterations (which will be costly to run), Unrolling can learn effective Sata-to-graph mapping with little sacrifice GMSE. However, L2G significantly outperforms Unrolling in terms of preserving topological properties, which are hard be reflected by GMSE. Unrolling might fail detecting edges that are important to structural characteristics. For example, as shown in Figure [e Beland [d in Appendix, rewired edges in WS graphs are missing from the results of Unrolling but successtully Icarned by L2G. In Appendix C we discuss these results well as scalability in more details.
6 Real-world applications
Many real-world graphs are found to have particular structural propertics. Random graph models can generate graph samples with these structural propertics. In this section, show that L2G can be pretrained on these random graph samples and then transferred real-world data learn a graph that automatically incorporates the structural priors present in training samples.
S&P 100 Stock Returns. We apply a pretrained L2G on SBM graphs to a financial dataset where we aim to recover the relationship between S&P 100 companies. We use the daily returns of stocks obtained from YahooFinance Figure ggives glives visualisation of the estimated graph adjacency matrix where the rows and columns are sorted by sectors. The heatmap clearly shows that two stocks in the same sectors are likely to behave similarly. Some connections between the companies across sectors are also detected, such as the link between CVS Health (38 CVS) and Walgreens Boosts Alliance (78 WBA). This intuitive as both are related health care. More details can be found in Appendix.
Assistant Diagnosis of Autism. L2G is pretrained with sparse ER graphs and then transferred learn the brain functional connectivity of Autism from soood-oxgenation--eeeell leveeeedeeeell (BOLD) time series. We collect data from the datascef) which contains 539 subjects with autism spectrum
9

---

Exite
Inferattoon Technoloy
100
100
801
Porth tare
5.5%
MIC
HET
400
0.00
1000
Consumer D Dipppaser
D9 14:3110
Servece
Figure 4: The learned graph adjacency matrix by L2G that reveals the relationship between S&P 100 companies. The rows and columns are sorted by sectors.
8.5
075
037
0.30
0.5
(a) Autistic group
(b) Control group
Figure 5: The connectivity of the 39 regions in brain estimated by L2G using 35 subjects
disorder and 573 typical controls. We extract BOLD time series from the fMRI images by using atlas with regions interest (35). Figure shows the learned connectivity of the regions using data from 35 subjects in the autistic group (Figure 5ab and 35 subjects in the control group (Figure 5b). The functional connectivity of two groups are apparently different, which provides reference for judging and analysing autism spectrum disorder. The difference also consistent with current studies showing the underconnectivity ASD [7]. The stability analysis the recovered graph structure is presented in Appendix, where our method is shown to be more stable than other methods.
7 Conclusion
this paper, we utilise technique of learning to optimise to learn graph topologies from node observations. Our method is able to learn a data-to-graph mapping, which leverages the inductive bias provided by classical iterative algorithm that solves structural-regularise minimisation. We further propose topological difference variational autoencoder to enhance the expressiveness and flexibility the structural regularisers. Limitations of the current method include its focus on unrolling an algorithm for learning undirected graph, and scalability to learning large-scale graphs. We leave these directions as future work.
Laplacian quadratic
10

---

Acknowledgements
X.P. and X.D. gratefully acknowledge support from the Oxford-Man Institute of Quantitative Finance. S.C gratefully acknowledges support from the National Natural Science Foundation of China under Grant 6217010074 and the Science and Technology Commission of Shanghai Municipal under Grant 2151 100900. The authors thank the anonymous reviewers for valuable feedback, and Ammar Mahran, Henry Kenlay and Yin-Cong Zhi for their helpful comments.
References
[1] Pierre Ablin, Thomas Morcau, Mathurin Massias, and Alexandre Gramfort. Learning step sizes for unfolded sparse coding. In Advances in Neural Information Processing Systems, volume 32, 2019.
[2] Onureena Banerjee. Laurent El Ghaoui, and Alexandre D' D'Aspremont. Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data. Journal of Machine Learning Research, 9:485-516, 2008
[3] Amir Beek. First-Order Methods in Optimization. SIAM-Society for Industrial and Applicd Mathematics, Philadelphia, PA, USA, 2017.
[4] Eugene Belilovsky, Kyle Kastner, Gael Varoquaux, and Matthew B. Blaschko. Learning discover sparse graphical models. In Proceedings of 34th International Conference on Machine Learning, volume 70, pages 440-448. PMLR, 06-11 Aug 2017.
[5] Peter Berger, Gabor Hannak, and Gerald Matz. Efficient graph learning from noisy and incomplete data. IEFE Transactions on Signal and Information Processing over Networks, 6: 100-1199 2020.
[6] Stephen Boyd, Neal Parikh, and Eric Chu. Distributed optimization and statistical learning via the alternating direction method of multipliers. Now Publishers Inc, 2011.
[7] Christopher P Burgess, Trina Higgins, Arka Pal, Loic Matthey, Nick Watters, Guillaume Des- jardins, and Alexander Lerchner. Understanding disentangling in 8-vac. In Proceedings of the 31th International Conference on Neural Information Processing Systems, 2017.
[8] Tianlong Chen, Xiaohan Chen, Wuyang Chen, Howard Heaton, Jialin Liu, Zhangyang Wang, and Wotao Yin. Learning to optimize: A primer and benchmark. arXiv preprint a03. 72828, 2021.
Alexandre D' Aspremont, Onurcena Banerjec, and Laurent El Ghaoui. First-order methods for sparse covariance selection. SIAM Journal on Matrix Analysis and Applications, 30(1):56-66, 2008.
[10] Zengde Deng and Anthony Man-Cho So. A Fast Proximal Point Algorithm for Generalized Graph Laplacian Learning. ICASSP 2020, IEEE International Conference Acoustics, Speech and Signal Processing Proceedings, pages 5425-5429, 2020.
[11] Xiaowen Dong, Dorina Thanou, Pascal Frossard, and Pierre Vandergheynst. Learning Laplacian Matrix in Smooth Graph Signal Representations. IEEE Trans. Signal Process., 64(23):6160- 6173, 2016.
[12] Hilmi E. Egilmez, Eduardo Pavez, and Antonio Ortega. Graph Learning from Data under Laplacian and Structural Constraints. IEFE Journal on Selected Topics Signal Processing, 1166)825--41, 2017.
[13] Jerome Friedman, Trevor Hastie, and Robert Tihshirani. Sparse inverse covariance estimation with the graphical lasso. 93):432-441, 2008
[14] Karol Gregor and Yann LeCun. Learning fast approximations of sparse coding. In Proceedings of the 27th international conference on international conference on machine learning, pages 2010.
11

---

[15] Dominique Guillot, Bala Rajaratnam, Benjamin T Rolfs, Arian Maleki, and Ian Wong. Iterative thresholding algorithm for sparse inverse covariance estimation. In Proceedings of the 25th International Conference on Neural Information Processing Systems, 2012.
[16] Vassilis Kalofolias. How to learn graph from smooth signals. Proc. 19th Int. Conf. Artif. Intell. Stat. AISTATS 2016, jan 2016.
[17] Rajesh K. Kana, Lauren E. Libero, and Marie S. Moore. Disrupted cortical connectivity theory as explanatory model for autism spectrum disorders. Physics of Life Reviews, 104):410-437, 2011.
[18] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015.
[19] Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In Proceedings of the 2nd International Conference on Learning Representations (ICLR), 2014.
[20] Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[21] Nikos Komodakis and Jean- Christophe Pesquet. Playing with duality: An overview of recent primal? dual approaches for solving large-scale optimization problems. JEEE Signal Processing Magazine, 32(6):31-54 54, 2015.
[22) Sandcep Kumar, Jiaxi Ying, Jose Vinicius de Miranda Cardoso, and Danicl Palomar, Structured graph learning via laplacian spectral constraints. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[23] Brenden M Lake and Joshua B Tenenbaum. Proceedings of the 32nd Annual Conference of the Cognitive Science Society, 2010.
Discovering Structure Learning Sparse Graphs.
[24] Steffen L Lauritzen. Graphical models. Clarendon Press, 1996.
[25] Zhaosong Lu. Adaptive first-order methods for general sparse inverse covariance selection. SIAM Journal on Matrix Analysis and Applications, 3 (44:2000-20 2009.
[26] Vishal Monga, Yuelong Li, and Yonina C Eldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. IEEE Signal Processing Magazine, 38(2):18-44 2021.
[27] Thomas Moreau and Joan Bruna. Understanding the learned iterative soft thresholding algo- rithm with matrix factorization. In Proceedings of the International Conference on Learning Representations (ICLR), 2017.
[28] Antonio Ortega, Pascal Frossard. Jelena Kovačević, José MF Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106(5):808- 828, 2018.
[29] JH Rick Chang, Chun-Liang Li, Barnabas Poczos, BVK Vijaya Kumar, and Aswin C Sankara- narayanan. One network to solve them all-solving linear inverse problems using deep projection models. In Proceedings of the IEEE International Conference on Computer Vision, pages 1888-5892 2017.
[30] Aliaksei Sandryhaila and José MF Moura. Discrete signal processing on graphs. IEEE transactions on signal processing, 61(7).1644-1656 2013.
[31] Harsh Shrivastava, Xinshi Chen, Binghong Chen, Guanghui Lan, Srinivas Aluru, Han Liu, and Le Song. Glad: Learning sparse graph recovery. In International Conference on Learning Representations, 2020.
[32] David Shuman, Sunil Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine, 3(30):83-98, 2013.
12

---

[33] Martin Slawski and Matthias Hein. Estimation of positive definite M-matrices and structure learning for attractive Gaussian Markov random fields. Linear Algebra and Its Applications, 473:145-179,, 2015.
[34] Pablo Sprechmann, Roee Litman, Tal Ben Yakar, Alexander M Bronstein, and Guillermo Sapiro. Supervised sparse analysis and synthesis operators. In Advances in Neural Information Processing Systems, volume 26, pages 908-916 2013.
[35] Gael Varoquaux, Alexandre Gramfort, Fabian Pedregosa, Vincent Michel, and Bertrand Thirion. Multi-subject dictionary learning segment atlas of brain spontameous activity. In Gáhor Székely and Horst K. Hahn, editors, Information Processing in Medical Imaging, pages 562-573, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
[36] Dunean Watts and Steven Strogatz. Collective dynamics of 'small- worldd-orrd'haha networks, nature. 393(6684):4404444 442, 1998.
[37] Kai Zhang, Wangmeng Zuo, Shuhang Gu, and Lci Zhang. Learning deep enn denoiscr prior for image restoration. In Proceedings of the IEEE conference on computer vision and pattem recognition, pages 3929-39299 3938, 2017.
13

---

Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See Abstract and Scction |
(b) Did you describe the limitations of your work? [Yes] See Section 7
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
(b) Did you include complete proofs of all theoretical results? [No]
If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL)? [Yes] See Section [
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they
were chosen)? [Yes] See Scction
(c) Did report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes] See Section we report confidence intervals.
(d) Did include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [Yes] See Section
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? (Ys]] See Section 5
(b) Did you mention the license of the assets? [Yes] See Section
(c) Did you include any new assets either in the supplemental material or as URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you' 're using/curating? [No]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No]
If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots. if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "yBwXkfYkCHN", "reviewer": "Reviewer_H66k", "summary": "This paper presents a novel method to estimate a graph topology between nodes directly from observations on nodes. In the field of graph signal processing and graphical models, it has been shown that we can estimate the graph topology from data observations at nodes when we can assume that data values at nodes vary smoothly over a graph, in other words when data values observed at node A would be statistically close to the data values observed at node B if node A and B are located in close positions at the entire graph.  \n\nThis assumption enables us to formulate the graph topology estimation as an optimization problem over the space of graph candidates. In this formulation, the objective function often is defined as a convex function having a form of \"graph-data fidelity term\" + \"structural regularization term\", which is then optimized by many iterative algorithms such as proximal gradient descent.\n\nThis paper aims to write these handcrafted convex regularizers by a differentiable module, and perform end-to-end learning in a more expressive and flexible manner. This can relax the strong assumption required for each specific regularization (such as L1 or L2 penalty), and extend the same framework flexibly to a wider range of graphs, scale-free graphs, or small-world graphs, which is usually difficult to explicitly write out the corresponding relevant regularization. \n\nA very interesting technical point is, the paper's approach is different from just replacing the regularizer with a neural network module, rather enroll the optimization steps of proximal gradient descent as an iterative procedure, and only critical parts are redesigned by neural networks. By doing this, the method can leverage the effective inductive bias developed in the field not to over-reformulate that target problem.\n\nThe experimental evaluations on both synthetic and real datasets demonstrate that this idea actually worked nicely, also showing clear superiority over existing approaches such as GLAD and DeepGraph.", "questions": "", "limitations": "", "rating": 7, "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": "This paper presents a very interesting and principled way to the network topology estimation from data on nodes as an optimization form of eq (1). Usually, we need to design the regularization term, Omega(L), in eq(1) by domain knowledge, but because we need to mathematically solve this optimization as convex optimization, and the options for any possible forms for Omega can be limited. Thus, the idea of enrolling the iterative procedure of optimization, and redesign some critical parts by a flexible neural network sounds quite interesting and promising. Also, it was nice to empirically see that this idea worked in their experimental evaluations.\n\nOverall I liked the idea, and but here are some questions and comments.\n\n- It is quite interesting that in the original enrolled description of proximal-dual splitting at Algorithm 1, only the proximal projection for the primal variable (line 5, Algorithm 1) was replaced by a VAE. The paper explained this motivation as \"We do not consider a trainable function to replace the proximal operator in Step 6 of Algorithm 1, as it projects dual variables that do not have a direct connection to graph structures.\"  \nHowever, if the dual variables correspond to the node degree, it should be also highly relevant to the graph structure. Did you actually try also replacing the dual variable with some NN and saw a poor performance or this is just an assumption?  \nOriginally both Omega_1 for primal and Omega_2 for dual come from the \"handcrafted structural priors\" as in line 112. So relaxing both of them sounds more natural at the first glance, given the purpose of the paper explained. The current form is a kind of hybrid mixture of \"handcrafted\" + \"neural\", and I'd like to understand this point more in detail. What does it really mean this leaving 2nd regularizer as it is? If we go neural for both of them, the behavior as a proximal gradient descent became chaotic...?\n\n- In Algorithm 1, why line 5 is gamma-free but line 6 is not? I suppose that line 5 should also come with gamma (somewhere around in \"max{0,r_1(t)}\"), but either way, we replace it a VAE, and doesn't matter...?\n\n- Related to the question above, I'd like to ask the scope of the proposed approach. We see that it worked for synthetic cases of many variations of random graphs such as BA, ER, SBM, and WS including many model forms of real-world graphs. But, the current form should be affected by \"the restriction\" of leaving the 2nd regularizer as is. How can this design policy affect the applicable scope of the proposed method? Either way, we need to have some assumptions for the relationship between graph topology and observations on nodes, and is there some guideline on what kinds of graphs can be estimated from observations on nodes by this proposed method?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It is appreciated to describe the limitations on the applicable scope of this proposed method.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "smMRTfPa56O", "reviewer": "Reviewer_8sof", "summary": "This paper aims to learn a graph from observations/signals on data entities. They propose a new method based on Learning to Optimise (L2O) whereby they map the node data to a graph. They argue that more complex phenomena like scale-free and small-world properties cannot simply be modelled or incorporated as priors in convex regularizers that are handcrafted. Instead, they propose an unrolling of a well-known iterative primal-dual splitting algorithm designed specifically for graph learning by a neural network, namely a topological difference variational autoencoder termed TopoDiffVAE. The proposed method improves over the results by a large margin compared with the baselines (iterative solvers for graph learning) in generating graphs from synthetic random graphs and real data.", "questions": "", "limitations": "", "rating": 8, "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:\n1. The paper is very well-written and easy to understand. I believe the idea is very interesting and novel and will help incorporate very interesting prior knowledge into graph learning which can represent very complex topological priors. The paper was indeed a pleasure to read and the technical details were clearly elucidated. \n\n2. The L20 method for learning graph structure from signal data proposed by the authors is extremely interesting and quite timely. Especially the idea of taking a well-known iterative optimization algorithm for graph learning and replacing it with an auto-encoder in the right places.\n\n3. Improves over the results by a large margin compared with the baselines in generating graphs from synthetic random graphs and real data.\n\n4. Clearly exhibits the ability to transfer the learnings on random graphs to real world settings\n\n\n-- Weaknesses:\n1. How is the T (number of iterations) in Algorithm 2 ascertained?\n\n2. On Lines 140-142, the authors claim that finding an indicator function where the proximal operator projects onto the space of graphs sharing similar properties is hard to come up with. I would assume that the space of graphs can easily be partitioned after having run them through some kind of a graph kernel (like a WL algorithm maybe?) and then it would just be a matter of defining what a “projection operator” in this graph kernel space might mean? Can this point possibly be expanded upon in the rebuttal?\n\n3. It would be interesting to theoretically analyze the computational complexity of the overhead in terms of the parameters introduced and needed for training in each unrolling step and the resulting scalability issues that arise due to this. I understand this has been mentioned as a future work by the authors, but I think this information would really help get a better understanding of this method.\n\n-- Minor Typos:\nLine 148: “abuse use of notation”.\n\nLine 157: w_x repeated.\n\nLine 160: w_x repeated.\n\nLine 210: ...eigenvalues of 1...\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hrs"}, "extra_text": {}}, {"review_id": "XvuQbGjwpNP", "reviewer": "Reviewer_aKqR", "summary": "This work studies how to learn the graph topology, the algorithm is developed based on learning to optimize (L2O), which first unrolls an iterative primal-dual splitting algorithm into a neural network, and then the network is stacked with a variantional autoencoder that refines the estimated graph with structure properties. Experiments on both synthetic and real-world data demonstrate the model is more efficient different iterative algorithms.", "questions": "", "limitations": "", "rating": 6, "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": "The reviewer finds the paper clearly written and easy to follow, but the originality and significance need to be further clarified.\n\nOne major concern of the reviewer is that the model is adopting the L2O, and it is not clear whether the effectiveness is due to the  L2O or due to the modeling and regularization proposed in this work. Note that it is known that L2O provides an advantage compared with ADMM and PDS compared in this work. \n\nWhile the paper indeed compared with other L2O algorithms including [29] and [3]. But the reviewer finds the performance of these two algorithms surprisingly unsatisfactory in Table 1, with GMSE close to 1, and is significantly worse than conventional learning algorithms including ADMM and PDS. This does not seem right to the reviewer. For example, as is pointed out by the author and can be seen from Figure 2, the performance of GLAD in fact outperforms the proposed L2G if sigma^2 is selected as 1 and improves with a larger sigma value. However, Figure 2 only shows sigma^2 from 1e-6 to 1 which is a very small range. it is likely that the performance will be stable if sigma improves even more and the performance will be stable if sigma>1, which is not shown in figure 2.  Similarly Comparing deep-graph which is designed for binary graph for a weighted synthetic graph is not a fair comparison. Hence, the experiments cannot convince the reviewer the proposed algorithm indeed outperform existing L2O-based algorithms since the parameter selection and the generation of the synthetic data might favor the current scheme.\n\nSimilar concerns exist for the experiments in Table 2, as the alternative L2O-based algorithm achieves worth result than the basic primal-dual splitting algorithm (PDS) which is surprising and may be due to an unfavorable selection of parameters.\n\nThe experiments on real-datasets seem promising, but given the concerns mentioned above, the reviewer is not very convinced by the comparison.\n\n\n-------\n\nPost rebuttal: The reviewer appreciates the authors for their efforts in addressing the questions and providing more thorough and convincing numerical results. The major concerns have been addressed and the score has been raised.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "QnXKTQ_vt3B", "reviewer": "Reviewer_nzro", "summary": "The authors study graph structure learning. The paper's main contribution is to improve the unrolling primal-dual iterative algorithm used to solve equation 4 in the paper. The authors propose a Topological difference variational autoencoder (TopoDiffVAE), which can learn a mapping between two graph domains where one graph domain consists of richer structure information. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Originality\nI think there is a lot of novelty in the paper. Though the paper is motivated by some recent works on L2O, according to the authors, it is a very early attempt to address the difficult challenge of designing convex functions to represent complex topological priors.\n \nQuality\n1. The authors show superior performance on a few synthetic data sets. According to table 1 and table 2, the L2G's prediction is very much to the ground truth graph structure than other methods. However, I did not see the authors comparing with baselines on real-world applications. For figure 4, can Graphical lasso/group graphical lasso obtain something similar? \n\n2. According to figure 3, can we conclude that the difference between unrolling and L2G (with TopoDiffVAE) can be tiny if we use more iterations? I think simply saying L2G converges faster does not make sense, as the computation price is much higher than the unrolling per iteration.\n\n3. I also have a slight concern about the scalability of the methods. Can the technique be applied to modeling a much larger graph (e.g., >=1000 nodes)?\n\n4. What are the tao values (introduced in equation 8) and your beta value (KL divergence term weight) in your experiments?\n \n\n\n\nClarity\n\na. Line 157, typo, w_x, and w_x.\n\nb. Actually, I am a bit confused about what is w_x and w_y. \nAccording to line 5 of Algorithm 2, TopoDiffVAE takes r_1^{t} as input. According to lines 177-178, it seems w_x is r_1^{t} after the gradient descent step, which is line 3 in algorithm 2.\n\nc. For w_y, is there a real ground truth w_y?\nOr, according to lines 177-178, it seems w_y takes the form of p_1^{t}? Should it be p_1^{t-1}? Or should it be p_1^{t} in line 5 of algorithm 1?\n\nd. Is there only one pair of w_x and w_y used to train the autoencoder in every of the T steps? I am not sure how the proposed approach would work, given a much larger graph.\n\n\nSignificance\nModeling graph structure is with sufficient interest in both the machine learning community and real-life application.\nThough I have a few concerns (it could be I missed something), but the idea of this paper seems to be interesting.\n\nPost rebuttal:  I read the authors's response. The authors have answered all my questions, clarified some small typos and addressed my concerns. Score increased.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

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