Research map / Learning theory and algorithms / Matrix and tensor methods
Efficient Network Automatic Relevance Determination
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Network ARD (NARD), a matrix-normal ARD model with graphical-lasso output covariance, plus Sequential, Surrogate and Hybrid variants that cut per-iteration cost for high-dimensional multi-output regression.
Problem
Standard ARD for multi-output linear regression costs O(d^3) per iteration, and joint sparse mean-covariance estimation is computationally heavy for high-dimensional inputs and outputs (e.g., omics data).
Approach
Extends ARD to multi-output regression with a matrix normal prior whose output covariance is sparsified via graphical lasso, and reduces cost via sequential feature add/delete based on a closed-form alpha update and a surrogate (Lipschitz-based) lower bound that makes the column covariance diagonal.
Key results
- On synthetic data (d=5000, m=1500, N=1500), Hybrid NARD ran in 23 total time units vs 53 for MRCE, with TPR 0.9471 and FPR 0.0068 comparable to HS-GHS (TPR 0.9463, FPR 0.0033 but >3000 time).
- At N=20000, m=2000, d=20000, Surrogate NARD took 33.7 s per iteration versus 168.6 s for NARD and 201.9 s for MRCE.
- On A-shares data (m=3032, d=60640), Surrogate NARD reached Jaccard 0.893 in 5.5 h total, versus 17 h for MRCE.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Sequential NARD instead of NARD | NARD · Synthetic data (p=0.1, d=5000, m=1500, N=1500) | Time (Total): 49 -> 35 | Helped |
| Use Surrogate NARD instead of NARD | NARD · Synthetic data (p=0.1, d=5000, m=1500, N=1500) | Time (Total): 49 -> 31 | Helped |
| Combine sequential updates with the surrogate function method | NARD · Synthetic data (p=0.1, d=5000, m=1500, N=1500) | Time (Total): 49 -> 23 | Helped |
| Use Sequential NARD instead of NARD | NARD · Synthetic data (p=0.1, d=5000, m=1500, N=1500) | TPR: 0.9483 -> 0.9459 | Hurt |
| Use Surrogate NARD instead of NARD | NARD · Synthetic data (p=0.1, d=5000, m=1500, N=1500) | TPR: 0.9483 -> 0.9462 | Hurt |
| Combine sequential updates with the surrogate function method | NARD · Synthetic data (p=0.1, d=5000, m=1500, N=1500) | TPR: 0.9483 -> 0.9471 | Hurt |
| Use Surrogate NARD instead of NARD | NARD · Aging phenotype data | Jaccard index: 0.988 -> 0.989 | Helped |
| Use Hybrid NARD instead of NARD | NARD · Aging phenotype data | Jaccard index: 0.988 -> 0.989 | Helped |
Surprising findings
- Surrogate NARD sometimes shows numerical instability on large real-world high-dimensional data, per the appendix discussion.
- The Bayesian baselines HS-GHS and JRNS could not finish on the larger A-shares dataset within 4 days.
Limitations
- Surrogate NARD can be numerically unstable on ill-conditioned high-dimensional real data.
- Model is linear (nonlinear extension via kernels only briefly evaluated on aging data).
- Hyperprior and the sequential update rely on heuristic choices; the prior on V is restricted to flat prior in main analysis.
Experimental setup
Datasets: synthetic Erdos-Renyi data aging phenotype cohort (1022 individuals) TCGA cancer RPPA and mRNA data Beijing multi-site air quality A-shares stock data
Benchmarks: synthetic data (TPR/FPR) aging phenotype Jaccard index TCGA pathway associations A-shares Jaccard index air quality
Metrics: TPR FPR Jaccard index CPU time
Baselines: MRCE CAPME HS-GHS JRNS
Builds on: Automatic Relevance Determination Graphical Lasso Tipping's sparse Bayesian learning greedy update MRCE
Closest papers by meaning
- Inferring Dynamic Networks from Marginals with Iterative Proportional Fitting (ICML 2024 · similarity 0.82)
- NUDGE: Lightweight Non-Parametric Fine-Tuning of Embeddings for Retrieval (ICLR 2025 · similarity 0.82)
- Explainable Neural Networks with Guarantee: A Sparse Estimation Approach (AAAI 2025 · similarity 0.81)
- Graph Structure Inference with BAM: Neural Dependency Processing via Bilinear Attention (NeurIPS 2024 · similarity 0.81)
- NetInfoF Framework: Measuring and Exploiting Network Usable Information (ICLR 2024 · similarity 0.81)
- SPAC: Sparse Partitioning and Adaptive Core Tensor Pruning Model for Knowledge Graph Completion (AAAI 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.