# Detecting Antagonistic and Allied Communities on Social Media

Amin Salehi, Hasan Davulcu  Computer Science and Engineering
Arizona State University, Tempe, USA
{asalehi1<EMAIL_ADDRESS>
###### Abstract

Community detection on social media has attracted considerable attention for
many years. However, existing methods do not reveal the relations between
communities. Communities can form alliances or engage in antagonisms due to
various factors, e.g., shared or conflicting goals and values. Uncovering such
relations can provide better insights to understand communities and the
structure of social media. According to social science findings, the attitudes
that members from different communities express towards each other are largely
shaped by their community membership. Hence, we hypothesize that inter-
community attitudes expressed among users in social media have the potential
to reflect their inter-community relations. Therefore, we first validate this
hypothesis in the context of social media. Then, inspired by the hypothesis,
we develop a framework to detect communities and their relations by jointly
modeling users’ attitudes and social interactions. We present experimental
results using three real-world social media datasets to demonstrate the
efficacy of our framework.

††publicationid: pubid: IEEE/ACM ASONAM 2018, August 28-31, 2018, Barcelona,
Spain 978-1-5386-6051-5/18/$31.00 © 2018 IEEE

##  I Introduction

Although community detection plays an important role in providing insights
into the structure and function of social media [1], existing community
detection methods do not reveal inter-community relations, which are
indispensable to deepen our insights. Moreover, to better understand
communities, there is a need to uncover their relations. Indeed, social
scientists suggest that “the understanding of policies and practices
prevailing within groups will be inadequate unless relations among them are
brought into the picture” [2]. A community, or group in social sciences, is
defined as a set of users with many intra-group social interactions and few
inter-group ones [3], who tend to have mainly positive attitudes towards each
other [4, 5].

Several methods [6, 7, 8, 9, 10, 11] have been proposed to detect antagonistic
communities. There are generally two categories of such methods: (1) those
which detect antagonistic communities from signed networks [6, 7, 8, 9], and
(2) those which mine antagonistic communities by finding frequent patterns in
users’ ratings [10, 11]. However, these methods suffer from two main
limitations. First, they cannot be applied to a majority of popular social
network platforms (e.g., Facebook and Twitter) since these platforms do not
provide signed links or users’ ratings explicitly. Second, inter-community
relations are not restricted to antagonisms. Indeed, communities can also form
alliances.

According to social science findings, inter-community attitudes that
individuals express towards each other are largely shaped by their community
membership rather than their characteristics or personal relationships [12,
13]. Moreover, Tajfel [14] observed a pair of characteristics in inter-
community behavior. First, the members of a community display uniformity in
their behavior and attitude towards any other community. Second, they tend to
perceive the characteristics and behavior of the members of any other
community as undifferentiated. Moreover, social scientists suggest that “the
social psychology of intergroup relations is concerned with intergroup
behaviour and attitudes” [14]. According to these observations, inter-
community attitudes that users express towards each other in social media have
the potential to reflect inter-community relations.

In this paper, we propose a framework, namely DAAC, which detects communities
and their relations (i.e., antagonism, alliance, or neither) by exploiting
users’ social interactions (e.g., retweets) and attitudes expressed on social
media. Our main contributions are:

  * •

Validating the hypothesis suggesting that inter-community attitudes that users
express towards each other in social media can reflect the relations of their
communities;

  * •

Achieving higher performance in detecting communities compared to several
standard community detection methods;

  * •

Uncovering inter-community relations, i.e., antagonism, alliance, or no
relation.

The rest of the paper is organized as follows. In Section II, we review
related work. In Section III, we formally define the problem of detecting
communities and their relations on social media. Section IV describes three
real-world social media datasets used in our experiments. In Section V, we
first validate the aforementioned hypothesis and then present our framework.
In Section VI, we demonstrate the effectiveness of the proposed framework.
Section VII concludes the paper and discusses future work.

##  II Related Work

There has been a lot of efforts to detect communities efficiently and
accurately. To this end, a wide variety of approaches have been utilized.
Modularity-based methods are among the most well-know techniques to detect
communities. The modularity measure proposed in [15] evaluates whether a
division is good enough to form communities. Many variants of modularity-based
community detection [16, 17] have been developed. Another well-known category
includes spectral algorithms [18, 19, 20, 21] which aims to divide the network
into several communities in which most of the interactions are within
communities while the number of interactions across communities are minimized.
Probabilist approaches [22], in which users are assigned to clusters in a
probabilistic way, are also applied to the problem of community discovery.
There are a variety of approaches such as information theory based methods
[23], random walk techniques [24, 25], and model-based methods [26, 27] to
tackle this problem.

Although there has been a great deal of efforts to detect communities, to the
best of our knowledge, no previous work has been proposed to uncover the
existence of antagonism and alliance between communities. However, some
efforts have been made [6, 7, 8, 9, 10, 11] to detect only antagonistic
communities. These methods can be roughly divided into two main categories.
First category includes the methods [10, 11] utilizing frequent patterns in
users’ ratings to mine antagonistic communities. Second category includes the
methods [6, 7, 8, 9] utilizing signed networks, having trust and distrust
links, to detect antagonistic communities. A majority of these methods [7, 8,
9] detect a pair of subgraphs with most trust links preserved between the
members of each subgraph and most distrust links remained between the members
of different subgraphs. These methods are limited to detecting only a pair of
antagonistic communities. To address this limitation, another method [6] has
been proposed to detect multiple antagonistic communities by finding several
dense subgraphs with the mentioned property. However, as experiments in [6]
show such methods usually end up with large number of small subgraphs due to
high sparsity of users’ interactions in social media.

##  III Problem Statement

We first begin with the introduction of the notations used in the paper as
summarized in Table I. Let $\mathcal{U}=\\{u_{1},u_{2},...,u_{n}\\}$ be the
set of $n$ users and $\mathcal{C}=\\{c_{1},c_{2},...,c_{k}\\}$ indicate the
set of $k$ communities. $\mathbf{R}\in\mathbb{R}_{+}^{n\times n}$ denotes the
social interaction matrix, where $\mathbf{R}_{i,j}$ corresponds to the number
of social interactions between user $u_{i}$ and user $u_{j}$.
$\mathbf{S}\in\mathbb{R}^{n\times n}$ indicates the attitude matrix, where the
positive/negative value of $\mathbf{S}_{i,j}$ corresponds to the
positive/negative attitude strength of user $u_{i}$ towards user $u_{j}$.
$\mathbf{U}\in\mathbb{R}_{+}^{n\times k}$ indicates the community membership
matrix, in which $\mathbf{U}_{i,l}$ corresponds to the membership strength of
user $u_{i}$ to community $c_{l}$. $\mathbf{H}\in\mathbb{R}^{k\times k}$
denotes intra/inter-community relation matrix, where $\mathbf{H}_{i,j}$, if
$i\neq j$, corresponds to the strength and type of inter-community relation
between community $c_{i}$ and community $c_{j}$; the negative, positive, and
zero value of $\mathbf{H}_{i,j}$ indicates antagonism, alliance, or no
relation between community $c_{i}$ and community $c_{j}$, respectively.
Moreover, $\mathbf{H}_{i,i}$ corresponds to the intra-community attitudes that
the members of community $c_{i}$ have expressed towards each other. We define
the symmetric normalization of $\mathbf{R}$ as
$\overset{\sim}{\mathbf{R}}=\mathbf{D}^{-1/2}\mathbf{R}\mathbf{D}^{-1/2}$,
where $\mathbf{D}=diag(d_{1},d_{2},...,d_{n})$ is the degree matrix of
$\mathbf{R}$ and the degree of user $u_{i}$ is
$d_{i}=\sum_{j=1}^{n}\mathbf{R}_{i,j}$. We separate positive and negative
parts of matrix $\mathbf{A}$ as
$\mathbf{A}_{i,j}^{+}=(|\mathbf{A}_{i,j}|+\mathbf{A}_{i,j})/2$ and
$\mathbf{A}_{i,j}^{-}=(|\mathbf{A}_{i,j}|-\mathbf{A}_{i,j})/2$.

By using the aforementioned notations, the problem of detecting communities
and their relations on social media can be defined as: Given social
interaction matrix $\mathbf{R}$ and attitude matrix $\mathbf{S}$, we aim to
obtain community membership matrix $\mathbf{U}$ and intra/inter-community
relation matrix $\mathbf{H}$.

TABLE I: Notations used in the paper Notation | Explanation
---|---
$\mathcal{U}$ | The set of users
$\mathcal{C}$ | The set of communities
$n$ | The number of users
$k$ | The number of communities
$\mathbf{R}$ | The social interaction matrix
$\mathbf{S}$ | The attitude matrix
$\mathbf{U}$ | The community membership matrix
$\mathbf{H}$ | The community intra/inter-relation matrix
$\overset{\sim}{\mathbf{R}}$ |  Symmetrically normalized matrix $\mathbf{R}$
$\mathbf{D}$ |  Degree matrix of $\mathbf{R}$
$\mathbf{A}^{+}$ |  The positive part of matrix $\mathbf{A}$ (i.e., $(|\mathbf{A}|+\mathbf{A})/2$)
$\mathbf{A}^{-}$ |  The negative part of matrix $\mathbf{A}$ (i.e., $(|\mathbf{A}|-\mathbf{A})/2$)

##  IV Data Description

Politics is a domain in which it is common among political parties (i.e.,
communities) to form alliances or engage in antagonisms. To validate the
aforementioned hypothesis and evaluate our proposed framework, we use the
following political Twitter datasets:

  * •

US Dataset consists of the tweets posted by 583 politicians from two major US
political parties (the Republican Party and the Democratic Party) from August
26 to November 29, 2016. For the period of time that this dataset covers,
there were antagonisms between these parties particularly due to the 2016
presidential election campaigning [28].

  * •

Australia Dataset consists of the tweets posted by 225 user accounts,
including politicians and political groups, from five major Australian
political parties (the Liberal Party, the National Party, the Liberal National
Party, the Greens, and the Labor Party) from January 1 to November 18, 2016.
For several decades, there has been a coalition among the Liberal Party, the
National Party, and the Liberal National Party [29]. In the 2016 federal
election, all relations between the parties were antagonistic except the
relations between the members of the coalition,.

  * •

UK Dataset consists of the tweets posted by 389 user accounts, including
politicians and political groups, from five major UK political parties (the
Conservative Party, the Labour Party, the Scottish National Party, the Liberal
Democrats Party, and the UK Independence Party) from January 1 to October 31,
2015. There were antagonism among five major UK political parties in this
period of time, especially due to the 2015 general election campaigning [30].

Preprocessing: For all datasets, we remove the users who do not have any
retweet (i.e., social interaction). Table II shows the statistics of the
preprocessed datasets. All users in the datasets have been labeled with their
corresponding parties, and these labels are used to evaluate our proposed
method.

Although aspect-based sentiment classification techniques [31] have been
proposed to capture users’ attitudes towards entities, publicly available
training datasets are either too small or domain-oriented, making such
techniques incapable to tackle real-world problems. Therefore, we use the
following technique to extract the attitudes that users express towards each
other in social media. Given each message in which author $u_{i}$ has
mentioned user $u_{j}$, we add the strength of the message’s sentiment to the
corresponding elements of matrix $\mathbf{S}$ (i.e., $\mathbf{S}_{i,j}$). Even
though some messages may carry a negative sentiment, the author may not
necessarily have an antagonistic attitude towards a mentioned user. To
alleviate this problem, we ignore such messages if there is a social
interaction (i.e., retweet) between the author and the mentioned user since a
social interaction indicates the presence of a good relationship [32]. We
utilize SentiStrength [33] to detect the sentiment polarity and strength of
messages. We have made the code and datasets used in this paper
available111https://github.com/amin-salehi/DAAC.

TABLE II: The statistics of the cleaned datasets. | US | Australia | UK
---|---|---|---
# of tweets | 111,743 | 159,499 | 267,085
# of retweets | 17,724 | 21,111 | 14,892
# of mentions | 8,470 | 14,996 | 33,462
# of user accounts | 583 | 225 | 389
# of true communities | 2 | 5 | 5
# of allied relations | 0 | 3 | 0
# of antagonistic relations | 1 | 7 | 10

##  V The Proposed Framework

In this section, we first demonstrate the existence of a significant level of
correlation between the type of inter-community relation (i.e., alliance or
antagonism) between two communities and the type of sentiment (i.e., positive
or negative) that members from these communities expressed towards each other.
Next, we propose our framework.

###  V-A Validating the Hypothesis

According to social science findings [12, 13], the attitudes that members from
different communities express towards each other are largely shaped by their
community membership. Therefore, we hypothesize that inter-community attitudes
expressed among users towards each other in social media have the potential to
reflect inter-community relations. However, the findings borrowed from social
sciences do not necessarily hold in social media due to many factors, such as
the validity and representativeness of available information [34, 35].
Moreover, the attitudes that users express towards each other in social media
might result from users’ personal relationships. Therefore, in this section,
we aim to verify our hypothesis by answering the following two questions. With
this respect, we utilize the Australia dataset since it is the only dataset
containing both allied and antagonistic relations.

  * •

Are the communities of two users who express negative attitudes towards each
other more likely to be in antagonism?

  * •

Are the communities of two users who express positive attitudes towards each
other more likely to be in alliance?

We first answer the former by using the following procedure inspired by [36].
For each pair of users $(u_{i},u_{j})$ who are from different communities and
have expressed negative attitudes towards each other (i.e.,
$\mathbf{S}_{i,j}<0$), we randomly select a user $u_{k}$ where users $u_{i}$
and $u_{k}$ are from different communities and have not expressed negative
attitudes towards each other (i.e., $\mathbf{S}_{i,k}\geq 0$). Then, we check
whether there is antagonism between the communities of $u_{i}$ and $u_{j}$ and
between the communities of $u_{i}$ and $u_{k}$. If there is antagonism between
the communities of $u_{i}$ and $u_{j}$, we set $t_{p}=1$; otherwise $t_{p}=0$.
Similarly, if there is antagonism between the communities of $u_{i}$ and
$u_{k}$, we set $t_{r}=1$; otherwise $t_{r}=0$. Let vector $T_{p}$ denote the
set of all $t_{p}$s for pairs of users from different communities who have
expressed negative attitudes towards each other, and vector $T_{r}$ denote the
set of all $t_{r}$s for pairs of users from different communities who have not
expressed negative attitudes towards each other.

We conduct a two-sample t-test on $T_{p}$ and $T_{r}$. The null hypothesis
$H_{0}$ and alternative hypothesis $H_{1}$ are defined as follows:

$\displaystyle H_{0}:T_{p}\leq T_{r},\quad H_{1}:T_{p}>T_{r}$ (1)

The null hypothesis is rejected at significance level $a=0.01$ with p-value of
$3.56\mathrm{e}{-105}$. Therefore, the result of the two-sample t-test
demonstrates that the communities of two users who express negative attitudes
towards each other are highly probable to be in antagonism. We apply a similar
procedure to answer the second question. For brevity, we only report the
result of the two-sample t-test. The null hypothesis is rejected at
significance level $a=0.01$ with p-value of $1.57\mathrm{e}{-26}$. As a
result, we conclude that the communities of two users who express positive
attitudes towards each other are highly probable to be in alliance.

###  V-B Modeling Users’ Attitudes

In the previous section, we demonstrated that inter-community attitudes
expressed by users can reflect the relation of their communities in the
context of social media. Inspired by this observation, we propose a model
which uncovers intra/inter-community relations by exploiting the attitudes
users express towards each other as,

$\displaystyle\underset{\mathbf{U},\mathbf{H}}{\text{min}}$
$\displaystyle||\mathbf{W}\odot(\mathbf{S}-\mathbf{U}\mathbf{H}\mathbf{U}^{T})||_{F}^{2}$
(2) s.t. $\displaystyle\mathbf{U}\geq 0.$

where $\odot$ is Hadamard product, $\mathbf{W}_{i,j}$ controls the
contribution of $S_{i,j}$ in the model, and a typical choice of
$\mathbf{W}\in\mathbb{R}_{+}^{n\times n}$ is,

$\displaystyle\mathbf{W}=\left\\{\begin{array}[]{ll}0,\text{ if
}\mathbf{S}=0\\\ 1,\text{ otherwise }\\\ \end{array}\right.$ (3)

Given communities $c_{i}$ and $c_{j}$, Eq. (2) aims to uncover their inter-
community relation $\mathbf{H}_{i,j}$ by using their attitudes. To this end,
$\mathbf{U}_{:,i}\mathbf{H}_{i,j}\mathbf{U}_{:,j}^{T}$ estimates the inter-
community attitudes among the members of these two communities as presented in
matrix $\mathbf{S}$. Since the non-negativity constraint only holds on
$\mathbf{U}$, $\mathbf{H}_{i,j}$ will be negative, positive, or zero if the
members of two communities have generally expressed negative, positive, or no
attitudes towards each other, respectively. The lower the negative value of
$\mathbf{H}_{i,j}$ is, the more antagonistic communities $c_{i}$ and $c_{j}$
are. On the other hand, the larger the positive value of $\mathbf{H}_{i,j}$
is, the more allied communities $c_{i}$ and $c_{j}$ are. Moreover,
$\mathbf{H}_{i,i}$ indicates the intra-community attitudes that the members of
community $c_{i}$ have expressed towards each other.

###  V-C Modeling Social Interactions

Social interactions are one of the most effective sources of information to
detect communities [1]. In this section, we aim to cluster users into $k$
communities with the most social interactions within each community and the
fewest social interactions between communities. To this end, we use the
following model,

$\displaystyle\underset{\mathbf{U}}{\text{max}}$ $\displaystyle
Tr(\mathbf{U}^{T}\overset{\sim}{\mathbf{R}}\mathbf{U})$ (4) s.t.
$\displaystyle\mathbf{U}\geq 0,\mathbf{U}^{T}\mathbf{U}=\mathbf{I}.$

where $\mathbf{I}$ is the identity matrix with the proper size. In fact, Eq.
(4) is equivalent to the nonnegative relaxed normalized cut as put forth in
[19].

TABLE III: Comparison of community detection methods. | US dataset | Australia dataset | UK dataset
---|---|---|---
Method | NMI | ARI | Purity | NMI | ARI | Purity | NMI | ARI | Purity
Louvain | 0.431095 | 0.386347 | 0.943396 | 0.825234 | 0.833025 | 0.942222 | 0.858118 | 0.841718 | 0.987147
InfoMap | 0.431437 | 0.351938 | 0.946826 | 0.831903 | 0.831737 | 0.942222 | 0.909684 | 0.928716 | 0.992288
Leading eigenvectors | 0.580117 | 0.678051 | 0.938250 | 0.779931 | 0.573488 | 0.693334 | 0.913700 | 0.9533703 | 0.982005
CNM | 0.502925 | 0.487620 | 0.945111 | 0.842446 | 0.848269 | 0.937778 | 0.939093 | 0.971631 | 0.984576
Label propagation | 0.600777 | 0.655619 | 0.958833 | 0.822237 | 0.826724 | 0.937778 | 0.958379 | 0.979031 | 0.989717
Soft clustering | 0.735760 | 0.829228 | 0.955403 | 0.841264 | 0.812856 | 0.844444 | 0.951260 | 0.974292 | 0.987147
DAAC | 0.768307 | 0.854484 | 0.962264 | 0.903691 | 0.908264 | 0.951111 | 0.958806 | 0.978770 | 0.989717

###  V-D The Proposed Framework DAAC

We separately introduced our models to utilize users’ attitudes and social
interactions. In this section, we propose our framework DAAC, which jointly
exploits these two models to uncover communities and their relations. The
proposed framework requires solving the following optimization problem,

$\displaystyle\underset{\mathbf{U},\mathbf{H}}{\text{min}}$
$\displaystyle\bm{\mathcal{F}}=||\mathbf{W}\odot(\mathbf{S}-\mathbf{U}\mathbf{H}\mathbf{U}^{T})||_{F}^{2}-\lambda
Tr(\mathbf{U}^{T}\overset{\sim}{\mathbf{R}}\mathbf{U})$ (5) s.t.
$\displaystyle\mathbf{U}\geq 0,\mathbf{U}^{T}\mathbf{U}=\mathbf{I}.$

where $\lambda$ is a non-negative regularization parameter controlling the
contribution of social interactions in the final solution.

Algorithm 1 The Proposed Algorithm for DAAC

1:Input: attitude matrix $\mathbf{S}$ and social interaction matrix
$\mathbf{R}$

2:Output: community membership matrix $\mathbf{U}$ and intra/inter-community
relation matrix $\mathbf{H}$

3:Initialize $\mathbf{U}$ and $\mathbf{H}$ randomly where $\mathbf{U}\geq 0$

4:while not convergent do

5: Update $\mathbf{U}$ according to Eq. (6)

6: Update $\mathbf{H}$ according to Eq. (14)

7:end while

Since the optimization problem in Eq. (5) is not convex with respect to
variables $\mathbf{U}$ and $\mathbf{H}$ together, there is no guarantee to
find the global optimal solution. As suggested by [37], we introduce an
alternative scheme to find a local optimal solution of the optimization
problem. The key idea is optimizing the objective function with respect to one
of the variables $\mathbf{U}$ or $\mathbf{H}$, while fixing the other one. The
algorithm keeps updating the variables until convergence.

Optimizing the objective function $\mathcal{F}$ with respect to $\mathbf{U}$
leads to the following update rule,

$\mathbf{U}=\mathbf{U}\odot\sqrt{\frac{\mathbf{E}_{1}^{+}+\mathbf{E}_{2}^{+}+\mathbf{E}_{3}^{-}+\mathbf{E}_{4}^{-}+\lambda\overset{\sim}{\mathbf{R}}\mathbf{U}+\mathbf{U}\mathbf{\Gamma}^{-}}{\mathbf{E}_{1}^{-}+\mathbf{E}_{2}^{-}+\mathbf{E}_{3}^{+}+\mathbf{E}_{4}^{+}+\mathbf{U}\mathbf{\Gamma}^{+}}}$
(6)

where,

$\displaystyle\mathbf{E}_{1}=-(\mathbf{W}\odot\mathbf{W}\odot\mathbf{S})\mathbf{U}\mathbf{H}^{T}$
(7)
$\displaystyle\mathbf{E}_{2}=-(\mathbf{W}\odot\mathbf{W}\odot\mathbf{S})^{T}\mathbf{U}\mathbf{H}$
(8)
$\displaystyle\mathbf{E}_{3}=(\mathbf{W}\odot\mathbf{W}\odot\mathbf{U}\mathbf{H}\mathbf{U}^{T})\mathbf{U}\mathbf{H}^{T}$
(9)
$\displaystyle\mathbf{E}_{4}=(\mathbf{W}\odot\mathbf{W}\odot\mathbf{U}\mathbf{H}\mathbf{U}^{T})^{T}\mathbf{U}\mathbf{H}$
(10) $\displaystyle\mathbf{\Gamma}\ \
=-\mathbf{U}^{T}\mathbf{E}_{1}-\mathbf{U}^{T}\mathbf{E}_{2}-\mathbf{U}^{T}\mathbf{E}_{3}-\mathbf{U}^{T}\mathbf{E}_{4}$
(11) $\displaystyle\qquad\
+\lambda\mathbf{U}^{T}\overset{\sim}{\mathbf{R}}\mathbf{U}$ (12)

The details are given in the Appendix.

The derivative of $\bm{\mathcal{F}}$ with respect to $\mathbf{H}$ is as
follows:

$\displaystyle\frac{\partial\bm{\mathcal{F}}}{\partial\mathbf{H}}=$
$\displaystyle-2\mathbf{U}^{T}(\mathbf{W}\odot\mathbf{W}\odot\mathbf{S})\mathbf{U}$
(13)
$\displaystyle-2\mathbf{U}^{T}(\mathbf{W}\odot\mathbf{W}\odot\mathbf{U}\mathbf{H}\mathbf{U}^{T})\mathbf{U}$

Thus, the update rule of $\mathbf{H}$ is as follows:

$\mathbf{H}=\mathbf{H}-\alpha\frac{\partial\bm{\mathcal{F}}}{\partial\mathbf{H}}$
(14)

where $\alpha$ is the learning rate for updating $\mathbf{H}$.

The detailed algorithm for DAAC is shown in Algorithm 1. We briefly review
Algorithm 1. In line 1, it randomly initializes $\mathbf{U}$ and $\mathbf{H}$.
From line 2 to 5, it updates $\mathbf{U}$ and $\mathbf{H}$ until convergence
is achieved.

###  V-E Time Complexity

In Algorithm 1, the most costly operations are the matrix multiplications in
update rules Eq. (6) and Eq. (14) on which we focus in this section.
$\mathbf{W}$ and $\mathbf{R}$ are usually very sparse matrices, so let $N_{w}$
and $N_{r}$ denote the number of non-zero elements of $\mathbf{W}$ and
$\mathbf{R}$, respectively. The time complexities of Eq. (6) and Eq. (14) are
described as follows:

  * •

We first focus on the time complexity of Eq. (6). Note that
$\mathbf{W}\odot\mathbf{W}\odot\mathbf{S}$ needs to be calculated once.
Therefore, the time complexities of both $\mathbf{E_{1}}$ and $\mathbf{E_{2}}$
are $\mathcal{O}(N_{w}k+nk^{2})$ thanks to the sparsity of matrices
$\mathbf{W}$ and $\mathbf{S}$. The time complexity of
$\mathbf{W}\odot\mathbf{W}\odot\mathbf{U}\mathbf{H}\mathbf{U}^{T}$ is
$\mathcal{O}(N_{w}n+nk^{2}+n^{2}k)$. The number of non-zero values of
$\mathbf{W}\odot\mathbf{W}\odot\mathbf{U}\mathbf{H}\mathbf{U}^{T}$ is the same
as $\mathbf{W}$ owing to the sparsity of $\mathbf{W}$. Thus, the time
complexities of both $\mathbf{E_{3}}$ and $\mathbf{E_{4}}$ are
$\mathcal{O}(N_{w}n+nk^{2}+n^{2}k)$. Using a similar procedure, the time
complexities of $\overset{\sim}{\mathbf{R}}\mathbf{U}$ and $\mathbf{\Gamma}$
are $\mathcal{O}(N_{r}k)$ and $\mathcal{O}(N_{w}n+nk^{2}+n^{2}k+N_{r}k)$,
respectively. As a result, the time complexity of Eq. (6) is
$\mathcal{O}(N_{w}(n+k)+N_{r}k+nk^{2}+n^{2}k)$.

  * •

Now we provide the time complexity of Eq. (14). The cost of
$\mathbf{U}^{T}(\mathbf{W}\odot\mathbf{W}\odot\mathbf{S})$ is
$\mathcal{O}(N_{w}k)$ thanks to the sparsity of $\mathbf{W}$. Thus, the time
complexity of
$\mathbf{U}^{T}(\mathbf{W}\odot\mathbf{W}\odot\mathbf{S})\mathbf{U}$ is
$\mathcal{O}(N_{w}k+nk^{2})$. Similarly, the cost of
$\mathbf{U}^{T}(\mathbf{W}\odot\mathbf{W}\odot\mathbf{U}\mathbf{H}\mathbf{U}^{T})\mathbf{U}$
is $\mathcal{O}(N_{w}n+nk^{2}+n^{2}k)$. Therefore, the time complexity of Eq.
(14) is $\mathcal{O}(N_{w}(n+k)+nk^{2}+n^{2}k)$.

Hence, the time complexity of Algorithm 1 is
$\mathcal{O}(i(N_{w}(n+k)+N_{r}k+nk^{2}+n^{2}k))$ where $i$ is the number of
iterations required for the convergence. Our framework can be applied to large
scale social network platforms by exploiting distributed approaches outlined
in [38, 39, 40].

##  VI Experiments

To evaluate our proposed framework, we design the required experiments to
answer the following two questions.

  1. 1.

How effective is the proposed framework compared to the standard community
detection methods?

  2. 2.

How effective is our framework in discovering inter-community relations?

In the next section, we first compare the performance of several well-known
community detection methods with DAAC. Then, we evaluate the effectiveness of
our framework in uncovering inter-community relations. Finally, we study the
sensitivity of our framework with respect to regularization parameter
$\lambda$. For the experiments, we set the number of communities for any
method, if it is required, as the true number of communities (i.e., parties)
in each dataset.

###  VI-A Evaluation of Community Detection

####  VI-A1 Baselines

In order to demonstrate the efficacy of DAAC, we compare it with six well-
known community detection methods presented as follows:

  * •

Louvain: This method [17] greedily maximizes the benefit function known as
modularity to detect communities.

  * •

InfoMap: This baseline [23] is based on information theory and compresses the
description of random walks in order to find communities.

  * •

Leading eigenvectors: Newton [20] presents a formulation of modularity in a
matrix form, namely modularity matrix. Then, he proposes to use the
eigenvectors of modularity matrix to detect communities.

  * •

CNM: This method [16] uses a greedy approach to find the divisions of the
network which maximizes the modularity.

  * •

Label propagation: [26] This method initially assigns unique labels to users.
Then, in each iteration, users adopt the label that most of their neighbors
posses. Finally, users with the same label fall into the same community.

  * •

Soft clustering: This baseline [22] assigns users to communities in a
probabilistic way.

TABLE IV: The uncovered relations between detected communities (i.e., parties)
by using DAAC in the US dataset.

|  Republicans |  Democrats
---|---|---
Republicans |  259 |  -138
Democrats |  -138 |  112

_Note:_ all values in the table are rounded.

####  VI-A2 Performance Measures

To evaluate the performance of the methods, we utilize three following
measures which are frequently used for community detection evaluation:
Normalized Mutual Information (NMI), Adjusted Rand Index (ARI), and Purity.

####  VI-A3 Experimental Results

We run all methods with their hyperparameters initialized from
$\\{10^{x}|x\in[0,9]\\}$. Table III shows the best result for each method.
According to the table, we can make the following observations:

  * •

Our proposed framework achieves the highest performance in terms of NMI and
ARI for all three datasets. In terms of Purity, it also achieves the best in
US and Australia datasets. In the UK dataset, only InfoMap obtains higher
Purity compared to our framework since it generates a large number of
communities (e.g., 11 communities for the UK dataset) for sparse graphs such
as social media networks.

  * •

Our framework achieves its highest performance with large values of
regularization parameter $\lambda$ (e.g., $10^{7}$). This implies that social
interactions are more effective in detecting communities compared to users’
attitudes. We will study more on the impact of the regularization parameter in
Section VI-C.

TABLE V: The uncovered relations between detected communities (i.e., parties)
by using DAAC in the Australia dataset.

|  Liberals |  Nationalists |  Liberal Nationalists |  Labors |  Greens
---|---|---|---|---|---
Liberals |  87 |  61 |  34 |  -21 |  -32
Nationalists |  61 |  52 |  46 |  -4 |  -22
Liberal Nationalists |  34 |  46 |  39 |  -4 |  -61
Labors |  -21 |  -4 |  -4 |  121 |  -31
Greens |  -32 |  -22 |  -61 |  -31 |  64

_Note:_ all values in the table are rounded.

###  VI-B Evaluation of Inter-community Relations

In this section, we evaluate the effectiveness of our proposed framework in
uncovering inter-community relations by conducting two experiments. To the
best of our knowledge, there is no previous work to discover inter-community
antagonistic and allied relations. Therefore, as the first experiment, we
compare the inter-community relations which our framework detects with the
real-word inter-community relations. Each community detected by our framework
is labeled with the party to which the majority of its members belong. Then,
we evaluate inter-community relations (i.e., matrix $\mathbf{H}$) detected by
our algorithm according to the known ground-truth inter-party relations as
previously presented in Section IV.

Table IV shows intra/inter-community relation matrix $\mathbf{H}$ for the US
dataset as well as the parties corresponding to the detected communities. In
2016, the Republican Party and the Democratic Party were strongly antagonistic
towards each other, especially due to the 2016 presidential election
campaigning222https://en.wikipedia.org/wiki/United_States_presidential_election,_2016
[28]. As Table IV shows, our framework uncovers the existence of strong
antagonism between these two parties. It also discovers that intra-community
attitudes among the members of each community are highly positive as expected
owing to the election campaign dynamics.

Table V shows intra/inter-community relation matrix $\mathbf{H}$ for the
Australia dataset as well as the parties corresponding to the detected
communities. The Liberal Party, the National Party, and the Liberal National
party forged a coalition in the 2016 federal election. Except the relations
between the members of the coalition, other relations among all parties were
antagonistic333https://en.wikipedia.org/wiki/Australian_federal_election,_2016.
As shown in Table V, our framework uncovers the coalition in which the three
involved parties are in alliance with each other. It also discovers antagonism
between the members of the coalition and other parties as well as the
antagonism between the Greens and the Labor Party. Moreover, it detects high
positive intra-community attitudes among the members of communities as
expected.

Table VI shows intra/inter-community relation matrix $\mathbf{H}$ for the UK
dataset as well as the parties corresponding to the detected communities. In
2015, there were antagonisms between all five major UK political parties,
especially due to the 2015 general election
campaigning444https://en.wikipedia.org/wiki/United_Kingdom_general_election,_2015
[30]. As shown in Table VI, our framework correctly detects all antagonistic
relations between these parties. It also discovers that intra-community
attitudes among the members of each community are highly positive as expected.

TABLE VI: The uncovered relations between detected communities (i.e., parties)
by using DAAC in the UK dataset.

|  Conservatives |  Labours |  Lib dems |  SNPs |  UKIPs
---|---|---|---|---|---
Conservatives |  154 |  -37 |  -7 |  -21 |  -9
Labours |  -37 |  242 |  -8 |  -11 |  -26
Lib dems |  -7 |  -8 |  63 |  -3 |  -14
SNPs |  -21 |  -11 |  -3 |  55 |  -5
UKIPs |  -9 |  -26 |  -14 |  -5 |  30

_Note:_ all values in the table are rounded.

The second experiment compares our framework with a two-step approach
described as follows. We first utilize social interactions to detect
communities. Then, we aggregate the sentiment expressed among the members of
different communities in order to figure out their inter-community relations.
To have a fair comparison, we use Eq. (4) to detect communities for the two-
step approach; which is the main component in DAAC for utilizing social
interactions. As Table VII shows, the two-step approach is able to detect
correct relations in US and Australia datasets. However, it fails to detect
two out of ten inter-community relations in the UK dataset. This result shows
that our proposed framework can detect inter-community relations more
accurately by jointly using and social interactions and attitudes among users
compared to a approach which sequentially detects communities and their
relations.

TABLE VII: Inter-community detection performance between DAAC and the two-step approach. |  US |  Australia |  UK
---|---|---|---
Two-step approach |  $1.0$ |  $1.0$ |  $0.8$
DAAC |  $1.0$ |  $1.0$ |  $1.0$

$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$0$$0.2$$0.4$$0.6$$0.8$$1$Regularization
parameterPerformanceNMIARIPurity

(a) US dataset

$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$0$$0.2$$0.4$$0.6$$0.8$$1$Regularization
parameterPerformanceNMIARIPurity

(b) Australia dataset

$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$0$$0.2$$0.4$$0.6$$0.8$$1$Regularization
parameterPerformanceNMIARIPurity

(c) UK dataset

Figure 1: Community detection performance with regard to $\lambda$.

$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$0$$1$Regularization parameterCorrect
# of inter-community relations

(a) US dataset

$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$Regularization
parameterCorrect # of inter-community relations

(b) Australia dataset

$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$Regularization
parameterCorrect # of inter-community relations

(c) UK dataset

Figure 2: The correct number of inter-community relations with regard to
$\lambda$.

###  VI-C Study on the Regularization Parameter

In this section, we investigate the sensitivity of our framework with respect
to regularization parameter $\lambda$. We vary the value of $\lambda$, and
plot NMI, ARI and Purity measures in Figure 1 for all three datasets used in
the study. Similarly, we plot the correct number of inter-community relations
discovered by DAAC in Figure 2 for all three datasets with respect to
different values of $\lambda$.

As we observe from Figure 1, very large values of $\lambda$ (e.g., $10^{6}$
and $10^{7}$) for all datasets result in the highest performance of DAAC in
detecting communities. Similarly, Figure 2 shows that very large values of
$\lambda$ also result in the highest number of correct inter-community
relations discovered by DAAC. The rationale behind this is that inter-
community relations cannot be correctly identified unless communities are
accurately detected.

##  VII Conclusion and Future Work

In this paper, we proposed a framework to discover communities and their
relations by exploiting social interactions and user-generated content. We
validated the hypothesis that inter-community attitudes that users express
towards each other in social media can reflect inter-community relations. As
inspired by this hypothesis, our proposed framework DAAC jointly models users’
attitudes and social interactions in order to uncover communities and their
antagonistic/allied relations. Experimental results on three real-world social
media datasets demonstrated that our framework obtains significant performance
in detecting communities compared with several baselines and also detects
inter-community relations correctly. Moreover, we showed that a two-step
approach, which sequentially detect communities and their relations, can fail
to detect correct inter-community relations.

Since communities and their relations evolve over time, studying such dynamics
provides deeper insights into understanding communities. In our future work,
we aim to study uncovering the dynamics of communities and their relations and
the motives behind these dynamics.

##  Appendix A Appendix

Optimizing the objective function $\bm{\mathcal{F}}$ in Eq. (5) with respect
to $U$ is equivalent to solving

$\displaystyle\underset{\mathbf{U}}{\text{min}}$
$\displaystyle\bm{\mathcal{F}}_{\mathbf{U}}=||\mathbf{S}-\mathbf{U}\mathbf{H}\mathbf{U}^{T}||_{F}^{2}-\lambda
Tr(\mathbf{U}^{T}\overset{\sim}{\mathbf{R}}\mathbf{U})$ (15) s.t.
$\displaystyle\mathbf{U}\geq 0,\mathbf{U}^{T}\mathbf{U}=\mathbf{I}.$

Let $\mathbf{\Gamma}$ and $\mathbf{\Lambda}$ be the Lagrange multiplier for
constraints $\mathbf{U}^{T}\mathbf{U}=\mathbf{I}$ and $\mathbf{U}\geq 0$,
respectively, and the Lagrange function is defined as follows:

$\displaystyle\underset{\mathbf{U}}{\text{min}}$
$\displaystyle\bm{\mathcal{L}}_{\mathbf{U}}=||\mathbf{S}-\mathbf{U}\mathbf{H}\mathbf{U}^{T}||_{F}^{2}-\lambda
Tr(\mathbf{U}^{T}\overset{\sim}{\mathbf{R}}\mathbf{U})$ (16)
$\displaystyle\quad-
Tr(\mathbf{\Lambda}\mathbf{U}^{T})+Tr(\mathbf{\Gamma}(\mathbf{U}^{T}\mathbf{U}-\mathbf{I}))$

The derivative of $\bm{\mathcal{L}}_{\mathbf{U}}$ with respect to $\mathbf{U}$
is

$\displaystyle\frac{\partial\bm{\mathcal{L}}_{\mathbf{U}}}{\partial\mathbf{U}}=-2(\mathbf{W}\odot\mathbf{W}\odot\mathbf{S})\mathbf{U}\mathbf{H}^{T}-2(\mathbf{W}\odot\mathbf{W}\odot\mathbf{S})^{T}\mathbf{U}\mathbf{H}$
(17)
$\displaystyle\quad+2(\mathbf{W}\odot\mathbf{W}\odot\mathbf{U}\mathbf{H}\mathbf{U}^{T})\mathbf{U}\mathbf{H}^{T}$
$\displaystyle\quad+2(\mathbf{W}\odot\mathbf{W}\odot\mathbf{U}\mathbf{H}\mathbf{U}^{T})^{T}\mathbf{U}\mathbf{H}$
$\displaystyle\quad-2\lambda\overset{\sim}{\mathbf{R}}\mathbf{U}-\mathbf{\Lambda}+2\mathbf{U}\mathbf{\Gamma}$

For the sake of simplicity, let us assume that,

$\displaystyle\mathbf{E}_{1}=-(\mathbf{W}\odot\mathbf{W}\odot\mathbf{S})\mathbf{U}\mathbf{H}^{T}$
(18)
$\displaystyle\mathbf{E}_{2}=-(\mathbf{W}\odot\mathbf{W}\odot\mathbf{S})^{T}\mathbf{U}\mathbf{H}$
(19)
$\displaystyle\mathbf{E}_{3}=(\mathbf{W}\odot\mathbf{W}\odot\mathbf{U}\mathbf{H}\mathbf{U}^{T})\mathbf{U}\mathbf{H}^{T}$
(20)
$\displaystyle\mathbf{E}_{4}=(\mathbf{W}\odot\mathbf{W}\odot\mathbf{U}\mathbf{H}\mathbf{U}^{T})^{T}\mathbf{U}\mathbf{H}$
(21)

By setting
$\frac{\partial\bm{\mathcal{L}}_{\mathbf{U}}}{\partial\mathbf{U}}=0$, we get

$\Lambda=-2\mathbf{E}_{1}-2\mathbf{E}_{2}+2\mathbf{E}_{3}+2\mathbf{E}_{4}-2\lambda\overset{\sim}{\mathbf{R}}\mathbf{U}+2\mathbf{U}\mathbf{\Gamma}$
(22)

With the KKT complementary condition for the nonnegativity of $\mathbf{U}$, we
have

$\mathbf{\Lambda}_{ij}\mathbf{U}_{ij}=0$ (23)

Therefore, we have

$(\mathbf{E}_{1}+\mathbf{E}_{2}+\mathbf{E}_{3}+\mathbf{E}_{4}-\lambda\overset{\sim}{\mathbf{R}}\mathbf{U}+2\mathbf{U}\mathbf{\Gamma})_{ij}\mathbf{U}_{ij}=0$
(24)

where

$\mathbf{\Gamma}=-\mathbf{U}^{T}\mathbf{E}_{1}-\mathbf{U}^{T}\mathbf{E}_{2}-\mathbf{U}^{T}\mathbf{E}_{3}-\mathbf{U}^{T}\mathbf{E}_{4}+\lambda\mathbf{U}^{T}\overset{\sim}{\mathbf{R}}\mathbf{U}$
(25)

Since $\mathbf{E}_{1}$, $\mathbf{E}_{2}$, $\mathbf{E}_{3}$, $\mathbf{E}_{4}$,
and $\mathbf{\Gamma}$ can take mixed signs. Suggested by [41], we separate
positive and negative parts of any matrix $A$ as

$\displaystyle\mathbf{A}_{ij}^{+}=(|\mathbf{A}_{ij}|+\mathbf{A}_{ij})/2$ (26)
$\displaystyle\mathbf{A}_{ij}^{-}=(|\mathbf{A}_{ij}|-\mathbf{A}_{ij})/2$

Then, we get the following update rule of $\mathbf{U}$,

$\mathbf{U}=\mathbf{U}\odot\sqrt{\frac{\mathbf{E}_{1}^{+}+\mathbf{E}_{2}^{+}+\mathbf{E}_{3}^{-}+\mathbf{E}_{4}^{-}+\lambda\overset{\sim}{\mathbf{R}}\mathbf{U}+\mathbf{U}\mathbf{\Gamma}^{-}}{\mathbf{E}_{1}^{-}+\mathbf{E}_{2}^{-}+\mathbf{E}_{3}^{+}+\mathbf{E}_{4}^{+}+\mathbf{U}\mathbf{\Gamma}^{+}}}$
(27)

## Acknowledgments

This work was partially supported by ONR Grant N00014-16-1-2015 and USAF Grant
FA9550-15-1-0004.

## References

  * [1] S. Papadopoulos, Y. Kompatsiaris, A. Vakali, and P. Spyridonos, “Community detection in social media,” _Data Mining and Knowledge Discovery_ , vol. 24, no. 3, pp. 515–554, 2012.
  * [2] M. Sherif and C. W. Sherif, “Groups in harmony and tension; an integration of studies of intergroup relations.” 1953.
  * [3] M. Girvan and M. Newman, “Community structure in social and biological networks,” _Proc. Natl. Acad. Sci. USA_ , vol. 99, no. cond-mat/0112110, pp. 8271–8276, 2001.
  * [4] L. Festinger, K. W. Back, and S. Schachter, “The spatial ecology of group formation,” in _Social pressures in informal groups: A study of human factors in housing_. Stanford University Press, 1950, vol. 3, ch. 4.
  * [5] A. J. Lott and B. E. Lott, “Group cohesiveness as interpersonal attraction: a review of relationships with antecedent and consequent variables.” _Psychological bulletin_ , vol. 64, no. 4, p. 259, 1965.
  * [6] L. Chu, Z. Wang, J. Pei, J. Wang, Z. Zhao, and E. Chen, “Finding gangs in war from signed networks,” in _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. ACM, 2016, pp. 1505–1514.
  * [7] M. Gao, E.-P. Lim, D. Lo, and P. K. Prasetyo, “On detecting maximal quasi antagonistic communities in signed graphs,” _Data Mining and Knowledge Discovery_ , vol. 30, no. 1, pp. 99–146, 2016.
  * [8] D. Lo, D. Surian, P. K. Prasetyo, K. Zhang, and E.-P. Lim, “Mining direct antagonistic communities in signed social networks,” _Information Processing & Management_, vol. 49, no. 4, pp. 773–791, 2013.
  * [9] D. Lo, D. Surian, K. Zhang, and E.-P. Lim, “Mining direct antagonistic communities in explicit trust networks,” in _Proceedings of the 20th ACM international conference on Information and knowledge management_. ACM, 2011, pp. 1013–1018.
  * [10] K. Zhang, D. Lo, and E.-P. Lim, “Mining antagonistic communities from social networks,” in _Pacific-Asia Conference on Knowledge Discovery and Data Mining_. Springer, 2010, pp. 68–80.
  * [11] K. Zhang, D. Lo, E.-P. Lim, and P. K. Prasetyo, “Mining indirect antagonistic communities from social interactions,” _Knowledge and information systems_ , vol. 35, no. 3, pp. 553–583, 2013.
  * [12] H. Tajfel, “Human intergroup conflict: Useful and less useful forms of analysis,” _Human ethology: Claims and limits of a new discipline_ , pp. 369–422, 1979.
  * [13] M. Billig and H. Tajfel, “Social categorization and similarity in intergroup behaviour,” _European Journal of Social Psychology_ , vol. 3, no. 1, pp. 27–52, 1973.
  * [14] H. Tajfel, _Social identity and intergroup relations_. Cambridge University Press, 2010.
  * [15] M. E. Newman and M. Girvan, “Finding and evaluating community structure in networks,” _Physical review E_ , vol. 69, no. 2, p. 026113, 2004.
  * [16] A. Clauset, M. E. Newman, and C. Moore, “Finding community structure in very large networks,” _Physical review E_ , vol. 70, no. 6, p. 066111, 2004.
  * [17] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” _Journal of statistical mechanics: theory and experiment_ , vol. 2008, no. 10, p. P10008, 2008.
  * [18] I. S. Dhillon, Y. Guan, and B. Kulis, “Kernel k-means: spectral clustering and normalized cuts,” in _Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining_. ACM, 2004, pp. 551–556.
  * [19] C. H. Ding, X. He, and H. D. Simon, “On the equivalence of nonnegative matrix factorization and spectral clustering.” in _SDM_ , vol. 5. SIAM, 2005, pp. 606–610.
  * [20] M. E. Newman, “Finding community structure in networks using the eigenvectors of matrices,” _Physical review E_ , vol. 74, no. 3, p. 036104, 2006.
  * [21] A. Salehi, M. Ozer, and H. Davulcu, “Sentiment-driven community profiling and detection on social media,” in _Proceedings of the 29th ACM Conference on Hypertext and Social Media_. ACM, 2018\.
  * [22] K. Yu, S. Yu, and V. Tresp, “Soft clustering on graphs,” in _Advances in neural information processing systems_ , 2005, pp. 1553–1560.
  * [23] M. Rosvall and C. T. Bergstrom, “Maps of random walks on complex networks reveal community structure,” _Proceedings of the National Academy of Sciences_ , vol. 105, no. 4, pp. 1118–1123, 2008.
  * [24] D. Harel and Y. Koren, “On clustering using random walks,” in _FSTTCS_. Springer, 2001, pp. 18–41.
  * [25] P. Pons and M. Latapy, “Computing communities in large networks using random walks.” _J. Graph Algorithms Appl._ , vol. 10, no. 2, pp. 191–218, 2006\.
  * [26] U. N. Raghavan, R. Albert, and S. Kumara, “Near linear time algorithm to detect community structures in large-scale networks,” _Physical review E_ , vol. 76, no. 3, p. 036106, 2007.
  * [27] S. Gregory, “Finding overlapping communities in networks by label propagation,” _New Journal of Physics_ , vol. 12, no. 10, p. 103018, 2010\.
  * [28] D. Lilleker, D. Jackson, E. Thorsen, and A. Veneti, “Us election analysis 2016: Media, voters and the campaign.” 2016.
  * [29] D. Clune, “Contemporary australian political party organisations,” 2016.
  * [30] M. Moran, _Politics and Governance in the UK_. Palgrave Macmillan, 2015.
  * [31] M. Pontiki, D. Galanis, H. Papageorgiou, I. Androutsopoulos, S. Manandhar, A.-S. Mohammad, M. Al-Ayyoub, Y. Zhao, B. Qin, O. De Clercq _et al._ , “Semeval-2016 task 5: Aspect based sentiment analysis,” in _Proceedings of the 10th international workshop on semantic evaluation (SemEval-2016)_ , 2016, pp. 19–30.
  * [32] M. Conover, J. Ratkiewicz, M. R. Francisco, B. Gonçalves, F. Menczer, and A. Flammini, “Political polarization on twitter.” _ICWSM_ , vol. 133, pp. 89–96, 2011.
  * [33] M. Thelwall, K. Buckley, G. Paltoglou, D. Cai, and A. Kappas, “Sentiment strength detection in short informal text,” _Journal of the American Society for Information Science and Technology_ , vol. 61, no. 12, pp. 2544–2558, 2010.
  * [34] Z. Tufekci, “Big questions for social media big data: Representativeness, validity and other methodological pitfalls,” _arXiv preprint arXiv:1403.7400_ , 2014.
  * [35] D. Ruths and J. Pfeffer, “Social media for large studies of behavior,” _Science_ , vol. 346, no. 6213, pp. 1063–1064, 2014.
  * [36] G. Beigi, J. Tang, and H. Liu, “Signed link analysis in social media networks.” in _ICWSM_ , 2016, pp. 539–542.
  * [37] D. D. Lee and H. S. Seung, “Algorithms for non-negative matrix factorization,” in _Advances in neural information processing systems_ , 2001, pp. 556–562.
  * [38] C. Liu, H.-c. Yang, J. Fan, L.-W. He, and Y.-M. Wang, “Distributed nonnegative matrix factorization for web-scale dyadic data analysis on mapreduce,” in _Proceedings of the 19th international conference on World wide web_. ACM, 2010, pp. 681–690.
  * [39] R. Gemulla, E. Nijkamp, P. J. Haas, and Y. Sismanis, “Large-scale matrix factorization with distributed stochastic gradient descent,” in _Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining_. ACM, 2011, pp. 69–77.
  * [40] F. Li, B. Wu, L. Xu, C. Shi, and J. Shi, “A fast distributed stochastic gradient descent algorithm for matrix factorization,” in _Proceedings of the 3rd International Conference on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications-Volume 36_. JMLR. org, 2014, pp. 77–87.
  * [41] C. H. Ding, T. Li, and M. I. Jordan, “Convex and semi-nonnegative matrix factorizations,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 32, no. 1, pp. 45–55, 2010.


# Ensemble Learning Priors Driven Deep Unfolding for
Scalable Snapshot Compressive Imaging

Chengshuai Yang
Westlake University
<EMAIL_ADDRESS>Shiyu Zhang
Westlake University
<EMAIL_ADDRESS>Xin Yuan
Westlake University
<EMAIL_ADDRESS>
###### Abstract

Snapshot compressive imaging (SCI) can record the 3D information by a 2D
measurement and from this 2D measurement to reconstruct the original 3D
information by reconstruction algorithm. As we can see, the reconstruction
algorithm plays a vital role in SCI. Recently, deep learning algorithm show
its outstanding ability, outperforming the traditional algorithm. Therefore,
to improve deep learning algorithm reconstruction accuracy is an inevitable
topic for SCI. Besides, deep learning algorithms are usually limited by
scalability, and a well trained model in general can not be applied to new
systems if lacking the new training process. To address these problems, we
develop the ensemble learning priors to further improve the reconstruction
accuracy and propose the scalable learning to empower deep learning the
scalability just like the traditional algorithm. What’s more, our algorithm
has achieved the state-of-the-art results, outperforming existing algorithms.
Extensive results on both simulation and real datasets demonstrate the
superiority of our proposed algorithm. The code and models will be released to
the public.
https://github.com/integritynoble/ELP-Unfolding/tree/master

##  1 Introduction

Recently, video snapshot compressive imaging (SCI) [22, 46] has attracted much
attention because it can improve the imaging speed by capturing three-
dimensional (3D) information from one 2D measurement. When video SCI works,
multiple frames are first modulated by different masks, and these modulated
frames are mapped into a single measurement. After this, the reconstruction
algorithm recovers these multiple frames from the single measurement [43]. At
present, the mask can easily be adjusted with a higher speed than the capture
rate of the camera [14, 29, 31]. Thus, SCI enjoys the advantages of high
speed, low memory, low bandwidth, low power and potentially low cost [44].

Figure 1: Trade-off between quality and testing-time of various algorithms for
SCI reconstruction. Our proposed Ensemble Learning Priors (ELP) unfolding
achieves the state-of-the-art results in a short testing time. Besides, after
scalable learning, our ELP-Unfolding can be used in different masks and
different compression ratios and thus can be applied to various scenes by a
single trained model, similar to traditional optimization-based algorithms,
such as GAP-TV [42].

How to recover the original multiple frames from the single measurement always
plays a vital role in SCI. Recently, deep learning reconstruction methods have
outperformed the traditional iterative reconstruction method not only in
reconstruction accuracy but also in testing time [17, 25, 33, 39, 40]. But
most deep learning methods lack interpretability. To increase
interpretability, deep unfolding method has been developed, which simulates
the traditional iteration algorithm [39, 40, 47, 23, 35]. Deep unfolding
method adopts iterative framework but replaces traditional denoiser (such as
total variation [3, 19] and nonlocal self-similarity [8, 21]) with the
training neural network denoiser. So far, the deep unfolding method has
achieved the best result for SCI. Among deep unfolding algorithms, GAP-net
[23] can use the shortest time (0.0072 s) to achieve 32 dB for PSNR for
benchmark dataset [21]. Dense3D-Unfolding [37] achieved best result (35 dB),
though it costs a long time (1.35 s) because of using complex 3D convolutional
neural networks (CNNs). Thus, the speed and accuracy have not coexisted in one
algorithm yet. What’s worse, most of these deep learning algorithms are
limited by the scalability. To apply the trained model to new systems, the
model usually should be trained again. Although MetaSCI [36] can quickly be
applied to new SCI modulations in spatial but not in temporal size, it still
needs the adaptation (retraining) process.

Bearing the above concerns in mind, in order to achieve a higher
reconstruction accuracy meanwhile with a high computing speed, we develop the
Ensemble Learning Priors (ELP) unfolding based on 2D-CNN for SCI.
Specifically, 2D-CNN can retain the fast processing and ensemble learning can
increase reconstruction accuracy. Ensemble learning has a strong power to
achieve the reconstruction accuracy and has also achieved the state-of-the-art
(SOTA) results in a number of models for other tasks [49, 50, 27], due to the
fact that several models have complementary advantages over a single model.
Fortunately, the deep unfolding algorithm often contain many neural network
priors, even though these priors stay in different iteration stages. Hereby,
in this paper, we first propose to gather multiple neural network priors in
one stage to realize ensemble learning for SCI without increasing training
models. To further increase the reconstruction accuracy, the dense connection
is added in the training models, which can help latter models learn some
useful information from previous models. Thus our ELP-unfolding can achieve
the SOTA result, better than Dense3D-Unfolding [37], and in a short running
time.

Furthermore, to realize the scalability, we develop the scalable learning for
SCI. Our method not only has scalability in the spatial dimensions but also in
the temporal dimension. Considering spatial scalability, we set our ELP-
unfolding without multilayer perception (MLP) structure. For dimensional
scalability, the input of neural network priors are set to have the same
channels even for different temporal dimensional scenes. Based on this, our
scalable learning method can have the same capability as the traditional
iteration algorithms, to be applied to different systems. Our specific
contributions are listed as follows:

  * •

We develop the ensemble learning prior unfolding for SCI. ELP unfolding is a
general method for inverse algorithms, which can also be applied to other
field, such as single pixel camera [13, 30, 12], MRI [2, 20] and tomography
imaging [41, 7].

  * •

We first propose the scalable learning for SCI, which can be used in the same
way as the plug-and-play (PnP) algorithm [44]. For new systems with different
modulations or different compression ratios, the trained model can still be
applicable. Besides, scalable learning can achieve better results than PnP
algorithm with a fast inference speed.

  * •

We adopt the connection techniques in unfolding. In our ELP-unfolding, the
connection technique just uses the adding and concatenating operation, which
is simple. By contrast, the Dense3D-Unfolding [37] adopts a complex method
such as DFMA (dense feature map adaption) to realize connection.

  * •

Our method achieves the SOTA results for SCI in benchmark dataset based on
2D-CNN, outperforming the 3D-CNN method at a faster inference speed [37] as
shown in Fig. 1.

In a nutshell, our ensemble learning priors unfolding has two periods. In the
first period, that is single prior period, every stage contains one neural
network prior. Afterwards, in the second (ensemble priors) period, every stage
contains all the previous stage priors in the ensemble manner.

Figure 2: Principle of Video SCI (left) and our ELP-unfolding (right). Left:
the high speed dynamic scene at timestamps $t_{1}$ to $t_{B}$, are encoded by
the high-speed variant masks (dynamic coded apertures) and then integrated to
a single coded measurement (a compressed image) ${{\bf Y}}$. Right: our whole
ELP-unfolding reconstructs the original dynamic scene from the masks $\\{{\bf
C}_{1},\dots,{\bf C}_{B}\\}$ and the compressed image ${{\bf Y}}$, which
includes the single prior period in Fig. 3 and ensemble priors period in Fig.
4.

##  2 Related Work

SCI is related to compressive sensing (CS) [15], where the reconstruction is
significantly important as it provides the desired signals (such as images)
from the compressed measurements. For CS [15, 17, 25, 33, 23], there are two
kinds of reconstruction methods: traditional iterative method and deep
learning method. The traditional iteration method contains a lot of iterations
and each iteration contains the projection operation and denoising operation
(and optionally some other steps). The denoising operation generally
determines the performance of one algorithm. For example, total variation [3,
19] denoiser has a fast speed but usually can only provide blurry images while
the nonlocal self-similarity based denoiser [8, 21] can achieve a clearer
image but takes a long time. Recently, deep learning has shown its strong
power in reconstructing images [17, 25, 33, 39, 40]. At first, deep learning
was regarded as a black box and the trained model can get the better images
than traditional iterative method at a fast speed. As a black box to train,
the trained model would contain the measurement matrix (masks) information.
Thus, the training model usually can not be applied to new masks (such as a
new hardware system). To address this problem, the deep unfolding method for
CS has be developed. Deep unfolding method simulates traditional iterative
method and uses a lot of iterations (stages), each of which has projection
operation and denoising operation. Different from traditional methods, deep
unfolding used the trained neural network as a denoising prior. Therefore,
deep learning mainly contributes to denoising in deep unfolding method and has
little dependence on the mask information. The mask information is mainly
processed by the projection operation. Thus, deep unfolding algorithms has a
strong robustness to a variety of masks [47, 23]. Besides, Dense3D-Unfolding
[37] obtained SOTA for SCI by combining deep unfolding method and 3D-CNN, but
at the cost of a slow computing speed. Though the unfolding method can solve
the scalability problem in a variety of masks, the scalability problem in a
variety of sizes (both spatial size and temporal size, a.k.a., the compression
ratio) still remains in unfolding method. Deep unfolding method still does not
have the same scalability as the traditional iterative method.

To address these challenges, we develop the ensemble learning priors unfolding
for scalable SCI. We use the ensemble learning and 2D-CNN to realize the high
reconstruction accuracy and speed and develop the scalable learning to realize
scalability.

##  3 Preliminary: Video SCI System

As depicted in Fig. 2, let $\\{{\bf X}_{1},\dots,{\bf X}_{B}\\}$ denote the
discretized video frames at timestamps $\\{t_{1},\dots,t_{B}\\}$. These video
frames are modulated by dynamic coded aperture, a.k.a., the masks $\\{{\bf
C}_{1},\dots,{\bf C}_{B}\\}$, respectively. The modulated frames are then
integrated into a single coded measurement (a compressed image) ${{\bf Y}}$.
Here, $\\{{\bf X}_{b}\\}_{b=1}^{B}\in{\mathbb{R}}^{n_{x}\times n_{y}\times
B}$, $\\{{\bf C}_{b}\\}_{b=1}^{B}\in{\mathbb{R}}^{n_{x}\times n_{y}\times B}$
and ${{\bf Y}}\in{\mathbb{R}}^{n_{x}\times n_{y}}$. This forward model can be
written as

$\textstyle{{\bf Y}}=\sum_{b=1}^{B}{\bf C}_{b}\odot{\bf X}_{b}+{\bf Z},$ (1)

where $\odot$ and ${\bf Z}\in{\mathbb{R}}^{n_{x}\times n_{y}}$ denote the
matrix element-wise product and noise, respectively. Eq. (1) is equivalent to
the following linear form

$\bm{y}={{\bf H}}\bm{x}+\bm{z},$ (2)

where $\bm{y}={\rm Vec}({{\bf Y}})\in{\mathbb{R}}^{n_{x}n_{y}}$,$\bm{z}={\rm
Vec}({\bf Z})\in{\mathbb{R}}^{n_{x}n_{y}}$ and $\bm{x}={\rm Vec}({\bf
X})=[{\rm Vec}({\bf X}_{1})^{\top},\dots,{\rm Vec}({\bf
X}_{B})^{\top}]^{\top}\in{\mathbb{R}}^{n_{x}n_{y}B}$. Different from
traditional compressive sensing [9, 11, 10], the sensing matrix ${{\bf H}}$ in
(2) has a very special structure and can be written as

${{\bf H}}=[{\bf D}_{1},\dots,{\bf D}_{B}],$ (3)

where $\\{{\bf D}_{b}=diag({\rm Vec}({\bf
C}_{b}))\in{\mathbb{R}}^{n_{x}n_{y}\times n_{x}n_{y}}\\}_{b=1}^{B}$are
diagonal matrices of masks. Therefore, the compressive sampling rate in SCI is
equal to $1/B$. The reconstruction error of SCI is bounded even when $B>1$
[15].

Figure 3: Principle of the single prior period.

##  4 Our proposed methods

###  4.1 Ensemble learning priors unfolding for SCI

Given the compressed measurement ${{\bf Y}}$ and coding pattern $\\{{\bf
C}_{b}\\}_{b=1}^{B}$ captured by the SCI system, there exist two optimization
frameworks to predict the desired high speed frames $\\{{\bf
X}_{b}\\}_{b=1}^{B}$: penalty function method and augmented Lagrangian (AL)
method. The performance of the AL method is better than that of the penalty
function method, which has been proved in previous works [18, 1, 38], and
therefore, the AL method is adopted here, which is formulated as follows:

$\bm{x}=\textstyle\arg\\!\min_{\bm{x}}\Phi(\bm{x})-{\bm{\lambda}}_{1}(\bm{y}-{{\bf
H}}\bm{x})+\textstyle\frac{\gamma_{1}}{2}\left\|\bm{y}-{{\bf
H}}\bm{x}\right\|_{2}^{2},$ (4)

where $\Phi(\bm{x}),{\bm{\lambda}}_{1}$ and $\gamma_{1}$ denote the prior
regularization, Lagrangian multiplier and penalty parameter, respectively. For
convenience, Eq. (4) is further written as

$\displaystyle\bm{x}=\textstyle\arg\\!\min_{\bm{x}}\Phi(\bm{x})+\frac{\gamma_{1}}{2}\left\|\bm{y}-{{\bf
H}}\bm{x}-\frac{{\bm{\lambda}}_{1}}{\gamma_{1}}\right\|_{2}^{2}.$ (5)

####  4.1.1 Single prior

To solve Eq. (5), an auxiliary variable $\bm{v}$ is introduced. Then Eq. (5)
is further written as

$\displaystyle\bm{x}=\textstyle\arg\\!\min_{\bm{x}}\Phi(\bm{v})+\frac{\gamma_{1}}{2}\left\|\bm{y}-{{\bf
H}}\bm{x}-\frac{{\bm{\lambda}}_{1}}{\gamma_{1}}\right\|_{2}^{2}$
$\displaystyle~{}\text{subject to}~{}~{}\bm{v}=\bm{x}.$ (6)

By adopting alternating direction method of multipliers (ADMM) method [4], Eq.
(6) is further written as

$\displaystyle\bm{x},\bm{v}=\textstyle\arg\\!\min_{\bm{x},\bm{v}}\Phi(\bm{v})+\frac{\gamma_{2}}{2}\left\|\bm{x}-\bm{v}-\frac{{\bm{\lambda}}_{2}}{\gamma_{2}}\right\|_{2}^{2}$
$\displaystyle+\textstyle\frac{\gamma_{1}}{2}\left\|\bm{y}-{{\bf
H}}\bm{x}-\frac{{\bm{\lambda}}_{1}}{\gamma_{1}}\right\|_{2}^{2}.$ (7)

According to ADMM, Eq. (7) can be divided into the two subproblems and solved
iteratively

$\displaystyle\bm{v}^{i}$
$\displaystyle=\textstyle\arg\\!\min_{\bm{v}}\Phi(\bm{v})+\frac{\gamma_{2}^{i}}{2}\left\|\bm{x}^{i-1}-\bm{v}-\frac{{\bm{\lambda}}_{2}^{i}}{\gamma_{2}^{i}}\right\|_{2}^{2},$
(8) $\displaystyle\bm{x}^{i}$
$\displaystyle=\textstyle\arg\\!\min_{\bm{x}}\frac{\gamma_{2}^{i}}{2}\left\|\bm{x}-\bm{v}^{i}-\frac{{\bm{\lambda}}_{2}^{i}}{\gamma_{2}^{i}}\right\|_{2}^{2}+\textstyle\frac{\gamma_{1}^{i}}{2}\left\|\bm{y}-{{\bf
H}}\bm{x}-\frac{{\bm{\lambda}}_{1}^{i}}{\gamma_{1}^{i}}\right\|_{2}^{2},$ (9)

where the superscript _i_ denotes the iteration index.

For subproblem $\bm{x}_{i}$, there exists a closed-form solution, which is
called projection operation

$\displaystyle\bm{x}^{i}=\textstyle(\gamma_{2}^{i}+{{\bf
H}}^{T}\gamma_{1}^{i}{{\bf
H}})^{-1}\left[{\bm{\lambda}}_{2}^{i}+\gamma_{2}^{i}\bm{v}^{i}+{{\bf
H}}^{T}\gamma_{1}^{i}(\bm{y}-\frac{{\bm{\lambda}}_{1}^{i}}{\gamma_{1}^{i}})\right].$
(10)

Due to the special structure of H, this can be solved in one shot [21].

For subproblem $\bm{v}_{i}$, Eq. (8) can be rewritten as

$\displaystyle\bm{v}^{i}=\textstyle\arg\\!\min_{\bm{v}}\Phi(\bm{v})+\frac{\gamma_{2}^{i}}{2}\left\|{\bm{u}}^{i-1}-\bm{v}\right\|_{2}^{2}\
,$ (11)

where
${\bm{u}}^{i-1}=\bm{x}^{i-1}-\frac{{\bm{\lambda}}_{2}^{i-1}}{\gamma_{2}^{i}}$.
Eq. (11) is a classical denoising problem, which can be solved by denoising
prior such as TV, wavelet transformation, denoising network, _etc_. In this
paper, denoising network prior is adopted as shown in Fig. 5.

####  4.1.2 Ensemble priors

Figure 4: Principle of the ensemble priors period.

In every stage of unfolding, the denoising prior has different parameters and
thus plays different roles in removing noise, even if these priors have the
same structure. To take full use of different denoisers among different
stages, these priors after ${\bm{m}}$ stages are gathered together to perform
projection operation to produce $\bm{x}$. Therefore, Eq. (8) and Eq. (9) in
ensemble priors period becomes

$\displaystyle\bm{v}^{m+j}=\textstyle\arg\\!\min_{\bm{v}}\Phi(\bm{v}_{1})+\frac{\gamma_{2}^{m+j}}{2}\left\|\bm{x}^{m+j-1}-\bm{v}-\frac{{\bm{\lambda}}_{2}^{m+j-1}}{\gamma_{2}^{m+j}}\right\|_{2}^{2},$
(12)

and

$\displaystyle\bm{x}^{m+j}$
$\displaystyle=\textstyle\arg\\!\min_{\bm{x}}\frac{\gamma_{2}^{m}}{2}\left\|\bm{x}-\bm{v}^{m}-\frac{{\bm{\lambda}}_{2}^{m}}{\gamma_{2}^{m}}\right\|_{2}^{2}$
$\displaystyle+\textstyle\frac{\gamma_{2}^{m+1}}{2}\left\|\bm{x}-\bm{v}^{m+1}-\frac{{\bm{\lambda}}_{2}^{m+1}}{\gamma_{2}^{m+1}}\right\|_{2}^{2}+\cdots$
$\displaystyle+\textstyle\frac{\gamma_{1}^{m+j}}{2}\left\|\bm{y}-{{\bf
H}}\bm{x}-\frac{{\bm{\lambda}}_{1}^{m+j}}{\gamma_{1}^{m+j}}\right\|_{2}^{2}.$
(13)

For subproblem $\bm{v}_{i}$, Eq. (12) can still adopt the same denoising prior
form as in single-prior period. For subproblem $\bm{x}_{i}$, there is slightly
difference because of ensemble

$\displaystyle\bm{x}^{m+j}=(\gamma_{2}^{m}+\gamma_{2}^{m+1}+\cdots+\gamma_{2}^{m+j}+{{\bf
H}}^{T}\gamma_{1}^{m+j}{{\bf H}})^{-1}$
$\displaystyle[{\bm{\lambda}}_{2}^{m}+\gamma_{2}^{m}\bm{v}^{m}+{\bm{\lambda}}_{2}^{m+1}+\gamma_{2}^{m+1}\bm{v}^{m+1}+\cdots$
$\displaystyle+\textstyle{\bm{\lambda}}_{2}^{m+j}+\gamma_{2}^{m+j}\bm{v}^{m+j}+{{\bf
H}}^{T}\gamma_{1}^{m+j}(\bm{y}-\frac{{\bm{\lambda}}_{1}^{m+j}}{\gamma_{1}^{m+j}})].$
(14)

Last but not least, the Lagrangian multipliers ${\bm{\lambda}}_{1}^{i}$ and
${\bm{\lambda}}_{2}^{i}$ are updated by

$\displaystyle{\bm{\lambda}}_{1}^{i}$
$\displaystyle={\bm{\lambda}}_{1}^{i-1}-\gamma_{1}^{i}(\bm{y}-{{\bf
H}}\bm{x}^{i-1}),$ (15) $\displaystyle{\bm{\lambda}}_{2}^{i}$
$\displaystyle={\bm{\lambda}}_{2}^{i-1}-\gamma_{2}^{i}(\bm{x}-\bm{v}^{i-1}).$
(16)

Besides, the $\gamma_{1}^{i}$ and $\gamma_{2}^{i}$ are trained with the
denoising prior parameters in every stage.

####  4.1.3 Denoising prior structure

As shown in Fig. 5, U-net [32] is used as the backbone for denoising prior,
which we adopt from FastDVDnet [34], but here we remove the batch
normalization and quadruple the depth; this means that the channels for three
different features are 128, 256 and 512, respectively. Thus, the training
parameters of our proposed ELP-unfolding mainly consists of these 13 U-net
structures. More details can be found in the supplementary materials (SM).
Following [34, 48], the penalty parameter $\gamma_{2}^{i}$ is expanded into a
noise map as a part of the input. To help denoise, the normalized measurement
$\overline{{{\bf Y}}}$ is also added into the input [36, 5, 37], which is
defined as

$\displaystyle\overline{{{\bf Y}}}=\textstyle{{\bf
Y}}\oslash\sum_{b=1}^{B}{\bf C}_{b},$ (17)

where $\oslash$ represents the matrix element-wise division. Therefore, the
input consists of noise map $\gamma_{2}^{i}$, normalized measurement
$\overline{{{\bf Y}}}$ and
$\bm{x}^{i-1}-\frac{{\bm{\lambda}}_{2}^{i-1}}{\gamma_{2}^{i}}$, and the output
is $\bm{v}^{i}$. Besides, the the dense connection is employed in the
denoising prior network design.

Figure 5: Denoising prior structure based on U-net [32]. Algorithm 1 ELP-
unfolding for SCI Reconstruction

0: ${{\bf H}}$, $\bm{y}$, $\overline{{{\bf
Y}}}$,$\\{\gamma_{1}^{0},\dots,\gamma_{1}^{m+n}\\}$,$\\{\gamma_{2}^{0},\dots,\gamma_{2}^{m+n}\\}$.

1: Initial $\bm{v}^{0}$ = $\mathbf{0}$, ${\bm{\lambda}}_{1}^{0}$ =
$\mathbf{0}$, ${\bm{\lambda}}_{2}^{0}$ = $\mathbf{0}$.

2: Update $\bm{x}^{0}$ by Eq. (10)

3:  _% single prior period_

4: for $\mathbf{i}$ = 1, … , m do

5: Update $\bm{v}^{i}$ by Eq. (11), ${\bm{\lambda}}_{2}^{i}$ by Eq. (16).

6: Update ${\bm{\lambda}}_{1}^{i}$ by Eq. (15), $\bm{x}^{i}$ by Eq. (10).

7: end for

8:  _% ensemble priors period_

9: for $\mathbf{k}$ = m+1, … , m+n do

10: Update $\bm{v}^{k}$ by Eq. (11), ${\bm{\lambda}}_{2}^{k}$ by Eq. (16).

11: Update ${\bm{\lambda}}_{1}^{k}$ by Eq. (15), $\bm{x}^{k}$ by Eq. (14).

12: end for

####  4.1.4 Dense connection for unfolding

In traditional unfolding method, the connection between two stages are
$\bm{v}$ and ${\bm{u}}$, that is
$\bm{x}^{i-1}-\frac{{\bm{\lambda}}_{2}^{i-1}}{\gamma_{2}^{i}}$, which have a
small number of temporal dimensions. Therefore, most latent information in
U-net structure can not transmit between different priors. To break this
bottleneck, the skip connection technique is used here. As shown in Fig. 5, in
the ${\bm{i}}^{th}$ prior, the feature ${{\bf E}}^{i}_{j}$ and feature ${{\bf
E}}^{i-1}_{sumj}$ concatenate into one new feature, which will be as one whole
feature operated in latent space in U-net structure. Besides, the feature
${{\bf E}}^{i}_{j}$ will add to ${{\bf E}}^{i-1}_{sumj}$ to form ${{\bf
E}}^{i}_{sumj}$, that is, ${{\bf E}}^{i}_{sumj}={{\bf E}}^{i-1}_{sumj}+{{\bf
E}}^{i}_{j}$.

By re-ordering the updating equations, we summarize the entire algorithm in
Algorithm 1.

###  4.2 Scalable learning for SCI

The traditional deep learning methods usually do not have scalability. One
trained model can only be applied to one system with specific masks and
compression ratios $B$. When the scene data size changes, the new
corresponding model usually needs to be trained again. The most recent MetaSCI
[36] can quickly be applied to a new model but also demands new adaptation
process. In addition, MetaSCI adaptation is limited in space but not suitable
for time. Even some deep learning method, which is independent of multi-layer
perception, such as Dense3D-Unfolding [5], can be applied to different spatial
size case, but they have no temporal scalability. They must be trained again
for new applications with different temporal dimensions _i.e_., $B$.

To address this problem, we develop the scalable learning for SCI. This
scalable learning has scalability not only in the spatial dimension but also
in temporal dimension. Specifically, to ensure spatial scalability, we only
employ the convolutional neural network; to ensure temporal scalability, we
first compute the maximum frames (temporal dimension) this model should have.
For example, one model has ${B}$ frames. The input of the denoising prior
should have ${B+2}$ frames, as shown in Fig. 5. If the dynamic scene
coincidentally has ${B}$ frames, the input can directly use original data.
Otherwise, the original data should be rearranged several times to satisfy the
frames number. When ${B}$ is not an integer multiple of the frame number of
dynamic scene, only the first several frames of original data are used in the
last arranging process. In the training process, the model randomly chooses
different frames.

Even though the maximum temporal size needs to be set in front, the new
maximum temporal model can conveniently use the previous different maximum
temporal models as the pre-trained model to speed up the training process.

###  4.3 Training

Given the measurement ${{\bf Y}}$ and masks $\\{{\bf C}_{b}\\}_{b=1}^{B}$, our
ELP-unfolding can generate $\\{\hat{{\bf
X}}_{b}\\}_{b=1}^{B}\in{\mathbb{R}}^{n_{x}\times n_{y}\times B}$. The mean
square error (MSE) is selected as our loss function, expressed as

$\displaystyle\ell_{MSE}=\textstyle\frac{1}{SBn_{x}n_{y}}\sum_{s=1}^{S}\sum_{b=1}^{B}\left\|{\bf
X}_{b}-\hat{{\bf X}}_{b}\right\|_{2}^{2},$ (18)

where ${\bf X}_{b}$ is ground truth and $S$ is batchsize.

Table 1: Benchmark dataset: the average results of PSNR in dB (left entry in
each cell) and SSIM (right entry in each cell) and run time per measurement in
seconds by different algorithms on the 6 benchmark datasets.

Algorithm | Kobe | Traffic | Runner | Drop | Crash | Aerial | Average | Run time (s)
---|---|---|---|---|---|---|---|---
GAP-TV [42] | 26.92, 0.838 | 20.66, 0.691 | 29.81, 0.895 | 34.95, 0.966 | 24.48, 0.799 | 24.81, 0.811 | 26.94, 0.833 | 4.2 (CPU)
DeSCI [21] | 33.25, 0.952 | 28.71, 0.925 | 38.48, 0.969 | 43.10, 0.992 | 27.04, 0.909 | 25.33, 0.860 | 32.65, 0.934 | 6180 (CPU)
PnP-FFDNet [44] | 30.33, 0.925 | 24.01, 0.835 | 32.44, 0.931 | 39.68, 0.986 | 24.67, 0.833 | 24.29, 0.820 | 29.21, 0.888 | 3.0 (GPU)
PnP-FastDVDnet [45] | 32.73, 0.947 | 27.95, 0.932 | 36.29, 0.962 | 41.82, 0.989 | 27.32, 0.925 | 27.98, 0.897 | 32.35, 0.942 | 6 (GPU)
BIRNAT [6] | 32.71, 0.950 | 29.33, 0.942 | 38.70, 0.976 | 42.28, 0.992 | 27.84, 0.927 | 28.99, 0.927 | 33.31, 0.951 | 0.16 (GPU)
GAP-Unet-S12 [23] | 32.09, 0.944 | 28.19, 0.929 | 38.12, 0.975 | 42.02, 0.992 | 27.83, 0.931 | 28.88, 0.914 | 32.86, 0.947 | 0.0072 (GPU)
Meta-SCI [36] | 30.12, 0.907 | 26.95, 0.888 | 37.02, 0.967 | 40.61, 0.985 | 27.33, 0.906 | 28.31, 0.904 | 31.72, 0.926 | 0.025 (GPU)
RevSCI [5] | 33.72, 0.957 | 30.02, 0.949 | 39.40, 0.977 | 42.93, 0.992 | 28.12, 0.937 | 29.35, 0.924 | 33.92, 0.956 | 0.19 (GPU)
Dense3D-Unfolding [37] |  35.00, 0.969 |  31.76, 0.966 | 40.03, 0.980 | 44.96, 0.995 | 29.33, 0.956 | 30.46, 0.943 | 35.26, 0.968 | 1.35 (GPU)
ELP-Unfolding (Ours) | 34.41, 0.966 | 31.58, 0.962 |  41.16, 0.986 |  44.99, 0.995 |  29.65, 0.960 |  30.68, 0.943 |  35.41, 0.969 | 0.24 (GPU)

Figure 6: Selected reconstruction results of benchmark dataset by GAP-TV [42],
DeSCI [21], PnP-FFDNet [44], RevSCI [5] and the proposed ELP-unfolding (Please
zoom-in to see details.).

We use PyTorch [26] to train our model on one NVIDIA A40 GPU. For all training
processes, we adopt the same Adam optimizer [16] with a mini-batch size of 3
and a spatial size of 256 ${\times}$ 256\. We also adopt the pre-training
strategy. The whole training process has two periods. Firstly, 8 stages with a
single prior model is trained to be used as the pretrained parameters.
Secondly, the whole ELP-unfolding with the pretrained parameters, is then
trained, with 13 stages, 6 ensemble-priors in the last stage. And the first 8
stages just contains a single prior. Besides, the former 8 stages in whole
ELP-unfolding match the pretrained model very well and completely adopt the
pretrained parameters. The latter 5 stages priors adopt the same last stage
parameters in the pretrained model.

Regarding the learning rate, we adopt the same strategy for these two training
periods. The difference lies in the initial learning rate. For the first
(pretrained) period, the initial learning rate is set to
$\text{1}{\times}10^{-4}$. For the second (ELP-unfolding) period, the initial
learning rate is set to be $\text{2}{\times}10^{-5}$. After the first five
epochs, the learning rate decays with a factor of 0.9 every fifteen epochs.
Besides, The number of total epochs for the first (pretrained) period is 200
while for the second (ELP-unfolding) period is 320.

##  5 Experiment

###  5.1 Training Dataset

We used DAVIS2017 [28] dataset with resolution 480${\times}$894 (480p) as our
training dataset for all experiments. Video clips with spatial size of 256
${\times}$ 256 are randomly cropped from this training dataset.

###  5.2 Benchmark datasets for SCI

The Kobe, Traffic, Runner, Drop, Crash, and Aerial are the Benchmark datasets
for SCI[21, 45, 44, 6, 37, 5], where the data-size is
256${\times}$256${\times}$8, _i.e_. $n_{x}$=$n_{y}$=256, $B$=8. Based on these
datasets, our ELP-unfolding with a special temporal size of 8 is been compared
with other SOTA algorithms, including GAP-TV [42], DeSCI [21], PnP-FFDNet
[44], PnP-FastDVDnet [45], BIRNAT [6], GAP-Unet-S12 [23], Meta-SCI [36],
RevSCI [5], Dense3D-Unfolding [37]. The results are summarized in Table 1. As
we can see, iterative algorithms including PnP based algorithms (GAP-TV,
DeSCI, PnP-FFDNet, PnP-FastDVDnet) provide inferior results at a slow speed
(more than one second). Deep learning algorithms can achieve the better result
in a short running time (usually less than 1 second). Although
Dense3D-Unfolding had achieved the best results before, it costs a long time
to test (1.35 s). Our ELP-unfolding algorithm not only achieves better result
than Dense3D-Unfolding, but also saves the testing time (costing 0.24 s). For
visualization purpose, we also present some images in Fig. 6, where we can see
from the zooming areas that our ELP-unfolding provides much clearer images
with sharper edges and more abundant details than other algorithms. We also
believe that by adopting 3D-CCN, ELP-unfolding can achieve even better
results.

###  5.3 Scalable datasets for SCI

Figure 7: Scalability: Selected reconstruction results by GAP-TV, PnP-FFDNet,
PnP-FastDVDnet and the proposed ELP-unfolding with various spatial sizes and
compression ratios. Figure 8: Scalability comparison based on PSNR and SSIM
obtained by various algorithms for different spatial and temporal (compression
ratio) sizes.

To verify the scalability of our ELP-unfolding method, we test four different
size datasets: 256${\times}$256${\times}$24, 512${\times}$512 ${\times}$10,
1024 ${\times}$1024${\times}$18 and 1536${\times}$1536${\times}$12\. The
latter three datasets are cropped from the Ultra Video Group (UVG) dataset
[24] in the same way as in Meta-SCI [36]. The former one dataset is also the
benchmark but the compression ratio $B$ is now set to 24. Because the previous
deep learning algorithms (including Meta-SCI) cannot scale for different
compression ratios, the traditional iteration algorithms including GAP-TV,
PnP-FFDNet and PnP-FastDVDnet are chosen as the baselines. It can be noticed
from Fig. 8 that these algorithms achieve worse results than ELP-unfolding
meanwhile cost a longer time. In the 1536${\times}$1536${\times}$12 case, PnP-
FFDNet is able to get good results as the ELP-unfolding. However, it is
unstable and gets the worst results in 256${\times}$256${\times}$24 case. Fig.
7 shows some selected images with much sharper boundaries and fewer artifacts
reconstructed by ELP-unfolding than other algorithms. Please refer to the
reconstructed videos in the SM.

Table 2: Ablation Study: Average PSNR and SSIM For different stages and
ensemble priors (in the last stage) on the benchmark dataset.

1 stage | 3 stages | 5 stages | 7 stages | 8 stages | 9 stages | 11 stages | 13 stages | 1 prior | 2 priors | 4 priors | 6 priors | 8 priors
---|---|---|---|---|---|---|---|---|---|---|---|---
31.21, 0.926 | 33.29, 0.953 | 34.33, 0.964 | 34.50, 0.965 | 34.83, 0.966 | 34.92, 0.967 | 35.11, 0.968 | 35.07, 0.968 | 34.83, 0.966 | 34.98, 0.967 | 35.15, 0.968 | 35.41, 0.969 | 35.34, 0.969

Table 3: Ablation Study: Average PSNR and SSIM for running 13 stages in
different situations on benchmark datasets.

Ensemble all | Ensemble no | Part training-set | Removing connection | Integrating all
---|---|---|---|---
34.97, 0.967 | 35.09, 0.968 | 34.73, 0.966 | 34.77, 0.966 | 35.41, 0.969

Table 4: Ablation Study: Average PSNR and SSIM for connection between priors
on the benchmark dataset. Here, ‘7-1’ means seven stages one prior while
‘13-6’means thirteen stages six priors.

7-1 w/o connection | 7-1 w/ connection | 13-6 w/o connection | 13-6 w/connection
---|---|---|---
34.23, 0.961 | 34.85, 0.967 | 34.77, 0.966 | 35.41, 0.969

###  5.4 Ablation Study

Effect of stages and ensemble priors: In our ELP-unfolding model, the single
prior period contains 8 stages, ensemble priors period contains 5 stages and
thus the whole model contains 13 stages. The 9-th stage has two priors to deal
with projection operation while the 10-th stage has three priors and so on and
so forth. In the end, in the 13-th stage, there are six priors.

Focusing on the number of stages in Table 2, we can see that the more stages
one model has, the better result this model can achieve. But when the number
of stages reaches 13, the reconstruction accuracy can not be improved any
more. Regarding the priors, by adopting ensemble learning priors strategy, the
6 priors (with 13 stages) model can still improve reconstruction accuracy.
Besides, in the same number of stage case, ensemble learning model always
behaves better than its single prior counterpart. For instance, in the 9-stage
model, two priors in the last stage always leads to better results than the
single prior counterpart.

Next, we consider a more complicated structure. Specifically, we use 2 priors
in stage-2 and 3 priors in stage-3 and so on and so forth. For a fair
comparison, we also use a 13 stage model. The result of this complicated model
is called ‘Ensemble all’ in Table 3. We can observe that even though the model
is more complicated, it cannot lead to better results than our proposed
structure. In addition, the ‘Ensemble no’ in Table 3 means a single prior used
in all stages, and the same for the 13 stages in Table 2. This model can lead
to decent results but not as good as our proposed structure. Thus, after
comparison, we set the 6 priors model as our final ELP-unfolding, the results
of which are also shown in ‘Integrating all’ in Table 3.

Effect of dense connection: To verify the effect of the dense connection in
ELP-unfolding, we make the comparisons with and without dense connection in
the 7 stages model (‘7-1’) and 6 priors model (‘13-6’). The 7 stages model has
seven stages but just contains one prior in every stage while 6 priors model
is the full model in our paper to achieve SOTA results. As shown in Table 4,
removing the dense connection will lower the performance of unfolding
algorithms including the single prior model and the ensemble prior model,
because the information transmitted between priors is limited. It should be
noticed that our dense connection operation is simple, just consisting of
adding and concatenating, instead of complex operations such as the dense
feature map adaption in Dense3D-Unfolding [37]. Thus our ELP-unfolding
provides a simple strategy (dense connection) to improve the performance of
deep unfolding.

Effect of training dataset: The training dataset plays a key role in
performance of deep learning algorithms, and ELP-unfolding is no exception. We
verify this by using part of the training dataset, _i.e_., only train dataset
on 480p videos in DAVIS2017 but not including test dataset and test-challenge
dataset; the results are shown in ‘Part training-set’ in Table 3. By comparing
‘Part training-set’ and ‘Integrating all’, we find reducing the amount of
training set hurts the performance of ELP-unfolding.

###  5.5 Real datasets for SCI

Figure 9: Real data Chopwheel: Fourteen ($B$=14) 256×256 frames (7 are shown
in the right) are reconstructed from a compressed measurement (left).  Figure
10: Real data duomino: Ten ($B$=10) 512×512 frames reconstructed from a
compressed measurement (left) .  Figure 11: Real data waterballon: Ten
($B$=10) 512×512 frames reconstructed from a compressed measurement (left) .

We now apply the proposed ELP-unfolding to real datasets, namely, chopwheel
[22], waterBalloon and duomino [29]. Because of the unavoidable measurement
noise, it is more challenging to reconstruct real measurements. The chopwheel
data is of size 256${\times}$256${\times}$14 while the other two datasets have
size 512${\times}$512 ${\times}$10\. From the Figs. 9, 10 and 11, we can see
that our method can generate more apparent contours with fewer artifacts and
ghosting. Therefore, we can conclude that in real applications, our method is
powerful to reconstruct the desired high-speed scenes.

##  6 Conclusions and Future Work

Inspired by ensemble learning and iterative based optimization algorithm, we
develop the ensemble learning priors unfolding for scalable snapshot
compressive imaging. Our ELP-unfolding algorithm has achieved the state of the
art results at a short running time. Besides, we have firstly proposed the
scalable function for SCI, not only in the spatial dimension but also in
temporal dimension.

To further improve the reconstruction accuracy, we will consider combining
3D-CNN into ELP-unfolding. Besides, to reduce the testing time and the
parameters of neural network, the distilling method will be taken into use. We
believe that our proposed ELP-unfolding framework can also be used in other
inverse problems such as the image compressive sensing and hyperspectral
compressive imaging.

## References

  * [1] Manya V Afonso, José M Bioucas-Dias, and Mário AT Figueiredo.  An augmented lagrangian approach to the constrained optimization formulation of imaging inverse problems.  IEEE Transactions on Image Processing, 20(3):681–695, 2010.
  * [2] Zeynettin Akkus, Alfiia Galimzianova, Assaf Hoogi, Daniel L Rubin, and Bradley J Erickson.  Deep learning for brain mri segmentation: state of the art and future directions.  Journal of digital imaging, 30(4):449–459, 2017.
  * [3] José M Bioucas-Dias and Mário AT Figueiredo.  A new twist: Two-step iterative shrinkage/thresholding algorithms for image restoration.  IEEE Transactions on Image processing, 16(12):2992–3004, 2007.
  * [4] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein.  Distributed optimization and statistical learning via the alternating direction method of multipliers.  Foundations and Trends in Machine Learning, 3(1):1–122, January 2011.
  * [5] Ziheng Cheng, Bo Chen, Guanliang Liu, Hao Zhang, Ruiying Lu, Zhengjue Wang, and Xin Yuan.  Memory-efficient network for large-scale video compressive sensing.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16246–16255, 2021.
  * [6] Ziheng Cheng, Ruiying Lu, Zhengjue Wang, Hao Zhang, Bo Chen, Ziyi Meng, and Xin Yuan.  Birnat: Bidirectional recurrent neural networks with adversarial training for video snapshot compressive imaging.  In European Conference on Computer Vision, pages 258–275. Springer, 2020.
  * [7] Jianbing Dong, Jian Fu, and Zhao He.  A deep learning reconstruction framework for x-ray computed tomography with incomplete data.  PloS one, 14(11):e0224426, 2019.
  * [8] Weisheng Dong, Guangming Shi, Xin Li, Yi Ma, and Feng Huang.  Compressive sensing via nonlocal low-rank regularization.  IEEE transactions on image processing, 23(8):3618–3632, 2014.
  * [9] D. L. Donoho.  Compressed sensing.  IEEE Transactions on Information Theory, 52(4):1289–1306, April 2006.
  * [10] Marco F Duarte, Mark A Davenport, Dharmpal Takhar, Jason N Laska, Ting Sun, Kevin F Kelly, and Richard G Baraniuk.  Single-pixel imaging via compressive sampling.  IEEE signal processing magazine, 25(2):83–91, 2008.
  * [11] Candes Emmanuel, Justin Romberg, and Terence Tao.  Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information.  IEEE Transactions on Information Theory, 52(2):489–509, February 2006.
  * [12] Graham M Gibson, Baoqing Sun, Matthew P Edgar, David B Phillips, Nils Hempler, Gareth T Maker, Graeme PA Malcolm, and Miles J Padgett.  Real-time imaging of methane gas leaks using a single-pixel camera.  Optics express, 25(4):2998–3005, 2017.
  * [13] Catherine F Higham, Roderick Murray-Smith, Miles J Padgett, and Matthew P Edgar.  Deep learning for real-time single-pixel video.  Scientific reports, 8(1):1–9, 2018.
  * [14] Yasunobu Hitomi, Jinwei Gu, Mohit Gupta, Tomoo Mitsunaga, and Shree K Nayar.  Video from a single coded exposure photograph using a learned over-complete dictionary.  In 2011 International Conference on Computer Vision, pages 287–294. IEEE, 2011.
  * [15] Shirin Jalali and Xin Yuan.  Snapshot compressed sensing: Performance bounds and algorithms.  IEEE Transactions on Information Theory, 65(12):8005–8024, 2019\.
  * [16] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [17] Kuldeep Kulkarni, Suhas Lohit, Pavan Turaga, Ronan Kerviche, and Amit Ashok.  Reconnet: Non-iterative reconstruction of images from compressively sensed measurements.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 449–458, 2016.
  * [18] Chengbo Li.  An efficient algorithm for total variation regularization with applications to the single pixel camera and compressive sensing.  Rice University, 2010.
  * [19] Chengbo Li, Wotao Yin, Hong Jiang, and Yin Zhang.  An efficient augmented lagrangian method with applications to total variation minimization.  Computational Optimization and Applications, 56(3):507–530, 2013\.
  * [20] Jin Liu, Yi Pan, Min Li, Ziyue Chen, Lu Tang, Chengqian Lu, and Jianxin Wang.  Applications of deep learning to mri images: A survey.  Big Data Mining and Analytics, 1(1):1–18, 2018.
  * [21] Yang Liu, Xin Yuan, Jinli Suo, David J Brady, and Qionghai Dai.  Rank minimization for snapshot compressive imaging.  IEEE transactions on pattern analysis and machine intelligence, 41(12):2990–3006, 2018.
  * [22] Patrick Llull, Xuejun Liao, Xin Yuan, Jianbo Yang, David Kittle, Lawrence Carin, Guillermo Sapiro, and David J. Brady.  Coded aperture compressive temporal imaging.  Opt. Express, 21(9):10526–10545, May 2013.
  * [23] Ziyi Meng, Shirin Jalali, and Xin Yuan.  Gap-net for snapshot compressive imaging.  arXiv preprint arXiv:2012.08364, 2020.
  * [24] Alexandre Mercat, Marko Viitanen, and Jarno Vanne.  Uvg dataset: 50/120fps 4k sequences for video codec analysis and development.  In Proceedings of the 11th ACM Multimedia Systems Conference, pages 297–302, 2020.
  * [25] Ali Mousavi, Ankit B Patel, and Richard G Baraniuk.  A deep learning approach to structured signal recovery.  In 2015 53rd annual allerton conference on communication, control, and computing (Allerton), pages 1336–1343. IEEE, 2015.
  * [26] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  Advances in neural information processing systems, 32:8026–8037, 2019.
  * [27] Panagiotis Pintelas and Ioannis E Livieris.  Special issue on ensemble learning and applications, 2020.
  * [28] Jordi Pont-Tuset, Federico Perazzi, Sergi Caelles, Pablo Arbeláez, Alex Sorkine-Hornung, and Luc Van Gool.  The 2017 davis challenge on video object segmentation.  arXiv preprint arXiv:1704.00675, 2017.
  * [29] Mu Qiao, Ziyi Meng, Jiawei Ma, and Xin Yuan.  Deep learning for video compressive sensing.  APL Photonics, 5(3):030801, 2020.
  * [30] Neal Radwell, Steven D Johnson, Matthew P Edgar, Catherine F Higham, Roderick Murray-Smith, and Miles J Padgett.  Deep learning optimized single-pixel lidar.  Applied Physics Letters, 115(23):231101, 2019.
  * [31] Dikpal Reddy, Ashok Veeraraghavan, and Rama Chellappa.  P2c2: Programmable pixel compressive camera for high speed imaging.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 329–336, June 2011.
  * [32] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In (MICCAI), volume 9351 of LNCS, pages 234–241. Springer, 2015.
  * [33] Wuzhen Shi, Feng Jiang, Shengping Zhang, and Debin Zhao.  Deep networks for compressed image sensing.  In 2017 IEEE International Conference on Multimedia and Expo (ICME), pages 877–882. IEEE, 2017.
  * [34] Matias Tassano, Julie Delon, and Thomas Veit.  Fastdvdnet: Towards real-time deep video denoising without flow estimation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1354–1363, 2020.
  * [35] Junxiang Wang, Fuxun Yu, Xiang Chen, and Liang Zhao.  Admm for efficient deep learning with global convergence.  In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 111–119, 2019.
  * [36] Zhengjue Wang, Hao Zhang, Ziheng Cheng, Bo Chen, and Xin Yuan.  Metasci: Scalable and adaptive reconstruction for video compressive sensing.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2083–2092, 2021.
  * [37] Zhuoyuan Wu, Jian Zhang, and Chong Mou.  Dense deep unfolding network with 3d-cnn prior for snapshot compressive imaging.  arXiv preprint arXiv:2109.06548, 2021.
  * [38] Chengshuai Yang, Dalong Qi, Fengyan Cao, Yilin He, Xing Wang, Wenlong Wen, Jinshou Tian, Tianqing Jia, Zhenrong Sun, and Shian Zhang.  Improving the image reconstruction quality of compressed ultrafast photography via an augmented lagrangian algorithm.  Journal of Optics, 21(3):035703, 2019.
  * [39] Yan Yang, Jian Sun, Huibin Li, and Zongben Xu.  Deep admm-net for compressive sensing mri.  In Proceedings of the 30th international conference on neural information processing systems, pages 10–18, 2016.
  * [40] Yan Yang, Jian Sun, Huibin Li, and Zongben Xu.  Admm-csnet: A deep learning approach for image compressive sensing.  IEEE transactions on pattern analysis and machine intelligence, 42(3):521–538, 2018.
  * [41] Jaejun Yoo, Sohail Sabir, Duchang Heo, Kee Hyun Kim, Abdul Wahab, Yoonseok Choi, Seul-I Lee, Eun Young Chae, Hak Hee Kim, Young Min Bae, et al.  Deep learning diffuse optical tomography.  IEEE transactions on medical imaging, 39(4):877–887, 2019.
  * [42] Xin Yuan.  Generalized alternating projection based total variation minimization for compressive sensing.  In 2016 IEEE International Conference on Image Processing (ICIP), pages 2539–2543, September 2016.
  * [43] Xin Yuan, David J. Brady, and Aggelos K. Katsaggelos.  Snapshot compressive imaging: Theory, algorithms, and applications.  IEEE Signal Processing Magazine, 38(2):65–88, 2021.
  * [44] Xin Yuan, Yang Liu, Jinli Suo, and Qionghai Dai.  Plug-and-play algorithms for large-scale snapshot compressive imaging.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 1447–1457, June 2020.
  * [45] Xin Yuan, Yang Liu, Jinli Suo, Frédo Durand, and Qionghai Dai.  Plug-and-play algorithms for video snapshot compressive imaging.  arXiv: 2101.04822, January 2021.
  * [46] Xin Yuan, Patrick Llull, Xuejun Liao, Jianbo Yang, and Lawrence Carin.  Low-cost compressive sensing for color video and depth.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), page 3318–3325, June 2014.
  * [47] Jian Zhang and Bernard Ghanem.  Ista-net: Interpretable optimization-inspired deep network for image compressive sensing.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1828–1837, 2018.
  * [48] Kai Zhang, Wangmeng Zuo, and Lei Zhang.  Ffdnet: Toward a fast and flexible solution for cnn-based image denoising.  IEEE Transactions on Image Processing, 27(9):4608–4622, 2018.
  * [49] Hao Zheng, Yizhe Zhang, Lin Yang, Peixian Liang, Zhuo Zhao, Chaoli Wang, and Danny Z Chen.  A new ensemble learning framework for 3d biomedical image segmentation.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 5909–5916, 2019.
  * [50] Kaiyang Zhou, Yongxin Yang, Yu Qiao, and Tao Xiang.  Domain adaptive ensemble learning.  IEEE Transactions on Image Processing, 30:8008–8018, 2021.