Factor graph is a representative graphical model to handle uncertainty of random variables. Factor graph has been used in various application domains such as named entity recognition, social network analysis, and credibility evaluation. In this paper, we study the problem of reducing uncertainty in factor graph towards reaching a common truth or deterministic information. We propose a pay-as-you-go approach that leverages user feedback for uncertainty reduction. As the availability of human input is often limited, we develop techiniques to identify the most uncertain spots in factor graph for maximizing the benefits of a given user feedback. We demonstrate the efficiency of our techniques on real-world applications.