Enhancing Real-World Complex Network Representations with Hyperedge
  Augmentation
Xiangyu Zhao Zehui Li Mingzhu Shen Guy-Bart Stan Pietro Liò Yiren Zhao
Graph augmentation methods play a crucial role in improving the performance
and enhancing generalisation capabilities in Graph Neural Networks (GNNs).
Existing graph augmentation methods mainly perturb the graph structures and are
usually limited to pairwise node relations. These methods cannot fully address
the complexities of real-world large-scale networks that often involve
higher-order node relations beyond only being pairwise. Meanwhile, real-world
graph datasets are predominantly modelled as simple graphs, due to the scarcity
of data that can be used to form higher-order edges. Therefore, reconfiguring
the higher-order edges as an integration into graph augmentation strategies
lights up a promising research path to address the aforementioned issues. In
this paper, we present Hyperedge Augmentation (HyperAug), a novel graph
augmentation method that constructs virtual hyperedges directly form the raw
data, and produces auxiliary node features by extracting from the virtual
hyperedge information, which are used for enhancing GNN performances on
downstream tasks. We design three diverse virtual hyperedge construction
strategies to accompany the augmentation scheme: (1) via graph statistics, (2)
from multiple data perspectives, and (3) utilising multi-modality. Furthermore,
to facilitate HyperAug evaluation, we provide 23 novel real-world graph
datasets across various domains including social media, biology, and
e-commerce. Our empirical study shows that HyperAug consistently and
significantly outperforms GNN baselines and other graph augmentation methods,
across a variety of application contexts, which clearly indicates that it can
effectively incorporate higher-order node relations into graph augmentation
methods for real-world complex networks.