Graph Wavelet-Based Multilevel Graph Coarsening and Its Application in Graph-CNN for Alzheimer’s Disease Detection

Abstract

Along with the classical applications like graph partitioning, graph visualization, etc., graph coarsening has been recently applied in graph convolutional neural network (GCNN) architectures to perform the pooling operation in the graph domain. In this paper, we propose a novel two-stage graph coarsening method rooted on the graph signal processing with its application in the GCNN architecture. In the first stage of coarsening, the graph wavelet transform (GWT) based features are used to obtain a coarsened graph which preserves the topological characteristics of the original graph. In the second stage, the coarsening problem is formulated as an optimization problem where the reduced Laplacian operator at each level is obtained as a restriction of the original Laplacian operator to a specified subspace that also maximizes the topological similarity. The performance of the proposed coarsening algorithm is quantified in the general coarsening context using different graph coarsening quality measures. Its effectiveness as a pooling operator in GCNN is validated by applying it for the graph coarsening operation in the GCNN architecture. This modified GCNN architecture is then used as a graph signal classifier for the early detection of Alzheimer's disease. The results show that the proposed coarsening method outperforms state-of-the-art methods, both in the general coarsening context and as a pooling operator in the GCNN architecture.

Keywords

• Graph coarsening
• graph signal processing
• convolutional neural network
• Alzheimer’s disease