Keyword Extraction Using Graph-Based Clustering

A comprehensive comparative study of graph-based clustering algorithms for automatic keyword extraction from scientific documents.

Overview

This project implements and evaluates 7 clustering algorithms (TextRank, Louvain, MCL, Chinese Whispers, Spectral Clustering, Girvan-Newman, Label Propagation) for keyword extraction across 4 benchmark datasets (INSPEC, SEMEVAL, NUS, DUC) containing 1,111 documents.

Key Results

• Best Overall: TextRank (F1-Score: 0.494)
• Best Cluster Quality: Louvain (Silhouette: 0.683, Calinski-H: 2845.2)
• Fastest: Louvain (0.28 sec/document)
• Correlation: Strong positive correlation (r=0.82) between cluster quality and extraction performance

Features

• 7 Clustering Algorithms: TextRank, Louvain, MCL, Chinese Whispers, Spectral, Girvan-Newman, Label Propagation
• 4 Benchmark Datasets: INSPEC (300 docs), SEMEVAL (300 docs), NUS (211 docs), DUC (300 docs)
• 6 Evaluation Metrics: Precision@10, Recall@10, F1@10, NDCG@10, MAP, ROUGE-1
• 3 Cluster Quality Metrics: Silhouette Score, Calinski-Harabasz Index, Davies-Bouldin Index
• TF-IDF Embeddings: 1-4 gram extraction with cosine similarity graphs

Project Structure

keyword_graph_project/
├── src/
│   ├── preprocessing.py           # Text cleaning and tokenization
│   ├── embeddings.py              # TF-IDF vectorization
│   ├── graph_builder.py           # Similarity graph construction
│   ├── clustering_algorithms.py   # 7 clustering implementations
│   ├── experiment_runner.py       # Main experiment pipeline
│   ├── dataset_analysis.py        # Dataset statistics
│   ├── final_results.py           # Results aggregation
│   └── utils.py                   # Utility functions
├── results/
│   ├── cleaned_data/              # Preprocessed datasets (CSV)
│   └── model_logs/                # Analysis results (JSON)
├── requirements.txt               # Python dependencies
└── README.md                      # This file

Installation

Prerequisites

• Python 3.8+
• pip

Setup

# Clone the repository
git clone https://github.com/pdschandel/Keyword-Extraction-Using-Graph-Based-Clustering.git
cd Keyword-Extraction-Using-Graph-Based-Clustering

# Create virtual environment
python -m venv venv
source venv/bin/activate  # On Windows: venv\Scripts\activate

# Install dependencies
pip install -r requirements.txt

# Download NLTK data
python -c "import nltk; nltk.download('punkt'); nltk.download('stopwords'); nltk.download('wordnet')"

Usage

Quick Start

from src.preprocessing import preprocess_documents
from src.embeddings import compute_embeddings
from src.graph_builder import build_similarity_graph
from src.clustering_algorithms import extract_keywords_louvain

# Load and preprocess documents
documents = preprocess_documents('path/to/your/documents.csv')

# Generate TF-IDF embeddings
embeddings = compute_embeddings(documents)

# Build similarity graph
graph = build_similarity_graph(embeddings, threshold=0.2)

# Extract keywords using Louvain clustering
keywords = extract_keywords_louvain(graph, top_k=10)

Run Full Experiments

from src.experiment_runner import run_experiments

# Run all algorithms on all datasets
results = run_experiments(
    datasets=['INSPEC', 'SEMEVAL', 'NUS', 'DUC'],
    algorithms=['textrank', 'louvain', 'mcl', 'chinese_whispers', 
                'spectral', 'girvan_newman', 'label_propagation']
)

Dataset Analysis

from src.dataset_analysis import analyze_dataset

# Analyze dataset characteristics
stats = analyze_dataset('INSPEC')
print(f"Documents: {stats['num_docs']}")
print(f"Avg Length: {stats['avg_length']}")
print(f"Avg Keywords: {stats['avg_keywords']}")

Algorithms

1. TextRank (Baseline)

• Approach: PageRank-based centrality ranking
• F1-Score: 0.494 (Best)
• Runtime: 0.42 sec/doc
• Strengths: Fast, consistent, no clustering overhead

2. Louvain (Community Detection)

• Approach: Modularity optimization
• F1-Score: 0.483 (2nd best)
• Cluster Quality: Best (Silhouette: 0.683)
• Runtime: 0.28 sec/doc (Fastest)
• Strengths: Excellent trade-off between speed, quality, and performance

3. MCL (Markov Cluster Algorithm)

• Approach: Flow simulation
• F1-Score: 0.465
• Runtime: 1.87 sec/doc
• Strengths: Good balance of performance and cluster quality

4. Chinese Whispers

• Approach: Label propagation with randomization
• F1-Score: 0.453
• Runtime: 0.31 sec/doc
• Weaknesses: Over-segmentation (642 clusters on NUS)

5. Label Propagation

• Approach: Deterministic label spreading
• F1-Score: 0.442
• Runtime: 0.35 sec/doc
• Weaknesses: Over-fragmentation tendency

6. Spectral Clustering

• Approach: Eigenvalue decomposition
• F1-Score: 0.432
• Cluster Quality: 2nd best (Silhouette: 0.621)
• Runtime: 2.14 sec/doc
• Weaknesses: Slow due to O(n³) complexity

7. Girvan-Newman

• Approach: Edge betweenness-based division
• F1-Score: 0.417 (Lowest)
• Runtime: 45.3 sec/doc (Slowest)
• Weaknesses: Prohibitively slow, poor performance

Datasets

Dataset	Documents	Avg Length	Domain	Best F1
INSPEC	300	152.6 words	CS Abstracts	0.471
SEMEVAL	300	184.5 words	Scientific	0.483
NUS	211	8,431.2 words	Mixed Scientific	0.455
DUC	300	846.4 words	News	0.410

Performance Metrics

Overall Performance (Average across all datasets)

Algorithm	Precision@10	Recall@10	F1@10	NDCG@10	MAP	ROUGE-1
TextRank	0.423	0.578	0.494	0.612	0.435	0.387
Louvain	0.412	0.562	0.483	0.598	0.421	0.375
MCL	0.395	0.548	0.465	0.581	0.408	0.362
Chinese Whispers	0.385	0.535	0.453	0.569	0.395	0.351
Label Propagation	0.376	0.521	0.442	0.554	0.383	0.342
Spectral	0.368	0.508	0.432	0.541	0.372	0.335
Girvan-Newman	0.354	0.492	0.417	0.523	0.358	0.324

Cluster Quality Metrics (INSPEC Dataset)

Algorithm	Silhouette ↑	Calinski-H ↑	Davies-B ↓
Louvain	0.683	2845.2	0.245
Spectral	0.621	2345.8	0.298
MCL	0.598	2156.4	0.312
Chinese Whispers	0.542	1876.3	0.356
Label Propagation	0.539	1823.7	0.361
Girvan-Newman	0.487	1534.2	0.423

Key Findings

1. TextRank Dominance: Achieves best F1-score (0.494) through pure centrality-based ranking without explicit clustering
2. Louvain's Potential: Best cluster quality (Silhouette: 0.683) with 2nd-best F1, fastest runtime (0.28 sec)
3. Quality-Performance Correlation: Strong correlation (r=0.82) between cluster quality and F1-scores
4. Optimal Cluster Count: 15-25 clusters for short documents provide best balance
5. Computational Efficiency: TextRank and Louvain suitable for production; Girvan-Newman prohibitively slow
6. Domain Sensitivity: Scientific texts (INSPEC F1: 0.471) outperform news articles (DUC F1: 0.410)

Dependencies

See requirements.txt for full list. Key dependencies:

• numpy >= 1.21.0
• scipy >= 1.7.0
• scikit-learn >= 1.0.0
• networkx >= 2.6.0
• python-louvain >= 0.15
• nltk >= 3.6.0
• pandas >= 1.3.0
• markov-clustering >= 0.0.6

Citation

If you use this code in your research, please cite:

@misc{chandel2024keyword,
  author = {Chandel, Pushpdeep},
  title = {Keyword Extraction Using Graph-Based Clustering: A Comparative Study},
  year = {2024},
  institution = {National Institute of Technology Hamirpur},
  url = {https://github.com/pdschandel/Keyword-Extraction-Using-Graph-Based-Clustering}
}

License

This project is licensed under the MIT License - see the LICENSE file for details.

Author

Pushpdeep Chandel
National Institute of Technology Hamirpur
GitHub: @pdschandel

Acknowledgments

• Benchmark datasets: INSPEC, SEMEVAL-2010, NUS, DUC-2001
• Graph clustering implementations: NetworkX, python-louvain, markov-clustering
• Evaluation framework: scikit-learn, NLTK

Future Work

• Transformer-based embeddings (BERT, RoBERTa) instead of TF-IDF
• Hierarchical clustering for multi-level keyword extraction
• Adaptive similarity thresholds per document
• Pure cluster-based selection (round-robin) to maximize diversity
• Ensemble approaches combining multiple algorithms
• Real-time keyword extraction API