# GEST: the Graph of Events in Space and Time as a
Common Representation between Vision and Language

Mihai Masala
<EMAIL_ADDRESS>Nicolae Cudlenco
<EMAIL_ADDRESS>Traian Rebedea
<EMAIL_ADDRESS>Marius Leordeanu
<EMAIL_ADDRESS>
###### Abstract

One of the essential human skills is the ability to seamlessly build an inner
representation of the world. By exploiting this representation, humans are
capable of easily finding consensus between visual, auditory and linguistic
perspectives. In this work, we set out to understand and emulate this ability
through an explicit representation for both vision and language - Graphs of
Events in Space and Time (GEST). GEST alows us to measure the similarity
between texts and videos in a semantic and fully explainable way, through
graph matching. It also allows us to generate text and videos from a common
representation that provides a well understood content. In this work we show
that the graph matching similarity metrics based on GEST outperform classical
text generation metrics and can also boost the performance of state of art,
heavily trained metrics.

##  1 Introduction

Making connections between vision and language seems easy for humans, but
extremely challenging for machines, despite a large body of research on image
and video captioning You et al. (2016); Aneja et al. (2018); Anderson et al.
(2018); Gao et al. (2017); Zhou et al. (2018); Wang et al. (2018), visual
question answering Antol et al. (2015); Lu et al. (2016); Zhong et al. (2020),
image synthesis Reed et al. (2016); Dong et al. (2017); Zhou et al. (2019) or
video generation Li et al. (2018); Balaji et al. (2019); Wu et al. (2022);
Singer et al. (2022); Villegas et al. (2022). While major improvements were
made using Transformers Vaswani et al. (2017), there is still a long way to
go. Also, these tasks were widely tackled independently of each other, with no
significant push for a more unified approach.

For tasks involving vision or language, information is usually processed by an
encoder (e.g. Transformers, CNNs or LSTMs) that builds a numerical
representation. While this approach is ubiquitous across both vision and NLP,
it is fundamentally limited by its implicit, mostly unexplainable, and highly
volatile nature. We strongly believe that such a representation can be
replaced (or augmented) by a better, explicit, and more robust one.

Figure 1: Functional overview of the proposed framework, centered around GEST.
GEST represent the central component, allowing for seamless transitions
between different forms. For example the transition from text to video is done
via steps A and C, while the transformation from video to text can be done via
steps D and B. In this work we focus on modules A and B .

In this work we introduce the Graph of Events in Space and Time (GEST) for
representing visual or textual stories, as groups of events related in space
and time at any level of semantics. GEST provides a common and meaningful
representation, through which we can compute similarities or differences
between texts or videos, and we could also generate texts or videos in an
explainable, analytical way.

##  2 Related Work

Graphs that model text: Graphs were traditionally used in natural language
processing (NLP) in many forms: syntactic trees (e.g. dependency or
constituency parsing trees) Lin (1998); Culotta and Sorensen (2004), semantic
trees (in the form of Combinatory Categorial Grammar) Zettlemoyer and Collins
(2012), Rhetorical Structure Theory (RST) Mann and Thompson (1988) trees,
Discourse Graphs Christensen et al. (2013), knowledge graphs Hao et al.
(2017); Bauer et al. (2018); Wang et al. (2019) and Abstract Meaning
Representation (AMR) graphs Banarescu et al. (2013). Recently, Graph Neural
Networks (GNNs) Zhou et al. (2020); Wu et al. (2020) were employed to parse
and encode such structures. RST trees Mann and Thompson (1988) and Discourse
Graphs Christensen et al. (2013) were developed as theories of text
organization using relations between claims as the central component and
emphasizing relations between these claims. Then, knowledge graphs are used
for encoding true fact about the world, allowing for efficient interogation
for Question Answering systems. Conversely, AMR graphs are semantic and
represent links between concepts from the natural text. Crucially, two
syntactically different sentences can share the same AMR graph if they are
semantically similar.

Graphs that model videos: Graphs were also used as a way to model videos
Sridhar et al. (2010); Aoun et al. (2011); Singh and Mohan (2017). While
previous approaches Brendel and Todorovic (2011); Chen and Grauman (2016);
Yuan et al. (2017); Wang and Gupta (2018); Cherian et al. (2022) consider the
nodes in the graph as video regions, we opt for a fundamentally different
approach, modeling events as graph nodes.

Aditya et al. (2018) define Scene Description Graphs (SDGs), graph-based
intermediate representation built specifically for describing images. SDGs are
based on objects, actions and semantic (based on KM-Ontology Clark et al.
(2004) ), ontological and spatial relations. With GEST we explicitly add the
temporal aspect as we are interested in representing videos instead of images.
Furthermore, our formulation is uniform (everything is an event), leads to a
more compact representation, allows for more complex (e.g. semantic, logical)
relations between events, while also being capable of representing such events
at different scales (see Figure 2).

Text generation metrics: Text generation metrics were studied in the field of
NLP for comparing two or more texts or documents Sai et al. (2022). Common
metrics include BLEU Papineni et al. (2002), METEOR Banerjee and Lavie (2005),
ROUGE Lin (2004) and SPICE Anderson et al. (2016). While BLEU and ROUGE
compute the similarity as the exact n-gram overlap, METEOR uses a more relaxed
matching criteria, based on stemmed matching, followed by synonymy and
paraphrase matching. SPICE builds a semantic scene-graph that is used to
extract information about objects, attributes and their relationships. More
recently, BERT Devlin et al. (2019) was integrated into text metrics.
BERTScore Zhang et al. (2019) uses a BERT backbone to obtain embeddings for
each token in the hypothesis and reference, which are matched using a greedy
approach, The state-of-the-art BLEURT Sellam et al. (2020) is pre-trained on a
large number of synthetic samples then finetuned on WMT Bojar et al. (2017)
and WebNLG Gardent et al. (2017). Synthetic data is generated by altering
Wikipedia sentences via back-translation, random words dropping or mask-
filling with BERT. Most pretraining signals are employed in the form of BLEU,
ROUGE and BERTScore, back-translation likelihood or textual entailment.

All mentioned text generation metrics employ clear rules, but they lack
explainability, due to the space in which computations are formed. The n-gram
space of BLEU, METEOR or ROUGE is simple, but totally counter-intuitive for
humans. In the case of BERTScore and BLEURT the projected space is even more
blurry and void of any intuitive understanding. Instead of projecting texts
into an n-gram or Transformer space, we propose a new representation space,
namely the space of events in space-time. Comparing events and their relations
expressed in two texts is much more natural. The fact that the GEST space is
explicit and grounded in the real world, is the very reason for which we
obtain explainability and interpretability.

##  3 Graph of Events in Space and Time

Fundamentally, a GEST is a means of representing stories. We focus on modeling
stories as they are the main way of expressing ideas, sentiments, facts,
perceptions, real-world or fantasy happenings. Stories are an essential
component in theater, cinema in the form of storyboards and are also an
integral part in relating, communicating and teaching historical events.
Stories are universal: a life is a story, a dream is a story, a single event
is a story. Atomic events create intricate stories in the same way that small
parts form an object in a picture, or how words form a sentence. Therefore, in
modeling stories, we distinguish interactions in space and time as the central
component. In general, changes in space and time lead to the notion of events
and interactions. Similarly to how changes in an image (image gradients) might
represent edges, space-time changes (at different levels of abstraction)
represent events. Accordingly, events in space and time could be detectable,
repeatable and discriminative. Interactions between events in space and time
change the current state of the world, can trigger or cause other events and
in turn cause other changes. Therefore, we use these events and their
interactions in space and time as the fundamental component of GEST.
Fundamentally, an edge connects two events in space and time. This connection
can be, but is not limited to temporal (e.g. after, meanwhile), logical (e.g.
and, or) or spatial (e.g. on top of). Since a node in GEST can also represent
physical objects (e.g, “The house exists for this period of time”) the graph
connections can represent any potential relation between two objects or two
events: the event “house” was involved in event: “holding a meeting at that
house”. Therefore, an edge can also represent an event by itself . For each
event we encode mainly the type of action, the involved entities, the location
and the timeframe in which an event takes place. Crucially, in GEST both
explicit (e.g. actions) and implicit (e.g. existence) events are represented
using the same rules. A GEST example can be found in Fig. 2 , while more
examples are in Appendix, Sec. A.

GEST can represent events at different scales, in greater detail by expanding
an event node into another graph, or in a lesser detail by abstracting a graph
into a single event node. In Fig. 2 we exemplify the power of such an
approach. On the left of Fig. 2 we show the GEST associated to the following
story: "John says that Daniel bought a watch". In the right half we expand the
event "Daniel bought a watch" to a more detailed story (GEST). All other event
nodes can be expanded into their own GEST stories (e.g. the paying action can
be further expanded by detailing the procedure: currency, amount, method and
so on). In principle, any GEST could become an event into a higher-level GEST
and vice-versa, any event could be expanded into a more detailed GEST.

Figure 2: GEST that illustrates the concept of multiple viewpoints and graph-
node equivalence. Note that for brevity, we omit some details in the nodes
(e.g. timeframe) and also add details to emphasize some points (e.g. the same
entity edges).

GEST represents concisely what happens in the real world. So, when vision and
language represent the same world, they could also be represented by the same
GEST. GEST is suitable for many tasks, including video-to-text or text-to-
video generation. GEST is an alternative to the standard way of solving these
tasks. Instead of generating natural language descriptions directly from an
obfuscated and implicit representation given by a video encoder, GEST breaks
video captioning in two problems: generate GEST from video, followed by
generating text from GEST. Conversely, generating a video starting from a text
prompt can be split into building GEST from text, followed by independently
creating the video (Fig. 1). In this paper we demonstrate both directions and
the advantages of the approach. We also argue that the main advantage of the
highly-explicit GEST representation is to give total knowledge and control
over the content of the text or video. Additional details and formal
definition of GEST is given in Appendix, Sec. B.

Building ground truth GEST from text: Ground truth GEST from text is needed
for training and evaluation. We note that building GEST representation from
text is not a trivial task, and we aim to automate this process. Nevertheless,
to obtain correct GEST from text human intervention is still needed. From each
sentence, we want to extract information such as the type of actions, the
entities involved, locations and the times of actions, as well as their
relations. All this is extracted by parsing the dependency tree (automatically
extracted111https://spacy.io/models/en#en_core_web_lg last accessed on 19th of
January 2023) of each individual sentence using a set of handcrafted rules
(followed if needed by human correction). Context (e.g. location inference)
and event ordering is also injected into the graph to obtain the complete GEST
of a story.

###  3.1 bAbI corpus

The bAbI corpus Weston et al. (2015) introduces a set of 20 question answering
tasks that are designed to act as proxy tasks for reading comprehension. As
the grammar of bAbI is rather simple, we devised a set of handcrafted rules to
automatically parse the dependency tree of each sentence in order to extract
the relevant information. For bAbI, the text-to-graph automatic module works
flawlessly, always detecting and extracting the correct information from each
sentence. In this work we focus on bAbI tasks numbered 1, 2, 3, 5, 6, 7, 8, 9,
10, 11, 12, 13, 14. We leave the other tasks for future work, as they are
devised with other goals in mind (e.g. tasks numbered 16 and 18 are devised
for basic induction or size reasoning) This leads to a total of 26.364 graphs,
with 21.588 train, 2.388 validation and 2.388 test graphs.

###  3.2 Videos-to-Paragraphs dataset

The Videos-to-Paragraphs dataset Bogolin et al. (2020) contains videos with
two stages of text representations. The 1st stage contains contains simple
sentences that describe simple actions, while the 2nd stage contains
semantically rich descriptions. This duality is especially suited for GEST as
the 1st stage is simple enough that we can immediately extract events as
simple actions. The 2nd stage is semantically richer and compacter. This
represents a crucial step-up from the bAbI corpus where only the simpler
linguistic stage is present. Following Bogolin et al. (2020), we will refer to
sentences from the 1st stage as SVOs (Subject, Verb, Object) and to the 2nd
stage texts as stories. In Videos-to-Paragraphs we identify thre types of
temporal relations between events (SVOs): "next", "same time" and "meanwhile",
using soft margins to extract them. Using both 1st and 2nd stage texts
annotations, we build (with minimal manual intervention) ground truth GEST
representations for the entire dataset, a total of 1048 samples (with a
85-5-10 training, dev, test split) consisting of GESTs and the two stages of
text descriptions.

##  4 GEST as a metric for comparing stories

We first want to study and evaluate the power of GEST to capture content from
stories in natural language. Ideally, different texts that illustrate the same
underlying story should have the same GEST. We evaluate this property by first
defining a similarity metric between two GESTs and compare its performance (in
separating texts that represent the same story vs. different stories) to other
metrics from the literature that work directly on the original text in natural
language.

Method | Corr | Acc | F | AUC
---|---|---|---|---
BLEU@4 | 24.45 | 75.52 | 0.2816 | 52.65
METEOR | 58.48 | 84.23 | 1.1209 | 73.90
ROUGE | 51.11 | 83.40 | 0.7164 | 68.92
SPICE | 59.42 | 84.65 | 1.0374 | 74.43
BS | 57.39 | 85.89 | 1.0660 | 77.93
G SM | 61.70 | 84.65 | 1.2009 | 75.47
G NGM | 60.93 | 86.31 | 0.9770 | 76.75
BLEURT | 70.93 | 90.04 | 2.0280 | 88.02
Table 1: Results comparing GEST representation power with common text
generation metrics applied on stories from Videos-to-Paragraphs test set. Both
text generation metrics and graph similarity function are applied on the
ground truth (stories and graphs). We show in bold the best value for each
metric, and with underline 2nd best. BS stands for BERTScore, G for GEST, corr
for correlation, Acc for Accuracy, F for Fisher score and AUC for the area
under the precision-recall curve. For brevity all (except F) are scaled by
100.

###  4.1 Graph matching similarity metric

Comparing two GEST representations, being graphs, is naturally suited for a
graph matching formulation. we test two graph matching methods, a classical
approach, Spectral Matching (SM) Leordeanu and Hebert (2005) and a modern deep
learning based approach, Neural Graph Matching (NGM) Wang et al. (2021). SM is
a fast, robust and accurate method that uses the principal eigenvector of an
affinity matrix222more details on building the matrix in Appendix, Sec. D.2,
while NGM employs multiple neural networks that learn and transform the
affinity matrix into the association graph, which is further embedded and used
as input for a vertex classifier.

###  4.2 Results and Discussion

Results in Tab. 1 attest the power of our proposed representation: graph
matching in the GEST space outperforms all classic text generation metrics
(i.e. BLEU@4, METEOR and ROUGE) and even modern metrics based on pre-trained
Transformers such as BERTScore. Nevertheless, the specifically and heavily
trained BLEURT metric outperforms all considered metrics on this dataset. Note
that the other metrics all lack access to the sheer amount of data that BLEURT
metric was trained on (around 1.8 million samples). We reckon that given such
data, a trained GRAPH-BLEURT metric could outperform the original BLEURT.

Method | Corr | Acc | F | AUC
---|---|---|---|---
BLEURT | 70.93 | 90.04 | 2.0280 | 88.02
+BLEU@4 | 70.93 | 90.04 | 2.0274 | 88.04
+METEOR | 71.20 | 89.63 | 2.0659 | 87.62
+ROUGE | 70.76 | 90.04 | 1.9973 | 87.71
+SPICE | 71.94 | 88.80 | 2.0808 | 87.71
+BS | 71.11 | 89.63 | 2.0089 | 87.25
+G SM | 72.89 | 90.87 | 2.2086 | 89.80
+G NGM | 71.91 | 90.46 | 2.0537 | 88.58
Table 2: Results comparing the power of BLEURT coupled with common text
generation metrics and GEST, applied on stories from Videos-to-Paragraphs test
set. Text generation metrics are computed on the ground truth stories, while
the GEST similarity (G) with graph matching is computed on GEST learned from
stories. Notations are the same as in Tab. 1.

The initial test show the representational power of GEST, but they do not test
yet the capability of this representation to be combined with a heavily
trained one. That would be another, complementary way, to prove the
effectiveness of GEST. We test this capability by showing that GEST can boost
a state-of-the-art, strongly trained metric, even when we combine the two in
the simplest, linear way. Starting from the original text of the story, we
learn to transform the story automatically into GEST, and then obtain a GEST
similarity score between stories by comparing, using graph matching, the
corresponding generated GESTs. A second, BLEURT score between the stories is
obtained as before. We then learn, on the training set, how to linearly
combine the two scores, to best separate the texts of the same story vs. texts
of different stories. We apply the same procedure to all classic metrics, in
order to evaluate the benefit brought by GEST relative to other methods. We
learn to transform a graph from a story in natural text, by using a sequence-
to-sequence framework, with the story as input and the serialized graph as
output. For further details on the training process see Appendix, Sec. D.2.

In Tab. 2 we show the results of BLEURT (top), those of other metrics combined
with BLEURT using the same linear regression approach (middle) and the results
of GEST (bottom), using the two graph matching methods (SM and NGM). It is
important to note that in combination with other metrics BLEURT does not
always improve, but when combined with GEST it always improves and by the
largest margin. In the Appendix Sec. G, we show cases when BLEURT fails to
predict when two different textual descriptions stem from the same video. In
the first case this is due to the different writing style of the two
annotators, while in the second case BLEURT assigns a high similarity score in
spite of the fact that different actors perform somewhat similar actions. In
both cases, the graph matching algorithm manages to correctly predict if the
two pairs depict the same video. These tests prove the power of GEST: its new
space and associated graph matching metric can be effectively used, with
minimal training cost, to boost the performance of existing state-of-the-art.

##  5 GEST for text generation

Method | B@1$\uparrow$ | B@2$\uparrow$ | B@3$\uparrow$ | B@4$\uparrow$ | M$\uparrow$ | R$\uparrow$ | C$\uparrow$ | BS$\uparrow$ | BT$\uparrow$
---|---|---|---|---|---|---|---|---|---
S2T | 43.81 | 30.95 | 22.87 | 16.90 | 20.15 | 38.87 | 78.60 | 38.87 | 58.28
G2T | 46.73 | 32.90 | 24.23 | 18.15 | 20.88 | 39.57 | 87.29 | 41.24 | 58.73
S2T222 | 42.39 | 30.37 | 22.73 | 17.21 | 20.32 | 39.64 | 96.10 | 40.63 | 57.57
G2T222 | 52.34 | 36.92 | 27.11 | 19.91 | 23.18 | 41.49 | 94.59 | 40.42 | 59.42
Table 3: Results for the task of the text generation on the test set of
Videos-to-Paragraphs dataset, presented using common text generation metrics:
BLEU@N (B@N), METEOR(M), ROUGE(R), CIDEr(C), BERTScore(BS) and BLEURT(BT). In
the S2T (SVOs to text) experiments we trained models that take as input the
SVO sequence, while in the G2T (Graph to text) experiments we give the
serialized graph as input. 222 marks experiments in which we use an additional
training stage with data from bAbI corpus. We highlight with bold the best
value for each metric. For brevity all values are scaled by a factor of 100.

GEST describes the world in terms of events and how they relate in space and
time and could provide a common ground between the real space and time and
"what we say" about it in natural language. Atomic events in a linguistic
story (e.g. SVOs) are also well formed events in real space and time, thus
they provide a direct link between both worlds. Then relations between events
define the space-time structure at semantic level, inevitably becoming a
central component in natural language generation. In the following set of
experiments we want to better understand and evaluate the importance of these
relations, which are an essential component of GEST. We will evaluate the
importantce of these connections between events, by comparing language that is
generated from events only (task S2T - SVOs-to-Text) to language that is
generated from events and their relations, that is full GESTs (G2T - GEST-to-
Text) - for both using the sequence-to-sequence net.

We perform the tests on the Video-to-Paragraphs dataset, where the relations
between events are mainly temporal in nature. Thus, to better highlight the
differences between the textual SVOs and GEST representations we decide to
break the implicit temporal relations given by SVOs ordering, by randomizing
(with the same seed) both representations. In the case of SVOs, the order is
randomized while for the graphs the order of the edges in the representation
is randomized (based on the SVOs permutation). In this setup we can clearly
evaluate the impact of the temporal information encoded in the graph
structure.

###  5.1 Results and Discussion

Results in Tab. 2 validate that GEST is suited for text generation and
provides a better representation than plain textual descriptions of the atomic
events. Conceptually, the graph representation should always be better as it
explicitly encodes complex temporal relations that are not present in SVOs.
Nevertheless this does not directly guarantee a better off the shelf
performance for text generation as the available training data in our tests is
very limited. Our tests show that these limitation is overcome by the power of
the representation. In the first two rows of Tab. 2, both SVOs to text (S2T)
and graph to text (G2T) models are trained starting from a general pre-trained
encoder-decoder model with no previous knowledge of our proposed
representation. Even in this very limited setup (under 900 training samples)
the graph representation proves to be superior. Adding more pretraining data,
using the bAbI corpus only extends the performance gap between the two
approaches (last section of Tab. 2). In the case of bABi we only have access
to a single textual representation for each graph, which is akin to the SVOs
in the Videos-to-Paragraphs dataset. For this reason, the S2T task on bAbI can
be simply solved by using the identity function, while the G2T task can be
solved by describing each node. However they provide valuable aditional
pretraining data, especially for G2T as it helps the model to better
understand and order events in time. The ability to understand and order
events in time enables a better transition from simple sentences to longer,
more complex natural language

##  6 Conclusions

In this paper we introduce GEST, which could set the groundwork for a novel
and universal representation for events and stories. We discuss and motivate
its necessity and versatility, while also empirically validating its practical
value, in comparing and generating stories. Even with very limited data, our
experiments show that GEST is more than fitted for recreating the underlying
story, within a space that allows for very reliable and human correlated
comparisons. This explicit and structured nature of the GEST space lends
itself beautifully to various other uses (e.g. video generation).

GEST aims to bring together vision and language, as a central component in an
explainable space. Such explicit models are largely missing in the literature,
but as we believe that our work demonstrates, they could be useful to better
understand language and also control its relation to the visual world.

##  7 Limitations

Maybe the most important limitation of our work is, for the moment, data
availability. This lack of quality data affects both learning tasks (i.e.
graph-to-text and text-to-graph), as access to more graph-text pairs will
greatly improve performance. We found that this is especially relevant for the
text-to-graph task, as we conjecture that is represents the harder task.
Because we use models that are pre-trained with natural language as input and
output, the graph representation has to be learned and understood by the
encoder (for the graph-to-text task) and the decoder (for the text-to-graph
task). Especially with a limited number of samples, we believe understanding
the new graph representation is easier than generating it. Moreover, for the
text-to-graph task we ask the decoder to generate a very structured output,
defined by a precise grammar.

Our experiments highlighted the power of GEST when applied on real-world
events with temporal relations between events. Crucially, this represents only
a small subset of what GEST can model. Due to lack of data, we are unable in
this work to show the full potential of GEST, namely to represent more
abstract events. For example, a revolution is still an event, but at the same
time a complex story comprised of multiple events.

## References

  * Aditya et al. (2018) Somak Aditya, Yezhou Yang, Chitta Baral, Yiannis Aloimonos, and Cornelia Fermüller. 2018.  Image understanding using vision and reasoning through scene description graph.  _Computer Vision and Image Understanding_ , 173:33–45.
  * Allen (1981) James F Allen. 1981.  An interval-based representation of temporal knowledge.  In _IJCAI_ , volume 81, pages 221–226. Citeseer.
  * Anderson et al. (2016) Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould. 2016.  Spice: Semantic propositional image caption evaluation.  In _Computer Vision–ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part V 14_ , pages 382–398. Springer.
  * Anderson et al. (2018) Peter Anderson, Xiaodong He, Chris Buehler, Damien Teney, Mark Johnson, Stephen Gould, and Lei Zhang. 2018.  Bottom-up and top-down attention for image captioning and visual question answering.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 6077–6086.
  * Aneja et al. (2018) Jyoti Aneja, Aditya Deshpande, and Alexander G Schwing. 2018.  Convolutional image captioning.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 5561–5570.
  * Antol et al. (2015) Stanislaw Antol, Aishwarya Agrawal, Jiasen Lu, Margaret Mitchell, Dhruv Batra, C Lawrence Zitnick, and Devi Parikh. 2015.  Vqa: Visual question answering.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2425–2433.
  * Aoun et al. (2011) Najib Ben Aoun, Haytham Elghazel, and Chokri Ben Amar. 2011.  Graph modeling based video event detection.  In _2011 International Conference on Innovations in Information Technology_ , pages 114–117. IEEE.
  * Balaji et al. (2019) Yogesh Balaji, Martin Renqiang Min, Bing Bai, Rama Chellappa, and Hans Peter Graf. 2019.  Conditional gan with discriminative filter generation for text-to-video synthesis.  In _IJCAI_ , volume 1, page 2.
  * Banarescu et al. (2013) Laura Banarescu, Claire Bonial, Shu Cai, Madalina Georgescu, Kira Griffitt, Ulf Hermjakob, Kevin Knight, Philipp Koehn, Martha Palmer, and Nathan Schneider. 2013\.  Abstract meaning representation for sembanking.  In _Proceedings of the 7th linguistic annotation workshop and interoperability with discourse_ , pages 178–186.
  * Banerjee and Lavie (2005) Satanjeev Banerjee and Alon Lavie. 2005.  METEOR: An automatic metric for MT evaluation with improved correlation with human judgments.  In _Proceedings of the ACL Workshop on Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization_ , pages 65–72, Ann Arbor, Michigan. Association for Computational Linguistics.
  * Bauer et al. (2018) Lisa Bauer, Yicheng Wang, and Mohit Bansal. 2018.  Commonsense for generative multi-hop question answering tasks.  _arXiv preprint arXiv:1809.06309_.
  * Bogolin et al. (2020) Simion-Vlad Bogolin, Ioana Croitoru, and Marius Leordeanu. 2020.  A hierarchical approach to vision-based language generation: from simple sentences to complex natural language.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 2436–2447.
  * Bojar et al. (2017) Ondřej Bojar, Yvette Graham, and Amir Kamran. 2017.  Results of the WMT17 metrics shared task.  In _Proceedings of the Second Conference on Machine Translation_ , pages 489–513, Copenhagen, Denmark. Association for Computational Linguistics.
  * Brendel and Todorovic (2011) William Brendel and Sinisa Todorovic. 2011.  Learning spatiotemporal graphs of human activities.  In _2011 International Conference on Computer Vision_ , pages 778–785. IEEE.
  * Chen and Grauman (2016) Chao Yeh Chen and Kristen Grauman. 2016.  Efficient activity detection in untrimmed video with max-subgraph search.  _IEEE transactions on pattern analysis and machine intelligence_ , 39(5):908–921.
  * Cherian et al. (2022) Anoop Cherian, Chiori Hori, Tim K Marks, and Jonathan Le Roux. 2022.  (2.5+ 1) d spatio-temporal scene graphs for video question answering.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pages 444–453.
  * Christensen et al. (2013) Janara Christensen, Stephen Soderland, Oren Etzioni, et al. 2013.  Towards coherent multi-document summarization.  In _Proceedings of the 2013 conference of the North American chapter of the association for computational linguistics: Human language technologies_ , pages 1163–1173.
  * Clark et al. (2004) Peter Clark, Bruce Porter, and Boeing Phantom Works. 2004.  Km–the knowledge machine 2.0: Users manual.  _Department of Computer Science, University of Texas at Austin_ , 2(5).
  * Culotta and Sorensen (2004) Aron Culotta and Jeffrey Sorensen. 2004.  Dependency tree kernels for relation extraction.  In _Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL-04)_ , pages 423–429.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers)_ , pages 4171–4186. Association for Computational Linguistics.
  * Dong et al. (2017) Hao Dong, Simiao Yu, Chao Wu, and Yike Guo. 2017.  Semantic image synthesis via adversarial learning.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pages 5706–5714.
  * Gao et al. (2017) Lianli Gao, Zhao Guo, Hanwang Zhang, Xing Xu, and Heng Tao Shen. 2017.  Video captioning with attention-based lstm and semantic consistency.  _IEEE Transactions on Multimedia_ , 19(9):2045–2055.
  * Gardent et al. (2017) Claire Gardent, Anastasia Shimorina, Shashi Narayan, and Laura Perez-Beltrachini. 2017.  The WebNLG challenge: Generating text from RDF data.  In _Proceedings of the 10th International Conference on Natural Language Generation_ , pages 124–133, Santiago de Compostela, Spain. Association for Computational Linguistics.
  * Hao et al. (2017) Yanchao Hao, Yuanzhe Zhang, Kang Liu, Shizhu He, Zhanyi Liu, Hua Wu, and Jun Zhao. 2017.  An end-to-end model for question answering over knowledge base with cross-attention combining global knowledge.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 221–231.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_.
  * Leordeanu and Hebert (2005) Marius Leordeanu and Martial Hebert. 2005.  A spectral technique for correspondence problems using pairwise constraints.  In _Tenth IEEE International Conference on Computer Vision (ICCV’05) Volume 1_ , volume 2, pages 1482–1489 Vol. 2.
  * Lewis et al. (2019) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov, and Luke Zettlemoyer. 2019.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  _arXiv preprint arXiv:1910.13461_.
  * Li et al. (2018) Yitong Li, Martin Min, Dinghan Shen, David Carlson, and Lawrence Carin. 2018.  Video generation from text.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 32.
  * Lin (2004) Chin-Yew Lin. 2004.  ROUGE: A package for automatic evaluation of summaries.  In _Text Summarization Branches Out_ , pages 74–81, Barcelona, Spain. Association for Computational Linguistics.
  * Lin (1998) Dekang Lin. 1998.  A dependency-based method for evaluating broad-coverage parsers.  _Natural Language Engineering_ , 4(2):97–114.
  * Lu et al. (2016) Jiasen Lu, Jianwei Yang, Dhruv Batra, and Devi Parikh. 2016.  Hierarchical question-image co-attention for visual question answering.  In _Advances in neural information processing systems_ , pages 289–297.
  * 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.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pages 311–318, Philadelphia, Pennsylvania, USA. Association for Computational Linguistics.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014.  Glove: Global vectors for word representation.  In _Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1532–1543.
  * Reed et al. (2016) Scott Reed, Zeynep Akata, Xinchen Yan, Lajanugen Logeswaran, Bernt Schiele, and Honglak Lee. 2016.  Generative adversarial text to image synthesis.  In _International Conference on Machine Learning_ , pages 1060–1069. PMLR.
  * Ribeiro et al. (2020) Leonardo FR Ribeiro, Martin Schmitt, Hinrich Schütze, and Iryna Gurevych. 2020\.  Investigating pretrained language models for graph-to-text generation.  _arXiv preprint arXiv:2007.08426_.
  * Sai et al. (2022) Ananya B Sai, Akash Kumar Mohankumar, and Mitesh M Khapra. 2022.  A survey of evaluation metrics used for nlg systems.  _ACM Computing Surveys (CSUR)_ , 55(2):1–39.
  * Sellam et al. (2020) Thibault Sellam, Dipanjan Das, and Ankur Parikh. 2020.  BLEURT: Learning robust metrics for text generation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7881–7892, Online. Association for Computational Linguistics.
  * Singer et al. (2022) Uriel Singer, Adam Polyak, Thomas Hayes, Xi Yin, Jie An, Songyang Zhang, Qiyuan Hu, Harry Yang, Oron Ashual, Oran Gafni, et al. 2022.  Make-a-video: Text-to-video generation without text-video data.  _arXiv preprint arXiv:2209.14792_.
  * Singh and Mohan (2017) Dinesh Singh and C Krishna Mohan. 2017.  Graph formulation of video activities for abnormal activity recognition.  _Pattern Recognition_ , 65:265–272.
  * Sridhar et al. (2010) Muralikrishna Sridhar, Anthony G Cohn, and David C Hogg. 2010.  Relational graph mining for learning events from video.  _STAIRS 2010_ , pages 315–327.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in neural information processing systems_ , pages 5998–6008.
  * Vedantam et al. (2015) Ramakrishna Vedantam, C Lawrence Zitnick, and Devi Parikh. 2015.  Cider: Consensus-based image description evaluation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 4566–4575.
  * Villegas et al. (2022) Ruben Villegas, Mohammad Babaeizadeh, Pieter-Jan Kindermans, Hernan Moraldo, Han Zhang, Mohammad Taghi Saffar, Santiago Castro, Julius Kunze, and Dumitru Erhan. 2022.  Phenaki: Variable length video generation from open domain textual description.  _arXiv preprint arXiv:2210.02399_.
  * Wang et al. (2018) Bairui Wang, Lin Ma, Wei Zhang, and Wei Liu. 2018.  Reconstruction network for video captioning.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 7622–7631.
  * Wang et al. (2021) Runzhong Wang, Junchi Yan, and Xiaokang Yang. 2021.  Neural graph matching network: Learning lawler’s quadratic assignment problem with extension to hypergraph and multiple-graph matching.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_.
  * Wang et al. (2019) Xiang Wang, Dingxian Wang, Canran Xu, Xiangnan He, Yixin Cao, and Tat-Seng Chua. 2019.  Explainable reasoning over knowledge graphs for recommendation.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 33, pages 5329–5336.
  * Wang and Gupta (2018) Xiaolong Wang and Abhinav Gupta. 2018.  Videos as space-time region graphs.  In _Proceedings of the European conference on computer vision (ECCV)_ , pages 399–417.
  * Weston et al. (2015) Jason Weston, Antoine Bordes, Sumit Chopra, Alexander M Rush, Bart van Merriënboer, Armand Joulin, and Tomas Mikolov. 2015.  Towards ai-complete question answering: A set of prerequisite toy tasks.  _arXiv preprint arXiv:1502.05698_.
  * Wu et al. (2022) Chenfei Wu, Jian Liang, Lei Ji, Fan Yang, Yuejian Fang, Daxin Jiang, and Nan Duan. 2022.  Nüwa: Visual synthesis pre-training for neural visual world creation.  In _Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XVI_ , pages 720–736. Springer.
  * Wu et al. (2020) Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. 2020.  A comprehensive survey on graph neural networks.  _IEEE transactions on neural networks and learning systems_ , 32(1):4–24.
  * You et al. (2016) Quanzeng You, Hailin Jin, Zhaowen Wang, Chen Fang, and Jiebo Luo. 2016.  Image captioning with semantic attention.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 4651–4659.
  * Yuan et al. (2017) Yuan Yuan, Xiaodan Liang, Xiaolong Wang, Dit-Yan Yeung, and Abhinav Gupta. 2017\.  Temporal dynamic graph lstm for action-driven video object detection.  In _Proceedings of the IEEE international conference on computer vision_ , pages 1801–1810.
  * Zettlemoyer and Collins (2012) Luke S Zettlemoyer and Michael Collins. 2012.  Learning to map sentences to logical form: Structured classification with probabilistic categorial grammars.  _arXiv preprint arXiv:1207.1420_.
  * Zhang et al. (2019) Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q Weinberger, and Yoav Artzi. 2019\.  Bertscore: Evaluating text generation with bert.  _arXiv preprint arXiv:1904.09675_.
  * Zhong et al. (2020) Huasong Zhong, Jingyuan Chen, Chen Shen, Hanwang Zhang, Jianqiang Huang, and Xian-Sheng Hua. 2020.  Self-adaptive neural module transformer for visual question answering.  _IEEE Transactions on Multimedia_ , 23:1264–1273.
  * Zhou et al. (2020) Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. 2020.  Graph neural networks: A review of methods and applications.  _AI Open_ , 1:57–81.
  * Zhou et al. (2018) Luowei Zhou, Yingbo Zhou, Jason J Corso, Richard Socher, and Caiming Xiong. 2018\.  End-to-end dense video captioning with masked transformer.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 8739–8748.
  * Zhou et al. (2019) Xingran Zhou, Siyu Huang, Bin Li, Yingming Li, Jiachen Li, and Zhongfei Zhang. 2019\.  Text guided person image synthesis.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 3663–3672.

##  Appendix A More Examples of GEST

Figure 3 presents an example of automatically generated GEST based on a story
from the bAbI corpus. Furthermore, this example is used to showcase the
spatio-temporal inference (in this particular case only spatial inference)
aspect present in converting textual stories into GEST: the node corresponding
to the sentence "John picked up the football" contains no explicit spatial
information (as the sentence contains no such information), but the location
is inferred from the previous action of entity John.

Figure 3: Automatically generated GEST associated to the following bAbI story:
"John is in the playground. Bob is in the office. John picked up the football.
Bob went to the kitchen.". Notice that the third sentence does not contain any
explicit location. Nevertheless, this location is inferred from the context of
the story and is added in the corresponding node. Also note that for brevity,
we omit some details in the nodes (e.g. timeframe and location for some nodes)
and also add details to emphasize some points (e.g. the "same entity" edges).

##  Appendix B Definition of GEST

Formally, a Graph of Events in Space and Time (GEST) is a graph defined by the
following components:

$V$ = set of event nodes

$E$ = set of edges, $\textbf{E}\bm{\subseteq}\textbf{V X V}$

where

$V_{i}$ = ($action$, $entities$, $location$, $timeframe$, $properties$)

$E_{i}$ = temporal (we use Allen (1981) time interval algebra with minor
modifications for ease of use), spatial (e.g. on top, behind, left of),
logical (e.g. and, or, cause/effect, double implication) or semantic
relations.

Finally, each element of $V_{i}$ is defined as follows:

$action$ = the main action; string

$entities$ = list of entities that are involved in the action; [string]

$location$ = list of locations in which the action takes place; [string]

$timeframe$ = list of timeframes in which the action takes place; [string]

$properties$ = additional properties; dict <property:value>

All elements of $V_{i}$, with the exception of the $properties$ field, can
also refer to other nodes. In particular, in the case of $entities$ we use
references to the "exists" node for each actor or object involved in an action
(this is emphasized by the added dotted lines in the graphical
representation). For complex cases, such as the one presented in Figure 2,
references to other actions can be used in $entitites$ to model complex
interactions (including multiple viewpoints).

Furthermore, our GEST framework is a step-up from the classic Subject-Verb-
Object (SVO) approach. In our case, the Subject becomes an event (even if we
are talking about events of type "exists", they are still events) and also the
Object becomes an event. An event is composed by objects, and any event
requires interaction between objects and the world. As in our formulation
objects are events, any interaction (and so any edge) becomes in itself an
event. This allows a hierarchical and recursive representation in GEST.
Classic models represent object to object interactions, that GEST can easily
represent as well. Moreover, we can go to the next level, modeling hyper-
events, collapsing such interactions to a single node, generating an infinite
recursive process in which nodes expand and collapse into events.

##  Appendix C Building ground truth GEST from text

In the case of bAbI dataset, inferring the location or timeframe in which an
action takes places (for actions that do not explicitly provide this
information) is simply done by memorizing the last place or time in which a
given entity (mainly actor) was found. This simple process works for this
particular dataset as all changes in time or space are explicitly present in
text: each movement of any entity in space is always marked with a sentence
(e.g. John travelled to the kitchen, Mary went to the office), while if
explicit timeframes are mentioned in a sentence, they are mentioned in all
sentences of a given story (this happens for task number 14, the only task in
which timeframes are mentioned). For task number 14 we apply an additional
sorting step before parsing, to ensure that sentences are in chronological
order (i.e. we consider the following chronological order "yesterday", "this
morning", "this afternoon", "this evening" and break ties using the original
order in the story).

While for the bAbI corpus all entities (e.g. actors, objects) are unique for
each story (e.g. a single actor with the name John in each story), in the case
of Videos-to-Pargraphs this is not always the case. In this case we have to
manually intervene and set the proper references (build and link the proper
number of nodes), as different entities are referred with the same name in the
SVOs (e.g. "man", "desk"). To find and accurately annotate these cases we
manually go through each pair of SVOs and story and semantically check their
validity. To ease this process we define a set of personal objects (e.g.
phone, cup, backpack), entities that are intimately linked with their owner.
Unless other specified, all personal objects are unique (in the sense that
each owner has its own unique personal object) and, for example, two phones
linked with different actors (e.g. by the action of "speaking at the phone")
will be represented using two different nodes. We give special attention to
cases in objects (personal or not) are passed around different actors. For
example, for the following set of SVOs "John picks up his backpack. John gives
the backpack to Mary" we will define a single node representing the backpack
and internally keep track of its owner. So if a future SVO (in the same story)
tells that "Mary handed the backpack to Michael" we will not define a new node
and use the reference to the previously defined backpack (as the original
backpack moved from John to Mary to Michael). We are now left with cases in
which the same word, or set of words, refer different entities. In most cases
the telling sign is the presences in the story (not in the SVOs!) of the word
"another". For example if the SVOs are "A man talks at the phone. A man enters
the room." and the story is "A man talks at the phone. After that, another man
enters the room", we will build and use two different nodes (one for each
"man’) to properly represent the story. For these cases we manually annotate
if and where the same word refers to an already existing entity or we have to
build a new one. Nevertheless this happens for around 5% of the entries (i.e.
49 out of 1048).

##  Appendix D Experimental Setup

###  D.1 Text Generation Metrics

For fair comparisons across the paper we employ a board set of text generation
metrics: BLEU Papineni et al. (2002), METEOR Banerjee and Lavie (2005), ROUGE
Lin (2004)333We use the common ROUGE-L variant, CIDEr Vedantam et al. (2015),
SPICE Anderson et al. (2016), BERTScore Zhang et al. (2019)444With the
recommended ”microsoft/deberta-xlarge-mnli” bacbkone and BLEURT Sellam et al.
(2020)555With the recommended ”BLEURT-20” checkpoint. Computing the metrics
was done using coco-captions666https://github.com/tylin/coco-caption last
accessed on 8th of December 2022 for BLEU, METEOR, ROUGE, CIDEr and SPICE, and
official code released by the authors for
BERTScore777https://github.com/Tiiiger/bert_score last accessed on 8th of
December 2022 and BLEURT888https://github.com/google-research/bleurt last
accessed on 8th of December 2022.

###  D.2 GEST as a metric

For this set of experiments we use the Videos-to-Paragraphs dataset, as it
contains multiple annotations (at all levels, graph, SVOs and story) for each
video. We consider triplets that stem from the same video as positive examples
(they provide different representation for the same underlying story presented
in video format), while any other pairs of triplets as negative examples. For
our experiments we consider all positive pairs from the test set (a total of
67 in our case) and 174 negative pairs sampled randomly from the same test
set.

Figure 4: Qualitive example for the story generation task on the test set of
Videos-to-Paragraphs dataset. Both natural (as found in the dataset) and
randomized SVOs are provided in the left and in the right column. S2T
experiments mark models that take as input the SVO sequence (in random order),
while for G2T we give the serialized graph as input (in the same random
order). Note that, while both trained models output the same number of
activities (namely five) the G2T model is capable of better reconstructing the
original order, although not perfectly.

For both SM and NGM algorithms, the affinity matrix is built using both node
and edge level similarity functions that exploit pre-trained word embeddings.
We use pre-trained GloVe Pennington et al. (2014) embeddings of size 300, to
measure the similarity at each level (e.g. action, entities) for nodes. In
order to compare two edges, we integrate node-level similarity (from the nodes
that are connected to the particular edges) with the edge-level similarity
(i.e. the similarity between the edges type). Essentially, two nodes are as
similar as are their actions and entities, while the similarity of two edges
is given by multiplying the edge type (e.g. next, meanwhile) similarity with
the similarity of the corresponding nodes.

For a fair comparison, the graph similarity metrics is normalized as follows:

$\hat{f}(G_{1},G_{2})=\frac{f(G_{1},G_{2})}{\sqrt{f(G_{1},G_{1})*f(G_{2},G_{2})}}$

As we are interested in how similar two human annotated stories/graphs are, we
need to ensure that all used metrics are symmetric. Out of the considered
metrics, only BERTScore and the graph similarity are symmetric by their very
own construction. For all other metrics, we force symmetry by computing the
metric twice for each pair $(s_{1},s_{2})$ (i.e. $metric(s_{1},s_{2})$ and
$metric(s_{2},s_{1})$) and average the results.

For both datasets (i.e. bAbI and Videos-to-Paragraphs) we use the official
train, dev and test splits and follow the standard training procedure (i.e.
training exclusively on the train set until the performance on the dev split
stabilizes and reporting the results on the test set).

For learning to building graphs from raw text, we finetune a GPT3 model (text-
curie-001999https://platform.openai.com/docs/models/gpt-3 last accesed on 8th
of May 2023) on Videos-To-Paragraphs dataset. The model has as input the
textual description (story) and the output is represented by the (serialized)
graph. Finally, we apply a syntactic correction step to ensure that the
generated strings are well formed and therefore can be converted into a GEST.

###  D.3 GEST for text generation

For text generation we invert the inputs and ouputs from the graph-learning
case: the input now is represented by the (serialized) graph, while the output
is the ground truth story. As for the model, we start from a pre-trained BART
Base Lewis et al. (2019) (140M parameters), minimizing the cross-entropy loss
using the Adam optimizer Kingma and Ba (2014), for a maximum number of 100
epochs. We set the base learning rate at 1e-5 and use a warm-up phase that
lasts for 10% of the entire training process. Training is done on six Nvidia
Quadro RTX 5000 graph cards, using an effective batch size of 24 (4 x 6). In
this case, for Videos-to-Paragraphs dataset an epoch took around 45 seconds,
while 11 minutes per epoch were needed for bAbI.

##  Appendix E GEST for text generation

In Figure 4 we present a qualitative example of story generation. This example
highlights several important factors. First, as previously mentioned, the
story part is not just a description of the atomic actions. The ground truth
label for this examples contains only one explicit atomic action present in
the SVOs, the writing in a notebook. The other part of the action, namely
leaving the room is not explicitly present in the SVOs. Nevertheless
preliminary actions, such as packing, standing up, walking are present and
with enough examples a model can (and does!) learn that such actions usually
entail leaving. However, in this particular case, the models are not able to
summarize the actions into a single action (i.e. leaving). The S2T model has
some problems reconstructing the original order of actions and also misjudges
some entities, inverting the bag and the notebook in the picking up and
putting away actions. On the other hand, the G2T model generates a more
coherent order of action that better matches the original order. While better,
the implicit order generated by the G2T model is still not perfect: it
"misses" an action (the second action in the natural order and next to last in
the randomized one). Missing to describe an action does not necessarily
represent an error as it can represent a part of summarization process.

Figure 5: Pair of GEST and text that stem from the same video. Dotted lines
mark matched nodes. GEST graph matching score: 0.3493, prediction: 1. BLEURT
similarity: 0.3755, prediction: 0. Figure 6: Pair of GEST and text that stem
from the different videos. Dotted lines mark matched nodes. GEST graph
matching score: 0.0822, prediction: 0. BLEURT similarity: 0.5625, prediction:
1.

##  Appendix F GEST serialization

In order to be used either as input or output in a training pipeline, the
graph representation needs to be transformed into the format used by the
employed encoder-decoder models. For our case, this is represented by natural
language text. Besides the need to be as close as possible to natural
language, the serialized graph should contain all the information from the
original graph and ensure that the original is recoverable from the serialized
version. Following Ribeiro et al. (2020) and after extensive experimenting
with different serialization methods, we settle for two methodologies, one for
each task (i.e. graph-to-text and text-to-graph). For text-to-graph task we
opt to use a process that generates string that are easier to fix (so they are
sound) and simpler to generate. In the case of graph-to-text generation, we
prefer a richer representation that reduces the number of references, thus
easing the learning process (searching for a particular reference in text
while easy to solve programmatically, is a hard task for Transformer based
encoder-decoder models. Both methodologies (V1 is used for text-to-graph while
V2 for is used for graph-to-text). are depicted on a illustrative example in
Figure 7.

Figure 7: Methodologies for transforming a GEST into a string.

##  Appendix G GEST Graph Mathcing vs BLEURT

In Figures 5 and 6 we present two examples of pairs from the Videos-to-
Paragraphs dataset. In Figure 5, both entries (graph + text) stem from the
same video, information that is reproduced by the graph matching approach.
BLEURT metric fails to capture this information due, most probably, to the
different writing style of the two texts. While the first one is descriptive,
the second one is richer, more complex (e.g. "same empty hall") and
significantly shorter. For the example in Figure 5, BLEURT incorrectly marks
the texts as stemming from the same video. This highlights a limitation of the
metric, as it is fails to understand that while the actions might look
similar, they are still very different, especially when considering they are
performed by different actors. Our approach is not focused exclusively on
actions, as it also take into account the entities involved in a certain
action. The action writing with a pen in a notebook while semantically
similar, is still different from writing on a blackboard. Breaking up the
action and entities involved allows for a finer semantic level of detail, as
we will be comparing actions with actions and entities with entities.

Note that we take a very simple approach to building the affinity matrix, that
coupled with graph matching algorithms does not always yield optimal results.
Furthermore, the metric (affinity matrix and graph matching algorithm) is not
trained or optimized for this task or dataset. Even with this very basic
approach and limited data, we obtain state-of-the-art results for text
similarity, proving the power of GEST. We leave optimizing (e.g. by error
analysis) the affinity matrix and learning the metric for further research.