Weisfeiler-Lehman
This algorithm identifies isomorphic subgraphs in a graph, and labels the corresponding vertices isomorphic graphs.
Two graphs are considered isomorphic if there is a mapping between the nodes of the graphs that preserves node adjacencies. That is, a pair of nodes may be connected by an edge in the first graph if and only if the corresponding pair of nodes in the second graph is also connected by an edge in the same way. An example of two isomorphic graphs is shown here[1]:
This algorithm gives every vertex in the graph a label. It finds the isomorphic subgraphs, and gives every vertex in the isomorphic subgraphs the same label.
Specifications
CREATE QUERY tg_weisfeiler_lehman(STRING v_type,STRING e_type,
INT depth, INT output_limit, BOOL print_accum = TRUE,
STRING result_attr = "",STRING file_path = "")Parameters
| Parameter | Type | Description |
|---|---|---|
|
|
Vertex type to consider. |
|
|
Edge type to traverse. |
|
|
Number of hops to consider |
|
|
If |
|
|
If true, print JSON to standard output. |
|
|
If not empty, save the label of each vertex to this attribute. |
|
|
If not empty, save the result in CSV format to this filepath. |
Output
When print_accum is set to true, the @current_label accumulator on a vertex represents the final label of the vertex.
If two vertices share a label, it means that they are corresponding vertices in two isomorphic subgraphs.
Example
Suppose we have the following graph:
We can see that there are two distinct subgraphs that are isomorphic. Running the algorithm on the graph produces the following results：
RUN QUERY tg_weisfeiler_lehman ("Person", "Friendship", 3, 8, true, _, _)We can see in the results that corresponding vertex pairs such as Emily and Jose share the same label.
[
{
"Start": [
{
"attributes": {
"@current_label": "237612459038074888",
"@label_list": [],
"@previous_label": "1"
},
"v_id": "Wyatt",
"v_type": "Person"
},
{
"attributes": {
"@current_label": "13342665574248803982",
"@label_list": [],
"@previous_label": "1"
},
"v_id": "Emily",
"v_type": "Person"
},
{
"attributes": {
"@current_label": "13342665574248803982",
"@label_list": [],
"@previous_label": "1"
},
"v_id": "Jose",
"v_type": "Person"
},
{
"attributes": {
"@current_label": "6556095808804302272",
"@label_list": [],
"@previous_label": "1"
},
"v_id": "Thomas",
"v_type": "Person"
},
{
"attributes": {
"@current_label": "13342665574248803982",
"@label_list": [],
"@previous_label": "1"
},
"v_id": "Amy",
"v_type": "Person"
},
{
"attributes": {
"@current_label": "237612459038074888",
"@label_list": [],
"@previous_label": "1"
},
"v_id": "Dolores",
"v_type": "Person"
},
{
"attributes": {
"@current_label": "13342665574248803982",
"@label_list": [],
"@previous_label": "1"
},
"v_id": "Jack",
"v_type": "Person"
},
{
"attributes": {
"@current_label": "6556095808804302272",
"@label_list": [],
"@previous_label": "1"
},
"v_id": "Ming",
"v_type": "Person"
}
]
}
]