HOG-Diff: Higher-Order Guided Diffusion for Graph Generation

HOG-Diff is a principled graph generation framework that leverages a coarse-to-fine curriculum guided by higher-order topology and diffusion bridges to overcome the limitations of existing image-adapted models, achieving superior performance and scalability across diverse benchmarks.

The Gist

Imagine you are trying to teach a robot how to draw a complex city map from scratch.

The Old Way (Classical Diffusion):
Most current AI models try to do this by starting with a blank page covered in static noise (like TV snow) and slowly trying to "clean" the noise until a city appears. They look at the page one tiny dot at a time, asking, "Is this dot a street? Is it a building?"
The problem? They treat the city as just a collection of individual dots and lines. They often forget the big picture. They might draw a perfect street, but then realize it doesn't connect to a neighborhood, or they draw a building that has no roof. They miss the "soul" of the city—the way neighborhoods, parks, and districts are organized together.

The New Way (HOG-Diff):
The paper introduces a new method called HOG-Diff (Higher-order Guided Diffusion). Think of this as teaching the robot a better strategy: "Build the skeleton first, then add the flesh."

Here is how it works, using a few simple analogies:

1. The "Skeleton" vs. The "Flesh"

Instead of trying to draw every street and building at once, HOG-Diff starts by drawing the skeleton of the city.

• The Skeleton: These are the big, important shapes. In a city, this might be the main ring roads, the central park, or the layout of a specific neighborhood. In the paper's language, these are called "Higher-Order Structures" (like triangles, rings, or clusters).
• The Flesh: Once the skeleton is solid, the AI fills in the details: the side streets, the individual houses, and the tiny connections.

The Analogy: Imagine building a house.

• Old Method: You try to lay every single brick perfectly while hoping the roof eventually appears. You might end up with a pile of bricks that looks like a house but has no structure.
• HOG-Diff Method: You first build the frame (the beams and the roof structure). Once the frame is standing, you fill in the walls and windows. The house is guaranteed to stand up because the "skeleton" was built first.

2. The "Diffusion Bridge" (The Guided Path)

In the old method, the AI wanders blindly through the noise, hoping to stumble upon a good shape.
HOG-Diff uses something called a "Diffusion Bridge."

• The Analogy: Imagine you are hiking in thick fog.
  • Old Way: You walk randomly, hoping to find the trail. You might get lost or walk in circles.
  • HOG-Diff Way: You have a GPS that shows you the destination (the final city) and a map of the "skeleton" (the main roads). You don't just wander; you walk along a specific, guided path that ensures you stay on the main roads before you even think about the side streets.

3. Why "Higher-Order" Matters

The paper argues that real-world things (like molecules, social groups, or brain networks) aren't just random connections. They have groups.

• Example: In a molecule, atoms don't just connect in a line; they form rings (like a benzene ring). In a social network, people don't just have one-on-one chats; they form tight-knit groups (triangles of friends).
• The Problem: Old AI models often miss these groups. They might draw a ring of atoms that is chemically impossible.
• The HOG-Diff Solution: It explicitly looks for these "groups" (rings, triangles, clusters) and forces the AI to build those first. It says, "Okay, make sure you have a triangle here, and a ring there. Then connect the dots."

4. The Result: Better, Faster, and Smarter

Because HOG-Diff builds the "skeleton" first:

• It's more accurate: The generated molecules or graphs actually look like real ones because they have the right "shape" from the start.
• It's faster to learn: The AI doesn't have to guess the big picture; it just has to fill in the details. This makes the training process smoother and faster.
• It's more reliable: It avoids creating "nonsense" structures that look okay locally but fall apart globally.

Summary

HOG-Diff is like an architect who refuses to lay a single brick until the blueprints (the skeleton) are perfect. By focusing on the big, complex shapes (higher-order topology) first, it creates graphs, molecules, and networks that are not just random collections of dots, but coherent, realistic, and structurally sound systems. It turns a chaotic guessing game into a structured, step-by-step construction project.

Technical Summary

1. Problem Statement

Graph generation is a critical task for applications in drug discovery, material science, and network analysis. However, existing generative models face significant limitations:

• Pairwise Bias: Most current models treat graphs as mere collections of pairwise edges, ignoring higher-order topological structures (e.g., triangles, cliques, rings, motifs) that are fundamental to real-world systems like molecules and neural networks.
• Structural Collapse: Standard diffusion models often treat graphs as noisy adjacency matrices. This approach can lead to "oversmoothing" or the collapse of intermediate states into meaningless noise, failing to preserve the intrinsic hierarchical organization of complex systems.
• Lack of Guidance: Existing methods do not explicitly integrate higher-order topology as a guiding signal during the generative process, resulting in generated graphs that may lack valid chemical or structural properties.

2. Methodology: HOG-Diff

The authors propose HOG-Diff, a principled framework that employs a coarse-to-fine generation curriculum guided by higher-order topology. The core components are:

A. Coarse-to-Fine Curriculum via Cell Complex Filtering

Instead of generating edges directly, HOG-Diff decomposes the generation process into hierarchical stages:

1. Lifting: The input graph is lifted into a Cell Complex (CC), a topological space that generalizes graphs by including higher-dimensional cells (e.g., 2-cells representing faces or rings).
2. Filtering: A Cell Complex Filtering (CCF) operation is applied to extract a "skeleton" of the graph. This involves pruning nodes and edges that do not belong to specific higher-order cells (e.g., retaining only edges that form 2-cells).
3. Hierarchical Generation: The generation proceeds through $K$ time windows. It starts by synthesizing the coarse higher-order skeleton (the filtered graph) and progressively refines it into the full pairwise connectivity.

B. Generalized Ornstein-Uhlenbeck (GOU) Diffusion Bridge

To transition smoothly between these hierarchical states, HOG-Diff utilizes a Diffusion Bridge process:

• GOU Process: Unlike standard diffusion which moves from data to noise, the GOU process is a mean-reverting stochastic differential equation (SDE) that targets a specific terminal state.
• Doob's h-transform: The authors apply Doob's h-transform to the GOU process to create a GOU Bridge. This ensures the diffusion process is conditioned on a specific endpoint (the coarser graph structure from the previous stage), forcing the trajectory to pass through meaningful topological intermediates.
• Spectral Domain Implementation: To address permutation ambiguity and sparsity issues in adjacency matrices, the diffusion is performed in the Laplacian spectral domain. The model learns to denoise the eigenvalues ($\Lambda$) and eigenvectors ($U$) of the graph Laplacian rather than the raw adjacency matrix.

C. Score Network Architecture

The model employs a unified score network to estimate the gradient of the log-probability density (score function) for both node features and the spectrum:

• Dual-Stream Architecture: It combines a Graph Convolutional Network (GCN) for local feature aggregation and a Graph Transformer (ATTN) for global information extraction.
• FiLM Integration: Time information is injected via Feature-wise Linear Modulation (FiLM) layers.
• Outputs: The network predicts the score for the node features ($\nabla_X \log p$) and the spectrum ($\nabla_\Lambda \log p$).

3. Key Contributions

1. Novel Framework: Introduction of HOG-Diff, the first graph generative model to explicitly use higher-order topology (via cell complexes) as a guiding signal in a diffusion framework.
2. Theoretical Guarantees:
   • Faster Convergence: The authors prove that the coarse-to-fine curriculum leads to a smaller smoothness constant ($\beta$) in the loss landscape, implying faster convergence in score matching compared to classical diffusion.
   • Tighter Error Bounds: They derive a reconstruction error bound showing that HOG-Diff achieves a tighter bound than classical single-stage diffusion models.
3. Efficient Filtering: The proposal of Cell Complex Filtering (CCF) allows for the extraction of higher-order skeletons without the computational expense of enumerating all possible cells, making the method scalable.
4. Spectral Diffusion: Adapting the diffusion bridge to the spectral domain of the graph Laplacian to ensure permutation invariance and better signal-to-noise ratios.

4. Experimental Results

The method was evaluated on eight benchmarks across molecular and generic graph domains:

• Molecular Generation (QM9, ZINC250k, MOSES, GuacaMol):
  • HOG-Diff achieved State-of-the-Art (SOTA) performance on validity, uniqueness, and novelty.
  • It significantly outperformed baselines (e.g., GDSS, DiGress, GraphAF) on Fréchet ChemNet Distance (FCD) and NSPDK, indicating generated molecules are chemically and topologically closer to real data.
  • On the large-scale MOSES dataset, it achieved the lowest FCD score (0.94), demonstrating superior distribution learning.
• Generic Graph Generation (Community-small, Ego-small, Enzymes, SBM):
  • HOG-Diff consistently achieved the lowest Mean Maximum Discrepancy (MMD) across degree, clustering coefficient, and orbit counts.
• Topological Preservation:
  • Using Curvature Filtrations (Forman-Ricci and Ollivier-Ricci curvature), HOG-Diff showed the smallest distance to the ground truth distribution, proving it preserves higher-order geometric relations better than baselines.
• Ablation Studies:
  • Experiments confirmed that using Cell-based guides yields significantly better results than using random noise or peripheral structures as guides.
  • The spectral domain diffusion was shown to be more efficient and theoretically sound than adjacency matrix diffusion.

5. Significance

• Paradigm Shift: HOG-Diff moves graph generation from a purely edge-level denoising task to a structure-aware generative paradigm. It demonstrates that higher-order topology is not just a post-hoc property but a critical generative signal.
• Interpretability: By varying the guide structures, researchers can probe which topological motifs are most influential in determining the graph's properties, offering new avenues for interpretability in generative AI.
• Scalability: The method scales effectively to large datasets (e.g., MOSES with ~2M molecules) and large graphs, with the filtering step being a one-time preprocessing cost that does not hinder training or sampling speed.
• Foundation for Future Work: This work establishes a strong baseline for "Topological Deep Learning" in generative modeling, suggesting that future models for complex systems (biological, social, physical) must explicitly account for group interactions beyond pairwise edges.