Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-11195312-B1
Publication Date
2021-12-07
Expiration Date
Abstract
A graph processing system, method and apparatus classifies graphs based on a linearly computable set of features defined as a feature vector adapted for comparison with the feature vectors of other graphs. The features result from graph statistics (“gragnostics”) computable from the edges and vertices of a set of graphs. Graphs are classified based on a multidimensional distance of the resulting feature vectors, and similar graphs are classified according to a distance, or nearest neighbor, of the feature vector corresponding to each graph. Projection of the feature vector onto two dimensions allows visualization of the classification, as similar graphs appear as clusters or groups separated by a relatively shorter distance. Different types or classifications of graphs also appear as other, more distant, clusters. An initial training set defines the classification types, and sampled graphs are evaluated and classified based on the feature vector and nearest neighbors in the training set.
Core Innovation
A scalable method renders graph data for visual recognition and comparison of statistical trends defined in a plurality of graphs. Each graph is provided as associations between data entities and is rendered in a visual form having a plurality of vertices connected by one or more edges. For each graph, the method computes a plurality of features based on the edges and vertices and derives similarity across graphs using the computed features.
The method computes each feature value in linear computability time based on a number of edges or a number of vertices of each respective graph independently of reference to any other graphs. The computed feature values are normalized into a predetermined range and arranged into a feature vector whose ordering specifies the features. The ordered feature values include a tree feature computed in linear time by traversing vertices, accumulating a number of edges, determining a number of edges whose removal would result in a tree by removing cyclic paths, and comparing the determined number of edges with the traversed vertices.
The method computes a multidimensional distance between each of the feature vectors to determine similarity between graphs and computes a two-dimensional position for each feature vector based on a projection of the computed multidimensional distance. It renders a two-dimensional visualization by displaying the computed two-dimensional position of each feature vector, where the two-dimensional visualization depicts clusters of closely located sets of points, and each point defines a projection of a multidimensional value defined by the corresponding graph and feature vector.
Claims Coverage
Two independent claims are described: one centered on a tree feature computed in linear time and one centered on a linearity feature computed in linear time. Both independent claims include per-graph linear-time feature computation independent of other graphs, normalization into a predetermined range, feature-vector construction, multidimensional distance for similarity, projection to a two-dimensional position, and rendering a clustered two-dimensional visualization.
Linear-time feature-vector rendering for graph similarity
A scalable method receives a plurality of graphs, computes for each graph a plurality of features based on edges and vertices in linear computability time independently of reference to any other graphs, normalizes computed feature values into a predetermined range, arranges normalized feature values into an ordered feature vector, and includes a tree feature computed in linear time by traversing vertices, accumulating edges, determining a number of edges whose removal would result in a tree by removing cyclic paths, and comparing the determined number of edges with the traversed vertices.
Multidimensional-distance projection visualization with linearity feature
A scalable method receives a plurality of graphs, computes for each graph a plurality of features based on edges and vertices in linear computability time independently of reference to any other graphs, normalizes computed feature values into a predetermined range, arranges normalized feature values into an ordered feature vector, and includes a linearity feature computed in linear time by traversing vertices, determining at each vertex if a number of edges emanating from the vertex is consistent with a linear graph, accumulating the number of vertices consistent with a linear graph, and comparing the accumulated vertices with the number of traversed vertices.
Across the independent claims, graphs are rendered by converting each graph into a normalized ordered feature vector computed in linear time from that graph alone, deriving similarity via multidimensional distance between feature vectors, projecting the distances to two-dimensional positions, and rendering a clustered two-dimensional visualization. The distinction between the independent claims is the inclusion of a tree feature computed through cycle removal reasoning versus a linearity feature computed through per-vertex consistency with a linear graph.
Stated Advantages
Scalable method of rendering graph data.
Feature values are computed in linear computability time based on a number of edges or a number of vertices independently of reference to any other graphs.
Two-dimensional visualization depicts clusters of closely located sets of points representing projections of multidimensional values.
Documented Applications
Visual recognition and comparison of statistical trends defined in a plurality of graphs via a two-dimensional visualization of feature-vector projections and clusters.
Determining similarity between graphs corresponding to the computed feature vectors using multidimensional distance and rendering clustered visualizations.
Interested in licensing this patent?