Jaccard Similarity

Overview

Jaccard similarity, or Jaccard index, was proposed by Paul Jaccard in 1901. It’s a metric of similarity for two sets of data. In the graph, collecting the neighbors of a node into a set, two nodes are considered similar if their neighborhood sets are similar.

Jaccard similarity ranges from 0 to 1, where 1 indicates that two sets are identical, and 0 indicates that they share no common elements.

Concepts

Jaccard Similarity

Given two sets A and B, the Jaccard similarity between them is computed as:

In the following example, set A = {b,c,e,f,g}, set B = {a,d,b,g}, their intersection A⋂B = {b,g}, their union A⋃B = {a,b,c,d,e,f,g}, hence the Jaccard similarity between A and B is 2 / 7 = 0.285714.

When applying Jaccard Similarity to compare two nodes in a graph, we use the 1-hop neighborhood set to represent each target node. The 1-hop neighborhood set:

• contains no repeated nodes;
• excludes the two target nodes.

In this graph, the 1-hop neighborhood set of nodes u and v is:

• N_u = {a,b,c,d,e}
• N_v = {d,e,f}

Therefore, the Jaccard similarity between nodes u and v is 2 / 6 = 0.333333.

Weighted Jaccard Similarity

The Weighted Jaccard Similarity is an extension of the classic Jaccard Similarity that takes into account the weights associated with elements in the sets being compared.

The formula for Weighted Jaccard Similarity is given by:

In this weighted graph, the union of the 1-hop neighborhood sets N_u and N_v is {a,b,c,d,e,f}. For each element in the union set, assign a value equal to the sum of the edge weights between the target node and the corresponding node; assign 0 if no edge exists between them:

Therefore, the Weighted Jaccard Similarity between nodes u and v is (0+0+0+0.5+0.5+0) / (1+1+1+1+1.6+1) = 0.151515.

NOTE

Please ensure that the sum of the edge weights between the target node and the neighboring node is greater than or equal to 0.

Considerations

• The algorithm treats all edges as undirected.
• Self-loops are ignored when computing neighborhoods.

Example Graph

GQL
INSERT (userA:user {_id: "userA"}), (userB:user {_id: "userB"}),
       (userC:user {_id: "userC"}), (userD:user {_id: "userD"}),
       (running:sport {_id: "running"}), (tennis:sport {_id: "tennis"}),
       (baseball:sport {_id: "baseball"}), (swimming:sport {_id: "swimming"}),
       (badminton:sport {_id: "badminton"}), (iceball:sport {_id: "iceball"}),
       (userA)-[:likes {weight: 2}]->(tennis),
       (userA)-[:likes {weight: 1}]->(baseball),
       (userA)-[:likes {weight: 3}]->(swimming),
       (userA)-[:likes {weight: 2}]->(badminton),
       (userB)-[:likes {weight: 1}]->(running),
       (userB)-[:likes {weight: 3}]->(swimming),
       (userC)-[:likes {weight: 2}]->(swimming),
       (userD)-[:likes {weight: 1}]->(running),
       (userD)-[:likes {weight: 2}]->(badminton),
       (userD)-[:likes {weight: 2}]->(iceball)

Parameters

Supports three computation modes:

• All-pairs: When both ids and ids2 are empty, computes similarity between all node pairs in the graph.
• Pairing: When both ids and ids2 are specified, computes similarity between each node in ids and each node in ids2.
• Selection: When only ids is specified (no ids2), computes similarity between each node in ids and all other nodes. Use top_limit to limit results per source node.

Run Mode

Returns:

Jaccard similarity in pairing mode:

GQL
CALL algo.similarity({
  type: "jaccard",
  ids: ["userC"],
  ids2: ["userA", "userB", "userD"]
}) YIELD node1, node2, similarity

Result:

Jaccard similarity in selection mode:

GQL
CALL algo.similarity({
  type: "jaccard",
  ids: ["userA"],
  weight: ["weight"],
  top_limit: 2
}) YIELD node1, node2, similarity
RETURN node1, node2, similarity

Result:

Stream Mode

Returns the same columns as run mode, streamed for memory efficiency.

GQL
CALL algo.similarity.stream({
  type: "jaccard",
  degreeCutoff: 3
}) YIELD node1, node2, similarity
RETURN node1, node2, similarity

Result:

Stats Mode

Returns:

GQL
CALL algo.similarity.stats({
  type: "jaccard"
}) YIELD pairCount, minSimilarity, maxSimilarity, avgSimilarity

Result:

Write Mode

Computes results and writes them back to node properties. The write configuration is passed as a second argument map.

Write parameters:

Writable columns:

Returns:

GQL
CALL algo.similarity.write({type: "jaccard", ids: ["userA", "userB"]}, {
  db: {
    property: "sim_score"
  }
}) YIELD task_id, nodesWritten, computeTimeMs, writeTimeMs