Abstract

The area of Data Analytics on graphs promises a paradigm shift, as we approach information processing of new classes of data which are typically acquired on irregular but structured domains (such as social networks, various ad-hoc sensor networks). Yet, despite the long history of Graph Theory, current approaches tend to focus on aspects of optimisation of graphs themselves rather than on eliciting strategies relevant to the objective application of the graph paradigm, such as detection, estimation, statistical and probabilistic inference, clustering and separation from signals and data acquired on graphs. In order to bridge this gap, we first revisit graph topologies from a Data Analytics point of view, to establish a taxonomy of graph networks through a linear algebraic formalism of graph topology (vertices, connections, directivity). This serves as a basis for spectral analysis of graphs, whereby the eigenvalues and eigenvectors of graph Laplacian and adjacency matrices are shown to convey physical meaning related to both graph topology and higher-order graph properties, such as cuts, walks, paths, and neighborhoods. Through a number of carefully chosen examples, we demonstrate that the isomorphic nature of graphs enables both the basic properties of data observed on graphs and their descriptors (features) to be preserved throughout the data analytics process, even in the case of reordering of graph vertices, where classical approaches fail. Next, to illustrate the richness and flexibility of estimation strategies performed on graph signals, spectral analysis of graphs is introduced through eigenanalysis of mathematical descriptors of graphs and in a generic way. Finally, benefiting from enhanced degrees of freedom associated with graph representations, a framework for vertex clustering and graph segmentation is established based on graph spectral representation (eigenanalysis) which demonstrates the power of graphs in various data association tasks, from image clustering and segmentation trough to low-dimensional manifold representation. The supporting examples demonstrate the promise of Graph Data Analytics in modeling structural and functional/semantic inferences. At the same time, Part I serves as a basis for Part II and Part III which deal with theory, methods and applications of processing Data on Graphs and Graph Topology Learning from data.

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.