Clustering-based techniques for compression of graph signals via geometric graph wedgelets

The graph data structure, while extremely flexible, presents several computational challenges in the context of deep learning architectures due to its variable dimension and relational structure, and thus requires some mathematical device to convert such a free-form structure to a standardised, fixed-size one. This work explores the use of graph wavelets and binary graph partitioning trees, a special case of a more general discrete approximation framework, as a way to express any graph signal as a sum of simple, pre-defined functions. More specifically, it focuses on a partitioning strategy driven by the choice of nodes within a partition and splits based on graph distance: this greedy technique, formalised in terms of binary wedge partitioning trees, can be enriched by leveraging topological properties of the vertices as scores to be used for choosing the next split. After giving the necessary theoretical results, the algorithm is tested against RGB-encoded images and single-channel signals on both synthetic and real graphs.