Research map / Graph learning / GNN architectures
Neural Gaussian Similarity Modeling for Differential Graph Structure Learning
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 a differentiable graph structure learner using Gaussian similarity (GauSim, and learnable NeuralGauSim) for non-nearest-neighbor edge sampling plus a transition-graph projection to reduce complexity to O(n).
Problem
Graph structure learning is hampered by non-differentiable discrete edge sampling (blocking gradient flow) and O(n^2) similarity computation that limits scalability to large graphs.
Approach
Replace linear similarity-based sampling with a bell-shaped Gaussian similarity (with learnable per-node center and width) so non-nearest neighbors can be sampled, use Gumbel-Softmax relaxation for differentiable sampling, and sample edges to a learned small transition node set instead of all nodes.
Key results
- NeuralGauSim-T reaches 70.15% on CiteSeer and 84.89% on Mini-ImageNet (K=5), with the best results on 6 of 8 datasets vs. baselines per the authors.
- Under the full-graph setting, GauSim and NeuralGauSim outperform LinSim at every K in {5,10,15,20}, while LinSim degrades as K grows (e.g., CiteSeer 67.23 to 64.39).
- On CiteSeer, NeuralGauSim-T trains in 0.0393 s per epoch with 1,821 MB GPU memory versus 0.1238 s and 4,664 MB for full-graph NeuralGauSim.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use NeuralGauSim-T instead of the strongest reported baseline | Graph structure learning · CiteSeer | accuracy: 67.19$\pm$0.28 -> 70.15$\pm$0.37 | Helped |
| Use NeuralGauSim-T instead of the strongest reported baseline | Graph structure learning · PubMed | accuracy: 82.57$\pm$0.45 -> 82.65$\pm$0.74 | Helped |
| Use NeuralGauSim-T instead of the strongest reported baseline | Graph structure learning · Chameleon | accuracy: 47.02$\pm$0.61 -> 48.25$\pm$0.63 | Helped |
| Use NeuralGauSim-T instead of the strongest reported baseline | Graph structure learning · Squirrel | accuracy: 28.23$\pm$0.19 -> 28.57$\pm$0.36 | Helped |
| Use NeuralGauSim-T instead of the strongest reported baseline | Graph structure learning · CS | accuracy: 91.77$\pm$0.10 -> 89.22$\pm$1.55 | Hurt |
| Use NeuralGauSim-T instead of the strongest reported baseline | Graph structure learning · Physics | accuracy: 94.81$\pm$0.11 -> 94.64$\pm$0.10 | Hurt |
| Use NeuralGauSim-T instead of the strongest reported baseline | Graph structure learning · 20News | accuracy: 62.70$\pm$0.84 -> 62.89$\pm$1.10 | Helped |
| Use NeuralGauSim-T instead of the strongest reported baseline | Graph structure learning · Mini-ImageNet | accuracy: 83.10$\pm$0.49 -> 84.89$\pm$0.37 | Helped |
| Replace linear similarity sampling with Gaussian similarity sampling (ablation) | Full-graph GSL · CiteSeer | accuracy: 67.23$\pm$0.23 -> 69.19$\pm$0.14 | Helped |
| Replace Gaussian similarity with learnable Neural Gaussian Similarity (ablation) | Full-graph GSL · Chameleon | accuracy: 47.84$\pm$0.54 -> 48.02$\pm$0.20 | No clear effect |
| Use NeuralGauSim-T rather than GauSim-T (ablation) | Transition-graph GSL · CiteSeer | accuracy: 70.19$\pm$0.84 -> 70.15$\pm$0.37 | No clear effect |
| Use NeuralGauSim-T rather than GauSim-T (ablation) | Transition-graph GSL · Mini-ImageNet | accuracy: 83.33$\pm$0.88 -> 84.89$\pm$0.37 | Helped |
Surprising findings
- Removing transition-graph nodes from NeuralGauSim-T does not significantly hurt and sometimes improves performance, while IDGL-Anchor degrades markedly.
Limitations
- Does not incorporate structure regularization or refinement strategies from recent work.
- Scalability to graphs with millions of nodes is not addressed.
- Heterogeneous and multiplex graphs are not handled.
Experimental setup
Datasets: CiteSeer PubMed Chameleon Squirrel CS Physics 20News Mini-ImageNet
Benchmarks: CiteSeer PubMed Chameleon Squirrel CS Physics 20News Mini-ImageNet
Metrics: accuracy training time (s) GPU memory (MB)
Baselines: GCN-kNN HeatGCN-kNN LINKX-kNN SLAPS IDGL-Full IDGL-Anchor NodeFormer LinSim
Builds on: Gumbel-Softmax / concrete relaxation NodeFormer IDGL GCN
Closest papers by meaning
- OpenGSL: A Comprehensive Benchmark for Graph Structure Learning (NeurIPS 2023 · similarity 0.89)
- Bridging Graph Worlds: Neural Approximation of Gromov-Wasserstein Distances (NeurIPS 2026 · similarity 0.88)
- On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks (ICML 2025 · similarity 0.87)
- Exploring Consistency in Graph Representations: from Graph Kernels to Graph Neural Networks (NeurIPS 2024 · similarity 0.87)
- NoiseHGNN: Synthesized Similarity Graph-Based Neural Network for Noised Heterogeneous Graph Representation Learning (AAAI 2025 · similarity 0.87)
- Graph Structure Inference with BAM: Neural Dependency Processing via Bilinear Attention (NeurIPS 2024 · similarity 0.86)
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.