Graph matching is an important component in many object recognition algorithms. Although most graph matching algorithms seek a one-to-one correspondence between nodes, it is often the case that a more meaningful correspondence exists between a cluster of nodes in one graph and a cluster of nodes in the other. We present a matching algorithm that establishes many-to-many correspondences between nodes of noisy, vertex-labeled weighted graphs. The algorithm is based on recent developments in efficient low-distortion metric embedding of graphs into normed vector spaces. By embedding weighted graphs into normed vector spaces, we reduce the problem of many-to-many graph matching to that of computing a distribution-based distance measure between graph embeddings. We use a specific measure, the earth mover's distance, to compute distances between sets of weighted vectors. Empirical evaluation of the algorithm on an extensive set of recognition trials demonstrates both the robustness and efficiency of the overall approach.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Many-to-many graph matching via metric embedding


    Contributors:


    Publication date :

    2003-01-01


    Size :

    564880 byte





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Many-to-Many Graph Matching via Metric Embedding

    Keselman, Y. / Shokoufandeh, A. / Demirci, M. et al. | British Library Conference Proceedings | 2003


    Object Recognition as Many-to-Many Feature Matching

    Demirci, M. F. / Shokoufandeh, A. / Keselman, Y. et al. | British Library Online Contents | 2006


    Efficient many-to-many feature matching under the l1 norm

    Demirci, M. F. / Osmanlioglu, Y. / Shokoufandeh, A. et al. | British Library Online Contents | 2011


    A generative model for graph matching and embedding

    Xiao, B. / Hancock, E. R. / Wilson, R. C. | British Library Online Contents | 2009


    A dynamic graph-based many-to-one ride-matching approach for shared autonomous electric vehicles

    Wang, Ning / Lyu, Yelin / Jia, Shengling et al. | Springer Verlag | 2024