Introduction
Graph Neural Networks (GNNs) have become the standard for learning on graph-structured data. However, their performance is often predicated on the assumption of homophily, where connected nodes share similar features or labels. In many real-world scenarios—such as protein-protein interactions or transaction networks—graphs exhibit heterophily, where edges connect dissimilar nodes. While Sheaf Neural Networks (SNNs) were introduced to address this by utilizing cellular sheaves to model complex relationships, they are notoriously sensitive to initialization and hyperparameter tuning. This paper introduces Bayesian Sheaf Neural Networks (BSNN), a framework that treats the underlying geometric structure of the graph as a latent random variable, providing a robust and principled approach to graph learning under uncertainty.
The Problem: Sensitivity in Sheaf Learning
Standard SNNs assign vector spaces to nodes and linear maps (restriction maps) to edges. This structure allows for more nuanced message passing than traditional GCNs, as the restriction maps can transform features as they move across the graph. However, in deterministic SNNs, these sheaves are typically learned as fixed functions of the input data. This leads to several challenges:
- Instability: Small changes in initialization or noise in the data can lead to vastly different learned sheaves.
- Hyperparameter Sensitivity: Achieving peak performance often requires exhaustive grid searches.
- Overfitting: On small datasets, deterministic sheaves can easily overfit to spurious correlations in the graph structure.
Methodology
BSNNs address these issues by placing a distribution over the sheaf itself. The core innovation lies in treating the sheaf Laplacian—the operator governing information flow—as a latent random variable.
1. Variational Sheaf Learner
Instead of a single set of restriction maps, the BSNN employs a Variational Sheaf Learner. An MLP maps node features to the parameters of a distribution over the sheaf. This allows the model to capture the uncertainty inherent in the graph's geometric structure.
2. The Cayley Distribution on $SO(n)$
A significant technical contribution of this work is the introduction of the Cayley distribution. To maintain expressive power, the authors focus on restriction maps within the special orthogonal group $SO(n)$. Modeling distributions on manifolds like $SO(n)$ is difficult because they must be "reparameterizable" to allow for gradient-based training via the backpropagation algorithm. By utilizing the Cayley transform, the authors define a family of distributions that allow for efficient sampling and tractable calculation of the Kullback-Leibler (KL) divergence.
3. Variational Inference
The model is trained by maximizing the Evidence Lower Bound (ELBO): $$\mathcal{L} = \mathbb{E}_{q(\mathcal{F}|X)}[\log p(Y|X, \mathcal{F})] - \text{KL}(q(\mathcal{F}|X) || p(\mathcal{F}))$$ where $\mathcal{F}$ represents the latent sheaf. The first term ensures the sampled sheaves accurately predict node labels, while the KL term regularizes the learned distribution against a prior.
Experimental Evaluation
The authors evaluated BSNN variants (General Linear, Invertible Diagonal, and Special Orthogonal) on the NSD benchmark, which spans seven datasets with varying homophily levels:
- Heterophilic: Texas, Wisconsin, Film, Cornell.
- Homophilic: Citeseer, Pubmed, Cora.
Key Results
- State-of-the-Art Performance: BSNNs consistently ranked in the top three across all benchmarks. Notably, on the Texas dataset, the General-BSNN achieved 88.11% accuracy, a significant jump from the deterministic SNN (82.97%) and standard GCN (55.14%).
- Separation Power: The authors provide theoretical and empirical evidence that sheaves using $SO(d)$ maps possess superior "linear separation power," allowing the model to distinguish between multiple classes even in low-dimensional spaces.
- Robustness and Calibration: BSNNs demonstrated a much lower standard deviation in performance across hyperparameter settings compared to deterministic models. Furthermore, the Expected Calibration Error (ECE) remained below 0.1 on homophilic datasets, indicating that the model's predicted probabilities are well-aligned with actual accuracy.
- Low-Data Resilience: In experiments where only 32% of nodes were used for training, the Bayesian approach significantly outperformed deterministic baselines, highlighting the effectiveness of uncertainty quantification as a regularizer.
Conclusion and Future Directions
Bayesian Sheaf Neural Networks provide a powerful framework for handling heterophily while mitigating the instability of traditional SNNs. By treating the graph's geometry as a latent variable, BSNNs offer improved robustness, better calibration, and superior performance in data-scarce environments.
Future work may expand this framework to handle dynamic topologies, where the graph edges themselves are treated as random variables. Additionally, the authors suggest exploring continuous-time evolution, where the sheaf Laplacian evolves as a stochastic process, potentially leading to new classes of diffusion-based graph models.
Summary updated