TMLR 2025

Heterophily-informed Message Passing

Haishan Wang, Arno Solin, Vikas Garg

Main figure for Heterophily-informed Message Passing

Abstract

Graph neural networks (GNNs) are known to be vulnerable to oversmoothing due to their implicit homophily assumption. We mitigate this problem with a novel scheme that regulates the aggregation of messages, modulating the type and extent of message passing locally thereby preserving both the low and high-frequency components of information. Our approach relies solely on learnt embeddings, obviating the need for auxiliary labels, thus extending the benefits of heterophily-aware embeddings to broader applications,, generative modelling. Our experiments, conducted across various data sets and GNN architectures, demonstrate performance enhancements and reveal heterophily patterns across standard classification benchmarks. Furthermore, application to molecular generation showcases notable performance improvements on chemoinformatics benchmarks.

Benchmark Results

Tested on 11 datasets 34 baseline values reported too low Non-standard metric on 2 datasets

Tables show presented results in global context (best 3 papers + GCN + MLP).

Classic

#ModelAccuracy ↑Paper
1
LGTL
0.9518 ±0.0011
2
MixHop (LO)
0.9513 ±0.0038
3
GraphSAGE (LO)
0.9511 ±0.0036
18
GCN
actual #18 vs paper #130 112 places worse
0.9296 ±0.0015
best reported
actual #18 vs paper #130 112 places worse
paper 0.8850 ±0.0050
20
GAT
actual #20 vs paper #200 180 places worse
0.9233 ±0.0018
best reported
actual #20 vs paper #200 180 places worse
paper 0.8710 ±0.0050
95
GraphSAGE+mix.
0.8930 ±0.0040
This paper
114
GraphSAGE+hom.
0.8890 ±0.0040
This paper
116
SAGE
0.8881 ±0.0015
122
GCN+hom.
0.8870 ±0.0050
This paper
125
GraphSAGE
actual #125 vs paper #156 31 places worse
0.8864 ±0.0030
best reported
actual #125 vs paper #156 31 places worse
paper 0.8810 ±0.0050
paper 0.8810 ±0.0050 Δ at pub 0.0054
127
GCN+mix.
0.8860 ±0.0050
This paper
155
GAT+hom.
0.8820 ±0.0050
This paper
157
GIN
actual #157 vs paper #228 71 places worse
0.8810
best reported
actual #157 vs paper #228 71 places worse
paper 0.8610 ±0.0080
paper 0.8610 ±0.0080 Δ at pub 0.0200
167
GAT+mix.
0.8780 ±0.0070
This paper
190
GIN+hom.
0.8740 ±0.0080
This paper
210
MLP
0.8690 ±0.0074
222
GIN+mix.
0.8660 ±0.0090
This paper
282
GCN+het.
0.8390 ±0.0050
This paper
368
GIN+het.
0.8110 ±0.1490
This paper
496
GAT+het.
0.7960 ±0.0090
This paper

Amazon-Photo

Global leaderboard →
Non-default metric. This paper reports ROC-AUC; the dataset default is Accuracy. Values below use ROC-AUC only.

Sorted by ROC-AUC. Highlighted rows are from other papers.

#ModelROC-AUC ↑Paper
1
GraphSAGE
0.9550 ±0.0040
This paper
2
GraphSAGE+hom.
0.9550 ±0.0040
This paper
3
GraphSAGE+mix.
0.9520 ±0.0050
This paper
4
GraphSAGE+het.
0.9500 ±0.0060
This paper
5
GCN+mix.
0.9460 ±0.0060
This paper
6
GCN
0.9440 ±0.0050
This paper
7
GCN+hom.
0.9440 ±0.0040
This paper
8
GAT
0.9410 ±0.0050
This paper
9
GAT+mix.
0.9410 ±0.0030
This paper
10
GAT+hom.
0.9360 ±0.0060
This paper
11
GAT+het.
0.8730 ±0.0130
This paper
12
GCN+het.
0.8540 ±0.0160
This paper
13
GIN+mix.
0.7820 ±0.1360
This paper
14
GIN+het.
0.3840 ±0.1570
This paper
15
GIN+hom.
0.3770 ±0.0800
This paper
16
GIN
0.3530 ±0.0710
This paper

Amazon-Computers

Global leaderboard →
Non-default metric. This paper reports ROC-AUC; the dataset default is Accuracy. Values below use ROC-AUC only.

Sorted by ROC-AUC. Highlighted rows are from other papers.

#ModelROC-AUC ↑Paper
1
GCN
0.9160 ±0.0050
This paper
2
GCN+hom.
0.9150 ±0.0050
This paper
3
GCN+mix.
0.9120 ±0.0060
This paper
4
GAT
0.9120 ±0.0030
This paper
5
GAT+mix.
0.9110 ±0.0030
This paper
6
GAT+hom.
0.9090 ±0.0030
This paper
7
GraphSAGE
0.9090 ±0.0030
This paper
8
GraphSAGE+hom.
0.9060 ±0.0040
This paper
9
GraphSAGE+mix.
0.9030 ±0.0050
This paper
10
GraphSAGE+het.
0.8940 ±0.0060
This paper
11
GAT+het.
0.8400 ±0.0200
This paper
12
GCN+het.
0.7830 ±0.0140
This paper
13
GIN+mix.
0.5730 ±0.1470
This paper
14
GIN+het.
0.4310 ±0.0930
This paper
15
GIN+hom.
0.4280 ±0.0380
This paper
16
GIN
0.4120 ±0.0310
This paper

Heterophilic Graphs

#ModelAccuracy ↑Paper
1
P^2GNN
0.9672 ±0.0147
2
DoG
0.9660 ±0.0210
3
GPF-plus
0.9583 ±0.0419
34
MLP
0.9230 ±0.0070
53
GraphSAGE
actual #53 vs paper #261 208 places worse
0.9000 ±0.0365
best reported
actual #53 vs paper #261 208 places worse
paper 0.7900 ±0.0120
paper 0.7900 ±0.0120 Δ at pub 0.1100 Δ today 0.1100
189
SAGE
0.8269
211
GAT
actual #211 vs paper #544 333 places worse
0.8162 ±0.0645
best reported
actual #211 vs paper #544 333 places worse
paper 0.5780 ±0.0460
paper 0.5780 ±0.0460 Δ at pub 0.2302 Δ today 0.2382
249
GraphSAGE+mix.
0.7970 ±0.0590
This paper
257
GCN
actual #257 vs paper #532 275 places worse
0.7933 ±0.0447
best reported
actual #257 vs paper #532 275 places worse
paper 0.5840 ±0.0460
best at pub: Graph Wave Networks (WWW 2025)
paper 0.5840 ±0.0460 Δ at pub 0.2093
303
GraphSAGE+het.
0.7590 ±0.0680
This paper
326
GIN
actual #326 vs paper #550 224 places worse
0.7460 ±0.0080
best reported
actual #326 vs paper #550 224 places worse
paper 0.5700 ±0.0690
384
GraphSAGE+hom.
0.7050 ±0.0550
This paper
501
GCN+het.
0.6000 ±0.0770
This paper
509
GAT+het.
0.5970 ±0.0550
This paper
511
GAT+hom.
0.5950 ±0.0490
This paper
512
GIN+het.
0.5950 ±0.0800
This paper
525
GAT+mix.
0.5920 ±0.0470
This paper
531
GCN+hom.
0.5860 ±0.0510
This paper
533
GIN+mix.
0.5840 ±0.0680
This paper
538
GIN+hom.
0.5810 ±0.0680
This paper
554
GCN+mix.
0.5680 ±0.0530
This paper
#ModelAccuracy ↑Paper
1
P^2GNN
0.9541 ±0.0272
2
ACM-GCN
actual #2 vs paper #2
0.9480 ±0.0380
actual #2 vs paper #2
paper 0.9480 ±0.0380
paper 0.9480 ±0.0380 Δ at pub 0.0909
3
RF-GCN
0.9429
22
GPRGNN
actual #22 vs paper #22
0.9157 ±0.0196
best reported
actual #22 vs paper #22
paper 0.9140 ±0.0070

Difference within reported uncertainty; not counted as underperformance.

paper 0.9140 ±0.0070 Δ at pub 0.0017
24
MLP
0.9136 ±0.0070
68
H2GCN
actual #68 vs paper #71 3 places worse
0.8620 ±0.0470
actual #68 vs paper #71 3 places worse
paper 0.8620 ±0.0470

Improvement within reported uncertainty; not highlighted.

paper 0.8620 ±0.0470 Δ at pub 0.0110
84
ACMP
0.8540 ±0.0700
This paper
138
SAGE
0.8269
157
GraphSAGE
actual #157 vs paper #280 123 places worse
0.8196 ±0.0739
best reported
actual #157 vs paper #280 123 places worse
paper 0.7050 ±0.0370
paper 0.7050 ±0.0370 Δ at pub 0.1146
158
GAT
actual #158 vs paper #524 366 places worse
0.8190 ±0.0540
best reported
actual #158 vs paper #524 366 places worse
paper 0.4570 ±0.0630
paper 0.4570 ±0.0630 Δ at pub 0.3620
170
GCN
actual #170 vs paper #542 372 places worse
0.8082 ±0.0360
best reported
actual #170 vs paper #542 372 places worse
paper 0.4270 ±0.0490
paper 0.4270 ±0.0490 Δ at pub 0.3745 Δ today 0.3812
201
GIN
actual #201 vs paper #516 315 places worse
0.7800 ±0.0190
best reported
actual #201 vs paper #516 315 places worse
paper 0.4680 ±0.0710
266
GraphSAGE+het.
0.7220 ±0.0760
This paper
300
GraphSAGE+mix.
0.6810 ±0.0650
This paper
307
GraphSAGE+hom.
0.6730 ±0.0410
This paper
342
Geom-GCN
actual #342 vs paper #371 29 places worse
0.6412
best reported
actual #342 vs paper #371 29 places worse
paper 0.6080
paper 0.6080 Δ at pub 0.0332
390
GAT+het.
0.5890 ±0.0940
This paper
484
GAT+mix.
0.5050 ±0.0750
This paper
486
GIN+het.
0.5030 ±0.1070
This paper
491
GCN+het.
0.5000 ±0.0820
This paper
494
GIN+mix.
0.4950 ±0.0670
This paper
499
GCN+mix.
0.4890 ±0.0620
This paper
515
GAT+hom.
0.4700 ±0.0750
This paper
518
GIN+hom.
0.4680 ±0.0660
This paper
549
GCN+hom.
0.4140 ±0.0540
This paper
#ModelAccuracy ↑Paper
1
DMD++
0.9190 ±0.0260
2
F-GREAD-BS
0.9059 ±0.0380
3
APPNP
0.9010 ±0.0350
37
MLP
0.8629 ±0.0450
49
GraphSAGE+mix.
0.8450 ±0.0110
This paper
53
GAT
actual #53 vs paper #207 154 places worse
0.8430 ±0.0370
best reported
actual #53 vs paper #207 154 places worse
paper 0.5080 ±0.0870
paper 0.5080 ±0.0870 Δ at pub 0.3350
63
GCN
actual #63 vs paper #199 136 places worse
0.8310 ±0.0320
best reported
actual #63 vs paper #199 136 places worse
paper 0.5240 ±0.0600
paper 0.5240 ±0.0600 Δ at pub 0.3070
69
GraphSAGE
actual #69 vs paper #94 25 places worse
0.8118 ±0.0556
best reported
actual #69 vs paper #94 25 places worse
paper 0.7710 ±0.0650

Difference within reported uncertainty; not counted as underperformance.

paper 0.7710 ±0.0650 Δ at pub 0.0408 Δ today 0.0408
77
GraphSAGE+hom.
0.8020 ±0.0520
This paper
78
GraphSAGE+het.
0.8000 ±0.0430
This paper
86
GIN
actual #86 vs paper #216 130 places worse
0.7900 ±0.0060
best reported
actual #86 vs paper #216 130 places worse
paper 0.4490 ±0.0680
149
SAGE
0.6480 ±0.0520
187
GAT+mix.
0.5530 ±0.0630
This paper
188
GAT+hom.
0.5490 ±0.0580
This paper
190
GCN+hom.
0.5450 ±0.0330
This paper
192
GCN+het.
0.5390 ±0.0380
This paper
195
GAT+het.
0.5330 ±0.0680
This paper
203
GCN+mix.
0.5200 ±0.0610
This paper
204
GIN+het.
0.5200 ±0.0380
This paper
209
GIN+mix.
0.5060 ±0.0780
This paper
214
GIN+hom.
0.4900 ±0.0630
This paper

Heterophily Benchmark

#ModelAccuracy ↑Paper
1
Dir-Poly
0.9451 ±0.0022
2
D-CDE
0.9387 ±0.0041
3
LargeScaleNet
0.9358 ±0.0024
26
GraphSAGE
actual #26 vs paper #97 71 places worse
0.9106 ±0.0027
best reported
actual #26 vs paper #97 71 places worse
paper 0.7890 ±0.0040
paper 0.7890 ±0.0040 Δ at pub 0.0684 Δ today 0.1216
64
SAGE
0.8574 ±0.0067
77
GCN
actual #77 vs paper #193 116 places worse
0.8272 ±0.0082
best reported
actual #77 vs paper #193 116 places worse
paper 0.4780 ±0.0080
paper 0.4780 ±0.0080 Δ at pub 0.3492
83
GAT
actual #83 vs paper #193 110 places worse
0.8145 ±0.0009
best reported
actual #83 vs paper #193 110 places worse
paper 0.4710 ±0.0060
paper 0.4710 ±0.0060 Δ at pub 0.3377 Δ today 0.3435
98
GraphSAGE+mix.
0.7870 ±0.0070
This paper
99
GraphSAGE+hom.
0.7860 ±0.0060
This paper
103
GraphSAGE+het.
0.7810 ±0.0070
This paper
118
GCN+mix.
0.7150 ±0.0050
This paper
128
GAT+mix.
0.6890 ±0.0090
This paper
135
MLP
0.6665 ±0.0047
140
GIN+hom.
0.6590 ±0.0080
This paper
151
GIN+mix.
0.6400 ±0.0100
This paper
164
GCN+het.
0.6020 ±0.0050
This paper
170
GIN+het.
0.5860 ±0.0110
This paper
174
GAT+hom.
0.5760 ±0.0100
This paper
177
GIN
actual #177 vs paper #192 15 places worse
0.5680 ±0.0100
best reported
actual #177 vs paper #192 15 places worse
paper 0.4820 ±0.0120
paper 0.4820 ±0.0120 Δ at pub 0.0860
178
GCN+hom.
0.5660 ±0.0060
This paper
193
GAT+het.
0.4800 ±0.0130
This paper
#ModelAccuracy ↑Paper
1
UniGAP
0.6375 ±0.0110
2
H2GCN + HalfHop
0.5961 ±0.0100
3
GraphSAGE + HalfHop
0.5897 ±0.0150
12
SAGE
0.5569 ±0.0023
14
GAT
actual #14 vs paper #109 95 places worse
0.5559 ±0.0027
best reported
actual #14 vs paper #109 95 places worse
paper 0.4880 ±0.0050
15
GraphSAGE
actual #15 vs paper #51 36 places worse
0.5540 ±0.0020
best reported
actual #15 vs paper #51 36 places worse
paper 0.5270 ±0.0060
24
GCN
actual #24 vs paper #105 81 places worse
0.5411 ±0.0034
best reported
actual #24 vs paper #105 81 places worse
paper 0.4910 ±0.0060
34
GraphSAGE+mix.
0.5350 ±0.0070
This paper
61
GraphSAGE+het.
0.5220 ±0.0060
This paper
67
GraphSAGE+hom.
0.5160 ±0.0050
This paper
84
MLP
0.5058
89
GAT+mix.
0.5020 ±0.0050
This paper
88
GIN
actual #88 vs paper #88
0.5020 ±0.0070
actual #88 vs paper #88
paper 0.5020 ±0.0070
paper 0.5020 ±0.0070 Δ at pub 0.0610
98
GCN+mix.
0.4970 ±0.0080
This paper
104
GIN+hom.
0.4920 ±0.0070
This paper
119
GIN+het.
0.4820 ±0.0120
This paper
120
GIN+mix.
0.4820 ±0.0150
This paper
130
GAT+hom.
0.4720 ±0.0070
This paper
131
GCN+hom.
0.4710 ±0.0050
This paper
136
GCN+het.
0.4640 ±0.0060
This paper
157
GAT+het.
0.4410 ±0.0060
This paper
#ModelROC-AUC ↑Paper
1
BuNN
0.9899 ±0.0016
2
DC-GNN
0.9850 ±0.0021
3
Tango -GPS
0.9839 ±0.0054
36
GAT
actual #36 vs paper #154 118 places worse
0.9391 ±0.0035
best reported
actual #36 vs paper #154 118 places worse
paper 0.5440 ±0.0160
paper 0.5440 ±0.0160 Δ at pub 0.3761 Δ today 0.3951
42
GraphSAGE
actual #42 vs paper #130 88 places worse
0.9358 ±0.0005
best reported
actual #42 vs paper #130 88 places worse
paper 0.7320 ±0.0170
paper 0.7320 ±0.0170 Δ at pub 0.2031 Δ today 0.2038
46
SAGE
0.9351 ±0.0057
68
GCN
actual #68 vs paper #155 87 places worse
0.9150 ±0.0006
best reported
actual #68 vs paper #155 87 places worse
paper 0.5230 ±0.0060
paper 0.5230 ±0.0060 Δ at pub 0.3745 Δ today 0.3920
104
GIN
actual #104 vs paper #154 50 places worse
0.8782 ±0.0034
best reported
actual #104 vs paper #154 50 places worse
paper 0.5510 ±0.0320
paper 0.5510 ±0.0320 Δ at pub 0.3272
127
GAT+mix.
0.7510 ±0.0240
This paper
128
GCN+mix.
0.7450 ±0.0230
This paper
131
GraphSAGE+mix.
0.7310 ±0.0190
This paper
136
GCN+het.
0.7150 ±0.0180
This paper
138
GraphSAGE+het.
0.7100 ±0.0190
This paper
142
GraphSAGE+hom.
0.6840 ±0.0140
This paper
146
GIN+het.
0.6570 ±0.0980
This paper
151
GIN+mix.
0.6050 ±0.0700
This paper
152
GIN+hom.
0.5820 ±0.0460
This paper
153
GCN+hom.
0.5730 ±0.0100
This paper
154
GAT+hom.
0.5550 ±0.0320
This paper
155
GAT+het.
0.5270 ±0.0380
This paper
156
MLP
0.5099 ±0.0147
#ModelROC-AUC ↑Paper
1
Polynormer-r
0.8591 ±0.0074
2
DC-GNN
0.8588 ±0.0081
3
TANGO-GPS
0.8566 ±0.0101
28
GAT
actual #28 vs paper #161 133 places worse
0.8443 ±0.0100
best reported
actual #28 vs paper #161 133 places worse
paper 0.5700 ±0.0270
paper 0.5700 ±0.0270 Δ at pub 0.2743
50
GCN
actual #50 vs paper #159 109 places worse
0.8364 ±0.0067
best reported
actual #50 vs paper #159 109 places worse
paper 0.5800 ±0.0290
paper 0.5800 ±0.0290 Δ at pub 0.2564 Δ today 0.2564
77
GraphSAGE
actual #77 vs paper #156 79 places worse
0.8243 ±0.0044
best reported
actual #77 vs paper #156 79 places worse
paper 0.6050 ±0.0160
paper 0.6050 ±0.0160 Δ at pub 0.2193 Δ today 0.2193
76
SAGE
0.8243 ±0.0044
89
GIN
actual #89 vs paper #166 77 places worse
0.8072 ±0.0119
best reported
actual #89 vs paper #166 77 places worse
paper 0.5330 ±0.0690
paper 0.5330 ±0.0690 Δ at pub 0.2742
139
MLP
0.7362 ±0.0020
156
GAT+mix.
0.6240 ±0.0270
This paper
157
GraphSAGE+hom.
0.5970 ±0.0150
This paper
158
GraphSAGE+mix.
0.5920 ±0.0200
This paper
159
GCN+mix.
0.5870 ±0.0160
This paper
160
GCN+hom.
0.5770 ±0.0320
This paper
161
GraphSAGE+het.
0.5770 ±0.0140
This paper
162
GIN+mix.
0.5630 ±0.0700
This paper
163
GAT+hom.
0.5570 ±0.0320
This paper
164
GCN+het.
0.5510 ±0.0110
This paper
165
GIN+het.
0.5370 ±0.0580
This paper
167
GIN+hom.
0.5300 ±0.0640
This paper
168
GAT+het.
0.5050 ±0.0050
This paper
#ModelROC-AUC ↑Paper
1
NID_GAT
0.9703 ±0.0002
2
NID_GCN
0.9685 ±0.0010
3
UniGAP
0.8421 ±0.0080
16
GCN
actual #16 vs paper #154 138 places worse
0.7902 ±0.0060
best reported
actual #16 vs paper #154 138 places worse
paper 0.5320 ±0.0040
26
GAT
actual #26 vs paper #157 131 places worse
0.7835 ±0.0116
best reported
actual #26 vs paper #157 131 places worse
paper 0.5240 ±0.0040
paper 0.5240 ±0.0040 Δ at pub 0.2595
46
GraphSAGE
actual #46 vs paper #145 99 places worse
0.7721 ±0.0130
best reported
actual #46 vs paper #145 99 places worse
paper 0.5600 ±0.0080
58
SAGE
0.7644 ±0.0062
96
MLP
0.7082 ±0.0010
118
GIN
actual #118 vs paper #159 41 places worse
0.6776
best reported
actual #118 vs paper #159 41 places worse
paper 0.5180 ±0.0300
paper 0.5180 ±0.0300 Δ at pub 0.1596
138
GIN+mix.
0.5930 ±0.0390
This paper
142
GraphSAGE+mix.
0.5720 ±0.0120
This paper
145
GraphSAGE+het.
0.5610 ±0.0070
This paper
148
GraphSAGE+hom.
0.5570 ±0.0070
This paper
149
GIN+hom.
0.5570 ±0.0460
This paper
151
GAT+mix.
0.5480 ±0.0090
This paper
155
GCN+mix.
0.5310 ±0.0060
This paper
156
GAT+hom.
0.5300 ±0.0070
This paper
157
GCN+hom.
0.5280 ±0.0020
This paper
159
GCN+het.
0.5210 ±0.0090
This paper
160
GAT+het.
0.5130 ±0.0080
This paper
162
GIN+het.
0.5080 ±0.0260
This paper
SOTA performance (not significantly different from the best) Baseline / comparison (this paper) Global context (other papers) Best at pub — reported result worse than the best known when published (best reported in green) Best at pub — reported value improved over the best known when published Best today — OK at publication; today's leaderboard best is elsewhere