# ArguSense: Argument-Centric Analysis of Online Discourse

Arman Irani, Michalis Faloutsos, Kevin Esterling

###### Abstract

How can we model arguments and their dynamics in online forum discussions? The
meteoric rise of online forums presents researchers across different
disciplines with an unprecedented opportunity: we have access to texts
containing discourse between groups of users generated in a voluntary and
organic fashion. Most prior work so far has focused on classifying individual
monological comments as either argumentative or not argumentative. However,
few efforts quantify and describe the dialogical processes between users found
in online forum discourse: the structure and content of interpersonal
argumentation. Modeling dialogical discourse requires the ability to identify
the presence of arguments, group them into clusters, and summarize the content
and nature of clusters of arguments within a discussion thread in the forum.
In this work, we develop ArguSense, a comprehensive and systematic framework
for understanding arguments and debate in online forums. Our framework
consists of methods for, among other things: (a) detecting argument topics in
an unsupervised manner; (b) describing the structure of arguments within
threads with powerful visualizations; and (c) quantifying the content and
diversity of threads using argument similarity and clustering algorithms. We
showcase our approach by analyzing the discussions of four communities on the
Reddit platform over a span of 21 months. Specifically, we analyze the
structure and content of threads related to GMOs in forums related to
agriculture or farming to demonstrate the value of our framework.

## Introduction

How can we measure the structure and content of argumentation in online
discourse? This is the question at the heart of our work.

Online platforms and social media serve as a primary venue for discourse over
public policies and other topics in modern society. Social media sites are
said to place users in echo chambers of ideologically like-minded content
(Flaxman, Goel, and Rao 2016), but threads of posts in online discussion
forums often vary in the variety of perspectives and the intensity and
dynamics of argumentation (Friess and Eilders 2015). Given the importance of
idea sharing in online platforms in contemporary society (Sunstein 2017), it
is important to develop measures of the nature and diversity of arguments and
perspectives which users actually observe.

While one can measure many aspects of discourse in online forums, in this
paper we focus specifically on the presence and process of arguments, a
concept of interest that spans the fields of linguistics, communication,
philosophy and political science (Chesñevar et al. 2006). Formally, an
argument is defined as the conjunction of at least one claim with at least one
premise to justify the claim (Yanal 1991). Understanding the arguments posited
in online forums help us to understand not only the opinions users hold on
topics, but also the reasoning for why they hold those opinions (Mercier and
Landemore 2012).

Figure 1: A visual representation of the deliberation of a real Reddit thread
around the GMO debate: 18 posts, 13 aspect-based posts, 7 argumentative posts,
4 different aspects, depth of 7, and a fan out of 7. The color of a node
corresponds to an aspect and the color of the border to the stance towards
that aspect.

Problem Definition: The problem we address in this paper is as follows: how
can we measure the properties of online argumentation effectively around a
topic of interest? Our input is an online forum, The desired output is the
dominant arguments and the interplay of these arguments. The ultimate goal is
to understand the dynamics among the different arguments to discern the
function each argument plays in deliberation. For example, one argument could
be brought up consistently and repeatedly by many different users, while
another argument could be an “ending” argument that is left without a counter
argument in the deliberation (Boschi et al. 2021).

Our work focuses on online discourse on Reddit, which provides certain
challenges for mining arguments since the writing is short and informal
(Dutta, Das, and Chakraborty 2020). Unlike Twitter-like broadcasting,
discussion forums consist of threads, which naturally maps to group
discussion. These discussions may be non-linear, as they might be centered
around a topic set by the first post, but then users are able to splinter off
into ’sub-threads’ where discussion around other topics may occur.

Previous work: In the section on Related Work below, we describe our
relationship to the vast literature on argument mining found in computational
linguistics and computer and social science. In short, while there is a
variety of approaches for classifying and extracting arguments at the
individual or monological level of argumentation (for recent reviews, see
Lawrence and Reed 2020; Schaefer and Stede 2021), there is a relative dearth
of methods for assessing the nature and quality of the dialogical process that
occurs between users, and particularly so for the special case of online
forums (but see Chakrabarty et al. 2020). Below we describe how we leverage
monological methods of unsupervised argument classification to build measures
of the dialogical processes in Reddit threads, and we show how our work is a
complement to related efforts to quantify and describe the dialogical
processes in forums.

Contribution: We develop ArguSense, a systematic framework for quantifying the
extent and nature of argumentation in online discussion forums around a
concept of interest. In a nutshell, ArguSense consumes the unstructured data
of a forum, and outputs meaningful insights as to the intensity and breadth of
arguments in the deliberation of the threads. Our framework consists of the
following synergistic modules, each of which comes with non-trivial technical
challenges: (a) we identify the topical aspects around which arguments are
formed for a concept; (b) we identify the relevant threads to the concept and
aspects of interest; (c) we identify the argument(s) (or lack thereof) in each
post, which includes the main aspect and the stance; (d) we represent the
discussion with an annotated semantically-rich tree and develop metrics to
characterize the deliberation; (e) we provide an intelligent content-aware
method to cluster similar arguments; (f) we propose a measure of deliberative
intensity of threads, which is a weighted sum of the diversity of arguments
and the amount of argumentation within a thread. In each module, we adapt and
customize state-of-the-art methods. However, the key novelty is the seamless
integration of these tools and the overarching conceptual framework of
measuring the nature and extent of argumentation.

We demonstrate the capabilities of ArguSense by applying it to 200,000+ posts
across 21 months of agriculture-focused sub-Reddit forums.

We use the term topic to define a controversial debate, and we consider here
the debate around Genetically Modified Organisms (GMOs). We use the term
aspect to refer to concepts that represent arguments associated with the topic
of interest. For example, the aspects are Monsanto, Climate Change, Soil
Science appear often in a GMO discussion. It is important to note that our
framework can be applied to any topic, especially if that topic can easily be
captured in a small set of keywords. Note that our approach can leverage
keyword expansion methods, and identification of related topics helps to
automate its deployment by minimizing the need for manual input. Some of these
capabilities are discussed later.

We highlight a few of the main observations from our study below.

a. Argumentation happens: 27% of posts contain arguments. We find that across
all the posts of the GMO threads 27% of them contain an argument. At the same
time, posts without an argument may still contribute to the discussion, as
they can convey: (a) agreement or disagreement, or (b) provide information,
e.g., point to a related article.

b. Identifying echo chamber behavior. We observe two phenomena that suggest
the presence and reinforcement of echo chambers: (1) A post is more likely to
reply to a post with the same stance and aspect as them if the argument is
against. Arguments against an aspect have a 19% higher chance of being
responded to by another argument against an aspect. This indicates echo
chambers with against stance arguments occurring. Conversely, in favor aspect
arguments have an equal likelihood of both stances responding, encouraging
cross stance interactions. (2) Arguments In Favor of an aspect are more likely
to be upvoted. Users are considerably more likely to upvote posts with an in
favor argument than an argument against, as seen in Figure 5. This dialogical
behavior promotes the visibility of in favor arguments over against arguments.

c. Users put effort in their arguments: 50% of argumentative posts have more
than 50 words. We observe that argumentative posts represent substantial
effort. This point seems to suggest that online forums could have more
informative discussions, especially if we compare it with posts of other
social media, like Twitter.

d. Deliberation intensity does not increase with the size of the thread.
Observing the diversity of arguments and argument clusters within the
conversation on GMOs allow us to quantify the intensity of deliberation. We
propose a Deliberation Intensity Score metric, DIS, to capture the dynamic
nature of a deliberation. The metric is on a scale from 0 to 1, with 1 being
intensely deliberative. We find 85% of posts have a Deliberation Intensity
Score of 0.2 or less, while only 5% of threads have a Deliberation Intensity
Score of more than 0.5. Contrary to intuition, we find that longer threads do
not exhibit higher Deliberation Intensity Score. This indicates our DIS metric
captures aspects of the intensity of the debate in a way that goes beyond
counting the number of posts. We explain how the DIS metric is calculated in
the Methodology section.

## Data and Definitions

This work will explore the extent and nature of argumentation in online
forums. Therefore, we must define what we mean by “arguments” and we consider
how the environment specific to Reddit influences how arguments are expressed.

What is an Argument? In the field of informal logic, an argument is a
statement that contains a claim supported by at least one premise (Isenmann
and Reuter 1997). For example, an argument might be, (a) pesticides harm the
environment, (b) GMOs reduce pesticide use, and so (c) GMOs are beneficial to
the environment. In this argument, a) and b) are premises, while (c) is a
claim. The three statements taken together can be classified as an argument.
While the claim (c) may appear to be argumentative, without the related
premises, (c) is only an opinion.

Forum | # Threads | # Posts | # Users
---|---|---|---
r/vegetablegardening | 19,249 | 115,914 | 16,995+
r/farming | 12,441 | 69,683 | 11,198+
r/agriculture | 4,525 | 5,876 | 3,035+
r/horticulture | 2,792 | 14,521 | 3,822+
Table 1: Reddit dataset description.

The study of arguments, and their proliferation and diversity, is important in
public opinion research (Mercier and Landemore 2012). In our modern media
landscape, online forums such as Reddit have a significant impact on public
discourse and opinion (Sunstein 2017). Understanding the structures of
communication in these mediums help policymakers and researchers keep up with
rapidly evolving methods of persuasion and debate, and mining forums for the
variety of arguments across topics on a policy issue can be informative to
academics, government officials, media outlets, and the general public about
the diversity of opinions and reasoning within communities of interest.

We should be clear that in this paper, we do not consider the validity of
arguments (see Yanal 1991). An argument is internally invalid if (and only if)
the claims do not follow from the premises, irrespective of whether the
premises are themselves true, such as if statement (c) were rewritten to say
GMOs are harmful to the environment. Importantly, one does not need to agree
with an argument to acknowledge its internal validity. An argument is
externally invalid if (but not only if) the premises are false, for example if
premise (b) was factually inaccurate. Generally speaking, invalid arguments
are a subset of misinformation, the classification of which is outside the
scope of this paper. However, because our methods identify and describe
arguments in unstructured text, our results could help human labelers sift
through text to identify arguments that can be assessed for their validity
(Alnemr 2020).

Online forums: Reddit. We consider Reddit to be a valuable source of
information. It is a popular online deliberation site, where millions of
people come together to share information and opinions. The platform consists
of sub-forums or subreddits, which we can think of as a community. Each
subreddit consists of threads, which function as discussions: a thread can be
started by post of a user. Given the site’s open nature, any user can
participate in any thread within any subreddit. Therefore, there is typically
a diverse range of opinions, beliefs and sub-interests represented. Naturally,
there will be conflict and debate over specific topics and generally these
topics focus on current events of ongoing public interest. A user can express
their support or disagreement towards a post by “upvoting” or “downvoting,”
with the numbers of up and down votes visible for each post. These votes can
be taken as a community-led stamp of credibility and agreement (but see
Ciampaglia et al. 2018).

The GMO debate. Here we focus on the debate around Genetically Modified
Organisms or GMOs. The topics and keywords have been provided by researchers
at our university who study GMOs. We explain later how we identify the related
aspects by combining external input and automatically discovering some
aspects. We list all the topics and aspects in the beginning of our Case Study
section.

Figure 2: Breakdown of Argumentative Posts in our $T_{GMO}$ dataset. Soil
Science dominates the argumentative space, but there remains a relatively
equal distribution of argumentative stance for all GMO aspects.

Our datasets. For our analysis, we use data collected from four subreddit’s,
r/agriculture, r/horticulture, r/vegetablegardening, and r/farming. These four
communities each represent a sector of the industry. r/agriculture consists of
discussion regarding crops and livestock for consumption and the industry
around it. r/horticulture is a science based community that discusses
methodologies behind crop cultivation. r/VegetableGardening contains hobbyists
who engage in conversations regarding small-scale and personal gardening.
r/Farming has a user base of large-scale farmers who specialize in monoculture
farming (barley, wheat, corn, soy), and the techniques and equipment used to
do so. Combined we have a total of 205,000+ posts and 35,000+ unique users
participating in these subreddits between January 2019 and September 2020. For
ease of reference, we can define the following sets of threads:

$T_{all}$: All the threads that we collected from our forums.

$T_{GMO}$: All the threads that we find to be relevant to the GMO debate as we
explain later.

$T_{Long}$: We select the threads in $T_{GMO}$ that have more than 5 posts,
which leads to 586 threads.

$T_{XLong}$: We select the threads in $T_{GMO}$ that have more than 10 posts,
which leads to 74 threads.

Subsetting our data for longer threads creates the opportunity to examine more
extensive discussions, which we want to do when we do argument clustering and
cluster summaries, or assess the Deliberation Intensity Score.

## Methodology

Figure 3: A visual representation of our methodology: the major phases and key
capabilities.

Our methodology consists of many different algorithms and capabilities. For
ease of presentation, we discuss them at three inter-connected levels: (a)
arguments, (b) groups of arguments, and (c) threads. We provide a visual
representation of our methodology in Figure 3.

### A. Our Argument Level Methods

Here we propose measures to mine individual arguments within threads, for now
setting aside the dialogical process between users. Our tasks are to identify
the topic of the threads and to classify posts as either argumentative or not
argumentative.

#### Aspect detection.

As we mentioned in the introduction, we use the term aspect to refer to
concepts that are commonly used in arguments for the topic of interest. In
fact, these aspects can thought of as “anchors” of different arguments. E.g.
the concept “cancer” in a GMO discussion could anchor arguments that claim
that GMOs cause or do not cause cancer. The reason for this is two fold. We
want to use the set of aspects in: (a) identifying relevant threads, and (b)
determining if a post contains an argument. We discuss both these functions
below.

The aspects to a topic can be provided in three ways: (a) given by a domain
expert, (b) identified algorithmically, and (c) both of the above. There are
several methods that can identify aspects related to a topic. A recent method,
Flair (Akbik et al. 2019), is considered the state-of-the-art NLP framework
developed with PyTorch and a pretrained Named Entity Recognition (NER) model,
available under the MIT License, which is shown to perform very well. We use
this method in our study. For initial thread posts, we consider both the title
and content of the post. Using the pretrained NER model, we classify each word
in the post as either a person, location, organization, or other entity.

Identifying topic-relevant threads.  At this stage, we assume that we have the
topic and the aspects of interest. As an optimization step, we focus only on
the threads that are relevant to the discussion to improve performance and
avoid “noise” from irrelevant threads. We therefore select threads that match
our topic of interest as follows. We identify all the likely-relevant posts:
posts that contain words of interest, namely keywords of the topic or the
aspects. We then select the threads that have at least one likely-relevant
post.

Argument and stance identification. Having identified threads of interest, we
classify topic-related posts as making an argument or not making an argument.
As monological argument mining is a relatively established area, we adopt and
use a technique that relies on contextualized BERT-based word embeddings
(Reimers et al. 2019) available under the Apache 2.0 License. For a given set
of aspects, the algorithm classifies the post as: $\\{\mbox{No
Argument},\mbox{Argument For},\mbox{Argument Against}\\}$. Tested on a
publicly available benchmark, this algorithm exhibits superior performance: an
F1 score of 0.6325 compared to 0.3796 of the earlier bilstm model (Stab et al.
2018b).

In an effort to evaluate the effectiveness of the method, we compared the
BERT-based model against ChatGPT (OpenAI 2023). ChatGPT is arguably the most
well-known large language model currently, which has been proven to be able to
understand complex and nuanced natural language with high accuracy. Using the
gold labeled validation data, (therefore unseen by the BERT-based model), the
Reimers et al. (2019) argument classification model had an $F_{1}$ score of
0.6325. On the same data, ChatGPT had an $F_{1}$ score of 0.6330. Furthermore
the Cohen’s Kappa agreement score is 0.4567 indicating a moderate level of
agreement between the two models. We can safely conclude that the argument
classification model we use is performing at the current research and industry
standard. In future works, we will focus on making improvements to this
classification model.

### B. Our Argument Grouping Methods

The goal here is to compare, cluster, and summarize arguments. We specifically
apply these methods to arguments in the discussion forums, but the methods can
operate on any set of arguments.

#### Argument Similarity.

A fundamental capability is to identify posts that establish the same
argument. To measure the similarity of arguments, we adopt and customize a
BERT-based content similarity model which is shown to provide great results
(Reimers et al. 2019). The model is trained on 28 contemporary topics, from
the UKP ASPECT Corpus using a fine-tuned BERT transformer. Upon evaluation,
this method has been shown to achieve an F-score of 0.67 compared to 0.75 for
humans.

Algorithm 1 Argument Clustering

Input: A pair of arguments and their similarity score [0,1]
Parameter: None
Output: [0,n] amount of clusters containing similar arguments

Let $N=0$.

Let similarity_threshold = 0.75

for S1 and S2 in model output do

if S1 & S2 $>=$ similarity_threshold then

if S1 AND S2 not in existing clusters then

Create new cluster and add S1 and S2

$N$+=1

else if S1 in existing cluster but not S2 then

Add S2 to S1’s cluster

else if S2 in existing cluster but not S1 then

Add S1 to S2’s cluster

end if

end if

end for

return N

#### Argument Clustering.

We use the above similarity measure to cluster similar arguments. For a group
of arguments, we iterate through each argument, calculating the similarity to
every other argument. We employ the following logic for the strict
hierarchical clustering of arguments. We choose to derive strict non-
overlapping clusters to get the true diversity of viewpoints. Once we have the
similarity score for every pairwise combination of arguments, we create
cluster of arguments which are similar. The algorithm for this is described in
Algorithm 1.

#### Summarizing clusters of arguments.

Given our clustering, we wish to provide summaries of the substantive content
of each cluster. We use SBERT, a state-of-the-art modified BERT network using
siamese and triple network structures that accurately computes the semantic
meaning of a sentence using sentence embeddings (Reimers and Gurevych 2019).
The evaluation of SBERT reveals significant improvement over state-of-the-art
sentence embeddings such as GloVe embeddings and BERT out-of-the-box
embeddings. Furthermore, SBERT is computationally efficient, performing tasks
55% faster than Universal Sentence Encoder, a necessary requirement for
corpuses as large as ours. Using a pre-trained sentence transformer, every
sentence is converted to a 384 dimensional dense vector space before being
passed through the SBERT summarization model.

### C. Our Thread Level Methods

Having identified arguments and their essence, we can model the deliberation
process at the level of a thread. In other words, we want to capture and
quantify the structure of the dialogical discussion and the interplay of its
arguments.

#### The deliberation profile of a thread.

We propose to profile a thread and its deliberation activity with the
following metrics, some of which will be defined in this section: a) number of
posts, b) argumentative posts, c) depth of thread tree, d) sub-threads, e)
Deliberation Intensity Score. Sub-threads is the number of times a post is
responded to by more than one post.

#### Representing threads using graphs.

A key novelty of our work is the use of semantically-enhanced tree structures
to represent the discussion that unfolds in a thread as shown in Figure 1. It
should be clear that this representation: (a) has significant visual power,
and (b) lends itself to quantifiable metrics leveraging graph theoretic
concepts.

We represent a thread as a directed graph, $G=(V,A)$, where $V$ is a set of
nodes which represent the posts, and $A$ is a set of directed edges. Threads
create a tree structure where each post $p_{2}$ is a response to some previous
post $p_{1}$ in that thread, and we use a directed edge, $(p_{1},p_{2})$ to
connect the two posts. Only the first post that creates the thread does not
have an outgoing edge. Furthermore, a node does not have to have an incoming
edge, in other words a responding post.

Let $v\in V$. We denote the in-degree of node $v$ by deg${}^{-}(v)$ and the
out-degree to be denoted as deg${}^{+}(v)$. In our graph, it is possible to
have nodes that do not have any incoming edges, or any outgoing edges, but can
theoretically have as many as $A$ incoming and zero or one outgoing edges
(posts that start a thread have zero outgoing degrees).

We use the term Fan Out to describe the number of leaves in a tree (thread).
This captures the number of sub-threads or branches of discussion within a
thread. For example, if two posts independently reply to the first post in a
thread the fan out value will be 2. The fan out of the thread in Figure 1 is
7. For visualizing the threads, we use the open-source tool Gephi (Bastian,
Heymann, and Jacomy 2009).

#### Thread Deliberation Intensity.

We next propose a measure of the deliberative intensity of threads.
Intuitively, a thread has higher “deliberative intensity” if it has: (a) a
greater variety of distinct arguments indicated by clusters of arguments, and
(b) a greater number of argumentative posts. We introduce two metrics
$D_{Arg}$ and $D_{Cluster}$ to capture each dimension of deliberation
respectively.

$D_{Cluster}$ $\displaystyle=\frac{\textnormal{\\# Clusters}}{\textnormal{\\#
Arguments}},\begin{aligned} \textnormal{ for \\# Arguments}>0\end{aligned}$
(1) $D_{Arg}$ $\displaystyle=\frac{\textnormal{\\# Arguments}}{\textnormal{\\#
Total Posts}},\begin{aligned} \textnormal{ for \\# Total
Posts}>0\end{aligned}$ (2)

Intuitively, cluster diversity captures the variation of arguments within a
thread as the percentage of arguments that are unique. Similarly, argument
diversity captures the argumentativeness of a thread as the percentage of
posts that are argumentative.

We now define our Deliberation Intensity Score, $DIS$, of a thread by
considering both the above metrics as follows:

$DIS=\sigma_{1}*\textnormal{$D_{Cluster}$}+\sigma_{2}*\textnormal{$D_{Arg}$}$
(3)

Setting a value for the weights $\sigma_{1}$ and $\sigma_{2}$ allows us to put
more emphasis on the diversity of interest. Here, we define their values with
the use of logit functions: $a_{1}=\frac{1}{1+e^{-(\textnormal{\\#
Arguments})}}$ and $a_{2}=\frac{1}{1+e^{-(\textnormal{\\# Total Posts})}}$. We
set $\sigma_{1}=\frac{a_{1}}{a_{1}+a_{2}}$ and
$\sigma_{2}=\frac{a_{2}}{a_{1}+a_{2}}$. The logit functions use the data to
assign weights, with the intuition if the denominator of the ratio increases,
the importance increases. For example, 30% of unique arguments out of 20
arguments is more “important” than the same ratio out of 5 arguments.

#### Identifying important arguments within a thread.

Having a graph representation, we can leverage powerful graph mining
techniques to study the thread. One such application is identifying important
arguments within a thread. Adopting a graph theoretic approach, the importance
of a node in a graph reflects its connectivity: an important node will be
connected to many other important nodes. We propose, PostRank, a modified
version of the PageRank algorithm to identify important nodes (Page et al.
1999). The algorithm works by iteratively calculating the importance of the
node by considering the importance of its neighbor nodes. Another
consideration for PostRank is the bias PageRank will have towards the root
node of trees, as this will always be the source of all incoming edges.

To overcome the issue above, and give more on emphasis on the discourse, we
remove nodes with deg${}^{+}(v)=0$, before running PostRank. The node with the
highest score is the post that spins off more sub-threads, which is an
indication of its impact and importance.

#### Argument Stance Dependence.

We calculate the dependence of argument stances within a thread using the
conditional probability:

$P(B|A)=\frac{P(B\cap A)}{P(A)}$ (4)

Where $P(B|A)$ is the probability of the subsequent B argument stance, given
the previous A argument stance. $P(B\cap A)$ is the probability both stances
occur, while P(A) is the independent probability of argument stance A
occurring.

## Case Study: The GMO Debate on Reddit

Figure 4:  The CCDF of the length of the posts in number of words for
different types argument stance. Interestingly, posts in favor of an aspect
tend to be longer than arguments against an aspect, while posts with no
argument are the shortest.

We demonstrate the kind of results and insights we can get from our approach
by applying it on the Reddit forums that we described earlier.

To showcase the way our approach can be used in practice, we elaborate on the
way we go about defining our topic and identifying its related aspects. Recall
that we are focusing on the GMO debate. We can define the topic as a set of
keywords. Some of the aspects are given by experts, but this is optional. Our
method can identify related aspects in an unsupervised way as we discussed
earlier.

  * •

Topic: GMO, Genetically Modified Organisms

  * •

Aspects:

a. Provided by experts: gene editing, CRISPR, biotechnology, genomics based

b. Identified by ArguSense: Monsanto, China, John Deere, Climate Change, Soil
Science

### Part 1: GMO Arguments and Argument Groups

Here, we study properties of posts and the arguments that these posts may
contain.

Our work is motivated by the intuition that online forums can provide
substantial information on deliberation around a topic of interest. We first
start by making two observations that support this thesis.

Argumentation happens: 27% of posts contain arguments. We find that across all
the posts of the GMO threads 27% of them contain an argument. Arguments are
essential for deliberation. At the same time, posts without an argument may
still provide information, as they can convey: (a) agreement or disagreement,
or (b) provide information, e.g., pointing to a relevant article.

Users put effort in their arguments: 50% of argumentative posts have more than
50 words. We observe that argumentative posts represent substantial effort. We
use the length of the post in number of words as a proxy for the amount of
effort. We plot the distribution of the post length for for non-argumentative,
In Favor argumentative, and Against argumentative posts in Figure 4. We see
that roughly 50% of argumentative posts have more than 50 words. Note that 50
words corresponds111https://numberofwords.com/character-count roughly to 250
characters. As reference a twitter post is currently limited to 280
characters, while its “ideal” range for user engagement is 71-100 characters
(or roughly 20 words) according to marketing studies. We argue that the higher
number of words in the posts indicates more effort, which possibly translates
to more substantiated opinions.

Figure 5: Positive stance posts get more upvotes: Upvote probability distribution based upon the stance of the argument. We do not count the default first upvote that every post on Reddit receives. Post Type | #Posts | Percentage
---|---|---
All | 22,537 | 100%
No Argument | 16,521 | 73%
With Arguments | 6016 | 27%
Arguments For | 3,796 | 17%
Arguments Against | 2,220 | 10%
Table 2: Quantifying argumentation: posts with arguments and further
categorized as having a stance In Favor or Against towards the aspect that the
argument is based on for our $T_{GMO}$ dataset.

#### Argument Upvotes.

We investigate the probability for the number of upvotes each argumentative
post receives, irrespective of their aspect. We discovered posts expressing an
argument In Favor of an aspect have a higher likelihood of obtaining more
upvotes than posts expressing arguments against an aspect.

Upvotes are an important metric to consider, as it is an indirect measure of
how accepted and trustworthy a comment is by users, although the pattern of
upvotes might reflect a kind of bandwagon or herd behavior (Ciampaglia et al.
2018). Furthermore, votes can magnify arguments yet also be tools for
suppression as specific posts and arguments can be targeted, if they go
against the community’s beliefs (Graham and Rodriguez 2021). Therefore, we can
conclude arguments of a positive or favorable stance may unintentionally be
promoted by Reddit’s ecosystem, while arguments being expressed with negative
language are becoming less visible and accepted. This is an important
distinction, as a post can be arguing against a topic while being in support
of social good. For example, “I am against chemicals that cause cancer.”

Identifying important arguments. Recall that our PostRank algorithm can
identify posts that seem to play a critical or central role in their
discussion as captured by the thread. Indicatively, we show results of this
algorithm by listing some of the most influential posts. This capability could
be used to provide a fingerprint of the key posts within a thread and by
extension of a forum.

> “Synthetic fertilizers and excessive tilling caused the dust bowl. I would
> look up no till gardening and stick with natural organic fertilizers. Even
> the guy who created synthetic fertilizers realized it was bad and refused to
> use it but the ease of use trumped all logic so it erupted into what is now
> modern gardening. Even my grandparents used to say organic is not better so
> I would not necessarily trust the old timer methods too much.”

This was correctly classified as an argument against synthetic fertilizers.
The next most important argument made was against GMOs:

> “The only concern I have with GMOs is if they are all the same potentially
> leading to a massive failure of crops should a disease or something hit a
> specific gene of the predominant strain. Kind of like if some disease
> suddenly wiped out all the holsteins the dairy industry would be
> devastated.”

Figure 6: Using the arguments from the thread visualized in Figure 1, we
cluster semantically similar arguments together. The aspects are in bold
italics, green colored texts represent arguments in favor of the aspect, and
text in red represents arguments against the aspect.

Argument Clustering. We use our argument clustering method as described in our
Methodology section. Here we will use our $T_{XLong}$ dataset with 74 threads,
which just so happens to consist of 74 arguments. We run the argument
similarity model across the threads. Then we apply our clustering method to
group similar arguments. This reveals a relatively diverse set of arguments
for GMOs, with 26 distinct clusters out of 74 total arguments If clustering
based on topic and stance, In Favor of arguments for GMOs reveals 14 distinct
clusters with 45 arguments while Against GMO arguments reveals 8 distinct
clusters with 28 total arguments. Proportionally this reveals that In Favor
arguments are more diverse than Against arguments.

Argument Summarization. Once we have identified the most discussed arguments,
and clustered similar arguments together how can we practically gain insight
from what we have found? We propose to include the summarization of our
clusters as an additional step in our framework’s pipeline.

To illustrate this we display one of the summarized clusters for arguments In
Favor of GMOs.

> “If anything, GMO technology has potential to slow this trend down because
> it is much cheaper than traditional breeding which means it much easier for
> smaller players, like universities, to found new companies and increase
> competition innovation.”

Conversely, summarizing of one of the clusters that contain against GMO
arguments yields the following result:

> “Over 80% of genetically modified crops grown worldwide are engineered to
> tolerate being sprayed with glyphosate herbicides, 1 the best known being
> Roundup. Fuck Monsanto, and now Bayer, and i urge any idiot who thinks its
> harmless to get real comfortable with having nonhodgkins lymphoma…”

The motive behind summarizing clusters is to quickly and effectively gain an
understanding about what the general views and arguments are towards
controversial topics. By doing so, policy makers and educators are able to
identify misinformation or calls of concern. Given the two summarized
clusters, we can gain a snapshot into the overarching narratives of the
prevailing arguments.

### Part 2: Deliberation in GMO Threads

Figure 7: The CCDF of the Deliberation Intensity Score distribution for $T_{Long}$ (586 threads that have more than 5 posts.) Dataset | # of Nodes | # of Edges | Avg. Degree | Avg. Tree Depth | Max Tree Depth
---|---|---|---|---|---
$T_{GMO}$ | 22,537 | 13,960 | 0.680 | 1.6 | 12
Table 3: Properties of the graph representations of the threads in our
$T_{GMO}$ dataset.

Here, we apply our methods to modeling the dialogical dynamics of the
deliberation in our online forum. We want to quantify the deliberativeness of
the threads and understand the interplay of arguments in the discussion.

In our $T_{GMO}$ dataset, we have 8,316 threads with 22,537 posts. Additional
properties of this dataset can be seen in Table 3 and recall that we represent
a thread as a tree. For example, we see that the average tree depth is 1.6
while the maximum tree depth is 12.

We want to see the distribution of argumentative posts across the threads. In
Figure 2 we can see the breakdown of the argument stances across all of our
aspects. Soil Science is the aspect with the higher number of arguments, with
more arguments In Favor of the aspect compared to arguments Against.

Modeling the post-response dynamic. A natural question that arises is whether
a correlation exists between arguments and their stance between consecutive
posts in online dialogue. This is a large topic in its own right and here we
will explore only one dimension. Specifically, we focus on the users’ stance
towards the aspect in their post. This analysis focuses on per-post basis,
which may not capture full conversational level nuances.

The formulation for this conditional probability is outlined in our
Methodology section. Applied on our dataset, we observe that if the post is an
argument against an aspect, then there is 59% likelihood of the response also
being an argument against the same aspect compared to 40% probability of being
In Favor. For posts with arguments In Favor of an aspect, the response stance
is equally likely to be in In Favor and Against, the aspect 50% and 49%
respectively.

We can conclude from this that Arguments In Favor of an aspect tend to result
in more stance diverse arguments, while Arguments Against an aspect tend to
create a bias towards more against arguments being generated as responses.

Figure 8: Number of argumentative posts versus the size of the thread and
showing also the line of a Linear Regression fit.

Argumentation and Deliberation. We want to understand which threads are likely
to generate more deliberation. We plot the number of argumentative posts as a
function of the size of the thread in Figure 8. We observe that there is a
loose correlation between the two metrics as indicated by the linear
regression fit with 95% confidence. This is somewhat expected as more posts
are more likely to have more arguments.

Deliberation Intensity Score is not affected by thread size. We arrive at this
counter-intuitive observation by assessing the quality of the deliberation
with our Deliberation Intensity Score. Recall that this metric considers the
percentage of argumentative posts and thus removes the advantage of longer
threads compared to shorter threads. We plot the Deliberation Intensity Score
of threads versus their size in Figure 9: the two metrics are not correlated.
This indicates that there is a hidden variable that our deliberation intensity
score is capturing, and that is the relative intensity of the argumentation
(by considering the percentage of argumentative posts), and the diversity of
these arguments (using the number of argument clusters).

## Discussion: Perspectives and Ethics

Figure 9: The Deliberation Intensity Score as a function of the size of a
thread. There is no clear correlation between thread size and deliberation
intensity, which is rather counter-intuitive. Our initial manual inspection of
large threads and low Deliberation Intensity attributes this phenomenon to the
presence of Question & Answer type discourse. Future work will investigate
these discourse nuances more comprehensively.

Broader perspective: understanding versus polarization. We see our approach as
a significant capability in mining social media. The goal of our work is to
understand discourse: the interaction between users and their arguments at the
level of a discussion. As such, our work leverages and incorporates existing
methods, and its value is that it synthesizes to create a holistic framework
for understanding discourse. We envision our work as an enabling capability
that can: (a) quantify online deliberation, and (b) reveal not only the
opinions that users hold toward policy topics, but also the reasoning for why
they hold those opinions (Mercier and Landemore 2012). Its ideal application
is to help promote dialogue and understanding as a way to bridge differences
in controversial topics (Sunstein 2017). Reducing polarization requires
listening to and understanding the diverse reasons and arguments supporting
different perspectives (Cohen 1989). This helps to ensure all diverse views in
society have a voice, and we can move towards constructive communication.

Having said this, we should stress that technology is ultimately a tool, which
can be used for good or evil: a hammer can be used to build a house or injure
someone. Malicious users can find ways to exploit our framework, including the
ability to identify important arguments, to raise the visibility of morally
objectionable content in order to sow discord or spread their viewpoint.

Applicability and limitations. The applicability of our framework is fairly
wide. It can be used for: (a) a wide range of topics, and (b) most online
discussion forums. Naturally, specific features of a forum or a topic could
limit the type of information that can be extracted. First, our framework
could apply to many topics, especially ones that can be anchored by a set of
keywords. Given one or more keywords that describe a topic of discussion, such
as “abortion,” “police brutality,” “war on Ukraine,” we can use these, or a
union or intersection of these, to identify aspects and arguments around the
topic. In addition, we can use well established keyword-expansion methods to
identify the appropriate keyword sets (Gharibshah et al. 2022). Second, our
framework can apply equally well to all discussion forums or even commenting
platforms. Obviously, the usefulness of our thread-level analysis relies on
the features that we saw in Reddit, which include forums forming communities
of interest, with the post as a well-defined discrete argument unit, and the
opportunity to observe users offering posts in response to other posts. Our
thread-level measures would only apply to other online forums with similar
affordances. Luckily, these features are widely supported by most discussion
platforms. By contrast, some platforms differ in substantial ways. For
example, users are anonymous in some forums like 4chan, which will prohibit a
user-centric analysis of the argumentation.

Going beyond online forums, ArguSense can be used for different sources of
data, such as transcripts of dialogue. In fact, we intend to study
congressional hearings and compare the argumentation differences between
politicians and lay people in online forums.

Public dissemination and open-sourcing. We intend to share our code and
datasets with the research community. We will provide a GitHub repository that
will provide the code, a how-to manual, and select datasets, including our
labeled data, which can greatly facilitate future efforts. We also have a
funded partnership with the news aggregator website AllSides.com to provide
results from our validated methods for the public on a variety of policy
topics.

Beyond English.The current implementation of our framework works on English
text. However, it is easy to see how it can extend to other languages.
Adapting to a new language requires changes in the text processing
capabilities. Specifically, the adaptation is quite straightforward for
alphabet-based languages, as the key thing is to train the models with the new
language. Note that there are BERT models for logographic and other types of
languages such as Chinese(Cui et al. 2021), and Arabic (Antoun, Baly, and Hajj
2020).

Accuracy and biases. The effectiveness of our framework relies on several
factors. First, the quality of the data is a critical factor, as poorly
written posts and badly formed statements can become impediments. Second, our
approach relies on the effectiveness of the methods that we deploy in each
step of our pipeline. The positive view here is that as better methods emerge,
we can incorporate them in our framework and benefit from them. Third, the
keyword selection, which we consider as an input, can introduce biases or
limit the representativeness of a study.

Ethical Considerations. Our work follows ethical guidelines as specified by
the AAAI code of conduct and ethics. First, the data that we collected is
publicly available: anyone can access the discussions on Reddit and users know
that their comments are visible by anyone who visits the platform.
Furthermore, IRBs do not require informed consent for data collection (Vitak
et al. 2017). Second, all the data is anonymized, and any metadata linking to
personal identifiable information was removed in the preprocessing stage.
Finally, all reported data is aggregated in a way that there are no users
identified by name.

## Related Work

While there is extensive work developing methods for unsupervised topic and
argument mining, most of this work centers on classifying arguments in an
individual’s monological speech or writing. By contrast, our work leverages
monological classifiers to measure the inter-user dialogical process within
online forums. Our work differs from the majority of previous efforts by
virtue of its focus that rests at the intersection of: (a) online forums, (b)
argument extraction, and (c) quantifying and assessing the dialogical process
of argumentation within and between forum threads.

For recent reviews of argument mining, see Lawrence and Reed (2020) and
Schaefer and Stede (2021). There is a vast literature in computational
linguistics and computer science centered on mining of monological arguments
from a variety of corpuses, including structured text such as legal writing
(Palau and Moens 2009), news articles (Ein-Dor et al. 2020; Slonim et al.
2021), and student essays (Stab and Gurevych 2017), as well as unstructured
text mostly from web-scraped or Wikipedia data (Reimers et al. 2019; Chernodub
et al. 2019; Daxenberger et al. 2020; Habernal and Gurevych 2017; Stab et al.
2018a).

Within the field of argument and stance detection there are several works
utilizing NLP to classify different niche grammatical devices. Liu et al.
(2022) uses pretrained language models to characterize and predict ideologies
across different genres of text. Zhang et al. (2022) uses graph neural
networks to classify political perspectives. Conforti et al. (2022) uses
multi-genre stance detection for financial signaling. Sia et al. (2022) uses a
constraint based modeling approach to predict the winning argument in Reddit
debate datasets.

There are relatively few efforts however, to leverage these monological
classifiers to measure and assess the dialogical process of argumentative
discourse in online forums like Reddit using unsupervised methods. At the
dialogical level, much of the work measuring the nature and quality of
argumentation in social science and communication uses either hand coding or
semi-supervised methods to assess transcripts of speeches (such as Fournier-
Tombs and Di Marzo Serugendo 2020). Most similar to our work is Chakrabarty et
al. (2020) who identify intra-turn argument relations between posts on Reddit,
which we complement by proposing macro-level measures of the nature and
quality of the dialogical argumentative process within and between threads. We
note other papers making use of argument extraction graph representation (for
example Sakai et al. 2021) and that leverage topic and stance detection and
other tools from opinion mining (Stede 2020). Dialogical methods for assessing
the persuasiveness of arguments (such as Boschi et al. 2021; Dutta, Das, and
Chakraborty 2020) are complementary to our work but outside of the scope of
this paper.

## Conclusion

The key contribution of our work is ArguSense, a comprehensive and systematic
approach for modeling deliberation in online forums. The approach consists of
many capabilities that rely on specific model and metric definitions.
Specifically, we develop methods: (a) detecting argumentative posts; (b)
describing the structure of arguments within threads with powerful
visualizations; and (c) summarizing and clustering arguments, and (d)
quantifying the deliberation diversity of threads.

We conduct a substantial study, where we apply our approach on four
communities on the Reddit platform over a span of 21 months which produced
more than 200K posts and more than 35K users. We focus on the GMO debate in
order to have a long lasting and reasonably controversial topic. We find that
27% of posts contain arguments and these posts are often fairly long.

Our observations suggest that there is substantial dialogue that happens in
these forums. We qualify this, although we note that we selected threads that
relate to a controversial topic. Nevertheless, the case study demonstrates the
opportunity our methods present to mine dialogical argumentation as
researchers and institutions an gain insights into not only the opinions
people hold, but also how people reason about a topic in terms of both
arguments and how they debate their position.

Future Work. Encouraged by this initial study, we intend to extend our work in
two different directions. First, we will improve, expand and fine-tune our
methodology. Second, we will expand our study to: (a) more topics, and (b)
more online discussion forums.

## Acknowledgments

This work was supported by NSF SaTC Grant No. 2132642. and CDFA grant 2021
Specialty Crop Block Grant Program H.R. 133 No. 000705282.

## References

  * Akbik et al. (2019) Akbik, A.; Bergmann, T.; Blythe, D.; Rasul, K.; Schweter, S.; and Vollgraf, R. 2019.  FLAIR: An easy-to-use framework for state-of-the-art NLP.  In _NAACL 2019, 2019 Annual Conference of the North American Chapter of the Association for Computational Linguistics (Demonstrations)_ , 54–59.
  * Alnemr (2020) Alnemr, N. 2020.  Emancipation cannot be programmed: blind spots of algorithmic facilitation in online deliberation.  _Contemporary Politics_ , 26(5): 531–552.
  * Antoun, Baly, and Hajj (2020) Antoun, W.; Baly, F.; and Hajj, H. 2020.  AraBERT: Transformer-based Model for Arabic Language Understanding.  In _LREC 2020 Workshop Language Resources and Evaluation Conference 11–16 May 2020_ , 9.
  * Bastian, Heymann, and Jacomy (2009) Bastian, M.; Heymann, S.; and Jacomy, M. 2009.  Gephi: An Open Source Software for Exploring and Manipulating Networks.  _Proceedings of the International AAAI Conference on Web and Social Media_ , 3(1): 361–362.
  * Boschi et al. (2021) Boschi, G.; Young, A. P.; Joglekar, S.; Cammarota, C.; and Sastry, N. 2021.  Who Has the Last Word? Understanding How to Sample Online Discussions.  _ACM Trans. Web_ , 15(3): 1–25.
  * Chakrabarty et al. (2020) Chakrabarty, T.; Hidey, C.; Muresan, S.; Mckeown, K.; and Hwang, A. 2020.  AMPERSAND: Argument Mining for PERSuAsive oNline Discussions.  _Working Paper_.
  * Chernodub et al. (2019) Chernodub, A.; Oliynyk, O.; Heidenreich, P.; Bondarenko, A.; Hagen, M.; Biemann, C.; and Panchenko, A. 2019.  TARGER: Neural Argument Mining at Your Fingertips.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics: System Demonstrations_ , 195–200. Florence, Italy: Association for Computational Linguistics.
  * Chesñevar et al. (2006) Chesñevar, C.; Mcginnis; Modgil, S.; Rahwan, I.; Reed, C.; Simari, G.; South, M.; Vreeswijk, G.; and Willmott, S. 2006.  Towards an argument interchange format.  _Knowl. Eng. Rev._ , 21(4): 293–316.
  * Ciampaglia et al. (2018) Ciampaglia, G. L.; Nematzadeh, A.; Menczer, F.; and Flammini, A. 2018.  How algorithmic popularity bias hinders or promotes quality.  _Sci. Rep._ , 8(1): 15951.
  * Cohen (1989) Cohen, J. 1989.  _Deliberation and Democratic Legitimacy_ , 17–34.  Basil Blackwell.
  * Conforti et al. (2022) Conforti, C.; Berndt, J.; Pilehvar, M. T.; Giannitsarou, C.; Toxvaerd, F.; and Collier, N. 2022.  Incorporating Stock Market Signals for Twitter Stance Detection.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , 4074–4091.
  * Cui et al. (2021) Cui, Y.; Che, W.; Liu, T.; Qin, B.; and Yang, Z. 2021.  Pre-Training With Whole Word Masking for Chinese BERT.  _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , 29: 3504–3514.
  * Daxenberger et al. (2020) Daxenberger, J.; Schiller, B.; Stahlhut, C.; Kaiser, E.; and Gurevych, I. 2020.  ArgumenText: Argument Classification and Clustering in a Generalized Search Scenario.  _Datenbank-Spektrum_ , 20(2): 115–121.
  * Dutta, Das, and Chakraborty (2020) Dutta, S.; Das, D.; and Chakraborty, T. 2020.  Changing views: Persuasion modeling and argument extraction from online discussions.  _Inf. Process. Manag._ , 57(2): 102085.
  * Ein-Dor et al. (2020) Ein-Dor, L.; Shnarch, E.; Dankin, L.; Halfon, A.; Sznajder, B.; Gera, A.; Alzate, C.; Gleize, M.; Choshen, L.; Hou, Y.; Bilu, Y.; Aharonov, R.; and Slonim, N. 2020.  Corpus Wide Argument Mining—A Working Solution.  _AAAI_ , 34(05): 7683–7691.
  * Flaxman, Goel, and Rao (2016) Flaxman, S.; Goel, S.; and Rao, J. M. 2016.  Filter Bubbles, Echo Chambers, and Online News Consumption.  _Public Opin. Q._ , 80(S1): 298–320.
  * Fournier-Tombs and Di Marzo Serugendo (2020) Fournier-Tombs, E.; and Di Marzo Serugendo, G. 2020.  DelibAnalysis: Understanding the quality of online political discourse with machine learning.  _J. Inf. Sci. Eng._ , 46(6): 810–822.
  * Friess and Eilders (2015) Friess, D.; and Eilders, C. 2015.  A systematic review of online deliberation research.  _Policy Internet_ , 7(3): 319–339.
  * Gharibshah et al. (2022) Gharibshah, J.; Tachaiya, J.; Irani, A.; Papalexakis, E. E.; and Faloutsos, M. 2022.  IKEA: Unsupervised domain-specific keyword-expansion.  In _IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2022, Istanbul, Turkey, November 10-13, 2022_ , 496–503. IEEE.
  * Graham and Rodriguez (2021) Graham, T.; and Rodriguez, A. 2021.  The Sociomateriality of Rating and Ranking Devices on Social Media: A Case Study of Reddit’s Voting Practices.  _Social Media+ Society_ , 7(3): 20563051211047667.
  * Habernal and Gurevych (2017) Habernal, I.; and Gurevych, I. 2017.  Argumentation mining in user-generated Web discourse.  _Comput. Linguist. Assoc. Comput. Linguist._ , 43(1): 125–179.
  * Isenmann and Reuter (1997) Isenmann, S.; and Reuter, W. D. 1997.  IBIS—a convincing concept…but a lousy instrument?  In _Proceedings of the conference on Designing interactive systems processes, practices, methods, and techniques - DIS ’97_. New York, New York, USA: ACM Press.
  * Lawrence and Reed (2020) Lawrence, J.; and Reed, C. 2020.  Argument mining: A survey.  _Comput. Linguist. Assoc. Comput. Linguist._ , 45(4): 765–818.
  * Liu et al. (2022) Liu, Y.; Zhang, X. F.; Wegsman, D.; Beauchamp, N.; and Wang, L. 2022.  POLITICS: pretraining with same-story article comparison for ideology prediction and stance detection.  _arXiv preprint arXiv:2205.00619_.
  * Mercier and Landemore (2012) Mercier, H.; and Landemore, H. 2012.  Reasoning is for arguing: Understanding the successes and failures of deliberation.  _Polit. Psychol._ , 33(2): 243–258.
  * OpenAI (2023) OpenAI. 2023.  GPT-4 Technical Report.  arXiv:2303.08774.
  * Page et al. (1999) Page, L.; Brin, S.; Motwani, R.; and Winograd, T. 1999.  The PageRank Citation Ranking: Bringing Order to the Web.  Technical Report 1999-66, Stanford InfoLab.  Previous number = SIDL-WP-1999-0120.
  * Palau and Moens (2009) Palau, R. M.; and Moens, M.-F. 2009.  Argumentation mining: the detection, classification and structure of arguments in text.  In _Proceedings of the 12th International Conference on Artificial Intelligence and Law_ , ICAIL ’09, 98–107. New York, NY, USA: Association for Computing Machinery.
  * Reimers and Gurevych (2019) Reimers, N.; and Gurevych, I. 2019.  Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks.
  * Reimers et al. (2019) Reimers, N.; Schiller, B.; Beck, T.; Daxenberger, J.; Stab, C.; and Gurevych, I. 2019.  Classification and Clustering of Arguments with Contextualized Word Embeddings.
  * Sakai et al. (2021) Sakai, A.; Suzuki, S.; Hadfi, R.; and Ito, T. 2021.  Extracting Issue-Based Information System Structures from Online Discussions for Automated Facilitation Agent.  _The 16TH International Conference on Knowledge, Information and Creativity Support Systems_.
  * Schaefer and Stede (2021) Schaefer, R.; and Stede, M. 2021.  Argument Mining on Twitter: A survey.  _IT - Information Technology_ , 63(1): 45–58.
  * Sia et al. (2022) Sia, S.; Jaidka, K.; Ahuja, H.; Chhaya, N.; and Duh, K. 2022.  Offer a Different Perspective: Modeling the Belief Alignment of Arguments in Multi-party Debates.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , 11939–11950.
  * Slonim et al. (2021) Slonim, N.; Bilu, Y.; Alzate, C.; Bar-Haim, R.; Bogin, B.; Bonin, F.; Choshen, L.; Cohen-Karlik, E.; Dankin, L.; Edelstein, L.; Ein-Dor, L.; Friedman-Melamed, R.; Gavron, A.; Gera, A.; Gleize, M.; Gretz, S.; Gutfreund, D.; Halfon, A.; Hershcovich, D.; Hoory, R.; Hou, Y.; Hummel, S.; Jacovi, M.; Jochim, C.; Kantor, Y.; Katz, Y.; Konopnicki, D.; Kons, Z.; Kotlerman, L.; Krieger, D.; Lahav, D.; Lavee, T.; Levy, R.; Liberman, N.; Mass, Y.; Menczel, A.; Mirkin, S.; Moshkowich, G.; Ofek-Koifman, S.; Orbach, M.; Rabinovich, E.; Rinott, R.; Shechtman, S.; Sheinwald, D.; Shnarch, E.; Shnayderman, I.; Soffer, A.; Spector, A.; Sznajder, B.; Toledo, A.; Toledo-Ronen, O.; Venezian, E.; and Aharonov, R. 2021.  An autonomous debating system.  _Nature_ , 591(7850): 379–384.
  * Stab et al. (2018a) Stab, C.; Daxenberger, J.; Stahlhut, C.; Miller, T.; Schiller, B.; Tauchmann, C.; Eger, S.; and Gurevych, I. 2018a.  ArgumenText: Searching for Arguments in Heterogeneous Sources.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Demonstrations_ , 21–25. Stroudsburg, PA, USA: Association for Computational Linguistics.
  * Stab and Gurevych (2017) Stab, C.; and Gurevych, I. 2017.  Parsing argumentation structures in persuasive essays.  _Comput. Linguist. Assoc. Comput. Linguist._ , 43(3): 619–659.
  * Stab et al. (2018b) Stab, C.; Miller, T.; Schiller, B.; Rai, P.; and Gurevych, I. 2018b.  Cross-topic Argument Mining from Heterogeneous Sources.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , 3664–3674. Brussels, Belgium: Association for Computational Linguistics.
  * Stede (2020) Stede, M. 2020.  Automatic argumentation mining and the role of stance and sentiment.  _Journal of Argumentation in Context_ , 9(1): 19–41.
  * Sunstein (2017) Sunstein, C. R. 2017.  _#Republic: Divided Democracy in the Age of Social Media_.  Princeton University Press.
  * Vitak et al. (2017) Vitak, J.; Proferes, N.; Shilton, K.; and Ashktorab, Z. 2017.  Ethics regulation in social computing research: Examining the role of institutional review boards.  _Journal of Empirical Research on Human Research Ethics_ , 12(5): 372–382.
  * Yanal (1991) Yanal, R. J. 1991.  Dependent and Independent Reasons.  _IL_ , 13(3).
  * Zhang et al. (2022) Zhang, W.; Feng, S.; Chen, Z.; Lei, Z.; Li, J.; and Luo, M. 2022.  KCD: Knowledge walks and textual cues enhanced political perspective detection in news media.  _arXiv preprint arXiv:2204.04046_.


# Temporalizing digraphs via linear-size balanced bi-trees

Stéphane Bessy  LIRMM, Univ Montpellier, CNRS, Montpellier, France  Stéphan
Thomassé  Univ Lyon, EnsL, UCBL, CNRS, LIP, F-69342, LYON Cedex 07, France
Laurent Viennot  Inria Paris, Irif, Université Paris Cité

###### Abstract

In a directed graph $D$ on vertex set $v_{1},\dots,v_{n}$, a _forward arc_ is
an arc $v_{i}v_{j}$ where $i<j$. A pair $v_{i},v_{j}$ is _forward connected_
if there is a directed path from $v_{i}$ to $v_{j}$ consisting of forward
arcs. In the Forward Connected Pairs Problem (FCPP), the input is a strongly
connected digraph $D$, and the output is the maximum number of forward
connected pairs in some vertex enumeration of $D$. We show that FCPP is in
APX, as one can efficiently enumerate the vertices of $D$ in order to achieve
a quadratic number of forward connected pairs. For this, we construct a linear
size balanced bi-tree $T$ (an out-tree and an in-tree with same size which
roots are identified). The existence of such a $T$ was left as an open problem
motivated by the study of temporal paths in temporal networks. More precisely,
$T$ can be constructed in quadratic time (in the number of vertices) and has
size at least $n/3$. The algorithm involves a particular depth-first search
tree (Left-DFS) of independent interest, and shows that every strongly
connected directed graph has a balanced separator which is a circuit.
Remarkably, in the request version RFCPP of FCPP, where the input is a strong
digraph $D$ and a set of requests $R$ consisting of pairs $\\{x_{i},y_{i}\\}$,
there is no constant $c>0$ such that one can always find an enumeration
realizing $c.|R|$ forward connected pairs $\\{x_{i},y_{i}\\}$ (in either
direction).

##  1 Introduction

Motivated by network design applications, the following problem of scheduling
the arcs of a multi-digraph was mentioned as an open problem in [6] and
formally introduced in [1]. The Maximum Reachability Edge Temporalisation
(MRET) consists in assigning a time label $t_{xy}\in\mathbb{N}$ to each arc
$xy$ of a digraph $D=(V,A)$ so as to maximize the number of pairs $x,z$ of
vertices connected by a _temporal path_ , that is a path from $x$ to $z$ where
time labels strictly increase along the path. In the acyclic case, all
existing paths can be made temporal using a topological order of the vertices,
and transferring the index of a node $x$ to every arc leaving $x$. The problem
becomes particularly intriguing in the strongly connected case in which every
pair of vertices are connected by a path. It was shown in [1] that MRET is NP-
hard even restricted to strongly connected digraphs. In the same paper, the
authors suggest that MRET is in APX by conjecturing, in any strongly connected
digraph, the existence of some arc-disjoint in-branching $T^{-}$ and out-
branching $T^{+}$, both with linear size and rooted at the same vertex $r$.

We show that this conjecture holds, and since the branchings can be
constructed in polynomial time, that MRET is indeed in APX. The reason is that
given such branchings $T^{-}$ and $T^{+}$, it is then straightforward to
schedule the arcs of $T^{-}$ from leaves to $r$, and then the arcs of $T^{+}$
from $r$ to leaves, to obtain an arc scheduling temporally connecting
$|T^{-}|\cdot|T^{+}|$ pairs of vertices. If both branchings span a fraction
$c$ of vertices, for some $c>0$, then this scheduling temporally connects at
least a fraction $c^{2}$ of all pairs which guarantees approximation ratio at
most $1/c^{2}$.

#### Related work

The undirected version of the MRET problem is studied in [8] where it is
proven that it is NP-complete to decide whether an undirected graph has an
edge scheduling connecting all pairs. However, one can easily produce an edge
scheduling connecting a constant fraction of pairs by decomposing a spanning
tree at a centroid $c$ so as to produce two disjoint trees $T,T^{\prime}$ with
the same root $c$ and each of them covering one third of the vertices. It is
then straightforward to schedule edges so as to connect a constant fraction of
pairs. A similar problem where an edge can be scheduled several times is
considered in [9]. The goal is then to minimize the total number of time
labels used while respecting some connectivity constraints. Note that
scheduling each edge twice is sufficient for temporally connecting every pair
of nodes of a connected graph. The MRET problem can be seen as a simplified
version of the problem of scheduling buses in a public transit network [6].
Related problems [7, 10] target the minimization of temporally connected pairs
and are driven by applications to mitigation of epidemic propagation.

It is shown in [2] that it is NP-complete to decide whether a strongly
connected digraph contains an in-branching and an out-branching with same
root, which are edge disjoint, and that both span all vertices. The same paper
also relates the conjecture that such branchings exist if the digraph is
$c$-edge-connected for sufficiently large $c$. The conjecture holds for $c=2$
in digraphs with independence number at most 2 [3]. It is also shown in [4]
that it is NP-complete to decide whether a strongly connected digraph has a
partition of its vertices into two parts of size at least 2, such that the
first part is spanned by an in-branching and the second part is spanned by an
out-branching.

#### Main results

Our approach is to address these problems from a vertex point of view, which
is enough to obtain an approximation algorithm for MRET. Specifically, we
consider two maximization problems: In the Forward Connected Pairs Problem
(FCPP) the goal is to find an enumeration $v_{1},\dots,v_{n}$ of a strongly
connected digraph $D=(V,A)$ such that the number of pairs $v_{i},v_{j}$ joined
by a directed path with increasing indices (called _forward pairs_) is
maximized. In the Balanced Bi-Tree Problem (BBTP) the goal is to find an in-
tree and an out-tree only intersecting at their root (thus making a _bi-tree_)
with equal size (to be maximized).

The main result of this paper is that one can find a solution $T$ of BBTP in
time $O(n^{2})$ with size at least $n/3-1$. Therefore each in-tree and out-
tree has size at least $n/6$, and by considering any enumeration of $V$
extending a topological order of $T$, we obtain a solution of FCPP of size at
least $n^{2}/36$. Since the maximum possible solution of FCPP is $n^{2}/2$,
this gives a $1/18$ approximation for the Forward Connected Pairs Problem. Our
construction can be extended to a weighted digraph where each vertex $u$ is
associated to a weight $w_{u}$. It then produces a bi-tree where the in-tree
and the out-tree both have total weight at least $W/6$, where $W=\sum_{u\in
V}w_{u}$ is the total weight of the digraph.

We also consider a covering version CFCPP of FCPP where we look for a minimal
set of orderings of the vertex set such that for every pair $x,y$, one of $xy$
or $yx$ is a forward pair in one of the orders. Since we can cover a positive
fraction of pairs, it is natural to wonder if CFCPP has a constant solution
(or at most $\log n$). To this end, we consider a request variant of the
problem, called RFCPP, where we ask to connect by forward paths a maximum
number of pairs among a given set $R\subseteq{V\choose 2}$ of requested pairs.
We provide a family of instances showing that RFCPP is not at least a constant
fraction of $|R|$. We do not know if CFCPP and RFCPP can be efficiently
approximated. This still leaves open the existence of an $O(\log n)$ solution
for CFCPP.

#### Main techniques: Left-DFS and balanced circuit separators

From an algorithmic perspective, our solution relies on finding a _cyclic
balanced separator_ $C$ of $D$. Specifically, the vertex set of $D$ is
partitioned into three parts $I,C,O$ such that $C$ spans a circuit, no arc
links a node from $I$ to a node in $O$, and which is balanced in the sense
that both $I\cup C$ and $C\cup O$ have size at least $n/3$. Note that $I$ and
$O$ can be empty, as this is the case when $D$ is a circuit.

Such a partition can be computed in linear time from a left-maximal depth-
first-search (DFS) tree, that is a DFS tree such that the children of any node
are ordered from left-to-right by non-increasing sub-tree size. Both of these
structures could be of independent interest in the field of digraph
algorithms. The computation of the left-DFS is the (quadratic) complexity
bottleneck of our algorithm. We feel that a linear algorithm for finding a
cyclic balanced separator should be achievable either by other means, or by
relaxing the requirement on left-maximal DFS (we just need it to be ”not too
much unbalanced to the right”). However, actually computing in linear time a
left-maximal DFS tree could prove more challenging. Could decremental SCC help
[5]?

##  2 Definitions

In this paper we consider directed graphs $D=(V,A)$ (_digraphs_) in which
cycles of length two are allowed. The set $V$ is the set of _vertices_
(usually $n$ of them) and $A$ is the set of _arcs_. We say that $x,y$ are
_connected_ in $D$ if there exists a directed path from $x$ to $y$. A digraph
is _strongly connected_ , or simply _strong_ , if all $x,y$ are connected. In
particular, if $D$ has $n$ vertices, the number of connected couples $x,y$ is
$n^{2}$. The _out-section_ generated by a vertex $x$ of $D$ is the set of
vertices $y$ for which $x,y$ are connected. We say that $x$ _out-generates_
$D$ if the out-section of $x$ is $V$.

A _schedule_ is an injective mapping $f$ of $A$ into the positive integers. In
a scheduled digraph $(D,f)$ we say that a couple of vertices $x,y$ is
_connected_ if there is a directed path $x=x_{1},x_{2},\dots,x_{k}=y$ such
that $f(x_{i}x_{i+1})<f(x_{i+1}x_{i+2})$ for all $i=1,\dots,k-2$. We denote by
$c(D,f)$ the number of connected couples and by $s(D)$ the maximum over all
choices of $f$ of $c(D,f)$. We now define our scheduled ratio $r_{s}$ which is
the infimum of $s(D)/n^{2}$ over strongly connected digraphs $D$ on $n$
vertices, when $n$ goes to infinity.

This ratio $r_{s}$ is based on scheduling arcs, and a similar ratio $r_{t}$
can be defined via a total order on vertices. We consider for this a digraph
$D$ and a total ordering $<$ on its vertices. An arc $xy$ of $D$ is _forward_
if $x<y$. We say that a couple $(x,y)$ is _connected_ in $(D,<)$ if there is a
directed path from $x$ to $y$ consisting of forward arcs, and we then call
$(x,y)$ a _forward couple_. We denote by $c(D,<)$ the number of forward
couples and by $t(D)$ the maximum over all choices of $<$ of $c(D,<)$. The
ordered ratio $r_{t}$ is the infimum of $t(D)/n^{2}$ over strongly connected
digraphs $D$ on $n$ vertices, when $n$ goes to infinity.

The main problem we address in this paper is to show that both $r_{s}$ and
$r_{t}$ are positive. Let us first prove that these questions are related.

###### Theorem 1

$r_{t}\leq r_{s}$

Proof. Given $(D,<)$, we can consider that $<$ is a bijective mapping $g$ from
$V$ to $0,\dots,n-1$ respecting the order (that is $x<y$ whenever
$g(x)<g(y)$). Now observe that if one define $f(xy)=n.g(x)+g(y)$ for every
arc, then every forward couple in $(D,<)$ is a connected pair in $(D,f)$.

Thus we can focus on the following problem.

###### Problem 1

What is the value of $r_{t}$?

The fact that $r_{t}>0$ is not obvious and is indeed our central result.
Observe that we can assume that $D$ is _minimally strongly connected_ , i.e.
every arc $xy$ of $D$ is the unique directed $x,y$-path in $D$. A classical
result using ear-decompositions asserts that the number of arcs of a minimally
strongly connected digraph is at most $2n-2$. Unfortunately we were unable to
use these decompositions to prove the positivity of $r_{t}$. Our strategy
instead is to find inside $D$ a particular type of oriented tree.

An _out-tree_ $T^{+}$ is an orientation of a tree in which one _root_ vertex
out-generates $T^{+}$. Reversing all arcs, we obtain an _in-tree_. When
identifying the root $r$ of an in-tree $T^{-}$ and the root of an out-tree
$T^{+}$, we obtain a tree orientation called a _bi-tree_ $T$ where $r$ is the
_center_. Note that $x,y$ are connected for every $x\in T^{-}$ and $y\in
T^{+}$. We say that a bi-tree is _balanced_ if $|T^{+}|=|T^{-}|$. In
particular, if every strongly connected $D$ contains a balanced bi-tree of
linear size, one directly obtains that $r_{t}>0$ for Problem 1.

###### Problem 2

What is the maximum $c_{b}$ for which every strongly connected directed graph
on $n$ vertices has a balanced bi-tree of size at least $c_{b}.n$?

We show in Theorem 4 that $c_{b}\geq 1/3$, where both $|T^{+}|$ and $|T^{-}|$
have size at least $1/6$. One can naturally ask if the enumeration problem
directly implies the bi-tree problem. But the following example shows that
this is not true in general.

###### Proposition 1

For every integer $k$, there exists a minimally strongly connected digraph $D$
on $n=3k^{2}+2k+2$ vertices admitting an enumeration $E=v_{1},\dots,v_{n}$
such that:

\- the number of forward couples in $E$ is quadratic in $n$ (at least
$k^{4}$), and

\- the maximal size of a balanced bi-tree only using forward arcs in $E$ is
$2k+5=O(\sqrt{n})$.

Proof. Let $D$ be the digraph with vertex set $\\{x\\}\cup A\cup
A^{\prime}\cup X\cup B^{\prime}\cup B\cup\\{y\\}$ where $A^{\prime}$,
$B^{\prime}$ have size $k$ and $A$, $B$ and $X$ all have size $k^{2}$.
Consider $(A_{i})_{1\leq i\leq k}$ a partition of $A$ into $k$ sets of size
$k$ and $(B_{i})_{1\leq i\leq k}$ a partition of $B$ into $k$ sets of size
$k$. Moreover, we denote by $a_{1},\dots a_{k}$ the vertices of $A^{\prime}$,
$b_{1},\dots b_{k}$ the vertices of $B^{\prime}$, and $(x_{i,j})_{1\leq
i,j\leq k}$ the vertices of $X$. Now, add to $D$ the following sets of arcs:
$\\{xa\ :\ a\in A\\}$, $\\{aa_{i}\ :\ a\in A_{i}\\}$ for all $1\leq i\leq k$,
$\\{a_{i}x_{i,j}\ :\ j=1,\dots,k\\}$ for all $1\leq i\leq k$,
$\\{x_{i,j}b_{j}\ :\ i=1,\dots,k\\}$ for all $1\leq j\leq k$, $\\{b_{j}b\ :\
b\in B_{j}\\}$ for all $1\leq j\leq k$, $\\{by\ :\ b\in B\\}$ and $\\{yx\\}$.
The construction is depicted in Figure 1.

$A$$X$$B$$x_{1,2}$$x_{1,k}$$x_{1,1}$$x_{2,1}$$x_{k,1}$$x_{k,2}$$x_{k,k}$$b_{2}$$b_{k}$$x$$y$$A^{\prime}$$B^{\prime}$$A_{1}$$A_{2}$$A_{k}$$a_{k}$$a_{2}$$a_{1}$$B_{1}$$b_{1}$$B_{2}$$B_{k}$

Figure 1: The digraph $D$ in the proof of Proposition 1. An arc between a
block and a particular vertex stands for all the arcs between every vertices
of the block and the particular vertex. The arc $yx$ is not drawn.

The digraph $D$ is strongly connected and has $n=3k^{2}+2k+2$ vertices.
Furthermore, $D$ is minimally strongly connected, as for every arc $uv$ we
have either $d^{+}(u)=1$ (if $uv=yx$ or $u\in A\cup X\cup B$) or $d^{-}(v)=1$
(if $v\in A\cup X\cup B$).

Consider now any enumeration of $D$ where $x$ is the first vertex, then $A$ is
before $A^{\prime}$, then $A^{\prime}$ is before $X$, then $X$ is before
$B^{\prime}$, then $B^{\prime}$ is before $B$, and finally $y$ is the last
vertex. For such an enumeration all the arcs of $D$ are forward except $yx$.
For every $1\leq i,j\leq k$, any vertex of $A_{i}$ has a path to any vertex of
$B_{j}$ using the vertex $x_{ij}$. So the number of forward couples is at
least $|A|.|B|=k^{4}$, which is quadratic in $n$. However, the largest
balanced bi-tree only using forward arcs has its center in $X$ and has size
$2k+5=O(\sqrt{n})$.

##  3 Computing a left-maximal depth first search tree

Given an out-tree $T$ and a node $x$ of $T$, we denote by $T_{x}$ the
_subtree_ rooted at $x$ consisting of all vertices in the ousection of $x$ in
$T$. A _child_ of $x$ is an outneighbor of $x$ in $T$. Let $D=(V,A)$ be a
directed graph. A _depth first search tree_ $T$ of $D$ (_dfs -tree_ for short)
is an out-tree which is a spanning subgraph of $D$ with the following
properties:

  * •

For every node $x$, there is a total order $\leq_{x}$ on the childs of $x$,
which is called a _left-right order_.

  * •

If $y,z$ are two childs of $x$ and there exists an arc of $D$ from $T_{z}$ to
$T_{y}$, then $y\leq_{x}z$ (i.e. arcs between disjoint subtrees goes from
right to left).

We are interested in a particular type of dfs-tree called _left-maximal_ in
which we have $|T_{y}|\geq|T_{z}|$ for every node $x$ and childs $y,z$ such
that $y\leq_{x}z$. In other words the size of the child subtrees of any vertex
is non-increasing from left to right.

###### Theorem 2

If $x$ out-generates $D$, then there exists a left-maximal dfs-tree $T$ rooted
at $x$. Moreover $T$ can be computed in quadratic time in minimally strongly
connected digraphs.

Proof. We construct a left-maximal dfs-tree rooted at $x$ as follows. Compute
the strongly connected components of $D\setminus\\{x\\}$ and their sizes.
Consider the acyclic digraph $D^{\prime}$ between components where an arc
$(C,C^{\prime})$ indicates that there is an arc from $C$ to $C^{\prime}$ in
$D$. By traversing $D^{\prime}$ according to a reverse topological order, we
obtain the size of the out-section of each node in $D\setminus\\{x\\}$. Let
$y$ be a node with out-section $S_{y}$ having maximum size. Note that $y$
belongs to some strongly connected component $C$ which is a source in
$D^{\prime}$. Since $D$ is strongly connected, $C$ contains an out-neighbor of
$x$. Free to choose $y$ in $C$, we assume for simplicity that $xy$ is indeed
an arc. Construct recursively a left-maximal dfs-tree $T^{\prime}$ rooted at
$x$ in $D\setminus S_{y}$, and a left-maximal dfs-tree $T^{\prime\prime}$
rooted at $y$ in the digraph induced by $S_{y}$. The final out-tree $T$ is
obtained by inserting $T^{\prime\prime}$ as the leftmost child of $x$ in
$T^{\prime}$. It is indeed a dfs-tree as there exists no arc from $S_{y}$ to
any node in $D\setminus T^{\prime}$ by the definition of outsection. To
realize that it is also left-maximal, consider the leftmost child $z$ of $x$
in $T^{\prime}$. The outsection $S_{z}$ of $z$ in $D\setminus\\{x\\}$ has size
at most $|S_{y}|$, and we thus have $|T_{z}|\leq|S_{z}|\leq|S_{y}|=|T_{y}|$.

As the computation of strongly connected components, digraph $D^{\prime}$, and
outsection sizes can be done in linear time, the whole computation can be done
in $O(n^{2})$ time in minimally strongly connected graphs (where the number of
arcs is linear in the number of vertices).

###### Problem 3

Can we compute a left-maximal dfs-tree in $o(n^{2})$ time in minimally
strongly connected digraphs? What about the complexity in the general case?

Let us now introduce our key-definition which is a particular type of
partition of a strongly connected digraph $D$. To get beforehand a bit of
intuition, one can picture a connected (undirected) graph $G$ with a depth
first search tree $T$ drawn on the plane. The key-feature here is that any
path $P$ from the root to a leaf partitions the rest of the graph into two
subsets $L$ and $R$ which are respectively the vertices of $V\setminus P$ to
the left and to the right of $P$. In other words, $G$ has a cutset $V(P)$ with
a remarkable property since it is spanned by a path. Observe also that _any_
root-leaf path can be used, so by a classical left-right sweeping argument,
one can find $P$ such that both $L$ and $R$ have size at most $2n/3$ (so that
the cut is balanced). We now generalize this argument to strongly connected
digraphs, where a directed cycle takes over the role of $P$.

An _$(I,C,O)$ -decomposition_ of a strongly connected digraph is defined as:

  * •

a partition of $V$ into three subsets $I,C,O$,

  * •

$C$ is spanned by a directed cycle,

  * •

there is no arc from $I$ to $O$.

Observe that, by strong connectivity and the fact that there is no arc from
$I$ to $O$, for every vertex $x$ in $I$, there exists a directed path from $x$
to $C$ with internal vertices inside $I$. Similarly, for every vertex $x$ in
$O$, there exists a directed path from $C$ to $x$ with internal vertices
inside $O$. We now show how to get a balanced $(I,C,O)$-decomposition.

Given a dfs-tree $T$, we call _left path_ $L_{T}$ the path starting at the
root of $T$ and which iteratively selects the leftmost child of the current
vertex as the next vertex of the path. In particular, in a planar drawing
respecting the left-right order of childs, $L_{T}$ is the path from the root
to the leftmost leaf. Let $x$ be a vertex of the left path of $L_{T}$. Given a
child $y$ of $x$, we define the subtree $T_{x,y}$ of $T$ as the subtree of
$T_{x}$ containing $x$ and all $T_{z}$ for $z\leq_{x}y$. We call $T_{x,y}$ a
_left subtree_ of $T$. Note that $T_{x}$ is the left subtree $T_{x,y}$
obtained by selecting $y$ as its rightmost child. Also, if $y$ is the leftmost
child, $x$ has only one child in $T_{x,y}$.

###### Proposition 2

For every left subtree $T_{x,y}$, there exists an $(I,C,O)$-decomposition such
that $T_{x,y}$ is included in $I\cup C$ and $V\setminus T_{x,y}$ is included
in $O\cup C$.

Proof. As $T$ is a dfs-tree, any arc from $T_{x,y}\setminus\\{x\\}$ reaches a
vertex in $T_{x,y}$ or in $L_{T}$. By strong connectivity, some arc $uv$ with
$u\in T_{x,y}\setminus\\{x\\}$ reaches $L_{T}$ between the root and $x$, and
we select $uv$ such that $v$ has minimum distance from the root in $T$. Note
that $v$ can be equal to $x$. We define $C$ as the set of vertices in the path
$P_{vu}$ from $v$ to $u$ in $T$. Note that $C$ is spanned by the cycle formed
by $P$ and the arc $uv$. We now set $I:=V(T_{x,y})\setminus C$ and
$O=V\setminus(C\cup I)$. Every arc leaving $T_{x,y}\setminus\\{x\\}$ reaches a
vertex $w$ of the left-path between $v$ and $x$ by the choice of $v$. Thus $w$
is in $C$, therefore there is no arc from $I$ to $O$.

###### Proposition 3

Every strongly connected directed graph with at least four vertices has a dfs-
tree $T$ which has a left subtree $T_{x,y}$ such that $n/3<|T_{x,y}|<2n/3$.

Proof. We consider a left-maximal dfs-tree $T$ of $D$. Scanning the left-path
of $T$ from the root, we consider the first node $z$ such that $|T_{z}|\leq
n/3$. Let $x$ be the parent of $z$. If $|T_{z}|=n/3$, the left subtree
$T_{x,z}$ with size $n/3+1$ is the solution we are looking for. Let $y$ be the
rightmost child of $x$ such that $|T_{x,y}|<2n/3$. Assume for contradiction
that $|T_{x,y}|\leq n/3$. By the definition of $z$, we have $|T_{x}|>n/3$,
hence $y$ is not the rightmost child of $x$. In particular, $y$ has a (next)
right sibling $y^{\prime}$. As $|T_{y^{\prime}}|\leq|T_{z}|<n/3$, we reach a
contradiction to the choice of $y$ since $|T_{x,y^{\prime}}|<2n/3$. Thus
$T_{x,y}$ is our solution.

###### Corollary 1

Every strongly connected directed graph has an $(I,C,O)$-decomposition such
that both $I\cup C$ and $O\cup C$ have size strictly greater than $n/3$.

Proof. This is a direct consequence of Proposition 2 and Proposition 3. The
case $n\leq 3$ follows by enumerating the cases.

Such an $(I,C,O)$-decomposition is _balanced_. We now compute a linear size
bi-tree from it.

##  4 Bilabels

We now consider a directed graph $D$ equipped with a _bi-label_ , that is
every vertex $x$ receives a couple $(i(x),o(x))$ of positive integers. The
_weight_ of $D$ is $(i(V),o(V))$, the sum of all $i$ and $o$ values
respectively. Assume that $D$ is a bi-labelled digraph which is the union of a
digraph $D^{\prime}$ and an out-tree $T^{+}$ rooted at $r\in V(D^{\prime})$
such that $D^{\prime}\cap T^{+}=\\{r\\}$, we can _transfer_ the weight
$o(T^{+})$ to $D^{\prime}$ by adding $o(T^{+}\setminus r)$ to $o(r)$ and
removing all the vertices of $T^{+}\setminus r$. We define similarly the
transfer operation of $i$ for an in-tree.

Given a bi-tree $B$ of $D$, the _value_ of $B$ is the pair $(a,b)$ where $a$
is the sum of all $i(x)$ for $x$ in $B^{-}$ and $b$ is the sum of all $o(x)$
for $x$ in $B^{+}$. In other words, the value of $B$ is the label of the
center after the transfers of $B^{+}$ and $B^{-}$. Observe that if
$D^{\prime}$ is obtained from $D$ by some transfer and $D^{\prime}$ has a bi-
tree with value $(a,b)$, then $D$ also has a bi-tree with value $(a,b)$.

###### Theorem 3

If $C$ is a cycle equipped with a bilabel $(i,o)$ with weight $(w,w)$, it
contains a bi-tree with value at least $(w/2,w/2)$.

Proof. Consider a shortest path $P$ in $C=x_{1},\dots,x_{n}$ such that
$i(P)\geq w/2$ or $o(P)\geq w/2$. Assume without loss of generality that
$P=C[x_{1},\dots,x_{k}]$. First consider the case where we have $i(P)\geq
w/2$. By minimality of $P$, we have $o(C[x_{k},\dots,x_{n}])\geq w/2$, and
therefore the bi-tree $B$ centered at $x_{k}$ such that
$B^{+}=C[x_{k},\dots,x_{n}]$ and $B^{-}=C[x_{1},\dots,x_{k}]$ satisfies the
hypothesis. In the case $o(P)\geq w/2$, we proceed similarly with $x_{1}$ as
center.

The bound in Theorem 3 is sharp. Consider for this a directed 4-cycle in which
all labels are $(w/4,w/4)$: any bi-tree has value $(a,b)$ with
$\min\\{a,b\\}=w/2$.

###### Theorem 4

Every strong digraph $D=(V,A)$ on $n$ vertices contains a bi-tree $B$ such
that both $B^{+}$ and $B^{-}$ have size at least $n/6$.

Proof. By Corollary 1, $D$ has an $(I,C,O)$-decomposition such that both
$I\cup C$ and $O\cup C$ have size at least $n/3$. Observe that $D$ is spanned
by a subgraph $S$ consisting of the directed cycle spanning $C$, together with
a disjoint collection of in-trees rooted at some vertices of $C$ and with
other vertices in $I$, and a collection of out-trees rooted at some vertices
of $C$ and with other vertices in $O$. We consider that $S$ is a bi-labelled
digraph by setting the value $(1,1)$ to every vertex. We can then transfer the
weight of all in-trees and out-trees to their respective roots to obtain a bi-
label on $C$ with weight at least $(n/3,n/3)$. We now invoke Theorem 3 to
obtain a bi-tree with value at least $(n/6,n/6)$ for the cycle, and unfold it
by reversing appropriate transfers to get a bi-tree of $S$ with same value.

Note that the above constructions of left-maximal DFS and bi-tree can be
extended to a weighted digraph $D$ where each vertex $u$ has a non-negative
weight $w_{u}$. Given a subset $U\subseteq V$ of $n^{\prime}$ vertices, we can
set $w_{u}=1$ for $u\in U$ and $w_{u}=0$ for $u\notin U$ to compute similarly
a bi-tree $B$ such that $B^{-}$ and $B^{+}$ both span $n^{\prime}/6$ vertices
of $U$. One can then easily obtain an ordering of $V$ such that a constant
fraction of pairs in $U\times U$ are forward-connected.

We now consider the more general version of the problem where we want to
connect pairs in a given set $R\subseteq{V\choose 2}$ of requests.

##  5 Forward connecting a set of requested pairs

In the Request Forward Connected Pairs Problem (RFCPP), the input is a
strongly connected digraph $D=(V,A)$ and a set $R\subseteq{V\choose 2}$ of
_requests_ , and the output is a vertex ordering of $D$ maximizing the number
of forward pairs $\\{x,y\\}\in R$ (that is either $x,y$ or $y,x$ is forward).
Note that FCPP is the particular instance of RFCPP satisfying $R={V\choose
2}$. Since FCPP is in APX, it is natural to raise the following problem:

###### Problem 4

Is there a polytime constant approximation algorithm for RFCPP?

In particular, is it always possible to satisfy a linear fraction of $R$? In
the more restricted variant where $R$ is a set of couples $(x,y)$ instead of
pairs (where one wants to maximize the number of forward couples $x,y$), one
cannot expect to satisfy a large proportion of $R$. Indeed, if $D$ is the
circuit $(v_{1},\dots,v_{n})$ and $R$ consists of all couples
$(v_{i+1},v_{i})$, any vertex ordering can only satisfy at most one request of
$R$, hence only a ratio of $1/n$ can be realized as forward couples.

Surprisingly, when requests are pairs, we could not find any set of request
$R$ which is not satisfied within a ratio of $1/\log n$. However, contrary to
the case of FCPP where a positive ratio is achievable, the following result
shows that there are instances of RFCPP for which only a logarithmic ratio can
be realized as forward pairs.

###### Proposition 4

For all $n$, there exists an instance of RFCPP where $D$ has $2^{n+1}-1$
vertices, $R$ has size $n2^{n-1}$, and no more than $2^{n}$ requested pairs
can be realized as forward paths.

Proof. The graph $D$ is the complete binary tree of height $n$ seen as a
directed graph by letting each edge to be a circuit of length two. The set of
requests is recursively defined in the following way. We consider the set
$L_{l}$ of all leaves which are descendants of the left child of the root $r$
and the set $L_{r}$ of leaves descendants of its right child. Now we pick an
arbitrary perfect matching $M$ between $L_{l}$ and $L_{r}$ and set as requests
all the $|M|$ pairs formed by the edges of $M$. We call this set $R_{1}$, and
recursively define in the same way a set of requests for each of the two
childs of $r$. We stop when reaching leaves. With the right choice of
matchings, the set of requests can correspond for instance to a hypercube of
dimension $n$ on the leaves. We shall not need it, but it gives a good
intuition of the possible structure of requests.

To sum up, $D$ has $2^{n+1}-1$ nodes, $2^{n}$ of them being leaves. Each
internal node creates a matching of requests in its set of descendant leaves,
hence the total number of requests is $n.2^{n-1}$.

Any ordering $<$ of $V(D)$ can be considered as the sub-digraph $D^{\prime}$
of $D$ where we keep only arcs $xy$ satisfying $x<y$. Note that this
corresponds to an orientation of the edges of the tree. Our goal is to show
that the number of requests $x,y$ which are connected by a forward path is at
most $2^{n}$. To show this, for a given node $x$ we denote by
$\operatorname{{\it rf}}(x)$ the number of requests between descendants of $x$
(in the tree $D$) which are realized by a forward path. We also denote by
$in(x)$ the number of leaves $y$ descendant of $x$ such that there is a
forward path from $y$ to $x$. Finally $out(x)$ is the number of leaves $z$
descendant of $x$ such that there is a forward path from $x$ to $z$.

We now show by induction that both $\operatorname{{\it rf}}(x)+in(x)$ and
$\operatorname{{\it rf}}(x)+out(x)$ are upper bounded by $\ell(x)$, the number
of leaves descendant of $x$. This is true if $x$ has two leaves as childs
since either $x$ is a source (resp. a sink) in $D^{\prime}$ and
$\operatorname{{\it rf}}(x)+\max(in(x),out(x))=0+2$, or $x$ has both in and
out-degree 1 and $\operatorname{{\it rf}}(x)+in(x)=\operatorname{{\it
rf}}(x)+out(x)=1+1$. For the induction step, we assume that $x$ has two childs
$y,z$.

  * •

if we have both arcs $xy,xz$ in $D^{\prime}$, we have $\operatorname{{\it
rf}}(x)+in(x)\leq\operatorname{{\it rf}}(x)+out(x)=\operatorname{{\it
rf}}(y)+\operatorname{{\it rf}}(z)+out(y)+out(z)$, which by induction is at
most $\ell(y)+\ell(z)=\ell(x)$.

  * •

if we have both arcs $yx,zx$, we conclude similarly.

  * •

if we have both arcs $yx,xz$, note that $\operatorname{{\it
rf}}(x)\leq\operatorname{{\it rf}}(y)+\operatorname{{\it
rf}}(z)+\min(in(y),out(z))$. Also $in(x)=in(y)$ and $out(x)=out(z)$. Thus, if
$in(y)\leq out(z)$ we have $\operatorname{{\it
rf}}(x)+in(x)\leq\operatorname{{\it rf}}(x)+out(x)\leq\operatorname{{\it
rf}}(y)+\operatorname{{\it
rf}}(z)+\min(in(y),out(z))+out(z)=\operatorname{{\it
rf}}(y)+in(y)+\operatorname{{\it rf}}(z)+out(z)\leq\ell(y)+\ell(z)=\ell(x)$.
And the same conclusion holds when $in(y)>out(z)$.

  * •

if we have both arcs $xy,zx$, we conclude as previously.

Thus the maximum number of forward requests is $2^{n}$.

Noteworthily, for the instance in Proposition 4, there is a set of $2n$
orderings such that every pair $x,y$ of leaves is forward connected in one of
the orderings. Let us call a _forward cover_ of $D$ a set of vertex orderings
$\leq_{1},\dots,\leq_{k}$ such that for every pair $\\{x,y\\}$, there is some
$i$ such that $x,y$ or $y,x$ is a forward pair in $\leq_{i}$. This suggests
the following conjecture:

###### Conjecture 1

Every strong digraph $D$ on $n$ vertices has a $O(\log n)$ size forward cover.

Conjecture 1 holds when $D$ is a bi-oriented graph. Here is a sketch: it
suffices to consider a spanning tree $T$ of $D$ and to fix a centroid $c$. We
then let $T=T_{1}\cup T_{2}$ where $T_{1}\cap T_{2}=\\{c\\}$ and both
$T_{1},T_{2}$ have size at least $n/3$. We consider any vertex enumeration
$T_{1}\leq c\leq T_{2}$. Now we find recursively in $T_{1}$ and $T_{2}$ two
families $F_{1}$ and $F_{2}$ of vertex enumerations of size logarithmic in
$2n/3$. We conclude by gluing (on $c$) the orderings in $F_{1}$ and $F_{2}$ by
pairs. We get in total $1+\max(|F_{1}|,|F_{2}|)$ orders, hence a logarithmic
size family.

Another intriguing question is the ”forward orientation” of a pair $x,y$. We
have seen that in some cases, like the circuit, pairs $v_{i},v_{i+1}$ are
(obviously!) much more likely to be forward than pairs $v_{i+1},v_{i}$. If
indeed a forward cover of logarithmic size exists, it could be that some
couples $x,y$ are more involved in a small cover than their reverse $y,x$.
This suggests a kind of ”forwardness” of a pair of vertices which might be
interesting to characterize.

##  6 Questions

Our main open question concerns Conjecture 1. A possible way to solve it would
be to find $O(\log n)$ bi-trees such that for any pair $\\{x,y\\}$, there
exists a bi-tree $T$ such that either $x\in T^{-}$ and $y\in T^{+}$, or $y\in
T^{-}$ and $x\in T^{+}$. The reason is that each bi-tree can easily be
converted to an ordering where each couple $(x,y)$ with $x\in T^{-}$ and $y\in
T^{+}$ is a forward couple.

Another question concerns the maximum size of a balanced bi-tree that can be
found in any strongly connected digraph with $n$ vertices. Our construction
shows that any such digraph contains a balanced bi-tree where both trees have
size $n/6$. The construction given in [1] implies that there exists strongly
connected digraphs such that in any bi-tree $T$, either $T^{-}$ or $T^{+}$ has
size at most $n/3+O(1)$. This leaves a factor 2 gap.

If we relax the bi-tree definition by requiring that the in-tree and the out-
tree are edge disjoint (an _edge-bi-tree_). What is the maximum size of a
balanced edge-bi-tree in any strongly connected digraph? The upper-bound of
$n/3+O(1)$ given in [1] indeed holds for edge-bi-trees. Is there a gap between
the maximum size of a balanced edge-bi-tree and that of a balanced bi-tree?

More generally, what are the exact values of $r_{s}$ and $r_{t}$? In other
words, what is the maximum ratio of couples that can be connected through an
ordering of the arcs, or an ordering of the vertices respectively? Is it
possible to obtain an interesting lower-bound of $r_{t}$ as a function of
$r_{s}$?

### Acknowledgement

This research was partially supported by the ANR project Digraphs
ANR-19-CE48-0013 and the ANR project Tempogral ANR-22-CE48-0001.

## References

  * [1] Alkida Balliu, Filippo Brunelli, Pierluigi Crescenzi, Dennis Olivetti, and Laurent Viennot.  A note on the complexity of maximizing temporal reachability via edge temporalisation of directed graphs.  CoRR, abs/2304.00817, 2023.
  * [2] Jørgen Bang-Jensen.  Edge-disjoint in- and out-branchings in tournaments and related path problems.  J. Comb. Theory, Ser. B, 51(1):1–23, 1991.
  * [3] Jørgen Bang-Jensen, Stéphane Bessy, Frédéric Havet, and Anders Yeo.  Arc-disjoint in- and out-branchings in digraphs of independence number at most 2.  J. Graph Theory, 100(2):294–314, 2022.
  * [4] Jørgen Bang-Jensen, Nathann Cohen, and Frédéric Havet.  Finding good 2-partitions of digraphs II. enumerable properties.  Theor. Comput. Sci., 640:1–19, 2016.
  * [5] Aaron Bernstein, Maximilian Probst, and Christian Wulff-Nilsen.  Decremental strongly-connected components and single-source reachability in near-linear time.  In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 365–376. ACM, 2019.
  * [6] Filippo Brunelli, Pierluigi Crescenzi, and Laurent Viennot.  Maximizing reachability in a temporal graph obtained by assigning starting times to a collection of walks.  Networks, 81(2):177–203, 2023.
  * [7] Jessica A. Enright, Kitty Meeks, George B. Mertzios, and Viktor Zamaraev.  Deleting edges to restrict the size of an epidemic in temporal networks.  J. Comput. Syst. Sci., 119:60–77, 2021.
  * [8] F. Göbel, J. Orestes Cerdeira, and Henk Jan Veldman.  Label-connected graphs and the gossip problem.  Discret. Math., 87(1):29–40, 1991.
  * [9] George B. Mertzios, Othon Michail, and Paul G. Spirakis.  Temporal network optimization subject to connectivity constraints.  Algorithmica, 81(4):1416–1449, 2019.
  * [10] Hendrik Molter, Malte Renken, and Philipp Zschoche.  Temporal reachability minimization: Delaying vs. deleting.  In Filippo Bonchi and Simon J. Puglisi, editors, 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, August 23-27, 2021, Tallinn, Estonia, volume 202 of LIPIcs, pages 76:1–76:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.