The focus of this paper is the discovery of negative association rules. Such association rules are complementary to the sorts of association rules most often encountered in literatures and have the forms of X \rightarrow \neg Y or \neg X \rightarrow Y. We present a rule discovery algorithm that finds a useful subset of valid negative rules. In generating negative rules, we employ a hierarchical graph-structured taxonomy of domain terms. A taxonomy containing classification information records the similarity between items. Given the taxonomy, sibling rules, duplicated from positive rules with a couple items replaced, are derived together with their estimated confidence. Those sibling rules that bring big confidence deviation are considered candidate negative rules. Our study shows that negative association rules can be discovered efficiently from large database.