Semi-Supervised Hierarchical Graph Classification

In this work, we study node classification in a hierarchical graph perspective which arises in many domains such as social network and document collection. In the hierarchical graph, each node is represented with one graph instance. We propose the Hierarchical Graph Mutual Information (HGMI) to model consistency among different levels of hierarchical graph and design two novel semi-supervised solutions named SEAL-C/AI for node labels are usually limited in node classification

Motivation

A node of a graph usually is linked with a real-world entity such as a user belong to a social network, or a document in one document citation network. It is novel and interesting to represent a node with graph instance which leads to a hierarchical graph perspective. However, there is a lack of theoretical guarantee and practical solution for the hierarchical graph setting.

Method

Here we propose the Hierarchical Graph Mutual Information (HGMI) to provide theoretical guarantee for modeling relation among different levels of hierarchical graph. Our key innovation is to formulate node classification in the setting of hierarchical graph into optimization problem based on mutual information. And we first prove that HGMI coincides with graph mutual information between graph instance input and final hierarchical graph node representation when the hierarchical graph forms a Markov chain. Figure 1 shows the overview of the proposed hierarchical graph mutual information computation, where G represents graph instance input, E represents graph instance embedding and Γ represents final hierarchical graph node feature.


Figure 1: Overview of the proposed HGMI framework

As the nodes lables in hierarchical graph are usually limited, we also introudce two semi-supervised ways called SEAL-AI and SEAL-CI to enlarge nodes labels based on the HGMI. Figure 2 shows the schematic diagram of the learning framework SEAL-CI.

Figure 2: Schematic diagram of the learning framework SEAL-CI

Key Results

We evaluate our SEAL-C/AI methods on various data including synthetic data, text data and social network data sets. Compared with existing methods, our methods obtain the state of the art performance. The following figures show our comparative results: Figure 3 shows the evaluatation results on QQ group dataset which is a socical network dataset. And we can see our methods SEAL-CI/AI outperform than the state of the art MIRACLE by at least 5%.


Figure 3: Comparison of different methods on Tencent QQ group data for semi-supervised graph classification.

Please refer to our paper for detailed explanations and more results.

Code and Datasets

We release SEAL on GitHub. The datasets are included in the code repository.

Contributors

Jia Li*
Yongfeng Huang*
Heng Chang
Yu Rong

References

Semi-Supervised Graph Classification: A Hierarchical Graph Perspective. Jia Li, Yu Rong, Hong Cheng, Helen Meng, Wenbing Huang, Junzhou Huang International World Wide Web Conferences (WWW), 2019.