Research map / Graph learning / GNN architectures
Learning From Simplicial Data Based on Random Walks and 1D Convolutions
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 SCRaWl, a simplicial complex neural network that samples random walks over simplices, encodes them as walk feature matrices, and processes them with 1D convolutions, achieving strong results on Semantic Scholar imputation and social contact vertex classification.
Problem
Higher-order models on simplicial complexes are expressive but computationally expensive; the paper seeks an efficient architecture that captures higher-order relations and is expressive in a way different from message-passing simplicial networks.
Approach
Replace message passing with random walks on simplices (uniform connection or neighbor sampling), encode walks with simplex states and local identity/adjacency features, and update simplex states with fast 1D CNNs; the number and length of walks trade off cost against expressivity, and expressivity is proven incomparable to MPSN.
Key results
- On Semantic Scholar imputation SCRaWl reaches 0.95-0.99 accuracy across missing rates, on par with MPSN and above SCNN, SAN and SAT for most orders.
- On the primary-school social contact dataset SCRaWl achieves 0.927 ± 0.026 vs. 0.727 ± 0.043 for MPSN; on high-school it reaches 1.000 ± 0.000 vs. 0.943 ± 0.033 for MPSN.
- CAt-Walk marginally outperforms SCRaWl on primary-school (0.932 ± 0.025 vs. 0.927 ± 0.026).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SCRaWl instead of SIN (MPSN) | Vertex classification · Primary-school | validation accuracy: 0.727 ± 0.043 -> 0.927 ± 0.026 | Helped |
| Use SCRaWl instead of SIN (MPSN) | Vertex classification · High-school | validation accuracy: 0.943 ± 0.033 -> 1.0 ± 0.0 | Helped |
| Add higher-order simplicial interactions rather than using only the graph skeleton | SCRaWl on social contact datasets · Primary-school | validation accuracy: 0.415 ± 0.030 -> 0.927 ± 0.026 | Helped |
| Add higher-order simplicial interactions rather than using only the graph skeleton | SCRaWl on social contact datasets · High-school | validation accuracy: 0.823 ± 0.042 -> 1.000 ± 0.000 | Helped |
| Use only upper adjacency (ablation) | SCRaWl · Primary-school | validation accuracy: 0.927 ± 0.026 -> 0.889 ± 0.063 | Hurt |
| Use only lower adjacency (ablation) | SCRaWl · Primary-school | validation accuracy: 0.927 ± 0.026 -> 0.454 ± 0.099 | Hurt |
| Use only upper adjacency (ablation) | SCRaWl · High-school | validation accuracy: 1.0 ± 0.0 -> 0.994 ± 0.009 | Hurt |
| Use only lower adjacency (ablation) | SCRaWl · High-school | validation accuracy: 1.0 ± 0.0 -> 0.975 ± 0.009 | Hurt |
| Increase local window size from s=1 to s=8 (ablation) | SCRaWl · Primary-school | validation accuracy: 0.571 ± 0.079 -> 0.927 ± 0.026 | Helped |
| Increase local window size from s=1 to s=8 (ablation) | SCRaWl · High-school | validation accuracy: 0.977 ± 0.006 -> 1.0 ± 0.0 | Helped |
| Increase walk length (ablation) | SCRaWl · Social contact datasets | validation accuracy | Helped |
| Increase walk length to ℓ=50 (ablation) | SCRaWl · Primary-school | validation accuracy: 0.927 ± 0.026 | Helped |
Surprising findings
- CAt-Walk marginally beats SCRaWl on the primary-school dataset.
- Using only upper adjacency gives 0.889 accuracy on primary-school, while only lower adjacency gives 0.454.
Limitations
- Expects one random walk per simplex to not scale well on large complexes.
- Performance on the primary-school dataset is slightly below CAt-Walk.
- Evaluated mainly on two datasets for vertex classification and one for imputation; no edge-flow tasks.
Experimental setup
Datasets: Semantic Scholar co-authorship network primary-school social contact dataset high-school social contact dataset
Benchmarks: Semantic Scholar co-authorship imputation primary-school vertex classification high-school vertex classification
Metrics: imputation accuracy within ±5% validation accuracy
Baselines: k-simplex2vec SNN SCNN SAT SAN MPSN (SIN) CRaWl HyperGCN AllSetTransformer CAt-Walk
Builds on: CRaWl MPSN SCNN simplex2vec
Closest papers by meaning
- Unsupervised Parameter-free Simplicial Representation Learning with Scattering Transforms (ICML 2024 · similarity 0.87)
- Non-convolutional graph neural networks. (NeurIPS 2024 · similarity 0.86)
- Revisiting Random Walks for Learning on Graphs (ICLR 2025 · similarity 0.85)
- Higher-Order Graph Convolutional Network with Flower-Petals Laplacians on Simplicial Complexes (AAAI 2024 · similarity 0.83)
- Towards Understanding Transformers in Learning Random Walks (NeurIPS 2025 · similarity 0.83)
- Towards Scalable and Deep Graph Neural Networks via Noise Masking (AAAI 2025 · similarity 0.83)
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.