A Generative Model for Controllable Feature Heterophily in Graphs

Haoyu Wang, Renyuan Ma, Gonzalo Mateos, Luana RuizarXiv 2025 · DOI · arXiv

Abstract

Evaluating graph machine learning models requires synthetic datasets with precisely tunable properties. This paper presents a mathematically grounded generative framework for creating graphs and node features with controllable "feature heterophily." By integrating graphon-based graph generation with stationary graph signal filters, the authors establish theoretical guarantees for the convergence of empirical heterophily to predictable levels. We demonstrate that the resulting heterophily is primarily determined by the graphon's degree profile, providing a robust tool for benchmarking graph neural networks.

Introduction

The performance of Graph Neural Networks (GNNs) is intrinsically linked to the relationship between graph topology and node features, often characterized by homophily or heterophily. While benchmarking environments exist, they frequently lack the mathematical rigor needed to guarantee specific heterophily levels as graphs scale. This work addresses this gap by proposing a generative model based on limit theories, allowing for explicit control over feature heterophily.

Methodology

The proposed generative model follows a two-stage process:

  1. Graph Generation via Graphons: Graphs are sampled from a Lipschitz graphon, a continuous limit model for dense graphs (e.g., Erdos-Rényi or Stochastic Block Models).
  2. Feature Generation via Stationary Signals: Node features are produced by applying a linear shift-invariant graph filter—a polynomial of the rescaled graph Laplacian—to white Gaussian noise.

This approach allows for precise control over feature propagation by parameterizing the filter and selecting the appropriate graphon. The authors utilize matrix concentration inequalities and spectral convergence theorems to prove that the resulting feature heterophily behaves predictably.

Theoretical Insights

A key finding is that the limiting feature heterophily depends on the underlying graphon only through its degree profile (the expected degree of the nodes), rather than its full spectral structure. Furthermore, the authors prove that empirical heterophily scores concentrate tightly around a deterministic spectral quantity as the graph size increases, with the initial randomness of the noise features becoming negligible. Specifically, the deviation between the empirical score and its expected limit shrinks at a rate of $\mathcal{O}\left(\frac{(\log N)^{1+\epsilon}}{\sqrt{N}}\right)$.

Empirical Results

The theoretical claims are validated through extensive simulations using Erdos-Rényi (ER) and Stochastic Block Model (SBM) graphons paired with various polynomial filters. As shown in the figure below, the mean absolute error between empirical and theoretical heterophily values decreases significantly as the number of nodes $n$ increases, confirming the predicted convergence rates across different filter degrees.

Convergence of empirical heterophily to theoretical limits as the number of nodes increases for various filter degrees.

Conclusion and Limitations

While the framework provides a principled "knob" for benchmarking, it currently assumes a dense graph regime typical of graphon theory. Real-world networks are often sparse, which remains an area for future exploration. Nevertheless, this model offers a powerful tool for stress-testing modern GNN architectures under varying heterophily conditions by providing a mathematically guaranteed target for synthetic data generation.

Summary updated

BibTeX
@misc{wang2025generative,
  author = {Haoyu Wang and Renyuan Ma and Gonzalo Mateos and Luana Ruiz},
  title = {{A Generative Model for Controllable Feature Heterophily in Graphs}},
  year = {2025},
  eprint = {2509.23230},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.23230},
}
Figure