PaperlayerView exact revision on arXiv

Source-linked AI summary

$hp$-adaptive trees for graph signal approximation

Giacomo Elefante, Wolfgang Erb, Michael Multerer

arXiv:2609.11701v2eess.SPcs.NAmath.NA

TL;DR

Approximating graph signals requires partitionings that adapt to graph geometry and local signal regularity. The paper combines spatial refinement with higher-degree polynomial approximation, using knapsack selection, error-cost pruning, and local embeddings. Its experiments favor combining the two refinement strategies, including a 25.7% storage-cost reduction on the 3D MRI scan, compared with 15.5% for Binev’s construction.

  • Problem

    Graph-signal approximation needs methods that adapt to both graph geometry and local signal regularity, while pure partition refinement is limited to algebraic convergence rates.

    Source: §1.1 · p. 1, §3.1 · p. 7

  • Method

    The paper combines spatial h-refinement with higher-degree polynomial approximation, selecting refinements by a greedy knapsack criterion and pruning by error-cost trade-offs.

    Source: §4 · p. 7, §4.2 · p. 12, §7 · p. 22

  • Results

    25.7% reduction in combined storage costs on the 3D MRI scan for the combined methods, versus 15.5% for Binev’s hp-near-optimal construction.

    Source: §6 · p. 15

  • Takeaways & Limitations

    The experiments and conclusion support hp-adaptivity as an efficient approach to graph-signal approximation and compression, with the combined strategies especially favorable for reducing coefficients and tree size.

    Source: §7 · p. 22

    Polynomial p-adaptivity assumes the graph can be locally embedded in a domain where polynomial basis systems are available.

    Source: §4 · p. 7

Abstract

from arXiv · show

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.

1. Introduction

Graph-signal approximation needs partitions that adapt both to graph geometry and to local signal regularity. The paper extends partition-based methods with polynomial refinement, knapsack selection, error-cost pruning, and local embeddings.

1.1. Motivation.

  • Graph-signal approximation must adapt to both domain geometry and local signal regularity, while existing partition refinement is limited to algebraic convergence rates.The introduction motivates combining domain refinement with local polynomial-degree adaptation, especially for signals with heterogeneous regularity.Source: §1.1 · p. 1, §1.2 · p. 2

1.2. Literature review.

  • Partition-based methods build hierarchical graph decompositions and locally approximate signals; adaptive variants refine where local error is large, including graph wedgelets.The introduction contrasts these spatially localized methods with diffusion and spectral graph wavelets and.Source: §1.2 · pp. 1–2

1.3. Contributions.

  • The paper combines graph wedgelet partition trees with higher-degree polynomial refinement, using local Euclidean embeddings to construct polynomial spaces on general graphs.Its contributions include greedy profit-cost refinement as a binary knapsack problem and bottom-up error-cost pruning that replaces an h-approximation with a p-approximation when more efficient.Source: §1.3 · pp. 2–3

1.4. Outline.

  • The article develops BGP trees and wedgelets, analyzes greedy h-refinement, presents hp strategies and embeddings, and evaluates them on real-world and synthetic data.The introduction outlines Sections 2–7, ending with numerical tests and a conclusion.Source: §1.4 · p. 3

2. Binary Graph Partitioning Trees and Wedgelet Approximation

The section defines binary graph partitioning trees as hierarchical encodings of graph partitions and describes adaptive wedgelet approximation on those trees. Wedgelet refinements produce piecewise-constant approximations and geometric-wavelet details.

2.1. Binary graph partitioning trees

  • A BGP tree encodes recursive dyadic partitions of a graph’s vertex set as a full binary tree, whose leaves form the final partition.The framework assumes a simple undirected graph; a complete tree has all graph vertices as leaves.Source: §2 · pp. 3–4

2.2. Wedgelet approximation

  • Graph wedgelets adaptively split partition elements using the signal, selecting wedge splits to minimize the summed squared errors on the two resulting regions.The construction encodes wedge splits and partitions using graph center nodes.Source: §2 · p. 4
  • Wedgelet approximations are piecewise constant on tree partitions, while differences between consecutive partition levels can be represented by geometric wavelets.For best m-term geometric-wavelet approximation, the cited result gives algebraic L2-error decay with an exponent depending on the signal’s Besov-type smoothness class.Source: §2 · p. 4

3. Greedy h-refinements of partitioning trees

The section starts from a fixed BGP partition tree and refines its leaves using local approximation errors. Under stated error assumptions, repeatedly splitting the largest-error leaf yields a near-best h-adaptive approximation among trees with comparable leaf counts.

3. Greedy h-refinements of partitioning trees

  • Greedy h-refinement repeatedly splits the current leaf with the largest local approximation error, producing subtrees of a fixed initial BGP tree.The global error is the sum of local contributions over the leaves of the tree.Source: §3.1 · p. 4, §3 · p. 4

3.1. Near-best h-approximation

  • Under superadditivity and an even distribution of error between children, greedy largest-error refinement is near-best among h-adaptive trees with comparable leaf counts.The theorem’s guarantee applies to trees satisfying both assumptions on their local errors.Source: §3.1 · pp. 5–6
  • The even-error assumption excludes splits whose error is concentrated in one child, and wedgelet adaptivity does not guarantee balanced child errors.Consequently, the theory does not generally guarantee near-best performance for greedy wedgelet refinement, although the numerical tests suggest it often performs reasonably.Source: §3.1 · p. 7
  • Pure h-refinement remains limited to algebraic convergence rates, motivating hp-refinement that combines domain splits with adaptive local polynomial degrees.The paper presents this as motivation for the subsequent refinement strategies.Source: §3.1 · p. 7

4. hp -adaptivity strategies

The section combines partition refinement with local increases in polynomial degree to balance approximation error and cost. It presents a greedy knapsack strategy and a complementary expansion-and-pruning strategy for hp-adaptive trees.

4. hp -adaptivity strategies

  • hp-adaptivity combines h-refinement of the partition with local p-refinement, which can exploit smooth signal regions using higher-degree polynomials.The polynomial coefficient count depends on embedding dimension, and the approximation is formed by least-squares fits on tree leaves.Source: §4 · pp. 7–8

4.1. Greedy knapsack hp-adaptivity.

  • The greedy knapsack strategy selects admissible h- or p-refinements by error reduction per unit cost, subject to a refinement budget.Its h-refinement cost includes the added constant and partition cost; p-refinement cost reflects the increase in polynomial coefficients.Source: §4.1 · pp. 8–10
  • The greedy algorithm operates within a fixed reference tree that prescribes admissible splits and limits available refinements; it may stop before reaching tolerance if the tree is truncated.It iteratively performs the most efficient admissible refinement until tolerance is met or no further refinement is possible.Source: §4.1 · pp. 8, 10

4.2. Error-cost pruning.

  • In the ECP expansion phase, polynomial degree at an ancestor rises when its approximation uses fewer coefficients than the number of leaves beneath it.The subsequent bottom-up pruning removes subtrees when an ancestor approximation is at least as accurate as their combined leaf approximations.Source: §4.2 · p. 12
  • ECP pruning never increases approximation error or coefficient-storage cost relative to the expanded tree.The pruning step replaces a subtree only when the approximation at its ancestor is at least as accurate as the combined leaf approximations.Source: §4.2 · pp. 12–13
  • In the wedgelet framework, pruning can reduce storage of landmarks because a smaller leaf count requires fewer landmarks.ECP complements greedy knapsack selection: expansion can increase cost to reduce error, while pruning seeks a replacement with no greater error or cost.Source: §4.2 · p. 13

5. Polynomial function spaces for general graphs

The section constructs polynomial approximation spaces for general graphs using low-dimensional, patch-wise Euclidean embeddings. It explains how the patches and their coordinates support local polynomial approximation and affect refinement cost.

5. Polynomial function spaces for general graphs

  • Because a single low-distortion Euclidean embedding may not exist for a general graph, the method partitions it into disjoint local patches using graph partitioning algorithms such as METIS.When vertices sample an unknown manifold, the patches act like discrete local charts.Source: §5 · p. 13
  • Each patch receives a low-dimensional coordinate map, constructible with multidimensional scaling, ISOMAP, L-ISOMAP, t-SNE, or UMAP [29].These coordinates define the polynomial spaces used for p-refinement.Source: §5 · pp. 13–14
  • The patch embeddings induce polynomial functions, and a separate BGP tree is built on each patch to form a forest for graph-signal approximation.For a vertex v in patch U_r, the monomial function is given by the patch coordinate map ϕ_r(v).Source: §5 · p. 14
  • Choosing embedding dimension m much smaller than s can reduce polynomial approximation cost and mitigate the curse of dimensionality.Lower polynomial cost also improves p-refinement efficiency in the greedy knapsack approach and makes the ECP coefficient-versus-leaf bound easier to satisfy.Source: §5 · p. 14

6. Numerical Tests

Across the MRI, ERA5, RGB-image, and Swiss-roll tests, combined hp-refinement reduces storage more than Binev’s hp-near-optimal construction. The experiments compare approximation cost and tree leaves at a total error tolerance of 10^-4.

6. Numerical Tests

  • The experiments compare refinement steps separately and in combination across MRI, ERA5, an RGB image, and a Swiss-roll signal, using approximation cost and leaf count at total error tolerance 10^-4.The MRI and image trees use 13 uniform pre-partitioning levels, ERA5 uses 11, and each Swiss-roll patch uses 8.Source: §6 · pp. 14–15
  • 25.7% storage reduction on the 3D MRI scan exceeds the 15.5% gain from Binev’s hp-near-optimal construction.Table 1 compares the total number of polynomial coefficients and leaves for the 256 × 256 × 256 scan.Source: §6 · p. 15, Table 1 · p. 15
  • 19.0% storage reduction on ERA5 exceeds the 12.1% gain from Binev’s hp-near-optimal construction.The test signal is 2-meter temperature resampled at Fibonacci lattice points on the unit sphere.Source: §6 · p. 15, Table 2 · p. 16
  • 14.7% total storage reduction for the Tower of Belém image exceeds Binev’s 2.0% gain.Combined reductions are 14.4% (R), 15.3% (G), and 14.5% (B); individual knapsack reductions are 11.4% (R), 12.3% (G), and 11.6% (B), while ECP yields 9.4% (R), 9.5% (G), and 9.0% (B).Source: §6 · pp. 16–17, Table 3 · p. 18
  • 58.9% storage reduction on the Swiss-roll forest surpasses the 40.8% gain from Binev’s hp-near-optimal construction.For this smooth signal, ECP and Binev’s strategy select higher-degree polynomials whenever pruning is possible.Source: §6 · pp. 20–21, Figure 7 · p. 21

7. Conclusion

The conclusion presents hp-adaptivity as a way to combine geometric partitioning with local polynomial approximation for graph signals. Its experiments find that combining the greedy knapsack strategy with error-cost pruning gives the most favourable reductions in approximation complexity and storage.

7. Conclusion

  • The framework combines spatial h-refinement with local p-refinement to exploit both geometric and smoothness properties of signals.Source: §7 · pp. 21–22
  • The greedy knapsack criterion selects h- and p-refinements by efficiency, while error-cost pruning replaces refined subtrees with higher-order polynomial approximations when error and cost favour doing so.The two strategies can be applied independently, but their combination was most efficient in the experiments.Source: §7 · p. 22
  • Patch-wise local embeddings map graph neighbourhoods into low-dimensional Euclidean spaces to provide polynomial bases on general graphs and reduce the cost of high-dimensional bases.Source: §7 · p. 22
  • hp-adaptive wedgelet approximation substantially reduces complexity and storage requirements versus pure h-refinement, with the combined strategies most favourable for reducing polynomial coefficients and tree size.Fewer leaves also mean fewer landmarks to store for signal compression.Source: §7 · p. 22
  • The results support hp-adaptive strategies as an efficient framework for optimized approximation and compression of graph signals.Source: §7 · p. 22
Loading 2609.11701v2…