HITS

Algorithm introduction

HITS jointly computes hub and authority scores based on mutually reinforcing link structures.

Compute classic HITS scores on a directed graph. Each iteration updates authority by incoming hubs and hub by outgoing authorities, then applies L2 normalization.

For more information, see HITS.

Data model

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

• Entities are represented by nodes of type Node, with properties id and rating.
• Relationships are represented by edges of type Link, with property weight.

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

Procedure implementation

To compute HITS results, a procedure is created.

For more information about the procedure, see Procedure implementation. The following section describes the key components of the procedure and how it works.

The procedure takes the following input parameters:

• max_iterations: INT64 (default: 20). Maximum number of HITS iterations to run.

Additionally, the following variables are defined within the procedure:

Variable name	Variable type	Description
iter	Primitive value variable	Current iteration counter.
auth_norm	Global SumAgg aggregator value variable	L2 normalization factor for authority scores.
hub_norm	Global SumAgg aggregator value variable	L2 normalization factor for hub scores.
auth_scale	Primitive value variable	Scale factor derived from auth_norm.
hub_scale	Primitive value variable	Scale factor derived from hub_norm.
auth	Node-attached SumAgg aggregator value variable	Per-node current authority score.
hub	Node-attached SumAgg aggregator value variable	Per-node current hub score.
next_auth	Node-attached SumAgg aggregator value variable	Per-node authority score computed for the next iteration.
next_hub	Node-attached SumAgg aggregator value variable	Per-node hub score computed for the next iteration.
result_table	Table variable	Output table storing (vertex_id, hub_score, authority_score).

The following steps outline the logic of the procedure:

1. Initialize all nodes' auth and hub scores to 1.0.
2. Iterate: update next_auth for each node as the sum of in-neighbors' hub scores; update next_hub as the sum of out-neighbors' auth scores.
3. Normalize both next_auth and next_hub by their L2 norms, then assign to auth and hub.
4. Return (vertex_id, hub_score, authority_score) after max_iter iterations.

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 your data model.

   '''
   CREATE GRAPH TYPE IF NOT EXISTS hits_graph_type AS {
       NODE Node (LABEL Node {id INT PRIMARY KEY, rating INT}),
       EDGE Link (Node)-[LABEL Link {weight INT, MULTIEDGE KEY()}]->(Node)
   }
   '''
   

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

   • hits_node.csv: Node data.
   • hits_edge.csv: Edge data.
   Preview the CSV files

   hits_node.csv

   id,rating
   1,0
   2,2
   3,1
   4,0
   5,0
   6,2
   7,1
   8,2
   9,0
   10,1
   11,0
   12,2
   13,1
   14,1
   15,0
   16,2
   17,0
   18,1
   19,2
   20,0
   21,2
   22,1
   23,0
   24,1
   

   hits_edge.csv

   src_id,dst_id,weight
   1,2,4
   1,3,2
   1,4,7
   1,5,9
   2,3,1
   2,4,6
   2,5,5
   2,6,2
   3,4,3
   3,5,4
   3,6,8
   4,6,2
   4,7,6
   4,8,5
   5,6,4
   5,8,7
   5,9,6
   6,8,1
   6,9,5
   6,10,6
   7,9,2
   7,10,9
   8,9,3
   8,11,6
   8,12,4
   9,10,4
   9,12,7
   9,13,2
   10,12,1
   10,13,8
   10,14,4
   11,12,2
   11,14,5
   11,15,7
   12,14,3
   12,15,6
   12,16,5
   13,15,2
   13,16,7
   14,15,4
   14,17,8
   14,18,2
   15,16,1
   15,18,5
   15,19,3
   16,18,3
   16,19,6
   17,18,2
   17,20,7
   17,21,5
   18,19,4
   18,21,9
   18,22,6
   19,21,1
   19,22,5
   20,21,3
   20,23,6
   20,24,8
   21,22,2
   21,23,4
   21,24,7
   22,24,4
   23,24,1
   

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 #hits_graph TYPED hits_graph_type
   

   '''
   USE #hits_graph IMPORT INTO GRAPH {
         NODE (v@Node {id: id, rating: rating}) FROM DATAFILE {
             PATH: "file:///examples/algorithms/hits/hits_node.csv",
             FORMAT: "CSV",
             DELIMITER: ','
         },
         EDGE (id: src_id)-[e@Link {weight: weight}]->(id: dst_id) FROM DATAFILE {
             PATH: "file:///examples/algorithms/hits/hits_edge.csv",
             FORMAT: "CSV",
             DELIMITER: ','
         }
     }
   '''
   

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

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

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

2. Create a procedure

Create a procedure to implement the HITS algorithm. For more information about the procedure, see Procedure implementation.

'''
CREATE OR REPLACE PROCEDURE hits(max_iterations INT64 DEFAULT 20)
RETURNS (vertex_id INT64, authority_score DOUBLE, hub_score DOUBLE)
COMMENT "Compute classic HITS scores on a directed graph. Each iteration updates authority by incoming hubs and hub by outgoing authorities, then applies L2 normalization."
AS {
  VALUE iter INT64 = 0
  VALUE auth_norm SumAgg<DOUBLE> = 0.0
  VALUE hub_norm SumAgg<DOUBLE> = 0.0
  VALUE auth_scale DOUBLE = 1.0
  VALUE hub_scale DOUBLE = 1.0

  NODE VALUE auth SumAgg<DOUBLE> = 1.0
  NODE VALUE hub SumAgg<DOUBLE> = 1.0
  NODE VALUE next_auth SumAgg<DOUBLE> = 0.0
  NODE VALUE next_hub SumAgg<DOUBLE> = 0.0

  TABLE result_table TYPED TABLE {
    vertex_id INT64,
    authority_score DOUBLE,
    hub_score DOUBLE
  }

  WHILE iter < max_iterations THEN {
    MATCH (n)
    PER NODE (n) {
      SET n.@next_auth = 0.0
      SET n.@next_hub = 0.0
    }

    MATCH (u)-[e]->(v)
    PER PATH {
      SET v.@next_auth += u.@hub
      SET u.@next_hub += v.@auth
    }

    SET @auth_norm = 0.0
    SET @hub_norm = 0.0

    MATCH (n)
    PER NODE (n) {
      SET @auth_norm += n.@next_auth * n.@next_auth
      SET @hub_norm += n.@next_hub * n.@next_hub
    }

    SET auth_scale = 1.0
    SET hub_scale = 1.0

    IF @auth_norm > 0.0 THEN {
      SET auth_scale = sqrt(@auth_norm)
    }

    IF @hub_norm > 0.0 THEN {
      SET hub_scale = sqrt(@hub_norm)
    }

    MATCH (n)
    PER NODE (n) {
      SET n.@auth = n.@next_auth / auth_scale
      SET n.@hub = n.@next_hub / hub_scale
    }

    SET iter = iter + 1
  }

  MATCH (n)
  PER NODE (n) {
    EXPORT n.id, n.@auth, n.@hub INTO result_table
  }

  FOR r IN result_table
  RETURN r.vertex_id AS vertex_id,
         r.authority_score AS authority_score,
         r.hub_score AS hub_score
  ORDER BY authority_score DESC, hub_score DESC, vertex_id ASC
}
'''

3. Call your procedure

Set the maximum iteration count to 20 and compute the authority and hub scores for each node.

USE #hits_graph CALL hits(20) RETURN vertex_id, authority_score, hub_score

Returns:

Expand to view results

+-----------+----------------------+----------------------+
| vertex_id | authority_score      | hub_score            |
+-----------+----------------------+----------------------+
| 6         | 0.46078818086938617  | 0.22878573735316127  |
| 5         | 0.39884673775823076  | 0.31337330345878917  |
| 4         | 0.39884673775823076  | 0.24756037000663125  |
| 9         | 0.2789090624818426   | 0.17540742241976578  |
| 3         | 0.27260133168797474  | 0.38451877935783363  |
| 8         | 0.2533178717304967   | 0.19112269631042522  |
| 12        | 0.23089470319335856  | 0.1769811859355897   |
| 15        | 0.19204040064120753  | 0.13438018150476375  |
| 10        | 0.17263468965548384  | 0.1788396587810328   |
| 14        | 0.17097520171309802  | 0.13529227098655977  |
| 18        | 0.1375170138136927   | 0.10358544634202328  |
| 16        | 0.12808929359268753  | 0.08763016515043041  |
| 2         | 0.11906967331683077  | 0.46726820561541466  |
| 13        | 0.10802068157200848  | 0.1160588314479305   |
| 21        | 0.10491444566098529  | 0.06508571864806963  |
| 19        | 0.0972248950920121   | 0.06709133539037962  |
| 7         | 0.08023279859556993  | 0.1483217184376047   |
| 22        | 0.07033156295028854  | 0.021538550495216774 |
| 11        | 0.05927891040820165  | 0.21050754784532189  |
| 24        | 0.05557332059368472  | 0.0                  |
| 23        | 0.04272471207283504  | 0.021538550495216774 |
| 17        | 0.04051200770030375  | 0.10280073692903223  |
| 20        | 0.030685040504097108 | 0.0781496500805586   |
| 1         | 0.0                  | 0.36121770689840116  |
+-----------+----------------------+----------------------+

Save results to a file or graph

To save the returned results as CSV files or write them to a graph, see EXPORT. Match the exported fields to the returned columns and target properties.