1
Filter Learning for Subgraphs: Algebras and Performance Risk Bounds
arXiv:2607.21263v1 [cs.LG] 23 Jul 2026
Purui Zhang, Feng Ji, Yanan Zhao, Bihan Wen, and Wee Peng Tay
Abstract—Graph signal processing tasks that leverage spectral information typically assume access to the complete graph topology, which is often unavailable in practice. We propose a systematic framework for subgraph filter learning (SFL), where subgraph-supported operators approximate ambient graph filters under partial observations. We formulate SFL as a statistical learning problem in which optimal subgraph operators are inherently data-dependent. To address the difficulty of directly estimating such operators, we develop a subgraph filter algebra based on distance-aware Laplacian constructions, defining a structured and controllable class of filters for effective approximation. We further establish performance risk bounds under the least squares loss, quantifying how well the learned operator approximates the restricted ambient mapping. Experiments real-world datasets show that, for SFL tasks, the proposed algebraic models consistently outperform polynomial filters, distribution-agnostic operators, and direct numerical filter learning baselines that attempt to recover the underlying structure from data.
Fig. 1. Illustration of subgraph filtering. Note that the third party has no knowledge of nodes and edges beyond the subgraph structure. In the stakeholder’s graph filter with at least 2-hop connectivity, information from node v contributes to the output at node u. However, in the truncated filter, the contribution from node v to node u is lost. In contrast, using filters from a subgraph filter family can effectively capture the influence of node v on node u, resulting in improved performance.
I. I NTRODUCTION Since its inception, graph signal processing (GSP) has encompassed a diverse range of research areas, including the analysis of graph-structured data [1], [2], [3], statistical and spectral graph analysis [4], [5], [6], [7], the inference of graph topology [8], [9], [10], and advancements in graph neural networks [11], [12], [13]. At the heart of GSP lies the graph shift operator (GSO), which serves as a fundamental component directly linked to the graph’s topology. The GSO plays a pivotal role in enabling key operations such as filtering [14], [15], signal recovery [16], [17], [18], [19], [20], and the computation of the graph Fourier transform (GFT) [21], [22]. Conventional GSP tasks, including filtering, spectral analysis, and stationarity analysis[22], [23], typically assume access to the full graph topology and its associated GSO. In many practical settings, however, only a partial view of the graph is available. A stakeholder who owns the graph may grant a third party access to only a subset of nodes because of privacy, computational, or operational constraints; see Fig. 1. The third party seeks to estimate an output signal by filtering over the accessible subgraph, but it cannot directly observe the full graph topology or the complete input graph signal. Instead, the stakeholder provides a subgraph filter (or GSO) defined solely on the accessible nodes.1 The quality of a subgraph filter is evaluated by comparing two outputs: (i) the ambient graph filter applied to the full signal, followed by restriction to the node subset; and (ii) the subgraph filter applied directly to 1 Alternatively, the stakeholder could provide filtered data. However, this
approach incurs recurring service overhead, as the stakeholder must respond to each processing request. By contrast, providing a reusable subgraph filter is a one-time information transfer that avoids this overhead.
the restricted signal. A sufficiently small discrepancy between these outputs indicates that the subgraph filter is useful for the third party. A naive approach is a truncated filter formed by extracting the principal submatrix of the ambient filter (represented as a matrix) corresponding to the subgraph nodes. Although this construction preserves message passing within the subgraph, it removes all interactions between subgraph nodes and external nodes, leading to systematic information loss. Consequently, truncated filters often incur substantial approximation error. This limitation motivates the development of a more expressive class of subgraph filters that can better approximate the restricted ambient filtering operation without requiring access to the full graph structure. We study subgraph filter learning (SFL), which seeks to learn a subgraph-supported filter for a specified node subset from ambient graph data. The learned filter is deployed only on the accessible subgraph and approximates the restricted action of the ambient filtering operation, without revealing the ambient filter or the graph structure outside the subset. To the best of our knowledge, no comprehensive study has systematically formulated SFL and derived its error analysis with respect to both data and graph structure. Our main contributions are summarized as follows: • We formulate the problem of SFL, which studies how
to construct subgraph-supported filters that approximate the restricted action of an ambient graph transformation. We propose a k-hop, distance-based subgraph filter space based on matrix algebras for SFL.
2
• We provide a finite-sample excess-risk analysis of ridge-
graph Wiener filters and Bayesian estimation under prescribed stochastic models [38], [39], [40], [41]. Random-design regression provides an unstructured finite-sample counterpart. Specifically, the paper [42] analyzes ordinary least squares and ridge regression, while [43] presented a concise excess-risk analysis of ridge regression in the same setting. Unlike fullgraph stochastic estimators and unstructured random-design analyses, SFL learns subgraph-supported filters from graphsignal pairs and quantifies how intrinsic prediction and filterbank approximation errors depend on graph distances, subgraph boundary interactions, or the way a prescribed subgraph is embedded in the ambient graph. Organization of the paper. In Section II, we formalize the SFL problem and motivate the need for new filter-bank designs. In Section III, we present a filter-algebra architecture and introduce distance-based subgraph operators that integrate with this architecture. In Section IV, we provide a theoretical analysis of subgraph-filter approximation error, characterizing the intrinsic limits of SFL and informing the design of subgraph filter banks. Finally, in Section V, we evaluate the effectiveness of different subgraph filter-bank types across diverse SFL tasks. Notations. Let R denote the set of real numbers and N the set of natural numbers. Matrices and vectors are represented by boldface letters. For a set of signals {bi ∈ RN }Ti=1 , the design matrix [bi ]Ti=1 ∈ RN ×T is formed by stacking the column vectors bi along the rows. Let U ⊂ {1, . . . , N } be a subset A. Related Work of indices. We define the partition of a matrix S ∈ RN ×N of rows and columns if 1) Signal processing on substructures: Several prior works with respect to U h as (with reordering i SU U SU U c have studied GSP on graph substructures, including local-set- necessary) S = SU c U SU c U c . based graph signal reconstruction [25], graph signal decimaGiven a set of linear operators S, span S denotes the span of tion [26], and spectral graph reduction [27]. In graph neural S, i.e., the set of linear combinations of elements in S. networks (GNNs), SplitGNN [28] partitions the original graph and applies spectral graph filters to address heterophily in fraud II. T HE S UBGRAPH F ILTER L EARNING P ROBLEM detection, while STMS-GCN [29] employs multiple learnable In this section, we first formalize the SFL problem, which subgraphs to capture spatio-temporal motion patterns. These is a statistical learning problem that aims to find a subgraphworks use graph substructures for reconstruction, reduction, supported operator that approximates the restricted ambient or representation learning, whereas SFL characterizes the ap- mapping. Then, we present the empirical formulation of the proximation of ambient-graph transformations on prescribed problem, which is more practical for real-world applications. subgraphs. Finally, we provide examples as illustrations. 2) Graph filtering and filter-bank design: Polynomial graph filters for a prescribed GSO have been widely studied, including optimal designs for implementing or approximating A. Problem Formulation Let G = (V, E) be an undirected, unweighted graph with linear network operators [30]. Extensions beyond a single GSO include parallel filters associated with different GSOs [31], vertex set V , |V | = N , and edge set E. The adjacency |V |×|V | is defined by Aij = 1 if and polynomial filters of multiple commutative shifts [32], and matrix A ∈ {0, 1} graph-based classification with multiple shift matrices based on only if (vi , vj ) ∈ E, and Aij = 0 otherwise. The degree |V | features [33]. Expressiveness has also been improved by relax- matrix D = diag{deg(vi )}i=1 is a diagonal matrix, where ing node-invariant parameter sharing through node-variant [34], deg(vi ) denotes the degree of vertex vi in G. The Laplacian edge-varying [35], and partition-wise [36] graph filters, which is defined as L = D − A, and the normalized Laplacian as e = I − D−1/2 AD−1/2 . assign different weights to different nodes, edges, and node par- L Suppose the graph G is owned by a stakeholder. Associated titions, respectively. Although applicable to induced subgraphs, these methods do not explicitly address the ambient-subgraph with the graph is a random input graph signal x ∈ R|V | where relationship central to SFL, which requires filter banks tailored E∥x∥2 < ∞. The stakeholder grants access to a subset of to approximating ambient transformations on prescribed sub- nodes U ⊆ V , with |U | = N0 , to a third party. The U -induced subgraph is defined as GU := (U, {(u, v) ∈ E : u, v ∈ U }). graphs. 3) Stochastic graph signal estimation: Stationary GSP mod- The restriction of x to U is given by xU := PU x ∈ R|U | , els graph random processes through graph-dependent second- where PU ∈ {0, 1}|U |×|V | is the selection matrix, satisfying order statistics [4], [37], [5], supporting mean-square-optimal PU P⊺U = IU , the |U | × |U | identity matrix. regularized least-squares SFL over a k-hop, distancebased subgraph filter space under sub-Gaussian graphwide-sense stationary (WSS) inputs. The bound decomposes prediction error into (i) irreducible loss from subgraph-only observations, (ii) approximation error from excluding interactions beyond k hops in the ambient graph, (iii) regularization error, and (iv) filter-bank dimension effects. We also show how graph-distance structure controls the trade-off between model expressiveness and finitesample estimation error. • We evaluate the SFL framework on filtering, signal reconstruction, and prediction tasks using both synthetic and real-world datasets. The results verify consistent improvements over standard polynomial filtering methods and statistical baselines. A preliminary version of this work was presented in [24]. Compared with the preliminary version, this paper recasts SFL in a statistical signal processing framework, generalizes distance-based constructions from normalized Laplacians to broader types of shift operators on subgraphs, introduces a finite-sample excess-risk analysis for ridge-regularized SFL, and significantly expands experiments to filtering, reconstruction, and prediction with additional hyperparameter and ablation studies.
3
An output signal is modeled as y = f (x) + w ∈ RN , where E∥f (x)∥2 < ∞, and w is a random noise vector, which is uncorrelated to x. It satisfies Ew = 0 and E∥w∥2 < ∞. A third party has no knowledge of f (·) or the full ambient graph G. Instead, it has access only to the U -induced subgraph GU and the restricted signals xU . To estimate the restricted output signal yU = PU y, the stakeholder provides the third party with a subgraph filter FU supported on GU (see Fig. 2). The objective is to minimize the performance risk:
of an appropriate subgraph filter bank S(GU ) to accurately approximate the target restricted transformation. The choice of the subgraph filter bank S(GU ) plays a pivotal role in achieving accurate approximations, as it determines the expressiveness and flexibility of the learned operator. The design and construction of such filter banks are discussed in detail in Section III.
RL (FU ) = E[L(yU , FU xU )] = E[L(PU y, FU PU x)], (1)
In practice, when the distribution of x is unknown, the stakeholder can only learn the subgraph filter FU from a finite set of training data. We assume that the stakeholder has access to a training dataset {(xi , yi )}ni=1 consisting of n independent and identically distributed (i.i.d.) samples drawn from the joint distribution of (x, y). The empirically optimal subgraph filter is given by
where L(·, ·) is a nonnegative loss function.
f (·) + w (G, x)
PU
(G, y)
(GU , PU y)
B. Empirical Optimization
?
PU (GU , PU x)
FU
n
b (n) = F U (GU , FU PU x)
Fig. 2. The subgraph filter learning framework. The upper path represents the stakeholder’s processing pipeline, and the lower path represents the third party’s processing pipeline. The goal of SFL is to design subgraph filter FU such that the two pipelines produce consistent outputs on the subgraph.
The subgraph filter FU is constructed as a linear combination of basis elements from a specified subgraph filter bank S(GU ) = {Bj ∈ RN0 ×N0 }m j=1 , such that FU =
m X
θj Bj ,
(2)
where Bj ∈ S(GU ), and the filter bank size m is constrained by the budget m ≤ αN0β , with α > 0, 0 < β ≤ 2.
(3)
(4)
Using (2), the SFL problem (4) reduces to a finite-dimensional optimization problem over {θj }m j=1 . To mitigate potential ill-posedness caused by limited training data, regularization can be employed. A common approach is ridge regression, which introduces a penalty term to control the complexity of the learned filter. The regularized optimization problem is formulated as follows: n
b (n) = F U
j=1
1X L PU yi , FU PU xi , FU ∈span S(GU ) n i=1 arg min
1X L PU yi , FU PU xi + η∥FU ∥2F , FU ∈span S(GU ) n i=1 (5) arg min
where η > 0 is the regularization parameter, and ∥·∥F denotes the Frobenius norm. This regularization term reduces overfitting and improves numerical stability, particularly when the number of training samples is limited.
The performance loss in (1) quantifies the expected discrepancy between the restricted ambient transformation PU y and C. An Example: Least Squares SFL the output FU PU x generated by the subgraph filter. This metric To illustrate the SFL framework, we consider least-squares serves as a measure of the predictive accuracy of the subgraph SFL with L = L2 in (4) as a representative example. This filter. The optimization problem in SFL is inherently challeng- setting highlights both the empirical optimization procedure ing (under arbitrary loss functions) due to two primary factors: and the derivation of analytical solutions. By concatenating the (i) the fundamental approximation arising from the restricted training samples {(xi , yi )}ni=1 , we obtain observation xU , even when the filter space is unconstrained; 1 2 n xU · · · xU XU = xU ∈ RN0 ×n and (ii) the additional approximation error introduced by the 1 2 n constrained dimensionality of the filter space S(GU ). · · · xU XU c = xU c xU ∈ R(N −N0 )×n , c c In the context of the scenario in Section I, the stakeholder’s objective is to construct a subgraph filter FU such where XU and XU c collect the samples restricted to U and its that FU PU x ≈ PU y in expected loss, which can then be complement, respectively. Similarly, YU and YU c denote the transmitted to the third party. In scenarios where the map- corresponding output-signal matrices. We assume that the filter space is unconstrained, namely ping f (·) is unknown, the stakeholder relies on training data span S(GU ) = RN0 ×N0 . We further assume that the subgraph comprising input-output signal pairs (x, y) to learn FU by ⊺ MU U := E[xU xU ] and the sample minimizing the empirical performance loss. As demonstrated second-moment matrix ⊺ Gram matrix X X are nonsingular, and that PU f (x) is U U in Section II-B, even when the data distribution is fully known, square-integrable. the oracle subgraph filter generally differs from that based on The empirical optimization problem in (4) reduces to the naive induced subgraph shift operator. In particular, it in2 cludes a boundary-correction term arising from the unobserved min∥YU − FU XU ∥F . FU complement U c . This observation motivates the construction
4
This problem admits the closed-form solution b (n) = YU X⊺ (XU X⊺ )−1 , F U U U
A. Preliminaries (6)
which we refer to as the numerical LMMSE subgraph filter. By b (n) → F∗ almost surely the strong law of large numbers, F U U (a.s.) as n → ∞, where ⊺
⊺
F∗U = E[yU xU ](E[xU xU ])−1 ⊺ = E[PU f (x)xU ]M−1 UU .
(7)
The operator F∗U is referred to as the oracle LMMSE subgraph filter. We next consider the setting in which y = Fx, where F = I − ζL represents one-step graph diffusion and x ∈ N (0, (L + µI)−1 ) is a centered Gaussian Markov random field (GMRF). In this case, the oracle LMMSE filter takes the form F∗U = IU − ζLU U + ζAU U c (LU c U c + µIU c )−1 AU c U . This expression comprises the subgraph diffusion term IU − ζLU U and a boundary correction term ζAU U c (LU c U c + µIU c )−1 AU c U induced by signals outside U . Let Dµ := DU c U c + µIU c . The boundary correction term admits the Neumann series expansion ∞ X
k −1 AU U c (D−1 µ AU c U c ) Dµ AU c U .
R[B1 , . . . , Bk ] := span R≤r [B1 , . . . , Bk ] := span
k [ i=1 k [
R[Bi ],
(8)
R≤r [Bi ].
(9)
i=1
Elements in R[B1 , . . . , Bk ] consist of linear combinations of polynomials in individual matrices, without cross-products between distinct matrices. We define the matrix free algebra generated by a set of matrices {B1 , B2 , . . . , Bk } of the same dimensions as R≤r ⟨B1 , B2 , . . . , Bk ⟩ ( r ) Y = span Mli : Mli ∈ {B1 , B2 , . . . , Bk } . (10) i=0
k=0
The k-th term aggregates walks that leave U , take k steps within U c , and then return to U ; accordingly, these walks have length k + 2. Moreover, as shown in ?? of the supplementary material, the performance loss satisfies RL2 (F∗U ) ≤
The shortest-path distance between two nodes u and v in G is denoted by dG (u, v), and the diameter of G is defined as diam G = max{dG (u, v) : u, v ∈ G}. Two nodes u and v are said to be connected in G if a path exists between them, and disconnected otherwise (we let dG (u, v) = ∞ in this case). any matrix B, we define R[B] = {M : M = PFor r al Bl , al ∈ R, r ∈ N} and R≤r [B] = {M : l=0 P r0 al Bl , al ∈ R, r0 ≤ r}. For matrices B1 , . . . , Bk M = l=0 of the same dimensions, we define
ζ2 |cut(U, U c )|, µ + λmin (LU c U c )
where |cut(U, U c )| = |{(u, v) ∈ E(G) : u ∈ U, v ∈ U c }| denotes the size of the graph cut set. Thus, the performance loss is jointly determined by the diffusion strength, the GMRF regularization, and the connectivity between GU and its complement. The preceding results show that both the oracle subgraph filter and its achievable error depend jointly on the input statistics and the graph structure. Although the numerical LMMSE filter is available in closed form, its computation requires inverting the sample Gram matrix XU X⊺U , which may be singular or illconditioned when the available data are limited. This observation motivates learning within a structured finite-dimensional filter class of controllable size. We therefore develop a systematic construction of the filter bank S(GU ) through subgraph filter algebra and analyze its structural properties. III. S UBGRAPH F ILTER A LGEBRAS
B. Distance-based Subgraph Shift Operators For u, v ∈ U , the induced-subgraph distance satisfies dGU (u, v) ≥ dG (u, v), and nodes connected in G may become disconnected in GU . Consequently, relying solely on the adjacency matrix or Laplacian of GU may necessitate higher-order polynomials to propagate information between nodes, or may fail entirely if the nodes are disconnected. To mitigate these limitations and more effectively approximate the message-passing behavior of the original graph, we propose the use of auxiliary subgraphs derived from both G and GU . Definition 1 (DSSO). Let G be a graph and GU its induced subgraph. A matrix SU is termed a k-hop distance-based subgraph shift operator (DSSO) on GU with respect to G if its (i, j)-th entry (SU )i,j = 0 for all vi , vj ∈ U such that dG (vi , vj ) > k. Note that in Definition 1, the distance metric is based on the ambient graph G. For instance, the adjacency matrix and Laplacian of the induced subgraph GU are examples of 1-hop DSSOs. Additionally, diagonal matrices of size |U | × |U | can be regarded as 0-hop DSSOs. The following properties are immediate.
Corollary 1. Suppose S1 and S2 are k-hop DSSOs of GU over In this section, we construct structured filter banks S(GU ) G, then θ1 S1 + θ2 S2 is a k-hop DSSO (of GU over G) for any for SFL. We preface by introducing necessary notations and θ1 , θ2 ∈ R. definitions, followed by the formal definition of subgraph shift operators, which serve as the foundational elements for con- Corollary 2. Suppose S1 and S2 are k1 -hop and k2 -hop structing the filter bank. We then discuss the expressiveness and DSSOs of GU over G, respectively. Then S1 S2 is a (k1 + k2 )formal dimension of the resulting subgraph filter algebra. hop DSSO.
5
[i]
define the primitive set {LU }ki=1 . This choice allows the resulting filter algebra to combine multiple distance-dependent propagation patterns while keeping the primitive construction simple and fully supported on U . D. Expressiveness and Dimensionality Control Next, we address the question of whether SFFA can span the entire space of linear operators on R|U |×|U | , which is pivotal for understanding the theoretical capabilities and practical applications of SFFA in SFL. Fig. 3. Example for distance-based subgraphs on a cyclic graph G with 15 nodes.
In summary, the distance-dependent behavior of subgraph filters can be systematically controlled through linear combinations and products of DSSOs. We next introduce the notion of distance-k subgraphs, which provide a natural and illustrative example of k-hop DSSOs. Definition 2. For 1 ≤ k ≤ diam G, let the distance-k subgraph of GU be a graph such that its vertex set is U ; and its edge set is {(u, v) ∈ U × U : dG (u, v) = k}, i.e., the edges are those pairs of nodes in U that are k hops apart in the ambient graph [k] G. We denote this subgraph as GU .
Theorem 1 (Expressiveness of SFFA). Suppose G is a connected graph, and GU is the induced subgraph on U . Define Eij ∈ {0, 1}|U |×|U | as the elementary matrix with a 1 in the (i, j)-th position and 0 elsewhere. Consider the set of primitives |U |
G U = {Eii }i=1 ∪ {Ak }diam , k=1
where Ak is the adjacency matrix of the distance-k subgraph [k] GU . Then, the (|U|, 3)-SFFA satisfies dim A|U |,3 = dim R≤3 ⟨U⟩ = |U |2 .
Proof. First, it is immediate that dim R≤3 ⟨U⟩ ≤ |U |2 . Since R≤3 ⟨U⟩ already contains all diagonal elementary matrices Eii , it remains to show that it can represent every off-diagonal elementary matrix Eij for i = ̸ j, with i, j ∈ U . Because G [k] is connected, d (i, j) ≤ diam G < ∞. Let d = dG (i, j). Then G Fig. 3 illustrates the construction of GU on a cycle graph for A ∈ U , and its (i, j) entry is equal to 1. Moreover, since Eii d k ∈ {1, 2, 3}. In this example, GU comprises five connected E are primitives, we have Eij = Eii Ad Ejj , which is and jj components, including two isolated vertices. When filter design represented by at most three primitives from U. Therefore, is restricted to the induced subgraph GSO of GU , information transfer across disconnected components is prevented. In |U | R≤3 ⟨U⟩ ⊃ span{Eij }i,j=1 . contrast, DSSOs employing distance-k subgraphs enable crosscomponent propagation, thereby enhancing the representational Hence, capacity of the resulting filters. |U | |U |2 ≥ dim R≤3 ⟨U⟩ ≥ dim span{Eij }i,j=1 = |U |2 , C. DSSO Algebra
which concludes the proof.
As discussed above, GU may be disconnected, thereby limit- Remark 1. Theorem 1 also holds if we replace the adjacency ing information exchange across components. A natural remedy matrix with Laplacian, normalized adjacency, or normalized is to combine operators associated with different distance-k sub- Laplacian matrix of G[k] . U graphs. This leads to a non-commutative algebraic framework Theorem 1 establishes that, by incorporating diagonal (0for constructing filters from multiple DSSOs. If filtering on GU ⊆ G is restricted to a single subgraph GSO hop) DSSOs and all distance-based subgraph primitives, the LU , then the filter space is the commutative algebra R[LU ]. Its resulting SFFA can span the entire matrix space. The next step is to determine the dimension of SFFA filter operators share a common eigenspace, and its dimension is at most |U |. These structural constraints may limit expressiveness. banks. Accurately determining their dimension is challenging By contrast, we select DSSOs as primitives that are not jointly due to potential linear dependencies among monomials (e.g., diagonalizable. The resulting non-commutative algebra is con- while S1 and S2 may not commute, monomials such as S1 S2 S1 3 siderably richer, yielding a broader and more expressive class and S2 S1 could still be linearly dependent), so we instead focus on the formal dimension of the filter algebra, which of subgraph filters. provides a practical measure directly related to the number of Definition 3. Let {S1,U , S2,U , . . . , Sk,U } be a set of k-DSSOs trainable parameters when optimizing filters within the space as primitives. The (k, r)-subgraph filter free algebra (SFFA) of using optimization techniques. GU is given by (recall the notation in (10)): Definition 4 (Formal Dimension). The formal dimension of Ak,r = R≤r ⟨S1,U , S2,U , . . . , Sk,U ⟩. (11) a (k, r)-SFFA Ak,r is defined as the total number of distinct monomials of degree at most r generated by the primitives, A natural strategy of selecting primitives is to use DSSOs including the identity. [i] induced by {GU }ki=1 . For instance, their Laplacians naturally
6
Remark 2. The formal dimension is an upper bound on the true dimension of the evaluated filter space, since each monomial in SFFA, and each reversal-equivalence class in sym-SFFA, corresponds to one evaluated matrix generator. The bound may be strict when these generators are linearly dependent. In symSFFA, accidental symmetry of monomials only further reduces the actual dimension.
of Vk , i.e., ⟨Qj ,P Qj ′ ⟩F = δjj ′ . Every F ∈ Vk then admits the m expansion F = j=1 θj Qj . Let F∗U denote the oracle LMMSE subgraph filter. Define
Theorem 2. For k > 1, the formal dimension of a (k, r)-SFFA Pr r+1 is l=0 k l = k k−1−1 .
and the empirical ridge estimator ) ( n 1X i i 2 2 (n) ∥y − FxU ∥2 + η∥F∥F . F̂m,η := arg min n i=1 U F∈Vk
Proof. For a (k, r)-SFFA, a monomial of degree l is formed by multiplying l primitives. Since there are k available choices for each factor, there are exactly k l distinct monomials of degree l. Summing these quantities over all degrees from l = 0 to r yields the stated formal dimension. Pk For example, the sum of polynomial spaces i=1 R≤ri [Si ] Pk has a formal dimension of 1 + i=1 ri , as the identity matrix is For R≤3 ⟨U⟩ in Theorem 1, the formal dimension is Pshared. 3 (|U |+diam G)l , which vastly exceeds the true dimension l=0 2 |U | , indicating significant linear dependence among monomials. In practice, to make sure the choice of k and r reflects the underlying graph structure, it is advised to incorporate more distance-based primitives (larger k) while keeping r small (cf. Section V-C2). Conversely, for denser graphs (e.g., Erdős–Rényi graphs with p > 0.3), a smaller k together with a higher polynomial order r is often sufficient. In finite-sample regimes, estimating a larger number of parameters exacerbates estimation error and introduces numerical instability. Thus, the choice of filter algebra dictates a fundamental bias-variance trade-off between approximation capacity (determined by algebraic expressiveness) and statistical efficiency (determined by the formal dimension). We formalize this trade-off in the next section. IV. P ERFORMANCE R ISK B OUNDS In the SFL framework, estimating an optimal filter from a prescribed filter bank S(GU ) using finite samples inherently induces a bias-variance trade-off. A restricted filter class yields approximation error due to insufficient representational capacity, whereas an overly expressive class amplifies estimation error in the finite-sample regime. The following results provide formal excess-risk bounds that characterize how the approximation of the oracle operator depends on the filter-bank dimension, sample size, and data distribution. We make the following assumption throughout this section. Assumption 1. The input signal x is zero-mean, sub-Gaussian, and has a positive-definite second-moment matrix M. In addition, x is graph wide-sense stationary[4], [5], i.e., M and the graph Laplacian L are simultaneously diagonalizable. The noise vector w is sub-Gaussian and uncorrelated with f (x). The mapping f is globally Lipschitz: ∥f (u)∥2 ≤ Lf ∥u∥2 , for all u ∈ RN , and for some constant Lf > 0. Let Vk denote the linear space of k-hop DSSOs, and let m := dim(Vk ). Let {Qj }m j=1 be a Frobenius-orthonormal basis
F̄m := arg min RL2 (F), F∈Vk F̄m,η := arg min RL2 , (F) + η∥F∥2F , F∈Vk
(12)
To quantify the component of a filter that is activated by the input distribution, we introduce the MU U -induced norm and inner product: ⊺
∥S∥2MU U := E∥SxU ∥22 = tr(SMU U S )
(13)
and ⊺
⊺
⟨S1 , S2 ⟩MU U := E[(S2 xU ) (S1 xU )] = tr(S1 MU U S2 ). (14) For notational convenience, let κmin := λmin (M) and κmax := λmax (M) be the minimum and maximum eigenvalues of M, respectively. We denote by ∥·∥ψ2 the sub-Gaussian norm [44, Definition 2.5.6] and by ∥·∥ψ1 the sub-exponential norm [44, Definition 2.7.5]. For the coordinate representation over Vk , we also define the Gram matrix Γ ∈ Rm×m and the coordinate response vector b ∈ Rm by Γjℓ := ⟨Qj , Qℓ ⟩MU U ⊺ bj := E[yU Qj xU ],
(15) ⊺
b := (b1 , . . . , bm ) .
(16)
We now establish bounds on the least squares performance loss of the empirical ridge estimator in (12). Proof sketches for Theorem 3 and complete proofs of Theorem 4(i) are given in Appendix A; the remaining proofs are deferred to ?? of the supplementary material. We start with a few preliminary results. Lemma 1. Under Assumption 1, the Gram matrix Γ satisfies κmin ≤ λmin (MU U ) ≤ λmin (Γ) ; λmax (Γ) ≤ λmax (MU U ) ≤ κmax .
(17)
Lemma 1 establishes the numerical stability of the coordinate system induced by Vk : the eigenvalues of the Gram matrix Γ are sandwiched between those of MU U , and therefore lie within [κmin , κmax ]. This conditioning guarantee is invoked repeatedly throughout the analysis to control the norms of inverse Gram matrices and to translate errors in the coordinate coefficients into prediction errors. Lemma 2. Under the model y = f (x) + w with E[wx⊺ ] = 0, the coordinate response vector b satisfies X 2 ∥b∥22 = ((JM)uv ) , (18) u,v∈U dG (u,v)≤k
where J := E[f (x)x⊺ ]M−1 .
7
Lemma 2 connects the ridge analysis to graph distance. Specifically, it identifies b as the k-hop component of the input– output cross-moment; consequently, only correlations between node pairs with dG (u, v) ≤ k contribute to the coordinate response. This is precisely where the graph-local constraint of SFL enters the subsequent bounds.
(ii) The approximation error
Theorem 3 (Ridge excess risk decomposition). Suppose Assumption 1 holds. Then, for any η > 0,
(iii) The ridge regularization error
2 E∥PU f (x) − F̂(n) m,η xU ∥2 ≤ RL2 (F∗U ) + ∥F∗U − F̄m ∥2MU U + 2∥F̄m − F̄m,η ∥2MU U 2 + 2∥F̄m,η − F̂(n) m,η ∥MU U . (19)
Theorem 3 decomposes the prediction risk into four components: ∗ • Performance error RL2 (FU ): the irreducible discrepancy between PU f (x) and the best linear predictor based on xU ; this term is independent of both the filter-bank class and the sample size. ∗ 2 • Approximation error ∥FU − F̄m ∥M : the error induced UU by constraining the oracle LMMSE filter to the k-hop subspace Vk , i.e., the component of F∗U that cannot be represented in Vk . This term decreases as k increases. 2 : the bias intro• Regularization bias 2∥F̄m − F̄m,η ∥M UU duced by ridge regularization; it vanishes in the limit η → 0+ . (n) 2 : finite• Empirical estimation error 2∥F̄m,η − F̂m,η ∥M UU sample deviation of the empirical estimator from its population counterpart. This term typically decreases with n and may increase with the filter dimension m; hence, enlarging Vk can reduce approximation error while potentially increasing estimation error. In what follows, we derive bounds for each error component as functions of the filter space Vk , through the following quantities: 2 2 • σU := E∥PU (f (x) − Jx)∥2 measures the intrinsic residual of f after its oracle linear approximation Jx, and thus captures the performance error that is independent of the choice of Vk . • N>k (U ; G) := |{(u, v) ∈ U × U : dG (u, v) > k}|, defined as the number of ordered node pairs in U that are more than k hops apart in G, quantifies the number of within-subgraph filter entries excluded by the k-hop support constraint defining Vk . • s∂ := maxu∈U,v∈U c |Juv |, with s∂ = 0 when U = ∅ or U c = ∅, quantifies the strength of boundary dependence from U c to U , and captures the performance error induced by boundary propagation between U and U c . • sc := maxu,v∈U,dG (u,v)>k |Juv |, with sc = 0 when N>k (U ; G) = 0, quantifies the strength of withinsubgraph oracle interactions that lie outside the representable k-hop support of Vk . Theorem 4. Suppose Assumption 1 holds. Then, we have the following bounds: (i) The intrinsic performance error 2 RL2 (F∗U ) ≤ σU + κmax |U ||U c |s2∂ .
(20)
∥F∗U − F̄m ∥2MU U ≤ κmax N>k (U ; G) sc + s∂ ∥MU c U M−1 U U ∥1
∥F̄m − F̄m,η ∥2MU U η2 ≤ κmin (κmin + η)2
2
. (21)
(22) X
2
(JM)uv .
u,v∈U dG (u,v)≤k
(iv) For any β ∈ (0, 1), if n is sufficiently large, then with probability at least 1 − β, the estimation error is bounded as ∥F̄m,η − F̂(n) m,η ∥MU U ! r √ κmax m log(m/β) ≤ O κmin /2 + η n ! r log(m/β) +O m Θη , n where O(·) is the big-O notation, and 21
Θη :=
1
κmin + η
X
u,v∈U dG (u,v)≤k
2 (JM)uv .
As shown in Theorem 4, increasing k can reduce the approximation error but enlarges the filter-space Vk with dimension m, potentially increasing the estimation error in finite samples. Likewise, decreasing η reduces the regularization bias but may increase the estimation error. The overall risk therefore balances the approximation error, regularization bias, and estimation error through k, m, n, and η. The first two bounds, bounds (i) and (ii), characterize the performance error and approximation error specific to SFL. The former quantifies the performance error from predicting with only xU , while the latter quantifies the approximation error introduced by enforcing k-hop support. Together, they relate these errors to subgraph restriction, graph distance, and the input-output distribution. The remaining bounds, bounds (iii) and (iv), characterize the regularization bias and estimation error within a fixed filter space. They quantify, respectively, the effect of ridge regularization and the finite-sample deviation governed by n, m, η, and data conditioning. V. N UMERICAL E XPERIMENTS In this section, we apply SFL in filtering, reconstruction and prediction tasks.2 We compare the proposed SFFA-based SFL filters with data-agnostic filters, structure-agnostic filters, and polynomial-based filters.
8
where
TABLE I P RIMITIVES USED IN EXPERIMENTS . Primitives on GU eind L eKron L
erand,i , L i = 1, 2, 3, . . . ∪
eUk L
Description the normalized induced subgraph Laplacian on GU the normalized Kron-reduced Laplacian on U derived from G normalized Laplacians from independently sampled p0 = 0.9 induced sub-subgraphs of U , zeropadded to U the normalized Laplacian of the union of the distance-1, 2, 3, . . . , k subgraphs normalized distance-k subgraph Laplacian
(Bi − ρ) , B ∼ Bernoulli(ρ), ρ = 0.8; ε= p ρ(1 − ρ) u ℓτ,δ (u) = δ · τ ln 1 + exp δ u + (1 − τ ) ln 1 + exp − , τ = 0.8, δ = 0.1. δ
For each trial of SFL filtering, we randomly sample a subset U ⊂ V containing N0 = γN nodes to define the subgraph GU , e with γ = 0.1, 0.2, . . . , 0.9. We instantiate the subgraph filter bank according to Section V-A. To control the maximum size A. Subgraph Filter Banks and Baselines of the SFFA-based filter bank, we set the parameter budget to The primitives used to construct filter banks are listed in αN β with α = 1 and β = 1.5 as specified in (3). To determine 0 e denotes the normalized version of L. Table I. Recall that L the (k, r) pair for the SFFA-based filter for each given N0 , we Given the number of primitives k and the maximum order r, we fix r = 3 (which provides non-trivial filtering without overdescribe baseline SFL methods and our proposed SFFA below. relying on distance-based subgraph Laplacians) and maximize • Numerical LMMSE in (6) corresponds to optimization k. We compare the proposed distance-based subgraph Laplaover the maximal subgraph filter space RN0 ×N0 with N02 cian SFFA-based filters against other SFL methods using the trainable parameters, and is included only as a reference. same loss function for training. • Single-GSO polynomials denoted as From Table II, we have the following observations: e ind ], R≤r [L e Kron ], R≤r [L e ∪k ], which are order-r R≤r [L U • The numerical LMMSE is competitive yet suboptimal polynomial filters of different GSOs. even with sufficient training data. This is because it esti• Distance-based subgraph Laplacian polynomials denoted mates the oracle LMMSE filter in (6), which is optimal e [1] , L e [2] , . . . , L e [k] ], cf. Section III-A. as R≤r [L U U U only under the least squares loss criterion. • Random-group Laplacian algebra. We use • The polynomial filter families adapt standard GSO-based e rand,1 , L e rand,2 , . . . , L e rand,k ⟩, e rand,i R≤r ⟨L where L filtering to subgraphs, but their performance is suboptimal denotes the normalized Laplacian of the induced subgraph because their filter spaces are inherently limited. For the of GU obtained by sampling a γ0 = 0.9 fraction of same maximum order r = 3, a polynomial filter captures nodes from U , zero-padded to U , for i = 1, . . . , k. It only a single message-passing pattern, whereas the SFFA is a baseline to build up a matrix algebra structure with filter space supports a richer set of patterns. randomized subgraph connections. e [1] , L e [2] , . . . , L e [k] ⟩ • The proposed SFFA filter space R≤r ⟨L U U U • Distance-based subgraph Laplacian SFFA. Our proachieves the best performance. Under the same param[1] e [2] [k] e e posed method R≤r ⟨LU , LU , . . . , LU ⟩ uses normalized eter budget, it consistently outperforms all polynomial distance-based subgraph Laplacians and the SFFA filter e [1] , L e [2] , . . . , L e [k] ] by leveraging a richer filters and R≤r [L U U U bank structure. noncommutative algebra generated by multiple subgraphsupported primitives. Moreover, by using distance-based subgraph Laplacians as primitives, this filter space enB. Semi-Synthetic Subgraph Filtering codes more informative message-passing schemes than We use the graph G and signals x from the METR-LA e rand,1 , L e rand,2 , . . . , L e rand,k ⟩, which is built from R≤r ⟨L dataset [45]. After removing edge directions, the resulting randomly selected sub-subgraphs. graph contains N = 207 nodes. We retain only the time stamps We also conduct significance tests for each fixed subgraph with complete sensor readings and split the data chronologically ratio γ. We use paired one-sided t-tests with the proposed using a 7:3 ratio for train and test, respectively. We evaluate the behavior of different subgraph filter banks in SFFA as the reference method. Specifically, for each competing a setting with a nonlinear ground-truth function, non-Gaussian method M, we form the paired loss differences skewed noise, and a nontrivial loss function. To construct the (M,p) di = LM,i (p) − LSFFA,i (p) , i = 1, . . . , 10, output y, we let where a positive mean difference indicates that SFFA achieves e 2x L e 2 Lx e ; a smaller test loss. The null and alternative hypotheses are f (x) = 20(I − L) ⊙ tanh q 1 e2 therefore ∥L x∥22 [k] LU
N
H0 : E[di (M,p) ] ≤ 0,
w = 20ε;
H1 : E[di (M,p) ] > 0.
N
L(ŷU , yU ) =
0 1 X ℓτ,δ (ŷj − yj ), N0 j=1
2 The code is available at https://github.com/temperierte/DSSO.
For each subgraph ratio p, the resulting p-values from comparing SFFA against all competing methods are corrected using the Holm-Bonferroni procedure with a predetermined significance level αs = 0.05.
9
TABLE II T EST LOSS WITH STANDARD DEVIATION FOR SEMI - SYNTHETIC SUBGRAPH FILTERING ON METR-LA WITH PARAMETER BUDGET 1 · N01.5 , WITH THE BEST , SECOND , AND THIRD BEST PERFORMANCE HIGHLIGHTED . γ = 0.1 (4, 3)
Subgraph ratio (k, r)
γ = 0.2 (6, 3)
γ = 0.3 (7, 3)
γ = 0.4 (8, 3)
γ = 0.6 (10, 3)
γ = 0.7 (11, 3)
γ = 0.8 (12, 3)
γ = 0.9 (13, 3)
14.61 ± 0.54
14.01 ± 0.44
13.66 ± 0.33
13.16 ± 0.17
12.90 ± 0.14
Numerical LMMSE
20.06 ± 0.87
eind ] R≤r [L eKron ] R≤r [L e∪Uk ] R≤r [L
20.14 ± 1.43 20.69 ± 1.22 20.58 ± 1.01 20.55 ± 0.72 20.49 ± 0.53 20.34 ± 0.45 20.51 ± 0.34 20.50 ± 0.15 20.42 ± 0.13 19.93 ± 1.52 20.31 ± 1.22 20.38 ± 0.95 20.41 ± 0.63 20.40 ± 0.47 20.28 ± 0.44 20.47 ± 0.30 20.47 ± 0.15 20.41 ± 0.13 19.58 ± 1.55 20.02 ± 1.15 19.92 ± 0.89 19.56 ± 0.65 19.47 ± 0.48 19.42 ± 0.47 19.54 ± 0.34 19.48 ± 0.16 19.39 ± 0.11
[1]
[2]
[k]
[1]
[2]
[k]
18.14 ± 0.87 16.58 ± 0.69 15.37 ± 0.52
γ = 0.5 (9, 3)
eU , L eU , . . . , L eU ] R≤r [L 18.69 ± 1.60 18.31 ± 0.79 18.24 ± 0.90 17.98 ± 0.76 17.35 ± 0.56 17.06 ± 0.49 17.03 ± 0.27 17.05 ± 0.19 17.00 ± 0.16 erand,1 , L erand,2 , . . . , L erand,k ⟩ 18.01 ± 1.88 15.07 ± 0.86 14.55 ± 0.70 14.38 ± 0.51 14.23 ± 0.33 14.16 ± 0.51 14.05 ± 0.32 14.01 ± 0.47 14.01 ± 0.34 R≤r ⟨L eU , L eU , . . . , L eU ⟩ R≤r ⟨L
14.51 ± 0.69
13.97 ± 0.40 13.58 ± 0.35
13.29 ± 0.28
13.16 ± 0.25
13.01 ± 0.32
12.97 ± 0.35 12.93 ± 0.23 12.81 ± 0.14
TABLE III H OLM -B ONFERRONI - ADJUSTED p- VALUES OF SIGNIFICANCE TEST OVER PROPOSED SFFA IN SUBGRAPH FILTERING TASK . γ = 0.1 (4, 3)
Subgraph ratio (k, r)
[2]
γ = 0.3 (7, 3)
γ = 0.4 (8, 3)
γ = 0.5 (9, 3)
γ = 0.6 (10, 3)
γ = 0.7 (11, 3)
γ = 0.8 (12, 3)
γ = 0.9 (13, 3)
1.22×10−7 3.51×10−8 3.81×10−9 8.40×10−10 4.92×10−11 7.65×10−12 4.53×10−12 1.52×10−14 1.78×10−17 3.30×10−7 3.29×10−8 3.05×10−9 4.55×10−10 2.32×10−11 4.16×10−12 1.80×10−12 1.18×10−14 1.67×10−17 3.16×10−7 2.93×10−8 3.11×10−9 1.19×10−9 4.61×10−11 1.10×10−11 6.32×10−12 3.14×10−14 1.38×10−17
eind ] R≤r [L eKron ] R≤r [L e∪Uk ] R≤r [L [1]
γ = 0.2 (6, 3)
[k]
eU , L eU , . . . , L eU ] R≤r [L 1.40×10−6 1.94×10−8 8.53×10−8 1.95×10−8 erand,1 , L erand,2 , . . . , L erand,k ⟩ 3.29×10−5 2.17×10−3 4.94×10−4 2.72×10−5 R≤r ⟨L
According to Table III, the null hypothesis is rejected for all comparisons under each fixed subgraph ratio γ, supporting the statistical superiority of SFFA for γ = 0.1, 0.2, . . . , 0.9. C. Subgraph Signal Reconstruction We evaluate multiple subgraph filtering methods on a bandlimited signal reconstruction task using subgraphs derived from the Windmill large dataset [46]. To construct the ambient graph G with N = 319 nodes, we first build an unweighted, symmetric 5-nearest-neighbor graph, which yields two connected components. We then connect these components by adding a single inter-component edge corresponding to the largest original proximity weight between them, resulting in the final graph G with a total of 999 edges. The raw Windmill dataset contains T = 17, 472 timestamps, each associated with a graph signal defined on the node set V of G. From these raw signals, we construct the target signal yi , i = 1, . . . , T , as a Ke bandlimited signal with respect to the normalized Laplacian L i of G, with K = 250. The input signal x is obtained by masking yi over a randomly selected missing-node set UM ⊂ U of size NM . We use the first n = 200 raw signals for training and the subsequent n0 = 200 raw signals for testing. 1) Different subgraph sizes: For each trial of SFL on reconstruction with (x, y) restricted to a subgraph, we randomly pick a subset U ⊂ V with N0 = γN nodes to generate the subgraph GU , with γ ∈ {0.3, 0.4, 0.5, 0.6, 0.7}. We further randomly choose a missing node set UM ⊂ U with NM = γ1 N nodes, where p1 = 0.1, and the goal is to reconstruct yU from xU . Besides numerical LMMSE reference, we also report an asymptotic oracle LMMSE baseline, which estimates the unrestricted subgraph LMMSE operator using the subgraph signals from all T = 17, 472 timestamps, thereby approximating the oracle LMMSE filter. We compare the proposed distance-based SFFA with other structured SFL filter banks and the numerical LMMSE baseline.
9.13×10−9 2.45×10−10 9.47×10−11 1.30×10−12 1.81×10−15 1.85×10−6 4.87×10−7 8.20×10−6 7.40×10−6 8.10×10−7
We set the parameter budget αN0β with α = β = 1 according to (3). We fix r = 2 and maximize k to exploit the budget, leading to k = 9, 10, 12, 13, 14 for γ = 0.3, 0.4, 0.5, 0.6, 0.7, respectively. For the three single-GSO polynomial baselines, we separately increase their degrees from 2 to 6 and report the best result within each family to indicate the upper limit of these polynomial filters. The results in Table IV indicate that the SFFA filter bank with distance-based subgraph Laplacians consistently outperforms all competing methods for γ = 0.3, 0.4, 0.5. As expected, as γ and correspondingly k increases, the performance becomes similar to random-group SFFA since the random group now has a high probability of selecting DSSOs with similar properties as the primitives in the distance-based subgraph Laplacian SFFA. With only 200 training samples, numerical LMMSE performs suboptimal because of the numerical instability issues; nevertheless, since it uses the full N02 -dimensional matrix space, it is reported only as a reference and excluded from the competing methods. These results demonstrate that with appropriately chosen Laplacian primitives, a maximum order of r = 2 suffices to construct a sufficiently expressive SFFA filter space. In contrast, traditional GSO filtering quickly reaches its representational limits regardless of the maximum order r, as it is inherently constrained to a single message propagation scheme. For reference, the asymptotic oracle LMMSE provides an empirical approximation to the population lower bound for subgraph-only linear filters under the L2 loss. We also conduct the same significance test as in Section V-B, for each fixed γ and significance level αs = 0.05[47]. Referring to Table V, excluding LMMSE-based methods, the corrected tests show that our proposed SFFA is significantly better than all competing methods, except for e rand,1 , L e rand,2 , . . . , L e rand,k ⟩ at γ = 0.5, 0.6, 0.7, where R≤2 ⟨L the differences are not statistically significant after correction.
10
TABLE IV T EST RMSE ×10−2 FOR SUBGRAPH SIGNAL RECONSTRUCTION WITH PARAMETER BUDGET 1 · N01 , WITH THE BEST , SECOND , AND THIRD BEST PERFORMANCE HIGHLIGHTED . LMMSE RESULTS ARE PROVIDED AS REFERENCES .
γ = 0.3 9
γ = 0.4 10
Asymptotic Oracle LMMSE Numerical LMMSE
6.50 ± 0.47 9.30 ± 0.72
5.76 ± 0.33 9.85 ± 0.82
eind ] Best R≤r [L eKron ] Best R≤r [L e∪Uk ] Best R≤r [L
16.81 ± 2.00 14.62 ± 1.26 12.92 ± 2.40 11.40 ± 1.10 11.59 ± 1.88 11.97 ± 1.59 11.30 ± 0.87 11.52 ± 1.46 10.76 ± 1.00 11.03 ± 1.39 12.33 ± 0.84 11.99 ± 0.64 12.44 ± 0.90 12.51 ± 0.70 12.47 ± 0.90
[1]
[k]
9.94 ± 0.97 8.98 ± 2.18
9.39 ± 0.54 7.37 ± 0.46
9.27 ± 0.83 7.74 ± 1.57
[1]
[k]
8.13 ± 0.61
7.56 ± 0.39
7.44 ± 0.62
Subgraph ratio k
γ = 0.5 12
eU , . . . , L eU ] R≤2 [L 10.92 ± 1.30 9.97 ± 0.72 erand,1 , . . . , L erand,k ⟩ 14.57 ± 2.12 11.27 ± 1.72 R≤2 ⟨L eU , . . . , L eU ⟩ R≤2 ⟨L
8.86 ± 0.62
8.37 ± 0.55
γ = 0.6 13
γ = 0.7 14
5.15 ± 0.20 4.49 ± 0.34 3.96 ± 0.23 10.71 ± 0.46 12.48 ± 1.01 22.43 ± 3.07
TABLE V H OLM -B ONFERRONI - ADJUSTED p- VALUES OF SIGNIFICANCE TEST OVER PROPOSED SFFA IN SUBGRAPH SIGNAL RECONSTRUCTION TASK . N ON - SIGNIFICANT RESULTS AT LEVEL αs = 0.05 ARE BOLDFACED .
γ = 0.3 9
Subgraph ratio k
1.30×10−7 1.64×10−7 9.49×10−6 3.16×10−7 1.24×10−8 8.29×10−9
eind ] Best R≤r [L eKron ] Best R≤r [L e∪Uk ] Best R≤r [L [1]
γ = 0.4 10
γ = 0.5 12
γ = 0.6 13
γ = 0.7 14
4.02×10−5 6.07×10−6 2.66×10−9
5.81×10−7 9.30×10−7 4.59×10−9
3.91×10−6 3.27×10−7 5.83×10−10
[k]
eU , . . . , L eU ] R≤2 [L 1.15×10−5 7.81×10−7 2.79×10−6 4.48×10−7 4.58×10−7 erand,1 , . . . , L erand,k ⟩ 4.20×10−6 3.17×10−4 1.00×10−1 9.50×10−1 2.04×10−1 R≤2 ⟨L SFFA budget analysis
Test RMSE on missing nodes
0.110 (3,2) (2,3)
0.105 0.100
(2,5)
(2,4)
(2,6)
(4,2)
0.095
(5,2)
(3,3)
(3,4)
(6,2)
0.090
(4,3)
(7,2)
0.085 0.080
(8,2)
0
20
40
60
80
(9,2)
100
Nearly all tested (k, r) pairs for the distance-based subgraph Laplacian SFFA outperform numerical LMMSE, with the sole exception of (2, 2), further underscoring the importance of a sufficiently expressive subgraph filter bank. • The graph G in our experimental setting (N = 319 nodes) is sparse with 999 edges. As discussed in Section III-D, such sparsity favors SFFA designs with more primitives over those with higher maximum order. This is reflected in the results in two ways: fixing k and increasing r yields no notable improvement for r ≥ 4, whereas fixing r and increasing k consistently improves the performance of the subgraph filter bank. •
SFFA r = 2 SFFA r = 3 SFFA r = 4 SFFA r = 5 SFFA r = 6
(2,2)
0.115
(5,3) (10,2)
120
Number of learned SFFA coefficients
(11,2)
(12,2)
140
160
Fig. 4. Test RMSE for subgraph signal reconstruction for different parameters (k, r).
D. Traffic Flow Prediction on Subgraphs
2) Parameter budget analysis: We fix γ = 0.5 and report the performance of the distance-based subgraph Laplacian SFFA over all (k, r) pairs with k, r ≥ 2, subject to the constraint that the number of trainable parameters does not exceed the budget N0 . For reference, we also include the performance of numerical LMMSE, as well as the best-performing instances of e ind ], R≤r [L e Kron ], and R≤r [L e ∪12 ]. The following obserR≤r [L U vations can be drawn from Fig. 4:
We now evaluate the performance of different SFL methods on a subgraph traffic flow prediction task using the same dataset METR-LA dataset [45] in Section V-B. We split the data in a 7:1:2 ratio for training, validation, and testing, respectively. Given input and output horizons Tin and Tout , each inputoutput subgraph signal pair indexed by (t1 , t2 ), where 1 ≤ t1 ≤ Tin and 1 ≤ t2 ≤ Tout , is modeled by a linear subgraph filter FtU1 ,t2 ∈ span S(GU ). Specifically, for each training window, the prediction is given by
• The polynomial filter spaces induced by single-GSO filter-
ing on the subgraph are inherently limited in expressiveness, causing all three single-GSO methods to perform worse than numerical LMMSE. Importantly, these structural limitations cannot be overcome by increasing the maximum filter order.
PU ŷ
t2
=
Tin X
(t ,t )
FU 1 2 PU xt1 .
t1 =1
Therefore, the traffic prediction task can be formulated as a multi-input multi-output SFL problem in which all Tin × Tout
11
filters belong to the same subgraph filter space span S(GU ) but use distinct coefficients. For prediction, we set the input horizon to Tin = 12 and the output horizon to Tout = 3, and slide time windows of length Tin + Tout across each split of the dataset. For each SFL trial on subgraph prediction, we select a subset U ⊂ V with N0 = γN nodes to construct the subgraph GU , where γ = 0.3, 0.4, . . . , 0.7. For single-GSO filter banks, we set r = 3. For [1] [2] [k] R≤r [LU , LU , . . . , LU ], R≤r ⟨Lrand,1 , Lrand,2 , . . . , Lrand,k ⟩, [1] [2] [k] and R≤r ⟨LU , LU , . . . , LU ⟩, we use (k, r) = (10, 2). We optimize using the least-squares loss. In this task, we use the autoregressive (AR) model as the basic baseline: ŷut2 =
Tin X
a(t1 ,t2 ) xtu1 ,
t1 =1
where xtu1
denotes the scalar input signal at node u ∈ U , extracted from xt1 . This linear model treats the time series at each node independently. For each method and each p, we report the test MSE and the relative improvement (RI) over AR. Additional optimization details are provided in ?? in the supplementary material. From Table VI, we observe that the proposed distance-based subgraph Laplacian SFFA consistently outperforms competing methods with stable RI values. These findings demonstrate the advantage of an SFFA-based subgraph filter bank in conjunction with structured DSSO primitives, even for SFL tasks with multiple inputs and outputs. We also conduct the same significance test as in Section V-B, for each fixed γ and significance level αs = 0.05. Referring to Table VII, the corrected tests show that our proposed SFFA is significantly better than all competing methods, except for e rand,1 , L e rand,2 , . . . , L e rand,k ⟩ at γ = 0.3. R≤2 ⟨L VI. C ONCLUSION
discrete-time graph signals by learning subgraph-supported joint-domain filters via a spatio-temporal filter algebra that couples spatial filtering with temporal dependency modeling. Another direction is subgraph sheaf diffusion [49], which generalizes the structural component of SFL from subgraph Laplacian-based filters to sub-sheaf diffusion operators, where local spaces and restriction maps provide a more flexible mechanism for aligning heterogeneous or phase-shifted signals. A PPENDIX A S ELECTED P ROOFS In this section we provide the proof sketch for Theorem 3 and the complete proof of Theorem 4, bound (i). Other proofs are provided in the supplementary material. Proof sketch of Theorem 3. The decomposition follows by tracking which splits are orthogonal. First, since w is uncorrelated with both x and f (x), the cross terms vanish, and hence 2 (n) E∥PU f (x) − F̂(n) m,η xU ∥2 ≤ RL2 (F̂m,η ).
Then, we split the risk through F∗U and F̄m : ∗ ∗ RL2 (F̂(n) m,η ) =RL2 (FU ) + RL2 (F̄m ) − RL2 (FU ) + RL2 (F̂(n) m,η ) − RL2 (F̄m ) .
The first difference is an equality because the residual of F∗U is orthogonal to every direction in RN0 ×N0 , so RL2 (F̄m ) − RL2 (F∗U ) = ∥F̄m − F∗U ∥2MU U . The second difference is also an equality because the residual of (n) F̄m is orthogonal to every direction in Vk , and F̂m,η −F̄m ∈ Vk . Hence (n) 2 RL2 (F̂(n) m,η ) − RL2 (F̄m ) = ∥F̂m,η − F̄m ∥MU U .
Finally, we split the last norm: In this paper, we introduced a framework for subgraph filter learning and developed a principled method based on subgraph (n) F̂(n) m,η − F̄m = F̂m,η − F̄m,η + F̄m,η − F̄m . filter free algebras for learning under partial graph observations. By leveraging distance-k subgraphs, the proposed construction This split is not orthogonal, so it only gives an inequality with captures multi-scale neighborhood interactions in the ambient a factor 2: graph, yielding a structured Laplacian algebra that is both 2 (n) 2 ∥F̂(n) m,η − F̄m ∥MU U ≤ 2∥F̄m,η − F̂m,η ∥MU U interpretable and expressive. From a theoretical standpoint, we characterized the performance gap between learned subgraph +2∥F̄m − F̄m,η ∥2MU U . filters and the ground-truth mapping, and showed that this gap arises from multiple sources, including the intrinsic lim- Combining these three splits gives (19). itations of linear filtering, distance-based restrictions of the Proof of bound (i). Let ϵ(x) := f (x) − Jx. Then, filter space, numerical approximation error, and regularization ⊺ ⊺ ⊺ E[ϵ(x)x ] = E[f (x)x ] − JE[xx ] effects. These findings clarify key trade-offs in subgraph-based ⊺ ⊺ learning. Empirically, experiments on real-world traffic and = E[f (x)x ] − E[f (x)x ]M−1 M = 0. wind-speed datasets show that the proposed framework consisc tently outperforms numerical filter-approximation methods and Partition J and M according to U and U . Then polynomial subgraph filters, underscoring its practical effectivePU f (x) = JU U xU + JU U c xU c + PU ϵ(x). ness. Future work may consider more challenging settings, in- By the definition of the oracle LMMSE subgraph filter and cluding distribution shift, time-varying signals, and signals on by the assumption that the noise is uncorrelated with x, we ⊺ ⊺ −1 ]M−1 higher-order structures. One promising direction is joint spatio- have F∗U = E[yU xU U U = E[PU f (x)xU ]MU U . Using ⊺ temporal SFL [48], which extends the present framework to the decomposition above and E[ϵ(x)xU ] = 0, we obtain
12
TABLE VI AVERAGE TEST MSE ( FIRST SUB - ROW ) AND RI ( SECOND SUB - ROW ) WITH STANDARD DEVIATION FOR TRAFFIC FLOW PREDICTION ON METR-LA, WITH THE BEST , SECOND , AND THIRD BEST PERFORMANCE HIGHLIGHTED . γ = 0.3
γ = 0.4
γ = 0.5
γ = 0.6
γ = 0.7
AR
69.09 ± 1.75
69.44 ± 1.16
69.81 ± 0.75
69.88 ± 1.01
69.89 ± 1.01
eind ] R≤3 [L
68.79 ± 1.70 69.04 ± 1.15 69.36 ± 0.73 69.37 ± 0.97 69.32 ± 0.95 0.44 ± 0.12% 0.57 ± 0.10% 0.64 ± 0.08% 0.74 ± 0.06% 0.81 ± 0.09%
eKron ] R≤3 [L
68.76 ± 1.73 69.01 ± 1.17 69.35 ± 0.75 69.36 ± 0.95 69.33 ± 0.94 0.48 ± 0.07% 0.61 ± 0.08% 0.65 ± 0.08% 0.74 ± 0.09% 0.80 ± 0.10%
e∪U ] R≤3 [L
68.89 ± 1.74 69.23 ± 1.18 69.58 ± 0.74 69.65 ± 0.98 69.64 ± 0.97 0.29 ± 0.07% 0.30 ± 0.09% 0.32 ± 0.08% 0.33 ± 0.05% 0.35 ± 0.07%
Subgraph ratio
[1]
68.65 ± 1.74 68.92 ± 1.18 69.23 ± 0.74 69.27 ± 0.95 69.23 ± 0.93 0.63 ± 0.12% 0.74 ± 0.10% 0.82 ± 0.09% 0.88 ± 0.10% 0.93 ± 0.11%
[10]
eU , . . . , L eU ] R≤2 [L
68.44 ± 1.65 68.76 ± 1.15 69.11 ± 0.71 69.15 ± 0.99 69.12 ± 0.95 erand,1 , . . . , L erand,10 ⟩ 0.94 R≤2 ⟨L ± 0.22% 0.98 ± 0.11% 1.00 ± 0.10% 1.05 ± 0.09% 1.09 ± 0.08% [1]
68.40 ± 1.74 68.62 ± 1.17 68.94 ± 0.76 68.99 ± 0.95 68.97 ± 0.92 1.00 ± 0.26% 1.18 ± 0.16% 1.24 ± 0.07% 1.28 ± 0.11% 1.31 ± 0.14%
[10]
eU , . . . , L eU ⟩ R≤2 ⟨L
TABLE VII H OLM -B ONFERRONI - ADJUSTED p- VALUES OF SIGNIFICANCE TEST OVER PROPOSED SFFA IN SUBGRAPH SIGNAL PREDICTION TASK . N ON - SIGNIFICANT RESULTS AT LEVEL αs = 0.05 ARE BOLDFACED . γ = 0.3
Subgraph ratio
γ = 0.4
γ = 0.5
γ = 0.6
γ = 0.7
AR
2.42 × 10−6
5.81 × 10−9 3.07 × 10−12 2.25 × 10−10 1.53 × 10−9
eind ] R≤3 [L eKron ] R≤3 [L e∪U ] R≤3 [L
1.09 × 10−4 1.09 × 10−4 1.90 × 10−5
4.26 × 10−6 1.34 × 10−8 4.26 × 10−9 6.43 × 10−9 2.05 × 10−6 1.03 × 10−8 3.87 × 10−9 4.88 × 10−9 9.02 × 10−9 3.99 × 10−11 2.25 × 10−10 1.29 × 10−9
[1]
[10]
eU , . . . , L eU ] R≤2 [L 1.23 × 10−4 2.74 × 10−7 e e R≤2 ⟨Lrand,1 , . . . , Lrand,10 ⟩ 2.75 × 10−1 3.12 × 10−4 ⊺ E[PU f (x)xU ] = JU U MU U + JU U c MU c U . Hence, F∗U = JU U + JU U c MU c U M−1 U U . Therefore, PU f (x) − F∗U xU = JU U c xU c − MU c U M−1 U U xU + PU ϵ(x).
:= xU c − MU c U M−1 For brevity, define r U U xU . Then, h i ⊺ −1 c c E rU c |U rU c |U = E xU − MU U MU U xU ⊺ −1 xU c − MU c U MU U xU U c |U
= MU c U c − MU c U M−1 U U MU U c . Moreover, since E[ϵ(x)x⊺ ] = 0, we also have h i ⊺ ⊺ E PU ϵ(x)rU c |U = E[PU ϵ(x)xU c ] ⊺
− E[PU ϵ(x)xU ]M−1 U U MU U c = 0. Thus the cross term vanishes, and RL2 (F∗U ) = E∥PU f (x) − F∗U xU ∥22
1.48 × 10−8 3.45 × 10−5
3.87 × 10−9 1.23 × 10−4
6.20 × 10−9 8.55 × 10−6
Using the standard trace bound ⊺
tr(SCS ) ≤ λmax (C) ∥S∥2F ,
C ⪰ 0,
with S = JU U c and C = MU c U c − MU c U M−1 U U MU U c , and using the Loewner order of Schur complement, we get 2 RL2 (F∗U ) − σU
2 ≤ λmax MU c U c − MU c U M−1 U U MU U c ∥JU U c ∥F ≤ λmax (MU c U c ) ∥JU U c ∥2F ≤ κmax ∥JU U c ∥2F . Finally, by the definition of s∂ , X X 2 ∥JU U c ∥2F = |(J)uv | ≤ |U ||U c |s2∂ . u∈U v∈U c
Substituting this into the previous display gives 2 RL2 (F∗U ) ≤ σU + κmax |U ||U c |s2∂ ,
which concludes the proof.
= E∥JU U c rU c |U + PU ϵ(x)∥22 ⊺ = tr JU U c MU c U c − MU c U M−1 U U MU U c JU U c + E∥PU ϵ(x)∥22 . 2 By the definition of σU , this becomes
RL2 (F∗U ) ⊺ 2 = σU + tr JU U c MU c U c − MU c U M−1 U U MU U c JU U c .
R EFERENCES [1] D. Shuman, S. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field of signal processing on graphs: Extending highdimensional data analysis to networks and other irregular domains,” IEEE Signal Process. Mag., vol. 30, no. 3, pp. 83–98, Apr. 2013. [2] A. Ortega, P. Frossard, J. Kovačević, J. M. F. Moura, and P. Vandergheynst, “Graph signal processing: Overview, challenges, and applications,” Proc. IEEE, vol. 106, no. 5, pp. 808–828, May 2018.
13
[3] G. Mateos, S. Segarra, A. G. Marques, and A. Ribeiro, “Connecting the dots: Identifying network structure via graph signal processing,” IEEE Signal Process. Mag., vol. 36, no. 3, pp. 16–43, May 2019. [4] B. Girault, “Stationary graph signals using an isometric graph translation,” in 2015 23rd European Signal Processing Conference (EUSIPCO), Aug 2015, pp. 1516–1520. [5] N. Perraudin and P. Vandergheynst, “Stationary signal processing on graphs,” IEEE Trans. Signal Process., vol. 65, no. 13, pp. 3462–3477, July 2017. [6] X. Jian, W. P. Tay, and Y. C. Eldar, “Kernel based reconstruction for generalized graph signal processing,” IEEE Trans. Signal Process., pp. 1–15, 2024. [7] X. Jian, M. Gölz, F. Ji, W. P. Tay, and A. M. Zoubir, “A graph signal processing perspective of network multiple hypothesis testing with false discovery rate control,” IEEE Trans. Signal Process., vol. 73, pp. 3496– 3512, 2025. [8] X. Dong, D. Thanou, P. Frossard, and P. Vandergheynst, “Learning Laplacian matrix in smooth graph signal representations,” IEEE Trans. Signal Process., vol. 64, no. 23, pp. 6160–6173, Dec. 2016. [9] H. E. Egilmez, E. Pavez, and A. Ortega, “Graph learning from data under Laplacian and structural constraints,” IEEE J. Sel. Topics Signal Process., vol. 11, no. 6, pp. 825–841, Sep. 2017. [10] Z. Zhu, S. Jin, X. Song, and X. Luo, “Learning graph structure with stationary graph signals via first-order approximation,” in 2017 22nd International Conference on Digital Signal Processing (DSP), Aug 2017, pp. 1–5. [11] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, “The graph neural network model,” IEEE Trans. Neural Netw., vol. 20, no. 1, pp. 61–80, Jan. 2009. [12] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in International Conference on Learning Representations, 2017. [13] F. Ji, Y. Zhao, S. H. Lee, K. Zhao, W. P. Tay, and J. Yang, “Graph distributional signals for regularization in graph neural networks,” IEEE Trans. Signal Inf. Process. Netw., vol. 11, pp. 670–682, 2025. [14] S. Chen, A. Sandryhaila, J. M. F. Moura, and J. Kovacevic, “Signal denoising on graphs via graph filtering,” in Proc. IEEE Global Conf. on Signal and Information Processing, Dec. 2014, pp. 872–876. [15] F. Ji, W. P. Tay, and A. Ortega, “Graph signal processing over a probability space of shift operators,” IEEE Trans. Signal Process., vol. 71, pp. 1159– 1174, 2023. [16] S. Chen, A. Sandryhaila, J. M. F. Moura, and J. Kovačević, “Signal recovery on graphs: Variation minimization,” IEEE Trans. Signal Process., vol. 63, no. 17, pp. 4609–4624, Sep. 2015. [17] S. Segarra, A. G. Marques, G. Leus, and A. Ribeiro, “Reconstruction of graph signals through percolation from seeding nodes,” IEEE Trans. Signal Process., vol. 64, no. 16, pp. 4363–4378, Aug 2016. [18] K. Qiu, X. Mao, X. Shen, X. Wang, T. Li, and Y. Gu, “Time-varying graph signal reconstruction,” IEEE J. Sel. Topics Signal Process., vol. 11, no. 6, pp. 870–883, Sep. 2017. [19] X. Wang, J. Chen, and Y. Gu, “Generalized graph signal sampling and reconstruction,” in Proc. IEEE Global Conf. on Signal and Information Processing, Dec 2015, pp. 567–571. [20] Y. Cao, J. Wang, Z. Li, X.-Q. Jiang, and X. Hou, “Time-varying EEG signal reconstruction based on local graph signal smoothness,” in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing, April 2025, pp. 1–5. [21] A. Sandryhaila and J. M. F. Moura, “Discrete signal processing on graphs: Graph fourier transform,” in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing, May 2013, pp. 6167–6170. [22] F. Ji and W. P. Tay, “A hilbert space theory of generalized graph signal processing,” IEEE Trans. Signal Process., vol. 67, no. 24, pp. 6188–6203, Dec. 2019. [23] X. Jian and W. P. Tay, “Wide-sense stationarity in generalized graph signal processing,” IEEE Trans. Signal Process., vol. 70, pp. 3414–3428, 2022. [24] P. Zhang, F. Ji, Y. Zhao, W. P. Tay, and B. Wen, “Distance-based Laplacian algebra for effective subgraph filter learning,” in 2025 Asia Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC), Oct 2025, pp. 1301–1306. [25] X. Wang, P. Liu, and Y. Gu, “Local-set-based graph signal reconstruction,” IEEE Trans. Signal Process., vol. 63, no. 9, pp. 2432–2444, May 2015. [26] N. Tremblay and P. Borgnat, “Subgraph-based filterbanks for graph signals,” IEEE Trans. Signal Process., vol. 64, no. 15, pp. 3827–3840, Aug 2016. [27] A. Loukas, “Graph reduction with spectral and cut guarantees,” Journal of Machine Learning Research, vol. 20, no. 116, pp. 1–42, 2019. [Online]. Available: http://jmlr.org/papers/v20/18-680.html
[28] B. Wu, X. Yao, B. Zhang, K.-M. Chao, and Y. Li, “Splitgnn: Spectral graph neural network for fraud detection against heterophily,” in Proceedings of the 32nd ACM international conference on information and knowledge management, 2023, pp. 2737–2746. [29] J. Wang, Y. Guo, and B. Su, “Spatio-temporal multi-subgraph gcn for 3d human motion prediction,” in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing, April 2025, pp. 1–5. [30] S. Segarra, A. G. Marques, and A. Ribeiro, “Optimal graph-filter design and applications to distributed linear network operators,” IEEE Trans. Signal Process., vol. 65, no. 15, pp. 4117–4131, Aug 2017. [31] F. Hua, C. Richard, J. Chen, H. Wang, P. Borgnat, and P. Gonçalves, “Learning combination of graph filters for graph signal modeling,” IEEE Signal Processing Letters, vol. 26, no. 12, pp. 1912–1916, Dec 2019. [32] N. Emirov, C. Cheng, J. Jiang, and Q. Sun, “Polynomial graph filters of multiple shifts and distributed implementation of inverse filtering,” Sampling Theory, Signal Processing, and Data Analysis, vol. 20, no. 1, p. 2, 2022. [33] J. Fan, C. Tepedelenlioglu, and A. Spanias, “Graph-based classification with multiple shift matrices,” IEEE Transactions on Signal and Information Processing over Networks, vol. 8, pp. 160–172, 2022. [34] S. Segarra, A. G. Marques, and A. Ribeiro, “Linear network operators using node-variant graph filters,” in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing, March 2016, pp. 4850–4854. [35] E. Isufi, F. Gama, and A. Ribeiro, “Edgenets: Edge varying graph neural networks,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 44, no. 11, pp. 7457–7473, Nov 2022. [36] G. Li, J. Yang, and Y. Chen, “Partition-wise graph filtering: A unified perspective through the lens of graph coarsening,” in Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 2, 2025, pp. 1353–1364. [37] A. G. Marques, S. Segarra, G. Leus, and A. Ribeiro, “Stationary graph processes and spectral estimation,” IEEE Trans. Signal Process., vol. 65, no. 22, pp. 5911–5926, Nov 2017. [38] E. Isufi, P. Di Lorenzo, P. Banelli, and G. Leus, “Distributed wienerbased reconstruction of graph signals,” in 2018 IEEE Statistical Signal Processing Workshop (SSP), June 2018, pp. 21–25. [39] J. Hara, Y. Tanaka, and Y. C. Eldar, “Graph signal sampling under stochastic priors,” IEEE Trans. Signal Process., vol. 71, pp. 1421–1434, 2023. [40] A. Kroizer, T. Routtenberg, and Y. C. Eldar, “Bayesian estimation of graph signals,” IEEE Transactions on Signal Processing, vol. 70, pp. 2207–2223, 2022. [41] T. Fukuhara, J. Hara, H. Higashi, and Y. Tanaka, “Period estimation for time-varying graph signals and its application to graph wiener filter,” in 2025 Asia Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC), Oct 2025, pp. 1544–1549. [42] D. Hsu, S. M. Kakade, and T. Zhang, “Random design analysis of ridge regression,” in Conference on learning theory. JMLR Workshop and Conference Proceedings, 2012, pp. 9–1. [43] J. Mourtada and L. Rosasco, “An elementary analysis of ridge regression with random design,” Comptes Rendus. Mathématique, vol. 360, no. G9, pp. 1055–1063, 2022. [44] R. Vershynin, High-Dimensional Probability: An Introduction with Applications in Data Science, ser. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018. [45] Y. Li, R. Yu, C. Shahabi, and Y. Liu, “Diffusion convolutional recurrent neural network: Data-driven traffic forecasting,” in International Conference on Learning Representations, 2018. [46] B. Rozemberczki, P. Scherer, Y. He, G. Panagopoulos, A. Riedel, M. Astefanoaei, O. Kiss, F. Beres, G. Lopez, N. Collignon et al., “Pytorch geometric temporal: Spatiotemporal signal processing with neural machine learning models,” in Proceedings of the 30th ACM international conference on information & knowledge management, 2021, pp. 4564– 4573. [47] B. Trawinski, M. Smȩtek, Z. Telec, and T. Lasota, “Nonparametric statistical analysis for multiple comparison of machine learning regression algorithms,” International Journal of Applied Mathematics and Computer Science, vol. 22, 01 2012. [48] P. Zhang, W. P. Tay, and B. Wen, “Joint spatio-temporal subgraph filter learning,” in Proc. IEEE Sensor Array and Multichannel Signal Processing Workshop, 2026, to appear. [49] ——, “Sheaf Laplacian localization for subgraph signal diffusion,” in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing, May 2026, pp. 436–440.