ICLR 2024

Unleashing the Potential of Fractional Calculus in Graph Neural Networks with FROND

Qiyu Kang, Kai Zhao, Qinxu Ding, Feng Ji, Xuhao Li, Wenfei Liang, Yang Song, Wee Peng Tay

Main figure for Unleashing the Potential of Fractional Calculus in Graph Neural Networks with FROND

Abstract

We introduce the FRactional-Order graph Neural Dynamical network (FROND), a new continuous graph neural network (GNN) framework. Unlike traditional continuous GNNs that rely on integer-order differential equations, FROND employs the Caputo fractional derivative to leverage the non-local properties of fractional calculus. This approach enables the capture of long-term dependencies in feature updates, moving beyond the Markovian update mechanisms in conventional integer-order models and offering enhanced capabilities in graph representation learning. We offer an interpretation of the node feature updating process in FROND from a non-Markovian random walk perspective when the feature updating is particularly governed by a diffusion process. We demonstrate analytically that oversmoothing can be mitigated in this setting. Experimentally, we validate the FROND framework by comparing the fractional adaptations of various established integer-order continuous GNNs, demonstrating their consistently improved performance and underscoring the framework's potential as an effective extension to enhance traditional continuous GNNs. The code is available at.

Benchmark Results

Tested on 10 datasets SOTA at publication on 1 13 baseline values reported too low

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

Classic

#ModelAccuracy ↑Paper
1
GraphTARIF
0.9703 ±0.0019
2
GAT
actual #2 vs paper #503 501 places worse
0.9669 ±0.0014
best reported
actual #2 vs paper #503 501 places worse
paper 0.8570 ±0.2030

Difference within reported uncertainty; not counted as underperformance.

paper 0.8570 ±0.2030 Δ at pub 0.0928 Δ today 0.1099
3
GAT+T
0.9660 ±0.0007
7
SAGE
0.9643 ±0.0027
8
GCN
actual #8 vs paper #395 387 places worse
0.9632 ±0.0008
best reported
actual #8 vs paper #395 387 places worse
paper 0.9120 ±0.0120
182
RL-GRAND-l
0.9330 ±0.0070
This paper
207
F-GRAND-nl
0.9310 ±0.0090
This paper
239
F-GRAND-l
0.9280 ±0.0060
This paper
298
GRAND-nl
0.9240 ±0.0080
This paper
310
GRAND-l
0.9230 ±0.0090
This paper
390
MLP
0.9128 ±0.0063
461
GIL
0.8960 ±0.0130
This paper
489
HGCN
0.8820 ±0.0140
This paper
#ModelAccuracy ↑Paper
1
GraphTARIF
0.9461 ±0.0017
2
GCN
actual #2 vs paper #389 387 places worse
0.9412 ±0.0008
best reported
actual #2 vs paper #389 387 places worse
paper 0.8260 ±0.0240
paper 0.8260 ±0.0240 Δ at pub 0.0712 Δ today 0.1152
3
GAT
actual #3 vs paper #442 439 places worse
0.9398 ±0.0022
best reported
actual #3 vs paper #442 439 places worse
paper 0.7800 ±0.1900

Difference within reported uncertainty; not counted as underperformance.

paper 0.7800 ±0.1900 Δ at pub 0.1278 Δ today 0.1598
8
SAGE
0.9351 ±0.0006
320
MLP
0.8463
332
F-GRAND-l
0.8440 ±0.0150
This paper
348
F-GRAND-nl
0.8410 ±0.0090
This paper
360
GRAND-l
0.8370 ±0.0120
This paper
394
GRAND-nl
0.8240 ±0.0210
This paper
426
HGCN
0.8060 ±0.0180
This paper

OGB

#ModelAccuracy ↑Paper
1
Jacobi
0.8968
2
GPR
0.8953
3
LEMP4HG
0.8939
4
SAGE
0.8933
83
GraphSAGE
actual #83 vs paper #215 132 places worse
0.8287
best reported
actual #83 vs paper #215 132 places worse
paper 0.7829 ±0.0016
229
F-GRAND-l
0.7725 ±0.0062
This paper
251
Full-batch GCN
0.7564 ±0.0021
This paper
257
GRAND-l
0.7556 ±0.0067
This paper
313
Node2Vec
0.7249 ±0.0010
This paper
351
MLP
actual #351 vs paper #370 19 places worse
0.6605 ±0.0020
best reported
actual #351 vs paper #370 19 places worse
paper 0.6106 ±0.0008
paper 0.6106 ±0.0008 Δ at pub 0.2312 Δ today 0.0499

Heterophilic Graphs

#ModelAccuracy ↑Paper
1
P^2GNN
0.9672 ±0.0147
2
DoG
0.9660 ±0.0210
3
GPF-plus
0.9583 ±0.0419
5
ACM-GCN
actual #5 vs paper #91 86 places worse
0.9557 ±0.0360
best reported
actual #5 vs paper #91 86 places worse
paper 0.8784 ±0.0440
27
F-GREAD-BS
0.9297 ±0.0439
This paper
34
MLP
0.9230 ±0.0070
39
GGCN
actual #39 vs paper #148 109 places worse
0.9213 ±0.0305
best reported
actual #39 vs paper #148 109 places worse
paper 0.8486 ±0.0455
best today: Graph Wave Networks (WWW 2025)
paper 0.8486 ±0.0455 Δ today 0.0727
40
H2GCN
actual #40 vs paper #148 108 places worse
0.9189 ±0.0393
best reported
actual #40 vs paper #148 108 places worse
paper 0.8486 ±0.0723

Difference within reported uncertainty; not counted as underperformance.

paper 0.8486 ±0.0723 Δ at pub 0.0104 Δ today 0.0703
53
GraphSAGE
0.9000 ±0.0365
70
GCNII
actual #70 vs paper #280 210 places worse
0.8918 ±0.0443
best reported
actual #70 vs paper #280 210 places worse
paper 0.7757 ±0.0383
paper 0.7757 ±0.0383 Δ at pub 0.0289 Δ today 0.1161
75
GREAD-BS
actual #75 vs paper #75
0.8892 ±0.0372
actual #75 vs paper #75
paper 0.8892 ±0.0372

Improvement within reported uncertainty; not highlighted.

paper 0.8892 ±0.0372 Δ at pub 0.0002
82
GRAFF
0.8838 ±0.0453
This paper
141
GloGNN
actual #141 vs paper #164 23 places worse
0.8524 ±0.0490
best reported
actual #141 vs paper #164 23 places worse
paper 0.8432 ±0.0415

Difference within reported uncertainty; not counted as underperformance.

paper 0.8432 ±0.0415 Δ today 0.0092
145
Sheaf
0.8505 ±0.0551
This paper
182
BLEND
0.8324 ±0.0465
This paper
217
GRAND
actual #217 vs paper #308 91 places worse
0.8140 ±0.0350
best reported
actual #217 vs paper #308 91 places worse
paper 0.7568 ±0.0725

Difference within reported uncertainty; not counted as underperformance.

paper 0.7568 ±0.0725 Δ at pub 0.0452 Δ today 0.0572
325
LINKX
0.7460 ±0.0837
This paper
376
CGNN
actual #376 vs paper #378 2 places worse
0.7140 ±0.0410
best reported
actual #376 vs paper #378 2 places worse
paper 0.7135 ±0.0405

Difference within reported uncertainty; not counted as underperformance.

paper 0.7135 ±0.0405 Δ at pub 0.0005
415
Geom-GCN
actual #415 vs paper #425 10 places worse
0.6760
best reported
actual #415 vs paper #425 10 places worse
paper 0.6676 ±0.0272

Difference within reported uncertainty; not counted as underperformance.

paper 0.6676 ±0.0272 Δ at pub 0.0084
#ModelAccuracy ↑Paper
1
DiGGR
0.4535 ±0.0353
2
TRIGON
0.4402 ±0.0028
3
DoG
0.4320 ±0.0120
16
ACM-GCN
actual #16 vs paper #173 157 places worse
0.4198 ±0.0089
best reported
actual #16 vs paper #173 157 places worse
paper 0.3628 ±0.0109
paper 0.3628 ±0.0109 Δ at pub 0.0032 Δ today 0.0570
38
GCNII
actual #38 vs paper #114 76 places worse
0.4082 ±0.0179
best reported
actual #38 vs paper #114 76 places worse
paper 0.3744 ±0.0130
paper 0.3744 ±0.0130 Δ at pub 0.0117 Δ today 0.0338
42
MLP
0.4026 ±0.0108
58
GloGNN
actual #58 vs paper #116 58 places worse
0.3959 ±0.0029
best reported
actual #58 vs paper #116 58 places worse
paper 0.3735 ±0.0130
paper 0.3735 ±0.0130 Δ at pub 0.0224
62
GGCN
actual #62 vs paper #113 51 places worse
0.3929 ±0.0048
best reported
actual #62 vs paper #113 51 places worse
paper 0.3754 ±0.0156

Difference within reported uncertainty; not counted as underperformance.

paper 0.3754 ±0.0156 Δ at pub 0.0027 Δ today 0.0175
68
GraphSAGE
0.3899 ±0.0085
71
H2GCN
actual #71 vs paper #198 127 places worse
0.3885 ±0.0117
best reported
actual #71 vs paper #198 127 places worse
paper 0.3570 ±0.0100
paper 0.3570 ±0.0100 Δ at pub 0.0270 Δ today 0.0315
82
F-GREAD-BS
0.3828 ±0.0074
This paper
87
Geom-GCN
actual #87 vs paper #308 221 places worse
0.3810
best reported
actual #87 vs paper #308 221 places worse
paper 0.3159 ±0.0115
paper 0.3159 ±0.0115 Δ at pub 0.0651
94
GREAD-BS
0.3790 ±0.0117
This paper
102
Sheaf
0.3781 ±0.0115
This paper
129
GRAFF
actual #129 vs paper #181 52 places worse
0.3711 ±0.0108
best reported
actual #129 vs paper #181 52 places worse
paper 0.3609 ±0.0081

Difference within reported uncertainty; not counted as underperformance.

paper 0.3609 ±0.0081 Δ at pub 0.0102 Δ today 0.0102
180
LINKX
0.3610 ±0.0155
This paper
189
CGNN
0.3595 ±0.0086
This paper
201
BLEND
0.3563 ±0.0101
This paper
203
GRAND
0.3562 ±0.0101
This paper
#ModelAccuracy ↑Paper
1
Hetero-S (GAT 8-layer)
0.8693
2
Dir-GNN+CNA
0.8586 ±0.0180
3
GAT
0.8560
28
ACM-GCN
actual #28 vs paper #76 48 places worse
0.7476 ±0.0220
best reported
actual #28 vs paper #76 48 places worse
paper 0.6693 ±0.0185
41
F-GREAD-BS
0.7145 ±0.0198
This paper
42
GREAD-BS
actual #42 vs paper #44 2 places worse
0.7142 ±0.0178
best reported
actual #42 vs paper #44 2 places worse
paper 0.7138 ±0.0131

Difference within reported uncertainty; not counted as underperformance.

paper 0.7138 ±0.0131 Δ at pub 0.0002 Δ today 0.0004
45
GloGNN
actual #45 vs paper #56 11 places worse
0.7133 ±0.0242
best reported
actual #45 vs paper #56 11 places worse
paper 0.6978 ±0.0242

Difference within reported uncertainty; not counted as underperformance.

paper 0.6978 ±0.0242 Δ at pub 0.0143 Δ today 0.0155
48
GGCN
0.7114 ±0.0184
This paper
49
GRAFF
0.7108 ±0.0175
This paper
52
GCN
0.7033
64
LINKX
0.6842 ±0.0138
This paper
69
Sheaf
0.6804 ±0.0158
This paper
103
GCNII
0.6386 ±0.0304
This paper
124
Geom-GCN
actual #124 vs paper #137 13 places worse
0.6090
best reported
actual #124 vs paper #137 13 places worse
paper 0.6000 ±0.0281

Difference within reported uncertainty; not counted as underperformance.

paper 0.6000 ±0.0281 Δ at pub 0.0090 Δ today 0.0090
133
H2GCN
actual #133 vs paper #136 3 places worse
0.6030 ±0.0231
best reported
actual #133 vs paper #136 3 places worse
paper 0.6011 ±0.0215

Difference within reported uncertainty; not counted as underperformance.

paper 0.6011 ±0.0215 Δ at pub 0.0019
137
BLEND
0.6011 ±0.0209
This paper
143
CGNN
actual #143 vs paper #215 72 places worse
0.5910 ±0.0078
best reported
actual #143 vs paper #215 72 places worse
paper 0.4689 ±0.0166
paper 0.4689 ±0.0166 Δ at pub 0.0001 Δ today 0.1221
151
GRAND
actual #151 vs paper #167 16 places worse
0.5467 ±0.0254
actual #151 vs paper #167 16 places worse
paper 0.5467 ±0.0254
paper 0.5467 ±0.0254 Δ at pub 0.0434
169
MLP
0.5429
#ModelAccuracy ↑Paper
1
IBG-NN
0.7763 ±0.0179
2
Dir-GNN+CNA
0.7747 ±0.0128
3
DHGNN
0.7684 ±0.0161
19
GloGNN
actual #19 vs paper #57 38 places worse
0.7121 ±0.0184
best reported
actual #19 vs paper #57 38 places worse
paper 0.5754 ±0.0139
paper 0.5754 ±0.0139 Δ at pub 0.0034 Δ today 0.1367
25
ACM-GCN
actual #25 vs paper #75 50 places worse
0.6740 ±0.0221
best reported
actual #25 vs paper #75 50 places worse
paper 0.5440 ±0.0188
39
H2GCN
actual #39 vs paper #202 163 places worse
0.6190 ±0.0140
best reported
actual #39 vs paper #202 163 places worse
paper 0.3648 ±0.0186
paper 0.3648 ±0.0186 Δ at pub 0.0427 Δ today 0.2542
40
LINKX
0.6181 ±0.0180
This paper
45
F-GREAD-BS
0.6086 ±0.0105
This paper
46
GCN
0.6067
52
GREAD-BS
actual #52 vs paper #52
0.5922 ±0.0144
actual #52 vs paper #52
paper 0.5922 ±0.0144

Improvement within reported uncertainty; not highlighted.

paper 0.5922 ±0.0144 Δ at pub 0.0002
53
GRAFF
actual #53 vs paper #75 22 places worse
0.5901 ±0.0131
best reported
actual #53 vs paper #75 22 places worse
paper 0.5452 ±0.0137
66
Sheaf
0.5634 ±0.0132
This paper
69
GGCN
actual #69 vs paper #71 2 places worse
0.5567 ±0.0187
best reported
actual #69 vs paper #71 2 places worse
paper 0.5517 ±0.0158

Difference within reported uncertainty; not counted as underperformance.

paper 0.5517 ±0.0158 Δ today 0.0050
132
BLEND
0.4306 ±0.0139
This paper
164
GRAND
0.4005 ±0.0150
This paper
172
MLP
0.3930 ±0.0079
176
GCNII
actual #176 vs paper #178 2 places worse
0.3881 ±0.0197
best reported
actual #176 vs paper #178 2 places worse
paper 0.3847 ±0.0158

Difference within reported uncertainty; not counted as underperformance.

paper 0.3847 ±0.0158 Δ today 0.0034
179
Geom-GCN
actual #179 vs paper #181 2 places worse
0.3832 ±0.0092
best reported
actual #179 vs paper #181 2 places worse
paper 0.3815 ±0.0092

Difference within reported uncertainty; not counted as underperformance.

paper 0.3815 ±0.0092 Δ at pub 0.0017 Δ today 0.0017
228
CGNN
actual #228 vs paper #242 14 places worse
0.2924 ±0.0109
actual #228 vs paper #242 14 places worse
paper 0.2924 ±0.0109

Improvement within reported uncertainty; not highlighted.

paper 0.2924 ±0.0109 Δ at pub 0.0004 Δ today 0.0516
#ModelAccuracy ↑Paper
1
DMD++
0.9190 ±0.0260
2
F-GREAD-BS
0.9059 ±0.0380
This paper
3
APPNP
0.9010 ±0.0350
7
GREAD-BS
0.8941 ±0.0330
This paper
8
Sheaf
0.8941 ±0.0474
This paper
13
GRAND
actual #13 vs paper #80 67 places worse
0.7941 ±0.0364
actual #13 vs paper #80 67 places worse
paper 0.7941 ±0.0364
paper 0.7941 ±0.0364 Δ at pub 0.1455 Δ today 0.0919
15
ACM-GCN
0.8843 ±0.0322
This paper
22
H2GCN
actual #22 vs paper #23 1 place worse
0.8765 ±0.0498
actual #22 vs paper #23 1 place worse
paper 0.8765 ±0.0498

Improvement within reported uncertainty; not highlighted.

paper 0.8765 ±0.0498 Δ at pub 0.0098
24
GRAFF
0.8745 ±0.0294
This paper
27
GloGNN
0.8706 ±0.0353
This paper
32
GGCN
0.8686 ±0.0329
This paper
37
MLP
0.8629 ±0.0450
57
BLEND
0.8412 ±0.0356
This paper
63
GCN
0.8310 ±0.0320
75
GCNII
0.8039 ±0.0340
This paper
97
LINKX
0.7549 ±0.0572
This paper
110
CGNN
0.7431 ±0.0726
This paper
139
Geom-GCN
actual #139 vs paper #149 10 places worse
0.6451 ±0.0366
actual #139 vs paper #149 10 places worse
paper 0.6451 ±0.0366

Improvement within reported uncertainty; not highlighted.

paper 0.6451 ±0.0366 Δ at pub 0.0041

Heterophily Benchmark

#ModelAccuracy ↑Paper
1
Dir-Poly
0.9451 ±0.0022
2
D-CDE
0.9387 ±0.0041
3
LargeScaleNet
0.9358 ±0.0024
6
F-CDE
0.9306 ±0.0055
This paper
18
CDE
0.9164 ±0.0028
This paper
26
GraphSAGE
0.9106 ±0.0027
105
Diag-NSD
0.7750 ±0.0067
This paper
107
GBK-GNN
actual #107 vs paper #107
0.7587 ±0.0043
actual #107 vs paper #107
paper 0.7587 ±0.0043
prev best: Evolving Computation Graphs (ICML 2023)
paper 0.7587 ±0.0043 Δ at pub 0.0130
108
FAGCN
actual #108 vs paper #122 14 places worse
0.7053 ±0.0099
actual #108 vs paper #122 14 places worse
paper 0.7053 ±0.0099
prev best: Evolving Computation Graphs (ICML 2023)
paper 0.7053 ±0.0099 Δ at pub 0.0531 Δ today 0.0518
114
GPR-GNN
actual #114 vs paper #114
0.7337 ±0.0068
actual #114 vs paper #114
paper 0.7337 ±0.0068
prev best: Evolving Computation Graphs (ICML 2023)
paper 0.7337 ±0.0068 Δ at pub 0.0852
115
ACM-GCN
actual #115 vs paper #128 13 places worse
0.7189 ±0.0061
best reported
actual #115 vs paper #128 13 places worse
paper 0.6835 ±0.0195
116
GRAND
0.7160 ±0.0058
This paper
119
ACMP
0.7127 ±0.0059
This paper
126
GraphBel
0.6947 ±0.0037
This paper
129
H2GCN
actual #129 vs paper #129
0.6809 ±0.0029
actual #129 vs paper #129
paper 0.6809 ±0.0029
paper 0.6809 ±0.0029 Δ at pub 0.0798
135
MLP
0.6665 ±0.0047
141
ResNet
actual #141 vs paper #141
0.6588 ±0.0038
best reported
actual #141 vs paper #141
paper 0.6571 ±0.0044
best at pub: Evolving Computation Graphs (ICML 2023)

Difference within reported uncertainty; not counted as underperformance.

paper 0.6571 ±0.0044 Δ at pub 0.0017 Δ today 0.0017
152
CPGNN
actual #152 vs paper #154 2 places worse
0.6396 ±0.0062
best reported
actual #152 vs paper #154 2 places worse
paper 0.6378 ±0.0050
best at pub: Evolving Computation Graphs (ICML 2023)

Difference within reported uncertainty; not counted as underperformance.

paper 0.6378 ±0.0050 Δ at pub 0.0018 Δ today 0.0018
154
GloGNN
actual #154 vs paper #154
0.6385 ±0.0049
actual #154 vs paper #154
paper 0.6385 ±0.0049
paper 0.6385 ±0.0049 Δ at pub 0.0422
#ModelAccuracy ↑Paper
1
UniGAP
0.6375 ±0.0110
2
H2GCN + HalfHop
0.5961 ±0.0100
3
GraphSAGE + HalfHop
0.5897 ±0.0150
7
H2GCN
actual #7 vs paper #182 175 places worse
0.4136 ±0.0047
actual #7 vs paper #182 175 places worse
paper 0.4136 ±0.0047
12
SAGE
0.5569 ±0.0023
47
ACM-GCN
actual #47 vs paper #191 144 places worse
0.5294 ±0.0023
best reported
actual #47 vs paper #191 144 places worse
paper 0.3851 ±0.0338
paper 0.3851 ±0.0338 Δ at pub 0.1443
84
MLP
0.5058
103
GPR-GNN
actual #103 vs paper #159 56 places worse
0.4937 ±0.0071
best reported
actual #103 vs paper #159 56 places worse
paper 0.4390 ±0.0048
best at pub: Evolving Computation Graphs (ICML 2023)
paper 0.4390 ±0.0048 Δ at pub 0.0098 Δ today 0.0547
106
F-CDE
0.4901 ±0.0056
This paper
127
CDE
0.4763 ±0.0043
This paper
137
FAGCN
actual #137 vs paper #137
0.4632 ±0.0250
actual #137 vs paper #137
paper 0.4632 ±0.0250
prev best: Evolving Computation Graphs (ICML 2023)

Improvement within reported uncertainty; not highlighted.

paper 0.4632 ±0.0250 Δ at pub 0.0220
140
GBK-GNN
actual #140 vs paper #162 22 places worse
0.4598 ±0.0071
best reported
actual #140 vs paper #162 22 places worse
paper 0.4347 ±0.0051
best at pub: Evolving Computation Graphs (ICML 2023)
paper 0.4347 ±0.0051 Δ at pub 0.0251 Δ today 0.0251
141
ResNet
actual #141 vs paper #142 1 place worse
0.4590 ±0.0052
best reported
actual #141 vs paper #142 1 place worse
paper 0.4570 ±0.0069
best at pub: Evolving Computation Graphs (ICML 2023)

Difference within reported uncertainty; not counted as underperformance.

paper 0.4570 ±0.0069 Δ at pub 0.0020 Δ today 0.0020
148
GRAND
0.4505 ±0.0065
This paper
151
ACMP
0.4476 ±0.0052
This paper
154
CPGNN
actual #154 vs paper #154
0.4436 ±0.0035
actual #154 vs paper #154
paper 0.4436 ±0.0035
prev best: Evolving Computation Graphs (ICML 2023)
paper 0.4436 ±0.0035 Δ at pub 0.0457
162
GraphBel
0.4363 ±0.0042
This paper
194
Diag-NSD
0.3796 ±0.0020
This paper
196
GloGNN
actual #196 vs paper #196
0.3728 ±0.0066
actual #196 vs paper #196
paper 0.3728 ±0.0066

Improvement within reported uncertainty; not highlighted.

paper 0.3728 ±0.0066 Δ at pub 0.0039
SOTA performance (not significantly different from the best) Proposed method (this paper) 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 Improved at pub — later paper surpassed this result Best today — OK at publication; today's leaderboard best is elsewhere