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.

NOTE

In practice, you may need to convert some node properties into node schemas in order to calculate the similarity index that is based on common neighbors, just as the Jaccard Similarity. For instance, when considering the similarity between two applications, information like phone number, email, device IP, etc. of the application might have been stored as properties of @application node schema; they need to be designed as nodes and incorporated into the graph in order to be used for comparison.

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 Jaccard Similarity algorithm ignores the direction of edges but calculates them as undirected edges.
• The Jaccard Similarity algorithm ignores any self-loop.

Example Graph

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

GQLUQL
ALTER GRAPH CURRENT_GRAPH ADD NODE {
  user (),
  sport()
};
ALTER GRAPH CURRENT_GRAPH ADD EDGE {
  like ()-[{weight int32}]->()
};
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)-[:like {weight: 2}]->(tennis),
       (userA)-[:like {weight: 1}]->(baseball),
       (userA)-[:like {weight: 3}]->(swimming),
       (userA)-[:like {weight: 2}]->(badminton),
       (userB)-[:like {weight: 1}]->(running),
       (userB)-[:like {weight: 3}]->(swimming),
       (userC)-[:like {weight: 2}]->(swimming),
       (userD)-[:like {weight: 1}]->(running),
       (userD)-[:like {weight: 2}]->(badminton),
       (userD)-[:like {weight: 2}]->(iceball);

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

GQLUQL
CALL algo.similarity.write("my_hdc_graph", {
  return_id_uuid: "id",
  ids: "userC",
  ids2: ["userA", "userB", "userD"],
  type: "jaccard"
}, {
  file: {
    filename: "jaccard"
  }
})

Result:

File: jaccard
_id1,_id2,similarity
userC,userA,0.25
userC,userB,0.5
userC,userD,0

Full Return

GQLUQL
CALL algo.similarity.run("my_hdc_graph", {
  return_id_uuid: "id",
  ids: ["userA","userB"], 
  ids2: ["userB","userC","userD"],
  type: "jaccard"
}) YIELD jacc
RETURN jacc

Result:

Stream Return

GQLUQL
CALL algo.similarity.stream("my_hdc_graph", {
  return_id_uuid: "id",
  ids: ["userA"], 
  type: "jaccard",
  edge_weight_property: "weight",
  top_limit: 2    
}) YIELD jacc
RETURN jacc

Result: