Xiaofeng Zhou Multiple web-scale knowledge bases (e.g., Freebase, YAGO, NELL) have been constructed using semi-supervised or unsupervised information extraction techniques and many of them, despite their large sizes, are continuously growing. Much research effort has been put into mining inference rules from these knowledge bases. To address the task of rule mining over evolving web-scale knowledge bases,