# De-biasing Distantly Supervised Named Entity Recognition
via Causal Intervention

Wenkai Zhang1,3, Hongyu Lin1,, Xianpei Han1,2,11footnotemark: 1, Le Sun 1,2
1Chinese Information Processing Laboratory 2State Key Laboratory of Computer
Science
Institute of Software, Chinese Academy of Sciences, Beijing, China
3 University of Chinese Academy of Sciences, Beijing, China
<EMAIL_ADDRESS>Corresponding authors

###### Abstract

Distant supervision tackles the data bottleneck in NER by automatically
generating training instances via dictionary matching. Unfortunately, the
learning of DS-NER is severely dictionary-biased, which suffers from spurious
correlations and therefore undermines the effectiveness and the robustness of
the learned models. In this paper, we fundamentally explain the dictionary
bias via a Structural Causal Model (SCM), categorize the bias into intra-
dictionary and inter-dictionary biases, and identify their causes. Based on
the SCM, we learn de-biased DS-NER via causal interventions. For intra-
dictionary bias, we conduct backdoor adjustment to remove the spurious
correlations introduced by the dictionary confounder. For inter-dictionary
bias, we propose a causal invariance regularizer which will make DS-NER models
more robust to the perturbation of dictionaries. Experiments on four datasets
and three DS-NER models show that our method can significantly improve the
performance of DS-NER.

##  1 Introduction

Named entity recognition (NER) aims to identify text spans pertaining to
specific semantic types, which is a fundamental task of information
extraction, and enables various downstream applications such as Relation
Extraction (Lin et al., 2016) and Question Answering (Bordes et al., 2015).
The past several years have witnessed the remarkable success of supervised NER
methods using neural networks (Lample et al., 2016; Ma and Hovy, 2016; Lin et
al., 2020), which can automatically extract effective features from data and
conduct NER in an end-to-end manner. Unfortunately, supervised methods rely on
high-quality labeled data, which is very labor-intensive, and thus severely
restricts the application of current NER models. To resolve the data
bottleneck, a promising approach is distant supervision based NER (DS-NER).
DS-NER automatically generates training data by matching entities in easily-
obtained dictionaries with plain texts. Then this distantly-labeled data is
used to train NER models, commonly be accompanied by a denoising step. DS-NER
significantly reduces the annotation cost for building an effective NER model,
and therefore has attracted great attention in recent years (Yang et al.,
2018; Shang et al., 2018; Peng et al., 2019; Cao et al., 2019; Liang et al.,
2020; Zhang et al., 2021).

Figure 1: Dictionary bias in DS-NER happens both at intra-dictionary and
inter-dictionary aspects: (a) Averaged likehoods of mentions in/not in the
dictionary significantly diverge. (b) Mention likehoods of the models using
different dictionaries significantly diverge. Figure 2: The proposed
structural causal model for DS-NER. It can be roughly divided into two parts:
distant supervision (DS) and NER. From the SCM, we identify that the intra-
dictionary bias stems from the spurious correlations caused by backdoor paths,
while the inter-dictionary bias stems from the over-fit on the dictionary
characteristics. Detailed explanations can be found in Section 2.

However, the learning of DS-NER is _dictionary-biased_ , which severely harms
the generalization and the robustness of the learned DS-NER models.
Specifically, entity dictionaries are often incomplete (missing entities),
noisy (containing wrong entities), and ambiguous (a name can be of different
entity types, such as _Washington_). And DS will generate positively-labeled
instances from the in-dictionary names but ignore all other names. Such a
biased dataset will inevitably mislead the learned models to overfit in-
dictionary names and underfit out-of-dictionary names. We refer to this as
_intra-dictionary bias_. To illustrate this bias, Figure 1 (a) shows the
predicting likelihood of a representative DS-NER model (RoBERTa + Classifier
(Liang et al., 2020)). We can see that there is a remarkable likelihood gap
between in-dictionary mentions and out-of-dictionary mentions: the average
likelihoods of out-of-dictionary mentions are $<0.2$, which means that a great
majority of them cannot be recalled. Furthermore, such a skewed distribution
makes DS-NER models very sensitive to slight perturbations. We refer to this
as _inter-dictionary bias_ , i.e., different dictionaries can result in very
different model behaviors. In the example shown in Figure 1 (b), we train the
same DS-NER model by respectively using 4 dictionaries sampled from the same
original dictionary, where each of them covers 90% of entities in the original
one. We can see that the predicting likelihood diverges significantly even
these 4 dictionaries share the majority part. Consequently, the dictionary-
biased learning will undermine both the effectiveness and robustness of DS-NER
models.

In this paper, we propose a causal framework to fundamentally explain and
resolve the dictionary bias problem in DS-NER. We first formulate the
procedure of DS-NER from the causal view with a Structural Causal Model (SCM)
Pearl et al. (2000), which is shown in the left part of Figure 2. From the
SCM, we identified that the intra-dictionary bias stemming from the dictionary
which serves as a confounder during the model learning. The dictionary
confounder will introduce two backdoor paths, one from positively-labeled
instances ($X^{p}$) to entity labels ($Y$) and the other from negatively-
labeled instances ($X^{n}$) to entity labels. These backdoor paths introduce
spurious correlations during learning, therefore result in the intra-
dictionary bias. Furthermore, the current learning criteria of DS-NER models
is to optimize over the correlations between the instances ($X$) and entity
types ($Y$) given one specific dictionary ($D$), namely $P(Y|X,D)$. Such
criteria, however, diverges from the primary goal of learning a dictionary-
free NER model (i.e., $P(Y|X)$), and results in the inter-dictionary bias.
Based on the above analysis, unbiased DS-NER should remove the spurious
correlations introduced by backdoor paths and capture the true dictionary-free
causal relations.

To this end, we conduct causal interventions to de-bias DS-NER from the biased
dictionary. For intra-dictionary bias, we intervene on the positive instances
and the negative instances to block the backdoor paths in SCM, then the
spurious correlations introduced by dictionary confounder will be removed.
Specifically, we conduct backdoor adjustment to learn de-biased DS-NER models,
i.e., we optimize the DS-NER model based on the causal distribution, rather
than from the spurious correlation distribution. For inter-dictionary bias, we
propose to leverage causal invariance regularizer Mitrovic et al. (2021),
which will make the learned representation more robust to the perturbation of
dictionaries. For each instance in the training data, causal invariance
regularizer will preserve the underlying causal effects unchanged across
different dictionaries. The proposed method is model-free, which can be used
to resolve the dictionary bias in different DS-NER models by being applied as
a plug-in during model training.

We conducted experiments on four standard DS-NER datasets: CoNLL2003,
Twitter2005, Webpage, and Wikigold. Experiments on three state-of-the-art DS-
NER models show that the proposed de-biasing method can effectively solve both
intra-dictionary and inter-dictionary biases, and therefore significantly
improve the performance and the robustness of DS-NER in almost all settings.
Generally, the main contributions of this paper are:

  * •

We proposed a causal framework, which not only fundamentally formulates the
DS-NER process, but also explains the causes of both intra-dictionary bias and
inter-dictionary bias.

  * •

Based on the causal framework, we conducted causal interventions to de-bias
DS-NER. For intra-dictionary bias, we conduct causal interventions via
backdoor adjustment to remove spurious correlations introduced by the
dictionary confounder. For inter-dictionary bias, we propose a causal
invariance regularizer which will make DS-NER models more robust to the
perturbation of dictionaries.

  * •

Experimental results on four standard DS-NER datasets and three DS-NER models
demonstrate that our method can significantly improve the performance and the
robustness of DS-NER.

##  2 A Causal View on DS-NER

In this section, we formulate DS-NER with a structural causal model (SCM),
then identify the causes of both intra-dictionary bias and inter-dictionary
bias using the SCM. An SCM captures the causal effect between different
variables and describes the generative process of a causal distribution, which
can be visually presented using a directed acyclic graph (DAG). In SCM, each
node represents a random variable, and a directed edge represents a direct
causal relationship between two variables. Based on SCM, the confounders and
backdoor paths Pearl et al. (2000) can be identified. In the following, we
will describe the causal view of DS-NER and then identify the dictionary bias.

###  2.1 Structural Causal Model for DS-NER

Figure 2 shows the structural causal model for DS-NER, which contains 7 key
variables in the DS-NER procedure: 1) the applied dictionary $D$ for distant
annotation; 2) the unlabeled instances $X$, where each instance is a pair of
(mention candidate, context), and in training stage $X$ will be automatically
labeled by $D$; 3) the positive training instances $X^{p}$, which are
instances in $X$ being labeled as positive instances (i.e., entity mentions)
by dictionary $D$; 4) the negative training instances $X^{n}$, which are
instances being labeled as negative instances by dictionary $D$; 5) the
learned DS-NER model $M$, which summarizes NER evidences from DS-labeled data
during training, and predicts new instances during testing; 6) the
representations of instances $R$, which is encoded dense representations of
instances $X$ using the learned model $M$; 7) the predicted entity labels $Y$
of instances in $X$ based on the representation $R$.

Defining these variables, the causal process of DS-NER can be formulated using
SCM into two steps: distant supervision (DS) step and NER step respectively.
For DS step, the procedure will generate DS-labeled data and learn DS-NER
models by following causal relations:

  * •

${D}{\rightarrow}{X^{p}}{\leftarrow}{X}$ and
${D}{\rightarrow}{X^{n}}{\leftarrow}{X}$ represent the distant annotation
process, which uses dictionary $D$ to annotate the unlabeled instances $X$ and
splits them into two sets: $X^{p}$ and $X^{n}$.

  * •

${X^{p}}{\rightarrow}{M}{\leftarrow}{X^{n}}$ represents the learning process,
where model $M$ is the learned DS-NER model using $X^{p}$ and $X^{n}$. We
denote the $X^{p}$ and $X^{n}$ generated from dictionary $D$ as $X^{p}(D)$ and
$X^{n}(D)$ respectively.

And the causal relation in NER step can be summarized as:

  * •

${M}{\rightarrow}{R}{\leftarrow}{X}$ is the representation learning procedure,
which uses the learned model $M$ to encode instances $X$.

  * •

${R}{\rightarrow}{Y}$ represents the entity recognition process, where the
labels of instances depend on the learned representation $R$ and instances
$X$. We denote the entity labels corresponding to $X^{p}$ and $X^{n}$ as
$Y^{p}$ and $Y^{n}$ respectively.

###  2.2 Cause of Intra-dictionary Bias

Given distant annotation $X^{p}$ and $X^{n}$, the learning process of DS-NER
will maximize the probability $P(Y^{p}{=}1,Y^{n}{=}0|X^{p},X^{n},D)$.
Unfortunately, because $D$ is a confounder for $X^{p}$ and $X^{n}$ in SCM,
this criteria will introduce spurious correlations and result in the intra-
dictionary bias: (1) When maximizing $P(Y{=}1|X^{p},D)$, we want NER models to
rely on the actual causal path ${X^{p}}{\rightarrow}{Y}$. However, in SCM
there exists a backdoor path
${X^{p}}{\leftarrow}{D}{\rightarrow}{X^{n}}{\rightarrow}{M}$ which will
introduce spurious correlation between $Y$ and $X^{p}$. Intuitively, this
backdoor path appears as the false negative instances in $X^{n}$. Because
these false negative instances have correct entity contexts but out-of-
dictionary names, they will mislead the models to underfit the entity context
for prediction. (2) When maximizing $P(Y{=}0|X^{n},D)$, we want NER models to
rely on the actual causal path ${X^{n}}{\rightarrow}{Y}$. However, in SCM
there exists a backdoor
path${X^{n}}{\leftarrow}{D}{\rightarrow}{X^{p}}{\rightarrow}{M}$ which will
introduce spurious correlation between $Y$ and $X^{n}$. Intuitively, this
backdoor path appears as the false positive instances in $X^{p}$. Because
these false positive instances have in-dictionary entity names but spurious
context, they will mislead the models to overfit the names in dictionary.

In general, the intra-dictionary bias is caused by backdoor paths introduced
by $D$, and this bias will mislead the NER models to overfit names in
dictionary and underfit the context of entities.

###  2.3 Cause of Inter-dictionary Bias

As mentioned above, DS-NER models are learned by fitting
$P(Y^{p}{=}1,Y^{n}{=}0|X^{p},X^{n},D)$. This criteria will mislead the model
when learning the correlation between $X$ and $Y$ with spurious information in
$D$ because the learning criteria is conditioned on it. However, a robust NER
model should fit the underlying distribution $P(Y|X)$, rather than the
dictionary-conditioned distribution $P(Y|X,D)$. From the SCM, the dictionary
$D$ will significantly influence the learned NER models $M$, and in turn
result in different learned causal effects in the path $X\rightarrow
R\rightarrow Y$ and entity prediction $Y$. As a result, DS-NER models will fit
different underlying distributions given different dictionaries, and therefore
results in inter-dictionary bias.

However, in real-world applications, the dictionaries are affected by various
factors, such as source, coverage or time. Therefore, to enhance the
robustness of the learning process, it is critical to alleviate the spurious
influence of dictionary $D$ on the learned causal effects between $X$ and $Y$.
That is, we want DS-NER models to capture the dictionary-invariant entity
evidence, rather than fit the dictionary-specific features.

##  3 De-biasing DS-NER via Causal Intervention

In this section, we describe how to de-bias DS-NER. Specifically, for intra-
dictionary bias, we propose to use backdoor adjustment to block the backdoor
paths. For inter-dictionary bias, we design a causal invariance regularizer to
capture the dictionary-invariant evidence for NER.

###  3.1 Removing Intra-dictionary Bias via Backdoor Adjustment

Based on the analysis in Section 2.2, the intra-dictionary bias is caused by
the backdoor paths
${X^{p}}{\leftarrow}{D}{\rightarrow}{X^{n}}{\rightarrow}{M}$ and
${X^{n}}{\leftarrow}{D}{\rightarrow}{X^{p}}{\rightarrow}{M}$. To remove these
biases, we block both backdoor paths by intervening both $X^{p}$ and $X^{n}$.
After causal intervention, the learning of DS-NER models will fit the correct
causal relation $P(Y^{p}{=}1|do(X^{p}(D)),X^{n})$ and
$P(Y^{n}{=}0|do(X^{n}(D)),X^{p})$. Here $do(X^{p}(D)){=}do(X^{p}{=}X^{p}(D))$
represents the mathematical operation to intervene $X^{p}$ and preserve it to
be $X^{p}(D)$ in the whole population.

#### Backdoor Adjustments.

To calculate the distribution $P(Y^{p}{=}1|do(X^{p}(D)))$ after causal
intervention, we conduct backdoor adjustment according to causal theory Pearl
(2009):

$\displaystyle P_{pos}(D){\triangleq}$ $\displaystyle
P(Y^{p}{=}1|do(X^{p}(D)))$ (1) $\displaystyle{=}$
$\displaystyle\sum_{i}P(Y^{p}{=}1|X^{p}(D),X^{n}(D_{i}))$ $\displaystyle\quad\
\ \times P(D_{i})$

where $X^{n}(D_{i})$ denotes the negative instances generated from the DS
dictionary $D_{i}$. $P(Y^{p}{=}1|X^{p}(D),X^{n}(D_{i}))$ is the probability of
predicting $X^{p}(D)$ into $Y{=}1$, which can be formulated using a neural
network-based DS-NER model parametrized by $\theta$, i.e., $P(Y|X^{p},X^{n})$
= $P(Y|X^{p},X^{n};\theta)$. Detailed derivations is shown in appendix A.

Note the distribution $P(Y^{p}{=}1|do(X^{p}(D)))$ in the causal framework is
not the marginalized distribution $P(Y^{p}{=}1|X^{p}(D))$ in the probability
framework. Otherwise the marginalization should take place in the conditional
distribution $P(D_{i}|X^{p})$ rather than $P(D_{i})$. Furthermore, as shown in
Figure 3, $X^{p}{=}X^{p}(D_{i})$ and $X^{n}{=}X^{n}(D_{j})$ can not happen
together in probabilistic view unless $D_{i}{=}D_{j}$. However, in the causal
view, they can happened together via the causal intervention. That is
$do(X^{p}{=}X^{p}(D_{i}))$ and $X^{n}{=}X^{n}(D_{j})$, which is shown in
Figure 3 (c). For more details, please refer to Neal (2020) for a brief
introduction.

Figure 3: An illustration on causal intervention. (a) and (b) show the
generated instances according to dictionary $D_{i}$ and $D_{j}$. And (c) shows
the generated instances from $do(X^{p}(D_{i}))$ and $X^{n}(D_{j})$.

Similarly, to block the backdoor paths and calculate the causal distribution
$P(Y^{n}{=}0|do(X^{n}(D)))$, we can conduct backdoor adjustment on $X^{n}$ by:

$\displaystyle P_{neg}(D){\triangleq}$ $\displaystyle
P(Y^{n}{=}0|do(X^{n}(D)))$ (2) $\displaystyle{=}$
$\displaystyle\sum_{i}P(Y^{n}{=}0|X^{n}(D),X^{p}(D_{i}))$ $\displaystyle\quad\
\ \times P(D_{i})$

#### Estimating Dictionary Probabilities.

Because we only have one global dictionary $D$, it is hard to estimate the
probability of other dictionary $D_{i}$ used in the Equation (1) and (2). To
tackle this problem, we sample $K$ sub-dictionaries by sampling entities from
the global dictionary $D$. The probability of each entity being sampled
corresponds to its utterance frequency in a large-scale corpus. Then we
applied a uniform probability assumption to these sampled dictionaries, which
means that these sub-dictionaries will then be used to conduct backdoor
adjustment with equal dictionary probabilities, i.e., $P(D_{i})=\frac{1}{K}$.

#### Learning DS-NER Models with Causal Relation.

Given the above two causal distributions after backdoor adjustment, the DS-NER
models can be effectively learned, and the intra-dictionary bias can be
eliminated based on the causal relations between $X^{p}$, $X^{n}$ and $Y$.
Formally, we optimize DS-NER models by minimizing the following negative
likelihood based on causal relation:

$L_{BA}(\theta){=}-\log P_{pos}(D)-\log P_{neg}(D)$ (3)

Note that the proposed method is model-free, which means that it can be
applied to the majority of previous DS-NER methods by adaptively changing the
underlying parametrization of probability distribution
$P(Y|X^{p},X^{n};\theta)$ .

###  3.2 Eliminating Inter-dictionary Bias via Causal Invariance Regularizer

This section describes causal invariance regularizer to eliminate the inter-
dictionary bias. Specifically, after backdoor adjustment for intra-dictionary
bias, the causal distribution we optimize (i.e., $P_{pos}(D)$ and
$P_{neg}(D)$) still depends on the dictionary $D$. As a result, given
different dictionaries, DS-NER models will fit different underlying causal
distributions and result in inter-dictionary bias.

Ideally, a robust DS-NER learning algorithm should be dictionary-free, i.e.,
we should directly optimize towards the implicit distribution of $P(Y|X)$.
However, it is impossible to directly achieve this because the golden answer
$Y$ of $X$ is invisible in DS-NER. To enhance the robustness of the learning
process, this section proposes a causal invariance regularizer, which ensures
DS-NER models to learn useful entity evidence for NER but not to fit
dictionary-specific features. Specifically, the goal of causal invariance
Pearl et al. (2000) is to ensure learned NER models will keep similar causal
effects using different dictionaries, which can be formulated as:

$\displaystyle\theta^{*}_{inv}{=}\arg\min_{\theta}\|$ $\displaystyle
P_{pos}(D_{i})-P_{pos}(D_{j})$ (4) $\displaystyle+$ $\displaystyle
P_{neg}(D_{i})-P_{neg}(D_{j})\|$

Here $||*||$ measures the distance between two distributions. However, as we
mentioned above, this distance cannot be directly optimized because the golden
label $Y$ of $X$ is unknown. Fortunately, in the SCM, the impact from
dictionary $D$ to the entity label $Y$ are all through the model $M$ and the
representation $R$, i.e., through the path $D\rightarrow M\rightarrow
R\rightarrow Y$. As a result, the bias from the dictionary $D$ can be
eliminated by preserving the causal effects between $X$ and any node in the
path. A simple and reasonable solution is to preserve the causal invariance of
the representation $R$. That is, given different dictionaries, we keep the
causal effects from $X$ to $R$ unchanged, and therefore causal effects of
$X\rightarrow Y$ will remain unchanged. Specifically, when learning causal
effects given an dictionary $D$, the causal invariance regularizer will
further enhance its causal consistency with other dictionaries by minimizing
its representation distances to other dictionaries:

$\displaystyle L_{CIR}(\theta;D){=}\sum_{i{=}1}^{K}\sum_{x\in X}$
$\displaystyle||R_{D}(x;\theta)$ $\displaystyle-R_{D^{i}}(x)||^{2}$ (5)

Here $R_{D}(x;\theta)$ is the representation of instance $x$, which is derived
from the NER model $M$ by fitting the causal effects of dictionary $D$. The
reference dictionary $D^{i}$ in the formulations are generated in the same way
as we described in Section 3.1 and $K$ is the number of sub-dictionaries.
Therefore, this regularizer ensures that the representations learned using
different dictionaries will be consistent, and the inter-dictionary bias is
eliminated.

Finally, we combine (3) and (5) to de-bias both intra-dictionary bias and
inter-dictionary bias and obtain the final DS-NER models by optimizing:

$L=\sum_{i}L_{BA}^{i}+\lambda L_{CIR}$ (6)

where $\lambda$ is a hyper-parameter which controls the relative importance of
these two losses and is tuned on the development set.

##  4 Experiments

###  4.1 Experimental Settings

#### Datasets.

We conduct experiments on four standard datasets: (1) CoNLL2003 (Tjong Kim
Sang and De Meulder, 2003) is a well known open-domain NER dataset. It
consists of 20744 sentences collected from 1393 English news articles and is
annotated with four types: PER, ORG, LOC and MISC. (2) Twitter (Godin et al.,
2015) is from the WNUT 2016 NER shared task. It consists of 7236 sentences
with 10 entity types. (3) Webpage (Ratinov and Roth, 2009) contains 20
webpages, including personal, academic and computer-science conference
homepages. It consists of 619 sentences with the four types the same as
CoNLL2003. (4) Wikigold (Balasuriya et al., 2009) contains 149 articles from
the May 22, 2008 dump of English Wikipedia. It consists of 1969 sentences with
the same types of CoNLL2003.

#### Distant Annotation Settings.

We use two distant annotation settings: String-Matching and KB-Matching (Liang
et al., 2020). String-Matching labels dataset by directly matching names in
dictionary with sentences. KB-Matching is more complex, which uses a set of
hand-crafted rules to match entities. We find KB-Matching can generate better
data than String-Matching, but String-Matching is a more general setting. In
our experiments, we report performance on both KB-Matching and String-Matching
settings.

#### Implementation Detail.

We implement BiLSTM-CRF with AllenNLP (Gardner et al., 2017), an open-source
NLP research library, and the input vector is the 100-dimension GloVe
Embeddings (Pennington et al., 2014). For other baselines, we use the
officially released implementation from the authors. We openly release our
source code at github.com/zwkatgithub/DSCAU.

| KB-Matching | String-Matching
---|---|---
Methods | CoNLL2003 | Twitter | Webpage | Wikigold | CoNLL2003 | Twitter | Webpage | Wikigold
| Supervised Learning Baselines
BiLSTM-CRF | 85.98 | 32.30 | 51.59 | 57.01 | – | – | – | –
RoBERTa-base | 91.12 | 50.47 | 74.07 | 84.02 | – | – | – | –
| Distant Supervision Baselines
DictMatch | 71.40 | 35.83 | 52.45 | 47.76 | 43.91 | 19.18 | 2.56 | 19.04
BiLSTM-CRF | 64.62 | 30.25 | 13.90 | 37.46 | 60.52 | 31.67 | 24.67 | 27.97
RoBERTa-base | 76.04 | 46.40 | 54.07 | 52.83 | 73.94 | 46.02 | 57.14 | 37.94
+BA (Ours) | 76.43(+0.40) | 46.75(+0.35) | 59.28(+5.21) | 53.56(+0.73) | 75.43(+1.49) | 46.69(+0.67) | 58.71(+1.57) | 42.23(+4.59)
+BA+CIR (Ours) | 78.78(+2.74) | 47.12(+0.72) | 59.06(+4.99) | 55.60(+2.77) | 75.59(+1.65) | 47.27(+1.25) | 58.04(+0.90) | 44.19(+6.25)
BOND | 79.83 | 47.72 | 61.28 | 60.23 | 75.51 | 48.72 | 66.23 | 42.17
+BA (Ours) | 80.81(+0.98) | 48.45(+0.73) | 64.65(+3.37) | 60.81(+0.58) | 76.21(+0.70) | 49.12(+0.40) | 66.67(+0.44) | 42.53(+0.36)
+BA+CIR (Ours) | 81.54(+1.71) | 49.01(+1.29) | 64.71(+3.43) | 61.48(+1.25) | 76.53(+1.02) | 48.82(+0.10) | 66.67(+0.44) | 45.55(+3.38)

Table 1: F1 scores on CoNLL2003, Twitter, Webpage and Wikigold. BA and CIR
denotes the proposed backdoor adjustment and causal invariance regularizer
respectively. We can see that the proposed causal intervention approach
achieves significant improvements on almost all settings.

| KB-Matching | String-Matching
---|---|---
PU-Learning | 74.96 | 72.42
+BA (Ours) | 80.93(+5.97) | 76.17(+3.75)
+BA+CIR (Ours) | 81.96(+7.00) | 76.62(+4.20)

Table 2: F1 scores on CoNLL2003 dataset based on PU-Learning Peng et al.
(2019). We don’t report the results on other datasets, because PU-Learning
needs high-quality dictionary which only provided by CoNLL2003.

###  4.2 Baselines

The proposed de-biased training strategy is both model-free, and learning
algorithm-free. Therefore, we use the following base DS-NER baselines and
compare the performance of using/not using our de-biased training strategy:

#### DictMatch

, which perform NER by directly matching text with names in a dictionary, so
no learning is needed.

#### Fully-supervised baselines

, including: (i) BiLSTM-CRF (Lample et al., 2016), which uses Glove
(Pennington et al., 2014) for word embeddings; (ii) RoBERTa-base (Liu et al.,
2019), which encodes text using RoBERTa-base then predict token label via a
multi-layer perceptron.

#### Naive Distant Supervision (Naive)

, which directly uses weakly labeled data to train a fully-supervised model.
It could be considered as the lower bound of DS-NER.

#### Positive-Unlabeled Learning (PU-Learning)

(Peng et al., 2019), which formulates DS-NER as a positive-unlabeled learning
problem. It could obtain unbiased loss estimation of unlabeled data. However,
it assumes that there are no false positive instances which may be incorrect
in many datasets.

#### BOND

(Liang et al., 2020), which is a two-stage learning algorithm: In the first
stage, it leverages pre-trained language model to improve the recall and
precison of the NER model; In the second stage, it adopts a self-training
approach to further improve the model performance.

###  4.3 Main Results

Table 1 and Table 2 show the overall performance (F1 scores) of different
baselines and our methods. For our method, we use BA to denote backdoor
adjustment, and CIR to denote causal invariance regularizer. We conduct our
debiasing method on three base models: RoBERTa-base, PU-Learning and BOND,
therefore we have 6 systems of our methods: RoBERTa+BA, RoBERT+BA+CIR, PU-
Learning+BA, PU-Learning+BA+CIR, BOND +BA, BOND+BA+CIR.

We can see that: (1) DS-NER models are severely influenced by the dictionary
bias. Without debiasing, the naive DS-NER baselines BiLSTM-CRF and RoBERTa-
base can only achieve comparable performance with the simple DictMatch
baselines. And by taking the dictionary bias into consideration, PU-Learning,
BOND with our method can significantly improve the performance of DS-NER.
Compared with DictMatch, they correspondingly achieve 4.99%, 21.98% F1
improvements on average. This verified that the dictionary bias is critical
for DS-NER models. (2) By debiasing DS-NER models via causal intervention, our
method can achieve significant improvement. Compared with their counterparts,
our full methods RoBERTa+BA+CIR, BOND+BA+CIR correspondingly achieve 4.91%,
3.18% improvements averaged on four datasets in KB-Matching (5.75%, 2.56%
improvements on String-Matching) and PU-Learning+BA+CIR achieves 9.34%
improvement on CoNLL2003 dataset in KB-Matching (5.80% improvement in String-
Matching). This verified the effectiveness of using causal intervention for
debiasing DS-NER. (3) Our method can effectively resolve both intra-dictionary
and inter-dictionary biases. Both of backdoor adjustment and causal invariance
regularizer can improve the NER performance. By conducting backdoor
adjustment, our method can achieve a 3.27% F1 improvement averaged on all base
models and all datasets. And further conducting causal invariance regularizer
can future improve 4.63% average F1.

###  4.4 Effects on Robustness

To verify whether the causal invariance regularizer can significantly improve
the robustness of DS-NER across different dictionaries, we further compared
the predicting likelihood of golden mentions using different dictionaries.
Specifically, we train the same RoBERTa-Classifier DS-NER models by sampling 4
dictionaries. Figure 4 shows the average predicting likelihood before/after
using our de-biasing method.

From Figure 4, we can see that the proposed causal invariance regularizer
significantly reduced the likelihood gaps between different dictionaries. This
verified that removing the inter-dictionary bias can significant benefit the
robustness of DS-NER. Furthermore, we can see that the likelihoods of golden
mentions are remarkably increased, which represents a better NER performance.
These all demonstrate the effectiveness of the proposed causal invariance
regularizer.

Figure 4: The likelihood variance between different dictionaries before/after
using causal invariance regularizer (RoBERTa-Classifier on CoNLL2003), We can
see that the performance variance significantly decreases, which verifies that
causal invariance regularizer can significantly improve the robustness of DS-
NER. Figure 5: F1 scores when with different sub-dictionary coverages on the
test set of CoNLL2003. Figure 6: F1 scores when using different sub-dictionary
quantities on the test set of CoNLL2003.

###  4.5 Influence of Sub-dictionaries

To conduct causal intervention, our method needs to sample sub-dictionaries
from the original one. To analyze the influence of the coverage and the
quantity of sub-dictionaries, we conducted experiments on sub-dictionaries
with different coverages and different quantities.

#### Dictionary Coverage.

Figure 5 shows the results with different dictionary coverages. We can see
that our method is not sensitive to the coverage of sub-dictionaries: it can
achieve robust performance from 40% to 80% coverage. All three models achieved
the best performance at the 70% coverage. This result demonstrates the
robustness of our method on dictionary coverage.

#### Dictionary Quantity.

Figure 6 shows the results with different sub-dictionary quantities. We can
see that our method can achieve performance improvement by sampling more sub-
dictionaries. This is because more sub-dictionaries will lead to more accurate
estimation of both the dictionary probability in backdoor adjustment and the
dictionary variance in causal invariance regularizer. Futhermore, we can see
that the performance using only one sub-dictionary (i.e., DS-NER without
causal intervention) is significantly worse than other settings, this further
verifies the effectiveness of our method.

##  5 Related Work

DS-NER. Supervised NER models have achieved promising performance (Lample et
al., 2016; Lin et al., 2019a, b). However, the reliance on labeled data limits
their applications in open situations. Distant supervision (Mintz et al.,
2009) is a promising technique to alleviate the data bottleneck for NER, which
generates large-scale training data by matching sentences with external
dictionaries. Current DS-NER studies focus on denoising the distantly labeled
training data for better model learning. Yang et al. (2018) adopted
reinforcement learning for denoising. Shang et al. (2018) proposed a sequence
labeling framework TieOrBreak, which can avoid noise caused by a single word.
Cao et al. (2019) promoted the quality of data by exploiting labels in
Wikipedia. Peng et al. (2019) employed Positive-Unlabeled Learning to obtain
unbiased estimation of the loss value. Liang et al. (2020) used self-training
method which leverages a pretrained language model as teacher model to guide
the training of student model.

Causal Inference. Causal Inference (Pearl, 2009; Pearl and Mackenzie, 2018)
has been widely adopted in psychology, politics and epidemiology for years
(MacKinnon et al., 2007; Richiardi et al., 2013; Keele, 2015). It can provide
more reliable explanations by removing confounding bias in data, and also
provide debiased solutions by learning causal effect rather than correlation
effect. Recently, many causal inference techniques are used in computer vision
(Tang et al., 2020; Qi et al., 2020) and natural language process (Wu et al.,
2020; Zeng et al., 2020).

##  6 Conclusions

This paper proposes to identify and resolve the dictionary bias in DS-NER via
causal intervention. Specifically, we first formulate DS-NER using a
structural causal model, then identity the causes of both intra-dictionary and
inter-dictionary biases, finally de-bias DS-NER via backdoor adjustment and
causal invariance regularizer. Experiments on four datasets and three
representative DS-NER models verified the effectiveness and the robustness of
our method.

## Acknowledgements

This work is supported by the National Natural Science Foundation of China
under Grants no.U1936207, Beijing Academy of Artificial Intelligence
(BAAI2019QN0502), scientific research projects of the State Language
Commission (YW135-78), and in part by the Youth Innovation Promotion
Association CAS(2018141). Moreover, we thank all reviewers for their valuable
comments and suggestions.

## References

  * Balasuriya et al. (2009) Dominic Balasuriya, Nicky Ringland, Joel Nothman, Tara Murphy, and James R. Curran. 2009.  Named entity recognition in Wikipedia.  In _Proceedings of the 2009 Workshop on The People’s Web Meets NLP: Collaboratively Constructed Semantic Resources (People’s Web)_. Association for Computational Linguistics.
  * Bordes et al. (2015) Antoine Bordes, Nicolas Usunier, Sumit Chopra, and Jason Weston. 2015.  Large-scale simple question answering with memory networks.  _CoRR_.
  * Cao et al. (2019) Yixin Cao, Zikun Hu, Tat-seng Chua, Zhiyuan Liu, and Heng Ji. 2019.  Low-resource name tagging learned with weakly labeled data.  Association for Computational Linguistics.
  * Gardner et al. (2017) Matt Gardner, Joel Grus, Mark Neumann, Oyvind Tafjord, Pradeep Dasigi, Nelson F. Liu, Matthew Peters, Michael Schmitz, and Luke S. Zettlemoyer. 2017\.  Allennlp: A deep semantic natural language processing platform.
  * Godin et al. (2015) Fréderic Godin, Baptist Vandersmissen, Wesley De Neve, and Rik Van de Walle. 2015.  Multimedia lab @ ACL WNUT NER shared task: Named entity recognition for Twitter microposts using distributed word representations.  In _Proceedings of the Workshop on Noisy User-generated Text_. Association for Computational Linguistics.
  * Keele (2015) Luke Keele. 2015.  The statistics of causal inference: A view from political methodology.  _Political Analysis_ , pages 313–335.
  * Lample et al. (2016) Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami, and Chris Dyer. 2016.  Neural architectures for named entity recognition.  Association for Computational Linguistics.
  * Liang et al. (2020) Chen Liang, Yue Yu, Haoming Jiang, Siawpeng Er, Ruijia Wang, Tuo Zhao, and Chao Zhang. 2020.  Bond: Bert-assisted open-domain named entity recognition with distant supervision.  In _ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_.
  * Lin et al. (2019a) Hongyu Lin, Yaojie Lu, Xianpei Han, and Le Sun. 2019a.  Sequence-to-nuggets: Nested entity mention detection via anchor-region networks.  Association for Computational Linguistics.
  * Lin et al. (2019b) Hongyu Lin, Yaojie Lu, Xianpei Han, Le Sun, Bin Dong, and Shanshan Jiang. 2019b.  Gazetteer-enhanced attentive neural networks for named entity recognition.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 6232–6237, Hong Kong, China. Association for Computational Linguistics.
  * Lin et al. (2020) Hongyu Lin, Yaojie Lu, Jialong Tang, Xianpei Han, Le Sun, Zhicheng Wei, and Nicholas Jing Yuan. 2020.  A rigorous study on named entity recognition: Can fine-tuning pretrained model lead to the promised land? In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 7291–7300, Online. Association for Computational Linguistics.
  * Lin et al. (2016) Yankai Lin, Shiqi Shen, Zhiyuan Liu, Huanbo Luan, and Maosong Sun. 2016.  Neural relation extraction with selective attention over instances.  Association for Computational Linguistics.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized BERT pretraining approach.  _CoRR_ , abs/1907.11692.
  * Ma and Hovy (2016) Xuezhe Ma and Eduard Hovy. 2016.  End-to-end sequence labeling via bi-directional LSTM-CNNs-CRF.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. Association for Computational Linguistics.
  * MacKinnon et al. (2007) David P MacKinnon, Amanda J Fairchild, and Matthew S Fritz. 2007.  Mediation analysis.  _Annu. Rev. Psychol._ , 58:593–614.
  * Mintz et al. (2009) Mike Mintz, Steven Bills, Rion Snow, and Daniel Jurafsky. 2009.  Distant supervision for relation extraction without labeled data.  Association for Computational Linguistics.
  * Mitrovic et al. (2021) Jovana Mitrovic, Brian McWilliams, Jacob C Walker, Lars Holger Buesing, and Charles Blundell. 2021.  Representation learning via invariant causal mechanisms.  In _International Conference on Learning Representations_.
  * Neal (2020) Brady Neal. 2020.  _Introduction to Causal Inference from a Machine Learning Perspective_.
  * Pearl (1995) Judea Pearl. 1995.  Causal diagrams for empirical research.  _Biometrika_ , 82(4):669–688.
  * Pearl (2009) Judea Pearl. 2009.  _Causality_.  Cambridge university press.
  * Pearl and Mackenzie (2018) Judea Pearl and Dana Mackenzie. 2018.  _The Book of Why: The New Science of Cause and Effect_.  Basic Books.
  * Pearl et al. (2000) Judea Pearl et al. 2000.  Models, reasoning and inference.  _Cambridge, UK: CambridgeUniversityPress_.
  * Peng et al. (2019) Minlong Peng, Xiaoyu Xing, Qi Zhang, Jinlan Fu, and Xuanjing Huang. 2019.  Distantly supervised named entity recognition using positive-unlabeled learning.  Association for Computational Linguistics.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014.  Glove: Global vectors for word representation.  In _Empirical Methods in Natural Language Processing (EMNLP)_.
  * Qi et al. (2020) Jiaxin Qi, Yulei Niu, Jianqiang Huang, and Hanwang Zhang. 2020.  Two causal principles for improving visual dialog.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10860–10869.
  * Ratinov and Roth (2009) Lev Ratinov and Dan Roth. 2009.  Design challenges and misconceptions in named entity recognition.  In _Proceedings of the Thirteenth Conference on Computational Natural Language Learning (CoNLL-2009)_. Association for Computational Linguistics.
  * Richiardi et al. (2013) Lorenzo Richiardi, Rino Bellocco, and Daniela Zugna. 2013.  Mediation analysis in epidemiology: methods, interpretation and bias.  _International journal of epidemiology_ , 42(5):1511–1519.
  * Shang et al. (2018) Jingbo Shang, Liyuan Liu, Xiaotao Gu, Xiang Ren, Teng Ren, and Jiawei Han. 2018\.  Learning named entity tagger using domain-specific dictionary.  Association for Computational Linguistics.
  * Tang et al. (2020) Kaihua Tang, Jianqiang Huang, and Hanwang Zhang. 2020.  Long-tailed classification by keeping the good and removing the bad momentum causal effect.  _Advances in Neural Information Processing Systems_ , 33.
  * Tjong Kim Sang and De Meulder (2003) Erik F. Tjong Kim Sang and Fien De Meulder. 2003.  Introduction to the CoNLL-2003 shared task: Language-independent named entity recognition.  In _Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003_.
  * Wu et al. (2020) Yiquan Wu, Kun Kuang, Yating Zhang, Xiaozhong Liu, Changlong Sun, Jun Xiao, Yueting Zhuang, Luo Si, and Fei Wu. 2020.  De-biased court’s view generation with causality.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 763–780.
  * Yang et al. (2018) Yaosheng Yang, Wenliang Chen, Zhenghua Li, Zhengqiu He, and Min Zhang. 2018.  Distantly supervised NER with partial annotation learning and reinforcement learning.  Association for Computational Linguistics.
  * Zeng et al. (2020) Xiangji Zeng, Yunliang Li, Yuchen Zhai, and Yin Zhang. 2020.  Counterfactual generator: A weakly-supervised method for named entity recognition.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 7270–7280.
  * Zhang et al. (2021) Wenkai Zhang, Hongyu Lin, Xianpei Han, Le Sun, Huidan Liu, Zhicheng Wei, and Nicholas Yuan. 2021.  Denoising distantly supervised named entity recognition via a hypergeometric probabilistic model.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35(16):14481–14488.

##  Appendix A Proof of Backdoor Adjustment

We prove the backdoor adjustment for SCM using the do-calculus (Pearl, 1995)
and the Truncated Factorization (Neal, 2020).

First of all, we write the joint distribution as shown in our causal graph:

$\displaystyle P(D,$ $\displaystyle X^{p},X^{n},Y,M,R,X)$ $\displaystyle=$
$\displaystyle P(D)P(X)P(X^{p}|D,X)P(X^{n}|D,X)$ $\displaystyle
P(M|X^{p},X^{n})P(R|M,X)P(Y|R)$

Due to the objective of our method is debiasing DS-NER models during training,
we ignore the unlabeled instances variable $X$ which is not related to the
training process. Then we obtain the following equation:

$\displaystyle P(D,$ $\displaystyle X^{p},X^{n},Y,M,R)$ $\displaystyle=$
$\displaystyle P(D)P(X^{p}|D)P(X^{n}|D)$ $\displaystyle
P(M|X^{p},X^{n})P(R|M)P(Y|R)$

Note that the prediction step of a NER model
${M}{\rightarrow}{R}{\rightarrow}{Y}$ doesn’t have causal effects with other
variables, we abbreviate $P(M|X^{p},X^{n})P(R|M,X)P(Y|R)$ as
$P(Y|X^{p},X^{n})$. Finally, we obtain the simplified joint distribution:

$\displaystyle P($ $\displaystyle D,X^{p},X^{n},Y)$ $\displaystyle=$
$\displaystyle P(D)P(X^{p}|D)P(X^{n}|D)P(Y|X^{p},X^{n})$

Then we conduct causal intervention on $X^{p}$, i.e., $do(X^{p}{=}X^{p}(D))$
where $X^{p}(D)$ denotes positive instances generated by dictionary $D$. Here,
we abbreviate it as $do(X^{p}(D))$. In practice, $do(X^{p}(D))$ denotes that
we use these positive instances to calculate loss value, therefore, in order
to explicitly indicate this, we use $Y^{p}{=}1$ in the following equation.
According to the Truncated Factorization (Neal, 2020), we can know
$P(X^{p}|D){=}1$, and obtain the following equation:

$\displaystyle P(D,$ $\displaystyle X^{n},Y^{p}{=}1|do(X^{p}(D)))$
$\displaystyle=$ $\displaystyle P(D)P(X^{n}|D)P(Y^{p}{=}1|X^{p}(D),X^{n})$

Next, we integrate $D$ and $X^{n}$:

$\displaystyle P(Y^{p}{=}1|do(X^{p}(D)))$ $\displaystyle=$
$\displaystyle\sum_{i}\sum_{X^{n}}P(D_{i})P(X^{n}|D_{i})P(Y^{p}{=}1|X^{p}(D),X^{n})$

Note that $P(X^{n}(D_{i})|D_{i}){=}1$ if and only if $X^{n}$ is generated by a
specific dictionary $D_{i}$, therefore we can obtain:

$\displaystyle P(Y^{p}{=}1|do(X^{p}(D)))$ $\displaystyle=$
$\displaystyle\sum_{i}\sum_{X^{n}}{P(D_{i})P(X^{n}|D_{i})P(Y^{p}{=}1|X^{p}(D),X^{n})}$
$\displaystyle=$
$\displaystyle\sum_{i}{P(D_{i})P(Y^{p}{=}1|X^{p}(D),X^{n}(D_{i}))}$


# Conformity: a Path-Aware Homophily measure for Node-Attributed Networks

Giulio Rossetti
KDD-Lab, ISTI (CNR)
G. Moruzzi, 1, Pisa
<EMAIL_ADDRESS>
Salvatore Citraro
Department of Computer Science, University of Pisa
Largo Bruno Pontecorvo, 3, Pisa
<EMAIL_ADDRESS>
Letizia Milli
Department of Computer Science, University of Pisa
Largo Bruno Pontecorvo, 3, Pisa
<EMAIL_ADDRESS>

###### Abstract

Unveil the homophilic/heterophilic behaviors that characterize the wiring
patterns of complex networks is an important task in social network analysis,
often approached studying the assortative mixing of node attributes. Recent
works underlined that a global measure to quantify node homophily necessarily
provides a partial, often deceiving, picture of the reality. Moving from such
literature, in this work, we propose a novel measure, namely Conformity,
designed to overcome such limitation by providing a node-centric
quantification of assortative mixing patterns. Differently from the measures
proposed so far, Conformity is designed to be path-aware, thus allowing for a
more detailed evaluation of the impact that nodes at different degrees of
separations have on the homophilic embeddedness of a target. Experimental
analysis on synthetic and real data allowed us to observe that Conformity can
unveil valuable insights from node-attributed graphs.

_K_ eywords Homophily $\cdot$ Attributed Networks $\cdot$ Mixing Patterns

00footnotetext: 2020 IEEE. Personal use of this material is permitted.
Permission from IEEE must be obtained for all other uses, in any current or
future media, including reprinting/republishing this material for advertising
or promotional purposes, creating new collective works, for resale or
redistribution to servers or lists, or reuse of any copyrighted component of
this work in other works.

##  1 Introduction

During the last decades, network science has become one of the fastest growing
multidisciplinary research fields. Every year, countless researchers, from
heterogeneous backgrounds, leverage network theory to analyze complex data
describing alternative facets of real world phenomena. From sociology to
biology, more and more domains study entities composed of several components -
each having its internal complexity and peculiar functionalities - all of them
strictly tied in functional relationships. Such complex organizations can
naturally be modeled as networks, and as such, analyzed. While reasoning on
networks built on top of contextual data, topology is only one of the aspects
to take into account: nodes and edges often carry additional semantic
information that are of uttermost importance to properly understand the
phenomena expressed by the underlying topological structure. Often, such
augmented structures are referred to as Feature-rich networks [1]. That
general term acts as an umbrella for several, more specific, class of network
extensions including temporal as well as probabilistic and attributed (or
labeled) networks. In this work, we are particularly interested in labeled or
node-attributed networks, where reliable external information is added to the
nodes as categorical or numerical attributes. Node-attributed graphs are a
quite expressive model of social network environments since several salient
dimensions (age, gender, nationality…) can be meaningfully studied by
leveraging such a framework.

Indeed, one of the salient aspects that makes network science a widespread
research methodology is its ability to unveil emergent behaviors of complex
systems. Network topology is, perhaps, the clearest example of how the overall
complexity of a whole system is more than the sum of the coupled interactions
among its components. Several modeling works have shown how some universal
network properties are the results of emergent behaviors: classic examples are
the long-tail degree distribution [2] and the meso-scale modular organization
[3] that describe complex systems as sparsely connected dense components.
Another relevant emerging behavior is _homophily_. It has been observed that
individuals are more likely to group in social circles if they share common
features and stay apart when some specificity diverges. Social network
analysis has deeply investigated such a phenomenon, trying to measure its
impact and propose a mechanistic explanation to its existence. A proxy often
used to estimate for homophilic behaviors fall under the name of Newman’s
_assortativity_ [4]. Such a measure aims to classify a whole network in a
range that goes among two extremes: _disassortative mixing_ , where nodes are
likely to be connected if they are anti-correlated w.r.t. a given property,
and _assortative mixing_ , where, conversely, nodes are likely to be connected
if they share a given property. Assortativity has been widely studied and
applied to characterize several phenomena such as degree correlation and node-
attribute correlations. One of the major drawbacks of such a measure, and
similar ones, lies in its definition scale: a complex behavior is summarized
in a single, average, score. Recently, a few works [5] tried to overcome such
limitation by proposing a multiscale extension of Newman’s assortativity, thus
allowing to analyze multimodal behaviors that the original score makes
impossible to observe (e.g., identifying different, even conflicting,
homophilic/heterophilic behaviors within the same complex system).

In this work, we move from such a line of research, proposing an alternative
proxy for measuring multiscale node homophilic couplings: Conformity, a node-
centric path-aware measure, able to unveil heterogeneous mixing patterns in
node-attributed networks, designed to cope with categorical (single and
multi)-attributes. Inspired by a higher-order assortativity definition, namely
the clumpiness score [6], Conformity takes into consideration the evidence
that nodes with similar characteristics are not divided by long chains.
Experimental results carried out on real world node-attributed networks
underline that Conformity allows to study homophilic patterns from a novel
point of view and make valuable inference on the social contexts it is applied
to.

The work is organized as follows. Section 2 introduces the relevant literature
to frame the proposed contribution; Section 3 formally introduces Conformity;
Section 4 discusses experimental results obtained applying Conformity to
synthetic as well as real-world data. Finally, Section 5 concludes the paper.

##  2 Related

Literature defines social homophily as the tendency of people to interact with
similar others in respect of dimensions such as age, gender, education, as
well as values, attitudes, and political beliefs, sourced by geographical
distances, households, workplaces, and universal human cognitive processes
[7]. Hidden social dynamics can be unveiled studying homophily as well as
heterophily among people: in the presence of segregation, interracial
friendships are less probable when social class is correlated with race [8];
in the early school grades, boys tend to form larger and more heterogeneous
cliques compared to the smaller and more homogeneous cliques of girls [9];
intergroup mixing is also a key factor in academic success when
interdisciplinary research is involved [10]. Such a brief set of examples let
us know how both homophily, and its counterpart, act as fundamental principles
in the choice of people’s social circles.

In the language of network science, they act as a discriminant factor for node
neighborhood selection. Network homophily can refer either to explicit
topology (e.g., nodes with a similar degree preferably connect) or to the
interactions between nodes sharing similar labels. Newman’s assortativity
coefficient [4] is the most known and used measure for quantifying homophily
in complex networks. Based on modularity, the coefficient is calculated as the
sum of the differences between the observed and the expected fraction of edges
between nodes sharing similar values of an attribute. Some recent extensions
or alternative approaches, like ProNe [11] or the VA-Index [12], are also able
to cope with pairs of attributes or vector of features, shedding light, more
than Newman’s coefficient, on the phenomenon of similarity between two or more
attributes based on network structure.

Such global and aggregated measures flatten and simplify a heterogeneous
context in one only score, and avoid the presence of outliers or different
mixing interactions characterizing different zones of networks and perhaps
also single nodes. In such scenarios, local or node-centric approaches (able
to assign a score to each graph node) should help for quantifying a more
reliable and exploitable network description. Since the only direct
neighborhood (or ego-network) of nodes can not be taken into consideration due
to its limited expressive power (inherited in the scale-free-like degree
distribution of complex networks), the issue is to define connectivity
boundednesses able to circumscribe those nodes whose importance is fundamental
in the assortative attitude measurement of a target one. While some lines of
research focused on degree assortativity [13] (extended to cope with higher-
order notions of node neighborhood such as a two-walks degree correlation [14]
or transsortativity [15]), the node-attributed counterpart of the problem has
not received much of attention.

Only a few studies address such a task in this latter scenario. Recent works
aimed to study the existence of possible relations among network structure and
label distribution among nodes (e.g., how structure and minority size generate
perception biases [16]) as well as shed light on the individual differences in
mixing (e.g., in the analysis of monophily, a concept aiming to identify those
individuals with extreme preferences for different labels [17]). Accordingly,
inferring and quantifying individual differences as well as different local
mixing comes as a hard task in complex networks studies. A model able to
characterize the within-group mean and variation of mixing patterns was
recently proposed in the framework of Bayesian inference [18]: when variation
is consistently present, the group mean only is not able to fully describe
individual node preferences. In some work, locality is exploited through a
definition of assortativity based on the correlation between two consecutive
nodes visited by a random walker. For instance, this rationale is used in
[19], and applied in the graph classification task; a multi-hop assortativity
is defined, here, as the probability that a randomly selected node and a
randomly selected $t$-hop neighbor belong to the same category, where $t$
indicates the time of the visit of the random walker. Closer to the current
work, a node-centric and Newman’s-normalized measure, namely Peel’s
assortativity [5], was recently proposed in the context of local-aware
homophily, modeling similarities between nodes as an autocorrelation of a
time-series defined as a sequence of node labels visited by a random walker
with restart.

##  3 Conformity

We aim to design a local proxy to measure the degree of homophilic
embeddedness of network nodes w.r.t. the attributes they carry. Such a task
has been recently approached by Peel et al. [5] to overcome the limitation of
classical approaches that usually propose a single aggregate score to
characterize the overall assortativity of network nodes. A multiscale strategy
to estimate the presence of homophilic patterns within a complex system
enables the discovery of emergent behaviors that classical indexes often are
not capable of unveiling. The score proposed in [5] moves from the classical
Newman’s assortativity [4] that, in turn, poses its ground on a
reinterpretation of the modularity score - a measure often used to quantify
the quality of network clustering partitions.

Modularity, $Q$, computes the difference between the observed and the expected
fraction of edges between nodes sharing similar attribute values: in the
assortativity coefficient, $r_{global}$, such quantity is normalized in the
range $-1\leq r_{global}\leq 1$. Thus: $r_{global}=1$ implies that all edges
only connect nodes labeled with the same value; $r_{global}=0$ that all edges
are randomly connected, and; hypothetically, $r_{global}=-1$ that all edges
only connect nodes with a different value. Formally,

$r_{global}=\frac{Q}{Q_{max}}=\frac{\sum_{g}{e_{gg}}-\sum_{g}{a^{2}_{g}}}{1-\sum_{g}{a^{2}_{g}}}$

where $e_{gg}$ is the proportion of edges connecting nodes of the same type
$g$, and $a_{g}=\sum_{i\in g}{k_{i}/2m}$ is the sum of degrees ($k_{i}$) of
nodes with type $g$.

Indeed, the approach in [5] yields valuable results; however, it misses a
fundamental high-order property of networks: the length of paths connecting
nodes. To address such an issue, we define a novel measure, namely
Conformity111Python code available at
https://github.com/GiulioRossetti/conformity.

Given an undirected attributed network $G=(V,E,A)$, where
$V=\\{v_{1},v_{2},\dots,v_{n}\\}$ is the set of nodes,
$E=\\{(v_{i},v_{j})|v_{i},v_{j}\in V\\}$ the set of edges among them, and
$A=\\{l_{1},l_{2},\dots,l_{n}\\}$ the set of node attributes, Conformity
computes the similarity between the attributes of the node $u\in V$ with the
ones of the other nodes of the network, weighing it with the distance among
them. Here, we will focus only on networks with nodes carrying categorical
attributes.

(a)

(b)

(c)

Figure 1: Toy Examples. (a-c) Node colors map categorical attribute values,
while node sizes encode the respective Conformity scores (the smaller the
size, the lower the score). (a) A scenario in which all nodes minimize the
Conformity score: all nodes have the same size, $\psi(u,\alpha)=-1$, since no
connection exists among pairs sharing the same color. (b) The effect of
distance on the $\psi(u,\alpha)$ value: the central node’s score approaches 1,
while moving toward the graph periphery (composed by nodes having different
color) nodes’ $\psi(u,\alpha)$ decreases – reaching negative values for the
extreme periphery. (c) Karate Club. Node colors encode the two factions of the
Karate Club dispute, node sizes are proportional to Conformity scores for
$\alpha=2.5$

To facilitate the introduction of Conformity we need to define a few support
functions.

Considering a node $u\in V$ we define the set $N_{u,d}$ as the set of $u$
neighboring nodes at a distance $d$:

$N_{u,d}=\\{v|dist(u,v)=d\\}.$ (1)

Moreover, lets call $I(u,v)$ the indicator function that compares the
attribute values of two nodes $u,v\in V$

$I_{u,v}=\left\\{\begin{array}[]{ll}1&\mbox{if }l_{u}=l_{v}\\\
-1&\mbox{otherwise}\end{array}\right.$ (2)

and $f_{u,l_{u}}$ the function that, if among the neighboring nodes of $u$
there is at least one node sharing the same attribute value $l_{u}$, computes
the ratio of $u$’s neighbors sharing it

$f_{u,l_{u}}=\frac{|\\{v|v\in\Gamma(u)\land l_{u}=l_{v}\\}|}{|\Gamma(u)|},$
(3)

where $\Gamma(u)$ is the first order neighborhood of node $u$, i.e., the set
of nodes adjacent to it. Moreover, to assure a consistent interpretation of
Conformity, we force $f_{u,l_{u}}$ to assume values in $(0,1]$ by setting its
value to 1 when its numerator nullifies.

Finally, we define the Conformity score for a node $u\in V$ and a given real
number $\alpha$ in $[0,+\infty)$ as:

$\psi(u,\alpha)=\frac{\sum_{d\in D}\frac{\sum_{v\in
N_{u,d}}I_{u,v}f_{v,l_{v}}}{|N_{u,d}|d^{\alpha}}}{\sum_{d\in D}d^{-\alpha}},$
(4)

where $D$ is $max(\\{dist(i,j)|i,j\in V\\})$, and the parameter $\alpha$
controls the level of interaction between nodes, which exponentially decreases
while the distances among nodes increase; thus, imposing $\alpha=1$, we force
a linear decrease w.r.t. the distance, while $\alpha>1$ imposes a sublinear
decrease which reduces the level of interaction between relatively distant
nodes.

Conformity can be algorithmically interpreted as follows.

  1. 1.

For each node pair $u,v\in V$, with $v\in N_{u,d}$ with $1\leq d\leq
max(\\{dist(i,j)|i,j\in V\\})$ the nodes attribute concordance – given by
$I(u,v)$ – is weighted by $f_{v,l_{v}}$, namely the degree of homophily of the
node $v$ toward its first order neighborhood;

  2. 2.

The average of such score aggregated over all the nodes in $N_{u,d}$ is then
damped by a factor $d^{\alpha}$, to account for the distance that separates
the nodes considered by the source $u$. Note that we used an inverse power-law
distance decay – that recalls well-known physical measures such as the
Coulombic and gravitational ones – since such an approach has already proven
its consistency in the definition of the clumpiness measure [6], a widely used
degree dispersion index.

  3. 3.

Finally, the computed score is normalized to ensure that Conformity lies in
the range $[-1,1]$.

Intuitively, the value of $\psi(u,\alpha)$ is maximized when a node $u$ is
surrounded by neighbors having the same attribute value, minimized in the
opposite scenario. Fig. 1(a) shows a network whose nodes (colored by their
attribute value) always minimize their Conformity value independently from the
chosen decay exponent. Such a limit case example perfectly captures the
essence of anti-conformity: edges always connect nodes with a different
attribute value, resulting in the absence of homophilic islands. Conversely,
Fig. 1(b) shows a simple scenario where the length of the paths among nodes
sharing different labels plays a crucial role in the Conformity values. We can
easily observe how Conformity (coded with the relative node size) tends to
decrease moving from the inner layer to the outer ones – e.g., moving from the
more homophilic embedded nodes to the more heterophilic ones.

As discussed, Conformity is a node-related measure: we can define the overall
degree of Conformity of a network as:

$\Psi(\alpha)=\frac{1}{|V|}\sum_{u\in V}\psi(u,\alpha).$ (5)

Indeed, such average score is only able to capture a general trend, not to
provide a clear picture of the emergent homophilic behaviors at a local level.

To better understand the information that the proposed measure can unveil, let
us consider the classic example offered by Karate Club dataset [20],
representing the small social network of a club after a conflict arose between
the administrator, “John A.", and an instructor, ‘Mr. Hi". The graph is
classically used as a toy example for characterizing community discovery
algorithms since it is neatly divided into two factions and very suitable for
explaining a clustering methodology. Moreover, since each node is labeled with
the club it belongs (“John A." or “Mr. Hi"), this external information is
commonly exploited as a ground truth to test the goodness of the algorithm
outputs, even if it has been shown not to be a proper approach [21]. In Fig. 1
(c), different colors encode the two categorical node attribute values
characterizing the network while, as in the previous example, the node sizes
are proportional to the node Conformity score ($\alpha=2.5$). As we expected,
the highest Conformity values are assigned to those nodes that prevalently
connect to same attributed peers while, on the other hand, the lowest ones
characterize bridge-nodes. Particular attention must be paid to node 8, which
registers the lowest Conformity score ($\simeq$-0.18). Indeed, the data paper
that discusses the origin of the Karate Club network dataset [20] help us in
providing a neat justification for such Conformity value: node 8 identifies a
weak supporter of “Mr. Hi", that joined with the “John A."’s faction, after
the split, for personal advantage, so he represents a bridge between the two
opposite sides of the Karate Club dispute indeed.

Figure 2: Peel’s quintet toy example. KDE’s distributions of several local
mixing patterns according to Conformity, for different values of $\alpha$: the
higher the value, the less the contribution of distant nodes to the target
final score – as shown by the progressive amplification of the distributions
toward close-to-bound values.

##  4 Experimental analysis

Studying the homophilic patterns of actors embedded in a network is a way to
unveil emergent behaviors that are otherwise hard to identify. In this
section, we propose a characterization of both synthetic and real-world
networks using the proposed Conformity score.

(a)

(b)

(c)

Figure 3: Copenhagen Network analysis. (a) Conformity analysis ($\alpha=2.5$)
in the SMS layer analysis; (b-c) Conformity analysis ($\alpha=2.5$) in the
proximity graphs of Monday and Saturday.

###  4.1 Synthetic data

Inspired by the Peel’s quintet [5], in Fig. 2 we replicate the building of a
set of five small synthetic graphs with the same number of nodes and edges (40
nodes – 20 red, 20 green – and 160 edges), but involving a rewiring of edges
leading to the emergence of different local mixing patterns that Newman’s
assortativity coefficient, $r$, is not able to detect (i.e., $r=0$). Indeed,
Newman’s score is a valid indicator only for the leftmost graph of the figure,
the only one where all edges are randomly rewired across all nodes. This is
showed by the unimodal distribution in the Conformity plot for (a). In
contrast, other plots reflect and capture the heterogeneous patterns obtained
by planting homophilic relations among nodes: in such scenarios, the unimodal
distribution breaks down into bimodal ones – e.g., the twin peaks observed for
the rightmost graph describe the most extreme case where exactly half the
nodes is perfectly homogeneous; in contrast, the other half is entirely
heterogeneous.

An aspect worth noticing is the effect played by the $\alpha$ parameter on the
$\psi$ values. As discussed, the $\alpha$ exponent allows tuning Conformity
sensitivity w.r.t. the distance among node pairs. For $\alpha=0$, all nodes
are perceived at the same distance from the source node, thus contributing
equally to its final score; for $\alpha>0$, the contribution of nodes is
weighted w.r.t. their distance, and progressively dumped while increasing such
value. The effect of increasing $\alpha$, as shown by the KDEs distributions
in Fig. 2, is to concentrate the actual contribution to low-distance
neighborhoods, thus favoring a polarization of the scores to the extreme
values of the domain. Indeed, there is no one-fits-all value for such
parameter: it needs to be fitted to the analytical needs and the underlying
network topology.

###  4.2 Real data

Copenhagen Network Study. We firstly consider a small real-world network,
namely the interaction data from Copenhagen Network Study [22]. It is composed
of different layers connecting a sample of 700 among male and female
university students for four weeks: we consider, here, the SMS layer and the
proximity estimated via Bluetooth signal strength. Since information about
node gender is available, we mainly aim to relate a characterization of the
network based on Conformity to some of the analysis already shown in the
original data paper, e.g., more frequent male-male interaction than male-
female and female-female ones [22]. Since the underlying network reflects
these frequencies, we describe homophily by gender leveraging Conformity,
trying to give more insights than the only number of exchanged messages. Fig.
3 shows that several male nodes are perfectly homophilic w.r.t. gender, but
also that there exist a few highly heterophilic ones among them. The same
(i.e., the same mixing pattern) is not true observing female node Conformity
distribution, even taking into account the fact that the two populations are
unbalanced. Considering the proximity layer, we show the graph analysis of two
days, namely Monday and Saturday. Fig. 3(b-c) underlines how different mixing
patterns arise considering different days of the week.

Facebook100. Facebook100 [23] is a collection of 100 Facebook friendships
networks among 100 U.S. colleges, built during the early history of the social
network. Nodes are labeled with several categorical attributes, profiling
people by gender, college year, dormitory…In the following, we will focus on
the first 50 networks ordered by size, considering two single-attributes
analyses - namely gender and college year - and a multi-attribute overview. Be
aware that the gender attribute yields three values, referring to male, female
and missing information; quoting the original data paper, we use a “missing"
label for situations in which individuals did not volunteer a particular
characteristic [23], namely that the individual itself does not specify his
gender.

Figure 4: Gender analysis ($\alpha=2.5$). The box-plot above compares male
(blue diamonds) and female (red diamonds) distributions of the analyzed
colleges, while the box-plot below compares male-and-female (purple diamonds)
and missing values (green diamonds) distributions. Three binned networks show
heterogeneity of distributions along the colleges.

Figure 5: A comparison between Conformity ($\alpha=2.5$) and Peel’s
assortativity in the three female colleges.

Gender. Fig. 4 shows gender assortativity of the 50 selected networks. In
general, we can not state a male/female tendency to homophily/heterophily as a
common behavior across all networks; even if it seems that females’ average
behavior is more assortative than males, this should be examined on a case-by-
case basis. Nevertheless, for the work, it is more interesting to focus on the
scoring of three specific networks, whose male and female homophilic behaviors
are different w.r.t. the other colleges.

They are Simmons, Smith and Wellesley, whose distributions are also
highlighted in Fig. 5, in view of a comparison with Peel’s assortativity [5]
222This other measure has also a parameter $\alpha\in[0,1]$, which is
integrated over all its possible values in the paper where it is defined and
presented [5]: we replicated the same approach for the comparison in the
current study.. First of all, referring to the analysis present in the
original data paper [23], they are three predominantly female colleges whose
Newman’s assortativity coefficient tends to 0. Leveraging Conformity, we can
observe (Fig. 4) how i) the few male nodes connect disassortatively by gender
(i.e., form ties only with females), inducing the emergence of two extreme and
distinct mixing, and meanwhile ii) we observe some differences with Peel’s
assortativity, where the same overall strong assortative behavior of the
networks is not maintained (Fig. 5). Apparently, the extreme disassortative
behavior of few nodes should not so strongly affect the entire network mixing.
Since a real comparison between the two measures is not possible i) due to the
absence of ground truth, but mostly because ii) they capture different aspects
of mixing, our interpretation is that the local assortativity variant we face
suffers from the same limits about network constraints impacting on the
reaching of the whole measure range, as already studied in [24].

Also, the presence of missing values has a non trivial effect on the resulting
Conformity distribution. The ability to discriminate noisy information from
sensible one is important while analyzing a complex system. Since nodes with
missing information are homogeneously distributed within the network tissue,
Conformity can correctly classify them as noise, as shown in the labeled vs.
missing box-plot of Fig. 4. This observation simply implies that these nodes
can not induce to homophilic behaviors since missing information is not a real
social dimension implying assortative attitudes.

Figure 6: Year analysis ($\alpha=2.5$). The box-plot compares the first year
(red diamonds) and other years (green diamonds) distributions of the selected
colleges. Three networks are selected, where also a distinction between first
and second year students is highlighted.

Year. Fig. 6 shows year assortativity of the 50 selected networks. As already
shown in [5], first year students highly contribute to the homophilic behavior
of the attribute, even when the network attitude does not tend to be globally
assortative (see Haverford in Fig. 6). According to the original data paper
[23], the year attribute is the most assortative in terms of Newman’s
coefficient. Also, in this case, a node-centric measure tends to discover
different mixing pattern and allows to differentiate the values that show high
homogeneity from the ones that prefer a heterogeneous neighborhood; the three
binned networks in Fig. 6 also suggest that homophilic behavior tends to
decrease with the increase of enrolment years in a coherent way with the
ordinal nature of the attribute.

Multi-attribute. In a multi-attribute scenario, we want to measure homophily
among complex node profile composed by multiple independent fields. Fig. 7
focuses on dorm-gender and dorm-year assortativity of two selected networks.
Smith college, as Wellesley, shows a consistent difference between male-female
distributions when the only gender attribute is considered, while no
substantial differences are highlighted when the only dormitory attribute is
analyzed. However, male nodes tend to be more assortative than female ones
when the two attributes are measured together, allowing us to provide a more
reliable description of the social media friendships mirroring college
interactions. Like all other colleges, first year students are highly
assortative w.r.t. the other years, while the same pattern does not emerge
considering the dormitory attribute. However, such a pattern emerges anew when
dormitory and years are analyzed in a multi-attribute scenario.

Figure 7: Multi-attribute ($\alpha=2.5$). Dorm-gender and dorm-year analysis
of Smith and Bucknell colleges: respectively, male-female and first year vs.
other years differences are highlighted in the distributions.

##  5 Discussion and future work

This work introduced Conformity, a novel strategy to measure the homophilic
mixing of network nodes w.r.t. their categorical attributes. The proposed
measure aims to address some limitations of the well-known assortativity
coefficient, in its classic definition given by Newman’s work [4]. The main
reason behind Conformity is the need to take into account (the often
neglected) impact of node distance on the homophilic/heterophilic behaviors
that, in social contexts, favor the creation of social ties. As shown, the
proposed measure can unveil interesting nodes’ behaviors and can, in practice,
be fruitfully adapted to support several tasks (e.g., the
identification/measuring of echo-chambers or polarized islands among users
living in a social media ecosystem).

In particular, the multi-attribute analysis it enables can support fine
grained analysis of complex homophilic patterns to uncover, for instance,
homogeneous nuclei among individuals w.r.t. their age and political views,
thus supporting tasks such as attributed community discovery [25]. Moreover,
Conformity ability to characterize different extreme behavior of even handfuls
of nodes (as seen both in homophily by gender analysis of colleges as Smith
and Wellesley and in noise isolation when in the presence of missing values)
is a promising feature that can support a wide set of network related task as,
for instance, graph-based anomaly detection.

As future works, since in the current study we focused only on networks
encoding categorical attributes, we plan to extend Conformity to handle scalar
attributes. We also plan to propose an approximate version of Conformity to
lower its computational complexity and to study its effectiveness as support
for network analysis tasks in heterogeneous applicative scenarios.

### Acknowledgments

This work is supported by the scheme ’INFRAIA-01-2018-2019: Research and
Innovation action’, Grant Agreement n. 871042 ’SoBigData++: European
Integrated Infrastructure for Social Mining and Big Data Analytics’.

## References

  * [1] R. Interdonato, M. Atzmueller, S. Gaito, R. Kanawati, C. Largeron, and A. Sala, “Feature-rich networks: going beyond complex network topologies,” Applied Network Science, vol. 4, p. 4, Jan 2019.
  * [2] A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” science, vol. 286, no. 5439, pp. 509–512, 1999.
  * [3] S. Fortunato and D. Hric, “Community detection in networks: A user guide,” Physics reports, vol. 659, pp. 1–44, 2016.
  * [4] M. E. Newman, “Mixing patterns in networks,” Physical Review E, 2003.
  * [5] L. Peel, J.-C. Delvenne, and R. Lambiotte, “Multiscale mixing patterns in networks,” Proceedings of the National Academy of Sciences, 2018.
  * [6] E. Estrada, N. Hatano, and A. Gutierrez, “‘clumpiness’ mixing in complex networks,” Journal of Statistical Mechanics: Theory and Experiment, 2008\.
  * [7] M. McPherson, L. Smith-Lovin, and J. M. Cook, “Birds of a feather: Homophily in social networks,” Annual review of sociology, 2001.
  * [8] J. Moody, “Race, school integration, and friendship segregation in america,” American journal of Sociology, vol. 107, no. 3, pp. 679–716, 2001.
  * [9] W. Shrum, N. H. Cheek Jr, and S. MacD, “Friendship in school: Gender and racial homophily,” Sociology of Education, pp. 227–239, 1988.
  * [10] S. Feng and A. Kirkley, “Mixing patterns in interdisciplinary co-authorship networks at multiple scales,” Scientific Reports, vol. 10, no. 1, pp. 1–11, 2020.
  * [11] R. Rabbany, D. Eswaran, A. W. Dubrawski, and C. Faloutsos, “Beyond assortativity: proclivity index for attributed networks (p ro n e),” in Pacific-Asia Conference on Knowledge Discovery and Data Mining, Springer, 2017\.
  * [12] K. Pelechrinis and D. Wei, “Va-index: Quantifying assortativity patterns in networks with multidimensional nodal attributes,” PloS one, vol. 11, no. 1, p. e0146188, 2016.
  * [13] R. Noldus and P. Van Mieghem, “Assortativity in complex networks,” Journal of Complex Networks, vol. 3, no. 4, pp. 507–542, 2015.
  * [14] A. Allen-Perkins, J. M. Pastor, and E. Estrada, “Two-walks degree assortativity in graphs and networks,” Applied Mathematics and Computation, vol. 311, pp. 262–271, 2017.
  * [15] S.-C. Ngo, A. G. Percus, K. Burghardt, and K. Lerman, “The transsortative structure of networks,” Proceedings of the Royal Society A, vol. 476, no. 2237, p. 20190772, 2020.
  * [16] E. Lee, F. Karimi, C. Wagner, H.-H. Jo, M. Strohmaier, and M. Galesic, “Homophily and minority size explain perception biases in social networks,” arXiv preprint arXiv:1710.08601, 2017.
  * [17] K. M. Altenburger and J. Ugander, “Monophily in social networks introduces similarity among friends-of-friends,” Nature human behaviour, vol. 2, no. 4, pp. 284–290, 2018.
  * [18] G. T. Cantwell and M. Newman, “Mixing patterns and individual differences in networks,” Physical Review E, vol. 99, no. 4, p. 042306, 2019.
  * [19] L. Gutiérrez-Gómez and J.-C. Delvenne, “Multi-hop assortativities for network classification,” Journal of Complex Networks, vol. 7, no. 4, pp. 603–622, 2019.
  * [20] W. W. Zachary, “An information flow model for conflict and fission in small groups,” Journal of anthropological research, 1977.
  * [21] L. Peel, D. B. Larremore, and A. Clauset, “The ground truth about metadata and community detection in networks,” Science advances, vol. 3, no. 5, p. e1602548, 2017.
  * [22] P. Sapiezynski, A. Stopczynski, D. D. Lassen, and S. Lehmann, “Interaction data from the copenhagen networks study,” Scientific Data, vol. 6, no. 1, pp. 1–10, 2019.
  * [23] A. L. Traud, P. J. Mucha, and M. A. Porter, “Social structure of facebook networks,” CoRR, vol. abs/1102.2166, 2011.
  * [24] M. Cinelli, L. Peel, A. Iovanella, and J.-C. Delvenne, “Network constraints on the mixing patterns of binary node metadata,” arXiv preprint arXiv:1908.04588, 2019.
  * [25] S. Citraro and G. Rossetti, “Identifying and exploiting homogeneous communities in labeled networks,” Applied Network Science, vol. 5, no. 1, pp. 1–20, 2020.

### Authors

Giulio Rossetti is a permanent researcher at the Information Science and
Technology Institute of the Italian National Research Council (ISTI-CNR).
Giulio holds a PhD in Computer Science from the University of Pisa (2015).
Since 2011, he has been performing research in the fields of complex network
analysis and data science as a member of the Knowledge Discovery and Data
Mining laboratory. His recent work focuses on the modeling and study of
dynamics of and on networks and on the definition of data-driven models for
the forecast of rare events. He is the main contributor of several open-source
software applications (https://github.com/GiulioRossetti), some of which have
been developed to support big data analysis carried out in a series of EU
projects.

Salvatore Citraro is a PhD student in Computer Science at the University of
Pisa and a member of the Knowledge Discovery and Data Mining Laboratory (KDD-
Lab), a joint research group with the Information Science and Technology
Institute of the Italian National Research Council in Pisa. Currently, his
main research interests focus on complex networks, including classic and
feature-rich network data analysis, with a focus on attribute-aware community
discovery tasks. His PhD line of research will also include the study of
linguistic networks and how their hidden structures and properties can be
meaningfully exploited and applied in cognitive contexts.

Letizia Milli received in 2018 the PhD in Computer Science from the University
of Pisa with a thesis on the study of spreading phenomena over complex
networks. She is a post doc researcher in Computer Science at the University
of Pisa and a member of the Knowledge Discovery and Data Mining Laboratory
(KDD-Lab), a joint research group with the Information Science and Technology
Institute of the Italian National Research Council in Pisa. Her research
interests include data mining, quantification, diffusion of phenomena, and
innovation in complex networks and the Science of Success.