Graph algorithms

This page is about graph algorithms as traditionally conceived in computer science and discrete math. Algorithmic methods of a 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.

  • 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
  • Marcolli & Port, 2015: Graph grammars, insertion Lie algebras, and quantum field theory (doi, arxiv)
    • Inspired by DPO approach but uses other ideas too
    • See also Marcolli’s lecture notes on graph grammars (2015 , 2019 ) from a course on mathematical and computational linguistics (2015 , 2019 )

Span rewriting

Two popular approaches to graph rewriting, double pushout graph rewriting (DP0) and single pushout graph rewriting (SPO), are category-theoretic, being based on pushouts and pushout complements. Span rewriting is not restricted to graphs but can be performed in any adhesive category , in particular in any topos.

  • Ehrig, 1979: Introduction to the algebraic theory of graph grammars (a survey) (doi)
    • Sec 3: DPO rules, pushout complements, and gluing conditions
    • Sec 4: Church-Rosser, parallelism, and concurrency theorems
  • Ehrig et al, 2006: Fundamentals of algebraic graph transformation (doi)
  • Heckel, 2006: Graph transformation in a nutshell (doi)
    • Simplified presentation of DPO method
  • Schneider, 2012, book draft: Graph transformations: An introduction to the categorical approach (pdf)

The SPO 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)

Reachability in graphs

Many algorithms have been developed for reachability problems in directed graphs, such as computing a transitive closure or its conceptual opposite, a transitive reduction . Reachability analysis in a simple digraph is the algorithmics of a preorder; reachability in a simple DAG is the algorithmics of a partial order.

Transitive closure

Transitive closures can be computing using simple algorithms based on breadth-first, depth-first, or bidirectional breadth-first search. Lots of effort has gone into dynamic algorithms for transitive closure.

  • Williams, 2016, lecture notes: Dynamic transitive closure (pdf)
    • Summarizes (King & Sagert, 1999) and (Demetrescu & Italiano, 2000)
  • Roditty + Zwick, 2016: A fully dynamic reachability algorithm for directed graphs with an almost linear update time (doi)
  • King & Sagert, 2002: A fully dynamic algorithm for maintaining the transitive closure (doi)
    • Conference version: STOC 1999 (doi)
  • Demetrescu & Italiano, 2005: Trade-offs for fully dynamic transitive closure on DAGs: breaking through the \(O(n^2)\) barrier (doi)
    • Conference version: FOCS 2000
  • Italiano, 1986: Amortized efficiency of a path retrieval data structure (doi)

However, recent empirical studies suggest that simple static algorithms for transitive closure may be faster even in dynamic settings:

  • Frigioni, Miller, Nanni, Zaroliagis, 2001: An experimental study of dynamic algorithms for transitive closure (doi)
    • “In conclusion, the fine-tuned version or the new variant of Italiano’s algorithms should be preferred in the case of not very sparse unstructured inputs in incremental environments. The same is true in the case of decremental and fully dynamic environments whose (not very sparse) unstructured input concerns a DAG. In all other cases, one should resort to the simple-minded approaches.”
  • Hanauer, Henzinger, Schulz, 2020: Faster fully dynamic transitive closure in practice (arxiv)