Signal Processing on Temporal Graphs

The LISIC lab is the information science laboratory of the University of Littoral Côte d'Opale. This internship will be supervised within the newly created LoRAL (Low-Rank Approximation and Learning) team at LISIC. This team currently comprises 8 faculty members, 2 emeritus professors, 4 postdoctoral researchers, and 10 doctoral students. The internship will take place in the new LISIC antenna in Longuenesse. The laboratory is located in the heart of the Regional Natural Park “Caps and Marais d’Opale”, near Lille, England, Belgium, and Northern Europe. Its Longuenesse premises are located next to the CROUS student residence and close to all amenities (everything can be done on foot or by bus). The teaching team can also put the recruited intern in contact with private landlords.

Context:

Many modern systems such as the Internet, transport networks, financial networks, or sensor networks, generate data that can be very well modeled as an attributed temporal graph [3]: where nodes and edges evolve over time and information is associated to them. For instance, in network traffic, computers can be modeled as nodes, packets can be represented as time-stamped edges, and packet characteristics (such as size) serve as edge attributes.
Despite the ubiquity of such data, there is a drastic lack of tools to analyze them properly. Currently, two major frameworks are used: Temporal Network Theory (TNT) [4], which focuses on the study of temporal graphs, and Graph Signal Processing (GSP) [5], which studies attributes defined on static graphs. Neither of them is fully satisfactory: TNT largely ignores attributes, while GSP struggles with time-varying topologies. These limitations therefore motivate the development of a unified formalism that coherently integrates ideas from both domains and is better suited to attributed temporal graphs.

Goal:

The goal of this internship is to take the first concrete steps toward bringing together the ideas of TNT and GSP. In particular, our aim is to leverage recent results in TNT to extend three key concepts of GSP: spectral transforms, regularity, and filtering [2]; so that they apply to attributed graphs that evolve over time. To achieve this, we plan to build upon on a recent and fundamental result in TNT that shows how a temporal graph can be decomposed into a set of elementary temporal–structural motifs [1]. Interestingly, these motifs form an orthonormal basis that captures both the temporal evolution and the structural patterns of the graph. Projecting an attribute signal onto this basis provides a natural spectral representation for temporal graph signals, playing a role analogous to classical spectral transforms in signal processing, such as the Fourier transform or wavelet transforms.

The internship will explore the potential of this spectral representation to extend the core notions of GSP. First, we will investigate how regularity can be characterized simultaneously in time and structure through how the energy localizes in the spectral domain. Then, we will study how filtering operations can be designed by manipulating the spectral coefficients associated with specific temporal or structural behaviors. These questions will raise the issue of choosing an appropriate motif decomposition, and part of the internship will consist in exploring which temporal and structural dictionaries lead to meaningful, interpretable, and useful transforms.

References:

[1] E. Bautista and M. Latapy. A frequency-structure approach for link stream analysis. In Temporal Network Theory, pages 449–482. Springer, 2023.
[2] A. Gavili and X.-P. Zhang. On the shift operator, graph frequency, and optimal filtering in graph signal
processing. IEEE Transactions on Signal Processing, 65(23):6303–6318, 2017.
[3] P. Holme and J. Saram¨aki. Temporal networks. Physics reports, 519(3):97–125, 2012.
[4] P. Holme and J. Saram¨aki. Temporal network theory, volume 2. Springer, 2019.
[5] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine, 30(3):83–98, 2013

This internship is intended for students with a background in applied mathematics, signal processing, or a closely related field. Candidates with a strong interest in theoretical approaches to data science are particularly encouraged to apply. The ideal candidate will have: (a) interest in theoretical and algorithmic research; (b) curiosity about temporal data, network analysis, or tensor methods; and (c) Python programming skills.