## Abstract

Graph association is the problem of merging many graphs that collectively describe a set of possibly repetitive entities and relationships into a single graph that contains unique entities and relationships. As a form of data association, graph association can be used to identify when two sensors are observing the same object so information from both sensors can be combined and analyzed in a meaningful and consistent way. Graph association between two graphs is related to the problem of graph matching, and between multiple graphs it is related to the common labeling of a graph set (also known as multiple graph matching) problem. This article contribution is to formulate graph association as a binary linear program and introduce a heuristic for solving multiple graph association using a Lagrangian relaxation approach to address issues with between-graph transitivity requirements. The algorithms are tested on a representative dataset. The developed model formulation was found to accurately solve the graph association problem. Furthermore, the Lagrangian heuristic was found to solve the developed model within 3% of optimal on many problem instances, and found better solutions to large problems than is possible by directly using CPLEX.

Original language | English (US) |
---|---|

Pages (from-to) | 251-268 |

Number of pages | 18 |

Journal | Naval Research Logistics |

Volume | 60 |

Issue number | 3 |

DOIs | |

State | Published - Apr 1 2013 |

Externally published | Yes |

## Keywords

- data association
- graph analytics
- graph association
- knowledge discovery

## ASJC Scopus subject areas

- Modeling and Simulation
- Ocean Engineering
- Management Science and Operations Research