TextRank

Overview

TextRank, derived from PageRank, is a graph-based ranking model for text processing. It can be used for various natural language processing tasks, including keyword extraction, keyphrase extraction, and text summarization.

• R. Mihalcea, P. Tarau, TextRank: Bringing Order Into Texts (2004)

Concepts

Text as a Graph

To apply the TextRank algorithm, the text must first be represented as a graph .The structure of the graph depends on the specific application:

• Nodes: Text units that best fit the task, such as words, collocations, or sentences, are added as nodes in the graph.
• Edges: Relationships between text units, such as semantic similarity, co-occurrence, or contextual overlap, are used to connect nodes with edges.

Sample graph build for keyphrase extraction: nodes are selected lexical units from the text, and edges are established based on co-occurrence within a defined window of words (Source: Original paper)

TextRank Model

TextRank computes the ranks of all text units recursively using a "recommendation" mechanism, similar to the PageRank algorithm. It incorporates edge weights through a modified formula that integrates them effectively:

where,

• Out(v) is the set of nodes that node v points to;
• w_vu is the edge weight between nodes v and u;
• d is the damping factor.

Considerations

• The rank of isolated text unit will stay the same as the value of (1 - d).
• A self-loop acts as both a successor and a predecessor, meaning a node can pass some rank to itself. If a network has many self-loops, it will take more iterations to converge.

Example Graph

To create this graph:

// Runs each row separately in order in an empty graphset
create().edge_property(@default, "weight", int32)
insert().into(@default).nodes([{_id:"A"}, {_id:"B"}, {_id:"C"}, {_id:"D"}, {_id:"E"}, {_id:"F"}, {_id:"G"}])
insert().into(@default).edges([{_from:"A", _to:"E", weight:3}, {_from:"B", _to:"A", weight:3}, {_from:"B", _to:"E", weight:2}, {_from:"C", _to:"A", weight:1}, {_from:"C", _to:"D", weight:4}, {_from:"D", _to:"E", weight:5}, {_from:"E", _to:"G", weight:2}, {_from:"F", _to:"B", weight:1}, {_from:"F", _to:"G", weight:3}])

Creating HDC Graph

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

CALL hdc.graph.create("hdc-server-1", "hdc_textrank", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
})

hdc.graph.create("hdc_textrank", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
}).to("hdc-server-1")

Parameters

Algorithm name: text_rank

File Writeback

CALL algo.text_rank.write("hdc_textrank", {
  params: {
    return_id_uuid: "id",
    init_value: 1,
    loop_num: 50,
    damping: 0.8,
    edge_schema_property: "weight",
    order: 'desc'
  },
  return_params: {
    file: {
      filename: "textrank"
    }
  }
})

algo(text_rank).params({
  projection: "hdc_textrank",
  return_id_uuid: "id",
  init_value: 1,
  loop_num: 50,
  damping: 0.8,
  edge_schema_property: "weight",
  order: 'desc'
}).write({
  file: {
    filename: "textrank"
  }
})

Result:

_id,text_rank
G,0.973568
E,0.81696
A,0.3472
D,0.328
B,0.24
F,0.2
C,0.2

DB Writeback

Writes the text_rank values from the results to the specified node property. The property type is double.

CALL algo.text_rank.write("hdc_textrank", {
  params: {
    loop_num: 50,
    edge_schema_property: "@default.weight"
  },
  return_params: {
    db: {
      property: "rank"
    }
  }
})

algo(text_rank).params({
  projection: "hdc_textrank",
  loop_num: 50,
  edge_schema_property: "@default.weight"
}).write({
  db:{ 
    property: 'rank'
  }
})

Full Return

CALL algo.text_rank("hdc_textrank", {
  params: {
    return_id_uuid: "id",    
    init_value: 1,
    loop_num: 50,
    damping: 0.8,
    edge_schema_property: "weight",
    order: 'desc',
    limit: 5
  },
  return_params: {}
}) YIELD TR
RETURN TR

exec{
  algo(text_rank).params({
    return_id_uuid: "id",    
    init_value: 1,
    loop_num: 50,
    damping: 0.8,
    edge_schema_property: "weight",
    order: 'desc',
    limit: 5
  }) as TR
  return TR
} on hdc_textrank

Result:

Stream Return

CALL algo.text_rank("hdc_textrank", {
  params: {
    return_id_uuid: "id",
    loop_num: 50,
    damping: 0.8,
    edge_schema_property: "weight",
    order: 'desc',
    limit: 5
  },
  return_params: {
  	stream: {}
  }
}) YIELD TR
RETURN TR

exec{
  algo(text_rank).params({
    return_id_uuid: "id",
    loop_num: 50,
    damping: 0.8,
    edge_schema_property: "weight",
    order: 'desc',
    limit: 5
  }).stream() as TR
  return TR
} on hdc_textrank

Result: