# Difference-of-Convex Regularization for Graph Learning by Differentiable Programming

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 56 references that are in the map.
- First posted on arXiv 13 Aug 2026.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Graph Neural Networks for Graphs with Heterophily: A Survey](https://mlsanity.com/paper/2202.07082/) (2022)
- [The Elements of Differentiable Programming](https://mlsanity.com/paper/2403.14606/) (2024)
- [Disciplined Convex-Concave Programming](https://mlsanity.com/paper/1604.02639/) (2016)
- [Regularized Tyler's Scatter Estimator: Existence, Uniqueness, and Algorithms](https://mlsanity.com/paper/1407.3079/) (2014)
- [Graph Convolutions Enrich the Self-Attention in Transformers!](https://mlsanity.com/paper/2312.04234/) (2023)
- [CCCP is Frank-Wolfe in disguise](https://mlsanity.com/paper/2206.12014/) (2022)
- [Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalization](https://mlsanity.com/paper/2410.08473/) (2024)
- [Distributed Majorization-Minimization for Laplacian Regularized Problems](https://mlsanity.com/paper/1803.10317/) (2018)
- [Pseudoinverse Graph Convolutional Networks: Fast Filters Tailored for Large Eigengaps of Dense Graphs and Hypergraphs](https://mlsanity.com/paper/2008.00720/) (2020)
- [A graph Laplacian regularization for hyperspectral data unmixing](https://mlsanity.com/paper/1410.3699/) (2014)
- [Reducing the Computational Complexity of Pseudoinverse for the Incremental Broad Learning System on Added Inputs](https://mlsanity.com/paper/1910.07755/) (2019)
- [Minimizing Oracle-Structured Composite Functions](https://mlsanity.com/paper/2105.14153/) (2021)
- [Computing one-bit compressive sensing via zero-norm regularized DC loss model and its surrogate](https://mlsanity.com/paper/2303.09738/) (2023)
- [A globally convergent difference-of-convex algorithmic framework and application to log-determinant optimization problems](https://mlsanity.com/paper/2306.02001/) (2023)
- [Iterative Polynomial Approximation Algorithms for Inverse Graph Filters](https://mlsanity.com/paper/2504.14341/) (2025)
- [Learning to Optimize by Differentiable Programming](https://mlsanity.com/paper/2601.16510/) (2026)
- [Accelerating Regularized Attention Kernel Regression for Spectrum Cartography](https://mlsanity.com/paper/2604.25138/) (2026)

## Abstract (arXiv)

Laplacian-regularized minimization is fundamental in signal processing and machine learning, but explicit construction of the dense graph Laplacian pseudoinverse can be computationally expensive. To address this issue, we consider the setting where the graph Laplacian is given and propose a Difference-of-Convex Regularizer (DCR) graph learning framework that learns a reusable approximation of the pseudoinverse action through regularized Maximum Likelihood Estimation (MLE) and shrinkage-regularized Convex--Concave Procedure (CCCP) iterations. For Laplacian-Regularized Nonnegative Least Squares (LR-NNLS), dual and Karush-Kuhn-Tucker (KKT) analysis motivates separating graph-dependent pseudoinverse learning from instance-specific optimization. The learned pseudoinverse is embedded into a differentiable primal optimization procedure as a graph-aware preconditioner for nonnegative reconstruction and can be reused across LR-NNLS instances sharing the same graph. We establish stability and fixed-point existence guarantees for the proposed pseudoinverse-learning iteration. Experiments across different graph topologies and scales demonstrate near-reference accuracy, competitive time-to-moderate-accuracy behavior, and effective cross-instance reuse across independently generated problem instances sharing the same graph.