Overlapping community finding with noisy pairwise constraints

Several types of prior knowledge have been used in semi-supervised strategies to guide the community detection process. The most widely-used approach has been to employ pairwise constraints, either must-link or cannot-link, which indicate that either two nodes must be in the same community or must be in different communities. This strategy has been implemented via several algorithms, including modularity-based methods (Li et al. 2014), spectral partitioning methods (Habashi et al. 2016; Zhang 2013), a spin-glass model (Eaton and Mansbach 2012), matrix factorization methods (Shi et al. 2015), and various other methods (Yang et al. 2017; Zhang et al. 2019). Such approaches have often provided significantly better results on benchmark data, when compared to standard unsupervised algorithms.

Other authors have used different kinds of prior knowledge to provide supervision for community detection. For instance, Ciglan and Nørvåg (2010) developed an algorithm for finding communities with size constraints, where the upper limit size of communities is given as a user-specified input. This algorithm is based on standard label propagation methods for finding disjoint communities. In Wu et al. (2016) an optimization algorithm based on density constraints was proposed. This algorithm constructs an initial skeleton of the community structure by maximizing a criterion function that incorporates constraints to only find communities with intra-cluster densities above a given threshold. The remaining nodes are subsequently classified with respect to this skeleton. Other algorithms have used node labels as prior knowledge to improve the performance of community detection, using an approach which resembles traditional training data in classification (Leng et al. 2013; Liu et al. 2014; Wang et al. 2015). Liu et al. (2015) developed a method that uses a semi-supervised label propagation algorithm based on node labels and negative information, where a node is deemed not to belong to a specific community.

The majority of algorithms in this area have been designed to only find non-overlapping communities, where each node can only belong to a single community. However, many real-world networks naturally contain overlapping community structure (Adamcsek et al. 2006). To the best of our knowledge, little work has been done in the context of finding overlapping communities from a semi-supervised perspective. Dreier et al. (2014) performed some initial work here, using supervision for the purpose of algorithm initialization. Specifically, a small set of seed nodes was selected, whose affinities to a community was provided as prior knowledge in order to infer the rest of the nodes’ affinities in the network. On the other hand, Shang et al. (2017) used an expansion method that classifies edges into communities, where this model is trained on set of predefined seeds. However, there is no external human supervision used during the seed selection or expansion processes. In contrast, for our study, we focus on the problem of semi-supervised community detection based on the external supervision by human who are part of the networks or domain experts, and encode it as pairwise constraints since they have proven to be effective in a range of other learning contexts (Basu et al. 2004c; Greene and Cunningham 2007).

Various algorithms have been proposed for the general task of pairwise constrained clustering, based on a variety of different clustering paradigms (e.g. Basu et al. 2004d; Davidson and Ravi 2005; Li et al. 2009). However, most assume the existence of “perfect” pairwise constraints which will be clean and will not contradict one another. Fewer studies have considered the requirement to handle noisy pairwise constraints. However, some relevant work in clustering has involved the development of new algorithms which are robust to noisy or conflicting pairwise constraints (Basu et al. 2004b; Coleman et al. 2008; Liu et al. 2007; Pelleg and Baras 2007). Other studies have introduced new metrics to assess the quality of constraints, considering aspects such as their informativeness and coherence (Davidson et al. 2006; Wagstaff et al. 2006). These can be used to filter or clean the pairwise constraints prior to clustering. A related study (Zhu et al. 2015) proposed an approach for handling noise by using a random forest classifier to identify incoherent constraints.

In contrast, in the field of semi-supervised community finding, the issue of noisy pairwise constraints has rarely been studied, and algorithms generally assume the veracity of any supervision supplied by an oracle. One related study from Li et al. (2014) initiated the work of handling “conflicting” pairwise constraints in non-overlapping community finding. That is, cases where (\(v_{i}, v_{j}\)) \(\in\) must-link, (\(v_{i}, v_{k}\)) \(\in\) must-link, and (\(v_{j}, v_{k}\)) \(\in\) cannot-link. Such cases of conflict were identified using a dissimilarity index metric to measure the reliability of constraint pairs. However, this type of constraint conflict is in fact legitimate in the context of overlapping communities, as shown in our previous work in Alghamdi and Greene (2018). Therefore, the challenge remains of handling noisy constraints for overlapping community finding in an appropriate manner, which we seek to address in the next section.

Before describing our proposed architecture, we first provide a formal definition for the pairwise constraints which are used in this study. These definitions map to those which are widely adopted in the wider semi-supervised learning literature (Chapelle et al. 2006). Given a set of nodes V in a network, we define two constraint types: As discussed in Alghamdi and Greene (2019), implementing pairwise constraints in the context of overlapping communities is challenging due to the lack of the transitive property for must-link constraints in the context of overlapping communities. In the case of non-overlapping communities, must-link constraints have a transitive property, where a third must-link relationship can be inferred from two other associated must-link constraint pairs. For instance, if (\(v_{i}, v_{j}\)) \(\in\) ML, and (\(v_{i}, v_{k}\)) \(\in\) ML, then we can also infer that (\(v_{j}, v_{k}\)) \(\in\) CL. This property does not hold for overlapping communities. For instance, node \(v_{i}\) might be an overlapping node and in this case there are two possible scenarios for the pair (\(v_{j}, v_{k}\)): (1) (\(v_{j}, v_{k}\)) \(\in\) CL where node \(v_{i}\) might be an overlapping node that have a must-link constraint with both \(v_{j}\) and \(v_{k}\), yet these two nodes could belong to two different communities; (2) (\(v_{j}, v_{k}\)) \(\in\) ML where all three nodes are in fact in the same community. This problem has been addressed in detail in Alghamdi and Greene (2019) and therefore is not the main focus of this paper.

Now we describe our proposed general architecture for semi-supervised community detection which incorporates a methodology to reduce the presence of noisy pairwise constraints using an outlier detection model, as illustrated in Fig. 1. This architecture begins with a set of noisy pairwise constraints provided by a human oracle (\(PC-\)). The set of noisy pairwise constraints (\(PC-\)) is composed of must-link (\(ML-\)) and cannot-link (\(CL-\)) constraints. These constraints are cleaned to produce a revised set of constraints (\(PC+\)) (composed of must-link (\(ML+\)) and cannot-link (\(CL+\)) constraints) which are fed into the community finding process. The proposed architecture consists of three distinct phases: In the following sections, we describe the details of the proposed architecture in terms of the outlier detection methods used to identify potentially-noisy constraints (Section “Outlier detection methods”), the different variations of the second phase of the architecture shown in Fig. 1 (see Section “Process for identifying noisy constraints”), and the implementation of the proposed architecture in the context of the AC-SLPA community finding algorithm (see Section “AC-SLPA with noise identification”).

Isolation Forests: This method, proposed by Liu et al. (2008), uses a tree-based ensemble strategy for anomaly detection. The assumption underlying this method is that anomalies will be isolated earlier in their trees as these examples are not only rare, but also have feature values substantially different from the normal data. Random partitions are used in order to separate examples, with the number of partitions acting as the path length. Because anomalous feature values are assumed to significantly differ from that of normal examples, these features will more easily split anomalous examples from normal examples early on in the tree, leading to a shorter path. This shortening effect is compounded by the fact that these examples are also assumed to be rare. In order to compute an anomaly score, the average path length over multiple trees is computed, and normalized by the average path length over all paths. Scores close to 1 are said to be anomalous and scores close to 0 are assumed normal. This algorithm fits the problem of noise detection when there are far fewer noisy labels than normal examples.

One-class SVM: One class Support Vector Machine (OCSVM) (Schölkopf et al. 2000, 2001) is a commonly-used method for anomaly detection which extends support vector algorithms to one-class classification. The reference to “one class” here refers to the assumption that primarily data from the normal class (i.e. non-outliers) will be modeled during training. First, data is transformed by a map \(\phi\) to a higher dimensional space by evaluating a kernel function. The algorithm then seeks to find the separating hyperplane in the kernel space between data and the origin with the largest margin. This is achieved by solving the following quadratic program for given training examples \({\pmb {x}}_1,{\pmb {x}}_2,\ldots ,{\pmb {x}}_l\):subject towhere w and p solve the problem. Here, \(\xi _i\) refers to the slack variable for a given example \({\pmb {x}}_i\) which softens the margin, allowing for some points to reside outside the margin, essentially relaxing the assumption of complete separability between normal and outlying data. The hyperparameter \(\nu \in (0,1)\) controls the number of outliers with smaller values allowing outliers to have a greater affect on the decision function. The decision function is given bywhere sgn(z) outputs a value of \(+1\) for \(z \geqslant 0\), indicating normal data and \(-1\) otherwise, indicating an outlier.

Local Outlier Factor: This method is based on the concept of local density in detecting outliers. Given a particular point p, we measure the density of p with respect to the density of its k nearest neighbors. Intuitively, if the local density of p is lower than the local densities of its neighbors, this indicates that p is an outlier. As discussed in Breunig et al. (2000), for a given neighborhood size k, the k-distance(p) for a point p is defined as the distance between p and its k-th neighbor o (i.e. the k-th closest point to p). The k-distance neighborhood \(N_k(p)\) is the set of points whose distances do not exceed the k-distance(p). The reachability distance is then defined as:This means that if p is o’s k-th nearest neighbor, this will be returned, otherwise, the true distance between p and o will be returned. In order to calculate the densities of different clusters of points, the “local reachability density” \(lrd_k\) is calculated.Finally, the local outlier factor (LOF) of point p is defined as:Autoencoders: An autoencoder (AE) represents a type of neural network architecture that attempts to reconstruct a given input in an effort to learn an informative latent feature representation. Formally, for an input vector x, an attempt is made to find a mapping from x to a reconstruction of itself \(x^\prime\) . By doing this, a latent representation of the data is created in the hidden layer(s) of the network. The general form of a single hidden layer autoencoder as follows:where f(x) is the encoder function for input x, g(z) is decoder function for encoding z, \(\sigma\) is a non-linear function, \(W^e\) and \(W^d\) are weight matrices for the encoder and decoder respectively and \(x ^\prime\) is the reconstruction of the input vector (Goodfellow et al. 2016).

These networks can use a “bottleneck” configuration where the hidden layer(s) of the network compress the data (Goodfellow et al. 2016). The network is trained by minimizing the mean squared error (MSE) between the reconstruction and input. as shown in formal (8):Additionally, autoencoders can be constrained to enforce sparsity in the network and therefore no longer require a compressed network capacity. One type of constrained autoencoder adds a sparsity penalty to hidden representations by constraining their absolute value. This penalty term is weighted and added to the cost function. The constrained cost is defined as.where \(\lambda\) is the sparsity penalty and \(h = f(x)\) (Goodfellow et al. 2016).

Autoencoders can be used in a number of capacities. In this work, we propose a number of techniques for noise detection from pairwise constraint sets which make use of autoencoders in different ways. Firstly, we show that autoencoders can be used as an effective outlier detection technique for noise detection in pairwise constraints. Secondly, we demonstrate that autoencoders can also be used as an embedding method to support other outlier detection methods in the identification of noisy constraints.

In this section, we describe a number of alternative cleaning processes for reducing noise in pairwise constraints, before passing them to a semi-supervised community detection algorithm. These cleaning processes employ some of the outlier detection models described in Section “Outlier detection methods”. It is important to note that pairwise constraints are of two distinct types: must-link and cannot-link. The differences in their respective distributions, which can be seen in Fig. 2, motivates the use of two separate cleaning processes and exploring different outlier detection models for each. The selection of models is based on best performance in detecting noises in constraints as illustrated in the evaluation section.

In this study, we explore the implementation of the following cleaning processes which are classified into four categories based on the employed outlier detection model: We see from Fig. 2 that the distributions of correct labels and noisy constraints is more complex in the case of cannot-link constraints—i.e., there is a high overlap between both the correct and noisy groups. Separating these groups requires a more complex function, as compared to the equivalent case for must-link constraints, which are relatively easy to separate.

Now we discuss the implementation of the general architecture discussed in Section “Overview” in the context of the existing AC-SLPA algorithm (Alghamdi and Greene 2018) in order to create a robust active semi-supervised SLPA algorithm that can handle the presence of noisy pairwise constraints. The new modified AC-SLPA consists of three stages. The first two stages include the pairwise constraints cleaning process, which are executed iteratively as follows:

Stage 1: Detecting noises in constraints during selection and annotation. At each iteration of AC-SLPA, informative pair of nodes are selected using Node Pair Selection method (Alghamdi and Greene 2019) and passed to the noisy oracle to be labelled as pairwise constraints. After generating a set of noisy pairwise constraints (\(PC-\)), this set is passed to the process of identifying noisy constraints for multiple sub-iterations of cleaning. As a new set of constraints is introduced at each iteration, the outlier detectors are retrained at each one of these iterations and reapplied to the remaining set of constraints. The output constraints of this process are then used to apply PC-SLPA algorithm. At the end of each run of AC-SLPA, the cleaned pairwise constraint set (\(PC+\)) is accumulated and mixed with the new chunk of noisy pairwise constraints (\(PC-\)) in the next iteration. The larger the constraints set passed to the outlier detection model, the better the performance.

Stage 2. Rechecking discarded pairwise constraints. The previous stage of cleaning may result in a number of non-noisy constraints being labelled as noisy. This is more likely to happen when the distribution of noisy constraints is highly overlapped with non-noisy constraints. The second stage is designed to recheck the discarded pairwise constraints set (\(PC-\)) that were potentially mislabelled as noises, by passing them to the process of identifying noisy constraints for another multiple iterations of cleaning, thus reducing any wastage of the annotation budget. The returned set of constraints from this process is added to the accumulated cleaned pairwise constraints set (\(PC+\)) from stage 1.

Stage 3. Apply PC-SLPA. The final stage involves applying the semi-supervised community detection process PC-SLPA using the final accumulated cleaned pairwise constraints (\(PC+\)) obtained from the previous two stages, thus producing a final set of communities. The complete architecture is summarized in Algorithm 1.

Synthetic data. We constructed a diverse set of 64 benchmark synthetic networks using the widely-used LFR generator (Lancichinetti et al. 2008). These networks vary in terms of number of nodes \(N \in [1000, 5000]\), communities per node (overlapping diversity) \(O_m \in [2,8]\), and the fraction of nodes belonging to multiple communities (overlapping density) \(On \in \{10\%,50\% \}\). These networks contain either small communities (\(10-50\) nodes), or large communities (\(20-100\) nodes). The mixing parameter \(\mu\) varies from 0.1 to 0.3, which controls the level of community overlap. Details of the network generation parameters are in Table 1.

Real-world data. We use three real-world networks which contain annotated ground truth overlapping communities. These are: (1) a co-purchasing network from Amazon.com; (2) a friendship network from YouTube; (3) a scientific collaboration network from DBLP. These networks have previously been used in the community finding literature (Leskovec and Krevl 2015). For each network, we include only the 5000 largest communities, as performed in Yang and Leskovec (2015). We then conduct a filtering process as per Harenberg et al. (2014). The remaining communities are ranked based on their internal densities and the bottom quartile is discarded, along with any duplicate communities. As an additional step, we remove extremely small communities. For the Amazon and YouTube networks, communities of size \(<5\) nodes are discarded, while for the DBLP network communities with \(<10\) nodes are discarded. Details of the final networks are summarized in Table 2.

Constraint noise. In all of our experiments we mimic the presence of an oracle by using pairwise node co-assignment information in the ground truth communities for each network. We use this information to create pairwise constraints, according to the definition of constraints given in Section “Overview”. We subsequently add noise to these constraints by flipping the labels of a randomly-selected subset of must-link and cannot-link pairs. The level of noise is fixed at \(10\%\) of the smallest constraint set, either must-link or cannot-link.

Evaluation metrics. To compare the ability of autoencoders variants to detect noisy constraints before their use in community finding, we calculate the AUC (Area Under the ROC Curve) over the reconstruction error. This provides an estimate of the number of constraints that were successfully detected in the absence of a threshold. After integrating this step into the community finding process, performance is assessed using the overlapping form of Normalized Mutual Information (NMI) (Lancichinetti et al. 2009), which has been widely adopted in the literature (Xie et al. 2013). For this measure, a value close to 1 indicates a high level of agreement with the ground truth communities, while a value close to 0 indicates that the communities generated by an algorithm are no better than random.

Several alternative validation metrics have been proposed in the literature to capture the topological properties of a network. These are used to assess the quality of a set of communities when no ground truth communities are available, and include metrics such as modularity (Newman 2004) and its overlapping counterpart (Lázár et al. 2010).

Some studies have suggested measuring the topological features of communities generated by an algorithm, and then comparing the outputs to the ground truth communities in the network (Dao et al. 2020; Orman et al. 2012). This can be seen as a complementary evaluation to the more widely-adopted external metrics. These approaches involve considering factors such as community size distributions, average distance between all pairs of nodes within a community, and scaled community density. Later in Section “Experiment 4: Real-world networks”, we consider the analysis of community size distributions to provide an additional evaluation perspective on our proposed approach.

In this experiment, the objective is to find the best models for detecting noisy constraints in must-link and cannot-link sets in Phase 2 (identifying noisy constraints) of the proposed general architecture in Fig. 1. As described in Section “Process for identifying noisy constraints”, there are four categories of cleaning processes that can be used in Phase 2. This experiment is designed to find the best model for each category. There are three main aspects of this experiment: This experiment is designed to assess the performance of Phase 2 detached from the general architecture in Fig. 1. Specifically, constraints are selected over 10 independent iterations of the existing AC-SLPA algorithm and then split into must-link and cannot-link sets to be processed separately.

Methodology. In the previous experiment, we focused on Phase 2 in Fig. 1 as a separate component. Now we evaluate the performance of the proposed architecture incorporating Phase 2. Given the best-performing outlier detection models and deep embedding functions identified in Experiment 1, we assess the performance of AC-SLPA community finding using each category of constraint cleaning process described in Section “Process for identifying noisy constraints” to identify the best option. Table 9 summarize the types of cleaning processes and models that are used in this experiment. Again we make use of 64 synthetic LFR networks.

Results. Tables 10 and 11 provide an overview of how the performance of AC-SLPA with various cleaning methods changes on synthetic networks. Recall that these networks vary in terms of mixing parameter \(\mu\), overlapping diversity \(O_m\), overlapping density \(O_n\), and the size of both the networks themselves and their ground truth communities. Each table entry includes the average NMI score of AC-SLPA combined with each cleaning methods (on the rows) over networks with specific parameters (on the columns). The best score is highlighted in bold. The detailed NMI scores are shown in Figs. 7 and 8, which indicate the agreement between the obtained communities in each case and the corresponding ground truth.

Generally, increasing the value of \(\mu\) results in lower NMI scores for all algorithms, due to the increased proportion of inter-community edges that lead to weakly-defined community structure. As can be seen from Tables 10 and 11, compared to the case of \(\mu =0.1\), the average NMI scores of all algorithms considerably decreased on small networks with \(\mu =0.3\). In both cases of \(\mu\), we can see that AC-SLPA with the Hybrid method outperformed other methods on small and large networks. As for examining the performance on networks with small and large communities, we can see that all algorithms show higher average NMI scores for small community networks compared to large community networks. In addition, we notice that AC-SLPA with the hybrid method shows the best performance on all networks, except for large networks with large communities.

Now we investigate the effect of two network properties, overlapping diversity \(O_m\) and overlapping density \(O_n\), on the performance of all algorithms. As we can see from Tables 10 and 11, the quality of obtained communities of all algorithms consistently decreases as the overlapping diversity and overlapping density increase. In most of the cases of \(O_m\) and \(O_n\), AC-SLPA with the Hybrid method outperform other methods except cases on \(O_n=10\%\) and \(O_m=4\) shows the second best scores after SVM_IF. Overall, in most cases of network parameters, the algorithms show higher average NMI scores on large networks compared to small networks, excluding AC-SLPA with AE method which shows a contrasting trend.

Table 12 summarizes the average ranks based on NMI scores for all algorithms on the synthetic networks. Each table entry shows the average rank of AC-SLPA with a cleaning method (on the columns) for different sizes of synthetic networks (on the rows). The average ranks based on NMI scores for each individual network is shown in Figs. 7 and 8. As we can see, AC-SLPA with the Hybrid method achieved the best rank on both small and large networks. The second-best algorithms with AE_SVM_IF method on small networks and with SVM_IF method on large networks. AE_SVM_IF and SVM_IF show approximately comparable performance on small networks, however the difference in performance between both methods grows higher on large networks.

To further understand the performance differences, we perform a Friedman aligned rank test with the Finner p value correction (García et al. 2010) to compare the above methods. The critical difference plots with a significance value \(\alpha = 0.05\) of the test results are shown in Fig. 9, where the vertical lines indicate the corresponding algorithm’s rank. The algorithms which are not connected with the black horizontal line are significantly different with the mentioned significance level. In the case of the small synthetic networks, the Hybrid method was found to be significantly better than the other three methods. On the other hand, for big networks, this method was found to be significantly better than AE_SVM_IF and AE.

Methodology. In the previous section, we compared different cleaning methods as they were integrated into the overall architecture as can be seen in Fig. 1. The best performing cleaning process identified was the Hybrid method. We term this overall architecture AC-SLPA with Hybrid cleaning. In the following sections, we compare this architecture to the baseline algorithms, SLPA and AC-SLPA, without any constraint cleaning on both small and large synthetic networks.

Results. We assess the quality of the obtained communities by AC-SLPA with hybrid (top-ranked cleaning process) compared to AC-SLPA and SLPA from the perspective of different network parameters as illustrated in Tables 13 and 14. The NMI scores of each network are reported in Figs. 10 and 11 on small and large networks respectively.

As can be seen from the Tables 13 and 14, AC-SLPA with Hybrid cleaning significantly outperformed other algorithms in most cases of networks parameters. For instance, in high mixing parameters large networks, AC-SLPA with the Hybrid method shows significantly higher score with NMI=0.530 compared to AC-SLPA and SLPA with NMI=0.343 and NMI=0.451 respectively. Similarly, AC-SLPA with the Hybrid method beats the other algorithms in most overlapping density (\(O_n\)) and overlapping diversity (\(O_m\)) cases, except on large networks with low overlapping density. SLPA shows slightly better average NMI score than AC-SLPA with cleaning process, with NMI=0.777 and NMI=0.768 respectively. In addition, we notice that the AC-SLPA with hybrid cleaning and SLPA show higher average NMI scores on large networks compared to small networks.

On the small networks, the performance of AC-SLPA without any cleaning process shows slightly better than SLPA in most cases. In contrast, the performance of AC-SLPA is significantly affected by noisy pairwise constraints on the large networks, where the average NMI score is consistently lower compared to SLPA. Overall, the best NMI scores across all algorithms are shown on networks with low overlapping density, as we might expect. For instance, we can see from Figs. 10 and 11 that the Hybrid method achieves higher NMI scores on most networks with low overlapping density compared to other algorithms, and the scores drop in high overlapping density case, in particular on small networks. On the large networks, the performance of the Hybrid method is considerably higher and more stable as the overlapping diversity increases, when compared to AC-SLPA and SLPA. Table 15 lists the average ranks of NMI scores of all algorithms on small and large networks, which shows the average ranks (lower values are better) of an algorithm (on the columns) over different size of synthetic networks (on the rows). The best scores are shown in boldface. As we see in Table 15, AC-SLPA with Hybrid cleaning method achieved the best rank score on both small and large networks, followed by SLPA on small networks and AC-SLPA on large networks.

As in Section “Experiment 2: Evaluation of noise removal methods”, we perform a Friedman aligned rank test with the Finner p value correction to support a multiple comparison test between the three methods above. The critical difference plots of the results with a significance level of \(\alpha = 0.05\) are shown in Fig. 12. In the case of both the small and large networks, the AC-SLPA with Hybrid method performed significantly better than the other two methods.

Methodology. We now discuss our final experiment on three real-world networks (Amazon, YouTube, DBLP). We use the same setup employed in Sections “Experiment 2: Evaluation of noise removal methods” and “Experiment 3: End-to-end evaluation” to examine the performance of each cleaning method after integration with AC-SLPA. Note that we employ the same models used with large synthetic networks, see Table 9. As baselines we consider AC-SLPA without cleaning (i.e. keeping noisy constraints), and the purely unsupervised algorithm SLPA. We also compare AC-SLPA with the best cleaning method to other baseline algorithms which are OSLOM (Lancichinetti et al. 2011), MOSES (McDaid and Hurley 2010), COPPRA (Adamcsek et al. 2006) on real-world networks in Table 20.

Results. Table 19 lists the NMI scores for each algorithm (columns) on each network (rows). The last row reports the average rank score of each algorithm. When comparing the performance of AC-SLPA with different cleaning methods to the baseline algorithms, we can see AC-SLPA with the Hybrid method achieves the best NMI scores on YouTube and DBLP networks (with NMI=0.818 and NMI=0.921 respectively). On the YouTube network, the performance of the AC-SLPA with Hybrid cleaning method increases significantly with a small amount of supervision. The next best performer is the AC-SLPA with the AE method, followed by SLPA and AC-SLPA with noisy pairwise constraints. All algorithms achieve their highest NMI scores on the YouTube dataset.

However, the cleaning methods fail to lead to any improvement over the baselines in the case of the Amazon network. After investigating these results in more detail, we notice two behaviors which frequently occur. Firstly, far more must-link constraints than cannot-link constraints are selected by AC-SLPA. For example, the number of must-link constraints often exceed 2,000 pairs, while the selected cannot-link constraint set can contain fewer than 100 pairs. Secondly, all of the noisy constraints are in the cannot-link set, and the number of incorrectly-labelled pairs exceeds the number of correctly-labelled pairs. This situation renders noisy detection almost impossible using most outlier detection methods.

Now we compare the performance of AC-SLPA with the Hybrid method to an additional set of baseline algorithms: OSLOM (Lancichinetti et al. 2011), MOSES (McDaid and Hurley 2010), and COPRA (Adamcsek et al. 2006). From the results shown in Table 20, we see that OSLOM achieves the highest NMI score on the Amazon network. However, AC-SLPA with Hybrid cleaning achieves the highest NMI score on the YouTube and DBLP networks. Table 20 also reports the average ranks for NMI scores across all algorithms on the real-world networks. This shows the average rank (lower values are better) of an algorithm (columns) over networks (rows). As can be seen, AC-SLPA with Hybrid cleaning achieved the best overall rank score, with SLPA and OSLOM next best.

Topological evaluation. Finally, we explore the obtained communities’ topological properties for the methods AC-SLPA with Hybrid cleaning, AC-SLPA with and without noisy constraints, and SLPA. Specifically, we look at the community size distributions, as shown in Figs. 13, 14, and 15. We compare the size distribution of the communities produced by each algorithm against the distribution for the ground truth communities for each network (i.e., the reference distribution). Since all of these algorithms include a random component and were run 10 times, we focus on the run with the highest NMI score in each case. To compare distributions, we use a two-sample Kolmogorov–Smirnov test (KS) (Massey 1951). This is a non-parametric statistical test to compare two cumulative distributions, which calculates the maximum difference between them. We can then compute a p value based on this maximum distance and the sample sizes. The null hypothesis is that both distributions are identical. This hypothesis is rejected when the p value is small (< 0.05), and the distance value is high.

Table 21 reports the KS results for all the algorithms on the real-world networks. We observe that the p values for all variants of AC-SLPA on the Amazon network indicate that their size distributions are the same as the reference distribution, unlike SLPA. In term of the distance values, we can see that the distribution for AC-SLPA without noisy constraints is closest to the reference distribution. On the YouTube network we observe that, according to the p values, all algorithms’ distributions are not the same as the reference. However, when we inspect the distance values, again AC-SLPA without noisy constraints has the lowest score. We can also see that using Hybrid method with AC-SLPA reduces the distance value significantly. The same observation also applies for the DBLP network, although the p value for AC-SLPA without noisy constraints on this network is above 0.05.

Overall, we see that the semi-supervised approaches can successfully identify heterogeneously-sized communities present in the real-world networks as illustrated in Figs. 13, 14, and 15. Also, we notice that using the Hybrid method with AC-SLPA reduces the difference between the obtained communities and the ground-truth communities in terms of their size distributions, which results from the presence of noisy constraints.