A fuzzy graph matching approach in intelligence analysis and maintenance of continuous situational awareness

Geoff Gross, Rakesh Nagi, Kedar Sambhoos

Research output: Contribution to journalArticlepeer-review


In intelligence analysis a situation of interest is commonly obscured by the more voluminous amount of unimportant data. This data can be broadly divided into two categories, hard or physical sensor data and soft or human observed data. Soft intelligence data is collected by humans through human interaction, or human intelligence (HUMINT). The value and difficulty in manual processing of these observations due to the volume of available data and cognitive limitations of intelligence analysts necessitate an information fusion approach toward their understanding. The data representation utilized in this work is an attributed graphical format. The uncertainties, size and complexity of the connections within this graph make accurate assessments difficult for the intelligence analyst. While this graphical form is easier to consider for an intelligence analyst than disconnected multi-source human and sensor reports, manual traversal for the purpose of obtaining situation awareness and accurately answering priority information requests (PIRs) is still infeasible. To overcome this difficulty an automated stochastic graph matching approach is developed. This approach consists of three main processes: uncertainty alignment, graph matching result initialization and graph matching result maintenance. Uncertainty alignment associates with raw incoming observations a bias adjusted uncertainty representation representing the true value containing spread of the observation. The graph matching initialization step provides template graph to data graph matches for a newly initialized situation of interest (template graph). Finally, the graph matching result maintenance algorithm continuously updates graph matching results as incoming observations augment the cumulative data graph. Throughout these processes the uncertainties present in the original observations and the template to data graph matches are preserved, ultimately providing an indication of the uncertainties present in the current situation assessment. In addition to providing the technical details of this approach, this paper also provides an extensive numerical testing section which indicates a significant performance improvement of the proposed algorithm over a leading commercial solver.

Original languageEnglish (US)
Pages (from-to)43-61
Number of pages19
JournalInformation Fusion
Issue number1
StatePublished - Jul 2014
Externally publishedYes


  • Fuzzy systems
  • Graph matching
  • Incremental graph matching
  • Situational awareness
  • Stochastic graphical methods

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Information Systems
  • Hardware and Architecture


Dive into the research topics of 'A fuzzy graph matching approach in intelligence analysis and maintenance of continuous situational awareness'. Together they form a unique fingerprint.

Cite this