$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.