ADVANCED SEARCH
Journals & Magazines >IEEE Signal Processing Magazine >Volume: 36 Issue: 3

Learning Graphs From Data: A Signal Representation Perspective

Publisher: IEEE
PDF
All Authors
Abstract:
The construction of a meaningful graph topology plays a crucial role in the effective representation, processing, analysis, and visualization of structured data. When a natural choice of the graph is not readily available from the data sets, it is thus desirable to infer or learn a graph topology from the data. In this article, we survey solutions to the problem of graph learning, including classical viewpoints from statistics and physics, and more recent approaches that adopt a graph signal processing (GSP) perspective. We further emphasize the conceptual similarities and differences between classical and GSP-based graph-inference methods and highlight the potential advantage of the latter in a number of theoretical and practical scenarios. We conclude with several open issues and challenges that are keys to the design of future signal processing and machine-learning algorithms for learning graphs from data.
Published in: IEEE Signal Processing Magazine ( Volume: 36, Issue: 3, May 2019)
Page(s): 44 - 63
Date of Publication: 06 May 2019
ISSN Information:
INSPEC Accession Number: 18621116
DOI: 10.1109/MSP.2018.2887284
Publisher: IEEE

The construction of a meaningful graph topology plays a crucial role in the effective representation, processing, analysis, and visualization of structured data. When a natural choice of the graph is not readily available from the data sets, it is thus desirable to infer or learn a graph topology from the data. In this article, we survey solutions to the problem of graph learning, including classical viewpoints from statistics and physics, and more recent approaches that adopt a graph signal processing (GSP) perspective. We further emphasize the conceptual similarities and differences between classical and GSP-based graph-inference methods and highlight the potential advantage of the latter in a number of theoretical and practical scenarios. We conclude with several open issues and challenges that are keys to the design of future signal processing and machine-learning algorithms for learning graphs from data.

Sign in to Continue Reading
More Like This
Learning Laplacian Matrix in Smooth Graph Signal Representations

IEEE Transactions on Signal Processing

Published: 2016

Topology Inference and Signal Representation Using Dictionary Learning

2019 27th European Signal Processing Conference (EUSIPCO)

Published: 2019

Show More

References

1.X. Zhu, Semi-supervised learning with graphs, 2005.
Show Context Google Scholar
2.S. Fortunato, "Community detection in graphs", Physics Rep., vol. 486, no. 3–5, pp. 75-174, 2010.
Show Context CrossRef Google Scholar
3.D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega and P. Vandergheynst, "The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains", IEEE Signal Process. Mag., vol. 30, no. 3, pp. 83-98, 2013.
Show Context View Article Full Text: PDF (3576KB) Google Scholar
4.J. Richiardi, S. Achard, H. Bunke and D. V. D. Ville, "Machine learning with brain graphs: Predictive modeling approaches for functional imaging in systems neuroscience", IEEE Signal Process. Mag., vol. 30, no. 3, pp. 58-70, 2013.
Show Context View Article Full Text: PDF (1551KB) Google Scholar
5.D. Koller and N. Friedman, Probabilistic Graphical Models: Principles and Techniques, Cambridge, MA:MIT Press, 2009.
Show Context Google Scholar
6.O. Banerjee, L. E. Ghaoui and A. d’Aspremont, "Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data", J. Mach. Learn. Res., vol. 9, pp. 485-516, 2008, [online] Available: https://dl.acm.org/citation.cfm?id=1390696.
Show Context Google Scholar
7.M. Gomez-Rodriguez, J. Leskovec and A. Krause, "Inferring networks of diffusion and influence", Proc. ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, pp. 1019-1028, 2010.
Show Context Access at ACM Google Scholar
8.S. A. Myers and J. Leskovec, "On the convexity of latent social network inference", Proc. Neural Information Processing Systems (NIPS), pp. 1741-1749, 2010.
Show Context Google Scholar
9.M. Gomez-Rodriguez, J. Leskovec, D. Balduzzi and B. Schölkopf, "Uncovering the structure and temporal dynamics of information propagation", Netw. Sci., vol. 2, no. 1, pp. 26-65, 2014.
Show Context CrossRef Google Scholar
10.N. Du, L. Song, A. J. Smola and M. Yuan, "Learning networks of heterogeneous influence", Proc. Neural Information Processing Systems (NIPS), pp. 2789-2797, 2012.
Show Context Google Scholar
11.C. Groendyke, D. Welch and D. R. Hunter, "Bayesian inference for contact networks given epidemic data", Scandinavian J. Statist., vol. 38, no. 3, pp. 600-616, 2011.
Show Context Google Scholar
12.A. Sandryhaila and J. M. F. Moura, "Discrete signal processing on graphs", IEEE Trans. Signal Process., vol. 61, no. 7, pp. 1644-1656, 2013.
Show Context View Article Full Text: PDF (2576KB) Google Scholar
13.A. Ortega, P. Frossard, J. Kovacˇevic´, J. M. F. Moura and P. Vandergheynst, "Graph signal processing: Overview challenges and applications", Proc. IEEE, vol. 106, no. 5, pp. 808-828, 2018.
Show Context View Article Full Text: PDF (1145KB) Google Scholar
14.N. Meinshausen and P. Bühlmann, "High-dimensional graphs and variable selection with the Lasso", Ann. Statist., vol. 34, no. 3, pp. 1436-1462, 2006.
Show Context CrossRef Google Scholar
15.J. Friedman, T. Hastie and R. Tibshirani, "Sparse inverse covariance estimation with the graphical Lasso", Biostatist., vol. 9, no. 3, pp. 432-441, 2008.
Show Context CrossRef Google Scholar
16.C.-J. Hsieh, I. S. Dhillon, P. K. Ravikumar and M. A. Sustik, "Sparse inverse covariance matrix estimation using quadratic approximation", Proc. Neural Information Processing Systems (NIPS), pp. 2330-2338, 2011.
Show Context Google Scholar
17.D. Heckerman, A tutorial on learning with Bayesian networks, 1995.
Show Context Google Scholar
18.A. P. Dempster, "Covariance selection", Biometrics, vol. 28, no. 1, pp. 157-175, 1972.
Show Context CrossRef Google Scholar
19.R. Tibshirani, "Regression shrinkage and selection via the Lasso", J. Roy. Statist. Soc. Series B, vol. 58, no. 1, pp. 267-288, 1995.
Show Context Google Scholar
20.M. Yuan and Y. Lin, "Model selection and estimation in regression with grouped variables", J. Roy. Statist. Soc. Series B, vol. 68, no. 1, pp. 49-67, 2006.
Show Context CrossRef Google Scholar
21.B. A. Cipra, "An introduction to the Ising model", Amer. Math. Monthly, vol. 94, no. 10, pp. 937-959, 1987.
Show Context CrossRef Google Scholar
22.P. Ravikumar, M. J. Wainwright and J. Lafferty, "High-dimensional Ising model selection using l1-regularized logistic regression", Ann. Statist., vol. 38, no. 3, pp. 1287-1319, 2010.
Show Context CrossRef Google Scholar
23.M. Slawski and M. Hein, "Estimation of positive definite M-matrices and structure learning for attractive Gaussian Markov random fields", Linear Algebra Applicat., vol. 473, pp. 145-179, May 2015.
Show Context CrossRef Google Scholar
24.G. Poole and T. Boullion, "A survey on M-matrices", SIAM Rev., vol. 16, no. 4, pp. 419-427, 1974.
Show Context CrossRef Google Scholar
25.B. Lake and J. Tenenbaum, "Discovering structure by learning sparse graph", Proc. 32nd Annu. Meeting Cognitive Science Society (CogSci), pp. 778-784, 2010.
Show Context Google Scholar
26.S. I. Daitch, J. A. Kelner and D. A. Spielman, "Fitting a graph to vector data", Proc. Int. Conf. Machine Learning, pp. 201-208, 2009.
Show Context Access at ACM Google Scholar
27.C. Hu, L. Cheng, J. Sepulcre, K. A. Johnson, G. E. Fakhri, Y. M. Lu, et al., "A spectral graph regression model for learning brain connectivity of Alzheimer’s disease", PLoS ONE, vol. 10, no. 5, 2015.
Show Context CrossRef Google Scholar
28.S. T. Roweis and L. K. Saul, "Nonlinear dimensionality reduction by locally linear embedding", Amer. Math. Monthly, vol. 290, no. 5500, pp. 2323-2326, 2000.
Show Context CrossRef Google Scholar
29.R. Castro, M. Coates, G. Liang, R. Nowak and B. Yu, "Network tomography: Recent developments", Statistical Sci., vol. 19, no. 3, pp. 499-517, 2004.
Show Context CrossRef Google Scholar
30.S. Ratnasamy and S. McCanne, "Inference of multicast routing trees and bottleneck bandwidths using end-to-end measurements", Proc. IEEE Infocom, pp. 353-360, 1999.
Show Context CrossRef Google Scholar
31.M. Rabbat, M. Coates and R. Nowak, "Multiple-source internet tomography", IEEE J. Select. Areas Commun., vol. 24, no. 12, pp. 2221-2234, 2006.
Show Context View Article Full Text: PDF (604KB) Google Scholar
32.P. Sattari, M. Kurant, A. Anandkumar, A. Markopoulou and M. Rabbat, "Active learning of multiple source multiple destination topologies", IEEE Trans. Signal Process., vol. 62, no. 8, pp. 1926-1937, 2014.
Show Context View Article Full Text: PDF (2135KB) Google Scholar
33.R. Pastor-Satorras, C. Castellano, P. V. Mieghem and A. Vespignani, "Epidemic processes in complex networks", Rev. Modern Physics, vol. 87, no. 3, pp. 925-979, 2015.
Show Context CrossRef Google Scholar
34.M. Gomez-Rodriguez, L. Song, H. Daneshmand and B. Schölkopf, "Estimating diffusion networks: Recovery conditions sample complexity and soft-thresholding algorithm", J. Mach. Learn. Res., no. 90, pp. 1-29, 2016, [online] Available: http://jmlr.org/papers/v17/14-430.html.
Show Context Google Scholar
35.S. Shaghaghian and M. Coates, "Bayesian inference of diffusion networks with unknown infection times", Proc. 2016 IEEE Statistical Signal Processing Workshop (SSP), 2016.
Show Context View Article Full Text: PDF (1307KB) Google Scholar
36.D. K. Hammond, P. Vandergheynst and R. Gribonval, "Wavelets on graphs via spectral graph theory", Appl. Comput. Harmon. Anal., vol. 30, no. 2, pp. 129-150, 2011.
Show Context CrossRef Google Scholar
37.X. Zhang, X. Dong and P. Frossard, "Learning of structured graph dictionaries", Proc. IEEE Int. Conf. Acoustics Speech and Signal Processing, pp. 3373-3376, 2012.
Show Context View Article Full Text: PDF (204KB) Google Scholar
38.D. Thanou, D. I. Shuman and P. Frossard, "Learning parametric dictionaries for signals on graphs", IEEE Trans. Signal Process., vol. 62, no. 15, pp. 3849-3862, 2014.
Show Context View Article Full Text: PDF (3173KB) Google Scholar
39.X. Dong, D. Thanou, P. Frossard and P. Vandergheynst, "Learning Laplacian matrix in smooth graph signal representations", IEEE Trans. Signal Process., vol. 64, no. 23, pp. 6160-6173, 2016.
Show Context View Article Full Text: PDF (1421KB) Google Scholar
40.V. Kalofolias, "How to learn a graph from smooth signals", Proc. Int. Conf. Artificial Intelligence and Statistics, pp. 920-929, 2016.
Show Context Google Scholar
41.H. E. Egilmez, E. Pavez and A. Ortega, "Graph learning from data under structural and Laplacian constraints", IEEE J. Sel. Topics Signal Process., vol. 11, no. 6, pp. 825-841, 2017.
Show Context View Article Full Text: PDF (1133KB) Google Scholar
42.S. P. Chepuri, S. Liu, G. Leus and A. O. Hero, "Learning sparse graphs under smoothness prior", Proc. IEEE Int. Conf. Acoustics Speech and Signal Processing, pp. 6508-6512, 2017.
Show Context View Article Full Text: PDF (489KB) Google Scholar
43.F. Chung, "The heat kernel as the pagerank of a graph", Proc. Nat. Academy Sci., vol. 104, no. 50, pp. 19,735-19,740, 2007.
Show Context CrossRef Google Scholar
44.H. Ma, H. Yang, M. R. Lyu and I. King, "Mining social networks using heat diffusion processes for marketing candidates selection", Proc. 17th ACM Conf. Information and Knowledge Management, pp. 233-242, 2008.
Show Context Access at ACM Google Scholar
45.S. Segarra, A. G. Marques, G. Mateos and A. Ribeiro, "Network topology inference from spectral templates", IEEE Trans. Signal Inform. Process. Netw., vol. 3, no. 3, pp. 467-483, 2017.
Show Context View Article Full Text: PDF (893KB) Google Scholar
46.B. Pasdeloup, V. Gripon, G. Mercier, D. Pastor and M. G. Rabbat, "Characterization and inference of graph diffusion processes from observations of stationary signals", IEEE Trans. Signal Inform. Process. Netw., vol. 4, no. 3, pp. 481-496, 2018.
Show Context View Article Full Text: PDF (730KB) Google Scholar
47.D. Thanou, X. Dong, D. Kressner and P. Frossard, "Learning heat diffusion graphs", IEEE Trans. Signal Inform. Process. Netw., vol. 3, no. 3, pp. 484-499, 2017.
Show Context View Article Full Text: PDF (1324KB) Google Scholar
48.R. Shafipour, S. Segarra, A. G. Marques and G. Mateos, "Identifying the topology of undirected networks from diffused non-stationary graph signals", 2018, [online] Available: .
Show Context Google Scholar
49.H. E. Egilmez, E. Pavez and A. Ortega, "Graph learning from filtered signals: Graph system and diffusion kernel identification", IEEE Trans. Signal Inform. Process. Netw..
Show Context Google Scholar
50.H. P. Maretic, D. Thanou and P. Frossard, "Graph learning under sparsity priors", Proc. IEEE Int. Conf. Acoustics Speech and Signal Processing, pp. 6523-6527, 2017.
Show Context View Article Full Text: PDF (380KB) Google Scholar
51.R. Rubinstein, A. M. Bruckstein and M. Elad, "Dictionaries for sparse representation modeling", Proc. IEEE, vol. 98, no. 6, pp. 1045-1057, 2010.
Show Context View Article Full Text: PDF (469KB) Google Scholar
52.I. Tosic and P. Frossard, "Dictionary learning", IEEE Signal Process. Mag., vol. 28, no. 2, pp. 27-38, 2011.
Show Context View Article Full Text: PDF (1894KB) Google Scholar
53.K. J. Friston, "Functional and effective connectivity in neuroimaging: A synthesis", Human Brain Mapping, vol. 2, no. 1–2, pp. 56-78, 1994.
Show Context CrossRef Google Scholar
54.Y. Shen, B. Baingana and G. B. Giannakis, "Nonlinear structural vector autoregressive models for inferring effective brain network connectivity", 2016, [online] Available: .
Show Context Google Scholar
55.J. Mei and J. M. F. Moura, "Signal processing on graphs: Causal modeling of unstructured data", IEEE Trans. Signal Process., vol. 65, no. 8, pp. 2077-2092, 2017.
Show Context View Article Full Text: PDF (5231KB) Google Scholar
56.J. Songsiri and L. Vandenberghe, "Topology selection in graphical models of autoregressive processes", J. Mach. Learn. Res., vol. 11, pp. 2671-2705, 2010, [online] Available: https://dl.acm.org/citation.cfm?id=1953020.
Show Context Google Scholar
57.A. Bolstad, B. D. V. Veen and R. Nowak, "Causal network inference via group sparse regularization", IEEE Trans. Signal Process., vol. 59, no. 6, pp. 2628-2641, 2011.
Show Context View Article Full Text: PDF (843KB) Google Scholar
58.A. Roebroeck, E. Formisano and R. Goebel, "Mapping directed influence over the brain using Granger causality and fMRI", NeuroImage, vol. 25, no. 1, pp. 230-242, 2005.
Show Context CrossRef Google Scholar
59.R. Goebel, A. Roebroeck, D.-S. Kim and E. Formisano, "Investigating directed cortical interactions in time-resolved fMRI data using vector autoregressive modeling and Granger causality mapping", Magn. Resonance Imag., vol. 21, no. 10, pp. 1251-1261, 2003.
Show Context CrossRef Google Scholar
60.D. W. Kaplan, Structural Equation Modeling: Foundations and Extensions, Newbury Park, CA:Sage, 2009.
Show Context CrossRef Google Scholar
61.A. McIntosh and F. Gonzalez-Lima, "Structural equation modeling and its application to network analysis in functional brain imaging", Hum. Brain Mapp., vol. 2, no. 1–2, pp. 2-22, 1994.
Show Context CrossRef Google Scholar
62.B. Baingana and G. B. Giannakis, "Tracking switched dynamic network topologies from information cascades", IEEE Trans. Signal Process., vol. 65, no. 4, pp. 985-997, 2017.
Show Context View Article Full Text: PDF (1439KB) Google Scholar
63.P. A. Traganitis, Y. Shen and G. B. Giannakis, "Network topology inference via elastic net structural equation models", Proc. European Signal Processing Conf., pp. 146-150, 2017.
Show Context View Article Full Text: PDF (140KB) Google Scholar
64.G. Chen, D. R. Glen, Z. S. Saad, J. P. Hamilton, M. E. Thomason, I. H. Gotlib, et al., "Vector autoregression structural equation modeling and their synthesis in neuroimaging data analysis", Comput. Biol. Med., vol. 41, no. 12, pp. 1142-1155, 2011.
Show Context CrossRef Google Scholar
65.G. B. Giannakis, Y. Shen and G. V. Karanikolas, "Topology identification and learning over graphs: Accounting for nonlinearities and dynamics", Proc. IEEE, vol. 106, no. 5, pp. 787-807, 2018.
Show Context View Article Full Text: PDF (1677KB) Google Scholar
66.G. Cheung, E. Magli, Y. Tanaka and M. Ng, "Graph spectral image processing", Proc. IEEE, vol. 106, no. 5, pp. 907-930, 2018.
Show Context View Article Full Text: PDF (2116KB) Google Scholar
67.W. Hu, G. Cheung, A. Ortega and O. C. Au, "Multi-resolution graph Fourier transform for compression of piecewise smooth images", IEEE Trans. Image Process., vol. 24, no. 1, pp. 419-433, 2015.
Show Context View Article Full Text: PDF (2881KB) Google Scholar
68.I. Rotondo, G. Cheung, A. Ortega and H. E. Egilmez, "Designing sparse graphs via structure tensor for block transform coding of images", Proc. Asia-Pacific Signal and Information Processing Assoc. Annu. Summit and Conf., pp. 571-574, 2015.
Show Context View Article Full Text: PDF (259KB) Google Scholar
69.G. Fracastoro, D. Thanou and P. Frossard, "Graph-based transform coding with application to image compression", 2017, [online] Available: .
Show Context Google Scholar
70.V. Kalofolias, A. Loukas, D. Thanou and P. Frossard, "Learning time varying graphs", Proc. IEEE Int. Conf. Acoustics Speech and Signal Processing, pp. 2826-2830, 2017.
Show Context View Article Full Text: PDF (4135KB) Google Scholar
71.K.-S. Lu and A. Ortega, "A graph Laplacian matrix learning method for fast implementation of graph Fourier transform", Proc. IEEE Int. Conf. Image Processing, pp. 1677-1681, 2017.
Show Context View Article Full Text: PDF (669KB) Google Scholar
72.W. Huang, T. A. W. Bolton, J. D. Medaglia, D. S. Bassett, A. Ribeiro and D. V. D. Ville, "A graph signal processing perspective on functional brain imaging", 2018, [online] Available: .
Show Context View Article Full Text: PDF (2887KB) Google Scholar
73.R. Liu, H. Nejati and N.-M. Cheung, "Joint estimation of low-rank components and connectivity graph in high-dimensional graph signals: Application to brain imaging", 2018, [online] Available: .
Show Context Google Scholar
74.I. Jablonski, "Graph signal processing in applications to sensor networks smart grids and smart cities", IEEE Sensors J., vol. 17, no. 23, pp. 7659-7666, 2017.
Show Context View Article Full Text: PDF (1987KB) Google Scholar
75.A. Gadde, A. Anis and A. Ortega, "Active semi-supervised learning using sampling theory for graph signals", Proc. ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, pp. 492-501, 2014.
Show Context Access at ACM Google Scholar
76.S. Vlaski, H. Maretic, R. Nassif, P. Frossard and A. H. Sayed, "Online graph learning from sequential data", Proc. IEEE Data Science Workshop, pp. 190-194, 2018.
Show Context View Article Full Text: PDF (2557KB) Google Scholar
77.H. N. Mhaskar, "A unified framework for harmonic analysis of functions on directed graphs and changing data", Appl. Comput. Harmon. Anal., vol. 44, no. 3, pp. 611-644, 2018.
Show Context CrossRef Google Scholar
78.B. Girault, A. Ortega and S. Narayanan, "Irregularity-aware graph Fourier transforms", IEEE Trans. Signal Process., vol. 66, no. 21, pp. 5746-5761, 2018.
Show Context View Article Full Text: PDF (1999KB) Google Scholar
79.S. Sardellitti, S. Barbarossa and P. D. Lorenzo, "On the graph Fourier transform for directed graphs", IEEE J. Sel. Topics Signal Process., vol. 11, no. 6, pp. 796-811, 2017.
Show Context View Article Full Text: PDF (1718KB) Google Scholar
80.R. Shafipour, A. Khodabakhsh, G. Mateos and E. Nikolova, "A directed graph Fourier transform with spread frequency components", 2018, [online] Available: .
Show Context Google Scholar
81.A. D. Col, P. Valdivia, F. Petronetto, F. Dias, C. T. Silva and L. G. Nonato, "Wavelet-based visual analysis of dynamic networks", IEEE Trans. Vis. Comput. Graph., vol. 24, no. 8, pp. 2456-2469, 2018.
Show Context View Article Full Text: PDF (1706KB) Google Scholar
82.E. Pavez, H. E. Egilmez and A. Ortega, "Learning graphs with monotone topology properties and multiple connected components", IEEE Trans. Signal Process., vol. 66, no. 9, pp. 2399-2413, 2018.
Show Context View Article Full Text: PDF (897KB) Google Scholar
83.M. Sundin, A. Venkitaraman, M. Jansson and S. Chatterjee, "A connectedness constraint for learning sparse graphs", Proc. European Signal Processing Conf., pp. 151-155, 2017.
Show Context View Article Full Text: PDF (868KB) Google Scholar
84.X. Dong, P. Frossard, P. Vandergheynst and N. Nefedov, "Clustering on multi-layer graphs via subspace analysis on Grassmann manifolds", IEEE Trans. Signal Process., vol. 62, no. 4, pp. 905-918, 2014.
Show Context View Article Full Text: PDF (2156KB) Google Scholar
85.S. Segarra, G. Mateos, A. G. Marques and A. Ribeiro, "Blind identification of graph filters", IEEE Trans. Signal Process., vol. 65, no. 5, pp. 1146-1159, 2017.
Show Context View Article Full Text: PDF (913KB) Google Scholar
86.S. Sardellitti, S. Barbarossa and P. Di Lorenzo, "Graph topology inference based on transform learning", Proc. IEEE Global Conf. Signal and Information Processing, pp. 356-360, 2016.
Show Context View Article Full Text: PDF (161KB) Google Scholar
87.Y. Yankelevsky and M. Elad, "Dual graph regularized dictionary learning", IEEE Trans. Signal Inform. Process. Netw., vol. 2, no. 4, pp. 611-624, 2016.
Show Context View Article Full Text: PDF (1599KB) Google Scholar
88.D. Hallac, Y. Park, S. Boyd and J. Leskovec, "Network inference via the time-varying graphical Lasso", Proc. ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, pp. 205-213, 2017.
Show Context Access at ACM Google Scholar