\section{Introduction}

A relational triple consists of two entities connected by a semantic relation, which is in the form of (subject, relation, object). The extraction of relational triples from unstructured raw texts is a key technology for automatic knowledge graph construction, which has received growing interest in recent years.

There have been several studies addressing technical solutions for relational triple extraction. Early researches, such as \citet{zelenko2003kernel,chan2011exploiting}, employ a pipeline manner to extract both of entities and relations, where entities are recognized first and then the relation between the extracted entities is predicted. Such a pipeline approach ignores the relevance of entity identification and relation prediction \cite{li2014incremental} and tends to suffer from the error propagation problem.

To model cross-task dependencies explicitly and prevent error propagation in the pipeline approach, subsequent studies propose joint entity and relation extraction. These studies can be roughly categorized into three main
paradigms. The first stream of work, such as \citet{miwa2016end,gupta2016table,zhang2017end}, treats joint entity and relation extraction task as an end-to-end table filling problem. Although these methods represent entities and relations with shared parameters in a single model, they extract the entities and relations separately and produce redundant information \cite{zheng2017joint}. The second stream of work, such as \citet{zheng2017joint,dai2019joint,wei-etal-2020-novel}, transforms joint entity and relation extraction into sequence labeling. To do this, human experts need to design a complex tagging schema. The last stream of work, including \citet{zeng2018extracting,zeng2019learning,nayak2019ptrnetdecoding,zeng2020copymtl}, is driven by the sequence-to-sequence (seq2seq) model \cite{sutskever2014sequence} to generate relational triples directly, which is a flexible framework to handle overlapping triples and does not require the substantial effort of human experts.

We follow the seq2seq based models for joint entity and relation extraction. Despite the success of existing seq2seq based models, they are still limited by the autoregressive decoder and the cross-entropy loss. The reasons are as follows: the relational triples contained in a sentence have no intrinsic order in essence. However, in order to adapt the autoregressive decoder, whose output is a sequence,  the unordered target triples must be sorted in a certain order during the training phase. Meanwhile, cross-entropy is a permutation-sensitive loss function, where a penalty is incurred for every triple that is predicted out of the position. Consequently, current seq2seq base models not only need to learn how to generate triples, but also are required to consider the extraction order of multiple triples.

In this work, we formulate the joint entity and relation extraction task as a set prediction problem, avoiding considering the order of multiple triples. In order to solve the set prediction problem, we propose an end-to-end network featured by transformers with non-autoregressive parallel decoding and bipartite matching loss. In detail, there are three parts in the proposed set prediction networks (SPN): a sentence encoder, a set generator, and a set based loss function. First of all, we adopt the BERT model \cite{devlin2018bert} as the encoder to represent the sentence. Then, since an autoregressive decoder must generate items one by one in order, such a decoder is not suitable for generating unordered sets. In contrast, we leverage the transformer-based non-autoregressive decoder \cite{gu2018non} as the set generator, which can predict all triples at once and avoid sorting triples. Finally, in order to assign a predicted triple to a unique ground truth triple, we propose bipartite matching loss function inspired by the assigning problem in operation research \cite{kuhn1955hungarian,munkres1957algorithms,edmonds1972theoretical}. Compared with  cross-entropy loss
that highly penalizes small shifts in
triple order, the proposed loss function is invariant to any permutation of predictions; thus it is suitable for evaluating the difference between ground truth set and prediction set.

In a nutshell, our main contributions are:

\begin{itemize}
\item We formulate the joint entity and relation extraction task as a set prediction problem.
\item We combine non-autoregressive parallel decoding with bipartite matching loss function to solve this problem.
\item Our proposed method yields state-of-the-art results on two benchmark datasets, and we perform various experiments to verify the effectiveness of the method.
\textbf{}
\end{itemize}
\section{Related Work}
\subsection{Relation Extraction}
Relation extraction is a long-standing natural language process task of mining factual knowledge from free texts. When giving a sentence with annotated entities, this task degenerates into a simple task, namely relation classification. Some studies, such as \citet{zeng-etal-2014-relation,xu2015classifying}, leveraged CNN or RNN to solve the relation classification task. However, these methods ignore the extraction of entities from sentences and could not truly extract relational facts.

When giving a sentence without any annotated entities, researchers proposed several methods to extract entities and relations jointly. Existing studies on multiple relation extraction
task can be divided into four paradigms: (1) Pipeline based methods, such as \citet{zelenko2003kernel,chan2011exploiting}, firstly recognize entities and then conduct relation classification; (2) Table filling based methods, like \citet{miwa2016end,gupta2016table,zhang2017end}, represent entities and relations with shared parameters, but extract the entities and relations separately; (3) Tagging based methods, such as \citet{zheng2017joint,dai2019joint,wei-etal-2020-novel}, treat this task as a sequence labeling problem and need to design complex tagging schema; (4) Seq2seq based methods, like \citet{zeng2018extracting,zeng2019learning,nayak2019ptrnetdecoding,zeng2020copymtl},
apply seq2seq model to generate relational triples directly. Our work is in line with seq2seq based methods.  In contrast with the previous studies, we reckon the triples in a sentence are in the form of a set instead of a sequence, and treat the joint entity and relation extraction as a set prediction problem.

\subsection{Non-Autoregressive Model}
Non-autoregressive models \cite{gu2018non,lee2018deterministic, ma-etal-2019-flowseq} generate all the tokens of a target in parallel and can speed up inference. Non-autoregressive models are widely explored in natural language and speech processing tasks such as neural machine translation \cite{gu2018non} and automatic speech recognition \cite{chen2019non}. To the best of our knowledge, this is the first work to apply non-autoregressive models to information extraction. In this work, we resort to the
non-autoregressive model to generate the set of triples in one shot.

\begin{figure*}[t]
  	\begin{center} \includegraphics*[clip=true,width=0.96\textwidth,height=0.3\textheight]{graph/model_v5_clip.pdf}
  	\caption{The main architecture of set prediction networks.
  	The set prediction networks predict the final set of triples in parallel by combining a BERT encoder with a non-autoregressive decoder. In the training phrase, bipartite matching uniquely assigns predictions with ground truths to provide accurate training signals.
  	} \label{fig}
  \end{center}
  \end{figure*}
\section{Method}

The goal of joint entity and relation extraction is to identify all possible relational triples in a given sentence. Formally, given an raw sentence $X$, the conditional probability of the target triple set $Y=\{(s_1, r_1, o_1),..., (s_n, r_n, o_n)\}$ is:
\begin{equation}
    P(Y|X;\theta) = p_L(n|X)\prod \limits_{i=1}^n p(Y_i|X, Y_{j \neq i}; \theta)
\label{equ1}
\end{equation}
where $p_L(n|X)$ model the size of the target triple set, and $p(Y_i|X, Y_{j \neq i}; \theta)$ means that a target triple $Y_i$ is related not only to the given sentence $X$, but also to the other triples $Y_{j \neq i}$.

In this paper, this conditional probability is parameterized using set prediction networks (SPN), which are shown in Figure \ref{fig}. Three key components of the proposed networks will be elaborated in the following section. Concretely, we first introduce the sentence encoder, which represents each token in a given sentence based on its bidirectional context. Then, we present how to use the non-autoregressive decoder to generate a set of triples in a single pass. Finally, we describe a set-based loss, dubbed as bipartite matching loss,  which forces unique matching between predicted and ground truth triples.

\subsection{Sentence Encoder}
\label{encoder}
The goal of this component is to obtain the context-aware representation of each token in a sentence. Given the impressive performance of recent deep transformers \cite{vaswani2017attention} trained on variants of language modeling, we utilize the BERT model \cite{devlin2018bert} as the sentence encoder.
The input sentence is segmented with tokens by the byte pair encoding \cite{sennrich-etal-2016-neural}, and then fed into the BERT model. The output of the BERT model is the context-aware embedding of tokens, and is denoted as $\mathbf{H}_e \in \mathbb{R}^{l \times d}$, where $l$ is the sentence length (including ${\rm [CLS]}$ and ${\rm [SEP]}$, two special start and end markers), and $d$ is the number of hidden units in the BERT model.

\subsection{Non-Autoregressive Decoder for Triple Set Generation}
\label{decoder}
We regard joint entity and relation extraction as a set prediction problem and use the transformer-based non-autoregressive decoder \cite{gu2018non} to directly generate the triple set. Previous studies \cite{zeng2018extracting, zeng2019learning,nayak2019ptrnetdecoding,zeng2020copymtl} transform the triple set to a triple sequence and then leverage the autoregressive decoder to generate triples one by one. In such a way, the conditional probability of the target triple set in Equation \ref{equ1} is modified into:
\begin{equation}
        P(Y|X;\theta) =\prod \limits_{i=1}^n p(Y_i|X, Y_{j < i}; \theta)
\end{equation}
In contrast, we use the non-autoregressive decoder to direct model the Equation \ref{equ1}. Compared with previous seq2seq based method, the non-autoregressive decoder can not only
avoid learning the extraction order of multiple triples, but also generate triples based on bidirectional information, not just left-to-right information.

\textbf{Input.} Before decoding starts, the decoder need to know  the size of  the target set, in other words, $p_L(n|X)$ in Equation \ref{equ1} is required to be modeled at first. In this work, we simplify the $p_L(n|X)$ into a constant by requiring the non-autoregressive decoder to generate a fixed-size set of $m$ predictions for each sentence,  where $m$ is set to be significantly larger than the typical number of triples in a sentence.  Instead of copying tokens from the encoder side \cite{gu2018non}, the input of the decoder is initialized by $m$ learnable embeddings that we refer to as triple queries. Note that all sentences share the same triple queries.

\textbf{Architecture.} The non-autoregressive decoder is composed of a stack of $N$ identical transformer layers. In each transformer layer, there are multi-head self attention mechanism to model the relationship between triples, and multi-head inter attention mechanism to fuse the information of the given sentence. Notably, compared with autoregressive decoder, the non-autoregressive decoder does not have the constraint of an autoregressive factorization of the output, so there is no need to prevent earlier decoding steps from accessing information from later steps. Thus, there is no casual mask used in the multi-head self attention mechanism. Instead, we use the unmasked self-attention.

The $m$ triple queries are transformed into $m$ output embeddings by the non-autoregressive decoder, which are denoted as $\mathbf{H}_d \in \mathbb{R}^{m \times d}$. The output embeddings $\mathbf{H}_d$ are then independently decoded into relation types and entities by feed forward networks (FFN), resulting $m$ final predicted triples. Concretely, given an output embedding $\mathbf{h}_d \in \mathbb{R}^d$ in $\mathbf{H}_d$, the predicted relation type is obtained by:
\begin{equation}
    \mathbf{p}^r = \rm{softmax}(\mathbf{W_r} \mathbf{h}_d)
    \label{pr}
\end{equation}
and the predicted entities (subject and object) are decoded by separately predicting the starting and ending indices with four $l$-class classifiers:
\begin{align}
\mathbf{p}^{s-start} = \rm{softmax}(\mathbf{v_1^T}\rm{tanh}(\mathbf{W_1} \mathbf{h}_d + \mathbf{W_2}\mathbf{H_e}))\\
\mathbf{p}^{s-end}  = \rm{softmax}(\mathbf{v_2^T}\rm{tanh}(\mathbf{W_3} \mathbf{h}_d + \mathbf{W_4}\mathbf{H_e}))\\
\mathbf{p}^{o-start} = \rm{softmax}(\mathbf{v_3^T}\rm{tanh}(\mathbf{W_5} \mathbf{h}_d + \mathbf{W_6}\mathbf{H_e}))\\
\mathbf{p}^{o-end} = \rm{softmax}(\mathbf{v_4^T}\rm{tanh}(\mathbf{W_7} \mathbf{h}_d + \mathbf{W_8}\mathbf{H_e}))
\label{pe}
\end{align}
where $\mathbf{W}_r\in\mathbb{R}^{t\times d}$, $\{\mathbf{W}_i\in\mathbb{R}^{d\times d}\}_{i=1}^8$ and $\{\mathbf{v}_i\in\mathbb{R}^d\}_{i=1}^4$ are learnable parameters, $t$ is the total number of relation types (including a special relation type $\varnothing$ to indicate no triple), $l$ is the sentence length, and $\textbf{H}_e$ is the output of the BERT model.

\subsection{Bipartite Matching Loss}
\label{loss}
The main difficulty of training is to score the predicted triples with respect to the ground truths. It is not proper to apply cross-entropy loss function to measure the difference between two sets, since cross-entropy loss is sensitive to the permutation of the predictions. Inspired by the assigning problem in operation research \cite{kuhn1955hungarian}, we propose a set prediction loss that can produce an optimal bipartite matching between predicted and ground truth triples.

\textbf{Notations.} Let us denote by $\mathbf{Y} = \{\mathbf{Y}_i\}_{i=1}^n$ the set of ground truth triples, and $\hat{\mathbf{Y}} = \{\hat{\mathbf{Y}}_i\}_{i=1}^m$ the set of m predicted triples, where $m$ is larger than $n$. We consider $\mathbf{Y}$ also as a set of size $m$ padded with $\varnothing$ (no triple).  Each element $i$ of the ground truth set can be seen as a $\mathbf{Y}_i = (r_i,s^{start}_i, s^{end}_i,o^{start}_i,o^{end}_i)$,  where $r_i$ is the target relation type (which may be $\varnothing$) and $s^{start}_i, s^{end}_i,o^{start}_i,o^{end}_i$ are the starting or ending indices of subject $s$ or object $o$. Each element $i$ of the set of predicted  triples is denoted as $\hat{\mathbf{Y}}_i =(\mathbf{p}^r_i, \mathbf{p}^{s-start}_i ,\mathbf{p}^{s-end}_i ,\mathbf{p}^{o-start}_i,\mathbf{p}^{o-end}_i)$, which is calculated based on Equation \ref{pr}-\ref{pe}.

\textbf{Loss. } The process of computing bipartite matching loss is divided into two steps: finding an optimal matching and computing the loss function.

To find an optimal matching between the set of ground truth triples $\mathbf{Y}$ and the set of predicted triples $\hat{\mathbf{Y}}$, we search for a permutation of elements $\pi^\star$ with the lowest cost:
\begin{equation}
    \pi^\star = \mathop{\arg \min} \limits_{\pi \in \Pi(m)} \sum \limits_{i=1}^m \mathcal{C}_{match}(\mathbf{Y}_i, \hat{\mathbf{Y}}_{\pi(i)})
    \label{assignment}
\end{equation}
where $\Pi(m)$ is the space of all m-length permutations.  $\mathcal{C}_{match}(\mathbf{Y}_i, \hat{\mathbf{Y}}_{\pi(i)})$ is a pair-wise matching cost between the ground truth $\mathbf{Y}_i$ and the predicted triple with index $\pi(i)$. By taking into account both the prediction of relation type and the predictions of entity spans, we define $\mathcal{C}_{match}(\mathbf{Y}_i, \hat{\mathbf{Y}}_{\pi(i)})$ as:
\begin{equation}
\begin{split}
     \mathcal{C}_{match}(\mathbf{Y}_i, \hat{\mathbf{Y}}_{\pi(i)})  &= - \mathbbm{1} _{\{r_i \neq \varnothing\}}[\mathbf{p}^r_{\pi(i)}(r_i) \\
    & + \mathbf{p}^{s-start}_{\pi(i)}(s_i^{start})\\
    &+ \mathbf{p}^{s-end}_{\pi(i)}(s_i^{end})\\
    &   + \mathbf{p}^{o-start}_{\pi(i)}(o_i^{start}) \\
    &+ \mathbf{p}^{o-end}_{\pi(i)}(o_i^{end})]
\end{split}
\end{equation}

This optimal assignment $\pi^\star$ is computed in polynomial time ($O(m^3)$) via the Hungarian algorithm \footnote{ \url{https://en.wikipedia.org/wiki/Hungarian_algorithm}}. In detail, we can view the set of ground truth $\mathbf{Y}$ as a set of people in the assignment problem, the set of predicted triples $\mathbf{\hat{Y}}$ as a set of jobs. The cost of assigning $\mathbf{Y}_i$ (the people $i$) with $\mathbf{\hat{Y}_j}$ (the job $j$) is defined as  $\mathcal{C}_{match}(\mathbf{Y}_i, \hat{\mathbf{Y}}_{j})$. The optimal matching with the minimum total cost is easy to be computed via the classical Hungarian algorithm.

The second step is to compute the loss function for all pairs matched in the previous step. We define the loss as:
\begin{equation}
\begin{split}
    \mathcal{L}(\mathbf{Y}, \hat{\mathbf{Y}})  &= \sum \limits_{i=1}^m\{-\log \mathbf{p}^r_{\pi^\star(i)}(r_i) \\
    & + \mathbbm{1} _{\{r_i \neq \varnothing\}}[-\log \mathbf{p}^{s-start}_{\pi^\star(i)}(s_i^{start})\\
    &-  \log \mathbf{p}^{s-end}_{\pi^\star(i)}(s_i^{end})\\
    & - \log \mathbf{p}^{o-start}_{\pi^\star(i)}(o_i^{start}) \\
    & - \log \mathbf{p}^{o-end}_{\pi^\star(i)}(o_i^{end})]\}
\end{split}
\label{loss_equ}
\end{equation}
where $\pi^\star$ is the optimal assignment computed in the first step  (Equation \ref{assignment}).
\section{Experiments}
In this section, we carry out an extensive set of experiments with the aim of answering the following research questions:
\begin{itemize}
    \item  \textbf{RQ1}: What is the overall performance of the proposed set prediction networks (SPN) in joint entity and relation extraction?
    \item \textbf{RQ2}: How does each design of our model matter?
    \item \textbf{RQ3}: What is the performance of the proposed model in sentences annotated with different numbers of triples?
    \item \textbf{RQ4}: How does our proposed model adapt to different overlapping patterns?
\end{itemize}
In the remainder of this section, we describe the datasets, experimental setting, and all baselines.

\subsection{Datasets}
We evaluate the proposed method on two widely used joint entity and relation extraction datasets: New York Times (NYT) \cite{riedel2010modeling} and WebNLG \cite{gardent2017creating} \footnote{These datasets are available at \url{https://github.com/xiangrongzeng/copy_re}}. The statistics of these datasets are shown in Table \ref{dataset}.

\textbf{NYT}. This dataset is produced by the distantly supervised method, which automatically aligns Freebase with 1987-2007 New York Times news articles. There are 24 predefined relation types in total. Following previous studies \cite{zheng2017joint,zeng2018extracting}, we ignore the noise in this dataset and treat it as a supervised dataset. Since there are many versions of the NYT dataset, we adopted the preprocessed dataset used in \citet{zeng2018extracting}, which is publicly available.

\textbf{WebNLG}. This data is originally created for Natural Language Generation (NLG) task. In this dataset, an instance includes a set of triples and several standard sentences written by humans. Every standard sentence contains all triples of this instance. There are 246 predefined relation types in this dataset.

\textbf{Overlap Between Triples}. According to different overlapping patterns of triples, sentences are split into three categories \cite{zeng2018extracting}: Normal, Entity Pair Overlap (EPO) and Single Entity Overlap (SEO). A sentence belongs to Normal class if none of its triples have overlapped entities. A sentence belongs to EPO class if some of its triples have overlapped entity pairs. And a sentence belongs to SEO class if some of its triples have an overlapped entity and these triples don’t have overlapped entity pair. Note that a sentence
can belongs to both EPO class and SEO class.
\begin{table}[h]
\begin{center}
\scalebox{0.88}{
\begin{tabular}{c|cc|cc}
\hline
\multirow{2}{*}{Category} &
\multicolumn{2}{c|}{NYT} & \multicolumn{2}{c}{WebNLG} \\
\cline{2-5}
                          & Train       & Test      & Train        & Test        \\
                          \hline\hline
Normal                    & 37013       & 3266      & 1596         & 246         \\
EPO                       & 9782        & 978       & 227          & 26          \\
SEO                       & 14735       & 1297      & 3406         & 457         \\ \hline
ALL                       & 56195       & 5000      & 5019         & 703        \\ \hline
\end{tabular}}
\caption{The statistics of NYT and WebNLG.}
\label{dataset}
\end{center}
\end{table}

\begin{table*}[thbp]
\begin{center}
\begin{tabular}{l|ccc|ccc}
\hline
\multirow{2}{*}{Models}               & \multicolumn{3}{c|}{Partial Matching} & \multicolumn{3}{c}{Exact Matching} \\\cline{2-7}

                                      & Precision    & Recall    & F1     & Precision   & Recall   & F1     \\
                                      \hline\hline
NovelTagging \cite{zheng2017joint}     & 62.4         & 31.7      & 42     & -            &  -        &   -     \\
CopyRE-One \cite{zeng2018extracting}   & 59.4         & 53.1      & 56.0   &   -          &    -      &   -     \\
CopyRE-Mul\cite{zeng2018extracting} & 61.0         & 56.6      & 58.7   &  -           &     -     &    -    \\
GraphRel-1p \cite{fu2019graphrel}          & 62.9         & 57.3      & 60.0   & -            & -         &    -    \\
GraphRel-2p \cite{fu2019graphrel}            & 63.9         & 60.0      & 61.9   &        -     &      -    &      -  \\
CopyRRL \cite{zeng2019learning}          & 77.9         & 67.2      & 72.1   &           -  &    -      &   -     \\
WDec\cite{nayak2019ptrnetdecoding}     &   -           &  -         &  -                    &88.1         & 76.1      & 81.7        \\
PNDec\cite{nayak2019ptrnetdecoding} &   -           &  -         &  -                    &80.6         & 77.3      & 78.9        \\
CopyMTL-One \cite{zeng2020copymtl} &-&-&-&72.7 &69.2 &70.9 \\
CopyMTL-Mul \cite{zeng2020copymtl} &-   &- &- &  75.7 &68.7 &72.0 \\
Attention as Relation \cite{ijcai2020-524} &-&-&-&88.1& 78.5& 83.0\\
CasRel \cite{wei-etal-2020-novel}                        & 89.7         & 89.5      & 89.6   & 90.1$ ^\dag$       & 88.5$ ^\dag$    & 89.3 $ ^\dag$\\
\hline
    SPN (Ours)                                  & \textbf{93.3}         & \textbf{91.7}      & \textbf{92.5}   &  \textbf{92.5}           &   \textbf{92.2}       & \textbf{92.3}    \\
\hline
\end{tabular}
\caption{Precision (\%) , Recall (\%)  and F1 score (\%) of our proposed SPN and state-of-the-art mehtods on the NYT test set. $\dag$ indicates that the result is reproduced by us.}
\label{NYT_result}
\end{center}
\end{table*}

\begin{table}[thbp]
\begin{center}
\begin{tabular}{l|ccc}
\hline
Models  & Precision    & Recall    & F1  \\
                                      \hline\hline
NovelTagging     & 52.5         & 19.3      & 28.3       \\
CopyRE-One   & 32.2         &28.9      & 30.5    \\
CopyRE-Mul & 37.7         &36.4     & 37.1    \\
GraphRel-1p        & 42.3         & 39.2     & 40.7    \\
GraphRel-2p           & 44.7         & 41.1     & 42.9  \\
CopyRRL       &63.3         & 59.9      & 61.6  \\
CasRel                       & \textbf{93.4}         & 90.1      & 91.8 \\
\hline
SPN (Ours) & 93.1         & \textbf{93.6}      & \textbf{93.4} \\
\hline
\end{tabular}
\caption{Precision (\%) , Recall (\%)  and F1 score (\%) of our proposed SPN and state-of-the-art mehtods on the WebNLG test set.}
\label{WebNLG_result}
\end{center}
\end{table}

\subsection{Evaluation Metrics}
We adopt standard micro-F1 to evaluate the performance. A triple is regarded as correct if the relation type and the two corresponding entities are all correct. Notably, there are two ways to judge whether the extracted entities are correct. One is Partial Matching, where the extracted entities are regarded as correct if the predictions of subject and object are the same as the head words of the ground truth. Since the head word of entity is not annotated in most situations, the last word of entity is treated as the head word. The other is Exact Matching. In this way, only if the predictions of subject and object are identical to the ground truth, the extracted entities are treated as correct. Note that the training data under partial matching is different from the one under exact matching. Under partial matching, only head words of entities are annotated, while the whole entities  are annotated under exact matching.
\subsection{Implementation Details}
To conduct a fair comparison, we use the cased base version of BERT in our experiments, which contains 110M parameters. The initial learning rate of BERT is set to 0.00001, and the initial learning of the non-autoregressive decoder is set to 0.00002. The number of stacked bidirectional transformer blocks in non-autoregressive decoder is set to 3. We use the dropout strategy to mitigate overfitting, the dropout rate is set to 0.1. Meanwhile, We apply gradient clipping to prevent exploding gradients. The set prediction networks are trained by minimizing the loss function defined in Equation \ref{loss_equ} through stochastic gradient descent over shuffled mini-batch with the AdamW update rule  \cite{loshchilov2017decoupled}. All experiments are conducted with an NVIDIA GeForce RTX 2080 Ti.

\begin{table*}[thbp]
\begin{center}
\begin{tabular}{c|c|ccc|ccc}
\hline
\multirow{2}{*}{Models}    & \multirow{2}{*}{Element} & \multicolumn{3}{c|}{NYT}   & \multicolumn{3}{c}{WebNLG} \\
\cline{3-8}
                           &                          & Precsoion & Recall & F1   & Precision  & Recall & F1   \\
                           \hline \hline
\multirow{3}{*}{CasRel \cite{wei-etal-2020-novel}}    & ($s$,$o$)                    & 89.2      & 90.1   & 89.7 & \textbf{95.3}       & 91.7   & 93.5 \\
                           & $r$                        & 96.0     & 93.8   & 94.9 & \textbf{96.6}       & 91.5   & 94.0 \\
                           & Overall   & 89.7         & 89.5      & 89.6  &  \textbf{93.4}         & 90.1      & 91.8 \\
                           \hline
\multirow{3}{*}{SPN (Ours)} & $(s,o)$                    & \textbf{93.2}      & \textbf{92.7}   & \textbf{92.9} & 95.0       & \textbf{95.4}   & \textbf{95.2} \\
                           & $r$                        & \textbf{96.3}     & \textbf{95.7}   & \textbf{96.0} & 95.2       & \textbf{ 95.7}   & \textbf{95.4}\\
                           & Overall & \textbf{93.3}         & \textbf{91.7}      & \textbf{92.5} & 93.1         & \textbf{93.6}      & \textbf{93.4}\\
                           \hline
\end{tabular}
\end{center}
\caption{Results on extracting elements of relational triples.}
\label{detail_result}
\end{table*}

\subsection{Baselines}
The following state-of-the-art (SoTA) models have been compared in the experiments.
\begin{itemize}
\item NovelTagging \cite{zheng2017joint} introduces a novel tagging scheme that transforms the joint entity and relation extraction task into a sequence labeling problem.
\item CopyRE \cite{zeng2018extracting} is a seq2seq based model with copy mechanism, which can effectively extract overlapping triples.
\item GraphRel \cite{fu2019graphrel} is a two phases model based on graph convolutional networks (GCN), where a relation-weighted GCN is utilized to
model the interaction between entities and relations.
\item CopyRRL \cite{zeng2019learning} combines the reinforcement
learning with a seq2seq model to automatically learn the
extraction order of triples. In such a way, the interactions among
triples can be considered.
\item CopyMTL \cite{zeng2020copymtl} is a multi-task learning
framework, where conditional random field is used to identify entities, and
a seq2seq model is adopted to extract relational triples.
\item WDec \cite{nayak2019ptrnetdecoding} fuses a seq2seq model with a new representation scheme, which enables the decoder to generate one word at a and can handle full entity names of different length and overlapping entities.
\item PNDec \cite{nayak2019ptrnetdecoding} is a modification of seq2seq model. Pointer networks are used in the decoding framework to identify the entities in the sentence using their start and end locations.
\item Attention as Relation \cite{ijcai2020-524} contains
a conditional random field based entity extraction module and a supervised multi-head self attention based relation detection module.
\item CasRel \cite{wei-etal-2020-novel} is a novel cascade binary tagging
framework, where all possible subjects are identified in the first stage, and then for each identified subject, all possible relations and the corresponding objects are simultaneously identified by a relation specific tagger. This work achieves the SoTA results.
\end{itemize}

Note that \citet{li2020downstream} claimed that they have achieved the SoTA results in WebNLG, but we find that the model they proposed is only designed for relation classification. Therefore, we do not compare our method with REDN \cite{li2020downstream}.

\subsection{Main Results}

To start, we address the research question \textbf{RQ1}. Table \ref{NYT_result} and Table \ref{WebNLG_result} show the results of our model against baselines on two benchmark datasets. Overall, our proposed model significantly outperforms baselines on these datasets.

In NYT dataset, Our proposed model outperforms all the baselines in both partial matching and exact matching and achieves 2.9\% and 3.0\% improvements in F1 score respectively over the current SoTA method \cite{wei-etal-2020-novel}. Combined with Table \ref{detail_result}, we find that our proposed model outperforms the SoTA model \cite{wei-etal-2020-novel} in both entity pair extraction and relation type extraction, demonstrating the effectiveness of our proposed model. We also find that there is an obvious gap between the F1 score on relation type extraction and entity pair extraction, but a trivial gap between entity pair extraction and overall extraction. It reveals that entity pair extraction is the main bottleneck of joint entity and relation extraction in NYT dataset.

In WebNLG dataset, since there is no unified version of data under exact matching, we only compare our proposed networks with baselines under partial matching metric. In general, our proposed model achieves the best F1 score under partial matching, which is 93.4\%. There is 1.6\% improvement compared with the result of the SoTA model \cite{wei-etal-2020-novel}, which is 91.8\%. Compared with the SoTA model, We find our model to be more balanced in terms of precision and recall. A further analysis combined with Table \ref{detail_result} shows that our proposed model exhibits balanced results of precision and recall in both entity pair extraction and relation type extraction, while there is an obvious gap between precision and recall in the results of CasRel \cite{wei-etal-2020-novel}. We conjecture that this is largely due to that the number of triple queries is set to be significantly larger than the typical number of triples in a sentence, which ensures that enough triples can be recalled. In addition, we observe that the results of entity pair extraction and relation type extraction are much higher than that of joint entity and relation extraction, which means that the accurate combination of entity pair extraction and relation type extraction is the key to improve the joint entity and relation extraction.
\begin{table}[t]
\scalebox{0.96}{
\begin{tabular}{l|ccc}
\hline
                                                                                & Precision & Recall & F1   \\
                                                                                \hline \hline
\begin{tabular}[c]{@{}l@{}}Bipartite Matching Loss, \\ Num of Decoder Layers = 3\end{tabular} & \textbf{93.3}      & \textbf{91.7}   & \textbf{92.5} \\
\hline
\begin{tabular}[c]{@{}l@{}}Bipartite Matching Loss, \\ Num of Decoder Layers = 2\end{tabular} & 92.7      & 91.3   & 92.0 \\
\hline
\begin{tabular}[c]{@{}l@{}}Bipartite Matching Loss, \\ Num of Decoder Layers = 1\end{tabular}  & 91.9      & 90.9   & 91.4 \\
\hline
\begin{tabular}[c]{@{}l@{}}Cross-Entropy Loss,\\ Num of Decoder Layers = 3\end{tabular}   & 87.2     & 80.9   & 84.0 \\
\hline
\end{tabular}}
\caption{Results of ablation studies on NYT dataset.}
\label{oblation}
\end{table}

 \begin{table*}[thbp]
\begin{center}
\begin{tabular}{l|ccccc|ccccc}
\hline
\multirow{2}{*}{Models} & \multicolumn{5}{c|}{NYT}          & \multicolumn{5}{c}{WebNLG}       \\\cline{2-11}
                        & N=1  & N=2  & N=3  & N=4  & N$\geq$5 & N=1  & N=2  & N=3  & N=4  & N$\geq$5 \\
                        \hline \hline
CopyRE-One \cite{zeng2018extracting}             & 66.6 & 52.6 & 49.7 & 48.7 & 20.3 & 65.2 & 33.0 & 22.2 & 14.2 & 13.2 \\
CopyRE-Mul \cite{zeng2018extracting}         & 67.1 & 58.6 & 52.0 & 53.6 & 30.0 & 59.2 & 42.5 & 31.7 & 24.2 & 30.0 \\
GraphRel-1p \cite{fu2019graphrel} & 69.1 & 59.5 & 54.4 & 53.9 & 37.5 & 63.8 & 46.3 & 34.7 & 30.8 & 29.4 \\
GraphRel-2p \cite{fu2019graphrel}  & 71.0 & 61.5 & 57.4 & 55.1 & 41.1 & 66.0 & 48.3 & 37.0 & 32.1 & 32.1 \\
CopyRRL \cite{zeng2019learning} & 71.7 & 72.6 & 72.5 & 77.9 & 45.9 & 63.4 & 62.2 & 64.4 & 57.2 & 55.7 \\
CasRel \cite{wei-etal-2020-novel} & 88.2 & 90.3 & 91.9 & 94.2 & 83.7 & 89.3 & 90.8 & 94.2 & 92.4 & 90.9 \\ \hline
SPN (Ours)              & \textbf{90.9} & \textbf{93.4} & \textbf{94.2} & \textbf{95.5} & \textbf{90.6} & \textbf{89.5} & \textbf{91.3} & \textbf{96.4} & \textbf{94.7} & \textbf{93.8}\\
\hline
\end{tabular}
\caption{Partial matching F1 score of conducting extraction in sentences that contains different numbers of triples. We divide the sentences of the test sets into 5 sub-classes. Each class contains sentences that have 1,2,3,4 or $\geq$5 triples.}
\label{num_reulst}
\end{center}
\end{table*}

\subsection{Ablation Studies}
Next, we turn to the research question \textbf{RQ2}. We conduct ablation studies to investigate the importance of the non-autoregressive decoder and the bipartite matching loss. To evaluate the importance of the non-autoregressive decoder, we change the number of decoder layers. To evaluate the importance of bipartite matching loss, we replacing bipartite matching loss with cross-entropy loss.

Table \ref{oblation} shows the results. We find that increasing the number of layers of the non-autoregressive decoder can achieve better results. When the number of decoder layers is set to 1, 2, and 3, the best results are 91.4\%, 92.0\% and 92.15\%, respectively. We conjecture that this is largely due to that with the deepening of the non-autoregressive decoder layers,  more multi-head self attention modules allow for better modeling of relationships between triple queries, and more multi-head inter attention modules allow for more complete integration of sentence information into triple queries.

Compared our proposed bipartite matching loss with widely used cross-entropy loss, we find that there is 8.9\% improvement, which indicates bipartite matching loss is very suitable for joint entity and relation extraction. We hypothesize that in order to adopt to cross-entropy loss, the model is required to consider the generative order of triples, which places an unnecessary burden on the model.

\subsection{Detailed Results on Sentences with Different Number of Triples}
In this section, we answer the research question \textbf{RQ3}. To do this, we compare the models' ability of extracting relational facts from sentences annotated with different numbers of triples. We divide the sentences in test sets into 5 sub-classes. Each class contains sentences that have 1, 2, 3, 4 or $\geq$5 triples. The results are shown in Table \ref{num_reulst}. In general, our proposed model achieves the best results in all sub-classes. Besides, we observe that though the our proposed model gains considerable improvements on all five sub-classes compared to the SoTA model \cite{wei-etal-2020-novel}, the greatest improvement of F1 score on the two datasets both come from the most difficult sub-class (N$\geq$5), in particular, there is 6.9\% improvement in the NYT data. Such results indicate that our proposed model is more suitable for complicated scenarios than the current SoTA model.
\subsection{Detailed Results on Different Overlapping Patterns}
Finally, to address  the research question \textbf{RQ4}, we conduct further experiments on NYT dataset to verify the ability of our proposed model in handling the overlapping problem.  Figure \ref{overlap} shows the results of our proposed model and baseline models in Normal, Single Entity Overlap (SEO) and Entity Pair Overlap (EPO) classes.

Overall, our proposed model performs better than all baseline models in all three classes.  In details, there are 3.5\%, 2.6\% and 2.1\% improvements compared with the SoTA model \cite{wei-etal-2020-novel} in Normal, SEO and EPO classes, respectively. Such results show that our proposed model is very effective in handling the overlapping problem, which is widely existed in joint entity and relation extraction. In addition,  We also observe that the performance of all seq2seq based models, such as CopyRE \cite{zeng2018extracting} and CopyRRL\cite{zeng2019learning}, on Normal, EPO and SEO presents a decreasing trend, which indicates that the Normal class presents a relatively easiest pattern while EPO and SEO classes are the relatively harder ones for these seq2seq based models to extract. In contrast, our
proposed model attains consistently strong performance over all three overlapping patterns.
\begin{figure}[t]
  	\begin{center} \includegraphics*[clip=true,width=0.47\textwidth,height=0.22\textheight]{graph/overlap_nyt_v7.pdf}
  	\caption{F1 score of extracting relational triples from sentences with different overlapping pattern in NYT dataset.} \label{overlap}
  \end{center}
  \end{figure}

\section{Conclusion and Future Work}
In this paper, we introduce set prediction networks for joint entity and relation extraction. Compared with previous seq2seq based models, We formulate the  joint entity and relation extraction task as a set prediction problem. In such a way, the extraction model will be relieved of predicting the extraction order of multiple triples. To solve the set prediction problem, We combine non-autoregressive parallel decoding with bipartite matching loss function. We conduct extensive experiments on two widely used datasets to validate the effectiveness of the proposed set prediction networks. Experimental results show that our proposed networks outperforms state-of-the-art baselines over different scenarios. This challenging task is far from being solved. We find that relation types exhibit an imbalanced or long-tailed distribution in NYT dataset and WebNLG dataset. Our future work will concentrate on how to combine cost-sensitive learning with the proposed set prediction networks.


\section{Introduction}
\label{sec:Introduction}
\input{tex/Introduction}

\section{Related Work}
\label{sec:RelatedWork}
\input{tex/RelatedWork}

\section{The Proposed QOCE Method}
\label{sec:ProposedMethod}
\input{tex/ProposedMethod}

\section{Experimental Results}
\label{sec:Experiments}
\input{tex/Experiments}

\section{Conclusion}
\label{sec:Conclusion}
\input{tex/Conclusion}

\bibliographystyle{IEEEtran}

\subsection{Synthetic Networks.}~
For synthetic datasets, we use the LFR benchmark networks \cite{lancichinetti2008benchmark}. The LFR benchmark graphs have a built-in binary community structure, which simulates the property of real-world networks on the heterogeneity of node degrees and community size distribution.

\begin{table}[htbp]
    \setlength{\abovecaptionskip}{0pt}
	\setlength{\belowcaptionskip}{5pt}
	\caption{Parameters for the LFR benchmark networks.}
	\label{tab:lfr}
	\centering
	\scalebox{0.8}
	{
	\begin{tabular}{l|l}
	\hline
	Parameter & Description\\
	\hline
	$n=5,000$ & number of nodes in the network\\
	$\mu = 0.3$ & mixing parameter\\
	$\bar d = 10$ & average degree of the nodes\\
	$d_{max} = 50$ & maximum degree of the nodes \\
	$s:[10,50], b:[20,100]$ & range of the community size \\
	$\tau_1 = 2$ & node degree distribution exponent\\
	$\tau_2 = 1$ &community size distribution exponent \\
	$om \in \{2,3...,8\}$ &overlapping membership\\
	$on \in \{500, 2500\}$& number of overlapping nodes\\
	\hline
	\end{tabular}
	}
\end{table}

We adopt the standard LFR parameter settings used in the survey of overlapping community detection~\cite{xie2013overlapping} and generate four groups with a total of 28 LFR benchmark networks. Our parameter settings are summarized in Table \ref{tab:lfr}. The four groups of LFR networks are distinguished by the range of community size ($s$ or $b$) and the number of overlapping nodes ($on=500$ or $2500$). For each group, we vary the overlapping membership $om$ from 2 to 8 to generate seven networks. Denote these groups by $\text{LFR}\_\{s,b\}\_on/n$ and networks by $\text{LFR}\_\{s,b\}\_on/n\_om$, such as $\text{LFR}\_s\_0.5$ for the group $\{s:[10,50],~on=2500,~om=\{2,3...,8\}\}$ and $\text{LFR}\_s\_0.5\_2$ for the network $\{s:[10,50],~on=2500,~om=2\}$.

\subsection{Real-world Networks.}~
We consider six real-world network datasets with labeled ground-truth in various domains. The TerroAttack and TerroristRel networks~\cite{zhao2006entity} are related to terrorist attacks and terrorist organizations, respectively. The Polbooks is a network of books about U.S. politics from the 2004 U.S. presidential election\footnote{http://orgnet.com} taken from Amazon.com. Polblogs is a network of hyperlinks between weblogs on U.S. politics, recorded in 2005 by Adamic and Glance \cite{adamic2005political}. Additionally, two well-known large networks called Amazon and DBLP are from the SNAP website\footnote{http://snap.stanford.edu/}.

\begin{table}[htbp]
    \setlength{\abovecaptionskip}{0pt}
	\setlength{\belowcaptionskip}{5pt}
	\caption{Some statistics of real-world datasets.}
	\label{tab:real}
	\centering
	\scalebox{0.85}
	{
	\begin{threeparttable}
	\begin{tabular}{l | r r r r}
	\hline
	Network & \#Nodes & \#Edges & \#Comms  & $\overline{|C|}^{*}$ \\
	\hline
	TerrorAttack	& 51	& 1,178	& 2		& 24.000 \\
	TerroristRel	& 665	& 6552	& 21	& 30.619 \\
	Polbooks		& 105	& 441	& 4		& 26.000 \\
	polblogs		& 1222	& 16714	& 3		&398.333 \\
	Amazon		& 334,863	& 925,872	& 75,149	& 30.000 \\
	DBLP		& 317,080	& 1,049,866	& 13,477	& 53.000 \\
	\hline
	\end{tabular}
	\begin{tablenotes}
		\footnotesize
		\item[*] $\overline{|C|}$ denotes the average size of communities in the network.
	\end{tablenotes}
	\end{threeparttable}
	}
\end{table}

As some of the labeled communities in these networks are disconnected, we preprocess all the datasets as follows: The datasets are first made undirected and unweighted, and the largest connected component (LCC) is extracted. For each dataset, we confine each labeled community to a subset of its members inside this LCC. For any disconnected community,  we separate into the connected components, and regard each such connected component with at least three nodes as a separate ground-truth community. Table \ref{tab:real} summarizes the statistics of the six real-world networks and their ground-truth communities after data cleaning process.

\begin{figure*}[htbp]
    \centering
    \subfigure[$\text{LFR}\_s\_0.1$]{
    \includegraphics[width=1.5in]{figs/F1_s_1.png}
    }
    \subfigure[$\text{LFR}\_s\_0.5$]{
    \includegraphics[width=1.5in]{figs/F1_s_5.png}
    }
    \subfigure[$\text{LFR}\_b\_0.1$]{
    \includegraphics[width=1.5in]{figs/F1_b_1.png}
    }
    \subfigure[$\text{LFR}\_b\_0.5$]{
    \includegraphics[width=1.5in]{figs/F1_b_5.png}
    }
    \vspace{-1em}
    \caption{Comparison on the average F1-score on 28 LFR benchmark networks in four groups.}
    \label{Fig:lfr_f1}
    \vspace{-1em}
\end{figure*}

\subsection{Baseline Methods.}~
We select four state-of-the-art overlapping community detection algorithms as the baseline methods.

\begin{itemize}
\setlength{\itemsep}{0pt}
\setlength{\parsep}{0pt}
\setlength{\parskip}{0pt}
	\item \textbf{DEMON}~\cite{coscia2012demon}. DEMON is a local-first approach, which lets each vertex vote for the surrounded communities in its limited view of the global system using a label propagation algorithm, and then it merges the local communities into a global collection.
	\item \textbf{BIGCLAM}~\cite{yang2013overlapping}. BIGCLAM is a nonnegative matrix factorization based model, which builds on an observation that overlaps between communities are densely connected.
    \item \textbf{NISE}~\cite{whang2016overlapping}. NISE is a seed set expansion algorithm that develops a seeding strategy based on neighborhood-inflated for a personalized PageRank scheme that optimizes the conductance score of communities.
	\item \textbf{DNMF}~\cite{ye2019discrete}. DNMF is a nonnegative matrix factorization based model, but it seeks for a discrete community membership matrix for overlapping community detection directly.
\end{itemize}

\vspace{-1em}
\subsection{Evaluation Metric.}~
For evaluating the performance of the community detection algorithms on labeled datasets, we consider metrics that quantify the similarity between the detected communities and the ground-truth communities. Given a set of detected communities $\mathcal{C}=\{C_1, C_2, ..., C_{|\mathcal{C}|}\}$ and a set of ground-truth communities $\mathcal{C}^*=\{C_1^*, C_2^*, ..., C_{|\mathcal{C}^*|}^*\}$, we consider the following metric to measure the similarity between $\mathcal{C}$ and $\mathcal{C}^*$.

\textbf{Average F1-score}~\cite{yang2013overlapping}.~
For each detected community $C_i \in \mathcal{C}$, find the most similar ground-truth community and quantify the similarity by F1-score. Then, for each ground-truth community $C_i^* \in \mathcal{C}^*$, also find the most similar detected community and compute the F1-score. Formally, the average F1-score is defined as:
\begin{equation}\nonumber
\frac{1}{2|\mathcal{C}^*|} \sum_{C_i^* \in \mathcal{C}^*} \max_{C_j\in \mathcal{C}} F_1(C_i^*, C_j) + \frac{1}{2|\mathcal{C}|} \sum_{C_i \in \mathcal{C}} \max_{C_j^* \in \mathcal{C}^*} F_1(C_i,C_j^*),
\end{equation}
where the F1-score between two communities is
$$F_1(C_i, C_j) = \frac{2|C_i \cap C_j|}{C_i| + |C_j|}.$$

\subsection{Accuracy Comparison on LFR Benchmark Networks.}~
For the four competitive baselines, we use codes provided by the authors. Note that the number of seeds $k$ in NISE and the number of communities $k$ in BIGCLAM and DNMF are hyperparameters. We set $k$ to 200, which is also the number of communities for most ground-truth for all the LFR benchmark networks. Other hyperparameters are set as default values according to their guidelines.

Figure \ref{Fig:lfr_f1} shows the accuracy evaluated by the average F1-score of our QOCE method and the baselines on the 28 LFR benchmarks in four groups. Regarding the average F1-score, QOCE outperforms BIGCLAM, DEMON, and NISE on all the LFR benchmark networks. As for the comparison with DNMF, in general, the average accuracy of QOCE is slightly better than that of DNMF. The average F1-score of QOCE is higher than DNMF on 15 networks and lower than DNMF on 13 networks.
DNMF works slightly better on relatively highly overlapping networks, and QOCE works better on somewhat less overlapping networks. Nevertheless, we will see in the next subsection that DNMF can not scale to large real-world networks.

QOCE detects communities through seed set expansion, and each clique seed set generates one community. When a node belongs to more communities (i.e., the $om$ is larger), it usually has more edges, which means the node would belong to a particular maximal clique and becomes a clique seed set. Thus, the number of detected communities to which a highly overlapping node belongs is usually smaller than that of ground-truth communities to which the node belongs. This phenomenon may explain why our method's accuracy decreases faster than DNMF when $om$ increases.

\begin{figure*}
    \centering
    \subfigure[Joint effects of $t_0$ and $\mu$]{
    \includegraphics[width=2.4in]{figs/t0_mu.png}
    }
    \subfigure[Effects of $\alpha$]{
    \includegraphics[width=1.8in]{figs/alpha.png}
    }
    \subfigure[Effects of $w$]{
    \includegraphics[width=1.8in]{figs/w.png}
    }
    \vspace{-1em}
    \caption{Sensitive study of the parameters.}
    \label{Fig:parameters}
    \vspace{-1em}
\end{figure*}

\subsection{Accuracy Comparison on Real-world Networks.}~
We set the key parameter $k$ of some baselines in different values favorable to these baselines for comparisons on real-world data. For small and medium-scale networks such as TerrorAttack, TerroristRel, polbooks, and polblogs, since the number of ground-truth communities is small, the hyperparameter $k$ in BIGCLAM is set as $-1$ (detect automatically), while the $k$ in NISE and DNMF (which do not support automatic detection) is set as 10. For large networks such as Amazon and DBLP, as in \cite{whang2016overlapping}, we set parameter $k$ in BIGCLAM, NISE, and DNMF as 25,000. Other hyperparameters are still set by their default values.

\begin{table}[htbp]
    \setlength{\abovecaptionskip}{0em}
	\setlength{\belowcaptionskip}{1em}
	\caption{Comparison on the average F1-score on real-world networks.}
	\label{tab:real_f1}
	\centering
	\scalebox{0.7}
	{
	\begin{threeparttable}
	\begin{tabular}{l | c c c c c}
	\hline
	\textbf{Network}	& \textbf{BIGCLAM}	& \textbf{DEMON}	& \textbf{NISE}	& \textbf{DNMF}	& \textbf{QOCE} \\
	\hline
	TerrorAttack	& 0.438 	& \textbf{0.635}	& 0.429	& 0.346	& \underline{0.615} \\
	TerroristRel	& 0.453 	& \textbf{0.557}	& 0.462	& 0.417	& \underline{0.473} \\
	polbooks	& 0.470 	& 0.675	& \underline{0.714}	& 0.482	& \textbf{0.749} \\
	polblogs	& 0.321 	& 0.438	& \textbf{0.647}	& 0.333	& \underline{0.564} \\
	Amazon	& 0.423	& \underline{0.442}	& 0.338	& NaN*	& \textbf{0.473} \\
	DBLP	& \underline{0.355}	& 0.242	& 0.242	& NaN*	& \textbf{0.379} \\
	\hline
	\end{tabular}
	\begin{tablenotes}
		\footnotesize
		\item[*] out of memory.
	\end{tablenotes}
	\end{threeparttable}
	}
	\vspace{-1em}
\end{table}

Table \ref{tab:real_f1} shows the accuracy evaluated by the average F1-score of QOCE and the baselines on six real-world networks. As Table \ref{tab:real_f1} shows, QOCE always performs the best or the second-best in terms of the average F1-score, and QOCE performs better on larger networks. Note that DNMF cannot scale to large networks due to its excessive space overhead. When running on the Amazon network, DNMF requires 835.5GB memory to load the adjacency matrix.

\begin{figure}
    \centering

    \includegraphics[width=3.2in]{figs/LFR_time.png}

    \vspace{-2em}
    \caption{The running time comparison on LFR benchmark networks.

    Note that there is average running time on each of four groups of LFR networks. e.g., the group $\text{LFR}\_b\_0.5$ in the bar represents the average running time of different methods on the seven networks in Group $\text{LFR}\_b\_0.5$.
    }
    \label{Fig:time}
    \vspace{-1em}
\end{figure}

\subsection{Comparison on Running Time.}~
DEMON only supports sequential execution, BIGCLAM, NISE, and QOCE can be executed in parallel with multiple threads, and DNMF can be accelerated by the parallel matrix operation built in MATLAB. We set the number of threads for BIGCLAM, NISE, DNMF, QOCE to 20, and DEMON executes serially for all networks. Since these methods are implemented in different programming language, the comparison is for reference only.

Figure \ref{Fig:time} illustrates the running time of different methods on LFR benchmark networks and real-world networks. On LFR benchmark networks, QOCE has a similar average running time with NISE, and runs much faster than DNMF. BIGCLAM, which is implemented in C++, has the shortest running time.
Furthermore, these methods show a similar trend on real-world networks, DNMF is always the slowest method and runs out of memory on Amazon and DBLP.

\subsection{Sensitive Analysis on Parameters.}~
We also analyze the parameter sensitivity of QOCE on $\text{LFR}\_s\_0.1\_5$. Similar results can be observed on other networks. There are a total of four hyperparameters in QOCE, including the random walk step $t_0$, the random walk threshold $\mu$, the trade-off parameter $\alpha$, and the window size $w$, as shown in Algorithm \ref{alg:qoce}.

The random walk step $t_0$ and threshold $\mu$ jointly control the size of the subgraph. We fixed $\alpha=0.2$ and $w=5$, and evaluate QOCE with the average F1-score by varying $t_0$ in [1,10] and $\mu$ in [0,0.01] simultaneously. The results are presented in Figure \ref{Fig:parameters} (a). We can see that QOCE performs poorly when $t_0=1$, because the subgraph obtained by one-step random walk sampling is too small to extract the community. Similarly, when $t_0$ and $\mu$ increase, the average probability of the vertices decreases, and the threshold is increased, which means the subgraph is too small to extract the proper community. Meanwhile, when $\mu$ takes 0 as the default setting, QOCE performs best and is robust to $t_0$.

The trade-off parameter $\alpha$ effects the value of affiliation vector $\mathbf{y}$. We obtain the effects of $\alpha$ by fixed $t_0=3, \mu=0, w=5$ and varying $\alpha$ in [0,1], and present it in Figure \ref{Fig:parameters} (b). We can observe that the performance of QOCE decreases slightly with the increase of $\alpha$, and the decline is less than 0.16. When $\alpha$ takes 0.1 or 0.2 (same as default), QOCE shows the best performance.

The window size $w$ controls the size of the detected communities. We fixed $t_0=3, \mu=0, \alpha=0.2$ and varying $\alpha$ in [1,10]. The effects of $w$ are illustrated in Figure \ref{Fig:parameters} (c). Obviously, QOCE is not sensitive to $w$, especially when $w \geq 3$, the average F1-score hardly changes and reaches the optimal.

\subsection{Seeding.}
In this phase, we first enumerate all maximal cliques in graph $G$, and then select high-quality maximal cliques to form the initial seed sets $\mathcal{S}$. A \textit{clique} is a complete subgraph such that every two distinct vertices are connected. A \textit{maximal clique} is a clique that is not contained in any larger clique.

In general, enumerating all maximal cliques in a graph is computationally expensive, however, maximal cliques can be found quickly in graphs that are sufficiently sparse. To this end, our implementation apply the Bron-Kerbosch (BK) algorithm \cite{bron1973algorithm}, a recursive backtracking algorithm, to efficiently find all maximal cliques with at least four vertices. To speedup the computation, before applying the BK algorithm, we introduce a preprocessing procedure to recursively remove vertices with degree less than three to obtain $k-$\textit{cores} ($k = 3$) in the graph. For these $k-$cores, we run the BK algorithm sequentially or in parallel.

For ``high-quality"  maximal cliques, we mean they are large in sizes and do not overlap with each other heavily. If highly overlapping maximal cliques are all treated as seeds, we are likely to obtain almost duplicate communities. Therefore, we employ a simple filtering method to exclude highly overlapping maximal cliques. In particular, we first sort all maximal cliques by sizes in the non-ascending order, and then remove subsequent cliques with at least $75\%$ (which is an appropriate threshold for seed exclusion, and also adopted by \cite{lee2010detecting}) of vertices contained in any previous clique.

\subsection{Sampling.}

In large networks, performing seed set expansion in the entire graph is computationally expensive. Inspired by the work of local community detection~\cite{HeSBH/TKDD2019}, which only cares about finding the local community of a given seed set and does local sampling to reduce the subsequent computational overhead, we do a local sampling from each clique seed set to reduce the subsequent calculation. Due to the ``local" property of a community, that is, a vertex will not go too far in reaching other vertices in its community, as the \textit{diameter} of the community (i.e., the maximum pairwise distance among vertices) are usually small.
To sample a subgraph covering the community, we could do short random walks from each clique seed set.

Given a clique seed set $S \in \mathcal{S}$, for which we hope to find a community, the initial probability distribution vector $\mathbf{p}_0$ is defined by:
\begin{equation}
\mathbf{p}_0(v) =
\begin{cases}
	\mathbf{d}(v)/\text{Vol}(S) & \text{if} ~v\in S, \\
	0 & \text{otherwise}.
\end{cases}
\label{Eq:init_prob}
\end{equation}
Here $\mathbf{d}(v)$ is the degree of vertex $v$ and $\text{Vol}(S)$ is the total degree of the vertices in $S$.

In order to retain some probability at the current vertex, we adopt lazy random walk, and the transition matrix is as follows:
\begin{equation}
\mathbf{N_{rw}} = (\mathbf{D} + \mathbf{I})^{-1} (\mathbf{A} + \mathbf{I}),
\label{Eq:tran_matrix}
\end{equation}
where the degree matrix $\mathbf{D} \in \mathbb{Z}^{|\mathcal{V}| \times |\mathcal{V}|}$ is defined as a diagonal matrix whose $i\text{-th}$ diagonal entry is $\sum_j a_{ij}$, and the identity matrix $\mathbf{I}$ is of order $|\mathcal{V}|$.
So we can calculate the probability distribution vector of $t$-step lazy random walks by:
\begin{equation}
\mathbf{p}_{t} = (\mathbf{N_{rw}} ^ T)^{t} \mathbf{p}_0.
\label{Eq:new_prob}
\end{equation}

It is a typical approach to obtain the probability distribution $\mathbf{p}_{t}$ by (\ref{Eq:new_prob}). However, it is unpractical to compute on the transition matrix $\mathbf{N_{rw}}$ for a large graph. We implement a fast method to gain $\mathbf{p}_{t}$ and the corresponding sampling graph. See details in Algorithm \ref{alg:random_walk}, where $N(s_i)$ denotes the neighbourhood (set of adjacent vertices) of vertex $s_i$ in $G$.

\begin{algorithm}
\begin{algorithmic}[1]
\REQUIRE Graph $G = (\mathcal{V},\mathcal{E})$, clique seed set $S \in \mathcal{S}$, number of steps $t_0$, and threshold $\mu$
\ENSURE Sampled subgraph $G_s = (\mathcal{V}_s, \mathcal{E}_s)$
\STATE  Initialize $t = 0$, $\mathbf{p}_0$ by (\ref{Eq:init_prob})
\WHILE {($t < t_0$)}
\STATE $U = \emptyset$
\STATE $\mathbf{p}_{t+1} = \mathbf{0}$
\FOR{each $s_i \in S$}
\STATE $U_i = N(s_i)$
\STATE $\mathbf{p}_{t+1}(s_i) = \mathbf{p}_{t+1}(s_i) + \mathbf{p}_t(s_i)/(|U_i|+1)$
\FOR {each $v_i \in U_i$}
\STATE $\mathbf{p}_{t+1}(v_i) = \mathbf{p}_{t+1}(v_i) + \mathbf{p}_t(s_i)/(|U_i|+1)$
\ENDFOR
\STATE $U = U \cup U_i \cup {s_i}$
\ENDFOR
\STATE $S = U$
\STATE $t = t + 1$
\ENDWHILE
\STATE $\mathcal{V}_s \leftarrow$ \text{vertices whose entry value $> \mu$ in} $\mathbf{p}_{t_0}$
\STATE $G_s = (\mathcal{V}_s,\mathcal{E}_s)$ is the induced subgraph from $\mathcal{V}_s$
\caption{Fast random walk sampling}
\label{alg:random_walk}
\end{algorithmic}
\end{algorithm}

For each clique seed set $S$ in seed sets $\mathcal{S}$, we sample a comparatively small subgraph $G_s$ by Algorithm \ref{alg:random_walk}. This procedure can be completed in milliseconds for large networks with millions of vertices. All subsequent procedures are then carried on subgraph $G_s$, rather than on the entire graph $G$, which significantly reduces the computational overhead.

\subsection{Extraction.}
To extract a community $C$ with most sparse external links from $G_s=(\mathcal{V}_s, \mathcal{E}_s)$, we employ the Cheeger cut \cite{chung1997spectral} and derive the following optimization problem:
\begin{equation}
\min_{C \subset \mathcal{V}_s} \psi(C) = \frac{\text{cut}(C,\overline{C})}{\text{min}\{|C|,|\overline{C}|\}},
\label{Eq:ori_opt}
\end{equation}
where vertex set $\overline{C} = \mathcal{V}_s / C$, and $\text{cut}(C, \overline{C})$ denotes the number of edges between $C$ and $\overline{C}$.

Let $\mathbf{L}_s = \mathbf{D}_s - \mathbf{A}_s$ be the Laplacian matrix of $G_s$ where $\mathbf{A}_s$ and $\mathbf{D}_s$ are the adjacency matrix and the diagonal degree matrix of $G_s$, respectively.
Let $\mathbf{y} \in \{0,1\}^{|\mathcal{V}_s|}$ be an affiliation vector with each entry $\mathbf{y}_i$ representing whether vertex $v_i$ belongs to the detected community $C$. Then, $\mathbf{y}^T \mathbf{y}$, $\mathbf{y}^T \mathbf{D}_s \mathbf{y}$, and $\mathbf{y}^T \mathbf{A}_s \mathbf{y}$ can be respectively treated as the number of vertices, the total degree of vertices, and two times the number of internal edges in $C$~\cite{HeSBH/TKDD2019}. So $\text{cut}(C,\overline{C}) = \mathbf{y}^T \mathbf{D}_s \mathbf{y} - \mathbf{y}^T \mathbf{A}_s \mathbf{y} = \mathbf{y}^T \mathbf{L}_s \mathbf{y}$.

Community $C$ is relatively small in the sampled graph $G_s$, which means $|C| < \frac{1}{2}|\mathcal{V}_s|$. Then the Cheeger cut $\psi(C)$ could be written as a Rayleigh quotient, and the problem in (\ref{Eq:ori_opt}) could be rewritten as follows:
\begin{equation}
\begin{aligned}
\min_{\mathbf{y}} ~&~ \frac{\mathbf{y}^T \mathbf{L}_s \mathbf{y}}{\mathbf{y}^T \mathbf{y}} \\
\emph{s.t.} ~&~ y_i \in \{0,1\} ~~ \forall v_i \in \mathcal{V}_s,
\end{aligned}
\label{Eq:int_opt}
\end{equation}
where $y_i$ denotes the $i\text{-th}$ entry of the affiliation vector $\mathbf{y}$, and $v_i$ denotes the $i\text{-th}$ vertex in $G_s$.

Due to the constraint on $\mathbf{y}$, (\ref{Eq:int_opt}) is a 0-1 integer programming problem that is NP-complete. We relax $\mathbf{y}$ from $\{0,1\}^{|\mathcal{V}_s|}$ to  $[0,1]^{|\mathcal{V}_s|}$, and note that $\mathbf{y}^T \mathbf{y} = \mathbf{e}^T \mathbf{y}$ where vector $\mathbf{e}$ is $\mathbf{1}$. Thus, we relax the 0-1 integer programming problem to the following quadratic optimization problem:
\begin{equation}
\begin{aligned}
\min_{\mathbf{y}} ~&~ \mathbf{y}^T \mathbf{L}_s \mathbf{y} \\
\emph{s.t.} ~&~ \mathbf{e}^T \mathbf{y} = 1, \\
~&~ y_i \in [0,1] ~~ \forall v_i \in \mathcal{V}_s.
\end{aligned}
\label{Eq:quad_opt}
\end{equation}

There is a trick that the first constraint in (\ref{Eq:quad_opt}) can be regarded as an regulation term in the objective function. Expecting the detected community $C$ to contain the seed set $S$, we also add a new constraint to this optimization problem. Finally, the quadratic optimization problem in (\ref{Eq:quad_opt}) can be rewritten as follows:
\begin{equation}
\begin{aligned}
\min_{\mathbf{y}} ~&~ \mathbf{y}^T \mathbf{L}_s \mathbf{y} + \alpha \mathbf{e}^T \mathbf{y} \\
\emph{s.t.} ~&~ y_i \in [0,1] ~~ \forall v_i \in \mathcal{V}_s, \\
~&~ y_i \geq \frac{1}{|S|} ~~ \forall v_i \in S,
\end{aligned}
\label{Eq:final_opt}
\end{equation}
where parameter $\alpha$ is added to balance the two terms

The quadratic programming problem in (\ref{Eq:final_opt}) can be efficiently solved by interior point method~\cite{altman1999regularized}. The optimal solution $\mathbf{y}^*$ is the affiliation between the community $C$ and all vertices in $G_s$.

\subsection{Post-processing.}
The resulting $\mathbf{y}^*$ is a soft community membership with each entry $y^*_i$ representing the probability of vertex $v_i$ belonging to community $C$. In order to obtain the ultimate community membership, we need to post-process $\mathbf{y}^*$. Generally, the post-processing is to specify a threshold on $\mathbf{y}^*$ manually, but it is not a desirable approach \cite{ye2019discrete}. We introduce the conductance metric to determine the community boundary.

\begin{Definition}[Conductance]
For a subgraph $C$ whose vertex set $V_C \subset V_s$, its conductance \cite{kannan2004clusterings} is:
\begin{equation} \nonumber
\label{Eq:cond}
\Phi(C) = \frac{\text{cut}(C,\overline{C})}{\text{min}\{\text{Vol}(C),\text{Vol}(\overline{C})\}},
\end{equation}
where $\text{Vol}(C)$ denotes the total degree of vertices inside subgraph $C$.
\label{Def:cond}
\end{Definition}

We first sort the vertices based on the entry values of $\mathbf{y}^*$ in non-ascending order. Suppose the sorted sequence is $\{ v_1, v_2, ..., v_{|\mathcal{V}_s|} \}$. For each integer $k \in \{1,..., |\mathcal{V}_s|\}$, we extract a vertex set from $G_S$ with the first $k$ vertices in the sorted sequence, denoted by $\hat{C}_k = \{v_i|i<=k\}$. Then for each vertex set $\hat{C}_k$, we compute its conductance $\Phi(\hat{C}_k)$, and a vertex set $\hat{C}_{k^*}$ with the first local minimum conductance is the desired community $C$.

\iffalse
However, we observe that the algorithm does not perform well, and the detected communities are sometimes too large, covering almost half of the sampled subgraph. This is because when community $\hat{C}_{k}$ is about to cover half of the entire sampled graph $G_s$, $\text{Vol}(\hat{C}_{k})$ is almost equal to $\text{Vol}(\overline{\hat{C}_{k}})$, and the denominator of $\Phi(\hat{C}_{k})$ is the maximum while $\Phi(\hat{C}_{k})$ reach the minimum. Take the conductance of the vertex set shown in Figure \ref{Fig:cond} as an example: when taking the local minimum conductance, the size of the detected community is more reasonable than taking a global minimum conductance.

\begin{figure}
\centering
\includegraphics[width = 3in]{figs/conds.png}
\caption{An example on the conductance of vertex set $\hat{C}_{k}$ on $\text{LFR}\_s\_0.5\_2$ (described in Section \ref{sec:Experiments}). The global minimum appears at $k = 1915$, which covers almost a half of the sampled graph $G_s$ ($|\mathcal{V}_s|=4099$). The local minimum appears at $k = 13$, which is close to the size of the ground-truth community.}
\label{Fig:cond}
\end{figure}

To escape this dilemma, we adopt a local minimum instead of the global minimum,
as shown in Algorithm \ref{alg:post_proc}. After the modification, the size of the detected community $C$ is closer to that of the ground-truth community. However, it also reduces much unnecessary computational overhead on the conductance. Furthermore, we introduce a window $w$ to ensure $\Phi(\hat{C}_{k^*})$ is the minimum in $\{ \Phi(\hat{C}_1), \Phi(\hat{C}_2),...,\Phi(\hat{C}_{k^*}),\Phi(\hat{C}_{k^*+1}),...,\Phi(\hat{C}_{k^*+w}) \}$, which avoids short-term fluctuation of conductance.
\fi

The method of finding a local minimal conductance of the community is shown in Algorithm \ref{alg:post_proc}.
Empirical observation shows that not only the size of the community obtained by a local minimum is closer to the size of the ground-truth community than that obtained by the global minimum, but also a lot of unnecessary computational overhead is saved compared with the global minimum. Furthermore, we introduce a window $w$ to ensure $\Phi(\hat{C}_{k^*})$ is the minimum in $\{ \Phi(\hat{C}_1), \Phi(\hat{C}_2),...,\Phi(\hat{C}_{k^*}),\Phi(\hat{C}_{k^*+1}),...,\Phi(\hat{C}_{k^*+w}) \}$, which avoids short-term fluctuation of conductance.

\begin{algorithm}
\begin{algorithmic}[1]
\REQUIRE Sampled graph $G_s=(\mathcal{V}_s, \mathcal{E}_s)$, affiliation vector $\mathbf{y}^*$, window size $w$
\ENSURE Detected community $C$
\STATE Sort vertices in $\mathcal{V}_s$ by the corresponding values in $\mathbf{y}^*$ in non-ascending order, the sorted sequence is $\{ v_1, v_2, ..., v_{|\mathcal{V}_s|} \}$
\FOR {$k = 1:w$}
\STATE Calculate $\Phi(\hat{C}_k)$ by Definition \ref{Def:cond}
\ENDFOR
\STATE $k = 0, n = 0$
\WHILE {$n < w$}
\STATE $k = k + 1$
\STATE Calculate $\Phi(\hat{C}_{k+w})$ by Definition \ref{Def:cond}
\STATE $n = |\{\hat{C}_i|\Phi(\hat{C}_i)>\Phi(\hat{C}_k), \forall i, k < i \leq k+w\}|$
\ENDWHILE
\STATE $C = \{v_j | 1 \leq j \leq k\}$
\caption{Post-processing}
\label{alg:post_proc}
\end{algorithmic}
\end{algorithm}

Based on the above four phases, the overall Quadratic Optimization based Clique Expansion (QOCE) algorithm is shown in Algorithm \ref{alg:qoce}.

\begin{algorithm}
\begin{algorithmic}[1]
\REQUIRE $G=(\mathcal{V}, \mathcal{E})$,
         random walk steps $t_0$,
         random walk threshold $\mu$
         trade-off parameter $\alpha$,
         and window size for post-processing $w$
\ENSURE A set of detected communities $\mathcal{C}$
\STATE Get $k-$cores ($k = 3$) in $G$
\STATE Find all maximal cliques $\mathcal{\hat{S}}$ by BK algorithm \cite{bron1973algorithm}
\STATE Get seed sets $\mathcal{S}$ by excluding highly overlapping cliques from $\mathcal{\hat{S}}$
\STATE $\mathcal{C} = \emptyset$
\FOR {each clique seed set $S \in \mathcal{S}$}
\STATE Sample $G_s = (\mathcal{V}_s,\mathcal{E}_s)$ from $S$ by Algorithm~\ref{alg:random_walk}
\STATE Obtain affiliation vector $\mathbf{y}^*$ by solving (\ref{Eq:final_opt})
\STATE Detect a community $C$ by Algorithm \ref{alg:post_proc}
\STATE $\mathcal{C} = \mathcal{C} \cup \{C\}$
\ENDFOR
\caption{The QOCE algorithm}
\label{alg:qoce}
\end{algorithmic}
\end{algorithm}

\subsection{Time Complexity Analysis.}
For the maximal clique enumeration, we adopt the BK algorithm \cite{bron1973algorithm} with complexity $O(d|\mathcal{V}|3^{d/3})$, where $d$ is the degeneracy of the graph ($d<<|\mathcal{V}|$ in sparse networks).
The preprocessing of removing edges to get $k-$cores ($k = 3$) is $O(|\mathcal{V}|)$.
And maximal cliques filtering is $O(|\mathcal{S}|^2)$. The complexity of fast random walk, scaled with the output size of each sampled subgraph, is $|\mathcal{V}_s|$. So the total complexity of the sampling is $O(\sum_{S\in\mathcal{S}} |\mathcal{V}_s|)$.

In the extraction phase, we employ interior point method \cite{altman1999regularized} to solve the quadratic optimization problem, in which the variable is an affiliation vector $\mathbf{y} \in [0,1]^{|\mathcal{V}_s|}$. And the interior point method requires $O(nL)$ iterations, where $n$ is the dimension of variable $\mathbf{y}$ in (\ref{Eq:final_opt}), that is $n=|\mathcal{V}_s|$, and $L$ is the length of a binary coding of the input data in problem (\ref{Eq:final_opt}), that is $L=\sum_{i=0}^{|\mathcal{V}_s|} \sum_{j=0}^{\mathcal{V}_s} (\lceil \log_2 (|L_{ij}| + 1) + 1 \rceil) + |S| \lceil \log_2 (\frac{1}{|S|} + 1) + 1 \rceil + (|\mathcal{V}_s| - |S|) \lceil \log_2 (0 + 1) + 1 \rceil$, in which $L_{ij}$ is the entry of the Laplacian matrix $\mathbf{L}_s$ and its value is usually equal to 0 in sparse networks. Thus, $L= |\mathcal{V}_s|^2 + |S| + |\mathcal{V}_s|$ for each subgraph, and the complexity of each extraction is $O(|\mathcal{V}_s|^3)$. The total complexity of this phase is $O(\sum_{S \in \mathcal{S}} |\mathcal{V}_s|^3)$.

Finally, our post-processing first sorts entries of the affiliation vector with complexity $O(|\mathcal{V}_s|log|\mathcal{V}_s|)$, then searches for the top $k$ vertices with local minimum conductance which is output-sensitive procedure with complexity $O(|C|)$. Note that the community is extracted from the sampled subgraph, $C \in \mathcal{V}_s$, the total complexity of this phase is $O(\sum_{S\in\mathcal{S}} |\mathcal{V}_s|log|\mathcal{V}_s|)$.

Hence, the overall complexity is $O(d|\mathcal{V}|3^{d/3} + |\mathcal{S}|^2 + \sum_{S\in\mathcal{S}} |\mathcal{V}_s|^3)$.

\subsection{Parallel QOCE.} \label{sec:parallel}
The QOCE algorithm is a pipeline architecture consisting of four phases: seeding, sampling, extraction, and post-processing. The last three phases are a series of independent operations on each clique seed set. As shown in Algorithm \ref{alg:qoce}, line $5 \sim 8$ is a loop body, and each loop is independent. So we can run these loops in parallel without dependency issues.

Therefore, we design a parallel version of QOCE. We run the remaining phases on $h$ identical machines or CPUs in parallel after the seeding phase. Specifically, we regard each seed set's remaining phases as an individual task and each machine or CPU as an individual worker. We iteratively assign a new task to a free worker until all tasks have been executed. In this way, we reduce the running time of the last three phases to almost $1/h$ of the sequential version. The complexity of parallel QOCE is $O(d|\mathcal{V}|3^{d/3} + |\mathcal{S}|^2 + \frac{1}{h} \sum_{S\in\mathcal{S}} |\mathcal{V}_s|^3)$.

Furthermore, after preprocessing, if the $k-$core ($k = 3$) is composed of multiple connected components, we also seep on each connected component in parallel.