# XLM-V: Overcoming the Vocabulary Bottleneck in
Multilingual Masked Language Models

Davis Liang Hila Gonen Yuning Mao Rui Hou

Naman Goyal Marjan Ghazvininejad Luke Zettlemoyer Madian Khabsa

Meta AI

###### Abstract

Large multilingual language models typically rely on a single vocabulary
shared across 100+ languages. As these models have increased in parameter
count and depth, vocabulary size has remained largely unchanged. This
vocabulary bottleneck limits the representational capabilities of multilingual
models like XLM-R. In this paper, we introduce a new approach for scaling to
very large multilingual vocabularies by de-emphasizing token sharing between
languages with little lexical overlap and assigning vocabulary capacity to
achieve sufficient coverage for each individual language. Tokenizations using
our vocabulary are typically more semantically meaningful and shorter compared
to XLM-R. Leveraging this improved vocabulary, we train XLM-V, a multilingual
language model with a one million token vocabulary. XLM-V outperforms XLM-R on
every task we tested on ranging from natural language inference (XNLI),
question answering (MLQA, XQuAD, TyDiQA), to named entity recognition
(WikiAnn). XLM-V is particularly effective on low-resource language tasks and
outperforms XLM-R by 11.2% and 5.8% absolute on MasakhaNER and Americas NLI,
respectively.

##  1 Introduction

While multilingual language models have increased in parameter count and depth
over time, vocabulary size has largely remained unchanged: mBART (680M
parameters; Liu et al. 2020), XGLM (7.5B parameters, Lin et al. 2021), XLM-R
XXL (10.7B parameters; Goyal et al. 2021), mT5 XXL (13B parameters; Xue et al.
2020); and BLOOM (176B parameters; Scao et al. 2022) all share the same 250K
token vocabulary size as XLM-R base Conneau et al. (2019), a 250M parameter
model.

For models like mT5 and XLM-R, this 250K vocabulary is shared across 100+
languages. Discounting shared tokens, this results in an average of 2,500
unique tokens per language, calling into question the vocabulary’s ability to
represent the diverse selection of languages that it was intended to model.
For example, there are 8,105 characters in the Table of General Standard
Chinese characters and over 100,000 unique characters in total; the number of
commonly used Chinese words (consisting of multiple characters) is even larger
Wikipedia (2023). In fact, prior work has already shown that this vocabulary
bottleneck hinders the performance of multilingual models on question
answering and sequence labeling where in-depth token-level and sequence-level
understanding is essential Wang et al. (2019).

In this paper, we construct a large multilingual vocabulary by attending to
two core principles: (1) vocabularies can be improved by de-emphasizing token
sharing between languages with little lexical overlap and (2) proper
vocabulary capacity allocation for individual languages is crucial for
ensuring that diverse languages are well-represented. Then, we show that our
new vocabulary exhibits favorable characteristics including the ability to
frequently output semantically meaningful tokenizations while reducing over-
tokenization for low-resource languages. Finally, we present XLM-V, the first
multilingual language model with a one million token vocabulary trained on
2.5TB of data from Common Crawl Conneau et al. (2019).

Our main contributions are as follows:

  * •

In Section 3, we present our method for constructing large multilingual
vocabularies. Specifically, we improve upon the language clustering algorithm
from Chung et al. (2020) by constructing better vector representations for
individual languages and leverage Zheng et al. (2021) to improve the
vocabulary capacity assignments for each cluster.

  * •

In Section 5, we demonstrate that XLM-V outperforms comparable baselines that
have the same vocabulary size on XNLI. Additionally, XLM-V outperforms XLM-R
on every multilingual language understanding task we tested on (including
XNLI, WikiAnn, MLQA, XQuAD, and TyDiQA) by an average of 3.5 points absolute.
XLM-V performs especially well on low-resource evaluation datasets like
AmericasNLI and MasakhaNER, outperforming XLM-R by 5.8% absolute accuracy and
11.2% absolute F1, respectively.

  * •

Finally, in Section 6, we provide examples and quantitative analysis to
compare our new vocabulary to various baselines. Most notably, we provide
evidence showing that expanding the vocabulary beyond 1M tokens can degrade
performance on downstream tasks.

##  2 Background

###  2.1 Sentencepiece

The Unigram Language Model (ULM) from Kudo and Richardson (2018) is a popular
subword segmentation algorithm used to construct vocabularies. ULM begins with
a large initial vocabulary that is iteratively pruned to maximize the
likelihood of the training corpus (under a unigram language model of the
tokens) until the number of tokens falls below some pre-determined vocabulary
size threshold, $|V|$. During tokenization, ULM decodes the most probable
segmentation of a sequence through the Viterbi algorithm Viterbi (1967). This
method is used by both XLM-R and our work.

###  2.2 Clustering

Chung et al. (2020) proposed an approach to multilingual vocabulary
construction that balances the trade-off between optimizing for cross-lingual
subword sharing and the need for robust representation of individual
languages.

Their procedure for building a multilingual vocabulary contains several steps.
First, the authors train individual sentencepiece models for each language:
for each language $l$ in the set of languages $L$, a vocabulary $V^{l}$ is
generated. Then, they create the shared lexicon $V^{L}$ by taking the union of
each language-specific vocabulary, $V^{L}=\cup_{l\in L}V^{l}$. Next, for each
language $l$, they construct a binary vector $v^{l}$ of dimension $|V^{L}|$
which represents the lexicon of $l$. Each component of $v^{l}$ corresponds to
a subword in $V^{L}$. In other words, the binary vector $v^{l}$ contains a 1
corresponding to each subword present in the vocabulary of $l$. An
illustration of this step is shown in Figure 1. Then, the authors cluster the
binary vectors to group lexically similar languages together. Finally, they
construct a vocabulary for each cluster and combine the per-cluster
vocabularies together to form a unified multilingual vocabulary.

###  2.3 Vocabulary allocation

Zheng et al. (2021) proposed the average log probability (ALP) to evaluate the
ability of a vocabulary to represent a particular language. Specifically,
given a monolingual corpus composed of sentences
$\mathcal{D}_{i}=\\{s_{1},...,s_{|\mathcal{D}_{i}|}\\}$ from the $i$-th
language and tokenized with vocabulary $V$, the average log probability is
defined as;

$ALP(\mathcal{D}_{i},V)=\frac{1}{|\mathcal{D}_{i}|}\sum_{j=1}^{|\mathcal{D}_{i}|}\sum_{k=1}^{|s_{j}|}\log
p_{uni}(s^{k}_{j})$ (1)

where $s_{j}^{k}$ is the $k$-th subword of the sentence $s_{j}$ and
$p_{uni}(\cdot)$ is the unigram distribution counted on the monolingual corpus
$\mathcal{D}_{i}$. The authors first show that ALP is highly correlated with
downstream task performance and then propose a greedy algorithm to determine
the desired vocabulary capacity for individual languages in the multilingual
vocabulary.

##  3 Methodology

Cluster | $|V^{c}|$ | Languages
---|---|---
$c_{1}$ | 174,504 | fa, pa, sa, ka, ur, lo, my, ne, am, te, my, th, ta, ko, bn, ml, he, sd, as, hi, km, gu, kn, si, yi, mr, ps, or, xh, ar, ug
$c_{2}$ | 102,722 | ja, zh-TW, zh-CN
$c_{3}$ | 186,881 | fi, sk, om, sw, ln, az, lg, uz, so, hy, ss, hu, la, ff, et, ta, wo, lv, ku, te, sc, el, pl, lt, tr
$c_{4}$ | 110,148 | pt, eu, gl, gn, it, ca, qu, es
$c_{5}$ | 24,752 | af, li, nl, fy
$c_{6}$ | 19,801 | hr, sl, bs
$c_{7}$ | 101,485 | bg, ky, uk, be, kk, sr, mk, ru, mn
$c_{8}$ | 279,702 | su, jv, tl, sv, tn, no, id, ig, bn, ns, mg, cs, ms, ro, ur, rm, ha, ga, ht, is, eo, gd, br, hi, en, cy, fr, vi, da, yo, de, sq
Table 1: Lexical clustering results for XLM-V with number of clusters $k=8$
and a total vocabulary capacity of 1M.

###  3.1 Building the vocabulary

In this subsection, we describe our method for constructing multilingual
vocabularies. At a high level, we (1) train individual monolingual
sentencepiece models (SPM) for each language in our dataset using the Unigram
Language Model (ULM) algorithm Kudo and Richardson (2018), (2) use the per-
language vocabularies to construct lexical representation vectors for each
language, (3) cluster the lexical representation vectors using K-Means, assign
vocabulary capacities for each cluster using the ALP, and then construct per-
cluster vocabularies using the ULM algorithm, and (4) create the final
multilingual vocabulary by taking the union of the vocabularies for each
cluster.

#### Training monolingual SPMs

To acquire the data for building the vocabulary, we perform sampling with
temperature $t=2$ to sample 1 billion lines of text from CC100 (up-sampling
lower-resource and down-sampling data from high resource languages). Then, for
each language in CC100, we train a language-specific sentencepiece model with
a vocabulary size of 30,000 (per language) using this data.

Figure 1: Similar to Chung et al. (2020), we also leverage the per-language
sentencepiece vocabularies as a “lexical fingerprint” for clustering. However,
instead of using binary vectors, we use the unigram log probability instead.

#### Constructing lexical fingerprints

We then construct a vector representation of each language using the
vocabularies of each language as shown in Figure 1. Unlike Chung et al.
(2020), where a language is represented by a binary vector containing a 1
corresponding to each subword present in the vocabulary of that language, we
instead use the negative log probability that each token appears in the
respective language’s monolingual corpus. We hypothesize that weighting each
token by its likelihood of occurring better represents the lexical fingerprint
of a language.

#### Clustering and capacity allocation

Next, we construct language clusters and train sentencepiece models for each
cluster in order to discourage the vocabulary sharing between lexically
dissimilar languages. Before training per-cluster sentencepiece models, we
need to first decide on the vocabulary size, or vocabulary capacity, to
allocate to each cluster. Unfortunately, we found that the method for
assigning vocabulary capacities used by Chung et al. (2020) (i.e.
proportionally to the set union of the per-language vocabularies in each
cluster) resulted in several clusters with deficient vocabulary capacity. For
example, cluster $c_{2}$ in Table 1 (a smaller cluster that contains lexically
diverse languages: Chinese Simplified, Chinese Traditional, and Japanese), was
assigned a capacity of just 28,593 tokens.

We instead use the per-language vocabulary capacity allocations Zheng et al.
(2021) optimized for the CC100 dataset. By doing so, the vocabulary capacity
assigned to $c_{2}$ was increased to 102,722. For each tail-end (low-resource)
language that was not covered in Zheng et al. (2021), we allocate a 2,000
token vocabulary budget. Rather than use the vocabulary allocations directly,
we take their relative values and rescale them to sum up to the vocabulary
capacity of our choosing (e.g. 1M, 2M, etc.). Finally, we perform K-Means
clustering with $k=8$, based on experiments from Chung et al. (2020) showing
that $k=8$ results in the best performance on downstream tasks. We expect the
ideal number of clusters to vary not based on the number of languages but
rather on the identity of those languages and their respective similarities to
one another.

#### The final vocabulary

For each resulting cluster, we train per-cluster sentencepiece models and
combine the vocabularies of each cluster into a single multilingual
vocabulary. The final vocabulary consists of 901,629 tokens (remaining 98,371
tokens overlapped between the 8 clusters), meaning that on average over 90% of
the tokens learned in each cluster are unique.

###  3.2 Training the model

To pretrain our model, we follow the same training procedure from XLM-R
Conneau et al. (2019). Specifically, we use the CC100 dataset with a sampling
temperature of 0.3 to increase the amount of low- and medium-resource language
examples seen during training. We use the Adam optimizer Kingma and Ba (2014)
with the default $(\beta_{1},\beta_{2})$ and $\epsilon$ parameters of (0.9,
0.98) and 1e-6, respectively. We use a learning rate of 6e-4, a warmup of
15,000 steps, a batch size of 8,192 distributed across 256 A100 GPUs, and
train for a total of 1.5M iterations. Each batch consists of examples
concatenated up to the maximum sequence length of 512. We pretrain the model
using the Masked Language Model (MLM) task Devlin et al. (2018) with the
standard masking rate of 15%.

Increasing the vocabulary size can significantly increase pretraining time due
to the computationally intensive softmax layer. To address this, prior works
have leveraged approximation tricks such as adaptive softmax Baevski and Auli
(2018) and adaptive inputs Joulin et al. (2017). However, we found that these
tricks require non-trivial amounts of tuning and resulted in slower
convergence and increased training instability. In this paper, we perform
pretraining without any approximation tricks noting that this method may not
be feasible when the vocabulary is scaled beyond 2M.111For a model with a
vocabulary size of 1M, each iteration of MLM pretraining took 2.5 times longer
than the same model with a 250K token vocabulary.

##  4 Experiment setup

Model |  XNLI |  NER |  MLQA |  TyDiQA |  XQuAD |  ANLI |  MNER |  Average
---|---|---|---|---|---|---|---|---
| Acc. | Acc. | EM / F1 | EM / F1 | EM / F1 | F1 | F1 |
XLM | 69.1 | - | 32.6 / 48.5 | 29.1 / 43.6 | 44.3 / 59.8 | - | - | -
XLM-R | 76.2 | - | 46.3 / 63.7 | \- / - | \- / - | 38.5 | - | -
XLM-R reimpl. | 74.9 | 61.3 | 46.7 / 64.4 | 38.3 / 56.0 | 56.0 / 71.3 | 39.6 | 20.9 | 55.5
XLM-V | 76.0 | 64.7 | 47.7 / 66.0 | 39.7 / 56.9 | 56.3 / 71.9 | 45.4 | 32.1 | 59.0
Table 2: Overall results across multiple multilingual datasets comparing our
model against the XLM and XLM-R baselines. All results are based on
crosslingual transfer after fine-tuning on English data. We computed the
average result using the accuracy or F1 of each task. “reimpl” is our re-
implementation of finetuning, used by both XLM-R and XLM-V. Please refer to
the appendix for specific hyperparameters to reproduce each result. EM stands
for exact match. ANLI refers to AmericasNLI and MNER refers to MasakhaNER.

###  4.1 Baselines

Aside from training XLM-V, we also construct several baselines to compare our
model against. To construct our baselines, we first create the respective
vocabularies and then pretrain transformer encoders (12-layers, equivalent to
XLM-R base) using these vocabularies. For the rest of the paper, we will use
the following names to refer to the vocabulary and the model interchangeably.

#### XLM-R (250K)

The XLM-R vocabulary is created using the same procedure from Conneau et al.
(2019) by applying the ULM algorithm described in Section 2 on a corpus of 1B
lines of text sampled from CC100. The result is a multilingual vocabulary with
250,002 tokens. For our experiments, we simply re-use the publicly available
XLM-R sentencepiece model and pretrained model checkpoint from fairseq Ott et
al. (2019).

#### XLM-R (1M)

We construct a 1M token vocabulary by following the same approach as XLM-R
(250K) with an increased vocabulary capacity.

####  Chung et al. (2020) (1M)

We create a 1M token vocabulary using the lexical clustering approach from
Chung et al. 2020 as described in Section 2.

###  4.2 Datasets

CC100 Conneau et al. (2019) is a multilingual corpus created from one Common
Crawl dump for English and twelve dumps for all other languages. The resulting
corpus contains 2.5 TB of data split between 116 languages. We use this
dataset exclusively for constructing vocabularies and pretraining our models.

#### FLoRes-200

Goyal et al. (2022) is an evaluation corpus consisting of 3,001 sentences
extracted from 842 English Wikipedia articles and covering a variety of
different topics and domains. These sentences have been translated into 200
languages by professional translators through a carefully controlled process.

#### XNLI

Conneau et al. (2018) asks whether a premise sentence entails, contradicts, or
is neutral toward a hypothesis sentence. Crowd-sourced English data is
translated to 10 other languages by professional human translators and used
for evaluation, while the Multi-Genre Natural Language Inference Corpus
(MultiNLI) Williams et al. (2018) data is used for training.

#### MLQA

Lewis et al. (2019) 222For the question answering tasks, instead of validating
the selected spans after retrieving the n-best answers, we propose to only
retrieve n-best answer spans that are valid (e.g. span start and end indices
are part of the passage context). This change improves QA performance for both
the baseline models and XLM-V. is a QA evaluation dataset created by mining
target language sentences that are parallel to sentences in English from
Wikipedia, crowd-sourcing annotations in English, and translating the question
and aligning the answer spans in one of the 6 target languages. It consists of
over 12K QA instances in English and 5K in each other language. The training
set of MLQA is SQuAD v1.1 Rajpurkar et al. (2016).

#### XQuAD

Artetxe et al. (2019) translates the dev set of SQuAD v1.1 into 10 other
languages through professional translators. The resulting dataset is used for
evaluation. The training set of XQuAD is SQuAD v1.1.

#### TyDiQA-GoldP

Clark et al. (2020) is a question answering (QA) dataset covering 11
typologically diverse languages with 200K QA pairs. Questions in TyDiQA are
written without seeing the answers leading to significantly less lexical
overlap than XQuAD or MLQA. The languages of TyDiQA are selected to be diverse
with regard to their typology. We use the gold passage version of the
Typologically Diverse Question Answering dataset.

#### NER

Pan et al. (2017) consists of 48 languages and is based on the WikiAnn (PAN-X)
dataset. Named entities were automatically annotated with LOC, PER, and ORG
tags through knowledge base properties, crosslingual and anchor links, self-
training, and data selection. Similar to Hu et al. (2020), we use the balanced
dev and test splits from Rahimi et al. (2019).

#### Americas NLI

Ebrahimi et al. (2021) is an extension of XNLI to 10 indigenous languages of
the Americas constructed by translating a subset of XNLI using human
translators. These languages contain interesting linguistic features such as a
rich system of applicative suffixes (Asháninka), directional verbs (Bribri),
and nominal incorporation (Wixarika). Presently, these languages are written,
spoken, and used in an official capacity by tens of thousands to several
million people in Central and Southern America. The training set of Americas
NLI is MultiNLI.

#### MasakhaNER

Adelani et al. (2021) is the first large, publicly available, and high-quality
dataset for named entity recognition (NER) in ten African languages including
Amharic, Hausa, Igbo, and others. The languages covered in this dataset have
varied scripts and range from 4M to 98M speakers in regions across East, West,
Central, and Northwest Africa.

##  5 Results

Model |  en |  fr |  es |  de |  el |  bg |  ru |  tr |  ar |  vi |  th |  zh |  hi |  sw |  ur |  AVG
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Finetune multilingual model on English training set (Cross-lingual Transfer) |  |  |  |  |
XLM-R reimpl. | 85.4 | 78.5 | 79.1 | 77.7 | 76.1 | 78.1 | 76.3 | 73.9 | 72.3 | 75.6 | 73.0 | 74.9 | 70.5 | 65.8 | 66.5 | 74.9
XLM-V | 85.6 | 79.6 | 79.5 | 78.4 | 76.9 | 79.6 | 76.6 | 74.0 | 73.1 | 76.2 | 73.0 | 75.1 | 72.0 | 70.5 | 69.4 | 76.0
Finetune multilingual model on all training sets (Translate-Train-All) |  |  |  |  |  |
XLM-R reimpl. | 85.4 | 81.5 | 82.0 | 80.7 | 80.2 | 81.2 | 78.9 | 78.4 | 77.6 | 79.9 | 77.6 | 79.5 | 75.8 | 73.4 | 72.3 | 79.0
XLM-V | 85.6 | 81.5 | 82.1 | 81.5 | 80.7 | 81.5 | 79.6 | 78.7 | 77.6 | 80.0 | 77.7 | 79.5 | 77.0 | 74.3 | 73.9 | 79.4
Table 3: XLM-V outperforms XLM-R on cross-lingual transfer on every language in XNLI with outsized improvements on the lower-resource languages, Swahili and Urdu. We observe similar improvements on translate-train-all. The model is trained for 12 epochs (2 epochs for translate-train-all) on 8 A100 GPUs with float16 precision. We use a learning rate of 7.5e-6 with a max sequence length of 256, a batch size of 16, no weight decay, and no warmup. Model |  aym |  bzd |  cni |  gn |  hch |  nah |  oto |  quy |  shp |  tar |  AVG
---|---|---|---|---|---|---|---|---|---|---|---
XLM-R reimpl. | 36.6 | 39.6 | 40.5 | 41.6 | 38.8 | 40.2 | 39.4 | 38.7 | 42.7 | 37.6 | 39.6
XLM-V | 39.9 | 41.5 | 41.7 | 58.8 | 40.7 | 44.7 | 42.1 | 56.9 | 46.5 | 41.2 | 45.4
Tok. Length (rel.) | -10.8% | -11.6% | -11.9% | -16.5% | -6.5% | -10.7% | -8.4% | -18.4% | -10.9% | -9.1% | -11.5%
Table 4: We show the zero-shot cross-lingual transfer results on Americas NLI
(trained on English and evaluated on the unseen languages). Our model, XLM-V,
outperforms XLM-R by a wide margin with outsized improvements on Quechua and
Guaraní. Tok. Length (rel.) refers to the relative difference in the average
number of tokens (post-tokenization) between XLM-R and XLM-V. XLM-V
consistently outputs shorter sequences post-tokenization. The model is trained
for 12 epochs on 8 A100 GPUs with float16 precision. We use a learning rate of
7.5e-6 with a max sequence length of 256, batch size of 16, no weight decay,
and no warmup.

###  5.1 Comparisons using partial training

We first perform a study to measure the impact of our new vocabulary on
downstream performance. Specifically, we pretrain a 12-layer transformer
encoder model using Masked Language Modeling on the CC100 corpus for each
baseline as well as for our proposed method. Because pretraining is expensive,
we limit the batch size to 2,048 and the number of total steps to 300,000 for
these experiments. The results in Figure 2 show that our model outperforms all
baselines on XNLI including XLM-R (1M) by 1.34% and Chung et al. (2020) by
1.11% absolute accuracy.

Figure 2: We compare the performance of the same model trained with different
sentencepiece vocabularies. The models are all trained for 300K iterations
with a batch size of 2,048 on the CC100 corpus.

###  5.2 Fully trained model

We evaluate an XLM-V (1M) model, trained on CC100 for 1.5M iterations with a
batch size of 8,192, on several tasks including natural language inference
(XNLI), question answering (MLQA, TyDiQA, and XQuAD), named enitity
recognition (WikiAnn), and low resource language tasks (AmericasNLI,
MasakhaNER). All tasks leverage crosslingual transfer from English-only
finetuning and are trained using float16 precision with the AdamW optimizer
Loshchilov and Hutter (2017). We use hyperparameters selected based on the
best English performance on the dev set,333For tasks trained on MNLI we follow
Conneau et al. (2019) and select the checkpoint with the best average
performance across all languages. and finally evaluate on the test set. We
compile all of our results in Table 2 for XLM-V and XLM-R. We also include
results for XLM Lample and Conneau (2019) for additional context.

Table 2 shows that XLM-V outperforms our re-implementation of XLM-R on all
datasets by an average of 3.5 points absolute (we compute the average result
using either the accuracy or F1 of each task). In Table 3, we show that XLM-V
outperforms XLM-R on all languages in cross-lingual transfer (training on
English and evaluating on other languages) with similar improvements on
translate-train-all (finetuning the model on both the English and translated
training sets). In particular, we find that XLM-V consistently outperforms
XLM-R on low-resource languages. For example, in Table 3, we observe a 4.7%
and 2.9% accuracy improvement on Swahili (sw) and Urdu (ur) on XNLI.
Similarly, we show an average gain of 11.2% F1 on MasakhaNER, a low-resource
African language NER dataset.

In Table 4 we show that XLM-V not only consistently outperforms XLM-R on
Americas NLI in zero-shot crosslingual transfer but is able to obtain 18.2%
absolute F1 improvement on Quechua (quy) and 17.2% absolute improvement on
Guaraní (gn). Interestingly, Quechua and Guaraní are also the two languages
with the largest relative drop in average token count per sentence –
suggesting that these languages are over-tokenized by XLM-R.

##  6 Analysis

Language | Tokenizer | Tokenized Output
---|---|---
zh | Original Sentence | 剑桥大学本科生和研究生
XLM-R (250K) | [’剑’, ’桥’, ’大学’, ’本科’, ’生’, ’和’, ’研究生’]
XLM-R (1M) | [’剑’, ’桥’, ’大学’, ’本’, ’科’, ’生’, ’和’, ’研究’, ’生’]
Chung et al. (2020) (1M) | [’剑桥’, ’大学本科’, ’生’, ’和’, ’研究生’]
XLM-V (1M) | [’剑桥大学’, ’本科生’, ’和’, ’研究生’]
en, fr, es | Original Sentence | narcolepsy narcolepsie narcolepsia
XLM-R (250K) | [’▁na’, ’r’, ’cole’, ’psy’] [’▁na’, ’r’, ’cole’, ’psi’, ’e’] [’▁na’, ’r’, ’cole’, ’psi’, ’a’]
XLM-R (1M) | [’▁na’, ’rcole’, ’psy’] [’▁na’, ’rcole’, ’psie’] [’▁na’, ’rcole’, ’psia’]
Chung et al. (2020) (1M) | [’▁na’, ’rcole’, ’psy’] [’▁narco’, ’lepsi’, ’e’] [’▁na’, ’rcole’, ’psia’]
XLM-V (1M) | [’▁narco’, ’le’, ’psy’] [’▁narco’, ’lepsi’, ’e’] [’▁narco’, ’lepsi’, ’a’]
de | Original Sentence | Betäubungsmittelverschreibungsverordnung
XLM-R (250K) | [’▁Be’, ’tä’, ’ub’, ’ungs’, ’mittel’, ’ver’, ’schreibung’, ’s’, ’ver’, ’ordnung’]
XLM-R (1M) | [’▁Be’, ’tä’, ’ub’, ’ungsmittel’, ’ver’, ’schreibung’, ’s’, ’verordnung’]
Chung et al. (2020) (1M) | [’▁Bet’, ’äub’, ’ungsmittel’, ’ver’, ’schreibung’, ’sverordnung’]
XLM-V (1M) | [’▁Bet’, ’äub’, ’ungsmittel’, ’ver’, ’schreibung’, ’sverordnung’]
Table 5: We provide examples comparing tokenization using the XLM-V vocabulary against baselines. We find that our sentencepiece model reduces overtokenization and can be surprisingly good at splitting sentences into pseudo-meaningful segments out-of-the-box. Model |  vi |  zh |  fr |  de |  en |  xho |  tel |  AVG
---|---|---|---|---|---|---|---|---
XLM-R (250K) | 34.3 | 28.5 | 37.5 | 33.9 | 29.1 | 43.9 | 38.8 | 43.6
XLM-R (1M) | 33.5 | 31.7 | 34.8 | 31 | 26.8 | 40.3 | 41.6 | 41.4
Chung et al. (2020) (1M) | 32.7 | 24.4 | 32.9 | 29.1 | 27.8 | 29.2 | 25.7 | 37.7
XLM-V (1M) | 32.4 | 23.4 | 32.2 | 28.3 | 25.5 | 37.4 | 33.2 | 38.6
Table 6: Average number of tokens after tokenization on the FLoRes-200 dataset
for several high, medium, and low resource languages. AVG denotes the average
tokenized lengths per sentence across all 200 languages in Flores-200. Figure
3: We compare the token utilization of each sentencepiece vocabulary on the
FLoRes-200 dataset. We see diminishing returns as the size of the vocabulary
is increased beyond 1M tokens.

###  6.1 The Zipf ceiling

We explored training models with vocabulary sizes greater than 1M tokens but
found that these models perform comparatively worse on downstream tasks. We
visualize the diminishing utility of increasing the vocabulary size in Figure
3. Specifically, we create vocabularies with 500K, 1M, 1.5M, and 2M tokens
using our methodology. Then, we use these vocabularies to tokenize the
FLoRes-200 dataset. For vocabulary sizes of 500K, 1M, and 2M, we find that 99%
of the content is covered by just 140,337, 197,817, and 243,832 unique tokens,
respectively.

We hypothesize that since the Unigram LM Kudo and Richardson (2018) algorithm
used to construct the vocabulary iteratively prunes a large initial set, as
discussed in Section 2, further expanding the vocabulary is equivalent to
inheriting tokens from the long tail of a Zipfian distribution. These token
embeddings are problematic because they are trained on significantly less data
during the course of MLM pretraining and will learn sub-optimal
representations as a result. As a consequence, vocabularies past a certain
size will cease to improve model performance and can potentially degrade it. A
clear example of this is shown in Figure 2 where our model with a 1M token
vocabulary outperforms its 1.5M token counterpart trained using an equivalent
amount of data.

###  6.2 Qualitative improvements in tokenization

Table 5 shows a few tokenized examples from Chinese (zh), English (en), French
(fr), Spanish (es), and German (de). For languages in the same cluster (en,
fr, es), our method can separate shared roots (e.g. narco) from the same word
in different languages. Notably, our method demonstrates a surprising ability
to segment Chinese out-of-the-box, parsing out individual entities in the
original phrase. For example, the XLM-V tokenizer is able to meaningfully
break down the phrase 剑桥大学本科生和研究生, translated as Cambridge University
undergraduates and postgraduates. Specifically, the output of the XLM-V
tokenizer is 剑桥大学 (Cambridge University), 本科生 (undergraduates), 和 (and), and
研究生 (postgraduates). Qualitatively, our tokenizer frequently performs
tokenizations that are semantically meaningful, one possible contributor to
the improved downstream performance.

###  6.3 Over-tokenization

Representing input data with fewer tokens can speed up inference, allow the
model to make use of longer context, and help with over-tokenization for low-
resource languages Rust et al. (2020). Table 6 shows the average number of
resulting tokens (post-tokenization) for several languages in FLoRes-200. On
average, the XLM-V tokenizer returns fewer tokens for high and medium resource
languages while Chung et al. (2020) returns the fewest tokens for low-resource
languages. Overall, XLM-V returns 11.5% fewer tokens compared to the baseline
XLM-R tokenizer, meaning that input sequences are on average 11.5% shorter.

Figure 4: We track training speed vs. vocabulary size using a typical training
setup on XNLI: one A100 GPU, a batch size of 16, sequence length of 128, and
float16 precision. The text above each point denotes the vocabulary size.

###  6.4 Speed vs. size

For XLM-R, which has a vocabulary size of 250K tokens, the vocabulary
embedding matrix contains 77% of the model’s trainable parameters. For XLM-V,
the 1M token vocabulary accounts for 93% of the model’s trainable parameters.
While scaling the vocabulary can markedly increase the number of trainable
parameters in a model, we can treat it as an efficient form of conditional
compute Bengio et al. (2015): only a small fraction of the embedding matrix is
used for any given input. We illustrate the relationship between the
vocabulary size and training speed in Figure 4. By increasing the vocabulary
from 250K to 1M tokens, we can increase the number of trainable parameters by
3.3x with just a 25% increase in training time.

##  7 Related work

###  7.1 Vocabulary-free models

In recent years, vocabulary-free models like ByT4 Xue et al. (2022) and CANINE
Clark et al. (2022) have demonstrated on-par or better performance compared to
their subword tokenization-based counterparts. However, one consistent
drawback of these models is slower training and inference speed. For example,
ByT5 is 6.4 to 9.5 times slower than mT5 Xue et al. (2020) on classification
tasks like XNLI. CANINE fares better, leveraging optimizations like lower
input character dimensions and heavy down sampling, but still remains
approximately 1.6 times slower than a comparable BERT baseline. On the other
hand, simply using a larger sentencepiece vocabulary can improve downstream
performance, increase the capacity of the model, and reduce the over-
tokenization and coverage of low-resource languages all with a smaller impact
on inference latency. We believe that both directions are useful areas of
research and can be explored simultaneously.

###  7.2 Building larger vocabularies

Prior work on vocabulary expansion Wang et al. (2019) sought to augment the
vocabulary of existing models to address out-of-vocabulary (OOV) problems in
multilingual settings. While these results are potentially useful in
augmenting subword models like BERT, sentencepiece models by nature encounter
significantly fewer OOVs.

More recent work on building larger vocabularies Chung et al. (2020); Zheng et
al. (2021) leverage tricks like lexical clustering and more principled methods
for vocabulary allocation have tackled issues with over-tokenization and
vocabulary coverage for low-resource languages. While compelling, these works
are unfortunately limited by data (the models are trained on Wikipedia, a
relatively small pretraining corpus) and scale (the largest vocabulary
explored was 500K, only twice the size of the vocabulary in XLM-R). As such,
the resulting models significantly under-perform the public XLM-R baseline.
Our work seeks to combine and improve upon existing methods for building
large-scale vocabularies, pretrain with substantially bigger datasets, and
explore vocabularies of 1M tokens and beyond.

##  8 Conclusion

In this paper, we presented XLM-V, a multilingual language model with a 1M
token vocabulary. We showed that our model outperforms XLM-R, has outsized
gains on tasks in low-resource languages, results in semantically meaningful
tokenizations, reduces average sequence length, and serves as an efficient
form of conditional compute. In the future, we would like to further
investigate the Zipf ceiling discussed in Section 6 by increasing the
vocabulary beyond 2M tokens while also using more data. Another possible
direction for future work is to explore larger multilingual vocabularies for
autoregressive language models. Finally, further exploration with different
clustering methods such as hierarchical clustering may prove both interesting
and effective.

## Limitations

While the strengths of XLM-V are clear, there remains several scalability
issues that are notable. First, while scaling the vocabulary is an efficient
form of conditional compute, it can result in increased pre-training times due
to the computational complexity of the softmax over the entire vocabulary. We
believe these issues can be solved by adopting approximation techniques like
adaptive softmax Joulin et al. (2017) and adaptive inputs Baevski and Auli
(2018). Additionally, scaling the vocabulary can also significantly increase
the memory footprint of a model. However, we believe memory-related issues
become less of a problem as we begin to work with larger models, where the
number of non-embedding parameters vastly outweigh the size of the vocabulary
embedding matrix.

## References

  * Adelani et al. (2021) David Ifeoluwa Adelani, Jade Abbott, Graham Neubig, Daniel D’souza, Julia Kreutzer, Constantine Lignos, Chester Palen-Michel, Happy Buzaaba, Shruti Rijhwani, Sebastian Ruder, et al. 2021.  Masakhaner: named entity recognition for african languages.  _Transactions of the Association for Computational Linguistics_ , 9:1116–1131.
  * Artetxe et al. (2019) Mikel Artetxe, Sebastian Ruder, and Dani Yogatama. 2019.  On the cross-lingual transferability of monolingual representations.  _arXiv preprint arXiv:1910.11856_.
  * Baevski and Auli (2018) Alexei Baevski and Michael Auli. 2018.  Adaptive input representations for neural language modeling.  _arXiv preprint arXiv:1809.10853_.
  * Bengio et al. (2015) Emmanuel Bengio, Pierre-Luc Bacon, Joelle Pineau, and Doina Precup. 2015.  Conditional computation in neural networks for faster models.  _arXiv preprint arXiv:1511.06297_.
  * Chung et al. (2020) Hyung Won Chung, Dan Garrette, Kiat Chuan Tan, and Jason Riesa. 2020.  Improving multilingual models with language-clustered vocabularies.  _EMNLP_.
  * Clark et al. (2020) Jonathan H Clark, Eunsol Choi, Michael Collins, Dan Garrette, Tom Kwiatkowski, Vitaly Nikolaev, and Jennimaria Palomaki. 2020.  Tydi qa: A benchmark for information-seeking question answering in typologically diverse languages.  _Transactions of the Association for Computational Linguistics_ , 8:454–470.
  * Clark et al. (2022) Jonathan H Clark, Dan Garrette, Iulia Turc, and John Wieting. 2022.  Canine: Pre-training an efficient tokenization-free encoder for language representation.  _Transactions of the Association for Computational Linguistics_ , 10:73–91.
  * Conneau et al. (2019) Alexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Unsupervised cross-lingual representation learning at scale.  _arXiv preprint arXiv:1911.02116_.
  * Conneau et al. (2018) Alexis Conneau, Guillaume Lample, Ruty Rinott, Adina Williams, Samuel R Bowman, Holger Schwenk, and Veselin Stoyanov. 2018.  Xnli: Evaluating cross-lingual sentence representations.  _arXiv preprint arXiv:1809.05053_.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Ebrahimi et al. (2021) Abteen Ebrahimi, Manuel Mager, Arturo Oncevay, Vishrav Chaudhary, Luis Chiruzzo, Angela Fan, John Ortega, Ricardo Ramos, Annette Rios, Ivan Vladimir, et al. 2021.  Americasnli: Evaluating zero-shot natural language understanding of pretrained multilingual models in truly low-resource languages.  _arXiv preprint arXiv:2104.08726_.
  * Goyal et al. (2021) Naman Goyal, Jingfei Du, Myle Ott, Giri Anantharaman, and Alexis Conneau. 2021.  Larger-scale transformers for multilingual masked language modeling.  _arXiv preprint arXiv:2105.00572_.
  * Goyal et al. (2022) Naman Goyal, Cynthia Gao, Vishrav Chaudhary, Peng-Jen Chen, Guillaume Wenzek, Da Ju, Sanjana Krishnan, Marc’Aurelio Ranzato, Francisco Guzman, and Angela Fan. 2022.  The flores-101 evaluation benchmark for low-resource and multilingual machine translation.  _Transactions of the Association for Computational Linguistics_ , 10:522–538.
  * Hu et al. (2020) Junjie Hu, Sebastian Ruder, Aditya Siddhant, Graham Neubig, Orhan Firat, and Melvin Johnson. 2020.  Xtreme: A massively multilingual multi-task benchmark for evaluating cross-lingual generalisation.  In _International Conference on Machine Learning_ , pages 4411–4421. PMLR.
  * Joulin et al. (2017) Armand Joulin, Moustapha Cissé, David Grangier, Hervé Jégou, et al. 2017\.  Efficient softmax approximation for gpus.  In _International conference on machine learning_ , pages 1302–1310. PMLR.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_.
  * Kudo and Richardson (2018) Taku Kudo and John Richardson. 2018.  Sentencepiece: A simple and language independent subword tokenizer and detokenizer for neural text processing.  _arXiv preprint arXiv:1808.06226_.
  * Lample and Conneau (2019) Guillaume Lample and Alexis Conneau. 2019.  Cross-lingual language model pretraining.  _arXiv preprint arXiv:1901.07291_.
  * Lewis et al. (2019) Patrick Lewis, Barlas Oğuz, Ruty Rinott, Sebastian Riedel, and Holger Schwenk. 2019.  Mlqa: Evaluating cross-lingual extractive question answering.  _arXiv preprint arXiv:1910.07475_.
  * Lin et al. (2021) Xi Victoria Lin, Todor Mihaylov, Mikel Artetxe, Tianlu Wang, Shuohui Chen, Daniel Simig, Myle Ott, Naman Goyal, Shruti Bhosale, Jingfei Du, et al. 2021.  Few-shot learning with multilingual language models.  _arXiv preprint arXiv:2112.10668_.
  * Liu et al. (2020) Yinhan Liu, Jiatao Gu, Naman Goyal, Xian Li, Sergey Edunov, Marjan Ghazvininejad, Mike Lewis, and Luke Zettlemoyer. 2020.  Multilingual denoising pre-training for neural machine translation.  _Transactions of the Association for Computational Linguistics_ , 8:726–742.
  * Loshchilov and Hutter (2017) Ilya Loshchilov and Frank Hutter. 2017.  Decoupled weight decay regularization.  _arXiv preprint arXiv:1711.05101_.
  * Ott et al. (2019) Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. 2019.  Fairseq: A fast, extensible toolkit for sequence modeling.  _arXiv preprint arXiv:1904.01038_.
  * Pan et al. (2017) Xiaoman Pan, Boliang Zhang, Jonathan May, Joel Nothman, Kevin Knight, and Heng Ji. 2017.  Cross-lingual name tagging and linking for 282 languages.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1946–1958.
  * Rahimi et al. (2019) Afshin Rahimi, Yuan Li, and Trevor Cohn. 2019.  Massively multilingual transfer for ner.  _arXiv preprint arXiv:1902.00193_.
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016.  Squad: 100,000+ questions for machine comprehension of text.  _arXiv preprint arXiv:1606.05250_.
  * Rust et al. (2020) Phillip Rust, Jonas Pfeiffer, Ivan Vulić, Sebastian Ruder, and Iryna Gurevych. 2020.  How good is your tokenizer? on the monolingual performance of multilingual language models.  _arXiv preprint arXiv:2012.15613_.
  * Scao et al. (2022) Teven Le Scao, Angela Fan, Christopher Akiki, Ellie Pavlick, Suzana Ilić, Daniel Hesslow, Roman Castagné, Alexandra Sasha Luccioni, François Yvon, Matthias Gallé, et al. 2022.  Bloom: A 176b-parameter open-access multilingual language model.  _arXiv preprint arXiv:2211.05100_.
  * Viterbi (1967) Andrew Viterbi. 1967.  Error bounds for convolutional codes and an asymptotically optimum decoding algorithm.  _IEEE transactions on Information Theory_ , 13(2):260–269.
  * Wang et al. (2019) Hai Wang, Dian Yu, Kai Sun, Janshu Chen, and Dong Yu. 2019.  Improving pre-trained multilingual models with vocabulary expansion.  _arXiv preprint arXiv:1909.12440_.
  * Wikipedia (2023) Wikipedia. 2023.  Table of general standard chinese characters — wikipedia, the free encyclopedia.  http://en.wikipedia.org/w/index.php?title=Table%20of%20General%20Standard%20Chinese%20Characters&oldid=1123968033.  [Online; accessed 05-January-2023].
  * Williams et al. (2018) Adina Williams, Nikita Nangia, and Samuel R Bowman. 2018.  The multi-genre nli corpus.
  * Xue et al. (2022) Linting Xue, Aditya Barua, Noah Constant, Rami Al-Rfou, Sharan Narang, Mihir Kale, Adam Roberts, and Colin Raffel. 2022.  Byt5: Towards a token-free future with pre-trained byte-to-byte models.  _Transactions of the Association for Computational Linguistics_ , 10:291–306.
  * Xue et al. (2020) Linting Xue, Noah Constant, Adam Roberts, Mihir Kale, Rami Al-Rfou, Aditya Siddhant, Aditya Barua, and Colin Raffel. 2020.  mt5: A massively multilingual pre-trained text-to-text transformer.  _arXiv preprint arXiv:2010.11934_.
  * Zheng et al. (2021) Bo Zheng, Li Dong, Shaohan Huang, Saksham Singhal, Wanxiang Che, Ting Liu, Xia Song, and Furu Wei. 2021.  Allocating large vocabulary capacity for cross-lingual language model pre-training.  _EMNLP_.

##  Appendix A Appendix

##  Appendix B Appendix

We show the per-language results for each task we tested on. For the sake of
reproducibility, we also provide the hyperparameters that we used to finetune
the model for each task.

Model |  en |  es |  de |  ar |  hi |  vi |  zh |  AVG
---|---|---|---|---|---|---|---|---
XLM-R reimpl. | 65.9 / 78.7 | 50.4 / 67.7 | 47.6 / 62.2 | 36.8 / 55.8 | 42.1 / 59.3 | 45.2 / 65.2 | 37.8 / 60.7 | 46.5 / 64.2
XLM-V | 67.5 / 80.4 | 51.1 / 69.4 | 49.8 / 64.3 | 38.1 / 58.2 | 44.5 / 62.7 | 46.4 / 67.2 | 36.3 / 59.9 | 47.7 / 66.0

Table 7: MLQA results (EM/F1). The model is trained for 2 epochs on a single A100 GPU with float16 precision. We use a learning rate of 3e-5 with a max sequence length of 512, batch size of 6, no weight decay, and no warmup. Model |  en |  ar |  bn |  fi |  id |  ko |  ru |  sw |  te |  AVG
---|---|---|---|---|---|---|---|---|---|---
XLM-R reimpl. | 55.5/68.6 | 42.0/63.9 | 18.6/37.6 | 42.8/61.6 | 54.7/73.1 | 23.6/39.9 | 31.5/59.9 | 30.7/54.1 | 27.5/44.3 | 36.3/55.9
XLM-V | 52.3/66.9 | 45.4/65.5 | 27.4/42.7 | 46.0/63.6 | 56.1/72.3 | 22.8/37.4 | 31.5/59.3 | 43.1/61.4 | 32.4/43.2 | 39.7/56.9
Table 8: TyDiQA-GoldP results (EM/F1). The model is trained for 8 epochs on a single A100 GPU with float16 precision. We use a learning rate of 3e-5 with a max sequence length of 512, batch size of 6, no weight decay, and no warmup. Model |  en |  es |  de |  el |  ru |  tr
---|---|---|---|---|---|---
XLM-R reimpl. | 72.1 / 83.5 | 58.5 / 76.5 | 57.6 / 73.0 | 55.4 / 72.2 | 56.6 / 73.1 | 52.2 / 68.3
XLM-V | 72.9 / 84.2 | 60.3 / 78.1 | 57.3 / 75.1 | 53.5 / 72.4 | 56.0 / 73.2 | 51.8 / 67.5
|  ar |  vi |  th |  zh |  hi |  AVG
XLM-R reimpl. | 49.2 / 65.9 | 53.5 / 72.9 | 55.7 / 66.3 | 55.5 / 65.3 | 49.8 / 57.7 | 56.0 / 71.3
XLM-V | 51.2 / 67.5 | 53.7 / 73.1 | 56.9 / 67.0 | 53.5 / 63.1 | 51.9 / 69.4 | 56.3 / 71.9
Table 9: XQuAD Results (EM/F1). The model is trained for 2 epochs on a single A100 GPU with float16 precision. We use a learning rate of 3e-5 with a max sequence length of 512, batch size of 6, no weight decay, and no warmup. Model |  ro |  gu |  pa |  lt |  az |  uk |  pl |  qu |  hu |  fi |  et |  tr |  kk |  zh |  my |  yo |  sw
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
XLM-R reimpl. | 73.5 | 62.9 | 53.6 | 72.7 | 61.0 | 72.4 | 77.5 | 60.4 | 75.8 | 74.4 | 71.2 | 75.4 | 42.2 | 25.3 | 48.9 | 33.6 | 66.3
XLM-V | 73.8 | 66.4 | 48.7 | 75.6 | 66.7 | 65.7 | 79.5 | 70.0 | 79.5 | 78.7 | 75.0 | 77.3 | 50.4 | 30.2 | 61.5 | 54.2 | 72.4
|  th |  ko |  ka |  ja |  ru |  bg |  es |  pt |  it |  fr |  fa |  ur |  mr |  hi |  bn |  el |  de
XLM-R reimpl. | 5.2 | 49.4 | 65.4 | 21.0 | 63.1 | 76.1 | 70.2 | 77.0 | 76.9 | 76.5 | 44.6 | 51.4 | 61.5 | 67.2 | 69.0 | 73.8 | 74.4
XLM-V | 3.3 | 53.0 | 69.5 | 22.4 | 68.1 | 79.8 | 74.5 | 80.5 | 78.7 | 77.6 | 50.6 | 48.9 | 59.8 | 67.3 | 72.6 | 76.7 | 76.8
|  en |  nl |  af |  te |  ta |  ml |  eu |  tl |  ms |  jv |  id |  vi |  he |  ar |  AVG |  |
XLM-R reimpl. | 83.0 | 80.0 | 75.83 | 49.2 | 56.3 | 61.9 | 57.2 | 69.8 | 68.3 | 59.4 | 48.6 | 67.7 | 53.2 | 43.8 | 61.3 |  |
XLM-V | 83.4 | 81.4 | 78.3 | 51.8 | 54.9 | 63.1 | 67.1 | 75.6 | 70.0 | 67.5 | 52.6 | 67.1 | 60.1 | 45.8 | 64.7 |  |
Table 10: NER Results. The model is trained for 10 epochs on a single A100 GPU with float16 precision. We use a learning rate of 2e-5 with a max sequence length of 128, batch size of 32, no weight decay, and no warmup. Model |  amh |  hau |  ibo |  kin |  lug |  luo |  pcm |  swa |  wol |  yor |  AVG
---|---|---|---|---|---|---|---|---|---|---|---
XLM-R reimpl. | 25.1 | 43.5 | 11.6 | 9.4 | 9.5 | 8.4 | 36.8 | 48.9 | 5.3 | 10.0 | 20.9
XLM-V | 20.6 | 35.9 | 45.9 | 25.0 | 48.7 | 10.4 | 38.2 | 44.0 | 16.7 | 35.8 | 32.1
Table 11: We show the zero-shot cross-lingual transfer results on MasakhaNER
(trained on English and evaluated on the unseen languages). The model is
trained for 10 epochs on a single A100 GPU with float16 precision. We use a
learning rate of 2e-5 with a max sequence length of 128, batch size of 32, no
weight decay, and no warmup.


$\displaystyle=m^{M-M_{2}-M_{4}}m^{M_{2}+M_{4}}n^{k-M_{2}}{\rho_{\mathrm{a}}}^{2M_{2}+M_{4}}{q_{\mathrm{a}}}^{M_{4}}{\rho_{\mathrm{u}}}^{2k}$
$\displaystyle=m^{M-M_{2}-M_{4}}(m\rho_{\mathrm{a}}^{2}\rho_{\mathrm{u}}^{2})^{M_{2}}(m{q_{\mathrm{a}}}{\rho_{\mathrm{a}}})^{M_{4}}(n\rho_{\mathrm{u}}^{2})^{k-M_{2}}.$

Suppose $m{q_{\mathrm{a}}}{\rho_{\mathrm{a}}}\geq 1$, then we have

$\displaystyle
m^{M-M_{2}-M_{4}}(m\rho_{\mathrm{a}}^{2}\rho_{\mathrm{u}}^{2})^{M_{2}}(m{q_{\mathrm{a}}}{\rho_{\mathrm{a}}})^{M_{4}}(n\rho_{\mathrm{u}}^{2})^{k-M_{2}}$
$\displaystyle\geq
m^{M-M_{2}-M_{4}}(m\rho_{\mathrm{a}}^{2}\rho_{\mathrm{u}}^{2})^{M_{2}}(n\rho_{\mathrm{u}}^{2})^{k-M_{2}}$
$\displaystyle\geq
m^{M-M_{2}-M_{4}}(\min\\{m\rho_{\mathrm{a}}^{2}\rho_{\mathrm{u}}^{2},n\rho_{\mathrm{u}}^{2}\\})^{k}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\omega(n^{2}),$

where (c) follows because
$m\rho_{\mathrm{a}}^{2}\rho_{\mathrm{u}}^{2}=\omega(n^{2/k})$ and
$n\rho_{\mathrm{u}}^{2}=\omega(n^{2/k})$.

Suppose $m{q_{\mathrm{a}}}{\rho_{\mathrm{a}}}<1$. Because $M_{4}\leq k-M_{2}$,
we have

$\displaystyle
m^{M-M_{2}-M_{4}}(m\rho_{\mathrm{a}}^{2}\rho_{\mathrm{u}}^{2})^{M_{2}}(m{q_{\mathrm{a}}}{\rho_{\mathrm{a}}})^{M_{4}}(n\rho_{\mathrm{u}}^{2})^{k-M_{2}}$
$\displaystyle\geq
m^{M-M_{2}-M_{4}}(m\rho_{\mathrm{a}}^{2}\rho_{\mathrm{u}}^{2})^{M_{2}}(m{q_{\mathrm{a}}}{\rho_{\mathrm{a}}}n\rho_{\mathrm{u}}^{2})^{k-M_{2}}$
$\displaystyle\geq
m^{M-M_{2}-M_{4}}(\min\\{m\rho_{\mathrm{a}}^{2}\rho_{\mathrm{u}}^{2},m{q_{\mathrm{a}}}{\rho_{\mathrm{a}}}n\rho_{\mathrm{u}}^{2}\\})^{k}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}\omega(n^{2}),$

where (d) follows by assumptions
$m\rho_{\mathrm{a}}^{2}\rho_{\mathrm{u}}^{2}=\omega(n^{2/k})$ and
$m{q_{\mathrm{a}}}{\rho_{\mathrm{a}}}n\rho_{\mathrm{u}}^{2}=\omega(n^{2/k})$.

Next, we show that $\tilde{\Gamma}_{ij}=O(\bar{\Gamma}_{ij})$. The key idea in
this part of the proof is that since we already fixed an edge $(i,j)$ in the
union graph of the four tuples in $\tilde{\Lambda}_{ij}$, the choices of the
4-tuples is greatly restricted, and hence, it become a dominated case
comparing to $\bar{\Lambda}_{ij}$.

Firstly, we further partition $\tilde{\Lambda}_{ij}$ into three subsets

$\tilde{\Lambda}_{ij}=\tilde{\Lambda}_{ij}(1)\cup\tilde{\Lambda}_{ij}(2)\cup\tilde{\Lambda}_{ij}(3),$
(84)

where

$\displaystyle\tilde{\Lambda}_{ij}(1)$
$\displaystyle\triangleq\\{(S_{1},S_{2},T_{1},T_{2})\in\tilde{\Lambda}_{ij}:(i,j)\in({\mathcal{E}^{\mathrm{u}}}(S_{1})\cap{\mathcal{E}^{\mathrm{u}}}(T_{1}))\cap({\mathcal{E}^{\mathrm{u}}}(S_{2})\cup{\mathcal{E}^{\mathrm{u}}}(T_{2}))^{c}\\}$
$\displaystyle\tilde{\Lambda}_{ij}(2)$
$\displaystyle\triangleq\\{(S_{1},S_{2},T_{1},T_{2})\in\tilde{\Lambda}_{ij}:(i,j)\in({\mathcal{E}^{\mathrm{u}}}(S_{1})\cup{\mathcal{E}^{\mathrm{u}}}(T_{1}))^{c}\cap({\mathcal{E}^{\mathrm{u}}}(S_{2})\cap{\mathcal{E}^{\mathrm{u}}}(T_{2}))\\}$
$\displaystyle\tilde{\Lambda}_{ij}(3)$
$\displaystyle\triangleq\\{(S_{1},S_{2},T_{1},T_{2})\in\tilde{\Lambda}_{ij}:(i,j)\in{\mathcal{E}^{\mathrm{u}}}(S_{1})\cap{\mathcal{E}^{\mathrm{u}}}(T_{2})\cap{\mathcal{E}^{\mathrm{u}}}(S_{2})\cap{\mathcal{E}^{\mathrm{u}}}(T_{2})\\}.$

In other words, $\tilde{\Lambda}_{ij}(1)$ includes the cases that $(i,j)$ is
shared only by $S_{1},T_{1}$, $\tilde{\Lambda}_{ij}(2)$ includes the cases
that $(i,j)$ is shared only by $S_{2},T_{2}$ and $\tilde{\Lambda}_{ij}(3)$
includes the cases that $(i,j)$ is shared all four graphs. We notice that
$\tilde{\Lambda}_{ij}(1),\tilde{\Lambda}_{ij}(2),\tilde{\Lambda}_{ij}(3)$
indeed partition the set $\tilde{\Lambda}_{ij}$ because of
${\mathcal{E}^{\mathrm{u}}}(S_{1})={\mathcal{E}^{\mathrm{u}}}(T_{1})$ and
${\mathcal{E}^{\mathrm{u}}}(S_{2})={\mathcal{E}^{\mathrm{u}}}(T_{2})$.
Following this definition, we define

$\displaystyle\tilde{\Gamma}_{ij}(t)$
$\displaystyle\triangleq\sigma_{\mathrm{u}}^{4k}\sigma_{\mathrm{a}}^{4k}\sum_{(S_{1},S_{2},T_{1},T_{2})\in\tilde{\Lambda}_{ij}(t)}\Theta^{\mathrm{u}}(S_{1},S_{2},T_{1},T_{2})\Theta^{\mathrm{a}}(S_{1},S_{2},T_{1},T_{2}).$

for each $t\in[3]$. Thus, to show that
$\tilde{\Gamma}_{ij}=O(\bar{\Gamma}_{ij})$, it suffices to show that
$\tilde{\Gamma}_{ij}(t)=O(\bar{\Gamma}_{ij})$ for each $t\in[3]$.

Firstly, we show that $\tilde{\Gamma}_{ij}(1)=o(\bar{\Gamma}_{ij})$. Similarly
to our analysis for $\bar{\Gamma}_{ij}$, we can partition
$\tilde{\Lambda}_{ij}(1)$ as

$\tilde{\Lambda}_{ij}(1)=\bigcup_{0\leq M_{1}+M_{2}+M_{3}+M_{4}\leq
k}\tilde{\Lambda}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}(1),$

according to the number of the four types of shared attributes in the union
graph $H$, and define

$\tilde{\Gamma}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}(1)\triangleq\sigma_{\mathrm{u}}^{4k}\sigma_{\mathrm{a}}^{4k}\sum_{(S_{1},S_{2},T_{1},T_{2})\in\tilde{\Lambda}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}(1)}\Theta^{\mathrm{u}}(S_{1},S_{2},T_{1},T_{2})\Theta^{\mathrm{a}}(S_{1},S_{2},T_{1},T_{2}).$

For each
$(S_{1},S_{2},T_{1},T_{2})\in\tilde{\Lambda}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}(1)$,
it is easy to check that

$\Theta^{\mathrm{u}}(S_{1},S_{2},T_{1},T_{2})=1,$

and

$\Theta^{\mathrm{a}}(S_{1},S_{2},T_{1},T_{2})={\rho_{\mathrm{a}}}^{2k-2M_{2}-2M_{4}}c^{M_{4}}\max\\{1,\tfrac{{\rho_{\mathrm{a}}}^{M_{4}}}{{q_{\mathrm{a}}}^{M_{4}}}\\},$

which are the same as a 4-tuple
$(S_{1},S_{2},T_{1},T_{2})\in\bar{\Lambda}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}$.
However, the cardinality of
$\tilde{\Lambda}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}(1)$ is much smaller than the
cardinality of $\bar{\Lambda}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}$. To see that,
we observe that number of choices of the user-attribute part of the union
graph in $\tilde{\Lambda}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}(1)$ is the same as
the number of choices in $\bar{\Lambda}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}$.
However, the number of ways of choosing the user-user part in
$\tilde{\Lambda}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}(1)$ is upper bounded by

$\sum_{\beta=k-M_{2}}^{k}\binom{n}{\beta}\binom{n}{k-1-\beta}\binom{n}{k-\beta}.$
(85)

This is because we can choose $\beta$ users shared by
$S_{1},S_{2},T_{1},T_{2}$, $k-\beta$ users shared by $T_{1},T_{2}$ and
$k-\beta-1$ _users other than $j$ that are shared by $S_{1},T_{1}$_. If we
compare (85) to (78), we can observe that there is a factor $n$ missing in
(85). This is because one of the users in $S_{1}$ and $T_{1}$ are already
fixed to $j$, so we have one less user to choose. This implies that
$\tilde{\Gamma}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}(1)=O(\bar{\Gamma}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}/n)$
for any $0\leq M_{1}+M_{2}+M_{3}+M_{4}\leq k$, and it follows that
$\tilde{\Gamma}_{ij}(1)=o(\bar{\Gamma}_{ij})$. The proof of
$\tilde{\Gamma}_{ij}(2)=o(\bar{\Gamma}_{ij})$ follows similarly as the proof
of $\tilde{\Gamma}_{ij}(1)=o(\bar{\Gamma}_{ij})$.

Finally, we show that $\tilde{\Gamma}_{ij}(3)=O(\bar{\Gamma}_{ij})$. We
perform the similar partition again:

$\tilde{\Lambda}_{ij}(3)=\bigcup_{0\leq M_{1}+M_{2}+M_{3}+M_{4}\leq
k}\tilde{\Lambda}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}(3),$

according to the number of the four types of shared attributes in the union
graph $H$, and define

$\tilde{\Gamma}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}(3)\triangleq\sigma_{\mathrm{u}}^{4k}\sigma_{\mathrm{a}}^{4k}\sum_{(S_{1},S_{2},T_{1},T_{2})\in\tilde{\Lambda}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}(3)}\Theta^{\mathrm{u}}(S_{1},S_{2},T_{1},T_{2})\Theta^{\mathrm{a}}(S_{1},S_{2},T_{1},T_{2}).$

For each
$(S_{1},S_{2},T_{1},T_{2})\in\tilde{\Lambda}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}(3)$,
in the user-attribute part of the union graph, we still have

$\Theta^{\mathrm{a}}(S_{1},S_{2},T_{1},T_{2})={\rho_{\mathrm{a}}}^{2k-2M_{2}-2M_{4}}c^{M_{4}}\max\\{1,\tfrac{{\rho_{\mathrm{a}}}^{M_{4}}}{{q_{\mathrm{a}}}^{M_{4}}}\\}.$

However, in the user-attribute part, we have $|K_{22}^{\mathrm{u}}|=1$ instead
of $|K_{22}^{\mathrm{u}}|=0$ in the previous case. This is because we have the
edge $(i,j)$ shared by all four graphs. It is easy to check that we still have
$|K_{11}^{\mathrm{u}}|=|K_{12}^{\mathrm{u}}|=|K_{21}^{\mathrm{u}}|=0$. Thus,
we have

$\Theta^{\mathrm{u}}(S_{1},S_{2},T_{1},T_{2})=c\max\\{1,\tfrac{{\rho_{\mathrm{u}}}}{q_{u}}\\}\leq\tfrac{c}{{q_{\mathrm{u}}}}.$

Moreover, if we compare
$|\tilde{\Lambda}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}(3)|$ to
$|\bar{\Lambda}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}|$, we observe that

$\frac{|\tilde{\Lambda}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}(3)|}{|\bar{\Lambda}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}|}=O(1/n^{2}).$

This is because in the union graph of a 4-tuple
$(S_{1},S_{2},T_{1},T_{2})\in\tilde{\Lambda}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}(3)$,
we have two less users to choose, since one of the ports in $S_{1},T_{1}$ is
fixed to $j$ and one of the ports in $S_{2},T_{2}$ is fixed to $i$. As a
result, for any $0\leq M_{1}+M_{2}+M_{3}+M_{4}\leq k$, we have

$\frac{\tilde{\Gamma}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}(3)}{\bar{\Gamma}_{ij}^{(M_{1},M_{2},M_{3},M_{4})}}=O\left(\frac{c}{n^{2}{q_{\mathrm{u}}}}\right)=O(1),$

because of assumption $n^{2}{q_{\mathrm{u}}}=\Omega(1)$. This further implies
that $\tilde{\Gamma}_{ij}(3)=O(\bar{\Gamma}_{ij})$, which completes the proof.

##  Appendix C Proof of Theorem 2

In this section, we prove the theoretical performance guarantee for exact
alignment. Recall that Theorem 1 ensures that Algorithm 1 outputs a set of
users $I$ with $|I|=n-o(n)$ and a mapping $\hat{\Pi}$ with
$\hat{\Pi}(i)=\hat{\Pi}^{*}(i),\forall i\in I$. Therefore, to prove Theorem 2,
it suffices to show that Algorithms 2 and 3 can exactly recover $\Pi^{*}$ with
input $I,\hat{\Pi}$ under the AttrSparse regime and AttrRich regime
respectively. In the following two propositions, we provide performance
guarantee for the two refinement algorithms respectively. To state the two
propositions, we define function

$f(x)\triangleq x\log x-x+1.$

Note that $f(x)$ is a function monotonically decreasing in $(0,1)$, and
monotonically increasing in $(1,\infty)$.

######  Proposition 4 (Feasible region of Algorithm 2 in AttrSparse regime).

Suppose
$(G_{1},G_{2}^{\prime})\sim{\mathcal{G}}(n,{q_{\mathrm{u}}},{\rho_{\mathrm{u}}};m,{q_{\mathrm{a}}},{\rho_{\mathrm{a}}})$,
where

$n\rho_{\mathrm{u}}^{2}=\omega(\log n),$ (86)
$n{q_{\mathrm{u}}}({q_{\mathrm{u}}}+{\rho_{\mathrm{u}}}(1-{q_{\mathrm{u}}}))\geq(1+\epsilon)\log
n$ (87)

and

$\frac{{\rho_{\mathrm{u}}}(1-{q_{\mathrm{u}}})}{{q_{\mathrm{u}}}}\geq\epsilon$
(88)

for some arbitrarily small constant $\epsilon$. Let
$\hat{\pi}\equiv\hat{\pi}(G_{1},G_{2}^{\prime})$ be a mapping
$I\rightarrow[n]$ such that $\hat{\pi}=\pi^{*}|_{I}$ and
$|I|\geq(1-\epsilon/16)n$. Let $\gamma_{1}$ denote the unique solution in
$(1,\infty)$ to $f(\gamma_{1})=\frac{3\log n}{(n-2)q_{\mathrm{u}}^{2}}$. Then
there exists an algorithm, namely Algorithm 2 with inputs $\gamma_{1},I$ and
$\hat{\pi}$, that outputs $\tilde{\pi}=\pi^{*}$ with high probability.

######  Proposition 5 (Feasible region of Algorithm 3 in AttrRich regime).

Suppose $(G_{1},G_{2}^{\prime})\sim{\mathcal{G}}$
$(n,{q_{\mathrm{u}}},{\rho_{\mathrm{u}}};m,{q_{\mathrm{a}}},{\rho_{\mathrm{a}}})$,
where

$n\rho_{\mathrm{u}}^{2}=\omega(\log n),$ (89)
$m\rho_{\mathrm{a}}^{2}=\omega(\log n),$ (90)
$n{q_{\mathrm{u}}}({q_{\mathrm{u}}}+{\rho_{\mathrm{u}}}(1-{q_{\mathrm{u}}}))+m{q_{\mathrm{a}}}({q_{\mathrm{a}}}+{\rho_{\mathrm{a}}}(1-{q_{\mathrm{u}}}))\geq(1+\epsilon)\log
n$ (91)
$n{q_{\mathrm{u}}}({q_{\mathrm{u}}}+{\rho_{\mathrm{u}}}(1-{q_{\mathrm{u}}}))=\Omega(\log
n),$ (92)
$m{q_{\mathrm{a}}}({q_{\mathrm{a}}}+{\rho_{\mathrm{a}}}(1-{q_{\mathrm{u}}}))=\Omega(\log
n),$ (93)
$\frac{{\rho_{\mathrm{u}}}(1-{q_{\mathrm{u}}})}{{q_{\mathrm{u}}}}\geq\epsilon,$
(94)

and

$\frac{{\rho_{\mathrm{a}}}(1-{q_{\mathrm{a}}})}{{q_{\mathrm{a}}}}\geq\epsilon,$
(95)

for some arbitrarily small constant $\epsilon$. Let
$\hat{\pi}\equiv\hat{\pi}(G_{1},G_{2}^{\prime})$ be a mapping
$I\rightarrow[n]$ such that $\hat{\pi}=\pi^{*}|_{I}$ and
$|I|\geq(1-\epsilon/16)n$. Let $\gamma_{2}$ denote the unique solution in
$(1,\infty)$ to $f(\gamma_{2})=\frac{3\log n}{(n-2)q_{\mathrm{u}}^{2}}$, and
let $\gamma_{3}$ denote the unique solution in $(1,\infty)$ to
$f(\gamma_{3})=\frac{3\log n}{mq_{\mathrm{a}}^{2}}$. Then there exists an
algorithm, namely Algorithm 3 with inputs $\gamma_{2},\gamma_{3},I$ and
$\hat{\pi}$, that outputs $\tilde{\pi}=\pi^{*}$ with high probability.

With Propositions 4 and 5, we are now ready to prove Theorem 2.

###### Proof of Theorem 2..

In this proof, we partition the information theoretic feasible region

$n{q_{\mathrm{u}}}({q_{\mathrm{u}}}+{\rho_{\mathrm{u}}}(1-{q_{\mathrm{u}}}))+m{q_{\mathrm{a}}}({q_{\mathrm{a}}}+{\rho_{\mathrm{a}}}(1-{q_{\mathrm{a}}}))\geq(1+\epsilon)\log
n$

into three regimes:

  1. 1.

$m{q_{\mathrm{a}}}({q_{\mathrm{a}}}+{\rho_{\mathrm{a}}}(1-{q_{\mathrm{a}}}))=o(\log
n)$, and
$n{q_{\mathrm{u}}}({q_{\mathrm{u}}}+{\rho_{\mathrm{u}}}(1-{q_{\mathrm{u}}}))\geq(1+\epsilon)\log
n$;

  2. 2.

$m{q_{\mathrm{a}}}({q_{\mathrm{a}}}+{\rho_{\mathrm{a}}}(1-{q_{\mathrm{a}}}))=\Omega(\log
n)$, and
$n{q_{\mathrm{u}}}({q_{\mathrm{u}}}+{\rho_{\mathrm{u}}}(1-{q_{\mathrm{u}}}))=\Omega(\log
n)$;

  3. 3.

$m{q_{\mathrm{a}}}({q_{\mathrm{a}}}+{\rho_{\mathrm{a}}}(1-{q_{\mathrm{a}}}))\geq(1+\epsilon)\log
n$, and
$n{q_{\mathrm{u}}}({q_{\mathrm{u}}}+{\rho_{\mathrm{u}}}(1-{q_{\mathrm{u}}}))=o(\log
n)$,

and separately prove the feasibility of exact alignment in each regime.

In the first regime, by the assumptions in Theorem 2, all the conditions in
Theorem 1 are satisfied, so the outputs $I$ and $\hat{\pi}$ from Algorithm 1
satisfy that $\hat{\pi}=\pi^{*}|_{I}$, and $|I|\geq n-o(n)$ with high
probability. Moreover, because condition (3) implies condition (86) and we
have
$n{q_{\mathrm{u}}}({q_{\mathrm{u}}}+{\rho_{\mathrm{u}}}(1-{q_{\mathrm{u}}}))\geq(1+\epsilon)\log
n$ in this regime, all the conditions in Proposition 4 are satisfied.
Therefore, on the event that $\\{\hat{\pi}=\pi^{*}|_{I}\\}\cap\\{|I|\geq
n-o(n)\\}$, Algorithm 2 outputs $\tilde{\pi}=\pi^{*}$ with high probability.
This completes the proof for the regime.

In the second regime, similarly, we know that the outputs from Algorithm 1
satisfy $\hat{\pi}=\pi^{*}|_{I}$, and $|I|\geq n-o(n)$ with high probability.
Notices that condition (2) implies condition (90), and condition (3) implies
condition (89). By assumptions
$m{q_{\mathrm{a}}}({q_{\mathrm{a}}}+{\rho_{\mathrm{a}}}(1-{q_{\mathrm{u}}}))=\Omega(\log
n)$, and
$n{q_{\mathrm{u}}}({q_{\mathrm{u}}}+{\rho_{\mathrm{u}}}(1-{q_{\mathrm{u}}}))=\Omega(\log
n)$ for the AttrRich regime, we can see that all the conditions in Proposition
5 are satisfied. Thus, on the event
$\\{\hat{\pi}=\pi^{*}|_{I}\\}\cap\\{|I|\geq n-o(n)\\}$, Algorithm 3 outputs
$\tilde{\pi}=\pi^{*}$ with high probability. Therefore, exact recovery is
achieved with high probability.

Finally, consider the third regime. In this regime, we consider a strictly
harder problem where all user-user edges are removed from the two graphs
$G_{1}$ and $G_{2}^{\prime}$. Then both graphs reduce to bipartite graphs with
edges only between the users and the attributes. For this bipartite graph
alignment problem, it is well-known that the optimal MAP estimator can be
implemented efficiently within $O(n^{3})$ complexity (See for example Cullina
et al., (2018)). In Theorem 1 of Zhang et al., (2024), it is shown that the
MAP estimator achieves exact recovery if

$m(\sqrt{q_{11}q_{00}}-\sqrt{q_{01}q_{10}})^{2}\geq\log n+\omega(1),$ (96)

where

$q_{11}\triangleq{q_{\mathrm{a}}}({q_{\mathrm{a}}}+{\rho_{\mathrm{a}}}(1-{q_{\mathrm{a}}})),$
$q_{00}\triangleq
1-{q_{\mathrm{a}}}({q_{\mathrm{a}}}+{\rho_{\mathrm{a}}}(1-{q_{\mathrm{a}}}))-2{q_{\mathrm{a}}}(1-{q_{\mathrm{a}}}-{\rho_{\mathrm{a}}}(1-{q_{\mathrm{a}}}))$

and

$q_{10}=q_{01}\triangleq{q_{\mathrm{a}}}(1-{q_{\mathrm{a}}}-{\rho_{\mathrm{a}}}(1-{q_{\mathrm{a}}})).$

To complete the proof, it suffices to show that (96) is satisfied under
$m{q_{\mathrm{a}}}({q_{\mathrm{a}}}+{\rho_{\mathrm{a}}}(1-{q_{\mathrm{a}}}))\geq(1+\epsilon)\log
n$ and other conditions of Theorem 2. Towards the proof, we define two more
quantities
$s_{\mathrm{a}}\triangleq{q_{\mathrm{a}}}+{\rho_{\mathrm{a}}}(1-{\rho_{\mathrm{a}}})$
and $q\triangleq{q_{\mathrm{a}}}/s_{\mathrm{a}}$. In view of condition (7), we
know that $q$ is bounded away from $1$. We separately consider two regimes of
$q$ to complete the proof.

Firstly, consider the regime $q=o(1)$. Notice that
$\frac{1}{q}=1+\frac{{\rho_{\mathrm{a}}}(1-{q_{\mathrm{a}}})}{{q_{\mathrm{a}}}}$,
we then have ${\rho_{\mathrm{a}}}=\omega({q_{\mathrm{a}}})$, which further
implies that $s_{\mathrm{a}}=(1-o(1)){\rho_{\mathrm{a}}}$. It follows that

$\displaystyle m(\sqrt{q_{11}q_{00}}-\sqrt{q_{01}q_{10}})^{2}$
$\displaystyle\geq m(\sqrt{q_{11}q_{00}}-{q_{\mathrm{a}}})^{2}$
$\displaystyle=m(\sqrt{{q_{\mathrm{a}}}s_{\mathrm{a}}}-{q_{\mathrm{a}}})^{2}(1-o(1))$
$\displaystyle=(1-o(1))m{q_{\mathrm{a}}}s_{\mathrm{a}},$

where the penultimate equality follows because $q=o(1)$ and the last equality
follows because
$s_{\mathrm{a}}=(1-o(1)){\rho_{\mathrm{a}}}=\omega({q_{\mathrm{a}}})$.
Finally, (96) follows by the assumption that
$m{q_{\mathrm{a}}}s_{\mathrm{a}}\geq(1+\epsilon)\log n$.

Next, we consider the regime $q=\Theta(1)$. In this regime, by the definitions
of $q$ and $s_{\mathrm{a}}$, we have
${\rho_{\mathrm{a}}}=\Theta({q_{\mathrm{a}}})$ and
${\rho_{\mathrm{a}}}=\Theta(s_{\mathrm{a}})$. Moreover, we have

$\displaystyle m(\sqrt{q_{11}q_{00}}-\sqrt{q_{01}q_{10}})^{2}$
$\displaystyle=(1-q)m{q_{\mathrm{a}}}s_{\mathrm{a}}\frac{1}{\left(\sqrt{1+\frac{q(1-s_{\mathrm{a}})^{2}}{1-q}}+\sqrt{\frac{q(1-s_{\mathrm{a}})^{2}}{1-q}}\right)^{2}}=\Theta(m{q_{\mathrm{a}}}s_{\mathrm{a}}),$

because $q$ is bounded away from 1. The proof is then completed by realizing

$\displaystyle
m{q_{\mathrm{a}}}s_{\mathrm{a}}=mqs_{\mathrm{a}}^{2}=\Omega(mq\rho_{\mathrm{a}}^{2})=\Omega(n^{\Theta(1)}),$

where the last equality follows by condition (2) and the assumption that
$q=\Theta(1)$. ∎

###  C-A Proof of Proposition 4

In this section, we show that Algorithm 2 achieves exact recovery under the
conditions specified by Proposition 4. Towards that goal, we first present a
lemma in Mao et al., 2023b  that shows an Erdős–Rényi graph
$G\sim{\mathcal{G}}(n,p)$ has good expansion property with high probability.

######  Lemma 5 (Lemma 13 in Mao et al., 2023b ).

Suppose $G\sim{\mathcal{G}}(n,p)$, where $np\geq(1+\epsilon)\log n$ for an
arbitrarily small constant $\epsilon$. Let $\kappa_{G}(I,I^{c})$ denote the
number of edges between $I\subseteq[n]$ and $I^{c}$, where
$I^{c}\triangleq[n]\setminus I$. Then with probability at least
$1-O(n^{-\epsilon/8})$, for all subsets $I\subseteq[n]$ with
$|I|\leq\frac{\epsilon}{16}n$, we have
$\kappa_{G}(I,I^{c})\geq\eta|I||I^{c}|p$, where $\eta$ is the unique solution
in $(0,1)$ to $f(\eta)=\frac{(1+\epsilon/8)\log n}{(1-\epsilon/16)np}$.
Moreover, $\eta$ satisfies lower bound

$\eta\geq\max\left\\{\frac{\epsilon}{16},1-\sqrt{\frac{2(1+\epsilon/8)\log
n}{(1-\epsilon/16)np}}\right\\}.$ (97)

Now, we are ready to prove Proposition 4. We assume without generality that
the true permutation $\pi^{*}$ is the identity permutation. For a pair of user
vertices $i\in{\mathcal{V}^{\mathrm{u}}_{1}}$ and
$j\in{\mathcal{V}^{\mathrm{u}}_{2}}$, let $N^{\mathrm{u}}(i,j)$ denote the
number of user vertices $u\in[n]$ such that $u$ is connected to $i$ in $G_{1}$
and $u$ is connected to $j$ in $G_{2}^{\prime}$. By the definition of the
attributed Erdős–Rényi graph pair model, we have
$N^{\mathrm{u}}(i,j)\sim\mathrm{Binom}(n-2,q_{\mathrm{u}}^{2})$ for any $i\neq
j$. By the multiplicative Chernoff bound (see for example Mitzenmacher and
Upfal, (2005, Theorem 4.4)), we have

${\mathsf{P}}(N^{\mathrm{u}}(i,j)\geq\gamma_{1}(n-2)q_{\mathrm{u}}^{2})\leq\exp(-(n-2)q_{\mathrm{u}}^{2}h(\gamma_{1}))=n^{-3}.$

By a union bound over all the $\binom{n}{2}$ pairs of users, we have that

${\mathsf{P}}(\exists i,j\in[n],i\neq
j:N^{\mathrm{u}}(i,j)\geq\gamma_{1}(n-2)q_{\mathrm{u}}^{2})\leq\binom{n}{2}n^{-3}\leq
n^{-1}.$ (98)

Now, we assume that $\\{\nexists i,j\in[n],i\neq
j:N^{\mathrm{u}}(i,j)\geq\gamma_{1}(n-2)q_{\mathrm{u}}^{2}\\}$. From this, we
are going prove by induction that $\tilde{\pi}=\pi^{*}|_{J}$ throughout out
the process of the algorithm. At the beginning of the algorithm, this
certainly holds because we set $J=I$ and $\tilde{\pi}=\hat{\pi}$. Now we
suppose $\tilde{\pi}=\pi^{*}|_{J}$ up to $l$ calls of the while loop in
Algorithm 2. Consider the $(l+1)$-th call of the while loop. By the induction
hypothesis, we have that

$N^{\mathrm{u}}_{\tilde{\pi}}(i,j)\leq
N^{\mathrm{u}}(i,j)<\gamma_{1}(n-2)q_{\mathrm{u}}^{2},$

for all $i,j\in[n]$, $i\neq j$. As a result, at $(l+1)$-th call of the while
loop, we either have that Algorithm 2 terminates or some $i$ is added to $J$
and $\tilde{\pi}(i)=i$. This proves that $\tilde{\pi}=\pi^{*}|_{J}$ after
$l+1$ calls of the while loop.

To complete the proof, next we show that when the algorithm terminates, we
have $J=[n]$ and $\tilde{\pi}$ equals to the identity permutation. Towards
contradiction, we suppose that the algorithm ends with $|J|<n$. This suggests
that $N^{\mathrm{u}}_{\tilde{\pi}}(i,i)<\gamma_{1}(n-2)q_{\mathrm{u}}^{2}$ for
each $i\in J^{c}$, which further implies that

$\kappa_{G_{1}^{\mathrm{u}}\cap G_{2}^{\mathrm{u}}}(J,J^{c})=\sum_{i\in
J^{c}}N^{\mathrm{u}}_{\tilde{\pi}}(i,i)<\gamma_{1}(n-2)q_{\mathrm{u}}^{2}|J^{c}|.$
(99)

From the attributed Erdős–Rényi graph pair model, it is not hard to see that
$G_{1}^{\mathrm{u}}\cap
G_{2}^{\prime{\mathrm{u}}}\sim{\mathcal{G}}(n,{q_{\mathrm{u}}}s_{\mathrm{u}})$,
where
$s_{\mathrm{u}}\triangleq{q_{\mathrm{u}}}+{\rho_{\mathrm{u}}}(1-{q_{\mathrm{u}}})$.
Because condition (87) holds, from Lemma 5, we know that with probability at
least $1-O(n^{-\epsilon/8})$,

$\kappa_{G_{1}^{\mathrm{u}}\cap
G_{2}^{\mathrm{u}}}(J,J^{c})\geq\eta|J||J^{c}|{q_{\mathrm{u}}}s_{\mathrm{u}}\stackrel{{\scriptstyle(a)}}{{\geq}}\eta(1-\epsilon/16)n|J^{c}|{q_{\mathrm{u}}}s_{\mathrm{u}},$
(100)

where $\eta$ is the unique solution in $(0,1)$ to
$h(\eta)=\frac{(1+\epsilon/8)\log
n}{(1-\epsilon/16)n{q_{\mathrm{u}}}s_{\mathrm{u}}}$ and (a) follows because we
assume $|J|\geq(1-\epsilon/16)n$ at the very beginning of the algorithms. To
complete the proof, it suffices to show that
$\gamma_{1}(n-2)q_{\mathrm{u}}^{2}|J^{c}|\leq\eta(1-\epsilon/16)n|J^{c}|{q_{\mathrm{u}}}s_{\mathrm{u}}$,
i.e., we want to show that

$\gamma_{1}\leq\eta(1-\epsilon/16)\frac{s_{\mathrm{u}}}{{q_{\mathrm{u}}}}\triangleq\bar{\gamma}_{1}.$

By taking derivative, one can check that $f(x)$ is monotone increasing on
$(1,\infty)$. Thus, it suffices to show that $\bar{\gamma}_{1}>1$ and
$f(\bar{\gamma}_{1})\geq f(\gamma_{1})$. We show these by considering two
different cases.

Case 1: ${q_{\mathrm{u}}}=o({\rho_{\mathrm{u}}}):$ In view of
$\eta\geq\epsilon/16$, we have

$\displaystyle\bar{\gamma}_{1}$
$\displaystyle\geq(1-\epsilon/16)\frac{\epsilon
s_{\mathrm{u}}}{16{q_{\mathrm{u}}}}$
$\displaystyle=(1-\epsilon/16)\frac{\epsilon}{16}\left(1+\frac{{\rho_{\mathrm{u}}}(1-{q_{\mathrm{u}}})}{{q_{\mathrm{u}}}}\right)$
$\displaystyle=\omega(1),$

where the last equality follows because
${q_{\mathrm{u}}}=o({\rho_{\mathrm{u}}})$. Therefore, it follows that

$\displaystyle
f(\bar{\gamma}_{1})>\bar{\gamma}_{1}(\log\bar{\gamma}_{1}-1)\stackrel{{\scriptstyle(b)}}{{=}}\omega(\bar{\gamma}_{1})\stackrel{{\scriptstyle(c)}}{{=}}\omega\left(\frac{s_{\mathrm{u}}}{{q_{\mathrm{u}}}}\right),$

where (b) follows because $\bar{\gamma}_{1}=\omega(1)$ and (c) follows because
$\eta\geq\epsilon/16$ and $\epsilon=\Theta(1)$. Finally, the proof of Case 1
is completed by realizing $f(\bar{\gamma}_{1})\geq f(\gamma_{1})$ because

$\frac{s_{\mathrm{u}}/{q_{\mathrm{u}}}}{f(\bar{\gamma}_{1})}=\frac{s_{\mathrm{u}}/{q_{\mathrm{u}}}}{3\log
n/((n-2)q_{\mathrm{u}}^{2})}=\frac{(n-2){q_{\mathrm{u}}}s_{\mathrm{u}}}{3\log
n}=\Omega(1),$

where the last equality follows by the assumption that
$n{q_{\mathrm{u}}}s_{\mathrm{u}}\geq(1+\epsilon)\log n$.

Case 2: ${q_{\mathrm{u}}}=\Omega({\rho_{\mathrm{u}}}):$ Recall that we have
$\eta\geq 1-\sqrt{\frac{2(1+\epsilon/8)\log
n}{(1-\epsilon/16)n{q_{\mathrm{u}}}s_{\mathrm{u}}}}$. Notice that

$n{q_{\mathrm{u}}}s_{\mathrm{u}}\geq
nq_{\mathrm{u}}^{2}=\Omega(n\rho_{\mathrm{u}}^{2})=\omega(\log n),$

where the last equality follows by condition (86) in the proposition. Then it
follows that $\eta\geq 1-\epsilon/16$. Therefore, we have

$\displaystyle\bar{\gamma}_{1}$
$\displaystyle\geq(1-\epsilon/16)^{2}\frac{s_{\mathrm{u}}}{{q_{\mathrm{u}}}}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\geq}}(1-\epsilon/16)^{2}(1+\epsilon)$
$\displaystyle\geq 1+\epsilon/2,$

where (d) follows by condition (88) in the proposition. Finally, the proof is
completed by

$\displaystyle f(\bar{\gamma}_{1})\geq
f(1+\epsilon/2)\stackrel{{\scriptstyle(e)}}{{>}}\frac{3\log
n}{(n-2)q_{\mathrm{u}}^{2}}=f(\gamma_{1}),$

where (e) follows because $f(1+\epsilon/2)=\Omega(1)$, while $\frac{3\log
n}{(n-2)q_{\mathrm{u}}^{2}}=O(\frac{3\log
n}{(n-2)\rho_{\mathrm{u}}^{2}})=o(1)$ by condition (86).

###  C-B Proof of Proposition 5

To show Proposition 5, we firstly study some expansion property of random
attributed graphs. To state the result, we need to define the _attributed
Erdős–Rényi graph model_ ${\mathcal{G}}(n,p;m,q)$, which generates random
attributed graphs. In this model, we generate an attributed graph $G$ with
$n+m$ vertices, where ${\mathcal{V}^{\mathrm{u}}}(G)=[n]$ and
${\mathcal{V}^{\mathrm{a}}}(G)=\\{a_{1},\ldots,a_{m}\\}$. Between each pair
$(i,j)\in{\mathcal{V}^{\mathrm{u}}}(G)\times{\mathcal{V}^{\mathrm{u}}}(G),i\neq
j$, a user-user edge is generated i.i.d. with probability $p$, and between
each pair
$(i,a_{j})\in{\mathcal{V}^{\mathrm{u}}}(G)\times{\mathcal{V}^{\mathrm{a}}}(G)$,
a user-attribute edge is generated i.i.d. with probability $q$. We show that
attributed graphs generated from the attributed Erdős–Rényi graph model
satisfies good expansion property with high probability.

######  Lemma 6 (Expansion property of attributed Erdős–Rényi graph).

Suppose $G\sim{\mathcal{G}}(n,p;m,q)$. Assume
$np\geq\lambda_{1}(1+\epsilon)\log n$, $mq\geq\lambda_{2}(1+\epsilon)\log n$
for some constants $\epsilon,\lambda_{1},\lambda_{2}$ with
$\lambda_{1}+\lambda_{2}\geq 1$. Let $\kappa^{\mathrm{u}}_{G}(I,I^{c})$ denote
the number of user-user edges between $I\subseteq[n]$ and $I^{c}$, where
$I^{c}\triangleq[n]\setminus I$. Let
$\kappa^{\mathrm{a}}_{G}(I,{\mathcal{V}^{\mathrm{a}}}(G))$ denote the number
of user-attribute edges between $I\subseteq[n]$ and
${\mathcal{V}^{\mathrm{a}}}(G)$. Let $\eta_{1}$ denote the unique solution in
$(0,1)$ to $f(\eta_{1})=\frac{\lambda_{1}(1+\epsilon/8)\log
n}{(1-\epsilon/16)np}$, and $\eta_{2}$ denote the unique solution in $(0,1)$
to $f(\eta_{2})=\frac{\lambda_{2}(1+\epsilon/8)\log n}{mq}$. Then with
probability at least $1-O(n^{-\epsilon/8})$, for all subsets $I\subseteq[n]$
with $|I|\leq\frac{\epsilon}{16}n$, at least one of the following two events
happens:

  1. 1.

$\kappa^{\mathrm{u}}_{G}(I,I^{c})\geq\eta_{1}|I||I^{c}|p$;

  2. 2.

$\kappa^{\mathrm{a}}_{G}(I,{\mathcal{V}^{\mathrm{a}}}(G))\geq\eta_{2}|I|mq$.

Moreover, $\eta_{1}$ and $\eta_{2}$ satisfy lower bounds

$\eta_{1}\geq\max\left\\{\epsilon/16,1-\sqrt{\frac{2\lambda_{1}(1+\epsilon/8)\log
n}{(1-\epsilon/16)np}}\right\\},$ (101)
$\eta_{2}\geq\max\left\\{\epsilon/16,1-\sqrt{\frac{2\lambda_{2}(1+\epsilon/8)\log
n}{mq}}\right\\}.$ (102)

###### Proof of Lemma 6..

When $|I|=\emptyset$, both events in Lemma 6 happen. Therefore, we only
consider the non-trivial cases of $1\leq|I|\leq\epsilon/16$. For some fixed
$I$ with $1\leq|I|\leq\epsilon/16$, we observe that
$\kappa^{\mathrm{u}}_{G}(I,I^{c})\sim\mathrm{Binom}(|I||I^{c}|,p)$. Notice
that

$f(\eta_{1})=\frac{\lambda_{1}(1+\epsilon/8)\log
n}{(1-\epsilon/16)np}\leq\frac{1+\epsilon/8}{(1-\epsilon/16)(1+\epsilon)}<1.$

Therefore, there indeed exists a unique solution $\eta_{1}\in(0,1)$. By the
multiplicative Chernoff bound, we have

$\displaystyle{\mathsf{P}}(\kappa^{\mathrm{u}}_{G}(I,I^{c})\leq\eta_{1}|I||I^{c}|p)$
$\displaystyle\leq\exp(-f(\eta_{1})|I||I^{c}|p)$
$\displaystyle=\exp\left(-\frac{\lambda_{1}(1+\epsilon/8)\log
n}{(1-\epsilon/16)np}|I||I^{c}|p\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\left(-\frac{\lambda_{1}(1+\epsilon/8)\log
n}{(1-\epsilon/16)np}|I|(1-\epsilon/16)np\right)$
$\displaystyle=\exp\left(-\lambda_{1}(1+\epsilon/8)|I|\log n\right),$

where (a) follows because $|I^{c}|\geq(1-\epsilon/16)n$. Similarly, we observe
that
$\kappa^{\mathrm{a}}_{G}(I,{\mathcal{V}^{\mathrm{a}}}(G))\sim\mathrm{Binom}(|I|m,q)$.
Note that

$f(\eta_{2})=\frac{\lambda_{2}(1+\epsilon/8)\log
n}{mq}\leq\frac{1+\epsilon/8}{1+\epsilon}<1.$

Thus, there indeed exists a unique solution $\eta_{2}\in(0,1)$. By the
multiplicative Chernoff bound, we have

$\displaystyle{\mathsf{P}}(\kappa^{\mathrm{a}}_{G}(I,{\mathcal{V}^{\mathrm{a}}}(G))\leq\eta_{2}|I|{\mathcal{V}^{\mathrm{a}}}(G)q)$
$\displaystyle\leq\exp(-f(\eta_{2})|I|mq)$
$\displaystyle=\exp\left(-\frac{\lambda_{2}(1+\epsilon/8)\log
n}{mq}|I|mq\right)$ $\displaystyle=\exp(-\lambda_{2}(1+\epsilon/8)|I|\log n).$

Notice that $\kappa^{\mathrm{u}}_{G}(I,I^{c})$ and
$\kappa^{\mathrm{a}}_{G}(I,{\mathcal{V}^{\mathrm{a}}}(G))$ are two independent
random variables because $\kappa^{\mathrm{u}}_{G}(I,I^{c})$ only counts user-
user edges, while $\kappa^{\mathrm{a}}_{G}(I,{\mathcal{V}^{\mathrm{a}}}(G))$
only counts user-attribute edges. Hence, we have

$\displaystyle{\mathsf{P}}(\kappa^{\mathrm{u}}_{G}(I,I^{c})\leq\eta_{1}|I||I^{c}|p\text{
and
}\kappa^{\mathrm{a}}_{G}(I,{\mathcal{V}^{\mathrm{a}}}(G))\leq\eta_{2}|I|{\mathcal{V}^{\mathrm{a}}}(G)q)$
$\displaystyle\leq\exp(-(\lambda_{1}+\lambda_{2})(1+\epsilon/8)|I|\log n)$
$\displaystyle\leq n^{-(1+\epsilon/8)|I|},$

where the last inequality follows because $\lambda_{1}+\lambda_{2}\geq 1$.
Applying a union bound over all $\binom{n}{k}$ choices of $|I|=l$ yields

$\displaystyle{\mathsf{P}}(\exists
I\subseteq[n]:|I|=l,\kappa^{\mathrm{u}}_{G}(I,I^{c})\leq\eta_{1}|I||I^{c}|p\text{
and
}\kappa^{\mathrm{a}}_{G}(I,{\mathcal{V}^{\mathrm{a}}}(G))\leq\eta_{2}|I|{\mathcal{V}^{\mathrm{a}}}(G)q)$
$\displaystyle\leq\binom{n}{l}n^{-(1+\epsilon/8)l}\leq n^{-\epsilon l/8}.$

Finally, applying a union bounder over $1\leq l\leq\lfloor\epsilon n/16\rceil$
yields

$\displaystyle{\mathsf{P}}(\exists I\subseteq[n]:1\leq|I|\leq\lfloor\epsilon
n/16\rceil,\kappa^{\mathrm{u}}_{G}(I,I^{c})\leq\eta_{1}|I||I^{c}|p\text{ and
}\kappa^{\mathrm{a}}_{G}(I,{\mathcal{V}^{\mathrm{a}}}(G))\leq\eta_{2}|I|{\mathcal{V}^{\mathrm{a}}}(G)q)$
$\displaystyle\leq\sum_{l=1}^{\lfloor\epsilon n/16\rceil}n^{-\epsilon
l/8}=O(n^{-\epsilon/8}).$

To complete the proof, we still need show the two lower bounds for $\eta_{1}$
and $\eta_{2}$. For $\eta_{1}$, we notice that

$f(\eta_{1})=\frac{\lambda_{1}(1+\epsilon/8)\log
n}{(1-\epsilon/16)np}\leq\frac{1+\epsilon/8}{(1-\epsilon/16)(1+\epsilon)}\leq
f(\epsilon/16).$ (103)

Because $f(x)$ is monotone decreasing on $x\in(0,1)$, we know that
$\eta_{1}\geq\epsilon/16$. Moreover, because $f(x)\geq(1-x)^{2}/2$ for any
$x\in(0,1)$, it follows that

$\frac{\lambda_{1}(1+\epsilon/8)\log
n}{(1-\epsilon/16)np}\geq\frac{(1-\eta_{1})^{2}}{2}.$

This proves that

$\eta_{1}\geq 1-\sqrt{\frac{2\lambda_{1}(1+\epsilon/8)\log
n}{(1-\epsilon/16)np}}.$

For $\eta_{2}$, similarly, we have

$f(\eta_{2})=\frac{\lambda_{2}(1+\epsilon/8)\log
n}{mq}\leq\frac{1+\epsilon/8}{1+\epsilon}\leq f(\epsilon/16),$ (104)

which implies that $\eta_{2}\geq\epsilon/16$. Finally, we have

$\eta_{2}\geq 1-\sqrt{\frac{2\lambda_{2}(1+\epsilon/8)\log n}{mq}},$

because

$\frac{\lambda_{2}(1+\epsilon/8)\log n}{mq}\geq\frac{(1-\eta_{2})^{2}}{2}.$

∎

Now, we can proceed to prove Proposition 5. We assume without generality that
the true permutation $\pi^{*}$ is the identity permutation. For a pair of user
vertices $i\in{\mathcal{V}^{\mathrm{u}}_{1}}$ and
$j\in{\mathcal{V}^{\mathrm{u}}_{2}}$, let $N^{\mathrm{u}}(i,j)$ denote the
number of user vertices $u\in[n]$ such that $u$ is connected to $i$ in $G_{1}$
and $u$ is connected to $j$ in $G_{2}^{\prime}$, and let $N^{\mathrm{a}}(i,j)$
denote the number of attribute vertices $a\in\\{a_{1},\ldots,a_{m}\\}$ such
that $a$ is connected to $i$ in $G_{1}$ and $a$ is connected to $j$ in
$G_{2}^{\prime}$. By the definition of Erdős–Rényi graph pair model, we have
$N^{\mathrm{u}}(i,j)\sim\mathrm{Binom}(n-2,q_{\mathrm{u}}^{2})$ and
$N^{\mathrm{a}}(i,j)\sim\mathrm{Binom}(m,q_{\mathrm{a}}^{2})$ for any $i\neq
j$. By the multiplicative Chernoff bound, we have

${\mathsf{P}}(N^{\mathrm{u}}(i,j)\geq\gamma_{2}(n-2)q_{\mathrm{u}}^{2})\leq\exp(-(n-2)q_{\mathrm{u}}^{2}f(\gamma_{2}))=n^{-3},$

and

${\mathsf{P}}(N^{\mathrm{a}}(i,j)\geq\gamma_{3}mq_{\mathrm{a}}^{2})\leq\exp(-mq_{\mathrm{a}}^{2}f(\gamma_{3}))=n^{-3}.$

By the union bound, for a fixed pair $(i,j)$,

${\mathsf{P}}(N^{\mathrm{u}}(i,j)\geq\gamma_{2}(n-2)q_{\mathrm{u}}^{2}\text{
or }N^{\mathrm{a}}(i,j)\geq\gamma_{3}mq_{\mathrm{a}}^{2})\leq 2n^{-3}.$

Moreover, by a union bound over all $\binom{n}{2}$ pairs, we have

${\mathsf{P}}(\exists i,j\in[n],i\neq
j:N^{\mathrm{u}}(i,j)\geq\gamma_{2}(n-2)q_{\mathrm{u}}^{2}\text{ or
}N^{\mathrm{a}}(i,j)\geq\gamma_{3}mq_{\mathrm{a}}^{2})\leq\binom{n}{2}2n^{-3}\leq
2n^{-1}.$ (105)

Now, we assume that $\\{\nexists i,j\in[n],i\neq
j:N^{\mathrm{u}}(i,j)\geq\gamma_{2}(n-2)q_{\mathrm{u}}^{2}\text{ or
}N^{\mathrm{a}}(i,j)\geq\gamma_{3}mq_{\mathrm{a}}^{2}\\}$. By a similar
induction as in the proof of Proposition 4, we have that
$\tilde{\pi}=\pi^{*}|_{J}$ throughout out the process of the algorithm.
Therefore, it suffices to show that when the algorithm terminates, we have
$J=[n]$. Towards contradiction, we suppose that the algorithm ends with
$|J|<n$. This suggests that for each $i\in J^{c}$,
$N^{\mathrm{u}}_{\tilde{\pi}}(i,i)<\gamma_{2}(n-2)q_{\mathrm{u}}^{2}$ and
$N^{\mathrm{a}}(i,i)<\gamma_{3}mq_{\mathrm{a}}^{2}$. These further imply that

$\kappa^{\mathrm{u}}_{G_{1}\cap G_{2}}(J^{c},J)=\sum_{i\in
J^{c}}N^{\mathrm{u}}_{\tilde{\pi}}(i,i)<\gamma_{2}(n-2)q_{\mathrm{u}}^{2}|J^{c}|,$
(106)

and

$\kappa^{\mathrm{a}}_{G_{1}\cap
G_{2}}(J^{c},{\mathcal{V}^{\mathrm{a}}}(G_{1}))=\sum_{i\in
J^{c}}N^{\mathrm{a}}(i,i)<\gamma_{3}mq_{\mathrm{a}}^{2}|J^{c}|.$ (107)

From the attributed Erdős–Rényi graph pair model, it is not hard to see that
$G_{1}\cap
G_{2}^{\prime}\sim{\mathcal{G}}(n,{q_{\mathrm{u}}}s_{\mathrm{u}};m,{q_{\mathrm{a}}}s_{\mathrm{a}})$,
where
$s_{\mathrm{u}}\triangleq{q_{\mathrm{u}}}+{\rho_{\mathrm{u}}}(1-{q_{\mathrm{u}}})$
and
$s_{\mathrm{a}}\triangleq{q_{\mathrm{a}}}+{\rho_{\mathrm{a}}}(1-{q_{\mathrm{a}}})$.
By conditions (91), (92) and (93), we know that there exists constants
$\lambda_{1},\lambda_{2},\epsilon$ with $\lambda_{1}+\lambda_{2}\geq 1$ such
that $n{q_{\mathrm{u}}}s_{\mathrm{u}}\geq\lambda_{1}(1+\epsilon)\log n$ and
$m{q_{\mathrm{a}}}s_{\mathrm{a}}\geq\lambda_{2}(1+\epsilon)\log n$. Let
$\eta_{1}$ denote the unique solution in $(0,1)$ to
$f(\eta_{1})=\frac{\lambda_{1}(1+\epsilon/8)\log
n}{(1-\epsilon/16)n{q_{\mathrm{u}}}s_{\mathrm{u}}}$, and $\eta_{2}$ denote the
unique solution in $(0,1)$ to $f(\eta_{2})=\frac{\lambda_{2}(1+\epsilon/8)\log
n}{m{q_{\mathrm{a}}}s_{\mathrm{a}}}$. By Lemma 6, with probability at least
$1-O(n^{-\epsilon/8})$, we have at least one of

$\kappa^{\mathrm{u}}_{G_{1}\cap
G_{2}}(J^{c},J)\geq\eta_{1}|J||J^{c}|{q_{\mathrm{u}}}s_{\mathrm{u}}\geq\eta_{1}(1-\epsilon/16)n|J^{c}|{q_{\mathrm{u}}}s_{\mathrm{u}},$

or

$\kappa^{\mathrm{a}}_{G_{1}\cap
G_{2}}(J^{c},{\mathcal{V}^{\mathrm{a}}}(G_{1}))\geq\eta_{2}|J^{c}|m{q_{\mathrm{a}}}s_{\mathrm{a}}.$

To complete the proof, it suffices to show that

$\bar{\gamma}_{2}\triangleq\eta_{1}(1-\epsilon/16)\frac{s_{\mathrm{u}}}{{q_{\mathrm{u}}}}\geq\gamma_{2},$
(108)

and

$\bar{\gamma}_{3}\triangleq\eta_{2}\frac{s_{\mathrm{a}}}{{q_{\mathrm{a}}}}\geq\gamma_{3}.$
(109)

We firstly show (108) by considering two different cases.

Case 1: ${q_{\mathrm{u}}}=o({\rho_{\mathrm{u}}}):$ Because
$\eta_{1}\geq\epsilon/16$, we have

$\displaystyle\bar{\gamma}_{2}$
$\displaystyle\geq(1-\epsilon/16)\frac{\epsilon
s_{\mathrm{u}}}{16{q_{\mathrm{u}}}}$
$\displaystyle=\frac{\epsilon}{16}(1-\epsilon/16)\left(1+\frac{{\rho_{\mathrm{u}}}(1-{q_{\mathrm{u}}})}{{q_{\mathrm{u}}}}\right)$
$\displaystyle=\omega(1),$

where the last equality follows because
${q_{\mathrm{u}}}=o({\rho_{\mathrm{u}}})$. Therefore,

$\displaystyle f(\bar{\gamma}_{2})$
$\displaystyle>\bar{\gamma}_{2}(\log\bar{\gamma}_{2}-1)$
$\displaystyle=\omega(\bar{\gamma}_{2})$
$\displaystyle=\omega(s_{\mathrm{u}}/{q_{\mathrm{u}}}),$ (110)

where the penultimate equality follows because $\bar{\gamma}_{2}=\omega(1)$
and the last equality follows because $\epsilon=\Theta(1)$. Notice that (110)
further implies that $f(\bar{\gamma}_{2})>\frac{3\log
n}{(n-2)q_{\mathrm{u}}^{2}}=f(\gamma_{2})$ because
$\frac{s_{\mathrm{u}}(n-2){q_{\mathrm{u}}}}{3\log n}=\Omega(1)$ by condition
(92). Therefore, we have $\bar{\gamma}_{2}>\gamma_{2}$.

Case 2: ${q_{\mathrm{u}}}=\Omega({\rho_{\mathrm{u}}}):$ By Lemma 6, we have
$\eta_{1}\geq 1-\sqrt{\frac{2(1+\epsilon/8)\log
n\lambda_{1}}{(1-\epsilon/16)n{q_{\mathrm{u}}}s_{\mathrm{u}}}}$. Because
$n{q_{\mathrm{u}}}s_{\mathrm{u}}\geq
nq_{\mathrm{u}}^{2}=\Omega(n\rho_{\mathrm{u}}^{2})=\omega(\log n)$ by (89), we
have $\eta_{1}\geq 1-\epsilon/16$. Hence, we have

$\displaystyle\bar{\gamma}_{2}$
$\displaystyle\geq(1-\epsilon/16)^{2}\frac{s_{\mathrm{u}}}{{q_{\mathrm{u}}}}$
$\displaystyle=(1-\epsilon/16)^{2}\left(1+\frac{{\rho_{\mathrm{u}}}(1-{q_{\mathrm{u}}})}{{q_{\mathrm{u}}}}\right)$
$\displaystyle\geq(1-\epsilon/16)^{2}(1+\epsilon)$ $\displaystyle\geq
1+\frac{\epsilon}{2},$

where the penultimate inequality follows by assumption (94). Finally, we have

$f(\bar{\gamma}_{2})\geq f(1+\epsilon)\geq\frac{3\log
n}{(n-2)q_{\mathrm{u}}^{2}},$

where the last inequality follows because $f(1+\epsilon)=\Theta(1)$ and
$(n-2)q_{\mathrm{u}}^{2}=\Omega(n\rho_{\mathrm{u}}^{2})=\omega(\log n)$ by
assumption (89).

To show (109), we again consider two cases.

Case 1: ${q_{\mathrm{a}}}=o({\rho_{\mathrm{a}}}):$ By Lemma 6, we have
$\eta_{2}\geq\epsilon/16$. Therefore, we have

$\bar{\gamma}_{3}\geq\frac{\epsilon}{16}\left(1+\frac{{\rho_{\mathrm{a}}}(1-{q_{\mathrm{a}}})}{{q_{\mathrm{a}}}}\right)=\omega(1),$

where the last equality follows because
${q_{\mathrm{a}}}=o({\rho_{\mathrm{a}}})$. It follows that

$f(\bar{\gamma}_{3})>\bar{\gamma}_{3}(\log\bar{\gamma}_{3}-1)=\omega(\bar{\gamma}_{3})=\omega\left(\frac{\epsilon
s_{\mathrm{a}}}{16{q_{\mathrm{a}}}}\right).$

From here, we conclude that $f(\bar{\gamma}_{3})>\frac{3\log
n}{mq_{\mathrm{a}}^{2}}=f(\gamma_{3})$ because
$m{q_{\mathrm{a}}}s_{\mathrm{a}}=\Omega(\log n)$. This completes the proof for
$\bar{\gamma}_{3}>\gamma_{3}$.

Case 2: ${q_{\mathrm{a}}}=\Omega({\rho_{\mathrm{a}}}):$ By Lemma 6, we have
$\eta_{2}\geq 1-\sqrt{\frac{2\lambda_{2}(1+\epsilon/8)\log
n}{m{q_{\mathrm{a}}}s_{\mathrm{a}}}}$. It follows that $\eta_{2}\geq
1-\epsilon/16$ because $m{q_{\mathrm{a}}}s_{\mathrm{a}}\geq
mq_{\mathrm{a}}^{2}=\Omega(m\rho_{\mathrm{a}}^{2})=\omega(\log n)$. Then by
assumption (95), we have

$\bar{\gamma}_{3}\geq(1-\epsilon/16)\frac{s_{\mathrm{a}}}{{q_{\mathrm{a}}}}=(1-\epsilon/16)\left(1+\frac{{\rho_{\mathrm{a}}}(1-{q_{\mathrm{a}}})}{{q_{\mathrm{a}}}}\right)\geq(1-\epsilon/16)(1+\epsilon)\geq
1+\epsilon/2.$

Finally, we have

$f(\bar{\gamma}_{3})\geq f(1+\epsilon/2)>\frac{3\log
n}{mq_{\mathrm{a}}^{2}}=f(\gamma_{3}),$

where the penultimate inequality follows because $f(1+\epsilon/2)=\Omega(1)$
and $mq_{\mathrm{a}}^{2}=\Omega(m\rho_{\mathrm{a}}^{2})=\omega(\log n)$. This
shows that $\bar{\gamma}_{3}>\gamma_{3}$ and completes the proof.

##  Appendix D Comparison to Existing works for Seeded Graph Alignment

In this section, we compare the feasible region of the proposed algorithms to
the best-known feasible region under the context of seeded graph alignment. In
the seeded Erdős–Rényi graph pair model $\mathcal{G}(N,\alpha,p,s)$ by Mossel
and Xu, (2020), the graph generation process is described as follows: First, a
base graph $G$ is sampled from Erdős–Rényi model $\mathcal{G}(N,p)$. Next, two
correlated graphs $G_{1}$ and $G_{2}$ are produced by independently retaining
each edge from $G$ with a probability $s$. The graph $G_{2}^{\prime}$ is then
generated by applying a random permutation $\Pi^{*}$ to $G_{2}$. Let
$\mathcal{V}_{1}$ and $\mathcal{V}_{2}$ denote the sets of vertices in $G_{1}$
and $G_{2}^{\prime}$ respectively. A subset
$\mathcal{V}_{s}\subset\mathcal{V}_{1}$ of size $\lfloor N\alpha\rfloor$ is
then selected uniformly at random, and the vertex pairs
$\mathcal{I}_{0}=\\{(v,\Pi^{*}(v)):v\in\mathcal{V}_{s}\\}$ are identified as
the seed set. The graph pair $(G_{1},G_{2}^{\prime})$ and the seed set
$\mathcal{I}_{0}$ are provided, and the goal is to recover the vertex
correspondence for all the remaining vertices.

In the attributed Erdős–Rényi graph pair model
$\mathcal{G}(n,{q_{\mathrm{u}}},{\rho_{\mathrm{u}}};m,{q_{\mathrm{a}}},{\rho_{\mathrm{a}}})$,
when we set ${q_{\mathrm{u}}}={q_{\mathrm{a}}}$ and
${\rho_{\mathrm{u}}}={\rho_{\mathrm{a}}}$, the $m$ attributes can be viewed as
seeds, and graph pair can be viewed as generated from the seeded Erdős–Rényi
graph pair model
$\mathcal{G}(n+m,\frac{m}{n+m},\frac{{q_{\mathrm{u}}}}{{q_{\mathrm{u}}}+{\rho_{\mathrm{u}}}(1-{q_{\mathrm{u}}})},{q_{\mathrm{u}}}+{\rho_{\mathrm{u}}}(1-{q_{\mathrm{u}}}))$
except that the edges between the seeds are removed. Therefore, the feasible
region of the proposed algorithms for attributed graph alignment directly
implies feasible region for seeded graph alignment. In the following, we
compare the feasible region of the proposed algorithms to that of the
algorithms by Mossel and Xu, (2020), and demonstrate that the implied feasible
region covers certain parameter regimes that are unknown from the literature.
For simplicity, we denote $N\triangleq n+m$, $\alpha\triangleq\frac{m}{m+n}$,
$p\triangleq\frac{{q_{\mathrm{u}}}}{{q_{\mathrm{u}}}+{\rho_{\mathrm{u}}}(1-{q_{\mathrm{u}}})}$
and $s\triangleq{q_{\mathrm{u}}}+{\rho_{\mathrm{u}}}(1-{q_{\mathrm{u}}})$.
Firstly, the feasible region by Mossel and Xu, (2020) requires a constant
correlation $s=\Theta(1)$, while our feasible region includes both cases of
$s=o(1)$ and $s=\Theta(1)$. In the rest of the comparison, we consider
constant correlation regime $s=\Theta(1)$. In this regime, we demonstrate that
the seed fraction $\alpha$ required by the proposed algorithms is strictly
smaller in the following two cases:

Case 1: $np=n^{c}$ for some constant $1/2<c<1$. In this case, one can check
that conditions (1), (3) and (4) in Theorem 1, and conditions (6) and (7) in
Theorem 2 are satisfied without any further assumptions. To satisfy condition
(2), we need to set $m=\omega(n^{\epsilon})$ for an arbitrarily small
$\epsilon$. This is equivalent as $\alpha=\omega(n^{\epsilon-1})$. In
contrast, Theorem 4 in Mossel and Xu, (2020) requires at least
$\alpha=\Omega(\frac{\log n}{n^{c}})$.

Case 2: $np=n^{c}$ for some constant $1/3<c<1/2$. In this case, one can check
that conditions (1) and (3) in Theorem 1, and conditions (6) and (7) in
Theorem 2 are satisfied without any further assumptions. For conditions (2)
and (4), we need to set $m=\omega(n^{1-2c})$. This is equivalent as
$\alpha=\omega(n^{-2c})$. In contrast, Theorem 4 in Mossel and Xu, (2020)
requires at least $\alpha=\Omega(\frac{\log n}{n^{2c}})$.

To provide a fair comparison, we point to that when $np=n^{c}$ for some
$c=1/2$ or $c\leq 1/3$ or $c=o(1)$, the algorithms by Mossel and Xu, (2020)
requires strictly less seeds to achieve exact recovery.

##  Appendix E Tightness of Propositions 2 and 3

The conditions presented in Propositions 2 and 3 are not only sufficient, but
also necessary for the variance lower bounds under the assumption that
$k=\Theta(1)$. By the definition of $\Phi_{ij}$, we can expand its variance
expression as

$\displaystyle{\mathrm{Var}}(\Phi_{ij})$
$\displaystyle={\mathrm{Var}}\left(\sum_{{\mathcal{A}}\subseteq{\mathcal{V}^{\mathrm{a}}}:|{\mathcal{A}}|=k}W_{i,{\mathcal{A}}}(G_{1})W_{j,{\mathcal{A}}}(G_{2}^{\prime})\right)$
$\displaystyle=\sum_{{\mathcal{A}},{\mathcal{B}}\subseteq{\mathcal{V}^{\mathrm{a}}}:|{\mathcal{A}}|=|{\mathcal{B}}|=k}\sum_{S_{1}\in{\mathcal{G}}_{i,{\mathcal{A}}}}\sum_{S_{2}\in{\mathcal{G}}_{i,{\mathcal{A}}}}\sum_{T_{1}\in{\mathcal{G}}_{i,{\mathcal{B}}}}\sum_{T_{2}\in{\mathcal{G}}_{i,{\mathcal{B}}}}{\mathrm{Cov}}(\omega_{1}(S_{1})\omega_{2}(S_{2}),\omega_{1}(T_{1})\omega_{2}(T_{2})).$

By considering specific overlapping patterns of the four subgraphs
$S_{1},S_{2},T_{1},T_{2}$ satisfying the conditions in the summation, we can
obtain lower bounds on the variance. For a true pair of matched users, we have

$\frac{{\mathrm{Var}}(\Phi_{ii})}{{\mathsf{E}}[\Phi_{ii}]^{2}}=\Omega\left(\max\left(\frac{1}{n{q_{\mathrm{u}}}{\rho_{\mathrm{u}}}},\frac{1}{n\rho_{\mathrm{u}}^{2}}\right)+\frac{1}{m\rho_{\mathrm{u}}^{2}\rho_{\mathrm{a}}^{2}}+\max\left(\frac{1}{n{q_{\mathrm{u}}}{\rho_{\mathrm{u}}}m{q_{\mathrm{a}}}{\rho_{\mathrm{a}}}},\frac{1}{n\rho_{\mathrm{u}}^{2}m{q_{\mathrm{a}}}{\rho_{\mathrm{a}}}}\right)\right).$
(111)

$S_{1},S_{2}$
---
$S_{1},S_{2}$
---
$T_{1},T_{2}$
---
$T_{1},T_{2}$
---
$S_{1},S_{2},T_{1},T_{2}$
---
$i$
---
(a)

$S_{1},S_{2}$
---
$S_{1},S_{2}$
---
$T_{1},T_{2}$
---
$T_{1},T_{2}$
---
$i$
---
$S_{1},S_{2},T_{1},T_{2}$
---
$S_{1},T_{1}$
---
$S_{2},T_{2}$
---
(b)

$S_{1},S_{2}$
---
$S_{1},S_{2}$
---
$T_{1},T_{2}$
---
$T_{1},T_{2}$
---
$S_{1},S_{2},T_{1},T_{2}$
---
$i$
---
$S_{1},S_{2},T_{1},T_{2}$
---
(c)

Figure 7: Three overlapping patterns of $(S_{1},S_{2},T_{1},T_{2})$ for a
correct pair of users $(i,i)$: In these figures we assume $k=3$. The black
nodes represent users and the red nodes represent attributes. The solid lines
represent user-user edges and the dotted lines represent user-attribute edges.
The subgraph names in the figures indicate which subgraphs do the vertices
belong to.

To see the first term, consider the overlapping pattern shown in Figure 7(a).
In this case, we have $S_{1}=S_{2}$, $T_{1}=T_{2}$ and $S_{1},T_{1}$ overlap
at only $1$ user-user edge. We can show that

${\mathrm{Cov}}(\omega_{1}(S_{1})\omega_{2}(S_{2}),\omega_{1}(T_{1})\omega_{2}(T_{2}))=\Omega(\sigma_{\mathrm{u}}^{4k}\sigma_{\mathrm{a}}^{4k}\rho_{\mathrm{u}}^{2k-2}\rho_{\mathrm{a}}^{2k}\max({\rho_{\mathrm{u}}}/{q_{\mathrm{u}}},1)),$

and there are in total $\Omega(n^{2k-1}m^{2k})$ copies of
$(S_{1},S_{2},T_{1},T_{2})$ satisfying this pattern. Together with the first
moment expression (15), we have
$\frac{{\mathrm{Var}}(\Phi_{ii})}{{\mathsf{E}}[\Phi_{ii}]^{2}}=\Omega\left(\max\left(\frac{1}{n{q_{\mathrm{u}}}{\rho_{\mathrm{u}}}},\frac{1}{n\rho_{\mathrm{u}}^{2}}\right)\right).$

For the second term in the lower bound, we consider the overlapping pattern
shown in Figure 7(b). In this case, we can show that

${\mathrm{Cov}}(\omega_{1}(S_{1})\omega_{2}(S_{2}),\omega_{1}(T_{1})\omega_{2}(T_{2}))=\Omega(\sigma_{\mathrm{u}}^{4k}\sigma_{\mathrm{a}}^{4k}\rho_{\mathrm{u}}^{2k-2}\rho_{\mathrm{a}}^{2k-2}),$

and $\Omega(n^{2k}m^{2k-1})$ copies of $(S_{1},S_{2},T_{1},T_{2})$ follow this
pattern. This would lead to the lower bound
$\frac{{\mathrm{Var}}(\Phi_{ii})}{{\mathsf{E}}[\Phi_{ii}]^{2}}=\Omega\left(\frac{1}{m\rho_{\mathrm{u}}^{2}\rho_{\mathrm{a}}^{2}}\right).$

The third term in (111) comes from the overlapping pattern shown in Figure
7(c). In this case, we can show that

${\mathrm{Cov}}(\omega_{1}(S_{1})\omega_{2}(S_{2}),\omega_{1}(T_{1})\omega_{2}(T_{2}))=\Omega\left(\sigma_{\mathrm{u}}^{4k}\sigma_{\mathrm{a}}^{4k}\rho_{\mathrm{u}}^{2k-2}\rho_{\mathrm{a}}^{2k-2}\frac{{\rho_{\mathrm{a}}}}{{q_{\mathrm{a}}}}\max({\rho_{\mathrm{u}}}/{q_{\mathrm{u}}},1)\right),$

and there are $\Omega(n^{2k-1}m^{2k-1})$ copies of $(S_{1},S_{2},T_{1},T_{2})$
following this pattern. With the first moment expression (15), we can get the
lower bound
$\frac{{\mathrm{Var}}(\Phi_{ii})}{{\mathsf{E}}[\Phi_{ii}]^{2}}=\Omega\left(\max\left(\frac{1}{n{q_{\mathrm{u}}}{\rho_{\mathrm{u}}}m{q_{\mathrm{a}}}{\rho_{\mathrm{a}}}},\frac{1}{n\rho_{\mathrm{u}}^{2}m{q_{\mathrm{a}}}{\rho_{\mathrm{a}}}}\right)\right).$

$S_{1},T_{1}$
---
$S_{2},T_{2}$
---
$i$
---
$j$
---
$S_{1},S_{2},T_{1},T_{2}$
---
(a)

$S_{1},S_{2}$
---
$S_{1},S_{2}$
---
$i$
---
$j$
---
$S_{1},S_{2},T_{1},T_{2}$
---
(b)

$i$
---
$j$
---
$S_{1},S_{2},T_{1},T_{2}$
---
$S_{1},S_{2},T_{1},T_{2}$
---
(c)

Figure 8: Three overlapping patterns of $(S_{1},S_{2},T_{1},T_{2})$ for a
wrong pair of users $(i,j)$: In these figures we assume $k=3$. The black nodes
represent users and the red nodes represent attributes. The solid lines
represent user-user edges and the dotted lines represent user-attribute edges.
The subgraph names in the figures indicate which subgraphs do the vertices
belong to.

For a wrong pair of matching $(i,j)$, we can similarly show that

$\frac{{\mathrm{Var}}(\Phi_{ij})}{{\mathsf{E}}[\Phi_{ii}]^{2}}=\Omega\left(\frac{1}{(m\rho_{\mathrm{u}}^{2}\rho_{\mathrm{a}}^{2})^{k}}+\frac{1}{(n\rho_{\mathrm{u}}^{2})^{k}}+\frac{1}{(n\rho_{\mathrm{u}}^{2}m{q_{\mathrm{a}}}{\rho_{\mathrm{a}}})^{k}}\right),$
(112)

where the three terms in the lower bound come from the three overlapping
patterns shown in Figure 8 respectively. Note the condition
$n^{2}{q_{\mathrm{u}}}=\Omega(1)$ in Propositions 3 is not shown to be
necessary by (112). However, $n^{2}{q_{\mathrm{u}}}=\Omega(1)$ is a mild
condition ensuring the existence of at least one user-user edge in graphs
$G_{1}$ and $G_{2}^{\prime}$. Moreover, it is implied by condition
$n{q_{\mathrm{u}}}{\rho_{\mathrm{u}}}=\omega(1)$ in Proposition 2, so it does
not affect the overall feasible region of the algorithm.