Interpretable Lightweight Transformer via Unrolling of Learned Graph Smoothness Priors
Authors: VIET HO TAM THUC DO
Parham Eftekhar
Seyed Alireza Hosseini
Gene Cheung
Philip Chou
Venue: NeurIPS 2024 poster (2024)
Keywords: Algorithm Unrolling
Graph Smoothness Prior
White-box Transformer
Primary area: optimization
TL;DR: We build interpretable and lightweight transformer-like neural networks by unrolling iterative optimization algorithms that minimize graph smoothness priors

Abstract: We build interpretable and lightweight transformer-like neural networks by unrolling iterative optimization algorithms that minimize graph smoothness priors---the quadratic graph Laplacian regularizer (GLR) and the $\ell_1$-norm graph total variation (GTV)---subject to an interpolation constraint. The crucial insight is that a normalized signal-dependent graph learning module amounts to a variant of the basic self-attention mechanism in conventional transformers. Unlike "black-box" transformers that require learning of large key, query and value matrices to compute scaled dot products as affinities and subsequent output embeddings, resulting in huge parameter sets, our unrolled networks employ shallow CNNs to learn low-dimensional features per node to establish pairwise Mahalanobis distances and construct sparse similarity graphs. At each layer, given a learned graph, the target interpolated signal is simply a low-pass filtered output derived from the minimization of an assumed graph smoothness prior, leading to a dramatic reduction in parameter count. Experiments for two image interpolation applications verify the restoration performance, parameter efficiency and robustness to covariate shift of our graph-based unrolled networks compared to conventional transformers.

Interpretable Lightweight Transformer via Unrolling of Learned Graph Smoothness Priors
Tam Thuc Do York University Toronto, Canada dtamthuc@yorku.co
Parham Eftekhar York University Toronto, Canada ef ettekhar@yrrk..c ca
Seyed Alireza Hosseini
York University Toronto, Canada
ahoseini @errniiyyouucccc
Gene Cheung
Philip A. Chou
York University
packet media Seattle, USA pachouβieee.. org
Toronto, Canada
genecdyorku.co ca
Abstract
We build interpretable and lightweight transformer-like neural networks by un- rolling iterative optimization algorithms that minimize graph smoothness priors- the quadratic graph Laplacian regularizer (GLR) and the f--norm graph total to interpolation constraint. The crucial insight is that a normalized signal-dependent graph learning module amounts to a variant of the basic self-attention mechanism in conventional transformers. Unlike "black-box" transformers that require learning of large key, query and value matrices to compute scaled dot products affinities and subsequent output embeddings, resulting in huge parameter sets, our unrolled networks employ shallow CNNs to learn low- dimensional features per node establish pairwise Mahalanobis distances and construct sparse similarity graphs. At each layer, given a learned graph, the target interpolated signal simply low-pass filtered output derived from the minimiza- tion of an assumed graph smoothness prior, leading to dramatic reduction in parameter count. Experiments for two image interpolation applications verify the restoration performance, parameter efficiency and robustness to covariate shift of our graph-based unrolled networks compared conventional transformers.
variation
Introduction
Focusing on the self-attention mechanism 1 as the basic building block-where the affinity between two input tokens computed transformed dot podduct-tranffommeet sets to achieve state-of-the- (SOTA) performance in wide range of signal prediction//lassifcattioo problems 3 outperforming convolutional neural nets (CNNs) and recurrent neural nets (RNNs). However, there are shortcomings: i) lack of mathematical interpretability to characterize general performance ii) requiring substantial training datasets train sizable parameters 12 and iii)
learn large parameter
fragility to covariate shif training and testing data have different distributions 11
Orthogonally, algorithm unrolling [14] implements iterations of a model-based algorithm sequence of neural layers to build feed-forward network, whose parameters can be learned end- to-end via back propaaarpnn from data. A classic example the unrolling of the iterative soft-
only 10, IT characterized the performance of single self attention layer and a shallow transformer, respectively. In contrast, we build transformer- like networks by unrolling graph-base based algorithms, so that each layer is interpretable by construction.
'hile works exist to analyze existing transformer architectures 5 d 7
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

thresholding algorithm (ISTA) in sparse coding into Learned ISTA (LISTA) [5]. Recently, [[6] showed that by unrolling an iterative algorithm minimizing sparse rate reduction (SRR) objective, wansformer-like deep neural nets that are 100% mathematically can lead to a family of "white-box" interpretable. Inspired by [6], in this work we also seek to build white-box transformers via algorithm unrolling, but from unique graph signal processing (GSP) perspective [17
Over the last decade and a half, GSP studies spectral analysis and processing of discrete signals on structured data kernels described by finite graphs, Specifically, by assuming that the sought signal smooth (low-pass) with respect to (w.r.t)) a particular graph, a plethora of graph-based restoration algorithms can be designed for practical applications, including image denoising [20], JPEG dequantization (2n,, interpolation (22). 3D point cloud denoising [23] (4) and super-resolutie
25
At the heart of GSP is the construction of a similarity graph that captures pairwise similarities
between signal samples on two connected nodes. We first demonstrate that ignal-dependen similarity graph learning with normalization is akin to affinity computation in the self-attention mechanism. Thus, our first contribution is to show that unrolling of a graph-based iterative algorithn with normalized graph learning results in an interpretable transformer-like feed-forward network.
Second, computation of a positive weight wi, exp(-d(i, j)) of an edge (i, j) connecting two graph nodes i and j often employs Mahalanobis distance d(i, (f: [5) MM - (;) between representative (e.g., CNN-computed) feature vectors f; and f,. where f., f, TR. reside in low- dimensional space 127 288 Hence, unlike a conventional transformer that requires large key and query matrices, K and Q to compute transformed dot products, the similarity graph learning module can be more parameter-efficient. Moreover, by adding a graph smoothness prior such as graph Laplacian regularizer (GLR) [8 20 or graph total variation (GTV) 29 30 31 in the optimization objective, once a graph G is learned, the target signal is simply computed as the low-pass filtered output derived from the minimization of the assumed graph smoothness prior. Thus, large value matrix V to compute output embeddings typical in transformer is also not needed. Our second contribution is to demonstrate that a lightweight transformer with fewer parameters can be built via unrolling of a graph-based based restoration algorithm with chosen graph signal smoothness prior.
Specifically, focusing on the signal interpolation problem, we first derive linear-time graph-based algorithms by minimizing GLR or GTV, via conjugate gradient (CG) (32 or a modern adaptation of alternative method of multipliers (ADMM) for sparse linear programming (SLP) 33 respectively. In each iteration, given a learned graph, each algorithm deploys a low-pass graph filter to interpolate the up- up-sampled observation vector into the target signal. We intersperse unrolled algorithm iterations with graph learning modules into compact and interpretable neural network. We demonstrate its restoration performance, parameter efficiency (3% of SOTA's parameters in one case), and robustness to covariate shift for two practical applications: image demosaicking, and image interpolation.
Vectors and matrices are written in bold lowercase and uppercase letters, respectively. The (i.j) element and the j-th column of matrix A are denoted by Ar, and a,. respectively. The i-th element in the vector a is denoted by a, The square identity matrix of rank N is denoted by IN. the M- M-by-N zero matrix is denoted by OM,N. and the vector of all ones / zeros of length N is denoted by 1y / ON, respectively. Operator || Ip denotes the E-p norm.
Notation:
2
Preliminaries
2.1 GSP Definitions
A graph G(N,E, W) is defined by a node set Net (l..... .N} and an edge set E of size | = M. where (i, E E meaas nodes i, A are connected with weight Wa, Wt, E R. In this paper, consider only positive graphs G with no self-loops, i.e., way 2 0, Vi,j. and Wi, = 0, Vi. We assume edges are undirected, and thus adjacency matrix W E NNNN is symmetric. The combinatorial graph Laplucian matrix is defined as L A D W E RNNN where D A (aaggWIn) is the degree matrix, and (iag(v) returns diagonal matrix with along its diagonal. L for positive graph G is provably positive semi remi-iefinite (PSD), i.e., all its cigenvalues X 's are non-negative [19]
'While there exist works on unrolling of graph-based algorithms (26). they typically assume a fixed graph and optimize other parameters. In contrast, the key point in our work is that the normalized graph learning module is akin to the basic self-attention mechanism in conventional transformers.

---

We define also the incidence matrix C = RMxN; each k-th row of C corresponds to the k-th edge (i.j) &, where Cg.₁ Wi.j Ck.j - -. and Cr, = O, AI * i.j. Since our assumed graph undirected, the polarities of Ck,; and Ck.y are arbitrary, as long as they are opposite.
2.2 Graph Laplacian Regularizer
Given a positive connected graph 9 with N nodes and M edges, first define smoothness of
signal x E N w.r.t. G using the graph Laplacian regularizer (GLR) [8] 20 as
| x x
Σ (KJ)EE
Wig(s; xz))
where L is combinatorial Laplacian matrix specifying graph G. GLR |I is non-negative for positive graph, and thus is suitable as a signal prior for minimization problems 20
2.3
Graph Total Variation
Instead of GLR we can alternatively define graph signal smoothness using graph total variation x1 for signal R.
(GTV) 29 30
| = ||Cx|]
(0)
Σ (i.))EE
12 - xzl
(2)
where (a) is true since G is positive. GTV is also non-nege non-negative for positive G, and has been used as a signal prior for restoration problems such as image deblurring [34]
Problem Formulation & Optimization using GLR
3.1 Problem Formulation
We first assume positive, sparse and connected graph G with N nodes and M edges specified by graph Laplacian matrix L. By sparse, mean that M is O(N) and not ((N2). By connected, mean that any node j can be traversed from any other node i. Given G, we first derive a linear-time iterative algorithm interpolate signal x by minimizing GLR given observed samples y. In Section 4 we derive an algorithm by minimizing GTV instead given y. In Section we unroll iterations of one of two derived algorithms into neural layers, together with strategically inserted graph learning modules, to construct graph-based lightweight transformer-like neural nets.
We first employ GLR [20 as the objective reconstruct R-V given partial observation y E R where < N. Denote by H E {0, K'N x.N a sampling matrix defined as
if node j is the i-th sample o.w.
Has
(3)
that picks out K samples from signal x. The optimization is thus
min x Lx, s.t. Hx =
(4)
where L NxN is graph Laplacian matrix corresponding positive graph G [19]. PSD L
implies that x Lx 2 0, Vx, and thus ( has a convex objective with a linear interpolation constraint.
3.2 Optimization
We solve (4) via a standard Lagrangian approach Lagrangian function f(x, (1)
[35 and write its corresponding unconstrained
f(x, 11)
Lx + p (Hx- y)
where μ E KKK is the Lagrange multiplier vector. To minimize fxx, (4) in (5), we take the derivative w.r.t. and μ separately and set them to zero, resulting the following linear system:
2L
ON.N y
(6)
H
OK.K
P
3

---

Given that the underlying graph G is positive and connected, coefficient matrix P is provably full-rank and thus invertible (see Appendix for proof). Hence. (6) has a unique solution x".
Suppose we index the sampled nodes S in x before the non-sampled nodes S, Lee, x = [xs: xs] Then H [Ix OK.N-K)- and the second block row in (6) implies xs y. Suppose write
L s Ls Ls, Ls.sl in blocks also. For the first block row in ( consider only the non-sampled rows:
1) Ax p
12L H
2(L Xs Lg,8xs) = ON-K
where (H') (1)s -N since the non-sampled rows of H (the non-sampled columns of H) are zeros. Thus. X5 can be computed via the following system of linear equations:
Ls. Xg L
(8)
where Lgg a symmetric, sparse, and provably positive definite (PD) matrix (see Appendix A.2 for proof). Thus, there exists unique solution x in (8)
Complexity: For notation simplicity, let C Lg.s. Linear system (8) can be solved efficiently using conjugate gradient (CG), an iterative descent algorithm with complexity Onnz L/ (C)) log(e)).
where nnz () is the number of non-zero entries matrix L, x(C) Amaz
Amin(( (C) is the condition number of C, Amax (C) and Amiu (C) are the respective largest and smallest eigenvalues of L. and the convergence threshold of the gradient search [32]. Because
sparse by graph construction (O(N) edges). L = Lg,s is also sparse, i.e., nnz = O(N). Assuming k(() can be reasonably lower-bounded for PD and is reasonably chosen, the complexity of solving ( using CG is (NN).
Interpretation: To elicit signal filtering interpretation from (6) assume for now that L is PD and thus invertible. Recall that the block matrix inversion formula [36] is
P-1 ([ A B )
= [
A A- A B(P/A)AA-- -PPA)( (P/A)
(9)
- -(P/AJCA-
where P/A = (D- - CA -1 'B)- is the Schur complement of block A of matrix P. Solution x" can thus be computed as:
x H HHL -H L ((L -1 L-
(10)
where L A ((L-))s) and (L (L-))s denotes the rows and columns of L- corresponding the sampled nodes. L is high-pass filter similar to Ls. Thus, we can interpret x" as a low-pass filtered output of up-sampled H L y- low-pass filter response r(A) A-1 where L VAVT. An)), ), is eigen-decomposible with frequencies A 's and Fourier modes vg
=
4 Problem Formulation & Optimization using GTV
4.1 Problem Formulation
Given positive connected graph G specified by incidence matrix C RxX and partial observation y, we now employ instead GTV as the objective to interpolate target signal x, resulting
min |Cx||1 s.t.
Hx y,
(11)
is a linear program (LP), since both the objective and the lone constraint are linear. Thus, while minimizing GLR leads to a linear system (6). minimizing GTV leads a linear program II
A combinatorial graph Laplacian matrix for positive graph with at least one additional positive self- is provably PD; proof in Appendix A.2

---

4.1.1 LP in Standard Form
First, we rewrite LP (11) in standard form as follows. Define upper-bound variable RM with pair of linear constraints z 2 +Cx. This enables linear objective 1,,2 for minimization problem (thus ensuring the upper bound is tight), i.e., ||Cx|] Second, we introduce non-negative slack variables qı q E I to convert inequality constraints z 2 +C to equality constraints Cx + and Cx q2. Thus, LP
11
can be rewritten as
IM
-C
(Iar MM.M)
z
0M OM y
min 12 2,x.9
Im
C
-
-0sMa IM)
0
02M
(12)
0K.M
0K,2M
q
where q [q13 q2] E RR2M
Optimization Algorithm
Because coefficient matrix A is sparse, 12 is a sparse linear program (SLP). We solve SLP
(12) efficiently by adopting an ADMM approach for SLP in 33
We first define a convex but
non-differentiable (non-smooth indicator function:
0
if 20 Vj
(
(13)
OC
O.W.
We next introduce auxiliary variable q E RR2.M and equality constraint q with single equality constraint as
We now rewrite
12
A
b q
min 1 12 g(9), S.t. 2.x.q.9
02M.M+N 1aM
X
=
(14)
q
We now rewrite 11 into an unconstrained version using the augmented Lagrangian method
z q
b q
b
min 1, + (()) + n ax..9.
B
B
(15)
2
2
where μ E B4M+K is Lagrange multiplier vector, and y > is scalar parameter. In the sequel, we write μ = Hyg pe pa me]. where pa Mb: pai Me E RM and μ E RK
4.2.1 Optimizing Main Variables
As typically done in ADMM, minimize the unconstrained objective (5) alternately as follows.
At iteration I, when q' and p are fixed, the optimization for z 2++ ++1 and (+1 becomes
Ta ( 2.x.q
B
x
b â
+
7
B
x
b
(16)
9
The solution to this convex and smooth quadratic optimization is system of linear equations,
++1
1
1M
27 (Hà p 2a # + 2 (qf + a
(17)
7
(CT+H
H)x**
H+
TT
(1's ui + uaa m!) L
"he
-
1 C
(ql
a
+
(18)
24
2
qi
1+1
(2) + 27 (m' - 44 + *
42
(2 1+1
Cx*t1)
(ms 2: +
(19)
27
See the Appendix A.3 for a derivation.
5

---

Linear system 18)
is solvable if the coefficient matrix L - L H'HH H. where L C C is a PSD graph Laplacian for a positive graph, invertible. See Appendix A.4 proof that C is PD and thus invertible.
Complexity: Linear system 18 again be solved efficiently using CG with complexity (nnzz(C) /C))) log(e)) [32]. Because C is sparse by graph construction (O(N) edges) and H is sparse by definition, L is also sparse, i.e. nnz(C) = O(N). Thus, assuming x(C) is also upper-bounded and is reasonably chosen, the complexity of solving (8) using CG O(N).
Interpretation: 18 can be interpreted as follows. H is the up-sampled version of observation Av]). an eigen-decomposible generalized Laplacian matrix Laplacian matrix C C plus self-loops of weight at sampled nodes due diagonal matrix H H, and like a graph Laplacian L without self-loops, can be interpreted
y. -= VAVT.
high-pass spectral filter 37. -- = - is thus a low-pass spectral filter with frequency response r(A) = A -- to interpolate output L H-' y. We interpret the remaining terms on the right-hand side of (18) as bias.
4.2.2 Optimizing Auxiliary Variable Fixing z'+1, x(+1 and t the optimization for q for 15 simplifies to
min (()) (42)) (q ++
q)
7 2
11q +1 - q
(20)
The solution for optimal qtth is jerm-by-tern thresholding:
{
q
1 + 1 Maa
if 9;
++1
+ H 20
Vi.
(21)
O.W.
See Appendix A.5 for derivation.
4.2.3 Updating Lagrange Multiplier
The Lagrange multiplier + can be updated in the usual manner an ADMM framework
38
b P q 1
11¹ +
B
x
(22)
Algorithm Complexity: Given that the number of iterations until ADMM convergence is not function of input size, it is (1). The most time-consuming step in each ADMM iteration is the solving of linear system (88 via CG in O(N). Thus, we conclude that solving SLP (12) using the aforementioned ADMM algorithm is O(N).
Algorithm Comparison:
Comparing the CG algorithm used solve linear system and the
ADMM algorithm developed to solve SI.P (12). we first observe that, given a similarity graph G specified by Laplacian incidence matrix, or C, both algorithms compute the interpolated signal x* as a low-pass filtered output of the up-sampled input H y in (IO) and (18). respectively. This is intuitive, given the assumed graph smoothness priors, GLR and GTV. We also that the ADMM algorithm is more intricate: in each iteration, the main variables are computed using CG, while the auxiliary variable is updated via ReLU-like thresholding, As result, the ADMM algorithm is more amenable to deep algorithm unrolling with better performance in general (see Section for details).
Graph Learning & Algorithm Unrolling
We now diseuss how similarity graph G can be learned from data, specified by graph Laplacian for GLR minimization 4 or incidence matrix C for GTV minimization (T]). so that the two proposed graph- interpolations can take place. Moreover, we show how normalized graph learning m performms comparable operations to the self-attention mechanism in conventional transformers. Thus, unrolling sequential pairs of graph-based iterative algorithm and graph learning module back-to-back leads to an interpretable "white-box"" transformer-lik neural net.
While estimating precision (graph Laplacian) matrix from an empirical covariance matrix computed from data is another graph learning approach [39 40 41, pursue Seature-based approach here 27 28).

---

5.1 Self-Attention Operator in Transformer
We first review the self-attention operator in a conventional transformer architecture, defined using a transformed dot product and softmax operation M. Specifically, first denote by E R an embedddig for token of N tokens. Affinity e(i, between tokens and j defined as the dot product between tmear-transformer embeddings Kx; and Qx,, where Q, K E Bx are the query and key matrices, respectively. Using softmax, a non-linear function that maps a vector of real numbers to vector of positive numbers that sum 1, attention weight as,j is computed as
exp(e(i,3))
04 E exp(e(i,()
e(i.)) = (Qx,) (Kx;).
(23)
Given self-attention weights 0z output embedding y; for token i is computed as Y1
V
(24)
where V E Fx is a value matrix. "Self-attention" here means that input embeddings are weighted to compute output embeddings. A transformer is thus sequence of sebbedding-to-mmeedeee mappings via different learned self-attention operations defined by Q, K and V matrices. Multi-head attention is possible when multiple query and key matrices Q(m) and ((m) are used to compute different attention weights (m))ss for the same input embeddings and Xj. and the output embedding (m)) y; is computed using an average of these multi-head attention weights di s.
5.2 Computation of Graph Edge Weights
Consider now how edge weights Wa,j 's can be computed from data to specify finite graph G 27 28 A low-dimensional feature vector f, E IR can be computed for each node from embedding X, _ via some (possibly non-linear) function = Fxx,), where typically D E. Edge weight Wi, between nodes i and j in a graph G can then be computed as
i. exp((d((is (-d(i,j)), d(i = -
(25)
where ([ is the squared Mahalanobis distance given PSD metric matrix M that quantifies the difference between nodes i and j. M edge weights [wa.}} compose a graph 9, specified by the Laplacian matrix for GLR minimization 4 and the incidence matrix MxN for GTV minimization
(11). Because Wa. 0, Ji constructed graph G is positive.
As a concrete example, consider bilateral filter (BF) weights commonly used image filtering 42 where feature f; contains the 2D grid location 1; and color intensity p: of pixel i, and metric M diag([1/o²; 1/ is a diagonal matrix with weights to specify the relative strength of the domain and range filters in BF. Because BF uses input pixel intensities pi 's to compute weighted output pixel intensities p: ss BF is dependen,,, similar to self-attention weights in transformers.
Edge weights are often first normalized before being used for filtering.
Normalization: For normalization, the symmetric normalized graph Laplacian L,, is defined as L, D DDI/LLD--- 1/22 so that the diagonal entries of L,, are all ones (assuming & is connected and positive) 18 We assume normalized L,, is used for Laplacian L in GLR minimization in (4)
Alternatively, the asymmetric random walk graph Laplacian L,w is defindd as L,w - L so that the sum of each row of Lrw equals to zero [88. Interpreting L,w Laplacian matrix to directed graph, the weight sum of edges leaving each node is one, i.e., Enian)e Wi,1 = Vi. To accomplish this, undirected edges weights {wis) are normalized to (wi,s) via
exp(-d(i.j)
wij
(26)
Emginee exp(-d(i,()
For GTV minimization in This results in normalized C E 22M X for directed graph with 2.M directed edges. Subsequently,
we normalize edge weights in incidence matrix C instead using (26).
7

---

back- Paack-propagation
loss function
0
3
Graph Learn
ADMM Block
ADMM Block
ADMM Block
ground
truth
output
a) Unrolling of ADMM algorithm
ADMM Layer
ADMM Leyer
ADMM layer
CG
x
x
(17)
Z
(21)
Q
(19)
(22)
1
main variables
aux, variable
Lag. multiplier
b) ADMM block
c) ADMM layer
Figure 1: Unrolling of GTV-based signal interpolation algorithm.
we define symmetric graph Laplacian L C C and generalized graph Laplacian - L H H. Note that ||C1]|| >i= Wi, 1| 0 after normalization, as expected for total variation constant signal 1. Further, note that while C is incidence matrix for directed graph with 2M edges, L is a graph Laplacian for an undirected graph with M edges. See Fig. 3 in Appendix (A.6 for an example of incidence matrix C, normalized incidence matrix C, and graph Laplacian matrix L.
Comparison to Self-Attentinn Operator:
We see how the definitions of edge weights (25 and
normalization (26) are similar to attention weights in (23) Specifically, interpreting the negalive squared Mahalanobis distance -d(i, j) as affinity e(i, normalized edge weights W.s. in (25) are
essentially the same attention weights oi,j in (23). There
subtle but important differences:
how non-negee non-negative Mahalanobis distance d(i,j) is computed in (25) using features f, = F(x:) and metric M versus how real-vat real-valued affinity is computed via transformed dot product in 23 and ii)
how the normalization term is computed in a one-hop neighborhood from node in 26 versus how it is computed using all N tokens in (3) The first difference conceptually means that edge weight based on Mahalanobis distance di., j) is symmetric (i.e., i = Wy.s), while attention weight as, is not. Both differences have crucial complexity implications, which we will revisit in the sequel.
Further, we note that, given graph G, the interpolated signal x is computed simply as low-pass filtered output of the up-sampled input observation H Hy via (TO) or (T8). depending the assumed graph smoothness prior, GLR or GTV, while the output embedding y; in a conventional transformer requires value matrix V in 24). This also has a complexity implication.
5.3 Deep Algorithm Unrolling
We unroll T sequential pairs of an iterative interpolation algorithm (GLR- or GTV-based) with graph learning module into an interpretable neural net. See Fig. IT for an illustration of the GTV- based algorithm unrolling, where the 1-th pair of ADMM block and the graph learning module have respective parameters O and 4 that are learned from back-propagation via a defined loss function. 4 include parameters used define feature function F(-) and metric matrix M (25). so the module can construet graph G specified by incidence matrix C++1 given signal x In implementation, we employ a shallow CNN to map a neighborhood of pixels centered at pixel to a low-dimensional feature f, with parameter size smaller than query and key matrices, Q and K, in conventional transformer. See Section 6. for details.
An ADMM block contains multiple ADMM layers that are unrolled iterations of the iterative ADMM algorithm deseribed in Section 4.2 Each ADMM layer updates the main variables x, z, q. auxiliary variable q. and Lagrange multiplier in turn using (17) to (22). ADMM weight parameter as well as parameters CG used to compute linear system (88). are learned via hack-propagation Specifically, two CG parameters a and 3 that represent step size and momentum during the conjugate gradient descent step are learned. See Appendix A.7 for details.

---

McM
Methad
PSNR
PSNR in d6
10
50
RST-B
28.01
22.7
19.34
15.03
UGTV UGUR RST-8 KSTV
uGLR
28.24
22.84
19.49
15.203
uGTV
28.31
22.89
19.56
15.38
Table 1:
Demosaicking performance noisy see- nario, where models are trained on noiseless datasct.
training data size in 1000
Figure 2: Demosaicking performance training size for different models.
6 Experiments
6.1 Experimental Setup
All models were developed using Python 3.11. We leveraged PyTorch to implement all models and trained them using NVIDIA GeForce RTX 2080 Ti. To train each learned model, we used the DIV2K dataset, which contains 800 and 100 high-resolution (HR) training and validation images, respectively, Since the images are HR, we patchified the images into small images and used only about 1 to 4% of the patches for training and validation sets. randomly sampled patches 64 x 64 pixels to train the model. To test model, used the McM 43 Kodak [44] and Urban 100 45 datasets, running each model on the whole images. See Appendix A.8 for more implementation details.
We tested model performance in two imaging applications: demosaicking and image interpolation. Demosaicking reconstructs full-color image (each pixel contains RGB colors) from a Bayer- patterned image, where each pixel location has only one of Red, Green, or Blue. Interpolation reconstructs empty pixels missing all three colors in an image. To create input images, for the first application, according to the Bayer pattern. For the second application, we directly down-sampled horizontally and vertically a HR image by factor of 2 to get the corresponding lowrresolution (LR) image without any anti-aliasing filtering. This is equivalent to keeping every four pixels in the HR image.
started from full-color image and then removed color components per pixel
6.2 Experimental Results
For the first application, evaluated our graph-based models against variants of RSTCANet [4). RSTCANet-B and RSTCANet-S (RST-B and RST-S for short), a SOTA framework that employs swin transformer architecture, Menon 47), Malvar 488 and bicubic interpolation. Menon [47] employs directional approach combined with an a posteriori decision, followed by an additional re- finement step. Malvar (8] uses linear filtering technique that incorporates inter-channel information across all channels for demosaicking.
The baselines for second application are MAIN 44], multi-scale deep learning framework for
image interpolation, SwinIR [50], and bicubic interpolation. SwinIR consists of three stages: shallow feature extraction, deep feature extraction, and final reconstruction stage; (50) for details. We
use Peak Signal-to-Noise Ratio (PSNR) and Structural Similarity Index Measure (SSIM) (1 as our
evaluation metries, common in image quality assessment.
McM
Kodak
Urban
Method
Params#f
PSNR
SSIM
PSNR
SSIM
PSNR
SSIM
Bicubic
29.01
0.8922
26.75
0.8299
22.95
0.7911
MAIN [49
10942977 904744
32.72
0.822
28.23
0.728
25.46
0.806
SwinIR-lightweight 50
32.24
0.9354
28.62
0.8794
25.08
0.8553
iGLR
28.53
0.8537
26.71
0.8005
22.87
0.7549
iGTV
30.41
0.887
28.05
0.832
24.26
0.7855
uGLR
319090 319115
33.31
0.9431
29.10
0.8870
25.94
0.8777
uGTV
33.36
0.9445
29.08
0.8888
26.12
0.8801
Table Interpolation performance for different models, trained on 10k sample dataset.

---

McM
Kodak
Urban 100
Method
Params#
PSNR
SSIM
PSNR
SSIM
PSNR
SSIM
Bilinear
29.71
0.9304
28.22
0.8898
24.18
0.8727
RST-B
46
931763
34.85
0.9543
38.75
0.9857
32.82
0.973
RST-S
46
3162211
35.84
0.961
39.81
0.9876
33.87
0.9776
Menon
47
32.68
0.9305
38.00
0.9819
31.87
0.966
Malvar
48
32.79
0.9357
34.17
0.9684
29.00
0,9482
iGLR
29.39
0.8954
27.50
0.8487
23.13
0.8406
iGTV
30.43
0.8902
28.66
0.8422
24.91
0.8114
uGLR
323410 323435
36.09
0.9650
37.88
0.9821
33.60
0.9772
uGTV
36.59
0.9665
39.11
0.9855
34.01
0.9792
Table 2: Demosaicking performance for different models, trained on 10k sample dataset.
Table shows the demosaicking performance for different models, where all models were trained on the same dataset and the same number of epochs (30), using subset of DIV2K dataset containing 10K of 64 x 64 patches. We observe that our unrolled GTV model (uGTV) achieved the best overall performance, while the unrolled GLR model (uGLR) and RST-S performed similarly. Both our models (uGTV and uGLR) performed better than RST-B while employing significantly fewer parameters. Crucially, we observe that although our normalized edge weight Wi, based on Mahalanobis distance is symmetric while the self-attention weight di,j is not (due to query and key matrices Q and K not being the same in general), the directionality in the self-attention mechanism does not appear to help improve performance of the conventional transformer further, at least for image interpolation tasks. The iterative GTV algorithm (iGTV) without parameter optimization performed the worst, demonstrating the importance of parameter learning.
In Fig. 2 we see the demosaicking performance of different models versus training data size. We that for small data size, our models (uGTV and uGLR) performed significantly better than RST-B. This is intuitive, since a model with more parameters requires more training data in general. See Appendix A.9 for example visual results.
Next, we test robustness to covariate shift by testing models trained on noiseless data using dataset artificially injected with Gaussian noise. T shows the demosaicking performance versus different noise variances. We observe that models outperformed RST-B in all noisy scenarios.
For image interpolation, we interploated LR image to a corresponding HR image. We trained all models the same dataset as the first application with the same number of epochs (15). Table shows that under the same training conditions, our proposed models (uGTV and uGLR) outperformed MAIN in interpolation performance in all three benchmark datasets by about 0.7 dB. Note that for this application we only interpolated Y-channel from YCbCr color space for PSNR computation. Similar to the first application, models achieved slight performance gain while employing drastically fewer parameters; specifically, uGTV employed only about 3% of the parameters in MAIN.
7 Conclusion
By unrolling iterative algorithms that minimize one of two graph smoothness priors E norm graph Laplacian regularizer (GLR) or --oormm graph total variation (GTV) ww build interpretable and light-weight transformer-lic neural nets for the signal interpolation problem. The key insight is that the normalized graph learning module is akin to the self-attention mechanism in conventional transformer architecture. Moreover, the interpolated signal each layer simply the low-pass filtered output derived from the assumed graph smoothness prior, eliminating the need for the value matrix. Experiments in two imaging applications show that interpolation results on par with SOTA can be achieved with a fraction of the parameters used in conventional transformers.
References
[1] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio, "Neural machine translation by jointly learning to align and translate," CORR, vol. abs/1409 hts/1409.0443.. 2014.
[2] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez,
Lukasz Kaiser, and Illia Polosukhin, "Attention is all you need," Advances in neural information
10

---

processing systems, vol. 30, 2017.
[3] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo, "Swin transformer: Hierarchical vision transformer using shifted windows," in 202/ IEEE/CVF International Conference on Computer Vision (ICCV), 2021, pp. 9992-10002.
[4] Alexander Kolesnikov, Alexey Dosovitskiy, Dirk Weissenborn, Georg Heigold, Jakob Uszkoreit, Lucas Beyer, Matthias Minderer, Mostafa Dehghani, Neil Houlsby. Sylvain Gelly, Thomas Unterthiner, and Xiaohua Zhai, "An image is worth 16x16 words: Transformers for image recognition scale," in The Ninth International Conference Learning Representations (ICLR), 2021.
[5] James Vuckovic, Aristide Baratin, and Rémi Tachet des Combes, "A mathematical theory of attention," " ArXiv, vol. abs/2007. 0.0766,, 2020.
[6]
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra, "Why are adaptive methods good for attention models?," in Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, Eds. 2020, vol. 33, pp. 15383-15393, Curran Associates, Inc.
[7] Charles Burton Snell, Ruiqi Zhong, Dan Klein, and Jacob Steinhardt, "Approximating how single head attention learns," ArXiv, vol. abs/2103.07601, 2021.
[8] Colin Wei, Yining Chen, and Tengyu Ma, "Statistically meaningful approximation: a case study on approximating turing machines with transformers," in Advances in Neural Information Processing Systems, S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, Eds. 2022, vol. 35, pp.
Curran Associates, Inc.
[9] Hyunjik Kim, George Papamakarios, and Andriy Mnih, "The lipschitz constant of self-attention," in Proceedings of the 38th International Conference on Machine Learning, Marina Meila and Tong Zhang, Eds. 18-24 Jul 2021, vol. 139 of Proceedings of Machine Learning Research, pp. 5562-5571, PMLR.
[10] Benjamin L Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang, "Inductive biases and variable creation in self-attention mechanisms," in Proceedings of the 39th International Conference on Machine Learning. Kamalika Chaudhuri, Stefanic Jegelka, Le Song. Csaba Szepesvari, Gang Niu, and Sivan Sabato, Eds. 17-23 Jul 2022, vol. 162 of Proceedings of Machine Learning Research, pp. 5793-5798888 5831, PMLR.
[11] Hongkang Li, Meng Wang. Sijia Liu, and Pin- Yu Chen, "A theoretical understanding of shallow vision transformers: Learning, generalization, and sample complexity," in The Eleventh International Conference on Learning Representutions, 2023.
[12] Mostafa Dehghani, Josip Djolonga, Basil Mustafa, Piotr Padlewski, Jonathan Heek, Justin Gilmer, Andreas Peter Steiner, Mathilde Caron, Robert Geirhos. Ibrahim Alabdulmohsin. Rodolphe Jenatton, Lucas Beyer, Michael Tschannen, Anurag Arnab, Xiao Wang. Carlos Riquelme Ruiz, Matthias Minderer, Joan Puigcerver, Utku Evci, Manoj Kumar. Sjoerd Van Steenkiste, Gamaleldin Fathy Elsayed, Aravindh Mahendran, Fisher Yu, Avital Oliver, Fantine Huot, Jasmijn Bastings, Mark Collier, Alexey A. Gritsenko, Vighnesh Birodkar, Cristina Nader Vasconcelos, Yi Tay, Thomas Mensink, Alexander Kolesnikov, Filip Pavetic, Dustin Tran, Thomas Kipf, Mario Lucie, Xiaohua Zhai, Daniel Keysers, Jeremiah J. Harmsen, and Neil Houlsby, "Scaling vision transformers to 22 billion parameters." in Proceedings of the 40th International Conference on Machine Learning, Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, Eds. 23-29 Jul 2023, vol. 202 of Proceedings of Machine Learning Research, pp. 7480-7512, PMLR.
[13] Ruiqi Zhang, Spencer Frei, and Peter L. Bartlett, "Trained transformers learn linear models in-context," Journal of Machine Learning Research, vol. 25, no. 49, pp. 1-55, 2024.
[14] Vishal Monga, Yuelong Li, and Yonina C. Eldar, "Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing," IEEE Signal Processing Magazine, vol. 38, no. 2, pp. 18 18-44,200 2021.
[15] Karol Gregor and Yann LeCun, "Learning fast approximations of sparse coding," in Proceed- ings of the 27th International Conference on International Conference on Machine Learning, Madison, WI, USA. 2010, ICML' 10, p. 999-406, Omnipress.

---

[16] Yaodong Yu, Sam Buchanan, Druv Pai, Tianzhe Chu, Ziyang Wu, Shengbang Tong, Benjamin Haeffele, and Yi Ma, "White-box transformers via sparse rate reduction," in Advances in Neural Information Processing Systems, A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, Eds. 2023, vol. 36, pp. 9422-9457, Curran Associates, Inc.
[17] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, "The emerging field of signal processing on graphs: Extending high- nigh-dimensiona data analysis to networks and other irregular domains," in IEEE Signal Processing Magazine, May 2013, vol. 30, no.3, pp. 83-98.
[18) A. Ortega, P. Frossard, J. Kovacevic, J. M. F. Moura, and P. Vandergheynst, "Graph signal processing: Overview, challenges, and applications," in Proceedings of the IEEE, May 2018, vol. 106, no.5, pp. 808-828.
[19] G. Cheung, E. Magli, Y. Tanaka, and M. Ng. "Graph spectral image processing," in Proceedings of the IEEE, May 2018, vol. 106, no.5, pp. 907-930.
[20] Pang and G. Cheung, "Graph Laplacian regularization for inverse imaging: Analysis in the continuous domain," in IEEE Transactions on Image Processing, April 2017, vol. 26, no.4, pp. 1770-1785.
[21] X. Liu, G. Cheung, X. Wu, and D. Zhao, "Random walk graph Laplacian based smoothness prior for soft decoding of JPEG images," IEEE Transactions on Image Processing, vol. 26, no.2, pp- 509-524, February 2017.
[22] Fei Chen, Gene Cheung, and Xue Zhang, "Manifold graph signal restoration using gradient graph Laplacian regularizer," IEEE Transactions on Signal Processing, vol. 72, pp. 744-761, 2024.
[23] Jin Zeng, Jiahao Pang. Wenxiu Sun, and Gene Cheung, "Deep graph Laplacian regularization for robust denoising of real images," " in 2019 JEEE/CVF Conference on Computer Vision and Puttern Recognition Workshops (CVPRW), 2019, pp. 1759-1768.
[24] Chinthaka Dinesh, Gene Cheung, and Ivan V. Bajic, "Point cloud denoising via feature graph laplacian regularization," IEEE Transactions on Image Processing, vol. 29, pp. 4158- 2020.
[25] Chinthaka Dinesh, Gene Cheung, and Ivan V. Bajié, "Point cloud video super-resolution via partial point coupling and graph smoothness," " IEEE Transactions on Image Processing, vol. 31, pp. 4117-4132, 2022.
[26] Yongyi Yang. Tang Liu, Yangkun Wang. Jinjing Zhou, Quan Gan, Zhewei Wei, Zheng Zhang, Zengfeng Huang, and David Wipf. "Graph neural networks inspired by classical iterative algorithms," in Proceedings of the 38th International Conference on Machine Learning, Marina Meila and Tong Zhang, Eds. 18-24 Jul 2021, vol. 139 of Proceedings of Machine Learning Research, pp. 11773-11783 PMLR.
[27] Wei Hu, Xiang Gao, Gene Cheung, and Zongming Guo, "Feature graph learning for 3D point cloud denoising," " IEEE Transactions on Signal Processing, vol. 68, pp. 2841-2856, 2020.
[28) Cheng Yang, Gene Cheung, and Wei Hu, "Signed graph metric learning via Gershgorin disc perfect alignment," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 44, 10, pp. 7219-7234 2022.
[29] Abderrahim Elmoataz, Olivier Lezoray, and SÉbastien Bougleux, "Nonlocal discrete regulariza- tion on weighted graphs: A framework for image and manifold processing," IEEE Transactions on Image Processing, vol. 17, no. 7, pp. 1047-1060, 2008
[30] Camille Couprie, Leo Grady, Laurent Najman, -harihhiittophe Pesquet, and Hugues Talbot, "Dual constrained tv-based regularization on graphs," SIAM Journal on Imaging Sciences, vol.
6, no. 3. pp. 1246-1273 2013.
[31] Peter Berger, Gabor Hannak, and Gerald Matz, "Graph signal recovery via primal-dual algo- rithms for total variation minimization," IEFE Journal of Selected Topics in Signal Processing, vol. 11, no. 6, pp. 842-855, 2017.
[32] J. R Shewchuk, "An introduction to the conjugate gradient method without the agonizing pain," Tech. Rep., USA, 1994.
[33] Sinong Wang and Ness Shroff, "A new alternating direction method for linear programming." in Advances in Neural Information Processing Systems, I. Guyon, U. Von Luxburg, S. Bengio,
12

---

H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds. 2017, vol. 30, Curran Associates, Inc.
[34] Y. Bai, G. Cheung. X. Liu, and W. Gao, Ctraph-based blind image deblurring from a single photograph," IEEE Transactions on Image Processing, vol. 28, no.3, pp. 1404-1418, 2019.
[35] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge, 2004.
[36] G. Golub and C. F. Van Loan, Matrix Computations (Johns Hopkins Studies in the Mathematical Sciences), Johns Hopkins University Press, 2012.
[37] E. BrianDavies, Graham M. L. Gladwell, Josef Leydold, Peter F. Stadler, and Peter F. Stadler, "Discrete nodal domain theorems," " Linear Algebra and its Applications, vol. 336, pp. 51-60,
2000.
[38] S. Boyd, N. Parikh, E. Chu, B. Pelcato, and J. Eckstein, "Distributed optimization and statistical learning via the alternating direction method of multipliers," " in Foundations and Trends in Optimization, 2011, vol. 3, no. pp. 1-122.
[39] H. Egilmez, E. Pavez, and A. Ortega, "Graph learning from data under Laplacian and structural constraints," in IEEE Journal of Selected Topics in Signal Processing, July 2017, vol. 11, no.6,
pp. 825-841.
[40] Xiaowen Dong, Dorina Thanou, Michael Rabbat, and Pascal Frossard, "Learning graphs from data: A signal representation perspective." IEEE Signal Processing Magazine, vol. 36, no. 3, pp. 44-63, 2019.
[41] Saghar Bagheri, Tam Thuc Do, Gene Cheung, and Antonio Ortega, "Spectral graph learning with core eigenvectors prior via iterative GLASSO and projection," IEEE Trunsactions on Signal Processing, vol. 72, pp. 3958-39777 2024.
[42] C. Tomasi and R. Manduchi, "Bilateral filtering for gray and color images," in Proceedings of the IEEE International Conference on Computer Vision, Bombay, India, 1998.
[43] Lei Zhang, Xiaolin Wu, Antoni Buades, and Xin Li, "Color demosaicking by local directional interpolation and nonlocal adaptive thresholding," Journal of Electronic imaging, vol. 20, no. 2, pp. 0230166023016, 2011.
[44] Eastman Kodak, "Kodak lossless true color image suite (photocd pcd0992)," URL http://Ok us/graphics/kodak, vol. 6, pp. 2, 1993.
[45] Jia-Bin Huang, Abhishek Singh, and Narendra Ahuja, "Single image super-resolution from transformed self-exemplars," Proceedings of the IEEE conference on computer vision and pattern recognition, 2015, pp. 5197-5206.
[46] Wenzhu Xing and Karen Egiazarian, "Residual swin transformer channel attention network for image demosaicing," in 2022 10th European Workshop Visual Information Processing (EUVIP). IEEE, 2022, pp. 1-6.
[47] Daniele Menon, Stefano Andriani, and Giancarlo Calvagno, "Demosaicing with directional filtering and posteriori decision," IEEE Transactions Image Processing, vol. 16, no. 1, pp. 132-141, 2007.
[48] H.S. Malvar, Li wei He, and R. Cutler, "High-quality linear interpolation for demosaicing of bayer-patterned color images," in 2004 IEEE International Conference Acoustics, Speech, and Signal Processing, 2004, vol. 3, pp. iii-485.
[49] Jiahuan Ji, Baojiang Zhong, and Kai- Kuang Ma, "Image interpolation using multi-scale attention-aware inception network," IEEE Transactions on Image Processing, vol. 29, pp. 9418,9428,00 2020.
[50] Jingyun Liang, Jiezhang Cao, Guolei Sun, Kai Zhang, Lue Van Gool, and Radu Timofte, "Swinir: Image restoration using swin transformer," in Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV) Workshops, October 2021, pp. 1833-1844.
[51] Zhou Wang, A.C. Bovik, H.R. Sheikh, and E.P. Simoncelli, "Image quality assessment: from error visibility to structural similarity," IEEE Transactions Image Processing, vol. 13, no. 4, pp. 600-612, 2004.
[52] Yurii Nesterov, Introductory lectures on convex optimization: basic course, vol. 87, Springer Science & Business Media, 2013.
13

---

A Appendix
A.1 Full-Rankness of Matrix P in
Given that the underlying graph G is positive and connected, we prove that coefficient matrix P in ( is full-rank and thus invertible. We prove by contradiction: suppose P is not full-rank, and there exists a vector v = [x; 14] such that Pv = ON+K. Suppose we order K sampled entries Xs before N- K non-sampled entries x5 in x, i.e., x [xs; Xs]. First, given sampling matrix
H = IK 0K.N k| E {0, 1] K focusing on the second block row of P. [H 0K,KJv 0g means Hx & 0 OKNN-KA x
0g- Thus, sampled entries of x must be zeros, L.e,, X5 0x-
Second, suppose we write Laplacian in blocks, i.e., L [Ls, Ls, Ls. Lg,s). Then, the non-sampled rows of the first block row of Mv are
x 11 1)
12L H
- LL + sg,)ss)
(27)
where (H 1 ON-K since non non- con-sapped rows of H [I: -N-K.Kl are all zeros. From above, we know X5 0k, and thus ([2L H Hv)y)s ON-K K implies that we require Lg O,- However, since Lg,s is combinatorial Laplacian matrix for positive sub-graph connecting non- sampled nodes plus least one strictly positive self-loop (representing an edge from non-sampled node to sample node), given G is connected positive graph, Lg.s must be PD (see Appendix A.2 below). Thus, #xĄg & s.t. Lg -N-K. must be full-rank.
--- contradiction. Therefore, we can conclude that
A.2 Positive Definiteness Matrix Lg.s in
Given that the underlying graph G is positive and connected, prove that coefficient matrix L in (8) is PD. By definition L å diag( (1x) ) - W, where W is an adjacency matrix for a positive graph without self-loops, i.e., Wij 2 0, Vi # j and W 0, vi. Thus, L,, = E, Waj, Vi, and 0, Vi * j. For sub-matrix Lg.s, I,,; = E,es Wa, + Ejes Wt,,, Vi E S. Define L'g.5 as graph Laplacian matrix for nodes in S considering only edges between nodes in S, i.e.,
Tr.J = w S
Lis; = Ejes Wa,, Vi S. Define D's,8 as a diagonal degree matrix for nodes in S considering only edges between S and S, i.e., Di,, Ejes Wig, Vi E S. Note that D 0, Vi. We can now write Lg,5
Lg.5 L L'g.s + D's.s-
(28)
L'g.6 s. is combinatorial graph Laplacian for a positive graph without self-loops, and thus is provably PSD [19]. D's.s is a non-negative diagonal matrix, and thus also PSD. By Weyl's inequality, Ls.s also PSD.
We prove by contradiction: suppose Lg.s not PD, and Fx + such that x Lg = 0. x LL,5x = 0 iff x LL' 0 and 'D's D' O simultaneously. Denote by S and S2 the indices of nodes in S with and without connections to nodes S, respectively. S₁ * 0, since G is connected. Suppose first S₂ 0. Then D's,s has strictly positive diagonal entries and is PD, and there is no x + 0 s.t. x D's D' 0, a contradiction.
Suppose now S² + 0. First, x D's,5x implies xs. 0. Then,
L' Σ iJES
Wey(s, (o,,)),))²2 2,
Σ iES1.jE8,
Wi - (1))=
(29)
Since each term in the sum is non-negative, the sum is zero only if for each (i,j) E where E S and j E Sz, 23 = Zy. For nodes & E S₂ connected only to nodes j E S2 connected to i S Jkk = = = x; = 0 necessarily, and for nodes I S₂ connected to l: E S2 must have 27 = F2k = and Thus, 0, a contradiction. Thus, can conclude that Lg,8 is PD.
14

---

A.3 Derivation of 177
18 and 19
define Φ [2; x; q qa] and rewrite the objective (16) to
min
M N-M
T
Φ + (H0'T
([
A 02M M+N
2M Φ
q"' 1)
?
A
(30)
2
02M,M+N 1aM
q'
B
30
a convex quadratic objective, and we take the derivative w.r.t. & and set
1M 0 N 1y-220 2M
A
OM1N,2M
(ae))
IaM
0.5+N,2M 12M
OM--N2M N2M 12M
][
1) = 0. (31) q'
b
A
O2M,M+N 12M
Given that B is the following matrix:
IM
-IM
0M
IM
C
0
-IM
B
OK.M
OK,M
OK,as
(32)
M.M
M
LM
M.M
O
M
IM
Hence, B is
2
OM.N
-I
-IM
B
ON.M
2C
C C
H
C
-C OM
(33)
LM
2L
IM
-C
M..
2
Note that adding two of row to rows 3 and 4, we get [2IM OMN,N N Owr OM. Solving for Φ (31),
we get
O
1M
0 y
B T BØ=
OM
ON
B
H
(34)
OM
11
qi
92
-IM
CT
CT
CT
H 14
+
7H
(35)
7
can solve for *1+1 directly; by adding two of row to rows 3 and of we get
2/z² ++ = -2((1m) 4 μ - μ/s Ee + 7 + a6)
1 (n's + 1 pn + (4) + qqÍ +
a 7
1M
(36)
24
Subtracting row 4 from row 3 of (35) we get
2x L+1 2-(9 1+1 o
1+1) _1 p/ / 1ee 7 4
7(q1 4+1
2 Cx
++1
+ 2 (44 - μh, μă - u!) + (q) Tb) (37)
2
15

---

Thus, row 2 can be rewritten as
7220 - H)x +1 C 7" - C nr C μr H p + 7HHH y
CT (ug ná + p' 11) -H 14d
2 cá - ab) + + y.
(38)
2
Finally, from rows 3 and 4, qf and q can be computed
1
1
q
z 1+1 Cx(+1)
(Mi uaa + +
2
27
1
1
Φ 2
2 ++
Cxtt1)
(nj 14 + 7()))
(39)
24
A.4 Invertibility of = CT
Clearly L -CC+H H H is real, symmetric, and positive semi-definite Thus its eigenvalues real and non-nege non-negative. To show that is invertible, it suffices to show that its minimum eigenvalue Amin (C) is strictly greater than zero. But Amin (C) minx:||x |=1 x Cx. Hence it suffices to show that x Lx where S is the set of nodes with constrained values. If Lx = 0 then all terms must be zero, meaning that x; in S are zero, and hence all of their neighbors, and all of their neighbors, and so on. Thus, L is invertible if there exists least one node with constrained value (i.e., self-loop) in each connected component the graph.
implies
Now observe that x T Lxx E(.))e w2 - z2)² Eies x?.
A.5 Derivation of (1
We derive the solution to optimization (20). Ignoring the first convex but non-smooth term g(ā). the remaining two terms in the objective convex and smooth. Taking the derivative w.r.t. variable and setting it to O, we get
uua - 79 1+1 + +-q = -0
1
q ++1 +
(40)
This solution valid iff g(ā") = 0: otherwise the first term g(ā") dominates and q" -O. Given that (40) can be computed entry-by-entry separately, 21 follows.
A.6 Example of Edge Weight Normalization for the Incidence Matrix
In Fig. $top), we show an example three-node undirected graph with three edge weights w1,2 1/2, W1.3 1/2, and W2.3 = 1/33, and the corresponding incidence matrix C. Normalizing edge weights using (26). see Fig. 3(iiddle) a directed graph with six edges where the sum of normalized edge weights leaving a node is 1, resulting in normalized incidence matrix C. Finally, we see in Fig. (bottoom an undirected graph with three edges corresponding to graph Laplacian -= C C.
Note that C1sl|: = 0g as expected.
A.7 Parameters Learning in Conjugate Gradient Algorithm (CG)
The linear systems that need to solve have the follow form,
(8) for GLR minimization and (88 for GTV minimization
Cx = b. Given L is PD, we consider the minimization problem,
(41)
min Q(x) = - -x-b"
(42)
with gradient
8Q(x) Lx b.
(43)
8x
16

---

1/2
-1/2
1/2
1/3
C
0
1/3
1/3
1
2
1/2
0
1/3
1/2
3
1/2
-1/2
0
1/2
2/5
3/5
3/5
0
2
2/5
-2/5
C
3/5
2/5
0
-2/5
2/5
1/2
1/2
-1/2
3/5
3/5
0
3/5
(1+53/4
29
1
2
1+
L
1+
2g
1/4+5
9
9
3
28
3
Figure 3: 3-node graph for incidence matrix C (top), 3-node graph for normalized incidence matrix
C (middle), 3-node graph for graph Laplacian L C where s (bottom).
Thus, the simple gradient descent has the following update rules with or commonly known as learning rate,
g' Lx' b g" og x+1 x' aa'g.
(44)
(45)
Next, momentum term 3, and the cumulative gradients term vt are added, resulting in the well- known Accelerated Gradient Descent Algorithm [22] also known as Conjugated Gradient Descent. The new update rules are
g' g" a2 LvLv
(46)
g' + 3,
(47)
++ x' -,vv
(48)
where both 0g and in each iteration t are considered trainable parameters.
A.8 Experimental Details
Initially, we developed our unrolled ADMM model without training any parameters. The target signal estimated using linear interpolation of known values in 5 5 pixel neighborhood. RGB values and pixel locations were combined to form feature vectors for computing edge weights Ways, which were shared across the three channels. The metric matrix M was initialized as a diagonal matrix with all entries set to 1.5. Vectors Pa. Pbs Pes Hd. and He were initialized with all entries equal to 0.1. The parameters 7/ a, and in CG were to 10, 0.5, and 0.3, respectively. For the learned ADMM block, the parameters 7/2 a, 3, and the metric matrix M were learned during training. A training dataset created consisting of 5000. 10000, 20000 image patches, each of size 64 64, train the model.
All matrix multiplications in our models are implemented to take advantage of the sparsity of the constructed graphs, which were restricted to be a window of size 5 x 25 nearest neighbors of each pixel. This ensures that our graphs are always connected and sparse. We stacked vertically Graph Learning modules coupled with ADMM block, so that we can learn multiple graphs in parallel. This is commonly known multi-head in the transformer architecture. We also stacked 5 graph learning modules and ADMM blocks horizontally to further learn more graphs. In all ADMM blocks, set the number of ADMM iterations to 5 and the number of CG iterations to 10.
To extract high-level features, a shallow CNN was employed, consisting four convolutional layers with 48 feature maps (12 features for each graph learning head). After each convolutional layer, a ReL.U activation function was applied. Convolutional layers utilized 3 x kernels without any down-sampling, generating 48 features for each pixel. The feature maps were divided into four sets,
17

---

(b) Original
(c) iGTV
(d) uGTV
Urban 100: image062.png
(c) uGLR
RST-B
(g) RST-S
Figure 4: Visual demosaicking results for image Urban062.
with each set serving as the imput for a Graph Learning module, allowing for the parallel production of four graphs. A simple weighted average scheme then used to combine the outputs into single output x'. Additionally, skip connections were introduced between the convolutional layers to facilitate the training process.
A.9
Additional Experimental Results
Fig. shows visual results for a test image for all models, including our uGTV, uGLR and the baselines. Two variants of RSTCANet, uGTV and uGLR are trained on 10000 images patches of size 64 x 64 for 30 epochs. We observe that our two models, especially uGTV, has better performance compared to RST-B and comparable performance with RST-S in selected high-frequency area.
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Main claims are clearly stated in the abstract and Introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We state the limitation of our edge weight computation, as compared to self-attention weights in conventional transformers, in Section 5.2
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
19

---

Justification:
All proofs and derivations are included in the Appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Details of our experiments explained in Section 6. and Appendix A.8
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
20

---

Answer:
[No]
Justification:
We used open source data: McM
43 Kodak
44]. and Urban 100
45 datasets.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
Cooeeeoodeesssseeeeee / casssnnnnccccyyc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
We described the experiments setup in Section 6.1 and Appendix A.8.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: We did provide various metrics for many datasets to compare models with the baseline models.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
21

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We described the experimental setup in Section 6.1 and Appendix A.8
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
As authors, we have made every effort to conform to the NeurlPS Code of
Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: The performed work is purely computational and does not have direct societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
22

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
23

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
24


Reviews:
[{"review_id": "AifnOc9EPU", "reviewer": "Reviewer_oH21", "summary": "The authors build a \"white-box\" Transformer-like neural network through algorithm unrolling and graph signal processing. This network utilizes convolutions to learn low-dimensional features per node, constructs sparse similarity graphs, and employs low-pass filtering at each layer, significantly reducing the parameter count compared to conventional transformers. The experimental results demonstrate its parameter efficiency and robustness to covariate shift in image interpolation tasks.", "questions": "1. Since this is a white-box Transformer-like neural network, why not use some Transformer benchmarks such as long-range arena for the experiments?", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper utilizes algorithm unrolling and graph signal processing to construct a lightweight white-box Transformer-like model.", "weaknesses": "1. Considering directed graph signal processing (DGSP) is much better than graph signal processing (GSP) in reality. The later is limited to undirected graphs. Therefore, the method proposed in this paper merely approximates symmetric self-attention, where the query equals the key, and cannot mimic or surpass general self-attention.\n2. The experiments are not enough to fully validate the theory.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. The reviewer raised a good point that the affinity notion in conventional self-attention mechanism in equation (23) using query and key matrices, Q and K, is asymmetric, while the feature distance in graph learning in equation (25) is symmetric, leading to an undirected graph. However, one key goal of our paper is interpretability, and given an undirected graph with well understood notion of graph frequencies (e.g., eigenvectors of eigen-decomposable symmetric graph Laplacian matrix), our GLR and GTV minimization algorithms both lead to interpretable low-pass filters of the up-sampled observations (see last paragraph of Section 4). In contrast, notion of graph frequencies for directed graphs is still actively being investigated; for example, see the following recent publications proposing different frequency definitions for directed graphs:\n\nH. Kitamura, H. Yasuda, Y. Tanaka and S. Muramatsu, \"Realization of Digraph Filters Via Augmented GFT,\" 2023 IEEE International Conference on Image Processing (ICIP), Kuala Lumpur, Malaysia, 2023.\n\nS. Kwak, L. Shimabukuro and A. Ortega, \"Frequency Analysis and Filter Design for Directed Graphs with Polar Decomposition,\" ICASSP 2024 - 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Seoul, Korea, Republic of, 2024.\n\nThus, constructing an interpretable low-pass filter of the input for directed graphs is significantly more difficult at the current time. We leave the generalization of our framework to directed graphs for future work. Nonetheless, we demonstrated in this paper that the symmetric notion of similarity for an undirected graph is already sufficient to result in unrolled neural nets that has SOTA image demosaicking and interpolation performance.\n\n2. We thank the reviewer's suggestion to use benchmark datasets in long-range arena for comparisons. One key design that enables a lightweight and interpretable transformer-like neural net is the mapping from high-dimensional input embeddings to low-dimensional feature representations (from which we compute feature distances and edge weights), which we made possible using shallow CNNs--well-known in imaging for relevant feature generation. While we believe our framework can be generally applicable to other applications beyond imaging, analogous mapping functions to low-dimensional feature representations are needed for languages and other data types. We are currently engaging experts in other domains to build such lightweight transformers.\n\nNonetheless, in the attached PDF we provide a more comprehensive comparison with additional baseline schemes in image demosaicking and interpolation, as requested by another reviewer.", "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": "", "extra_scores": {}}, {"review_id": "gnJKnmpvcl", "reviewer": "Reviewer_1kQ9", "summary": "This paper proposes a novel approach to build interpretable and lightweight transformer-like networks by unrolling graph-based algorithms. The authors propose unrolling iterative graph-based algorithms for signal restoration with graph smoothness priors (minimizing roughness) into interpretable neural network layers. Two graph smoothness priors are explored: graph Laplacian regularizer (GLR) and graph total variation (GTV). Experimental results demonstrate the advance of proposed methods.", "questions": "See weaknesses section", "limitations": "The authors don't discuss the limitations of the methods", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "S1. The paper details the mathematical formulation for both GLR and GTV based optimization problems.\n\nS2. The proposed methods achieve good restoration performance with significantly fewer parameters compared to conventional transformer-based methods.\n\nS3. The authors show robustness of the proposed approach to covariate shifts.", "weaknesses": "W1. My major concern is about the claim related to interpretability. The paper claims the proposed network is interpretable. However, the specific mechanisms for interpretability are unclear to me. Could the authors provide additional details or visualizations (e.g., activation maps) to support this claim?\n\nW2. While the paper explains the connection between the proposed graph learning module and the self-attention mechanism in transformers, there is still a large gap between these two things as the authors acked on page 7. Furthermore, It's unclear why the authors highlight the similarity. Is it because the performance advantage directly stems from this connection? Can the authors clarify the purpose of this comparison?\n\nW3. While the paper shows a reduce of proposed methods on parameter size, a runtime analysis of the proposed method compared to existing methods would be beneficial.\n\nW4. The inclusion of commonly used metrics like cPSNR and SSIM would strengthen the evaluation. Besides, adding more baselines can be more convincing. \n\nW5. The paper explores two priors, GLR and GTV. Can the authors discuss the advantages and disadvantages of each, and provide guidance on when to choose one over the other?\n\nW6. Why is there only \"iGTV\" in the experimental results, how about \"iGLR\"?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed comments, which we respond point-by-point below.\n\n1. Interpretability in the context of \"algorithm unrolling\" (see [14, 15, 16]) means that each neural layer corresponds to an iteration in an iterative algorithm minimizing a formulated optimization objective. For example, each block in our ADMM layer in Fig. 1(c) corresponds to an equation we derive in our ADMM-based algorithm to minimize our GTV objective in equation (11). This is in stark contrast to off-the-shelf deep neural nets such as transformer, where individual neural layers and their combinations are not mathematically interpretable. [16] makes the same argument that the layers of their unrolled transformer-like network minimizing a sparse rate reduction (SRR) objective are interpretable. [14] provides a good recent overview of SOTA unrolled algorithms and the interpretability they provide.\n\n2. First, while we acknowledge that there are MINOR differences between the notion of affinity in self-attention in equation (23) and the notion of similarity in graph learning in equation (25), we do argue explicitly that \"the normalized edge weights in (25) are essentially the same attention weights in (23)\" (second last paragraph in Section 5.2). THERE ARE NO LARGE GAPS. Second, drawing the connection between graph learning and conventional self-attention in transformer enables an \"interpretation\" of the graph learning module as a self-attention mechanism, and thus the unrolling of a graph-based algorithm (such as GLR-/GTV-based interpolation algorithms in our paper) can be interpreted as a transformer---the title of the paper. It also helps explain why our unrolled GTV neural net has comparable signal interpolation performance with SOTA transformer implementation, while employing a fraction of the network parameters. \n\n3. While we claim and demonstrated a drastic reduction of parameter size in our lightweight and interpretable transformer-like neural net relative to conventional transformers, we never claim a reduction of runtime (during inference), which is related to the number of neural layers. Note that both our GLR and GTV algorithms are linear time in complexity, and thus the number of unrolled neural layers are also linear w.r.t. the input size. During inference, this would mean that our execution time is comparable to other linear time algorithms / neural nets.\n\n4. We are unsure what the reviewer meant by \"cPSNR\"; to the best of our knowledge, there are no standard and widely accepted image quality assessment metrics by that name. We do clarify that for demosaicking, our posted PSNR numbers are averages computed over the three color components, R, G and B, while for interpolation, out posted PSNR numbers are for the Y-component in Y-Cr-Cb color space. We have added SSIM numbers in the attached PDF along with more baseline comparison schemes.\n\n5. We did compare our GLR and GTV algorithms in the last paragraph in Section 4.2.3. The main point here is that unrolling of the GTV algorithm is more intricate and enables more network parameters for end-to-end learning, and thus results in better performance (as demonstrated in Section 6) if sufficient training data are available.\n\n6. We have provided experimental results for iGLR (GLR algorithm without unrolling and end-to-end parameter turning) in the added PDF.", "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": "", "extra_scores": {}}, {"review_id": "edDe5hjhWN", "reviewer": "Reviewer_rsiC", "summary": "The authors propose a transformer-like NN by unrolling iterative optimization algorithms that minimize graph smoothness, which is used for imaging tasks.", "questions": "1.\tThe ideas of unfolding traditional graph optimization methods are popular in recent years. The authors may consider discuss more related works in GNNs, e.g.,\n[1] Graph neural networks inspired by classical iterative algorithms Y Yang, T Liu, Y Wang, J Zhou, Q Gan, Z Wei, Z Zhang, Z Huang, D Wipf, International Conference on Machine Learning, 11773-11783.\n[2] Simple and deep graph convolutional networks, M Chen, Z Wei, Z Huang, B Ding, Y Li\nInternational conference on machine learning, 1725-1735\n2.\tCould you provide a convergence guarantee for the proposed model.\n3.\tIt seems that all parameters are trained and updated following ADMM. However, in LISTA and other LISTA-like methods, most parameters are trained with back propagation. ADMM is just a way to build optimization-inspired networks, where each iteration corresponds to a single block in the network. What’s the difference between your model and these LISTA-like methods? And what’s the advantage of the proposed model.", "limitations": "No limitations are discussed in the paper.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1.\tThe method is well-illustrated, and the theoretical details are convinced.\n2.\tExperiments in imaging tasks show superior experimental results compared with SOTA methods.", "weaknesses": "Some more discussions on the proposed method are needed. See my questions for details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed comments.\n\n1. We thank the reviewer for the two suggested references. The first reference [1] indeed provides unrolling techniques based on proximal gradient descent (Section 2 in [1]) and IRLS (Section 3). While the objective in equation (1) in [1] employs a quadratic graph smoothness term similar to our GLR term in equation (4) in our paper, their learned parameter W in (1) differs from our learned parameters alpha and beta in our unrolled conjugate gradient (CG) to solve a linear system. More importantly, [1] assumes a FIXED graph Laplacian matrix L, while the key insight in our paper is the graph learning module that learns an appropriate similarity graph from data---one that resembles the self-attention mechanism in transformer. This insight enables us to interpret our unrolled neural net as a transformer, and explains its good performance that is comparable to SOTA transformer implementations. The unrolling of IRLS in Section 3 aims at improving robustness to edge connectivity errors in their defined unweighted Laplacian matrix; in contrast, we assume that the learned graph is sufficiently reliable for us to build a low-pass filter to compute the output. Thus, we believe that IRLS unrolling is orthogonal to our contributions.\n\nThe second reference [2] addresses the problem of \"oversmoothing\" in GCN using two techniques: initial residual and identity mapping. This work also assumes a FIXED graph, while the key insight of our work is again the graph learning module from data that is akin to the self-attention mechanism in transformer. Thus, we believe [2] is orthogonal to our contributions. We will add an abridged discussion of the first paper in the final draft of this paper.\n\n2. Convergence of an ADMM algorithm for a strictly convex optimization objective is established in several notable works, for example:\n\nRobert Nishihara, Laurent Lessard, Ben Recht, Andrew Packard, Michael Jordan, \"A General Analysis of the Convergence of ADMM\", Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:343-352, 2015.\n\nWe will reference these papers in the final draft of the paper.\n\n3. We would like to clarify that to minimize the GTV objective in equation (11), we develop an ADMM algorithm that iteratively minimizes different terms until convergence. The unrolled algorithm dictates an architecture of a feed-forward neural net (see Fig. 1), whose parameters are optimized end-to-end via back-propagation and stochastic gradient descent. In this respect, our parameter tuning is no different than LISTA [15] and many other algorithm unrolling works in the literature such as [16]. Unlike previously algorithm unrolling works, however, the key insight in our work is to connect our graph learning module with the self-attention mechanism in transformer, so that our unrolled neural net, with periodic insertion of the graph learning module, can be interpreted as a transformer also, albeit with drastic reduction in parameter size. To the best our our knowledge, we are the first to draw the connection between unrolled graph-based algorithms and transformer, and demonstrate competitive performance, while reducing the number of parameters significantly.", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their thoughtful and detailed comments. We responded to each reviewer individually in separate rebuttals below. We also attached a PDF containing extra experimental results requested by two reviewers.

Meta-review: All reviewers have appreciated the contribution, which is to propose lightweight Transformer-like architecture inspired by unrolling iterative algorithms designed to minimize graph smoothness.
Decision: Accept (poster)