Model-Agnostic Augmentation for Accurate Graph Classification
  Given a graph dataset, how can we augment it for accurate graph
classification? Graph augmentation is an essential strategy to improve the
performance of graph-based tasks, and has been widely utilized for analyzing
web and social graphs. However, previous works for graph augmentation either a)
involve the target model in the process of augmentation, losing the
generalizability to other tasks, or b) rely on simple heuristics that lead to
unreliable results. In this work, we introduce five desired properties for
effective augmentation. Then, we propose NodeSam (Node Split and Merge) and
SubMix (Subgraph Mix), two model-agnostic approaches for graph augmentation
that satisfy all desired properties with different motivations. NodeSam makes a
balanced change of the graph structure to minimize the risk of semantic change,
while SubMix mixes random subgraphs of multiple graphs to create rich soft
labels combining the evidence for different classes. Our experiments on social
networks and molecular graphs show that NodeSam and SubMix outperform existing
approaches in graph classification.
