Abstract

The area of Data Analytics on graphs deals with information processing of data acquired on irregular but structured graph domains. The focus of Part I of this monograph has been on both the fundamental and higher-order graph properties, graph topologies, and spectral representations of graphs. Part I also establishes rigorous frameworks for vertex clustering and graph segmentation, and illustrates the power of graphs in various data association tasks. Part II embarks on these concepts to address the algorithmic and practical issues related to data/signal processing on graphs, with the focus on the analysis and estimation of both deterministic and random data on graphs. The fundamental ideas related to graph signals are introduced through a simple and intuitive, yet general enough case study of multisensor temperature field estimation. The concept of systems on graph is defined using graph signal shift operators, which generalize the corresponding principles from traditional learning systems. At the core of the spectral domain representation of graph signals and systems is the Graph Fourier Transform (GFT), defined based on the eigendecomposition of both the adjacency matrix and the graph Laplacian. Spectral domain representations are then used as the basis to introduce graph signal filtering concepts and address their design, including Chebyshev series polynomial approximation. Ideas related to the sampling of graph signals, and in particular the challenging topic of data dimensionality reduction through graph subsampling, are presented and further linked with compressive sensing. The principles of time-varying signals on graphs and basic definitions related to random graph signals are next reviewed. Localized graph signal analysis in the joint vertex-spectral domain is referred to as the vertex-frequency analysis, since it can be considered as an extension of classical time-frequency analysis to the graph serving as signal domain. Important aspects of the local graph Fourier transform (LGFT) are covered, together with its various forms including the graph spectral and vertex domain windows and the inversion conditions and relations. A link between the LGFT with a varying spectral window and the spectral graph wavelet transform (SGWT) is also established. Realizations of the LGFT and SGWT using polynomial (Chebyshev) approximations of the spectral functions are further considered and supported by examples. Finally, energy versions of the vertex-frequency representations are introduced, along with their relations with classical timefrequency analysis, including a vertex-frequency distribution that can satisfy the marginal properties. The material is supported by illustrative examples.

Data Analytics on Graphs

The current availability of powerful computers and huge data sets is creating new opportunities in computational mathematics to bring together concepts and tools from graph theory, machine learning and signal processing, creating Data Analytics on Graphs.

In discrete mathematics, a graph is merely a collection of points (nodes) and lines connecting some or all of them. The power of such graphs lies in the fact that the nodes can represent entities as diverse as the users of social networks or financial market data, and that these can be transformed into signals which can be analyzed using data analytics tools. Data Analytics on Graphs is a comprehensive introduction to generating advanced data analytics on graphs that allows us to move beyond the standard regular sampling in time and space to facilitate modelling in many important areas, including communication networks, computer science, linguistics, social sciences, biology, physics, chemistry, transport, town planning, financial systems, personal health and many others.

The authors revisit graph topologies from a modern data analytics point of view, and proceed to establish a taxonomy of graph networks. With this as a basis, the authors show how the spectral analysis of graphs leads to even the most challenging machine learning tasks, such as clustering, being performed in an intuitive and physically meaningful way. The authors detail unique aspects of graph data analytics, such as their benefits for processing data acquired on irregular domains, their ability to finely-tune statistical learning procedures through local information processing, the concepts of random signals on graphs and graph shifts, learning of graph topology from data observed on graphs, and confluence with deep neural networks, multi-way tensor networks and Big Data. Extensive examples are included to render the concepts more concrete and to facilitate a greater understanding of the underlying principles.

Aimed at readers with a good grasp of the fundamentals of data analytics, this book sets out the fundamentals of graph theory and the emerging mathematical techniques for the analysis of a wide range of data acquired on graph environments. Data Analytics on Graphs will be a useful friend and a helpful companion to all involved in data gathering and analysis irrespective of area of application.