uqa_graph/
cross_paradigm.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Cross-paradigm operators (Sections 3.1-3.3, Paper 2).
8//!
9//! These bridge the document, vector, and graph algebras: build a
10//! graph from a document corpus or from a token-co-occurrence
11//! analysis, score graph traversal results by vector similarity, or
12//! re-rank pattern matches against a query embedding. `FromGraph` is
13//! just [`GraphPostingList::to_posting_list`] — call it directly.
14
15use std::collections::BTreeMap;
16
17use uqa_analysis::{analyzer::standard_analyzer, AnalysisError};
18use uqa_core::{Edge, Payload, PostingEntry, PostingList, Value, Vertex, VertexId};
19
20use crate::memory_store::MemoryGraphStore;
21use crate::operators::{GMatch, Traverse};
22use crate::pattern::GraphPattern;
23use crate::posting_list::{GraphPayload, GraphPostingList, GraphPostingListError};
24use crate::store::{GraphStore, GraphStoreError};
25
26#[derive(Debug, thiserror::Error)]
27pub enum CrossParadigmError {
28    #[error(transparent)]
29    Analysis(#[from] AnalysisError),
30    #[error(transparent)]
31    GraphStore(#[from] GraphStoreError),
32    #[error(transparent)]
33    InvalidPostingList(#[from] GraphPostingListError),
34    #[error("invalid cross-paradigm input: {0}")]
35    InvalidInput(String),
36    #[error("cross-paradigm arithmetic overflow: {0}")]
37    ArithmeticOverflow(String),
38}
39
40pub type CrossParadigmResult<T> = Result<T, CrossParadigmError>;
41
42/// A simple document representation for `ToGraph` / `TextToGraph`.
43#[derive(Debug, Clone, Default)]
44pub struct Document {
45    pub doc_id: VertexId,
46    pub fields: BTreeMap<String, Value>,
47}
48
49impl Document {
50    pub fn new(doc_id: VertexId) -> Self {
51        Self {
52            doc_id,
53            fields: BTreeMap::new(),
54        }
55    }
56}
57
58/// Convert a document corpus into a fresh `MemoryGraphStore`.
59///
60/// One vertex per document under graph `default`, one directed
61/// `link`-labeled edge for each id listed under `edge_field`. Document
62/// fields outside `edge_field` are copied into the vertex's
63/// `properties`.
64pub struct ToGraph {
65    pub documents: Vec<Document>,
66    pub edge_field: String,
67}
68
69impl ToGraph {
70    pub fn new(documents: Vec<Document>) -> Self {
71        Self {
72            documents,
73            edge_field: "links".into(),
74        }
75    }
76
77    pub fn edge_field(mut self, name: impl Into<String>) -> Self {
78        self.edge_field = name.into();
79        self
80    }
81
82    pub fn execute(self) -> CrossParadigmResult<MemoryGraphStore> {
83        let mut graph = MemoryGraphStore::new();
84        graph.create_graph("default");
85        for doc in &self.documents {
86            let mut props: BTreeMap<String, Value> = doc.fields.clone();
87            props.remove(&self.edge_field);
88            graph.add_vertex(
89                Vertex {
90                    vertex_id: doc.doc_id,
91                    label: String::new(),
92                    properties: props,
93                },
94                "default",
95            )?;
96        }
97        let mut edge_counter = 1u64;
98        for doc in &self.documents {
99            let Some(targets) = doc.fields.get(&self.edge_field) else {
100                continue;
101            };
102            let Value::List(items) = targets else {
103                return Err(CrossParadigmError::InvalidInput(format!(
104                    "document {} field {:?} must be a list of integer vertex ids",
105                    doc.doc_id, self.edge_field
106                )));
107            };
108            for target in items {
109                let Value::Int(target_id) = target else {
110                    return Err(CrossParadigmError::InvalidInput(format!(
111                        "document {} field {:?} contains a non-integer vertex id",
112                        doc.doc_id, self.edge_field
113                    )));
114                };
115                let target_id = VertexId::try_from(*target_id).map_err(|_| {
116                    CrossParadigmError::InvalidInput(format!(
117                        "document {} field {:?} contains negative vertex id {target_id}",
118                        doc.doc_id, self.edge_field
119                    ))
120                })?;
121                graph.add_edge(
122                    Edge::new(edge_counter, doc.doc_id, target_id, "link"),
123                    "default",
124                )?;
125                edge_counter = edge_counter.checked_add(1).ok_or_else(|| {
126                    CrossParadigmError::ArithmeticOverflow(
127                        "document link edge id counter overflow".to_string(),
128                    )
129                })?;
130            }
131        }
132        Ok(graph)
133    }
134}
135
136/// Build a token co-occurrence graph from a document corpus.
137///
138/// Each unique token becomes a vertex (label `""`, property `token`).
139/// `window_size == 0` connects every pair of distinct tokens that
140/// appear in the same document; a positive `window_size` only connects
141/// tokens within `window_size` positions of each other. Edges are
142/// labeled `co_occurs` and carry a `weight` property equal to the
143/// total co-occurrence count.
144pub struct TextToGraph {
145    pub documents: Vec<Document>,
146    pub text_field: String,
147    pub window_size: usize,
148    pub language: String,
149}
150
151impl TextToGraph {
152    pub fn new(documents: Vec<Document>) -> Self {
153        Self {
154            documents,
155            text_field: "text".into(),
156            window_size: 0,
157            language: "english".into(),
158        }
159    }
160
161    pub fn text_field(mut self, name: impl Into<String>) -> Self {
162        self.text_field = name.into();
163        self
164    }
165
166    pub fn window_size(mut self, w: usize) -> Self {
167        self.window_size = w;
168        self
169    }
170
171    pub fn language(mut self, lang: impl Into<String>) -> Self {
172        self.language = lang.into();
173        self
174    }
175
176    pub fn execute(self) -> CrossParadigmResult<MemoryGraphStore> {
177        let analyzer = standard_analyzer(&self.language);
178        let mut token_set: std::collections::BTreeSet<String> = std::collections::BTreeSet::new();
179        let mut cooccurrences: BTreeMap<(String, String), u64> = BTreeMap::new();
180
181        for doc in &self.documents {
182            let text = match doc.fields.get(&self.text_field) {
183                Some(Value::Str(s)) => s.clone(),
184                _ => String::new(),
185            };
186            let tokens = analyzer.analyze(&text)?;
187            for token in &tokens {
188                token_set.insert(token.clone());
189            }
190            if self.window_size == 0 {
191                let mut unique: Vec<String> = tokens.clone();
192                unique.sort();
193                unique.dedup();
194                for i in 0..unique.len() {
195                    for j in (i + 1)..unique.len() {
196                        let pair = (unique[i].clone(), unique[j].clone());
197                        increment_cooccurrence(&mut cooccurrences, pair)?;
198                    }
199                }
200            } else {
201                for i in 0..tokens.len() {
202                    let end = i
203                        .saturating_add(self.window_size)
204                        .saturating_add(1)
205                        .min(tokens.len());
206                    for j in (i + 1)..end {
207                        if tokens[i] == tokens[j] {
208                            continue;
209                        }
210                        let (a, b) = if tokens[i] < tokens[j] {
211                            (tokens[i].clone(), tokens[j].clone())
212                        } else {
213                            (tokens[j].clone(), tokens[i].clone())
214                        };
215                        increment_cooccurrence(&mut cooccurrences, (a, b))?;
216                    }
217                }
218            }
219        }
220
221        let mut graph = MemoryGraphStore::new();
222        graph.create_graph("default");
223        let mut token_to_id: BTreeMap<String, VertexId> = BTreeMap::new();
224        for (idx, token) in token_set.iter().enumerate() {
225            let vid = VertexId::try_from(idx)
226                .ok()
227                .and_then(|value| value.checked_add(1))
228                .ok_or_else(|| {
229                    CrossParadigmError::ArithmeticOverflow(
230                        "token vertex id counter overflow".to_string(),
231                    )
232                })?;
233            token_to_id.insert(token.clone(), vid);
234            let mut props = BTreeMap::new();
235            props.insert("token".into(), Value::Str(token.clone()));
236            graph.add_vertex(
237                Vertex {
238                    vertex_id: vid,
239                    label: String::new(),
240                    properties: props,
241                },
242                "default",
243            )?;
244        }
245        for (index, ((t1, t2), weight)) in cooccurrences.into_iter().enumerate() {
246            let edge_counter = u64::try_from(index)
247                .ok()
248                .and_then(|value| value.checked_add(1))
249                .ok_or_else(|| {
250                    CrossParadigmError::ArithmeticOverflow(
251                        "co-occurrence edge id counter overflow".to_string(),
252                    )
253                })?;
254            let src = token_to_id.get(&t1).copied().ok_or_else(|| {
255                CrossParadigmError::InvalidInput(format!("missing token vertex for {t1:?}"))
256            })?;
257            let tgt = token_to_id.get(&t2).copied().ok_or_else(|| {
258                CrossParadigmError::InvalidInput(format!("missing token vertex for {t2:?}"))
259            })?;
260            let mut edge = Edge::new(edge_counter, src, tgt, "co_occurs");
261            let weight = i64::try_from(weight).map_err(|_| {
262                CrossParadigmError::ArithmeticOverflow(format!(
263                    "co-occurrence weight {weight} exceeds i64"
264                ))
265            })?;
266            edge.properties.insert("weight".into(), Value::Int(weight));
267            graph.add_edge(edge, "default")?;
268        }
269        Ok(graph)
270    }
271}
272
273/// Per-vertex cosine similarity to a query embedding. Reads the named
274/// vector property and emits a standard `PostingList` keyed by vertex
275/// id, with the cosine score on the payload.
276pub struct VertexEmbedding<'a> {
277    pub graph: &'a str,
278    pub query_vector: Vec<f64>,
279    pub vector_field: String,
280    pub threshold: f64,
281}
282
283impl<'a> VertexEmbedding<'a> {
284    pub fn new(graph: &'a str, query_vector: Vec<f64>) -> Self {
285        Self {
286            graph,
287            query_vector,
288            vector_field: "embedding".into(),
289            threshold: 0.0,
290        }
291    }
292
293    pub fn vector_field(mut self, name: impl Into<String>) -> Self {
294        self.vector_field = name.into();
295        self
296    }
297
298    pub fn threshold(mut self, t: f64) -> Self {
299        self.threshold = t;
300        self
301    }
302
303    pub fn execute<G: GraphStore>(&self, store: &G) -> CrossParadigmResult<PostingList> {
304        validate_vector_query(&self.query_vector, self.threshold)?;
305        let mut entries: Vec<PostingEntry> = Vec::new();
306        let mut ids: Vec<VertexId> = store.vertex_ids_in_graph(self.graph)?.into_iter().collect();
307        ids.sort_unstable();
308        for vid in ids {
309            let Some(vertex) = store.get_vertex(vid) else {
310                return Err(GraphStoreError::CorruptGraph(format!(
311                    "graph {:?} references missing vertex {vid}",
312                    self.graph
313                ))
314                .into());
315            };
316            let Some(vec) = read_vector(&vertex.properties, &self.vector_field)? else {
317                continue;
318            };
319            let sim = cosine_similarity(&self.query_vector, &vec)?;
320            if sim >= self.threshold {
321                entries.push(PostingEntry::new(vid, Payload::with_score(sim)));
322            }
323        }
324        Ok(PostingList::from_sorted_unchecked(entries))
325    }
326}
327
328/// `Traverse` followed by a vector-similarity filter: keep only the
329/// vertices whose `vector_field` similarity to `query_vector` clears
330/// `threshold`. The retained entries' scores are the cosine values.
331pub struct SemanticGraphSearch<'a> {
332    pub graph: &'a str,
333    pub start_vertex: VertexId,
334    pub label: Option<&'a str>,
335    pub max_hops: u32,
336    pub query_vector: Vec<f64>,
337    pub vector_field: String,
338    pub threshold: f64,
339}
340
341impl<'a> SemanticGraphSearch<'a> {
342    pub fn new(graph: &'a str, start_vertex: VertexId, query_vector: Vec<f64>) -> Self {
343        Self {
344            graph,
345            start_vertex,
346            label: None,
347            max_hops: 1,
348            query_vector,
349            vector_field: "embedding".into(),
350            threshold: 0.5,
351        }
352    }
353
354    pub fn label(mut self, label: &'a str) -> Self {
355        self.label = Some(label);
356        self
357    }
358
359    pub fn max_hops(mut self, hops: u32) -> Self {
360        self.max_hops = hops;
361        self
362    }
363
364    pub fn vector_field(mut self, name: impl Into<String>) -> Self {
365        self.vector_field = name.into();
366        self
367    }
368
369    pub fn threshold(mut self, t: f64) -> Self {
370        self.threshold = t;
371        self
372    }
373
374    pub fn execute<G: GraphStore>(&self, store: &G) -> CrossParadigmResult<GraphPostingList> {
375        validate_vector_query(&self.query_vector, self.threshold)?;
376        let mut traverse = Traverse::new(self.start_vertex, self.graph).max_hops(self.max_hops);
377        if let Some(l) = self.label {
378            traverse = traverse.label(l);
379        }
380        let gpl = traverse.execute(store)?;
381        let mut entries: Vec<PostingEntry> = Vec::new();
382        let mut graph_payloads: BTreeMap<VertexId, GraphPayload> = BTreeMap::new();
383        for entry in gpl.inner().entries() {
384            let Some(vertex) = store.get_vertex(entry.doc_id) else {
385                return Err(GraphStoreError::CorruptGraph(format!(
386                    "traversal returned missing vertex {}",
387                    entry.doc_id
388                ))
389                .into());
390            };
391            let Some(vec) = read_vector(&vertex.properties, &self.vector_field)? else {
392                continue;
393            };
394            let sim = cosine_similarity(&self.query_vector, &vec)?;
395            if sim < self.threshold {
396                continue;
397            }
398            entries.push(PostingEntry::new(entry.doc_id, Payload::with_score(sim)));
399            if let Some(gp) = gpl.get_graph_payload(entry.doc_id) {
400                let mut copy = gp.clone();
401                copy.score_override = Some(sim);
402                graph_payloads.insert(entry.doc_id, copy);
403            }
404        }
405        GraphPostingList::try_from_parts(
406            PostingList::from_sorted_unchecked(entries),
407            graph_payloads,
408        )
409        .map_err(Into::into)
410    }
411}
412
413/// `GMatch` followed by a per-match cosine filter against the vertex
414/// bound to `score_variable`. Matches with similarity below
415/// `threshold` are dropped; surviving entries take the cosine value as
416/// their score.
417pub struct VectorEnhancedMatch<'a> {
418    pub graph: &'a str,
419    pub pattern: GraphPattern,
420    pub query_vector: Vec<f64>,
421    pub score_variable: String,
422    pub vector_field: String,
423    pub threshold: f64,
424}
425
426impl<'a> VectorEnhancedMatch<'a> {
427    pub fn new(
428        graph: &'a str,
429        pattern: GraphPattern,
430        query_vector: Vec<f64>,
431        score_variable: impl Into<String>,
432    ) -> Self {
433        Self {
434            graph,
435            pattern,
436            query_vector,
437            score_variable: score_variable.into(),
438            vector_field: "embedding".into(),
439            threshold: 0.0,
440        }
441    }
442
443    pub fn vector_field(mut self, name: impl Into<String>) -> Self {
444        self.vector_field = name.into();
445        self
446    }
447
448    pub fn threshold(mut self, t: f64) -> Self {
449        self.threshold = t;
450        self
451    }
452
453    pub fn execute<G: GraphStore>(&self, store: &G) -> CrossParadigmResult<GraphPostingList> {
454        validate_vector_query(&self.query_vector, self.threshold)?;
455        let match_op = GMatch::new(self.pattern.clone(), self.graph);
456        let result = match_op.execute(store)?;
457        let mut entries: Vec<PostingEntry> = Vec::new();
458        let mut graph_payloads: BTreeMap<VertexId, GraphPayload> = BTreeMap::new();
459        for entry in result.inner().entries() {
460            let Some(Value::Int(vid_i)) = entry.payload.fields.get(&self.score_variable) else {
461                continue;
462            };
463            let vid = VertexId::try_from(*vid_i).map_err(|_| {
464                CrossParadigmError::InvalidInput(format!(
465                    "match variable {:?} contains invalid vertex id {vid_i}",
466                    self.score_variable
467                ))
468            })?;
469            let Some(vertex) = store.get_vertex(vid) else {
470                return Err(GraphStoreError::CorruptGraph(format!(
471                    "match variable {:?} references missing vertex {vid}",
472                    self.score_variable
473                ))
474                .into());
475            };
476            let Some(vec) = read_vector(&vertex.properties, &self.vector_field)? else {
477                continue;
478            };
479            let sim = cosine_similarity(&self.query_vector, &vec)?;
480            if sim < self.threshold {
481                continue;
482            }
483            entries.push(PostingEntry::new(
484                entry.doc_id,
485                Payload {
486                    positions: Vec::new(),
487                    score: sim,
488                    fields: entry.payload.fields.clone(),
489                },
490            ));
491            if let Some(gp) = result.get_graph_payload(entry.doc_id) {
492                let mut copy = gp.clone();
493                copy.score_override = Some(sim);
494                graph_payloads.insert(entry.doc_id, copy);
495            }
496        }
497        GraphPostingList::try_from_parts(
498            PostingList::from_sorted_unchecked(entries),
499            graph_payloads,
500        )
501        .map_err(Into::into)
502    }
503}
504
505fn increment_cooccurrence(
506    cooccurrences: &mut BTreeMap<(String, String), u64>,
507    pair: (String, String),
508) -> CrossParadigmResult<()> {
509    let count = cooccurrences.entry(pair).or_insert(0);
510    *count = count.checked_add(1).ok_or_else(|| {
511        CrossParadigmError::ArithmeticOverflow("co-occurrence counter overflow".to_string())
512    })?;
513    Ok(())
514}
515
516fn validate_vector_query(query: &[f64], threshold: f64) -> CrossParadigmResult<()> {
517    if query.is_empty() {
518        return Err(CrossParadigmError::InvalidInput(
519            "query vector must not be empty".to_string(),
520        ));
521    }
522    if query.iter().any(|value| !value.is_finite()) || !threshold.is_finite() {
523        return Err(CrossParadigmError::InvalidInput(
524            "query vector and threshold must be finite".to_string(),
525        ));
526    }
527    Ok(())
528}
529
530fn read_vector(
531    properties: &BTreeMap<String, Value>,
532    field: &str,
533) -> CrossParadigmResult<Option<Vec<f64>>> {
534    let Some(value) = properties.get(field) else {
535        return Ok(None);
536    };
537    let Value::List(items) = value else {
538        return Err(CrossParadigmError::InvalidInput(format!(
539            "vector field {field:?} must be a list"
540        )));
541    };
542    let mut out = Vec::with_capacity(items.len());
543    for v in items {
544        match v {
545            Value::Float(f) if f.is_finite() => out.push(*f),
546            Value::Int(n) if n.unsigned_abs() <= (1_u64 << 53) => out.push(*n as f64),
547            Value::Int(n) => {
548                return Err(CrossParadigmError::InvalidInput(format!(
549                    "integer vector component {n} cannot be represented exactly as f64"
550                )));
551            }
552            _ => {
553                return Err(CrossParadigmError::InvalidInput(format!(
554                    "vector field {field:?} contains a non-numeric or non-finite component"
555                )));
556            }
557        }
558    }
559    Ok(Some(out))
560}
561
562fn cosine_similarity(a: &[f64], b: &[f64]) -> CrossParadigmResult<f64> {
563    if a.len() != b.len() || a.is_empty() {
564        return Err(CrossParadigmError::InvalidInput(format!(
565            "cosine vectors must have the same non-zero dimension ({} != {})",
566            a.len(),
567            b.len()
568        )));
569    }
570    let mut dot = 0.0;
571    let mut na = 0.0;
572    let mut nb = 0.0;
573    for i in 0..a.len() {
574        dot += a[i] * b[i];
575        na += a[i] * a[i];
576        nb += b[i] * b[i];
577    }
578    if na == 0.0 || nb == 0.0 {
579        return Err(CrossParadigmError::InvalidInput(
580            "cosine vectors must have non-zero norm".to_string(),
581        ));
582    }
583    let similarity = dot / (na.sqrt() * nb.sqrt());
584    if !similarity.is_finite() {
585        return Err(CrossParadigmError::InvalidInput(
586            "cosine similarity is non-finite".to_string(),
587        ));
588    }
589    Ok(similarity)
590}
uqa_graph/cross_paradigm.rs

uqa_graph/
cross_paradigm.rs
