The DOI matches its Crossref record; 53 of the 53 references it cites were found in a registry or an index.
Graph Learning From Data Under Laplacian and Structural Constraints
Open accessAbstract
Graphs are fundamental mathematical structures used in various fields to represent data, signals, and processes. In this paper, we propose a novel framework for learning/estimating graphs from data. The proposed framework includes (i) formulation of various graph learning problems, (ii) their probabilistic interpretations, and (iii) associated algorithms. Specifically, graph learning problems are posed as the estimation of graph Laplacian matrices from some observed data under given structural constraints (e.g., graph connectivity and sparsity level). From a probabilistic perspective, the problems of interest correspond to maximum a posteriori parameter estimation of Gaussian-Markov random field models, whose precision (inverse covariance) is a graph Laplacian matrix. For the proposed graph learning problems, specialized algorithms are developed by incorporating the graph Laplacian and structural constraints. The experimental results demonstrate that the proposed algorithms outperform the current state-of-the-art methods in terms of accuracy and computational efficiency.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
Regression shrinkage and selection via the lasso
Tibshirani, R. (1996) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1996.tb02080.x · Cited by 51,482
A tutorial on spectral clustering
von Luxburg, U. (2007) · Statistics and Computing · doi:10.1007/s11222-007-9033-z · Cited by 10,349
Koller, D., & Friedman, N. (2009) · The MIT Press eBooks · Cited by 7,555
Fundamentals of digital image processing
Jain, A. K. (1988) · Cited by 7,111
Sparse inverse covariance estimation with the graphical lasso
Friedman, J., Hastie, T., & Tibshirani, R. (2008) · Biostatistics · doi:10.1093/biostatistics/kxm045 · Cited by 6,355
Enhancing Sparsity by Reweighted ℓ 1 Minimization
Candès, E. J., Wakin, M. B., & Boyd, S. P. (2008) · Journal of Fourier Analysis and Applications · doi:10.1007/s00041-008-9045-x · Cited by 4,863
Fundamentals of digital image processing
(1989) · Computer Vision, Graphics, and Image Processing · doi:10.1016/0734-189x(89)90041-8 · Cited by 4,677
Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., & Vandergheynst, P. (2013) · IEEE Signal Processing Magazine · doi:10.1109/msp.2012.2235192 · Cited by 4,421 · cited 3×
“Moreover, weighted graphs naturally emerge in networked data applications, such as learning, signal processing and analysis on computer, social, sensor, energy, transportation and biological networks [4], where the signals/data are inherently related to a graph associated with the underlying network.”
BackgroundMethodSelf-citationHigh dimensional graphs and variable selection with the Lasso
Meinshausen, N., & Bühlmann, P. (2006) · Cited by 2,539
High-dimensional graphs and variable selection with the Lasso
Meinshausen, N., & Bühlmann, P. (2006) · The Annals of Statistics · doi:10.1214/009053606000000281 · Cited by 2,521 · cited 1×
“Later, a neighborhood selection approach was proposed for graphical model estimation [31] by using the Lasso algorithm [32].”
MethodRue, H., & Held, L. (2005) · Chapman & Hall/CRC eBooks · doi:10.1201/9780203492024 · Cited by 1,823
Statistics for High-Dimensional Data: Methods, Theory and Applications
Bühlmann, P., & van de Geer, S. (2011) · Springer Series in Statistics · doi:10.1007/978-3-642-20192-9 · Cited by 1,680
Statistics for High-Dimensional Data: Methods, Theory and Applications
Bhlmann, P., & van de Geer, S. (2011) · Cited by 1,527
Wright, S. J. (2015) · Mathematical Programming · doi:10.1007/s10107-015-0892-3 · Cited by 1,438
Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix
Sherman, J., & Morrison, W. J. (1950) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729893 · Cited by 1,402 · cited 1×
“After adding a scalar value ν to (Θ)ii, we use the Sherman-Morrison formula [51] to update C as”
MethodBanerjee, O., Ghaoui, L. E., & d’Aspremont, A. (2007) · arXiv (Cornell University) · doi:10.1145/1390681.1390696 · Cited by 1,233
Spike and slab variable selection: Frequentist and Bayesian strategies
Ishwaran, H., & Rao, J. S. (2005) · The Annals of Statistics · doi:10.1214/009053604000001147 · Cited by 1,033
(2000) · Electric Power System Applications of Optimization · doi:10.1201/9781420056266-13 · Cited by 908
Dempster, A. P. (1972) · Biometrics · doi:10.2307/2528966 · Cited by 905
Kernels and Regularization on Graphs
Smola, A. J., & Kondor, R. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45167-9_12 · Cited by 841
1Kron Reduction of Graphs with Applications to Electrical Networks
Bullo, F. (2015) · Cited by 821
High-dimensional covariance estimation by minimizing ℓ1-penalized log-determinant divergence
Ravikumar, P., Wainwright, M. J., Raskutti, G., & Yu, B. (2011) · Electronic Journal of Statistics · doi:10.1214/11-ejs631 · Cited by 744
The discovery of structural form
Kemp, C., & Tenenbaum, J. B. (2008) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0802631105 · Cited by 650
Learning Laplacian Matrix in Smooth Graph Signal Representations
Dong, X., Thanou, D., Frossard, P., & Vandergheynst, P. (2016) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2016.2602809 · Cited by 640
A Tour of Modern Image Filtering: New Insights and Methods, Both Practical and Theoretical
Milanfar, P. (2013) · IEEE Signal Processing Magazine · doi:10.1109/msp.2011.2179329 · Cited by 605
On the Convergence of Block Coordinate Descent Type Methods
Beck, A., & Tetruashvili, L. (2013) · SIAM Journal on Optimization · doi:10.1137/120887679 · Cited by 572
Spielman, D. A., & Teng, S. (2014) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/090771430 · Cited by 462
Perfect Reconstruction Two-Channel Wavelet Filter Banks for Graph Structured Data
Narang, S. K., & Ortega, A. (2012) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2012.2188718 · Cited by 387
Self-citationEfficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
Anis, A., Gadde, A., & Ortega, A. (2016) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2016.2546233 · Cited by 336
Self-citationSpielman, D. A., & Teng, S.-H. (2013) · SIAM Journal on Computing · doi:10.1137/080744888 · Cited by 316
Network Topology Inference from Spectral Templates
Segarra, S., Marques, A. G., Mateos, G., & Ribeiro, A. (2017) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2017.2731051 · Cited by 287
The graphical lasso: New insights and alternatives
Mazumder, R., & Hastie, T. (2012) · Electronic Journal of Statistics · doi:10.1214/12-ejs740 · Cited by 267
BIG & QUIC: Sparse Inverse Covariance Estimation for a Million Variables
Hsieh, C., Sustik, M. A., Dhillon, I. S., Ravikumar, P., & Poldrack, R. A. (2013) · neural information processing systems · Cited by 219
Laplacian Eigenvectors of Graphs
Biyikoğu, T., Leydold, J., & Stadler, P. F. (2007) · Lecture Notes in Mathematics · doi:10.1007/978-3-540-73510-6 · Cited by 214
Nonnegativity constraints in numerical analysis
Chen, D., & Plemmons, R. J. (2009) · The Birth of Numerical Analysis · doi:10.1142/9789812836267_0008 · Cited by 206
Loh, P., & Wainwright, M. J. (2013) · The Annals of Statistics · doi:10.1214/13-aos1162 · Cited by 205
Matrix Nearness Problems with Bregman Divergences
Dhillon, I. S., & Tropp, J. A. (2008) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/060649021 · Cited by 189
Spectral sparsification of graphs
Batson, J., Spielman, D. A., Srivastava, N., & Teng, S. (2013) · Communications of the ACM · doi:10.1145/2492007.2492029 · Cited by 154
Exact covariance thresholding into connected components for large-scale Graphical LassoPreprint
Mazumder, R., & Hastie, T. J. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1108.3829 · Cited by 132
Generalized Laplacian precision matrix estimation for graph signal processing
Pavéz, E., & Ortega, A. (2016) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2016.7472899 · Cited by 124
Self-citationSpectral anomaly detection using graph-based filtering for wireless sensor networks
Egilmez, H. E., & Ortega, A. (2014) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2014.6853764 · Cited by 117
Self-citationSlawski, M., & Hein, M. (2014) · Linear Algebra and its Applications · doi:10.1016/j.laa.2014.04.020 · Cited by 115
Analyzing the Optimality of Predictive Transform Coding Using Graph-Based Models
Zhang, C., & Florencio, D. A. F. (2012) · IEEE Signal Processing Letters · doi:10.1109/lsp.2012.2230165 · Cited by 105
Portugal, L., Júdice, J. J., & Vicente, L. N. (1994) · Mathematics of Computation · doi:10.2307/2153286 · Cited by 96
High-dimensional covariance estimation based on Gaussian graphical modelsPreprint
Zhou, S., Rütimann, P., Xu, M., & Bühlmann, P. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1009.0530 · Cited by 87
Determinant Inequalities via Information Theory
Cover, T. M., & Thomas, A. (1988) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0609033 · Cited by 80
Woods, J. (2012) · Elsevier eBooks · doi:10.1016/b978-0-12-381420-3.00011-4 · Cited by 71
Topology identification of undirected consensus networks via sparse inverse covariance estimation
Hassan-Moghaddam, S., Dhingra, N. K., & Jovanović, M. R. (2016) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2016.7798973 · Cited by 38
Grechkin, M., Fazel, M., Witten, D., & Lee, S. (2015) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v29i1.9636 · Cited by 25
Algorithms, Graph Theory, and the Solution of Laplacian Linear Equations
Spielman, D. A. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-31585-5_5 · Cited by 11
Graph learning with Laplacian constraints: Modeling attractive Gaussian Markov random fields
Egilmez, H. E., Pavéz, E., & Ortega, A. (2016) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/acssc.2016.7869621 · Cited by 11
Self-citationThe f -Adjusted Graph Laplacian: a Diagonal Modification with a Geometric Interpretation
Kurras, S., Ulrike Von Luxburg, A., & Blanchard, G. (2014) · HAL · Cited by 5
Cited by
Graph Signal Processing: Overview, Challenges, and Applications
Ortega, A., Frossard, P., Kovačević, J., Moura, J. M. F., & Vandergheynst, P. (2018) · Proceedings of the IEEE · doi:10.1109/jproc.2018.2820126 · Cited by 1,787
Self-citationXia, F., Sun, K., Yu, S., Aziz, A., Wan, L., Pan, S., & Liu, H. (2021) · IEEE Transactions on Artificial Intelligence · doi:10.1109/tai.2021.3076021 · Cited by 473
Learning Graphs From Data: A Signal Representation Perspective
Dong, X., Thanou, D., Rabbat, M., & Frossard, P. (2019) · IEEE Signal Processing Magazine · doi:10.1109/msp.2018.2887284 · Cited by 406
Connecting the Dots: Identifying Network Structure via Graph Signal Processing
Mateos, G., Segarra, S., Marques, A. G., & Ribeiro, A. (2019) · IEEE Signal Processing Magazine · doi:10.1109/msp.2018.2890143 · Cited by 369
Non-Negative Kernel Graphs for Time-Varying Signals Using Visibility Graphs
Bozkurt, E., & Ortega, A. (2022) · 2022 30th European Signal Processing Conference (EUSIPCO) · doi:10.23919/eusipco55093.2022.9909594 · Cited by 1
Self-citation
Metadata
- Authors
- Egilmez, H. E., Pavez, E., & Ortega, A.
- Venue
- IEEE Journal of Selected Topics in Signal Processing
- Published
- 2017-09
- Volume
- 11
- Issue
- 6
- Pages
- 825-841
- ISSN
- 1932-4553 (ISSN-L)
- 1941-0484
- OpenAlex
- W2615556757
- Cited by
- 364
- References
- 53
- FWCI
- 20.66
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.