hp-adaptive trees for graph signal approximation
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.
Related
- Rare subtree patterns in size-conditioned Bienaymé trees: Poisson approximation and declumping
- From Trees to Binary Trees: Approximation Algorithms and a PTAS
- Receiver-Surface Hit Patterns via Legendre Approximation for Molecular Signal Detection
- Constrained minimax approximation for quantum signal processing
- Graph neural networks for sampling-invariant embeddings of organized signal sets
BibTeX
@misc{elefante2026hpadaptive,
title = {{$hp$-adaptive trees for graph signal approximation}},
author = {Giacomo Elefante and Wolfgang Erb and Michael Multerer},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11701},
eprint = {2609.11701},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11701},
}
RIS
TY - UNPB
TI - hp-adaptive trees for graph signal approximation
AU - Giacomo Elefante
AU - Wolfgang Erb
AU - Michael Multerer
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2609.11701
UR - https://arxiv.org/abs/2609.11701
AB - 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.
ER -