Patent ID: 8396884
Filing Date: 2013-03-12
Classification: G06F

Abstract:
1. A computer-implemented method for determining a significance of frequent subgraphs in a database graph comprising: (a) selecting one or more vertices or edges of a database graph as features using, as criteria for the selection, a frequency that a vertex or edge occurs in the database graph, a size of a vertex or edge in the database graph, a structural overlap between vertices or edges in the database graph, or a co-occurrence of vertices or edges in the database graph; (b) transforming the selected features into feature vectors, wherein each feature vector comprises a frequency of the selected features in the database graph; (c) evaluating the feature vectors by modeling a probability that the selected features occur in a random one of the feature vectors; and (d) determining a statistical significance of the feature vectors based on the evaluating step (c), by computing a probability of occurrence of the feature vectors in a random one of the features vector based on the modeled probability, and then obtaining a probability distribution on support of the features vector in a database of random vectors using the probability of occurrence.