search

april-tools / cirkit

a python framework to build, learn and reason about probabilistic circuits and tensor networks
https://cirkit-docs.readthedocs.io/en/latest/
GNU General Public License v3.0
71 stars 1 forks source link

Generalize region graphs to support non-binary partitions #134

Closed loreloc closed 4 months ago

loreloc commented 11 months ago

Generalize region graphs such that partition nodes are not necessarily binary. Implementing this requires reviewing the file format, as we assumed only "left" and right" regions until now.

Why is this useful? To support sparse region graphs such as those derived from the Chow-Liu algorithm.

lkct commented 11 months ago

Why is this useful: 2. Omni-compatible circuits cannot be represented in the current RG structure, which is useful in circuit multiplication.

arranger1044 commented 11 months ago

You can always reshape an omni-compatible circuit to have any region graph.

lkct commented 11 months ago

You can always reshape an omni-compatible circuit to have any region graph.

Then I can only have an omni-compatible circuit when I know the shape. I think the better solution is to directly construct an omni-compatible circuit and then put it into any functional transforms (e.g. in multiplication, it's reshaped based on the opposite side).

arranger1044 commented 11 months ago

That would be the ideal solution, but to start with your projects, just reshape it (you always know in advance the shape of the other circuit).

lkct commented 11 months ago

NOTE We already support multi-partition in RG data structure. https://github.com/april-tools/cirkit/blob/e013eefb63dbfaf149e6dfe92ab5162f0fc2fb89/cirkit/region_graph/rg_node.py#L60-L61

What's missing is the code making use of it.