# One Model, Multiple Modalities: A Sparsely Activated Approach for Text,
Sound, Image, Video and Code

Yong Dai∗, Duyu Tang , Liangxin Liu∗, Minghuan Tan∗, Cong Zhou∗, Jingquan
Wang∗,
Zhangyin Feng, Fan Zhang, Xueyu Hu, Shuming Shi

Tencent AI Lab Correspondence to: Duyu Tang (duyutang@tencent.com), ∗
indicates equal contribution

###### Abstract

People perceive the world with multiple senses (e.g., through hearing sounds,
reading words and seeing objects). However, most existing AI systems only
process an individual modality. This paper presents an approach that excels at
handling multiple modalities of information with a single model. In our
“SkillNet” model, different parts of the parameters are specialized for
processing different modalities. Unlike traditional dense models that always
activate all the model parameters, our model sparsely activates parts of the
parameters whose skills are relevant to the task. Such model design enables
SkillNet to learn skills in a more interpretable way. We develop our model for
five modalities including text, image, sound, video and code. Results show
that, SkillNet performs comparably to five modality-specific fine-tuned
models. Moreover, our model supports self-supervised pretraining with the same
sparsely activated way, resulting in better initialized parameters for
different modalities. We find that pretraining significantly improves the
performance of SkillNet on five modalities, on par with or even better than
baselines with modality-specific pretraining. On the task of Chinese text-to-
image retrieval, our final system achieves higher accuracy than existing
leading systems including Wukong${}_{\text{ViT-B}}$ and Wenlan 2.0 while using
less number of activated parameters.

##  1 Introduction

In recent years, Transformer [40] and Transformer-based pretrained models [12,
35] have revolutionized natural language processing [33] and there have been
growing interests in extending the successful paradigm to broader artificial
intelligence areas including computer vision [8, 23, 32], speech processing
[4] and program analysis [18]. Researchers from different communities have no
communication barrier and typically repeat the same process: pretraining for
each modality and finetuning all the model parameters for each task.

Despite the remarkable progress made in artificial intelligence, existing
methods differ from human learning in the following three aspects [11]. First,
we human perceive the world using multiple senses. We know that the word
“dog”, the bark of a dog and the image/video of a dog all refer to the same
concept. However, most existing methods only process one modality of
information. Second, the human brain has around 100 billion neurons, of which
different parts are specialized for different skills. When we accomplish a
task, we only call upon a small fraction of neurons that are relevant to the
task. However, most existing methods activate all the model parameters. Third,
when we solve a new problem or learn a new skill, we don’t learn from nothing
but combine old skills to learn new things quickly. However, existing methods
typically learn for each task from scratch (or from a general or foundation
model), resulting in hundreds of models for hundreds of tasks.

In this work, we propose a multitask multimodal approach called SkillNet. We
use a single model to handle multiple tasks that require the understanding of
different modalities of information. In SkillNet, different parts of the
parameters are specialized for different skills. When the model is applied to
a downstream task, unlike traditional “dense” models that always activate all
the model parameters, it “sparsely” activates parts of the parameters whose
skills are relevant to the target task. For example, we could define five
modality-related skills {$s_{text}$, $s_{image}$, $s_{sound}$, $s_{video}$,
$s_{code}$}, which are specialized for understanding text, image, sound, video
and code, respectively. Consider the task of automatic speech recognition
(ASR), which only relates to the skill of auditory understanding (i.e.,
$s_{sound}$). When SkillNet is applied to ASR, model parameters related to
other four skills (i.e., {$s_{text}$, $s_{image}$, $s_{video}$, $s_{code}$})
are deactivated. Similarly, for text-to-image retrieval, which is to find
semantically related images given texts, only $s_{text}$ and $s_{image}$ are
activated. Figure 1 gives high-level illustrations of the aforementioned
situations. There are many different ways to implement SkillNet. In this work,
we provide a simple implementation on top of Transformer [40]. Instead of
producing general $K/Q/V$ vectors for each token, we activate different
modality-specific parameters to produce different modality-specific $K/Q/V$
vectors before conducting multi-head attention. The intuition is that we
expect the model to call upon different parts as needed to process different
types of signals and combine information from multiple senses to form our
understanding about a concept (like the aforementioned example about the
concept of dog).

We conduct experiments on tasks of five modalities, including text
classification, automatic speech recognition, text-to-image retrieval, text-
to-video retrieval and text-to-code retrieval. Results show that, SkillNet
performs comparably to five modality-specific models with only one model file.
Furthermore, after being pretrained, SkillNet performs better than systems
with modality-specific pretraining on three of five modalities. On the task of
Chinese text-to-image retrieval, SkillNet obtains higher accuracy than
existing systems (e.g., Wukong${}_{\text{ViT-B}}$ and Wenlan 2.0) while using
less number of activated parameters. Our work demonstrates the feasibility of
developing one general model that is both accuracy and efficient to tackle
multiple tasks of different modalities.

(a) Fully activated dense model (b) Sparsely activated MoE (c) SkillNet for
ASR. (d) SkillNet for text-to-image retrieval

(e) SkillNet for text-to-video retrieval (f) SkillNet for text-to-code
retrieval

Figure 1:  In SkillNet, each pillar refers to a skill. Pillars filled in color
(e.g., yellow, blue, green, purple and red) are activated.

##  2 Comparison to Existing Methods

We describe the connections and differences of this work to related
multimodal, multitask and mixture-of-experts methods.

#### Multimodal

Since there are large amounts of multimodal works, we only describe the
closely related ones. Omnivore [19] uses a single model to process multiple
visual modalities, including single-view 3D data, images and videos. VATT [1]
learns multimodal representations on raw signals for video, audio and text.
Compared to Omnivore and VATT, our work studies more modalities and our
approach is sparse. Data2vec [5] is a general learning objective that
manipulates over latent representations instead of modality-specific tokens.
The same learning objective is used to learn for text, speech and vision.
However, they don’t perform multitask training. Our work is orthogonal to
Data2vec and it is interesting to combine the advantages of Data2vec and
SkillNet.

#### Multitask

This work also relates to multitask learning methods. Systems built upon
Transformer typically use shared feature encoder plus task-specific prediction
layers for understanding tasks [29] and use natural language prompts to steer
encoder-decoder model for generation tasks [37]. Most existing multitask
methods are dense —all the model parameters are activated. An exception is
SkillNet-NLU and SkillNet-NLG [46, 28], recently introduced sparse models that
perform multitask learning on text. This work can be viewed as an extension to
the multimodal situation.

#### Mixture-of-Expert (MoE)

Transformer-based MoE methods typically include multiple homogeneous neural
networks (called experts), which can be fully activated or partially activated
guided by an additional gating function [38, 27, 16, 15]. However, it is
unclear what type of knowledge is learned in each expert and why an expert is
activated. From this point of view, our approach can be viewed as a sparse
multimodal MoE. Unlike traditional MoE methods, each expert in our model has a
clear definition and the activation of each expert has a clear reason (judged
by human experts). For example, the expert corresponding to $s_{text}$ is
responsible for understanding text signal and it is activated only if the
input signal is text.

##  3 Method

This section gives our sparsely activated model SkillNet. We first give a
brief background on Transformer (§3.1). Then, we describe the model
architecture of SkillNet (§3.2). Finally, we describe how to produce the
embeddings for different modalities (§3.3).

###  3.1 Background on Transformer

To make our paper self-contained, we briefly describe Transformer here.
Transformer [40] is a commonly used model architecture with multiple layers,
each of which consists of a multi-head attention layer followed by a feed-
forward network (FFN) layer. The multi-head attention mechanism concatenates
the output vectors of $H$ different heads and then linearly projects them by
$W^{O}$:

$\text{Multi-
Head}(Q,K,V)=\text{Concat}(\text{head}_{1},...,\text{head}_{H})W^{O},$ (1)

where $Q$ (Query), $K$ (Key), $V$ (Value) are the hidden representations of
the previous layer.

Figure 2: An illustration of image search with Transformer-based Siamese
network.

In each head, $Q$, $K$ and $V$ are transformed with projection matrices before
being fed to the attention function:

$\text{head}_{i}=\text{Attention}(QW_{i}^{Q},KW_{i}^{K},VW_{i}^{V}),$ (2)

where $W_{i}^{Q}$, $W_{i}^{K}$ and $W_{i}^{V}$ are model parameters, and $i$
denotes the $i$-th head. The attention function computes the dot products of
the query with all keys, and uses softmax to obtain the weights on values:

$\text{Attention}(Q,K,V)=\text{softmax}(\frac{QK^{T}}{\sqrt{d_{k}}})V,$ (3)

where $d_{k}$ is the dimension of key. Finally, the FNN layer is applied to
obtain the final representations.

Residual connection [22] and layer normalization [3] are adopted for both
multi-head attention layer and FFN layer. Since Transformer is prevalent, we
exclude the details and refer readers to the original paper.

We use image search via Siamese network as the running example to show how to
apply Transformer to downstream tasks. As shown in Figure 2, two Transformers
are used to encode the text and the image, respectively. For each side, we
take the vector of the first token ([CLS]) to represent the input. The
semantic similarity between text and image is computed using dot product or
cosine.

###  3.2 Architecture of SkillNet

We build our SkillNet model by using Transformer [40] as the backbone.
Specifically, we modify the multi-head attention of each Transformer layer as
follows. Instead of producing general $K/Q/V$ vectors for each token, we
activate different modality-specific parameters to produce different modality-
specific $K/Q/V$ vectors before conducting multi-head attention. Take $Q$ as
an example. Instead of having only one projection matrix $W_{i}^{Q}$ for all
queries, we have five projection parameter matrices {$W_{i}^{Q_{text}}$,
$W_{i}^{Q_{image}}$, $W_{i}^{Q_{sound}}$, $W_{i}^{Q_{video}}$,
$W_{i}^{Q_{code}}$}, of which each item stands for a skill of understanding
the information of a particular modality. When the model is applied to a task,
we only activate the corresponding projection matrices of relevant skills.
Similar modifications are made for keys and values. The computation of a head
is modified as follows.

$\text{head}_{i}^{\text{skill}}=\text{Attention}(QW_{i}^{Q_{Activated}},KW_{i}^{K_{Activated}},VW_{i}^{V_{Activated}})$
(4) $W_{i}^{Q_{Activated}}=\begin{cases}W_{i}^{Q_{text}}&\text{if}\
\texttt{s}_{text}\ \text{is activated}\\\ W_{i}^{Q_{image}}&\text{if}\
\texttt{s}_{image}\ \text{is activated}\\\ W_{i}^{Q_{sound}}&\text{if}\
\texttt{s}_{sound}\ \text{is activated}\\\ W_{i}^{Q_{video}}&\text{if}\
\texttt{s}_{video}\ \text{is activated}\\\ W_{i}^{Q_{code}}&\text{if}\
\texttt{s}_{code}\ \text{is activated}\\\ \end{cases}$ (5)

As shown in Figure 4, we only need one model to handle the the task of image
retrieval, where we activate stext and simage for the text encode and image
encoder, respectively.

Figure 3: Architecture of SkillNet for image retrieval. Text encoder and image
encoder are two pathways of one shared model — stext and simage are activated
for the text encoder and the image encoder, respectively.

###  3.3 Embeddings

We describe how to produce the embeddings for different modalities.

#### Text

Following BERT [12], we tokenize a text into a sequence of wordpiece tokens
[45] and build the embedding of each wordpiece by adding up its token
embedding, position embedding and segment embedding. We also add a special
classification token [CLS${}_{\texttt{text}}$] at the beginning of a sequence
to produce the representation of the sequence. If the input includes two
segments, we add a special token [SEP] between the two segments.

#### Sound

Given a raw waveform as the input, we follow wav2vec [4] and use convolutional
network to produce a sequence of vectors as the embeddings. Specifically, we
use seven convolutions with 512 channels, strides of (5,2,2,2,2,2,2) and
kernel widths of (10,3,3,3,3,2,2) to generate a vector sequence from a 20ms
framerate sampled at 16KHz. After that, we adopt a 1D convolutional network to
transform the vector sequence to 768 dimensional embeddings, which are summed
up with their corresponding position embeddings as the final sound embeddings.

#### Image

Following Vision Transformer (ViT)[13], we build patch embeddings for each
image. We first reshape each image of $\mathbf{x}\in\mathbb{R}^{H\times
W\times C}$ into 2D patches of
$\mathbf{x}_{p}\in\mathbb{R}^{N\times(P^{2}\cdot C)}$, where $(H,W)$ is the
image resolution, $(P,P)$ is the resolution of each patch, $N$ is the number
of patches and $C$ is the number of image channels (e.g. 3 for RGB). Then, a
2D convolutional network is applied to transform patch pixels to 768
dimensional embeddings, which are added with the corresponding position
embeddings as the final patch embeddings.111In this work, we use different
positional embeddings for different modalities. We add a special token
[CLS${}_{\texttt{image}}$] at the beginning of each sequence to produce the
representation of the image.

#### Video

We follow Vivit [2], an extension of ViT for video, to produce video
embeddings. Given a video $V\in R^{T\times H\times W\times C}$, where $T$ is
the number of sampled frames, we extract $[T/t]\cdot[H/h]\cdot[W/w]$ non-
overlapping, spatio-temporal “tubes” and use a 3D convolution to produce a
representation for each tube. We further add $[T/t]+[H/h]+[W/w]$ positional
embeddings and concatenate a special token [CLS${}_{\texttt{video}}$] at the
beginning of each sequence to represent the whole video input.

#### Code

We follow CodeBERT [18] to produce code embeddings. We tokenize a code snippet
to a sequence of code-specific wordpiece tokens. The final embedding of each
token is the sum of token embedding, position embedding and segment embedding.
A special token [CLS${}_{\texttt{code}}$] is added to the beginning of each
sequence to produce the embedding of the entire code.

Figure 4: An illustration of the pipeline and the embeddings of different
modalities.

##  4 Tasks

In this section, we first describe downstream tasks involving five modalities
in §4.1. Each modality relates to an active research area that covers many
tasks. We select one task for each modality with preferences for well
recognized tasks (e.g., ASR) and tasks relate to multiple modalities (e.g.,
video/code retrieval). Since our framework also supports sparsely activated
pretraining, we conduct multimodal pretraining to initialize the model
parameters. The pretraining tasks are described in §4.2.

###  4.1 Downstream Tasks

Task Id | Task | Skills
---|---|---
stext | simage | ssound | svideo | scode
T1 | Text Classification | ✓ |  |  |  |
T2 | Automatic Speech Recognition |  |  | ✓ |  |
T3 | Text-to-Image Retrieval | ✓ | ✓ |  |  |
T4 | Text-to-Video Retrieval | ✓ |  |  | ✓ |
T5 | Text-to-Code Retrieval | ✓ |  |  |  | ✓
Table 1: Relations between tasks and skills. Relevant skills for each task are
marked with ticks.

#### Text

Text classification is a classic and fundamental text understanding task [34].
Given a sentence as the input, the task is to predict which category the
sentence belongs to. Following BERT [12], we add a [CLS${}_{\texttt{text}}$]
token at the beginning of each sentence to represent the meaning of the whole
sentence. For the task of text classification, only the parameters that relate
to stext are activated.

#### Sound

Automatic speech recognition (ASR) is to convert speech to text [24].
Following wave2vec [4], we produce speech features and generate a
transcription by performing token-level classification. Connectionist temporal
classification loss [20] is adopted for model training. For the task of ASR,
only the parameters that relate to ssound are activated.

#### Image

We consider text-to-image retrieval. Given a text as the query, the task is to
find the target image from a set of candidates. Considering the efficiency of
the inference stage, we use two separate passes (like Siamese Network) to
produce text and image vectors separately with no cross-modality attention.
Notably, we use the same model with different activation configurations (i.e.,
stext is activated for text and the simage is activated for image) to produce
text and image vectors. The semantic similarity between a text and an image is
calculated with dot product or cosine function.

#### Video

We consider text-to-video retrieval. Given a text as the query, the task is to
find the target video from a set of candidates. The framework is similar to
the aforementioned image retrieval. We use the same model with different
activated parameters (i.e., stext is avtivated for text and svideo is
activated for video) to produce text and video vectors separately.

#### Code

We consider natural language code retrieval. Given a text as the query, the
task is to find the most relevant code from a set of candidates. We use the
same model with different activated parameters (i.e., stext for text and scode
for code) to produce text and code vectors separately. The framework is
similar to image retrieval.

###  4.2 Pretraining Tasks

Recap that our approach also supports multimodal pretraining with sparse
activation. We describe the pretraining tasks for each modality here.

#### Text

We adopt masked language modeling (MLM) as the pre-training task [12, 30].
Given a text, we randomly mask 15% of the tokens. Each masked token is
replaced with a special [MASK] token 80% of the time, a random token 10% of
the time, and left unchanged for the remaining 10% of the time.

#### Sound

We develop a simplified version of HuBERT [25] and pretrain through predicting
the categories of the masked sound tokens, whose target labels are produced
with an offline clustering process. We set the number of clusters to 100 and
use k-mean clustering with Mel-Frequency Cepstral Coefficients (MFCCs)
acoustic features. We use the same masking strategies of wav2vec2 [4], where
about 5% of the time-steps are randomly sampled as start indices and the
subsequent 10 time-steps are masked.

#### Image

We follow CLIP [36] and use contrastive objectives for pretraining. We use the
same architecture for image retrieval as illustrated in §4.1 and adopt in-
batch negative sampling.

#### Video

Similar to the configuration of image pretraining, we consider a contrastive
pretraining task of text-video matching. In-batch negative sampling is
adopted.

#### Code

Like CodeBERT [18], we concatenate code and text, separate them with [SEP] and
randomly mask 15% of the tokens. The pretraining task is to predict the masked
tokens.

##  5 Experiments

###  5.1 Setup

We compare to the following baselines.

$\bullet$ Modality-specific models. We train five different models for
different modalities. The model architecture for each modality is the standard
Transformer.

$\bullet$ Dense multimodal baseline. We train a multimodal model that jointly
learns for five modalities. This is a dense model in that all these modalities
share a common standard Transformer architecture, which is equivalant to
SkillNet with only one skill and that skill is always activated.

$\bullet$ MoE multimodal baseline. We train a Mixture-of-Expert (MoE) [27]
baseline and set the number of experts as the number of skills of SkillNet
(i.e., 5). There is a gating function to selectively active top-2 experts for
each token.

We implement SkillNet on top of HuggingFace’s Transformers [42]. We conduct
experiment with 12 Transformer encoder layers and 768 hidden state dimensions
and leave the extension to larger model scales to the future. Since the
parameters of SkillNet can be pretrained (as described in §4.2), we have two
model configurations, depending on whether the parameters are pretrained in
the same sparsely activated manner. We also compare to baselines with
modality-specific pretraining. For text, we compare to [46], which uses the
superset of our text pretraining corpus to pretrain BERT. For image, we
compare to Wukong${}_{\text{ViT-B}}$ [21], which has the similar model scale
(with 12 Transformer layers) and is pretrained with a superset of our image
pretraining data. For speech, video and code, we pretrain modality-specific
models with the same amount of pretraining data of SkillNet.

Details about the datasets and training process are given in the Appendix.

###  5.2 Results and Analysis

Table 2 gives the results on five tasks.

Method | Text | Image | Sound | Video | Code
---|---|---|---|---|---
Modality-specific models | 0.48 | 69.63 | 0.20 | 63.18 | 53.97
Dense multimodal baseline | 0.48 | 55.70 | 0.23 | 19.46 | 57.59
MoE multimodal baseline | 0.49 | 60.93 | 0.19 | 64.81 | 50.04
SkillNet w/o pretraining | 0.48 | 68.76 | 0.20 | 66.49 | 60.14
Baselines with modality-specific pretraining |  0.56∗ |  71.70† | 0.17 | 77.31 | 66.33
SkillNet | 0.57 | 73.59 | 0.17 | 81.77 | 70.66
Table 2: Results on five tasks. Evaluation metrics for five modalities are
accuracy, Recall@10, CER (lower is better), Recall@10 and Recall@10,
respectively. The result tagged with ∗ is from [46], whose pretraining text
corpus is the superset of our work. The result tagged with † is from the
previous best system for Chinese text-to-image retrieval [21], whose
pretraining image corpus is also the superset of our image pretraining data.

Systems in the first group are not pretrained. We can see that SkillNet
performs comparably to modality-specific models. An interesting finding is
that the joint model with a dense encoder is not friendly to the low-resource
task like text-to-video, but this phenomenon does not exist in either MoE
system or SkillNet. The second group includes systems with modality-specific
pretraining or joint pretraining. We can see that pretraining consistently
improves the performance of SkillNet on all five tasks, even better than
modality-specific pretraining on image, video and code.

On the task of text-to-image retrieval, SkillNet achieves better accuracy
compared to existing leading systems but using less number of activated
parameters. Numbers are given in Table 3. Since the parameters of Wenlan 2.0
and Wukong${}_{\text{ViT-B}}$ are not reported in their papers, we calculate
their parameters based on their model descriptions. The parameters of Wenlan
2.0 [17] include three parts, an image encoder consisting of an
EfficientNet-B7 [39] (66M) and four Transformer encoder layers (50M), a text
encoder RoBERTa-Large [10] (326M) and a cross-modal projection layer with two
fully-connected layers (3M). Wukong${}_{\text{ViT-B}}$ [21] includes a Vision
Transformer (ViT) [14] (86M) as the image encoder, a standard decoder-only
transformer (110M) as the text encoder and a linear cross-modal projection
layer (0.6M).

Method | Number of Activated Params | R@1 | R@10
---|---|---|---
Wenlan 2.0 [17] | 445M | 34.1 | 69.1
Wukong${}_{\text{ViT-B}}$ [21] | 197M | 36.7 | 71.7
SkillNet | 124M | 37.0 | 73.6
Table 3: Performance and activated model parameters of text-to-image retrieval
methods.

Figure 5 shows the learning curves of SkillNet with or without pretraining on
different tasks. We can see that in general pretraining gives the model a good
starting point and leads to better accuracy.

(a) SkillNet for text-to-image retrieval. (b) SkillNet for text-to-video
retrieval. (c) SkillNet for ASR. (d) SkillNet for text-to-code retrieval.

Figure 5: Performance of SkillNet with different finetuning steps. X-axis
stands for the training steps. Y-axis stands for the evaluation metric (lower
is better for CER).

Figure 6, 7 and 8 give case studies on image, video and code retrieval,
respectively.

Figure 6: Case study for text-to-image retrieval. For each query, we show
top-3 returned images and the relevance scores returned by SkillNet. Figure 7:
Case study for text-to-video retrieval. For each query, we show the top-3
returned videos returned by SkillNet and provide three frames for each video.
Figure 8: Case study for text-to-code retrieval. For each query, we show top-3
returned codes and the relevance scores returned by SkillNet.

##  6 Conclusion

This paper presents a sparsely activated multimodal multitask approach called
SkillNet. We demonstrate the feasibility of using one model to achieve
comparable performance compared to multiple modality-specific models. We
further show that sparse pretraining gives a better initialized parameters
which leads to improved accuracy, even better than modality-specific
pretraining on three of five modalities. On Chinese text-to-image retrieval,
our final system yields better accuracy with less activated parameters
compared to existing leading systems. Our approach is modality-agnostic and
task-agnostic. We leave the extension to larger number of modalities and tasks
to the future.

## References

  * Akbari et al. [2021] Hassan Akbari, Liangzhe Yuan, Rui Qian, Wei-Hong Chuang, Shih-Fu Chang, Yin Cui, and Boqing Gong.  Vatt: Transformers for multimodal self-supervised learning from raw video, audio and text.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Arnab et al. [2021] Anurag Arnab, Mostafa Dehghani, Georg Heigold, Chen Sun, Mario Lučić, and Cordelia Schmid.  Vivit: A video vision transformer.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 6836–6846, 2021.
  * Ba et al. [2016] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton.  Layer normalization.  _arXiv preprint arXiv:1607.06450_ , 2016.
  * Baevski et al. [2020] Alexei Baevski, Yuhao Zhou, Abdelrahman Mohamed, and Michael Auli.  wav2vec 2.0: A framework for self-supervised learning of speech representations.  _Advances in Neural Information Processing Systems_ , 33:12449–12460, 2020.
  * Baevski et al. [2022] Alexei Baevski, Wei-Ning Hsu, Qiantong Xu, Arun Babu, Jiatao Gu, and Michael Auli.  data2vec: A general framework for self-supervised learning in speech, vision and language.  _arXiv preprint arXiv:2202.03555_ , 2022.
  * Bahrami et al. [2021] Mehdi Bahrami, NC Shrikanth, Shade Ruangwan, Lei Liu, Yuji Mizobuchi, Masahiro Fukuyori, Wei-Peng Chen, Kazuki Munakata, and Tim Menzies.  Pytorrent: A python library corpus for large-scale language models.  _arXiv preprint arXiv:2110.01710_ , 2021.
  * Bain et al. [2021] Max Bain, Arsha Nagrani, Gül Varol, and Andrew Zisserman.  Frozen in time: A joint video and image encoder for end-to-end retrieval.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 1728–1738, 2021.
  * Bao et al. [2021] Hangbo Bao, Li Dong, and Furu Wei.  Beit: Bert pre-training of image transformers.  _arXiv preprint arXiv:2106.08254_ , 2021.
  * Bu et al. [2017] Hui Bu, Jiayu Du, Xingyu Na, Bengu Wu, and Hao Zheng.  Aishell-1: An open-source mandarin speech corpus and a speech recognition baseline.  In _2017 20th Conference of the Oriental Chapter of the International Coordinating Committee on Speech Databases and Speech I/O Systems and Assessment (O-COCOSDA)_ , pages 1–5. IEEE, 2017.
  * Cui et al. [2020] Yiming Cui, Wanxiang Che, Ting Liu, Bing Qin, Shijin Wang, and Guoping Hu.  Revisiting pre-trained models for Chinese natural language processing.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 657–668, Online, November 2020. Association for Computational Linguistics.
  * Dean [2021] Jeff Dean.  Introducing pathways: A next-generation ai architecture.  In _Google Blog_ , 2021.  URL https://blog.google/technology/ai/introducing-pathways-next-generation-ai-architecture/.
  * Devlin et al. [2018] 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.
  * Dosovitskiy et al. [2020] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ , 2020.
  * Dosovitskiy et al. [2021] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _International Conference on Learning Representations_ , 2021.
  * Du et al. [2021] Nan Du, Yanping Huang, Andrew M Dai, Simon Tong, Dmitry Lepikhin, Yuanzhong Xu, Maxim Krikun, Yanqi Zhou, Adams Wei Yu, Orhan Firat, et al.  Glam: Efficient scaling of language models with mixture-of-experts.  _arXiv preprint arXiv:2112.06905_ , 2021.
  * Fedus et al. [2021] William Fedus, Barret Zoph, and Noam Shazeer.  Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity.  _arXiv preprint arXiv:2101.03961_ , 2021.
  * Fei et al. [2021] Nanyi Fei, Zhiwu Lu, Yizhao Gao, Guoxing Yang, Yuqi Huo, Jingyuan Wen, Haoyu Lu, Ruihua Song, Xin Gao, Tao Xiang, et al.  Wenlan 2.0: Make ai imagine via a multimodal foundation model.  _arXiv preprint arXiv:2110.14378_ , 2021.
  * Feng et al. [2020] Zhangyin Feng, Daya Guo, Duyu Tang, Nan Duan, Xiaocheng Feng, Ming Gong, Linjun Shou, Bing Qin, Ting Liu, Daxin Jiang, et al.  Codebert: A pre-trained model for programming and natural languages.  _arXiv preprint arXiv:2002.08155_ , 2020.
  * Girdhar et al. [2022] Rohit Girdhar, Mannat Singh, Nikhila Ravi, Laurens van der Maaten, Armand Joulin, and Ishan Misra.  Omnivore: A single model for many visual modalities.  _arXiv preprint arXiv:2201.08377_ , 2022.
  * Graves et al. [2006] Alex Graves, Santiago Fernández, Faustino Gomez, and Jürgen Schmidhuber.  Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks.  In _Proceedings of the 23rd international conference on Machine learning_ , pages 369–376, 2006.
  * Gu et al. [2022] Jiaxi Gu, Xiaojun Meng, Guansong Lu, Lu Hou, Minzhe Niu, Hang Xu, Xiaodan Liang, Wei Zhang, Xin Jiang, and Chunjing Xu.  Wukong: 100 million large-scale chinese cross-modal pre-training dataset and a foundation framework.  _arXiv preprint arXiv:2202.06767_ , 2022.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * He et al. [2021] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick.  Masked autoencoders are scalable vision learners.  _arXiv preprint arXiv:2111.06377_ , 2021.
  * Hinton et al. [2012] Geoffrey Hinton, Li Deng, Dong Yu, George E Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Tara N Sainath, et al.  Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups.  _IEEE Signal processing magazine_ , 29(6):82–97, 2012.
  * Hsu et al. [2021] Wei-Ning Hsu, Benjamin Bolte, Yao-Hung Hubert Tsai, Kushal Lakhotia, Ruslan Salakhutdinov, and Abdelrahman Mohamed.  Hubert: Self-supervised speech representation learning by masked prediction of hidden units.  _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , 29:3451–3460, 2021.
  * Huang et al. [2021] Guoping Huang, Lemao Liu, Xing Wang, Longyue Wang, Huayang Li, Zhaopeng Tu, Chengyan Huang, and Shuming Shi.  Transmart: A practical interactive machine translation system.  _arXiv preprint arXiv:2105.13072_ , 2021.
  * Lepikhin et al. [2020] Dmitry Lepikhin, HyoukJoong Lee, Yuanzhong Xu, Dehao Chen, Orhan Firat, Yanping Huang, Maxim Krikun, Noam Shazeer, and Zhifeng Chen.  Gshard: Scaling giant models with conditional computation and automatic sharding.  _arXiv preprint arXiv:2006.16668_ , 2020.
  * Liao et al. [2022] Junwei Liao, Duyu Tang, Fan Zhang, and Shuming Shi.  Skillnet-nlg: General-purpose natural language generation with a sparsely activated approach, 2022.  URL https://arxiv.org/abs/2204.12184.
  * Liu et al. [2019a] Xiaodong Liu, Pengcheng He, Weizhu Chen, and Jianfeng Gao.  Multi-task deep neural networks for natural language understanding.  _arXiv preprint arXiv:1901.11504_ , 2019a.
  * Liu et al. [2019b] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_ , 2019b.
  * Loshchilov and Hutter [2019] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  In _International Conference on Learning Representations_ , 2019.
  * Luo et al. [2021] Huaishao Luo, Lei Ji, Ming Zhong, Yang Chen, Wen Lei, Nan Duan, and Tianrui Li.  Clip4clip: An empirical study of clip for end to end video clip retrieval.  _arXiv preprint arXiv:2104.08860_ , 2021.
  * Manning [2022] Christopher D Manning.  Human language understanding & reasoning.  _Daedalus_ , 151(2):127–138, 2022.
  * Minaee et al. [2021] Shervin Minaee, Nal Kalchbrenner, Erik Cambria, Narjes Nikzad, Meysam Chenaghlu, and Jianfeng Gao.  Deep learning–based text classification: a comprehensive review.  _ACM Computing Surveys (CSUR)_ , 54(3):1–40, 2021\.
  * Radford et al. [2019] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9, 2019.
  * Radford et al. [2021] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In _International Conference on Machine Learning_ , pages 8748–8763. PMLR, 2021.
  * Raffel et al. [2019] 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.  _arXiv preprint arXiv:1910.10683_ , 2019.
  * Shazeer et al. [2017] Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc Le, Geoffrey Hinton, and Jeff Dean.  Outrageously large neural networks: The sparsely-gated mixture-of-experts layer.  _arXiv preprint arXiv:1701.06538_ , 2017.
  * Tan and Le [2019] Mingxing Tan and Quoc Le.  Efficientnet: Rethinking model scaling for convolutional neural networks.  In _International conference on machine learning_ , pages 6105–6114. PMLR, 2019.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _Advances in neural information processing systems_ , pages 5998–6008, 2017.
  * Wang et al. [2019] Xin Wang, Jiawei Wu, Junkun Chen, Lei Li, Yuan-Fang Wang, and William Yang Wang.  Vatex: A large-scale, high-quality multilingual dataset for video-and-language research.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 4581–4591, 2019.
  * Wolf et al. [2020] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush.  Huggingface’s transformers: State-of-the-art natural language processing.  _arXiv preprint arXiv:1910.03771_ , 2020.
  * Wu et al. [2017] Jiahong Wu, He Zheng, Bo Zhao, Yixin Li, Baoming Yan, Rui Liang, Wenjia Wang, Shipei Zhou, Guosen Lin, Yanwei Fu, et al.  Ai challenger: A large-scale dataset for going deeper in image understanding.  _arXiv preprint arXiv:1711.06475_ , 2017.
  * Xu et al. [2020] Liang Xu, Hai Hu, Xuanwei Zhang, Lu Li, Chenjie Cao, Yudong Li, Yechen Xu, Kai Sun, Dian Yu, Cong Yu, et al.  Clue: A chinese language understanding evaluation benchmark.  _arXiv preprint arXiv:2004.05986_ , 2020.
  * Yonghui et al. [2016] W Yonghui, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al.  Bridging the gap between human and machine translation.  _arXiv preprint arXiv:1609.08144_ , 2016.
  * Zhang et al. [2022] Fan Zhang, Duyu Tang, Yong Dai, Cong Zhou, Shuangzhi Wu, and Shuming Shi.  Skillnet-nlu: A sparsely activated model for general-purpose natural language understanding.  _arXiv preprint arXiv:2203.03312_ , 2022.

##  Appendix A Appendix

#### Configurations for Downstream Tasks

We describe the datasets and configurations for the downstream tasks as
described in §4.1. For text, we use TNEWS [44], a benchmark dataset for
Chinese text classification with 15 categories. It includes 53,300 sentences
for training, 10,000 for development, and 10,000 for testing. Evaluation
metric is accuracy. For sound, we adopt the dataset of AISHELL [9] for
automatic speech recognition. It includes 170 hours of speech data in
Mandarin. The evaluation metric is character error rate (CER), which means the
percentage of characters that are incorrectly predicted (the lower the
better). For image, we use AIC-ICC dataset [43], a benchmark dataset for text-
to-image retrieval. It includes 210,000 image-text pairs for training and
30,000 for evaluation. We follow Wukong [21] and consider the first 10,000
images and 50,000 texts from the validation set as the final testing set.
Evaluation metric is Recall @K (e.g., K = 1 and 10). For video, we carry out
text-to-video retrieval on VATEX [41], which includes 25,991 videos for
training and 3,000 for validation. Since some videos are unavailable for they
are deleted or hidden by either YouTube or the users, we actually obtain
23,453 videos for training and 2,709 videos for validation. We randomly select
1,500 videos from validation set as our testing set and use the remaining
videos as the development set. In the original dataset, there are 10 sentences
in Chinese and 10 sentences in English to describe each video. In this work,
we only utilize the Chinese captions. Similar to image retrieval, we use
Recall @K (e.g., K = 1, 5 and 10) as the evaluation metrics. For code, since
there is no publicly available dataset for Chinese language, we create a
dataset by translating the PyTorrent [6] dataset. It contains 218,814 Python
package libraries from PyPI and Anaconda environment. We translate English
docstrings to Chinese by a translation toolkit Transmart [26]. We delete
duplicate code-text pairs and remove instances with low translation quality.
We mix the original training set, development set and test set. At last, we
shuffle the mixed set and randomly select 100,000/20,000/30,000 for training,
validation and testing, respectively. The evaluation metric is Recall @K.

The model configurations are given as follows. For text, the max length is
512, and a special text padding token is padded if the input is shorter. For
sound, we truncate each waveform to no more than 20ms, which leads to the max
length of the sound embedding being 1,000. If the input is shorter, the
remaining positions are filled with a special sound padding token. Other
configurations can be found in 3.3. For image, same with ViT-B/16 from CLIP
[36], we first resize and normalize each image to $224\times 224$. Then, we
split each image into 196 patches with the patch size of $16\times 16$, which
are sent into a 3 in-channel and 768 out-channel 2D-convolution with kernel
size of (16, 16) and stride step of (16, 16). For video, we truncate each
video to no more than 10 seconds and transform each video into frames by 3
frames per second. Then, we randomly sample 6 frames for each video. At last,
6 video frames after cropping and normalizing are sent into a 3 in-channel and
768 output-channel 3D-convolution with a kernel size of (3, 16, 16) and stride
step (3, 16, 16). For code, we set the whole max length as 512 with the limit
of text max length of 64. We use AdamW [31] optimizer and linear scheduler
with 1,000 warmup steps. There are different ways to initialize the model
parameters. To accelerate the training process, instead of training from
random initialization, we use ViT-B/16 from CLIP [36] to initialize image-
related parameters and initialize other parameters from scratch. Since
different modalities have different memory costs, we set the batch sizes as
512/1024/3072/1024/512 for text/sound/image/video/code to maximize the memory
usage of GPUs. We observe that sound and code modalities require longer
training steps to converge and the data scale of video is smaller than other
modalities. Therefore, we sample instances for text/sound/image/video/code
modalities with the ratio of 2/4/2/1/4. For each update, we only sample
instances from one modality, which makes the learning process more stable. We
update our model for 200,000 steps in total.

#### Configurations for Pretraining Tasks

We describe the datasets and configurations for the pretraining tasks as
described in §4.2. For text, we crawl a collection of raw Chinese texts
containing Wikipedia, novels, news, lyrics and poems. We clean the data and
finally obtain a dataset of about 300 gigabytes. For sound, we collect audio
datasets from an open-source platform
222https://blog.ailemon.net/2018/11/21/free-open-source-chinese-speech-
datasets/, which includes about 1,200 hours of Chinese speech data. For image,
we download the Wukong dataset [21] which originally includes 101,483,885
text-image pairs and filter out low-quality instances that with no Chinese
words, too many illegal symbols and the length of captions is less than 4. We
finally use about 84,000,000 text-image pairs for pretraining. For video, we
use WebVid-2M [7], which comprises of over two million video-text pairs
scraped from the internet. We translate the original English texts to Chinese
by the translation tool Transmart and use the translated data for pretraining.
For code pretraining, we hold out 800,000 code-text pairs from the
aforementioned code dataset translated from PyTorrent, which have no overlaps
with the datasets used for the downstream task of text-code retrieval.

We pretrain SkillNet using the AdamW [31] optimizer with the learning rate
1e-5 and a linear scheduler with 10,000 warmup steps. Same with the
configuration for downstream tasks, we use one-modality data to pretrain our
model in each update. The model is pretrained for 1,000,000 steps in total
with batch sizes of 1024/512/8192/2048/512 for text/sound/image/video/code,
respectively. Pretraining takes about 14 days on 64 A100 GPUs of 40GB memory
size.


# On the Complexity of the Bipartite Polarization Problem: from Neutral to
Highly Polarized Discussions

Teresa Alsinet Corresponding Author. Email<EMAIL_ADDRESS>Josep
Argelich  Ramón Béjar  Santi Martínez  Departament d’Enginyeria Informàtica i
Disseny Digital (DEIDD), University of Lleida, Spain

###### Abstract

The Bipartite Polarization Problem is an optimization problem where the goal
is to find the highest polarized bipartition on a weighted and labelled graph
that represents a debate developed through some social network, where nodes
represent user’s opinions and edges agreement or disagreement between users.
This problem can be seen as a generalization of the maxcut problem, and in
previous work approximate solutions and exact solutions have been obtained for
real instances obtained from Reddit discussions, showing that such real
instances seem to be very easy to solve. In this paper, we investigate further
the complexity of this problem, by introducing an instance generation model
where a single parameter controls the polarization of the instances in such a
way that this correlates with the average complexity to solve those instances.
The average complexity results we obtain are consistent with our hypothesis:
the higher the polarization of the instance, the easier is to find the
corresponding polarized bipartition.

##  1 Introduction

The emergence of polarization in discussions on social media networks, and the
responsibility of companies in this problem, is a topic that is causing a
significant interest among society [11], although the complete relationship
between digital platforms and polarized attitudes remains unclear [3]. For
example, there is some work that indicates that, at least for polarization in
people’s views of political parties, the increased use of social networks and
the internet may not be necessarily increasing polarization [7].

Online social networks are platforms for social and communicative interaction.
Studies have shown that polarization varies greatly across platforms [20], the
strength of the results being a function of how polarization is measured [10].
Previous work has studied the presence of polarization in different concrete
examples, trying to analyze the relevant characteristics in these cases. For
example, the works [5, 18] studied the emergence of so-called echo chambers,
where users are found to interact mainly only with the users that agree with
them and to have very few interactions with other groups. However, online
discussions in social networks can also show polarization where there are
answers with negative sentiment between different groups, which can be
considered the most worrying situation. For example, in [15] they studied
hyperpartisanship and polarization in Twitter during the 2018 Brazilian
presidential election. Their findings showed that there was more interaction
within each group (pro/anti Bolzonaro) but there was also an interaction
between both groups. Actually, there are also cases where the interaction
between groups can be more relevant than those within groups, like in the case
studied in [12] where the analysis of the 2016 U.S. elections on Reddit showed
a significant number of interactions between pro-Trump and pro-Hillary
supporters. So, the extent to which bias is due to inline echo chambers and
filter bubbles is also misunderstood, with evidence pointing in opposite
directions [3]. A major problem is that divisive content tends to spread
widely and quickly on social media. Posts that express moral outrage [8] or
bash one’s outparty [14], for example, tend to be particularly successful at
going viral. This virality is driven by the prioritizations made by social
media algorithms coupled with people’s general inclination to favor
sensational content. As a consequence, when people log on to social media,
they are likely to see content that is divisive and presses their emotional
buttons. In addition, these trends encourage politicians, media outlets and
potential influencers to publish divisive content because it is most likely to
give the commitment they desire. To try to mitigate the factors that may be
helping the spread of divisive content, for instance, Facebook has launched
some initiatives [16], even if this kind of content may be the one that
produces the maximum attention of their users, so being also the one producing
maximum economic benefit.

Because each online social network company can have its own personal interest
regarding when to control this kind of behaviour, one fundamental aspect is to
define more transparent ways to monitor such possible non-desirable
behaviours, so that we can inform solutions for creating healthier social
media environments. From our point of view, the goal to be achieved in this
direction is to provide mechanisms that allow us to detect situations where
one can deduce that polarization is taking place, and to a certain level of
severity, because there is some objective value we can measure for this.

With this goal in mind and given that Reddit turned out to be a decisive
political debate platform in different elections in the United States, such as
those of 2016, a research work introduced a problem [2] about finding the
highest polarized bipartition on a weighted and labelled graph that represents
a Reddit debate, where nodes represent user’s opinions and edges agreement or
disagreement between users. The authors showed that finding this target
bipartition is an optimization problem that can be seen as a generalization of
the maxcut problem, and they introduced a basic local search algorithm to find
approximate solutions of the problem. Later on, in [1], the complexity of
solving real instances from Reddit discussions with both complete and
approximate algorithms was also studied. These results on real Reddit
instances showed that solving those instances could be performed with little
computational cost as the size of the instances increased, and that all the
instances, obtained from different subreddits, tended to show polarization
values away from neutral discussions, although without reaching the case of
extreme polarization.

Our aim in this paper is to further investigate the complexity of this
problem, by introducing an instance generation model where a single parameter
controls the polarization of the instances in such a way that this correlates
with the average complexity to solve those instances. The average complexity
results we obtain are consistent with our hypothesis: the higher the
polarization of the instance, the easier is to find the corresponding
polarized bipartition. Although one can consider other alternative ways to
measure the polarization in online social networks, we believe that our
generation model could be used to easily check other measures. The results
obtained with our generation model together with the previous results on real
instances from Reddit discusions seem to indicate that in practice, it may be
feasible to compute the polarization of online discussions, at least with a
polarization measure like the one we use here.

Therefore, in view of the experimental results, checking polarization with
this measure seems to be difficult only in unrealistic cases. Clearly, it is
advantageous to can offer algorithms for monitoring polarization in online
social networks.

The structure of the rest of the paper is as follows. In Section 2, we present
both the model for weighted and labelled graphs that represents an online
debate and the measure to quantify the polarization in such debate graphs,
studied and developed in [2]. In Section 3 we prove that the computation of
such measure is NP-hard. In Section 4 we describe the algorithms that we use
to solve the Bipartite Polarization Problem. In Section 5, we introduce our
random generation model for user debate graphs based on a main parameter,
called $\alpha$, to control the polarization of the instances. Finally, in
Section 6, we perform an empirical evaluation to study how the complexity of
solving the typical instances obtained with our random model changes as we
modify the parameter $\alpha$ and how this at the same time affects to the
polarization of the instances.

##  2 Problem Definition

Polarization corresponds to the social process whereby a group of persons is
divided into two opposing subgroups having conflicting and contrasting
positions, goals and viewpoints, with few individuals remaining neutral or
holding an intermediate position [17]. The model we consider in this work is
inspired by the model used in [13] to identify supporting or opposing opinions
in online debates, based on finding a maximum cut in a graph that models the
interactions between users. Moreover, as we are interested in quantifying
polarization, we consider a model that is based on a weighted graph and with
labeled edges, where node weights represent the side of the user in the debate
and edge labels represent the overall sentiment between two users. Then, given
a bipartition of this graph, the polarization degree of the bipartition is
based on how homogeneous each partition is and how negative the interactions
are between both partitions. Finally, the measure of debate polarization is
based on the maximum polarization obtained in all the possible bipartitions of
the graph.

Adapting from [2], an online debate $\Gamma$ on a root comment $r$ is a non-
empty set of comments, that were originated as successive answers to a root
comment $r$. An online debate is modeled as a two-sided debate tree, where
nodes are labelled with a binary value that denotes whether the comment is in
agreement (1) or in disagreement (-1) with the root comment. 111In [2] they
introduced this model specifically for Reddit debates. However, it is clearly
a model suitable for other similar social networks.

######  Definition 1 (Two-Sided Debate Tree)

Let $\Gamma$ be an online debate on a root comment r. A Two-Sided Debate Tree
(SDebT) for $\Gamma$ is a tuple $\mathcal{T}_{S}=\langle C,r,E,W,S\rangle$
defined as follows:

  * •

For every comment $c_{i}$ in $\Gamma$, there is a node $c_{i}$ in $C$.

  * •

Node $r\in C$ is the root node of $\mathcal{T}$.

  * •

If a comment $c_{1}\in C$ answers another comment $c_{2}\in C$, there is a
directed edge $(c_{1},c_{2})$ in $E$.

  * •

$W$ is a labelling function of answers (edges) $W:E\rightarrow[-2,2]$, where
the value assigned to an edge $(c_{1},c_{2})\in E$ denotes the sentiment of
the answer $c_{1}$ with respect to $c_{2}$, from highly negative ($-2$) to
highly positive ($2$).

  * •

$S$ is a labelling function of comments (nodes) $S:C\rightarrow\\{-1,1\\}$,
where the value assigned to a node $c_{i}\in C$ denotes whether the comment
$c_{i}$ is in agreement (1) or in disagreement (-1) with the root comment $r$
and it is defined as follows:

    * -

$S(r)=1$ and

    * -

For all node $c_{1}\neq r$ in $C$, $S(c_{1})=1$ if for some node $c_{2}\in C$,
$(c_{1},c_{2})\in E$ and either $S(c_{2})=1$ and $W(c_{1},c_{2})>0$, or
$S(c_{2})=-1$ and $W(c_{1},c_{2})\leq 0$; otherwise, $S(c_{1})=-1$.

Only the nodes and edges obtained by applying this process belong to $C$ and
$E$, respectively.

Next, we present the formalization of a User Debate Graph based on a Two-Sided
Debate Tree, where now all the comments of a same user are aggregated into a
single node that represents the user’s opinion.

######  Definition 2 (User Debate Graph)

Let $\Gamma$ be a online debate on a root comment $r$ with users’ identifiers
$U=\\{u_{1},\ldots,u_{m}\\}$ and let $\mathcal{T}_{S}=\langle
C,r,E,W,S\rangle$ be a SDebT for $\Gamma$. A User Debate Graph (UDebG) for
$\mathcal{T}_{S}$ is a tuple
$\mathcal{G}=\langle{\mathcal{C}},{\mathcal{E}},{\mathcal{S}},{\mathcal{W}}\rangle$,
where:

  * •

$\mathcal{C}$ is the set of nodes of $\mathcal{G}$ defined as the set of
users’ opinions $\\{C_{1},\ldots,C_{m}\\}$; i.e.,
$\mathcal{C}=\\{C_{1},\ldots,C_{m}\\}$ with $C_{i}=\\{c\in\Gamma\mid c\neq
r{\textrm{ and user}(c)=u_{i}}\\}$, for all users $u_{i}\in U$.

  * •

$\mathcal{E}\subseteq\mathcal{C}\times\mathcal{C}$ is the set of edges of
$\mathcal{G}$ defined as the set of interactions between different users in
the debate; i.e., there is an edge $(C_{i},C_{j})\in\mathcal{E}$, with
$C_{i},C_{j}\in\mathcal{C}$ and $i\neq j$, if and only if for some
$(c_{1},c_{2})\in E$ we have that $c_{1}\in C_{i}$ and $c_{2}\in C_{j}$.

  * •

$\mathcal{S}$ is an opinion weighting scheme for $\mathcal{C}$ that expresses
the side of users in the debate based on the side of their comments. We define
$\mathcal{S}$ as the mapping $\mathcal{S}:\mathcal{C}\rightarrow[-1,1]$ that
assigns to every node $C_{i}\in\mathcal{C}$ the value

$\mathcal{S}(C_{i})=\frac{\sum_{c\in C_{i}}S(c_{i})}{|C_{i}|}$

in the real interval $[-1,1]$ that expresses the side of the user $u_{i}$ with
respect to the root comment, from strictly disagreement ($-$1) to strictly
agreement (1), going through undecided opinions (0).

  * •

$\mathcal{W}$ is an interaction weighting scheme for $\mathcal{E}$ that
expresses the overall sentiment between users by combining the individual
sentiment values assigned to the responses between their comments.

We define $\mathcal{W}$ as the mapping
$\mathcal{W}:\mathcal{E}\rightarrow[-2,2]$ that assigns to every edge
$(C_{i},C_{j})\in\mathcal{E}$ a value $w\in[-2,2]$ defined as follows:

$w=\sum_{\\{(c_{1},c_{2})\in E\cap(C_{i}\times
C_{j})\\}}W(c_{1},c_{2})/|\\{(c_{1},c_{2})\in E\cap(C_{i}\times C_{j})\\}|$

where $w$ expresses the overall sentiment of the user $u_{i}$ regarding the
comments of the user $u_{j}$, from highly negative ($-$2) to highly positive
(2).

Only the nodes and edges obtained by applying this process belong to
$\mathcal{C}$ and $\mathcal{E}$, respectively.

Given a User Debate Graph
$\mathcal{G}=\langle{\mathcal{C}},{\mathcal{E}},{\mathcal{S}},{\mathcal{W}}\rangle$,
a model to measure the level of polarization in the debate between its users
was also introduced in [2]. It is based on two characteristics that a
polarization measure should capture. First, a polarized debate should contain
a bipartition of ${\mathcal{C}}$ into two sets $(L,R)$ such that the set $L$
contains mainly users in disagreement, the set $R$ contains mainly users in
agreement, and both sets should be similar in size. The second ingredient is
the sentiment between users of $L$ and $R$. A polarized discussion should
contain most of the negative interactions between users of $L$ and users of
$R$, whereas the positive interactions, if any, should be mainly within the
users of $L$ and within the users of $R$.

To capture these two characteristics with a single value, two different
measures are combined in a final one, referred to as the bipartite
polarization.

######  Definition 3 (Bipartite Polarization)

Given a User Debate Graph
$\mathcal{G}=\langle{\mathcal{C}},{\mathcal{E}},{\mathcal{S}},{\mathcal{W}}\rangle$
and a bipartition $(L,R)$ of ${\mathcal{C}}$, we define:

  * •

The level of consistency and balance of $(L,R)$ is a real value in $[0,0.25]$
defined as follows:

${\textrm{\em SC}}(L,R,\mathcal{G})={\textrm{\em
LC}}(L,\mathcal{G})\cdot{\textrm{\em RC}}(R,\mathcal{G})$

with:

${\textrm{\em LC}}(L,\mathcal{G})=\frac{\sum_{\begin{subarray}{c}C_{i}\in
L,\\\ \mathcal{S}(C_{i})\leq
0\end{subarray}}-{\mathcal{S}}(C_{i})}{|{\mathcal{C}}|}$

and

${\textrm{\em RC}}(R,\mathcal{G})=\frac{\sum_{\begin{subarray}{c}C_{i}\in
R,\\\
\mathcal{S}(C_{i})>0\end{subarray}}{\mathcal{S}}(C_{i})}{|{\mathcal{C}}|}.$

  * •

The sentiment of the interactions between users of different sides is a real
value in $[0,4]$ defined as follows 222According with [1], each edge label
$(i,j)$ can incorporate a correction factor that is used to modify the final
weight used in this function. However, to simplify the model notation, we will
consider that the weight $\mathcal{W}(i,j)$ already reflects this factor.:

${\textrm{\em
SWeight}}(L,R,\mathcal{G})=\frac{\sum_{\begin{subarray}{c}(i,j)\in{\mathcal{E}}\cap\\\
((L\times R)\cup(R\times
L))\end{subarray}}-\mathcal{W}(i,j)}{|{\mathcal{E}}|}+2,$

Then, the Bipartite Polarization of $\mathcal{G}$ on a bipartition $(L,R)$ is
the value in the real interval $[0,1]$ defined as follows:

${\textit{BipPol}}(L,R,\mathcal{G})=SC(L,R,\mathcal{G})\cdot{\textit{SWeight}}(L,R,\mathcal{G}).$

Finally, the Bipartite Polarization of $\mathcal{G}$ is the maximum value of
${\textit{BipPol}}(L,R,\mathcal{G})$ among all the possible bipartitions
$(L,R)$.

##  3 Worst-case Complexity of the Bipartite Polarization Problem

###### Proposition 1

The UDebG bipartite polarization problem is NP-hard.

Proof. We prove that the simple maxcut problem, that it is NP-hard even for
graphs with bounded degree $\leq 3$ [19], can be reduced to the UDebG
bipartite polarization problem in polynomial time. Consider an undirected
graph instance $G=(V,E)$ of the simple maxcut problem. Then, we build an
instance
$\mathcal{G}=\langle{\mathcal{C}},{\mathcal{E}},{\mathcal{S}},{\mathcal{W}}\rangle$
of the bipartite polarization problem such that:

  1. 1.

The set of vertices ${\mathcal{C}}$ is equal to $V\cup\\{u^{-},u^{+}\\}$. For
${\mathcal{S}}$ we have that $\forall v\in V,{\mathcal{S}}(v)=0$ and
${\mathcal{S}}(u^{-})=-1,{\mathcal{S}}(u^{+})=+1$.

  2. 2.

The set of edges ${\mathcal{E}}$ is defined only for those vertices that have
an edge in the input graph: ${\mathcal{E}}=\\{(v_{1},v_{2}),(v_{2},v_{1})\ |\
\\{v_{1},v_{2}\\}\in E\\}$. And for any $e\in{\mathcal{E}}$ we have that
${\mathcal{W}}(e)=-1/2$.

Then, assume $G=(V,E)$ has a bipartition $(L,R)$ with total weight (number of
edges between $L$ and $R$) equal to $W$. Consider the bipartition
$(L\cup\\{u^{-}\\},R\cup\\{u^{+}\\})$ for the instance $\mathcal{G}$ obtained
by the reduction. Clearly:

${\textit{BipPol}}(L\cup\\{u^{-}\\},R\cup\\{u^{+}\\},\mathcal{G}))=\frac{-(-1)}{|{\mathcal{C}}|}\frac{1}{|{\mathcal{C}}|}\left(\frac{W}{|E|}+2\right)$

Next, assume
$\mathcal{G}=\langle{\mathcal{C}},{\mathcal{E}},{\mathcal{S}},{\mathcal{W}}\rangle$
has a bipartition $(L^{\prime},R^{\prime})$ with bipartite polarization value
equal to $BPol$. Then, as all the nodes have ${\mathcal{S}}(v)=0$, except for
${\mathcal{S}}(u^{-})=-1,{\mathcal{S}}(u^{+})=+1$ , we have that if $BipPol>0$
then $u^{-}$ will be in $L^{\prime}$ and $u^{+}$ will be in $R^{\prime}$, so
the BipPol value will be of the same form as before:

${\textit{BipPol}}(L^{\prime},R^{\prime},\mathcal{G}))=\frac{-(-1)}{|{\mathcal{C}}|}\frac{1}{|{\mathcal{C}}|}\left(\frac{W}{|E|}+2\right)$

where $W$ will be equal to half the number of edges between $L^{\prime}$ and
$R^{\prime}$ in $\mathcal{G}$, as for any undirected edge in the input graph
$G$ we have two directed edges in $\mathcal{G}$ each one with $W(e)=-1/2$. But
this implies that
$(L^{\prime}\setminus\\{u^{-}\\},R^{\prime}\setminus\\{u^{+}\\})$ is a
bipartition for the input graph $G$ with value $W$. For the case $BPol=0$,
this could only happen because the vertices $u^{-}$ or $u^{+}$ are in the
wrong side. But we can always transform any bipartition
$(L^{\prime},R^{\prime})$ to one in which $u^{-}$ and $u^{+}$ are in the right
side, and so derive the value of $W$ from the value of $BPol$.

As a consequence, $(L,R)$ is a simple maximum cut for $G=(V,E)$ if and only if
$(L\cup\\{u^{-}\\},R\cup\\{u^{+}\\})$ is a bipartition for
$\mathcal{G}=\langle{\mathcal{C}},{\mathcal{E}},{\mathcal{S}},{\mathcal{W}}\rangle$
with maximum BipPol value.

This reduction shows two interesting facts about our problem. First, we can
have instances that are as hard to solve as the Maxcut problem when almost all
the users have ${\mathcal{S}}(v)=0$. But at the same time, observe that we
need to have at least one user with negative value and another one with
positive value. This is because if strictly all the users have
${\mathcal{S}}(v)=0$ then the $BipPol(L,R,{\mathcal{G}})$ value is equal to
zero for any bipartition $(L,R)$ and then it becomes trivial to solve the
problem. These facts together with the experimental results in [1] with real
instances from Reddit discussions, where instances with polarization values
away from neutral were very easy to solve on average, makes us to present the
following hypothesis.

###### Hypothesis 1

On one hand, the closer the maximum bipartite polarization of a UDebG instance
is to zero, the more difficult is to find such bipartition as many possible
bipartitions will have a bipartite polarization very close to the optimum. On
the other hand, the closer the maximum bipartite polarization of a UDebG
instance is to one, the easier is to find such bipartition as any user $i$
will tend to have values for ${\mathcal{S}}(i)$ and $\mathcal{W}(i,j)$ that
are correlated, and users will tend to have only negative sentiment answers to
the users of the other side in the optimal bipartition.

The random generator model we present in Section 5 will be used in the
experimental section to try to check this hypothesis.

##  4 Solving the Bipartite Polarization Problem

To solve the Bipartite Polarization Problem we use two approaches, one based
on a complete algorithm to find the exact polarization, and another one based
on a local search algorithm that finds an approximate solution. The complete
algorithm uses the same SCIP branch-and-bound solver (version 8.0) [6] and the
same integer nonlinear programming formulation (MINLP) used in [1]. For the
approximate approach, we use a local search solver inspired by an algorithm
for the maxcut problem [4]. The algorithm uses a greedy approach based on a
steepest ascent hill climbing strategy plus restarts to escape from local
minimas. The number of steps of the local search algorithm is bounded by the
number of nodes, and the number of restarts is set to 10. So the worst case
running time of the local search approach is linear in the number of nodes.

##  5 A Random Generator Model for UDebG Instances

We present a random generator of UDebG instances where the goal is to control
the expected bipartite polarization of the instance by means of a single
parameter $\alpha$ that lies in the range $(0,1]$. The number of nodes (users)
is given by a parameter $m$. The generation process consists of the two
following steps:

  1. 1.

Generation of the set of nodes $\mathcal{C}$ with their $\mathcal{S}(C_{i})$
value. Each node $C_{i}$ is generated with a value $\mathcal{S}(C_{i})$ from
$[-\alpha,\alpha]$ obtained with a bimodal distribution that arises as a
mixture of two different truncated normal distributions
$TN(-\alpha,0,\mu_{1},\sigma_{1})$ and $TN(0,\alpha,\mu_{2},\sigma_{2})$
333Note that for $\alpha=0$, all the nodes would have $\mathcal{S}(C_{i})=0$.
This extreme case corresponds to the trivial problem where the bipartite
polarization is zero for any bipartition. For this reason, $\alpha=0$ is not
considered in our random generator.. The first distribution is defined on the
interval $[-\alpha,0]$ with mean $\mu_{1}$ and standard deviation $\sigma_{1}$
equal to:

$\mu_{1}=-\alpha,\ \sigma_{1}=\frac{1}{1+20\alpha}$

and anologously for the second distribution, but now defined on the interval
$[0,\alpha]$ and with values:

$\mu_{2}=\alpha,\ \sigma_{2}=\frac{1}{1+20\alpha}$

So, with this bimodal distribution the values are concentrated around the two
modes ($-\alpha$ and $\alpha$), but how tightly they concentrate is inversely
proportional to $\alpha$, so the higher the value of $\alpha$ the smaller the
standard deviation.

  2. 2.

Generation of the set of edges $\mathcal{E}$ with their $\mathcal{W}(i,j)$
value. For each node $i$, we randomly select a set of $k$ target vertices
$\\{j_{1},j_{2},\ldots,j_{k}\\}$, with $k$ randomly selected from
$[1,\lceil\log_{10}(m)\rceil]$, to build outgoing edges from $i$ to those
vertices. The value of $\mathcal{W}(i,j)$ is generated with a truncated normal
distribution on the interval $[-2,2]$ with $\mu$ and $\sigma$ that depend on
the values of $\mathcal{S}(C_{i})$ and $\mathcal{S}(C_{j})$ as follows:

$\mu=\left\\{\begin{array}[]{ll}2\cdot|\mathcal{S}(C_{i})|-|\mathcal{S}(C_{i})-\mathcal{S}(C_{j})|&\textrm{if}\
C_{i},C_{j}\textrm{\ \ same side}\\\
-|\mathcal{S}(C_{i})|\cdot|\mathcal{S}(C_{i})-\mathcal{S}(C_{j})|&\textrm{if}\
C_{i},C_{j}\textrm{\ \ different side}\\\ \end{array}\right.$
$\sigma=\frac{2}{3+10|\mu|}$

So, when the users $C_{i}$ and $C_{j}$ are on the same side
($\mathcal{S}(C_{i})$ and $\mathcal{S}(C_{j})$ are both either positive or
$\leq 0$), the mean of the distribution will be positive and the more similar
are the values $\mathcal{S}(C_{i})$ and $\mathcal{S}(C_{j})$ and the closer is
$|\mathcal{S}(C_{i})|$ to 1, the closer will be $\mu$ to 2. By contrast, when
the users $C_{i}$ and $C_{j}$ are on different sides, the more different are
the values $\mathcal{S}(C_{i})$ and $\mathcal{S}(C_{j})$ and the closer is
$|\mathcal{S}(C_{i})|$ to 1 , the closer will be $\mu$ to -2. So, observe that
the sign of $\mu$ depends on the sign of users $i$ and $j$. Regarding the
absolute value $|\mu|$, it depends on both $\mathcal{S}(C_{i})$ and
$\mathcal{S}(C_{j})$, but more on the first one. This is because in principle
the overall sentiment $\mathcal{W}(i,j)$ (answers from user $i$ to user $j$)
is not necessarily equal to $\mathcal{W}(j,i)$, although it is natural to
think that there will be some positive correlation between them. In any case,
we think that it makes sense to force the sign of the mean to be the same one
when generating $\mathcal{W}(i,j)$ and $\mathcal{W}(j,i)$. As for the absolute
value, it is natural that users with stronger opinions (those with
$|\mathcal{S}(C_{i})|$ closer to $1$) have stronger sentiments towards the
rest of the users.

The overall intention of this way to select the values of $\mathcal{S}(C_{i})$
and $\mathcal{W}(i,j)$ is to move from a UDebG instance corresponding to a
clearly neutral discussion when $\alpha$ approaches $0$ to one corresponding
to a highly polarized discussion when $\alpha$ approaches $1$. We control this
by making the expected values of both $\mathcal{S}(C_{i})$ and
$\mathcal{W}(i,j)$ to approach the neutral value $0$ as $\alpha$ approaches
$0$. Observe, however, that even in the case when $\mu=0$ for the generation
of $\mathcal{W}(i,j)$ the standard deviation is $2/3$. This allows the
generation of some negative and positive values around the mean to ensure a
more realistic generation of users where not all the answers to any user are
strictly neutral. Then, as $\alpha$ approaches $1$, the expected value for
$\mathcal{S}(C_{i})$ tends to be more tightly concentrated around -1 or 1 due
to the standard deviation tending to $1/21$ and the expected value for
$\mathcal{W}(i,j)$ is more concentrated around the extreme values $-2$ and $2$
due to the standard deviation tending to $2/13$.

We make that for $\alpha=1$ the standard deviation for the generation of
$\mathcal{S}(C_{i})$ and $\mathcal{W}(i,j)$ to not be $0$, but very low,
because we do not believe that in practice one encounters real discussions
with such extreme polarization value of 1. So, we have preferred instead to
move towards a zone of high polarization, but without reaching the extreme
case. However, it is very easy to expand the range of possible polarizations
by simply using other values to move the standard deviation of both
distributions closer to 0 as $\alpha$ approaches $1$.

To select the number of out edges for each node, we use the function $\lceil
log_{10}(m)\rceil$ as the maximum number of out edges per node. Once more, we
use this function as we believe this represents better the number of
interactions of real debates in social networks. If we compute the maximum out
degree and mean out degree of each instance used in [1] 444Instances obtained
from the authors of the paper., we obtain that the mean of the maximum out
degree of all the instances is 4.05, and the mean of the mean out degree of
all the instances is 0.89, where the instances have a median number of nodes
around 50 555There are some nodes (users) that only answer to the root node.
As the answers to the root node are not considered for the UDebG, they do not
have out edges, so it is possible to have a mean out degree below 1 in the
UDebG.. With those numbers in mind, the $log_{10}(m)$ function allows us to
limit the maximum out degree to a realistic number of edges as $m$ increases,
and at the same time keep a low mean value.

Figure 1: CPU time needed to solve the instances (left plot) and polarization
of the solution (right plot) as we increase the alpha value for instances with
nodes ranging from 25 to 40.

##  6 Experimental Results

In this section we present an empirical evaluation of the complexity to solve
the instances obtained with our random generator for different values of the
parameter $\alpha$ and increasing the number of nodes (users) of the
instances. Our main interest is to understand how the complexity of the exact
algorithm based on integer programming changes as $\alpha$ moves from almost
$0$ to $1$. As a second goal, we want also to compare the quality of the
approximate polarization value returned by the algorithm based on local
search. The results reported in [1] indicate that for real instances, coming
from Reddit discussions, the median time complexity was always very low and
that the approximation of the polarization value given by the local search
algorithm was always almost identical to the exact value. The experiments were
performed on an Intel® Core® i5-6400 CPU at 2.70GHz with 16GB of RAM memory.

The results of the median time to solve instances with
$\alpha\in\\{0.05,0.08,0.11,0.14,0.4,0.7,1.0\\}$ and $m\in\\{25,30,35,40\\}$
as well as the bipartite polarization of the instances are shown on Figure 1.
For each combination of $\alpha$ and $m$, the median shown on the figure is
obtained from a set of 50 instances obtained with our random generator. We
have used close values of $\alpha$ up to $0.14$ because as one can observe,
the median time to solve the instances increases quickly as $m$ increases for
very low values of $\alpha$, but as we move away from $0$ the median time
decreases abruptly. At the same time, the median bipartite polarization of the
instances increases slowly for low values of $\alpha$ but then it starts to
increase more quickly as $\alpha$ increases. So, these results are consistent
with our hypothesis about the relation between polarization and complexity to
solve the instances.

Figure 2: Number of nodes of the SCIP search tree needed to solve the
instances as we increase the alpha value for instances with nodes ranging from
25 to 40.

If we compare these results with the ones with real instances from Reddit in
[1], that have median number of nodes around 50, we observe that they are also
consistent, in the sense that in the Reddit discussions used in that paper the
median polarization of the instances was around 0.5, and the median time was
around 2 seconds. To make a more fair comparison of the complexity, given that
we do not know the exact hardware used in that paper to solve the instances,
we have also computed the median number of nodes performed by the exact
algorithm based on the SCIP solver (the same one used in that previous paper),
given that in the previous paper the authors also showed the median number of
nodes of the SCIP search tree. Figure 2 shows the median number of nodes for
the same instances of Figure 1. As we can observe, the number of nodes follows
the same qualitative behavior as the time, and for instances with median
polarization around 0.5 (that have $\alpha>0.7$) the median number of nodes
would be around 1 (by interpolating between our cases $\alpha=0.7$ and
$\alpha=1.0$), like it happens in the results of [1] with the Reddit
instances.

Finally, we were also interested in comparing the quality of the approximation
provided by the local search approach, presented in Section 4, with the one of
the exact algorithm. Table 1 shows, for each combination of number of nodes
and value of $\alpha$, the minimum, median and maximum value for the
polarization obtained in each set of instances with the exact algorithm
(columns labeled with SCIP BipPol). Observe that is for higher values of
$\alpha$ where we observe more variations in the polarization of the instances
(difference between the min and the max values). Then, in the next three
columns we show for the same three instances of the previous columns (instance
with minimum polarization, with median one, and with maximum one) the ratio of
the approximate polarization computed by the local search solver to the exact
polarization of the instance (LS ratio). As we observe, the quality of the
solutions computed by the local search algorithm is perfect for instances with
$\alpha\geq 0.4$ (that are precisely the ones that are easily solved by the
exact algorithm) and for lower values of $\alpha$ we observe only a tiny
relative error. Overall, we can say that the quality of the solution provided
by the local search algorithm is always satisfactory with the advantage that
its computational complexity is always linear with respect to the number of
nodes, so there is no hard region for the local search approach.

Table 1: Comparison of the quality of the solutions between SCIP and LS solvers for different $\alpha$ values and number of nodes in the range 25-40. |  | SCIP BipPol | LS ratio
---|---|---|---
$m$ | $\alpha$ | min | median | max | min | median | max
25 | 0.05 | 0.0001 | 0.0003 | 0.0005 | 1 | 0.998 | 1
0.08 | 0.0004 | 0.0008 | 0.0013 | 1 | 0.9995 | 0.9999
0.11 | 0.0007 | 0.0015 | 0.0025 | 1 | 0.9998 | 1
0.14 | 0.0013 | 0.0025 | 0.0042 | 1 | 1 | 0.9999
0.4 | 0.0359 | 0.0497 | 0.0611 | 1 | 1 | 1
0.7 | 0.1907 | 0.2487 | 0.2786 | 1 | 1 | 1
1.0 | 0.4834 | 0.6631 | 0.7446 | 1 | 1 | 1
30 | 0.05 | 0.0002 | 0.0003 | 0.0005 | 0.9963 | 0.9985 | 0.9989
0.08 | 0.0005 | 0.0008 | 0.0012 | 0.9989 | 0.9995 | 0.9992
0.11 | 0.0010 | 0.0015 | 0.0023 | 0.9997 | 0.9997 | 1
0.14 | 0.0017 | 0.0025 | 0.0038 | 0.9998 | 0.9999 | 0.9999
0.4 | 0.0424 | 0.0505 | 0.0597 | 1 | 1 | 1
0.7 | 0.2046 | 0.2492 | 0.2724 | 1 | 1 | 1
1.0 | 0.5289 | 0.6657 | 0.7459 | 1 | 1 | 1
35 | 0.05 | 0.0002 | 0.0003 | 0.0005 | 1 | 0.9991 | 1
0.08 | 0.0006 | 0.0008 | 0.0012 | 1 | 0.9996 | 1
0.11 | 0.0011 | 0.0015 | 0.0022 | 0.9996 | 0.9999 | 1
0.14 | 0.0018 | 0.0025 | 0.0037 | 0.9998 | 1 | 1
0.4 | 0.0432 | 0.0503 | 0.0588 | 1 | 1 | 1
0.7 | 0.2150 | 0.2482 | 0.2697 | 1 | 1 | 1
1.0 | 0.5530 | 0.6590 | 0.7490 | 1 | 1 | 1
40 | 0.05 | 0.0002 | 0.0003 | 0.0004 | 1 | 1 | 0.9983
0.08 | 0.0006 | 0.0008 | 0.0011 | 0.9994 | 1 | 0.9989
0.11 | 0.0011 | 0.0015 | 0.0021 | 0.9996 | 0.9995 | 0.9995
0.14 | 0.0018 | 0.0025 | 0.0035 | 0.9995 | 0.9999 | 0.9999
0.4 | 0.0423 | 0.0507 | 0.0574 | 1 | 1 | 1
0.7 | 0.2113 | 0.2481 | 0.2679 | 1 | 1 | 1
1.0 | 0.5491 | 0.6553 | 0.7400 | 1 | 1 | 1

##  7 Conclusions

We have presented a random generator of User Debate Graph instances, where a
parameter $\alpha$ is introduced to control the expected bipartite
polarization of the instances. As previous results with real instances seemed
to indicate that instances with polarization away from neutral (0) were easy
to solve on average, we wanted to check if this was still the case when
working with instances with a more wide set of polarization values.

On the one hand, the results obtained are consistent with the ones obtained
with real instances, but show that hard to solve instances are in principle
possible, at least for very low polarization values, something that is
consistent with the fact that the problem is NP-hard. On the other hand, the
results also show that the verification of polarization with this measurement
seems difficult only in unrealistic cases, so that it can be used to monitor
polarization in online debates with the final goal to inform solutions for
creating healthier social media environments.

Despite the existence of hard instances, they are tightly concentrated around
a very thin region with very low polarization (that we could argue that it
represents a zone of uncommon real instances), and in any case the results
about the quality of the solutions obtained with the efficient local search
approach indicates that it is a good approach to make the computation of the
polarization feasible. Of course, it could be that some specific
characteristics of instances coming from some social networks could be not
significantly present in our random generator model, or that other measures of
polarization could present a different behavior to the one of the measure used
in this work. So, as future work, we could consider the validation of our
model with respect to other social networks and consider alternative measures
for the polarization that could make sense in some settings, as the
polarization metric introduced in [9] to analyze opinions expressed on the gun
control issue in Twitter.

## Acknowledgements

This work was partially funded by Spanish Project
PID2019-111544GB-C22/AEI/10.13039/501100011033 (MICIN), consolideted research
group grant 2021-SGR-01615.

## References

  * [1] Teresa Alsinet, Josep Argelich, Ramón Béjar, and Santi Martínez, ‘Approximate and optimal solutions for the bipartite polarization problem’, in Artificial Intelligence Research and Development - Proceedings of the 24th International Conference of the Catalan Association for Artificial Intelligence, CCIA 2022, Sitges, Spain, 19-21 October 2022, eds., Atia Cortés, Francisco Grimaldo, and Tommaso Flaminio, volume 356 of Frontiers in Artificial Intelligence and Applications, pp. 17–24. IOS Press, (2022).
  * [2] Teresa Alsinet, Josep Argelich, Ramón Béjar, and Santi Martínez, ‘Measuring polarization in online debates’, Applied Sciences, 11(24), (2021).
  * [3] Pablo Barberá, Social Media, Echo Chambers, and Political Polarization, 34–55, SSRC Anxieties of Democracy, Cambridge University Press, 2020.
  * [4] Una Benlic and Jin-Kao Hao, ‘Breakout local search for the max-cutproblem’, Eng. Appl. Artif. Intell., 26(3), 1162–1173, (2013).
  * [5] Alessandro Bessi, Fabiana Zollo, Michela Del Vicario, Michelangelo Puliga, Antonio Scala, Guido Caldarelli, Brian Uzzi, and Walter Quattrociocchi, ‘Users polarization on facebook and youtube’, PLoS ONE, 11(8), (2016).
  * [6] Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, Leona Gottwald, Christoph Graczyk, Katrin Halbig, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Thorsten Koch, Marco Lübbecke, Stephen J. Maher, Frederic Matter, Erik Mühmer, Benjamin Müller, Marc E. Pfetsch, Daniel Rehfeldt, Steffan Schlein, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Boro Sofranac, Mark Turner, Stefan Vigerske, Fabian Wegscheider, Philipp Wellner, Dieter Weninger, and Jakob Witzig, ‘The scip optimization suite 8.0’, Technical Report 21-41, ZIB, Takustr. 7, 14195 Berlin, (2021).
  * [7] Levi Boxell, Matthew Gentzkow, and Jesse M. Shapiro, ‘Cross-country trends in affective polarization’, National Bureau of Economic Research, (2020).
  * [8] William J. Brady, Julian A. Wills, John T. Jost, and Jay J. Van Bavel, ‘Emotion shapes the diffusion of moralized content in social networks’, Psychological and Cognitive Sciences, 114(28), 7313–7318, (2017).
  * [9] Pedro Henrique Calais Guerra, Wagner Meira Jr., Claire Cardie, and Robert Kleinberg, ‘A measure of polarization on social media networks based on community boundaries’, in Proceedings of the Seventh International Conference on Weblogs and Social Media, ICWSM 2013, Cambridge, Massachusetts, USA, July 8-11, 2013, eds., Emre Kiciman, Nicole B. Ellison, Bernie Hogan, Paul Resnick, and Ian Soboroff. The AAAI Press, (2013).
  * [10] Emily Kubin and Christian von Sikorski, ‘The role of (social) media in political polarization: a systematic review’, Annals of the International Communication Association, 45(3), 188–206, (2021).
  * [11] Philipp Lorenz-Spreen, Lisa Oswald, Stephan Lewandowsky, and Ralph Hertwig, ‘A systematic review of worldwide causal and correlational evidence on digital media and democracy’, Nat Hum Behav, 7, 74–101, (2023).
  * [12] Gianmarco De Francisci Morales, Corrado Monti, and Michele Starnini, ‘No echo in the chambers of political interactions on reddit’, Scientific Reports, 11(2818), (2021).
  * [13] Akiko Murakami and Rudy Raymond, ‘Support or oppose? classifying positions in online debates from reply activities and opinion expressions’, in COLING 2010, 23rd International Conference on Computational Linguistics, Posters Volume, 23-27 August 2010, Beijing, China, eds., Chu-Ren Huang and Dan Jurafsky, pp. 869–875. Chinese Information Processing Society of China, (2010).
  * [14] Steve Rathje, Jay J. Van Bavel, and Sander van der Linden, ‘Out-group animosity drives engagement on social media’, Psychological and Cognitive Sciences, 118(26), (2021).
  * [15] Raquel Recuero, Felipe Bonow Soares, and Anatoliy A. Gruzd, ‘Hyperpartisanship, disinformation and political conversations on twitter: The brazilian presidential election of 2018’, in Proceedings of the Fourteenth International AAAI Conference on Web and Social Media, ICWSM 2020, Held Virtually, Original Venue: Atlanta, Georgia, USA, June 8-11, 2020, eds., Munmun De Choudhury, Rumi Chunara, Aron Culotta, and Brooke Foucault Welles, pp. 569–578. AAAI Press, (2020).
  * [16] Guy Rosen.  Facebook: Investments to fight polarization.  https://about.fb.com/news/2020/05/investments-to-fight-polarization/, 2020\.  date: 2020-05-27.
  * [17] Cass R. Sunstein, ‘The law of group polarization’, Journal of Political Philosophy, 10(2), (2002).
  * [18] Michela Del Vicario, Gianna Vivaldo, Alessandro Bessi, Fabiana Zollo, Antonio Scala, Guido Caldarelli, and Walter Quattrociocchi, ‘Echo chambers: Emotional contagion and group polarization on facebook’, Scientific Reports, 6(37825), (2016).
  * [19] Mihalis Yannakakis, ‘Node- and edge-deletion np-complete problems’, in Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, eds., Richard J. Lipton, Walter A. Burkhard, Walter J. Savitch, Emily P. Friedman, and Alfred V. Aho, pp. 253–264. ACM, (1978).
  * [20] Moran Yarchi, Christian Baden, and Neta Kligler-Vilenchik, ‘Political polarization on the digital sphere: A cross-platform, over-time analysis of interactional, positional, and affective polarization on social media’, Political Communication, 38(1-2), 98–139, (2021).