# A note on extremal digraphs containing at most $t$ walks of length $k$ with
the same endpoints

Zhenhua Lyu  School of Science, Shenyang Aerospace University, Shenyang,
110136, China<EMAIL_ADDRESS>
###### Abstract

Let $n,k,t$ be positive integers. What is the maximum number of arcs in a
digraph on $n$ vertices in which there are at most $t$ distinct walks of
length $k$ with the same endpoints? In this paper, we prove that the maximum
number is equal to $n(n-1)/2$ and the extremal digraph are the transitive
tournaments when $k\geq
n-1\geq\max\\{2t+1,2\left\lceil\sqrt{2t+9/4}+1/2\right\rceil+3\\}$. Based on
this result, we may determine the maximum numbers and the extremal digraphs
for $k\geq\max\\{2t+1,2\left\lceil\sqrt{2t+9/4}+1/2\right\rceil+3\\}$ and $n$
is sufficiently large, which generalises the existing results. A conjecture is
also presented.

Key words: digraph, Turán problem, walk

AMS subject classifications: 05C20, 05C35

##  1 Introduction

We discuss only finite simple digraphs (without multiple arcs but allowing
loops). The terminology and notation is that of [1], except as indicated. The
number of the vertices of a digraph is its order and the number of the arcs
its size. We abbreviate directed walks and directed cycles as walks and
cycles, respectively. The length of a walk or cycle is its number of arcs. A
$p$-cycle is a cycle of length $p$. Similarly, a $p$-walk is a walk of length
$p$. Let $D=(\mathcal{V},\mathcal{A})$ be a digraph with vertex set
$\mathcal{V}$ and arc set $\mathcal{A}$. The size of $D$ is denoted by $a(D)$.
The outdegree and indegree of a vertex $u$, denoted by $d^{+}(u)$ and
$d^{-}(u)$, is the number of arcs with tails and heads $u$, respectively.
Denote by

$N^{+}(u)=\\{x\in\mathcal{V}|(u,x)\in\mathcal{A}\\}\quad and\quad
N^{-}(u)=\\{x\in\mathcal{V}|(x,u)\in\mathcal{A}\\}.$

For a set $X\subset\mathcal{V}$, we denote by $D[X]$ the subgraph of $D$
induced by $X$. For $u,v\in\mathcal{V}$, $uv$ denotes the arc from $u$ to $v$
and the notation $u\rightarrow v$ means $uv\in\mathcal{A}$.

Turán type problems are among the most important topics in graph theory, which
concern the possible largest number of edges in graphs forbidding given
subgraphs and the extremal graphs achieving that maximum number of edges. The
systematic investigation of digraph extremal problem was initiated by Brown
and Harary [2]. For more details, see [3, 4]. Given a family of digraphs
$\mathscr{F}$, a digraph $D$ is said to be $\mathscr{F}$-free if $D$ contains
no subgraph from $\mathscr{F}$. Let $ex(n,\mathscr{F})$ be the maximum size of
$\mathscr{F}$-free digraphs of order $n$ and $EX(n,\mathscr{F})$ be the set of
$\mathscr{F}$-free digraphs of order $n$ with size $ex(n,\mathscr{F})$. Given
two positive integers $k,t$, denote by $\mathscr{F}_{k,t}$ the family of
digraphs consisting of $t$ different walks of length $k$ with the same initial
vertex and the same terminal vertex. In [5], the authors posed a Turán type
problem as follows.

######  Problem 1.

Given positive integers $n,k,t$, determine $ex(n,\mathscr{F}_{k,t+1})$ and
$EX(n,\mathscr{F}_{k,t+1})$.

The initial version of Problem 1 was posed by Zhan at a seminar in 2007, which
concerned the case $t=1$, see [13, p. 234]. In the last decade, Problem 1 for
the case $t=1$ has been completely solved by Wu [12], by Huang and Zhan [8],
by Huang, Lyu and Qiao [7], by Lyu [11], and by Huang and Lyu [6]. For the
general cases of Problem 1, the case $k=2$ has been studied in [9], and the
case for $k\geq n-1\geq 6t+1$ has been solved in [5].

######  Theorem 2 ([5]).

Let $t$ be a positive integer. For $k\geq n-1\geq 6t+1$, a digraph $D\in
EX(n,\mathscr{F}_{k,t+1})$ if and only if $D$ is a transitive tournament.

We define $z(t)$ as the smallest integer such that if $k\geq n-1\geq z(t)$,
then $D\in EX(n,\mathscr{F}_{k,t+1})$ if and only if $D$ is a transitive
tournament. Huang and Zhan [8] proved that $z(1)=4$. It follows from Theorem 2
that $z(t)$ is well defined for each positive integer $t$ and

$z(t)\leq 6t+1.$

Based on this fact, using induction on $n$, Lyu [10] obtained the following
result.

######  Theorem 3.

Let $k,n,t$ be positive integers with $k\geq 6t+1$ and $n\geq
k+5+\lfloor\log_{2}(t)\rfloor$. Then $D\in EX(n,\mathscr{F}_{k,t+1})$ if and
only if $D$ is an balanced blow-up of the transitive tournament of order $k$.

Motivated by Theorem 3, [11, Theorem 2] and [7, Theorem 1], we present the
conjecture as follows.

######  Conjecture 4.

Let $k\geq z(t)$ and let $n$ be sufficiently large. Then $D\in
EX(n,\mathscr{F}_{k,t+1})$ if and only if $D$ is a balanced blow-up of the
transitive tournament of order $k$.

From [8] we get $z(1)=4$. Hence, Conjecture 4 holds confirmly when $t=1$. In
the point of this view, it is important to determine the exact value or a
better upper bound of $z(t)$ for each $t$. In this note, we present a new
upper bound for $z(t)$ as follows.

######  Theorem 5.

let $t$ be a positive integer. Then

$z(t)\leq\max\\{2t+1,2\left\lceil\sqrt{2t+9/4}+1/2\right\rceil+3\\}.$ (1.1)

Adopting the same arguments as in the proofs in [10](modify a few details in
the proof), we may obtain that Theorem 3 holds for
$k\geq\max\\{2t+1,2\left\lceil\sqrt{2t+9/4}+1/2\right\rceil+3\\}$, which
improves the main result of [10] when $t\geq 2$.

##  2 Proof of Theorem 5

We need the following lemmas.

######  Lemma 6.

Let $n,t$ be positive integers and let $D$ be a digraph of order $n$. If an
$m_{1}$-cycle $C_{1}$ and an $m_{2}$-cycle $C_{2}$ in $D$ are joint, then $D$
is not $\mathscr{F}_{k,t+1}$-free for all $k\geq L\lceil\log_{2}(t+1)\rceil,$
where $L$ is the least common multiple of $m_{1}$ and $m_{2}$.

###### Proof.

Let $a_{1}=L/m_{1}$ and $a_{2}=L/m_{2}$. Assume $C_{1}$ and $C_{2}$ are joint
at vertex $v$. Let $w$ be the walk of length $L\lceil\log_{2}(t+1)\rceil$ from
$v$ to $v$ along $C_{1}$. We partition $w$ into $\lceil\log_{2}(t+1)\rceil$
walks of the same length from $v$ to $v$, say
$w_{1},\ldots,w_{\lceil\log_{2}(t+1)\rceil}$. Each of
$\\{w_{1},\ldots,w_{\lceil\log_{2}(t+1)\rceil}\\}$ could be replaced by
repeating $C_{2}$ $a_{2}$ times. Therefore, there exist $t+1$ distinct walks
of length $L\lceil\log_{2}(t+1)\rceil$ from $v$ to $v$. For
$k>L\lceil\log_{2}(t+1)\rceil$, we can extend these walks along $C_{2}$ to
$k$-walks with the same endpoints. ∎

######  Lemma 7 ([5]).

Let $n,t$ be positive integers and let $D$ be a digraph of order $n$. If an
$m_{1}$-cycle $C_{1}$ and an $m_{2}$-cycle $C_{2}$ in $D$ are connected by an
arc, then $D$ is not $\mathscr{F}_{k,t+1}$-free for $k\geq tL+1.$

The girth of a digraph with a cycle is the length of its shortest cycle, and a
digraph with no cycle has infinite girth.

######  Lemma 8 ([5]).

Let $D$ be a loopless digraph of order $n$. If $a(D)=n(n-1)/2$, then $D$ is a
transitive tournament or

$g(D)\leq 3.$

Let $D=(\mathcal{V},\mathcal{A})$ be a digraph with $l$ loops. Denote by
$d(u)$ the number of arcs incident with $u$. We have

$d(u)=\left\\{\begin{array}[]{ll}d^{+}(u)+d^{-}(u)-1,&if~{}u\rightarrow u;\\\
d^{+}(u)+d^{-}(u),&\textrm{otherwise}.\end{array}\right.$

Since $a(D)=\sum\limits_{u\in\mathcal{V}}d^{+}(u)$ and
$a(D)=\sum\limits_{u\in\mathcal{V}}d^{-}(u)$, we have

$2a(D)=\sum\limits_{u\in\mathcal{V}}d(u)+l,$ (2.1)

and

$d(u)=a(D)-a(D[\mathcal{V}\setminus\\{u\\}])~{}\text{for~{}all}~{}u\in\mathcal{V}.$

######  Lemma 9.

Let $D=(\mathcal{V},\mathcal{A})$ is $\mathscr{F}_{k,t+1}$-free with $k\geq
2\lceil\log_{2}(t+1)\rceil$. Then $d(u)\leq|\mathcal{V}|$ for all
$u\in\mathcal{V}$.

###### Proof.

Suppose there exists $u\in\mathcal{V}$ such that $d(u)\geq|\mathcal{V}|+1$. It
follows that at least two cycles are joint at $u$. Moreover, these 2 cycles
are either two 2-cycles or one loop and one 2-cycle. By Lemma 6, $D$ is not
$\mathscr{F}_{k,t+1}$-free for $k\geq 2\lceil\log_{2}(t+1)\rceil$, a
contradiction. ∎

######  Lemma 10.

Let $D=(\mathcal{V},\mathcal{A})$ be a digraph and let $C$ and $T$ be disjoint
cycle and tournament in $D$, where $|\mathcal{V}(T)|\geq
2\left\lceil\sqrt{2t+9/4}+1/2\right\rceil+1$. If there exists at least one arc
between each vertex of $C_{1}$ and each vertex of $T$, then $D$ is not
$\mathscr{F}_{k,t+1}$-free for
$k\geq\max\\{t+1,3\lceil\log_{2}(t+1)\rceil\\}$.

###### Proof.

To the contrary, suppose $D$ is $\mathscr{F}_{k,t+1}$-free for
$k\geq\max\\{t+1,3\lceil\log_{2}(t+1)\rceil\\}$. Suppose $T$ contains a
3-cycle $C_{1}$ as its subdigraph. Let

$C\equiv w_{1}\rightarrow\dots\rightarrow w_{l}\rightarrow
w_{1}~{}\text{and}~{}C_{1}\equiv u_{1}\rightarrow u_{2}\rightarrow
u_{3}\rightarrow u_{1}.$

Without loss of generality, we assume $w_{1}\rightarrow u_{1}$. If
$u_{2}\rightarrow w_{1}$, we obtain a 3-cycle $u_{2}\rightarrow
w_{1}\rightarrow u_{1}\rightarrow u_{2}$. Since two 3-cycles are joint, by
Lemma 6 we obtain $D$ is not $\mathscr{F}_{k,t+1}$-free, a contradiction.
Hence, $w_{1}\rightarrow u_{2}$. Similarly, $w_{1}\rightarrow u_{3}$. If there
exists some $i$ such that $u_{i}\rightarrow w_{l}$, we obtain
$u_{i}\rightarrow w_{l}\rightarrow w_{1}\rightarrow u_{i}$. Then two 3-cycles
are joint. By Lemma 6, $D$ is not $\mathscr{F}_{k,t+1}$-free, a contradiction.
Hence $w_{l}\rightarrow u_{i}$ for $i\in\\{1,2,3\\}$. Repeate the above
arguments, we have

$w_{i}\rightarrow
u_{j}\quad\text{for}~{}i\in\\{1,2,\ldots,l\\}~{}\text{and}~{}j\in\\{1,2,3\\}.$
(2.2)

We construct walks of length $k$ from $w_{1}$ to $u_{1}$ in the following way.
For each $t_{1}\in\\{0,1,\ldots,t\\}$, there are a walk of length $t_{1}$ with
its initial vertex $w_{1}$ along $C$, say $W_{t_{1}}$, and a walk of length
$k-t_{1}-1$ with terminal vertex $u_{1}$ along $C_{1}$, say
$W^{\prime}_{t_{1}}$. Since (2.2), $W_{t_{1}}W^{\prime}_{t_{1}}$ is a walk of
length $k$ with initial vertex $w_{1}$ and terminal vertex $u_{1}$. Then there
exist $t+1$ distinct walks of length $k$ from $w_{1}$ to $u_{1}$, a
contradiction. Hence $T$ contains no 3-cycles. Combining this with Lemma 8,
$T$ is acyclic, and hence it is transitive. Let
$a=\left\lceil\sqrt{2t+9/4}+1/2\right\rceil$. Since $|\mathcal{V}(T)|\geq
2a+1$, without loss of generality, we assume $w_{1}$ has at least $a+1$
successors in $T$. Let those successors be
$\\{t_{0},t_{1},t_{2},\ldots,t_{a}\\}$ with $t_{i}\rightarrow t_{0}$ for
$i=\\{1,2,\ldots,a\\}$. For any pair $i,j\in\\{1,2,\ldots,a\\}$ with $i<j$, we
have $\cdots\rightarrow w_{1}\rightarrow t_{i}\rightarrow t_{j}\rightarrow
t_{0}$. Since $a(a-1)/2\geq t+1$, then there are more than $t$ walks of length
at least 3, a contradiction. ∎

Now we are ready to give the proof of Theorem 5.

Proof of Theorem 5. Let $a=2\left\lceil\sqrt{2t+9/4}+1/2\right\rceil+1$ and
let $n^{\prime}\geq a+2$. It is easily seen that the transitive tournament of
order $n^{\prime}$ is in $EX(n^{\prime},\mathscr{F}_{k,t+1})$. Hence,

$ex(n^{\prime},\mathscr{F}_{k,t+1})\geq\frac{n^{\prime}(n^{\prime}-1)}{2}$
(2.3)

First we prove that

$ex(n^{\prime},\mathscr{F}_{k,t+1})=\frac{n^{\prime}(n^{\prime}-1)}{2}.$ (2.4)

Suppose otherwise that $D$ is $\mathscr{F}_{k,t+1}$-free on $n^{\prime}$
vertices with $l$ loops and

$a(D)\geq\frac{n^{\prime}(n^{\prime}-1)}{2}+1.$ (2.5)

By the pigeonhole principle, there exists some $v$ such that $d(v)\geq
n^{\prime}$. Combining this with Lemma 9, we have

$d(v)=n^{\prime}.$ (2.6)

We distinguish the following two cases.

Case 1. $vv\notin\mathcal{A}$. Then there exists
$u\in\mathcal{V}\setminus\\{v\\}$ such that $vu,uv\in\mathcal{A}$. By Lemma 6,
two $2$-cycles can not be joint. Hence $v$ is on exactly one 2-cycle.
Combining this with (2.6), each vertex in $\mathcal{V}\setminus\\{u,v\\}$ is
jointed with $v$ by exactly one arc. By Lemma 7, $D-v$ has no 2-cycles or
loops, which implies that $d(w)\leq n^{\prime}-1$ for all
$w\in\mathcal{V}\setminus\\{v,u\\}$. By Lemma 9 and (2.5), we obtain
$d(u)=n^{\prime}$ and

$d(w)=n^{\prime}-1{\rm~{}for~{}all~{}}w\in\mathcal{V}\setminus\\{v,u\\}.$

Hence, $D[\mathcal{V}\setminus\\{u,v\\}]$ is a tournament. Moreover, each
vertex in $\mathcal{V}\setminus\\{u,v\\}$ is jointed with each of $\\{u,v\\}$
by exactly one arc. Since $|\mathcal{V}\setminus\\{u,v\\}|\geq a$, by Lemma
10, $D$ is not $\mathscr{F}_{k,t+1}$, a contradiction.

Case 2. $vv\in\mathcal{A}$. By Lemma 7, $v$ is jointed by exactly one arc with
each vertex in $\mathcal{V}$. Moreover, each vertex in
$\mathcal{V}\setminus\\{v\\}$ is not on a loop or a 2-cycle. It follows from
(2.5) and (2.6) that $D[\mathcal{V}\setminus\\{v\\}]$ is a tournament. By
Lemma 10, $D$ is not $\mathscr{F}_{k,t+1}$-free, a contradiction. Now we get
(2.4).

Now we characterize the structures of the digraphs in
$EX(n,\mathscr{F}_{k,t+1})$. Let $D\in EX(n,\mathscr{F}_{k,t+1})$. First we
show that $D$ contains no loops. By (2.4), we obtain that

$a(D)=\frac{n(n-1)}{2}~{}\text{and}~{}a(D[\mathcal{V}\setminus\\{u\\}])\leq(n-1)(n-2)/2.$

Combining this with the definition of $d(u)$, we get $d(u)\geq n-1$ for all
$u\in\mathcal{V}$. Recalling (2.1), $D$ is loopless. Moreover,

$d(u)=n-1~{}{\rm for~{}all~{}}u\in\mathcal{V}.$ (2.7)

Suppose $D$ contains a 2-cycle $u\rightarrow v\rightarrow u$. By Lemma 6, $v$
can not be on two distinct 2-cycles. Hence, it is joined with $n-2$ distinct
vertices. Let $v_{0}\in\mathcal{V}$ such that there is no arc between $v$ and
$v_{0}$. From (2.7) $v_{0}$ is on a 2-cycle, say $v_{0}\rightarrow
v_{1}\rightarrow v_{0}$. Obviously, $v_{1}$ is joined with $v$. By Lemma 7,
$D$ is not $\mathscr{F}_{k,t+1}$-free, a contradiction. Hence, $D$ contains no
2-cycles. Recalling (2.7), $D$ is a tournament.

Suppose $D$ contains a 3-cycle $u\rightarrow v\rightarrow w\rightarrow u$.
Note that $D[\mathcal{V}\setminus\\{u,v,w\\}]$ is also a tournament. Since
$n-3\geq a$, by Lemma 10, $D$ is not $\mathscr{F}_{k,t+1}$-free, a
contradiction. It follows from Lemma 8 that $D$ is a transitive tournament.

Conversely, it is easily seen that the transitive tournament of order $n$ is
in $EX(n,\mathscr{F}_{k,t+1})$. This completes the proof. ∎

## References

  * [1] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, The Macmillan Press, London, 1976.
  * [2] W.G. Brown and F. Harary, Extremal digraphs, Combinatorial Theory and its Applications, Colloq. Math. Soc. Janos Bolyai 4 (1970) I, 135-198.
  * [3] W.G. Brown, P. Erdős, M. Simonovits, Extremal problems for directed graphs, J. Combin. Theory Ser. B 15 (1973) 77-93.
  * [4] W. G. Brown, M. Simonovits, Extremal multigraph and digraph problems, Paul Erdős and his mathematics, II (Budapest, 1999), 157-203, Bolyai Soc. Math. Stud., 11, J nos Bolyai Math. Soc., Budapest, 2002.
  * [5] Z. Huang, Z. Lyu, 0-1 matrices whose $k$-th powers have bounded entries, Linear Multilinear Algebra 68 (2020) 1972-1982.
  * [6] Z. Huang, Z. Lyu, Extremal digraphs avoiding distinct walks of length 3 with the same endpoints, Manuscript.
  * [7] Z. Huang, Z. Lyu, P. Qiao, A Turán problem on digraphs avoiding distinct walks of a given length with the same endpoints, Discrete Math. 342 (2019) 1703-1717.
  * [8] Z. Huang, X. Zhan, Digraphs that have at most one walk of a given length with the same endpoints, Discrete Math. 311 (2011) 70-79.
  * [9] Z. Lyu, 0-1 matrices whose squares have bounded entries, Linear Algebra Appl. 607 (2020) 1-8.
  * [10] Z. Lyu, Digraphs that contain atmost $t$ distinct walks of a given length with the same endpoints, J. Comb. Optim. 41 (2021) 762-779.
  * [11] Z. Lyu, Extremal digraphs avoiding distinct walks of length 4 with the same endpoints, Discuss. Math. Graph Theory, doi:10.7151/dmgt.2321.
  * [12] H. Wu, On the 0-1 matrices whose squares are 0-1 matrices, Linear Algebra Appl. 432 (2010) 2909-2924.
  * [13] X. Zhan, Matrix theory, Graduate Studies in Mathematics 147, American Mathematical Society, Providence, RI, 2013.


# FSD: An Initial Chinese dataset for Fake Song Detection

###### Abstract

Singing voice synthesis and singing voice conversion have significantly
advanced, revolutionizing musical experiences. However, the rise of “Deepfake
Songs” generated by these technologies raises concerns about authenticity.
Unlike Audio DeepFake Detection (ADD), the field of song deepfake detection
lacks specialized datasets or methods for song authenticity verification. In
this paper, we initially construct a Chinese Fake Song Detection (FSD) dataset
to investigate the field of song deepfake detection. The fake songs in the FSD
dataset are generated by five state-of-the-art singing voice synthesis and
singing voice conversion methods. Our initial experiments on FSD revealed the
ineffectiveness of existing speech-trained ADD models for the task of song
deepfake detection. Thus, we employ the FSD dataset for the training of ADD
models. We subsequently evaluate these models under two scenarios: one with
the original songs and another with separated vocal tracks. Experiment results
show that song-trained ADD models exhibit a 38.58% reduction in average equal
error rate compared to speech-trained ADD models on the FSD test set.

Index Terms—  deepfake songs, song deepfake detection, dataset

##  1 Introduction

Singing voice synthesis [1, 2, 3] and singing voice conversion [4, 5, 6] have
witnessed remarkable advancements in recent years, revolutionizing the way we
perceive and enjoy music. This advancement, while captivating, raises alarming
issues related to authenticity and trustworthiness. The growing capabilities
of singing voice synthesis and singing voice conversion enable the creation of
fake singing voices, commonly referred as “Deepfake Songs,” which can imitate
the style, timbre, and emotion of real singers with astonishing accuracy. This
poses a considerable threat to the integrity of audio content, artistic
integrity, and the credibility of vocal performances.

In light of these challenges, the necessity for robust and reliable methods of
detecting and verifying the authenticity of songs has become increasingly
apparent. The field of song deepfake detection has emerged as a crucial area
of research. song deepfake detection task aims to develop techniques that can
differentiate between genuine and synthetic songs, thereby safeguarding the
integrity of musical works, protecting the reputation of artists, and
maintaining the trust of listeners. However, to the best of our knowledge,
there are currently no dedicated song deepfake detection datasets or methods
for detecting the authenticity of songs.

For a similar area to song deepfake detection, the field of Audio DeepFake
Detection (ADD) is relatively comprehensive and boasts an abundance of
detection datasets and methods. In order to propel the research in ADD,
numerous datasets have been introduced, including those derived from
competitions such as the ASVspoof series [7] and ADD challenge series [8]. In
terms of methods, models like AASIST [9] and those based on Wav2Vec2 (W2V2)
[10] have achieved equal error rate (EER) below 1% in single-domain scenarios
[11, 12]. However, to our knowledge, there has been no investigation of
whether these methods can effectively detect the authenticity of songs.

Judging the authenticity of songs poses a significant challenge. Currently,
ADD models can only detect domain-specific datasets in a single domain,
lacking robustness and generalizability to out-of-domain datasets [13]. For
singing songs, they are created by mixing vocal tracks and instrumental
tracks. Vocals exhibit distinctive attributes, including varying pitch range
and modulation, distinguishing them from typical speech which may lead to
misjudgment for current ADD methods. On the other hand, the presence of
instrumental tracks in songs can be perceived as “interfering noise” by
current ADD approaches. It is significant to investigate their effect on song
deepfake detection task.

To carry out the relevant research, the construction of the dataset is the
first step. In our paper, we introduce a Chinese fake song detection (FSD)
dataset. For the fake songs, they totally cover 5 types, which are the popular
and expressive generated methods. We extract the instrumental track from real
songs and mix it with the fake singing voice to create the final fake song. We
also employ state-of-the-art (SOTA) ADD methods to evaluate the FSD dataset
under two conditions: the original songs, and the vocal tracks isolated
through separation technique. Our main contributions can be summarized as
follows:

  * •

We initially present FSD dataset, specifically designed for investigating song
deepfake detection task.

  * •

Leveraging the proposed FSD dataset and audio source separation strategy for
training, we achieve a 38.58% reduction in EER on the FSD test set when
compared to speech-trained ADD algorithms.

##  2 Dataset Design

The FSD dataset comprises a total of 200 real songs and 450 fake songs. In
this section, we will introduce the process of generating the fake songs.

###  2.1 Fake singing voice generation

We select 5 different representative singing voice synthesis and singing voice
conversion methods, denoted as F01 to F05, to generate the fake songs.

F01: SO-VITS111https://github.com/svc-develop-team/so-vits-svc. This is a
project differs fundamentally from VITS [14], as it focuses on singing voice
conversion rather than Text-to-Speech. The singing voice conversion model
employs the content encoder from SoftVC [15] to extract speech features from
the source singing voice. These feature vectors are directly input into VITS
without necessitating conversion to an intermediary text-based representation.
This approach preserves the pitch and intonations of the original singing
voice. Additionally, in SO-VITS, the NSF-HiFiGAN vocoder is employed as the
vocoder. This modified version of HifiGAN [16], based on the neural source
filter [17], effectively addresses the problem of sound interruptions.

F02: SO-VITS (NSF-HifiGAN with Snake [18]). This generation method, modified
from F01, introduces modifications to the decoder of VITS, specifically, the
vocoder component of the network. The NSF-HiFiGAN vocoder is optimized and
integrated, leveraging a novel activation function called ”Snake.” This
activation function is designed to achieve the desired periodic inductive
bias, allowing the network to learn periodic functions while retaining the
favorable optimization properties associated with ReLU-based activations.

F03: SO-VITS (with shallow diffusion [1]). To address the issue of electrical
sound problems, this approach incorporates a solution within VITS.
Specifically, we trained a separate shallow diffusion model to further enhance
the quality of mel-spectrogram. During this training process, we employed a
pre-trained NSF-HifiGAN to convert mel-spectrogram into audio.

F04: DiffSinger [1]. This is an acoustic model for singing voice synthesis
task based on the diffusion probabilistic model [19]. DiffSinger commences
generation at a shallow step determined by the intersection of the diffusion
trajectories of the ground-truth mel-spectrogram and the one predicted by a
simple mel-spectrogram decoder. Additionally, DiffSinger introduces a boundary
prediction technique to dynamically locate and ascertain this intersection
point.

Fig. 1: The pipeline of fake song generation.

F05: RVC222https://github.com/RVC-Project/Retrieval-based-Voice-Conversion-
WebUI. This is a popular project modified from VITS [14], as it focuses on
voice conversion and also shows promising result in singing voice conversion
task. RVC utilize the content vector [20] as the input and reduce tone leakage
by replacing the source feature with a training-set feature using top1
retrieval. To address the issue of muted sound, RVC incorporates a powerful
high-pitch voice extraction algorithm [21], showing promising result with
enhanced efficiency.

###  2.2 Fake song generation

In practice, fake songs not only take the form of fake singing voice but also
involve mixing with instrumental track, making detection more challenging.
Therefore, in this step, we perform the mixing with the corresponding
instrumental track, as illustrated in Fig. 1. For the F01, F02, F03, and F05
generation types, we initially employ an audio source separation
tool333https://github.com/Anjok07/ultimatevocalremovergui to isolate the raw
audio into vocal and instrumental track. Subsequently, the singing voice
conversion method is applied to convert the vocal of singer A to that of
singer B. Finally, the generated fake song is produced by combining the vocal
track and instrumental track while considering their corresponding amplitudes.
For the F04 generation type, we use
Pypinyin444https://github.com/mozillazg/python-pinyin to convert Chinese
lyrics from real songs to phonemes and let professional annotator to correct
the automatically converted phonemes to standard phonemes by listening to the
audio. Then, singing voice synthesis method is used to generate the fake
singing voice from the phoneme information. Lastly, we mix the separated
instrumental track with the fake singing voice to generate the fake song.

Table 1: Details for fake singing voice generation in FSD dataset. Method | Type | Synthesizer | Vocoder | Source | Target | Songs | Hours
---|---|---|---|---|---|---|---
F01 | SVC | SO-VITS | NSF-HifiGAN | M1/F1 | bass-1/opencpop | 100 | 5.88
F02 | SVC | SO-VITS | NSF-Snake-HifiGAN | M1/F1 | bass-1/opencpop | 100 | 5.88
F03 | SVC | SO-VITS-Diff | NSF-HifiGAN | M1/F1 | bass-1/opencpop | 100 | 5.88
F04 | SVS | DiffSinger | NSF-HifiGAN | Phoneme | M2/F2 | 100 | 5.07
F05 | SVC | RVC | NSF-HifiGAN | M3/F3 | tenor-7/alto-5 | 50 | 3.55
Fig. 2: Partition and construction of FSD dataset. The numbers in the table
correspond to the indices of the songs.

##  3 Experiments

###  3.1 Data construction details

The details for fake singing voice generation are shown in Table 1. For
F01-F03 conditions, we collect 100 real songs including one male (M1) singer
and one female (F1) singer as source domain. Subsequently, we employ the
bass-1 male singer from the M4singer dataset [22] and a female singer from the
opencpop dataset [23] to train the SO-VITS model. This enables the
transformation of singer M1 into bass-1 and singer F1 into opencpop. For F04
conditions, we collect 50 real songs including 25 different male singers, and
25 female singers and extract the phoneme information. Then, for training, we
utilize M4singer dataset to train a basic DiffSinger model and finetune on one
male singer (M2) and one female (F2) singer. For F05 conditions, we collect 50
real songs which include one male (M3) singer and one female (F3) singer as
source domain. Then, we train the RVC model using the tenor-7 male singer and
alto-5 female singer, allowing the conversion from singer M3 to tenor-7 and
singer F3 to alto-5.

###  3.2 Experiments settings

To assess the performance of current ADD models on the FSD dataset, we
segmented the fake songs into 4-second segments. We further divided the
dataset into training, development, and evaluation sets as shown in Fig. 2.
The division is based on the sequential numbering of the source domain songs,
with the first 35 songs allocated to the training set, songs 36 to 40 to the
development set, and songs 41 to 50 to the evaluation set. We create five
testing conditions, denoted as FC1 to FC5, corresponding to different fake
generation types. Each testing condition includes both the synthetic fake song
and the genuine song from their source domain. For example, FC1 comprises the
41th to 50th songs generated by F01 method, as well as the 41th to 50th songs
from the source domain, which are authentic. It is worth noting that we
employed FC5 as an unseen test set to evaluate the generalizability of the
model. This implies that there are no FC5 songs in either the training or
development sets. The number of segments in each subset is shown in Table 2.

Table 2: Number of segments in each subset Type | Train | Dev | FC1 | FC2 | FC3 | FC4 | FC5
---|---|---|---|---|---|---|---
Real | 5261 | 795 | 1131 | 1131 | 1131 | 482 | 3226
Fake | 14242 | 2094 | 1131 | 1131 | 1131 | 964 | 3226
Total | 19503 | 2889 | 2262 | 2262 | 2262 | 1446 | 6452
Table 3: EER (%) results on the full FSD test set. “AVG” represents the average EER across FC1-FC5, while “AVG↓” denotes the EER reduction from the speech-trained ADD model to the song-trained ADD model. Model | speech-trained ADD model (I) | song-trained ADD model (II) | AVG↓
---|---|---|---
19LA | FC1 | FC2 | FC3 | FC4 | FC5 | AVG | Dev | FC1 | FC2 | FC3 | FC4 | FC5 | AVG
AASIST | 0.83 | 46.50 | 45.53 | 48.62 | 46.21 | 41.75 | 45.72 | 8.68 | 8.22 | 8.66 | 8.93 | 16.85 | 23.68 | 13.27 | 32.45
Mel-LCNN | 2.68 | 47.92 | 47.74 | 49.43 | 47.30 | 44.82 | 47.44 | 10.89 | 11.40 | 11.31 | 12.82 | 21.57 | 20.42 | 15.50 | 31.94
W2V2-LCNN | 0.69 | 43.23 | 46.77 | 48.01 | 49.01 | 47.76 | 46.96 | 13.65 | 16.09 | 16.89 | 16.90 | 18.46 | 23.24 | 18.32 | 28.64
Table 4: EER (%) results on the separated vocal track of FSD test set. “AVG” represents the average EER across FC1-FC5, while “AVG↓” denotes the EER reduction from the speech-trained ADD model to the song-trained ADD model. Model | speech-trained ADD model (I) | song-trained ADD model (II) | AVG↓
---|---|---|---
19LA | FC1 | FC2 | FC3 | FC4 | FC5 | AVG | Dev | FC1 | FC2 | FC3 | FC4 | FC5 | AVG
AASIST | 0.83 | 51.45 | 50.04 | 52.87 | 48.96 | 36.36 | 47.94 | 7.65 | 7.07 | 7.26 | 6.81 | 12.24 | 31.25 | 12.93 | 35.01
Mel-LCNN | 2.68 | 48.80 | 48.27 | 49.42 | 48.13 | 46.47 | 48.22 | 14.73 | 18.30 | 18.56 | 17.77 | 25.31 | 29.82 | 21.95 | 26.27
W2V2-LCNN | 0.69 | 47.39 | 49.60 | 48.01 | 49.58 | 45.93 | 48.10 | 6.79 | 6.98 | 7.25 | 7.07 | 12.44 | 13.85 | 9.52 | 38.58

###  3.3 Implementation details

We comprehensively evaluate the FSD dataset using SOTA ADD methods, namely
AASIST [9] and LCNN [24]. In terms of features, we utilized three distinct
types: raw audio, mel spectrogram, and W2V2 representations. For the mel
spectrogram, we extracted a 128-dimensional mel spectrogram. For W2V2, we
employed the Wav2Vec-
XLS-R555https://huggingface.co/facebook/wav2vec2-xls-r-300m model with frozen
parameters, extracting the 1024-dimensional last hidden states as the feature
representation. All models are trained for 100 epochs. We used Adam optimizer
with a learning rate of $10^{-4}$ and cosine annealing learning rate decay.

##  4 Results and Discussion

###  4.1 Speech-trained ADD models results

We first assessed the efficacy of the present speech-trained ADD models using
the FSD dataset, as outlined in Table 3(I). Concretely, we conducted training
on three distinct models: AASIST, Mel-LCNN, and W2V2-LCNN, utilizing the
ASVspoof2019LA (19LA) [25] training set. From the results, we can observe that
they achieve promising result in 19LA test sets and W2V2-LCNN achieve the
lowest EER with 0.69%. Then, for FSD test sets, the results are quite
unfavorable, with all EER falling between 40% and 50%. We suppose that this
might be due to the influence of mixing the instrumental tracks. Thus, we
conduct a second experiment, where we tested the extracted vocal track of FSD
test set through audio source separation methods. The results are displayed in
Table 4(I). We observe that the results of detecting the separated vocal track
are not satisfactory. This could be attributed to the inherent limitations of
speech-driven models for cross-domain detection, especially when detecting
vocal, which contains richer pitch and rhythm information. Furthermore, both
genuine and fake songs underwent vocal track separation using the same method,
which involves upsampling convolution. This process might introduce artifacts
that affect both real and fake vocals, thereby impacting the final decision.

###  4.2 Song-trained ADD models results

Due to the poor performance of speech-trained ADD models on the FSD test set,
we proceed to train the baseline models using the FSD training set. The
results are presented in the Table 3(II). In comparison to the speech-trained
models, the AASIST, Mel-LCNN, and W2V2-LCNN models exhibited reductions in
average EER of 32.45%, 31.94%, and 28.64%, respectively, on the FSD full test
set. Among these, AASIST achieved the best average EER of 13.27%. Since the
validation set includes domain information for FC1-FC4, their EER performances
are similar. However, the genuine source domain of FC4 includes real songs
from out-of-domains, resulting in slightly worse performance than FC1-FC3. For
the unseen condition FC5, the performance of three baseline models is not
particularly strong, which indicate that the current models lack the
generalization ability to detect out-of-domain songs effectively.

Similarly, we also evaluate the performance of the separated vocal tracks as
shown in Table 4(II). In comparison with the results for full test set, we
observed a significant improvement in performance for the W2V2-LCNN, achieving
a lowest EER of 9.52% and a highest 38.58% average EER reduction compared to
the speech-trained W2V2-LCNN. This indicates that W2V2 features hold certain
advantages in vocal-level discrimination similar to their performance in
speech deepfake detection. Furthermore, under the unseen condition of FC5,
W2V-LCNN maintains a low EER value of 13.85%, which demonstrates the strong
generalization characteristics of W2V2 features even when applied to vocal
domain.

##  5 Conclusion

In this paper, we propose fake song detection (FSD) dataset for song deepfake
detection task. We constructed the novel song dataset utilizing five of the
most popular and expressive generation methods. With this dataset, we first
investigate the performance of SOTA ADD methods for song deepfake detection
task. Due to the unsatisfactory outcomes achieved by speech-trained ADD
methods, we turned to training with the FSD dataset. Specifically, we employed
both the original songs and the vocal tracks separated through audio source
separation for training and testing. Experimental results reveal the
effectiveness of training with the separated vocal track, with the W2V2-LCNN
model achieving the lowest EER of 9.52%. Future work will encompass the
incorporation of a wider range of generation methods and the development of
novel detection algorithms specifically to the task of song deepfake
detection.

## References

  * [1] Jinglin Liu, Chengxi Li, Yi Ren, Feiyang Chen, and Zhou Zhao,  “Diffsinger: Singing voice synthesis via shallow diffusion mechanism,”  in Proceedings of the AAAI conference on artificial intelligence, 2022, vol. 36, pp. 11020–11028.
  * [2] Jiawei Chen, Xu Tan, Jian Luan, Tao Qin, and Tie-Yan Liu,  “Hifisinger: Towards high-fidelity neural singing voice synthesis,”  arXiv preprint arXiv:2009.01776, 2020.
  * [3] Yi Ren, Xu Tan, Tao Qin, Jian Luan, Zhou Zhao, and Tie-Yan Liu,  “Deepsinger: Singing voice synthesis with data mined from the web,”  in Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2020, pp. 1979–1989.
  * [4] Tejas Jayashankar, Jilong Wu, Leda Sari, David Kant, Vimal Manohar, and Qing He,  “Self-supervised representations for singing voice conversion,”  in ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2023, pp. 1–5.
  * [5] Adam Polyak, Lior Wolf, Yossi Adi, and Yaniv Taigman,  “Unsupervised cross-domain singing voice conversion,”  arXiv preprint arXiv:2008.02830, 2020.
  * [6] Chengqi Deng, Chengzhu Yu, Heng Lu, Chao Weng, and Dong Yu,  “Pitchnet: Unsupervised singing voice conversion with pitch adversarial network,”  in ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2020, pp. 7749–7753.
  * [7] H. Delgado, N. Evans, T. Kinnunen, K. Lee, X. Liu, A. Nautsch, J. Patino, M. Sahidullah, M. Todisco, X. Wang, et al.,  “Asvspoof 2021: Automatic speaker verification spoofing and countermeasures challenge evaluation plan,”  arXiv preprint arXiv:2109.00535, 2021.
  * [8] Jiangyan Yi, Ruibo Fu, Jianhua Tao, Shuai Nie, Haoxin Ma, Chenglong Wang, Tao Wang, Zhengkun Tian, Ye Bai, Cunhang Fan, et al.,  “Add 2022: the first audio deep synthesis detection challenge,”  in ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2022, pp. 9216–9220.
  * [9] Jee-weon Jung, Hee-Soo Heo, Hemlata Tak, Hye-jin Shim, Joon Son Chung, Bong-Jin Lee, Ha-Jin Yu, and Nicholas Evans,  “Aasist: Audio anti-spoofing using integrated spectro-temporal graph attention networks,”  in ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2022, pp. 6367–6371.
  * [10] Alexei Baevski, Yuhao Zhou, Abdelrahman Mohamed, and Michael Auli,  “wav2vec 2.0: A framework for self-supervised learning of speech representations,”  Advances in neural information processing systems, vol. 33, pp. 12449–12460, 2020.
  * [11] Youngsik Eom, Yeonghyeon Lee, Ji Sub Um, and Hoi Rin Kim,  “Anti-Spoofing Using Transfer Learning with Variational Information Bottleneck,”  in Proc. Interspeech 2022, 2022, pp. 3568–3572.
  * [12] Juan M Martín-Doñas and Aitor Álvarez,  “The vicomtech audio deepfake detection system based on wav2vec2 for the 2022 add challenge,”  in ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2022, pp. 9241–9245.
  * [13] Nicolas Müller, Pavel Czempin, Franziska Diekmann, Adam Froghyar, and Konstantin Böttinger,  “Does Audio Deepfake Detection Generalize?,”  in Proc. Interspeech 2022, 2022, pp. 2783–2787.
  * [14] Jaehyeon Kim, Jungil Kong, and Juhee Son,  “Conditional variational autoencoder with adversarial learning for end-to-end text-to-speech,”  in International Conference on Machine Learning. PMLR, 2021, pp. 5530–5540.
  * [15] Benjamin van Niekerk, Marc-André Carbonneau, Julian Zaïdi, Matthew Baas, Hugo Seuté, and Herman Kamper,  “A comparison of discrete and soft speech units for improved voice conversion,”  in ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2022, pp. 6562–6566.
  * [16] J. Kong, J. Kim, and J. Bae,  “Hifi-gan: Generative adversarial networks for efficient and high fidelity speech synthesis,”  Advances in Neural Information Processing Systems, vol. 33, pp. 17022–17033, 2020.
  * [17] Xin Wang, Shinji Takaki, and Junichi Yamagishi,  “Neural source-filter-based waveform model for statistical parametric speech synthesis,”  in ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2019, pp. 5916–5920.
  * [18] Liu Ziyin, Tilman Hartwig, and Masahito Ueda,  “Neural networks fail to learn periodic functions and how to fix it,”  Advances in Neural Information Processing Systems, vol. 33, pp. 1583–1594, 2020.
  * [19] Jonathan Ho, Ajay Jain, and Pieter Abbeel,  “Denoising diffusion probabilistic models,”  Advances in Neural Information Processing Systems, vol. 33, pp. 6840–6851, 2020.
  * [20] Kaizhi Qian, Yang Zhang, Heting Gao, Junrui Ni, Cheng-I Lai, David Cox, Mark Hasegawa-Johnson, and Shiyu Chang,  “Contentvec: An improved self-supervised speech representation by disentangling speakers,”  in International Conference on Machine Learning. PMLR, 2022, pp. 18003–18017.
  * [21] Haojie Wei, Xueke Cao, Tangpeng Dan, and Yueguo Chen,  “Rmvpe: A robust model for vocal pitch estimation in polyphonic music,”  arXiv preprint arXiv:2306.15412, 2023.
  * [22] Lichao Zhang, Ruiqi Li, Shoutong Wang, Liqun Deng, Jinglin Liu, Yi Ren, Jinzheng He, Rongjie Huang, Jieming Zhu, Xiao Chen, et al.,  “M4singer: A multi-style, multi-singer and musical score provided mandarin singing corpus,”  Advances in Neural Information Processing Systems, vol. 35, pp. 6914–6926, 2022.
  * [23] Yu Wang, Xinsheng Wang, Pengcheng Zhu, Jie Wu, Hanzhao Li, Heyang Xue, Yongmao Zhang, Lei Xie, and Mengxiao Bi,  “Opencpop: A high-quality open source chinese popular song corpus for singing voice synthesis,”  arXiv preprint arXiv:2201.07429, 2022.
  * [24] G. Lavrentyeva, Andzhukaev Novoselov, S., M. Volkova, A. Gorlanov, and A. Kozlov,  “Stc antispoofing systems for the asvspoof2019 challenge,”  arXiv preprint arXiv:1904.05576, 2019.
  * [25] Massimiliano Todisco, Xin Wang, Ville Vestman, Md. Sahidullah, Héctor Delgado, Andreas Nautsch, Junichi Yamagishi, Nicholas Evans, Tomi H. Kinnunen, and Kong Aik Lee,  “ASVspoof 2019: Future Horizons in Spoofed and Fake Audio Detection,”  in Proc. Interspeech 2019, 2019, pp. 1008–1012.