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