Difference-of-Convex Regularization for Graph Learning by Differentiable Programming
Abstract
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.
Related
- Autoregressive Differentiable Method for Integer Programming
- Sample-Smooth Spaces: A Convenient Category for Differentiable Probabilistic Programming
- Spectral Dependence of Convex Regularization: Fundamental Limits under Right-Rotationally Invariant Designs
- cuPDQPx: A GPU-Accelerated Restarted Halpern PDHG for Large-Scale Convex Quadratic Programming
- Configuration-Constrained Tube MPC for Difference-of-Convex Nonlinear Systems
BibTeX
@misc{tao2026differenceofconvex,
title = {{Difference-of-Convex Regularization for Graph Learning by Differentiable Programming}},
author = {Liping Tao and Chee Wei Tan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.12757},
eprint = {2608.12757},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.12757},
}
RIS
TY - UNPB
TI - Difference-of-Convex Regularization for Graph Learning by Differentiable Programming
AU - Liping Tao
AU - Chee Wei Tan
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2608.12757
UR - https://arxiv.org/abs/2608.12757
AB - 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.
ER -