Data-Adaptive Graph Framelets with Generalized Vanishing Moments for Graph Machine Learning
This work addresses the challenge of graph learning, particularly for heterophilous graphs where connected nodes differ, by providing a novel feature generation method, though it appears incremental in its application to specific graph types.
The paper tackles the problem of constructing tight framelet systems on graphs for machine learning, introducing a framework that yields sparse coefficients and fast transforms, and demonstrates effectiveness in tasks like node classification for heterophilous graphs.
In this paper, 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 possesses ``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. Furthermore, we further exploit the generality of our proposed graph framelet systems for heterophilous graph learning, where graphs are characterized by connecting nodes mainly from different classes. The usual assumption that connected nodes are similar and belong to the same class for homophilious graphs 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 the graph learning ability of certain neural networks in node classification. We derive a specific system of graph framelets and propose a heuristic method to select framelets as features for neural network input. Several experiments demonstrate the effectiveness and superiority of our approach for non-linear approximation, denoising, and node classification.