IAPR TC15 Web Page

Some Lectures on Graph based representations :

First TC15 Webseminar
- Differentiable graph matching (Romain Raveaux)
- Graph based video processing (Ananda Chowdhury)
- Graph pre image (Benoit Gaüzère)
- Sub graph isomorphism in Pattern Recognition (Pasquale Foggia)
Graph Classification
- Graph Embedding in Vector Spaces (Gibert Jaume )
- Graph kernels (Luc Brun)
- Graph kernels and applications in chemoinformatics (Jean Philippe Vert)
- Graph Neural Network (Marco Gori)
Graph Matching
- Experimental Evaluation of Subgraphs Isomorphism Solvers (Christine Solnon)
- From cliques to equilibria: The dominant set framework for pairwise data clustering (Marcello Pelillo)
Graph Theory
- Graph Theory (S.C. Locke)
- Graph Theory (Reinhard Diestel)
PDEs on Graphs
- Combinatorial Calculus in Computer Vision: Formulating and Solving Continuous PDEs on Graphs (Leo Grady)
- Graph transduction (Aykut Erdem)
- Image segmentation with random walks (Leo Grady)
- Partial Difference Equations on graphs for image and data processing (Olivier Lezoray)
GbR'2007 in Video (Francisco Escolano)
Irregular Pyramids (Luc Brun)

If you wish to see your own lectures (related to GbR topics) published on this web page, please do not hesitate to send an email to iapr-tc15 with the following informations:

Your first and last names,
The title of the lecture,
A short description of the content and
at least one link or one attached file

Combinatorial Calculus in Computer Vision: Formulating and Solving Continuous PDEs on Graphs

Leo Grady

A tutorial on Continuous PDEs on Graphs provided By Leo Grady and Sebastien Bougleux at ECCV 2008, Oct. 12th, 2008, Marseilles, France.

Links :

Experimental Evaluation of Subgraphs Isomorphism Solvers

Christine Solnon

Subgraph Isomorphism (SI) is an NP-complete problem which is at the heart of many structural pattern recognition tasks as it involves finding a copy of a pattern graph into a target graph. In the pattern recognition community, the most well-known SI solvers are VF2, VF3, and RI. SI is also widely studied in the constraint programming community, and many constraint-based SI solvers have been proposed since Ullman, such as LAD and Glasgow, for example. All these SI solvers can solve very quickly some large SI instances, that involve graphs with thousands of nodes. However, Mc Creesh et al. have recently shown how to randomly generate SI instances the hardness of which can be controlled and predicted. In particular, they have shown how to generate small instances (with thirty pattern nodes and 200 target nodes, for example) which are computationally challenging for all solvers. This study also showed that some small instances which are easily solved by constraint-based solvers, appear to be challenging for VF2 and VF3. In this talk, we will widen this study by considering a large test suite of 14,621 instances coming from eight different benchmarks.We will show that, as expected for an NP-complete problem, the solving time ofan instance does not depend on its size, and that some small instances coming from real applications are not solved by any of the considered solvers. We will also show that, if RI and VF3 are able to solve very quickly a large number of easy instances, for which Glasgow or LAD need more time, they fail at solving some other instances that are quickly solved by Glasgow or LAD, and they are clearly outperformed by Glasgow on hard instances. Finally, we will show that we can easily combine solvers to take benefit of their complementarity.

Links :

Pdf of the talk

From cliques to equilibria: The dominant set framework for pairwise data clustering

Marcello Pelillo

The course will provide an overview of recent work on pairwise data clustering which has lead to establish intriguing connections between unsupervised learning and (evolutionary) game theory. The framework is centered around the notion of a "dominant set," a novel graph-theoretic concept which generalizes that of a maximal clique to edge-weighted graphs. Algorithms inspired from evolutionary game theory, and applications in computer vision and pattern recognition will be discussed.

Links :

Graph Neural Network

Marco Gori

The indisputable success of deep learning mostly relies on vector-based representations of the inputs. Yet, many applications deal with non-Euclidean data that typically exhibit a graph structure. Examples come from very different domains, including social networks, molecular graphs in chemistry, and computer vision. In the last couple of years, the extension of neural computation to graphical domains, that was brought to the attention of the scientific community at the end of nineties, has come back to life thanks to a small community of scientists, who have significantly contributed to improve the algorithmic framework and, especially, to show remarkable experimental achievements in different application domains.

In this talk, we begin noticing that, apart from the above mentioned advances, the underlying idea behind the process of learning the weights is still based on an appropriate extension of Backpropagation to graphs. As such, we are still in front of a computational process that has been the source of many debates on its arguable biological plausibility. Then, we propose a novel reformulation of learning in graphical domains that is based on the description of the given graphs and of the neural network by a correspondent set of constraints that must be “parsimoniously satisfied.” We propose a Lagrangian framework that gives rise to a biologically plausible local algorithm based on the search for saddle points in the learning adjoint space (LAS) composed of weights, neural outputs, and Lagrangian multipliers. This Local Propagation algorithm (LP) only involves local updates of the weights. Preliminary experiments are shown to illustrate the features and the performance of this novel local propagation learning algorithm. Interestingly, the learning of LP in the LAS also allow us to circumvent the classic problem of gradient vanishing in deep sequences.

Links :

Pdf of the talk

Graph pre image

Benoit Gaüzère

A graph kernel maps a graph into a feature space. This talk explores different research directions in order to perform the reverse mapping. A central application consists in computing the graph corresponding to a mean/median in the feature space.