Treewidth Algorithms

To efficiently contract a tensor network, it is essential to find an order to contract the tensors in (which we refer to as a contraction plan) which is computationally feasible. It was shown by Markov and Shi that a contraction plan for a network can be mapped to a tree decomposition of the network's line graph. The computational cost of the contraction plan is then exponential in the treewidth of that tree decomposition.

In this context, the treewidth of a tree decomposition of a networks line graph serves as an indirect measure of the size of the largest intermediate tensor produced while contracting the network according to the contraction plan that maps to the tree decompositon. As the cost of contracting a network is dominated by contractions involing the largest intermediate tensor, it is thus also an indirect measure of the computational cost of the contraction plan used.

The problem of finding a computationally feasible contraction plan for a tensor network can be solved by searching for tree decompositions, or equivalently vertex elimination orderings, that minimise the treewidth. QXGraphDecompositions provides functions for finding such tree decompositions and vertex elimination orders.

Tree Decompositions

An algorithm for finding tree decompositions with minimal treewidth was developed at KIT in the group of Prof. Dorothea Wagner is available here. QXGraphDecompositions uses the FlowCutterPACE17_jll wrapper package to provide the following function for computing such a tee decompostion of a graph.

QXGraphDecompositions.flow_cutter — Function

flow_cutter(G::lg.AbstractGraph, time::Integer=10; seed::Integer=-1)

Run the flow cutter algorithm for time seconds to find a tree decomposition for the graph G with minimal treewidth.

The tree decomposition is returned in a dictionary with the following key value pairs:

:treewidth => The treewidth of the tree decomposotion,
:num_bags => The number of bags in the tree decomposition,
:num_vertices The number of vertices in G,
:b_n => The n-th bag of the decomposition where n is an integer from 1 to the number of bags in the decomposition. A bag is an array of vertices of G.
:edges => An array of integer pairs indicating the edges of the tree decomposition.
:comments => An array of comments created by flow cutter regarding heuristics used and if it had enough time to find a decomposition.

The flow cutter algorithm and how it is used to find tree decompositions is described by Michael Hamann and Ben Strasser in the following papers:

Graph Bisection with Pareto Optimization - https://dl.acm.org/doi/10.1145/3173045 Computing Tree Decompositions with FlowCutter - https://arxiv.org/abs/1709.08949

Keywords

seed::Integer=-1: The seed used by flow cutter. Most be a non negative integer, otherwise the seed is set by flow cutter.

source

A vertex elimination order for a graph can be converted into a tree decomposition for the graph known as a clique tree. The following function implements the method outlined by Shutski et al here.

QXGraphDecompositions.build_clique_tree — Function

build_clique_tree(G, π̃)

Returns a tree decomposition for the graph G built from the given vertex elimination order π.

The algorithm used is by Schutski et al in Phys. Rev. A 102, 062614.

source

Vertex Elimination Orders

An equivalent strategy for finding contraction plans for tensor networks involves finding an order in which to eliminate the vertices in the network's line graph. Here, eliminating a vertex from a graph means connecting all of its neighbours together before removing it from the graph. Vertex elimination orders can be mapped to tree decompositions and have an equivalent notion of treewidth. The treewidth of a graph, with respect to a vertex elimination order, is the maximum number of neighbours a vertex has in the graph when it is eliminated according the order.

The min-fill heuristic is a popular heuristic for computing an upper bound on treewidth of a graph and an elimination order with the returned treewidth.

QXGraphDecompositions.min_fill — Function

min_fill(G::LabeledGraph)

Returns the upper bound on the tree width of G found using the min-fill heuristic. An elimination order with the returned treewidth is also returned.

source

The following function can be used to recover a vertex elimination order from a tree decomposition whose treewidth equals that of the tree decomposition. The provided tree decompositon is assumed to be contained in a dictionary similar to the one returned by the flow cutter algorithm.

QXGraphDecompositions.order_from_tree_decomposition — Function

order_from_tree_decomposition(td::Dict{Symbol, Any}; root::Symbol=:b_1)

Return a vertex elimination order with the same treewidth as the given tree decompositon.

The algorithm used to construct the vertex elimination order is described by Shutski et al in the following paper https://doi.org/10.1103/PhysRevA.102.062614

Keywords

root::Symbol=:b_1: The node of the tree to take as the root. Must be a symbol of the form :b_n where n is an integer between 1 and the number of bags in the tree decomposition.

source

Given an elimination order $\pi$ for a particualr graph $G$, the treewidth of $G$ with respect to the order $\pi$ can be computed using the following function.

QXGraphDecompositions.find_treewidth_from_order — Function

find_treewidth_from_order(G::LabeledGraph, π̄::Array{Symbol, 1})

Return the treewidth of G with respect to the elimination order π̄.

source

The following functions can be used to create an elimination order for a graph $G$ with a specified clique of $G$ appearing at the end of the order. This is useful for finding contraction plans for tensor networks containing open indices. The algorithm and application of these functions is described further by Shutski et al in this paper.

QXGraphDecompositions.restricted_mcs — Function

restricted_mcs(H::LabeledGraph, C::Array{Symbol, 1})

Return an elimination order for the chordal graph 'H' with the vertices in 'C' appearing at the end.

If the chordal graph H was created from an elimination order π for a graph G, the returned elimination order for H will have a treewidth equal to that of π if C is a clique in H.

The algorithm is described by Shutski et al in https://arxiv.org/abs/1911.12242

source

Treewidth deletion

The problem of finding a select number of vertices in a graph to delete, in order to reduce the treewidth of the graph, is known as the treewidth deletion problem. A method for solving this problem, implemented by the functions below, and it's application to tensor network slicing is discussed by Shutski et al here.

QXGraphDecompositions.greedy_treewidth_deletion — Function

greedy_treewidth_deletion(G::LabeledGraph, m::Int=4;
                          score_function::Symbol=:tree_trimming, 
                          elim_order::Array{Symbol, 1}=[])

Greedily remove vertices from G with respect to minimising the chosen score function. Return the reduced graph and an array of vertices which were removed.

The intermediate elimination orders and corresponding treewidths of the intermediate graphs are also returned if an elimination order for G is provided.

The algorithm is described by Schutski et al in Phys. Rev. A 102, 062614.

Keywords

score_function::Symbol=:tree_trimming: function to maximise when selecting vertices to remove. (:degree, :directtreewidth, :treetrimming)
elim_order::Array{Symbol, 1}=Symbol[]: The elimination order for G to be used by direct_treewidth score function.

source

QXGraphDecompositions.direct_treewidth_score — Function

direct_treewidth_score(G::LabeledGraph, π::Array{Symbol, 1})

Return an array of integers, one for each vertex in G, indicating the change in treewidth of G, with respect to π, if that vertex is removed.

source