gabfon's picture
Upload folder using huggingface_hub
3e363e2 verified
Raw History Blame Contribute Delete
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
@dataclass(frozen=True)
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)
@property
def entities(self) -> set[str]:
return {head for head, _, _ in self.triples} | {
tail for _, _, tail in self.triples
}
@property
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)
@dataclass(frozen=True)
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"
)