WorksComputer Science
On Counting Graphs for Modal Logic with Counting
Abstract
In this paper, we study the theoretical computational complexity of counting trees and graphs that are classified positively by a graph neural networks, or said equivalently that satisfy a given formula of modal logic with counting. We also study convergence.
Introduction
Validity problems in modal logic is relevant in many reasoning tasks: verification of systems, epistemic planning. However, validity problem is rigid in this sense: a formula is valid if it holds in all models. In this paper, we relax the validity problem to model counting and we study the probabilistic validity problem: Is a formula true in a large proportion of models? Is a formula asymptotically true for large models? What is the proportion of models in which a formula holds? First, let us give motivation from a verification problem of graph neural networks (GNNs).
Recently, an exact correspondence between modal logic with counting verifying GNNs has been settled and applied for verifying properties on GNNs ([19], [18], [5]). In this paper, the only thing the reader must know is that each GNN from a large class of GNNs, namely with an eventually constant activation function or let say with truncated ReLU, is equivalent to a formula from a logic called , which is a natural extension of graded modal logic with linear arithmetic inequations (see [19], [18], [5]). The notion of equivalence is: a pointed graph is classified positively by the GNN iff holds in .
An example of -formula is which means that there are more -successors than -successors plus two. For instance, the formula is true in the pointed
Figure 1.
graph since .
Verifying GNNs is important in order to understand how they classify data. For instance, we could verify that a GNN recommends a person whenever that person has at least 3 violinist friends, meaning that for all pointed graphs , if the current vertex has at least 3 violinist successors then the GNN classifies positively. This kind of verification tasks were addressed in [18], and on quantized GNNs in [21] and [8].
However, it is unlikely that a property holds for all GNNs. For instance, it is unlikely that a GNN recommends a person whenever that person has at least 3 violinist friends. The reason is because the concept of recommended persons is a vague concept that is difficult to explain and does not completely match a property as precise as "having at least 3 violinist friends" (written ). The second reason is that there are approximations due to learning process itself, making unlikely that the obtained GNN exactly corresponds to a given property.
However, it is possible that a property like "having at least 3 violinist friends" is a probable explanation of the classification of the GNN. That is why, instead of checking that is valid, we want to compute the probability that holds where is a formula that is true when the GNN recommends the current model, and is a property, e.g. “the person has at least 3 violinist friends", . We may then conclude that the probability that holds in graph of size 42 is more than 0.8.
Our paper is related to 0-1 law that first-order logic has: any FO-sentence is asymptotically true in large models or false in large models. While specific classes of GNNs have 0-1 law ([2], [1]), this is clearly false for logic . Indeed, the limit of the truth of is . This justify the study of computing the probability of a formula given the size of the graph, or counting the number of -models of size . As many modal logics have the tree-model property, we also focus on trees and counting the number of trees satisfying given a branching factor.
Counting models. We study the complexity of counting -trees/graphs, given formula from logic (see Figure 1).

Figure 1 (PDF p. 3). Complexity results about counting trees ( is the branching factor) or graphs ( is then the number of vertices).
Convergence. We show that the proportion of -trees does not converge for some . We propose an artificial trick to make it converge.
Outline. In Section 2 we discuss the related work. In Section 3, we recall the formal definition of logic . In Section 4, we define the counting problems we are studying. In Section 5, we provide our complexity results. We also have an implementation using Montecarlo method that samples arbitrary large graphs and trees and gives out the proportion of satisfiability1. In Section 6, we exemplify non-convergence in trees and provide a patch for having convergence. In Section 7, we conclude.
Some parts of the proof of Theorem 28 were obtained by AI, although the authors have come up with the general approach by themselves.
Related Work
The study of convergence of properties when the size of the models goes to infinity goes back to 0-1 law of first-order logic [12], [9]. It means that the proportion of models satisfying a first-order property converges to 0 or 1 when the size of the model goes to infinity. In this work, the notion of random graph is given by the Erdős–Rényi random graph model.
Later, Granjean proved that deciding whether the limit is 1 for a given FO property is PSPACE-complete [14]. As modal logic is a syntactic fragment of first-order logic, it also has 0-1 law. But, the computation of the limit of a modal formula is -complete when the formula is represented by a DAG, and -complete if represented by a tree (see Theorem 4.6 in [15]), where is the class of problems decided in poly-time with an NP oracle, and is the class of problems decided in poly-time with at most queries to some NP oracle.
First-order logic when there are function symbols does not have the 0-1 law but still the proportion of models converges when the size of the model goes to infinity [17].
In literature, there are many logical frameworks developed that deal with boolean combinations of linear inequalities. In [10], the authors have developed a logical framework that expresses probabilities of combination of events in real numbers. In order to do that, they use a boolean combination of linear inequalities to reason. Although they have axiomatised the framework, the underlying model they use is a usual First Order logic model of domains of real numbers.
Counting models has been a major part of modal logic literature. A related work can be [22], where the authors consider Linear Temporal Logics. The paper gives decision versions of counting models: whether a formula has models upto an input bound. The paper proposes procedures for counting word and tree models, each one for when the bound is unary and one for when bound is in binary..
In [23], the authors investigate zero-one law on various coloring and edge probability (proportion) conditions on Markov Logic Networks. They define “regimes” that describe the global structure of the coloring and edge assignment, for example, most vertices are colored using same, etc. They showed results on whether zero-one laws and convergence laws hold depending on such regimes.
In [2], the authors proved 0-1 law for some graph neural networks but with strong assumptions. First, they focus on graph properties while we focus on node properties. But their stronger assumption is that they restrict to classifier that are non-splitting, meaning that the property is not on a limit case (see details in their paper). For instance \\#p \\ge\\#q is a limit case and its probability converges to while the probability (1+\\epsilon)\\#p \\ge\\#q converges to 1 when the number of successors goes to infinity, when . Compared to them, we consider any K^{\\#}-formula, without non-splitting assumption. However, we also consider truncated ReLU or eventually constant activation functions; setting which corresponds K^{\\#}.
In [1], the authors investigate convergence laws of some classes of GNNs. They prove convergence by sampling large graphs from probabilistic graph models like Erdős–Rényi graphs. However, the GNN architecture they consider do not use summation in message passing, but mean.
Background and Preliminaries
We present a modal logic of counting denoted by K^{\\#}, that was introduced in [18], but also in [4] and and [5] with a first-order syntax. Logic K^{\\#} has the same expressivity than graph neural networks with truncated ReLU as an activation function ([18], [5]).
Kripke model
We recall that a Kripke model is a directed graph like structures with each node having some propositional valuations over a countable set of propositions .
Definition 1. A Kripke model is a tuple where is a finite countable set of worlds, is the accessible relation, and is the valuation function. A pointed graph/model is a Kripke model and a vertex in .
Syntax
Fix a countable set of propositions . The set of K^{\\#}-formulas is defined by the grammar:
where , is an integer constant. The non-terminal is for arithmetic expressions. The construction is an indicator representing whether is true in the current state. The construction \\#\\varphi is the number of -successors. We write for the set of propositions appearing in .
Example 2. Here is a well-formed K^{\\#}-formula: \\varphi=(\\#p\\ge3\\#(\\#r\\ge2))\\land r.
Truth Conditions
The truth conditions (formula is true at vertex ) is defined as follows.
Definition 3. Given a -formula and a Kripke model , is defined by induction on by:
Figure 1 (PDF p. 5).
Example 4. Consider the following Kripke model and the formula in Example 2 evaluated from the top node pointed with an arrow. Formula holds true in this model from the root node. The root node has true in it. Now consider the part of the formula. Note that, (s, t and u). Also, consider the successor node where only is true (the node t). has two successors where holds (nodes u and v). Hence holds in . Note that is the only successor of root that holds . Hence at the root. Hence also holds true at root.
Definition 5 (Modal Depth). The modal depth of formula is defined as:
Intuitively, modal depth is the length of the longest nesting of the modality operator .
Example 6. We have . This is because has the maximum modal depth, which is 2.
A subformula of a -formula is direct when it does lie under the scope of exactly one -modality. The concept of direct formula is important because we count the number of successors satisfying these direct subformulas to evaluate a formula in the current node. We write for the set of direct subformulas.
Example 7. In the formula , subformulas , and are direct while and are not. We have .
Formally is defined as follows.
Definition 8 (Direct Sub formulas). Given a formula , the set of direct subformulas is defined by induction on as:
Link with other logics
Note that standard modal logic can be expressed in : is a shorthand for (there exists a -successor), while is a shorthand for . Graded modal logic can also be expressed in : is a shorthand for (there exists at least -successor).
Counting models
In this section, we define our counting problems. To do that, we suppose that is finite (otherwise there is already an infinite number of 1-vertex models!).
Counting graphs
We write for the set of pointed graphs whose domain of size . More precisely, we fix the domain to be and the pointed state is , i.e.
We define to be the subset pointed graphs in satisfying formula . When not explicitly said otherwise, we suppose then that i.e. that the set of propositions contains exactly the propositions appearing in .
Example 9. The number of pointed graphs of size 2 on the proposition set is (self-loop on 1, self-loop on 2, type of edges between 1 and 2, valuations). There are 4 pointed graphs of size 2 satisfying :
Said differently, when we consider , .
Then the proportion of pointed graphs of size satisfying is defined by:
Note that the definition of does not depend on , as long as contains the propositions appearing in . As presented in [9], a logical framework is defined to have zero-one law if for any formula , . As discussed in the introduction, logic does not have zero-one law.
Note that (choosing the set of edges and the valuations at each vertex). Thus, computing reduces to compute .
Counting trees
Many modal logics have the tree-like model property: if a formula is satisfiable, then it is satisfiable in a pointed tree. That is why it is natural to count the number of trees satisfying a property wrt to the branching factor (i.e. outgoing arity). We define to be the set of pointed trees of depth and branching factor . Similarly than for graphs, we define to be the subset of pointed trees in satisfying .
Example 10. Here are the 4 pointed trees of depth 1 with branching factor 2 on the proposition set satisfying : Said differently, when we consider , .
We define the proportion of pointed trees of branching factor satisfying as follows:
In the definition of , we consider trees of depth . Note that every vertices after depth is not relevant when evaluating . Again, for computing , it is sufficient to compute since (choosing the valuation for each of the vertices).
Complexity of Counting models
In this section, we investigate the problem of computing and , that is computing and .
Complexity of Counting Tree Models
We investigate on calculating the number of trees satisfying some -formula .
Definition 11. The Counting-Tree problem is defined as:
input: a -formula , a number (branching factor)
output: , the number of pointed tree models , with branching factor and depth such that .
In this subsection, we prove the following theorem.
Theorem 12. Counting-Tree is in #Pspace, if is in binary (and also in unary).
Consider a formula . We now define the notion of local consistency of at a given vertex in a tree. The only information we need is the propositional valuation and the number of successors in which each subformula in is true. That last information is modeled by a function that assigns to each subformula by the number of successors in which hold. We now define formally local-consistency of , denoted by .
Definition 13 (Local Consistency ). Consider a formula , a propositional valuation over the propositions of , and a function . Formula is said to be local-consistent with , denoted by , if holds true after applying the following steps in order:
For each , replace each non--nested occurrence in by .
Replace each proposition left by .
Example 14. Consider . If , and , then is local consistent with since is true (since ), is replaced by , and is replaced by , and .
A Dsf()-valuation is a function . Furthermore, given a Dsf()-valuation , we define
For instance, , , then . We prove Theorem 12 using Algorithm 2 (guessTree). We prove it by the following facts.
Fact 15. The number of accepting executions of guessTree() is .
Proof. Given a formula , the set of propositions appearing in , and the branching factor , we show that there is a one-to-one correspondence between non-rejecting executions of exploreAllTrees() and trees in . This sufficient because an accepting execution of guessTree() corresponds to a non-rejecting execution of exploreAllTrees().
For that we first formally define, by induction on the modal depth of , a function where is the set of non-rejecting paths of exploreAllTrees().
The base case is when is Boolean. By written the execution that guessed valuation at Line 2, we set to the single pointed vertex tagged with the valuation . In picture:
Induction case for a formula . In that case, the execution starts by guessing a valuation , guess a valuation over Dsf(), perform an execution at line 11 with , guess a valuation over Dsf(), perform an execution at line 11 with , etc. Said, differently, the execution is parameterized by and we write . The tree is then a root tagged with valuation with children corresponding to the sub-executions . The child for is obtained via .
Each accepting path corresponds to a satisfying model. In other words, we prove that function is a bijection. The proof goes by induction on the modal depth of . The base case, when is Boolean, is straightforward. Now for inductive step, we proceed as follows.
Surjection. Consider a pointed tree model . We construct an execution as follows. First, we guess the valuation over as in the root of at Line 6. Now consider child among the many children of the root. Note that Dsf() are exactly the sub-formulas of that have exactly one less #-modal depth. Hence, in our execution, we guess the valuation over Dsf() making exactly the formulas in Dsf() true in the -th child (Line 9 of the -th iteration of for loop in Line 8). Hence at that -child, holds. By induction hypothesis, there exists a non-rejecting execution for the -th call at Line 11. The obtained execution is .
Injection. Take two non-rejecting executions . Hence they differ on at least one of the nondeterministic choice. Just like the surjection proof, since the non-deterministic choices correspond to valuation of either propositions in the root or child nodes, they will correspond to different trees.
Fact 16. exploreAllTrees runs in poly-space.
Proof. The number of nested calls is bounded by the #-modal depth of the initial formula . Remember that the loop at Line 7 takes an exponential time in the size of (since is in binary), but the memory usage of each recursive call is cleaned after having been performed. The memory used at each call is polynomial in the size of the input: storing the valuation and is in where is the initial formula. Also, for all , . So can be represented with bits which is of polynomial size to the input.
Algorithm 1 exploreAllTrees
Input: K#-formula φ, P = P(φ) propositions of φ, branching factor n in binary
Output: reject or hand over
1 if φ is Boolean then
2 Guess a valuation ν over P;
3 if ν ⊭ φ then reject ;
4 else
5 Guess a valuation ν over P;
6 counter ← [0]Dsf(φ);
7 for i = 1 . . . n do
8 Guess a valuation V over Dsf(φ);
9 counter[ψ] ← counter[ψ] + 1 for each ψ ∈ Dsf(φ) such that V(ψ) = 1;
10 exploreAllTrees (descr(V), P, n);
11 if (ν, counter) ⊭L φ then reject ;
Algorithm 2 guessTree
Input: K#-formula φ, integer n in binary
Output: accept if exploreAllTrees hands over; reject otherwise
1 exploreAllTrees (φ, n);
2 accept ;
Theorem 17. Given , deciding that is PSPACE-hard.
Proof. Reduction from the satisfiability problem of standard modal logic in a tree of branching 2 which is PSPACE-hard (this is folklore but stated formally in Lemma 14 of [21]).
Now counting is important. But usually we want to deal with proportions, for instance knowing that . This problem reduces to know that . More generally, we aim at knowing whether . However, there is a trick in the representation of . Indeed, note that represented in binary is not sufficient since is which requires an exponential number of bits in to written down. However, that number is easily represented by . And can be written down with a polynomial number of bits. In other words, we represent with a RLE (Run-length encoding) representation where each blocks of 0 and 1 are represented by the digit (0 or 1) and the number of occurrences of that digit.
Theorem 18. Given , , , deciding whether is in PSPACE, when is in binary, and is in RLE compression representation.
Proof. First by Ladner theorem, we have that [16]. It means there is a poly-space machine, given , , output on a write-only tape the number of trees with branching satisfying . Note that this number can have an exponential number of bits. Finally, we compare to that output number on-the-fly (comparing numbers with RLE compression representation can be performed in time where is the size of the RLE compression representation, see [3]).
Complexity of Counting Graph Models
Unlike the previous sections, which deals with formulas being interpreted on pointed trees, we now generalise and look at pointed directed graphs. We call this problem as Counting-Graph problem. Formally,
Definition 19 (Counting-Graph). The Counting-Graph problem is defined as
Input: A formula , an integer
Output: , the number of pointed -state Kripke models that satisfy , where the set of propositions is .
In the previous definition, remember that the domain of a Kripke model of size is and that the designated point is always 1. We also suppose that the set of propositions is implicitly given by the formula .
Algorithm 3 guessGraph
Input: -formula , integer in unary
Output: Guess a pointed Kripke model such that and accept if or reject otherwise
Non-deterministically guess a pointed graph of vertices and on set of propositions ;
accept if else reject ;
Theorem 20. Counting-Graph is -complete when is given in unary.
Proof.
Upper Bound. Algorithm 3 gives a nondeterministic algorithm guessGraph taking as an input a formula , an integer in unary, it guesses an -state pointed Kripke model and checks if it satisfies . Each pointed graph of vertices can be represented by its adjacency matrix and a valuation at each vertex, we suppose here that the designated point is always the first one. So there are possible models of size .
Fact 21. guessGraph runs in poly-time in , and .
Proof. Let us analyze the algorithm.
Line 1. This step consists in guessing a binary word of length in time .
Line 2. Checking is in time .
Fact 22 (correctness). is exactly the number of accepting paths of guessGraph.
Proof. One execution of guessGraph is guessing a distinct Kripke model . So the number of accepting executions of of guessGraph is .
Lower Bound. Recall the problem of #SAT of propositional logic is: given a propositional formula , compute the number of valuations that makes true. The problem #SAT is #P-complete [24].
We reduce #SAT problem in poly-time to Counting-Graph as follows. Given a formula , we build the Counting-Graph instance . Note that the reduction is in poly-time. Finally, we have: #SAT iff .
The same Algorithm 3 gives an exponential blow-up in the upper bound when in binary.
Theorem 23. Counting-Graph is in #Exptime when is given in binary.
Theorem 24. Given , deciding whether is Pspace-hard when is in binary.
Proof. By reduction from satisfiability problem of standard modal logic in a tree of branching 2 which is PSPACE-hard. Let be a formula of standard modal logic. Take to be the size of trees with branching 2 of depth , i.e. . Take a formula that says that the model contains a tree of branching factor 2. Typically, is the formula
where are fresh propositions (see [7]). The idea of is that there is a 2-branching over the Boolean value of while values of with are propagated. Leaves correspond to all valuations over . The proposition means that we are at level . The reduction is . If is satisfiable in a tree of branching 2, then is satisfiable in a tree of branching 2 which is a graph of size . Conversely, if is true in a graph of size , then that graph must be a tree of branching 2.
Theoretical results at infinity
We now study the convergence of when the branching factor goes to infinity.
Counterexample for convergence
In this subsection, we come up with an example of a formula such that does not exist. Our candidate formula is where and are:
Intuitively, is a formula that asserts that the number of children to the current tree-node should be exactly twice the number of children where holds. In other words, number of children where holds is equal to the number of children where it does not. Similarly, asserts that the number of children where holds is exactly 1 less than the number of children where it does not.
Unfortunately, does not converge when goes to infinity: its value flips between 1 and numbers that are converging to 0; see Figure 2.

Figure 2. Values of depending on the branching factor .
Proposition 25. does not exist.
Proof. We only consider trees with depth 2. This is because the formula has modal depth of 2, hence cannot evaluate nodes that lie deeper. We also treat the probability of a tree node holding true to be equally likely: a fair coin toss. Hence, each leaf node (depth 2) represents one independent fair coin toss. Each node in the level above (depth 1) represents an experiment that involves exactly many independent coin tosses. It is in this level where we evaluate the event space of the experiment based on or . Lastly, in the root (depth 0), we compare the count of the event spaces. Let us compute the probability of depending on the parity of the branching factor.
Even branching. When the branching is even, is false. There, is always 0. Thus, formula is trivially true. Thus we have, .
Odd branching. As is zero when the branching is odd, by definition is the probability that . Now, the probability that holds in a node is (the probability of among trials). So the probability of is the probability of having false times. So
which tends to 0 when tends to (see appendix § 7).
Alternative definition of the limit
The following theorem gives a limit result for the probability of a formula to be true when the number of successors goes to infinity. Computing the limit of directly causes technical issues that we will discuss after the following theorem.
The technical solution we propose to study a limit result works as follows. Instead of taking the limit of when goes to infinity, we propose going to infinity at each level in the tree, and define a new quantity denoted by . The base case is when is Boolean. In that case, is constant and thus trivially exists. Now for the inductive case, we define as the limit when the branching factor at the root goes to infinity, provided that a direct subformula is true with probability which exists by induction.
It turns out that we define inside the following theorem because the existence for the direct subformulas is actually the conclusion of the theorem: exists.
Observe that for all formulas of modal depth 1, .
Definition 26. We define by induction on to be the probability that a rooted tree of the form
Figure 1 (PDF p. 13).
such that for all , the probability that some successor satisfies is .
The previous definition is well-formed because of the following theorem, and we kept the definition apart from the theorem for better clarity. If the limit exists, then it is written .
Example 27. Following the counterexample given in § 6.1, note that exists. When the branching factor goes to infinity, the probability that holds at the root tends to 0 (it becomes less and less probable to have exactly half of the successors to satisfy ). Similarly, the probability of also tends to 0. Therefore, . Hence, for any . This implies .
Theorem 28. For all -formulas , exists.
Proof. As per the syntax of , each formula is a boolean combination of literals and linear equations with as variables. Hence, we can write a formula as a DNF:
where the 's are mutually exclusive systems (conjunctions) of inequalities and is a Boolean formula. Note that and are independent because is about the current vertex valuation and is about the successors.
Example 29. is rewritten as
For the rest of the proof, we assume that the given formula is in DNF. The proof proceeds by induction on the -modal depth. For -modal depth 0, the formula is Boolean. Therefore is constant and thus converges.
Now, we suppose the limits exist for a modal depth . Consider the formula in DNF of modal depth .
Consider the formulas such that they occur in as for any . By induction, converges to some when goes to .
We have to prove that converges to some when goes to .
Since is in a DNF form, hence . As are propositional, is constant. First we prove that if exists for all , then exists in the following fact. The rest of the proof becomes proving that exists for all .
Fact 30. Let be a system of inequalities. Then exists.
Proof. For a given , and , and be a (direct) subformula, let be an indicator random variable such that
Therefore, .
Let be the number of successors satisfying among the at most successors. Formally, . We define the -vector , that is a column vector of dimension. Formally, it is defined by .
Let be the number of inequations in . The system for branching is of the form
where is -matrix; is a dimension column vector. We use a version of Lindeberg-Feller Central Limit theorem [11] to prove the convergence/existence of the limit. Since we have vectors of sum of indicator random variable, we use the Cramer-Wold theorem and Multivariate CLT [6]. For that purpose, we need the covariance matrix of every pair of indicator random variable.
Given a , the covariance between and for any :
Consider the covariance matrix .
Since, the setup is a summation of indicator random variables, by applying Cramer-Wold theorem and then translating to Multivariate CLT [6] we get:
where is the covariance matrix whose entries are indexed by and are given by (2). denotes the Normal distribution of dimension vectors, whose mean is at 0 and the variance along each of dimensions is , the covariance matrix.
Since we have our system of inequalities as , we rewrite system in (3) as:
Since as , the expression . Hence the validity of the (4) depends only on .
Recall that are -vectors, is a -matrix; is a -vector. Also, the (3) becomes:
Since each row in are the co-efficients of one inequality in the system, depending on how rows in (row denoted by ) behaves, the convergence of the coordinates of can be one of following cases:
If at least for one , , then converges to . So system is unsatisfiable at the limit. Therefore .
If for all , , converges to . Hence grows faster than the RHS in (4) as which implies
If for every , , then converges to . We have . By Equation (5), and since , by Portmanteau theorem [6]:
applying Portmanteau theorem
Example 31. With system , we have matrix and . Thus we are in case 2 and all the constraints can be ignored. We are left with a matrix of "relevant" constraints of size . Thus .
Example 32. With system , we have matrix and , thus . As the second coordinate of is negative, we are in point 1 and .
Example 33. With system , we have matrix and , thus . As the second coordinate of is positive, so we can ignore the second constraint. At the limit, system has the same probability to be true than system . The limit probability is where is a 2-dimensional normal distribution. Since is a standard normal distribution, .
Example 34. With system , we have matrix and , thus .
Probability that are reached
In this section, we study the value of the limit probability that exists and can be reached by some -formula . Let us recall Sheppard’s Formula.
Lemma 35 (Sheppard’s Formula [20]). Let be standard 1-dimension Gaussian random variables with correlation . Then
Proposition 36. For all numbers , there is a sequence of a -formula that are systems with two inequalities such that .
Proof. Given a matrix with two rows and let us compute . According to Sheppard’s formula, where . We can make approximate all values for between with arbitrary big matrices . Since , all values of can be approximated by .
The probability over -formulas can get arbitrarily close to any number in as stressed by the following proposition.
Proposition 37. For all , for all , there is a -formula such that .
Proof. We prove the statement using the fact that the set of dyadic rationals is dense in . So for all , for all , there is such that . We now give a formula with . Consider
where and are distinct propositional variables. Since each propositions are independent and , the ANDs product the probabilities and the ORs adds the probabilities up.
Conjecture 38. is equal to some adherence point of .
Open problems
This work opens the path of studying convergence on general graphs and not only trees, as done in § 6. We finish our work by listing some open problems.
How to decide when converges? Is it decidable? What is the complexity of that decision problem? Are there some approximation algorithms? These questions are relevant to solve verification problems of GNNs for large graphs. In fact, we conjecture that a fragment, we call majority logic, with a boolean bias condition can have 0-1 law. (for more details, see Appendix)
How to put proportion information in the logic and construct a proof system for reasoning about proportions of models? The answer to this research question may provide a tool for giving justifications of some verification verdict.
How to compute conditioned proportion? For instance how to compute the proportion of -models among the -models? This is relevant for more involved verification tasks.
Convergence to 0 of
Theorem 39.
Proof. Note that:
Hence the statement expression becomes
Now we approximate the expression asymptotically. Note that by Stirling’s approximation [13], . Hence,
Therefore, as :
As , let
Taking logarithms on both sides:
As , . Also, as , by Taylor expansion,
Hence,
Therefore
Computations
Computation of proportion of pointed graphs for
The number of graphs of size is .
The number of configurations for the successors of a point to satisfy is
where is the number of ways to put subsets in a set of size and with .
Computation of proportion of pointed graphs for
The number of configurations is:
We now also have to consider the choices elsewhere. So the number of models satisfying is:
So the probability that holds in a pointed graph of size is:
Computation of proportion of pointed trees for
We compute the probability of satisfying in tree model from the root with number of branching at most .
Also, since truth depends on modal depth, we do not care about depth.
Number of trees of at most branching with two propositions:
From the current node, we just count that given number of branches , how many ways can there be valuations such that number of positive is at least just like above:
By above we have
Hence
A Condition for 0-1 Law for Majority Logic
In this section, we introduce a fragment of that we call Majority Logic. The restriction is as follows. The inequations we allow are of the form . Majority logic does not have 0-1 law (e.g. ). But we introduce a constraint, called full Boolean bias, that gives majority logic 0-1 law back.
Boolean Bias Condition
The idea is to resolve all the Boolean bias. Given , we compute the probability of for a Boolean formula by assuming that the truth values of are independent.
Definition 40. has full Boolean bias iff for all Boolean formulas , if then .
Example 41 (no full Boolean bias). If and , then there is a no full Boolean bias because:
(no bias)
Example 42 (full Boolean bias). If and , then there is a full Boolean bias because:
The following is our conjecture:
Conjecture 43. Under the condition full Boolean biais, for all of majority logic,
References
- [1]Sam Adam-Day, Michael Benedikt, Ismail İlkan Ceylan, and Ben Finkelstein. Almost surely asymptotically constant graph neural networks. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 124843–124886. Curran Associates, Inc., 2024. URL: https://proceedings.neurips.cc/paper_files/paper/2024/file/e1cd1db6fcd4a6df8618259f5b9cca0f-Paper-Conference.pdf, doi:10.52202/079017-3965.
- [2]Sam Adam-Day, Theodor-Mihai Iliant, and Ismail İlkan Ceylan. Zero-one laws of graph neural networks. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023. URL: http://papers.nips.cc/paper_files/paper/2023/hash/dfba85bc32a3cb63a96d1142062b4d8e-Abstract-Conference.html.
- [3]Alberto Apostolico, Gad M. Landau, and Steven Skiena. Matching for run-length encoded strings. In Bruno Carpentieri, Alfredo De Santis, Ugo Vaccaro, and James A. Storer, editors, Compression and Complexity of SEQUENCES 1997, Positano, Amalfitan Coast, Salerno, Italy, June 11-13, 1997, Proceedings, pages 348–356. IEEE, 1997. doi:10.1109/SEQUEN.1997.666929.
- [4]Bartosz Bednarczyk, Maja Orlowska, Anna Pacanowska, and Tony Tan. On classical decidable logics extended with percentage quantifiers and arithmetics. In Mikolaj Bojanczyk and Chandra Chekuri, editors, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2021, Virtual Conference, December 15-17, 2021, volume 213 of LIPIcs, pages 36:1–36:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2021.36, doi:10.4230/LIPIcs.FSTTCS.2021.36.
- [5]Michael Benedikt, Chia-Hsuan Lu, Boris Motik, and Tony Tan. Decidability of graph neural networks via logical characterizations. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia, volume 297 of LIPIcs, pages 127:1–127:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. URL: https://doi.org/10.4230/LIPIcs.ICALP.2024.127, doi:10.4230/LIPIcs.ICALP.2024.127.
- [6]P. Billingsley. Probability and Measure. Wiley Series in Probability and Statistics. Wiley, 1995. URL: https://books.google.fr/books?id=z39JgQJgAACAAJ.
- [7]Patrick Blackburn, Maarten de Rijke, and Yde Venema. Modal Logic, volume 53 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2001. doi:10.1017/CBO9781107050884.DOI
- [8]Artem Chernobrovkin, Marco Sälzer, François Schwarzentrüber, and Nicolas Troquard. Verifying quantized gnns with readout is decidable but highly intractable. In Renata Wassermann, Marie-Laure Mugnier, and Franz Baader, editors, Proceedings of the 23rd International Conference on Principles of Knowledge Representation and Reasoning, KR 2026, Lisbon, Portugal, July 20-23, 2026, 2026. URL: https://doi.org/10.24963/kr.2026/83, doi:10.24963/KR.2026/83.
- [9]Ronald Fagin. Probabilities on finite models. J. Symb. Log., 41(1):50–58, 1976. doi:10.1017/S0022481200051756.DOI
- [10]Ronald Fagin, Joseph Y. Halpern, and Nimrod Megiddo. A logic for reasoning about probabilities. Inf. Comput., 87(1/2):78–128, 1990. doi:10.1016/0890-5401(90)90060-U.DOI
- [11]W. Feller. An Introduction to Probability Theory and Its Applications, Volume 2. Number v. 1-2 in An Introduction to Probability Theory and Its Applications. Wiley, 1957. URL: https://books.google.fr/books?id=BsSwAAAAIAAJ.
- [12]Yu V Glebskii, Dmitry I Kogan, MI Liogon’kil, and Vladimir A Talanov. Range and degree of realizability of formulas in the restricted predicate calculus. Cybernetics, 5(2):142–154, 1969.
- [13]Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics: A Foundation for Computer Science, 2nd Ed. Addison-Wesley, 1994. URL: https://www-cs-faculty.stanford.edu/%7Eknuth/gkp.html.
- [14]Etienne Grandjean. Complexity of the first-order theory of almost all finite structures. Inf. Control., 57(2/3):180–204, 1983. doi:10.1016/S0019-9958(83)80043–6.DOI
- [15]Joseph Y. Halpern and Bruce M. Kapron. Zero-one laws for modal logic. Ann. Pure Appl. Log., 69(2-3):157–193, 1994. doi:10.1016/0168-0072(94)90084–1.
- [16]Richard E. Ladner. Polynomial space counting problems. SIAM J. Comput., 18(6):1087–1097, 1989. doi:10.1137/0218073.DOI
- [17]James F. Lynch. Probabilities of first-order sentences about unary functions. Transactions of the American Mathematical Society, 287(2):543–568, 1985.
- [18]Pierre Nunn, Marco Sälzer, François Schwarzen truber, and Nicolas Troquard. A logic for reasoning about aggregate-combine graph neural networks. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI 2024, Jeju, South Korea, August 3-9, 2024, pages 3532–3540. ijcai.org, 2024. URL: https://www.ijcai.org/proceedings/2024/391.arxiv.org/abs/2405.00205
- [19]Pierre Nunn and François Schwarzen truber. A modal logic for explaining some graph neural networks. CoRR, abs/2307.05150, 2023. URL: https://doi.org/10.48550/arXiv.2307.05150, arXiv:2307.05150, doi:10.48550/ARXIV.2307.05150.
- [20]Ryan O’Donnell. Analysis of boolean functions. CoRR, abs/2105.10386, 2021. URL: https://arxiv.org/abs/2105.10386, arXiv:2105.10386.
- [21]Marco Sälzer, François Schwarzen truber, and Nicolas Troquard. Verifying quantized graph neural networks is pspace-complete. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025, Montreal, Canada, August 16-22, 2025, pages 4660–4668. ijcai.org, 2025. URL: https://doi.org/10.24963/ijcai.2025/519, doi: 10.24963/IJCAI.2025/519.
- [22]Hazem Torfah and Martin Zimmermann. The complexity of counting models of linear-time temporal logic, 2014. URL: https://arxiv.org/abs/1408.5752, arXiv:1408.5752.
- [23]Yasmin Toussaint and Vera Koponen. Random coloured digraphs defined by a markov logic network. CoRR, abs/2606.23715, 2026. URL: https://doi.org/10.48550/arXiv.2606.23715, arXiv:2606.23715, doi:10.48550/ARXIV.2606.23715.
- [24]Leslie G. Valiant. The complexity of computing the permanent. Theor. Comput. Sci., 8:189–201, 1979. doi:10.1016/0304-3975(79)90044–6.DOI


