Graph Edge Sparsification

Follow this topic Ask about this topic

Momentum

9 papers in the last four weeks, up 80% on the four weeks before. 0.1% of all new papers.

Jul 6Week of Sep 21

Latest papers 45

Sep 30, 2026cs.DC

Reinforcement Learning-Guided Graph Transformations for SpTRSV Optimization

Sparse triangular solve (SpTRSV) is a fundamental kernel in numerous scientific and engineering applications. However, the data dependencies inherent in sparse triangular matrices significantly limit the available parallelism and make efficient workload distribution challenging. Recent graph transformation techniques address these limitations by modifying the dependency graph of the input matrix to improve parallel execution. Existing graph transformation strategies, however, rely on manually designed heuristics, making their development and adaptation to different optimization objectives challenging. This work proposes a reinforcement learning-guided graph transformation framework for SpTRSV, in which graph transformation is formulated as a sequential decision-making problem and an RL agent learns matrix-dependent transformation policies. Experimental results on real-world sparse matrices demonstrate level reductions of up to 94% and reductions of up to 80% in the coefficient of variation of level costs, while modifying only 1.50% of the rows in the highest case. On average, the RL- guided graph transformation achieves a 23% reduction in the number of levels and a 29% reduction in the coefficient of variation of level costs while rewriting only 0.82% of the matrix rows. Although the heuristic strategies generally achieve more aggressive level reduction(between 31% and 46%), the RL-based approach achieves the largest average reduction in the coefficient of variation of level costs, demonstrating its ability to balance competing graph transformation objectives. The results further show that the learned policies can be transferred to previously unseen matrices through curriculum learning and fine-tuning, while zero-shot experiments provide insights into the limitations of generalizing graph transformation policies across different sparsity patterns.

Buse Yılmaz

Department of Computer Engineering, MEF University, Huzur, Maslak Ayazağ̆a Cd., İstanbul, Turkey.

Multiplex Graph Transformers Graph Edge Sparsification Offline Reinforcement Learning

Sep 30, 2026cs.LG

Graph Residual Conjugate Diffusion: SNR-Equalized Heat Flow for Graph Signals

Diffusion models generate data by reversing a forward corruption process that typically approaches a simple Gaussian prior. Recent work has extended this framework to signals supported on fixed graphs, e.g., road-network traffic and sensor-network measurements. Many graph signals have nonuniform spectral energy, whereas isotropic corruption adds the same conditional noise variance to every graph-frequency mode. Driving all modes to near-zero terminal signal-to-noise ratio (SNR) requires strong corruption, which increases the noise range that must be covered under a fixed sampling budget. We introduce Graph Residual Conjugate Diffusion (GRCD), which replaces the shared clock of graph heat diffusion with a mode-dependent clock that gives every graph-Fourier mode the same conditional SNR. GRCD fits a zero-mean graph-spectral Gaussian reference on the training split and stops at a finite terminal SNR at which the propagated reference still carries the fitted spectral variances. The Gaussian component has an exact modewise propagator in the probability-flow ODE, so sampling advances it analytically and integrates only the learned residual score numerically. We evaluate GRCD on five settings (METR-LA traffic, Molene weather, and three stochastic block models) against seven comparators under a matched protocol: Graph-Aware Diffusion (GAD), EDM (graph backbone), two adaptations of Whitened Score Diffusion (WSD), and three preconditioning controls. At four function evaluations (NFEs), GRCD lowers averaged maximum mean discrepancy (aMMD) by 22 to 36 times over the best comparator on all five settings, reaching 0.054 on METR-LA, where it clears an aMMD 0.1 target with 87% less sampling wall-clock time than the cheapest comparator that reaches it. Fitting the terminal reference reduces aMMD by 2.7 to 7.3 times at finite terminal SNR, while the factors shrink to 1.00 to 1.01 near zero.

Jinwei Li, Daniel Tenbrinck

Department of Data Science Friedrich-Alexander-Universität Erlangen-Nürnberg Erlangen, Germany

Residual Conditional Diffusion Model Graph Edge Sparsification Signal-To-Noise Ratio Heat Diffusion Adversarial Corruption

Sep 23, 2026cs.LG

Pheno-GS: Phenoscape-scale Geodesic Sinkhorn

High-throughput single-cell data is now collected across large patient cohorts. Understanding patient-level heterogeneity from cellular-level data motivates phenoscaping: embedding each single-cell distribution as a "datapoint," with distances given by optimal transport (OT). Computing geometry-aware OT at this scale, between all pairs of patient datasets, remains an open challenge, since existing methods either rely on Euclidean ground metrics that distort manifold structure or fail under sparse, unevenly sampled, or large-scale data. We present \textbf{Pheno-GS} (Phenoscape-scale Geodesic Sinkhorn), which computes accurate, scalable geodesic transport distances under noisy, unbalanced, large-scale settings via three components: (

1

) graph connectivity regularization for well-defined geodesics on sparse/disconnected manifolds; (

2

) an unbalanced OT formulation via KL marginal penalties; and (

3

) a batched matrix algorithm computing all pairwise distances in one heat diffusion (over

200 \times

faster than Geodesic Sinkhorn for

500

distributions). We validate Pheno-GS on synthetic benchmarks and a CyTOF perturbation dataset.

Alistair Wilkinson, Christopher J. Tape, Smita Krishnaswamy

Department of Oncology, University College London, London, UK. · Department of Computer Science, Yale University, New Haven, CT, USA.

Fused Sinkhorn-Localized Similarity Single-Cell Rna Graph Edge Sparsification

Sep 23, 2026cs.LG

Graph Learning with Spectral Connectivity Priors for Scarce Data

Learning a sparse graph from scarce data is practically important but challenging. Motivated by the desirable combination of local sparsity and strong global connectivity exhibited by expander-like graphs, we propose spectral connectivity-regularized graph learning (SCoGL), a framework that incorporates a family of Laplacian spectral priors to explicitly promote global connectivity. Specifically, SCoGL augments a combinatorial-Laplacian-constrained graphical lasso (GLASSO) objective over a target adjacency matrix

\mathbf{W}

with a general connectivity prior computed from Laplacian eigenvalues. We derive gradients for several representative connectivity priors and develop a projected gradient descent (PGD) algorithm with Armijo backtracking to efficiently optimize

\mathbf{W}

. Experiments show that the proposed SCoGL variants improve graph recovery and enhance downstream tasks such as graph signal denoising when signal observations are scarce.

Mingxiao Liu, Bahar Oveisgharan, Bingyan Zou +3

Tsinghua University, China · York University, Canada

Graph Edge Sparsification Graph Laplacians Sparsity Prior Knowledge Integration

Sep 21, 2026cs.LG

Dual-GNN Multilevel Coarsening for Maximum Independent Set

The maximum independent set (MIS) problem is a fundamental NP-hard combinatorial optimization problem with applications in scheduling, resource allocation, and network analysis. Exact solvers can provide high-quality solutions or optimality certificates, but their computational cost grows rapidly with graph size, while hand-crafted heuristics improve scalability at the expense of guarantees. Learning-based methods offer an alternative by exploiting structural patterns across graph instances, yet directly predicting independent sets can make global coordination difficult on large graphs. We instead use learning to guide multilevel graph coarsening while retaining combinatorial search for final decision making. Our Dual-GNN Multilevel Coarsening framework uses a Partition GNN to score candidate contractions and a Representative GNN to select top-k local independent-set states for each final cluster. Experiments on Erdős--Rényi graphs with up to 2,000 vertices demonstrate a favorable quality--runtime trade-off. On 500-vertex instances with certified optima, our method achieves an average independent-set size of 19.20, corresponding to 99.5% of the optimal value of 19.30, while reducing the mean wall-clock time from 643.57 seconds for exact solving to 3.41 seconds, yielding an approximately 189

\times

speedup. On larger graphs with 1,000 and 2,000 vertices, our method achieves the best mean solution quality among all evaluated methods. Moreover, although trained only on Erdős--Rényi graphs with edge probability

p=0.35

, the learned coarsening policy generalizes effectively across both unseen graph densities and structurally different graph families.

Tianfeng Chen, Xianyue Li

School of Mathematics and Statistics Lanzhou University

Salesman Problem Graph Edge Sparsification Combinatorial Optimization Maximum Independent Set Sparsity

Sep 16, 2026cs.LG

Provable Guarantees for Spectral Structured Prediction

Structured prediction is the simultaneous prediction of multiple labels, and is widely used in various fields, such as natural language processing and computer vision. In this paper, we study binary node label recovery on signed graphs with edge-flip noise, a model introduced by (Globerson et al., 2015), via a simple spectral method that decodes node labels from the signs of the principal eigenvector of the noisy signed adjacency matrix. We develop graph structure-agnostic theoretical guarantees for approximate inference of node labels as well as guarantees for maximum angle deviation with respect to the ground truth node labels. By leveraging tools from matrix concentration theory and eigenvector perturbation analysis, we derive new concentration inequalities that explicitly quantify the effect of the spectral gap of the adjacency matrix, number of nodes, degree distribution, and noise level. As a corollary, we relate our general results to the Cheeger constant and provide results for different classes of graphs. We perform several synthetic experiments to validate our theory. To the best of our knowledge, we are the first to provide theoretical guarantees for the spectral-based approach. As a byproduct of our analysis, we derive technical results that might be of independent interest and useful for other machine learning problems.

Violet Zheng, Jean Honorio

CIS, The University of Melbourne

Graph Edge Sparsification Provable Guarantees

Sep 11, 2026quant-ph

Learning structural balance of graphs from quantum spectral features

We develop a quantum approach to spectral feature extraction from the density of states (DOS) of a problem-dependent Hamiltonian, and apply it to machine learning on signed graphs. We propose to embed a signed graph as an Ising model instance with positive and negative interactions, and use the standardized moments of the Ising DOS as features for learning. We show that these moments count signed closed walks, are switching-invariant, and are size-free by construction. As a benchmark, we target learning the frustration index, an NP-hard measure of structural balance that can be labeled exactly at moderate size. At zero field, the models can be sampled classically, allowing the quantum extraction procedure to be certified against exact ground truth. We propose DOS-QPE, a phase estimation on a purified maximally mixed probe, which samples the spectral density with orders of magnitude fewer shots than Hadamard test-based trace sampling and feeds the resulting features directly into classically trained models. On

1.4\times10^5

labeled graphs the exact DOS determines the frustration index, and five moments recover it with a mean error of 0.4, well below one sign flip. Beyond zero field, the underlying trace-estimation problem is DQC1-complete, providing access to spectral features for which no efficient classical sampling method is known. Our work opens routes towards quantum applications in social network balance analysis, spin-glass studies, correlation clustering, and protein-interaction networks.

Stefano Scali, Oleksandr Kyriienko

Department of Physics and Astronomy, University of Exeter, Exeter EX4 4QL, UK · School of Mathematical and Physical Sciences, University of Sheffield, Sheffield S10 2TN, UK

Graph Edge Sparsification Qubit Spectral Hamiltonian Balance Spectral Features+1

Sep 11, 2026cs.LG

When does a spectral prior help graph learning? Connectivity-loss estimation under road-network disruptions

Rapid evaluation of many simultaneous road-link disruptions requires a practical compromise between exact spectral recomputation and local approximation. We estimate relative algebraic-connectivity loss after multi-edge deletion using graph neural networks (GNNs) that learn a bounded correction to a first-order Fiedler sensitivity. The study considers independent, spatially clustered, and edge-betweenness-targeted failures, with graph-disjoint synthetic splits and zero-shot transfer to 13 OpenStreetMap (OSM) areas in six countries. GCN, GraphSAGE, and edge-aware MPNN backbones are compared with analytical baselines. In expanded OSM tests, residual GCN improves spatial-failure MAE by 0.0391 (95% hierarchical interval 0.0151-0.0662), while residual GraphSAGE improves targeted-failure MAE by 0.0257 (0.0095-0.0446). Second-order perturbation improves first-order MAE by only 0.0028-0.0053. Correction slopes decrease under targeted transfer, indicating residual shrinkage around systematic prior error. Leave-one-country-out OSM-to-OSM transfer is mixed: residual GCN improves targeted-failure MAE by 0.0622 (0.0169-0.1153) but worsens the spatial point estimate. Sparse scaling extends to 20,000 nodes and separates one-time spectral setup from amortized screening cost. These results characterize the spectral residual as a useful but domain-sensitive inductive bias for structural connectivity screening. Code, cached networks, and reproducibility artifacts are archived at doi:10.5281/zenodo.22307723.

Van-Truong Le

Faculty of Information Technology, University of Science, Viet Nam National University Ho Chi Minh City, Viet Nam

Graph Edge Sparsification Mean Squared Error Prior Knowledge Integration

Sep 9, 2026cs.LG

Kernel-Complexity Edge Sanitization for Training-Free Defense against Structural Graph Attacks

Graph Neural Networks (GNNs) have achieved remarkable success across diverse applications, yet they remain highly vulnerable to adversarial attacks that maliciously perturb graph structure. Existing defenses often lack rigorous theoretical grounding, rely on attack-specific heuristics, or require costly retraining procedures such as adversarial training. To address these limitations, we propose Kernel-Complexity Edge Sanitization (KCES), a training-free and model-agnostic framework for defending against structural attacks. KCES is built upon Graph Kernel Complexity (GKC), a principled metric derived from the graph Gram matrix that appears in a generalization upper bound on the GNN test error. From this bound, we define an edge-specific KC score that quantifies each edge's structural influence via its induced change in GKC. KCES then identifies and prunes high-KC edges, which are empirically enriched with adversarial perturbations under structural attacks, to mitigate their harmful impact. Computationally efficient and scalable, KCES operates as a lightweight preprocessing step without retraining and can be seamlessly integrated with existing defenses. Extensive experiments demonstrate that KCES consistently outperforms representative robust baselines across diverse attack settings and scales effectively to large graphs. Supported by theoretical analysis and extensive empirical validation, KCES provides a principled and efficient framework for securing GNNs. Our code is available at https://github.com/karpning/KCScore.

Yaning Jia, Shenyang Deng, Yaoqing Yang +3

Department of Computer Science Dartmouth College Hanover, New Hampshire, USA

Graph Neural Networks Graph Edge Sparsification

Sep 8, 2026cs.CR

Concept drift mitigation through community and spectral graph analysis for the detectionof cyberattacks in network traffic

In network traffic, legitimate behaviours and attack techniques evolve jointly - the phenomenon known as 'concept drift' [1]. Every detector is thereby left obsolete between two updates, and always one step behind adversaries. In this work, we propose to move the point of intervention from the model, repaired after the drift, to the feature space, selected before learning. We therefore introduce t-robustness, a stability score defined for each feature independently of any detection model, comparable across an entire feature space. It combines the step-by-step distance between successive statistical states of a feature, and its cumulative divergence from its initial state, so that a slow monotonic drift cannot pass for stability. The candidates are drawn from abnormal network connectivity patterns left by scans, DoS and communications between endpoints, read through graph community metrics and spectral metrics. The evaluation is performed on the UGR16 dataset, across three learning scenarios and a control scenario, as well as without model update, and demonstrate that t-robust feature spaces sustain detection where the baselines collapse: retained expectancy at the last test interval reaches 0.6025, against 0.5230 for graph community features and 0.3831 for the base NetFlow features.

Julien Michel, Abdul Qadir Khan, Majed Jaber +1

Laboratoire de Recherche de l’EPITA, 14-16 Rue Voltaire, Le Kremlin-Bicêtre, 94270, France · ICube, UMR7357, Université de Strasbourg, Strasbourg, 67000, France

Threat Detection Generalist Graph Anomaly Detection Network Traffic Graph Edge Sparsification Lateral String Stability

Sep 3, 2026cs.LG

Geometry-Aware Graph Construction via Adaptive Spectral Bandwidth Control

Kernelized graph methods - spectral clustering, diffusion maps, and sparse kernel -regression graphs - that use Gaussian kernels depend on the choice of Gaussian bandwidth sigma, which governs the spectral character of the local kernel operator. When sigma is too small, the kernel overestimates local complexity and treats each sample as an independent direction; when sigma is too large, the kernel collapses multiple directions together, the condition number diverges, and all geometric discrimination is lost. We propose a choice of scale to make the spectral complexity of the kernel consistent with the intrinsic complexity of the underlying manifold. We propose a per-node bandwidth criterion that operationalizes this principle by jointly matching the kernel's effective rank to the local intrinsic dimension estimated via minimum spanning tree, anchoring the search in the manifold-consistent log-log scaling regime. We evaluate SSL embeddings from six encoders on CIFAR-100, showing that adaptive bandwidth consistently improves leave-one-out (LOO) classification and label propagation (LP) accuracy over fixed-bandwidth methods and competing adaptive methods.

Ecem Bozkurt, Antonio Ortega

Department of Electrical and Computer Engineering University of Southern California, Los Angeles, CA, USA

Graph Edge Sparsification Kernel Method Bandwidth Extension Frequency-Aware Regularization Construction

Aug 12, 2026eess.IV

Domain-Aware Lightweight Spectral-Grouped Convolutions for Hyperspectral Fish Freshness Classification

Hyperspectral imaging (HSI) offers nondestructive assessment of fish freshness by detecting biochemical alterations across spectral bands. However, conventional deep learning approaches do not fully address the particular characteristics of HSI data, such as spectral dominance over spatial textures, ordinal label structure, and a small number of training samples. We propose SGNet (Spectral-Grouped Network), a lightweight architecture that separates spectral and spatial feature extraction using grouped convolutions and a depthwise spatial pathway. A dual attention mechanism that couples channel-wise squeeze-and-excitation with spatial gating adaptively highlights informative features. SGNet achieves 97.8% classification accuracy and 0.64 days mean absolute error (MAE) with just 4.75M parameters when tested on our newly developed 16-day refrigerator-stored salmon fillet dataset. Ablation studies validate the contribution of each component, while comparisons demonstrate a five- to eighteen-fold parameter reduction relative to ResNet-50 and Vision Transformers. Our findings indicate that domain-aware design supports precise, real-time freshness prediction for industrial implementation.

Kazi Nabiul Alam, Pooneh Bagheri Zadeh, Akbar Sheikh-Akbari

School of Built Environment, Engineering, and Computing, Leeds Beckett University. Leeds LS6 3QS, United Kingdom.

Hyperspectral Image Convolutional Vision Transformer Graph Edge Sparsification

Aug 11, 2026cs.SI

Spectral graph clustering with inhomogeneous latent geometry

We study spectral clustering in the presence of a confounding latent geometry. The leading eigenvectors may then be dominated by the latent geometry rather than by the communities. Nevertheless, we show in a block latent-space model that communities can be recovered from eigenvectors deeper in the spectrum. We analyze the spectral properties of the adjacency matrix through a limiting integral operator and use its structure to develop DBSPEC, a density-based spectral clustering algorithm that requires only approximate localization of the informative eigenvalue and is robust to poor eigenvalue separation. Crucially, this approach handles general latent geometries, overcoming restrictions to homogeneous toroidal models in prior works. Our theoretical predictions for the location of the informative eigenvalue notably align with observations in real-world experiments.

Konstantin Avrachenkov, Lucas S. Sibemberg, Alexander Van Werde

Inria Sophia Antipolis, France · Federal University of Rio Grande do Sul, Brazil · University of Münster, Germany

Graph Edge Sparsification Spectral Decomposition Discriminative Congruence Transform

Aug 11, 2026stat.ML

Spectral Embeddings of Degree- $α$ Laplacians in Random Dot Product Graphs

Spectral clustering methods for network data are commonly based on a few matrix representations, such as the adjacency matrix and the symmetric Laplacian. We study a continuum of degree-normalized spectral embeddings that includes these commonly used choices as special cases. Under a random dot product graph model, we establish a row-wise central limit theorem for this family of embeddings. The result provides an explicit description of how degree normalization affects both population geometry and the local uncertainty of embedded nodes. We use the limiting distributions to compare different normalizations in two-community stochastic block models through a projected-Gaussian Bayes-error diagnostic. These comparisons show that no single normalization is uniformly preferred. Instead, the favored normalization depends on network density, community imbalance, and block-probability structure. Typically, stronger normalization is favored in lower-density or more imbalanced settings. These results provide a unified distributional understanding of when and why alternative normalizations may improve spectral clustering.

John Park, Ning Hao

University of Hong Kong · University of Arizona

Graph Edge Sparsification Graph Laplacians Network Science

Aug 7, 2026cs.LG

Edge Sparsification via Temporal Forman-Ricci Curvature for Dynamic Graph Learning

Temporal graph learning has become essential for analyzing real-world systems whose interactions continuously evolve over time, including financial transaction networks, communication systems, and online social platforms. However, learning from large-scale temporal graphs remains computationally challenging when networks are dense and rapidly changing. To address this limitation, we propose a network-curvature-inspired edge sparsification framework for dynamic graph learning. Our proposed method, TRicci, extends classical Forman-Ricci curvature to directed weighted temporal graphs by capturing structural support, temporal recency, and local interaction competition. Experiments on 9 transaction networks and 3 temporal graph benchmark datasets demonstrate that the proposed framework preserves predictive performance across multiple graph-level prediction tasks. The results show that TRicci sparsifies temporal graphs by approximately 80% while reducing end-to-end downstream training and inference time by an average of 55.94%, without substantial degradation in predictive performance. Our findings suggest that temporal curvature can serve as a principled basis for scalable temporal graph learning by preserving predictive temporal-structural information under substantial sparsification.

Poupak Azad, Cuneyt Gurcan Akcora, Kiarash Shamsi

University of Manitoba, Canada · University of Central Florida, United States

Temporal Graph Neural Networks Graph Edge Sparsification Local Curvature Edge

Aug 5, 2026physics.chem-ph

Physics-Based Molecular Fingerprints from Spectral Graph Theory Provide Efficient Geometry-Aware Measures of Chemical Similarity

Molecular representations are essential for the evaluation of molecular similarity and the development of structure-property relationships. Despite the known importance of 3D structure to determine chemical and physical properties, the most widely used molecular fingerprints encode only two-dimensional connectivity. Such representations fail to distinguish similar but distinct stereoisomers and conformers. Alternative 3D methods are typically defined pairwise, making their application to large chemical spaces prohibitive, while deep learning embeddings are expressive but uninterpretable and limited by their training data diversity. Here, we introduce novel physics-inspired molecular fingerprints based on principles from spectral graph theory. We represent molecules as a complete graph in 3D space, with edge weights encoding heuristic physical interactions. Eigenvalue decomposition of the resulting graph Laplacian matrix results in a computationally efficient fixed-length chemical fingerprint that encodes 3D structure while obeying necessary physical symmetries of permutation and E(3) invariance. Spectral fingerprints differentiate between unique molecular structures with identical 2D connectivity, overcoming a limitation of 2D descriptors, while maintaining the low computational cost needed for efficient screening of vast chemical spaces. We evaluate our fingerprints with community detection algorithms and observe strong performance against representative baselines across datasets from organic, inorganic, biological, reticular, and reaction chemistry. Nearest-neighbor property estimation and applicability domain analyses reveal the utility of our molecular representation in machine learning and cheminformatics. We anticipate that spectral fingerprints will serve as generalizable, interpretable, and efficient measures of chemical similarity that incorporate 3D information at minimal cost.

Jacob W. Toney, Ayleen Y. Farnood, Samir Darouich +1

Department of Chemical Engineering, Massachusetts Institute of Technology, Cambridge, MA 02139, USA · Center for Computational Science and Engineering, Massachusetts Institute of Technology, Cambridge, MA 02139, USA · Institute for Theoretical Chemistry, University of Stuttgart, 70569 Stuttgart, Germany +2

Molecular Representation Learning Chemical Structures Graph Edge Sparsification Similarity and Metrics

Jul 30, 2026cs.LG

Kohn-Sham Spectral Embedding on Sparse Graphs at the Nishimori Temperature for Image Classification

We propose Kohn-Sham Spectral Embedding (KSSE), an energy-based model replacing the top-layer classifier of convolutional networks with a sparse-graph spectral embedding at the Nishimori temperature of an associated Random-Bond Ising Model the spectral detectability threshold where class structure becomes marginally distinguishable from disorder. Mapping pre-trained features onto quasi-cyclic low-density parity-check graphs, we construct a regularized Laplacian (Bethe-Hessian) as an effective Kohn-Sham Hamiltonian, yielding D independent spectral problems-one per feature channel-solvable in

O(N log N + k_{mode}^{2} N)

time by FFT on circulant blocks (Pontryagin self-duality), with low-mode Rayleigh-Ritz refinement (

k_{mode}=5

). Physically, this is a k.p effective-mass reduction on a one-dimensional ring crystal: the circulant support is the perfect crystal, the data weights a slowly varying impurity potential, and the Nishimori crossing a Fermi level at the band edge. Star-domain surgery optimizes the graph: instead of eliminating all frustrated cycles impossible without destroying the codewords-edge shifts create certified convexity around codewords with bounded residual frustration, with multi-scale fractal certification (basins

D_{2}<1

vs rough landscapes

D_{2}>3

). The theory includes a generalized Ihara-Bass identity with a sharp spectral threshold, a non-backtracking growth trichotomy with frustration as a gauge-invariant

Z_{2}

flux, a trapping-set spectral test, exact channel separability with a cup-product obstruction, plus loop-series, convexity, surgery, and quasi-stationarity bounds. On ImageNet-1000 with frozen EfficientNet-B4 features (D=1792) under a transductive protocol, KSSE achieves 88.93% Top-1 accuracy with ~21.24M parameters-beating Swin-L (197M, 86.4-87.3%) and matching the lower end of ViT-H/14 (632M, 88.0-89.5%) with 10x and 30x fewer parameters.

V. S. Usatyuk, D. A. Sapozhnikov, S. I. Egorov

Department of Computer Engineering, South-West State University (SWSU), Kursk, 305040 Russia · T8 LLC, R&D Department, Information Theory Group, Moscow, 107076 Russia

Graph Edge Sparsification Image Classification Convolutional Neural Networks Spatial Photonic Ising Machines

Jul 25, 2026cs.LG

Does Graph Compression Preserve Signal Propagation?

Graph compression reduces the computational cost of graph learning, but its effect on signal propagation remains largely underexplored. Existing work evaluates compression through downstream task performance or structural preservation, neither of which directly captures how propagation dynamics change after compression. We study two fundamental compression paradigms, coarsening and sparsification, and ask whether they preserve the propagation behavior of the original graph. Across five datasets, varying compression rates, and propagation depths, we measure signal behavior through three complementary metrics. Our results reveal a consistent tension between the two compression families. Sparsification retains higher signal diversity and mitigates oversmoothing, but its propagation trajectory progressively diverges from that of the original graph. Coarsening more faithfully preserves propagation behavior, but at the cost of stronger smoothing and rank collapse. These findings demonstrate that two propagation-centric objectives, preserving signal diversity and preserving propagation fidelity, are distinct and empirically at odds under graph compression, highlighting the need for evaluation protocols that jointly consider both dimensions. The code and results are available at: https://github.com/KawshikBanerjee/Compression-Propagation-Duality

Kawshik Banerjee, Khaled Mohammed Saifuddin

School of Computing, Southern Illinois University, Carbondale, IL, USA

Graph Edge Sparsification Data Compression Methods Propagation Sparsity Coarse

Jul 9, 2026cs.LG

Group Invariant Spectral Embedding

Spectral embedding methods are widely used for dimensionality reduction and clustering of high-dimensional datasets with intrinsic low-dimensional structures. Although many datasets of practical interest exhibit invariance under symmetries such as rotations, standard spectral embedding methods do not account for this, treating symmetry-related data points as unrelated. Our approach to this problem is to incorporate the symmetries directly into the affinity kernels used for spectral embedding. We analyze the case of a Riemannian data manifold

M

with symmetries given by a compact Lie group~

G

and prove that, under suitable conditions, graph Laplacians constructed from three types of invariant kernels converge pointwise to explicit second-order differential operators on the quotient space

M/G

. Our analysis implies improved convergence rates, as the effective dimension drops according to the dimension of the group. We validate our approach on datasets with

\mathrm{SO}(2)

or

\mathrm{SO}(3)

symmetry, and show that

G

-invariant spectral embedding recovers the intrinsic geometry of the data, in contrast to standard spectral embedding, which fails to do so even in the limit of infinite data.

Yeari Vigder, Paulina Hoyos, David Thong +3

Department of Statistics and Operations Research, Tel Aviv University, Tel Aviv, Israel · Department of Mathematics, University of Texas at Austin, Austin, TX, USA · Department of Mathematics, KTH Royal Institute of Technology, Stockholm, Sweden

Graph Edge Sparsification Symmetry Graph Laplacians Low-Dimensional Structure Kernel Method

Jul 8, 2026stat.ML

DiPhon: Diffusion on Graphons for Scalable Graph Generation

Diffusion models represent a leading paradigm for graph generation, with notable impact in domains such as molecular design. Yet, scaling these models to large graphs remains an open problem. We approach this question in the dense-graph setting through the lens of graphons, the size-agnostic limit objects of dense graph sequences, to study how structural graph statistics behave across node-size scales. This perspective leads to DiPhon, a diffusion framework for size-scalable graph generation. Specifically, we formulate a continuous diffusion process on the graphon space via a Jacobi stochastic differential equation (SDE), and propose DiPhon, a discretized graph-level process that mimics these dynamics on finite graphs. We further derive the corresponding reverse-time process, which requires access to the marginal score. For the Jacobi process, this score interestingly admits a tractable form, which we estimate from data via graph denoising and plug into the reverse process to generate graph samples. We prove that DiPhon matches exactly the first moment of the marginal distributions induced by the continuous graphon process, and approximates the second moment up to a closed-form discrepancy. Thus, DiPhon inherits key size-agnostic statistical properties of the graphon dynamics, providing a principled route toward scalable graph generation. Empirically, we demonstrate this scalability by training on small graphs and generating progressively larger graphs at inference time, without retraining, while preserving their core topological properties.

Sergio Rozada, Yiming Qin, Manuel Madeira +2

King Juan Carlos University · EPFL, Lausanne, Switzerland · University of Pennsylvania

Physics-Guided Diffusion Diffusion Models Graph Edge Sparsification Data Generation

Jul 8, 2026cs.LG

Eigenbasis-Independent Learnable Spectral Positional Encodings for Directed Graphs via Hermitian Block Krylov Subspaces

Spectral positional encodings (PEs) for \emph{directed} graphs face two obstacles: magnetic Laplacians require an

O(n^3)

Hermitian eigendecomposition per potential, and their complex eigenvectors are defined only up to unitary gauge, which prior work handles with basis-invariant architectures. We propose learnable spectral PEs of the form

h_θ(A_q)\,R

, where

A_q

is a normalized magnetic operator,

h_θ

a learnable scalar spectral response, and

R

a block of random probes. Because the PE is a \emph{matrix function} of the operator, it is gauge-invariant by construction. We compute it in a Hermitian block Krylov subspace from sparse matrix--vector products only, prove that

k = O(\log(1/\varepsilon))

block steps suffice uniformly over heat--resolvent response families, and give a covering-number argument for why low-dimensional structured families generalize where free per-eigenvalue weights overfit. On a directed SBM whose symmetrization is uninformative by construction, direction-blind PEs stay at chance while magnetic Krylov PEs converge to the exact-eigendecomposition oracle as the depth grows. The same probes yield gauge-invariant pairwise features with

1/\sqrt{s}

Monte-Carlo error, and the undirected

q{=}0

case improves heterophilous benchmarks over no-PE and polynomial baselines.

Jiaqing Xie, Yuxin Wang

Fudan University

Graph Edge Sparsification Graph Laplacians Spectral Decomposition Positional Encoding Solver Iterations Symmetry

Jun 25, 2026cs.LG

A Generalization Theory for JEPA-Based World Models

Joint Embedding Predictive Architectures (JEPAs) have recently emerged as a promising paradigm for world modeling by learning predictive dynamics in a latent space rather than generating future observations at the input level. Despite their empirical success, the theoretical understanding of JEPA-based world models remains limited. In this paper, we develop the first generalization theory for JEPA-based world models. We formulate JEPA pretraining as a conditional spectral graph learning problem and show that the JEPA objective is equivalent to a low-rank factorization of an action-conditioned co-occurrence matrix. Building on this characterization, we establish a connection between JEPA pretraining error and downstream planning regret, leading to a finite-sample generalization bound for JEPA-based world models. Our analysis reveals an inherent trade-off between approximation and sample errors with respect to the latent dimension, providing theoretical insights into the advantages and limitations of latent predictive models compared with input-level predictive approaches.

Jingyi Cui, Qi Zhang, Hongwei Wen +1

State Key Lab of General AI, School of Intelligence Science and Technology, Peking University · University of Sydney

Joint-Embedding Predictive Architectures World Models Token Co-Occurrence Graphs Graph Edge Sparsification

Jun 23, 2026cs.LG

A Framework for Directed Hypergraph Signal Processing via tensor t-SVD

We introduce Directed Hypergraph Signal Processing (DHGSP), a unified framework that extends graph signal processing to accommodate both higher-order (polyadic) and asymmetric (directional) relationships simultaneously. Using the tensor singular value decomposition (t-SVD) within the t-product algebra, we define a novel adjacency tensor for directed hypergraphs, a topologically faithful shift operator, and a lossless Directed Hypergraph Fourier Transform (t-DHGFT). Experiments on real traffic networks demonstrate that DHGSP outperforms matrix-based (graph and digraph) and undirected tensor-based (hypergraph) baselines in denoising tasks.

Carlos Mundo-Levano, Nicolás Bello, Daniel L. Lau +1

Department of Electrical and Computer Engineering, University of Delaware, Newark, DE 19716, USA · Institute for Financial Services Analytics, University of Delaware, Newark, DE 19716, USA · Department of Electrical and Computer Engineering, University of Kentucky, Lexington, KY 40506, USA

Hypergraphs Graph Edge Sparsification Graph Signal Processing Singular Value Decomposition Fourier

Jun 23, 2026cs.AI

GES-TSP: Graph Edge Sparsification for TSP

Solving large-scale instances of the Traveling Salesman Problem (TSP) exactly is computationally expensive. Researchers often employ graph sparsification methods to improve computational efficiency. Traditional sparsification methods typically rely on fixed heuristics and fail to fully exploit instance-specific structural information. In this paper, we propose Graph Edge Sparsification (GES), a learning-based sparsification approach for Euclidean TSP. By incorporating geometric structural information and combinatorial optimization technology, our proposed method adaptively generates a sparsification graph for different instances, significantly reducing the graph size and accelerating the solving process. Experimental results demonstrate that our sparsification method can prune up to 95% of edges on the MATILDA dataset, while keeping the solution gap within 1% of the optimal value. Moreover, our approach exhibits strong generalization capability on the TSPLIB benchmark.In some large-scale instances, the pruning rate exceeds 99%, while the optimality gap remains below 1%.

Tianfeng Chen, Xianyue Li

School of Mathematics and Statistics Lanzhou Universtiy

Salesman Problem Graph Edge Sparsification Combinatorial Optimization Edge

Jun 19, 2026cs.LG

Dual-Attention Convolution Experts for Sparse Tensor Completion

Tensor factorization (TF) has been widely adopted for high-dimensional sparse data completion tasks. Despite significant progress, neural TF methods often struggle to capture complex cross-mode interactions and remain vulnerable to (extreme) data sparsity. To address these challenges, we propose a novel neural tensor factorization approach, termed Dual-Attention Convolution Expert Networks with Group-Level Contrastive Learning (DCGC). For the first problem, DCGC generates diverse non-linear alignment patterns of latent factors via a multi-channel convolution network, and leverages the gated dual-attention mechanism to drive the model to focus on more important output channels (i.e., convolution experts) and the aligned features. Furthermore, DCGC introduces a group-level contrastive learning strategy that aggregates positive samples with identical feedback levels while separating negative samples across different levels. This strategy injects high-quality self-supervised signals to mitigate data sparsity. Extensive experiments conducted on five datasets demonstrate that our DCGC outperforms the state-of-the-art methods in sparse tensor completion for traffic and recommendation applications. Code to reproduce the experimental results in the paper is available at https://github.com/ku1z/DCGC.

Yanlei Liu, Zhenyu Liao

School of Electronic Information and Communications (EIC), Huazhong University of Science and Technology (HUST), Wuhan, China

Tensor Completion Graph Edge Sparsification Convolutional Contrastive Learning

Jun 8, 2026cs.LG

Improved Convergence Analysis of Topology Dependence in Decentralized SGD

Decentralized SGD is a fundamental algorithm in decentralized learning, although the influence of an underlying network topology on its convergence behavior is not yet fully understood. Existing convergence analyses have shown that topologies with a small spectral gap significantly deteriorate the convergence rate of Decentralized SGD in both homogeneous and heterogeneous cases. However, many prior papers have reported that indeed the choice of the topology has a significant experimental impact in the heterogeneous case, but has little experimental impact on training behavior in the homogeneous case. In this paper, we present a tighter convergence analysis of Decentralized SGD, offering a more precise understanding of how topologies affect the convergence rate than the prior analysis. Specifically, unlike existing convergence analyses that used only the spectral gap as a property of the topology, our novel analysis shows that all eigenvalues of the mixing matrix affect the convergence rate. Throughout the experiments, we carefully evaluated the convergence behavior of Decentralized SGD and demonstrated that our novel convergence analysis can more accurately describe the effect of topology on the convergence rate.

Yuki Takezawa, Anastasia Koloskova, Sebastian U. Stich

Toyota Motor Corporation · University of Zurich · CISPA Helmholtz Center for Information Security

Decentralized Learning Network Topology Convergence Graph Edge Sparsification Stochastic Gradient Descent Topology

Jun 7, 2026cs.CV

Learnable Token Sparsification for Efficient Gigapixel Whole Slide Image Reasoning

The processing of gigapixel whole slide images within vision language models faces a major difficulty due to an excessive number of visual tokens. Existing solutions typically rely on spatial downsampling or heuristic pruning strategies that operate without training, and these methods often discard subtle but clinically meaningful patterns because pathological evidence is scattered irregularly across the tissue. To overcome this limitation, we reformulate token reduction in whole slide images as a trainable sparsification problem, allowing the model to learn an optimal selection strategy instead of following fixed heuristics. We propose a decoupled routing architecture. To enable gradient propagation through the nondifferentiable pruning operation during training, we introduce a component called SparseLearn. This component uses a variance-preserving noise gate that regulates the information flow of each patch via a differentiable Soft Top-K operator, together with a diagonal attention denoiser that recovers perturbed representations without leaking spatial information. At inference time, the SparseLearn module is entirely discarded, and the trained scorer applies a deterministic Hard Top-K operator to keep only the highest scoring 32 tokens, incurring no extra computation. By compressing the visual sequence down to a sparse set of just 32 tokens, which represents as little as 0.78% of the original length, our framework achieves 73.32% overall accuracy on SlideBench (TCGA), consistently surpassing sampling-based baselines and general-purpose vision language models. It also demonstrates strong zero shot generalization on SlideBench (BCNB) and WSI VQA*. By resolving the visual context bottleneck and preventing the dilution of sparse diagnostic evidence, this work provides a highly efficient paradigm for end to end gigapixel whole slide image reasoning.

Jingzhi Chen, Landi He, Zhuo Chen +2

Shenzhen University of Advanced Technology

Whole-Slide Images Graph Edge Sparsification

May 22, 2026cs.LG

Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them

Graphs with a simple spectrum admit cubic-time isomorphism testing, yet we prove that for every natural number

k

, the

k

-Weisfeiler-Leman (

k

-WL) test cannot distinguish all non-isomorphic graphs with a simple spectrum. As the WL hierarchy upper-bounds the distinguishing power of widely-used Graph Neural Networks (GNNs), this incompleteness applies to all such GNNs, ruling out completeness for every

k

-WL-aligned GNN family. To close this gap, we introduce PRiSM (Partition, Refine, Solve, Match), the first provably complete canonicalization of simple-spectrum eigendecompositions. PRiSM obtains the completeness guarantee that prior canonicalizations provably lack, and resolves the open problem of achieving complete expressivity on simple-spectrum graphs. When composed with DeepSets or a Transformer, PRiSM achieves universal approximation on simple-spectrum graphs, justifying the use of canonicalized Laplacian positional encodings. Empirically, PRiSM performs comparably to or outperforms existing spectral canonicalizations on graph regression, classification, and expressivity

Snir Hordan, Nadav Dym, Tim Seppelt

Faculty of Mathematics Technion - Israel Institute of Technology · IT University of Copenhagen

Graph Edge Sparsification Graph Neural Networks

May 21, 2026cs.LG

Minimum Description Length based Granular-Ball Tree Regularization for Spectral Clustering

Spectral clustering largely depends on the affinity graph, yet constructing a graph that preserves reliable local connectivity while adapting to heterogeneous data structures remains challenging. Existing granular-ball-based spectral clustering methods usually reduce graph complexity by using coarse-grained representatives. However, the learned local regions are often treated as graph nodes or anchors, and their structural information is not sufficiently used to regularize the original sample-level graph. To address this issue, this paper proposes a Minimum Description Length based Granular-Ball Tree-Regularized Spectral Clustering method, termed MDL-GBTRSC. The proposed method constructs a granular-ball tree through local MDL model selection, with reciprocal neighborhood continuity used to discourage splits that break reliable local connections. The stable leaf balls obtained from the tree provide coding-scale information for regularizing the sample-level affinity graph. In addition, a shared-neighbor bridge code is introduced to adjust weak local bridge relations without requiring an additional user-specified threshold. In this way, MDL-GBTRSC connects interpretable local representation learning with affinity graph construction in a unified spectral clustering framework. Experiments on real and synthetic datasets show that MDL-GBTRSC achieves the best average ARI and NMI under the adopted fixed-configuration protocol compared with classical spectral clustering baselines and representative granular-ball, micro-cluster, and anchor-based methods.

Zeqiang Xian, Caihui Liu, Yong Zhang +1

Department of Mathematics and Computer Science, Gannan Normal University, Ganzhou 341000, Jiangxi, China · Key Laboratory of Data Science and Artificial Intelligence of Jiangxi Education Institutes, Gannan Normal University, Ganzhou 341000, Jiangxi, China

Granular-Ball Computing Clustering Graph Edge Sparsification Model Selection Trees Less Data+1

May 21, 2026stat.ML

The ASE-LSE Disagreement Landscape: An End-to-End Characterisation of Extremes and Structural Drivers

Two of the most widely used methods for analysing graph data, Adjacency Spectral Embedding and Laplacian Spectral Embedding, often produce different results when applied to the same graph. Yet the structural reasons behind this disagreement remain incompletely understood. This paper provides an end-to-end account of ASE-LSE latent subspace disagreement. We first prove that the two methods produce identical latent subspaces for every embedding dimension whenever the Laplacian is a scalar multiple of the adjacency matrix, and show that this scalar relationship holds if and only if the graph is either regular or bipartite biregular. This anchor result identifies a sufficient condition for perfect agreement that pins down the floor of the disagreement spectrum and supplies the baseline for the perturbation analysis. We then prove that no maximal-disagreement graph or family of graphs exists: the disagreement is always strictly below its theoretical ceiling, and we exhibit a witness family demonstrating that no finite maximum is attainable, so the disagreement landscape has no maximiser. With both endpoints established, we derive a Regularity Departure Bound whose two terms isolate degree heterogeneity and eigengap as the primary structural factors influencing disagreement in the middle regime. Empirical validation across thousands of simulated graphs confirms the mechanisms predicted by the bound: heterogeneity pushes disagreement up, eigengap suppresses it, and their joint ratio emerges as a unified predictor of ASE-LSE disagreement, suggesting when the two embeddings can be treated as interchangeable and when they cannot.

Minh Triet Pham, Ian Gallagher

School of Mathematics and Statistics The University of Melbourne, Australia

Graph Edge Sparsification Heterogeneity Disagreement Subspace Extremes Suppression

May 18, 2026cs.SI

Neural Acceleration for Graph Partitioning

Graph Partitioning is a critical problem in numerous scientific and engineering domains including social network analysis, VLSI design, and many more. Spectral methods are known to produce quality partitions while minimizing edge cuts for a wide range of problems. However, the computational cost associated with the calculation of the Fiedler vector, an eigenvector associated with the second smallest eigenvalue of the graph Laplacian, remains a significant bottleneck due to memory issues and computational costs. In this paper, we present an accelerated approach to spectral bisection partitioning by replacing the traditional eigenvalue calculation with a simple artificial neural network model to approximate the Fiedler vector. We demonstrate that our approach achieves partitioning quality comparable to spectral bisection while significantly reducing the computational overhead, making it more scalable and efficient for large-scale problems

Joshua Dennis Booth, Vishvam Patel

Department of Computer Science University of Alabama in Huntsville Huntsville AL, USA

Graph Edge Sparsification Partitioning Graph Laplacians Computational Cost Acceleration Maximization

May 18, 2026eess.SP

Topological Signal Processing: An Application-Oriented Tutorial

Many modern datasets are large and carry complex structural relationships. Graph-based methods have traditionally been used to represent networked data, modeling individual elements as nodes and pairwise interactions as edges. Furthermore, Graph Signal Processing (GSP) has been developed to analyze signals on graph nodes, such as temperature measurements (node signals) across different regions of a country represented as a graph. Topological Signal Processing (TSP) is an emerging field that generalizes GSP, enabling the analysis of signals defined not only on nodes but also on edges, triangles, and higher-dimensional network elements, modeled as simplicial complexes and related topological structures. This makes TSP naturally well-suited for studying higher-order interactions in complex systems by extending classical signal processing concepts, such as filtering and Fourier transforms, to the topological level. Despite its versatility, TSP remains challenging for many practitioners. Therefore, we present an accessible overview of TSP foundations while drawing connections with application-oriented settings. We focus on processing techniques based on the combinatorial Hodge Laplacian, which generalizes the graph Laplacian to simplicial complexes. In particular, we review key TSP concepts, relate them to real-world examples, and discuss how higher-order structures and signals can be derived from datasets. For instance, we introduce an edge-level signal capturing lagged interactions between nodal signals, and demonstrate its use in a case study on TSP-based analysis of brain imaging data, revealing nontrivial interactions between sets of brain regions. Overall, we aim to promote a broader adoption of TSP by bridging methodological developments with applications, fostering its use among a wide community of theoretical and applied researchers.

Flavia Petruso, Maria Giulia Preti, Dimitri Van De Ville

Graph Edge Sparsification Graph Signal Processing Graph Representations

May 17, 2026cs.LG

Self-Supervised Learning for Sparse Matrix Reordering

Rearranging the rows or columns of a sparse matrix using an appropriate ordering can significantly reduce fill-ins, i.e., new nonzeros introduced during matrix factorization, decreasing memory usage and runtime. However, finding an ordering that minimizes fill-ins is NP-complete. Existing approaches, including graph-theoretic and deep learning methods, rely on surrogate objectives without theoretical guarantees. The Fill-Path Theorem reveals a direct and intrinsic relationship between fill-in generation and the sparse structure of the matrix as path triplet inequalities. Here we first employ a multigrid graph network to capture structural information for each vertex. We then derive a triplet sampling strategy based on inequalities. Finally, we introduce an end-max chain loss function to reduce the number of triplets whose predicted scores satisfy these inequalities. Experimental evaluations on the publicly available SuiteSparse matrix collection demonstrate the superiority of the proposed method in terms of both fill-in reduction and speedup in LU factorization time.

Ziwei Li, Tao Yuan, Fangfang Liu +3

Institute of Software, Chinese Academy of Sciences, Beijing, China

Sparsity Graph Edge Sparsification Loss Function Self-Supervised Learning

May 17, 2026cs.LG

Bridging the Gap between Sparse Matrix Reordering and Factorization: A Deep Learning Framework for Fill-in Reduction

Sparse matrix reordering can significantly reduce the fill-in during matrix factorization, thereby decreasing the computational and storage requirements in sparse matrix computations. Finding a minimal fill-in ordering is known to be an NP-hard problem. Moreover, there is a paradox: matrix reordering is applied before matrix factorization, but fill-ins that matrix reordering methods aim at are generated from matrix factorization. To bridge the gap between reordering and factorization, we propose a deep learning framework to minimize a fill-in surrogate function based on spectral embedding. First, we employ a multi-grid-like GNN architecture to learn to approximate the smallest eigenvectors of its graph Laplacian matrix, i.e. spectral embedding, and capture the global structural information of the matrix. Then, another multi-grid-like GNN architecture is used to minimize the potential space where fill-in can occur based on the rank distribution. Experimental results indicate that our approach achieves competitive performance compared with traditional graph-theoretic algorithms and deep learning methods.

Ziwei Li, Tao Yuan, Shuzi Niu +1

Institute of Software, Chinese Academy of Sciences, Beijing, China · University of Chinese Academy of Sciences, Beijing, China

Graph Edge Sparsification Factor Graph Neural Networks Deep Learning Framework Deep Learning

May 14, 2026cs.LG

Spectral structural distortion reveals redundant neurons in neural networks

Overparameterized neural networks often contain many removable neurons, yet what makes a neuron redundant remains poorly understood. Existing pruning criteria commonly rely on local quantities such as weight magnitude, activation strength, or gradient sensitivity, but these measures provide limited insight into the structural role of a neuron in the transformation performed by a layer. Here we show that neuronal redundancy can be characterized by weak participation in the spectral structural distortion induced by layer-wise representation transformations. For each hidden layer of a trained network, we record pre-activation and post-activation hidden states, model neurons as graph nodes, and construct input-side and output-side graphs that describe neuron-level relational structure before and after the layer transformation. We then define a spectral structural importance score that measures the contribution of each neuron to the dominant graph-spectral distortion between these two relational structures. Low-participation neurons are treated as structurally redundant and removed through an iterative pruning process in which scores are recomputed after each structural change. No parameter updates are performed during intermediate pruning rounds; after the target parameter reduction is reached, a single recovery fine-tuning stage is applied to the compact model. Direct ablation analysis and experiments across conventional neural networks, encoder-only Transformers, and decoder-only language models show that this graph-spectral criterion identifies removable neurons and Transformer units while preserving task performance after compression. These results suggest that neural redundancy is not merely a consequence of small weights or weak activations, but can be understood through weak participation in the spectral distortion of layer-wise relational structure.

Yongyu Wang

Neurons Unstructured Pruning Neural Network Graph Edge Sparsification

May 11, 2026cs.LG

Rank Is Not Capacity: Spectral Occupancy for Latent Graph Models

Graph representation learning has become a standard approach for analyzing networked data, with latent embeddings widely used for link prediction, community detection, and related tasks. Yet a basic design choice, the latent dimension, is still treated as a brittle hyperparameter, fixed before training and tuned by held-out performance. Learned factors are also identifiable only up to rotation and rescaling, so the nominal rank rarely coincides with the quantity that governs model behavior. We propose Spectral Prefix Extraction and Capacity-Targeted Representation Analysis (Spectra), which replaces rank as the unit of analysis with the spectrum of a learned positive semidefinite kernel, trace-normalized so that spectra are comparable across fits. The normalized eigenvalues form a distribution on the simplex, and their Shannon effective rank acts both as a summary of learned capacity and as a controllable training-time coordinate: a single scalar shapes this realized dimension during training, and bisection targets any desired value within the rank cap. To theoretically support that, we show local regularity and monotonicity of the realized-dimension profile. Across collaboration, social, biological, and infrastructure networks, Spectra traces performance--capacity frontiers that make the trade-off between predictive accuracy and realized dimension visible. It performs competitively with strong link-prediction baselines, yields aligned lower-capacity views of the same fitted model through spectral prefixes, and provides a principled handle on capacity in the overparameterized regime. Capacity thus becomes a property of the fitted model rather than a hyperparameter of the training.

Nikolaos Nakis, Panagiotis Promponas, Konstantinos Tsirkas +4

Human Nature Lab, Yale University · Department of Electrical and Computer Engineering, Yale University · Department of Statistics and Data Science, Yale University +1

Graph Edge Sparsification Graph Representation Learning Spectral Low-Rank Structure Capacity

May 1, 2026cs.LG

Spectral Graph Sparsification Preserves Representation Geometry in Graph Neural Networks

Spectral graph sparsification is a classical tool for reducing graph complexity while preserving Laplacian quadratic forms. In graph neural networks (GNNs), sparsification is often used to accelerate computation while maintaining predictive performance. In this work, we study a complementary representation-level question: does sparsification preserve the geometry of learned embeddings? For polynomial-filter GNNs, we prove that any

ε

-spectral sparsifier induces

O(ε)

perturbations in polynomial graph filters, multilayer hidden representations, and their Gram matrices. These guarantees imply stability of squared pairwise distances, class means, and covariance structure in embedding space. We further establish finite-time training stability: under smoothness and boundedness assumptions, gradient descent on dense and sparsified graphs produces weight trajectories whose separation grows at most proportionally to the sparsification distortion. Empirically, effective-resistance sparsification validates the predicted perturbation chain on synthetic graphs and preserves hidden representation geometry on real datasets. In our experiments, the gram matrix and training dynamics show low divergence even under substantial sparsification, consistent with the predicted stability under spectral sparsification. Hidden Gram preservation strongly predicts neighborhood preservation and class-centroid stability across FashionMNIST, Cora, and Paul15. Together, these results show that spectral sparsification preserves not only graph operators, but also the representation geometry that supports downstream use of GNN embeddings for interpretability.

Sanjukta Krishnagopal

Department of Computer Science, University of California Santa Barbara

Graph Edge Sparsification Graph Neural Networks Sparsity Representation Space

Apr 29, 2026cs.LG

Large-scale semi-supervised learning with online spectral graph sparsification

We introduce Sparse-HFS, a scalable algorithm that can compute solutions to SSL problems using only O(n polylog(n)) space and O(m polylog(n)) time.

Daniele Calandriello, Alessandro Lazaric, Michal Valko

Team SequeL Inria Lille – Nord Europe, France

Graph Edge Sparsification Sparsity Semi-Supervised Learning Self-Supervised Learning

Apr 28, 2026eess.SP

Sparse Graph Learning from Sparse Data via Fiedler Number Maximization

We aim to learn a sparse and connected graph from sparse data, where the number of observations K can be substantially smaller than the signal dimension N for signals x in R^N, and the underlying distribution is unknown. In this severely ill-posed setting, we incorporate Fiedler number (the second eigenvalue of the graph Laplacian matrix that quantifies connectedness) as a robust regularization term in the sparse graph learning objective. We first develop a greedy algorithm that iteratively selects one edge globally for weakening/removal to reduce the objective, leveraging eigenvalue perturbation theorems that bound the adverse effect of an edge change to the Fiedler number. Next, we design a parallel variant, based on the Cheeger's inequality, that recursively partitions an input graph into two sub-graphs using an approximate Cheeger cut to distributedly find an optimal edge. Simulation experiments show that Fiedler number maximization robustifies sparse graph estimates, outperforming previous sparse graph learning algorithms.

Bahar Oveisgharan, Gene Cheung, Andrew Eckford

York University, Canada

Graph Edge Sparsification Graph Laplacians Sparsity Maximization

Apr 22, 2026cs.LG

Spectral Embeddings Leak Graph Topology: Theory, Benchmark, and Adaptive Reconstruction

Graph Neural Networks (GNNs) excel on relational data, but standard benchmarks unrealistically assume the graph is centrally available. In practice, settings such as Federated Graph Learning, distributed systems, and privacy-sensitive applications involve graph data that are localized, fragmented, noisy, and privacy-leaking. We present a unified framework for this setting. We introduce LoGraB (Local Graph Benchmark), which decomposes standard datasets into fragmented benchmarks using three strategies and four controls: neighborhood radius

d

, spectral quality

k

, noise level

σ

, and coverage ratio

p

. LoGraB supports graph reconstruction, localized node classification, and inter-fragment link prediction, with Island Cohesion. We propose AFR (Adaptive Fidelity-driven Reconstruction), a method for noisy spectral fragments. AFR scores patch quality via a fidelity measure combining a gap-to-truncation stability ratio and structural entropy, then assembles fragments using RANSAC-Procrustes alignment, adaptive stitching, and Bundle Adjustment. Rather than forcing a single global graph, AFR recovers large faithful islands. We prove heat-kernel edge recovery under a separation condition, Davis--Kahan perturbation stability, and bounded alignment error. We establish a Spectral Leakage Proposition: under a spectral-gap assumption, polynomial-time Bayesian recovery is feasible once enough eigenvectors are shared, complementing AFR's deterministic guarantees. Experiments on nine benchmarks show that LoGraB reveals model strengths and weaknesses under fragmentation, AFR achieves the best F1 on 7/9 datasets, and under per-embedding

(ε,δ)

-Gaussian differential privacy, AFR retains 75% of its undefended F1 at

ε=2

. Our anonymous code is available at https://anonymous.4open.science/r/JMLR_submission

Thinh Nguyen-Cong, Truong-Son Hy, Thang N. Dinh

Department of Computer Science Virginia Commonwealth University Richmond, VA, USA · Department of Computer Science The University of Alabama at Birmingham Birmingham, AL, USA

Graph Edge Sparsification Federated Graph Learning Theory

Apr 22, 2026cs.LG

Machine Learning-based Two-Stage Graph Sparsification for the Travelling Salesman Problem

High-performance TSP solvers such as Lin-Kernighan-Helsgaun (LKH) search within a \emph{candidate graph} -- a small subset of edges pre-selected for the solver -- rather than over the complete graph. The two leading sparsification heuristics,

α

-Nearest and POPMUSIC, each fall short of the density-coverage balance:

α

-Nearest is dense with stable recall, while POPMUSIC is sparser but its recall degrades with scale. Their union closes the recall gap while remaining far below the complete graph in density, leaving room for further reduction. Existing learning-based sparsifiers score edges on the complete graph, an approach that is expensive and largely limited to Euclidean instances. We propose a two-stage method that inverts this logic. Stage1 takes the union of $α$ -Nearest and POPMUSIC, achieving near-perfect recall at ${\sim}6N$ edges. Crucially, the union annotates each edge with its \emph{source provenance} -- whether it was endorsed by $α$ -Nearest, POPMUSIC, or both. Stage2 trains a lightweight classifier on these annotated edges and prunes the lowest-scoring ones. Because dual-source edges are almost always optimal, the learning problem reduces to filtering the single-source subset -- a substantially easier task than classifying all

O(N^2)

edges from scratch. Across four distance types, five spatial distributions, and problem sizes from 50 to 500, the pipeline reduces candidate-graph density by

37

-

47\%

while retaining

{\geq}99.69\%

of optimal-tour edges, and matches or exceeds the coverage of recent Euclidean-only neural sparsifiers at lower density at TSP500.

Bo-Cheng Lin, Yi Mei, Mengjie Zhang

Centre for Data Science and Artificial Intelligence, and the School of Engineering and Computer Science, Victoria University of Wellington, Wellington, 6140, New Zealand

Salesman Problem Graph Edge Sparsification Edge Factual Recall

Apr 22, 2026cs.LG

Improved large-scale graph learning through ridge spectral sparsification

Graph-based techniques and spectral graph theory have enriched the field of machine learning with a variety of critical advances. A central object in the analysis is the graph Laplacian L, which encodes the structure of the graph. We consider the problem of learning over this Laplacian in a distributed streaming setting, where new edges of the graph are observed in real time by a network of workers. In this setting, it is hard to learn quickly or approximately while keeping a distributed representation of L. To address this challenge, we present a novel algorithm, GSQUEAK, which efficiently sparsifies the Laplacian by maintaining a small subset of effective resistances. We show that our algorithm produces sparsifiers with strong spectral approximation guarantees, all while processing edges in a single pass and in a distributed fashion.

Daniele Calandriello, Ioannis Koutis, Alessandro Lazaric +1

SequeL team, INRIA Lille - Nord Europe, France · LCSL, IIT, Italy · New Jersey Institute of Technology, USA +1

Graph Edge Sparsification Graph Laplacians Sparsity Ridge

Apr 20, 2026cs.LG

Faster by Design: Interactive Aerodynamics via Neural Surrogates Trained on Expert-Validated CFD

Computational Fluid Dynamics (CFD) is central to race-car aerodynamic development, yet its cost -- tens of thousands of core-hours per high-fidelity evaluation -- severely limits the design space exploration feasible within realistic budgets. AI-based surrogate models promise to alleviate this bottleneck, but progress has been constrained by the limited complexity of public datasets, which are dominated by smoothed passenger-car shapes that fail to exercise surrogates on the thin, complex, highly loaded components governing motorsport performance. This work presents three primary contributions. First, we introduce a high-fidelity RANS dataset built on a parametric LMP2-class CAD model and spanning six operating conditions (map points) covering straight-line and cornering regimes, generated and validated by aerodynamics experts at Dallara to preserve features relevant to industrial motorsport. Second, we present the Gauge-Invariant Spectral Transformer (GIST), a graph-based neural operator whose spectral embeddings encode mesh connectivity to enhance predictions on tightly packed, complex geometries. GIST guarantees discretization invariance and scales linearly with mesh size, achieving state-of-the-art accuracy on both public benchmarks and the proposed race-car dataset. Third, we demonstrate that GIST achieves a level of predictive accuracy suitable for early-stage aerodynamic design, providing a first validation of the concept of interactive design-space exploration -- where engineers query a surrogate in place of the CFD solver -- within industrial motorsport workflows.

Nicholas Thumiger, Andrea Bartezzaghi, Mattia Rigotti +5

IBM Research · Dallara Automobili

Computational Fluid Dynamic Aerodynamics Surrogate Models Graph Edge Sparsification

Apr 18, 2026cs.SI

Spectral Analysis of Fake News Propagation

The propagation structure of fake news has been shown to be an important cue for detecting it; yet, existing propagation-based fake news detection methods have mainly relied on ad hoc topological features, and a unified view of cascade patterns is still lacking. To address this, we study news propagation from a spectral view by connecting graph spectra to propagation-related structural properties through rigorous spectral bounds. In particular, we introduce several new bounds and integrate them with existing ones into a unified spectral representation of information propagation. We then use these spectral bounds for downstream classification and design a discrete structural optimization framework to interpret learned propagation patterns. For efficient optimization, we rely on a first-order perturbation approximation and consider both score-guided and bound-guided objectives. Experiments on real-world data reveal meaningful spectral differences between fake and real news, competitive classification performance from spectral bounds, and interpretable evolution trajectories from structural optimization. The findings demonstrate the value of spectral analysis for understanding and modeling news propagation.

Weibin Cai, Reza Zafarani

Data Lab, Department of EECS, Syracuse University, New York, USA.

Fake News Detection Spectral Graph Edge Sparsification Fake News Propagation Headlines

Apr 2, 2026cs.LG

A Spectral Decomposition Framework for Multiscale Nonlinear Dimensionality Reduction

Dimensionality reduction (DR) involves two longstanding trade-offs. First, preserving local neighborhoods can come at the cost of global structure. Neighbor embedding methods such as t-SNE and UMAP prioritize local similarity preservation but do not explicitly constrain global organization, whereas standard spectral methods such as Laplacian Eigenmaps capture smooth, coarse-scale graph structure but offer limited flexibility to depict finer local structure. Second, the flexibility of nonlinear DR methods often comes at the cost of analytical transparency. Many methods do not explicitly reveal how high-dimensional structure produces patterns in the embedding. We introduce SDMP (Spectral Decomposition for Multiscale Projection), a nonlinear DR framework built on an explicit spectral decomposition. In this formulation, each embedding dimension is expressed as a weighted combination of Laplacian eigenvectors derived from a neighborhood graph, with the weights learned via a UMAP-style cross-entropy objective. By progressively expanding the spectral subspace to capture increasingly fine graph structure, SDMP produces a sequence of embeddings, making the evolving balance between global organization and local detail explicit, controllable, and inspectable. The explicit decomposition also reveals which spectral scales shape the overall embedding and how individual eigenvectors influence point positions. Quantitative evaluations on synthetic, image, and single-cell data show competitive local and global structure preservation, while case studies illustrate how the decomposition supports interpretation of clusters and developmental trajectories across spectral scales.

Zeyang Huang, Angelos Chatzimparmpas, Thomas Höllt +1

Linköping University, Sweden · Utrecht University, The Netherlands · University of Bergen, Norway +1

Dimensionality Reduction Graph Edge Sparsification Intrinsic Dimensionality Multiscale Spectral Decomposition Single-Cell Rna+1