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()

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

class HyperedgeReplacementGrammar(name='')

Bases: object

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

add_rule(rule)

Parameters:

rule (HyperedgeReplacementRule)

Return type:

None

refresh_rules()

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()

What log_density returns relative to the true log-density (default: exact).

Override to declare that this distribution’s log_density is a variational lower bound (ELBO), an upper bound, or an approximation rather than the exact log p(x). This is surfaced as the ExactDensity capability and noted in mixle.describe(), so code that needs an exact likelihood can require(x, ExactDensity) instead of silently trusting a bound.

density(x)

Return the probability density or mass at a single observation.

Concrete default: exponentiate log_density (the abstract method subclasses must provide). Leaves with a cheaper closed form may override this.

log_density(x, with_status=False)

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

seq_encode(x)

seq_log_density(x, with_status=False)

Return vectorized log-density values for sequence-encoded observations.

sampler(seed=None)

Return a sampler for drawing observations from this distribution.

estimator(pseudo_count=None)

Return an estimator for fitting this distribution from data.

dist_to_encoder()

Return the data encoder used by this distribution for 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 observations.

Combinator samplers (mixture/sequence/…) accept batched. With batched=True (the default) each child stream is drawn in one vectorized call instead of a per-draw Python loop – far faster. Because every child sampler owns an independent RandomState, batching consumes each stream in the same order as the loop, so the draws are identical to the legacy path. batched=False forces that legacy per-draw loop as a guaranteed- stable reference. Leaf samplers are already vectorized and ignore the flag.

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)

initialize(x, weight, rng)

seq_initialize(x, weights, rng)

seq_update(x, weights, estimate)

combine(suff_stat)

value()

from_value(x)

key_merge(stats_dict)

Pool this accumulator’s statistics into stats_dict under its merge key.

The structural default implements the common single-key pattern: store the accumulator under self.keys the first time the key is seen, else combine into the one already there. Accumulators with several named keys (e.g. an HMM’s init/trans/state keys) or a non-accumulator stats payload override this. A keys of None (the default) is a no-op.

key_replace(stats_dict)

Replace this accumulator’s statistics from the pooled stats_dict entry (see key_merge).

acc_to_encoder()

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

Bases: StatisticAccumulatorFactory

Creates accumulators carrying the rule structure whose frequencies are estimated.

make()

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()

estimate(nobs, suff_stat)

class HyperedgeReplacementGrammarDataEncoder

Bases: DataSequenceEncoder

Identity encoder for sequences of observed graphs.

seq_encode(x)

Encode the iid observation sequence x for vectorized evaluation.