Source-linked AI summary
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
TL;DR
Community-detection research lacks high-quality labeled datasets and flexible generators that represent varied structural and sub-community patterns. SynCo provides controllable synthetic generation, graph mimicking, and augmentation, with evaluations reporting stronger generation and augmentation performance while preserving dataset distributions.
Problem
Community detection is hindered by scarce ground-truth labels, reliance on classification datasets, and generators with limited control over degree distributions and sub-community structures.
Method
SynCo generates, mimics, and augments attributed graphs while controlling community sizes, sub-community structures, degree distributions, noise, and attributes.
Results
SynCo supports systematic evaluation under controlled structural and semantic complexity, with reported advantages in synthetic generation and data augmentation.
Takeaways & Limitations
SynCo offers a flexible framework for benchmarking attributed graph clustering and graph neural networks beyond fixed real-world datasets.
Takeaways & Limitations
Mimicking depends on an external community-detection partition, while rank-based attribute transfer limits feature-level generalization.
Abstract
from arXiv · showhide
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.
1. Introduction
Community-detection research is constrained by scarce labeled datasets and classification benchmarks that may lack community structure. SynCo addresses this gap with flexible generation, mimicking, and augmentation capabilities for attributed graphs.
- Scarce ground-truth community labels force researchers to use classification datasets as proxies, even when those datasets lack inherent community structure.
- SynCo generates attributed graphs with controllable cluster densities, node counts, edge distributions, and homogeneity.
- Its four-stage framework assigns communities, constructs edges, generates noise, and assigns attributes.
- SynCo can generate user-specified datasets, mimic existing graphs while preserving structural and attribute characteristics, and augment mimicked graphs.
- The evaluation covers parametric synthetic generation, scale-free analysis of mimicked data, and stress testing across ten node-clustering algorithms.
- The study evaluates synthetic benchmarking and dataset mimicking, highlighting SynCo’s potential to produce realistic and diverse attributed graphs.
2. Problem Statement and Related Works
Existing attributed graph generators support different structural, semantic, and augmentation goals but rarely model internal sub-community organization jointly with these properties. SynCo targets this limitation because local organization can distinguish graphs with otherwise similar global statistics.
- Prior methods span preferential-attachment, latent-factor, degree-preserving, homophilic, heterophilic, and learnability-oriented generation strategies.
- Most generators do not jointly support attributed generation, graph cloning, augmentation, heterophily control, degree preservation, and explicit sub-community modeling.
- Global degree distributions and community mixing may match while graphs still differ substantially in their internal community organization.
- Figure 1 compares a selected Cora community with generated counterparts, showing that conventional generators can reorganize localized dense regions and connectivity patterns.
- SynCo’s sub-community modeling is designed to retain finer-grained organization in mimicked graphs and create heterogeneous internal structures for controlled benchmarks.
3. Synthetic Community-Aware Attributed Graph Generator
SynCo is designed for fully synthetic generation, graph cloning, and controlled augmentation while addressing heterogeneous densities, degree distributions, and homophily or heterophily. Its unified pipeline combines community assignment, edge construction, topological noise, and attribute assignment.
- SynCo supports fully synthetic generation, structural graph cloning, and controlled augmentation of cloned graphs.
- The framework targets heterogeneous densities, specified degree distributions, and adjustable homophily or heterophily in sub-community graphs.
- Its unified pipeline sequentially performs community and sub-community assignment, edge construction, topological noise generation, and attribute assignment.
- Figure 1 presents mimicked graphs produced by different models for class label 5 of Cora.
3.1. SynCo generation from user-defined inputs
SynCo generates attributed graphs from user-defined community, sub-community, connectivity, degree, and attribute parameters. Its controls cover both intra-community organization and inter-community heterogeneity, while attribute generation balances community separation with topology.
- Input specification: SynCo accepts community sizes, sub-community distributions, interaction matrices, degree-distribution types, edge counts, and attribute parameters as user-defined inputs.The user-driven mode specifies target community structure, connectivity patterns, node degree characteristics, and attribute-generation controls.
- Node community and sub-community assignment: Each node is assigned exactly one community and one sub-community, providing the structural basis for controlled intra- and inter-sub-community connectivity.Community sizes determine community labels, while sub-community distributions determine finer-grained assignments.
- Edge construction: The generator controls topology through community-specific homogeneous edge counts, sub-community interaction matrices, and a global edge count 𝜌 that regulates inter-community connectivity.These mechanisms jointly control intra-community organization and inter-community heterogeneity.
- Degree distribution control: SynCo supports normal, power-law, and uniform degree distributions, enabling distinct structural roles such as core and border nodes.The degree-generating distribution is defined independently for each community or partition, supporting local structural variation.
- Attribute generation: Node attributes combine orthogonal community prototypes, Gaussian perturbations controlled by 𝛼feat, and topology-aware smoothing controlled by 𝛼topo.Smaller 𝛼feat values produce more compact feature clusters, while lower 𝛼topo values increase neighborhood influence.
3.2. SynCo for graph mimicking and augmentation
For graph mimicking, SynCo reconstructs community and sub-community topology from an existing attributed graph and transfers attributes using degree-ranked, label-conditional matching. The resulting design aims to preserve structural and semantic organization without relying on external distributions.
- Graph mimicking: SynCo mimics an attributed graph by preserving structural, community-level, and connectivity-homogeneity patterns while using the original graph’s degree distributions.The mimicked graph inherits community labels and reconstructs topology through community partitions and degree-weighted node selection.
- Edge reconstruction: Sub-community detection and interaction matrices guide edge construction, while heterogeneous edges are added until the synthetic graph reaches the original total edge count 𝜌.Homogeneous edges are constructed first, followed by cross-community edges sampled from the original inter-community interaction probabilities.
- Graph mimicking: SynCo’s topology is based on the original graph, and its absence of external distributions is described as supporting fidelity to that graph.This contrasts the mimicking procedure with GenCAT and SkyMAP as characterized in the supplied passage.
- Attribute assignment: Nodes are matched by identical degree rank within each community, aligning similar structural roles before transferring node attributes.The correspondence is label-conditional and topology-aware, connecting each original node to an analogous node in the mimicked graph.
- Attribute assignment: The rank-based transfer preserves within-community feature distributions and maintains semantic coherence between reconstructed topology and node attributes.The resulting graphs are intended for clustering, node classification, and graph representation learning.
3.3. Graph Augmentation Stage
SynCo augments mimicked graphs by sampling new nodes from empirical community and sub-community structures, initializing their attributes locally, and wiring them according to observed interaction and degree patterns.
- Augmentation objective: SynCo adds user-specified nodes while preserving empirical community proportions, sub-community structure, and degree-driven connectivity patterns.The augmentation target contains n′−|V| new nodes when n′ exceeds the original graph size.
- Community and sub-community assignment: New nodes are assigned to communities and sub-communities according to their empirical prevalence in the mimicked graph.Community sampling follows the observed label distribution, while partition sampling is proportional to partition sizes.
- Attribute initialization: Each added node receives the mean feature vector of its selected sub-community, preserving local attribute coherence.This initialization keeps new nodes compatible with the attribute geometry learned during mimicking.
- Edge formation: New-node degree is set from the average homogeneous-node degree of its source sub-community, and targets are sampled through sub-community interactions with degree-proportional attachment.The interaction matrix is updated after each newly created edge.
- Augmentation outcome: The complete augmentation procedure yields larger synthetic graphs that remain structurally and semantically consistent with the original network.It combines empirical community sampling, sub-community attribute statistics, and sub-community-level wiring.
4. Experiments and Experimental Setup
Experiments evaluate SynCo’s parameter control, graph generation under varying homophily and scale, clustering robustness, runtime, and dataset augmentation. Results show flexible feature and topology control, stable scaling behavior, heterophily-dependent clustering performance, and strong augmentation results relative to baselines.
- Ablation Study: SynCo’s parameters provide finer separability control at lower edge counts, while larger inter-community edge proportions support separable representations across a broader parameter region.At lower ρ, the clearest control region is 0.4 < αtopo < 0.8 and 0 < αfeat < 0.4; values near one can produce semantic noise.
- Effective Evaluation in different scenarios: Varying intra-community edge counts while fixing total edges shifts generated graphs from predominantly homophilous toward increasingly heterophilous structures.The experiment demonstrates explicit control over communities’ topological separability.
- Effective Evaluation in different scenarios: Increasing heterophilic edges generally decreased NMI, with topology- and optimization-based models declining more steeply than KL-Divergence and embedding-based models.The reported explanation is that topology-oriented methods rely more strongly on homophily and geometric network information.
- Effective Evaluation in different scenarios: Across increasing network sizes, clustering models generally maintained consistent performance, while SynCo generated networks preserving topological and semantic characteristics.The graph-size setup also assessed algorithmic performance and memory usage.
- Scale-Free Analysis: When considering all three augmentation scenarios jointly, SynCo outperformed the baseline algorithms overall on CiteSeer.For PubMed, classification consistency was lost only at 1.5× node growth, while SynCo preserved degree distributions more stably than GenCAT.
5. Discussion and Conclusion
SynCo provides fine-grained control over structural and semantic complexity in attributed graph generation, supporting both benchmarking and dataset replication. Experiments show interpretable difficulty manipulation, hyperparameter stress-testing, and more consistent structural preservation than baseline generators, while attribute transfer and sub-community recovery remain limitations.
- SynCo independently controls community sizes, sub-community structures, degree distributions, inter-community noise, and attribute generation mechanisms.
- By varying ρ, α_feat, and α_topo, SynCo enables progressive increases in task difficulty and analysis of clustering degradation under structural mixing and feature noise.
- DGCluster experiments show that hyperparameter sensitivity depends strongly on structural conditions, particularly at higher heterophily levels.
- SynCo preserves structural properties more consistently than baseline generators in graph mimicking and augmentation scenarios.
- SynCo’s mimicking stage depends on external community detection, while rank-based attribute transfer preserves structural roles but reduces feature-level generalization.
- SynCo supports benchmarking beyond DGCluster and offers a practical bridge between fully synthetic generation and structure-preserving dataset replication.