Authors: Luke Braithwaite, Alessio Borgi, Gabriele Onorato, Kristjan Tarantelli, Francesco Restuccia, Fabrizio Silvestri, Pietro Liò
Organizations: Department of Computer Science and Technology, University of Cambridge · Department of Computer, Control and Management Engineering, Sapienza University of Rome · Department of Electrical and Computer Engineering, Northeastern University
Heterogeneous graphs, whose nodes and edges can belong to different types and feature spaces, arise in many real-world domains, including biology, recommendation, social networks, and computer systems. Existing heterogeneous graph neural networks typically handle this heterogeneity at the architectural level through relation-specific modules, meta-path machinery or type-aware attention, which often leads to increasingly specialised parameter-heavy designs. In this work, we propose HetSheaf, a framework for learning heterogeneous graphs through cellular sheaves. Instead of encoding heterogeneity solely in the architecture, HetSheaf represents it directly in the underlying data structure by assigning type-aware local feature spaces and learning restriction maps conditioned on node features, node types, and edge types. To support graph-level prediction, we further introduce SheafPool, a universal stalk-space readout that aggregates node representations while being invariant to local changes of basis, thereby making graph classification with sheaf networks well-defined and achieving an F1 Score up to 42 percentage points higher than mean pooling. Across a diverse suite of benchmarks (node classification, link prediction and graph classification). HetSheaf consistently achieves up to 2 percentage points higher performance (up to 94.97% Macro F1 Score on node classification and up to 99.62% on link prediction) on the Heterogeneous Graph Benchmark (HGB) framework against homogeneous (GCN, GAT, GIN, GraphSAGE), heterogeneous (R-GCN, HAT, HGT) and type-agnostic sheaf baselines, while reducing the number of parameters by up to 10×.
Figures & tables
Figure 1
Figure 1: Heterogeneous Sheaf Predictors. For an edge e=(u,v) , ϕ(u) and ϕ(v) denote node types, ψ(e) denotes the edge type, xu,xv are the raw node features, projected in the shared channel via z∗=Pϕ(∗)(x∗) . ∥ denotes concatenation, and MLPψ(e) denotes a separate MLP for each edge type.
Figure 2: The SheafPool Architecture. Our readout processes node stalk embeddings in five steps. (1) Per-node Whitening removes GL(d) scaling and shearing. (2) Anchor Alignment resolves residual O(d) rotations. (3) Attention Weights are computed via stalk energies. (4) Stalk Pooling aggregates into a Late Receive-only Token without altering message passing. (5) Feature Extraction collapses the stalk dimension, yielding a permutation- and gauge-invariant graph embedding.
ACM
DBLP
IMDB
Macro F1
Micro F1
Macro F1
Micro F1
Macro F1
Micro F1
Homogeneous
GCN
92.25 ± 0.82
91.25 ± 0.84
90.87 ± 1.77
91.68 ± 1.83
58.26 ± 0.36
60.89 ± 0.26
GAT
92.16 ± 1.55
91.95 ± 0.87
92.33 ± 1.13
92.81 ± 0.99
60.23 ± 0.67
64.06 ± 0.80
GIN
88.70 ± 2.20
88.78 ± 1.98
94.83 ± 0.43
95.24 ± 0.43
60.30 ± 0.75
63.96 ± 0.52
SAGE
92.18 ± 1.61
92.07 ± 1.51
90.23 ± 1.31
90.69 ± 1.26
60.60 ± 1.75
63.73 ± 0.63
Table 2: Heterogeneous node classification. Macro/Micro F1, mean ± std over five seeds. Top three by mean: first , second , third .
LastFM
MovieLens
PubMed
Amazon
YouTube
AUPR
AUROC
AUPR
AUROC
AUPR
AUROC
AUPR
AUROC
AUPR
AUROC
Homogeneous
GCN
97.05 ± 0.25
96.95 ± 0.17
99.67 ± 0.04
99.62 ± 0.04
96.03 ± 0.11
92.88 ± 0.28
92.44 ± 0.28
89.61 ± 0.27
89.44 ± 0.18
83.25 ± 0.17
GAT
63.03 ± 0.22
51.11 ± 0.50
97.50 ± 0.22
97.83 ± 0.18
96.06 ± 0.14
93.23 ± 0.27
88.59 ± 0.19
86.11 ± 0.25
66.79 ± 0.39
58.31 ± 0.28
GIN
97.98 ± 0.19
97.73 ± 0.30
99.58 ± 0.14
99.54 ± 0.04
96.11 ± 0.07
92.84 ± 0.12
92.04 ± 0.28
89.12 ± 0.29
88.62 ± 0.58
82.92 ± 0.49
SAGE
95.07 ± 1.76
92.70 ± 2.89
99.21 ± 0.09
99.12 ± 0.08
95.53 ± 0.52
88.66 ± 0.97
90.82 ± 0.39
87.82 ± 0.32
84.52 ± 0.09
80.22 ± 0.32
Table 3: Heterogeneous link prediction. Binary AUPR/AUROC; mean ± std over five seeds. Top three by mean: first , second , third .
MUTAG
PROTEINS
ENZYMES
NCI1
Macro F1
Micro F1
Macro F1
Micro F1
Macro F1
Micro F1
Macro F1
Micro F1
Homogeneous
GCN
89.56 ± 1.04
90.00 ± 1.35
76.82 ± 2.45
80.34 ± 2.47
12.71 ± 1.92
28.30 ± 2.71
64.13 ± 2.12
64.94 ± 2.31
GAT
89.56 ± 1.02
90.00 ± 1.32
75.76 ± 1.51
78.54 ± 1.75
14.12 ± 1.29
16.60 ± 2.27
64.19 ± 2.44
64.90 ± 2.07
GIN
94.88 ± 0.72
95.00 ± 0.78
70.64 ± 1.38
72.32 ± 1.32
20.10 ± 2.46
28.33 ± 2.43
64.17 ± 2.18
64.91 ± 2.86
SAGE
89.56 ± 1.04
90.00 ± 1.35
74.59 ± 1.56
78.55 ± 1.35
8.55 ± 1.80
18.33 ± 2.26
63.64 ± 0.85
65.41 ± 1.09
Table 4: Heterogeneous graph classification. Macro/Micro F1; mean ± std over five seeds. Top three by mean: first , second , third .
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
Hyperparameter
Search space
Sheaf type
{general,O(d),diagonal,SheafAN}
Sheaf learner
{NSD,TE,EE,NE,types,NT,ET}
Attention Learner †
{Yes,No}
d
\left\{2345\right\}
# Layers
{2345678}
input_dropout
\left[00.9\right]
Appendix
Table 5: Hyperparameter search space.
Node classification
# Nodes
# Node types
# Edges
# Edge types
Target
# Classes
DBLP
26,128
4
239,566
6
author
4
IMDB
21,420
4
86,642
6
movie
5
ACM
10,942
4
547,806
7
paper
3
Link prediction
Target
LastFM
20,612
3
141,521
3
user-artist
MovieLens
10,352
2
201,672
2
user-movie
Appendix
Table 6: Statistics of benchmark datasets.
Biomedical
# Nodes
# Node types
# Edges
# Edge types
Target
CTD-DDA
12,765
2
43,492
1
drug-disease
DrugBank-DDI
2,191
1
242,027
1
drug-drug
NDFRT-DDA
13,545
2
4,709
1
drug-disease
String-PPI
15,131
1
359,776
1
protein-protein
Appendix
Table 7: Statistics of biomedical link prediction datasets.
Networking
# Nodes
# Node types
# Edges
# Edge types
Task
Target
AS-733
6,474
1
13,895
3
LP
customer-provider
RouteNet Traffic Models
∼ 674
2
∼ 1,200
2
NC
link congestion
Appendix
Table 9: Statistics of networking datasets.
ACM
DBLP
IMDB
Family
d=2
d=3
d=4
d=5
d=2
d=3
d=4
d=5
d=2
d=3
d=4
d=5
Diag
93.7/93.6
93.0/92.9
92.6/92.5
93.0/92.9
94.0/94.5
94.1/94.5
94.1/94.5
93.5/94.0
62.4/65.4
63.6/66.6
62.8/65.9
63.2/65.8
Bundle
92.6/92.5
91.2/91.1
91.0/90.8
92.1/92.1
93.8/94.3
93.7/94.2
93.2/93.7
93.4/93.9
64.4/ 67.2
64.5 /66.6
63.9/66.5
64.2/66.4
General
91.8/91.7
91.7/91.7
91.9/91.8
92.1/92.0
93.8/94.3
94.0/94.4
94.7/95.1
94.0/94.4
63.5/65.6
62.5/65.5
62.4/65.4
63.0/65.8
Diag-P
93.3/93.2
93.1/93.0
94.2/94.1
93.5/93.4
94.9/95.3
94.7/95.1
94.9/95.3
94.6/95.0
61.5/64.7
61.6/64.6
61.1/64.1
60.2/63.6
Bundle-P
90.3/90.2
92.1/92.0
89.3/89.1
90.3/90.2
94.7/95.1
93.3/93.8
94.6/95.0
93.6/94.0
61.5/64.3
61.8/64.6
61.0/64.3
61.9/65.2
Appendix
Table 17: Node classification: Macro-F1 / Micro-F1 (%) by restriction map family and stalk dimension d . Cyan = best in family, bold = global best per dataset.
MUTAG
PROTEINS
ENZYMES
NCI1
Family
d=2
d=3
d=4
d=5
d=2
d=3
d=4
d=5
d=2
d=3
d=4
d=5
d=2
d=3
d=4
d=5
Diag
80.0/80.0
80.0/80.0
83.3/83.3
76.9/76.9
74.6/75.9
67.3/67.9
73.6/75.9
61.5/67.9
53.0/53.3
46.1/46.7
34.2/35.0
39.1/40.0
72.1/72.1
68.5/68.5
73.7/73.7
61.8/61.8
Bundle
78.0/80.0
84.7/85.0
94.9/95.0
84.7/85.0
74.8/76.8
75.8/77.7
78.8/80.4
54.4/54.5
50.8/50.0
51.2/53.3
62.3 / 63.3
51.0/51.7
62.6/62.6
57.6/57.6
68.0/68.0
60.4/60.4
General
89.0/90.0
94.9/95.0
89.9/90.0
74.9/75.0
71.3/72.3
64.2/74.1
78.7/81.2
64.2/67.0
49.9/51.7
47.7/50.0
50.7/51.7
46.9/46.7
63.2/63.2
64.4/64.4
67.5/67.5
62.1/62.1
Diag-P
95.7/95.7
95.7/95.7
96.0/96.0
100.0 / 100.0
51.8/67.9
78.9/ 82.1
71.6/74.1
63.2/74.1
22.7/28.3
25.6/30.0
14.0/21.7
14.9/23.3
60.2/60.2
62.1/62.1
62.1/62.1
61.4/61.4
Bundle-P
100.0 / 100.0
100.0 / 100.0
100.0 / 100.0
100.0 / 100.0
75.6/77.7
78.8/80.4
78.4/80.4
79.8/ 82.1
52.6/53.3
46.5/48.3
51.9/51.7
56.7/56.7
69.2/69.2
54.4/54.4
74.7/74.7
76.3/76.3
Appendix
Table 18: Graph classification: Macro-F1 / Micro-F1 (%) by restriction map family and stalk dimension d . Cyan = best in family, bold = global best per dataset.
LastFM
MovieLens
Amazon
YouTube
Family
d=2
d=3
d=4
d=5
d=2
d=3
d=4
d=5
d=2
d=3
d=4
d=5
d=2
d=3
d=4
d=5
Diag
98.4/98.2
98.5/98.2
98.4/98.2
98.5/98.2
99.7 /99.6
99.7/99.6
99.7/99.6
99.7 /99.6
93.8/91.5
93.8/91.6
93.8/91.6
93.8/91.5
90.5/85.4
90.7/86.0
90.6/85.7
90.6/85.9
Bundle
98.5/98.2
98.4/98.3
98.5/98.2
98.5/98.2
99.7/ 99.6
99.7/99.6
99.7/99.6
99.7/99.6
93.7/91.3
93.8/91.6
93.7/91.5
93.8/91.6
90.1/84.4
89.3/83.2
90.4/85.4
90.7/85.9
General
98.5/98.3
98.5/98.3
98.5/98.3
98.5/98.3
99.7/99.6
99.7/ 99.6
99.7/ 99.6
99.7/ 99.6
93.8/91.6
93.8/91.6
93.8/91.6
93.8/91.7
90.7/86.0
90.1/84.9
91.3 / 87.3
91.3 / 87.3
Diag-P
98.3/97.9
98.4/98.0
98.3/98.0
98.4/98.1
99.6/99.5
99.7/99.6
99.6/99.6
99.7/99.6
93.2/90.6
93.3/90.5
93.5/90.9
93.3/90.8
90.1/85.3
90.5/85.8
90.7/86.5
90.6/85.4
Bundle-P
98.3/98.0
98.3/98.1
98.3/98.1
98.4/98.0
99.7/99.6
99.7/99.6
99.7/99.6
99.7/99.6
93.5/91.1
93.5/91.1
93.6/91.1
93.6/91.2
89.4/83.4
89.4/83.3
89.4/83.3
89.4/83.3
Appendix
Table 19: Link prediction: (AUPR / AUROC, %). by restriction map family and stalk dimension d . Cyan = best in family, bold = global best per dataset.
ACM
DBLP
IMDB
L=2
L=3
L=4
L=5
L=6
L=7
L=8
L=2
L=3
L=4
L=5
L=6
L=7
L=8
L=2
L=3
L=4
L=5
L=6
L=7
L=8
Homogeneous baselines
GCN
92.3/92.2
92.1/92.0
65.2/67.3
53.6/57.0
38.6/42.3
30.8/39.1
32.8/40.9
82.2/83.0
88.4/89.2
88.4/89.2
89.8/90.6
90.4/91.1
91.0/91.7
87.0/88.2
15.5/25.8
58.3/60.9
15.4/39.4
57.1/60.1
23.3/45.2
58.2/62.1
16.6/28.2
GAT
92.1/92.0
92.2/92.1
83.1/84.1
28.1/38.2
29.2/37.6
28.8/38.3
17.0/34.3
84.4/85.1
90.3/91.0
89.4/89.9
92.3/92.8
90.0/90.7
91.1/91.7
91.4/92.0
24.7/32.9
60.2/64.0
14.1/40.0
59.0/61.3
24.7/32.9
55.7/61.3
23.3/45.2
GIN
88.7/88.8
86.8/86.5
35.3/45.2
49.0/49.4
42.2/43.3
41.6/45.4
41.3/43.7
79.9/80.5
93.6/93.9
93.2/93.7
93.2/93.7
92.9/93.4
94.8/95.2
92.9/93.3
53.1/56.9
60.2/63.9
55.7/60.0
57.3/60.8
52.2/58.5
59.1/62.2
52.1/56.7
SAGE
91.4/91.3
91.8/91.7
92.0/91.9
89.1/89.0
90.6/90.5
92.2/92.1
85.1/85.0
83.6/84.6
88.0/89.0
90.1/90.7
88.4/88.9
89.8/90.5
88.9/89.7
87.7/88.5
58.2/62.4
58.6/61.2
59.5/61.8
60.6/63.8
55.6/57.6
59.2/63.4
58.1/63.6
Appendix
Table 20: Node classification: Macro-F1 / Micro-F1 (%) by model and number of layers L . Cyan = best in family, bold = global best per dataset.
MUTAG
PROTEINS
L=2
L=3
L=4
L=5
L=6
L=7
L=8
L=2
L=3
L=4
L=5
L=6
L=7
L=8
Homogeneous baselines
GCN
89.6/90.0
89.6/90.0
89.6/90.0
89.6/90.0
89.6/90.0
89.6/90.0
89.6/90.0
76.4/80.4
71.8/77.7
69.5/71.4
75.8/78.6
74.1/76.8
69.0/70.5
75.8/78.6
GAT
89.6/90.0
89.6/90.0
89.6/90.0
89.6/90.0
89.6/90.0
58.3/60.0
84.0/85.0
56.2/56.2
75.8/78.6
71.8/77.7
48.8/70.5
71.8/77.7
74.6/77.7
52.2/52.7
GIN
89.6/90.0
94.9/95.0
89.9/90.0
85.0/85.0
85.0/85.0
89.6/90.0
84.7/85.0
70.3/71.4
51.3/71.4
64.1/69.6
70.6/72.3
–
66.8/67.9
62.7/68.8
SAGE
60.0/70.0
60.0/70.0
89.6/90.0
89.6/90.0
89.6/90.0
85.0/85.0
89.6/90.0
69.9/78.6
71.8/77.7
64.7/75.9
64.7/75.9
64.7/75.9
71.8/77.7
74.7/78.6
Appendix
Table 21: Graph classification: Macro-F1 / Micro-F1 (%) by model and number of layers L . Cyan = best in family, bold = global best per dataset.
LastFM
MovieLens
L=2
L=3
L=4
L=5
L=6
L=7
L=8
L=2
L=3
L=4
L=5
L=6
L=7
L=8
Homogeneous baselines
GCN
96.7/96.5
96.5/96.0
96.9/96.8
96.8/96.8
97.1/97.0
97.1/96.9
97.0/97.0
99.5/99.5
99.6/99.6
99.6/99.6
99.6/99.6
99.6/99.6
99.6/99.6
99.6/99.6
GAT
62.7/50.4
62.7/50.4
62.7/50.4
63.1/51.1
62.7/50.4
62.7/50.4
62.9/50.7
97.0/97.4
97.6/97.9
96.8/97.3
96.8/97.3
96.8/97.2
96.8/97.2
96.8/97.2
GIN
97.4/96.3
98.1/97.6
98.0/97.7
97.9/97.7
96.7/96.6
97.0/96.9
96.9/96.5
99.6/99.5
99.6/99.6
99.6/99.6
99.6/99.5
99.6/99.6
99.3/99.3
99.5/99.5
SAGE
92.7/89.2
88.0/86.4
83.5/80.1
95.1/92.7
90.0/86.4
88.5/86.5
88.0/86.6
98.8/98.8
98.8/98.8
99.1/99.0
99.2/99.1
99.1/99.0
99.2/99.0
99.2/99.1
Appendix
Table 22: Link prediction: AUPR / AUROC (%) by model and number of layers L . Cyan = best in family, bold = global best per dataset.
Predictor Name
Acronym Meaning
Inputs Used
Sheaf-NSD
N eural S heaf D iffusion
z
HetSheaf-TE
T ype E mbeddings
z,ϕ,ψ
HetSheaf-NE
N ode E mbeddings
z,ϕ
HetSheaf-EE
E dge E mbeddings
z,ψ
HetSheaf-types
All types only
ϕ,ψ
HetSheaf-NT
N ode T ypes only
ϕ
Appendix
Table 26: Summary of Heterogeneous Sheaf Predictors and their inputs.
Model
Computational complexity
Non-sheaf baselines
GCN
O(nc2+mc)
GAT
O(nc2h+mch)
HAN
O(tnc2h+tmch)
HetSheaf predictors (diag)
NSD
O(nc2+mdc)
Appendix
Table 27: Per-layer computational complexities of heterogeneous sheaf predictors and baselines. Notation: n nodes, m edges, s node types, t edge types, stalk dimension d , channels f , c=df (or c=f for non-sheaf models), attention heads h . Diagonal restriction maps are denoted (diag); general or orthogonal maps are denoted (non-diag).
Sheaf Neural Networks (SNNs) generalize Graph Neural Networks (GNNs) by replacing scalar node signals with stalk-valued signals and by using restriction maps to measure compatibility across edges. Unlike standard graph diffusion, which encourages neighboring node features to become similar, sheaf diffusion promotes consistency through the restriction maps and can therefore model more general relationships between neighboring nodes. However, existing sheaf neural architectures mainly operate at a fixed graph resolution and do not provide a principled pooling mechanism for building hierarchical representations. In this paper, we introduce Hierarchical Sheaf Pool (HiSP), a sheaf-aware pooling framework based on local spectral coarsening. Given a partition of the graph, HiSP constructs each coarse stalk by projecting fine stalk-valued features onto the low-frequency eigenmodes of the cluster-internal sheaf Laplacian. These local modes define a cochain-level prolongation map, which allows the fine sheaf energy to be represented on the coarse space through a Galerkin operator. We further analyze the approximation induced by coarsening by separating truncation loss, due to discarded local modes, from realization loss, due to representing the projected operator as a coarse sheaf. Finally, we implement HiSP as a GNN pooling layer compatible with SNNs and provide a PyG implementation supporting batching, lifted sheaf Laplacians, and hierarchical architectures.
Dionisia Naddeo, Carlo Abate, Pietro Liò +2
UiT The Arctic University of Norway · UiT The Arctic University of Norway NORCE Norwegian Research Centre AS
Many real-world heterogeneous graphs exhibit pronounced heterophily, where connected nodes often have dissimilar labels or play different semantic roles. In such settings, standard heterogeneous graph neural networks that aggregate messages along metapaths or meta-relations primarily based on feature similarity can propagate misleading information, since feature similarity may be misaligned with underlying relational semantics. In this paper, we propose HeterSEED, a semantics-structure decoupling framework for heterogeneous graph learning under heterophily. HeterSEED decouples representation learning into a heterogeneous semantic channel that captures type- and relation-aware local semantics and a structure-aware heterophily channel that separates homophilic and heterophilic neighborhoods via pseudo-label-guided partitioning and aggregates them using metapath-based structural weights. A node-level adaptive fusion mechanism then combines the two channels to produce context-dependent node representations. Theoretically, we establish that, on heterogeneous graphs under heterophily, HeterSEED is strictly more expressive than standard heterogeneous graph neural networks that rely primarily on feature similarity and provably reduces the prediction bias introduced by heterophilic neighbors. Experiments on five real-world heterogeneous graphs, including two large-scale networks at the million-node and hundred-million-edge scale, demonstrate that HeterSEED consistently outperforms representative heterogeneous graph neural networks and recent heterophily-aware baselines, especially in strongly heterophilic regimes.
Xinyi Li, Ming Li, Lu Bai +5
Zhejiang Normal University · Beijing Normal University · Central University of Finance and Economics +2
Graph Neural Networks (GNNs) have become the de facto standard for learning on relational data. While traditional GNNs' message passing is well suited for vector-valued node features, there are cases in which node features are better represented by probability distributions than real vectors. Concretely, when node features are Gaussians, characterized by a mean and a covariance matrix, naively concatenating their parameters into a single vector and applying standard message passing discards the geometric and algebraic structure that governs means and covariances. We propose Gaussian Sheaf Neural Networks (GSNNs), a principled framework that incorporates these inductive biases into graph-based learning. Building on the theory of cellular sheaves, we derive a new Laplacian operator that generalizes the sheaf Laplacian to this setting and preserves its key properties. We complement our theoretical contributions with experiments on synthetic and real-world data that illustrate the practical relevance of GSNNs.
André Ribeiro, Ana Luiza Tenório, Tiago da Silva +1