Piecewise Constant Spectral Graph Neural Network

Vahan Martirosyan [email protected], Jhony H. Giraldo [email protected], Fragkiskos D. Malliaros [email protected] · 2025

Read Piecewise Constant Spectral Graph Neural Network by Vahan Martirosyan [email protected], Jhony H. Giraldo [email protected], Fragkiskos D. Malliaros [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-04808.txt.

Introduction

Vahan Martirosyan, Jhony Giraldo, and Fragkiskos Malliaros present a new graph learning model in a 2025 paper. Graph networks learn from linked data, and one family works with the graph's spectrum. Those models use small formulas that may miss much of the spectrum. Larger formulas cost more and can stop helping or even hurt results.

Their model, PieCoN, mixes flat filters with the usual formula filters. It splits the spectrum into parts and adjusts to each part. That gives the model more ways to learn from graph shape. Tests on nine data sets, with both like-linked and mixed-linked graphs, showed clear gains. The design aims to keep costs in check while reaching more of the spectrum.

Catalog record

CREATORVahan Martirosyan [email protected], Jhony H. Giraldo [email protected], Fragkiskos D. Malliaros [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE59 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-04808

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Piecewise Constant Spectral Graph Neural Network Vahan Martirosyan [email protected], Jhony H. Giraldo [email protected], Fragkiskos D. Malliaros [email protected] Abstract Graph Neural Networks (GNNs) have achieved significant success across various domains by leveraging graph structures in data. Existing spectral GNNs, which use low-degree polynomial filters to capture graph spectral properties, may not fully identify the graph’s spectral characteristics because of the polynomial’s small degree. However, increasing the polynomial degree is computationally expensive and, beyond certain thresholds, leads to performance plateaus or degradation. In this paper, we introduce the Pie cewise Co nstant Spectral Graph N eural Network (PieCoN) to address these challenges. PieCoN combines constant spectral filters with polynomial filters to provide a more flexible way to leverage the graph structure. By adaptively partitioning the spectrum into intervals, our approach increases the range of spectral properties that can be effectively learned. Experiments on nine benchmark datasets, including both homophilic and heterophilic graphs, demonstrate that PieCoN is particularly effective on heterophilic datasets, highlighting its potential for a wide range of applications. The implementation of PieCoN is available at https://github.com/vmart20/PieCoN . 1 Introduction Graph Neural Networks (GNNs) ( Wu et al. 2021 ; Zhou et al. 2020 ) have demonstrated remarkable performance across various application domains. They have been successfully applied in areas such as social network analysis ( Panagopoulos et al. 2023 ) , recommendation systems ( Wu et al. 2019 ; Ying et al. 2018 ) , drug discovery ( Jiang et al. 2021 ; Bongini et al. 2021 ) , and materials modeling ( Coley et al. 2019 ; Duval et al. 2023 ) , where data can naturally be represented as graphs. GNNs can be broadly classified into two types: spatial and spectral GNNs. Spatial GNNs ( Kipf & Welling 2017 ; Veličković et al. 2018 ; Chien et al. 2021 ) use a message passing approach to learn node representations by collecting information from neighboring nodes. This approach allows spatial GNNs to capture local structural information and adapt to varying neighborhood sizes. On the other hand, spectral GNNs ( Wang & Zhang 2022 ; Defferrard et al. 2016 ; He et al. 2021 ; Castro-Correa et al. 2024 ) use the graph’s spectral characteristics, such as the graph Laplacian’s eigenvalues and eigenvectors, to transform node features. By leveraging the spectral domain, these models can capture global structural patterns and apply graph convolution operations in the frequency domain. Many existing spectral GNNs use low-degree polynomial filters, which approximate the filtering functions by applying polynomials to the graph’s Laplacian matrix or other graph-shift operators ( Wang & Zhang 2022 ; Defferrard et al. 2016 ; He et al. 2021 ) . One disadvantage of these low-degree polynomial filters is that they are continuous and, because of the low degree, may not give enough weight to specific eigenvalues, as the change between closely spaced eigenvalues cannot vary significantly. This can be problematic, particularly in real-world graphs where certain eigenvalues like zero 1 1 1 Note that, for the Laplacian matrix, the multiplicity of eigenvalue zero corresponds to the number of connected components. This correspondence does not hold for the normalized adjacency matrix we employ here. have large multiplicities ( Lu et al. 2024 ; Lim et al. 2023 ) . In this paper, we propose the Pie cewise Co nstant Spectral Graph N eural Network (PieCoN) to overcome this limitation. Our approach combines constant spectral filters with polynomial filters to better capture the spectral properties of the graph. The constant filters are defined by setting the values in the diagonal eigenvalue matrix to ones within specific intervals and zeros elsewhere, effectively isolating different frequency bands. Figure 1: Comparison of JacobiConv and PieCoN trained filters on the Chameleon dataset. By partitioning the spectrum into intervals, PieCoN expands the range of spectral characteristics that can be learned, improving the model’s performance. Figure 1 compares the response of a JacobiConv filter ( Wang & Zhang 2022 ) versus the response of a PieCoN filter across the spectrum. The figure shows how polynomial filters produce a smooth response, while piecewise constant filters can sharply focus on selected intervals, capturing crucial spectral properties that polynomial filters miss. For example, PieCoN can create a sharp drop at eigenvalue 0, which is impossible to achieve with low-degree polynomial filters like JacobiConv. This sharp discontinuity is crucial because eigenvalue 0 often has high multiplicity in real-world graphs (as detailed in Table 1 ) and contains important structural information. Our theoretical analysis provides important insights about spectral GNNs by establishing error bounds for polynomial spectral filtering and proving that our model is invariant to eigenvector sign flips and basis changes. We validate our approach on standard benchmark datasets, showing improved performance, particularly when handling graphs with multiple zero eigenvalues. Our main contributions are as follows: • We introduce a novel spectral GNN model (PieCoN) that uses piecewise constant filters combined with polynomial filters to enhance learning from the spectral properties of graphs. • We propose a new method to isolate frequency bands in the spectral domain by partitioning the eigenvalue spectrum into intervals, allowing the model to focus on crucial spectral properties. • We demonstrate, through experiments, that PieCoN outperforms or shows competitive performance against spatial and spectral GNNs on real-world datasets. 2 Related Work GNNs have evolved significantly since the early work by Bruna et al. 2014 , who introduced the first modern spectral-based graph convolution network using the graph Fourier transform. Later, Kipf & Welling 2017 simplified this approach with the Graph Convolutional Network (GCN) model, which applies a first-order approximation of spectral filters to make GNNs more scalable. Other important advancements include Graph Attention Networks (GAT) ( Veličković et al. 2018 ) , which use attention mechanisms to weigh neighboring nodes differently, and GraphSAGE ( Hamilton et al. 2017 ) , which focuses on inductive learning by generating node embeddings through sampling and aggregation techniques. Message-passing neural networks (MPNNs) ( Gilmer et al. 2017 ) are a class of GNNs where nodes iteratively exchange and aggregate information with their neighbors. Besides GCN and GAT, several other message-passing approaches have emerged to address specific challenges. For instance, the Graph Isomorphism Networks (GIN) model ( Xu et al. 2019 ) is designed to be as powerful as the 1-WL test for distinguishing non-isomorphic graphs, thus improving expressiveness. Spectral GNNs leverage the eigenvalues and eigenvectors of the graph Laplacian to perform graph convolution in the spectral domain. ChebNet ( Defferrard et al. 2016 ) introduced the use of Chebyshev polynomials for spectral filtering, improving the scalability of spectral GNNs. JacobiConv ( Wang & Zhang 2022 ) further enhances this by employing orthogonal Jacobi polynomials to flexibly learn graph filters. Recent work by Maskey et al. 2023 introduces a novel fractional graph Laplacian approach defined in the singular value domain to address over-smoothing, providing theoretical guarantees for both directed and undirected graphs. For heterophilic graphs with label noise, R 2 LP ( Cheng et al. 2024 ) demonstrates that increasing graph homophily can help mitigate the impact of noisy labels. While previous spectral GNNs have leveraged polynomial filters to approximate spectral properties of graphs, they are limited by their lack of flexibility in handling critical eigenvalues because of the low degree of

Read the complete text