  Graph data augmentation has shown superiority in enhancing generalizability
and robustness of GNNs in graph-level classifications. However, existing
methods primarily focus on the augmentation in the graph signal space and the
graph structure space independently, neglecting the joint interaction between
them. In this paper, we address this limitation by formulating the problem as
an optimal transport problem that aims to find an optimal inter-graph node
matching strategy considering the interactions between graph structures and
signals. To solve this problem, we propose a novel graph mixup algorithm called
FGWMixup, which seeks a midpoint of source graphs in the Fused
Gromov-Wasserstein (FGW) metric space. To enhance the scalability of our
method, we introduce a relaxed FGW solver that accelerates FGWMixup by
improving the convergence rate from $\mathcal{O}(t^{-1})$ to
$\mathcal{O}(t^{-2})$. Extensive experiments conducted on five datasets using
both classic (MPNNs) and advanced (Graphormers) GNN backbones demonstrate that
FGWMixup effectively improves the generalizability and robustness of GNNs.
Codes are available at https://github.com/ArthurLeoM/FGWMixup.
