Systems and methods for extracting patterns from graph and unstructered data

• US 8,738,361 B2
• Filed: 07/01/2009
• Issued: 05/27/2014
• Est. Priority Date: 07/01/2009
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gryc, Wojciech, Lawrence, Richard, Liu, Yan
• Primary Examiner(s): Armstrong, Angela A
• Application Number:
  US12/496,252
• Publication Number:
  US 20110004463A1
• Time in Patent Office: 1,791 Days
• Field of Search: None
• US Class Current: 704/9
• CPC Class Codes: G06F 40/20 Natural language analysis semantic analysis of natural language G06F40/30
• CPC Class Codes: G06F 40/258 Heading extraction; Automatic titling; Numbering
• CPC Class Codes: G06F 40/279 Recognition of textual entities
• CPC Class Codes: G06F 40/295 Named entity recognition

Abstract

A computing system receives input data having both graph and unstructured data and computes a current log likelihood of the input data. The computing system compares the current log likelihood with a previous log likelihood of the input data. If the current log likelihood is larger than the previous log likelihood, the computing system update topic modeling parameters, community modeling parameters, and the link generation parameter until the computing system obtains a maximal value of the log likelihood of the input data. Then, the computing system creates a graph indicating topic similarity between the input data based on the topic modeling parameters, creates another graph indicating community similarity between entities associated with the input data based on the community modeling parameters, and predicts a link existence between input data or entities based on the link generation parameter, the topic modeling parameter and the community modeling parameter.

Claims

1. A computer-implemented system for discovering communities, the system comprising:

a computer-implemented topic modeling module for receiving documents as inputs, extracting topics in the documents, and constructing a first graph representing content similarities between the documents, said constructing comprising generating values of two or more parameters for topic modeling;

a computer-implemented community modeling module for uncovering relationships between entities associated with the documents and constructing a second graph representing the relationships between entities, said constructing comprising generating values of two or more community modeling parameters; and

a computer-implemented link modeling module for communicating with the topic-modeling module and the community modeling module, and predicting whether an edge in the first graph will be formed based on the uncovered relationship, predicting whether an edge in the second graph will be formed based on the extracted topics, and constructing an entity relationship graph based on the first graph and the second graph,

wherein a community grouping for an entity is a variable hidden from a data collection process, said constructing said entity relationship graph comprising;

implementing a model that iterates until convergence;

estimating expected values of community hidden variables given current parameters for topic modeling and community modeling parameter;

updating values of said parameters for said topic modeling; and

updating values of said parameters for edge generation,

using said model for said edge predicting, wherein resulting edges of said entity relationship graph associated with an entity friendship or partnering relationship are distinguished from edges of said entity relationship graph associated with topic similarity.

2. A computer system for discovering a relationship between entities comprising:

a memory;

a processor in communications with the memory, wherein the computer system is configured for performing a method comprising;

receiving input data W representing a word vector matrix and input data G representing a link graph matrix having values that capture relationships amongst user or business entities;

computing a current log likelihood of the input data W and G, the current likelihood of the input data being a probability distribution function of topic modeling parameters and community modeling parameters, the parameters representing topic similarity between unstructured texts of the entities and the community modeling parameters represent community similarity between the entities;

comparing the current log likelihood of the input data and a previous log likelihood of the input data computed previously;

updating values of the parameters, if the current log likelihood is larger than the previous log likelihood;

repeating the comparing and the updating until the current log likelihood becomes less than or equal to the previous log likelihood; and

constructing at least one graph based on the updated values of the parameters, if the current log likelihood is less than or equal to the previous log likelihood, the at least one graph indicating the relationship between the entities.

3. The computer system according to claim 2, wherein the relationship comprises:

a partnership between the entities, a friendship between the entities, and a similarity between the entities.

4. The computer system according to claim 2, wherein the updating comprises:

estimating expected values of topic modeling parameters representing the topic similarity, the topic modeling parameters including α

, β

, θ

, wherein the α

represents a first prior probability matrix whose elements representing prior probabilities that unstructured texts of the entities is related to topics, the β

represents a topic representation matrix whose elements representing degrees that words in the unstructured texts represented by the document word matrix W is associated with the topics, and the θ

represents a document topic association matrix whose elements representing degrees that the unstructured texts of the entities are associated with the topics.

5. The computer system according to claim 4, wherein

the expected value of α

, E[α

], is estimated by computing ∫

α

P(α

)dα

, where P(α

) is a distribution of α

,

the expected values of β

, E[β

], is estimated by computing ∫

β

P(β

)dβ

, where P(β

) is a distribution of β

, and

the expected values of θ

, E[θ

] is estimated by computing ∫

θ

P(θ

)dθ

, where P(θ

) is a distribution of θ

.

6. The computer system according to claim 2, wherein the updating comprises:

estimating expected values of community modeling parameters representing the community similarity, the community modeling parameters including κ

, μ

, wherein the κ

represents a second prior probability matrix whose elements representing prior probabilities that entities belongs communities, and the μ

represents an entity community association matrix whose elements representing a degree that the entities associated with the communities.

7. The computer system according to claim 6, wherein

the expected value of κ

, E[κ

], is estimated by computing ∫

κ

P(κ

)dκ

, where P(κ

) is a distribution of κ

, and

the expected value of μ

, E[μ

], is estimated by computing ∫

μ

P(μ

)dμ

, where P(μ

) is a distribution of k.

8. The computer system according to claim 2, wherein the updating comprises:

calculating an optimal value of a link generation parameter, τ

.

9. The computer system according to claim 8, wherein the optimal value of the link generation parameter τ

is a value of τ

that maximize the log likelihood of the input data.

10. A computer readable medium embodying computer program instructions being executed by a processor for causing a computer to perform method steps for clustering entities, said medium not a propagating signal, said method steps comprising:

receiving documents as inputs, extracting topics in the documents, and constructing a first graph representing content similarities between the documents, said constructing comprising generating values of two or more parameters for topic modeling;

uncovering relationships between entities associated with the documents and constructing a second graph representing the relationships between entities, said constructing comprising generating values of two or more community modeling parameters; and

predicting whether an edge in the first graph will be formed based on the uncovered relationship, and predicting whether an edge in the second graph will be formed based on the extracted topics, and constructing an entity relationship graph based on the first graph and the second graph,

wherein a community grouping for an entity is a variable hidden from a data collection process, said constructing said entity relationship graph comprising;

implementing a model that iterates until convergence;

estimating expected values of community hidden variables given current parameters for topic modeling and community modeling parameter;

updating values of said parameters for said topic modeling; and

updating values of said parameters for edge generation,

using said model for said edge predicting, wherein resulting edges of said entity relationship graph associated with an entity friendship or partnering relationship are distinguished from edges of said entity relationship graph associated with topic similarity.

11. A computer program product comprising computer usable medium having computer readable program code means embodied therein for causing functions to cluster entities, said medium not a propagating signal, the computer program code means in said computer program product for causing a computer to perform a method comprising

receiving input data W representing a word vector matrix and input data G representing a link graph matrix having values that capture relationships amongst user or business entities;

computing a current log likelihood of the input data W and G, the current likelihood of the input data being a probability distribution function of topic modeling parameters and community modeling parameters, the parameters representing topic similarity between unstructured texts of the entities and the community modeling parameters represent community similarity between the entities;

comparing the current log likelihood of the input data and a previous log likelihood of the input data computed previously;

updating values of the parameters, if the current log likelihood is larger than the previous log likelihood;

repeating the comparing and the updating until the current log likelihood becomes less than or equal to the previous log likelihood; and

constructing at least one graph based on the updated values of the parameters, if the current log likelihood is less than or equal to the previous log likelihood, the at least one graph indicating the relationship between the entities.

12. The computer program product of claim 11, wherein said constructing at least one graph comprises:

constructing a first graph representing content similarities between the documents; and

constructing a second graph indicating said relationship between the entities associated with the documents, said method further comprising;

predicting whether an edge in the constructed first graph will be formed based on an uncovered relationship,

predicting whether an edge in the second graph will be formed based on extracted topics, and

constructing an entity relationship graph based the first graph and the second graphs.

13. The computer program product of claim 12, wherein weights of edges in said entity relationship graph that link between entities of different similarities are processed differently to uncover communities having community similarity.

14. The computer program product of claim 12, wherein the updating comprises:

calculating an optimal value of a link generation parameter τ

that determines a degree that community similarity and topic similarity contribute to an existence or non-existence of a link between an unstructured text i and an unstructured text j of the entities.