Most graph neural networks assume homophily, meaning that linked nodes tend to be alike, so averaging a node's features with its neighbors' is a sensible way to compute. Most provable sampling algorithms assume something structurally similar: log-concavity, meaning the target distribution's energy is a convex bowl with a single basin. The two assumptions fail together. Write a probability distribution over node representations whose energy rewards neighbors for being close. That energy is a quadratic built from the graph Laplacian, so the distribution is Gaussian and trivially log-concave. It is also exactly the homophily prior. To model heterophily, where linked nodes tend to differ, the energy must push some neighbors apart. The obvious way to do that, adding negative edge weights to the quadratic, makes the energy unbounded below. The distribution then cannot be normalized, and a Langevin sampler (gradient descent with injected noise) runs off to infinity.
This note proposes a specific design rule and tests it. Attraction between nodes may be quadratic, but repulsion must grow at most linearly. Under that rule the graph energy becomes a difference of convex functions that is still confining at infinity. The resulting distribution is non-log-concave and genuinely multimodal, since a node can sit "anywhere but next to its neighbor." It remains normalizable, and it can plausibly satisfy a log-Sobolev inequality, the functional inequality that gives Langevin methods polynomial mixing without convexity. The payoff is a heterophily-aware probabilistic graph model whose sampler has a stated condition for fast mixing, a "heterophily budget," instead of the unconstrained latent energies used today.
Core Claim
Let $z_v \in \mathbb{R}^d$ be the latent state of node $v$, let $f_\theta(x_v)$ be an encoder's output from its features, and let each edge carry a learned sign that splits the edges into attractive edges $E^+$ and repulsive edges $E^-$. We study
$$U(Z) = \sum_v \frac{\|z_v - f_\theta(x_v)\|^2}{2\sigma^2} + \alpha \sum_{(u,v)\in E^+} \|z_u - z_v\|^2 \;-\; \beta \sum_{(u,v)\in E^-} \|z_u - z_v\|,$$
where $\sigma$ sets the strength of the anchor to the features, $\alpha$ sets attraction, and $\beta$ sets repulsion. The first two terms are convex and together strongly convex. The last term is the negative of a convex, $\beta$-Lipschitz function. So $U$ has exactly the difference-of-convex form that DC-LA: Difference-of-Convex Langevin Algorithm handles: that algorithm smooths each convex piece with a Moreau envelope, moves the concave piece into an explicit gradient step, and requires "distant dissipativity." Because the repulsion grows only linearly, the quadratic anchor dominates at infinity and $U$ is dissipative. Near $z_u = z_v$ the repulsion creates a local maximum, which produces separated modes.
The claim has three parts. First, a quadratic signed energy of the kind implied by the signed messages in Two Sides of the Same Coin (GGCN, which uses signed cosine-similarity edge weights) is unnormalizable once repulsion exceeds the confinement. The sublinear version never is. Second, standard perturbation arguments give a log-Sobolev constant for $U$, but it degrades with the size of the gradient of the repulsive term. Taken naively over all $nd$ coordinates, that gradient grows with the number of nodes $n$. This is precisely the "LSI constant decays with dimension" failure flagged for Non-asymptotic Error Bounds … beyond Log-Concavity. The theoretical target is a local condition that yields a dimension-free constant: roughly, $\beta \sigma \cdot \deg^-(v)$ bounded for every node, where $\deg^-(v)$ is the node's number of repulsive edges. When that holds, that paper's $\tilde O(d^{1/2}\epsilon^{-1})$ iteration bound applies with a constant independent of graph size. Third, and empirically, the non-log-concave model beats its best log-concave counterpart where heterophily is diffuse, on both accuracy and calibration.
Research Program
The theory work proves normalizability and dissipativity for the sublinear-repulsion family. It then derives the log-Sobolev constant, first by the naive global perturbation argument and then under the per-node budget, and states exactly what the budget buys. We will say plainly if only the $n$-dependent bound can be proven. In that case the per-node condition becomes an empirical conjecture tested by measured mixing times.
A secondary result concerns cost. DC-LA lists proximal overhead as a limitation, but here the convex part is a quadratic whose proximal step is a sparse linear solve. The concave part's Moreau envelope, the smoothed version of the Euclidean norm, has a closed form. Each step therefore costs about the same as one message-passing layer plus a few conjugate-gradient iterations.
The modeling work makes the energy learnable. Edge signs come from a gate on feature similarity, in the spirit of GGCN. The repulsion strength $\beta$ is capped by the budget. The encoder and gates are trained end to end through short reparameterized sampling chains, with predictions averaged over posterior samples.
The role of prior work is as follows. Descent Steps of a Relation-Aware Energy (HALO) supplies the idea of deriving layers from a graph energy. We keep its compatibility-matrix quadratic as a log-concave special case and add noise and repulsion. Decoupled Graph Energy-based Model (DeGEM) motivates the work. It showed that energy propagation breaks under heterophily, and it runs Langevin sampling on an unconstrained neural latent energy with no mixing analysis. Our energy is structured and comes with a stated mixing condition. Neural Sheaf Diffusion and Bayesian Sheaf Neural Networks constrain the design and serve as competitors. The first achieves polarization deterministically. The second quantifies uncertainty variationally. Neither samples a Gibbs measure. Conditionally Strongly Log-Concave Generative Models is the alternative route to tractability: it recovers log-concavity by conditioning on coarse scales. We treat conditioning on predicted class assignments as a fallback if the budget proves too restrictive.
Baselines
The naive reference points are a graph-agnostic MLP and a standard GCN. The file reports GCN at 55.14% test accuracy on Texas (Bayesian Sheaf Neural Networks). Graph Neural Networks with Heterophily (CPGNN, which learns an explicit class compatibility matrix) shows that structured models beat MLPs by up to 30% under synthetic heterophily. Any gain we report must clear both.
The strongest accuracy-plus-calibration competitor is General-BSNN from Bayesian Sheaf Neural Networks. It reports 88.11% on Texas against 82.97% for the deterministic sheaf model, and expected calibration error below 0.1 on homophilic benchmarks. It is the most direct rival because it is also a probabilistic, heterophily-aware model. For deterministic accuracy we include GGCN, which reports the best average rank of 1.78 across nine datasets (Two Sides of the Same Coin), and ACM from Is Heterophily A Real Nightmare (node-wise mixing of low-pass, high-pass and identity channels).
For out-of-distribution detection, the strongest method is DeGEM, reported at +20.29% average AUROC over prior methods on heterophilic graphs. No absolute per-dataset AUROC for DeGEM is available on Lacuna, so we will rerun it under its released protocol.
All methods share the same splits, the same encoder width, and an equal hyperparameter search budget, measured in trials. For the samplers, all methods get equal wall-clock time. Beating BSNN means matching its Texas accuracy within noise while lowering calibration error on heterophilous datasets. Beating DeGEM means higher AUROC and lower FPR95, the false-positive rate at 95% true-positive rate, on the same heterophilic splits.
Two ablations isolate the key ingredient. The first is a log-concave twin: the HALO-style compatibility quadratic sampled exactly as a Gaussian, with an identical encoder. The second is the quadratic signed energy with diagonal loading, which adds a large enough constant to the diagonal to restore positive semi-definiteness. For the sampler itself, we compare DC-LA against unadjusted Langevin (plain noisy gradient steps) and MALA (the same with a Metropolis accept/reject correction) on the same energy.
Why not just…?
Why not just sample HALO's quadratic energy, which already handles heterophily through a compatibility matrix and is exactly Gaussian? This is the most serious threat, and it may win wherever heterophily is structured, meaning each class links predictably to another class. A Gaussian can only express "be near $H$ times my neighbor." When a node's neighbors spread across many classes, its posterior mean regresses toward an average of class centers that matches none of them. We will stratify test nodes by the entropy of their empirical compatibility row. If the log-concave twin matches us on high-entropy nodes, the non-log-concavity is unnecessary, and we will report that.
Why not just restore positive semi-definiteness in the signed quadratic by diagonal loading? It works, but only by making repulsion weaker than confinement everywhere. That caps how strongly any node can be pushed away. Linear repulsion can be strong near collision and negligible far away. The loaded-quadratic ablation measures what that difference is worth.
Why not just run DeGEM's latent Langevin sampler with longer chains? Longer chains do not help if the learned energy has high barriers. DC-LA shows plain unadjusted and proximal Langevin failing on difference-of-convex targets even in two dimensions. We will measure autocorrelation times of DeGEM's chains against ours at matched compute.
Why not just use deep ensembles or dropout on GGCN for uncertainty? This is a legitimate cheap competitor. We include a five-member GGCN ensemble at matched compute and compare calibration error and AUROC.
Proposed Experiments
On synthetic graphs with controlled heterophily and controlled compatibility-row entropy, we first run the divergence check. Langevin sampling on the quadratic signed energy should diverge once repulsion exceeds confinement, while the linear version stays bounded. We then sweep $\beta \sigma \cdot \max_v \deg^-(v)$ against graph size and measure integrated autocorrelation time under unadjusted Langevin, MALA and DC-LA. The decisive test is whether mixing time stays flat in $n$ below the budget and grows sharply above it. Flat mixing supports the local log-Sobolev conjecture. Growth with $n$ even below the budget falsifies it.
On Texas, Wisconsin, Cornell, Chameleon, Squirrel and Film, with Cora, CiteSeer and PubMed as homophilous controls and ogbn-Arxiv for scale, we report accuracy and expected calibration error against the baselines above, stratified by compatibility entropy. We then repeat DeGEM's out-of-distribution protocol, reporting AUROC and FPR95.
The central prediction is specific. The non-log-concave model should beat the log-concave twin mainly on high-entropy heterophilous nodes. It should tie on homophilous graphs, where the learned repulsive edges should nearly vanish.
References
- DC-LA: Difference-of-Convex Langevin Algorithm
- Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks
- Non-asymptotic Error Bounds in W2-Distance with Sqrt(d) Dimension Dependence and First Order Convergence for Langevin Monte Carlo beyond Log-Concavity
- Descent Steps of a Relation-Aware Energy Produce Heterogeneous Graph Neural Networks
- Decoupled Graph Energy-based Model for Node Out-of-Distribution Detection on Heterophilic Graphs
- Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs
- Bayesian Sheaf Neural Networks
- Conditionally Strongly Log-Concave Generative Models
- Graph Neural Networks with Heterophily
- Is Heterophily A Real Nightmare For Graph Neural Networks on Performing Node Classification?