  Graph neural networks (GNNs) are processing architectures that exploit graph
structural information to model representations from network data. Despite
their success, GNNs suffer from sub-optimal generalization performance given
limited training data, referred to as over-fitting. This paper proposes
Topology Adaptive Edge Dropping (TADropEdge) method as an adaptive data
augmentation technique to improve generalization performance and learn robust
GNN models. We start by explicitly analyzing how random edge dropping increases
the data diversity during training, while indicating i.i.d. edge dropping does
not account for graph structural information and could result in noisy
augmented data degrading performance. To overcome this issue, we consider graph
connectivity as the key property that captures graph topology. TADropEdge
incorporates this factor into random edge dropping such that the edge-dropped
subgraphs maintain similar topology as the underlying graph, yielding more
satisfactory data augmentation. In particular, TADropEdge first leverages the
graph spectrum to assign proper weights to graph edges, which represent their
criticality for establishing the graph connectivity. It then normalizes the
edge weights and drops graph edges adaptively based on their normalized
weights. Besides improving generalization performance, TADropEdge reduces
variance for efficient training and can be applied as a generic method modular
to different GNN models. Intensive experiments on real-life and synthetic
datasets corroborate theory and verify the effectiveness of the proposed
method.
