Towards an Optimal Asymmetric Graph Structure for Robust Semi-supervised Node Classification

Graph Neural Networks (GNNs) have demonstrated great power for the semi-supervised node classification task. However, most GNN methods are sensitive to the noise of graph structures. Graph structure learning (GSL) is then introduced for robustification, which contains two major parts: recovering the optimal graph and fine-tuning the GNN parameters on this generated graph for the downstream task. Nonetheless, most of the existing GSL solutions merely focus on the node features during the first module for graph generation and exploit label information only by back-propagation during the second module for GNN training. They neglect the different roles that labeled and unlabeled nodes could play in GSL for the semi-supervised task, leading to a sub-optimal graph under this setting. In this paper, we give a precise definition on the optimality of the refined graph and provide the exact form of an optimal asymmetric graph structure designed explicitly for the semi-supervised node classification by distinguishing the different roles of labeled and unlabeled nodes through theoretical analysis. We propose a probabilistic model to infer the edge weights in this graph, which can be jointly trained with the subsequent node classification component. Extensive experimental results demonstrate the effectiveness of our method and the rationality of the optimal graph.