  Graph machine learning (GML) has made great progress in node classification,
link prediction, graph classification and so on. However, graphs in reality are
often structurally imbalanced, that is, only a few hub nodes have a denser
local structure and higher influence. The imbalance may compromise the
robustness of existing GML models, especially in learning tail nodes. This
paper proposes a selective graph augmentation method (SAug) to solve this
problem. Firstly, a Pagerank-based sampling strategy is designed to identify
hub nodes and tail nodes in the graph. Secondly, a selective augmentation
strategy is proposed, which drops the noisy neighbors of hub nodes on one side,
and discovers the latent neighbors and generates pseudo neighbors for tail
nodes on the other side. It can also alleviate the structural imbalance between
two types of nodes. Finally, a GNN model will be retrained on the augmented
graph. Extensive experiments demonstrate that SAug can significantly improve
the backbone GNNs and achieve superior performance to its competitors of graph
augmentation methods and hub/tail aware methods.
