# Spectral Graph Forge: Graph Generation Targeting Modularity

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jan 2018.

## Built on by (most cited first, 5 of 5)

- [SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators](https://mlsanity.com/paper/2204.01613/) (2022)
- [Theoretical analysis and computation of the sample Frechet mean for sets of large graphs based on spectral information](https://mlsanity.com/paper/2201.05923/) (2022)
- [Theoretical Insights into Line Graph Transformation on Graph Learning](https://mlsanity.com/paper/2410.16138/) (2024)
- [Cyclic Neural Network](https://mlsanity.com/paper/2402.03332/) (2024)
- [Approximate Fr'echet Mean for Data Sets of Sparse Graphs](https://mlsanity.com/paper/2105.04062/) (2021)

## Abstract (arXiv)

Community structure is an important property that captures inhomogeneities common in large networks, and modularity is one of the most widely used metrics for such community structure. In this paper, we introduce a principled methodology, the Spectral Graph Forge, for generating random graphs that preserves community structure from a real network of interest, in terms of modularity. Our approach leverages the fact that the spectral structure of matrix representations of a graph encodes global information about community structure. The Spectral Graph Forge uses a low-rank approximation of the modularity matrix to generate synthetic graphs that match a target modularity within user-selectable degree of accuracy, while allowing other aspects of structure to vary. We show that the Spectral Graph Forge outperforms state-of-the-art techniques in terms of accuracy in targeting the modularity and randomness of the realizations, while also preserving other local structural properties and node attributes. We discuss extensions of the Spectral Graph Forge to target other properties beyond modularity, and its applications to anonymization.