A Generative Model for Controllable Feature Heterophily in Graphs
This work addresses the need for tunable mechanisms in graph learning methods for data modeling and generation, though it appears incremental as it builds on existing graphon and spectral theory.
The paper tackles the problem of controlling feature heterophily in graph signals by introducing a generative framework that combines a Lipschitz graphon-based random graph generator with Gaussian node features, establishing theoretical guarantees for concentration and convergence of heterophily measures. The result is validated through experiments showing precise control of homophily across graph families and spectral filters.
We introduce a principled generative framework for graph signals that enables explicit control of feature heterophily, a key property underlying the effectiveness of graph learning methods. Our model combines a Lipschitz graphon-based random graph generator with Gaussian node features filtered through a smooth spectral function of the rescaled Laplacian. We establish new theoretical guarantees: (i) a concentration result for the empirical heterophily score; and (ii) almost-sure convergence of the feature heterophily measure to a deterministic functional of the graphon degree profile, based on a graphon-limit law for polynomial averages of Laplacian eigenvalues. These results elucidate how the interplay between the graphon and the filter governs the limiting level of feature heterophily, providing a tunable mechanism for data modeling and generation. We validate the theory through experiments demonstrating precise control of homophily across graph families and spectral filters.