Research map / Graph learning / GNN architectures
Learning Regularization for Graph Inverse Problems
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 learned-regularization framework for graph inverse problems (GRIPs) that combines data-fit gradient steps with GNN-learned priors, instantiated as Var-GNN, ISS-GNN, and Prox-GNN and tested on five GRIP tasks.
Problem
Recovering unobserved node or edge properties of a graph from noisy, indirect, and often ill-posed measurements (graph inverse problems), where purely learned direct maps may not fit the observed data.
Approach
Adapts learned variational, inverse scale-space, and proximal regularization from grid-based inverse problems to graphs by implementing the learned regularizer/score/proximal operator with a GNN and feeding meta-data into it, so the output balances data fit and learned priors.
Key results
- On ShapeNet property completion (nb=4), Var-GNN reaches 89.16% accuracy vs 74.90% for LaplacianReg and 6.91% for TikhonovReg.
- On CLUSTER inverse source estimation (k=16), Var-GNN achieves 82.36% accuracy vs 26.28% for LaplacianReg.
- On METR-LA inverse graph transport (pl=32), Var-GNN attains nMSE 0.004 vs 0.61 for LaplacianReg.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use learned Var-GNN regularization instead of LaplacianReg | Property completion · ShapeNet, nb=4 | accuracy (%): 74.90$\pm$0.00 -> 89.16$\pm$0.31 | Helped |
| use learned Var-GNN regularization instead of LaplacianReg | Property completion · CLUSTER, nb=4 | accuracy (%): 70.13$\pm$0.00 -> 88.89$\pm$0.51 | Helped |
| use learned Var-GNN regularization instead of LaplacianReg | Inverse source estimation · CLUSTER, k=16 | accuracy (%): 26.28$\pm$0.00 -> 82.36$\pm$0.20 | Helped |
| use learned Var-GNN regularization instead of LaplacianReg | Inverse source estimation · CPOX, k=16 | nMSE: 0.84$\pm$0.00 -> 0.59$\pm$0.01 | Helped |
| use learned Var-GNN regularization instead of TikhonovReg | Inverse graph transport · METR-LA, pl=32 | nMSE: 0.36$\pm$0.00 -> 0.004 $\pm2.0 \cdot 10^{-5}$ | Helped |
| use learned Var-GNN regularization instead of LaplacianReg | Edge property recovery · CIFAR10 superpixels | nMSE: 0.598$\pm$0.00 -> 0.114$\pm$0.03 | Helped |
| remove meta-data (ablation) | Var-GNN · ShapeNet property completion, nb=4 | accuracy (%): 89.16$\pm$0.31 -> 26.89$\pm$0.02 | Hurt |
| remove meta-data (ablation) | ISS-GNN · ShapeNet property completion, nb=4 | accuracy (%): 89.59$\pm$0.53 -> 26.45$\pm$0.02 | Hurt |
| remove meta-data (ablation) | Prox-GNN · ShapeNet property completion, nb=4 | accuracy (%): 89.33$\pm$0.23 -> 26.96$\pm$0.01 | Hurt |
| increase node budget per label per graph | Property completion models · ShapeNet and CLUSTER | accuracy (%) | Helped |
Surprising findings
- ISS-GNN accuracy on CLUSTER property completion (57.08%) and Prox-GNN (53.58%) fall well below Var-GNN (88.89%), and Prox-GNN lags Var-GNN on several tasks.
- Removing meta-data drops ShapeNet completion accuracy from about 89% to about 27%, roughly to the level of the classical baselines.
Limitations
- Ill-posed inverse problems; Var-GNN/Prox-GNN/ISS-GNN results vary across tasks, with no single method dominating.
- Theoretical understanding of inverse scale-space methods is limited, and convergence and out-of-distribution behavior are not studied.
- Experiments use a simple GCN backbone and only five datasets; other GNN backbones are not explored.
Experimental setup
Datasets: CLUSTER ShapeNet METR-LA Chickenpox-Hungary CIFAR10 superpixels
Benchmarks: CLUSTER ShapeNet METR-LA Chickenpox-Hungary CIFAR10 superpixels
Metrics: accuracy normalized MSE data fit cross-entropy data fit nMSE
Baselines: LaplacianReg TikhonovReg
Builds on: learned proximal networks learned inverse scale-space Tikhonov regularization GCN
Closest papers by meaning
- Generalizing CNNs to graphs with learnable neighborhood quantization (NeurIPS 2024 · similarity 0.87)
- How Graph Neural Networks Learn: Lessons from Training Dynamics (ICML 2024 · similarity 0.87)
- DFA-GNN: Forward Learning of Graph Neural Networks by Direct Feedback Alignment (NeurIPS 2024 · similarity 0.86)
- A Manifold Perspective on the Statistical Generalization of Graph Neural Networks (ICML 2025 · similarity 0.86)
- Deep Graph Neural Networks via Posteriori-Sampling-based Node-Adaptative Residual Module (NeurIPS 2024 · similarity 0.85)
- Edge Prompt Tuning for Graph Neural Networks (ICLR 2025 · similarity 0.85)
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.