Workshop > Invited Speakers

Constraint Programming illustrated on the Subgraph Isomorphism Problem

Christine Solnon

Short Bio

Christine Solnon received the Dipl. and Ph.D. degrees in computer science from the University of Nice-Sophia Antipolis, France, in 1989 and 1993, respectively.,Since 1994, she has been an Associate Professor with the Computer Science Department, University Claude Bernard, Lyon, France. Her current research interests include ant algorithms, constraint satisfaction problems, and solvers cooperation. Her previous research interests include type inference systems and the static analysis of Prolog programs

Abstract

According to Gene Freuder, Constraint Programming (CP) represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it. Problems are modelled by means of constraints using high level languages, and they are solved by generic solvers. In this talk, we'll illustrate CP through a problem which is at the core of many pattern recognition tasks, i.e., subgraph isomorphism (SI). In particular, we’ll see how to model and solve SI with existing CP libraries. We’ll also describe various ingredients used by generic CP solvers, such as constraint propagation, ordering heuristics, restarts and no-good learning, and evaluate their practical interest for solving SI.

Enhancing Graph Neural Networks with Topological Structure

Fragkiskos Malliaros

Short Bio

Fragkiskos Malliaros (http://fragkiskos.me) is an Associate Professor (HDR) at CentraleSupélec, Université Paris-Saclay and associate researcher at Inria Saclay (Opis team). He is the co-director of the Master's Program in Data Sciences and Business Analytics (CentraleSupélec and ESSEC Business School). Previously, he was a postdoctoral researcher at UC San Diego (2016-17) and École Polytechnique (2015-16). He received his Ph.D. in Computer Science from École Polytechnique (2015) and his Diploma (2009) and M.Sc. (2011) degrees from the University of Patras, Greece. He is the recipient of the 2012 Google European Doctoral Fellowship in Graph Mining, the 2015 Thesis Prize by École Polytechnique, and best paper awards at TextGraphs-NAACL 2018 and AAAI ICWSM 2020 (honorable mention). In the past, he has been in the organization committee of various data science conferences and workshops. He has also presented several invited tutorials at international conferences in the areas of graph mining and data science (e.g., ICDM, WSDM, WWW, EMNLP, EDBT). His research interests span the broad area of data science, with focus on graph machine learning, geometric deep learning, and graph-based information extraction.

Abstract

Graph Neural Networks (GNNs) have become the cornerstone of graph machine learning and geometric deep learning in general. In this talk, I will discuss how the underlying graph structure can be leveraged to enhance GNNs, focusing primarily on two problems. The first concerns over-smoothing and over-squashing, which are two intrinsic limitations when stacking multiple message passing layers to form deep GNNs. Specifically, I will introduce a fundamental topological trade-off between over-smoothing and over-squashing, and algorithms to mitigate it. The second problem deals with the design of pooling operators used by GNNs to compute graph-level representations (e.g., in the case of graph classification). I will discuss how the clustering stucture of the graph can be incorporated to define pooling operators, allowing to better capture the graph’s hierarchical structure.