# Model Predictive Control Design for Unlocking the Energy Flexibility of Heat
Pump and Thermal Energy Storage Systems

Weihong Tang1, Yun Li1, Shalika Walker2, Tamas Keviczky1 1W. Tang, Y. Li and
T. Keviczky are with the Delft Center for Systems and Control, Delft
University of Technology, Delft, the Netherlands<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Walker is with the Kropman BV,
the Netherlands<EMAIL_ADDRESS>work was supported by the
Brains4Buildings project under the Dutch grant programme for Mission-Driven
Research, Development and Innovation (MOOI).

###### Abstract

Heat pump and thermal energy storage (HPTES) systems, which are widely
utilized in modern buildings for providing domestic hot water, contribute to a
large share of household electricity consumption. With the increasing
integration of renewable energy sources (RES) into modern power grids, demand-
side management (DSM) becomes crucial for balancing power generation and
consumption by adjusting end users’ power consumption. This paper explores an
energy flexible Model Predictive Control (MPC) design for a class of HPTES
systems to facilitate demand-side management. The proposed DSM strategy
comprises two key components: i) flexibility assessment, and ii) flexibility
exploitation. Firstly, for flexibility assessment, a tailored MPC formulation,
supplemented by a set of auxiliary linear constraints, is developed to
quantitatively assess the flexibility potential inherent in HPTES systems.
Subsequently, in flexibility exploitation, the energy flexibility is
effectively harnessed in response to feasible demand response (DR) requests,
which can be formulated as a standard mixed-integer MPC problem. Numerical
experiments, based on a real-world HPTES installation, are conducted to
demonstrate the efficacy of the proposed design.

##  I Introduction

Climate change has emerged as a pressing global concern, and prompts global
actions. To achieve carbon neutrality and sustainable energy usage, the
European Union has set an ambitious goal to increase the share of renewable
energy sources (RES), such as solar energy and wind energy, to at least 27% by
2030 [1]. However, it is well-known that due to the intermittency and
volatility of RES, growing reliance on the electricity generation from RES can
introduce significant challenges in balancing supply and demand in the power
grid, and hence lead to congestion. As a response, the concept of demand-side
management (DSM) is proposed, which entails adjusting the energy consumption
of end users according to the needs of the power grid, to balance the real-
time power generation and consumption [2, 3].

As an energy efficient and low-carbon thermal generation option, heat pumps
(HP) are widely adopted in Europe to provide thermal energy in buildings, such
as floor heating and domestic hot water usage, and the number of installations
are on a sharp rise. It is estimated that by 2027, 10 million additional heat
pumps will be installed in the EU [4]. A typical utilization of HPs is the
combination of HP and thermal storage system, which we refer to as HPTES in
this paper. With the support of TES, the thermal energy generated by HPs can
be stored, which largely increases the flexibility of electricity consumption
of HPs [5]. Considering the large amount of energy consumption of HPs in
buildings and the energy flexibility emanating from HPTES systems, it is of
interest to investigate potential improvements or replacement of the existing
rule-based control schemes in HPTES systems for achieving DSM. As an advanced
control technique, model predictive control (MPC) is regarded as a promising
and effective control scheme to be widely implemented in future building
mangement systems (BMS) due to its versatality in coping with system
constraints, economic considerations, as well as the alignment of predicted
energy consumption and availability. In [6, 7, 8, 9] and references therein,
MPC-based operation schemes are designed for HPTES systems.

While MPC-based schemes for economic operation of HPTES have been extensively
studied in literature and are shown to be effective, when considering DSM in
the form of demand response (DR) requests, there is room for further
improvement and alternative control schemes. The existing works about DSM of
HPTES follow the so-called incentive-based or price-based programs [10, 11].
As pointed out in [12], while such schemes are relatively easy to implement,
these programs fall short of full exploitation of energy flexibility and might
fail to achieve the expected energy reduction from the power grid. In order to
better utilize the energy flexibility of buildings and meet the demands of the
power grid, a two-step DSM framework is proposed in [12]. This scheme entails
assessing the energy flexibility potential of the system, and a bidirectional
communication between BMS and the power grid. Also, this two-step DSM
framework fits in the S2 standard that is developed by the European Commission
for exploiting energy flexibility in built environment [13].

In this paper, we will design an MPC-based DSM scheme based on the framework
proposed in [12] and investigate an energy flexible MPC design for a class of
HPTES systems to achieve demand-side management. A general control-oriented
model for the HPTES system is introduced. Based this model, a unified MPC
framework for quantitatively assessing the energy flexibility potential of the
HPTES system and exploting the flexibility via DR requests are designed. The
proposed flexibility assessment approach only entails considering extra linear
constraints within a typical economic MPC problem. With the proposed approach,
the energy flexibility emanated from the thermal storage tanks is utilized to
solve grid congestion problems without violating system constraints.

The remaining parts of this paper are organized as follows. Section II
describes a control-oriented model for the HPTES system. Section III provides
a unified MPC design framework for assessing and exploiting the energy
flexibility of the HPTES system. Simulation results are presented in Section
IV, followed by Conclusions in Section V.

##  II HPTES System Modelling and Problem Formulation

In this section, a general control-oriented model of the HPTES system and the
corresponding physical constraints are introduced. The HPTES system considered
in our work is composed of three main components: a heat pump, a heat
exchanger (HE), and two thermal storage tanks. The configuration of the HPTES
system that will be investigated is shown in Fig. 1, where blue lines
represent cold water flows, red lines represent hot water flows, and arrows
represent the flow directions. The mass flow rates and temperature of
corresponding pipelines that are used in developing the HPTES model are also
indicated. This configuration is based on a typical real HPTES system
installation located in an office building in the Netherlands.

Hot water from the top of Tank 1 is circulated at a mass flow rate
$\dot{m}_{c}$ going through connected taps to meet hot water usage demands.
The real-time hot water usage is $\dot{m}_{s}$, whose future values are
assumed to be predictable with sufficient accuracy from historical data. When
hot water is consumed, the same amount of cold water $\dot{m}_{s}$ is supplied
to the bottom of Tank 2 at the same time so that the total amount of water in
the HPTES system is always constant. If the HP is off, the cold water will be
directly injected into the bottom of Tank 2; otherwise, the water from the
bottom of Tank 2 with mass flow rate $\dot{m}_{p}$ will be heated by HP then
pumped into the top of Tank 1. The corresponding mass flow rates of the water
circulations are indicated in Fig. 1.

Figure 1: Diagram of the considered general HPTES system.

In the following, we will provide a general control-oritened model of the
above HPTES system, which will be used for our MPC design in Section III.

###  II-A Heat Pump Model

Heat pumps are used for providing thermal energy in the HPTES system. To model
the relationship between the electricity consumption and thermal energy
generation of HP, the concept of coefficient of performance (COP) is used. The
COP is defined as the ratio of heat output to work input, which can be
expressed as

$\text{COP}=\frac{Q_{\text{hp}}}{P_{\text{hp}}},$ (1)

where $Q_{\text{hp}}$ denotes the heat output of the heat pump and
$P_{\text{hp}}$ its power input.

It is assumed in our design that the HP only operates in two modes: on and
off. Hence, it follows from (1), that the thermal energy generated by HP can
be denoted as

$Q_{\text{hp}}=\text{COP}\cdot P_{r}\cdot u,$ (2)

where $P_{r}$ is the rated power of the heat pump, and $u\in\mathbb{B}$ is the
on/off binary control signal.

In order to balance approximation accuracy and computational burden of the
resulting MPC problem, the following bilinear COP model is adopted:

$\text{COP}=a_{1}+a_{2}\cdot T_{\text{in,hp}}+a_{3}\cdot
T_{\text{amb}}+a_{4}\cdot T_{\text{in,hp}}\cdot T_{\text{amb}},$ (3)

where $T_{\text{in,hp}}$ is the inlet water temperature of HP,
$T_{\text{amb}}$ is the ambient air temperature of HP, and
$(a_{1},a_{2},a_{3},a_{4})$ are parameters to be identified.

###  II-B Thermal Energy Storage Model

The thermal energy generated by HP is used to heat the water in the connected
water tanks. For modeling the water tanks, the stratified tank model is
adopted to balance modeling accuracy and computational burden [14]. In the
stratified water tank model, a single water tank is divided into several
connected layers, or called nodes. Each layer is assumed to function as an
individual node with uniform temperature distribution. The general thermal
behavior of each layer is depicted in Fig. 2, where the thermal exchange of
each node is composed by the following parts:

  * •

$\dot{Q}_{\text{wall},j}$: the heat loss from layer $j$ to the tank wall.

  * •

$\dot{Q}_{j+1,j}$ and $\dot{Q}_{j-1,j}$: thermal conduction between layer $j$
and its adjacent layers $j+1$ and $j-1$.

  * •

$\dot{Q}_{\text{conv}}$: heat exchange due to water flows $\dot{m}_{t}$ in/out
of $j$-th layer from/to adjacent layers.

Figure 2: Heat flow diagram of a single layer of TES.

Then, the thermal dynamics of each thermal node can be written as

$\displaystyle
m_{j}c_{p}\frac{dT_{j}}{dt}=-\dot{Q}_{\text{wall},j}+\dot{Q}_{j+1,j}+\dot{Q}_{j-1,j}+\dot{Q}_{\text{conv}},$
(4a)
$\displaystyle\dot{Q}_{\text{conv}}\\!=\\!\begin{cases}\dot{m}_{t}c_{p}(T_{j-1}-T_{j}),\
\dot{m}_{t}\text{ flows from $j\\!-\\!1$ to $j$ }\\\
\dot{m}_{t}c_{p}(T_{j+1}-T_{j}),\ \dot{m}_{t}\text{ flows from $j\\!+\\!1$ to
$j$}\end{cases}$ (4b)
$\displaystyle\dot{Q}_{j+1,j}=R_{j,j+1}\left(T_{j+1}-T_{j}\right),$ (4c)
$\displaystyle\dot{Q}_{j-1,j}=R_{j-1,j}\left(T_{j-1}-T_{j}\right),$ (4d)
$\displaystyle\dot{Q}_{\text{wall},j}=R_{w}\left(T_{j}-T_{\text{amb}}\right),$
(4e)

where $m_{j}$ is the mass of the $j$-th node, $c_{p}$ is the specific heat
capacity of water, $\dot{m}_{t}$ is the water mass flow rate between adjacent
tank layers, $R_{j,j+1}$ and $R_{w}$ are thermal resistances between the
$j$-th layer and the $(j+1)$-st layer and the tank wall, respectively.

Equation (4) describes the general thermal behaviour of a water layer. For
layers with hot water extraction and cold water supplement, their thermal
dynamics need extra modification. For the top layer of Tank 1, it does not
have an upper layer so the thermal conduction $\dot{Q}_{j-1,j}=0$, and the
heat convection $\dot{Q}_{\text{conv}}=\dot{m}_{t}c_{p}(T_{j-1}-T_{j})$ should
be computed with $T_{j-1}$ as the temperature of the inlet water injected into
Tank 1. The same analysis is also applicable to the bottom layer of Tank 2,
where no lower layer exists. In addition, in our system, since the water
circulation direction will change with the operation of HP, namely $u$, the
mass flow rate of convection, $\dot{m}_{t}$, is a function of HP control
signal $u$ and the mass flow rate of hot water consumption $\dot{m}_{s}$.

The thermal dynamics in (4) is able of capturing the thermal behaviour of a
general thermal storage system and can be easily adapted to other water tank
configurations with minor modification. Also, this model is sufficiently
simple to be incorporated into MPC design as a prediction model.

###  II-C System Constraints

For safe operation and demand requirements satisfaction, the HPTES system is
subject to several physical constraints. In this subsection, we describe the
system constraints that the proposed control scheme has to satisfy.

Firstly, to provide qualified hot water and ensuring safe operation, the water
temperature of the HPTES system has to be within an admissible range, which is
denoted as

$x^{l}\leq x\leq x^{u},$ (5)

where $x$ denotes the temperature vector of different water layers and
pipelines, $x^{l}$ and $x^{u}$ are the corresponding temperature lower bound
and upper bound, respectively.

Secondly, frequent on-off switches of HP is unfavourable since it can cause
excessive wear and tear and reduce the HP lifetime. Consequently, the proposed
MPC scheme should prevent frequently switching the HP. For this purpose, the
following constraint is added:

$\sum_{k=1}^{m}(u_{t-k+1}-u_{t-k})^{2}\leq N_{\text{ctrl}},$ (6)

where $N_{\text{ctrl}}$ is the maximal number of switches that is allowed
during $m$ time steps, and $u_{t-k}$ denotes the control input $k$ time steps
in the past compared to the current time instant $t$. Because
$u_{t}\in\mathbb{B}$, the LHS of (6) computes the number of switches during
the most recent $m$ time steps. For instance, setting $m=8$ and
$N_{\text{ctrl}}=1$ implies that, within an 8-step time window, only one
switch is allowed.

Remark 1: The HPTES configuration and the corresponding control-oriented
models and system constraints described in this section are general enough to
cover a wide range of possible HPTES systems. Also, the control-oriented
models can be flexibly adjusted while still keeping a similar model structure
even if other alternative configurations are adopted. For example, the
position of hot water extraction, which is at the top of Tank 1 in our case,
and the position of cold water supplement, which is at the bottom of Tank 2 in
our case, can be placed in other positions. Consequently, our MPC-based
control design scheme in Section III will also be applicable to these
alternative configurations with only minor modifications.

##  III Energy Flexible MPC Design for Demand-Side Management

In this section, an MPC strategy is designed for the HPTES system by following
the two-step DSM framework shown in Fig. 3. The DSM scheme consists of two
steps: flexibility assessment and flexibility exploitation.

As pointed out in [10, 11, 12], most of the DSM strategies follow either
price-based or incentive-based programs, which are both one-step approaches
and fail to fully exploit the energy flexibility of the system. With this two-
step DSM framework, at step 1, the flexibility potential of the HPTES system
is assessed by BMS and the flexibility information $\mathcal{F}$ is sent to
the grid operator. Then, at step 2, the grid operator generates a feasible DR
request $\mathcal{R}$ to the BMS to activate the energy flexibility. In
contrast to the existing price-based or incentive-based programs, this two-
step DSM approach guarantees that the expected DR requests from the power grid
will be achieved. This is achieved by quantitatively assessing the flexibility
potential of the system before exploitation, and generating feasible DR
requests. This property is beneficial in efficiently coordinating different DR
service providers and conducting DSM.

Figure 3: Diagram of the two-step DSM scheme.

###  III-A Flexibility Assessment

The first question to answer for the two-step DSM scheme is how to assess the
energy flexibility potential of the HPTES system that is performed in step 1.
It has been proposed that there are three basic factors in determining energy
flexibility: magnitude, time duration, and cost [15, 16]. Consequently, we
will quantitatively describe the energy flexibility of the HPTES system via
these factors.

Since we focus on solving the grid congestion problem, which is currently a
challenging issue in the Dutch electricity market, the exploitation of
flexibility refers to reducing the electricity consumption of HP. For our
considered HPTES system, the control input of HP only has two modes: on and
off. Consequently, the capacity of flexibility is proportional to the time
duration that HP can remain off. Accordingly, in our work, the goal of
flexibility assessment is to determine the optimal flexibility duration to
maximize the benefits of providing DR services, i.e., the period during which
HP is off without violating system constraints.

To conduct flexibility assessment, we introduce two sets of auxiliary decision
variables $\mathcal{S}_{\mathcal{T}}:=\\{s_{t},t\in\mathcal{T}\\}$ and
$\mathcal{Z}_{\mathcal{T}}:=\\{z_{t},t\in\mathcal{T}\\}$, where
$s_{t}\in\mathbb{B}$ and $z_{t}\in\mathbb{B}$ are binary variables, and
$\mathcal{T}:=\\{t_{f_{1}},\cdots,t_{f_{n}}\\}$ is the set of time indices
during which the flexibility is assessed, called flexibility assessment
period. Based on $s_{t}$ and $z_{t}$, we design the following logic:

  * •

$s_{t}=1$ and $z_{t}=0$: time instant $t$ is within the flexibility period,
and hence $u_{t}=0$.

  * •

$s_{t}=0$ and $z_{t}=0$: time instant $t$ is before the flexibility period,
and $u_{t}\in\mathbb{B}$.

  * •

$s_{t}=0$ and $z_{t}=1$: time instant $t$ is after flexibility period, and
$u_{t}\in\mathbb{B}$.

The above logic can be mathematically formulated as the following linear
constraints:

$\displaystyle u_{t}\leq 1-s_{t},$ (7a) $\displaystyle s_{t+1}\geq
s_{t}-z_{t+1},$ (7b) $\displaystyle s_{t}+z_{t}\leq 1,$ (7c) $\displaystyle
z_{t+1}\geq z_{t}.$ (7d)

In Fig. 4, a schematic illustration of the above logics is provided, where the
flexibility assessment period is defined by $\mathcal{T}$, and the flexibility
period is defined by $\mathcal{F}$, whose formal definition is given below.

$\mathcal{F}:=\\{t|s_{t}=1,t\in\mathcal{T}\\}\subseteq\mathcal{T}.$ (8)

The flexibility period $\mathcal{F}$ gives the optimal flexibility capacity,
i.e., the time period within $\mathcal{T}$ that the HP can be off without
violating system constraints, that the BMS will promise to the grid operator.

Figure 4: Schematic of the logic in (7) indicating flexibility periods.

Finally, flexibility assessment can be mathematically formulated as the
following optimization problem

$\displaystyle\min_{u_{t},s_{k},z_{k}}\ $ $\displaystyle J_{o}-J_{f}$ (9a)
s.t. $\displaystyle x_{t+1}=f(x_{t},u_{t},d_{t}),$ (9b) $\displaystyle
x_{t}\text{ satisfy }\eqref{eq:temp_cons},\ u_{t}\text{ satisfy
}\eqref{eq:switch},$ (9c) $\displaystyle\forall t=0,1,2,\cdots,N-1,$ (9d)
$\displaystyle(u_{k},s_{k},z_{k})\text{ satisfy }\eqref{eq:flexi_cons},\forall
k\in\mathcal{T}$ (9e)

where $N$ is the length of prediction horizon,
$J_{o}=\sum_{t=1}^{N}l_{t}(x_{t},u_{t-1})$ is the total operational cost of
the HPTES system within the prediction horizon with $l_{t}(x_{t},u_{t-1})$ as
the $t$-th stage cost, $J_{f}=\lambda\sum_{t\in\mathcal{T}}s_{t}$ is the
revenue of flexibility that is proportional to the length of flexibility
period, $\lambda\in\mathbb{R}_{+}$ is a scaling factor, $f(x_{t},u_{t},d_{t})$
is the control-oriented model of the HPTES system introduced in (2) and (4)
with system states $x_{t}$ as the temperature vector of different water layers
and pipelines, $d_{t}$ as the mass flow rate of hot water consumption
$\dot{m}_{s}$ at time instant $t$, and $u_{t}$ the binary control input of HP.
For the sake of brevity, the detailed expressions of $f(x_{t},u_{t},d_{t})$
are given in Section VI.

Remark 2: The optimization problem (9) aims at optimally balancing the
operational cost and the benefit of promising a certain capacity for
flexibility as DSM to the power grid. If the operational cost term $J_{o}$ in
the objective function is omitted, solving (9) will allow us to calculate the
maximal capacity of energy flexibility. Namely, the longest consecutive time
period during which the HP can remain off without violating system
constraints. It should be noted that, compared with a typical economic MPC
problem formulation, the proposed flexibility assessment problem only entails
introducing extra linear constraints (7), and is independent of the structure
of the system dynamics (9b). These properties are beneficial to the
scalability and applicability of the proposed scheme.

###  III-B Flexibility Exploitation

After solving the optimization problem (9), BMS will send the promised
flexibility capacity $\mathcal{F}$ to the power grid. Based on this
information, the grid operator will subsequently generate a feasible DR
request $\mathcal{R}=\\{t|t\in\mathcal{F}\\}\subseteq\mathcal{F}$ to specify
the exact time instants that the HP is required to be off. Namely,

$u_{t}=0,\forall t\in\mathcal{R}.$ (10)

For achieving this DR request, in BMS a general MPC problem can be formulated
by imposing the constraints (10). An example for such a formulation will be
shown in (14) of Section IV. Since the DR request $\mathcal{R}$ is feasible
w.r.t. the flexibility capacity $\mathcal{F}$, i.e.,
$\mathcal{R}\subseteq\mathcal{F}$, it can be guaranteed that the DR request in
(10) can be achieved without violating system constraints owing to the fact
that $u_{t}=0$ $(\forall t\in\mathcal{F})$ is always a feasible solution.

##  IV Simulation Results

In order to demonstrate the effectiveness of the proposed scheme, a numerical
simulation is performed for an HPTES system, which is based on a real
installation for providing domestic hot water in an office building in the
Netherlands, see Fig. 5. This system is composed of one air-to-water HP and
two 500L water tanks. The hot water is used for dish washing in dining hall
and showering in fitness rooms in the building. The detailed model and
corresponding parameters of this HPTES system are provided in Section VI.

(a) Air-to-water HP.

(b) Two 500L water tanks.

Figure 5: Motivating example of an HPTES system for our numerical case-study.

In our case study, the HP is operated during working hours 7:00 am - 5:30 pm.
To implement the proposed strategy, hot water consumption $d_{t}$ and its
predicted value $\hat{d}_{t}$ are needed. Fig. 6 gives the real hot water
consumption profile, which is used for simulating the dynamics of the HPTES
system, and the predicted value, which is used for MPC design. The non-
negligible prediction errors visible in the figure allow for testing the
robustness of our proposed scheme.

To provide qualified hot water, the temperature of the water supplied to
buildings, in our case the water temperature at the top of Tank 1 that is
denoted as $T_{1}$, has to satisfy

$55\leq T_{1}\leq 75.$ (11)

In addition, to mitigate the risk of legionella bacteria, which proliferate
between $20^{\circ}$C - $50^{\circ}$C, and to provide hot water with
sufficient temperature, it is recommended to maintain $T_{1}$ above
$60^{\circ}$C most of the time:

$T_{1}\geq 60,\text{ for most of the time}.$ (12)

Since both constraints (11) and (12) are hard constraints, to ensure the
feasibility of the proposed MPC design, they are relaxed as soft constraints:

$\displaystyle 55-\delta_{1}\leq T_{1}\leq 75+\delta_{1},$ (13a)
$\displaystyle T_{1}\geq 60-\delta_{2},$ (13b)

where $\delta_{1}>0$ and $\delta_{2}>0$ are slack variables that will be
penalized in the MPC objection function, see (14).

During the whole simulation period, the flexibility task is performed every 3
hours (3 times in total). For flexibility assessment in (9), the prediction
horizon is selected as 4 hours, and the first 3 hours are chosen as
flexibility assessment period. The boundaries of flexibility assessment
periods are indicated with red dash lines in Fig. 8. The objective function of
the flexibility assessment (9) is chosen as $-\sum_{t\in\mathcal{T}}s_{t}$,
which implies computing the longest period during which HP can remain off
without violating system constraints.

After finishing the flexibility assessment task, the corresponding DR request
is set as $\mathcal{R}=\mathcal{F}$. Namely, the power grid tries to utilize
all available energy flexibility to reduce electricity consumption during the
flexibility period. For achieving the DR request, the following economic MPC
formulation is adopted:

$\displaystyle\min_{u_{t},\delta}\ $
$\displaystyle\sum_{t=0}^{N}e_{t}u_{t}+M_{1}\delta_{1}+M_{2}\delta_{2}$ (14a)
s.t. $\displaystyle x_{t+1}=f(x_{t},u_{t},\hat{d}_{t}),$ (14b) $\displaystyle
x_{t}\text{ satisfy }\eqref{eq:soft_cons},\ u_{t}\text{ satisfy
}\eqref{eq:switch},$ (14c) $\displaystyle\forall t=0,1,2,\cdots,N-1$ (14d)
$\displaystyle u_{k}=0,\forall k\in\mathcal{R},$ (14e)

where $e_{t}$ represents the electricity price at time instant $t$,
$\delta_{1}$ and $\delta_{2}$ are the slack variables for relaxing the input
and state constraints (13) if needed, $M_{1}$ and $M_{2}$ are corresponding
penalties. A typical electricity price in the Netherlands during the
simulation period is shown in Fig. 7, which is used in our simulation.

Figure 6: Hot water consumption and its prediction. Figure 7: Electricity
price used in simulation.

Simulation results are given in Fig. 8 \- 9. Fig. 8 depicts the HP input
signals during the simulation period. It can be seen that during all
flexibility periods, which are green shaded regions, the HP is kept off to
reduce its energy consumption for providing DR services. Fig. 9 shows the
water temperature at the top of Tank 1. It is clear that during the whole
simulation period, our proposed approach is able to maintain the temperature
within permissable range, which is crucial for providing qualified hot water
for buildings. Table I compares the operational performance of the proposed
MPC approach with that of the existing rule-based approach implemented for the
HPTES installation. With the rule-based approach, the HP is operated only
based on the temperature of the water tanks: if water temperature at the
bottom of Tank 2 is higher than 62∘C, HP is off; if temperature at the top of
Tank 1 is lower than $62^{\circ}$C, HP is on. Clearly, the proposed MPC
approach gives better operational performance than the existing rule-based
approach even under the presence of flexibility exploitation, which usually
degrades the economical performance of MPC. In summary, the proposed MPC
approach is not only able to provide DR services by exploiting the energy
flexibility of the HPTES system, but is also capable of operating the HPTES
system safely and efficiently to provide qualified domestic hot water usage.

| Rule-Based Approach | MPC
---|---|---
Average Water Temperature (∘C) | 65.53 | 64.85
Maximal Constraint violation (∘C) | 4.43 | 4.12
Energy Consumption(kWh) | 64.17 (100%) | 62.50 (97.40%)
Energy Cost (Euro) | 8.69 (100%) | 8.41 (96.78%)

TABLE I: Operational performance of the MPC and the rule-based scheme. Figure
8: Control input signals of heat pump. Figure 9: Water temperature at the top
of Tank 1.

##  V Conclusions

This paper proposed an energy flexible MPC scheme for assessing and exploiting
the energy flexibility of HPTES systems to provide demand response services.
With the proposed approach, the energy flexibility potential of the HPTES
system is quantitatively analyzed by solving a typical mixed-integer economic
MPC problem with extra linear constraints. Then the flexibility is activated
via feasible DR requests to achieve the reduction of energy consumption
without violating system constraints. The proposed scheme provides a
systematical approach to take advantage of the flexibility potential of HPTES
systems to achieve demand-side management. The efficacy of our design is
demonstrated via the simulation results based on a real-world HPTES
installation. Future work includes implementing pilot experiments of the
proposed scheme on the real-world HPTES installation.

## References

  * [1] D. Government, “Klimaatnota 2022,” 2022. [Online]. Available: https://www.rijksoverheid.nl/documenten/publicaties/2022/11/01/klimaatnota-2022
  * [2] F. Bünning, J. Warrington, P. Heer, R. S. Smith, and J. Lygeros, “Robust MPC with data-driven demand forecasting for frequency regulation with heat pumps,” _Control Engineering Practice_ , vol. 122, p. 105101, 2022.
  * [3] European Commission, Directorate General for Energy, “Clean energy for all europeans package,” 2019. [Online]. Available: https://energy.ec.europa.eu/topics/energy-strategy/clean-energy-all-europeans-package_en
  * [4] E. Commission, “Heat pumps are key to enabling the clean energy transition and achieving the EU’s carbon neutrality goal by 2050,” 2022. [Online]. Available: https://energy.ec.europa.eu/topics/energy-efficiency/heat-pumps_en
  * [5] C. Ermel, M. V. Bianchi, A. P. Cardoso, and P. S. Schneider, “Thermal storage integrated into air-source heat pumps to leverage building electrification: A systematic literature review,” _Applied Thermal Engineering_ , p. 118975, 2022.
  * [6] B. Alimohammadisagvand, J. Jokisalo, S. Kilpeläinen, M. Ali, and K. Sirén, “Cost-optimal thermal energy storage system for a residential building with heat pump heating and demand response control,” _Applied Energy_ , vol. 174, pp. 275–287, 2016.
  * [7] R. Tang and S. Wang, “Model predictive control for thermal energy storage and thermal comfort optimization of building demand response in smart grids,” _Applied Energy_ , vol. 242, pp. 873–882, 2019.
  * [8] K. J. Kircher and K. M. Zhang, “Model predictive control of thermal storage for demand response,” in _2015 American Control Conference (ACC)_. IEEE, 2015, pp. 956–961.
  * [9] R. Renaldi, A. Kiprakis, and D. Friedrich, “An optimisation framework for thermal energy storage integration in a residential heat pump heating system,” _Applied energy_ , vol. 186, pp. 520–529, 2017.
  * [10] F. D’Ettorre, M. De Rosa, P. Conti, D. Testi, and D. Finn, “Mapping the energy flexibility potential of single buildings equipped with optimally-controlled heat pump, gas boilers and thermal storage,” _Sustainable Cities and Society_ , vol. 50, p. 101689, 2019.
  * [11] H. Golmohamadi, K. G. Larsen, P. G. Jensen, and I. R. Hasrat, “Integration of flexibility potentials of district heating systems into electricity markets: A review,” _Renewable and Sustainable Energy Reviews_ , vol. 159, p. 112200, 2022.
  * [12] Y. Li, N. Yorke-Smith, and T. Keviczky, “Unlocking energy flexibility from thermal inertia of buildings: A robust optimization approach,” in _2023 62nd IEEE Conference on Decision and Control (CDC)_. IEEE, 2023, pp. 2555–2562.
  * [13] M. Konsman, E. Werkman, and in collaboration with TC 205 WG 18 members, “S2 white paper,” 2023. [Online]. Available: https://s2standard.org/
  * [14] S. Rastegarpour, M. Ghaemi, and L. Ferrarini, “A predictive control strategy for energy management in buildings with radiant floors and thermal storage,” in _2018 SICE International Symposium on Control Systems (SICE ISCS)_. IEEE, 2018, pp. 67–73.
  * [15] R. G. Junker, A. G. Azar, R. A. Lopes, K. B. Lindberg, G. Reynders, R. Relan, and H. Madsen, “Characterizing the energy flexibility of buildings and districts,” _Applied Energy_ , vol. 225, pp. 175–182, 2018.
  * [16] S. Ø. Jensen, A. Marszal-Pomianowska, R. Lollini, W. Pasut, A. Knotzer, P. Engelmann, A. Stafford, and G. Reynders, “Iea ebc annex 67 energy flexible buildings,” _Energy and Buildings_ , vol. 155, pp. 25–34, 2017.

##  VI Appendix

In the following, the detailed model and parameters of the HPTES used in our
simulation are provided. For the stratified tank model, Tank 1 and Tank 2 are
modeled with 2 and 4 layers, respectively. The thermal dynamics is given in
(15), the definition of the state variables is given in Table II, and the
value of the parameters in (15) is in Table III.

$\displaystyle x^{1}_{k+1}=$ $\displaystyle
u_{k}\left(x^{2}_{k+1}+\frac{Q_{\text{hp}}}{m_{\dot{p}}c_{p}}\right)+(1-u_{k})\bigg{(}x^{1}_{k}$
$\displaystyle-\frac{\Delta
t}{m_{\text{pipe}}c_{p}}\left(R_{\text{pipe}}(x^{1}_{k}-T^{\text{amb}}_{k})\right.$
$\displaystyle\left.+R_{\text{pipe,upper}}(x^{1}_{k}-x^{3}_{k})+R_{\text{pipe,bottom}}(x^{1}_{k}-x^{8}_{k})\right)\bigg{)},$
(15a) $\displaystyle x^{2}_{k+1}=$ $\displaystyle
T_{\text{s}}\frac{\dot{m}_{s}}{\dot{m}_{p}}+x^{8}_{k}\left(1-\frac{\dot{m}_{s}}{\dot{m}_{p}}\right),$
(15b) $\displaystyle x^{3}_{k+1}=$ $\displaystyle x^{3}_{k}+\frac{\Delta
t}{m_{1}c_{p}}\bigg{(}\dot{m}_{p}c_{p}\left(x^{1}_{k}-x^{3}_{k}\right)u_{k}$
$\displaystyle-(\dot{m}_{c}-\dot{m}_{s})c_{p}\triangle T_{c}$ $\displaystyle-
R_{12}(x^{3}_{k}-x^{4}_{k})+\dot{m}_{s}c_{p}(x^{4}_{k}-x^{3}_{k})(1-u_{k})\bigg{)}$
$\displaystyle+\Delta T_{\text{off}}\cdot(u_{k}-u_{k-1})\cdot u_{k-1},$ (15c)
$\displaystyle x^{4}_{k+1}=$ $\displaystyle x^{4}_{k}+\frac{\Delta
t}{m_{2}c_{p}}\bigg{(}\left(\dot{m}_{p}-\dot{m}_{s}\right)c_{p}\left(x^{3}_{k}-x^{4}_{k}\right)u_{k}$
$\displaystyle+R_{12}(x^{3}_{k}-x^{4}_{k})-R_{23}(x^{4}_{k}-x^{5}_{k})$
$\displaystyle+\dot{m}_{s}c_{p}(x^{5}_{k}-x^{4}_{k})(1-u_{k})\bigg{)},$ (15d)
$\displaystyle x^{5}_{k+1}=$ $\displaystyle x^{7}_{k}+\frac{\Delta
t}{m_{3}c_{p}}\bigg{(}\left(\dot{m}_{p}-\dot{m}_{s}\right)c_{p}\left(x^{4}_{k}-x^{5}_{k}\right)u_{k}$
$\displaystyle+R_{23}(x^{4}_{k}-x^{5}_{k})-R_{34}(x^{5}_{k}-x^{6}_{k})$
$\displaystyle+\dot{m}_{s}c_{p}(x^{6}_{k}-x^{5}_{k})(1-u_{k})\bigg{)},$ (15e)
$\displaystyle x^{6}_{k+1}=$ $\displaystyle x^{8}_{k}+\frac{\Delta
t}{m_{4}c_{p}}\bigg{(}\left(\dot{m}_{p}-\dot{m}_{s}\right)c_{p}\left(x^{5}_{k}-x^{6}_{k}\right)u_{k}$
$\displaystyle+R_{34}(x^{5}_{k}-x^{6}_{k})-R_{45}(x^{6}_{k}-x^{7}_{k})$
$\displaystyle+\dot{m}_{s}c_{p}(x^{7}_{k}-x^{6}_{k})(1-u_{k})\bigg{)},$ (15f)
$\displaystyle x^{7}_{k+1}=$ $\displaystyle x^{7}_{k}+\frac{\Delta
t}{m_{5}c_{p}}\bigg{(}\left(\dot{m}_{p}-\dot{m}_{s}\right)c_{p}\left(x^{6}_{k}-x^{7}_{k}\right)u_{k}$
$\displaystyle+R_{45}(x^{6}_{k}-x^{7}_{k})-R_{56}(x^{7}_{k}-x^{8}_{k})$
$\displaystyle+\dot{m}_{s}c_{p}(x^{8}_{k}-x^{7}_{k})(1-u_{k})\bigg{)},$ (15g)
$\displaystyle x^{8}_{k+1}=$ $\displaystyle x^{8}_{k}+\frac{\Delta
t}{m_{6}c_{p}}\bigg{(}\left(\dot{m}_{p}-\dot{m}_{s}\right)c_{p}\left(x^{7}_{k}-x^{8}_{k}\right)u_{k}$
$\displaystyle+R_{56}(x^{7}_{k}-x^{8}_{k})+\dot{m}_{s}c_{p}(T_{s}-x^{8}_{k})(1-u_{k})\bigg{)},$
(15h) $\displaystyle Q_{hp}=$ $\displaystyle\text{COP}\cdot P_{r}\cdot u,$
(15i) $\displaystyle\text{COP}=$ $\displaystyle
a_{1}+a_{2}T_{\text{in,hp}}+a_{3}T_{\text{amb}}+a_{4}T_{\text{in,hp}}T_{\text{amb}},$
(15j) $\displaystyle T_{\text{in,hp}}=$ $\displaystyle\Delta
T_{\text{he}}+T_{\text{out,tank}}.$ (15k)

In (15), the thermal loss $\dot{Q}_{\text{wall},j}$ in (4) is omitted since
the HPTES system is well-insulated such that the thermal loss is negligible.
Equality (15k) is derived via

$T_{\text{out,hp}}-T_{\text{in,hp}}=T_{\text{in,tank}}-T_{\text{out,tank}}$
(16)

with $\Delta T_{\text{he}}:=T_{\text{out,hp}}-T_{\text{in,tank}}$ as a
relatively stable temperature difference, which is true when the heat
exchanger is operated with high efficiency.

In addition, the term $\Delta T_{\text{off}}\cdot(u_{k}-u_{k-1})\cdot u_{k-1}$
in (15c) is used to reflect a special phenomenon of the temperature drop
$\Delta T_{\text{off}}$ for water in the top of Tank 1 when HP is switched
from on to off, which is caused by the HP and the circulation pump of water
tanks being out of sync in our HPTES system.

State | Description | Units
---|---|---
$x^{1}$ |  | The inlet water temperature of
---
the water tanks, $T_{\text{in,tank}}$
∘C
$x^{2}$ |  | The outlet water temperature of
---
the water tanks $T_{\text{out,tank}}$
∘C
$x^{3}$ |  | The temperature of the 1st layer of
---
the water tanks $T_{1}$
∘C
$x^{4}$ |  | The temperature of the 2nd layer of
---
the water tanks $T_{2}$
∘C
$x^{5}$ |  | The temperature of the 3rd layer of
---
the water tanks $T_{3}$
∘C
$x^{6}$ |  | The temperature of the 4th layer of
---
the water tanks $T_{4}$
∘C
$x^{7}$ |  | The temperature of the 5th layer of
---
the water tanks $T_{5}$
∘C
$x^{8}$ |  | The temperature of the 6th layer of
---
the water tanks $T_{6}$
∘C
TABLE II: Description of notations in (15).

Term | Description | Value | Units
---|---|---|---
$\Delta t$ | sampling time | 1/3 | h
$c_{p}$ |  | Specific heat capacity of water
---
4186 | $\mathrm{J/kg\cdot K}$
$R_{\text{pipe}}$ |  | Thermal resistance for outlet pipe
---
of the heat exchanger
0.30 | $\mathrm{W/K}$
$R_{\text{pipe,upper}}$ |  | Thermal resistance between
---
outlet pipes of the heat exchanger
and the upper layer of Tank 1
0 | $\mathrm{W/K}$
$R_{\text{pipe,bottom}}$ |  | Thermal resistance between
---
outlet pipes of the heat exchanger
and the bottom layer of Tank 2
2 | $\mathrm{W/K}$
$R_{12}$ |  | Thermal resistance between the 1st
---
and 2nd layers of the water tanks
0.24 | $\mathrm{W/K}$
$R_{23}$ |  | Thermal resistance between the 2nd
---
and 3rd layers of the water tanks
0.24 | $\mathrm{W/K}$
$R_{34}$ |  | Thermal resistance between the 3rd
---
and 4th layers of the water tanks
0.49 | $\mathrm{W/K}$
$R_{45}$ |  | Thermal resistance between the 4th
---
and 5th layers of the water tanks
0.54 | $\mathrm{W/K}$
$R_{56}$ |  | Thermal resistance between the 5th
---
and 6th layers of the water tanks
0.53 | $\mathrm{W/K}$
$m_{\text{pipe}}$ |  | Mass of the outlet pipe of
---
the heat exchanger
3.27 | kg
$m_{1}$ | Mass of the 1st layers of the water tanks | 250 | kg
$m_{2}$ | Mass of the 2nd layers of the water tanks | 250 | kg
$m_{3}$ | Mass of the 3rd layers of the water tanks | 169.66 | kg
$m_{4}$ | Mass of the 4th layers of the water tanks | 95.38 | kg
$m_{5}$ | Mass of the 5th layers of the water tanks | 136.67 | kg
$m_{6}$ | Mass of the 6th layers of the water tanks | 98.29 | kg
$\Delta T_{\text{he}}$ | Temperature difference of the heat exchanger | 2.84 |  ∘C
$\Delta T_{c}$ | Temperature difference in the demand pipe | 1.76 |  ∘C
$T_{s}$ | Temperature of the water in supply pipe | 13 |  ∘C
$\Delta T_{\text{off}}$ |  | Temperature drop of
---
the heat pump’s deactivation
2.5 |  ∘C
$T_{\text{amb}}$ | Ambient Temperature | 18.5 |  ∘C
$\dot{m}_{s}$ | Flow rate in the supplement pipe | - | kg/h
$\dot{m}_{c}$ | Flow rate in the demand circulation pipe | 1100 | $\mathrm{kg/h}$
$\dot{m}_{p}$ | Flow rate in the main circulation pipe | 880 | $\mathrm{kg/h}$
$a_{1}$ | Parameter in COP | 3.3297 | -
$a_{2}$ | Parameter in COP | -0.0423 | -
$a_{3}$ | Parameter in COP | 0.0219 | -
$a_{4}$ | Parameter in COP | 0.0003 | -

TABLE III: Nominal values of the parameters in (15).


footnote

# Learning Hierarchical Discourse-level Structure for Fake News Detection

Hamid Karimi
Computer Science and Engineering
Michigan State University
<EMAIL_ADDRESS>
&Jiliang Tang
Computer Science and Engineering
Michigan State University
<EMAIL_ADDRESS>
###### Abstract

On the one hand, nowadays, fake news articles are easily propagated through
various online media platforms and have become a grand threat to the
trustworthiness of information. On the other hand, our understanding of the
language of fake news is still minimal. Incorporating hierarchical discourse-
level structure of fake and real news articles is one crucial step toward a
better understanding of how these articles are structured. Nevertheless, this
has rarely been investigated in the fake news detection domain and faces
tremendous challenges. First, existing methods for capturing discourse-level
structure rely on annotated corpora which are not available for fake news
datasets. Second, how to extract out useful information from such discovered
structures is another challenge. To address these challenges, we propose
Hierarchical Discourse-level Structure for Fake news detection. HDSF learns
and constructs a discourse-level structure for fake/real news articles in an
automated and data-driven manner. Moreover, we identify insightful structure-
related properties, which can explain the discovered structures and boost our
understating of fake news. Conducted experiments show the effectiveness of the
proposed approach. Further structural analysis suggests that real and fake
news present substantial differences in the hierarchical discourse-level
structures.

##  1 Introduction

In this work, we focus on detecting fake news articles (hereafter referred to
as _documents_) based on their contents. Many existing linguistic approaches
for fake news detection Feng et al. (2012); Pennebaker et al. (2015); Ott et
al. (2011) overlook a crucial linguistic aspect of fake/real news documents
i.e., the hierarchical discourse-level structure. Usually, in a document,
discourse units (e.g., sentences) are organized in a hierarchical structure
e.g., a tree. The importance of considering the hierarchical discourse-level
structure for fake news detection is three-fold. First, previous studies
Bachenko et al. (2008); Rubin and Lukoianova (2015) explored discourse-level
structure in fake news detection and discovered that the way two discourse
units of a document are connected could be quite revealing and insightful
about its truthfulness. For instance, Rubin and Lukoianova (2015) applied
Rhetorical Structure Theory (RST) Mann and Thompson (1988) and noted that fake
stories lack “evidence” as a defined inter-discourse relation. Second, fake
news is typically produced by connecting disjoint pieces of news and unlike
well-established journalism (e.g., New York Times) fake news production lacks
a meticulous editorial board. Therefore, by incorporating the hierarchical
discourse-level structure, we can investigate the coherence of fake/real news
documents (we will show this later). Third, a substantial number of studies
have shown that using hierarchical structures yields a better document
representation in various downstream tasks whose predictions depend on the
entire text Bhatia et al. (2015); Morey et al. (2018); Li et al. (2014b).
Since typically fake news detection is considered as a classification problem
based on the entire text, applying discourse analysis has the potential to
advance fake news detection (this will be verified later).

On the other hand, incorporating the hierarchical structure at the discourse
level for fake news detection faces tremendous challenges. First, many
existing methods incorporating structural discourse Li et al. (2014a); Bhatia
et al. (2015) (not for fake news detection though) rely on annotated corpora
such as Penn Discourse Treebank Prasad et al. (2007). Constructing and
annotating such corpora is an arduous and costly process. Incorporating
hierarchical structure is even more difficult for fake news detection as there
exists virtually no available annotated discourse corpus in this domain.
Therefore, we need to learn the discourse-level structure in a data-driven and
automated manner. Second, how to use the hierarchical discourse-level
structure and extract insightful information that can boost our understanding
of fake news is another challenge.

In this study, we embrace the opportunities and challenges and propose
Hierarchical Discourse-level Structure for Fake news detection (HDSF)
framework. HDSF in an automated manner learns a hierarchical structure for a
given document through an approach based on the dependency parsing at the
sentence level (i.e., sentences are discourse units). As an example, Figure 1
illustrates a hierarchical structure of a document i.e., a dependency tree of
sentences. Sentences represent discourse units and two sentences are connected
by a directed link where a sentence at the _head_ of the link semantically
depends on a sentence at the _tail_ of the link e.g., in Figure 1, the
sentence $s_{4}$ depends on the sentence $s_{2}$.

Our key contributions are summarized as follow.

  * •

To the best of our knowledge, we are the first to study automatic document
structure learning for fake news detection.

  * •

We propose the framework HDSF that automatically and in an end-to-end manner
learns structurally rich representations for fake and real news documents.

  * •

We identify a set of structure-related properties delineating meaningful
structural differences between fake and real news documents.

Figure 1: An illustration of the hierarchical discourse-level structure of a
document using a dependency tree

The rest of the paper is organized as follows. In Section 2, we formally
define the problem. Section 3 describes the proposed framework. In Section 4,
we introduce several structure-related properties to analyze the hierarchical
structures. Section 5 presents the experiments and discussions followed by an
overview of the related work in Section 6. We conclude the paper in Section 7
and shed light on a few future directions.

##  2 Notations and Problem Statement

Following the previous work Allcott and Gentzkow (2017); Shu et al. (2017), we
define the fake news as follows.

Definition. We define a news document fake if its content is verified to be
false and real otherwise.

Let’s briefly introduce some notations. Suppose we have a corpus $\mathcal{D}$
of fake and real news documents. Let a document $d\in\mathcal{D}$ contain $k$
sentences $s_{1},s_{2},\cdots s_{k}$. Suppose a sentence $s_{j}\in d$ ($1\leq
j\leq k$) includes words $W_{j}=\\{w_{1},w_{2},\cdots,w_{T_{j}}\\}$ where
$T_{j}$ denotes the number of words in sentence $s_{j}$. Additionally, binary
labels ${Y}$ (i.e., _fake_ or _real_ labels) hold ground-truth labels
associated with documents in $\mathcal{D}$.

Given the corpus of fake/real news documents (i.e., $\mathcal{D}$), we aim to
learn model $\mathcal{M}$ that can automatically learn hierarchical and
structurally rich representations for documents in $\mathcal{D}$. Meanwhile,
given binary labels ${Y}$, the model $\mathcal{M}$ uses the hierarchical
representations to automatically predict the labels of unseen news documents.

##  3 The Proposed Framework

Figure 2: The proposed framework Hierarchical Discourse-level Structure for
Fake news detection (HDSF)

To incorporate the discourse-level structure for fake news detection, we
propose the framework HDSF illustrated in Figure 2. It provides three
components: the _Hierarchical Discourse-level Structure Learning_
automatically learns a proper structure for a given document, the _Structural
Document-level Representation_ yields a numerical and unified representation
for the entire document, which is used by the _Fake News Classification_
component to predict the label of a document.

###  3.1 Hierarchical Discourse-level Structure Learning

In this component, we aim to construct a hierarchical structure between
discourse units (i.e., sentences) without relying on an annotated corpus. To
achieve this, we use a dependency parsing approach Liu and Lapata (2018); Li
et al. (2014a); Kim et al. (2017) and represent the hierarchical structure of
a document as a dependency tree (see Figure 1 for an example of a dependency
tree). In dependency parsing of discourse units, we mainly need to identify if
a discourse unit semantically depends on another one. If so, a _parent-child_
(or _tail-head_) link in the dependency tree can be established. Therefore, as
long as the semantic dependencies between discourse units are identified, we
can construct a discourse-level dependency tree without an annotated corpus.
In Section 3.1.1, we describe a method to discover the semantic dependencies
between discourse units in an automated manner. Afterward, in Section 3.1.2,
we utilize these dependencies to construct the dependency tree of a document.

####  3.1.1 Learning Inter-Discourse Dependencies

Since discourse units are defined as sentences, we first need to get a fixed
representation for each sentence. To this end, we utilize Bi-directional Long
Short-Term Memory (BLSTM) network Schuster and Paliwal (1997). We represent
each word in a sentence $s_{j}$ by a fixed-size word embedding, and further
the BLSTM network at each time step $t\in[1,T_{j}]$ executes the following
functions111Note that the backward LSTM (i.e., the lower part of Eq. 1) takes
a sequence of words in a reverse order.:

$\displaystyle\overrightarrow{h}_{t}$
$\displaystyle=\mathcal{F}(\overrightarrow{h}_{t-1};w_{t-1})$ (1)
$\displaystyle\overleftarrow{h}_{t}$
$\displaystyle=\mathcal{F}(\overleftarrow{h}_{t-1};w_{T_{j}-t+1})$

where $\mathcal{F}$ is the LSTM function Hochreiter and Schmidhuber (1997),
and $\overrightarrow{h}_{t}$ and $\overleftarrow{h}_{t}$ are outputs of the
forward and backward LSTM networks at time step $t$, respectively. Then, a
fixed representation for a sentence $s_{j}$, denoted as $f_{j}$, is defined as
the average of the last output of forward and backward LSTM networks:

$\displaystyle
f_{j}=\frac{[\overrightarrow{h}_{T_{j}}+\overleftarrow{h}_{T_{j}}]}{2}$ (2)

Similarly, we apply the BLSTM network to all sentences of a document and
obtain a sequence of sentential representations i.e.,
$f_{1},f_{2},\cdots,f_{k}$ (see Figure 2).

As mentioned before, in dependency parsing, we need to identify the dependency
between two discourse units in an automated manner. To do this, the HDSF
framework learns and optimizes an inter-sentential attention matrix
$\mathbf{A}\in\mathbb{R}^{k\times k}$. The entry $(m,n)$ of $\mathbf{A}$ holds
the probability of the sentence $s_{m}$ being the parent of the sentence
$s_{n}$ where $1\leq m,n\leq k$ and $m\neq n$. In other words, $\mathbf{A}$
contains parent-child probabilities and is computed as follows.

$\displaystyle u_{m}$ $\displaystyle=\mathcal{G}(\mathbf{W}\times
f_{m}+\mathbf{b})$ (3) $\displaystyle u_{n}$
$\displaystyle=\mathcal{G}(\mathbf{W}\times f_{n}+\mathbf{b})$
$\displaystyle\mathbf{A}[m,n]$ $\displaystyle=\frac{e^{(u_{m}\odot
u_{n})}}{\sum_{i=1}^{k}e^{\sum(u_{i}\odot u_{n})}}$

where $\mathcal{G}$ is a non-linear activation function, $\mathbf{W}$ is some
weight matrix, $\mathbf{b}$ is a bias vector, and $\odot$ denotes the dot
product operator. Further, since we need a root node in a dependency tree, we
compute the probability of a sentence $s_{j}$ being the root node, denoted as
$r_{j}$, as follows.

$\displaystyle u_{j}$ $\displaystyle=\mathcal{G}(\mathbf{W}\times
f_{j}+\mathbf{b})$ (4) $\displaystyle r_{j}$
$\displaystyle=\frac{e^{\sum_{\forall
y}u_{j}[y]}}{\sum_{i=1}^{k}e^{\sum_{\forall y}u_{i}[y]}}$

where $u_{j}[y]$ is the $y$-th element of vector $u_{j}$. Similarly, we
calculate the root probabilities for all sentences and obtain the array of
root probabilities denoted as $\mathbf{r}=\\{r_{1},r_{2},\cdots,r_{k}\\}$
where $0\leq r_{j}\in\mathbf{r}\leq 1$.

####  3.1.2 Discourse Dependency Tree Construction

We use the learned matrix of inter-sentential parent-child probabilities i.e.,
$\mathbf{A}$ (Eq. 3) as well as the array of root probabilities i.e.,
$\mathbf{r}$ (Eq. 4) and propose a greedy algorithm, illustrated in Algorithm
1, to construct the discourse dependency tree of a document. A sentence with
the maximum value in $\mathbf{r}$ is considered the root node and is inserted
into the tree (line 1). Then, at each iteration, the algorithm finds the
maximum entry in a block of the matrix $\mathbf{A}$ whose rows correspond to
the rows of current nodes added to the tree (i.e., nodes $V$ in line 1) and
its columns correspond to columns of the rest of nodes (i.e., nodes
$N\backslash V$ in line 1). Note that the columns of the current nodes are
excluded because their parents have already been identified and also each node
should have exactly one parent (except the root which has no parent). Assume
the search in line 1 results in the entry $(p,c)$ of $\mathbf{A}$ where $1\leq
p,c\leq k$ and $p\neq c$. Then, the sentence $s_{c}$ is added as the child
node of the sentence $s_{p}$ (line 1). Algorithm 1 continues until all
sentences of a document are added to the tree $\mathcal{T}$.

Input: $\mathbf{A}$; $\mathbf{r}$

Output: Discourse dependency tree $\mathcal{T}$

1 $\mathcal{T}=empty$

$N=\\{s_{1},s_{2},\cdots,s_{k}\\}$ // All nodes

$V=\\{\\}$ // Set of current nodes

2 Add $N[argmax(\mathbf{r})]$ to $V$

$\mathcal{T}.root=N[argmax(\mathbf{r})]$ // Adding the root

3 while  _$|V|\neq k$_ do

$p,c=argmax(\mathbf{A}[V,N\backslash V])$ // Search block

$\mathcal{T}.link(N[c],N[p])$ // Child-parent link

$V.add(N[c])$ // Adding the child node

4

5 end while

return $\mathcal{T}$

Algorithm 1 The proposed algorithm for discourse dependency tree construction

To fix the idea of discourse dependency tree construction algorithm, we
present a step-by-step execution of this algorithm demonstrated in Figure 3.
In Step 0, the sentence $s_{1}$ is added as the root of the tree $\mathcal{T}$
since it has the maximum value in the array of the root probabilities. Next in
Step 1, the algorithm searches for the maximum probability value in the row
$s_{1}$ while the column $s_{1}$ is excluded. The maximum value is this block
is $0.4$ and corresponds to entry ($s_{1}$,$s_{2}$). Therefore, the sentence
$s_{2}$ is added as the child node of the sentence $s_{1}$. In a similar
fashion, the algorithm continues until all $6$ sentences are added to the
tree.

Figure 3: An illustration of a step-by-step execution of Algorithm 1 for the
sample document presented in Figure 1. The search block at each iteration has
been highlighted. Note the letter ‘p’ for the _parent node_ and ‘c’ for the
_child node_.

###  3.2 Structural Document-level Representation

We use a similar method presented in Liu and Lapata (2018) to extract a
structurally rich representation for the entire document. First, for each
sentence (i.e., a discourse unit), we obtain a structurally-aware
representation. To achieve this, we take into account the parent-child
probabilities as well as the root probabilities as follows.

$\displaystyle\mathbf{p}_{j}$
$\displaystyle=r_{j}\times\mathbf{e}_{root}+\sum_{z=1}^{k}{\mathbf{A}[z,j]\times
f_{z}}$ (5) $\displaystyle\mathbf{c}_{j}$
$\displaystyle=\sum_{z=1}^{k}{\mathbf{A}[j,z]\times f_{j}}$
$\displaystyle\mathbf{g}_{j}$
$\displaystyle=\mathcal{G}(\mathbf{W}[\mathbf{p}_{j}||\mathbf{c}_{j}||f_{j}]+\mathbf{b})$

where $\mathbf{p}_{j}$ and $\mathbf{c}_{j}$ are two context vectors taking
into account possible parents and children of a sentence $s_{j}$,
respectively, $\mathbf{e}_{root}$ denotes a special root embedding vector,
$||$ denotes vector concatenation operator, and $\mathbf{g}_{j}$ is a
_structurally-aware representation for sentence $s_{j}$_. Finally, to extract
a structurally rich representation for the entire document, we average all of
its $\mathbf{g}_{j}$ vectors:

$\displaystyle x=\frac{1}{k}\sum_{j=1}^{k}\mathbf{g}_{j}$ (6)

where $x$ denotes _the structurally rich document-level representation_.

###  3.3 Fake News Classification

We hypothesize that the document-level structurally rich representations (Eq.
6) offer a discriminatory power to detect fake news documents. Therefore, as
shown in Figure 2, we employ a binary classification for fake news detection
formulated as follows.

$\displaystyle c_{i}$
$\displaystyle=-\big{(}y_{i}log(p^{i}_{f})+(1-y_{i})log(p^{i}_{r})\big{)}$ (7)
$\displaystyle\mathcal{L(\theta)}$ $\displaystyle=\sum_{\forall
d_{i}\in\mathcal{D}}c_{i}$

where $y_{i}$ is the ground-truth label of a document $d_{i}\in\mathcal{D}$,
$c_{i}$ is the cross-entropy loss value, $p^{i}_{f}$ and $p^{i}_{r}$ are
probabilities of $d_{i}$ being fake or real, respectively. $p^{i}_{f}$ and
$p^{i}_{r}$ are obtained from the representation $x$ (Eq. 6) fed to a fully
connected layer followed by the softamx function. In Eq. 7, $\theta$ denotes
the framework’s parameters and $\mathcal{L}$ is the total loss of the model.
Since the entire framework (Eq. 1 to 7) is fully differentiable, we utilize
the error backpropagation Hecht-Nielsen (1992) to calculate the gradients
followed by the stochastic gradient descent Bottou (2010) to update and
optimize the parameters. Note that the discourse dependency tree construction
algorithm presented in Section 3.1.2 is employed post hoc. Hence, the gradient
calculation over $argmax$ operator (line 1 of Algorithm 1) is not performed.

##  4 Structure-related Properties

Incorporating discourse-level structure offer a discriminatory power
distinguishing fake and real documents, which will be verified in Section 5.3.
We expect more than this discriminatory power. We expect to identify
insightful and interpretable information from extracted structures which can
delineate intrinsic differences between fake and real news documents. To meet
this expectation, we define three fundamental properties of constructed
discourse dependency trees. Note that we leave the definitions of more
advanced properties as one future work. We seek to fulfill two goals by
defining the structure-related properties. First, we intend to highlight the
way that fake and real news documents are different. Second, we intend to
leverage these properties to shed light on the coherence of fake and real news
documents. Coherence has been the subject of many studies Barzilay and Lapata
(2008); Lin et al. (2011); Guinaudeau and Strube (2013); Li and Hovy (2014)
and is concerned with how constituents of a document (e.g., discourse units)
are linked together in a way that the entire text creates a clear mental
picture to the readers Storrer (2002). Notwithstanding its importance,
coherence has not been investigated in the fake news domain in a large-scale
and systematic fashion. Aiming at filling this gap, we naturally connect the
defined structure-related properties with the coherence of news documents.

######  Property 1 (Number of Leaf Nodes)

This property, denoted as $\mathsf{P}_{l}$, defines the normalized number of
leaf nodes in a discourse dependency tree:

$\displaystyle\mathsf{P}_{l}=\frac{l}{{log}(k)}$ (8)

where $l$ is the number of leaf nodes (i.e., sentences) in the discourse
dependency tree of a document. Recall that $k$ is the total number of
sentences in a document.

The intuition behind defining Property 1 is as follows. According to the
description of the dependency tree in Section 3.1, leaf nodes are isolated
discourse units and no other discourse units depend on them. Thus, the more
the number of leaf nodes is, the less inter-linked the discourse units will
be, and vice versa. Therefore, Property 1 is likely to indicate the coherence
of a document – the higher $\mathsf{P}_{l}$, the more isolated sentences and
the less coherent the document. Also, for a document with $k$ sentences
$\mathsf{P}_{l}\in[\frac{1}{log(k)},\frac{k-1}{log(k)}]$.

######  Property 2 (Preorder Difference)

This property, denoted as $\mathsf{P}_{t}$, defines the normalized positional
difference between the preorder traversal of a document’s discourse dependency
tree and its original sentential sequential order:

$\displaystyle\mathsf{P}_{t}=\frac{\sum_{j=1}^{k}{|s^{position}_{j}-j|}}{log(k)}$
(9)

where $s^{position}_{j}$ denotes the position of a sentence $s_{j}$ in the
preorder traversal222The subtrees are ordered based on _when_ they are added
as the child nodes of a parent node in Algorithm 1. That is why we can compute
preorder traversal. of dependency tree of a document e.g.,
$s^{position}_{3}=4$ in Figure 1. The position of $s_{j}$ in the original
sequential order is simply $j$333We assume that the sentences in the
sequential order are numbered incrementally from $1$ to $k$.. The preorder
traversal of the tree in Figure 1 is the sequence
$\\{s_{1},s_{2},s_{4},s_{3},s_{5}\\}$ and the sentential sequential order is
$\\{s_{1},s_{2},s_{3},s_{4},s_{5}\\}$. Therefore, according to the definition
of Property 2:

$\mathsf{P}_{t}=\frac{|1-1|+|2-2|+|4-3|+|3-4|+|5-5|}{log(5)}\approx 2.86$.

The preorder traversal of a document’s discourse dependency tree takes into
consideration the organization of a document respect to the dependencies
between sentences. Then, the purpose of Property 2 is to measure how much the
organization of a document, captured through the preorder traversal, deviates
from its sentential sequential order. Sentence order is highly related to the
coherence of a document where the displaced order of sentences in a document
makes it less coherent Li and Hovy (2014). Thus, intuitively, the less the
value of Property 2 for a document is, the more coherent that document should
be. Also, for a document with $k$ sentences
$\mathsf{P}_{t}\in[\frac{k-1}{log(k)},\frac{(k^{2}-1)}{2log(k)}]$ if $k$ is
odd and $\mathsf{P}_{t}\in[\frac{k-1}{log(k)},\frac{k^{2}}{2log(k)}]$ if $k$
is even.

######  Property 3 (Parent-Child Distance)

This property, denoted as $\mathsf{P}_{c}$, defines the normalized sum of
positional distances between child nodes and their parents when they are
considered in the original sequential order:

$\displaystyle\mathsf{P}_{c}=\frac{\sum_{\forall
c,p\in\mathcal{T}}|c_{position}-p_{position}|}{log(k)}$ (10)

where $c_{position}$ and $p_{position}$ denote the positions of a child node
$c$ and a parent node $p$, respectively, in the original sentential sequential
order. For instance, in our running example, the parent node $s_{3}$ has
$p_{position}=3$ (i.e., it is the third sentence) and its child node $s_{5}$
has $c_{position}=5$. Therefore, their parent-child distance is $|5-3|=2$.
Following a similar calculation for other parent-child pairs, we have
$\mathsf{P}_{c}=\frac{1+2+2+2}{log(5)}\approx 10$ .

Similar to Property 2, Property 3 pertains to the organization of a document
and takes into consideration the deviation from sentential sequential order.
Intuitively speaking, usually, we expect that a child node and its parent to
be close to each other in the original sequential order. Consequently, the
less value of this property is, the more coherent a document is likely to be.
The range of Property 3 in a document containing $k$ sentences is
$\mathsf{P}_{c}\in[\frac{k-1}{log(k)},\frac{k(k-1)}{2log(k)}]$.

##  5 Experiments

To verify the performance of the proposed framework HDSF, we conduct a set of
experiments. We seek to answer the following research questions:

(1). How does the proposed framework perform on fake news detection?

(2). How do the defined structure-related properties describe the fake and
real news documents?

In this section, we first describe the datasets followed by presenting the
experimental settings. Afterward, we evaluate the performance of HDSF compared
to several representative baselines. Finally, we present a structural analysis
of the fake/real news documents.

###  5.1 Datasets

We utilize five available fake news datasets in this study. The first two
datasets are collected by Shu et al. (2017) and include online articles whose
veracities have been identified by experts in
BuzzFeed444https://www.buzzfeed.com and
PolitiFact555http://www.politifact.com/. For the next two datasets, we utilize
two available online fake news datasets provided by
kaggle.com666https://www.kaggle.com/mrisdal/fake-news/data
777https://www.kaggle.com/jruvika/fake-news-detection. Finally, we include the
dataset constructed and shared by
McIntire888https://github.com/GeorgeMcIntire/fake_real_news_dataset. Since the
proposed framework HDSF is a general-purpose framework investigating
discourse-level structures of fake/real news documents based on their textual
contents, we do not restrict HDSF to a particular source of data and therefore
combine all datasets. Similar to the previous work Shu et al. (2017), we
balance the dataset to avoid a trivial solution as well as ensuring a fair
performance comparison. In total, we have $3360$ fake and $3360$ real
documents.

###  5.2 Experimental Settings

First, we pre-process the documents by removing numbers, non-English
characters, stop-words (e.g., ‘with’), and converting all characters to lower
case. We randomly select $134$ documents as the development set, ($67$ from
each class) and $134$ documents ($67$ from each class) as the test set. The
remaining $6452$ documents are used for training. The development set is used
for tuning the hyper-parameters. We initialize the word embeddings from the
Google news pre-trained word2vec embeddings Mikolov et al. (2013)999Out-of-
vocabulary words are initialized randomly.. LeakyReLU Xu et al. (2015) is used
as the non-linear activation function and the number of hidden units in the
BLSTM network is set to $100$. Each simulation is run for $200$ steps with a
random mini-batch size of $40$ documents. The learning rate starts at $0.01$
with the decay rate of $0.9$ after every $50$ steps. We use the ADAM optimizer
Kingma and Ba (2014) to optimize the parameters. The PyTorch
package101010https://pytorch.org/ is utilized for the implementation and the
code and data are publicly available in https://github.com/hamidkarimi/HDSF.

###  5.3 Comparison Results

To answer the research question (1), we compare the performance of HDSF with
the following representative baselines.

N-grams. In this baseline method, we extract and combine unigrams, bigrams,
and trigrams features and use SVM (Support Vector Machines) Scholkopf and
Smola (2001) for classification.

LIWC Pennebaker et al. (2015). LIWC (Linguistic Inquiry and Word Count) offers
a set of rich psycholinguistic features for a written document. We extract
$94$ features for each document and use SVM for classification.

RST Rubin and Lukoianova (2015). We extract a set of RST relations Mann and
Thompson (1988) using the implementation of the method proposed by Ji and
Eisenstein (2014). Then, we vectorize the relations and employ SVM for
classification. This baseline takes into account the hierarchical structure of
documents via RST.

BiGRNN-CNN Ren and Zhang (2016). A CNN (Convolutional Neural Network) is
applied at the sentence-level on word embeddings and a BiGRNN (Bi-Directional
Gated Recurrent Neural Network) extracts features from a sequence of extracted
sentential features. This baseline takes into consideration a two-level
sequential structure for a document.

LSTM[w+s]. In this baseline, we apply an LSTM network on a sequence of word
embeddings belonging to a sentence and then apply another LSTM on a sequence
of extracted sentential features. LSTM[w+s] also considers a two-level
sequential structure for a document.

LSTM[s]. This method is similar to LSTM[w+s] except that the mean of word
embeddings in a sentence is used instead of applying an LSTM network. LSTM[s]
considers a single sequential structure for a document.

We use accuracy as the metric of performance evaluation given that the dataset
is fully balanced. Table 1 shows the comparison results on the test set and we
make the following observations:

  * •

N-grams achieve a better performance than LIWC. In line with the previous
study Ott et al. (2011), this shows that for fake news detection, taking into
account the context of a document as n-grams do is more effective than
employing the existing pre-defined dictionaries as LIWC does.

  * •

Most of the time, methods wherein a document’s structure is somehow taken into
account outperform n-grams and LIWC. This observation shows that for fake news
detection, the content’s structure plays an important role.

  * •

The poor performance of RST is because of the following reasons: a) using RST
without an annotated corpus is not very effective, and b) RST relations are
extracted using auxiliary tools optimized for other corpora which cannot be
applied effectively to the fake news corpus in hand. Note that annotating RST
for our corpus is extremely unscalable and time-consuming.

  * •

The proposed framework HDSF significantly outperforms all other methods. This
observation shows that hierarchical discourse-level representations are
effectively rich for fake news prediction.

Table 1: Comparison results Method | Accuracy (%)
---|---
N-grams | 72.37
LIWC | 70.26
RST | 67.68
BiGRNN-CNN | 77.06
LSTM[w+s] | 80.54
LSTM[s] | 73.63
HDSF | 82.19

###  5.4 The Inspection of HDSF

To further verify the working of the HDSF framework, we inspect HDSF in more
detail. Figure 4(a) demonstrates the training error during model optimization.
As we can observe from this figure, the error is decreasing as the training
process proceeds. Furthermore, Figure 4(b) demonstrates the accuracy on the
development set during the training and it is monotonically increasing as the
training goes on. Hence, based on these figures, we can ensure the framework
is getting optimized and _learns_ to classify fake news documents correctly.

(a) The training error

(b) The accuracy on dev set

Figure 4: The Inspection of HDSF

###  5.5 Structural Analysis for Fake/Real Documents

In this section, we compute the average values of structure-related
properties, presented in Section 4, for the fake/real news documents belonging
to the test set. Figure 5 shows the results. We make the two key observations
based on this figure:

  * •

There is a significant difference in all three properties for fake news
documents vs. real news documents. _This observation shows the fact that
structures of fake news documents at the discourse-level are substantially
different from those of real ones_.

  * •

Noticeably, in all three properties, the real news documents show less value
than the fake news documents. As described in Section 4, all three properties
are closely connected to the coherence of a document. _Therefore, real news
documents indicate more degree of coherence_.

Figure 5: Average values of the proposed structure-related properties for fake
and real news documents

##  6 Related Work

Content-based fake news detection has been the subject of many linguistic
research endeavors. DePaulo et al. (2003) investigated fake stories introduced
insightful cues in fake stories and highlighted ‘unusual’ language in such
stories. N-grams and Part-of-Speech (POS) tags are fundamental features of a
text which have been utilized for fake news detection Ahmed et al. (2017); Ott
et al. (2013). Also, LIWC Pennebaker et al. (2015) has been employed to
investigate the role of individual words in a document for deception detection
Ott et al. (2011). Since POS tags, n-grams, and LIWC features are considered
as ‘shallow’ and hand-crafted features, deep neural networks have been
utilized for fake news detection where features are extracted automatically
Wang (2017); Ren and Zhang (2016); Volkova et al. (2017); Karimi et al.
(2018). In this study, we also utilized an automated feature extraction
instead of relying on hand-craft features.

Syntax-based approaches have been employed to take into account the
hierarchical structure of textual documents for fake news detection Feng et
al. (2012); Pérez-Rosas and Mihalcea (2015). One caveat of syntax-based
approaches is their reliance on auxiliary parsing tools which might propagate
error in later part of a developed model. Moreover, generating syntactic
production rules in an automated manner is a complicated process.

Another way of incorporating structure is discourse-level parsing Mann and
Thompson (1988); Li et al. (2014a); Ren and Zhang (2016) which has seldom been
explored for fake news detection. The noticeable exception is the approach
developed by Rubin and Lukoianova (2015). They extracted a set of RST
relations in fake and real documents and vectorized them using a Vector Space
Model (VSM) method Strehl and Ghosh (2000). Unlike Rubin and Lukoianova
(2015), in this work, we proposed an automated and data-driven discourse-level
parsing approach which used neither any annotated corpus nor any external
tool.

##  7 Conclusion and Future Work

In this work, we looked into fake news detection from a new perspective. We
hypothesized that hierarchical discourse-level structure of news documents
offers a discriminatory power for fake news detection. To investigate this
hypothesis, we proposed a new framework HDSF, which can automatically extract
discourse-level structures of real/fake news documents represented by
dependency trees while does not rely on an annotated corpus. Moreover, we
defined a set of insightful properties describing tree structures. Conducted
experiments confirmed the power of our approach where it outperformed
representative baselines. More importantly, we highlighted noticeable
differences between structures of fake and real news documents. These
differences also indicated less coherency in the fake news documents.

The new perspective pursued in this paper can be continued in several
directions. First, we intend to define more advanced properties from the
discourse dependency trees. Second, investigating the hierarchical structure
at the word-level will be an exciting research inquiry. Finally, unsupervised
discourse-level structure extraction of fake/real news documents is a
worthwhile research topic.

## Acknowledgment

This work is supported by the National Science Foundation (NSF) under grant
numbers IIS-1714741, IIS-1715940, IIS-1845081, CNS-1815636, and a grant from
Criteo Faculty Research Award. We would like to thank Mr. Tyler Derr and other
members of the Data Science and Engineering (DSE) lab at Michigan State
University111111http://dse.cse.msu.edu/ for their constructive comments.

## References

  * Ahmed et al. (2017) Hadeer Ahmed, Issa Traore, and Sherif Saad. 2017.  Detection of online fake news using n-gram analysis and machine learning techniques.  In _International Conference on Intelligent, Secure, and Dependable Systems in Distributed and Cloud Environments_ , pages 127–138. Springer.
  * Allcott and Gentzkow (2017) Hunt Allcott and Matthew Gentzkow. 2017.  Social media and fake news in the 2016 election.  _Journal of Economic Perspectives_ , 31(2):211–36.
  * Bachenko et al. (2008) Joan Bachenko, Eileen Fitzpatrick, and Michael Schonwetter. 2008.  Verification and implementation of language-based deception indicators in civil and criminal narratives.  In _Proceedings of the 22nd International Conference on Computational Linguistics-Volume 1_ , pages 41–48. Association for Computational Linguistics.
  * Barzilay and Lapata (2008) Regina Barzilay and Mirella Lapata. 2008.  Modeling local coherence: An entity-based approach.  _Computational Linguistics_ , 34(1):1–34.
  * Bhatia et al. (2015) Parminder Bhatia, Yangfeng Ji, and Jacob Eisenstein. 2015.  Better document-level sentiment analysis from rst discourse parsing.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pages 2212–2218.
  * Bottou (2010) Léon Bottou. 2010.  Large-scale machine learning with stochastic gradient descent.  In _Proceedings of COMPSTAT’2010_ , pages 177–186. Springer.
  * DePaulo et al. (2003) Bella M DePaulo, James J Lindsay, Brian E Malone, Laura Muhlenbruck, Kelly Charlton, and Harris Cooper. 2003.  Cues to deception.  _Psychological bulletin_ , 129(1):74.
  * Feng et al. (2012) Song Feng, Ritwik Banerjee, and Yejin Choi. 2012.  Syntactic stylometry for deception detection.  In _Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Short Papers-Volume 2_ , pages 171–175. Association for Computational Linguistics.
  * Guinaudeau and Strube (2013) Camille Guinaudeau and Michael Strube. 2013.  Graph-based local coherence modeling.  In _Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , volume 1, pages 93–103.
  * Hecht-Nielsen (1992) Robert Hecht-Nielsen. 1992.  Theory of the backpropagation neural network.  In _Neural networks for perception_ , pages 65–93. Elsevier.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780.
  * Ji and Eisenstein (2014) Yangfeng Ji and Jacob Eisenstein. 2014.  Representation learning for text-level discourse parsing.  In _Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , volume 1, pages 13–24.
  * Karimi et al. (2018) Hamid Karimi, Proteek Roy, Sari Saba-Sadiya, and Jiliang Tang. 2018.  Multi-source multi-class fake news detection.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , pages 1546–1557.
  * Kim et al. (2017) Yoon Kim, Carl Denton, Luong Hoang, and Alexander M Rush. 2017.  Structured attention networks.  _arXiv preprint arXiv:1702.00887_.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_.
  * Li and Hovy (2014) Jiwei Li and Eduard Hovy. 2014.  A model of coherence based on distributed sentence representation.  In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 2039–2048.
  * Li et al. (2014a) Jiwei Li, Rumeng Li, and Eduard Hovy. 2014a.  Recursive deep models for discourse parsing.  In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 2061–2069.
  * Li et al. (2014b) Sujian Li, Liang Wang, Ziqiang Cao, and Wenjie Li. 2014b.  Text-level discourse dependency parsing.  In _Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , volume 1, pages 25–35.
  * Lin et al. (2011) Ziheng Lin, Hwee Tou Ng, and Min-Yen Kan. 2011.  Automatically evaluating text coherence using discourse relations.  In _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1_ , pages 997–1006. Association for Computational Linguistics.
  * Liu and Lapata (2018) Yang Liu and Mirella Lapata. 2018.  Learning structured text representations.  _Transactions of the Association of Computational Linguistics_ , 6:63–75.
  * Mann and Thompson (1988) William C Mann and Sandra A Thompson. 1988.  Rhetorical structure theory: Toward a functional theory of text organization.  _Text-Interdisciplinary Journal for the Study of Discourse_ , 8(3):243–281.
  * Mikolov et al. (2013) Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013.  Efficient estimation of word representations in vector space.  _arXiv preprint arXiv:1301.3781_.
  * Morey et al. (2018) Mathieu Morey, Philippe Muller, and Nicholas Asher. 2018.  A dependency perspective on rst discourse parsing and evaluation.  _Computational Linguistics_ , (Just Accepted):1–54.
  * Ott et al. (2013) Myle Ott, Claire Cardie, and Jeffrey T Hancock. 2013.  Negative deceptive opinion spam.  In _Proceedings of the 2013 conference of the north american chapter of the association for computational linguistics: human language technologies_ , pages 497–501.
  * Ott et al. (2011) Myle Ott, Yejin Choi, Claire Cardie, and Jeffrey T Hancock. 2011.  Finding deceptive opinion spam by any stretch of the imagination.  In _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1_ , pages 309–319. Association for Computational Linguistics.
  * Pennebaker et al. (2015) James W Pennebaker, Ryan L Boyd, Kayla Jordan, and Kate Blackburn. 2015.  The development and psychometric properties of liwc2015.  Technical report.
  * Pérez-Rosas and Mihalcea (2015) Verónica Pérez-Rosas and Rada Mihalcea. 2015.  Experiments in open domain deception detection.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pages 1120–1125.
  * Prasad et al. (2007) Rashmi Prasad, Eleni Miltsakaki, Nikhil Dinesh, Alan Lee, Aravind Joshi, Livio Robaldo, and Bonnie L Webber. 2007.  The penn discourse treebank 2.0 annotation manual.
  * Ren and Zhang (2016) Yafeng Ren and Yue Zhang. 2016.  Deceptive opinion spam detection using neural network.  In _Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers_ , pages 140–150.
  * Rubin and Lukoianova (2015) Victoria L Rubin and Tatiana Lukoianova. 2015.  Truth and deception at the rhetorical structure level.  _Journal of the Association for Information Science and Technology_ , 66(5):905–917.
  * Scholkopf and Smola (2001) Bernhard Scholkopf and Alexander J Smola. 2001.  _Learning with kernels: support vector machines, regularization, optimization, and beyond_.  MIT press.
  * Schuster and Paliwal (1997) Mike Schuster and Kuldip K Paliwal. 1997.  Bidirectional recurrent neural networks.  _IEEE Transactions on Signal Processing_ , 45(11):2673–2681.
  * Shu et al. (2017) Kai Shu, Suhang Wang, and Huan Liu. 2017.  Exploiting tri-relationship for fake news detection.  _arXiv preprint arXiv:1712.07709_.
  * Storrer (2002) Angelika Storrer. 2002.  Coherence in text and hypertext.  _Document Design_ , 3(2):156–168.
  * Strehl and Ghosh (2000) Alexander Strehl and Joydeep Ghosh. 2000.  Impact of similarity measures on web-page clustering.
  * Volkova et al. (2017) Svitlana Volkova, Kyle Shaffer, Jin Yea Jang, and Nathan Hodas. 2017.  Separating facts from fiction: Linguistic models to classify suspicious and trusted news posts on twitter.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , volume 2, pages 647–653.
  * Wang (2017) William Yang Wang. 2017.  ” liar, liar pants on fire”: A new benchmark dataset for fake news detection.  _arXiv preprint arXiv:1705.00648_.
  * Xu et al. (2015) Bing Xu, Naiyan Wang, Tianqi Chen, and Mu Li. 2015.  Empirical evaluation of rectified activations in convolutional network.  _arXiv preprint arXiv:1505.00853_.


product of $\mathscr{F}(A_{1}),\dots,\mathscr{F}(A_{n})$.

######  Lemma C.14.

If a functor $\mathscr{F}$ preserves products, then $\mathscr{F}\circ A^{-}$
and $\mathscr{F}(A)^{-}$ are naturally equivalent.

######  Proof C.15.

We define a natural equivalence $\eta\colon\mathscr{F}\circ
A^{-}\to\mathscr{F}(A)^{-}$ by components as
$\eta_{n}\colon\mathscr{F}(A^{n})\to\mathscr{F}(A)^{n}$ is defined as the map
given by the $n$-tuple
$\mathscr{F}(p_{1}),\dots,\mathscr{F}(p_{n})\colon\mathscr{F}(A^{n})\to\mathscr{F}(A)$.
Since $\eta_{n}$ commutes with the projections of the two products, it is an
isomorphism by the same argument as we used in showing that product is unique
up to isomorphisms. It is also straightforward to check that $\eta$ is natural
using the universal property of the product.

###  C.1 Two general lemmata

Given the definitions above, the first lemma is rather trivial. It claims that
we can transfer polymorphisms through any functor that preserves products. It
was mentioned in the context of promise CSPs in [31], although in different
flavours it can be tracked down to Lawvere theories.

######  Lemma C.16.

If a functor $\mathscr{F}\colon\text{cat}_{1}\to\text{cat}_{2}$ preserves
products, then there is a minion homomorphism

$\xi\colon\operatorname{pol}(A,B)\to\operatorname{pol}(\mathscr{F}(A),\mathscr{F}(B))$

for all $A,B\in\text{cat}_{1}$ such that $\hom(A,B)\neq\emptyset$.

######  Proof C.17.

By definition $\operatorname{pol}(\mathscr{F}(A),\mathscr{F}(B))$ is the
composition of $\mathscr{F}(A)^{-}$ and $\hom({-},\mathscr{F}(B))$. Since the
first functor is naturally equivalent to $\mathscr{F}\circ A^{-}$, we may
assume they are equal. We can then define a natural transformation
$\xi\colon\hom(A^{-},B)\to\hom(\mathscr{F}(A^{-}),\mathscr{F}(B))$ by

$\xi_{n}(f)=\mathscr{F}(f).$

To show $\xi$ preserves minors, observe that $f^{\pi}$ is defined as $f\circ
p_{\pi}^{A}$, and consequently $\mathscr{F}(f^{\pi})=\mathscr{F}(f\circ
p_{\pi}^{A})=\mathscr{F}(f)\circ\mathscr{F}(p_{\pi}^{A})=\mathscr{F}(f)\circ
p_{\pi}^{\mathscr{F}(A)}=\mathscr{F}(f)^{\pi}$.

The second lemma is a direct generalisation of [3, Lemma 4.8(1)], and the
proof is analogous.

######  Lemma C.18.

Let $A,A^{\prime},B,B^{\prime}\in\text{cat}$ be such that $\hom(A,B)$ is non-
empty. Then every pair $a\in\hom(A^{\prime},A)$ and $b\in\hom(B,B^{\prime})$
induces a minion homomorphism

$\xi\colon\operatorname{pol}(A,B)\to\operatorname{pol}(A^{\prime},B^{\prime}).$

######  Proof C.19.

First, observe that $a$ induces a natural transformation
$A^{-}\to(A^{\prime})^{-}$, which can be shown by using the definition of
products. We will denote its components by
$a^{n}\in\hom(A^{n},(A^{\prime})^{n})$. The minion homomorphism is defined by
$\xi_{n}(f)=b\circ f\circ a^{n}$. To show that $\xi$ preserves minors, observe
that the following diagram commutes.

${(A^{\prime})^{n}}$${A^{n}}$${(A^{\prime})^{m}}$${A^{m}}$${B}$${B^{\prime}}$$\scriptstyle{p_{\pi}^{A^{\prime}}}$$\scriptstyle{a^{n}}$$\scriptstyle{p_{\pi}^{A}}$$\scriptstyle{f^{\pi}}$$\scriptstyle{a^{m}}$$\scriptstyle{f}$$\scriptstyle{b}$

Consequently, we have that $\xi(f^{\pi})=b\circ f^{\pi}\circ a^{n}=(b\circ
f\circ a^{m})\circ p_{\pi}^{A^{\prime}}=\xi_{m}(f)^{\pi}$.

###  C.2 Homomorphism complexes preserve products

We prove that the functor $\operatorname{Hom}({\mathbf{R}_{3}},\mathbf{-})$
preserves products in the categorical sense. Essentially, it follows by the
same argument as the well-known fact that the product of homomorphisms
complexes is homotopically equivalent to the homomorphism complex of the
product (see, e.g., [20, Section 18.4.2]). We provide a bit more detailed
proof to show that the homotopy equivalence can be taken equivariant, and that
the products are preserved in the categorical sense which is a slightly
stronger statement. Let us first prove that there is an equivariant homotopy
equivalence. To provide this equivalence, we use the following technical
lemma.

######  Lemma C.20.

Let $\mathsf{K}$ be an order complex of a poset. If $\alpha,\beta\colon
V(\mathsf{K})\to V(\mathsf{K})$ are monotone maps such that
$\alpha(x)\leq\beta(x)$ for each $x$, then their linear extensions are
homotopic.

######  Proof C.21.

Observe that the map $h\colon\\{0,1\\}\times V(\mathsf{K})\to V(\mathsf{K})$
defined by $h(0,x)=\alpha(x)$ and $h(1,x)=\beta(x)$ is monotone, and that the
complex of the product poset is homeomorphic to $[0,1]\times\mathsf{K}$.
Consequently, $h$ induces a homotopy between $\alpha$ and $\beta$ by linear
extension.

######  Lemma C.22.

For each $G$-structure $\mathbf{A}$, and structures $\mathbf{B}_{1}$, …,
$\mathbf{B}_{n}$, there is a $G$-equivariant homotopy equivalence

$\operatorname{Hom}(\mathbf{A},\mathbf{B}_{1})\times\dots\times\operatorname{Hom}(\mathbf{A},\mathbf{B}_{n})\sim_{G}\operatorname{Hom}(\mathbf{A},\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}).$

######  Proof C.23.

For each functor $\mathscr{F}$, we always have a morphism

$f\in\hom(\mathscr{F}(\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}),\mathscr{F}(\mathbf{B}_{1})\times\dots\times\mathscr{F}(\mathbf{B}_{n}))$

defined by the universal property of the product applied to the maps
$\mathscr{F}(p_{i})$. In the case
$\mathscr{F}=\operatorname{Hom}({\mathbf{R}_{3}},\mathbf{-})$, this morphism
is represented by the continuous map

$\alpha:\operatorname{Hom}(\mathbf{A},\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n})\to\operatorname{Hom}(\mathbf{A},\mathbf{B}_{1})\times\dots\times\operatorname{Hom}(\mathbf{A},\mathbf{B}_{n})$

defined by $\alpha(m)=(p_{1}\circ m,\dots,p_{n}\circ m)$ for each
$m\in\operatorname{mhom}(\mathbf{A},\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n})$
and extending linearly. It is straightforward to check that $\alpha$ is an
equivariant continuous map. We prove that it has a homotopy inverse $\beta$
defined on vertices by

$\beta(m_{1},\dots,m_{n})\colon x\mapsto m_{1}(x)\times\cdots\times m_{n}(x),$

and extending linearly. Clearly, $\beta$ is $G$-equivariant and
$\alpha\circ\beta=1$.

We show that $\beta\circ\alpha$ is equivariantly homotopic to the identity. It
is easy to observe that $\beta(\alpha(m))\geq m$ for each
$m\in\operatorname{mhom}(\mathbf{A},\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n})$.
Since both $\alpha$ and $\beta$ are monotone and equivariant, so is the
composition, and the inequality gives an equivariant homotopy between
$\beta\circ\alpha$ and the identity by the above lemma.

The proof above immediately gives that
$\operatorname{Hom}({\mathbf{R}_{3}},\mathbf{-})$ preserves products. This is
since we showed that $[\alpha]$, which commutes with projections, is an
isomorphism.

######  Corollary C.24.

For each $G$-structure $\mathbf{A}$, the functor
$\operatorname{Hom}(\mathbf{A},{-})\colon\text{rel}\to\text{htop}_{G}$
preserves products.

###  C.3 The minion homomorphism
$\operatorname{pol}(\mathbf{LO}_{3},\mathbf{LO}_{4})\to\mathscr{Z}_{3}$

We can now conclude the proof of the lemma claiming that there is a minion
homomorphism
$\operatorname{pol}(\mathbf{LO}_{3},\mathbf{LO}_{4})\to\mathscr{Z}_{3}$.

######  Proof C.25 (Proof of Lemma 3.2).

We have the following minion homomorphisms

$\operatorname{pol}(\mathbf{LO}_{3},\mathbf{LO}_{4})\to\operatorname{hpol}(\operatorname{Hom}({\mathbf{R}_{3}},\mathbf{LO}_{3}),\operatorname{Hom}({\mathbf{R}_{3}},\mathbf{LO}_{4}))\to\operatorname{hpol}(S^{1},P^{2}).$

Where the first arrow follows from a combination of Corollary C.24, and Lemma
C.16, and the second arrow follows from Lemmata C.18, A.1, and A.18. The last
minion is isomorphic to $\mathscr{Z}_{3}$ by Lemma B.1, which yields the
required.

## References

  * [1] Per Austrin, Venkatesan Guruswami, and Johan Håstad.  (2+$\varepsilon$)-Sat is NP-hard.  SIAM Jounal on Computing, 46(5):1554–1573, 2017.  URL: https://eccc.weizmann.ac.il/report/2013/159/, doi:10.1137/15M1006507.
  * [2] Libor Barto, Diego Battistelli, and Kevin M. Berg.  Symmetric promise constraint satisfaction problems: Beyond the Boolean case.  In Markus Bläser and Benjamin Monmege, editors, 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16–19, 2021, Saarbrücken, Germany (Virtual Conference), volume 187 of LIPIcs, pages 10:1–10:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPIcs.STACS.2021.10.
  * [3] Libor Barto, Jakub Bulín, Andrei Krokhin, and Jakub Opršal.  Algebraic approach to promise constraint satisfaction.  J. ACM, 68(4):28:1–66, 2021.  doi:10.1145/3457606.
  * [4] Joshua Brakensiek and Venkatesan Guruswami.  New hardness results for graph and hypergraph colorings.  In Ran Raz, editor, Conference on Computational Complexity (CCC 2016), volume 50 of LIPIcs, pages 14:1–14:27, Dagstuhl, Germany, 2016\. Schloss Dagstuhl–LZI.  doi:10.4230/LIPIcs.CCC.2016.14.
  * [5] Joshua Brakensiek and Venkatesan Guruswami.  Promise constraint satisfaction: Algebraic structure and a symmetric Boolean dichotomy.  SIAM Jounal on Computing, 50(6):1663–1700, 2021.  doi:10.1137/19M128212X.
  * [6] Mark Braverman, Subhash Khot, Noam Lifshitz, and Dor Minzer.  An invariance principle for the multi-slice, with applications.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science—FOCS 2021, pages 228–236. IEEE Computer Soc., Los Alamitos, CA, 2022.  doi:10.1109/FOCS52979.2021.00030.
  * [7] Glen E. Bredon.  Equivariant Cohomology Theories, volume 34 of Lecture Notes in Mathematics.  Springer Berlin Heidelberg, 1967.  URL: http://link.springer.com/10.1007/BFb0082690, doi:10.1007/BFb0082690.
  * [8] Andrei A. Bulatov.  A dichotomy theorem for nonuniform CSPs.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 319–330, Berkeley, CA, USA, 2017. IEEE.  doi:10.1109/FOCS.2017.37.
  * [9] Jakub Bulín, Andrei Krokhin, and Jakub Opršal.  Algebraic approach to promise constraint satisfaction.  In Proc. of the 51st Annual ACM-SIGACT Symposium on the Theory of Computing, STOC 2019, pages 602–613, New York, USA, 2019. ACM.  doi:10.1145/3313276.3316300.
  * [10] Lorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin, Tamio-Vesa Nakajima, and Stanislav Živný.  On the complexity of the approximate hypergraph homomorphism problem, 2023\.  arXiv:2302.03456, doi:10.48550/arXiv.2302.03456.
  * [11] Víctor Dalmau and Jakub Opršal.  Local consistency as a reduction between constraint satisfaction problems, 2023.  arXiv:2301.05084, doi:10.48550/arXiv.2301.05084.
  * [12] Irit Dinur, Elchanan Mossel, and Oded Regev.  Conditional hardness for approximate coloring.  SIAM J. Comput., 39(3):843–873, 2009.  doi:10.1137/07068062X.
  * [13] Irit Dinur, Oded Regev, and Clifford Smyth.  The hardness of 3-uniform hypergraph coloring.  Combinatorica, 25(5):519–535, 2005.  doi:10.1007/s00493-005-0032-4.
  * [14] Venkatesan Guruswami and Sai Sandeep.  $d$-to-1 hardness of coloring 3-colorable graphs with $O(1)$ colors.  In 47th International Colloquium on Automata, Languages, and Programming, volume 168 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 62, 12. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020.
  * [15] Magnús M. Halldórsson.  A still better performance guarantee for approximate graph coloring.  Inform. Process. Lett., 45(1):19–23, 1993.  doi:10.1016/0020-0190(93)90246-6.
  * [16] Allen Hatcher.  Algebraic topology.  Cambridge University Press, Cambridge, 2002.
  * [17] Richard M. Karp.  Reducibility among combinatorial problems.  In Raymond E. Miller, James W. Thatcher, and Jean D. Bohlinger, editors, Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, Mar 20–22, 1972, Yorktown Heights, New York, pages 85–103, Boston, MA, 1972. Springer US.  doi:10.1007/978-1-4684-2001-2_9.
  * [18] Ken-ichi Kawarabayashi and Mikkel Thorup.  Coloring 3-colorable graphs with less than $n^{1/5}$ colors.  J. ACM, 64(1):4:1–4:23, 2017.  doi:10.1145/3001582.
  * [19] Sanjeev Khanna, Nathan Linial, and Shmuel Safra.  On the hardness of approximating the chromatic number.  Combinatorica, 20(3):393–415, 2000.  doi:10.1007/s004930070013.
  * [20] Dmitry Kozlov.  Combinatorial algebraic topology, volume 21 of Algorithms and Computation in Mathematics.  Springer, 2008.  doi:10.1007/978-3-540-71962-5.
  * [21] Andrei Krokhin and Jakub Opršal.  The complexity of 3-colouring $H$-colourable graphs.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS’19), pages 1227–1239, Baltimore, MD, USA, 2019. IEEE.  doi:10.1109/FOCS.2019.00076.
  * [22] Andrei Krokhin and Jakub Opršal.  An invitation to the promise constraint satisfaction problem.  ACM SIGLOG News, 9(3):30–59, 2022.  arXiv:2208.13538, doi:10.1145/3559736.3559740.
  * [23] Andrei A. Krokhin, Jakub Opršal, Marcin Wrochna, and Stanislav Živný.  Topology and adjunction in promise constraint satisfaction.  SIAM Journal on Computing, 52(1):38–79, 2023.  arXiv:2003.11351, doi:10.1137/20M1378223.
  * [24] László Lovász.  Kneser’s conjecture, chromatic number, and homotopy.  J. Combin. Theory Ser. A, 25(3):319–324, 1978.  doi:10.1016/0097-3165(78)90022-5.
  * [25] Jiří Matoušek.  Using the Borsuk-Ulam Theorem.  Lectures on Topological Methods in Combinatorics and Geometry. Springer-Verlag Berlin Heidelberg, first edition, 2003.  doi:10.1007/978-3-540-76649-0.
  * [26] Tamio-Vesa Nakajima and Stanislav Živný.  Linearly ordered colourings of hypergraphs.  ACM Trans. Comput. Theory, 14(3–4), February 2023.  doi:10.1145/3570909.
  * [27] Tamio-Vesa Nakajima and Stanislav Živný.  Boolean symmetric vs. functional PCSP dichotomy.  In 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–12, 2023.  doi:10.1109/LICS56636.2023.10175746.
  * [28] Jean-Pierre Serre.  Groupes d’homotopie et classes de groupes abeliens.  Annals of Mathematics, 58(2):258–294, 1953.  URL: http://www.jstor.org/stable/1969789.
  * [29] Tammo tom Dieck.  Transformation Groups.  De Gruyter, Berlin, New York, 1987.  URL: https://doi.org/10.1515/9783110858372, doi:doi:10.1515/9783110858372.
  * [30] Marcin Wrochna.  Homomorphism reconfiguration via homotopy.  SIAM J. Discret. Math., 34(1):328–350, 2020.  doi:10.1137/17M1122578.
  * [31] Marcin Wrochna and Stanislav Živný.  Improved hardness for $H$-colourings of $G$-colourable graphs.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’20), pages 1426–1435, Salt Lake City, UT, USA, 2020\. SIAM.  doi:10.1137/1.9781611975994.86.
  * [32] Dmitriy Zhuk.  A proof of the CSP dichotomy conjecture.  J. ACM, 67(5):30:1–30:78, 2020.  doi:10.1145/3402029.
  * [33] David Zuckerman.  Linear degree extractors and the inapproximability of max clique and chromatic number.  Theory Comput., 3:103–128, 2007.  doi:10.4086/toc.2007.v003a006.