This algorithm assigns a unique integer value known as its color to the vertices of a graph such that no neighboring vertices share the same color. The reason why this is called color is that this task is equivalent to assigning a color to each nation on a map so that no neighboring nations share the same color.
Given a set of k vertices, the algorithm first colors all vertices with the same color - the first color. It then starts from all the vertices and has each vertex send its own colors to its neighbors. If there are two neighboring vertices with the same color, the algorithm will reassign colors where there is a conflict. The same process is repeated until all conflicts are resolved.
The algorithm has a worst-case time complexity of O(V^2 + E), where V is the number of vertices and E is the number of edges.
On the social10 graph, say we want to color the Person
vertices in such a way that any two vertices that are either connected by a Friend
edge or a Coworker
edge do not have the same color. By running the greedy_graph_color
algorithm, we get the following result:
Name
Description
v_type
A set of all vertex types to color.
e_type
A set of all edge types to traverse.
max_colors
The Maximum number of colors that can be used. Use a large number like 999999 unless there is a strict limit.
print_color_count
If set to true, the total number of colors used will be displayed
display
If set to true, the output will display all vertices and their associated color
file_path
If a file path is provided, the output will be saved to the file indicated by the file path in CSV format.
The k-Nearest Neighbors (kNN) algorithm is one of the simplest classification algorithms. It assumes that some or all the vertices in the graph have already been classified. The classification is stored as an attribute called the label. The goal is to predict the label of a given vertex, by seeing what are the labels of the nearest vertices.
Given a source vertex in the dataset and a positive integer k, the algorithm calculates the distance between this vertex and all other vertices and selects the k vertices that are nearest. The prediction of the label of this node is the majority label among its k-nearest neighbors.
The distance can be physical distance as well as the reciprocal of similarity score, in which case "nearest" means "most similar". In our algorithm, the distance is the reciprocal of cosine neighbor similarity. The similarity calculation used here is the same as the calculation in Cosine Similarity of Neighborhoods, Single Source. Note that in this algorithm, vertices with zero similarity to the source node are not considered in prediction. For example, if there are 5 vertices with non-zero similarity to the source vertex, and 5 vertices with zero similarity, when we pick the top 7 neighbors, only the label of the 5 vertices with non-zero similarity score will be used in prediction.
The algorithm will not output more than K vertex pairs, so the algorithm may arbitrarily choose to output one vertex pair over another if there are tied similarity scores.
For the movie graph, we add the following labels to the Person vertices.
When we install the algorithm, answer the questions like:
We then run kNN, using Neil as the source person and k=3. This is the JSON output :
If we run cosine_nbor_ss, using Neil as the source person and k=3, we can see the persons with the top 3 similarity score:
Kat has a label "b", Kevin has a label "a", and Jing does not have a label. Since "a" and "b" are tied, the prediction for Neil is just one of the labels.
If Jing had label "b", then there would be 2 "b"s, so "b" would be the prediction.
If Jing had label "a", then there would be 2 "a"s, so "a" would be the prediction.
Characteristic
Value
Result
The predicted label for the source vertex.
The result is available in three forms:
streamed out in JSON format
written to a file in tabular format, or
stored as a vertex attribute value.
Input Parameters
VERTEX source
: The vertex which you want to predict the label
SET<STRING> v_type
: Vertex types to calculate distance to source vertex for
SET<STRING> e_type
: Edge types to traverse
SET<STRING> re_type
: Reverse edge types to traverse
STRING weight
: Edge attribute to use as the weight of the edge
STRING label
: Vertex attribute to recognize as the label of the vertex
INT top_k
: number of nearest neighbors to consider
BOOL print_accum
: If true, the algorithm will output the result to the console in JSON format.
STRING filepath
: If provided, the algorithm will output to this file path in CSV format
STRING attr
: Vertex attribute to save the predicted label as.
Result Size
V = number of vertices
Time Complexity
O(D^2), D = outdegree of vertex v
Graph Types
Undirected or directed edges, weighted edges
k-Nearest Neighbors (kNN) is often used for machine learning. You can choose the value for topK
based on your experience, or using cross-validation to optimize the hyperparameters. In our library, Leave-one-out cross-validation for selecting optimal k is provided. Given a k value, we run the algorithm repeatedly using every vertex with a known label as the source vertex and predict its label. We assess the accuracy of the predictions for each value of k, and then repeat for different values of k in the given range. The goal is to find the value of k with highest predicting accuracy in the given range, for that dataset.
Run knn_cosine_cv with min_k=2, max_k = 5. The JOSN result:
Characteristic
Value
Result
A list of prediction accuracy for every k value in the given range, and
the value of k with the highest predicting accuracy in the given range.
The result is available in JSON format
Input Parameters
SET<STRING> v_type
: Vertex types to calculate distance to source vertex for
SET<STRING> e_type
: Edge types to traverse
SET<STRING> re_type
: Reverse edge types to traverse
STRING weight
: Edge attribute to use as the weight of the edge
STRING label
: Vertex attribute to recognize as the label of the vertex
INT min_k
: lower bound of k (inclusive)
INT max_k
: upper bound of k (inclusive)
Result Size
max_k-min_k+1
Time Complexity
O(max_k*E^2 / V), V = number of vertices, E = number of edges
Graph Types
Undirected or directed edges, weighted edges
This algorithm is a batch version of the k-Nearest Neighbors, Cosine Neighbor Similarity, single vertex. It makes a prediction for every vertex whose label is not known (i.e., the attribute for the known label is empty), based on its k nearest neighbors' labels.
For the movie graph shown in the single vertex version, run knn_cosine_all, using topK=3. Then you get the following result:
Characteristic
Value
Result
The predicted label for the vertices whose label attribute is empty.
The result is available in three forms:
streamed out in JSON format
written to a file in tabular format, or
stored as a vertex attribute value.
Input Parameters
SET<STRING> v_type
: Vertex types to calculate distance to source vertex for
SET<STRING> e_type
: Edge types to traverse
SET<STRING> re_type
: Reverse edge types to traverse
STRING weight
: Edge attribute to use as the weight of the edge
STRING label
: Vertex attribute to recognize as the label of the vertex
INT top_k
: number of nearest neighbors to consider
BOOL print_accum
: Boolean value that indicates whether to output to console in JSON
STRING filepath
: If provided, the algorithm will output to this file path in CSV format
STRING attr
: Vertex attribute to save the predicted label as.
Result Size
V = number of vertices
Time Complexity
O(E^2 / V), V = number of vertices, E = number of edges
Graph Types
Undirected or directed edges, weighted edges