# The generalised distribution semantics and projective families of
distributions

Felix Q. Weitkämper
Institut für Informatik  LMU München  Oettingenstr. 67  80538 München
<EMAIL_ADDRESS>
###### Abstract

We generalise the distribution semantics underpinning probabilistic logic
programming by distilling its essential concept, the separation of a free
random component and a deterministic part. This abstracts the core ideas
beyond logic programming as such to encompass frameworks from probabilistic
databases, probabilistic finite model theory and discrete lifted Bayesian
networks. To demonstrate the usefulness of such a general approach, we
completely characterise the projective families of distributions representable
in the generalised distribution semantics and we demonstrate both that large
classes of interesting projective families cannot be represented in a
generalised distribution semantics and that already a very limited fragment of
logic programming (acyclic determinate logic programs) in the determinsitic
part suffices to represent all those projective families that are
representable in the generalised distribution semantics at all.

##  1 Introduction

The distribution semantics, first explicitly introduced by Sato Sato95,
kickstarted the development of probabilistic logic programming, a paradigm
that extends traditional logic programming with probabilistic primitives to
enable probabilistic relational programming with recursion. By cleanly
separating the probabilistic part from the deterministic part, the
distribution semantics allows the use of techniques developed over decades of
logic programming research, such as negation as failure which unlocks
recursion as a programming tool.

From this point of view, probabilistic logic programming is a specific set-up
of logic programs over independent probabilistic facts. There is no intrinsic
reason, though, why the fundamental principle of separating probabilistic and
logical components of a statistical relational formalism should be limited to
this specific set-up. In this paper, the distribution semantics is studied as
the abstract concept of defining a statistical relational specification by
specifying an independent probabilistic part and an arbitrary deterministic
part on top of that.

There are several motivations for studying the concept in this generality.

The original motivation for the distribution sematics comes from probabilistic
logic programming. In its classical formulation, this is considered to be a
Datalog program over independent probabilistic facts. However, the logic
programming paradigm includes far more than Datalog; its main proponent,
Prolog, is a Turing-complete programming language whose support for
metaprogramming via higher-order predicates is a key feature. Already today
the main implementations of probabilistic logic programming such as CPlint or
ProbLog support higher-order predicates and meta-calls [De Raedt and Kimmig
(2015)].

The concept of the distribution semantics is also key to probabilistic
databases in the guise of the tuple-independent database model [Suciu et al.
(2011)]. As Datalog is but one of several query languages considered in the
database community, combining the tuple-independent database model with
different query logics is very natural. In particular, aggregates are commonly
supported by real-life databse query languages without being expressible in
the classical probabilistic logic programming concept.

On the theoretical side, Cozman and Maua’s probabilistic finite model theory
CozmanM19 centres around evaluating the expressivity of different logics above
independent probabilistic facts. By evaluating the distribution semantics as a
general concept, one can distinguish sharply between limitations on
expressivity induced by the logic employed in the deterministic part as
opposed to intrinsic limitations occasioned by the separation of logic and
probability.

Finally, sometimes models that appear to consist of several probabilistic
layers can in fact be reduced to a single independent probability
distribution. This is true for lifted Bayesian networks based on discrete
conditional probability tables, for instance. One such case where the logic
employed is very different from classical first-order or fixed-point logic are
Koponen’s lifted Bayesian networks Koponen20, which are formulated in terms of
conditional probability logic. This logical language allows the expression of
statistical statements within the defining formulas of intensional predicates.

To show the potential of the general framework, we characterise the
_projective families of distributions_ obtainable in the generalised
distribution semantics.

Projectivity was recently introduced to the artificial intelligence literature
[Jaeger and Schulte (2018), Jaeger and Schulte (2020)] as a strong condition
guaranteeing that marginal probabilities are independent of the domain into
which the constants invoked in a query are embedded. However, they have been
studied for decades in the field of _pure inductive logic_ , where they are
used to characterise degrees of belief that rational agents could adopt about
the world they might be inhabiting [Carnap (1950), Paris and Vencovská
(2015)]. We build on recent work from that tradition to obtain our
characterisation, and we see that the assumptions of the generalised
distribution semantics already severly limits the representable projective
families of distributions.

Such results have heretofore been obtained for classical PLP from the
asymptotic theory of the concrete fixpoint logic involved in the deterministic
part [Weitkämper (2021)]. The 0-1 laws of finite model theory, on which such
arguments are based, are very brittle, though. A dependency on, say, the
number of domain elements being even, would immediately invalidate such
arguments, although they are easy to represent using database aggregates or
Prolog-style metaprogramming.

##  2 Frameworks

In this section we introduce our main framework, the generalised distribution
semantics, and we provide an alternative formulation of projectivity that
integrates well with the concept.

###  2.1 Preliminaries and distributions

######  Definition 1.

We define shorthands for some of the categories that we refer to throughout:

  * •

$\mathrm{SET}_{\mathrm{inj}}$ is the category of finite sets, with injective
maps as morphisms.

  * •

$\mathrm{SET}_{\mathrm{sur}}$ is the category of finite sets with surjective
maps as morphisms.

  * •

MEAS is the category of finite measure spaces, with measure-preserving
surjective maps as morphisms.

  * •

$\mathrm{STRUCT}^{L}$ is the category of finite $L$-structures with embeddings
as morphisms.

######  Definition 2.

When introducing the following notation around $L$-structures, $A\subseteq B$
are sets and $L^{\prime}\subseteq L$ are signatures.

  * •

If $\omega$ is an $L$-structure with domain $B$, then the _restriction_ of
$\omega$ to $A$ is the $L$-structure $\omega_{A}$ on $A$ for which
$\omega_{A}\models R(\vec{a})$ if and only if $\omega\models R(\vec{a})$, for
any relation symbol $R$ of $L$ and any tuple $\vec{a}$ of elements of $A$. In
this situation, $\omega$ is called an _extension_ of $\omega_{A}$ to $B$. The
inclusion map is always an embedding from $\omega_{A}$ to $\omega$.

  * •

If $\omega$ is an $L$-structure with domain $A$, then _reduct_ of $\omega$ to
$L^{\prime}$ is the $L^{\prime}$-structure $\omega^{L^{\prime}}$ for which
$\omega^{L^{\prime}}\models R(\vec{a})$ if and only if $\omega\models
R(\vec{a})$, for any relation symbol $R$ of $L^{\prime}$ and any tuple
$\vec{a}$ of elements of $A$. In this situation, $\omega$ is called an
_expansion_ of $\omega_{\mid L^{\prime}}$ to $L$.

######  Definition 3.

A _random $L$-world_ with domain $D$ is a probability distribution over the
set of $L$-structures with domain $D$. We denote that set by
${\Omega_{D}}^{L}$.

######  Definition 4.

For any signature $L$, can define a contravariant functor $\Omega^{L}$ (the
_possible worlds_ functor) from $\mathrm{SET}_{\mathrm{inj}}$ to
$\mathrm{SET}_{\mathrm{sur}}$ as follows:

$\Omega^{L}(D)$ is ${\Omega_{D}}^{L}$, the set of $L$-structures with domain
$D$.

For any injective function of finite sets $\iota:A\rightarrow B$,
$\Omega^{L}(\iota):{\Omega_{B}}^{L}\rightarrow{\Omega_{A}}^{L}$ maps every
$L$-structure $\omega$ with domain $B$ to the $L$-structure $\omega_{\iota}$
on domain $A$, which models $R(\vec{a})$ if and only if $\omega\models
R(\vec{\iota(a)})$. If $\iota$ is the inclusion map of an $A\subseteq B$, then
$\omega_{\iota}$ is just the restriction of $\omega$ to $A$.

Now we can define a projective family of distributions categorically.

######  Definition 5.

A projective $L$-family of distributions $P$ is a contravariant functor from
$\mathrm{SET}_{\mathrm{inj}}$ to MEAS which extends $\Omega^{L}$. In other
words, if $F$ is the forgetful functor from MEAS to
$\mathrm{SET}_{\mathrm{sur}}$, then $F\circ P=\Omega^{L}$. Since $P$ is
completely determined by the measure on $P(A)$ for a set $A$, we refer to this
measure as $P_{A}$.

This notion of projectivity is a direct generalisation of the one advanced by
Jaeger and Schulte JaegerS18,JaegerS20. More precisely:

######  Proposition 6.

Every projective family of distributions in their sense extends uniquely to a
projective family of distributions in our sense, and each of our projective
families of distributions extend a projective family in their sense.

###### Proof.

The sets $\\{1,\dots,n\\}$ with inclusion maps are a skeletal subcategory of
$\mathrm{SET}_{\mathrm{inj}}$. ∎

###  2.2 The distribution semantics

The key idea of the distribution semantics is to split the complex
distribution into two parts, one purely probabilistic (’free’) and one purely
deterministic. We first introduce the probabilistic part.

######  Definition 7.

A _free_ $L$-family of distributions is a projective family of distributions
$P:\mathrm{SET}_{\mathrm{inj}}\rightarrow\mathrm{MEAS}$ defined from a _weight
function_ $w:L\rightarrow(0,1)$ by setting

$P_{A}(\omega)=\left(\prod_{\begin{subarray}{c}\vec{a}\in A,R\in L\\\
\omega\models
R(\vec{a})\end{subarray}}w(R)\right)\times\left(\prod_{\begin{subarray}{c}\vec{a}\in
A,R\in L\\\ \omega\models\neg R(\vec{a})\end{subarray}}(1-w(R))\right).$

It is easy to see that any such weight function defines a free $L$-family of
distributions $P_{w}$. Furthermore, any free family of distributions is an
equivalence of categories from ${\mathrm{SET}_{\mathrm{inj}}}^{\mathrm{op}}$
to its image $\mathrm{Im}(P)$, the subcategory of MEAS whose objects are the
measure spaces $P_{w}(A)$ for a finite set $A$ and whose morphisms are the
measure-preserving maps induced by injective functions between finite sets.

We now turn to the deterministic part.

######  Definition 8.

A _choice of expansions_ (from $L^{\prime}$ to $L$) is a family of maps
$\Pi:{\Omega_{D}}^{L^{\prime}}\rightarrow{\Omega_{D}}^{L}$ for all finite sets
$D$ such that $\Pi(\omega)$ expands $\omega$ for all
$\omega\in{\Omega_{D}}^{L^{\prime}}$.

######  Definition 9.

A _generalised probabilistic logic program_ $(P,\Pi)$ is a map from SET to
MEAS, whose data is given by a free family of $L^{\prime}$-distributions $P$
and a choice of expansions from $L^{\prime}$ to $L$, for an
$L^{\prime}\subseteq L$. For any finite set $D$,
$(P,\Pi)(D):={\Omega_{D}}^{L}$. For any finite set $D$ and every
$\Delta\subseteq{\Omega_{D}}^{L}$, the probability of $\Delta$ under $(P,\Pi)$
is given by $P_{D}(\Pi^{-1}(\Delta))$.

######  Proposition 10.

A generalised probabilistic logic program defines a projective family of
distributions if and only if its associated choice of expansions $\Pi$
commutes with restrictions and extensions, that is, if for any injective
$\iota:A\rightarrow B$, the following square commutes, where $\pi$ denotes the
restriction of a structure along an embedding:

${{\Omega_{A}^{L^{\prime}}}}$${{\Omega_{A}^{L}}}$${{{\Omega_{B}}^{L^{\prime}}}}$${{{\Omega_{B}}^{L}}}$$\scriptstyle{\Pi}$$\scriptstyle{\pi}$$\scriptstyle{\Pi}$$\scriptstyle{\pi}$

###### Proof.

Since the free part $P$ of the logic program induces an equivalence of
categories, the generalised PLP is functorial if and only if the map $\Pi^{*}$
from $\mathrm{Im}(P)$ to MEAS induced by $\Pi$ is functorial (where the
underlying set of $\Pi^{*}(({\Omega_{D}}^{L^{\prime}},\mu))$ is
${\Omega_{D}}^{L^{\prime}}$ and the probability measure is the pushforward
measure of $\mu$ under $\Pi$, i. e.
$\Pi^{*}(\mu)(\Delta)=\mu(\Pi^{-1}(\Delta))$).

This is encapsulated in the commutativity of the following diagram,

${{(\Omega_{A}^{L^{\prime}},\mu_{A})}}$${{(\Omega_{A}^{L},\Pi^{*}\mu_{A})}}$${{({\Omega_{B}}^{L^{\prime}},\mu_{B})}}$${{({\Omega_{B}}^{L},\Pi^{*}\mu_{B})}}$$\scriptstyle{\Pi}$$\scriptstyle{\pi}$$\scriptstyle{\Pi}$$\scriptstyle{\pi}$

with maps $\pi$ induced by an injective map $\iota:A\rightarrow B$.

As the maps here coincide with the maps in the requirements of the
proposition, the “only if” direction is immediate.

“If”: If $\Pi$ satisfies the requirements in the proposition, then this
diagram clearly commutes. It suffices therefore to show therefore that the
restriction map from $({\Omega_{B}}^{L},\Pi^{*}\mu_{B})$ to
$(\Omega_{A}^{L},\Pi^{*}\mu_{A})$ is measure-preserving, that is, that for any
$\omega\in\Omega_{A}^{L}$,

$\mu_{A}(\Pi^{-1}(\\{\omega\\}))=\mu_{B}\Pi^{-1}\\{(\pi^{-1}(\omega))\\}.$

However, since by the requirements of the proposition
$\Pi^{-1}\\{(\pi^{-1}(\omega))\\}=\pi^{-1}\\{(\Pi^{-1}(\omega))\\}$, this
follows from the fact that $\pi$ is measure-preserving with respect to
$\mu_{B}$ and $\mu_{A}$.

∎

######  Corollary 11.

Let $(P,\Pi)$ be a projective PLP, let $L^{\prime}$ be the signature of $P$
and $L$ the signature of $\Pi$. Let $\omega_{1},\omega_{2}$ be
$L^{\prime}$-structures and let $g\in\mathbb{N}$ such that the $g$-trace of
$\omega_{1}$ coincides with the $g$-trace of $\omega_{2}$. Then the $g$-trace
of $\Pi(\omega_{1})$ coincides with the $g$-trace of $\Pi(\omega_{2})$.

###### Proof.

For any $A=\\{a_{1},\dots,a_{g}\\}\subseteq\omega_{1},\omega_{2}$ consider the
restrictions $\omega_{1,A}$ and $\omega_{2,A}$. Since the $g$-traces of
$\omega_{1}$ and $\omega_{2}$ coincide, $\Pi(\omega_{1,A})=\Pi(\omega_{2,A})$.
By the theorem above, ${\Pi(\omega_{1})}_{A}=\Pi(\omega_{1,A})$ and
${\Pi(\omega_{2})}_{A}=\Pi(\omega_{2,A})$, and since $A$ was arbitrary with
cardinality not exceeding $g$, this shows that the $g$-trace of
$\Pi(\omega_{1})$ coincides with the $g$-trace of $\Pi(\omega_{2})$. ∎

##  3 Classification of projective generalised PLP

###  3.1 Strong independence property

We identify projective generalised PLP as those satisfying the _strong
independence property_ , first isolated in the context of pure inductive logic
[Paris and Vencovská (2015)] by Ranel and Vencovska RonelV16.

An important auxiliary concept in the analysis is the $g$-_trace_ , which is
usually defined in terms of formulas satisifed by a given random world:

######  Definition 12.

Let $\omega$ be an $L$-world. Then the $g$-ary (syntactic) _trace_
$\mathrm{tr}_{g}(\omega)$ of $\omega$ is defined as the set of all literals
$\varphi(a_{1},\dots,a_{g})$ that hold in $\omega$, where $a_{1},\dots,a_{g}$
are elements from $\omega$. A $g$-ary trace over a domain $D$ is a $g$-ary
trace over an $L$-world with domain $D$. A $g$-ary trace over $L$ is a trace
over the domain $\\{1,\dots,g\\}$.

Let $\varphi$ be a quantifier-free $L$-formula whose variables have been
ground to elements of a domain. Then $\varphi$ _mentions_ a tuple
$a_{1},\dots,a_{n}$ if there is an atomic subformula $R(b_{1},\dots,b_{m})$ of
$\varphi$ such that $\\{a_{1},\dots,a_{n}\\}\subseteq\\{b_{1},\dots,b_{m}\\}$.

Note that the $k$-trace of an $L$-world with domain $D$ completely specifies
that world, where $k$ is at least the minimum of the highest arity ocurring in
$L$ and the cardinality of $D$.

Since semantic concepts fit better into our framework than criteria defined in
terms of quantifier-free formulas, we give equivalent semantic notions:

######  Definition 13.

Let $\omega$ be an $L$-world. Then the $g$-ary (semantic) trace of $\omega$ is
defined as the set of all worlds $\omega^{\prime}$ on the same domain as
$\omega$ such that for every subset $D$ of that domain of cardinality not
exceeding $g$, $\omega^{\prime}_{D}=\omega_{D}$. A $g$-ary trace over a domain
$D$ is a $g$-ary trace over an $L$-world with domain $D$.

Let $\varphi$ be a set of elements over a domain $D$. Then $\varphi$
_mentions_ a tuple of distinct elements $a_{1},\dots,a_{g+1}$ of $D$ if there
are $\omega_{1}$ and $\omega_{2}$ such that
${\omega_{1}}_{D^{\prime}}={\omega_{2}}_{D^{\prime}}$ for all
$D^{\prime}\subseteq D$ with $\\{a_{1},\dots,a_{g+1}\\}\nsubseteq D^{\prime}$
and $\omega_{1}\in\varphi$, but $\omega_{2}\notin\varphi$.

######  Proposition 14.

The semantic trace of a possible world $\omega$ are exactly the models of the
syntactic trace of $\omega$.

Whenever a formula $\varphi$ does not (syntactically) mention a tuple, then
the models of $\varphi$ do not (semantically) mention it. When a set does not
mention a tuple semantically, this set is the set of models of a sentence
which does not (syntatically) mentions that tuple.

###### Proof.

We first show the statement for traces. Let $\theta$ be the syntactic trace of
$\omega$. Then for any world $\omega^{\prime}$ satisfying $\theta$ and every
subset $D$ of cardinality $g$, ${\omega^{\prime}}_{D}$ has the same $g$-trace
over $D$, namely the restriction of $\theta$ to $D$, which completely
specifies ${\omega^{\prime}}_{D}$. Conversely, if
${\omega^{\prime}}_{D}=\omega_{D}$ for all $D$ of cardinality $g$, then
$\omega^{\prime}$ satisfies the ame formulas with entries from $D$ as
$\omega$, for all $g$-tuples of entries $D$. This implies that
$\omega^{\prime}$ satisfies $\theta$.

We now show the statement for mentions. Let $\varphi$ not (syntactically)
mention $a_{1},\dots,a_{n}$. Then for all atoms $\lambda$ in $\varphi$, there
is an $a_{\lambda}\in\\{a_{1},\dots,a_{n}\\}$ that does not occur in
$\lambda$. Let ${\omega_{1}}_{D}={\omega_{2}}_{D}$ for all $D$ omitting an
$a_{i}$ and let $\omega_{1}\models\varphi$. This implies that
${\omega_{1}}_{D}$ and ${\omega_{2}}_{D}$ agree on the truth value of all
atoms whose paramters are contained in such a $D$, in other words, on all
those atoms for which there is an $a_{\lambda}\in\\{a_{1},\dots,a_{n}\\}$ that
does not occur in $\lambda$. Thus ${\omega_{1}}_{D}$ and ${\omega_{2}}_{D}$
agree on the truth value of all atoms in $\varphi$, and thus on the truth
value of $\varphi$ itself. Conversely, let $\tilde{\varphi}$ be a set of
worlds that does not mention a tuple $a_{1},\dots,a_{n}$. Then let $\varphi$
be defined as follows:
For every $\omega\in\tilde{\varphi}$, let $\varphi_{\omega}$ be the
conjunction of the $|D|$-traces of $\omega_{D}$ for all $D$ which omit at
least one $a_{i}$. Then $\varphi$ is defined as the disjunction of the
$\varphi_{\omega}$ for all $\omega\in\tilde{\varphi}$. Clearly, $\varphi$ does
not mention $a_{1},\dots,a_{n}$. It remains to show that the set of models of
$\varphi$ is exactly $\tilde{\varphi}$. Every element $\omega$ of
$\tilde{\varphi}$ is a model of $\varphi$ since it satisfies
$\varphi_{\omega}$. To see that the converse is true, let
$\omega^{\prime}\models\varphi$. Then $\omega^{\prime}\models\varphi_{\omega}$
for an $\omega\in\tilde{\varphi}$. This implies that
${\omega^{\prime}}_{D}={\omega}_{D}$ for all $D$ omitting an $a_{i}$. By the
semantic mentioning condition, this implies that
$\omega^{\prime}\in\tilde{\varphi}$. ∎

######  Definition 15.

Let $L$ be a language with maximal arity $r$. A projective $L$-family of
distributions $P$ satisfies the _Strong Independence Principle (SIP)_ if the
following holds:

Let $0\leq g<r$ and let $\varphi$ and $\psi$ be ground quantifier-free
formulas with values in a domain $D$ that mention no joint $g+1$-set of
constants. Furthermore, let $\theta$ be a $g$-ary trace for the elements
ocurring in both $\varphi$ and $\psi$. Then

$P_{D}(\varphi\cap\psi\mid\theta)=P(\varphi\mid\theta)\cdot
P(\psi\mid\theta).$

From Proposition 14 we can immediately deduce that the SIP is equivalent to
what we call _semantic_ SIP, where “trace” and “mentioning” are replaced by
their respective semantic equivalents.

Theorem 7 of Ronel and Vencovska’s RonelV16 paper gives a concrete
characterisation of projective distributions with SIP.

The projective distributions with SIP are exactly those obtainable as follows:

Given a signature $L$, for each domain $D=\\{a_{1},\dots,a_{n}\\}$, the
construction proceeds by induction on $g$, starting at $g=1$ and proceeding to
the highest arity of relation symbols in $L$. For every $g$, we construct a
distribution over the $g$-traces over $D$. When $g$ is the highest arity of
relation symbols ocurring in $L$, a $g$-trace over $D$ completely specifies an
world on this domain and therefore a distribution over $g$-traces over $D$ is
the same as a distribution over $L$-worlds with domain $D$.

So let $\gamma_{1},\dots,\gamma_{l}$ be an enumeration of the 1-traces over
$L$. Then specify $p_{1},\dots,p_{l}\in[0,1]$ with $p_{1}+\cdots+p_{l}=1$. For
every $a\in D$, choose the 1-trace of $a$ independently, where $\gamma_{i}$ is
chosen with probability $p_{i}$. This results in a distribution over the
1-traces over $D$.

Assume we are given a distribution over the $g$-traces over $D$.

We extend this to a distribution over the $g+1$-traces over $D$ by defining
conditional on every distribution over $g$-traces a distribution over
$g+1$-traces extending that $g$-trace. We obtain our overall distribution over
$g+1$-traces by first choosing a $g$-trace according to the distribution from
the last step and then choosing an extension according to the newly-defined
distribution. So specify for every $g$-trace $\theta$ over $\\{1,\dots,g+1\\}$
whose extensions to $g+1$-traces over $L$ are
$\gamma_{\theta,1},\dots,\gamma_{\theta,k}$, real numbers
$p_{\theta,1},\dots,p_{\theta,k}\in[0,1]$ such that (1)
$p_{\theta,1}+\cdots+p_{\theta,k}=1$ for every $g$-trace $\theta$ and (2) such
that $p_{\theta,i}=p_{\theta^{\prime},j}$ whenever the worlds described by
$\gamma_{\theta,i}$ and $\gamma_{\theta^{\prime},j}$ on $\\{1,\dots,g+1\\}$
are isomorphic (the latter requirement is necessary to ensure exchangeability
of the resulting distribution). Then for every sequence
$\vec{a}:=a_{i_{1}},\dots,a_{i_{g+1}}$ of $D$-elements with strictly ascending
indices, let $\theta_{\vec{a}}$ be the $g$-trace over $\\{1,\dots,g+1\\}$
induced by the $g$-trace over $D$ by identifying $j\in\\{1,\dots,g+1\\}$ with
$a_{i_{j}}$, and choose among the extensions $\gamma_{\theta_{\vec{a}},h}$ of
$\theta_{\vec{a}}$ independently and with probability
$p_{\theta_{\vec{a}},h}$. This results in a distribution over the $g+1$-traces
over $D$.

The parameters of the construction are the $(p_{i})$ and $(p_{\theta,i})$, and
choosing different values for these parameters generates all possible
projective families of distributions with SIP.

######  Remark 1.

If the signature is binary, the projective families satisfying SIP are exactly
the relational block models of Malhotra and Serafini [Malhotra and Serafini
(2022)]. Thus SIP distributions can also be seen as a higher-arity
generalisation of relational block models [Holland et al. (1983)].

######  Example 1.

We illustrate the procedure with a classical relational block model on a
signature $L={P,E}$ of coloured graphs, where $P$ is unary and $E$ is binary:

There are four possible 1-traces over $L$, stating whether $P(1)$ is true or
false and whether $E(1,1)$ is true or false. Let $\gamma_{1}$ express that
both are false, $\gamma_{2}$ express that $P(1)$ is true and $E(1,1)$ is
false, $\gamma_{2}$ express that $P(1)$ is false and $E(1,1)$ is true and
$\gamma_{4}$ express that both are true. Thus one can specify $p_{1}$,
$p_{2}$, $p_{3}$ and $p_{4}$, the probabilities of each of the four
possibilities. If we want to define a distribution over loop-free graphs in
which $P$ is determined completely randomly, we can set $p_{1}=p_{2}=0.5$ and
$p_{3}=p_{4}=0$. Then for every pair of nodes $(a,b)$, there are four
possibilities for the edge relation: (1) There can be no edge, (2) there is an
edge from $a$ to $b$ but not vice versa, (3) there is an edge from $b$ to $a$
but not vice versa, and (4) there are edges both from $a$ to $b$ and vice
versa. Say that we want to define a distribution over undirected graphs, and
that there should be a higher likelihood for two edges to be connected if both
nodes satisfy $P$. Then we might set $p_{\theta,1}$ to be 0.3 if $\theta$
implies that both nodes satisfy $P$, and 0.1 if not, and set $p_{\theta,4}$ to
be 0.7 and 0.9 respectively. Since we want to enforce only undirected graphs,
we set all $p_{\theta,2}$ and $p_{\theta,3}$ to zero.

Then the overall distribution over coloured graphs on a given node set is
defined by first throwing a fair coin for every node to determine whether the
node satisfies $P$ or not, and then to go through all pairs of nodes and throw
a biased coin to determine whether the pair of nodes is connected by an edge
or not. The bias of that coin depends on whether the two nodes both satisfy
$P$ or not.

###  3.2 Projective generalised probabilistic logic programs

In this subsection, we will prove our main result, characterising the
distributions induced by projective generalised probabilistic logic programs.

######  Theorem 16.

Every projective generalised PLP satisfies SIP.

###### Proof.

We show that every projective generalised PLP satisfies semantic SIP. So let
$(P,\Pi)$ be a projective generalised PLP.

Let $\varphi_{1},\varphi_{2}\subseteq\Omega_{D}^{L}$ not mention any joint
$g+1$-ary trace and let $\theta$ be a $g$-ary trace over $D$. We show that
$\Pi^{-1}(\theta)$ is a $g$-ary trace over $D$ or the empty set, and that
$\Pi^{-1}(\varphi_{1})$ and $\Pi^{-1}(\varphi_{2})$ do not mention any joint
$g+1$-ary trace. Then we can derive the statement from semantic SIP for free
distributions.

  1. 1.

“$\Pi^{-1}(\theta)$ is a $g$-ary trace over $D$ or the empty set.”

Let ‘$\Pi^{-1}(\theta)$ be nonempty. Then the following equalities demonstrate
that $\Pi^{-1}(\theta)$ is a $g$-ary trace over $D$:

$\displaystyle\Pi^{-1}(\theta)$
$\displaystyle=\\{\omega\in\Omega_{D}^{L^{\prime}}\mid{\Pi(\omega)}_{D_{i}}=\omega_{i}\forall_{D_{i}\subseteq
D:|D|=y}\\}$ (3.1)
$\displaystyle=\\{\omega\in\Omega_{D}^{L^{\prime}}\mid{\Pi(\omega_{D_{i}})}=\omega_{i}\forall_{D_{i}\subseteq
D:|D|=y}\\}$ (3.2)
$\displaystyle=\\{\omega\in\Omega_{D}^{L^{\prime}}\mid\omega_{D_{i}}\in\Pi^{-1}(\omega_{i})\forall_{D_{i}\subseteq
D:|D|=y}\\}$ (3.3)
$\displaystyle=\\{\omega\in\Omega_{D}^{L^{\prime}}\mid\omega_{D_{i}}=\omega_{i}^{L^{\prime}}\forall_{D_{i}\subseteq
D:|D|=y}\\}$ (3.4)

  2. 2.

“ $\Pi^{-1}(\varphi_{1})$ and $\Pi^{-1}(\varphi_{2})$ do not mention any joint
$g+1$-ary trace”. We show that generally whenever $\varphi$ does not mention a
$g+1$-ary tuple, then $\Pi^{-1}(\varphi)$ does not mention a $g+1$-ary tuple
either. So let $a_{1},\dots,a_{g+1}$ be a tuple of distinct elements of $D$
and $\omega_{1}$ and $\omega_{2}$ $L^{\prime}$-worlds with domain $D$ such
that ${\omega_{1}}_{D^{\prime}}={\omega_{2}}_{D^{\prime}}$ for all
$D^{\prime}\subseteq D$ omitting an $a_{i}$ and
$\omega_{1}\in\Pi^{-1}(\varphi)$.

It remains to show that $\Pi(\omega_{2})\in\varphi$. By the assumptions on
$\varphi$, it sufices to show that
${\Pi({\omega_{1}})}_{D^{\prime}}={\Pi({\omega_{2}})}_{D^{\prime}}$ for all
$D^{\prime}\subseteq D$ omitting an $a_{i}$.

This follows from

${\Pi({\omega_{1}})}_{D^{\prime}}=\Pi({\omega_{1}}_{D^{\prime}})=\Pi({\omega_{2}}_{D^{\prime}})={\Pi({\omega_{2}})}_{D^{\prime}}.$

  3. 3.

Every free distribution satisfies semantic SIP.

So let $(P,\Pi)$ be a projective generalised PLP, and let $\varphi_{1}$ and
$\varphi_{2}$ not mention a joint $g$-ary trace. Further let $\theta$ be a
$g$-ary trace. We want to show that $\varphi_{1}$ and $\varphi_{2}$ are
conditionally independent over $\theta$. The conditional probabilities of
$\varphi_{1}$, $\varphi_{2}$ and $\varphi_{1}\cap\varphi_{2}$ over $\theta$
under $(P,\Pi)$ is given by the probabilities of $\Pi^{-1}(\varphi_{1})$,
$\Pi^{-1}(\varphi_{2})$ and $\Pi^{-1}(\varphi_{1}\cap\varphi_{2})$ over
$\Pi^{-1}(\theta)$ respectively. By the analysis above, the strong
independence statement follows directly from the strong independence property
for the free distribution $P$. ∎

Generalised probabilistic logic programs always have a non-zero likelihood of
inducing a completely symmetric model, since all random predicates may be
simultaneously true or false. This is formalised in the following definition.

######  Definition 17.

Let $\theta_{g}(a_{1},\dots,a_{g+1})$ be a $g$-ary trace,
$\theta_{g+1}(a_{1},\dots,a_{g+1})$ be a $g+1$-ary trace and
$\theta_{g}\subseteq\theta_{g+1}$. Then $\theta_{g}\subseteq\theta_{g+1}$ is
an _symmetric extension_ if for every permutation $\rho$ of
$a_{1},\dots,a_{g+1}$ such that
$\theta_{g}(\rho(a_{1}),\dots,\rho(a_{g+1}))=\theta_{g}(a_{1},\dots,a_{g+1})$,
$\theta_{g+1}(\rho(a_{1}),\dots,\rho(a_{g+1}))=\theta_{g+1}(a_{1},\dots,a_{g+1})$.

A projective family of distributions $P$ is called _essentially asymmetric_ if
there is a $g$-ary trace $\theta(a_{1},\dots,a_{g+1})$ such that
$P_{\\{a_{1},\dots,a_{g+1}\\}}(\theta)>0$ and

$P_{\\{a_{1},\dots,a_{g+1}\\}}\left(\mathrm{tr}_{g+1}(\omega)\textrm{
symmetric extension of }\theta\mid\omega\models\theta\\}\right)=0.$

######  Proposition 18.

Let $(P,\Pi)$ be a projective generalised PLP. Then its induced distribution
is not essentially asymmetric.

###### Proof.

Note first that since $P$ is a free distribution, every random
$L^{\prime}$-world has non-zero probability, where $L^{\prime}$ is the
signature of the free random predicates. Let $\theta(a_{1},\dots,a_{g+1})$ be
a $g$-ary trace such that ${(P,\Pi)}_{\\{a_{1},\dots,a_{g+1}\\}}(\theta)>0$.
By Corollary 11, the $g$-trace only depends on the $g$-trace in $L^{\prime}$.
So there is a random $L^{\prime}$ world $\tilde{omega}$ on
$a_{1},\dots,a_{g+1}$ such that $\Pi(\omega^{\prime})\models\theta$ for all
$\omega^{\prime}$ whose $g$-trace coincides with that of $\tilde{\omega}$.
Then let $\omega$ be the $L^{\prime}$ world for which the $g$-trace coincides
with $\tilde{\omega}$ and all atomic formulas with $g+1$ different entries are
false. We claim that $\Pi(\omega)$ is not an asymmetric extension of
$\tilde{\omega}$. Let $\rho$ be a permutation of $a_{1},\dots,a_{g+1}$ such
that $\theta(\rho(a_{1}),\dots,\rho(a_{g+1}))=\theta(a_{1},\dots,a_{g+1})$.
Then in particular the $g$-ary $L^{\prime}$-trace of $\omega$ is invariant
under $\rho$. This implies that the $g+1$-trace of $\omega$ is also invariant
under $\rho$, since all atomic formulas with $g+1$ different entries are false
in $\omega$ and having $g+1$ different entries is conserved under $\rho$. Thus
the $g+1$-ary trace of $\Pi(\omega)$ is also invariant under $\rho$ as
desired. ∎

######  Theorem 19.

Every projective family of distribution that has the strong independence
property and is not essentially asymmetric is the reduct of a projective
generalised PLP.

###### Proof.

We have to solve two problems simultaneously:

  * •

We have to define a distribution over the $\gamma$s in accordance with the
given parameters $(p_{i})$ and $(p_{\theta,i})$.

  * •

We have to define a local ordering on $a_{1},\dots,a_{n}$, where $n$ does not
exceed the highest arity of predicates in $L$.

We begin with the first issue, revisiting the classical approach to
representing annotated disjunctions in probabilistic logic programming under
the distribution semantics (see e. g. Subsection 3.2 in Ziguzzi’s RiguzziS18
book). Assume we want to define a distribution where for any given
$a_{1},\dots,a_{n}$, exactly one of

$Q_{1}(a_{1},\dots,a_{n}),\dots,Q_{m}(a_{1},\dots,a_{n})$

is true, the probability of $Q_{i}(a_{1},\dots,a_{n})$ is $p_{i}$ and the
choices are independent for different $a_{1},\dots,a_{n}$. We introduce new
free predicates $R_{i}$, $1\leq i\leq n-1$, with probabilities
$w(R_{i}):=\frac{p_{i}}{\prod_{j=1}^{i-1}(1-w_{j})}$, and then define in $\Pi$
the following definitions for $Q_{i}$:

$\displaystyle Q_{1}$ $\displaystyle\leftarrow R_{1}.$ (3.5) $\displaystyle
Q_{2}$ $\displaystyle\leftarrow R_{2},\neg R_{1}.$ (3.6) $\displaystyle\vdots$
(3.7) $\displaystyle Q_{m}$ $\displaystyle\leftarrow\neg R_{m-1},\dots,\neg
R_{1}.$ (3.8)

We proceed by induction on $g$. For $g=1$, we introduce auxiliary unary
predicates $R_{i}$ for $\gamma_{1},\dots,\gamma_{n}$ as above. So assume that
we have induced the correct distribution on $g$-traces.

For every $g$-trace $\theta$ over $a_{1},\dots,a_{g+1}$ we could now introduce
auxiliary $g+1$-ary predicates $R_{\theta,i}$ as above to match the prescribed
distribution on $\gamma_{\theta,1},\dots,\gamma_{\theta,n}$.

However, we need to address the second issue, as we currently have conflicting
information from the $R_{\theta,i}$ for every permutation of
$a_{1},\dots,a_{g+1}$. Thus, we need to use the information on the validity of
free predicates for $a_{1},\dots,a_{g+1}$ to induce an ordering and thereby
fix a privileged permutation.

Because the distribution is not essentially asymmetric, we can assume without
loss of generality that $\gamma_{\theta^{\prime},1}$ is a symmetric extension
of nonzero conditional probability for any $g$-ary trace $\theta^{\prime}$.
Furthermore, we choose $\gamma_{\theta^{\prime},1}$ and
$\gamma_{\theta^{\prime\prime},1}$ to be isomorphic extensions whenever
$\theta^{\prime}$ and $\theta^{\prime\prime}$ are isomorphic.

Let $p_{\min}$ be the minimum of the probabilities of
$\gamma_{\theta^{\prime},1}$ for all $g$-ary traces $\theta^{\prime}$ We form
a $g+1$-ary annotated disjunction of $\mathrm{Ord}_{g+1,i}$, such that for a
given $a_{1},\dots,a_{g+1}$ the probability that there is a disjunct
$\mathrm{Ord}_{g+1,j}$ and a nontrivial permutation $\rho$ with
$\mathrm{Ord}_{g+1,j}(a_{1},\dots,a_{g+1})\land\mathrm{Ord}_{g+1,j}(\rho{a_{1}},\dots,\rho{a_{g+1}})$
is less than $p_{\min}$. We call that probability $p_{\mathrm{sym}}$. This is
always possible, since the probability of two disjuncts coinciding among the
fixed number of possible permutations limits to 0 as the number of disjuncts
$k$ increases.

Now let $R_{\theta,0}$ be defined by a rule saying that
$R_{\theta,0}(a_{1},\dots,a_{g+1})$ holds if and only if two of the
$\mathrm{Ord}$-disjuncts coincide for permutations of $a_{1},\dots,a_{n}$.
Note that $R_{\theta,0}$ itself is permutation invariant, that is, it holds
for one permutation of its arguments if and only if it holds for all
permutations of its arguments. Whenever $R_{\theta,0}$ is false, we only
consider the annotated disjunction over the
$R_{\theta,i}(a_{1},\dots,a_{g+1})$ for that permutation
$(a_{1},\dots,a_{g+1})$ for which $\mathrm{Ord}_{g+1,j}(a_{1},\dots,a_{g+1})$
is true for the highest $j$ among permutations. Since all permutations have a
different such $j$, the maximum is uniquely determined. We define
$R_{g+1,\max}(a_{1},\dots,a_{g+1})$ to be true if and only if
$(a_{1},\dots,a_{g+1})$ is the unique permutation with the maximal $j$ such
that $\mathrm{Ord}_{g+1,j}(a_{1},\dots,a_{g+1})$ is true. Whenever
$R_{\theta,0}(a_{1},\dots,a_{g+1})$ is false,
$R_{g+1,\max}(a_{1},\dots,a_{g+1})$ is true for exactly one permutation of
$a_{1},\dots,a_{g+1}$, and whenever $R_{\theta,0}(a_{1},\dots,a_{g+1})$ is
true, $R_{g+1,\max}(a_{1},\dots,a_{g+1})$ is false for all permutations of
$a_{1},\dots,a_{g+1}$.

Finally we can proceed with the annotated disjunction for

$\gamma 1_{\theta,1},\gamma 2_{\theta,1},\dots,\gamma_{\theta,n},$

where $\gamma 1_{\theta,1}$ holds with probability $p_{\mathrm{sym}}$, the
probability of $\gamma 2_{\theta,1}$ is the difference between the
probabilities of $\gamma_{\theta}$ and $\gamma 1_{\theta,1}$ and
$\gamma_{\theta,1}$ is defined as holding whenever $\gamma 1_{\theta,1}$ or
$\gamma 2_{\theta,1}$ holds. Let $R_{\theta,0}$ be the auxiliary predicate
corresponding to $\gamma 1_{\theta,1}$, and then form the auxiliary rules and
probabilities as before, but appending $R_{g+1,\max}(a_{1},\dots,a_{g+1})$ to
every rule as follows (where the arguments have been omitted for readability
and are always assumed to be $a_{1},\dots,a_{g+1}$).

$\displaystyle\gamma 1_{\theta,1}$ $\displaystyle\leftarrow R_{\theta,0}.$
(3.9) $\displaystyle\gamma 2_{\theta,1}$ $\displaystyle\leftarrow
R_{\theta,1},R_{g+1,\max}.$ (3.10) $\displaystyle\gamma_{\theta,2}$
$\displaystyle\leftarrow R_{\theta,2},\neg R_{\theta,1},R_{g+1,\max}.$ (3.11)
$\displaystyle\vdots$ (3.12) $\displaystyle\gamma_{\theta,n}$
$\displaystyle\leftarrow\neg R_{m-1},\dots,\neg R_{1},R_{g+1,\max}.$ (3.13)

Since $R_{g+1,\max}$ holds for exactly one permutation whenever $R_{\theta,0}$
is false, the rules for $\gamma 2_{\theta,1}$ and below fire for exactly one
permutation, so there is no conflict between different permutations. When
$R_{\theta,0}$ holds, it holds for all permutations, but there is still no
conflict since all $\gamma_{\theta,1}$ are symmetric and different
permutations have isomorphic $\theta$, hence isomorphic $\gamma_{\theta,1}$.

∎

##  4 Discussion and conclusion

We introduced a functorial definition of projectivity and the generalised
distribution semantics, capturing the core idea of the distribution semantics
independently of the deterministic framework that is used on top of it.

The main results of the paper showed that all projective families of
distributions that can be represented in the generalised distribution
semantics satisfy the Strong Independence Property, which restricts models to
a stochastic-block-model construction as well as an additional property that
ensures that symmetry is possible. In practice, one is less interested in the
total distribution of a probabilistic logic program and more in its reducts;
the free component of the probabilstic logic program is usually seen as “error
terms” that are marginalised out, and the deterministic part will often
contain auxiliary predicates too. Thus the main results give a complete
characterisation of the reducts of probabilistic logic programs as exactly the
reducts of projective families of distributions with the SIP that are not
essentially asymmetric. Unfortunately SIP is not conserved under reduct, since
reducts of traces are usually not traces in the smaller vocabulary. However,
the (Constant) Independence Property, a much studied weaker condition than
SIP, is clearly preserved (see [Paris and Vencovská (2015), Ronel and
Vencovská (2016)] for this notion and the following paragraphs):

######  Definition 20.

Let $\varphi$ and $\psi$ be quantifier-free $L$ formulas whose variables have
been ground to elements of a domain, and who do not mention any joint element.
Then the probability of $\varphi\wedge\psi$ is the product of the
probabilities of $\varphi$ and $\psi$.

Therefore every reduct of a projective generalised PLP satisifies IP, which
precludes modelling dependencies between the validity of relation symbols for
different tuples in a projective way. In unary vocabularies, the situation is
clearer: There, IP and SIP coincide, and the families that can be modelled are
precisely those which are expressible by independently choosing 1-traces for
every element according to a prescribed probability for every 1-trace. The
restrictiveness of this fragment can be gleaned from de Finetti’s
representation theorem, which represents any projective family of
distributions over a unary vocabulary as an infinite mixture of such basic
distributions.

This leads in to the next dimension of generalisation: In general,
probabilistic logic programming also allows propositions, that is, 0-ary
predicates. These straightforwardly extend the distributions that can be
represented as reducts by allowing finite mixtures of the distributions that
can be represented without them [Weitkämper (2021)]. It is clear that neither
of the independence properties generalise to mixtures of distributions. In the
unary case, this allows for representing finite mixtures of the basic
distributions. However, the (non-trivial) distributions of “Carnap’s
continuum”, the fundamental distributions of unary pure inductive logic, are
all infinite mixtures and therefore cannot be represented by generalised PLP.

In the polyadic, the situation is more complicated. Unlike in the unary case,
not every projective family of distributions is an infinite mixture of
distributions with SIP. Indeed, all infinite mixtures of SIP distributions
share a strengthened notion of exchangeability known as signature
exchangeability [Ronel and Vencovská (2016)]. In the binary case, it is known
that a projective distribution has signature exchangeability if and only if it
is an infinite mixture of SIP distributions; in higher arities this is still
open. However, signature exchangeability is not conserved under reducts
either, and we do not know of a weaker property implied by it that is
conserved.

While the generalised distribution semantics captures classical probabilistic
logic programming based on logic programming with stratified negation as well
as any extensions thereof that also has a unique model for any logic program,
other extensions of logic programming such as answer set programming or
disjunctive logic programming go beyond this and support programs with several
stable models. There are different approaches for adding probabilistic facts
to such extensions. One way to retain a unique probability distribution over
models of a domain is to assume the principle of indifference. This means
simply dividing the weight equally between each of the multiple stable models.
This concept has been realised in the languages P-Log [Baral et al. (2009)]
and Probabilistic Disjunctive Logic Programming [Ngo (1996)] for answer set
programming and disjunctive logic programming respectively.

Such a set-up us outside the generalised distribution semantics, since we no
longer allocate a unique extension to every intensional world. Indeed, we can
see that it is not generally possible to extend the intensional vocabulary and
obtain any P-log program or disjunctiv elogic program as a reduct, since both
can define essentially asymmetric models. Take for instance the answer set
program

$R(x,y)\leftarrow\neg R(y,x),x\neq y.$

The stable models of this answer set program are precisely those where each
two nodes $a$ and $b$ are connected by exactly one directed edge, either from
$a$ to $b$ or from $b$ to $a$. By the principle of indifference, every such
model is allocated equal probability; however, none of them are essentially
asymmetric.

The same argument applies to probabilistic disjunctive logic programming,
using the disjunctive logic program

$R(x,y)\vee R(y,x).$

in place of the answer set program given above.

## References

  * Baral et al. (2009) Baral, C., Gelfond, M., and Rushton, J. N. 2009\.  Probabilistic reasoning with answer sets.  Theory Pract. Log. Program. 9, 1, 57–144.
  * Carnap (1950) Carnap, R. 1950\.  Logical Foundations of Probability.  University of Chicago Press.
  * Cozman and Mauá (2019) Cozman, F. G. and Mauá, D. D. 2019\.  The finite model theory of bayesian network specifications: Descriptive complexity and zero/one laws.  Int. J. Approx. Reason. 110, 107–126.
  * De Raedt and Kimmig (2015) De Raedt, L. and Kimmig, A. 2015\.  Probabilistic (logic) programming concepts.  Mach. Learn. 100, 1, 5–47.
  * Holland et al. (1983) Holland, P. W., Laskey, K. B., and Leinhardt, S. 1983\.  Stochastic blockmodels: First steps.  Social Networks 5, 2, 109–137.
  * Jaeger and Schulte (2018) Jaeger, M. and Schulte, O. 2018\.  Inference, learning, and population size: Projectivity for SRL models.  In Eighth International Workshop on Statistical Relational AI (StarAI).
  * Jaeger and Schulte (2020) Jaeger, M. and Schulte, O. 2020\.  A complete characterization of projectivity for statistical relational models.  In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, C. Bessiere, Ed. ijcai.org, 4283–4290.
  * Koponen (2020) Koponen, V. 2020\.  Conditional probability logic, lifted bayesian networks, and almost sure quantifier elimination.  Theor. Comput. Sci. 848, 1–27.
  * Malhotra and Serafini (2022) Malhotra, S. and Serafini, L. 2022\.  On projectivity in Markov logic networks.
  * Ngo (1996) Ngo, L. 1996\.  Probabilistic disjunctive logic programming.  In UAI ’96: Proceedings of the Twelfth Annual Conference on Uncertainty in Artificial Intelligence, Reed College, Portland, Oregon, USA, August 1-4, 1996, E. Horvitz and F. V. Jensen, Eds. Morgan Kaufmann, 397–404.
  * Paris and Vencovská (2015) Paris, J. and Vencovská, A. 2015\.  Pure inductive logic.  Perspectives in Logic. Association for Symbolic Logic, Ithaca, NY; Cambridge University Press, Cambridge.
  * Riguzzi and Swift (2018) Riguzzi, F. and Swift, T. 2018\.  A survey of probabilistic logic programming.  In Declarative Logic Programming: Theory, Systems, and Applications, M. Kifer and Y. A. Liu, Eds. ACM / Morgan & Claypool, 185–228.
  * Ronel and Vencovská (2016) Ronel, T. and Vencovská, A. 2016\.  The principle of signature exchangeability.  Journal of Applied Logic 15, 16–45.
  * Sato (1995) Sato, T. 1995\.  A statistical learning method for logic programs with distribution semantics.  In Logic Programming, Proceedings of the Twelfth International Conference on Logic Programming, Tokyo, Japan, June 13-16, 1995, L. Sterling, Ed. MIT Press, 715–729.
  * Suciu et al. (2011) Suciu, D., Olteanu, D., Ré, C., and Koch, C. 2011\.  Probabilistic Databases.  Synthesis Lectures on Data Management. Morgan & Claypool Publishers.
  * Weitkämper (2021) Weitkämper, F. 2021\.  An asymptotic analysis of probabilistic logic programming, with implications for expressing projective families of distributions.  Theory Pract. Log. Program. 21, 6, 802–817.


# GSLB: The Graph Structure Learning Benchmark

Zhixun Li1 Liang Wang2,3 Xin Sun4 Yifan Luo5 Yanqiao Zhu6 Dingshuo Chen2,3
Yingtao Luo7 Xiangxin Zhou2,3 Qiang Liu2,3 Shu Wu2,3 Liang Wang2,3,4 Jeffrey
Xu Yu1
1 Department of Systems Engineering and Engineering Management
The Chinese University of Hong Kong
2Center for Research on Intelligent Perception and Computing
State Key Laboratory of Multimodal Artificial Intelligence Systems
Institute of Automation, Chinese Academy of Sciences
3 School of Artificial Intelligence, University of Chinese Academy of Sciences
4Department of Automation, University of Science and Technology of China
5School of Cyberspace Security, Beijing University of Posts and
Telecommunications
6Department of Computer Science, University of California, Los Angeles
7Heinz College of Information Systems and Public Policy, Machine Learning
Department
School of Computer Science, Carnegie Mellon University
[regular] Primary contact<EMAIL_ADDRESS>

###### Abstract

Graph Structure Learning (GSL) has recently garnered considerable attention
due to its ability to optimize both the parameters of Graph Neural Networks
(GNNs) and the computation graph structure simultaneously. Despite the
proliferation of GSL methods developed in recent years, there is no standard
experimental setting or fair comparison for performance evaluation, which
creates a great obstacle to understanding the progress in this field. To fill
this gap, we systematically analyze the performance of GSL in different
scenarios and develop a comprehensive Graph Structure Learning Benchmark
(GSLB) curated from 20 diverse graph datasets and 16 distinct GSL algorithms.
Specifically, GSLB systematically investigates the characteristics of GSL in
terms of three dimensions: effectiveness, robustness, and complexity. We
comprehensively evaluate state-of-the-art GSL algorithms in node- and graph-
level tasks, and analyze their performance in robust learning and model
complexity. Further, to facilitate reproducible research, we have developed an
easy-to-use library for training, evaluating, and visualizing different GSL
methods. Empirical results of our extensive experiments demonstrate the
ability of GSL and reveal its potential benefits on various downstream tasks,
offering insights and opportunities for future research. The code of GSLB is
available at: https://github.com/GSL-Benchmark/GSLB.

##  1 Introduction

Graphs, structures made of vertices and edges, are ubiquitous in real-world
applications. A wide variety of applications spanning social network
[zhang2022robust, fan2019graph], molecular property prediction
[wieder2020compact, hao2020asgn], fake news detection [xu2022evidence,
bian2020rumor], and fraud detection [li2022devil, liu2021pick] have found
graphs instrumental in modeling complex systems. In recent years, Graph Neural
Networks (GNNs) have attracted increasing attention due to their powerful
ability to learn node or graph representations. However, most of the GNNs
heavily rely on the assumption that the initial structure of the graph is
trustworthy enough to serve as ground-truth for training. Due to uncertainty
and complexity in data collection, graph structures are inevitably redundant,
biased, noisy, incomplete, or the original graph structures are even
unavailable, which will bring great challenges for the deployment of GNNs in
real-world applications.

To mitigate the aforementioned problems, Graph Structure Learning (GSL)
[chen2020iterative, zheng2020robust, luo2021learning, fatemi2021slaps,
zhu2021survey, zhang2021mining] has become an important theme in graph
learning. GSL aims to make the computation structure of GNNs more suitable for
downstream tasks and improve the quality of the learned representations. While
it is widespread in different communities and the research enthusiasm for GSL
is increasing, there is no standardized benchmark that could offer a fair and
consistent comparison of different GSL algorithms. Moreover, due to the
complexity and diversity of graph datasets, the experimental setups in
existing work are not consistent, such as varying ratios of the training set
and different train/validation/test splits. This poses a great obstacle to a
holistic understanding of the current research status. Therefore, the
development of a standardized and comprehensive benchmark for GSL is an urgent
need within the community.

Table 1: An overview of GSLB. Both algorithms and datasets are divided into
three categories: homogeneous node-level, heterogeneous node-level, and graph-
level. The evaluation is divided into three dimensions: effectiveness,
robustness, and complexity.

_Algorithms_ Homogeneous GSL LDS [franceschi2019learning], GRCN [yu2021graph],
ProGNN [jin2020graph], IDGL [chen2020iterative], CoGSL [liu2022compact],
SUBLIME [liu2022towards], GEN [wang2021graph], STABLE [li2022reliable],
NodeFormer [wu2022nodeformer], SLAPS [fatemi2021slaps], GSR [zhao2023self],
HES-GSL [wu2023homophily] Heterogeneous GSL GTN [yun2019graph], HGSL
[zhao2021heterogeneous] Graph-level GSL HGP-SL [zhang2019hierarchical], VIB-
GSL [sun2022graph] _Datasets_ Homogeneous datasets Cora [yang2016revisiting],
Citeseer [yang2016revisiting], Pubmed [yang2016revisiting], ogbn-arxiv
[hu2020open], Polblogs, Cornell [pei2020geom], Texas [pei2020geom], Wisconsin
[pei2020geom], Actor [tang2009social] Heterogeneous datasets ACM
[yun2019graph], DBLP [yun2019graph], Yelp [lu2019relation] Graph-level
datasets IMDB-B [cai2018simple], IMDB-M [cai2018simple], COLLAB
[yanardag2015deep], REDDIT-B [yanardag2015deep], MUTAG [debnath1991structure],
PROTEINS [borgwardt2005protein], Peptides-Func [dwivedi2022long], Peptides-
Struct [dwivedi2022long] _Evaluations_ Effectiveness Homogeneous node
classification (Topology Refinement/Topology Inference), Heterogeneous node
classification, Graph-level tasks Robustness Supervision signal robustness,
Structure robustness, Feature robustness Complexity Time complexity, Space
complexity

In this work, we propose Graph Structure Learning Benchmark (GSLB), which
serves as the first comprehensive benchmark for GSL. Our benchmark encompasses
16 state-of-the-art GSL algorithms and 20 diverse graph datasets covering
homogeneous node-level, heterogeneous node-level, and graph-level tasks. We
systematically investigate the characteristics of GSL in terms of three
dimensions: effectiveness, robustness, and complexity. Based on these three
dimensions, we conduct an extensive comparative study of existing GSL
algorithms in different scenarios. For effectiveness, GSLB provides a fair and
comprehensive comparison of existing algorithms on homogeneous node-level,
heterogeneous node-level, and graph-level tasks, where we consider both
homophilic and heterophilic graph datasets for homogeneous node-level tasks,
and cover both Topology Refinement (TR, i.e., refining graphs from data with
the original topology) and Topology Inference (TI, i.e., inferring graphs from
data without initial topology) settings. For robustness, GSLB evaluates GSL
models under three types of noise: supervision signal noise, structure noise,
and feature noise. We also compare GSL algorithms with the models specifically
designed to improve these types of robustness. For complexity, GSLB conducts a
detailed evaluation of representative GSL algorithms in terms of time
complexity and space complexity.

Through extensive experiments, we observe that: (1) GSL generally brings
performance improvement for node-level tasks, especially on heterophilic
graphs; (2) on graph-level tasks, current GSL models bring limited improvement
and their performance varies greatly across different datasets; (3) most GSL
algorithms (especially unsupervised GSL algorithms) show impressive
robustness; (4) GSL models require significant time and memory overhead,
making them challenging to deploy on large-scale graphs. In summary, we make
the following three contributions:

  * •

We propose GSLB, the first comprehensive benchmark for graph structure
learning. We integrate 16 state-of-the-art GSL algorithms and 20 diverse graph
datasets covering homogeneous node-level, heterogeneous node-level, and graph-
level tasks. An overview of our benchmark is shown in Table 1.

  * •

To explore the ability and limitations of GSL, we systematically evaluate
existing algorithms from three dimensions: effectiveness, robustness, and
complexity. Based on the results, we reveal the potential benefits and
drawbacks of GSL to assist future research efforts.

  * •

To facilitate future work and help researchers quickly use the latest models,
we develop an easy-to-use open-source library. Besides, users can evaluate
their own models or datasets with less effort. Our code is available at
https://github.com/GSL-Benchmark/GSLB.

##  2 Problem Definition

In this section, we will briefly review the advances and basic concepts of
GSL. Given an undirected graph $\mathcal{G}=(\mathbf{A},\mathbf{X})$, where
$\mathbf{A}\in\mathbb{R}^{N\times N}$ is the adjacency matrix, $a_{uv}=1$ if
edge $(u,v)$ exists and $a_{uv}=0$ otherwise, and
$\mathbf{X}\in\mathbb{R}^{N\times F}$ is the node features matrix, $N$ is the
number of nodes, $F$ is the dimension of node features. Given an optional
graph $\mathcal{G}$, the goal of GSL is to jointly optimize computation graph
$\mathcal{G}^{\star}=(\mathbf{A}^{\star},\mathbf{X})$ and the parameters of
graph encoder $\Theta_{f}$ to obtain high-quality node representations
$\mathbf{Z}^{\star}\in\mathbb{R}^{N\times F^{\prime}}$ for downstream tasks,
where $\mathbf{A}^{\star}$ is the refined graph by graph learner.

In general, the objective of GSL can be summarized as the following formula:

$\mathcal{L}_{\text{GSL}}=\mathcal{L}_{\text{Task}}(\mathbf{Z}^{\star},\mathbf{Y})+\lambda\mathcal{L}_{\text{Reg}}(\mathbf{A}^{\star},\mathbf{Z}^{\star},\mathcal{G})$
(1)

where the first term $\mathcal{L}_{\text{Task}}$ refers to a task-specific
objective with respect to the learned representation $\mathbf{Z}^{\star}$ and
ground-truth $\mathbf{Y}$, the second term $\mathcal{L}_{\text{Reg}}$ imposes
constraints on the learned graph structure and representations, and $\lambda$
is a hyper-parameter that controls the trade-off between the two terms. The
general framework of GSL is shown in Figure 1.

Figure 1: A general framework of Graph Structure Learning (GSL). GSL methods
start with input features and an optional initial graph structure. Its
corresponding computation graph is refined/inferred through a structure
learning module. With the learned computation graph, Graph Neural Networks
(GNNs) are used to generate graph representations.

##  3 GSLB: Graph Structure Learning Benchmark

In this section, we introduce the overview of Graph Structure Learning
Benchmark, with considerations of algorithms (Section 3.1), datasets (Section
3.2) and evaluations (Section 3.3).

###  3.1 Benchmark Algorithms

Table 1 shows the overall 16 algorithms integrated in GSLB. They are divided
into three categories: homogeneous GSL, heterogeneous GSL, and graph-level
GSL. We briefly introduce each category in the following, and more details are
provided in Appendix LABEL:appen:alg.

Homogeneous GSL. Most of the existing GSL algorithms are designed for
homogeneous graphs. They assume there is only one type of nodes and edges in
the graph. We select 7 TR-oriented algorithms including GRCN [yu2021graph],
ProGNN [jin2020graph], IDGL [chen2020iterative], GEN [wang2021graph], CoGSL
[liu2022compact], STABLE [li2022reliable], and GSR [zhao2023self]. For TI-
oriented algorithms, we select SUBLIME [liu2022towards], NodeFormer
[wu2022nodeformer], SLAPS [fatemi2021slaps], and HES-GSL [wu2023homophily]. It
is worth noting that TR-oriented algorithms can only be applied if the
original graph structure is available, but we can construct a preliminary
graph based on node features (e.g., $k$NN graphs or $\epsilon$-graphs).

Heterogeneous GSL. We integrate two representative heterogeneous GSL
algorithms: Graph Transformer Networks (GTN) [yun2019graph] and Heterogeneous
Graph Structure Learning (HGSL) [zhao2021heterogeneous], which can handle the
heterogeneity and capture complex interactions in heterogeneous graphs.

Graph-level GSL. Graph-level GSL algorithms aim to refine each graph structure
in datasets. We select two graph-level algorithms: Hierarchical Graph Pooling
with Structure Learning (HGP-SL) [zhang2019hierarchical] and Variational
Information Bottleneck guided Graph Structure Learning (VIB-GSL)
[sun2022graph].

###  3.2 Benchmark Datasets

To comprehensively and effectively evaluate the characteristics of GSL in the
field of graph learning, we have integrated a large number of datasets from
various domains for different types of tasks. For node-level tasks, to
evaluate the most mainstream task of GSL, node classification, we use four
citation networks (i.e., Cora, Citeseer, Pubmed [yang2016revisiting]), and
ogbn-arxiv [hu2020open], three website networks from WebKB (i.e., Cornell,
Texas, and Wisconsin [pei2020geom]), and a cooccurrence network Actor with
homophily ratio ranging from strong homophily to strong heterophily.
Subsequently, to validate the effectiveness of GSL in heterogeneous node
classification, we utilized three heterogeneous graph datasets (i.e., DBLP
[yun2019graph], ACM [yun2019graph], and Yelp [lu2019relation]). To investigate
the robustness of GSL, we further incorporate the Polblogs dataset for
evaluation. For graph-level tasks, we select six public graph classification
benchmark dataset from TUDataset [morris2020tudataset] for evaluation,
including IMDB-B [cai2018simple], IMDB-M [cai2018simple], RDT-B
[yanardag2015deep], COLLAB [yanardag2015deep], MUTAG [debnath1991structure]
and PROTEINS [borgwardt2005protein]. Each dataset is a collection of graphs
where each graph is associated with a level. Besides, exploring whether GSL
can capture long-range information is an exciting topic. Therefore, we have
utilized recently proposed long-range graph datasets: Peptides-func and
Peptides-struct [dwivedi2022long]. See more details and statistics about
datasets in Appendix LABEL:appen:dataset.

###  3.3 Benchmark Evaluations

To comprehensively investigate the pros and cons of GSL, our benchmark
evaluations encompass three dimensions: effectiveness, robustness, and
complexity. For effectiveness, GSLB provides a fair and comprehensive
comparison of existing algorithms from three perspectives: homogeneous node
classification, heterogeneous node classification, and graph-level tasks. In
the case of homogeneous node classification, we evaluated them on both
homophilic and heterophilic graph datasets, conducting experiments in both TR
and TI scenarios. For graph-level, we evaluate graph-level GSL algorithms on
TUDataset and long-range graph datasets for exploring the capabilities on
graph-level tasks. For most datasets, we use accuracy as our evaluation
metric. For robustness, GSLB evaluates three types of robustness: supervision
signal robustness, structure robustness, and feature robustness. We control
the count of labels to explore the supervision signal robustness of GSL and
find that GSL exhibits excellent performance in the scenarios with few labels.
We inject random structure noise and graph topology attacks to investigate the
structure robustness. We also study the feature robustness by randomly masking
a certain proportion of node features. For complexity, we conduct a detailed
evaluation of representative GSL algorithms in terms of time complexity and
space complexity. It will help to facilitate the deployment of GSL in real-
world applications.

##  4 Experiments and Analysis

In this section, we systematically investigate the effectiveness, robustness,
and complexity of GSL algorithms by answering the following specific
questions:

  * •

For effectiveness, RQ1: How effective are the algorithms on node-level
representation learning (Section 4.2)? RQ2: Can GSL mitigate homophily
inductive bias of traditional message-passing based GNNs (Section 4.2)? RQ3:
How does GSL perform on heterogeneous graph datasets (Section 4.3)? RQ4: How
effective are the algorithms on graph-level representation learning (Section
4.4)? RQ5: Can GSL methods capture long-range information on the graph
(Appendix LABEL:appen:exp)?

  * •

For robustness, RQ6: How robust are GSL algorithms when faced with a scarcity
of labeled samples? RQ7: How robust are GSL algorithms in the face of
structure attack or noise? RQ8: How is the feature robustness of GSL? (Section
LABEL:sec:robust)

  * •

For complexity, RQ9: How efficient are these algorithms in terms of time and
space (Section LABEL:sec:complexity)?

  * •

Otherwise, RQ10: What does the learned graph structure look like (Appendix
LABEL:appen:visual)?

###  4.1 Experimental Settings

All algorithms in GSLB are implemented by PyTorch [paszke2019pytorch], and
unless specifically indicated, the encoders for all algorithms are Graph
Convolutional Networks. All experiments are conducted on a Linux server with
GPU (NVIDIA GeForce 3090 and NVIDIA A100) and CPU (AMD EPYC 7763), using
PyTorch 1.13.0, DGL 1.1.0 [wang2019deep] and Python 3.9.16.

###  4.2 Performance on node-level representation learning

For node-level representation learning, we conduct experiments on homogeneous
graph datasets under both TR and TI scenarios, and use classification accuracy
as our evaluation metric. Table 2 shows the experimental results of various
GSL algorithms under the standard setting of transductive node classification
task in the TR scenario. We can observe that: 1) Most GSL algorithms generally
show improvements in node classification task, particularly on datasets with
high heterophily ratio. Due to the presence of heterophilic connections in
heterophily graphs, where nodes are often connected to nodes with different
labels, it violates the homophily assumption of message-passing neural
networks. As a result, traditional GNNs like GCN and GAT exhibit poor
performance. However, GSL can improve significantly on heterophily graph
datasets by learning new graph structures based on downstream tasks and
specific learning objectives, thus enhancing the homophily of the graph and
promoting the performance on node-level representation learning. 2) SUBLIME
achieves optimal or near-optimal results on most datasets. It learns graph
structure through contrastive learning in an unsupervised manner. As mentioned
in the recent literature [fatemi2021slaps], optimizing graph structures solely
based on label information is insufficient. Leveraging a large and abundant
amount of unlabeled information can enhance the performance of GSL. 3) The
scalability of GSL still needs improvement, as only a few models can be
trained on large-scale datasets (e.g., ogbn-arxiv). We will discuss the
scalability of GSL algorithms in detail in a subsequent section (Section
LABEL:sec:complexity).

Table 3 shows the experimental results of the transductive node classification
task in the TI scenario. Some GSL algorithms are designed for TR scenario
(i.e., GRCN, IDGL, etc.), so we use kNN graphs as their original graph
structure. As we can observe, on the homophily graph datasets, GSL outperforms
baselines, such as MLP, GCNknn and GATknn. However, on the heterophily graph
datasets, most GSL algorithms often have difficulty achieving better results
than baseline models. As mentioned in earlier literature, a network with
randomness tends to get better performance utilizing kNN for direct
information propagation [jin2021universal]. Therefore, traditional message-
passing neural networks with kNN graphs demonstrate powerful performance. In
addition, as observed in the TR scenario, models that leverage self-
supervision to extract abundant unlabeled information often achieve better
performance.

Table 2: Accuracy $\pm$ STD comparison (%) under the standard setting of
transductive node classification task in the Topology Refinement (TR)
scenario, which means the original graph structure is available for each
method. Performance is averaged from 10 independent repetitions. The highest
results are highlighted with bold, while the second highest results are marked
with underline. "OOM" denotes out of memory.

Cora Citeseer Pubmed ogbn-arxiv Cornell Texas Wisconsin Actor Edge Hom. 0.81
0.74 0.80 0.65 0.12 0.06 0.18 0.22 GCN 81.46$\pm$0.58 71.36$\pm$0.31
79.18$\pm$0.29 70.77$\pm$0.19 47.84$\pm$5.55 57.83$\pm$2.76 57.45$\pm$4.30
30.01$\pm$0.77 GAT 81.41$\pm$0.77 70.69$\pm$0.58 77.85$\pm$0.42 69.90$\pm$0.25
46.22$\pm$6.33 54.05$\pm$7.35 57.65$\pm$7.75 28.91$\pm$0.83 GPRGNN
83.66$\pm$0.77 71.64$\pm$0.49 75.99$\pm$1.63 50.80$\pm$0.29 76.76$\pm$5.30
85.14$\pm$3.68 83.33$\pm$3.42 34.09$\pm$1.09 LDS 83.01$\pm$0.41 73.55$\pm$0.54
OOM OOM 47.87$\pm$7.14 58.92$\pm$4.32 61.70$\pm$3.58 31.05$\pm$1.31 GRCN
83.87$\pm$0.49 72.43$\pm$0.61 78.92$\pm$0.39 OOM 54.32$\pm$8.24 62.16$\pm$7.05
56.08$\pm$7.19 29.97$\pm$0.71 ProGNN 80.30$\pm$0.57 68.51$\pm$0.52 OOM OOM
54.05$\pm$6.16 48.37$\pm$12.17 62.54$\pm$7.56 22.35$\pm$0.88 IDGL
83.88$\pm$0.42 72.20$\pm$1.18 80.00$\pm$0.38 OOM 50.00$\pm$8.98 62.43$\pm$6.09
59.41$\pm$4.11 28.16$\pm$1.41 GEN 80.21$\pm$1.72 71.15$\pm$1.81 78.91$\pm$0.69
OOM 57.02$\pm$7.19 65.94$\pm$1.38 66.07$\pm$3.72 27.21$\pm$2.05 CoGSL
81.76$\pm$0.24 73.09$\pm$0.42 OOM OOM 52.16$\pm$3.21 59.46$\pm$4.36
58.82$\pm$1.52 32.95$\pm$1.20 SUBLIME 83.40$\pm$0.42 72.30$\pm$1.09
80.90$\pm$0.94 71.75$\pm$0.36 70.54$\pm$5.98 77.03$\pm$4.23 78.82$\pm$6.55
33.57$\pm$0.68 STABLE 80.20$\pm$0.68 68.91$\pm$1.01 OOM OOM 44.03$\pm$4.05
55.24$\pm$6.04 53.00$\pm$5.27 30.18$\pm$1.00 NodeFormer 80.28$\pm$0.82
71.31$\pm$0.98 78.21$\pm$1.43 55.40$\pm$0.23 42.70$\pm$5.51 58.92$\pm$4.32
48.43$\pm$7.02 25.51$\pm$1.77 GSR 82.48$\pm$0.43 71.10$\pm$0.25 78.09$\pm$0.53
OOM 44.32$\pm$2.16 60.81$\pm$4.87 56.86$\pm$1.24 30.23$\pm$0.38

Table 3: Accuracy $\pm$ STD comparison (%) under the standard setting of
transductive node classification task in the Topology Inference (TI) scenario,
which means the original graph structure is not available for each method.

Cora Citeseer Pubmed ogbn-arxiv Cornell Texas Wisconsin Actor Edge Hom. 0.81
0.74 0.80 0.65 0.12 0.06 0.18 0.22 MLP 58.55$\pm$0.80 59.52$\pm$0.64
73.00$\pm$0.30 55.21$\pm$0.11 71.35$\pm$6.19 80.27$\pm$5.93 84.71$\pm$3.14
35.49$\pm$1.04 GCNknn 66.10$\pm$0.44 68.33$\pm$0.89 69.23$\pm$0.49
55.21$\pm$0.22 75.14$\pm$2.65 75.95$\pm$4.43 84.12$\pm$3.97 32.98$\pm$0.49
GATknn 64.62$\pm$1.04 68.05$\pm$1.12 68.76$\pm$0.80 55.92$\pm$0.30
74.05$\pm$5.16 76.49$\pm$4.99 82.16$\pm$4.06 31.67$\pm$1.19 GPRGNNknn
69.27$\pm$0.62 70.29$\pm$0.54 68.19$\pm$1.19 51.39$\pm$0.13 75.68$\pm$2.70
81.08$\pm$4.18 84.12$\pm$3.22 34.71$\pm$1.51 LDS 69.87$\pm$0.41 72.43$\pm$0.61
OOM OOM 72.65$\pm$3.86 70.20$\pm$5.07 78.14$\pm$4.50 32.39$\pm$0.79 GRCNknn
69.48$\pm$0.66 68.41$\pm$0.50 68.96$\pm$0.85 OOM 71.08$\pm$6.84 74.32$\pm$5.02
78.63$\pm$4.92 30.83$\pm$0.76 ProGNNknn 67.11$\pm$0.56 64.55$\pm$0.95 OOM OOM
71.35$\pm$4.04 71.89$\pm$5.69 72.94$\pm$7.93 31.56$\pm$1.14 IDGLknn
69.74$\pm$0.57 66.33$\pm$0.84 74.01$\pm$0.64 OOM 72.70$\pm$4.75 75.40$\pm$4.75
79.21$\pm$3.94 33.07$\pm$1.37 GENknn 66.95$\pm$1.40 67.29$\pm$1.17
69.76$\pm$1.53 OOM 71.08$\pm$5.54 74.59$\pm$3.46 81.76$\pm$2.91 31.28$\pm$1.06
CoGSLknn 66.65$\pm$0.37 68.72$\pm$0.84 OOM OOM 70.27$\pm$3.42 72.70$\pm$4.26
76.96$\pm$5.25 34.52$\pm$1.56 GSRknn 66.28$\pm$0.59 66.77$\pm$0.62
68.49$\pm$1.49 OOM 70.27$\pm$3.62 74.86$\pm$3.63 78.62$\pm$5.91 33.73$\pm$1.12
SLAPS 72.28$\pm$0.97 70.71$\pm$1.13 74.50$\pm$1.47 55.19$\pm$0.21
74.59$\pm$3.67 79.19$\pm$4.99 81.96$\pm$3.26 37.16$\pm$0.91 SUBLIME
72.74$\pm$1.91 72.63$\pm$0.60 75.08$\pm$0.55 55.57$\pm$0.18 72.35$\pm$3.57
75.51$\pm$5.08 82.14$\pm$2.62 32.20$\pm$1.02 NodeFormer 54.35$\pm$5.33
45.90$\pm$5.42 59.83$\pm$6.50 55.37$\pm$0.23 42.70$\pm$5.51 58.92$\pm$4.32
48.24$\pm$6.63 29.24$\pm$1.68 HES-GSL 73.68$\pm$1.04 70.12$\pm$1.11
77.08$\pm$0.78 56.46$\pm$0.27 66.22$\pm$6.19 74.05$\pm$6.42 79.61$\pm$5.28
36.73$\pm$0.76

###  4.3 Performance on heterogeneous graph node-level representation learning

In this section, we evaluate the performance of GSL algorithms on
heterogeneous node classification task and use Macro-F1 and Micro-F1 as our
evaluation metrics. Table 4 shows the experimental results on heterogeneous
graph datasets. By observing the results, we can find that: 1) Because GTN and
HGSL consider both heterogeneity and structure learning, they generally
outperform other models on heterogeneous graph datasets. 2) GSL algorithms
generally outperform the vanilla GNN models (e.g. GCN and GAT) since they have
learned better structures to facilitate message passing. 3) Due to the
majority of GSL algorithms not explicitly accounting for heterogeneity, they
may exhibit poorer performance on heterogeneous graph datasets. 4) Some
datasets (e.g. Yelp) exhibit stronger heterogeneity, and on such datasets,
models that consider heterogeneity (e.g. HAN, GTN, and HGSL) perform
significantly better.

Table 4: Macro-F1 and Micro-F1 $\pm$ STD comparison (%) under the standard
setting of heterogeneous node classification task.

Method ACM DBLP Yelp Macro-F1 Micro-F1 Macro-F1 Micro-F1 Macro-F1 Micro-F1 GCN
90.27$\pm$0.59 90.18$\pm$0.61 90.01$\pm$0.32 90.99$\pm$0.28 78.01$\pm$1.89
81.03$\pm$1.81 GAT 91.52$\pm$0.62 91.46$\pm$0.62 90.22$\pm$0.37 91.13$\pm$0.40
82.12$\pm$1.47 84.43$\pm$1.56 HAN 91.67$\pm$0.39 91.47$\pm$0.22 90.53$\pm$0.24
91.47$\pm$0.22 88.49$\pm$1.73 88.78$\pm$1.40 LDS 92.35$\pm$0.43 92.05$\pm$0.26
88.11$\pm$0.86 88.74$\pm$0.85 75.98$\pm$2.35 78.14$\pm$1.98 GRCN
93.04$\pm$0.17 92.94$\pm$0.18 88.33$\pm$0.47 89.43$\pm$0.44 76.05$\pm$1.05
80.68$\pm$0.96 IDGL 91.69$\pm$1.24 91.63$\pm$1.24 89.65$\pm$0.60
90.61$\pm$0.56 76.98$\pm$5.78 79.15$\pm$5.06 ProGNN 90.57$\pm$1.03
90.50$\pm$1.29 83.13$\pm$1.56 84.83$\pm$1.36 51.76$\pm$1.46 58.39$\pm$1.25 GEN
87.91$\pm$2.78 87.88$\pm$2.61 89.74$\pm$0.69 90.65$\pm$0.71 80.43$\pm$3.78
82.68$\pm$2.84 STABLE 83.54$\pm$4.20 83.38$\pm$4.51 75.18$\pm$1.95
76.42$\pm$1.95 71.48$\pm$4.71 76.62$\pm$2.75 GEN 87.91$\pm$2.78 87.88$\pm$2.61
89.74$\pm$0.69 90.65$\pm$0.71 80.43$\pm$3.78 82.68$\pm$2.84 SUBLIME
92.42$\pm$0.16 92.13$\pm$0.37 90.98$\pm$0.37 91.82$\pm$0.27 79.68$\pm$0.79
82.99$\pm$0.82 NodeFormer 91.33$\pm$0.77 90.60$\pm$0.95 79.54$\pm$0.78
80.56$\pm$0.62 91.69$\pm$0.65 90.59$\pm$1.21 GSR 92.14$\pm$1.08 92.11$\pm$0.99
76.59$\pm$0.45 77.69$\pm$0.42 83.85$\pm$0.76 85.73$\pm$0.54 GTN 92.04$\pm$0.38
91.94$\pm$0.39 90.52$\pm$0.45 91.48$\pm$0.39 92.98$\pm$0.52 92.44$\pm$0.46
HGSL 93.23$\pm$0.50 93.13$\pm$0.51 91.58$\pm$0.40 92.49$\pm$0.35
92.79$\pm$0.44 92.24$\pm$0.48

###  4.4 Performance of GSL algorithms on graph-level tasks

In this section, we conduct graph classification experiments on four social
datasets (i.e., IMDB-B, RDT-B, COLLAB, and IMDB-M) and two biological datasets
(i.e., MUTAG and PROTEINS). Table 4.4 shows the experimental results of
average accuracy and the standard deviation of 10-fold cross-validation. We
can observe that HGP-SL (with GCN as the encoder) consistently outperforms GCN
on all datasets. However, we find that VIB-GSL exhibits strong instability
across different random seeds. And due to the absence of training scripts in
the official code111https://github.com/RingBDStack/VIB-GSL, we performed
hyperparameter tuning based on the parameter search space
($\beta\in\\{10^{-1},10^{-2},10^{-3},10^{-4},10^{-5},10^{-6}\\}$) provided in
the paper, but we are unable to surpass the performance of the baseline models
consistently. Lastly, we conducted an analysis of graph-level GSL algorithms
on long-range graph dataset [dwivedi2022long]. For detailed information,
please refer to Appendix LABEL:appen:exp.

Table 5: Accuracy $\pm$ STD comparison (%) under the setting of graph-level
classification task.