A Unified Spectral-Spatial Framework for GNNs: Balancing Over-Smoothing and Over-Squashing

1 Introduction

Graph-structured data has gained increasing attention in the field of machine learning and has been widely applied in various real-world domains, including bioinformatics [Yan et al., 2023], social networks [Min et al., 2021], and recommendation systems [Wang et al., 2023]. However, most classical deep learning methods are originally designed for gridstructured data such as images or sequences, which cannot directly accommodate the irregular graph data from the nonEuclidean space. To address this limitation, Graph Neural Networks (GNNs) have emerged as powerful frameworks for learning on graphs, achieving notable success in tasks such as node classification, graph classification, and link prediction.

∗Corresponding Author: Lu Bai

Most existing GNNs generally follow two dominant perspectives including spectral filtering and spatial message passing. Spectral methods are grounded in the eigendecomposition of the graph Laplacian and the graph Fourier transform, where the graph convolution is formulated as the spectral filtering operation. Although this formulation provides a solid theoretical foundation, it typically incurs high computational costs due to the eigendecomposition [Bruna et al., 2013]. To alleviate this issue, various spectral variants based on polynomial approximations or simplified filters have been proposed, such as the ChebNet [Defferrard et al., 2016], vanilla Graph Convolutional Network (GCN) [Kipf and Welling, 2017], and JacobiConv [Wang and Zhang, 2022]. Among them, the first-order approximation adopted by the vanilla GCN enables spectral filtering to be efficiently implemented in the spatial domain, where a node updates its representation by aggregating the representations of its neighbors. This process facilitates the propagation of information across nodes, offering improved interpretability. This mechanism has further driven the rapid development of spatial GNNs, such as the GraphSAGE [Hamilton et al., 2017], GIN [Xu et al., 2019], and DGCNN [Zhang et al., 2019].

Despite these advances in modeling flexibility and computational efficiency, GNNs still suffer from two fundamental challenges in practice, namely over-smoothing (OSM) [Rusch et al., 2023; Li et al., 2018; NT and Maehara, 2019; Chen et al., 2020a] and over-squashing (OSQ) [Dai et al., 2023; Singh, 2025]. As the network depth or propagation distance increases, node representations tend to become increasingly homogeneous. This homogenization degrades the discriminability of the node representations and is commonly referred to as OSM. Meanwhile, OSQ arises from the rapid expansion of the receptive field, where the information from a large number of distant nodes must be compressed into fixeddimensional embeddings, leading to severe information loss and creating an information bottleneck.

However, most existing studies treat OSM and OSQ as separate phenomena, and only a limited number of works have begun to explore the trade-off between them. For instance, FoSR [Karhadkar et al., 2023] and ProxyDelete [Jamadandi et al., 2024] investigate spectral reconnection strategies from the perspectives of the spectral gap and the Cheeger constant, aiming to improve graph structures and alleviate excessive smoothing and compression during the information propagation. From a geometric viewpoint, BORF [Nguyen et al., 2023] analyzes the relationship between edges with the positive and negative curvature as well as the OSM/OSQ phenomena, and proposes a curvature-driven graph reconnection method that can mitigate both issues to some extent. Nevertheless, these approaches largely rely on a single analytical perspective, focusing either on spectral properties or geometric characteristics. Consequently, they do not capture the interplay between spectral and spatial factors that jointly influence OSM and OSQ. A unified framework that systematically characterizes this interplay from both spectral and spatial perspectives is essential to understand the intrinsic trade-off, explain feature homogenization and information compression in deep GNNs, and guide the design of architectures that balance these phenomena effectively.

Motivated by the aforementioned observations, we revisit classical polynomial spectral filters and establish a unified spectral-spatial framework for graph convolution, aiming to systematically investigate the trade-off between OSM and OSQ in a principled manner. The main contributions of this paper are summarized as follows.

First, we establish a unified spectral-spatial analysis framework based on the polynomial spectral filters, which explicitly and rigorously characterizes the intrinsic relationship between the polynomial order k, spectral frequency selectivity, and the spatial aggregation range.

Second, within the proposed framework, we provide a systematic theoretical analysis of how the polynomial order k influences the OSM and OSQ issues in GNNs. We show that the increasing polynomial order k can enhance the spectral expressiveness and alleviate OSM caused by dominant lowfrequency components, but also simultaneously expands the spatial receptive field and further exacerbates the information compression, thereby increasing the risk of OSQ.

Third, motivated by the above analysis, we argue that a moderate polynomial order is critical for achieving a better balance between OSM and OSQ. Following this principle, we propose a new Quadratic Spectral Graph Convolution Network (QS-GCN) for graph classification, comprising a Quadratic Spectral Graph Convolution (QS-Conv) and an alignment-based readout module. Extensive experiments on multiple benchmark datasets demonstrate the effectiveness of the proposed QS-GCN.

This paper is organized as follows. Section 2 reviews the OSM and OSQ problems. Section 3 presents a unified theoretical framework, and Section 4 analyzes OSM and OSQ through this framework. Section 5 introduces the proposed trade-off strategy QS-GCN. Section 6 reports the experimental evaluation. Section 7 concludes this paper.

2 RelatedWorks

2.1 The Over-Smoothing (OSM) Problem

The OSM problem is a fundamental challenge in GNNs, where repeated message passing causes node representations to become increasingly indistinguishable, ultimately degrading the performance on both node-level and graph-level tasks. Several studies have investigated its underlying mechanisms from different perspectives. For example, [Li et al., 2018] model GCN layers as Laplacian smoothing processes and demonstrate that deeper networks result in indistinguishable node embeddings. From a spectral perspective, [NT and Maehara, 2019] and [Balcilar et al., 2021] interpret GCNs as low-pass filters that suppress high-frequency signals. Although such filtering can effectively reduce noise, the excessive smoothing inevitably blurs discriminative information. To address the OSM problem, various solutions have been proposed, including PairNorm [Zhao and Akoglu, 2019], DropEdge [Rong et al., 2020], GCNII [Chen et al., 2020b], GraphCON [Rusch et al., 2022a], G2 [Rusch et al., 2022b], and Res-GCN [Li et al., 2023].

2.2 The Over-Squashing (OSQ) Problem

The OSQ issue is another challenge for GNNs [Dai et al., 2023; Singh, 2025]. It refers to the phenomenon where the information from a large number of nodes within an expanding receptive field is excessively compressed into fixeddimensional node vectors, resulting in ineffective message propagation from distant nodes. Recently, several approaches have been proposed to alleviate OSQ. For instance, FA [Alon and Yahav, 2021] connects all nodes of the final layer to reduce the compression. SDRF [Topping et al., 2022] improves the message flow by modifying negatively curved edges. FoSR [Karhadkar et al., 2023] alleviates OSQ by optimizing the spectral gap. GTR [Black et al., 2023] rewires edges to reduce the effective resistance between nodes.

3 AUnified Spectral-Spatial Framework

This section establishes a unified spectral-spatial framework for graph convolution based on polynomial spectral filters. By explicitly connecting spectral filtering behavior with spatial neighborhood aggregation, the framework provides a principled foundation for analyzing the intrinsic trade-off between OSM and OSQ arising in GNNs.

Let G = (V, E) be an undirected graph with n nodes, represented by an adjacency matrix A ∈ {0, 1}n×n and a node feature matrix X ∈ Rn×f . To incorporate self-information into the message propagation, self-loops are added, yielding ˜ A = A+ I. Let ˜D denote the degree matrix, whose diagonal entries are given by ˜Dii = ∑j ˜ Aij. The symmetrically normalized adjacency matrix is ˆ A = ˜D- 12 ˜ A ˜D- 12 . Accordingly, the normalized graph Laplacian is ˆL = I - ˆ A. Since ˆL is symmetric and positive semi-definite, it admits the eigendecomposition ˆL = U diag(λ)U ⊤, where U ∈ Rn×n is the matrix of eigenvectors, and λ = (λ1, . . . , λn) denotes the corresponding eigenvalues.

A general spectral graph convolution is defined as

where σ(·) is a nonlinear activation function, W is a learnable weight matrix, and g(λ) denotes the element-wise evaluation of the spectral response function g(λ) on the eigenvalue vector λ, i.e., g(λ) = (g(λ1), g(λ2), . . . , g(λn)). In this paper, we focus on the k-th order polynomial spectral filter

where {αt}kt=0 are polynomial coefficients. Substituting gk(λ) into Eq. (1), we have

This derivation shows that polynomial spectral filtering is equivalent to a linear combination of powers of the normalized graph Laplacian applied to node features.

From the spatial perspective, aggregating the information from k-hop neighborhoods can be written as

Since the normalized Laplacian satisfies ˆL = I- ˆ A, the above polynomial spectral convolution is equivalent to

Applying the binomial expansion to each term, we have

Substituting this expansion into the convolution and rearranging the sums, we have

Defining

we can rewrite the above convolution compactly as

This derivation demonstrates that a k-th order polynomial spectral filter is spatially equivalent to a weighted aggregation over neighborhoods up to k hops. Thus, the polynomial order k governs both the spectral expressiveness and the spatial receptive field of the convolution.

4 Theoretical Analysis of OSMand OSQ

The unified spectral-spatial framework indicates that increasing polynomial order k allows the convolution to aggregate more information over larger neighborhoods while realizing richer spectral responses. This dual perspective provides a solid theoretical foundation for analyzing the information propagation in GNNs in relation to OSM and OSQ. Based on this foundation, we systematically investigate the impact of the polynomial order k on the OSM and OSQ issues.

4.1 Analyzing OSMwith Polynomial Order k

Generally, first-order spectral filters often yield simple monotonic frequency responses under common parameterizations, whereas higher-order polynomial filters enhance spectral expressiveness, mitigating the low-pass bias responsible for OSM. Based on this observation, we first provide a formal definition of OSM and then present a rigorous analysis to characterize its relationship with the polynomial order k.

Definition 1 (OSM). Let h(l) p ∈ Rf ′ denote the representation of node p at layer l. The OSM phenomenon occurs when the network depth increases, and all node representations tend to converge to the same vector, i.e.,

In this case, node representations discard their discriminative power and become indistinguishable.

Theorem 1. Increasing the polynomial order k of a spectral graph filter can help mitigate OSM under the following mild assumptions: (i) the normalized graph Laplacian ˆL has a finite spectrum; and (ii) there exists at least one discriminative spectral component whose contribution induces a nonzero node-wise separation.

Proof. OSM fundamentally arises from the selective suppression of discriminative spectral components by graph convolutional filtering, and stacking layers further amplifies this effect. To reveal the underlying mechanism, we analyze a single spectral filtering operation and investigate how the polynomial order k affects the preservation of discriminative information. For analytical simplicity, we omit the nonlinear activation function and the feature transformation matrix W, and consider a single-channel input signal x ∈ Rn . Let ˆx = U ⊤x. Then Eq. (1) reduces to

where u(i) is the i-th eigenvector of ˆL. Let S ⊆ {1, . . . , n} denote the set of discriminative spectral components, and define the ideal target response ri as below

For any pair of nodes p, q ∈ V , define M and E as

so that

By the non-degeneracy assumption, there exists at least one pair of nodes p, q such that Mp,q ̸= 0. Define ∆p,q := |Mp,q| > 0. For the error term, let δk = max1≤i≤n |gk(λi)- ri|. Since the eigenvectors are normalized, we have |u(i) p - u(i) q | ≤ 2 for any i. Therefore,

Since the spectrum of ˆL contains only finitely many eigenvalues, polynomial interpolation on the discrete spectral set guarantees that there exists a polynomial filter gk of sufficiently large order k such that δk ≤ ε for any ε > 0. So

In particular, once k is large enough such that 2ε√n∥x∥2 < ∆p,q, we obtain |hp -hq| > 0. This result indicates that sufficiently high-order polynomial spectral filters preserve discriminative spectral components and prevent node representations from collapsing to identical embeddings after graph convolution. Therefore, increasing the polynomial order k helps mitigate OSM.

4.2 Analyzing OSQwith Polynomial Order k

Within the unified spectral-spatial framework, the polynomial order k determines the number of node hops whose features are aggregated during graph convolution. As k increases, the convolution aggregates information from more distant neighbors, thereby expanding the spatial receptive field of each node. However, under fixed-dimensional node embeddings, this expansion can intensify information compression and lead to OSQ. In this part, we first provide a formal definition of OSQ and then analyze how the polynomial order affects it.

Definition 2 (OSQ). Let hp ∈ Rf ′ be the representation of node p after graph convolution, measuring the sensitivity of hp to the input feature of node q by the node-wise Jacobian

OSQ occurs when Jp←q is close to zero for a non-negligible fraction of node pairs (p, q) ∈ V × V , indicating that information from node q is excessively compressed and thus fails to meaningfully influence the representation of node p.

Theorem 2. Increasing the polynomial order k enlarges the spatial receptive field and can exacerbate the OSQ issue.

Proof. To isolate the intrinsic compression mechanism of OSQ, we omit the nonlinear activation and analyze a single graph convolution layer. For theoretical clarity, we consider a connected non-bipartite c-regular graph, which is commonly used in prior theoretical studies on OSQ [Nguyen et al., 2023; Karhadkar et al., 2023; Dai et al., 2023]. After adding selfloops, the augmented graph becomes (c + 1)-regular, so ˜D = (c + 1)I and ˆ A = ˜D-1/2 ˜ A ˜D-1/2 = ˜D-1 ˜ A = P, where P is the random-walk transition matrix on the augmented graph. From the spatial form in Eq. (9), we have

For any pair of nodes (p, q), let dist(p, q) = d be the shortestpath distance. Since [ ˆ As ]pq = 0 for all s < d, we obtain

By the classical spectral mixing theorem for random walks [Chung, 1997], there exist constants C0 > 0 and ρ ∈ (0, 1) such that

The stationary term 1/n is identical for all node pairs and is therefore non-discriminative. Further assume that the polynomial coefficients are bounded, i.e., |βs| ≤ B for all s = 0, . . . , k. Substituting the above bound into Eq. (20) yields

where C ′ = ∥W∥2BC0 1-ρ . This shows that, after removing the stationary averaging component, the node-specific sensitivity decays exponentially with the shortest-path distance d.

We now examine the spatial effect induced by increasing k. As k increases, progressively farther distance shells are incorporated into the receptive field. In a connected nonbipartite c-regular graph, the number of nodes in the distanced shell grows on the order of cd , whereas the above bound shows that the discriminative sensitivity of these nodes decays exponentially with d. Therefore, although higher-order convolution introduces exponentially more distant nodes, the node-specific information carried by each newly added node becomes exponentially weaker. As a result, increasing k rapidly enlarges the set of low-sensitivity node pairs, making many Jacobian entries Jp←q nearly negligible. In other words, the expansion of the receptive field does not yield a proportional gain in effective information; instead, it compresses an increasing number of weak signals into the same fixed-dimensional representation hp, thereby intensifying information mixing and aggravating the OSQ issue.

4.3 Trade-Off Insights between OSMand OSQ

To illustrate the impact of the polynomial order k on node representations, Figure 1 provides a schematic example. Here, k = 1, 2, 3 are used to represent low, medium, and high polynomial orders. The upper row depicts the spectral responses of polynomial filters at different orders. As k increases, the filter exhibits greater spectral expressiveness, which helps mitigate OSM, consistent with Theorem 1. The lower row shows the corresponding spatial receptive fields. Higher-order polynomials enlarge the receptive field, allowing information aggregation from more distant neighbors and potentially aggravating OSQ, as established by Theorem 2.

This analysis reveals the dual role of k in governing OSM and OSQ. Specifically, a small k limits spectral expressiveness, causing node representations to become overly similar and leading to OSM. In contrast, an excessively large k overly expands the receptive field, forcing weak long-range signals to be compressed into fixed-dimensional representations and thereby aggravating OSQ. Therefore, a moderate polynomial order enables a better balance between spectral discriminability and spatial locality, effectively alleviating both phenomena. In summary, selecting an appropriate k is crucial for balancing spectral filtering and spatial neighborhood aggregation. To validate this trade-off, we present experiments on the effect of polynomial order in Section 6.1.

5 The Proposed QS-GCNModel

In this section, we propose a Quadratic Spectral Graph Convolutional Network (QS-GCN) to balance OSM and OSQ, thereby enhancing the discriminative power of graph representations. Motivated by the theoretical analysis in Section 4.3 and later empirically validated in Section 6.1, we set the polynomial order to k = 2 in the proposed model. This choice balances spectral expressiveness and spatial locality, mitigating OSM while avoiding excessive OSQ. Specifically, QS-GCN consists of two main components: the Quadratic Spectral Graph Convolution (QS-Conv) and the Alignmentbased Readout Module. The former provides node-level feature extraction with an interpretable trade-off between spectral expressiveness and spatial locality. The latter aligns node features into a fixed cluster order and maps the aligned representation to the final graph-level output via a shared MultiLayer Perceptron (MLP).

5.1 The Quadratic Spectral Graph Convolution

The QS-Conv performs convolution on graph signals using a quadratic spectral polynomial. This design provides a flexible frequency response, which helps alleviate OSM, while restricting the convolutional scope to at most two hops and thus preventing excessive expansion of the receptive field. The operation is defined as

where (α0, α1, α2) are learnable coefficients for the quadratic spectral terms.

5.2 The Alignment-based Readout Module

Although OSM and OSQ are typically discussed at the node level, they also directly affect graph-level tasks. Traditional readout functions, such as sum, mean, or max, are permutation-invariant but do not explicitly preserve structural correspondence across graphs. To address this issue, we propose an alignment-based readout module that reduces indiscriminate aggregation, preserves local structural distinctions, and produces order-consistent graph representations.

Specifically, let H ∈ Rn×d denote the node feature matrix after the last graph convolution layer. We softly assign nodes to s clusters using a shared assignment function parameterized by WS ∈ Rd×s , which produces an assignment probability matrix S ∈ Rn×s as

where softmax is applied row-wise so that each row of S forms a valid probability distribution over clusters. Using S, we align the node feature matrix H into fixed-order cluster representations as

Since ˜H is order-consistent across graph samples, we flatten it into a vector of dimension sd and feed it into an MLP to assign different importance weights to each cluster, producing the final graph-level representation as

6 Experiments

In this section, we first explore the impact of the polynomial order k on graph classification performance to validate the theoretical analysis presented earlier. We then compare the effectiveness of our QS-GCN with representative graph kernels and GNNs on benchmark datasets.

6.1 Impact of Polynomial Order k

We investigate the effect of the polynomial order k on graph classification performance within the QS-GCN framework, where k is varied from 0 to 5. Experiments are conducted on representative graph classification datasets from the TUDataset. For each dataset, the model hyperparameters are kept fixed across different values of k. The detailed hyperparameter settings are provided in Section 6.2. We report the average results over 10-fold cross-validation.

As shown in Table 1, the polynomial order k has a substantial impact on classification performance. Across all datasets, k = 2 generally achieves the best results, in agreement with the trade-off analysis in Section 4.3. When k is too small, the graph filter has limited frequency selectivity and tends to bias toward low-frequency components, resulting in overly smooth node representations and degraded discriminability. In contrast, larger k increases spectral flexibility but simultaneously enlarges the spatial receptive field, compressing weak long-range signals into fixed-dimensional representations and aggravating OSQ. Overall, the quadratic setting achieves an effective balance between spectral discrimination and spatial locality, thereby mitigating both OSM and OSQ.

To further validate the generalizability of our method, we additionally evaluate it on the node classification dataset Cora and the large-scale molecular graph classification benchmark OGB-MolHIV (∼41k graphs), following the standard evaluation protocol used in GCN-based studies. We report classification accuracy (%) on Cora and ROC-AUC on OGBMolHIV. The results in Table 4 exhibit the same trend as our theoretical analysis and the observations on the TUDataset.

6.2 Performance Evaluation of QS-GCN

We further evaluate the overall performance of the proposed QS-GCN model, considering classification accuracy and the ability to mitigate the OSM and OSQ problems. Specifically, experiments are conducted on multiple benchmark graph classification datasets covering two major application domains: bioinformatics (Bio) and social networks (SN). Detailed statistics of the datasets are summarized in Table 2. All experiments are implemented using PyTorch and PyTorch Geometric and are executed on a single NVIDIA GeForce RTX 3090 GPU with 24GB of VRAM.

We initialize the polynomial spectral filters as band-pass filters whose peak frequency response is located in the midfrequency region (λ ≈ 1). Specifically, for k = 2, the coefficients are designed to produce a unimodal spectral response, given by g(λ) = -λ2+2λ. For higher-order polynomials, the coefficients are extended into a smoothly varying oscillatory pattern. The number of convolutional layers is set between 2 and 4, the node embedding dimension is fixed as 64, and the number of clusters in the readout stage is set to 8. We adopt the ReLU activation function and optimize the models using Adam. The learning rate is selected from {0.001, 0.005}, the weight decay from {10-5 , 10-4 , 10-3 }, and the batch size is set to 64. Depending on the dataset, the number of training epochs ranges from 100 to 1000. To ensure statistical robustness, we perform 10 independent repetitions of 10-fold cross-validation and report the mean classification accuracy and the standard error. Code is available on GitHub. 1

Comparison on Graph Classification Performance. We compare QS-GCN with a range of representative graph kernel methods and GNNs. The graph kernels include RWGK [Gartner et al., 2003], SPGK [Borgwardt and Kriegel, 2005], WLSK [Shervashidze et al., 2011], JTQK [Bai et al., 2014] (with q = 2), EDBMK [Xu et al., 2021], QBMK [Bai et al., 2024], and AEGK [Bai et al., 2025]. The GNNs include DGCNN [Zhang et al., 2019], DiffPool [Ying et al., 2018], ECC [Simonovsky and Komodakis, 2017], GIN [Xu et al., 2019], GraphSAGE [Hamilton et al., 2017], S2GCN [Zhu and Koniusz, 2021], JacobiConv [Wang and Zhang, 2022], MidGCN [Huang et al., 2023], GWRNN [Nikolentzos and Vazirgiannis, 2023], Co-GNN [Finkelshtein et al., 2024], LASER [Barbero et al., 2024], GNN-VPA [Schneckenreiter et al., 2024], CGP [Wilson et al., 2025], GKNN-WL, and GKNN-GL [Cosmo et al., 2025]. For DGCNN, DiffPool, ECC, GIN, and GraphSAGE, we adopt the results from [Errica et al., 2020] or evaluate them under the same experimental settings for datasets not originally reported. For S2GCN [Zhu and Koniusz, 2021], JacobiConv [Wang and Zhang, 2022], and MidGCN [Huang et al., 2023], we reimplement the models under the same experimental settings for fair comparison. For the remaining methods, we report results as presented in their original publications.

1 https://github.com/Xiaoqin0421/QS-GCN

Table 3 and 5 report the classification accuracy and standard error on each dataset. Overall, QS-GCN achieves the best or highly competitive performance on most benchmarks, demonstrating its effectiveness for graph classification. This advantage mainly stems from two aspects. First, the QSConv employs a learnable quadratic spectral polynomial filter that captures information across different frequency bands, enhancing spectral expressiveness, while the limited 2-hop propagation helps alleviate OSQ. Second, the alignmentbased readout module performs structured cluster alignment and aggregation, effectively integrating local node features with global graph structure to improve discriminative capability. To provide spatial interpretability, Figure 2 illustrates the attention weights assigned by a 3-layer QS-GCN to multi-hop neighbors of a central node on a sample graph from the MUTAG dataset. The results show that the proposed QS-GCN can dynamically adjust the importance of multi-hop information across layers.

Analysis of Over-Smoothing (OSM). To quantify the diversity of graph representations, we adopt the Average Cosine Distance (AD) as the evaluation metric. Given a graph-level representation matrix H ∈ RN×d , the AD value is defined as

where Hi and Hj denote the embeddings of the i-th and jth graphs. A higher AD value indicates greater representation diversity and thus reduced OSM. To examine robustness to network depth, we compare QS-GCN with GCN, GIN, and GraphSAGE on four representative datasets, varying the number of layers over {2, 4, 8, 16, 32, 64}. Both classification accuracy and AD are reported in Figures 3. As depth increases, QS-GCN exhibits significantly less performance degradation and consistently maintains higher AD values, whereas the baselines suffer sharp AD drops, indicating severe OSM. These results show that QS-GCN effectively alleviates OSM and remains robust under increased depth.

Analysis of Over-Squashing (OSQ). We evaluate the effectiveness of QS-GCN in mitigating the over-squashing problem by comparing our method with several GNNs specifically designed to address OSQ, including FA [Alon and Yahav, 2021], SDRF [Topping et al., 2022], FoSR [Karhadkar et al., 2023], and GTR [Black et al., 2023], and report the results as presented in their original papers. As summarized in Table 6, QS-GCN achieves competitive performance among these methods, suggesting its effectiveness in alleviating OSQ while preserving strong predictive capability.

Ablation Study on Alignment-based Readout. To further isolate the contribution of the alignment-based readout module, we replace it with a standard average readout and evaluate both variants on MUTAG, PTC MR, PROTEINS, and IMDB-B under different polynomial orders. The results are reported in Table 7. A consistent trend is observed across all datasets: regardless of the readout strategy, the performance first improves and then declines as k increases, with the best results consistently achieved at k = 2. This suggests that the spectral design governed by the quadratic polynomial plays the dominant role in balancing OSM and OSQ. Moreover, under the same polynomial order, the alignment-based readout consistently outperforms average readout, indicating its effectiveness in further enhancing graph-level representation learning through more discriminative structural preservation.

Computational Complexity. Finally, we analyze the computational complexity of QS-GCN. Let n denote the number of nodes, m the number of edges, d the feature dimension, s the number of clusters, l the number of layers, and k the polynomial order. Under a recursive propagation-based implementation, the QS-Conv requires O(kmdl) complexity. The readout module aligns node representations into s clusters followed by MLP aggregation, with complexity O(nds). Therefore, the overall complexity of QS-GCN is O(kmdl + nds), which scales approximately linearly with k when other hyperparameters are fixed. To validate this analysis, we further measure runtime per epoch and GPU memory usage under different polynomial orders on the MUTAG dataset. As summarized in Table 8, the empirical results confirm the predicted scaling behavior, showing that increasing k introduces only moderate computational overhead.

7 Conclusion

This work investigates the phenomena of OSM and OSQ in GNNs from a unified spectral-spatial perspective. We first develop a unified spectral-spatial framework for analyzing polynomial graph convolution, providing a principled understanding of how the polynomial order k jointly affects spectral filtering and spatial information propagation. Based on this framework, we reveal an intrinsic trade-off induced by k, where higher-order filters enhance spectral expressiveness and help alleviate OSM, while simultaneously expanding the receptive field and exacerbating information compression, thereby intensifying OSQ. Motivated by this insight, we propose the QS-GCN, which achieves an effective balance between these two phenomena. Extensive experiments validate both our theoretical analysis and the effectiveness of the proposed model. Future work will explore more principled and generalizable metrics for quantifying OSQ, as well as adaptive, data-dependent selection of the polynomial order k to further improve the balance between OSM and OSQ.

Acknowledgements

This work is supported by National Natural Science Foundation of China (No. 62576371, 62576198, and 62536006), and the Open Project Foundation of Key Laboratory of Computation Intelligence and Chinese Information Processing of Ministry of Education and Key Laboratory of Data Intelligence and Cognitive Computing of Shanxi Province.