Greedy Structure Search for Sum-Product Networks

1 Introduction

Sum-product networks (SPNs) are a recently-proposed class of probabilistic models in which exact inference is guaranteed to take linear time in the size of the model. They can efficiently represent a larger class of distributions than some other models such as mixture models and thin junction trees [Poon and Domingos, 2011]. SPN parameters can be learned using expectation-maximization or gradient descent in both the generative and discriminative settings [Poon and Domingos, 2011; Gens and Domingos, 2012].

Results [Gens and Domingos, 2012] on twenty real-world datasets compare SPNs to Bayesian networks learned using the WinMine toolkit [Chickering, 2002] and to Markov networks learned using two other methods [Della Pietra et al., 1997; Ravikumar et al., 2010]. In these experiments SPNs and graphical models fit the data with comparable likelihood, but the inference accuracy of SPNs is better, as measured using conditional-likelihood. Also, SPN inference is about two orders of magnitude faster. Similar results [Rooshenas and Lowd, 2014] were found when comparing an augmented SPN to mixtures of trees [Meila and Jordan, 2001] and latent tree models [Choi et al., 2011].

SPNs are represented using a directed, acyclic graph (DAG) of sum and product nodes. Recent approaches to SPN learning focus on the structure of this graph along with its parameters [Rooshenas and Lowd, 2014; Gens and Domingos, 2013; Peharz et al., 2013; Dennis and Ventura, 2012]. These algorithms add nodes in either a top-down or bottomup fashion until a complete SPN is constructed. In contrast, the algorithm introduced in this paper uses a search procedure that incrementally expands a simple, but complete, SPN to produce a series of increasingly complex SPNs.

SPNs and multilinear arithmetic circuits (MACs), a model from circuit complexity theory, are closely related. Both are represented by DAGs whose internal nodes are sums and products and both compute multilinear polynomials in their leaf nodes. Multilinear arithmetic formulas (MAFs) are MACs whose DAG is a tree. Raz has shown that MACs are, in a sense, more powerful than MAFs: he proves a certain polynomial to be computable by a MAC of polynomial-size but only computable by a MAF of super-polynomial-size [Raz, 2006].

In a way this result is irrelevant to SPNs. With SPNs we are concerned with representing probability distributions, not computing polynomials. In other words, we care that an SPN computes a certain function, not that it uses a certain polynomial to do so. Still we conjecture that DAG-structured SPNs are more powerful than tree-structured SPNs with respect to their ability to compactly represent probability distributions.

We do not attempt to prove or disprove this conjecture here. Instead we introduce a greedy structure search algorithm that learns DAG-structured SPNs and compare this with a structure learning algorithm that learns tree-structured SPNs. Empirical results provide evidence that DAG-SPNs have advantages over tree-SPNs. We also prove a theorem that helps clarify and simplify certain SPN concepts and helps us define a useful approximate likelihood function for SPNs.

2 Previous Work

Delalleau & Bengio [2011] connect SPNs to work in both circuit complexity and deep learning. They provide theoretical evidence for the utility of deep learning by proving lower bounds on the size of shallow (depth two) sum-product networks for two classes of functions F and G. They show an exponential separation in the size of shallow and deep SPNs; to compute functions in F a shallow SPN requires at least 2√n-1 nodes while a deep SPN requires only n - 1 nodes.

Darwiche [2003] introduced the idea of representing a Bayesian network using polynomials, called network polynomials, and of computing these polynomials using arithmetic circuits. He also showed how to perform inference using network polynomials and their corresponding circuits. This work was foundational to the introduction of SPNs by Poon &Domingos [2011].

Lowd & Domingos [2008] proposed the first search algorithm for learning the structure of arithmetic circuits. Since an arithmetic circuit can be converted to an equivalent SPN, this work can be thought of as the first SPN structure search algorithm. Their algorithm builds an arithmetic circuit that maintains equivalence with a Bayesian network. A result of this equivalence constraint is that a single step in the search process can dramatically increase the size of the arithmetic circuit. Our search algorithm increases the size of an SPN by a modest amount at each step.

Several SPN structure learning algorithms have been proposed; these we denote and reference as follows: DV [Dennis and Ventura, 2012], GD [Gens and Domingos, 2013], RL [Rooshenas and Lowd, 2014], and PGP [Peharz et al., 2013]. DV, GD, and RL are top-down SPN structure learning algorithms that start with a root node and recursively add children until a full SPN has been built. DV uses an ad-hoc clustering method to build several SPNs that are then merged together; GD and RL take a more principled approach that creates product node children using tests of independence and that creates sum node children by learning naive Bayes models. GD and RL construct trees, with the leaves of GD being univariate distributions and the leaves of RL being multivariate distributions [Lowd and Rooshenas, 2013]; the graphs constructed by DV and PGP are not restricted to trees. PGP uses a bottom-up approach, merging smaller SPNs into larger ones. Another approach learns an SPN structure by sampling from a prior over tree or DAG structures [Lee et al., 2014]; no experimental results have been reported yet for this algorithm.

One of the difficulties in SPN structure learning has been taking advantage of the architectural flexibility of SPNs. GD and RL use well-justified algorithms but limit themselves to learning SPN trees-except at the leaf nodes in the case of RL, which can be arithmetic-circuit representations of Markov networks. One of the aims of this paper is to provide an algorithm that employs the principled approaches of GD and RL while learning DAG-structured SPN.

3 Sum-Product Networks

Indicators for a random variable Xi are defined as

where j is one of the values that Xi can take. An SPN can be represented as a rooted DAG whose leaf nodes are indicators and whose internal nodes are sums and products. If an indicator for Xi appears in an SPN then its scope contains Xi. Let X = {X1, . . . , Xm} be the set of random variables in the scope of an SPN.

Definition 1. A sum-product network (SPN) is:

1. an indicator node,
2. a product node whose children are SPNs with disjoint scopes, or

3. a sum node whose children are SPNs with the same scope, and whose edges to these children have nonnegative weights.

We do not use the similar definition from Gens & Domingos [2013], even though it handles continuous variables more naturally, because Definition 1 simplifies the discussion in this paper. We assume without loss of generality that the children of product nodes are sum nodes and that the children of sums are either products or indicators.

Definition 2 (based on Chan & Darwiche [2006]). A tree c embedded within an SPN is a complete sub-circuit if and only if it can be constructed recursively, starting from the root of c, by including all children of a product node p (and the edges connecting them to p), and exactly one child of a sum node s (and the edge connecting it to s). Let C be the set of all complete sub-circuits embedded in an SPN.

An SPN computes a multilinear polynomial in which indicators appear as variables. For any node n in an SPN let fn be the polynomial computed by it and let ch(n) be its children. Let wst be the weight on the edge between sum node s and its child t; we assume that ∑t∈ch(s) wst = 1. The root node r of an SPN computes polynomial fr as follows. If r is the indicator node for λXi=j then fr = λXi=j; if r is a product node then fr = ∏t∈ch(r) ft; if r is a sum node then fr = ∑t∈ch(r) wrtft. We say that an SPN computes the polynomial computed by its root node. The polynomial computed by a complete sub-circuit is defined similarly. For input x and polynomial fn we let fn(x) be the value of fn at input x. For input x and gc, the polynomial computed by complete sub-circuit c, we let c(x) = gc(x) be the value of gc at input x.

A proof of the following theorem appears in the appendix.

Theorem 1. For some SPN let r be its root and let gc be the polynomial computed by c ∈ C. Then fr = ∑c∈C gc.

Using Theorem 1 we place a simple probabilistic interpretation on the computation of an SPN. For c ∈ C the polynomial gc = ∏w∈Wc w ∏c (λX), where Wc is the multiset of weights in c and ∏c (λX) is the product of indicators in c. We interpret this by letting ∏w∈Wc w = P(Z=c) and ∏c (λX) = P (X|Z= c), where Z is a hidden variable whose values are the circuits in C. Therefore gc = P(X, Z=c) and

Thus an SPN represents a joint distribution over X. From Definition 1 we see that each node n in an SPN is the root of its own SPN. Let Φn be the distribution represented by the SPN rooted at n.

SPNs compute the marginal probability of any subset of X when the indicators for variables not in the subset are all set to one. Thus marginal and, consequently, conditional inference always takes time linear in the size of the SPN [Poon and Domingos, 2011]. Inferring argmax X,Z P(X, Z), called the

most probable explanation (MPE), is also done in linear time. After replacing sum nodes with max nodes, the SPN is evaluated in an upward pass followed by a downward pass. The downward pass assigns the (or an) MPE circuit to Z and assigns values to any unobserved variables in X. The circuit is constructed by starting at the root, traversing to all children of product nodes and at sum nodes traversing to the (or a) child whose weighted value is a maximum [Poon and Domingos, 2011; Chan and Darwiche, 2006]. We let c∗x be an MPE circuit for variable setting X = x.

Poon & Domingos [2011] associate with each sum node s a hidden variable Hs whose values are the children of s. Similar to how we see hidden variable Z as being summed out of P(X,Z), they view an SPN as summing out H from P(X,H), where H is the set of all Hs. The benefits of our interpretation are a simpler mathematical formulation and a clearer relationship to MPE inference. We do make use of the variables in H, however, and relate them to Z by way of complete sub-circuits as follows. A complete sub-circuit c assigns values to a subset of H and all of the observed variables. If the edge from s to t ∈ ch(s) is in c then Hs = t. If the indicator node for λXi=j is in c then Xi = j. Let Hc be the set of variables to which c assigns values. See Figure 1.

4 SPN Structure Search

To learn an SPN, our greedy structure search algorithm uses a training set T that contains i.i.d. samples of the variables in X. For each product node p we use T to create another dataset Tp. We infer for each training instance x ∈ T the MPE state X=x, Z=c∗x , which in turn assigns values to the variables in Hc∗x . If p is in c∗x (for some x ∈ T) then all of its children are in c∗x as well and c∗x assigns values to all Hs, s ∈ ch(p). Thus MPE inference gives us a sample of the hidden variables associated with children of p; this sample is added to Tp.

In brief, a step in the search is as follows. We use the datasets Tp to select a product node p∗ (Section 4.2). We pass Tp∗ to modified versions of the variable- and instancepartitioning procedures (Section 4.2) found in GD [Gens and Domingos, 2013]. The structure modification algorithm (Section 4.1) then uses the partitioning of Tp∗ to change the SPN structure at p∗ . As described, variable- and instancepartitioning in GD applies at the leaves of half-formed SPNs. The use of the datasets Tp broadens the applicability of these procedures to the internal nodes of SPNs.

4.1 Search Operator

The structure modification algorithm, or structure operator, we use is called MIXCLONES and is outlined in Algorithm 1. An example of applying this operator to an SPN is shown in Figure 2. By analyzing the scopes of the newly added nodes, we can see that the operator transforms one SPN into another SPN. The new SPN has more parameters, making it more flexible in approximating a target distribution.

Product node p∗ , a subset of its children S1, and an integer k are given as input to MIXCLONES. The set S1 identifies the sub-distribution ∏s′∈S1 Φs′ , which is assumed to not fit the training data well enough. MIXCLONES replaces it with a more expressive distribution: a mixture of k clones of the subdistribution (where the mixing coefficients and parameters of each sub-distribution are subsequently changed, with the goal of better fitting the training data).

MIXCLONES builds the mixture of clones as follows. It removes the connections between p∗ and the nodes in S1. It then creates k-1 clone sets, S2, . . . , Sk, of the set S1; a clone set contains, for each s′ ∈ S1, a corresponding sum node with the same set of children as s′ . MIXCLONES creates product node pi for each set Si (including p1 for S1), and adds pi as the parent of the nodes in Si. The product nodes pi now represent the k clones of the sub-distribution ∏s′∈S1 Φs′ . Adding a new sum node s as parent to the nodes pi creates the mixture of clones: Φs = ∑i wspi ∏s′∈Si Φs′ . The mixture is tied back in to the SPN by adding p∗ as the parent of s. Sum node s is returned.

The weights wspi of s are the mixing coefficients of the mixture model Φs and the weights of the sum nodes in S1, . . . , Sk are the sub-distribution parameters. Outside of MIXCLONES these parameters are chosen to (indirectly) increase the training set likelihood.

4.2 Search Algorithm

This section describes and justifies Algorithm 2 (SEARCHSPN), our SPN structure search procedure. At a high level it is simply a repeated application of MIXCLONES followed by some parameter updating. This requires selecting p∗ , S1, and k at each search iteration. We now explain how these selections are made and how parameter updating is done.

Selecting p∗ .

We think of product node p∗ as identifying the weakest point in the SPN structure, where we say a node is weaker than another node if it contributes less to the likelihood. An approximate likelihood function ˜ L gives us a simple method for measuring weakness. Using Theorem 1, the true likelihood can be written as L(fr|T ) = ∏x∈T ∑c∈C c(x). The approximation is derived from L by replacing the sum with a max operator. Thus

where c∗x is, as defined before, the circuit whose output is maximal for input x.

Remember that c∗x (x) = ∏w∈Wc∗x w, where here we assume that when X=x the indicators in c∗x take the value one. Substituting this expression into Equation 1 we see that ˜ L = ∏x∈T ∏w∈Wc∗x w is a product of weights in the SPN; weights in the product may appear more than once. We will reorder the product of weights to assign partial responsibility for the value of ˜ L to each product node.

We define the multiset Wr for root node r and, letting P be the set of product nodes, define the multiset Wp for every p ∈ P. For some x ∈ T, if product node p and weight wst are both in c∗x , and p is a parent of s, then we add wst to Wp; if wst is in c∗x and s = r then we add wst to Wr. With these definitions it is possible to rewrite ˜ L as

Product node p is said to be responsible for multiplying into ˜ L the value ∏w∈Wp w. Therefore p∗ = argmin p ∏w∈Wp w is the product node that contributes least to a high value of ˜ L.

Algorithm 1 MIXCLONES(p∗ , S1, k)

Input: product node p∗ , S1 ⊆ ch(p∗ ), k > 1 Output: sum node s remove the edge between p∗ and each s ∈ S1 s ← new sum node set p∗ as the parent of s S2, . . . , Sk ← k - 1 clones of S1 for all Si ∈ {S1, . . . , Sk} do pi ← new product node set s as the parent of pi set pi as the parent of each s′ ∈ Si end for return s

Algorithm 2 SEARCHSPN(N, T )

Input: SPNN, training instances T

while stop criteria not met do p∗ ← argmin p ∏w∈Wp w use Tp∗ to partition {Hs|s ∈ ch(p∗ )} into approximately independent subsets Vj for all Sj ={s|Hs ∈ Vj} where |Sj | > 1 do partition Tp∗ into k groups Ti of similar instances, ignoring variables not in Vj s ←MIXCLONES(p∗ , Sj, k) update weights of s and its grandchildren end for end while

Selecting S1 and k.

With p∗ selected, we would like to change the structure of the SPN at p∗ such that the distribution Φp∗ = ∏s∈ch(p∗ ) Φs better fits the training data T. Since it is unclear how to do this directly, SEARCHSPN instead solves a simpler, related problem that admits the use of the variable- and instancepartitioning methods of GD. More specifically, it changes the structure of the SPN such that the distribution Ψp∗ = ∏s∈ch(p∗ ) Ψs better fits the training set Tp∗, where Ψs, for each s ∈ ch(p∗ ), is a categorical distribution over the variable Hs and its parameters are the weights of s.

If the variables in Vp∗ = {Hs|s ∈ ch(p∗ )} are mutually independent then Ψp∗ is an appropriate model. If, however, dependencies exist amongst the variables in some subset Vj ⊆ Vp∗ then there will be a loss of likelihood. SEARCHSPN attempts to detect such subsets Vj that also have no dependencies with the other variables Vp∗ \ Vj. Calling MIXCLONES with S1 set to {s|Hs ∈ Vj} changes the structure of the SPN to better model the dependencies in Vj. We now describe how SEARCHSPN selects subsets Vj and how it fits the model created by MIXCLONES to the data Tp∗ .

Variable-partitioning, or selecting subsets Vj, can be done empirically by analyzing Tp∗ as follows. SEARCHSPN detects pairwise dependencies among the variables in Vp∗, builds a graph representation of these dependencies, and partitions Vp∗ by finding the connected components in the graph. It uses a normalized mutual information measure (and tunable threshold τ) to test for pairwise dependencies. MIXCLONES is called once for each non-singleton subset in the partition of Vp∗ . If the partition only contains singleton subsets then p∗ is added to a blacklist so that it is not selected again and a new search iteration is started.

After selecting Vj ⊆ Vp∗, SEARCHSPN builds a mixture model to explain the dependencies amongst the variables in Vj. It does this by fitting the model to TVj , the portion of the dataset Tp∗ that involves only variables in Vj. The mixture model is defined as ∑ki=1 wi ∏Hs∈Vj Ψ(i) s , where the wi are mixing coefficients and each component ∏Hs∈Vj Ψ(i) s is a product of categorical distributions Ψ(i) s over the variables in Vj. We use K-means to partition TVj into k datasets T1, . . . , Tk and, assigning Ti to the ith component, set the mixture model parameters to their maximum likelihood estimate. The parameters of the ith categorical distribution over Hs, Ψ(i) s , are set to maximize its likelihood given the dataset Ti, where we ignore all variables in Ti except Hs. Mixture coefficient wi is set to |Ti|/|TVj |.

We could use hard EM instead of K-means, but Rooshenas & Lowd report little difference between the two methods [Rooshenas and Lowd, 2014]. We run K-means several times, increasing k on each run, and select the k that leads to the mixture model with highest penalized likelihood. Like GD we penalize the likelihood by placing an exponential prior on k, P(k) ∝ exp(-γk|Vj|), where γ is a tunable parameter.

Updating Parameters and Efficiency.

SEARCHSPN calls MIXCLONES with S1 set to {s|Hs ∈ Vj} and this returns a sum node that we denote sVj . The weights of sVj are set to the mixing coefficients wi and the weights of the sum nodes in S1, . . . , Sk (the grandchildren of sVj ) are set using the distributions Ψ(i) s as follows. Let Si be the grandchildren of sVj from its ith child. We set the weights of each s′ ∈ Si to the parameters of Ψ(i) s , where s is chosen as follows. If Si = S1 then we set s = s′ ; otherwise we set s to be the node in S1 that s′ is a clone of.

A key technical problem in implementing our search algorithm is maintaining the training sets Tp as the SPN graph structure changes. The obvious method is to re-build these sets from scratch after each search step, but this requires a full pass through the dataset, evaluating the SPN for each instance. We avoid this (to almost the same effect) by updating only those sets directly affected by the search step.

Our structure search algorithm uses data likelihood as its scoring function. We stop when the likelihood of a validation set reaches a maximum. To reduce the computational burden we take many steps in the search space before computing the likelihood. If the likelihood begins to drop we intelligently re-trace our steps to find an SPN with high likelihood.

5 Experiments

We compare SEARCHSPN and LEARNSPN (from GD) on twenty datasets that were recently used in Rooshenas and Lowd [2014] and Gens and Domingos [2013]. We also compare the algorithms on a set of artificially-generated datasets based on the permanent of an n × n matrix. For each dataset we run a grid search over hyperparameter values γ ∈ {0.1, 0.3, 1.0, 3.0, 10.0} and τ ∈ {0.003, 0.01, 0.03, 0.1, 0.3}, the cluster penalty and pairwise dependency threshold, respectively. Chosen models are those with the highest likelihood on a validation set. Table 1 and Table 2 show the mean test set likelihood over ten runs.

We implement LEARNSPN using the same variable- and instance-partitioning code that we use in SEARCHSPN. We do this to make the algorithms as similar as possible so that result differences in our experiments can be attributed as much as possible to the different classes of SPN structure that the algorithms are able to learn (DAG vs. tree).

5.1 Permanent Distribution

A result from circuit complexity theory shows that a MAF cannot compute the permanent of an n × n matrix unless it is super-polynomial in size [Raz, 2009]. We also assume it is a difficult problem for MACs since computing the permanent is #P-complete [Valiant, 1979].

We build MNPerm, a set of artificial datasets based on the permanent. Let aij be the entries in an n×n matrix. Let Sn be the set of all permutations of {1, . . . , n}. Then the permanent is defined as ∑σ∈Sn ∏ni=1 aiσ(i). Viewing the entries aij as variables we see that this expression is a multilinear polynomial. It defines an unnormalized probability distribution over variables X1, . . . ,Xn if we view the entries aij as indicator variables, where aij = λXi=j. Thus each variable Xi is discrete and can take one of n values. This distribution evaluates to zero unless each variable takes a value that is different from the value taken by every other variable. The partition function is n!.

For each n ∈ {2, . . . , 9} we construct a fully-connected pairwise Markov network whose distribution is a softened version of the permanent distribution. We do this by defining the factor for each pair of variables Xi, Xj to take the value one if Xi = Xj and take the value ten otherwise. The datasets used to produce the results in Table 2 were generated by sampling from the constructed Markov networks using Gibbs sampling.

5.2 Observations

The performance of SEARCHSPN is better than LEARNSPN on thirteen of the twenty datasets and worse on six of them. A similar outcome is seen when comparing the SEARCHSPN results with the results reported in [Gens and Domingos, 2013], although statistical significance cannot be determined in this comparison.

Comparing to the results reported in [Rooshenas and Lowd, 2014]-again without any significance claim-we see that SEARCHSPN only gets a higher likelihood on the Ad dataset. One explanation for the success of the RL models is that, like SEARCHSPN models, they are not restricted to being tree-structured. Leaf nodes in RL models are multivariate Markov networks modeled using arithmetic circuits that are not restricted to having a tree structure.

SEARCHSPN arguably has an advantage over RL models in that it seems to produce smaller networks in shorter training times. We have model-size and training-time data for RL models [Rooshenas, 2014] on six of the datasets (NLTCS, KDDCup 2k, Book, 20 Newsgrp., and Ad). The models learned by RL range in size from 385k to 1.2M nodes and the DAG-SPNs ranged in size from 2k to 114k nodes. Learning times for RL ranged from 19m to 15.7h and the DAG-SPNs ranged from 3m to 1.4h. For any of these datasets the DAGSPN has at least 10 times fewer nodes and its learning time is at least 7 times faster. The learning-time results are less definitive than the model-size results since some or all of the difference reported here could be due to differences in such factors as the hardware and programming language used in the experiments, and not due to differences in the algorithms. While further investigation is warranted, SEARCHSPN seems to produce compact models quickly.

The results in Table 2 for the MNPerm datasets show a clear separation in likelihood between DAG-SPNs and treeSPNs as n increases. And the difference does not seem due to a difference in the size of the learned SPNs since the DAGstructured SPNs are only marginally larger. These results support the idea that DAG-structured SPNs have a distinct advantage over tree-structured SPNs.

6 Conclusion

SEARCHSPN is the first algorithm designed for SPNs that takes a search approach to structure-learning. In contrast with previous work it does not dramatically increase the size of the SPN at any point in the search and it uses principled methods without restricting the class of learned structure to trees.

We have linked SPNs to the MAC and MAF models from circuit complexity theory and highlighted some interesting connections to that field that suggest tree-structured models may be less powerful than DAG-structured models. Our experiments indicate that being able to learn a wider class of SPN structures can be advantageous. Future work includes better understanding what types of datasets and distributions benefit from a DAG-structured SPN and what types can be well-modeled with tree-structured SPNs.

A Proof of Theorem 1

Proof. The proof is by induction from the leaf nodes to the root node; thus if r has children we assume that for any t ∈ ch(r) ft = ∑c∈Ct gc. The proof is also broken into the cases from Definition 1. Let Cn be the set of complete sub-circuits in the SPN rooted at node n (thus C = Cr).

Case 1. Let r be an indicator node for λX=i. Then fr = λX=i. Since C = {c′ }, where c′ consists of the node r, gc′ = λX=i. Thus fr = gc′ = ∑c∈C gc.

Case 2. Let r be a product node whose children are SPNs with disjoint scopes. Let ch(r) = {t1, . . . , tm}, C × be the Cartesian product ∏mi=1 Cti , and c× = (c1, . . . , cm) ∈ C ×. The scopes of the children of r are disjoint so any two circuits ci, cj , ci ̸= cj from c× have no common nodes or edges. Thus every c× yields a unique c ∈ C using the following construction. Add r, add r's edges, and add the nodes and edges in each ci; then gc = ∏mi=1 gci . Every circuit in C can be constructed in this manner. Thus the construction is a one-to-one and onto mapping from C × to C. By definition fr = ∏mi=1 fti and by the inductive hypothesis fr = ∏mi=1 ∑c′∈Cti gc′ . Multiplying out the right-hand side yields fr = ∑c×∈C× ∏mi=1 gci and applying the mapping yields fr = ∑c∈C gc.

Case 3. Assume r is a sum node whose children are SPNs with the same scope. Let C ∪ = ⋃t∈ch(r) Ct. Every c′ ∈ C ∪ yields a unique c ∈ C using the following construction. Add r, add the edge from r to the root t of c′ , and add the nodes and edges in c′ ; then gc = wrtgc′ . Every circuit in C can be constructed in this manner. Thus the construction is a one-to-one and onto mapping from C ∪ to C. By definition fr = ∑t∈ch(r) wrtft and by the inductive hypothesis fr = ∑t∈ch(r) wrt ∑c′∈Ct gc′ . The double summation ranges over C ∪ so fr = ∑c′∈C∪ wrtgc′ . Applying the mapping yields fr = ∑c∈C gc.