Novel Graph Signature Extraction Techniques on Recognizing Textual Entailment and Natural Language Processing

This is a multidisciplinary project that involves complex networks, graph theoretic, linguistic structural analysis, network structure identifications and combinatorial optimizations. In this project, novel network analysis techniques will be adopted to linguistic studies especially on the alignment task in Recognizing Textual Entailment (RTE) systems. This alignment task will be converted into network comparison/graph matching problems; and these problems can then be converted into combinatorial optimization problems; such as general quadratic assignment problems, or general covering problems and they are NP-hard; but via relaxation procedures, they are solvable with good computable speed and size.Also, in this project we proposed to use a network invariant metric namely a network signature to solve the identification/characterization problem. Network invariant metrics are metric of network that is independent of node labeling. By making use of this special metric, the network comparison/graph matching no longer require the time consuming permutation/mapping of nodes and hence could yield an approximate solution. The improved RTE system will be applied onto different domain for applications.