Abstract: As one of the most important problems in natural language processing, word sense disambiguation (WSD) aims to identify the intended meaning (sense) of words in context. Traditional knowledge-based WSD methods usually leverage only one sort of knowledge (semantic or co-occurrence relationships) but ignore the complementarity between different types for disambiguation. To deal with this problem, this paper proposes a novel WSD model using heterogeneous relation graph. Based on the reconstruction of traditional graph-based WSD model, different kinds of knowledge are naturally incorporated. Furthermore, since not all types of knowledge play an equally important role in WSD, an automatic parameter estimation method is designed and implemented to optimize the disambiguation effect by estimating the weight of various kinds of relations. The parameter estimation algorithm is adapted based on simulated annealing algorithm. The proposed WSD model is unsupervised. It can make full use of multi-source knowledge and alleviate the data sparseness and knowledge acquisition problems. The model is evaluated on a standard multilingual Chinese English lexical task (SemEval-2007), and the results indicate that the proposed method could significantly outperform the baseline method. Moreover, the proposed model also performs better than the best participating system in the evaluation.