Download code/graph/real/kg.py from frontal-labs/graph-reasoner-typed-compositional: direct link, hf CLI and curl.
- Browser
- Download file 12.8 kB
-
https://huggingface.co/frontal-labs/graph-reasoner-typed-compositional/resolve/main/code/graph/real/kg.py
- Command line
-
hf download hf://frontal-labs/graph-reasoner-typed-compositional/code/graph/real/kg.py
-
curl -L -o kg.py https://huggingface.co/frontal-labs/graph-reasoner-typed-compositional/resolve/main/code/graph/real/kg.py
12.8 kB
| """Real multi-relational knowledge graphs: FB15k-237 and WN18RR. | |
| These are the standard benchmarks for multi-relational reasoning, and they supply | |
| what synthetic graphs cannot: real entity distributions, real relation semantics, | |
| and heavy-tailed degrees with hub entities that genuinely mislead a search. | |
| Queries are relation compositions sampled from the graph, which is the | |
| established complex-query-answering setup. Note what this does and does not | |
| measure: the composition is given, so the difficulty is traversal and answer | |
| selection under real branching, not inferring intent from language. The | |
| HotpotQA workload covers intent inference. | |
| Because a full KG is far larger than one reasoning query needs, each query | |
| carries an extracted *neighbourhood* rather than the whole graph, which is the | |
| graph-local expansion PLAN sections 48 and 49 require. | |
| """ | |
| from __future__ import annotations | |
| import json | |
| import random | |
| from collections import Counter, defaultdict | |
| from collections.abc import Iterator, Mapping, Sequence | |
| from dataclasses import dataclass, field | |
| from pathlib import Path | |
| from graph.graph import EdgeRecord, GraphStore | |
| from graph.types import GraphPath, GraphQuery, PathStep, ReasoningStatus | |
| #: Relations whose target is functionally determined, used for contradiction | |
| #: detection. Real KGs do not ship cardinality metadata, so it is inferred from | |
| #: the data: a relation is treated as functional when almost every subject that | |
| #: uses it has exactly one object. | |
| FUNCTIONAL_THRESHOLD = 0.98 | |
| class KnowledgeGraphDataset: | |
| """Triples plus derived indices for one real KG split.""" | |
| name: str | |
| triples: tuple[tuple[str, str, str], ...] | |
| entity_names: Mapping[str, str] = field(default_factory=dict) | |
| def entities(self) -> set[str]: | |
| return {head for head, _, _ in self.triples} | { | |
| tail for _, _, tail in self.triples | |
| } | |
| def relations(self) -> set[str]: | |
| return {relation for _, relation, _ in self.triples} | |
| def outgoing(self) -> Mapping[str, tuple[tuple[str, str], ...]]: | |
| index: dict[str, list[tuple[str, str]]] = defaultdict(list) | |
| for head, relation, tail in self.triples: | |
| index[head].append((relation, tail)) | |
| return {key: tuple(value) for key, value in index.items()} | |
| def functional_relations(self) -> frozenset[str]: | |
| """Infer which relations are single-valued from the data itself.""" | |
| counts: dict[str, Counter[str]] = defaultdict(Counter) | |
| for head, relation, _ in self.triples: | |
| counts[relation][head] += 1 | |
| functional: set[str] = set() | |
| for relation, subjects in counts.items(): | |
| if not subjects: | |
| continue | |
| single = sum(1 for value in subjects.values() if value == 1) | |
| if single / len(subjects) >= FUNCTIONAL_THRESHOLD: | |
| functional.add(relation) | |
| return frozenset(functional) | |
| def label(self, entity: str) -> str: | |
| """Human-readable entity label when the dataset ships one.""" | |
| return self.entity_names.get(entity, entity) | |
| def statistics(self) -> dict[str, int | float]: | |
| degrees = Counter(head for head, _, _ in self.triples) | |
| values = sorted(degrees.values(), reverse=True) | |
| return { | |
| "triples": len(self.triples), | |
| "entities": len(self.entities), | |
| "relations": len(self.relations), | |
| "functional_relations": len(self.functional_relations()), | |
| "max_out_degree": values[0] if values else 0, | |
| "mean_out_degree": sum(values) / len(values) if values else 0.0, | |
| "p99_out_degree": values[max(0, len(values) // 100)] if values else 0, | |
| } | |
| def load_knowledge_graph( | |
| directory: str | Path, *, splits: Sequence[str] = ("train", "valid", "test") | |
| ) -> KnowledgeGraphDataset: | |
| """Read tab-separated ``head<TAB>relation<TAB>tail`` triples.""" | |
| root = Path(directory) | |
| if not root.is_dir(): | |
| raise FileNotFoundError( | |
| f"{root} is not a directory; download the dataset first" | |
| ) | |
| triples: list[tuple[str, str, str]] = [] | |
| for split in splits: | |
| path = root / f"{split}.txt" | |
| if not path.exists(): | |
| continue | |
| for line in path.read_text(encoding="utf-8").splitlines(): | |
| parts = line.split("\t") | |
| if len(parts) != 3: | |
| continue | |
| triples.append((parts[0], parts[1], parts[2])) | |
| if not triples: | |
| raise ValueError(f"{root} contained no triples in splits {list(splits)}") | |
| names: dict[str, str] = {} | |
| mapping = root / "entity2wikidata.json" | |
| if mapping.exists(): | |
| raw = json.loads(mapping.read_text(encoding="utf-8")) | |
| names = { | |
| key: value.get("label") or key | |
| for key, value in raw.items() | |
| if isinstance(value, dict) | |
| } | |
| return KnowledgeGraphDataset(root.name, tuple(triples), names) | |
| class KGQueryExample: | |
| """One composition query over an extracted real-KG neighbourhood.""" | |
| example_id: str | |
| graph: GraphStore | |
| query: GraphQuery | |
| answers: tuple[str, ...] | |
| supporting_paths: tuple[GraphPath, ...] | |
| competing_paths: tuple[GraphPath, ...] | |
| composition: tuple[str, ...] | |
| start_id: str | |
| status: ReasoningStatus | |
| neighbourhood_nodes: int | |
| neighbourhood_edges: int | |
| def _relation_type(relation: str) -> str: | |
| """Coarse entity type proxy derived from the relation string. | |
| FB15k-237 relation names encode a type path | |
| (``/location/country/form_of_government``); WN18RR entities encode a | |
| part-of-speech suffix (``reform.n.01``). Neither dataset ships entity types, | |
| so a proxy is derived rather than inventing one, and the proxy is documented | |
| as such rather than presented as ground truth. | |
| """ | |
| stripped = relation.strip("/") | |
| return stripped.split("/")[0] if "/" in stripped else "entity" | |
| def _entity_type(entity: str) -> str: | |
| if "." in entity and entity.count(".") >= 2: | |
| # WN18RR: lemma.pos.sense | |
| return f"wn_{entity.split('.')[-2]}" | |
| return "entity" | |
| def extract_neighbourhood( | |
| dataset: KnowledgeGraphDataset, | |
| outgoing: Mapping[str, tuple[tuple[str, str], ...]], | |
| start: str, | |
| hops: int, | |
| *, | |
| max_branch: int, | |
| max_nodes: int, | |
| rng: random.Random, | |
| ) -> GraphStore: | |
| """Breadth-first neighbourhood around ``start``, bounded for tractability. | |
| Real hubs have out-degrees in the thousands; an unbounded expansion would | |
| pull most of the graph into one query. Branch sampling is what keeps the | |
| workload graph-local while preserving real topology locally. | |
| """ | |
| frontier = [start] | |
| seen = {start} | |
| edges: list[EdgeRecord] = [] | |
| functional = dataset.functional_relations() | |
| for _ in range(hops + 1): | |
| next_frontier: list[str] = [] | |
| for node in frontier: | |
| candidates = list(outgoing.get(node, ())) | |
| if len(candidates) > max_branch: | |
| candidates = rng.sample(candidates, max_branch) | |
| for relation, tail in candidates: | |
| edges.append( | |
| EdgeRecord( | |
| source_id=node, | |
| relation_id=relation, | |
| target_id=tail, | |
| source_type=_entity_type(node), | |
| target_type=_entity_type(tail), | |
| relation_name=relation, | |
| attributes={}, | |
| ) | |
| ) | |
| if tail not in seen and len(seen) < max_nodes: | |
| seen.add(tail) | |
| next_frontier.append(tail) | |
| frontier = next_frontier | |
| if not frontier: | |
| break | |
| nodes = {node: _entity_type(node) for node in seen} | |
| kept = [ | |
| edge for edge in edges if edge.source_id in nodes and edge.target_id in nodes | |
| ] | |
| return GraphStore( | |
| nodes, | |
| kept, | |
| graph_version=f"{dataset.name}@{start}", | |
| relation_attributes={ | |
| relation: { | |
| "functional": str(relation in functional).lower(), | |
| "type_path": _relation_type(relation), | |
| } | |
| for relation in {edge.relation_id for edge in kept} | |
| }, | |
| ) | |
| def _walk_composition( | |
| graph: GraphStore, start: str, composition: Sequence[str] | |
| ) -> tuple[GraphPath, ...]: | |
| results: list[GraphPath] = [] | |
| def walk( | |
| node: str, index: int, steps: tuple[PathStep, ...], visited: frozenset[str] | |
| ) -> None: | |
| if index == len(composition): | |
| results.append(GraphPath(steps=steps)) | |
| return | |
| for edge in graph.outgoing(node): | |
| if edge.relation_id != composition[index] or edge.target_id in visited: | |
| continue | |
| walk( | |
| edge.target_id, | |
| index + 1, | |
| ( | |
| *steps, | |
| PathStep( | |
| source_id=edge.source_id, | |
| relation_id=edge.relation_id, | |
| target_id=edge.target_id, | |
| source_type=edge.source_type, | |
| target_type=edge.target_type, | |
| edge_attributes=edge.attributes, | |
| ), | |
| ), | |
| visited | {edge.target_id}, | |
| ) | |
| walk(start, 0, (), frozenset({start})) | |
| return tuple(results) | |
| def sample_composition_queries( | |
| dataset: KnowledgeGraphDataset, | |
| *, | |
| count: int = 100, | |
| hops: int = 2, | |
| seed: int = 0, | |
| max_branch: int = 12, | |
| max_nodes: int = 400, | |
| max_attempts_per_query: int = 60, | |
| ) -> Iterator[KGQueryExample]: | |
| """Sample answerable ``hops``-length composition queries from the real KG.""" | |
| rng = random.Random(seed) | |
| outgoing = dataset.outgoing() | |
| starts = [node for node, edges in outgoing.items() if edges] | |
| if not starts: | |
| raise ValueError(f"{dataset.name} has no outgoing edges") | |
| produced = 0 | |
| attempts = 0 | |
| while produced < count and attempts < count * max_attempts_per_query: | |
| attempts += 1 | |
| start = starts[rng.randrange(len(starts))] | |
| # Walk a real path to obtain a composition that is guaranteed answerable. | |
| composition: list[str] = [] | |
| node = start | |
| for _ in range(hops): | |
| options = outgoing.get(node, ()) | |
| if not options: | |
| break | |
| relation, tail = options[rng.randrange(len(options))] | |
| composition.append(relation) | |
| node = tail | |
| if len(composition) != hops: | |
| continue | |
| graph = extract_neighbourhood( | |
| dataset, | |
| outgoing, | |
| start, | |
| hops, | |
| max_branch=max_branch, | |
| max_nodes=max_nodes, | |
| rng=rng, | |
| ) | |
| supporting = _walk_composition(graph, start, composition) | |
| if not supporting: | |
| continue | |
| answers = tuple( | |
| dict.fromkeys(path.endpoint_id for path in supporting if path.endpoint_id) | |
| ) | |
| competing = tuple( | |
| path | |
| for path in graph.iter_paths((start,), hops) | |
| if path.hop_count == hops | |
| and tuple(path.relation_sequence) != tuple(composition) | |
| )[:32] | |
| label = dataset.label(start) | |
| # The composition is supplied as an explicit constraint: this workload | |
| # measures traversal and selection at real scale, not intent inference. | |
| query = GraphQuery( | |
| text=( | |
| f"Which entities are reached from {label} by following " | |
| f"{' then '.join(composition)}?" | |
| ), | |
| start_entities=(start,), | |
| start_entity_ids=(start,), | |
| required_relation_sequence=tuple(composition), | |
| min_hops=hops, | |
| max_hops=hops, | |
| exact_hops=hops, | |
| return_paths=True, | |
| verify=True, | |
| operation="find_entities", | |
| answer_mode="entity", | |
| ) | |
| yield KGQueryExample( | |
| example_id=f"{dataset.name}-{hops}hop-{produced}", | |
| graph=graph, | |
| query=query, | |
| answers=answers, | |
| supporting_paths=supporting, | |
| competing_paths=competing, | |
| composition=tuple(composition), | |
| start_id=start, | |
| status=ReasoningStatus.SUPPORTED, | |
| neighbourhood_nodes=len(graph.nodes), | |
| neighbourhood_edges=len(graph.edges), | |
| ) | |
| produced += 1 | |
| if produced < count: | |
| raise RuntimeError( | |
| f"only sampled {produced}/{count} answerable {hops}-hop queries from " | |
| f"{dataset.name} after {attempts} attempts" | |
| ) | |