# Communication Body-UAV Near-Ground LoRa Links through a Mediterranean Forest

Giulio Maria Bianco, and Gaetano Marrocco Submitted for review on XX Month
20XX.G. M. Bianco is with the Department of Civil Engineering and Computer
Science Engineering of the University of Rome Tor Vergata, Rome, Italy
(e-mail: giulio.maria.bianco@uniroma2.it).G. Marrocco is with the Department
of Civil Engineering and Computer Science Engineering of the University of
Rome Tor Vergata, Rome, Italy (e-mail: gaetano.marrocco@uniroma2.it).

###### Abstract

LoRa low-power wide-area network protocol has recently gained attention for
deploying ad-hoc search and rescue (SaR) systems. They could be empowered by
exploiting body-UAV links that enable communications between a body-worn radio
and a UAV-mounted one. However, to employ UAVs effectively, knowledge of the
signal’s propagation in the environment is required. Otherwise, communications
and localization could be hindered. The radio range, the packet delivery ratio
(PDR), and the large- and small-scale fading of body-UAV LoRa links at
$\mathbf{868}$ MHz when the radio wearer is in a Mediterranean forest are here
characterized for the first time with a near-ground UAV having a maximum
flying height of $\mathbf{30}$ m. A log-distance model accounting for the body
shadowing and the wearer’s movements is derived. Over the full LoRa radio
range of about $\mathbf{600}$ m, the new model predicts the path loss (PL)
better than the state-of-the-art ones, with a reduction of the median error
even by $\sim\mathbf{10}$ dB. The observed small-scale fading is severe and
follows a Nakagami-m distribution. Extensions of the model for similar
scenarios can be drawn through appropriate corrective factors.

###### Index Terms:

Aerial communication, LoRa, off-body links, path loss, UAV, wearable antennas.

##  I Introduction

LoRa is a convenient low-power wide-area network protocol that can enable
kilometric communications by low transmission power [1, 2, 3]. It is hence
extremely promising for fostering search and rescue (SaR) missions [4] that
usually take place in harsh environments like mountains [5], disaster areas
[6], and forests [7]. Forested areas, in particular, are challenging scenarios
for LoRa devices due to the detrimental effects of vegetation on path loss
(PL) [8, 9]. Indeed, the radio range is lowered down to a few hundred meters
independently from the selected transmission parameters [10, 11, 12]. Indirect
propagation can even be forbidden [13], and the PL heavily depends on the
density, type, and age of the vegetation [14].

To the authors’ best knowledge, even though terrestrial LoRa links in forests
were already investigated, air-ground (AG) links in such environments have
never been considered. Instead, unmanned aerial vehicles (UAVs) and systems
(UASs) are game-changing technologies for SaR missions. They could
dramatically increase the survival chances of the targets to be rescued by
avoiding terrestrial obstacles and speeding up operations through near-ground
flights having altitudes of tens of meters [15, 16]. Thus, body-UAV links,
viz., electromagnetic links between a body-worn device and a UAV [17], can
maximize the benefits of using wearable LoRa devices [18]. However, available
ground-UAV propagation models are not suitable for describing the signal
attenuation in forests since they are tuned for urban environments mainly and
do not account for the presence and movements of the radio wearer.

By expanding the preliminary results in [19], this paper presents for the
first time the characterization of low-altitude body-UAV LoRa non-line-of-
sight (NLoS) links through a Mediterranean forest (Fig. 1). In the considered
scenario, the user wearing a LoRa receiver is moving inside the forest, while
a SaR quadcopter, equipped with a LoRa transmitter, is hovering just outside
the forest. Near-ground altitudes ($h\leq 30$ m) are considered to reproduce
fast, on-site deployment of a low-cost drone that broadcasts emergency
signals, can be carried by terrestrial SaR teams, and could swiftly become
unstable, displace or discharge due to turbulent winds if its altitude is not
low enough [20]. As body-UAV links combine AG and off-body links, the derived
empirical model includes the equivalent gain of the on-body antenna and the
polarization losses, and it is compared with existing AG models.

Figure 1: Sketch and parameters of the propagation scenario for a body-UAV
LoRa communication through a Mediterranean forest.

##  II Methods and Instrumentation

###  II-A Body-UAV Propagation Modeling

The PL of channels involving a terrestrial radio and a low-flying UAV is here
modelled by a log-distance representation which depends on the flying height
of the UAV [21, 22]. This approach avoids the use of a reference terrestrial
PL [23]. Furthermore, off-body links need to account for the variable Tx-Rx
angular arrangements and the movements of the radio’s wearer. The gain of the
body-worn antenna and the polarization losses are hereafter taken into account
using a numerical-statistical approach [18], as detailed in §II-B, whereas the
movements can cause unpredictable body shadowing and polarization losses and,
thus, additional fluctuations of the signal’s strength.

With reference to Fig. 1, for a given frequency and indirect propagation, the
AG link is parametrized [21] as

$PL_{m}\left(d_{3D},h\right)=PL_{m}\left(d_{0}\right)+10\gamma\cdot\log_{10}\left(d_{3D}\right)-\eta
h,$ (1)

where $PL_{m}$ is the mean PL, $d_{3D}$ is the Tx-Rx tridimensional distance
between man and UAV, $h$ is the UAV flying height, $d_{0}$ is a reference
distance in the far-field of the transmitter ($d_{0}=1$ m in the following),
$\gamma$ is the path loss exponent, and $\eta$ is the altitude impact factor.
The parameters fitting the experimental data are hence
$\left\\{PL\left(d_{0}\right),\gamma,\eta\right\\}$.

Small- and large-scale fluctuations are accounted for by the instantaneous
path loss ($PL_{i}$). The small-scale fading $f_{sm}$ includes the
fluctuations within the order of a wavelength $\lambda$ [8] and can be
filtered out by means of a $\pm\lambda/2$ moving window average [21]. $PL_{m}$
is derived by application of least-square fitting to the PL measurements
through (1) after the removal of the small-scale fading. Finally, a zero-mean
gaussian shadow fading with standard deviation $\sigma_{SF}$ [21] models the
remaining large-scale differences between the instantaneous and the mean PL.
The $PL_{i}$ is hence written as

$PL_{i}\left(d_{3D},h\right)=PL_{m}\left(d_{3D},h\right)+f_{sm}+\mathcal{N}\left(0,\sigma_{SF}\right).$
(2)

$PL_{i}\left(d_{3D},h\right)$ is derived from the received signal strength
indicator (RSSI) and signal-to-noise ratio (SNR) recorded by the receiver LoRa
board [18, 3] as

$PL_{i}\left(d_{3D},h\right)=P_{Tx}+G_{Tx}+G_{Rx}+\chi+\\\
+10\cdot\log_{10}\left(1+\frac{1}{SNR}\right)-RSSI$ (3)

being $P_{Tx}$ the transmission power, $\chi$ the polarization loss factor
(PLF) between the Tx and Rx antennas, and $G_{Tx}$ and $G_{Rx}$ the
corresponding radiation power gains. The PL calculated in (1) and (2) and all
the terms in (3) are exposed in the dB scale except for the SNR, which is in
the linear scale.

Since the resulting model fits experimental data, it will be accurate under
the same environmental conditions as during the data collection. Nevertheless,
different conditions that can affect the signal’s strength and increase the
difference with the expected PL can be accounted for by an appropriate
corrective factor $\xi$ of the $PL_{m}$ computed according to (1). The refined
estimation of the median path loss ($PL_{m}^{\prime}$) can be hence expressed
as

$PL_{m}^{\prime}\left(d_{3D},h\right)=PL_{m}\left(d_{3D},h\right)+\xi.$ (4)

The corrective factor can be parametrized regarding the difference of RSSI
($\Delta RSSI$) and SNR ($\Delta SNR$) between the values in the new
conditions and the reference ones

$\xi\left(\Delta RSSI,SNR,\Delta SNR\right)=-\Delta RSSI+\\\
+10\cdot\log_{10}\left[1+10^{-\left(SNR+\Delta SNR\right)/10}\right]$ (5)

where all the terms in (4) and (5) are in the dB scale. As reported by the
literature on LoRa, $\left\\{\Delta RSSI,\Delta SNR\right\\}$ could depend on
the type of vegetation (e.g., Malaysian palm [24], Japanese mountainous forest
[25], eastern China mixed forest [26]), season [27, 28, 29], weather [29, 30,
31] and the relative speed between the antennas yielding to significant
Doppler effect [32, 33].

(a) (b)

(c) (d)

Figure 2: Numerical simulations of the on-body receiver. (a) Phantom of the
body-worn antenna with the coordinate reference system. Polar plots of the
receiver’s gain according to the anatomical planes: (b) transverse and (c)
sagittal and coronal planes. (d) CCDF of $G_{Rx}$ and the PLF.

###  II-B Equivalent Gains and Polarization Losses

The computation of (3) requires estimating the parameters
$\\{G_{Tx},G_{Rx},\chi\\}$. Under the assumption that the radiation patterns
of the two antennas are not very directive and that the range of the relative
movements between them is limited, the gains of the transmitter and the
receiver are considered invariant with respect to their mutual orientation and
distance. In particular, the transmitter’s gain is fixed to $G_{Tx}=0$ dBi
since the position of the antenna onboard the UAV can be properly optimized to
provide a reasonable and uniform gain towards the ground. The receiver’s
effective gain and the PLF

$\chi=\left|\hat{\rho}_{Tx}\cdot\hat{\rho}_{Rx}^{*}\right|^{2}$ (6)

with ‘∗’ the conjugate operator, ‘$\cdot$’ the inner product, and
$\hat{\rho}_{Tx/Rx}$ the unitary polarization vector of the Tx/Rx, are instead
estimated through a statistical approach. The method is conservative and
accounts for the body shadowing by numerical simulations111Numerical
simulations performed through CST Microwave Studio $2018$. involving a
homogeneous anatomical phantom of the human body222The model is available at
https://grabcad.com/library/corpo-humano-masculino-adulto-by-jari-ikonen-
rev-01-1.. The phantom is made of muscle-like material (conductivity
$\sigma=1.56$ S/m-1; relative permittivity $\epsilon_{r}=51.6$; density $1055$
kg/m$3$ [34, 35]) and stands on an infinite, perfect electric conductor (PEC)
ground. The simulated LoRa dipole (a $1$-mm-wide and $35$-$\mu$m-thick copper
trace long $155$ mm; Fig. 2(a)) is placed at $5$ mm from the skin, as it was
in a pocket during the experiments. Both the transmitting and receiving
dipoles form a $30^{\textnormal{o}}$-angle with the planes parallel to the
ground so that i) nulls in the radiation pattern of the dipoles are not
expected along the ray path, ii) the dipoles’ axes stay parallel for maximum
polarization coupling, and iii) movements of the UAV’s rotors are not
hindered.

Table I: Employed LoRa’s transmission parameters. Transmission |  | Transmission |
---|---|---|---
parameter | Value | parameter | Value
Transmission power |  $14$ dBm | Bandwidth |  $125$ kHz
Carrier frequency |  $868$ MHz | Coding rate | $4/5$
Spreading factor | $7$ | Message rate |  $4^{-1}$ msg/sec

(a) |  (b)
---|---

(c)

Figure 3: UAV equipped with the LoRa transmitter: (a) side and (b) top view. (c) Satellite view of the forested area. The position of the hovering UAV and the path walked by the volunteer are highlighted. Table II: Maximum observed communication range and PDRs for the three flying heights of the UAV. |  $\mathbf{h=3}$ m |  $\mathbf{h=10}$ m |  $\mathbf{h=30}$ m
---|---|---|---
Radio range |  $597$ m |  $676$ m |  $589$ m
PDR | $93.7\%$ | $91.9\%$ | $91.0\%$
Table III: Path loss model parameters for body-UAV links. | Mediterranean | 3GPP UMa | 3GPP UMa | 3GPP UMi | Cui’s NLoS
---|---|---|---|---|---
Model | forest (this work) | TR 38.901 [22] | TR 38.901 optional [22] | TR 38.901 [22] | ($\mathbf{1}$ GHz) [21]
PL exponent $\gamma$ | $4.19$ | $3.91$ | $3.00$ | $3.53$ | $2.00$
PL intercept $\mathbf{PL(1}$ m$\mathbf{)}$ |  $10.69$ dB |  $13.21$ dB |  $31.17$ dB |  $21.54$ dB |  $61.18$ dB
Altitude impact factor $\eta$ |  $0.12$ $\textnormal{dB}\left(\textnormal{m}\right)^{-1}$ |  $0.60$ $\textnormal{dB}\left(\textnormal{m}\right)^{-1}$ | Absent |  $0.30$ $\textnormal{dB}\left(\textnormal{m}\right)^{-1}$ |  $1.19$ $\textnormal{dB}\left(\textnormal{m}\right)^{-1}$
Shadow fading $\sigma_{SF}$ |  $8.05$ dB |  $6.00$ dB |  $7.80$ dB |  $7.82$ dB |  $3.60$ dB
Median difference |  |  |  |  |
with measurements |  $\mathbf{7.34}$ dB |  $14.96$ dB |  $11.44$ dB |  $13.37$ dB |  $17.00$ dB

$G_{Rx}$ and $\chi$ are computed over the half-space free from the PEC ground
(i.e., $0^{\textnormal{o}}\leq\phi\leq 180^{\textnormal{o}}$) with a
$1^{\textnormal{o}}$ resolution. Fig. 2(b,c) show the polar plots of the gain
over the three principal anatomical planes. Then, the effective values to be
used in (3) are derived from complementary cumulative distribution functions
(CCDFs) as the minimum value that is guaranteed in $75\%$ of the Tx-Rx angular
arrangements. The receiver’s versor is obtained from simulations, whilst
constant
$\hat{\rho}_{Tx}=-\cos\left(30^{\textnormal{o}}\right)\hat{x}+\sin\left(30^{\textnormal{o}}\right)\hat{y}$
is considered for the transmitter. Overall, the values
$G_{Rx}\left(CCDF=75\%\right)=-11.0$ dBi and $\chi\left(CCDF=75\%\right)=-6.2$
dB (Fig. 2(d)) are finally inserted in (3) to derive $PL_{i}$. The resulting
PL model will account for the residual variability that is not captured by
this approximation.

###  II-C Link Characterization

The link is characterized based on i) the maximum communication range, ii) the
packet delivery ratio (PDR; the ratio between received and sent packets), iii)
the large-scale fading and iv) the small-scale fluctuations. The large-scale
fading comprises the mean PL and the large-scale fluctuations.

As mentioned above, this work considers the rapid changes of the signal
strength over a short distance on the order of a wavelength [8, 36] as small-
scale fading. This is a crucial phenomenon for predicting outage probability
since such fading can be as high as $40$ dB [36] and can follow several
different statistical distributions. According to [21], the small-scale
fluctuations are analyzed with a spatial moving average and by fitting its
empirical statistical distribution using a set of trial fits, viz., log-
logistic, Nakagami-m, Weibull, Rayleigh, and Rician. The fade depth is the
difference (in decibel scale) of small-scale signal fading between the $50$%
and $99$% levels, which are computed as in [37], and denotes the possible
expected fluctuations.

The statistical validity of the estimated PL (EPL) model is verified by
calculating the relative standard error of the mean (RSE) for each
$\\{d_{3D},h\\}$ pair as [23]

$RSE_{PL_{m}}\left(d_{3D},h\right)=\sigma_{SF}\left[\sqrt{M\left(d_{3D},h\right)}PL_{m}\left(d_{3D},h\right)\right]^{-1}$

(7)

being $M\left(d_{3D},h\right)$ the number of $PL_{i}\left(d_{3D},h\right)$
measurements averaged, after subtracting the small-scale fading, to obtain a
measurement of the large-scale PL for each pair.

Finally, to assess the improvement in accuracy of the PL prediction, the
derived EPL is compared with known AG models suitable for LoRa indirect
propagation. The considered models are i) 3GPP urban macrocell (UMa) NLoS
[22], ii) 3GPP optional UMa NLoS model [22], iii) 3GPP optional urban
microcell (UMi) [22], and iv) Cui’s NLoS model at $1$ GHz [21]. These models
that describe large-scale fading are optimized for urban scenarios and assume
a fixed terrestrial radio. The accuracy of each model is evaluated by
considering the difference between the EPL and $PL_{i}$.

###  II-D Measurement Set-Up

The experimental LoRa system comprises two LoPy-4 boards (by Pycom; datasheet
available online [38]) connected to commercial half-wavelength dipoles. The
LoRa transmission parameters (Table I) maximize the RSS seen by the UAV and
the message rate in compliance with the European duty-cycle limitations [3].
The UAV is a low-cost quadcopter for fast deployment (FreeX model by Only
Flying Machines). The transmitting board is fixed to the quadcopter (Fig.
3(a,b)), while the body-worn receiver is tied in the pocket of the jacket of a
volunteer. The dipoles form the same $30^{\textnormal{o}}$-angle with the
ground as in the simulations.

The forest for the experiment is in Colle Romito (Ardea, Lazio, Italy; maximum
extension $\sim 720$ m; GPS coordinates $41^{\textnormal{o}}33^{\prime}01.9"$N
$12^{\textnormal{o}}35^{\prime}08.4"$E) and is mostly composed of poplars
(scientific name ”Populus tremula”). The trees are young adults, not pruned,
and approximately $10$ m tall. All measurements were completed on sunny days
(relative humidity $\sim 30$%, temperature $\sim 25$ Celsius). The Doppler
effect was neglected as the maximum relative speed between the antennas was
about $1$ m/s. Overall, about $1300$ data were collected during the
measurements.

The transmitting UAV hovered at the limit of the forest, at a fixed flying
height, without moving. In this way, there is some flexibility in enforcing
the hovering height when transmitting emergency signals to warn and group
people in the area [3], e.g., in the case of wildfires. The GPS-tracked
volunteer was slowly walking along a roughly straight path (Fig. 3(c)) inside
the forest. Trees, trunks, and other obstacles forced the wearer to deviate
slightly from the straight line path adding additional environmental
variability to the AG link. The Rx board simulated a radiofrequency wearable
device or mobile phone worn by a hiker. The RSSI and SNR values were stored on
an SD memory. Multiple flights were completed at three near-ground flying
heights: $h=\\{3,10,30\\}$ m. The wearer walked forth and back many times up
to the limits of the forested area.

##  III Data Analysis

###  III-A Radio Range and Packet Delivery Ratio

The maximum observed radio range and the recorded PDR for the three UAV
altitudes are reported in Table LABEL:tab:WoodRangePDR. A peak in the maximum
communication distance is experienced for $h=10$ m, whereas the PDR is
$\gtrsim 90\%$ in all the cases. Beyond the maximum radio range, the PDR
suddenly decays to zero, in agreement with the literature on terrestrial LoRa
links through forests. The absence of a strong correlation of these parameters
with the near-ground altitude of the UAV is coherent with the suburban
measurements we reported in [19]. This fact is a further confirmation that an
increase in the UAV altitude can both improve or degrade the reception of the
packets in near-ground links. Therefore, finding the optimal flying height is
not straightforward, unlike the case of scenarios where heightening the
drone’s altitude can avoid obstacles to establish a LoS ray path and reduce
the PL significantly [21, 22]. To establish a link even with the most distant
people without knowing the optimal $h$ in the forest wherein the SaR takes
place, the altitude of the aerial drone should vary continuously between the
minimum and maximum possible values. This procedure could be exploited, for
instance, to broadcast the GPS coordinates of the rescue point.

Figure 4: Averaged PL measurements and zoomed-in view of the proposed model.
The lines derived from the model for different flying heights are coloured in
different shades of grey, as in the legend.

(a) (b)

Figure 5: CDF of the difference between the EPL by the propagation models and
the measured instantaneous PL. (a) Difference and (b) absolute value.

(a) (b)

Figure 6: (a) Fade depth and (b) statistical distribution of small-scale
fading for some standard fits.

###  III-B Large-scale Fading

Even if near-ground altitudes were investigated, the mean PL experienced by
the signal is decreased when heightening $h$, as it is depicted in Fig. 4. For
the sake of benchmarking, the fitting parameters of the EPL model derived in
this work are reported in Table III, together with the parameters of state-of-
the-art AG NLoS models whose $\\{\gamma,PL\left(1\leavevmode\nobreak\
\textnormal{m}\right),\eta,\sigma_{SF}\\}$ values were derived from the
literature as detailed at the end of §II-C. The resulting altitude impact
factor is lower than in urban environments since no direct ray path can ever
be achieved by increasing $h$ over the trees. Variable body shadowing
contributes to increasing $\sigma_{SF}$ above the benchmark values. The
average RSE, calculated for the new model according to (7), is lower than
$4.7\%$, and the statistical validity of the model is thereof proven.

To evaluate the difference between the EPL by propagation models and the
actual $PL_{i}$ in our scenario, $\\{d_{3D},h\\}$ parameters were given as
input to the models to compute (1) assuming no shadow fading, then the
corresponding $PL_{i}(d_{3D},h)$ is subtracted from the EPL for each PL
measurement. All the benchmarking models underestimate the fading experienced
by the signal (Fig. 5(a)). The proposed model instead fits the instantaneous
PL better than the existing ones, with a reduction in the median error between
$4.10$ and $9.66$ dB (Fig. 5(b)).

###  III-C Small-scale Fading

Table IV: Fade depth and maximum fade. $\mathbf{50}$% fade |  $0.5$ dB |  $\mathbf{99}$% fade |  $20.75$ dB
---|---|---|---
Fade depth |  $20.25$ dB | Maximum fade |  $21.6$ dB

The maximum small-scale fluctuation in the signal strength over all the
measurements exceeded $30$ dB, as shown by the empirical cumulative
distribution function (CDF) of the small-scale fading values in Fig. 6(a). The
fade depth is higher than $20$ dB (Table IV) and hence stronger than NLoS AG
models for urban links [21]. The wearer’s movements cause swift variations in
$G_{Rx}$ and $\chi$, thus deepening the fading.

Regarding the statistical distribution, the envelope of the small-scale fading
in Fig. 6(b) shows that the small-scale fading is severe, namely, worse-than-
Rayleigh [39]. In particular, the Rician distribution fit overlaps the
Rayleigh fit, thus confirming the continuous absence of dominant LoS
components. The best fitting for the fading distribution is determined through
maximum log-likelihood and the envelope of the fading [21]. The Nakagami-m
distribution best fits the gathered data, with fading figure $\mu=0.64$ and
spread parameter $\Omega=32.27$ [40]. Hence, multipath scattering is the
dominant small-scale propagation phenomenon [40] due to body movements and
dense foliage.

##  IV Conclusion

A body-UAV link through a Mediterranean forest has been evaluated for the
first time involving a near-ground UAV reproducing a SaR scenario. The maximum
LoRa radio range is about $600$ m, and hard degradation of the signal is
observed beyond this limit. The large-scale attenuation is higher than that
predicted by state-of-the-art AG NLoS models that are developed for urban
environments since they underestimate the median PL by about $4$-$10$ dB. The
small-scale fading is about $20$ dB deep, severe, and follows a Nakagami-m
distribution. The body-UAV PL is very different from that reported over flat
lands (max. radio range $\sim 10$ km) [18] and mountain canyons (max. radio
range $\sim 350$ m) [41], with more relevant small-scale fading, which can
stimulate new challenges for localization and emergency communications.
Moreover, since the poplars in the Mediterranean forests were young adults,
even stronger attenuation is expected if the trees in the forested areas are
more ancient or dense [14]. Finally, even though the proposed model was
derived from a particular scenario, it can nevertheless be extended to
different environmental conditions by introducing proper corrective factors,
which can be borrowed from the growing literature on LoRa propagation.

## Acknowledgments

The authors thank professor Leila Guerriero for her helpful comments on the
data analysis.

## References

  * [1] R. Cheriyan, J. Abraham, E. Sree Sankar, S. Narayanan, and R. Mathai, “Nemo: Energy efficient location tracker for dementia patients using LoRaWAN and adaptive GPS duty cycling strategies,” _EAI/Springer Innov. Commun. Comput._ , pp. 511–521, 2022.
  * [2] T. Ameloot, P. Van Torre, and H. Rogier, “LoRa base-station-to-body communication with simo front-to-back diversity,” _IEEE Trans. Antennas Propag._ , vol. 69, no. 1, pp. 397–405, 2021.
  * [3] G. M. Bianco, R. Giuliano, G. Marrocco, F. Mazzenga, and A. Mejia-Aguilar, “LoRa System for Search and Rescue: Path Loss Models and Procedures in Mountain Scenarios,” _IEEE Internet Things J_ , vol. 8, no. 3, pp. 1985–1999, Feb. 2021.
  * [4] C. Bouras, A. Gkamas, and S. A. K. Salgado, “Energy efficient mechanism for LoRa networks,” _Internet Things_ , vol. 13, pp. 1–17, Mar. 2021.
  * [5] G. M. Bianco, A. Mejia-Aguilar, and G. Marrocco, “Performance evaluation of LoRa LPWAN technology for mountain search and rescue,” in _5th Int. Conf. Smart Sustain. Technol._ , 2020, pp. 1–4.
  * [6] M. P. Manuel, M. Faied, and M. Krishnan, “A novel LoRa LPWAN-based communication architecture for search & rescue missions,” _IEEE Access_ , vol. 10, pp. 57 596–57 607, 2022.
  * [7] A. Calabrò and R. Giuliano, “Integrated Wi-Fi and LoRa network on UAVs for localizing people during SAR operations,” in _Int. Conf. Elect. Electron. Technol. Automot._ , Nov. 2021, pp. 1–6.
  * [8] J. S. Seybold, _Introduction to RF Propagation_. Hoboken, NJ, USA: John Wiley & Sons, 2005.
  * [9] K. A. Ahmad, M. S. Salleh, J. D. Segaran, and F. R. Hashim, “Impact of foliage on LoRa 433 MHz propagation in tropical environment,” in _AIP Conf. Proc._ , Feb. 2018, pp. 1–6.
  * [10] A. Sharma, D. Kapoor, A. Nayyar, B. Qureshi, K. Singh, and K. Thakur, “Exploration of IoT nodes communication using LoRaWAN in forest environment,” _Comput., Mater. & Continua_, vol. 71, no. 2, pp. 6240–6256, 2022.
  * [11] G. P. N. Hakim _et al._ , “Near ground pathloss propagation model using adaptive neuro fuzzy inference system for wireless sensor network communication in forest, jungle and open dirt road environments,” _Sensors_ , vol. 22, no. 9, 2022.
  * [12] A. E. Ferreira _et al._ , “A study of the LoRa signal propagation in forest, urban, and suburban environments,” _Ann. Telecommun._ , vol. 75, pp. 333–351, 2020.
  * [13] G. Callebaut and L. Van der Perre, “Characterization of LoRa point-to-point path loss: Measurement campaigns and modeling considering censored data,” _IEEE Internet Things J._ , vol. 7, no. 3, pp. 1910–1918, Mar. 2020.
  * [14] L. Guerriero _et al._ , “Ground-based remote sensing of forests exploiting GNSS signals,” _IEEE Trans. Geoscience Remote Sens._ , vol. 58, no. 10, pp. 6844–6860, 2020.
  * [15] L. Xing _et al._ , “Multi-UAV cooperative system for search and rescue based on YOLOv5,” _Int. J. Disaster Risk Reduction_ , vol. 76, 2022.
  * [16] J. Grau, K. Liang _et al._ , “Improved accuracy of riparian zone mapping using near ground unmanned aerial vehicle and photogrammetry method,” _Remote Sens._ , vol. 13, no. 10, 2021.
  * [17] A. Kachroo _et al._ , “Unmanned aerial vehicle-to-wearables (UAV2W) indoor radio propagation channel measurements and modeling,” _IEEE Access_ , vol. 7, pp. 73 741–73 750, May 2019.
  * [18] G. M. Bianco, A. Mejia-Aguilar, and G. Marrocco, “Numerical and experimental characterization of LoRa-based helmet-to-unmanned aerial vehicle links on flat lands: A numerical-statistical approach to link modeling.” _IEEE Antennas Propag. Mag._ , pp. 2–15, 2022.
  * [19] G. M. Bianco and G. Marrocco, “Indirect propagation of body-UAV LoRa links over wood and suburb,” in _3rd URSI Atlantic Asia Pacific Radio Sci. Meeting_ , Gran Canaria, Spain, May 2022, pp. 1–4.
  * [20] B. Wang, D. Wang, Z. Ali, B. Ting Ting, and H. Wang, “An overview of various kinds of wind effects on unmanned aerial vehicle,” _Meas. Control_ , vol. 52, no. 7-8, pp. 731–739, 2019.
  * [21] Z. Cui, C. Briso-Rodríguez, K. Guan, C. Calvo-Ramírez, B. Ai, and Z. Zhong, “Measurement-based modeling and analysis of UAV air-ground channels at 1 and 4 GHz,” _IEEE Antennas Wireless Propag. Lett._ , vol. 18, no. 9, pp. 1804–1808, Sep. 2019.
  * [22] 3GPP, “Technical Specification Group Radio Access Network; Study on channel model for frequencies from 0.5 to 100 GHz,” 3GPP, Sophia-Antipolis, France, Rep. no. 38.901 V16.1.10, Dec. 2019. Accessed: March 3, 2022. [Online]. Available: https://portal.3gpp.org/desktopmodules/Specifications/SpecificationDetails.aspx?specificationId=3173.
  * [23] A. Al-Hourani and K. Gomez, “Modeling cellular-to-UAV path-loss for suburban environments,” _IEEE Wireless Commun. Lett._ , vol. 7, no. 1, pp. 82–85, Feb. 2018.
  * [24] R. Anzum _et al._ , “A multiwall path-loss prediction model using 433 MHz LoRa-WAN frequency to characterize foliage’s influence in a Malaysian palm oil plantation environment,” _Sensors_ , pp. 1–17, 2022.
  * [25] B. Myagmardulam _et al._ , “Path loss prediction model development in a mountainous forest environment,” _IEEE Open J. Comm. Soc._ , pp. 1–8, 2021\.
  * [26] Y. Wu, G. Guo, T. Guiyun, and W. Liu, “A model with leaf area index and trunk diameter for LoRaWAN radio propagation in eastern China mixed forest,” _J. Sensors_ , pp. 1–16, Jun. 2020.
  * [27] E. Sudirjo, P. De Jager, C. Buisman, and D. Strik, “Performance and long distance data acquisition via LoRa technology of a tubular plant microbial fuel cell located in a paddy field in West Kalimantan, Indonesia,” _Sensors_ , pp. 1–18, 2019.
  * [28] T. Ameloot, P. Van Torre, and H. Rogier, “Variable link performance due to weather effects in a long-range, low-power LoRa sensor network,” _Sensors_ , pp. 1–22, 2021.
  * [29] O. Elijah _et al._ , “Effect of weather condition on LoRa IoT communication technology in a tropical region: Malaysia,” _IEEE Access_ , pp. 1–9, 2021.
  * [30] L. Parri, S. Parrino, G. Peruzzi, and A. Pozzebon, “Offshore LoRaWAN networking: Transmission performances analysis under different environmental conditions,” _IEEE Trans. Instr. Meas._ , pp. 1–10, 2021.
  * [31] J. Gaelens, P. Van Torre, J. Verhaevert, and H. Rogier, “LoRa mobile-to-base-station channel characterization in the antarctic,” _Sensors_ , pp. 1–18, 2017.
  * [32] T. Ameloot, M. Moeneclaey, P. Van Torre, and H. Rogier, “Characterizing the impact of Doppler effects on body-centric LoRa links with SDR,” _Sensors_ , pp. 1–15, 2021.
  * [33] J. Petäjäjärvi, K. Mikhaylov, M. Pettissalo, J. Janhunen, and J. Iinatti, “Performance of a low-power wide-area network based on LoRa technology: Doppler robustness, scalability, and coverage,” _Int. J. Distributed Sensor Netw._ , pp. 1–16, 2017.
  * [34] W. Scanlon, B. Burns, and N. Evans, “Radiowave propagation from a tissue-implanted source at 418 MHz and 916.5 MHz,” _IEEE Tran. Biomed. Eng._ , vol. 47, no. 4, pp. 527–534, 2000.
  * [35] S. Ward and R. Lieber, “Density and hydration of fresh and fixed human skeletal muscle,” _J. Biomechanics_ , vol. 38, no. 11, pp. 2317–2320, Nov. 2005.
  * [36] A. Grami, _Introduction to Digital Communication_ , 1st ed. New York, NY, USA: Academic Press Inc., 2015, ch. 12, sec. 3, pp.504-511.
  * [37] R. He _et al._ , “Short-term fading behavior in high-speed railway cutting scenario: Measurements, analysis, and statistical models,” _IEEE Trans. Antennas Propag._ , vol. 61, no. 4, pp. 2209–2222, 2013.
  * [38] “Pycom_002_Specsheets_LoPy4_v2,” https://docs.pycom.io/datasheets/development/lopy4/, 2017, Pycom Company, Guildford, U.K. Accessed: Jan. 6, 2023.
  * [39] D. W. Matolak and J. Frolik, “Worse-than-Rayleigh fading: Experimental results and theoretical models,” _IEEE Commun. Mag._ , vol. 49, no. 4, pp. 140–146, Apr. 2011.
  * [40] H. Popovic, D. Stefanovic, A. Mitic, I. Stefanovic, and D. Stefanovic, “Some statistical characteristics of Nakagami-m distribution,” in _8th Int. Conf. Telecommun. Modern Satell., Cable Broadcast. Services_ , 2007, pp. 509–512.
  * [41] G. M. Bianco, A. Mejia-Aguilar, and G. Marrocco, “Measurements and modeling of Radiohelmet-UAV LoRa links in a mountain canyon,” in _16th Eur. Conf. Antennas Propag._ , 2022, pp. 1–4.


# Community-based Outlier Detection
for Edge-attributed Graphs

Supriya Pandhre  Indian Institute of Technology, Hyderabad
Hyderabad, India
<EMAIL_ADDRESS>Manish Gupta  Microsoft
Hyderabad, India
<EMAIL_ADDRESS>Vineeth N Balasubramanian  Indian Institute of
Technology, Hyderabad
Hyderabad, India
<EMAIL_ADDRESS>
###### Abstract

The study of networks has emerged in diverse disciplines as a means of
analyzing complex relationship data. Beyond graph analysis tasks like graph
query processing, link analysis, influence propagation, there has recently
been some work in the area of outlier detection for information network data.
Although various kinds of outliers have been studied for graph data, there is
not much work on anomaly detection from edge-attributed graphs. In this paper,
we introduce a method that detects novel outlier graph nodes by taking into
account the node data and edge data simultaneously to detect anomalies. We
model the problem as a community detection task, where outliers form a
separate community. We propose a method that uses a probabilistic graph model
(Hidden Markov Random Field) for joint modeling of nodes and edges in the
network to compute _Holistic Community Outliers (HCOutliers)_. Thus, our model
presents a natural setting for heterogeneous graphs that have multiple
edges/relationships between two nodes. EM (Expectation Maximization) is used
to learn model parameters, and infer hidden community labels. Experimental
results on synthetic datasets and the DBLP dataset show the effectiveness of
our approach for finding novel outliers from networks.

##  I Introduction

Outlier (or anomaly) detection is a very broad field which has been studied in
the context of a large number of research areas like statistics, data mining,
sensor networks, environmental science, distributed systems, spatio-temporal
mining, etc. Many algorithms have been proposed for outlier detection in high-
dimensional data, uncertain data, stream data and time series data. By its
inherent nature, network data provides very different challenges that need to
be addressed in a special way. Network data is gigantic, contains nodes of
different types, rich nodes with associated attribute data, noisy attribute
data, noisy link data, and is dynamically evolving in multiple ways. Outlier
detection on networks for various applications can be useful for: (1)
identification of interesting entities or sub-graphs, (2) data de-noising
(both with respect to the network nodes and edges), (3) understanding the
anomalous temporal behavior of entities, and (4) identification of new trends
or suspicious activities in both static and dynamic scenarios. Some examples
of network outliers include users who spread rumors on Twitter, unusual but
successful associations of persons with various organizations in an
organizational network, sensor with anomalous readings in a sensor network,
anomalous traffic between two components in a distributed network, snapshot
with broken correlation between network properties across time, etc.

Given a static graph, one can find node, edge or subgraph outliers. For
dynamic graphs, the outliers could be time stamps where the properties of the
snapshot are significantly different from the properties of other snapshots.
In the dynamic scenario, one can also identify a node (or an edge, or a
subgraph) which shows anomalous behavior across time as an outlier. Popular
outlier detection methods for static graphs include the Minimum Description
Length (MDL) method [10], frequent subgraph mining, egonet analysis [5], and
community analysis [12, 14]. Popular methods for outlier detection for dynamic
graphs include graph similarity based methods [20], temporal spectral analysis
[19], temporal structural connectivity analysis [3], and temporal community
analysis [15, 16].

While most work in the past on network outlier detection has focused on graphs
with node data and links, there is very little work in the area of edge-
attributed graphs. In some cases, node data and linkage could be normal even
when edge data is abnormal, in the context of nodes on which the edge is
incident. With the rich variety of interactions in various complex graphs
across a variety of domains, it is critical to incorporate such edge
attributes in finding novel outliers. If we could assign a latent community to
every node and every edge, a HCOutlier node is one which is linked to many
nodes of another community, or has incident edges belonging to another
community.

The following real-world examples demonstrate the importance of HCOutliers.

Organizational Graph Example: A graph of people working in a company is called
an organization graph. Edges represent frequent communication. Role of a
person can be considered as the community label. Usually a chemist in a
company would communicate frequently with other chemists. But a suspicious
HCOutlier node would not just communicate frequently with members of other
roles, but also the community of the communications would be different from
the one expected for its role. Such a person could be an activist planning a
malicious activity with other folks in the company, or a star performer
working on a secret collaborative project.

Co-authorship Graph Example: A co-authorship graph contains authors as nodes.
Two authors are connected if they have published a paper together. On such
graphs, research areas can be considered as latent communities. Most authors
collaborate with other authors, and publish papers _in the same research
area_. An HCOutlier would be an author who: (1) collaborates frequently with
authors from other research areas, and (2) collaborates with other authors of
same or different community on papers which belong to other research areas.
Such authors perform inter-disciplinary research and are vital in cross-
pollination of concepts across research areas.

Co-actorship Graph Example: A co-actorship graph contains actors as nodes. Two
actors are connected if they have worked in a movie together. On such graphs,
movie genres can be considered as latent communities. Most actors collaborate
with other actors, and work in movies _in the same genre_. An HCOutlier would
be an actor who: (1) collaborates frequently with actors from other genres,
and (2) collaborates with other actors of same or different genre in movies
which belong to other genres. HCOutlier actors are ones who have built a
reputation for being multi-faceted actors with an eclectic range of movies.

Limitations of Past Approaches: In the past, various approaches have been
proposed by looking only at node data and ignoring network structure. Clearly,
HCOutliers cannot be detected using such a global approach because HCOutlier
nodes belong to popular communities. There has been work on finding community
outliers for both homogeneous [12] and heterogeneous graphs [14] by
considering node data and link structure but ignoring edge data. Clearly, such
an approach can identify some HCOutliers who are linked to nodes with a
different community label. But they cannot identify a HCOutlier who could be
connected to nodes of the same community label but has incident edges with a
different community label.

Brief Overview of the Proposed Approach: We propose a probabilistic model for
detection of Holistic Community Outliers. We model the problem as a community
detection task where the outliers are modeled as a separate community. A
Hidden Markov Random Field (HMRF) is used to perform joint community analysis
for both nodes and edges considering node data, edge data and the linkage
structure. Thus, the HMRF contains both nodes and edges from the graph as
vertices, referred to as a node-vertex and an edge-vertex respectively.
Community labels for outliers are sampled from a uniform distribution while
normal vertices could be sampled from Gaussian or a multinomial distribution.
EM is used for the inference, and to compute the hidden community label $Z$
for every vertex.

We make the following contributions in this paper:

  * •

We look at the community outlier detection problem from a holistic perspective
by incorporating node data, edge data, and the linkage structure. Based on
such a view, we propose the problem of detecting novel HCOutliers.

  * •

We model the problem as a community analysis task over a HMRF and provide
inference using an EM algorithm.

  * •

Using several experiments on synthetic datasets and a DBLP dataset, we show
the effectiveness of the proposed approach in identifying HCOutliers.

Section II gives a brief summary of related work. We describe our HMRF model
in detail in Section III and present the inference in Section IV. We discuss
hyper-parameter settings and initialization details in Section V. We provide
details of experiments on synthetic datasets and the DBLP dataset in Section
VI and conclude in Section VII.

##  II Related Work

Outlier detection has a long history and [2, 11, 18] provide extensive
overviews of popular methods; [6, 13] focus on network outlier detection
methods. Our work is most related to two main sub-areas of network outlier
detection: community-based outlier detection and analysis of edge-attributed
graphs, each of which is discussed below.

###  II-A Community-based Graph Outlier Detection

Community-based outlier detection methods perform community analysis on
graphs. Nodes that do not belong to any community are labeled as outliers.
Community-based outlier detection has been studied both for static networks
and dynamic networks. The notion of community outliers has been studied for
static bipartite graphs using random walks in [23], for static homogeneous
networks using probabilistic models in [12], and for static heterogeneous
graphs using non-negative matrix factorization in [14]. [22] summarizes
different anomaly detection methods in dynamic graphs such as decomposition
based methods [4], [24], distance based methods [1]. Community based outlier
detection method, for dynamic graphs, is proposed for a two-snapshots setting
in [16] and for a series of snapshots in [15].

###  II-B Analysis of Edge-attributed Graphs

Edge content indicates the type of relationship between the two nodes. However
very little work exists on analysis of edge-attributed graphs. Qi et al. [21]
proposed a edge-induced matrix factorization based method for finding
communities in social graph using edge content. [8] proposed a method that
considers edge data of User-Likes-Pages Facebook graph for temporal analysis
to find the page-like pattern. [9] proposed a method for mining coherent sub-
graphs in multi-layer edges by exploiting edge content. [17] proposed a method
for finding top-$K$ interesting subgraphs matching a query template where
interestingness is defined using edge weights. We propose a community-based
outlier detection method for edge-attributed graphs which jointly exploits
edge content along with node data and the linkage structure.

##  III Anomaly Detection using Node Data, Edge Data, and Linkage

In this section, we develop the HMRF model which we use to perform joint
community analysis for both nodes and edges considering node data, edge data
and the linkage structure. Consider an undirected graph $G=\\{V,E\\}$, where
$V$ is the set of vertices and $E$ is the set of edges.

Node and Edge Data: Let $S$ be the set of observed data.

  * •

Let $S_{i}$ represent the observed data of node $v_{i}\in V$ which has $p$
attributes, $S_{i_{1}}$, $S_{i_{2}}$, $\cdots$, $S_{i_{p}}$.

  * •

Let $S_{ij}$ represent the observed data of edge $e_{ij}\in E$, i.e., edge
data between nodes $v_{i}$ and $v_{j}$, and there are $q$ number of
attributes, $S_{ij_{1}}$, $S_{ij_{2}}$, $\cdots$, $S_{ij_{q}}$.

HMRF Model: The HMRF contains a vertex representing each node and each edge
from $G$. We refer to the HMRF vertices representing nodes and edges as node-
vertices and edge-vertices respectively. We use the index $i$ to refer to
node-vertices in the HMRF, and the index $ij$ to refer to edge-vertices in the
HMRF. We use the index $b$ to refer to all the vertices in the HMRF. Thus
$b\in
B=\\{1,2,\cdots,i,\cdots,|V|,(1,2),(1,3),\cdots,(1,|V|),(2,3),\cdots,(|V|-1,|V|)\\}$.
Note that $ij\in B$ if $i<j$. Thus, $|B|=|V|+|E|$.

  * •

Let $X=\\{X_{b}\\}$ be a set of random variables. $X_{i}$ generates node data
$S_{i}$, and $X_{ij}$ generates edge data $S_{ij}$.

  * •

Let $Z=\\{Z_{b}\\}$ be the set of hidden random variables. $Z_{i}$ indicates
the community assignment of $v_{i}$. Suppose there are $K$ communities, then
$Z_{i}\in\\{0,1,2,\cdots,K\\}$. If $Z_{i}=0$, then $v_{i}$ is an outlier. If
$Z_{i}=k$, then $v_{i}$ belongs to the community $k$. Similarly, $Z_{ij}$
denotes the community assignment for edge $e_{ij}$.

  * •

Let $W$ denote the weights in the HMRF. $W_{v_{i},v_{j}}$ is set to the weight
of the edge $e_{ij}\in E$ and represent edge strength.
$W_{v_{i},v_{j},e_{ij}}$ are weights for a triangle clique consisting of
$v_{i}$, $v_{j}$ and $e_{ij}$. Thus, $|W|=4|E|$ (3 faces of the triangle
formed by two node-vertices and an edge-vertex, and the whole triangle
itself).

$W_{v_{i},e_{ij}}$ can be set in multiple ways. We set it to the inverse of
number of neighbors of $v_{i}$ in $G$. Thus, for a co-authorship graph, this
weight can be set to the inverse of the number of co-authors of author $v_{i}$
in the graph. For a Twitter users graph, this weight can be set to the inverse
of the number of other users that the user $v_{i}$ is connected to. In a
directed network sense, the weight can also be set to the ratio of the number
of tweets from user $v_{i}$ to user $v_{j}$ to number of total tweets from
user $v_{i}$.

$W_{v_{i},v_{j},e_{ij}}$ should reflect some property of the triangle clique
which cannot be captured using individual edges. For a co-authorship network,
this could be set to ratio of number of papers where authors $v_{i}$ and
$v_{j}$ are co-authors to the total number of papers on which either $v_{i}$
or $v_{j}$ are authors. Similarly, for a Twitter user network, this weight can
be set to the ratio of tweets exchanged between users $v_{i}$ and $v_{j}$ to
the total tweets posted by either $v_{i}$ or $v_{j}$.

$Z_{b}$’s are influenced by their neighbors, i.e., if two nodes are linked, it
is likely that both belong to the same community. This does not hold for the
outliers. Let $N_{i}$ denote the set of neighbors of node $v_{i}$. If
$Z_{i}=0$, then $v_{i}$ is an outlier, and so the neighborhood set is empty.
Also, each node-vertex is connected to the edge-vertex corresponding to the
edges which are incident on the node in $G$.

$\displaystyle\small N_{i}=\begin{cases}\\{v_{j}|W_{v_{i}v_{j}}>0,i\neq
j,Z_{j}\neq 0\\}\cup\\\ \\{e_{xy}|W_{v_{i}e_{xy}}>0,x=i\ or\ y=i,Z_{xy}\neq
0\\}&\quad Z_{i}\neq 0\\\ \phi&\quad Z_{i}=0\\\ \end{cases}$ (1)

Similarly, we also define neighbors for edge-vertices, $N_{ij}$, as follows.
Note that for an edge-vertex, the neighbors are only the node-vertices on
which the edge-vertex is incident except for the case when these node-vertices
are outliers.

$\displaystyle\small N_{ij}=\begin{cases}\\{v_{i}|z_{i}\neq
0\\}\cup\\{v_{j}|z_{j}\neq 0\\}&\quad Z_{ij}\neq 0\\\ \phi&\quad Z_{ij}=0\\\
\end{cases}$ (2)

Data Likelihood: Let $\Theta$ = {$\theta_{1},\theta_{2},..,\theta_{K}$} be the
set of parameters describing the normal communities. Thus, likelihood for
node/edge data can be written as follows.

$\displaystyle P(X_{b}=S_{b}|Z_{b}=k)=P(X_{b}=S_{b}|\theta_{k})$ (3)

We assume the outliers follow uniform distribution as we do not know
beforehand which elements(node-vertex or edge-vertex) are anomalous or what
they look like.

$\displaystyle P(X_{b}=S_{b}|Z_{b}=k)=\rho_{0}$ (4)

where $\rho_{0}$ is a constant.

Figures 2 and 2 illustrate a sample graph and its corresponding HMRF model.
The graph has two communities, blue and red. The node $v_{5}$ has connection
with the member of blue community as if it is part of blue community but its
node attributes are similar to red community. Hence, in the HMRF model, it is
not connected to any other node, indicating $v_{5}$ as an outlier. The edge
between $v_{4}$ and $v_{6}$ indicate the cross-community collaboration and
thus detected as interesting nodes.

(a)

Figure 1: Original Graph G=(V,E)

(a)

Figure 2: HMRF model of G indicating anomalous node $v_{4}$, $v_{5}$ and
$v_{6}$

###  III-A Cliques and Potentials in HMRF

As the community label assignment follows an HMRF, we can define
$P(Z)=\frac{1}{H_{1}}\exp(-U(Z))$ where $U(Z)$ is the potential function,
defined as sum over all possible cliques.

We consider two kinds of clique potentials: pairwise ($v_{i}$ to $v_{j}$,
$v_{i}$ to $e_{ij}$) and triangular (between $v_{i}$, $v_{j}$ and $e_{ij}$).
Then, the potential function can be written as follows.

$\displaystyle\small\begin{split}U(Z)=-\lambda_{1}\sum_{\begin{subarray}{c}W_{v_{i}v_{j}}>0,\\\
Z_{i}\neq 0,\\\ Z_{j}\neq 0\end{subarray}}W_{v_{i}v_{j}}\delta(Z_{i}-Z_{j})\\\
-\lambda_{2}\sum_{\begin{subarray}{c}W_{v_{i}e_{ij}}>0,\\\ Z_{i}\neq 0,\\\
Z_{ij}\neq 0\end{subarray}}W_{v_{i}e_{ij}}\delta(Z_{i}-Z_{ij})\\\
-\lambda_{2}\sum_{\begin{subarray}{c}W_{v_{j}e_{ij}}>0,\\\ Z_{j}\neq 0,\\\
Z_{ij}\neq 0\end{subarray}}W_{v_{j}e_{ij}}\delta(Z_{j}-Z_{ij})\\\
-\lambda_{3}\sum_{\begin{subarray}{c}W_{v_{i}v_{j}e_{ij}}>0,\\\ Z_{i}\neq
0,\\\ Z_{j}\neq 0,\\\ Z_{ij}\neq
0\end{subarray}}W_{v_{i}v_{j}e_{ij}}\psi(Z_{i},Z_{j},Z_{ij})\end{split}$ (5)

where $\lambda_{1},\lambda_{2},\lambda_{3}$ are constants, $W_{v_{i}v_{j}}>0$,
$W_{v_{i}e_{ij}}>0$, $W_{v_{j}e_{ij}}>0$, $W_{v_{i}v_{j}e_{ij}}>0$, imply that
there are links connecting $v_{i}$-$v_{j}$, $v_{i}$-$e_{ij}$, $v_{j}$-$e_{ij}$
and $Z_{i}$, $Z_{j}$, $Z_{ij}$ are non-zero. The $\delta$ function is defined
as $\delta(x)=1$ if $x=0$ and $\delta(x)=0$ otherwise. Also,
$\psi(Z_{i},Z_{j},Z_{ij})=1$ if
$\delta(Z_{i}-Z_{j})+\delta(Z_{i}-Z_{ij})+\delta(Z_{j}-Z_{ij})\leq 1$, and 0
otherwise. Note that we define $\psi$ this way to capture the intuition that
the clique potential should fire if at least two of the members in the clique
share the same community label. Overall, the potential function suggests that,
if members of the clique are normal objects, they are more likely to be in the
same community when there exists a link connecting them in G, and the
probability becomes higher if their link (weight) is stronger.

###  III-B Probability of Generating the Data

Given the community label of a vertex ($Z_{i}$ or $Z_{ij}$) in the HMRF, the
corresponding data ($X_{i}$ or $X_{ij}$) can be modeled as data generated from
a distribution with parameters specific to the community. Community labels can
be obtained using either Gaussian mixture model on the data if it is
continuous, or as multinomial if the data is textual.

Continuous Data: If the data is numeric and 1-dimensional, we need to learn
the mean ($\mu_{k}$), and standard deviation ($\sigma_{k}$) for each community
$k$ represented using a Gaussian. Given the parameters and the community
label, the log likelihood can be written as follows.

$\displaystyle\ln
P(X_{i}=S_{i}|Z_{i}=k)=-\frac{(S_{i}-\mu_{k})^{2}}{2\sigma_{k}^{2}}-\ln\sigma_{k}-\ln\sqrt{2\pi}$
(6)

In case of multi-dimensional data with $p$ dimensions, the log likelihood can
be written as follows.

$\displaystyle\ln
P(X_{i}=S_{i}|Z_{i}=k)=-\frac{(S_{i}-\mu_{k})^{T}\Sigma_{k}^{-1}(S_{i}-\mu_{k})}{2}$
$\displaystyle-\frac{\ln\Sigma_{k}}{2}-\ln\sqrt{(2\pi)^{p}}$ (7)

Discrete Data: If the node (or edge) data can be represented as a document, we
assume that the attributes (or words) are independent of each other, given the
community label.

$\displaystyle
P(X_{i}=S_{i}|\theta_{k})=\prod_{c=1}^{p}P(X_{i_{c}}=S_{i_{c}}|\theta_{k})$
(8) $\displaystyle
P(X_{ij}=S_{ij}|\theta_{k})=\prod_{c=1}^{q}P(X_{ij_{c}}=S_{ij_{c}}|\theta_{k})$
(9)

For text data, given a vocabulary of $T$ words, let $d_{bl}$ be the number of
times the word $l$ appears in data related to vertex $b$. Then the parameters
$\theta_{k}=\\{\beta_{k1},\cdots,\beta_{kT}\\}$ denote the probability of a
particular word belonging to community $k$. Given the parameters, the data
likelihood of an object belonging to the $k^{th}$ community can be computed as
follows.

$\displaystyle\ln
P(X_{i_{c}}=S_{i_{c}}|Z_{i}=k)=\sum_{l=1}^{T}d_{il}\ln\beta_{kl}$ (10)

where $\beta_{kl}$ is the probability of the word with index $l$ belonging to
community $k$.

##  IV Inferring $Z$ and Estimating $\Theta$

The model parameters $\Theta$ and the set of hidden labels $Z$ are unknown as
described in Section III. In this section, we describe methods to infer the
hidden labels and also estimate the model parameters.

###  IV-A Inferring Hidden Labels

Assuming the model parameters $\Theta$ are known, we find the configuration
$Z$ that will maximize the posterior distribution as follows.

$\displaystyle\hat{Z}=\arg\max_{\begin{subarray}{c}Z\end{subarray}}P(X=S|Z)P(Z)$
(11)

To find such a configuration, we use the Iterated Conditional Modes (ICM)
algorithm [7]. It is a greedy algorithm which guarantees convergence to a
local optima by sequentially updating one $Z_{b}$ at a time assuming other
$Z$’s (i.e., $Z_{B-{b}}$) as constant. At each step, the algorithm updates
$Z_{b}$ given $X_{b}=S_{b}$ and the other labels such that the posterior
$P(Z_{b}|X_{b}=S_{b},Z_{B-{b}})$ is maximized. If $Z_{b}\neq 0$, applying
Bayes rule,

$\displaystyle P(Z_{b}|X_{b}=S_{b},Z_{B-{b}})\propto P(X_{b}=S_{b}|Z)P(Z)$
(12)

In Eq. 12, $P(Z)$ can be computed using Eq. 5. But rather than considering
potential for the entire graph, Eq. 12 needs potentials defined over only
those cliques in which $Z_{b}$ is involved. Thus, we can write the following
equation for node-vertices:

$\displaystyle\small\begin{split}P(Z_{i}|X_{i}=S_{i},Z_{B-\\{i\\}})&\propto
P(X_{i}=S_{i}|Z)\times\\\ &\exp(\lambda_{1}\sum_{\begin{subarray}{c}v_{j}\in
N_{i}\end{subarray}}W_{v_{i}v_{j}}\delta(Z_{i}-Z_{j})\\\
&+\lambda_{2}\sum_{\begin{subarray}{c}e_{xy}\in
N_{i}\end{subarray}}W_{v_{i}e_{xy}}\delta(Z_{i}-Z_{xy})\\\
&+\lambda_{3}\sum_{\begin{subarray}{c}v_{j}\in N_{i},\\\ e_{xy}\in
N_{i}\end{subarray}}W_{v_{i}v_{j}e_{xy}}\psi(Z_{i},Z_{j},Z_{xy}))\end{split}$
(13)

Also, the corresponding equation for the edge-vertices can be written as
follows.

$\displaystyle\small\begin{split}P(Z_{ij}|X_{ij}=S_{ij},Z_{B-\\{(i,j)\\}})&\propto
P(X_{ij}=S_{ij}|Z)\times\\\
&\exp(\lambda_{2}\sum_{\begin{subarray}{c}v_{i^{\prime}}\in
N_{ij}\end{subarray}}W_{v_{i^{\prime}}e_{ij}}\delta(Z_{i^{\prime}}-Z_{ij})\\\
&+\lambda_{3}W_{v_{i}v_{j}e_{ij}}\psi(Z_{i},Z_{j},Z_{ij}))\end{split}$ (14)

Taking log of the posterior probability, we can transform the maximizing
posterior problem to minimizing the conditional posterior energy function
defined as shown in Eqs. 15 and 16 for node-vertices and edge-vertices
respectively.

$\displaystyle\small\begin{split}U_{i}(k)&=-\ln
P(X_{i}=S_{i}|Z_{i}=k)-\lambda_{1}\sum_{\begin{subarray}{c}v_{j}\in
N_{i}\end{subarray}}W_{v_{i}v_{j}}\delta(k-Z_{j})\\\
&-\lambda_{2}\sum_{\begin{subarray}{c}e_{xy}\in
N_{i}\end{subarray}}W_{v_{i}e_{xy}}\delta(k-Z_{xy})\\\
&-\lambda_{3}\sum_{\begin{subarray}{c}v_{j}\in N_{i},\\\ e_{xy}\in
N_{i}\end{subarray}}W_{v_{i}v_{j}e_{xy}}\psi(k,Z_{j},Z_{xy})\\\ \end{split}$
(15) $\displaystyle\small\begin{split}U_{ij}(k)&=-\ln
P(X_{ij}=S_{ij}|Z_{ij}=k)\\\
&-\lambda_{2}\sum_{\begin{subarray}{c}v_{i^{\prime}}\in
N_{ij}\end{subarray}}W_{v_{i^{\prime}}e_{ij}}\delta(Z_{i^{\prime}}-k)-\lambda_{3}W_{v_{i}v_{j}e_{ij}}\psi(Z_{i},Z_{j},k)\end{split}$
(16)

If $Z_{b}=0$, the vertex has no neighbors, and thus

$\displaystyle\begin{split}P(Z_{b}|X_{b}=S_{b},Z_{B-\\{b\\}})\ \propto\
P(X_{b}=S_{b}|Z_{b}=0)P(Z_{b}=0)\end{split}$ (17)

Hence,

$\displaystyle U_{b}(0)=-\ln(\rho_{0}\pi_{0})=a_{0}$ (18)

Finally, the label $Z_{b}$ for vertex $b$ in HMRF is set to
$k\in\\{0,1,\cdots,K\\}$ such that $U_{b}(k)$ is minimized. The predefined
hyper-parameters, $\lambda_{1},\lambda_{2},\lambda_{3}$, represent the
importance of the respective components of the graph structure. $a_{0}$ is the
outlierness threshold. Algorithm 1 first randomly initializes the labels for
all vertices. At each step, labels are updated sequentially by minimizing
$U_{b}(k)$.

Algorithm 1 Inferring Hidden Labels

Input: Node/Edge data $S$, weights $W$, set of model parameters $\theta$,
number of clusters $K$, hyper-parameters
($\lambda_{1},\lambda_{2},\lambda_{3}$), threshold $a_{0}$, initial assignment
of labels $Z^{(1)}$
Output: Updated assignment of labels $Z$

1:Randomly set $Z^{(0)}$

2:$t\leftarrow 1$

3:while $Z^{(t)}$ is not close enough to $Z^{(t-1)}$ do

4: $t\leftarrow t+1$

5: for $b=1;b\leq|B|;i++$ do

6: Update $Z_{b}^{(t)}=k$ which minimizes $U_{b}(k)$ using Eqs. 15, 16 and 18

7:return $Z^{(t)}$

###  IV-B Estimating Parameters

In this subsection, we discuss a method for estimating unknown $\theta$ from
the data. $\theta$ describes the model that generates node data and edge data.
Hence we seek to maximize the data likelihood $P(X=S|\theta)$ to obtain
$\hat{\theta}$. However, since both the hidden labels and the parameters are
unknown and they are inter-dependent, we use expectation-maximization (EM)
algorithm (as shown in Algorithm 2) to solve the problem. We direct the reader
to [12] for details.

The algorithm starts with an initial estimate of hidden labels $Z^{(1)}$.
Given the current configuration of hidden labels, we can estimate model
parameters as follows. For univariate numeric data, $\mu_{k}^{(t+1)}$ and
$\sigma_{k}^{(t+1)}$ are estimated as follows:

$\displaystyle\mu_{k}^{(t+1)}=\frac{\sum_{b=1}^{|B|}P(Z_{b}=k|X_{b}=S_{b},\Theta^{(t)})S_{b}}{\sum_{b=1}^{|B|}P(Z_{b}=k|X_{b}=S_{b},\Theta^{(t)})}$
(19)
$\displaystyle(\sigma_{k}^{(t+1)})^{2}=\frac{\sum_{b=1}^{|B|}P(Z_{b}=k|X_{b}=S_{b},\Theta^{(t)})(S_{b}-\mu_{k})^{2}}{\sum_{b=1}^{|B|}P(Z_{b}=k|X_{b}=S_{b},\Theta^{(t)})}$
(20)

For text data, given a vocabulary of $T$ words, let $d_{bl}$ be the number of
times the word $l$ appears in data related to vertex $b$. Then, given the
current configuration of hidden labels, we can estimate parameters of the
multinomial distribution $\beta_{kl}$ for $k\in\\{1,\cdots,K\\}$ and
$l\in\\{1,\cdots,T\\}$ as follows:

$\displaystyle\beta_{kl}^{(t+1)}=\frac{\sum_{b=1}^{|B|}P(Z_{b}=k|X_{b}=S_{b},\Theta^{(t)})d_{bl}}{\sum_{l=1}^{T}\sum_{b=1}^{|B|}P(Z_{b}=k|X_{b}=S_{b},\Theta^{(t)})d_{bl}}$
(21)

Given the updated parameters, the new configuration of hidden labels can be
estimated using Algorithm 1 where $P(Z_{b}=k^{*}|X_{b}=S_{b},\Theta^{(t)})=1$
if $k^{*}=\arg\min_{k}U_{b}(k)$, and 0 otherwise.

In summary, the Holistic Community Outlier detection algorithm shown in
Algorithm 2 works as follows. It begins with some initial label assignment of
the vertices in the HMRF. In the M-step, the model parameters are estimated
using the EM algorithm to maximize the data likelihood, based on the current
label assignment. In the E-step, Algorithm 1 is run to re-assign the labels to
the objects by minimizing $U_{b}^{(k)}$ for each HMRF vertex sequentially. The
E-step and M-step are repeated until convergence is achieved, and the outliers
are the nodes that have 0 as the final estimated labels.

Algorithm 2 Holistic Community Outlier Detection

Input: Node/Edge data $S$, weights $W$, set of model parameters $\theta$,
number of clusters $K$, hyper-parameters
($\lambda_{1},\lambda_{2},\lambda_{3}$), threshold $a_{0}$, initial assignment
of labels $Z^{(1)}$
Output: Set of Holistic Community Outliers

1:Randomly set $Z^{(0)}$

2:$t\leftarrow 1$

3:while Z(t) is not close enough to Z(t-1) do

4: M-step: Given $Z^{(t)}$, update parameters $\Theta^{(t+1)}$ according to
Eqs. 19, 20 or 21.

5: E-step: Given $\Theta^{(t+1)}$, update the hidden labels as $Z^{(t+1)}$
using Algorithm 1.

6: $t\leftarrow t+1$

7:return the indices of outliers: $\\{i:Z_{b}^{(t)}=0,b\in B\\}$

##  V Discussions

In this section, we discuss how to set the hyperparameters and how to
initialize the hidden labels.

Setting Hyperparameters: The HCOutlier detection algorithm has the following
hyperparameters: threshold $a_{0}$, clique importance variables,
$\lambda_{1},\lambda_{2},\lambda_{3}$ and number of communities $K$.

$\lambda_{1},\lambda_{2},\lambda_{3}$ indicate the importance of link between
two nodes, the importance of link between edge-vertex and a node-vertex, and
the importance of the triangle between the edge-vertex and the node-vertices
of which the edge is incident respectively. If $\lambda$s are set to low
values, the algorithm will consider only node information for finding the
outliers. If their values are set too high, all connected nodes will have the
same label, so an upper bound can be set for
$\lambda_{1}+\lambda_{2}+\lambda_{3}$, such that a value above this bound will
result into empty communities. High $\lambda_{1}$ will give more importance to
the linkage in the graph. High $\lambda_{2}$ will give high importance to
consistency between the node data and edge data in the graph. High
$\lambda_{3}$ will give high importance to consistency between the edge data
and both the incident nodes in the graph.

The threshold $a_{0}$ can be replaced by another parameter (percentage of
outliers $r$) as follows. In Algorithm 1, first calculate
$\hat{Z}_{i}=\arg\min_{k}U_{i}(k)(k\neq 0)$ for each $i\in\\{1,\cdots,|V|\\}$
and then sort $U_{i}(\hat{Z}_{i})$ in non-descending order. Finally, select
top $r$ percentage as outliers.

$K$ represents the number of normal communities. For small value of $K$,
algorithm will find the global outliers, and for large value of $K$ many local
outliers will be detected because of many communities. An appropriate $K$ can
be set using a variety of methods like Akaike Information Criterion (AIC),
Bayesian Information Criterion (BIC), Minimum Description Length (MDL), etc.

Initialization of labels: Instead of initializing $Z$ randomly, we initialize
$Z$ values by clustering the nodes without considering outliers. To overcome
local optima issues, we run the algorithm multiple times with different
initialization, and choose the one with the largest data likelihood value.

##  VI Experiments

Evaluation of outlier detection algorithms is difficult in general due to lack
of ground truth. Hence, we perform experiments on multiple synthetic datasets.
We evaluate outlier detection accuracy of the proposed algorithm based on
outliers injected in synthetic datasets. We evaluate the results on real
datasets using case studies. We perform comprehensive analysis of objects to
justify the top few outliers returned by the proposed algorithm. The code and
the data sets are publicly available111https://github.com/supriya-
pandhre/HCODA. All experiments are performed on a machine with Intel core
i3-2330M processor running at 2.20GHz and 4GB RAM.

We compare our algorithm with Community Outlier Detection Algorithm (CODA)
[12]. CODA is also an algorithm for community-based outlier detection which
performs community detection using node data and linkage; but ignores edge-
data completely.

###  VI-A Synthetic Datasets

We synthetically generate three graphs: Graph A ($|V|$=1000), Graph B
($|V|$=10000) and Graph C ($|V|$=100000). The node data is generated using 5
different Gaussian distributions and similar procedure is followed to generate
edge data as well. Then for each of these graphs, different percentage of
outliers are injected by randomly changing the data associated with 1%, 5% and
10% of the nodes.

We generate a variety of synthetic datasets by varying the number of nodes in
the graph, percentage of outliers injected in the graph and percentage of
outliers to be extracted by the algorithm. Table I shows the synthetic dataset
results for the baseline (CODA) as well as the proposed algorithm (HCODA). We
set the number of clusters ($K$) to 5 for these experiments (based on the
generation process). We measure the performance of the two algorithms from two
perspectives: firstly, accuracy of extraction of the injected outliers (OD
Acc.) and secondly, how well it assigns the community label to all the nodes
of the graph (CA Acc.). Note that each cell of the table corresponds to
average over five runs of the algorithm. As the table shows, the proposed
algorithm (HCODA) is 6.2% more accurate than the baseline on average in terms
of outlier detection accuracy. Similarly, HCODA is 2.2% better than CODA on
average. The performance is consistent across various graph sizes as well as
across different degrees of outlierness in the graph.

TABLE I: Synthetic Dataset Results on Graphs A, B and C (K=5; OD Acc.=Outlier Detection Accuracy, CA Acc.=Community Assignment Accuracy; CODA is Baseline, HCODA is the proposed algorithm) $|V|$ |  % injected |  % extracted |  CODA [12] OD Acc. |  HCODA OD Acc. |  CODA [12] CA Acc. |  HCODA CA Acc. |  Average runtime of HCODA (ms)
---|---|---|---|---|---|---|---
1000 |  1 |  1 |  1.000 |  1.000 |  0.714 |  0.713 |  898.6
1000 |  5 |  1 |  1.000 |  1.000 |  0.725 |  0.735 |  930
1000 |  5 |  5 |  0.760 |  0.800 |  0.739 |  0.756 |  899
1000 |  10 |  1 |  1.000 |  1.000 |  0.683 |  0.699 |  917.2
1000 |  10 |  5 |  0.960 |  0.980 |  0.720 |  0.738 |  913
1000 |  10 |  10 |  0.760 |  0.840 |  0.729 |  0.762 |  926
10000 |  1 |  1 |  0.690 |  0.730 |  0.770 |  0.784 |  9846.6
10000 |  5 |  1 |  0.970 |  1.000 |  0.740 |  0.755 |  10259
10000 |  5 |  5 |  0.746 |  0.780 |  0.758 |  0.777 |  10478.8
10000 |  10 |  1 |  1.000 |  1.000 |  0.705 |  0.718 |  10026.8
10000 |  10 |  5 |  0.958 |  1.580 |  0.741 |  0.757 |  9840.4
10000 |  10 |  10 |  0.795 |  0.814 |  0.759 |  0.777 |  9626.8
100000 |  1 |  1 |  0.722 |  0.735 |  0.773 |  0.787 |  120587
100000 |  5 |  1 |  0.995 |  0.996 |  0.747 |  0.762 |  113171.5
100000 |  5 |  5 |  0.751 |  0.789 |  0.764 |  0.783 |  113749.2
100000 |  10 |  1 |  0.997 |  0.999 |  0.698 |  0.714 |  104812.4
100000 |  10 |  5 |  0.946 |  0.974 |  0.733 |  0.751 |  103004
100000 |  10 |  10 |  0.784 |  0.808 |  0.750 |  0.770 |  100314

Hyperparameter Sensitivity: To understand the impact of various
hyperparameters ($\lambda$’s), we performed a few experiments. The results are
shown in Figures 3, 4 and 5. Figure 3 shows the sensitivity of the outlier
detection accuracy with respect to variation of $\lambda_{3}$. We plot the
curves for Graph A and B for the case of 10% injected outliers and 10%
outliers to be extracted. Recall that $\lambda_{3}$ is the weight for the
triangular clique. As can be seen from the figure, higher values of
$\lambda_{3}$ are preferable but in general any value greater than 0.5 is
reasonable.

Figure 3: Sensitivity of $\lambda_{3}$

Figures 4 and 5 show the sensitivity of the outlier detection accuracy with
respect to variation of $\lambda_{1}$ for both the proposed algorithm (HCODA)
and the baseline (CODA). Figures 4 is the plot for Graph A while Figures 5 is
the one for Graph B. Both the plots are for the case of 10% injected outliers
and 1% outliers to be extracted. Recall that $\lambda_{1}$ is the weight for
the linkage in the original graph. As can be seen from the figure, lower
values of $\lambda_{1}$ are preferable both in the case of CODA as well as
HCODA.

Figure 4: Sensitivity of $\lambda_{1}$ (Graph A) Figure 5: Sensitivity of
$\lambda_{1}$ (Graph B)

We noticed that the algorithm is not significantly sensitive to the parameter
$\lambda_{2}$ and hence we do not show the corresponding plot.

###  VI-B Four Area Dataset

DBLP (http://dblp.uni-trier.de/) contains information about computer science
journals and proceedings. Four Area is a subset of DBLP for the four areas of
data mining (DM), databases (DB), information retrieval (IR) and machine
learning (ML). It consists of papers from 20 conferences (five per area): KDD,
PAKDD, ICDM, PKDD, SDM, ICDE, VLDB, SIGMOD, PODS, EDBT, SIGIR, WWW, ECIR,
WSDM, IJCAI, AAAI, ICML, ECML, CVPR, CIKM. Thus, we consider the authors who
have published papers in these conferences, and work with the co-authorship
network (edge weight = co-authorship frequency). The edge data consisted of a
vector of size four representing the count of papers co-authored in a
particular research area.

The graph contains a total of 42844 author nodes. Each author is associated
with a vector of size 20 containing the count of papers published by an author
in the twenty conferences. There is an edge between two authors if they co-
authored a paper together and the count of such co-authored papers is the
weight $W_{v_{i}v_{j}}$ between two nodes.

The graph contains 118618 co-authorship edges. The weight of the link between
the author-vertex and the co-authorship-edge-vertex in the HMRF (i.e.,
$W_{v_{i}e_{ij}}$) is set to the inverse of the number of co-authors of author
$v_{i}$ in the graph. $W_{v_{i},v_{j},e_{ij}}$ is set to ratio of number of
papers where authors $v_{i}$ and $v_{j}$ are co-authors to the total number of
papers on which either $v_{i}$ or $v_{j}$ are authors. We set the number of
communities to $K$=4 (i.e., four normal communities and an outlier community).
Also, we set the percentage of outlier parameter $r$ as 1%. The average
execution time of the lgorithm is 30.32 seconds.

Case Studies: Result of algorithm show that it is able to identify interesting
nodes(authors) and edges(co-authorship). We validate the result produced by
algorithm by manually visiting the authors’ homepages. For example, work by
Sameer K. Antani is mainly in Clinical data standards and electronic medical
records, but he published a paper with authors working in information
retrieval i.e. node data of Sameer K. Antani is different from the fellow co-
authors but the relationship is similar to what two authors from information
retrieval should have and hence the algorithm has identified this node as
interesting one. Similarly, Ivo Krka mainly focuses on software engineering
and system modeling, however, he has published a paper on data mining and
hence identified by the algorithm.

The proposed algorithm also identified authors based on the edge information.
We discuss a few cases now. Anindya Datta usually publishes in information
systems, and Debra E. VanderMeer usually publishes work related to design
science research, but their co-authored work is published on data management
and very large databases topics. Sabyasachi Saha has co-authored papers with
Sandip Sen on topics related to artificial intelligence and he has also
published work on information and knowledge management with Pang-Ning Tan. The
algorithm was able to identify him because of his work in multiple research
areas.

##  VII Conclusion

In this paper, we introduced a method (HCODA) that detects novel Holistic
Community Outlier graph nodes by taking into account the node data and edge
data simultaneously to detect anomalies. We modeled the problem as a community
detection task using a Hidden Random Markov Model, where outliers form a
separate community. We used ICM and EM to infer the hidden community labels
and model parameters iteratively. Experimental results show that the proposed
algorithm consistently outperforms the baseline CODA method on synthetic data,
and also identifies meaningful community outliers from the Four Area network
data.

## References

  * [1] James Abello, Tina Eliassi-Rad, and Nishchal Devanur.  Detecting novel discrepancies in communication networks.  In ICDM 2010, The 10th IEEE International Conference on Data Mining, Sydney, Australia, 14-17 December 2010, pages 8–17, 2010.
  * [2] Charu C. Aggarwal.  Outlier Analysis.  Springer, 2013.
  * [3] Charu C. Aggarwal, Yuchen Zhao, and Philip S. Yu.  Outlier Detection in Graph Streams.  In Proc. of the $27^{th}$ Intl. Conf. on Data Engineering (ICDE), pages 399–409. IEEE Computer Society, 2011.
  * [4] Leman Akoglu and Christos Faloutsos.  Event detection in time series of mobile communication graphs.  In Army Science Conference, pages 77–79, 2010.
  * [5] Leman Akoglu, Mary McGlohon, and Christos Faloutsos.  Oddball: Spotting Anomalies in Weighted Graphs.  In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 410–421. Springer, 2010.
  * [6] Leman Akoglu, Hanghang Tong, and Danai Koutra.  Graph based Anomaly Detection and Description: A Survey.  Data Mining and Knowledge Discovery, 29(3):626–688, 2015.
  * [7] Julian Besag.  On the Statistical Analysis of Dirty Pictures.  Journal of the Royal Statistical Society. Series B (Methodological), pages 259–302, 1986.
  * [8] Alex Beutel, Wanhong Xu, Venkatesan Guruswami, Christopher Palow, and Christos Faloutsos.  Copycatch: Stopping Group Attacks by Spotting Lockstep Behavior in Social Networks.  In Proceedings of the 22nd international conference on World Wide Web, pages 119–130. ACM, 2013.
  * [9] Brigitte Boden, Stephan Günnemann, Holger Hoffmann, and Thomas Seidl.  Mining Coherent Subgraphs in Multi-layer Graphs with Edge Labels.  In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1258–1266. ACM, 2012.
  * [10] Deepayan Chakrabarti.  Autopart: Parameter-free Graph Partitioning and Outlier Detection.  In European Conference on Principles of Data Mining and Knowledge Discovery, pages 112–124. Springer, 2004.
  * [11] Varun Chandola, Arindam Banerjee, and Vipin Kumar.  Anomaly detection: A Survey.  ACM computing surveys (CSUR), 41(3):15, 2009.
  * [12] Jing Gao, Feng Liang, Wei Fan, Chi Wang, Yizhou Sun, and Jiawei Han.  On Community Outliers and their Efficient Detection in Information Networks.  In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 813–822. ACM, 2010.
  * [13] Manish Gupta, Jing Gao, Charu Aggarwal, and Jiawei Han.  Outlier Detection for Temporal Data.  Synthesis Lectures on Data Mining and Knowledge Discovery, 5(1):1–129, 2014.
  * [14] Manish Gupta, Jing Gao, and Jiawei Han.  Community Distribution Outlier Detection in Heterogeneous Information Networks.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 557–573. Springer, 2013.
  * [15] Manish Gupta, Jing Gao, Yizhou Sun, and Jiawei Han.  Community Trend Outlier Detection using Soft Temporal Pattern Mining.  In Proc. of the European Conf. on Machine Learning and Knowledge Discovery in Databases (ECML PKDD), pages 692–708, 2012.
  * [16] Manish Gupta, Jing Gao, Yizhou Sun, and Jiawei Han.  Integrating Community Matching and Outlier Detection for Mining Evolutionary Community Outliers.  In Proc. of the $18^{th}$ ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining (KDD), pages 859–867, 2012.
  * [17] Manish Gupta, Jing Gao, Xifeng Yan, Hasan Cam, and Jiawei Han.  Top-k interesting subgraph discovery in information networks.  In 2014 IEEE 30th International Conference on Data Engineering, pages 820–831. IEEE, 2014.
  * [18] Victoria J Hodge and Jim Austin.  A Survey of Outlier Detection Methodologies.  Artificial intelligence review, 22(2):85–126, 2004.
  * [19] Tsuyoshi Idé and Hisashi Kashima.  Eigenspace-based Anomaly Detection in Computer Systems.  In Proc. of the $10^{th}$ ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining (KDD), pages 440–449, 2004.
  * [20] Brandon Pincombe.  Anomaly Detection in Time Series of Graphs using ARMA Processes.  ASOR Bulletin, 24(4):2–10, 2005.
  * [21] Guo-Jun Qi, Charu C Aggarwal, and Thomas Huang.  Community Detection with Edge Content in Social Media Networks.  In 2012 IEEE 28th International Conference on Data Engineering, pages 534–545. IEEE, 2012.
  * [22] Stephen Ranshous, Shitian Shen, Danai Koutra, Steven Harenberg, Christos Faloutsos, and Nagiza F. Samatova.  Anomaly detection in dynamic detworks: A survey.  WIREs Comp Stat, 7(3):223–247, 2015.
  * [23] Jimeng Sun, Huiming Qu, Deepayan Chakrabarti, and Christos Faloutsos.  Neighborhood Formation and Anomaly Detection in Bipartite Graphs.  In Fifth IEEE International Conference on Data Mining (ICDM’05), pages 418–425. IEEE, 2005.
  * [24] Jimeng Sun, Dacheng Tao, and Christos Faloutsos.  Beyond streams and graphs: dynamic tensor analysis.  In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 374–383. ACM, 2006.