PaperlayerView exact revision on arXiv

Source-linked AI summary

Causal Network Inference via Group Sparse Regularization

Andrew Bolstad, Barry Van Veen, Robert Nowak

arXiv:1106.0762v1stat.ML

TL;DR

The paper asks when sparse causal networks represented by multivariate autoregressive processes can be reliably inferred in high-dimensional, limited-sample settings. It analyzes Group Lasso consistency through a false connection score and proposes a self-connected variant, showing that recovery is supported when the score is below one and that the score remains informative in finite-sample studies.

  • Problem

    Inferring sparse causal-network structure is challenging when the number of observations is smaller than the number of MAR parameters, especially with limited data and changing connectivity patterns.

  • Method

    The paper derives Group Lasso consistency conditions for SMART models, defines the false connection score, and proposes SCSG by removing penalties on self-connections.

  • Results

    When ψmax < 1, SG and SCSG can recover the true network structure with high probability, while ψmax > 1 implies false positives with high probability; the score also indicates recovery performance at relatively small sample sizes.

  • Takeaways & Limitations

    The false connection score provides a practical indicator of identifiability and recovery, while SCSG can improve recovery by treating self-connections differently.

  • Takeaways & Limitations

    The consistency condition requires networks to be sparse and sufficiently independent across nodes, so it may not hold for all realistic network structures.

Abstract

from arXiv · show

This paper addresses the problem of inferring sparse causal networks modeled by multivariate auto-regressive (MAR) processes. Conditions are derived under which the Group Lasso (gLasso) procedure consistently estimates sparse network structure. The key condition involves a "false connection score." In particular, we show that consistent recovery is possible even when the number of observations of the network is far less than the number of parameters describing the network, provided that the false connection score is less than one. The false connection score is also demonstrated to be a useful metric of recovery in non-asymptotic regimes. The conditions suggest a modified gLasso procedure which tends to improve the false connection score and reduce the chances of reversing the direction of causal influence. Computational experiments and a real network based electrocorticogram (ECoG) simulation study demonstrate the effectiveness of the approach.

I. INTRODUCTION

The paper formulates causal-network inference with sparse multivariate autoregressive models and develops group-sparse estimation for identifying directed connections. It characterizes when Group Lasso can recover network structure despite high dimensionality and introduces a self-connection variant aimed at improving recovery.

  • I. INTRODUCTION: MAR models represent each node’s current measurement as a linear combination of past measurements from all nodes plus innovation noise.The autoregressive coefficients encode directed influence at different time delays, and the model supports Granger-causality analysis.
  • I. INTRODUCTION: Sparse MAR networks are difficult to infer because noisy, finite time series cannot reliably estimate the many coefficients of an overparameterized fully connected model.The key inference task is identifying the active connection set; coefficient estimation becomes simpler once that structure is known.
  • I. INTRODUCTION: Group Lasso matches the network’s group structure by penalizing collections of delay coefficients corresponding to connections between node pairs.Unlike ordinary Lasso, the grouped penalty favors solutions with only a small number of nonzero connection groups.
  • I. INTRODUCTION: The paper’s false connection score characterizes consistency: scores below one permit high-probability recovery, whereas scores above one imply false positives asymptotically.This condition remains relevant when the number of observations grows much more slowly than the network size.
  • I. INTRODUCTION: Self-Connected SMART gLasso removes the penalty on each node’s own past and typically lowers the false connection score relative to standard SMART gLasso.The paper evaluates this variant through example networks, simulations, and a macaque-brain connectivity study.

B. Graphical Model Identification

The paper develops SMART-specific consistency conditions for Group Lasso recovery of directed, temporally structured causal networks. Its analysis centers on a false connection score that characterizes recoverability and motivates a self-connection-aware variant.

  • B. Graphical Model Identification: SMART gLasso consistency requires conditions tailored to autoregressive design dependence, rather than directly applying standard gLasso incoherence results.The analysis uses the MAR structure of the design matrix and derives conditions analogous in spirit to incoherence conditions but different in form.
  • B. Graphical Model Identification: Under the stated scaling, signal-strength, power, and false-connection conditions, SG recovers the exact active-link set with probability greater than 1−exp(−Θ(n)).The theorem allows the network dimension to grow polynomially with the number of observations, including cases where network size grows faster than sample size.
  • B. Graphical Model Identification: The false connection score measures whether inactive predictors can be explained through active predictors, and it is central to controlling false links.The paper interprets the key assumption as requiring nodes without direct influence to be difficult to predict from direct parent nodes.
  • B. Graphical Model Identification: If the false connection score exceeds 1+c for any node pair, SG fails to recover the true connections with probability exceeding 1−exp(−Θ(n)).This establishes the score as a necessary condition for recovery for a large class of networks, including fixed-size networks.
  • B. Graphical Model Identification: SCSG leaves self-connections unpenalized and retains a high-probability exact-recovery guarantee under a modified false-connection condition.The paper argues that this variant typically lowers the false connection score for SMART models.

IV. NETWORK RECOVERY

The paper next shifts from asymptotic guarantees to the practically relevant finite-sample behavior of SMART network recovery. It examines how the derived conditions apply when network parameters are fixed and observations increase.

  • IV. NETWORK RECOVERY: Finite-sample regimes connect the asymptotic consistency results to recovery performance when network parameters are fixed and the number of measurements grows.The following subsection specializes this setting to fixed-parameter networks.

A. Recovery of Finite Parameter Networks

For fixed-parameter SMART networks, recovery depends primarily on whether the false connection score is below the consistency threshold. The paper provides a covariance-based route for computing this score from the model structure.

  • A. Recovery of Finite Parameter Networks: For fixed SMART parameters, SG recovers the correct network with probability greater than 1−exp(−Θ(n)) when its false connection score satisfies the recovery condition.With fixed m, p, and N, the scaling requirement reduces to a condition on λ, while the remaining assumptions are automatically satisfied under driving noise.
  • A. Recovery of Finite Parameter Networks: If the corresponding false connection score exceeds the threshold, SG fails to recover the correct structure with probability exceeding 1−exp(−Θ(n)); the analogous statement holds for SCSG.The paper therefore presents the score as a practical diagnostic for whether a given SMART structure is recoverable by either procedure.
  • A. Recovery of Finite Parameter Networks: The score can be evaluated from the MAR coefficients and covariance sequence by forming the relevant covariance blocks and calculating the predictor matrices for active and inactive nodes.The paper defines Γ(τ), constructs the coefficient and noise-covariance collections, and uses a closed-form covariance expression to obtain the required matrices.
  • A. Recovery of Finite Parameter Networks: The resulting score is compared with one using the paper’s false-connection formulas for SG or SCSG.This supplies a direct structural check for fixed-parameter network recoverability.

C. Challenges in Realistic Networks

Realistic network inference is challenged by correlated, limited, and time-varying data, while normalization and regularization choices affect recovery. Example networks show that false connection scores help characterize recoverability and that SCSG can reduce certain false causal directions.

  • Dependence in realistic data: Correlated rows in realistic Toeplitz designs violate the independence assumption, but simulations indicate that the false alarm score affects performance more strongly than row dependence.Rows decorrelate as the time lag grows, and prior first-order autoregressive analysis provides a lower bound on required observations.
  • Finite-sample challenges: When n is limited, recovering all connections—especially weak ones—becomes less likely, while selecting λ requires balancing missed connections against false positives.Calculating connection-level p-values for a specified λ remains an open problem, motivating solution paths over varying λ and cross-validation.
  • Normalization: Normalization tends to decrease the maximum false connection score, improving asymptotic recoverability, but can weaken connections and hinder finite-sample recovery.The trade-off arises because normalization changes connection strengths even as it improves the score used for asymptotic identifiability.
  • Example networks: Example topologies use false connection scores to assess identifiability, with scores below one supporting recovery as n approaches infinity for both SG and SCSG in the circle network.The circle network has maximum false connection score 0.43, and both methods recover its connectivity asymptotically.
  • Example networks: In the parallel network, SCSG reduces asymptotic false links from a child to its parent-related nodes, although both methods still falsely connect node 2 to node 1.The example attributes the persistent false link to four parallel paths and notes that an additional unconnected node does not change the false connection score.

VI. SIMULATIONS

Finite-sample simulations compare SG and SCSG on circle and parallel networks, showing that SCSG improves recovery when penalizing self-connections creates misleading alternatives. Recovery improves with more samples, but weak links remain harder to identify and some false connections persist.

  • Circle network: In the circle network, most true connections are identified, while the weakest links 2→3 and 4→1 are missed most often.SCSG identifies 2→3 considerably more often, and SG’s most common false connection occurs in only 2 of 30 trials.
  • Parallel network: The parallel network’s five most common false connections reverse the true causal direction, with four having false connection score 1.93 and one occurring in 80% of trials.The four links from node 1 to nodes 3–6 have score 1.93; the node 1→2 false connection has score 1.41.
  • Parallel network: SCSG substantially improves parallel-network recovery, whereas SG misses all true connections into node 1 and repeatedly selects incorrect links.SG identifies the 1→6 false connection in every case; SCSG nearly always finds node 2→nodes 3–6, though it still misses some links into node 1.
  • Penalty design: Penalizing self-connections can prevent SG from selecting true incoming links, whereas leaving self-connections unpenalized lets lower regularization activate other-node connections.With SG, decreasing λ below λ∗ first activates the self-connection; with SCSG, self-connections are already present.
  • Sample-size effects: Increasing the sample count from n = 50 to n = 150 noticeably improves identification of true connections.Additional simulations with n = 50 and n = 100 show that SCSG recovery improves with sample size, although some false connections also become more frequent.

VII. MACAQUE BRAIN SIMULATION

The macaque-brain simulations evaluate SCSG against several network-estimation methods on physical and sparse active-connectivity models. SCSG performs strongly when observations are fewer than coefficients, but the full network violates the false-connection condition while many individual node neighborhoods remain recoverable.

  • Simulation design: The simulations use a 71-node macaque connectivity matrix with 746 physical connections, comparing all-active connectivity with models having up to ten active parents per node.The two simulated networks represent dense physical connectivity and a sparse active subset, respectively.
  • Full network: Normalization reduces the full-network SCSG false connection score from 1.73 to 1.25, so asymptotic consistency is not guaranteed.Despite this violation, the parents of 67 nodes can be recovered accurately; four problematic neighborhoods resemble the parallel-network topology.
  • Sparse subset: Sparse active-connectivity networks may remain recoverable even when some full-network neighborhoods violate the false-connection condition.Only four nodes violate the condition in the described subset setting, and their neighborhood structure is linked to the parallel-network example.
  • ROC evaluation: ROC curves vary λ to compare SCSG, standard Lasso, least squares, ridge regression, and M&B without selecting a single regularization parameter.A detection is a nonzero estimate coinciding with a true directed connection, while a miss is a zero estimate for such a connection.
  • ROC evaluation: With n = 300 samples and 30,246 coefficients, SCSG and Lasso clearly outperform least squares, ridge regression, and M&B, which perform near coin flipping.SCSG outperforms Lasso because grouped penalties better match the true connection structure.
  • Conclusion: The study’s broader conclusion is that grouped sparse estimation can recover causal structure with fewer observations than coefficients when the network satisfies the false-connection condition.The paper identifies ψmax < 1 as the key condition for identifiability and presents SCSG as a modified gLasso procedure.

APPENDIX A PROOF OF ASYMPTOTIC CONSISTENCY

The appendix proves asymptotic recovery by analyzing an oracle group-sparse solution and then showing that its active blocks remain nonzero and satisfy the full optimization conditions with high probability. Gaussian concentration and covariance bounds control the relevant error terms.

  • Concentration bounds: Gaussian concentration and union bounds provide exponentially high-probability control of the stochastic terms used in the consistency proof.The appendix repeatedly invokes bounds with probabilities of the form 1 − exp(−Θ(n)).
  • Oracle recovery: The proof first analyzes an oracle solution with the active set known, targeting nonzero estimates for every active coefficient block.The argument assumes active-set knowledge temporarily, then establishes conditions under which the oracle solution is also the overall solution.
  • KKT verification: The regularization parameter must be large enough to suppress inactive groups but not so large that it eliminates active coefficient blocks.The proof separately checks inactive-block conditions and the nonzero active-block KKT conditions.
  • Regularity conditions: The proof requires the sample size to grow faster than the product of the maximum parent count and model order so the active-design covariance is invertible for large n.The appendix states this through the assumption that n grows faster than mp.
  • Oracle recovery: Under the stated growth assumptions, active-block estimation errors vanish with high probability, ensuring every true group remains nonzero asymptotically.The proof uses bounds on inverse sample covariance matrices and Gaussian quadratic forms, with probabilities exceeding 1 − exp(−Θ(n)).

Limiting False Positives

The limiting-false-positive argument uses KKT conditions to bound inactive-group correlations after conditioning on an oracle active solution. The false connection score controls the dominant term, while the remaining stochastic terms vanish asymptotically.

  • Full optimization: The oracle solution is embedded into the full parameter vector, and the proof verifies that it satisfies the full problem’s KKT conditions with high probability.This step links the active-set oracle analysis to the absence of false positives in the unrestricted optimization problem.
  • Term decomposition: The proof decomposes each inactive-group condition into three terms involving predictable structure, the false-connection contribution, and stochastic residual effects.The second term is controlled directly by Assumption 6; the other terms are bounded separately using Gaussian lemmas.
  • Concentration bound: A Gaussian concentration lemma bounds ∥V^T w∥_2 for random design and residual vectors with probability exceeding 1 − p exp(−n).The bound is obtained by controlling each coordinate with a chi-square tail bound and applying a union bound.
  • KKT condition: No false positives occur when the KKT bound for each inactive group is less than one.The dominant term is bounded by Cfc < 1 under the false-connection assumption, while the first and third terms vanish with increasing n.

Union Bound

The proof extends correct-parent recovery for node 1 to the whole network using a union bound.

  • Node 1’s correct parent set is recovered with probability exceeding 1 − exp(−Θ(n)).

APPENDIX B PROOF OF NECESSARY CONDITION

The appendix proves a necessary scaling condition by contradiction: under the stated assumptions, avoiding false positives forces a bound that conflicts with the growth regime n > m2p.

  • Assuming false positives vanish while oracle coefficient blocks remain nonzero forces KKT condition (12) to hold with high probability.
  • The proof derives a lower bound on λ using Assumption 3, equation (16), and the fact that mp/n tends to zero.
  • KKT-based bounds make the left-hand side of (25) smaller than Cpower while its right-hand side is Ω(n/m), yielding a contradiction when n grows faster than m2p.
  • The scaling law n > m2p, equivalently 2c2 + c3 < 1, is not needed for asymptotic consistency and may be improvable with other proof techniques.

APPENDIX C PROOF OF COROLLARY 1

The corollary proof follows Theorem 1 with minor changes, including a modified KKT condition for l = 1 and replacing m by m − 1 in Lemma 1's application.

  • The proof reuses Theorem 1 with a few minor changes.
  • For l = 1, the KKT condition implies ˆz1,1 = 0.
  • Lemma 1 remains applicable after replacing m with m − 1.
Loading 1106.0762v1…