Community-entropy Based Graph Structure Learning for Topology-imbalance

Abstract

Graph Structure Learning (GSL) recently has attracted considerable attentions. Existing GSL methods assume that nodes with high attribute similarity belong to the same class. However, our experiments have found that the performance of similarity-based GSL methods decreases in cases of topology-imbalance caused by uneven topology positions of labeled nodes. In imbalanced structures, nodes with intermediate similarity become a large number of uncertain nodes due to the inability or incorrect supervision signals. In this paper, we propose CE-GSL, a general community-entropy based GSL framework that connects uncertain nodes based on entropy measurement. Particularly, we design a unit community-entropy that maximizes embedded information content when neighbourhood attributes are fused to enhance the original graph. Then, we cluster the enhanced graphs to obtain community partitioning knowledge. Finally, we present a novel node pair sampling mechanism for restoring the graph structure via class-level and node-level community-entropy distribution. This sampling mechanism increases the connectivity among nodes with larger uncertainty within and between communities. CE-GSL is compatible with various Graph Neural Network (GNN) models and enhances supervision of uncertain nodes in imbalanced structures. Extensive experiments show significant improvements in the effectiveness of structure learning and node representation learning. Our code is available at https://github.com/Simba9257/CE-GSL.