Symmetric Algebraic Circuits and
Homomorphism Polynomials

We broaden the scope of [6] twofold by precisely characterising the symmetric circuit complexity of all, i.e. not necessarily uniform, graph motif parameters. To that end, we observe that the matrix-symmetric polynomials $p\in \mathbb{Q}[{𝒳}_{n,m}]$ are precisely those that can be written as linear combination of homomorphism polynomials, cf. Lemma 4: For a bipartite multigraph $F$ with bipartition $A\uplus B$, the homomorphism polynomial ${\mathrm{hom}}_{F,n,m}\in \mathbb{Q}[{𝒳}_{n,m}]$ is defined as

The name is justified by the fact that ${\mathrm{hom}}_{F,n,m}$ evaluates to the number of homomorphisms from $F$ to a $(n,m)$-vertex bipartite graph $G$ when substituting the bi-adjacency matrix of $G$ for the matrix of variables ${𝒳}_{n,m}$.

Our main result asserts that the symmetric complexity of a family $(p_{n,m})$ of matrix-symmetric polynomials is completely governed by the treewidth of the graphs whose homomorphism polynomials arise in linear expansions¹¹1In stark contrast to uniform graph motif parameters studied by [6], non-uniform graph motif parameters generally do not admit a unique expansion as linear combinations of homomorphism counts. of $(p_{n,m})$. By symmetric complexity we mean the smallest possible orbit size of a family ${(C_{n,m})}_{n,m\in \mathbb{N}}$ of symmetric circuits representing ${(p_{n,m})}_{n,m\in \mathbb{N}}$. This is the number of gates of $C_{n,m}$ in the largest orbit of the action of ${\mathrm{𝐒𝐲𝐦}}_n\times {\mathrm{𝐒𝐲𝐦}}_m$ on $C_{n,m}$ (see Section 2). Note that lower bounds on orbit size imply lower bounds on the total number of gates in a circuit but not vice versa. We also show that orbit size, not total size, is the correct measure that allows us to build our theory, cf. Theorem 5.

To state our main result, let ${𝔗}_{n,m}^k$ denote, for every $k,n,m\in \mathbb{N}$, the collection of all polynomials that can be obtained as linear combinations of homomorphism polynomials ${\mathrm{hom}}_{F,n,m}$ for graphs $F$ of treewidth less than $k$.

It is instructive to consider again the permanent ${\mathrm{perm}}_n={\sum }_{\pi \in {\mathrm{𝐒𝐲𝐦}}_n}{\prod }_{i\in [n]}{x}_{i\pi (i)}$. This is not a homomorphism polynomial and not even a uniform graph motif parameter but it can be seen as counting, given a bipartite graph $G$ instantiated as a bi-adjacency matrix ${𝒳}_{n,n}$, the number of subgraphs isomorphic to an $n$-matching. By Möbius inversion [12, Corollary A.3], subgraph counts can be written as a linear combination of homomorphism counts. One consequence of Theorem 1 together with the exponential lower bound on symmetric circuits for the permanent [15] is that ${\mathrm{perm}}_n$ cannot be expressed as a linear combination of homomorphism polynomials of bounded treewidth. Alternatively, we can understand one direction of Theorem 1 as a vast (in fact, as vast as possible) generalisation of the lower bound on the permanent. Indeed, the theorem captures all super-polynomial lower bounds on the orbit size of symmetric circuits for matrix-symmetric polynomials.

Theorem 1 stipulates that, to derive a super-polynomial lower bound for some family $p_{n,m}$, one must show that there is no constant $k\in \mathbb{N}$ such that $p_{n,m}\in {𝔗}_{n,m}^k$ for all $n,m\in \mathbb{N}$. This, however, seems to be difficult with the presently available techniques. Therefore, our next goal is to give more usable characterisations of ${𝔗}_{n,m}^k$ via a descriptive complexity measure for graph parameters, namely in terms of counting width. The counting width [13, 10] of a graph parameter $p$ is defined as the smallest $k\in \mathbb{N}$ such that whenever two graphs $G$, $H$ are indistinguishable by the $k$-dimensional Weisfeiler-Leman algorithm, then $p(G)=p(H)$, see also Definition 6 or [12, Definition 6.1]. The Weisfeiler-Leman indistinguishability on graphs is a standard relaxation of graph isomorphism (see [4, 27]), and coincides with equivalence in the $(k+1)$-variable fragment of first-order logic with counting quantifiers.

Counting width is well-studied in finite model theory and affords lower bounds, usually via the so-called Cai-Fürer-Immerman construction [4]. For Boolean circuits, a tight relationship between the counting width and orbit size of symmetric circuits is known [1].

The aforementioned exponential lower bound for symmetric circuits for the permanent was in fact established via a counting width lower bound for the number of perfect matchings. In general, unbounded counting width implies super-polynomial symmetric circuit lower bounds (via techniques for example from [1, 15]), so by Theorem 1, polynomials with unbounded counting width cannot be in ${𝔗}_{n,m}^k$, for any fixed $k$. The question is, does the converse hold: Is bounded counting width a sufficient criterion for the existence of orbit-small symmetric circuits? We answer this question positively, at least in certain restricted, but interesting cases, cf. Figure 1:

1. 1.

   when the $p_{n,m}$ are single homomorphism polynomials (rather than linear combinations of such), cf. Theorem 9,

2. 2.

   when the $p_{n,m}$ are single subgraph polynomials for graphs of sublinear size, i.e. counting the number of subgraphs isomorphic to the pattern, cf. Theorem 10, and

3. 3.

   when the $p_{n,m}$ are linear combinations of homomorphism polynomials of sublinear size, cf. Theorem 8.

Moreover, in the case of Items 1 and 2 and when Item 3 is restricted to linear combinations of polynomially many homomorphism counts, bounded counting width characterises the families of matrix-symmetric polynomials admitting symmetric circuits of polynomial size (rather than orbit size). For Items 1 and 2, we give a combinatorial characterisation of the families of patterns whose homomorphism/subgraph polynomials have bounded counting width in terms of treewidth and vertex cover number, respectively.

Finally, to give another concrete example for the merits of the symmetric circuit framework, we show that a complexity dichotomy for the immanant families due to [5], whose hard cases are conditional on certain complexity-theoretic assumptions, holds unconditionally for symmetric circuits. The immanants interpolate between the permanent and determinant polynomials, which are in fact the extreme cases. Thus, the symmetric dichotomy for the immanants completes the picture begun in [15].

Symmetric circuits are an emerging area of research in recent years. We have already mentioned the lower bound for symmetric circuits for the permanent from [15]. In a similar vein, it has been shown that the determinant admits no small ${\mathrm{𝐀𝐥𝐭}}_n\times {\mathrm{𝐀𝐥𝐭}}_n$-symmetric circuits, even though it does have polynomial size ${\mathrm{𝐒𝐲𝐦}}_n$-symmetric ones [17]. Other known lower bounds are for example for the symmetric formula complexity of computing the product of permutation matrices [24], and a lower bound for certain types of symmetric AC⁰ circuits for the parity function [37]. More recent work establishes lower bounds for symmetric bounded-depth circuits with modular counting gates [26]. In [1], a precise characterisation of the power of uniform polynomial-size symmetric Boolean circuits with threshold gates was given: Such circuit families are equally powerful as fixed-point logic with counting, a formalism that is also related to the Weisfeiler-Leman algorithm. In particular, the graph properties computable with these circuits have bounded counting width, too. Similarly, in [16], rank logic is characterised via a class of symmetric circuits with more involved types of gates.

Another direction that has been explored are symmetric algebraic circuits in the context of algebraic proof complexity, more specifically in the circuit-based Ideal Proof System [11]. We hope that this direction will benefit from the framework we develop here, possibly leading to new lower bounds in proof complexity.

Another aspect of our work are the homomorphism polynomials. Interestingly, their complexity has been studied before with respect to a different restricted model, namely monotone circuits. In [28, 3] it is shown that the monotone circuit complexity of homomorphism polynomials is controlled by the treewidth of the pattern graphs in a similar way as we show this for symmetric circuits (and moreover, the circuit depth relates to the depth of the tree decompositions). It should be mentioned, though, that our setting is more general in two ways: We consider linear combinations of homomorphism polynomials, rather than single ones, and our set-up is non-uniform, while in [28, 3], the pattern graph is taken to be the same fixed graph for all sizes of host graphs. Certain types of homomorphism polynomials (defined differently from the ones we study) have also been shown to be $\mathrm{𝖵𝖯}$-complete [19].

Our results also compare nicely to what is known on the computational complexity of homomorphism and subgraph counting. As already mentioned, it was shown in [6] that the computational complexity of graph parameters expressible as linear combinations of homomorphism counts (so-called graph motif parameters) depends only on the treewidth of the pattern graphs. The problem is in $\mathrm{𝖥𝖯𝖳}$ if the treewidth is bounded, and $\mathrm{\#}𝖶[1]$-hard, otherwise. Our Theorem 1 yields the same tractability criterion for the symmetric circuit complexity of the polynomials expressing these parameters but our proof techniques are very different. Moreover, as already mentioned, [6] concerns only uniform graph motif parameters, whereas we also cover the non-uniform case where we are counting different patterns for each host graph size.

The relationship between the complexity of subgraph counting and the vertex cover number of the pattern graphs that we obtain in Theorem 10 also appears in [6]. In [33, Theorem 1.3], a tight connection between the counting width of subgraph counts (for a fixed constant-size pattern) and the vertex cover number of the pattern is established. Our Theorem 10 generalises this result to the case of sublinearly growing patterns.

Let $\mathrm{\Gamma }$ be a group acting on a set $X$. For $S\subseteq X$, let ${\mathrm{𝐒𝐭𝐚𝐛}}_{\mathrm{\Gamma }}(S)≔\{\pi \in \mathrm{\Gamma }\mid \pi (S)=S\}$ be the stabiliser of $S$ and let ${\mathrm{𝐒𝐭𝐚𝐛}}_{\mathrm{\Gamma }}^{\bullet }(S)≔\{\pi \in \mathrm{\Gamma }\mid \pi (s)=s\text{ for every }s\in S\}$ be the pointwise stabiliser of $S$. Let $\mathrm{\Delta }\le \mathrm{\Gamma }$ be a subgroup. A set $S\subseteq X$ is a support of $\mathrm{\Delta }$ if ${\mathrm{𝐒𝐭𝐚𝐛}}_{\mathrm{\Gamma }}^{\bullet }(S)\le \mathrm{\Delta }$. For $\mathrm{\Gamma }={\mathrm{𝐒𝐲𝐦}}_n$ or $\mathrm{\Gamma }={\mathrm{𝐒𝐲𝐦}}_n\times {\mathrm{𝐒𝐲𝐦}}_m$ it is known that many subgroups $\mathrm{\Delta }\le \mathrm{\Gamma }$ have a unique minimal support, which we denote $\sup (\mathrm{\Delta })$, see [12, Lemma 4.1] and [10].

An algebraic circuit over a variable set $𝒳$ and a field $𝔽$ is a connected DAG with multiedges such that each vertex is labelled with an element of $𝒳\cup 𝔽\cup \{+,\times \}$. The vertices of a circuit are called gates, the edges wires. Gates labelled with elements from $𝒳\cup 𝔽$ are called input gates and they are not allowed to have incoming edges. Every element of $𝒳\cup 𝔽$ is allowed to appear at most once as the label of a gate – this is no restriction because one can simply identify the respective gates. We assume that a circuit contains exactly one gate without outgoing wires, and this is called the output gate. An algebraic circuit represents (or computes) a polynomial in $𝔽[𝒳]$ in the obvious way: the gates $+$ and $\times$ are simply interpreted as addition and multiplication on polynomials, and we care about the polynomial at the output gate. Arrows are directed from a computation result towards the next gate where that result is used as an input. Multiedges are allowed so that for example the polynomial $x^2$ can be represented with just one input and one multiplication gate. The size of a circuit $C$, is defined as the number of gates plus the number of wires, counted with multiplicities. It is denoted $\parallel C\parallel$.

Let $\mathrm{\Gamma }$ be a group that acts on $𝒳$. Then a circuit $C$ is $\mathrm{\Gamma }$-symmetric if the action of every $\pi \in \mathrm{\Gamma }$ on the input gates $𝒳$ extends to an automorphism of the circuit: For every input gate $g$, let $\mathrm{\ell }(g)$ denote its label. This is either a variable or a field element. Field elements are fixed by every $\pi \in \mathrm{\Gamma }$. We say that a permutation $\pi \in \mathrm{\Gamma }$ extends to a circuit automorphism of the circuit $C$ if there exists a $\sigma \in \mathrm{𝐒𝐲𝐦}(V(C))$ such that $\mathrm{\ell }(\sigma (g))=\pi (\mathrm{\ell }(g))$ for every input gate, and such that $\sigma$ is an automorphism of the multigraph structure of $C$ (i.e. it maps edges to edges, non-edges to non-edges, and preserves the operation types of the gates). For more details, see [14].

A $\mathrm{\Gamma }$-symmetric circuit is called rigid if it has no non-trivial circuit automorphism that fixes every input gate. This is equivalent to saying that for every $\pi \in \mathrm{\Gamma }$, there is a unique circuit automorphism $\sigma$ that extends $\pi$. In that case, we also write $\pi (g)$ for internal gates $g$, to denote the application of the unique circuit automorphism that extends $\pi$. As shown in [12, Lemma 4.3], symmetric circuits can always be assumed to be rigid. An advantage of working with rigid circuits is that we obtain a well-defined notion of support of gates, and that there is a strong link between the size of these supports and the orbit sizes of the gates. In the following, we always assume that $\mathrm{\Gamma }$ is ${\mathrm{𝐒𝐲𝐦}}_n$ or ${\mathrm{𝐒𝐲𝐦}}_n\times {\mathrm{𝐒𝐲𝐦}}_m$. In the former case, our variable set is ${𝒳}_n=\{x_{ij}\mid i,j\in [n]\}$, and $\pi \in {\mathrm{𝐒𝐲𝐦}}_n$ acts simultaneously on both indices, so $\pi (x_{ij})=x_{\pi (i)\pi (j)}$. In the latter case, the variable set is ${𝒳}_{n,m}=\{x_{ij}\mid i\in [n],j\in [m]\}$. Then a pair of permutations $(\pi ,{\pi }^{\prime })\in {\mathrm{𝐒𝐲𝐦}}_n\times {\mathrm{𝐒𝐲𝐦}}_m$ applied to $x_{ij}$ yields $x_{\pi (i){\pi }^{\prime }(j)}$.

An important measure for $\mathrm{\Gamma }$-symmetric circuits is $\mathrm{maxOrb}(C)$, the maximum orbit size of any gate in $C$, formally

If $C$ is rigid, and $\mathrm{\Gamma }$ and $C$ are such that every stabiliser group of a gate admits a unique minimal support, then we can also speak about the support size of $C$. In particular, this is possible if $\mathrm{\Gamma }\in \{{\mathrm{𝐒𝐲𝐦}}_n,{\mathrm{𝐒𝐲𝐦}}_n\times {\mathrm{𝐒𝐲𝐦}}_m\}$ and $\mathrm{maxOrb}(C)$ is subexponential. We write $\sup (g)\subseteq [n]\uplus [m]$ to denote the minimal support of the group ${\mathrm{𝐒𝐭𝐚𝐛}}_{{\mathrm{𝐒𝐲𝐦}}_n\times {\mathrm{𝐒𝐲𝐦}}_m}(g)$ in ${\mathrm{𝐒𝐲𝐦}}_n\times {\mathrm{𝐒𝐲𝐦}}_m$. The support size of a circuit $C$ is then

We have the following relations between $\mathrm{maxOrb}$ and $\mathrm{maxSup}$. Lemma 3 establishes the converse of Lemma 2, part 1. Proofs of both lemmas are given in [12, Section 4.2].

Counting logic is first-order logic augmented by counting quantifiers of the form ${\exists }^{\ge i}x$, for every $i\in \mathbb{N}$. A graph $G$ satisfies a formula ${\exists }^{\ge i}x\phi (x)$, written as $G\vDash {\exists }^{\ge i}x\phi (x)$, if there exist at least $i$ many distinct $v\in V(G)$ such that $G\vDash \phi (v)$. The $k$-variable fragment of counting logic is denoted ${𝒞}^k$. More details on counting logic and references may be found in [7]. For our purposes, the main interest is the equivalence relation that this induces on graphs. Two structures $G,H$ are called ${𝒞}^k$-equivalent, denoted $G{\equiv }_{{𝒞}^k}H$, if $G$ and $H$ satisfy exactly the same sentences of ${𝒞}^k$. This family of equivalence relations has many characterisations, e.g. in combinatorics [20, 18], machine learning [40, 32], and optimisation [23, 31, 2]. In particular, it is known that $G{\equiv }_{{𝒞}^{k+1}}H$ if, and only if, $G$ and $H$ are not distinguished by the $k$-dimensional Weisfeiler-Leman test for graph isomorphism [4].