On the quasi polynomiality of extremal homology of configuration spaces

by

Muhammad Yameen

###### Abstract

Consider the unordered configuration spaces of manifolds. Knudsen, Miller and
Tosteson proved that the extremal homology groups of configuration spaces of
manifold are eventually quasi polynomials. In this paper, we give the precise
degree of top non-trivial quasi polynomials. This shows that the upper bound
of Knudsen, Miller and Tosteson for the degree of quasi polynomials is sharp
for every manifold.

> Key Words: Configuration spaces, quasi polynomials, extremal stability
>
>
> Mathematics Subject Classification: Primary 55R80, Secondary 55P62.

##  1 Introduction

For any manifold $M$, let

$F_{n}(M):=\\{(x_{1},\ldots,x_{n})\in M^{n}|x_{i}\neq x_{j}\,for\,i\neq j\\}$

be the configuration space of $n$ distinct ordered points in $M$ with induced
topology. The symmetric group $S_{k}$ acts on $F_{k}(M)$ by permuting the
coordinates. The quotient

$B_{n}(M):=F_{n}(M)/S_{n}$

is the unordered configuration space with quotient topology.

It is well known fact that the homology groups $H_{i}(B_{n}(M);\mathbb{Q})$
are vanish for $i\geq\nu_{n},$ where $\nu_{n}=(d-1)n+1.$ In the paper [5] (see
also [6]), Knudsen, Miller and Tosteson prove that the extremal homology
groups of configuration spaces of manifold are eventually quasi polynomials:

######  Theorem 1.

Let $M$ be a manifold of even dimension $d\geq 2.$ For each $i\geq 0,$ there
is a quasi-polynomial in $n$ of degree at most dim
$H_{d-1}(M;\mathbb{Q}^{w})-1)$ and period at most 2, which coincides with dim
$H_{\nu_{n}-i}(B_{n}(M);\mathbb{Q})$ for all $n$ sufficiently large.

If $H_{d-1}(M;\mathbb{Q})=0,$ then the extremal homology groups
$H_{\nu_{n}-i}(B_{n}(M);\mathbb{Q})$ are eventually vanish. Equivalently,
Theorem 1 states that there are two polynomials $p_{M}^{\nu_{n}-i}(n)$ and
$q_{M}^{\nu_{n}-i}(n)$ such that

$Q_{M}^{\nu_{n}-i}(n)=\begin{cases}p_{M}^{\nu_{n}-i}(n)&\mbox{ $n$ is even}\\\
q_{M}^{\nu_{n}-i}(n)&\mbox{ $n$ is odd}.\\\ \end{cases}$

where $Q_{M}^{\nu_{n}-i}(n)=\mbox{dim}H_{\nu_{n}-i}(B_{n}(M);\mathbb{Q}).$ The
degree of quasi-polynomial $Q_{M}^{\nu_{n}-i}(n)$ is maximum of
$deg(p_{M}^{\nu_{n}-i}(n))$ and $deg(q_{M}^{\nu_{n}-i}(n).$ We give the
precise degree of top non-trivial quasi polynomials for every orientable
manifold.

######  Theorem 2.

Let $M$ be a closed orientable manifold of even dimension $d\geq 2.$ If
$H_{d-1}(M;\mathbb{Q})$ is non-trivial then the degree of quasi-polynomial
$Q_{M}^{\nu_{n}}(n)$ is dim$H_{d-1}(M;\mathbb{Q})-1.$

If $M$ is not closed then the homology group
$H_{\nu_{n}}(B_{n}(M);\mathbb{Q})$ is vanish. In this case, we will focus on
the homology group $H_{\nu_{n}-1}(B_{n}(M);\mathbb{Q}).$

######  Theorem 3.

Let $M$ be an orientable manifold of even dimension $d\geq 2.$ If $M$ is not
closed and $H_{d-1}(M;\mathbb{Q})$ is non-trivial then the degree of quasi-
polynomial $Q_{M}^{\nu_{n}-1}(n)$ is dim$H_{d-1}(M;\mathbb{Q})-1.$

In light of main theorems, we formulate the following conjecture:

######  Conjecture 1.

Let $M$ be an orientable manifold of even dimension $d\geq 2.$ If
$H_{d-1}(M;\mathbb{Q})$ and $Q_{M}^{\nu_{n}-i}(n)$ are non-trivial then the
degree of quasi-polynomial $Q_{M}^{\nu_{n}-i}(n)$ is
dim$H_{d-1}(M;\mathbb{Q})-1$ for $i\geq 0.$

######  Remark 1.

Drummond-Cole and Knudsen [1] computed the all Betti numbers of configuration
spaces of surfaces. From their computations, we see that the Conjecture 1 is
true for surfaces.

### Notations

$\bullet$ We work throughout with finite dimensional graded vector spaces. The
degree of an element $v$ is written $|v|$.

$\bullet$ The symmetric algebra $Sym(V^{*})$ is the tensor product of a
polynomial algebra and an exterior algebra:

$Sym(V^{*})=\bigoplus_{k\geq 0}Sym^{k}(V^{*})=Poly(V^{even})\bigotimes
Ext(V^{odd}),$

where $Sym^{k}$ is generated by the monomials of length $k.$

$\bullet$ The $n$-th suspension of the graded vector space $V$ is the graded
vector space $V[n]$ with $V[n]_{i}=V_{i-n},$ and the element of $V[n]$
corresponding to $a\in V$ is denoted $s^{n}a;$ for example

$H^{*}(S^{2};\mathbb{Q})[n]=\begin{cases}\mathbb{Q},&\text{if
$*\in\\{n,n+2\\}$}\\\ 0,&\mbox{otherwise}.\\\ \end{cases}$

$\bullet$ We write $H_{-*}(M;\mathbb{Q})$ for the graded vector space whose
degree $-i$ part is the $i$-th homology group of $M;$ for example

$H^{-*}(\text{CP}^{m};\mathbb{Q})=\begin{cases}\mathbb{Q},&\text{if
$*\in\\{-2m,-2m+2,\ldots,0.\\}$}\\\ 0,&\mbox{otherwise}.\\\ \end{cases}$

##  2 Chevalley–Eilenberg complex

Félix–Thomas [3] (see also [2]) constructed the model for rational cohomology
of unordered configuration spaces of closed orientable even dimension
manifolds. More recently, the identification was established in full
generality by the Knudsen in [4]. We will restrict our attention to the case
of orientable even dimensional manifolds.

Let us introduced some notations. Consider two graded vector spaces

$V^{*}=H^{-*}_{c}(M;\mathbb{Q})[d],\quad
W^{*}=H_{c}^{-*}(M;\mathbb{Q})[2d-1]:$

where

$V^{*}=\bigoplus_{i=0}^{d}V^{i},\quad W^{*}=\bigoplus_{j=d-1}^{2d-1}W^{j}.$

We choose bases in $V^{i}$ and $W^{j}$ as

$V^{i}=\mathbb{Q}\langle v_{i,1},v_{i,2},\ldots\rangle,\quad
W^{j}=\mathbb{Q}\langle w_{j,1},w_{j,2},\ldots\rangle$

(the degree of an element is marked by the first lower index; $x_{i}^{l}$
stands for the product $x_{i}\wedge x_{i}\wedge\ldots\wedge x_{i}$ of
$l$-factors). Always we take $V^{0}=\mathbb{Q}\langle v_{0}\rangle$. Now
consider the graded algebra

$\Omega^{*,*}_{n}(M)=\bigoplus_{i\geq
0}\bigoplus_{\omega=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\Omega^{i,\omega}_{n}(M)=\bigoplus_{\omega=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\,(Sym^{n-2\omega}(V^{*})\otimes
Sym^{\omega}(W^{*}))$

where the total degree $i$ is given by the grading of $V^{*}$ and $W^{*}$. We
called $\omega$ is a weight grading. The differential
$\partial:Sym^{2}(V^{*})\rightarrow W^{*}$ is defined as a coderivation by the
equation

$\partial(s^{d}a\wedge s^{d}b)=(-1)^{(d-1)|b|}s^{2d-1}(a\cup b),$

where

$\cup\,:H^{-*}_{c}(M;\mathbb{Q})^{\otimes 2}\rightarrow
H^{-*}_{c}(M;\mathbb{Q})$

(here $H^{-*}_{c}$ denotes compactly supported cohomology of $M$). The degree
of $\partial$ is $-1.$ It can be easily seen that $s^{d}a,\,s^{d}b\in V^{*}$
and $s^{2d-1}(a\cup b)\in W^{*}.$ The differential $\partial$ extends over
$\Omega^{*,*}_{n}(M)$ by co-Leibniz rule. By definition the elements in
$V^{*}$ have length 1 and weight 0 and the elements in $W^{*}$ have length 2
and weight 1. By definition of differential, we have

$\partial:\Omega^{*,*}_{n}(M)\longrightarrow\Omega^{*-1,*+1}_{n}(M).$

######  Theorem 4.

If $d$ is even, $H_{*}(B_{n}(M);\mathbb{Q})$ is isomorphic to the homology of
the complex

$(\Omega^{*,*}_{n}(M),\partial).$

For a closed manifold, the compactly supported cohomology is the ordinary
cohomology. In this case the two graded vector spaces are

$V^{*}=H_{-*}(M;\mathbb{Q})[d],\quad W_{*}=H_{-*}(M;\mathbb{Q})[2d-1].$

Now, we will define the dual complex of $(\Omega^{*,*}_{n}(M),\partial).$
First, we define a dual differential $D$ on $\Omega^{*,*}_{n}(M).$ The dual
differential is defined as

$D|_{V^{*}}=0,\quad D|_{W^{*}}:\,W^{*}\simeq
H_{*}(M;\mathbb{Q})\xrightarrow{\Delta}Sym^{2}(V^{*})\simeq
Sym^{2}(H_{*}(M;\mathbb{Q})),$

where $\Delta$ is a diagonal comultiplication corresponding to cup product. By
definition of differential, we have

$D:\Omega^{*,*}_{n}(M)\longrightarrow\Omega^{*+1,*-1}_{n}(M).$

######  Theorem 5.

If $d$ is even and $M$ is closed, then $H^{*}(B_{n}(M);\mathbb{Q})$ is
isomorphic to the cohomology of the complex

$(\Omega^{*,*}_{n}(M),D).$

##  3 Reduced Chevalley–Eilenberg complex

In this section, we define an acyclic subcomplex of $(\Omega^{*,*}_{n}(M),D).$

######  Theorem 6.

Let $M$ be a closed orientable manifold of dimension $d.$ The subspace

$\Omega_{n-2}^{*,*}(M).(v_{d}^{2},w_{2d-1})<\Omega_{n}^{*,*}(M)$

is acyclic for $n\geq 2.$

###### Proof.

Let $M$ is closed and orientable. An element in
$\Omega_{n-2}^{*,*}(M).(v_{d}^{2},w_{2d-1})$ has a unique expansion
$v_{d}^{2}A+Bw_{2d-1},$ where $A$ and $B$ have no monomial containing
$w_{2d-1}.$ The operator

$h(v_{d}^{2}A+Bw_{2d-1})=Bv_{d}^{2}$

gives a homotopy $id\simeq 0.$

∎

We denote the reduced complex
$(\Omega_{n}^{*,*}(M)/\Omega_{n-2}^{*,*}(M).(v_{d}^{2},w_{2d-1}),D_{\text{induced}})$
by

$({}^{r}\Omega_{n}^{*,*}(M),D).$

######  Corollary 1.

If $n\geq 2$ and $M$ is closed orientable, then we have an isomorphism

$H^{*}({}^{r}\Omega_{n}^{*,*}(M),D)\cong H^{*}(B_{n}(M)).$

######  Remark 2.

If $M$ is not closed then the subspace
$\Omega_{n-2}^{*,*}(M).(v_{d}^{2},w_{2d-1})$ is vanish.

##  4 Proof of Theorem 2

In this section, we give the proof of Theorem 2.

Proof of Theorem 2. Let $M$ be a closed orientable. Assume
$H_{d-1}(M;\mathbb{Q})$ is non-trivial and $H_{d-1}(M;\mathbb{Q})=k.$ The
corresponding two vector spaces are following

$V^{*}=\oplus_{i=0}^{d}V^{i},\quad W^{*}=\oplus_{i=d-1}^{2d-1}W^{i}$

where

$W^{2d-2}=\langle w_{2d-2,1},\ldots,w_{2d-2,k}\rangle,\quad V^{d-1}=\langle
v_{d-1,1}\ldots,v_{d-1,k-1}\rangle.$

There is no element of degree greater than $\nu_{n}$ in reduced complex.
Therefore, we just focus on the degree $\nu_{n}.$ We will use the notation
$\mbox{J}=\langle w_{2d-2,1},\ldots,w_{2d-2,k}\rangle.$ Let $n$ be odd. We
have

${}^{r}\Omega^{\nu_{n},\lfloor\frac{n}{2}\rfloor}_{n}(M)=v_{d}\mbox{J}^{\lfloor\frac{n}{2}\rfloor}.$

The cardinality of the bases elements of $\mbox{J}^{l}$ is
$\binom{l+k-1}{k-1}.$ The cardinality of the bases elements of
${}^{r}\Omega^{\nu_{n},\lfloor\frac{n}{2}\rfloor}_{n}(M)$ is
$\binom{\frac{n-2}{2}+k-1}{k-1}.$ Moreover, the differential of each bases
element of J is

$D(w_{2d-2,i})=v_{d}v_{d-1,i}.$

We have

$D(v_{d}w_{2d-2,i})=0,\quad\mbox{for }i\in\\{1,\ldots,k-1\\}.$

Note that $v_{d}^{\geq 2}=0$ in reduced complex. Also,
${}^{r}\Omega^{*,j>\lfloor\frac{n}{2}\rfloor}_{n}(M)=0.$ The differential has
bi-degree $(1,-1).$ Therefore each $v_{d}w_{2d-2,i}$ gives a cohomology class.
We can write

$q^{\nu_{n}}_{M}(n)=\binom{\frac{n-2}{2}+k-1}{k-1}+\overline{q}_{M}^{\nu_{n}}(n).$

where $\overline{q}_{M}^{\nu_{n}}(n)$ is a polynomial in $n.$ We can write

$\binom{\frac{n-2}{2}+k-1}{k-1}=\dfrac{(\frac{n-2}{2}+1)(\frac{n-2}{2}+2))\ldots(\frac{n-2}{2}+k-1)}{(k-1)!}.$

This implies that the degree of $q^{\nu_{n}}_{M}(n)$ is at least $k-1.$ From
Theorem 1, the degree of quasi-polynomial $Q_{M}^{\nu_{n}}$ is at most $k-1.$
Hence the degree of $Q_{M}^{\nu_{n}}$ is $k-1.$ $\hfill\square$

##  5 Proof of Theorem 3

In this section, we give the proof of Theorem 3.

Proof of Theorem 3. Let $M$ be a orientable manifold. Assume $M$ is not closed
and $H_{d-1}(M;\mathbb{Q})$ is non-trivial. Furthermore,
$H_{d-1}(M;\mathbb{Q})=k.$ The corresponding two vector spaces are following

$V^{*}=\oplus_{i=0}^{d}V^{i},\quad W^{*}=\oplus_{i=d-1}^{2d-1}W^{i}$

where

$W^{2d-2}=\langle w_{2d-2,1},\ldots,w_{2d-2,k}\rangle,\quad V^{d-1}=\langle
v_{d-1,1}\ldots,v_{d-1,k-1}\rangle.$

There is no element of degree greater than $\nu_{n}-1$ in complex. Therefore,
we just focus on the degree $\nu_{n}-1.$ We will use the notation

$\mbox{I}=\langle v_{d-1,1},\ldots,v_{d-1,k}\rangle,\quad\mbox{J}=\langle
w_{2d-2,1},\ldots,w_{2d-2,k}\rangle.$

Let $n$ be odd. We have

${}^{r}\Omega^{\nu_{n}-1,\lfloor\frac{n}{2}\rfloor}_{n}(M)=\mbox{I}\mbox{J}^{\lfloor\frac{n}{2}\rfloor}.$

The cardinality of the bases elements of
${}^{r}\Omega^{\nu_{n}-1,\lfloor\frac{n}{2}\rfloor}_{n}(M)$ is
$k\binom{\frac{n-2}{2}+k-1}{k-1}.$ We have

$\partial(v_{d-1,j}w_{2d-2,i})=0,\quad\mbox{for }i,j\in\\{1,\ldots,k-1\\}.$

The differential has bi-degree $(-1,1)$ and
${}^{r}\Omega^{j\geq\nu_{n},*}_{n}(M)=0.$ Therefore each $v_{d-1,j}w_{2d-2,i}$
gives a homology class. We can write

$q^{\nu_{n}-1}_{M}(n)=k\binom{\frac{n-2}{2}+k-1}{k-1}+\overline{q}_{M}^{\nu_{n}-1}(n).$

where $\overline{q}_{M}^{\nu_{n}-1}(n)$ is a polynomial in $n.$ We can write

$\binom{\frac{n-2}{2}+k-1}{k-1}=\dfrac{(\frac{n-2}{2}+1)(\frac{n-2}{2}+2))\ldots(\frac{n-2}{2}+k-1)}{(k-1)!}.$

This implies that the degree of $q^{\nu_{n}-1}_{M}(n)$ is at least $k-1.$ From
Theorem 1, the degree of quasi-polynomial $Q_{M}^{\nu_{n}-1}$ is at most
$k-1.$ Hence the degree of $Q_{M}^{\nu_{n}-1}$ is $k-1.$ $\hfill\square$

Acknowledgement. The author gratefully acknowledge the support from the ASSMS,
GC university Lahore. This research is partially supported by Higher Education
Commission of Pakistan.

## References

  * [1] G. C. Drummond-Cole, B. Kundsen, Betti numbers of configuration spaces of surfaces, J. London Math. Soc. Vol 96, 2 (2017) 367-393.
  * [2] Y. Félix, D. Tanré, The cohomology algebra of unordered configuration spaces, J. London Math. Soc. Vol. 72 no. 2 (2005), 525-544.
  * [3] Y. Félix, J. C. Thomas, Rational Betti numbers of configuration spaces, Topol. Appl. Vol. 102 no. 2 (2000), 139-149.
  * [4] B. Knudsen, Betti numbers and stability for configuration spaces via factorization homology, Algebr. Geom. Topol.  Vol. 17 no. 5 (2017), 3137-3187.
  * [5] B. Knudsen, J. Miller, P. Tosteson, Extremal stability for configuration spaces, Math. Ann.  386 (2023), 1695-1716.
  * [6] M. Yameen, A remark on extremal stability of configuration spaces, J. Pure Appl. Algebra. Vol. 227 (2023), 107154.

Abdus Salam School of Mathematical Sciences,
GC University Lahore, Pakistan.
E-mail<EMAIL_ADDRESS>


# Lone Pine at SemEval-2021 Task 5: Fine-Grained Detection of Hate Speech
Using BERToxic

Yakoob Khan, Weicheng Ma, Soroush Vosoughi
Department of Computer Science, Dartmouth College
<EMAIL_ADDRESS>
###### Abstract

This paper describes our approach to the Toxic Spans Detection problem
(SemEval-2021 Task 5). We propose BERToxic, a system that fine-tunes a pre-
trained BERT model to locate toxic text spans in a given text and utilizes
additional post-processing steps to refine the boundaries. The post-processing
steps involve (1) labeling character offsets between consecutive toxic tokens
as toxic and (2) assigning a toxic label to words that have at least one token
labeled as toxic. Through experiments, we show that these two post-processing
steps improve the performance of our model by 4.16% on the test set. We also
studied the effects of data augmentation and ensemble modeling strategies on
our system. Our system significantly outperformed the provided baseline and
achieved an F1-score of 0.683, placing Lone Pine in the 17th place out of 91
teams in the competition. Our code is made available at
https://github.com/Yakoob-Khan/Toxic-Spans-Detection

##  1 Introduction

The promotion of respectful discourse has always been a core tenet of
civilized societies. The Cambridge dictionary defines hate speech as “public
speech that expresses hate or encourages violence towards a person or group
based on something such as race, religion, sex, or sexual orientation.” Online
platforms enable malicious actors to hide behind a cloak of anonymity and
surreptitiously post toxic comments that are a “menace to democratic values,
social stability and peace” (United Nations). To combat this problem, such
platforms often employ human moderators to address offensive content that goes
against community standards. However, moderators are unable to manually keep
pace with the large volume of user-generated content today. This motivates the
development of natural language processing systems to automatically detect
hate speech and ensure that online platforms remain healthy and inclusive for
all.

There has been extensive research on hate speech detection, with the creation
of large datasets (Wulczyn et al., 2017) and the use of pre-trained text
representations (Devlin et al., 2019) for varied modeling approaches.
Competitions on offensive language identification (Zampieri et al., 2020) have
further attracted attention to this topic. Prior work has hitherto focused on
classification at the document-level based on various taxonomies, such as
whether a given text contains offensive language or if it is targeted towards
an individual or group. This line of inquiry does not identify the toxic spans
that ascribe a text as hate speech. Doing so will assist human moderators to
efficiently locate offensive content in long posts and elucidate further
insight into hate speech explainability.

This motivated the Toxic Spans Detection task (Pavlopoulos et al., 2021) where
systems are asked to extract the list of toxic spans that attribute to a
text’s toxicity. Consider the following example111We caution readers that the
examples included in this work contain explicit language to illustrate the
severity and challenges of hate speech detection.:

Text |  Because he’s a moron and bigot. It’s not any more complicated than that.
---|---
Span |  [15, 16, 17, 18, 19, 27, 28, 29, 30, 31]
Table 1: A sample example from the task dataset.

As there are two toxic spans in the above text, systems are tasked to extract
the character offsets (zero-indexed) corresponding to the sequence of toxic
words. This is a challenging task as classification at the word-level is
inherently more difficult than at the document-level. The intentional
obfuscation of toxic words, use of sarcasm and the subjective nature of hate
speech further adds complexity to the problem.

####

Our contributions to the task is threefold:

  1. 1.

We propose BERToxic, a system that finetunes a pre-trained BERT model with
additional post-processing steps to achieve an F1-score of $0.683$, placing
Lone Pine in the $17$th place out of 91 teams in the competition.

  2. 2.

We study the effects of simple data augmentation strategies on our system and
find that they yield no improvement in classification performance.

  3. 3.

We examine late fusion and multi-task learning neural architectures and
conclude that they under-perform compared to the standalone BERT model for
this task.

##  2 Our Approach

###  2.1 Baselines

To have a better sense of our final system’s performance, we initially
examined two baseline models. First, we created a trivial model that randomly
predicts each character offset of a text as toxic if its $\rho>0.5$, drawn
from a continuous uniform probability distribution.

To have a stronger baseline model, we fine-tuned the off-the-shelf spaCy NER
model provided by the task organizers. This model consists of a multi-hash
embedding layer (feed-forward sub-network) that uses sub-word features and an
encoding layer consisting of a CNN and a layer-normalized maxout activation
function. The model uses a transition-based algorithm that assumes that the
“most decisive information” regarding the entities “will be close to their
initial tokens”, with a loss function that optimizes for whole-entity
accuracy.

###  2.2 BERToxic

We framed the toxic spans detection task as a sequence labeling problem and
leverage the Bidirectional Encoder Representation from Transformers (Devlin et
al., 2019) model to extract rich feature representations from the input texts.

Figure 1: The BERToxic model architecture. Image modified from (Devlin et al.,
2019).

The first step in the BERToxic system pipeline (Figure 1) was to tokenize the
text inputs and generate the word embeddings using BERT’s WordPiece tokenizer.
This sub-word tokenization algorithm (Schuster and Nakajima, 2012) tokenizes a
word like "moron" into ["mo","##ron"] and we ensured that the ground truth
labels were preserved across all tokens of a word. As BERT uses absolute
position embeddings, we padded shorter sequences with [PAD] tokens on the
right side such that all tensor inputs are set to equal the maximum sequence
length observed for batched parallelized training. Long sequences were
truncated to $512$ tokens, the maximum sequence length allowed by BERT. As the
data was obtained from online comments that are generally shorter in nature,
the truncation procedure was not needed in this task but nevertheless served
to handle long sequences if present. We also stored the mapping

$\mathcal{M}:t_{i}\mapsto{(start_{i},end_{i})}$

of each token to its relative character offsets in the original string, used
for outputting the toxic span predictions at the post-processing stage.

We performed all of our experiments using the BERTBASE model architecture that
consisted of $12$ layers, $768$ hidden size, $12$ self-attention heads and
$109M$ parameters. The BERTLARGE model was not explored in this work due to
its compute-intensive nature. Our intuition suggested that letter casing could
be helpful for this task as proper nouns (e.g Muslim) can be used offensively,
so we selected the cased model for our experiments. A token classification
head containing a linear layer was applied on top of the final hidden-states
output, with a label prediction of $1$ denoting a toxic token, $0$ otherwise.
For each token $t_{i}$ labeled as toxic, we utilized $\mathcal{M}$ to output
all character indices in the range of ${(start_{i},end_{i})}$ inclusive as the
toxic span of this token.

Additionally, our system performed two post-processing steps to refine the
boundary predictions. Consider the following tokenized sequence:

$t_{1},\cdots,t_{i},t_{i+1},t_{i+2},\cdots,t_{n}$

First, for any two consecutive tokens $t_{i}$ and $t_{i+1}$ whose prediction
labels are toxic, we output the character indices in the range of
$(end_{i}+1,start_{i+1}-1)$ inclusive as toxic as well. This had the effect of
including the delimiter characters between consecutive toxic words, thereby
detecting toxic phrases. Second, recall that BERT’s WordPiece tokenizer could
split a word into multiple tokens, say $t_{i},t_{i+1}$ and $t_{i+2}$. If at
least one token was predicted toxic by the model, our system assigned a toxic
label to all constituent tokens of this word. This achieved coherence in the
prediction of toxic words and phrases, thus avoiding incomplete word piece
issues.

We also attempted to vary the thresholds of the confidence scores before
SoftMax for toxic token predictions but observed no improvement in
performance.

###  2.3 Data Augmentation

Data augmentation is widely used to improve the generalization of models by
acting as a regularizer to reduce overfitting. While various sophisticated
techniques exist to artificially enhance the size and quality of the training
set without collecting additional manually labeled examples, we chose to apply
the set of Easy Data Augmentation (EDA) techniques (Wei and Zou, 2019) to
generate synthetic training data for this task.

The four operations in EDA are Synonym Replacement (SR) using WordNet (Miller,
1995), Random Insertion (RI), Random Swap (RS) and Random Deletion (RD) of
words in a document. Shorter documents are disproportionately more affected by
these operations if a fixed number of words are modified per document. To
ensure that all documents experienced the augmentation strength
proportionately, the number of words $n$ modified was varied based on the
document length $l$ using the formula $n=\alpha\cdot l$, where $\alpha$ is a
hyper-parameter that indicates the percentage of words changed per document.
Each operation was applied once per document and care was taken to ensure that
the ground truth labels were preserved.

Our experiments revealed that the recommended value of $\alpha=0.1$ was too
low for this task and we observed small but consistent improvements as
$\alpha$ increases. Furthermore, we noted that the SR technique alone leads to
better performance than using all four operations to create the augmented
training set for this task.

We also attempted data augmentation using an external dataset, HateXplain
(Mathew et al., 2020), that contains $20,148$ documents with word-level
annotations that we processed to conform to this task’s data format. Each
document consisted of $2$ \- $3$ annotations and we used their intersection to
maximize the inter-annotator agreement in constructing the ground truth
labels. HateXplain’s annotation strategy appeared to be different and included
labeling pronouns, conjunctions and stop words as toxic when located between
offensive words. We removed such toxic labels so that the external dataset
annotation was more similar to this task. When our task dataset was augmented
with the full external dataset, the model experienced underfitting, while
removing all the non-toxic labeled documents from the external dataset
alleviated the issue to some extent.

###  2.4 Ensemble Modeling

Ensemble modeling is an approach where multiple different models are trained
and their predictions are aggregated. By adding bias to counter the variance
of a single model, this line of work has been shown to improve the predictive
performance of a system (Liu et al., 2019). While numerous ensemble modeling
techniques like boosting, bagging, etc. exist, we investigated two techniques
of interest: late fusion and multi-task learning.

We reframed the problem as a binary classification task and trained a sequence
classifier to predict whether a given sentence is toxic. In the late fusion
approach, we utilized NLTK’s tokenizer to split each document into sentences.
If a sentence contained a ground truth toxic span, we assigned the toxic class
label $1$, $0$ otherwise. In this way, a binary classification dataset was
created to separately fine-tune a pre-trained BERT sequence classifier. We
hypothesized that token labels should be predicted toxic only if the
corresponding sentence was classified as toxic as well. Late fusion was
performed at the prediction phase, where both the sequence and token
classifiers voted in the predictions by having the former model filter toxic
sentences on which the latter model made final toxic span predictions.

Rather than fine-tuning the two models separately, we also investigated if
multi-task learning (MTL) improved the predictive performance of the ensemble
model. We hypothesized that a training regime where the two classifiers were
learned jointly could be useful as the knowledge gained in learning one task
could benefit the other. To perform MTL, we fine-tuned an MT-DNN (Liu et al.,
2019) model where the text encoding lower BERT layers are shared across the
two tasks while the top layers are task-specific.

##  3 Experiments

The following sections describe the experimental set-up of our work.

###  3.1 Dataset

The task data was sourced from the Civil Comments dataset (Borkan et al.,
2019), which contains public comments made between $2015$ \- $2017$ that
appeared on approximately $50$ English-language news sites across the world.
As the original dataset contained only document-level class labels, the task
organizers selected a subset of the data for crowd-sourced toxic spans
annotation. For the data split, we chose to fine-tune our models using the
entire provided training dataset $(N=7939)$ to maximize performance, validate
using the trial dataset $(N=690)$, and submit our predictions using the test
data $(N=2000)$. The test labels were withheld during the evaluation phase of
the competition and were only released afterward.

###  3.2 Evaluation Metric

To evaluate the performance of the models, the task organizers employed a
variant of the F1-score (Da San Martino et al., 2019). For a document $d$,
define $S_{d}$ as the set of toxic character offsets predicted by a system and
$G_{d}$ as the set of ground truth annotations. Then the F1-score of the
system with respect to ground truth $G$ for $d$ is defined as

${F_{1}}^{d}(G)=\frac{2\cdot P^{d}(G)\cdot R^{d}(G)}{P^{d}(G)+R^{d}(G)}$

where

$P^{d}(G)=\frac{|S_{d}\cap G_{d}|}{|S_{d}|}$ $R^{d}(G)=\frac{|S_{d}\cap
G_{d}|}{|G_{d}|}$

If a document has no ground truth annotation $(G_{d}=\emptyset)$, or the
system outputs no character offset prediction $(S_{d}=\emptyset)$, we set

${F_{1}}^{d}(G)=\begin{cases}1&G_{d}=S_{d}=\emptyset\\\
0&otherwise\end{cases}$

We finally take the arithmetic mean of ${F_{1}}^{d}(G)$ over all the documents
of an evaluation dataset to obtain a single F1-score for the system.

###  3.3 Implementation Details

We utilized the PyTorch framework for the development of our system,
HuggingFace’s transformers library Wolf et al. (2020) for the BERT-based
models and Microsoft’s implementation of the MT-DNN model. All models were
trained on Google Colab Pro’s High-RAM environment using a single NVIDIA P100
GPU. The training policy used the following hyper-parameters: batch size of
$16$, sequence length of $512$, weight decay of $0.01$. For optimization, we
used Adam with a learning rate of 5e-5 and a linear warm-up schedule over
$500$ steps. Except for MT-DNN222MT-DNN was fined-tuned for $3$ epochs with a
batch size of $8$., all our models were fine-tuned for approximately $2$
epochs and we practiced early stopping by monitoring the dev F1-score to
reduce overfitting. The EDA experiment was performed with $\alpha=0.8$ using
only the SR technique. All other hyper-parameters were set to their default
values according to HuggingFace’s implementation. We set a random seed for all
our experiments and open-sourced the code for reproducibility.

##  4 Results

Model | Dev | Test
---|---|---
| Precision | Recall | F1 | Precision | Recall | F1
Random | 0.143 | 0.463 | 0.175 | 0.089 | 0.413 | 0.122
SpaCy | 0.692 | 0.588 | 0.595 | 0.664 | 0.686 | 0.656
BERToxic | 0.781 | 0.678 | 0.681 | 0.683 | 0.732 | 0.683
\+ EDA | 0.787 | 0.683 | 0.684 | 0.681 | 0.725 | 0.678
\+ HateXplain | 0.792 | 0.674 | 0.681 | 0.683 | 0.721 | 0.678
BERT late fusion | 0.733 | 0.636 | 0.639 | 0.675 | 0.709 | 0.669
BERT multi-task | 0.744 | 0.629 | 0.634 | 0.665 | 0.694 | 0.656
Table 2: A summary of the performance of all our models, reporting the
precision and recall scores along with the F1 evaluation metric used for the
competition. The BERToxic model outperformed the strong spaCy baseline by
$4.16$% on the test set, placing Lone Pine in the $17$th place out of 91
teams. In comparison, the top-ranked submission achieved an F1-score of 0.708.
The experiments revealed that our data augmentation and ensemble modeling
strategies did not outperform the standalone BERT model.

On the following page, Figure 2 visualizes the precision-recall curves333The
curves for the spaCy and BERT multi-task model are less detailed due to the
ambiguity in obtaining the probability scores from their respective
implementations, necessitating the use of their predicted labels instead. of
all the models and Table 2 summarizes their performance metrics. Figure 3
shows the confusion matrix of our best performing BERToxic model and Table 3
highlights selected predictions that it made.

An interesting observation we noted from Table 2 was that the F1 scores for
the test set were higher than the dev set for many of the models. We
hypothesize that this is because the models have an inductive bias to predict
shorter toxic spans, evidenced by the average ground truth span length of
$7.2$ in the test set and $14.7$ in the dev set.

Our proposed system performed well at the toxic spans detection task, showing
strength in identifying profanity and common toxic words like “idiot” and
“stupid”. The model identified the obfuscation of offensive words and
successfully detected hate speech from such adversarial cases (Example 1).

1. |  Kill this F’n W*ore on site.
---|---
2. | .. how I am an ignorant fool ..
3. |  Nazi boneheads deserve being punched.
4. | @ remoore Shut up, racist.
5. | Cruz is a piece of garbage a globalist fraud
Table 3: Selected examples obtained from the test set. BERToxic’s predictions
are shown in red while ground truth annotations are italicized. Figure 2:
Comparison of the precision-recall curves of all the models at the token level
on the test set. The area under the curve is enclosed within parentheses.
Figure 3: A confusion matrix of the BERToxic system at the token level,
revealing insights about the classification performance in each category and
highlighting the imbalance of the class labels in the test set.

The error analysis revealed that the system lacked nuance as it would
sometimes classify toxic words used in neutral contexts (Example 2). It is
also worth mentioning that there was considerable noise in the ground truth
annotations. Our manual inspections concurred with the model’s predictions
that some words and phrases were used in offensive contexts but the annotators
thought they were neutral (Example 3 and 4). Furthermore, we observed some
inconsistencies in the labeling scheme as some annotations spanned entire
sentences (Example 5) while others only highlighted a few words in the
sentence. These issues point to the subjective nature of hate speech and the
challenges involved in its fine-grained classification.

We found through our ablation studies of data augmentation that generating
synthetic data using the EDA techniques did not improve the performance of the
system. This suggested that the dataset size does not appear to be the
limiting factor affecting the performance of BERT in this task. Using
HateXplain’s external dataset, we learned that different data sources and
annotation guidelines can introduce noise that hurts the performance of
models.

Finally, the ensemble modeling strategies we explored did not outperform the
standalone BERT model. The late fusion technique performed slightly better
than the spaCy baseline, but it seemed that the sequence classifier made
errors on similar parts of the input space as the token classifier. The multi-
task learning approach under-performed compared to late fusion, suggesting
that the sequence labeling and classification tasks are not closely related
enough to benefit their joint training.

##  5 Conclusion and Future Work

In this work, we have proposed BERToxic, an empirically powerful system that
performed fine-grained detection of hate speech. We found that our exploration
of data augmentation and ensemble modeling strategies did not outperform the
standalone model. The error analysis revealed that BERT lacked nuance in
understanding the use of offensive words in neutral contexts and encountered
boundary detection issues when faced with noisy ground truth annotations.

Future avenues of work could address these limitations and explore other
transformer-based models to develop more robust hate speech detectors. We hope
that our findings inspire more creative approaches towards fine-grained
detection of hate speech so that online discourse can remain healthy and
inclusive for all.

## Acknowledgments

Yakoob Khan is thankful to be supported by the Stamps Scholarship funded by
Dartmouth College and the Strive Foundation.

## References

  * Borkan et al. (2019) Daniel Borkan, Lucas Dixon, Jeffrey Sorensen, Nithum Thain, and Lucy Vasserman. 2019\.  Nuanced metrics for measuring unintended bias with real data for text classification.  _CoRR_ , abs/1903.04561.
  * Da San Martino et al. (2019) Giovanni Da San Martino, Seunghak Yu, Alberto Barrón-Cedeño, Rostislav Petrov, and Preslav Nakov. 2019.  Fine-grained analysis of propaganda in news article.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 5636–5646, Hong Kong, China. Association for Computational Linguistics.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Liu et al. (2019) Xiaodong Liu, Pengcheng He, Weizhu Chen, and Jianfeng Gao. 2019.  Multi-task deep neural networks for natural language understanding.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4487–4496, Florence, Italy. Association for Computational Linguistics.
  * Mathew et al. (2020) Binny Mathew, Punyajoy Saha, Seid Muhie Yimam, Chris Biemann, Pawan Goyal, and Animesh Mukherjee. 2020.  Hatexplain: A benchmark dataset for explainable hate speech detection.  _arXiv preprint arXiv:2012.10289_.
  * Miller (1995) George A. Miller. 1995.  Wordnet: A lexical database for english.  _Commun. ACM_ , 38(11):39–41.
  * Pavlopoulos et al. (2021) John Pavlopoulos, Léo Laugier, Jeffrey Sorensen, and Ion Androutsopoulos. 2021\.  SemEval-2021 task 5: Toxic Spans Detection (to appear).  In _Proceedings of the 15th International Workshop on Semantic Evaluation_.
  * Schuster and Nakajima (2012) M. Schuster and K. Nakajima. 2012.  Japanese and korean voice search.  In _2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 5149–5152.
  * Wei and Zou (2019) Jason Wei and Kai Zou. 2019.  EDA: Easy data augmentation techniques for boosting performance on text classification tasks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 6383–6389, Hong Kong, China. Association for Computational Linguistics.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online. Association for Computational Linguistics.
  * Wulczyn et al. (2017) Ellery Wulczyn, Nithum Thain, and Lucas Dixon. 2017.  Ex machina: Personal attacks seen at scale.  In _Proceedings of the 26th International Conference on World Wide Web_ , WWW ’17, page 1391–1399, Republic and Canton of Geneva, CHE. International World Wide Web Conferences Steering Committee.
  * Zampieri et al. (2020) Marcos Zampieri, Preslav Nakov, Sara Rosenthal, Pepa Atanasova, Georgi Karadzhov, Hamdy Mubarak, Leon Derczynski, Zeses Pitenis, and Çağrı Çöltekin. 2020.  SemEval-2020 task 12: Multilingual offensive language identification in social media (OffensEval 2020).  In _Proceedings of the Fourteenth Workshop on Semantic Evaluation_ , pages 1425–1447, Barcelona (online). International Committee for Computational Linguistics.


# Link Prediction and Unlink Prediction on Dynamic Networks

Christina Muro1, Boyu Li, Kun He,2 1The first two authors contribute
equally.2Corresponding author.C. Muro, B. Li and K. He are with the School of
Computer Science and Technology, Huazhong University of Science and
Technology, Wuhan, China (E-mail: {christinamuro, afterslby,
<EMAIL_ADDRESS>
###### Abstract

Link prediction on dynamic networks has been extensively studied and widely
applied in various applications. However, temporal unlink prediction, which
also plays an important role in the evolution of social networks, has not been
paid much attention. Accurately predicting the links and unlinks on the future
network greatly contributes to the network analysis that uncovers more latent
relations between nodes. In this work, we assume that there are two kinds of
relations between nodes, namely long-term relation and short-term relation,
and we propose an effective algorithm called LULS for temporal link prediction
and unlink prediction based on such relations. Specifically, for each snapshot
of a dynamic network, LULS first collects higher-order structure as two
topological matrices by applying short random walks. Then, LULS initializes
and optimizes a global matrix and a sequence of temporary matrices for all the
snapshots by using non-negative matrix factorization (NMF) based on the
topological matrices, where the global matrix denotes long-term relation and
the temporary matrices represent short-term relations of snapshots. Finally,
LULS calculates the similarity matrix of the future snapshot and predicts the
links and unlinks for the future network. Additionally, we further improve the
prediction results by using graph regularization constraints to enhance the
global matrix, resulting that the global matrix contains a wealth of
topological information and temporal information. The conducted experiments on
real-world networks illustrate that LULS outperforms other baselines for both
link prediction and unlink prediction tasks.

###### Index Terms:

Link prediction, unlink prediction, dynamic network, random walk, non-negative
matrix factorization

##  I Introduction

Link prediction is one of the fundamental problems that predicts whether two
disconnected nodes in a network are likely to have a link [1]. It is useful in
a wide variety of applications, such as recommendation [2], network
reconstruction [3], and protein-protein interaction [4]. These networks always
have dynamic nature, indicating that nodes and links can be added or removed
with the evolution of networks [5]. It is inspiring and, in some respects,
difficult to study networks at the level of individual edge formation or
removal, especially in the dynamic scenario. Consequently, it still needs to
be further studied on understanding the mechanisms by which such networks
evolve at the level of individual edges.

Link prediction has been studied extensively in recent years [1, 6, 7], and
there are two primary independent scenarios for predicting unknown links in
the networks, forecasting of missing relationships and projection of future
relationships. Although real-world networks have a highly dynamic structure,
most of the previous link prediction studies focus on static networks [8]. In
such scenario, it is anticipated that once two nodes are tied, they mostly
remain tied (e.g., in the Facebook network, once two people are connected,
they rarely break up). As a result, the link prediction problem focuses on
identifying new links. On the other hand, for many networks, additional
temporal information, such as the time of link creation and deletion as well
as node addition and deletion, is available over a time interval, which is
beneficial to understand the structure of the network. Inferring links in
dynamic networks is more challenging because dynamic networks are often
subjected to short-period changes due to noise. Furthermore, due to changes in
the overall environment, some dynamic networks may endure long-term shifts
[9].

Existing dynamic link prediction methods consider only either the structure of
the network [8, 10, 11] or the temporal information [12, 13]. However, these
families of approaches have several limitations. First, real-world networks
are generally sparse and have partially observable links, resulting that the
approaches based on only structure information may perform poorly. Second, the
methods considering temporal information alone may lack insight provided by
the other model. It is thus essential to use both topological and temporal
features to comprehend complex behaviours of the dynamic network. Up to now,
only a few studies [9, 14] have utilized both types of information together
for the dynamic link prediction task. However, these methods fail to consider
the intrinsic geometric structure of the data [15] resulting in lacking
discriminative information for prediction.

Additionally, unlink prediction, which attempts to predict whether a
previously occurred relationship will disappear in the future, is an important
fundamental problem related to link prediction. Several studies [16, 17, 18]
reveal that the probability of relationship to persist or to-be formed
increases if a node pair has a high number of common neighbors as well as high
transitivity through third parties. Furthermore, they also divulge that the
probability of an edge to befall occurs between edges with low resemblance,
fewer communal neighbors, and typically of low transitivity. These findings
illustrate that the processes guiding link creations are negatively correlated
with those guiding link removals, which signifies the importance of unlink
prediction tasks. However, up until now, the link prediction problem has been
heavily studied [8, 19, 20], while its counterpart, unlink prediction problem,
although reporting a high proportion of link changes [21], is rarely studied
[22].

In this work, we assume that the relations in the dynamic networks can be
divided into two categories, long-term relation and short-term relation. The
long-term relation represents a certain kind of stable relation, while the
short-term relation denotes a sort of temporary relation. For instance, in the
collaboration network, the authors in the same lab maintain a stable relation,
and they may always collaborate on publishing papers. While the authors in the
different labs or even focusing on different research fields have a temporary
relation such that they only cooperate occasionally. As a result, these two
kinds of relations determine the states of links and unlinks in the future
network to a large extent.

Based on such assumption, we propose a new algorithm for the link prediction
and unlink prediction with long-term relation and short-term relation, termed
LULS. LULS utilizes the method of non-negative matrix factorization (NMF) that
embeds nodes into two kinds of representation matrices containing both
structural similarity and temporal information. More specifically, for each
snapshot of network, LULS collects higher-order topological information as
matrices by performing two random walk methods, which are light lazy random
walk [23] and a new variant of random walk called modified light lazy random
walk. Then, LULS initializes and optimizes a global matrix and a temporary
matrix for each snapshot by using the method of NMF, where the global matrix
represents the long-term relation that stores the temporal information and is
shared by all the snapshots, while the series of temporary matrices denotes
the short-term relation that only stores the topological information within
the corresponding snapshot. Additionally, LULS also incorporates the geometric
structure by using graph regularization constraints to enhance the global
matrix. Therefore, the global matrix contains a wealth of both topological
information and temporal information, which can further improve the prediction
results. Afterwards, LULS calculates the similarity matrix of the future
snapshot for the temporal predictions of links and unlinks based on the global
matrix and temporary matrices. The experiments conducted on real-world
networks illustrate that LULS outperforms other baselines on AUC for both
tasks of link prediction and unlink prediction.

##  II Related Work

Link prediction in static network has been extensively studied [1]. On the
other hand, for many real-world networks, additional temporal information is
available overtime interval, and the network build from such data can be
represent as a dynamic network. One feasible strategy to model the dynamic
network is to explore the network topological properties, which indicates that
any two nodes close to each other in the network are likely to form a link in
the near future. For example, Rahman et al. [24] capture the topology of
dynamic networks by graphlets, where graphlet transitions between different
timestamps are coded in a feature vector and can be used by supervised
learning. Gunes et al. [25] apply the ARIMA model on the series of node
similarity scores to predict links in the next period based on the previous
time series data. Moradabadi et al. [26] predict the future connections
between pairs of nodes by using the previous snapshot as input. Besides, many
approaches based on the matrix factorization approach has also been proposed
[27, 10, 11, 14, 28]. Matrix factorization has the advantages of generating
embedding which are simple to interpret. The main idea is to learn a latent
low-dimensional vector representation for each node and the nodes close to
each other in the low-rank space are similar. However, most of the real-world
networks are sparse, so that the methods considering only the structural
characteristics of the network may perform poorly.

Moreover, there are some approaches that utilizes temporal information, which
reveals the relationship between the current snapshot and the previous
snapshots, to predict links on dynamic networks [29, 10, 30, 12, 14, 31]. The
main idea is the temporal smoothness, which assumes that the embeddings from
the current snapshot should not deviate dramatically from the previous
snapshots [29]. Although the approaches utilizing structural or temporal
information alone have shown an encouraging performance, the combination of
topological and temporal information always provides further insights that are
missed with the use of single modeling. LIST [31] is proposed which exploits
structural and temporal information and characterizes network information
using time function to predict links on evolving networks. STEP [9] is
presented to exploit structural and temporal information for prediction and
characterize network evolution using a global transition matrix to reflect
different types of evolutionary patterns. Despite their good predictive
performance, these approaches fail to consider the intrinsic geometric
structure of the data, lacking discriminative information for prediction.
Other approaches such as those based on graph neural network (GNN) [32, 33,
34] requires the node features, which may not always be available or may
produce embedding with limited interpretability.

In additional to link prediction, unlink prediction also plays an important
role in network evolution. For example, although some temporary relationships
among people in an online social network are formed during a short-term, some
of these relationships are likely to decay or even disappear in the future.
Until now, there are only few studies address the problem. Preusse et al. [35]
use various network structural features extracted from a knowledge network to
predict the disappearance of links. Oliveira et al. [22] propose the method
combining both the topology information and the information of individuals
(semantic metrics) on evolving networks to predict the disappearance of links.

Comparing to the previous link prediction and unlink prediction methods, LULS
has several advantages. First, to preserve the higher-order topological
information as much as possible, LULS applies two random walk methods on each
snapshot, so that after optimization, the global matrix and the temporary
matrices include more and better topological information. Second, LULS
utilizes NMF to optimize a global matrix and a series of temporary matrices to
reconstruct the matrices obtained by random walk methods. On the one hand, the
global matrix is optimized by all the snapshots, resulting that the global
matrix preserves a wealth of temporal information (i.e., long-term relation).
On the other hand, each temporary matrix contains the specific topological
information of the corresponding snapshot that accurately preserves the short-
term relations between nodes. Therefore, the topological information of future
snapshot can be precisely reconstructed. Last but not least, LULS also
optimizes the global matrix by using graph regularization constraints which
makes the global matrix preserve more topological information that further
improves the prediction results.

##  III Preliminaries

In this section, we first give the problem definition, and then briefly
introduce the random walk method. Important symbols used in this paper are
listed in Table I.

Table I: Symbols and definitions. Symbol | Definition
---|---
$G_{t}=(V_{t},E_{t})$ | the snapshot $G_{t}$ with node set $V_{t}$ and edge set $E_{t}$
$N$ | the final timestamp
$\textbf{W}_{t}$, $\textbf{H}_{t}$ | the similarity matrices for $G_{t}$
U | the global representation matrix
$\textbf{V}_{t}$ | the temporary representation matrix for $G_{t}$
$m$ | the dimension of node representation
$\theta$ | decay weight
$\lambda$ | smoothness weight
$\gamma$ | control the importance of constraint terms
$k$ | the steps of random walk

###  III-A Problem Definition

Consider an undirected and unweighted graph $G=(V,E)$, where $V$ and $E$
denote the set of observed nodes and edges, respectively. Let
$\textbf{A}\in[0,1]^{|V|\times|V|}$ be the associated adjacency matrix, D be a
diagonal matrix of node degrees, and I represents the identity matrix. A
dynamic network is represented as a sequence of snapshots of graph
$\mathcal{G}=\\{G_{1},G_{2},\cdots,G_{N}\\}$, where $N$ is the final
timestamp. We denote $G_{t}=(V_{t},E_{t})$ as the graph at timestamp $t$
($1\leq t\leq N$). For simplicity, we assume the set of nodes do not change
over snapshots, i.e., $V_{t_{i}}=V_{t_{j}}$, for any
$t_{i},t_{j}\in\\{1,\cdots,N\\}$, indicating that we ignore newly added and
removed nodes. However, edges do appear and disappear in snapshots over the
timestamps. Our goal is to predict the edges that will be added or removed in
$G_{N+1}$ based on the previous observed snapshots in $\mathcal{G}$.

######  Definition 1 (Dynamic Link Prediction)

Given a sequence of snapshots of graph
$\mathcal{G}=\\{G_{1},G_{2},\cdots,G_{N}\\}$, where $N$ is the final
timestamp, all the snapshots are with the same set of nodes but some edges may
emerge or disappear along the sequence. For any pair of unconnected nodes $u$
and $v$ in $G_{N}$, the link prediction task on dynamic network aims to
predict whether $u$ and $v$ will have a link in $G_{N+1}$.

######  Definition 2 (Dynamic Unlink Prediction)

Given a sequence of snapshots of graph
$\mathcal{G}=\\{G_{1},G_{2},\cdots,G_{N}\\}$, where $N$ is the final
timestamp, all the snapshots are with the same set of nodes but some edges may
emerge or disappear along the sequence. For any edge $(u,v)\in E_{N}$, the
unlink prediction task on dynamic network aims to predict whether edge $(u,v)$
will disappear in $G_{N+1}$.

Figure 1: An example of temporal link prediction and unlink prediction. In
practice, we use the link states at previous timestamps $t=1$ and $t=2$ to
predict the formations and disappearances of links at timestamp $t=3$.

For example, as shown in Figure 1, given a graph and its two snapshots at
$t=1$ and $t=2$, we know all the changes of edges in both snapshots. For
instance, nodes $v$ and $w$ are unconnected at timestamp $t=1$ and then get
linked at timestamp $t=2$, while the edge between $u$ and $v$ presented at
timestamp $t=1$ disappears at timestamp $t=2$. Then, we aim to predict all the
to-be formed links (e.g., the edge between $m$ and $w$) and to-be removed
links (e.g., the edge between $u$ and $m$) at timestamp $t=3$ by using the
link states at previous timestamps.

###  III-B Random Walk Method

Random walk is one of the most popular methods to measure the importance of
nodes in the graph w.r.t. the given node. Suppose that we start a standard
random walk from the given node $u$, $p_{0}$ is a one-hot vector in which the
corresponding entry of $u$ is 1 and the rest entries are 0. $\textbf{N}_{rw}$
is the transition probability given as
$\textbf{N}_{rw}=\textbf{D}^{-1}\textbf{A}$. Then, the $k$-steps probability
vector can be iteratively calculated by

$p^{(k)}=\textbf{N}_{rw}^{T}p^{(k-1)}=(\textbf{N}_{rw}^{T})^{k}p^{(0)}.$

Let $\textbf{P}^{(k)}\in\mathbb{R}^{|V|\times|V|}$ be the matrix that combines
$p^{(k)}$ for all the nodes in the graph. Then, the $ij$-th entry in
$\textbf{P}^{(k)}$ represents the probability that the random walker starts at
node $i$ to reach node $j$ in $k$ steps. In this work, we use
$\hat{\textbf{P}}^{(k)}=\textbf{P}^{(k)}+(\textbf{P}^{(k)})^{T}$ as the
similarity scores for all the pairs of nodes, where
$\hat{\textbf{P}}^{(k)}_{ij}$ denotes the sum of the probabilities that a
random walker jumps from node $i$ to node $j$ as well as from node $j$ to node
$i$ within $k$ steps.

##  IV Methodology

In this section, we illustrate the detailed procedures of LULS that contains
three main steps. First, for each snapshot $G_{t}$, LULS calculates two
matrices $\textbf{H}_{t}$ and $\textbf{W}_{t}$ by using local random walk
methods to collect higher-order topological information. Then, LULS
initializes a global representation matrix U and a temporal representation
matrix $\textbf{V}_{t}$ for each snapshot $G_{t}$ to represent the long-term
relations and short-term relations respectively, and optimizes U and
$\textbf{V}_{t}$ by applying the method of NMF according to $\textbf{H}_{t}$
and $\textbf{W}_{t}$ of each snapshot. Finally, LULS computes the similarity
matrix R of the future snapshot based on the matrices
$\textbf{V}_{1},\textbf{V}_{2},\cdots,\textbf{V}_{N}$ and U, and predicts the
states of links and unlinks for the future snapshot. The whole framework is
given in Algorithm 1, and we elaborate each step as follows.

Algorithm 1 The LULS Algorithm

1:A series of adjacency matrices
$\textbf{A}_{1},\textbf{A}_{2},\cdots,\textbf{A}_{N}$, the hyper-parameters
$\lambda$, $\gamma$, and $\theta$

2:Similarity matrix R

3:compute matrices ${\textbf{H}_{1}},{\textbf{H}_{2}},\cdots,{\textbf{H}_{N}}$

4:compute matrices ${\textbf{W}_{1}},{\textbf{W}_{2}},\cdots,{\textbf{W}_{N}}$

5:for $t=1$ to $N$ do

6: randomly initialize ${\textbf{V}_{t}}$

7:end for

8:randomly initialize U

9:repeat:

10: for $t=1$ to $N$ do

11: update ${\textbf{V}_{t}}$ according to Eq. (5)

12: end for

13: update U according to Eq. (6)

14:until termination criteria are reached

15:compute R according to Eq. (7)

16:return R

###  IV-A Collecting Topological Information

In the first step, for each snapshot $G_{t}$, LULS computes two matrices
${\textbf{H}_{t}}$ and ${\textbf{W}_{t}}$ to represent topological
information. Note that the basic idea of NMF is to learn a low-dimensional
vector for each node by factorizing the adjacency matrix. However, the
adjacency matrix can not fully capture the higher-order relations between
nodes. Moreover, since the real-world networks are always extremely large with
millions or even billions of nodes, it is computationally expensive to apply
global proximity methods to measure the strength between nodes. Therefore, a
few variants of random walk, which can effectively collect the topological
information, are proposed as solutions [23, 36].

In this work, we adopt light lazy random walk (LLRW) [23] and propose a new
random walk variant called modified light lazy random walk (MLLRW) to collect
the higher-order topological information. LLRW and MLLRW are defined as
follows:

  * (1)

Light Lazy Random Walk (LLRW).

$\textbf{N}_{rw}=(\textbf{D}+\alpha\textbf{I})^{-1}(\alpha\textbf{I}+\textbf{A}),$

where $\alpha\in N^{0+}$ is a hyper-parameter. Compared to standard random
walk, LLRW retains some probability at the current node for the random walks.
Moreover, LLRW degenerates to standard random walk when $\alpha=0$, and
$\alpha=l$ indicates that the random walker performs $l$ loops on each node.

  * (2)

Modified Light Lazy Random Walk (MLLRW).

$\textbf{N}_{rw}=\beta\textbf{S}+(1-\beta)\left((\textbf{D}+\alpha\textbf{I})^{-1}(\alpha\textbf{I}+\textbf{A})\right),$

where S is the diagonal matrix with degree centrality similarity between every
node in the network, and $\beta\in[0,1]$ is a hyper-parameter. MLLRW expects
the ranking score of the nodes to be biased more to higher degree nodes, such
that a random walker of MLLRW performs light lazy walk to one of the neighbors
of the current node with probability $(1-\beta)$ and jumps to any other node
in the graph according to S with probability $\beta$. Additionally, MLLRW
degenerates to LLRW when $\beta=0$.

Let $\hat{\textbf{P}}^{(k)}_{LLRW}$ and $\hat{\textbf{P}}^{(k)}_{MLLRW}$
represent the similarity matrices as introduced in Section III-B obtained by
performing LLRW and MLLRW over the graph, respectively. Then, we separately
calculate $\textbf{H}_{t}=\hat{\textbf{P}}^{(k)}_{LLRW}$ and
$\textbf{W}_{t}=\hat{\textbf{P}}^{(k)}_{MLLRW}$ for each snapshot $G_{t}$.

###  IV-B Node Representation

In the dynamic real-world network, nodes have long-term relations and short-
term relations, and the temporal predictions of links and unlinks are
determined by these two relations. Consequently, we leverage NMF to find the
temporary representation matrices
$\textbf{V}_{1},\textbf{V}_{2},\cdots,\textbf{V}_{N}$ and a global
representation matrix U such that the inner product of $\textbf{V}_{i}$ and U
can approximate the topological information $\textbf{W}_{t}$ of $G_{t}$. Note
that, the global representation U can be considered as long-term relation
between nodes, while the temporary representations
$\textbf{V}_{1},\textbf{V}_{2},\cdots,\textbf{V}_{N}$ evolved over time is
regarded as short-term relations.

Specifically, let $m$ be the dimension of node representation, and for each
$\textbf{W}_{t}$, we aim to factorize the matrix as
${\textbf{W}_{t}}\approx\textbf{U}\textbf{V}_{t}^{T}$, where the matrices
$\textbf{U}\in{\mathbb{R}_{+}}^{|V|\times m}$ and
${\textbf{V}_{t}}\in{\mathbb{R}_{+}}^{|V|\times m}$ represent the global
representation matrix and temporary representation matrix, respectively.
Additionally, to ensure that the temporary representations of nodes between
snapshots do not change significantly, we apply regularization to maintain the
smoothness. Therefore, for the matrix $\textbf{W}_{t}$, the objective function
is given as

$\displaystyle\mathop{\min}\limits_{\textbf{U}\geq 0,{\textbf{V}_{t}}\geq 0}J$
$\displaystyle=\sum\limits_{t=1}^{N}{{\theta^{N-t}}\left\|{{\textbf{W}_{t}}-\textbf{U}\textbf{V}_{t}^{T}}\right\|}_{F}^{2}$
(1)
$\displaystyle+\lambda\sum\limits_{t=2}^{N}{\theta^{N-t}}{{\left\|{{\textbf{V}_{t}}-{\textbf{V}_{t-1}}}\right\|}^{2}_{F}},$

where $\theta\in[0,1]$ is the decay weight and $\lambda$ is the smoothness
weight.

Furthermore, to enhance the node representation U that preserves more
topological information,motivated by graph regularization technique [37], we
define the similarity constraint term $M_{t}$ based on $\textbf{H}_{t}$ for
each snapshot $G_{t}$ as follows

$M_{t}=\frac{1}{2}{\sum\limits_{ij}{\left\|{u_{i}-u_{j}}\right\|}^{2}}\textbf{H}_{t_{ij}}=Tr(\textbf{U}^{T}{\textbf{L}_{t}}\textbf{U}),$
(2)

where $\textbf{H}_{t_{ij}}$ is the $ij$-th entry in $\textbf{H}_{t}$,
$\textbf{L}_{t}=\textbf{D}_{t}-\textbf{H}_{t}$ is the Laplacian matrix, and
$Tr(\cdot)$ is the trace matrix. Overall, the enhanced objective function is
expressed as follows:

$\displaystyle\mathop{\min}\limits_{\textbf{U}\geq 0,\textbf{V}_{t}\geq 0}J=$
$\displaystyle\sum\limits_{t=1}^{N}{{\theta^{N-t}}\left\|{{\textbf{W}_{t}}-\textbf{U}\textbf{V}_{t}^{T}}\right\|}_{F}^{2}+\gamma\sum\limits_{t=1}^{N}M_{t}$
(3)
$\displaystyle+\lambda\sum\limits_{t=2}^{N}{\theta^{N-t}}{{\left\|{{\textbf{V}_{t}}-{\textbf{V}_{t-1}}}\right\|}^{2}_{F}},$

where $\gamma$ is a hyper-parameter to control the relevance importance of
constraint terms.

###  IV-C Optimization

In this section, we present an iterative update algorithm to solve the
optimization problem in Eq. (3). In each iteration, the algorithm updates each
matrix in turn while fixing the other matrices. This procedure repeats until
the matrices converge or the maximum number of iterations is reached. By
removing the irrelevant items, i.e., $\theta$, Eq. (3) can be simplified as:

$\displaystyle\mathop{\min}\limits_{\textbf{U}\geq 0,{\textbf{V}_{t}}\geq 0}J$
$\displaystyle={\sum\limits_{t=1}^{N}{\left\|{{\textbf{W}_{t}}-\textbf{U}\textbf{V}_{t}^{T}}\right\|}^{2}_{F}}+\gamma\sum\limits_{t=1}^{N}{Tr({\textbf{U}^{T}}{\textbf{L}_{t}}\textbf{U})}$
$\displaystyle+\lambda\sum\limits_{t=2}^{N}{{{\left\|{{\textbf{V}_{t}}-{\textbf{V}_{t-1}}}\right\|}^{2}_{F}}}.$

We first address the problem of optimizing $\textbf{V}_{t}$ for each
$t\in[1,N]$. According to Eq. (3), the optimization problem is transformed as
follows:

$\begin{split}\mathop{\min}\limits_{{\textbf{V}_{t}}\geq
0}J=&\sum\limits_{t=1}^{N}{Tr(\gamma({\textbf{W}_{t}}}-\textbf{U}\textbf{V}_{t}^{T}){({\textbf{W}_{t}}-\textbf{U}\textbf{V}_{t}^{T})^{T}})\\\
&+\sum\limits_{t=2}^{N-1}{Tr(\lambda({\textbf{V}_{t}}}-{\textbf{V}_{t-1}}){({\textbf{V}_{t}}-{\textbf{V}_{t-1}})^{T}}).\end{split}$
(4)

Based on the non-negativity constraint of ${\textbf{V}_{t}}$ following the
standard constraint optimization theory, we introduce the Lagrangian
multiplier ${\phi_{t}}=\left[{{\phi_{ij}}}\right]$ and minimize the Lagrangian
function $L$, such that

$L=J+\sum\limits_{t=1}^{N}{Tr({\phi_{t}}}{\textbf{V}_{t}}^{T}).$

By computing the derivate of $L$ with respect to ${\textbf{V}_{t}}$, we have
the following expression:

$\displaystyle\frac{{\delta L}}{{\delta{\textbf{V}_{t}}}}$
$\displaystyle=-2{\textbf{W}_{t}}\textbf{U}+\textbf{U}\textbf{V}_{t}^{T}{\textbf{U}^{T}}+2\lambda({\textbf{V}_{t}}-{\textbf{V}_{t-1}})+{\phi_{t}}.$

Next, by setting ${{\delta L}\over{\delta{\textbf{V}_{t}}}}=0$ and
${\left[{{\phi_{t}}}\right]_{ij}}{\left[{{\textbf{V}_{t}}}\right]_{ij}}=0$, we
obtain the following equation for ${\left[{{\textbf{V}_{t}}}\right]_{ij}}$:

${[-{\textbf{W}_{t}}\textbf{U}+\textbf{U}\textbf{V}_{t}^{T}{\textbf{U}^{T}}+\lambda({\textbf{V}_{t}}-{\textbf{V}_{t-1}})]_{ij}}{({\textbf{V}_{t}})_{ij}}=0.$

Then, the update rule for ${\textbf{V}_{t}}$ is derived as follows:

${\textbf{V}_{t}}\leftarrow{\textbf{V}_{t}}\odot\sqrt{{{{\textbf{H}_{t}}\textbf{U}+\lambda({\textbf{V}_{t-1}})}\over{\textbf{U}\textbf{V}_{t}^{T}{\textbf{U}^{T}}+\lambda({\textbf{V}_{t}})}}}.$
(5)

The global matrix U can be learned in a very similar to latent factor
${\textbf{V}_{t}}$. To handle non-negative constraints, we introduce the
Lagrangian multiplier $\psi=\left[{{\psi_{ij}}}\right]$ and minimize the
Lagrangian function $L$:

$L=J+\psi$

Taking the derivate of L with respect to $U$, we have the following expression

$\displaystyle{{\delta L}\over{\delta
U}}=-2{W_{t}}{V_{t}}+2U{V_{t}}^{T}{V_{t}}^{T}+2\gamma{L_{t}}U+\psi,$

by setting ${{\delta L}\over{\delta{U}}}=0$, and using KKT conditions
${[\psi]_{ij}}{[U]_{ij}}=0$, we obtain the following equation for
${[U]_{ij}}$:

${[-{W_{t}}{V_{t}}+U{V_{t}}^{T}{V_{t}}^{T}+\gamma{L_{t}}U]_{ij}}{({U})_{ij}}=0$

Then the update rule for $U$ is derived as follows:

$U\leftarrow
U\odot\sqrt{{{\sum\limits_{t=1}^{N}{({W_{t}}{V_{t}}+\gamma{H_{t}}U)}}\over{\sum\limits_{t=1}^{N}{(U{V_{t}}^{T}{V_{t}}^{T}+\gamma{D_{t}}U)}}}}.$
(6)

###  IV-D Predicting Links and Unlinks

After optimizing $\textbf{V}_{1},\textbf{V}_{2},\cdots,\textbf{V}_{N}$ and U,
LULS calculates the similarity matrix of future snapshot for the predictions
of links and unlinks. The probability of link formation and link disappearance
can be obtained by the inner product of the latent factors U and
${\textbf{V}_{t}}$ for each $t\in[1,N]$, such that

$\textbf{R}=\sum\nolimits_{t=1}^{N}{\textbf{U}\textbf{V}_{t}}^{T}.$ (7)

Each $ij$-th entry in R denotes the proximity score for the pair of nodes $i$
and $j$. For the link prediction problem, the higher the similarity score
between unconnected nodes in R the higher the probability of connect in the
future. In contrast, for the unlink prediction problem, for two connected
nodes in R if this pair of nodes have a lower similarity score, then they have
a higher probability of disappearing in the future.

###  IV-E Complexity Analysis

In this section, we discuss the time complexity of LULS. Local spectal
diffusion [6] depends on the number of nodes on the network, and the time
complexity is $O(Nl{\left|V\right|^{2}})$, where $l$ is the number of
iterations to convergence. For NMF, the computation is dominated by matrix
multiplications, i.e., the matrix multiplication between $|V|\times|V|$ matrix
and $|V|\times m$ matrix. Therefore, the complexity involved for updating
$V_{t}$ and $U$ is $O(rN{\left|V\right|^{2}}m)$, where $r$ denotes the number
of iterations. Besides, the complexity of computing $R$ is
$O({\left|V\right|^{2}}m)$. Thus, the overall time complexity of our LULS
model is $O((rN+1){\left|V\right|^{2}}m+Nl{\left|V\right|^{2}})$. Note that,
since all matrices are sparse, the complexity between two sparse matrix is
much smaller than $O({|V|^{2}})$.

##  V Experimental Setup

###  V-A Datasets

We use six real-world dynamic networks for evaluating the performance of LULS.
The datasets contain Facebook Forum, Reality Mining, Dublin, Hep-Th, Facebook
Messages, and Retweet. Table II summarizes the detailed information of these
datasets.

Table II: Statistics of the datasets. | Facebook Forum | Reality Mining | Dublin | Hep-Th | Facebook Messages | Haggle
---|---|---|---|---|---|---
Number of nodes | 899 | 6416 | 6454 | 22908 | 274 | 18470
Number of edges | 7046 | 7250 | 24097 | 2444798 | 15737 | 2124
Average degree | 15.68 | 2.26 | 7.45 | 213.44 | 16.57 | 15.51
Density | 0.0175 | 0.0004 | 0.0012 | 0.0093 | 0.0087 | 0.0568
Avg shortest-path distance | 2.8320 | 4.2367 | 6.6808 | 2.7220 | 3.0552 | 2.42
Number of snapshots | 6 | 7 | 8 | 11 | 8 | 6

  * -

Facebook Forum [38]: The Facebook Forum network is the private messages
exchanged between Facebook users from May to October in 2004, where the nodes
are the users, and each edge is a message exchanged between a pair of users.

  * -

Reality Mining [38]: Reality Mining network consists of individual’s mobile
phone call events between a set of core users at Massachusetts Institute of
Technology (MIT), where the vertices are users, and each edge is a phone call
or voicemail between a pair of users.

  * -

Dublin [38]: Dublin network is a human contact network where the vertices
represent individuals and the edges denote proximity.

  * -

Hep-Th111http://networkrepository.com: This dataset is a collaboration network
from high energy physics theory section on arXiv, where vertices are authors
and an edge denotes a common publication for a pair of authors.

  * -

Facebook Messages††footnotemark: : This dataset is a Facebook-like social
network originated from online community of the students at the University of
California, where the nodes are users, and the edges are the messages
exchanged between pairs of users.

  * -

Haggle222http://konect.cc/networks: This network reflects connections between
people as measured by wireless devices carried by the participants. A node
symbolizes a person, and an edge between two people indicates that they came
into touch.

###  V-B Evaluation Metric

In this paper, we apply AUC and average precision (AP) to evaluate the
performance of LULS. Specifically, for each dataset, we use
${G_{1}},{G_{2}},\cdots,{G_{N-1}}$ as the training data and ${G_{N}}$ as the
test data. Furthermore, the test data is divided into positive test samples
and negative test samples. For the link prediction problem, the positive test
set consists of the edges that appear in ${G_{N}}$ and do not present in
${G_{N-1}}$, while the negative test set consists of the edges that do not
appear in ${G_{N-1}}$ and ${G_{N}}$. On the other hand, for unlink prediction
problem, the positive test set contains the edges that appear in ${G_{N-1}}$
and ${G_{N}}$, while the negative test set consists of the edges that present
in ${G_{N-1}}$ and disappear in ${G_{N}}$. To avoid the class imbalance, we
randomly generate the same size of negative test set as that of positive test
set for both link prediction and unlink prediction. In addition, the
experiments are carried out five times independently and the average result is
reported.

Generally, the AUC is described as the likelihood that the randomly selected
actual link in the positive test set is assigned a higher score than a
randomly selected link in the negative test set. Formally, if among $n$
comparisons, there are ${n^{\prime}}$ times the the edges in the negative test
set has a lower score than the edges in the positive test set and
$n^{\prime\prime}$ times they have the same scores, the AUC scores are
calculated as follows

$\displaystyle AUC=\frac{{n^{\prime}+0.5*n^{\prime\prime}}}{n}.$

Note that, an algorithm has a better performance than pure chance when the
value of AUC is bigger than 0.5.

AP combines recall and precision for ranking results. We calculate the
precision after each true positive given a ranked list of predicted links. The
average of these values gives the average precision for that link.

###  V-C Baselines

We compare our method with the the-state-of-the-art methods as follows:

  * -

AA [20]: AA assumes that two nodes are more likely to be linked together if
they share more common neighbors.

  * -

DCN [39]: This method uses a decay common neighbor to characterize the
relationship between node pair.

  * -

TD [11]: This method stacks all adjacency matrices of historical snapshots
into a tensor with the time as the third dimension to improve the link
prediction results.

  * -

TMF [14]: This method uses matrix factorization techniques to characterize the
network characteristics as a function of time

  * -

GrNMF [40]: This method directly approximates the link matrix over time $T$
using NMF by setting networks from 1 to $T-1$ as a regularizer.

Note that, the methods AA and DCN can be applied only to static network.
Therefore, in the case of link prediction, these approaches are performed
based on the links from all past time periods by combining them into a single
link matrix. For the unlink prediction task, these approaches are conducted
based on the link states over ${G_{N-1}}$.

##  VI Experimental Results

In the experiments, all the parameters of LULS have been manually tuned.
Specifically, we set $m=5$, $\theta=0.4$, $\gamma=1$ and $\lambda=0.0001$ for
facebook Forum, Facebook Messages and Haggle networks. And for Reality mining
and Dublin network, we set $\gamma=0.0001$. For the random walks variants, we
use $\alpha=1$ for LLRW, and $\beta=0.01$ for MLLRW. Besides, we use the
random walk step $k=4$ for the Facebook Forum, Reality mining, Facebook
Messages and Hep-Th networks, and $k=5$ for the Dublin network. Moreover, for
evaluating the effectiveness of smoothness and constraint terms, we implement
three versions of LULS as follows:

  * -

LULS1: $\lambda\neq 0$ and $\gamma\neq 0$;

  * -

LULS2: $\lambda\neq 0$ and $\gamma=0$;

  * -

LULS3: $\lambda=0$ and $\gamma=0$.

Table III: The AUC scores for the link prediction task.

Methods Datasets | Facebook Forum | Reality Mining | Dublin | Hep-Th | Facebook Messages | Haggle
---|---|---|---|---|---|---
LULS1 | 0.9324 | 0.9735 | 0.9913 | 0.7351 | 0.9765 | 0.9881
LULS2 | 0.9232 | 0.9764 | 0.9909 | 0.7089 | 0.9741 | 0.9870
LULS3 | 0.8278 | 0.9750 | 0.9908 | 0.6974 | 0.9750 | 0.9835
AA | 0.5252 | 0.5192 | 0.8914 | 0.5612 | 0.7351 | 0.9230
DCN | 0.5313 | 0.5194 | 0.9620 | 0.5612 | 0.4601 | 0.4532
TD | 0.9059 | 0.9214 | 0.6495 | 0.6268 | 0.9192 | 0.5693
TMF | 0.8314 | 0.9284 | 0.6037 | 0.6985 | 0.7122 | 0.9127
GrNMF | 0.8792 | 0.9204 | 0.6542 | 0.6837 | 0.9474 | 0.9213

Table IV: The AP scores for the Link prediction task.

Methods Datasets | Facebook Forum | Reality Mining | Dublin | Hep-Th | Facebook Messages | Haggle
---|---|---|---|---|---|---
LULS1 | 0.8942 | 0.9570 | 0.9850 | 0.7012 | 0.9528 | 0.9810
LULS2 | 0.8731 | 0.9604 | 0.9843 | 0.6926 | 0.9521 | 0.9775
LULS3 | 0.8646 | 0.9602 | 0.9844 | 0.6845 | 0.9510 | 0.9642
AA | 0.5160 | 0.5150 | 0.8909 | 0.5547 | 0.7400 | 0.9430
DCN | 0.5646 | 0.4424 | 0.9563 | 0.5610 | 0.4619 | 0.6096
TD | 0.8870 | 0.9106 | 0.9028 | 0.6248 | 0.9357 | 0.7481
TMF | 0.8271 | 0.9117 | 0.5926 | 0.6954 | 0.7018 | 0.8020
GrNMF | 0.8444 | 0.9071 | 0.6018 | 0.6773 | 0.7155 | 0.8587

Table V: The AUC scores for the unlink prediction task.

Methods Datasets | Facebook Forum | Reality Mining | Dublin | Hep-Th | Facebook Messages | Haggle
---|---|---|---|---|---|---
LULS1 | 0.8363 | 0.7970 | 0.7525 | 0.6923 | 0.7790 | 0.9345
LULS2 | 0.8268 | 0.7968 | 0.7532 | 0.6567 | 0.8044 | 0.9334
LULS3 | 0.8278 | 0.7661 | 0.7517 | 0.5051 | 0.8036 | 0.9316
AA | 0.546 | 0.5192 | 0.5437 | 0.5558 | 0.5101 | 0.6492
DCN | 0.4858 | 0.5014 | 0.5871 | 0.5437 | 0.5117 | 0.6096
TD | 0.7596 | 0.7651 | 0.5731 | 0.6154 | 0.7032 | 0.9367
TMF | 0.6780 | 0.7946 | 0.5861 | 0.6748 | 0.6961 | 0.8143
GrNMF | 0.6395 | 0.7848 | 0.6351 | 0.6645 | 0.7411 | 0.8445

Table VI: The AP scores for the Unlink prediction task.

Methods Datasets | Facebook Forum | Reality Mining | Dublin | Hep-Th | Facebook Messages | Haggle
---|---|---|---|---|---|---
LULS1 | 0.8120 | 0.7885 | 0.8231 | 0.7014 | 0.8162 | 0.9333
LULS2 | 0.7958 | 0.8773 | 0.8218 | 0.6612 | 0.8293 | 0.9320
LULS3 | 0.7877 | 0.8776 | 0.8210 | 0.5152 | 0.8280 | 0.9268
AA | 0.5462 | 0.5083 | 0.5437 | 0.5610 | 0.5089 | 0.6520
DCN | 0.4931 | 0.5011 | 0.5667 | 0.4619 | 0.4991 | 0.5741
TD | 0.8077 | 0.7620 | 0.7447 | 0.6272 | 0.7928 | 0.9377
TMF | 0.8280 | 0.7940 | 0.5612 | 0.6675 | 0.6961 | 0.8138
GrNMF | 0.7812 | 0.7845 | 0.6326 | 0.6651 | 0.7155 | 0.8341

###  VI-A Link Prediction

In this experiment, we evaluate the performance of LULS for link prediction.
Table III and Table IV shows the performance of different approaches on six
dynamic networks for the link prediction task. It can be observed that LULS
models perform best in all the datasets, indicating that LULS can effectively
integrate both temporal and structural information to extract significant node
representation for the link prediction task. Precisely, our model has shown an
impressive performance even on a very sparse graphs, e.g., Dublin network.
Furthermore, all the approaches based on dynamic characteristics (i.e., LULS,
TD, TMF, and GrNMF) consistently perform better than the approaches that
ignore the temporal behaviour of the network (i.e., AA and DCN) in almost all
the datasets. In addition, among LULS models, LULS1 is better than LULS2 and
LULS3. Consequently, the smoothness and similarity constraint terms play
important roles in link prediction.

###  VI-B Unlink Prediction

Next, we investigate the effectiveness of LULS for the unlink prediction task.
In Table V and Table VI, the AUC and AP scores show that LULS models
significantly outperform the baseline methods in almost all the datasets.
Precisely, our model have shown an impressive performance on Haggle network,
suggesting that unlink prediction is more likely on dense graph than on sparse
graphs. Similar to link prediction task, all the approaches which consider
temporal information of the network outperform other methods. Moreover, among
LULS models, LULS1 is also better than LULS2 and LULS3, which indicates that
the smoothness and similarity constraint terms are useful in unlink
prediction. Additionally, comparing to link prediction, we can observe that
the AUC scores of unlink prediction are lower, indicating that it is more
difficult to predict unlinks than links in the future network.

##  VII Conclusion

In this work, we address the problems of temporal link prediction and unlink
prediction on dynamic networks. Assuming that there are two kinds of relations
between nodes, namely long-term relation and short-term relation, we propose
an effective algorithm called LULS for temporal link prediction and unlink
prediction based on such relations. Specifically, LULS collects the
topological information for each snapshot of a dynamic network and generates a
global matrix and a sequence of temporary matrices to represent the long-term
relation and short-term relation. Then, LULS utilizes the global matrix and
the temporary matrices to predict the links and unlinks for the future
network. The experiments conducted on six real-world networks show the
superior results of LULS compared with the state of the art methods.

## References

  * [1] A. Kumar, S. S. Singh, K. Singh, and B. Biswas, “Link prediction techniques, applications, and performance: A survey,” _Physica A: Statistical Mechanics and its Applications_ , vol. 553, p. 124289, 2020.
  * [2] Y. Koren, R. Bell, and C. Volinsky, “Matrix factorization techniques for recommender systems,” _IEEE Computer_ , vol. 42, no. 8, pp. 30–37, 2009\.
  * [3] M. Nickel, K. Murphy, V. Tresp, and E. Gabrilovich, “A review of relational machine learning for knowledge graphs,” _arXiv preprint arXiv:1503.00759_ , vol. 104, no. 1, pp. 11–33, 2016.
  * [4] I. A. Kovács, K. Luck, K. Spirohn, Y. Wang, C. Pollis, S. Schlabach, W. Bian, D. K. Kim, N. Kishore, T. Hao, M. A. Calderwood, M. Vidal, and A. L. Barabási, “Network-based prediction of protein interactions.” _Nature Communications_ , vol. 10, no. 1, 2019\.
  * [5] C. Aggarwal and K. Subbian, “Evolutionary network analysis: A survey,” _ACM Computing Surveys_ , vol. 47, no. 1, 2014.
  * [6] V. Martínez, F. Berzal, and J.-C. Cubero, “A survey of link prediction in complex networks,” _ACM Computing Surveys_ , vol. 49, no. 4, 2017.
  * [7] P. Wang, B. Xu, Y. Wu, and X. Zhou, “Link prediction in social networks: the state-of-the-art,” _Science in China Series F: Information Sciences_ , vol. 58, no. 1, pp. 1–38, 2015.
  * [8] D. Liben-Nowell and J. Kleinberg, “The link-prediction problem for social networks,” _Journal of the Association for Information Science and Technology_ , vol. 58, no. 7, pp. 1019–1031, 2007.
  * [9] H. Chen and J. Li, “Exploiting structural and temporal evolution in dynamic link prediction,” in _Proceedings of the 27th ACM International Conference on Information and Knowledge Management_ , 2018, pp. 427–436.
  * [10] D. Deng, C. Shahabi, U. Demiryurek, L. Zhu, R. Yu, and Y. Liu, “Latent space model for road networks to predict time-varying traffic,” in _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , 2016, pp. 1525–1534.
  * [11] D. M. Dunlavy, T. G. Kolda, and E. Acar, “Temporal link prediction using matrix and tensor factorizations,” _ACM Transactions on Knowledge Discovery from Data (TKDD)_ , vol. 5, no. 2, pp. 1–27, 2011.
  * [12] R. A. Rossi, B. Gallagher, J. Neville, and K. Henderson, “Modeling dynamic behavior in large evolving graphs,” in _Proceedings of the sixth ACM international conference on Web search and data mining_ , 2013, pp. 667–676.
  * [13] P. Sarkar and A. W. Moore, “Dynamic social network analysis using latent space models,” _Acm Sigkdd Explorations Newsletter_ , vol. 7, no. 2, pp. 31–40, 2005.
  * [14] W. Yu, C. C. Aggarwal, and W. Wang, “Temporally factorized network modeling for evolutionary network analysis,” in _Proceedings of the Tenth ACM International Conference on Web Search and Data Mining_ , 2017, pp. 455–464.
  * [15] D. Cai, X. He, X. Wu, and J. Han, “Non-negative matrix factorization on manifold,” in _2008 Eighth IEEE International Conference on Data Mining_. IEEE, 2008, pp. 63–72.
  * [16] H. Kwak, H. Chun, and S. Moon, “Fragile online relationship: a first look at unfollow dynamics in twitter,” in _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems_ , 2011, pp. 1091–1100.
  * [17] D. Quercia, M. Bodaghi, and J. Crowcroft, “Loosing ”friends” on facebook,” in _Proceedings of the 4th Annual ACM Web Science Conference on_ , 2012.
  * [18] F. Kivran-Swaine, P. Govindan, and M. Naaman, “The impact of network structure on breaking ties in online social networks: unfollowing on twitter,” in _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems_ , 2011, pp. 1101–1104.
  * [19] R. Eyal, A. Rosenfeld, S. Sina, and S. Kraus, “Predicting and identifying missing node information in social networks,” _ACM Transactions on Knowledge Discovery From Data_ , vol. 8, no. 3, 2014.
  * [20] T. Zhou, L. Lü, and Y.-C. Zhang, “Predicting missing links via local information,” _European Physical Journal B_ , vol. 71, no. 4, pp. 623–630, 2009.
  * [21] S. A. Myers and J. Leskovec, “The bursty dynamics of the twitter information network,” in _Proceedings of the 23rd international conference on World wide web_ , 2014, pp. 913–924.
  * [22] M. A. de Oliveira, K. C. Revoredo, and J. E. O. Luna, “Semantic unlink prediction in evolving social networks through probabilistic description logic,” in _2014 Brazilian Conference on Intelligent Systems_ , 2014.
  * [23] K. He, P. Shi, D. Bindel, and J. E. Hopcroft, “Krylov subspace approximation for local community detection in large networks,” _ACM Transactions on Knowledge Discovery From Data_ , vol. 13, no. 5, pp. 1–30, 2019\.
  * [24] M. Rahman and M. A. Hasan, “Link prediction in dynamic networks using graphlet,” in _ECML PKDD 2016 European Conference on Machine Learning and Knowledge Discovery in Databases - Volume 9851_ , 2016, pp. 394–409.
  * [25] İsmail Güneş, Şule Gündüz-Öğüdücü, and Z. Çataltepe, “Link prediction using time series of neighborhood-based node similarity scores,” _Data Mining and Knowledge Discovery_ , vol. 30, no. 1, pp. 147–180, 2016\.
  * [26] B. Moradabadi and M. R. Meybodi, “A novel time series link prediction method: Learning automata approach,” _Physica A: Statistical Mechanics and its Applications_ , vol. 482, pp. 422–432, 2017.
  * [27] E. Acar, D. M. Dunlavy, and T. G. Kolda, “Link prediction on evolving data using matrix and tensor factorizations,” in _2009 IEEE International conference on data mining workshops_. IEEE, 2009, pp. 262–269.
  * [28] L. Zhu, D. Guo, J. Yin, G. Ver Steeg, and A. Galstyan, “Scalable temporal latent space inference for link prediction in dynamic social networks,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 28, no. 10, pp. 2765–2777, 2016.
  * [29] Y. Chi, X. Song, D. Zhou, K. Hino, and B. L. Tseng, “Evolutionary spectral clustering by incorporating temporal smoothness,” in _Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2007, pp. 153–162.
  * [30] Y.-R. Lin, Y. Chi, S. Zhu, H. Sundaram, and B. L. Tseng, “Facetnet: a framework for analyzing communities and their evolutions in dynamic networks,” in _Proceedings of the 17th international conference on World Wide Web_ , 2008, pp. 685–694.
  * [31] W. Yu, W. Cheng, C. C. Aggarwal, H. Chen, and W. Wang, “Link prediction with spatial and temporal consistency in dynamic networks.” in _IJCAI_ , 2017, pp. 3343–3349.
  * [32] J. Chen, J. Zhang, X. Xu, C. Fu, D. Zhang, Q. Zhang, and Q. Xuan, “E-lstm-d: A deep learning framework for dynamic network link prediction,” _IEEE Transactions on Systems, Man, and Cybernetics: Systems_ , 2019.
  * [33] M. Yang, J. Liu, L. Chen, Z. Zhao, X. Chen, and Y. Shen, “An advanced deep generative framework for temporal link prediction in dynamic networks,” _IEEE transactions on cybernetics_ , vol. 50, no. 12, pp. 4946–4957, 2019\.
  * [34] K. Lei, M. Qin, B. Bai, G. Zhang, and M. Yang, “Gcn-gan: A non-linear temporal link prediction model for weighted dynamic networks,” in _IEEE INFOCOM 2019-IEEE Conference on Computer Communications_. IEEE, 2019, pp. 388–396.
  * [35] J. Preusse, J. Kunegis, M. Thimm, S. Staab, and T. Gottron, “Structural dynamics of knowledge networks,” in _Seventh International AAAI Conference on Weblogs and Social Media_ , 2013.
  * [36] D. Kamuhanda, M. Wang, and K. He, “Sparse nonnegative matrix factorization for multiple-local-community detection,” _IEEE Transactions on Computational Social Systems_ , vol. 7, no. 5, pp. 1220–1233, 2020.
  * [37] D. Cai, X. He, J. Han, and T. S. Huang, “Graph regularized nonnegative matrix factorization for data representation,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 33, no. 8, pp. 1548–1560, 2010.
  * [38] A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , vol. 2016, 2016, pp. 855–864.
  * [39] H. Tian and R. Zafarani, “Exploiting common neighbor graph for link prediction,” in _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, 2020, pp. 3333–3336.
  * [40] X. Ma, P. Sun, and Y. Wang, “Graph regularized nonnegative matrix factorization for temporal link prediction in dynamic networks,” _Physica A: Statistical mechanics and its applications_ , vol. 496, pp. 121–136, 2018.

|  Christina Muro received bachelor’s degree with Computer Science from the
University of Dar-es-salaam, Dar-es-salaam, Tanzania in 2009 and the master’s
degree in Computer Science, from the University of Dodoma, Dodoma, Tanzania in
2013. She is currently pursuing the Ph.D. degree with the School of Computer
Science and Technology, Huazhong University of Science and Technology, Wuhan,
China. She has been a Lecturer in the Department of Computer Science and
Engineering at the University of Dodoma since 2018. Her research interests
include machine learning and social network analysis.
---|---
|  Boyu Li received his M.S. degree and Ph.D. degree in Computer Science and
Technology from Jilin University, in 2014 and 2018, respectively. He is
currently a post-doctor in School of Computer Science and Technology, Huazhong
University of Science and Technology. His research interests include privacy-
preserving data publishing, social network and graph embedding.
---|---
|  Kun He is currently a Professor in School of Computer Science and
Technology, Huazhong University of Science and Technology (HUST) Wuhan, P.R.
China; and a Mary Shepard B. Upson Visiting Professor for the 2016-2017
Academic year in Engineering, Cornell University NY, USA. She received the B.S
degree in physics from Wuhan University, Wuhan, China, in 1993; the M.S.
degree in computer science from Huazhong Normal University, Wuhan, China, in
2002; and the Ph.D. degree in system engineering from HUST, Wuhan, China, in
2006. Her research interests include machine learning, deep learning, social
networks, and algorithm design.
---|---