Comparing large graphs efficiently by margins of feature vectors

M. Dehmer, Frank Emmert-Streib

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)


Measuring the structural similarity of graphs is a challenging and outstanding problem. Most of the classical approaches of the so-called exact graph matching methods are based on graph or subgraph isomorphic relations of the underlying graphs. In contrast to these methods in this paper we introduce a novel approach to measure the structural similarity of directed and undirected graphs that is mainly based on margins of feature vectors representing graphs. We introduce novel graph similarity and dissimilarity measures, provide some properties and analyze their algorithmic complexity. We find that the computational complexity of our measures is polynomial in the graph size and, hence, significantly better than classical methods from, e.g. exact graph matching which are NP-complete. Numerically, we provide some examples of our measure and compare the results with the well-known graph edit distance. (c) 2006 Elsevier Inc. All rights reserved.
Original languageEnglish
Pages (from-to)1699-1710
Number of pages12
JournalApplied Mathematics and Computation
Issue number2
Publication statusPublished - 15 May 2007

ASJC Scopus subject areas

  • Applied Mathematics
  • Computational Mathematics
  • Numerical Analysis

Fingerprint Dive into the research topics of 'Comparing large graphs efficiently by margins of feature vectors'. Together they form a unique fingerprint.

Cite this