Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-10657686-B2
Publication Date
2020-05-19
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
The invention provides a scalable gragnostics rendering method for visualized graph data in an analytics environment where graphs are rendered for visual recognition and comparison of statistical trends. It receives a plurality of graphs, each graph defining associations between data entities and renderable in a visual form having a plurality of vertices connected by one or more edges. For each graph, it computes a plurality of features based on the edges and vertices interconnected by the edges, with feature values computed in linear computability time that varies linearly with at least one of a number of nodes or number of vertices.
The computed features are normalized into a predetermined range and arranged into a feature vector with ordered values for each of the features, including a tree feature and a linearity feature for each graph. The tree feature is determined in linear time by traversing each vertex, accumulating based on the traversal a number of edges, determining a number of edges for which removal would result in a tree by removing cyclic paths, and comparing the determined number of edges with the number of traversed vertices. The linearity feature is determined in linear time by traversing each vertex, 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.
For each graph, a multidimensional distance is computed between the corresponding feature vectors to determine similarity between graphs. Each feature vector is assigned a two-dimensional position corresponding to a projection of the multidimensional distance. The position of each vector is displayed onto a visualized two dimensional rendering, and the feature vectors are rendered so that graphs are grouped and classified by visual clusters of the positions on the two dimensional rendering, where similar graphs form visually separated clusters.
Claims Coverage
Independent claims are clm-00001, clm-00012, and clm-00016. Across these independent claims, the inventive features cover linear-time computation of gragnostics feature vectors including tree and linearity features, normalized ordered feature-vector representation, similarity determination via multidimensional distance, projection into a two-dimensional rendering for visualization, and classification of groups using visual clusters on the two-dimensional rendering.
Scalable linear-time gragnostics feature computation from vertices and edges
receiving a plurality of graphs; computing, for each graph, a plurality of features based on the edges and vertices interconnected by the edges, including computing a feature value for each of the features in a linear computability time such that the feature value is computable in a time that varies linearly with at least one of a number of nodes or a number of vertices
Normalized ordered feature vectors including tree feature and linearity feature
normalizing the computed features into a predetermined range; for each graph, arranging each of the normalized features into a feature vector, the feature vector having ordered values for each of the features, the ordered values including a tree feature and a linearity feature for each graph
Linear-time tree feature determination via traversal and cyclic-path edge removal
determining the tree feature in linear time by traversing each of the vertices in the graph; accumulating, based on the traversal, a number of edges; determining a number of edges for which the removal would result in a tree by removing cyclic paths; and comparing the determined number of edges with a number of the traversed vertices
Linear-time linearity feature determination via traversal and linear-graph consistency
determining the linearity feature in linear time by traversing each of the vertices in the graph; 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 computing the accumulated vertices with the number of traversed vertices
Graph similarity from multidimensional distance between feature vectors
computing a multidimensional distance between each of the feature vectors for determining a similarity between the graphs corresponding to the feature vectors
Two-dimensional projection rendering of similarity using projected multidimensional distance
computing a two dimensional position corresponding to each of the feature vectors based on a projection of the multidimensional distance; displaying the position of each vector onto a visualized two dimensional rendering; and rendering a visualization of the feature vectors
Classification by groups of graphs defined by visual clusters on the two-dimensional rendering
determining similarity of the graphs based on a distance between the corresponding visualized feature vectors by classifying, based on a distance on the visualized two dimensional rendering, groups of graphs, the classification defined by visual clusters of the positions on the two dimensional rendering
The independent claims define a scalable method, device, and program product that computes gragnostics feature vectors from vertices and edges with linear computability time, normalizes and orders the features including tree and linearity features, determines similarity using multidimensional distance, projects similarity into a two-dimensional rendering, and classifies groups of graphs using visual clusters formed by the two-dimensional projected positions.
Stated Advantages
Scalability with feature computation in linear computability time that varies linearly with at least one of a number of nodes or number of vertices.
Interpretability provided through a visualized two dimensional rendering with groups of graphs defined by visual clusters.
Reduced constraints on input graphs.
Documented Applications
Graph classification for visual recognition and comparison of statistical trends defined in a plurality of graphs using a gragnostics rendering.
Interested in licensing this patent?