A few unsupervised metrics have been applied to automatic paraphrase identification and extraction<cite> (Barzilay & Lee, 2003</cite>; Dolan & Brockett, 2004) . However, these unsupervised methodologies show a major drawback by extracting quasi-exact 2 or even exact match pairs of sentences as they rely on classical string similarity measures such as the Edit Distance in the case of (Dolan & Brockett, 2004) and word N-gram overlap for<cite> (Barzilay & Lee, 2003)</cite> . Such pairs are clearly useless.