The DOI matches its Crossref record; 46 of the 46 references it cites were found in a registry or an index.
Network Topology Inference from Spectral Templates
Open accessAbstract
We address the problem of identifying the structure of an undirected graph from the observation of signals defined on its nodes. Fundamentally, the unknown graph encodes direct relationships between signal elements, which we aim to recover from observable indirect relationships generated by a diffusion process on the graph. The fresh look advocated here leverages concepts from convex optimization and stationarity of graph signals, in order to identify the graph shift operator (a matrix representation of the graph) given only its eigenvectors. These spectral templates can be obtained, e.g., from the sample covariance of independent graph signals diffused on the sought network. The novel idea is to find a graph shift that, while being consistent with the provided spectral information, endows the network with certain desired properties such as sparsity. To that end, we develop efficient inference algorithms stemming from provably tight convex relaxations of natural nonconvex criteria, particularizing the results for two shifts: the adjacency matrix and the normalized Laplacian. Algorithms and theoretical recovery conditions are developed not only when the templates are perfectly known, but also when the eigenvectors are noisy or when only a subset of them are given. Numerical tests showcase the effectiveness of the proposed algorithms in recovering synthetic and real-world networks.
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
Introduction to information retrieval
(2009) · Choice Reviews Online · doi:10.5860/choice.46-2715 · Cited by 12,278
Introduction to Information Retrieval
Manning, C. D., Raghavan, P., & Schütze, H. (2008) · doi:10.1017/cbo9780511809071 · Cited by 11,288
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
Bollobás, B. (1985) · Cited by 6,196
Chung, F. (1996) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/092 · Cited by 5,524
Atomic Decomposition by Basis Pursuit
Chen, S. S., Donoho, D. L., & Saunders, M. A. (2001) · SIAM Review · doi:10.1137/s003614450037906x · Cited by 5,085
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
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
Mapping the structural core of human cerebral cortex
Hagmann, P., Cammoun, L., Gigandet, X., Meuli, R., Honey, C. J., Wedeen, V. J., & Sporns, O. (2008) · PLoS Biology · doi:10.1371/journal.pbio.0060159 · Cited by 4,173
Sparse Approximate Solutions to Linear Systems
Natarajan, B. K. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539792240406 · Cited by 2,783
Bollobás, B. (2001) · doi:10.1017/cbo9780511814068 · Cited by 2,639
Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality
Newman, M. E. J. (2001) · Physical Review E · doi:10.1103/physreve.64.016132 · Cited by 2,613
High 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
Discrete Signal Processing on Graphs
Sandryhaila, A., & Moura, J. M. F. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2238935 · Cited by 1,531
Protein 3D Structure Computed from Evolutionary Sequence Variation
Marks, D. S., Colwell, L. J., Sheridan, R., Hopf, T. A., Pagnani, A., Zecchina, R., & Sander, C. (2011) · PLoS ONE · doi:10.1371/journal.pone.0028766 · Cited by 1,144
Brovelli, A., Ding, M., Ledberg, A., Chen, Y., Nakamura, R., & Bressler, S. L. (2004) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0308538101 · Cited by 1,065
Statistical Analysis of Network Data: Methods and Models
Kolaczyk, E. D. (2009) · Springer Series in Statistics · doi:10.1007/978-0-387-88146-1 · Cited by 980
Discrete Signal Processing on Graphs: Frequency Analysis
Sandryhaila, A., & Moura, J. M. F. (2014) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2321121 · Cited by 879
NESTA: A Fast and Accurate First-Order Method for Sparse Recovery
Becker, S., Bobin, J., & Candès, E. J. (2011) · SIAM Journal on Imaging Sciences · doi:10.1137/090756855 · Cited by 848
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
Discrete Signal Processing on Graphs: Sampling Theory
Chen, S., Varma, R., Sandryhaila, A., & Kovacevic, J. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2469645 · Cited by 666
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
Numerical Analysis, A Second Course
de Boor, C. W., & Ortega, J. M. (1973) · Mathematics of Computation · doi:10.2307/2005671 · Cited by 556
Discovering the Human Connectome
Sporns, O. (2012) · The MIT Press eBooks · doi:10.7551/mitpress/9266.001.0001 · Cited by 350
Network deconvolution as a general method to distinguish direct dependencies in networks
Feizi, S., Marbach, D., Médard, M., & Kellis, M. (2013) · Nature Biotechnology · doi:10.1038/nbt.2635 · Cited by 287
Optimal Graph-Filter Design and Applications to Distributed Linear Network Operators
Segarra, S., Marques, A. G., & Ribeiro, A. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2703660 · Cited by 251
Self-citationStationary Signal Processing on Graphs
Perraudin, N., & Vandergheynst, P. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2690388 · Cited by 244
Stationary Graph Processes and Spectral Estimation
Marques, A. G., Segarra, S., Leus, G., & Ribeiro, A. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2739099 · Cited by 235
Self-citationLaplacian 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
Characterization and Inference of Graph Diffusion Processes From Observations of Stationary Signals
Pasdeloup, B., Gripon, V., Mercier, G., Pastor, D., & Rabbat, M. (2017) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2017.2742940 · Cited by 181
Cai, X., Bazerque, J. A., & Giannakis, G. B. (2013) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1003068 · Cited by 160
Stationary graph signals using an isometric graph translation
Girault, B. (2015) · European Signal Processing Conference (EUSIPCO) · doi:10.1109/eusipco.2015.7362637 · Cited by 150
Ortega, J. M. (1990) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971323 · Cited by 149
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
Slawski, M., & Hein, M. (2014) · Linear Algebra and its Applications · doi:10.1016/j.laa.2014.04.020 · Cited by 115
Reconstruction of Graph Signals Through Percolation from Seeding Nodes
Segarra, S., Marques, A. G., Leus, G. J. T., & Ribeiro, A. (2016) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2016.2552510 · Cited by 106
Self-citationProximal-Gradient Algorithms for Tracking Cascades Over Social Networks
Baingana, B., Mateos, G., & Giannakis, G. B. (2014) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2014.2317284 · Cited by 103
Self-citationSmoothing and Decomposition for Analysis Sparse Recovery
Tan, Z., Eldar, Y. C., Beck, A., & Nehorai, A. (2014) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2304932 · Cited by 95
Kernel-Based Structural Equation Models for Topology Identification of Directed Networks
Shen, Y., Baingana, B., & Giannakis, G. B. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2664039 · Cited by 94
Signal processing on graphs: Estimating the structure of a graph
Mei, J., & Moura, J. M. F. (2015) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2015.7179022 · Cited by 48
Multi-kernel based nonlinear models for connectivity identification of brain networks
Karanikolas, G. V., Giannakis, G. B., Slavakis, K., & Leahy, R. M. (2016) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2016.7472892 · Cited by 47
Distributed implementation of linear network operators using graph filters
Segarra, S., Marques, A. G., & Ribeiro, A. (2015) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2015.7447173 · Cited by 45
Self-citationInterpolation of graph signals using shift-invariant graph filters
Segarra, S., Marques, A. G., Leus, G. J. T., & Ribeiro, A. (2015) · European Signal Processing Conference (EUSIPCO) · doi:10.1109/eusipco.2015.7362375 · Cited by 41
Self-citationDistributed Linear Network Operators using Graph FiltersPreprint
Segarra, S., Marques, A. G., & Ribeiro, A. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1510.03947 · Cited by 21
Self-citationNetwork topology identification from imperfect spectral templates
Segarra, S., Marques, A. G., Mateos, G., & Ribeiro, A. (2016) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/acssc.2016.7869620 · Cited by 5
Self-citation
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
Xia, 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
Self-citationGraph Learning From Data Under Laplacian and Structural Constraints
Egilmez, H. E., Pavez, E., & Ortega, A. (2017) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2017.2726975 · Cited by 364
Metadata
- Authors
- Segarra, S., Marques, A. G., Mateos, G., & Ribeiro, A.
- Venue
- IEEE Transactions on Signal and Information Processing over Networks
- Published
- 2017-09
- Volume
- 3
- Issue
- 3
- Pages
- 467-483
- ISSN
- 2373-776X (ISSN-L)
- 2373-7778
- OpenAlex
- W2487418985
- Cited by
- 287
- References
- 46
- FWCI
- 21.32
- 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.