# Community Detection from Location-Tagged Networks

Zhi Liu  Yan Huang

Department of Computer Science and Engineering  University of North Texas,
Denton, Texas<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Many real world systems or web services can be represented as a network such
as social networks and transportation networks. In the past decade, many
algorithms have been developed to detect the communities in a network using
connections between nodes. However in many real world networks, the locations
of nodes have great influence on the community structure. For example, in a
social network, more connections are established between geographically
proximate users. The impact of locations on community has not been fully
investigated by the research literature. In this paper, we propose a community
detection method which takes locations of nodes into consideration. The goal
is to detect communities with both geographic proximity and network closeness.
We analyze the distribution of the distances between connected and unconnected
nodes to measure the influence of location on the network structure on two
real location-tagged social networks. We propose a method to determine if a
location-based community detection method is suitable for a given network. We
propose a new community detection algorithm that pushes the location
information into the community detection. We test our proposed method on both
synthetic data and real world network datasets. The results show that the
communities detected by our method distribute in a smaller area compared with
the traditional methods and have the similar or higher tightness on network
connections.

###### keywords:

Community Detection, Geo-tagged Network, Connection Locality

††terms: Algorithm

##  1 Introduction

Many real world systems or web services can be represented as a network such
as social networks, transportation networks, the World Wide Web, and
biological networks. Detecting communities from those networks has received
considerable attention and is the main focus of many research efforts in the
past decade [3, 12, 5, 4]. Generally, the goal of community detection is to
find the subgraphs with tight internal connection based on node connections,
labels of nodes, and the weights derived from data or network structure. Nodes
in the same community are closer to each other. Therefore, in the real world,
a community represents a group of nodes sharing some similar common friends or
features.

However, the formation of many real world networks is greatly influenced by
the geographic locations of the nodes which has not been fully investigated by
the currently literature. For example, in a social network, people have a high
probability to build a connection with his/her colleague or schoolmate because
they know each other or in most cases, they became friends because they are
geographically close. Furthermore, some network applications, such as
FourSquare, are mostly location-based social networks. The geographic location
will play even more importance in the social network structure in these
platforms. There are preliminary studies on the relationship between social
network structure and geographic distance [16] and [13]. However, those
studies do not push location information into community detection.

We observe that the nodes in a tightly connected community tend to be more
close to each other in space as well. Location can have different impact on
social networks and the impact can be quantified and used in community
detection. Introducing locations of nodes to community detection can improve
the performance of detection on real world networks. In this paper, we propose
community detection methods that take the locations of the nodes into
consideration with the main goal of improving the quality of the detection
results in terms of average internal degree, accuracy, and geographic span of
detected communities. Our research is based on the following two premises: (1)
Location is an important factor and can greatly influence the connection
establishment in many location-tagged networks; (2) For many applications,
detecting communities with constrained geographic distribution is important.
For example, finding local communities will be useful for arranging meetups of
communities with similar interests. Knowing geographically constrained
communities with potential interests in certain concert or talk shows can help
arranging and scheduling the tours.

Figure 1: Two different divisions of a small location-tagged network. The left
division is only based on the network structure and the right one takes the
locations of the nodes into account.

We focus on finding communities with nodes distributing in a small range of
area and at the same time, keeping the connection tightness of the nodes in
the community. Figure 1 gives an example of how the geographic location of
nodes can influence the detecting results. In this case, we set the number of
communities to two. If we only consider the network structure, the left one is
a good result. There are only two edges coming across communities. After we
introduce the location of the nodes, we will have two communities as in the
right side. There are still only two connections across communities however
the geographic spans of the two communities are much smaller than the left
one. Unfortunately, in some networks, we may need to make a tradeoff on the
structure tightness for keeping the nodes in the same community close. This
paper presents a way to measure the locality and node similarity and gives an
guidance on if a given network has locality in communities.

This paper makes the following contributions:

  * •

This is the first effort to detect communities with locality on large
location-tagged networks;

  * •

Given a location-tagged network, we proposed a new measurement called Total
Variation Difference to help determine if the network has a locality property
and a location-based community detection method is suitable. We introduce two
concepts: connection locality to measure the closeness of two nodes and node
similarity to measure the “importance” of an edge. Using these two concepts,
we propose a new community detection algorithm that pushes the location
information into the community detection;

  * •

We propose optimization techniques and indexing method to allow the algorithm
to scale well for large networks. It took around 30 seconds to detect
communities from a real network of 20,000 nodes;

  * •

We test our proposed method on both synthetic data and real world network
datasets. The results show that the communities detected by our method
distribute in a smaller area compared with the traditional methods and have
the similar or higher tightness on network connections.

The rest of the paper are organized as the following. Section 2 reviews the
related work. We describe the relationship between geographic location and the
network structure; and propose our algorithm in section 3. We also discuss
optimization and indexing methods in this section. In section 4, we conduct
experiments on both synthetic data and real world dataset. And then we give
the conclusion in section 5.

##  2 Related Work

Community detection: In the past decade, many algorithms have been developed
to detect communities in a network. For complete discussion of various
algorithms, please refer to [5] and [4].

We only describe the most relevant work here. Aaron et al. provide a
hierarchical clustering approach to detect communities using internal density
in [3]. The internal density is the number of edges inside a community in a
network. The basic idea is to increase the ratio of the edges in communities
during the hierarchical clustering process using Equation 1:

$Q=\dfrac{1}{2m}\sum_{vw}[A_{vw}-\dfrac{k_{v}k_{w}}{2m}]\delta(c_{v},c_{w})\vspace{-2ex}$
(1)

where $A_{vw}$ is the adjacency matrix of the network and $k_{v}$ is the
degree of node $v$. $c_{v}$ represents the community of node $v$ and
$\delta(c_{v},c_{w})$ is 1 if $c_{v}=c_{w}$. $m$ is the number of edges in the
whole network $G$.

So the value $Q$ will be large when more edges are inside a community, which
represents a good divisions of the work. To avoid the problem that the largest
$Q$ value 1 will only happen when all nodes belong to the same community, the
authors introduce the component ${k_{v}k_{w}}/{2m}$ in the modularity of $Q$.
${k_{v}k_{w}}/{2m}$ is the probability of an edge existing between nodes $v$
and $w$ if edges were randomly placed. So $Q$ will be close to zero when the
network is randomly generated without community structure. Some other work is
also based on modularity optimization such as [1], [15], and [10].

Another popular algorithm [12] is based on iteratively removing “unimportant”
edges. The basic assumption of this method is that communities are weakly
connected by a few edges. The importance of an edge, called betweenness score,
is the number of shortest paths that go through that edge. The paths between
different communities must go through an edge across communities so the edges
across communities will get a higher betweenness score. The edge with the
highest score will be removed from the network iteratively.

In [8], the authors define the similarity between nodes using their degrees
and the number of common neighborhood. The sum of the similarities of edges
inside or outside a community was defined as internal or external similarity
of a community.

These works do not consider locations of nodes in a network.

(a) Twitter: the total variation distance is $0.315$ and the inflection
distance is $4180km$

(b) Gowalla: the total variation distance is $0.533$ and the inflection
distance is $580km$

Figure 2: The cumulative distribution function of distance between every user
pair/friend pair on Twitter and Gowalla.

Geography and networks: In the last few years, some researchers have studied
the geographic constraints on real world networks. In [13], the authors build
a network based on the cell phone communication records. Then they study the
relationship between distance and the call/text tie probability. By dividing
the network into communities[14, 6, 11, 7], the authors show that the
geographic span of real world community is much smaller than the null
community especially when the community has less than 30 people. In [17], the
authors define the concepts of node locality and geographic clustering
coefficient. Then they show the value distribution of these two coefficients
with respect to the degree of nodes. The node locality is slowly decreasing
with node degree increasing. Their study shows that people tend to build
connections with other nearby users. Some users have social connections only
with others within a close geographic distance.

The most relevant work to ours is proposed in [19]. Yves et. al. propose a
geosocial communities detection method. The authors assign each edge with a
similarity score using social relationship and the Euclidean distance between
their average stop locations and then run the spectral clustering algorithm.

However, the authors only built their model on a small scale application and
didn’t provide evidence on how the social relation is influenced by the
geographic location, which is important for using geographic information in
community detection in location-tagged networks. In addition, the efficiency
of the spectral clustering algorithm may be the main bottleneck when dealing
with a large dataset. In this paper, we push the location information of nodes
in networks into the community detecting algorithm and design an efficient
algorithm that can scale to large networks.

##  3 The Algorithm

We denote the network as $G=(N,E,L)$, where $N$ is the set of nodes, $E$ is
the edge set, and $L$ is the location set of the nodes. To determine whether
the locations of nodes will help in community detection, we will analyze the
locality of the network first. Then we propose our locality-based method. We
follow the hierarchical clustering framework combined with the location
information. A good division of the network produces communities with higher
ratio of internal edges and smaller geographical scope.

###  3.1 Network Locality

As we discussed before, the formation of connections in many real world
networks are influenced by the location of nodes in the network. However, some
networks are more location influenced than others. So before we provide the
location-based community detection algorithm, we need to analyze the influence
of the location on networks to see the degree of influence. This will be
helpful in determining if location based community detection is a suitable
method. Here, we use network locality defined below to measure the
relationship between location and connection in a network.

######  Definition 1 (Network Locality)

In a network $G$, we use two indexes to measure its locality: Total Variation
Difference (TVD) and the Inflection Distance. Let $F(dis)$ be the cumulative
distribution function (CDF) of distance between any two nodes in $G$ and
$F_{c}(dis)$ be the CDF of the distance between connected nodes in $G$, the
total variation distance is defined as:

$TVD(F,F_{c})=max(F_{c}(dis)-F(dis))$ (2)

and the Inflection distance is defined as the distance where
$F_{c}(dis)-F(dis)$ achieves the maximum value.

From the definition, we can see that a higher value of the total variation
distance indicates the network is more geographically close because connected
nodes in nearby locations have higher percentages. When the total variation
difference is close to zero, the connection has little relationship with the
locations of nodes. When the $TVD$ is less than zero, the connection has
negative correlation with location. It is obvious that a small value of
inflection distance represents a more geographic close network.

We analyze the network locality of two real datasets: Gowalla and Twitter.
Gowalla is a location-based social network and users are able to check in at
“spots” in their local vicinity. The Gowalla dataset [2] is a 196,591 users’
friendship network. The check-in data were collected from February 2009 to
October 2010 and each user has 32.8 check-in records on average. We use 99,563
of those users who have check-in records in our analysis. Since there is no
user profile, we take the center of the $25km\times 25km$ area with the most
number of check-ins as the user home location [18]. We also collected user
profiles from Twitter, an on-line social networking and micro blogging service
which allows users to follow each other; post and read “tweets”. The data are
collected from April 14 to April 28, 2013. The social network comes from [20].
There are 660,000 distinct user IDs in total together with their social
relations. We obtained locations of 148,860 users through their profiles. We
define the friend relation in the same way as [9], i.e. users $i$ and $j$ has
friend relation if they follow each other.

In Figure 2, we plot the cumulative distribution function of distance between
every user pairs and friend pairs. In the Twitter dataset, the total variation
distance is $0.315$ and the inflection distance is $4,180km$. That means that
the percentage of connected edges with the distance less than $4,180km$ in all
the connected edges is higher than that percentage of random user pairs by
$0.315$. Compared with Twitter, the Gowalla network is more close
geographically since it has a higher $TVD$, $0.533$, and a smaller inflection
distance $580km$. This phenomenon illustrates that users in Gowalla tend to
build friend relations with others who are geographically close to them
compared with Twitter. In other words, the locations of nodes have greater
influence on the network structure in Gowalla. Our experiment later also show
that our method can perform better on Gowalla than Twitter network for this
reason.

In practice, the total variation difference is more helpful to measure how the
network structure is influenced by location. We suggest applying our method on
the networks with the total variation difference larger than $0.25$.

###  3.2 Connection Locality

To take location into account in community detection, first we define the
concept of connection locality to qualify the graphic closeness between nodes.

######  Definition 2 (Connection Locality)

Let $dis_{vw}$ be the geographic distance between nodes $v$ and $w$. Let
$\sigma$ be the average distance between all user pairs. The connection
locality can be defined as:

$L_{vw}=exp(-dis_{vw}/\sigma)$ (3)

So connection locality will achieve a high value when the two nodes are close.
Since our goal is to detect communities with both geographic closeness and
network tightness, we measure the geographic and network closeness of the
communities using the following equation:

$C_{G}=\dfrac{1}{\sum_{vw}A_{vw}L_{vw}}\sum_{vw}A_{vw}L_{vw}\delta(c_{v},c_{w})\vspace{-1ex}$
(4)

We can see that this method is equivalent to assign each edge in network $G$
with the locality as weight. Inspired by the method in [3], we introduce the
expected value of $C_{G}$ to avoid the situation that the largest value of
$C_{G}$ will be achieved when all the nodes belong to the same community.

Figure 3: In this example, each dashed circle represents a community. The
solid lines are connections between nodes.

The expected value of $C_{G}$ is obtained from a random connection network.
For a given network $G$, the location of the nodes and their degrees are
fixed. In a random connection network, the probability of an edge existing
between a node pair is $k_{v}k_{w}/2m$. Since we already know the locations of
the nodes, the community locality $l_{vw}$ between a node pair $v$ and $w$ is
also known. So the expect value for each edge is $l_{vw}k_{v}k_{w}/2m$ and the
expect value of $C_{G}$ is the sum of the expect value of all the edges:

$P_{G}=\dfrac{1}{\sum_{vw}A_{vw}L_{vw}}\sum_{vw}\dfrac{k_{v}k_{w}}{2m}L_{vw}\delta(c_{v},c_{w})\vspace{-1ex}$
(5)

In Figure 3, there are three communities denoted by the dashed circles. The
solid lines are the edges in the network. We use dashed lines to complement
each community as a complete graph. Given the locations of all nodes, the
community localities can be easily calculated. The probability of an edge
existing between the bottom two nodes in the left community is $\frac{2\times
2}{13}$.

Let $\omega=\sum_{vw}A_{vw}L_{vw}$, we define the modularity Q as:

$Q=\dfrac{1}{\omega}\sum_{vw}[A_{vw}L_{vw}-\dfrac{k_{v}k_{w}}{2m}L_{vw}]\delta(c_{v},c_{w})\vspace{-1ex}$
(6)

The community locality between each node pair is fixed. If the network is not
built based on locations, community locality will have no influence on $Q$ and
the value of the modularity $Q$ will be close to zero. When the network has a
good divisions, which means the communities are close on both geographic
distance and network structure, the modularity $Q$ will achieve a higher
value.

###  3.3 Node Similarity

In this section, we will discuss how to enhance the influence of network
structure in the detection process. Here we define the node similarity between
nodes pair by the common neighbors and their degrees:

######  Definition 3 (Node Similarity)

Let $\Gamma_{v}$ be the set of neighbors of vertex $v$. The similarity of two
nodes is calculated by their common neighbors and their degrees as:

$S_{vw}=\dfrac{|\Gamma_{v}\cap\Gamma_{w}|}{\sqrt{|\Gamma_{v}||\Gamma_{w}|}}$
(7)

(a) 1-degree node pairs

(b) 1- and 2-degree node pairs

Figure 4: The average geographic distance under different values of node
similarity.

First we study the relationship between node similarity and the geographic
distance between node pairs in real world networks. From Figure 4(a) we can
see that with the increasing of the value of node similarity, the average
geographic distance has a significant decrease. Then we extend the
investigation of node similarity to all 1- and 2-degree friend pairs. From
Figure 4(b) we can see a similar tendency between node similarity and average
geographic distance as that on 1-degree friends. But the average distances are
much longer than the 1-degree friends especially on the Gowalla data set.

To apply the node similarity in our modularity, we also need to calculate the
expect value under random connection network. In the random case, when we
calculate the expect value of $S_{vw}$, we need to know the probability of an
edge existing between node $v$ or $w$ and any other node $i$. Assuming node
$i$ has $k_{i}$ neighbors, the probability of node $i$ is connected to $v$
($w$) is $k_{v}k_{i}/2m$ ($k_{w}k_{i}/2m$). Since the probability of
connection is independent, so the probability of node $i$ connected to both
$v$ and $w$ is $\frac{k_{v}k_{i}}{2m}\frac{k_{w}k_{i}}{2m}$. The expected
value of $S_{vw}$ is the sum of the probabilities of both $v$ and $w$
connected to any other node $i$:

$\begin{split}S_{vw}&=\dfrac{|\Gamma_{v}\cap\Gamma_{w}|}{\sqrt{|\Gamma_{v}||\Gamma_{w}|}}\\\
&=\sum_{i\neq v\&i\neq w}(k_{v}k_{i}/2m)(k_{w}k_{i}/2m)/\sqrt{k_{v}k_{w}}\\\
&=\sqrt{k_{v}k_{w}}\sum_{i\neq v\&i\neq w}k_{i}^{2}/4m^{2}\\\ \end{split}$ (8)

In practice, we use $\tau=\sum_{i}k_{i}^{2}/4m^{2}$ instead of $\sum_{i\neq
v\&i\neq w}k_{i}^{2}/4m^{2}$ because they have similar value on larger
networks.

We then revise $\omega$ as $\sum_{vw}A_{vw}S_{vw}L_{vw}$, and the new
modularity $Q^{s}$ is defined as:

$Q^{s}=\dfrac{1}{2\omega}\sum_{vw}[A_{vw}S_{vw}L_{vw}-L(v,w)\dfrac{k_{v}k_{w}}{2m}\tau\sqrt{k_{v}k_{w}}]\delta(c_{v},c_{w})\vspace{-2ex}$
(9)

In this paper, we only consider the node similarity between connected nodes
for the following reasons: (1) Relation of 2-degree neighbors (the node pairs
which are connected but share at least one common neighbors) introduce many
new connections. The number of 2-degree neighbors is much more than directly
connected neighbors and will significantly increase the computation
complexity. (2) The influence of 2-degree neighbors is much smaller than
directly connected ones. Based on our investigation, the average distance
between 2-degree neighbors are three to times times longer than directly
connected neighbors even when they have the same node similarity.

###  3.4 Optimization and Complexity

In this section, we will discuss how to implement the algorithm efficiently
with optimization and indexing. The algorithm is based on the hierarchical
clustering method with greedy strategy. At first, each node is a community. In
each step, two communities whose combination increases the value of the
modularity $Q$ most are combined. In [3], the authors provide an efficient
method to implement their model. They maintain and update a matrix $\Delta
Q_{ij}$ which records the change of $Q$ after combing the communities $i$ and
$j$. When Equation 6 is used as $Q$ value, we can implement the model in a
similar way. When Equation 9 is used as the modularity, we discuss the
optimization here.

$\begin{split}Q&=\dfrac{1}{2\omega}\sum_{vw}A_{vw}S_{vw}L_{vw}\delta(c_{v},c_{w})\\\
&-\dfrac{1}{2\omega}\sum_{vw}L(v,w)\dfrac{k_{v}k_{w}}{2m}\tau\sqrt{k_{v}k_{w}}\delta(c_{v},c_{w})\\\
\end{split}$ (10)

We can rewrite the modularity in Equation 9 into Equation 10. By analyzing the
modularity, we can see that after we combine two communities $i$ and $j$, the
change of $Q^{s}$ includes two parts: 1) the connections between these two
communities will increase the value of $Q^{s}$ (the first part in Equation
10), the value equals to:

$\Delta
Q_{1}=\dfrac{1}{2\omega}\sum_{vw}A_{vw}S_{vw}L_{vw}\delta(c_{v},i)\delta(c_{w},j)$
(11)

and 2) the value generated by node pairs from communities $i$ and $j$ and this
value equals to:

$\Delta
Q_{2}=-\dfrac{1}{2\omega}\sum_{vw}L(v,w)\dfrac{k_{v}k_{w}}{2m}\tau\sqrt{k_{v}k_{w}}\delta(c_{v},i)\delta(c_{w},j)$
(12)

So the $\Delta Q_{ij}$ equals to $\Delta Q_{1}+\Delta Q_{2}$. Since we will
combine two communities with the largest $\Delta Q_{ij}$, we only need to keep
values in Equations 11 and 12. Now we only need to solve two problems, how to
initialize the $\Delta Q_{ij}$ and how to update it after we combine two
communities.

The combination of two disconnected communities will not increase the value of
$Q$, so we only keep the $\Delta Q_{ij}$ if there is at least one edge between
them. At first, every node is a community and the $\Delta Q$ between each
connected node pair is:

$L_{ij}[\dfrac{S_{ij}}{2\omega}-\dfrac{\tau(k_{i}k_{j})^{1.5}}{4\omega m}]$
(13)

After we combine communities $i$ and $j$, we need to update all the
communities $k$ which are connected to $i$ or $j$. We use $(ij)$ to denote the
community generated by combining $i$ and $j$ and use $\Delta Q_{k,(ij)}$ to
denote the new $\Delta Q$ value between $k$ and $(ij)$. If the community $k$
is connected to both $i$ and $j$, we can get the new $\Delta Q_{k,(ij)}$ by
$\Delta Q_{ik}+\Delta Q_{jk}$. If $k$ is only connected to one of them, e.g.
$i$, we do not have $Q_{jk}$ since they are disconnected. So we need to
calculate it. We have already known that $\Delta Q$ is the sum of Equation 11
and 12. The $\Delta Q_{1}$ will be zero since there is no edge between $j$ and
$k$. So we can have the $\Delta Q_{jk}$ as:

$\Delta Q_{jk}=-\dfrac{1}{2\omega}\sum_{vw}\tau
L(v,w)\dfrac{(k_{v}k_{w})^{1.5}}{2m}\delta(c_{v},j)\delta(c_{w},k)$ (14)

And then we can update the $\Delta Q_{k,(ij)}$ by:

$\Delta Q_{k,(ij)}=\Delta Q_{ik}+\Delta Q_{jk}$ (15)

1: Input: Network $G=(N,E,l)$

2: Output: Communities in $G$

3: Assign each node a community label from 1 to n

4: Initialize the $\Delta Q_{ij}$ as Eq.13

5: Find the maximum $\Delta Q_{ij}$, $max\Delta Q$

6: while $max\Delta Q$ > 0 do

7: Update $\Delta Q_{k,(ij)}$ of all the communities $k$ connect to $i$ or $j$
by Eq.14 and Eq.15

8: Update the community label in community $i$ as $j$

9: end while

10: Return node list with the community label

Algorithm 1 Detecting communities from location-tagged network

The Algorithm 1 describes the frame work of all the process. We will stop the
hierarchical clustering process when the modularity $Q$ achieve its maximum
value, which means that the largest $\Delta Q_{ij}$ is less than zero.

We store each row of the $\Delta Q_{ij}$ and the node list in different
communities in a balanced binary trees. When we update a $\Delta Q_{k,(ij)}$,
the worst case is that we need to calculate the $\Delta Q_{jk}$ by Equation 14
and the complexity is $O(|j||k|logn)$, where $|j|$ represents the number of
nodes in community $j$. For each combination of two communities, the worst
case is that all the nodes connected to all the communities. Assume that the
depth of the hierarchical clustering is $d$ and the number of nodes in a
community is $c_{n}$, the complexity is $O(mdc_{n}^{2}logn)$.

##  4 Experiment

In this section, we test our method on synthetic networks and two real world
social network datasets described before: Twitter and Gowalla. We use three
different measurements to evaluate the results:

######  Definition 4 (Geographic Span)

The geographic span of a community $c$ is defined as the average distance of
the nodes in $c$ to the centroid $(\bar{x},\bar{y})$ of all the nodes in the
community:

$S(c)=\frac{1}{|c|}\sum_{v}\sqrt{(x_{v}-\bar{x})^{2}+(y_{v}-\bar{y})^{2}}\delta(c_{v},c)$
(16)

######  Definition 5 (Average Internal Degree)

The internal degree of a node $v$ is the number of its neighbors in the same
community. The average internal degree of a community $c$ is the average value
of the internal degrees of all the nodes in $c$ and it can be represented as:

$A(c)=\frac{1}{|c|}\sum_{vw}\delta(c_{v},c)\delta(c_{w},c)$ (17)

The last measurement is the detection accuracy. Since we do not have a class
label of the real world datasets, we only apply this on the synthetic
networks. We implemented four community detection methods in our experiments:
1) Randomly select nodes as community (Random). 2) The method proposed in [3]
(Clauset’s Method). 3) The method discussed in section 3 using Equation 6 as
the modularity $Q$ (Connection Locality). 4) The method discussed in section 3
with Equation 9 as the modularity (Node Similarity).

Table 1: The accuracy of different community detection methods $\Omega$ | Clauset’s Method | Connection Locality | Node Similarity
---|---|---|---
1 | 16.24 | 16.63 | 18.38
3 | 16.48 | 22.82 | 24.63
5 | 17.72 | 22.40 | 28.77
10 | 22.16 | 25.14 | 26.60
30 | 32.84 | 19.76 | 24.42
$+\infty$ | 36.04 | 19.20 | 19.76

(a) $\Omega=3$

(b) $\Omega=10$

(c) $\Omega=+\infty$

(d) $\Omega=3$

(e) $\Omega=10$

(f) $\Omega=+\infty$

Figure 5: The geographic span and average internal degree of the synthetic
network under different values of $\Omega$.

###  4.1 Tests on Synthetic Networks

First we test the methods on the generated networks because a synthetic
datasets allow for better parameter control. We analyze the results using the
three measurements discussed above. When generating the dataset, we control
the influence of geographic distance on building connection between two nodes
in order to see the how the geographic feature affect the detection methods.

We generate the networks on a $50\times 50$ grid. There are 2,500 nodes in
total in the network. For each node, we randomly assign a community label to
it. There are 10 different community labels in the network. We generate the
probability of an edge existing between node $v$ and $w$ as:

$p_{e}=\alpha p_{c}e^{-dis_{vw}/\Omega}$ (18)

The value of $p_{c}$ depends on whether the node $v$ and $w$ have the same
community label. If their community labels are the same, $p_{s}$ is set to
$0.5$ and if not, $p_{c}$ is set to $0.1$. So the edges have a higher
probability of occurrence between the nodes with the same community label. The
component $e^{-dis_{vw}/\Omega}$ is used to control the influence of the
locations of nodes. When we set a large enough value to $\Omega$, the value of
$e^{-dis_{vw}/\Omega}$ is close to 1 and the probability is almost not
influenced by $dis_{vw}$. So the network structure is not influenced by the
locations of nodes. On the contrary, if the value of $\Omega$ is small, the
value of $e^{-dis_{vw}/\Omega}$ will be greatly influenced by the distance
between $v$ and $w$. In that case, only the nearby neighbors with the same
community label will have a high probability of connecting. The parameter of
$\alpha$ is used to control the average degrees of nodes in the network. In
the following experiment, we make the number of average degree around 15 by
adjust the value of $\alpha$.

Table 1 shows the accuracy of different algorithms on different generated
networks. Since the largest distance in the network is only 70, when we set
the $\Omega$ larger than 10, the probability of connecting is not very
sensitive to the distance. We can see that when the $\Omega$ is less than 10,
which means the building of connections is greatly influenced by the location
of nodes, our two methods can achieve a similar or higher accuracy than the
Clauset’s method. With the increasing of the value of $\Omega$, when the
location has little or no influence on the network structure, the accuracy of
Clauset’s method performance better than our methods. So we recommend to
evaluate the influence of geographic information first as described in section
3.1 before applying our methods on a network.

Figure 5 shows how the three methods perform on different synthetic networks.
From Figure 5(a) to 5(c) we can see for all levels of influence ($\Omega$)
that the geographic location on network structure, the connection locality
have the smallest geographic span. The geographic span of the node similarity
method is smaller than the Clauset’s method. Figure 5(d) to 5(f) show the
average internal degree of the three methods. When $\Omega$ is 3, where the
location of nodes will have the greatest influence on the network structure,
the connection locality method has a higher value of internal degree. This
illustrates that this method is suitable to deal with the highly
geographically influenced networks. When the value of $\Omega$ increases to
10, the average internal degree of these three methods is similar. But when we
set the $\Omega$ as infinity, the connection locality and node similarity
method perform worse than Clauset’s method.

###  4.2 Twitter Network

(a) The geographic span of different size of communities detected by different
methods

(b) The average internal degree of different size of communities detected by
different methods

Figure 6: Analyzing the community detection results of different methods on
the Twitter Network.

(a) The geographic span of different size of communities detected by different
methods

(b) The average internal degree of different size of communities detected by
different methods

Figure 7: Analyzing the community detection results of different methods on
the Gowalla Network.

In the real world, the factors which can influence the network structure can
be very complex. We now test the algorithms on the networks generated by some
real world applications. The first example is the Twitter network. We have
introduced the details of this network in Section 3.1. Since we do not have a
community label for the real world dataset, we only apply the geographic span
and the average internal degree of the communities to evaluate the detection
results.

In Figure 6(a), we demonstrate the geographic span of different sizes (number
of nodes in the community) of communities. From this figure we can see that
under the random case, the geographic span is much larger and increases
quickly to $800$ kilometers. The communities detected by Clauset’s method has
a smaller geographic span. It begin with 280 kilometers when the community
size is 2 but increases quickly when the community size become larger.
Finally, the geographic span fluctuates between 500 to 600 kilometers. The two
methods proposed in this paper have the best performance on controlling the
geographic span on communities. Although the geographic span increases quickly
when the community size becomes larger, these two method can keep the span
much smaller than Clauset’s method and the random case, especially for the
method with the Equation 6 as the modularity. The geographic spans in
different sizes of communities are only half of Clauset’s method.

The Figure 6(b) shows the average internal degrees of different sizes of
communities. This measurement evaluates the detection result by the network
structure only. From the definition we know that if a community have a higher
internal degree, that means the connections inside the community is tighter.
From the figure we can see that with the increasing of the community size, the
average internal degree also becomes larger, which means nodes have more
neighbors in the same community with them. The Clauset’s method and one of our
method, which use $Q^{s}$ as the modularity, have a similar performance. The
connection locality method has a smaller average internal degree when the
community size is larger than 40.

The results are encouraging and showing that our methods can detect
communities with similar internal degree and smaller community in geographic
span.

###  4.3 Gowalla Network

The second real world network is Gowalla. From the analysis in section 3.1, we
know that compared with the Twitter network, the geographic information in
Gowalla has greater influence on the network structure. So the Gowalla network
is more suitable to use our community detection methods.

From Figure 7(a), we can see that our methods have a strong effect on limiting
the geographic span of communities. Both the two methods can keep the span
around or less than 200 kilometers. Especially for the connection locality
method, even when the community size is very large, it can still keep the
geographic span in a small range.

Another important observation is that in the highly geographically influenced
networks, our method can also improve the network tightness in the
communities. Figure 7(b) shows the results of the average internal degree. The
performances of these algorithm are similar to the case on the Twitter
network. The different is that in the Twitter network, the connection locality
method performs worse than the other two methods. But on the Gowalla network,
it performs much better. This phenomenon illustrates that on the high
geographically influenced networks, our method can improve the quality of the
detection results on both geographic span and the tightness inside
communities.

##  5 Conclusion

In this paper, we studied the algorithms used in community detection. We argue
that finding communities with small geographic span is important for many
application domains. We analyzed two real datasets and found that they have
different level of locality. We propose a new community detection method that
keep the communities in small range of areas while maintaining the connection
closeness of the nodes in the communities. We performed extensive experiments
on both synthetic and real world datasets. Results show that the proposed
method find communities with nodes distributing in a smaller area compared
with the traditional methods and having the similar or higher tightness on
network connections. In our future work, we would like to explore low cost
community detection algorithm utilizing the property of locality of nodes in
communities.

## References

  * [1] Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre.  Fast unfolding of communities in large networks.  Journal of Statistical Mechanics: Theory and Experiment, 2008(10):P10008, 2008.
  * [2] Eunjoon Cho, Seth A Myers, and Jure Leskovec.  Friendship and mobility: user movement in location-based social networks.  In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1082–1090. ACM, 2011.
  * [3] Aaron Clauset, Mark EJ Newman, and Cristopher Moore.  Finding community structure in very large networks.  Physical review E, 70(6):066111, 2004.
  * [4] Michele Coscia, Fosca Giannotti, and Dino Pedreschi.  A classification for community discovery methods in complex networks.  Statistical Analysis and Data Mining, 4(5):512–546, 2011.
  * [5] Santo Fortunato.  Community detection in graphs.  Physics Reports, 486(3):75–174, 2010.
  * [6] Santo Fortunato.  Community detection in graphs.  Physics Reports, 486(3):75–174, 2010.
  * [7] Michelle Girvan and Mark EJ Newman.  Community structure in social and biological networks.  Proceedings of the National Academy of Sciences, 99(12):7821–7826, 2002.
  * [8] Jianbin Huang, Heli Sun, Yaguang Liu, Qinbao Song, and Tim Weninger.  Towards online multiresolution community detection in large-scale networks.  PloS one, 6(8):e23829, 2011.
  * [9] Bernardo A. Huberman, Daniel M. Romero, and Fang Wu.  Social networks that matter: Twitter under the microscope.  CoRR, abs/0812.1045, 2008.
  * [10] Erwan Le Martelot and Chris Hankin.  Fast multi-scale detection of relevant communities in large-scale networks.  The Computer Journal, 56(9):1136–1150, 2013.
  * [11] Mark EJ Newman.  Mixing patterns in networks.  Physical Review E, 67(2):026126, 2003.
  * [12] Mark EJ Newman and Michelle Girvan.  Finding and evaluating community structure in networks.  Physical review E, 69(2):026113, 2004.
  * [13] Jukka-Pekka Onnela, Samuel Arbesman, Marta C González, Albert-László Barabási, and Nicholas A Christakis.  Geographic constraints on social network groups.  PLoS one, 6(4):e16939, 2011.
  * [14] Mason A Porter, Jukka-Pekka Onnela, and Peter J Mucha.  Communities in networks.  Notices of the AMS, 56(9):1082–1097, 2009.
  * [15] Jörg Reichardt and Stefan Bornholdt.  Statistical mechanics of community detection.  Physical Review E, 74(1):016110, 2006.
  * [16] Salvatore Scellato, Cecilia Mascolo, Mirco Musolesi, and Vito Latora.  Distance matters: geo-social metrics for online social networks.  Proceedings of WOSN, 10, 2010.
  * [17] Salvatore Scellato, Cecilia Mascolo, Mirco Musolesi, and Vito Latora.  Distance matters: geo-social metrics for online social networks.  In Proceedings of the 3rd conference on Online social networks, pages 8–8, 2010.
  * [18] Salvatore Scellato, Anastasios Noulas, Renaud Lambiotte, and Cecilia Mascolo.  Socio-spatial properties of online location-based social networks.  ICWSM, 11:329–336, 2011.
  * [19] Yves van Gennip, Blake Hunter, Raymond Ahn, Peter Elliott, Kyle Luh, Megan Halvorson, Shannon Reid, Matthew Valasik, James Wo, George E Tita, et al.  Community detection using spectral clustering on sparse geosocial data.  SIAM Journal on Applied Mathematics, 73(1):67–83, 2013.
  * [20] Xufei Wang, Huan Liu, Peng Zhang, and Baoxin Li.  Identifying information spreaders in twitter follower networks.  Technical Report TR-12-001, School of Computing, Informatics, and Decision Systems Engineering, Arizona State University, Tempe, AZ 85287, USA, 2012\.


$\sum_{\makebox[7.00002pt][l]{$\scriptstyle\\{\omega\mid
t\in\Omega_{\omega}\\}$}}G(t\cdot\textsf{reset}_{\omega})\leq
G(t\cdot\textsf{undo}(f))<G_{1}(t\cdot\textsf{undo}(f))\leq\sum_{\makebox[7.00002pt]{$\scriptstyle\\{\omega\mid
t\in\Omega_{\omega}\\}$}}G_{1}(t\cdot\textsf{undo}_{\omega})=\sum_{\makebox[7.00002pt]{$\scriptstyle\\{\omega\mid
t\in\Omega_{\omega}\\}$}}G(t\cdot\textsf{undo}_{\omega}).$

Hence, there is an $\omega$ with $t\in\Omega_{\omega}$ and
$G(t\cdot\textsf{reset}_{\omega})<G(t\cdot\textsf{undo}_{\omega})$. This
$\omega$ must have the form $k\in T^{\prime}$ with
$k\mathbin{\raisebox{0.0pt}[0.0pt][0.0pt]{$\stackrel{{\scriptstyle\\#}}{{=}}$}}c$.
We now obtain

$\begin{array}[b]{r@{~\leq~}ll}\lx@intercol\hfil
0~{}=~{}&G(\textsf{finalise}^{k})&\mbox{(by (\ref{r2}))}\\\
~{}\leq~{}&G(t\cdot\textsf{elide}_{k})+G(t\cdot\textsf{reset}_{k})&\mbox{(by
(\ref{reset}))}\\\
\lx@intercol\hfil~{}<~{}&G(t\cdot\textsf{elide}_{k})+G(t\cdot\textsf{undo}_{k})\\\
~{}\leq~{}&\sum_{l\geq^{\\#}k}G(\textsf{execute}^{k}_{l})&\mbox{(by
(\ref{undo}))}.\end{array}$

Hence, there is an
$l\geq^{\\#}k\mathbin{\raisebox{0.0pt}[0.0pt][0.0pt]{$\stackrel{{\scriptstyle\\#}}{{=}}$}}c$
with $G(\textsf{execute}^{k}_{l})>0$. By (M) we obtain
$\neg(j\mathbin{\raisebox{0.0pt}[0.0pt][0.0pt]{$\stackrel{{\scriptstyle\\#}}{{=}}$}}k)$,
so ${\vphantom{j}}^{\bullet}j\cap{\vphantom{k}}^{\bullet}k=\emptyset$.
Additionally, we have
${\vphantom{j}}^{\bullet}j\cap{\vphantom{c}}^{\bullet}c\neq\emptyset$ and
${\vphantom{c}}^{\bullet}c\cap{\vphantom{k}}^{\bullet}k\neq\emptyset$. By (N)
we obtain $M^{\prime}[j\rangle$, and by (D) and (F) $M^{\prime}[k\rangle$.
Furthermore, by (11),
$G(t\cdot\textsf{undo}(f))<G_{1}(t\cdot\textsf{undo}(f))\leq
G_{1}(t\cdot\textsf{fire})=G(t\cdot\textsf{fire})$, so, for all
$p\mathbin{\in}{\vphantom{c}}^{\bullet}c$,

$\begin{array}[b]{r@{~\leq~}ll}F^{\prime}(p,c)~{}\leq~{}&F^{\prime}(p,c)\cdot\big{(}G(t\cdot\textsf{fire})-G(t\cdot\textsf{undo}(f))\big{)}\\\
~{}\leq~{}&F^{\prime}(p,c)\cdot\big{(}G(t\cdot\textsf{fire})-G(t\cdot\textsf{undone})\big{)}&\mbox{(by
(\ref{took}))}\\\
~{}\leq~{}&G(\textsf{distribute}_{p})-\sum_{j\geq^{\\#}i\in{p}^{\bullet}}F^{\prime}(p,i)\cdot
G(\textsf{fetch}_{i,j}^{p,c})&\mbox{(by (\ref{p_j}))}\\\
~{}\leq~{}&G(\textsf{distribute}_{p})&\mbox{(by (\ref{rFp}) and
(\ref{fetch}))}\\\ ~{}\leq~{}&M^{\prime}(p)&\mbox{(by (\ref{r3}).}\\\
\end{array}$

It follows that $M^{\prime}[c\rangle$. Thus $N^{\prime}$ contains a fully
reachable pure M, which contradicts the assumptions of Lemma LABEL:lem-
essentially_distributed.

######  Theorem 6.6.

cri-distributed Let $N$ be the conflict replicating implementation
$\mathcal{I}(N^{\prime})$ of a finitary plain structural conflict net
$N^{\prime}$ without a fully reachable pure M. Then $N$ is essentially
distributed.

######  Proof 6.7.

We take the canonical distribution $D$ of $N$, in which $\equiv_{D}$ is the
equivalence relation on places and transitions generated by Condition (1) of
Definition LABEL:df-distributed. We need to show that this distribution
satisfies Condition ($2^{\prime}$) of Definition LABEL:df-
externally_distributed. A given transition $t$ with $\ell(t)\neq\tau$ must
have the form $\textsf{execute}^{i}_{j}$ for some $i\leq^{\\#}\\!j\in
T^{\prime}$. By following the flow relation of $N$ one finds the places and
transitions that, under the canonical distribution, are co-located with
$\textsf{execute}^{i}_{j}$:

$\begin{array}[]{@{}l@{}}\pi_{j\\#l}\rightarrow\textsf{transfer}^{j}_{l}\cdot\textsf{fire}\leftarrow\textsf{trans}^{j}_{l}\textsf{-in}\rightarrow\textsf{initialise}_{l}\cdot\textsf{undo}(\mbox{$\textsf{trans}^{j}_{l}\textsf{-in}$})\leftarrow\textsf{take}(\textsf{trans}^{j}_{l}\textsf{-in},\textsf{initialise}_{l})\\\
~{}~{}\downarrow\\\ \textsf{execute}^{i}_{j}\\\ ~{}~{}\uparrow\\\
\textsf{trans}^{h}_{j}\textsf{-out}\rightarrow\textsf{transfer}^{h}_{j}\cdot\textsf{undo}(\textsf{trans}^{h}_{j}\textsf{-out})\leftarrow\textsf{take}(\textsf{trans}^{h}_{j}\textsf{-out},\textsf{transfer}^{h}_{j})\\\
~{}~{}\downarrow\\\ \textsf{execute}^{g}_{j}\\\ ~{}~{}\uparrow\\\
\textsf{pre}^{g}_{j}\rightarrow\textsf{initialise}_{g}\cdot\textsf{undo}(\textsf{pre}^{g}_{j})\leftarrow\textsf{take}(\textsf{pre}^{g}_{j},\textsf{initialise}_{g})\end{array}$

for all $l\mathbin{>^{\\#}}j$, $h\mathbin{<^{\\#}}j$ and $g\leq^{\\#}\\!j$. We
need to show that none of these transitions can happen concurrently with
$\textsf{execute}^{i}_{j}$. For transitions
$\textsf{transfer}^{j}_{l}\cdot\textsf{fire}$ and $\textsf{execute}^{g}_{j}$
this follows directly from Lemma LABEL:lem-S-invariant. For
$\textsf{transfer}^{h}_{j}\cdot\textsf{undo}(\textsf{trans}^{h}_{j}\textsf{-out})$
this also follows from Lemma LABEL:lem-S-invariant, in which $j$, $k$ and $l$
play the rôle of the current $h$, $i$ and $j$. For the transitions
$\textsf{initialise}_{l}\cdot\textsf{undo}(\mbox{$\textsf{trans}^{j}_{l}\textsf{-in}$})$
and $\textsf{initialise}_{g}\cdot\textsf{undo}(\textsf{pre}^{g}_{j})$ this has
been established in Lemma LABEL:lem-essentially_distributed.

Our main result follows by combining Theorems LABEL:thm-correctness and
LABEL:thm-cri-distributed and Proposition LABEL:pr-
essentiallydistributedequal:

######  Theorem 6.8.

fullmgttrulysync Let $N$ be a finitary plain structural conflict net without a
fully reachable pure M. Then $N$ is distributable up to
$\approx^{\Delta}_{bSTb}$.

######  Corollary 6.9.

fullmeqtrulysync Let $N$ be a finitary plain structural conflict net. Then $N$
is distributable iff it has no fully reachable pure M.

##  7 Conclusion

In this paper, we have given a precise characterisation of distributable Petri
nets in terms of a semi-structural property. Moreover, we have shown that our
notion of distributability corresponds to an intuitive notion of a distributed
system by establishing that any distributable net may be implemented as a
network of asynchronously communicating components. In order to formalise what
qualifies as a valid implementation, we needed a suitable equivalence
relation. We have chosen step readiness equivalence for showing the
impossibility part of our characterisation, since it is one of the simplest
and least discriminating semantic equivalences imaginable that abstracts from
internal actions but preserves branching time, concurrency and divergence to
some small degree. For the positive part, stating that all other nets are
implementable, we have introduced a combination of several well known rather
discriminating equivalences, namely a divergence sensitive version of
branching bisimulation adapted to ST-semantics. Hence our characterisation is
rather robust against the chosen equivalence; it holds in fact for all
equivalences between these two notions. However, ST-equivalence (and our
version of it) preserves the causal structure between action occurrences only
as far as it can be expressed in terms of the possibility of durational
actions to overlap in time. Hence a natural question is whether we could have
chosen an even stronger causality sensitive equivalence for our
implementability result, respecting e.g. pomset equivalence or history
preserving bisimulation. Our conflict replicating implementation does not
fully preserve the causal behaviour of nets; we are convinced that we have
chosen the strongest possible equivalence for which our implementation works.
It is an open problem to find a class of nets that can be implemented
distributedly while preserving divergence, branching time and causality in
full. Another line of research is to investigate which Petri nets can be
implemented as distributed nets when relaxing the requirement of preserving
the branching structure. If we allow linear time correct implementations
(using a step trace equivalence), we conjecture that all Petri nets become
distributable. However, also in this case it is problematic, in fact even
impossible in our setting, to preserve the causal structure, as has been shown
in [17]. A similar impossibility result has been obtained in the world of the
$\pi$-calculus in [15]. The interplay between choice and synchronous
communication has already been investigated in quite a number of approaches in
different frameworks. We refer to [7] for a rather comprehensive overview and
concentrate here on recent and closely related work. The idea of modelling
asynchronously communicating sequential components by sequential Petri nets
interacting though buffer places has already been considered in [16]. There
Wolfgang Reisig introduces a class of systems, represented as Petri nets,
where the relative speeds of different components are guaranteed to be
irrelevant. His class is a strict subset of our LSGA nets, requiring
additionally, amongst others, that all choices in sequential components are
free, i.e. do not depend upon the existence of buffer tokens, and that places
are output buffers of only one component. Another quite similar approach was
taken in [4], where transition labels are classified as being either input or
output. There, asynchrony is introduced by adding new buffer places during net
composition. This framework does not allow multiple senders for a single
receiver. Other notions of distributed and distributable Petri nets are
proposed in [12, 2, 3]. In these works, given a distribution of the
transitions of a net, the net is distributable iff it can be implemented by a
net that is distributed w.r.t. that distribution. The requirement that
concurrent transitions may not be co-located is absent; given the fixed
distribution, there is no need for such a requirement. These papers differ
from each other, and from ours, in what counts as a valid implementation. A
comparison of our criterion with that of Hopkins [12] is provided in [7]. In
[7] we have obtained a characterisation similar to Corollary LABEL:cor-
fullmeqtrulysync, but for a much more restricted notion of distributed
implementation (_plain distributability_), disallowing nontrivial transition
labellings in distributed implementations. We also proved that fully reachable
pure Ms are not implementable in a distributed way, even when using transition
labels (Theorem LABEL:thm-trulysyngltfullm). However, we were not able to show
that this upper bound on the class of distributable systems was tight. Our
current work implies the validity of Conjecture 1 of [7]. While in [7] we
considered only one-safe place/transition systems, the present paper employs a
more general class of place/transition systems, namely structural conflict
nets. This enables us to give a concrete characterisation of distributed nets
as systems of sequential components interacting via non-safe buffer places.

## References

  * [1]
  * [2] E. Badouel, B. Caillaud & P. Darondeau (2002): _Distributing Finite Automata Through Petri Net Synthesis_.  Formal Aspects of Computing 13(6), pp. 447–470, 10.1007/s001650200022.
  * [3] E. Best & Ph. Darondeau (2012): _Petri Net Distributability_.  In E.M. Clarke, I. Virbitskaite & A. Voronkov, editors: Perspectives of Systems Informatics - Revised Selected Papers presented at the 8th International Andrei Ershov Memorial Conference, PSI 2011, Novosibirsk, LNCS 7162, Springer, pp. 1–18, 10.1007/978-3-642-29709-0_1.
  * [4] D. El Hog-Benzina, S. Haddad & R. Hennicker (2010): _Process Refinement and Asynchronous Composition with Modalities_.  In N. Sidorova & A. Serebrenik, editors: Proceedings of the 2nd International Workshop on Abstractions for Petri Nets and Other Models of Concurrency (APNOC’10), Braga, Portugal.  Available at http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/EHH-apnoc10.pdf.
  * [5] R.J. van Glabbeek (1993): _The Linear Time - Branching Time Spectrum II_.  In: Proceedings of the 4th International Conference on Concurrency Theory (CONCUR’93), Springer, London, UK, pp. 66–81, 10.1007/3-540-57208-2_6.
  * [6] R.J. van Glabbeek & U. Goltz (2001): _Refinement of actions and equivalence notions for concurrent systems_.  Acta Informatica 37(4/5), pp. 229–327, 10.1007/s002360000041.
  * [7] R.J. van Glabbeek, U. Goltz & J.-W. Schicke (2008): _On Synchronous and Asynchronous Interaction in Distributed Systems_.  In E. Ochmański & J. Tyszkiewicz, editors: Mathematical Foundations of Computer Science 2008, LNCS 5162, Springer, pp. 16–35, 10.1007/978-3-540-85238-4_2.  Full version available as Technical Report 2008-03, TU-Braunschweig; http://arxiv.org/abs/0901.0048.
  * [8] R.J. van Glabbeek, U. Goltz & J.-W. Schicke (2011): _Abstract Processes of Place/Transition Systems_.  Information Processing Letters 111(13), pp. 626 – 633, 10.1016/j.ipl.2011.03.013.
  * [9] R.J. van Glabbeek, B. Luttik & N. Trčka (2009): _Branching Bisimilarity with Explicit Divergence_.  Fundamenta Informaticae 93(4), pp. 371–392.  Archived at http://arxiv.org/abs/0812.3068.
  * [10] R.J. van Glabbeek & F.W. Vaandrager (1987): _Petri net models for algebraic theories of concurrency (extended abstract)_.  In: Proceedings PARLE ’87, LNCS 259, Springer, pp. 224–242, 10.1007/3-540-17945-3_13.  Available at http://kilby.stanford.edu/~rvg/pub/petri.pdf.
  * [11] R.J. van Glabbeek & W.P. Weijland (1996): _Branching Time and Abstraction in Bisimulation Semantics_.  Journal of the ACM 43(3), pp. 555–600, 10.1145/233551.233556.
  * [12] R.P. Hopkins (1991): _Distributable nets_.  In: Advances in Petri Nets 1991, LNCS 524, Springer, pp. 161–187, 10.1007/BFb0019974.
  * [13] R. Milner (1989): _Communication and Concurrency_.  Prentice Hall, Englewood Cliffs.
  * [14] E.-R. Olderog & C.A.R. Hoare (1986): _Specification-oriented semantics for communicating processes_.  Acta Informatica 23, pp. 9–66, 10.1007/BF00268075.
  * [15] K. Peters, J.-W. Schicke & U. Nestmann (2011): _Synchrony vs Causality in the Asynchronous Pi-Calculus_.  In B. Luttik & F. Valencia, editors: Proceedings 18th International Workshop on Expressiveness in Concurrency, Aachen, Germany, 5th September 2011, Electronic Proceedings in Theoretical Computer Science 64, pp. 89–103, 10.4204/EPTCS.64.7.
  * [16] W. Reisig (1982): _Deterministic Buffer Synchronization of Sequential Processes_.  Acta Informatica 18, pp. 115–134, 10.1007/BF00264434.
  * [17] J.-W. Schicke, K. Peters & U. Goltz (2011): _Synchrony vs. Causality in Asynchronous Petri Nets_.  In B. Luttik & F. Valencia, editors: Proceedings 18th International Workshop on Expressiveness in Concurrency, Aachen, Germany, 5th September 2011, Electronic Proceedings in Theoretical Computer Science 64, pp. 119–131, 10.4204/EPTCS.64.9.
  * [18] W. Vogler (1993): _Bisimulation and Action Refinement_.  Theoretical Computer Science 114(1), pp. 173–200, 10.1016/0304-3975(93)90157-O.


# Does the Magic of BERT Apply to Medical Code Assignment? A Quantitative
Study

Shaoxiong Ji  Matti Hölttä  Pekka Marttinen

###### Abstract

Unsupervised pretraining is an integral part of many natural language
processing systems, and transfer learning with language models has achieved
remarkable results in downstream tasks. In the clinical application of medical
code assignment, diagnosis and procedure codes are inferred from lengthy
clinical notes such as hospital discharge summaries. However, it is not clear
if pretrained models are useful for medical code prediction without further
architecture engineering. This paper conducts a comprehensive quantitative
analysis of various contextualized language models’ performances, pretrained
in different domains, for medical code assignment from clinical notes. We
propose a hierarchical fine-tuning architecture to capture interactions
between distant words and adopt label-wise attention to exploit label
information. Contrary to current trends, we demonstrate that a carefully
trained classical CNN outperforms attention-based models on a MIMIC-III subset
with frequent codes. Our empirical findings suggest directions for building
robust medical code assignment models.

Keywords— Medical Code Assignment; Pretrained Language Models; BERT;
Quantitative Study

##  1 Introduction

Clinical notes generated by healthcare professionals are parts of electronic
health records and provide an essential source for intelligent healthcare
applications [Zhang et al., 2020]. Medical information management aims to
assign standard medical codes to each clinical document for categorization
purposes, which requires professional medical knowledge and is usually costly
and error-prone [Hsia et al., 1988, Stanfill et al., 2010]. The International
Classification of Diseases (ICD) system, as the most used coding system,
provides a global standard for reporting diseases and health conditions. The
rapid development of machine learning and natural language processing (NLP)
can replace manual code assignment with automatic coding systems [Farkas and
Szarvas, 2008, Crammer et al., 2007, Farzandipour et al., 2010]. Practical
medical code assignment requires to capture semantic concepts [Falis et al.,
2019] and tackle the challenges of lengthy note encoding and large-dimensional
code schemes.

Figure 1: Fine-tuning for ICD coding with pretraining in different domains:
general, closely related, target, or mixed-domain pretraining.

Pretrained language models (PTM) such as BERT [Devlin et al., 2019] learn
contextualized text representation and have started a new era in NLP. NLP
applications benefit from large-scale pretraining on massive corpora, and
universal language representations from PTMs have been successfully utilized
in downstream tasks via transfer learning. In the field of clinical NLP,
incorporating pretrained contextualized language models to encode lengthy
clinical notes for large-scale medical code prediction has not been well-
studied. Recently, Li and Yu [2020], ji2021medical and Dong et al. [2020]
performed preliminary experiments with pretrained models; however, these three
pilot studies failed to achieve satisfactory results or provide in-depth
analysis.

This paper investigates language models pretrained in various domains. A
language domain here defines a distribution over a topical field such as
biomedical documents and clinical notes. Specifically, we investigate the
following three research questions (RQ1-3).

RQ1:

What kind of BERT pretraining works best? We adopt domain-specific corpora and
BERT variants pretrained with different domain adaptation illustrated in Fig.
1, and compare their performance on the MIMIC-III benchmark.

RQ2:

What kind of BERT fine-tuning formulation works best for long notes? We employ
classical fine-tuning, develop a hierarchical architecture for long clinical
notes, and consider label-aware feature representation.

RQ3:

Are BERT models better than convolution-based approaches? We reproduce
convolutional neural networks (CNNs) with classical pretrained word embeddings
and conduct a comparison.

Understanding medical text is a long-lasting research problem. We study an
essential task in medical information management and diagnosis support -
medical code assignment, assigning medical codes to clinical notes. Language
models can either be pretrained using a large corpus of medical text or
trained from scratch and fine-tuned for a specific task. Several pretrained
models have been published for medical NLP, and they differ in the collections
of medical texts used for pretraining, e.g., biomedical, clinical, and
medical-related social domains. We study the usefulness and relative merits of
these different pretrained models and suggest improvements to the neural
network architecture to improve performance with long notes: a hierarchical
model for longer notes and label-wise attention to leverage relevant
information about medical codes. Despite our careful attempts, we nevertheless
find that fine-tuning pretrained models performs worse than carefully training
conventional neural architectures from scratch. Hence, our results provide
practical guidance for building medical information management systems:
pretrained models offer a convenient plug-and-play solution; however, training
robust existing standard models offers an appealing practical alternative with
good performance in practice.

Our contributions are as follows.

  * •

This paper conducts a comprehensive quantitative study to investigate the
effect of knowledge transfer via mixed-domain and task-adaptive language model
pretraining in different domains, and a thorough comparative study to answer
the research questions.

  * •

We propose a hierarchical BERT architecture with a label attention mechanism
to enhance contextualized representation with label awareness for long
clinical notes.

  * •

We demonstrate that the classical CNN model with appropriate training can
improve the predictive performance, achieving new state-of-the-art results on
frequent medical codes (MIMIC-III top-50 dataset).

##  2 Related Work

Rule-based and machine learning-based methods have been studied for diagnosis
code assignment from clinical notes [Medori and Fairon, 2010, Perotte et al.,
2014]. Perotte et al. [2014] proposed an SVM-based classification algorithm
with a flat and hierarchy-based classifier. Recently, the research trend turns
to deep neural networks. Convolutional neural networks are one popular
category with many model architecture proposed, including CAML that applies
CNNs and a label-wise attention mechanism [Mullenbach et al., 2018],
MultiResCNN that uses residual connection [Li and Yu, 2020] and DCAN that
utilizes dilated convolutions [Ji et al., 2020a]. Recurrent neural networks
are also extensively studied to capture sequential dependency in clinical
notes. Such recurrent models include AttentiveLSTM [Shi et al., 2017], HA-GRU
[Baumel et al., 2018] and tree-of-sequences LSTM network [Xie and Xing, 2018]
Attention mechanism for matching important diagnosis snippets is widely
integrated into CNN- and RNN-based models [Shi et al., 2017, Dong et al.,
2020]. CAML [Mullenbach et al., 2018] introduced a label-wise attention
mechanism to learn label-aware document representations.

Understanding clinical notes require professional medical knowledge. Many
methods incorporate external knowledge sources to enhance neural architectures
and facilitate clinical text understanding. Prakash et al. [2017] proposed a
condensed memory network model with iterative condensation of external memory
for network updating and data retrieval from Wikipedia. Bai and Vucetic [2019]
used Wikipedia articles of medical codes to learn knowledge-aware embeddings
jointly, and Cao et al. [2020] utilized ICD code hierarchy with hyperbolic
representation. Another direction to incorporate knowledge is through language
pretraining and transfer learning. Li and Yu [2020] and ji2021medical reported
preliminary results with semantic knowledge transferring. This paper conducts
a comprehensive quantitative analysis.

Pretrained language models are trained on an auxiliary task, such as masked
language modeling that predicts a word or sequence based on the surrounding
context and gains improvement in many NLP tasks [Xipeng et al., 2020].
Pretraining such auxiliary tasks benefit from large-scale training on
unlabeled corpora that are readily available from the web or textbooks. Erhan
et al. [2010] hypothesized that pretraining acts as a type of regularization
and found that pretrained models exhibit lower generalization errors on
average. Several pretraining models in specific domains have been released,
such as BioBERT [Lee et al., 2020] and ClinicalBERT [Alsentzer et al., 2019].
They have also been applied in many domain applications; for example, Mulyar
et al. [2019] applied contextualized language models for phenotyping and Huang
et al. [2019] used pretrained models to encode clinical notes to predict
hospital readmission.

##  3 Method

we develop fine-tuning with different architectures, including a fully-
connected classifier and a hierarchical classifier with an extra transformer
atop (Fig. 2) to address the long-document challenge. Label-wise attention to
learn label-aware document representations with these two fine-tuning
architectures is described in Section 3.3.

###  3.1 Pretraining Domains

We study three types of domains: 1) general domains such as book corpora and
general Wikipedia articles; 2) domains that are closely related to the target
clinical domain; 3) the target clinical domain. Assigning ICD codes from
clinical notes is a task in the clinical domain. We consider biomedical and
health-related social domains as candidate domains closely related to the
clinical domain. Inspired by domain- and task-adaptive pretraining [Gururangan
et al., 2020], we investigate different ways of pretraining models for medical
code assignment: 1) pretrain only on general domains and immediately transfer
to the target clinical domain; 2) continue pretraining on close domains and
clinical domains such as the biomedical domain, and transfer to the target
clinical domain 3) pretrain on close domains from scratch and transfer to the
target clinical domain; 4) pretrain on mixed domains and further fine-tune on
the target domain. The details of methods that fall into these classes can be
summarized with three categories:

#### Pretraining in General Domains

does not involve specific topics or genres. We use BERT [Devlin et al., 2019]
pretrained on two unsupervised prediction tasks, i.e., masked language model
and next sentence prediction, using the BooksCorpus [Zhu et al., 2015] and
English Wikipedia.

#### Mixed-domain Pretraining

contains a mixture of domains. We consider continued training and training
from scratch. Domain-adaptive pretraining has been validated for the ability
to improve the predictive performance [Gururangan et al., 2020] further. We
use 1) BlueBERT [Peng et al., 2019] pretrained with PubMed text and MIMIC-III
clinical notes; 2) BioBERT [Lee et al., 2020] continually pretrained on
domain-specific data from PubMed abstracts and PMC full-text articles; 3)
BioRedditBERT [Basaldella et al., 2020] initialized from BioBERT and
continually pretrained on health-related posts from health-themed forums in
Reddit; 4) PubMedBERT [Gu et al., 2020] domain-specific pretrained from
scratch in biomedical domain using PubMed publications; and 5) SapBERT [Liu et
al., 2020] that benefits from self-aligning biomedical entities to the Unified
Medical Language System (UMLS) ontology and non-parametric metric learning,
leading to a better-separated embedding space.

#### In-domain Continued Pretraining

continues pretraining in the target clinical domain, which is also called
task-specific pretraining [Howard and Ruder, 2018, Gururangan et al., 2020].
We use the ClinicalBERT [Alsentzer et al., 2019] with the second phase of
pretraining in the clinical domain using clinical notes and discharge
summaries.

###  3.2 Fine-tuning with Hierarchical Structure

Clinical notes, consisting of patient history and discharge summaries, are
often long documents. To address this, we develop two fine-tuning strategies,
one based on the straightforward truncation and the other with hierarchical
architecture. In the first approach, we truncate clinical notes to 512 tokens,
take the final hidden state of the first token [CLS] as the pooled
representation of the truncated note (denoted as $C\in\mathbb{R}^{d_{h}}$),
and apply a fully connected network (FCN) as the classifier with sigmoid
activation to predict output probabilities. This straightforward fine-tuning
structure is denoted as BERT-trun, and it serves as the baseline.

Besides, we propose a hierarchical fine-tuning structure to deal with long
notes, shown in Fig. 2. The lengthy clinical notes (with more than 512 tokens)
are first divided into several shorter subsequences to build the lower-level
contextualized representation. An additional transformer network [Vaswani et
al., 2017] is built atop to capture the second-level sequential dependencies
between the note segments. The classifier follows the same setup of the
truncated version, i.e., FCN with sigmoid. We call this hierarchical structure
BERT-hier.

Figure 2: Hierarchical BERT dealing with long clinical notes.

The learning objective function adopts the binary cross entropy loss denoted
as:

$\small\mathcal{L}=\sum_{i=1}^{m}\left[-y_{i}\log\left(\hat{y}_{i}\right)-\left(1-y_{i}\right)\log\left(1-\hat{y}_{i}\right)\right],$
(1)

where $y_{i}\in\\{0,1\\}$ is the ground-truth label, $\hat{y}_{i}$ is the
sigmoid score for prediction, and $m$ is the number of ICD codes. We use the
AdamW optimizer [Loshchilov and Hutter, 2019] to fine-tune the model with
backpropagation.

###  3.3 Label-wise Attention

To further connect the document representation with label information, we
introduce label-wise attention [Mullenbach et al., 2018] in the fine-tuning
procedures. The label attention network (LAN) prioritizes essential
information in the hidden note representation relevant to the medical ICD
codes. The LAN calculates the attention score
$\mathbf{A}\in\mathbb{R}^{n\times m}$, which measures the importance between
each pair of medical codes and words in the document. It is defined as a dot
product:

$\mathbf{A}=\operatorname{Softmax}(\mathbf{H}\mathbf{U}),$ (2)

where $\mathbf{H}\in\mathbb{R}^{n\times h}$ is the hidden encoding of the BERT
encoder’s last layer, $\mathbf{U}\in\mathbb{R}^{{h}\times m}$ is the parameter
matrix of the label attention layer (also known as the query), $n$ is the
number of tokens in the document, $h$ is the hidden representation dimension,
and $m$ is the number of ICD codes. The attention layer’s output is then
calculated by multiplying attention $\mathbf{A}$ with the hidden
representation from the last layer of BERT encoder. The attentive
representation $\mathbf{V}\in\mathbb{R}^{m\times{h}}$ formalized as
$\mathbf{V}=\mathbf{A}^{\mathrm{T}}\mathbf{H}$ is further used for medical
code classification, representing sequential dependency and label awareness.
The BERT-trun and BERT-hier fine-tuning architectures can both integrate the
label-wise attention mechanism.

###  3.4 Experimental Setup

This paper focuses on assigning ICD codes to textual discharge summaries from
a hospital stay. The Medical Information Mart for Intensive Care III (MIMIC-
III) repository [Johnson et al., 2016] contains patients admitted to the
Intensive Care Unit (ICU) at a US medical center from 2001 to 2012. The MIMIC
database is available by request via this website https://mimic.physionet.org.
We use the “noteevents” table in the latest release of version 1.4 with a
total of 58,576 hospital admissions. Specifically, free-text discharge
summaries are extracted. Two settings are used for experimental evaluation.
One uses the top 50 frequent labels derived from Shi et al. [2017], while
another uses the full set of ICD codes. Table 1 shows a statistical summary of
two sets of MIMIC data.

Table 1: A statistical summary of datasets Dataset | Train | Dev. | Test | Labels
---|---|---|---|---
MIMIC-III top-50 | 8,066 | 1,573 | 1,729 | 50
MIMIC-III full | 47,723 | 1,631 | 3,372 | 8,921

#### Preprocessing.

We use raw notes, ICD diagnoses, and procedures for patients from the public
clinical MIMIC-III dataset for experiments. Discharge summaries labeled with a
set of ICD-9 diagnosis and procedure codes include descriptions of procedures
performed by a physician, diagnosis notes, patient’s medical history, and
discharge instructions. Addenda of admissions are concatenated to a single
document. The NLTK package is utilized for tokenization, and all tokens are
converted into lowercase. Non-alphabetic characters, such as numbers and
punctuations, are removed. All documents are truncated at 512 tokens and 2500
tokens for a single BERT encoder (BERT-trun) and hierarchical BERT encoders
(BERT-hier).

#### Training.

For the prior publications and the recommendation of fine-tuning the BERT
model, we choose some common settings. For example, the dropout probability is
0.1. The Adam optimizer [Kingma and Ba, 2014] is used to optimize CNN-based
models, and the AdamW optimizer [Loshchilov and Hutter, 2019] to fine-tune
BERT variants. We utilize a linear learning rate scheduler with warmup and
layer-wise learning rates when fine-tuning BERT-based models. For retraining
the CNN-based models, we use the CBOW of word2vec [Mikolov et al., 2013] and
adopt static word embeddings. We set the batch size for MIMIC-III top-50 and
full sets at 8, and the learning rate from $1\mathrm{e}^{-6}$ to
$1\mathrm{e}^{-3}$.

All the models are run on a Linux cluster with Nvidia P100 or V100 GPUs. For
the MIMIC-III top-50 data set, the fine-tuning architecture with truncated
notes and a linear classifier has about 109M parameters. In comparison, the
MIMIC-III full set takes about 115M parameters. For the hierarchical
architecture, MIMIC-III top-50 and full codes data sets have 115M and 128M
parameters, respectively. Generally speaking, fine-tuning pretrained models
consumes the memory of a large GPU; however, it is arguably less expensive
than training from scratch.

Table 2: Results of PLM fine-tuning with BERT-hier \+ LAN in various domains on MIMIC-III dataset with top-50 and full ICD codes. Clinical notes are truncated at length of 2500. Hierarchical fine-tuning structure with label-wise attention is used. Bold text denotes the best and italic text denotes the second best. Model | MIMIC-III Top-50 Codes | MIMIC-III Full Codes
---|---|---
AUC-ROC | F1 | P@5 | AUC-ROC | F1 | P@8 | P@15
Macro | Micro | Macro | Micro | Macro | Micro | Macro | Micro
BERT-base | 82.7 | 86.3 | 40.8 | 50.8 | 52.2 | 82.2 | 96.6 | 5.8 | 44.1 | 63.3 | 48.1
BlueBERT | 89.4 | 92.0 | 61.0 | 65.6 | 62.8 | 84.4 | 97.5 | 5.1 | 42.5 | 62.6 | 47.3
BioBERT full text | 88.8 | 91.7 | 60.4 | 66.0 | 63.1 | 85.2 | 97.4 | 6.4 | 47.0 | 65.8 | 50.7
BioRedditBERT | 87.1 | 89.6 | 59.4 | 64.8 | 62.4 | 86.5 | 98.0 | 3.0 | 40.6 | 62.4 | 47.8
PubMedBERT full text | 88.6 | 90.8 | 63.3 | 68.1 | 64.4 | 87.4 | 98.1 | 4.3 | 44.5 | 65.2 | 50.4
SapBERT full text | 88.5 | 90.8 | 62.2 | 66.7 | 63.1 | 86.4 | 97.7 | 6.2 | 46.8 | 68.5 | 53.0
ClinicalBERT all notes | 89.2 | 91.6 | 59.5 | 64.8 | 62.0 | 84.7 | 97.4 | 6.0 | 46.6 | 65.1 | 49.9

##  4 Results

We conduct a series of experiments with different pretrained models on various
domains using two fine-tuning architectures and reproduce classical CNN-based
models with word embeddings from scratch. We make our code publicly available
at https://agit.ai/jsx/MCA_BERT.

Different evaluation metrics are utilized for experimental evaluation,
including micro and macro F1 scores and area under the receiver operating
characteristic curve (AUC-ROC). We evaluate the metrics of precision at $k$,
where $k=5$ for MIMIC-III subset with top-$50$ frequent codes and $k=8,15$ for
full sets of MIMIC-III, given the observation that most medical documents are
assigned no more than 20 codes. For example, the macro precision is calculated
as the overall average precision across all labels, given by:

$\small\text{ Macro-Precision
}=\frac{1}{m}\sum_{\ell=1}^{m}\frac{\mathrm{TP}_{\ell}}{\mathrm{TP}_{\ell}+\mathrm{FP}_{\ell}},$

where $\mathrm{TP}_{\ell}$ and $\mathrm{FP}_{\ell}$ are the numbers of true
and false positives of code $\ell$. Micro scores give more weight to frequent
labels by considering all labels jointly. For example, the micro precision is
defined as:

$\small\text{ Micro-Precision
}=\frac{\sum_{\ell=1}^{m}\mathrm{TP}_{\ell}}{\sum_{\ell=1}^{m}\mathrm{TP}_{\ell}+\mathrm{FP}_{\ell}}.$

###  4.1 Pretraining in Close Domains Improves Prediction (RQ1)

Table 3: Effect of more pretraining data with BERT-hier \+ LAN on MIMIC-III dataset with top-50 and full ICD codes. Clinical notes are truncated at length of 2500. Bold text denotes better performance. Model | MIMIC-III Top-50 Codes | MIMIC-III Full Codes
---|---|---
AUC-ROC | F1 | P@5 | AUC-ROC | F1 | P@8 | P@15
Macro | Micro | Macro | Micro | Macro | Micro | Macro | Micro
PubMedBERT abstract | 90.1 | 92.5 | 62.3 | 67.0 | 63.8 | 85.2 | 97.1 | 5.8 | 37.5 | 66.6 | 50.4
PubMedBERT full text | 88.6 | 90.8 | 63.3 | 68.1 | 64.0 | 87.4 | 98.1 | 4.3 | 44.5 | 65.2 | 51.7
BioBERT abstract | 89.4 | 91.6 | 59.5 | 64.8 | 62.7 | 84.5 | 97.3 | 6.3 | 46.5 | 65.3 | 50.0
BioBERT full text | 88.8 | 91.7 | 60.4 | 66.0 | 63.1 | 85.2 | 97.4 | 6.4 | 47.0 | 65.8 | 50.7
ClinicalBERT disch. sum. | 88.7 | 91.4 | 60.6 | 65.9 | 62.6 | 82.9 | 96.6 | 6.2 | 45.0 | 63.8 | 48.7
ClinicalBERT all notes | 89.2 | 91.6 | 59.5 | 64.8 | 62.0 | 84.7 | 97.4 | 6.0 | 46.6 | 65.1 | 49.9

This section studies pretraining in different domains (Sec. 3.1) to evaluate
which pretraining scheme works best for medical coding in the clinical domain.
Results on MIMIC-III top-50 and full code set are shown in Table 2, where
hierarchical fine-tuning architecture is used. Overall, pretraining in mixed
domains improves predictive performance to some extent over the BERT-base
pretrained in general domains. These results show the effectiveness of
transfer learning to enhance the learning capacity on downstream tasks. Among
all pretrained models from various domains, PubMedBERT pretrained from scratch
on biomedical article corpora gains a comparatively better performance.
Specifically, it leads to improvements of 3.9% and 3.3% for F1 macro and micro
scores on the MIMIC-III top-50 code set. One possible explanation is that
specific domain pretraining makes downstream classifier concentrate on
specified semantic knowledge. While for ClinicalBERT with three types of
domain, the model’s attention may be distracted from relatively broad
information. However, it still performs better than BERT-base with semantic
knowledge only from general domains.

###  4.2 Effect of Pretraining with More Data (RQ1)

Can a larger pool of unsupervised pretraining data lead to performance gain in
downstream clinical prediction? To answer this question, we conduct
experiments on the effect of more pretraining data using three groups of
pretrained model. In the biomedical domain, there are 200K abstracts from
PubMed and 270K full-text articles from PubMedCentral. For the clinical
domain, The CATEGORY value of the MIMIC-III dataset includes ‘Discharge
Summary’, ‘ECG’, ‘Radiology’, and ‘Echo’. ‘Discharge summary’ indicates that
the note is a discharge summary. Besides, there are also other free-text
notes. For example, ‘Report’ indicates a full report, and ‘Addendum’ indicates
an additional text added to the previous report.

The results with BERT-hier fine-tuning architecture on two sets of the MIMIC-
III dataset are shown in Table 3. We also study the effect using truncated
short notes with fully connected tuning architecture, with results reported in
Table 4. These two tables suggest that pretraining with more data leads to
better performance in most cases.

Table 4: Effect of more pretraining data with BERT-trun on MIMIC-III top-50 code set. Clinical notes truncated at length of 512. Bold text denotes better performance. Model | AUC-ROC | F1 | P@5
---|---|---|---
Macro | Micro | Macro | Micro
PubMedBERT abstract | 82.4 | 85.9 | 47.5 | 54.8 | 54.7
PubMedBERT full text | 82.1 | 84.4 | 52.6 | 57.3 | 55.7
BioBERT abstract | 80.9 | 83.6 | 48.9 | 54.8 | 54.0
BioBERT full text | 81.8 | 84.3 | 50.5 | 55.4 | 54.5
ClinicalBERT disch. sum. | 81.8 | 84.2 | 49.7 | 55.8 | 54.9
ClinicalBERT all notes | 82.3 | 85.3 | 50.6 | 56.9 | 55.7

###  4.3 Hierarchical Fine-Tuning Improves Prediction (RQ2)

This section answers to the second research question (RQ2) by comparing the
BERT-trun and BERT-hier fine-tuning architectures. Table 5 shows the results
on the MIMIC-III top-50 code set using the two fine-tuning architectures when
used either with a fully connected classifier or the label attention network.
Our results are slightly better than the preliminary results reported by
ji2021medical with appropriate training tricks. Mixed domain pretraining
models, such as PubMedBERT and ClinicalBERT, gain increases in evaluation
scores. However, most BERT-trun variants’ predictive performance suffers due
to the lack of information when long notes are truncated into short ones.
These results show that the proposed hierarchical fine-tuning architecture
effectively utilizes long sequences and boosts performance. The label-wise
attention mechanism can further improve the prediction in most cases.

###  4.4 Reproducing CNN Outperforms Advanced Methods on Frequent Codes (RQ3)

Several recent advances for medical code assignment are CNN-based models. This
section investigates whether improved training of CNN can improve prediction.
Inspired by performance improvement owing to training tricks, we reproduce the
CNN model to check if appropriate training strategies can lead to better
scores.

#### Baselines.

CNN [Kim, 2014] is built on pre-trained word vectors with 1D convolution and
max-pooling for text classification. CAML [Mullenbach et al., 2018] integrates
CNNs and a label-wise attention mechanism to learn rich representations. It
has a variant called DR-CAML that uses ICD code descriptions to regularize the
loss function. MultiResCNN [Li and Yu, 2020] combines residual learning [He et
al., 2016] and multiple channels concatenation with different convolutional
filters, achieving good performance in most settings. HyperCore [Cao et al.,
2020] utilizes hyperbolic embedding and co-graph representation with code
hierarchy. It gains slightly better performance than the MultiResCNN.

#### Reproducing CNNs.

Table 6 shows the reproduced results compared with baselines. The hyper-
parameters are as follows: the learning rate is 0.003, the filter size is 4,
the number of filters is 500, the dropout probability is 0.2, and word2vec
embeddings are static. Our retrained vanilla CNN gains a better performance
compared with two recent advanced MultiResCNN [Li and Yu, 2020] and HyperCore
[Cao et al., 2020] on the MIMIC-III top-50 code dataset. Moreover, the P@15
score of the retrained CAML model leads to a significant performance increase
in the MIMIC-III full code dataset. These results suggest that a simple model
with appropriate training could achieve decent performance in NLP applications
such as this clinical application.

Table 5: Results on MIMIC-III top-50 code set fine-tuning with BERT-trun and BERT-hier with FCN or LAN. Model | AUC-ROC | F1 | P@5
---|---|---|---
Macro | Micro | Macro | Micro
BERT-base-trun + FCN | 80.1 | 83.0 | 46.3 | 51.6 | 51.1
BERT-base-hier + FCN | 85.4 | 88.4 | 53.1 | 59.4 | 57.6
BERT-base-hier + LAN | 83.7 | 86.5 | 48.1 | 54.2 | 53.5
BlueBERT-trun + FCN | 78.2 | 82.1 | 23.7 | 36.6 | 45.9
BlueBERT-hier + FCN | 89.1 | 91.8 | 59.9 | 65.1 | 62.5
BlueBERT-hier + LAN | 89.4 | 92.0 | 61.0 | 65.6 | 62.8
BioBERT-trun + FCN | 81.8 | 84.3 | 50.5 | 55.4 | 54.5
BioBERT-hier + FCN | 87.3 | 89.5 | 59.9 | 65.6 | 62.7
BioBERT-hier + LAN | 88.8 | 91.7 | 60.4 | 66.0 | 63.1
BioRedditBERT-turn + FCN | 80.7 | 83.5 | 49.3 | 55.5 | 53.8
BioRedditBERT-hier + FCN | 87.0 | 89.4 | 59.1 | 64.2 | 61.9
BioRedditBERT-hier + LAN | 87.1 | 89.6 | 59.4 | 64.8 | 62.4
PubMedBERT-trun + FCN | 82.1 | 84.4 | 52.6 | 57.3 | 55.7
PubMedBERT-hier + FCN | 88.8 | 91.4 | 57.7 | 64.2 | 62.2
PubMedBERT-hier + LAN | 88.6 | 90.8 | 63.3 | 68.1 | 64.4
SapBERT-trun + FCN | 82.3 | 84.8 | 51.2 | 56.8 | 55.2
SapBERT-hier + FCN | 88.5 | 90.3 | 63.3 | 67.3 | 63.8
SapBERT-hier + LAN | 88.5 | 90.8 | 62.2 | 66.7 | 63.1
ClinicalBERT-trun + FCN | 82.3 | 85.3 | 50.6 | 56.9 | 55.7
ClinicalBERT-hier + FCN | 87.2 | 90.7 | 54.6 | 62.5 | 60.7
ClinicalBERT-hier + LAN | 89.2 | 91.6 | 59.5 | 64.8 | 62.0

How did the CNN- and BERT-based models perform on the full code set? We bin
ICD codes into different groups according to the frequency observed in the
training set of the MIMIC-III full code dataset to study the effect of code
frequency on the model’s predictive performance. We take ClinicalBERT as a
clinical note encoding representative and compare three fine-tuning strategies
with CNN and CAML model. Fig. 3 shows models’ predictive behavior on frequent
and less frequent codes taking F1 scores as the evaluation metrics. These two
figures show that all compared models’ predictive performance decreases when
the ICD code groups have fewer training samples. When dealing with few-shot
codes, model performance drops sharply. These results again suggest that
medical code prediction algorithms should focus on less frequent codes and
enhance the robustness of less frequent codes.

(a) F1 macro

(b) F1 micro

Figure 3: F1 scores of different models on the MIMIC-III full code dataset (8,922 labels). Code frequency groups are sorted in ascending order from left to right. Table 6: Results of retrained CNNs on MIMIC-III with top-50 and full ICD codes. Bold text denotes the new state of the art obtained by an old model. Model | MIMIC-III Top-50 Codes | MIMIC-III Full Codes
---|---|---
AUC-ROC | F1 | P@5 | AUC-ROC | F1 | P@8 | P@15
Macro | Micro | Macro | Micro | Macro | Micro | Macro | Micro
CNN [Kim, 2014] | 87.6 | 90.7 | 57.6 | 62.5 | 62.0 | 80.6 | 96.9 | 4.2 | 41.9 | 58.1 | 44.3
CAML [Mullenbach et al., 2018] | 87.5 | 90.9 | 53.2 | 61.4 | 60.9 | 89.5 | 98.6 | 8.8 | 53.9 | 70.9 | 44.5
MultiResCNN [Li and Yu, 2020] | 89.9 | 92.8 | 60.6 | 67.0 | 64.1 | 91.0 | 98.6 | 8.5 | 55.2 | 73.4 | 58.4
HyperCore [Cao et al., 2020] | 89.5 | 92.9 | 60.9 | 66.3 | 63.2 | 93.0 | 98.9 | 9.0 | 55.1 | 72.2 | 57.9
CNN (retrained) | 90.8 | 93.1 | 62.4 | 67.1 | 64.0 | 85.0 | 97.4 | 5.9 | 36.5 | 49.0 | 39.4

###  4.5 Discussion

Pretrained models in both general and specific domains have shown
effectiveness in capturing contextual information. However, they encounter
limitations in this study. In the dataset with top-50 frequent codes, fine-
tuning with pretrained models can achieve a good performance; however, the PTM
fine-tuning does not work well for high-dimensional structured prediction with
a full label set that has more than 8,000 labels. This study suggests focusing
on less frequent codes.

Self attention-based models suffer from the complexity of $O(n^{2}d)$, where
$n$ is the sequence length, and $d$ is the dimension of hidden representation,
making it hard to encode extremely long documents. We investigated how to
incorporate the pretrained BERT model and its variants with hierarchical fine-
tuning architecture to tackle lengthy clinical document encoding.
Nevertheless, CNN-based models [Mullenbach et al., 2018, Li and Yu, 2020, Ji
et al., 2020a] and RNN-based models [Shi et al., 2017] perform considerably
well with the relatively small model scale and remain a meaningful direction.
Recently, some improved transformer-based models such as Longformer [Beltagy
et al., 2020], Linformer [Wang et al., 2020] and Big Bird [Zaheer et al.,
2020] aim to solve the problem of encoding long document and mitigating the
quadratic complexity. We leave these emerging models as future work.

##  5 Conclusion

This paper presented a comprehensive quantitive analysis of medical code
assignment from clinical notes using various pretrained models with BERT. We
compared the behavior of several different domain-specific BERT variants. To
solve the problem of lengthy clinical note encoding, we developed two fine-
tuning architectures: 1) fully connected network with simple truncation into
short notes; 2) hierarchical fine-tuning architecture with long note
segmentation and an additional Transformer on top. Moreover, we employed label
attention to facilitate label-aware representation learning. Through intensive
experiments, we found that the magic of BERT does not apply to the task of
assigning ICD codes from clinical notes. In contrast, we found that a simple
CNN trained from scratch can achieve superior predictive performance on
frequent codes, achieving a new state of the art in the MIMIC-III top-50
dataset. This demonstrates how recent training strategies can improve old
models. Our results furthermore suggest that medical code assignment
algorithms should pay more attention to less frequent codes.

## Acknowledgments

This work was supported by the Academy of Finland (grant 336033) and EU H2020
(grant 101016775). We acknowledge the computational resources provided by the
Aalto Science-IT project. The authors wish to acknowledge CSC - IT Center for
Science, Finland, for computational resources.

## References

  * Alsentzer et al. [2019] E. Alsentzer, J. Murphy, W. Boag, W.-H. Weng, D. Jindi, T. Naumann, and M. McDermott.  Publicly Available Clinical BERT Embeddings.  In _Proceedings of the 2nd Clinical Natural Language Processing Workshop_ , pages 72–78, 2019.
  * Bai and Vucetic [2019] T. Bai and S. Vucetic.  Improving Medical Code Prediction from Clinical Text via Incorporating Online Knowledge Sources.  In _The World Wide Web Conference_ , pages 72–82, 2019.
  * Basaldella et al. [2020] M. Basaldella, F. Liu, E. Shareghi, and N. Collier.  COMETA: A Corpus for Medical Entity Linking in the Social Media.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics, 2020\.
  * Baumel et al. [2018] T. Baumel, J. Nassour-Kassis, R. Cohen, M. Elhadad, and N. Elhadad.  Multi-label Classification of Patient Notes: Case Study on ICD Code Assignment.  In _Workshops at the Thirty-Second AAAI Conference on Artificial Intelligence_ , 2018.
  * Beltagy et al. [2020] I. Beltagy, M. E. Peters, and A. Cohan.  Longformer: The Long-Document Transformer.  _arXiv preprint arXiv:2004.05150_ , 2020.
  * Cao et al. [2020] P. Cao, Y. Chen, K. Liu, J. Zhao, S. Liu, and W. Chong.  HyperCore: Hyperbolic and Co-graph Representation for Automatic ICD Coding.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 3105–3114, 2020.
  * Crammer et al. [2007] K. Crammer, M. Dredze, K. Ganchev, P. Talukdar, and S. Carroll.  Automatic Code Assignment to Medical Text.  In _Biological, Translational, and Clinical language processing_ , pages 129–136, 2007.
  * Devlin et al. [2019] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  In _NAACL-HLT_ , 2019.
  * Dong et al. [2020] H. Dong, V. Suárez-Paniagua, W. Whiteley, and H. Wu.  Explainable Automated Coding of Clinical Notes using Hierarchical Label-wise Attention Networks and Label Embedding Initialisation.  _arXiv preprint arXiv:2010.15728_ , 2020.
  * Erhan et al. [2010] D. Erhan, Y. Bengio, A. Courville, P.-A. Manzagol, P. Vincent, and S. Bengio.  Why Does Unsupervised Pre-training Help Deep Learning?  _Journal of Machine Learning Research_ , 11:625–660, 2010\.
  * Falis et al. [2019] M. Falis, M. Pajak, A. Lisowska, P. Schrempf, L. Deckers, S. Mikhael, S. Tsaftaris, and A. O’Neil.  Ontological attention ensembles for capturing semantic concepts in ICD code prediction from clinical text.  In _Proceedings of the Tenth International Workshop on Health Text Mining and Information Analysis (LOUHI 2019)_ , pages 168–177, 2019.
  * Farkas and Szarvas [2008] R. Farkas and G. Szarvas.  Automatic Construction of Rule-based ICD-9-CM Coding Systems.  In _BMC Bioinformatics_ , volume 9(Suppl 3), pages 1–9. Springer, 2008.
  * Farzandipour et al. [2010] M. Farzandipour, A. Sheikhtaheri, and F. Sadoughi.  Effective Factors on Accuracy of Principal Diagnosis Coding based on International Classification of Diseases, the 10th Revision (ICD-10).  _International Journal of Information Management_ , 30(1):78–84, 2010.
  * Gu et al. [2020] Y. Gu, R. Tinn, H. Cheng, M. Lucas, N. Usuyama, X. Liu, T. Naumann, J. Gao, and H. Poon.  Domain-specific language model pretraining for biomedical natural language processing.  _arXiv preprint arXiv:2007.15779_ , 2020.
  * Gururangan et al. [2020] S. Gururangan, A. Marasović, S. Swayamdipta, K. Lo, I. Beltagy, D. Downey, and N. A. Smith.  Don’t stop pretraining: Adapt language models to domains and tasks.  In _ACL_ , 2020.
  * He et al. [2016] K. He, X. Zhang, S. Ren, and J. Sun.  Deep Residual Learning for Image Recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * Howard and Ruder [2018] J. Howard and S. Ruder.  Universal language model fine-tuning for text classification.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 328–339, 2018.
  * Hsia et al. [1988] D. C. Hsia, W. M. Krushat, A. B. Fagan, J. A. Tebbutt, and R. P. Kusserow.  Accuracy of Diagnostic Coding for Medicare Patients under the Prospective-payment System.  _New England Journal of Medicine_ , 318(6):352–355, 1988.
  * Huang et al. [2019] K. Huang, J. Altosaar, and R. Ranganath.  ClinicalBERT: Modeling clinical notes and predicting hospital readmission.  _arXiv preprint arXiv:1904.05342_ , 2019.
  * Ji et al. [2020a] S. Ji, E. Cambria, and P. Marttinen.  Dilated Convolutional Attention Network for Medical Code Assignment from Clinical Text.  In _3rd Clinical Natural Language Processing Workshop at EMNLP_ , 2020a.
  * Ji et al. [2020b] S. Ji, S. Pan, and P. Marttinen.  Medical code assignment with gated convolution and note-code interaction.  _arXiv preprint arXiv:2010.06975_ , 2020b.
  * Johnson et al. [2016] A. E. Johnson, T. J. Pollard, L. Shen, H. L. Li-wei, M. Feng, M. Ghassemi, B. Moody, P. Szolovits, L. A. Celi, and R. G. Mark.  MIMIC-III, a Freely Accessible Critical Care Database.  _Scientific Data_ , 3:160035, 2016.
  * Kim [2014] Y. Kim.  Convolutional Neural Networks for Sentence Classification.  _arXiv preprint arXiv:1408.5882_ , 2014.
  * Kingma and Ba [2014] D. P. Kingma and J. Ba.  Adam: A Method for Stochastic Optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Lee et al. [2020] J. Lee, W. Yoon, S. Kim, D. Kim, S. Kim, C. H. So, and J. Kang.  BioBERT: a pre-trained biomedical language representation model for biomedical text mining.  _Bioinformatics_ , 36(4):1234–1240, 2020.
  * Li and Yu [2020] F. Li and H. Yu.  ICD Coding from Clinical Text Using Multi-Filter Residual Convolutional Neural Network.  In _Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence_ , 2020.
  * Liu et al. [2020] F. Liu, E. Shareghi, Z. Meng, M. Basaldella, and N. Collier.  Self-alignment pre-training for biomedical entity representations.  _arXiv preprint arXiv:2010.11784_ , 2020.
  * Loshchilov and Hutter [2019] I. Loshchilov and F. Hutter.  Decoupled weight decay regularization.  In _International Conference on Learning Representations_ , 2019.
  * Medori and Fairon [2010] J. Medori and C. Fairon.  Machine Learning and Features Selection for Semi-automatic ICD-9-CM Encoding.  In _Proceedings of the NAACL HLT 2010 Second Louhi Workshop on Text and Data Mining of Health Documents_ , pages 84–89. Association for Computational Linguistics, 2010.
  * Mikolov et al. [2013] T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean.  Distributed Representations of Words and Phrases and their Compositionality.  In _Advances in neural information processing systems_ , pages 3111–3119, 2013.
  * Mullenbach et al. [2018] J. Mullenbach, S. Wiegreffe, J. Duke, J. Sun, and J. Eisenstein.  Explainable Prediction of Medical Codes from Clinical Text.  In _Proceedings of NAACL-HLT_ , pages 1101–1111, 2018.
  * Mulyar et al. [2019] A. Mulyar, E. Schumacher, M. Rouhizadeh, and M. Dredze.  Phenotyping of Clinical Notes with Improved Document Classification Models Using Contextualized Neural Language Models.  _arXiv preprint arXiv:1910.13664_ , 2019.
  * Peng et al. [2019] Y. Peng, S. Yan, and Z. Lu.  Transfer Learning in Biomedical Natural Language Processing: An Evaluation of BERT and ELMo on Ten Benchmarking Datasets.  In _Proceedings of the 18th BioNLP Workshop and Shared Task_ , pages 58–65, 2019.
  * Perotte et al. [2014] A. Perotte, R. Pivovarov, K. Natarajan, N. Weiskopf, F. Wood, and N. Elhadad.  Diagnosis Code Assignment: Models and Evaluation Metrics.  _Journal of the American Medical Informatics Association_ , 21(2):231–237, 2014.
  * Prakash et al. [2017] A. Prakash, S. Zhao, S. A. Hasan, V. Datla, K. Lee, A. Qadir, J. Liu, and O. Farri.  Condensed Memory Networks for Clinical Diagnostic Inferencing.  In _Thirty-First AAAI Conference on Artificial Intelligence_ , 2017\.
  * Shi et al. [2017] H. Shi, P. Xie, Z. Hu, M. Zhang, and E. P. Xing.  Towards Automated ICD Coding Using Deep Learning.  _arXiv preprint arXiv:1711.04075_ , 2017.
  * Stanfill et al. [2010] M. H. Stanfill, M. Williams, S. H. Fenton, R. A. Jenders, and W. R. Hersh.  A Systematic Literature Review of Automated Clinical Coding and Classification systems.  _Journal of the American Medical Informatics Association_ , 17(6):646–651, 2010.
  * Vaswani et al. [2017] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin.  Attention is all you need.  In _Advances in neural information processing systems_ , pages 5998–6008, 2017.
  * Wang et al. [2020] S. Wang, B. Li, M. Khabsa, H. Fang, and H. Ma.  Linformer: Self-Attention with Linear Complexity.  _arXiv preprint arXiv:2006.04768_ , 2020.
  * Xie and Xing [2018] P. Xie and E. Xing.  A neural architecture for automated icd coding.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1066–1076, 2018\.
  * Xipeng et al. [2020] Q. Xipeng, S. TianXiang, X. Yige, S. Yunfan, D. Ning, and H. Xuanjing.  Pre-trained models for natural language processing: A survey.  _SCIENCE CHINA Technological Sciences_ , 63:1872–1897, 2020\.
  * Zaheer et al. [2020] M. Zaheer, G. Guruganesh, A. Dubey, J. Ainslie, C. Alberti, S. Ontanon, P. Pham, A. Ravula, Q. Wang, L. Yang, et al.  Big Bird: Transformers for Longer Sequences.  _arXiv preprint arXiv:2007.14062_ , 2020.
  * Zhang et al. [2020] D. Zhang, J. Thadajarassiri, C. Sen, and E. Rundensteiner.  Time-Aware Transformer-based Network for Clinical Notes Series Prediction.  In _Machine Learning for Healthcare Conference_ , pages 566–588. PMLR, 2020.
  * Zhu et al. [2015] Y. Zhu, R. Kiros, R. Zemel, R. Salakhutdinov, R. Urtasun, A. Torralba, and S. Fidler.  Aligning books and movies: Towards story-like visual explanations by watching movies and reading books.  In _Proceedings of the IEEE international conference on computer vision_ , pages 19–27, 2015.