GraphUCB-CD is an adaptive focused web crawler that learns its link-selection policy online using a contextual bandit algorithm (LinUCB) over graph-structured arms, with explicit change-point detection that drives re-exploration when the relevance landscape shifts. The system combines a trainable GraphSAGE encoder, CUSUM + Bayesian change-point detectors, a composite LLM-judged reward function, and a hierarchical meta-controller into a single reproducible pipeline.
- Abstract
- Screenshots
- Architecture
- Quick Start
- Module Reference
- Offline Replay Mode
- Testing
- Configuration
- Roadmap
- License
Focused crawling — maximizing the harvest of topically relevant pages under a fixed fetch budget — is fundamentally a sequential decision problem under uncertainty. The web is non-stationary: relevance distributions drift as the crawler crosses domain boundaries, site structures evolve, and the reward signal (page relevance) is only observed after the fetch. GraphUCB-CD addresses all three challenges with a single integrated system: a graph-aware contextual bandit (LinUCB with GraphSAGE features), a dual change-point detector (CUSUM on reward residuals + Bayesian online posterior), and a hierarchical meta-controller that allocates the crawl budget across domain-level strategies. The system is evaluated via a fully deterministic offline replay simulator that generates a 200-page synthetic web snapshot with configurable drift injection, enabling reproducible benchmarking without network access. Step 1 delivers the repository skeleton, all core interfaces, the in-memory implementations, and the working simulator — verified by 12 passing unit tests.
The simulator generates a deterministic 200-page web snapshot (seed=42) with 14 domains, 3 topics, and graph-structured links. The demo runs 20 simulated fetches and reports the harvest rate, graph topology, and frontier state.
All interfaces, implementations, and simulator behaviours are covered by unit tests: snapshot determinism, link extraction, ground-truth relevance, step counting, drift injection, frontier priority ordering, graph neighbors, and vector similarity search.
The modular design separates configuration, interfaces, in-memory implementations, and the simulator. Green boxes are implemented (Step 1); grey boxes are upcoming (Steps 3-7).
The bar chart shows the ground-truth relevance of each fetched page. Green bars (≥0.5) are relevant; grey bars are irrelevant. The first 3 fetches (the seed pages) are highly relevant (0.96-0.99), after which the crawler explores the graph frontier with placeholder scores (the bandit is wired in Step 3).
The simulator injects a relevance shift at step 120: pages that were relevant become irrelevant, and vice versa. The green zone (steps 0-120) shows the stable pre-drift distribution; the red zone (steps 121-200) shows the shifted post-drift distribution. The change-point detector (Step 3) must detect this shift and inflate the exploration coefficient to recover.
graphucb-cd/
├── config/
│ └── settings.py CrawlConfig — 30+ typed hyperparameters (pydantic)
├── crawler/
│ ├── interfaces.py Protocols: Frontier, GraphStore, VectorStore, Judge
│ ├── frontier.py InMemoryFrontier — heap-based priority queue
│ └── cli.py CLI: demo / run / eval / report
├── graph/
│ ├── store.py NetworkXGraphStore — DiGraph with 1/2-hop neighbors
│ └── vectors.py NumpyVectorStore — cosine-similarity search
├── judge/
│ └── simulator.py OfflineSimulator — 200-page deterministic snapshot
├── bandit/ GraphUCB-CD bandit (Step 3)
├── meta/ Hierarchical controller (Step 5)
├── eval/ Evaluation pipeline (Step 6)
├── report/ Report generation (Step 7)
├── results/ Logs + CSV + plots
├── tests/ 12 unit tests
├── docs/screenshots/ 5 screenshots + diagrams
├── Makefile demo / test / report targets
├── requirements.txt Python dependencies
├── LICENSE MIT License
└── README.md This file
┌──────────────────────────┐
│ config/settings.py │
│ CrawlConfig (seed=42) │
└────────────┬─────────────┘
│
┌────────────▼─────────────┐
│ judge/simulator.py │
│ OfflineSimulator │
│ • 200-page snapshot │
│ • drift at step 120 │
└────────────┬─────────────┘
│
┌────────────▼─────────────┐
│ crawler/frontier.py │
│ InMemoryFrontier │
│ • priority queue │
│ • visited-set dedup │
└────────────┬─────────────┘
│
┌──────────────────┼──────────────────┐
│ │ │
┌──────────▼─────┐ ┌────────▼─────────┐ ┌─────▼──────────┐
│ graph/store.py │ │ graph/vectors.py │ │ crawler/cli.py │
│ NetworkXGraph │ │ NumpyVectorStore │ │ CLI entry │
│ • nodes/edges │ │ • cosine search │ • demo / run │
│ • 1/2-hop BFS │ │ • add/get/search │ • eval / report│
└────────────────┘ └──────────────────┘ └────────────────┘
- Python 3.11+
- pip
git clone https://github.com/Vaskoor/graphucb-cd.git
cd graphucb-cd
pip install -r requirements.txtmake demo
# or: python -m crawler.cli demoOutput:
============================================================
GraphUCB-CD — Offline Simulator Demo
============================================================
Snapshot: 200 pages, drift at step 120
Topic: quantum_hardware
Seeds: ['https://quantum-labs.com/page/0027', 'https://stanford.edu/page/0067', 'https://wiki.org/page/0089']
Simulating 20 fetches...
Step URL Domain Rel
---- --------------------------------------------- -------------------- -----
1 https://quantum-labs.com/page/0027 quantum-labs.com 0.99
2 https://stanford.edu/page/0067 stanford.edu 0.97
...
Results:
Pages fetched: 20
Relevant harvested: 3
Harvest rate: 15.0%
Graph nodes: 79
Graph edges: 99
Frontier size: 59
✅ Simulator is running. Step 1 complete.
make test
# or: python -m pytest tests/ -vOutput: 12 passed in 0.89s
Central configuration object. Every module receives a copy. Includes:
| Parameter | Default | Description |
|---|---|---|
seed |
42 | Master RNG seed |
max_pages |
200 | Total fetch budget |
alpha |
1.0 | LinUCB exploration coefficient |
discount |
0.98 | Discounted LinUCB weight for old observations |
feature_dim |
64 | GraphSAGE output dimension |
detector_window |
50 | Sliding window for residual-based detection |
cusum_threshold |
3.0 | CUSUM alarm threshold (σ units) |
bayes_prob_threshold |
0.35 | Bayesian P(changepoint) threshold |
w_relevance |
0.6 | Reward weight for LLM relevance |
w_novelty |
0.3 | Reward weight for information-gain novelty |
w_efficiency |
0.1 | Reward weight for cost penalty |
Loaded from YAML: config = load_yaml("config/default.yaml"). Overrides
via CLI: config = load_config({"alpha": 2.0}). Config hash:
config.config_hash → stable SHA-256 prefix for manifest/checkpointing.
Five structural-typing Protocols + three dataclasses:
| Protocol | Contract |
|---|---|
Frontier |
add(url, score, domain, depth), pop() → (url, score, ...), peek(n), visited() |
GraphStore |
add_node(url, domain, depth, relevance), add_edge(src, dst, anchor), neighbors(url, hops), in_degree(url) |
VectorStore |
add(key, vector, meta), search(query, k) → [(key, sim)], get(key) |
Judge |
judge_relevance(page, topic) → float, judge_novelty(page, summary) → float, calibration_error() |
FeatureExtractor |
extract(url, anchor, context, graph, page) → [float], dim(), update_graph_encoder(graph, pos, neg) |
Dataclasses: Page (url, html, text, content_hash, domain, depth),
Link (source_url, target_url, anchor_text, context_text, domain),
DecisionLog (step, arm_url, scores, reward components, detector state).
Heap-based priority queue. Thread-safe (threading.Lock). Pop returns highest-scored URL. Re-adds of visited URLs are silently dropped. A Redis-backed implementation would share the same Frontier Protocol.
Wraps networkx.DiGraph. Supports 1-hop and 2-hop neighborhood
retrieval via BFS for GraphSAGE aggregation. Node metadata includes
domain, depth, and relevance. A Neo4j adapter would share the same
GraphStore Protocol.
Brute-force cosine-similarity search over normalized vectors. Used by the novelty judge to compute information gain relative to already- harvested content. A FAISS/Chroma adapter would share the same VectorStore Protocol.
The reproducible benchmark. Generates a deterministic 200-page synthetic web snapshot from a seed:
- 14 domains (arxiv.org, ieee.org, nature.com, mit.edu, etc.)
- 3 topics (quantum_hardware, renewable_energy, machine_learning_theory)
- Topic keywords appear in body text proportional to relevance
- 2-8 outgoing links per page (graph-structured)
- Drift injection at step 120 — 40% of pages have their relevance
scores swapped (pre-drift scores preserved, post-drift stored
separately;
ground_truth_relevance()switches based on step vs drift_step)
The simulator exposes: simulate_request(url), extract_links(page),
ground_truth_relevance(url, topic), seeds(topic, k).
The offline replay mode is the primary evaluation mode. It requires no network access and produces identical results on every run given the same seed.
from judge.simulator import OfflineSimulator
from crawler.frontier import InMemoryFrontier
from graph.store import NetworkXGraphStore
# Initialize
sim = OfflineSimulator(seed=42, n_pages=200, drift_step=120)
frontier = InMemoryFrontier()
graph = NetworkXGraphStore()
# Seed the frontier
for url in sim.seeds(topic="quantum_hardware", k=5):
frontier.add(url, score=0.5, domain="seed", depth=0)
# Crawl loop
for step in range(200):
entry = frontier.pop()
if entry is None:
break
url, score, domain, depth, anchor, context = entry
page = sim.simulate_request(url)
if page is None:
continue
graph.add_node(url, domain=domain, depth=depth)
for link in sim.extract_links(page):
graph.add_edge(url, link.target_url, link.anchor_text)
frontier.add(link.target_url, 0.5, link.domain, depth+1,
link.anchor_text, link.context_text)
rel = sim.ground_truth_relevance(url, "quantum_hardware")
print(f"Step {step+1}: {url} → rel={rel:.2f}")$ python -m pytest tests/ -v
tests/test_simulator.py::TestSnapshotDeterminism::test_same_seed_same_snapshot PASSED
tests/test_simulator.py::TestSnapshotDeterminism::test_different_seed_different_snapshot PASSED
tests/test_simulator.py::TestSimulator::test_seeds_returned PASSED
tests/test_simulator.py::TestSimulator::test_simulate_request PASSED
tests/test_simulator.py::TestSimulator::test_extract_links PASSED
tests/test_simulator.py::TestSimulator::test_ground_truth_relevance PASSED
tests/test_simulator.py::TestSimulator::test_step_counter PASSED
tests/test_simulator.py::TestSimulator::test_drift_changes_relevance PASSED
tests/test_simulator.py::TestFrontier::test_priority_ordering PASSED
tests/test_simulator.py::TestFrontier::test_no_duplicate_visits PASSED
tests/test_simulator.py::TestGraphStore::test_add_and_neighbors PASSED
tests/test_simulator.py::TestVectorStore::test_add_and_search PASSED
============================== 12 passed in 0.89s ==============================
Tests cover:
- Snapshot determinism — same seed → identical snapshot; different seed → different URLs
- Simulator — request, link extraction, ground-truth relevance, step counter, drift injection
- Frontier — priority ordering (highest score pops first), no duplicate visits
- Graph store — node/edge insertion, 1-hop neighbors, in-degree
- Vector store — add + cosine-similarity search, nearest-neighbor correctness
# config/default.yaml
seed: 42
max_pages: 200
alpha: 1.0
discount: 0.98
detector_window: 50
cusum_threshold: 3.0
w_relevance: 0.6
w_novelty: 0.3
w_efficiency: 0.1
offline_topics:
- quantum_hardware
- renewable_energy
- machine_learning_theorypython -m crawler.cli run --seed 99 --max-pages 500 --topic renewable_energycfg = load_config()
print(cfg.config_hash) # → "a3f9b2e1c4d8" (stable SHA-256 prefix)The system is built in 8 steps. Step 1 is complete.
| Step | Status | Deliverable |
|---|---|---|
| 1 | ✅ Done | Repo skeleton, config, interfaces, offline simulator |
| 2 | Next | Fetch layer, feature extraction, GraphSAGE encoder |
| 3 | Pending | GraphUCB-CD bandit, change-point detector, unit tests |
| 4 | Pending | LLM judge, calibration, caching, composite reward |
| 5 | Pending | Hierarchical controller, full integration, JSONL logs |
| 6 | Pending | All baselines + experiment suite + results/ populated |
| 7 | Pending | Report generation (report.md + PDF with real numbers) |
| 8 | Pending | Docker Compose, live crawl, reproducibility check |
This project is licensed under the MIT License — see LICENSE for the full text.
MIT License
Copyright (c) 2025 Bhaskar Kaphle
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.