Jaccard Similarity

Algorithm introduction

The Jaccard similarity algorithm is a measure of similarity coefficient between two sets. The Jaccard similarity coefficient, also known as the Jaccard index, is a statistical measure used to gauge the similarity between two finite sample sets. It is defined as the size of the intersection divided by the size of the union of the two sets. The formula for calculating Jaccard similarity coefficient is as follows:

\[J(A, B) = \frac{|A \cap B|}{|A \cup B|}\]

Where:

• \(J(A, B)\): Jaccard similarity coefficient between sets A and B.
• \(|A \cap B|\): Number of elements in the intersection of sets A and B.
• \(|A \cup B|\): Number of elements in the union of sets A and B.

The value of the Jaccard similarity coefficient ranges from 0 to 1, where 0 indicates no similarity (no common elements) and 1 indicates complete similarity (identical sets).

For more information about the Jaccard similarity algorithm, see Jaccard index.

Data model

To implement the Jaccard similarity algorithm in GQL, the following data model is used to create a graph type:

• Entities are represented by nodes of type User and type Movie.
• Relationships between entities of these two node types (that is, which user likes which movie) are represented by edges of type Likes.

In this data model, each entity of one type (for example, a user) is linked to a set of entities of another type (such as movies the user likes). To quantify the similarity between two entities of the same type, the Jaccard similarity algorithm is used. The Jaccard similarity coefficient is calculated by dividing the size of the intersection of their associated sets by the size of the union of those sets. This value reflects the degree of overlap in their connections.

For the complete definition of the graph type, see Prepare graph data.

Procedure implementation

To compute the Jaccard similarity among 2 sets in GQL, two types of procedures are created to implement the Jaccard similarity algorithm.

The two procedures are single-source Jaccard similarity procedure and batch output Jaccard similarity procedure respectively. For the complete definition of these procedures, see Create procedures. The following section describes the key components of procedures and how they work.

Single-source Jaccard similarity procedureBatch output Jaccard similarity procedure

This procedure takes the following input parameter:

• u_id: The ID of the source entity (the specified user ID) for which to calculate the Jaccard similarity coefficients with target entities (other users).

Additionally, the following variables are defined within the procedure:

Variable name	Variable type	Description
source_edges	Global SumAgg aggregator value variable	The total number of connections from the source entity to entities of the other type. It refers to the number of movies the source user likes in this procedure.
target_edges	Node-attached SumAgg aggregator value variable	The total number of connections from the target entity to entities of the other type. It refers to the number of movies the target user likes in this procedure.
intersection	Node-attached SumAgg aggregator value variable	The count of shared connections to entities of the other type between the source and target entities. It refers to the movies both the source user and target user like.
topk_similarity	Global TopKAgg aggregator value variable	Stores the top-k similarity coefficient along with the corresponding entity IDs.
v_set	Active set variable	The set of entities connected to the source entity. It refers to the set of the movies the source user likes.
result_file	File variable	The file that saves the final results, including the target entity ID and the corresponding Jaccard similarity coefficient.

The following steps outline the logic of the procedure:

1. Traverse each Likes edge to count the total number of connections for each entity (target_edges for every entity).

2. Select the source entity based on the input parameter u_id and calculate source_edges as the total number of connections from the source entity.

3. Collect all entities of the other type (movies) connected to the source entity into the set v_set.

4. For each target entity, compute the source_edges, target_edges and intersection.

5. Compute the Jaccard similarity coefficient using source_edges, target_edges, and intersection.

6. Store the top-k similarity coefficient and corresponding entity ID in topk_similarity.

7. After processing all target entities, export the final similarity results using the file variable result_file.

This procedure takes the following input parameters:

• num_of_batch: The number of batches to divide the computation into.
• min_intersection: The minimum intersection count required to consider the similarity between two entities.

Additionally, the following variables are defined within the procedure:

Variable name	Variable type	Description
batch	Primitive value variable	The current batch number being processed.
source_edges	Global MapAgg aggregator value variable	A mapping of source entity IDs to their respective total connection counts. It refers to the number of movies liked by the source user in this procedure.
source	Active set variable	The set of source entities for the current batch.
neighbor	Active set variable	The set of entities of the other type connected to the current batch of source entities. It refers to the set of movies that the source user likes in this procedure.
out_edges	Node-attached SumAgg aggregator value variable	The total number of connections for each entity. It refers to the number of movies liked by each user.
intersection_map	Node-attached MapAgg aggregator value variable	A mapping of source entity IDs to their respective intersection counts with the target entity.
topk_similarity	Node-attached TopKAgg aggregator value variable	Stores the top-k similarity coefficient along with the corresponding entity ID for each target entity.
result_file	File variable	The file that saves the final results, including the source and target entity ID, as well as the corresponding Jaccard similarity coefficient.

The following steps outline the logic of the procedure:

1. For each batch, select a subset of entities as the source entities.

2. For each source entity in the batch:

   1. Calculate source_edges as the total number of entities linked to each source entity.

   2. Collect all entities connected to the source entity into the set neighbor.

   3. For each item in neighbor, build an intersection_map that records which source entities are connected to each entity.

3. For each target entity (any entity linked to at least one entity in the set neighbor):

   1. Propagate the intersection_map from connected entities to target entities, recording how many connected entities each target entity shares with each source entity.

   2. For each source–target entity pair, calculate the source_edges, target_edges and intersection.

   3. Compute the Jaccard similarity coefficient when the intersection meets the min_intersection threshold and the union is not 0.

   4. Store the top-k Jaccard similarity coefficient along with the corresponding entity ID for each target entity in topk_similarity.

4. After processing all pairs in the batch, export the final similarity results using the file variable result_file.

Steps

Run the following code blocks in order in the NebulaGraph Studio CONSOLE. For first-time setup, follow Prepare algorithm sample data to check where to run commands and how the directory is mounted.

1. Prepare graph data

1. Create a graph type that matches the data model.

   '''
   CREATE GRAPH TYPE IF NOT EXISTS jaccard_graph_type AS {
           NODE User  (LABEL User {id INT PRIMARY KEY, name STRING}),
           NODE Movie (LABEL Movie {id INT PRIMARY KEY, title STRING}),
           EDGE Likes  (User)-[LABEL Likes {MULTIEDGE KEY ()}]->(Movie)
       }
   '''
   

2. Download these CSV files and save them with their original names in examples/algorithms/jaccard/ under your deployment directory:

   • jaccard_node_user.csv: User nodes.
   • jaccard_node_movie.csv: Movie nodes.
   • jaccard_edge.csv: Edge data.
   Preview the CSV files

   jaccard_node_user.csv

   u_id,u_name
   1,Alice
   2,Bob
   3,Charlie
   4,David
   5,Eve
   

   jaccard_node_movie.csv

   m_id,m_title
   1,The Shawshank Redemption
   2,The Dark Knight
   3,12 Angry Men
   4,The Lord of the Rings: The Return of the King
   5,Schindler's List
   

   jaccard_edge.csv

   u_id,m_id
   1,1
   1,2
   2,2
   2,3
   3,2
   3,3
   3,4
   4,3
   4,4
   5,5
   

3. Create a temporary graph based on the graph type and load the data files into the temporary graph.

   CREATE TEMPORARY GRAPH IF NOT EXISTS #jaccard_graph TYPED jaccard_graph_type
   

   '''
   USE #jaccard_graph IMPORT INTO GRAPH {
           NODE (u@User {id: u_id, name: u_name}) FROM DATAFILE {
               PATH: "file:///examples/algorithms/jaccard/jaccard_node_user.csv",
               FORMAT: "CSV",
               DELIMITER: ','
           },
           NODE (m@Movie {id: m_id, title: m_title}) FROM DATAFILE {
               PATH: "file:///examples/algorithms/jaccard/jaccard_node_movie.csv",
               FORMAT: "CSV",
               DELIMITER: ','
           },
           EDGE (id: u_id)-[e@Likes {}]->(id: m_id) FROM DATAFILE {
               PATH: "file:///examples/algorithms/jaccard/jaccard_edge.csv",
               FORMAT: "CSV",
               DELIMITER: ','
           }
         }
   '''
   

   After the import succeeds, run this query in the console to check the node count:

   '''
   USE #jaccard_graph
   MATCH (n)
   RETURN count(n) AS node_count
   '''
   

   The expected node_count is 10. If it differs, check the files and import results before continuing.

2. Create procedures

There are two types of procedures for implementing the Jaccard similarity algorithm: single-source Jaccard similarity procedure and batch output Jaccard similarity procedure. For more information about the implementation of these procedures, see Procedure implementation.

Both procedures compute pairwise Jaccard similarity coefficient between entities, based on the sets of connected entities in the graph. Aggregation techniques are used to determine the size of each entity’s connection set and the size of the intersection between sets.

The key difference between the two procedures lies in their approach to processing entities:

• The single-source Jaccard similarity procedure calculates similarity coefficient between the connection set of a specified source entity and the connection sets of all other entities. It is suitable for scenarios where you want to find similar entities of the same type to a specific one.
• The batch output Jaccard similarity procedure processes multiple source entities in batches, efficiently computing similarity coefficient between their respective connection sets and those of other entities. This enables more efficient computation when dealing with large datasets. It incorporates batching, advanced aggregation maps, threshold-based filtering, and resource management strategies to handle large-scale data efficiently. This makes it well-suited for the comprehensive similarity analysis across an entire dataset.

Single-source Jaccard similarity procedureBatch output Jaccard similarity procedure

'''
CREATE OR REPLACE PROCEDURE jaccard_ss(u_id INT64) RETURNS () AS {
    VALUE      source_edges    SumAgg<INT64> = 0
    VALUE      topk_similarity TopKAgg<5, similarity DOUBLE DESC, id INT DESC>
    NODE VALUE target_edges    SumAgg<INT64> = 0
    NODE VALUE intersection    SumAgg<INT64> = 0
    VALUE      v_set           ACTIVE_SET

    FILE       result_file     {id INT64, similarity DOUBLE} = DATAFILE {
                                PATH: "file:///examples/algorithms/jaccard/output/single_source",
                                FORMAT: "CSV"
                               }

    MATCH (u:User)-[e:Likes]->(m:Movie)
    PER PATH {
      SET u.@target_edges += 1
    }

    MATCH (u:User)-[:Likes]->(m:Movie) WHERE u.id = u_id
    PER NODE (u){
      SET @source_edges += u.@target_edges
    }
    FINALLY {
      SET v_set = m
    }

    MATCH(m:Movie)<-[:Likes]-(t:User) WHERE t.id <> u_id AND m IN v_set
    PER PATH {
      SET t.@intersection += 1
    }
    PER NODE (t){
      VALUE union_size = t.@target_edges + @source_edges - t.@intersection
      if union_size <> 0 THEN {
         VALUE similarity = ROUND(CAST(t.@intersection as DOUBLE) / union_size, 5)
         SET @topk_similarity += RECORD{similarity:similarity,id:t.id}
         EXPORT t.id, similarity INTO result_file
      }
    }
}
'''

'''
CREATE OR REPLACE PROCEDURE jaccard_batch(num_of_batch INT64, min_intersection INT64) RETURNS () AS {
    VALUE      batch            INT32         = 0
    VALUE      source_edges     MapAgg<INT64, SumAgg<INT64>>
    VALUE      source           ACTIVE_SET
    VALUE      neighbor         ACTIVE_SET
    NODE VALUE out_edges        SumAgg<INT64> = 0
    NODE VALUE intersection_map MapAgg<INT64, SumAgg<INT64>>
    NODE VALUE topk_similarity  TopKAgg<2, similarity DOUBLE DESC, target_id INT DESC>

    FILE       result_file      {source INT64, target INT64,
                                similarity DOUBLE} = DATAFILE {
                                PATH: "file:///examples/algorithms/jaccard/output/batch",
                                FORMAT: "CSV"
                                }

    // Count the total number of connections for each entity (movies liked by each user)
    MATCH (s:User)-[e:Likes]->(t:Movie)
    PER PATH {
      SET s.@out_edges += 1
    }

    // Loop through batches and select the source entity set (source users) for each batch
    WHILE batch < num_of_batch THEN {
      LOG_INFO("batch: ", batch)
      MATCH (s:User) WHERE (element_id(s) % num_of_batch = batch)
      PER NODE (s){
        SET @source_edges += TUPLE(element_id(s), s.@out_edges)
      }
      FINALLY {
        SET source = s
      }

      // For each source entity (source user), collect all linked entities (liked movies)
      MATCH (s:User)-[:Likes]->(t:Movie) WHERE s IN source
      PER PATH {
        SET t.@intersection_map += TUPLE(element_id(s), 1)
      }
      FINALLY {
        SET neighbor = t
      }

      // From each entity of the other type (movie), propagate the intersection map to each target entity (target user)
      MATCH (t:Movie)<-[:Likes]-(target:User) WHERE t IN neighbor
      PER PATH {
        SET target.@intersection_map += t.@intersection_map
      }

      // For each target entity, count the intersection size with each source entity (the size of the set of commonly liked movies), and calculate Jaccard similarity coefficient
      PER NODE (target)  {
        VALUE iter = 0
        VALUE `map` = target.@intersection_map
        WHILE iter < length(`map`) THEN {
            VALUE item = `map`[iter]
            VALUE source_node_id = item._0
            VALUE intersection = item._1
            if element_id(target) <> source_node_id AND intersection >= min_intersection THEN {
              VALUE union_size = target.@out_edges + @source_edges.get(source_node_id) - intersection
              if (union_size <> 0) THEN {
                  VALUE similarity = CAST(intersection AS DOUBLE) / union_size
                  SET NODE(source_node_id).@topk_similarity += RECORD{similarity:similarity, target_id:target.id}
              }
            }
            SET iter = iter+1
      }

        // Clear temporary data
        SET target.@intersection_map.clear()
      }
      PER NODE (t) {
        SET t.@intersection_map.clear()
      }

      // Export the similarity results for each source entity in the batch
      MATCH (s:User) WHERE s IN source
      PER NODE (s) {
        VALUE topk = s.@topk_similarity
        VALUE j = 0
        WHILE j < length(topk) THEN {
            VALUE item = topk[j]
            VALUE target_id = item.target_id
            VALUE similarity = item.similarity
            EXPORT s.id, target_id, similarity INTO result_file
            SET j = j + 1
        }
        SET s.@topk_similarity.clear()
      }
      SET @source_edges.clear()

      SET batch = batch + 1
    }
  }
'''

3. Call your procedure

Call the corresponding procedure to calculate the Jaccard similarity coefficient between 2 sets. The following examples set the user ID to 2 for the single-source Jaccard similarity procedure. For the batch output Jaccard similarity procedure, the number of batches is set to 2 and the minimum intersection to 0.

Single-source Jaccard similarity procedureBatch output Jaccard similarity procedure

USE #jaccard_graph CALL jaccard_ss(2) FINISH

This call writes the results to CSV files and does not return a table in the console.

On the Docker host, open the CSV files in examples/algorithms/jaccard/output/single_source/ under your deployment directory. Example contents:

"id","similarity"
1,0.33333
3,0.66667
4,0.33333

id represents the target entity ID (target user ID), and similarity refers to the Jaccard similarity coefficient between the source entity (user ID 2) and the target entity.

USE #jaccard_graph CALL jaccard_batch(2,0) FINISH

This call writes the results to CSV files and does not return a table in the console.

Return:

Log:
2025-10-27T09:50:38.747142 INFO  - batch: 0
2025-10-27T09:50:38.764850 INFO  - batch: 1

On the Docker host, open the CSV files in examples/algorithms/jaccard/output/batch/ under your deployment directory. Example contents:

"source","target","similarity"
2,3,0.6666666666666666
4,3,0.6666666666666666
2,4,0.3333333333333333
4,2,0.3333333333333333
1,2,0.3333333333333333
3,4,0.6666666666666666
1,3,0.25
3,2,0.6666666666666666

source represents the source entity ID (source user ID), target represents the target entity ID (target user ID), and similarity refers to the Jaccard similarity coefficient between the source and target entities.

Write results to a graph

If you need to persist Jaccard results in a graph, follow the approach in EXPORT and adapt it to Jaccard output fields:

• For the single-source procedure, write rows such as (source_id, target_id, similarity) to a table variable before insertion.
• For the batch procedure, use the existing batch output schema (source, target, similarity) as the write-back payload.
• For catalog graphs on the same instance (in standalone-mode temporary graph scenarios), use USE <target_graph> + INSERT.
• For remote graphs, split rows with table_split(...) and send batched USE + INSERT statements via nebula_exec.

Define the target graph type to match the fields you want to persist (for example, store similarity as an edge property between User nodes or as properties on result nodes).