Spectral Graph Embedding

Follow this topic Ask about this topic

Latest papers

16 papers1 paper in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Oct 1, 2026

Learning Commute-Time-Preserving World Models for Planning

World models allow agents to plan in latent space by choosing a sequence of actions that most reduces the distance to a given goal state. Thus, planning can benefit from latent representations whose distances mirror commute-times in the environment. The spectral embedding space of the graph Laplacian provides such a representation, if it obeys a specific eigenvalue-dependent scaling. Unfortunately, instantiating the graph Laplacian is intractable in large, continuous environments. Self-supervised learning offers a natural route to such commute-time-preserving embeddings at scale. However, here we show that existing methods, which commonly encourage isotropic representations to prevent representational collapse, tend to degrade the "correct" eigenvalue-dependent scaling, leading to an inaccurate representation of commute times. To address this problem, we introduce Commute-Time-Preserving World Models (CTWMs), combining a latent displacement predictor and a log-determinant regularizer that prevents collapse, which provably recover the correctly scaled Laplacian representation under reversible deterministic dynamics and at the predictor's fixed point. In numerical simulations, CTWM matches or outperforms LeWM, a task-agnostic baseline, on several complex, continuous goal-reaching benchmarks, while using half the parameters.

Michael Hauri, Peter Buttaroni, Fabian A. Mikulasch +1

Friedrich Miescher Institute for Biomedical Research, Basel, Switzerland · Faculty of Science, University of Basel, Switzerland

Spectral Graph Embedding Representation Learning World Model Learning Latent Dynamics Modeling World Model-Based Planning Model-Based Planning+2

Sep 2, 2026

Spectral Initialization and Scheduled Graph Smoothness for Uncertain Knowledge Graph Completion

Uncertain knowledge graphs (UKGs) extend knowledge graphs by assigning each triple a continuous confidence score. Since most possible triples lack observed confidences, recent methods rely on semi-supervised learning to generate pseudo-labels. These methods initialize entity embeddings without using the confidence-weighted graph, discarding its global community and hub structure. We introduce QUEST, which adds no trainable parameters to the standard confidence-distribution learning pipeline. First, QUEST initializes entity embeddings using the smallest non-trivial eigenvectors of the confidence-weighted graph Laplacian, incorporating community and hub structure before training. Second, QUEST applies an unbiased mini-batch Dirichlet energy regularizer to enforce early-stage structural consistency. On two UKG datasets, QUEST improves confidence prediction and link prediction on six of eight metric-dataset pairs over prior methods and matches the previous best on the remaining two, while removing the instability spike observed on dense graphs. These results indicate that spectral structural priors combined with a graph Dirichlet energy regularizer improve accuracy, training stability, and checkpoint reliability in UKG completion.

Md Abrar Jahin, Taufikur Rahman Fuad, Jay Pujara +1

University of Southern California · Islamic University of Technology

Spectral Graph Embedding KG Completion Link Prediction Graph Embedding Spectral Regularization

Aug 12, 2026

Adjacency-Based Spectral Proxy Control of Mobile Communication Agents

We consider a heterogeneous mobile-agent network composed of uncontrolled task agents and controllable communication agents. The objective is to reposition communication agents online as task agents move. Since throughput-based objectives are generally unsuitable for real-time control, spectral graph metrics such as algebraic connectivity are commonly adopted as surrogate objectives. However, controlling algebraic connectivity relies on the eigenvector corresponding to the second-smallest eigenvalue of a graph's Laplacian matrix (i.e., the Fiedler vector), whose distributed estimation requires an unbounded number of communication rounds to converge. In this work, we identify a structural decomposition of this Fiedler-gradient controller into a local interaction rule and a graph embedding component, suggesting the use of alternative embeddings that are easier to estimate distributively than the Fiedler vector. As a particular instance, we propose A-Fiedler, which replaces the Fiedler embedding with the dominant eigenvector of the adjacency matrix, commonly used as a graph embedding of nodes into a latent geometry. This representation is more naturally suited for distributed implementation under local communication constraints. We evaluate A-Fiedler against the classical Fiedler-gradient controller. Results show comparable network performance in the absence of communication constraints and improved robustness under distributed estimation. For instance, under the same number of communication rounds, the Fielder-gradient may even converge to disconnected configurations whereas our proposition maintains performance. We believe our contribution provides a simpler path toward distributed network control.

Mariana del Castillo, Federico Larroca

Facultad de Ingenier´ıa Universidad de la Rep´ublica Montevideo, Uruguay

Spectral Graph Embedding Multi-Agent Control

Aug 11, 2026

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

Clustering Spectral Clustering Graph Embedding Spectral Graph Embedding

Jul 30, 2026

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

Spectral Graph Embedding Graph Representation Learning Energy-Based Models Graph Embedding Image Classification

Jul 9, 2026

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

Manifold Learning Dimensionality Reduction Spectral Methods Invariant Representation Learning Spectral Graph Embedding

Jul 8, 2026

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

Spectral positional encodings (PEs) for 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 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

Positional Encoding Spectral Methods Invariant Representation Learning Krylov Subspace Methods Graph Positional Encoding Spectral Graph Embedding

Jun 30, 2026

Planar-SfM: Camera Pose Estimation via Homography Graph Embeddings

Structure from Motion (SfM) systems traditionally struggle with planar scenes, where standard epipolar geometry-based methods become degenerate. Rather than viewing planar surfaces as a limitation, we propose a unified framework that leverages them as a source of geometric constraints. Our key insight is that each planar surface visible across multiple views provides an independent estimate of relative camera poses through homography decomposition. By aggregating estimates from multiple planes or even from a single dominant plane we achieve robust pose recovery in scenarios where traditional methods fail. We introduce a novel graph-based approach that constructs a pose-graph from homography estimates and employs spectral embedding to identify and filter unreliable edges. Our method maps homography-based pose estimates onto the real line based on their geometric and visual consistency, enabling efficient extraction of a maximally consistent spanning tree for pose recovery. This approach naturally handles both highly planar scenes, such as indoor sports arenas, and general

3

D environments. We demonstrate superior performance on basketball court imagery where existing methods struggle, while matching or exceeding state-of-the-art results on unconstrained outdoor scenes from the IMC Phototourism benchmark.

Gabi Pragier, Matan Karklinsky, David Ungarish +1

Amazon Prime Video Live Events

Spectral Graph Embedding Multi-View Geometry Camera Pose Estimation Structure from Motion

Jun 11, 2026

SMGFM: Spectral Multimodal Graph Pretraining for Multimodal-Attributed Graphs

Multimodal-attributed graphs (MAGs) couple graph topology with node semantics from text, images, and other modalities. Traditional graph learning contextualizes node semantics by coupling topology with node features. However, this coupling design becomes troublesome in MAGs, where structure-induced and modality-intrinsic semantics may contribute differently to downstream tasks. Structure-induced semantics promote relational consistency through smooth topological variation, whereas modality-intrinsic semantics often encode local, fine-grained distinctions that should not be uniformly smoothed or aligned. Therefore, the key challenge is to identify semantic roles before cross-modal fusion. To this end, we leverage graph-frequency variation as a prior, where low-frequency components capture topology-consistent semantics and high-frequency components preserve modality-specific semantics. Based on this intuition, we propose SMGFM, a spectral multimodal graph pretraining framework that decomposes each modality-specific node signal into graph-frequency bands and assigns band-level semantic roles before cross-modal interaction. Concretely, SMGFM constructs frequency-resolved modality tokens with scalable Chebyshev filters, estimates their coupling reliability through topology-conditioned routing, and performs band-modality interaction before fusion. Its frequency-routed objectives align smooth consensus routes while preserving modality-specific routes, mitigating spatial-domain entanglement and uniform cross-modal alignment. Extensive experiments conducted on the MAG datasets demonstrate that SMGFM achieves state-of-the-art performance across graph-level and modality-level tasks.

Zhengyu Wu, Xu Wang, Hongchao Qin +4

Spectral Graph Embedding Graph Representation Learning Cross-Modal Alignment Multimodal Pretraining Multimodal Graph Learning Multimodal Fusion

May 21, 2026

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 Embedding Spectral Methods Spectral Graph Embedding

May 6, 2026

Multiscale Euclidean Network Trajectories: Second-Moment Geometry, Attribution, and Change Points

A central challenge in dynamic network analysis is to represent temporal evolution in a way that is both geometrically meaningful and statistically identifiable. One approach embeds a sequence of network snapshots as trajectories in a Euclidean space and relates these trajectories to node embeddings. In multilayer and unfolded spectral constructions, however, node embeddings and their underlying latent positions are identifiable only up to general linear transformations. Although this ambiguity preserves edge probabilities, it can distort geometry and invalidate distance based temporal comparisons at both the trajectory and node-levels. We develop Multiscale Euclidean Network Trajectories (MENT), a framework for multiscale temporal trajectories based on second-moment geometry. By imposing an isotropic normalization on the anchor latent positions, we reduce the relevant ambiguity to orthogonal transformations and prevent distortion of the second-moment geometry. In this canonical representation, we define a trace variation distance and mode-wise variation distances along orthogonal directions, and use multidimensional scaling to obtain low-dimensional trajectories of time points at both global and mode-wise levels. The resulting trajectories support interpretation and inference. They admit mode-wise decompositions, support attribution of global and mode-wise temporal changes to nodes, and enable change point detection through 1D trajectories. We prove consistency of the proposed unfolded spectral embedding and of the induced temporal trajectories. Experiments on two synthetic and two real dynamic networks illustrate stable and interpretable recovery of temporal structure and show strong performance against existing change point detection baselines.

Haruka Ezoe, Ryohei Hisano

Graduate School of Information Science and Technology The University of Tokyo · The Canon Institute for Global Studies

Spectral Graph Embedding Dynamic Graph Learning Change-Point Detection Graph Embedding

Apr 27, 2026

Diffusion-Guided Feature Selection via Nishimori Temperature: Noise-Based Spectral Embedding

We propose Noise-Based Spectral Embedding (NBSE), a physics-informed framework for selecting informative features from high-dimensional data without greedy search. NBSE constructs a sparse similarity graph on the samples and identifies the Nishimori temperature

β_N

the critical inverse temperature at which the Bethe Hessian becomes singular. The corresponding smallest eigenvector captures the dominant mode of an intrinsically degree-corrected diffusion process, naturally reweighting nodes to prevent hub dominance. By transposing the data matrix and applying NBSE in feature space, we obtain a one-dimensional spectral embedding that reveals groups of redundant or semantically related dimensions; balanced binning then selects one representative per group. We prove that coloured Gaussian perturbations shift

β_N

by at most

O(\barσ^2)

, guaranteeing robustness to measurement noise. Experiments on ImageNet embeddings from MobileNetV2 and EfficientNet-B4 show that NBSE preserves classification accuracy even under aggressive compression: on EfficientNet-B4 the accuracy drop is below

1\%

when retaining only

30\%

of features, outperforming ANOVA

F

-test and random selection by up to

6.8\%

.

Vasiliy S. Usatyuk, Denis A. Sapozhnikov, Sergey I. Egorov

R&D Department T8 LLC Moscow, Russia · Department of Computer Science South-West State University Kursk, Russia

Feature Selection Dimensionality Reduction Spectral Methods Spectral Graph Embedding

Apr 22, 2026

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 Reconstruction Spectral Methods Spectral Graph Embedding

Mar 12, 2026

Uncovering Locally Low-dimensional Structure in Networks by Locally Optimal Spectral Embedding

Standard Adjacency Spectral Embedding (ASE) relies on a global low-rank assumption often incompatible with the sparse, transitive structure of real-world networks, causing local geometric features to be 'smeared'. To address this, we introduce Local Adjacency Spectral Embedding (LASE), which uncovers locally low-dimensional structure via weighted spectral decomposition. Under a latent position model with a kernel feature map, we treat the image of latent positions as a locally low-dimensional set in infinite-dimensional feature space. We establish finite-sample bounds quantifying the trade-off between the statistical cost of localisation and the reduced truncation error achieved by targeting a locally low-dimensional region of the embedding. Furthermore, we prove that sufficient localisation induces rapid spectral decay and the emergence of a distinct spectral gap, theoretically justifying low-dimensional local embeddings. Experiments on synthetic and real networks show that LASE improves local reconstruction and visualisation over global and subgraph baselines, and we introduce UMAP-LASE for assembling overlapping local embeddings into high-fidelity global visualisations.

Hannah Sansford, Nick Whiteley, Patrick Rubin-Delanchy

School of Mathematics, University of Bristol, UK · School of Mathematics, University of Edinburgh, UK

Spectral Graph Embedding Graph Embedding Spectral Methods Manifold Learning

Feb 18, 2026

Eigenmood Space: Uncertainty-Aware Spectral Graph Analysis of Psychological Patterns in Classical Persian Poetry

Classical Persian poetry is a historically sustained archive in which affective life is expressed through metaphor, intertextual convention, and rhetorical indirection. These properties make close reading indispensable while limiting reproducible comparison at scale. We present an uncertainty-aware computational framework for poet-level psychological analysis based on large-scale automatic multi-label annotation. Each verse is associated with a set of psychological concepts, per-label confidence scores, and an abstention flag that signals insufficient evidence. We aggregate confidence-weighted evidence into a Poet

\times

Concept matrix, interpret each poet as a probability distribution over concepts, and quantify poetic individuality as divergence from a corpus baseline using Jensen--Shannon divergence and Kullback--Leibler divergence. To capture relational structure beyond marginals, we build a confidence-weighted co-occurrence graph over concepts and define an Eigenmood embedding through Laplacian spectral decomposition. On a corpus of 61{,}573 verses across 10 poets, 22.2% of verses are abstained, underscoring the analytical importance of uncertainty. We further report sensitivity analysis under confidence thresholding, selection-bias diagnostics that treat abstention as a category, and a distant-to-close workflow that retrieves verse-level exemplars along Eigenmood axes. The resulting framework supports scalable, auditable digital-humanities analysis while preserving interpretive caution by propagating uncertainty from verse-level evidence to poet-level inference.

Kourosh Shahnazari, Seyed Moein Ayyoubzadeh, Mohammadali Keshtparvar

Sharif University of Technology, Tehran, Iran. · Amirkabir University of Technology, Tehran, Iran.

Spectral Graph Embedding Computational Literary Studies Uncertainty Quantification

Feb 17, 2026

Random Wavelet Features for Graph Kernel Machines

Node embeddings map graph vertices into low-dimensional Euclidean spaces while preserving structural information. They are central to tasks such as node classification, link prediction, and signal reconstruction. A key goal is to design node embeddings whose dot products capture meaningful notions of node similarity induced by the graph. Graph kernels offer a principled way to define such similarities, but their direct computation is often prohibitive for large networks. Inspired by random feature methods for kernel approximation in Euclidean spaces, we introduce randomized spectral node embeddings whose dot products estimate a low-rank approximation of any specific graph kernel. We provide theoretical and empirical results showing that our embeddings achieve more accurate kernel approximations than existing methods, particularly for spectrally localized kernels. These results demonstrate the effectiveness of randomized spectral constructions for scalable and principled graph representation learning.

Valentin de Bassompierre, Jean-Charles Delvenne, Laurent Jacques

INMA/ICTEAM, UCLouvain, Belgium

Graph Representation Learning Graph Embedding Spectral Graph Embedding Kernel Methods Random Feature Methods