Euclidean Distance

Overview

In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points. In the graph, N numeric node properties (features) are specified to represent each node's position in an N-dimensional Euclidean space.

Concepts

Euclidean Distance

In 2-dimensional space, the formula to compute the Euclidean distance between points A(x₁, y₁) and B(x₂, y₂) is:

In 3-dimensional space, the formula to compute the Euclidean distance between points A(x₁, y₁, z₁) and B(x₂, y₂, z₂) is:

Generalized to N-dimensional space, the formula to compute the Euclidean distance is:

where xi₁ represents the i-th dimensional coordinates of the first point, and xi₂ represents the i-th dimensional coordinates of the second point.

Euclidean distance ranges from 0 to +∞; smaller values indicate greater similarity between the two nodes.

Normalized Euclidean Distance

Normalized Euclidean distance scales the Euclidean distance into range from 0 to 1; the closer to 1, the more similar the two nodes.

Ultipa adopts the following formula to normalize the Euclidean distance:

Considerations

• Theoretically, the calculation of Euclidean distance between two nodes is independent of their connectivity.

Example Graph

Run the following statements on an empty graph to define its structure and insert data:

GQLUQL
ALTER GRAPH CURRENT_GRAPH ADD NODE {
  product ({price int32, weight int32, width int32, height int32})
};
INSERT (:product {_id:"product1", price:50, weight:160, width:20, height:152}),
       (:product {_id:"product2", price:42, weight:90, width:30, height:90}),
       (:product {_id:"product3", price:24, weight:50, width:55, height:70}),
       (:product {_id:"product4", price:38, weight:20, width:32, height:66});

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as my_hdc_graph:

GQLUQL
CREATE HDC GRAPH my_hdc_graph ON "hdc-server-1" OPTIONS {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static"
}

Parameters

Algorithm name: similarity

File Writeback

Computes similarities in pairing mode:

GQLUQL
CALL algo.similarity.write("my_hdc_graph", {
  return_id_uuid: "id",
  ids: "product1",
  ids2: ["product2", "product3", "product4"],
  node_schema_property: ["price", "weight", "width", "height"],
  type: "euclideanDistance"
}, {
  file: {
    filename: "euclideanDistance"
  }
})

Result:

File: euclideanDistance
_id1,_id2,similarity
product1,product2,94.3822
product1,product3,143.962
product1,product4,165.179

Full Return

GQLUQL
CALL algo.similarity.run("my_hdc_graph", {
  return_id_uuid: "id",
  ids: ["product1","product2"], 
  ids2: ["product2","product3","product4"],
  node_schema_property: ["price", "weight", "width", "height"],
  type: "euclideanDistance"
}) YIELD distance
RETURN distance

Result:

Stream Return

GQLUQL
CALL algo.similarity.stream("my_hdc_graph", {
  return_id_uuid: "id",
  ids: ["product1", "product3"], 
  node_schema_property: ["price", "weight", "width", "height"],
  type: "euclideanDistance",
  top_limit: 1
}) YIELD top
RETURN top

Result: