Scalable Hierarchical Graph Generation via Soft Community Structure

Ahmet Tüzen; Helge Langseth; Kjetil Nørvåg

cs.LGOct 8, 2026

Scalable Hierarchical Graph Generation via Soft Community Structure

Authors: Ahmet Tüzen, Helge Langseth, Kjetil Nørvåg

Organizations: Department of Computer Science Norwegian University of Science and Technology

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.

Figures & tables

Figure 1: Overview of Schema . The reference graph is recursively decomposed into soft communities. Generation then proceeds in three stages: node features, intra-community edges, and inter-community edges through the bridge nodes.

Figure 2: Cluster tree construction. Leaf communities are contracted into supernodes, and Leiden is applied recursively to the supernode graph until a termination criterion is met. Here, the branching cap is $b=3$ .

Model	Citeseer				Cora ML
Model	Deg. W1	Tri. Rat.	Assort. Diff.	Inter/Intra	Deg. W1	Tri. Rat.	Assort. Diff.	Inter/Intra
Config	$0.007{\scriptscriptstyle\pm 0.002}$	$0.026{\scriptscriptstyle\pm 0.006}$	$0.059{\scriptscriptstyle\pm 0.011}$	$5.207{\scriptscriptstyle\pm 0.051}$	$0.047{\scriptscriptstyle\pm 0.004}$	$0.097{\scriptscriptstyle\pm 0.008}$	$0.048{\scriptscriptstyle\pm 0.005}$	$6.653{\scriptscriptstyle\pm 0.151}$
DC-SBM	$0.445{\scriptscriptstyle\pm 0.016}$	$0.467{\scriptscriptstyle\pm 0.039}$	$0.061{\scriptscriptstyle\pm 0.023}$	$0.993{\scriptscriptstyle\pm 0.099}$	$0.466{\scriptscriptstyle\pm 0.032}$	$0.382{\scriptscriptstyle\pm 0.011}$	$0.052{\scriptscriptstyle\pm 0.005}$	$0.969{\scriptscriptstyle\pm 0.054}$
GenCAT	$0.027{\scriptscriptstyle\pm 0.004}$	$0.093{\scriptscriptstyle\pm 0.011}$	$0.105{\scriptscriptstyle\pm 0.006}$	$3.022{\scriptscriptstyle\pm 0.194}$	$0.183{\scriptscriptstyle\pm 0.007}$	$0.245{\scriptscriptstyle\pm 0.014}$	$0.010{\scriptscriptstyle\pm 0.007}$	$1.826{\scriptscriptstyle\pm 0.177}$
NetGAN	$0.612{\scriptscriptstyle\pm 0.131}$	$1.024{\scriptscriptstyle\pm 0.084}$	$0.063{\scriptscriptstyle\pm 0.027}$	$1.472{\scriptscriptstyle\pm 0.549}$	$0.875{\scriptscriptstyle\pm 0.034}$	$0.489{\scriptscriptstyle\pm 0.060}$	$0.012{\scriptscriptstyle\pm 0.011}$	$1.810{\scriptscriptstyle\pm 0.425}$
CELL	$0.744{\scriptscriptstyle\pm 0.012}$	$0.088{\scriptscriptstyle\pm 0.008}$	$0.073{\scriptscriptstyle\pm 0.015}$	$3.370{\scriptscriptstyle\pm 0.071}$	$0.961{\scriptscriptstyle\pm 0.030}$	$0.403{\scriptscriptstyle\pm 0.016}$	$0.025{\scriptscriptstyle\pm 0.004}$	$2.436{\scriptscriptstyle\pm 0.108}$

Table 1: Structural fidelity. Results are given as the mean over 10 generated graphs with standard deviation.

Model	Citeseer			Cora ML			Amazon Photo			Amazon Computers
Model	EO	SO	NM	EO	SO	NM	EO	SO	NM	EO	SO	NM
Config	$0.003$	$0.002$	$0.001$	$0.007$	$0.008$	$0.003$	$0.017$	$0.016$	$0.007$	$0.019$	$0.017$	$0.006$
DC-SBM	$0.084$	$0.063$	$0.140$	$0.052$	$0.046$	$0.050$	$0.075$	$0.066$	$0.046$	$0.056$	$0.051$	$0.031$
GenCAT	$0.002$	$0.004$	$0.001$	$0.005$	$0.014$	$0.002$	$0.015$	$0.028$	$0.007$	$0.015$	$0.029$	$0.005$
NetGAN	$0.228$	$0.142$	$0.208$	$0.174$	$0.094$	$0.151$	$0.027$	$0.801$	$0.025$	OOM
CELL	$0.384$	$0.258$	$0.500$	$0.442$	$0.284$	$0.516$	$0.337$	$0.237$	$0.340$	$0.348$	$0.232$	$0.393$

Table 2: Memorization. Each result is the mean over 10 generated graphs. NetGAN runs on the largest connected component, not on the full graph.

Model	Citeseer				Cora ML
Model	Utility	TSTS-TRTR	Spearman $\rho$	Pearson $r$	Utility	TSTS-TRTR	Spearman $\rho$	Pearson $r$
GenCAT	$0.752{\scriptscriptstyle\pm 0.298}$	$0.017{\scriptscriptstyle\pm 0.119}$	$0.261{\scriptscriptstyle\pm 0.118}$	$0.682{\scriptscriptstyle\pm 0.087}$	$0.686{\scriptscriptstyle\pm 0.241}$	$-0.050{\scriptscriptstyle\pm 0.150}$	$0.527{\scriptscriptstyle\pm 0.114}$	$0.750{\scriptscriptstyle\pm 0.070}$
GraphMaker	$1.055{\scriptscriptstyle\pm 0.034}$	$0.135{\scriptscriptstyle\pm 0.025}$	$0.673{\scriptscriptstyle\pm 0.081}$	$0.854{\scriptscriptstyle\pm 0.071}$	$0.976{\scriptscriptstyle\pm 0.039}$	$0.086{\scriptscriptstyle\pm 0.009}$	$0.755{\scriptscriptstyle\pm 0.083}$	$0.974{\scriptscriptstyle\pm 0.061}$
SynGen	$0.251{\scriptscriptstyle\pm 0.064}$	$-0.503{\scriptscriptstyle\pm 0.009}$	$0.050{\scriptscriptstyle\pm 0.221}$	$0.176{\scriptscriptstyle\pm 0.278}$	$0.263{\scriptscriptstyle\pm 0.092}$	$-0.835{\scriptscriptstyle\pm 0.017}$	$0.019{\scriptscriptstyle\pm 0.268}$	$0.115{\scriptscriptstyle\pm 0.043}$
Schema	$0.861{\scriptscriptstyle\pm 0.076}$	$-0.132{\scriptscriptstyle\pm 0.037}$	$0.538{\scriptscriptstyle\pm 0.175}$	$0.853{\scriptscriptstyle\pm 0.095}$	$0.816{\scriptscriptstyle\pm 0.062}$	$-0.125{\scriptscriptstyle\pm 0.029}$	$0.492{\scriptscriptstyle\pm 0.107}$	$0.971{\scriptscriptstyle\pm 0.019}$
Model	Amazon Photo				Amazon Computers

Table 3: Downstream utility. Utility: TSTR to TRTR ratio, where 1 is ideal.

Figure 3: Runtime and peak memory usage of Schema per stage on the six scalability datasets.

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	$N$	$\|E\|$	Avg. deg.	# Con. Comp.	LCC	$F$	Feat. den.	$C$
Citeseer	3,327	4,552	2.74	438	63.7%	3,703	0.009	6
Cora ML	2,995	8,158	5.45	61	93.8%	2,879	0.018	7
Amazon Photo	7,650	119,081	31.13	136	97.9%	745	0.347	8
Amazon Computers	13,752	245,861	35.76	314	97.3%	767	0.348	10
Flickr	89,250	449,878	10.08	1	100%	500	0.464	7
Reddit	232,965	57,307,946	491.99	1	100%	602	1.000	41

Appendix

Table 4: Dataset statistics. # Con. Comp. is the number of connected components. LCC is the fraction of nodes in the largest connected component.

F

is the number of node attributes. Feat. den. is the fraction of non-zero entries in the attribute matrix.

C

is the number of classes.

Model	Deg. Rat.	Deg. W1	Tri. Rat.	Clus. C. Rat.	Assort. Diff.	Mod. Diff.	Inter/Intra	CPL Rat.
ER $G(n,p)$	$0.992{\scriptscriptstyle\pm 0.013}$	$0.834{\scriptscriptstyle\pm 0.018}$	$0.004{\scriptscriptstyle\pm 0.001}$	$0.008{\scriptscriptstyle\pm 0.003}$	$0.045{\scriptscriptstyle\pm 0.022}$	$0.194{\scriptscriptstyle\pm 0.004}$	$6.404{\scriptscriptstyle\pm 0.137}$	$0.852{\scriptscriptstyle\pm 0.010}$
ER $G(n,m)$	$1.000{\scriptscriptstyle\pm 0.000}$	$0.846{\scriptscriptstyle\pm 0.016}$	$0.004{\scriptscriptstyle\pm 0.002}$	$0.008{\scriptscriptstyle\pm 0.005}$	$0.041{\scriptscriptstyle\pm 0.007}$	$0.195{\scriptscriptstyle\pm 0.003}$	$6.409{\scriptscriptstyle\pm 0.102}$	$0.851{\scriptscriptstyle\pm 0.004}$
WS	$0.731{\scriptscriptstyle\pm 0.000}$	$1.415{\scriptscriptstyle\pm 0.012}$	$0.000{\scriptscriptstyle\pm 0.000}$	$0.001{\scriptscriptstyle\pm 0.002}$	$0.091{\scriptscriptstyle\pm 0.021}$	$0.072{\scriptscriptstyle\pm 0.001}$	$0.298{\scriptscriptstyle\pm 0.012}$	$14.745{\scriptscriptstyle\pm 5.090}$
BA	$0.731{\scriptscriptstyle\pm 0.000}$	$0.852{\scriptscriptstyle\pm 0.026}$	$0.000{\scriptscriptstyle\pm 0.000}$	$0.000{\scriptscriptstyle\pm 0.000}$	$0.137{\scriptscriptstyle\pm 0.015}$	$0.065{\scriptscriptstyle\pm 0.001}$	$0.344{\scriptscriptstyle\pm 0.017}$	$0.886{\scriptscriptstyle\pm 0.053}$
CL	$0.997{\scriptscriptstyle\pm 0.010}$	$0.441{\scriptscriptstyle\pm 0.018}$	$0.040{\scriptscriptstyle\pm 0.008}$	$0.035{\scriptscriptstyle\pm 0.006}$	$0.057{\scriptscriptstyle\pm 0.006}$	$0.285{\scriptscriptstyle\pm 0.004}$	$7.939{\scriptscriptstyle\pm 0.153}$	$0.577{\scriptscriptstyle\pm 0.007}$
Config	$0.997{\scriptscriptstyle\pm 0.001}$	$0.007{\scriptscriptstyle\pm 0.002}$	$0.026{\scriptscriptstyle\pm 0.006}$	$0.027{\scriptscriptstyle\pm 0.006}$	$0.059{\scriptscriptstyle\pm 0.011}$	$0.185{\scriptscriptstyle\pm 0.002}$	$5.207{\scriptscriptstyle\pm 0.051}$	$0.654{\scriptscriptstyle\pm 0.004}$

Appendix

Table 5: Citeseer structural fidelity results.

Model	Deg. Rat.	Deg. W1	Tri. Rat.	Clus. C. Rat.	Assort. Diff.	Mod. Diff.	Inter/Intra	CPL Rat.
ER $G(n,p)$	$0.994{\scriptscriptstyle\pm 0.010}$	$2.448{\scriptscriptstyle\pm 0.031}$	$0.004{\scriptscriptstyle\pm 0.001}$	$0.014{\scriptscriptstyle\pm 0.003}$	$0.067{\scriptscriptstyle\pm 0.010}$	$0.335{\scriptscriptstyle\pm 0.003}$	$7.241{\scriptscriptstyle\pm 0.086}$	$0.934{\scriptscriptstyle\pm 0.005}$
ER $G(n,m)$	$1.000{\scriptscriptstyle\pm 0.000}$	$2.459{\scriptscriptstyle\pm 0.026}$	$0.005{\scriptscriptstyle\pm 0.001}$	$0.015{\scriptscriptstyle\pm 0.002}$	$0.074{\scriptscriptstyle\pm 0.012}$	$0.336{\scriptscriptstyle\pm 0.001}$	$7.245{\scriptscriptstyle\pm 0.106}$	$0.932{\scriptscriptstyle\pm 0.001}$
WS	$0.734{\scriptscriptstyle\pm 0.000}$	$3.278{\scriptscriptstyle\pm 0.011}$	$0.413{\scriptscriptstyle\pm 0.009}$	$3.076{\scriptscriptstyle\pm 0.072}$	$0.049{\scriptscriptstyle\pm 0.019}$	$0.099{\scriptscriptstyle\pm 0.005}$	$0.800{\scriptscriptstyle\pm 0.043}$	$2.008{\scriptscriptstyle\pm 0.045}$
BA	$1.100{\scriptscriptstyle\pm 0.000}$	$1.078{\scriptscriptstyle\pm 0.052}$	$0.068{\scriptscriptstyle\pm 0.006}$	$0.067{\scriptscriptstyle\pm 0.005}$	$0.018{\scriptscriptstyle\pm 0.008}$	$0.364{\scriptscriptstyle\pm 0.002}$	$7.278{\scriptscriptstyle\pm 0.206}$	$0.734{\scriptscriptstyle\pm 0.002}$
CL	$1.002{\scriptscriptstyle\pm 0.015}$	$0.451{\scriptscriptstyle\pm 0.064}$	$0.147{\scriptscriptstyle\pm 0.009}$	$0.141{\scriptscriptstyle\pm 0.005}$	$0.053{\scriptscriptstyle\pm 0.005}$	$0.379{\scriptscriptstyle\pm 0.005}$	$7.431{\scriptscriptstyle\pm 0.141}$	$0.750{\scriptscriptstyle\pm 0.006}$
Config	$0.991{\scriptscriptstyle\pm 0.001}$	$0.047{\scriptscriptstyle\pm 0.004}$	$0.097{\scriptscriptstyle\pm 0.008}$	$0.104{\scriptscriptstyle\pm 0.009}$	$0.048{\scriptscriptstyle\pm 0.005}$	$0.342{\scriptscriptstyle\pm 0.002}$	$6.653{\scriptscriptstyle\pm 0.151}$	$0.790{\scriptscriptstyle\pm 0.003}$

Appendix

Table 6: Cora ML structural fidelity results.

Model	Deg. Rat.	Deg. W1	Tri. Rat.	Clus. C. Rat.	Assort. Diff.	Mod. Diff.	Inter/Intra	CPL Rat.
ER $G(n,p)$	$0.999{\scriptscriptstyle\pm 0.003}$	$18.734{\scriptscriptstyle\pm 0.055}$	$0.007{\scriptscriptstyle\pm 0.000}$	$0.023{\scriptscriptstyle\pm 0.000}$	$0.043{\scriptscriptstyle\pm 0.003}$	$0.576{\scriptscriptstyle\pm 0.002}$	$14.867{\scriptscriptstyle\pm 4.432}$	$0.716{\scriptscriptstyle\pm 0.000}$
ER $G(n,m)$	$1.000{\scriptscriptstyle\pm 0.000}$	$18.750{\scriptscriptstyle\pm 0.029}$	$0.007{\scriptscriptstyle\pm 0.000}$	$0.023{\scriptscriptstyle\pm 0.000}$	$0.045{\scriptscriptstyle\pm 0.004}$	$0.576{\scriptscriptstyle\pm 0.001}$	$15.704{\scriptscriptstyle\pm 3.271}$	$0.716{\scriptscriptstyle\pm 0.000}$
WS	$0.964{\scriptscriptstyle\pm 0.000}$	$21.240{\scriptscriptstyle\pm 0.014}$	$0.817{\scriptscriptstyle\pm 0.002}$	$2.968{\scriptscriptstyle\pm 0.008}$	$0.041{\scriptscriptstyle\pm 0.003}$	$0.104{\scriptscriptstyle\pm 0.001}$	$1.153{\scriptscriptstyle\pm 0.008}$	$0.899{\scriptscriptstyle\pm 0.001}$
BA	$1.026{\scriptscriptstyle\pm 0.000}$	$7.820{\scriptscriptstyle\pm 0.020}$	$0.067{\scriptscriptstyle\pm 0.001}$	$0.099{\scriptscriptstyle\pm 0.001}$	$0.034{\scriptscriptstyle\pm 0.003}$	$0.586{\scriptscriptstyle\pm 0.001}$	$19.438{\scriptscriptstyle\pm 1.753}$	$0.688{\scriptscriptstyle\pm 0.001}$
CL	$0.997{\scriptscriptstyle\pm 0.003}$	$0.593{\scriptscriptstyle\pm 0.052}$	$0.191{\scriptscriptstyle\pm 0.003}$	$0.195{\scriptscriptstyle\pm 0.002}$	$0.018{\scriptscriptstyle\pm 0.001}$	$0.597{\scriptscriptstyle\pm 0.001}$	$20.538{\scriptscriptstyle\pm 2.191}$	$0.698{\scriptscriptstyle\pm 0.001}$
Config	$0.981{\scriptscriptstyle\pm 0.000}$	$0.582{\scriptscriptstyle\pm 0.015}$	$0.137{\scriptscriptstyle\pm 0.001}$	$0.157{\scriptscriptstyle\pm 0.001}$	$0.010{\scriptscriptstyle\pm 0.001}$	$0.594{\scriptscriptstyle\pm 0.002}$	$20.407{\scriptscriptstyle\pm 1.599}$	$0.704{\scriptscriptstyle\pm 0.000}$

Appendix

Table 7: Amazon Photo structural fidelity results.

Model	Deg. Rat.	Deg. W1	Tri. Rat.	Clus. C. Rat.	Assort. Diff.	Mod. Diff.	Inter/Intra	CPL Rat.
ER $G(n,p)$	$1.000{\scriptscriptstyle\pm 0.002}$	$24.577{\scriptscriptstyle\pm 0.033}$	$0.005{\scriptscriptstyle\pm 0.000}$	$0.024{\scriptscriptstyle\pm 0.000}$	$0.056{\scriptscriptstyle\pm 0.002}$	$0.487{\scriptscriptstyle\pm 0.002}$	$11.048{\scriptscriptstyle\pm 1.701}$	$0.872{\scriptscriptstyle\pm 0.000}$
ER $G(n,m)$	$1.000{\scriptscriptstyle\pm 0.000}$	$24.562{\scriptscriptstyle\pm 0.022}$	$0.005{\scriptscriptstyle\pm 0.000}$	$0.024{\scriptscriptstyle\pm 0.000}$	$0.056{\scriptscriptstyle\pm 0.003}$	$0.487{\scriptscriptstyle\pm 0.001}$	$10.704{\scriptscriptstyle\pm 1.886}$	$0.872{\scriptscriptstyle\pm 0.000}$
WS	$1.007{\scriptscriptstyle\pm 0.000}$	$27.549{\scriptscriptstyle\pm 0.013}$	$1.005{\scriptscriptstyle\pm 0.002}$	$4.918{\scriptscriptstyle\pm 0.012}$	$0.053{\scriptscriptstyle\pm 0.001}$	$0.215{\scriptscriptstyle\pm 0.001}$	$0.611{\scriptscriptstyle\pm 0.008}$	$1.081{\scriptscriptstyle\pm 0.001}$
BA	$1.005{\scriptscriptstyle\pm 0.000}$	$11.047{\scriptscriptstyle\pm 0.020}$	$0.052{\scriptscriptstyle\pm 0.001}$	$0.113{\scriptscriptstyle\pm 0.001}$	$0.049{\scriptscriptstyle\pm 0.001}$	$0.494{\scriptscriptstyle\pm 0.001}$	$10.036{\scriptscriptstyle\pm 1.078}$	$0.839{\scriptscriptstyle\pm 0.000}$
CL	$0.996{\scriptscriptstyle\pm 0.002}$	$0.606{\scriptscriptstyle\pm 0.038}$	$0.287{\scriptscriptstyle\pm 0.002}$	$0.307{\scriptscriptstyle\pm 0.002}$	$0.016{\scriptscriptstyle\pm 0.001}$	$0.508{\scriptscriptstyle\pm 0.001}$	$11.379{\scriptscriptstyle\pm 0.784}$	$0.836{\scriptscriptstyle\pm 0.001}$
Config	$0.978{\scriptscriptstyle\pm 0.000}$	$0.797{\scriptscriptstyle\pm 0.006}$	$0.199{\scriptscriptstyle\pm 0.001}$	$0.246{\scriptscriptstyle\pm 0.001}$	$0.013{\scriptscriptstyle\pm 0.000}$	$0.506{\scriptscriptstyle\pm 0.001}$	$9.857{\scriptscriptstyle\pm 0.865}$	$0.843{\scriptscriptstyle\pm 0.001}$

Appendix

Table 8: Amazon Computers structural fidelity results.

Model	Deg. Rat.	Deg. W1	Tri. Rat.	Clus. C. Rat.	Assort. Diff.	Mod. Diff.	Inter/Intra	CPL Rat.
ER $G(n,p)$	$1.000{\scriptscriptstyle\pm 0.002}$	$5.127{\scriptscriptstyle\pm 0.014}$	$0.003{\scriptscriptstyle\pm 0.000}$	$0.029{\scriptscriptstyle\pm 0.002}$	$0.044{\scriptscriptstyle\pm 0.001}$	$0.248{\scriptscriptstyle\pm 0.002}$	$3.551{\scriptscriptstyle\pm 0.151}$	$1.221{\scriptscriptstyle\pm 0.001}$
ER $G(n,m)$	$1.000{\scriptscriptstyle\pm 0.000}$	$5.127{\scriptscriptstyle\pm 0.005}$	$0.003{\scriptscriptstyle\pm 0.000}$	$0.029{\scriptscriptstyle\pm 0.002}$	$0.044{\scriptscriptstyle\pm 0.002}$	$0.249{\scriptscriptstyle\pm 0.002}$	$3.549{\scriptscriptstyle\pm 0.196}$	$1.221{\scriptscriptstyle\pm 0.000}$
WS	$0.992{\scriptscriptstyle\pm 0.000}$	$6.020{\scriptscriptstyle\pm 0.002}$	$10.167{\scriptscriptstyle\pm 0.019}$	$122.913{\scriptscriptstyle\pm 0.231}$	$0.035{\scriptscriptstyle\pm 0.002}$	$0.353{\scriptscriptstyle\pm 0.000}$	$0.218{\scriptscriptstyle\pm 0.001}$	$1.815{\scriptscriptstyle\pm 0.003}$
BA	$0.992{\scriptscriptstyle\pm 0.000}$	$1.565{\scriptscriptstyle\pm 0.008}$	$0.063{\scriptscriptstyle\pm 0.003}$	$0.211{\scriptscriptstyle\pm 0.006}$	$0.030{\scriptscriptstyle\pm 0.001}$	$0.243{\scriptscriptstyle\pm 0.001}$	$2.468{\scriptscriptstyle\pm 0.139}$	$1.002{\scriptscriptstyle\pm 0.002}$
CL	$0.999{\scriptscriptstyle\pm 0.001}$	$1.004{\scriptscriptstyle\pm 0.008}$	$1.271{\scriptscriptstyle\pm 0.015}$	$1.313{\scriptscriptstyle\pm 0.017}$	$0.026{\scriptscriptstyle\pm 0.000}$	$0.252{\scriptscriptstyle\pm 0.001}$	$2.473{\scriptscriptstyle\pm 0.064}$	$0.897{\scriptscriptstyle\pm 0.001}$
Config	$0.996{\scriptscriptstyle\pm 0.000}$	$0.043{\scriptscriptstyle\pm 0.001}$	$0.877{\scriptscriptstyle\pm 0.009}$	$0.980{\scriptscriptstyle\pm 0.011}$	$0.023{\scriptscriptstyle\pm 0.000}$	$0.246{\scriptscriptstyle\pm 0.000}$	$2.403{\scriptscriptstyle\pm 0.032}$	$0.892{\scriptscriptstyle\pm 0.000}$

Appendix

Table 9: Flickr structural fidelity results.

Model	Alignment	Citeseer				Cora ML				Amazon Photo
Model	Alignment	EO	SO	NM	Frac.	EO	SO	NM	Frac.	EO	SO	NM	Frac.
CL	Degree	$0.003$	$0.003$	$0.001$	$0.000$	$0.007$	$0.009$	$0.003$	$0.000$	$0.019$	$0.020$	$0.007$	$0.000$
Config	Degree	$0.003$	$0.002$	$0.001$	$0.000$	$0.007$	$0.008$	$0.003$	$0.000$	$0.017$	$0.016$	$0.007$	$0.000$
GenCAT	Degree	$0.002$	$0.004$	$0.001$	$0.000$	$0.005$	$0.014$	$0.002$	$0.000$	$0.015$	$0.028$	$0.007$	$0.000$
DC-SBM	Node	$0.084$	$0.063$	$0.140$	$0.085$	$0.052$	$0.046$	$0.050$	$0.015$	$0.075$	$0.066$	$0.046$	$0.002$
GAE	Node	$0.227$	$0.750$	$0.125$	$0.017$	$0.191$	$0.749$	$0.106$	$0.004$	$0.174$	$0.743$	$0.075$	$0.000$

Appendix

Table 10: Structural memorization results. † NetGAN is trained and evaluated on the largest connected component, so its values are computed over a smaller node set than the other rows. EO is edge overlap, SO is self-overlap, and NM is neighborhood memorization. Frac. is the fraction of nodes with

J(v)\geq 0.9

Model	Feat. Type	Feat. Den.	Feat. $\rho$	NNDR	Leak	Feat. Type	Feat. Den.	Feat. $\rho$	NNDR	Leak
	Citeseer					Cora ML
Reference	binary	31.6	–	–	–	binary	50.5	–	–	–
GenCAT	cont.	–	0.298	$1.000$	$0.000^{\ast}$	cont.	–	0.082	$0.999$	$0.000^{\ast}$
GraphMaker S	binary	23.1	0.873	$1.000$	$0.012$	binary	33.8	0.922	$0.988$	$0.000$
GraphMaker A	binary	21.1	0.860	$1.000$	$0.273$	binary	26.1	0.898	$0.969$	$0.074$
SynGen	binary	1561.9	0.465	$1.000$	$0.000^{\ast}$	binary	1584.7	0.389	$0.999$	$0.000^{\ast}$

Appendix

Table 11: Attribute memorization. The first row of each block is the reference graph. Feat. Den. is the mean number of non-zero attributes per node for binary attributes and the mean L1 norm per node for continuous attributes; it is left empty where the generated attribute type differs from the reference, as the two quantities are then on different scales. Feat.

\rho

is the Spearman correlation between the column means of the generated and the reference attribute matrix. For binary attributes, the column mean is the frequency of the attribute. The reference row carries no Feat.

\rho

, NNDR, or Leak value, as all three are defined between a generated graph and the reference. ∗ Leak value not interpretable because the generated attribute marginals do not match the reference.

Model		Citeseer	Cora ML	A. Photo	A. Computers	Flickr
Majority class		0.21	0.30	0.27	0.37	0.42
Reference	TRTR	0.69	0.86	0.94	0.90	0.50
GenCAT	TSTR	0.52	0.59	0.44	0.38	0.42
	TSTS	0.71	0.81	0.72	0.41	0.42
GraphMaker S	TSTR	0.71	0.85	0.80	TO	OOM
	TSTS	0.62	0.83	0.99	TO	OOM

Appendix

Table 12: Absolute node classification accuracy, averaged over architectures and seeds. The majority-class rate is the accuracy of always predicting the most frequent class.

Dataset	Model	$h_{\mathrm{adj}}$	$\|E\|/\|E_{\mathrm{ref}}\|$	Feature-only
Citeseer	Reference	0.671	1.00	0.686
	Schema	0.512	1.00	0.529
	GraphMaker S	0.516	0.86	0.766
	GraphMaker A	0.870	4.28	0.810
Cora ML	Reference	0.749	1.00	0.798
	Schema	0.503	1.03	0.482

Appendix

Table 13: Properties of the reference and generated graphs.

h_{\mathrm{adj}}

: adjusted homophily. Feature-only: accuracy of a logistic regression trained on node attributes without edges.

			Ref. rewired to $h_{m}$		Gen. rewired
Dataset	Model	TSTS $-$ TRTR	$C_{\mathrm{ref}}(h_{m})-$ TRTR	TSTS $-C_{\mathrm{ref}}(h_{m})$	$C_{\mathrm{gen}}(h_{\mathrm{ref}})-$ TRTR
Citeseer	Schema	$-$ 0.069	$-$ 0.068	$-$ 0.001	$-$ 0.019
	GraphMaker S	$-$ 0.005	$-$ 0.067	+0.062	+0.070
	GraphMaker A	+0.126	+0.137	$-$ 0.011	+0.102
Cora ML	Schema	$-$ 0.129	$-$ 0.076	$-$ 0.053	+0.042
	GraphMaker S	$-$ 0.026	$-$ 0.028	+0.003	+0.029

Appendix

Table 14: Homophily calibration of TSTS. TSTS

-

TRTR is split into

C_{\mathrm{ref}}(h_{m})-\mathrm{TRTR}

, the change in accuracy when the reference is rewired to the model’s homophily

h_{m}

(Table 13 ), and the residual

\mathrm{TSTS}-C_{\mathrm{ref}}(h_{m})

C_{\mathrm{gen}}(h_{\mathrm{ref}})

: TSTS after rewiring the generated graph to the reference homophily

h_{\mathrm{ref}}

. TRTR is

0.744

on Citeseer,

0.857

on Cora ML, and

0.938

on Amazon Photo, each under a separate draw of the default split; on Citeseer, it differs from Table 12 , and so do the TSTS

-

TRTR values. Rewiring alone raises accuracy by

0.013

0.025

, so rewired differences smaller than that are not interpretable.

Model		Flickr	Reddit	Yelp	OGBN	DGraphFin	IGB
GenCAT	Fit	0.72 s	11.55 s	2.4 s §	20.34 s	2.23 s	30.92 s ∗
	Generate	36.78 s	33 m	24.44 m §	OOM	19.91 m	OOM
SynGen	Fit	14.03 s	12.47 s	261.33 s ‡	50.30 s	603.21 s	332.59 s
	Generate	5.68 s	24.92 s	18.38 s ‡	16.18 s	4.73 s	53.9 s
Schema	Clustering	8.2 s	423.3 s	261.9 s	151.86 m	214.0 s	31.91 m †
	Train	145.3 s	22.71 m	92.46 m	5.69 h	72.42 m	5.16 h †

Appendix

Table 15: Training and generation time on the scalability graphs, in seconds (s), minutes (m), and hours (h).

Scale	$N_{\text{exp}}$	$N_{\text{gen}}$	Edge rat. (gen)	Edge rat. (ref)
0.5	44,625	45,225	$1.040\pm 0.044$	$0.864\pm 0.036$
1	89,250	89,250	$1.000\pm 0.001$	$0.831\pm 0.001$
1.5	133,875	135,058	$0.992\pm 0.014$	$0.824\pm 0.012$
2	178,500	178,500	$0.987\pm 0.001$	$0.820\pm 0.001$
2.5	223,125	223,433	$0.985\pm 0.005$	$0.818\pm 0.004$
5	446,250	446,250	$0.992\pm 0.000$	$0.824\pm 0.000$

Appendix

Table 16: Generation at different scale factors on Flickr. Scale is the scale factor

s

N_{\text{exp}}

is the expected number of nodes, and

N_{\text{gen}}

is the generated number of nodes. Edge rat. (gen) is the number of generated edges divided by

s

times the edge count Schema generates at scale one. Edge rat. (ref) divides it by

s

times the reference edge count.

Noise			Structure			Memorization		Downstream
Node	Intra	Inter	Deg. W1	Tri. Rat.	Inter/Intra	EO	SO	TSTS $-$ TRTR
			$1.502$	$1.171$	$0.871$	$0.149$	n/a	$-0.080\pm 0.012$
✓			$0.590\pm 0.062$	$0.417\pm 0.051$	$0.837\pm 0.035$	$0.113$	$0.104$	$-0.118\pm 0.019$
	✓		$1.170\pm 0.013$	$0.095\pm 0.004$	$0.992\pm 0.060$	$0.112$	$0.105$	$-0.082\pm 0.013$
✓	✓		$1.177\pm 0.018$	$0.091\pm 0.005$	$0.986\pm 0.064$	$0.111$	$0.105$	$-0.126\pm 0.024$
		✓	$1.587\pm 0.045$	$1.360\pm 0.048$	$0.989\pm 0.028$	$0.074$	$0.183$	$-0.095\pm 0.013$

Appendix

Table 17: Stage-wise ablation on Cora ML. A check mark means the stage draws noise at generation. The last row is the configuration reported in the main text. SO is undefined in the first row, since all samples are identical without noise.

		Structure			Memorization		Downstream
Ablation	Setting	Deg. W1	Tri. Rat.	Inter/Intra	EO	SO	TSTS $-$ TRTR
Reported		$1.075\pm 0.024$	$0.275\pm 0.019$	$1.030\pm 0.083$	$0.038$	$0.066$	$-0.125\pm 0.029$
Partitioning	Louvain	$0.933\pm 0.037$	$0.277\pm 0.015$	$1.263\pm 0.088$	$0.037$	$0.061$	$-0.107\pm 0.021$
Partitioning	Random	$4.026\pm 0.034$	$3.515\pm 0.069$	$7.516\pm 0.472$	$0.017$	$0.170$	n/a
Assignment	Hard	$1.226\pm 0.026$	$0.208\pm 0.007$	$0.838\pm 0.048$	$0.033$	$0.044$	$-0.142\pm 0.027$
Branching cap	$b=2$	$1.365\pm 0.027$	$0.332\pm 0.015$	$0.946\pm 0.032$	$0.036$	$0.071$	$-0.127\pm 0.026$

Appendix

Table 18: Component ablations on Cora ML. Each row changes one part of the pipeline and leaves the rest at the reported configuration, given in the first row.

Explore similar work

SynCo: Synthetic Community-Aware Attributed Graph Generator for Graph Neural Network Benchmarking
Sep 9, 2026Guilherme Henrique Messias, Mariana Caravanti de Souza, Sylvia Iasulaitis +1Synthetic Data Augmentation Graph Generation
Federal University of São Carlos, São Carlos, São Paulo, Brazil · Federal University of Mato Grosso do Sul, Campo Grande, Mato Grosso do Sul, Brazil
Graph Data Augmentation via Contrastive Generator Inversion ( $\texttt{DCBA}$ )
Oct 5, 2026Mateusz Stolarski, Michał Czuba, Łukasz Kraiński +4Synthetic Data Augmentation Data Augmentation
Wrocław University of Science and Technology · University of Technology Sydney · SGH Warsaw School of Economics +1
Scaling Novel Graph Generation via Lightweight Structure-Guided Autoregressive Models
Jun 2, 2026Alessio Barboni, Massimiliano Lupo Pasini, Bishal Lakha +1Graph Generation Generative Modeling
Boise State University Boise, Idaho, USA · Oak Ridge National Laboratory Oak Ridge, Tennessee, USA

Sep 9, 2026, cs.SIJ/K move · Enter open · S save

SynCo: Synthetic Community-Aware Attributed Graph Generator for Graph Neural Network Benchmarking

Guilherme Henrique Messias, Mariana Caravanti de Souza, Sylvia Iasulaitis, Alan Demétrius Baria Valejo

Federal University of São Carlos, São Carlos, São Paulo, Brazil · Federal University of Mato Grosso do Sul, Campo Grande, Mato Grosso do Sul, Brazil

Synthetic Data Augmentation Graph Generation Synthetic Data Generation Synthetic Benchmark Generation

Open paper AskPDF arXiv

Graph Neural Networks (GNNs) are powerful models for handling attributed graphs in tasks such as classification, link prediction, and community detection, as they enable the aggregation of information from both structural and semantic sources. However, progress in community detection is hindered by the lack of high-quality datasets, since ground-truth community labels are often unavailable and most algorithms proposed in recent literature rely on the same benchmark datasets for model training and evaluation. To address this issue, attributed random graph generators are commonly employed to create synthetic graphs for assessing the strengths and limitations of GNN-based models. Nevertheless, most existing generators rely heavily on power-law degree distributions, despite recent evidence indicating that scale-free networks are rare, particularly in social network contexts. Moreover, state-of-the-art attributed graph generators provide limited flexibility, as they do not allow users to construct communities with varying densities, degree distributions, and sub-community structures. To overcome these limitations, we introduce the Synthetic Community-Aware Attributed Graph Generator (SynCo), a graph generation algorithm that allows users to control the node degree distribution and sub-community structure. We evaluate SynCo across three different tasks: graph mimicking, hyperparameter evaluation, and node clustering tuning. The results show that our model outperforms state-of-the-art approaches in synthetic graph generation and data augmentation, while preserving the original distributions of duplicated and augmented datasets, as confirmed by statistical tests well know in literature. We also demonstrate the ability of SynCo to generate nodes in large scale, up to 2.1 million nodes.

Abstract

Explore similar work

SynCo: Synthetic Community-Aware Attributed Graph Generator for Graph Neural Network Benchmarking

Graph Data Augmentation via Contrastive Generator Inversion (DCBA\texttt{DCBA}DCBA)

Scaling Novel Graph Generation via Lightweight Structure-Guided Autoregressive Models

Graph Data Augmentation via Contrastive Generator Inversion ( $\texttt{DCBA}$ )