Locating paraphrases through utilization of a multipartite graph
First Claim
1. A method comprising the following computer-executable acts:
- receiving a selection of a first phrase in a first language;
executing a random walk over a computer-implemented multipartite graph, wherein a number of steps undertaken during the random walk is limited to a threshold number, wherein the multipartite graph comprises a first set of nodes that are representative of phrases in the first language, a second set of nodes that are representative of phrases in a second language, and edges between nodes that are representative of relationships between the respective phrases, and wherein the random walk comprises traversals over edges of the graph between nodes; and
indicating that a second phrase in the first language is a paraphrase of the first phrase based at least in part upon the random walk.
2 Assignments
0 Petitions
Accused Products
Abstract
A method is described herein that includes acts of receiving a selection of a first phrase in a first language and executing a random walk over a computer-implemented multipartite graph, wherein the multipartite-graph includes a first set of nodes that are representative of phrases in the first language, a second set of nodes that are representative of phrases in a second language, and edges between nodes that are representative of relationships between the respective phrases. The random walk includes traversals over edges of the graph between nodes. The method also includes the act of indicating that a second phrase in the first language is a paraphrase of the first phrase based at least in part upon the random walk.
-
Citations
20 Claims
-
1. A method comprising the following computer-executable acts:
-
receiving a selection of a first phrase in a first language; executing a random walk over a computer-implemented multipartite graph, wherein a number of steps undertaken during the random walk is limited to a threshold number, wherein the multipartite graph comprises a first set of nodes that are representative of phrases in the first language, a second set of nodes that are representative of phrases in a second language, and edges between nodes that are representative of relationships between the respective phrases, and wherein the random walk comprises traversals over edges of the graph between nodes; and indicating that a second phrase in the first language is a paraphrase of the first phrase based at least in part upon the random walk. - View Dependent Claims (2, 3, 5, 6, 7, 8, 9, 10, 11)
-
-
4. The method 1, further comprising:
-
receiving the first phrase as at least a portion of a query that is desirably input to a search engine; and responsive to receiving the first phrase, causing the search engine to display the second phrase as a suggested query.
-
-
12. A computing apparatus, comprising:
-
a processor; and a memory that comprises components that are executed by the processor, the components comprising; a random walk component that executes a random walk over a multipartite graph, wherein the multipartite graph comprises a first set of nodes that represent phrases in a first language, a second set of nodes that represent phrases in a second language, and edges between nodes in the first set of nodes and nodes in the second set of nodes, wherein an edge between two nodes indicates that phrases represented by the two nodes have a substantially similar semantic meaning, wherein the edges in the multipartite graph are weighted, and wherein the random walk component considers weights assigned to the edges when undertaking the random walk; and a paraphrase indicator component that outputs a ranked list of phrases in the first language that are found to be paraphrases of a first phrase in the first language based at least in part upon the random walk executed by the random walk component. - View Dependent Claims (13, 14, 15, 16, 17)
-
-
18. A computing device comprising a computer-readable medium, the computer-readable medium comprising instructions that, when executed by a processor, cause the processor to perform acts comprising:
-
executing a random walk over a computer-implemented multipartite graph, wherein the multipartite graph comprises; a first set of nodes that represent phrases in a first language; a second set of nodes that represent phrases in a second language; a third set of nodes that represent phrases in a third language; at least one feature node that represents a feature pertaining to phrases in the first language; and edges between nodes that represent relationships between nodes connected by the edges; wherein the random walk begins at a first node in the first set of nodes and travels over edges to other nodes in the multipartite graph; counting a number of steps in the random walk between the first node in the first set of nodes and a second node in the first set of nodes; and assigning a score to a phrase pair comprising a first phrase represented by the first node and a second phrase represented by the second node based at least in part upon the number of steps taken in the random walk between the first node and the second node, wherein the score is indicative of whether the second phrase is a paraphrase of the first phrase. - View Dependent Claims (19, 20)
-
Specification