2019/01/29 by Nils M. Kriege, Pierre-Louis Giscard, Kriege, Nils M. +5 · 8 citations
Computer Science · Mathematics · #Advanced Graph Neural Networks #Algorithm #Artificial intelligence #Assignment problem #Combinatorics #Computation #Computer science #Data Management and Algorithms #Edit distance #FOS: Computer and information sciences #Graph #Graph Theory and Algorithms #Linear programming #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Matching (statistics) #Mathematical optimization #Mathematics #Pairwise comparison #Theoretical computer science #Time complexity #Tree (set theory) #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1901.10356
published in arXiv (Cornell University) (Cornell University) · IEEE ICDM 2019
openalex publication_date 2019/01/29 · arxiv created 2019/09/10 · arxiv updated 2019/09/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
Finding an optimal assignment between two sets of objects is a fundamental\nproblem arising in many applications, including the matching of `bag-of-words'\nrepresentations in natural language processing and computer vision. Solving the\nassignment problem typically requires cubic time and its pairwise computation\nis expensive on large datasets. In this paper, we develop an algorithm which\ncan find an optimal assignment in linear time when the cost function between\nobjects is represented by a tree distance. We employ the method to approximate\nthe edit distance between two graphs by matching their vertices in linear time.\nTo this end, we propose two tree distances, the first of which reflects\ndiscrete and structural differences between vertices, and the second of which\ncan be used to compare continuous labels. We verify the effectiveness and\nefficiency of our methods using synthetic and real-world datasets.\n