Summarized network graph for semantic similarity graphs of large corpora

• US 9,836,183 B1
• Filed: 09/14/2016
• Issued: 12/05/2017
• Est. Priority Date: 09/14/2016
• Status: Active Grant

• Current Assignee: Quid, Inc. (Netbase Quid)
• Original Assignee: Quid, Inc. (Netbase Quid)
• Inventors: Love, Oriana Jeannette, Lowe, Mary Kate, Tacchi, Ruggero Altair, Marrs, Alex
• Primary Examiner(s): Theriault, Steven B
• Application Number:
  US15/264,975
• Time in Patent Office: 447 Days
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: G06F 3/0481 based on specific properties of the displayed interaction object or a metaphor-based environment, e.g. interaction with desktop elements like windows or icons, or assisted by a cursor's changing behaviour or appearance
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

Provided is a process including: obtaining a clustered graph, the clustered graph having three or more clusters, each cluster having a plurality of nodes of the graph, the nodes being connected in pairs by one or more respective edges; determining visual attributes of cluster icons based on amounts of nodes in clusters corresponding to the respective cluster icons; determining positions of the cluster icons in a graphical visualization of the clustered graph; obtaining, for each cluster, a respective subset of nodes in the respective cluster; determining visual attributes of node icons based on attributes of corresponding nodes in the subsets of nodes, each node icon representing one of the nodes in the respective subset of nodes; determining positions of the node icons in the graphical visualization based on the positions of the corresponding cluster icons of clusters having the nodes corresponding to the respective node icons; and causing the graphical visualization to be displayed.

Claims

1. A tangible, non-transitory, machine-readable media storing instructions that when executed by one or more computers effectuate operations comprising:

obtaining, with one or more processors, a clustered graph, the clustered graph having three or more clusters, each cluster having a plurality of nodes of the graph, the nodes being connected in pairs by one or more respective edges, wherein obtaining the clustered graph comprises;

ingesting a corpus of documents via a network;

forming a graph of the documents, the graph having edges determined by ascertaining relationships between the documents based on unstructured natural language text in the documents; and

clustering the graph with a graph processing algorithm;

determining, with one or more processors, visual attributes of cluster icons based on amounts of nodes in clusters corresponding to the respective cluster icons;

determining, with one or more processors, positions of the cluster icons in a graphical visualization of the clustered graph;

obtaining, with one or more processors, for each cluster, a respective subset of nodes in the respective cluster by selecting representative or anomalous nodes in the respective cluster;

determining, with one or more processors, visual attributes of node icons based on attributes of corresponding nodes in the subsets of nodes, each node icon representing one of the nodes in the respective subset of nodes;

determining, with one or more processors, positions of the node icons in the graphical visualization based on the positions of the corresponding cluster icons of clusters having the nodes corresponding to the respective node icons; and

sending, via a network, with a server, instructions causing the graphical visualization to be displayed on display of a client computing device, wherein the graphical visualization concurrently displays;

a given cluster icon representing a given cluster among the three or more clusters; and

a representative node icon representing a first document within the given cluster and determined to be representative of documents within the given cluster and having a first position on the display determined relative to a second position of the given cluster icon;

or

an anomalous node icon representing a second document within the given cluster and determined to be anomalous relative to a distribution of documents within the given cluster and having a third position on the display determined relative to the second position of the given cluster icon.

2. The media of claim 1, wherein:

determining visual attributes of cluster icons comprises determining sizes of the cluster icons, the different cluster icons having different sizes corresponding to amounts of nodes in the corresponding clusters;

determining positions of the cluster icons comprises executing a simulation of a physical system in which objects corresponding to the cluster icons apply forces to one another and the forces depend on the distance there between in the graphical visualization;

obtaining, for each cluster, a respective subset of nodes comprises selecting nodes in response to determining the selected nodes have representative or anomalous attributes among the nodes in the respective cluster;

determining visual attributes of the node icons comprises determining sizes of the node icons based on the attributes that caused the node icons to be selected; and

determining positions of the node icons in the graphical visualization comprises executing a simulation of a physical system in which objects representing the node icons are repelled from one another and are attracted to objects representing the corresponding cluster icons.

3. The media of claim 1, wherein obtaining a clustered graph comprises obtaining a semantic similarity graph of documents based on semantic similarly of unstructured text in the documents by performing operations comprising:

determining a feature vector for each document, each feature vector having plurality of scores, each score corresponding to a given n-gram and being based on;

an amount of occurrences of the given n-gram in the respective document,

a length of the respective document,

an amount of occurrences of the given n-gram in a plurality of other documents different from the respective document, and

whether the given n-gram is among the set of n-grams pertaining to the selected topic; and

determining an adjacency matrix based on the feature vectors, wherein rows and columns of the adjacency matrix correspond to the documents, values of the feature matrix correspond to a selected-topic-adjusted semantic similarity of documents corresponding to the respective row and column of the values, and values of the feature matrix are based on angles between feature vectors of the documents corresponding to the respective row and column of the values, the operations comprising steps for reducing movement of data across a memory hierarchy.

4. The media of claim 1, wherein:

determining visual attributes of cluster icons comprises steps for determining visual attributes of cluster icons.

5. The media of claim 1, wherein:

determining visual attributes of cluster icons comprises determining an area of a cluster icon based on an amount of nodes in the corresponding cluster and a result of steps for scaling a visual attribute.

6. The media of claim 1, wherein:

determining positions of the cluster icons comprises approximating a solution to a combinatorial optimization problem in which a lower energy state is iteratively approached for a collection of bodies interacting with one another over distance with forces that are a function of pairwise distances.

7. The media of claim 1, wherein:

obtaining, for each cluster, a respective subset of nodes in the respective cluster comprises selecting nodes based on one or more of the following node attributes;

an amount of social sharing of an item represented by the node;

an amount of times an item represented by the node was republished;

an amount of times an item represented by the node was cited;

an amount of times an item represented by the node was commented upon;

a score indicating that the node bridges between topics in unstructured text represented by the nodes;

user ratings or reviews of items represented by the node; and

metrics of a business represented by the node.

8. The media of claim 1, wherein:

determining visual attributes of node icons comprises determining a spatial dimension of the icon based on magnitudes of attributes of the nodes represented by the icons and normalizing the magnitudes among a plurality of nodes.

9. The media of claim 1, wherein:

the cluster icons are circles and the node icons are circles adjacent the corresponding cluster icons.

10. The media of claim 1, wherein:

the graphical visualization is configured to receive a user selection of a cluster icon and a request to break-up the cluster corresponding to the selected cluster icon and respond by performing operations comprising;

obtaining a clustering of nodes in the selected cluster, the clustering yielding a division of the selected cluster into a plurality of new clusters;

determining visual attributes and positions of new cluster icons corresponding to the plurality of clusters yielded by the division and clustering of the selected cluster;

obtaining a subsets of nodes of the new clusters; and

determining visual attributes and positions of new node icons corresponding to the subsets of nodes of the new clusters.

11. The media of claim 1, wherein:

the graphical visualization is configured to receive a user selection of first and second cluster icons and respond to the selection by performing operations comprising;

merging clusters corresponding to the first and second cluster icons;

determining a new subset of nodes in the merged cluster based on attributes of the nodes;

determining a position and a visual attribute of a new cluster icon corresponding to the merged clusters;

determine positions and visual attributes of node icons corresponding to the new subset.

12. The media of claim 11, wherein receiving a user selection comprises:

receiving a drag-and-drop even with an event handler of the graphical visualization.

13. The media of claim 1, wherein:

visual elements of the graphical visualization link a subset of pairwise combinations of the cluster icons; and

for a given cluster icon, a given node icon associated with the given cluster icon is positioned within the graphical visualization based on a position of a visual element linking the given cluster icon to another cluster icon.

14. The media of claim 13, wherein:

the given node icon corresponds to a document including in natural language text a topic addressed in the cluster corresponding to the other cluster icon, the topic being determined with steps for determining topics of unstructured text; and

the given node icon at least partially overlaps with the visual element.

15. The media of claim 1, wherein:

the nodes are associated with respective dates; and

the graphical visualization includes a histogram of a time-series of the node dates.

16. The media of claim 15, wherein:

the graphical visualization is configured to receive a user selection of a cluster icon and respond by adjusting the histogram of the time series to include a histogram of a time series of node dates of nodes in the cluster corresponding to the selected cluster icon, such that a contribution of the selected cluster to the time-series is distinguished from contributions from nodes of un-selected clusters.

17. The media of claim 1, wherein:

the graph contains more than 1000 nodes and more than 2000 edges;

the clustered graph contains more than 10 clusters;

the subsets of nodes are less than 20 for each cluster.

18. The media of claim 1, wherein:

determining positions of the cluster icons comprises steps for determining positions of cluster icons;

obtaining, for each cluster, a respective subset of nodes in the respective cluster comprises steps for selecting representative or anomalous nodes of a cluster;

determining positions of the node icons comprises steps for determining positions of node icons; and

causing the graphical visualization to be displayed comprises steps for causing graphical visualizations to be displayed.

19. The media of claim 1, wherein:

obtaining a clustered graph comprises analyzing relationships between a plurality of entities.

20. The media of claim 1, wherein determining positions of the node icons in the graphical visualization comprises:

obtaining attributes of the nodes corresponding to the node icons; and

positioning the node icons around a corresponding cluster such that resulting positions indicate relative values of the attributes.

21. The media of claim 20, wherein positioning the node icons around a corresponding cluster comprises positioning the node icons at angles determined based on ages of the nodes corresponding to the node icons.

23. The method of claim 1, wherein clustering the graph with a graph processing algorithm comprises:

randomly traversing the graph by choosing edges with probabilities based on respective edge weights of the respective edges;

forming a transition probability matrix based on the traversing, the transition probability matrix indicating a probability of traveling from one node to another node in the graph;

normalizing the transition probability matrix;

iteratively expanding and inflating the matrix until the matrix converges; and

ascertaining clusters according to positive values along rows of the converged matrix.

24. The method of claim 1, the operations comprising, for the given cluster:

identifying a high-side anomalous document by determining the high-side anomalous document is an outlier on a high side of a distribution of attributes values;

identifying a low-side anomalous document by determining the low-side anomalous document is an outlier on a low side of a distribution of attributes values; and

instructing the client computing device, via the network, to graphically represent low-side anomalous document and the high-side anomalous document differently in the user interface.

25. The method of claim 1, wherein:

selecting representative or anomalous nodes in the respective cluster comprises selecting representative nodes in the respective cluster and selecting anomalous nodes in the respective cluster; and

the sent instructions cause the client computing device to display both the representative node icon in spaced relation to the given cluster icon in the user interface and the anomalous node icon in spaced relation to the given cluster icon in the user interface.

26. The method of claim 1, wherein:

selecting representative or anomalous nodes in the respective cluster comprises selecting representative or anomalous nodes based on an interaction between two or more attributes of a respective node.

27. The method of claim 1, wherein:

selecting representative or anomalous nodes in the respective cluster comprises, for each node in the given cluster, forming a respective attribute vector having a plurality of dimensions; and

for the nodes in the given cluster, executing a density based clustering algorithm on the attribute vectors of the nodes in the given cluster and determining which nodes in the given cluster are designated as outlier nodes by the density based clustering algorithm.

22. A method, comprising:

obtaining, with one or more processors, a clustered graph, the clustered graph having three or more clusters, each cluster having a plurality of nodes of the graph, the nodes being connected in pairs by one or more respective edges, wherein obtaining the clustered graph comprises;

ingesting a corpus of documents via a network;

forming a graph of the documents, the graph having edges determined by ascertaining relationships between the documents based on unstructured natural language text in the documents; and

clustering the graph with a graph processing algorithm;

determining, with one or more processors, visual attributes of cluster icons based on amounts of nodes in clusters corresponding to the respective cluster icons;

determining, with one or more processors, positions of the cluster icons in a graphical visualization of the clustered graph;

obtaining, with one or more processors, for each cluster, a respective subset of nodes in the respective cluster;

determining, with one or more processors, visual attributes of node icons based on attributes of corresponding nodes in the subsets of nodes, each node icon representing one of the nodes in the respective subset of nodes;

determining, with one or more processors, positions of the node icons in the graphical visualization based on the positions of the corresponding cluster icons of clusters having the nodes corresponding to the respective node icons; and

sending, via a network, with a server, instructions causing the graphical visualization to be displayed on display of a client computing device, wherein the graphical visualization concurrently displays;

a given cluster icon representing a given cluster among the three or more clusters; and

a representative node icon representing a first document within the given cluster and determined to be representative of documents within the given cluster and having a first position on the display determined relative to a second position of the given cluster icon;

or

an anomalous node icon representing a second document within the given cluster and determined to be anomalous relative to a distribution of documents within the given cluster and having a third position on the display determined relative to the second position of the given cluster icon.