Scalable method generates large graphs with realistic community structure
Scalable Hierarchical Graph Generation via Soft Community Structure
Machine LearningArtificial Intelligence
Summary
Creating big networks with lots of details is tough because you usually have only one big example to learn from. The authors introduce Schema, a way to break down a big network into smaller overlapping groups, then generate the network step-by-step using these groups. This method makes it easier to produce large realistic networks that keep important patterns without simply copying the original. Their method works well on real networks and scales up to networks with millions of nodes.
What this means in practice
- •For social network engineers: Generate synthetic large social networks with realistic communities for testing features without exposing real user data.
- •For telecom network planners: Create large-scale network models that reflect community-level connectivity to simulate and optimize infrastructure deployment.
Authors
Ahmet Tüzen, Helge Langseth, Kjetil Nørvåg
Abstract
Generating large attributed graphs requires reproducing the topology, generating attributes jointly with the structure, and remaining scalable. Many real-world graphs exist as a single large graph, so a generative model has to generalize from the one graph it is fit on, without independent samples. We present Schema, which recursively decomposes a reference graph into a hierarchy of soft communities, assigning each node a membership distribution. Generation is then split into three stages, each trained independently: (1) synthesizing node attributes conditioned on soft memberships, (2) generating intra-community edges from local structural context, and (3) modeling inter-community connections over bridge nodes whose membership mass is distributed across several communities. No stage forms the full adjacency matrix, and each stage operates on a subgraph bounded by the community size. We also introduce an evaluation protocol that covers structural fidelity, memorization, downstream utility, and scalability. On four real-world attributed graphs, Schema recovers the balance between local and long-range structure more closely than any other model that generates attributes, while reproducing only a small fraction of the reference edges. It retains the downstream accuracy of the reference graph without raising it artificially above that level. Baselines that match its structural fidelity memorize the reference, while those with higher downstream accuracy either exceed the reference accuracy or fail to complete on the larger graphs. We measure scalability on six additional graphs with up to 10 million nodes.