In this research, we proposed an effective and explainable graph vertex classification method, called GraphHop. Unlike the graph convolutional network (GCN) that is based on the end-to-end optimization, the GraphHop method generates an effective feature set for each vertex in an unsupervised and feedforward manner. GraphHop determines the local-to-global attributes of each vertex through successive one-hop information exchange, called the GraphHop unit. The GraphHop method is mathematically transparent. It can be explained using the recently developed “successive subspace learning (SSL)” framework [1, 2], which is mathematically transparent. Unlike GCN that is based on the end-to-end optimization of an objective function using back propagation, GraphHop generates an effective feature set for each vertex in an unsupervised and feedforward manner. Since no backpropagation is required in the feature learning process, the training complexity of GraphHop is significantly lower. By following the traditional pattern recognition paradigm, the GraphHop method decouples the feature extraction task and the classification task into two separate modules, where the feature extraction module is completely un-supervised. In the feature extraction module, GraphHop determines the local-to-global attributes of each vertex through successive one-hop information exchange, called the GraphHop unit. To control the rapid increase of the dimension of vertex attributes, the Saab transform is adopted for dimension reduction inside the GraphHop unit. Multiple Graph-Hop units are cascaded to obtain the higher order proximity information of a vertex. In the classification module, vertex attributes of multiple GraphHop units are extracted and ensembled for the classification task. There are many machine learning tools to be considered. In the experiments, we choose the random forest classifier because of its good performance and low complexity. To demonstrate the effectiveness of the GraphHop method, we apply it to three real-world citation datasets in the experimental section, and show that it offers state-of-the-art performance at much lower training complexity.
– by Jessica Chen
[1] Y. Chen and C.-C. J. Kuo, “Pixelhop: A successive subspace learning (SSL) method for object recognition,” Journal of Visual Communication and Image Representation, p. 102749, 2020.
[2] M. Zhang, H. You, P. Kadam, S. Liu, and C.-C. J. Kuo, “Pointhop: An explainable machine learning method