PageRank & Graph Analytics (v0.88.0+)

pg_ripple v0.88.0 adds a Datalog-native PageRank engine that runs entirely inside PostgreSQL via SPI and the existing Datalog aggregation infrastructure. All scores are persisted in _pg_ripple.pagerank_scores and are queryable with standard SQL — no external process required. v0.90.0 adds WCOJ integration, convergence norm GUC, IVM full-recompute threshold, and Count-Min Sketch approximate top-N. v0.91.0 adds IVM Prometheus gauges and explain_pagerank_json().

Quick Start

-- Load some RDF triples
SELECT pg_ripple.load_ntriples($nt$
  <http://example.org/Alice> <http://xmlns.com/foaf/0.1/knows> <http://example.org/Bob> .
  <http://example.org/Bob>   <http://xmlns.com/foaf/0.1/knows> <http://example.org/Carol> .
  <http://example.org/Carol> <http://xmlns.com/foaf/0.1/knows> <http://example.org/Alice> .
$nt$, 'http://example.org/graph');

-- Run PageRank (default: damping=0.85, 100 iterations)
SELECT node_iri, score
FROM pg_ripple.pagerank_run()
ORDER BY score DESC;

SQL Functions

pg_ripple.pagerank_run(...)

Runs iterative PageRank and persists results. Returns one row per node.

All parameters are optional and can be passed as named arguments (API-03, v0.91.0):

-- Named-argument invocation (recommended for clarity)
SELECT node_iri, score
FROM pg_ripple.pagerank_run(
    damping          => 0.85,
    max_iterations   => 50,
    topic            => 'citation'
);

-- Restrict to a specific named graph, reverse direction
SELECT node_iri, score
FROM pg_ripple.pagerank_run(
    graph_uri  => 'http://example.org/graph1',
    direction  => 'reverse'
)
ORDER BY score DESC LIMIT 20;

pg_ripple.centrality_run(metric text, ...)

Computes an alternative centrality measure and stores results in _pg_ripple.centrality_scores.

Supported metric values: 'betweenness', 'closeness', 'degree', 'pagerank'.

SELECT COUNT(*) FROM pg_ripple.centrality_run('betweenness');
SELECT * FROM _pg_ripple.centrality_scores ORDER BY score DESC LIMIT 10;

pg_ripple.explain_pagerank(node_iri text, top_k int DEFAULT 5)

Returns the score explanation tree for a node — which other nodes contributed how much.

SELECT depth, contributor_iri, contribution, path
FROM pg_ripple.explain_pagerank('<http://example.org/Alice>', 5);

pg_ripple.explain_pagerank_json(node_iri text, top_k int DEFAULT 5) (API-05, v0.91.0)

Returns the same explanation tree as explain_pagerank(), but serialised as a JSONB object. Use this when you need to return the explanation from a PL/pgSQL function or REST handler:

SELECT pg_ripple.explain_pagerank_json('<http://example.org/Alice>');
-- Returns JSONB: {"node_iri": "...", "total_score": 0.023, "contributors": [...]}

-- Useful in REST queries via pg_ripple_http /pagerank/explain/:iri?format=json

pg_ripple.export_pagerank(format text, top_k bigint DEFAULT 10000, topic text DEFAULT '')

Serialises scores in 'csv', 'turtle', 'ntriples', or 'jsonld' format.

SELECT pg_ripple.export_pagerank('turtle', 1000);

pg_ripple.pagerank_queue_stats()

Returns IVM dirty-edge queue metrics useful for monitoring.

SELECT * FROM pg_ripple.pagerank_queue_stats();
-- queued_edges | max_delta | oldest_enqueue | estimated_drain_seconds

pg_ripple.vacuum_pagerank_dirty()

Drains processed entries from _pg_ripple.pagerank_dirty_edges.

pg_ripple.pagerank_find_duplicates(metric text, centrality_threshold float8, fuzzy_threshold float8)

Returns candidate duplicate node pairs detected via centrality + label similarity.

GUC Parameters

Convergence Norm (v0.90.0)

pg_ripple uses the L1 norm (sum of absolute differences) to test convergence between iterations, consistent with NetworkX's default behaviour. The convergence threshold pg_ripple.pagerank_convergence_delta (default 0.0001) is compared against the L1 norm of the score delta vector.

Alternative norms can be selected via the pg_ripple.pagerank_convergence_norm GUC:

-- Match igraph convergence behaviour
SET pg_ripple.pagerank_convergence_norm = 'l2';
SELECT node_iri, score FROM pg_ripple.pagerank_run();

Incremental Refresh Error Bounds (v0.90.0)

The bounded K-hop incremental refresh approximates the full PageRank recomputation. The theoretical error bound after K hops of incremental propagation is:

$$|\Delta \text{score}| \leq \alpha^K \times \max_\text{delta_per_iteration}$$

where $\alpha$ is the damping factor (default 0.85) and $K$ is pagerank_khop_limit (default 30). At K=30:

$$\alpha^{30} = 0.85^{30} \approx 0.0076$$

The maximum error per dirty node is < 1% of the per-iteration delta — acceptable for most use cases. For high-precision applications, use pagerank_run() directly.

Tuning Damping for Your Graph (v0.92.0)

The default damping factor pg_ripple.pagerank_damping = 0.85 was calibrated for citation graphs and the original web (Brin & Page 1998). For other graph types:

• Sparse social graphs (Twitter-style follows): 0.50–0.75 recommended. High damping over-amplifies hub nodes in sparse graphs.
• Citation graphs (papers citing papers): 0.85 (default) is well-suited.
• Knowledge graphs (diverse predicate types): 0.85 is a safe default; consider per-predicate-filtered runs with lower damping for dense predicate subsets.
• Temporal graphs with decay (decay_rate > 0): lower damping (0.70–0.80) reduces the influence of long-range links that may be heavily time-discounted.

-- Tune for sparse social graph
SET pg_ripple.pagerank_damping = 0.65;
SELECT node_iri, score FROM pg_ripple.pagerank_run();

Automatic Full Recompute

When the fraction of stale = true rows in pagerank_scores for a given topic exceeds pg_ripple.pagerank_full_recompute_threshold (default 0.01 = 1%), the next IVM worker cycle automatically triggers a full pagerank_run() for that topic.

-- Lower threshold: trigger full recompute when 0.5% of scores are stale
SET pg_ripple.pagerank_full_recompute_threshold = 0.005;

Count-Min Sketch Parameters (v0.90.0)

The top-K PageRank query path uses a Count-Min Sketch to track approximate frequency distributions without materialising the full score table. Two GUCs control sketch memory:

Memory usage: width × depth × 8 bytes per active topic. With defaults: 2000 × 5 × 8 = 80 KB per topic — negligible even for thousands of topics.

Error bound: with probability $1 - e^{-\text{depth}}$ the frequency estimate overestimates by at most $e / \text{width}$ of the total stream mass.

-- Increase accuracy for large graphs at the cost of more memory
SET pg_ripple.pagerank_sketch_width = 10000;
SET pg_ripple.pagerank_sketch_depth = 7;

REST API (pg_ripple_http)

Storage

Scores are persisted in _pg_ripple.pagerank_scores:

\d _pg_ripple.pagerank_scores
-- node BIGINT, topic TEXT, score FLOAT8,
-- score_lower FLOAT8, score_upper FLOAT8,
-- computed_at TIMESTAMPTZ, iterations INT, converged BOOL,
-- stale BOOL, stale_since TIMESTAMPTZ

The IVM dirty-edge queue (_pg_ripple.pagerank_dirty_edges) tracks which edges changed since the last full run, enabling k-hop incremental refresh (PR-TRICKLE-01).

owl:sameAs Deduplication (v0.92.0)

When owl:sameAs canonicalization is active (v0.23.0), pg_ripple merges entity clusters into a canonical representative before computing PageRank. This deduplication ensures that edges to equivalent entities are not double-counted, which would otherwise inflate the PageRank score of heavily sameAs-clustered nodes.

See Reasoning and Inference for canonicalization details.

Portability Note (STD-04, v0.92.0)

pg:pagerank(), pg:centrality(), and pg:topN_approx() are pg_ripple-specific extension functions. They are not defined by the W3C SPARQL 1.1 specification and are not portable to other SPARQL endpoints (Apache Jena, Virtuoso, Stardog, etc.).

In federated queries, use the full IRI form and ensure the pg_ripple-specific endpoint is the SERVICE target. Federated queries that include pg:pagerank() in a SERVICE block targeting a non-pg_ripple endpoint will fail with SPARQL function not found.

Feature Status

SELECT feature, status, version FROM pg_ripple.feature_status()
WHERE feature LIKE 'pagerank%' OR feature LIKE 'centrality%';

Further reading

• Blog: PageRank in pg_ripple — Datalog-native PageRank with IVM and Prometheus integration