A Hierarchical Poisson Generator for Universal Graphs under Limited Resources

Xiaorui Qi, Yanlong Wen, Xiaojie Yuan

Abstract

Graph generation is one of the most challenging tasks in recent years, and its core is to learn the ground truth distribution hiding in the training data. However, training data may not be available due to security concerns or unaffordable costs, which severely blows the learning models, especially the deep generative models. The dilemma leads us to rethink non-learned generation methods based on graph invariant features. Based on the observation of scale-free property, we propose a hierarchical Poisson graph generation algorithm. Specifically, we design a two-stage generation strategy. In the first stage, we sample multiple anchor nodes according to the Poisson distribution to further guide the formation of substructures, splitting the initial node set into multiple ones. Next, we progressively generate edges by sampling nodes through a degree mixing distribution, adjusting the tolerance towards exotic structures via two thresholds. We provide theoretical guarantees for hierarchical generation and verify the effectiveness of our method under 12 datasets of three categories. Experimental results show that our method fits the ground truth distribution better than various generation strategies and other distribution observations.

Introduction

The ability to generate realistic graphs is vital for simulating social interactions, modeling biological pathways, and designing new materials. In recent years, Deep Generative Models (DGMs) have set new benchmarks by learning high-dimensional distributions from large datasets. However, the success of DGMs is predicated on the availability of massive amounts of training data. In many real-world applications—such as sensitive medical records, proprietary financial networks, or emerging biological research—data is often scarce, expensive, or restricted due to privacy concerns.

The Challenge of Limited Data

When DGMs are deprived of sufficient training data, they lose their ability to map the underlying data distribution accurately. This often results in the generation of "messy" graphs that fail to preserve the structural properties of the target domain. This research addresses this bottleneck by shifting the focus from data-intensive learning to the utilization of "invariant features"—statistical properties like degree distribution and clustering coefficients that are universal across specific classes of networks.

Comparison of graph generation under limited data constraints.

Methodology: Hierarchical Poisson Generation

The authors propose a non-learned, hierarchical algorithm designed to replicate the "scale-free" nature of real-world networks, where a few "hub" nodes have many connections while most nodes have few. The generation process follows a two-stage strategy:

Stage 1: Anchor Node Sampling

Instead of a flat generation process, the model first identifies "anchor nodes." It employs a Poisson distribution to determine the expected degrees of these anchors. These nodes serve as the centers of star-shaped substructures, effectively partitioning the node set and establishing the skeleton of the network.

Stage 2: Progressive Edge Generation

The remaining edges are generated progressively using a "degree mixing distribution." This stage leverages the principle of preferential attachment—the "rich-get-richer" phenomenon where nodes with higher existing degrees are more likely to receive new connections. To ensure structural realism, the authors introduce two thresholds: $d_{max}$ to limit maximum node degrees and a truncation parameter $k$ to filter out low-probability exotic structures.

Comparison of our hierarchical method with classical graph generation models.

Experimental Evaluation

The proposed method was rigorously tested against 12 diverse datasets across three categories:

  • Bioinformatics: ENZYMES, MUTAG, NCI1, PROTEINS.
  • Social Networks: Deezer, IMDB-BINARY, IMDB-MULTI, REDDIT-BINARY.
  • Synthetic/Large-Scale: GRID, TREE, PPI, and Flickr.

Performance was evaluated using the Maximum Mean Discrepancy (MMD) metric across degree, clustering, and orbit counts.

Key Results and Insights

  • Superior Distribution Matching: The hierarchical Poisson generator consistently outperformed traditional models like Erdős-Rényi (ER), Barabási-Albert (BA), and Watts-Strogatz (WS) in matching real-world graph statistics.
  • Robustness Against Undertrained AI: In head-to-head comparisons with DGMs like GraphRNN and GraphILE, the proposed method produced significantly more realistic graphs when the AI models were restricted to limited training data.
  • Computational Efficiency: With a time complexity of $O(N^2)$, the algorithm is highly efficient. It can generate massive networks, such as the Flickr dataset, in seconds—tasks that often cause DGMs to fail due to memory or time constraints.

Conclusion and Future Work

This research demonstrates that for many graph generation tasks, leveraging universal statistical invariants is more effective than relying on data-hungry deep learning models, especially under resource constraints. While the current model is optimized for scale-free networks and may struggle with highly regular structures like 2D grids, it provides a robust foundation for universal graph generation. Future work will explore incorporating additional invariant features to broaden the model's applicability to a wider range of graph topologies.

Summary updated

Abstract

Graph generation is one of the most challenging tasks in recent years, and its core is to learn the ground truth distribution hiding in the training data. However, training data may not be available due to security concerns or unaffordable costs, which severely blows the learning models, especially the deep generative models. The dilemma leads us to rethink non-learned generation methods based on graph invariant features. Based on the observation of scale-free property, we propose a hierarchical Poisson graph generation algorithm. Specifically, we design a two-stage generation strategy. In the first stage, we sample multiple anchor nodes according to the Poisson distribution to further guide the formation of substructures, splitting the initial node set into multiple ones. Next, we progressively generate edges by sampling nodes through a degree mixing distribution, adjusting the tolerance towards exotic structures via two thresholds. We provide theoretical guarantees for hierarchical generation and verify the effectiveness of our method under 12 datasets of three categories. Experimental results show that our method fits the ground truth distribution better than various generation strategies and other distribution observations.
BibTeX
@misc{qi2024hierarchical,
  author = {Xiaorui Qi and Yanlong Wen and Xiaojie Yuan},
  title = {{A Hierarchical Poisson Generator for Universal Graphs under Limited Resources}},
  year = {2024},
  eprint = {2411.13888},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2411.13888},
}
Figure