ICML 2024

Diss-l-ECT: Dissecting Graph Data with local Euler Characteristic Transforms

Julius von Rohrscheidt, Bastian Rieck

Main figure for Diss-l-ECT: Dissecting Graph Data with local Euler Characteristic Transforms

Abstract

=3em =10000 The Euler Characteristic Transform (ECT) is an efficiently-computable geometrical-topological invariant that characterizes the global shape of data. In this paper, we introduce the Local Euler Characteristic Transform ($ $), a novel extension of the ECT particularly designed to enhance expressivity and interpretability in graph representation learning. Unlike traditional graph neural networks (GNNs), which may lose critical local details through aggregation, the $ $ provides a lossless representation of local neighborhoods. This approach addresses key limitations in GNNs by preserving local structures while maintaining global interpretability. Moreover, we construct a rotation-invariant metric based on $ $s for spatial alignment of data spaces. Our method exhibits superior performance compared to standard GNNs on a variety of benchmark node-classification tasks, while also offering theoretical guarantees that demonstrate its effectiveness.

Benchmark Results

Tested on 8 datasets 32 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 #68 66 places worse
0.9669 ±0.0014
best reported
actual #2 vs paper #68 66 places worse
paper 0.9480 ±0.0110
3
GAT+T
0.9660 ±0.0007
7
SAGE
0.9643 ±0.0027
8
GCN
actual #8 vs paper #133 125 places worse
0.9632 ±0.0008
best reported
actual #8 vs paper #133 125 places worse
paper 0.9360 ±0.0170
34
H2GCN
actual #34 vs paper #237 203 places worse
0.9548 ±0.0043
best reported
actual #34 vs paper #237 203 places worse
paper 0.9280 ±0.0120
paper 0.9280 ±0.0120 Δ at pub 0.0268
56
GraphSAGE
actual #56 vs paper #279 223 places worse
0.9508 ±0.0026
best reported
actual #56 vs paper #279 223 places worse
paper 0.9250 ±0.0070
paper 0.9250 ±0.0070 Δ at pub 0.0258
64
LECT_1+LECT_2
0.9490 ±0.0060
This paper
328
GIN
actual #328 vs paper #524 196 places worse
0.9211 ±0.0032
best reported
actual #328 vs paper #524 196 places worse
paper 0.8220 ±0.0130
best at pub: Union Subgraph Neural Networks (AAAI 2023)
paper 0.8220 ±0.0130 Δ at pub 0.0991
390
MLP
0.9128 ±0.0063
#ModelAccuracy ↑Paper
1
GraphTARIF
0.9461 ±0.0017
2
GCN
actual #2 vs paper #41 39 places worse
0.9160 ±0.0160
actual #2 vs paper #41 39 places worse
paper 0.9160 ±0.0160

Improvement within reported uncertainty; not highlighted.

paper 0.9160 ±0.0160 Δ at pub 0.0188
3
GAT
actual #3 vs paper #18 15 places worse
0.9240 ±0.0130
actual #3 vs paper #18 15 places worse
paper 0.9240 ±0.0130

Improvement within reported uncertainty; not highlighted.

paper 0.9240 ±0.0130 Δ at pub 0.0162
8
SAGE
0.9351 ±0.0006
24
LECT_1+LECT_2
0.9220 ±0.0060
This paper
46
GraphSAGE
actual #46 vs paper #149 103 places worse
0.9120 ±0.0029
best reported
actual #46 vs paper #149 103 places worse
paper 0.8920 ±0.0090
paper 0.8920 ±0.0090 Δ at pub 0.0200 Δ today 0.0200
114
H2GCN
actual #114 vs paper #323 209 places worse
0.8986 ±0.0022
best reported
actual #114 vs paper #323 209 places worse
paper 0.8450 ±0.0140
paper 0.8450 ±0.0140 Δ at pub 0.0518 Δ today 0.0536
282
GIN
actual #282 vs paper #486 204 places worse
0.8626 ±0.0056
best reported
actual #282 vs paper #486 204 places worse
paper 0.5590 ±0.0150
best at pub: Union Subgraph Neural Networks (AAAI 2023)
paper 0.5590 ±0.0150 Δ at pub 0.3036
320
MLP
0.8463
#ModelAccuracy ↑Paper
1
GCN
actual #1 vs paper #230 229 places worse
0.9302 ±0.0011
best reported
actual #1 vs paper #230 229 places worse
paper 0.7520 ±0.0080
paper 0.7520 ±0.0080 Δ at pub 0.1782
2
RSE + RGCN (70b)
0.8852 ±0.0019
3
LEMP+T
0.8825
9
SAGE
0.8771
20
H2GCN
actual #20 vs paper #229 209 places worse
0.8660
best reported
actual #20 vs paper #229 209 places worse
paper 0.7530 ±0.0140
31
GAT
actual #31 vs paper #147 116 places worse
0.8533
best reported
actual #31 vs paper #147 116 places worse
paper 0.7870 ±0.0120
54
GIN
actual #54 vs paper #242 188 places worse
0.8303 ±0.0021
best reported
actual #54 vs paper #242 188 places worse
paper 0.7420 ±0.0170
69
GraphSAGE
actual #69 vs paper #245 176 places worse
0.8146 ±0.0010
best reported
actual #69 vs paper #245 176 places worse
paper 0.7340 ±0.0150
237
MLP
0.7469 ±0.0085
238
Diss-l-ECT
0.7460 ±0.0050
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
40
H2GCN
actual #40 vs paper #367 327 places worse
0.9189 ±0.0393
best reported
actual #40 vs paper #367 327 places worse
paper 0.7230 ±0.0300
paper 0.7230 ±0.0300 Δ at pub 0.1535 Δ today 0.1959
53
GraphSAGE
actual #53 vs paper #372 319 places worse
0.9000 ±0.0365
best reported
actual #53 vs paper #372 319 places worse
paper 0.7180 ±0.0240
paper 0.7180 ±0.0240 Δ at pub 0.1820 Δ today 0.1820
189
SAGE
0.8269
211
GAT
actual #211 vs paper #576 365 places worse
0.8162 ±0.0645
best reported
actual #211 vs paper #576 365 places worse
paper 0.5170 ±0.0320
paper 0.5170 ±0.0320 Δ at pub 0.2830 Δ today 0.2992
257
GCN
actual #257 vs paper #594 337 places worse
0.7933 ±0.0447
best reported
actual #257 vs paper #594 337 places worse
paper 0.4730 ±0.0150
best today: Graph Wave Networks (WWW 2025)
paper 0.4730 ±0.0150 Δ at pub 0.3110 Δ today 0.3203
326
GIN
actual #326 vs paper #572 246 places worse
0.7460 ±0.0080
best reported
actual #326 vs paper #572 246 places worse
paper 0.5420 ±0.0290
#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
68
H2GCN
actual #68 vs paper #319 251 places worse
0.8623 ±0.0471
best reported
actual #68 vs paper #319 251 places worse
paper 0.6620 ±0.0350
138
SAGE
0.8269
157
GraphSAGE
actual #157 vs paper #222 65 places worse
0.8196 ±0.0739
best reported
actual #157 vs paper #222 65 places worse
paper 0.7600 ±0.0350

Difference within reported uncertainty; not counted as underperformance.

paper 0.7600 ±0.0350 Δ at pub 0.0596
158
GAT
actual #158 vs paper #528 370 places worse
0.8190 ±0.0540
best reported
actual #158 vs paper #528 370 places worse
paper 0.4470 ±0.0290
paper 0.4470 ±0.0290 Δ at pub 0.3720
170
GCN
actual #170 vs paper #527 357 places worse
0.8082 ±0.0360
best reported
actual #170 vs paper #527 357 places worse
paper 0.4500 ±0.0220
paper 0.4500 ±0.0220 Δ at pub 0.3515 Δ today 0.3582
201
GIN
actual #201 vs paper #519 318 places worse
0.7800 ±0.0190
best reported
actual #201 vs paper #519 318 places worse
paper 0.4650 ±0.0310
309
Diss-l-ECT_1+Diss-l-ECT_2
0.6710 ±0.0410
This paper
312
Diss-l-ECT_2
0.6700 ±0.0490
This paper
313
Diss-l-ECT_1
0.6680 ±0.0420
This paper
#ModelAccuracy ↑Paper
1
DiGGR
0.4535 ±0.0353
2
TRIGON
0.4402 ±0.0028
3
DoG
0.4320 ±0.0120
42
MLP
0.4026 ±0.0108
68
GraphSAGE
actual #68 vs paper #345 277 places worse
0.3899 ±0.0085
best reported
actual #68 vs paper #345 277 places worse
paper 0.3020 ±0.0140
paper 0.3020 ±0.0140 Δ at pub 0.0879
71
H2GCN
actual #71 vs paper #333 262 places worse
0.3885 ±0.0117
best reported
actual #71 vs paper #333 262 places worse
paper 0.3070 ±0.0190
paper 0.3070 ±0.0190 Δ at pub 0.0770 Δ today 0.0815
135
GCN
actual #135 vs paper #333 198 places worse
0.3690
best reported
actual #135 vs paper #333 198 places worse
paper 0.3070 ±0.0210
paper 0.3070 ±0.0210 Δ at pub 0.0620
182
GAT
actual #182 vs paper #324 142 places worse
0.3605 ±0.0035
best reported
actual #182 vs paper #324 142 places worse
paper 0.3110 ±0.0180
paper 0.3110 ±0.0180 Δ at pub 0.0495
266
GIN
actual #266 vs paper #415 149 places worse
0.3410 ±0.0030
best reported
actual #266 vs paper #415 149 places worse
paper 0.2650 ±0.0200
paper 0.2650 ±0.0200 Δ at pub 0.0587 Δ today 0.0760
314
ECT_1
0.3140 ±0.0190
This paper
329
ECT_1+ECT_2
0.3090 ±0.0070
This paper
349
ECT_2
0.3010 ±0.0130
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 #105 79 places worse
0.9106 ±0.0027
best reported
actual #26 vs paper #105 79 places worse
paper 0.7740 ±0.0080
paper 0.7740 ±0.0080 Δ at pub 0.0834 Δ today 0.1366
64
SAGE
0.8574 ±0.0067
77
GCN
actual #77 vs paper #114 37 places worse
0.8272 ±0.0082
best reported
actual #77 vs paper #114 37 places worse
paper 0.7330 ±0.0080
paper 0.7330 ±0.0080 Δ at pub 0.0942
83
GAT
actual #83 vs paper #106 23 places worse
0.8145 ±0.0009
best reported
actual #83 vs paper #106 23 places worse
paper 0.7640 ±0.0120
paper 0.7640 ±0.0120 Δ at pub 0.0447 Δ today 0.0505
84
L-ECT_1+L-ECT_2
0.8110 ±0.0040
This paper
129
H2GCN
actual #129 vs paper #149 20 places worse
0.6809 ±0.0029
best reported
actual #129 vs paper #149 20 places worse
paper 0.6420 ±0.0090
paper 0.6420 ±0.0090 Δ at pub 0.0389 Δ today 0.0389
135
MLP
0.6665 ±0.0047
177
GIN
0.5680 ±0.0100
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 #186 179 places worse
0.5681 ±0.0090
best reported
actual #7 vs paper #186 179 places worse
paper 0.4010 ±0.0070
12
SAGE
0.5569 ±0.0023
14
GAT
actual #14 vs paper #152 138 places worse
0.5559 ±0.0027
best reported
actual #14 vs paper #152 138 places worse
paper 0.4460 ±0.0090
15
GraphSAGE
actual #15 vs paper #180 165 places worse
0.5540 ±0.0020
best reported
actual #15 vs paper #180 165 places worse
paper 0.4220 ±0.0050
24
GCN
actual #24 vs paper #176 152 places worse
0.5411 ±0.0034
best reported
actual #24 vs paper #176 152 places worse
paper 0.4230 ±0.0070
84
MLP
0.5058
88
GIN
actual #88 vs paper #156 68 places worse
0.5020 ±0.0070
best reported
actual #88 vs paper #156 68 places worse
paper 0.4410 ±0.0080
best today: Heterophily-informed Message Passing (TMLR 2025)
paper 0.4410 ±0.0080 Δ today 0.0610
97
L-ECT_1+L-ECT_2
0.4980 ±0.0030
This paper
99
L-ECT_2
0.4960 ±0.0030
This paper
116
L-ECT_1
0.4840 ±0.0030
This paper
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 today — OK at publication; today's leaderboard best is elsewhere