#  ODGR: Online Dynamic Goal Recognition

Matan Shamir
<EMAIL_ADDRESS>
Department of Computer Science
Bar-Ilan University, Ramat Gan, Israel &Osher Elhadad11footnotemark: 1
<EMAIL_ADDRESS>
Department of Computer Science
Bar-Ilan University, Ramat Gan, Israel &Matthew E. Taylor
<EMAIL_ADDRESS>
Department of Computing Science
Alberta Machine Intelligence Institute (Amii)
University of Alberta, Edmonton, Canada &Reuth Mirsky
<EMAIL_ADDRESS>
Department of Computer Science
Bar-Ilan University, Ramat Gan, Israel These authors contributed equally.

###### Abstract

Traditionally, Reinforcement Learning (RL) problems are aimed at optimization
of the behavior of an agent. This paper proposes a novel take on RL, which is
used to learn the policy of another agent, to allow real-time recognition of
that agent’s goals. Goal Recognition (GR) has traditionally been framed as a
planning problem where one must recognize an agent’s objectives based on its
observed actions. Recent approaches have shown how reinforcement learning can
be used as part of the GR pipeline, but are limited to recognizing predefined
goals and lack scalability in domains with a large goal space. This paper
formulates a novel problem, “Online Dynamic Goal Recognition” (ODGR), as a
first step to address these limitations. Contributions include introducing the
concept of dynamic goals into the standard GR problem definition, revisiting
common approaches by reformulating them using ODGR, and demonstrating the
feasibility of solving ODGR in a navigation domain using transfer learning.
These novel formulations open the door for future extensions of existing
transfer learning-based GR methods, which will be robust to changing and
expansive real-time environments.

##  1 Introduction

Goal Recognition plays a crucial role in a variety of domains in Human-Robot
Interaction (Massardi et al., 2020; Jiang et al., 2021; Shvo et al., 2022;
Geib, 2002; Inam et al., 2018) and Multi-Agent Systems (Avrahami-Zilberbrand &
Kaminka, 2005; Freedman & Zilberstein, 2017; Su et al., 2023). Reasoning about
the goal of another agent presents an important challenge that complements an
ego agent’s policy learning and can inform and leverage RL techniques by
facilitating significant breakthroughs in how machines perceive and interpret
other agents, especially human intentions.

Existing GR approaches commonly assume that a fixed set of goals is provided
as part of the problem formulation (Mirsky et al., 2021; Meneguzzi & Pereira,
2021). In recent GR approaches that leverage Reinforcement Learning (RL),
which are also called GR as RL (Amado et al., 2022), a policy is learned for
each goal during a dedicated learning phase, often occurring offline before
the GR task. Then, during the inference phase, the algorithm is given a
sequence of observed actions and uses inference methods to perform GR. Unlike
planning-based GR (Ramírez & Geffner, 2010; Meneguzzi & Pereira, 2021), these
approaches have two fundamental limitations: first, all possible goals must be
specified before the inference phase. This requirement may not hold in dynamic
environments where goals can emerge or change over time. Second, an issue of
scalability arises when dealing with domains that encompass many goals. GR
requires significant computational effort and resources for considering each
individual goal, posing a challenge for large-scale applications. This problem
is further exacerbated in learning-based GR methods, where training an agent
for each goal becomes prohibitively costly and infeasible due to the
computational burden and time required for training.

Considering these two limitations, the first contribution of this paper is
conceptual: it formulates a problem called Online Dynamic Goal Recognition
(ODGR) with a temporal setting, where the time steps in which inputs are given
are specified. By generalizing the definition of GR, this paper can identify
the strengths and limitations of various GR frameworks across different
settings and assumptions. For example, consider the potential locations that a
researcher attending the RLC 2024 conference will choose to visit during their
day off. First, a recognition task should focus on navigation in
Massachusetts’s towns. Once inside Amherst, one might recognize the locations
people are moving towards to identify which attraction they are interested in.
Lastly, if the researcher is visiting the Beneski Museum of Natural History,
the recognition task changes to recognize the specific exhibition that the
researcher is interested in. One alternative is representing each task as a
different recognition problem, yet this solution means that a new set of goals
needs to be learned for each new task. This paper suggests a formulation where
these tasks can all be captured using a single recognition problem with a
single set of states and actions and changing goals.

The second contribution of this paper is algorithmic: we offer a general
algorithm that leverages Transfer Learning between RL tasks and demonstrates
the feasibility of a future framework that would implement this solution by
presenting a proof-of-concept for simple navigational environments. The
suggested algorithm expands the capacity of traditional learning-based GR
methods by adapting to “dynamic goals” – goals not set before the inference
phase. For this simple navigational domain, we propose a heuristic method that
aggregates existing Q-functions into new Q-functions for the dynamic goals,
which can adequately facilitate recognition. In the proposed solution,
existing Q-functions are learned before any observations are given, and they
are specifically designed to represent the expected policies for a predefined
set of base goals. The success of our solution is measured by the ability of
the recognizer to use the generated policies when performing the recognition
process and succeed in inferring the correct goal.

By introducing the concept of dynamic goals and presenting an approach for
policy transfer in navigational domains, we show that GR methods can be
extended to recognize and adapt to goals that emerge or change over time,
thereby broadening the range of problems and real-time domains to which these
methods can be applied. This research provides a significant first step
towards a more robust and adaptable GR system capable of handling dynamic
environments.

##  2 Preliminaries

The basic model used to describe a domain is a Markov Decision Process (MDP)
M, which is a 4-tuple $\langle S,A,P,R\rangle$ such that $S$ represents a set
of states in the environment, $A$ is the set of actions the agent can execute,
$P$ is a transition function, and $R$ is a reward function. A transition
function $P(s^{\prime}|s,a)$ returns the probability of transitioning from
state $s$ to state $s^{\prime}$ after taking action $a$, and a reward function
$R(s,a,s^{\prime})$ returns the reward obtained when an agent transitions from
$s$ to $s^{\prime}$ using action $a$. The utility function $Q$ (or Q-function)
is a function $Q:S\times A\rightarrow\mathcal{R}$ that defines the expected
utility of executing an action $a\in A$ in state $s\in S$. A Q-learning agent
estimates the values of $Q(s,a)$ from its experiences. A Policy $\pi:S\times
A\rightarrow[0,1]$ represents the probability that an agent would choose to
perform an action $a\in A$ in state $s\in S$.

The Goal Recognition (GR) problem consists of two agents: an actor and an
observer. The GR problem is defined from the observer’s perspective, who needs
to recognize the actor’s goal. Recognizing someone’s goal can be challenging,
particularly when these goals undergo sudden and unanticipated
transformations. This work relies on a line of work in which a GR algorithm
produces a set of policies or behaviors, one per goal (Polyvyanyy et al.,
2020; Ko et al., 2023; Chiari et al., 2023). We follow the utility-based GR
problem formulation from Amado et al. (2022):

###### Definition 1

A Goal Recognition problem is a tuple $\langle S,A,O,G,Q_{G}\rangle$, such
that $S$ is a set of states and $A$ is a set of actions an observed actor can
take, $O$ is a sequence of observations which are states and actions tuples,
$G\subseteq S$ is a set of goals (the actor pursues only one goal at a time),
and $Q_{G}$ is a set of Q-functions $\\{Q_{g}\\}_{g\in G}$. The output of a GR
problem is a goal $g\in G$ that best explains $O$.

Notice that this definition is very broad to enable different solutions.
First, it does not force a specific way to learn the Q-functions that the
actor will assume to reach $g$. Second, it does not elaborate on how a goal
explains the observations. Third, there is no single metric to quantify the
quality of one explanation over another.

Addressing GR through existing RL methodologies, such as those proposed by
Amado et al. (2022), involves learning a distinct policy for each goal within
a predefined goal set and then comparing these policies against observed
behaviors. Importantly, policies should not be perfectly optimal to tackle
many GR challenges. Hence, this article will introduce the application of
zero-shot transfer learning and heuristic strategies in simple navigational
domains as a first step in developing sub-optimal policies that nevertheless
provide precise GR outcomes. This paper focuses on goal-directed reward
functions (i.e., a reward function-oriented towards a goal $g$). In addition,
we focus on a specific implementation of GR using Q-Learning, but we highlight
that the ODGR problem, in general, is not limited to this implementation. To
represent the behavior of agents pursuing each potential goal in $G$, we use a
set $\Pi_{G}$. Each policy $\pi_{g}$ for an actor pursuing goal $g$ is a
softmax based on the Q values over all actions in state $s$:
$\pi_{g}(a|s)=\frac{Q_{g}(s,a)}{\sum_{a^{\prime}\in\mathcal{A}}Q_{g}(s,a^{\prime})}$.
Then, the policy for an agent pursuing a goal $\pi_{g}$ chooses an action
based on this probability distribution. Using this formulation, we can say
that a goal $g$ explains an observation sequence by evaluating the likelihood
that the actor will produce $o$ from $\pi_{g}$. As this paper focuses on
learning dynamic goals, we use an existing underlying approach to learn
$\Pi_{G}$ and follow a similar learning procedure as Amado et al. (2022) to
learn $\Pi_{G}$.

##  3 Online Dynamic Goal Recognition

Certain methodologies for GR rely on the notion that inputs to the problem
arrive at distinct time steps, along with varying assumptions regarding their
nature, such as whether they constitute goals or new observations. For
example, in Plan Recognition as Planning (Ramírez & Geffner, 2010), it is
expected that the description of the environment will be decoupled from a
specific problem instance, and different GR problems can be defined for the
same environment. We now present a formulation that aims to identify the
different components that can change within each problem, potentially
facilitating the selection of a more appropriate framework based on the
expected scenarios the user may encounter, and the requirements from the
expected solution.

###### Definition 2

An Online Dynamic Goals Recognition (ODGR) problem is a tuple $\langle
T,\langle G^{i},\\{O\\}^{i}\rangle_{i\in 1..n}\rangle$, where $T=\langle
S,A\rangle$ is a domain theory such that $S$ is the set of all possible states
and $A$ is the set of actions, $G^{i}$ is a set of goals such that $\forall
i\in\\{1..n\\},G^{i}\subseteq S$, and $\\{O\\}^{i}$ represents a set of
observations sequences (which might contain gaps), where each
$O_{j}\in\\{O\\}^{i}$ is a single observation sequence $O_{j}=\langle
o_{j}^{1},o_{j}^{2}\ldots\rangle=\langle\langle
s_{j}^{1},a_{j}^{1}\rangle,\langle s_{j}^{2},a_{j}^{2}\rangle,\ldots\rangle$.
Aligning with other online problems, each input is given at an increasing
time-step, lexicographically ordered, while it is inherent that because of the
input dependency, $T,G^{i}$ and $O_{j}\in\\{O\\}^{i}$ arrive at increasing
time-steps $\forall i,j$. For each two sequences of observations
$o^{l}_{t},o^{m}_{t}\in O_{t}$ $o^{z}_{j},o^{k}_{j}\in O_{j}$ where $t<j$,
$l<m$, and $z<k$, it holds that the observations are given chronologically,
such that $o^{l}_{t}<o^{m}_{t}<o^{z}_{j}<o^{k}_{j}$.

An algorithm for the ODGR problem is expected to return a goal $g\in G^{i}$
that best explains $O_{j}\in\\{O\\}^{i}$ upon its arrival for all $i,j$. The
final output is a set of goals
$G^{*}=\\{\\{g_{1}^{1},g_{2}^{1},...\\},\\{g_{1}^{2},g_{2}^{2},...\\},...,\\{g_{1}^{n},g_{2}^{n},...\\}\\}$
where $g_{j}^{i}$ is the goal returned by the algorithm upon receiving
$O_{j}\in\\{O\\}^{i}$. Using this formulation, one can now define a general GR
domain according to the domain theory $T$. In this work, the domain consists
of an MDP, but the formulation allows for different representations as well.
For each domain, several instances can be constructed at different times
according to the set of potential goals $G^{i}$ the actor may be pursuing. For
each instance, a single recognition problem is an observation trace that needs
to be explained by $G^{i}$. We can split an ODGR problem into several time
intervals, depending on the reception of each input type, $T$, $G$, and $O$.

Figure 1: OSGR and ODGR. The symbol $t_{i}$ denotes the initiation time of
each process.

Domain Learning Time is the duration necessary from receiving the domain
theory $T$ until concluding the domain-specific processing and being prepared
to receive $G$.

Goals Adaptation Time is the duration from receiving $G$ until completing the
inner-state changes and becoming ready to perform inference based on
observation trajectories $O$.

Inference Time is the time it takes to process an observation and produce a
goal in response.

A GR framework can receive a new piece of input before completing the
processing of the previous one. Following Allen’s interval algebra (Allen,
1983), we say that one input may overlap another input. These definitions
remain independent of the time steps assigned to each input. However, for
simplicity, in this work, we assume that inputs must precede one another.

We identify the family of problems where $n=1$ as Online Static GR (OSGR)
problems. They are static in the sense that in all instances, the set of goals
remains the same. Later in this section, we will show that many GR solutions
solve OSGR problems rather than their dynamic counterparts. Figure 1
illustrates OSGR and ODGR problems. The next section reviews recent work,
accompanied by an evaluative analysis associated with each methodology in
light of the novel definitions.

###  3.1 Model-Based GR (MBGR)

In MBGR, the recognition process entails utilizing a pre-defined model that
encompasses the characteristics of an environment along with the actions that
can be executed within that environment (Mirsky et al., 2021; Meneguzzi &
Pereira, 2021; Masters & Vered, 2021). Traditional MBGR often exploits
planning and parsing techniques (Avrahami-Zilberbrand & Kaminka, 2005; Geib &
Goldman, 2009; Geib, 2009; Ramirez & Geffner, 2009; Mirsky & Gal, 2016; Son et
al., 2016). A major limitation of such approaches is their inflexibility in
dynamic domains and that a complete model is crucial to solving the GR
problem. Such algorithms require complex computation processes to calculate
the likelihood of the goal given the observations. These computations are
required for every given observation sequence, making these solutions less
suitable for real-time performance.

Baker et al. (2009) and Ramırez & Geffner (2011) propose approaches to perform
GR over MDPs and Partially Observable MDPs (POMDPs) using planners, which
generally incur lower computational costs than training RL agents. However, it
is worth noting that MDP and POMDP planners may not scale as effectively as
classical planners. The use of MDPs enables a framework to incorporate
uncertainty modeling and, despite being model-based, opens a door for
employing RL to solve GR. These approaches require significant computation for
every observation sequence at Inference Time.

Several MBGR approaches focus on shortening the Inference Time by using pre-
processing. For example, in metric-based goal recognition, distances between
potential states are computed in the Domain Learning Time (Smith et al., 2015)
or in the Goals Adaptation Time (Masters & Sardina, 2017; Vered & Kaminka,
2017; Mirsky et al., 2019).

###  3.2 Model-Free GR (MFGR)

A Model-Free GR problem (MFGR) (Geffner, 2018) is one in which the recognizer
does not have access to the underlying model that describes the properties and
dynamics of the environment. While some approaches learn the model dynamics
and then employ MBGR methods (Asai & Fukunaga, 2018; Amado et al., 2018),
other approaches perform GR directly, without learning the model of the world.
Among these approaches, the main techniques include leveraging RL (Amado et
al., 2022) or employing deep neural networks to perform GR using a
classification network (Min et al., 2014; Borrajo et al., 2020; Chiari et al.,
2023). These methods typically have no Domain Learning Time, as the learning
process depends on the set of goals, a fairly long Goals Adaptation Time, and
a short Inference Time when given an observation sequence.

Different approaches have been proposed for learning an MFGR classification
model using languages like PDDL (Geib & Kantharaju, 2018; Maynard et al.,
2019; Borrajo et al., 2020; Min et al., 2014; 2016; Fang et al., 2023). These
approaches aim for generality by employing a simple domain file that specifies
actions using labels and defines a state space based on a finite set of
fluents (facts). Chiari et al. (2023) proposed a framework (termed GRnet) that
generalizes to any set of goals without additional learning, presenting a
model-free solution suitable for environments with changing goals. Compared to
the other approaches, GRnet excels in ODGR, demonstrating immediate adaptation
to new goal sets and fast inference for new observations through a forward
pass of the trained network. While this approach is promising, its reliance on
fluent enumeration is critical for its success.

A separate line of work uses MDPs instead of planning languages to model the
environment. Amado et al. (2022) presented an MDP-based method termed GR as
RL, which trains RL agents during Domain Adaptation Time and computes the
likelihood of such agents to produce the sequence of observations given at
Inference Time. In this method, the sharing of information across various GR
problems constructed by different observation traces with identical domain
theories and goals is inherent. This sharing facilitates short Inference Time.
This approach integrates the domain theory with the problem instance by
incorporating the policies of agents for each goal within their domain theory.
The fact that learning typically occurs only after receiving the domain theory
along with a set of goals limits the framework to recognizing goals only from
this set. This framework demonstrates high effectiveness in an OSGR setting,
However, as these approaches are not designed to handle dynamic environments
if employed in an ODGR context, every new set of goals necessitates expensive
re-training of agents for each distinct goal.

##  4 Dynamic Goal Recognition using Transfer Learning

To tackle ODGR problems, we introduce a general algorithm based on transfer
learning between source and target RL tasks (Taylor & Stone, 2009). It
facilitates learning in new tasks by transferring relevant parts from the
policies of the source tasks. This algorithm selects specific goals, $G_{b}$,
after receiving the domain theory $T$, and trains agents with policies
$\Pi_{G_{b}}$ for each of them as part of the Domain Learning time. Upon
receiving a set of goals $G_{d}$, the algorithm creates a set of policies
$\Pi_{G_{d}}$ for each new goal by leveraging transfer learning from the base
goals’ trained agents, as part of the Goals Adaptation time. When given an
observation trace of an actor, the algorithm returns the most likely goal by
using distance metrics, as part of the Inference time. For convenience, we
refer to the original set of goals, $G_{b}$, and the policies of their agents,
$\Pi_{G_{b}}$, as base goals and base policies. Similarly, the new goals,
$G_{d}$, in the adaptation phase are referred to as dynamic goals, and the
policies generated for them, $\Pi_{G_{d}}$, are called dynamic policies.

Algorithm 1 DomainLearningPhase

1:$T=\langle S,A\rangle$ \- a domain theory

2:$G_{b}=\text{SelectBaseGoals}(T)$

3:for $g\in G_{b}$ do

4: $q_{g}=\text{Learn}(T,g)$

5:$Q_{G_{b}}=\\{q_{g}\\}_{g\in G_{b}}$

6:$T_{G_{b}}=\langle S,A,Q_{G_{b}}\rangle$

7:return $T_{G_{b}}$

Algorithm 2 GoalsAdaptationPhase

1:$T_{G_{b}}=\langle S,A,Q_{G_{b}}=\\{q_{g}\\}_{g\in G_{b}}\rangle$

2:$g_{d}\in G_{d}$: a set of new goals

3:for $g\in G_{d}$ do

4: $q_{g}=\text{Transfer}(T_{G_{b}},g)$

5:$Q_{G_{d}}=\\{q_{g}\\}_{g\in G_{d}}$

6:$T_{G_{d}}=\langle S,A,Q_{G_{d}}\rangle$

7:return $T_{G_{d}}$

Algorithm 3 InferencePhase

1:$T_{G_{c}}=\langle S,A,Q_{G_{c}}\rangle,Q_{G_{c}}=\\{q_{g}\\}_{g\in G_{c}}$
\- State and action spaces, and Q-functions per goal ($g_{c}$)

2:$O$: an observation sequence (a sequence of states and actions tuples)
$(\langle s_{0},a_{0}\rangle,\ldots,\langle s_{t},a_{t}\rangle)$, where t is
the length of $O$

3:Sample/receive set of dynamic goals $G_{d}$

4:$m_{g}^{*}\leftarrow\infty$ $\triangleright$ Init shortest distance

5:for all $g$ in $G_{c}$ do $\triangleright$ Compute distances from $O$

6: $q_{g}^{O}$ is the Q-function of goal $g$ from $\\{q_{g}\\}_{g\in G_{c}}$
for $O$ states and actions

7: $m_{g}\leftarrow\text{DISTANCE}(q_{g}^{O},O)$ $\triangleright$ Use distance
measure

8: if $m_{g}\leq m_{g}^{*}$ then

9: $g^{*}\leftarrow g$ and $m_{g}^{*}\leftarrow m_{g}$

10:return $g^{*}$

Goal Adaptation using Transfer Learning (GATLing) consists of three parts that
are essential to solving the ODGR problem. The Domain Learning Time consists
of building a domain theory using Algorithm 1. Then, the system receives
inputs sequentially. If the input is a set of new goals, it creates a new
domain theory using algorithm 2, which uses transfer learning from the base
policies to train agents to the new goals, with the objective of minimizing
the Goals Adaption Time in this phase. The framework keeps the most updated
domain theory for future recognition, and if the input is a trace of
observations, it performs recognition using the most updated domain theory by
calling Algorithm 3. Algorithm 3 takes the dynamic goals’ Q-functions,
compares them to the observation, and chooses the most likely dynamic goal
using the DISTANCE metric, operations that typically require a short Inference
Time.

###  4.1 Implementation in a Navigational Domain

We implement GATLing using a simple navigational domain without obstacles to
show feasibility. We use the Gym MiniGrid navigational domain (Chevalier-
Boisvert et al., 2023) as a case study, in which we conduct a comparative
analysis of the different techniques’ respective performances.

We implement Algorithm 1 using Q-Learning, as suggested in the GRAQL framework
of Amado et al. (2022). As part of Algorithm 2, for policy transfer, we assign
utilities to states and actions by applying weights to the expected utilities
of actions from states in the Q-functions of the base goals. The weights
assigned to these Q-functions are determined by the similarity of the path
from the state to the base goal and the path to the dynamic goal, as perceived
at each state individually. The notion of similarity can also be interpreted
as distance in navigational domains. In the navigational domain, we used the
distance metric as a similarity metric (where a lower distance means greater
similarity). We employed two different methods to calculate this distance:

Static weights are assigned between each pair of base on dynamic goal,
according to their Euclidean distance. The weight assignment is considered
static as the weight for each action utility remains unchanged regardless of
the states’ spatial proximity to the dynamic goal. However, this approach
introduces challenges, notably because it applies equal weights to all
Q-values for every state in relation to a dynamic goal. As a result, in
certain states, there may be a tendency to move in directions contrary to
those leading to the dynamic goal, deviating from the optimal policy. This
issue often arises from the proximity of the dynamic goal to another
foundational goal in the opposite direction within these states.

Dynamic assigns variable weights to each state’s utility. This weight
assignment is based on the cosine similarity between the trajectory from the
current state at which the Q-function was being calculated to the dynamic goal
and the trajectory from this state to each base goal. The equation that
describes the dynamic approach based on cosine similarity is denoted as
follows:

$\small\text{Cosine\\_Similarity}(s,g_{b},g_{d})=\frac{\text{traj}(s,g_{b})\cdot\text{traj}(s,g_{d})}{\|\text{traj}(s,g_{b})\|\cdot\|\text{traj}(s,g_{d})\|}$
(1)

where $s$ is the current state, $g_{b}$ is a base goal, $g_{d}$ is a dynamic
goal, and $\text{traj}(s,g_{b})$ represents a 2D vector originating in $s$ and
ending at $g_{b}$. The cosine similarity between two trajectories ranges from
-1 (perfectly opposite directions) to 1 (perfectly aligned directions), with 0
indicating orthogonality.

To combine the policies of the base goals into a single policy for the dynamic
goal, we employed three different aggregation techniques of the Q-values:

Weighted Average (normalize) is a fair and accurate approach, but slow:
$\frac{\sum_{i=1}^{n}w_{i}\cdot Q_{i}(s,a)}{\sum_{j=1}^{n}w_{j}}$

Softmax is an accurate approach, but slow, and highly
variable:$\frac{\sum_{i=1}^{n}e^{w_{i}}\cdot
Q_{i}(s,a)}{\sum_{j=1}^{n}e^{w_{j}}}$

Max (Hard Weighted Average) is a greedy approach, fast but less accurate:
$\max_{i=1}^{n}Q_{i}(s,a)$

###  4.2 Empirical Evaluation

In this section, we present the results of our experiments, which evaluate
GATLing in different scenarios. Our evaluation focuses on four key evaluation
metrics: accuracy, precision, recall, and F-score. As the output of GATLing is
a distribution over a set of goals rather than a label, we explain the
implementation of each metric in Appendix A.

Evaluating policy transfer can be complex, as it varies greatly given the
domain’s dynamics and the properties of the source policies. Instead of
running batches of runs on an arbitrary subspace of policies, we focus our
experiments on two clear and controlled use cases: the first presents a
completely smooth environment (without sudden changes in Q-values) and the
second breaks this smoothness property. Both experiments employed Q-learning
for learning, and during the inference stage, we leveraged KL-divergence to
compare each policy with a pseudo-policy based on the observations reported by
Amado et al. (2022). The hyperparameters were set according to that work, and
were consistent across both experiments: $\alpha=1\times 10^{-3}$,
$\epsilon=1\times 10^{-8}$, $\gamma=0.99$, and $Episodes=10^{7}$. The base
goals used for the first experiment were (1,6), (6,6), and (6,1), and for the
second one (1,7), (7,7), and (7,1). The results are reported for partial
traces of 0.1, 0.3, and 0.5, as traces with a completeness score of 0.7 or
higher achieved a 100% success rate across all four metrics in all our
experiments, for both GRAQL and GATLing. (fuller traces showed absolute
success for both GRAQL and GATLing). We also implemented a scaling factor that
prioritizes and emphasizes each state’s highest-ranked action (or actions)
while reducing the Q-values of other actions in the same state. Appendix B
shows an example of the Q-table generated with and without this scaling.

| Empty 8x8 Minigrid
---|---
GATLing | GRAQL
OBS | Goals | Acc | Prec | Rec | F-score | Acc | Prec | Rec | F-score
0.1 | 2 | 1.0±0.0 | 0.95±0.15 | 0.95±0.15 | 0.95±0.15 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0
3 | 0.95±0.15 | 0.9±0.2 | 0.9±0.2 | 0.9±0.2 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0
4 | 0.9±0.2 | 0.8±0.4 | 0.8±0.4 | 0.8±0.4 | 0.95±0.15 | 0.9±0.2 | 0.9±0.2 | 0.9 ±0.2
0.3 | 2 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0
3 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0
4 | 0.95±0.15 | 0.95±0.15 | 0.95±0.15 | 0.95±0.15 | 1.0±0.0 | 0.95±0.15 | 0.95±0.15 | 0.95 ±0.15
0.5 | 2 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0
3 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0
4 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0
Average | 0.97 ±0.05 | 0.95 ±0.1 | 0.95 ±0.1 | 0.95 ±0.1 | 0.99 ±0.01 | 0.98 ±0.03 | 0.98 ±0.03 | 0.98 ±0.03
Table 1:  A comparison of dynamic GATLing and GRAQL in Experiment 1. The setup varies by the number of goals and observability level (OBS). We present the accuracy (Acc), Precision (Prec), Recall (Rec), and F-score . Cells show the average result (± standard dev.) over 10 executions.  | Simple Crossing (with 2 walls) 9x9 Minigrid
---|---
GATLing | GRAQL
OBS | Goals | Acc | Prec | Rec | F-score | Acc | Prec | Rec | F-score
0.1 | 2 | 0.9±0.2 | 0.9±0.2 | 0.9±0.2 | 0.9±0.2 | 0.8±0.4 | 0.8±0.4 | 0.8±0.4 | 0.8±0.4
0.3 | 2 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0
0.5 | 2 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0 | 1.0±0.0
Average | 0.96 ±0.06 | 0.96 ±0.06 | 0.96 ±0.06 | 0.96 ±0.06 | 0.93 ±0.13 | 0.93 ±0.13 | 0.93 ±0.13 | 0.93 ±0.13
Table 2:  A comparison of dynamic GATLing and GRAQL in Experiment 2.

####  4.2.1 Results

Tables 1 and 2 show the results from Experiment 1 and Experiment 2,
respectively. The dynamic approach significantly outperformed the static
approach, highlighting the importance of adaptability in ODGR. When using the
dynamic approach, the softmax and normalized techniques were always able to
effectively combine policies from base goals’ agents into coherent policies
for dynamic goals. In contrast, the max aggregation could not rank the true
goal as the most likely one. We, therefore, show the performance results of
the softmax aggregation method with a dynamic distance metric that performed
best, leaving out the results using other approaches presented in this paper.
Regarding runtime, GATLing policy construction comes only after a Domain
Learning Phase, in which runtime compares with GRAQL’s. Similarly, the
inference times are swift for both GATLing and GRAQL because both don’t
require any form of learning or planning. However, constructing a dynamic goal
policy using the GATLing framework required only 1.56 seconds on average
across 10 runs on a GPU. In contrast, learning a single goal with the GRAQL
approach took significantly longer, averaging 485.45 seconds across 10 runs on
the same GPU, emphasizing the potential of transfer learning in requiring
shorter goal adaptation times. While this evaluation cannot precisely
determine the performance of different approaches due to implementation
variability, it provides some insight into the potential benefits of
considering ODGR problems.

##  5 Conclusion

This paper presented the novel problem of ODGR, which emphasizes the time in
which different parts of the input are received, and the potential gain from
policy transer. It formally defines ODGR problems and how they compare to most
existing GR problems. Then, the paper provides an overview of existing GR
algorithms and their computational effort distribution according to ODGR’s
components. Lastly, the paper introduces GATLing, a general algorithm for
performing ODGR in 2D navigational domains, with an implementation using two
distance metrics and three aggregation techniques for the policy ensemble. Our
experiments demonstrate that in navigational domains without obstacles,
GATLing offers effective ODGR capabilities, with accurate recognition
performance and significantly reduced run-time compared to existing RL
recognition approaches.

While GATLing provides a foundation for future algorithms, there are several
clear areas for potential improvements. First, the proposed aggregation
techniques are expected to fail in domains that consist of rapid changes in Q
values. Moreover, it is not straightforward how this approach can be extended
to continuous state and action spaces. Nevertheless, by avoiding the lengthy
policy learning phases. GATLing ensures that the recognition process remains
efficient and scalable, even in environments where goals may emerge or evolve.
As the field of data-driven GR develops, we anticipate that the need for
faster goal learning will increase. This research is expected to contribute to
developing adaptable and efficient GR systems in dynamic, changing
environments.

## References

  * Allen (1983) James F Allen.  Maintaining knowledge about temporal intervals.  _Communications of the ACM_ , 26(11):832–843, 1983.
  * Amado et al. (2018) Leonardo Amado, Ramon Fraga Pereira, Joao Aires, Mauricio Magnaguagno, Roger Granada, and Felipe Meneguzzi.  Goal recognition in latent space.  In _2018 International Joint Conference on Neural Networks (IJCNN)_ , pp. 1–8. IEEE, 2018.
  * Amado et al. (2022) Leonardo Amado, Reuth Mirsky, and Felipe Meneguzzi.  Goal recognition as reinforcement learning.  In _Tthe AAAI Conference on Artificial Intelligence_ , volume 36, pp. 9644–9651, 2022.
  * Asai & Fukunaga (2018) Masataro Asai and Alex Fukunaga.  Classical planning in deep latent space: Bridging the subsymbolic-symbolic boundary.  In _Proceedings of the aaai conference on artificial intelligence_ , volume 32, 2018.
  * Avrahami-Zilberbrand & Kaminka (2005) Dorit Avrahami-Zilberbrand and Gal A Kaminka.  Fast and complete symbolic plan recognition.  In _IJCAI_ , pp. 653–658, 2005.
  * Baker et al. (2009) Chris L. Baker, Rebecca Saxe, and Joshua B. Tenenbaum.  Action understanding as inverse planning.  _Cognition_ , 113(3):329–349, 2009.  ISSN 0010-0277.  doi: https://doi.org/10.1016/j.cognition.2009.07.005.  URL https://www.sciencedirect.com/science/article/pii/S0010027709001607.  Reinforcement learning and higher cognition.
  * Borrajo et al. (2020) Daniel Borrajo, Sriram Gopalakrishnan, and Vamsi K. Potluru.  Goal recognition via model-based and model-free techniques, 2020.
  * Chevalier-Boisvert et al. (2023) Maxime Chevalier-Boisvert, Bolun Dai, Mark Towers, Rodrigo de Lazcano, Lucas Willems, Salem Lahlou, Suman Pal, Pablo Samuel Castro, and Jordan Terry.  Minigrid & miniworld: Modular & customizable reinforcement learning environments for goal-oriented tasks.  _arXiv preprint arXiv:2306.13831_ , 2023.
  * Chiari et al. (2023) Mattia Chiari, Alfonso Emilio Gerevini, Francesco Percassi, Luca Putelli, Ivan Serina, and Matteo Olivato.  Goal recognition as a deep learning task: the grnet approach.  In _Proceedings of the International Conference on Automated Planning and Scheduling_ , volume 33, pp. 560–568, 2023.
  * Fang et al. (2023) Zihao Fang, Dejun Chen, Yunxiu Zeng, Tao Wang, and Kai Xu.  Real-time online goal recognition in continuous domains via deep reinforcement learning.  _Entropy_ , 25(10):1415, 2023.
  * Freedman & Zilberstein (2017) Richard Freedman and Shlomo Zilberstein.  Integration of planning with recognition for responsive interaction using classical planners.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 31, 2017.
  * Geffner (2018) Hector Geffner.  Model-free, model-based, and general intelligence, 2018.
  * Geib (2009) Christopher Geib.  Delaying commitment in plan recognition using combinatory categorial grammars.  In _Twenty-First International Joint Conference on Artificial Intelligence_ , 2009.
  * Geib & Kantharaju (2018) Christopher Geib and Pavan Kantharaju.  Learning combinatory categorial grammars for plan recognition.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Geib (2002) Christopher W Geib.  Problems with intent recognition for elder care.  In _Proceedings of the AAAI-02 Workshop “Automation as Caregiver_ , pp. 13–17, 2002.
  * Geib & Goldman (2009) Christopher W Geib and Robert P Goldman.  A probabilistic plan recognition algorithm based on plan tree grammars.  _Artificial Intelligence_ , 173(11):1101–1132, 2009.
  * Inam et al. (2018) Rafia Inam, Klaus Raizer, Alberto Hata, Ricardo Souza, Elena Forsman, Enyu Cao, and Shaolei Wang.  Risk assessment for human-robot collaboration in an automated warehouse scenario.  In _International Conference on Emerging Technologies and Factory Automation (ETFA)_ , volume 1, pp. 743–751. IEEE, 2018.
  * Jiang et al. (2021) Yu-Sian Jiang, Garrett Warnell, and Peter Stone.  Goal blending for responsive shared autonomy in a navigating vehicle.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pp. 5939–5947, 2021.
  * Ko et al. (2023) Jonghyeon Ko, Fabrizio Maria Maggi, Marco Montali, Rafael Peñaloza, and Ramon Fraga Pereira.  Plan recognition as probabilistic trace alignment.  In _5th International Conference on Process Mining_ , 2023.
  * Massardi et al. (2020) Jean Massardi, Mathieu Gravel, and Éric Beaudry.  Parc: A plan and activity recognition component for assistive robots.  In _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , pp. 3025–3031. IEEE, 2020.
  * Masters & Sardina (2017) Peta Masters and Sebastian Sardina.  Cost-based goal recognition for path-planning.  In _Proceedings of the 16th conference on autonomous agents and multiagent systems_ , pp. 750–758, 2017.
  * Masters & Vered (2021) Peta Masters and Mor Vered.  What’s the context? implicit and explicit assumptions in model-based goal recognition.  In Zhi-Hua Zhou (ed.), _Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21_ , pp. 4516–4523. International Joint Conferences on Artificial Intelligence Organization, 8 2021.  doi: 10.24963/ijcai.2021/615.  URL https://doi.org/10.24963/ijcai.2021/615.  Survey Track.
  * Maynard et al. (2019) Mariane Maynard, Thibault Duhamel, and Froduald Kabanza.  Cost-based goal recognition meets deep learning.  _arXiv preprint arXiv:1911.10074_ , 2019.
  * Meneguzzi & Pereira (2021) Felipe Rech Meneguzzi and Ramon Fraga Pereira.  A survey on goal recognition as planning.  In _International Joint Conference on Artificial Intelligence (IJCAI), 2021, Canadá._ , 2021.
  * Min et al. (2014) Wookhee Min, Eun Ha, Jonathan Rowe, Bradford Mott, and James Lester.  Deep learning-based goal recognition in open-ended digital games.  In _The AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_ , volume 10, pp. 37–43, 2014.
  * Min et al. (2016) Wookhee Min, Bradford W Mott, Jonathan P Rowe, Barry Liu, and James C Lester.  Player goal recognition in open-world digital games with long short-term memory networks.  In _IJCAI_ , pp. 2590–2596, 2016.
  * Mirsky & Gal (2016) Reuth Mirsky and Ya’akov Gal.  Slim: semi-lazy inference mechanism for plan recognition.  In _Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence_ , pp. 394–400, 2016.
  * Mirsky et al. (2019) Reuth Mirsky, Ya’ar Shalom, Ahmad Majadly, Kobi Gal, Rami Puzis, and Ariel Felner.  New goal recognition algorithms using attack graphs.  In _Cyber Security Cryptography and Machine Learning: Third International Symposium, CSCML 2019, Beer-Sheva, Israel, June 27–28, 2019, Proceedings 3_ , pp. 260–278. Springer, 2019.
  * Mirsky et al. (2021) Reuth Mirsky, Sarah Keren, and Christopher Geib.  _Introduction to symbolic plan and goal recognition_ , volume 16.  Springer, 2021.
  * Polyvyanyy et al. (2020) Artem Polyvyanyy, Zihang Su, Nir Lipovetzky, and Sebastian Sardina.  Goal recognition using off-the-shelf process mining techniques.  In _International Conference on Autonomous Agents and MultiAgent Systems_ , pp. 1072–1080, 2020.
  * Ramirez & Geffner (2009) M. Ramirez and H. Geffner.  Plan recognition as planning.  In _Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence (IJCAI-09)_ , 2009.
  * Ramírez & Geffner (2010) Miguel Ramírez and Hector Geffner.  Probabilistic plan recognition using off-the-shelf classical planners.  In _The AAAI conference on artificial intelligence_ , volume 24, pp. 1121–1126, 2010.
  * Ramırez & Geffner (2011) Miquel Ramırez and Hector Geffner.  Goal recognition over pomdps: Inferring the intention of a pomdp agent.  In _IJCAI_ , pp. 2009–2014. IJCAI/AAAI, 2011.
  * Shvo et al. (2022) Maayan Shvo, Ruthrash Hari, Ziggy O’Reilly, Sophia Abolore, Sze-Yuh Nina Wang, and Sheila A McIlraith.  Proactive robotic assistance via theory of mind.  In _International Conference on Intelligent Robots and Systems (IROS)_ , pp. 9148–9155. IEEE, 2022.
  * Smith et al. (2015) David E Smith et al.  A fast goal recognition technique based on interaction estimates.  In _International Joint Conferences on Artificial Intelligence (IJCAI-15)_ , number ARC-E-DAA-TN24965, 2015.
  * Son et al. (2016) Tran Son, Orkunt Sabuncu, Christian Schulz-Hanke, Torsten Schaub, and William Yeoh.  Solving goal recognition design using asp.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 30, 2016.
  * Su et al. (2023) Zihang Su, Artem Polyvyanyy, Nir Lipovetzky, Sebastian Sardiña, and Nick van Beest.  Fast and accurate data-driven goal recognition using process mining techniques.  _Artificial Intelligence_ , 323:103973, 2023.
  * Taylor & Stone (2009) Matthew E Taylor and Peter Stone.  Transfer learning for reinforcement learning domains: A survey.  _Journal of Machine Learning Research_ , 10(7), 2009.
  * Vered & Kaminka (2017) Mor Vered and Gal A Kaminka.  Heuristic online goal recognition in continuous domains.  In _Proceedings of the 26th International Joint Conference on Artificial Intelligence_ , pp. 4447–4454, 2017.

##  Appendix A Evaluation Metrics Definition

As the output of our GATLing is a distribution over a set of goals rather than
a label, we explain how we implemented each measure:

  * •

Accuracy measures the proportion of correctly recognized dynamic goals. A goal
is considered correctly recognized if it has the highest likelihood of being
the actor’s goal in comparison to other goals.

  * •

Precision indicates how many of the most likely goals were the actor’s goal.

  * •

Recall indicated how many of the actor’s true goals were correctly identified.

  * •

F-score is the harmonic mean of Precision and Recall.

##  Appendix B Scaling Factor for Q-function Aggregation

Sometimes, the desired action may not have the highest Q-value after
aggregation. This phenomenon can sometimes be attributed to how two base
goals’ policies bias the dynamic policy in a slightly wrong direction. To
mitigate this issue, we implemented a scaling factor that prioritizes and
emphasizes each state’s highest-ranked action (or actions) while reducing the
Q-values of other actions in the same state. Figures 2 (left) and 2 (right)
show the crafting of a dynamic goal (4,4) Q-table for a $8\times 8$ Minigrid
environment without obstacles. The experimental setup is the same as
experiment 1. These scaling methods fine-tune the Q-values for particular
actions for every state to ensure consistent and optimal behavior of the
agent.

Figure 2: The heuristic Q-table generated from Q-tables whose base goals are
at (1,6), (6,1), and (6,6) using cosine similarity and softmax (without
scaling) at the $8\times 8$ environment. Each cell shows the Q-values for
taking the actions up, right, down, and left. The left (right) grid shows the
outcome Q-table without (with) scaling.


# Improving Graph-Based Text Representations with Character and Word Level
N-grams

Wenzhe Li  Nikolaos Aletras
Computer Science Department, University of Sheffield, UK
{wli90<EMAIL_ADDRESS>
###### Abstract

Graph-based text representation focuses on how text documents are represented
as graphs for exploiting dependency information between tokens and documents
within a corpus. Despite the increasing interest in graph representation
learning, there is limited research in exploring new ways for graph-based text
representation, which is important in downstream natural language processing
tasks. In this paper, we first propose a new heterogeneous word-character text
graph that combines word and character n-gram nodes together with document
nodes, allowing us to better learn dependencies among these entities.
Additionally, we propose two new graph-based neural models, WCTextGCN and
WCTextGAT, for modeling our proposed text graph. Extensive experiments in text
classification and automatic text summarization benchmarks demonstrate that
our proposed models consistently outperform competitive baselines and state-
of-the-art graph-based models.111Code is available here:
https://github.com/GraphForAI/TextGraph

##  1 Introduction

State-of-the art graph neural network (GNN) architectures Scarselli et al.
(2008) such as graph convolutional networks (GCNs) Kipf and Welling (2016) and
graph attention networks (GATs) Veličković et al. (2017) have been
successfully applied to various natural language processing (NLP) tasks such
as text classification Yao et al. (2019); Liang et al. (2022); Ragesh et al.
(2021); Yao et al. (2021) and automatic summarization Wang et al. (2020); An
et al. (2021).

The success of GNNs in NLP tasks highly depends on how effectively the text is
represented as a graph. A simple and widely adopted way to construct a graph
from text is to represent documents and words as graph nodes and encode their
dependencies as edges (i.e., word-document graph). A given text is converted
into a _heterogeneous graph_ where nodes representing documents are connected
to nodes representing words if the document contains that particular word
Minaee et al. (2021); Wang et al. (2020). Edges among words are typically
weighted using word co-occurrence statistics that quantify the association
between two words, as shown in Figure 1 (left).

However, word-document graphs have several drawbacks. Simply connecting
individual word nodes to document nodes ignores the ordering of words in the
document which is important in understanding the semantic meaning of text.
Moreover, such graphs cannot deal effectively with word sparsity. Most of the
words in a corpus only appear a few times that results in inaccurate
representations of word nodes using GNNs. This limitation is especially true
for languages with large vocabularies and many rare words, as noted by
Bojanowski et al. (2017). Current word-document graphs also ignore explicit
document relations i.e., connections created from pair-wise document
similarity, that may play an important role for learning better document
representations Li et al. (2020).

Figure 1: A simple word-document graph (left); and our proposed Word-Character
Heterogeneous graph (right). For right figure, the edge types are defined as
follows: (1) word-document connection if a document contains a word (i.e., tf-
idf); (2) word-word connection based on co-occurrence statistics (i.e., PMI);
(3) document-document connection with similarity score (i.e., cosine
similarity); (4) word n-grams and words connection if a word is part of
n-grams (0/1); (5) word n-grams and document connection if a document contains
a n-grams (0/1); and (6) character n-grams and words connection if a character
n-grams is part of a word (0/1).

Contributions: In this paper, we propose a new simple yet effective way of
constructing graphs from text for GNNs. First, we assume that word ordering
plays an important role for semantic understanding which could be captured by
higher-order n-gram nodes. Second, we introduce character n-gram nodes as an
effective way for mitigating sparsity Bojanowski et al. (2017). Third, we take
into account document similarity allowing the model to learn better
associations between documents. Figure 1 (right) shows our proposed Word-
Character Heterogeneous text graph compared to a standard word-document graph
(left). Finally, we propose two variants of GNNs, WCTextGCN and WCTextGAT,
that extend GCN and GAT respectively, for modeling our proposed text graph.

##  2 Methodology

Given a corpus as a list of text documents
$\mathcal{C}=\\{D_{1},...,D_{n}\\}$, our goal is to learn an embedding
$\mathbf{h}_{i}$ for each document $D_{i}$ using GNNs. This representation can
subsequently be used in different downstream tasks such as text classification
and summarization.

###  2.1 Word-Character Heterogeneous Graph

The Word-Character Heterogeneous graph $G=(V,E)$ consists of the node set
$V=V_{d}\cup V_{w}\cup V_{g}\cup V_{c}$, where $V_{d}=\\{d_{1},..,d_{n}\\}$
corresponds to a set of documents, $V_{w}=\\{w_{1},...,w_{m}\\}$ denotes a set
of unique words, $V_{g}=\\{g_{1},...,g_{l}\\}$ denotes a set of unique n-gram
tokens, and finally $V_{c}=\\{c_{1},...,c_{p}\\}$ denotes a set of unique
character n-grams. The edge types among different nodes vary depending on the
types of the connected nodes. In addition, we also add edges between two
documents if their cosine similarity is larger than a pre-defined threshold.

###  2.2 Word and Character N-grams Enhanced Text GNNs

The goal of GNN models is to learn representation for each node. We use
$\mathbf{H}^{d}\in R^{n_{d}\times k},\mathbf{H}^{w}\in R^{n_{w}\times
k},\mathbf{H}^{g}\in R^{n_{g}\times k},\mathbf{H}^{c}\in R^{n_{c}\times k}$ to
denote representations of document nodes, word nodes, word n-grams nodes and
character n-grams nodes, where $k$ is the size of the hidden dimension size.
$n_{d},n_{w},n_{g},n_{w}$ represent the number of documents, words, word
n-grams and character n-grams in the graph respectively. We use $e^{dw}_{ij}$
to denote the edge weight between the $i$th document and $j$th word.
Similarly, $e^{cw}_{kj}$ denotes the edge weight between the $k$th character
n-gram and $j$th word.

The original GCN and GAT models only consider simple graphs where the graph
contains a single type of nodes and edges. Since we now are dealing with our
Word-Character Heterogeneous graph, we introduce appropriate modifications.

#### Word and Character N-grams Enhanced Text GCN (WCTextGCN)

In order to support our new graph type for GCNs, we need a modification for
the adjacency matrix $\mathbf{A}$. The updating equation for original GCN is:

$\mathbf{H}^{(L+1)}=f(\hat{\mathbf{A}}\mathbf{H}^{L}\mathbf{W}_{L})$

where $W_{L}$ is the free parameter to be learned for layer $L$. We assume
$\mathbf{H}$ is simply the concatenation of
$\mathbf{H}^{d},\mathbf{H}^{w},\mathbf{H}^{g},\mathbf{H}^{c}$. For WCTextGCN,
the adjacency matrix $\mathbf{A}$ is re-defined as:

$\mathbf{A}=\begin{pmatrix}\mathbf{A}^{dd}_{sim}&\mathbf{A}^{dw}_{tfidf}&\mathbf{A}^{dg}_{tfidf}&-\\\
\mathbf{A}^{wd}_{tfidf}&\mathbf{A}^{ww}_{pmi}&\mathbf{A}^{wg}_{0/1}&\mathbf{A}^{wc}_{0/1}\\\
\mathbf{A}^{gd}_{tfidf}&\mathbf{A}^{gw}_{0/1}&-&-\\\
-&\mathbf{A}^{cw}_{0/1}&-&-\end{pmatrix}$

where $\mathbf{A}^{dd}_{sim}$ denotes the pair-wise similarity between
documents 222We remove edges with similarity score less than a pre-defined
threshold to avoid uninformative links., sub-matrix $\mathbf{A}^{dw}_{tfidf}$
represents the tf-idf score for all edges linking documents to words,
$\mathbf{A}^{wg}_{0/1}$ is the boolean sub-matrix representing whether a word
n-gram contains a specific word, and so on. The sub-matrix
$\mathbf{A}^{dw}_{tfidf}$ is the transpose of sub-matrix $A^{wd}_{tfidf}$.

#### Word and Character N-grams Enhanced Text GAT WCTextGAT

In GAT, the updates to the node representation is computed by weighting the
importance of neighboring nodes. Since our text graph contains four types of
nodes, each updating procedure consists of the following four phases
(dependency relation among nodes can be seen in Figure 1):

$\displaystyle\hat{\mathbf{H}}^{d}$
$\displaystyle=\text{GAT}(\mathbf{H}^{d},\mathbf{H}^{w},\mathbf{H}^{g})$
$\displaystyle\hat{\mathbf{H}}^{w}$
$\displaystyle=\text{GAT}(\mathbf{H}^{d},\mathbf{H}^{w},\mathbf{H}^{g},\mathbf{H}^{c})$
$\displaystyle\hat{\mathbf{H}}^{g}$
$\displaystyle=\text{GAT}(\mathbf{H}^{d},\mathbf{H}^{w})$
$\displaystyle\hat{\mathbf{H}}^{c}$ $\displaystyle=\text{GAT}(\mathbf{H}^{w})$

For example, to update word representation $\hat{\mathbf{H}}^{w}$, we need to
aggregate information from document nodes, word nodes, word n-gram nodes and
character n-gram nodes, respectively. Assume that we update the embedding for
word node $i$ by considering neighboring document nodes only (similar
procedure applies to other three types of nodes). The computation is as
follows:

$\displaystyle z_{ij}$
$\displaystyle=\text{Leaky}(a^{T}[\mathbf{W}_{v}\mathbf{h}^{w}_{i};\mathbf{W}_{d}\mathbf{h}^{d}_{j};\mathbf{W}_{e}{e}_{ij}^{wd}])$
$\displaystyle\alpha_{ij}$
$\displaystyle=\frac{\exp(z_{ij})}{\sum_{l\in\mathcal{N}_{i}}\exp(z_{il})}$
$\displaystyle\hat{\mathbf{h}^{1}_{i}}$
$\displaystyle=\sigma(\sum_{j\in\mathcal{N}_{i}}\alpha_{ij}\mathbf{W}_{d}\mathbf{h}^{d}_{j})$

where $\mathbf{W}_{v},\mathbf{W}_{d},\mathbf{W}_{e}$ are the trainable weights
of the model, that are applied to different types of nodes. $\alpha_{ij}$ is
the attention weight between word $i$ and document $j$. $\mathcal{N}_{i}$
denotes the set of neighboring documents for word $i$, and $\sigma(.)$ is the
activation function. Multi-head attention Vaswani et al. (2017) is also
introduced to capture different aspects of semantic representations for text:

$\hat{\mathbf{h}^{1}_{i}}=\parallel_{k=1}^{K}\sigma(\sum_{j\in\mathcal{N}_{i}}\alpha^{k}_{ij}\mathbf{W}^{k}_{d}\mathbf{h}_{j})$

Similarly, we can also compute
$\hat{\mathbf{h}^{2}_{i}},\hat{\mathbf{h}^{3}_{i}},\hat{\mathbf{h}^{4}_{i}}$
by considering other types of neighboring nodes. Finally, these
representations are concatenated, followed by linear transformation.

Dataset | 20NG | R8 | R52 | Ohsumed | MR |
---|---|---|---|---|---|---
TF-IDF+LR | 83.19$\pm$0.00 | 93.74$\pm$0.00 | 86.95$\pm$0.00 | 54.66$\pm$0.00 | 74.59$\pm$0.00 |
fastText | 79.38$\pm$0.30 | 96.13$\pm$0.21 | 92.81$\pm$0.09 | 57.70$\pm$0.49 | 75.14$\pm$0.20 |
CNN-rand | 76.83$\pm$0.61 | 94.02$\pm$0.57 | 85.37$\pm$0.47 | 43.87$\pm$1.00 | 74.98$\pm$0.70 |
CNN-non-static | 82.15$\pm$0.52 | 95.71$\pm$0.52 | 87.59$\pm$0.48 | 58.44$\pm$1.06 | 77.75$\pm$0.72 |
LSTM-rand | 65.71$\pm$1.52 | 93.68$\pm$0.82 | 85.54$\pm$1.13 | 41.13$\pm$1.17 | 75.06$\pm$0.44 |
LSTM-pretrain | 75.43$\pm$1.72 | 96.09$\pm$0.19 | 90.48$\pm$ 0.86 | 51.10$\pm$1.50 | 77.33$\pm$0.89 |
PTE | 76.74$\pm$0.29 | 96.69$\pm$ 0.13 | 90.71$\pm$ 0.14 | 53.58$\pm$ 0.29 | 70.23$\pm$0.36 |
BERT | 83.41$\pm$0.20 | 96.98$\pm$ 0.08 | 92.87$\pm$ 0.01 | 67.22$\pm$ 0.27 | 77.02$\pm$0.23 |
TextGCN | 86.34$\pm$0.09 | 97.07$\pm$ 0.10 | 93.56$\pm$0.18 | 68.36$\pm$0.56 | 76.74$\pm$0.20 |
WCTextGCN (Ours) | 87.21$\pm$0.54 | 97.49$\pm$0.20 | 93.88$\pm$0.34 |  68.52$\pm$0.20 | 77.85$\pm$ 0.34 |
TextGAT | 85.78$\pm$ 0.10 | 96.88$\pm$0.24 | 93.61$\pm$0.12 | 67.46$\pm$0.32 | 76.45$\pm$0.38 |
WCTextGAT (Ours) | 87.02$\pm$ 0.32 | 97.12$\pm$0.42 | 94.02$\pm$0.45 | 68.14$\pm$0.18 | 77.98$\pm$0.10 |
Table 1: Predictive test accuracy on five text classification benchmark
datasets. We run models 10 times and report mean$\pm$standard deviation.

##  3 Experiments and Results

We conduct experiments on two NLP tasks, i.e., text classification and
extractive summarization. The latter one can be also viewed as a
classification problem for each sentence level (i.e., to be included in the
summary or not).

###  3.1 Text Classification

#### Data

We select five widely used benchmark datasets including 20-Newsgroups,
Ohsumed, R52, R8 and MR. The statistics and the descriptions for these
datasets can be found in Yao et al. (2019).

#### Baselines

We compare our models to multiple existing state-of-the-art text
classification methods including TF-IDF+LR, fastText Joulin et al. (2016), CNN
Le and Mikolov (2014), LSTM Liu et al. (2016), PTE Tang et al. (2015), BERT
Devlin et al. (2018), TextGCN Yao et al. (2019) and TextGAT.

R8 | 3 | 4 | 5 | 6
---|---|---|---|---
3 | 97.1 | 97.5 | 97.5 | 97.4
4 |  | 96.9 | 97.1 | 97.5
5 |  |  | 97.1 | 97.4
6 |  |  |  | 97.4

R52 | 3 | 4 | 5 | 6
---|---|---|---|---
3 | 93.5 | 93.8 | 93.8 | 93.7
4 |  | 93.4 | 93.6 | 93.8
5 |  |  | 93.6 | 93.7
6 |  |  |  | 93.8

MR | 3 | 4 | 5 | 6
---|---|---|---|---
3 | 76.8 | 78.2 | 78.3 | 78.3
4 |  | 77.2 | 78.2 | 78.3
5 |  |  | 78.1 | 78.1
6 |  |  |  | 77.9

Table 2: The effect on performance by using character n-grams of $n$ in
{3,..,6}.

#### Experimental Settings

We randomly select 10% of the training set for the validation. For the
WCTextGCN model, we set the hidden size to $200$. For the TextGAT and
WCTextGAT models, we use $8$ attention heads with each containing $16$ hidden
units, and set edge feature dimension to $32$. The learning rate is $0.002$
and dropout rate $0.5$. We train all models for $200$ epochs using Adam
optimizer Kingma and Ba (2014) and early stopping with patience $20$. For all
the GNNs models, we use two hidden layers and $1$-of-$K$ encoding for
initialization.

#### Results

Table 1 shows the text classification results. We observe that the
incorporation of word n-grams, character n-grams and document similarity are
helpful and consistently improve predictive performance over other models.
i.e., the WCTextGCN model improves accuracy on 20NG over 0.8% compared to the
TextGCN model. The improvements in MR and R8 datasets are more substantial
than others, 0.5% and 1.1%, respectively. This is because character n-grams
help more when text is short, which is consistent with our hypothesis that
character n-grams are helpful for mitigating sparsity problems.

#### Varying the size of n-grams

For character n-grams, we set n-grams ranging from $3$ to $6$ characters, and
record the performance in different combinations of n-grams, i.e., $3$-grams
to $4$-grams, $3$-grams to $5$-grams and so on. The results are shown in Table
2 with best scores in bold. We observe that the best results are often
obtained when we vary the range of $n$ from $3$ to $4$. Further increase of
$n$ provides limited effects in model performance. In terms of word $n$-grams,
we observe similar results.

###  3.2 Extractive Text Summarization

Extractive single-document summarization is formulated as a binary
classification for each sentence with the aim to predict whether a sentence
should be included in the summary or not. We follow the same setting as the
HeterogeneousSumGraph (HSG) proposed by Wang et al. (2020) except that we use
our new Word-Character Heterogeneous graph representation denoted as HSG-Ours.

#### Data

We select two widely used benchmark newes articles datasets, CNN/DailyMail
(Hermann et al., 2015) and NYT50 Durrett et al. (2016). The first contains
287,227/13,368/11,490 examples for training, validation and test. The second
contains 110,540 articles with their summaries and is split into 100,834 and
9,706 for training and test. Following Durrett et al. (2016), we use the last
4,000 documents from the training set for validation and 3,452 test examples.

#### Baselines and Experimental Settings

We evaluate our models on single document summarization by comparing to three
different baselines Wang et al. (2020), Ext-BILSTM, Ext-Transformer and HSG.
For all experiments, we simply follow the same settings as in Wang et al.
(2020) and evaluate performance using ROUGE Lin and Hovy (2003).

#### Results

Tables 3 and 4 show the ROUGE scores on the two datasets. HGS-Ours with our
new text graph performs consistently better than competing ones. In
particular, for NYT50 data, the R-1 and R-2 metrics improve more than $0.5$
compared to the HSG model. We observe similar performance differences for R-L
on CNN/DailyMail data. This highlights the efficacy of our new text graph in
learning better word and sentence representations, especially for the words
that appear only few times but play an important role in summarization.

Model | R-1 | R-2 | R-L
---|---|---|---
Ext-BiLSTM | 46.32 | 25.84 | 42.16
Ext-Transformer | 45.07 | 24.72 | 40.85
HSG | 46.89 | 26.26 | 42.58
HSG-Ours | 46.96 | 26.20 | 43.43
Table 3: Performance (ROUGE) of different models on CNN/DailyMail. Model | R-1 | R-2 | R-L
---|---|---|---
Ext-BiLSTM | 41.59 | 19.03 | 38.04
Ext-Transformer | 41.33 | 18.83 | 37.65
HSG | 42.31 | 19.51 | 38.74
HSG-Ours | 42.85 | 20.03 | 38.90
Table 4: Performance (ROUGE) of different models on NYT50.

##  4 Conclusion

In this paper, we proposed a new text graph representation by incorporating
word and character level information. GNN models trained using our text graph
provide superior performance in text classification and single-document
summarization compared to previous work. In the future, we plan to extend our
proposed method to other tasks such as opinion extraction Mensah et al.
(2021), misinformation detection Chandra et al. (2020); Mu and Aletras (2020);
Mu et al. (2022), voting intention forecasting Tsakalidis et al. (2018) and
socioeconomic attribute analysis Aletras and Chamberlain (2018). We finally
plan to extend our GNN models by weighting the contribution of neighboring
nodes Zhang et al. (2022).

## References

  * Aletras and Chamberlain (2018) Nikolaos Aletras and Benjamin Paul Chamberlain. 2018.  Predicting twitter user socioeconomic attributes with network and language information.  In _Proceedings of the 29th on Hypertext and Social Media_ , pages 20–24.
  * An et al. (2021) Chenxin An, Ming Zhong, Yiran Chen, Danqing Wang, Xipeng Qiu, and Xuanjing Huang. 2021.  Enhancing scientific papers summarization with citation graph.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 12498–12506.
  * Bojanowski et al. (2017) Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. 2017.  Enriching word vectors with subword information.  _Transactions of the Association for Computational Linguistics_ , 5:135–146.
  * Chandra et al. (2020) Shantanu Chandra, Pushkar Mishra, Helen Yannakoudakis, Madhav Nimishakavi, Marzieh Saeidi, and Ekaterina Shutova. 2020.  Graph-based modeling of online communities for fake news detection.  _arXiv preprint arXiv:2008.06274_.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Durrett et al. (2016) Greg Durrett, Taylor Berg-Kirkpatrick, and Dan Klein. 2016.  Learning-based single-document summarization with compression and anaphoricity constraints.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1998–2008.
  * Hermann et al. (2015) Karl Moritz Hermann, Tomáš Kočiskỳ, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom. 2015.  Teaching machines to read and comprehend.  _arXiv preprint arXiv:1506.03340_.
  * Joulin et al. (2016) Armand Joulin, Edouard Grave, Piotr Bojanowski, and Tomas Mikolov. 2016.  Bag of tricks for efficient text classification.  _arXiv preprint arXiv:1607.01759_.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_.
  * Kipf and Welling (2016) Thomas N Kipf and Max Welling. 2016.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_.
  * Le and Mikolov (2014) Quoc Le and Tomas Mikolov. 2014.  Distributed representations of sentences and documents.  In _International conference on machine learning_ , pages 1188–1196. PMLR.
  * Li et al. (2020) Chen Li, Xutan Peng, Hao Peng, Jianxin Li, Lihong Wang, and S Yu Philip. 2020.  Textsgcn: Document-level graph topology refinement for text classification.
  * Liang et al. (2022) Bin Liang, Hang Su, Lin Gui, Erik Cambria, and Ruifeng Xu. 2022.  Aspect-based sentiment analysis via affective knowledge enhanced graph convolutional networks.  _Knowledge-Based Systems_ , 235:107643.
  * Lin and Hovy (2003) Chin-Yew Lin and Eduard Hovy. 2003.  Automatic evaluation of summaries using n-gram co-occurrence statistics.  In _Proceedings of the 2003 human language technology conference of the North American chapter of the association for computational linguistics_ , pages 150–157.
  * Liu et al. (2016) Pengfei Liu, Xipeng Qiu, and Xuanjing Huang. 2016.  Recurrent neural network for text classification with multi-task learning.  _arXiv preprint arXiv:1605.05101_.
  * Mensah et al. (2021) Samuel Mensah, Kai Sun, and Nikolaos Aletras. 2021.  An empirical study on leveraging position embeddings for target-oriented opinion words extraction.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 9174–9179, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Minaee et al. (2021) Shervin Minaee, Nal Kalchbrenner, Erik Cambria, Narjes Nikzad, Meysam Chenaghlu, and Jianfeng Gao. 2021.  Deep learning–based text classification: A comprehensive review.  _ACM Computing Surveys (CSUR)_ , 54(3):1–40.
  * Mu and Aletras (2020) Yida Mu and Nikolaos Aletras. 2020.  Identifying twitter users who repost unreliable news sources with linguistic information.  _PeerJ Computer Science_ , 6:e325.
  * Mu et al. (2022) Yida Mu, Pu Niu, and Nikolaos Aletras. 2022.  Identifying and characterizing active citizens who refute misinformation in social media.  In _14th ACM Web Science Conference 2022_ , WebSci ’22, page 401–410, New York, NY, USA. Association for Computing Machinery.
  * Ragesh et al. (2021) Rahul Ragesh, Sundararajan Sellamanickam, Arun Iyer, Ramakrishna Bairi, and Vijay Lingam. 2021.  Hetegcn: Heterogeneous graph convolutional networks for text classification.  In _Proceedings of the 14th ACM International Conference on Web Search and Data Mining_ , pages 860–868.
  * Scarselli et al. (2008) Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. 2008.  The graph neural network model.  _IEEE transactions on neural networks_ , 20(1):61–80.
  * Tang et al. (2015) Jian Tang, Meng Qu, and Qiaozhu Mei. 2015.  Pte: Predictive text embedding through large-scale heterogeneous text networks.  In _Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining_ , pages 1165–1174.
  * Tsakalidis et al. (2018) Adam Tsakalidis, Nikolaos Aletras, Alexandra I Cristea, and Maria Liakata. 2018\.  Nowcasting the stance of social media users in a sudden vote: The case of the greek referendum.  In _Proceedings of the 27th ACM International Conference on Information and Knowledge Management_ , pages 367–376.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _arXiv preprint arXiv:1706.03762_.
  * Veličković et al. (2017) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_.
  * Wang et al. (2020) Danqing Wang, Pengfei Liu, Yining Zheng, Xipeng Qiu, and Xuanjing Huang. 2020.  Heterogeneous graph neural networks for extractive document summarization.  _arXiv preprint arXiv:2004.12393_.
  * Yao et al. (2021) Huaxiu Yao, Yingxin Wu, Maruan Al-Shedivat, and Eric P Xing. 2021.  Knowledge-aware meta-learning for low-resource text classification.  _arXiv preprint arXiv:2109.04707_.
  * Yao et al. (2019) Liang Yao, Chengsheng Mao, and Yuan Luo. 2019.  Graph convolutional networks for text classification.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 7370–7377.
  * Zhang et al. (2022) Li Zhang, Heda Song, Nikolaos Aletras, and Haiping Lu. 2022.  Node-feature convolution for graph convolutional networks.  _Pattern Recognition_ , 128:108661.