@InProceedings{CI-mariana-2025, author="Brito Azevedo, Mariana and Brun, Luc and H{\'e}roux, Pierre and Lamotte, Jean-Luc and Bureau, Ronan and Lepailleur, Alban", editor="Brun, Luc and Carletti, Vincenzo and Bougleux, S{\'e}bastien and Ga{\"u}z{\`e}re, Beno{\^i}t", title="Graph Neural Network Based on Molecular and Pharmacophoric Features for Drug Design Applications", booktitle="Graph-Based Representations in Pattern Recognition", year="2025", publisher="Springer Nature Switzerland", address="Caen", pages="47--57", abstract="Research fields that leverage relational data, like many others, have been significantly impacted by Deep Learning (DL) techniques, particularly Graph Neural Networks (GNNs). Among these fields, drug design, which aims to create new molecules with optimal affinities for specific targets, is a crucial step in the development of new medicinal drugs. In silico approaches in this area often rely on molecular graphs that encode the atoms and bonds of a molecule, without prior knowledge of the biological properties to be predicted. To address this limitation, pharmacophoric features are essential, as they contain structural information that captures important biological properties. These features have proven effective in tasks involving protein-ligand interactions. In this context, we propose the MCP-GNN model, which combines molecular representations with complete graphs of pharmacophoric features, both based on 2D information, to classify biological activity. Our experimental results demonstrate that this approach, using simple yet efficient techniques, achieves better performance than more complex architectures.", isbn="978-3-031-94139-9", url="Springer:=https://link.springer.com/chapter/10.1007/978-3-031-94139-9_5, HAL:= https://hal.science/hal-05110964v1", theme="pattern" } @article{STANOVIC202514, title = {Graph Neural Networks with maximal independent set-based pooling: Mitigating over-smoothing and over-squashing}, journal = {Pattern Recognition Letters}, volume = {187}, pages = {14-20}, year = {2025}, issn = {0167-8655}, doi = {https://doi.org/10.1016/j.patrec.2024.11.004}, url = {HAL:=https://hal.science/hal-04848262, PRL:=https://www.sciencedirect.com/science/article/pii/S0167865524003106}, author = {Stevan Stanovic and Benoit Gaüzère and Luc Brun}, keywords = {Graph Neural Networks, Graph pooling, Over-squashing, Over-smoothing, Maximal independent sets}, abstract = {Graph Neural Networks (GNNs) have significantly advanced graph-level prediction tasks by utilizing efficient convolution and pooling techniques. However, traditional pooling methods in GNNs often fail to preserve key properties, leading to challenges such as graph disconnection, low decimation ratios, and substantial data loss. In this paper, we introduce three novel pooling methods based on Maximal Independent Sets (MIS) to address these issues. Additionally, we provide a theoretical and empirical study on the impact of these pooling methods on over-smoothing and over-squashing phenomena. Our experimental results not only confirm the effectiveness of using maximal independent sets to define pooling operations but also demonstrate their crucial role in mitigating over-smoothing and over-squashing.}, theme="pattern" } @InProceedings{CI-Wallnig-2024, author = {Julia Wallnig and Luc Brun and Benoit Gaüzère and Sébastien Bougleux and Florian Yger and Blumenthal, David B.}, title = {A Differentiable Approximation of the Graph Edit Distance}, booktitle = {Proceedings of SSPR'2024}, year = 2024, editor = {Andrea Torsello and Luca Rossi}, series = {LNCS}, month = {September}, address = {Venice, Italy}, organization = {IAPR}, publisher = {Springer}, note = {to be published}, theme="pattern,ged", abstract="To determine the similarity of labeled graphs, the graph edit distance (GED) is widely used due to its metric properties on the graph space and its interpretability. It is defined as the minimal cost of a sequence of edit operations transforming one graph into another one, with the cost of each edit operation being a parameter of the distance. Although calculating GED is NP-hard, various heuristics exist which, in practice, typically yield tight upper or lower bounds. Since determining appropriate edit operation costs for a given dataset or application can be challenging, it is attractive to learn these costs from the data, e. g., using metric learning architectures. However, for this approach to be feasible, a differentiable algorithm to approximate the GED is required. In this work, we present such an algorithm and show via an empirical evaluation on three datasets that the obtained distances closely match the distances computed by a state-of-the-art combinatorial GED heuristic.", url={HAL:=https://normandie-univ.hal.science/hal-04740015} } @Article{RI-Seraphim-2024, author = {Mathieu Seraphim and Alexis Lechervy and Florian Yger and Luc Brun and Olivier Etard}, title = {Automatic Classification of Sleep Stages from EEG Signals Using Riemannian Metrics and Transformer Networks}, journal = {Springer Nature Computer Science}, year = 2024, month="Oct", volume="5", number="7", pages="953", theme = "pattern", abstract="In sleep medicine, assessing the evolution of a subject’s sleep often involves the costly manual scoring of electroencephalographic (EEG) signals. In recent years, a number of Deep Learning approaches have been proposed to automate this process, mainly by extracting features from said signals. However, despite some promising developments in related problems, such as Brain-Computer Interfaces, analyses of the covariances between brain regions remain underutilized in sleep stage scoring. Expanding upon our previous work, we investigate the capabilities of SPDTransNet, a Transformer-derived network designed to classify sleep stages from EEG data through timeseries of covariance matrices. Furthermore, we present a novel way of integrating learned signal-wise features into said matrices without sacrificing their Symmetric Definite Positive (SPD) nature. Results: Through comparison with other State-of-the-Art models within a methodology optimized for class-wise performance, we achieve a level of performance at or beyond various State-of-the-Art models, both in single-dataset and - particularly - multi-dataset experiments. In this article, we prove the capabilities of our SPDTransNet model, particularly its adaptability to multi-dataset tasks, within the context of EEG sleep stage scoring - though it could easily be adapted to any classification task involving timeseries of covariance matrices.", url="SNSharedIt:=https://rdcu.be/dWNI2, HAL:=https://hal.science/hal-04638612v1" } @InProceedings{CI-seraphim-2024, author = {Mathieu Seraphim and Alexis Lechervy and Florian Yger and Luc Brun and Olivier Etard}, title = {Structure preserving transformers for sequences of SPD matrices}, booktitle = {Proceedings of EUSIPCO 2024}, year = 2024, pages = {1451-1455}, month = {August}, address = {Lyon, France}, organization = {EURASIP}, url = "Eurasip:=https://eurasip.org/Proceedings/Eusipco/Eusipco2024/pdfs/0001451.pdf, HAL:=https://hal.science/hal-04638595", theme = "pattern", abstract ="In recent years, Transformer-based auto-attention mechanisms have been successfully applied to the analysis of a variety of context-reliant data types, from texts to images and beyond, including data from non-Euclidean geometries. In this paper, we present such a mechanism, designed to classify se- quences of Symmetric Positive Definite matrices while preserving their Riemannian geometry throughout the analysis. We apply our method to automatic sleep staging on timeseries of EEG- derived covariance matrices from a standard dataset, obtaining high levels of stage-wise performance." } @inproceedings{CI-StanovicGB23, author = {Stevan Stanovic and Benoit Ga{\"{u}}z{\`{e}}re and Luc Brun}, editor = {Mario Vento and Pasquale Foggia and Donatello Conte and Vincenzo Carletti}, title = {Maximal Independent Sets for Pooling in Graph Neural Networks}, booktitle = {Graph-Based Representations in Pattern Recognition - 13th {IAPR-TC-15} International Workshop, GbRPR 2023, Vietri sul Mare, Italy, September 6-8, 2023, Proceedings}, series = {Lecture Notes in Computer Science}, volume = {14121}, pages = {113--124}, publisher = {Springer}, year = {2023}, url = {Springer:=https://link.springer.com/chapter/10.1007/978-3-031-42795-4_11, HAL:=https://hal.science/hal-04160860v1}, doi = {10.1007/978-3-031-42795-4\_11}, theme = "pattern", 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. " } @inproceedings{CI-Seraphim23, author = {Mathieu Seraphim and Paul Dequidt and Alexis Lechervy and Florian Yger and Luc Brun and Olivier Etard}, editor = {Nicolas Tsapatsoulis and Andreas Lanitis and Marios Pattichis and Constantinos S. Pattichis and Christos Kyrkou and Efthyvoulos Kyriacou and Zenonas Theodosiou and Andreas Panayides}, title = {Temporal Sequences of {EEG} Covariance Matrices for Automated Sleep Stage Scoring with Attention Mechanisms}, booktitle = {Computer Analysis of Images and Patterns - 20th International Conference, {CAIP} 2023, Limassol, Cyprus, September 25-28, 2023, Proceedings, Part {II}}, series = {Lecture Notes in Computer Science}, volume = {14185}, pages = {67--76}, publisher = {Springer}, year = {2023}, doi = {10.1007/978-3-031-44240-7\_7}, url = {Springer:=https://link.springer.com/chapter/10.1007/978-3-031-44240-7_5, HAL:=https://hal.science/hal-04216925v1}, theme = "pattern", abstract ="Sleep monitoring has traditionally required expensive equipment and expert assessment. Wearable devices are however becoming a viable option for monitoring sleep. This study investigates methods for autonomously identifying sleep segments base on wearable device data. We employ and evaluate machine and deep learning models on the benchmark MESA dataset, with results showing that they outperform traditional methods in terms of accuracy, F1 score, and Matthews Correlation Coefficient (MCC). The most accurate model, namely Light Gradient Boosting Machine, obtained an F1 score of 0.93 and an MCC of 0.73. Additionally, sleep quality metrics were used to assess the models. Furthermore, it should be noted that the proposed approach is device-agnostic, and more accessible and cost-effective than the traditional polysomnography (PSG) methods." } @InProceedings{CI-paulDequidt2023, author = "Paul Dequidt and Mathieu Seraphim and Alexis Lechervy and Ivan Igor Gaez and Luc Brun and Olivier Etard", editor="Juarez, Jose M. and Marcos, Mar and Stiglic, Gregor and Tucker, Allan", title = "Automatic sleep stage classification on EEG signals using time-frequency representation", booktitle = "Proceedings of {AIME} 2023, Slovenia", month = jun, year = 2023, publisher = "Springer Nature", pages="250-259", theme="pattern", url ={Springer:=https://link.springer.com/chapter/10.1007/978-3-031-34344-5_30, HAL:=https://hal.science/hal-04249277v1/document}, abstract="Sleep stage scoring based on electroencephalogram (EEG) signals is a repetitive task required for basic and clinical sleep studies. Sleep stages are defined on 30 seconds EEG-epochs from brainwave patterns present in specific frequency bands. Time-frequency representations such as spectrograms can be used as input for deep learning methods. In this paper we compare different spectrograms, encoding multiple EEG channels, as input for a deep network devoted to the recognition of image's visual patterns. We further investigate how contextual input enhance the classification by using EEG-epoch sequences of increasing lengths. We also propose a common evaluation framework to allow a fair comparison between state-of-art methods. Evaluations performed on a standard dataset using this unified protocol show that our method outperforms four state-of-art methods." } @inProceedings{CN-mathieu2023, author = "Mathieu Seraphim and Paul Dequidt and Alexis Lechervy and Florian Yger and Luc Brun and Olivier Etard", title = "Analyse automatique de l'état de sommeil sur données EEG par utilisation de Transformers et de matrices de covariance", booktitle = "Proceedings of {ORASIS} 2023, Carqueiranne", month = may, year = 2023, publisher = "AFRIF", note = "To be published", theme="pattern", abstract="Les données électroencéphalographiques (EEG) sont communément utilisées en médecine du sommeil. Il s'agit d'un ensemble de signaux électriques cérébraux issus de différents capteurs, subdivisés en segments devant être annotés manuellement pour quantifier les différents stades de sommeil. Ces dernières années, une littérature croissante s'est accumulée sur l'automatisation de ce processus d'annotation, offrant des résultats prometteurs, mais insuffisants pour une utilisation en milieu clinique. Nous proposons d'explorer une approche alternative afin d'améliorer la classification, basée sur l'étude de l'information portée par les covariations entre plusieurs signaux EEG représentatifs de différentes régions cérébrales. Ces covariations prennent la forme de séquences temporelles de matrices de covariance, exploitées au travers de mécanismes d'attention à l'échelle intra-époque et inter-époque. Nous validons nos résultats sur un jeu de données standard de l'État de l'Art. ENGLISH: Electroencephalographic data (EEG) is commonly used in sleep medecine. It consists of a number of cerebral electrical signals measured from various brain locations, subdivided into segments that must be manually scored to reflect their sleep stage. These past few years, multiple implementations of an automatization of this scoring process have been attempted, with promising results, although they are not yet accurate enough to see clinical use. We propose a novel approach, that relies on the information contained within the covariations between multiple EEG signals, each signal reresentative of a different cerebral region. This is done through temporal sequences of covariance matrices, analyzed through attention mechanisms at both the intra- and inter-epoch levels. Evaluation is performed on a standard dataset, for comparison with the State of the Art.", url="HAL(pdf):=https://hal.science/hal-04055874v2/document, HAL:=https://hal.science/hal-04055874v2" } @InProceedings{CI-Brun2022, author = {Luc Brun and Benoit Gauzere and Guillaume Renton and Sebastien Bougleux and Florian Yger}, title = {A differentiable approximation for the Linear Sum Assignment Problem with Edition (LSAPE)}, booktitle = {Proceedinds of 26th ICPR 2022}, year = 2022, month = {August}, address = {Montréal}, organization = {IAPR}, publisher = {IEEE}, theme="pattern", url={HAL:=https://hal.archives-ouvertes.fr/hal-03768664, TR(pdf):=https://hal.archives-ouvertes.fr/hal-03454896/file/main.pdf} abstract="Linear Sum Assignment Problem (LSAP) consists in mapping two sets of points of equal sizes according to a matrix encoding the cost of mapping each pair of points. The Linear Sum Assignment Problem with Edition (LSAPE) extends this problem by allowing the mapping of sets of different sizes and adding the possibility to reject some matchings. This problem is set up by a rectangular cost matrix whose last column and last line encode the costs of rejecting the match of an element of respectively the first and the second sets. LSAPE has been the workhorse of many fundamental graph problems such as graph edit distance, median graph computation or sub graph matching. LSAP may be solved using the Hungarian algorithm while an equivalent efficient discrete algorithm has been designed for LSAPE. However, while the Sinkhorn algorithm constitutes a continuous solver for LSAP, no such algorithm yet exists for LSAPE. This lack of solvers forbids the integration of LSAPE in Neural networks requiring continuous operations from the input to the final loss. This paper aims at providing such a solver, hence paving the way to an integration of LSAPE solvers in Neural Networks." } @inproceedings{CN-Stanovic2022, TITLE = {{Ensemble de sommets ind{\'e}pendant maximal appliqu{\'e} au pooling sur graphes}}, AUTHOR = {Stanovic, Stevan and Ga{\"u}z{\`e}re, Benoit and Brun, Luc}, URL = {HAL:=https://hal.archives-ouvertes.fr/hal-03696263, Pdf:=https://hal.archives-ouvertes.fr/hal-03696263/file/Ensemble_de_sommets_ind_pendant_maximal_appliqu__au_pooling_sur_graphes.pdf}, BOOKTITLE = {{Congr{\`e}s Reconnaissance des Formes, Image, Apprentissage et Perception ( RFIAP)}}, ADDRESS = {VANNES, France}, YEAR = {2022}, MONTH = Jul, KEYWORDS = {Graph Neural Networks ; Graph Pooling ; Graph Classification ; Maximal Independant Vertex Set ; R{\'e}seaux de neurones sur graphes ; Ensemble de sommets ind{\'e}pendant maximal ; Classification de graphes ; Pooling sur graphes}, theme="pattern", abstract={Les réseaux de neurones convolutifs (CNN) ont permis des avancées majeures dans la classification d'images grâce à la convolution et au pooling. En particulier, le pooling sur image transforme une grille discrète connexe en une grille réduite de même connexité et permet aux fonctions de réduction de prendre en compte tous les pixels de l'image. Cependant, un pooling satisfaisant de telles propriétés n'existe pas pour les graphes. En effet, certaines méthodes sont restreintes à la sélection de sommets selon leur importance. Ceci induit la création de graphes réduits non connexes et une perte d'information importante. D'autres méthodes apprennent un partitionnement flou des sommets causant une hyper-connectivité du graphe réduit. Dans cette publication, nous proposons de pallier ces problématiques à l'aide de notre méthode de pooling, nommée MIVSPool. Elle est basée sur une sélection de sommets appelés sommets survivants à l'aide d'un ensemble de sommets indépendant maximal (MIVS) et d'une affectation des autres sommets aux survivants. Par conséquent, notre méthode donne la garantie de préserver la totalité de l'information du graphe lors de sa réduction. Les résultats expérimentaux montrent une augmentation de l'exactitude de la classification sur plusieurs jeux de données standards.} } @techreport{brun:hal-03454896, TITLE = {{A new Sinkhorn algorithm with Deletion and Insertion operations}}, AUTHOR = {Brun, Luc and Ga{\"u}z{\`e}re, Benoit and Bougleux, S{\'e}bastien and Yger, Florian}, TYPE = {Research Report}, INSTITUTION = {{GREYC, UMR 6072}}, YEAR = {2021}, MONTH = Nov, KEYWORDS = {Sinkhorn algorithm ; Linear Sum Assignment problem}, url = {Pdf(HAL):=https://hal.archives-ouvertes.fr/hal-03454896/file/main.pdf,HAL:=https://hal.archives-ouvertes.fr/hal-03454896, ArXiv:=https://arxiv.org/abs/2111.14565, Pdf(ArXiv):=https://arxiv.org/pdf/2111.14565}, HAL_ID = {hal-03454896}, HAL_VERSION = {v1}, theme="pattern", abstract="This 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. Our algorithms are iterative and differentiable and may thus be easily inserted within a backpropagation based learning framework such as artificial neural networks." } @InProceedings{CI-benNaceur-2021, author = {Ben Naceur, Mostefa and Luc Brun and Olivier Lezoray}, title = {Lightweight Deep Symmetric Positive Definite Manifold Network for Real-Time 3D Hand Gesture Recognition}, booktitle = {Proceedings of the IEEE International Conference on Automatic Face and Gesture Recognition 2021}, year = 2021, month = {December}, address = {Jodhpur, India}, organization = {IEEE}, theme="pattern", url= {HAL:=https://hal.science/hal-03531927]}, abstract="This paper proposes a new neural network based on Symmetric Positive Definite (SPD) manifold learning for real-time skeleton-based hand gesture recognition. The transformation of the input skeletal data into SPD matrices allows to encode efficiently high-order statistics such as covariances or correlations between the joints’ features. These matrices are combined and transformed by our deep neural network which is thus constrained to work on the manifold of such matrices. The online recognition is performed using two sliding windows moving along the gesture’s stream in order to simultaneously detect and classify the occurrence of a new gesture within the stream. The proposed network is validated on a challenging dataset and shows state-of-the-art performances both in terms of accuracy and inference time." } @article{BLUMENTHAL2021101766, title = {Scalable generalized median graph estimation and its manifold use in bioinformatics, clustering, classification, and indexing}, journal = {Information Systems}, volume = 100, pages = {101766}, year = {2021}, issn = {0306-4379}, doi = {https://doi.org/10.1016/j.is.2021.101766}, url = {ScienceDirect:=https://www.sciencedirect.com/science/article/pii/S0306437921000284, Code:=https://forge.greyc.fr/projects/gedlibpy/repository}, author = {David B. Blumenthal and Nicolas Boria and Sébastien Bougleux and Luc Brun and Johann Gamper and Benoit Gaüzère}, keywords = {Generalized median graphs, Graph edit distance, Graph similarity search, Clustering, Classification, Indexing}, abstract = {In this paper, we present GMG-BCU —a local search algorithm based on block coordinate update for estimating a generalized median graph for a given collection of labeled or unlabeled input graphs. Unlike all competitors, GMG-BCU is designed for both discrete and continuous label spaces and can be configured to run in linear time w.r.t. the size of the graph collection whenever median node and edge labels are computable in linear time. These properties make GMG-BCU usable for applications such as differential microbiome data analysis, graph classification, clustering, and indexing. We also prove theoretical properties of generalized median graphs, namely, that they exist under reasonable assumptions which are met in almost all application scenarios, that they are in general non-unique, that they are NP-hard to compute and APX-hard to approximate, and that no polynomial α-approximation exists for any α unless the graph isomorphism problem is in P. Extensive experiments on six different datasets show that our heuristic GMG-BCU always outperforms the state of the art in terms of runtime or quality (on most datasets, both w.r.t. runtime and quality), that it is the only available heuristic which can cope with collections containing several thousands of graphs, and that it shows very promising potential when used for the aforementioned applications. GMG-BCU is freely available on GitHub: https://github.com/dbblumenthal/gedlib/.}, theme="pattern" } @inproceedings{CI-GhezaielBL20, author = {Wajdi Ghezaiel and Luc Brun and Olivier L{\'{e}}zoray}, title = {Hybrid Network For End-To-End Text-Independent Speaker Identification}, booktitle = {25th International Conference on Pattern Recognition, {ICPR} 2020, Virtual Event / Milan, Italy, January 10-15, 2021}, pages = {2352--2359}, publisher = {{IEEE}}, year = {2020}, url = {IEEXplore:=https://doi.org/10.1109/ICPR48806.2021.9413293, Slides:=https://brunl01.users.greyc.fr/ARTICLES/Presentation_Ghezaiel_ICPR2020.pdf, PDF:=https://brunl01.users.greyc.fr/ARTICLES/Ghezaiel_icpr2020.pdf,HAL:=https://hal.archives-ouvertes.fr/hal-03086433v1}, timestamp = {Fri, 07 May 2021 12:53:57 +0200}, abstract = "Deep learning has recently improved the performance of Speaker Identification (SI) systems. Promising results have been obtained with Convolutional Neural Networks (CNNs). This success is mostly driven by the advent of large datasets. However in the context of decentralized commercial applications, collection of large amount of training data is not always possible. In addition, robustness of a SI system is adversely effected by short utterances. Therefore, in this paper, we propose a novel text-independent speaker identification system able to identify speakers by learning from only few training short utterances examples. To achieve this, we combine a two-layer wavelet scattering network coupled with a CNN. The proposed architecture takes variable length speech segments. To evaluate the effectiveness of the proposed approach, Timit and Librispeech datasets are used in the experiments. Our experiments shows that our hybrid architecture provides satisfactory results under the constraints of short and limited number of utterances. These experiments also show that our hybrid architecture are competitive with the state of the art.", theme = "pattern" } @inproceedings{CI-GhezaielBL20b, author = {Wajdi Ghezaiel and Luc Brun and Olivier L{\'{e}}zoray}, title = {Wavelet Scattering Transform and {CNN} for Closed Set Speaker Identification}, booktitle = {22nd {IEEE} International Workshop on Multimedia Signal Processing, {MMSP} 2020, Tampere, Finland, September 21-24, 2020}, pages = {1--6}, publisher = {{IEEE}}, year = {2020}, url = {IEEXplore:=https://doi.org/10.1109/MMSP48831.2020.9287061,PDF:=https://brunl01.users.greyc.fr/ARTICLES/Ghezaiel_MMSP2020.pdf,HAL:=https://hal.archives-ouvertes.fr/hal-02955532v1}, timestamp = {Wed, 13 Jan 2021 17:58:38 +0100}, biburl = {https://dblp.org/rec/conf/mmsp/GhezaielBL20.bib}, abstract = "In real world applications, the performances of speaker identification systems degrade due to the reduction of both the amount and the quality of speech utterance. For that particular purpose, we propose a speaker identification system where short utterances with few training examples are used for person identification. Therefore, only a very small amount of data involving a sentence of 2-4 seconds is used. To achieve this, we propose a novel raw waveform end-to-end convolutional neural network (CNN) for text-independent speaker identification. We use wavelet scattering transform as a fixed initialization of the first layers of a CNN network, and learn the remaining layers in a supervised manner. The conducted experiments show that our hybrid architecture combining wavelet scattering transform and CNN can successfully perform efficient feature extraction for a speaker identification, even with a small number of short duration training samples.", theme = "pattern" } @inproceedings{ghezaiel:hal-02552042, TITLE = {{Scattering transform et r{\'e}seaux convolutionels pour l'identification du locuteur}}, AUTHOR = {Ghezaiel, Wajdi and Brun, Luc and L{\'e}zoray, Olivier and Mokhtari, Myriam}, URL = {HAL:=https://hal.archives-ouvertes.fr/hal-02552042, PDF:=https://hal.archives-ouvertes.fr/hal-02552042/file/RFIAP_2020_paper_20.pdf}, BOOKTITLE = {{RFIAP (Reconnaissance des Formes, Image, Apprentissage et Perception)}}, ADDRESS = {Vannes, France}, YEAR = {2020}, MONTH = Jun, HAL_ID = {hal-02552042}, HAL_VERSION = {v1}, abstract="Les assistants vocaux sont devenus très populaires ces der-nières années. Les utilisateurs peuvent contrôler ces ap-pareils intelligents par la voix et obtenir divers services. Combinés à la biométrie, ces dispositifs peuvent permettre de distinguer des profils utilisateurs et sécuriser l'usage de l'appareil. Dans ce scénario, quelques segments de dis-cours de courte durée (2-4 sec.) sont utilisés pour l'au-thentification. Afin de limiter le nombre de paramètres utili-sés pour l'apprentissage, nous proposons de combiner une Wavelet Scattering Transform (ST) et un réseau convolutif (CNN). Nos expérimentations montrent que la combinaison ST/CNN extrait efficacement les caractéristiques de l'iden-tité du locuteur sur des discours de courte durée. Mots Clef Assistant vocal, identification du locuteur, réseau de neurones convolutifs, réseau hybride.", theme="pattern" } @article{blumenthal-2021, author = {David B. Blumenthal and S{\'{e}}bastien Bougleux and Johann Gamper and Luc Brun}, title = {Upper Bounding {GED} via Transformations to {LSAPE} Based on Rings and Machine Learning}, journal = {Int. Journal Pattern Recognition and Artificial Intelligence}, volume = {35}, number = {8}, year = {2021}, url = {ArXiv:=http://arxiv.org/abs/1907.00203, DOI:=https://doi.org/10.1142/S0218001421510083}, eprint = {1907.00203}, timestamp = {Sat, 23 Jan 2021 01:12:27 +0100}, biburl = {https://dblp.org/rec/journals/corr/abs-1907-00203.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, theme="pattern", abstract="The graph edit distance (GED) is a flexible distance measure which is widely used for inexact graph matching. Since its exact computation is NP-hard, heuristics are used in practice. A popular approach is to obtain upper bounds for GED via transformations to the linear sum assignment problem with error-correction (LSAPE). Typically, local structures and distances between them are employed for carrying out this transformation, but recently also machine learning techniques have been used. In this paper, we formally define a unifying framework LSAPE-GED for transformations from GED to LSAPE. We also introduce rings, a new kind of local structures designed for graphs where most information resides in the topology rather than in the node labels. Furthermore, we propose two new ring based heuristics RING and RING-ML, which instantiate LSAPE-GED using the traditional and the machine learning based approach for transforming GED to LSAPE, respectively. Extensive experiments show that using rings for upper bounding GED significantly improves the state of the art on datasets where most information resides in the graphs' topologies. This closes the gap between fast but rather inaccurate LSAPE based heuristics and more accurate but significantly slower GED algorithms based on local search. " } @inproceedings{nguyen-2021, TITLE = {{Learning Recurrent High-order Statistics for Skeleton-based Hand Gesture Recognition}}, AUTHOR = {Nguyen, Xuan Son and Brun, Luc and L{\'e}zoray, Olivier and Bougleux, S{\'e}bastien}, BOOKTITLE = {{International Conference on Pattern Recognition (ICPR - IEEE)}}, ADDRESS = {Milan (virtual), Italy}, YEAR = {2021}, url = {HAL:= https://hal.archives-ouvertes.fr/hal-03107675, pdf:=https://hal.archives-ouvertes.fr/hal-03107675/file/ICPR20__home_papercept_iapr.papercept.net_www_conferences_conferences_ICPR20_submissions_0443_FI.pdf}, HAL_ID = {hal-03107675}, HAL_VERSION = {v1}, theme="pattern", abstract="High-order statistics have been proven useful in the framework of Convolutional Neural Networks (CNN) for a variety of computer vision tasks. In this paper, we propose to exploit high-order statistics in the framework of Recurrent Neural Networks (RNN) for skeleton-based hand gesture recognition. Our method is based on the Statistical Recurrent Units (SRU), an un-gated architecture that has been introduced as an alternative model for Long-Short Term Memory (LSTM) and Gate Recurrent Unit (GRU). The SRU captures sequential information by generating recurrent statistics that depend on a context of previously seen data and by computing moving averages at different scales. The integration of high-order statistics in the SRU significantly improves the performance of the original one, resulting in a model that is competitive to state-of-the-art methods on the Dynamic Hand Gesture (DHG) dataset, and outperforms them on the First-Person Hand Action (FPHA) dataset. " } @article{RI-BORIA2019, title = "Improved local search for graph edit distance", journal = "Pattern Recognition Letters", year = "2020", volume=129, pages={19-25}, issn = "0167-8655", doi = "https://doi.org/10.1016/j.patrec.2019.10.028", url = "ScienceDirect:=http://www.sciencedirect.com/science/article/pii/S016786551930306X, DraftVersion:=https://arxiv.org/pdf/1907.02929.pdf", author = "Nicolas Boria and David B. Blumenthal and Sébastien Bougleux and Luc Brun", keywords = "Graph Edit Distance, local search, stochastic warm start", abstract = "The graph edit distance (GED) measures the dissimilarity between two graphs as the minimal cost of a sequence of elementary operations transforming one graph into another. This measure is fundamental in many areas such as structural pattern recognition or classification. However, exactly computing GED is NP-hard. Among different classes of heuristic algorithms that were proposed to compute approximate solutions, local search based algorithms provide the tightest upper bounds for GED. In this paper, we present K-REFINE and RANDPOST. K-REFINE generalizes and improves an existing local search algorithm and performs particularly well on small graphs. RANDPOST is a general warm start framework that stochastically generates promising initial solutions to be used by any local search based GED algorithm. It is particularly efficient on large graphs. An extensive empirical evaluation demonstrates that both K-REFINE and RANDPOST perform excellently in practice.", theme="pattern,ged" } @InProceedings{CI-Nguyen2019, author = {Nguyen, Xuan Son and Brun, Luc and Lezoray, Olivier and Bougleux, Sebastien}, title = {A Neural Network Based on SPD Manifold Learning for Skeleton-Based Hand Gesture Recognition}, booktitle = {The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)}, month = {June}, year = {2019}, theme="pattern", abstract="This paper proposes a new neural network based on SPD manifold learning for skeleton-based hand gesture recognition. Given the stream of hand's joint positions, our approach combines two aggregation processes on respectively spatial and temporal domains. The pipeline of our network architecture consists in three main stages. The first stage is based on a convolutional layer to increase the discriminative power of learned features. The second stage relies on different architectures for spatial and temporal Gaussian aggregation of joint features. The third stage learns a final SPD matrix from skeletal data. A new type of layer is proposed for the third stage, based on a variant of stochastic gradient descent on Stiefel manifolds. The proposed network is validated on two challenging datasets and shows state-of-the-art accuracies on both datasets." url="openAccess:=http://openaccess.thecvf.com/content_CVPR_2019/papers/Nguyen_A_Neural_Network_Based_on_SPD_Manifold_Learning_for_Skeleton-Based_CVPR_2019_paper.pdf, HAL:=https://hal.archives-ouvertes.fr/hal-02456437v1, PDF(HAL):=https://hal-normandie-univ.archives-ouvertes.fr/hal-02456437/document, arXiv:=https://arxiv.org/abs/1904.12970" } @article{RI-GRENIER2017, title = "Chemoinformatics and stereoisomerism: A stereo graph kernel together with three new extensions", journal = "Pattern Recognition Letters", volume = "87", pages = "222 - 230", year = "2017", note = "Advances in Graph-based Pattern Recognition", issn = "0167-8655", doi = "https://doi.org/10.1016/j.patrec.2016.06.025", url = "ScienceDirect:=http://www.sciencedirect.com/science/article/pii/S0167865516301581", author = "Pierre-Anthony Grenier and Luc Brun and Didier Villemin", keywords = "Chemoinformatics, Stereoisomerism, Graph kernel", abstract = "In chemoinformatics, Quantitative Structure Activity and Property Relationships (QSAR and QSPR) are two fields which aim to predict properties of molecules thanks to computational techniques. In these fields, graph kernels provide a powerful tool which allows to combine the natural encoding of molecules by graphs with usual statistical tools. However, some molecules may have a same graph but differ by the three dimensional orientation of their atoms in space. These molecules, called stereoisomers, may have different properties which cannot be correctly predicted using usual graph encodings. In a previous study we proposed to encode the stereoisomerism property of each atom by a local subgraph, called minimal stereo subgraph, and we designed a kernel based on the comparison of bags of such subgraphs. This kernel allows to predict properties induced by the stereoisomerism which cannot be correctly predicted using usual graph kernels. However, it has two major drawbacks : it considers each minimal stereo subgraph without taking into account its surroundings, and it considers that two non identical minimal stereo subgraphs have a null similarity. In this paper we present three extensions to tackle those drawbacks. The first extension allows to take into account interactions between minimal stereo subgraphs. The second extension allows to compare the neighborhood of minimal stereo subgraphs. And finally, the third extension provides a measure of similarity between different minimal stereo subgraphs.", theme="pattern,chemo" } @Article{RI-Blumenthal2019, author="Blumenthal, David B. and Boria, Nicolas and Gamper, Johann and Bougleux, S{\'e}bastien and Brun, Luc", title="Comparing heuristics for graph edit distance computation", journal="The VLDB Journal", year="2020", volume=29, pages="419-458", month="Jul", day="15", abstract="Because of its flexibility, intuitiveness, and expressivity, the graph edit distance (GED) is one of the most widely used distance measures for labeled graphs. Since exactly computing GED is NP-hard, over the past years, various heuristics have been proposed. They use techniques such as transformations to the linear sum assignment problem with error correction, local search, and linear programming to approximate GED via upper or lower bounds. In this paper, we provide a systematic overview of the most important heuristics. Moreover, we empirically evaluate all compared heuristics within an integrated implementation.", issn="0949-877X", doi="10.1007/s00778-019-00544-1", url="Springer:=https://doi.org/10.1007/s00778-019-00544-1, HAL:=https://hal-normandie-univ.archives-ouvertes.fr/hal-02189832", theme={pattern,ged} } @InProceedings{CI-Blumenthal-2019, author = {David Blumenthal and Sébastien Bougleux and Johann Gamper and Luc Brun}, title = {GEDLIB: A C++ Library for Graph Edit Distance Computation}, booktitle = {12th IAPR TC15 Workshop on Graph-Based Representation in Pattern Recognition (GbR)}, year = 2019, editor = {Donatello Conte and Jean-Yves Ramel and Pasquale Foggia}, volume = 11510, series = {LNCS}, pages = {14-24}, month = {June}, address = {Tours}, organization = {IAPR TC15}, publisher = {Springer}, url={HAL:=https://hal-normandie-univ.archives-ouvertes.fr/hal-02162839, Python Binding(GIT):=https://forge.greyc.fr/projects/gedlibpy/repository}, theme={pattern,ged}, abstract={The graph edit distance (GED) is a flexible graph dissimilarity measure widely used within the structural pattern recognition field. In this paper, we present GEDLIB, a C++ library for exactly or approximately computing GED. Many existing algorithms for GED are already implemented in GEDLIB. Moreover, GEDLIB is designed to be easily extensible: for implementing new edit cost functions and GED algorithms, it suffices to implement abstract classes contained in the library. For implementing these extensions, the user has access to a wide range of utilities, such as deep neural networks, support vector machines, mixed integer linear programming solvers, a blackbox optimizer, and solvers for the linear sum assignment problem with and without error-correction} } @inproceedings{CI-brun2018, TITLE = {{A structural approach to Person Re-identification problem}}, AUTHOR = {Brun, Luc and Mahboubi, Amal and Conte, Donatelo}, BOOKTITLE = {{24th International Conference on Pattern Recognition (ICPR)}}, ADDRESS = {P{\'e}kin, China}, YEAR = {2018}, pages={1616-1621}, MONTH = Aug, url = {HAL:= https://hal-normandie-univ.archives-ouvertes.fr/hal-01865218,HAL(PDF):=https://hal-normandie-univ.archives-ouvertes.fr/hal-01865218/document}, note={ISBN: 978-1-5386-3787-6}, theme={pattern,ged}, abstract={Although it has been studied extensively during past decades, object tracking is still a difficult problem due to many challenges. Several improvements have been done, but more and more complex scenes (dense crowd, complex interactions) need more sophisticated approaches. Particularly long-term tracking is an interesting problem that allow to track objects even after it may become longtime occluded or it leave/re-enter the field-of-view. In this case the major challenges are significantly changes in appearance, scale and so on. At the heart of the solution of long-term tracking is the re-identification technique, that allows to identify an object coming back visible after an occlusion or re-entering on the scene. This paper proposes an approach for pedestrian re-identification based on structural representation of people. The experimental evaluation is carried out on two public data sets (ETHZ and CAVIAR4REID datasets) and they show promising results compared to others state-of-the-art approaches.} } @InProceedings{CI-boria-2019, author = {Nicolas Boria and Sébastien Bougleux and Benoit Gaüzère and Luc Brun}, title = {Generalized Median Graph via Iterative Alternate Minimizations}, booktitle = {Proceedings of the International 12th workshop on Graph-Based Representation in Pattern Recognition}, year = 2019, editor = {Donatello Conte and Jean-Yves Ramel}, series = {LNCS}, month = {June}, address = {Tours}, organization = {IAPR}, publisher = {Springer}, url={HAL:=https://hal-normandie-univ.archives-ouvertes.fr/hal-02162838}, theme="pattern", 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." } @InProceedings{CI-Son-2019, author = {Nguyen, Xuan Son and Luc Brun and Olivier Lezoray and Sébastien Bougleux}, title = {Skeleton-Based Hand Gesture Recognition by Learning SPD Matrices with Neural Networks}, booktitle = {Proceedings of the 14th IEEE International Conference on Automatic Face and Gesture Recognition (FG 2019)}, year = 2019, organization = {IEEE}, theme="pattern", url={HAL:= https://hal.archives-ouvertes.fr/hal-02133684}, abstract=" In this paper, we propose a new hand gesture recognition method based on skeletal data by learning SPD matrices with neural networks. We model the hand skeleton as a graph and introduce a neural network for SPD matrix learning, taking as input the 3D coordinates of hand joints. The proposed network is based on two newly designed layers that transform a set of SPD matrices into a SPD matrix. For gesture recognition, we train a linear SVM classifier using features extracted from our network. Experimental results on a challenging dataset (Dynamic Hand Gesture dataset from the SHREC 2017 3D Shape Retrieval Contest) show that the proposed method outperforms state-of-the-art methods" } @InProceedings{CI-blumenthal18-2, author = {David Blumenthal and Sébastien Bougleux and Johann Gamper and Luc Brun}, title = {Quasimetric Graph Edit Distance As a Compact Quadratic Assignment Problem}, booktitle = {Proceedings of ICPR 2018}, year = 2018, pages = {934-939}, month = {August}, address = {Beijing, China}, organization = {IAPR}, publisher = {IEEE}, note={ISBN: ISBN: 978-1-5386-3787-6}, theme={pattern,ged}, url={HAL:=https://hal-normandie-univ.archives-ouvertes.fr/hal-01865214, HAL(PDF):= https://hal-normandie-univ.archives-ouvertes.fr/hal-01865214/document}, abstract={The graph edit distance (GED) is a widely used distance measure for attributed graphs. It has recently been shown that the problem of computing GED, which is a NP-hard optimization problem, can be formulated as a quadratic assignment problem (QAP). This formulation is useful, since it allows to derive well performing approximative heuristics for GED from existing techniques for QAP. In this paper, we focus on the case where the edit costs that underlie GED are quasimetric. This is the case in many applications of GED. We show that, for quasimetric edit costs, it is possible to reduce the size of the corresponding QAP formulation. An empirical evaluation shows that this reduction significantly speeds up the QAP-based approximative heuristics for GED. } } @InProceedings{CI-blumenthal18, author = {David Blumenthal and Sébastien Bougleux and Johann Gamper and Luc Brun}, title = {Ring Based Approximation of Graph Edit Distance}, booktitle = {Proceedins of Structural, Syntactic, and Statistical Pattern Recognition (SSPR)'2018}, year = 2018, pages= {293-303}, month = {August}, address = {Beijing}, organization = {IAPR}, editor="Bai, Xiao and Hancock, Edwin R. and Ho, Tin Kam and Wilson, Richard C. and Biggio, Battista and Robles-Kelly, Antonio", publisher = {Springer International Publishing}, isbn="978-3-319-97785-0", theme={pattern,ged}, url={PDF(local):=https://brunl01.users.greyc.fr/ARTICLES/sspr18ring-bged.pdf, HAL(PDF):=https://hal-normandie-univ.archives-ouvertes.fr/hal-01865194/file/sspr18ring-bged.pdf, HAL:=https://hal-normandie-univ.archives-ouvertes.fr/hal-01865194}, abstract={The graph edit distance (GED) is a flexible graph dissimilar-ity measure widely used within the structural pattern recognition field. A widely used paradigm for approximating GED is to define local structures rooted at the nodes of the input graphs and use these structures to transform the problem of computing GED into a linear sum assignment problem with error correction (LSAPE). In the literature, different local structures such as incident edges, walks of fixed length, and induced subgraphs of fixed radius have been proposed. In this paper, we propose to use rings as local structure, which are defined as collections of nodes and edges at fixed distances from the root node. We empirically show that this allows us to quickly compute a tight approximation of GED.} } @InProceedings{CI-Daller2018b, author = {\'Evariste Daller and Sébastien Bougleux and Luc Brun and Olivier L\'ezoray}, title = {Local Patterns and Supergraph for Chemical Graph Classification with Convolutional Networks}, booktitle = {Proceedins of Structural, Syntactic, and Statistical Pattern Recognition(SSPR)'2018}, year = 2018, month = {August}, address = {Beijing}, pages="97--106", editor="Bai, Xiao and Hancock, Edwin R. and Ho, Tin Kam and Wilson, Richard C. and Biggio, Battista and Robles-Kelly, Antonio", organization = {IAPR}, publisher = {Springer International Publishing}, theme={pattern,ged}, url={HAL:=https://hal-normandie-univ.archives-ouvertes.fr/hal-01865180, HAL(PDF):=https://hal-normandie-univ.archives-ouvertes.fr/hal-01865180/file/sspr-2018.pdf}, abstract={Convolutional neural networks (CNN) have deeply impacted the field of machine learning. These networks, designed to process objects with a fixed topology, can readily be applied to images, videos and sounds but cannot be easily extended to structures with an arbitrary topology such as graphs. Examples of applications of machine learning to graphs include the prediction of the properties molecular graphs, or the classification of 3D meshes. Within the chemical graphs framework, we propose a method to extend networks based on a fixed topology to input graphs with an arbitrary topology. We also propose an enriched feature vector attached to each node of a chemical graph and a new layer interfacing graphs with arbitrary topologies with a full connected layer. } } @InProceedings{CN-Daller2018c, author = {\'Evariste Daller and Sébastien Bougleux and Luc Brun and Olivier Lezoray}, title = {Motifs locaux et super-graphe pour la classification de graphes symboliques avec des r\'eseaux convolutionnels}, booktitle = {Actes de la con\'erence RFIAP 2018}, year = 2018, month = {Juin}, address = {Marne la val\'ee}, organization = {AFRIF}, theme={pattern,ged}, url={HAL:=https://hal.archives-ouvertes.fr/hal-01796587v1}, abstract="Les r\'eseaux convolutionnels ont r\'evolutionn\'e le domaine de l'apprentissage machine. Ces r\'eseaux s'appliquent naturellement aux images, vid\'eos et aux sons. En revanche, la structure fixe de leur couche d'entr\'ee ne permet pas de les \'etendre facilement à des structures de topologie arbitraire tels que les graphes. On peut citer comme exemples d'applications la pr\'ediction de propri\'et\'es de mol\'ecules chimiques ou la classification de maillages 3D. Dans le cadre de graphes symboliques, nous proposons une m\'ethode permettant d'appliquer des r\'eseaux bas\'es sur une topologie fixe de la couche d'entr\'ee à des graphes de topologie arbitraire. Nous proposons \'egalement d'enrichir l'information contenu dans chaque sommet pour am\'eliorer la pr\'ediction de ses propri\'et\'es ainsi qu'une nouvelle couche permettant d'interfacer des graphes de topologie arbitraire avec une couche entièrement connect\'ee." } @InProceedings{CI-Boria2018, author = {Nicolas Boria and Sébastien Bougleux and Luc Brun}, title = {Approximating GED using a Stochastic Generator and Multistart IPFP}, booktitle = {Proceedings of SSPR'2018}, year = 2018, pages= "460--469", month = {August}, organization = {IAPR}, publisher = {Springer International Publishing}, editor="Bai, Xiao and Hancock, Edwin R. and Ho, Tin Kam and Wilson, Richard C. and Biggio, Battista and Robles-Kelly, Antonio", theme={pattern,ged}, url={HAL:=https://hal-normandie-univ.archives-ouvertes.fr/hal-01865351, HAL(PDF):= https://hal-normandie-univ.archives-ouvertes.fr/hal-01865351/document}, abstract={ The Graph Edit Distance defines the minimal cost of a sequence of elementary operations transforming a graph into another graph. This versatile concept with an intuitive interpretation is a fundamental tool in structural pattern recognition. However, the exact computation of the Graph Edit Distance is N P-complete. Iterative algorithms such as the ones based on Franck-Wolfe method provide a good approximation of true edit distance with low execution times. However, underlying cost function to optimize being neither concave nor convex, the accuracy of such algorithms highly depends on the initialization. In this paper, we propose a smart random initializer using promising parts of previously computed solutions.}, isbn="978-3-319-97785-0" } @InProceedings{CI-daller2018, author = {Evariste Daller and Sébastien Bougleux and Benoit Gaüzère and Luc Brun}, title = {Approximate Graph Edit Distance by Several Local Searches in Parallel}, booktitle = {7th Internation Conference on Pattern Recognition Applications and Methods}, year = 2018, editor = {Ana Fred}, month = "jan", theme="pattern,ged", url={HAL:= https://hal.archives-ouvertes.fr/hal-01664529v1}, abstract="Solving or approximating the linear sum assignment problem (LSAP) is an important step of several constructive and local search strategies developed to approximate the graph edit distance (GED) of two attributed graphs, or more generally the solution to quadratic assignment problems. Constructive strategies find a first estimation of the GED by solving an LSAP. This estimation is then refined by a local search strategy. While these search strategies depend strongly on the initial assignment, several solutions to the linear problem usually exist. They are not taken into account to get better estimations. All the estimations of the GED based on an LSAP select randomly one solution. This paper explores the insights provided by the use of several solutions to an LSAP, refined in parallel by a local search strategy based on the relaxation of the search space, and conditional gradient descent. Two other generators of initial assignments are also considered, approximate solutions to an LSAP and random assignments. Experimental evaluations on several datasets show that the proposed estimation is comparable to more global search strategies in a reduced computational time." } @article{RI-ABUAISHEH201796, title = "Graph edit distance contest: Results and future challenges", journal = "Pattern Recognition Letters", volume = "100", number = "Supplement C", pages = "96 - 103", year = "2017", issn = "0167-8655", doi = "https://doi.org/10.1016/j.patrec.2017.10.007", url = "HAL:=https://hal.archives-ouvertes.fr/hal-01624592, ScienceDirect:=http://www.sciencedirect.com/science/article/pii/S0167865517303690", author = "Zeina Abu-Aisheh and Benoit Gaüzère and Sébastien Bougleux and Jean-Yves Ramel and Luc Brun and Romain Raveaux and Pierre H\'eroux and Sébastien Adam", keywords = "Graph edit distance, Pattern Recognition, Binary linear programming, Quadratic assignment, Branch-and-bound", theme={pattern,ged}, abstract = "Abstract Graph Distance Contest (GDC) was organized in the context of ICPR 2016. Its main challenge was to inspect and report performances and effectiveness of exact and approximate graph edit distance methods by comparison with a ground truth. This paper presents the context of this competition, the metrics and datasets used for evaluation, and the results obtained by the eight submitted methods. Results are analyzed and discussed in terms of computation time and accuracy. We also highlight the future challenges in graph edit distance regarding both future methods and evaluation metrics. The contest was supported by the Technical Committee on Graph-Based Representations in Pattern Recognition (TC-15) of the International Association of Pattern Recognition (IAPR)." } @article{RI-BRUN2018, title = "Trends in graph-based representations for Pattern Recognition", journal = "Pattern Recognition Letters", year = "2018", issn = "0167-8655", doi = "https://doi.org/10.1016/j.patrec.2018.03.016", url = "http://www.sciencedirect.com/science/article/pii/S0167865518300953", author = "Luc Brun and Pasquale Foggia and Mario Vento", keywords = "Graph-based representations, Graph matching, Graph edit distance, Graph kernels", theme={pattern,ged}, abstract = "In this paper we try to examine recent trends on the use of graph-based representations in Pattern Recognition, using as a vantage point the 11th IAPR-TC15 Workshop GbR2017, dedicated to this topic. A survey of the paper presented at GbR2017 will give us the opportunity to reflect on the directions where the interest of the research community working on this subject is moving." } @article{RI-BOUGLEUX2018, title = "Fast linear sum assignment with error-correction and no cost constraints", journal = "Pattern Recognition Letters", volume = "134", pages = {37-45}, year = "2018", issn = "0167-8655", doi = "https://doi.org/10.1016/j.patrec.2018.03.032", url = "ScienceDirect:=http://www.sciencedirect.com/science/article/pii/S0167865518301120, HAL:=https://hal-normandie-univ.archives-ouvertes.fr/hal-02110718v1", author = "Sébastien Bougleux and Benoit Gaüzère and David B. Blumenthal and Luc Brun", keywords = "Inexact graph matching, Linear assignment, Graph edit distance", theme={pattern,ged}, abstract = "We propose an algorithm that efficiently solves the linear sum assignment problem with error-correction and no cost constraints. This problem is encountered for instance in the approximation of the graph edit distance. The fastest currently available solvers for the linear sum assignment problem require the pairwise costs to respect the triangle inequality. Our algorithm is as fast as these algorithms, but manages to drop the cost constraint. The main technical ingredient of our algorithm is a cost-dependent factorization of the node substitutions." } @inproceedings{CI-Bougleux2017, TITLE = {{A Hungarian Algorithm for Error-Correcting Graph Matching}}, AUTHOR = {Bougleux, S{\'e}bastien and Ga{\"u}z{\`e}re, Benoit and Brun, Luc}, BOOKTITLE = {{11th IAPR-TC-15 International Workshop on Graph-Based Representation in Pattern Recognition (GbRPR 2017)}}, ADDRESS = {AnaCapri, Italy}, ORGANIZATION = {{Pasquale Foggia}}, EDITOR = {Pasquale Foggia and Cheng-Lin Liu and Mario Vento}, PUBLISHER = {{Springer}}, SERIES = {Lecture notes in Computer Sciences (LNCS)}, VOLUME = {10310}, PAGES = {118-127}, YEAR = {2017}, MONTH = May, DOI = {10.1007/978-3-319-58961-9\_11}, KEYWORDS = {Graph edit distance ; Bipartite matching ; Error-correcting matching ; Hungarian algorithm}, URL = {PDF(HAL):=https://hal.archives-ouvertes.fr/hal-01540920/file/hungarian-algorithm-error.pdf, www page :=https://hal.archives-ouvertes.fr/hal-01540920}, HAL_ID = {hal-01540920}, HAL_VERSION = {v1}, theme={pattern,ged} } @article{RI-Bougleux2016, title = "Graph edit distance as a quadratic assignment problem ", journal = "Pattern Recognition Letters ", pages = " 38-46", volume=87, year = 2017, note = "Impact factor : 1.586", issn = "0167-8655", doi = "http://dx.doi.org/10.1016/j.patrec.2016.10.001", url = "ScienceDirect:=http://www.sciencedirect.com/science/article/pii/S0167865516302665,HAL:=https://hal-normandie-univ.archives-ouvertes.fr/hal-01613964v1", author = "Sébastien Bougleux and Luc Brun and Vincenzo Carletti and Pasquale Foggia and Benoit Gaüzère and Mario Vento", keywords = "Structural pattern recognition", keywords = "Graph edit distance", keywords = "Edit paths", keywords = "Quadratic assignment problem", keywords = "Combinatorial optimization", keywords = "Relaxation methods ", abstract = "Abstract The Graph Edit Distance (GED) is a flexible measure of dissimilarity between graphs which arises in error-correcting graph matching. It is defined from an optimal sequence of edit operations (edit path) transforming one graph into another. Unfortunately, the exact computation of this measure is NP-hard. In the last decade, several approaches were proposed to approximate the \{GED\} in polynomial time, mainly by solving linear programming problems. Among them, the bipartite \{GED\} 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. This is achieved 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 adapting two algorithms: Integer Projected Fixed Point method and Graduated Non Convexity and Concavity Procedure. Experiments show that the proposed approach is generally able to reach a more accurate approximation of the exact \{GED\} than the bipartite GED, with a computational cost that is still affordable for graphs of non trivial sizes. ", theme={pattern,ged} } @InProceedings{Grenier2016, author = {Grenier, Pierre Anthony and Luc Brun and Didier Villemin}, title = {Taking into Account Stereoisomerism in the Prediction of Molecular Properties}, booktitle = {Proceedings of ICPR 2016}, year = 2016, month = {December}, address = {Cancun}, organization = {IAPR}, pages ="1543-1548", publisher = {IEEE}, theme= "pattern,chemo", url={PDF:=https://brunl01.users.greyc.fr/ARTICLES/grenier2016.pdf, HAL:=https://hal.archives-ouvertes.fr/hal-01418939} } @inproceedings{RhabiSBCL16, author = {Rhabi, Youssef El and Lo{\"{\i}}c Simon and Luc Brun and Llados Canet, Josep and Felipe Lumbreras}, title = {Information Theoretic Rotationwise Robust Binary Descriptor Learning}, booktitle = {Structural, Syntactic, and Statistical Pattern Recognition - Joint {IAPR} International Workshop, {S+SSPR} 2016, M{\'{e}}rida, Mexico, November 29 - December 2, 2016, Proceedings}, pages = {368--378}, year = {2016}, month ={November}, url = {Springer:=http://dx.doi.org/10.1007/978-3-319-49055-7_33, HAL:=https://hal.archives-ouvertes.fr/hal-01418934}, theme="pattern" } @inproceedings{GauzereBB16, author = {Benoit Ga{\"{u}}z{\`{e}}re and S{\'{e}}bastien Bougleux and Luc Brun}, title = {Approximating Graph Edit Distance Using {GNCCP}}, booktitle = {Structural, Syntactic, and Statistical Pattern Recognition - Joint {IAPR} International Workshop, {S+SSPR} 2016, M{\'{e}}rida, Mexico, November 29 - December 2, 2016, Proceedings}, pages = {496--506}, year = {2016}, month = {November}, crossref = {DBLP:conf/sspr/2016}, url = {Springer:=http://dx.doi.org/10.1007/978-3-319-49055-7_44, HAL:=https://hal.archives-ouvertes.fr/hal-01418936}, doi = {10.1007/978-3-319-49055-7_44}, theme= "pattern,ged" } @inproceedings{CI-bougleux2016, TITLE = {{Graph Edit Distance as a Quadratic Program}}, AUTHOR = {Bougleux, S{\'e}bastien and Ga{\"u}z{\`e}re, Benoit and Brun, Luc}, URL = {HAL:=https://hal.archives-ouvertes.fr/hal-01418937, PDF:=https://hal.archives-ouvertes.fr/hal-01418937/file/icpr.pdf}, BOOKTITLE = {{ICPR 2016 23rd International Conference on Pattern Recognition}}, pages ="1701–1706", ADDRESS = {Cancun, Mexico}, PUBLISHER = {{IEEE}}, SERIES = {Proceedings of ICPR 2016}, YEAR = {2016}, MONTH = December, KEYWORDS = {Graph edit distance ; IPFP ; }, HAL_ID = {hal-01418937}, HAL_VERSION = {v1}, theme="pattern,ged" } @techreport{bougleux2016, TITLE = {{Linear Sum Assignment with Edition}}, AUTHOR = {Bougleux, S{\'e}bastien and Brun, Luc}, TYPE = {Research Report}, INSTITUTION = {{Normandie Universit{\'e} ; GREYC CNRS UMR 6072}}, YEAR = {2016}, MONTH = March, KEYWORDS = {Bipartite graph matching ; Edit Distance ; Hungarian Method ; Assignment Problem ; Matching Technique ; Assignment algorithms}, url = {HAL:=https://hal.archives-ouvertes.fr/hal-01288288, PDF:= https://hal.archives-ouvertes.fr/hal-01288288/file/lsape-rr.pdf, arXiv:=https://arxiv.org/abs/1603.04380}, HAL_ID = {hal-01288288}, HAL_VERSION = {v3}, theme= "pattern,ged" } @InProceedings{Hafiane2015, author = {Rachid Hafiane and Luc Brun and Salvatore Tabbone}, title = {Incremental embedding within a dissimilarity-based framework}, booktitle = { Proceedings of the 10 th IAPR-TC15 Workshop on Graph-based Representations (GbR) in Pattern Recognition}, year = 2015, editor = {Cheng-Lin Liu and Bin Luo and Kropatsch, Walter G. and Jian Cheng}, volume = 9069, series = {LNCS}, pages = {64-73}, month = {May}, address = {Bejing, China}, organization = {IAPR TC15}, publisher = {Springer International Publishing}, note = {aceptance rate:67.9\% }, theme= "pattern" } @InProceedings{Grenier2015, author = {Pierre-Anthony Grenier and Luc Brun and Didier Villemin}, title = {From bags to graphs of stereo subgraphs in order to predict molecule's properties}, booktitle = { Proceedings of the 10 th IAPR-TC15 Workshop on Graph-based Representations (GbR) in Pattern Recognition}, year = 2015, editor = {Cheng-Lin Liu and Bin Luo and Kropatsch, Walter G. and Jian Cheng}, volume = 9069, series = {LNCS}, pages = {305-314}, month = {May}, address = {Bejing, China}, organization = {IAPR TC15}, url ={HAL:=https://hal-normandie-univ.archives-ouvertes.fr/hal-01848014v1, ResearchGate:=https://www.researchgate.net/publication/300896987_From_Bags_to_Graphs_of_Stereo_Subgraphs_in_Order_to_Predict_Molecule'S_Properties}, publisher = {Springer International Publishing}, note = {aceptance rate:67.9\% }, theme= "pattern,chemo", abstract={Quantitative Structure Activity and Property Relationships (QSAR and QSPR), aim to predict properties of molecules thanks to computational techniques. In these fields, graphs provide a natural encoding of molecules. However some molecules may have a same graph but differ by the three dimensional orientation of their atoms in space. These molecules, called stereoisomers, may have different properties which cannot be correctly predicted using usual graph encodings. In a previous paper we proposed to encode the stereoisomerism property of each atom by a local subgraph. A kernel between bags of such subgraphs then provides a similarity measure incorporating stereoisomerism properties. However, such an approach does not take into account potential interactions between these subgrahs. We thus propose in this paper, a method to take these interactions into account hence providing a global point of view on molecules’s stereoisomerism properties.} } @InProceedings{Vincenzo2015, author = {Vincenzo Carletti and Benoit Gaüzère and Luc Brun and Mario Vento}, title = {Approximate Graph Edit Distance Computation Combining Bipartite Matching and Exact Neighborhood Substructure Distance}, booktitle = {Proceedings of the 10 th IAPR-TC15 Workshop on Graph-based Representations (GbR) in Pattern Recognition}, year = 2015, editor = {Cheng-Lin Liu and Bin Luo and Kropatsch, Walter G. and Jian Cheng}, volume = 9069, series = {LNCS}, pages = {188-197}, month = {May}, address = {Bejing, China}, organization = {IAPR TC15}, url ={draft version (PDF) :=https://brunl01.users.greyc.fr/ARTICLES/gbr2015Carletti.pdf, HAL:= https://hal.archives-ouvertes.fr/hal-01389626}, publisher = {Springer International Publishing}, note = {aceptance rate:67.9\% }, theme= "pattern,ged", abstract={Graph edit distance corresponds to a flexible graph dissimilarity measure. Unfortunately, its computation requires an exponential complexity according to the number of nodes of both graphs being compared. Some heuristics based on bipartite assignment algorithms have been proposed in order to approximate the graph edit distance. However, these heuristics lack of accuracy since they are based either on small patterns providing a too local information or walks whose tottering induce some bias in the edit distance calculus. In this work, we propose to extend previous heuristics by considering both less local and more accurate patterns defined as subgraphs defined around each node.} } @article{BrunAction2015, title = {Action recognition by using kernels on aclets sequences}, author = {L. Brun and G. Percannella and A. Saggese and M. Vento}, url = {CVIU:=http://www.sciencedirect.com/science/article/pii/S1077314215001988,HAL:=https://hal-normandie-univ.archives-ouvertes.fr/hal-01921521v1}, year = {2016}, journal = {Computer Vision and Image Understanding}, keywords = {Video analysis and interpretation}, pubstate = {published}, tppubtype = {article}, pages={3-13}, volume=144, theme="pattern", abstract= "In this paper we propose a method for human action recognition based on a string kernel framework. An action is represented as a string, where each symbol composing it is associated to an aclet, that is an atomic unit of the action encoding a feature vector extracted from raw data. In this way, measuring similarities between actions leads to design a similarity measure between strings. We propose to define this string’s similarity using the global alignment kernel framework. In this context, the similarity between two aclets is computed by a novel soft evaluation method based on an enhanced gaussian kernel. The main advantage of the proposed approach lies in its ability to effectively deal with actions of different lengths or different temporal scales as well as with noise introduced during the features extraction step. The proposed method has been tested over three publicly available datasets, namely the MIVIA, the CAD and the MHAD, and the obtained results, compared with several state of the art approaches, confirm the effectiveness and the applicability of our system in real environments, where unexperienced operators can easily configure it." } @techreport{bougleux:hal-01246709, TITLE = {{A Quadratic Assignment Formulation of the Graph Edit Distance}}, AUTHOR = {Bougleux, S{\'e}bastien and Brun, Luc and Carletti, Vincenzo and Foggia, Pasquale and Ga{\"u}z{\`e}re, Benoit and Vento, Mario}, TYPE = {Research Report}, INSTITUTION = {{Normandie Universit{\'e} ; GREYC CNRS UMR 6072 ; LITIS}}, YEAR = {2015}, MONTH = Dec, KEYWORDS = { Relaxation methods ; Structural pattern recognition ; Graph edit distance ; Edit paths ; Quadratic assignment problem ; Combinatorial optimization}, url = {PDF:= https://hal.archives-ouvertes.fr/hal-01246709/file/technical_report_ged.pdf, HAL:=https://hal.archives-ouvertes.fr/hal-01246709,arXiv:=https://arxiv.org/abs/1512.07494}, HAL_ID = {hal-01246709}, HAL_VERSION = {v1}, theme="pattern,ged" } @inproceedings{CI-visapp15_ed, title = {Recognition of human actions using edit distance on aclet strings}, author = {L. Brun and P. Foggia and A. Saggese and M. Vento}, year = {2015}, date = {2015-03-13}, url = {HAL:=https://hal-normandie-univ.archives-ouvertes.fr/hal-01921532v1}, booktitle = {V.I.S.A.P.P 2015}, keywords = {Video analysis and interpretation}, theme="pattern" } @inproceedings{CI-avss14_string, title = {HacK: A System for the Recognition of Human Actions by Kernels of Visual Strings}, author = {L. Brun and G. Percannella and A. Saggese and M. Vento}, editor = {IEEE}, isbn = {978-1-4799-4871-0/14}, year = {2014}, date = {2014-08-29}, booktitle = {IEEE International Conference on Advanced Video and Signal-Based Surveillance (AVSS 2014)}, address={Seoul, Korea}, url ={HAL:=https://hal-normandie-univ.archives-ouvertes.fr/hal-01921540v1}, keywords = {Video analysis and interpretation}, theme="pattern" } @inproceedings{CI-avss14_vrs1, title = {Detection of Anomalous Driving Behaviors by Unsupervised Learning of Graphs}, author = {L. Brun and B. Cappellania and A. Saggese and M. Vento}, editor = {IEEE}, isbn = {978-1-4799-4871-0/14}, year = {2014}, date = {2014-08-29}, booktitle = {IEEE International Conference on Advanced Video and Signal-Based Surveillance (AVSS 2014)}, address={Seoul, Korea}, url ={HAL:=https://hal-normandie-univ.archives-ouvertes.fr/hal-01921543v1}, keywords = {Video analysis and interpretation}, theme="pattern" } @inproceedings{CI-avss14_vrs2, title = {A Reliable String Kernel based Approach for Solving Queries by Sketch}, author = {L. Brun and A. Saggese and M. Vento}, editor = {IEEE}, isbn = {978-1-4799-4871-0/14}, year = {2014}, date = {2014-08-29}, booktitle = {IEEE International Conference on Advanced Video and Signal-Based Surveillance (AVSS 2014)}, address={Seoul, Korea}, keywords = {Video analysis and interpretation}, theme="pattern", url = {ResearchGate:=https://www.researchgate.net/publication/265167481_A_Reliable_String_Kernel_based_Approach_for_Solving_Queries_by_Sketch#fullTextFileContent}, abstract ={In this paper we propose a novel and efficient method for solving queries by sketch in traffic scenarios, aiming to find the k nearest neighbor trajectories to the one hand drawn by the human operator. Each trajectory is represented as a sequence of symbols, namely a string, and it is stored into a k-d tree by taking into account the similarity between trajectories, evaluated by a global fast alignment kernel. The experimentation has been conducted over the standard MIT trajectories dataset and results confirm the effective- ness and the robustness of the proposed approach} } @article{CI-Saggesse-elcvia_14, title = {Detecting and indexing moving objects for Behavior Analysis by Video and Audio Interpretation}, author = {A. Saggese and L. Brun and M. Vento}, url = {http://elcvia.cvc.uab.es/article/view/603}, issn = {1577-5097}, year = {2014}, date = {2014-06-07}, journal = {Electronic Letters on Computer Vision and Image Analysis}, volume = {13}, number = {2}, keywords = {Audio analysis and interpretation, Video analysis and interpretation}, theme="pattern" } @inproceedings{CI-Gauzere2014b, url = {HAL:= http://hal.archives-ouvertes.fr/hal-01066389, Pdf:=http://hal.archives-ouvertes.fr/hal-01066389/PDF/GauzereAl-ICPR2014-Graph\_kernel\_encoding\_substituents\_relative\_positioning.pdf}, title = {Graph kernel encoding substituents relative positioning}, author = {Ga{\"u}z{\`e}re, Benoit and Brun, Luc and Villemin, Didier}, abstract = {Chemoinformatics aims to predict molecular properties using informational methods. Computer science's research fields concerned by this domain are machine learning and graph theory. An interesting approach consists in using graph kernels which allow to combine graph theory and machine learning frameworks. Graph kernels allow to define a similarity measure between molecular graphs corresponding to a scalar product in some Hilbert space. Most of existing graph kernels proposed in chemoinformatics do not allow to explicitly encode cyclic information, hence limiting the efficiency of these approaches. In this paper, we propose to define a cyclic representation encoding the relative positioning of substituents around a cycle. We also propose a graph kernel taking into account this information. This contribution has been tested on three classification problems proposed in chemoinformatics.}, affiliation = {Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen - GREYC , Laboratoire de chimie mol{\'e}culaire et thioorganique - LCMT}, booktitle = {Proceedings of International Conference on Pattern Recognition (ICPR), 2014}, pages = {6 p.}, address = {Stockholm(SE)}, year = {2014}, month = Sep, theme = "pattern,chemo" } @article{RI-gauzere2014, hal_id = {hal-01066295}, title = {Treelet kernel incorporating cyclic, stereo and inter pattern information in Chemoinformatics}, author = {Ga{\"u}z{\`e}re, Benoit and Grenier, Pierre-Anthony and Brun, Luc and Villemin, Didier}, keywords = {Chemoinformatics; Graph kernel; Machine learning}, language = {Anglais}, affiliation = {Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen - GREYC , Laboratoire de chimie mol{\'e}culaire et thioorganique - LCMT}, volume=48, number=2, pages = {356-367}, journal = {Pattern Recognition}, audience = {international}, year = {2015}, month = "February", url = {HAL :=http://hal.archives-ouvertes.fr/hal-01066295, Pdf := http://hal.archives-ouvertes.fr/hal-01066295/PDF/article.pdf}, abstract = {Chemoinformatics is a research field concerned with the study of physical or biological molecular properties through computer science's research fields such as machine learning and graph theory. From this point of view, graph kernels provide a nice framework which allows to naturally combine machine learning and graph theory techniques. Graph kernels based on bags of patterns have proven their efficiency on several problems both in terms of accuracy and computational time. Treelet kernel is a graph kernel based on a bag of small subtrees. We propose in this paper several extensions of this kernel devoted to chemoinformatics problems. These extensions aim to weight each pattern according to its influence, to include the comparison of non-isomorphic patterns, to include stereo information and finally to explicitly encode cyclic information into kernel computation.}, theme = {pattern,chemo} } @inproceedings{CN-Gauzere2014c, hal_id = {hal-00989071}, url = {Description := http://hal.archives-ouvertes.fr/hal-00989071, pdf:=http://hal.archives-ouvertes.fr/hal-00989071/PDF/rfia2014\_submission\_51.pdf}, title = {Repr{\'e}sentation des cycles d'une mol{\'e}cule sous forme d'hypergraphe}, author = {Ga{\"u}z{\`e}re, Benoit and Brun, Luc and Villemin, Didier}, abstract = {La ch{\'e}moinformatique utilise des m{\'e}thodes issues de la th{\'e}orie des graphes et de l'apprentissage automatique afin de classifier ou pr{\'e}dire des propri{\'e}t{\'e}s mol{\'e}culaires. De ce point de vue, les noyaux sur graphes constituent une approche int{\'e}ressante combinant les m{\'e}thodes d'apprentissage et la repr{\'e}sentation naturelle des mol{\'e}cules sous forme de graphes. Cependant, bien que les graphes mol{\'e}culaires encodent l'ensemble de l'information structurelle des mol{\'e}cules, ils n'encodent pas explicitement l'information cyclique. Dans cet article, nous proposons de repr{\'e}senter une mol{\'e}cule par un hypergraphe encodant explicitement {\`a} la fois l'information cyclique et acyclique d'une mol{\'e}cule dans une m{\^e}me repr{\'e}sentation. Nous proposons {\'e}galement une mesure de similarit{\'e} sous forme de noyau afin d'utiliser cette repr{\'e}sentation mol{\'e}culaire dans des probl{\`e}mes rencontr{\'e}s en ch{\'e}moinformatique.}, booktitle = {Actes de la conf{\'e}rence RFIA 2014}, address = {Rouen, France}, audience = {nationale }, year = {2014}, month = Jun, theme = {pattern,chemo} } @inproceedings{CI-grenier2014c, hal_id = {hal-00988762}, url = {Description := http://hal.archives-ouvertes.fr/hal-00988762, pdf:= http://hal.archives-ouvertes.fr/hal-00988762/PDF/rfia2014\_submission\_88.pdf}, title = {{Un noyau sur graphe prenant en compte la st{\'e}r{\'e}oisom{\'e}rie des mol{\'e}cules}}, author = {Grenier, Pierre-Anthony and Brun, Luc and Villemin, Didier}, abstract = {{L'{\'e}tude des relations quantitatives structure-activit{\'e} (QSAR) ou structure-propri{\'e}t{\'e} (QSPR) sont deux domaines de recherche actifs, o{\`u} le but est la pr{\'e}diction de propri{\'e}t{\'e}s de mol{\'e}cules. Dans ces domaines, les noyaux sur graphes permettent de combiner la repr{\'e}sentation naturelle des mol{\'e}cules par des graphes avec des m{\'e}thodes classiques d'apprentissage automatique tels que les machines {\`a} vecteurs de support. Malheureusement, le positionnement relatif des atomes dans l'espace peut {\^e}tre diff{\'e}rent pour des mol{\'e}cules repr{\'e}sent{\'e}es par un m{\^e}me graphe, ces mol{\'e}cules peuvent donc avoir des propri{\'e}t{\'e}s diff{\'e}rentes. Ces mol{\'e}cules sont appel{\'e}es st{\'e}r{\'e}oisom{\`e}res. Les propri{\'e}t{\'e}s variant entre les st{\'e}r{\'e}oisom{\`e}res ne peuvent pas {\^e}tre pr{\'e}dites par les m{\'e}thodes habituelles bas{\'e}es sur des graphes simples. Dans cet article, nous pr{\'e}sentons une nouvelle repr{\'e}sentation des mol{\'e}cules qui prend en compte la st{\'e}r{\'e}oisom{\'e}rie et nous proposons un noyau entre ces structures permettant de pr{\'e}dire des propri{\'e}t{\'e}s li{\'e}es {\`a} la st{\'e}r{\'e}oisom{\'e}rie.}}, booktitle = {{Actes de la conf{\'e}rence RFIA 2014}}, address = {France}, year = {2014}, month = Jun, theme = {pattern,chemo}, } @inproceedings{CI-Grenier2014b, hal_id = {hal-01059530}, title = {{A Graph Kernel incorporating molecule's stereisomerism information}}, author = {Grenier, Pierre-Anthony and Brun, Luc and Villemin, Didier}, abstract = {{The prediction of molecule's properties through Quantitative Structure Activity (resp. Property) Relationships are two active research fields named QSAR and QSPR. Within these frameworks Graph kernels allow to combine a natural encoding of a molecule by a graph with classical statistical tools such as SVM or kernel ridge regression. Unfortunately some molecules encoded by a same graph and differing only by the three dimensional orientations of their atoms in space have different properties. Such molecules are called stereoisomers. These latter properties can not be predicted by usual graph methods which do not encode stereoisomerism. In this paper we propose a new graph encoding of molecules taking explicitly into account stereoisomerism and propose a new kernel between these structures in order to predict properties related to stereoisomerism.}}, booktitle = {{Proceedings of ICPR 2014}}, pages = {-}, address = {Stockholm, Su{\`e}de}, year = {2014}, month = Aug, url = {HAL:=http://hal.archives-ouvertes.fr/hal-01059530}, theme="pattern,chemo" } @inproceedings{CI-Grenier2014, author = {Pierre{-}Anthony Grenier and Luc Brun and Didier Villemin}, title = {Incorporating Molecule's Stereisomerism within the Machine Learning Framework}, booktitle = {Structural, Syntactic, and Statistical Pattern Recognition - Joint{IAPR} International Workshop, {S+SSPR} 2014. Proceedings}, address ={Joensuu, Finland}, month ={August 20-22}, year = {2014}, pages = {12--21}, theme = "pattern,chemo", doi = {10.1007/978-3-662-44415-3_2}, url ={LNCS:=http://dx.doi.org/10.1007/978-3-662-44415-3_2, HAL:=http://hal.archives-ouvertes.fr/docs/01/05/95/21/PDF/article.pdf} } @inproceedings{Mahboubi2014, author = {Amal Mahboubi and Luc Brun and Donatello Conte and Pasquale Foggia and Mario Vento}, title = {Tracking System with Re-identification Using a {RGB} String Kernel}, booktitle = {Structural, Syntactic, and Statistical Pattern Recognition - Joint IAPR International Workshop, S+SSPR 2014. Proceedings}, address ={Joensuu, Finland}, month ={August 20-22}, year = {2014}, pages = {333--342}, doi = {10.1007/978-3-662-44415-3_34}, theme = "pattern" } @inproceedings{CI-Gauzere2014, author = {Benoit Ga{\"{u}}z{\`{e}}re and S{\'{e}}bastien Bougleux and Kaspar Riesen and Luc Brun}, title = {Approximate Graph Edit Distance Guided by Bipartite Matching of Bags of Walks}, booktitle = {Structural, Syntactic, and Statistical Pattern Recognition - Joint{IAPR} International Workshop, {S+SSPR} 2014. Proceedings}, address ={Joensuu, Finland}, month ={August 20-22}, year = {2014}, pages = {73--82}, url = {DOI:=http://dx.doi.org/10.1007/978-3-662-44415-3_8, HAL:=http://hal.archives-ouvertes.fr/hal-01066384, Pdf:= http://hal.archives-ouvertes.fr/docs/01/06/63/84/PDF/ssspr2014_submission_59.pdf}, theme = "pattern,chemo,ged" } @InBook{CL-Gauzere2014, author = {Benoit Gaüzère and Luc Brun and Didier Villemin}, title = {Quantitative Graph Theory: Mathematical Foundations and Applications}, chapter = {Graph kernels in chemoinformatics}, publisher = {CRC Press}, year = 2014, series = {Discrete Mathematics and Its Applications}, theme= "pattern,chemo", url = {Draft version(pdf):=https://brunl01.users.greyc.fr/ARTICLES/BookGraphKernel.pdf} } @inproceedings{CI-Brun2013, title = {Learning and classification of car trajectories in road video by string kernels}, author = {Luc Brun and Alessia Saggese and Mario Vento}, year = {2013}, date = {2013-01-01}, booktitle = {Proceedings of the International Conference on Computer Vision Theory and Applications (V.I.S.A.P.P)}, address={Barcelona, Spain}, pages = {709-714}, keywords = {Video analysis and interpretation}, theme="pattern", abstract= {An abnormal behavior of a moving vehicule or a moving person is characterized by an unusual or not expected trajectory. The definition of exptected trajectories refers to supervised learning where an human operator should define expected behaviors. Conversely, definition of usual trajectories, requires to learn automatically the dynamic of a scene in order to extract its typical trajectories. We propose, in this paper, a method able to identify abnormal behaviors based on a new unsupervised learning algorithm. The original contributions of the paper lies in the following aspects: first, the evaluation of similarities between trajectories is based on string kernels. Such kernels allow us to define a kernel-based clustering algorithm in order to obtain groups of similar trajectories. Finally, identification of abnormal trajectories is performed according to the typical trajectories characterized during the clustering step. The method has been evaluated on a real dataset and comparisons with other state-of-the-arts methods confirm its efficiency.}, url= {paper:=https://brunl01.users.greyc.fr/ARTICLES/visapp2013.pdf} } @Article{RI-brun-2014, author = {Luc Brun and Alessia Saggese and Mario Vento}, title = {Dynamic Scene Understanding for behavior analysis based on string kernels}, journal = {Circuits and Systems for Video Technology, IEEE Transactions on}, year = 2014, volume = {24}, number = 10, pages = {1669 - 1681}, theme = "pattern", abstract={This work aims at dynamically understanding the properties of a scene from the analysis of moving object trajectories. Two different applications are proposed: the first one is devoted to identify abnormal behaviors, while the latter allows to extract the k most similar trajectories to the one handdrawn by an human operator. A set of normal trajectories’ models is extracted by means of a novel unsupervised learning technique: the scene is adaptively partitioned into zones by using the distribution of the training set and each trajectory is represented as a sequence of symbols by taking into account positional information (the zones crossed in the scene), speed and shape. The main novelties are the following: first, the use of a kernel based approach for evaluating the similarity between trajectories. Furthermore, we define a novel and efficient kernelbased clustering algorithm, aimed at obtaining groups of normal trajectories. Experimentations, conducted over three standard datasets, confirm the effectiveness of the proposed approach.}, url={TR(pdf):= https://brunl01.users.greyc.fr/ARTICLES/TR_traj_string_kernel.pdf} } @inproceedings{CN-gauzere-2013, title = {A new hypergraph molecular representation}, author = {Gaüzère, Benoit and Brun, Luc and Villemin, Didier}, abstract = {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.}, language = {Anglais}, affiliation = {Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen - GREYC , Laboratoire de chimie moleculaire et thioorganique - LCMT}, booktitle = {Actes des 6 iemes Journees de la Chemoinformatique.}, pages = {1}, address = {Nancy, France}, audience = {internationale }, year = {2013}, month = Oct, theme="pattern,chemo", url = {abstract:=http://hal.archives-ouvertes.fr/hal-00867298,pdf := http://hal.archives-ouvertes.fr/hal-00867298/PDF/article.pdf} } @inproceedings{CN-grenier-2013, title = {{Chiral Kernel : Taking into account stereoisomerism}}, author = {Grenier, Pierre-Anthony and Brun, Luc and Villemin, Didier}, keywords = {Chemoinformatics; Graph kernel; Chirality}, language = {Anglais}, affiliation = {Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen - GREYC , Laboratoire de chimie mol{\'e}culaire et thioorganique - LCMT}, booktitle = {6emes journees de la Societe Francaise de Chemoinformatique (SFCi)}, address = {Nancy, France}, audience = {nationale }, year = {2013}, month = Oct, theme="pattern,chemo", abstract = {Graph kernels provides a framework combining machine learning and graph theory. However, kernels based upon the molecular graph, which can not distinguish stereoisomers, are unable to predict properties which differs among stereoisomers. This article presents a graph kernel which takes into account chirality, and is used (in combination with a classical graph kernel) to predict the optical rotation of molecules.}, url = {HAL :=http://hal.archives-ouvertes.fr/hal-00864278,PDF := http://hal.archives-ouvertes.fr/hal-00864278/PDF/article.pdf}, } @InProceedings{jaume-2013, author = {Jaume Gibert and Ernest Valveny and Horst Bunke and Luc Brun}, title = {Graph Clustering Through Attribute Statistics Based Embedding}, booktitle = {Computer Analysis Images and Patterns 2013}, year = 2013, month = {August}, address = {York}, editor = {R. Wilson and E. Hancock and A. Bors and W. Smith}, pages= {302-309}, volume = {lncs 8047}, theme= "pattern", url = {Pdf := https://brunl01.users.greyc.fr/ARTICLES/CAIP2013-Embedding.pdf} } @InProceedings{mahboubi-2013b, author = {Amal MAHBOUBI and Luc BRUN and Donatello CONTE and Pasquale FOGGIA and Mario VENTO}, title = {Re-identification de Personnes par Modele de Noyaux de Graphe}, booktitle = {GRETSI 2013}, year = 2013, month = {September}, address = {Brest}, theme = "pattern" } @InProceedings{amal-2013, author = {Amal Mahboubi and Luc Brun and Donatello Conte and Pasquale Foggia and Mario Vento}, title = {Tracking System with Re-identification Using a Graph Kernels Approach}, booktitle = {Computer Analysis Images and Patterns 2013}, year = 2013, month = {August}, address = {York}, editor = {R. Wilson and E. Hancock and A. Bors and W. Smith}, pages= {401-408}, volume = {lncs 8047}, theme= "pattern", abstract= "This paper addresses people re-identification problem for visual surveillance applications. Our approach is based on a rich description of each occurrence of a person thanks to a graph encoding of its salient points. The appearance of persons in a video is encoded by bags of graphs whose similarities are encoded by a graph kernel. Such similarities combined with a tracking system allow us to distinguish a new person from a re-entering one into the video. The efficiency of our method is demonstrated through experiments.", url = {Pdf := https://brunl01.users.greyc.fr/ARTICLES/caip_amal_2013.pdf} } @inproceedings{CI-conte-2013, author = {Donatello Conte and Jean-Yves Ramel and Nicolas Sidere and Luqman, Muhammad Muzzamil and Benoit Ga{\"u}z{\`e}re and Jaume Gibert and Luc Brun and Mario Vento}, title = {A Comparison of Explicit and Implicit Graph Embedding Methods for Pattern Recognition}, booktitle = {Graph-Based Representations in Pattern Recognition - 9th IAPR-TC-15 International Workshop}, year = {2013}, pages = {81-90}, ee = {http://dx.doi.org/10.1007/978-3-642-38221-5_9}, theme = "pattern", url = {Abstract and Pdf := http://hal.archives-ouvertes.fr/hal-00829226} } @Article{RN-Gauzere-2012, author = {Benoit Gaüzère and Luc Brun and Didier Villemin}, title = {Noyau de Treelets appliqu\'e aux graphes \'etiquet\'es et aux graphes de cycles}, journal = {Revue d'Intelligence Artificielle}, year = 2013, volume = 27, number = 1, pages = {121-144}, abstract= "La ch\'emoinformatique utilise des m\'ethodes issues de l’informatique, plus particulièrement la th\'eorie des graphes et l’apprentissage automatique, afin de classifier ou pr\'edire les propri\'et\'es de bases de mol\'ecules. Dans ce contexte, les noyaux sur graphes fournissent une approche int\'eressante en combinant les m\'ethodes d’apprentissage automatique et la repr\'esentation naturelle des mol\'ecules par graphes. Parmi les m\'ethodes bas\'ees sur les noyaux sur graphes, la d\'ecomposition du graphe en sous-structures repr\'esente une importante famille de noyau. Dans cet article, nous pr\'esentons deux extensions d’un noyau pr\'ec\'edemment bas\'e sur les sous-structures non \'etiquet\'ees à l’\'enum\'eration de sous structures \'etiquet\'ees et à la prise en compte de l’information cyclique des mol\'ecules. Nous proposons \'egalement des m\'ethodes de s\'election de variables permettant de pond\'erer un ensemble de sous-structures afin d’am\'eliorer la pr\'ecision de la pr\'ediction.", theme="pattern,chemo", url={RIA Online := http://ria.revuesonline.com/article.jsp?articleId=18201,HAL:=http://hal.archives-ouvertes.fr/hal-00847279} } @inproceedings{CI-gauzere-2013-2, hal_id = {hal-00829227}, title = {{Relevant Cycle Hypergraph Representation for Molecules}}, author = {Ga{\"u}z{\`e}re, Benoit and Brun, Luc and Villemin, Didier}, abstract = {Chemoinformatics aims to predict molecule's properties through informational methods. Some methods base their prediction model on the comparison of molecular graphs. Considering such a molecular representation, graph kernels provide a nice framework which allows to combine machine learning techniques with graph theory. Despite the fact that molecular graph encodes all structural information of a molecule, it does not explicitly encode cyclic information. In this paper, we propose a new molecular representation based on a hypergraph which explicitly encodes both cyclic and acyclic information into one molecular representation called relevant cycle hypergraph. In addition, we propose a similarity measure in order to compare relevant cycle hypergraphs and use this molecular representation in a chemoinformatics prediction problem.}, language = {Anglais}, affiliation = {Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen - GREYC , Laboratoire de chimie mol{\'e}culaire et thioorganique - LCMT}, booktitle = {Graph-Based Representations in Pattern Recognition}, pages = {111}, address = {Autriche}, audience = {internationale }, year = {2013}, month = May, url = {Abstract:= http://hal.archives-ouvertes.fr/hal-00829227,pdf:=http://hal.archives-ouvertes.fr/hal-00829227/PDF/GbR2013\_014.pdf}, theme="pattern", } @inproceedings{CI-grenier-2013, hal_id = {hal-00824172}, title = {{Treelet Kernel Incorporating Chiral Information}}, author = {Grenier, Pierre-Anthony and Brun, Luc and Villemin, Didier}, abstract = {{Molecules being often described using a graph representation, graph kernels provide an interesting framework which allows to combine machine learning and graph theory in order to predict molecule's properties. However, some of these properties are induced both by relationships between the atoms of a molecule and by constraints on the relative positioning of these atoms. Graph kernels based solely on the graph representation of a molecule do not encode this relative positioning of atoms and are consequently unable to predict accurately some molecule's properties. This paper presents a new method which incorporates spatial constraints into the graph kernel framework in order to overcome this limitation.}}, keywords = {Graph kernel; Chemoinformatics; Chirality}, language = {Anglais}, affiliation = {Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen - GREYC , Laboratoire de chimie mol{\'e}culaire et thioorganique - LCMT}, booktitle = {{9th IAPR-TC15 International Workshop on Graph-based Representations in Pattern Recognition}}, address = {Vienne, Autriche}, audience = {internationale }, year = {2013}, month = May, url = {Abstact:=http://hal.archives-ouvertes.fr/hal-00824172,PDF:=http://hal.archives-ouvertes.fr/hal-00824172/PDF/article.pdf}, theme="pattern,chemo" } @Article{PRL2012, author = {Benoit Gaüzère and Luc Brun and Didier Villemin}, title = {Two new graphs kernels in chemoinformatics}, journal = {Pattern Recognition Letters}, year = 2012, issn = "0167-8655", doi = "10.1016/j.patrec.2012.03.020", url = "ScienceDirect:=http://www.sciencedirect.com/science/article/pii/S016786551200102X, HAL := http://hal.archives-ouvertes.fr/hal-00773283", keywords = "Chemoinformatics", keywords = "Graph kernel", keywords = "Machine learning", abstract = "Chemoinformatics is a well established research field concerned with the discovery of molecule’s properties through informational techniques. Computer science’s research fields mainly concerned by chemoinformatics are machine learning and graph theory. From this point of view, graph kernels provide a nice framework combining machine learning and graph theory techniques. Such kernels prove their efficiency on several chemoinformatics problems and this paper presents two new graph kernels applied to regression and classification problems. The first kernel is based on the notion of edit distance while the second is based on subtrees enumeration. The design of this last kernel is based on a variable selection step in order to obtain kernels defined on parsimonious sets of patterns. Performances of both kernels are investigated through experiments.", theme="pattern,chemo", volume=33, number=15, pages={2038-2047} } @inproceedings{sitis2012, title = {A clustering algorithm of trajectories for behaviour understanding based on string kernels}, author = {Luc Brun and Alessia Saggese and Mario Vento}, year = {2012}, date = {2012-11-28}, booktitle = {Proceedings of the Conference on Signal Image Technology & Internet Based Systems (SITIS)}, address={Sorrento, Italy}, pages = {267--274}, publisher = {IEEE}, keywords = {Video analysis and interpretation}, theme="pattern", url={Abstract and Pdf := http://hal.archives-ouvertes.fr/hal-00768648} } @InProceedings{CI-gauzere-2012, author = {Benoit Gaüzère and Luc Brun and Didier Villemin}, title = {Graph Kernels Based on Relevant Patterns and Cycle Information for Chemoinformatics}, booktitle = {Proceedings of ICPR 2012}, address = {Tsukuba, Japan}, year = 2012, month = {November}, organization = {IAPR}, publisher = {IEEE}, pages= {1775-1778}, theme="pattern,chemo", url ={Abstract and Pdf := http://hal.archives-ouvertes.fr/hal-00768652} } @InProceedings{CI-Bougleux-2012, author = {Sébastien Bougleux and Francois-Xavier Dup\'e and Luc Brun and Gaüzère Benoit and Myriam Mokhtari}, title = {Shape Similarity based on Combinatorial Maps and a Tree Pattern Kernel}, booktitle = {Proceedings of ICPR 2012}, address = {Tsukuba, Japan}, year = 2012, volume = 7626, month = {November}, organization = {IAPR}, publisher = {IEEE}, pages={1602-1605}, address={Tsukuba, Japan}, theme="pattern", url ={Abstract and Pdf := http://hal.archives-ouvertes.fr/hal-00768662} } @InProceedings{CI-gauzere-2012-2, author = {Benoit Gaüzère and Hasegawa Makoto and Luc Brun and Salvatore Tabbone}, title = {Implicit and Explicit Graph Embedding: Comparison of both Approaches on Chemoinformatics Applications.}, booktitle = {Proceedings of S+SSPR2012}, address={Miyajima-Itsukushima, Hiroshima, Japan}, year = 2012, editor = {A. Imiya et al.}, volume = 7626, series = {LNCS}, month = {November}, organization = {IAPR TC 2}, publisher = {Springer}, pages= {510-518}, theme="pattern", url = {Abstract and Pdf :=http://hal.archives-ouvertes.fr/hal-00768654} } @InProceedings{CI-Bougleux-2012b, author = {Sébastien Bougleux and Francois-Xavier Dup\'e and Luc Brun and Myriam Mokhtari}, title = {Shape Similarity based on a Treelet Kernel with Edition}, booktitle = {Proceedings of S+SSPR2012}, address={Miyajima-Itsukushima, Hiroshima, Japan}, year = 2012, editor = {A. Imiya et al.}, volume = 7626, pages= {199-207}, series = {LNCS}, month = {November}, organization = {IAPR TC 2}, publisher = {Springer}, theme="pattern", url ={Abstract and Pdf := http://hal.archives-ouvertes.fr/hal-00768661}, } @InProceedings{CI-gauzere-2012-3, author = {Benoit Gaüzère and Luc Brun and Didier Villemin}, title = {Graph Kernels: Crossing Information from Different Patterns using Graph Edit Distance}, booktitle = {Proceedings of S+SSPR2012}, address={Miyajima-Itsukushima, Hiroshima, Japan}, year = 2012, editor = {A. Imiya et al.}, volume = 7626, series = {LNCS}, pages= {42-50}, month = {November}, organization = {IAPR TC 2}, publisher = {Springer}, theme="pattern,chemo", url={Abstract and Pdf := http://hal.archives-ouvertes.fr/hal-00768658} } @InProceedings{CN-GAUZERE-2011a, author = {Benoit Gaüzère and Luc Brun and Didier Villemin}, title = {Deux nouveaux noyaux sur Graphes et leurs applications en chimioinformatique}, booktitle = {Apprentissage et Graphes pour les Syst\`emes complexes (AGS) 2011}, year = 2011, month = {May}, organization = {AFIA}, pages={28-39}, url = {Abstract and Pdf :=http://hal.archives-ouvertes.fr/hal-00596513}, theme="pattern,chemo" } @InProceedings{CN-GAUZERE-2012, author = {Benoit Gaüzère and Luc Brun and Didier Villemin}, title = {Noyau de Treelets Appliqu\'e aux Graphes \'Etiquet\'es}, booktitle = {Actes de RFIA 2012}, year = 2012, month = {Jan.}, organization = {AFRIF}, address = {Lyon, France}, note = {Actes en ligne accessibles sous HAL}, url = {paper (pdf):=http://hal.archives-ouvertes.fr/hal-00656519/PDF/rfia2012\_submission\_96.pdf}, abstract = "La ch\'emoinformatique utilise des m\'ethodes issues de l’informatique, plus particulièrement la th\'eorie des graphes et l’apprentissage automatique, afin de classifier ou pr\'edire les propri\'et\'es de bases de mol\'ecules. Dans ce contexte, les noyaux sur graphes fournissent une approche int\'eressante en combinant les m\'ethodes d’apprentissage automatique et la repr\'esentation naturelle des mol\'ecules par graphes. Plusieurs m\'ethodes bas\'ees sur les noyaux sur graphes ont \'et\'e propos\'ees pour r\'esoudre des problèmes en ch\'emoinformatique. La d\'ecomposition du graphe en sous structures repr\'esente une importante famille de noyau. Dans cet article, nous pr\'esentons une extension d’un noyau pr\'ec\'edemment bas\'e sur les sous structures non \'etiquet\'ees à l’\'enum\'eration de sous structures \'etiquet\'ees. Nous proposons \'egalement deux m\'ethodes it\'eratives permettant de s\'electionner un ensemble de sous structures afin d’am\'eliorer la pr\'ecision de la pr\'ediction. Le noyau a \'et\'e valid\'e sur deux jeux de donn\'ees impliquant des graphes \'etiquet\'es.", theme="pattern,chemo" } @inproceedings{CI-GAUZERE-2011, author = {Benoit Gaüzère and Luc {Brun} and Didier {Villemin}}, title = {Two new Graph Kernels and Applications to Chemoinformatics}, booktitle = {In 8th IAPR - TC-15 Workshop on Graph-based Representations in Pattern Recognition (GBR'11)}, publisher = {Springer}, editor = {Xiaoyi {Jiang} and Miquel {Ferrer} and Andrea {Torsello}}, series = {Lecture Notes in Computer Science}, volume = {6658}, pages = {112-122}, year = {2011}, month = {May}, url = {Abstract and Pdf :=http://hal.archives-ouvertes.fr/docs/00/59/65/06/PDF/article.pdf}, keywords = {Graph kernels}, theme={pattern,chemo} } @inproceedings{CI-BRUN-2011, author = {Luc {Brun} and Donatello Conte and Pasquale Foggia and Mario Vento}, title = {A graph kernel method for Re-identification}, booktitle = {In 8th International Conference on Image Analysis and Recognition (ICIAR'2011)}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, year = {2011}, month = {June}, pages={173-182}, volume={6753}, keywords = {Graph kernels,Video analysis}, theme={pattern}, url={HAL:= http://hal.archives-ouvertes.fr/hal-00770260, pdf:=http://hal.archives-ouvertes.fr/docs/00/77/02/60/PDF/ICIAR2011.pdf} } @inproceedings{CI-BRUN-2011, author = {Luc {Brun} and Donatello Conte and Pasquale Foggia and Mario Vento}, title = {People Re-identification by Graph Kernel Methods}, booktitle = {In 8th IAPR - TC-15 Workshop on Graph-based Representations in Pattern Recognition (GBR'11)}, publisher = {Springer}, editor = {Xiaoyi {Jiang} and Miquel {Ferrer} and Andrea {Torsello}}, series = {Lecture Notes in Computer Science}, volume = {6658}, pages = {285-294}, year = {2011}, month = {May}, url = {Abstract and Pdf :=http://hal.archives-ouvertes.fr/hal-00680229}, keywords = {Graph kernels}, theme={pattern} } @InProceedings{CI-BRUN-2010, author = {Luc Brun and Donatello Conte and Pasquale Foggia and Mario Vento and Didier Villemin}, title = {Symbolic Learning vs. Graph Kernels: An Experimental Comparison in a Chemical Application}, booktitle = {Proceedings of the First International Workshop on Querying Graph Structured Data}, year = 2010, address = {Novi Sad, Serbia}, month = {September}, publisher = {Springer}, theme={pattern}, url={paper(pdf) := https://brunl01.users.greyc.fr/ARTICLES/GraphQ2010BrunConte.pdf}, abstract = "In this paper we present a quantitative comparison between two approaches, Graph Kernels and Symbolic Learning, within a classification scheme. The experimental case-study is the predictive toxicology evaluation, that is the inference of the toxic characteristics of chemical compounds from their structure. The results demonstrate that both approaches are comparables in terms of accuracy, but present pros and cons that are discussed in the last part of the paper." } @InProceedings{ACTI-DUPE-2010, author = {Francois-Xavier Dup{\'e} and S{\'e}ebastien Bougleux and Luc Brun and Olivier Lezoray and Abder Elmoataz}, title = {Kernel Based Implicit Graph Regularization of Structured Objects}, booktitle = {Proc. of ICPR'2010}, year = 2010, month = {August}, organization = {IAPR}, theme = {shape,pattern}, url= {paper(pdf) :=https://brunl01.users.greyc.fr/ARTICLES/icpr2010Dupe.pdf}, abstract = "Weighted Graph regularization provides a rich framework which allow to regularize functions defined over the vertice of a weighted graph. Until now, such a framework has been only defined for real or multivalued functions hereby restricting the regularization framework to numerical objects. On the other hand, several kernels have been defined on structured objects such as strings or graphs. Using definite positive kernels, each original object is associated by the ``kernel trick'' to one element of an Hilbert space. This paper proposes to extend the weighted graph regularization framework to objects implicitly defined by their kernel hereby performing the regularization within the Hilbert space associated to the kernel. This work opens the door to the regularization of structured objects." } @InProceedings{CN-DUPE-2009, author = {Francois-Xavier Dup\'e and Luc Brun}, title = {Classification de formes avec un noyau sur graphes flexible et robuste au bruit}, booktitle = {Proceedings of RFIA'2010}, year = 2010, address = {Caen}, month = {January}, organization = {AFRIF}, theme={shape,pattern}, url={papier(pdf) := https://brunl01.users.greyc.fr/ARTICLES/RFIA2010DupeBrun.pdf}, abstract={La squelettisation par axe median \'etant une transformation homotopique, le squelette d'une forme 2D correspond à un graphe planaire dont les faces codent les trous et les sommets chaque jonction et extr\'emit\'e. Ce graphe n'est pas un graphe simple, car compos\'e de boucles internes et d'arêtes multiples a cause des trous. Dans le cadre de la comparaison de formes, celui-ci est souvent transform\'e en une structure plus simple comme un arbre ou un graphe simple, perdant de ce fait des informations importantes sur la forme. Dans ce papier, nous proposons un noyau sur graphes combinant un noyau sur sacs de chemins et un noyau sur faces. Les chemins sont d\'efinis à partir du graphe non simple et le noyau sur chemins est renforc\'e par un processus d'\'edition. Le noyau sur faces reflète l'importance des trous dans une forme, cette information pouvant être une caract\'eristique importante de la forme. Le noyau r\'esultant est un noyau d\'efini positif, comp\'etitif avec les noyaux propos\'es dans l'\'etat de l'art. } } @inproceedings{CI-ROSENBERGER-2008-1, author={Christophe Rosenberger and Luc Brun}, title={Similarity-Based Matching for Face Authentication}, booktitle={Proceedings of the International Conference on Pattern Recognition (ICPR'2008)}, year={2008}, address={Tampa, Florida, USA}, pages={0-0}, theme={pattern} } @InProceedings{CI-DUPE-2008-2, author = {Dup\'e, F.-X. and Brun, L.}, title = {Hierarchical Bag of Paths for Kernel Based Shape Classification}, booktitle = {Proceedings of S+SSPR 2008}, pages = {227-236} , year = {2008}, theme= {shape,pattern}, address = {Orlando}, abstract={Graph kernels methods are based on an implicit embedding of graphs within a vector space of large dimension. This implicit embedding allows to apply to graphs methods which where until recently solely reserved to numerical data. Within the shape classification framework, graphs are often produced by a skeletonization step which is sensitive to noise. We propose in this paper to integrate the robustness to structural noise by using a kernel based on a bag of path where each path is associated to a hierarchy encoding successive simplifications of the path. Several experiments prove the robustness and the flexibility of our approach compared to alternative shape classification methods.}, url={paper(pdf):=https://brunl01.users.greyc.fr/ARTICLES/sspr2008.pdf, arXiv:=https://arxiv.org/abs/0810.3579} } @Misc{BR-LEBOSSE-2006, author = {J\'erome Leboss\'e and Jean-Claude Pailles}, title = {D\'etermination d'identification de signal}, institution = {France T\'el\'ecom}, year = {2006}, theme= {fingerprint}, note= {Brevet 06 50403} } @InProceedings{CI-LEBOSSE-2007, author = {Jerome Leboss{\'e} and Luc Brun}, title = {Audio Fingerprint Identification by Approximate String Matching}, booktitle = {Proceedings of ISMIR 2007}, url = {pdf (see the conference site) := http://ismir2007.ismir.net/schedule.html}, theme= {fingerprint}, year = 2007, address = {Vienna (Austria)}, month = {September} } @InProceedings{CN-LEBOSSE-2006, author = {J\'erome Leboss\'e and Luc Brun and Pailles, Jean Claude}, title = {Fingerprint audio robuste pour la gestion de droits}, booktitle = {Actes de CORESA 2006}, year = 2006, address = {Caen}, month = {Novembre}, theme= {fingerprint}, abstract= "Le fingerprint audio permet d'identifier un document audio {\'e}ventuellement corrompu, {\`a} partir d'un court extrait. Ces m{\'e}thodes peuvent {\^e}tre utilis{\'e}es dans le cadre de la gestion des droits num{\'e}riques (DRM) dans le but d'associer les informations de gestion et de contr{\^o}le {\`a} chaque document. Dans cet article, nous proposons un nouveau mode de calcul de fingerprint audio qui combine une m{\'e}thode de segmentation avec un nouveau sch{\'e}ma de construction des codes d{\'e}finissants le fingerprint. La m{\'e}thode propos{\'e}e est robuste aux alt{\'e}rations du document audio telles la compression et la suppression de parties ou d{\'e}calages temporels.", url = {article(pdf):=https://brunl01.users.greyc.fr/ARTICLES/CORESA_16_05.pdf} } @InProceedings{CI-Lebosse-2007, author = {J\'erome Leboss\'e and Luc Brun and Pailles, Jean Claude}, title = {A Robust Audio Fingerprint's Based Identification Method}, booktitle = {Proceedings of IbPRIA'2007}, pages = {185-192}, year = 2007, editor = {Joan Marti and Benedi, Jose Miguel and Mendonca, Ana Maria and Serrat, Joan}, volume = {I}, number = 4477, address = {Girona}, month = {June}, publisher = {LNCS}, theme= {fingerprint}, abstract= "An audio fingerprint is a small digest of an audio file computed from its main perceptual properties. Like human fingerprints, audio fingerprints allow to identify an audio file among a set of candidates but does not allow to retrieve any other characteristics of the files. Applications of audio fingerprint include audio monitoring on broadcast chanels, filtering peer to peer networks, meta data restoration in large audio library and the protection of author's copyrights within a Digital Right Management(DRM) system. We propose in this paper a new fingerprint extraction algorithm based on a new audio segmentation method. A scoring function based on q-grams is used to determine if an input signal is a derivated version of a fingerprint stored in the database. A rule based on this scoring function allows to either recover the original input file or to decide that no fingerprint belonging to the database correspond to the signal. The proposed method is robust against compression and time shifting alterations of audio files.", url = {article(ps):=https://brunl01.users.greyc.fr/ARTICLES/ibpria2007.ps} } @InProceedings{CN-Lebosse-2007, author = {J\'erome Leboss\'e and Luc Brun and Pailles, Jean Claude}, title = {Identification de signaux audio par appariement de ch\^{\i}nes}, booktitle = {Proc. of GRETSI 2007}, year = {2007}, address = {Troyes, France}, month = {September}, theme= {fingerprint}, abstract= "Nous proposons une m{\'e}thode d'identification bas{\'e}e {\`a} la fois sur une d{\'e}coupe adaptative du signal et sur un traitement des erreurs de segmentation {\`a} l'aide d'une fonction de similarit{\'e} entre chaines.La fonction de similarit{\'e} que nous proposons permet {\`a} la fois d'identifier un fichier lorsqu'il est pr{\'e}sent et de tester sa pr{\'e}sence dans la base. ", url = {article(pdf):=https://brunl01.users.greyc.fr/ARTICLES/gretsi.pdf} } @PhdThesis{TH-Lebosse-2009, author = {Jerome Leboss\'e}, title = {M\'ethodes d'identification pour le controle de l'utilisation de documents audio}, school = {Universit\'e de Caen}, year = 2009, month = {May}, url ={manuscript(pdf):=https://brunl01.users.greyc.fr/ARTICLES/TheseJerome.pdf}, theme= {fingerprint}, abstract= "L'objectif de ces travaux de recherche est de proposer une m\'ethode fiable et robuste d'identification de documents audio et plus particulièrement musicaux. Les contraintes de cette m\'ethode sont nombreuses puisque nous d\'esirons une m\'ethode avec un fort pouvoir discriminant qui soit capable d'identifier un document audio parallèlement à sa lecture, qui requière de faibles capacit\'es de stockage et soit robuste vis à vis de certaines alt\'erations du signal. Nous avons donc conçu une m\'ethode d'identification de signaux audio bas\'ee sur l'extraction d'une empreinte. Cette empreinte permet de reconnaître un signal parmi un ensemble de signaux caract\'eris\'es par leurs empreintes. Pour cela, l'empreinte est calcul\'ee à partir de certaines propri\'et\'es du signal. L'originalit\'e de notre m\'ethode vient du fait que la plupart des m\'ethodes existantes se basent sur une analyse des fr\'equences. Or notre m\'ethode se base uniquement sur une analyse temporelle du signal et l'extraction de positions remarquables (onsets) à l'int\'erieur de celui-ci. Les mesures de similarit\'e que nous proposons utilisent les sp\'ecificit\'es de nos empreintes pour identifier de façon pr\'ecise des documents tout en conservant de faibles temps de calculs malgr\'e la taille et le nombre de nos empreintes. Ce m\'emoire d\'ecrira les deux \'etapes conduisant à l'identification d'un extrait audio inconnu, à savoir une première phase de calcul d'empreinte et une seconde de comparaison avec un ensemble d'empreintes pr\'ecalcul\'ees afin d'identifier l'extrait. L'efficacit\'e de chacune de ces \'etapes sera d\'emontr\'ee à travers diff\'erents essais et compar\'ee avec la r\'ef\'erence en matière d'empreintes audio. Nous conclurons sur l'int\'erêt de nos travaux et les perspectives ouvertes par ceux-ci." } @InProceedings{CI-Lebosse-2006, author = {J\'erome Leboss\'e and Luc Brun and Pailles, Jean Claude}, title = {A Robust Audio Fingerprint Extraction Algorithm}, booktitle = {Proceedings of SPPRA'2006}, pages = {185-192}, year = 2006, editor= {Robert Sablatnig and O. Scherze}, address = {Innsbruck(Austria)}, month = {February}, publisher = {ACTA Press}, theme= {fingerprint}, abstract= "An Audio fingerprint is a small digest of an audio file computed from its main perceptual properties. Like human fingerprints, Audio fingerprints allow to identify an audio file among a set of candidates but does not allow to retreive any other characteristics of the files. Applications of Audio fingerprint include audio monitoring on broadcast chanels, filtering peer to peer networks, meta data restoration in large audio library and the protection of author's copyrights within a Digital Right Management(DRM) system. We propose in this paper a new fingerprint extraction algorithm which combines a segmentation method with a new fingerprint construction scheme. The proposed method is robust against compression and time shifting alterations of the audio files.", url ={article(ps):=https://brunl01.users.greyc.fr/ARTICLES/sppra2006.ps} } @INPROCEEDINGS{CI-Dupe2009a, author = {Dup\'e, F. -X. and Brun, L.}, title = {Edition within a graph kernel framework for shape recognition}, booktitle = {Graph Based Representation in Pattern Recognition 2009}, year = {2009}, theme={shape,pattern}, pages = {11-21}, url={paper(pdf):=https://brunl01.users.greyc.fr/ARTICLES/gbr2009_dupe.pdf}, abstract={ The medial axis being an homotopic transformation, the skeleton of a 2D shape corresponds to a planar graph having one face for each hole of the shape and one node for each junction or extremity of the branches. This graph is non simple since it can be composed of loops and multiple-edges. Within the shape comparison framework, such a graph is usually transformed into a simpler structure such as a tree or a simple graph hereby loosing major information about the shape. In this paper, we propose a graph kernel combining a kernel between bags of trails and a kernel between faces. The trails are defined within the original complex graph and the kernel between trails is enforced by an edition process. The kernel between bags of faces allows to put an emphasis on the holes of the shapes and hence on their genre. The resulting graph kernel is positive semi-definite on the graph domain.} } @INPROCEEDINGS{CI-Dupe2009b, author = {Dup\'e, F. -X. and Brun, L.}, title = {Tree covering within a graph kernel framework for shape classification.}, booktitle = {ICIAP 2009}, year = {2009}, theme={shape,pattern}, series = {Lecture Notes in Computer Science}, volume = 5716, publisher = {Springer}, editor = {Pasquale Foggia and Carlo Sansone and Mario Vento}, pages = {278-287}, url ={paper(pdf):=https://brunl01.users.greyc.fr/ARTICLES/ICIAP2009DupeBrun.pdf}, abstract={ The medial axis being an homotopic transformation, the skeleton of a 2D shape corresponds to a planar graph having one face for each hole of the shape and one node for each junction or extremity of the branches. This graph is non simple since it can be composed of loops and multiple-edges. Within the shape comparison framework, such a graph is usually transformed into a simpler structure such as a tree or a simple graph hereby loosing major information about the shape. In this paper, we propose a graph kernel combining a kernel between bags of trails and a kernel between faces. The trails are defined within the original complex graph and the kernel between trails is enforced by an edition process. The kernel between bags of faces allows to put an emphasis on the holes of the shapes and hence on their genre. The resulting graph kernel is positive semi-definite on the graph domain.} } @InProceedings{CI-Dupe2009c, author = {Dup\'e, F. -X. and Brun, L.}, title = {Shape classification using a flexible graph kernel}, booktitle = {Proceedings of CAIP 2009}, year = 2009, editor = {Xiaoyi Jiang}, month = {September}, publisher = {LNCS}, theme={shape,pattern}, url={paper(pdf):=https://brunl01.users.greyc.fr/ARTICLES/caip2009.pdf}, abstract = {The medial axis being an homotopic transformation, the skeleton of a 2D shape corresponds to a planar graph having one face for each hole of the shape and o ne node for each junction or extremity of the branches. This graph is non simple since it can be composed of loops and multiple-edges. Within the shape comparison framework, s uch a graph is usually transformed into a simpler structure such as a tree or a simp le graph hereby loosing major information about the shape. In this paper, we propose a graph kernel combining a kernel between bags of trails and a kernel between faces. T he trails are defined within the original complex graph and the kernel between trails is enforced by an edition process. The kernel between bags of faces allows to put an empha sis on the holes of the shapes and hence on their genre. The resulting graph kernel is po sitive semi-definite on the graph domain.} } @inproceedings{CI-stanovic-2022, TITLE = {{Maximal Independent Vertex Set applied to Graph Pooling}}, AUTHOR = {Stanovic, Stevan and Ga{\"u}z{\`e}re, Benoit and Brun, Luc}, BOOKTITLE = {{Structural and Syntactic Pattern Recognition (SSPR)}}, ADDRESS = {Montr{\'e}al, Canada}, YEAR = {2022}, MONTH = Aug, KEYWORDS = {Graph Neural Networks ; Graph Pooling ; Graph Classification ; Maximal Independant Vertex Set ; Graph Neural Networks}, url= {HAL:=https://hal.archives-ouvertes.fr/hal-03739114, pdf:= https://hal.archives-ouvertes.fr/hal-03739114/file/main.pdf, ArXiv:=https://arxiv.org/abs/2208.01648}, theme="pattern", 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.} }