# 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 )
- 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)