Computing Optimal Assignments in Linear Time for Approximate Graph Matching

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Standard

Computing Optimal Assignments in Linear Time for Approximate Graph Matching. / Kriege, Nils; Giscard, Pierre-Louis; Bause, Franka; Wilson, Richard Charles.

International Conference on Data Mining. IEEE Computer Society, 2019.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Harvard

Kriege, N, Giscard, P-L, Bause, F & Wilson, RC 2019, Computing Optimal Assignments in Linear Time for Approximate Graph Matching. in International Conference on Data Mining. IEEE Computer Society.

APA

Kriege, N., Giscard, P-L., Bause, F., & Wilson, R. C. (Accepted/In press). Computing Optimal Assignments in Linear Time for Approximate Graph Matching. In International Conference on Data Mining IEEE Computer Society.

Vancouver

Kriege N, Giscard P-L, Bause F, Wilson RC. Computing Optimal Assignments in Linear Time for Approximate Graph Matching. In International Conference on Data Mining. IEEE Computer Society. 2019

Author

Kriege, Nils ; Giscard, Pierre-Louis ; Bause, Franka ; Wilson, Richard Charles. / Computing Optimal Assignments in Linear Time for Approximate Graph Matching. International Conference on Data Mining. IEEE Computer Society, 2019.

Bibtex - Download

@inproceedings{629a92ee72f940d48eadc375608d1121,
title = "Computing Optimal Assignments in Linear Time for Approximate Graph Matching",
abstract = "Finding an optimal assignment between two sets ofobjects is a fundamental problem arising in many applications,including the matching of {\textquoteleft}bag-of-words{\textquoteright} representations innatural language processing and computer vision. Solving theassignment problem typically requires cubic time and its pairwisecomputation is expensive on large datasets. In this paper, wedevelop an algorithm which can find an optimal assignment inlinear time when the cost function between objects is representedby a tree distance. We employ the method to approximate the editdistance between two graphs by matching their vertices in lineartime. To this end, we propose two tree distances, the first of whichreflects discrete and structural differences between vertices, andthe second of which can be used to compare continuous labels.We verify the effectiveness and efficiency of our methods usingsynthetic and real-world datasets.",
author = "Nils Kriege and Pierre-Louis Giscard and Franka Bause and Wilson, {Richard Charles}",
year = "2019",
month = sep,
day = "6",
language = "English",
booktitle = "International Conference on Data Mining",
publisher = "IEEE Computer Society",
address = "United States",

}

RIS (suitable for import to EndNote) - Download

TY - GEN

T1 - Computing Optimal Assignments in Linear Time for Approximate Graph Matching

AU - Kriege, Nils

AU - Giscard, Pierre-Louis

AU - Bause, Franka

AU - Wilson, Richard Charles

PY - 2019/9/6

Y1 - 2019/9/6

N2 - Finding an optimal assignment between two sets ofobjects is a fundamental problem arising in many applications,including the matching of ‘bag-of-words’ representations innatural language processing and computer vision. Solving theassignment problem typically requires cubic time and its pairwisecomputation is expensive on large datasets. In this paper, wedevelop an algorithm which can find an optimal assignment inlinear time when the cost function between objects is representedby a tree distance. We employ the method to approximate the editdistance between two graphs by matching their vertices in lineartime. To this end, we propose two tree distances, the first of whichreflects discrete and structural differences between vertices, andthe second of which can be used to compare continuous labels.We verify the effectiveness and efficiency of our methods usingsynthetic and real-world datasets.

AB - Finding an optimal assignment between two sets ofobjects is a fundamental problem arising in many applications,including the matching of ‘bag-of-words’ representations innatural language processing and computer vision. Solving theassignment problem typically requires cubic time and its pairwisecomputation is expensive on large datasets. In this paper, wedevelop an algorithm which can find an optimal assignment inlinear time when the cost function between objects is representedby a tree distance. We employ the method to approximate the editdistance between two graphs by matching their vertices in lineartime. To this end, we propose two tree distances, the first of whichreflects discrete and structural differences between vertices, andthe second of which can be used to compare continuous labels.We verify the effectiveness and efficiency of our methods usingsynthetic and real-world datasets.

M3 - Conference contribution

BT - International Conference on Data Mining

PB - IEEE Computer Society

ER -