Many physical phenomena and complex systems can be modeled as networks of interacting entities. Prominent examples include social networks, the web, computer and transportation networks, and the brain. The goal of the EGS project is to leverage techniques from signal processing to the analysis and understanding of such complex objects when viewed as graph signals. A graph signal is a graph with values assigned to its vertex set, in a similar way that an image signal consists of values arranged on a grid. A graph signal may evolve over time through changes in the graph structure, or though changes in the values of the nodes. Graph signals offer a very rich structure for representing the information of complex systems consisting of smaller parts, as well as processes that take place on these systems.
The project will explore the vast research on signal processing and graph theory towards developing new analytical tools for the study of graph signals, in particular graph signals that evolve over time. Building on a sound theoretical basis, the project will revisit classical data mining, knowledge extraction and machine learning tasks through the graph signal lens, with the purpose of developing new models and algorithms. As a practical benchmark for testing our new techniques and methods, we plan to investigate the formulation and evolution of online communites and the automatic detection of events in urban or online settings, as well as the analysis of phenomena on biological networks.
The EGS project aspires to introduce a radically novel approach to the analysis of complex systems and dynamic processes on networks or other irregular structures.
One of the key challenges will reside in properly matching temporally successive signals that possibly live on different graphs; graph spectral features will be of high importance in that problem. These results will be exploited to offer a novel approach to compression, segmentation and summarization of dynamic graphs. Furthermore, we plan to use time-series analysis for studying temporally evolving graph signals where values change over static graphs. The joint analysis of time series that are associated through graph edges will require revisiting standard time series analysis tools and techniques.
Another novelty of our approach is that it cuts across different fields. We plan to enhance the representative power of both graph signals and dynamic graph signals, by exploring how graph theoretical concepts (such as cliques and bridges) can be captured and processed using signal-processing operators and transforms. Along this direction, we also plan to investigate how concepts developed separately in signal processing and graph theory relate to each other. As an example consider the problem of identifying important nodes in graph signals. There is a lot of research in graph theory for determining central nodes based on the graph structure (e.g., PageRank) and in image analysis for identifying key-points in images based on the signal differences in the neighbourhood of a pixel (e.g., SIFT). Our goal is to investigate how to combine the two concepts towards the analysis of transformations in dynamic graph signals. Furthermore, we will identify graphs with special properties; for example, planar graphs, which may lead to simplified transformations suitable for large-scale implementations. Another novel research problem to be investigated is the formulation of statistical generative models for graph signals and temporally evolving graph signals. Such models have been applied for generating the graph structure or the attributes on graph nodes. Statistical models for graph signals require the definition of generation mechanisms for both the underlying graph structure and the signal values. They permit different designs depending on the assumptions about the inter-dependence of these two generation mechanisms. Along with generative models, we will develop statistical inference algorithms to estimate the model parameters given a collection of graph signals.
The algorithms that we will develop will be executed on large datasets. Organizing the work for such data is nontrivial and we need appropriate scheduling algorithms. Therefore, an important component of our work will be the design of automatic scheduling algorithms. For example, the application of the graph-signal approach in biological networks requires the enumeration of all the solutions to a system. This is a challenging goal; it requires (1) the design of efficient algorithms that are able to enumerate all the solutions to the input problem and (2) the design of efficient scheduling mechanisms for such algorithms.
The expected immediate impact of EGS project is a radically new line of research and technology in understanding evolving complex systems and processes on them founded on dynamic graph signals. Research in the project will be a proof-of-principle of this new technological possibility by setting the necessary scientific underpinnings in terms of graph-signal theory, models, operators, and transforms, as well as in terms of data mining and knowledge discovery. Through this new theory, the proposed research will have a transformational impact on data science in general, since it will introduce a new powerful paradigm through the modeling of complex systems as (dynamic) graph signals.