# AEGIS: Authentic Edge Growth In Sparsity for Link Prediction in Edge-Sparse Bipartite Knowledge Graphs

arXiv: https://arxiv.org/abs/2509.22017 · HTML: https://mlsanity.com/paper/2509.22017/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 24 references that are in the map.
- First posted on arXiv 26 Sep 2025.

## Builds on (most cited first, 9 of 9)

- [Image-based Recommendations on Styles and Substitutes](https://mlsanity.com/paper/1506.04757/) (2015)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [Graph Random Neural Network for Semi-Supervised Learning on Graphs](https://mlsanity.com/paper/2005.11079/) (2020)
- [GraphSMOTE: Imbalanced Node Classification on Graphs with Graph Neural Networks](https://mlsanity.com/paper/2103.08826/) (2021)
- [Data Augmentation for Deep Graph Learning: A Survey](https://mlsanity.com/paper/2202.08235/) (2022)
- [Learning from Counterfactual Links for Link Prediction](https://mlsanity.com/paper/2106.02172/) (2021)
- [Graph Data Augmentation for Graph Machine Learning: A Survey](https://mlsanity.com/paper/2202.08871/) (2022)
- [Data Augmentation on Graphs: A Technical Survey](https://mlsanity.com/paper/2212.09970/) (2022)
- [Data-Augmented Counterfactual Learning for Bundle Recommendation](https://mlsanity.com/paper/2210.10555/) (2022)

## Abstract (arXiv)

Bipartite knowledge graphs in niche domains are typically data-poor and edge-sparse, which hinders link prediction. We introduce AEGIS (Authentic Edge Growth In Sparsity), an edge-only augmentation framework that resamples existing training edges -either uniformly simple or with inverse-degree bias degree-aware -thereby preserving the original node set and sidestepping fabricated endpoints. To probe authenticity across regimes, we consider naturally sparse graphs (game design pattern's game-pattern network) and induce sparsity in denser benchmarks (Amazon, MovieLens) via high-rate bond percolation. We evaluate augmentations on two complementary metrics: AUC-ROC (higher is better) and the Brier score (lower is better), using two-tailed paired t-tests against sparse baselines. On Amazon and MovieLens, copy-based AEGIS variants match the baseline while the semantic KNN augmentation is the only method that restores AUC and calibration; random and synthetic edges remain detrimental. On the text-rich GDP graph, semantic KNN achieves the largest AUC improvement and Brier score reduction, and simple also lowers the Brier score relative to the sparse control. These findings position authenticity-constrained resampling as a data-efficient strategy for sparse bipartite link prediction, with semantic augmentation providing an additional boost when informative node descriptions are available.