1. Optimal Transport vs Many-to-many assignment for Graph Matching
- Author
-
Grapa, Anca-Ioana, Blanc-Féraud, Laure, van Obberghen-Schilling, Ellen, Descombes, Xavier, Morphologie et Images (MORPHEME), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut de Biologie Valrose (IBV), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Signal, Images et Systèmes (Laboratoire I3S - SIS), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), Institut de Biologie Valrose (IBV), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), ANR-11-LABX-0028,SIGNALIFE,Réseau d'Innovation sur les Voies de Signalisation en Sciences de la Vie(2011), ANR-19-P3IA-0002,3IA@cote d'azur,3IA Côte d'Azur(2019), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Signal, Images et Systèmes (Laboratoire I3S - SIS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS), Grapa, Anca-Ioana, Centres d'excellences - Réseau d'Innovation sur les Voies de Signalisation en Sciences de la Vie - - SIGNALIFE2011 - ANR-11-LABX-0028 - LABX - VALID, and 3IA Côte d'Azur - - 3IA@cote d'azur2019 - ANR-19-P3IA-0002 - P3IA - VALID
- Subjects
[INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing ,[INFO.INFO-TS] Computer Science [cs]/Signal and Image Processing ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
National audience; Graph matching for shape comparison or network analysis is a challenging issue in machine learning and computer vision. Gener-ally, this problem is formulated as an assignment task, where we seek the optimal matching between the vertices that minimizes the differencebetween the graphs. We compare a standard approach to perform graph matching, to a slightly-adapted version of regularized optimal transport,initially conceived to obtain the Gromov-Wassersein distance between structured objects (e.g. graphs) with probability masses associated to thenodes. We adapt the latter formulation to undirected and unlabeled graphs of different dimensions, by adding dummy vertices to cast the probleminto an assignment framework. The experiments are performed on randomly generated graphs onto which different spatial transformations areapplied. The results are compared with respect to the matching cost and execution time, showcasing the different limitations and/or advantagesof using these techniques for the comparison of graph networks.
- Published
- 2019