Framelets on Spheres and Graphs: Nested Quadrature Rules and Parametric Systems

Abstract

Wavelet has been a paradigm notion in applied harmonic analysis for decades, with tremendous success and various applications across different fields. Due to the importance of sparsity, wavelets are usually replaced by a more common notion called framelets, i.e., frame wavelets, since sparsity is commonly related to redundancy in frames. One of the subsequent development of framelet is to extend the constructions to spaces other than the Euclidean ones, including manifolds and graphs. However, due to the differences between the Euclidean and non-Euclidean spaces, some of the key characteristics of framelet in the Euclidean spaces generally are absent or not as good in some of the state-of-the-art approaches, such as fast transforms with low memory footprint, coefficient/data sparsity, and flexibility in adapting target functions, which make such non-Euclidean framelets less desired in applications. This thesis aims to gather four works that address the aforementioned issue by improving state-of-the-art constructions. Specifically, the first and second works address the topic of nested quadrature rules that reduce storage and computation burden in spherical framelet transforms. On the other hand, the third work is a general parametric system, which allows flexible constructions of graph framelets and coefficient sparsity in data-adapting settings. Finally, the fourth work is a special realization of the parametric system, which improves the performance of node classification on heterophilous graphs. The content is summarized as follows:

1. Using spherical designs for nested quadrature rules, we prove the existence of a spherical t-design formed by adding extra points to an arbitrarily given point set on the sphere and deduce the existence of nested spherical designs. Estimates on the number of required points are also given. For the case that the given point set is a spherical t₁-design such that t₁ < t and the number of points is of optimal order (t₁)^d, we show that the upper bound of the total number of extra points and given points for forming nested spherical t-design is of order t^2d+1. A brief discussion concerning the optimal order in nested spherical designs is also given.

2. Compared with spherical designs, adopting uniformly sampled points for nested quadrature rules is a more viable option despite being less memory-efficient. Based on probabilistic quantities related to the measure and the diameter of Voronoi cells, we provide concrete probability estimates on the existence of exact quadrature rules for spherical harmonics with degrees up to t on the d-dimensional sphere using uniformly sampled points with bounded weights. We further investigate the problem of setting the numbers of points to be of order t^d. A simple analysis based on our estimates suggests that the constant in the order can not be fixed for all t and should increase as t increases. This is empirically verified in our experiments.

3. We propose a general framework for constructing tight framelet systems on graphs with localized supports based on partition trees. Our construction of framelets provides a simple and efficient way to obtain the orthogonality with k arbitrary orthonormal vectors. When the k vectors contain most of the energy of a family of graph signals, the orthogonality of the framelets intuitively possess "generalized (k-)vanishing'' moments, and thus, the coefficients are sparse. Moreover, our construction provides not only framelets that are overall sparse vectors but also fast and schematically concise transforms. In a data-adaptive setting, the graph framelet systems can be learned by conducting optimizations on Stiefel manifolds to provide the utmost sparsity for a given family of graph signals. Experimental results show that our learned graph framelet systems perform superiorly in non-linear approximation and denoising tasks.

4. Heterophilous graphs are characterized by connecting nodes mainly from different classes. The usual assumption that connected nodes are similar in class is contradictory for heterophilous graphs. Thus, we are motivated to bypass simple assumptions on heterophilous graphs and focus on generating rich node features induced by the graph structure, so as to improve learning in node classification. We propose a specific system of graph framelets and a heuristic method to select framelets as features for neural network input. Several experiments demonstrate the effectiveness of our approach for node classification.

Date of Award	2 Jul 2025
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Xiaosheng ZHUANG (Supervisor)