NeurIPS 2024

Distributed-Order Fractional Graph Operating Network

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

Main figure for Distributed-Order Fractional Graph Operating Network

Abstract

We introduce the Distributed-order fRActional Graph Operating Network (DRAGON), a novel continuous Graph Neural Network (GNN) framework that incorporates distributed-order fractional calculus. Unlike traditional continuous GNNs that utilize integer-order or single fractional-order differential equations, DRAGON uses a learnable probability distribution over a range of real numbers for the derivative orders. By allowing a flexible and learnable superposition of multiple derivative orders, our framework captures complex graph feature updating dynamics beyond the reach of conventional models. We provide a comprehensive interpretation of our framework's capability to capture intricate dynamics through the lens of a non-Markovian graph random walk with node feature updating driven by an anomalous diffusion process over the graph. Furthermore, to highlight the versatility of the DRAGON framework, we conduct empirical evaluations across a range of graph learning tasks. The results consistently demonstrate superior performance when compared to traditional continuous GNN models. The implementation code is available at.

Benchmark Results

Tested on 9 datasets 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
94
F-GraphCON-nl
0.9410 ±0.0070
This paper
115
D-GraphCON-nl
0.9380 ±0.0080
This paper
124
D-GraphCON-l
0.9370 ±0.0040
This paper
168
D-GRAND-nl
0.9340 ±0.0050
This paper
178
F-GraphCON-l
0.9330 ±0.0100
This paper
210
D-GRAND-l
0.9310 ±0.0080
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
410
GraphCON-l
0.9080 ±0.0180
This paper
461
GIL
0.8960 ±0.0130
This paper
489
HGCN
0.8820 ±0.0140
This paper
505
GraphCON-nl
0.8550 ±0.0230
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
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.1440 Δ today 0.1598
8
SAGE
0.9351 ±0.0006
244
D-GRAND-l
0.8730 ±0.0130
This paper
249
D-GRAND-nl
0.8710 ±0.0100
This paper
250
D-GraphCON-nl
0.8710 ±0.0100
This paper
258
D-GraphCON-l
0.8690 ±0.0100
This paper
284
F-GraphCON-l
0.8620 ±0.0080
This paper
314
GraphCON-l
0.8490 ±0.0050
This paper
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
364
F-GraphCON-nl
0.8360 ±0.0220
This paper
394
GRAND-nl
0.8240 ±0.0210
This paper
426
HGCN
0.8060 ±0.0180
This paper
433
GraphCON-nl
0.7920 ±0.0110
This paper
#ModelAccuracy ↑Paper
1
GrokFormer
0.9831 ±0.0018
2
PolyFormer
0.9808 ±0.0027
3
SGFormer
0.9796 ±0.0081
6
GAT
actual #6 vs paper #252 246 places worse
0.9782 ±0.0028
best reported
actual #6 vs paper #252 246 places worse
paper 0.9250 ±0.0090
paper 0.9250 ±0.0090 Δ at pub 0.0413 Δ today 0.0532
9
GCN
actual #9 vs paper #245 236 places worse
0.9774 ±0.0035
best reported
actual #9 vs paper #245 236 places worse
paper 0.9280 ±0.0100
paper 0.9280 ±0.0100 Δ at pub 0.0370 Δ today 0.0494
17
SAGE
0.9739 ±0.0018
58
MLP
0.9597 ±0.0007
172
D-GRAND-l
0.9460 ±0.0020
This paper
176
F-GRAND-l
0.9450 ±0.0040
This paper
185
D-GRAND-nl
0.9430 ±0.0060
This paper
186
D-GraphCON-l
0.9430 ±0.0050
This paper
195
F-GraphCON-l
0.9410 ±0.0050
This paper
199
D-GraphCON-nl
0.9400 ±0.0040
This paper
202
F-GRAND-nl
0.9390 ±0.0050
This paper
203
GraphCON-l
0.9390 ±0.0040
This paper
217
GRAND-l
0.9350 ±0.0090
This paper
234
GraphCON-nl
0.9310 ±0.0030
This paper
243
F-GraphCON-nl
0.9300 ±0.0060
This paper
267
GRAND-nl
0.9140 ±0.0130
This paper
271
HGCN
0.9080 ±0.0150
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
50
D-GREAD
0.9054 ±0.0325
This paper
53
GraphSAGE
0.9000 ±0.0365
57
GREAD
actual #57 vs paper #74 17 places worse
0.8973 ±0.0449
best reported
actual #57 vs paper #74 17 places worse
paper 0.8892 ±0.0372

Difference within reported uncertainty; not counted as underperformance.

paper 0.8892 ±0.0372 Δ at pub 0.0081
64
F-GREAD
0.8946 ±0.0374
This paper
107
D-GRAND
0.8649 ±0.0320
This paper
#ModelAccuracy ↑Paper
1
P^2GNN
0.9541 ±0.0272
2
ACM-GCN
0.9480 ±0.0380
3
RF-GCN
0.9429
24
MLP
0.9136 ±0.0070
26
D-GRAND
0.9000 ±0.0467
This paper
30
D-GREAD
0.8946 ±0.0426
This paper
52
GREAD
actual #52 vs paper #60 8 places worse
0.8703 ±0.0495
best reported
actual #52 vs paper #60 8 places worse
paper 0.8649 ±0.0715

Difference within reported uncertainty; not counted as underperformance.

paper 0.8649 ±0.0715 Δ at pub 0.0054 Δ today 0.0054
55
F-GREAD
0.8689 ±0.0416
This paper
75
BLEND
0.8595 ±0.0682
This paper
95
Sheaf
0.8486 ±0.0471
This paper
112
GRAFF
actual #112 vs paper #127 15 places worse
0.8405 ±0.0610
best reported
actual #112 vs paper #127 15 places worse
paper 0.8324 ±0.0649

Difference within reported uncertainty; not counted as underperformance.

paper 0.8324 ±0.0649 Δ at pub 0.0081 Δ today 0.0081
138
SAGE
0.8269

Heterophily Benchmark

#ModelAccuracy ↑Paper
1
Dir-Poly
0.9451 ±0.0022
2
D-CDE
0.9387 ±0.0041
This paper
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
0.7587 ±0.0043
This paper
108
FAGCN
actual #108 vs paper #122 14 places worse
0.7571 ±0.0139
best reported
actual #108 vs paper #122 14 places worse
paper 0.7053 ±0.0099
paper 0.7053 ±0.0099 Δ at pub 0.0518
114
GPR-GNN
0.7337 ±0.0068
This paper
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
0.6809 ±0.0029
This paper
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
149
TDE-GNN
0.6429 ±0.0058
This paper
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
0.6385 ±0.0049
This paper
#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.5681 ±0.0090
best reported
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
102
D-CDE
0.4943 ±0.0126
This paper
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
0.4632 ±0.0250
This paper
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
0.4436 ±0.0035
This paper
162
GraphBel
0.4363 ±0.0042
This paper
186
TDE-GNN
0.4033 ±0.0137
This paper
194
Diag-NSD
0.3796 ±0.0020
This paper
196
GloGNN
0.3728 ±0.0066
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
11
D-CDE
0.9647 ±0.0189
This paper
15
F-CDE
0.9604 ±0.0025
This paper
18
CDE
0.9550 ±0.0523
This paper
42
GraphSAGE
0.9358 ±0.0005
76
GBK-GNN
actual #76 vs paper #114 38 places worse
0.9085 ±0.0058
best reported
actual #76 vs paper #114 38 places worse
paper 0.8356 ±0.0084
best at pub: Evolving Computation Graphs (ICML 2023)
paper 0.8356 ±0.0084 Δ at pub 0.0729 Δ today 0.0729
81
ACM-GCN
0.9047 ±0.0057
This paper
85
H2GCN
actual #85 vs paper #85
0.8995 ±0.0038
actual #85 vs paper #85
paper 0.8995 ±0.0038

Improvement within reported uncertainty; not highlighted.

paper 0.8995 ±0.0038 Δ at pub 0.0024
91
FAGCN
actual #91 vs paper #91
0.8969 ±0.0060
actual #91 vs paper #91
paper 0.8969 ±0.0060
prev best: Evolving Computation Graphs (ICML 2023)
paper 0.8969 ±0.0060 Δ at pub 0.0152
94
Diag-NSD
0.8959 ±0.0061
This paper
110
GPR-GNN
actual #110 vs paper #115 5 places worse
0.8624 ±0.0061
best reported
actual #110 vs paper #115 5 places worse
paper 0.8179 ±0.0098
best at pub: Evolving Computation Graphs (ICML 2023)
paper 0.8179 ±0.0098 Δ at pub 0.0445 Δ today 0.0445
123
GRAND
0.7667 ±0.0098
This paper
124
GraphBel
0.7651 ±0.0103
This paper
125
ACMP
0.7615 ±0.0112
This paper
137
CPGNN
actual #137 vs paper #137
0.7127 ±0.0114
actual #137 vs paper #137
paper 0.7127 ±0.0114
prev best: Evolving Computation Graphs (ICML 2023)
paper 0.7127 ±0.0114 Δ at pub 0.1924
148
GloGNN
actual #148 vs paper #148
0.6253 ±0.0134
actual #148 vs paper #148
paper 0.6253 ±0.0134
paper 0.6253 ±0.0134 Δ at pub 0.1145
150
TDE-GNN
0.6115 ±0.0224
This paper
156
MLP
0.5099 ±0.0147
157
ResNet
actual #157 vs paper #157
0.5095 ±0.0112
actual #157 vs paper #157
paper 0.5095 ±0.0112
prev best: Evolving Computation Graphs (ICML 2023)

Improvement within reported uncertainty; not highlighted.

paper 0.5095 ±0.0112 Δ at pub 0.0006
#ModelROC-AUC ↑Paper
1
NID_GAT
0.9703 ±0.0002
2
NID_GCN
0.9685 ±0.0010
3
UniGAP
0.8421 ±0.0080
13
H2GCN
actual #13 vs paper #120 107 places worse
0.7928 ±0.0080
best reported
actual #13 vs paper #120 107 places worse
paper 0.6666 ±0.0184
16
GCN
0.7902 ±0.0060
43
FAGCN
actual #43 vs paper #48 5 places worse
0.7724 ±0.0126
best reported
actual #43 vs paper #48 5 places worse
paper 0.7704 ±0.0156
best at pub: Evolving Computation Graphs (ICML 2023)

Difference within reported uncertainty; not counted as underperformance.

paper 0.7704 ±0.0156 Δ at pub 0.0020 Δ today 0.0020
70
D-CDE
0.7553 ±0.0098
This paper
75
CDE
0.7517 ±0.0099
This paper
76
F-CDE
0.7517 ±0.0099
This paper
81
GBK-GNN
actual #81 vs paper #88 7 places worse
0.7447 ±0.0086
best reported
actual #81 vs paper #88 7 places worse
paper 0.7298 ±0.0105
best at pub: Evolving Computation Graphs (ICML 2023)

Difference within reported uncertainty; not counted as underperformance.

paper 0.7298 ±0.0105 Δ at pub 0.0149 Δ today 0.0149
86
GPR-GNN
actual #86 vs paper #86
0.7341 ±0.0124
actual #86 vs paper #86
paper 0.7341 ±0.0124
prev best: Evolving Computation Graphs (ICML 2023)
paper 0.7341 ±0.0124 Δ at pub 0.1793
93
ACMP
0.7118 ±0.0103
This paper
96
MLP
0.7082 ±0.0010
98
GraphBel
0.7079 ±0.0099
This paper
99
GRAND
0.7067 ±0.0128
This paper
101
ResNet
actual #101 vs paper #103 2 places worse
0.7034 ±0.0076
best reported
actual #101 vs paper #103 2 places worse
paper 0.7010 ±0.0075
best at pub: Evolving Computation Graphs (ICML 2023)

Difference within reported uncertainty; not counted as underperformance.

paper 0.7010 ±0.0075 Δ at pub 0.0024 Δ today 0.0024
111
Diag-NSD
0.6925 ±0.0115
This paper
113
TDE-GNN
0.6894 ±0.0169
This paper
119
GloGNN
actual #119 vs paper #119
0.6715 ±0.0192
actual #119 vs paper #119
paper 0.6715 ±0.0192
prev best: Evolving Computation Graphs (ICML 2023)

Improvement within reported uncertainty; not highlighted.

paper 0.6715 ±0.0192 Δ at pub 0.0141
120
CPGNN
actual #120 vs paper #120
0.6709 ±0.0263
actual #120 vs paper #120
paper 0.6709 ±0.0263
prev best: Evolving Computation Graphs (ICML 2023)

Improvement within reported uncertainty; not highlighted.

paper 0.6709 ±0.0263 Δ at pub 0.0113
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