# Neighborhood Structure Configuration Models

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Oct 2022.

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

- [Residual Connections and Normalization Can Provably Prevent Oversmoothing in GNNs](https://mlsanity.com/paper/2406.02997/) (2024)
- [Edge Probability Graph Models Beyond Edge Independency: Concepts, Analyses, and Algorithms](https://mlsanity.com/paper/2405.16726/) (2024)
- [Caterpillar GNN: Replacing Message Passing with Efficient Aggregation](https://mlsanity.com/paper/2506.06784/) (2025)

## Abstract (arXiv)

We develop a new method to efficiently sample synthetic networks that preserve the d-hop neighborhood structure of a given network for any given d. The proposed algorithm trades off the diversity in network samples against the depth of the neighborhood structure that is preserved. Our key innovation is to employ a colored Configuration Model with colors derived from iterations of the so-called Color Refinement algorithm. We prove that with increasing iterations the preserved structural information increases: the generated synthetic networks and the original network become more and more similar, and are eventually indistinguishable in terms of centrality measures such as PageRank, HITS, Katz centrality and eigenvector centrality. Our work enables to efficiently generate samples with a precisely controlled similarity to the original network, especially for large networks.