Graph algorithms

This page is about graph algorithms as traditionally conceived in computer science and discrete math. Algorithms of a more statistical nature, such as graph embeddings and graph kernels, are described in the stats/ML section.

Graph matching

Graph matching is the problem of finding correspondences, exact or inexact, between graphs, or otherwise measuring the similarity between graphs.

Surveys

  • Conte et al, 2004: Thirty years of graph matching in pattern recognition (doi)
  • Gao et al, 2010: A survey of graph edit distance (doi)
  • Riesen, Jiang, Bunke, 2010: Exact and inexact graph matching: Methodology and applications (doi)
    • Readable overview of classical graph matching
    • Emphasizes the graph edit distance, Bunke’s main research interest
  • Yan et al, 2016: A short survey of recent advances in graph matching (doi)
    • Poorly written, but the large bibliography is helpful
    • Sec. 3.5.2 reviews spectral, SDP, and double-stochastic relaxations of combinatorial problems in graph matching (see below)
  • Emmert-Streib et al, 2016: Fifty years of graph matching, network alignment and network comparison (doi)

Convex relaxations

  • Schellewald & Schnörr, 2005: Probabilistic subgraph matching based on convex relaxation (doi)
    • SDP relaxation of a quadratic integer programming problem
  • Aflalo, Bronstein, Kimmel, 2015: On convex relaxation of graph isomorphism (doi)
  • Lyzinski et al, 2016: Graph matching: Relax at your own risk (doi, arxiv)

Miscellaneous papers

  • Bomze et al, 1999: The maximum clique problem (doi)
    • Sequel to Pardalos & Xue, 1994: The maximum clique problem (doi)
    • Sec. 7.4 explains connections to matching graphs and “relational structures,” particularly how the maximum subgraph problem can be reduced to maximum clique via the association graph (a subgraph of the product graph)

Graph rewriting

Graph rewriting , also known as graph transformation and graph grammars, has generated a surprisingly large literature in computer science.

Books and surveys

  • Marcolli’s lecture notes on graph grammars (2015 , 2019 )
    • From a course on mathematical and computational linguistics (2015 , 2019 )
    • Marcolli & Port: Graph grammars, insertion Lie algebras, and quantum field theory (doi, arxiv)
  • Rozenberg, 1997: Handbook of graph grammars and computing by graph transformation, Vol 1: Foundations (doi)
    • Covers all the major approaches to graph transformation
    • Ch 3 and 4: Introductions to DPO and SPO approaches
  • Heckel, 2006: Graph transformation in a nutshell (doi)
    • Simplified presentation of DPO method

Span rewriting

Two popular approaches, double pushout graph rewriting (DP0) and single pushout graph rewriting (SPO), have a category-theoretic flavor, being based on pushouts of spans. Span rewriting is not restricted to graphs but can be done in any adhesive category .

The single pushout approach often uses partial morphisms:

  • Löwe & Ehrig, 1990: Algebraic approach to graph transformation based on single pushout derivations (doi)
  • Kennaway, 1990: Graph rewriting in some categories of partial morphisms (doi)
    • Similar to, but independent of, (Löwe & Ehrig, 1990)
  • Löwe, 1993: Algebraic approach to single-pushout graph transformation (doi)
    • As noted in footnote 7, the “basic ideas” appear already in (Löwe & Ehrig, 1990)