Jiatong Shi1∗,††thanks: ∗Equal Contribution. Yueqian Lin2∗, Xinyi Bai3,4, Keyi
Zhang, Yuning Wu5,
Yuxun Tang5, Yifeng Yu6, Qin Jin5, Shinji Watanabe1 [datatype=bibtex,
overwrite=true] [fieldsource=booktitle, match=.*Interspeech.*, replace=Proc.
Interspeech] [fieldsource=journal, match=.*INTERSPEECH.*, replace=Proc.
Interspeech] [fieldsource=booktitle, match=.*ICASSP.*, replace=Proc. ICASSP]
[fieldsource=booktitle, match=.*icassp_inpress.*, replace=Proc. ICASSP (in
press)] [fieldsource=booktitle,
match=.*Acoustics,.*Speech.*and.*Signal.*Processing.*, replace=Proc. ICASSP]
[fieldsource=booktitle,
match=.*International.*Conference.*on.*Learning.*Representations.*,
replace=Proc. ICLR] [fieldsource=booktitle,
match=.*International.*Conference.*on.*Computational.*Linguistics.*,
replace=Proc. COLING] [fieldsource=booktitle,
match=.*SIGdial.*Meeting.*on.*Discourse.*and.*Dialogue.*, replace=Proc.
SIGDIAL] [fieldsource=booktitle,
match=.*International.*Conference.*on.*Machine.*Learning.*, replace=Proc.
ICML] [fieldsource=booktitle,
match=.*North.*American.*Chapter.*of.*the.*Association.*for.*Computational.*Linguistics:.*Human.*Language.*Technologies.*,
replace=Proc. NAACL] [fieldsource=booktitle,
match=.*Empirical.*Methods.*in.*Natural.*Language.*Processing.*, replace=Proc.
EMNLP] [fieldsource=booktitle,
match=.*Association.*for.*Computational.*Linguistics.*, replace=Proc. ACL]
[fieldsource=booktitle,
match=.*Automatic.*Speech.*Recognition.*and.*Understanding.*, replace=Proc.
ASRU] [fieldsource=booktitle, match=.*Spoken.*Language.*Technology.*,
replace=Proc. SLT] [fieldsource=booktitle,
match=.*Speech.*Synthesis.*Workshop.*, replace=Proc. SSW]
[fieldsource=booktitle, match=.*workshop.*on.*speech.*synthesis.*,
replace=Proc. SSW] [fieldsource=booktitle,
match=.*Advances.*in.*neural.*information.*processing.*, replace=Proc.
NeurIPS] [fieldsource=booktitle,
match=.*Advances.*in.*Neural.*Information.*Processing.*, replace=Proc.
NeurIPS] [fieldsource=booktitle, match=.*Workshop.*on.* Applications.* of.*
Signal.*Processing.*to.*Audio.*and.*Acoustics.*, replace=Proc. WASPAA]
[fieldsource=publisher, match=.+, replace=] [fieldsource=month, match=.+,
replace=] [fieldsource=location, match=.+, replace=] [fieldsource=address,
match=.+, replace=] [fieldsource=organization, match=.+, replace=]

# Singing Voice Data Scaling-up:
An Introduction to ACE-Opencpop and KiSing-v2

###### Abstract

In singing voice synthesis (SVS), generating singing voices from musical
scores faces challenges due to limited data availability, a constraint less
common in text-to-speech (TTS). This study proposes a new approach to address
this data scarcity. We utilize an existing singing voice synthesizer for data
augmentation and apply precise manual tuning to reduce unnatural voice
synthesis. Our development of two extensive singing voice corpora, ACE-
Opencpop and KiSing-v2, facilitates large-scale, multi-singer voice synthesis.
Utilizing pre-trained models derived from these corpora, we achieve notable
improvements in voice quality, evident in both in-domain and out-of-domain
scenarios. The corpora, pre-trained models, and their related training recipes
are publicly available at Muskits-ESPnet (https://github.com/espnet/espnet).

Index Terms: singing voice synthesis, singing dataset, multi-singer singing
voice synthesis, transfer learning

##  1 Introduction

Singing voice synthesis (SVS) has emerged as an active research field within
artificial intelligence-generated content (AIGC), focusing on synthesizing
singing voices from provided musical scores, which includes aligning lyrics,
pitch, and note duration [1, 2, 3]. In recent years, similar to text-to-speech
(TTS), non-autoregressive singing voice synthesis based on sequence-to-
sequence models has become the dominant approach [4, 5, 6, 7, 8, 9, 10].

However, compared to TTS, SVS research often faces limited data availability
due to strict copyright laws, the need for professional recording
environments, and extensive annotation time. Various approaches to optimize
training with limited datasets have been explored [7, 11, 12, 13, 14, 15, 16,
17]. Some studies utilize additional data sources, such as crawled data or
corpora combinations [12, 15, 13, 16, 17], others construct specialized loss
functions for training stabilization [7], and some apply data augmentation
techniques for enhanced data diversity [11].

In addition to algorithmic advancements, several benchmarks for SVS have been
proposed to address data scarcity. Early works primarily focused on single-
singer corpora [18, 19, 20].111Many databases are open-sourced without
publications, such as Amaboshi Ciphyer Utagoe DB, Yuuri Natsume Singing DB,
Ofuton P Utagoe DB, etc. More recent efforts, such as M4Singer [21], provide
multi-singer support but with limited data per singer. In [16], a
multilingual-multi-singer corpus was compiled from six different sources,
though this required additional fine-tuning on single-singer databases.

In practical applications, singing voices often undergo an editing process,
including detailed manual tuning using digital signal processing techniques or
parametric vocoders [22, 23]. As AI singing synthesizers have advanced, more
amateur and professional musicians have started utilizing manual tuning to
mitigate unnatural voices within musical signals. These tuning procedures
offer valuable insights into the challenges of existing singing synthesis
systems.

Following the use of manual voice editing, this paper leverages ACE Studio, a
popular singing synthesizer, to generate large-scale singing voice corpora for
SVS research. We focus on manual tuning to reduce unnatural voices generated
by the synthesizer. Our contributions include the ACE-Opencpop and KiSing-V2
corpora, which contain approximately 130 hours and 32.5 hours of singing
voices from 30 and 34 singers, respectively. With extensive experiments over a
range of models, we show these corpora can directly benefit SVS research if
directly used as a large-scale SVS benchmark. Meanwhile, they can be used as
augmentation for other singing benchmarks, as demonstrated in both in-domain
and out-of-domain scenarios. Both corpora are shared under the CC-BY-NC-4.0
license.

(a) Pitch Distribution of ACE-Opencpop.

(b) Pitch distribution of KiSing-V2.

Figure 1: A comparison of pitch distribution between ACE-Opencpop and
KiSing-V2. Figure 2: Duration distribution of KiSing-V2.

##  2 The Corpora

###  2.1 Curation Process

As discussed in Section 1, both corpora are synthesized using ACE Studio with
additional manual tuning. The data curation process encompasses several major
stages:

Data Preparation: The initial step involves preparing the source data, which
is essential for the data curation process. This data comprises the singing
voice of various artists, the corresponding musical scores, and phonetic
(phone) alignment. The musical score includes elements such as the sequence of
musical notes, note durations, and syllable assignments for each note. In
contrast to previous SVS benchmarks [18, 19, 20, 16], which provide phone
alignment of real singing voices for reference, our approach also incorporates
this aspect.222Notably, many SVS systems utilize the provided phone alignment
as an additional feature [20, 24, 25].

Information Verification and Correction: This stage involves enlisting
individuals with musical expertise to meticulously refine the music score,
typically in MIDI format, ensuring it accurately aligns with the singing
voice. Concurrently, these experts also rectify any discrepancies found in the
initial phone alignment of the source singing voice.

Tuning for Voice Match: In this phase, there is an iterative process of
editing the synthesized voice to achieve an optimal match with the source
voice. This involves several steps: selecting a virtual singer whose voice
closely resembles the source, modifying the fundamental frequency (F0)
contour, incorporating additional breathing sounds, adjusting the vibrato, and
fine-tuning the syllable duration. These modifications aim to ensure that the
synthesized voice faithfully replicates the original song in the source
database.

Tuning for Singer Adaptation: This process is repeated for each singer
included in our study. For ACE-Opencpop, we feature 30 singers, whereas
KiSing-V2 includes 33. All voices are generated using ACE Studio version
1.7.2, and the data format is consistent across both corpora: 48kHz, single
channel, 16-bit PCM.

###  2.2 ACE-Opencpop

The ACE-Opencpop corpus is derived from the 5.2-hour Opencpop benchmark [20]
and inherits its song list. We employ the MIDI music scores from the
benchmark, adhering to the data curation stages delineated in Section 2.1. The
voices in ACE-Opencpop are organized by song, with the capability for
segmentation aligning with the original Opencpop dataset's configuration.
Owing to the utilization of identical music scores, ACE-Opencpop exhibits the
same statistical characteristics as the original Opencpop, including song
duration, pitch distribution, and phonetic (phone) distribution.

###  2.3 KiSing-v2

KiSing-V2, an extension of the 2021 KiSing database [16], incorporates eight
additional songs by singer Kiki Zhang, complete with corresponding music
scores. Notably, this expansion introduces four English songs, rendering
KiSing-V2 a bilingual singing voice corpus. Although bilingual singing
synthesis is not the primary focus of this study, these data are included in
our public release. A distinctive feature of KiSing-V2, in comparison to
previous works, is its emphasis on frequent melisma333Melisma refers to the
technique in singing where a single syllable is extended over a sequence of
notes. techniques. Approximately 27.0% of KiSing-V2's melodies exhibit
melisma, a significant increase from the 1.5% observed in Opencpop.

We present detailed statistics of KiSing-V2 in Figures 1 and 2. As depicted in
Figure 1, while both ACE-Opencpop444ACE-Opencpop shares the same
characteristics as the original Opencpop corpus. and KiSing-V2 exhibit similar
pitch ranges, KiSing-V2 demonstrates a broader pitch coverage due to the
presence of low-frequency notes. Furthermore, KiSing-V2 comes with suggested
segmentation for song-level singing voices, and its duration distribution is
shown in Figure 2.

Table 1: Comparison between the proposed corpora and existing singing voice
benchmarks.

Dataset | Year | Language | # of Songs | Dur. (hour) | # of Singers | Dur./Singer (hour) | Lyrics | Music Score |
---|---|---|---|---|---|---|---|---|---
NIT SONG070 F001 [18] | 2015 | JP | 31 | 1.2 | 1 | 1.2 | ✓ | ✓ |
JSUT Song [26] | 2018 | JP | 27 | 0.4 | 1 | 0.4 | ✓ | ✓ |
Kiritan [19] | 2021 | JP | 50 | 1.0 | 1 | 1.0 | ✓ | ✓ |
KiSing-v1 [16] | 2021 | CN | 14 | 0.7 | 1 | 0.7 | ✓ | ✓ |
Opencpop [20] | 2022 | CN | 100 | 5.2 | 1 | 5.2 | ✓ | ✓ |
PopCS [8] | 2022 | CN | 117 | 5.9 | 1 | 5.9 | ✓ | ✗ |
M1R-1K [27] | 2010 | CN | 1000 | 2.2 | 19 | 0.1 | ✓ | ✓ |
NUS-48E [28] | 2013 | EN | 48 | 1.9 | 12 | 0.2 | ✓ | ✗ |
NHSS [29] | 2019 | EN | 100 | 4.8 | 10 | 0.5 | ✓ | ✗ |
JVS-MuSiC [30] | 2020 | JP | 2 | 2.3 | 100 | 0.2 | ✓ | ✗ |
OpenSinger [31] | 2021 | CN | 1146 | 50.0 | 66 | 0.8 | ✓ | ✗ |
M4Singer [21] | 2022 | CN | 700 | 29.8 | 20 | 1.5 | ✓ | ✓ |
SingStyle111 [32] | 2023 | CN/EN/IT | 224 | 12.8 | 8 | 1.6 | ✓ | ✓ |
ACE-Opencpop | - | CN | 100 | 128.9 | 30 | 4.3 | ✓ | ✓ |
KiSing-V2 | - | CN/EN | 23 | 32.5 | 34 | 1.0 | ✓ | ✓ |

###  2.4 Comparison to Other Corpora

As highlighted in Section 1, the field of singing voice processing has
witnessed several significant contributions in open-source benchmarks. In
Table 1, we summarize some representative corpora that incorporate singing
voices in their collections.

A common limitation, as Table 1 illustrates, is that many databases featuring
singing voices either lack explicit music score information or offer
insufficient data per singer for robust singing synthesis research. These
datasets are predominantly tailored for tasks like music information
retrieval, singing voice conversion, or singing-focused vocoding [27, 28, 29,
30, 31]. In SVS contexts, previous studies have mitigated these limitations by
extracting pitch directly from the singing voice and using these pitch
sequences as surrogate music score information [8]. However, this method
inherently requires a reference singing voice for the synthesis process,
aligning it more closely with singing voice conversion applications.

Databases that do provide comprehensive music score information are typically
limited to single-singer recordings [8, 20, 16, 26, 19, 18]. In contrast,
M4Singer [21] and SingStyle111 [32] feature 20 and 8 singers, respectively,
but offer less than 2 hours of singing voice per artist.

In comparison, ACE-Opencpop and KiSing-V2 stand out with their coverage of
approximately 30 singers each, representing the broadest singer diversity in
SVS corpora. Moreover, ACE-Opencpop offers an extensive data size exceeding
100 hours, facilitating large-scale singing synthesis research. KiSing-V2 is
particularly notable for its focus on the melisma technique, offering a unique
dimension to singing voice studies.

##  3 Experiments

###  3.1 Experimental Models

To fully investigate the proposed corpora, we use four different models
supported by Muskits-ESPnet [16], including recurrent neural network
(RNN)-based SVS [7], Xiaoice [5], VISinger [9], and VISinger2 [10]:

  * •

RNN: The RNN-based model follows the non-autoregressive design and employs RNN
layers in both the encoder and decoder as the backbone [7]. The sequence-to-
sequence process is achieved by a length regulator which extends the encoder
output to the length of target signal lengths. In our experiments, we utilize
the same architecture and training configuration as outlined in the Opencpop
recipe555https://github.com/espnet/espnet/blob/master/egs2/opencpop/svs1. To
conduct close-set multi-singer SVS, we add additional singer ID embedding to
the extended encoder output after the length regulation. The singer ID
embedding is set to 256 dimensions.

  * •

Xiaoice: The Xiaoice model follows the XiaoiceSing2 [33] by using conformer
blocks [34, 35] in both the encoder and decoder. Additionally, voice/unvoiced
and log F0 prediction losses are added along with the Mel spectrogram
prediction. For multi-singer SVS, the singer ID embedding is repeated along
the time axis and concatenated with the hidden states before feeding to the
decoder. Other hyperparameters in the network architecture and training are
the same as the Xiaoice configuration in the Opencpop recipe.

  * •

VISinger: The VISinger model is an extension of the VITS model in TTS [36, 9].
The model applies conditional variational auto-encoder, jointly training with
adversarial objectives. In addition to VITS, the model accepts the music score
information as its input and utilizes a frame prior network with pitch
prediction to facilitate the flow learning process. We follow the same
configuration as defined in the ESPnet-Muskits. As to support the multi-singer
SVS, the singer ID embedding is used as the global information in the VITS
implementation, which is used in both the generator and discriminators.

  * •

VISinger2: The VISinger2 model further enhances the VISinger by using a
differentiable digital signal processing vocoder. We follow the same
configuration as in the Opencpop recipe. The singer embedding is injected in
the same way as VISinger.

For models that need additional vocoders, we pre-trained a 250k steps HiFi-GAN
vocoder[37] on corresponding corpora. Detailed parameters follow the open-
source ParallelWaveGAN repository666https://github.com/kan-
bayashi/ParallelWaveGAN/blob/master/egs/opencpop/voc1/conf/hifigan.v1.yaml. To
evaluate the models in different sampling rates, we conduct cascaded acoustic
models with the vocoder (i.e., RNN and Xiaoice) in 24kHz and 44.1kHz for end-
to-end SVS systems (i.e., VISinger and VISinger2).

###  3.2 Experimental Setup

To assess the efficacy of the corpora, we explore their application in
transfer learning contexts. Specifically, we fine-tune pre-trained SVS systems
of the corpora for other SVS benchmarks, with different model architectures
detailed in Section 3.1. This process demonstrates the practical utility of
the corpora.

In the ACE-Opencpop transfer learning experiments, we adapt the aforementioned
four pre-trained systems to assess whether ACE-Opencpop can effectively
complement other SVS corpora. Our evaluation covers two scenarios: an in-
domain scenario utilizing Opencpop, and an out-domain scenario employing
Kiritan.777There is a significant domain mismatch between ACE-Opencpop, which
focuses on Mandarin Pop songs, and Kiritan, primarily associated with Japanese
Animation songs. For a comprehensive comparison, we also examine SVS systems
trained solely on the original databases using the same model architectures.

In the context of KiSing-V2, we extend our evaluation to include only
VISinger2, incorporating transfer learning. The pre-trained models include
both original singing voices and augmented versions. Following the procedure
outlined in [16], we fine-tune the model exclusively on the original voices.
For a balanced evaluation, model trained solely on Kiki's original voices is
also compared.

Table 2: In-domain transfer learning experiments with Opencpop. * indicates
the use of pre-trained ACE-Opencpop models. 95% confidence intervals of MOS
are presented in parentheses.

Model | MCD $\downarrow$ | S. Acc. $\uparrow$ | F0 RMSE $\downarrow$ | MOS $\uparrow$
---|---|---|---|---
RNN | 8.85 | 56.94 | 0.306 | 2.96 ($\pm$ 0.06)
RNN* | 8.92 | 60.27 | 0.236 | 3.22 ($\pm$ 0.06)
Xiaoice | 9.26 | 59.22 | 0.185 | 2.78 ($\pm$ 0.03)
Xiaoice* | 8.78 | 60.72 | 0.182 | 3.08 ($\pm$ 0.05)
VISinger | 7.71 | 64.41 | 0.171 | 3.54 ($\pm$ 0.07)
VISinger* | 7.60 | 64.70 | 0.168 | 3.68 ($\pm$ 0.07)
VISinger2 | 7.54 | 64.50 | 0.172 | 3.63 ($\pm$ 0.07)
VISinger2* | 7.26 | 65.18 | 0.162 | 3.66 ($\pm$ 0.06)
G.T. | - | - | - | 4.69 ($\pm$ 0.06)

Table 3: Out-domain transfer learning experiments with Kiritan-singing. *
indicates the use of pre-trained ACE-Opencpop models. 95% confidence intervals
of MOS are presented in parentheses.

Model | MCD $\downarrow$ | S. Acc. $\uparrow$ | F0 RMSE $\downarrow$ | MOS $\uparrow$
---|---|---|---|---
VISinger | 7.46 | 49.73 | 0.115 | 3.45 ($\pm$ 0.06)
VISinger* | 7.51 | 50.04 | 0.114 | 3.59 ($\pm$ 0.07)
VISinger2 | 7.47 | 49.33 | 0.123 | 3.58 ($\pm$ 0.07)
VISinger2* | 7.54 | 50.88 | 0.122 | 3.68 ($\pm$ 0.07)
G.T. | - | - | - | 4.57 ($\pm$ 0.07)

###  3.3 Evaluation Metrics

We perform both objective and subjective evaluations on the synthesized
samples. In the objective evaluation, we employ mean cepstral distortion
(MCD), semitone accuracy (S. Acc.), and logarithmic F0 root mean square error
(F0 RMSE) as metrics. These metrics align with the standards set in previous
studies [16, 11, 25, 24]. For the subjective evaluation, we conduct a Mean
Opinion Score (MOS) test. To obtain the MOS, we randomly select 30 synthesized
samples from each system. These samples are then assessed by 30 subjects using
a 5-point scale, ranging from 1 (unreasonable singing) to 5 (natural singing
comparable to human performance).

###  3.4 Results and Discussion

Tables 2 and 3 display the outcomes of the in-domain and out-domain transfer
experiments, respectively. The data in Table 2 reveal that employing the pre-
trained model from ACE-Opencpop enhances both objective and subjective
performance metrics in SVS. VISinger achieves a notable improvement in
subjective evaluation, even surpassing VISinger2 in MOS. This outcome suggests
that data scaling may alter some previously held conclusions in small-scale
singing synthesis. Compared to cascaded approaches (e.g., RNN and Xiaoice),
end-to-end methods like VISinger and VISinger2 consistently yield superior
results, corroborating findings from previous studies [9, 10]. Nevertheless, a
substantial discrepancy persists between the highest-quality synthesized
voices and actual singing, indicating ample room for advancements in SVS
systems.

In the out-domain transfer learning experiments, as shown in Table 3, the
application of the pre-trained model does not result in improvements in MCD
metrics. However, we note reasonable enhancements in S. Acc, F0 RMSE, and
subjective MOS. Given the substantial domain disparity between the two
corpora, the pre-trained model evidently aids in generating more natural
singing voices, as evidenced by significant improvements in metrics other than
MCD.

Table 4 presents the results from the KiSing-V2 transfer scenarios. Echoing
the ACE-Opencpop experiments, models pre-trained with augmented voices
consistently perform better or comparably in both objective and subjective
evaluations. While the objective metrics show less pronounced improvements in
aspects like F0 RMSE, the S. Acc. and MOS scores exhibit notable differences.
This discrepancy may stem from the melisma technique prevalent in the
KiSing-V2 dataset, which tends to impact subjective listening quality more
significantly than objective scores in F0 RMSE.

###  3.5 Further Discussion

Table 5 provides an objective evaluation of various pre-trained models.
Notably, M4Singer, as cataloged in Table 1, was the most extensive SVS corpus
available prior to the release of ACE-Opencpop. The results interestingly
reveal that simply fine-tuning the model pre-trained on M4Singer does not
uniformly enhance the objective metrics. In contrast, the model pre-trained on
ACE-Opencpop consistently shows substantial improvements. This distinction
underscores the significance of ACE-Opencpop, not just as a standalone corpus
but as a valuable augmentation resource for SVS tasks.

Table 4: KiSing-V2 (original) transfer learning experiments. + indicates the
use of pre-trained KiSing-V2 (all) models. 95% confidence intervals of MOS are
presented in parentheses.

Model | MCD $\downarrow$ | S. Acc. $\uparrow$ | F0 RMSE $\downarrow$ | MOS $\uparrow$
---|---|---|---|---
VISinger2 | 5.55 | 68.12 | 0.168 | 3.58 ($\pm$ 0.07)
VISinger2+ | 4.99 | 72.51 | 0.170 | 3.83 ($\pm$ 0.10)
G.T. | - | - | - | 4.51 ($\pm$ 0.07)

Table 5: Ablation study of using models from M4Singer. * indicates the use of
pre-trained ACE-Opencpop models and △ indicates the use of pre-trained
M4Singer models.

Model | MCD $\downarrow$ | S. Acc. $\uparrow$ | F0 RMSE $\downarrow$
---|---|---|---
VISinger | 7.71 | 64.41 | 0.171
VISinger△ | 7.83 | 63.13 | 0.172
VISinger* | 7.60 | 64.70 | 0.168
VISinger2 | 7.54 | 64.50 | 0.172
VISinger2△ | 8.51 | 60.54 | 0.195
VISinger2* | 7.26 | 65.18 | 0.162

##  4 Conclusion

In this work, we present ACE-Opencpop and KiSing-V2, two corpora for singing
synthesis. The two corpora are augmented with ACE-Studio and manual tuning
procedures. Through extensive experiments, our findings highlight the
potential of ACE-Opencpop and KiSing-V2 in enriching and advancing the field
of SVS, particularly in the context of transfer learning.

##  5 Acknowledgements

Experiments of this work used the Bridges2 system at PSC and Delta system at
NCSA through allocations CIS210014 and IRI120008P from the Advanced
Cyberinfrastructure Coordination Ecosystem: Services & Support (ACCESS)
program, supported by NSF grants #2138259, #2138286, #2138307, #2137603, and
#2138296. We would like to thank Shengyuan Xu and Pengcheng Zhu for their
support in the data license.

##  6 References

## References

  * [1] Perry R Cook  ``Singing voice synthesis: History, current work, and future directions''  In _Computer Music Journal_ , 1996
  * [2] Yukiya Hono, Kei Hashimoto and Keiichiro Oura  ``Sinsy: A deep neural network-based singing voice synthesis system''  In _IEEE/ACM TASLP_ , 2021
  * [3] Hideki Kenmochi and Hayato Ohshita  ``VOCALOID-commercial singing synthesizer based on sample concatenation.''  In _Proc. Interspeech_ , 2007
  * [4] Yu Gu, Xiang Yin, Yonghui Rao, Yuan Wan, Benlai Tang, Yang Zhang, Jitong Chen, Yuxuan Wang and Zejun Ma  ``Bytesing: A Chinese singing voice synthesis system using duration allocated encoder-decoder acoustic models and WaveRNN vocoders''  In _ISCSLP_ , 2021, pp. 1–5
  * [5] Peiling Lu, Jie Wu and Jian Luan  ``XiaoiceSing: A High-Quality and Integrated Singing Voice Synthesis System''  In _Interspeech_ , 2020
  * [6] Merlijn Blaauw and Jordi Bonada  ``Sequence-to-Sequence Singing Synthesis Using the Feed-Forward Transformer''  In _Proc. ICASSP_ , 2020
  * [7] Jiatong Shi, Shuai Guo and Nan Huo  ``Sequence-To-Sequence Singing Voice Synthesis With Perceptual Entropy Loss''  In _Proc. ICASSP_ , 2021
  * [8] Jinglin Liu, Chengxi Li and Yi Ren  ``DiffSinger: Singing voice synthesis via shallow diffusion mechanism''  In _AAAI_ , 2022
  * [9] Yongmao Zhang, Jian Cong and Heyang Xue  ``VISinger: Variational Inference with Adversarial Learning for End-to-End Singing Voice Synthesis''  In _Proc. ICASSP_ , 2022
  * [10] Yongmao Zhang, Heyang Xue, Hanzhao Li, Lei Xie, Tingwei Guo, Ruixiong Zhang and Caixia Gong  ``VISinger2: High-Fidelity End-to-End Singing Voice Synthesis Enhanced by Digital Signal Processing Synthesizer''  In _Proc. INTERSPEECH 2023_ , 2023, pp. 4444–4448  DOI: 10.21437/Interspeech.2023-391
  * [11] Shuai Guo, Jiatong Shi and Tao Qian  ``SingAug: Data Augmentation for Singing Voice Synthesis with Cycle-consistent Training Strategy''  In _Proc. Interspeech_ , 2022
  * [12] Yi Ren, Xu Tan and Tao Qin  ``Deepsinger: Singing voice synthesis with data mined from the web''  In _ACM SIGKDD_ , 2020
  * [13] Soonbeom Choi and Juhan Nam  ``A melody-unsupervision model for singing voice synthesis''  In _Proc. ICASSP_ , 2022, pp. 7242–7246
  * [14] Zhiqing Hong, Chenye Cui, Rongjie Huang, Lichao Zhang, Jinglin Liu, Jinzheng He and Zhou Zhao  ``UniSinger: Unified End-to-End Singing Voice Synthesis With Cross-Modality Information Matching''  In _Proceedings of the 31st ACM International Conference on Multimedia_ , 2023, pp. 7569–7579
  * [15] Heyang Xue, Shan Yang, Yi Lei, Lei Xie and Xiulin Li  ``Learn2sing: Target speaker singing voice synthesis by learning from a singing teacher''  In _Proc. SLT_ , 2021, pp. 522–529
  * [16] Jiatong Shi, Shuai Guo and Tao Qian  ``Muskits: an End-to-End Music Processing Toolkit for Singing Voice Synthesis''  In _Proc. Interspeech_ , 2022
  * [17] Huali Zhou, Yueqian Lin and Yao Shi  ``BiSinger: Bilingual singing voice synthesis''  In _Proc. ASRU_ , 2023
  * [18] Keijiro Saino, Heiga Zen and Yoshihiko Nankaku  ``An HMM-based singing voice synthesis system''  In _SLT_ , 2006
  * [19] Itsuki Ogawa and Masanori Morise  ``Tohoku Kiritan singing database: A singing database for statistical parametric singing synthesis using Japanese pop songs''  In _Acoustical Science and Technology_ 42.3, 2021, pp. 140–145
  * [20] 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''  In _Proc. Interspeech_ , 2022, pp. 4242–4246  DOI: 10.21437/Interspeech.2022-48
  * [21] Lichao Zhang, Ruiqi Li, Shoutong Wang, Liqun Deng, Jinglin Liu, Yi Ren, Jinzheng He, Rongjie Huang, Jieming Zhu and Xiao Chen  ``M4Singer: A Multi-Style, Multi-Singer and Musical Score Provided Mandarin Singing Corpus''  In _Proc. NeurIPS_ , 2022, pp. 6914–6926
  * [22] Simon Langford  ``Digital audio editing: correcting and enhancing audio in Pro Tools, Logic Pro, Cubase, and Studio One'', 2013
  * [23] Wallace Jackson  ``Digital audio editing fundamentals'', 2015
  * [24] Yuning Wu, Yifeng Yu, Jiatong Shi, Tao Qian and Qin Jin  ``A Systematic Exploration of Joint-training for Singing Voice Synthesis''  In _arXiv preprint arXiv:2308.02867_ , 2023
  * [25] Yuning Wu, Jiatong Shi, Tao Qian, Dongji Gao and Qin Jin  ``Phoneix: Acoustic Feature Processing Strategy for Enhanced Singing Pronunciation With Phoneme Distribution Predictor''  In _Proc. ICASSP_ , 2023, pp. 1–5
  * [26] ``JSUT Song Corpus'' Accessed: 2024-01-22  URL: https://sites.google.com/site/shinnosuketakamichi/publication/jsut-song
  * [27] Chao-Ling Hsu and Jyh-Shing Roger Jang  ``On the Improvement of Singing Voice Separation for Monaural Recordings Using the MIR-1K Dataset''  In _IEEE Transactions on Audio, Speech, and Language Processing_ 18.2, 2010, pp. 310–319  DOI: 10.1109/TASL.2009.2026503
  * [28] Zhiyan Duan, Haotian Fang, Bo Li, Khe Chai Sim and Ye Wang  ``The NUS sung and spoken lyrics corpus: A quantitative comparison of singing and speech''  In _2013 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference_ , 2013, pp. 1–9
  * [29] Bidisha Sharma, Xiaoxue Gao, Karthika Vijayan, Xiaohai Tian and Haizhou Li  ``NHSS: A speech and singing parallel database''  In _Speech Communication_ 133, 2021, pp. 9–22  DOI: https://doi.org/10.1016/j.specom.2021.07.002
  * [30] Hiroki Tamaru, Shinnosuke Takamichi, Naoko Tanji and Hiroshi Saruwatari  ``JVS-MuSiC: Japanese multispeaker singing-voice corpus''  In _arXiv preprint arXiv:2001.07044_ , 2020
  * [31] Rongjie Huang, Feiyang Chen, Yi Ren, Jinglin Liu, Chenye Cui and Zhou Zhao  ``Multi-Singer: Fast Multi-Singer Singing Voice Vocoder With A Large-Scale Corpus''  In _Proceedings of the 29th ACM International Conference on Multimedia_ , MM '21, 2021, pp. 3945–3954
  * [32] Shuqi Dai, Yuxuan Wu, Siqi Chen, Roy Huang and Roger B Dannenberg  ``SingStyle111: A Multilingual Singing Dataset With Style Transfer''  In _ISMIR 2023 Hybrid Conference_ , 2023
  * [33] Wang Chunhui, Chang Zeng and Xing He  ``Xiaoicesing 2: A High-Fidelity Singing Voice Synthesizer Based on Generative Adversarial Network''  In _Proc. Interspeech_ , 2023, pp. 5401–5405  DOI: 10.21437/Interspeech.2023-119
  * [34] Anmol Gulati et al.  ``Conformer: Convolution-augmented Transformer for Speech Recognition''  In _Proc. Interspeech_ , 2020, pp. 5036–5040  DOI: 10.21437/Interspeech.2020-3015
  * [35] Pengcheng Guo, Florian Boyer, Xuankai Chang, Tomoki Hayashi, Yosuke Higuchi, Hirofumi Inaguma, Naoyuki Kamo, Chenda Li, Daniel Garcia-Romero and Jiatong Shi  ``Recent developments on espnet toolkit boosted by conformer''  In _Proc. ICASSP_ , 2021, pp. 5874–5878
  * [36] Jaehyeon Kim, Jungil Kong and Juhee Son  ``Conditional variational autoencoder with adversarial learning for end-to-end text-to-speech''  In _Proc. ICML_ , 2021, pp. 5530–5540
  * [37] Jungil Kong, Jaehyeon Kim and Jaekyoung Bae  ``HiFi-GAN: Generative adversarial networks for efficient and high fidelity speech synthesis''  In _NeurIPS_ , 2020


# SparRL: Graph Sparsification via Deep Reinforcement Learning

David S. Hippocampus
Department of Computer Science
Cranberry-Lemon University
Pittsburgh, PA 15213
<EMAIL_ADDRESS>
Use footnote for providing further information about author (webpage,
alternative address)— _not_ for acknowledging funding agencies.

###### Abstract

Graph sparsification concerns data reduction where an edge-reduced graph of a
similar structure is preferred. Existing methods are mostly sampling-based,
which introduce high computation complexity in general and lack of flexibility
for a different reduction objective. We present SparRL, the first general and
effective reinforcement learning-based framework for graph sparsification.
SparRL can easily adapt to different reduction goals and promise graph-size-
independent complexity. Extensive experiments show that SparRL outperforms all
prevailing sparsification methods in producing high-quality sparsified graphs
concerning a variety of objectives.

##  1 Introduction

Graphs are the natural abstraction of complex correlations found in numerous
domains including social media (Borgatti et al., 2009), communications (Chang,
2000), transportation and telematics (Li et al., 2017b; Lin et al., 2019b),
and medicine discovery (Barabási et al., 2011). Consequently, different types
of graphs have been a main topic in many scientific disciplines such as
computer science, mathematics, engineering, sociology, and economics. The
study of the interconnectedness of the graphs can lead to local/global
information inferring as well as latent structure discovery, thus benefiting
various downstream applications. However, the complexity of subject graphs in
modern studies tends to ever-increase because of the explosive growth of the
Internet and our computing capabilities. These features cause the exploration,
analysis, and utilization of a graph very inefficient.

Thus, the topic _graph sparsification_ has emerged in the past two decades
(Batson et al., 2013; Teng, 2016), where the objective is to prune edges from
a graph to produce a sparsified graph while preserving user-defined metrics in
query evaluation or knowledge inferring. As an example, commonly adopted
metrics include the graph spectrum and the effective resistance of edges
(Spielman & Srivastava, 2011; Spielman & Teng, 2011). Sparsification
techniques developed w.r.t these metrics have been applied to domains such as
power grid management (Zhao et al., 2014; Zhao & Feng, 2017), integrated
circuit simulation (Zhao et al., 2015), and influence maximization (Shen et
al., 2017; Mathioudakis et al., 2011).

Nevertheless, most graph sparsification techniques exist to-date are sampling-
based (Fung et al., 2019). While effective, they all introduce high
computation complexity (due the involvement of many matrix operations) and
lack the flexibility to preserve different graph properties in many
applications (since the sampling technique needs to be tailored for each
application), e.g., approximate graph analysis (Iyer et al., 2018; Ahn et al.,
2012; Satuluri et al., 2011a; Zhao, 2015), privacy preserving (Upadhyay, 2013;
Arora & Upadhyay, 2019), and representation learning (Calandriello et al.,
2018). Thus, a general, flexible graph sparsification technique for various
reduction objectives and application domains is highly desired.

We present SparRL, a general graph sparsification framework empowered by deep
reinforcement learning (RL) that can be applied to any edge sparsification
task with a customized reduction goal. Consider the example shown in Figure 1,
by setting modularity preservation as the edge reduction objective, SparRL can
prune a user-defined amount of edges from the original graph and still
preserve the substructure modularity. To improve learning efficiency and
convergence rate of SparRL, we place the RL agent to different initial states
by randomly sparsifying the original graph before each training episode, use
Double DQN (Van Hasselt et al., 2016) with Prioritized Replay (Schaul et al.,
2015), and employ $\epsilon$-greedy exploration strategy for the optimal
pruning behavior.

(a) Original Karate

(b) Karate (80% edge kept)

(c) Karate (60% edge kept)

Figure 1: Applying SparRL to Zachary’s karate club (Zachary, 1977) graph by
setting modularity preservation the edge reduction goal. Different colors
denote different modularity-based partitions, while a node size scales with
its degree. Modularity partition computed and plotted with Gephi (Bastian et
al., 2009)

We test SparRL on a wide range of graphs and metrics including PageRank,
community structure, and pairwise shortest-path distance. From our extensive
experiments, SparRL outperforms all baseline methods on preserving PageRank,
community structure, and single-pair shortest path (SPSP) at a variety of
edge-kept ratios. In summary, the contributions of SparRL are the following:

  * •

A novel reinforcement learning-based, general-purpose graph sparsification
framework with modular and easily modifiable components;

  * •

Task flexibility because of the plug-in reward function;

  * •

Task scalability as SparRL’s time complexity is independent from the size of a
graph.

The source code of SparRL can be found at https://github.com/rwickman/SparRL-
PyTorch.

##  2 Related Work

Originated from the cut problem (Benczúr & Karger, 1996), graph sparsification
has drawn extensive research interests (Batson et al., 2012; Lee & Sun, 2015;
2017; Spielman & Srivastava, 2011; Spielman & Teng, 2011). A straightforward
approach to this problem is to remove edges from a graph with probabilities
proportional to the edge weights. However, this approach may fail for a highly
structured graph, e.g., a graph with a small cut value where the sampling may
exclude the cut edges, thus losing the connectivity of the original graph. An
improved approach is to use the k-neighbors sparsifier (Sadhanala et al.,
2016), which performs local sparsification node-by-node via retaining edges of
nodes that have smaller degrees than a predefined threshold $\tau$ and
removing edges of nodes (proportionally to their weights) that have larger
degrees than $\tau$. Another method is to remove edges proportionally to their
effective resistance, which measures the importance of an edge in preserving
the minimum distance between two nodes. This approach will result in only
essential edges (on the order of $O(n\polylog n)$) being kept. Although there
has been advancement in fast approximation of effective resistance (Koutis et
al., 2012; 2016), the graph size remains a dominating factor affecting the
computing complexity.

A related line of research in graph theory, namely graph spanner (Peleg &
Ullman, 1989), aims to compute a subgraph that satisfies certain reachability
or distance constraints, e.g., $t$-spanner (Fekete & Kremer, 2001; Dragan et
al., 2011), where the geometric distance of every vertices pair in the
subgraph is at most $t$ times of the real distance in the original graph.
Therefore, $t$ is also named the stretch parameter, which needs to be
specified for a spanner algorithm. However, spanner has no guarantee on the
edge reduction ratio. In contrast, SparRL takes the edge reduction ratio as
input and make edge pruning decision via a learned model aiming to best
preserve the desired graph structural property. Moreover, techniques developed
for the spanner problem are subject to geometric distance preservation, which
make them hard to generalize to a variety of sparsification objectives. More
details on traditional graph sparsification techniques can be found in survey
papers (Batson et al., 2013; Teng, 2016).

In recent years, learning-based algorithms have gained popularity as they
allow for direct optimizing a task’s objective and have demonstrated superior
performance compared to traditional methods. However, few work exists on
learning to sparsify a graph. One related study is GSGAN (Wu & Chen, 2020)
which approaches graph sparsification using GAN (Goodfellow et al., 2014). The
goal is to preserve the community structure of a graph by learning to generate
a new graph. Despite the effectiveness, GSGAN could introduce edges that do
not present in the original graph, thus compromising the graph sparsification
objective on many real-world networks where establishing new edges/connections
is resource-intensive (e.g., road network). Another study, RNet-DQN (Darvariu
et al., 2020), uses RL to enhance the resilience of graph via adding edges
instead of pruning edges. GDPNet (Wang et al., 2019) also uses RL to prcess
graphs, but the goal is representation learning instead of graph
sparsification. The most relevant study to ours is NeuralSparse (Zheng et al.,
2020), whose focus is again representation learning. The subgraphs are
produced via supervised learning and need to go through a graph neural network
for downstream classification tasks. Due to these constraints, analytic
benchmarks such as community detection or shortest-path computing from
classical graph sparsification studies are omitted (Zheng et al., 2020). In
comparison, SparRL outputs a sparsified graph where existing graph analytic
benchmarks (and algorithms) can be directly applied. To the best of our
knowledge, SparRL is the first task-adaptive and effective graph
sparsification framework that is enabled by deep RL.

##  3 Preliminaries

Consider a $T$-step episodic task. At each timestep $t\in[1,T]$, the RL agent
uses its policy $\pi_{\theta}(a_{t}|s_{t})$ to choose action $a_{t}$ based on
state $s_{t}$ from the environment. Then, the environment responds with reward
$r_{t}$ and next state $s_{t+1}$ to the agent. This sequential decision-making
process is formulated as a Partially-Observable Markov Decision Process
(POMDP) defined by the tuple
$<\mathcal{S},\mathcal{A},P,R,\Omega,\mathcal{O},\gamma>$, where $\mathcal{S}$
is the state space, $\mathcal{A}$ is the action space, $P(s^{\prime}|s,a)$ is
the transition probability function, $R$ is the reward function, $\Omega$ is
the set of observations, $\mathcal{O}$ is the observation probability
function, and $\gamma\in[0,1]$ is the discount factor. The objective of the RL
agent is to find an effective policy $\pi_{\theta}$ that can maximize the sum
of discounted rewards, or the _return_ ,
$R_{t}=\sum_{i=t}^{T}\gamma^{i-t}r_{i}$.

Related to (PO)MDP is the concept of Q-function
$Q^{\pi}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$, which describes
the total expected reward by taking $a$ in $s$ and then following $\pi$
thereafter. The element that we want to obtain is the optimal Q-function
$Q^{*}$, from which we can trivially derive the optimal policy
$\pi^{*}(s)=argmax_{a}Q^{*}(s,a)$. One way to learn $Q^{*}$ is through
Q-learning (Watkins, 1989):

$Q_{t+1}(s_{t},a_{t})\leftarrow
Q_{t}(s_{t},a_{t})+\alpha_{t}\left[r_{t+1}+\gamma
max_{a^{\prime}}Q_{t}(s_{t+1},a^{\prime})-Q_{t}(s_{t},a_{t})\right],$

where $\alpha_{t}\in(0,1]$ is the step size. Accompanying the rise of deep
learning, many variations of Q-learning have been developed, among which Deep
Q-Network (DQN) (Mnih et al., 2015) has gained popularity due to its success
in playing Atari games. There exist several major improvements of DQN,
including Double DQN (Van Hasselt et al., 2016), Prioritized Replay (Schaul et
al., 2015), and Dueling DQN (Wang et al., 2016). In this work, we choose
Double DQN and Prioritized Replay as components of SparRL since they
significantly improve the vanilla DQN over small code changes.

##  4 SparRL Framework

In this section, we first provide an overview of SparRL, then detail its
components and design rationale.

###  4.1 Framework Overview

The overall goal is to find an edge sparsified graph
$G^{\prime}=(V^{\prime},E^{\prime})$ that approximates the original graph
$G=(V,E)$ measured over a performance metric. We treat this as an episodic
task, where edges are sequentially pruned from $G$. At each timestep, a
subgraph of edges are sampled from $E^{\prime}$ and SparRL’s action consists
of choosing an edge to prune from the sampled batch of edges. This continues
until $T$ edges are pruned from the graph which will produce $G^{\prime}$. We
describe this process in Algorithm 1.

for $i=0$ to $num\\_episodes$ do

$G^{\prime}=(V^{\prime},E^{\prime})\leftarrow G=(V,E)$ (clone $G$)

Sample $T\sim\mathcal{U}(1,T_{max})$

Sample $T_{p}\sim\mathcal{U}(1,|E|-T)$

Randomly prune $T_{p}$ edges from $G^{\prime}$

for $t=0$ to $T$ do

$H_{t}\leftarrow$ Randomly sample $|H|$ edges from $G^{\prime}_{t}$ (obtaining
a subgraph)

$d_{H_{t}}\leftarrow$ Degrees of nodes in $H_{t}$

$Q\\_values\leftarrow
f_{SparRL}(H_{t},d_{H_{t}},\frac{|E_{G^{\prime}_{t}}|}{|E_{G}|})$

$a_{t}\leftarrow$ Sample action using $\epsilon$-greedy exploration w.r.t
$Q\\_values$ (select an edge to prune)

Prune $a_{t}$ from $G^{\prime}$

$r_{t}\leftarrow R(G^{\prime}_{t})$ (compute performance metric over the
latest $G^{\prime}$)

Save transition $(s_{t},a_{t},r_{t},s_{t+1})$ to Prioritized Replay buffer

Train $f_{SparRL}$ on batch of trajectories

end for

end for

Algorithm 1 SparRL

We encourage efficient exploration of the state space by allowing the SparRL
agent to start in (almost) any part of the state space. This is implemented as
a preprocessing step, where before each episode, we randomly prune $T_{p}$
edges from $G^{\prime}$ to produce an initial sparsified graph and initial
state $s_{0}$.

###  4.2 MDP Formulation

We formalize the sparsification task as a POMDP that is solved using RL
(however, for ease of explanation, we will simplify it to an MDP). The state
$s_{t}$ includes the subgraph $H_{t}$, the degrees of all the nodes in the
subgraph $d_{H_{t}}$, and the percentage of edges left in the graph
$|E_{G^{\prime}_{t}}|/|E_{G}|$, where $|E_{G^{\prime}_{t}}|$ is the number of
edges in the sparsified graph and $|E_{G}|$ is the number of edges in the
original graph. The necessity to include the degrees of nodes in the state is
because during pruning, such information will change after an edge is removed
and affect a graph’s structure. For example, if a node has a degree of 1, then
pruning its edge would disconnect it from the graph, which information SparRL
will not know if the node’s degree is not included in the state. The reward
$r$ is dependent on the properties of the graph that is encouraged to be
preserved. At each timestep, we compute the reward after an edge is pruned to
avoid sparse rewards. The action $a_{t}$ is the edge to prune. The probability
transition function consists of a randomly sampled edge subgraph from
$G^{\prime}$, where each edge has an equal chance to be sampled. The episode
goes on for $T$ timesteps until it is terminated. For training, we keep $T$
small at $T=8$. The rationale for keeping $T$ small is to avoid overfitting
one randomly sampled sampled $G^{\prime}$ as a larger $T$ would forces SparRL
spends more time on training on a particular $G^{\prime}$. In addition, a
small $T$ would help the SparRL agent to start at various initial states
(since in each episode, $T_{p}$ edges will be randomly pruned from the
original graph) thus facilitating efficient exploration of the state space.
During test time, on the other hand, $T$ does not need to be kept small.

###  4.3 Policy Learning

We use Double DQN (Van Hasselt et al., 2016) to represent the SparRL
sparsification policy that is parameterized by a deep neural network. The
policy is trained over batch of trajectories sampled using Prioritized Replay
(Schaul et al., 2015).

The model architecture, shown in Figure 2, is composed of the node encoder,
edge encoder, and action-value function head. The node encoder first looks up
the initial node embedding for all the nodes in the graph, which are trained
jointly with the model. Then, the node encoder uses a GAT (Veličković et al.,
2017) that applies self-attention to the 1-hop neighborhood of each node to
produce a new node embedding. The node embeddings of the subgraph are then
separately combined with the nodes’ degrees (in-degree and out-degree if the
graph is directed) and the ratio of the edges left in the graph,
$|E_{G^{\prime}_{t}}|/|E_{G}|$. The edge encoder combines two end nodes that
represent the edge. Finally, the action-value head outputs the Q-values,
$Q(s_{t},a_{0})\dots Q(s_{t},a_{n})$, for each edge in the subgraph. The GAT
in the node-encoder uses a single fully-connected layer with 1 unit for
computing the attention coefficients. Both the main part of the node-encoder
and edge-encoder consists of two fully-connected layers with 128 units each
followed by LeakyReLU activation. The action-value head consists of a single
fully-connected layer with 1 unit. Thus, the model approximates the Q-value
function by running in parallel over each edge in the subgraph $H$:

$f_{SparRL}(H_{t},d_{H_{t}},\frac{|E_{G^{\prime}_{t}}|}{|E_{G}|})=Q(s_{t},a_{0}),\dots,Q(s_{t},a_{|H|}).$
(1)

Each edge of the subgraph is independently ran through the network, so the
subgraph length $|H|$ is not fixed by the network. Therefore, any number of
edges can be pruned at each timestep during the test time.

Figure 2: The SparRL model architecture that consists of the node encoder,
edge encoder, and action-value head. The input to the model includes the
subgraph, the degrees of the node, and ratio of edges still in the graph. The
node encoder combine uses a GAT on the 1-hop neighborhood of each node
embedding and then combines the output node embedding with its degrees and the
ratio of edges left in the graph. The edge encoder will combine each pair of
nodes that represent an edge. The action-value function edge will produce the
Q-value for each edge.

##  5 Experiments

We validate the effectiveness of SparRL using a variety of real-world graphs
over several performance metrics. The key observations include:

  * •

SparRL demonstrates superior performance to existing sparsification methods on
representative metrics over graphs of different scales;

  * •

SparRL can outperform the $t$-spanner method for preserving Single-Pair-
Shortest-Path (SPSP) distances at the same edge-kept ratio; and

  * •

SparRL allows for a simple time vs. performance trade-off by modifying $|H|$.

###  5.1 Experiment Setup

Datasets. We test SparRL using graphs from a variety of domains. The details
of these graphs are listed as follows while the number of nodes and edges of
each graph is summarized in Table 1.

  * •

Twitter (Leskovec & Mcauley, 2012): A social network dataset from the SNAP
project (https://snap.stanford.edu/data). The graph has 81,306 nodes and
1,768,149 edges.

  * •

Facebook (Leskovec & Mcauley, 2012): A social network dataset from the SNAP
project. The graph has 4,039 nodes and 88,234 edges.

  * •

YouTube (Mislove et al., 2007): A social network dataset where users establish
connections. Its community ground truth is defined by the groups created by
the users. In our experiment, we consider the top-100 communities for
evaluation, which consist of 4,890 nodes and 20,787 edges.

  * •

Amazon (Yang & Leskovec, 2015): A product co-purchasing network, where nodes
represent products and edges link the products that are often purchased
together. This network has a ground-truth community defined by the categories
of products. In our experiment, we consider the top-500 communities, which
consist of 4,259 nodes and 13,474 edges.

  * •

Email-Eu-Core (Email) (Leskovec et al., 2007; Yin et al., 2017; Leskovec &
Sosič, 2016): An interaction network of email data from a large European
research institution, where nodes represent people and edges represent sent
emails between people. The dataset consists of 1,005 nodes and 25,571 edges.

  * •

CiteSeer (Sen et al., 2008; Rossi & Ahmed, 2015): A citation network where
nodes represent scientific publications and edges represent references. The
network consists of 3,312 nodes and 4,536 edges.

Table 1: Graph datasets used in the experiments. Dataset | Twitter | Facebook | YouTube | Amazon | Email | CiteSeer
---|---|---|---|---|---|---
|  |  | (Top-100 Comm.) | (Top-500 Comm.) |  |
$|V|$ | 81,306 | 4,039 | 4,890 | 4,259 | 1,005 | 3,264
$|E|$ | 1,768,149 | 88,234 | 20,787 | 13,474 | 16,064 | 4,536

Baseline Methods. We compare SparRL with a wide range of sparsification
methods, which are implemented in Networkit (Staudt et al., 2015) with their
default settings:

  * •

Random Edge (RE): RE randomly prunes a given percentage of edges.

  * •

Local Degree (LD) (Hamann et al., 2016): For each node $v\in V$, the edges in
the top $\lfloor\text{deg}(v)^{\alpha}\rfloor$ are kept in $G^{\prime}$, where
$\alpha\in[0,1]$.

  * •

Edge Forest Fire (EFF) (Hamann et al., 2016): Based on the Forest Fire node
sampling algorithm (Leskovec & Faloutsos, 2006), a fire is started at a random
node and burns approximately $p/(1-p)$ neighbors, where $p$ is the probability
threshold of burning a neighbor. All burnt neighbors are added to a queue to
also have a fire started on them. Essentially, this method prunes edges based
on their visit count.

  * •

Algebraic Distance (AD) (Chen & Safro, 2011): Based on random walk distance,
the algebraic distance $\alpha(u,v)$ between two nodes is low if there is a
high probability that a random walk starting from $u$ will reach $v$ using a
small number of hops. AD uses $1-\alpha(u,v)$ as the edge score so that short-
range edges are considered important.

  * •

L-Spar (LS) (Satuluri et al., 2011b): LS applies the Jaccard similarity
function to nodes $u$ and $v$’s adjacency lists to determine the score of edge
$(u,v)$. It then ranks edges locally (w.r.t each node) and prune edges
according to their ranks.

  * •

Simmelian Backbone (SB) (Nick et al., 2013): SB measures each edge $(u,v)$’s
Simmelianness weight via the shared neighbors of $u$ and $v$. Then, for each
$u$, it ranks its neighbors w.r.t the edge weights in descending order. During
sparsification, SB will prune each node’s lower ranked edges according to a
given edge-prune ratio.

  * •

Quadrilateral Simmelian Backbone (QSB) (Nocaj et al., 2014): QSB measures each
edge $(u,v)$’s Simmeliannness weight via the shared quadrangles of $u$ and
$v$. Then, it follows the same pruning strategy as that of SB.

Metrics. We assess the sparsification methods by examining how well they
preserve the topological structure of the original graph w.r.t different
metrics, namely PageRank, community structures, and pairwise shortest path
distance (Hamann et al., 2016). For each metric, we evaluate the performance
of a sparsification method by running the method eight times independently and
report the average.

SparRL Setup. We update the target DQN network by applying soft updates after
training on a batch of trajectories at each timestep:
$\theta_{target}^{\prime}\leftarrow\varphi\theta_{target}+(1-\varphi)*\theta$,
where $\theta_{target}$ represents the parameters of the target DQN network
and $\theta$ represents the parameters of the current DQN network policy. We
find that $\varphi=0.001$ corresponds to stable results. We use $\alpha=0.6$
and $\beta=0.4$ for Prioritized Replay, $\gamma=0.95$ for the discounted
return, and initially set $\epsilon=0.99$ for $\epsilon$-greedy exploration
and decay it to $0.05$ over the first 10k policy update steps. We keep the
learning rate of the model fixed at $0.0002$ during the entire training
process.

When training the model for all experiments, we set $T_{max}=8$ and train
until negligible improvements are found over pruning $10\%$ of the edges.
Training the SparRL networks typically takes 1h–4h for the smaller graphs and
roughly 6h–12h for the larger graphs using an Intel Core i9-11900k CPU and RTX
3090 GPU. However, the run-time complexity when evaluating is simply
$O(|H|*T)$ as we are predicting over a subgraph of length $|H|$ for a total of
$T$ times. When evaluating on various test datasets, we act greedily w.r.t the
learned DQN policy and prune the edge that corresponds to the maximum Q-value
in the output.

Table 2: Comparison of PageRank preservation via the Spearman’s $\rho$ index,
where $r$ is the edge-kept ratio.

| Twitter | Facebook | Amazon (Top-500 Comm.)
---|---|---|---
Method |  $r$=0.2 |  $r$=0.4 |  $r$=0.6 |  $r$=0.8 |  $r$=0.2 |  $r$=0.4 |  $r$=0.6 |  $r$=0.8 |  $r$=0.2 |  $r$=0.4 |  $r$=0.6 |  $r$=0.8
SparRL | 0.846 | 0.944 | 0.984 | 0.995 | 0.942 | 0.982 | 0.996 | 0.998 | 0.779 | 0.907 | 0.944 | 0.988
LD | 0.512 | 0.775 | 0.876 | 0.929 | 0.899 | 0.979 | 0.995 | 0.995 | 0.755 | 0.884 | 0.929 | 0.978
RE | 0.763 | 0.864 | 0.924 | 0.967 | 0.802 | 0.905 | 0.955 | 0.982 | 0.549 | 0.749 | 0.871 | 0.948
EFF | 0.628 | 0.725 | 0.811 | 0.892 | 0.629 | 0.801 | 0.919 | 0.980 | 0.669 | 0.728 | 0.888 | 0.969
AD | 0.520 | 0.690 | 0.837 | 0.940 | 0.408 | 0.519 | 0.637 | 0.782 | 0.230 | 0.341 | 0.553 | 0.769
LS | 0.771 | 0.826 | 0.857 | 0.892 | 0.648 | 0.830 | 0.924 | 0.960 | 0.589 | 0.640 | 0.763 | 0.859
SB | 0.581 | 0.689 | 0.761 | 0.811 | 0.379 | 0.582 | 0.681 | 0.740 | 0.247 | 0.348 | 0.397 | 0.399
QSB | 0.642 | 0.746 | 0.794 | 0.821 | 0.512 | 0.585 | 0.671 | 0.737 | 0.280 | 0.354 | 0.399 | 0.399

Figure 3: PageRank preservation measures using Spearman’s $\rho$ index. SparRL
outperforms all other methods on all cases.

###  5.2 Effectiveness of SparRL

PageRank Preservation. PageRank serves a critical centrality metric for many
ranking-based graph applications. We examine the sparsification methods by
comparing the Spearman’s $\rho$ rank correlation coefficient (Myers & Well,
2003) between the PageRank score of the original graph ($G$) and of the
sparsified graph ($G^{\prime}$) at multiple edge-kept ratios. The reward is
defined as $r_{pr}=\rho_{G^{\prime}}-\rho_{G}$. The results in Figure 3 and
Table 2 show that SparRL outperforms all other methods on the Twitter,
Facebook, and Amazon (Top-500 Comm.) graphs.

Community Structure Preservation. We use the Adjusted Rand Index (ARI) (Hubert
& Arabie, 1985) to measure the effectiveness of SparRL on preserving the
community structure of a graph by comparing non-overlapping ground truth
communities to those found using the Louvian method (Blondel et al., 2008) at
multiple edge-kept ratios. We define the reward function as the different
between ARI scores for $G$ and $G^{\prime}$:

$r_{com}=ARI(G^{\prime})-ARI(G)+r_{label},$ (2)

where $ARI(G^{\prime})$ is the Louvian ARI score on $G^{\prime}$ and $ARI(G)$
is the original Louvian ARI score on $G$. The other reward, $r_{label}$, is
defined as:

$r_{label}=\begin{cases}1&\text{if }l_{a_{t}^{0}}==l_{a_{t}^{1}}\\\
-1&\text{otherwise},\end{cases}$ (3)

where $l_{a_{t}^{0}}$ is the label of the source node pruned at timestep t and
$l_{a_{t}^{1}}$ is the label of the destination node. We add this auxiliary
reward to encourage the agent to not prune an edge if its two end nodes belong
to the same community.

Table 3: Comparison of community structure preservation USING the ARI index,
where $r$ is the edge-kept ratio.

| YouTube (Top-100 Comm.) | Email | Amazon (Top-500 Comm.)
---|---|---|---
Method |  $r$=0.2 |  $r$=0.4 |  $r$=0.6 |  $r$=0.8 |  $r$=0.2 |  $r$=0.4 |  $r$=0.6 |  $r$=0.8 |  $r$=0.2 |  $r$=0.4 |  $r$=0.6 |  $r$=0.8
SparRL | 0.084 | 0.230 | 0.323 | 0.253 | 0.651 | 0.705 | 0.527 | 0.429 | 0.248 | 0.285 | 0.257 | 0.269
LD | 0.052 | 0.082 | 0.150 | 0.145 | 0.278 | 0.30 | 0.278 | 0.207 | 0.240 | 0.238 | 0.236 | 0.236
RE | 0.048 | 0.144 | 0.157 | 0.152 | 0.226 | 0.318 | 0.348 | 0.312 | 0.141 | 0.224 | 0.236 | 0.235
EFF | 0.029 | 0.092 | 0.117 | 0.134 | 0.407 | 0.385 | 0.347 | 0.334 | 0.109 | 0.180 | 0.223 | 0.232
AD | 0.035 | 0.068 | 0.111 | 0.143 | 0.263 | 0.272 | 0.284 | 0.333 | 0.105 | 0.169 | 0.210 | 0.234
LS | 0.016 | 0.071 | 0.150 | 0.147 | 0.446 | 0.390 | 0.375 | 0.319 | 0.209 | 0.250 | 0.249 | 0.245
SB | 0.039 | 0.127 | 0.161 | 0.166 | 0.274 | 0.326 | 0.365 | 0.358 | 0.225 | 0.225 | 0.235 | 0.249
QSB | 0.045 | 0.095 | 0.132 | 0.166 | 0.408 | 0.435 | 0.349 | 0.291 | 0.123 | 0.206 | 0.233 | 0.248

Figure 4: Community structure preservation measures using the ARI score.
SparRL outperforms all other methods on all cases.

The results in Figure 4 and Table 3 show that SparRL consistently outperforms
other methods on the YouTube (Top-100 Comm.), Email, and Amazon (Top-500
Comm.) graphs.

Table 4: Comparison of SPSP preservation over the average increase of the SPSP
distance, where $r$ is the edge-kept ratio.

| Citeseer | Email | Amazon (Top-500 Comm.)
---|---|---|---
Method |  $r$=0.2 |  $r$=0.4 |  $r$=0.6 |  $r$=0.8 |  $r$=0.2 |  $r$=0.4 |  $r$=0.6 |  $r$=0.8 |  $r$=0.2 |  $r$=0.4 |  $r$=0.6 |  $r$=0.8
SparRL | 2773 | 2473 | 338 | 15 | 0.326 | 0.133 | 0.07 | 0.021 | 281 | 106 | 0.518 | 0.24
LD | 2896 | 2898 | 2899 | 730 | 0.355 | 0.16 | 0.078 | 0.033 | 299 | 121 | 77 | 9
RE | 3233 | 2997 | 2047 | 1081 | 309 | 170 | 96 | 41 | 2930 | 1077 | 364 | 117
EFF | 3064 | 2645 | 1896 | 696 | 173 | 56 | 30 | 18 | 2042 | 1126 | 211 | 56
AD | 3252 | 3237 | 3165 | 2995 | 728 | 382 | 240 | 106 | 3803 | 3188 | 2460 | 1396
LS | 3230 | 3232 | 3204 | 1191 | 107 | 54 | 32 | 31 | 2537 | 813 | 519 | 400
SB | 3252 | 3192 | 3192 | 3191 | 891 | 531 | 321 | 250 | 2088 | 2084 | 1865 | 1400
QSB | 3250 | 3192 | 3193 | 3193 | 970 | 465 | 364 | 292 | 3783 | 3022 | 2356 | 1319

Figure 5: Shortest Path Distance Preservation measured by the average increase
of the SPSP distance between 8,196 randomly selected pairs. The fact that
SparRL’s line is below all the others shows its superior performance over all
other methods on all cases.

Shortest Path Distance Preservation. To test the ability of various
sparsification methods in preserving the pairwise shortest path distance, We
define the reward function for single-pair shortest path (SPSP) as follows:

$r_{spsp}=\frac{1}{|P|}\sum_{(u,v)\in P}dist(u,v)_{G^{\prime}}-dist(u,v)_{G},$
(4)

where $P$ is the set of SPSP pairs, and $dist(u,v)_{G^{\prime}}$ is the SPSP
distance between $u$ and $v$ in the sparsified graph $G^{\prime}$, and
$dist(u,v)_{G}$ is the SPSP distance between $u$ and $v$ in the original graph
$G$. In the case where $v$ becomes unreachable from $u$ in $G^{\prime}$ (i.e.,
$dist(u,v)_{G^{\prime}}=\infty$), we set this difference equal to $|V|$, as
this is greater than the maximum path length by one.

During training, $P$ is created at each timestep before an edge is pruned.
When the model chooses an edge $a_{t}$ to prune, we sample random nodes and
compute their shortest paths from the source node and destination node of
$a_{t}$. This design is to leverage the optimal substructure property of
shortest paths. That is, the only way a SPSP, for example from $u$ to $v$,
will be affected by $a_{t}$ is if $a_{t}$ is contained in that path. This is
because the SPSP between $u$ and $v$ must be composed of the SPSP from $u$ to
the source node in $a_{t}$ and the SPSP from the destination node in $a_{t}$
to $v$. Thus, when $a_{t}$ is pruned, a new SPSP must be generated between $u$
and $v$ without $a_{t}$.

During the test time, however, we run a maximum of 8,196 randomly sampled SPSP
queries over the graph and keep them fixed for the entire episode. The results
are given in Figure 5 and in Table 4 which show that SparRL consistently
outperforms other methods on the CiteSeer, Email, and Amazon (Top-500 Comm.)
graphs.

Comparing SparRL and $t$-Spanner. As $t$-spanner provides a way to sparsify a
graph while preserving the geometric distance between a pair of nodes at most
$t$ times of the original distance, we compare SparRL to a popular spanner
algorithm given in (Baswana & Sen, 2007). Due to the fact that the spanner
algorithm cannot guarantee the number of edges to prune, we run the NetworkX
(Hagberg et al., 2008) spanner implementation on various values of stretches
and record the edge-kept ratio. In addition, as an approximation algorithm,
the spanner algorithm produces a different sparsified graph at each run.
Therefore, we run the algorithm 16 times for each stretch value and compute
the average number of edges and average performance over preserving randomly
sampled SPSPs. We then run SparRL on the same average number of edges for each
stretch value and display the $r_{spsp}$ results in Table 5 on the CiteSeer
network. The edge-kept ratio of these experiments is kept high because the
$t$-spanner algorithm does not have much freedom on the number of edges to be
kept in a graph. Thus, we test on various $t$ values and prune the same amount
of edges using both approaches. These results show that SparRL can outperform
the $t$-spanner algorithm over various stretch values.

Table 5: Comparing SparRL with $t$-spanner for various stretch values $t$. ($x\%$: edge-kept ratio) Method |  $t$=3 (99.65%) |  $t$=4 (99.63%) |  $t$=8 (97.82%) |  $t$=16 (93.74%) |  $t=32$ (90.78%)
---|---|---|---|---|---
t-spanner | 0.0082 | 0.0054 | 0.0405 | 0.1187 | 0.1911
SparRL | 0.0031 | 0.0043 | 0.0350 | 0.0974 | 0.1820

###  5.3 Analysis of SparRL Components

Impact of Subgraph Size. At each timestep, SparRL inputs a subgraph which
contains edges randomly sampled from $E_{G^{\prime}_{t}}$. Due to the
flexibility of our model architecture, we can have variable length subgraphs
as input at test time. Thus, in Figure 6 we show results on applying the same
trained model on varying subgraph lengths and measure their performance over
Spearman’s $\rho$ on the Email graph. While increasing the subgraph length up
to a certain point can improve model performance (e.g., for 0.8 edge-ratio
$|H|=64$ performance the best, even though SparRL is trained on $|H|=32$),
SparRL does increase the time to prune the edge. Thus, this is a time vs
performance trade-off that can be adjusted according to user’s need.

Figure 6: Subgraph length $|H|$ affect on model perfomance measured over
Spearman’s $\rho$ on the Email graph.

##  6 Conclusion

In this work, we propose a general graph sparsification framework based on
deep reinforcement learning, namely SparRL. SparRL can overcome the
limitations of existing sparsification methods with relatively low computation
complexity and the flexibility to adapt to a wide range of sparsification
objectives. We evaluate SparRL using various experiments on many real-world
graphs and representative graph metrics. The results show that SparRL is
effective and generalizable in producing high-quality sparsified graphs.
Further analysis on the components of SparRL have validated our design
rationale.

There are many future directions. First of all, we would like to extend SparRL
to other types of graphs such as dynamic graphs and hierarchical graphs.
Second, we are interested in investigating how SparRL could help improve the
performance of graph learning tasks, e.g., link prediction, label
classification, and applications that use graph neural networks (Lin et al.,
2019a). Third, we want to study the effectiveness of SparRL in specific
subject domains. We are especially interested in applying SparRL to the
transportation domain where motion planning algorithms such as RRT* (Karaman &
Frazzoli, 2011) can be simplified for autonomous driving (Li et al., 2019;
Chao et al., 2020), robust analysis of networks are critical (Poudel & Li,
2021; Li et al., 2017a), and connected vehicles depend on communication
networks to cooperate with neighboring vehicles to make intelligent decisions
(Lin et al., 2021).

## References

  * Ahn et al. (2012) Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Graph sketches: sparsification, spanners, and subgraphs.  In _Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS_ , pp. 5–14. ACM, 2012\.
  * Arora & Upadhyay (2019) Raman Arora and Jalaj Upadhyay.  On differentially private graph sparsification and applications.  In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems, NeurIPS_ , pp. 13378–13389, 2019.
  * Barabási et al. (2011) Albert-László Barabási, Natali Gulbahce, and Joseph Loscalzo.  Network medicine: a network-based approach to human disease.  _Nature reviews genetics_ , 12(1):56–68, 2011\.
  * Bastian et al. (2009) Mathieu Bastian, Sebastien Heymann, and Mathieu Jacomy.  Gephi: An open source software for exploring and manipulating networks.  In _ICWSM_. The AAAI Press, 2009.
  * Baswana & Sen (2007) Surender Baswana and Sandeep Sen.  A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs.  _Random Struct. Algorithms_ , 30(4):532–563, 2007\.
  * Batson et al. (2012) Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava.  Twice-ramanujan sparsifiers.  _SIAM J. Comput._ , 41(6):1704–1721, 2012.
  * Batson et al. (2013) Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava, and Shang-Hua Teng.  Spectral sparsification of graphs: theory and algorithms.  _Commun. ACM_ , 56(8):87–94, 2013.
  * Benczúr & Karger (1996) András A. Benczúr and David R. Karger.  Approximating _s-t_ minimum cuts in _Õ_(_n_ ${}^{\mbox{2}}$) time.  In _Proceedings of the 28th Annual ACM Symposium on the Theory of Computing_ , pp. 47–55. ACM, 1996.
  * Blondel et al. (2008) Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre.  Fast unfolding of communities in large networks.  _Journal of statistical mechanics: theory and experiment_ , 2008(10):P10008, 2008.
  * Borgatti et al. (2009) Stephen P Borgatti, Ajay Mehra, Daniel J Brass, and Giuseppe Labianca.  Network analysis in the social sciences.  _science_ , 323(5916):892–895, 2009.
  * Calandriello et al. (2018) Daniele Calandriello, Ioannis Koutis, Alessandro Lazaric, and Michal Valko.  Improved large-scale graph learning through ridge spectral sparsification.  In _Proceedings of the 35th International Conference on Machine Learning, ICML_ , volume 80, pp. 687–696, 2018.
  * Chang (2000) Cheng-Shang Chang.  _Performance guarantees in communication networks_.  Springer Science & Business Media, 2000.
  * Chao et al. (2020) Qianwen Chao, Huikun Bi, Weizi Li, Tianlu Mao, Zhaoqi Wang, Ming C. Lin, and Zhigang Deng.  A survey on visual traffic simulation: Models, evaluations, and applications in autonomous driving.  _Computer Graphics Forum_ , 39(1):287–308, 2020\.  doi: https://doi.org/10.1111/cgf.13803.
  * Chen & Safro (2011) Jie Chen and Ilya Safro.  Algebraic distance on graphs.  _SIAM Journal on Scientific Computing_ , 33(6):3468–3490, 2011.
  * Darvariu et al. (2020) Victor-Alexandru Darvariu, Stephen Hailes, and Mirco Musolesi.  Improving the robustness of graphs through reinforcement learning and graph neural networks, 2020.
  * Dragan et al. (2011) Feodor F. Dragan, Fedor V. Fomin, and Petr A. Golovach.  Spanners in sparse graphs.  _J. Comput. Syst. Sci._ , 77(6):1108–1119, 2011\.
  * Fekete & Kremer (2001) Sándor P. Fekete and Jana Kremer.  Tree spanners in planar graphs.  _Discret. Appl. Math._ , 108(1-2):85–103, 2001\.
  * Fung et al. (2019) Wai Shing Fung, Ramesh Hariharan, Nicholas J. A. Harvey, and Debmalya Panigrahi.  A general framework for graph sparsification.  _SIAM J. Comput._ , 48(4):1196–1223, 2019.
  * Goodfellow et al. (2014) Ian J Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial networks.  _arXiv preprint arXiv:1406.2661_ , 2014.
  * Hagberg et al. (2008) Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart.  Exploring network structure, dynamics, and function using networkx.  In Gaël Varoquaux, Travis Vaught, and Jarrod Millman (eds.), _Proceedings of the 7th Python in Science Conference_ , pp. 11 – 15, Pasadena, CA USA, 2008.
  * Hamann et al. (2016) Michael Hamann, Gerd Lindner, Henning Meyerhenke, Christian L Staudt, and Dorothea Wagner.  Structure-preserving sparsification methods for social networks.  _Social Network Analysis and Mining_ , 6(1):22, 2016.
  * Hubert & Arabie (1985) Lawrence Hubert and Phipps Arabie.  Comparing partitions.  _Journal of classification_ , 2(1):193–218, 1985\.
  * Iyer et al. (2018) Anand Padmanabha Iyer, Aurojit Panda, Shivaram Venkataraman, Mosharaf Chowdhury, Aditya Akella, Scott Shenker, and Ion Stoica.  Bridging the gap: Towards approximate graph analytics.  In _Proceedings of the 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)_, 2018.
  * Karaman & Frazzoli (2011) Sertac Karaman and Emilio Frazzoli.  Sampling-based algorithms for optimal motion planning.  _The international journal of robotics research_ , 30(7):846–894, 2011.
  * Koutis et al. (2012) Ioannis Koutis, Alex Levin, and Richard Peng.  Improved spectral sparsification and numerical algorithms for SDD matrices.  In Christoph Dürr and Thomas Wilke (eds.), _29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France_ , volume 14 of _LIPIcs_ , pp. 266–277. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012.
  * Koutis et al. (2016) Ioannis Koutis, Alex Levin, and Richard Peng.  Faster spectral sparsification and numerical algorithms for SDD matrices.  _ACM Trans. Algorithms_ , 12(2):17:1–17:16, 2016.
  * Lee & Sun (2015) Yin Tat Lee and He Sun.  Constructing linear-sized spectral sparsification in almost-linear time.  In _IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS_ , pp. 250–269. IEEE Computer Society, 2015.
  * Lee & Sun (2017) Yin Tat Lee and He Sun.  An sdp-based algorithm for linear-sized spectral sparsification.  In _Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC_ , pp. 678–687. ACM, 2017.
  * Leskovec & Faloutsos (2006) Jure Leskovec and Christos Faloutsos.  Sampling from large graphs.  In _Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pp. 631–636, 2006.
  * Leskovec & Mcauley (2012) Jure Leskovec and Julian Mcauley.  Learning to discover social circles in ego networks.  In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger (eds.), _Advances in Neural Information Processing Systems_ , volume 25. Curran Associates, Inc., 2012.
  * Leskovec & Sosič (2016) Jure Leskovec and Rok Sosič.  Snap: A general-purpose network analysis and graph-mining library.  _ACM Transactions on Intelligent Systems and Technology (TIST)_ , 8(1):1, 2016.
  * Leskovec et al. (2007) Jure Leskovec, Jon Kleinberg, and Christos Faloutsos.  Graph evolution: Densification and shrinking diameters.  _ACM Trans. Knowl. Discov. Data_ , 1(1):2–es, March 2007.
  * Li et al. (2017a) Weizi Li, Dong Nie, David Wilkie, and Ming C. Lin.  Citywide estimation of traffic dynamics via sparse GPS traces.  _IEEE Intelligent Transportation Systems Magazine_ , 9(3):100–113, 2017a.  ISSN 1939-1390.  doi: https://doi.org/10.1109/mits.2017.2709804.
  * Li et al. (2017b) Weizi Li, David Wolinski, and Ming C. Lin.  City-scale traffic animation using statistical learning and metamodel-based optimization.  _ACM Trans. Graph._ , 36(6):200:1–200:12, November 2017b.  doi: https://doi.org/10.1145/3130800.3130847.
  * Li et al. (2019) Weizi Li, David Wolinski, and Ming C. Lin.  ADAPS: Autonomous driving via principled simulations.  In _IEEE International Conference on Robotics and Automation (ICRA)_ , pp. 7625–7631, 2019.  doi: https://doi.org/10.1109/icra.2019.8794239.
  * Lin et al. (2019a) Lei Lin, Weizi Li, and Srinivas Peeta.  Predicting station-level bike-sharing demands using graph convolutional neural network.  In _Transportation Research Board 98th Annual Meeting (TRB)_ , 2019a.
  * Lin et al. (2019b) Lei Lin, Weizi Li, and Srinivas Peeta.  Efficient data collection and accurate travel time estimation in a connected vehicle environment via real-time compressive sensing.  _Journal of Big Data Analytics in Transportation_ , 1(2):95–107, 2019b.  doi: https://doi.org/10.1007/s42421-019-00009-5.
  * Lin et al. (2021) Lei Lin, Weizi Li, Huikun Bi, and Lingqiao Qin.  Vehicle trajectory prediction using LSTMs with spatial-temporal attention mechanisms.  _IEEE Intelligent Transportation Systems Magazine_ , 2021.
  * Mathioudakis et al. (2011) Michael Mathioudakis, Francesco Bonchi, Carlos Castillo, Aristides Gionis, and Antti Ukkonen.  Sparsification of influence networks.  In _Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pp. 529–537, 2011.
  * Mislove et al. (2007) Alan Mislove, Massimiliano Marcon, Krishna P. Gummadi, Peter Druschel, and Bobby Bhattacharjee.  Measurement and Analysis of Online Social Networks.  In _Proceedings of the 5th ACM/Usenix Internet Measurement Conference (IMC’07)_ , San Diego, CA, October 2007.
  * Mnih et al. (2015) Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al.  Human-level control through deep reinforcement learning.  _nature_ , 518(7540):529–533, 2015.
  * Myers & Well (2003) Jerome L. Myers and Arnold D. Well.  _Research Design and Statistical Analysis (2nd ed.)_.  Lawrence Erlbaum, 2003.
  * Nick et al. (2013) Bobo Nick, Conrad Lee, Pádraig Cunningham, and Ulrik Brandes.  Simmelian backbones: Amplifying hidden homophily in facebook networks.  In _Proceedings of the 2013 IEEE/ACM international conference on advances in social networks analysis and mining_ , pp. 525–532, 2013.
  * Nocaj et al. (2014) Arlind Nocaj, Mark Ortmann, and Ulrik Brandes.  Untangling hairballs.  In _International Symposium on Graph Drawing_ , pp. 101–112. Springer, 2014.
  * Peleg & Ullman (1989) David Peleg and Jeffrey D. Ullman.  An optimal synchronizer for the hypercube.  _SIAM J. Comput._ , 18(4):740–747, 1989.
  * Poudel & Li (2021) Bibek Poudel and Weizi Li.  Black-box adversarial attacks on network-wide multi-step traffic state prediction models.  In _IEEE International Conference on Intelligent Transportation Systems (ITSC)_ , 2021.
  * Rossi & Ahmed (2015) Ryan A. Rossi and Nesreen K. Ahmed.  The network data repository with interactive graph analytics and visualization.  In _AAAI_ , 2015.
  * Sadhanala et al. (2016) Veeranjaneyulu Sadhanala, Yu-Xiang Wang, and Ryan J. Tibshirani.  Graph sparsification approaches for laplacian smoothing.  In _Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, AISTATS_ , volume 51 of _JMLR Workshop and Conference Proceedings_ , pp. 1250–1259, 2016.
  * Satuluri et al. (2011a) Venu Satuluri, Srinivasan Parthasarathy, and Yiye Ruan.  Local graph sparsification for scalable clustering.  In _Proceedings of the ACM SIGMOD International Conference on Management of Data_ , pp. 721–732. ACM, 2011a.
  * Satuluri et al. (2011b) Venu Satuluri, Srinivasan Parthasarathy, and Yiye Ruan.  Local graph sparsification for scalable clustering.  SIGMOD ’11, pp. 721–732, New York, NY, USA, 2011b. Association for Computing Machinery.
  * Schaul et al. (2015) Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver.  Prioritized experience replay.  _arXiv preprint arXiv:1511.05952_ , 2015.
  * Sen et al. (2008) Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad.  Collective classification in network data.  _AI magazine_ , 29(3):93–93, 2008.
  * Shen et al. (2017) Xiao Shen, Fu-Lai Chung, and Sitong Mao.  Leveraging cross-network information for graph sparsification in influence maximization.  In _Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , pp. 801–804, 2017.
  * Spielman & Srivastava (2011) Daniel A. Spielman and Nikhil Srivastava.  Graph sparsification by effective resistances.  _SIAM J. Comput._ , 40(6):1913–1926, 2011.
  * Spielman & Teng (2011) Daniel A. Spielman and Shang-Hua Teng.  Spectral sparsification of graphs.  _SIAM J. Comput._ , 40(4):981–1025, 2011.
  * Staudt et al. (2015) Christian L. Staudt, Aleksejs Sazonovs, and Henning Meyerhenke.  Networkit: A tool suite for large-scale complex network analysis, 2015\.
  * Teng (2016) Shang-Hua Teng.  Scalable algorithms for data and network analysis.  _Found. Trends Theor. Comput. Sci._ , 12(1-2):1–274, 2016.
  * Upadhyay (2013) Jalaj Upadhyay.  Random projections, graph sparsification, and differential privacy.  In _Advances in Cryptology - ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security_ , volume 8269, pp. 276–295. Springer, 2013.
  * Van Hasselt et al. (2016) Hado Van Hasselt, Arthur Guez, and David Silver.  Deep reinforcement learning with double q-learning.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 30, 2016.
  * Veličković et al. (2017) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ , 2017.
  * Wang et al. (2019) Lu Wang, Wenchao Yu, Wei Wang, Wei Cheng, Wei Zhang, Hongyuan Zha, Xiaofeng He, and Haifeng Chen.  Learning robust representations with graph denoising policy network.  In _2019 IEEE International Conference on Data Mining (ICDM)_ , pp. 1378–1383. IEEE, 2019.
  * Wang et al. (2016) Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Hasselt, Marc Lanctot, and Nando Freitas.  Dueling network architectures for deep reinforcement learning.  In _International conference on machine learning_ , pp. 1995–2003. PMLR, 2016.
  * Watkins (1989) Christopher John Cornish Hellaby Watkins.  Learning from delayed rewards.  1989\.
  * Wu & Chen (2020) Hang-Yang Wu and Yi-Ling Chen.  Graph sparsification with generative adversarial network, 2020.
  * Yang & Leskovec (2015) Jaewon Yang and Jure Leskovec.  Defining and evaluating network communities based on ground-truth.  _Knowl. Inf. Syst._ , 42(1):181–213, January 2015.  ISSN 0219-1377.
  * Yin et al. (2017) Hao Yin, Austin R. Benson, Jure Leskovec, and David F. Gleich.  Local higher-order graph clustering.  In _Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pp. 555–564. Association for Computing Machinery, 2017.
  * Zachary (1977) Wayne W Zachary.  An information flow model for conflict and fission in small groups.  _Journal of anthropological research_ , 33(4):452–473, 1977.
  * Zhao (2015) Peixiang Zhao.  Gsparsify: Graph motif based sparsification for graph clustering.  In _Proceedings of the 24th ACM International on Conference on Information and Knowledge Management_ , pp. 373–382, 2015.
  * Zhao et al. (2014) Xueqian Zhao, Zhuo Feng, and Cheng Zhuo.  An efficient spectral graph sparsification approach to scalable reduction of large flip-chip power grids.  In _The IEEE/ACM International Conference on Computer-Aided Design, ICCAD_ , pp. 218–223. IEEE, 2014.
  * Zhao et al. (2015) Xueqian Zhao, Lengfei Han, and Zhuo Feng.  A performance-guided graph sparsification approach to scalable and robust spice-accurate integrated circuit simulations.  _IEEE Trans. Comput. Aided Des. Integr. Circuits Syst._ , 34(10):1639–1651, 2015.
  * Zhao & Feng (2017) Zhiqiang Zhao and Zhuo Feng.  A spectral graph sparsification approach to scalable vectorless power grid integrity verification.  In _Proceedings of the 54th Annual Design Automation Conference, DAC_ , pp. 68:1–68:6. ACM, 2017.
  * Zheng et al. (2020) Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang.  Robust graph representation learning via neural sparsification.  In _International Conference on Machine Learning_ , pp. 11458–11468. PMLR, 2020.