Multi-Attribute Graph Estimation with Sparse-Group Non-Convex Penalties

Jitendra K. Tugnait · 2025

Read Multi-Attribute Graph Estimation with Sparse-Group Non-Convex Penalties by Jitendra K. Tugnait (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-11984.txt.

Introduction

In many datasets each node carries a whole vector of values, not a single number, and the links between nodes must be inferred from data. Jitendra Tugnait, writing alone in 2025, studied how to estimate those link graphs for Gaussian data with several attributes per node. The goal is a conditional independence graph: an edge means two nodes relate directly, not through others.

Tugnait gives a unified theory for penalized likelihood methods, covering both convex penalties and sharper non-convex ones that better avoid false edges. An optimization method based on splitting the problem is presented, with proofs about recovering the true links. On synthetic data the log-sum penalty beat the standard lasso clearly; real data examples are also shown.

Catalog record

CREATORJitendra K. Tugnait
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE100 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-11984

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Multi-Attribute Graph Estimation with Sparse-Group Non-Convex Penalties Jitendra K. Tugnait Abstract We consider the problem of inferring the conditional independence graph (CIG) of high-dimensional Gaussian vectors from multi-attribute data. Most existing methods for graph estimation are based on single-attribute models where one associates a scalar random variable with each node. In multi-attribute graphical models, each node represents a random vector. In this paper we provide a unified theoretical analysis of multi-attribute graph learning using a penalized log-likelihood objective function. We consider both convex (sparse-group lasso) and sparse-group non-convex (log-sum and smoothly clipped absolute deviation (SCAD) penalties) penalty/regularization functions. An alternating direction method of multipliers (ADMM) approach coupled with local linear approximation to non-convex penalties is presented for optimization of the objective function. For non-convex penalties, theoretical analysis establishing local consistency in support recovery, local convexity and precision matrix estimation in high-dimensional settings is provided under two sets of sufficient conditions: with and without some irrepresentability conditions. We illustrate our approaches using both synthetic and real-data numerical examples. In the synthetic data examples the sparse-group log-sum penalized objective function significantly outperformed the lasso penalized as well as SCAD penalized objective functions with F 1 F_{1} -score and Hamming distance as performance metrics. I Introduction Graphical models provide a powerful tool for analyzing multivariate data [ 3 , 2 ] . In an undirected graphical model, the conditional dependency structure among p random variables x_{1},x_{2},\cdots,x_{p} , ( {\bm{x}}=[x_{1}\;x_{2}\;\cdots\;x_{p}]^{\top} ), is represented using an undirected graph {\cal G}=\left(V,{\cal E}\right) , where V=\{1,2,\cdots,p\}=[p] is the set of p nodes corresponding to the p random variables x_{i} ’s, and {\cal E}\subseteq[p]\times[p] is the set of undirected edges describing conditional dependencies among x_{i} ’s. The graph {\cal G} is a conditional independence graph (CIG) where there is no edge between nodes i and j if and only if (iff) x_{i} and x_{j} are conditionally independent given the remaining p - 2 variables. Gaussian graphical models (GGMs) are CIGs where {\bm{x}} is multivariate Gaussian. Suppose {\bm{x}} has positive-definite covariance matrix \bm{\Sigma} with inverse covariance matrix \bm{\Omega}=\bm{\Sigma}^{-1} . Then {\Omega}_{ij} , the (i,j) -th element of \bm{\Omega} , is zero iff x_{i} and x_{j} are conditionally independent. Given n samples of {\bm{x}} , in high-dimensional settings, one estimates \bm{\Omega} under some sparsity constraints; see, e.g., [ 4 , 5 , 6 , 7 ] . In these graphs each node represents a scalar random variable. In many applications, there may be more than one random variable associated with a node. This class of graphical models has been called multi-attribute graphical models in [ 8 , 9 , 10 ] and vector graphs or networks in [ 11 , 12 ] . In [ 9 ] , a sparse-group lasso [ 13 , 14 ] based penalized log-likelihood approach for graph learning from multi-attribute data was presented whereas [ 8 ] considers only group lasso [ 15 ] . Both sparse-group lasso and group lasso are convex penalties. It is well-known that use of non-convex penalties such as smoothly clipped absolute deviation (SCAD) [ 16 , 5 ] or log-sum [ 17 ] , can yield more accurate results. Such penalties can produce sparse set of solution like lasso, and approximately unbiased coefficients for large coefficients, unlike lasso. The objective of this paper is to investigate use of sparse-group non-convex log-sum and SCAD penalties for estimation of multi-attribute graphs. I-A Related Work Although non-convex penalties have been extensively used for graph estimation (see [ 5 , 18 , 21 , 22 , 19 , 20 ] and references therein), its use for multi-attribute graph estimation is almost non-existent with the exception of [ 23 ] where SCAD is investigated. In [ 9 ] , a sparse-group lasso based penalized log-likelihood approach for graph learning from multi-attribute data was presented whereas [ 8 ] considers only group lasso. In sparse-group lasso there is group level lasso penalty as well as element-wise lasso penalty (see equations ( 6 ) and ( 7 ) in Sec. III in the sequel). We extend the approach of [ 9 ] to non-convex sparse-group penalties. For analysis, we rely on the proof technique of [ 24 ] as well as the primal-dual witness technique of [ 6 ] , both originally used in the context of element-wise lasso penalty for single-attribute graphs. The technique of [ 6 ] was extended to group-lasso penalty for multi-attribute graphs in [ 8 ] . The SCAD penalty for multi-attribute graphs has been considered in [ 23 ] but it does not have counterparts to our Lemma 1 and Theorems 2-5. Moreover, the sparse-group SCAD penalty used in this paper is different than that in [ 23 ] . In this paper we apply the primal-dual witness technique in a sparse-group non-convex penalty setting. Some prior results in an element-wise non-convex penalty setting are in [ 21 , 22 ] . For numerical optimization of the penalized log-likelihood we exploit an alternating direction method of multipliers (ADMM) approach [ 25 ] as in [ 9 , 23 ] , where for non-convex penalties (SCAD or log-sum), we use a local linear approximation of the penalties ( [ 18 , 5 , 23 ] ), initialized via sparse-group lasso results of [ 9 ] . I-B Our Contributions In this paper we provide a unified theoretical analysis of multi-attribute graph learning using a penalized log-likelihood objective function where both convex (sparse-group lasso) and non-convex (sparse-group log-sum and SCAD) penalty/regularization functions are considered. We establish sufficient conditions in a high-dimensional setting for consistency (convergence of the precision matrix to true value in the Frobenius norm), local convexity when using non-convex penalties, and graph recovery. Two alternative sets of sufficient conditions are investigated, with and without some irrepresentability conditions. For the latter, we follow the proof technique of [ 24 ] (as in [ 9 ] ), and for the former, we follow the primal-dual witness technique of [ 6 ] (as in [ 8 ] ), both applied in a sparse-group setting. Theoretical results not relying on irrepresentability conditions are in Theorems 1-3 and that based on some irrepresentability conditions are in Theorems 4 and 5. While the non-convex penalized log-likelihood objective function results in a non-convex optimization problem, Theorems 2 and 4 specify conditions under which it becomes a convex optimization problem (see Remark 2 in Sec. V-A ). These conditions favor log-sum penalty over SCAD. A preliminary version of parts of this paper appears in a conference paper [ 26 ] . Theorems 4-5, proof of Theorem 3, and synthetic and real data examples do not appear in [ 26 ] . Only sketches of proofs of Theorems 1 and 2 appear in [ 26 ] . I-C Outline The rest of the paper is organized as follows. The system model is presented in Sec. II where we describe the multi-attribute graphical model with m random variables per node, and also an associated larger single-attribute graph. A penalized log-likelihood objective function is presented in Sec. III for estimation of multi-attribute graph using non-convex penalties. An ADMM approach coupled with a local linear approximation to non-convex penalties is presented for optimization of the objective function in Sec. IV . In

Read the complete text