The graph association problem: Mathematical models and a Lagrangian heuristic

Gregory Tauer, Rakesh Nagi, Moises Sudit

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)251-268
Number of pages18
JournalNaval Research Logistics
Issue number3
StatePublished - Apr 1 2013
Externally publishedYes


  • data association
  • graph analytics
  • graph association
  • knowledge discovery

ASJC Scopus subject areas

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


Dive into the research topics of 'The graph association problem: Mathematical models and a Lagrangian heuristic'. Together they form a unique fingerprint.

Cite this