Graph Signal Processing -- Part III: Machine Learning on Graphs, from Graph Topology to Applications

Many modern data analytics applications on graphs operate on domains where\ngraph topology is not known a priori, and hence its determination becomes part\nof the problem definition, rather than serving as prior knowledge which aids\nthe problem solution. Part III of this monograph starts by addressing ways to\nlearn graph topology, from the case where the physics of the problem already\nsuggest a possible topology, through to most general cases where the graph\ntopology is learned from the data. A particular emphasis is on graph topology\ndefinition based on the correlation and precision matrices of the observed\ndata, combined with additional prior knowledge and structural conditions, such\nas the smoothness or sparsity of graph connections. For learning sparse graphs\n(with small number of edges), the least absolute shrinkage and selection\noperator, known as LASSO is employed, along with its graph specific variant,\ngraphical LASSO. For completeness, both variants of LASSO are derived in an\nintuitive way, and explained. An in-depth elaboration of the graph topology\nlearning paradigm is provided through several examples on physically well\ndefined graphs, such as electric circuits, linear heat transfer, social and\ncomputer networks, and spring-mass systems. As many graph neural networks (GNN)\nand convolutional graph networks (GCN) are emerging, we have also reviewed the\nmain trends in GNNs and GCNs, from the perspective of graph signal filtering.\nTensor representation of lattice-structured graphs is next considered, and it\nis shown that tensors (multidimensional data arrays) are a special class of\ngraph signals, whereby the graph vertices reside on a high-dimensional regular\nlattice structure. This part of monograph concludes with two emerging\napplications in financial data processing and underground transportation\nnetworks modeling.\n