# 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 Statistics/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 transformation

- Matilde Marcolli's lecture notes on graph grammars from her course on mathematical linguistics
- Rozenberg, 1997:
*Handbook of graph grammars and computing by graph transformation*- Covers all the major graph transformation approaches
- Ch 3: Decent introduction to algebraic (DPO) approach

- Heckel, 2006: Graph transformation in a nutshell [doi]
- Simplified presentation of DPO method