11institutetext: Institute of Theoretical and Applied Informatics, Polish
Academy of Sciences (PAN), ul. Baltycka 5, 44100 Gliwice, Poland
22institutetext: Lab. I3S, Université Côte d’Azur, Grand Château, 06103 Nice
Cecex 2, France 33institutetext: Department of Computer Engineering, Yaşar
University, Üniversite Cad. No: 37-39, Ag̃açlı Yol, Bornova, Izmir, Turkey
33email: seg<EMAIL_ADDRESS>
# Real-Time Cyberattack Detection with Offline and Online Learning††thanks:
This research has been supported by the European Commission H2020 Program
under the IoTAC Research and Innovation Action, under Grant Agreement No.
952684.

Erol Gelenbe 112233 0000-0001-9688-2201 Mert Nakıp 11 0000-0002-6723-6494

###### Abstract

This paper presents several novel algorithms for real-time cyberattack
detection using the Auto-Associative Deep Random Neural Network, which were
developed in the HORIZON 2020 IoTAC Project. Some of these algorithms require
offline learning, while others require the algorithm to learn during its
normal operation while it is also testing the flow of incoming traffic to
detect possible attacks. Most of the methods we present are designed to be
used at a single node, while one specific method collects data from multiple
network ports to detect and monitor the spread of a Botnet. The evaluation of
the accuracy of all the methods is carried out with real attack traces. These
novel methods are also compared with other state-of-the-art approaches,
showing that they offer better or equal performance, at lower computational
learning and shorter detection times as compared to the existing approaches.

###### Keywords:

Attack detection Cybersecurity Internet of Things (IoT) Auto-Associative
Random Neural Network Random Neural Network

##  1 Introduction

As the application areas of the Internet expand, and the number of IoT devices
increases rapidly, 52 % of the devices deployed in the IoT devices are
expected [14] to be of low-cost and have low-maintenance, and typically
perform a single task at a time. This sector of the IoT is often known as the
“Massive IoT” which is largely composed of devices which cannot run complex
real-time attack detection or prevention algorithms. Thus the IoT and the
Internet as a whole are becoming increasingly vulnerable to cyberattacks [18,
33, 50].

Another industry report [3] states that 70 % of IoT devices are vulnerable to
attacks, such as common Denial of Service (DoS) or Distributed Denial of
Service attacks (DDoS) [15]. According to some sources these represent 20 % of
all attacks [8], in which attackers or malicious devices send numerous
meaningless requests to prevent the targeted devices for arrying out their
normally required activities. In addition, many of these attacks can inject
malware [13, 11], as with Botnets which cause the victim to become an attacker
that in turn generates a flood of traffic against other IP addresses and
servers. A ajor example is the 2016 massive Mirai Botnet attack targeted
Domain Name System (DNS) provider Dyn [35], compromising numerous websites and
servers of leading companies [9, 27]. Botnets also have other undesirable
effects, such as increasing the power consumption and memory occupancy of the
devices [48]. Thus in detecting and countering a cyberattack, it is important
to identify not the malicious packets, and also the other compromised IP
addresses which themselves become attackers against IoT networks.

###  1.1 Related Work

Over recent years, much work has studied the characteristics of Botnet attacks
[6], and analyzed the charateristics of attack traffic flows [30]. The source
code of such attacks was examined in [43] while in [35] their capabilities and
impact are studied. Some authors [5] also suggest using blockchains to protect
IoT devices.

Other work has used different machine learning methods to detect Botnet
attacks including k-Nearest Neighbours (KNN), Support Vector Machines (SVM),
Decision Trees (DT) and Multi-Layer Perceptrons (MLP). Thus the work in [47]
compares the performance of classification models and Neural Networks (NNs),
and in [32] NNs are used to to detect Mirai Botnet attacks against Software
Defined Networks. While the work in [45] uses a deep MLP, in [44] NNs and
Naive Bayesian networks (NB) were used with a sequential architecture, and in
[49] Botnets are detected via a sparse representation framework. To detect
Botnet attacks using deep learning, in [36] text recognition is carried out
with a bidirectional Long-Short-Term Memory (LSTM). Furthermore in [34] a
Convolutional Neural Network (CNN) is combined with a feature transformation,
while the work in [41] cascaded a CNN with a LSTM. In [28] Classification and
Regression Trees (CART) were used, while in [7] DTs, Gradient Boosting and
Random Forest were considered, and in [42] Logistic Regression was used.

In [31] an optimization-based method scans the number of destination ports in
the headers of selected IoT packets to detect Bots infected by Mirai. Others
[12] developed a traffic analysis technique based on evidence theory in order
to detect compromised devices selecting the rarest features from the set of
traffic features including number of reconnections, transport layer protocol,
and source/destination ports. In [40], federated learning and language
analysis is used to detect malicious devices using pre-identified individual
device types, and in [4] compromised gateways that monitor the downlink
channels in an IoT network are detected. In [46] compromised mobile devices
are deected taking into account their location, classifying locations and
their possible changes as unusual behavior.

In earlier work, a Random Neural Network gradient descent learning technique
[20, 24] had been used to detect SYN type DoS attacks [16]. However the
approaches discussed in this paper are based on a more elaborate machine
learning model, the Auto-Associative Dense Random Neural Network (AADRNN),
that was first developed in [10] using a Deep and Dense Random Neural Network
[19, 25]. In addition, it uses an original characterization of network traffic
proposed in [38] to detect various types of attacks.

##  2 Contributions of the Present Paper

This paper presents novel Attack Detection (AD) algorithms that were developed
within the IoTAC Project funded by the Horizon2020 Programme, based on Auto-
Associative version of the Deep Random Neural Network (AADRNN). The three sets
of results we present show the ability of this AD learning approach to detect
Botnet attacks with online learning, as well as to simultaneously detect
different types of attacks, and its ability to identify compromised IoT
devices.

The main advantage of this approach is the use of an auto-associative network
(namely, the AADRNN), that only needs to learn from the legitimate network
traffic, without needing to learn from the different types of attacks that may
occur, and then generalizes what it has learned only from nomal traffic to
differentiate between benign and malicious packets so as to identify
compromised devices. Thus:

  1. 1.

Training of the proposed algrithms does not require attack traffic data, which
saves considerably on the time needed to collect it to create it artificially,
and also on the algorithms’ learning times.

  2. 2.

It follows that a give AADRNN after training with normal data can accurately
detect various types of attacks.

  3. 3.

The proposed AD can be trained in parallel to its real-time operation (when it
provides detection results) using the ongoing legitimate network traffic.

##  3 IoTAC’s Attack Detector Algorithms

IoTAC’s AD has been designed to recognize traffic patterns through specially
defined metrics and is trained with normal traffic to create an Auto-
Association Dense RNN (called AADRNN). Thus, this AD can recognize malicious
traffic even if the characteristics of an attack are unknown and no pre-
collected attack data is available.

Figure 1: Component diagram of AD

Figure 1 displays the component diagram of AD including the subcomponents,
APIs, external databases, and user interfaces. As shown in this figure, the AD
component is comprised of four subcomponents: Metrics Extraction, AD
Initialization, AADRNN Attack Detection, and AADRNN Training.

###  3.1 AD Initialization

At the first use of the AD module, parameter initialization is required for
the methods utilized in AD, such as Metric Extraction and AADRNN. To this end,
the AD Initialization subcomponent is developed to set the parameters of AD as
predefined values. It also calculates the initial values of scaling factors
used to normalize the metric values through historical normal traffic for a
fixed length time window.

###  3.2 Metric Extraction

First, the Metric Extraction subcomponent calculates three metrics proposed in
[38] to capture the footprints of the Mirai Botnet attack on the network
traffic:

  1. 1.

The total size of the latest packets,

  2. 2.

The average inter-transmission times of the latest packets,

  3. 3.

The total number of packets that are transmitted in a constant-length time
window.

These metrics are specifically defined to represent network traffic in a way
that the differences between attack and normal traffic become more visible
while they can be calculated using only the header information of the traffic
packets. Therefore, these metrics can be easily calculated without the need
for any sensitive or device-specific information, thus preventing AD from
making biased decisions, remaining anonymous regarding packet content and
communicating devices, and suitable for real-time operation on lightweight
systems.

###  3.3 AADRNN Attack Detection

The AADRNN Attack Detection subcomponent uses a trained AADRNN and a simple
decision-making algorithm. Based on the extracted metrics, the AADRNN in this
subcomponent predicts the expected metric values for the normal operation of
the network. That is, AADRNN provides the metric values expected to be
obtained if all packets are benign. The decision-making algorithm considers
these expected metric values as a baseline for actual metric values expecting
to observe a significant difference between them for malicious packet
transmission. Accordingly, this simple algorithm calculates the weighted
average of the absolute differences between the expected and actual metric
values and applies a threshold to the mean.

###  3.4 AADRNN Training

The AADRNN model of AD is trained incrementally in parallel to the real-time
operation of AD through ADT API using only normal traffic to learn its
metrics. To this end, we have developed an incremental semi-supervised
training procedure [39] based on a reconstruction problem [19]. Specifically,
our incremental training algorithm stores historical normal traffic for fixed-
length time windows and updates the connection weights of the AADRNN for this
traffic at the end of each window. During this incremental training, the
connection weights of this model are updated to reconstruct the metrics of
normal traffic from a noise-added version of these metrics. In this way, we
have obtained an auto-associative network that is able to retrieve normal
metrics from any metrics (which might be for either normal or malicious
traffic) provided as input. Using an auto-associative network with the
proposed metrics provides the following benefits for the AD module:

  1. 1.

Since the defined traffic metrics are calculated using only the high-level
(anonymous) packet information, the AD module does not use and does not
require knowledge of network architecture or device specifications.

  2. 2.

The AD module has the ability to react to malicious acitivities only by
learning the traffic patterns during the normal operation of the IoT network.
Therefore,

    1. (a)

it does not require data on "attack traffic" for training,

    2. (b)

it has no bias for any particular type of attack, and

    3. (c)

a single AD can detect several types of attacks simultaneously.

##  4 AADRNN-based Algorithm Detects Several Types of Cyberattacks

The AADRNN-based design of AD provides an opportunity to adapt its usage for
detecting different types of attacks in various environments. Thus we have
extended the design of the AADRNN attack detector for usage in three areas:

  * •

Botnet Attack Detection with Online Learning,

  * •

Simultaneous Detection of Different Attack Types, and

  * •

Compromised IoT Device Identification.

For each of these uses, the method i.e., AADRNN remains the same, while the
traffic metrics and the decision-making algorithm are adapted to each use.

###  4.1 Botnet Attack Detection with Online Learning

The original design of the AD module is targeting the Botnet attack detection.
Thus, this module with AADRNN and the proposed traffic metrics was evaluated,
as it is, for the detection of the Mirai Botnet attack [38, 39] on a publicly
available Kitsune dataset [2, 37]. This dataset contains 764,137 transmissions
including both normal and attack traffic packets. The evaluation results
displayed in Figure 2 have shown that the incremental online learning property
of AD is highly successful with a low false alarm rate as it adapts to the
changes in normal traffic over time.

Figure 2: Performance comparison of AADRNN based AD under Incremental Online
Training against Offline Training

Table 1 compares the performance of AADRNN-based AD with that of the state-of-
the-art ML methods. The numerical results in this table show the high success
of our AD and its superior performance against other ML methods. In detail, we
see that our AD based on AADRNN achieves 99.82 % true positive and 99.98 %
true negative rates.

Table 1: COMPARISON OF DIFFERENT ML METHODS IN AD MODULE | ML
---
Methods
Accuracy | TPR | FNR | TNR | FPR
AADRNN | 99.84 | 99.82 | 0.18 | 99.98 | 0.02
KNN | 99.79 | 99.79 | 0.21 | 99.75 | 0.25
Lasso | 99.78 | 99.75 | 0.25 | 99.95 | 0.05
Simple Thresholding | 93.18 | 93.09 | 6.94 | 93.63 | 6.37

###  4.2 Simultaneous Detection of Different Attack Types

The AD module was further implemented to detect various types of attacks
simultaneously [22]. To this end, two main revisions have been performed on
the design of AD. First, the Metric Extraction module was exchanged with a
preprocessing algorithm to apply min-max normalization on any input features
provided by the developer (or in a dataset). Then, the decision-making
algorithm was enhanced replacing the decision threshold with a statistical
whisker which is calculated using the training data. Since extensive threshold
selection often provides higher performance for the dataset than the actual
test data, data-driven threshold determination, e.g. whisker-valued threshold,
eliminates extensive threshold selection.

During the performance evaluation of the AD module to simultaneously detect
multiple types of attacks, the KDD Cup’99 data set [1] was used. Our AD was
trained using only the benign samples in the smaller training set (which is
equal to 97,278 samples) and evaluated using all samples in the test set
(which is equal to 311,029 samples). As the numerical test results on KDD
Cup’99 data set in Figure 3 show, the prediction accuracy of the AD module is
above 98 % for 21 out of 37 attack types.

Figure 3: Performance of the AD module for each attack type in the KDD Cup’99
dataset

###  4.3 Compromised IoT Device Identification

The AD methods wre also extended to identify the compromised IoT devices
during DDoS attacks, and especially Botnet attacks [23]. In this way, the AD
module may enable the gateway to blacklist devices affected by malware or take
preventive actions against the spread of the attack. To this end, the defined
traffic metrics were extended to analyze received and transmitted traffic
separately resulting in 6 different metrics. An independent detector was
utilized for each existing IP address in the considered IoT network, where
each detector was sequentially trained over time. Also, the output of AD was
revised to obtain the infection level of the device under consideration.

During the evaluation of the performance of the AADRNN based AD, we have used
various types of DDoS attacks provided in three different datasets: Kitsune
[2], MedBIoT [26], and Bot-IoT [29]. The results in Figure 4 show that the
extended version of the AD module is able to successfully identify compromised
devices in the course of various types of DoS and DDoS attacks.

Figure 4: Performance of AD for compromised IoT device identification on
Kitsune, MedBIoT, and Bot-IoT data sets

##  5 Conclusions

This paper has reviewed the algorithms developed in the IoTAC project, based
on an AADRNN using original network traffic metrics, to detect cyberattacks in
real-time with both offline and online learning. Experimental results are
summarized, and show that these algorithms are able to accurately:

  1. 1.

Detect Botnet attacks with periodically activated incremental learning
concurrently with real-time attack detection,

  2. 2.

Detect different types of cyberattacks simultaneously using a single AADRNN
that is trained offline on normal non-attack traffic, and

  3. 3.

Identify compromised IoT devices during an ongoing cyberattack.

Since the AADRNN is auto-associative, it learns communication patterns for
normal (non-attack) network traffic, and differentiates malicious from benign
packets (or normal and compromised devices) without prior learning of
malicious traffic. Using the publicly available Kitsune, MedBIoT, BotIoT, and
KDD’99 data sets, the three AADRNN based algorithms have been evaluated, and
it was observed that all three lead to a high detection accuracy for various
types of DoS and DDoS attacks.

Future research will examine methods for post-processing of the algorithms’
output to attempt to further reduce false alarms by an order of magnitude,
from the output data of AD algorithms. Another useful direction can be to
investigate dynamic system management techniques, such as those investigated
in [21, 17], to mitigate the consequences of cyberattacks using dynamic
traffic management for specific IoT systems.

## Acknowledgement

The authors gratefully acknowledge the support of the European Commission
H2020 Program under the IoTAC Research and Innovation Action, under Grant
Agreement No. 952684, for the research presented in this paper.

## References

  * [1] KDD Cup 1999 Data, http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html
  * [2] Kitsune Network Attack Dataset, https://www.kaggle.com/ymirsky/network-attack-dataset-kitsune
  * [3] Hp study reveals 70 percent of Internet of Things devices vulnerable to attack (Accessed on 25012022), https://www.hp.com/us-en/hp-news/press-release.html%3Fid=1744676
  * [4] Abhishek, N.V., Lim, T.J., Sikdar, B., Tandon, A.: An intrusion detection system for detecting compromised gateways in clustered iot networks. In: 2018 IEEE International Workshop Technical Committee on Communications Quality and Reliability (CQR). pp. 1–6. IEEE (2018)
  * [5] Ahmed, Z., Danish, S.M., Qureshi, H.K., Lestas, M.: Protecting IoTs from Mirai Botnet attacks using blockchains. In: 2019 IEEE 24th International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD). pp. 1–6 (2019). https://doi.org/10.1109/CAMAD.2019.8858484
  * [6] Antonakakis, M., April, T., Bailey, M., Bernhard, M., Bursztein, E., Cochran, J., Durumeric, Z., Halderman, J.A., Invernizzi, L., Kallitsis, M., Kumar, D., Lever, C., Ma, Z., Mason, J., Menscher, D., Seaman, C., Sullivan, N., Thomas, K., Zhou, Y.: Understanding the Mirai Botnet. In: Proceedings of the 26th USENIX Security Symposium (2017), https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/antonakakis
  * [7] Banerjee, M., Samantaray, S.: Network traffic analysis based iot botnet detection using honeynet data applying classification techniques. International Journal of Computer Science and Information Security (IJCSIS) 17(8) (2019)
  * [8] Benzarti, S., Triki, B., Korbaa, O.: A survey on attacks in Internet of Things based networks. In: 2017 International conference on engineering & MIS (ICEMIS). pp. 1–7. IEEE (2017)
  * [9] Biggs, J.: Hackers release source code for a powerful DDoS app called Mirai. TechCrunch (October 2018), https://techcrunch.com/2016/10/10/hackers-release-source-code-for-a-powerful-ddos-app-called-mirai/
  * [10] Brun, O., Yin, Y., Gelenbe, E., Kadioglu, Y.M., Augusto-Gonzalez, J., Ramos, M.: Deep learning with dense random neural networks for detecting attacks against IoT-connected home environments. In: International ISCIS Security Workshop. pp. 79–89. Springer, Cham (2018)
  * [11] Carl, G., Kesidis, G., Brooks, R., Rai, S.: Denial-of-Service attack-detection techniques. IEEE Internet Computing 10(1), 82–89 (2006). https://doi.org/10.1109/MIC.2006.5
  * [12] Chatterjee, M., Namin, A.S., Datta, P.: Evidence fusion for malicious bot detection in iot. In: 2018 IEEE International Conference on Big Data (Big Data). pp. 4545–4548 (2018). https://doi.org/10.1109/BigData.2018.8621895
  * [13] CISA: Understanding Denial-of-Service attacks, https://us-cert.cisa.gov/ncas/tips/ST04-015
  * [14] Cisco: Cisco Annual Internet Report (2018–2023) (Mar 2020), https://www.cisco.com/c/en/us/solutions/collateral/executive-perspectives/annual-internet-report/white-paper-c11-741490.html
  * [15] Douligeris, C., Mitrokotsa, A.: DDoS attacks and defense mechanisms: classification and state-of-the-art. Computer networks 44(5), 643–666 (2004)
  * [16] Evmorfos, S., Vlachodimitropoulos, G., Bakalos, N., Gelenbe, E.: Neural network architectures for the detection of syn flood attacks in IoT systems. In: Proceedings of the 13th ACM International Conference on PErvasive Technologies Related to Assistive Environments. pp. 1–4 (2020)
  * [17] Fröhlich, P., Gelenbe, E., Fiołka, J., Checinski, J., Nowak, M., Filus, Z.: Smart sdn management of fog services to optimize qos and energy. Sensors 21(9), 3105 (2021), https://doi.org/10.3390/s21093105
  * [18] Frustaci, M., Pace, P., Aloi, G., Fortino, G.: Evaluating critical security issues of the IoT world: Present and future challenges. IEEE Internet of Things Journal 5(4), 2483–2495 (2018). https://doi.org/10.1109/JIOT.2017.2767291
  * [19] Gelenbe, E., Yin, Y.: Deep learning with random neural networks. In: 2016 International Joint Conference on Neural Networks (IJCNN). pp. 1633–1638 (2016). https://doi.org/10.1109/IJCNN.2016.7727393
  * [20] Gelenbe, E.: Random neural networks with negative and positive signals and product form solution. Neural Computation 1(4), 502–510 (1989)
  * [21] Gelenbe, E., Domanska, J., Frohlich, P., Nowak, M., Nowak, S.: Self-aware networks that optimize security, qos and energy. Proceedings of the IEEE 108(7), 1150–1167 (2020)
  * [22] Gelenbe, E., Nakıp: G-networks can detect different types of cyberattacks. In: 2022 30th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS). pp. 1–8. IEEE (2022)
  * [23] Gelenbe, E., Nakip, M.: Traffic based sequential learning during botnet attacks to identify compromised iot devices. IEEE Access (2022)
  * [24] Gelenbe, E., Stafylopatis, A.: Global behavior of homogeneous random neural systems. Applied mathematical modelling 15(10), 534–541 (1991)
  * [25] Gelenbe, E., Yin, Y.: Deep learning with dense random neural networks. In: International Conference on Man–Machine Interactions. pp. 3–18. Springer (2017)
  * [26] Guerra-Manzanares, A., Medina-Galindo, J., Bahsi, H., Nõmm, S.: MedBIoT: Generation of an IoT botnet dataset in a medium-sized iot network. In: ICISSP. pp. 207–218 (2020)
  * [27] Hackett, R.: Why a hacker dumped code behind colossal website-trampling botnet (October 2016)
  * [28] Htwe, C.S., Thant, Y.M., Thwin, M.M.S.: Botnets attack detection using machine learning approach for iot environment. In: Journal of Physics: Conference Series. vol. 1646, p. 012101. IOP Publishing (2020)
  * [29] Koroniotis, N., Moustafa, N., Sitnikova, E., Turnbull, B.: Towards the development of realistic botnet dataset in the internet of things for network forensic analytics: Bot-IoT dataset. Future Generation Computer Systems 100, 779–796 (2019). https://doi.org/https://doi.org/10.1016/j.future.2019.05.041, https://www.sciencedirect.com/science/article/pii/S0167739X18327687
  * [30] Kumar, A., Lim, T.J.: Early detection of Mirai-like IoT Bots in large-scale networks through sub-sampled packet traffic analysis (2019)
  * [31] Kumar, A., Lim, T.J.: Early detection of mirai-like iot bots in large-scale networks through sub-sampled packet traffic analysis. In: Future of Information and Communication Conference. pp. 847–867. Springer (2019)
  * [32] Letteri, I., Del Rosso, M., Caianiello, P., Cassioli, D.: Performance of botnet detection by neural networks in software-defined networks. In: ITASEC (2018)
  * [33] Lin, J., Yu, W., Zhang, N., Yang, X., Zhang, H., Zhao, W.: A survey on internet of things: Architecture, enabling technologies, security and privacy, and applications. IEEE Internet of Things Journal 4(5), 1125–1142 (2017). https://doi.org/10.1109/JIOT.2017.2683200
  * [34] Liu, J., Liu, S., Zhang, S.: Detection of iot botnet based on deep learning. In: 2019 Chinese Control Conference (CCC). pp. 8381–8385. IEEE (2019)
  * [35] Margolis, J., Oh, T.T., Jadhav, S., Kim, Y.H., Kim, J.N.: An in-depth analysis of the mirai botnet. In: 2017 International Conference on Software Security and Assurance (ICSSA). pp. 6–12. IEEE (2017)
  * [36] McDermott, C.D., Majdani, F., Petrovski, A.V.: Botnet detection in the Internet of Things using deep learning approaches. In: 2018 international joint conference on neural networks (IJCNN). pp. 1–8. IEEE (2018)
  * [37] Mirsky, Y., Doitshman, T., Elovici, Y., Shabtai, A.: Kitsune: An ensemble of autoencoders for online network intrusion detection. In: The Network and Distributed System Security Symposium (NDSS) 2018 (2018)
  * [38] Nakip, M., Gelenbe, E.: MIRAI botnet attack detection with auto-associative dense random neural network. In: IEEE Global Communications Conference (Globecom). pp. 1–6 (2021)
  * [39] Nakip, M., Gelenbe, E.: Botnet attack detection with incremental online learning. In: International ISCIS Security Workshop. pp. 51–60. Springer (2022)
  * [40] Nguyen, T.D., Marchal, S., Miettinen, M., Fereidooni, H., Asokan, N., Sadeghi, A.R.: DÏot: A federated self-learning anomaly detection system for iot. In: 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS). pp. 756–767 (2019). https://doi.org/10.1109/ICDCS.2019.00080
  * [41] Parra, G.D.L.T., Rad, P., Choo, K.K.R., Beebe, N.: Detecting Internet of Things attacks using distributed deep learning. Journal of Network and Computer Applications 163, 102662 (2020)
  * [42] Prokofiev, A.O., Smirnova, Y.S., Surov, V.A.: A method to detect internet of things botnets. In: 2018 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus). pp. 105–108. IEEE (2018)
  * [43] Sinanović, H., Mrdovic, S.: Analysis of mirai malicious software. In: 2017 25th International Conference on Software, Telecommunications and Computer Networks (SoftCOM). pp. 1–5. IEEE (2017)
  * [44] Soe, Y.N., Feng, Y., Santosa, P.I., Hartanto, R., Sakurai, K.: Machine learning-based iot-botnet attack detection with sequential architecture. Sensors 20(16), 4372 (2020)
  * [45] Sriram, S., Vinayakumar, R., Alazab, M., Soman, K.: Network flow based iot botnet attack detection using deep learning. In: IEEE INFOCOM 2020-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). pp. 189–194. IEEE (2020)
  * [46] Taneja, M.: An analytics framework to detect compromised iot devices using mobility behavior. In: 2013 International Conference on ICT Convergence (ICTC). pp. 38–43 (2013). https://doi.org/10.1109/ICTC.2013.6675302
  * [47] Tuan, T.A., Long, H.V., Kumar, R., Priyadarshini, I., Son, N.T.K., et al.: Performance evaluation of botnet ddos attack detection using machine learning. Evolutionary Intelligence pp. 1–12 (2019)
  * [48] Tushir, B., Sehgal, H., Nair, R., Dezfouli, B., Liu, Y.: The impact of dos attacks onresource-constrained iot devices: A study on the mirai attack. arXiv preprint arXiv:2104.09041 (2021)
  * [49] Tzagkarakis, C., Petroulakis, N., Ioannidis, S.: Botnet attack detection at the iot edge based on sparse representation. In: 2019 Global IoT Summit (GIoTS). pp. 1–6. IEEE (2019)
  * [50] Yang, Y., Wu, L., Yin, G., Li, L., Zhao, H.: A survey on security and privacy issues in internet-of-things. IEEE Internet of Things Journal 4(5), 1250–1258 (2017). https://doi.org/10.1109/JIOT.2017.2694844


# Mixed Hegselmann-Krause Dynamics II

Hsin-Lun Li<EMAIL_ADDRESS>
###### Abstract.

The mixed Hegselmann-Krause (HK) model consists of a finite number of agents
characterized by their opinion, a vector in $\mathbf{R^{d}}$. For the
deterministic case, each agent updates its opinion by the rule: decide its
degree of stubbornness and mix its opinion with the average opinion of its
neighbors, the agents whose opinion differs by at most some confidence
threshold from its opinion at each time step. The mixed model is studied
deterministically in [1]. In this paper, we study it nondeterministically and
involve a social relationship among the agents which can vary over time. We
investigate circumstances under which asymptotic stability holds. Furthermore,
we indicate the mixed model covers not only the HK model but also the Deffuant
model.

###### Key words and phrases:

Mixed Hegselmann-Krause dynamics, mixed Deffuant dynamics, asymptotic
stability, consensus, social network

###### 1991 Mathematics Subject Classification:

05C40, 05C90, 37N99, 60G42, 91C20, 91D25, 91D30, 93D50, 94C15

Hsin-Lun Li

##  1\. Introduction

The mixed Hegselmann-Krause (HK) model originated from the HK model. The
original HK model comprises a finite set of agents characterized by their
opinion, a number in $[0,1]$. Agent $i$ updates its opinion $x_{i}$ by taking
the average opinion of its neighbors, the agents whose opinion differs by at
most some confidence threshold from $x_{i}$. There are two types of HK models:
the synchronous HK model and the asynchronous HK model. For the synchronous HK
model, all agents update their opinion at each step, whereas for the
asynchronous HK model, only one agent uniformly selected at random updates its
opinion at each time step. For the mixed model, all agents can decide their
degree of stubbornness and mix their opinion with the average opinion of their
neighbors. In [1], the mixed model is studied deterministically as follows.
Given a confidence threshold $\epsilon>0$ and a set $[n]=\\{1,2,\ldots,n\\}$
including all agents,

$x_{i}(t+1)=\alpha_{i}(t)x(t)+\frac{1-\alpha_{i}(t)}{|N_{i}(t)|}\sum_{k\in
N_{i}(t)}x_{k}(t)$

where

$\begin{array}[]{rcl}x_{i}(t)&\in&\mathbf{R^{d}}\ \hbox{is the opinion of
agent $i$ at time $t$},\vspace{2pt}\\\ \alpha_{i}(t)&\in&[0,1]\ \hbox{is the
degree of stubbornness of agent $i$ at time $t$}\ ,\vspace{2pt}\\\
N_{i}(t)&=&\\{j\in[n]:\|x_{i}(t)-x_{j}(t)\|\leq\epsilon\\}\ \hbox{is the
neighborhood of agent $i$ at time $t$.}\end{array}$

An agent is _absolutely stubborn_ if its degree of stubbornness equals 1. In
this paper, we study it nondeterministically and involve a social relationship
which can vary over time. Interpreting in graph, each vertex stands for an
agent. The edge connecting two vertices indicates a relationship between the
two, such as a friendship. We involve two types of graphs: the social graph
and the opinion graph. The social graph depicts the social relationship in
which two vertices are social neighbors if and only if they are socially
connected, whereas the opinion graph depicts the opinion relationship in which
two vertices are opinion neighbors if and only if they are at a distance of at
most $\epsilon$ apart. In words for the nondeterministic mixed model, an agent
updates its opinion by the mechanism: decide its degree of stubbornness and
mix its opinion with the average opinion of its social and opinion neighbors.
Before detail the mechanism of the nondeterministic mixed model and how it
also works for the Deffuant model, we introduce some terms and the Deffuant
model.

######  Definition 1.

A _social graph_ at time $t$, $G(t)=([n],E(t))$, is an undirected graph with
vertex set and edge set,

$[n]\ \hbox{and}\ E(t)=\\{(i,j)\in[n]^{2}:\hbox{vertices $i$ and $j$ are
socially connected}\\}.$

A _social graph for update_ at time $t$, $\tilde{G}(t)=([n],\tilde{E}(t))$, is
a subgraph of the social graph at time $t$ for the opinion update. An _opinion
graph_ at time $t$, $\mathscr{G}(t)=([n],\mathscr{E}(t))$, is an undirected
graph with vertex set and edge set,

$[n]\ \hbox{and}\ \mathscr{E}(t)=\\{(i,j)\in[n]^{2}:i\neq j\ \hbox{and}\
\|x_{i}(t)-x_{j}(t)\|\leq\epsilon\\}.$

A _profile_ at time $t$, $\tilde{G}(t)\cap\mathscr{G}(t)$, is the intersection
of the social graph for update and the opinion graph at time $t$.

######  Definition 2.

An opinion graph $\mathscr{G}$ is _$\delta$ -trivial_ if any two vertices in
$\mathscr{G}$ are at a distance of at most $\delta$ apart.

######  Definition 3.

A _matching_ $M$ in graph $G$ is a set of pairwise nonadjacent edges, none of
which are loops.

######  Definition 4.

A symmetric matrix $M$ is called a _generalized Laplacian_ of a graph
$G=(V,E)$ if for $x,y\in V$, the following two conditions hold:

$M_{xy}=0\ \hbox{for}\ x\neq y\ \hbox{and}\ (x,y)\notin E\quad\hbox{and}\quad
M_{xy}<0\ \hbox{for}\ x\neq y\ \hbox{and}\ (x,y)\in E.$

Let $d_{G}(x)$ = degree of $x$ in $G$, let $V(G)$ = vertex set of $G$, and let
$E(G)$ = edge set of $G$. Then, the _Laplacian_ of $G$ is defined as
$\mathscr{L}=D_{G}-A_{G}$ where

$D_{G}=\operatorname{diag}((d_{G}(x))_{x\in V(G)})\quad\hbox{and}\quad A_{G}=\
\hbox{the adjacency matrix}.$

In particular, $(A_{G})_{xy}=\mathbbm{1}\\{(x,y)\in E(G)\\}$ when the graph
$G$ is simple.

The original Deffuant model consists of a finite number of agents
characterized by their opinion, a number in $[0,1]$. Two socially connected
agents are uniformly selected at random and approach each other at a rate
$\mu\in[0,1/2]$ if and only if their opinion distance does not exceed some
confidence threshold, say $\epsilon>0$. The model is as follows:

$\begin{array}[]{rcl}x_{i}(t+1)&=&x_{i}(t)+\mu(x_{j}(t)-x_{i}(t))\mathbbm{1}\\{\|x_{i}(t)-x_{j}(t)\|\leq\epsilon\\},\vspace{2pt}\\\
x_{j}(t+1)&=&x_{j}(t)+\mu(x_{i}(t)-x_{j}(t))\mathbbm{1}\\{\|x_{i}(t)-x_{j}(t)\|\leq\epsilon\\}.\end{array}$

Now, we consider two interaction mechanisms: the pair interaction and the
group interaction. For the pair interaction, a selected pair of agents can
approach each other at distinct rates if and only if their opinion distance
does not exceed $\epsilon$, whereas for the group interaction, an agent can
decides its degree of stubbornness and mix its opinion with the average
opinion of its social and opinion neighbors. The difference between the
Deffuant model and the HK model is their interaction mechanism. The former is
pair interaction, whereas the latter is group interaction.

For nondeterministic mixed model, we assume that

  * •

$\alpha_{i}(t)$, $t\geq 0$ are independent and identically distributed random
variables on $[0,1]$ for all $i\in[n]$,

  * •

$U_{t}$, $t\geq 0$ are independent and identically distributed random
variables with a support $S$. For the pair interaction,
$U_{t}=\\{(i,j)\in[n]^{2}:\alpha_{i}(t)<1\ \hbox{or}\ \alpha_{j}(t)<1\\}$ and
$S\subset\\{\hbox{all matchings in}\ G(0)\\}$, whereas for the group
interaction, $U_{t}=\\{i\in[n]:\alpha_{i}(t)<1\\}$,
$S\subset\mathscr{P}([n])$, the power set of $[n]$, and $V(S)=\\{i:i\in a\
\hbox{for some}\ a\in S\\}\supset[n]$,

  * •

$\tilde{E}(t)=U_{t}\cap E(t)$ for the pair interaction, whereas
$\tilde{E}(t)=E(t)$ for the group interaction,

  * •

$(\Omega,\mathscr{F},P)$ is a probability space for
$\mathscr{F}\subset\mathscr{P}(\Omega)$ a $\sigma$-algebra and $P$ a
probability measure.

The update rule goes as follows:

$x(t+1)=\alpha_{i}(t)x_{i}(t)+\frac{1-\alpha_{i}(t)}{|\mathscr{N}_{i}(t)|}\sum_{k\in\mathscr{N}_{i}(t)}x_{k}(t)$

where
$\mathscr{N}_{i}(t)=\\{j\in[n]:(i,j)\in\tilde{E}(t)\cap\mathscr{E}(t)\\}$ is
the collection of social and opinion neighbors of agent $i$ for opinion
update. Express in matrix,

$x(t+1)=\operatorname{diag}(\alpha(t))\,x(t)+(I-\operatorname{diag}(\alpha(t)))\,A(t)\,x(t)$
(1)

where $A(t)\in\mathbf{R^{n\times n}}$ is row stochastic with

$A_{ij}=\mathbbm{1}\\{j\in\mathscr{N}_{i}(t)\\}/|\mathscr{N}_{i}(t)|$

and where

$\begin{array}[]{rclcl}x(t)&=&(x_{1}(t),x_{2}(t),\ldots,x_{n}(t))^{\prime}&=&\hbox{transpose
of}\ (x_{1}(t),x_{2}(t),\ldots,x_{n}(t)),\vspace*{4pt}\\\
\alpha(t)&=&(\alpha_{1}(t),\alpha_{2}(t),\ldots,\alpha_{n}(t))^{\prime}&=&\hbox{transpose
of}\ (\alpha_{1}(t),\alpha_{2}(t),\ldots,\alpha_{n}(t)).\end{array}$

In particular, (1) reduces to

  * •

the synchronous HK model if $G(t)$ is complete, $S=\\{[n]\\}$ and
$\alpha_{i}(t)=0$ for all $i\in[n]$ and $t\geq 0$,

  * •

the asynchronous HK model if $G(t)$ is complete,
$S=\big{\\{}\\{i\\}\big{\\}}_{i\in[n]}$, $U_{t}$ is a uniform random variable
on $S$, denoted by $U_{t}=\operatorname{uniform}{(S)}$, and $\alpha_{i}(t)=0$
if $i\in U_{t}$ at all times, and

  * •

the Deffuant model if $E(t)=E$, $S=\big{\\{}\\{(i,j)\\}\big{\\}}_{(i,j)\in
E}$, $U_{t}=\operatorname{uniform}{(S)}$ and
$\alpha_{i}(t)=\alpha_{j}(t)=1-2\mu$ for all $(i,j)\in U_{t}$ and $t\geq 0$.

##  2\. Main results

The power of the mixed model is that it can address at least two interaction
mechanisms: pair interaction and group interaction. For the Deffuant model,
the convergence parameter $\mu$ is constant, namely that the two selected
socially connected agents can only approach each other at the same rate.
However, for the pair interaction in the mixed model, all agents can decide
their convergence parameter at all times. We involve the term “matching” in
graph theory to express not only a pair of agents can update their opinion.
Apart from the deterministic case in [1] that all agents are considered, only
those agents who are not absolutely stubborn are considered in the
nondeterministic case, which stands to reason since the update occurs only on
the non-absolutely stubborn.

######  Theorem 5.

Assume that $0\leq\limsup_{t\to\infty}\sup\\{\alpha_{i}(t):i\in[n]\
\hbox{and}\ \alpha_{i}(t)<1\\}<1$ almost surely. Then, all components of a
profile are $\delta$-trivial in finite time almost surely for all $\delta>0$,
i.e.,

$\tau_{\delta}:=\inf\\{t\geq 0:\hbox{all components of
$\tilde{G}(t)\cap\mathscr{G}(t)$ are $\delta$-trivial}\\}<\infty\ \hbox{almost
surely}.$

Corollary 6 depicts circumstances under which asymptotic stability holds. It
turns out that agents in the same component for infinitely many times achieve
their consensus.

######  Corollary 6.

Assume that $0\leq\sup_{t\in\mathbf{N}}\sup\\{\alpha_{i}(t):i\in[n]\
\hbox{and}\ \alpha_{i}(t)<1\\}<1$ almost surely. Then, all components of a
profile are $\delta$-trivial after some finite time, i.e., asymptotic
stability holds in (1).

Next, we show circumstances under which a consensus can be achieved. The
author in [1] has indicated that an opinion graph preserves
$\delta$-triviality for all $\delta>0$, therefore when $\mathscr{G}(t)$ is
$\epsilon$-trivial and the social graph for update is connected for infinitely
many times, the profile is connected for infinitely many times. Hence, a
consensus can be achieved given that asymptotic stability holds in this case,
which elaborates Corollary 7.

######  Corollary 7.

Assume that $0\leq\sup_{t\in\mathbf{N}}\sup\\{\alpha_{i}(t):i\in[n]\
\hbox{and}\ \alpha_{i}(t)<1\\}<1$, the social graph for update is connected
for infinitely many times and $\mathscr{G}(t)$ is $\epsilon$-trivial almost
surely. Then,

$\lim_{t\in\infty}\max_{i,j\in[n]}\|x_{i}(t)-x_{j}(t)\|=0$

##  3\. The mixed model

The proof of Theorem 5 goes through several steps. The general ideas are to
find a monotone bounded function and construct an inequality involving the
current opinion and the updated opinion. We introduce several lemmas before
the proof.

######  Lemma 8 ([1]).

Let $Z(t)=\sum_{i,j\in[n]}\|x_{i}(t)-x_{j}(t)\|^{2}\wedge\epsilon^{2}.$ Then,
$Z$ is nonincreasing with respect to $t$. In particular,

$\begin{array}[]{rcl}\displaystyle Z(t)-Z(t+1)&\geq&\displaystyle
4\sum_{i\in[n]}\bigg{(}1+|\mathscr{N}_{i}(t)|\frac{\alpha_{i}(t)}{1-\alpha_{i}(t)}\mathbbm{1}\\{\alpha_{i}(t)<1\\}\bigg{)}\|x_{i}(t)-x_{i}(t+1)\|^{2}.\end{array}$

######  Lemma 9 (Perron-Frobenius for Laplacians [3]).

Assume that $M$ is a generalized Laplacian of a connected graph. Then, the
smallest eigenvalue of $M$ is simple and the corresponding eigenvector can be
chosen with all entries positive.

######  Lemma 10 (Courant-Fischer Formula [4]).

Assume that $Q$ is a symmetric matrix with eigenvalues
$\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{n}$ and corresponding
eigenvectors $v_{1},v_{2},\ldots,v_{n}$. Let $S_{k}$ be the vector space
generated by $v_{1},v_{2},\ldots,v_{k}$ and $S_{0}=\\{0\\}$. Then,

$\lambda_{k}=\min\\{x^{\prime}Qx:\|x\|=1,x\in S_{k-1}^{\perp}\\}.$

######  Lemma 11 (Cheeger’s Inequality [2]).

Assume that $G=(V,E)$ is an undirected graph with the Laplacian $\mathscr{L}$.
Define

$i(G)=\min\bigg{\\{}\frac{|\partial S|}{|S|}:S\subset
V,0<|S|\leq\frac{|G|}{2}\bigg{\\}}$

where $\partial S=\\{(u,v)\in E:u\in S,v\in S^{c}\\}$. Then,

$2i(G)\geq\lambda_{2}(\mathscr{L})\geq\frac{i^{2}(G)}{2\Delta(G)}\quad\hbox{where}\quad\Delta(G)=\
\hbox{maximum degree of\leavevmode\nobreak\ $G$}.$

######  Lemma 12 ([1]).

Assume that $Q$ is a real square matrix and that $V$ is invertible such that
the matrix $VQ=\mathscr{L}$ is the Laplacian of some connected graph. Then, 0
is a simple eigenvalue of $Q^{\prime}Q$ corresponding to the eigenvector
$\mathbbm{1}=(1,1,\ldots,1)^{\prime}$. In particular, we have

$\lambda_{2}(Q^{\prime}Q)=\min\\{x^{\prime}Q^{\prime}Qx:\|x\|=1\ \hbox{and}\
x\perp\mathbbm{1}\\}.$

######  Lemma 13.

If some component $G$ in $\tilde{G}(t)\cap\mathscr{G}(t)$ is
$\delta$-nontrivial and $\alpha_{i}(t)<1$ for all $i\in V(G)$, then

$\sum_{i\in V(G)}\,\|x_{i}(t)-x_{i}(t+1)\|^{2}>\frac{2\delta^{2}(1-\max_{i\in
V(G)}\alpha_{i}(t))^{2}}{|V(G)|^{8}}.$

###### Proof.

Without loss of generality, we may assume that
$\tilde{G}(t)\cap\mathscr{G}(t)$ is connected. For
$\mathbbm{1}\in\mathbf{R^{n}}$ and $W=\operatorname{Span}(\\{\mathbbm{1}\\})$,
$\mathbf{R^{n}}=W\oplus W^{\perp}$. Then, write

$x(t)=\left[c_{1}\mathbbm{1}\,|\,c_{2}\mathbbm{1}\,|\,\cdots\,|\,c_{d}\mathbbm{1}\right]+\left[\hat{c}_{1}u^{(1)}\,|\,\hat{c}_{2}u^{(2)}\,|\,\cdots\,|\,\hat{c}_{d}u^{(d)}\right]$

where $c_{i}$ and $\hat{c}_{i}$ are constants and
$u^{(i)}\in\mathbbm{1}^{\perp}$ is a unit vector for all $i\in[d]$.

$\hbox{Claim:}\quad\sum_{k=1}^{d}\,\hat{c}_{k}^{2}>\frac{\delta^{2}}{2}.$

Assume by contradiction that this is not the case. Then, for all $i,j\in[n]$,

$\begin{array}[]{l}\displaystyle\|x_{i}(t)-x_{j}(t)\|^{2}=\displaystyle\sum_{k=1}^{d}\,\hat{c}_{k}^{2}(u^{(k)}_{i}-u^{(k)}_{j})^{2}\vspace*{-4pt}\\\
\hskip 40.0pt\leq\displaystyle\sum_{k=1}^{d}\,\hat{c}_{k}^{2}\
2((u^{(k)}_{i})^{2}+(u^{(k)}_{j})^{2})\leq
2\,\sum_{k=1}^{d}\,\hat{c}_{k}^{2}\leq\delta^{2},\end{array}$

contradicting the $\delta$-nontriviality of $\tilde{G}(t)\cap\mathscr{G}(t)$.
Let
$B(t)=\operatorname{diag}(\alpha(t))+(I-\operatorname{diag}(\alpha(t)))A(t)$.
Then,

$x(t)-x(t+1)=(I-B(t))\,x(t)=\left[\hat{c}_{1}(I-B(t))u^{(1)}\,|\,\cdots\,|\,\hat{c}_{d}(I-B(t))u^{(d)}\right],$

from which it follows that

$\sum_{i=1}^{n}\,\|x_{i}(t)-x_{i}(t+1)\|^{2}=\sum_{j=1}^{d}\,\hat{c}_{j}^{2}\|(I-B(t))u^{(j)}\|^{2}.$

Now, observe that

$I-B(t)=(I-\operatorname{diag}(\alpha(t)))(I+D(t))^{-1}\mathscr{L}$

where $\mathscr{L}$ is the Laplacian of $\tilde{G}(t)\cap\mathscr{G}(t)$ and
$D(t)$ is diagonal with $D_{ii}(t)=d_{i}(t)$, the degree of vertex $i$. Assume
that $\alpha_{i}(t)<1$ for all $i\in[n]$. Then,
$I-\operatorname{diag}(\alpha(t))$ is invertible, and according to Lemmas 11
and 12,

$\begin{array}[]{l}\displaystyle\|(I-B(t))u^{(j)}\|^{2}=\displaystyle
u^{(j)^{\prime}}(I-B(t))^{\prime}(I-B(t))u^{(j)}\geq\displaystyle\lambda_{2}((I-B(t))^{\prime}(I-B(t)))\vspace*{8pt}\\\
\hskip
25.0pt=\displaystyle\lambda_{2}\bigg{(}\mathscr{L}\,\operatorname{diag}\bigg{(}\bigg{(}\bigg{(}\frac{1-\alpha_{i}(t)}{1+d_{i}(t)}\bigg{)}^{2}\bigg{)}_{i=1}^{n}\bigg{)}\mathscr{L}\bigg{)}\vspace*{8pt}\\\
\hskip
25.0pt\geq\displaystyle\bigg{(}\frac{1-\max_{i\in[n]}\alpha_{i}(t)}{n}\bigg{)}^{2}\lambda_{2}(\mathscr{L}^{2})=\displaystyle\bigg{(}\frac{1-\max_{i\in[n]}\alpha_{i}(t)}{n}\bigg{)}^{2}\lambda_{2}^{2}(\mathscr{L})\vspace*{8pt}\\\
\hskip
25.0pt>\displaystyle\frac{4(1-\max_{i\in[n]}\alpha_{i}(t))^{2}}{n^{8}}\end{array}$

where we used that

$\lambda_{2}(\mathscr{L})\geq\frac{i^{2}(\mathscr{G}(t))}{2\Delta(\mathscr{G}(t))}>\frac{(2/n)^{2}}{2n}=\frac{2}{n^{3}}.$

In particular, we obtain

$\sum_{i=1}^{n}\,\|x_{i}(t)-x_{i}(t+1)\|^{2}>\frac{2\delta^{2}(1-\max_{i\in[n]}\alpha_{i}(t))^{2}}{n^{8}}.$

∎

###### Proof of Theorem 5.

By the assumption, there is $(t_{k})_{k\geq 0}\subset\mathbf{N}$ strictly
increasing such that $\max\\{\alpha_{i}(t_{k}):i\in[n]\ \hbox{and}\
\alpha_{i}(t_{k})<1\\}\leq\gamma<1$ for some random variable $\gamma$ and for
all $k\geq 0$. For all $m\geq 1$,

$n^{2}\epsilon^{2}>Z(0)\geq Z(0)-Z(m)=\sum_{t=0}^{m-1}[Z(t)-Z(t+1)].$

Letting $m\to\infty$ and applying Lemma 8,

$n^{2}\epsilon^{2}\geq\sum_{t\geq 0}[Z(t)-Z(t+1)]\geq 4\sum_{t\geq
0}\sum_{i\in[n],\alpha_{i}(t)<1}\|x_{i}(t)-x_{i}(t+1)\|^{2}.$ (2)

Set $\tau=\tau_{\delta}$. Assume by contradiction that $\tau=\infty$ on some
$E\in\mathscr{F}$ with $P(E)>0$. Now, we separate to two parts: pair
interaction and group interaction.

(i) For group interaction, taking expectation on both sides on $E$, denoted by
$\mathbf{E}_{E}$,

$\displaystyle n^{2}\epsilon^{2}\ $ $\displaystyle\geq\ 4\sum_{t\geq
0}\mathbf{E}_{E}\bigg{(}\sum_{i\in[n],\alpha_{i}(t)<1}\|x_{i}(t)-x_{i}(t+1)\|^{2}\bigg{)}$
$\displaystyle=\ 4\sum_{t\geq 0}\sum_{a\in
S}\mathbf{E}_{E}\bigg{(}\sum_{i\in[n],\alpha_{i}(t)<1}\|x_{i}(t)-x_{i}(t+1)\|^{2}\bigg{|}U_{t}=a\bigg{)}P(U_{t}=a)$
$\displaystyle\geq\ 4\min_{a\in S}P(U_{0}=a)\sum_{t\geq 0}\sum_{a\in
S}\mathbf{E}_{E}\bigg{(}\sum_{i\in[n],\alpha_{i}(t)<1}\|x_{i}(t)-x_{i}(t+1)\|^{2}\bigg{|}U_{t}=a\bigg{)}$
$\displaystyle\geq\ 4\min_{a\in S}P(U_{0}=a)\sum_{t\geq
0}\mathbf{E}_{E}\bigg{(}\sum_{i\in[n]}\|x_{i}(t)-x_{i}(t+1)\|^{2}\bigg{)}$ (3)
$\displaystyle>\ 4\min_{a\in S}P(U_{0}=a)\sum_{t\geq
0}\mathbf{E}_{E}\bigg{(}\frac{2\delta^{2}(1-\max_{i\in[n]}\alpha_{i}(t))^{2}}{n^{8}}\bigg{)}$
(4) $\displaystyle\geq\ 4\min_{a\in S}P(U_{0}=a)\sum_{k\geq
0}\mathbf{E}_{E}\bigg{(}\frac{2\delta^{2}(1-\max_{i\in[n]}\alpha_{i}(t_{k}))^{2}}{n^{8}}\bigg{)}$
$\displaystyle\geq\ 4\min_{a\in S}P(U_{0}=a)\sum_{k\geq
0}\mathbf{E}_{E}\bigg{(}\frac{2\delta^{2}(1-\gamma)^{2}}{n^{8}}\bigg{)}=\infty,\
\hbox{a contradiction,}$

where $\min_{a\in S}P(U_{0}=a)>0$ is due to finite support $S$, (3) follows
$V(S)\supset[n]$, $\alpha_{i}(t)<1$ for all $i\in[n]$ and $t\geq 0$ during
(3), and (4) follows Lemma 13.

(ii) For pair interaction, since $\tau=\infty$ on $E$, there are
$(i,j)\in\tilde{E}(t)\cap\mathscr{E}(t)$, $\alpha_{i}(t)<1$ and
$\|x_{i}(t)-x_{j}(t)\|>\delta$ for all $t\geq 0$, therefore from (2),

$n^{2}\epsilon^{2}>4\sum_{k\geq 0}(1-\gamma)\delta/2=\infty,\ \hbox{a
contradiction.}$

Therefore, time $\tau$ is almost surely finite. ∎

###### Proof of Corollary 6.

Assume by contradiction that a profile is $\delta$-nontrivial for infinitely
many times on $E\in\mathscr{F}$ with $P(E)>0$. Then, there is a
$\delta$-nontrivial component $G$ in $\tilde{G}(t_{k})\cap\mathscr{G}(t_{k})$
for $(t_{k})_{\geq 0}\subset\mathbf{N}$ increasing. Let
$\gamma=\sup_{t\in\mathbf{N}}\sup\\{\alpha_{i}(t):i\in[n]\ \hbox{and}\
\alpha_{i}(t)<1\\}$

(i) For group interaction, following (3) in the proof of Theorem 5,

$\displaystyle\eqref{deter}$ $\displaystyle>\ 4\min_{a\in
S}P(U_{0}=a)\sum_{k\geq 0}\mathbf{E}_{E}\bigg{(}\frac{2\delta^{2}(1-\max_{i\in
V(G)}\alpha_{i}(t))^{2}}{|V(G)|^{8}}\bigg{)}$ $\displaystyle\geq\ 4\min_{a\in
S}P(U_{0}=a)\sum_{k\geq
0}\mathbf{E}_{E}\bigg{(}\frac{2\delta^{2}(1-\max_{i\in[n]}\alpha_{i}(t_{k}))^{2}}{n^{8}}\bigg{)}$
$\displaystyle\geq\ 4\min_{a\in S}P(U_{0}=a)\sum_{k\geq
0}\mathbf{E}_{E}\bigg{(}\frac{2\delta^{2}(1-\gamma)^{2}}{n^{8}}\bigg{)}=\infty,\
\hbox{a contradiction,}$

(ii) For pair interaction, $G$ is a complete graph of order 2, say
$V(G)=\\{i,j\\}$, therefore $\|x_{i}(t_{k})-x_{j}(t_{k})\|>\delta$ and
$\alpha_{\ell}(t_{k})\leq\gamma$ for all $k\geq 0$ and for some $\ell\in
V(G)$. Via (2) in the proof of theorem 5,

$n^{2}\epsilon^{2}>4\sum_{k\geq 0}(1-\gamma)\delta/2=\infty,\ \hbox{a
contradiction.}$

Therefore, all components of a profile are $\delta$-trivial after some finite
time. ∎

## References

  * [1] H Li,  Mixed Hegselmann-Krause Dynamics,  _Discrete and Continuous Dynamical Systems-B_ , (2021), https://arxiv.org/abs/2010.03050
  * [2] L. W. Beineke, P. J. Cameron and R. J. Wilson,  _Topics in Algebraic Graph Theory_ ,  Cambridge University Press, Cambridge, UK, 2004.
  * [3] (MR2340484) [10.1007/978-3-540-73510-6]  T. Biyikoglu, J. Leydold and P. F. Stadler,  _Laplacian Eigenvectors of Graphs: Perron-Frobenius and Faber-Krahn Type Theorems,_ Springer-Verlag, Berlin Heidelberg, 2007.
  * [4] (MR2978290)  R. A. Horn and C. R. Johnson,  _Matrix Analysis,_ Cambridge University Press, Cambridge, 2013.


# Legislator Representation Learning with Social Context and Expert Knowledge

Shangbin Feng1 Zhaoxuan Tan1 Zilong Chen1 Peisheng Yu1
Qinghua Zheng1 Xiaojun Chang2 Minnan Luo1 1Xi’an Jiaotong University, Xi’an,
Shaanxi, China
2RMIT University, Melbourne, Victoria, Australia {wind_binteng, tanzhaoxuan,
luoyangczl<EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Modeling the ideological perspectives of political actors is an essential task
in computational political science with applications in many downstream tasks.
Existing approaches are generally limited to textual data and voting records,
while they neglect the rich social context and valuable expert knowledge for
holistic evaluation. In this paper, we propose a representation learning
framework of political actors that jointly leverages social context and expert
knowledge. Specifically, we retrieve and extract factual statements about
legislators to leverage social context information. We then construct a
heterogeneous information network to incorporate social context and use
relational graph neural networks to learn legislator representations. Finally,
we train our model with three objectives to align representation learning with
expert knowledge, model ideological stance consistency, and simulate the echo
chamber phenomenon. Extensive experiments demonstrate that our learned
representations successfully advance the state-of-the-art in three downstream
tasks. Further analysis proves the correlation between learned legislator
representations and various socio-political factors, as well as bearing out
the necessity of social context and expert knowledge in modeling political
actors.

##  1 Introduction

Modeling the perspectives of political actors has applications in various
downstream tasks such as roll call vote prediction (Mou et al., 2021) and
political perspective detection (Feng et al., 2021). Existing approaches
generally focus on voting records or textual information of political actors
to induce their stances. Ideal point model (Clinton et al., 2004) is one of
the most widely used approach for vote-based analysis, while later works
enhance the ideal point model (Kraft et al., 2016; Gu et al., 2014; Gerrish
and Blei, 2011) and yield promising results on the task of roll call vote
prediction. For text-based methods, text analysis techniques are combined with
textual information in social media posts (Li and Goldwasser, 2019), Wikipedia
pages (Feng et al., 2021), legislative text (Mou et al., 2021) and news
articles (Li and Goldwasser, 2021) to enrich the perspective analysis process.

However, existing methods fail to incorporate the rich social context and
valuable expert knowledge. As illustrated in Figure 1, social context
information such as home state and party affiliation serves as background
knowledge and helps connect different political actors (Yang et al., 2021).
These social context facts about political actors also differentiate them and
indicate their ideological stances. In addition, expert knowledge from
political think tanks provides valuable insights and helps to anchor the
perspective analysis process. As a result, political actor representation
learning should be guided by domain expertise to facilitate downstream tasks
in computational political science. That being said, social context and expert
knowledge should be incorporated in modeling legislators to ensure a holistic
evaluation process.

Figure 1: Social context information and expert knowledge from political think
tanks to facilitate modeling different political actors. Figure 2: Overview of
our proposed framework for political actor representation learning.

In light of these challenges, we propose a legislator representation learning
framework that jointly leverages social context and expert knowledge. We
firstly collect a dataset of political actors by retrieving and extracting
social context information from their Wikipedia homepages and adapting expert
knowledge from two political think tanks AFL-CIO111https://aflcio.org/ and
Heritage Action222https://heritageaction.com/. After that, we construct a
heterogeneous information network to model social context information and
adopt relational graph neural networks for representation learning. Finally,
we train the framework with three training objectives to leverage expert
knowledge, model social and political phenomena, and learn representations of
political actors in the process. We apply our learned representations to three
downstream tasks, namely political perspective detection, roll call vote
prediction and entity stance prediction, to examine the effectiveness of our
proposed approach. Our main contributions are summarized as follows:

  * •

To the best of our knowledge, this is the first work to jointly leverage
social context and expert knowledge to learn representations of political
actors.

  * •

We propose a heterogeneous graph-based approach to learn legislator
representations with three training objectives, which aligns social context
with expert knowledge, ensures stance consistency, and models the echo chamber
phenomenon in socio-economic systems.

  * •

Extensive experiments demonstrate that our proposed approach outperforms the
state-of-the-art in three related downstream tasks. Further studies suggest
our learned legislator representations reflect various socio-political factors
and prove the necessity of social context and expert knowledge in our proposed
approach.

##  2 Related Work

The ideological perspectives of political actors play an essential role in
their individual behaviour and adds up to influence the overall legislative
process. Political scientists first explored to quantitatively model political
actors based on their voting behaviour. Ideal point model (Clinton et al.,
2004) is one of the earliest approach to leverage voting records to analyze
their perspectives. It projects political actors and legislation onto one-
dimensional spaces and measure distances. Many works later extended the ideal
point model. Gerrish and Blei (2011) leverages bill content to infer
legislator perspectives. Gu et al. (2014) introduces topic factorization to
model voting behaviour on different issues to establish a fine-grained
approach. Kraft et al. (2016) models legislators with multidimensional ideal
vectors to analyze voting records.

In addition to voting, various forms of textual data such as speeches and
public statements are also leveraged to model the perspectives of political
actors. Li and Goldwasser (2019) proposes to analyze social media posts to
better understand the stances of political content. Feng et al. (2021)
introduces textual information on Wikipedia and constructs a knowledge graph
to facilitate perspective detection. Mou et al. (2021) proposes to leverage
tweets, hashtags and legislative text to grasp the full picture of the
political discourse. Li and Goldwasser (2021) focuses on analyzing the
political perspectives of news articles and their mentioned political
entities. In this paper, we explore to leverage social context and expert
knowledge for legislator representation learning.

##  3 Methodology

Figure 2 presents an overview of our political actor representation learning
framework. We firstly collect data of political actors from Wikipedia and
political think tanks. We then construct a heterogeneous information network
to jointly model political actors, their social context and expert knowledge.
After that, we learn graph representations with gated relational graph
convolutional networks (gated R-GCN) and train the proposed framework with
three different objectives.

###  3.1 Data Collection

We collect a datset about political actors in the United States that were
active in the past decade while our proposed approach is applicable for all
nations and time ranges. For social context information, we retrieve the list
of senators and congresspersons from the 114th congress to the 117th
congress.333https://www.congress.gov/ We then retrieve their Wikipedia
pages444https://github.com/goldsmith/Wikipedia and extract these named
entities: presidents, senators, congresspersons, governors, states, political
parties, supreme court justices, government institutions, and office terms
(117th congress etc.). In this way, we obtain 1,069 social and political
entities. Based these entities, we identify five types of relations: party
affiliation, home state, political office, term in office, and appoint
relationships. In this way, we obtain 9,248 heterogeneous edges. For expert
knowledge, we make use of the legislator scoreboards at AFL-CIO and Heritage
Action, two political think tanks that lie in opposite ends of the ideological
spectrum. Specifically, we retrieve the scoreboard content and extract each
legislator’s score in each office term. In this way, we obtain 777 scores from
AFL-CIO and 679 scores from Heritage Action. We consolidate the collected
social context and expert knowledge to serve as the data set in our
experiments, which is available as supplementary material.

###  3.2 Graph Construction

To better model the interactions between political entities and their shared
social context, we propose to construct a heterogeneous information network
(HIN) from the dataset. For initial node features, we use pre-trained RoBERTa
(Liu et al., 2019) to encode the first paragraph of Wikipedia homepage.

####  3.2.1 Heterogeneous Nodes

Based on the collected dataset, we select diversified entities that are
essential factors in modeling the political process. Specifically, we use
eight types of nodes to represent political actors and diversified social
context entities.

N1: Office Terms We use four nodes to represent the 114th, 115th, 116th, 117th
congress spanning from 2015 to 2021. We use these nodes to model the change in
politics through time and could be similarly extended to other time periods.

N2: Legislators We retrieve senators and congresspersons from the 114th to the
117th congress and use one node to represent each distinct legislator.

N3: Presidents The presidency is the highest elected office in the United
States. We use three nodes to represent President Biden, Trump and Obama to
match with legislators.

N4: Governors State and local politics are also essential in analyzing the
political process. We use one node to represent each distinct governor of 50
states.

N5: States The home state of political actors is often an important indicator
and helps connect different individuals. We use one node to represent each
state in the United States.

N6: Government Institutions We use four nodes to represent the white house,
senate, house of representatives and supreme court. These nodes enable our
constructed HIN to separate different political actors based on the office
they hold.

N7: Supreme Court Justices Supreme court justices are nominated by presidents
and approved by senators, which helps connect different types of political
actors. We use one node to represent each supreme court justice.

N8: Political Parties We use two nodes to represent the two major political
parties in the United States: the Republican Party and the Democratic Party.

####  3.2.2 Heterogeneous Relations

Based on $N1$ to $N8$, we extract five types of informative interactions
between entities to complete the HIN structure. Specifically, we use five
types of heterogeneous relations to connect different nodes and construct our
political actor HIN.

R1: Party Affiliation We connect political actors and their affiliated
political party with $R1$:

$R1=(N2\cup N3\cup N4)\times N8$ (1)

R2: Home State We connect political actors with their home states with $R2$:

$R2=(N2\cup N3\cup N4\cup N7)\times N4$ (2)

R3: Hold Office We connect political actors with the political office they
hold with $R3$:

$R3=(N2\cup N3\cup N4\cup N7)\times N6$ (3)

R4: Time in Office If a political actor holds office during one of the time
stamps in $N1$, we connect them with $R4$:

$R4=(N2\cup N3\cup N4\cup N7)\times N1$ (4)

R5: Appoint Besides from being elected, certain political actors are appointed
by others. We denote this relation with $R5$:

$R5=(N3\times N7)\cup(N4\times N2)$ (5)

###  3.3 Representation Learning

Since nodes represent political actors, we learn node-level representations
with gated R-GCN to jointly leverage social context and external expert
knowledge. Let $E=\\{e_{1},\cdot\cdot\cdot,e_{n}\\}$ be $n$ entities and
$v_{i}$ be the initial features of entity $e_{i}$. Let $R$ be the
heterogeneous relation set and $N_{r}(e_{i})$ be entity $e_{i}$’s neighborhood
under relation type $r$. We firstly transform $v$ to serve as the input of
graph neural networks,

$x_{i}^{(0)}=\phi(W_{I}\cdot v_{i}+b_{I})$ (6)

where $\phi$ is leaky-relu, $W_{I}$ and $b_{I}$ are learnable parameters. We
then propagate entity messages and aggregate them with gated R-GCN. For the
$l$-th layer,

$u_{i}^{(l)}=\sum_{r\in R}\frac{1}{|N_{r}(e_{i})|}\sum_{j\in
N_{r}(e_{i})}f_{r}(x_{j}^{(l-1)})+f_{s}(x_{i}^{(l-1)})$ (7)

where $f_{s}$ and $f_{r}$ are parameterized linear layers for self loops and
edges of relation $r$, $u_{i}^{(l)}$ is the hidden representation for entity
$e_{i}$ at layer $l$. We then calculate gate levels,

$g_{i}^{(l)}=\sigma(W_{G}\cdot[u_{i}^{(l)},x_{i}^{(l-1)}]+b_{G})$ (8)

where $W_{G}$ and $b_{G}$ are learnable parameters, $\sigma(\cdot)$ denotes
the sigmoid function and $[\cdot,\cdot]$ denotes the concatenation operation.
We then apply the gate mechanism to $u_{i}^{(l)}$ and $x_{i}^{(l-1)}$,

$x_{i}^{(l)}=tanh(u_{i}^{(l)})\odot
g_{i}^{(l)}+x_{i}^{(l-1)}\odot(1-g_{i}^{(l)})$ (9)

where $\odot$ is the Hadamard product operation. After $L$ layer(s) of gated
R-GCN, we obtain node representations
$\\{x^{(L)}_{1},\cdot\cdot\cdot,x^{(L)}_{n}\\}$ and the nodes representing
political actors are extracted as learned representations.

###  3.4 Model Training

We propose to train our framework with a combination of supervised, self-
supervised and unsupervised tasks, which aligns social context with expert
knowledge, ensures stance consistency and simulates the echo chamber
phenomenon. The overall loss function of our model is as follows:

$L=\lambda_{1}L_{1}+\lambda_{2}L_{2}+\lambda_{3}L_{3}+\lambda_{4}\sum_{w\in\theta}w^{2}$
(10)

where $\lambda_{i}$ is the weight of loss $L_{i}$ and $\theta$ are all
learnable parameters in the model. We then present the motivation and details
of each loss function $L_{1}$, $L_{2}$ and $L_{3}$.

Method | SemEval | AllSides
---|---|---
Acc | MaF | Acc | MaF
BERT | $84.03$ | $81.55$ | $81.55$ | $80.13$
MAN_Glove | $81.58$ | $79.29$ | $78.29$ | $76.96$
MAN_ELMO | $84.66$ | $83.09$ | $81.41$ | $80.44$
MAN_Ensemble | $86.21$ | $84.33$ | $85.00$ | $84.25$
Feng et al. (2021) | $89.56$ | $84.94$ | $86.02$ | $85.52$
Ours | 91.30 | 87.78 | 86.81 | 86.33
Table 1: Adapting our learned representations for political perspective
detection. Acc and MaF denote accuracy and macro F1-score.

####  3.4.1 Objective 1: Expert Knowledge

The expert knowledge task aims to align the learned representations with
external expert knowledge from political think tanks. We use the learned
representations of political actors to predict their liberal and conservative
stances, which are adapted from AFL-CIO and Heritage Action. Specifically,

$\displaystyle l_{i}=softmax(W_{L}\cdot x_{i}^{(L)}+b_{L})$ (11)
$\displaystyle c_{i}=softmax(W_{C}\cdot x_{i}^{(L)}+b_{C})$

where $l_{i}$ and $c_{i}$ are predicted stances towards liberal and
conservative values, $W_{L}$, $b_{L}$, $W_{C}$ and $b_{C}$ are learnable
parameters. Let $E_{L}$ and $E_{C}$ denote the training set of AFL-CIO and
Heritage Action scores, $\hat{l_{i}}$ and $\hat{c_{i}}$ denote the ground-
truth labels. We calculate the expert knowledge loss,

$L_{1}=-\sum_{e_{i}\in
E_{L}}\sum_{d=1}^{D}\hat{l_{id}}log(l_{id})-\sum_{e_{i}\in
E_{C}}\sum_{d=1}^{D}\hat{c_{id}}log(c_{id})$ (12)

$L1$ enables the framework to align learned representations with external
expert knowledge from political think tanks.

####  3.4.2 Objective 2: Stance Consistency

The stance consistency task is motivated by the fact that liberalism and
conservatism are opposite ideologies, thus individuals often take inversely
correlated stances towards them. We firstly speculate entities’ stance towards
the opposite ideology by taking the opposite of the predicted stance,

$\tilde{l_{i}}=\psi(D-argmax(c_{i})),\ \ \tilde{c_{i}}=\psi(D-argmax(l_{i}))$
(13)

where $\psi$ is the one-hot encoder, $argmax(\cdot)$ calculates the vector
index with the largest value, $D$ is the number of stance labels,
$\tilde{l_{i}}$ and $\tilde{c_{i}}$ are labels derived with stance
consistency. We calculate the loss function $L_{2}$ measuring stance
consistency,

$L_{2}=-\sum_{e_{i}\in E}\ \sum_{d=1}^{D}\ (\tilde{l_{id}}\ log(l_{id})\ +\
\tilde{c_{id}}\ log(c_{id}))$ (14)

As a result, the loss function $L_{2}$ enables our approach to ensure stance
consistency among political actors.

####  3.4.3 Objective 3: Echo Chamber

The echo chamber task is motivated by the echo chamber phenomenon, where
social entities tend to reinforce their narratives by forming small and
closely connected interaction circles. We simulate echo chambers by assuming
that neighboring nodes in the HIN have similar representations while non-
neighboring nodes have different representations. We firstly define the
positive and negative neighborhood of entity $e_{i}$,

$\displaystyle P_{e_{i}}=\\{e\ \ |\ \exists\ r\in R\ \ s.t.\ \ e\in
N_{r}(e_{i})\\}$ (15) $\displaystyle N_{e_{i}}=\\{e\ \ |\ \forall\ r\in R\ \
s.t.\ \ e\notin N_{r}(e_{i})\\}$

We then calculate the echo chamber loss,

$\displaystyle L_{3}=-\sum_{e_{i}\in E}\sum_{e_{j}\in
P_{e_{i}}}log(\sigma(x_{i}^{{(L)^{T}}}x_{j}^{(L)}))$ (16)
$\displaystyle+Q\cdot\sum_{e_{i}\in E}\sum_{e_{j}\in
N_{e_{i}}}log(\sigma(-x_{i}^{{(L)^{T}}}x_{j}^{(L)}))$

where $Q$ denotes the weight for negative samples. $L_{3}$ enables our
framework to model the echo chamber phenomenon that is common in real-world
socio-economic systems.

Figure 3: Adapting our learned representations of political actors for the
downstream task of roll call vote prediction.

##  4 Experiments

###  4.1 Experiment Settings

We train our representation learning framework with the proposed loss function
$L$ in Equ (10) and evaluate the learned representations of political actors
on three downstream tasks: political perspective detection, roll call vote
prediction, and entity stance prediction. We submit our data, implemented
codes, hyperparameter settings and other experiment details as supplementary
material to facilitate reproduction.

Figure 4: Using t-sne to visualize learned representations of political
actors. DBI denotes the Davies-Bouldin Index.

####  4.1.1 Political Perspective Detection

Political perspective detection aims to detect stances in text such as public
statements and news articles, which generally mention many political actors to
provide context and present arguments. Feng et al. (2021) proposes to leverage
TransE (Bordes et al., 2013) to learn representations of political actors and
augment the argument mining process. To examine the quality of our
representation learning, we replace TransE in Feng et al. (2021) with our
learned representations and conduct political perspective detection. We adopt
the same datasets (Kiesel et al., 2019; Li and Goldwasser, 2019) and settings
so that the results are directly comparable.

####  4.1.2 Roll Call Vote Prediction

Roll call vote prediction aims to predict the voting behavior of legislators
given different pieces of legislation, which is essential in the political
process and involves analyzing political actors. To examine our
representations’ effectiveness in vote prediction, we concatenate our learned
representations with RoBERTa (Liu et al., 2019) encoding of legislation texts
and conduct vote prediction with two fully connected layers. We adopt the same
dataset and experiment settings as Mou et al. (2021) so that the results are
directly comparable.

####  4.1.3 Expert Knowledge Prediction

To the best of our knowledge, this is the first work to leverage expert
knowledge from political think tanks in modeling political perspectives. To
examine whether our learned representations correlate well with expert
knowledge, we compare with various text (Pedregosa et al., 2011; Horne et al.,
2018; Pennington et al., 2014; Liu et al., 2019; Beltagy et al., 2020) and
graph (Kipf and Welling, 2016; Veličković et al., 2017; Hamilton et al., 2017;
Shi et al., 2020; Bresson and Laurent, 2017) analysis baselines on the expert
knowledge task.

Method | Text | Graph | Acc | MaF | MiF
---|---|---|---|---|---
Linear BoW | ✓ |  | $68.49$ | $40.00$ | $68.53$
Bias Features | ✓ |  | $47.26$ | $20.08$ | $47.10$
Glove | ✓ |  | $52.05$ | $26.94$ | $52.01$
RoBERTa | ✓ |  | $71.92$ | $49.70$ | $71.87$
LongFormer | ✓ |  | $68.49$ | $42.27$ | $68.56$
GCN | ✓ | ✓ | $74.66$ | $54.16$ | $74.46$
GAT | ✓ | ✓ | $78.08$ | $55.82$ | $78.17$
GraphSAGE | ✓ | ✓ | $75.34$ | $51.39$ | $75.43$
TransformerConv | ✓ | ✓ | $77.40$ | $55.63$ | $77.48$
ResGatedConv | ✓ | ✓ | $76.03$ | $54.31$ | $75.97$
Ours | ✓ | ✓ | 80.82 | 60.37 | 80.89

Table 2: Our model’s performance on the expert knowledge prediction task
compared to various text and graph analysis baselines. Acc, MaF and MiF denote
accuracy, macro and micro averaged F1-score.

###  4.2 Results

####  4.2.1 Political Perspective Detection

Table 1 presents model performance on two political perspective detection
datasets. We run our approach five times and report the average performance.
It is demonstrated that our approach consistently outperforms all state-of-
the-art approaches on both benchmarks, which indicates that our learned
representations of political actors could serve as external knowledge in the
task of political perspective detection to help augment the argument mining
process.

####  4.2.2 Roll Call Vote Prediction

Figure 3 presents model performance on roll call vote prediction. We run ours
five times and report the average results. It is demonstrated that our
approach outperforms existing baselines, which suggests that our
representation learning could serve as high-quality features to analyze voting
behaviour.

####  4.2.3 Expert Knowledge Prediction

Table 2 presents model performance on the expert knowledge task. We run Ours
five times and report the average performance. It is demonstrated that our
framework consistently achieves the best performance compared to various graph
and analysis baselines, suggesting our learned representations successfully
reflect expert knowledge from political think tanks. Apart from that, graph-
based models generally outperform text-based methods, which suggests that the
constructed HIN is essential to model performance.

###  4.3 Representation Learning Study

Section 4.2 demonstrates that our framework successfully learns political
actor representations that improve performance in three downstream tasks.
Besides, high-quality representations of political actors should differentiate
them with regard to their social and political information. To examine whether
we have achieved this end, we adopt t-sne (Maaten and Hinton, 2008) to
illustrate our learned representations of political actors in Figure 4.

####  4.3.1 Social Context

Figure 4 (a) and (b) illustrate the correlation between learned
representations and social context. The DBI scores (Davies and Bouldin, 1979)
quantitatively indicate great collocation among different social context
groups.

####  4.3.2 Congressional Caucuses

Figure 4 (c) and (d) demonstrate the correlation between learned
representations and major congressional caucuses in both parties. Both the
illustration and the DBI scores suggest little collocation among caucuses,
which could be attributed to the fact that inter-party differences outweigh
intra-party differences in contemporary U.S. politics.

Figure 5: Ablation study of social context information. Definition of five
types of relations $R1$ to $R5$ follows that in Section 3.2.2.

####  4.3.3 Voting Records

Figure 4 (e), (f), (g) and (h) illustrate how legislators vote with or against
the sitting president. We retrieve this information from
FiveThirtyEight555https://fivethirtyeight.com/ and illustrate voting records
with color gradients. As a result, our learned representations of legislators
in the 115th and 116th congress correlate well with their voting records,
while the 117th congress might have not hold enough votes for an accurate
categorization.

###  4.4 Ablation Study

Our framework aims to learn representations of political actors with the help
of social context and expert knowledge as well as three training objectives.
We conduct ablation study to examine their effect in the representation
learning process and report performance on the expert knowledge prediction.

####  4.4.1 Social Context

We use five types of heterogeneous relations $R1$ to $R5$ to connect different
entities based on their social context. We gradually remove five types of
social context edges in the constructed HIN and report model performance in
Figure 5. It is illustrated that all relations but $R4$ (Time in Office)
significantly contributes to the overall performance. Besides, Figure 5
illustrates a great gap between $90\%$ and $100\%$ edges, suggesting the
importance of a complete HIN structure.

####  4.4.2 Expert Knowledge

We learn legislator representations with the help of two political think
tanks: AFL-CIO and Heritage Action. We retrieve their evaluation of political
actors amd construct a supervised task to train our framework. To examine the
effect of these expert knowledge in our proposed approach, we gradually remove
expert knowledge labels in $L_{1}$ and report model performance in Figure 6.
It is illustrated that our performance drops with partial expert knowledge
from either AFL-CIO or Heritage Action. As a result, expert knowledge is
essential in our model’s representation learning process.

####  4.4.3 Training Objectives

We propose to train our framework with three objectives. To examine their
effect, we train our method with different combinations of $L_{1}$, $L_{2}$
and $L_{3}$ and report performance in Table 3. Our model performs best with
all three training objectives, proving the effectiveness of our loss function
design.

Figure 6: Ablation study of expert knowledge. We report accuracy on the training objective 1 for different expert knowledge settings. Loss Function(s) | Acc | MaF | MiF
---|---|---|---
$L_{1}$ only | $78.08$ | $56.43$ | $78.17$
$L_{1}$ and $L_{2}$ | $79.45$ | $55.97$ | $79.52$
$L_{1}$ and $L_{3}$ | $76.03$ | $51.91$ | $76.11$
$L_{1}$, $L_{2}$, and $L_{3}$ | 80.82 | 60.37 | 80.89
Table 3: Ablation study of three training objectives.

##  5 Conclusion

In this paper, we present a framework to learn representations of political
actors with social context and expert knowledge. We retrieve context
information from Wikipedia and expert knowledge from political think tanks,
construct a HIN to model political actors and learn representations with gated
R-GCNs and multiple training objectives. Extensive experiments demonstrate
that our approach advances the state-of-the-art on three downstream tasks.
Further experiments also prove the quality of learned representations and the
necessity of social context and expert knowledge in our approach.

## References

  * Beltagy et al. [2020] Iz Beltagy, Matthew E Peters, and Arman Cohan.  Longformer: The long-document transformer.  arXiv preprint arXiv:2004.05150, 2020.
  * Bordes et al. [2013] Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko.  Translating embeddings for modeling multi-relational data.  Advances in neural information processing systems, 26, 2013.
  * Bresson and Laurent [2017] Xavier Bresson and Thomas Laurent.  Residual gated graph convnets.  arXiv preprint arXiv:1711.07553, 2017.
  * Clinton et al. [2004] Joshua Clinton, Simon Jackman, and Douglas Rivers.  The statistical analysis of roll call data.  American Political Science Review, 98(2):355–370, 2004.
  * Davies and Bouldin [1979] David L Davies and Donald W Bouldin.  A cluster separation measure.  IEEE transactions on pattern analysis and machine intelligence, (2):224–227, 1979.
  * Falcon [2019] et al. Falcon, WA.  Pytorch lightning.  GitHub. Note: https://github.com/PyTorchLightning/pytorch-lightning, 3, 2019.
  * Feng et al. [2021] Shangbin Feng, Minnan Luo, Zilong Chen, Qingyao Li, Xiaojun Chang, and Qinghua Zheng.  Knowledge graph augmented political perspective detection in news media.  arXiv preprint arXiv:2108.03861, 2021.
  * Fey and Lenssen [2019] Matthias Fey and Jan Eric Lenssen.  Fast graph representation learning with pytorch geometric.  arXiv preprint arXiv:1903.02428, 2019.
  * Gerrish and Blei [2011] Sean M Gerrish and David M Blei.  Predicting legislative roll calls from text.  In Proceedings of the 28th International Conference on Machine Learning, ICML 2011, 2011.
  * Gu et al. [2014] Yupeng Gu, Yizhou Sun, Ning Jiang, Bingyu Wang, and Ting Chen.  Topic-factorized ideal point estimation model for legislative voting network.  In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 183–192, 2014.
  * Hamilton et al. [2017] William L Hamilton, Rex Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 1025–1035, 2017.
  * Horne et al. [2018] Benjamin D Horne, Sara Khedr, and Sibel Adali.  Sampling the news producers: A large news and feature data set for the study of the complex media landscape.  In Twelfth International AAAI Conference on Web and Social Media, 2018.
  * Kiesel et al. [2019] Johannes Kiesel, Maria Mestre, Rishabh Shukla, Emmanuel Vincent, Payam Adineh, David Corney, Benno Stein, and Martin Potthast.  Semeval-2019 task 4: Hyperpartisan news detection.  In Proceedings of the 13th International Workshop on Semantic Evaluation, pages 829–839, 2019.
  * Kipf and Welling [2016] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  arXiv preprint arXiv:1609.02907, 2016.
  * Kraft et al. [2016] Peter Kraft, Hirsh Jain, and Alexander M Rush.  An embedding model for predicting roll-call votes.  In Proceedings of the 2016 conference on empirical methods in natural language processing, pages 2066–2070, 2016.
  * Li and Goldwasser [2019] Chang Li and Dan Goldwasser.  Encoding social information with graph convolutional networks forpolitical perspective detection in news media.  In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2594–2604, 2019.
  * Li and Goldwasser [2021] Chang Li and Dan Goldwasser.  Using social and linguistic information to adapt pretrained representations for political perspective identification.  In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pages 4569–4579, 2021.
  * Liu et al. [2019] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov.  Roberta: A robustly optimized bert pretraining approach.  arXiv preprint arXiv:1907.11692, 2019.
  * Maaten and Hinton [2008] Laurens van der Maaten and Geoffrey Hinton.  Visualizing Data using t-SNE.  Journal of Machine Learning Research, 9(86):2579–2605, 2008.
  * Mou et al. [2021] Xinyi Mou, Zhongyu Wei, Lei Chen, Shangyi Ning, Yancheng He, Changjian Jiang, and Xuan-Jing Huang.  Align voting behavior with public statements for legislator representation learning.  In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 1236–1246, 2021.
  * Paszke et al. [2019] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  Advances in neural information processing systems, 32:8026–8037, 2019.
  * Pedregosa et al. [2011] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al.  Scikit-learn: Machine learning in python.  the Journal of machine Learning research, 12:2825–2830, 2011.
  * Pennington et al. [2014] Jeffrey Pennington, Richard Socher, and Christopher D Manning.  Glove: Global vectors for word representation.  In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 1532–1543, 2014.
  * Shi et al. [2020] Yunsheng Shi, Zhengjie Huang, Wenjin Wang, Hui Zhong, Shikun Feng, and Yu Sun.  Masked label prediction: Unified message passing model for semi-supervised classification.  arXiv preprint arXiv:2009.03509, 2020.
  * Veličković et al. [2017] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  arXiv preprint arXiv:1710.10903, 2017.
  * Wolf et al. [2020] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush.  Transformers: State-of-the-art natural language processing.  In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 38–45, Online, October 2020. Association for Computational Linguistics.
  * Yang et al. [2021] Yuqiao Yang, Xiaoqiang Lin, Geng Lin, Zengfeng Huang, Changjian Jiang, and Zhongyu Wei.  Joint representation learning of legislator and legislation for roll call prediction.  In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pages 1424–1430, 2021.

##  Appendix A Supplementary Studies

To better understand the effectiveness of our propose framework, we present
additional studies that do not fit in the main paper. We report model
performance on the expert knowledge prediction task in supplementary studies.

###  A.1 Graph Learning Study

We construct a HIN to model social context and adopt gated R-GCNs for
representation learning, thus we further study the effect of these graph-
related elements.

####  A.1.1 GNN Operator

We adopt five heterogeneous relations $R1$ to $R5$ to connect eight types of
entities $N1$ to $N8$, thus our constructed graph is heterogeneous. To examine
whether the graph heterogeneity contributes to model performance, we
substitute gated R-GCNs with homogeneous GNNs such as GCN, GAT and GraphSAGE.
Table 4 shows that our model performs best with gated R-GCNs, proving the
necessity of heterogeneous relations to represent diversified social context.

####  A.1.2 GNN Layers

Two or three GNN layers are typically adopted for node-level representation
learning in similar tasks. To examine the effect of GNN layers in our proposed
approach, we learn node representations with one to five layers of gated
R-GCNs. Table 5 illustrates that two layers of gated R-GCNs perform best, thus
we adhere to this setting in other experiments.

Figure 7: Model performance with different loss weights. GNN operator | Het. | Acc | MaF | MiF
---|---|---|---|---
GCN | ✗ | $76.03$ | $58.31$ | $78.08$
GAT | ✗ | $77.40$ | $59.01$ | $78.85$
SAGE | ✗ | $78.77$ | $58.04$ | $78.81$
R-GCN | ✓ | $78.08$ | $55.61$ | $78.15$
Gated R-GCN | ✓ | 80.82 | 60.37 | 80.89
Table 4: Model performance with different GNN operators. Our approach adopts gated R-GCN and achieves the best performance. Het. denotes whether the method supports heterogeneous graphs. L | 0 | 1 | 2 | 3 | 4
---|---|---|---|---|---
Acc | 69.18 | 74.66 | 80.82 | 78.08 | 78.08
MaF | 42.00 | 52.87 | 60.37 | 57.66 | 62.33
MiF | 69.26 | 74.74 | 80.89 | 76.80 | 78.08
Table 5: Model performance with one to five gated R-GCN layers. Figure 8:
Model performance with different number of negative samples and weight $Q$.

###  A.2 Training Objective Study

We propose to train the representation learning framework with three
objectives: expert knowledge, stance consistency, and the echo chamber
phenomenon. We further study the effect of these training objectives in model
performance.

####  A.2.1 Loss Weight

We fix $\lambda_{1}=1$ and $\lambda_{4}=10^{-5}$, present model performance
under different settings of loss weights for auxiliary tasks $\lambda_{2}$ and
$\lambda_{3}$ in Figure 7. It is illustrated that $0.2\leq\lambda_{2}\leq 0.3$
and $0.01\leq\lambda_{3}\leq 0.1$ would generally lead to an effective balance
of differently supervised loss functions.

####  A.2.2 Negative Sample

For the echo chamber objective, we randomly select nodes from $N_{e_{i}}$ to
serve as negative samples and balance $L_{3}$ with $Q$. We study the effect of
negative sample amount and their weight $Q$ in the model’s performance and
present them in Figure 8. It is illustrated that 2 negative samples and
$Q=0.1$ or $0.2$ performs best, which indicates that the echo chamber
objective contributes to overall performance, while too many negative samples
and large $Q$s might overshadow the overall representation learning process.

##  Appendix B Experiment Details

In this section, we provide additional details to facilitate reproducing our
results and findings. We submit data and code as supplementary material and
commit to make them publicly available upon acceptance.

###  B.1 Hyperparameters

We present the hyperparameter settings of our proposed approach in Table 6. We
follow these settings throughout the paper unless stated otherwise.

###  B.2 Implementation

We use pytorch [Paszke et al., 2019], pytorch lightning [Falcon, 2019], torch
geometric [Fey and Lenssen, 2019] and the transformers library [Wolf et al.,
2020] for an efficient implementation of our proposed framework. All
implemented codes are available as supplementary material.

###  B.3 Experiment Details

####  B.3.1 Political Perspective Detection

We replace TransE in Feng et al. [2021] with our learned representations of
political actors. We use the GRGCN setting in Feng et al. [2021] as backbone.
We maintain the same evaluation settings to ensure a fair comparison and
highlight the effectiveness of our learned representations.

####  B.3.2 Roll Call Vote Prediction

We make our best effort to maintain the same experiment settings as Mou et al.
[2021] while their might be minor differences. For random, we conduct roll
call vote prediction for legislators in the 114th and 115th congress and
average the results. We follow the same 6:2:2 split for each setting. For
time-based, we use the 114th congress as training and validation set and the
115th congress as test set.

####  B.3.3 Expert Knowledge Prediction

We collect expert knowledge about legislators from two political think tanks,
which assigns a continuous score $s$ from 0 to 1 to indicate how liberal or
conservative a legislator is. We construct a classification task from expert
knowledge by creating five discrete labels: strongly favor ($0.9\leq s\leq
1$), favor ($0.75\leq s\leq 0.9$), neutral ($0.25\leq s\leq 0.75$), oppose
($0.1\leq s\leq 0.25$), and strongly oppose ($0\leq s\leq 0.1$). In this way,
we adapt from expert knowledge to derive liberal and conservative labels for
legislators. We use 7:2:1 to partition them into training, validation and test
sets. We calculate evaluation metrics on the liberal and conservative set
separately, and present the harmonic mean of two sets. In this way, the
presented results accurately and comprehensively reflect how our proposed
approach and existing baselines perform on both political think tanks. For
text-based baselines, we encode Wikipedia summaries of entities with these
methods and predict their stances with two fully connected layers. For graph-
based baselines, we train them with the constructed HIN and the expert
knowledge training objective.

Hyperparameter | Value | Hyperparameter | Value
---|---|---|---
RoBERTa size | $768$ | GNN size | $512$
optimizer | Adam | learning rate | $1e-3$
batch size | $64$ | max epochs | $100$
$L$ | $2$ | $\phi$ | ReLU
$Q$ | $-0.1$ | #negative sample | $2$
$\lambda_{1}$ | $0.01$ | $\lambda_{2}$ | $0.2$
$\lambda_{3}$ | $1$ | $\lambda_{4}$ | $1e-5$
Table 6: Hyperparameters of our proposed approach.