# Cross-Lingual Query-Based Summarization of Crisis-Related Social Media: An
Abstractive Approach Using Transformers

Fedor Vitiugin
Universitat Pompeu Fabra
Barcelona, Spain
<EMAIL_ADDRESS>
Carlos Castillo
ICREA and Universitat Pompeu Fabra
Barcelona, Spain
<EMAIL_ADDRESS>

###### Abstract

Relevant and timely information collected from social media during crises can
be an invaluable resource for emergency management. However, extracting this
information remains a challenging task, particularly when dealing with social
media postings in multiple languages. This work proposes a cross-lingual
method for retrieving and summarizing crisis-relevant information from social
media postings. We describe a uniform way of expressing various information
needs through structured queries and a way of creating summaries answering
those information needs. The method is based on multilingual transformers
embeddings. Queries are written in one of the languages supported by the
embeddings, and the extracted sentences can be in any of the other languages
supported. Abstractive summaries are created by transformers. The evaluation,
done by crowdsourcing evaluators and emergency management experts, and carried
out on collections extracted from Twitter during five large-scale disasters
spanning ten languages, shows the flexibility of our approach. The generated
summaries are regarded as more focused, structured, and coherent than existing
state-of-the-art methods, and experts compare them favorably against summaries
created by existing, state-of-the-art methods.

_K_ eywords abstractive summarization, multilingual retrieval, social media,
emergency management

##  1 Introduction

Social media platforms such as Twitter are widely used to share information
during disasters and mass convergence events [1]. During these situations,
users, including eyewitnesses, media, governmental and non-profit
organizations, post an enormous volume of diverse content, from personal
opinions and commentary to reports and messages providing relevant information
that could lead to better situational awareness. This work describes an
approach to automatically summarize information posted in social media about
an event, creating brief reports to help emergency response and recovery.
These reports can help emergency managers better understand a developing
situation and plan the following actions accordingly [2, 3].

The development of methods that automatically extract crisis-relevant
information from social media has been an active line of work for many years
[4]. Traditionally, crisis information extraction methods use linguistic and
semantic resources mainly concentrated on one language [5]. However, there are
many cases where a single crisis affects several countries or regions that
speak different languages [6, 7, 8], or affects a region where the population
speaks more than one language.

Previous work has shown that the information provided by social media postings
is related to the language in which they are posted, and indeed messages in
different languages about the same crisis often provide complementary
information [9, 10]. Extracting and summarizing information from social media
in only one language introduces the risk of missing valuable information.
However, creating or adapting language-specific resources or methodologies for
new languages is expensive and time-consuming. Therefore, current crisis
informatics solutions need effective cross-lingual tools for extracting
relevant information about appropriate categories of crisis-relevant
information.

Our main contributions are:

  * •

We describe a flexible, query-based, cross-lingual method for collecting from
social media relevant postings in multiple languages about specific
information categories. The method uses pre-trained multilingual sentence
embeddings (LASER [11]) to extract postings from a general collection of
crisis-related messages.

  * •

We describe an approach for crisis summarization that takes as input relevant
postings about an information category and generates a summary using a
transformer-based language model (T5 [12]). We use clustering and
diversification operations to create less redundant, more information-rich
summaries.

We perform empirical validation using both crowdsourcing annotators and
emergency management experts and release a new annotated dataset to evaluate
multilingual crisis informatics systems.

The remainder of this paper includes a presentation of related work (§2),
followed by a description of the query-based method for crisis information
extraction and cross-lingual classification and summarization (§3). Next, we
describe our experimental setup (§4) and the results of our analysis (§5).
Finally, we present our conclusions and envisioned future work (§6).

##  2 Related Work

Mining the social web for crisis-relevant information has been an active and
fruitful research topic for many years. Our coverage of it focuses on
overviewing methods for mining (§2.1), classification (§2.2), and
summarization (§2.3) of crisis-relevant social media messages.

###  2.1 Mining Social Media for During Crises

Social media is a key communication channel during all kinds of crises,
including natural and man-made disasters. Computational methods from many
disciplines can contribute to creating mining and retrieval systems that can
help emergency managers [1]. Crisis-related social spans many different
categories of information, including timely messages about urgent needs from
affected populations and damaged infrastructure such as bridges or roads.
Together, this information is relevant for emergency response, recovery
management, and assessments of the costs of damages [13] Unfortunately, most
methods for mining social media during disasters described in the extensive
literature on the topic are monolingual, limiting the applicability in
countries using languages other than English or even in English-speaking
countries with increasing multilingual urban populations [10]. The response
during the disasters could be significantly improved with the ability to
employ social data mining methods on user-generated data across multiple
languages [9]. Cross-lingual and multilingual classification and summarization
methods provide an opportunity to gather complementary information across
various languages spoken in affected areas.

###  2.2 Classification of Crisis-Related Messages

In the recent literature on this topic, “traditional” supervised learning
methods such as Naive Bayes and Support-Vector Machines (SVM) coexist with
neural-network-based methods [14]. Indeed, SVM for the classification crisis-
relevant social media has consistently shown to exhibit high performance,
especially when combined with semantic features computed with the help of
external knowledge bases [15].

Deep learning methods using various architectures have proven effective at
detecting crisis-relevant messages; a popular architecture is Convolutional
Neural Networks using word embeddings [16, 8]. The addition of information
specific to an event type, such as hydrological information in the case of
floods, has been shown to improve classification performance [17]. A
particularly influential model has been Bidirectional Encoder Representations
from Transformers (BERT) [18, 19], which is currently being used for various
challenging Natural Language Processing (NLP) tasks, including classification.
Recent papers on this topic describe end-to-end transformer-based models for
crisis classification tasks, demonstrating promising results [20, 21].

Language-Agnostic SEntence Representations (LASER) is an architecture to learn
joint multilingual sentence representations for 93 languages. The system uses
a single Bidirectional Long Short-Term Memory (BiLSTM) encoder with a shared
byte-pair encoding vocabulary for all languages, coupled with an auxiliary
decoder, and trained on publicly available parallel corpora. The resulting
embeddings are computed using English annotated data only and transferred to
any of the 93 languages without any modification [11]. LASER embeddings have
also been shown to be effective in multilingual classification tasks [22, 23].

###  2.3 Crisis-Related Information Summarization

Social media messages are usually short and thus tend to provide fragmented
information hence consolidating and summarizing information is key [24, 25].
An informative summary can help stakeholders gain situational awareness and
manage critical resources effectively [26].

The main approaches used for text summarization can be categorized as either
extractive or abstractive [27]. _Extractive_ approaches construct summaries by
combining selected informative phrases or sometimes whole sentences from the
source text [28]. _Abstractive_ summarization, on the other hand, generates
summaries from a representation of the semantics of a given text; an
abstractive summary may contain words or sentences that do not appear in the
source document(s). Abstractive summarization techniques usually employ a
generative approach [29, 30].

Despite the benefits of abstractive approaches, extractive approaches are
still considered state-of-the-art for summarization due to their simplicity
and high performance [31, 32]. However, extractive approaches often fail to
include key elements useful in a report, such as answers to “what,” “who,”
“where,” “when,” and “how” questions. These are important elements in the
domain of disaster and crisis management and need to be concisely incorporated
into summaries [33]. Query-based approaches have been described as a helpful
manner of incorporating this information to improve the quality of reports
[34]. In general, abstractive methods may facilitate the generation of more
informative summaries, not restricted to sentences that directly take
sequences of words from the source text [35]. State-of-the-art abstractive
summarization methods tend to adopt transformers and pre-trained models that
have demonstrated great performance in other NLP tasks: BART [36], T5 [37],
PEGASUS [38].

Our research builds upon previous work and contains two key innovations. To
the best of our knowledge, (1) we are the first to describe a summarization
method that retrieves crisis-relevant information using a query-based
approach, and (2) we are the first to propose a transformer-based
summarization model for crisis-related messages.

Figure 1: Overview of our cross-lingual information summarization framework.

##  3 Method overview

In this section, we provide an overview of the proposed method, named CLiQS-CM
(Cross-LIngual Query-based Summarization of Crisis Messages). An overview of
the method is shown in Figure 1. First, an automatic classification model is
used for detecting crisis-relevant, informative messages (§3.1). Second,
cross-lingual ranking is performed on these messages (§3.2). Third, the top
$k$ ranked messages are given as input to a summarization model (§3.3).

###  3.1 Classification Model

A large fraction of messages posted in social media in response to a crisis
event doesn’t include any informative claims beyond merely announcing that a
crisis situation is developing. Hence, a key step is detecting crisis-relevant
_informative_ messages. We model this as a binary classification task and
create an automated classification model that we name CLiQC-CM (Cross-LIngual
Query-based Classification of Crisis Messages).

Pre-processing. Messages are preprocessed by replacing URLs and account
mentions (“@user”) by specific tokens and turning hashtags into words. We
preserve punctuation and stopwords, as in the next steps, we use sentence
embeddings and dependency parsing.

Feature extraction. We include morphological and syntactical features. Using
the Stanza Part Of Speech (POS) tagger [39], we count the number of
numerals/numbers, nouns, verbs, adverbs, and adjectives in the messages. Using
the Stanza dependency parser, we extract and count syntactic features
indicating the presence/absence of claim-containing sentences, such as
subjective nouns, compounds, roots, and modality. For both tasks, we use pre-
trained models in each of the languages we work with. We normalize the count
of occurrences of each type of element in a message, such as “contains N
numerals/numbers,” “contains N subjective nouns,” and so on, using min-max
scaling to be in $[0,1]$. We also consider Named Entity Recognition (NER)
features extracted using the SpaCy library [40]. These are binary features
indicating whether a message contains persons’ names, the name of a place,
organization, or a date. We use SpaCy’s pre-trained models for each of the
languages we work with. Off-the-shelf, SpaCy supports 15 languages, including
all the ones we work with, except Croatian and Tagalog. For Croatian, we use a
contributed model for the Stanza package; for Tagalog, we use an open-source
pre-trained model111https://github.com/matthewgo/FilipinoStanfordPOSTagger.
Finally, we include _message-specific features_ indicating the (min-max
scaled) number of URLs and user mentions in messages.

Embeddings. For representing the input data, we used sentence embeddings
generated by the pre-trained transformer-based model, LASER [11]. LASER
sentence-level embeddings are obtained by applying max-pooling over the output
of BiLSTM BiLSTM sentence encoder. The BiLSTM output is constructed by
concatenating the outputs of two LSTMs working in opposite directions (forward
and backward). The bidirectional encoder captures more contextual information
than a single-direction Long Short Term Memory (LSTM) encoder (e.g., a left-
to-right one). In our experiments, we used LASER to embed all tweet sentences
into fixed-size vectors of length 1,024.

Architecture. In our classification architecture, the embeddings are passed to
an LSTM-layer and then combined with additional features. This architecture is
inspired by one proposed for the detection of fake news articles [41], which
has also been used for emotion detection [42].

The proposed scheme, depicted in Figure 2 (minus the query-based features,
which are only used by the ranking step), computes the feature vectors
separately and then combines them with the help of MLP Multi-Layer Perceptron
(MLP) layer. We use binary cross-entropy as the loss function to optimize and
include a soft-max layer to classify social media text into one of two classes
(“crisis relevant” or “not crisis relevant”). The hyper-parameter settings of
the feature extractor portions are shown in Table 1. The feature combination
layer uses the softmax activation function with Adam optimizer, the learning
rate of 0.001, batch size of 100, and binary cross-entropy loss.

Table 1: Values of hyper-parameters. Hyperparameter |  Text features |  LASER embeddings |  Similarity features
---|---|---|---
LSTM layers |  - |  1 |  -
MLP layers |  2 |  3 |  2
MLP neurons |  128;24 |  1024;256;128 |  128;24
Dropout |  - |  0.5 |  -
Activation |  relu |  sigmoid |  relu

###  3.2 Cross-lingual Ranking Model

The next step in our method is to retrieve, from the informative crisis-
related messages, a series of messages that are relevant for various
informational categories. Specifically, we retrieve and rank the top-$k$ most
relevant messages from each category to pass them to the summarization model
(§3.3).

To make information extraction more adaptable to different needs of emergency
managers, our method is based on structured queries. Each query is related to
a specific information need and contains keywords, templates, and prototypes;
a sample query is found in Table LABEL:tab:query. _Keywords_ are words used
frequently in messages of a category; _templates_ are fragments containing key
crisis-relevant facts; and _examples_ are entire sentences or even entire
messages corresponding to each category.

Each query is written in one language (English in our case) and used to
extract information across all languages. Queries are, for the most part,
agnostic of the type of event, but in some cases, they may include elements
that are specific to a type of disaster, for instance, in the case of
earthquakes, their magnitude, or in the case of storms, rainfall. We remark
that context-based semantics allow our system to work even if these elements
provided by the user are not 100% complete (e.g., we can find messages
containing related keywords or messages with similar semantics to the examples
provided but using different wording).

To calculate query similarity features, we measure average and maximum cosine
similarity between the query’s keywords, templates, prototypes, and each
message. As a result, we have six similarity features. For ranking messages,
we use basically the same architecture as in the previous step (S3.1), with
the addition of query similarity features. This is depicted in Figure 2. After
removing duplicates, we pass the top 100 candidates to the summarization step.
We tested with the top 20, 50, and 100 candidates, and observed that the top
100 provided the highest recall.

Figure 2: Combining the transformer embeddings with morphological, syntactic,
message-specific features and query similarity features using deep MLP

###  3.3 Summarization Model

The final component of our method creates a category-specific summary from the
retrieved messages for each category. These summaries are created by T5, a
pre-trained222HuggingFace - https://huggingface.co transformer model widely
used for summarization tasks [12]. In our preliminary experiments, this model
performed better than a similarly pre-trained BART-based model.

We tested two different configurations for the summarization model: a regular
condition and a diversified condition. In the _regular_ condition, we gave T5
as input the texts from the top-100 most relevant candidates and limited the
length of the output text. In the _diversified_ condition, we clustered the
top-100 most relevant candidates and gave to T5 as input the texts of all the
messages on each cluster, one cluster at a time; the resulting summary is the
concatenation of the per-cluster summaries. For the diversification step, we
first automatically find an appropriate number of clusters using the
Silhouette Score. Next, we cluster texts by the K-Means method. Because we
want to keep all summaries comparable in length for our experiments, we set a
maximum number of clusters to four. Also, during experiments, we found that
the heuristic of summarizing clusters in decreasing order by size (i.e.,
starting with the largest cluster) helps to generate more relevant summaries.
This is akin to following the “inverted pyramid” style typically used in
journalism.

##  4 Experimental Setup and Evaluation

In this section, we describe our data collection (§4.1) and the queries used
to retrieve relevant messages in various information categories (§4.2). Then,
we describe the baselines for classification (§4.3) and summarization (§4.4),
and the evaluation metrics used to compare the proposed method against the
baselines (§4.5).

###  4.1 Multilingual Data Collection

Table 2: Number of annotated messages for each event, including total number
of messages, and number of messages labeled as informative by a human
annotator. Local languages appear in bold.

| lang. 1 (en) | lang. 2 (es) | lang. 3 (fr) | language 4 | language 5
---|---|---|---|---|---
| dates | total | info | total | info | total | info | total | info | total | info
Australia bushfires | 06-31.01.2020 | 2000 | 233 | 2000 | 435 | 2000 | 460 | 2000 | 285 (ja) | 2000 | 167 (id)
Fukushima earthquake | 13.02.2021 | 2000 | 266 | 2000 | 529 | 2000 | 227 | 3000 |  101 (ja) | 3000 | 153 (id)
Gloria storm | 17-25.01.2020 | 703 | 393 | 571 | 210 | 517 | 168 | 542 |  233 (ca) | - | -
Taal eruption | 12-17.01.2020 | 551 | 123 | 691 | 202 | 610 | 114 | 1500 |  258 (tl) | 458 | 151 (pt)
Zagreb earthquake | 22-24.03.2020 | 537 | 162 | 509 | 243 | 520 | 187 | 1500 |  282 (hr) | 542 | 163 (de)

Our data collection followed standard practices to collect crisis-related
social media messages from Twitter. We collected public tweets using Twitter’s
public API, filtering by location-related keywords and date, without using any
additional filtering (e.g., we did not restrict the query to specific
languages). We considered five disaster events between January 2020 and
February 2021 that received substantial news coverage internationally:

  * •

_Australian bushfires_ (2019-2020): period of bushfires in many parts of
Australia, which, due to its unusual intensity, size, duration, and
uncontrollable dimension, was considered a
“megafire”;333https://en.wikipedia.org/wiki/2019–20_Australian_bushfire_season

  * •

_Fukushima earthquake_ (February 2021): a 7.1 Mw or 7.3 MJMA earthquake that
struck offshore east of Tōhoku, Japan and caused significant structural damage
across the Tōhoku and Kanto
regions;444https://en.wikipedia.org/wiki/2021_Fukushima_earthquake

  * •

_Gloria storm_ (January 2020): a Mediterranean storm that affected eastern
Spain and southern France with high winds and heavy
rainfall;555https://en.wikipedia.org/wiki/Storm_Gloria

  * •

_Taal volcano eruption_ (January 2020): a phreatomagmatic eruption from its
main crater that spewed ashes across Calabarzon, Metro Manila, and some parts
of Central Luzon and the Ilocos Region in the Philippines, resulting in
temporary closures of schools and workplaces, and disruptions of flights in
the area;666https://en.wikipedia.org/wiki/2020_Taal_Volcano_eruption

  * •

_Zagreb earthquake_ (March 2020): an earthquake of magnitude 5.3 Mw, 5.5 ML,
which hit the capital of Croatia, causing severe damage to hundreds of
buildings in its historical
center.777https://en.wikipedia.org/wiki/2020_Zagreb_earthquake

All messages include a “language” field computed by Twitter using a language
detection model developed specifically for tweets. We counted the number of
messages per language in each event. Three of the top languages were common to
all of the studied events: English (ISO 639-1 code: en), Spanish (es), and
French (fr). Additionally, we found several hundred messages for each event in
other languages, including Catalan (ca), Tagalog (tl), Croatian (hr), German
(de), Japanese (ja), Indonesian (id), and Portuguese (pt). After collecting
the data, we labelled tweets or their translation to English that contained
potentially informative factual information. We name this group of tweets
“informative messages.” One of the authors created the ground truth by
reviewing each event and hand labeling these tweets. Another author reviewed a
portion of the classified tweets, and adjustments to the classification task
were agreed upon when needed. Additionally, “informative messages” were
reviewed by crowdworkers during the categorization task and excluded if they
did not contain information related to any category. The number of annotated
messages is shown in Table 2.

Next, we used crowdsourcing to further categorize the messages into various
informational categories. Specifically, we employed crowdworkers through a
crowdsourcing platform,888SurgeHQ - https://www.surgehq.ai paying the standard
rate recommended by the platform. We asked three different workers to label
each of the approximately 5,700 informative messages across languages. The
target categories were based on an ontology from TREC-IS 2018 [43], where we
grouped some low-level ontology categories into higher-level ones. In total,
we defined nine high-level classes of information, shown in Table 3.

Table 3: Categories for multilingual information extraction, based on the ontology from TREC-IS 2018 [43]. Example messages have been paraphrased for anonymity. Category | Description | Example message
---|---|---
Casualties | Affected or injured people | Around 150 injured people
Damage | Built or natural environment damage | Destroying orange trees and rice paddies
Danger | Messages of caution or alerts | RED WARNING Barcelona - Danger to life
Government | Official report by public agencies | Local authorities continuing the search for …
Sensor | Seismic activity | Zargeb hit by 5.3 magnitude earthquake
Service | Providing a service or help | Local org. provides shelter for more than 1,000 people
Water | Water-related messages | floods in Catalonia
Weather | Weather updates | heavy rainfall and flooding across region

###  4.2 Queries

We use a set of queries covering the nine information categories listed in
Table 3. As described in §3.2, a query for an information category includes
keywords, templates, and prototypes. Creating a query requires some degree of
familiarity with social media messages posted during emergency situations.

_Keywords_ are nouns and verbs usually present in messages containing a
specific category of information. Practitioners could complete this task with
scripts or programs to find frequent words or phrases present in previous
collections of messages from past events. _Templates_ are small fragments of
text describing crisis-relevant facts. The kind of information that we seek is
in situation reports or in Wikipedia disaster-related _infoboxes_ , which are
templates that Wikipedia editors use to summarize crisis information. Users
can provide such templates by copy-pasting passages from these sources,
replacing the numbers or locations found there with the tokens NUMBER or
LOCATION. Finally, users can provide _prototypes_ – example messages or
central passages typical in category-related texts, which can be obtained by
sampling diverse, informative messages from past events. We envision a
specialized user interface may assist users in formulating such queries, and
we plan to explore that in future work. The scope of this paper is to
demonstrate the approach and provide an initial set of easily extended and
refined queries. One such query is shown in Table LABEL:tab:query.

Table 4: Example query. Each query includes keywords, templates, and
prototypes. Query for category: Weather
---
keywords: | snow, weather, rain, wind, coast, mph, kmh, forecast
templates: | batter parts of LOC, damages from winds, pummelling the region, NUMBER km/h winds,
| weather forecast, bad weather, heavy snow, strong wind, storm is hitting,
wind gust
prototypes: | Wind, rain and snow batter parts of country
| Storm brought around NUMBER m of snow and affect rivers
| Heavy rainfall, strong wind and more than NUMBER of snow across LOC
| Storm is hitting eastern LOC, with high winds and heavy rain
| Storm has battered parts of LOC and reportedly brought worth of rain
| Maximum gusts of wind in LOC NUMBER km / h
| Tonight, terrible rains in LOC
| Organisation has so far done NUM health care due to strong winds
| Gusts of wind left fallen trees

###  4.3 Message Classification Schemes

To compare our proposed method for informative messages detection, we
construct baseline models using one classical machine learning scheme (SVM)
and one deep learning scheme (LSTM) that uses LASER embeddings as input
features. Also, we compare our model with a cross-lingual LinearSVC-based
model that uses semantic features extracted with the BabelNet knowledge
base999https://babelnet.org. The complete list of proposed modeling schemes
for evaluation is the following:

  * •

LASER+SVM: this method uses pre-trained LASER embeddings; the embeddings are
then classified by a Linear SVM model;

  * •

LASER+LSTM: this method uses pre-trained LASER embeddings; the embeddings are
then classified by a LSTM model;

  * •

Khare [15]: this is a cross-lingual classification approach that uses
additional semantic features extracted from external knowledge bases;

  * •

CrisisBERT [20]: this is an end-to-end transformer-based model for crisis
classification tasks (our implementation uses the DistilBERT [44]
architecture);

  * •

CLiQC-CM (ours): this is our method for classification, using a combination of
LASER embeddings and tweet-related features. classified by a LSTM model.

###  4.4 Summarization Methods

We compare our CLiQS-CM model and its diversified variation CLiQS-D-CM against
several state-of-the-art summarization models. With the exception of the
LASER+LSTM+T5 method, all of the baselines use only category-related tweets as
input, i.e., we simulate the best scenario in which the input is received from
a perfect classifier. In our proposed models, we use the query-based model we
described. The complete list of baselines for summarization that we used is
the following:

  * •

LASER+LSTM+T5: this method uses pre-trained LASER embeddings, which are passed
as input to a LSTM model for category classification and then to a T5 model
for summarization;

  * •

C-SKIP [31]: this is a centroid-based method using a FastText skipgram model
trained on the CrisisLexT26 dataset [45], improved by the use of T5 pre-
trained model (originally, the method used a corpus extracted from Google
News);

  * •

CX_DB8 [34]: this is a queryable word-level unsupervised extractive
summarizer, which is based on the text embedding framework Flair [46]. We
tested this with different pre-trained embeddings, including transformer-based
such as BERT and XLNet; for this task and datasets, the best results were
obtained with Global Vectors for Word Representation (GLOVE) embeddings;

  * •

NAFI [35]: this is an abstractive text summarization method developed
specifically for crisis events;

  * •

CLiQS-CM (ours): we use a combination of LASER embeddings with tweet-related
features and query similarities features that are passed to a LSTM model for
the ranking step and then uses a T5 model for the summarization step;

  * •

CLiQS-D-CM (ours): this is the same as CLiQS-CM but retrieves diversified (see
§3.3) top-k candidates in the ranking step.

###  4.5 Evaluation Metrics

To evaluate the performance of the _classification_ models, we use three
standard metrics: Accuracy (ACC), Area Under the Receiver Operating
Characteristic Curve (AUC), and weighted F-measure (F1). These metrics are
typically used in research on social media for emergency management (e.g.,
[15, 8, 9]).

To evaluate the _summarization_ models, we considered four methods. First, we
annotated all summaries for factual claims and then computed, for each
summary, the fraction of factual claims it contained out of the total factual
claims mentioned across all summaries. Second, we computed the BERTScore [47]
of each summary, which is a metric for evaluation of a text that compares them
against a ground truth; in our case, an official report about the event.
Third, we performed a crowdsourced evaluation of the readability of each
summary across five dimensions: grammaticality, non-redundancy, referential
clarity, focus, and structure and coherence [48]; five crowdsourcing workers
were asked to compare summaries across each dimension. Fourth, we asked three
experts in emergency management to perform a side-by-side comparison of the
summaries and computed the number of times each summary was preferred.

##  5 Results

In this section, we present the results of our evaluation and comparison with
state-of-the-art methods. First, we present an evaluation of our
classification method (§5.1). Next, we consider the extent to which summaries
are comprehensive in terms of factual claims (§5.2). Then, we ask
crowdsourcing workers to evaluate the readability of summaries (§5.3).
Finally, we ask experts to perform a side-by-side comparison of the summaries
(§5.5).

###  5.1 Cross-lingual Classification

The first experiment is a “leave-one-language-out” evaluation: for each event,
the classifier is trained on data from 3 or 4 languages and tested on the last
language. What we simulate here is a scenario in which we have labeled data in
several languages and extract information in a new language. Table 5 shows the
performance comparison of our method CLiQC-CM (Cross-LIngual Query-based
Classification of Crisis Messages) with other baselines and state-of-the-art.
We also perform a “leave-one-event-out” evaluation, in which we train on
multilingual data for all events except one and test on the event that was
left out. Results are shown on Table 6.

We can observe that in general methods based on multilingual transformers
perform better than the semantic-based model by Khare. However, there are a
few differences between schemes based on LASER embeddings; SVM and LSTM
achieve in general the best performance, with some variations across datasets.
The performance of CrisisBERT is comparable to that of the proposed method
CLiQC-CM in some cases and across some metrics, but the average performance of
CLiQC-CM is better. We also observe that across all methods, “leave-one-event-
out” seems to pose a more difficult problem than “leave-one-language-out.”
This suggests that most of the multilingual methods we tested capture fairly
well event-specific concepts (such as specific places, impacts, or needs) of
each crisis but do not generalize so well across events.

Table 5: Results of cross-validation evaluation of message classification
across languages (“leave-one-language-out”), with 4-5 languages per event: the
test data contains all of the messages for an event in one language, while the
training data contains messages in other language for the same event.

| Australia bushfires | Fukushima earthquake | Gloria storm | Taal eruption | Zagreb earthquake | Average
---|---|---|---|---|---|---
Schemes | ACC | F1 | AUC | ACC | F1 | AUC | ACC | F1 | AUC | ACC | F1 | AUC | ACC | F1 | AUC | ACC | F1 | AUC
LASER+SVM | 92.3 | 91.1 | 70.7 | 97.4 | 97.3 | 85.4 | 83.6 | 81.6 | 66.6 | 95.4 | 94.4 | 77.9 | 92.9 | 92.9 | 90.6 | 92.3 | 91.5 | 78.2
LASER+LSTM | 91.9 | 74.6 | 92.7 | 97.5 | 92.7 | 99.5 | 83.2 | 66.9 | 86.2 | 94.5 | 84.3 | 96.7 | 93.7 | 83.0 | 97.2 | 92.2 | 80.3 | 94.4
Khare | 88.8 | 85.8 | 64.1 | 88.1 | 85.3 | 65.9 | 56.3 | 50.1 | 70.5 | 90.6 | 86.1 | 50.0 | 41.6 | 30.2 | 33.3 | 73.1 | 67.5 | 58.0
CrisisBERT | 91.4 | 87.1 | 96.2 | 97.6 | 96.6 | 99.4 | 87.7 | 83.4 | 94.2 | 95.3 | 92.6 | 98.0 | 94.1 | 90.6 | 98.3 | 93.2 | 90.1 | 97.2
*CLiQC-CM | 95.9 | 93.6 | 99.2 | 97.6 | 96.3 | 99.4 | 93.0 | 90.9 | 97.8 | 95.6 | 93.3 | 98.1 | 93.2 | 88.5 | 98.6 | 95.1 | 92.5 | 98.6

Table 6: Results of cross-validation evaluation of message classification
across events (“leave-one-event-out”): the test data contains all of the
messages for one event, while the training data contains messages from all of
the other events.

| Australia bushfires | Fukushima earthquake | Gloria storm | Taal eruption | Zagreb earthquake | Average
---|---|---|---|---|---|---
Schemes | ACC | F1 | AUC | ACC | F1 | AUC | ACC | F1 | AUC | ACC | F1 | AUC | ACC | F1 | AUC | ACC | F1 | AUC
LASER+SVM | 90.1 | 87.8 | 63.0 | 96.4 | 96.2 | 84.8 | 87.3 | 85.8 | 71.4 | 93.1 | 91.6 | 65.6 | 85.7 | 84.0 | 74.0 | 90.5 | 89.1 | 71.8
LASER+LSTM | 87.5 | 66.4 | 87.5 | 96.6 | 83.4 | 99.0 | 80.3 | 63.5 | 80.3 | 93.6 | 81.4 | 96.9 | 84.2 | 75.4 | 92.5 | 88.4 | 74.0 | 91.2
Khare | 86.2 | 83.3 | 54.8 | 93.4 | 93.4 | 81.9 | 80.8 | 77.1 | 57.9 | 90.2 | 88.4 | 58.8 | 80.6 | 77.4 | 65.9 | 86.2 | 83.9 | 63.9
CrisisBERT | 88.0 | 88.0 | 93.3 | 96.7 | 95.9 | 99.3 | 83.3 | 82.2 | 91.7 | 94.6 | 93.4 | 98.0 | 87.0 | 82.1 | 94.4 | 89.9 | 88.3 | 95.3
*CLiQC-CM | 89.1 | 88.2 | 94.0 | 96.1 | 95.9 | 98.4 | 86.4 | 84.8 | 93.3 | 93.7 | 93.5 | 96.3 | 88.4 | 84.4 | 95.0 | 90.7 | 89.4 | 95.4

###  5.2 Recall of Factual Claims

One way of measuring how informative are different summaries are, is to
consider the extent to which they contain factual claims related to an
information category for an event. To perform this evaluation, we manually
coded each category-related factual claim in each of the generated summaries
across all methods and then counted the number of claims in every summary
compared to the overall claims.101010These annotated summaries are part of our
data release. The fraction of claims contained in summary is divided by the
total number of claims across all summaries if what we call the _recall of
factual claims._ Table 7 shows the performance comparison of CLiQS-CM with
other baselines and state-of-the-art. CLiQS-CM and C-SKIP outperform the other
methods in both the cross-lingual and English-only evaluation, with a small
advantage for CLiQS-CM.

The diversified method CLiQS-D-CM produces summaries with less factual claims
than CLiQS-CM; in our observations, this is partially explained by
diversification leading to more low-ranking claims to be included, and those
claims are more likely to be incorrectly associated to the category under
analysis. In other words, the lower we go on the list of retrieved messages
for a category, the more likely we are to find messages that actually belong
to other categories. As we explain in subsection 3, we create clusters from
top-100 candidates, and often the number of category-related candidates is
much less than 100; in this case, clusters other than the first one are likely
to be non-related to a category.

Table 7: Factual claims present in each summary, on average, as a percentage of the total number of factual claims across all summaries for a category and event. We consider cross-lingual and English-only evaluations. The top two methods are extractive, while the remaining four are abstractive; our methods are marked with an asterisk. Scheme | Cross-lingual | English
---|---|---
C-SKIP | 28.8% | 29.0%
CD_DB8 | 24.1% | 17.8%
LASER+LSTM+T5 | 10.0% | 16.0%
Nafi | 25.1% | 28.8%
*CLiQS-CM | 29.4% | 31.2%
*CLiQS-D-CM | 23.8% | 23.5%

###  5.3 BERTScore - Similarity with Official Reports

To perform this evaluation, we retrieve summaries for each event prepared by
the Emergency Response Coordination Centre (ERCC).111111ERCC Portal -
https://erccportal.jrc.ec.europa.eu/ These summaries are created at the level
of entire events and not divided by category. Hence, we create an event-level
summary using each method by combining the summaries from all categories. Each
event-level summary is compared against the ERCC one using BERTScore.

Table 8 shows the results of the performance comparison of CLiQS-CM against
other models. Both proposed methods CLiQS-CM and CLiQS-D-CM show better
performance than the baselines in all datasets except one. The exception is
C-SKIP, a centroid-based extractive method, which demonstrates higher
performance for one of the analyzed events (Zagreb earthquake). The BERTScore
evaluation also helps us interpret the results regarding the recall of factual
claims, as often the precision of CLiQS-CM is higher than the one of CLiQS-D-
CM.

Table 8: Comparison of cross-lingual summaries against reports by ERCC using
BERTScore: precision (P), Recall (R), and F1 measure (F1). The top two methods
are extractive, while the remaining four are abstractive; ours are marked with
an asterisk.

| Australia bushfires | Fukushima earthquake | Gloria storm | Taal eruption | Zagreb earthquake | Average
---|---|---|---|---|---|---
Schemes | P | R | F1 | P | R | F1 | P | R | F1 | P | R | F1 | P | R | F1 | P | R | F1
C-SKIP | 78.9 | 79.5 | 79.2 | 79.9 | 84.0 | 81.9 | 79.5 | 81.5 | 80.5 | 80.6 | 80.7 | 80.7 | 82.5 | 82.8 | 82.6 | 80.3 | 81.7 | 81.0
CX_DB8 | 75.2 | 77.4 | 76.3 | 78.5 | 80.8 | 79.6 | 76.3 | 78.1 | 77.2 | 77.3 | 78.8 | 78.0 | 77.6 | 78.9 | 78.2 | 77.0 | 78.8 | 77.9
LSTM+LASER+T5 | 79.5 | 78.6 | 79.0 | 81.8 | 83.8 | 82.8 | 79.9 | 81.5 | 80.7 | 75.5 | 78.3 | 76.9 | 82.3 | 81.9 | 82.1 | 79.8 | 80.8 | 80.3
Nafi | 76.0 | 78.6 | 77.3 | 78.9 | 82.1 | 80.5 | 77.6 | 79.8 | 78.7 | 77.0 | 79.8 | 78.4 | 80.3 | 82.4 | 81.3 | 78.0 | 80.5 | 79.2
*CLiQS-CM | 81.0 | 80.6 | 80.8 | 80.6 | 85.4 | 82.9 | 81.2 | 82.0 | 81.6 | 82.7 | 81.2 | 81.9 | 81.8 | 82.2 | 82.0 | 81.5 | 82.3 | 81.9
*CLiQS-D-CM | 80.5 | 80.1 | 80.3 | 83.1 | 84.8 | 83.9 | 80.9 | 82.2 | 81.5 | 82.4 | 81.1 | 81.7 | 80.6 | 82.6 | 81.6 | 81.5 | 82.2 | 81.8

Additionally, the comparison of CLiQS-CM against other models, considering
only English messages as input for all models, is presented in Table 9. In
this monolingual evaluation, methods are closer to each other in terms of
BERTscore similarity with the reference. CLiQS-D-CM models show slightly
better average performance. In the Australia bushfires dataset, C-SKIP
performs better, and in the Taal volcano eruption dataset CLiQS-CM performs
slightly better.

Table 9: Comparison of English-only summaries against reports by ERCC using
BERTScore: precision (P), Recall (R), and F1 measure (F1). The top two methods
are extractive, while the remaining four are abstractive; ours are marked with
an asterisk.

| Australia bushfires | Fukushima earthquake | Gloria storm | Taal eruption | Zagreb earthquake | Average
---|---|---|---|---|---|---
Schemes | P | R | F1 | P | R | F1 | P | R | F1 | P | R | F1 | P | R | F1 | P | R | F1
C-SKIP | 78.2 | 79.2 | 78.7 | 79.8 | 80.7 | 80.3 | 77.4 | 78.9 | 78.2 | 77.9 | 80.1 | 79.0 | 80.2 | 81.0 | 80.6 | 78.7 | 80.0 | 79.3
CX_DB8 | 75.8 | 77.2 | 76.5 | 79.9 | 79.2 | 79.5 | 76.1 | 77.1 | 76.6 | 75.7 | 77.6 | 76.7 | 79.2 | 78.9 | 79.0 | 77.3 | 78.0 | 77.7
LSTM+LASER+T5 | 75.9 | 78.1 | 77.0 | 81.9 | 80.8 | 81.3 | 78.0 | 79.1 | 78.5 | 78.0 | 79.7 | 78.9 | 81.4 | 81.3 | 81.3 | 79.0 | 79.8 | 79.4
Nafi | 75.0 | 78.2 | 76.6 | 77.6 | 80.9 | 79.2 | 75.3 | 77.8 | 76.6 | 72.9 | 78.0 | 75.4 | 77.5 | 79.7 | 78.6 | 75.7 | 78.9 | 77.3
*CLiQS-CM | 77.9 | 78.8 | 78.3 | 80.4 | 80.7 | 80.5 | 77.6 | 79.4 | 78.5 | 77.9 | 80.2 | 79.0 | 80.8 | 82.2 | 81.5 | 78.9 | 80.3 | 79.6
*CLiQS-D-CM | 78.2 | 78.8 | 78.5 | 81.7 | 81.4 | 81.6 | 79.0 | 79.8 | 79.4 | 77.7 | 80.0 | 78.8 | 81.6 | 82.5 | 82.1 | 79.6 | 80.5 | 80.1

###  5.4 Readability evaluation

The _readability_ of crisis reports is crucial to provide information to
practitioners in an understandable way [49]. We considered five dimensions of
readability: grammaticality, non-redundancy, referential clarity, focus,
structure, and coherence [48]. We performed this evaluation through a
crowdsourcing platform,121212SurgeHQ - https://www.surgehq.ai/ and computed
our results by aggregating the assessments of five different annotators.
Annotators were shown an explanation of each annotation dimension before
starting the evaluation.

A total of 43 evaluation rounds were performed, and in each round, the five
annotators were shown independently the six summaries in random ordering. They
were asked to pick one of them as the best in terms of each evaluation
dimension. Then, we computed the best method for each round by majority voting
among the five annotators. The results of the evaluation, shown in Table 10,
indicate that annotators considered summaries generated by CLiQS-D-CM as less
redundant, more referentially clear, more focused, and more structured and
coherent than the summaries generated by other methods. On the other hand,
C-SKIP summaries, which are extractive summaries generated by a centroid-based
method, were considered as more grammatically correct.

Table 10: Readability evaluation of summaries, expressed as the percentage of times a method was chosen as the best for a given dimension (column). The top two methods are extractive, the remaining four are abstractive; ours are marked with an asterisk. |  | Non- | Referential |  | Structure and
---|---|---|---|---|---
Scheme | Grammaticality | Redundancy | Clarity | Focus | Coherence
C-SKIP | 33.5% | 14.9% | 14.9% | 10.2% | 13.0%
CD_DB8 | 0.5% | 4.2% | 2.8% | 2.8% | 1.4%
LSTM+LASER+T5 | 19.5% | 25.6% | 20.0% | 23.7% | 25.6%
Nafi | 1.4% | 1.4% | 5.6% | 4.2% | 1.4%
*CLiQS-CM | 20.0% | 20.9% | 27.0% | 24.7% | 24.2%
*CLiQS-D-CM | 25.1% | 33.0% | 29.8% | 34.4% | 34.4%

###  5.5 Expert Evaluation

The last evaluation involved three experts in emergency management, none of
them a co-author of this paper, working in three different EU countries: (1)
an operations coordinator with a VOST organization, (2) a program manager at a
Civil Protection Department, and (3) a project manager at an Emergency
Management System. Experts were shown 43 pairs of summaries randomly selected
from the five events; in each pair, which one of the summaries was generated
by our method and the other by one of the baselines. Each summary was
accompanied by references (links) to source tweets related to each sentence or
passage in the summary, as in the following example, in which underlined
letters represent links:

> at least 20,000 people have taken refuge in evacuation centers. evacuees
> need masks. there are also many evacuees in need. evacuees need food, water,
> shelter and medical help.[a] more than 30 thousand people evacuated due to
> the eruption of the Taal volcano in the Philippines. Taal volcano eruption
> threatens the lives of more than 900,000 inhabitants. eruption of the Taal
> volcano in the Philippines has caused more than 24,000 people to be
> evacuated. [b,c,d]

The evaluation was performed through an online form and was “blind” in the
sense that the experts did not know, in each pair, which summary was generated
by which method; the ordering of each pair was randomly chosen. We performed
two evaluation rounds, the first one comparing CLiQS-D-CM against Nafi, and
the second one comparing CLiQS-D-CM against LSTM+LASER+T5. Experts were asked
to chose in a 5-points scale whether they (1) preferred summary 1, (2) had a
slight preference for summary 1, (3) considered both summaries equally
preferable, (4) had a slight preference for summary 2, or (5) preferred
summary 2. We additionally asked respondents to optionally comment on the
quality of both summaries, if considered appropriate.

Table 11: Expert evaluation results: percentage of answers received, aggregated across three experts. |  $\leftarrow$ Prefers | Prefers slightly | Both equal | Prefers slightly | Prefers $\rightarrow$ |
---|---|---|---|---|---|---
*CLiQS-CM | 63.6% | 14.7% | 5.4% | 8.5% | 7.8% | Nafi
*CLiQS-CM | 55.8% | 14.0% | 12.4% | 9.3% | 8.5% | LSTM+LASER+T5

The results of the evaluation, shown in Table 11, indicate that the consulted
practitioners clearly preferred summaries generated by the proposed method in
64% of the cases when compared with Nafi, and in 56% of the cases when
compared with LSTM+LASER+T5. Practitioners’ opinions about summaries mentioned
that CLiQS-D-CM summaries were “more accurate and with fewer repetitions,”
“more information and better organized,” “better explained,”“more
understandable,” and they contain “fewer mistakes and more data.” In
comparison, according to their comments, they tended to reject summaries that
contain “contradictory information,” “a lot of repetitions,” “more mistakes
and subjects mixed.” Inspecting the evaluation, we noticed that in general
CLiQS-D-CM’s had lower performance in summaries related to the Zagreb
earthquake event. In contrast, in other events, our method was often
preferred.

##  6 Conclusions, Limitations, and Future Work

We have described a method for generating informative reports about crises
from multilingual social media. This method is based on structured queries,
which are matched against messages that potentially contain the information we
are interested on. Queries are straightforward to construct, which means this
method can be extended to a large variety of information needs. Experiments
with five different disaster events indicate that we can generate high-
quality, readable reports from the messages and that practitioners might
prefer the summaries generated by CLiQS-D-CM to those generated using state-
of-the-art methods.

Limitations. The applicability of our method depends on some resources that
are multilingual but that do not cover all existing languages. Currently, we
use Stanza for POS tagging, and dependency parsing [39] (50 languages
available through community contributions) and LASER embeddings to represent
sentences (93 languages available). Our method only works with 50 languages in
the intersection of those supported by the POS tagger, dependency parser, and
embeddings. Using the proposed method for unsupported languages may require
training new models for the additional languages. In the work, we generated
only English summaries which were useful for practitioners’ evaluation. The
generation of summaries in other languages could show different results. The
proposed approach is flexible and allows including additional categories of
information with help of queries, but we have not tested that at this point.
Finally, the use of sentence embeddings (LASER) allows using the same approach
for other social media (Facebook, Reddit, etc.) but this would require
additional experiments for performance evaluation.

Future work. Our structured queries (keywords, templates, prototypes) are
written in English and then used to rank informative messages in other
languages; it is possible that having multilingual queries could improve the
performance of the system. We are also summarizing information from social
media and comparing it against official reports while using both sources
(e.g., performing contrastive summarization) could help to generate summaries
with extended informativeness and improved veracity. Our method assumes that
messages are geolocated through some external method, while we could make our
method aware of the location of the messages and/or incorporate location
elements into the queries. An envisioned next step for our research is to
aggregate and consolidate extracted claims belonging to the same geographical
region or event and present these summaries through a map and other
information products, potentially integrating them with other information
sources.

Reproducibility. All of the data and code used for the experiments presented
in this paper will be made freely available in a public repository with the
camera-ready version of this paper. Code and data are available in a
repository https://github.com/vitiugin/CLiQS-CM.

Acknowledgments. This work has been partially supported by: "la Caixa"
Foundation (ID 100010434), under the agreement LCF/PR/PR16/51110009; the
Ministry of Science and Innovation of Spain with project "COMCRISIS",
reference code PID2019-109064GB-I00; and the EU-funded "SoBigData++" project,
under Grant Agreement 871042.

## References

  * [1] Carlos Castillo.  Big crisis data: social media in disasters and time-critical situations.  Cambridge University Press, 2016.
  * [2] Joao Porto De Albuquerque, Benjamin Herfort, Alexander Brenning, and Alexander Zipf.  A geographic approach for combining social media and authoritative data towards identifying useful information for disaster management.  International Journal of Geographical Information Science, 29(4):667–689, 2015.
  * [3] Qunying Huang and Yu Xiao.  Geographic situational awareness: mining tweets for disaster preparedness, emergency response, impact, and recovery.  ISPRS International Journal of Geo-Information, 4(3):1549–1568, 2015.
  * [4] Muhammad Imran, Carlos Castillo, Fernando Diaz, and Sarah Vieweg.  Processing social media messages in mass emergency: A survey.  ACM Computing Surveys (CSUR), 47(4):1–38, 2015.
  * [5] Koustav Rudra, Subham Ghosh, Niloy Ganguly, Pawan Goyal, and Saptarshi Ghosh.  Extracting situational information from microblogs during disaster events: a classification-summarization approach.  In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management (CIKM), pages 583–592, 2015.
  * [6] Randy Joy M Ventayen.  Multilingual detection and mapping of emergency and disaster-related tweets.  MATTER: International Journal of Science and Technology, 3(2), 2017\.
  * [7] M. J. Fuadvy and R. Ibrahim.  Multilingual sentiment analysis on social media disaster data.  In 2019 International Conference on Electrical, Electronics and Information Engineering (ICEEIE), volume 6, pages 269–272, 2019.
  * [8] V Lorini, C Castillo, F Dottori, M Kalas, D Nappo, and P Salomon.  Integrating social media into a pan-european flood awareness system: A multilingual approach.  In Proceedings of ISCRAM. 2019.
  * [9] F Vitiugin and C Castillo.  Comparison of social media in english and russian during emergencies and mass convergence events.  In Proceedings of ISCRAM. 2019.
  * [10] Valerio Lorini, Carlos Castillo, Steve Peterson, Paola Rufolo, Hemant Purohit, Diego Pajarito, João Porto de Albuquerque, and Cody Buntain.  Social media for emergency management: Opportunities and challenges at the intersection of research and practice.  In Proceedings of the 18th International Conference on Information Systems for Crisis Response and Management (ISCRAM), page 772–777, 2021.
  * [11] Mikel Artetxe and Holger Schwenk.  Massively multilingual sentence embeddings for zero-shot cross-lingual transfer and beyond.  Transactions of the Association for Computational Linguistics, 7:597–610, 2019.
  * [12] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer.  Journal of Machine Learning Research, 21:1–67, 2020.
  * [13] Amir Karami, Vishal Shah, Reza Vaezi, and Amit Bansal.  Twitter speaks: A case of national disaster situational awareness.  Journal of Information Science, 46(3):313–324, 2020.
  * [14] Anita Saroj and Sukomal Pal.  Use of social media in crisis management: A survey.  International Journal of Disaster Risk Reduction, 48:101584, 2020\.
  * [15] Prashant Khare, Grégoire Burel, Diana Maynard, and Harith Alani.  Cross-lingual classification of crisis data.  In Proceedings of the International Semantic Web Conference, pages 617–633. Springer, 2018.
  * [16] Dat Tien Nguyen, Kamela Ali Al Mannai, Shafiq Joty, Hassan Sajjad, Muhammad Imran, and Prasenjit Mitra.  Robust classification of crisis-related data on social networks using convolutional neural networks.  In Proceedings of the 11th International AAAI Conference on Web and Social Media (ICWSM), 2017.
  * [17] Jens A de Bruijn, Hans de Moel, Albrecht H Weerts, Marleen C de Ruiter, Erkan Basar, Dirk Eilander, and Jeroen CJH Aerts.  Improving the classification of flood tweets with contextual hydrological information in a multimodal neural network.  Computers & Geosciences, page 104485, 2020.
  * [18] Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever.  Improving language understanding by generative pre-training, 2018.
  * [19] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * [20] Junhua Liu, Trisha Singhal, Lucienne TM Blessing, Kristin L Wood, and Kwan Hui Lim.  Crisisbert: a robust transformer for crisis classification and contextual crisis embedding.  In Proceedings of the 32nd ACM Conference on Hypertext and Social Media (HT), pages 133–141, 2021.
  * [21] Hongmin Li, Doina Caragea, and Cornelia Caragea.  Combining self-training with deep learning for disaster tweet classification.  In Proceedings of the 18th International Conference on Information Systems for Crisis Response and Management (ISCRAM), 2021.
  * [22] Telmo Pires, Eva Schlinger, and Dan Garrette.  How multilingual is multilingual bert?  In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics (ACL), pages 4996–5001, 2019.
  * [23] Zewen Chi, Li Dong, Shuming Ma, Shaohan Huang, Saksham Singhal, Xian-Ling Mao, He-Yan Huang, Xia Song, and Furu Wei.  mt6: Multilingual pretrained text-to-text transformer with translation pairs.  In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1671–1683, 2021.
  * [24] Koustav Rudra, Pawan Goyal, Niloy Ganguly, Prasenjit Mitra, and Muhammad Imran.  Identifying sub-events and summarizing disaster-related information from microblogs.  In Proceedings of the 41st International Conference on Research anb Development in Information Retrieval (SIGIR), pages 265–274, 2018.
  * [25] Koustav Rudra, Ashish Sharma, Niloy Ganguly, and Muhammad Imran.  Classifying and summarizing information from microblogs during epidemics.  Information Systems Frontiers, 20(5):933–948, 2018.
  * [26] Himanshu Zade, Kushal Shah, Vaibhavi Rangarajan, Priyanka Kshirsagar, Muhammad Imran, and Kate Starbird.  From situational awareness to actionability: Towards improving the utility of social media data for crisis response.  Proceedings of the ACM Conference on Human-Computer Interaction (CHI), 2(CSCW):1–18, 2018.
  * [27] Nikita Munot and Sharvari S Govilkar.  Comparative study of text summarization methods.  International Journal of Computer Applications, 102(12), 2014.
  * [28] Soumi Dutta, Vibhash Chandra, Kanav Mehra, Sujata Ghatak, Asit Kumar Das, and Saptarshi Ghosh.  Summarizing microblogs during emergency events: A comparison of extractive summarization algorithms.  In Emerging Technologies in Data Mining and Information Security, pages 859–872. Springer, 2019.
  * [29] Hui Lin and Vincent Ng.  Abstractive summarization: A survey of the state of the art.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 9815–9822, 2019.
  * [30] Chenliang Li, Weiran Xu, Si Li, and Sheng Gao.  Guiding generation for abstractive text summarization based on key information guide network.  In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), pages 55–60, 2018.
  * [31] Gaetano Rossiello, Pierpaolo Basile, and Giovanni Semeraro.  Centroid-based text summarization through compositionality of word embeddings.  In Proceedings of the MultiLing 2017 Workshop on Summarization and Summary Evaluation Across Source Types and Genres, pages 12–21, 2017.
  * [32] Aishwarya Jadhav and Vaibhav Rajan.  Extractive summarization with swap-net: Sentences and words from alternating pointer networks.  In Proceedings of the 56th annual meeting of the Association for Computational Linguistics (ACL), pages 142–151, 2018.
  * [33] Jess Kropczynski, Rob Grace, Julien Coche, Shane Halse, Eric Obeysekare, Aurélie Montarnal, Frederick Benaben, and Andrea Tapia.  Identifying actionable information on social media for emergency dispatch.  Proceedings of ISCRAM Asia Pacific, page 11, 2018.
  * [34] Allen Roush.  Cx db8: A queryable extractive summarizer and semantic search engine.  arXiv preprint arXiv:2012.03942, 2020.
  * [35] Nasik Muhammad Nafi, Avishek Bose, Sarthak Khanal, Doina Caragea, and William H Hsu.  Abstractive text summarization of disaster-related document.  In Proceedings of the 17th International Conference on Information Systems for Crisis Response and Management (ISCRAM), 2020.
  * [36] Yisong Chen and Qing Song.  News text summarization method based on bart-textrank model.  In Proceedings of the IEEE 5th Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), volume 5, pages 2005–2010. IEEE, 2021.
  * [37] Anushka Gupta, Diksha Chugh, Rahul Katarya, et al.  Automated news summarization using transformers.  arXiv preprint arXiv:2108.01064, 2021.
  * [38] Ankit Sahu and Sriram G Sanjeevi.  Better fine-tuning with extracted important sentences for abstractive summarization.  In Proceedings of the International Conference on Communication, Control and Information Sciences (ICCISc), volume 1, pages 1–6. IEEE, 2021.
  * [39] Peng Qi, Yuhao Zhang, Yuhui Zhang, Jason Bolton, and Christopher D. Manning.  Stanza: A Python natural language processing toolkit for many human languages.  In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations (ACL), 2020.
  * [40] Matthew Honnibal and Ines Montani.  spacy 2: Natural language understanding with bloom embeddings, convolutional neural networks and incremental parsing.  To appear, 7(1), 2017.
  * [41] Gaurav Bhatt, Aman Sharma, Shivam Sharma, Ankush Nagpal, Balasubramanian Raman, and Ankush Mittal.  On the benefit of combining neural, statistical and external features for fake news identification.  arXiv preprint arXiv:1712.03935, 2017.
  * [42] Fedor Vitiugin and Giorgio Barnabo.  Emotion detection for spanish by combining laser embeddings, topic information, and offense features.  In Proc. of EmoEvalEs at IberLEF, 2021.
  * [43] R McCreadie, C Buntain, and I Soboroff.  Trec incident streams: Finding actionable information on social media.  In Proceedings of ISCRAM. 2019.
  * [44] Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf.  Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter.  arXiv preprint arXiv:1910.01108, 2019.
  * [45] Alexandra Olteanu, Carlos Castillo, Fernando Diaz, and Sarah Vieweg.  Crisislex: A lexicon for collecting and filtering microblogged communications in crises.  In Proceedings of the 8th International AAAI Conference on Weblogs and Social Media (ICWSM), 2014.
  * [46] Alan Akbik, Duncan Blythe, and Roland Vollgraf.  Contextual string embeddings for sequence labeling.  In Proceedings of the 27th International Conference on Computational Linguistics (COLING), pages 1638–1649, 2018.
  * [47] Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q Weinberger, and Yoav Artzi.  Bertscore: Evaluating text generation with bert.  In Proceedings of the International Conference on Learning Representations, 2019.
  * [48] Neslihan Iskender, Aleksandra Gabryszak, Tim Polzehl, Leonhard Hennig, and Sebastian Möller.  A crowdsourcing approach to evaluate the quality of query-based extractive text summaries.  In Proceedings of the 11th International Conference on Quality of Multimedia Experience (QoMEX), pages 1–3. IEEE, 2019.
  * [49] Irina Temnikova, Sarah Vieweg, and Carlos Castillo.  The case for readability of crisis communications in social media.  In Proceedings of the 24th International Conference on World Wide Web (WWW), pages 1245–1250, 2015.

  *[LASER]: Language-Agnostic SEntence Representations
  *[SVM]: Support-Vector Machines
  *[BERT]: Bidirectional Encoder Representations from Transformers
  *[NLP]: Natural Language Processing
  *[BiLSTM]: Bidirectional Long Short-Term Memory
  *[POS]: Part Of Speech
  *[NER]: Named Entity Recognition
  *[LSTMs]: Long Short Term Memory
  *[LSTM]: Long Short Term Memory
  *[MLP]: Multi-Layer Perceptron
  *[GLOVE]: Global Vectors for Word Representation
  *[ERCC]: Emergency Response Coordination Centre


2320213157084

# On non-adaptive majority problems of large query size

Dániel Gerbner  Máté Vizer  Alfréd Rényi Institute of Mathematics

(2021-01-13; 2021-08-06; 2021-10-27)

###### Abstract

We are given $n$ balls and an unknown coloring of them with two colors. Our
goal is to find a ball that belongs to the larger color class, or show that
the color classes have the same size. We can ask sets of $k$ balls as queries,
and the problem has different variants, according to what the answers to the
queries can be. These questions has attracted several researchers, but the
focus of most research was the adaptive version, where queries are decided
sequentially, after learning the answer to the previous query. Here we study
the non-adaptive version, where all the queries have to be asked at the same
time.

###### keywords:

combinatorial search, non-adaptive, majority

##  1 Introduction

A widely studied problem in combinatorial search theory is the so-called
Majority Problem. We are given $n$ indexed balls - say the set
$[n]=\\{1,2,...,n\\}$ \- as an input, each colored in some way unknown to us
with one of two colors. A ball $i\in[n]$ is called majority ball if there are
more than $\frac{n}{2}$ balls in the input set that have the same color as
$i$. We would like to find a ball of the majority color or show that there is
no majority color by asking subsets of $[n]$, that we call queries. We would
like to determine the minimum number of queries needed in the worst case with
an optimal strategy if all the queries are fixed at the beginning. We call
this the non-adaptive version of the Majority Problem. If the queries may
depend on the answers to the previous ones, that we call the adaptive version
of the Majority Problem.

We still need to describe what kind of queries one can use. Each query
corresponds to a subset of size $k$ of the input set. There are different
variants of this problem, according to what the answer to a query is. More
precisely, a model of the Majority Problem is given by $[n]$, the number of
colors, the size of the queries $k$, the possible answers and whether it is
adaptive or non-adaptive. In this paper we deal only with two colors, in the
non-adaptive case. Sometimes we look at the set of queries as a hypergraph
$\mathcal{Q}$, with the queries being the (hyper)edges. We refer to balls also
as vertices.

Models

The most basic model is the pairing model. In this model the size of a query
is two, and the answer is YES, if the two balls have the same color and NO
otherwise.

We note that the adaptive version of this problem, when the number of colors
is not limited was investigated by Fisher and Salzberg [8], who proved that
$\lceil 3n/2\rceil-2$ queries are necessary and sufficient. If the number of
colors is two, then Saks and Werman [14] proved that the minimum number of
queries needed is $n-b(n)$, where $b(n)$ is the number of $1$’s in the diadic
form of $n$. The non-adaptive version was studied in [9].

In this paper we deal with generalizations of the pairing model, when we ask
queries of larger size. The first model of this kind was introduced and
investigated by De Marco, Kranakis and Wiener [6], then many related results
appeared in the literature [2, 3, 5, 7, 10, 11]. However, most of them studied
only the adaptive case.

The authors considered some of these models in [12], and improved the existing
bounds in the adaptive case. Here we investigate the non-adaptive versions. We
remark that the first arXiv version of [12] contained a section on the non-
adaptive case, thus most of our results. Following the suggestion of an
anonymous referee, we removed that part from [12], with the plan of publishing
it separately. We also extended the results slightly.

Hypergraph language.

The queries can be considered as edges of a hypergraph, which we call query
hypergraph and usually denote by ${\mathcal{Q}}$. We introduce some hypergraph
properties, that we will use later. A hypergraph has Property B if its
vertices can be colored with two colors such that there is no monochromatic
edge in the hypergraph, i.e. an edge with vertices of the same color. For
$k\geq 1$, let us denote by $\mathsf{m}(k)$ the cardinality of the edge set of
a smallest $k$-uniform hypergraph that does not have Property B. This
parameter is widely studied, the best lower bound on $\mathsf{m}(k)$ we are
aware of is $\Omega(2^{k}\sqrt{k/\log{k}})$ due to Radhakrishnan and
Srinivasan [13]. For $n\geq 2k-1$ we also consider $\mathsf{m}(k,n)$, which is
the cardinality of a smallest $k$-uniform hypergraph with $n$ vertices that
does not have Property B. Obviously if $n$ is large enough, then we have
$\mathsf{m}(k,n)=\mathsf{m}(k)$.

We also use a similar notion that we call Property $C$. Let $k\geq 2$. We call
a coloring of a $k$-set with two colors balanced if the cardinality of the two
color classes differ by at most one. We say that a hypergraph has Property C
if its vertices can be colored with two colors such that every edge is
balanced. Let us denote by $\mathsf{d}(k)$ the cardinality of the edge set of
a smallest $k$-uniform hypergraph that does not have Property C. We also
consider $\mathsf{d}(k,n)$, which is the cardinality of the edge set of a
smallest $k$-uniform hypergraph with $n$ vertices that does not have Property
C. Obviously, if $n$ is large enough, then we have
$\mathsf{d}(k,n)=\mathsf{d}(k)$.

For odd $k$, Eppstein and Hirschberg [7] proved $\mathsf{d}(k)\leq k+3\log
k+4$. If $k$ is even, this problem can also be formulated as we are looking
for the smallest hypergraph with a positive discrepancy. If $k=2\mod 4$, then
it is easy to see that $\mathsf{d}(k)=3$. Let $snd(i)$ be the smallest
positive integer that does not divide $i$. Alon, Kleitman, Pomerance, Saks and
Seymour [1] and Cherkashin and Petrov [4] proved that there exist constants
$c_{1}$ and $c_{2}$ such that if $k=0\mod 4$, then

$c_{1}\frac{\log snd(k/2)}{\log\log snd(k/2)}\leq\mathsf{d}(k)\leq c_{2}\log
snd(k).$

Structure of the paper.

The rest of the paper is organised as follows: in Section 2 we introduce the
models and state the known results in the adaptive setting. In Section 3, 4
and 5 we state and prove our results regarding the different models.

##  2 Models

In this section we define the models we study, and state the results known in
the adaptive case. Three of the models were introduced by De Marco and
Kranakis [5], and their (adaptive) bounds were improved by Eppstein and
Hirschberg [7] and by the authors [12]. The last one was introduced by
Borzyszkowski [2], who found the exact answer in the adaptive case. In each of
these models, we are given $n$ indexed balls, colored with two colors, and we
ask queries of size $k$ ($k\geq 2$) that we denote by $Q$. The models differ
only in the possible answers to the queries, thus we emphasize what the
answers can be. We give each model an abbreviation that we indicate after its
name. If the abbreviation is $X$, then we will denote by $A(X,k,n)$ and
$N(X,k,n)$ the number of queries needed to ask in the worst case of the
adaptive/nonadaptive version of that model, respectively.

###  2.1 Models, adaptive results

$\bullet$ Output (or Partition) Model = OM:

$\mathbf{Answer:}$ $\\{Q^{\prime},Q^{\prime\prime}\\}$, a partition of $Q$,
where $Q^{\prime}$ is the set of balls of one color and $Q^{\prime\prime}$ of
the other color. No indication is provided about which of the colors is in
$Q^{\prime}$.

In the following theorem, the upper bound if $n$ is even is due to De Marco
and Kranakis [5], while the other bounds are due to Eppstein and Hirschberg
[7].

######  Theorem 1 (Eppstein, Hirschberg [7], De Marco, Kranakis [5]).

For all $2\leq k\leq n$ we have

$A(OM,k,n)\geq\left\\{\begin{array}[]{l
l}\lceil\frac{n-1}{k-1}\rceil&\textrm{if $k$ is odd,}\\\
\frac{n}{k-1}-O(n^{1/3})&\textrm{if $k$ is even,}\\\ \end{array}\right.$

$A(OM,k,n)\leq\left\\{\begin{array}[]{l
l}\lceil\frac{n-1}{k-1}\rceil&\textrm{if $n$ is even,}\\\
\lceil\frac{n-2}{k-1}\rceil&\textrm{if $n$ is odd.}\\\ \end{array}\right.$

$\bullet$ Counting Model = CM:

$\mathbf{Answer:}$ a number $i\leq k/2$ such that the query has exactly $i$
balls of one of the color classes (thus $k-i$ balls of the other color class).

In the following result, the upper bound is due to Eppstein and Hirschberg [7]
, while the lower bound is due to Gerbner and Vizer [12].

######  Theorem 2 (Eppstein, Hirschberg [7],Gerbner, Vizer [12]).

For all $2\leq k<n$ we have

$\frac{6n}{5k+6}-c(k)\leq
A(CM,k,n)\leq\frac{n}{\lfloor\frac{k}{2}\rfloor}+O(k),$

where $c(k)$ depends only on $k$.

$\bullet$ General (or Yes-No) Model = GM:

$\mathbf{Answer:}$ YES, if there exist two balls of different colors, NO
otherwise.

######  Theorem 3 (Gerbner, Vizer [12]).

For any $2\leq k<n$ with $2k-1\leq n$ we have

$\frac{3n+5}{4}\leq A(GM,k,n)\leq n-k+\mathsf{m}(k).$

$\bullet$ Borzyszkowski’s Model = BM, [6, 2]:

$\mathbf{Answer:}$ YES, if there exist two balls of different colors, and such
a pair is pointed out, NO if all balls have the same color.

######  Theorem 4 (Borzyszkowski [2]).

For all $3\leq k\leq n$ with $2k-3\leq n$ we have

$A(BM,k,n)=\left\\{\begin{array}[]{l l}\frac{n}{2}+k-2&\textrm{if $n$ is
even,}\\\ \lfloor\frac{n}{2}\rfloor+k-3&\textrm{if $n$ is odd.}\\\
\end{array}\right.$

### Basic inequalities

By definition, the following inequalities hold for the above models for all
$2\leq k\leq n$: $N(OM,k,n)\leq N(CM,k,n)\leq N(GM,k,n)$ and $N(OM,k,n)\leq
N(BM,k,n)\leq N(GM,k,n).$

##  3 Output model

######  Theorem 5.

For $2\leq k\leq n$ we have

$N(OM,k,n)=\left\\{\begin{array}[]{l l}\lceil\frac{n-1}{k-1}\rceil&\textrm{if
$n$ is even,}\\\ \lceil\frac{n-2}{k-1}\rceil&\textrm{if $n$ is odd.}\\\
\end{array}\right.$

###### Proof.

A hypergraph is connected if we cannot partition the underlying set into two
parts such that no edge contains vertices from both parts. Observe that the
least number of edges of a connected $k$-uniform hypergraph on an $n$-element
underlying set is $\lceil\frac{n-1}{k-1}\rceil$. Indeed, we can build one by
taking an arbitrary set of size $k$, and add new edges that intersect the
union of the earlier ones in one element. On the other hand, if we are given a
connected hypergraph, and we take an arbitrary set from it, there must exist
another set that intersects it, then another set that intersects the union of
the earlier ones, and so on. Similarly, if a hypergraph has $d$ connected
components, then the least number of edges it can have is
$\lceil\frac{n-d}{k-1}\rceil$.

It is easy to see that if the query hypergraph ${\mathcal{Q}}$ is connected,
we find more than a majority ball; we find the partition to color classes.
This proves the upper bound in case $n$ is even. If $n$ is odd, we can ask a
connected query hypergraph on $n-1$ vertices. A ball that is a majority ball
among those vertices is also a majority ball in the whole set of balls, while
if there is no majority ball there, then the remaining ball is a majority
ball. This finishes the proof of the upper bound.

Let us continue with the lower bound. If the query hypergraph ${\mathcal{Q}}$
is disconnected and $n$ is even, we consider an arbitrary partition of the
underlying set of balls into two parts with no edge intersecting both. Then
the answers might be that in both parts one of the color classes is larger by
the same number $l>0$. What we mean is that we take a coloring with the above
property, and then the answers do not tell any further information. If the
larger color class is the same color in the parts, there is majority,
otherwise there is not. We cannot find out which one is the case, hence we
cannot show a majority ball. This finishes the proof in case $n$ is even. If
$n$ is odd, and the underlying set can be partitioned into three parts such
that no edge contains vertices from two parts, then it is possible that in
each part the difference between the size of the color classes is 1 or 2. In
this case no majority ball can be shown. We have already mentioned that is
easy to see that at least $\lceil\frac{n-2}{k-1}\rceil$ queries are needed to
avoid this. ∎

##  4 Counting model

######  Theorem 6.

For $2\leq k,n$ with $2k-1\leq n$ we have

$N(CM,k,n)\leq\left\\{\begin{array}[]{l l}n-k+1&\textrm{if $k$ is even},\\\
(n-k+1)\times(1+\mathsf{d}(k-1,n))&\textrm{if $k$ is odd.}\\\
\end{array}\right.$

###### Proof.

If $k$ is even, then we ask all the $k$-sets containing a given $(k-1)$-set
$A\subset[n]$. Note that - using that $k$ is even - we know that
$i,j\in[n]\setminus A$ have the same color if and only if the answers to the
queries $A\cup\\{i\\}$ and $A\cup\\{j\\}$ are the same. Thus we can partition
$[n]\setminus A$ into two parts such that the balls in each part have the same
color. Additionally, if we ever get different answers for two such queries,
then we know the number of balls of the corresponding colors inside $A$ and we
can choose a majority ball or find out that there is none. If this is not the
case, then - knowing that $n\geq 2k-1$ \- we have that all balls in
$[n]\setminus A$ are of the majority color.

If $k$ is odd, then the previous argument does not work, as the answers to
some queries could be that there are $(k+1)/2$ and $(k-1)/2$ balls of the two
colors, even if the balls added to $A$ are of different color. However, it
cannot happen if $A$ contains different number of red and blue balls. So we
use unbalanced colorings here. Let us take a $(k-1)$-uniform hypergraph
$\mathcal{F}$ on $[n]$ that does not have Property C and has cardinality
$\mathsf{d}(k-1,n)$. Moreover, if every pair of edges in $\mathcal{F}$ has
intersection of size at least $(k-3)/2$, then we add another edge of size
$k-1$ that intersects one of them in a set of size less than $(k-3)/2$. This
way we get a hypergraph $\mathcal{F}^{\prime}$, and the query set consists of
all $k$-sets containing edges of $\mathcal{F}^{\prime}$. There is a set
$F\in\mathcal{F}^{\prime}$ that is unbalanced, i.e. it contains at least
$(k+1)/2$ ball of the same color, say blue.

If every answer (to every query) were the number $(k-1)/2$, then all the balls
not in $F$ would be red. In this case there would be exactly $(k+1)/2$ blue
balls and every member of $\mathcal{F}^{\prime}$ would contain at least
$(k-1)/2$ of them. Then their intersection would have size at least $(k-3)/2$,
a contradiction. That is why we added the additional set to $\mathcal{F}$.

Thus there is an answer different from $(k-1)/2$. Now similarly to the case
when $k$ is even, we can find $F$, and then we know the relation of the
outside balls to each other, and the number of the balls of the corresponding
colors inside $F$. ∎

######  Theorem 7.

For $2\leq k$ and sufficiently large $n$ we have

$N(CM,k,n)\geq\left\\{\begin{array}[]{l l}2n/(k+1)&\textrm{if $k$ is even and
$n$ is even},\\\ (2n-1)/(k+1)&\textrm{if $k$ is even and $n$ is odd}.\\\
\lceil\frac{n}{k}\mathsf{d}(k-1,n-1)\rceil&\textrm{if $k$ is odd, $n$ is even
and large enough},\\\ \lceil\frac{n-1}{2k}\mathsf{d}(k-1,n-1)\rceil&\textrm{if
$k$ is odd, $n$ is odd and large enough}.\\\ \end{array}\right.$

###### Proof.

To prove the lower bound for $k$ even and $n$ even, we first show that any
query can contain at most one vertex of degree one. Indeed, suppose a query
$Q$ contains $i$ and $j$ (with $i\neq j$) of degree one, then it is possible
that the answer to $Q$ is the number $(k-2)/2$ and there are $(k-2)/2$ red and
$(k-2)/2$ blue balls besides $i$ and $j$ in $Q$. Furthermore, it is possible
that altogether there are $n/2$ blue and $(n-4)/2$ red balls besides $i$ and
$j$. We know that $i$ and $j$ have the same color, but we do not know if it is
blue or red. Thus we do not know if there is a majority color or not.

Let $q$ denote the number of queries, and $x\leq q$ be the number of vertices
of degree one. First we show that there is no vertex of degree 0. Indeed
suppose that there is a vertex $v$ of degree 0. Then it is possible that among
the other vertices, the number of blue balls is larger than the number of red
balls by one. In this case we do not know that there is a majority ball or
not, as we do not know anything about the color of $v$. Therefore, we have at
least $n-x$ vertices of degree at least 2. Thus, the number of pairs $(Q,w)$
where $Q$ is a query, $w$ is a vertex and $w\in Q$ (i.e. the sum of the
degrees) is at least $2(n-x)+x$. On the other hand, this number is exactly
$kq$. Thus we have $kq\geq 2n-x\geq 2n-q$ and rearranging gives the bound.

In the other cases below, we just state and prove the degree conditions that
are needed to obtain the desired bound, and omit the similar easy calculation
that finishes the proof.

In the case $k$ is even and $n$ is odd, it is enough to show that at most one
query can contain two elements of degree one. We prove it by contradiction,
since otherwise we can get two monochromatic pairs, and it is possible that
there are $(n-1)/2$ blue and $(n-7)/2$ red balls besides those four balls. In
this case we cannot show a majority ball.

In the case $k$ is odd, while $n$ is even and large enough, it is enough to
show that for every $i\in[n]$, its degree is at least $\mathsf{d}(k-1,n-1)$.
This is true, since otherwise we can color the hypergraph with vertex set
$\cup\\{Q:i\in Q\\}\setminus\\{i\\}$ and edge set $\\{Q\setminus\\{i\\}:i\in
Q\\}$ (the open neighborhood hypergraph or link hypergraph of $i$) in a
balanced way, thus we do not get any information about the color of $i$. Then
- using that $n$ is large enough and even - we can color the remaining
elements (i.e. $[n]\setminus\cup\\{Q:i\in Q\\}$) such that the coloring of all
the balls is balanced. But then it depends on the color of $i$ if there is a
majority color or not.

If $n$ is odd, a similar argument shows that all but one of the balls have
degree at least $\mathsf{d}(k-1,n-1)/2$. Indeed, otherwise there are
$i,j\in[n]$ with $i\neq j$ such that less than $\mathsf{d}(k-1,n-1)$ queries
contain at least one of $i$ or $j$. Let ${\mathcal{F}}$ be the hypergraph that
has these queries as edges. Let us remove $i$ and $j$ from them and for those
queries containing both $i$ and $j$, we add a new ball $s\not\in[n]$ instead.
The resulting $(k-1)$-uniform hypergraph ${\mathcal{F}}^{\prime}$ has less
than $\mathsf{d}(k-1,n-1)$ edges, thus it has Property C. This gives a
coloring that is balanced on every edge of $\mathcal{F}^{\prime}$. Let red be
the color of $s$. This coloring can be extended to all the balls except for
$i$ and $j$ such a way that there are $(n-1)/2$ blue and $(n-3)/2$ red balls
among the balls in $[n]\setminus\\{i,j\\}$. Then the answers to queries
containing neither $i$ nor $j$ are according to this coloring. Moreover, a
query $Q$ containing exactly one of them can also be answered according to
this coloring without knowing the colors of $i$ and $j$, as
$Q\setminus\\{i,j\\}$ is balanced. Finally the answer to queries containing
both $i$ and $j$ is the number $(k-1)/2$. It is easy to see that if at least
one of $i$ and $j$ is red, the answers are consistent with the coloring. Thus
any color can be minority (i.e. not majority), hence a ball different from $i$
and $j$ cannot be the majority ball, as we know its color. But $i$ can be red
and $j$ blue, or the other way around. In that case the red ball is in
minority, thus we cannot say that $i$ or $j$ is a majority ball, finishing the
proof. ∎

The above theorem can be improved with similar, but more involved arguments,
as we show below. For simplicity, we only deal with the case when $k$ and $n$
are both even.

######  Theorem 8.

If $k$ is even and large enough, and $n$ is even, then we have

$N(CM,k,n)\geq\frac{n(5ik-k+i+i^{2})-2(k-i)}{(2k+3+i)ik}$

for every $k/2<i<k$. In particular, for every $\varepsilon$, there is a
$k_{0}$ such that if $k>k_{0}$ is even, then there is an $n_{0}(k)$, such that
if $n>n_{0}(k)$ is even, then $N(CM,k,n)>(11/5-\varepsilon)n/k$.

We remark that for any specific $k$, one can easily obtain from the first part
of the above theorem a lower bound for $N(CM,k,n)$ with a simple calculation.
For example, if $k=8$, then $i=5$ gives the best lower bound, and it is
slightly larger than the lower bound $2n/9$ from Theorem 7.

###### Proof.

Let ${\mathcal{F}}$ be the subhypergraph of the query hypergraph
${\mathcal{Q}}$ having as edges those queries that contain at least $i+1$
vertices of degree at most 2. Let ${\mathcal{F}}^{\prime}$ be the multi-
hypergraph obtained from ${\mathcal{F}}$ by deleting the vertices of degree
more than 2 from each edge. Note that ${\mathcal{F}}^{\prime}$ may be non-
uniform.

######  Claim 9.

The total size of ${\mathcal{F}}^{\prime}$, i.e. the sum of the edge sizes is
at most $2k+(i+1)n/i$.

###### Proof of Claim.

First we show that ${\mathcal{F}}^{\prime}$ is a linear hypergraph. Indeed,
otherwise there are two queries $Q_{1}\in{\mathcal{Q}}$ and
$Q_{2}\in{\mathcal{Q}}$ sharing two balls $x$ and $y$ that do not appear in
any other query. Then one can color the other balls of $Q_{1}$ and $Q_{2}$
such a way that both $Q_{1}$ and $Q_{2}$ have $(k-2)/2$ red and $(k-2)/2$ blue
balls besides $x$ and $y$. Furthermore, one can color the other balls such
that there are $n/2$ blue and $(n-4)/2$ red balls besides $x$ and $y$. Then
the answer to every query is according to this coloring, and the answer to
$Q_{1}$ and $Q_{2}$ is the number $(k-2)/2$. Then we know $x$ and $y$ have the
same color, but we do not know if it is blue or red, thus we do not know if
there is a majority color or not.

Next we show that ${\mathcal{F}}^{\prime}$ does not contain any linear cycle
covering at most $n/2+3$ vertices. A linear cycle of length $\ell$ consists of
$\ell$ edges $h_{1},\dots,h_{\ell}$ such that the only intersections among
those are the singleton intersections $v_{j}$ of $h_{j}$ and $h_{j+1}$ for
every $j$, modulo $\ell$ (i.e. we also have the singleton intersection
$v_{\ell}$ of $h_{\ell}$ and $h_{1}$). Let $V=\\{v_{1},\dots,v_{\ell}\\}$.

Assume that there is a linear cycle of length $\ell$ covering $m\leq n/2+3$
vertices, and for every $j$, let $Q_{j}$ denote the query that $h_{j}$ was
obtained from. We define a coloring of all the balls not in $V$ such that this
coloring already determines the answers to every query in $Q$, but does not
determine whether there is a majority ball (hence it leads to a
contradiction).

We first color the vertices that are in some $Q_{j}$ but not in any
$h_{j^{\prime}}$ with $j\neq j^{\prime}$, to red. Then we go through the edges
$h_{j}$ in an arbitrary order, and color the vertices in $h_{j}\setminus V$,
such a way that every $Q_{j}$ contains $(k-2)/2$ blue balls and $(k-2)/2$ red
balls not in $V$. This is doable, as only the vertices of $Q_{j}\setminus
h_{j}$, thus at most $k-(i+1)\leq(k-2)/2$ balls of $h_{i}$ had been colored
(to red) when we arrived to $h_{i}$. Observe that we colored to blue only the
vertices covered by the linear cycle, except the vertices
$v_{1},\dots,v_{\ell}$ and $\ell\geq 3$. Therefore, we have colored
$m-\ell\leq n/2$ vertices to blue so far. We claim that so far the number of
blue balls is at least the number of red balls. Indeed, for each $j\leq\ell$,
we colored $(k-2)/2$ vertices in $h_{j}\setminus V$ to blue. As these sets are
vertex-disjoint, there are $\ell(k-2)/2$ blue balls. Similarly, for each
$j\leq\ell$, we colored $(k-2)/2$ vertices in $Q_{j}$ to red, thus there are
at most $\ell(k-2)/2$ red balls.

Now we can color the remaining balls (besides those in $V$) so that there are
$n/2$ blue and $n/2-\ell$ red balls. Then we can give an answer to every
$Q_{j}$ as the number $(k-2)/2$, and answer every other query according to
this coloring. Then we know that every ball in $V$ has the same color, but we
do not know if it is blue or red, thus we do not know if there is a majority
color or not.

This implies that every linear cycle in ${\mathcal{F}}^{\prime}$ has more than
$n/2+3$ vertices. Next we show that ${\mathcal{F}}^{\prime}$ contains at most
three linear cycles. Let ${\mathcal{L}}$ and ${\mathcal{L}}^{\prime}$ be two
linear cycles in ${\mathcal{F}}^{\prime}$ with edges $h_{1},\dots,h_{\ell}$
and $h^{\prime}_{1},\dots,h^{\prime}_{\ell^{\prime}}$ Then by the pigeonhole
principle they share at least two vertices. We claim that ${\mathcal{L}}$ and
${\mathcal{L}}^{\prime}$ have to share a linear subpath and nothing more (a
linear path is a linear cycle without one of the edges, or a single edge, or a
single vertex). Indeed, otherwise they share two subpaths, thus following
${\mathcal{L}}^{\prime}$, one leaves ${\mathcal{L}}$ and returns to it at
least twice. It is easy to see that this way we can find two vertex disjoint
linear cycles, a contradiction.

Therefore, for some vertices $x$ and $y$ there are three linear paths
${\mathcal{P}}_{1},{\mathcal{P}}_{2},{\mathcal{P}}_{3}$ between $x$ and $y$
that share only these two vertices. These paths define three linear cycles. We
claim that these are all the linear cycles in ${\mathcal{F}}^{\prime}$.

A fourth cycle intersects each of our three cycles multiple times, in
particular it intersects two of the paths, say ${\mathcal{P}}_{1}$ and
${\mathcal{P}}_{2}$. It has a linear subpath ${\mathcal{P}}_{4}$ between
vertices $u$ in ${\mathcal{P}}_{1}$ and $v$ in ${\mathcal{P}}_{2}$ such that
${\mathcal{P}}_{4}$ shares only $u$ and $v$ with our three cycles. Let $l_{j}$
denote the number of vertices in ${\mathcal{P}}_{j}$, then
$l_{4}+(l_{1}+l_{2})/2>n/2+3$, because ${\mathcal{P}}_{4}$ forms a cycle with
any of the two paths between $u$ and $v$ in
${\mathcal{P}}_{1}\cup{\mathcal{P}}_{2}$. On the other hand,
$l_{1}+l_{3}>n/2+3$ and $l_{2}+l_{3}>n/2+3$, thus
$(l_{1}+l_{2})/2+l_{3}>n/2+3$. Adding up the above inequalities, we obtain
$l_{1}+l_{2}+l_{3}+l_{4}>n+6$, a contradiction.

Now we can delete two edges of ${\mathcal{F}}^{\prime}$ to obtain a linear
hypergraph ${\mathcal{F}}^{\prime\prime}$ without any linear cycles. We show
that this cycle-free property implies that sum of the degrees of
${\mathcal{F}}^{\prime\prime}$ is at most $(i+1)n/i$ (which completes the
proof of the claim). Indeed, we can build ${\mathcal{F}}^{\prime\prime}$ the
following way. We start with an arbitrary edge, and build a connected
component by adding a new edge sharing one vertex with the component. If a
component is finished, we start again with a disjoint edge and repeat this.
This way every new edge adds $j+1$ to the sum of the degrees for some $j\geq
i$, but also increases by $j$ the number of the vertices used. As
$(j+1)/j\leq(i+1)/i$, we will get the largest total size if we add an edge of
size $i+1$ all the time, that is, at most $n/i$ times. ∎

We also use that any query in ${\mathcal{Q}}$ has at most one vertex of degree
one, which we obtained at the beginning of the proof of Theorem 7.

Let us count the total sum $D$ of the degrees in ${\mathcal{Q}}$. On the one
hand, $D$ is obviously $k|{\mathcal{Q}}|$, because every query adds $k$ to the
sum. But look at this more precisely. Let $D^{\prime}$ be total sum of the
degrees of balls with degree 1 or 2, and $D^{\prime\prime}$ be total sum of
the degrees of balls with degree greater than 2, thus we have
$k|{\mathcal{Q}}|=D=D^{\prime}+D^{\prime\prime}$. Let us look at
$D^{\prime}+D^{\prime\prime}$ in a different way. For a query $Q$, let us
denote by $q^{\prime}(Q)$ the number balls in $Q$ with degree 1 or 2, and by
$q^{\prime\prime}(Q)$ the number of balls in $Q$ with degree greater than 2.
We say that $Q$ adds $q^{\prime}(Q)$ to $D^{\prime}$ and $q^{\prime\prime}(Q)$
to $D^{\prime\prime}$, since
$D^{\prime}=\sum_{Q\in{\mathcal{Q}}}q^{\prime}(Q)$ and
$D^{\prime}=\sum_{Q\in{\mathcal{Q}}}q^{\prime\prime}(Q)$.

If a query is not in ${\mathcal{F}}$, it adds to $D^{\prime\prime}$ at least
$(k-i)/i$ times as much as it adds to $D^{\prime}$. The queries in
${\mathcal{F}}$ altogether add at most $2k+(i+1)n/i$ to $D^{\prime}$. These
imply that $D^{\prime}\leq
iD^{\prime\prime}/(k-i)+2k+(i+1)n/i=i(k|Q|-D^{\prime})/(k-i)+2k+(i+1)n/i$,
thus $D^{\prime}\leq i|{\mathcal{Q}}|+2(k-i)+(i+1)(k-i)n/ik$.

Let $a$ be the number of balls of degree 1, $b$ be the number of balls of
degree 2 and $c$ be the number of balls of degree greater than 2. Then
$a\leq|{\mathcal{Q}}|$, $n=a+b+c$, $D^{\prime}=a+2b$ and $D^{\prime\prime}\geq
3c$. Thus $n\leq|{\mathcal{Q}}|/2+D^{\prime}/2+D^{\prime\prime}/3$, i.e.
$6n\leq
3|{\mathcal{Q}}|+3D^{\prime}+2D^{\prime\prime}=(2k+3)|{\mathcal{Q}}|+D^{\prime}\leq(2k+i+3)|{\mathcal{Q}}|+2(k-i)+(i+1)(k-i)n/ik$.
This implies $|{\mathcal{Q}}|\geq\frac{n(5ik-k+i+i^{2})-2(k-i)}{(2k+3+i)ik}$.
By choosing $i$ to be $k/2+1$, it is easy to see that this lower bound divided
by $n/k$ converges to $11/5$, which finishes the proof. ∎

##  5 General model and Borzyszkowski’s model

######  Theorem 10.

For $2\leq k$ and $2k-1\leq n$, we have

$N(BM,k,n)\leq N(GM,k,n)\leq(n-k+1)\times\mathsf{m}(k-1,n-1).$

###### Proof.

We consider a $(k-1)$-uniform hypergraph $\mathcal{F}$ of size
$\mathsf{m}(k-1,n-1)$ on $n-1$ vertices that does not have property B. Then we
add an additional $n$th vertex. We query each set of size $k$ that contains an
edge of $\mathcal{F}$, thus at most $(n-k+1)\mathsf{m}(k-1,n-1)$ sets. If we
get a NO answer, we can identify a monochromatic member $F$ of $\mathcal{F}$,
which is queried together with every other ball, thus we find out if the other
balls have the same color as balls in $F$ or not, i.e. we can identify the
color classes. Otherwise, as we know that there is a monochromatic member $F$
of $\mathcal{F}$, every ball in $[n]\setminus F$ is the other color, thus
majority ball, because of $2k-1\leq n$. In particular the ball not in members
of ${\mathcal{F}}$ is a majority ball. ∎

######  Theorem 11.

Let $k\geq 3$ and $n$ be large enough.

$\bullet$ If $n$ is even, then we have $f(n,k)\times\mathsf{m}(k-1)\leq
N(BM,k,n)\leq N(GM,k,n)$.

$\bullet$ If $n$ is odd, then we have $f(n,k)\times\mathsf{m}(k-1)\leq
N(GM,k,n)$ and

$f(n,k)\times\mathsf{m}(k-2)\leq N(BM,k,n)$, where

$f(n,k):=\left\\{\begin{array}[]{l l}\frac{n}{k}&\textrm{if $n$ is even},\\\
\frac{n-1}{2k}&\textrm{if $n$ is odd.}\\\ \end{array}\right.$

###### Proof.

Let us start with the General Model for even $n$. We prove that every ball $i$
has degree at least $\mathsf{m}(k-1)$. Indeed, otherwise it is possible that
the set $\bigcup\\{Q:i\in Q\\}\setminus\\{i\\}$ is colored by blue and red in
such a way, that no edge in the open neighborhood hypergraph of $i$ is
monochromatic. Thus one can answer such a way that the color of $i$ does not
change any answers. As $n$ is large enough, these less than $\mathsf{m}(k-1)$
queries contain less than $n/2$ balls, hence we can color the remaining balls
such a way that $n/2$ of them are red and $n/2-1$ of them are blue. As $i$ can
be of any color, we do not know if there is a majority ball or not.

If $n$ is odd, we will use a similar argument to the proof of Theorem 7 to
show that all but one balls have degree at least $\mathsf{m}(k-1)/2$. Indeed,
otherwise there are less than $\mathsf{m}(k-1)$ queries containing either $i$
or $j$. Let ${\mathcal{F}}\subset{\mathcal{Q}}$ be the hypergraph having those
queries as edges. Let us remove $i$ and $j$ from them, and for those queries
containing both we add a new ball $s\not\in[n]$. The resulting $(k-1)$-uniform
hypergraph ${\mathcal{F}}^{\prime}$ has less than $\mathsf{m}(k-1)$ edges,
thus it has Property B. This gives a coloring on a subset of
$[n]\setminus\\{i,j\\}\cup\\{s\\}$ without a monochromatic edge, let red be
the color of $s$. So far less than $\mathsf{m}(k-1)(k-1)$ balls have colors,
thus we can extend this coloring to all the balls except for $i$ and $j$ such
a way that there are $(n-1)/2$ blue and $(n-3)/2$ red balls among the balls in
$[n]\setminus\\{i,j\\}$. Then we answer according to this coloring, and in
particular we answer YES to queries containing one of $i$ and $j$ (as both
colors appear among the balls in those queries). We also answer YES to the
queries containing both $i$ and $j$. We know that those queries contain a blue
ball different from $i$ and $j$. Therefore, it is easy to see that if one of
$i$ and $j$ is red, the answers are consistent with the coloring. Thus any
color can be minority, hence another ball cannot be the majority ball, as we
know its color. But $i$ can be red and $j$ blue, or the other way around. In
that case the red ball is in minority, thus we cannot claim $i$ or $j$ is a
majority ball, finishing the proof for the General model.

In Borzyszkowski’s Model, if $n$ is even, the same proof works, as we can
point out a pair of balls not equal to $i$ in every query. If $n$ is odd, the
same proof does not work, as it is possible that only $s$ is of color red in a
query. In that case either $i$ or $j$ has to be put in the pair that is
pointed out, thus we might find out its color. However, we can show that all
but one of the balls have to be contained in at least $\mathsf{m}(k-2)/2$
queries. Indeed, otherwise there are less than $\mathsf{m}(k-2)$ queries
containing either $i$ or $j$. Let ${\mathcal{G}}$ be the hypergraph that has
those queries as edges, and remove $i$ and $j$ from them, and for those
queries containing only one of $i$ and $j$, we remove another arbitrary ball.
The resulting $(k-2)$-uniform hypergraph ${\mathcal{G}}^{\prime}$ has less
than $\mathsf{m}(k-2)$ edges, thus it has Property B. From here it works as in
the General model: We find a coloring without a monochromatic edge, then
extend this coloring to all the balls but $i$ and $j$, such a way that there
are $(n-1)/2$ blue and $(n-3)/2$ red balls. Then answer according to this
coloring, in particular we can answer YES and point out a pair of two balls of
different colors without using $i$ and $j$. By the same reasoning as in the
case of the General model, any ball can be a minority ball, finishing the
proof. ∎

##  6 Acknowledgement

We thank the reviewer for the careful review, which helped to improve the
presentation of the manuscript a lot.

Research was supported by the National Research, Development and Innovation
Office - NKFIH under the grants FK 132060, KH130371, KKP-133819 and SNN
129364. Research of Vizer was supported by the János Bolyai Research
Fellowship and by the New National Excellence Program under the grant number
UNKP-20-5-BME-45.

## References

  * [1] N. Alon, D.J. Kleitman, C. Pomerance, M. Saks, P. Seymour. The smallest $n$-uniform hypergraph with positive discrepancy. Combinatorica, 7(2), 151–160, 1987.
  * [2] A. M. Borzyszkowski. Computing majority via multiple queries. Theoretical Computer Science, 539, 106–111, 2014.
  * [3] Huilan Chang, Dániel Gerbner, and Balázs Patkós. Finding non-minority balls with majority and plurality queries. Discrete Applied Mathematics, 284(30) 631–639, 2020.
  * [4] D. Cherkashin, F. Petrov. On small $n$-uniform hypergraphs with positive discrepancy. Journal of Combinatorial Theory, Series B, 139, 353–359, 2019.
  * [5] G. De Marco, E. Kranakis. Searching for majority with $k$-tuple queries. Discrete Mathematics, Algorithms and Applications, 7(02), 1550009, 2015.
  * [6] G. De Marco, E. Kranakis, G. Wiener. Computing Majority with Triple Queries. Proceedings of COCOON 2011, Lecture Notes inComputer Science 6842, 604–611, 2011.
  * [7] D. Eppstein, D. S. Hirschberg. From Discrepancy to Majority. Algorithmica, 80, 1278–1297, 2018.
  * [8] M.J. Fisher, S.L. Salzberg. Finding a Majority Among n Votes. J. Algorithms, 3, 375–379, 1982.
  * [9] D. Gerbner, G. O. H. Katona, D. Pálvölgyi, B. Patkós. Majority and plurality problems. Discrete Applied Mathematics, 161(6), 813–818, 2013.
  * [10] D. Gerbner, B. Keszegh, D. Pálvölgyi, B. Patkós, M. Vizer, G. Wiener. Finding a non-minority ball with majority answers. Discrete Applied Mathematics, 219, 18–31, 2017.
  * [11] D. Gerbner, D. Lenger, M. Vizer. A plurality problem with three colors and query size three. arXiv preprint arXiv:1708.05864, 2017
  * [12] D. Gerbner, M. Vizer. Majority problems of large query size. Discrete Applied Mathematics, 254, 124–134, 2019.
  * [13] J. Radhakrishnan, A. Srinivasan. Improved bounds and algorithms for hypergraph 2-coloring. Random Structures and Algorithms, 16(1), 4–-32, 2000.
  * [14] M. E. Saks, M. Werman. On computing majority by comparisons. Combinatorica, 11, 383–387, 1991.