Decimated Framelet System and Fast $\gph$-Framelet Transforms on Graph

Graph representation learning has many real-world applications, from image processing, facial recognition, drug repurposing, social networks analysis to protein classification. For representation learning on graph, effective representation of graph data is crucial to learning performance. In this paper, we propose a new multiscale representation system for graph data --- decimated framelets. The framelets form a localized, tight framelet system on the graph via a data-driven filter bank. We establish discrete framelet transforms to decompose and reconstruct data on the graph under the decimated framelets. The graph framelets are built on a chain-based orthonormal basis which has fast graph Fourier transforms. From this, we then give a fast algorithm for the discrete framelet transforms on the graph --- {\fgt}, which has computational cost $\bigo{}{N\log N}$ for the graph with size $N$. Numerical examples verify the theory of decimated framelets and {\fgt}. Application to real-world examples, such as multiresolution analysis for traffic network, node classification by graph neural networks, illustrate that decimated framelets provide a useful graph data representation and {\fgt} is critical to improving computing performance.

This is joint work with Xuebin Zheng, Bingxin Zhou and Xiaosheng Zhuang.