SpecSphere: Dual-Pass Spectral-Spatial Graph Neural Networks with Certified Robustness

• URL: http://arxiv.org/abs/2505.08320v2
• Date: Wed, 14 May 2025 17:07:37 GMT
• Title: SpecSphere: Dual-Pass Spectral-Spatial Graph Neural Networks with Certified Robustness
• Abstract summary: We introduce SpecSphere, the first dual-pass spectral-spatial GNN that certifies every prediction against both $ell_0$ edge flips and $ell_inftyversa feature perturbations.<n>Our model couples a Chebyshev-polynomial spectral branch with an attention-gated spatial branch and fuses their representations through a lightweight trained in a cooperative-adrial min-max game.
• Score: 1.7495213911983414
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce SpecSphere, the first dual-pass spectral-spatial GNN that certifies every prediction against both $\ell\_{0}$ edge flips and $\ell\_{\infty}$ feature perturbations, adapts to the full homophily-heterophily spectrum, and surpasses the expressive power of 1-Weisfeiler-Lehman while retaining linear-time complexity. Our model couples a Chebyshev-polynomial spectral branch with an attention-gated spatial branch and fuses their representations through a lightweight MLP trained in a cooperative-adversarial min-max game. We further establish (i) a uniform Chebyshev approximation theorem, (ii) minimax-optimal risk across the homophily-heterophily spectrum, (iii) closed-form robustness certificates, and (iv) universal approximation strictly beyond 1-WL. SpecSphere achieves state-of-the-art node-classification accuracy and delivers tighter certified robustness guarantees on real-world benchmarks. These results demonstrate that high expressivity, heterophily adaptation, and provable robustness can coexist within a single, scalable architecture.

Related papers

• Unsupervised Graph Representation Learning with Complementary View Alignment [9.33832512108175]
  Unsupervised graph representation learning aims to derive meaningful node embeddings without relying on labeled data.<n>We propose textscAlignGAE, a novel extension of textitMaskGAE that preserves the full frequency spectrum through complementary view alignment.<n>Our framework introduces a dual-encoder architecture that separately processes structural and attribute information, incorporates node positional encoding, and employs dual reconstruction tasks for both edges and node attributes.
  arXiv  Detail & Related papers  (2026-07-27T12:15:25Z)
• Structure-Feature Aligned Graph Learning via Alternating Constrained Optimization [7.881713230406407]
  We introduce a constrained two-view framework for node prediction that aligns structure-conditioned GNN embeddings with a structure-free feature prior learned by an anchor model.<n>We also propose a Channel-Split Adaptive Gated GNN (CSAG-GNN) that dynamically routes representations between global spectral smoothing and local spatial discrimination through a node-wise gating mechanism.
  arXiv  Detail & Related papers  (2026-07-13T13:58:52Z)
• SpecGradFilter: A Spectral Gradient Filtering Framework for Taming Federated Heterogeneity [57.84199526590779]
  Federated Learning (FL) is fundamentally challenged by statistical heterogeneity, where non-identically distributed (non-IID) data induces client drift that hampers global convergence.<n>In this work, we revisit client drift from a novel frequency-domain perspective and uncover a critical Spectral Bias of Drift.<n>Motivated by this, we propose SpecGradFilter, a unified Spectral Filtering Gradient Framework that tames heterogeneity by suppressing discordant low-frequency signals.
  arXiv  Detail & Related papers  (2026-07-05T09:23:35Z)
• Robust Graph Representation Learning via Adaptive Spectral Contrast [0.9558392439655014]
  High-frequency signals are indispensable for encoding heterophily but exhibit significantly higher variance under spectrally concentrated perturbations.<n>We propose ASPECT, a framework that resolves this dilemma through a reliability-aware spectral gating mechanism.<n>ASPECT achieves new state-of-the-art performance on 8 out of 9 benchmarks, effectively decoupling meaningful structural heterophily from incidental noise.
  arXiv  Detail & Related papers  (2026-04-02T10:38:00Z)
• Evolutionary Router Feature Generation for Zero-Shot Graph Anomaly Detection with Mixture-of-Experts [60.60414602796664]
  We propose a novel MoE framework with evolutionary router feature generation (EvoFG) for zero-shot GAD.<n>EvoFG consistently outperforms state-of-the-art baselines, achieving strong and stable zero-shot GAD performance.
  arXiv  Detail & Related papers  (2026-02-12T06:16:51Z)
• Spectral Gating Networks [65.9496901693099]
  We introduce Spectral Gating Networks (SGN) to introduce frequency-rich expressivity in feed-forward networks.<n>SGN augments a standard activation pathway with a compact spectral pathway and learnable gates that allow the model to start from a stable base behavior.<n>It consistently improves accuracy-efficiency trade-offs under comparable computational budgets.
  arXiv  Detail & Related papers  (2026-02-07T20:00:49Z)
• SEA: Spectral Edge Attacks on Graph Neural Networks [1.066048003460524]
  We propose a new family of adversarial attacks that leverage spectral robustness evaluation to guide perturbations.<n>We introduce two complementary attack variants: (i) a Spade-guided deletion attack that removes the most spectrally robust edges, and (ii) a Spade-guided addition attack that inserts edges between nodes that are maximally incompatible in the fragile spectral space.
  arXiv  Detail & Related papers  (2025-11-30T01:40:15Z)
• HW-GNN: Homophily-Aware Gaussian-Window Constrained Graph Spectral Network for Social Network Bot Detection [5.793458146146123]
  Social bots are increasingly polluting online platforms by spreading misinformation and engaging in coordinated manipulation.<n>Graph Neural Networks (GNNs) have become mainstream for social bot detection due to their ability to integrate structural and attribute features.<n>We propose HW-GNN, a novel homophily-aware graph spectral network with Gaussian window constraints.
  arXiv  Detail & Related papers  (2025-11-27T14:29:40Z)
• Spectral Neuro-Symbolic Reasoning II: Semantic Node Merging, Entailment Filtering, and Knowledge Graph Alignment [0.0]
  This report extends the Spectral Neuro-Symbolic Reasoning (Spectral NSR) framework by introducing three semantically grounded enhancements.<n>The novelty lies in performing semantic and symbolic refinement entirely upstream of the spectral inference stage.<n>The result is a more robust, interpretable, and scalable reasoning system suitable for deployment in open-domain and real-world settings.
  arXiv  Detail & Related papers  (2025-11-02T21:57:15Z)
• From Eigenmodes to Proofs: Integrating Graph Spectral Operators with Symbolic Interpretable Reasoning [0.0]
  We introduce Spectral NSR, a fully spectral neuro-symbolic reasoning framework.<n>It embeds logical rules as spectral templates and performs inference directly in the graph spectral domain.<n>We show that Spectral NSR achieves superior accuracy, faster inference, improved robustness to adversarial perturbations, and higher interpretability compared to leading baselines.
  arXiv  Detail & Related papers  (2025-09-07T01:12:20Z)
• Sheaf Graph Neural Networks via PAC-Bayes Spectral Optimization [3.2771631221674333]
  Over-smoothing in Graph Neural Networks (GNNs) causes collapse in distinct node features.<n>We introduce a novel scheme called SGPC (Sheaf GNNs with PAC-Bayes)<n>We show that SGPC outperforms state-of-the-art spectral and sheaf-based GNNs while providing certified confidence intervals on unseen nodes.
  arXiv  Detail & Related papers  (2025-08-01T06:39:28Z)
• SpecBPP: A Self-Supervised Learning Approach for Hyperspectral Representation and Soil Organic Carbon Estimation [9.292155894591877]
  We propose a novel self-supervised learning framework for hyperspectral imagery.<n>SpecBPP challenges a model to recover the correct order of shuffled spectral segments.<n>Our results demonstrate that spectral order prediction is a powerful pretext task for hyperspectral understanding.
  arXiv  Detail & Related papers  (2025-07-26T04:11:43Z)
• SpectrumFM: A Foundation Model for Intelligent Spectrum Management [99.08036558911242]
  Existing intelligent spectrum management methods, typically based on small-scale models, suffer from notable limitations in recognition accuracy, convergence speed, and generalization.<n>This paper proposes a novel spectrum foundation model, termed SpectrumFM, establishing a new paradigm for spectrum management.<n>Experiments demonstrate that SpectrumFM achieves superior performance in terms of accuracy, robustness, adaptability, few-shot learning efficiency, and convergence speed.
  arXiv  Detail & Related papers  (2025-05-02T04:06:39Z)
• CARL: Camera-Agnostic Representation Learning for Spectral Image Analysis [75.25966323298003]
  Spectral imaging offers promising applications across diverse domains, including medicine and urban scene understanding.<n> variability in channel dimensionality and captured wavelengths among spectral cameras impede the development of AI-driven methodologies.<n>We introduce $textbfCARL$, a model for $textbfC$amera-$textbfA$gnostic $textbfR$esupervised $textbfL$ across RGB, multispectral, and hyperspectral imaging modalities.
  arXiv  Detail & Related papers  (2025-04-27T13:06:40Z)
• Federated Structured Sparse PCA for Anomaly Detection in IoT Networks [1.4500146354034478]
  We propose a novel federated anomaly minimization approach in IoT networks.<n>The proposed model integrates row-wise sparsity governed by $ell_2, sparse$.<n>Experiments prove that incorporating structured sparsity enhances both model interpretability.
  arXiv  Detail & Related papers  (2025-03-31T11:50:21Z)
• DiffFormer: a Differential Spatial-Spectral Transformer for Hyperspectral Image Classification [3.271106943956333]
  Hyperspectral image classification (HSIC) has gained significant attention because of its potential in analyzing high-dimensional data with rich spectral and spatial information.<n>We propose the Differential Spatial-Spectral Transformer (DiffFormer) to address the inherent challenges of HSIC, such as spectral redundancy and spatial discontinuity.<n>Experiments on benchmark hyperspectral datasets demonstrate the superiority of DiffFormer in terms of classification accuracy, computational efficiency, and generalizability.
  arXiv  Detail & Related papers  (2024-12-23T07:21:41Z)
• Point-Calibrated Spectral Neural Operators [54.13671100638092]
  We introduce Point-Calibrated Spectral Transform, which learns operator mappings by approximating functions with the point-level adaptive spectral basis. Point-Calibrated Spectral Neural Operators learn operator mappings by approximating functions with the point-level adaptive spectral basis.
  arXiv  Detail & Related papers  (2024-10-15T08:19:39Z)
• Degree-Conscious Spiking Graph for Cross-Domain Adaptation [51.58506501415558]
  Spiking Graph Networks (SGNs) have demonstrated significant potential in graph classification.<n>We introduce a novel framework named Degree-Consicious Spiking Graph for Cross-Domain Adaptation (DeSGraDA)<n>DeSGraDA enhances generalization across domains with three key components.
  arXiv  Detail & Related papers  (2024-10-09T13:45:54Z)
• Spectral Graph Reasoning Network for Hyperspectral Image Classification [0.43512163406551996]
  Convolutional neural networks (CNNs) have achieved remarkable performance in hyperspectral image (HSI) classification. We propose a spectral graph reasoning network (SGR) learning framework comprising two crucial modules. Experiments on two HSI datasets demonstrate that the proposed architecture can significantly improve the classification accuracy.
  arXiv  Detail & Related papers  (2024-07-02T20:29:23Z)
• Parameter-efficient Fine-tuning in Hyperspherical Space for Open-vocabulary Semantic Segmentation [10.502680141980642]
  Open-vocabulary semantic segmentation seeks to label each pixel in an image with arbitrary text descriptions.<n> vision-language foundation models, especially CLIP, have emerged as powerful tools for acquiring open-vocabulary capabilities.<n>H-CLIP achieves new SOTA open-vocabulary semantic segmentation results while only requiring updating approximately 4% of the total parameters of CLIP.
  arXiv  Detail & Related papers  (2024-05-29T07:41:34Z)
• Spectral regularization for adversarially-robust representation learning [32.84188052937496]
  We propose a new spectral regularizer for representation learning that encourages black-box adversarial robustness in downstream classification tasks. We show that this method is more effective in boosting test accuracy and robustness than previously-proposed methods that regularize all layers of the network.
  arXiv  Detail & Related papers  (2024-05-27T14:01:42Z)
• Mixture of Weak & Strong Experts on Graphs [56.878757632521555]
  Mixture of weak and strong experts (Mowst) Mowst is easy to optimize and achieves strong expressive power. On 4 backbone GNN architectures, Mowst shows significant accuracy improvement on 6 standard node classification benchmarks.
  arXiv  Detail & Related papers  (2023-11-09T07:45:05Z)
• Graph Agent Network: Empowering Nodes with Inference Capabilities for Adversarial Resilience [50.460555688927826]
  We propose the Graph Agent Network (GAgN) to address the vulnerabilities of graph neural networks (GNNs)<n>GAgN is a graph-structured agent network in which each node is designed as an 1-hop-view agent.<n>Agents' limited view prevents malicious messages from propagating globally in GAgN, thereby resisting global-optimization-based secondary attacks.
  arXiv  Detail & Related papers  (2023-06-12T07:27:31Z)
• Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Models [0.0]
  unsupervised classification problem in random hypergraphs under the non-uniform Hypergraph the Block Model (HSBM)<n>In this paper, the information-theoretic limits on the clustering accuracy and the strong consistency threshold are established.
  arXiv  Detail & Related papers  (2023-06-12T03:38:25Z)
• Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
  We propose a spectral algorithm that achieves perfect clustering with high probability on a class of large, sparse networks. Our method is the first to offer a guarantee of consistent latent structure recovery using spectral clustering.
  arXiv  Detail & Related papers  (2022-05-17T01:41:06Z)
• Structural Extensions of Basis Pursuit: Guarantees on Adversarial Robustness [0.0]
  We prove that the stability of BP holds upon the following generalizations. We introduce classification based on the $ell$ norms of the groups and show numerically that it can be accurate and offers considerable speedups.
  arXiv  Detail & Related papers  (2022-05-05T09:12:07Z)
• The Sample Complexity of One-Hidden-Layer Neural Networks [57.6421258363243]
  We study a class of scalar-valued one-hidden-layer networks, and inputs bounded in Euclidean norm. We prove that controlling the spectral norm of the hidden layer weight matrix is insufficient to get uniform convergence guarantees. We analyze two important settings where a mere spectral norm control turns out to be sufficient.
  arXiv  Detail & Related papers  (2022-02-13T07:12:02Z)
• Hyperspectral Image Denoising Using Non-convex Local Low-rank and Sparse Separation with Spatial-Spectral Total Variation Regularization [49.55649406434796]
  We propose a novel non particular approach to robust principal component analysis for HSI denoising. We develop accurate approximations to both rank and sparse components. Experiments on both simulated and real HSIs demonstrate the effectiveness of the proposed method.
  arXiv  Detail & Related papers  (2022-01-08T11:48:46Z)
• Self-Ensembling GAN for Cross-Domain Semantic Segmentation [107.27377745720243]
  This paper proposes a self-ensembling generative adversarial network (SE-GAN) exploiting cross-domain data for semantic segmentation. In SE-GAN, a teacher network and a student network constitute a self-ensembling model for generating semantic segmentation maps, which together with a discriminator, forms a GAN. Despite its simplicity, we find SE-GAN can significantly boost the performance of adversarial training and enhance the stability of the model.
  arXiv  Detail & Related papers  (2021-12-15T09:50:25Z)
• Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent [95.94432031144716]
  We propose a unified non- optimization framework for the analysis of a learning network. We show that existing guarantees can be trained unified through gradient descent.
  arXiv  Detail & Related papers  (2021-06-25T17:45:00Z)
• Convolutional Spectral Kernel Learning [21.595130250234646]
  We build an interpretable convolutional spectral kernel network (textttCSKN) based on the inverse Fourier transform. We derive the generalization error bounds and introduce two regularizers to improve the performance. Experiments results on real-world datasets validate the effectiveness of the learning framework.
  arXiv  Detail & Related papers  (2020-02-28T14:35:54Z)
• Target-Embedding Autoencoders for Supervised Representation Learning [111.07204912245841]
  This paper analyzes a framework for improving generalization in a purely supervised setting, where the target space is high-dimensional. We motivate and formalize the general framework of target-embedding autoencoders (TEA) for supervised prediction, learning intermediate latent representations jointly optimized to be both predictable from features as well as predictive of targets.
  arXiv  Detail & Related papers  (2020-01-23T02:37:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.