Search

Your search keyword '"Gaüzère, Benoit"' showing total 105 results
Start Over Author "Gaüzère, Benoit"

Refine your results

more »

more »

more »
105 results on '"Gaüzère, Benoit"'

1. Maximal Independent Sets for Pooling in Graph Neural Networks

Author

Stanovic, Stevan, Gaüzère, Benoit, and Brun, Luc

Subjects
Computer Science - Machine Learning, Computer Science - Artificial Intelligence, Computer Science - Computer Vision and Pattern Recognition
Abstract

Convolutional Neural Networks (CNNs) have enabled major advances in image classification through convolution and pooling. In particular, image pooling transforms a connected discrete lattice into a reduced lattice with the same connectivity and allows reduction functions to consider all pixels in an image. However, there is no pooling that satisfies these properties for graphs. In fact, traditional graph pooling methods suffer from at least one of the following drawbacks: Graph disconnection or overconnection, low decimation ratio, and deletion of large parts of graphs. In this paper, we present three pooling methods based on the notion of maximal independent sets that avoid these pitfalls. Our experimental results confirm the relevance of maximal independent set constraints for graph pooling.

Published
2023

2. Maximal Independent Vertex Set applied to Graph Pooling

Author

Stanovic, Stevan, Gaüzère, Benoit, and Brun, Luc

Subjects
Computer Science - Machine Learning, Computer Science - Artificial Intelligence, Computer Science - Computer Vision and Pattern Recognition
Abstract

Convolutional neural networks (CNN) have enabled major advances in image classification through convolution and pooling. In particular, image pooling transforms a connected discrete grid into a reduced grid with the same connectivity and allows reduction functions to take into account all the pixels of an image. However, a pooling satisfying such properties does not exist for graphs. Indeed, some methods are based on a vertex selection step which induces an important loss of information. Other methods learn a fuzzy clustering of vertex sets which induces almost complete reduced graphs. We propose to overcome both problems using a new pooling method, named MIVSPool. This method is based on a selection of vertices called surviving vertices using a Maximal Independent Vertex Set (MIVS) and an assignment of the remaining vertices to the survivors. Consequently, our method does not discard any vertex information nor artificially increase the density of the graph. Experimental results show an increase in accuracy for graph classification on various standard datasets.

Published
2022

3. A new Sinkhorn algorithm with Deletion and Insertion operations

Author

Brun, Luc, Gaüzère, Benoit, Bougleux, Sébastien, and Yger, Florian

Subjects
Computer Science - Machine Learning, Computer Science - Neural and Evolutionary Computing, Mathematics - Optimization and Control
Abstract

This technical report is devoted to the continuous estimation of an epsilon-assignment. Roughly speaking, an epsilon assignment between two sets V1 and V2 may be understood as a bijective mapping between a sub part of V1 and a sub part of V2 . The remaining elements of V1 (not included in this mapping) are mapped onto an epsilon pseudo element of V2 . We say that such elements are deleted. Conversely, the remaining elements of V2 correspond to the image of the epsilon pseudo element of V1. We say that these elements are inserted. As a result our method provides a result similar to the one of the Sinkhorn algorithm with the additional ability to reject some elements which are either inserted or deleted. It thus naturally handles sets V1 and V2 of different sizes and decides mappings/insertions/deletions in a unified way. Our algorithms are iterative and differentiable and may thus be easily inserted within a backpropagation based learning framework such as artificial neural networks., Comment: 20 pages

Published
2021

4. Breaking the Limits of Message Passing Graph Neural Networks

Author

Balcilar, Muhammet, Héroux, Pierre, Gaüzère, Benoit, Vasseur, Pascal, Adam, Sébastien, and Honeine, Paul

Subjects
Computer Science - Machine Learning, Computer Science - Artificial Intelligence, 68T07, I.5.0, I.2.0
Abstract

Since the Message Passing (Graph) Neural Networks (MPNNs) have a linear complexity with respect to the number of nodes when applied to sparse graphs, they have been widely implemented and still raise a lot of interest even though their theoretical expressive power is limited to the first order Weisfeiler-Lehman test (1-WL). In this paper, we show that if the graph convolution supports are designed in spectral-domain by a non-linear custom function of eigenvalues and masked with an arbitrary large receptive field, the MPNN is theoretically more powerful than the 1-WL test and experimentally as powerful as a 3-WL existing models, while remaining spatially localized. Moreover, by designing custom filter functions, outputs can have various frequency components that allow the convolution process to learn different relationships between a given input graph signal and its associated properties. So far, the best 3-WL equivalent graph neural networks have a computational complexity in $\mathcal{O}(n^3)$ with memory usage in $\mathcal{O}(n^2)$, consider non-local update mechanism and do not provide the spectral richness of output profile. The proposed method overcomes all these aforementioned problems and reaches state-of-the-art results in many downstream tasks., Comment: 18 pages, 6 figures

Published
2021

5. Bridging Distinct Spaces in Graph-Based Machine Learning

Author

Jia, Linlin, Ning, Xiao, Gaüzère, Benoit, Honeine, Paul, Riesen, Kaspar, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Lu, Huimin, editor, Blumenstein, Michael, editor, Cho, Sung-Bae, editor, Liu, Cheng-Lin, editor, Yagi, Yasushi, editor, and Kamiya, Tohru, editor

Published
2023
Full Text
View/download PDF

6. Graph Normalizing Flows to Pre-image Free Machine Learning for Regression

Author

Glédel, Clément, Gaüzère, Benoît, Honeine, Paul, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Vento, Mario, editor, Foggia, Pasquale, editor, Conte, Donatello, editor, and Carletti, Vincenzo, editor

Published
2023
Full Text
View/download PDF

7. Generalized Median Graph via Iterative Alternate Minimizations

Author

Boria, Nicolas, Bougleux, S'ebastien, Gaüzère, Benoit, and Brun, Luc

Subjects
Computer Science - Computer Vision and Pattern Recognition, Quantitative Biology - Quantitative Methods
Abstract

Computing a graph prototype may constitute a core element for clustering or classification tasks. However, its computation is an NP-Hard problem, even for simple classes of graphs. In this paper, we propose an efficient approach based on block coordinate descent to compute a generalized median graph from a set of graphs. This approach relies on a clear definition of the optimization process and handles labeling on both edges and nodes. This iterative process optimizes the edit operations to perform on a graph alternatively on nodes and edges. Several experiments on different datasets show the efficiency of our approach.

Published
2019

10. Predicting redox potentials by graph‐based machine learning methods.

Author

Jia, Linlin, Brémond, Éric, Zaida, Larissa, Gaüzère, Benoit, Tognetti, Vincent, and Joubert, Laurent

Subjects
GRAPH neural networks, MACHINE learning, OXIDATION-reduction reaction, PHYSICAL & theoretical chemistry, DENSITY functional theory
Abstract

The evaluation of oxidation and reduction potentials is a pivotal task in various chemical fields. However, their accurate prediction by theoretical computations, which is a complementary task and sometimes the only alternative to experimental measurement, may be often resource‐intensive and time‐consuming. This paper addresses this challenge through the application of machine learning techniques, with a particular focus on graph‐based methods (such as graph edit distances, graph kernels, and graph neural networks) that are reviewed to enlighten their deep links with theoretical chemistry. To this aim, we establish the ORedOx159 database, a comprehensive, homogeneous (with reference values stemming from density functional theory calculations), and reliable resource containing 318 one‐electron reduction and oxidation reactions and featuring 159 large organic compounds. Subsequently, we provide an instructive overview of the good practice in machine learning and of commonly utilized machine learning models. We then assess their predictive performances on the ORedOx159 dataset through extensive analyses. Our simulations using descriptors that are computed in an almost instantaneous way result in a notable improvement in prediction accuracy, with mean absolute error (MAE) values equal to 5.6 kcal mol−1 for reduction and 7.2 kcal mol−1 for oxidation potentials, which paves a way toward efficient in silico design of new electrochemical systems. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

11. A Graph Pre-image Method Based on Graph Edit Distances

Author

Jia, Linlin, Gaüzère, Benoit, Honeine, Paul, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Torsello, Andrea, editor, Rossi, Luca, editor, Pelillo, Marcello, editor, Biggio, Battista, editor, and Robles-Kelly, Antonio, editor

Published
2021
Full Text
View/download PDF

12. A Metric Learning Approach to Graph Edit Costs for Regression

Author

Jia, Linlin, Gaüzère, Benoit, Yger, Florian, Honeine, Paul, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Torsello, Andrea, editor, Rossi, Luca, editor, Pelillo, Marcello, editor, Biggio, Battista, editor, and Robles-Kelly, Antonio, editor

Published
2021
Full Text
View/download PDF

14. A Quadratic Assignment Formulation of the Graph Edit Distance

Author

Bougleux, Sébastien, Brun, Luc, Carletti, Vincenzo, Foggia, Pasquale, Gaüzère, Benoit, and Vento, Mario

Subjects
Computer Science - Data Structures and Algorithms
Abstract

Computing efficiently a robust measure of similarity or dissimilarity between graphs is a major challenge in Pattern Recognition. The Graph Edit Distance (GED) is a flexible measure of dissimilarity between graphs which arises in error-tolerant graph matching. It is defined from an optimal sequence of edit operations (edit path) transforming one graph into an other. Unfortunately, the exact computation of this measure is NP-hard. In the last decade, several approaches have been proposed to approximate the GED in polynomial time, mainly by solving linear programming problems. Among them, the bipartite GED has received much attention. It is deduced from a linear sum assignment of the nodes of the two graphs, which can be efficiently computed by Hungarian-type algorithms. However, edit operations on nodes and edges are not handled simultaneously, which limits the accuracy of the approximation. To overcome this limitation, we propose to extend the linear assignment model to a quadratic one, for directed or undirected graphs having labelized nodes and edges. This is realized through the definition of a family of edit paths induced by assignments between nodes. We formally show that the GED, restricted to the paths in this family, is equivalent to a quadratic assignment problem. Since this problem is NP-hard, we propose to compute an approximate solution by an adaptation of the Integer Projected Fixed Point method. Experiments show that the proposed approach is generally able to reach a more accurate approximation of the optimal GED than the bipartite GED, with a computational cost that is still affordable for graphs of non trivial sizes.

Published
2015

16. A Hungarian Algorithm for Error-Correcting Graph Matching

Author

Bougleux, Sébastien, Gaüzère, Benoit, Brun, Luc, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Pandu Rangan, C., Editorial Board Member, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Weikum, Gerhard, Series Editor, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Foggia, Pasquale, editor, Liu, Cheng-Lin, editor, and Vento, Mario, editor

Published
2017
Full Text
View/download PDF

17. Approximating Graph Edit Distance Using GNCCP

Author

Gaüzère, Benoît, Bougleux, Sébastien, Brun, Luc, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Robles-Kelly, Antonio, editor, Loog, Marco, editor, Biggio, Battista, editor, Escolano, Francisco, editor, and Wilson, Richard, editor

Published
2016
Full Text
View/download PDF

19. Semantic Web Technologies for Object Tracking and Video Analytics

Author

Gaüzère, Benoit, Greco, Claudia, Ritrovato, Pierluigi, Saggese, Alessia, Vento, Mario, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Bebis, George, editor, Boyle, Richard, editor, Parvin, Bahram, editor, Koracin, Darko, editor, Pavlidis, Ioannis, editor, Feris, Rogerio, editor, McGraw, Tim, editor, Elendt, Mark, editor, Kopper, Regis, editor, Ragan, Eric, editor, Ye, Zhao, editor, and Weber, Gunther, editor

Published
2015
Full Text
View/download PDF

20. Human Tracking Using a Top-Down and Knowledge Based Approach

Author

Gaüzère, Benoit, Ritrovato, Pierluigi, Saggese, Alessia, Vento, Mario, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Murino, Vittorio, editor, and Puppo, Enrico, editor

Published
2015
Full Text
View/download PDF

21. Approximate Graph Edit Distance Computation Combining Bipartite Matching and Exact Neighborhood Substructure Distance

Author

Carletti, Vincenzo, Gaüzère, Benoit, Brun, Luc, Vento, Mario, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Liu, Cheng-Lin, editor, Luo, Bin, editor, Kropatsch, Walter G., editor, and Cheng, Jian, editor

Published
2015
Full Text
View/download PDF

22. Approximate Graph Edit Distance Guided by Bipartite Matching of Bags of Walks

Author

Gaüzère, Benoit, Bougleux, Sébastien, Riesen, Kaspar, Brun, Luc, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Fränti, Pasi, editor, Brown, Gavin, editor, Loog, Marco, editor, Escolano, Francisco, editor, and Pelillo, Marcello, editor

Published
2014
Full Text
View/download PDF

24. A Comparison of Explicit and Implicit Graph Embedding Methods for Pattern Recognition

Author

Conte, Donatello, Ramel, Jean-Yves, Sidère, Nicolas, Luqman, Muhammad Muzzamil, Gaüzère, Benoît, Gibert, Jaume, Brun, Luc, Vento, Mario, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Kropatsch, Walter G., editor, Artner, Nicole M., editor, Haxhimusa, Yll, editor, and Jiang, Xiaoyi, editor

Published
2013
Full Text
View/download PDF

25. Relevant Cycle Hypergraph Representation for Molecules

Author

Gaüzère, Benoît, Brun, Luc, Villemin, Didier, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Kropatsch, Walter G., editor, Artner, Nicole M., editor, Haxhimusa, Yll, editor, and Jiang, Xiaoyi, editor

Published
2013
Full Text
View/download PDF

26. Graph Kernels: Crossing Information from Different Patterns Using Graph Edit Distance

Author

Gaüzère, Benoit, Brun, Luc, Villemin, Didier, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Gimel’farb, Georgy, editor, Hancock, Edwin, editor, Imiya, Atsushi, editor, Kuijper, Arjan, editor, Kudo, Mineichi, editor, Omachi, Shinichiro, editor, Windeatt, Terry, editor, and Yamada, Keiji, editor

Published
2012
Full Text
View/download PDF

27. Implicit and Explicit Graph Embedding: Comparison of Both Approaches on Chemoinformatics Applications

Author

Gaüzère, Benoit, Hasegawa, Makoto, Brun, Luc, Tabbone, Salvatore, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Gimel’farb, Georgy, editor, Hancock, Edwin, editor, Imiya, Atsushi, editor, Kuijper, Arjan, editor, Kudo, Mineichi, editor, Omachi, Shinichiro, editor, Windeatt, Terry, editor, and Yamada, Keiji, editor

Published
2012
Full Text
View/download PDF

28. Two New Graph Kernels and Applications to Chemoinformatics

Author

Gaüzère, Benoit, Brun, Luc, Villemin, Didier, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Jiang, Xiaoyi, editor, Ferrer, Miquel, editor, and Torsello, Andrea, editor

Published
2011
Full Text
View/download PDF

38. Spectral-designed depthwise separable graph neural networks

Author

Balcilar, Muhammet, Renton, Guillaume, Héroux, Pierre, Gaüzère, Benoit, Adam, Sébastien, Honeine, Paul, Honeine, Paul, APPEL À PROJETS GÉNÉRIQUE 2018 - Apprivoiser la Pré-image - - APi2018 - ANR-18-CE23-0014 - AAPG2018 - VALID, Equipe Apprentissage (DocApp - LITIS), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Université Le Havre Normandie (ULH), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA), and ANR-18-CE23-0014,APi,Apprivoiser la Pré-image(2018)

Subjects
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-TS] Computer Science [cs]/Signal and Image Processing, [INFO.INFO-NE] Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], [INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG], [INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], [STAT.ML] Statistics [stat]/Machine Learning [stat.ML], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-CY] Computer Science [cs]/Computers and Society [cs.CY], [INFO.INFO-CV] Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [INFO.INFO-CY]Computer Science [cs]/Computers and Society [cs.CY], [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, [MATH.MATH-ST] Mathematics [math]/Statistics [math.ST], [SPI.SIGNAL] Engineering Sciences [physics]/Signal and Image processing
Abstract

International audience; This paper aims at revisiting Convolutional Graph Neural Networks (ConvGNNs) by designing new graph convolutions in spectral domain with a custom frequency profile while applying them in the spatial domain. Within the proposed framework, we propose two ConvGNNs methods: one using a simple single-convolution kernel that operates as a low-pass filter, and one operating multiple convolution kernels called Depthwise Separable Graph Convolution Network (DSGCN). The latter is a generalization of the depthwise separable convolution framework for graph convolutional networks, which allows to decrease the total number of trainable parameters while keeping the capacity of the model unchanged. Our proposals are evaluated on both transductive and inductive graph learning problems, demonstrating that DSGCN outperforms the state-of-the-art methods.

Published
2020

43. Appariement d’ensembles avec édition : Application à la distance d’édition bipartie entre graphes

Author

Bougleux, Sébastien, Gaüzère, Benoit, Brun, Luc, Equipe Image - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA), Equipe Apprentissage (DocApp - LITIS), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Université Le Havre Normandie (ULH), and Bougleux, Sébastien

Subjects
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-CV] Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], ComputingMilieux_MISCELLANEOUS, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

National audience

Published
2016

44. Graph Edit Distance as a Quadratic Program

Author

Bougleux, Sébastien, Gaüzère, Benoit, Brun, Luc, and Brun, Luc

Subjects
[INFO.INFO-CV] Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], Graph edit distance, IPFP
Abstract

The graph edit distance (GED) measures the amount of distortion needed to transform a graph into another graph. Such a distance, developed in the context of error-tolerant graph matching, is one of the most flexible tool used in structural pattern recognition. However, the computation of the exact GED is NP-complete. Hence several suboptimal solutions, such as the ones based on bipartite assignments with edition, have been proposed. In this paper we propose a binary quadratic programming problem whose global minimum corresponds to the exact GED. This problem is interpreted as a quadratic assignment problem (QAP) where some constraints on solutions have been relaxed. This allows to adapt the integer projected fixed point algorithm, initially designed for the QAP, to efficiently compute an approximate GED by finding an interesting local minimum. Experiments show that our method remains quite close to the exact GED for datasets composed of small graphs, while keeping low execution times on datasets composed of larger graphs.

Published
2016

45. A new hypergraph molecular representation

Author

Gaüzère, Benoit, Brun, Luc, Villemin, Didier, Equipe Image - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), Laboratoire de chimie moléculaire et thioorganique (LCMT), Centre National de la Recherche Scientifique (CNRS)-Institut Normand de Chimie Moléculaire Médicinale et Macromoléculaire (INC3M), Institut de Chimie du CNRS (INC)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Université Le Havre Normandie (ULH), Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Institut de Chimie du CNRS (INC)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), and Gaüzère, Benoit

Subjects
[INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], [INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG]
Abstract

National audience; In this contribution, we define a new molecular representation together with a similarity measure which allows to encode adjacency relationships between cycles and their substituents.

Published
2013

46. Graph kernels in chemoinformatics

Author

Gaüzère, Benoit, Brun, Luc, Villemin, Didier, Equipe Image - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), Laboratoire de chimie moléculaire et thioorganique (LCMT), Centre National de la Recherche Scientifique (CNRS)-Institut Normand de Chimie Moléculaire Médicinale et Macromoléculaire (INC3M), Institut de Chimie du CNRS (INC)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Université Le Havre Normandie (ULH), Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Institut de Chimie du CNRS (INC)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Matthias Dehmer and Frank Emmert-Streib, and Brun, Luc

Subjects
graph kernels, [INFO.INFO-CV] Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], [CHIM.CHEM] Chemical Sciences/Cheminformatics, [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], Chemoinformatics, [CHIM.CHEM]Chemical Sciences/Cheminformatics
Abstract

International audience; Graphs provide a generic data structure widely used in chemo and bioin-formatics to represent complex structures such as chemical compounds orcomplex interactions between proteins. However, the high flexibility of thisdata structure does not allow to readily combine it with usual machine learn-ing algorithms based on a vectorial representation of input data. Graph kernels are defined as similarity measures between graphs. Undermild conditions, graph kernels correspond to scalar products between possi-bly implicit graph embeddings into an Hilbert space. Thanks to this graph embedding, machine learning methods which may be rewritten so as to useonly scalar products between input data, such as SVM, can be applied ongraphs. Graph kernels thus provide a natural connection between graph spaceand machine learning.

Published
2015

47. Relationships between Graph Edit Distance and Maximal Common Unlabeled Subgraph

Author

Brun, Luc, Gaüzère, Benoit, Fourey, Sébastien, Equipe Image - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), and Gaüzère, Benoit

Subjects
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], maximum common subgraph, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], graph edit distance, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

Graph edit distance measures the distance between two graphs as the number of elementary operations (vertex/edge insertion, deletion, substitution) required to transform the first graph into the second one. Such a distance allows to define a metric between graphs and has many applications in the structural pattern recognition framework. However, the complexity of the computation of this distance is exponential in the size of both graphs to be compared. In this technical report, we focus our attention on applications where families of graphs to be considered have a finite set of structures. We then investigate under which relationships between the costs of the different elementary operations, such a priori knowledge may be used to pre compute most of the optimal edit path between any two graphs.

Published
2012

48. Deux nouveaux noyaux sur graphes et leurs applications en chimioinformatique

Author

Gaüzère, Benoit, Brun, Luc, Villemin, Didier, Equipe Image - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), Laboratoire de chimie moléculaire et thioorganique (LCMT), Centre National de la Recherche Scientifique (CNRS)-Institut Normand de Chimie Moléculaire Médicinale et Macromoléculaire (INC3M), Institut de Chimie du CNRS (INC)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Université Le Havre Normandie (ULH), Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Institut de Chimie du CNRS (INC)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), and Gaüzère, Benoit

Subjects
[INFO.INFO-CV] Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [CHIM.CHEM] Chemical Sciences/Cheminformatics, [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], [INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG], [CHIM.CHEM]Chemical Sciences/Cheminformatics
Abstract

National audience; La chimioinformatique utilise des méthodes issues de l'informatique, plus particulièrement la théorie des graphes et l'apprentissage automatique, afin de traiter d'importants volumes de données fournis par l'étude de familles de molécules. Dans ce contexte, les noyaux sur graphes fournissent une approche intéressante en combinant les méthodes d'apprentissage automatique avec la théorie des graphes. Précédemment, les noyaux sur graphes ont été appliqués avec succès sur quelques problèmes proposés par la chimioinformatique. Dans cet article, nous présentons deux nouveaux noyaux sur graphes appliqués sur des problèmes de régression et de classification. Le premier noyau est basé sur la notion de distance d'édition entre deux graphes tandis que le second se base sur l'énumération des sous arbres d'un graphe. La dernière partie montre la complémentarité des deux approches grâce à plusieurs expériences.

Published
2011

49. Noyaux sur Graphes en chémoinformatique

Author

Gaüzère, Benoit, Brun, Luc, Villemin, Didier, Centre National de la Recherche Scientifique (CNRS), Equipe Apprentissage (DocApp - LITIS), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Université Le Havre Normandie (ULH), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Normandie Université (NU), Equipe Image - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Laboratoire de chimie moléculaire et thioorganique (LCMT), Centre National de la Recherche Scientifique (CNRS)-Institut Normand de Chimie Moléculaire Médicinale et Macromoléculaire (INC3M), Institut de Chimie du CNRS (INC)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Université Le Havre Normandie (ULH), Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Institut de Chimie du CNRS (INC)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Matthias Dehmer and Frank Emmert-Streib, and Brun, Luc

Subjects
Graph kernels, [INFO.INFO-CV] Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], [CHIM.CHEM] Chemical Sciences/Cheminformatics, [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], chemoinformatics, ComputingMilieux_MISCELLANEOUS, [CHIM.CHEM]Chemical Sciences/Cheminformatics
Abstract

International audience

Published
2014

50. Représentation des cycles d'une molécule sous forme d'hypergraphe

Author

Gaüzère, Benoit, Brun, Luc, Villemin, Didier, Adam, Sébastien, Equipe Image - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), Laboratoire de chimie moléculaire et thioorganique (LCMT), Centre National de la Recherche Scientifique (CNRS)-Institut Normand de Chimie Moléculaire Médicinale et Macromoléculaire (INC3M), Institut de Chimie du CNRS (INC)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Université Le Havre Normandie (ULH), Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN), and Normandie Université (NU)-Institut de Chimie du CNRS (INC)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN)

Subjects
[INFO.INFO-CV] Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], noyau sur graphe, [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], cycles pertinents, chémoinformatique
Abstract

National audience; La chémoinformatique utilise des méthodes issues de la théorie des graphes et de l'apprentissage automatique afin de classifier ou prédire des propriétés moléculaires. De ce point de vue, les noyaux sur graphes constituent une approche intéressante combinant les méthodes d'apprentissage et la représentation naturelle des molécules sous forme de graphes. Cependant, bien que les graphes moléculaires encodent l'ensemble de l'information structurelle des molécules, ils n'encodent pas explicitement l'information cyclique. Dans cet article, nous proposons de représenter une molécule par un hypergraphe encodant explicitement à la fois l'information cyclique et acyclique d'une molécule dans une même représentation. Nous proposons également une mesure de similarité sous forme de noyau afin d'utiliser cette représentation moléculaire dans des problèmes rencontrés en chémoinformatique.

Published
2014

Catalog

Books, media, physical & digital resources
See catalog results