Anomaly detection is a prominent research direction in machine learning and complex network analysis. In this paper, we target a special type of complex networks, i. e., bipartite multi-layer networks. Here, we exploit the properties of such a complex network, i. e., the partitioning of the set of nodes into two groups, and its multi-layer characteristics. Our proposed approach includes many-objective optimization, correlation analysis and clustering - based on Eigenvector centrality - incorporated into a novel framework for identifying candidates for anomalous nodes from multiple perspectives, in a human-centered interpretable way. We exemplify the application of the proposed approach in a case study using a real-world dataset on socio-spatial interaction data.
these are based on the notion of centrality, specifically Eigenvector centrality for anomaly detection, forming a combined interpretable approach including many-objective optimization, as well as correlation and cluster analysis. These methods are combined into a methodological framework, for providing the diferent perspectives and to enable assessment by also analyzing potential commonalities and diferences pointed to by the incorporated methods, respectively.
We build on our previous works [
In short, our presented approach starts by making projections of the bipartite network. Then, from those projections and each layer, we estimate the centrality of all its contained nodes. Next, we apply many objective optimization to identify the Pareto Front, as a basis for finding a set of anomalous nodes with minimal centrality. In addition, we apply correlation analysis on the centrality properties, and can further categorize nodes using clustering into positively correlated, negatively correlated (i. e., very diferent) or non-correlated nodes, as complementing perspectives in assessing anomalous nodes in an interpretable way.
In more detail, our proposed approach consists of the following steps: 1. Given the network represented as a bipartite multi-layer graph, we perform manyobjective optimization based on minimizing eigenvector centrality on bipartite projections of the multi-layer network. With the minimization, we aim at obtaining the set of the least important nodes according to eigenvector centrality, as candidates for anomalous nodes. This provides us with our first perspective for identifying anomalies, given by the Pareto-Front of the least important nodes according to their (minimized) eigenvector centrality. 2. Using the vector of centrality values for a node in each layer, we perform correlation analysis with respect to all other nodes, resulting in a correlation matrix and according heatmap perspective, respectively, to visually inspect anomalies. 3. Finally, we can apply clustering on the correlation matrix for obtaining clusters of nodes, as another perspective for detecting (sets of) anomalous nodes.
Overall, this enables the identification of anomaly candidates from multiple perspectives; this then facilitates a human-centered process for analysis and assessment with a human-in-the-loop. In particular, by making use of interpretable representations and visualizations, e. g., given by subnetwork visualizations of anomaly candidates, heatmap visualizations of clusters at the level of node vectors as well as comprehensive cluster diagrams. Then, this thus further provides for a transparent process and comprehensible approach.
It is important to note, that our approach tackles the novel problem of anomaly detection
on bipartite multi-layer networks. There exist methods for anomaly detection in bipartite
networks [
Our contributions are summarized as follows: 1. We present a novel framework incorporating many-objective optimization and centralitybased analysis for identifying a set of anomalous nodes on bipartite multi-layers networks, using complementing distinctive perspectives. 2. We exemplify our proposed approach using a case study. Our context is given by a real-world dataset of socio-spatial interactions [6]. Applying our approach on the dataset, we illustrate the key steps providing simple to interpret perspectives on the respective network structures; altogether, this demonstrates the efectiveness of our approach in this real-world dataset.
The rest of the paper is organized as follows: Section 2 discusses related work. After that, Section 3 describes our approach in detail. Next, Section 4 presents and discusses our results. Finally, Section 5 concludes with a summary and outlines several interesting directions for future research.
In the following, we briefly introduce basic notation and background on the foundational concepts of bipartite and multi-layer networks, represented as graphs. After that, we summarize related work on anomaly detection, also considering methods for bipartite and multi-layer networks.
Formally, a bipartite Graph is given by a triple = (, , ) with , being sets of vertices, where ∩ = ∅. Furthermore, for the set of edges it holds that for every edge ∈ : = (, ) with ∈ , ∈ or vice versa ∈ , ∈ .
For multi-layer (or multiplex) networks, we distinguish a set of layers – modeling sets of edges corresponding to relations, denoted by ⊆ , ∈ {1...}, where indicates the number of layers. A multiplex network can then be represented formally as follows: = (1, 2, . . . , , . . . , ), where = (, ), ⊆ . Figure 1 shows an illustration of a multi-layer network. Here, each network is represented by the adjacency matrix with the elements , for which > 0, if there is a positive weight of the link between the pair of nodes and , , ∈ in layer , and = 0 otherwise. To simplify the formalization of weighted multiplex networks, we will consider only taking a positive integer value or zero with respect to the link between any pair of such nodes and in layer .
Detecting anomalies in (complex) networks data is a prominent research direction, with many
practical applications. A classical definition of an anomaly [ 7] states it as “an outlier is an
observation that difers so much from other observations as to arouse suspicion that it was
generated by a diferent mechanism” [ 7]. Furthermore, for anomalies in complex networks,
the general graph anomaly detection problem can be defined as follows: “Given a [. . . ] graph
database, find the graph objects [. . . ] that are rare and that difer significantly from the majority
of the reference objects in the graph” [8]. However, as we have already discussed in [
Beyond simple graphs and multi-layer networks, we extend our view on more complex
structures, i. e., towards (multi-layer) bipartite graph representations, as discussed below in
more detail. In particular, our proposed approach builds on our
multi-objective-optimizationbased method for anomaly detection in multi-layer networks [
We have proposed a method in [
Altogether, in contrast to those approaches discussed above, we provide an unsupervised exploratory anomaly detection approach, embedded into a human-centered process, focusing on interpretable representations and visualizations. Furthermore, we focus on the novel special case of bipartite multi-layer networks, and present a novel combined approach tackling this. In a case study using a real-world dataset, we also discuss respective implications.
Below, we first provide a bird’s eye view on our proposed approach, before we discuss two of its core components, i. e., network centrality, and the applied method for many-objective optimization. Due to the limited space, we summarize correlation and -means clustering below and refer to e. g., [14, 15] for details.
Below, we outline the individual steps of proposed approach: 1. We start with the bipartite multi-layer network; here, each layer is a bipartite network.
We preprocess the network, constructing according bipartite projections for the individual
layers of the given multi-layer network. That is, for = (, , ) an edge is created
concerning a pair of nodes in ( , respectively), whenever their intersection of
connected nodes in ( , respectively), is not empty, for which we then assign || as the
new weight of that edge.
2. Given the preprocessed network, we perform many-objective optimization using
minimization on the eigenvector centrality values applying the method presented in [
Starting Point:
Bipartite Network / Layers (I)
(II) Methological Process - Overview (III)
Preprocessed Multi-Layer Bipartite Projections
Constructing Multi-Layer Bipartite Projected Networks
Many-Objective Optimization è Pareto Front
Multi-Perspective Analysis (1) Pareto Front View (2) Correlation View (3) Clustering View
Semi-Automatic & Human-in-the-loop
Assessment
With this approach, we can identify anomaly candidates from those given multiple
perspectives. First, the obtained Pareto-Front can be applied in order to find a group of nodes as
candidates for anomalies – i. e., having the least importance with respect to their centrality,
as we have discussed in [
In network science, there are special methods for finding the most influential nodes [ 17] in the
network using the notion of the so-called network centrality, which considers, for example,
degree or the connection (structure) to other nodes. In particular, there is Eigenvector centrality,
which considers the number of links from other nodes, their importance, and to how many
these other nodes the respective nodes themselves point to, e. g., [18, 19]. For our proposed
approach, we apply eigenvector centrality, since this precisely corresponds to our intuition for
estimating the notion of connections to important nodes and/or parts of the network, which is
relevant for anomaly detection, as discussed in [
In particular, in our proposed approach, we integrate a method which we presented in [
Below, we present the results of a case study exemplifying the presented approach in the context of a real-world socio-spatial dataset capturing human interactions [6]. Before that, we briefly summarize the applied dataset and its characteristics.
For demonstrating our approach, we provide a case study using a real-world dataset of bipartite network data. For details on the dataset, we refer to [6]. Essentially, the dataset is given by a set of bipartite networks which form a multiplex network, capturing interactions as well as preferences and perception of students attending a student career day; here, face-to-face proximity contacts between participants and companies were estimated between stationary sensors (denoting companies) and a wearable sensors worn by the participants with diferent signal strength thresholds, resulting in three diferent interaction networks. Furthermore, participants indicated preferences with respect to companies, as well as their perception which company they had really visited.
In total, for 59 participants as well as for 26 companies information is modeled. Specifically, the applied dataset [6] contains the following networks, as described in [6] in detail: 1. Socio-spatial interaction networks, taking the proximity contacts and a threshold on the received signal strength indicator (RSSI), selecting the contacts (as edges) that are stronger than the applied threshold. As individual thresholds, values of RSSI={-90, -93, -95} dBm, relating to stronger to weaker contacts were applied, resulting in the according networks. For a more detailed discussion we refer to [6]. 2. A preference network [6]: An edge is created between participant and company whenever selected as a preference. 3. A perception network [6]: Here, an edge is created between participant and company whenever perceived having visited .
In the following, we apply our approach and its proposed methods for identifying a set of anomalous nodes on the applied bipartite multi-layer network. Since the bipartite network consists of nodes in the participant as well as the company group, we first apply respective bipartite projections of the respective bipartite networks to those groups, respectively their nodes. The applied bipartite network data consists of five single networks, i. e., on the applied 90, 93, and 95 RSSI thresholds, as well as the perception and preference networks (corresponding to the layers 1, . . . 5 in the tables below). After performing the projections, we merge the single networks into a multi-layer network. With this, we thus overall obtain two multi-layer networks, focusing on the student or the company view. With this, each multi layer network consists of the described 5 layers. In a next step, we estimate the centrality for all nodes in all layers and applying many-objective optimization through minimization. Via many-objective optimization (as our first perspective), for the student multi-layer network (59 nodes), we found 18 nodes contained in the Pareto Front as shown in Table 1; from the multi-layer company network (26 nodes), we found 6 nodes contained in the Pareto Front, as shown in Table 2. (nodes are marked in green color). F1 is a node centrality in layer1, F2 is a node centrality in layer2,
Using the set of nodes in the Pareto Front as a candidate basis of anomalous nodes, we can apply correlation analysis as a complementing perspective (visualized as a heatmap) in order to understand the correlation and the proximity of each node compared to all other nodes in the Pareto Front better in the context of node centrality. For this, we compute the Pearson correlation values as described above. In Figure 3 we show the resulting heatmaps. The cluster perspectives are shown in Figure 4 given the respective Pareto fronts and visualization the according dimensions as discussed above.
As shown in Figure 3, for the correlation analysis in the student multi-layer network, we observe that the node of student 1 (NS1) is highly correlated regarding centrality (i. e., with very similar role of centrality) compared to the nodes NS58, NS6 and NS59 that are depicted in dark blue color; on the contrary, node NS1 is conflicting (i. e., with a diferent role of centrality) compared to nodes NS19, NS27, NS25, and NS57. Also, it is visible that NS1 has a considerable “conflict” with node NS14 (depicted in darker red color). Likewise, for the correlation analysis in the company multi-layer network, we can identify some distinctive results, regarding the set of nodes in the Pareto Front. In Figure 3, for example, we observe that the node of company 1 (NC1) is highly correlated with nodes NC14, NC22, NC24 and NC26; however, here we also observe that node NC1 is conflicting with NC17. For grouping the nodes according to their correlation, we utilize -means clustering for further assessing interesting nodes (in the Pareto Front and/or as indicated by correlation analysis). Then, from the formed clusters, we continue by calculating the average of the centrality for each cluster and compare these centrality averages to all other clusters in order to estimate the lowest average centrality. This lowest average centrality of a cluster can then be applied in categorizing clusters of anomalous nodes in the network.
In our case, considering the nodes in the respective Pareto Fronts, for the student multi-layer network we obtained 18 nodes, consisting of 3 clusters, for which 1 = {NS1 , NS6 , NS7 , NS9 , NS11 , NS16 , NS18 NS58 }, 2 = {NS14 , NS19 , NS25 , NS26 } and 3 = {NS8 , NS22 , NS27 , NS33 , NS58 , NS59 }. From those clusters, we observe that cluster 3 has the lowest average centrality, and therefore the nodes NS8 , NS22 , NS27 , NS33 , NS58 , NS59 can be categorized as anomalous node candidates for the student network. Likewise, from the company multi-layer network, we obtain 3 clusters, 1 = {NC17 }, 2 = NC14 }, and 3 = {NC1 , NC22 , NC24 , NC26 }, where the lowest average centrality is found at cluster 1.
In this paper, we proposed an approach for anomaly detection on bipartite multi-layer networks. We exemplified the approach in the context of socio-spatial interactions using a real-world dataset of human interactions. Specifically, our proposed approach integrates many-objective optimization, correlation analysis, as well as clustering for obtaining diferent yet complementing perspectives for anomaly detection in a human-centered way. This is facilitated, in particular, by the transparent and interpretable representations and visualizations, as we have also exemplified in our case study. For future work, we intend to extend the analysis by incorporating further methods and metrics investigating further real-world phenomena about potential anomalies [20], e. g., also including profiling [ 21] as well as exceptional subgraph mining techniques [22]. In addition, we aim to extend the analysis by incorporating attributed network information into the detection algorithms, e. g., [23, 24]. [5] H. Li, C. Zhao, Y. Liu, X. Zhang, Anomaly detection by discovering bipartite structure on complex networks, Computer Networks 190 (2021) 107899. [6] M. Atzmueller, C. Güven, S. Masiala, R. Mackenbach, P. Shayan, W. Liebregts, Behavioral Analysis on Socio-Spatial Interaction Networks concerning User Preferences, Interactions and their Perception, in: Proc. ABIS 2019/ACM Hypertext 2019, ACM, 2019. [7] D. Hawkins, Identification of Outliers, Monographs on Statistics and Applied Probability,
Springer Netherlands, 1980. [8] L. Akoglu, H. Tong, D. Koutra, Graph Based Anomaly Detection and Description, Data
Min Knowl Disc 29 (2015) 626–688. [9] A. Maulana, M. T. Emmerich, Towards many-objective optimization of eigenvector centrality in multiplex networks, in: Proc. International Conference on Control, Decision and Information Technologies, IEEE, 2017, pp. 0729–0734. [10] J. Sun, H. Qu, D. Chakrabarti, C. Faloutsos, Relevance search and anomaly detection in bipartite graphs, ACM SIGKDD Explorations Newsletter 7 (2005) 48–55. [11] R. Mittal, M. Bhatia, Anomaly detection in multiplex networks, Procedia Computer Science 125 (2018) 609–616. [12] P. Bindu, P. S. Thilagam, D. Ahuja, Discovering suspicious behavior in multilayer social networks, Computers in Human Behavior 73 (2017). [13] M. Bansal, D. Sharma, Ranking and discovering anomalous neighborhoods in attributed multiplex networks, in: Proc. ACM IKDD CoDS and 25th COMAD, ACM, 2020, pp. 46–54. [14] J. MacQueen, Some Methods for Classification and Analysis of Multivariate Observations,
Fifth Berkeley Symposium on Mathematical Statistics and Probability 1 (1967) 281–297. [15] L. Sachs, Angewandte Statistik: Anwendung Statistischer Methoden, Springer, 2013. [16] B. Shneiderman, The Eyes Have It: A Task by Data Type Taxonomy for Information Visualizations, in: Proc. IEEE Symposium on Visual Languages, Boulder, Colorado, 1996, pp. 336–343. [17] P. Bonacich, P. Lloyd, Eigenvector-like measures of centrality for asymmetric relations,
Social networks 23 (2001) 191–201. [18] M. Barthelemy, Betweenness centrality in large complex networks, The European physical journal B 38 (2004) 163–168. [19] L. Page, S. Brin, R. Motwani, T. Winograd, The PageRank citation ranking: Bringing order to the web., Technical Report, Stanford InfoLab, 1999. [20] M. Atzmueller, Onto Model-based Anomalous Link Pattern Mining on Feature-Rich Social
Interaction Networks, in: Proc. WWW (Companion), IW3C2 / ACM, 2019. [21] M. Atzmueller, F. Lemmerich, B. Krause, A. Hotho, Who are the Spammers? Understandable Local Patterns for Concept Description, in: Proc. 7th Conference on Computer Methods and Systems, Oprogramowanie Nauko-Techniczne, Krakow, Poland, 2009. [22] M. Atzmueller, H. Soldano, G. Santini, D. Bouthinon, MinerLSD: Eficient Mining of Local
Patterns on Attributed Networks, Applied Network Science 4 (2019). [23] R. Interdonato, M. Atzmueller, S. Gaito, R. Kanawati, C. Largeron, A. Sala, Feature-Rich Networks: Going Beyond Complex Network Topologies, Applied Network Science 4 (2019). [24] M. Atzmueller, S. Günnemann, A. Zimmermann, Mining communities and their descriptions on attributed graphs: a survey, DMKD 35 (2021).