Summer school on Graphs for data analysis

where we recall the definition of a few graph problems, manipulate them, and discover the complexity reductions and gadgets that have been put in place. The aim is to show, however, that hard instances are often quite specific

A very large number of common graph problems are NP-hard. In order to demonstrate this difficulty, we generally use gadgets, which are specific patterns in the graph that model another problem known to be NP-hard, typically 3-SAT. The instances produced in this way are highly constrained. The aim of this first talk is to introduce the definitions that will be used in the rest of the day and to highlight the specificity of the graphs that appear in complexity proofs. We will also show to what extent a small relaxation of the problem or a small variation of the graph makes the problem easy on the instances. The talk will be accessible and highly interactive, and will be given jointly with Aline Parreau.

where we will see efficient algorithms, approximation, dynamic programming using graph properties…

In this presentation, following on from the previous one, we will show more generally how certain properties of graphs can be exploited to find more efficient algorithms. Indeed, as soon as we assume that the graph has a certain structure (e.g. a bounded tree width or topological constraints), most problems are no longer NP-hard or can be approximated efficiently. We will illustrate this on several examples using approximation algorithms or dynamic programming to find fast algorithms. We will also discuss the notion of kernel and FPT schemes if time permits. The talk will be accessible and highly interactive, and will be given jointly with Paul Dorbec.

Many graphs encountered in practice have a particular structure. For example, road networks have few or no intersections when drawn in a plane. We will see how this type of property, whether topological or geometric, interacts with the combinatorics of graphs, and often leads to the development of algorithms that are more efficient than in the general case.

We know how to define a graphs, study them and study the associated problems, but what happens when we add a temporal dimension to a graph ? If it is observed over time and allowed to evolve over time, how is this new graph defined ? What happens to the basic definitions and notions of graph theory in this new context ? And what about the well-known optimization problems in graphs ? Our aim is to provide (at least partial) answers to these questions.

We will look at the links between distributed algorithms and dynamic graphs. In particular, we will see how classical distributed methods and reasoning can be used to find elegant solutions to even centralised dynamic graph problems.

With the explosion in the number and diversity of digital data, ana- lysing data on graphs has become an inescapable challenge when it comes to studying interacting entities, in addition to any characte- ristics of their own. Among the various approaches to this, we will present the advances made over the last twelve years in graph signal processing, which offers tools for processing and analysing data on graphs and graphs themselves. At the heart of this work, the Fourier transform equivalents of data (or signals) on graphs have made it possible to develop new tools for filtering, interpolation, denoising or multi-scale decomposition of signals on graphs, but also offer impor- tant elements for forging learning methods on graphs (such as Graph Neural Networks).

The talk presents the state of the art in the field, starting with basic principles and early work involving Fourier transforms for graph data, covering the main advances and then some connections with machine learning and graph neural networks. In so doing, the presentation also illustrates how Fourier’s approach remains modern and univer- sal, and shows how his ideas, derived from physics and enriched by mathematics, computer science and signal theory, remain essential for meeting current challenges in data science.

In this presentation we will look at the adaptation of signal and image processing methods to graphs. Despite their ubiquities, these methods are restricted to signals defined on Euclidean domains. After presenting the principle of no local image filtering, which can be interpreted as filtering on a grid graph using a Laplacian operator, we will present discrete graph computation. The latter provides a set of definitions of differential operators (gradient, divergence, p-Laplacian) that can be used to adapt the solution of many inverse problems to graphs. We will present examples for the regularisation of signals from the nodes of an arbitrary graph and their hierarchical decomposition for their manipulation/enhancement. We will then show how mathematical morphology (algebraic or continuous) and its two fundamental operators, dilation and erosion, can be adapted to graphs. Finally, we will show how active contours can be adapted to graphs for segmentation and clustering.

Problems involving a spatial component can often be solved by minimising a function defined on a graph, whose solutions exhibit a structured form of sparsity. We present the Cut Pursuit algorithm, which exploits this property to efficiently minimise functions with varying degrees of regularity and continuity. Applied to problems whose solution is spatially regular, the Cut Pursuit algorithm achieves a significant speed-up and provides convergence guarantees that are independent of the regularity or convexity of the minimised functions. Next, we present the Superpoint approach to analyse large-scale 3D data. This method exploits the spatial regularity of the semantic labels of 3D points by partitioning them into simple shapes. The graph encoding the adjacency between these shapes makes it possible to analyse their relationships rather than the individual points, thereby reducing the complexity of the 3D analysis by several orders of magnitude. This method considerably reduces the complexity of 3D analysis while maintaining high accuracy and using fewer computing resources.

The human brain is made up of a complex network of tens of billions of neurons, each connected to 100,000 others via the axons that make up the fiber bundles of the white matter. Over the past decade, neuroimaging projects such as the Human Connectome Project (HCP) have proposed mapping these brain connections, known as the ’connectome’, to improve our understanding of the functional and structural organization of the brain. Connectivity can be represented in the form of a graph in which the nodes represent brain areas and the edges symbolize the connections between them. Undirected brain connectivity has been classified into two categories : (i) structural connectivity estimated by diffusion MRI (dMRI), where links represent axons or the density of neuronal fibers, and (ii) functional connectivity (measured for example with fMRI, EEG or NIRS), where links represent statistical dependencies between brain signals from different regions, such as correlations, coherence or transfer entropy.

In these contexts, robust estimation of these networks remains a challenge. Conventional approaches to estimate connectivity do not exploit all the information in the imaging data, which could be useful for highlighting these complex modifications. The introduction of innovative quantitative imaging techniques for estimating micro-structure and multimodality for estimating finer, more specific biomarkers could lead to better estimation in these complex cases. Despite the considerable progress made in this field, relatively few methods exploit the topology of brain networks estimated by structural connectivity to analyse functional brain activity. Some studies have proposed graph signal processing (GSP) approaches, which decomposes brain activity onto the spectral components of the graph. In this presentation, we will give an overview of work in the literature that uses GSP to decode and interpret brain activity. We will also describe in more detail two works in progress. To characterize how signals interact with underlying brain networks, Fourier and wavelet transforms have been extended to graph data. In the first study, we analyse the coupling and decoupling of functional activity on a structural connectivity graph and these measures are then used to classify different diseases such as depression and anxiety. In the second study, we present the advantages of using graph wavelet packets in neuroimaging. We will show the advantages of this approach compared with conventional methods in the context of psychiatric illnesses.

Graphs are a versatile representation that simultaneously encodes data and their relationships. Defining Machine Learning models using data in graph form would allow you to take full advantage of their representational power. Unfortunately, the definition of efficient learning models on graphs is not trivial, particularly due to the intrinsic complexity of this type of structure. During this introduction, we will present the different existing approaches to solve this scientific problem : graph embedding, kernels on graphs, edit distance and neural networks on graphs.

The second part of this morning will be devoted to the implementation of machine learning models operating on graphs, with an application to chemical molecules. This tutorial provides a concise introduction to graph neural networks (GNNs) using PyTorch Geometric, a library extending PyTorch for processing graph-structured data. After a guided installation, the tutorial covers key concepts such as datasets and graph convolutions. Through the creation of a simple GNN model for classification, it explains data loading, model definition and training. Case studies illustrate the application of GNN to real-world problems, and advice on model optimisation and eva luation is provided. The tutorial concludes with resources for further learning about GNN and PyTorch Geometric, aimed at equipping readers for their own research or development projects.

In this presentation, we propose an overview of the most common approaches used in machine learning, with a perspective on the recent contributions from the MIVIA group, university of Salerno.

Bridging Graph Spaces: Novel Algorithms and Their Applications

Over the years, numerous graph-based machine learning algorithms have emerged. Yet the connections among these methods and the respective spaces remain unrevealed, keeping the underlying theories and potential applications behind the mist. This talk explores the intricate relationships among diverse graph-based machine learning methods and their associated metric spaces, including graph kernels, Graph Edit Distances (GEDs), and Graph Neural Networks (GNNs). The objective is to bridge the existing disparities within these graph spaces while simultaneously enhancing the performance of the underlying methodologies. To achieve this, we introduce two distinct yet interrelated pathways. The first path delves into the effort to refine graph metrics via embeddings across different spaces. The second path explores on the potential of learning graph metrics via GNNs. Beyond these methodologies, we extend our study to the practical applications of distinct graph-based models, with a focus on molecule properties prediction, leveraging recent advances in quantum chemistry.