# Edge Augmentation on Disconnected Graphs via Eigenvalue Elevation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 39 references that are in the map.
- First posted on arXiv 12 Jul 2022.

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

- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [Diffusion-Convolutional Neural Networks](https://mlsanity.com/paper/1511.02136/) (2015)
- [Data Augmentation for Graph Neural Networks](https://mlsanity.com/paper/2006.06830/) (2020)
- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [Data Augmentation for Deep Graph Learning: A Survey](https://mlsanity.com/paper/2202.08235/) (2022)
- [Graph Data Augmentation for Graph Machine Learning: A Survey](https://mlsanity.com/paper/2202.08871/) (2022)
- [GEMSEC: Graph Embedding with Self Clustering](https://mlsanity.com/paper/1802.03997/) (2018)
- [The ground truth about metadata and community detection in networks](https://mlsanity.com/paper/1608.05878/) (2016)
- [Training Robust Graph Neural Networks with Topology Adaptive Edge Dropping](https://mlsanity.com/paper/2106.02892/) (2021)
- [Fluid Communities: A Competitive, Scalable and Diverse Community Detection Algorithm](https://mlsanity.com/paper/1703.09307/) (2017)
- [Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networks](https://mlsanity.com/paper/1912.02903/) (2019)

## Abstract (arXiv)

The graph-theoretical task of determining most likely inter-community edges based on disconnected subgraphs' intra-community connectivity is proposed. An algorithm is developed for this edge augmentation task, based on elevating the zero eigenvalues of graph's spectrum. Upper bounds for eigenvalue elevation amplitude and for the corresponding augmented edge density are derived and are authenticated with simulation on random graphs. The algorithm works consistently across synthetic and real networks, yielding desirable performance at connecting graph components. Edge augmentation reverse-engineers graph partition under different community detection methods (Girvan-Newman method, greedy modularity maximization, label propagation, Louvain method, and fluid community), in most cases producing inter-community edges at >50% frequency.