CS Paper Radar

The Fast Tree Transform

Paul Burchard

cs.LG math.DGmath.SP ·submitted 2026-11-07 04:32 UTC · v1
unusual

Abstract

The Fast Tree Transform is a locally-aggregated transform defined for arbitrary graph geometries that generalizes both the Hadamard frequency transform and the Haar wavelet transform on the circle. The pure frequency part of the transform approximately diagonalizes the graph Laplacian; this fact makes it useful as a preconditioner in geometric optimization problems. The full transform provides an only slightly-redundant representation of signals on the graph that allows sparse representation of signals that include both edges and textures.

Closest papers

Nearest neighbours by meaning across the whole index.

Structure-Adaptive Tree Field Integrators

cs.LG cs.CVcs.DSmath.NA+1 ·2026-09-27 ·Millend Roy, Soham Samal, Ivan Zelich, Krzysztof Marcin Choromanski
similarity 0.52
Abstract

We present a new class of near-linear algorithms for efficiently integrating general tensor fields defined on trees with distance dependent kernels, the Structure-Adaptive Tree Field Integrators (STAD-TFIs). STAD-TFIs exploit the tree's underlying structure through decompositions built around path backbones and single vertex separators, and use two-dimensional fast Fourier transforms to compute interactions jointly. By exploiting this structural information, STAD-TFIs achieve more computationally efficient integration than their regular efficient tree field integrators (TFI) counterparts. We provide a detailed theoretical analysis of our proposed approach and complement it with an exhaustive empirical evaluation, ranging from speed tests on synthetic trees, through accelerated Sinkhorn-based relaxations of the Optimal Transport algorithms on real meshes, to Topological Attention Transformers for vision tasks. To the best of our knowledge, we provide some of the first results showing that efficient to compute and accurate relaxations of the geodesic Sinkhorn-based solutions of the Optimal Transport problem can be derived by applying fast TFI methods.

0.29

Learned Queries and Keys Are All You Need: Replacing the Value Projection with Structured Transforms

cs.LG ·2026-09-29 ·Ene Meco, Emadeldeen Hamdan, A. Enis Cetin
unusual similarity 0.43
Abstract

To reduce the number of parameters and cache memory requirements of transformers we introduce dual-headed transformers instead of three heads. We studied Walsh-Hadamard Transform (WHT), Discrete Cosine Transform (DCT), Discrete Fourier Transform, filterbank based Shearlet Transform, and Multiplication-Avoiding (MA) operators to construct dual heads. We combine spatial patches and their orthogonal transforms (or Shearlet and MA operators) in a structure similar to the attention block. We obtained better results than triple headed transformers in ImageNet. Extensive simulation examples are presented.

0.27

On the Real Part of Butterfly Factorizations, with Application to Fast Transforms

eess.SP ·2026-10-05 ·Ma{ë}l Chaumette, R{é}mi Gribonval, Elisa Riccietti
similarity 0.43
Abstract

Fast transforms such as the Discrete Cosine Transform can be expressed as the real part of a product of complex-valued structured sparse matrices known as Kronecker-sparse factors. More generally, products of such structured sparse matrices appear in square dyadic butterfly and monarch matrices, which are known to represent many fast transforms efficiently. Yet, it has remained unclear whether taking the real or the imaginary part of such products preserves this structure. In this letter, we give a condition on the factors to ensure that the structure is preserved. This condition is satisfied in the case of the Discrete Cosine Transform, the Discrete Sine Transform and the Discrete Hartley Transform, allowing us to provide a new representation of these transforms as products of real-valued Kronecker-sparse factors, which opens new avenues for efficient GPU implementations using low-precision numerical format.

0.22

$hp$-adaptive trees for graph signal approximation

eess.SP math.NA ·2026-09-10 ·Giacomo Elefante, Wolfgang Erb, Michael Multerer
similarity 0.43
Abstract

Tree-encoded partitionings of graphs are fundamental tools for the decomposition and approximation of graph signals. For the efficient approximation of such graph signals, we develop strategies based on $hp$-refinement by combining domain decomposition with an improved local approximation using polynomials of higher degree. In this way, from a given graph partitioning tree, a more efficient subtree is extracted in which the cost of the signal approximation is considerably reduced by still maintaining the same total error. To this end, we interpret the refinement process as a binary knapsack problem to determine an enhanced partitioning tree. We further study an a-posteriori strategy which prunes the partitioning tree by optimizing the polynomial degrees over the subdomains. To make polynomial basis systems accessible for general graphs or high-dimensional data, we propose local embeddings of graphs into low dimensional Euclidean spaces. We underpin the efficiency of our algorithms with extensive numerical tests which carefully assess the impact of the applied refinements and optimization strategies.

0.28

Tree Edit Distance: Near-Linear-Time Approximate, Sublinear, and Dynamic

cs.DS ·2026-10-15 ·Bingbing Hu, Tomasz Kociumaka, Jakob Nogler, Barna Saha
published similarity 0.43
Abstract · SODA 2027

Tree edit distance (TED), the analog of string edit distance (ED) for hierarchical data, is the minimum number of node insertions, deletions, and substitutions transforming one labeled rooted ordered tree into another. We narrow polynomial gaps between TED and ED in near-linear-time approximation, sublinear algorithms, and dynamic algorithms. We give an $n^{o(1)}$-approximation in $O(n)$ time and, for every $0<δ<1$, a $(\log n)^{O(1/δ)}$-approximation in $O(n^{1+δ})$ time. This improves the previous near-linear-time $O(\sqrt n)$-approximation [Boroujeni et al., STOC'19] and brings TED to parity with ED in this regime up to polylogarithmic factors. With query access to the balanced-parentheses (Euler-tour) representation of the input trees, we give the first sublinear-time TED algorithm: for every $τ\in[1,n]$, it computes a $τn^{o(1)}$-approximation of $1+\mathrm{ted}$ in $O(n/τ)$ time. For dynamic TED, we give an exact algorithm with amortized update time $\tilde{O}(k^7)$ and a $(1+\varepsilon)$-approximation with amortized update time $\tilde{O}_{\varepsilon}(k)$, where $k$ caps the distance that must be reported. The exact algorithm is the first to beat recomputation in a nontrivial parameter regime. The approximation improves prior dynamic guarantees [Das et al., FOCS'25] and cannot be significantly improved in any parameter regime without a breakthrough for static $(1+\varepsilon)$-approximation of ED. All results use dynamic programming on a new hierarchical tree decomposition, analogous to partitioning strings into blocks of geometrically decreasing sizes. It combines structural properties previously achieved only in isolation, providing a framework for transferring algorithmic ideas from ED to TED, with additional ingredients addressing the obstacles in each computational setting.

0.34

Diffusion Transformers for Roof Graph Synthesis and Reconstruction

cs.CV ·2026-08-26 ·Daniel Panangian, Ksenia Bittner
published similarity 0.42
Abstract · Pre-review manuscript. Accepted at the ICPR 2026 Workshop on Pattern Recognition in Remote Sensing (PRRS)

We present RoofDiT, a generative framework for 2D roof graph synthesis and reconstruction. Roofs are compactly described as planar graphs of junctions and structural edges, but existing methods often rely on fixed geometric rules or direct reconstruction objectives. RoofDiT instead models roof structures directly as vertex-edge graphs and learns a conditional generative prior over their geometry and connectivity. Our framework follows a two-stage design: a diffusion transformer generates roof vertices, and an edge prediction module infers the corresponding graph topology. To improve geometric fidelity, RoofDiT combines relative geometry-aware attention with footprint and aerial-image conditioning, while using an alignment regularizer to encourage common horizontal, vertical, and diagonal roof patterns. The same model supports unconditional generation, footprint-conditioned synthesis, and image-guided reconstruction by changing the conditioning signal. Experiments show improved graph generation quality over a diffusion baseline, favorable performance against a straight-skeleton prior in the footprint-conditioned setting, and the highest edge F1 among compared methods for image-guided reconstruction.

0.36

Beyond Pairwise Graphs in Science: Hypergraph Adaptive Wavelet Operators for Parametric PDEs

cs.LG physics.comp-ph ·2026-08-28 ·Rajat Sarkar, Venkataramana Runkana, Souvik Chakraborty
similarity 0.42
Abstract

Physical systems are often modeled by solution operators that map input fields, parameters, geometries, or past states to steady or future physical states. Learning these maps is difficult, especially for time-dependent systems that must assimilate history and remain stable under autoregressive rollout. Many neural operators work best on regular, structured grids, while realistic simulations often require unstructured meshes or point clouds to resolve complex geometries; in such settings, grid-centric representations can lose accuracy. Graph neural operators handle these domains through message passing or spectral graph filtering, but pairwise edges do not directly capture group-wise couplings among mesh cells, local neighborhoods, or conservation volumes. We introduce the Hypergraph Adaptive waveLet Operator (HALO), which lifts the domain to a hypergraph and learns in its spectral wavelet domain. HALO avoids explicit hypergraph-Laplacian eigendecomposition through Chebyshev polynomial wavelet filters, giving localized spectral kernels at linear sparse-matrix cost. Its trainable dyadic wavelet scales are regularized toward tight-frame coverage, allowing the frequency response to adapt to each PDE while encouraging stable multi-scale spectral coverage. Across 2D and 3D benchmarks on structured and unstructured discretizations, HALO achieves best or near-best accuracy among frequency-, transformer-, DeepONet-, state-space-, and graph-based baselines and sustains stable multi-step rollouts. The same model scales to industrial aerodynamic geometries: on meshes of a few hundred thousand points it is on par with, or better than, the strongest fixed-discretization transformers, while remaining resolution-equivariant.

0.19

Hierarchical Clustering and Signal Denoising on Digraphs

eess.SP cs.LG ·2026-09-28 ·Yi Wang, Sippanon Kitimoon, Hrushikesh N. Mhaskar, Xiaosheng Zhuang
similarity 0.42
Abstract

In this paper, we propose a representation of a digraph (directed graph) as a Hermitian matrix derived from its adjacency matrix. This representation characterizes both the connectivity and the edge orientation of the digraph. Based on the spectral decomposition of the Hermitian matrix, a digraph clustering algorithm with $k$-means is introduced to produce a partition on the graph. Applying this algorithm (bottom-up) recursively to a digraph with partially labeled vertices yields a spectral hierarchical digraph clustering (\myproj) algorithm that produces consistent nested partitions of the digraph, or equivalently, a tree structure. Furthermore, based on the in-degree and out-degree of each cluster in the digraph clustering, a pair of hierarchical interval partitions (filtrations) can be derived in a top-down manner to produce a pair of nested knot sequences. These knot sequences facilitate the construction of multilevel spline quasi-interpolants, enabling a noisy graph signal to be decomposed into a coarse approximation and inter-level details, followed by adaptive thresholding and reconstruction. Experiments on synthetic and real-world digraphs demonstrate the superiority of our {\myproj} algorithm for digraph clustering across diverse graph structural properties (homophily and heterophily) and supervision settings. Moreover, experiments on digraph signal processing using multilevel spline quasi-interpolants further demonstrate the effectiveness of signal recovery on digraphs in terms of RMSE and SNR.

0.24