Abstract
Crowdsourcing is an effective and efficient paradigm for obtaining labels for unlabeled corpus employing crowd workers. This work considers the budget allocation problem for a generalized setting on a graph of instances to be labeled where edges encode instance dependencies. Specifically, given a graph and a labeling budget, we propose an optimal policy to allocate the budget among the instances to maximize the overall labeling accuracy. We formulate the problem as a Bayesian Markov Decision Process (MDP), where we define our task as an optimization problem that maximizes the overall label accuracy under budget constraints. Then, we propose a novel stage-wise reward function that considers the effect of worker labels on the whole graph at each timestamp. This reward function is utilized to find an optimal policy for the optimization problem. Theoretically, we show that our proposed policies are consistent when the budget is infinite. We conduct extensive experiments on five real-world graph datasets and demonstrate the effectiveness of the proposed policies to achieve a higher label accuracy under budget constraints.
Introduction
Crowdsourcing has become a cornerstone for labeling large-scale datasets. However, it presents a significant challenge: non-expert workers are cost-effective but often provide noisy or incorrect labels. To ensure high data quality, multiple workers are typically assigned to the same "difficult" instances, which quickly exhausts limited budgets. Traditional budget allocation algorithms often treat data points as independent and identically distributed (i.i.d.), ignoring the inherent relationships between instances.
In many real-world scenarios, data is naturally structured as a graph—such as citation networks, social networks, or trust platforms. In these graphs, connected nodes often share similar characteristics, a phenomenon known as homophily. For example, in a citation network, a paper's topic is likely related to the topics of the papers it cites. Ignoring these dependencies leads to inefficient budget use, as labels for some nodes could be inferred from their neighbors. This research introduces GraphOBA (Graph-based Optimal Budget Allocation), a framework designed to maximize the labeling accuracy of an entire graph under a fixed budget by leveraging these structural dependencies.
Methodology
The core of GraphOBA is the formulation of the labeling task as a Bayesian Markov Decision Process (MDP). The framework consists of three primary pillars:
- Bayesian Modeling: The uncertainty of each node's label is modeled using a Beta distribution. These distributions are updated dynamically as new labels are received from crowd workers.
- Belief Propagation (BP): This is the critical mechanism for information sharing. When a node receives a label, GraphOBA uses BP to propagate this information throughout the graph. This updates the marginal probabilities of neighboring nodes, effectively "spreading" the knowledge gained from a single query.
- Stage-wise Reward Function: The framework employs a novel reward function that evaluates the expected global improvement in graph accuracy for each potential query. Instead of focusing on local gains, it selects nodes that offer the greatest reduction in overall uncertainty.
The authors propose two specific policies: GraphOBA-EXP, which maximizes the expected reward, and GraphOBA-OPT, an optimistic variant that targets nodes with the highest potential reward, similar to upper confidence bound strategies.
Experimental Setup
The effectiveness of GraphOBA was evaluated across five diverse real-world datasets, representing different domains and varying levels of homophily. These include citation networks (Cora, Citeseer, Pubmed), web page relationships (WebKB), and trust networks (Bitcoin).
Results and Discussion
The experimental results demonstrate that GraphOBA significantly outperforms traditional i.i.d. baselines like OPTKG and simple Uniform sampling.
Superior Accuracy and Efficiency
GraphOBA-EXP consistently achieved the highest accuracy across all datasets. The performance advantage is most pronounced when the budget is tight, indicating that the framework is highly efficient at identifying the most informative nodes to label early in the process. By labeling a central node or "hub," the Belief Propagation mechanism can drastically reduce uncertainty for many connected nodes simultaneously.
The Power of Information Propagation
The experiments also showed that simply adding Belief Propagation to baseline methods (e.g., "Uniform+BP") significantly improved their performance. However, the GraphOBA policies still maintained a lead, proving that the strategic selection of nodes is just as vital as the propagation of their labels. Furthermore, the authors provide theoretical proofs showing that their policies are consistent; with an infinite budget, the labeling accuracy is guaranteed to converge to 100%.
Conclusion
GraphOBA represents a significant advancement in crowdsourced budget allocation by moving beyond the i.i.d. assumption. By integrating Belief Propagation into a Bayesian MDP framework, it achieves superior accuracy with fewer queries. While the computational complexity of BP poses a challenge for massive graphs, the use of sampling strategies makes the approach practical for many real-world applications. Future work may focus on optimizing these calculations for even larger scales and exploring more complex dependency structures.
Summary updated