What is the Relationship between Tensor Factorizations and Circuits (and How Can We Exploit it)?
Authors: Lorenzo Loconte
Antonio Mari
Gennaro Gala
Robert Peharz
Cassio de Campos
Erik Quaeghebeur
Gennaro Vessio
Antonio Vergari
Venue: Accepted by TMLR ()

Abstract: This paper establishes a rigorous connection between circuit representations and tensor factorizations, two seemingly distinct yet fundamentally related areas. By connecting these fields, we highlight a series of opportunities that can benefit both communities. Our work generalizes popular tensor factorizations within the circuit language, and unifies various circuit learning algorithms under a single, generalized hierarchical factorization framework. Specifically, we introduce a modular “Lego block” approach to build tensorized circuit architectures. This, in turn, allows us to systematically construct and explore various circuit and tensor factorization models while maintaining tractability. This connection not only clarifies similarities and differences in existing models, but also enables the development of a comprehensive pipeline for building and optimizing new circuit/tensor factorization architectures. We show the effectiveness of our framework through extensive empirical evaluations, and highlight new research opportunities for tensor factorizations in probabilistic modeling.

Published in Transactions on Machine Learning Research (02/2025)
What is the Relationship between Tensor Factorizations and Circuits (and How Can We Exploit it)
Lorenzo Loconte
Lloconte Osmss ed.ac. uk
School of Informatics, Universily of Edinburyh, UK
Antonio Mari
intonio.aari@epa
École Polytechnique Fédérale de Lausanne (EPFL), Switzerland
Gennaro Gala
g-gola @tue. ml
Eindloven Universily of Technology, NL
Robert Peharz
robertppchar&&hggaz.d
Graz University of Technology, Austria
Cassio de Campos
c.decampos@tue.nl
Eindhoven Universily of Technology, NL
Erik Quaeghebeur
e.quaeghebeur@ttue.r
Eindhoven University of Technology, NL
Gennaro Vessio
gennaro. vessio www.wsswnsssssaa...... it
Compuler Science Departmend, Universily of Bari Aldo Moro, IT
Antonio Vergari
avergarited..cc. uk
School Informatics, University Edinburgh, UK
Reviewed on OpenReview: https: // openreview. net/ forum? Y7dRmpG4Hj
Code repository: https: //github. com/ www.ollssnnn-cii----
Abstract
This paper establishes a rigorous connection between circuit representations and tensor fac- torizations, two seemingly distinct yet fundamentally related areas. By connecting these fields, we highlight a series of opportunities that can benefit both communities. Our work generalizes popular tensor factorizations within the circuit language, and unifies various circuit. learning algorithms under single, generalized hierarchical factorization framework. Specifically, we introduce a modular "Lego block" approach to build tensorized circuit archi- tectures. This, in turn, allows us to systematically construct and explore various circuit and tensor factorization models while maintaining tractability. This connection not only clarifies similarities and differences existing models, but also enables the development of compre- hensive pipeline for building and optimizing new circuit/ dircui//tensor factorization architectures. We show the effectiveness of our framework through extensive empirical evaluations, and highlight new research opportunities for tensor factorizations in probabilistic modeling.
Shared first authorship.
Work partly done when visiting the University of Edinburgh.
The codebase this paper is based on ten-pes, an alder version currently maintained cirkit package.

---

Published in Transactions on Machine Learning Research (02/2025)
1 Introduction
This paper aims at bridging two apparently distant, but in fact intimately related fields: circuit representa- tions (Darwiche & Marquis, 2002; Choi et al., 2020; Vergari et al., 2021) and tensor factorizations (Kolda, 2006; Sidiropoulos el al., 2017). Specifically, we establish a formal connection wetween the two representa- tions and show how the latter can bring a unified perspective on the many learning algorithms devised to Iearn the former, as well as create research opportunities for both communitics.
Tensors are multidimensional generalizations of matrices that, are extensively used to represent high- dimensional data (Kroonenberg, 2007). Tensor factorizations are well-understood mathematical objects to compactly represent tensors in terms of simple operations acting on lower-dimensional tensors (Kolda, 2006). They have been extensively applied in ML and AI, e.g,, in computer vision (Vasilescu & Terzopoulos, 2002; Savas & Eldén, 2007; Panagakis et al., 2021), graph analysis (Kolda et al., 2005), computational neuroscience (Vos et al., 2007; Tresp et al., 2021), neuro-symbolic Al (Nickel et al., 2015; Balazevic et al., 2019; Gema et al., 2023; Loconte et al., 2023), language modeling (Ma et al., 2019; Hu et al., 2022; Xu et al., 2023), and as ways to encode probability distributions (Jaini et al., 2018b; Novikov et al., 2021; Amiridi et al., 2022; Hood & Schein, 2024). While usually defined in terms of shallow factorizations, tensor factorizations can be also expressed as a hierarchy of factorizations (Grasedyck, 2010), sometimes represented in the graphical formalism of tensor networks (Orús, 2013; Biamonte & Bergholm, 2017; Glasser et al., 2019).
Circuit representations (Darwiche & Marquis, 2002; Choi et al., 2020; Vergari et al., 2021), on the other hand, are structured computational graphs introdueed in the context of logical reasoning and probabilistic modeling (Darwiche, 2003; Poon & Domingos, 2011; Kisa et al., 2014). Probabilistic circuits (PCs) ( (Vergari et al., 2019b; Choi et al., 2020), in particular, are circuits that encode tractable probability distributions. They support a number of applications requiring exact and efficient inference routines, e.g., lossless com- pression (Liu et al., 2022), biomedical generative modeling (Dang et. al., 2022b), reliable neuro-symbolic Al (Ahmed et al., 2022: Loconte et al., 2023) and constrained text generation (Zhang et al., 2023). Many algorithms to learn PCs from data have been proposed in the past (sce c.g., Sidheekh & Natarajan (2024) for a review), with one paradigm emerging: building overparumelerized circuits, comprising millions or even bil- lions of parameters (Liu et al., 2023a; Gala et al., 2024a), and training these parameters by gradient-ascent, (Peharz et al., 2016; 2020c), or regularized variants (Dang et al., 2022a).
Both hierarchical tensor factorizations and PCs have been introduced as alternative representations of proba- bilistic graphical models (Song et al., 2013; Robeva & Seigal, 2017; Glasser et al., 2020; Bonnevic & Schmidt, 2021), and the connection between certain circuits and factorizations has been hinted in some works (Jaini et al., 2018b; Glasser et al., 2019). However, they mainly differ in how they are applied: tensor factorizations are usually used in tasks where a ground-truth tensor to approximate is available or a dimensionality reduc- tion problem can be formulated (aka tensor sketch), whereas PCs are usually Iearned from data in the same spirit generative models are trained. Similar to lensor factorizations, however, modern PC representations are overparameterized and usually encoded as collection of tensors as to leverage parallelism and modern deep learning frameworks (Vergari et al., 2019a; Peharz et al., 2020c; Mari et al., 2023). This bogs the ques- tion: is there any formal and systematic connection between circuits and tensor factorizations? Our answer is affirmative, we show that circust can be cast. as generalized sparse hicrarchical tensor factorization, where its parameters encode the lower-dimensional tensors of the factorization itself. Or alternatively, a hierarchical tensor factorization is a special case of a deep circuit with a particular tensorized architecture. When it comes to PCs, this implies decomposing probability distributions represented as non-negative ten- sors (Cichocki & Phan, 2009). At the same time, classical tensor factorizations can be exactly encoded as (shallow) circuits. By affirming the duality of tensor factorizations and circuits, we systematize previous results in the literature, open up new perspectives in representing and learning circuits, and suggest possible ways to construct new and extend existing (probabilistic) factorizations.
Specifically, in this paper we will first derive a compact way to denole several (ensorized circuit architectures, and represent them as computational graphs using a "Lego blocks " approach that stacks (locally) dense tensor factorizations while presorving the structural propertics of circuits required for tractability. This enables us to use novel "blocks" in a plug-and-play manner. Then, we unify the many different algorithms for learning PCs that have been proposed in the literature so far (Peharz et al., 2020c;a; Liu & Van den Broeck,
2

---

Published in Transactions on Machine Learning Research (02/2025)
2021b), which come from different perspectives and yield circuits that are considered different models. In particular, we show that their differences reduce to factorizations and syntactic transformations of their tensor parameters, since they can be understood under the same generalized (hierarchical) factorization based on the Tucker tensor factorization (Tucker, 1966) and its specializations (Kolda & Bador, 2009). Therefore, we argue the different performances that are often reported in the literature are actually the result. of different hyperparameters and learning methods more than different inductive biases (Liu et al., 2023b).
Furthermore, after making this connection, exploit tensor factorizations to further compress the param- eters of modern PC architectures already represented in tensor format. By doing so, we introduce PCs that are more parameter-effiiiet than previous ones, and we show that finding the best circuit architecture for a certain setting is far from solved. Lastly, we highlight how this connection with circuits can spawn interesting research opportunities for the tensor factorization community-highiightee as boxes throughout the paper-ranging from learning to decompose tensors from data, to interpreting tensor factorizations as latent-variable probabilistic models, to inducing sparsity via the specification of background knowledge.
Contributions. i) We generalize popular tensor factorization methods and their hierarchical formulation into the language of circuits (Section 2). ii) We connect PCs to non-negative tensor factorizations and highlight how the latter can be interpreted as latent variable models, and as such they can be used as generative models and for neuro-symbolic AI (Section 3). iii) Within our framework, we abstract away the many options used to build and learn modern overparameterrzee archilectures to arrive at a general algorithmic pipeline (Section 4) to represent and learn hierarchical tensor factorizations as tensorized circuits. iv) This allows us to analyze how existing, different parameterizations of circuits are related to each other by leveraging tensor factorizations, while proposing more paramcter-eficcint modeling choices that retain some of the expressiveness (Section 5). v) We evaluate several algorithmic choices in our framework on a wide range of distribution estimation tasks, highlighting the major trade-offs in terms of time and space complexity, and resulting performance (Section 6).
2 From Tensor Factorizations to Circuits
Symbols notation. We will adapt most of the notation and nomenclature from Kolda & Bader (2009). We denote sets of random variables with X, Y and Z, and we use [m] to express the set {1, .......,,,, n) with n > 0. The domain of a variable is denoted as dom(X), and we denoted as dom(X) = dom (1) x ..... x dom(Xn) the joint domain of variables X [X.) We denote scalars with lower-case letters (e.g., a I),, vectors with boldface lower-case letters (e.g., a E Rx), matrices with boldface upper-case letters (excluding those used for variables, c.g., A E MMxM), and tensors with boldface calligraphic letters (e.g., A e R(1x/xx1s). Moreover, we use subscripts to denote entries of tensors (e.g., Gijk is the (i, k)-th entry in A).
9." Matrix and tensor operations notation. We make use "f to denote tensor slicing (e-g., A.j: E R is obtained by selecting the j-th matrix slice of A along the second dimension). Furthermore, we denote with O the Hadamard (or element-wist product) of tensors having the same dimensions, and we denote with o the outer products of vectors, i.e., given u E RM v R.N we have that their outer product A u V E B is defined such that 0zj- = u,y, for all (i,5) E [M] x [M]. We denote with || the concatenation operator over vectors, i.e., u || v = [ur...., UM, U1,..., uN]
MMMN We use & to express the Kronecker product between vectors, i.c., @ v E MN the wow-wise flattening of o v into an Mdddmennsionall vector. Finally, we use Xn to denote the tensor-matrix dot product along the n-th dimension, i.e., given tensor T x and matrix A E Jx n E [d], then we have that T x, A E //xx xI. - is In defined in element-wise notation as (T Xn A)i ih 11 -i,-1 lip with j 1 [J].
2.1 Shallow Tensor Factorizations are Shallow Circuits
Tucker tensor factorization. Tensor factorizations approzimate high figh-dimensional tensors by a collection of lower-dimensional ones. Formally, given a tensor T E R whose size grows exponentially with respect to the dimensions d, we seek a low-rank factorization for it (Kroonenberg, 2007). Many popular tensor factorization methods, such as the cononical polyadic decomposition (CP) (Carroll & Chang, 1970).
3

---

Published in Transactions on Machine Learning Research (02/2025)
Xxa
fx1
3.4
13
-1.1
0.6
fx,
fx²
0.2
0.2
0.5
Jxa
A
Jxs
0.3
0.5
0.2
19
0.2
1.37
6.9
0.7
0.5
0.91
0.7
fx.
fxx
3.4
Figure 1: Example of a circuit (left) and its evaluation (right) for a circuit encoding the joint density over three continuous random variables X1.X2 X3. We denote input units with 2 as they are univariate Gaussian distributions and label them with their scopes (left) while later on we will draw generic input units with an empty circle. To compute the joint density for p(X1 X2 0.2, = 3.4), one has to first evaluate the Gaussian densities at the inputs (blue) and propagate the computed values. These densities are then multiplied across product units X and then passed through sums + (both in orange), whose parameters are here explicitly drawn in boxes. We will omit drawing the sum units weights in other pictures to avoid clutter. The value of p(X, = -.1, X2 = 0.2, X3 = 3.4) = 0.91 is obtained by collecting the output of the last unit (in purple). See Section for more circuits encoding distributions.
RESCAL (Nickel et al., 2011), and the higher-order singular value decomposition (HOSVD) (De Lathauwer et al., 2000) are all particular cases of the Tucker factorization (Tucker, 1964; 1966). For this reason, our treatment of tensor factorizations will focus on Tucker first, and its hierarchical formulation (Grasedyck, 2010) later. Our results will generalize to special cases such as CP, RESCAL and HOSVD.
Definition 1 (Tucker factorization (Tucker, 1964)). Let T E I be a d-dimensional tensor. The multilincar rank- R...... Ra) Tucker factorization of factorizes it as a core tensor multiplied by a matrix along each dimension, i.e,,
T x1 ( X2 ( ... x (d)
(1)
where W e R XR. is the core tensor, vt) E R with E [d] are the factor matrices, and & denotes the approximation of the tensor on the left-hand side given by the right-hand hand side factorization. The above equation can be rewritten element-wise notation as
R
Ra Wry Uar ..raa
ligonia
(1)
(d)
(2)
Focusing on the element-wise notation, we can view the factorization of T as a function c over d discrete variables X {X,)ş_1 each having domain dom(X,) = [T,], such that lx s c(x) for any assignment x= (iı,..., id) to variables X. In other words, each assignment X is mapped to one scalar tensor entry, whose value is computed by c. Eq. (2) highlights that such a tensor factorization encodes a polynomial defined over the factor matrix values associated to assignments to variables X (Kolda, 2006). Therefore, we can represent the factorization encoded in as circuit, i.e., a computational graph consisting of sums and products as atomic operators, formally defined next.
Definition (Circuit (Choi et al., 2020; Vergari et al., 2021)). A circuit c is a parameterized directed acyclic computational graph' over variables X encoding a function c(X), and comprising three kinds of computational units: inpul, product, and sum units. Each product or sum unit. receives the outputs of other units as inputs, denoted with the set in(n). Each unit n encodes function en defined as: (i) (s(((()) if n is an input unit, where fn is a function over variables sc(n) S X, called its scope, (ii) [[zein(n) (s((()) if is product unit, and (iii) E the weighted sum parameters. The scope of a product or sum unit is the union of the scopes of its inputs, i.e., sc(n) = Ujsin(n) sc(j). The size of circuit denoted as |c], is the number of edges between the computational units.
(sc((sc(j)) if is sum unit, with wy R denoting
In our figures, the direction of the circuit edges is always assumed be from input output units, but it not graphically shown avoid clutter.
4

---

Published in Transactions on Machine Learning Research (02/2025)
(3)
33
22,
Wiyk
V
W
333
O 21
22
VO)
O T22
Uxy1
Vayl
Uay2
(a)
(b)
Figure 2: Tucker tensor factorizations are circuits. Given a tensor T E R and its multilinear (2nk-(2,2,2) Tucker factorization T Xx v()) X2 v X3 v(3) (a), we can encode it as a circuit c whose evaluation corresponds to computing an entry of the decomposed tensor, i.e,, tz1z2a & c(I1, 22, x3) for any entry index (#1, 12, 23) (b). The diroctionality of the circuit connections goes from input units to output units, but it not shown to avoid clutter. The sum unit is parameterized by the entries Wijs of the core tensor W, while the input units are parameterized by the factor matrices v y(2), v For instance, evaluating the two input units depending on the index xı (b, in red) translates to indexing the æ æi-th row of ((1,, i.c., Var = [U (1) (1) T (a, in red).
2,2
Circuits can be understood as multilinear polynomials with exponentially many terms, but compactly en- coded a deep computational graph of polynomial size (Darwiche, 2003; Zhao al., 2016; Choi et al., 2020). From this perspective, is possible intuit how they are related to, but also different from, tensor factorizations. In fact, while also the latter encode compact multilinear operators (Eq. (2)), the indetermi- nates of the circuit polynomials can be more than just entries of matrices as per Def. 2, e.g., potentially non-linear input functions. For example, a circuit can encode the joint density over collection of continuous random variables, and input functions fa could encode Gaussian densities (Fig. 1). See also Opportunity 4 for discussion on the many ways to encode input units in circuits.
Evaluating the function encoded in a circuit is done by traversing its computational graph in the usual feedforward way inputs before outputs, Fig. 1. Furthermore, the circuit definition provided can be more general than tensor factorizations as it can represent sparse computational graphs, i.e., where units are irregularly connected. As we will argue later, this does not need to be the case. Circuits can be, in fact, designed to be locally-dense as it is common in many modern implementations (Section 4). Locally-dense architectures are also how tensor factorizations will look like, when turned into circuits, as we demonstrate in the following constructive proposition for general Tucker factorization (Def. 1).
Proposition 1 (Tucker as circuit). Let T B4 R.xxxx be tensor being decomposed via a multilinear rank- (Ri...., Rạ) Tucker factorization, as in Eq. (1). Then, there exists a circuit e over variables X = =[X,}²= with dom(X,) = [4g. j e [d] computing the same factorization. Moreover, we have that |c| Odd[l R2).
Appendix A.1 details our proof construction and Fig. 2 illustrates it for the Tucker factorization of three dimensional tensor. In nutshell, we build shallow circuit over the same variables that, when evaluated, outputs the reconstructed tensor entry for a set of coordinates, i.e., it encodes Eq. (2). Its input functions fn. fact, map variable states to embeddings, i.e., the real values contained in the matrices obtained from the Tucker factorization, see Fig. 1. Note that one can easily particularize our construction to obtain circuits corresponding to other factorizations such CP, RESCAL and HOSVD.
As concrete example of our construction, consider the following. Let T E R 3x333 be three-dimensional tensor defined as
-
1.68
4.02
-1.84
16.83
400.4
18.36
21.88
-52.31
23.87
T =
0.63
-1.50
0.68
- 66.27
14.99
6..8
-..5
19.49
-8.89
(3)
0.25
-0.59
0.27
-2.48
5.918
-2.7
-3.22
7.69,
-3.51
5

---

Published in Transactions on Machine Learning Research (02/2025)
and whose multilinear (2,,- Tucker decomposition is given by tensor W R2x2x2 whose entries are all 0.5 and by matrices
0.1
0.2
1.1
9.1
-2
0.9
v =
2.0
-1.0
v =
-3.3
-0.5
v(3) =
0.23
2.4
(4)
1.5
-5.4/
0.7
-2.
1.4
0.2
Then, we can build a circuit e with the same structure as the one in Fig. 2, equipping its input units with embeddings taken from v(1,, vr2) or v(9) depending on their scope, and by setting the sum unit parameters to be the vector we e R obtained by vectorizing the tensor W and therefore having values = (0.5.... 0.5). Now, to compute the approximate value of the 11,2, entry in T, we can evaluate the circuit in a feed-forward way evaluatigg inputs before outputs to compute c(1, 2,2).. 2). This would yield the following computation:
w ((0.1 0.2) 2 (-3.3 -0.5) @ (0.23 2.4)7) 11.4991.
(5)
Note how the color-coded blocks inside the brackets correspond to the outputs of the input functions the circuits (Fig. 2), and how the vector outer products (o) realize the produet units in e while the dot product with w is encoded in the final sum unit. We invite the reader to play with this example and try to recover other entries in the tensor, until they are comfortable with the translation of tensor factorization into our circuit format. Furthermore, since circuits can represent factorizations, they inherit the same non- uniqueness issue commonly arising in many lensor factorization methods (e.g. Tucker). That is, the tensor factorization encoded by a circuit is not unique: one can change the circuit parameters while still encoding the same function. Finally, we remark that the multilinear-rank of the factorization now translates into the number of the imput units in the circuit representation. Later, for hierarchical factorizations turned into deep circuits (Section 2.2) ranks will turn into the number of units located at different depths as well.
Representing tensor factorizations as compulational graphs of this kind will offer a nunber of opportunities for extending the former model class, in which case we will highlight them in boxes throughout the paper. At the same time, we can better understand why these factorizations already support the tractable computation of certain quantities of interest, e.g., the computation of integrals, information theoretic measures or maxi- mization (Vergari al., 2021). This can be done in a systematic way in the framework of circuits, that maps these computations to the presence of certain structural properties of the computational graph, precisely defining sufficient (and sometimes necessary) conditions for tractability. We start by defining smoothness and decomposabilllyy two structural properties of circuits that allow to tractably compute summations over exponentially many variable assignments, which are often intractable to compute for other models.
Definition 3 (Unit-wise snoothness and decomposability (Darwiche & Marquis, 2002)). A circuit is smooth if for every sum unit n, its input units depend all on the same variables, i.e,, Vi,j E in(n): sc(i) = sc(j). A circuit is decomposable if for every product unit n, its input units depend on mutually disjoint sets of variables, i.e. Vi,j # j: sc(i) n sc(j)= @.
For a smooth and decomposable circuit one can exactly compute summations the form Exedom c(y, 2), where Z c X, Y = X,Z, called marginals, in a single feedforward pass of its computational graphs (Choi et al., 2020). See also our discussion in Section 3 for more use cases of smoothness and decomposability. It easy to verify that a Tucker tensor factorization represented as a circuit (e.g., Fig. 2) is both smooth and decomposable, and hence inherits traciable marginalization. In addition, under this light, one can understand the expressiveness of these factorizations, for multilinear polynomials expressiveness is usually characterized in terms of circuits with these structural propertics (Shpilka & Ychudayoff, 2010; Martens & Medabalimi, 2014; de Colnet & Mengel, 2021).
Where do circuits and tensor factorizations come from? Now that we have established a first link between lensor factorizations and circuits, as the former can be rewritten as computational graphs with structural properties in the language of the latter, we also point out a first difference in how the two communities obtain and approach these objects. Tensor factorizations arise from the need to compressing a given digh-dimensional tensor, which is usually explicitly represented (if not on memory, on disk). A factorization is then retrieved as the output of optimization problem, e.g., find the factors that minimize
6

---

Published in Transactions on Machine Learning Research (02/2025)
certain reconstruction loss (Sidiropoulos et al., 2017; Cichocki et al., 2007). In contrast, modern circuits are learned from dala. While this can be done both in a supervised and unsupervised way, the latter is more common as circuits are learned to encode a probability distribution. Such a distribution can be thought as an implicit tensor that is never observed, but from which we sampled data points. Scction 3 formalizes this and the circuit learning problem. Even if reconstructing lensors is generally done differently than learning circuit from data, once a factorization is given, by looking at as a circuit, we can open up new opportunáties to use it and exploit it. We highlight them as boxes in the following sections. Next, we discuss how the framework of circuits also generalizes hierarchical (or deeper) tensor factorizations, which will also provide the entry point of our pipeline for learning both circuits and tensor factorizations (Section 4).
2.2 Hierarchical Tensor Factorizations are Deep Circuits
Tensor factorizations can be stacked together to form a deep or hierarchical factorization that can be much more space-efficient (i.e., of much lower rank) than its shallow materialization. For instance, Grasedyck (2010) proposed hierarchical Tucker, which stacks many low-rank Tucker factorizations according to a fixed hierarchical partitioning of tensor dimensions. Cohen et al. (2015) showed that in most cases equivalent or even approximate shallow factorizations would instead require an exponential rank with respect to the number of dimensions. Similar theoretical results have been also shown for circuits, i.e., deep eircuits can be exponentially smaller than shallow circuits, where the size of circuit is the number of unit connections (Delalleau & Bengio, 2011; Martens & Medabalimi, 2014; Jaini et al., 2018b).
In this section, we first roduce the hierarchical Tucker factorization, show that il is a deep circuit, and later use this connection to describe modern tensorized circuit. representations (Section 4). To do so, we borrow a tool from the circuit literature: a hierarchical partitioning of the scope of circuit (Vergari et al., 2021), aka region graph (RG) (Dennis & Ventura, 2012). As we formalize next, a RG is a bipartite graph whose nodes are either sets of variables, L.e., the dimensions of the tensor, or indicate how they are partitioned.
X,. X2 X3
Definition 4 (Region graph (Dennis & Ventura, 2012)). Given set of variables X, a region graph R is a bipartite and rooted directed acyclic graph (DAG) whose nodes are either regions, denoting subsets of X, or partitions, specifying how a region is partitioned into other regions. The root is the region node X.
X1
X2
Without loss of generality, we assume binary RGs, ie.,, each region partitioned into two others, as shown in Fig. 3. Similarly our graphical notation of cir- cuits (Def. 2), we remove the directionality of node connections from the figures and assume that edges are oriented from region nodes of more variables towards regions of fewer variables. Next, we define the hicrarchical variant of Tucker.
X1
Xa
Figure 3: A tree RG.
Definition 5 (Hicrarchical Tucker factorization). Let T E R4xx.xx be a d-dimensional tensor, and lot X be the region root of a tree-shaped binary RG R whose leaves have exactly one variable, where dom( X,) = [4]] for all X2 E X. The hierorchical Tucker factorization of T is given by recursively applying Tucker factorizations according to the partitioning of indices induced by R. There are three cases:
(Z) First, for every leaf region Z = (X1} in R, we define unyr to be an alias of the (zz, r)th entry of the factor matrix vo) E , Rz associated to Z.
Nexl, for every non-leaf region Y X partitioned into (Z,, Z2) in R, i.e., Y Z with Y (Y mm Z1 = 1 Ze = { we recursively define the Tucker factorization associated to Y as
Rz
Rzg
Y
Σ
Σ
w
STIT2
(ZA) 21.1
MT 1
with s E [Ry].
(6)
where (Ry, R2, Rzz)) denotes the multilinear rank of the Tucker factorization. Moreover, W!!)) E R xRz, xRz, is the corresponding core tensor, and y (,I,..., ,1),
22
(22,1,..., 22 are assignments to variables Y, Zi, Ze, respectively.
Finally, in the case of the root region Y X in the recursive rule in Eq. (6), we define Rx = and (Y) p in Eq. (6) becomes alias of the entry lanzgrzz of T.
7

---

Published in Transactions on Machine Learning Research (02/2025)
Tucker layers
X
W
+
"iik
(3)
(3)
X
+
(3)
Yag
22
(2) Vaga
(a)
(b)
Figure 4: Hicrarchical Tucker factorizations are deep (tensorized) circuits as shown here with the circuit representation of the hierarchical Tucker factorization of three dimensional tensor (a), which is obtained by stacking two Tucker factorizations according to the RG in Fig. 3. Evaluating the circuit from left to right for some entry (I1, 43) computes the corresponding tensor entry. In (b) we show the equivalent tensorized architecture (Def. 7) obtained by grouping units into layers, according the graphical convention introduced in Def. 7. Input layers map indices inlo rows of factor matrices, while products layers compute Kronecker products of their inputs, and sum units compute matrix-vector product. The core tensors (2 _222222 wy(1) 11x2x2 that parameterize the sun units in (a) are reshaped into matrices W 2 w(1), R1x4 in (b). In Section 4 we will refer to the composition of Kronecker product and layers simply Tucker layer, as showed in (b).
We provide an example of a hierarchical Tucker factorization, as to show an application of the recursive Tucker factorization shown in Eq. (6). Given dimensiimelli tensor T E IR I we factorize it via hicrarchical Tucker according to the RG shown in Fig. 3. Since the RG Fig. has two partitionings, wo recursively perform two Tucker factorizations (as Eq. (6)), and choose (Rqx, Xx) Rxx,), R(x, .x)) and (R) R(xs)) the respective multilinear ranks, i.e. each entry of T is approximated as
R(xa)
Rix Xal Σ
X2. 312273
Σ
(Xx)) (X, 12 21 P2
w Wirira
where W e [xx Rixx, is the core tensor of the first Tucker factorization, (Xx) ((xx8(x2) is the factor matrix associated to (X2), and (X)..aa) x consists of R(x,,xs) matricos of shape I I3 being factorized according to the second Tucker factorization," i.e.,
Rxx,)
Rix
(x1.Xa) 21 22 12
Σ
Σ
w (x.Xa) (x1)) (Xa)). Parana B1 Ta R3 P41
where (X)) ( ((x) R and V(Xs) RR R
Following this recursive definition of hierarchical Tucker factorization, now build equivalent circuit encoding the same factorization, ie., fx s c(x), by stacking weighted and product units together to construct a deep circuit. In the following constructive proposition we present this construction.
Proposition 2 (Hierarchical Tucker
deep circuit). Let T x be tensor being decomposed using hierarchical Tucker factorization according to a RG R. Then, there exists circuit over variables X = (X,] with dom(X,) = [4J. computing the same factorization. Furthermore, given ( Jm c 2X
the set of all non-leaf region nodes ((i) S X being factorized into (z()) - in R, with corresponding Tucker factorization multilincar rank (Rya) Rygo, Ryja), we have that |c| E O [ Rypo R R Rg50)
2The Tucker factorization of three-dlmensional tensor into only factor matrices implicitly assumes the identity matrix third factor, and it also called Tucker& factorization (Tucker, 1966; Kolda Bader, 2009).
8

---

Published in Transactions on Machine Learning Research (02/2025)
+
W
W
+
O
+
+
+
W
(3)
(4) Vag:
W
W
W
Vira:
Vaya
X
X
(1) Vari:
(2)
(6) 211
(3)
(4)
Varg
211
Varg
Vau
Figure 6: Tensorized circuits encode novel hierarchical multilinear factorizations by mixing different structures and layers. Section 2.3 and Fig. 7 formalize and illustrate our tensorized circuit formalism, respectively. The figure on the left shows lensorized circuit over variables X 1X1, X2, Xa) encoding an allowed multilinear factorization of three-dimensional tensor (as it is smooth and decomposable, see Def. 8). Note that each input layer has its own factor matrix V() with j E [6], and the architecture consists of a mix of Hadamard, Kronecker and sum inner layers. Overall, this tensorized circuit do not map to known hierarchical factorization. The figure on the right shows a similar tensorized circuit, where the factor matrices v and ((3) are instoad shared while still encoding an allowed multilincar factorization.
Appendix A.2 shows the construction, also illustrated in Fig. 4a for hicrarchical Tucker factorization based on the RG showed in Fig. 3. In the very same way one extend any tensor factorization to be hierarchical, one represent such a construction as circuit. However, in the circuit literature we found many architectures that are not limited to RGs that are trees nor to those having univariate input regions.
Opportunity 1. A wider choice of factorization structures
X X₃
Def. 4 allows for arbitrary DAGs and arbitrarily scoped-regions, while hicrarchical tensor factorizations are usually presented in terms of RGs with tree structure having region leaves containing exactly one variable (e.g., the RG in Fig. 3), which are sometimes called dimension trees mode cluster trees (Grasedyck, 2010) in the tensor factorization munity, and often utree in circuit literature (Pipatsrisawat & Darwiche, 2008; Kisa et al., 2014; Wedenig et al., 2024a). More intricate RG struc- tures can increase the expressiveness as well as flexibility in building deep circuits/ cireuits/hierarchicall hierarchical factorizations. Intuitively, we can share factor matrices among multiple factorizations, and therefore reduce the mum- ber of model parameters, making more spaco-efficient implementation possible. See Peharz et al. (2020c;a) for more details. We provide an example of such RG in Fig. 10 and Fig. 5 here on the left.
X
X₂. Xa
X1
X2
Figure 5: Region nodes can be shared between par- titionings a DAG RG.
The reader can check that this RG encodes the hierarchical scope partitioning of the decomposable circuit in figure Fig. 1. Fig. 9 then illustrates a fragment of this RG and shows how tensor factor- izations conforming to can be constructed as circuits Section The circuit literature provides several ways build RGs that are suitable for certain data modalities (e.g., image, sequence, tabular data), which can also be learned from data. Section 4.1 provides an overview of such techniques.
Imposing a particular factorization structure by leveraging a RG, and picking a particular parameterization for each region it (as it will be discussed in Scction 4), represents one way to encode novel hicrarchical factorizations that do not correspond to existing ones. Fig. 6 shows some examples. There, we represent cir- cuits in layer-wise formalism described later in Section 2.3. Note that instantiating tensor factorizations
9

---

Published in Transactions on Machine Learning Research (02/2025)
from RGs defined as above preserve decomposability, and that circuits built from RGs in the literature are typically also smooth (Def. 3). Hierarchical Tucker and its variants are also smooth and decomposable and therefore support the tractable computation of number of (probabilistic) inference tasks (Section 3). These hicrarchical factorizations (and the corresponding deep circuits) that follow a tree-shaped RG with univariate leaves satisfy an additional structural property, called structured-decome decooposabiilyyy Structured decomposabll bil- ity enables the tractable computation of harder operations for which smoothness and decomposability are not enough. For instance, squaring particular tensor factorizations formalized in the graphical language of tensor networks, known the Born rule in physics (Feynman, 1987; Glasser et al., 2019) (see also Section 2.4). We define structured decomposability below.
Definition 6 (Structured decomposability (Pipatsrisawat & Darwiche, 2008)). A circuit is structured de- composable if (1) it is smooth and decomposable, and (2) any pair of product units n,m m having the same scope decompose their scope at their imput units in the same way.
We can easily check that hierarchical Tucker yields a structured decomposable circuit, as it is obtained by stacking Tucker factorizations (which are computed by decomposable circuits) based on a tree RG, which in turn synchronizes all product units to decompose in the same way. We emphasize that eliciting the few structural properties that can explain the tractable computation of many different quantities of interest can help save effort aimed at (re)discovering and (re)engincering algorithms for specific hicrarchical factorizations.
Opportunity 2. Efficient Compositional Operations over Factorizations
Given one or more tensor factorizations appearing as operands in a computation of interest, how can we automatically devise tractable algorithm for it without having to materialize the exponentially large tensor operands? The circuit literature holds the answer and offers other structural properties that can unlock the tractable computation of many complex inference scenarios, in reusable fashion. F.g., when two deep circuits conform to the same tree RG, they are said to be compatâble (Vergari et al., 2021). Given two compatible hierarchical tensor factorizations and q over X, one can compute general expectations of the form
Σ (xx){(x))
(expectations)
in closed form in time O(pllal), where lo| and |ul are the size of the corresponding circuits encoding such factorizations. On the other hand, maximization problems as in maximum-a-pon a-posteriori inference
maxy ply, E = c)
(MAP inference)
where is the evidence assignment to variables E c X, and y is the assigmment to the remaining variables Y = X for which we want to maximize p, can be solved exactly and efficiently if is a decomposable circuit that supports an additional property, determinism (Darwiche, 2009). In a nutshell, sum units in a deterministic circuit receive inputs from functions with disjoint support (see Choi et al. (2020) for details). While determinism is a consolidated property in the circuit literature, it is off the radar for (hierarchical) tensor factorizations. Furthermore, the circuit literature provides a systematic way to quickly devise the tractability conditions for given mathematical expression that involves sums, products, powers, exponentials and logarithus,, and therefore automatically distill corresponding tractable algorithms (Vergari et al., 2021). For example, if one wants to compute Rényi's a-divergence between two factorizations p and over variables X, for a e N, defined as
a1- llg Σ, pd (x)g
(a-divergence)
then this can be done quickly if and q can be represented smooth, decomposable and compatible circuits and is also deterministic. Vergari et al. (2021) show how to automatically distill the tractable computation of more infomatiion-teooeed quantities.
10

---

Published in Transactions on Machine Learning Research (02/2025)
X
+
W
input layer
Hadamard layer
Kronecker layer
sum layer
Figure Tensorized "Lego blocks". In the rest of the figures we will abstract away from individual connections between units (as we did so far, and as we do in the top row illustrations) and represent layers as (colored) blocks (bottom row). Input layers O are the only layers that do not have any other layer input, i.e. they take variables assignment and output vector computed by function f. Hadamard o and Kronecker
product layers receive inputs from at least two other layers (represented in gray), and compute the Hadamard and Kronecker products of their inputs, respectively. A sum layer parameterized by a weight matrix W concatenates its input layers into a single vector, and then multiplies it by W.
2.3 Representing Circuits in a Tensorized Formalism
Representing (hierarchical) tensor factorization (deep) circuits highlights how circuit units can be naturally grouped together by type and scope into layers, as hinted already in Fig. 2. This perspective presents new opportunity: defining and representing certain circuit structures as tensorized computational gruphs. While circuits in the literature are defined in terms of scalar computational units, sum, product and inputs and single connections (Def. 2), many successful implementations of circuits nowadays already group units into tensors (Vergari et al., 2019a; Poharz et al., 2020c;a; Liu & Van den Brocck, 2021b; Loconte et al., 2024) with the goal of speeding up computation by using the acceleration provided by GPUs. Following these ideas, now provide general tensorized circuit definition that offers modular way to build overparameterized circuit architectures. This will allow us to design a single learning pipeline that subsumes many existing architectures (Section 4), and also suggest a way to create novel ones by mixing and reusing small "blocks".
Definition 7 (Tensorized circuit). A lensorized circwil is a computational graph composed of three kinds of layers: imput, product and sum. Each layer & consists of computational units defined over the same scope sc(E). Every non-input layer receives the output vectors of other layers as inputs, denoted with the set i()). The three kinds of layers are defined as follows:
Each input layer l has scope Y = X and computes vector function f: domm (Y) - R
Each product layer l computes either an Hadamard product (Oezein(e) ej) or Kronecker product (Øezeince) (j) over the vectors it receives from its input layers Ej.
A sum layer with S sum units computes the matrix-vector product W(ll e,inte) ()(sc(e))), where denotes vector concatenation and We e R K > 0 are the sum layer paramelers.
Note that a sum layer receives only one input vector, i.e., [in(E) 1, then it simply computes W&, (sc(E,)) ())). Fig. illustrates the layer types of tensorized circuit, together with the unit-wisc representation (Def. 2). Furthermore, we retrieve the previous scalar unit-wise definition by setting K, the size of each layer, to 1. The above four types of layers constitute the basic "Lego blocks" that will later use to create more sophisticated layers (Section 4.3, Section 5) and reproduce all modern circuit architectures (Table 1).
As a first example on how this definition can help to abstract away from details in circuit architectures, see Fig. 4. There, sum and Kronecker product layers are used to stack two Tucker tensor factorizations to represent hicrarchical one. We provide in Scction deep circuit this way. We can now casily extend the unit wise definition of structural properties in Def. 3 to this layer-wise representation, by defining the scope of each layer.
systematic way to stack different layers and build a
11

---

Published in Transactions on Machine Learning Research (02/2025)
A
A
A ()
Let (3)
oap === 2j-1 Vini D Cras
with v BANN B RR
Ce RRAN
w
+
X1 X2
Let V A R X3
V
V = A A C RAxN,
c(21, 22, 22)
= B RKN
(a)
(b)
deep tensorized circuit with Hadamard product layers (b). To obtain the parameters of the circuit, the tensor A in the MPS/TT (a, showed Penrose graphical notation) is firstly factorized into matrices V(2), B, C through a / CAAOOMPPPPAAAAAA /PARAFAC decomposition (Carroll & Chang, 1970). Then, v(),, v(3), W are obtained in the figure (a). See Loconte et al. (2024) for the detailed circuit construction. In (b) we denote with 1 row-matrix whose entries are all ones.
Figure 8: A MPS/TT represented
Definition 8 (Layer- smoothness and dccomposability). tensorized circuit over variables X is smooth layer L, its imputs depend all on the same variables, i.e., Vlg, in(e): sc((,) sc(e,), where
if for every sc(e) S X is the scope of layer i.c., the scope of the units in L. It is decomposable if for every product layer l in il, its inputs depend on disjoint sets of variables, i.e., vl,, Ej in(e), # sc((,) sc(e;) ø.
Note that by assuming that every layer is composed by units sharing the same scope, and by using the three layers defined in Def. 7, we obtain tensorized circuits that are smooth and decomposable by design. Furthermore, if the RG of a deop circuit is a tree, then the tensorized circuit will be structurad-dccompssable (Def. 6) as well. is possible to quickly read these properties out of the graphical representation of hier- archical Tucker as a tensorized circuit in Fig. 4b. Next, we use this layered abstraction bridge to the popular tensor networks, and show how they be naturally encoded as deep circuits.
2.4 Tensor Networks as Deep Circuits
Tensor networks (TNs) are often the preferred way represent hierarchical tensor factorizations in fields such physics and quantum computing (Markov & Shi, 2008; Schollwoeck, 2010; Biamonte & Bergholm, 2017). TNs come with graphical language Penrose notation to encode tensor dot products in a compact graphical formalism (also called tensor contractions). See Orús (2013) for review. Perhaps, the most popular TN factorization is the matrix-product state (MPS) (Pérez-García el. al., 2007), also called tensor-train factorization (TT) (Oseledets, 2011; Glasser et al., 2019; Novikov et al., 2021). For instance, given a tensor T 1R/1x--xla, its rank-R MPS/TT factorization is defined element-wise notation as
Σ
Σ
Σ Tu-1-1
(2) a a ia-iia-a 1a-1-
(d-1)
(d)
where A (1) R A (d) E R and A e R with 1 < < d. That is, an MPS factorization decomposes T into the complete contraction of a chain of smaller tensors A (1) A (d) and (A Fig. Sa shows an example of a MPS/TT represented in Penrose graphical notation, i.e., where nodes denote the tensors A (1) (2)
(d) edges denote summations over shared indices, and XI,..., Xa denote the tensor indices whose assigmment, yield the corresponding lensor entry. Loconte et al. (2024) showed how an MPS can be represented as a deep tensorized circuit by encoding summations and products in Eq. (7) into sum and (Hadamard) product layers, respectively.
(d-1) A A(d),
Proposition 3 (MPS as deep tensorized circuits (Loconte et al., 2024)). Lot T E R4xxxll be tensor being decomposed via rank R matrix-product state (MPS) factorization. Then, there exists structured decomposable tensorized circuit over variables X {X,)Ø=1 with dom(X,) [41.j e [d] computing the same factorization, i.c., tx & c(x) for all entries x. In addition, we have that |c| O(dN2) with N & min R2, R max (I,,.., Ta])-
12

---

Published in Transactions on Machine Learning Research (02/2025)
In Fig. 8 we show a tensorized circuit representing a MPS/TT over variables X = (X1, Xs), and, detailed in the proof of Proposition 3 in Loconte et al. (2024), the parameters of its input and dense layers are obtained by decomposing the tensors (= of the MPS/TT. Similarly to the tensorized circuit rep- resentation of hierarchical Tucker (Proposition 2), Proposition 3 yields a tensorized circuit that is structured is the crucial property in MPS/TTs that allows to per-
decomposable (Def. 6). Structured- form certain operations over them tractably, for instance squaring them as to recover a Born machine a probabilistic model devised to simulate quantum many-body systems in physics (Orás, 2013; Glasser et al., 2019). Understanding this enables practitioners to design alternative Born machine architectures that are not limited to a sequence of tensor operations as encoded in a "lincar" RG, without having to prove the tractability of the square operation over these architectures from scratch (Shi el al., 2005). This is one of the opportumities we highlighted for hierarchical tensor factorizations once represented circuits (Opportunity 1 and Opportunity 2). Further opportunities will be presented in the next section and directly translates to TNs as well as classical tensor factorizations.
Next steps. Until now, discussed the generic decomposition of a real-valued tensor. However, tensor faclorizations that are tailored for non-negative data (e.g. images), called non-negative lensor faclorizations, factorize tensors into non-negative factors that can be casily interpreted (Cichocki & Phan, 2009). In Section 3, we connect non-negative tensor factorizations to the literature of circuits for probabilistic modeling, which allows us to interpret them as deep latent-variabll models. In addition, by bridging non non-negative tensor factorizations and their representation as (deep) circuits, we showcase future research opportunities related to both paramcterizing tensor factorizations and performing probabilistic inference with them.
3 From Non-negative Factorizations to Circuits for Probabilistic modeling
Much attention has been paid in machine learning on circuit representations for tractable probabilistic mod- eling, i.e,, for modeling probability distributions that support tractable inference. Circuits built with such purpose are usually called probubilistic circuils (PCs) (Vergari el al., 2019b; Choi el al., 2020). In this section, we connect non-negative tensor factorizations and PCs, showing a number of research opportunities for the tensor factorization community within the probabilistic machine lcarning panorama.
First, we bridge non-negative (hierarchical) tensor factorizations with the discrete latent variable interpre- tation of (deep) PCs, showing examples of available algorithms for linear-time probabilistic inference that exploit this interpretation (not only marginals, discussed in the previous section, but also sampling). Sec- ond, we show how the rich literalure on PCs provides several compact parameterization techniques that can yield non-linear factorizations. At the same time, we leverage optimization tricks from the non-negative ten- sor literature to learn PCs. Finally, we connect with the literature of infinite-dimensional tensor factorizations showing their relationship with PCs encoding probability density functions, as well as with PCs equipped with infiiitediimensionall sum units. We start by describing how to represent a probability distribution over finitel-ddiscret random variables as tensor factorization.
Let p(X) be probability mass function (PMF) over Enitely-discrett random variables X = (X1}}_ where each X, E X takes values in dX,(X,) = [T]] Then, the simplest representation of p(X) is that of a probability lensor T R4 Il such that every entry encodes the probability of a joint configuration of X, i.e., tzi--z = p(. xa) for any x (.1,..., za) dom(X). Clearly, this representation is inefficient, as it scales exponentially in space with respect to the number of variables d. A natural way to compactly model p(X) is via a non-negative tensor factorization, e.g., the non-negative version of Tucker (Kim & Choi, 2007), where the factor matrices [ J and the core tensor W shown in Eq. (2) are restricted to have non-ncgative entries only. By trivially specializing Proposition 2, we can encode the non-ncgative hicrarchical Tucker factorization (Vendrow et al., 2021) in a circuit e that outputs non-negative values, also called a PC.
Definition 9 (Probabilistic circuit (Choi et al., 2020)). A probabilistic circuit (PC) over variables X is circuit encoding function c(X) that is non-negative for all assignments to X, i.e. Vx E dom(X): c(x) > 0.
A sufficient condition ensure a circuit is a PC is constraining both the parameters of sum units and the outputs of input units to be non-negative, resulting in circuit that is called monotonic (Shpilka &
13

---

Published in Transactions on Machine Learning Research (02/2025)
Yehudayoff, 2010). For instance, the circuit encoding non-negative hierarchical Tucker factorization that we mentioned above is monotonic PC, as its sum unit weights (i.e., the entries of the core tensor W) and the outputs of its input units (i.c., the entries of the factor matrices ( are restricted to be non- negative. Smoothness and decomposability in circuits allow for the tractable computation of summation and integrals (Section 2.1), which translates into exactly computing any marginal or conditional distribution for PC with these structural properties (Vergari et al., 2019b). However, these PCs are not just tractable probabilistic models, they are also generative models from which it is possible to sample exactly.
3.1 Non-negative Tensor Factorizations as Generative Models
As non-negative factorizations such as non-negative hierarchical Tucker are smooth and (structured) de- composable PCs (Defs. 3 and 6), they inherit the ability of PCs to perform tractable inference and to generate new data points, L.., certain configurations of the variables they are defined on. To the best of our knowl- edge, this treatment of tensor factorizations as generative models has gone unnoticed so far. We discuss it in the following, showing how one can devise (faster) sampling algorithms for these representations.
First, we review the simplest way to sample from a non-negative factorization. Consider a non-negative (hierarchical) Tucker factorization (Def. 5) encoding p(X) and modeled as tensorized monotonic PC c. We can sample a data point x = (x1,-..,,a, T.) from p(X) by autoregressively sampling one variable at a time, conditionod to the previously sampled variable assignments. That is, we can first marginalize all variables except X1, and then sample from the distribution p (1), i.e, Iı ~ p(X)). This can be done in time O(cc), as с is both smooth and decomposable (Def. 3, Def. 8). Then, for all d 1, we condition w.r.t. to the assignments to variables (X,)==] and sample Xd, i.c., Fd p(Xa ; Xa-1). This "naive" sampling procedure requires worst-case time O(d[c), where |c| is the circuit size (see Def. 2). This can be inefficient in case of large d. However, for smooth and decomposabl circuits, we can sample in ((cc) only, by interpreting them as discrete latent variable models (Peharz et al., 2017; Vergari et al., 2018).
Opportunity 3. Tensor factorizations as discrete latent variable models
Each sum unit in a smooth PC can be thought as a minture model computing:
Σx Wn,i Cn,i (X), where
Σ
K 1- Wn.i
C. (X)
Wn,i 0,
(8)
i.e., a convex combination of the its K inputs, each one representing a distribution. At the same time, this can be interpreted as summing out a discrete latent variable Z, that has K different states,
(x( = -x,,, p(Zn =
Pn, Un =
Pn,i
where the non-negative weights Wn, are the marginal probabilities of this latent variable. As such, the whole circuit, and hence the corresponding non-negative tensor factorization, can be seen a hierarchical latent variable model (Peharz et al., 2016; Choi et al., 2011), with as many discrete latent variables as the number of sum units. Therefore, as for any mixture model, to sample x we can first sample the latent variables, and then sample the mixture components. procedure can be done efficiently by performing a backward traversal of the circuit computational graph (Vergari et al., 2019a; Dang al., 2022a). We provide this algorithm for lensorized circuits in Algorithm C.1, which sample batch of N data points in parallel and discuss it in Appendix C. Other efficient probabilistic inference tasks can be "imported" from the circuit literature for smooth and decomposable PCs. See Vergari et al. (2021) for more details.
practice, this sampling
3.2 How to Parameterize Probability Tensor Factorizations?
Circuits and tensor factorizations are the output of two different optimization problems that however share some common challenges. Understanding them can open new opportunities for both communticss. In
Non-monatoiic PCs, which allow negative weights while ensuring non-negative outputs, are possible Loconte et al. (2024).
14

---

Published in Transactions on Machine Learning Research (02/2025)
application scenarios of (non-negative) tensor factorizations, the main task is to compress reconstruct given tensor, which is generally explicitly represented in memory. Hence, the parameters of the factorization are optimized as to minimize a reconstruction loss (Cichocki et al., 2007). In contrast, modern PCs are learned from data. That is, one is given a dataset of N datapoints |,=1 that are assumed to be drawn i..dd from and unknown distribution p(X) (Bishop & Nasrabadi, 2006). The probability tensor that encodes p(X) is therefore implicit and cannot be fully materialized, as the probability distribution is unknown, but also because of its possible exponential size (or even infinite, see Section 3.4).
As learning in PCs often reduces to an optimization problem, i.e, maximizing the data (log-)like likelihhood (Pe- harz et al., 2016), enforcing the non-negativity of the circuit is done by using one or more reparameteriaations. i.e,, mapping real-valued parameters to positive sum unit weights. This is necessary as the sun weights of a monotonic PC need to form a convex combination to yield a valid distribution (as shown in Eq. (8)). For instance, we can squash the K' parameters 0 R of a sum unit with K inputs through a softmax function, i.c. w softmax((). Using such reparameterization together with input functions encoding probability distribut ions delivers PC whose normalization constant is 1, as the probabilities of all variable assignments sum up to one. This is direct consequence of having the weights of each sum unit summing up to one. For tensorized circuits, this reparametcrization would act row-wise on the parameter matrix of every sum layer.
Luckily, if the circuit is smooth and decomposable (Def. 3), we can still compute its normalization constant exactly and efficiently even if sum weights are not normalized (Peharz et al., 2015). This allows us to use alternative ways to reparameterize a monotonic PC e, even if its reparameterization delivers an unnormalized distribution, i.e., a distribution not integrating to 1. In fact, we can still recover a distribution p(X) efficiently via. normalization, i.e., p(X) c(X)/Z with Z Exedom[x) c(x) being the normalization constant. For instance, we enforce each sun unit parameter 0 to be non-negative via exponentiation, ie. w = exp((). In this paper, we introduce a third way, simpler implementation trick that we borrow from the literature on gradient-based optimization for non-negative tensor factorizations (Cichocki et al., 2007): projecting the sum unit parameters in the positive orthant after every optimization stop, i.c.,
w == ==max(e,00) 0),
0E R
(9)
where 6 is a positive threshold close to zero. Each reparameterization can yield a different loss landscape and load to diffcrent solution during optimization. In our exporiments (Section 6), we found this third reparamelerization to be the most effective to learn PCs. When it comes to input units in monotonie PCs, they need to model valid distributions. Common parameterizations can include simple PMFs (or densities, see Section 3.4) such as Bernoulli or Categorical distributions, or even other probabilistic models as long as they can be tractably marginalized. This yields a set of possible parameterizations that go beyond the simple mappings from indices to matrix entries, as usually used in tensor factorizations (oriiiionnnPPPooooo (Proposition and Fig. 2).
Opportunity 4. A wide range of possible parameterizations
Estimating a PMF p(X) via a probabilistic model is another way to perform an implicit tensor com- pression. If this model is a circuit, then this compression exactly maps to a non-negative hierarchical tensor factorization but over a number of basis functions, which are the circuit input units. These input units (thus also input layers in our tensorized formalism) can encode more memory efficient and more expressive functions than indicators. For instance, one can use Binomial distributions instead of categoricals as to drastically reduce the number of parameters of the factorizations (Peharz et al., 2020c). In the case of infinite-dimensional probability tensors (sec Section 3.4 below), discrete vari- ables with infinite support can instead be modeled by using Poisson distributions (Molina et al., 2017) or generative models as input layers, such as normalizing flows (Papamakarios et al., 2021; Sidheekh et al., 2023), variational auto-encoders (Tan & Peharz, 2019), or also non-linear functions that can be integrated efficiently, e.g., splines (Novikov et al., 2021; Loconte et al., 2024). Parameterizing imput units in this way yields a tensor factorization that uses non-linenrilies. Along this direction, in the circuit literature parameters of sum layers have been directly parameterized by neural networks (Shao et al., 2020; 2022; Gala et al., 2024a). These non-linear cases have only been explored very recently in the matrix and tensor factorization literature (Leplat el al., 2023; Awari el al., 2024).
15

---

Published in Transactions on Machine Learning Research (02/2025)
3.3 Reliable Neuro-Symbolie Integration
A prominent use case for tractable inference with PCs is in safely-critical applications, where it is necessary to enforce hard constraints over the predictions of newral classifiers (Ahmed et al., 2022; van Krieken et al., 2024). Such constraints can be expressed as logical formulas over symbols extracted by a perceptual component (a classifier). For example, the safety rule that a self-driving car must stop in front a pedestrian or a traffic light. (Marconato et al., 2024b;a) can be written as a propositional logical formula o: (P v R =>> S), where P, R and S are Boolean variables representing that a Pedestrian and Red-light have been detected in the video stream of the car and the action to Stop must be taken.
Circuits are especially suitable for this neuro-symbolic integration (De Raedt et al., 2019), because they can represent both probability distributions and logical formulas. These two representations can be used in a single classifier to guarantee that the predictions that will violate the given constraint will always have 0 probability. Formally, we can implement such a classifier, mapping imputs x to outputs y that have to satisfy a constraint @, as (Ahmed et al., 2022):
ply x) oc aly xy +]
(10)
where q(y | x) is a conditional distribution encoded in a circuit that can be parameterized by a neural network (see Opportunity 4) and 1(y } Φ) is an indicator function that is when the predictions y satisfy (H) the constraint Φ. For instance, y is a Boolean assignment to variables P, R, S in our self-driving car example, and 1 F o) is iff substituting y to variables in é yields "true" (T). This indicator function be compactly represented as circuit made of sum and product units through process called knowledge compilation (Darwiche & Marquis, 2002; Chavira & Darwiche, 2008; Choi et al., 2013). If both the proba- bility distribution and the indicator function for the constraint & are compatible circuits (Opportunily 2), one can efficiently multiply them and renormalize by computing the partition function (Vergari et al., 2021), which equals the probability that the hard constraint & holds given x, i.c.,
Σ, g(y x) + o) = Ey [1ly - Φ}1 = x(==Txx
(11)
also called the weighted model count (Chavira & Darwiche, 2008; van Kricken et al., 2024) which is the crucial quantity to compute when combining logical and probabilistic reasoning (Darwiche, 2009; Zeng et al., 2020). This possible integration, as far as we can tell, off the radar of the tensor factorizations community.
Opportunity 5. Structured sparsity via logical constraints
Circuits encoding logical formulas are generally very sparse, nonetheless, they still represent a (sparse) factorization of a tensor, in this case a Boolean one. Analogously to the probability tensor described at the beginning of Section 3, this Boolean tensor would encode the logical formula as an exponentially large table of zeros and ones. Multiplying a probability tensor compactly encoded as circuit q as in Eq. (10) with this compact representation of a Boolean tensor equals structured form of masking: all the invalid (according to the logical constraint Φ) entries in the probability tensor are forcefully set to zero, thus making such entrics not predictable. A possible opportunity is therefore to connect with the vast. literature of knowledge compilation (Darwiche & Marquis, 2002; Choi et. al., 2013; Oztok & Darwiche, 2017) to impose structured sparsity to tensor factorizations.
Possible applications include ncuro-symbolic integration for graph data (Loconte et al., 2023) as well as representing rankings and user preferences (Choi et al., 2015), scaling cryptographic attacks (Wedenig et al., 2024b), enforcing constraints over the output of LLMs (Zhang et al., 2023) and promoting their self-consistency (Calanzone et al., 2025).
"Note that arbitrary ANDs and ORts in logical formula do not directly correspond to products and sums in circuit language. necessary compile the formula in representation that contains ANDs over sub-formulas with disjoints scopes corresponding to decomposable products and XORs corresponding deterministic sum units, and pushes negation towards the input functions (Darwiche & Marquis, 2002).
16

---

Published in Transactions on Machine Learning Research (02/2025)
3.4
Probability Tensors and Continuous Factorizations
Until now, we discussed circuits representing (hierarchical) factorization of a tensor having finite dimensions, ie., where the number of entries in every dimension is finite. That is, these circuits are defined over set of discrete variables, cach having a finite number of states. In this section, we focus on factorizations of tensors that can have dimensions having an infinite (and possibly uncountable) number of entries or quasi-lensors (Townsend & Trefethen, 2015). Analogously to the symmetry between (hierarchical) tensor factorizations and circuits (Soction 2) wc show that quasi-tensors can be represented as circuits defined over at least one variable having infinite (and possibly uncountable) domain. Furthermore, by connecting with very recent class of cireuits equipped with integral units, we point out at opportunities regarding the parameterization of infinite-rank (hierarchical) tensor factorizations, i.e, factorizations whose rank is not necessarily finite. We ground these ideas to the problem of modeling a probability density function (PDF).
Formally, let pXX) be a PDF over continuous variables X = (X,))_1 where each X, E X takes values in dom(X,) = R. Then, p(X) can be represented as an infiniteddimensionall probability tensor T such that t(FI....., =z)= = p(Z for any x E dom(X). anfinitedimmnssoon decomposed into a finite number of sums and products of factor matrices that live in Hilbert spaces of generie functions. For instance, we can re-adapt the Tucker factorization shown in Def. 1 different factorization method where, instead of having factor matrices v E xR, for all j, we encode a vector of R3 functions FU (/// dom(X,) - - That is, we factorize T
tensors such as p(X) can be
R1
1x Fa)
W Wm (21) ...
11 119(())) (ra).
(12)
Here, we have We R. x.xxxx.R. Rs, Then, one can trivially modify Proposition such that this Tucker factor- ization of p(X) can be represented as a PC of the same size where the inpul units over variable Xj now encode the functions in Fū), Similarly, one can retrieve PCs encoding mixed probability distributions over discrete and continuous variables (Molina et al., 2018), thus encoding factorizations of a quasi-tensor. In the same way, one can easily re-adapt hierarchical Tucker to factorize p(X), thus yielding an equivalent deep circuit over continuous variables.
Note that, while Eq. (12) is a factorization of an infiniteddimensional tensor, it is still a firite factorization. That is, the ranks Ri..... Ra are finite, and therefore the circuit representing the same factorization has sum unit having R.... Ra inputs (see Fig. 2). Very recent works have proposed to augment. the circuit definition (Def. 2) with integral units which, roughly speaking, encode sum over an infinite and uncountable nunber of inputs (Gala et al., 2024a;b). We can consider such PCs to encode cont inuous factorizations of a probability tensor, which can be though of as infinite-rank factorizations, For instance, consider the problem of factorizing a finite-dimensional tensor T e R4 xxxa, Instead of considcring a finitelyddimcnsional core tensor We e R in Tucker (Eq. (2)), we can use a function w: dZm(Z) - R over continuous variables Z = 12 where each Z, has domain dom (2,) = R. Similarly, we replace each factor matrix v x with a vector of I functions (5/5)= dom( Zz)) - / for all j. By doing so and since consists of continuous variables, we are in practice replacing the summations in Eq. (2) with a multivariate integral over Z. That is, we factorize T as
Rd [ w(1....., za) (2) ... f(d) (2a) dz. ddm(
(13)
Similarly, one can retrieve hierarchical versions of such continuous tensor factorizations, with applications for probabilistic modeling (Gala et al., 2024b). In case the integral in Eq. (13) is intractable to compute, quadrature rules can be applied as to approximate it. See Gala et al. (2024a) for the details.
In the following section (Section 4), we present a generic pipeline that can be used to build both finite- dimensional and infnite-dimensionall hicrarchical probability tensor factorizations as deep tensorized PCs (Def. 7). Before that, in the following opportunity box, we stress how circuits can also be used as alternative representations of probability distributions that do not correspond to probability lensor factorizations.
17

---

Published in Transactions on Machine Learning Research (02/2025)
Opportunity 6. More factorizations of alternative representations of distributions
Instead of explicitly encoding p(X) by modeling its PMF PDF one can instead encode its probability generating function, characteristic function or its cumulative density function. Circuits have been used to compactly represent these alternative representations of distributions. For instance, Yu et al. (2023) proposed to build circuits that encode charactoristic functions to represent and learn distribution over mixed discrete and continuous data domains. These characteristic circuits have also found application in causal probabilistic inference (Poonia al., 2024). Similarly to the correspondence between circuits and tensor factorizations shown in the previous sections, characteristic circuit be seen as a hierarchical factorization of a tensor encoding a characteristic function, i.c., factorization of tensor with complex entries that however still implicitly encodes a probability distribution.
Table 1: De-structuring circuit and tensor factorization architectures, and their implementa- tions, into simpler design choices conforming to our pipeline: which region graphs (Section 4.1) and sum-product layers to use (Section 4.3), and whether to apply folding (Section 4.4). New designs are possible by mix & matching these existing base ingredients. Furthermore, we propose new region graphs that deliver more efficient tensorized circuit: QG, QT-2 and QT-4, By leveraging tensor factorizations the weights of folded circuits, we propose two new sum-product layers: CP, CP$ and CPXS, Check mark v means that even if the original implementation of HCLTs does not implement folding as we describe it here, they achieve similar parallelism by custom CUDA kernels. In Appendix B present detailed discussion on the design choices of our pipeline that are implicitly made in each PC architecture.
PC ARCHITECTURE
RECION GRAPH
SUM-PRODUCT LAYER
FOLD
Poon&Domingos (Poon & Domingos, 2011)
PD
CPT
RAT-SPN (Peharz et al., 2020c)
RND
Tucker
X
EiNet (Peharz et al., 2020a)
RND,PD]
Tucker
HCLT (Liu & Van den Broeck, 2021b)
CL
CP
HMM/MPSB300 (Glasser et al., 2019)
CPT
BM (Han al., 2018)
LT
CPT
X
TTDE (Novikov et al., 2021)
LT
CPT
X
NPC² (Loconte al., 2024)
(LT, RND
{ (CPT, Tucker
TTN (Cheng et al., 2019)
QT-2
Tucker
x
RND, PD,, CL,QG, QT-2
Tucker,, CP, CP Yo
Mix & Match (our pipeline)
x
(CPS, cpxs FOLDV}
x (x, V}
4 How to Build and Scale Circuits: A Tensorized Perspective
We now have all the necessary background to start exploiting the connections between (hierarchical) tensor factorizations and (deep) circuits. In particular, in this section, we will show how we can understand and unify many- aany-apparentlyy different- ways build circuits (and other factorizations) in a single pipeline leveraging tensor factorizations as modular abstractions. By doing so, we can "disentangle" what are the key ingredients to build and effectively learn overparameterized circuits, i.e. circuits with very large number of parameters (Table 1).
Fig. 9 summarizes our pipeline: i) first, one builds RG structure to enforce the necessary structural properties (Section 4.1), then, ii) populates such template by introduiing units and grouping them inlo layers (Section 4.2), following the many possible tensor factorizations abstractions (Section 4.3), optionally, iif) these layers can be "foldod", i.c., stacked together exploit GPU parallelism (Section 4.4). Finally, the circuit parameters can be optimized by gradient descent or expectation maximization (Peharz al., 2016; Zhao et al., 2016).
18

---

Published in Transactions on Machine Learning Research (02/2025)
+
+
X1. X2
X X3
a
(2) Ue
W
W
X
X
X1
2
33
+
(i) Build a region graph.
(ii) Overparameterize & tensorize.
+
Figure Our pipeline for building overparameterized circuits. Given a (fragment of) region graph (i), we overparameterize it with sum, product and input units. In this case, the connections between sum and product units encode Tucker factorization (e.g., in Fig. 2). Then, we tensorize it by grouping units into layers (fi). In the final folding step, we can fuse together those layers that can be evaluated in parallel (iii.. To do so, we stack the parameter matrices w(!), ( into tensor W.
X
+
(iii) Folding.
4.1 Building and Learning Region Graphs
The first step of our pipeline is to construct RG (Def. 4). It specifies a hierarchical partitioning of the input variables according to which we build deep circuit architectures. In particular, PCs that are built out of RGs satisfying crucial structural properties such as smoothness and decomposability by design (and deructuredddecomppssally
the RG is a tree and has univariate leaves, see Section 2.2), which in turn guarantec tractable inference for many queries of interest (Section 2). RGs explicitly used to build PCs in some papers (Peharz et al., 2020c;a), but as show next, they can be implicitly found in many other PC and tensor factorization architectures. We also introduce novel way to quickly build RGs for images that are dataset-agnostic but exploit the structure of pixels.
Linear tree RGs (LT). A simple way to instantiate RG is by building partitionings that factorize variable at time. That is, given ordering over variables X, each i-th partition node factorizes its scope .X. into regions (X+(1)..... Xz(i-1)} and (X)(()) We call the resulting RG linear tree (LT) RG, and show an example for it case three variables in Fig. 3. The ordering of the variables can be the lexicographical one or depending on additional information such as time when modeling sequence data. This sequential RG the one adopted by chain-like tensor network factorizations, such as MPS, TT's or BMS (Pérez- Garcia al., 2007; Oseledets, 2011), as well as hidden Markov models (HMMs) when represented PCs (Rabiner & Juang, 1986; Liu al., 2023a).
Randomized tree RGs (RND). A slightly more sophisticated way build a RG is construct tree that is balanced. This can be done in datasel-agnoslic way randomly partitioning variables recursively. That is, the root region X recursively partitioned by randomly splitting variables in approximately even subsets, until no further partitionings introduced to build randomized and tensorized sum-product networks (RAT-SPNs) (Peharz et al., 2020c). A similar approach has been described by Di Mauro et al. (2017; 2021), with the difference that some randomly- chosen subsets of the data are also taken into account when parameterizing the circuit, thus entangling the construction of the RG with the circuit paramelerization.
possible. This approach, which label with RND, has been
Poon-Domingos construction (PD). One can devise other RG algorithms that are tailored for specific data modalities, but that are still Sataset-agnostic In the case images where variables are associated to pixel values, Poon Domingos (2011) proposed split them recursively performing horizontal and vertical cuts. However, the main drawback of this approach, labeled PD, is that it generally yields very deep circuit architectures that hard to optimize (Section 6), as it
form a deep hicrarchy of patches, by
19

---

Published in Transactions on Machine Learning Research (02/2025)
X11-X12-11 X21 X22 X23 Xan
Figure The quad graph (QG). We illustrate the quad graph RG delivered by Algo- rithm D.1 passing H = W = and Tree = False as input argu- ments. The region graph is wn- balanced as the image size (3x not a power of Differently from our quad trees (QTs), QGs have regions partitioned in more than a single way (e.g., the root region node), and regions can be shared among partitions. For ex- ample, in a QT, the top region could only be partitioned in a single way into two or four sub- regions, respectively called QT-2 and QT-4 region graphs.
X11-112113 X2222a
X12 X21 X22 Xa1 X31
X32
X X Xas
X11 X21 Xg2
X31
X1a
X
X11X12
X11
X21 X22
X22X22
X31
X32
X13
X
X11
X
X21
X22
considers all the possible ways to recursively split an image into patches whose number grows fast with respect to the image size. The PD RG has been extensively used in the circuit literature, e.g., for architectures like EiNets (Peharz et al., 2020a).
Novel RGs for image data: quad graphs (QG) and trees (QT). We want to devise RGs that are dataset-aguostic but still aware the pixel structure as PD, while at the same time not falling prey of the same optimization issues. Therefore, we propose a much simpler way to construct imago-tailored RGs that delivers smaller circuits that can achieve better performances, even when compared to RGs learned from data (see Section 6). Algorithm D.1 in the Appendix details construction. Similarly to PD, it builds RG by recursively splitting image patches of approximately the same size, but differently from PD it only splits them into four parts (a one vertical and horizontal cut) sharing the newly created patches. We call such RG quad-graph (QG). Fig. 10 shows an example of a QG RG for a 3x3 image.
Alternatively, one can obtain a tree RG by splitting the patches both horizontally and vertically, but without sharing patches. We call such tree RG quad-Iree (QT). Since regions of such RGs are associated to image patches, we can choose to partition them different ways. In particular, we will denote with QT-2 QT whose regions partitioned in two parts (bottom and top parts of the patch), and with QT-4 QT whose regions are partitioned into four parts (following quadrant division partitioning). With QT-2 retrieve tensor factorizations tailored for image-date used in prior work (Cheng et al., 2019).
Learning RGs from data. The approaches discussed so far do not depend on the training data. To exploit the data in the construction of RGs, one can test the statistical independence of subset of features inside a region node Y s X. This is the approach used in the seminal LearnSPN algorithm (Gens & Domingos, 2013), later extended many other works (Molina et al., 2018; Di Mauro et al., 2019). All these variants never mention a RG, but one is built implicitly by performing these statistical test and by introducing regions that are associated to different "chunk" of data obtained by clustering (Vergari et al., 2015). Alternatively, one can split regions according to some heuristics over the data that result in region nodes being shared (Jaini et al., 2018a). The same idea is at the base of the Chow-Liu algorithm to learn the tree-shaped PGM that better approximates the data likelihood (Chow & Liu, 1968b). The Chow-Liu algorithm (CL) can be used to implicitly build a RG as well, as done in many structure learning variants (Vergari et al., 2015; Rahman et al., 2014; Choi et al., 2011). more recent approach that leverages this idea and that generally yields state-of -hate-of-the-art performance first learns the Chow-Liu tree, then treats it latent tree model (Choi et al., 2011) that is finally compiled into PC (Liu & Van den Broeck, 2021b).
20

---

Published in Transactions on Machine Learning Research (02/2025)
Algorithm 1 overparamAnndTensoiiiRRRR, K) Input: a RG R over variables X, the sum layers width K, and the lype of inpul functions F.
Algorithm 2 SumProdLayer({; E2 K)
Input: Layers e,, l2 with width K and output width C.
Output: A composition of sum & product layers.
Output: A Lensorized circuit e over X.
procedure (parameterize Tucker)
E- From regions to layers 2: for each region Y postOrder ( do
1: L - emptyMap
2: Let W e BRCK2² be the sum layer parameters
8: return & compuling W (Zi) & (Z.))
3: if Y is partitioned into {(Z))) (() ) then
procedure (parameterizeCP)
4:
A - C 1 if Y = else K
5: Let Q(), Q E RC*K be the parameters
5:
return l computing (Q (Z.)) (Q R (Z2))
6:
for = 1 to N do
7:
f -
8:
A < A o (2)
Algorithm 3 (umLayer((44))
9:
[| < pop(A) if |A|-1 else SumLayer(A)
Input: Input layers {41) having scope Y and width K, with > L. Output: A sum layer.
10:
else
Y is a leaf region in R.
11:
4[ - InputLayer Y, K,F)
Let We (X(NK) be sum layer parameters
12:
return circuit having [ output layer
2: return & computing W(1l,, ((Y))
The construction of this hidden Chow-Liu tree (HCLT) exactly follows the steps in our pipeline, once one disentangles the role of the RG from the rest.
The construction of other PC and tensor factorization architectures mentioned so far (i.e., RAT-SPNs, EiNets, MPSs, BMs, etc) also follows the same patlern, and can be easily calegorized in our pipeline (Table 1). They not only differ in terms of the RGs they are built from, but also on the kind of the chosen sum and product layers. In the next section, provide generic algorithm that builds a tensorized circuit architecture from a given RG, given selection of sum and product layers encoding tensor factorizations.
4.2 Overparameterize & Tensorize Circuits
Given RG, the simplest way to build circuit is to associate single input distribution unit per leaf region, single sum per inner region, and single product unit per partition, and then connect them following the RG structure. This would deliver smooth and sparsely connected, and it is in fact the strategy that the many structure learning algorithms discussed in the previous section were implicitly using (Gens & Domingos, 2013; Vergari et al., 2015; Molina et al., 2018). We can adapt this strategy to the "deep learning recipe", and output instead an overparameterized circuit that is locally densely-coneected. With overparamettrization we refer to the process of "populating" RG with not one but many sum, product and input. units of the same scope. The resulting tensorized computational graph (Def. 7) has many more learnable parameters and lends itself to be parallelized on GPU, as we can vectorize computational units sharing the same scope as to form dense layers. Algorithm I details the overparameterization and tensorization process. The algorithm takes as input: a RG R, the type of input functions F (e.g., Gaussians), and the number of sum units K which governs the expressiveness of the circuit, or equivalently the rank of the factorization. 5 Furthermore, we can customize the choice of input layers as well as how to stack sum and product layers together, yielding many ways to build circuits with different degrees of efficiency and expressiveness.
circuit that is
Constructing input layers. The first step of Algorithm 1 consists of associating input units to leaf regions, i.e., regions that are not further decomposed. Leaf regions are often univariate, ie., of the form Y= for some variable X, e X. For each lcaf region over a variable X, we introduce K input units, cach computing a function ft: dxm(X,) - R. To guarantee the non-negativity of the output in monotonic PCs, fo are often chosen to be non-negative, e.g., by choosing them to be probability mass or density functions (Choi et al., 2020). However, one can possibly choose f. from a much wider set of expressive function familics, e.g., polynomial splines (de Boor, 1971; Loconte al., 2024), neural networks (Shao et al., 2020; Corrcia et al.,
5 As in a (hlerarchical) Tucker factorization, we can select different numbers of units, one for each layer, thus encoding Ki Kank factorization. For simplicity, we assume that K₃ K2 ... Kd-
21

---

Published in Transactions on Machine Learning Research (02/2025)
X1. X2. X₃
W
+
X2
Xa
W
W
Figure 12: A region node split into two partitionings ((x,,X): (Xal) and ((Xi): Xa)) of X2, is overparameterized using Tucker layers having parameters w w( e RK*," and with an additional sum layer pa- rameterized by w(3) RSx22)), for some S (right).
X
X
X2,Xx1 Xz) (above)
+
O
O
+
2023; Gala et al., 2024a;b) and normalizing flows (Sidheekh et al., 2023). See also Opportunity 4. Then, the input units can be tensorized by effectively replacing them with an input layer é: dom(X;) - R such that R(Xy); (X,) with e [K] can be computed in parallel (L11 in Algorithm 1). Next, sum and product layers are built. and connected according to the variables partitioning specified in the given RG.
4.3 Abstracting Sum and Product Layers into Modules
Alongside input layers, we introduced the other atomic "Lego blocks" for tensorized circuits in Def. 7: sum layers, Hadamard and Kronecker product layers. In the following, we will use these blocks to create composite layers that will act as further abstractions that can be seam- lessly plugged and CP (Fig. 16) layers. Each of these layers encodes a local factorization and stacks and con- efficiency. Note that given our semantics for tensorized layers, stacking these composite ab- stractions by applying Algorithm over a RG will always output tensorized circuit that is smooth and deaeeurrddddeccmppsabblle (Def. 8).
Algorithm 1. These composite layers include: Tucker (Fig. 11), CP (Fig. 15)
nects internal and product units in different. way to increase expressiveness
+
W
We start by considering composite layers that adopt the connoctivity of compu- tational units in the Tucker factorization, as shown in Fig. 2. This pattern introduced in architectures such as RAT-SPNs (Peharz et al., 2020c) and EiNets (Pcharz et al., 2020a). There, region node Y=X and partitioned into (Z,, Z2) is parameterized as layer l that is composition of a Kronecker product layer followed by sum layer, i.e., computing
X
Figure 11: Tucker layer
Y(Y) w (Z, (Z)))
(Tucker-layer)
where We RK is the parameter matrix for given number of units K, and l, are its input layers (in grey in Fig. 11), each computing a -- K-dimensional vector obtained via overparameterization and tensorization of region nodes over Z,, Zz, respectively. Algorithm 2 composes sum and product layers as to construct Eq. (Tucker-layer), and it is called to overparameterize the circuit (see L6-8 in Algorithm 1). However, note that the flexibility provided by Algorithm 1 allows us to define other possible parameterizations in Algorithum 2, without changing the rest of the algorithm.
Overparametcrizing multiple partitionings, the Mixing layer case. Some RGs can have multiple partitionings for a same region, as shown in Fig. 12. More formally, given a region node Y S X, we can split it into N different partitioning, i.c., {(Z) z (0) ) with Y z(d) Z for every i. This is the case of the PD RG used in EiNets (Peharz et al., 2020a), and the proposed QG (see Section 4.1 and Fig. 10). We illustrate an example of such RG in Fig. 12. The design adopted in EiNets to overparameterize them is to build an apporently special layer called mixing layer by Peharz et al. (2020a) computing
(() = Σ W: OY(Y
(Mixing-layer)
22

---

Published in Transactions on Machine Learning Research (02/2025)
where We E R denote the parameter matrix of L, and each & is layer that outputs K-dimensional vector. However, we observe that Eq. (Mixing-layer) can be computed by simple sum layer that already conforms to our Def. 7. In fact, Eq. (Mixing-layer) can be rewritten as E(Y) WI i (:YY), where W' EE [X((KK) is the parameter matrix obtained by concatenating N diagonal matrices {W along the columns, with W E RRKK for i [K]. This observation demystifies the need of treating mixing layers yet another type of layers, which happens to be the case in current EiNets implementations (Peharz et al., 2020a; Braun, 2021). Algorithm 3 specifies the construction of the generalization of the mixing layer as a single sum layer (used in L9 of Algorithm 1). Section 4.3 illustrates the overparameterization and tensorization of a region being dccomposed in more than one partitioning. Note that from our perspective it becomes clear that such sum layer does not necessarily increase the expressiveness, i.e., at the scalar unit level one could merge connected sum units as single sum unit. For this reason, in Section 6 we experiment with mixing layers whose parameter entries are fixed during learning." 6
N
4.4 Folding to Further Accelerate Learning and Inference
The final and optional step of our proposed pipcline (Fig. 9) consists of stacking together the layers that share the same functional form as to increase GPU parallelism. We name this step solding. Note that folding is only a syntactic transformation of the circuit, i.e., it does not change the encoded function and hence it preserves its expressiveness. This simple syntactic "rewriting" of a circuit can however significantly impact learning and inference performance. In fact, folding is the core ingredient of the additional speed-up introduced by FiNets (Peharz et al., 2020a) with respect to the same non-folded circuit architectures such as RAT-SPNs (Peharz et al., 2020c) which share with EiNets the other architecture details, e.g., the use of Tucker layers (see Table 1). As such, the difference in performance that is usually reported when treating RAT-SPNs and EiNets two different PC model classes (see e.g., Liu et al. (2023a)) must depend on other factors, such as the choice of the RG or a discrepancy in other hyperparameters used to learn those models, e.g., the chosen optimizer. By disentangling these aspects in our pipeline, we can design experiments that truly highlight which factors are responsible for increased performance (see Section 6).
Folding layers. To retrieve the folded representation of the Tucker layer (Eq. (Tucker-layer)), we need to stack the parameter matrices along a newly-introdueed dimension, which we call the fold dimension. Then, we can compute products accordingly to such extra dimension. For instance, given set { of Tucker layers having scopes {)))))== respectively, we evaluate them in parallel with a single folded layer computing a F K matrix and defined as
e <U x(rr),, Wnn: L1 (Un_Iz")) E2 (U., ). with n [F]
(Tucker-folded)
where Ei (resp. f2) denotes folded layer computing the F left (resp. right) inputs to e(x), each defined over variables zin) (resp. ) and each W.. E R is the parameter matrix of g(n), In other words, Wn:: n: is the n-th slice along the first dimension of a tensor W E Fxxx=² obtained by stacking together the parameter matrices of each Tucker layer. Since the same region node can possibly take part in multiple partitionings of other region nodes (e.g., see Fig. 9i), we might have folded inputs L,, 12 computing the same outputs. We illustrate an example of this in Fig. 9iii, which shows the folding of two Tucker sum-product layers sharing one input. In Appendix F, we report a pytorch snippet implementing a folded Tucker layer with an einsum operation. For this reason, while folding provides considerable speed-up when evaluating a tensorized circuit, it might come at the cost of increased memory usage depending on the chosen RG.
How to choose the layers to fold? It remains to decide how to choose the layers to fold together. The simplest way is traversing the tensorized circuit top-down (i.e., from the outputs towards the inputs) and to fold layers located at the same depth in the computational graph. However, note that we can also fold layers at different depth. For example, all input layers can be folded together if they encode the same input functional for all variables. This is the approach adopted in EiNets (Peharz et al., 2020a) and the one that will be used in all our experiments and benchmarks (soe Soction 6). However, note that this is
6 And we found that empirically this speeds up learning and does improve performances a bit.
23

---

Published in Transactions on Machine Learning Research (02/2025)
+
+
+
A
W
A
X
(b)
+
+
+
+
+
B
C
w
W(2)
B A (
C A (2)
+
+ A
X
X
(
(a)
(c)
Figure 14: Compressing Tucker layers into CP layers. Given a (Iragment of) tensorized circuit equipped with Tucker layers (a), we compress by computing a CP factorization for each parameter matrix w w(2), and W. By doing so, we recover a different parameterization given by the factor matrices of the CP factorizations, and the product layers now compute a Hadamard product of their inputs (b). Finally, we can simplify the circuit by collapsing consccutive sum layers (c). The circuit structure showed in (a) is typical of RAT-SPNs and EiNets architectures, while the one in (c) captures the connectivity in HCLTs, MPS/TTs, BMs and more (Table 1), since it interleaves Hadamard product and sum layers (e.g., MPS/TT in Fig. 8).
not regarded as the optimal way to fold layers, and different ways of choosing the layers to fold might bring additional speed-up and memory savings when tailored for specific architectures. While we do not investigate different ways of folding layers other than the one mentioned above, the disentanglement of the folding and overparameterization steps (Section 4.2) in our proposed pipeline will foster future work to rely the wide literature on parallelizing generic computational graphs (Shah et al., 2023).
5 Compressing Circuits and Sharing Parameters via Tensor Decompositions
In this section, we exploit again the literature of tensor factorizations to improve the design and learning of circuit architectures. We start by observing that as the parameters in circuit layers in our pipeline are stored large tensors (see e.g., Eqs. (Tucker-layer) and (Tucker-folded)) they can in principle be factorized again. And since factorizations are circuits (Proposition 1), in the end obtain several variants of circuit architectures and layers, some of which are new and offer an interesting trade-off between speed and accuracy (Section 5.2), while others are implicitly being used in the construction of existing circuits and tensor factorizations (Table 1). Again, we start from Tucker layers, with the aim of compressing a deep circuit using them, i.e. approximating it by using less parameters.
5.1 Compressing Tucker layers
Although expressive, Tucker layers in circuits require learning and storing K3 parameters, encoded in the matrix W e R in Eq. (Tucker-layer), which can be reshaped as the three dimensional tensor W e R More in general, by relaxing the assumption of binary RGs made so far, a Tucker layer taking input layers will be parameterized by N+1 parameters. To retrieve a more space efficient parameterization of Tucker layer, we propose to compress its parameter tensor W via rank- cononical polyadic (CP) factorization, which define below.
Definition 10 (CP factorization (Carroll & Chang, 1970)). Let T E g/xxxxxx be a d-dimensional tensor. The rank-R R comonical polyadic (CP) of T factorizes it as a sum of R rank-1 tensors, i.c.,
R
or in element-wise notation
U
(1)
(d)
(14)
where Vi) R x with [d] are factor matrices.
24

---

Published in Transactions on Machine Learning Research (02/2025)
Note that CP factorization can be represented circuit as it is special case of the Tucker factorization (Proposition 1). With this in mind, we proceed by decomposing the W E R parameter tensor of a Tucker layer via a rank-Rt CP factorization such that Rt < K, i.e.,
R
R Wisk R
W ar bjr Crr Σ
or in element-wise notation
ai byr
(15)
RxxR RRXR are newly-int roduced parameter matrices. This new parameterization requires only 3KR parameters and unlocks faster evaluation of Tucker layers. That is, we rewrite the function computed by a Tucker layer l in clement-wise notation as
where A, A,B,Ce
((Y) - A (B @ (c)))
(16)
where
l1 are imput layers to L having width K and scopes Zi Z2, respectively, Therefore, evaluating a compressed Tucker layer that has undergone the CP factor- ization requires time O(KR) R) (Eq. (16)), rather than O(K3) (Eq. (Tucker-layer). On top of this, we observe that if we use a CP factorization to all Tucker layers in PC, we will oblain a circuit in which sum and product layers are not alternated anymore. For example, starting from the Tucker layers in Fig. 14a, we would ob- tain new architccture where product layers can be followed by two sum layers, as in Fig. 14b, e.g., one parameterized by A (1) RK*R feeding another sum layer parameterized by B E R As we can always rewrite any compasition of con- secutive sum layers with a single sum layer parameterized by a product of matrices (c.g., by T ( e R)),), we can collapse the adjacent sum layers as to obtain the
+
+
(2)
Q(4)
Figure 15: CP layer. simplified architecture Fig. 14c. More formally, under such observation and by assuming that e,, l2 are also Tucker layers being decomposed, we can rewrite Eq. (16) as
((Y)
+ (Q (2(2))
(CP-layer)
where Q(1) Q(22 E R are parameter matrices of sum layers, such that Q = Q - C A (2) That is, we reduced the overall width of each layer from K the smaller R while still approximately comput- ing Tucker layer, by assuming that W was originally low-rank. From now on, we will refer Eq. (CP-layer) can use instead of Tucker layers in Algorithm 2
CP layer. This is new compositional abstraction to build tensorized circuits out of RG. For monotonic PCs, one can still recover the Tucker layer factor- ization above by replacing the CP factorization (Eq. (15)) with its non-negative version (Cichocki & Phan, 2009), which ensures the factors A, B, C and hence (1), Q(2) to be non-negative matrices. Furthermore, folded version of Eq. (CP-layer) can be obtained similarly to the one for Eq. (Tuckor-layer) (sce Section 4.4).
Finally, we introduce anot lype of layer which is very similar to the CP-layer above except that the Hadamard product is performed before the vector-matrix multiplication. We denote this sum-product layer as CPT, spelled CP-transpose or CP-T. Formally, CP layer l computes
Q
e(Y) (4)(()))) O Oz()))
(CPT
where Q E RRX The main difference between using CP and CPT layers is when Figure 16: CPT layer. these are applied on top of input layers, as there might be a slight difference in expressiveness, For instance, the product of two mixtures of Gaussians is different from a mixture of the product of two Gaussians.
Architectures such HCLTs are latent tree models (Choi et al., 2011) and such they be rewritten tensorized circuits using CPT layers (Table 1) plus one additional sum layer, as illustrated in Fig. 18. More specifically, since HCLIs are monotonic circuits, we can interpret each of the parameter matrices Q E R in Eq. (CPT-layee llyer) as conditional probability t of the form p(Zz Zz) with latent variables Z, Zj
The term CP indeed pun on the term conditional probability tables (CPTs) the Rayesian network terminology.
25

---

Published in Transactions on Machine Learning Research (02/2025)
Figure 18: PGMs can be com- piled as tensorized PCs. We show how the PGM in (a), a latent tree model (LTM), with latent variables Zi and observ- able variables X,, can be com- piled in the tensorized PC over X in (b) using input, dense, and CP layers paramelerized by the conditional probability tables of the LTM, following the compila- tion algorithm proposed by Liu & Van den Broeck (2021b).
22
7
+
O p(Z) +
X
7
Xs
M 2
O
(24122)
+
X4
p( XKx33 %2a
ptt 2
+
(a) Latent tree model
(b) Tensorized PC
attached to the latent tree model the HCLT is compiled from (as we mentioned in Section 4.1). In other words, the difference between these tensorized circuit architectures and others such as EiNets or RAT-SPNs translates to simply a CP factorization of parameters if one fixes the same RG. In Appendix we show that the same line of thought can be applied to the many tensorized PC architectures that have been developed far. That is, Appendix B further details how the tensorized PC architectures reported in Table 1 can be understood and built within our pipeline, by specifying which RG and sum and product layer composition to use (Tucker, CP or CP and whether to fold the computational graph or not. Next, we show how we can further exploit tensor factorizations as to build and compress folded tensorized circuit architectures.
5.2 Parameter Sharing by Tensor Factorizations
We now focus the problem of sharing parameters across layers in lensorized PC. We again exploit tensor factorizations for this task. Consider tensorized PC built out of a RG as per our pipeline (Section 4.2). It is reasonable to assume that layers located at the same depth might store a similar structure in their parameter tensors. For example, two distinct layers having adjacent pixel patches of the same size as scope may apply a similar transformation to their respective inputs, as we can assume the distributions of the two pixel patches be quite similar. If the RG is a perfectly balanced binary tree, folding the resulting circuit translates to folding layers located at the same depth, which are likely to share similar structure in parameter space. This motivates us to implement parameter sharing as factorization across folded layers.
Specifically, we start by compressing a folded Tucker layer (Eq. (Tuuker-folded)) and to retrieve a new layer that implements the aforementioned paramcter sharing, we again decompose its parameter tensor via a CP factorization (Def. 10). This time, we will have to decompose W E xFxxxx R ie,, the 4-dimensional tensor obtained by reshaping of the parameter tensor of a folded Tucker layer E, where F indicates the folding dimension. By applying a rank-R CP factorization such that It & K, we obtain that
W R
Σ d a o b,, Cr or in element-wise notation
Wnigh
Σ dnr
(17)
where B, CE kx and D E FxR, Note that A, B, C are independent of the fold dimension and are effectively shared among folds. By decomposing the parameter tensor in Eq. (Tucker-folded) as in Eq. (17) and by collapsing sum layers as done for the Tucker layer above, we can rewrite Eq. (Tucker-folded) as
(U__.''
= dr. ( (U._, ()))) (0 @ (U._zzz)) =.=zs)
n [F] (Cpe-layer)
where Q (1), Q(2) E RR do not depend on the fold dimension, and D E R However, we can go further in sharing parameters and drop the fold-dependent matrix D from Eq. (CpS-layer), hence effectively fixing it be matrix of ones. The reason is that its contribution can be "absorbed" by the matrices associated to the following sum layers (i.e., similarly to the "collapse" of consecutive sum layers shown in Fig. 14). We
26

---

Published in Transactions on Machine Learning Research (02/2025)
refer to this layer CPxs, Our experiments (Section 6) support this conjecture: experiment with both CP and CpXs, find they achieve comparable performances for distribution estimation. These new layers are a nice addition to the circuit literature, and possible inspiration for further layer designs.
Opportunity 7. Many new layers and circuit architectures
We rntrodueed Tucker, CP, CP CPs and CPXs as possible composite layers for circuits and tensor factorizations, and we provide Py'Torch snippets of them in Appendix However, one is limited such layers and can design in Def. 7, they be scamlessly plugged into Algorithm 1 to construct tensorized circuits. Our experiments (Section 6) show that the choice of RG and layer significantly impacts the performance of the resulting architecture (may it be time and memory requirements or accuracy as distribution ostimators), hence justifying further exploration of the design space of PC architectures. Lastly, we remark that one is not limited to pick the same composite layer for each node a RG, according to Algorithm 1. From the point of view of tensor factorizations, this would result in peculiar "Frankenstein" hierarchical tensor factorization that mixes different local factorizations, shown in Fig. 6. From an ML perspective, determining which layer structure to select for each RG node can be cast as neural archilecture search task (Ren et al., 2021).
as long they compositions of the building blocks outlined
tensor factorizations
Table 2: Distribution estimation results. We report the test-set bpd of our best architectures, QT-CP- 512 and QG-CP-512, and compare them against HCL.T (Liu & Van den Broeck, 2021b), RAT-SPN (Peharz et al., 2020c), SparsePC (Dang et al., 2022a), IDF (Hoogeboom al., 2019), BitSwap (Kingma et al., 2019), BBans (Townsend et al., 2019) and McBits (Ruan et al., 2021). SparsePC is structure learning algorithm for PCs that iteratively finetunes both structure and parameters of trained PC and can potentially be applied as post-processing step to the PCs we are learning with our pipeline. HCLT results are taken from Gala et al. (2024a). Dataset CELEBA* is preprocessed using the lossless YCoCg transform.
QT-CP-512
QG-CP-512
HCLT (CL-CP)
RAT (RND-Tucker)
Sp-PC
IDF
BitS
BBans
McB
MNIST
1.17
1.17
1,21
1.67
1.90
1.27
1.39
1.98
F-MNIST
3.38
3.32
3.34
4.29
3.27
3.47
3.28
3.66
3.72
EMN-MN
1.70
1.64
1.70
2.56
1.52
2.07
1.88
2.04
2.19
EMN-LE
1.70
1.62
1.75
2.73
1.58
1.95
1.84
2.26
3.12
EMN-BA
1.73
1.66
1.78
2.78
1.60
2.15
1.96
2.23
2.88
EMN-RY
1.54
1.47
1.73
2.72
1.54
1.98
1.87
2.23
3.14
QT-CP-256
QG-CP-128
CELEBA CELEBA
5.33
5.33
5.24
5.20
6 Empirical Evaluation: Which RG and Layers to use?
Destructuring modern PC architectures (as well as tensor factorizations) into our pipeline (Fig. 9) allows create new tensorized architectures by simply following mix & match approach (Table 1). At the same time, it helps understand what really matters between different model classes from the point of views of expressiveness, speed of inference and ease of optimization. We now in fact easily disentangle key ingredients such as the role of RGs and the choice of composite layers in modern circuit architectures, and pinpoint which is responsible for boost in performance. For example, HCLTs have been considered as one of the best performing circuit model architectures recent benchmarks (Liu et al., 2022; 2023a), but until now has not been clear why they were outperforming other architectures such as RAT-SPNs and EiNets. Within our framework, we can try answer that question by answering more precise questions: of their composite sum-product
is it the effect of their RG that is learned from data (Section 1), the
27

---

Published in Transactions on Machine Learning Research (02/2025)
layer parameterization (Section 5.1) or are other hyperparameter choices responsible? (spoiler: it is going to be the use of CP layers).
Specifically, in this section we are interested in answering the following three research questions following a rigorous empirical investigation. RQ1) What are the computational resources needed (time and GPU memory) at test and training time for some of the many tensorized architectures we can now build? RQ2) What is the impact of the choice of RG and composite sum-product layer on the performance of tensorized circuits trained as distribution estimators? RQ3) Can we retain (most of) the performances of pre-trained tensorized PCs using Tucker layers if we factorize these into CP layers as illustrated in Fig. 14a Fig. 14b? Note that we are not asking what is the impact of folding (Section 4.4), as we already know the answer: folding is essential for large-scale tensorized architectures. As such, throughout all experiments, we use folded tensorized circuits. We emphasise that the aim of our experiments is not to reach state-of-ther ahe results in distribution estimation, but rather to understand the role of the ingredients of tensorized circuit architectures. All experiments were run on a single NVIDIA RIX A6000 GPU with 48GB of memory. Our code is available at gjjhubbcomm/pprillooote ueniccrr-eii..
A new circuit nomenclature. We remark that HCLT, EiNets, RAT-SPNs, and all the other acronyms in Table 1 do not denote different model classes but just different architectures. They are instances of the same model class: smooth and pawpetuurdd-decoooppaae tensorized architecture as [sG]-ssum-product layor], possibly followed by K, the number of units used for overparameteriving layers as in Algorithm 1. Under this nomenclature, RAT-SPNs and EiNets will both be encoded as RND--ucker when they are both build with a random RG. When they are built with a Poon&Domingos RG, they will instcad be referred to as PD-Tucker, meanwhile HCLTs will become CL-CP.
circuits. In the following, we will denote a
Task & Datasets. We will mainly evaluate our architectures by performing distribution estimation on image datasets. We use the MNIsT-family, which includes 6 datasets of gray-scale 28 x 28 images -MIIST (LeCun et al., 2010), FASHIONMNIST (Xiao et al., 2017), and EMNIST with its 4 splits (Cohen et al., 2017) and the CelebA dataset down-scaled to 64 x 64 (Liu et al., 2015), which we explore in two versions: one with RGB pixels and the other with pixels preprocessed by the lossless YCoCg color-coding (Malvar & Sullivan, 2003), as recent results suggested that such a transform can greatly lower bpds.* R Furthermore, tabular data with continuous variables. In particular, we will evaluate different tensorized layers by performing density estimation on 5 UCI datasets, as they are typically used to evaluate normalizing flows (Papamakarios et al., 2017). We report the statistics of the UCI datasct in Table E.5.
we perform experiments
Parameter optimization. We train circuits to estimate the probability distribution that is assumed to have generated the images, considering each pixel as a random variable. As such, the input units in the circuit represent Categorical distributions having 256 values. For RGB images, we associate three Categorical distribution units per pixel (one per color channel). Instead, for the 5 UCI datasets (Table E.5), we use input units representing univariate Gaussian distributions, and we learn both the mcans and the standard deviations. We perform maximum likelihood by stochastic gradient ascent, i.e., want to maxinize the following objective
((B = [log(c(x)) - log(Z),
(18)
XEB
where Z = Ex c(x) is the partition function of the PC c², and B a batch of training data. After some preliminary experiments, we found that optimizing PCs with Adam (Kingma & Ba, 2015) using a learning rate of 10-2 delivered, settled to reparameterize the circuit sum parameters via clamping and sctting c = 10-19 (Eq. (9)) after each optimization slep as to keep them non-negative, as it was giving the best learning dynamics among all possible reparameterizations (Section 3.2). In the following, we will summarize our findings when answering RQ1-3, while distilling recommendations for practitioners on how to build and learn circuits.
average, the best performing models for the datasets
considered. We also
We take this evidence from Liu al. (2023xbb), which use however lossy variant of the YCoCg transform that unfortunately artificially inflates likelihuods. As such, their bpds for PCs are not directly comparable with ours, nor with the other deep generative models in their tables. We confirmed this issue in their evaluation protocol via personal communication. 9 After training, one can efficiently "embed" the norma mimaaiizaiinn constant the parameters of a PC, effectively renormalixing them (and thus yielding a partition function Z equal to 1), as detailed by Peharz et. al. (2015).
28

---

Published in Transactions on Machine Learning Research (02/2023)
Test Time (ms)
Train Time (ms)
Test Memory (GB)
Train Memory (GB)
10a
40
QT-CP
15-
QT-CPS
QG-CP
10a
10
QG-Tucker
QG-CPS
10a
20
PD-CP
PD-Tucker
101
10
PD-CP
10
29
2
25
2
2
24
2
2
2
2
2
2
2
2
2
2
2
2
2
2
K
K
Figure 19: Benchmarking the role of RGs and composite layers in tensorized circuits. We report the average time (ms) and GPU memory usage (GiBs) to process a batch of 128 samples from MNIST for different tensorized architectures- listed in the legend on the right- different values of K (x-axis). The stats reported for both test and training scenarios, where for training one has to expect additional overhead from performing gradient ascent.
RQ1) Benchmarking time & space for different tensorized architectures. For these experiments, we consider the following RGs: PD, as commonly used in architectures such as RAT-SPNs and EiNcts, and the two novel light-weight and data-agnostic RGs we introduced in Section 4.1, QTs 10 and QGs We do not consider RND as it is usually just a balanced binary tree (Peharz et. al., 2020c), and as such would yield the same time and memory performance a QT. For the same reason we do not consider CL as they are tree RGs that end up being quasi- balanced after being rooted." !I For layers, we consider Tucker (Eq. layee)r-layerr). CP (Eq. (CP-layer)), CPS (Eq. (Cys-layer) and Cpxs (Section 5.2).
In Fig. 19, we report the average time and peak GPU memory required to process data batch from MNIST for several tensorized PC architectures built by mixing & matching different RGs and type of sum- sum-product layers mentioned above, when possible on our GPU budget. For each architecture, we vary the model size by varying K, the number of units for each layer, in [2') We observe that the QT and QG region graphs deliver more scalable architectures than those based on the commonly used PD which is consistently slower and uses more memory. At the same time, one can see that CP and CP$ layers scale more gracefully: CP can accommddate K 20 with QT as a RG and CP8 even larger values of K, up to 213 with QG well. Doing this is instcad computationally impractical for Tucker layers on our GPUs, which allow only for K = 128 al most. We underline that this is expected as models using Tucker layers have more parameters than those using CP layers for the same model size K. This also explain why the architecture QT-Tucker is missing: QTs iteratively split images in 4 parts (Algorithm D.2) and therefore appling Tucker layers would require O(K+) parameters for such architectures, which is unfeasible even for K= 16 on our GPUs.
We emphasise that non-folded versions of these architectures, e.g. RAT-SPNs (Peharz et al., 2020c), can be orders of magnitude slower, hindering both learning and deployment in practice. In Fig. E.1, we show the results of the same benchmark reported in Fig. 19 but for the CELEBA dataset, which is more challenging because it is equivalent to perform distribution estimation
much higher dimensional space (12, 288 64 x 64 x 3 instead of 784 = 28 x 28 x 1)." From this additional experiment, we conclude that even in higher dimensions the scaling trend of RGs and layers is the same. Finally, in Fig. E.3, we zoom on a comparison between Cp$ and Cpxs, There, we show that for the same choice of RG and K, CP$ and CPXS layers require the same time/space resources as expected, with CPXS only being slightly faster training-time
Takeaway 1.
QT and QG should be preferred to PD as RGs if we want to scale circuits, with the former being more scalable than the latter. Layer-wise, CP layers scale, as expected, to larger values of K than Tucker layers and for even larger layers paramoter sharing (CPS, CPXS) recommended.
10 TTrroughout experiments, will refer QT-4 simply QT.
The root is chosen to the barycenter of the graph to increase parallelism (Dang al., 2021; 2022c). Note that for RQ1, all image datasets with the same resolutions would yield the very same results.
29

---

Published in Transactions on Machine Learning Research (02/2025)
Mnist
Fashion Mnist
CelebA
1.40
6.2
1.35
6.0
QT-CP
3.7-
QT-CPs
Test bpd
1.30
3,6
5.8
QG-Tucker
QG-CP
QG-CPS
5.6
PD-CP
PD-Tucker
3.4
PD-CP
5.4
3.3
16
32
64
128
256
512
16
32
64
128
256
512
16
32
64
128
256
K
K
Figure 20: Overparameterizing tensorized architectures delivers better performing models when using QTs and QGs, but not when using PDs. We report the test-set bpd (y-axis) at different values of K (x-axis) for MNIST (Icft), FASHIONMNIST (middle) and CELEBA (right) averaged over 5 runs for different tensorized architectures, which we report in the legend on the right. We keep the mixing layers in QG- and PD-based models fixed and normalized. We use batch size of 256.
RQ2) Accuracy as distribution estimators. We now test our tensorized PCs as distribution estimators and we consider our mixed&matchee architecture from RQL. For each architecture, we vary the model size by varying K, the mumber of units for each layer, in {16, 32, 64, 128, 256, 512] for the MNIST family and up to 256 for CELEBA. To assess the effect of learning RGs from data, we compare against HCLTs (CL-CP in our nomenclature) as reported by Dang et al. (2022a). We use a batch size of 256, and train for at most 200 epochs stopping training if the validation ligelikel does not improve after 5 epochs. We use the average test-set -ermmieinim (bpd) as the evalutation criterion, i.e. (Dd -(D, c)/(d- log2), where d is the number of features in dataset DD and L is defined as in Eq. (18).
In Fig. 20 we report the average test-set bpd on MNIST, FASHIONMNIST and CELEBA. An immediate visible pattern emerges when comparing the architectures w.r.t. the choice of RG: Both QT- and QG-based architectures outperform those based on PD, and also manage to scale to larger datasets like CELEBA. On average, the best performing architectures are those built out of QGs. This expected as such RGs, different from QTs,, allow different partitionings for a same region (and therefore require the usage of mixing layers as discussed in Eq. (Mixing-layer)) The PD region graphs, despite being DAG-shaped as QGs, deliver underperforming tensorized architoctures, suggesting that bigger models, while being more expressive, are harder to train, a behavior also noted by Liu et al. (2023a). This is particularly evident looking at the trend of PD-based architectures on FASHIONMNIST.
In Table 2, we compare our best performing architectures, with other statc-of-the-art models even outside the circuit literature. Our architectures deliver close-to state-of-the-arl results, and outperforms some VAE- and blow- models. When compared with RGs learned from data, as it is the case for HCLT, we note that our simpler, data-agnostic alternatives, QT's and QGs, perform equally well or better. Using them instead of HCLTs avoids the quadratic cost to learn the corresponding Chow-Liu tree (Dang et al., 2021).
As for the choice of type of sum-product layer, Tucker and CP layers deliver very similar performance on PD. We conjecture that this is due to PD being harder to train in general, as for other RGs the trend changes. In fact, with QT and QG, we observe that Tucker delivers the best bpds for the smallest values for K. Scaling to larger Ks impractical however. CP and variants not only scale better (see RQ1 and Fig. 19), but are able to deliver the best bpds for larger K. As expected, CP consistently outperforms CPS having more learnable parameters. However, if one has to privilege time over accuracy, CPS can be a useful alternative. Finally, we report results for CpXS layers and learnable mixing layers in Appendix E, along with the results showed in Fig. 20 in tabular form. We confirm that CPS and CPXS layers are equivalently accurate and that one does nol have to learn mixing layer parameters in tensorized PCs with DAG-shaped RGs (Section 4.3). All these conclusions carry over also to a larger image dataset such as CELEBA, with or without the lossless YCoCg color-coding.
Density estimation on tabular datasets. Finally, we perform density estimation experiments on UCI datasets (Table E.5), and compare the results achieved by tensorized PCs constructed by our pipeline by
30

---

Published in Transactions on Machine Learning Research (02/2025)
Table 3: Tucker layers are harder to scale than CP layers on high-dimensional UCI datasets. We show the best average test log-likelihoods achieved by normalizing flow models (top) and tensorized PCs that can be instantiated from our pipeline (bottom). See main text for their description. Tensorized PCs obtained by paramcterizing random binary tree RGs (Section 4.1) with CP (RND-CP) perform better higher-dimennsonal datasets Hepmass and MiniBooNE than those with Tucker layers (RND-TUCKER) while the latter have an advantage on lower- diver-dimensional datasets such as Power and Gas. For RND-CP and RND-TUCKER, we report the layer width (K) of the best performing model as a subscript of the log- likelihoods. Fig. E.5 shows training and test log-likellng log-likelihoods achieved by varying the layer width K. Details in Appendix E.1.
Power
Gas
Hepmass
M.BooNE
BSDS300
MADE (Germain et al., 2015)
-3.08
3.56
-20.98
-15.59
148.85
RealNVP (Dinh et al., 2017)
0.17
8.33
-18.71
-13.84
153.28
MAF (Papamakarios et al., 2017)
0.24
10.08
-17.73
-12.24
154.93
NSF (Durkan et al., 2019)
0.66
13.09
-14.01
-9.22
157.31
Gaussian
-7.74
-3.58
-27.93
-37.24
96.67
EiNet-LRS (Sidheekh et al., 2023, RND-Tucker)
0.36
4.79
-22.46
-34.21
TTDE Novikov et al. (2021, IT-CPP
0.46
8.93
-21.34
-28.77
143.30
RND-CP
0.28256
5.01256
22.5264
30.69
120.8264
MND-Tucker
0.52
8.41256
-23.4732
-31.30s
119.0964
parameterizing a RND RG (Section 4.1) with either CP or Tucker layers. To give context to our results, we show the average Lest. log-likelihoods achieved by normalizing flow models (Papamakarios al., 2021) that are often evaluated on UCI datasets: MADE (Germain et al., 2015), RealNVP (Dinh al., 2017), MAF (Papamakarios et al., 2017) and NSF (Durkan al., 2019). As additional baselines, show results of other PCs supporting tractable marginalization: single multivariate Gaussian, Einsum networks (Peharz et al., 2020a) with input layers encoding flows (EiNet-LRS) (Sidheekh et al., 2023), and TTDE (Novikov et al., 2021). We emphasize that both EiNet-LRS and TTDE can be built using our pipeline and characterized with our nomenclature, the former as RND RGs parameterized by Tucker layers, and the latter as LT RGs parameterized by CP layers (Table 1). Table 3 shows that CP layers to deliver better performances than Tucker layers on high-dimensional UCI datasets and therefore in the case of deeper tensorized PCs. On the other hand, Tucker layers outperform CP layers on the lower-dimensional UCI datasets. We believe this is due the parameters of Tucker layers being more difficult to train and scale, similarly to observation for MNIST and FASHIONMNIST in the case of QG RGs in Fig. 20, We further detail in Appendix E.1 the experimental setting, and show in Fig. E.5 the results achieved by varying the layer width K.
Takeaway 2.
In the case of image datasets, our recommendation for a go-to architecture is QG-CP-K, with the largest possible K one can squeeze in their GPU memory. If computational resources are not enough, As a general (rend, the simpler the
one can trade-off accuracy with speed and use QT-(CP,CPS)- architecture the easier training and scaling are. This is also suggested by our results on UCI datasets, where the simpler CP layers can perform better for high-dimensionall datasets than Tucker.
RQ3) Compressing circuits with Tucker layers. For our last research question, consider the problem when trained circuit with Tucker layers is given, and want to compress it into smaller using CP layers by using our compression pipeline as illustrated in Fig. 14a and Fig. 14b. With this in mind, we investigate the change in performance, if any, w.r.t. the number of tunable parameters. Specifically, for each folded Tucker layer (Eq. (Tucker-folded) in the given circuit, parameterized with a tensor W of shape Fx Kx Kx K we compress each tensor slice W fur by performing non-negative (NN) CP factorization via alternating least squares (Shashua & Hazan, 2005). This optimization eventually delivers a tensor W of shape Fx3x Rx K for R-ranked factorization.
31

---

Published in Transactions on Machine Learning Research (02/2025)
QG-32 Mnist
PD-64 Mnist
QG-32 Fashion Mnist
PD-32 Fashion Mnist
QG-32 CelebA
1.8
3.80
bpd
1.6
.42
4.0
6.5
1.4
.40
6.0
.38
1.2
2
8
16
32
8
16
32
64
2
8
16
32
1
16
32
1
2
8
16
32
R
R
Tucker
NN-CP
NN-CP + Train
-0- Random + Train
Figure 21: Compressing Tucker layers into CP layers (Fig. 14a Fig. 14b) can yield smaller and accurate models as seen when we performing non-negative (NN) CP factorization via alternating least squares (Shashua & Hazan, 2005). In each plot, we report the bpd of a pre-trained Tucker-layered PC (dashed blue line), whose RG, size K and dataset on which it was trained on are detailed at the top. We report the bpd of several R-ranked NN-CP factorizations of such PCs (red curves), which we then use as initialization for further fine-tuning (green curves). Finally, we report the bpd of Tocker-compreseed PCs (Fig. 14b) trained from a random initialization of their parameters (yellow curves).
We sketch the results of our invostigation in Fig. 21. As expected, taking a pre-trained Tucker-layered PC (blue dashed line) and compressing its parameters via NN-CP factorization leads a similar--erffrrmnng model as the rank R of the approximation increases, as shown by the bpd trend of the red curves in Fig. 21, Interestingly, we observe key difference between the two region graphs utilized. For tensorized PCs based PD region graphs, even rank approximation (i.e. R = 1) leads to relatively small bpd loss, while this is not the case for PCs built out of QGs. We conjecture that PD-based PCs have parameter tensors that are of much lower rank than QG-based PCs, and that very deep PCs learn low-rank parameter matrices.
Next, we investigate whether we can use these compressed models as an effective initialization scheme for smaller circuits, which we further train (fine-tune) maximize the training data likelihood (Eq. (18)). Again, we see different trend when comparing w.r.t. the region graph used, as shown by the bpds encoded as green curves in Fig. 21. Specifically, for PD-based PCs such fine-tuning leads quick overfitting already in the first optimization steps, leading to much higher bpds on test data. In contrast, fine-tuning QG-based PCs leads to models that consistently match or even outperform the original Tucker-based PCs (blue dashed line), i.e., we observe green curves consistently being below red curves and crossing the dashed blue lines.
As an additional baseline, we use the architecture these compressed models (Fig. 14b) but train them from scratch: starting from a random initialization of its parameters. Fig. 21 illustrates that the NN-CP initialization can be better than random one it leads to better performing models when using QG RGs (yellow curves over green curves). This trend flips when using PD region graphs (yellow curves below green curves), again signaling that much information for these models could be stored in the RG rather than in the parameters of the circuit. This, in turn, suggests that while new hierarchical factorizations with highly intricate RGs but very low-rank inner tensors are possible, they might be harder to learn effectively.
Takeaway 3.
Deep circuits encode distributions in highly-structured factorizations whose parameters can be effec- tively further compressed, e.g., by NN-CP factorizations. This yields simple and effective procedure to distill smaller tractable model from a larger one: compress each layer of the latter, then fine-tune the former by -ekiimum-likelhoood estimation.
7 Additional Related Work
In the previous sections, we surveyed and bridged the literature of circuit representations and tensor fac- torizations, and as such we have already reviewed several related works from both communitics. Now, we discuss works that partially tried establish this connection in the past, by trying to connect probabilistic graphical models.
32

---

Published in Transactions on Machine Learning Research (02/2025)
Tensor networks and PGMs. TNs (Orás, 2013) are widely used to model many-body systems in physics and quantum mechanics (Schollwoeck, 2010), and have been used to simulate quantum computations on classical hardware (Markov & Shi, 2008). They have been applied more recently for machine learning applications (Stoudenmire & Schwab, 2016; Han et al., 2018; Efthymiou et al., 2019; Bonnevic & Schmidt, 2021). As they essentially an alternative formalism for probabilistic graphical models over discrete variables (Koller & Friedman, 2009), people have started drawing connections between the two formalisms. For example, Bonnevie & Schmidt (2021) connects non-negative MPS/TTss to PGMs and offers routines for probabilistic reasoning. Similarly, Glasser et al. (2020) explores the same connection, but instead of drawing TNs as PGMs, they draw them as factor graphs (Kschischang et al., 2001).
Interestingly, these works are not aware of the latent variable interpretation of non-negative factorizations (Section 3.1) as they miss the connection through circuits. For the same reason, they are limited to au- toregressive sampling (Opportunity 3). To the best of our knowledge, this latent-variable perspective has been (re)discovered only very recently in this concurrent work by Ghalamkari et al. (2024) who proposes the classical expectation-maxiiiaalll (EM) algorithm to learn them. EM is consolidated way to learn the parameters of circuits (Peharz et al., 2016; 2020a) by maximun likelihood.
Instead, by representing non-negative tensor factorizations as monotonic PCs, we effortlessly unlock the developed theory and algorithms required to perform complex probabilistic inference, with possible appli- cations in lossless compression (Liu et al., 2022), neuro-symbolic Al with correctness guarantees (Ahmed et al., 2022) and constrained text generation (Zhang et al., 2023). Moreover, results about the succinctness or expressive efficiency of these factorizations (Glasser al., 2019) have been used recently to prove circuit complexity lowerbounds (Loconte et al., 2024; 2025). Finally, Loconte & Vergari (2025) took inspiration from canonical forms in tensor networks (Schollwoeck, 2010; Bonnevie & Schmidt, 2021) to parameterize normaiy-n squared circuits generalizing squared MPS/TTs and TTNs (Section 2.4), and to devise a more efficient marginalization algorithm within the circuit language.
Probabilistic circuits and PGMs. The modern formulation of PCs has been introduced for the first time in (Vergari et al., 2019b) as a unifying framework for several existing tractable probabilistic models (TPMs) including arithmetic circuits, (Darwiche, 2001), probabilistic decision graphs (Jaeger, 2004), and-or graphs (Marinescu & Dechter, 2009), cutset networks (Rahman et al., 2014), sum-product networks (Poon & Domingos, 2011) and more (Choi et, al., 2020). The aim of PCs has been to abstract away from the different syntaxes and model formalisms of the above TPMs and focus on structural properties that enable tractable inference in each. Non-negative tensor factorizations and tensor networks have been underlooked in this effort so far. Several ways to compile discrete PGMs into PCs (or one of the above formalisms) have been devised in the past (Oztok & Darwiche, 2017; Shen et al., 2016; Choi et al., 2013). These compilation techniques yield sparse deterministic circuits, and only recently PCs have started in code (Peharz et al., 2020c;a; Liu & Van den Broeck, 2021b) and then formally (Loconte et al., 2024) as tensorized architectures. Perhaps this lack of tensorized compilation targets has hidden the connection between PCs and matrix and tensor factorizations. The closest connection we are aware of can be found in Jaini et al. (2018b): they bridge sum-product networks to hierarchical mixture models and HMMs and hint at a connection with tensorial mixture models (Sharir et al., 2017) a variant of hierarchical Tucker (Def. 5).
be represented first
Matrix factorizations, circuit complexity, and tensor networks expressiveness. Finding lower bounds to the rank of mairix factorizations can be used as proxy to prove lower bounds to the size of circuits satisfying particular structural properties (de Colnet & Mengel, 2021). Proving an exponential (w.r.t. the number of variables) size lower bound for class of circuits shows limitation on which functions they can compute in polynomial time and number of parameters, thus allowing us to preciscly separate circuit classes in terms of their expressiveness ( (Valiant, 1979; Martens & Medabalimi, 2014). Recently, lower bounding the non-negative rank (Gillis, 2020) and the square root rank (Fawzi et al., 2014; Lee & Wei, 2014) of matrices has been used to draw an expressiveness hierarchy of classes PCs with negative real and complex-val valued parameters for distribution estimation (Locoute et al., 2024; 2025). Since circuits generalize many tensor network factorizations (see Section 2.4), showing size lower bounds for class of circuits can be used to show size lower bounds for tensor networks regardless of their structure, e.g. shown by Loconte et al. (2025) in generalizing a known rank lower bound for Born machines obtained by squaring a MPS/TV TT with real-valued tensors (Glasser et al., 2019).
33

---

Published in Transactions on Machine Learning Research (02/2025)
8 Conclusion
In this paper, we laid the foundations to connect two communities in ML that developed independently but are sharing many research directions: circuits and tensor factorizations. Despite their apparently different syntax, the way they are usually presented, and the tasks in which they are commonly employed, these two formalisms significantly overlap in semanties and potential applications. We create this bridge bet communities by first establishing formal reduction of popular tensor factorizations to circuits in Section 2.
We hope this can propel research on how to design more and more scalable low-rank parameterization for probabilistic inference. To this end, we highlighted a number of possible future avenues for the matrix and tensor factorization communities that leverage the connection with circuits we established: designing hicrarchical factorizations with non-tree structures (Opportunity 1); using the property-driven calculus that circuits offer automatically derive tractable algorithms in compositional way (Opportunity 2); treat non- negative (hicrarchical) factorizations as deep latent variable models (Opportunity 3); devise factorizations over non-discrete and non-linear input spaces (Opportunity 4); embed logical constraints to realize neuro- symbolic systems that can reason with symbolic knowledge (Opportunity 5); devising alternative ways to compactly encode distributions, going beyond probability masses or densities (Opportunity 6); as well as devising flexible factorizations by changing only the structure of (somc) layers in a circuit representation (Opportunity 7).
From the point of view of the circuit community, we leveraged this connection to systematize and demys- tify the construction of modern tensorized and overparameterized circuits (Section 4). We proposed single pipeline that generalizes existing (lensor factorization and circuit) architect ures and introduced a new nomen- clature, based on the steps of our pipeline, to understand old but also new architectures that can be created by mixing& & matching these steps (sec Table 1). Our empirical analysis of popular ways to combine these ingredients highlights how lower-rank structures can be easier to learn and useful to compress higher-rank layers (Section 6). Finally, we distilled our findings clear-cut recommendations TaaioonnsSSaaaa (Takeaways to 3) for practitioners that want to learn and scale circuits on high-dimensional data, and we hope this can foster future rigorous analysis.
Broader Impact Statement
This work is fundamental research in probabilistic modeling and reasoning and as such the algorithms and architectures discussed here can impact many possible downstream applications, in ways that go beyond our control. For example, circuits, or tensor factorizations, could be used computer vision classifiers to amplify the bias already encoded in non-curated datasets or be used in safety-critical applications without eliciting valid safety requirements. Since it is hard to foresce all possible future misuses, urge practitioners to pay attention to concrete problematic uses of our methodologies: use the time that tractable models save while performing inference to reflect on the direct impact your application can have.
Author Contributions
AV and AM devised the original idea of tensorizing and compressing circuits in a unified pipeline. This has yielded preliminary workshop paper whose content can be traced to Sections and 5. AV and GV wrote the workshop paper and AM designed and run its experiments, which constituted the basis for the experiments in Section 6. LL traced the theoretical connections with tensor factorizations and tensor networks, and lead the writing of all sections in the journal paper with AV. AV and LL are responsible for designing and drawing all circuit pictures in TikZ, with the exception of Fig. 18 done by GG who also provided feedback for several plots. GG simplified the algorithmic pipeline, wrote the sampling algorithm in Appendix C, produced Appendix F, and designed new experiments. GG and AM re-run and extended the workshop experiments adapt them to the journal version, and GG wrote Section with AV. EQ, RP and CdC critically read the manuscript. AV supervised all the phases of the project and provided feedback.
34

---

Published in Transactions on Machine Learning Research (02/2025)
Acknowledgments
We would like to acknowledge Nicolas Gillis and Grigorios Chrysos for providing feedback on an early draft of the paper. AV wants to thank Tain Murray for forwarding an email from Raul Garcia-Patron Sanchez inquiring about tensor networks and ML, and the latter for many following discussions about tensor networks. The Eindhoven University of Technology authors thank the support from (i) the Eindhoven Artificial Intelligence Systems Institute, (ii) the Department of Mathematics and Compuler Science of TU Eindhoven, and (iii) the EU European Defence Fund Project KOIOS DEDF-2021-DIIHI BELLL-IIGT----L---OEEE R-F-LOOOOSS This project has received funding from the European Union's 's EIC Pathfinder Challenges 2022 programme under grant agreement No 101115317 (NEO). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or European Innovation Council. Neither the European Union nor the European Innovation Council can be held responsible for them. AV was supported by the "UNREAL: Unified Reasoning Layer for Trustworthy ML" project (EP/ (EP/YY23838/1) selected by the ERC and funded by UKRI EPSRC.
References
Kareem Ahmed, Stefano Teso, Kai Chang, Guy Van den Broeck, and Antonio Vergari. Semantic probabilistic layers for neuro-symbolic learning. In Advances in Neural Information Processing Systems 35 (NeurIPS), volume 35, pp. 29944-29959. Curran Associates, Inc., 2022.
Magda Amiridi, Nikos Kargas, and Nicholas D. Sidiropoulos. Low-rank characteristic tensor density es- timation part i: Foundations. IEFE Transactions Signal Processing, 70:2654-266 22688, 2022. doi: (..1009/SSP2202..111
Atharva Awari, Harrison Nguyen, Samuel Wertz, Arnaud Vandaele, and Nicolas Gillis. Coordinate descent algorithm for nonlinear matrix decomposition with the relu function. arXiv preprint, 2024.
Ivana Balazevic, Carl Allen, and Timothy M. Hospedales. Tucker: Tensor factorization for knowledge graph completion. In EMNLP-IJCNLP, pp. 5184-5193. Association for Computational Linguistics, 2019.
Jacob D. Biamonte and Ville Bergholm. Tensor networks in a nutshell. arXiv: Quontum Physics, 2017.
Christopher M. Bishop and Nasser M. Nasrabadi. Pattern recognition and machine learning. J. Electronic Imaging, 16:049901, 2006.
Rasmus Bonnevie and Mikkel N. Schmidt. Matrix product states for inference in discrete probabilistic models. Journal of Machine Learning Research, 22:187:1 187:48, 2021.
Steven Braun. Simple-einet: An EinsumNetworks Implementation, 2021. URL https://github. com/ Srauu-steveenssmppeeeeeeee
Diego Calanzone, Stefano Teso, and Antonio Vergari. Logically consistent language models via neuro- symbolic integration. In The Thirteenth International Conference on Learning Representations (ICLR), 2025.
J. Douglas Carroll and Jih-Jic Chang. Analysis of individual differences in multidimensional scaling via an n-way generalization of "eckart-young" decomposition. Psychometrika, 35:283-31 -19,, 1970.
Mark Chavira and Adnan Darwiche.
On probabilistic inference by weighted model counting. Artificial
Intelligence,, 172(6-7):772 (7997) 2008.
Song Cheng, Lei Wang, Tao Xiang, and Pan Zhang. Tree tensor networks for generative modeling. Physical Review B, 99(15)1155131, 2019.
Arthur Choi, Doga Kisa, and Adnan Darwiche, Compiling probabilistic graphical models using sentential docision diagrams. In Symbolic and Quantitative Approaches Reasoning with Uncertainty: 12th European Conference, ECSQARU 2013, Utrecht, The Netherlands, July 8-10, 2013. Proceedings 12, pp. 121-132. Springer, 2013.
35

---

Published in Transactions on Machine Learning Research (02/2025)
Arthur Choi, Guy Van den Broeck, Adnan Darwiche, Qiang Yang, and Michael Wooldridge. Tractable learning for structured probability spaces: A case study in learning preference distributions. In 24th International Joint Conference on Artificial Intelligence (IJCAI), volume 2015, pp. 2861 2868. LJCAI, 2015.
Myung Jin Choi, Vincent YF Tan, Animashree Anandkumar, and Alan S Willsky. Learning latent tree graphical models. Journal of Machine Learning Research, 12:1771-1812, 2011.
YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unilying framework for tractable probabilistic modeling. Technical report, University of California, Los Angeles (UCLA), 2020.
C. K. Chow and C. N. Liu. Approximating discrete probability distributions with dependence trees. 1EEE Transactions on Information Theory, 14(3):462-467, 1968a.
CKCN Chow and Cong Liu. Approximating discrete probability distributions with dependence trees. IEEE transactions on Information Theory, :4(3):462 467, 1968b.
Andrzej Cichocki and Anh Huy Phan. Fast local algorithms for large scale nonnegative matrix and tensor factorizations. JEICE Trans. Fundam. Electron. Commun. Comput. Sci., 92-A (3)770777877 2009.
Andrzej Cichocki, Rafal Zdunek, and Shun-ichi Amari. Nonnegative matrix and tensor factorization [lecture notes]. IEEE signal processing magazine, 25(1):142 145, 2007.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and André van Schaik. EMNIST: Extending MNIST to handwritten letters. In IJCNN 2017, pp. 2921-2926, 2017. doi: 2TL10//IICNNN211..77966666
Nadav Cohen, Or Sharir, and Amnon Shashua. On the expressive power of deep learning: tensor analysis. In Annual Conference Computational Learning Theory, 2015.
Alvaro H. C. Corrcia, Gennaro Gala, Erik Quacghebeur, Cassio de Campos, and Robert Peharz. Contin- wous mixtures of tractable probabilistic models. In The Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-23), 2023.
Meihua Dang, Antonio Vergari, and Guy Van den Broeck. Strudel: A fast and accurate learner of structured- docomposable probabilistic circuits. The International Journal of Appronimate Reasoning (IJAR), 140: 92 115, 2021.
Meihua Dang, Anji Liu, and Guy Van den Broeck. Sparse probabilistic circuits via pruning and growing, Advances in Neural Information Processing Systems (NeurIPS), 35:28374-28885, 2022a.
Meihua Dang, Anji Liu, Xinzhu Wei, Sriram Sankararaman, and Guy Van den Broeck. Tractable and expressive generative models of genetic variation data. In Research in Computational Molecular Biology, pp. 356-357, 2022b. doi: 10.1007 0110/99978--31-0774559
Meihua Dang, Antonio Vergari, and Guy Van den Broeck. Strudel: A fast and accurate learner of structured- decomposable probabilistic circuits. International Journal of Approcimale Reasoning, 140:92- 115, 2022c.
Adnan Darwiche. Decomposable negation normal form. Journal of the ACM (JACM), 48:608 647, 2001.
Adnan Darwiche. A differential approach to inference in bayesian networks. Journal of the ACM (JACM), 50(3):280 305, 2003.
Adnan Darwiche. Modeling and Reasoning with Bayesian Networks. Cambridge University Press, 2009.
Adnan Darwiche and Pierre Marquis. A knowledge compilation map. Journal of Artificial Intelligence Research (JAIR), 17:229-266 264, 2002.
Carl de Boor. Subroutine package for calculating with B-splines. Technical report, Los Alamos National Lab. (L.NN..,, 1971.
36

---

Published in Transactions on Machine Learning Research (02/2025)
Alexis de Colnet and Stefan Mengel. A compilation of succinctness results for arithmetic circuits. In 18th International Conference on Principles of Knowledge Representation and Reasoning (KR), pp. 205-210 215, 2021.
Lieven De Lathauwer, Bart De Moor, and Joos Vandewalle. A multilinear singular value decomposition. SIAM Journal on Matric Analysis and Applications, 21:1253-1278, 2000.
Luc De Raedt, Robin Manhaeve, Sebastijan Dumancic, Thomas Demeester, and Angelika Kimmig, Neuro- symbolic= neural+ logical+ probabilistic. In NeSy@ IJCAI, 2019.
Olivier Delallcau and Yoshua Bengio. Shallow vs. deep sum-product networks. Advances in neural informa- lion processing systems, 24, 2011.
Aaron W. Dennis and Dan Ventura. Learning the architecture of sum-product networks using clustering variables. In Advonces in Nearal Information Processing Systems 25 (NeurIPS), pp. 2033 233-2041. Curran Associates, Inc., 2012.
Nicola Di Mauro, Antonio Vergari, Teresa Maria Altomare Basile, and Floriana Esposito. Fast and accurate density estimation with extremely randomized cutset networks. In ECML/PKDD, 2017.
Nicola Di Mauro, Floriana Esposito, Fabrizio G. Ventola, and Antonio Vergari. Sum-product network structure learning by efficient product nodes discovery. Intelligenaa Artificiale, 12:143 159, 2019.
Nicola Di Mauro, Gennaro Gala, Marco Iannotta, and Teresa M.A. Basile. Random probabilistic circuits.
In Proceedings of the Phirty-Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pp. 1682-1691. PMLR,, 27-30 Jul 2021.
Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using Real NVP. In 5th Inter- national Conference on Learning Representations (ICIRR, 2017.
Conor Durkan, Artur Bekasov, Tain Murray, and George Papamakarios. Neural spline flows. In Adoances in Newral Information Processing Systems 32 (NeurIPS), pp. 7511 7522. Curran Associates, Inc., 2019.
Stavros Efthymiou, Jack D. Hidary, and Stefan Leichenauer. Tensor network for machine learning. ArXiu, het//996.00629,, 2019.
Hamza Fawzi, João Gouveia, Pablo A. Parrilo, Richard Z. Robinson, and Rekha R. Thomas. Positive semidefinite rank. Mathematical Programming, 153:133-177, 2014.
Richard P. Feynman. Negative probability. In Quantum Implications: Essays in Honour of David Bohm, pD. Methuen, 1987.
Gennaro Gala, Cassio de Campos, Robert Peharz, Antonio Vergari, and Erik Quaeghebeur. Probabilis- tic integral circuits. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 2143-2151. PMLR, 2024a.
Gennaro Gala, Cassio de Campos, Antonio Vergari, and Erik Quaeghebeur. Scaling continuous latent variable models as probabilistic integral circuits, 2024b.
Aryo Pradipta Gema, Dominik Grabarczyk, Wolf De Wulf, Piyush Borole, Javier Antonio Alfaro, Pasquale Minervini, Antonio Vergari, and Ajitha Rajan Knowledge graph embeddings in the biomedical domain: Are they useful? a look at link prediction, rule learning, and downstream polypharmacy tasks. arXiv preprint 23v: 19979, 2023.
Robert Gens and Pedro M. Domingos. Learning the structure of sum-product networks. In International Conference Machine Learning, 2013.
Mathicu Germain, Karol Gregor, Iain Murray, and Hugo Larochelle. MADE; Masked autoencoder for distribution estimation. In 32nd International Conference on Machine Learning (ICML), pp. 881 889, 2015.
37

---

Published in Transactions on Machine Learning Research (02/2025)
Kazu Ghalamkari, Jesper Love Hinrich, and Morten Mørup. Non-negative tensor mixture learning for discrete density estimation. orXiv preprinl 2405 1 18220, 2024.
Nicolas Gillis. Nonnegative Motriz Factorization. Society for Industrial and Applied Mathematics (SIAM), 2020.
Tvan Glasser, Ryan Sweke, Nicola Pancotti, Jens Eisert, and Ignacio Cirac. Expressive power of tensor- network factorizations for probabilistic modeling, In Advances in Neural Information Processing Systems 32 (NeurIPS), pp. 1498-1510. Curran Associates, Inc., 2019.
Ivan Glasser, Nicola Pancotti, and J Ignacio Cirac. From probabilistic graphical models to generalized tensor networks for supervised learning. IEEE Access, 2020.
Lars Grasedyck. Hicrarchical singular value decomposition of tensors. SIAM journal on matrix analysis and applicalions, 31 (14:220029-20 20042222442,2 2010.
Zhao-Yu Yu Han, Jun Wang, Heng Fan, Lei Wang, and Pan Zhang. Unsupervised generative modeling using matrix product states. Physical Review X, 8:031012, Jul 2018.
John Hood and Aaron J. Schein. The AL&CORE tensor decomposition for sparse count data. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 4654 4662. PMLR, 02 May 2024.
Emiel Hoogeboom, Jorn W. T. Peters, Rianne van den Berg, and Max Welling, Integer discrete flows and lossless compression. In NewrIPS, pp. 12134-12144, 2019.
Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Ahl, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
Manfred Jaeger. Probabilistic decision graphs- combining verification and ai techniques for probabilistic inference. International Journal of Uncertainty, Fuzziness and Knowledge- Based Systems, 12(supp01): 19-42, 2004.
Priyank Jaini, Amur Ghose, and Pascal Poupart. Promethous: Directly learning acyclic directed graph structures for sum-product networks. In European Workshop on Probabilistic Gmphical Models, 2018a.
Priyank Jaini, Pascal Poupart, and Yaoliang Yu. Deep homogeneous mixture models: Representation, separation, and approximation. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. and R. Garnett (eds.). Advances in Neural Information Processing Systems (NeurIPS), volume 31. Curran Associates, Inc., 2018b.
Yong-Deok Kim and Scungjin Choi. Nonnogative tucker decomposition. In CVPR. IEEE Computer Society, 2007.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastie optimization. In 3rd International Conference Learning Representations (ICLR), 2015.
Friso Kingma, Pieter Abbeel, and Jonathan Ho. Bit-swap: Recursive bits-back coding for lossless compres- sion with hierarchical latent variables. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learwing Research, pp. 3408 3417, 2019.
Doga Gizem Kisa, Guy Van den Broeck, Arthur Choi, and Adnan Darwiche. Probabilistic sentential decision diagrams. In International Conference on Principles of Knowledge Representation and Reasoning, 2014.
Tamara G. Kolda. Multilinear operators for higher-order decompositions. Technical report, Sandia National Laboratories, 2006.
Tamara G. Kolda and Brett W. Bader. Tensor decompositions and applications. Society of Industrial and Applied Mathematics (STAM) Review, 51(3):455- 500, 2009.
38

---

Published in Transactions on Machine Learning Research (02/2025)
Tamara G. Kolda, Brett W. Bader, and Joseph P. Kenny. Higher-order web link analysis using multilinear algebra. In ICDM, pp. 242-24929999922 IEFE Computer Society, 2005.
Daphne, Koller and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques. Adaptive computation and machine learning. MIT Press, 2009.
Picter M. Kroonenberg. Applied Multiway Data Analysis. Wiley Interscience, 2007.
Frank Kschischang, Brendan J Frey, and H-A Loeliger. Factor graphs and the sum-product algorithm.
TEFE Transactions on information theory, 47(2):498 519, 2001.
Yann LeCun, Corinna Cortes, and CJ Burges. MNIST handwritten digit database. ATT Labs [Online].
Available: attp://yann..ecue www.nn..eeeum.co.. cww.annccc//eeemeaaeee com/erdb / 2, 2010.
Troy Lee and Zhaohui Wei. The square root rank of the correlation polytope is exponential. ArXiu, abs/1411.6712, 2014.
Valentin Leplat, Le Thi Khanh Hien, Akwum Onwunta, and Nicolas Gillis. Deep nonnegative matrix factorization with beta divergenoes. arXiv preprint arXim:2309.0822 2023.
Anji Liu and Guy Van den Broeck. HCLT reference implementation, 2021a. URL https://github.coom com/
Anji Liu and Guy Van den Broeck. Tractable regularization of probabilistic circuits. Tn Advances in Neural Information Processing Systems 34 (NeurIPS), pp. 3558 3570. Curran Associates, Inc., 2021b.
Anji Liu, Stephan Mandt, and Guy Van den Broeck. Lossless compression with probabilistic circuits. International Conference on Leorning Representations, 2022.
Anji Liu, Honghua Zhang, and Guy Van den Broeck. Scaling up probabilistic circuits by latent variable distillation. In The Eleventh International Conference on Learning Representations (ICLR), 2023a.
Xuejie Liu, Anji Liu, Guy Van den Broeck, and Yitao Liang. Understanding the distillation process from deep generalive models to tractable probabilistic circuits. In International Conference on Muchine Learning, pp. 21825-20 21838. PMLR, 2023b.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
Lorenzo Loconte and Antonio Vergari. On faster marginalization with squared circuits via orthonormaliza- tion. In 1st. workshop on Connecting Bankkank Pactorizations in AT (CoToRAT), 2025.
Lorenzo Loconte, Nicola Di Mauro, Robert Peharz, and Antonio Vergari. How turn your knowledge graph embeddings into generative models via probabilistic circuits. In Advances in Neural Information Processing Systems 37 (NeurIPS). Curran Associates, Inc., 2023.
Lorenzo Loconte, M. Sladek Aleksanteri, Stefan Mengel, Martin Trapp, Arno Solin, Nicolas Gillis, and Antonio Vergari. Subtractive mixture models via squaring: Representation and learning. In The Twelfth International Conference on Learning Representations (ICLR), 2024.
Lorenzo Loconte, Stefan Mengel, and Antonio Vergari. Sum of squares circuits. In The 39th Annual AAAI Conference on Artificial Intelligence (AAAI), 2025.
Xindian Ma, Peng Zhang, Shuai Zhang, Nan Duan, Yuexian Hou, Ming Zhou, and Dawei Song. A tensorized transformer for language modeling. In NeurIPS, pp. 2229-2239, 2019.
Henrique Malvar and Gary Sullivan. Ycoeg-r: A color space with rgb reversibility and low dynamic range. ISO/IEC JTC1/SC29/VV WG11 and ITU-T SG16 Q 6, 2003.
39

---

Published in Transactions on Machine Learning Research (02/2025)
Emanuele Marconato, Samuele Bortolotti, Emile van Kricken, Antonio Vergari, Andrea Passerini, and Ste- fano Teso. Bears make neuro-symbolic models aware of their reasoning shortcuts. In Uncerlainly in Artificial Intelligence (UAI), 2024a..
Emanuele Marconato, Stefano Teso, Antonio Vergari, and Andrea Passerini. Not all neuro-symbolic con- cepts created equal: Analysis and mitigation of reasoning shortcuts. Advances in Neural Information Processing Systems, 36, 2024b.
Antonio Mari, Gennaro Vessio, and Antonio Vergari. Unifying and understanding overparameterieed circuit representations via low-rank tensor decompositions. In 6th Workshop on Traclable Probabilislic Modeling. 2023.
Radu Marinescu and Rina Dechter. And/or branch-and-bound search for combinatorial optimization in graphical models. Artificial Intelligence, 173(16-17:1455--141, 2009.
Igor L. Markov and Yaoyun Shi. Simulating quantum computation by contracting tensor networks. STAM Journal on Computing, 38(3):963 981, 2008.
James Martens and Venkatesh Medabalimi. On the expressive efficiency of sum product networks. arXiv preprint arXte:1411.7717, 2014.
Alejandro Molina, Sriraam Natarajan, and Kristian Kersting. Poisson sun-product networks: A deep ar- chitecture for tractable multivariate poisson distributions. In AAAI Conference on Artificial Intelligence, 2017.
Alejandro Molina, Antonio Vergari, Nicola Di Mauro, Sriraam Natarajan, Floriana Esposito, and Kristian Kersting. Mixed sum-product networks: deep architecture for hybrid domains. In AAAI Conference on Artificial Intelligence, 2018.
Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. A three-way model for collective learning on multi-relational data. In JCML, pp. 809 816. Omnipress, 2011.
Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgenly Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings of the IEFE, 104(1):11-33) 2015.
Georgii S. Novikov, Maxim E. Panov, and Ivan V. Oseledets. Tensor-train density estimation. In 37th Conference on Uncertainty in Artificial Intelligence (UAI), volume 161 of Proceedings of Machine Learning Research, pp. 1321-1331. PMLR, 2021.
Román Orús. A practical introduction to tensor networks: Matrix product states and projected entangled pair states. Annals of Physics, 349:117 158, 2013.
Ivan. V. Oscledets. Tensor-train decomposition. SIAM Journal on Scientific Computing, 33:2295-2311 2011.
Unut Oztok and Adnan Darwiche. On compiling dnnfs without determinism. ArXiv, abs/ fabs/1170..o 1709.0709, 2017.
Yannis Panagakis, Jean Kossaifi, Grigorios G. Chrysos, James Oldfield, Mihalis A. Nicolaou, Anima Anand- kumar, and Stefanos Zafeiriou. Tensor methods in computer vision and deep learning. Proceedings of the IEEE, 109(5))863-88)) 890, 2021.
George Papamakarios, Theo Pavlakou, and lain Murray. Masked autoregressive flow for density estimation. In Advances in Neural Information Processing Systems 30 (NewrIPS), pp. Inc., 2017.
Curran Associates,
George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lakshmi- narayanan. Normalizing flows for probabilistic modeling and inference. The Journal of Machine Learning Research (JMLR), 22(1):2617-2680, 2021.
Robert Peharz, Sebastian Tschiatschek, Franz Pernkopf, and Pedro Domingos. On theoretical properties of sum-product networks. In Artificial Intelligence and Statistics, pp. 144-752. PMLR, 2015.
40

---

Published in Transactions on Machine Learning Research (02/2025)
Robert Peharz, Robert Gens, Franz Perukopf, and Pedro Domingos. On the latent variable interpretation in sum-product networks. IEBE transactions pattern analysis and machine intelligence, (9(10)20000200 2044, 2016.
Robert Peharz, Robert Gens, Franz Pernkopf, and Pedro M. Domingos. On the latent variable interpretation in sum-product networks. IEEE Transactions on Pottern Analalysis and Machine Intelligence, 39(1:): 2030 2044, 2017.
Robert Peharz, Antonio Vergari, Karl Stelzner, Alejandro Molina, Xiaoting Shao, Martin Trapp, Kristian Kensting, and Zoubin Ghahramani. RAT-SPN reference implementation, 2019. URL https://githul: com/cambridge BaaebbriddgggggAA------- mlg/RAT-SPN,
Robert Peharz, Steven Lang, Antonio Vergari, Karl Stelzner, Alejandro Molina, Martin Trapp, Guy Van Den Broeck, Kristian Kersting, and Zoubin Ghahramani. Finsum networks: Fast and scalable learning of tractable probabilistic circuits. In 37th International Conference on Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pp. 7563-7574. PMLR, 2020a.
Robert Peharz, Steven Lang, Antonio Vergari, Karl Stelzner, Alejandro Molina, Martin Trapp, Guy Van Den Broeck, Kristian Kersting, and Zoubin Ghahramani. EiNets reference implementation, 2020b. URL https:/ http//gtttuut.t//////// commccmbridde-ml. haaaaeemll//insmnnettrrttt
Robert Peharz, Antonio Vergari, Karl Stelzner, Alejandro Molina, Xiaoling Shao, Martin Trapp, Kristian Kersting, and Zoubbin Ghahramani. Random sum-prodduc networks: A simple and effective approach to probabilistic deep learning. In 35th Conference on Uncertainty in Artificial Intelligence (UAI), volume 115 of Proceedings of Machine Learning Reseavch, pp. 334 344. PMLR, 2020c.
David Pérez-García, F. Verstraete, Michael M. Wolf, and Juan Ignacio Cirac. Matrix product state repre- sentations. Quantum Information and Computing, 7(5):401-43)) 2007. ISSN 1533-7146.
Knot Pipatsrisawat and Adnan Darwiche. New compilation languages based on structured dccomposability. In 23rd Conference on Artificial Intelligence (AAAI), volume 8, pp. 117-522, 2008.
Hoifung Poon and Pedro Domingos. Sum-product networks: A new deep architecture. In IEEE International Conference Computer Vision Workshops (ICCV Workshops), pp. 689-690 IEFE, 2011.
Harsh Poonia, Moritz Willig, Zhongjie Yu, Matej Zečević, Kristian Kersting, and Devendra Singh Dhami. 8 chihSSPN:: Characteristic interventional sum- con-prrouct networks for causal inference in hybrid domains. In The 40th Conference on Uncertainty in Artificial Intelligence (UAT), 2024.
Lawrence Rabiner and Biinghwang Juang. An introduction to hidden Markov models. IEFE ASSP magazine, 3(1):4 16, 1986.
Tahrima Rahman, Prasanna Kothalkar, and Vibhav Gogate. Cutset networks: A simple, tractable, and scalable approach for improving the accuracy of chow-liu trees. In Machine Learning and Knowledge Discovery in Databoses: Europeon Conference, ECML PKDD 2014, Nancy, France, September 15-19, 2014. Proceedings, Part IT 14, pp. 630-645, Springer, 2014.
Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po-Yao Huang, Zhihui Li, Xiaojiang Chen, and Xin Wang. A comprehensive survey of neural architecture search: Challenges and solutions. ACM Computing Surveys (CSUR), 54(4):1-34, 2021.
Elina Robeva. and Anna Seigal. Duality of graphical models and tensor networks, 2017.
Yangjun Ruan, Karen Ulrich,, Daniel Severo, James Townsend, Ashish Khisti, Arnaud Doucet, Alireza Makhzani, and Chris Maddison. Improving lossless compression rates via monte carlo bits-back coding, In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 9136 91479 2021.
Berkant Savas and Lars Eldén. Handwritten digit classification using higher order singular value decompo- sition. Pattern Recognit., 40(3):993-11) 1003, 2007.
41

---

Published in Transactions on Machine Learning Research (02/2025)
Uhrich Schollwoeck. The density-matrix matrix renormalization group in the age of matrix product states. Annals of Physics, 326:96-192, 2010.
Nimish Shah, Wannes Meert, and Marian Verhelst. Efficient Execution of Irregular Dataflow Graphs. Springer, 2023.
Xiaoting Shao, Alejandro Molina, Antonio Vergari, Karl Stelzner, Robert Peharz, Thomas Liebig, and Kris- tian Kersting. Conditional sum-product networks: Imposing structure on deep probabilistic architectures. Tn International Conference on Probabilistic Graphical Models, pp- 401-412. PMLR,, 2020.
Xiaoting Shao, Alejandro Molina, Antonio Vergari, Karl Stelzner, Robert Peharz, Thomas Liebig, and
Kristian Kersting. Conditional sum-product networks: Modular probabilistic circuits via gate functions. International Journal of Approzimale Reasoning, 140:298 313, 2022.
Or Sharir, Ronen Tamari, Nadav Cohen, and Amnon Shashua. Tensorial mixture models. abs/1610.04167, 2017.
ArXiv,
Amnon Shashua and Tamir Hazan. Non-negative tensor factorization with applications to statisties and computer vision. In Proceedings of the 22nd international conference on Machine learning, pp. 792 799, 2005.
Yujia Shen, Arthur Choi, and Adnan Darwiche. Tractable operations for arithmetic circuits of probabilistic models. In Advances in Neural Information Processing Systems 29 (NeurlPS). Curran Associates, Inc., 2016.
Yaoyun Shi, Lumtng Duan, and Guifré Vidal. Classical sinulation of quantum many-body systems with a tree tensor network. Physical Review A, 74:022320, 2005.
Amir Shpilka and Amir Ychudayoff. Arithmetic circuits: A survey of recent results and open questions. Founddations and Trends in Theorefical Computer Science, 5:207 388, 2010.
Sahil Sidheekh and Sriraam Natarajan. Building expressive and tractable probabilistic generative models: A review. Xix preprinl urXiv:2402.0077: 00.5099, 2024.
Sahil Sidheekh, Kristian Kersting, and Sriraam Natarajan. Probabilistic flow circuits: Towards unified deep models for tractable probabilistic inference. In 39th Conference on Uncertainty in Artificial Intelligence (UAI), volume 216 of Proceedings of Machine Learning Research, pp. 1964-1973. PMLR, 2023.
Nicholas D. Sidiropoulos, Lieven De Lathauwer, Xiao Fu, Kejun Huang, Evangelos E. Papalexakis, and Christos Faloutsos. Tensor decomposition for signal processing and machine learning. IEEE Transactions on Signal Processing, 65(13):3551-356 -3582, 2017. doi: 10.1109 21.....11.26996.
Le Song, Mariya Ishteva, Ankur Parikh, Eric Xing, and Haesun Park. Hierarchical tensor decomposition latent tree graphical models. International Conference on Machine Learning, pp. 344-342. PMLR, 2013.
Edwin Stoudenmire and David J Schwab. Supervised learning with tensor networks. In Advances in Neural Information Processing Systems 29 (NewrIPS), pp.
Curran Associates, Inc., 2016.
Ping Liang Tan and Robert Peharz. Hierarchical decompositional mixtures of variational autoencoders. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6115-66 6124. PMLR, 09-15 15 Jun 2019.
Alex Townsend and Lloyd N. Trefethen. Continuous analogues of matrix factorizations. Proceedings of the Royal Society A: Mathematicul, Physical and Engineering Sciences, 471, 2015.
James Townsend, Thomas Bird, and David Barber. Practical lossless compression with latent variables using bits back coding. In ICLR 2019, 2019.
42

---

Published in Transactions on Machine Learning Research (02/2025)
Volker Tresp, Sahand Sharifzadeh, Hang Li, Dario Konopatzki, and Yumpu Ma. The tensor brain: A unified theory of perception, memory, and semantic decoding. Neural Compulation, 55:156-221 2021.
L. R. Tucker. The extension factor analysis to three-dimensional matrices. In Contributions to mothe- matical psychology,; pp. 110-127. Holt, Rinehart and Winston, 1964.
Ledyard R. Tucker. Some mathematical notes mode factor analysis. Psychometrika,, 31:279 311, 1966.
Leslie G. Valiant. Negation can exponentially powerful. In 11th Annual ACM Symposium on Theory of Computing, pp. 189-196, 1979.
Emile van Krieken, Pasquale Minervini, Edoardo Ponti, and Antonio Vergari. On the independence assump- tion in neurosymbolic learning. In Forty-first International Conference on Machine Learning, 2024.
M. Alex O. Vasilescu and Demetri Terzopoulos. Multilinear image analysis for facial recognition. In TCPR 2002, pp. 511 514. IEEE Computer Society, 2002.
Joshua Vendrow, Jamie Haddock, and Deanna Needell. A generalized hicrarchical nonnegative tensor de- composition. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4473-4477, 2021.
Antonio Vergari, Nicola Di Mauro, and Floriana Esposito. Simplifying, regularizing and strengthening sum-product network structure learning. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2015, Porto, Portugal, September 7-11, 2015, Proceedings, Part II 15, pp. 343-358. Springer, 2015.
Antonio Vergari, Robert Peharz, Nicola Di Mauro, Alejandro Molina, Kristian Kersting, and Floriana Es- posito. Suoduut autoencoding: Encoding and decoding representations using sum-product networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
Antonio Vergari, Nicola Di Mauro, and Floriana Esposito. Visualizing and understanding sum-product networks. Machine Learning, 108(4):551-373, 2019a
Antonio Vergari, Nicola Di Mauro, and Guy Van den Broeck. Tractable probabilistic models: Representa- tions, algorithms, learning, and applications. Tutorial at the 35th Conference Uncertainty in Artificial Intelligence (UAT), 2019b.
Antonio Vergari, YooJung Choi, Auji Liu, Stefano Teso, and Guy Van den Broeck. compositional atlas of tractable circuit operations for probabilistic inference. In Advances in Neural Information Processing Systems 34 (NeurIPS), pp. 13189 13201. Curran Associates, Inc., 2021.
Maarten De Vos, Lieven De Lathauwer, Bart Vanrumste, Sabine Van Huffel, and Wim Van Paesschen. Canonical decomposition of ietal scalp EEG and accurate source localisation: Principles and simulation study. Computational Intelligence and Neuroscience, 2007, 2007.
Thomas Wedenig, Rishub Nagpal, Gactan Cassiers, Stefan Mangard, and Robert Peharz. Exact soft an- alytical side-channel attacks using tractable circuits. In International Conference on Machine Learning, 2024a.
Thomas Wedenig, Rishub Nagpal, Gaëtan Cassiers, Stefan Mangard, and Robert Peharz. Exact soft an- alytical side-channel attacks using tractable circuits. In International Conference on Machine Learning, 2024b.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNISTT: Novel Image Datasct for Benchmarking Machine Learning Algorithms. ArXio, abs/1708.077477, 2017.
Mingxue Xu, Yao Lei Xu, and Danilo Mandic. Tensorgpt: Efficient compression of the embedding layer in lms based on the tensor-train decomposition. CoRR, abs/2307.0055 .005660 2023.
43

---

Published in Transactions on Machine Learning Research (02/2025)
Zhongjie Yu, Martin Trapp, and Kristian Kersting. Characteristic circuits. In shirty-seventh Conference Newral Information Processing Systems (NewrIPS), 2023.
Zhe Zeng, Paolo Morettin, Fanqi Yan, Antonio Vergari, and Guy Van den Broeck. Scaling up hybrid proba- bilistic inference with logical and arithmetic constraints via message passing. In International Conference on Machine Learning, pp. 10990-11000 PMLR, 2020.
Honghua Zhang, Meihua Dang, Nanyun Peng, and Guy Van den Broeck. Tractable control for autoregressive language generation. In 40th International Conference on Machine Learning (ICML), volume 202 of Proceedings of Machine Learning Research, pp- 00932-40940 PMLR, 2023.
Han Zhao, Pascal Poupart, and Geolfrey J Gordon. A unified approach for learning the parameters of sum-product networks. Advances in neural information processing systems, 29, 2016.
44

---

Published in Transactions on Machine Learning Research (02/2025)
A Proofs
A.1 Tucker as Circuit
Proposition (Tucker as a circuit). Let T e x be a tensor being decomposed via a multilinear rank- (RI,... Ra) Tucker factorization, as in Eq. (2). Then, there exists a circuit e over variables X { [g] j e [d] computing the same factorization. Moreover, we have that |c| O(d R2).
{X,}}=1
with dom(X,)
Proof. We prove it constructively by giving the structure and parameters of c. That is, we build a circuit c over variables computing
R1
c(X)
xd) Σ
Σ Tu-1
(19)
Note that in Eq- (19) each product cfrr, (2r1) ... cdrr (Ta) can be computed by a product unit prod over variables X. Moreover, encode each Shr, imput unit, for all j E [d] and ry [Ry]. In addition, the collection of sums -ー-1" ... -. that are weighted by the Wryorr can be computed by single sum unit having 115-1 R2 inputs, i.., the products grod with Tg E [Ry]] for all j. Since each product units has d inputs, we have that the overall circuit size is |c| E I Ry). Finally, we take Wr,-r, as the entries the core tensor W, and make each input unit Sry, compute "0,,, ezjor, for the factor matrices { (y in the Tucker factorization. That is, c(X) computes the same Tucker factorization given by hypothesis. J
())
1==1
A.2 Hierarchical Tucker Deep a Circuit
Proposition (Hierarchical Tucker as deep circuit). Let T 1 be tensor being decomposed us- ing hierarchical Tucker factorization according to a RG R (Def. 5). Then, there exists circuit over variables X (X,)ş_1 with dX,) = [Ty], computing the same factorization. Furthermore, given (Y li 2 the set of all non-leaf region nodes y( = X being factorized into (z (Z!)) in R, with corresponding Tucker factorization multilinear rank (Ryt, R2zo, Ryto), we have that |c| O 1 ReyinRye Ryz0 R2
Proof. Similarly our proof for Proposition 1, we prove constructively by giving the structure and parameters of That is, rewrite the recursive rules used to define a hierarchical Tucker factorization showed in Def. 5 in terms of equivalent circuit computational units. For every leaf region Z (X,) in R, we introduce the input units <hyy,, rú E [Rz], each computing (x,) = u2y for the factor matrix voi of the hierarchical Tucker factorization given by hypothesis. Next, we recursively introduce sum and product units by following the hierarchical variables factorization defined in R. That is, for every non-leaf region node Y c X being partitioned into (Z,, Z2) in R, we introduce sum and product units that encode Tucker factorization related to the region node Y. More formally, given (Ry, Rz, Rz,) the multilinear rank associated to the region node Y, we introduce the sum units Cy,s with E [Rr]] Moreover, we prod introduce the product units Crrr? with ri E [Rz,]] and r2 E [Rzz]. Each sum unit c. has the product R2,,.Rz, units (c 1r =11 as inputs, and is paramcterized by weights (Wari R2, R2, Furthermore, we recursively define the inputs to each product unit prod cy,,,r to be the pair of sum units Z1,7, and sum for all F [R2,, and r2 E [Rz,]. By setting the parameters of each sum unit 0gr to be the entries of the core tensor ((( (sce Eq. (6)), we recover that the constructed composition of sum and product units encodes the Tucker factorization associated to Y. Finally, in the case of the root region Y = X in R, we have that Ry = by hypothesis, and therefore the output of the circuit is given by the sum unit x.1 Since the circuit c built in this way consists a composition of Tucker factorizations represented as circuits (Proposition 1), the circuit size is |c| E O Ryto Rz(0 R2 )2) with ( |m being the set of non-leaf regions in R. j
45

---

Published in Transactions on Machine Learning Research (02/2025)
B Many Tensorized PC Architectures can be Obtained through our Pipeline
We will consider one tensorized PC architecture at time, and show how its construction can be understood in terms of simple design choices presented in our pipeline: (1) the region graph to parameterize (Section 4.1), (2) the sum and product layers chosen (Sections 4.2 and 4.3 and Section 5), and (3) whether the archilecture is folded or not (Section 4.4).
Poon & Domingos circuits (Poon & Domingos, 2011) for image data follow the homonomous region graph structure. While the circuit is nol Lensorized, i.e, the computational units defined over the same variable scope are not replicated and tensorized into layers, we can still see them as tensorized circuit where the width of cach layer is 1. Furthermore, no folding is performed to the best of our knowlodge.
circuits (RAT-SPN) (Peharz et. al., 2020c) are obtained by parameter- izing randomly-consstruuee constructe binary tree region graph (named RND in this paper). In particular, in this architecture Kronecker product layers and sum layers are alternated, thus being equivalent to circuits with Tucker layers (Eq. (Tucker-layer)) in our pipeline. In the original implementation of RAT-SPNs (Peharz et al., 2019), layers are no folded.
Einsum networks (EiNets) (Peharz et al., 2020a) include a folded version of RAT-SPNs, as well tensorized and folded circuits obtained by overparameterizing the PD region graph. See Peharz et al. (2020b) and Braun (2021) for known available implementations.
Hidden Chow-Liu Tree (HCLT) circuits (Liu & Van den Broeck, 2021b) are tensorized circuits obtained by compiling a tree-shaped graphical model that is learned with the Chow-Liu algorithm (Chow & Liu, 1968a). Therefore, it can be obtained in our pipeline by paramcterizing the CL region graph with CP layers whose parameter matrices encode conditional probability tables. HCLTs have been originally implemented within the Juice.jl Julia library (Liu & Van den Broeck, 2021a), which also includes parallelization scheme using custom CUDA kernels that fuse sum and products operations.
Non-negative matrix-product states (MPSg30) have been shown to be equivalent to hidden-markor models (HMMs) (Rabiner & Juang, 1986) up to renormalization (Glasser et al., 2019). Given a total ordering of variables Xi,..., Xx, it is known we can compile an HMM into an equivalent structured decomposable circuit (Vergari al., 2019b), which has the same structure of the tensorized circuit encoding an MPS showed in Fig. 8. Therefore, we can represent an HMM/MPS230 in our circuit construction pipeline by parameterizing a lincar-tree region graph (called LT in this paper) with CP layers.
Born machines (BM) (Han el al., 2018) and Tensor-Train Density Estimators (TTDE) (Novikov et al., 2021) are probabilistic models used to estimate probability mass functions and probability density functions, respectively. They are obtained by efficiently squaring an MPS, which is a structured decomposable tensorized circuit as for Proposition 3. Note that such a tensorized circuit can be obtained using the same region graph and tensorized layer used to construct a non-negative MPS, but instead just relax the non- negativity assumption over its parameters. It is known that squaring a MPS (resp. a structured decomposable tensorized circuit) yields BM (resp. another structured decomposable tensorized circuit having the same layers but with quadratic width increase). See e.g. Proposition 3 in Loconte et al. (2024). Therefore, BMs and TTDEs can be retrieved through our circuit construction pipeline by overaparameterizing a linear-tree region graph (LT) with CP Clllayers, followed by efficiently squaring the resulting circuit (Vergari et al., 2021).
Squared non-monotonic PCs (NPC²) (Loconte et al., 2024) are generalizations of BMs and TTDFs that also include the squaring of tensorized circuits obtained by overparameterizing a random binary tree region graph (as in RAT-SPNs above), as well as using Tucker layers instead of CP cllleyess Furthermore, the original implementation of NPC² allows circuits to be folded.
Tree Tensor Networks (TTNs) (Cheng et al., 2019) are trec-shaped hicrarchical tensor factorizations represented through the tensor network formalism. TTNs factorizations are equivalent to hierarchical Tucker, but one choose a particular structure based on the data distribution being modelled. For image data, Cheng et al. (2019) proposed a TTN structure obtained by recursively splitting an image in half, alternating horizontal and vertical splits. This structure is analogous to our quad tree region graph (QT), but allowing splitting image patches in just two parts (rather than four).
46

---

Published in Transactions on Machine Learning Research (02/2025)
C
Sampling
In Algorithm C.1, we interpret the entries of each non-negative parameter mairix W in e as the pa- rameters of categorical distributions associated to S latent variables, each taking values in f1...., K}. Note that we can always normalize a PC s.t. its normalization constant equal to thus yielding parameter matrices that sum up to along every row, as detailed in (Peharz et al., 2015). Then, sampling data point translates to iteratively sampling from such latent variables (see T8-13 13 of the algorithm) according to the hierarchical structure of the circuit, i.e. following a topological order like breadth first search (BFS). Note that sampling the latent variables corresponding to sum layer corresponds to choosing (i) selection of the input layers on which recursively continue sampling, and (ii) a particular computational unit within each selected layer. The information (i) and (ii) for each layer is stored in dictionarics (see L1-4). Due to decomposability (Def. 8), sampling from a product layer & translates to choosing a selection of the input computational units, as they will be defined on different variables. Unlike sum layers where we sample from Categoricals to select such units, in product layers they are unequivocally determined by which product unit of & has been selected previously and whether & is Kronecker or Hadamard layer (see L14-20). We sample all sum and product layers as explained below. Finally, it remains to sample from the input layers and assign values to the variables the PC is defined on. We sample from an input layer & when at least one input units within has boen selected by the sampling procodure above for sum and product layers. That is, given X E X the variable on which depends on and ny the k-th input unit to sample from, we sample an assignment X from my (sec 1.21-25).
Algorithm C.1
Input: tensorized PC a over X
{X.) a positive integer N.
Output: Samples S E R NXD drawn from c.
Assumptions: (1) c normalized: all sum layer parameters sum up to 1 over the columns; (2) Each input layer is defined over single RV; (3) the width of layer is multiple of K.
Notes: (1) All assignennts preceded by the symbol A can be parallelized; (2) unravel-index is the homonymous numpy function but whose indexing starts from 1 instead of O.
S - (e: []: Vl []
c]s- mapping layers to sample indices 14:
else if l Kronecker prod. layer then
2: U [e: []
veE c) t mapping layers to unit indices
15:
idx-list unravel-index(([ [], (K, (K))
3: S|c] - [M]
16:
Vi E [4] [exli]]exteed(((]]] &J)
4: u[c] 1x
17:
5: for each inner layer e (FS(c) do
18:
clse if É is a Hadamard prod. layer then
6:
C list of the L input layers of é
19:
Vi [4] S[[]]] [[C[]]]]xxteedd(]] (Stend(S[ {[])
7:
if S[e] is emply then skip
20:
[[[[[]] [[[[[]].extend() (((
else if é a sum layer with We e R Kc then v vector of size [S[é]] with values in [KL]
21: S - R NXD
9:
22: for each input layer E decst s.t. S(4] * [] do
10:
iN sample from categorical with p Wurd).
23: j- sc(()
11:
idx1, idx2 + unravel-index(v, K))
24: pairs - vstack(S1(),2((())
12:
vi E [4] [x]]i]].exted((SS(( extend = +])
== i))
25: V(i, pairs S. sample k-th unit of e
13:
26: return samples S
D Region Graphs:
and Quad- Trees
Algorithm D.1 details the construction of our proposed RGs for image-data: QTs and QGs. The algorithm takes as input the height (H) and width (W) of the image, and a flag (isTree), which specifies whether to enforce the output RG to be a tree (QT) or not (QG). The algorithm builds a RG in a bottom-up fashion, merging regions associated to smaller patches to bigger patches, starting from the single pixels. Specifically, build QTs-QTQ------ to be precise-we we merge regions using Algorithm D.2, whereas for QGs we merge regions using Algorithm D.3.
47

---

Published in Transactions on Machine Learning Research (02/2025)
X11-X12-11 X21 X22 X23 Xa1
Figure D.1: The quad graph (QG). We illustrate the quad graph RG delivered by Algo- rithm D.1 passing H = W = and Tree = False as input argu- ments. The region graph is wn- balanced as the image size (3x not a power of Differently from our quad troes (QTs), QGs have regions partitioned in more than a single way (e.g., the root region node), and regions can be shared among partitions. For ex- ample, in a QT, the top region could only be partitioned in a single way into two or four sub- regions, respectively called QT-2 and QT-4 region graphs.
X11-112113 X2222a
X12 X21 X22 Xa1 X31
X32XX
X X 23 Xas
X11 X21 Xg2
X31
X1a
X
X11X12
X11
X21 X22
X22
X31
X32
X13
X
X11
X
X21
X
Algorithm D.1 buildQuadGraph(HH H, W, isTree)
Algorithm D.2 mergeTree A,
Input: Image height H, image width W, and whether
Input: a RG R, a set of four coordinates A,
enforce the output RG be tree.
and a collection of regions S.
Output: RG over H W variables.
Behavior: It merges the regions indexed by A by forming tree structure.
1: S - (Y,,- (X+) (i.j) [M] [W])
2: R - a RG having leaf regions S
1: Let Zur = Yptu E s.t.
3: h H;
W
2: +.)+ A, u, (0,
4: while > v w > do
3: Y - Zuo U Zui Zıo U Zn1
h [h/2];
[w/2]; S'
4: addPartition R, (Zoo, Zoi Zio. Zn13)
6:
for i.j e [h] x [w] do
A ((2i-12 21) (2) (2 ([W]
8:
if | 1 then
Algorithm D.3 mergeDAG(RR,
,u s.t. (p.9)
Input: RG R, set of four coordinates A,
10:
addRegion(R, pn)
and a collection of regions Behavior: It merges the regions indexed by A in R by forming a DAG structure.
11:
else A = then
12:
Let Y Y. Y.s S s.t.
13:
2), (r, 8)
p 5
1: Let Zuv = Yptu E s.t.
14:
addPartition R, Y Yrs, (Y Y,sh)
2:
(p u, E u, e {0,
15:
else
- A =
3: Y - Zuo Zuz Zuo U Z11
16:
if Tsere then meegeTree(( A, else mergeDAG(R, 5)
4: addPartition( R, Y. (Zao Zon, Zuo u Zni)
17:
5: addPartition R, Y, (Zon Zin. Ze
Zn
18:
Y, - Unsees Yo. s.L. Y E
6: addPartition R, Zon u Zai, (Zoo, Zon
19:
- (Y
7: addPartition R, Z1o Z11, (Z10. Z
S S-5 S'
8: addPartition R, Zoo u Zιo (Zoo. Zιo))
21:
return R
9: addPartition R, Zui Zn, (Zo,, Zn1))
We illustrate in Fig. D.1 the resulting QG obtained via Algorithm D.1 with Hl 3, W and isTree False. The QG unbalanced as HW is not a power 2.
48

---

Published in Transactions on Machine Learning Research (02/2025)
E
Additional Results
Test Time (ms)
Train Time (ms)
Test Memory (GB)
Train Memory (GB)
17.5
15.0
40
QT-CP
QT-CP
QG-CP
30
QG-Tucker
10a
QG-CP*
PD-CP
10.0
20
7.5
10
5.0
24
26
23
26
2
24
2
2
2
2
K
K
Figure E.1: Benchmarking the role of RGs and composite layers in tensorized circuits on CelebA. We report the average time (ms) and GPU memory usage (GiBs) to process a batch of samples for different tensorized architectures listed in the legend on the right- at different values K (x-axis). The stats are reported both at test and training time. The benchmark conductod using the CELEBA datasct with a batch size of 128.
Mnist
Fashion Mnist
CelebA
1.40
6.2
Test bpd
1.35
3.7
6.0
OT-CPS
QT-CP
1.30
3.6
-0-lucckr
OG-CPP
1.25
5.6
PD-CP
PD-Tucker
5.4
3.3
128
512
256
16
128
256
K
Figure E.2: Overparameterizing tensorized architectures delivers better performing models when using QTs and QGs, but not when using PDs. Different from Fig. 20, we here learn the mixing layers in QG- and PD-based models. We report the test-set bpd (y-axis) at different values of K (x-axis) for MNIST (left), FASHIoNMNIST (middle) and CELEBA (right) averaged over 5 runs for different tensorized architectures, which we report in the legend on the right. We use a batch size of 256.
Test Time (ms)
Train Time (ms)
Test Memory (GB)
Train Memory (GB)
40
QT-CP*S
10a
QT-CPS QG-Cpxs
QG-CPS
PD-CPKS
102
20
PD-CPS
10a
5
10
0
26
2 2
212
24
2b
2
2/2
24
2
240
2
2
2
2
2/2
K
K
K
Figure E.3: For the same choice of RG and K, CPS and CPXS layers require the same time/space resources, with cp only being slightly faster at training-time. We report time (ms) and GPU memory usage (GiBs) at different values of K (x-axis) at both lest-lime and training-time for different tensorized architectures listed the legend on the right. The benchmark conducted on MNIST using a batch size of 128.
49

---

Published in Transactions on Machine Learning Research (02/2025)
Mnist
Fashion
CelebA
QT-CP>S
6.2
QT-CPS
QG-CPXS
Test bpd
3.7
QG-CPS
6.0
PD-CPsS
3.6
PD-CPS
3.5
5.8
16
32
128
256
512
64
128
256
512
16
32
64
128
256
K
K
K
Figure E.4: CPxs and CP3 layers are equivalently accurate when used in different tensorized ar- chitectures. We report the test-set bpd (y-axis) avcraged over 5 runs for different tensorized architectures listed in the legend on the right- at different values of K (x-axis). We use the MNIST, MASHIONMNIST and CELEBA datasets, and batch size of 256.
Table E.1: Mnist distribution cstimation results. Test-set bpd on MNIST averagod over runs for different tensorized PC architectures. We report 3 standard deviations from the mean.
Learn
RG
K
CP
Cpxs
CpS
Tucker
Mixing-Layer
16
1.383 + 0.008
1.392 + 0.008
1.392 + 0.007
1.380 + 0.006
32
1.380 + 0.007
1.387 + 0.005
1.387 + 0.008
1.375 + 0.004
64
1.379 + 0.009
1.384 0.005
1.387 + 0.009
1.372 + 0.004
PD
Yes
128
1.379
0.003
1.386 0.006
1.394 0.006
OOM
256
1.377
0.005
1.386
1.394 0.009
0OM
512
1.375
0.009
1.385 + 0.007
1.390 + 0.011
0OM
16
1.381
0.007
1.402 + 0.008
1.389 + 0.006
1.377 + 0.005
32
1.381
0.009
1.394 0.011
1.385 + 0.003
1.377 + 0.004
64
1.376
0.002
1.387 0.005
1.383 0.004
1,381 + 0.006
PD
No
128
1.375
0.003
1.387 0.003
OOM
256
1.373
0.005
0.006
1.390 + 0.009
0OM
512
1.370
0.002
1.395 0.014
1.384 + 0.008
00M
16
1.283
0.004
1.395 + 0.008
1.374 0.008
N/A
32
1.242
0.004
1.345
1.336 0.009
N/A
64
1.217
0.002
1.301
1.308 0.003
N/A
QT
N/A
128
1.196
0.004
+
1.284 + 0.002
N/A
256
1.184 + 0.002
1.245 + 0.028
1.266 + 0.003
N/A
512
1.175 + 0.001
1.225
0.010
1.251 + 0.002
N/A
16
1.249
0.004
1.375 + 0.014
1.346 0.010
1.235 + 0.012
32
1.213
0.003
1.334 0.010
1.317 + 0.004
1.225 + 0.011
64
1.190 + 0.003
+
1.289 + 0.003
1.258 + 0.005
QG
Yes
128
1.179 + 0.001
+
1.265 + 0.004
OOM
256
1.177 + 0.004
+
1.244 0.003
OOM
512
1.180
0.009
+
1.225 + 0.004
0OM
16
1.248
0.003
1.369 0.039
1.346 + 0.004
1.233 + 0.004
32
1,212 + 0.003
1.313 0.027
1.313 + 0.006
1.222 + 0.004
64
1.185 + 0.002
1.276 + 0.010
0.010
1.285 4 0.006
1.257 + 0.005
QG
No
128
1.171 + 0.002
1.259 0.011
1.258 + 0.004
OOM
256
1.173
0.009
1.245 + 0.009
1.236
0.002
0OM
512
1.177 0.006
1.235 + 0.010
1.212 0.010
00M
50

---

Published in Transactions on Machine Learning Research (02/2025)
Table E.2: FashionMnist distribution estimation results. Test-set bpd on FASHIONMNIST averaged over runs for different tensorized PC architectures. We report standard deviations from the mean.
RG
Learn
K
CP
Cpxs
Cps
Tucker
Mixing-Layer
16
3.719 0.014
3.757
3.757 0.011
3.719 + 0.015
32
3.705 + 0.012
+
3.739 + 0.005
3.709 + 0.004
64
3.025
3.750 0.009
3.731 + 0.014
PD
Yes
128
3.752 0.005
3.782 3.009
OOM
256
3.790 0.011
3.801
3.807
0OM
512
3.836 + 0.019
3.836 0.024
1.011
0OM
16
3.715
0.004
3.785
0.010
3.748 + 0.011
3.716 + 0.007
32
3.700 + 0.017
3.758 0.009
3.736 + 0.005
3.709 + 0.004
64
3.721 + 0.011
3.746 0.062
3.736 + 0.006
PD
No
128
3.752 + 0.012
3.775 0.001
OOM
256
8.779 0.012
0.004
1.79
OOM
512
3.814 0.012
3.860 0.024
3.829 0.015
OOM
16
3.589 + 0.005
3.806 0.042
3.772 + 0.031
N/A
32
3.497 + 0.003
3.731 + 0.032
3.720 + 0.007
N/A
64
3.442 + 0.003
3.648 + 0.019
3.671 + 0.005
N/A
QT
N/A
128
3.408 0.003
3.584
3.620 + 0.009
N/A
256
3.392
0.001
0.014
3.576 0.013
N/A
512
3.381
0.002
3.518 0.018
3.536 + 0.007
N/A
16
3.459
0.004
3.741 + 0.030
3.690 + 0.019
3.446 + 0.004
32
3.381 + 0.002
+ 0.026
3.611 + 0.016
3.416 + 0.006
64
3.341
0.004
4.022
3.563 0.020
3.518 + 0.012
QG
Yes
128
3.326 0.002
3.087
3.523 0.006
OOM
256
3.326 0.003
3.04
3.484 0.004
OOM
512
3.326 + 0.004
0.011
3.444 0.009
0OM
16
3.464
0.005
3.717 + 0.051
3.677
0.031
3.446 + 0.008
32
3.385
0.004
3.624 0.051
3.600 0.011
3.417 + 0.005
64
3.339
0.004
3.578 0.032
3.540 + 0.009
3.499 + 0.006
QG
No
128
3.319 + 0.004
4.033
3.501 0.017
OOM
256
3.317 + 0.002
3.491 0.013
3.470 + 0.005
0OM
512
3.317 + 0.005
3.467 0.032
3.425 + 0.010
0OM
51

---

Published in Transactions on Machine Learning Research (02/2025)
Table E.3: CelebA distribution estimation results (using RGB values). Test-set bpd on CELEBA averaged over 3 runs for different tensorized PC architectures. mean.
We report standard deviations from the
Learn
RG
K
CP
CPx8
CPS
Tucker
Mixing-Layer
16
5.828 0.008
6.237 + 0.026
6.171 t 0.006
N/A
32
5.612 = 0.012
6.024 0.032
5.981 + 0.007
N/A
64
5.457 + 0.010
5.831 + 0.022
5.843 + 0.017
N/A A
QT
N/A
128
5.374 + 0.002
5.732 + 0.044
5.766 + 0.022
N/A A
256
5.332 + 0.002
5.739 + 0.037
5.753 + 0.014
N/A
16
5.756
6.161
6.072
5.742
32
5.532
5.960
5.880
5.498
64
5.391
5.816
5.751
OOM
QG
Yes
128
5.329
5.771
5.715
OOM
256
OOM
5.731
5.702
OOM
16
5.755 + 0.010
6.292 + 0.037
6.069 + 0.006
5.738 + 0.011
32
5.528 + 0.023
6.056 + 0.072
5.875 + 0.016
5.494 + 0.023
64
5.392 + 0.026
5.906 + 0.052
5.746 + 0.010
OOM
QG
No
128
5.335 + 0.027
5.742 + 0.067
5.725 + 0.039
OOM
256
OOM
5.691 + 0.034
5.667 0.014
0OM
Table E.4: CelebA distribution estimation results using lossless YCoCg transform. Test-set bpd on CELEBA over single run for different tensorized PC architectures. We note how performance are consistently better than those in Table E.3, confirming that using the YCoCg transform helps. Note that results in this table are directly comparable with those in Table E.3 because the transformation used is lossless (and operates on discrete data, hence does not require a correction by the log-determinant).
Learn Mixing-Layer
RG
K
CP
Cpxs
CPS
Tucker
16
5.604
5.770
5.831
N/A
5.447
5.656
5.648
N/A
64
5.321
5.584
5.589
N/A
QT
N/A
128
5.248
5.570
5.549
N/A
256
5.238
5.522
5.548
N/A
5.541
5.840
5.757
5.541
32
5.383
5.660
5.622
5.383
64
5.273
5.544
5.510
OOM
QG
No
128
5.205
5.536
5.500
OOM
256
OOM
5.579
5.489
OOM
52

---

Published in Transactions on Machine Learning Research (02/2025)
E.1
Results UCI Tabular Datasets
Number of samples
train
validation
test
Table E.5: UCI dataset statistics. Di- mensionality D and number of samples of each dataset split after the preprocessing by Papamakarios et al. (2017).
Power
6
1,659,917
184,435
204,928
Gas
8
852,174
94,685
105,206
Hepmass
21
313,123
35,013
174,987
MiniBooNE
43
29,556
3,284
3,648
BSDS300
63
1,000,000
50,000
250,000
Density estimation on tabular datasets. Following Papamakarios et al. (2017), we evaluate our ten- sorized architectures for density estimation on five tabular datasets. For each dataset, we randomly construct 8 binary tree region graphs (cf. Section 4.1), and build a mixture of tensorized PCs based them. Specif- ically, following our mix-and-match approach Table 1, we build RND-CP and RND--acker architectures which we run for several model sizes K and learning rates (see below). Differently from images, all these datasets contain continuous features, which we model using input layers encoding Gaussian likelihoods. We train all PCs for up to 1000 epochs until convergence, using Adam optimizer and 512 batch size. Furthermore, perform the experiments using three different learning rates: 10-3, 5 10-3, and 10-2, and report the best results according to the validation set log-likelihood.
Results. Fig. E.5 reports the best results from our models, where we see that Tucker layers outperform
CP layers on the two lowest dimensional datasets - Power and Gas which also have the highost number of training data points (see Table E.5). On the other hand, CP-based archilect ures outperform Tucker-based ones on the other three datasets (Hepmass, MiniBooNE and BSDS300), even though the latter have much higher number of trainable parameters then the former for fixed K (i.c., K2 for CP while K3 for Tucker). Our results suggest that the more aggressive over-para weer-parameeerzation of Tucker layers lead to more difficult optimization for high-dimensional datasets and thus for deeper tensorized PCs.
Heppass
Power
Gas
Hepmass
M.BooNE RSDS300
7.5-
MADE
-3.08
3.56
-20.98
-15.59
148.85
RealNVP
0.17
8.33
-18.71
-13.84
153.28
MAF
0.24
10.08
-17.73
-12.24
154.93
X
27
K
21
2
NSF
0.66
13.09
-14.01
-9.22
157.31
MinBoNN
BSD8300
Gaussian
-7.74
-3.58
27.93
-37.24
96.67
(rain)
EiNet-LRS
0.36
4.79
22.46
-34.21
CP [ted]
TTDE
0.46
8.93
-2134
-28.77
143.30
35
1155
Tucker
Tucker (sais)
RND-CP
0.28
5.01
-22.52
-30.69
120.82
RND-Tackkr
0.52
8.41
-23447
-31.30
119.09
Figure E.5: Tucker layers are harder to scale than CP layers high-dimensional UCI datasets. The right table is the one reported in Table 3. The left plots show the train and test liglliklihoods of our architectures as the size K of the layers increases. We observe that increasing K is generally beneficial for CP layers in all UCT datasets (left). However, increasing in Tucker layers can decrease performances for higher-dimenniooall datasets, as shown for the cases of Hepmass and MiniBooNEE. The left plots showing the train set log-likelibne likelihoods (dotted lines) are evidence that the decrease of performances of tensorized PCs with Tucker layers is not due to overfitting.
53

---

Published in Transactions on Machine Learning Research (02/2025)
F How to implement (folded) layers?
In this section, we provide pytorch snippets to implement a folded Categorical imput layer, as well as all the folded sum-product layers we introduced, i.e. Tucker (Eq. (Tucker-layer)), CP (Eq. (CP-layer)), CP (Eq. (CP -laerr), CP and CPXs (Eq. (CPS-layer)) Our tensorized circuit architectures are nothing more than sequential application of such layers. We will release code upon acceptance.
def categorical, layer (batch, paran):
""EEvalutte folded Categorical layer with categories.
:paran batch: Input batch (sun_folds, num_ channels, batch_size)
iparan param: Baи paraneters (aun_folde, K, channehn ireturn log_prob: Output log prob (mun_folds, K, batch_size) ana
cat sat_log_pPa torch.arsnge
paran. lag_ aoftmax
idx_fold terch. arange (bacge (;)) None, Kone] chennel torch.
(batch. (1)) [Noze. None]
11
leg_prob
:, idx_channel batch) (din=1) retura log_prob. transpose -2)
Figure F.1: Pytorch snippet for a folded categorical layer. The snippet details the evaluation of a folded categorical layer, which can be used for any type categorical variable. For instance, it can be used evaluate the log- likeeliohhood of pixels image modeling well as tokens in language modeling. Note how the raw input parameters (param) undergo log-softmax reparameterization (Section 3.2) to model valid log- bog-prbbabilitiss for many categorical distributions.
def tucker layer (log_prob, W):
un*Evaluates a foldad Tucker layar with arity 2 via log log-aun-arp
+
:paran log_prob: Input log prob :paran Layer veights prob donain (nun_folds, :return out out_log_prob: Output log prob (nun_folda, 0, batch_siza)
2, X, batch_size)
W
0)
X
nax_log_prob mag (din=2, keapdin-Trus), values max max_ log__robb)
exp exp_log_pre prob exrch.exp(log_per
put_log_prob nax__og_prob cun (dm(din-1) f.bb,ffb,,ijjoote exp exp_log.probl: 01, exp_log. 11, 1lg raturn aut nut_log_prob
(insun(
11
12
Figure F.2: Pytorch snippet for a folded Tucker layer. folded Tucker layer parameterized by tensor W of shape O K2, and computes F' Tucker layer (Eq. (Tucker-layer)) (((") j in parallel. Specifically, the layer e computes
e {U_ L(m) R:
= W [e (U,,,, TT) 26 (U z(m))
n-1
where & (resp. Eg) denotes folded layer computing the left (resp. right) inputs to g(x), each defined variables z(() (resp. = and W n:: RoxK3 is the parameter matrix of g(r). Note that the snippet.
shapes the tensor W as F x K x K O for convenience with the einsum operation.
54

---

Published in Transactions on Machine Learning Research (02/2025)
def 1p..aayor NI, V2):
E"aEvaluates folded layer arity 2 via 1og-sun-exy
:paran 1og_prob: Input log probe, (uun_folde, 2, K, batch_aize)
:paran иI: Foldad layer veights, (oun_folds, K, 0)
:paran W2: Folded layer seights, (aun_folds, K, 0)
:return out_log_prod: Output log probs, (old_folde, 0, batch_size)
+
+
max_log.pres
keepdin=True), exp exp_ prob torch.exp exp nax_ max_log__roo out_log_proe nax_log_pre cum(din-1) torch.eineun(
W
11
+
"fib, sio,,fioffoo fio,
18
exp exp_log_prode [:, 0l, exp_log.prob 11, 81, 12).1og() out_log_prob
Figure F.3: Pytorch snippet for a folded CP layer. folded CP layer l is parameterized by two equally-sized tensors w and wil) shape F O K, and computes CP layer (Eq. (CP-layer)) p in parallel. Specifically, the layer & computes
F e e(U,_, x((1) = -W!!! & (U.m, z(mH ) +
W ls (U... 2I-h)
where l (resp. (g) denotes a folded layer computing the left (resp. right) inputs to e(x), each defined over variables z(n) (resp. ) and w()) w BoOK K are the parameter matrices of g(n)
n::
def Layyee W) "inEvaluates folded CP-T layer with arity If via log-sun-oxp
:paran log_prob: Input log prob (nun_folde B, X, batch_size) :paran Folded layer seights (nun, foun_folds, X, ireturn out_log_prob: Output log prob (nun_rolda, 0, batch_aiza)
W
leg_prob log_prob. sun(din keepdin-True)
nax max_log.pre torch. excoo.prp pax_lo
keapdin=frus) . values
exp_log_pros out out_log_prod nax_1og_prob. eun (din-11)) torch.
11
12
"2o exp_log_probls, 0l, w).log()
14
return out_log_prob
C layer. A folded CP CP layer parameterized by tensor W of shape F x O K, and computes F CP layer (Eq. (CP llayer) (g(n)) in parallel. Specifically, the layer computes
Figure F.4: Pytorch snippet for folded CP
(UTh, v(w) = W.. (a (LL, 3 l2 n= (()))
where L (resp. E2) denotes folded layer computing the left (resp. right) inputs to e(x), each defined variables =(x) (resp. Z(("),, and W o are the parameter matrices of g(n).
55

---

Published in Transactions on Machine Learning Research (02/2025)
def opxe, Lagg. 61, V2, D-Hone):
u.a Engaauutees CP-IS layer arity log-sun-eay
If D is None then evaluates CP-8 layer.
:paran 1og_prob: Input log probs, (nun_folda, 2, batch_siza) :paran W1: Folded layer veights, (K, 0)
sparan Folded layer Neights, (K, iparan D: Optional veights (nun_folds, 0)
:return log_pog Output log probs, (nun_folds, 0, batch_size)
+
11
nax_log_proe 1og_prob.maxddanx (ax keepdin-True) valuee (rrch.erppoog.rr
W
W 22)
exp_log_pras
nax_log_prob)
18
out out_log_pror nax_log_pros eun (din-11)) torch.
14
"fib, ,io,,,o, jo->fob",
exp_log_probl: [:, 0l, exp_log.probl;; 11, WI, 12).1og()
16
out_log_proo +- D. () unsqueeze (-1) return out_log_prob
18
Figure F.5: Pytorch snippet for Cps layer. A CP layer l is parameterized by two equally-sized matrices w(l) and w of shape x x K, and a matrix D of shape F x O. The layer computes F CP layer (Eq. (CPS-layer) (e(*) FF in parallel, each parameterized by w() and w(2), and then weights their outputs by D. Specifically, the layer & computes
(U..,, v(T))... = dn. O (WoD& & (U z(" O (wlz) &s (
where & (resp. (2) denotes folded layer computing the F left (resp. right) inputs to e(n), each defined over variables ((n) (resp. Z(n)), W w e ROxk are the parameter matrices of p(n), and as a folded- dependent parameter matrix. When D we retrieve CpXs.
56


Reviews:
[{"review_id": "hvGSO95vYp", "reviewer": "Reviewer_FGZY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I have a deep appreciation for papers that bridge disparate concepts, and this work is an excellent example of that. I applaud the authors for setting a high standard of quality. \n\n## Strengths\n\n1. **Clarity and Accessibility**  \nThe paper is written with clarity, consistency, and precision. The inclusion of pedagogical examples, paired with beautiful and illustrative figures, further enhances its accessibility.\n\n2. **Thorough Literature Review** \nThe coverage of related work is remarkably comprehensive. While this makes the paper a long read, it remains highly valuable, especially for readers (like me) who are familiar with only one of the two fields being connected.\n\n3. **Well-Designed Experiments**  \nThe research questions are clearly stated and systematically examined, providing compelling evidence to support the authors’ claims.\n\n4. **Potential for Broader Impact**\nI also see potential connections to other diverse areas, such as copulas, multi-marginal optimal transport, and symbolic regression. While these connections are outside the immediate scope of this paper, they represent exciting opportunities for future research that could build on the solid foundation laid here.\n\n## Weaknesses\n\nWhile this paper is already excellent, I'd suggest the following to make it even stronger:\n\n1. **Practical Guidance for Implementation**  \nThe only thing I found lacking is a few pointers to how one would start exploring these topics. While undoubtedly powerful, the presented methodologically is non-trivial to implement, so it would be helpful to get some more specific recommendations on the practical implementation. \n\nFinally, a minor suggestion would be to clarify that Propositions 1 and 2 are in fact constructive, as shown in the appendix.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper makes an exciting and meaningful connection between two areas in machine learning, circuit representations and tensor factorizations, that have traditionally developed independently. By bridging these fields, the authors create a generalized framework that:\n\n- Expands popular tensor factorizations using a circuit-based perspective.  \n- Offers a modular approach to systematically construct tensorized circuit architectures.  \n- Establishes a single pipeline for exploring and optimizing these models, bridging gaps in both theory and practice.  \n\nThe paper combines rigorous theory with comprehensive empirical evaluations, offering clear recommendations for practitioners and opening new perspectives for future research.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I'll recommend acceptance regardless, but please see my suggestions above.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "OZfXv7yhA6", "reviewer": "Reviewer_GfCJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. Innovative Integration of Two Domains: The framework effectively unifies tensor factorizations and circuits, which could have significant impact on both fields by enabling cross-domain techniques to benefit from advances in the other.\n2. Modular and Flexible Model Design: The “Lego block” modularity is a valuable contribution, allowing researchers and practitioners to design and test different architectures systematically and efficiently.\n3. Empirical Validation and Efficiency Gains**: The empirical results emphasize the proposed models’ computational efficiency, showing parameter savings while maintaining expressiveness, which could be particularly advantageous in resource-constrained environments.\n4.Accessibility of Mathematical Notation: The paper employs extensive and consistent notation, which may make it easier for readers that might not deeply familiar with tensor factorizations or circuits to fully grasp the framework. \n5. Broad Application Potential: The framework’s flexibility supports applications in probabilistic modeling, neuro-symbolic AI, and tasks that require reliable and interpretable probabilistic inferences. \n\nWeaknesses and Areas for Improvement\n\n1. Expanded Benchmarking: The empirical evaluations, though thorough, might benefit from additional benchmarks across diverse datasets and tasks, Applications to real-world data (e.g., in text, image, or biological data) would strengthen the impact, especially in domains where tensor factorizations and probabilistic circuits are already in use beyond image dataset compression.\n2.Opportunity Boxes: Interesting idea, however, they seem to be better be part of the discussion section of the paper instead of floating in the text. Makes the text read as a review paper instead of a research one.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper establish a formal connection between tensor factorizations and circuit representations. Within this formal connection, the paper focuses on non-negative tensor factorization and its relations to probabilistic circuits. Furthermore, the paper introduces a \"Lego block\" modular approach to building tensorized circuit architectures, enabling flexible model construction and tractable exploration of probabilistic models with complex factorization structures. \n\nKey contributions include:\n1. Unified Framework for Tensorized Circuits: The paper proposes a general framework that translates tensor factorizations into circuit representations, notably including hierarchical formulations like Tucker factorizations. This framework provides a systematic way to explore and unify various tensor and circuit-based probabilistic models.\n2. Parameter-Efficient Architectures: The proposed framework leverages tensor factorizations to improve the parameter efficiency of probabilistic circuits (PCs) by compressing circuit parameters into compact tensor representations.\n3. Pipeline for Model Construction: By representing tensor and circuit factorizations as modular components, the authors create a versatile pipeline for assembling tensorized circuit architectures, thus supporting the construction of complex, hierarchically structured models.\n\nOverall, the work presents an exciting new perspective that may open several avenues for future research at the intersection of tensor factorizations and circuit representations, with promising applications in a range of fields where probabilistic modeling is essential.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Major changes:\n\nImprove readability by:\n\n1.Move additional related work to the end of the manuscript after the experimental sections (Sections 6 and 7).\n2. Move opportunities and Takeaways into Discussion section.\n\nMinor Changes\n1. Decrease the mention of applications throughout the text by introducing it into either in introduction or discussion sections for readability. \n2. Would be ideal to compare the model beyond image compression. However, given that previous literature seem to focus on image dataset compression I would not penalize the manuscript because of its absence.\n3. Include ImageNet into the set of datasets given that HCLTs include it ( (Liu et al., 2022; 2023a)", "broader_impact_concerns": "The authors might wanna address ethical implications and potential broader impacts, especially given that tensorized circuits are relevant to sensitive applications in autonomous decision-making, and probabilistic modeling for high-stakes domains. Might wanna include a sentence or two about evaluating the fairness and bias of the models after compression.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "FR1k3K54zk", "reviewer": "Reviewer_3GRw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Even though the paper is mostly well-written, and arguments are easy to follow, it uses too much heavy notations at points. This might be unavoidable given the topic of the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies relationships and connections between circuit representation and tensor factorization approaches to representing, learning, and sampling from probabilistic distributions. Although there have been other works that examined these connections, this current submission appears to be a more comprehensive study of the topic.\n\nAuthors also highlight a number of opportunities for further research in the intersection between these areas. Overall, I believe many people in the ML community would find such a survey useful.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "None", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "PEfep3Rjxp", "reviewer": "Reviewer_uaDR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The numerous examples provided make the study of tensor factorization quite clear and easy to follow.\n2. The method demonstrates efficiency in both speed and GPU usage, showcasing the effectiveness of NN-CP factorization.\n\nWeaknesses:\n1. The direct benefit of framing tensor factorization in the language of circuits is not clear, and the paper lacks significant new theoretical contributions.\n2. The discussion is limited to the \"linear\" setting, with the high-order tensor considered purely in terms of decomposition. The deeper implications and practical usage of this approach are not well explored. Is there any possibility of generalizing this method to incorporate nonlinear activation? Some literature suggests that nonlinear approximations can be more efficient than their linear counterparts.\n3. A well-known issue with tensor factorization is the non-uniqueness of the factorization. A natural question arises: does this method suffer from the same problem? (Maybe add a bit ablation study by introducing perturbation to discuss the uniqueness) The paper mentions that the methods compared in the empirical experiments use different architectures but fall within the same model class. While this is a challenging question, addressing it would add important context to the study.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "1. This paper extends tensor factorization methods and their hierarchical formulations into the framework of circuits.\n2. Numerous demonstration graphs are provided, clearly illustrating the concepts of tensor factorization and circuit representation.\n3. The method proposed in this paper is shown to be faster, more memory-efficient, and capable of strong performance compared to other approaches on datasets such as MNIST and CelebA.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Provide examples that illustrate the relationship between the current circuit-based approach and the issue of non-uniqueness in tensor decomposition. Specifically, include a demonstration (possibly in the appendix) that shows how the decomposition of a tensor differs across various methods.", "broader_impact_concerns": "NA. The tensor factorization problem is a fundamental problem and is really important in various research areas including computer vision, large-scale optimization and deep learning such as video generation.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a novel connection between tensor factorizations and circuits and demonstrates strong theoretical and practical contributions. The authors addressed reviewer concerns thoroughly, improving clarity and experiments. 

The reviews strongly support the quality of the paper, with reviewers noting its contributions and addressing areas for improvement. Reviewers agreed that the paper provides novel insights, particularly in establishing a formal connection between tensor factorizations and circuits. This connection was identified as a major strength, enabling advancements in both fields. The modular framework and empirical results further highlight the paper’s practical contributions, which were praised for their clarity and accessibility.

The authors addressed several concerns raised by reviewers. On the issue of non-uniqueness in tensor factorizations, Reviewer uaDR noted this limitation, and the authors responded with a detailed discussion in Section 4 and robust experiments demonstrating stability. Reviewer FGZY suggested adding implementation guidance, which the authors addressed by including PyTorch snippets and committing to release code. To broaden the empirical scope, as requested by Reviewer GfCJ, the authors conducted additional experiments, such as density estimation on UCI datasets, and explained why ImageNet comparisons were omitted.
Decision: Accept (poster)