Ruigang Zheng

Jianfei Li, Ruigang Zheng, Han Feng et al.

The nature of heterophilous graphs is significantly different from that of homophilous graphs, which causes difficulties in early graph neural network models and suggests aggregations beyond the 1-hop neighborhood. In this paper, we develop a new way to implement multi-scale extraction via constructing Haar-type graph framelets with desired properties of permutation equivariance, efficiency, and sparsity, for deep learning tasks on graphs. We further design a graph framelet neural network model PEGFAN (Permutation Equivariant Graph Framelet Augmented Network) based on our constructed graph framelets. The experiments are conducted on a synthetic dataset and 9 benchmark datasets to compare performance with other state-of-the-art models. The result shows that our model can achieve the best performance on certain datasets of heterophilous graphs (including the majority of heterophilous datasets with relatively larger sizes and denser connections) and competitive performance on the remaining.

Ruigang Zheng, Xiaosheng Zhuang

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.