mlsanityData to 7 Oct 2026

Edge Augmentation on Disconnected Graphs via Eigenvalue Elevation

arXiv 2207.05301 ↗First posted 12 Jul 2022cs.SI physics.data-an physics.soc-phcited by 0

Not on the map. Why?

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.

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

Builds on

11 of 39 references.

References · 11

  1. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 679
  2. 2015Diffusion-Convolutional Neural Networkscited by 268
  3. 2020Data Augmentation for Graph Neural Networkscited by 200
  4. 2017Cooperative Game Theory Approaches for Network Partitioningcited by 134
  5. 2022Data Augmentation for Deep Graph Learning: A Surveycited by 132
  6. 2018GEMSEC: Graph Embedding with Self Clusteringcited by 61
  7. 2022Graph Data Augmentation for Graph Machine Learning: A Surveycited by 61
  8. 2016The ground truth about metadata and community detection in networkscited by 42
  9. 2021Training Robust Graph Neural Networks with Topology Adaptive Edge Droppingcited by 20
  10. 2017Fluid Communities: A Competitive, Scalable and Diverse Community Detection Algorithmcited by 16
  11. 2019Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networkscited by 1

Built on by

Not cited yet.