mixle.stats.graphs.hyperedge_replacement_grammar module

Hyperedge-replacement graph grammar (HRG) – a distribution over networks you can score, fit, and sample.

The second main kind of graph grammar (the other is vertex replacement; see vertex_replacement_grammar). A production A -> R rewrites a nonterminal HYPEREDGE labelled A with a ranked tuple of attachment nodes (its tentacles) by a right-hand-side hypergraph R carrying an ordered tuple of rank(A) external nodes; the rewrite fuses R’s external nodes with the hyperedge’s tentacles (so the gluing is intrinsic – no embedding relation, unlike NLC). HRGs are context-free and confluent, with cleaner parsing theory.

Observations are GRAPHS (networkx graphs, all-terminal); the start symbol has rank 0 by default, so a derivation generates a graph with no boundary. The distribution mirrors vertex_replacement_grammar:

• log_density(graph) is the MARGINAL likelihood – the graph is parsed (reduced back to the start symbol by un-applying productions) and scored as the log-sum over all derivations (the inside / sum-product recursion). Exact when the parse forest is fully explored, a lower bound if the budget truncates it, -inf if the grammar cannot derive the graph. best_derivation gives the Viterbi parse.

• sample() runs a real hyperedge-replacement derivation.

• the estimator learns rule FREQUENCIES by Viterbi parse-counting (structure given; induction is out of scope).

class Hypergraph(graph=None, hyperedges=())

Bases: object

A hypergraph: a networkx graph of terminal (rank-2) edges plus a list of nonterminal hyperedges.

graph holds the nodes and terminal edges (with label / node_color / weight / edge_color attributes, as for vertex replacement). hyperedges is a list of (label, tuple_of_attachment_nodes) – the nonterminal hyperedges still to be rewritten.

copy()

Return a structural copy of the terminal graph and nonterminal hyperedges.

class HyperedgeReplacementRule(lhs, rhs, external, frequency=1.0)

Bases: object

A production lhs -> rhs: replace a rank-k nonterminal hyperedge by rhs, fusing externals.

external is the ordered tuple of rhs nodes (length = rank of lhs) fused, in order, with the rewritten hyperedge’s tentacles. frequency weights the production within its left-hand side.

property rank: int

Return the arity of the left-hand-side nonterminal hyperedge.

class HyperedgeReplacementGrammar(name='')

Bases: object

A container of HyperedgeReplacementRule objects keyed by left-hand-side symbol.

add_rule(rule)

Add a production rule and refresh the flattened rule list.

Parameters:

rule (HyperedgeReplacementRule)

Return type:

None

refresh_rules()

Rebuild the flattened rule list and cached rule count.

Return type:

None

generate_graph(grammar, start_symbol, target_n=100, rng=None, start_rank=0)

Generate a graph by a hyperedge-replacement derivation.

Begins with a single nonterminal hyperedge start_symbol on start_rank fresh boundary nodes (default 0 -> no boundary). Repeatedly rewrites a nonterminal hyperedge by one of its symbol’s rules (probability proportional to frequency), fusing the rule’s external nodes onto the hyperedge’s tentacles. target_n is a soft node budget: once reached the derivation prefers terminal-only rules, and any hyperedges left after the step cap are dropped. Returns a networkx graph.

best_derivation(graph, grammar, start_symbol, budget=_PARSE_BUDGET)

Best (Viterbi) hyperedge-replacement derivation of a graph: (log_prob, [rules]) or (-inf, None).

marginal_log_prob(graph, grammar, start_symbol, budget=_PARSE_BUDGET, with_status=False)

Marginal log-likelihood: log-sum over ALL hyperedge-replacement derivations that yield the graph.

Exact when the parse forest is fully explored; a variational lower bound (ELBO) if the budget/depth cap truncates it. with_status returns (value, exact) with exact False iff a cap was hit.

class HyperedgeReplacementGrammarDistribution(grammar, start_symbol=None, orig_n=100, name=None)

Bases: SequenceEncodableProbabilityDistribution

A distribution over GRAPHS parameterised by a hyperedge-replacement grammar.

log_density(graph) is the marginal likelihood (sum over derivations, by parsing); sample() emits graphs by derivation; the estimator learns rule frequencies by Viterbi parse-counting.

density_semantics()

Return that graph densities are lower bounds when parsing is budget-truncated.

density(x)

Return the marginal probability of a graph under the grammar.

log_density(x, with_status=False)

Marginal log-likelihood of graph x (see marginal_log_prob). with_status -> (value, exact).

seq_encode(x)

Return graph observations unchanged for sequence scoring.

seq_log_density(x, with_status=False)

Return vectorized graph log-likelihoods, optionally with exactness flags.

sampler(seed=None)

Return a derivation sampler for this grammar distribution.

estimator(pseudo_count=None)

Return a Viterbi parse-count estimator for this grammar’s rule frequencies.

dist_to_encoder()

Return the identity graph encoder used by vectorized methods.

class HyperedgeReplacementGrammarSampler(grammar, start_symbol=None, orig_n=100, seed=None)

Bases: DistributionSampler

Sample graphs from a hyperedge-replacement grammar by derivation.

sample(size=None, *, batched=True)

Draw one graph or a list of graphs by HRG derivation.

class HyperedgeReplacementGrammarAccumulator(grammar=None, start_symbol=None, keys=None)

Bases: SequenceEncodableStatisticAccumulator

Accumulate Viterbi rule-firing counts: parse each graph and tally how often each rule fires.

update(x, weight, estimate)

Update Viterbi rule counts from one observed graph.

initialize(x, weight, rng)

Initialize rule counts from one observed graph.

seq_initialize(x, weights, rng)

Initialize rule counts from a batch of observed graphs.

seq_update(x, weights, estimate)

Update Viterbi rule counts from a batch of observed graphs.

combine(suff_stat)

Merge rule-frequency counts from another grammar accumulator value.

value()

Return the grammar-shaped rule-count accumulator.

from_value(x)

Restore grammar-shaped rule counts from value output.

key_merge(stats_dict)

Merge this accumulator into stats_dict under its configured key.

key_replace(stats_dict)

Replace this accumulator’s state from keyed statistics when present.

acc_to_encoder()

Return the graph encoder compatible with this accumulator.

class HyperedgeReplacementGrammarAccumulatorFactory(grammar=None, start_symbol=None, keys=None)

Bases: StatisticAccumulatorFactory

Creates accumulators carrying the rule structure whose frequencies are estimated.

make()

Create an empty HRG rule-count accumulator.

class HyperedgeReplacementGrammarEstimator(grammar=None, start_symbol=None, pseudo_count=None, name=None, keys=None)

Bases: ParameterEstimator

Estimate rule FREQUENCIES from graphs by Viterbi parse-counting (the structure is given).

accumulator_factory()

Return a factory for HRG Viterbi rule-count accumulators.

estimate(nobs, suff_stat)

Estimate rule frequencies from accumulated Viterbi parse counts.

class HyperedgeReplacementGrammarDataEncoder

Bases: DataSequenceEncoder

Identity encoder for sequences of observed graphs.

seq_encode(x)

Return graph observations unchanged.