CS Paper Radar

A dictionary learning framework for graphs via filters and optimal transport

Jinchuan Liao, Dai Hai Nguyen

cs.LG ·submitted 2026-09-05 06:27 UTC · v1
benchmark

Abstract

We propose a graph dictionary learning (GDL) framework where each graph is represented as a zero-mean Gaussian distribution derived from its filtered Laplacian. Each observed graph is approximated by a barycenter over learned atom graphs, computed under the filter graph distance (fGOT), a graph comparison metric sensitive to global structural properties. The reconstruction error between the observed graph and its barycenter is measured by the surrogate fGOT (sfGOT) distance, a tractable approximation of fGOT that handles graphs without known node correspondence, and is minimized end-to-end via backpropagation. We further provide a novel interpretation of sfGOT through the lens of the Hilbert-Schmidt Independence Criterion, showing that minimizing the sfGOT distance between two graphs is equivalent to maximizing statistical dependence between the spectral embedding of their nodes. Experiments on benchmark datasets demonstrate competitive performance over existing GDL methods on graph clustering and classification tasks.

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Transport for Network Comparison: A Unified Review with New Spectral Bounds and Machine Learning Applications

cs.LG stat.MLcs.SI ·2026-08-27 ·James Hyun, François G. Meyer
theory similarity 0.66
Abstract

Network comparison using optimal transport is a growing area of research in network science. Unlike standard graph metrics, optimal transport computes both network dissimilarity and a transport plan that explains how one graph morphs into another. In this paper, we review how optimal transport compares undirected, unweighted simple graphs using three primary distances: the Wasserstein, Gromov-Wasserstein, and Bures-Wasserstein distances. We examine the closed form of the Wasserstein distance in one dimension via node feature probability distributions, and show how the transport plans of the Wasserstein and Gromov-Wasserstein distances visualize how mass is shifted to transform one network into another. Beyond reviewing existing transport-based approaches, we establish new spectral lower and upper bounds for the Bures-Wasserstein distance and characterize the tightness of the lower bound under eigenbasis perturbations. Finally, we evaluate these distances using a synthetic network dataset for clustering and a real-world temporal network.

0.17

Graph Memory: Spectral Associative Memory via Dirichlet Energy

cs.LG cs.IR ·2026-09-26 ·Zhaoyang Shi
theory similarity 0.65
Abstract

Dense associative memories have traditionally focused on storing and retrieving vector-valued patterns. Many modern machine learning problems, however, are naturally graph-structured, requiring memory mechanisms for relational patterns, graph diffusion geometries, community structures, and graph-based inductive biases. We propose a spectral dense associative memory for storage and retrieval of graph data, extending the classical vector-valued memories. Retrieval is performed through a log-sum-exp energy induced by Dirichlet energy with spectral norm distances, producing a softmax-weighted average of the stored Laplacians that remains a valid graph Laplacian. We prove exponential storage capacity and exponentially decaying retrieval error. Beyond graph retrieval, we establish theoretical guarantees for spectral quantities central to graph learning, including eigenvalues, eigenspaces, and diffusion operators. Experiments on synthetic graph data, real-world airline network, protein conformation data and wearable sensor data demonstrate robust graph retrieval while preserving the graph geometry of the data. Our framework provides a new associative memory paradigm for graph-structured data and bridges dense associative memory with modern graph learning and generative AI.

0.15

Graph Learning with Spectral Connectivity Priors for Scarce Data

cs.LG eess.SP ·2026-09-23 ·Mingxiao Liu, Bahar Oveisgharan, Bingyan Zou, Gene Cheung, H. Vicky Zhao +1 more
similarity 0.65
Abstract · 5 pages, 1 figure. Submitted to IEEE ICASSP 2027

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.

0.24

Sparse Dictionary Learning for Measure-Valued Data via Linearized Optimal Transport: Efficient Algorithms and Sample Complexity

cs.LG stat.ML ·2026-10-09 ·Brendan Mallery, Shuchin Aeron, James Murphy
similarity 0.64
Abstract

We study dictionary learning for probability measure-valued data by embedding measures into Hilbert spaces using features derived from optimal transport geometry. We learn data-adapted dictionaries through sparse autoencoder parameterizations, producing fast, scalable representations of probability measures as sparse finite-dimensional codes. The resulting framework combines the rich, geometric structure of optimal transport with the interpretability and efficiency of sparse representation learning. We demonstrate its utility across diverse data modalities, including hyperspectral images, geometric point clouds, and document embeddings in large language model latent spaces. We also prove generalization bounds for sparse dictionary learning objectives on broad classes of $L^2$-valued measure embeddings, expressed in terms of the metric complexity of the atom class. For optimal transport and entropic transport map dictionaries, we derive new covering number bounds that yield explicit rates. Together, our computational and theoretical results support a new, scalable model for representation learning in the space of probability measures via embedding into Hilbert spaces.

0.28

GraCo: A Unified Toolkit of Graph Coarsening Algorithms and Metrics

cs.LG ·2026-10-31 ·Antonin Joly
code/data similarity 0.63
Abstract · Code: https://github.com/Antonin-J/graco

Graph coarsening aims to reduce a graph to a smaller one that preserves chosen properties of the original. It is increasingly used to scale graph learning to large graphs, as a non-differentiable step applied once before training. Many coarsening methods have been proposed in recent years, each with its own implementation, notation and evaluation. In this work, we introduce GraCo, a unified toolkit of graph coarsening methods. It relies on a single definition: a coarsening is fixed by a partition of the nodes and by the Laplacian the coarsened graph is consistent with. The coarsened graph, and the reduction and lifting matrices that map signals from the original graph to the coarsened one and back, follow from these two choices. We implement 17 methods from the literature and a random baseline, grouped into five families, with the same notation, inputs and outputs. We also build a collection of metrics from different papers, applicable to any coarsening. We check the implementations on a synthetic stochastic block model, then we report the runtime and peak memory of each method on Cora, PubMed, ogbn-arxiv and ogbn-products. GraCo is open-source and available at https://github.com/Antonin-J/graco.

0.42

Geometry-Aware Graph Construction via Adaptive Spectral Bandwidth Control

cs.LG eess.SP ·2026-09-03 ·Ecem Bozkurt, Antonio Ortega
published similarity 0.62
Abstract · Accepted at IEEE MLSP 2026. 6 pages, 4 figures

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.

0.27

Scaling Graph Similarity Learning with Graph Neural Networks

cs.LG cs.AI ·2026-11-06 ·Ahmet Tüzen, Helge Langseth, Kjetil Nørvåg
benchmark similarity 0.61
Abstract

Graph similarity computation is an important task in graph mining with many real-world applications, such as chemical compound analysis, program dependence comparison, and social network analysis. The problem is computationally challenging: Graph Edit Distance (GED) and Maximum Common Subgraph (MCS), which quantify the distance between graphs and identify their largest shared subgraph, respectively, are NP-hard to compute exactly. To address these computational challenges, Graph Neural Networks (GNNs) have been applied to this problem. However, existing GNN-based approaches have primarily focused on small-scale graph datasets, while scalability to larger scales remains underexplored. In this work, we propose FiLSim, a scalable GNN-based framework, and investigate whether a simplified GNN pipeline can maintain competitive performance on standard benchmarks while scaling to large graphs. We additionally propose a sequential graph-editing strategy to construct large-scale graph datasets with reliable GED labels to evaluate scalability. The proposed framework is evaluated on four benchmark datasets and four newly created large-scale datasets, demonstrating its effectiveness and scalability. FiLSim remains accurate on graphs with more than 150{,}000 nodes, where the baseline methods run out of memory or fail to learn, and scores all test pairs within seconds on a single GPU.

0.25

Graph Matching Relaxations and Amortization for Supervised Graph Prediction

cs.LG stat.ML ·2026-09-14 ·Federico Méndez, Paul Krzakala, Gabriel Melo, Charlotte Laclau, Rémi Flamary +1 more
similarity 0.61
Abstract

End-to-end Supervised Graph Prediction (SGP) requires a permutation-invariant loss to compare predicted and target graphs with arbitrary node orderings. Such losses typically involve a costly graph-matching problem. We first study three Optimal Transport relaxations of this problem and show, theoretically and empirically, that the Gromov-Wasserstein (GW) objective is the most suitable for SGP. Then, to avoid solving the resulting inner optimization for every training example, we propose to amortize the graph matching (node alignment) problem. For each training sample, the loss function leverages a transport plan provided by a parametric matcher based on the differentiable Sinkhorn algorithm applied on empirical node distributions. The graph prediction module and the matcher are jointly learned. We showcase the efficiency of this approach on toy and real world SGP problems of increasing complexity including a novel Mass-spectra to Scaffold task that we introduce.

0.13