LASE: Learned Adjacency Spectral Embeddings
Authors: María Sofía Pérez Casulo
Marcelo Fiori
Federico Larroca
Gonzalo Mateos
Venue: Accepted by TMLR ()

Abstract: We put forth a principled design of a neural architecture to learn nodal Adjacency Spectral Embeddings (ASE) from graph inputs. By bringing to bear the gradient descent (GD) method and leveraging the technique of algorithm unrolling, we truncate and re-interpret each GD iteration as a layer in a graph neural network (GNN) that is trained to approximate the ASE. Accordingly, we call the resulting embeddings and our parametric model Learned ASE (LASE), which is interpretable, parameter efficient, robust to inputs with unobserved edges, and offers controllable complexity during inference. LASE layers combine Graph Convolutional Network (GCN) and fully-connected Graph Attention Network (GAT) modules, which is intuitively pleasing since  GCN-based local aggregations alone are insufficient to express the sought graph eigenvectors. We propose several refinements to the unrolled LASE architecture (such as sparse attention in the GAT module and decoupled layerwise parameters) that offer favorable approximation error versus computation tradeoffs; even outperforming heavily-optimized eigendecomposition routines from scientific computing libraries. Because LASE is a differentiable function with respect to its parameters as well as its graph input, we can seamlessly integrate it as a trainable module within a larger (semi-)supervised graph representation learning pipeline. The resulting end-to-end system effectively learns "discriminative ASEs" that exhibit competitive performance in supervised link prediction and node classification tasks, outperforming a GNN even when the latter is endowed with open loop, meaning task-agnostic, precomputed spectral positional encodings.

Published in Transactions on Machine Learning Research (05/2025)
LASE: Learned Adjacency Spectral Embeddings
Sofia Pérez Casulo
sperez@ffing.ddu edu.
Facultad de Ingeniería Universidad de la República
Marcelo Fiori
mffori@fingeed edu. uy
Pacultad de Ingeniería Universidad de la República
Federico Larroca
flarrocn edu.
Pacultad Ingeniería
Universidad de la República
Gonzalo Matcos
menntessb@ece.rocheett edu
Depariment of Electrical and Computer Engineering University of Rochester
Reviewed on OpenReview: https: // optp///eepervvee...mm net/ hta//forurt forum? id= J-5NBL55NWWL Wrmh
Abstract
We put forth a principled design of neural architecture to learn nodal Adjacency Spec- tral Embeddings (ASE) from graph inputs. By bringing to bear the gradient descent (GD) method and leveraging the technique of algorithm unrolling, we truncate and re-interpret each GD itcration layer in a graph neural network (GNN) that is trained to approx- imate the ASE. Accordingly, we call the resulting embeddings and our parametric model Learned ASE (LASE), which is interpretable, parameter efficient, robust to inputs with unobserved odges, and offers controllable complexity during inference. LASE layers com- bine Graph Convolutional Network (GCN) and fully-connected Graph Attention Network (GAT) modules, which is intuitively pleasing since GCN-based local aggregations alone insufficient to express the sought graph eigenvectors. We propose several refinements to the unrolled LASE architecture (such as sparse attention in the GAT module and decoupled lay- erwise parameters) that ofler favorable approximation ion error versus computation tradeofis; even outperformigg heavily-optimizel eigendecomposition routines from scientifie comput- ing libraries. Because LASE a differentiable function with respect to its parameters as well as its graph input, we can scamlessly integrate it as a trainable module within larger (semi-)superviiee graph representation learning pipeline. The resulting end-to-end system effectively learns "discriminative ASEs" that exhibit competitive performance in supervised link prediction and node classification lasks, outperforming a GNN even when the latter is endowed with open loop, meaning task-agnostic, precomputed spectral positional encodings.
1 Introduction
Graphs are natural models of relational data, spanning domains diverse social networks, molecular biology, recommender systems, and knowledge graphs. Graph representation learning (GRL) has emerged as a powerful framework for extracting meaningful patterns from such structured data, enabling downstream machine learning tasks. At its core, this approach seeks to encode nodes (also edges, or entire subgraphs) into low-dimensional vectors -known as node embeddings- that capture both local and global graph struc- tural properties. These learned representations facilitate scalable, flexible, and effective learning, driving advancements in applications such drug discovery, fraud detection, and personalized recommendations.

---

Published in Transactions on Machine Learning Research (05/2025)
Objectives, context, and motivating challenges. Here we revisit spectral node embeddings derived from the eigendeccmposition of the graph's adjacency matrix; see e.g., (Lim et. al. 2023 and note extensions to Laplacian embeddings are straightforward. Spectral embeddings are central to unsupervised node clustering methods (von Luxburg 2007), which intuitively motivates why information encoded in the graph cigenvectors may be used to specily vertex positions in latent space. This intuition is further justified if we assume that the graph's s structure stems from a Random Dot Product Graph (RDPG) (Athreya et al. 2017), a generative model that subsumes the classic Stochastic Block Model (SBM) and which has close ties to the general class of latent position network models (Hoff et al. 2002). RDPGs associate vector X, E X C Rd to each node, and specify that an edge exists between nodes i and with probability given by the inner-product x, X, of the corresponding embeddings; independently of all other edges. That is, the random adjacency matrix A E {0, 1). has entries A:j ~ (ernoullixx] Xj), where N is the number of vertices. Unsurprisingly, the legacy solution to the embedding problem of estimating nodal positions from an observed graph is given in terms of the adjacency matrix cigenvectors (Athreya et al., (017];: see Scction 2.1 Note however that eigendecomposition of the adjacency matrix is not feasible when edge data are partially missing (e-g., in link prediction tasks). Furthermore, node embeddings need to be recomputed from scratch in inductive settings,
which may be a significant computational burden.
Our main contribution is the principled design of a neural architecture to learn these Adjacency Spectral Embeddings (ASE) solely from (undirected and unweighted) graph inputs, and which overcomes the afore- mentioned shortcomings of eigendecooppsition-neee based spectral embeddings. As we discuss in Section 5 there have been previous related efforts to learn so-termed nodal Positional Encodings (PEs), with the distinct goal of enhancing the expressive power of GNNs. However, virtually all these works precompude a set of PFs which are then fed inputs to neural architecture that, for instance, decouples how to refine the PEs and the node representations in GNN (Dwivedi et al. 2022); or, (in way akin to an autoencoder) train a GNN followed by a multilayer perceptron to reconstruct these input PEs (Cantürk et al.) 2024). Again, this pre-computation step may prove too costly for large graphs, and needs to be carried out repeatedly in inductive settings that embed multiple graphs from some underlying distribution. Our goal is to avoid this overhead altogether and design a model that learns ASEs in an unsupervised manner. Post training, embeddings of new graphs are efficiently obtained via a forward pass through a neural network (NN).
Another challenge to this end lies in the impossibility of computing the eigendecomposition of A (i.c., the ASE) through a GCN, at least in several important settings. For instance, consider a symmetric SBM graph with two equally-sized communities that have the same connection probabilities. Each node will locally "scc" the same structure, and if the input node features have the same characteristics across clusters, the GCN will fail to generate dist node embeddings for vertices that belong in different communities. This pitfall can be formalized by using graphons, a fairly general non-parametric model for large graphs. In particular, (Magner et al., 2020) identified the degree profile of the graph (i.e., the expected degree of each node) as the feature that enables a GNN to distinguish between two graphons. The Graphon Neural Network framework is particularly illuminating (Ruiz et al. 2020), and these expressive power conclusions still hold true for more general kernel-bascd based graph generative models (Keriven & Vaiter 2023). See Section 2.2 for an illustrative example and associated discussion about this inherent limitation of GNNs that molivales our work. We thus contend that a new architecture is needed when it comes to learning to approximate ASEs. Our objective here is not to propose a new statc-of-thh-art PE, but rather to broaden the applicability of ASE whose merits for statistical inference have been well documented; see e.g.; (Athreya et al., 2017).
Technical approach. Adopting low-rank adjacency matrix factorization perspective to the spectral embedding problem, one can bring to bear the gradient descent (GD) method that is provably locally convergent to the ASE solution (Fiori et al. 2024]. The optimization formulation is flexible to accommodate embeddings of partially observed graphs, and the GD solver is competitive in terms of computation cost when benchmarked against standard eigendecompositionn libraries. Starting from these GD iterations and leveraging the technique of algorithm unrolling (a.k.a, deep unfolding) (Gregor & LeCun 2010 Monga et al., 2021), we truncate and re-interpret each iteration of the algorithm as layer in a (graph) NN that can be trained to approximate the ASE. Accordingly, we call the resulting embeddings and our parametric model Learned ASE (LASE), which is interpretable, parameter efficient, robust to inputs with missing edges, and offers controllable complexity during inference.
2

---

we integrate LASE in a semi-supervised GRL pipeline that can be trained in an end-to-end fashion, endowing the learned PEs with a discriminative bias for the task at hand (c.g., node classification or link prediction in our tests). Comprehensive and reproducible experiments on numerous synthetic and Published in Transactions on Machine Learning Research (05/2025)
With regards to interpretabilityy LASE layers entail superposition of GCN and hully-connedte Graph Attention Network (GAT) modules (Veličković et al. 2018 Shi et al. 2021,, which is intuitively pleasing since (as argued before) GCN-based local aggregations alone are insufficient to express the sought graph cigenvectors. Furthermore, LASE inhorits desirable features of its GD blueprint, including the ability to operate streaming scenarios where nodal representations must be continuously tracked (Fiori et al. 2024). as well as when substantial edge information missing due to e-g., sampling, memory, or privacy constraints. We empirically show that refinements to the vanilla LASE architecture (such as sparse attention in the GAT module) can result in favorable approximation error versus computation tradeoffs -inference times are over an order of magnitude faster than GD, and even outperform heavily-optimized routines to estimate the top eigenvectors in scientific computing libraries (Chung et al. 2019). Accordingly, we find LASE can be particularly useful in scenarios where limited computational resources render eidencomposition of (mulciple) moderately large graphs excessively time consuming, or, outright infeasible depending on the number of considered embedding dimensions and edge sparsity levels. Finally, since the LASE architecture combines GCN and GAT modules, it can be naturally instantiated on different graphs. We exploit this flexibility to reduce computation costs by training LASE on smaller subgraphs sampled from the larger one to be embedded. We also empirically show how the learned weights are robust to modest shifts in the underlying graph distribution. All in all, LASE yields node embeddings that are robust to missing data as well as minor ion shifts, at a fraction of the cost. of prior art and without sacrificing approximation accuracy.
On top of unsupervised learning of ASEs that are useful e.g., in graph visualization, clustering, hypothesis testing (Athreya et a 2017), or change-point detection (Marenco et al., 2022). LASE may also be used in an end-to-end fashion for other supervised tasks such link prediction of node classification. Indeed, since LASE is a differentiable function with respect to its parameters as well as its graph input, we can scamlessly integrate it as trainable module within a larger (semi-)supervised GRL pipeline. That is, instead of using pre-trained LASE embeddings along nodal features as inputs to e.g. a GNN, consider instead training an end-to-end system whose loss function takes into account both the task at hand (c.g., link prediction) as well as the reconstruction errors |x] x - -Aiy between the output of the LASE decoder and the given adjacency matrix; see (Chami et al., 2022). In the end-to-end system training entails optimizing LASE and GNN parameters jointly. We show the resulting architecture effectively learns "discriminative ASEs" that exhibit competitive performance in link prediction and node classification tasks, outperforming GNN even when the latter is endowed with precomputed, but lask-agnostic, spectral PEs.
Summary of contributions. In this work, we contribute the following technical GRL innovations and provide experimental evidence to support our claims:
We propose T.SS (Section 3). an unsupervised NN model that can be trained to approximate spectral embeddings of input graphs, even in scenarios where GNNs fail because of their well-documented limitations to express graph cigenvectors. The permutation-cquuivrraatt LASE architecture is designed by unrolling a GD method to compute ASEs, i.., we truncate and map algorithm iterations to interpretable and parameter- efficient NN layers that combing graph convolution and transformer modules. The unrolling offers an explicit handle on complexity leading to faster (post training) inference times and satisfactory ASE approximation error performance, even when a sizable fraction of input graph data are missing: see the tests in Section 4.1
We introduce architectural and mothodological refinements with an eye towards scalability in resource- constrained settings (Section 3.3.. Leveraging sparse allention in the GAT module of the LASE layer enables embedding larger graphs, where spectral decomposition may prove computationally impractical. Since LASE is inductive, we propose a methodology whereby training is performed on smaller sub-graphs. Subsequent inference on the entire graph becomes feasible because of the simplicity of LASE's layers, and yields vectors with minimal performance degradation relative to ASF, the eigendecomposition gold standard.
In Section 3.4
real-world datasets demonstrate the resulting architecture outperforms GNN bascline supplemented with precomputed PEs, especially if there are unknown edges in the input graph; see the tests in Section 4.2
3

---

Published in Transactions on Machine Learning Research (05/2025)
2
Background
Here we briefly review the graph spectral embedding problem associated with RDPGs, introduce GNNs and discuss challenges facing their ability to express graph eigenvectons (hence, spectral node embeddings). We also outline the basic ideas behind the algorithm unrolling principle, which we will leverage in Section 3 to design NN that can learn to approximate spectral emboddings of graphs adhering to the RDPG model.
2.1 Adjacency spectral embedding
Going back to the RDPG model for undirected and unweighted graphs G(V,8) introduced in Section I lct us state the associated node embedding problem. To this end, start by stacking all the nodes' latent position vectors x, RR,, E V, in the matrix X = [x1,....,, xy]] R-xxd Matrix X is unknown and we would like to estimate it from observed graph data. The RDPG model ties the unknown latent positions with the observations, thus making the aforementioned estimation (i.e., node embedding) task feasible. Formally, recall that RDPGs specify edge-wise formation probabilities Pt := x, X, for each unordered pair (i,j) E V x V, which correspond to the entries of the rank-d, positive semidefinite (PSD) matrix P: XXT. Recalling A. ~ Bernoulli(x x xj) for i i j and because the diagonal entrics in A are zero (we model graphs with no self loops), then we say A RDPG(X I and have [A] X = M o P, where o is the entry-wise or Hadamard product and M 1 IN is a mask matrix with ones everywhere except in the diagonal where it is zero. Given the observed adjacency matrix A ~ RDPG(X) of G(V,E) and a proscribed embedding dimension d, the goal is to estimate X. Typically, d < N is obtained using an elbow rule on A eigenvalue scree plot [Chung et al. 2019
Since a maximum likelihood estimator of X is computationally challenging and may not be unique Xie &
Xu 2023 a natural alternative is to try leaat-squares (LS) instead (Scheinerman & Tucker 2010 namely
X E arg min M (A X XERNxd xd
In words, P = XXT the best rank-d PSD approximant to the off-diagonal entries of the adjacency matrix A, in the Frobenius-now norm sense. The RDPG model is identifiable modulo rotations (i.e., for any orthogonal matrix T E Rdxd we have XT(XT) = XX = P), and accordingly the solution of is not unique.
Entrywise multiplication with M = I IN effectively discards the residuals corresponding to the diagonal entries of A. If suitably redefined, the binary mask M may be used for other purposes, such as accounting for unobserved edges if data are missing. For instance, in a recommender system we typically have the rating of each user over only a limited number of items. These missing data may be accounted for in by zeroing out the entries of M corresponding to vertex pairs for which edge status unobserved.
Typically the mask M is ignored (and sometimes non-zero values are iteratively imputed to the diagonal of A (Scheinerman & Tucker 2010)), which results in closed-for forsed--ormm solution for X. Indeed, if we let M 1N 1 in (1) we have that X 1/2 where A VAVT is the cigendccomposition of A, Å Rdxd is diagonal matrix with the d magieste eigenvalues of A, and V E R. are the associated eigenvectors. This workhorse estimator is known the Adjacency Spectral Embedding (ASE); see also (Athreya et al. 2017) for consistency and asymptotic normality results, as well as applications of statistical inference with RDPGs.
2.2 Graph neural networks vis- aiss spectral embeddings
Graph convolutional filters, frequency representation, and GNNs. A GNN layer entails a graph convolution followed by pointwise non-linearity. The former can be represented as a polynomial
K
Xout Σ H',
A=
We have treated X as deterministic. One could also assume that the latent position vectors x; 6 Rd. i e V are random and drawn i..dd from a suitable "inner-product" distribution F supported in X' S. Rd; see e.g., (Athreya et al. 2017). The (hierarchical) RDPG model that consists of drawing and then A RDPG(X) denoted as (A, X) RDPG(F).
4

---

Published in Transactions on Machine Learning Research (05/2025)
where the input graph signal X E R Fin has Fin features per node, the output signal Xour R Nour pour has Fout nodal features, and H2 E "R=""xp'' is a matrix of learnable filter coefficients. Note that in (2) we use the adjacency matrix and its powers for simplicity; one could use other graph shift operators such as the Laplacian, or, dogrec-normalizer versions of any of these matrix representations of graph structure. See also Appendix A. and the lutorial (Isuli el al. 2024] for additional background on graph convolutional fillers. In particular, discussion in [Isufi et al. 2024, Section VIII-A argues that the polynomial representation (2) that is mainstream in graph signal processing circles subsumes "combination and aggregation" operations in several message-passingg GNN models, for specific choices of K, H3, and the graph shift operator.
Graph filters can be equivalently represented in the graph spectral (frequency) domain. To see this, consider F = pout_ = 1 to simplify exposition and once more let A = VAVT, where A = diag(Ai,..... ,N) collects the graph eigenvalues and V = [Vi....., v.] the respective orthonormal eigenvectors. Defining x = V x as the Graph Fourier Transform (GFT) of a graph signal x, it follows that the GFT of Xout in is
Σ haa* & Rm
Rout
which is a pointwise equality since A is diagonal. Furthermore, we may recover the actual output signal via the inverse GFT Xout VXout. These results are easier to grasp in terms of inner products and orthonormal signal dccompositions. GFT coefficients in Xin correspond to the inner product between x and the corresponding eigenvectors i.e, the graph's frequency modes. To carry out the graph convolution, the i-th coordinate &m, is scaled by the filter's frequency response h(A.) == Ek=o h at frequency d to yield Tour,i. Finally, each eigenvector v, is scaled by Zout, and summing over frequencies yields Xout = E Vy. Recapping, signal Xmn is decomposed in terms of the columns of V, each component is then filtered via h(*r), and the output is new combination of the columns of V using these filtered coefficients.
These insights carry over to the multi-channel graph filter (2) since Xout is a linear combination of several single-channel filters. Furthermore, a GNN layer is simply a pointwise non-linear operation (-) [e.g,, (x) = ReLU(x)] applied to the output of the graph convolution. Apparently, this frequency domain viewpoint suggests cigenvectors of A play crucial role in the expressivity of a GNN, as we now further illustrate; see also the studies in e.g.: Kanatsoulis & Ribeiro (2024): Ruiz et al. (2024).
On GNN's ability to express graph eigenvectors and spectral embeddings. Consider for instance vN
a regular graph where all nodes have the same degree r, implying that V1 = 1x is an eigenvector of A associated to eigenvalue Å = r. Suppose we want to perform unsupervised node clustering with GNN. Even if all nodes have the same degree, they can still belong to different classes and for instance prefer connecting to nodes of the same community; see Example D for an SBM where nodes in two different communities have the same expected degree. Since we only know the graph's structure and have no informative nodal attributes we could choose as an input signal, we are free to choose whatever signal we want. For instance,
Xin 1/2% or any other constant signal are widely used in the literature; see e.g.; (Morris et al. 2019 Xu
et al. 2018). It is clear that the GNN (with one or multiple layers) will output Xout = (((Ai) VN is also constant signal and thus ineffective to accomplish our discriminative goal.
which
The problem lies precisely in using a constant signal as an input, which happened to be one of the eigenvectors, and thus all other information on the graph's 's structure is lost because of mutual orthogonality of the frequency modes. A popular alternative to reveal further information by exciting all spectral components is to feod the GNN with zero-mean white noise across nodes (Sato al., 2021 Abboud et al., 2021 Kanatsoulis & Ribeiro 2024 For instance, by feeding standard white Gaussian noise to the convolutional layer, Nout becomes another zero-mean uncorrelated Gaussian vector, where now each entry has variance equal to h (Ax). The output signal Xout in the vertex domain is thus a lincar combination of the columns of V, with random weights. Interestingly, it is possible to recover, say, the j-th eigenvector V, through a graph convolution. For high enough K, filter coefficients h2 may be chosen so that h(A,) = 0, Vi J (i.e., a frequency selective or notc filter the signal procossing lingo). Actually, white noise may be used to compute the ASE (1) through a graph convolution as we show in the following example. However, the example also highlights how this solution is unsatisfactory, since transferability across graph sizes (from the same model) is not possible.
5

---

Published in Transactions on Machine Learning Research (05/2025)
h1(A)
0.0
ASE
h2(A)
Graph Conv.
-0.5
Iz
0.8
0.6
0.4
0.2
2
0.5
ASE
-2
Graph Conv.
0.0
-4
0.1
0.0
0.1 X
0.2
0.3
-0.5
0.0
0.3
Figure 1: (left) Estimates X in (1) obtained through ASE and graph convolution trained as in (3). When using a single white noise sample Xin and graph G, the graph convolution-baser embedding is quite accurate (top-left). However, the learned filter coefficients cannot be used estimate the ASE of another graph with more nodes, even if they stem from the same SBM model (bottom-left). (right) Filter frequency responses (A) and h2(A) for the learned coefficients in (3). as well as the GFT coefficients of both the original signal Xin and the new sample x The height each stem represents the value the i-th GFT coefficient, supported on the corresponding frequency \ç Since both G and G' adhere to the same SBM and we have used a normalized adjacency matrix, their cigenvalues are similar. However, the fact that we were forcod to generate new random input samples produced random combination of the eigenvectors the output, resulting in inaccurate estimates of X shown in the bottom-left subplot.
Example 1 (Symmetric SBM) Consider a graph G(V,E) sampled from SBM with = 2 classes of N/2 = 100 nodes each and symmetric inter-class connection probability matrix II = (0.5 0:)), where d = 2 is thus enough for X in [1.. Consider using a GNN to identify to which class each node belongs to. A baseline approach is to compute the ASE X and cluster the resulting vectors method that enjoys theoretical guarantecs (Athreya et al. 2017). Denote by 4 (x H) R the output of the graph convolution using filter coefficients 7 = (Hg- E R
x2 k. = 0, O..... 20). Given white noise sample Xin E RN, we want to find
filter coefficients H" such that (ef.
1
H- = arg min | (A (x H) (Xmi H))
where here A denotes the adjacency matrix normalized by the number of nodes N. The optimal coefficients may be found through backpropagation, which results in two set of filter coefficients (corresponding to each output dimension), and thus in two frequency-doman superimposed the ASE. solution is depicted in Fig. (top=left). The resulting embeddings are quite similar, with a total reconstruction error equal 81.7 and 81.6 for the graph convolution and ASE in ①1. respectively.
responses hy (A) and (A). The resulting ( H²)
Now suppose that want to use the learned architecture to embed nodes from another graph GV(V",E", Specifically, consider another SBM graph with the same parameters II, except that now both communities have double the size (i.c., N2/2 = 200 nodes cach). So even if we wanted to reuse X from the previous sctting, we must generate 200 new random samples to populate the input X E RRN'". The resulting embeddings 2 ix(n; H²) are shown Fig. [ (bottom-left), while the reconstruction errors are now 202.6 and 164.7 for the graph convolution and ASE, respectively. The reason behind this failure is illustrated in Fig. I (right), showing the resulting GFT coefficients of the input signals X and x supported on the corresponding eigenvalues of A and A' respectively. The filter coefficients in H*, producing hy hz(A) and hz(A), are such

---

Published in Transactions on Machine Learning Research (05/2025)
Algorithm 1 An iterative algorithm
Require: Initialize X
+
while Convergence criteria not met do
Unrolling
X +((;;,)
h(=00))
h(=:0z) + X
X1-1 +- h (1)
1+1+1
end while return X
Figure 2: A schematic illustration of the algorithm unrolling principle: given an iterative algorithm (left), each iteration is mapped into a NN layer and the number of iterations is truncated to L. The layers are then composed to form a deep NN of depth L (right). Algorithm step-sizes, penalty, or regularization parameters are mapped to NN weights {0r}, and learned from training data by minimizing a suitable loss function.
that they overfit the original white noise input Xin in order to produce a good approximation of X. Indeed, notice from Fig. | (right) that, expected, these optimal filters end up relying only on the two dominant components V1 and V2 (for X z 0.3 and A2 0.2), while all other frequency modes atennuated and effectively discarded. However, when another noise sample is used the input signal's GFT coefficients change significantly [compare i vs i and ž vs V in Fig. I (right)], and hence the resulting outputs will be (different) random linear combinations of the corresponding eigenvectors.
Apparently, the preceding example showcases the scnsitivity of the predicted spectral embeddings to the input signal Xin fed to the convolutional model. One could atlempt to train the architecture with sev- eral noise samples as input to improve generalization. However, the problem remains, since for any given set of parameters H. the output will still be random lincar combination of the cigenvectors and thus generalization not possible. An alternative output. For instance, the expected value of the entry-wise square of the output of convolutional layer; i.e., E (xii H)] (Kanatsoulis & Ribeiro 2024). However, in this symmetric case obtain constant signal (see Appendix A.2 for details), which takes us back to the discussion at the opening of this section. Since the node embedding (i.e., matrix factorization) problem I can be solved via factored GD and exhibits robust convergence propertics even from random initializations (Fiori et al. 2024 Chi et al. 2019). our idea is to mimic those iterations a custom NN obtained via algorithm unrolling the subject dealt with next.
instead consider (non-linear) statistic of this random
2.3 Algorithm unrolling
The algorithm unrolling (or deep unfolding) technique was pioncered by (Gregor & LeCun of truncating and mapping an iterative opt iptimization algorithm into a NN architecture. Each iteration of the algorithm becomes layer of the NN, and subsequently composed form a deep NN depicted in Fig. 2 The mapping process was quite natural in the sparse coding context of (Gregor & LeCun 2010). since the workhorse iterative sarinkaage-hheshoolee
2010 and consists
algorithm (ISTA, Beck & Teboulle (2009) boils down to repeated: (i) linear updates stemming from the gradient of the quadratic T. loss; followed by (ii) a pointwise nonlinear (ReLU-like) soft-thresholding operator (the proximal operator associated to the fn-nrrm regularizer). A forward pass through an unrolled NN emulates the execution of the iterative algorithm for a finite number of iterations. Optimization algorithm step-sizes, penalty, or regularization parameters are mapped NN weights, and therefore Iearned from data through end-to-end training using backpropagation.
One view this process effectively truncating the iterations of an asymptotically convergent proce- dure, to yield template architecture that learns to approximate solutions of optimization problems with substantial computational savings relative to the optimization algorithm. For instance, results in (Gregor & LeCun 2010)) show that the learned version of ISTA outputs sparse image representations of comparable performance, but 20x faster than the iterative solver. Moreover, as discussed in (Monga et al. 2021 the unrolled network amenable to architectural modifications, such as letting the learned parameters vary across different layers instead of being shared. This deviation from the original iterative algorithm can result
in major performance gains, as shown in various applications; see e.g., Yee & Mateos 2022 Pu et al. 2021
7

---

Published in Transactions on Machine Learning Research (05/2025)
Wasserman et al. 2023 Monga et al. 2021). Finally, the strong inductive biases encoded in the unrolled
NN makes these models both parameter and sample efficient (Monga et al. 2021
3 Learned Adjacency Spectral Embedding (LASE)
3.1 Problem statement
Suppose we are given training samples of adjacency matrices T := {A adhering to an (XP model. These adjacency matrices may be partially observed, which chase cach A A is accompanied by a mask M E (1,0) encoding which entries A are missing; see Section 2.1 Let d be prescribed
embedding dimension. Our goal in this paper is to learn a judicious paramctric mapping + that predicts
the nodal embeddings & +(AA; H) E R in (1) by minimizing the empirical risk
1 Σ C(H) == T
E(A ( H) (A (A(;H))
(4)
iT
to search for the best parameters H. The loss l can be adapted to the task at hand. In most cases we will adopt the squared reconstruction error discussed so far, where f(A, (A; (A; H)) := M (A - (AA; H T (A: dings that are suitable for a downstream task (e.g., node or link prediction). is prudent to augment the reconstruction error with task-dependent loss function such as cross-entropy. Such integration of & as a trainable module within larger (semi-) (semi-)supervised GRL pipeline will be considered in Section 3.4 where the training set T will also incorporate task-dependent supervision signals (e.g., node labels).
jcf. (1). In cases where we would like to learn discriminative embed-
Next, we discuss the design of the parametric model d using algorithm unrolling. Architectural refinements are outlined in Section 3.3
3.2 Learned ASE via algorithm unrolling: Gradient descent as neural architecture blueprint
Given the impossibility of a GNN to produce useful embeddings in some important settings discussed in Section 2.2 let us re-consider the original problem in [I]. Instead of estimating the ASE through a spectral decomposition of the adjacency matrix [which in fact solves (1) when M = 1y as argued Section 2.1 we could try to solve the optimization problem using iterative methods. This approach was explored in [Fiori et al. 2024), where factored GD was advocated and successfully used to estimate node embeddings, even in online settings where graph data arrive in streaming fashion and edge status may be partially unknown (as encoded in M).
Let us now briefly present this idea and illustrate how the resulting algorithm lends itself naturally to a re- re-interpretation as a GNN through the framework of algorithm unrolling we discussed in Section 2.3 For case of exposition, we will not consider the mask M here, and leave its inclusion to the next section along with other architectural refinements.
Let ʃ : Nxd + IR be the smooth, nonconvex objective function f(X) A XX 1|3 to be minimized. The factored GD algorithm consists of the following iterations
X = X, (VX)))), 1 1,
where Vf(X) 4XX A)X and > the step size. Given the favorable landscape of f(X), the local and global convergence properties of 5 are well understood (Bhojanapalli et al. 2016: Chi et al. 2019 Vu & Raich 2021 Fiori et al. 2024). In practice, randomly initialized Xo will suffice for convergence to clement X in the set of global minimizers [recall from Section 2.1 the solution of (1) is not unique duc to rotational ambiguities). Substituting the expression of the gradient (x(X) in 5 we arrive to the following
iterative update rule
X = X; 4a - A)X,
-I + 4o 4aX,X, X,
Note that the first summand in (6) is a first-order graph convolution as 2 where the graph shift operator is the adjacency matrix A, and the filter coefficients Hn I2 and H; 4o In turn, the second summand
8

---

Published in Transactions on Machine Learning Research (05/2025)
GD iterations LASE stacked layers
LASE Layer
LASE Layer
LASE Layer I.
X
GCN
GCN
GCN
X
GAT
GAT
GAT
Figure 3: An illustration of the proposed LASE unrolled NN, where L LASE blocks are seamlessly stacked, equivalent to truncating the GD algorithm 6 to iterations. Each LASE block consists of the superposition of a GCN with a GAT module, the latter acting on a fully-connected graph and using an inner-product- bbaeed attention mechanism. Input Xo consists of random samples, the same initialization as in the GD algorithm, resulting in estimated spectral embeddings X (A H) == X,,, where H. includes the learnable weights of all the GCN and GAT modules.
can be interpreted a Graph Attention Network (GAT) (Veličković et al. 2018 in a fully-connected graph, with particular choice of attention coefficients and no pointwise non-linear activation function. Recall that in a GAT, the output of the next. layer is similar to a GNN, except that the entry i, in the graph shift operator (i.e., the so-called attention coefficient) now depends on the signal on both incident nodes X and Xt,, In this case, attention coefficients are collected in the matrix X,X,X, That to say, they are expressed as an inner-product without the typical softmax used in (Veličković et al. 2018). While admittedly the attention mochanism is not employed in the standard GAT manner, in our view the GAT reference serves as an analogy to help better contextualize our method within the broader landscape of GNNs.
Taking this into consideration and letting some of the coefficients to be learnable (matrices H₁ and H2 below), each GD iteration in 6 can be reinterpreted as an NN layer. The I-th layer, which we will generically denote as the Learned Adjacency Spectral Embedding (LASE) block, produces the following output:
X X1 AXH X,X X,H2
X GCN(X.) - GAT(X:),
(7)
where the GCN term, as the GAT, also omits the non-lincarity. Using random samples as X, and cascading L of these LASE blocks [thus producing the parametric mapping X (AA := X ef. 44] can be interpreted as truncating the GD algorithm to L. steps. We will refer to the resulting I-layer unrolled NN as LASE. This process is illustrated in the diagram in Fig. 3
The LASE network undergoes saff-rriniig across realizations := = (A optimizing parameters H == (H, H2) to minimize the objective function L(H) in (4) through gradient-baser learning techniques. In Section 4.1 we empirically show that the necessary depth of the trained LASE is orders of magnitude smaller than the number of iterations required by the GD algorithm to achieve convergence. This is significant, because the inference time over multiple (potentially large) tests graphs can be markedly roducod.
|-= 1 of a specific graph distribution,
Properties of the LASE architecture. In the discussion so far we have assumed that the learnable weights H := (H, H2} are shared across LASE layers, consequence of the strict unrolling procedure, This approach has the benefit that we could train LASE network with Lerain layers, but then use it for inference with Laest > Lurain layers, polentially improving the estimated spectral embeddings during inference while keeping the training cost at a (resource-dependen) minimum. However, we decouple the parameters of cach layer and learn them independently, we may incrcase the expressive power of the NN and thus boost its performance for a given depth L. In our experiments we have opted for this latter alternative, using a total of 2 x L x d² independent parameters in H. (H1,1, H2/
9

---

Published in Transactions on Machine Learning Research (05/2025)
LASE (5- 411.3)
GNN 437.2)
ASE LASE
0.8
0.5
0.0
0.4
34
-12
0.2
82
-0.0
0.0
-0.
-06
-11 -05
Figure 4: GNN and LASE models are trained with several samples of a symmetric SBM using a loss of the form W. The left and center panels show the estimated probability matrix P = XXT for LASE and the GNN, respectively (the reconstruction error f = || (A (X-X--XX TI is also shown for reference). The most panel plots the estimated spectral embeddings X (including ASE as a reference). Whereas LASE using only layers produces useful spectral embeddings closely matching the ASE, a GNN fails.
Regarding computation cost, note that the number of Icarnable paramcters is, as in all convolutional GNNs, independent of the number of nodes N - and typically much smaller than N, it is customary with unrolled NNs (Monga et al. 2021). However, the greatest bottleneck resides in the GAT module, where the term X translates to 22 pairwise interactions over fully-connected graph. This negates one of the benefits of GNNs, which is leveraging the graph's 's sparse connectivity structure to compute graph convolutions through local, distributed message passing operations. To alleviate this problem, we will implement so-called sparse attention mechanisms; see the ensuing section about architectural refinements for full details.
Besides the alluded computational benefits, that the number of parameters is independent of N also implies that may train the model with graphs of certain size, and then infer the embeddings on any other graph, including larger oncs. Naturally, in order to produce useful embeddings these graphs should stem from similar underlying distribution, and we will empirically study the generalization capability of LASE in the next section; see e.g., (Ruiz et al.) 2020) for theoretical results regarding transferability of GNNs, As a practical benefit of this feature, consider computing node embeddings for a large graph. We contend one can Irain the model on several relatively small subgraphs of the original one. During inference (less computationally demanding), we compute the embeddings for the large graph; see the results in Section |
Finally, recall that GD was initialized at random and for LASE follow suit. This stands in stark contrast with Example ! where we showed the inability of GNNs produce useful spectral embeddings from noisy graph signals (or nodal attributes) in symmetric SBM. As we argue next, LASE avoids this pit and is able to recover embeddings with similar accuracy to ASE or GD, but using fewer iterations (i.e., layers).
Example 2 (Symmetric SBM revisited) Going back to Example ! recall there we considered an SBM graph with C' communities of equal size and symmetric inter-class connection probability matrix II (0.5 (..50.)). To avoid over-fitting the input signal, we may expose the learning architecture to several samples of both the input noise and even the graph (by generating several SBMs with the given II).
For instance, let consider a 2-layer GNN where each layer consists of convolution of order =3 followed by a tanh non-linearity (except in the last layer). All dimensions, including the hidden layers, are d = 2. We trained this GNN and LASE (with I, = 5 layers and d = 2) using T = 100 graph and noise samples, and a representative inference result (for a new noise and graph sample) is depicted in Fig. 4 As expected, the GNN is unable to produce useful embeddings for these regular graphs, whereas LASE is successful.
3.3 Architectural refinements
The barc-bones LASE model presented in the last section can be further customizod and enhancod, as traditionally done with unrolled deep learning architectures; see e.g., (Monga et al. 2021). Some architectural refinements are motivated by computational considerations, like the cost. of a dense GAT module, and some
10

---

Published in Transactions on Machine Learning Research (05/2025)
others allow the model to operate under more general settings. In the sequel we describe series of refinements integrated into LASE, with the objective of enhancing the model's robustness and performance.
Node-wise normalization. To improve stability during training, node-wise normalization was added to the LASE model. This normalization step consists of dividing both the GCN and GAT terms by the total number of nodes N. This action helps maintain numerical quantities at a balanced scale, mitigating any instability that may arise due to, e.g,, exploding gradients. The number of nodes is defined as a parameter of the network, making it possible to seamlessly change it during inference. Accordingly, the LASE block architecture introduced in ( is updated to
N X = X TOH+NAXIEE AXXH, - N XXX
(8)
Incorporation of a mask. For ease of exposition, the mask matrix was not considered during the derivation of the LASE block. To address the original formulation (1], for instance to specify observed and unobserved (or missing) data, the expression for the block computation including the mask Mobs becomes
X = X
(Mobs , Npobs
(Mobs (X(X)))XII
(9)
Npobs
where Pobs is the proportion of present edges with respect to the number of nodes in the mask matrix Mohs-
Sparse attention mechanisms. By default, the attention mechanism employed in the GAT term assumes fully-connected graph, emulating a full attention mechanism with quadratic all-to-all interactions X,X, To attain higher computational elficiency, we have explored and implemented several sparse attention mech- anisms to bring down the quadratic interactions to linear ones. These mechanisms entail various types of (sparse) graphs in the GAT block, including: (i) those generated with an Erdös Rényi model at different sparsity levels; (ii) those generated with a Watts Maats-Strogatee model; and (iii) the integration of the Big- at- tention mechanism (Zaheer et al. 2020) commonly used in language transformers. Given the aforementioned considerations, the LASE block is updated as follows
X = X1+ + Nposs
(Mobs o A)XHH
Mobs o (Matt o (X1X,))
(10)
NoonsPat
where Mat the adjacency matrix of the sparse graph used in the GAT term to improve computational efficiency (in other words, sparse attention mask), and pan is the proportion of edges with respect to the number of nodes in matrix Matt. Note that MAn is completely unrelated to A, just as in the fully-connected case. The idea is to rapidly propagate the information across all nodes, so for given sparsity level an Matt corresponding to a graph with a smaller diameter should yield better results. The performance of the different sparse attention mechanisms (i)-(ii) is reported in Section and discussion on the inference time-complexity of LASE can be found in Appendix A.5
The vanilla RDPG can only model random graphs with adjacency matrices that are PSD in expectation (recall from Section 2.1 that P E Generalized RDPG (GRDPG) model RRubin-Delanclyy et al. 2022,, which extends the RDPG framework to accommodate a broader range of graph structures, including those with mixed assortative and disassortative behaviors. The idea is to introduce a diagonal matrix Q, with p entries equal to +1 and entires equal to -1 (such that d = p + 4), so that the expected adjacency matrix is now E[A] = XQXT. The corresponding objective function and estimalor are then expressed as (cf. [1]
Generalized RDPG.
XXT). This limitation is overcome by the
X
E arg min A - XQX 12 X
(11)
We can minic the algorithm construction and unrolling processes in Section 3.2 The gradient of the cost function is (x()) = T - -A) and therefore the unrolling of the GD algorithm with step size a is
X = X, - Xx A)X;Q
(12)
= -X - XXQQ.
(13)
11

---

Published in Transactions on Machine Learning Research (05/2025)
Note that the required modifications to the LASE block are minimal, still consisting of combination of GCN and GAT modules with minor adaptations, namely
X = X + AX - X,XX XXOXXXXXXXHHH,,,
(14)
Taking H1 = H2 = 4ol. we recover L3 The only difference with respect to (7) is the diagonal matrix Q and can recover the legacy LASE block when Q Id- However, if we have reasons to believe that the graph is not fully homophilic, malrix Q may be considered hyper-parameter i.e. for a given d, one can verily how many negative values in Q work best in terms minimizing the the overall reconstruction cost (note that there are only d possibilities). If a spectral decomposition of the adjacency matrix is computationally viable, then a more direct method to estimate the entries of Q is to use the sign of the d dominant eigenvalues of A. Since computing the eigenvectors of a (potentially large) adjacency matrix could negate the computational benefits of LASE altogether, we can instead compute the d dominant eigenvalues of m smaller random subgraphs sampled from the observed large G. This way obtain set [Qi,.... Qm) } and we choose Q through the sign of the resulting average 1/m ΣT Qm- We use this latter approach for the experiments in Section 4 but note that several other possibilities exist, such as for instance directly learning the diagonal entries in Q.
3.4 End-to-end graph representation learning
So far we have focused on unsupervised learning to approximate spectral graph embeddings with LASE, However, these embeddings are typically used for a downstream task (e.g., node classification) as spectral PEs (Wang et al. 2022). Here we briefly articulate how to use LASE in this context. The first and perhaps most natural option would be to use pre-trained LASE outputs, just like any other PE. That is, first train LASE and then concatenate the predicted PEs Xr, to the input signal Xin (if nodal attributes are available). A GNN (or whatever architecture we choose) would then produce the mapping between a concatenation Xx to the output (e.g., one-hot encoding of the node's corresponding class) This requires second training phase, now of the GNN parameters to e.g., minimize cross-entropy loss.
A second option is to leverage the fact that the LASE block is fully differentiable, making it a viable candidate for inclusion within a larger GRL pipeline designed for some downstream task. Going back to our node classification example using a GNN, instead of first adapting the LASE weights H to minimize equation [ and then training the GNN to minimize cross-entropy loss, we could instead consider a combined loss and train them jointly. The resulting end-to-end learning system (which we will denote as LASE E2E) is schematically depicted in Fig. 5 It consists of a LASE block, whose output is concatenated with the nodes' features Xnn and fed to GNN, which will in turn produce the corresponding predictive output Y. The system is trained in an end-to-end fashion by minimizing a loss that combines the reconstruction error (1) (for which only the output X = & (AA HlASe) of the LASE module is considered) and the task at hand (for which only the output Y = GN [X=: HGNN) of the GNN is used). For instance, and again considering the semi-supervised node classification example in a transductive setting where we observe a single graph with adjacency matrix A, the combined loss could take the form
[(HONN, HLASE) = JCCrossEintoppyyY Y. X) + (1-
11) M (A - XX
(15)
where Y = GNN(X m X1; HGNN) and Y are the predicted and actual class labels of each node in the training set, respectively; and X is the output of an L-layered LASE block. Furthermore, syper-parameter a E [0, 1] controls the relative weight. between recovering pure spectral PEs (μ = 0) and focusing solely on the task at hand, neglecting the PEs (u = 1). Our results in Section 4.2 evidence that LASE E2E offers
truly learnable PEs, that outperform relevant. baselines in node classification and link prediction tasks.
4 Experimental Results
In this section we experimentally validate the proposed LASE architecture in two GRL tasks. Firstly, alternative of ASE or GD to compute the spectral embeddings of a large graph. In this case, LASE may be trained on smaller sampled sub-graphs including only fraction of the nodes of the original onc. The training set comprises pairs i E T, each consisting of graph A and random noise sample x(()
12

---

Published in Transactions on Machine Learning Research (05/2025)
LASE end-to-end
X
GNN
Y
LASE
X LASE Eniledding
Figure LASE end-to-end (E2E) architecture. The output of an L-layered LASE block is concatenated with the node features, which are then processed by GNN (or whatever variation of this architecture is chosen). The system is trained by minimizing combined loss that considers both the task hand through Y as well as the reconstruction through Xt. See (15) for example of such combined loss.
used as input to LASE. Just in Example 2 even if have single graph we generate several pairs, each including an independently sampled noise. However, when training on smaller subgraphs, cach training point contains randomly sampled subgraph. In any case, the training procedure follows the standard approach of employing mini-batch stochastic gradient descent (SGD) with backpropagation to minimize the empirical risk (4). Regarding the attention mask in (10), unless otherwise stated we use a fully-connected Matt 1y15. As we show in Section 4.1 even when using the sub-graph sampling strategy the estimated nodal embeddings on the original graph are of comparable quality to ASE or GD, in terms of the objectivv function [ Notably, demonstrate that LASE offers the added advantages of being: (i) computationally feasible in scenarios where eigen-decomppsittion
in ASE is not viable approach; (ii) markedly faster than GD or its iterative variants; and (iii) able to embed adjacency matrices with missing edge information.
The other task is the one we discussed in Scction 3.4 namely using LASE in an end-to-ond GRL pipeline, instead of concalenating the spectral embeddings computed by LASE with the nodes' features to be jointly processed by another learning architecture. The latter baseline typical procedure adopted when spectral embeddings used as PEs. Training is similar to the case where we only compute the spectral embeddings, except that now augment the training set with the corresponding labels Y and the loss is modified accordingly [recall [- Results in Section 4.2 corroborate that LASE F2F, which endows the embeddings with a discriminative bias towards the task at hand, outperforms relevant baselines.
Implementation details. Before moving on, some general remarks regarding implementation details are in order To compute the ASE we rely on the state-of-the-art RDPG inference library Graspologic (Chung eet al. 2019). Our implementation of LASE is based on PyG (Fey Lenssen 2019). fully integrated a server equipped with NVIDIA GeForce RTX 3060 (12 GB) GPU and 13th generation i5- 15-13400F processor with 64 GB of RAM. As input to LASE we use X, with i.i.d. random entries sampled from the uniform distribution in [011]. This corresponds to the same initialization of the factored GD in (Fiori et al. 2024), for which here we chose the step size a in 5 through the Armijo rule. The embeddings" dimension d is considered a hyper- parameter. For the selection of Q in GLASE, we rely on the subgraph sampling plus eigendecompoistion method described in the closing discussion of Scction 3.3
message passing layer in this popular framework. All experiments were
2 All anonymized source code and examples are available as supplementary files that accompany this submission.
13

---

Published in Transactions on Machine Learning Research (05/2025)
322.7)
3227)
355.8
08
08
0.
SBM -
06
06
0.
000
0.4
0.
644
0.1
0.2
02
0.2
62
4.0
(f- 600.9
CD Armilo ff 600.9)
CDP Armilo (f 710.8
LASE 5 610.2)
9.
66
SBM
0.4
0.4
0.4
0.4
02
02
02
0.2
4.1
4.11
ASB (1- 632.11
GD Acnijo [C- 632.1)
GD 5 Amniju (( 776.0
LASE 636.0)
96
SBM
0.1
81
0.
0.1
0.2
0.
102
M10
401
00
Figure 6: The estimated P XX using different methods (ASE, GD until convergence, steps of GD and LASE using 5 layers) tested in different synthetic SBM graphs. The resulting reconstruction cost is shown above each estimation. Note how LASE obtains significantly better results than GD when using the same number of iterations.
4.1 LASE to compute the spectral embeddings
4.1.1
Comparison to baselines
We first turn attention to the quality of LASE's estimates Xt. In particular, we will compare it to both the aigendoomposition--laesss gold standard ASE as well as the iterative GD method that served a blueprint for LASE. Regarding the latter, we implement two variants: running GD until convergence or using the same number of iterations as layers in LASE (L 5L=
Let us begin by considering SBM random graphs. As Example LASE was trained using 7 = 1000 samples of both the input noise and graph adjacency matrices generated with the prescribed II. Inference results in the form of the estimated probability matrix P - x for the four methods considered (ASE, GD Armijo, GD-5 Armijo, LASE) and corresponding to three different SBMs are depicted in Fig. 6 The main difference between the SBMs considered is the number of nodes (N = 100, 150, and 300) and communities (C = 2, 3 and 5 respectively). For all methods in this test case, we used d = C.
As expected, the two leftmost columns Fig. 6 show that ASE and GD (when run until convergence) yield similar results in terms of the overall reconstruction error f M (A X (indicated above each subplot). It is interesting note that GD Armijo required 44, 38 and iterations, respectively, for each of the graphs tested. If we instead GD for 5 iterations only, performance markedly degrades, particularly
14

---

Published in Transactions on Machine Learning Research (05/2025)
10a
ASE
10
ASE
LASE single model
LASE single model
LASE multi model
LASE multi model
[[ oA XXX)
I|M (A XX"
104
10
10a
10
-0.5
0.00
0.05
0.10
-0.05
0.00
0.05 0.10
6
Figure 7: trained with graphs stemming from an SBM with a given I1, inference for graphs following a perturbed SBM with II, II A, where A 81,12 (left) and A = (g8) (right, with a, and e following uniform distribution in [0, can result in poor performance as |ö] increases. On the other hand, including all of these models during training results in remarkably robust LASE, with performance good as ASE for all the considered values of 8.
as the number C' of SBM communities increases (check the third column in Fig. 6 This is not the case for LASE, which offers embeddings of similar quality ASE, except. in the last and most challenging graph SBM-5. Note, however, that LASE reconstruction always significantly better than GD-5 Armijo.
4.1.2 Robustness to distribution shifts
Note that in the previous examples have used graphs stemming from the same distribution both for training well inference. An intriguing question is how robust is LASE to changes in the underlying distribution. To investigate this out-of-distribution generalization issues, we present experiment in which LASE is trained using two approaches. In the first one we consider a single SBM model with C = communities, characterized by a connection probability matrix II, and N1 = 100, with 70% of the nodes Inference then performed on larger graphs with N2 1000 nodes, generated
belonging to community by SBM models with II, II, + A. The proportion of nodes in each community remains consistent with the training setup. We will consider two types of perturbations A. In the first one, we add a constant to all entries of I1; i.c. A 51,17, where the perturbation 8 varies within the range [-0.09, 0.1]. We also consider non-uniform perturbation where A == (g In this case, the perturbation coefficients b, e are sampled from a uniform distribution in the interval [0, 8), and d also varies within the range [-0.09, 0.10).
Reconstruction-crro results corresponding to the uniform (left) and non-uniform (right) case as we vary are shown with orange circles in Fig. 7 Note how the reconstruction cost obtained from this single-model LASE remains very similar to the one obtained by ASE (blue stars in the figure) under small perturbations. However, as the absolute value of the perturbation d increases, thus markedly deviating from the original connectivity matrix II, the resulting error grows and drifts away from that of ASE.
However, the robustness of LASE can be enhanced by exposing it to graphs stemming from multiple of these distributions (parameterized by d). The second training approach, which we will denole as LASE multi model, includes multiple SBM models using II, and Ni = 100, with the same per-class proportion as before. Specifically, the training set includes 500 samples for each II, with taking 11 evenly spaced values within the range [-0.09, 0.09], for a total of T 5500 graph samples. The green triangles in Fig. 7 show how, this case, LASE exhibits marked reduction in cost, matching ASE's performance for all values of 5.
15

---

Published in Transactions on Machine Learning Research (05/2025)
10
time
SVD Truncate
10
Coordinate GD
LASE Full Attention
LASE ER05 Attention
LASE WS03 Attention
LASE BB03 Attention
500
1000
1500
2000
2500
3000
3500
4000
N
Figure 8: Mean wall-clock time for computing ASE, Block Coordinate Descent (a faster version of GD studied in Fiori et al. (2024)) and LASE using full or sparse attention. This last method runs fastest overall, even out performmnn the highly-optimized Graspologic rout used for the ASE eigendecomposition.
4.1.3 Spectral embeddings in large graphs
Consider scenario involving a graph so large that computing the eigendecomposition to form the ASE becomes impractical. For instance, a gencral-purpose PC may struggle to compute the ASE of moderately- sized graph with approximately N = 10, 000 (or more) nodes. In such cases, it essential that LASE's computational cost scales better with N. This cost primarily depends on two parameters: (i) the number of layers L, which represents the total number of GD iterations we are willing perform; and (ii) the size of the graph N, the central focus of our current discussion.
Training on smaller sampled subgraphs. Leveraging the transferability of LASE, aim at training LASE on smaller portions of the graph that fit within the available computational resources. To illustrate this approach, consider an SBM graph with N = 12, 000 nodes divided into C = 3 communitics. Instead of training LASE, on the entire graph, we randomly select 5% of the nodes and use the induced subgraph for training. training set including T 800 such samples is generated, and the LASE weights are trained to minimize the average cost across all samples; see 14p. In this case, the resulting reconstruction error [Mo (A - )l on the original graph is 4296 for ASE, while LASE trained using this subgraph sampling approach achieves cost of 4498 marginal increase of less than 5%. This stands in stark contrast with the results we discussed in Section 2.2 underscoring the importance of transferability in the LASE architecture, which enables the reuse trained weights for inference on the original large graph.
Sparse attention. The GAT sub-module of LASE may still constitute significant computation bottleneck, since operates using a fully-connected graph linking all nodes. As discussed in Section 3.3] the literature on transfomers addresses this issue by considering so-called sparse attention; i.e. randomly selecting some edges
16

---

Published in Transactions on Machine Learning Research (05/2025)
dataset
N
d
ASE Loss
GD Loss
GD-5 Loss
LASE-5 Loss
Cora
2708
6
101.28
103.50 + 0.01
126.87 + 0.01
102.83 + 0.01
Citeseer
3327
6
98.17
96.07 + 0.01
148.54 + 0.01
102.14 + 0.02
Twitch ES
4648
7
345.95
337.54 + 0.02
356.13
+ 0.01
334.00 + 0.03
Amazon
7650
8
469.74
474.15 + 0.01
502.56 + 0.02
454.23 + 0.02
)I of ASE, GD, GD using only 5 iterations and 5-layered LASE when applied to four real-world nelworks. LASE systematically performs competitively, and as the network size increases it even outperforms the rest of the methods. The standard deviation of the results are also indicated for GD and LASE, illustrating their robustncss to the random input signal.
Table 1:
The resulting loss || (A
of the fully--onnected graph, which may be regarded as another mask |ef. 11 There are several choices for Matt, the most popular being Erdös- Rénssi (ER; i.c., uniformly sampling edges with certain probability). Walls-Strogalz (WS; ie., starting from regular lattice with given degree r, then randomly rewiring edges with a certain probability p) and Big- Big-Bird (BB; i... a combination of ER and a regular lattice).
We test these sparsifying mechanisms on an SBM graph with C = 10 communitics and varying number of nodes N E [500, 4000). Parameters of the sparse attention approaches were chosen so that the resulting sparsity Patt E {0.1, 0.3, 0.53. For each mechanism we report the time corresponding to the smallest Patt that resulted in a total loss that is within 5% of the one obtained with full attention (itself, and like in the previous sections, almost identical to the one obtained through traditional ASE). This resulted in mean degree of half of the original fully-connected graph for the ER mechanism. whereas only a third was enough for both WS and BB. Accordingly, we find that pure randomness is detrimental for attention.
Inference times are reported in Fig. B Each point in the graph is the mean wall-clock time over 10 independent trials, and the bands around the curves indicate one standard deviation. When using sparse attention mechanisms, inference time is halved with respect to full attention. Furthermore, we have included two references for comparison. Firstly, variant of the GD method introduced in (Fiori el al., 2024 which uses Block Coordinate Descent and is faster than vanilla GD for this node embedding problem. Note how LASE is roughly an order of magnitude faster than even this variant of GD. Secondly, we have also included the computation time for ASE, estimated through Graspologic, which uses highly-optimized routines for the eigen-deoomposition of the adjacency graph (SVD Truncate in Fig. S.. Note how either BB or WS (recall that in this case both use a sparsity of 30%) result in faster inference times than this highly-optimized library. We reiterate that all cases, the total resulting cost is within 5% of the one obtained by Graspologic.
4.1.4 Embedding real-world networks
Here we asses LASE's ability to approximate node embeddings for real-world graphs. For instance, let us consider set of networks typically used as benchmarks in several learning tasks: Cora (Yang et al. 2016) Citeseer Yangg et al. 2016). Twitch ES (Rozemberezki et al. 2021). and Amazon Photo (Shchur et al. 2018). The Cora dataset is a collection of N 2708 scientific publications. The connections between these publications correspond to a citation, resulting in 5429 links. The Amazon Photo network is a collection of N = 7650 products, where the 238,162 connections signify that the corresponding products are frequently purchased together. The Citeseer dataset is a citation network of N = 3327 publications, where nodes represent rescarch papers and the 9104 odges denote citation relationships between them. Finally, the Twitch ES dataset is a network of N 4648 Spanish-speaking Twitch users, where nodes represent gamers and an edge exists if they follow each other (with total of |1| 123, 412).
We are interested in computing the spectral embeddings of the underlying graphs, and as before we will compare ASE, GD, GD using only 5 iterations, and LASE with L = 5. We train LASE using T = 1000 sampled subgraphs of the original one, uniformly chosen at random so that approximately 300 nodes are retained in each of them. Full attention is used except for the Amazon network, which used WS attention (with r = 0.1 and p = 0.1). The resulting reconstruction errors are reported in Table Note how LASE with limited depth performs comparably to the GD algorithm run until convergence. Interestingly, for the two
17

---

Published in Transactions on Machine Learning Research (05/2025)
LASE Cost. Function
125
102.83
103.58
104.75
105.62
90
120
103.5 39
104.40
103-77 77
112.70 79
11.7 66
115
102
103.13
10
103.05
110
122
125
103 28
110.53 53
102.43
102.76
105,00
105
Figure 9: The resulting loss | (A - XQX of LASE on the Cora dataset, evaluated across different combinations of embedding dimension d and number of layers L (shown in the and y axis, respectively). Except for few pathological cases, the resulting loss exhibits limited variability with respect to L and
ASE
LASE single model
[M MA XQX!
LASE multi model
10a
10a
0.000
0.005
0.010
0.015
0.020
When trained on graphs from single model (e.g., the Cora dataset), inference on graphs generated by modifying the original structure- through random edge additions and deletions with probability 8 degrades as increases. In contrast, training on a diverse set of such graph models significantly enhances the robustness of LASE, yielding performance comparable ASE across all tested values of 6.
Figure 10:
largest graphs, but specially in the case of Amazon, LASE outperforms GD. The standard deviation of the results are also displayed for GD and LASE, since they both depend on the random mnitialiaation/ippl /input. The low variability for all of these methods confirms their robustness and ability attain the global optimum.
Robustness to hyperparameter selection. We also examine the effect of the chosen hyperparmeters in the resulting loss. Figure g depicts the results of such analysis for the Cora dataset. We have trained and evaluated LASE for grid of values of the only two hyperparameters of the architecture (d and L). Apparently, the model is fairly robust to modifications of these hyperparamter values.
Robustness to graph perturbations. Mimicking the experiments we carried out in Section 4.1.2 but now for the real-world datasets, here we verify the robustness of LASE to perturbations on the underlying network. Starting from the Cora dataset, we have randomly added and removed links with a certain probability 5. Results, shown in Fig. 10 consistent with previous findings. While inference of LASE the
18

---

Published in Transactions on Machine Learning Research (05/2025)
Year
d
ASE
GD
LASE-20
1960
154
0.115
4
23.98
18.00 + 0.01
18.81 + 0.08
1970
194
0.124
4
30.89
20.79
0.01
21.85 + 0.04
1980
257
0.102
4
35.17
20.71
+ 0.01
22.04 + 0.11
1993
248
0.108
4
30.10
13.56
0.01
15.35 = 0.10
2004
283
0.091
4
36.34
20.98
= 0.01
23.06
= 0.18
2017
324
0.096
4
45.96
30.08
0.01
31.64 + 0.15
Table 2:
The resulting loss, |M (A - -XQ I[.: for both GD and LASE-20 is evaluated across different
years of the UN General Assembly dataset. The proportion of unknown votes in each case is denoted by p.
perturbation increases yields a noticeable degradation, including graphs stemming from these perturbed distributions in the training set (i.e., multi-model training) results in performance that close matches ASE,
Missing edge data. Finally, let consider the problem of embodding network with unknown edges. To this end, we use United Nations (UN) General Assembly voling data (Voeten et al. 2009). This dalaset contains every roll call in the history of the UN General Assembly, including which of the member countries were present (or not) during its voting session, and which was the country's vote (either 'Yes', 'No', or 'Abstain"). We thus construct a graph for each year, where a node represents a roll call or a country. A link between two nodes included if the corresponding country voted affirmatively for the corresponding roll call; i.e., we build a bipartite graph connecting countries and roll calls. When a country was absent or abstained from voting, we will consider that the corresponding edge is unknown. The evaluation of [M (A - XQXT)] corresponding to the estimation of X for ASE, GD and LASE architecture with 20 layers, corresponding to six years across several decades, is shown in Table 2 details of the graph for each year). The column denoted by p indicates the proportion of unknown edges (from all potential votes) in the given graph. Note how LASE exhibits similar performance to GD, while ASE cannot recover accurate embeddings. Indeed, ASE's total loss typically 50% over that of GD.
(sce Appendix AA.4 for further
4.2 End-to-end graph representation learning for link prediction and node classification
Having shown the computational advantages of LASE over GD or ASE during inference, let now assess the performance of LASE E2E. Its merits will be evidenced in two scenarios. Firstly, when PEs are required, LASE E2E attains the same (or better) performance than if the PEs were precomputed and used along the node attributes, thus effectively rendering the precomputation step unnecessary. Secondly, if the graph has a negligbiee amount of unobserved edges (typical in several applications, such as recommender systems or the UN test case we study in Section 4.2.1 ; the ability of LASE E2E to accommodate those also translates to performance gains that may be significant. In the sequel, we illustrate these advantages in two widespread (asks using real-world datasets: link prediction and node classification.
4.2.1 Link prediction
We return to the UN General Assembly voting data, where we now include nodal signals (attributes) Xin- Regarding the roll calls, the publishers of the dataset have classified them into six categories (proposals related to the Palestinian conflict, colonialism, human rights, etc.). The signal on each node will be a 12-dimensional onc-hot encoding indicating in the first six dimensions the continent to which the country belongs to, and in the rest the category of the roll call.
We consider six randomly selected countries for which we have randomly chosen 30% of the roll calls (among those it voted) for prediction. They are thus also tagged unknown in the mask matrix Mobs- For the LASE E2E we use LASE block (with L = 10 and d 4), the output of which is concatenated to the node attributes Xi., which are then processed by a two-layer GNN to produce link predictions Á (sce Fig. 11 The combined loss utilized for this link prediction task is given by
L(HONN, HLASE) pCrossFanroppy A) + (1 [-] (A XQX I1,
(16)
19

---

Published in Transactions on Machine Learning Research (05/2025)
LASE E2E Link prediction
X
ML.
Enceder
eebclliig
Decoder
Aggragaee
Sigmaid
MLP
X LiKE
Negative secapling
Figure 11: LASE E2E architecture for link prediction. Instead of training LASE separately from the link prediction task, we train LASE module along with GNN so that loss combining both reconstruction and prediction errors is minimized.
To assess the benefits of the E2E architecture, we compare against more traditional way of using spectral PEs; i.e., concalenating precomputed spectral PEs obtained from ASE LASE to the input signal Xin- We have also included the results when not using PEs at all; i.., using only the 12-dimensional one-hot encoding signal input to the GNN. Finally, also compare against the state-of-the-art approach PowerEmbed (Huang
ct al.
2022 : see Section for detailed discussion of this and other related methods.
Figure 12 shows the results for the same years we considered in Table in the form of a boxplot of the resulting iink-predctton accuracy. Each daturn in the boxplot corresponds to one of ten experiments (where we have randomly picked the countries and the roll calls be predicted). The first thing to observe is that the incorporation of spectral PEs by itself leads to considerable improvement in prediction accuracy in several years (c.g., 1970 2004). This is in line with the discussion in Section 2.2 illustrating in real-life problem the need for PEs and the inability of GNNs to produce this information under certain inputs. Each such experiment includes different countries (and hence votes), so one expects a non-negligible variability in the results. Some countries' voting patterns are aligned with allics (in which case the spectral PEs should be quite informative), whereas others are more isolated and their votes will be harder to predict.
The second aspect to highlight in Fig. 12 is that in several years, using ASE as a PE results in an accuracy which may be significantly less than both LASE PE its E2E variant; in particular the years 1993 2017. PowerEmbed exhibits similar performance to ASE for these years. This is somewhat expected since, as explained in Section 5 PowerFmbedd is based on the power method to compute the dominant eigenvectors, although it also includes an Inception network (Szegedy et al. 2015)) which considers all the power iterations in its predictions. In any case, these results illustrate the importance of properly considering unknown edges in the model when computing PFs, an impossibility for ASF that requires the eigendecomposition of a fully- observed adjacency matrix.
interesting that for the year 1980, where using the PEs or not results similar accuracy, the method that performs best is PowerEmbed. This may be indicative that the actual graph structure is not important in the rest of the years (while the input signal is informative enough), and the Inception layer learns to ignore the higher-order powers. This observation is further explored in Section 4.2.2 when we shift focus to node-level prediction tasks.
The final noteworthty conclusion that can be drawn from Fig. 12 that LASE E2E obtains competitive results when compared to LASE as a precomputed PE, even surpassing it in some instances (c.g., the years 1993 2004). We remark that for the E2E variant a single training is necessary, resulting in less computational overhead and without sacrificing overall performance.
20

---

Published in Transactions on Machine Learning Research (05/2025)
1900
1900
0.0
2,500
0,8
0.70
0.70
663
LASE
PW arts
shi
ARR
LAEE
LASE Eat
PW Ang
1.00
0.6
0.00
0.00
0,30
0.70
0.80
6.70
ABESPE
LASR SPR
LASE Ea
PW Aspb
SPE
SPE
PW A.PRE
LASE
LASE
20H
2017
0.5
0,80
0.78
8.
SPE
LASE she
LAkE E3e
PW w0
ASe SPD
LASE
LASE Bne
PW APE
Figure 12: Accuracy in prodicting the votes during six years of randomly chosen countrics of the UN General Assembly. The evaluated methods include not using PEs at all, using either ASE or LASE as spectral PEs, the E2E architecture discussed in Section 3.4 and the PowerEmbed method (Huang et al. 2022). Not using PE typically exhibits the worst performance, as verified for all years except 1980. The E2E architecture typically outperforms all other methods for the rest of the years (c.g. 1993, 2004 and 2017), or is at least very competitive. This performance gain comes at computational cost. similar to that of using spectral PEs, since no pre-computations required.
4.2.2 Node classification
Moving on to node classification, we evaluated the performance of LASE F2E by considering the same four real-world network datasets in Section 4.1.4: Cora, Citeseer, Twitch ES and Amazon. We now also include node signals X,, for each network, and the goal is to predict the category for each node. For Cora, node features consist of 1433-dimensional one-hot word vector, its entries indicating the presence or absence of certain word in the publication, and each publication is categorized into one of seven classos. In Amazon, node features also consist of a one-hot word vector encoding product reviews, in this case of 745 dimensions indicating the presence or absence of a certain word. Each product assigned a label corresponding to one of eight product categories. In the Citeseer network, node features are represented as 3703-dimensional one-hot word vectors, indicating the presence or absence of specific words in paper's content, with each paper categorized into of six predefined classes. Finally, the Twitch ES dataset encodes node features
21

---

Published in Transactions on Machine Learning Research (05/2025)
LASE end-to-end Node classifier
X
MLP
GNN
X
LAN
Figure 13: LASE E2E architecture for node classification. The output of a LASE block is concatenated to the node features, but crucially the system is trained end-to-end using a loss that encompasses both reconstruction and classification.
P
No PE
ASE PE
LASE PE
LASE E2E
PowerEmbed RW-10
0
86.8
+ 0.4
86.5 + 0.6
86.4 + 0.3
86.9 + 0.3
85.0 + 0.4 (*)
0.2
84.6 + 0.3
85.0 + 0.5
85.8 + 0.3
85.8 + 0.6
84.2 = 0.5
0.4
83.1 + 0.3
83.2 0.5
84.3 0.4
85.4 0.5
82.7 = 0.4
0.6
79.3
+ 0.5
79.0 + 0.3
83.2 + 0.6
85.5 0.6
81.6 = 0.5
0.8
73.8
+ 0.8
73.0 + 0.6
79.6 + 0.4
84.6 0.5
79.1 = 0.7
Table 3: Mcan accuracy + standard deviation over 10 data splits for the CORA network with different proportions of missing edges The results with (*) corresponds to PowerFmbed(Tapp)-1 taken from Huang et al. 2022) which uses the Laplacian matrix and 10 iterations.
dense 128- 28-dimensional embeddings that capture information about games liked, user location, and streaming habits, and the primary (binary classification) task is predict whether a user streams mature content.
Here, the E2E LASE architecture consists of I. = 5-layer LASE block (with dimensions d = for CORA, d d= 8 for Amazon, d for Citescer, and d for Twitch), whose output is concatenated with the node attributes Xin These were then processed by three-layer GAT to produce node classifications through a softmax function (see Fig. 13 The resulting model was trained to predict among the different classes by minimizing the combined loss function given in (15), which includes a cross-cntropy and reconstruction loss I weighted by a lyper-parameter μ. In terms baselines, we will again consider a GNN with no PEs as well as using precomputed PEs obtained through ASE, a pre-trained LASE and PowerE
Table reporrts the results on the Cora dataset. In particular, each row corresponds to different proportion of missing edges (indicated in the first column parameter p). Note how LASE E2E systematically obtains the best results, above PowerEmbed with = 0 even with up to 60% of unknown edges. Using pretrained LASE PÉs also yields competitive results, since it can account for unknown edges unlike the vanilla ASE, This explains the latter's rapid degradation as increases. We also find that not using any PE performs similarly to using ASE. Again, as the number of unknown edges increases and thus the structural information is progressively lost, the capacity of LASE to provide good approximations of the actual PEs plays key role in its consistent performance. As further verification at hand, we trained 2-layered fully connected NN with hidden dimension of 64, using only the node features as input. The resulting performance is 75.2 + 0.6, significantly lower than the rest of the evaluated methods.
the importance of the connectivity in the problem
Let us now turn our attention to the Amazon dataset. Table shows the same comparison as before. Again, LASE E2E obtains the best results overall, even it is using sparse attention (in this case a WS with r = 0.1 and p 0.1). However, is interesting to highlight that the degradation in performance as p increases is not as significant before- both for ASE and when we do not use any PE. This suggests that the actual structure of the graph is not important as the input features. This is verified when we train simple fully-
22

---

Published in Transactions on Machine Learning Research (05/2025)
No PE
ASE PE
LASE PE
LASE E2E
PowerEmbed RW-10
94.3 + 0.6
93.9 + 0.6
94.2 0.6 (*)
94.4 + 0.4
94.2 + 0.2 (**)
0.2
94.2 + 0.4
94.0
+ 0.5
93.7 0.8 (*)
94.3 + 0.6 (*)
94.1 + 0.2
0.4
93.9 + 0.7
93.6 + 1.5
93.8
(*)
94.0 + 0.3 (*)
93.8 + 0.2
0.6
93.5
- 0.6
08.1 (
94.0 + 0.6
93.7 + 0.2
0.8
92.9
+ 0.7
92.9
12.90000
92.6 = 0.7 (*)
93.3 + 0.6
93.0 + 0.2
Table 4: Mean accuracy + standard deviation over 10 data splits for the Amazon Photo network with different proportions of missing edges p. The results marked with (*) were trained using sparse attention WS with 0.1 and p 0.1 instead of full ottention. The results with (**) corresponds to PowerEmbed
taken from Huang et al. (2022) which uses the Random Walk matrix and 2 iterations.
connected NN model with 2-layers (with a hidden dimension of 64) for this dataset. This network-agnoslic architecture obtains a mean accuracy of 91.7 0.2. A similar behavior was verified for both the Citeseer and Twitch ES, whose results are reported in Appendix A.3
5 Related Work
Leveraging the power method to learn spectral embeddings. One set of works related to ours aims to compute spectral embeddings through GNN iterations that can express the dominant eigenvectors of the
graph shift operator. The PowerEmbed method (Huang et al., 2022) based on spectral decomposition of the adjacency matrix, similar to the RDPG model in this paper, but only taking into account the eigenvectors. Inspired by the power method that is known to converge to the dominant eigenvectors, [uang et al. (2022) propose a normalization step after each GNN iteration, resembling the mentioned power method. The processed oulputs of each layer are then concatenated and used for downstream node classification tasks a so-called Inception layer (Szegedy et al., 2015)]. Since the method is initialized with the node features, initial layers retain this local information, while the final layers capture global spectral properties of the graph as the power iteration converge. A follow-up related paper inspired is (Eliasof et al.) 2023), which instead of initializing the model with node features as in PowerFmbed, it uses random values. The procedure is similar, alternating a normalization step after some iterations. Eliasof ct al. (2023) also propose to learn graph-dependenl propagation operator. Unlike these approaches that are inspired by the power method, the LASE architecture mimics GD iterations through an algorithm unrolling principle.
On the expressive power of GNNs. The expressive power of GNNs has been the subject of much rescarch interest over the last few years. In particular, useful links drawn between the classic Weisfeiler-Leman graph isomorphism test and the pusssag--aasingg GCN have shed light on the incapacity of this class of GNNs to distinguish between some graphs which are structurally different (Xu et al. 2018). These (and other related) findings have motivated host of alternative GNN architectures with increased expressive power; see e.g., (Sato 2020 Morris et al. 2024) and references therein.
Instead of modifying the architecture, an alternative to remedy the GCN's inability to distinguish between some non-isomorphic graphs is to endow each node with additional signals (i.e., features or attributes) to break structural symmetries leading to ambiguities. Farly works advocated using a unique identifier for each node, via one-hot encoding or a randomly generated label. While simple, these schemes seriously limit the transferability of the learned architecture to other graphs, and may lead to functions that are not equivariant to node permutations (Vignac et al. 2020). This has motivated the use of PEs (Srinivasan & Ribciro 2020 Rampášck et al. 2022). some of which we have already discussed in the precoding experiments. PEs, which may be interpreted as capturing global information of the graph, is to use methods based on sub-graphs, such as encoding an ego-net around each node (Zhao et al,, 2022 Bouritsas al. )023). Substructure-baste methods offer an attractive tradc-off due to their moderate computational and memory requirements, plus they have been shown to effectively address certain limitations of approaches that rely on random signal injection. A detailed comparison with subgraph-based mot
An alternative to these spectral-
23

---

Published in Transactions on Machine Learning Research (05/2025)
in end-to-end tasks remains an interesting direction for future work, particularly to explore the potential benefits of combining both local and spectral PFs.
On & related note, we comment on the implications of the anonymity of the input signal on a GNN's ability to discriminate nodes. Specifically, as discussed in KKnnasoulii & Ribeiro 2024), to evaluate the ability of GNN to differentiate nodes, one should feed the network with a signal that is not discriminative by itself. Otherwise, one will not be able to tell if the GNN can solely produce such a discriminative output. Kanatsoulis & Ribeiro (2024) prove that under mild assumptions, GNN with anonymous input produces different outputs for two graphs with different spectral properties. This is somehow related to our analysis in Section 2.2 but in their work, the authors discuss this phenomenon for two different graphs, while we focus the analysis for a given graph, distinguishing nodes in it. Although these interesting ideas could be adapted to our case, as we show in Appendix [A.2] there are pitfalls with, e.g., symmetric SBMs. Another related work, but also devoted to distinguishing graphs, is (Puny et al., 2020). Therein, an attention mechanism is added to the Random GNN (Sato et al.] p021p, and it is proved that this aligns with the 2-Folklore Weisneiler-Lehman algorithm.
Graph auto-encoders. Since LASE computes node embeddings from which it is possible to approxi- mately reconstruct a given adjacency matrix, we can frame our work in the graph auto-encoder context; see e-g. [Hamilton| 2020) and the comprehensive review in (Chami et al. 2022). The classical (non-probabilistic) graph encoder (Kipf & Welling 2016) proposes to compute embeddings X using a GCN with the fea- tures and graph structure as inputs (the encoder), and then reconstruct the adjacency matrix via an outer product decoder XXT. which resembles the RDPG model at the heart of our approach. Follow-up works such as (Ma et al., 2021 also use a GCN encoder, which, according to the discussion presented in Section 2.2 may fail to distinguish nodes with similar local structure. In (Salehi & Davulcu 2020), the authors propose to add a self-attention mechanism to the encoder, but their different goal is to reconstruct the features, and the method does not output a reconstruction of the graph structure using the latents.
Algorithm unrolling for GRL. Lastly, our method is based on the algorithm unrolling paradigın (Monaa ett al. 2021: Gregor & LeCun 2010 Sprechmann el. al. 2015). In their seminal paper, Gregor & LeCun (2010)
made an important connection between iterative optimization methods and NNs; see also our brief review of this work in Section 2.3 Although there is an emerging interest in applying those ideas to inverse problems
graphs such as network topology inference (Shrivastava el al. 2020 Wasserman el al. 2023 Pu et al.. 2021
Wasserman& & Mateos 2024), source localization (Ye & Mateos 2022), or signal denoising (Nagabama et al,
2022 Chen et al.
2021), to the best of our knowledge this is the first adaptation to GNNs for computing
node embeddings, given the graph structure.
6 Discussion and Future Work
We proposed LASE, a parametric model capable of learning to approximate the ASE of a given graph in an unsupervised fashion, even in cases where GNNs fail at this GRL task. The novel architecture is based on the unrolling of a GD algorithm that solves matrix factorization formulation of the ASE problem. This unrolling process leads to deep model, where each layer (or LASE block) consists of a superposition of GCN and GAT sub-modules. Interestingly, by default the GAT modules operate on fully-connected graph, with attention coefficients equal to the inner product between the incident nodes' embeddings. We empirically demonstrated that few layers (in comparison to the iterations needed for GD to converge) of a trained LASE ASE gold standard
suffice to output embeddings whose accuracy is on par with the eigendecomposiiion-bee even when the given graph has unobscrved edges. Regarding scalability, we proposed an efficient training scheme using randomly sampled sub-graphs from the target (large) graph we wish to embed. This technique together with sparse attention mechanisms, allowed us to infer accurate spectral embeddings faster than highly-optimized eigensolvers in scientific computing librarics, or, other state-of-the-art iterative methods.
In addition to their adoption for clustering or other network-analytic lasks (e.g,, visualization), spectral embeddings have been popularized as PEs. For this use case, spectral embeddings are typically precomputed and concatenated with any available node features before being fed to a GNN, whose output is used for downstream tasks such as node classification. We have verified how, as expected, the LASE PEs are as useful as those obtained via ASE, again with the added robustness benefit of tolerating significant number
24

---

Published in Transactions on Machine Learning Research (05/2025)
of unknown edges. Another one of our significant contributions is to demonstrate that LASE can also be used in an end-to-end fashion. Since LASE is a fully differentiable parametrie function, we can embed it within a larger GRL pipeline and train the whole system using an augmented loss that combines prediction and rcconstruction terms. The GNN's input is a concatenation of the output of LASE and the nodes' features, all in all resulting in a fully learnable PE architecture. Crucially, this eliminates the need for precomputing spectral PEs, achicving a prediction accuracy that is either superior to or competitive with methods requiring such computationally taxing offline step.
LASE opens up several research avenues, of which we highlight some of the most intriguing ones here. Firstly, the LASE architecture follows very closcly the GD algorithm it was inspired from. For instance, we have not used any form of non-linearity in our basic model. Interleaving non-linear activations may increase the system's expressivity, generate sparsity in the GAT sub-module, or even mimic second-oree optimization methods. Other modifications, such as skip connections mirroring momentum- based algorithms, may further reduce the number of layers required in LASE. We stress that is the algorithm unrolling principle that facilitates all these interesting potential links with advances in optimization theory and algorithms.
Secondly, there are several properties of LASE that we have empirically verified but deserve theoretical study. For instance, the transferability of the learned weights in LASE that we used when training in smaller sub-graphs is based on the fact that (with the proper normalizations); the optimum of the reconstruction cost in the original and smaller graphs should coincide, in expectation. However, a more precise analysis of the impact on LASE's parameters of this method, or assessing the transferability between graphs with different spectral properties, is in order.
Furthermore, have not considered directed graphs. In this case, the nodal representation includes two vectors, modeling the outgoing and incoming behavior of each node. Interestingly, these spectral embeddings can also be computed through a first-order iterative algorithm, although in this case it is necessary to consider certain Riemannian manifold constraints (Fiori et al. 2024). Taking an unrolling perspective on this method is clearly an interesting, albeit challenging, task that is part of our ongoing research agenda.
Finally, LASE (and its E2E variant) has broadened the applicability of ASE by showing that it can be an inductive, efficient alternative to the latter. In particular, demonstrated its validity as (lcarnable) PE and have shown promising results when compared to the PowerEmbed baseline. An interesting avenue of future research would be to further expand these comparisons to include other non-spectral PEs, that exhibit tatte-of-theaar performance in established downstream tasks such as node classification and link prediction.
Acknowledgements
Work in this paper was supported in part by CSIC (I+D project 225202201000766UD)
References
Ralph Abboud, ismail ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proc. Intl. Joint Conf. Artifical Intelligence, 2021.
Avanti Athreya, Donniell E. Fishkind, Minh Tang, Carey E. Priebe, Youngser Park, Joshua T. Vogelstein, Keith Levin, Vince Lyzinski, Yichen Qin, and Daniel L Sussman. Statistical inference on random dot product graphs: A survey. J. Mach. Learn. Res., 18(1):8393- 88844, Jamuary 2017. ISSN 1532-4435.
Amir Beck and Marc Teboulle. A fast iterative shrinkage-thrrebooddngg algorithm for linear inverse problems.
SIAM J. Imaging Sci., 2(1):183-20) 2022, 2009.
Srinadh Bhojanapalli, Anastasios Kyrillidis, and Sujay Sanghavi. Dropping convexity for faster semii cemi-definite optimization. Proc. Conf. Learn. Theory, pp. 530-582, 2016.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeirion, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEFE Trans. Pattern Anal. Mach. Intell., 45 (1):657-66) 668, 2023.
25

---

Published in Transactions on Machine Learning Research (05/2025)
Semih Cantürk, Renming Liu, Olivier Lapointe-Gagia Vincent Létourneau, Guy Wolf, Dominique Beaini, and Ladislav Rampášek. Graph positional and structural encoder. In Proc. Inl. Conf. Mach. Learn., pp. 5533 5566, 2024.
Tnes Chami, Sami Abu-El-Haija, Bryan Perozzi, Christopher Ré, and Kevin Murphy. Machine learning on graphs: A model and comprchensive taxonomy. J. Mach. Learn. REs., 23(89):1-64, 2022.
Siheng Chen, Yonina C. Eldar, and Lingxiao Zhao. Graph unrolling networks: Interpretable neural networks for graph signal denoising. IEEE Trans. Signal Process., 69:3699-3713, 2021.
Yuejie Chi, Yue M. Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix factorization: An overview. TEEE Trans. Signal Process., 67(20):5230-54 5269, 2019.
Jaewon Chung, Benjamin D. Pedigo, Eric W. Bridgeford, Bijan K. Varjavand, Hayden S. Helm, and Joshua T. Vogelstein. GraSPy: Graph statistics in Python. J. Mach. Learn. Res., 20(158):1-7, 2019.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In Proc. Inl. Conf. Learn. Represenla- tions, 2022.
Moshe Fliasof, Fabrizio Frasca, Beatrice Bevilacqua, Fran Treister, Gal Chechik, and Haggai Maron. Graph positional encoding via random feature propagation. In Proc. Int. Conf. Mach. Learn., pp. 9202-9223, 2023.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Marcelo Fiori, Bernardo Marenco, Federico Larroca, Paola Bermolen, and Gonzalo Mateos. Gradient-based spectral embeddings of random dot product graphs. IEEE Trans. Signal Inf. Process. Netw., 10:1 16, 2024.
Karol Gregor and Yann LeCun. Learning fast approximations of sparse coding. In Proc. Int. Conf. Mach. Learn., 2010.
William L. Hamilton. Graph representation learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 14:1-159, 2020.
Peter Hoff, Adrian E Raftery, and Mark S Handcock. Latent space approaches to social network analysis. J. Am. Stot. Assoc., 97(460):1090 1098, 2002.
Ningyuan Teresa Huang, Soledad Villar, Carcy Pricbe, Da Zheng, Chengyue Huang, Lin Yang, and Vladimir Braverman. From local to global: Spectral-inspired graph neural networks. In NewrIPS Workshop on New Frontiers in Graph Learning, 2022.
Elvin Isufi, Fernando Gama, David Shuman, and Santiago Segarra. Graph filters for signal processing and machine learning graphs. IEEE Trans. Signal Process., pp. 1-32, 2024.
Charilaos I Kanatsoulis and Alejandro Ribciro. Graph neural networks are more powerful than we think. In Proc. Inl. Conf. Acoustics, Speech, Signal Process., pp. 7550-7550
2024.
Nicolas Keriven and Samuel Vaiter. What functions can graph neural networks compute on random graphs? the role of positional encoding. In Proc. Adv. Neural. Inf. Process. Syst., volume 36, 2023.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. In NewrIPS Workshop on Bayesion Deep Learning, 2016.
Derek Lim, Joshua David Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanic Jegelka. Sign and basis invariant networks for spectral graph representation learning. In Proc. Int. Conf. Learn. Representations, 2023.
26

---

Published in Transactions on Machine Learning Research (05/2025)
Mingyuan Ma, Sen Na, and Hongyu Wang.
AEGCN: An autocnccoderrconnssraandd graph convolutional
network. Newrocompuling, 432:21-31, 2021.
Abram Magner, Mayank Baranwal, and Alfred O. Hero. The power of graph convolutional networks to distinguish random graph models. In Proc. IEFE International Symp. on Information Theory, pp. 2664- 2669, 2020.
Bernardo Marenco, Paola Bermolen, Marcelo Fiori, Federico Larroca, and Gonzalo Mateos. Online change point detection for weighted and directed random dot product graphs. JEEE Trans. Signal Inf. Process. Netw., 8:144-159, 2022.
Vishal Monga, Yuclong Li, and Yonina C. Eldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. IEEE Signal Process. Mag., 38(2):18 44, 2021.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe, Weisfeiler and Leman go neural: Higher-order graph neural networks. In Proc. AAAI Conf. Artif. Intell., 2019.
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fcy, and Karsten Borgwardt. Weisfeiler and Leman go machine lcarning: The story far. J. Mach. Learn. Res., 24(1), March 2024. ISSN 1532-4435.
Masatoshi Nagahama, Koki Yamada, Yuichi Tanaka, Stanley H. Chan, and Yonina C. Eldar. Graph signal restoration using nested deep algorithm unrolling. IEEE Trons. Signal Process., 70:3296-3311, 2022.
Xingyue Pu, Tianyue Cao, Xiaoyun Zhang, Xiaowen Dong, and Siheng Chen. Learning to learn graph topologics. In Proc. Adv. Neural. Inf. Process. Syst., 2021.
Omri Puny, Heli Ben-Hamu, and Yaron Lipman. Global attention improves graph networks generalization. In ICML Workshop on Graph Representation Learning and Beyond, 2020.
Ladislav Rampášck, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for general, powerful, scalable graph transformer. Proc. Adv. Neural. Inf. Process. Syst., 35:14501-1445 14515, 2022.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. J. Complex Networks, 9(2), May 2021.
Patrick Rubin-Delanchy, Joshua Cape, Minh Tang, and Carey E Priebe. A statistical interpretation of spectral embedding: the generalised random dot product graph. J. R. Stat. Soc. Ser. B Stat. Methodol, 84(4):1446-1473, 2022.
Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro. Graphon neural networks and the transferability of graph neural networks. In Proc. Adc. Neural. Inf. Process. Syst., volume 33, pp. 1702 1712, 2020.
Luana Ruiz, Ningyuan Teresa Huang, and Soledad Villar. A spectral analysis of graph neural networks dense and sparse graphs. In Proc. Int. Conf. Acoustics, Speech, Signal Process., pp. 9936-9944 2024.
Amin Salehi and Hasan Davuleu. Graph attention auto-encoders. In Proc. IEEE Inll. Conf. Tools with Artificial Intelligence, pp. 989 090-999,9200 2020.
Ryoma Sato. A survey on the expressive power of graph neural networks. orXiv preprint arXiw:2003.04078, 2020.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. Proc. SIAM Intl. Conf. Data Mining, pp. 333-341, 2021.
Edward R Scheinerman and Kimberly Tucker. Modeling graphs using dot product representations. Comput. Stat, 25:1-16, 2010.
27

---

Published in Transactions on Machine Learning Research (05/2025)
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. In NeurIPS Workshop on Relational Representation Learning, 2018.
Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjin Wang, and Yu Sun. Masked label predic- tion: Unified message passing model for semi-supervised classification. In Proc. Inll. Joint Conf. Artifical Intelligence, 2021.
Harsh Shrivastava, Xinshi Chen, Binghong Chen, Guanghui Lan, Srinvas Aluru, and Le Song. GLAD: Learning sparse graph recovery. In Proc. Int. Conf. Learn. Representations, pp. 1-22, 2020.
Pablo Sprechmann, Alexander M. Bronstein, and Guillermo Sapiro. Learning efficient sparse and low rank models. IEEE Trans. Pattern Anal. Mach. Intell. 37(9):1821-1833; 2015.
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. In Proc. Int. Conf. Learn. Representations, 2020.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions In IEEE Conf. Computer Vision and Pattern Recognation, pp. 1-9, June 2015.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liø, and Yoshua Bengio. Graph attention networks. In Proc. Int. Conf. Learn. Representations, 2018.
Clement Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural In Proc. Adv. Neural. Inf. Process. Syst., volume 33, pp.
networks with structural 14143 14155, 2020.
Erik Voeten, Anton Strezhnev, and Michael Bailey. United Nations General Assembly Voting Data. Harvard Dataverse, 2009. https://doi.org// http///di..r////911////// 1...7911//VV/LEJUQZZ
Ulrike von Luxburg. A tutorial spectral clustering. Stat. Compul., 17(4):395 416, 2007.
Trung Vu and Raviv Raich. Exact lincar convergence rate analysis for low-rank symmetric matrix completion via gradient descent. In Proc. Int. Conf. Acoustics, Speech, Signal Process., pp. 3240 3244, 2021.
Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. In Proc. Int. Conf. Learn. Represenlations, 2022.
Max Wasserman and Gonzalo Matcos. Graph structure learning with interpretable Bayesian neural networks. Trans. Mach. Learn. Res., 2024.
Max Wasserman, Saurabh Sihag, Gonzalo Mateos, and Alejandro Ribeiro. Learning graph structure from convolutional mixtures. Thans. Mach. Learn. Res., 2023.
Fangzheng Xie and Yanxun Xu. Efficient estimation for random dot product graphs via a one-step procedure. J. Am. Stet. Assoc., 1186541)6511-664 2023.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proc. Inl. Conf. Learn. Representations, 2018.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In Proc. Inl. Conf. Mach. Learn., June 2016.
Chang Ye and Gonzalo Matcos. Learning to identify sources of network diffusion. In Proc. of European Signal Process. Conf- pp. 727 731, Sep. 2022.
Manzil Zahcor, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslic, Chris Alborti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed. Big Bird: Transformers for longer sequences. In Proc. Adv. Neural. Inf. Process. Syst., 2020.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. In Proc. Int. Conf. Learn. Representations, 2022.
28

---

Published in Transactions on Machine Learning Research (05/2025)
A Appendix
A.1 Graph convolutional filters: A step-by-step derivation
Graph convolutions are defined in terms of the so-called Graph Shift Operator S E RNxX a matrix repre- sentation of the graph G(V,E) that respects its sparsily; i.e. Siy # if (i. E; see e.g, (Isufi et al. 2024). In the main body of the paper we used = = A for illustrative purposes, but other possibilities, such as the Laplacian or their normalized counterparts are also viable choices. Assume that cach node is endowed with a signal (Iin): R, then a first-order graph convolution defined as
(Iout): = (aia)sho +
Σ (ig(Fin) iEV,
where ho, h1 E IR are the filter coefficients. In words, the result of the convolution in given node is linear combination between its own signal and the sum of its neighbors' signals. This can be compactly written in terms of the matrix representation of the graph as
xou = Xin + Sx
where Xin, Xout E N are column vectors including all the nodes' signals. From this perspective, we may re-interpret Sx, as a displaced or shifted version of Xin- Arbitrary filters can be generated by repeatedly multiplying the input signal by S (i.e. repeatedly shifting the signal), resulting in the following general definition of K-th order graph convolution:
Xout Σ
(17)
k=0
By virtue of the Cayley-Hamilton theorem, one has that K S N. This expression can be extended to include multi-dimensional signals. If the input and output signals have Fin and Fout features per node respectively, then X E Nx Fi, and Xout E IR Fout, Fout, resulting in the final form of the graph convolution [cf. [2]
K
Xout Σ S km
(18)
where H₂ E Fou, To interpret 118 notice that the Fout dimensions of the output signal correspond to a linear combination of the Fm dimensions of the shifted input signal, where this last step does not include exchanged information between nodes.
A.2 Graph convolution's output under white Gaussian noise and the symmetric SBM
Assume that in 17 we have that Xin ~ (u, Σ) is white Gaussian noise, i.e., a standard multivariate Gaussian vector with mean =4=0 and covariance Σ = Iy. Recalling the definition of GFT & = V Xm and using basic properties of a Gaussian vector we have that Xin also a standard Normal random vector. Fur- thermore, applying the GFT results discussed in Section 2.2 we conclude that Xout random combination of the eigenvectors vi, weighted by the filter's frequency response i(()s), namely
Xout Σ ((s))
In particular, the j-th coordinate of Xout is zero-mean Gaussian random variable with variance equal to Ein, (v))) where the squaring operation is to be conducted entry-wise. Nole that if vž is a constant vector for all i, then Xout statistically identical for all its entries j. This is precisely the case for the symmetric SBM studied in Example In particular, the dominant cigenvectors are v 0.3 1 and V2 [0.3 12/2/l 0.3 1 Ny2 with eigenvalues of X 0.3 and Xg z 0.2 respectively. The other eigenvalues are orders of magnitude smaller.
29

---

Published in Transactions on Machine Learning Research (05/2025)
P
No
PE
ASE PE
LASE PE
LASE E2E
PowerEmbed RW-10
0
70.9
+ 0.5
71.1 + 0.5
71.4 + 0.4
71.8 + 0.5
71.2 = 0.4
0.2
71.0
+ 0.6
71.5 0.6
70.5
+ 0.5
71.8 + 0.3
71.5 = 0.5
0.4
70.6
+ 0.4
71.0 0.6
71.2 0.5
71.3 + 0.4
71.1 + 0.4
0.6
70.6
0.6
70.7 0.6
70.9 + 0.4
71.0 - 0.3
70.5 = 0.4
0.8
69.9
0.5
70.0
0.5
70.1 0.5
70.3 + 0.3
70.1 = 0.4
Table 5: Mean accuracy standard deviation over 10 data splits for the Twitch ES network with different
proportions of missing edges p. The results with (*) trained using sparse attention WS with 0.1 and p 0.1 instead of full attention. The results with (**) corresponds to PowerEmbed(RW)) taken from
Huang et al. (0222) which uses the Random Walk matrix and 2 iterations.
No PE
ASE PE
LASE PE
LASE E2E
PowerEmbed RW-10
75.0 + 0.2
74.6 + 0.4
74.6 0.3
74.6 + 0.4
73.2 = 0.5 (**)
0.2
73.7 + 0.5
73.8 + 0.4
73.7 + 0.4
73.0 + 0.5
71.8 + 0.5
0.4
73.0
+ 0.5
72.7 + 0.3
72.4 1.44
72.7 + 0.7
71.1 + 0.8
0.6
72.3
+ 0.6
71.9 + 0.7
72.3 + 0.5
72.4 = 0.5
71.2 + 0.5
0.8
71.8
0.4
71.1 = 0.3
71.9 = 0.7
71.0 + 0.2
70.0 + 0.5
Table 6: Mcan accuracy standard deviation over 10 data splits for the Citesoer network with different
proportions of missing edges p. The results with (*) trained using sparse allention WS with 0.1 and p 0.1 instead of full attention. The results with (**) corresponds to PowerEmbed(RWW)2 taken from
Huang et al. (0022) which uses the Random Walk matrix and 2 iterations.
In this context, consider the idea (Kanatsoulis & Ribeiro 2024). In order to avoid random outputs, they work with the output signal's variance instead, which is then fed to GNN. Accordingly, for the symmetric SBM of Example we obtain
N
Σ RROAVVV (h3(0.3) + (0.2)) x 0.09 x 1n.
which is a constant, and thus cannot be used to discriminate between nodes. Note that we are neglecting the smaller eigenvalues, but under an SBM these are noise and should ignored by any learning system.
A.3 Further node classification results
As complement to Section 4.2.2 results corresponding to the Twitch ES and Citeseer networks are re- ported in Tables 5 and i respectively. Just like for Amazon, all methods obtain approximately the same performance, and it is relatively independent of the proportion of unknown edges. This is indicative that the graph structure does not provide significant information, which we have verified by training 2-layered fully connected NN with hidden dimension 64, using only the node features as input. Node classification results for Twitch ES and Citeseer are 70.1 0.4 and 72.5 0.3, respectively.
A.4 UN dataset details
Table A.4 shows the details of the UN dataset we have used to showcase embeddings under unknown edges and link prediction tasks. We include the years considered in Sections 4.1.4 and 4.2.1
A.5 LASE complexity
The complexity of each LASE layer consists of one graph convolution using the matrix A as the graph shift (or aggregation) operator, meaning multiplication AX; and graph attention step that entails the
30

---

Published in Transactions on Machine Learning Research (05/2025)
Year
# Countries
# Resolutions
# Affirmatives
# Unknowns
1960
100
54
2577
1360
1970
126
67
5182
2325
1980
153
103
11825
3371
1993
183
65
8177
3307
2004
191
90
12432
3629
2017
193
129
18086
5021
Table 7: Details on the UN dataset. For each year, we indicate the number of countries, resolutions, and how many votes were either affirmative unknown.
multiplication X A is the adjacency matrix of sparse graph with |&| edges, then the convolution can be computed with O((Eld) operations. The attention term on the other hand, will require O(N2d) operations in general, therefore being the leading complexity term. Now, when sparsify the attention matrix with mask Matt. (Section 3.3 the complexity is reduced to O(pan The total inference cost for L layers in LASE is then O(Lpan
Regarding the number learnable parameters in LASE, they amount to a total of 2 x di corresponding H = (H H- When using AL) together with a GNN for downstream task, necessarily the dimensionality of the input the first layer increases by d (compared to not using any PE). However, when using the precomputed ASE or the LASE output a PE, the number of learnable parameters for the task corresponds to those of the GNN (as LASE is trained to solve ( without considering the task hand]. Only when using LASE E2E the learnable parameters add up to those in the GNN, increasing by 2 x L x d..
31


Reviews:
[{"review_id": "kesDdJqUS5", "reviewer": "Reviewer_Dfyx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n-) This paper is very well-written and easy to follow. Concepts and ideas are communicated well and in a reasonably clear manner. Previous work is cited somewhat adequately.\n-) The core of the new algorithm proposed is reasonably novel. Several practical details are discussed.\n-) Numerical experiments demonstrate good performance against baselines. Some more effort on comparing against other algorithms, e.g., autoencoder-based, could be beneficial. Also, transformer-based approaches are not really discussed but I do not seem this as a major limitation.\n\nWeaknesses:\n-) Section 2 is too long. Nothing new is really being discussed/presented until page 7. Please shorten the section or move some parts to the appendix.\n-) Some results obtained via LASE seem to feature high variance (e.g., Figure 10 and elsewhere). Why is that?\n\nGeneral comments:\n-) \"render eidencomposition of moderately large graphs infeasible\". This statement gives the impression that all eigenvectors of the Laplacian must be computed. The real cost of obtaining PEs from graph Laplacian matrices is the cost of applying the Lanczos algorithm for the computation of the eigenvectors associated with a few of the algebraically smallest eigenvalues. This cost is linear to the number of graph edges unless the number of eigenvectors to be computed is too large, in which case the computational cost is dominated by orthogonalization costs.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a new algorithm to learn nodal Adjacency Spectral Embeddings (ASE) from graph inputs. The main idea seems to be to leverage Gradient Descent with algorithm unrolling by truncating and re-interpreting\neach GD iteration as a layer in a graph neural network (GNN) that is trained to approximate the ASE. The authors term this approach as \nLearned ASE (LASE). LASE layers combine Graph Convolutional Network (GCN) and fully-connected Graph Attention Network\n(GAT) modules, which is intuitively pleasing since GCN-based local aggregations alone are\ninsufficient to express the sought graph eigenvectors. Numerical experiments demonstrate \nthe competitiveness of LASE and its end-to-end variants against other baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See comments above.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9hv9TmplfH", "reviewer": "Reviewer_Rta7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths** \n1. The proposed method, LASE, is carefully designed and its architecture and optimization algorithm are clearly explained. This contribution provides valuable insights that can inform further developments in the field.\n2. While the primary objective of this paper is to approximate ASE, the authors also demonstrate its application to end-to-end graph representation learning, which adds significant value to practical applications.\n3. The paper considers multiple experimental scenarios, including node classification and link prediction, which enhances its overall quality.\n\n**Weaknesses**  \n1. The motivation for this paper is unclear. While I understand the goal of developing a GNN-based method (LASE) to approximate ASE, it remains questionable why one would opt for LASE over directly performing ASE. The empirical performance differences are marginal (slightly better in some cases but within typical deviation ranges). Clarifying this point would help make the paper more accessible and appealing to the broader ML research community.\n2. The discussion regarding the example in Figure 1 is unconvincing. Node clustering on regular graphs without node labels (or node feature vectors) often lacks practical relevance since nodes are topologically identical. As a result, it is unsurprising that effective unsupervised node clustering is not feasible in such cases. The purpose of this discussion should be clarified.\n3. One of the target tasks is unsupervised learning, yet there is no sensitivity analysis of parameters of LASE. Such an analysis would be particularly valuable, given the inherent difficulty of parameter tuning in unsupervised settings.\n4. The presentation, while generally clear, could be improved. For example, in Section 2.1, the problem is introduced as estimating $\\mathbf{X}$ to approximate the adjacency matrix $\\mathbf{A}$ of a graph $G$. However, the current phrasing suggests that $\\mathbf{X}$ is already given, which is confusing. I had to refer to (Scheinerman & Tucker, 2010) to fully grasp the problem formulation.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a novel method, LASE, designed to approximate Adjacency Spectral Embedding (ASE) using a GNN-based approach. ASE aims to generate node embeddings that approximate the adjacency matrix of a given graph. LASE achieves this by integrating GCN and GAT architectures. Its effectiveness and efficiency are empirically evaluated across various datasets, tasks, and optimization techniques.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address each of the concerns outlined in the Weaknesses section above.", "broader_impact_concerns": "I do not have any concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "EGI7SQfRSa", "reviewer": "Reviewer_Qvgz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This section summarizes strengths and weaknesses first, and then provides a detailed review of the paper including comments and questions.\n\n### Strengths\n* The paper thoroughly describes the derivation from the ASE formulation to their proposed Learned ASE (LASE) embeddings produced via algorithm unrolling.\n* The writing is clear and accessible, with a notation that can be easily parsed and understood.\n* The relationship between ASE, LASE, algorithm unrolling, and their derivation shows some promising direction.\n* The proposed LASE method is inductive, can be trained in an end-to-end fashion, and the authors show certain cases in which it is robust to novel inputs and limited distribution shifts. \n\n### Weaknesses \n\nNote that major concerns are described in top bullets, with details nested.\n\n* The derivation of how LASE is designed does not provide any theoretical or practical insights — although it seems correct, it is not clear why it is particularly relevant on either formal grounds or specific applications. \n  * No formal assessment about the time / memory complexity of training and inference for LASE, and direct complexity comparisons with existing methods.\n  * Missing motivation for why ASE approximation is beneficial versus other Positional Encoding (PE) approaches.\n  * No theoretical analysis of model capacity / expressivity compared to existing spectral approaches.\n  * Unclear advantages over simpler positional encodings or non-spectral alternatives.\n* Several aspects of the paper are underspecified or poorly motivated:\n  * The application of sparse attention as a mask is not clear, particularly in how the attention mask is constructed and why.\n  * Upon reviewing the code, it seems that the sparse attention mask is just a set of randomly generated edges from a generative model (like Erdos-Renyi or Watts-Strogatz), with no relationship to the actual connectivity of the graph. This seems to me poorly motivated, specially as it seems to be a random connectivity structure overlaid over the graph with no theoretical basis or guarantees.\n  * Details about the training procedure (number of iterations, batching if applicable, other hyper-parameters) are missing.\n* The experimental evaluation has significant limitations:\n  * Dataset and task details are underspecified. \n    * For example, the authors provide a small-scale evaluation on link prediction task, with underspecified dataset details (number of graphs, average $|V|$, $|E|$, degree, etc.)\n    * An appendix providing dataset and task details would help clarify the data the authors rely on to make their claims.\n  * The analysis of robustness only considers a naïve form of distribution shift, and does not consider perturbations of the graph structure.\n  * Empirical timing results are unclear, in particular whether the time is relative to obtaining a comparable result, or at least the results described in any of the task-specific experiments.\n  * Most reported improvements seem to be statistically insignificant. \n    * All results in Table 3 seem to be statistically indistinguishable from the first column: \n    * In Table 1, statistical significance cannot be assessed (there's no stddev).\n    * In Table 2, stat. sig. improvements only show for $\\rho > 0$, which is expected given the inductive setup.\n  * Limited comparison with state-of-the-art positional encodings (see detailed review for related PEs, at least some of which should be compared against).\n    * Although the paper presents a spectral method, its position as a PE means the state-of-the-art is broader than just ASE as a set of features: the authors need to compare with other PEs that offer inductive, learnable representations and assess whether the costs, benefits, and model complexity complexity indicate LASE is preferrable. \n  * Key architectural choices (e.g. LASE depth, attention masks) are not validated through data (e.g. ablation studies for predictive performance and computational costs).\n  * The comparisons seem unfair regarding model capacity: they seem to feature a GNN baseline (\"No PE\") compared against the same GNN that is fed an input from $L$ LASE layers. \n    * There is significantly more depth in the second case, particularly considering that LASE layers can be learning weights over both local connectivity and the fully-connected graph. \n    * There are no comparisons on the basis of training / inference cost for both, nor accounting for the # of learnable parameters, as is typically done when comparing GNN architectures.\n\n### Detailed review\n\n* Page 2: What is the problem with these precomputed PEs? If time / memory cost, it would be helpful to be explicit about their limitations. There exist inductive, non-Spectral PEs that have acceptable time complexity (e.g. counting or encoding structures and subgraphs). If the claim is that LASE is less costly than Spectral PEs, the authors should still compare with non-spectral PEs to motivate why LASE is desirable (due to e.g. interpretability, the ability to capture global structures, etc.).\n* Page 5: Besides random signals to identify each node, other approaches encode (local) structural patterns so that nodes are identified by the (usually permutation-equivariant) structures surrounding them (Zhao et al., 2021, Bouritsas et al., 2023;  Alvarez-Gonzalez et al., 2024). These methods remain inductive, are deterministic, and have been shown to be more expressive than vanilla GNNs with moderate additional costs.\n* Page 8: GATs are defined in terms of  messages through node neighbourhoods with attention. Framing the $X_l X_l^T$ term as a GAT on a fully connected graph seems wrong, considering both the message-passing aspect and the softmax term are omitted. It is a node similarity matrix where each entry is the dot product of node pairs.\n* Page 9: The authors claim “The unrolling offers an explicit handle on complexity leading to faster (post training) inference times” but do not explicitly analyze the time complexity of their proposed approach. This echoes the introduction: “Learned ASE (LASE), which is interpretable, parameter efficient, robust to inputs with unobserved edges, and offers controllable complexity during inference.”). \n  * What is the worst-time cost of training L LASE layers in terms of $|V|$, $|E|$, $L$ and $d$? \n  * Are the LASE layers simply trained via backprop with SGD on mini-batches? \n  * Similarly, what is the cost of inference? \n  * Authors imply the forward cost of the GCN and GAT layers and can be stopped at a chosen depth to provide a balance between inference cost and output quality — but the time complexity alone vs. a GNN or a Graph Transformer is not discussed. After going through the paper, as far as I can see, they also do not analyse the impact of 'stopping early' during inference. \n* Page 10: How are the proposed attention masks computed? Since they determine a subset of the fully-connected set of edges, they should also affect whether $\\mathbf{X}_{l+1}$  is a good approximator of the vanilla ASE definition. The authors mention the mask ‘encodes the topology of the sparse graphs’ — how? which topology? based on substructures, subgraphs, or something else? This seems like a major architectural choice that is underspecified in the manuscript.\n  * Reading through the paper, it seems that in Page 16. they define the mask by sampling edges via Erdos-Renyi or Watts-Strogatz models — but these methods are generative, so it is not immediately clear how they would apply to an existing graph.\n  * Reading through the code (under `./training/train_glase_e2e_classifier.py`), it seems the authors either generate a fully-connected graph or a random Watts-Strogatz graph with a matching number of nodes, but it's unclear how that would be relevant for a given arbitrary input graph and the choice of 'overlaying' a randomly generated graph is poorly motivated. I am refering to the following code snippet:\n```python\nif att_mask == 'FULL':\n    edge_index_2 = torch.ones([num_nodes,num_nodes],).nonzero().t().contiguous().to(device)\nelse:\n    edge_index_2 =  from_networkx(watts_strogatz_graph(num_nodes, 700, 0.1, seed=None)).edge_index.to(device)\n```\n* Page 12: Given the objective as stated in Eq. 4., what would be the outcome if the LASE layers were not structure aware, i.e. they learned a mapping $f: \\mathbf{X} \\in \\mathbb{R}^d \\mapsto \\mathbb{R}^{\\hat{d}}$ such that $f(x_i) \\cdot f(x_j) \\approx A_{i,j}$ via an MLP? It is clear this would be a transductive, rather than inductive setting, as we’d be learning to map from each graph’s node feature distribution onto their nodal adjacency spectral embeddings. However, this would also provide baselines for the delta in performance between inductive and transductive cases, which currently are not clear, especially in terms of the relevance of Figure 7.\n* Page 13: Is each sample seen once, and trained via a batch-size-of-1 SGD? What is the actual training process for LASE? This is a key point that is not clear.\n* Page 14: \n  * Minor: is $\\Pi_2$ renormalized? It must be in order to remain a valid connection probability matrix where rows / columns add up to 1.\n  * How well do these results hold? E.g. if a LASE model is trained in a range $\\delta \\in (-0.01, 0.01)$, does it generalize to $(-0.1, 0.1)$? How about $\\pm 0.2, 0.4, …$? The SBM is a rather simple model, so assessing robustness from them is not clear, and it doesn’t inform us about the upper bound of what distribution shifts it tolerates. How about the real world graphs: does a LASE model trained on Cora remain valid on the CiteSeer or Amazon datasets? How about perturbations from a given graph (e.g. via node / edge removal)?\n* Page 15: Which of the four attention variants are used in the paper for reporting other empirical results? What is the time and memory consumption between the proposed methods? Which result shows the ASE baseline from Graspologic? Are the wall times computed with respect to reaching comparable performance? On which dataset / task?\n* Page 16: (Figure 1) What does it mean to perform competitively, in particular compared against the standard ASE that should serve as the baseline? Additionally, are the reported differences between losses statistically significant? \n* Page 18: \n  * This link prediction task seems rather small: how many graphs are contained in the dataset? What’s their average number of nodes and edges? Are the differences between “No PE”, “ASE PE” and “LASE PE” statistically significant? \n  * Link prediction is a standard task in GRL with datasets going up to traditional node embeddings like e.g. node2vec (Grover et al., 2016). The authors should evaluate their method in a larger benchmark with more methods compared against — to assess why / whether ASE and LASE are relevant.\n  * How were the hyper-parameters chosen ($L = 10$, $d = 4$)? Since $L = 10$ implies 10 LASE layers, each of which are potentially fully connected in the GAT, the comparison with a standalone GNN is hardly fair, particularly in the end-to-end case. Is the GNN architecture only a GCN? What if you use a GAT? What if the GNN without LASE has more stacked layers? An appendix describing how hyper-parameters were chosen, and how hyper-parameter search was performed, if any, would be valuable. It would also assess whether the experiments are fair and comparable, inasmuch when more experiments are performed for method A than method B, it is more likely that method A will hit a 'lucky' result.\n* Page 20:\n  * (Table 2): Same questions as above: what is the model, how are hyper-parameters chosen, why are these hyper-parameters comparable? Additionally, at least for the $\\rho = 0$ case in Table 2, results are statistically insignificant. \n  * (Table 3): All results between LASE E2E (highlighted) and the No PE columns seem to be statistically insignificant (. Why is there no comparison with GNNs (e.g. GCN, GAT, and sub-graph / positional GNNs and PEs like GNN-As-Kernel, Shortest Path Neural Networks, Equivariant Subgraph Aggregation Networks, Edge-Level Ego-Network Encodings, Subgraph Union Networks, …)?\n* On related work: Are there time / memory complexity differences with PowerEmbed? If not, it is hard to assess why LASE would be preferrable, as the experiments cover only two comparisons.\n* Page 21: Authors cite Puny et al. 2020, which seems relevant (and more applicable than GATs) but do not relate their results to their method. The expressive power of matrix operations has been studied in Matlang (Brijder et al, 2019) and has found applications to GNN design in GNNML1 / GNNML3 (Balcilar et al. 2021). There have also been direct connections between the expressive power of GNNs with spectral information (Wang et al., 2022) that provide connections with other related works. For instance (Chien et al., 2021), proposed a GNN architecture to that is provably more powerful by learning a Generalized PageRank. In these works, which in my view are related to manuscrupt inasmuch as they construct or learn signals from graph spectra, the theoretical analyses and experimental approaches may help better position the presented work.\n\n### References\n\n* Adaptive Universal Generalized PageRank Graph Neural Network. Chien et al., in International Conference on Learning Representations, 2021.\n* Benchmarking Graph Neural Networks. Dwivedi et al., in Journal of Machine Learning Research, 2023.\n* Breaking the Limits of Message Passing Graph Neural Networks. Balcilar et al., in International Conference on Machine Learning, 2021. \n* From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness. Zhao et al., in International Conference on Learning Representations, 2022.\n* How Powerful are Spectral Graph Neural Networks. Wang et al., in International Conference on Machine Learning, 2022.\n* Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting. Bouritsas et al., in IEEE Transactions on Pattern Analysis and Machine Intelligence. 2022.\n* Improving Subgraph-GNNs via Edge-Level Ego-Network Encodings. Alvarez-Gonzalez et al., in Transactions of Machine Learning Research, 2024.\n* node2vec: Scalable Feature Learning for Networks. Grover et al., in International Conference on Knowledge Discovery and Data Mining (KDD), 2016.\n* On the Expressive Power of Query Languages for Matrices. Brijder et al., in ACM Trans. Database Syst.  2019.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a neural architecture to learn Adjacency Spectral Embeddings (ASEs), whose design is characterized as the unrolling of the Gradient Descent algorithm via two GNN layers: a GCN, and a GAT applied over a fully connected instance of the graph. Authors describe variations of the architecture considering performance, and design downstream architectures using LASE layers to learn self-supervised ASEs or tackle end-to-end node classification and prediction tasks.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses and detailed review. In my view, given its current status, the paper requires (in order of importance):\n\n\n### Critical changes:\n#### These changes would provide theoretical and empirical support for the current claims.\n\n* Additional experimental results to help show that LASE _is_ relevant: comparisons with other PE methods, fairly considering model capacity (i.e. parameter counts) and depth, in common node / edge / graph-level tasks (e.g. datasets from Dwivedi et al., 2022, or the Open Graph Benchmark).\n* A comparison of the time and memory complexity of LASE versus existing approaches, together with whether existing methods are transductive (i.e. only apply to known nodes / edges / graphs), or inductive. \n* Improved empirical comparisons with existing approaches, at the very least containing approaches that are currently cited (e.g. Huang et al., 2022; Lim et al, 2023.), and ideally at least one example of other PE methods (e.g. sub-graph or substructure based).\n\n### Desirable improvements to strengthen the work:\n#### These changes would improve positioning the work against existing approaches, provide a more thorough picture of the merits of LASE, how it has been evaluated, and whether the experimental comparisons are fair.\n\n* A more systematic analysis of the empirical results regarding model performance and costs: what are the training and inference time / memory cost for each of the models in Tables 1, 2 and 3?\n* Better positioning with the state of the art: why is being able to efficiently approximate ASEs a relevant problem? how does it compare with existing approaches? which benefits does it bring (interpretability, performance, reduced computation or memory costs, ability to model higher-order signals, expressivity according to some test like Weisfeiler-Lehman, ...)?\n* Additional dataset details, as an appendix describing the datasets, number of graphs, avg. number of nodes, edges, number of features, classes, and objective.\n* Additional hyper-parameter details, including all explored hyper-parameters, how hyper-parameter search was conducted, if at all, and the number of hyper-parameters tried on each experiment for the models being evaluated.", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper was reviewed by three expert reviewers. The reviewers agreed that the paper is easy to read and that the proposed method is clearly explained and is well-designed. They also agreed that the idea behind this paper is promising. However, the reviewers raised concerns about the quality of presentation, the lack of theoretical insights, the lack of experiments on sensitivity, and issues with the empirical validation of the proposed approach. Importantly, some reviewers seemed skeptical about the motivation of this work since it is not clear what are the advantages of the proposed approach over methods that directly compute the spectral embeddings of a graph. Furthermore, one reviewer was concerned about the connection between the layers of the proposed model and the GCN and GAT layers, which actually seems somewhat misleading since the employed attention mechanism is different from the one of the standard GAT layer. Most of these concerns were addressed by the authors in their response, and one reviewer recommended acceptance of the paper, while the other two reviewers recommended weak acceptance. I believe that the submission now meets the TMLR acceptance criteria, and thus, I am recommending acceptance. I personally agree with the reviewers that it should be clearly explained in the manuscript why one should use the proposed model instead of directly computing the eigenvalue decomposition. I also suggest the authors describe in detail how the vanilla GCN and GAT models differ from the corresponding formulations employed in this paper. I also request that the final version of the manuscript carefully considers the reviewers' comments and suggestions.
Decision: Accept (poster)