Ranking of Bangla Word Graph using Graph-based Ranking Algorithms

S. M. Rafiuddin2017 3rd International Conference on Electrical Information and Communication Technology (EICT) 2017 · DOI · arXiv · OpenReview

Abstract

Ranking words is an important way to summarize a text or to retrieve information. A word graph is a way to represent the words of a sentence or a text as the vertices of a graph and to show the relationship among the words. It is also useful to determine the relative importance of a word among the words in the word-graph. In this research, the ranking of Bangla words are calculated, representing Bangla words from a text in a word graph using various graph based ranking algorithms. There is a lack of a standard Bangla word database. In this research, the Indian Language POS-tag Corpora is used, which has a rich collection of Bangla words in the form of sentences with their parts of speech tags. For applying a word graph to various graph based ranking algorithms, several standard procedures are applied. The preprocessing steps are done in every word graph and then applied to graph based ranking algorithms to make a comparison among these algorithms. This paper illustrate the entire procedure of calculating the ranking of Bangla words, including the construction of the word graph from text. Experimental result analysis on real data reveals the accuracy of each ranking algorithm in terms of F1 measure.

Introduction

Bangla (Bengali) is the 7th most spoken language globally, yet it remains a "low-resource" language in the field of Natural Language Processing (NLP). Standardized datasets and specialized tools for tasks like text summarization and information retrieval are scarce. This research addresses the challenge of word ranking—identifying the most significant words within a text. While statistical methods like TF-IDF are common, they often overlook the structural relationships between words. Graph-based methods offer a robust alternative by treating words as nodes and their relationships as edges. This study evaluates which graph algorithms are most effective for the unique syntax and structure of Bangla.

Methodology

The proposed pipeline transforms raw Bangla text into a ranked word list through three primary stages:

  1. Preprocessing: Raw text undergoes tokenization, stemming to identify root words, and stop-word removal to eliminate uninformative common terms.
  2. Graph Construction: Sentences are converted into a Word Graph, specifically a directed acyclic graph (DAG). In this model, nodes represent unique words, and edges represent the flow or relationship between them.
  3. Ranking Algorithms: Five distinct approaches were compared: PageRank, HITS, Positional Power Function (PPF), Min/Max Prefix Scores, and Reference Score Ranking.
Example of a word graph structure with weighted edges used for ranking.

Dataset

The study utilized the Indian Language POS-tag Corpora (bangla.pos), containing 895 Bangla sentences. The data, provided in XML format, includes Parts-of-Speech (POS) tags which were instrumental in constructing the initial word graphs.

Results and Discussion

The performance of each algorithm was evaluated using Precision, Recall, and the F1 Score. The results indicate that traditional web-ranking logic does not perfectly translate to the nuances of Bangla sentence structure.

Performance metrics (Precision, Recall, F1 Score) for the evaluated ranking algorithms.
Ranking Algorithm Precision Recall F1 Score
Min/Max Prefix 0.36 0.40 0.37
Reference Score 0.32 0.38 0.33
HITS 0.31 0.37 0.32
Positional Power Function 0.30 0.35 0.31
PageRank 0.29 0.36 0.31

Key Insights

  • Structure Over Popularity: The success of the Min/Max Prefix method (F1: 0.37) suggests that in linguistic graphs, the specific path and sequence (the "prefix") leading to a word are more indicative of its importance than the sheer volume of "links" it receives, as seen in PageRank (F1: 0.31).
  • Efficiency of DAGs: By utilizing a DAG structure, the research could apply topological ordering. This allows for efficient, non-iterative calculations that are more stable for short texts compared to the iterative convergence required by PageRank or HITS.

Conclusion

While this study demonstrates a successful proof-of-concept for Bangla word ranking, several limitations remain. The dataset size (895 sentences) may not fully represent the diversity of the language. Furthermore, an F1 score of 0.37 indicates significant room for improvement. Future work will focus on optimizing ranking functions and potentially integrating semantic features, such as word embeddings, to better capture the meaning behind word connections in the graph.

Summary updated

Abstract

Ranking words is an important way to summarize a text or to retrieve information. A word graph is a way to represent the words of a sentence or a text as the vertices of a graph and to show the relationship among the words. It is also useful to determine the relative importance of a word among the words in the word-graph. In this research, the ranking of Bangla words are calculated, representing Bangla words from a text in a word graph using various graph based ranking algorithms. There is a lack of a standard Bangla word database. In this research, the Indian Language POS-tag Corpora is used, which has a rich collection of Bangla words in the form of sentences with their parts of speech tags. For applying a word graph to various graph based ranking algorithms, several standard procedures are applied. The preprocessing steps are done in every word graph and then applied to graph based ranking algorithms to make a comparison among these algorithms. This paper illustrate the entire procedure of calculating the ranking of Bangla words, including the construction of the word graph from text. Experimental result analysis on real data reveals the accuracy of each ranking algorithm in terms of F1 measure.
BibTeX
@inproceedings{rafiuddin2017ranking,
  author = {S. M. Rafiuddin},
  title = {{Ranking of Bangla Word Graph using Graph-based Ranking Algorithms}},
  booktitle = {2017 3rd International Conference on Electrical Information and Communication Technology (EICT)},
  year = {2017},
  doi = {10.1109/eict.2017.8275214},
}
Figure