From graphs to DAGs: a low-complexity model and a scalable algorithm

• URL: http://arxiv.org/abs/2204.04644v1
• Date: Sun, 10 Apr 2022 10:22:56 GMT
• Title: From graphs to DAGs: a low-complexity model and a scalable algorithm
• Authors: Shuyu Dong, Mich\`ele Sebag
• Abstract summary: This paper presents a low-complexity model, called LoRAM for Low-Rank Additive Model, which combines low-rank matrix factorization with a sparsification mechanism for the continuous optimization of DAGs. The proposed approach achieves a reduction from a cubic complexity to quadratic complexity while handling the same DAG characteristic function as NoTears.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning directed acyclic graphs (DAGs) is long known a critical challenge at the core of probabilistic and causal modeling. The NoTears approach of (Zheng et al., 2018), through a differentiable function involving the matrix exponential trace $\mathrm{tr}(\exp(\cdot))$, opens up a way to learning DAGs via continuous optimization, though with a $O(d^3)$ complexity in the number $d$ of nodes. This paper presents a low-complexity model, called LoRAM for Low-Rank Additive Model, which combines low-rank matrix factorization with a sparsification mechanism for the continuous optimization of DAGs. The main contribution of the approach lies in an efficient gradient approximation method leveraging the low-rank property of the model, and its straightforward application to the computation of projections from graph matrices onto the DAG matrix space. The proposed method achieves a reduction from a cubic complexity to quadratic complexity while handling the same DAG characteristic function as NoTears, and scales easily up to thousands of nodes for the projection problem. The experiments show that the LoRAM achieves efficiency gains of orders of magnitude compared to the state-of-the-art at the expense of a very moderate accuracy loss in the considered range of sparse matrices, and with a low sensitivity to the rank choice of the model's low-rank component.

Related papers

• $ψ$DAG: Projected Stochastic Approximation Iteration for DAG Structure Learning [6.612096312467342]
  Learning the structure of Directed A Graphs (DAGs) presents a significant challenge due to the vast search space of possible graphs, which scales with the number of nodes. Recent advancements have redefined this problem as a continuous optimization task by incorporating differentiable a exponentiallyity constraints. We present a novel framework for learning DAGs, employing a Approximation approach integrated with Gradient Descent (SGD)-based optimization techniques.
  arXiv  Detail & Related papers  (2024-10-31T12:13:11Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Enhancing Low-Order Discontinuous Galerkin Methods with Neural Ordinary Differential Equations for Compressible Navier--Stokes Equations [0.18648070031379424]
  It is common to run a low-fidelity model with a subgrid-scale model to reduce the computational cost. We propose a novel method for learning the subgrid-scale model effects when simulating partial differential equations augmented by neural ordinary differential operators. Our approach learns the missing scales of the low-order DG solver at a continuous level and hence improves the accuracy of the low-order DG approximations.
  arXiv  Detail & Related papers  (2023-10-29T04:26:23Z)
• Probabilistic Unrolling: Scalable, Inverse-Free Maximum Likelihood Estimation for Latent Gaussian Models [69.22568644711113]
  We introduce probabilistic unrolling, a method that combines Monte Carlo sampling with iterative linear solvers to circumvent matrix inversions. Our theoretical analyses reveal that unrolling and backpropagation through the iterations of the solver can accelerate gradient estimation for maximum likelihood estimation. In experiments on simulated and real data, we demonstrate that probabilistic unrolling learns latent Gaussian models up to an order of magnitude faster than gradient EM, with minimal losses in model performance.
  arXiv  Detail & Related papers  (2023-06-05T21:08:34Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• Graph Polynomial Convolution Models for Node Classification of Non-Homophilous Graphs [52.52570805621925]
  We investigate efficient learning from higher-order graph convolution and learning directly from adjacency matrix for node classification. We show that the resulting model lead to new graphs and residual scaling parameter. We demonstrate that the proposed methods obtain improved accuracy for node-classification of non-homophilous parameters.
  arXiv  Detail & Related papers  (2022-09-12T04:46:55Z)
• An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification [97.28167655721766]
  We propose a novel doubly accelerated gradient descent (ADSGD) method for sparsity regularized loss minimization problems. We first prove that ADSGD can achieve a linear convergence rate and lower overall computational complexity.
  arXiv  Detail & Related papers  (2022-08-11T22:27:22Z)
• uGLAD: Sparse graph recovery by optimizing deep unrolled networks [11.48281545083889]
  We present a novel technique to perform sparse graph recovery by optimizing deep unrolled networks. Our model, uGLAD, builds upon and extends the state-of-the-art model GLAD to the unsupervised setting. We evaluate model results on synthetic Gaussian data, non-Gaussian data generated from Gene Regulatory Networks, and present a case study in anaerobic digestion.
  arXiv  Detail & Related papers  (2022-05-23T20:20:27Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Alternating minimization algorithms for graph regularized tensor completion [8.26185178671935]
  We consider a Canonical Polyadic (CP) decomposition approach to low-rank tensor completion (LRTC) The usage of graph regularization entails benefits in the learning accuracy of LRTC, but at the same time, induces coupling graph Laplacian terms. We propose efficient alternating minimization algorithms by leveraging the block structure of the underlying CP decomposition-based model.
  arXiv  Detail & Related papers  (2020-08-28T23:20:49Z)
• Estimation of sparse Gaussian graphical models with hidden clustering structure [8.258451067861932]
  We propose a model to estimate the sparse Gaussian graphical models with hidden clustering structure. We develop a symmetric Gauss-Seidel based alternating direction method of the multipliers. Numerical experiments on both synthetic data and real data demonstrate the good performance of our model.
  arXiv  Detail & Related papers  (2020-04-17T08:43:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.