We present a new multi-class graph-based transduction algorithm. Examples are associated with nodes in an undirected weighted graph and edge weights measure similarity between examples. Typical algorithms in this setting perform label propagation between neighbours, ignoring the quality, or estimated quality, in the labeling of various nodes. We introduce an additional quantity of confidence in label assignments. Confidence information is learned jointly with the label assignments, while being used to dynamically tune the influence each node has on its neighbours during label propagation. We cast learning as a convex optimization problem, and derive an efficient iterative algorithm for solving it. Empirical evaluations on Natural Language Processing (NLP) and speech (TIMIT) data sets, with more than one million examples, demonstrate our algorithm improves over other state-of-the-art graph-based transduction algorithms.