Markov clustering regularized multi-hop graph neural network.

• We analyze the limitations of directly applying the high-order multi-hop neighbors to graph neural networks, including computational inefficiency and limited representation ability of the multi-hop neighbor. • We propose a Markov Clustering Regularized Graph Neural Network (MCMGN) to overcome the limitations. By introducing iterative approximation and Regularized Markov Clustering strategies, the proposed model improves the performance of the multi-hop graph neural network for graph-level representation learning. • Extensive experimental results have verified the effectiveness of the proposed Markov Clustering Regularized Graph Neural Network for graph classification on eight graph benchmark datasets. • In this paper, we develop a Markov Clustering Regularized Multi-hop Graph Neural Network (MCMGN) to overcome the two limitations of higher-order multi-hop graph neural network, i.e., computational inefficiency and limited representation ability of multi-hop neighbor. We analyze the reasons of these two limitations in detail and give the corresponding solutions, i.e., iteration approximation and Markov Clustering regularized approaches, to achieve a excellent performance for graph-level representation learning. To evaluate the effectiveness of the proposed model, we carry out a series of experiments including the comparison with existing models, prune threshold comparison, impact of the number of iteration, impact of the normalization of node feature matrix, and computation cost comparison. Extensive experimental results strongly demonstrate the superiority of MCMGN in predictive performance for graph-level representation learning. [Display omitted] Graph Neural Networks (GNNs) have shown great potential for graph data analysis. In this paper, we focus on multi-hop graph neural networks and aim to extend existing models to a high-order multi-hop form for graph-level representation learning. However, such a directly extending method suffers from two limitations, i.e., computational inefficiency and limited representation ability of the multi-hop neighbor. For the former limitation, we utilize an iteration approach to approximate the power of a complex adjacency matrix to achieve linear computational complexity. For the latter limitation, we introduce the Regularized Markov Clustering (R-MCL) to regularize the flow matrix, i.e., the adjacency matrix, in each iteration step. With these two strategies, we construct Markov Clustering Regularized Multi-hop Graph Neural Network (MCMGN) for graph-level representation learning tasks. Specifically, MCMGN consists of a multi-hop message passing phase and a readout phase, where the multi-hop message passing phase aims to learn multi-hop node embedding, and then the readout phase aggregates multi-hop node representations to generate graph embedding for graph-level representation learning tasks. Extensive experiments on eight graph benchmark datasets strongly demonstrate the effectiveness of Markov Clustering Regularized Multi-hop Graph Neural Network, leading to superior performance on graph classification. [ABSTRACT FROM AUTHOR]