Big Data Research 29 (2022) 100332 Contents lists available at ScienceDirect Big Data Research www.elsevier.com/locate/bdr A Flexible Outlier Detector Based on a Topology Given by Graph Communities Oriol Ramos Terrades ∗ , Albert Berenguel, Débora Gil ∗ Computer Vision Center and the Department of Computer Science, Universitat Autònoma de Barcelona, Cerdanyola del Valles, 08193, Spain a r t i c l e i n f o a b s t r a c t Article history: Outlier detection is essential for optimal performance of machine learning methods and statistical Received 12 October 2021 predictive models. Their detection is especially determinant in small sample size unbalanced problems, Received in revised form 8 June 2022 since in such settings outliers become highly influential and significantly bias models. This particular Accepted 5 July 2022 experimental settings are usual in medical applications, like diagnosis of rare pathologies, outcome Available online 13 July 2022 of experimental personalized treatments or pandemic emergencies. In contrast to population-based Keywords: methods, neighborhood based local approaches compute an outlier score from the neighbors of each Classification algorithms sample, are simple flexible methods that have the potential to perform well in small sample size Detection algorithms unbalanced problems. A main concern of local approaches is the impact that the computation of each Description of feature space local structure sample neighborhood has on the method performance. Most approaches use a distance in the feature Graph communities space to define a single neighborhood that requires careful selection of several parameters, like the Machine learning algorithms number of neighbors. Outlier detectors This work presents a local approach based on a local measure of the heterogeneity of sample labels in the feature space considered as a topological manifold. Topology is computed using the communities of a weighted graph codifying mutual nearest neighbors in the feature space. This way, we provide with a set of multiple neighborhoods able to describe the structure of complex spaces without parameter fine tuning. The extensive experiments on real-world and synthetic data sets show that our approach outperforms, both, local and global strategies in multi and single view settings. © 2022 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). 1. Introduction The outlier concept is fuzzy, it depends on each task and thus each detection method provides its own definition. The authors in [1] define an outlier as a sample that “does not conform to ex- Outlier, or anomaly, detection is a major issue in many learning- pected behavior” and they classify them as point outliers, contextual based algorithms since the presence of outlier data on training outliers and collective outliers. Point outliers are samples with ab- data might affect the proper estimation of model parameters. normal feature values not expected for any of the classes and they Moreover, outlier detection becomes harder when data changes correspond to isolated samples either not belonging to any clus- along time, since it is unclear how to distinguish proper data, com- ter or not following the population distribution. Contextual outliers ing from a new arising class, from corrupted, or outlier, data. Out- are samples which are labeled differently from their neighboring lier detection is not just a technical step in a data cleaning process. samples, which define their context. In recent works authors de- It is, by itself, a key topic in many fields such as fraudulent doc- ument detection, in identity documents or passports, insurances tect outliers comparing samples to the other samples in the same claims and health care fraud; medical applications and assisted community [2,3]. Collective outliers are small group of samples diagnosis systems; detection of security threats, etc. In all these sharing unusual features that are clustered together. For instance, tasks, an accurate outlier detection will impact in the economic the authors in [4] detect these type of outliers on evolutionary net- balance of any company or to properly detect any security threat, works according to communities topological properties. In [5] split for instance. outliers are split into attribute outliers and class outliers in the con- text of multimodal representations. In such representations, usual in radiomics and computer assisted diagnosis [6], there are two or more feature spaces (called views) for each sample. Attribute out- * Corresponding authors. liers correspond to point outliers, while class outliers are similar E-mail addresses: oriolrt@cvc.uab.cat (O. Ramos Terrades), debora@cvc.uab.cat (D. Gil). to contextual outliers in the measure that are samples labeled dif- https://doi.org/10.1016/j.bdr.2022.100332 2214-5796/© 2022 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). O. Ramos Terrades, A. Berenguel and D. Gil Big Data Research 29 (2022) 100332 ferently across views. It follows that attribute and class outliers are With the advent of big data and deep learning techniques this different types of anomalous points and, thus, they are usually de- main drawback of global approaches seems to be mitigated since tected with different methods. In general existing methods only they can learn complex data structures from big amount of data. A perform optimally in one of the two types [7]. main issue when dealing with big data is labeling enough samples In this work we present a local approach based on a measure for training and testing deep learning methods, which is espe- of sample labels diversity in a set of topological neighborhoods of cially difficult in such an imbalanced classification task. In [11], each sample. We compute this topology extending the graph-based the authors define four groups of outlier detectors methods: unsu- method presented in [8]. In particular, we refine the initial topol- pervised, semi-supervised, hybrid and One-Class neural networks. ogy given by community detection methods to include isolated While is clear which methods belong to unsupervised and semi- non-outlier points. Sample diversity is computed using probabilis- supervised methods, hybrid methods use deep learning architec- tic measures, which summarize the variability of sample labels in tures for feature extraction and then use traditional outlier detec- the set of topological neighborhoods samples belong to. These di- tors. Finally, One-Class neural network (OC-NN) method is inspired versity measures provide a normalized outlierness representation by kernel methods on one-class classification tasks [12]. A variant feature space. This normalized space is independent of the actual of OC-NN architectures is Deep Support Vector Data Description sample features and only depends on their topological structure. (Deep-SVDD) [13]. In that work, the authors train a deep neu- Finally, a classifier, like support vector machine or random for- ral network to extract common variation factors by mapping close est, is used in a final step to detect outliers. We call our method inlier data instances to the center of a hyper-sphere. Generative Community-based Outlier Detector, COD. adversarial active learning (GAAL) networks are used to generate All in all, we contribute to the detection of outliers in the fol- potential outliers to help a binary classifier in accurately detect lowing aspects: outliers from normal data [14]. Recent works combine graph-based representations with deep learning techniques [15] and fuzzy clus- • A local description of feature spaces topology based on the tering methods optimized by Particle Swarm Optimization [16] to communities of a mutual-knn graph (mkNN) able to model detect anomaly behavior on time series. complex data distributions. There are some real use cases in which there are not enough • A normalized representation space of the degree of outlierness data for learning end-to-end methods. Although domain adapta- based on statistical measures of sample labels heterogeneity in tion and transfer learning techniques can be used to deal with the topological neighborhoods given by mkNN communities. small datasets, the success of these end-to-end methods relies on their capability to learn specific features for the outlier detection 2. Related work task. However, there are some use cases, like clinical decision sup- port systems or personalized models, in which feature vector are defined beforehand for the particular task and hence cannot be Existing methods for detection of outliers can be categorized modified to detect outliers. into global, local, graph-based and multiview approaches. Global methods are population based and they model the distribution in 2.2. Local methods the feature space of a set of (annotated) samples. Population distri- bution can be modeled using either parametric global descriptors Local methods are based on a description of each sample’s or unsupervised clustering approaches. These methods are suited neighborhood usually defined using the Euclidean distance among to detect point (or attribute) outliers as far as sample size is rela- samples in the feature space. Given that local methods define out- tively large and balanced. Local methods are based on a description liers in terms of such distances, they are distribution free and, thus, of the structure of each sample’s neighbors in the feature space better suited for unbalanced small datasets. The DBSCAN method and, thus, they are better suited to detect, both, attribute and class is a distance-based method able to discover clusters of arbitrary outliers, even in small sample size problems. Moreover, outlier shape while detecting outliers [17]. detector for structured data focus on identifying sub-graphs that Most local approaches, like [18] or [19], define outliers in terms broke repetitive patterns. Finally, outlier detectors for multiview of the distance to the k-th nearest point. LOF is an outlier de- data focus on finding samples that are not consistently labeled tector method defined in the context of knowledge discovery in across views. Below, we review the main methods in each cate- databases that assigns an outlierness score to each sample based gory. on local information [20]. This score is computed in terms of the distance to the k nearest neighbors of each point, meaning a score 2.1. Global methods near to 1 to not be an outlier while higher values provide higher certainty of being it. LOCI also bases on k-th nearest neighbors to Global approaches seek to estimate parametric data distribu- define a multi-granularity deviation factor (MDEF) as outlierness tions and define outliers as points not following the estimated measure [21]. The MDEF is the relative deviation of sample’s local distribution. For instance, in [9] the authors use Gaussian mix- neighborhood density from the average local neighborhood density, ture models (GMM) for outlier detection in which they define so that a point is an outlier if its MDEF is sufficient large. This way each point as a cluster and the outlierness score is the recipro- LOCI is effective to detect point outliers and collective outliers, as cal of the point likelihood. In general, data distribution cannot be well. The Isolation Forest, IF, technique builds a tree that isolates properly estimated in small sample size sets since outliers become attribute outliers using a binary search [22]. Since an attribute out- influential points which deviate global approaches from normal lier has different values compared to inlier points IF detects them population. This leads to lack of reproducibility and drop their po- as points such that the length path to reach them is significantly tential for outlier detection. Similarly, the authors in [10] propose shorter than the mean length to reach any other point. a Hidden Markov Random Field (HMRF) on attributed graphs to The selection of the parameters defining neighborhoods is a compute node outliers. Hidden variables represent community la- main bottleneck in local approaches. In particular, the selection bels, ranging from 0 to k, model parameters are estimated by the of the number k of nearest neighbors is crucial since it greatly EM algorithm and partition functions on each node are estimated affects methods performance. Therefore, several strategies for op- accordingly. Outliers are those nodes with partition function close timal selection of the parameter k have been proposed since the to 0. early years of nearest neighborhood approaches. 2 O. Ramos Terrades, A. Berenguel and D. Gil Big Data Research 29 (2022) 100332 2.3. Graph based methods Direct analysis of the local structural properties of graphs and networks also allows the detection of outliers and anomalies. The Neighboring relationship can be defined in terms of distances OddBall method is a widely used method for anomaly detection in but also in terms of friendship relationship on structured data, like networks which focus on detecting nodes having topological prop- graphs. In structured data, outliers are also linked to topological erties significantly different compared to neighboring nodes [30]. variation of subgraphs that broke a repetitive pattern [46]. To de- More recently, in [31], the authors propose an extension of the tect these local structural singularities, it has also been proposed NetEMD network method [32] to detect graph anomalies and spec- outlier detectors for graph-based representations. Deep learning tral localization statistics in financial transaction networks. Other has also been applied on such representations for anomaly detec- methods base on the Minimum Description Length (MDL) princi- tion [23]. ple. In [33] anomalous sub-graphs are detected using variants of The early work in [24] studied the relationship between con- MDL. In [34], the authors use MDL as well as other probabilistic nectivity of mutual-knn (mkNN) graph and outlier detection, pro- measures to detect several types of graph anomalies (e.g. unex- viding a criteria in terms of the graph topology. In particular, they pected/missing nodes/edges). studied the geometric properties of the underlying data points dis- tribution and derived a theoretical criterium to set a value of k 2.4. Multiview methods ensuring that the connected components of the graph correspond to clusters in the feature space. In that context, outliers were those All methods described above are specifically designed for the samples which did not belong to any of this connected compo- detection of attribute outliers in single view problems. Multimodal, nents, that is, they correspond to single node connected compo- or multiview, data can benefit of the different sources of informa- nents. The work in [24] was later extended in [25]. There, the tion to detect data outliers. In particular, class outliers are eas- authors provide further insights on the mutual k-nn graphs to de- ily spotted when a sample is labeled differently across views. In rive tighter bounds to estimate the optimal k to build a mkNN. this context, in [35] the authors detect class and attribute outliers A main inconvenience for a practical use is that these bounds are based on the spectral analysis of the combined adjacency matrix. still hard to compute with real data having class outliers. In that paper, those samples that lie in the kernel space of the In [26], the authors propose an algorithm to search the optimal combined adjacency matrix are identified as outliers. A different k to build the mkNN graph. In that work, the authors introduce the approach is the one proposed in [36] and [5]. In that works, the concepts of stability state and appropriate k (apk) for a mkNN graph authors propose a generalized K-means method that learns cluster and they propose an algorithm to search the optimal k. Finally, the label consistencies across views. Samples having different cluster most recent work of [27] also proposes a variation of mkNN graph labels are classified as class outliers. A specific limitation to multi to minimize the impact of k. In their approach, they compute mul- view methods is the combination of information across views, tiple local proximity graphs for k sampled uniformly in a range of which usually leads to under-detection of abnormalities arising in values. Then, their approach does not rely in finding the optimal k single views. Finally, another limitation is that being designed for of the mkNN graph but in combining the information of all mkNN more than view, multi view methods are prone to perform poorly graphs using a random walk to detect outliers. in single view problems. Aside fixing the parameter k, another concern about existing lo- cal approaches is that outlier scores are defined from the structure 3. COD: outlier detection based on a topological measure of of a single neighborhood defined using distances. From a mathe- pattern diversity matical point of view, this implies that the topological structure of feature spaces is modeled as a norm or metric space [28]. Al- Our method is a local approach based on graph communities, though Euclidean spaces admit a topology defined from a metric which encode the structure of a feature space. Fig. 1 sketches the or norm, these approaches might fail to properly describe more main steps of our method for the two-dimensional single view complex spaces (like manifolds [28]). Thus, topology is a powerful space shown in Fig. 1.a. The dataset has 2 classes (black dots and mathematical approach to model the structure of complex mani- red crosses), one class outlier (numbered 6) and one attribute out- folds without the assumption of any parametric model for the data. lier (numbered 10). The 3 main steps of the proposed method ap- Methods for the detection of communities in social networks plied to the synthetic data are shown in Fig. 1.b-d and described in can provide a mean to extract a set of topological neighbors the pseudocode of the algorithm of Algorithm 1. First, we encode from mkNN graphs. In this context, attribute outliers are often the local structure of feature vectors through a graph represent- non-connected, or hardly connected, individuals. Meanwhile, class ing their mutual k-nearest neighborhood. The nodes of the graph outliers correspond to community members with a user profile, are colored using each class color (red and black). Second, we use or interests, far of most of community members and they are methods for dynamical analysis of social networks to extend graph often ignored. While detecting attribute outliers is done using communities from an initial set of communities. Fig. 1.c shows the graph topological properties, computation of a topology in non- initial set of communities on the left and their extension on the structured spaces given by a discrete set of population samples right image. The algorithmic details of the extension of the initial still remains a challenge for topology. In [8], the authors presented communities are given in Algorithm 2. These extended communi- a local method based on neighborhoods given by the communities ties define, in the original feature space, a set of neighborhoods of the graph built from the samples distances. Despite the promis- of each sample. By definition of class and attribute outlier, isolated ing results in the diagnosis of lung cancer in confocal images, this nodes not belonging to any community are attribute outliers, while topology given by graph communities is prone to exclude many class outliers should belong to communities with an heterogeneous points that could not be considered isolated attribute outliers [29]. distribution of labels. In order to characterize the latter, we define Besides, like other local methods, a main concern is the impact of a local measure of abnormality from two probabilistic measures of the parameters used to compute the graph used to detect commu- each sample heterogeneity computed in its set of neighborhoods nities. In case k is too small, communities might exclude points (see Algorithm 3 for a pseudocode of this step). These two mea- that are not actually outliers [29], while increasing k produces a sures define a function from the set of samples to the unit square single community including all points. Thus, the method requires that maps inliers and outliers to different corners of the square. a proper accurate value for the parameter k, which the authors A classifier, C , discriminating between inliers and outliers provides fine-tuned to give optimal results. our measure of outlierness, Fig. 1.d. 3 O. Ramos Terrades, A. Berenguel and D. Gil Big Data Research 29 (2022) 100332 Fig. 1. Overview of the method: (a) Two-dimensional feature space with 2 classes (black dots and red crosses). (b) Graph encoding mutual k-nearest neighbors with nodes colored in red and black according to its class. Nodes 6 and 10 correspond, respectively, to the class attribute and attribute outliers. (c) Detection of communities: initial communities (c 1 , c 2 ) in left graph and their extension (ĉ 1 , ĉ 2 ) in the right graph. (d) Feature space and classifier margin (C ) giving the final outlierness measure from the communities. (For interpretation of the colors in the figure(s)and table(s), the reader is referred to the web version of this article.) Algorithm 1: COD: Community-based outlier detector Algorithm 2 for algorithmic details of this procedure. The initial (Single-View) communities are given by any community detection algorithms Data: V : labeled nodes, δ : percentile that generates overlapped communities. These detected communi- Result: s: outlier scores ties are prone to exclude many points that are not actual attribute A ← mkNN( V ) ; /* mutual-knn adjacency matrix */ outliers [29]. In order to add them to the set of initial communi- C ← CommunityDetection( A ); ties, we extend them following a modification of the iLCD com- Ĉ ← ExtendCommunities(G , C , δ); Φ ← ComputeTopologicaFeatures( V , Ĉ ); munity detector proposed in [37]. The iLCD method dynamically for ∀ϕi ∈ Φ do updates (extend, create or remove) an initial set of communities si ← Classify(ϕi ); using the temporal information in which node and edges appear end in a network. The criteria for updating communities are given in terms of the community internal connectivity, as well as, the con- In what follows, we give details about each of the main steps of nections between candidate nodes and community nodes. In our the proposed algorithm: graph construction, community detection case, an isolated node, w j , is added to an initially detected com- and definition of a outlierness feature space for the classification munity, c ∈ C , if it fulfills that: of inliers and outliers samples. CS(c , w j ) ≥ δ IC(c ) (3) 3.1. Graph construction for δ ∈ [0, 1] being a tolerance parameter, IC(c ) a measure of the community internal connectivity and CS(c , w j ) a measure of the The graph, G = ( V , A ), is given by the adjacency matrix of the connectivity between w j and the community c. Both measures are mutual k-nearest neighbor of samples. Let V := {(vi , vi ) | vi = computed from a function of the degree of the community nodes ( v 1i , . . . , v ni ) ∈ Rn , vi ∈ {1, . . . , L }, i = 1, . . . , N } be a set of N la- as follows. beled points in an n-dimensional feature space endowed with a Let S be the set composed of all nodes that belong to any of distance, namely d, and L the number of labels. For any positive the initially detected communities and G S and G c the subgraphs integer, k, let kNN(vi ) denote the set of vi k-nearest neighbors and induced by S and c, respectively. Then, for ∀vi ∈ C we can define mkNN( V i ) the set of vi mutual k-nearest neighbors defined as: the following function, ρc (vi ), measuring its belongingness to the community: mkNN(vi ) := {v j such that v j ∈ kNN(vi ) and vi ∈ kNN(v j )} (1) c Then, the adjacency matrix, A = (ai j ) = (a(v , v )), codifying G is i j degG (vi ) ρc (vi ) := S (4) defined as: degG (vi )  1 i j if v j ∈ mkNN(vi ) being deg the degree function of a node in a graph. The measure a(v , v ) = 1+d(vi ,v j ) (2) 0 otherwise of the internal connectivity of c is defined from ρc (vi ) as:  for d(vi , v j ) the distance between v j and vi . We note that the IC(c ) := ρc (vi ) (5) graph edges, ai j , are in [0, 1], being close to 0 if mutual neigh- vi ∈c bors are far from each other, close to 1, otherwise. This way, the number of neighbors for every node, vi , is related to the sparse- The measure of the connectivity between w j and c is also de- ness of the point vi in the feature space. fined from ρc (vi ) as:  ρc (vi ) 3.2. Community detection CS(c , w j ) := (6) d(w j , vi ) + 1 vi ∈c To alleviate the impact of k in the computation of (2), com- munities are computed using criteria for dynamic computation of since CS(c , w j ) is a weighted average of ρc (vi ) with weights 1 communities [37–39] to extend an initial set of communities, see j i , we have that: d(w ,v )+1 4 O. Ramos Terrades, A. Berenguel and D. Gil Big Data Research 29 (2022) 100332   1 The function ϕ1 measuring the heterogeneity in community la- CS(c , w j ) ≥ IC(c ) (7) max ji d(w j , vi ) + 1 bels is computed from their entropy as follows. For each sample 1 v, let Sv ⊆ Cˆ denote the subset of communities containing v and By the above inequality, we could set δ = . However, max ji d(w j ,vi )+1 Ent c the entropy of the labels of the nodes in a community c ∈ Sv such extreme value could aggregate some attribute outliers to the defined as: initial set of communities. In order to avoid such an artifact, we propose to define δ as a percentile of 1 probabilistic dis-  nl j i d(w ,v )+1 Ent c = − p ci log( p ci ) (9) tribution. i =1 Finally, candidate nodes w j that satisfy inequality (3) for a given community c are added in the extended community ĉ. We for p ci the probability in c of the i-th label. This probability is ap- denote by Cˆ the set of all the extended communities. proximated by the proportion of c nodes that are labeled i: |{w ∈ c | w = i }| p ci := (10) Algorithm 2: ExtendCommunities |{w ∈ c }| Data: G = ( V , A ): graph , C : set of communities, δ : percentile Result: Ĉ : set of extended communities for | · | denoting the cardinality of a set. Then, ϕ1 is defined as: S ← GetNonIsolatedNodes( V , C ); 1  W ←V \S ; ϕ1 (v, v ) := ϕ1 (v) := π ( Entc ≤ T ) (11) if W is empty then |S v | c ∈Sv return C ; /* if no isolated nodes exist, no need to extend communities */ being T ∈ [0, log(n )] a tolerance threshold on the maximum en- end tropy allowed in community labels and π (a) = 1 if a holds. We Ĉ ← ∅ ; note that log(n is the maximum value of Ent C achieved in case of for ∀c ∈ C do ĉ ← c ; /* Initialize the extended community with the uniformly distributed labels, p ci = 1/n , ∀i. original community */ The score ϕ1 (v) ∈ [0, 1] has extreme values ϕ1 (v) = 0 in case ρc ← ComputeRho(G , S , v ) ; /* as in (4) */ all communities in Sv have heterogeneous labels and ϕ1 (v) = 1 in IC(c ) ← ComputeIC(c , ρc ) ; /* as in (5) */ case the label within each community is the same for all nodes for ∀w j ∈ W do in the community. We note that, in this last case, by definition of CS(w j , c ) ← ComputeCS(w j , c , ρc ) ; /* as in (6) */ if (3) holds then Ent c , the label must be the same for all communities in Sv .  ĉ ← {w j } ĉ; The function ϕ2 measuring how many nodes in the community end have a label equal to the sample label, v, is computed from the end  probability of v , as follows. For each c ∈ Sv , let p cv denote the Ĉ ← {ĉ } Ĉ ; probability of v in c excluding v: end return Ĉ |{w ∈ c \ v | w = v }| p cv = (12) |{w ∈ c \ v}| Then, ϕ2 is defined as: 3.3. Outlierness feature space 1  c ϕ2 (v, v ) := p v (13) |S v | Given that communities define a set of neighbors in the feature c ∈Sv space, nodes not belonging to any of the extended communities The measure ϕ2 (v, v ) ∈ [0, 1] and has extreme values correspond to attribute outliers. Meanwhile, class outliers are ex- ϕ2 (v, v ) = 0 in case no community in Sv is consistent with v pected to belong to communities with either high heterogeneity in label, ϕ2 (v, v ) = 1 in case all communities have nodes with labels nodes label or the majority of nodes with a label different from equal to v . the class outlier label. Finally, in order to increase the separability across the differ- Under the above considerations, we define two quantities, ϕ1 , ent types of outliers, we transform ϕ1 , ϕ2 to logarithmic scale by ϕ2 , measuring how homogeneous the labels of the communities a applying the function: sample belongs to are. Algorithm 3 provides the pseudocode de- scribing how to compute them. For each sample, the function ϕ1 1 f (x) = (14) quantifies the heterogeneity in community labels, while ϕ2 quan- 1 − log x tifies how many nodes in the community have a label different to x = ϕi , i = 1, 2. from the sample label. Both measures are based on the probabilis- In the multi view case, we model the space as a Cartesian prod- tic distribution of the community node labels and are normalized uct and, thus, compute a mkNN graph for each view. Communities in [0, 1] in such a way that they define a function ϕ : are computed independently for each of these graphs and so are ϕ: V −→ [0, 1] × [0, 1] the probabilistic measures. These view-dependent measures are (8) aggregated to define the function that maps samples to the unit (vi , vi ) → (ϕ1 (vi , vi ), ϕ2 (vi , vi )) square. We compute the two measures for each view and aggre- j j mapping inliers to (1, 1), attribute outliers to (0, 0) and class out- gate them to define ϕ . If ϕ1 , ϕ2 denote the measures computed liers to either (1, 0) or (0, 1) depending on whether they be- for the j-th view, then their minimum values across views define long to one or more communities. In case v does not belong to the function ϕ as: any community, we have an attribute outlier and, thus, we set ϕ (v) = (0, 0). This way, ϕ defines a 2-dimensional feature space ϕ: V −→ [0, 1] × [0, 1] able to discriminate inliers and outliers. The probability of a classi- (vi , vi ) → (ϕ1 (vi , vi ), ϕ2 (vi , vi )) := (15) j j fier trained to discriminate between them provides our outlierness (min j ϕ1 (vi , vi ), min j ϕ2 (vi , vi )) score and its output class our outlier detection. 5 O. Ramos Terrades, A. Berenguel and D. Gil Big Data Research 29 (2022) 100332 Fig. 2. Synthetic data generated for experiments following 2 standard normal distributions. Distribution points have randomly generated and outliers (red points), as well. mkNN graph is generated for values: (a) k = 4, (b) k = 10 and (c) k = 40. Algorithm 3: ComputeTopologicaFeatures Table 1 Selected UCI and Synthetic Datasets. Data: V : labeled nodes, Ĉ : set of extended communities Result: Φ : set of topological features Datasets Dimension Num of Samples Num of Classes for ∀c ∈ Ĉ do Iris 4 150 3 Ent c ← ComputeEntropy(c ) ; /* as in (9) */ BCW 10 699 2 end Ionosphere 34 351 2 for ∀v ∈ V do Letter recognition 16 20,000 26 ϕ1 (v) ← ComputePhi1(v, { Ent c }) ; /* as in (11) */ ϕ2 (v) ← ComputePhi2(v, { Ent c }) ; /* as in (13) */ Synthetic 6 1,000 2 end Φ ← Transform(Φ) ; /* as in (14) */ return Φ each view. In order to simulate class outliers, we swapped the la- bels of points randomly selected from random pairs of classes. In the multi view case, classes were swapped in views randomly se- 4. Experimental set-up lected. For the first experiment, we generated a single view synthetic We carried out two experiments to evaluate the performance of dataset in R6 generated from two standard normal distributions the COD method: with minimal overlap, see Fig. 2. A total number of 30 different populations of 500 samples for each distribution were generated 1. Impact of COD configuration in communities. In a first exper- with different percentages of attribute outliers: 2%, 5% and 8%. Ta- iment, we evaluated the benefits of the community extension ble 1 summarizes the main characteristics of the synthetic dataset technique within the community detection step on a synthetic used for the first experiment. dataset. The performance of COD strongly depend on the de- For the second experiment, we have considered, both, attribute tected communities, which in turn also depend on the nodes and class outliers in single and multi view settings. In particular, connectivity. The goal of this experiment was to evaluate the we considered the following 3 combinations of attribute and class impact of the number of neighbors in the construction of the outliers: i) 8% class outlier + 2% attribute outlier, labeled 8-2, ii) mkNN graph, as well as, the method for the definition of the 5% class outlier + 5% attribute outlier, labeled 5-2 and iii) 2% class initial communities. For this experiment a single view syn- outlier + 8% attribute outlier, labeled 2-8. For the single view set- thetic dataset with attribute outliers was generated. ting, we also added the same 3 percentages of attribute outliers 2. Comparison to SoA single and multi view methods. In a sec- as for the synthetic data: 2%, 5% and 8%. Following [35], the multi ond experiment, we compared the COD method to other out- view case was defined by splitting UCI features into disjoint sets, lier detection methods on benchmark datasets from the UCI each of them defining one view. Feature splitting was done by tak- repository.1 The goal of this experiment was to compare the ing half of the original features for each view as reported in [35]. performance of the proposed method to detect the rate of We considered 2 and 3 views for all sets, with the exception of attribute and class outliers in, both, single and multi view Iris, which dimensionality only allows splitting features in 2-views. settings. For this experiment a selection of UCI datasets was For each outlier configuration and UCI dataset, we generated 50 altered to include several percetages of attribute and class out- different sets with outliers for statistical analysis of results. liers in a single and multi view setting. Table 1 reports the main characteristics of the 4 UCI datasets selected for these experiments. These datasets have been selected Next, we describe the generation of datasets and metrics used to be representative of the main configurations of classification for each experiment feature spaces. In particular, they include datasets presenting the most common artifacts dropping performance of methods, like 4.1. Generation of datasets with outliers small sample size (Ionosphere), large dimensionality (Ionosphere) and large number of classes with some of them being minority For each experiment, we generated attribute and class outliers groups (Letter Recognition). following the same experimental setting as in [5]. In order to sim- ulate attribute outliers, the features of the selected samples were 4.2. Quality metrics changed by random numbers following a distribution with the highest probability outside the range of the values expected for The metrics used for the first experiment are the false posi- the original data. In the multi view case, features were altered in tive (FP) and true positive (TP) rates before and after applying the community extension technique. The FP rate is computed as the ratio of inliers not in a community with respect to all the sam- 1 https://archive.ics.uci.edu/ml/datasets.php. ples without community. The TP rate is computed as the number 6 O. Ramos Terrades, A. Berenguel and D. Gil Big Data Research 29 (2022) 100332 Table 2 Mean and standard deviation of FP and TP rates for the selected CD algorithms before and after applying the community extension step. CD k FP rate TP rate before after reduction rate before after reduction rate angel 4 0,94 ± 0,03 0,01 ± 0 0,99 ± 0 0,99 ± 0,03 0,98 ± 0,03 0,01 ± 0,02 [40] 10 0,82 ± 0,07 0,01 ± 0,01 0,99 ± 0,01 0,95 ± 0,08 0,86 ± 0,22 0,09 ± 0,22 40 0,24 ± 0,1 0,23 ± 0,1 0,01 ± 0,03 0,81 ± 0,18 0,81 ± 0,18 0±0 core 4 0,83 ± 0,05 0±0 1±0 0,59 ± 0,19 0,53 ± 0,19 0,11 ± 0,08 expansion 10 0,84 ± 0,04 0±0 1±0 0,48 ± 0,2 0,44 ± 0,2 0,09 ± 0,08 [41] 40 0,55 ± 0,09 0,04 ± 0,04 0,92 ± 0,07 0,32 ± 0,18 0,31 ± 0,18 0,03 ± 0,05 danmf 4 0±0 0±0 0±0 0±0 0±0 0±0 [42] 10 0±0 0±0 0±0 0±0 0±0 0±0 40 0±0 0±0 0±0 0±0 0±0 0±0 dcs 4 0,89 ± 0,04 0±0 1±0 0,58 ± 0,19 0,53 ± 0,18 0,08 ± 0,06 10 0,81 ± 0,05 0,02 ± 0,02 0,97 ± 0,02 0,47 ± 0,18 0,46 ± 0,18 0,04 ± 0,05 40 0,13 ± 0,1 0,13 ± 0,1 0,01 ± 0,04 0,35 ± 0,18 0,35 ± 0,18 0 ± 0,01 k clique 4 0,93 ± 0,03 0±0 1±0 0,94 ± 0,06 0,91 ± 0,07 0,04 ± 0,04 10 0,78 ± 0,08 0,01 ± 0,01 0,99 ± 0,01 0,88 ± 0,1 0,84 ± 0,11 0,05 ± 0,04 40 0,19 ± 0,09 0,18 ± 0,09 0,03 ± 0,1 0,69 ± 0,19 0,69 ± 0,19 0 ± 0,01 of outliers without any community with respect the total number with the angel, dcs and k clique methods, due to a high internal of outliers. Thus, the targeted FP rate is 0, which means all inliers connectivity of the initial communities. In this case, the I C (C ) of points are within a community, and the targeted TP rate is 1, which the condition to add nodes is close to one and, thus, the inequality means that all attribute outliers are not in any community. In other given by (5) is hardly satisfied. For lower values of k, FP rate re- words, setting outliers as the positive class, this metrics measure duces to almost 0 cases, while a reduction in TP rates of less than the percentage of outliers correctly detected by the method and 10%. the percentage (over all normal samples) of non-outliers wrongly Therefore, the configuration for computing the initial commu- identified as outliers. Ranges (given by mean ± standard deviation) nities that we recommend is a low value of k and any CD giving a were computed, for each configuration and community detection large number of initial communities. approach, over the TP and FP for the 30 populations of synthetic data randomly generated. 5.2. Experiment 2. Comparison to SoA single and multi view methods The metric used for the second experiment reported in Ta- bles 2-3 is the Area Under the ROC Curve (AUC) computed taking We have compared COD to single view methods including 5 lo- outliers as the positive class. As before, for each method, ranges cal and 3 global approaches. The local methods are DBSCAN [17], (given by mean ± standard deviation) were computed over the LOF [20], LOCI [21], KNN [18] and IF [22], while the global ones 50 populations of each outlier configuration: single view with at- are GMM [9], the graph-based APS [27] and the deep-learning one tribute outliers for and multi view with, both, attribute and class SO-GAAL [14] model. The multi view methods are the best per- outliers. formers reported in [5], DMOD [5], AP [43] and MLRA [44], and the pioneering multi view approach HOAD [35]. According to the 5. Results first experiment, our method was computed using the following parameters. The mkNN graph was computed setting k = 10. For 5.1. Experiment 1. Impact of COD configuration in communities the extension of the initial communities, the tolerance δ in (3) was computed for the 75% percentile as before. Initial communities The mkNN graphs were built with values k = 4, 10 and 40 on were computed using the k-clique method. synthetic sets randomly generated as described in Section 4.1. For Finally, for the computation of the outlierness measure, we use each graph, we computed the initial communities using 5 off-the- a SVM classifier trained on a sub-set of the MirFlickr dataset [45] self community detection (CD) algorithms implemented in the CD altered to have the different types of outliers. To train it, we use pyhton Library.2 For the extension of the initial communities, the the second last layer of a pre-trained VGG network as feature tolerance δ in (3) was computed for the 75% percentile. Table 2 vector on images with a single annotation. Then, we applied a K- reports a statistical summary of TP and FP rates for each COD means to identify those annotations that does not highly overlap configuration before and after applying the community extension between them and, to further reduce the size of samples, we select technique o assess changes in FP and TP rates before and after ap- only those samples with minimal overlapping. Then, we generated plying the community extension. class and attribute outliers as explained in Section 4.1. First, given the standard deviation values we observe that FP Table 3 reports the AUC (mean ± standard deviation) for the re- and TP rates are quite stable through the repetitions and the sults obtained for the proposed COD, DBSCAN, LOF, LOCI, IF, GMM, outliers configuration. Second, the proposed community extension SO-GAAL and APS on Iris, Breast Cancer Winconsin (BCW), Iono- technique behaves as expected, i.e. overall, the FP ratio is reduced sphere and Letter Recognition datasets with different settings [27]. without significantly harming the TP ratio regardless the CD algo- Following [5], the first and second best performers for each con- rithm and the value of the mkNN graph. The only exception is the figuration are marked in red and blue, respectively. The analysis of deep learning approach danmf which assigns all samples to a sin- the ranges lead to the following observations. gle initial community and, thus, the extension technique is useless. According to the number of times that methods are ranked This is also the case for k = 40 with initial communities defined in the top 2, best performers are COD (being 12/24 = 50% times with 10/24 = 42% first rank), KNN (being 13/24 = 54% times with 3/24 = 12% first rank), GMM (being 7/24 = 30% times with 3/24 = 2 CDlib - Community Discovery Library: https://cdlib.readthedocs.io/. 12% first rank), APS (being 5/24 = 20% times with 4/24 = 17% 7 O. Ramos Terrades, A. Berenguel and D. Gil Big Data Research 29 (2022) 100332 Table 3 AUC values (mean ± standard deviation) for the Single View Case. DataSet Method 2-8 5-5 8-2 0-8 0-5 0-2 Iris DBSCAN 0.716 ± 0.074 0.675 ± 0.050 0.580 ± 0.027 0.805 ± 0.103 0.831 ± 0.100 0.883 ± 0.130 LOF 0.973 ± 0.020 0.958 ± 0.024 0.949 ± 0.039 0.992 ± 0.003 0.978 ± 0.003 0.958 ± 0.024 LOCI 0.962 ± 0.022 0.888 ± 0.052 0.728 ± 0.058 0.971 ± 0.007 0.966 ± 0.011 0.962 ± 0.006 KNN 0.974 ± 0.019 0.936 ± 0.042 0.866 ± 0.061 0.990 ± 0.002 0.982 ± 0.004 0.970 ± 0.002 IF 0.905 ± 0.025 0.855 ± 0.029 0.814 ± 0.036 0.987 ± 0.009 0.975 ± 0.001 0.959 ± 0.000 APS 0.882 ± 0.047 0.891 ± 0.046 0.882 ± 0.047 0.862 ± 0.07 0.854 ± 0.088 0.910 ± 0.120 GMM 0.484 ± 0.004 0.484 ± 0.004 0.485 ± 0.012 0.484 ± 0.003 0.484 ± 0.003 0.484 ± 0.002 SO-GAAL 0.614 ± 0.019 0.605 ± 0.096 0.559 ± 0.087 0.663 ± 0.090 0.631 ± 0.090 0.602 ± 0.134 COD 0.976 ± 0.045 0.980 ± 0.029 0.979 ± 0.020 0.971 ± 0.052 0.980 ± 0.041 0.989 ± 0.007 BCW DBSCAN 0.845 ± 0.025 0.724 ± 0.016 0.590 ± 0.008 0.936 ± 0.030 0.944 ± 0.034 0.970 ± 0.032 LOF 0.545 ± 0.092 0.528 ± 0.071 0.509 ± 0.032 0.513 ± 0.071 0.525 ± 0.088 0.511 ± 0.044 LOCI 0.882 ± 0.008 0.735 ± 0.010 0.593 ± 0.013 0.981 ± 0.005 0.972 ± 0.004 0.963 ± 0.002 KNN 0.889 ± 0.005 0.739 ± 0.008 0.592 ± 0.012 0.991 ± 0.002 0.981 ± 0.002 0.966 ± 0.001 IF 0.885 ± 0.005 0.733 ± 0.009 0.588 ± 0.013 0.987 ± 0.001 0.973 ± 0.001 0.959 ± 0.000 APS 0.794 ± 0.029 0.674 ± 0.029 0.580 ± 0.029 0.882 ± 0.033 0.863 ± 0.040 0.895 ± 0.048 GMM 0.371 ± 0.008 0.472 ± 0.015 0.574 ± 0.015 0.299 ± 0.003 0.299 ± 0.002 0.298 ± 0.002 SO-GAAL 0.693 ± 0.040 0.597 ± 0.032 0.533 ± 0.023 0.733 ± 0.056 0.709 ± 0.063 0.672 ± 0.084 COD 0.879 ± 0.039 0.830 ± 0.035 0.747 ± 0.033 0.936 ± 0.042 0.954 ± 0.037 0.978 ± 0.002 Ionosphere DBSCAN 0.850 ± 0.012 0.721 ± 0.015 0.582 ± 0.017 0.954 ± 0.007 0.952 ± 0.007 0.947 ± 0.010 LOF 0.679 ± 0.034 0.647 ± 0.030 0.572 ± 0.019 0.736 ± 0.041 0.797 ± 0.047 0.892 ± 0.059 LOCI 0.823 ± 0.025 0.722 ± 0.016 0.585 ± 0.020 0.922 ± 0.027 0.956 ± 0.023 0.954 ± 0.018 KNN 0.874 ± 0.009 0.734 ± 0.011 0.583 ± 0.017 0.987 ± 0.005 0.976 ± 0.002 0.960 ± 0.001 IF 0.871 ± 0.011 0.734 ± 0.012 0.584 ± 0.019 0.987 ± 0.006 0.974 ± 0.001 0.958 ± 0.010 APS 0.881 ± 0.025 0.742 ± 0.026 0.579 ± 0.034 0.995 ± 0.002 0.996 ± 0.004 0.996 ± 0.005 GMM 0.590 ± 0.012 0.697 ± 0.017 0.814 ± 0.019 0.497 ± 0.001 0.497 ± 0.001 0.497 ± 0.001 SO-GAAL 0.515 ± 0.035 0.503 ± 0.029 0.511 ± 0.025 0.514 ± 0.048 0.509 ± 0.043 0.503 ± 0.055 COD 0.845 ± 0.023 0.762 ± 0.032 0.686 ± 0.033 0.902 ± 0.007 0.891 ± 0.006 0.890 ± 0.003 Letter Rec. DBSCAN 0.891 ± 0.005 0.744 ± 0.003 0.606 ± 0.0018 0.994 ± 0.005 0.995 ± 0.0059 0.997 ± 0.008 LOF 0.533 ± 0.009 0.522 ± 0.007 0.508 ± 0.007 0.539 ± 0.011 0.527 ± 0.013 0.504 ± 0.015 LOCI ± ± ± ± ± ± KNN 0.513 ± 0.010 0.500 ± 0.008 0.486 ± 0.006 0.516 ± 0.012 0.510 ± 0.012 0.521 ± 0.014 IF 0.516 ± 0.013 0.503 ± 0.010 0.494 ± 0.009 0.514 ± 0.013 0.509 ± 0.016 0.534 ± 0.019 APS 0.492 ± 0.014 0.483 ± 0.010 0.473 ± 0.011 0.503 ± 0.015 0.640 ± 0.015 0.751 ± 0.014 GMM 0.894 ± 0.010 0.893 ± 0.009 0.901 ± 0.008 0.916 ± 0.011 0.939 ± 0.011 0.968 ± 0.012 SO-GAAL 0.495 ± 0.021 0.492 ± 0.020 0.487 ± 0.018 0.485 ± 0.024 0.493 ± 0.035 0.492 ± 0.043 COD 0.844 ± 0.013 0.872 ± 0.009 0.906 ± 0.007 0.821 ± 0.017 0.809 ± 0.015 0.795 ± 0.013 first rank) and DBSCAN (being 5/24 = 20% times with 3/24 = 12% uration 8-2) that it is the second best. The HOAD method is the first rank). The remaining methods achieve top ranges in less than worst performer with 0 times having top ranges. 20% of the cases, being the deep-learning method SO-GAAL the All methods, excluding the proposed COD, perform better in worst performer with 0 top ranges. The ranking of top ranges in- the 2-view case. Our COD is the only method that has similar dicates that local methods perform better than global ones, as 3 (top) ranges for, both, 2 and 3 view configurations. Regarding out- best ranked methods are local approaches. It is worth noticing that lier configurations, there is not a clear trend across datasets. For our COD is the only method that has top ranges for all datasets Iris and Breast performance increases with the number of class and outlier configurations. Meanwhile, the other top ranked meth- outliers, while it decreases for Ionosphere and Letter Recognition ods achieve their best performance only in some of the datasets. In datasets. Although this behavior holds for both views, the decrease particular, LOCI did not converge for the Letter Recognition dataset. rate seems to be a bit higher for the 3-view case. Therefore, we at- If we compare ranges between configurations with same quan- tribute it to, both, the separability of the original dataset, as well tity of attribute outliers but different quantity of class outliers (2-8 as, the partition of features to simulate the multi view configura- against 0-8, 5-5 against 0-5 and 8-2 against 0-2) we have that, tion, which might have selected features having the least discrim- in general, community detection methods are better detecting at- inating power. tribute outliers than class outliers. In particular, the configuration that has worst ranges is the one with higher number of class- 6. Discussion and conclusions outliers (8-2). Among all methods, our COD is the one that has the lowest drop in performance in the presence of class-outliers. Table 4 reports the AUC (average ± standard deviation) for The first experiment shows that our community extension elim- the results obtained for the proposed COD, HOAD, AP, MLRA and inates FP in the detection of attribute outliers in case of initial DMOD on Iris, Breast Cancer Winconsin (BCW), Ionosphere and communities with low connectivity. In such case, the rate of TP Letter Recognition with different settings. As before, the best two for the initial communities is already very high and close to one. performers for each configuration are marked in red and blue. The Low connectivity in communities is guaranteed for low values of analysis of the ranges lead to the following observations. k in mkNN graph, regardless of the DC method used. Therefore, Ranking as before according to the number of top ranges, since the community extension preserves TP rates, we conclude the best performers by large are COD (21/21 = 100% times with that COD has optimal performance for k ≤ 10 regardless of the DC 18/21 = 86% first ranks) and DMOD (17/21 = 81% times with only method used for the computation of initial communities. Conse- 2/21 = 10% first ranks). The proposed COD is the best performer quently, this makes the choice of community detection algorithm for all cases, but three cases (2-View Ionosphere with outlier con- and the values of the mkNN graph to be not critical for the final figuration 2-8 and 3-View Letter Recognition with outlier config- performance of the COD method. 8 O. Ramos Terrades, A. Berenguel and D. Gil Big Data Research 29 (2022) 100332 Table 4 AUC values (mean ± standard deviation) for the multi view Case. DataSet Method 2-View Case 3-View Case 2-8 5-5 8-2 2-8 5-5 8-2 Iris HOAD 0.167 ± 0.057 0.309 ± 0.063 0.430 ± 0.055 −− −− −− AP 0.326 ± 0.027 0.630 ± 0.021 0.840 ±0.021 −− −− −− MLRA 0.856 ± 0.063 0.828 ± 0.080 0.826 ± 0.089 −− −− −− DMOD 0.909 ± 0.044 0.831 ± 0.038 0.799 ± 0.068 −− −− −− COD 0.975 ± 0.024 0.971 ± 0.023 0.970 ± 0.021 −− −− −− BCW HOAD 0.555 ± 0.072 0.586 ± 0.061 0.634 ± 0.046 0.538 ±0.027 0.597 ± 0.038 0.643 ± 0.008 AP 0.293 ± 0.012 0.532 ± 0.024 0.693 ± 0.023 0.190 ± 0.016 0.388 ± 0.012 0.593 ± 0.046 MLRA 0.745 ± 0.056 0.715 ± 0.022 0.688 ± 0.028 0.614 ± 0.057 0.596 ± 0.032 0.599 ± 0.029 DMOD 0.824 ± 0.022 0.752 ± 0.019 0.692 ± 0.036 0.657 ± 0.017 0.720 ± 0.013 0.799 ± 0.016 COD 0.890 ± 0.027 0.935 ± 0.019 0.947 ± 0.013 0.838 ± 0.022 0.897 ± 0.020 0.910 ± 0.014 Ionosphere HOAD 0.446 ± 0.074 0.442 ± 0.051 0.448 ± 0.041 0.489 ± 0.079 0.477 ± 0.072 0.444 ± 0.065 AP 0.623 ± 0.033 0.761 ± 0.025 0.822 ± 0.030 0.511 ± 0.027 0.659 ± 0.043 0.758 ± 0.035 MLRA 0.645± 0.084 0.669 ± 0.028 0.776± 0.037 0.645 ± 0.040 0.663 ± 0.048 0.700 ± 0.045 DMOD 0.877 ± 0.032 0.801 ± 0.042 0.774 ± 0.049 0.818 ± 0.018 0.787 ± 0.039 0.784 ± 0.037 COD 0.841 ± 0.024 0.811 ± 0.024 0.780 ± 0.029 0.854 ± 0.019 0.827 ± 0.025 0.791 ± 0.036 Letter Rec. HOAD 0.536 ± 0.046 0.663 ± 0.057 0.569 ± 0.049 0.193 ± 0.022 0.488 ± 0.111 0.563 ± 0.081 AP 0.372 ± 0.057 0.550 ± 0.043 0.640 ± 0.051 0.189 ± 0.039 0.340 ± 0.037 0.570 ± 0.63 MLRA 0.883 ± 0.024 0.817± 0.051 0.786 ± 0.065 0.841 ± 0.055 0.716 ± 0.044 0.640 ± 0.081 DMOD 0.912 ± 0.029 0.846 ± 0.022 0.762 ± 0.025 0.916 ± 0.031 0.815 ± 0.038 0.664 ± 0.037 COD 0.926 ± 0.009 0.904 ± 0.011 0.877 ± 0.011 0.843 ± 0.014 0.816 ± 0.016 0.774 ± 0.017 Concerning comparison to SoA methods in single and multi The only method [5] able to detect both types only works for view settings, the analysis of results lead to the following con- multi view settings. COD representation space measuring di- clusions. In, both, single and multi view settings, local methods versity from topological neighborhoods allows the detection of perform better than global ones. In fact, the worst performers in all kinds of outliers regardless of the view structure. both settings are the global methods SO-GAAL (single view) and • A universal outlierness measure that can be directly applied HOAD (multi view). Among all local approaches, COD outperforms to any data set without any exta training or fine tuning. Since existing methods in, both, single and multi view settings, regard- COD is based on the distribution of intrinsic measures of het- less of the outlier configuration. Unlike most methods, it performs erogeneity, the only adaptation that requires is the computa- equally well in small size and high dimensionality datasets (like tion of mkNN graph communities of each new data set. This Ionosphere). COD is also top performer in case of minority classes is a main advantage over most existing methods that require (like the Letter Recognition dataset) for multi view settings. Al- training the model from scratch for each new data set. though for single view configurations performance drops, COD is still competitive compared to top performers. In summary, we propose an outlier detector based on a topolog- It is worth noticing that COD has been applied with the same ical description of local structure to provide a universal outlierness parameter configuration to all datasets in, both, training and test. representation space able to detect all types of outliers even in Regarding COD training, we used a completely different repository small size unbalanced settings which are specially challenging for (MirFlickr-25K dataset) and no learning transfer was applied. This most machine learning methods. is a main advantage compared to existing approaches that require fine tuning of parameters and a re-training for new datasets. Declaration of competing interest All in all, comparing to existing outliers detection methods, the proposed approach has the following advantages. On one side, our The authors declare that they have no known competing finan- description of feature spaces local structure endows COD with the cial interests or personal relationships that could have appeared to following properties: influence the work reported in this paper. • Capability to model data distributions structured as manifolds. Acknowledgement Our description based on mkNN graph communities provides, for each sample, with a set of multiple neighborhoods alter- This work was supported by the Spanish Ministry of Science native to the usual n-dimensional Euclidean balls centered at and Innovation with projects RTI2018-095645-B-C21, RTI2018- each sample. COD alternative neighborhoods can describe data 095209-B-C21, PID2021-126776OB-C21 and PID2021-12688OB-I00, distributions structured as manifolds, which is a significant ad- Generalitat de Catalunya, 2017-SGR-1624 and 2017-SGR-1783 and vantage over existing local methods. CERCA-Programme. DGil would like to dedicate this work to the • High performance in small sample size unbalanced sets. Unlike most outstanding outlier, her mother, Esther Resina Enfedaque. global and deep learning methods, graph communities can be robustly computed for small data sets regardless of the dimen- References sion of feature spaces. [1] V. Chandola, A. Banerjee, V. Kumar, Anomaly detection: a survey, ACM Comput. Surv. 41 (3) (2009) 15. On the other side, the normalized representation of outlierness [2] M. Kopp, M. Grill, J. Kohout, Community-based anomaly detection, in: 2018 has the following significance: IEEE International Workshop on Information Forensics and Security (WIFS), IEEE, 2018, pp. 1–6. [3] R. Francisquini, A.C. Lorena, M.C. Nascimento, Community-based anomaly • Ability to detect class, as well as, attribute outliers in single detection using spectral graph filtering, Appl. Soft Comput. 118 (2022) and multi view settings. With the exception of [5], existing 108489, https://doi.org/10.1016/j.asoc.2022.108489, https://www.sciencedirect. methods are specialized in detecting a unique type of outliers. com/science/article/pii/S1568494622000424. 9 O. Ramos Terrades, A. Berenguel and D. Gil Big Data Research 29 (2022) 100332 [4] Z. Chen, W. Hendrix, N.F. Samatova, Community-based anomaly detection in [26] J. Ning, L. Chen, C. Zhou, Y. Wen, Parameter k search strategy in outlier detec- evolutionary networks, J. Intell. Inf. Syst. 39 (1) (2012) 59–85. tion, Pattern Recognit. Lett. 112 (2018) 56–62. [5] H. Zhao, et al., Consensus regularized multi-view outlier detection, IEEE Trans. [27] C. Wang, Z. Liu, H. Gao, Y. Fu, Applying anomaly pattern score for outlier de- Image Process. 27 (1) (2018). tection, IEEE Access 17 (2019) 16008–16021. [6] P. Lambin, R. Leijenaar, T. Deist, et al., Radiomics: the bridge between medical [28] J. Munkres, General Topology, Prentice-Hall, 2000. imaging and personalized medicine, Nat. Rev. Clin. Oncol. 14 (2017) 749–762. [29] J. Mielgo, Analysis of Community Detection Algorithms for Image Annotation, [7] K. Choi, J. Yi, C. Park, S. Yoon, Deep learning for anomaly detection in 2017. time-series data: review, analysis, and guidelines, IEEE Access 9 (2021) [30] L. Akoglu, M. McGlohon, C. Faloutsos oddball, Spotting anomalies in weighted 120043–120065. graphs, in: M.J. Zaki, J.X. Yu, B. Ravindran, V. Pudi (Eds.), Advances in Knowl- [8] D. Gil, O. Ramos Terrades, E. Minchole, C. Sanchez, N. Cubero de Frutos, M. edge Discovery and Data Mining, Springer Berlin Heidelberg, Berlin, Heidelberg, Diez-Ferrer, A. Maria Ortiz, R. ans Rosell, Classification of confocal endomi- 2010, pp. 410–421. croscopy patterns for diagnosis of lung cancer, in: CLIP-MICCAI, in: Lecture [31] A. Elliott, M. Cucuringu, M.M. Luaces, P. Reidy, G. Reinert, Anomaly detection Notes in Computer Science, 2017, pp. 151–159. in networks with application to financial transaction networks, CoRR, arXiv: [9] X. Yang, L. Jan, L.D. Pokrajac, Outlier detection with globally optimal exemplar- 1901.00402, 2019. based gmm, in: SIAM International Conference on Data Mining, 2009, [32] A. Wegner Ospina-Forero, R. Gaunt, C. Deane, G. Reinert, Identifying net- pp. 145–154. works with common organizational principles, J. Complex Netw. 6 (6) (2018) [10] S. Pandhre, M. Gupta, V.N. Balasubramanian, Community-based outlier detec- 887–913. tion for edge-attributed graphs, CoRR, arXiv:1612.09435 [abs], 2016, arXiv: [33] C.C. Noble, D.J. Cook, Graph-based anomaly detection, in: Proceedings of the 1612.09435, http://arxiv.org/abs/1612.09435. 9th ACM SIGKDD International Conference on Knowledge Discovery and Data [11] R. Chalapathy, S. Chawla, Deep learning for anomaly detection: a survey, CoRR, Mining, KDD ’03, 2003, pp. 631–636. arXiv:1901.0340, 2019. [34] W. Eberle, L. Holder, Discovering structural anomalies in graph-based data, in: [12] R. Chalapathy, A. Krishna Menon, S. Chawla, Anomaly detection using one-class Seventh IEEE International Conference on Data Mining Workshops (ICDMW neural networks, CoRR, arXiv:1802.06360, 2018. 2007), 2007, pp. 393–398. [13] L. Ruff, N. Görnitz, L. Deecke, S.A. Siddiqui, R. Vandermeulen, A. Binder, E. [35] J. Gao, N. Du, W. Fan, D. Turaga, S. Parthasarathy, J. Han, A multi-graph spec- Müller, M. Kloft, Deep one-class classification, in: International Conference on tral framework for mining multi-source anomalies, in: Graph Embedding for Machine Learning, 2018, pp. 4390–4399. Pattern Analysis, Springer, 2013, pp. 205–228. [14] Y. Liu, Z. Li, C. Zhou, Y. Jiang, J. Sun, M. Wang, X. He, Generative adversarial ac- [36] H. Zhao, Y. Fu, Dual-regularized multi-view outlier detection, in: Proceedings tive learning for unsupervised outlier detection, CoRR, arXiv:1809.10816, 2018. of the 24th International Conference on Artificial Intelligence, IJCAI’15, AAAI [15] A. Deng, B. Hooi, Graph neural network-based anomaly detection in multi- Press, 2015, pp. 4077–4083. variate time series, in: Proceedings of the AAAI Conference on Artificial In- [37] R. Cazabet, F. Amblard, C. Hanachi, Detection of overlapping communities in telligence 35 (5) (2021) 4027–4035, https://ojs.aaai.org/index.php/AAAI/article/ dynamical social networks, in: IEEE 2nd International Conference on Social view/16523. Computing, 2010, pp. 309–314. [16] J. Li, H. Izakian, W. Pedrycz, I. Jamal, Clustering-based anomaly detec- [38] K.S. Xu, M. Kliger, A.O. Hero, Tracking communities in dynamic social net- tion in multivariate time series data, Appl. Soft Comput. 100 (2021) works, in: J. Salerno, S.J. Yang, D. Nau, S.-K. Chai (Eds.), Social Computing, 106919, https://doi.org/10.1016/j.asoc.2020.106919, https://www.sciencedirect. Behavioral-Cultural Modeling and Prediction, Springer Berlin Heidelberg, Berlin, com/science/article/pii/S1568494620308577. Heidelberg, 2011, pp. 219–226. [17] M. Ester, H.-P. Kriegel, J. Sander, X. Xu, A Density-Based Algorithm for Dis- [39] V. Sekara, A. Stopczynski, S. Lehmann, Fundamental structures of dynamic so- covering Clusters in Large Spatial Databases with Noise, AAAI Press, 1996, cial networks, Proc. Natl. Acad. Sci. 113 (36) (2016) 9977–9982. pp. 226–231. [40] G. Rossetti, Exorcising the demon: angel, efficient node-centric community dis- [18] S. Ramaswamy, R. Rastogi, K. Shim, Efficient algorithms for mining outliers covery, in: International Conference on Complex Networks and Their Applica- from large data sets, SIGMOD Rec. 29 (2) (2000) 427–438. tions, Springer, 2019. [19] F. Angiulli, C. Pizzuti, Fast outlier detection in high dimensional spaces, in: T. [41] A. Choumane, A. Awada, A. Harkous, Core expansion: a new community detec- Elomaa, H. Mannila, H. Toivonen (Eds.), Principles of Data Mining and Knowl- tion algorithm based on neighborhood overlap, Soc. Netw. Anal. Min. 10 (12) edge Discovery, Springer Berlin Heidelberg, Berlin, Heidelberg, 2002, pp. 15–27. (2020), https://doi.org/10.1007/s13278-020-00647-6. [20] M.M. Breunig, H.-P. Kriegel, R.T. Ng, J. Sander, Lof: identifying density-based [42] F. Ye, C. Chen, Z. Zheng, Deep autoencoder-like nonnegative matrix factoriza- local outliers, in: Proceedings of the 2000 ACM SIGMOD International Confer- tion for community detection, in: Proceedings of the 27th ACM International ence on Management of Data, SIGMOD ’00, ACM, New York, NY, USA, 2000, Conference on Information and Knowledge Management, CIKM ’18, Association pp. 93–104. for Computing Machinery, New York, NY, USA, 2018, pp. 1393–1402. [21] S. Papadimitriou, H. Kitagawa, P.B. Gibbons, C. Faloutsos, LOCI: fast outlier de- [43] A.M. Alvarez, M. Yamada, A. Kimura, T. Iwata, Clustering-based in multi-view tection using the local correlation integral, in: Proceedings 19th International data, in: ACM Int. Conf. Conf. Inf. Knowl. Manage, 2013. Conference on Data Engineering (Cat. No. 03CH37405), 2003, pp. 315–326. [44] S. Li, M. Shao, Y. Fu, Multi-view low-rank analysis for outlier detection, in: [22] F.T. Liu, K.M. Ting, Z.-H. Zhou, Isolation-based anomaly detection, ACM Trans. SIAM Int. Conf. Data Mining, 2015. Knowl. Discov. Data 6 (1) (mar 2012). [45] M.J. Huiskes, M.S. Lew, The MIR Flickr retrieval evaluation, in: MIR ’08: Pro- [23] X. Ma, J. Wu, S. Xue, J. Yang, C. Zhou, Q.Z. Sheng, H. Xiong, L. Akoglu, A com- ceedings of the 2008 ACM International Conference on Multimedia Information prehensive survey on graph anomaly detection with deep learning, IEEE Trans. Retrieval, ACM, 2008. Knowl. Data Eng. (2021) 1, https://doi.org/10.1109/TKDE.2021.3118815. [46] S. Fortunato, Community detection in graphs, Phys. Rep. 486 (3–5) (2010) [24] M.R. Brito, E.L. Chávez, A.J. Quiroz, J.E. Yukich, Connectivity of the mutual k- 75–174 nearest-neighbor graph in clustering and outlier detection, Stat. Probab. Lett. . 35 (1) (1997) 33–42. [25] M. Maier, M. Hein, U. von Luxburg, Cluster identification in nearest-neighbor graphs, in: M. Hutter, R.A. Servedio, E. Takimoto (Eds.), Algorithmic Learning Theory, Springer Berlin Heidelberg, Berlin, Heidelberg, 2007, pp. 196–210. 10