Graph Mining Meets Crowdsourcing: Extracting Experts for Answer Aggregation

1 Introduction

Crowdsourcing, which has become popular in recent years, is a process that requires completion of specific tasks by crowd workers. In crowdsourced single-answer multiplechoice questions, workers are asked to select one answer out of multiple candidates for each given question. Such a scheme is used, for instance, in annotating named entities for microblogs [Finin et al., 2010], sentiment classification on political blogs [Hsueh et al., 2009], and image tagging [Lin et al., 2015].

For the purpose of quality control, crowdsourcing systems usually assign multiple workers to the same questions and then aggregate their answers using some rule or algorithm. A critical fact here is that the workers often have different levels of expertise, skills, and motivation; some workers may guess the correct answers with their rich knowledge, while others may answer almost randomly to get a reward without any effort. Let us call the workers of the former and latter type experts and non-experts, respectively.

When only a few experts are overwhelmed by a large number of non-experts, the most intuitive answer aggregation rule, majority voting, often fails to acquire the correct answers. Consider a small example in Table 1. There are six workers w1, . . . ,w6 assigned to eight questions q1, . . . , q8. For each question, the candidate answers are A, B, C, D, and E. Among these workers, w1, w2, and w3 are experts who almost always give the correct answers, while the others, w4, w5, and w6, are non-experts who give random answers. Let us apply the majority voting to their answers. The majority answer for q1 is D, which is the correct answer. However, the majority answer for q8 is C, which is not the correct answer. In addition, we need tie-breaking for q3 because B and D get the same number of votes. It is very likely that as the fraction of non-experts increases, the quality of the majority voting answers deteriorates.

Various answer aggregation algorithms exist in addition to the majority voting (see Related Work). However, most of these algorithms implicitly strengthen the majority answers and therefore fail to provide the true answers when the majority answers are incorrect. To overcome this issue, Li et al. [2017] recently proposed a sophisticated answer aggregation algorithm for such a hard situation. More specifically, they introduced the notion of hyper questions, each of which is a set of single questions. Their algorithm applies the majority voting (or other existing answer aggregation algorithms) for the hyper questions and then decodes the results to votes on individual questions. Finally, it applies the majority voting again to obtain the final answers. The results of their experiments demonstrate that their algorithm outperforms existing algorithms.

1.1 Our Contribution

In this study, we further investigate the above-mentioned hard situation. Our contribution can be summarized as follows:

1. We introduce a graph-mining-based efficient algorithm that accurately extracts the set of experts;
2. We propose two types of answer aggregation algorithms based on the above experts extraction algorithm;
3. We provide a theoretical justification of our proposed algorithms;
4. We conduct thorough computational experiments using synthetic and real-world datasets to evaluate the performance of our proposed algorithms.

First result. To design a powerful answer aggregation algorithm for the above hard situation, it is crucial to extract reliable experts from the crowd workers. In the example above, if we recognize that w1, w2, and w3 are experts, we can obtain the correct answers for all questions by simply applying the majority voting to the answers of the experts. The fundamental observation we use is as follows: as the experts almost always give the correct answers, each pair of experts frequently gives the same answer to a question. Let us now consider constructing an edge-weighted complete undirected graph in which each vertex corresponds to a worker and each edge weight represents the agreement rate of the answers of two workers. From the above observation, it is very likely that there is a dense component consisting of the experts, which we call the expert core. Note that the formal definition of the expert core will be given in Section 2. Figure 1 depicts an edge-weighted graph constructed from the example in Table 1. As can be seen, experts w1, w2, and w3 form a dense component. Although, in this example, we simply set the edge weight to the number of same answers of two workers, we will use more suitable values in our algorithm. To extract the expert core, we use a well-known dense subgraph extraction algorithm called the peeling algorithm [Asahiro et al., 2000], which removes the most unreliable worker one by one.

Second result. Based on the expert core extraction algorithm, we propose two types of answer aggregation algorithms. The first one incorporates the expert core into existing answer aggregation algorithms such as the majority voting. Indeed, once we extract the expert core, we can apply existing algorithms to the answers of the workers in the expert core. The second one utilizes the information pertaining to the reliability of workers provided by the expert core extraction algorithm, which is quite effective when the task is very hard.

Third result. We first demonstrate that the expert core is very unlikely to contain a non-expert if the number of questions is sufficiently large (Theorem 2). We then prove that the majority voting is asymptotically correct if there are only experts (Theorem 3), but not reliable if there are a large number of non-experts (Theorem 4). Theorems 2 and 3 provide a theoretical justification for the first type of our algorithm. In fact, combining these two theorems, we see that if the number of questions and the number of workers in the expert core are sufficiently large, our proposed algorithm (i.e., the majority voting among the workers in the expert core) gives the correct answer with high probability. On the other hand, Theorem 4 provides the limitation of the majority voting, which implies that it is quite important to exclude non-experts when we use the majority voting.

Fourth result. We conduct thorough computational experiments using synthetic and real-world datasets to evaluate our proposed algorithms. To simulate the hard situation in this study, we use six datasets recently collected by Li et al. [2017] as real-world datasets, all of which have difficult heterogeneous-answer questions that require specialized knowledge. We demonstrate that the expert core counterparts of existing answer aggregation algorithms perform much better than their original versions. Furthermore, we show that our novel algorithm based on the information of the reliability of workers outperforms the other algorithms particularly when the task is quite hard.

1.2 RelatedWork

To date, a large body of work has been devoted to developing algorithms that estimate the quality of workers [Dawid and Skene, 1979; Whitehill et al., 2009; Welinder et al., 2010; Raykar et al., 2010; Karger et al., 2011; Wauthier and Jordan, 2011; Bachrach et al., 2012; Demartini et al., 2012; Kim and Ghahramani, 2012; Liu et al., 2012a; Liu et al., 2012b; Zhou et al., 2012; Aydin et al., 2014; Li et al., 2014b; Venanzi et al., 2014; Ma et al., 2015; Li et al., 2017; Zheng et al., 2017; Li et al., 2018]. In most existing work, the quality of workers and correct answers are estimated by an iterative approach comprising the following two steps: (i) infer the correct answers based on the quality of workers estimated and (ii) estimate the quality of workers based on the correct answers inferred. For example, Whitehill et al. [2009] modeled each worker's ability and each task's difficulty, and then designed a probabilistic approach, which they called GLAD (Generative model of Labels, Abilities, and Difficulties).

Finding a dense component in a graph is a fundamental and well-studied task in graph mining. A typical application of dense subgraph extraction is to identify components that have some special role or possess important functions in the underlying system represented by a graph.

Examples include communities or spam link farms extraction in Web graphs [Dourisboure et al., 2007; Gibson et al., 2005], identification of molecular complexes in proteinprotein interaction graphs [Bader and Hogue, 2003], and expert team formation in collaboration graphs [Tsourakakis et al., 2013], The peeling algorithm [Asahiro et al., 2000] is known to be effective in various optimization problems for dense subgraph extraction (e.g., the densest subgraph problem and its variations [Andersen and Chellapilla, 2009; Charikar, 2000; Kawase and Miyauchi, 2018; Miyauchi and Kakimura, 2018; Khuller and Saha, 2009] as well as other related problems [Tsourakakis et al., 2013; Miyauchi and Kawase, 2015]).

2 Model

An instance of our problem is a tuple (W,Q, C,L), where each component is defined as follows: There is a finite set of workers W = {w1, . . . , wn} and a finite set of questions Q = {q1, . . . , qm}. Each question q has a set of candidate answers Cq = {cq1 , . . . , cqs } (s ≥ 2). Suppose that, for each question q, worker w answers lwq ∈ Cq and let L = (lwq)w∈W, q∈Q. Our task is to estimate the unknown correct answers to the questions.

Suppose that, among the workers W = {w1, . . . ,wn}, there are nex experts E (⊆ W) who give the correct answer with probability pex (> 1/s), and the other nnon (= n-nex) workers are non-experts who give an answer independently and uniformly at random. If an expert makes a mistake, she selects a wrong answer independently and uniformly at random. Thus, for a question q ∈ Q with a correct answer aq ∈ Cq and an answer c ∈ Cq, it holds that

It should be noted that, by showing the candidate answers in random order for each worker, we can handle some biases (e.g., some non-expert workers always choose the first candidate of answers) using this model.

Let us consider the probability that a pair of workers u, v ∈ W (u ̸= v) gives the same answer for a question q ∈ Q. If at least one of u and v is a non-expert, then we have Pr[luq = lvq] = 1/s. On the other hand, if both workers are experts, then Pr[luq = lvq] = (pex-1/s)2 1-1/s + 1s , which is strictly larger than 1/s.

For each pair of workers u, v ∈ W, let τ(u, v) be the number of questions such that u and v give the same answer, that is, τ(u, v) = |{q ∈ Q : luq = lvq}|. Here, if Pr[luq = lvq] = p, then u and v give the same answers for at least τ (u, v) questions with probability ∑mi=τ (u,v) (mi )pi (1p)m-i .

For a given p ∈ (0, 1), a subset of workers W ⊆ W is called a θ-expert set with respect to p if

Input: Edge-weighted graph G = (V,E, ω) Output: S ⊆ V (k-core with maximum k) 1 S|V | ← V ; 2 for i ← |V |, . . . , 2 do 3 Find vi ∈ argminv∈Si dSi (v) and Si-1 ←Si \ {vi}; 4 return Si ∈ {S1, . . . , S|V |} that maximizes dSi (vi);

holds for all u ∈ W. Intuitively, a θ-expert set with small θ is a set of workers that is very unlikely to contain a nonexpert. Let θ(W) be the minimum threshold such that W is a θ-expert set, that is,

Then, we employ W ⊆ W that minimizes θ(W) as the estimated set of experts. We refer to such a set as the expert core (with respect to p). As will be shown in Theorem 2, the expert core is very unlikely to contain a non-expert if the number of questions is sufficiently large.

3 Algorithms

In this section, we design an algorithm to compute the expert core, and then propose two types of answer aggregation algorithms. Our expert core extraction algorithm first constructs an edge-weighted complete undirected graph that represents the similarity of the workers in terms of their answers. Then, it extracts a dense component in the graph using the peeling algorithm [Asahiro et al., 2000].

3.1 Peeling Algorithm

We first revisit the peeling algorithm. The algorithm iteratively removes a vertex with the minimum weighted degree in the current graph until we are left with only one vertex. Let G = (V,E, ω) be an edge-weighted graph. For S ⊆ V and v ∈ S, let dS(v) denote the weighted degree of v in the induced subgraph G[S], that is, dS(v) = ∑e={u,v}∈E: u∈S ω(e). Then, the procedure can be summarized in Algorithm 1. Note that the algorithm here returns Si ∈ {S1, . . . , S|V |} that maximizes dSi (vi), although there are other variants depending on the problem at hand [Charikar, 2000; Kawase and Miyauchi, 2018; Miyauchi and Kawase, 2015; Tsourakakis et al., 2013]. Algorithm 1 can be implemented to run in O(|E| + |V | log |V |) time.

Algorithm 1 indeed produces the k-core decomposition of graphs. For G = (V,E, ω) and a positive real k, a subset S ⊆ V is called a k-core if S is a maximal subset in which every vertex v ∈ S has a weighted degree of at least k in the induced subgraph G[S]. Note that a k-core is unique for a fixed k. The k-core decomposition reveals the hierarchical structure of k-cores in a graph and is particularly focused on finding the k-core with maximum k. Algorithm 1 is suitable for this scenario; in fact, it is evident that the algorithm returns the k-core with maximum k.

3.2 Expert Core Extraction Algorithm

Here, we present an algorithm to compute the expert core. In particular, we explain the construction of an edge-weighted graph, which represents the similarity of the workers in terms of their answers.

In our algorithm, we set p to the average agreement probability, that is,

where (W2 ) = {{u, v} : u, v ∈ W, u ̸= v}, and extract the expert core with respect to this p via the peeling algorithm. We construct a complete graph (W, (W2 )) with weight γ(u, v) = -log ∑mi=τ(u,v) (mi )pi (1 - p)m-i , where recall that τ(u, v) = |{q ∈ Q : luq = lvq}|. Then, we compute the k-core with maximum k for the edge-weighted graph (W, (W2 ), γ) using Algorithm 1. As a result, we can obtain a set of workers W ⊆ W such that the following value is maximized:

As -logx is monotone decreasing, the obtained set minimizes θ(W) and hence is the expert core.

Note that we can construct the edge-weighted graph (W, (W2 ), γ) in O(n2m) time and Algorithm 1 for the graph runs in O((n2 ) + n log n) = O(n2 ) time. Thus, we have the following theorem.

Theorem 1. The expert core can be found in O(n2m) time.

3.3 Answer Aggregation Algorithms

Once we extract the expert core, we can apply existing answer aggregation algorithms (e.g., the majority voting) to the answers of the workers in the expert core, which implies the expert core counterparts of the existing algorithms. In addition, we propose a novel answer aggregation algorithm. The peeling algorithm produces the ordering that represents the reliability of the workers. With this ordering, we can obtain a majority-voting-based algorithm as follows. At the beginning, we obtain the ordering of workers using the peeling algorithm for (W, (W2 ), γ). Then we pick the most reliable pair of workers, that is, the pair left until the second last round of the peeling algorithm. For each question, if the two workers select the same answer, then we employ this answer. If the two workers select different answers, then we add the next most reliable worker one by one according to the ordering until two of them give the same answer. Our algorithm, which we call Top-2, is summarized in Algorithm 2. Note that the algorithm runs in O(n2m) time, which is the same as that of the expert core extraction algorithm.

Input: Worker set W; Question set Q; Answer set L Output: Estimated true answers (zq)q∈Q 1 Calculate the average agreement probability p; 2 Construct the edge-weighted graph (W, (W2 ), γ); 3 Let S1, . . . , Sn be the sets computed in Algorithm 1; 4 for q ∈ Q do 5 for i ← 2, . . . , n do 6 if ∃c∗ ∈ Cq s.t. |{w ∈Wi : lwq = c∗ }| = 2 then zq ← c∗ and break ; 7 else if i = n then zq ← lwq, where {w} = S1 ; 8 return (zq)q∈Q;

4 Theoretical Results

In this section, we provide a theoretical justification for the first type of our proposed algorithm. Owing to space limitations, we omit the proofs, all of which can be found in the full version [Kawase et al., 2019]. Suppose that each worker gives answers according to the model described in Section 2.

The following theorem states that the expert core does not contain any non-expert with high probability if the number of questions is sufficiently large.

The next theorem states that the majority voting gives the correct answer with high probability if the number of workers is sufficiently large and all of them are experts. Let MVq be the output of the majority voting for question q ∈ Q.

Finally, the following theorem states that, the majority voting does not provide the correct answer with high probability if the number of non-experts is much larger than the number of experts.

Theorem 4. If nnon ≥ n2ex 2πϵ2 for ϵ > 0, then we have Pr [MVq = aq] ≤ 1 2 + ϵ (∀q ∈ Q).

It should be noted that when the number of candidate answers is 2, even the random choice gives the correct answer with probability 1/2. Thus, the above theorem indicates that the majority voting is no better than the random choice if the number of non-experts is much larger than the number of experts.

5 Experiments

In this section, we report the results of computational experiments. The objective of our experiments is to examine the performance of our proposed algorithms from various aspects using both synthetic and real-world datasets. The main component of our experiments comprises comparing our proposed answer aggregation algorithms with the following three existing algorithms: MV (the majority voting), GLAD [Whitehill et al., 2009], and Hyper-MV [Li et al.,

2017]. As our proposed algorithms, we employ the expert core counterparts of the above three algorithms, which we denote by Ex-MV, Ex-GLAD, and Ex-Hyper-MV, respectively, in addition to Top-2.

5.1 Datasets

As for synthetic datasets, we generate a variety of instances using the model described in Section 2. Recall the following five parameters: number of workers n = |W|, number of questions m = |Q|, number of candidate answers (for each question) s, number of ground-truth experts nex, and the probability pex that an expert gives the correct answer. Throughout the experiments, we set s = 5.

Table 2 summarizes six datasets that we use as real-world datasets. They were recently collected by Li et al. [2017] using Lancers, a commercial crowdsourcing platform in Japan. Consistent with the hard situation being addressed here, these datasets have difficult heterogeneous-answer questions that require specialized knowledge. In fact, as shown later, the majority voting performs poorly on these datasets. Note that the classical datasets used in other previous work (e.g., Bluebird and Dog in image tagging [Welinder et al., 2010; Zhou et al., 2012], Web in Web search relevance judging [Zhou et al., 2012], Price in product price estimation [Liu et al., 2013], and RTE and Temp in textual entailment recognition [Snow et al., 2008]) usually have relatively easy homogeneous-answer questions, which are not within the scope of this study. During the collection of the above six datasets, all workers were asked to answer all questions. This may not be the usual assumption in crowdsourcing but is effective in the current hard situation. Indeed, if we can identify reliable experts by asking all workers to answer a small number of questions at an early stage, then it is possible to ask only the identified experts to answer to the remaining questions, which may reduce the overall cost. This scenario has been studied in previous work [Li et al., 2017; Li et al., 2014a].

5.2 Experts Extraction

To evaluate the performance of our expert core extraction algorithm in terms of extracting reliable experts, we conducted simulations using synthetic datasets. We set the number of workers as n to 20 and the number of experts as nex to 4. In these settings, we generated two types of instances to simulate different situations. In the first type, to investigate the effect of the number of questions, we vary the number of questions m from 5 to 50 (in increments of 5) under a fixed value of pex = 0.8. In the second type, to investigate the effect of the expertise of workers, we vary the probability pex from 0.5 to 1.0 (in increments of 0.05) under a fixed value of m = 25.

As the sets of workers extracted by our peeling algorithm, we employ the Top-2 pair (i.e., a pair of workers left until the second last round of the peeling algorithm) and the expert core. To evaluate the quality of the set of workers at hand, we adopt the following two measures: the precision (number of ground-truth experts in the set divided by the size of the set) and the recall (number of ground-truth experts in the set divided by the number of all ground-truth experts).

The results are shown in Figure 2. Each point corresponds to an average over 100 data realizations. As can be seen, the precision of the expert core becomes better as the number of questions m or the probability pex increases. Moreover, the expert core is robust in terms of the recall; in fact, even when pex is small (i.e., pex ≤ 0.7), the expert core achieves an average recall of 0.8. The Top-2 pair achieves better precision in all parameter settings.

5.3 Ordering Defined by Peeling

The objective here is to demonstrate that the ordering of workers defined by the peeling algorithm for (W, (W2 ), γ) reflects the accuracy rate of the workers. To this end, we perform the peeling algorithm for the real-world datasets. The results are shown in Figure 3. In the subfigures, the horizontal axis represents the ordering of workers defined by the peeling algorithm; specifically, the peeling algorithm has removed the workers from right to left. The vertical axis represents the accuracy rate of the workers. The bars corresponding to the workers contained in the expert core are colored black, while those corresponding to the other workers are colored gray.

As can be seen, workers with smaller order tend to have higher accuracy rates, In addition, the expert core contains almost all workers with significantly high accuracy rates. which demonstrates the reliability of our peeling algorithm. In particular, for Pok´emon and Science, the ordering defined by the peeling algorithm correctly reproduces the ordering of the top five workers in terms of accuracy rates.

5.4 Comparison with Existing Algorithms

Using both synthetic and real-world datasets, we compare the performance of our proposed answer aggregation algorithms, that is, Top-2, Ex-MV, Ex-GLAD, and Ex-Hyper-MV, with existing algorithms, that is, MV, GLAD, and Hyper-MV. We first explain the details of GLAD and Hyper-MV. GLAD is a method that takes into account not only the worker expertise, denoted by α, but also the difficulty of each question, denoted by β, We set α ∼ N(1, 1) and β ∼ N(1, 1) as in Li et al. [2017]. It is known that GLAD runs in O(nmsT) time, where T is the number of iterations to converge. Hyper-MV is a method that applies the majority voting to the hyper questions rather than the original individual questions. Because the number of possible hyper questions may be too large, Li et al. [2017] suggested to apply the following random sampling procedure for r times: (i) shuffle the order of all single questions uniformly at random to generate a permutation and (ii) from this permutation, pick every k single questions from the beginning of the queue to generate hyper questions as long as they can be picked. Then, the overall time complexity of Hyper-MV is given by O(rmn). We performed the sampling procedure with k = 5 for r = 100 times, as suggested by Li et al. [2017].

Table 3 shows the results for synthetic datasets. We list the results for nine settings in which the probability pex varies in {0.7, 0.8, 0.9} and nex varies in {2, 4, 6}. We set the number of workers n to 100 and the number of questions m to

50. As can be seen, each expert core counterpart achieves better performance than the original algorithm. In particular, Ex-MV significantly improves the performance of MV. Top-2 outperforms the other algorithms particularly when the problem is quite difficult, although Ex-MV performs better when the problem is relatively easy.

Table 4 summarizes the results for the six real-world datasets. As can be seen, for all datasets except IT, our proposed algorithms achieve the best performance. In fact, for almost all datasets, the performance of the existing algorithms is improved by using the expert core. Among our proposed algorithms, Top-2 provides the best performance; in particular, for English and Science, the accuracy rate of Top-2 is even higher than those of the other algorithms. It should be noted that, for English, Medicine, and Science, the accuracy rate of Top-2 is strictly higher than the best accuracy rate among workers (presented in Table 2), which emphasizes the power of answer aggregation in crowdsourcing. According to the trend observed in synthetic datasets, it is very likely that the high performance of Top-2 stems from the high fraction of non-experts in real-world datasets.

6 Conclusion

In this study, we addressed the answer aggregation task in crowdsourcing. Specifically, we focused on a hard situation wherein a few experts are overwhelmed by a large number of non-experts. To design powerful answer aggregation algorithms for such situations, we introduced the notion of expert core, which is a set of workers that is very unlikely to contain a non-expert. We then designed a graph-mining-based efficient algorithm that exactly computes the expert core. Based on the expert core extraction algorithm, we proposed two types of answer aggregation algorithms. The first one incorporates the expert core into existing answer aggregation algorithms. The second one utilizes the information provided by the expert core extraction algorithm pertaining to the reliability of workers. In particular, we provided a theoretical justification for the first type of algorithm: if the number of questions and the number of workers in the expert-core are sufficiently large, our proposed algorithm gives the correct answer with high probability. Computational experiments using synthetic and real-world datasets demonstrated that our proposed answer aggregation algorithms outperform state-of-the-art algorithms.

There are several directions for future research. Our model assumes that all experts give the correct answer with the same probability and all non-experts give an answer independently and uniformly at random. However, in reality, experts themselves may have different levels of expertise and non-experts may not be completely random. Although we have already confirmed that our proposed algorithms work well on realworld datasets, it is interesting to extend our model to such a more general scenario. Another direction is to generalize our model in a higher-level perspective. This study has focused on crowdsourced closed-ended questions, where workers can select an answer from candidates. On the other hand, there are often cases where we wish to handle crowdsourced open-ended questions, where workers have to answer without any candidates. We believe that our proposed algorithms may be applicable to this more general scenario by introducing a measure of similarity of answers (and thus similarity of workers).

Acknowledgments

This work was partially supported by JST ACT-I Grant Number JPMJPR17U79 and JSPS KAKENHI Grant Numbers 16K16005, 17H07357, 18J23034, and 19K20218.