It is supposed that Dr is the set of predefined dependency relationships, and D′r is the set of opposite dependency relationships for Dr. The labels for a dependency relationship and its opposite dependency relationship may be different. For example, if the dependency relationship is labeled as “subj,” then the opposite dependency relationship may be labeled as “subj_opposite.” Two directed edges in the edge set ε of the sentence graph 512 connecting the i-th node and the j-th node may be represented as eij=(vi, vj, dij):dij∈Dr and eij=(vj, vi, d′ij), where dij is the dependency relationship from the word vj to the word vi, and d′ij is an opposite of the dependency relationship dij from the word vi to the word vj.
It would be appreciated that in generation of the sentence graph 512, if it is determined that there is a dependency relationship between two words, the graph generation module 510 may add either one directed edge to indicate the dependency relationship or one directed edge to indicate the opposite dependency relationship. In some other embodiments, the graph generation module 510 may also add both of the directed edges in the sentence graph 512.