How to generate a contraction path from an igraph dendrogram

[cotejer]

Hi Johnnie,

I'm trying to compare a tensor network contraction I've custom-built in igraph with a contraction using quimb and cotengra. I'm beginning with the igraph tensor network tn as the ground truth, and I'm contracting based on the following dendrogram:

dendrogram = tn.community_edge_betweenness()

Then, my plan was to feed the series of merges into cotengra using a snippet of code I found from your documentation (and defining a quimb tensor network quimbTN):

quimbTN = ... # Define tensor network
inputs, output, indexSizes = quimbTN.get_inputs_output_size_dict()
ssa_path = dendrogram.merges
tree = cotengra.core.ContractionTree.from_path(inputs, output, size_dict, ssa_path = ssa_path)

Then, my expectation is that ssa_path and tree.get_ssa_path() should be the same object, right? However, they do not coincide. Am I misunderstanding what these two objects are? Thanks!

[jcmgray]

I think probably its just that the ssa_path gets built into the binary tree which has many different ways to traverse it, each giving different ssa_paths (which is essentially a tree plus ordering of the merges). The default traversal is different to that initially supplied. I think you should be able to ensure the same ordering with tree.set_surface_order_from_path(ssa_path).

In general, for exact contraction, the cost is entirely decided by the tree, while the ordering (i.e. 'path') just has a minor effect on the total concurrent memory, as long as you choose it reasonably sensibly.

[cotejer]

Thanks for the explanation. Playing around with your suggestion, I think after I use tree.set_surface_order_from_path(ssa_path), I need to call tree.get_ssa_path_surface() (note the added "surface" at the end compared to what I had originally). Then, the two objects agree (up to sorting within each tuple).

Just to make sure I understand: Now if I contract my tensor network with the tree, it should give me the same ordering as the surface path I set, correct?

[jcmgray]

Ah to contract in exactly the same order, you might need tree.contract(arrays, order='surface_order') too.

In fact, you could also just use a ContractionTreeCompressed which both sets the surface order and uses it by default when traversing.

[cotejer]

If I can reference a discussion thread I had started (and you answered) over on the quimb repository, then I can just specify tree.traverse(order = "surface_order") and I should get the same thing.

Thanks for the help and mentioning the compressed versions of these classes. I'll make sure to look and see if I can make use of these!