# Faster Optimization on Sparse Graphs via Neural Reparametrization

arXiv: https://arxiv.org/abs/2205.13624 · HTML: https://mlsanity.com/paper/2205.13624/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 52 references that are in the map.
- First posted on arXiv 26 May 2022.

## Builds on (most cited first, 26 of 26)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Fourier Neural Operator for Parametric Partial Differential Equations](https://mlsanity.com/paper/2010.08895/) (2020)
- [DeepONet: Learning nonlinear operators for identifying differential equations based on the universal approximation theorem of operators](https://mlsanity.com/paper/1910.03193/) (2019)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Learning Mesh-Based Simulation with Graph Networks](https://mlsanity.com/paper/2010.03409/) (2020)
- [Optimizing Neural Networks with Kronecker-factored Approximate Curvature](https://mlsanity.com/paper/1503.05671/) (2015)
- [Neural Operator: Graph Kernel Network for Partial Differential Equations](https://mlsanity.com/paper/2003.03485/) (2020)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Shampoo: Preconditioned Stochastic Tensor Optimization](https://mlsanity.com/paper/1802.09568/) (2018)
- [Deep Learning on Graphs: A Survey](https://mlsanity.com/paper/1812.04202/) (2018)
- [On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization](https://mlsanity.com/paper/1802.06509/) (2018)
- [Graph Embedding Techniques, Applications, and Performance: A Survey](https://mlsanity.com/paper/1705.02801/) (2017)
- [A roadmap for the computation of persistent homology](https://mlsanity.com/paper/1506.08903/) (2015)
- [A Topology Layer for Machine Learning](https://mlsanity.com/paper/1905.12200/) (2019)
- [Learning to Optimize Multigrid PDE Solvers](https://mlsanity.com/paper/1902.10248/) (2019)
- [Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks](https://mlsanity.com/paper/2111.13171/) (2021)
- [A Physics-Informed Machine Learning Approach for Solving Heat Transfer Equation in Advanced Manufacturing and Engineering Applications](https://mlsanity.com/paper/2010.02011/) (2020)
- [Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology](https://mlsanity.com/paper/1907.05008/) (2019)
- [Connectivity-Optimized Representation Learning via Persistent Homology](https://mlsanity.com/paper/1906.09003/) (2019)
- [Neural reparameterization improves structural optimization](https://mlsanity.com/paper/1909.04240/) (2019)
- [Neural networks for topology optimization](https://mlsanity.com/paper/1709.09578/) (2017)
- [Unsupervised Deep Learning Algorithm for PDE-based Forward and Inverse Problems](https://mlsanity.com/paper/1904.05417/) (2019)
- [An unsupervised learning approach to solving heat equations on chip based on Auto Encoder and Image Gradient](https://mlsanity.com/paper/2007.09684/) (2020)
- [Half-Inverse Gradients for Physical Deep Learning](https://mlsanity.com/paper/2203.10131/) (2022)

## Abstract (arXiv)

In mathematical optimization, second-order Newton's methods generally converge faster than first-order methods, but they require the inverse of the Hessian, hence are computationally expensive. However, we discover that on sparse graphs, graph neural networks (GNN) can implement an efficient Quasi-Newton method that can speed up optimization by a factor of 10-100x. Our method, neural reparametrization, modifies the optimization parameters as the output of a GNN to reshape the optimization landscape. Using a precomputed Hessian as the propagation rule, the GNN can effectively utilize the second-order information, reaching a similar effect as adaptive gradient methods. As our method solves optimization through architecture design, it can be used in conjunction with any optimizers such as Adam and RMSProp. We show the application of our method on scientifically relevant problems including heat diffusion, synchronization and persistent homology.