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
graph topology is not known a priori, and hence its determination becomes part
of the problem definition, rather than serving as prior knowledge which aids
the problem solution. Part III of this monograph starts by addressing ways to
learn graph topology, from the case where the physics of the problem already
suggest a possible topology, through to most general cases where the graph
topology is learned from the data. A particular emphasis is on graph topology
definition based on the correlation and precision matrices of the observed
data, combined with additional prior knowledge and structural conditions, such
as the smoothness or sparsity of graph connections. For learning sparse graphs
(with small number of edges), the least absolute shrinkage and selection
operator, known as LASSO is employed, along with its graph specific variant,
graphical LASSO. For completeness, both variants of LASSO are derived in an
intuitive way, and explained. An in-depth elaboration of the graph topology
learning paradigm is provided through several examples on physically well
defined graphs, such as electric circuits, linear heat transfer, social and
computer networks, and spring-mass systems. As many graph neural networks (GNN)
and convolutional graph networks (GCN) are emerging, we have also reviewed the
main trends in GNNs and GCNs, from the perspective of graph signal filtering.
Tensor representation of lattice-structured graphs is next considered, and it
is shown that tensors (multidimensional data arrays) are a special class of
graph signals, whereby the graph vertices reside on a high-dimensional regular
lattice structure. This part of monograph concludes with two emerging
applications in financial data processing and underground transportation
networks modeling.
