Rule-Based Graph Reduction

[samuelsonric]

There are some well-known "rules" for reducing a graph prior to using an exact treewidth solver. I implemented the ones in this paper.

julia> using CliqueTrees, TreeWidthSolver

julia> graph = [
           0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0
           0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
           1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
           1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
           1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0
           0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0
           0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0
           0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
           0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0
           0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1
           0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
           0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1
           0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0
           0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0
           1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1
           0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0
           0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0
       ];

julia> @time treewidth(graph; alg=BT()) # solve using TreeWidthSolver.jl
  0.000498 seconds (7.11 k allocations: 543.391 KiB)
3

julia> @time treewidth(graph; alg=RuleReduction(BT())) # reduce graph, then solve using TreeWidthSolver.jl
  0.000059 seconds (200 allocations: 18.375 KiB)
3

I ran both versions on your benchmark suite. The red points are with rules, the blue points are without.

I thought you might find this interesting!

[samuelsonric]

I also implemented ComponentReduction, so we can run your algorithm on disconnected graphs.

[GiggleLiu]

Wow, this is a remarkable performance improvement. 🚀

[GiggleLiu]

I am wondering if this reduction can be used for weighted, hyper graphs? @samuelsonric

Since we use TreeWidthSolver to find the optimal contraction order of tensor networks: https://github.com/TensorBFS/OMEinsumContractionOrders.jl , weights (log-dimension size) and hyperedges (high order tensors) are essential.

We had a discussion for using CliqueTrees as a backend, but have no clue how to add the weighted and hyperedge support.

Note: the hyperedge requirement is optional, because they can be converted to regular graphs with some polynomial overhead. But the weights are essential.

[samuelsonric]

Hello @GiggleLiu! These rules can be adapted to solve the weighted treewidth problem.

I have been thinking about weighted graphs as well. I could add three argument constructors for algorithms that support weights.

permutation(graph, weights; alg)
cliquetree(graph, weights; alg)
treewidth(graph, weights; alg)

and so on. I would have to look into hypergraphs.

[GiggleLiu]

Nice! That will be a great contribution to the tensor network community.

[samuelsonric]

Why log2? Are there issues with blowup?

[GiggleLiu]

Why log2? Are there issues with blowup?

No need to worry about log2, it only happens in the stage of problem conversion.
Imaging you have a tensor of size (100, 1000, 10000), the total storage is 100 x 1000 x 10000. In graph theory, we prefer to add up the weights. Then, converting the size to (log2(100), log2(1000), log2(10000)), the storage in log2 is an addition of weights. Then "minimizing the storage" becomes "minimizing the summation of weights".

[ArrogantGao]

Wow, many thanks. @GiggleLiu I think we do not need hyper graph solver since we are working on line graph, which are simple graphs. And as I know, the BT algorithm also do not support hyper graph.

Additionaly, @samuelsonric is that easy to mapped the decompostion tree of the reduced graph back to the original graph?

[samuelsonric]

@ArrogantGao Yes: we are just pre-eliminating some vertices. The function rulereduce(graph) returns a triple (stack, label, kernel), where

• kernel is the reduced graph (nv(kernel) <= nv(graph))
• stack is a vector of length nv(graph) - nv(kernel) containing eliminated vertices.
• label is a vector of length nv(kernel) mapping the vertices of kernel to vertices of graph.

We build a full elimination ordering by constructing an elimination ordering of kernel and then appending it to the stack. This happens here. Does this answer your question?

[ArrogantGao]

Cool! Thank you very much for the answer. It should be very useful in our use case.

[samuelsonric]

Implemented some of the weighted rules (not published yet). I ran the benchmarks with random weights between 1 and 11. For d3 you are seeing a 30% reduction on average.

These rules seem to struggle a bit more.

[samuelsonric]

Ok, I pushed it. It looks like the more repeated weights you have, the better the rules do. Here is the api.

julia> using CliqueTrees, Graphs, TreeWidthSolver

julia> graph = Graph([
          0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0
          0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
          1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
          1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
          1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0
          0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0
          0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0
          0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
          0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0
          0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1
          0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
          0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1
          0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0
          0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0
          1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1
          0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0
          0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0
      ])
{17, 22} undirected simple Int64 graph

julia> w = log2.(rand(2:3, 17));

julia> @time exact_treewidth(graph; weights=w)
  0.000609 seconds (6.52 k allocations: 508.141 KiB) # solve using TreeWidthSolver.jl
4.169925001442312

julia> @time treewidth(w, graph; alg=BT())
  0.000638 seconds (7.12 k allocations: 532.750 KiB) # solve using TreeWidthSolver.jl
5.169925001442312

julia> @time treewidth(w, graph; alg=RuleReduction(BT())) # reduce graph, then solve using TreeWidthSolver.jl
  0.000074 seconds (271 allocations: 18.984 KiB)
5.169925001442312

CliqueTrees.treewidth does not subtract 1 from weighted treewidth.

[ArrogantGao]

Many thanks!

[samuelsonric]

reran with only three weights per graph (weights = log2.(rand(2:4, nv(graph))))