Research map / Graph learning / Graph self-supervised learning
Effective Structural Encodings via Local Curvature Profiles
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Local Curvature Profiles (LCP), a structural encoding that summarizes each node's incident Ollivier-Ricci curvature distribution, and shows it outperforms other structural/positional encodings and curvature-based rewiring on GNN node and graph classification.
Problem
Which structural properties yield the most effective structural or positional encodings for GNNs remains open, and curvature-based rewiring only uses extreme curvature values, ignoring the rest of the curvature distribution.
Approach
Use summary statistics (min, max, mean, std, median) of the Ollivier-Ricci curvatures of each node's incident edges as a local structural node encoding, computed once as preprocessing, and shown to be more expressive than 1-WL (distinguishes 4x4 Rooke and Shrikhande graphs).
Key results
- LCP with GIN reaches 82.1 ± 3.8 on MUTAG vs 67.5 ± 2.7 with no encoding, and GCN with LCP reaches 35.4 ± 2.6 on ENZYMES vs 25.4 ± 1.3 with no encoding.
- LCP outperforms all other encodings (LA, RW, SUB) on all four graph classification datasets across GCN, GIN and GAT.
- Using LCP as a structural encoding outperforms BORF curvature-based rewiring on all graph classification datasets, e.g., GCN on MUTAG 79.0 vs 68.2 (no encoding after rewiring).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add LCP encoding | GCN · Graph classification datasets: Enzymes, IMDB, MUTAG, PROTEINS | accuracy | Helped |
| Add LCP encoding | GIN and GAT · Graph classification datasets | accuracy | Helped |
| Add LCP encoding | GCN, GIN, and GAT · Cora and Citeseer | accuracy | Mixed |
| Combine LCP with a global positional encoding (LA or RW) | GCN, GIN, and GAT · Enzymes, IMDB, MUTAG, PROTEINS, Cora, Citeseer | accuracy | Mixed |
| Use LCP encoding rather than BORF rewiring | GCN, GIN, and GAT · Graph classification datasets | accuracy | Helped |
| Combine BORF rewiring with positional encodings instead of LCP | GCN, GIN, and GAT · Node classification datasets | accuracy | Mixed |
| Use FRC instead of ORC to compute LCP (ablation) | GCN · Enzymes, MUTAG, and PROTEINS | accuracy | Hurt |
| Use FRC instead of ORC to compute LCP (ablation) | GCN · IMDB | accuracy | Helped |
| Use AFRC-3 or AFRC-4 instead of ORC to compute LCP (ablation) | GCN · Enzymes, IMDB, MUTAG, and PROTEINS | accuracy | Hurt |
| Use extreme curvature values instead of summary statistics for LCP (ablation) | GCN · Enzymes, IMDB, MUTAG, PROTEINS | accuracy | Mixed |
| Use only minimum and maximum curvature values for LCP (ablation) | GCN · Enzymes, IMDB, MUTAG, PROTEINS | accuracy | Mixed |
| Use combinatorial ORC bounds for LCP (ablation) | GCN · Enzymes, IMDB, MUTAG, PROTEINS | accuracy | Mixed |
Surprising findings
- Forman-Ricci curvature, which is much cheaper to compute, works surprisingly well as a substitute for ORC in LCP on IMDB (69.6 vs 67.7 for ORC).
- Node classification gains from LCP are small, and other encodings sometimes outperform LCP there.
Limitations
- Relationship between LCP and the k-WL hierarchy remains open.
- Node classification gains are smaller and inconsistent across encodings.
- Hyperparameters held constant across encodings and no tuning for BORF, so the comparison may be sensitive to settings.
Experimental setup
Datasets: CORA CITESEER ENZYMES IMDB MUTAG PROTEINS Peptides-func Peptides-struct CORNELL TEXAS WISCONSIN
Benchmarks: CORA CITESEER ENZYMES IMDB MUTAG PROTEINS Peptides-func Peptides-struct CORNELL TEXAS WISCONSIN
Metrics: test accuracy (mean with 95% confidence interval over 100 ra mean absolute error (Peptides-struct)
Baselines: Laplacian eigenvectors (LA) random walk positional encoding (RW) substructure counts (SUB) BORF rewiring Curvature Graph Network (CurvGN) no encoding
Builds on: Ollivier-Ricci curvature BORF GCN GIN GAT
Closest papers by meaning
- The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisited (ICLR 2025 · similarity 0.88)
- Discrete Curvature Graph Information Bottleneck (AAAI 2025 · similarity 0.88)
- Homomorphism Counts as Structural Encodings for Graph Learning (ICLR 2025 · similarity 0.87)
- On the Stability of Expressive Positional Encodings for Graphs (ICLR 2024 · similarity 0.87)
- Simple Path Structural Encoding for Graph Transformers (ICML 2025 · similarity 0.87)
- Spectro-Riemannian Graph Neural Networks (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.