mixle.stats.graphs.vertex_replacement_grammar module

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

A node-label-controlled (NLC) vertex-replacement grammar: each rule rewrites a single nonterminal NODE with a right-hand-side graph and reconnects it to the replaced node’s former neighbours via an NLC embedding relation (pairs of (neighbour_label, rhs_node_label)). This is one kind of graph grammar; the other main kind – hyperedge replacement – lives in hyperedge_replacement_grammar.

Observations are GRAPHS (networkx graphs); the model is parameterised by a VertexReplacementGrammar.

• log_density(graph) is the grammar’s MARGINAL likelihood: the graph is parsed (reduced back to the start symbol along the productions) and the score is the log-sum over ALL derivations that yield it (the inside / sum-product recursion, marginal_log_prob). It is exact when the parse forest is fully explored, a variational lower bound (ELBO) if the budget truncates it, and -inf if the grammar cannot derive the graph. best_derivation gives the single best (Viterbi) parse.

• sample() runs a real vertex-replacement derivation, so sampling and scoring share one space.

• the estimator learns rule FREQUENCIES from graphs by Viterbi parse-counting (the rule structure is given; inducing the structure from graphs is a separate problem, out of scope).

Defines VertexReplacementRule, VertexReplacementGrammar, and the VertexReplacementGrammar{Distribution,Sampler,Estimator,Accumulator,AccumulatorFactory,DataEncoder} classes. Pre-0.4 generic Grammar* spellings remain as aliases.

class VertexReplacementRule(lhs, graph, frequency=1.0, embedding=None)

Bases: object

A node-replacement rule: rewrite a nonterminal node with graph, then reconnect via embedding.

The right-hand side graph is a networkx graph whose nodes are terminals (carrying label / node_color) or nonterminals (carrying a nonterminal attribute equal to some rule’s left-hand side, enabling recursive derivation). embedding is an NLC-style connection relation: an iterable of (neighbour_label, rhs_node_label) pairs. When this rule replaces a node v, each former neighbour u of v is reconnected to every right-hand-side node w with (label(u), label(w)) in the relation (the original edge data is preserved). embedding=None means “no relation given”: each former neighbour is connected to the right-hand side’s canonical connector (its first node), which keeps derivations connected.

property embedding_relation

The embedding as a set of (neighbour_label, rhs_node_label) tuples (empty if None).

class VertexReplacementGrammar(grammar_type='mu_level_dl', clustering='leiden', name='', mu=4)

Bases: object

Small in-tree node-replacement grammar container.

add_rule(rule)

Parameters:

rule (VertexReplacementRule)

Return type:

None

refresh_rules()

Return type:

None

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

Best (Viterbi) derivation of a graph under the grammar: parse by reducing to the start symbol.

Repeatedly un-applies rules (_reductions) until a single start_symbol node remains, searching for the reduction sequence of highest probability prod freq(rule)/total(lhs). Returns (log_probability, [rules applied in derivation order]); (-inf, None) if the graph cannot be reduced to the start symbol (the grammar does not generate it) or the search budget is exhausted.

This is the max over derivations, a tractable lower bound on the exact likelihood (sum over all derivations), which is intractable – general graph-grammar parsing is NP-hard.

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

Marginal log-likelihood of a graph: log-sum over ALL derivations that yield it.

This is the inside (sum-product) recursion over the reduction state graph – identical to best_derivation but combining a state’s children with logsumexp instead of max, so it sums prod freq(rule)/total(lhs) over every parse rather than taking the single best one. It is therefore >= the Viterbi value and equals the EXACT marginal when the whole parse forest is explored.

The search is bounded by budget (reduction expansions) and a recursion depth of 3n+10. If either cap is reached the forest is truncated and the result is the log-sum over the explored parses – a variational ELBO (the tightest bound for a posterior on that set), still >= Viterbi. For acyclic grammars on graphs that fit the budget, neither cap is hit and the value is exact.

Parameters:

with_status – if True, return (value, exact) where exact is False iff a cap was reached (so the value may be a lower bound); if False, return just value.

Returns -inf if the grammar cannot derive the graph at all.

decomp_pair(sub_rule, method='connected')

Decompose a sub-rule graph into connected components.

This conservative fallback leaves connected graphs unchanged and produces one sub-rule per connected component for disconnected graphs.

generate_graph(rule_dict, target_n=100, rng=None, start_symbol=None)

Generate a graph by a node-label-controlled (NLC) vertex-replacement derivation.

Starts from a single nonterminal node carrying start_symbol (default: the left-hand side with the most total rule frequency). Repeatedly picks a nonterminal node, chooses one of its symbol’s rules with probability proportional to frequency, deletes the node, splices in a fresh copy of the rule’s right-hand side, and reconnects the deleted node’s former neighbours via the rule’s embedding relation. Derivation is recursive: right-hand sides may themselves carry nonterminal nodes.

target_n is a soft node budget, not an exact size: once it is reached the derivation prefers terminal-only rules so it can finish, and any nonterminals still left after the step cap are demoted to terminals. A non-recursive grammar therefore yields exactly its right-hand side, while a recursive one grows until the budget. Returns (networkx graph, list of symbols rewritten in order).

get_degree_dist(rule_list)

Node-degree histogram over the graphs of a list of grammar rules.

Parameters:

rule_list – List of rule objects, each with a networkx graph attribute.

Returns:

Dict mapping an observed node degree to its count, plus an 'inf' bucket of count 1 that reserves smoothing mass for degrees not seen in the model.

class VertexReplacementGrammarDistribution(grammar, mix_p, decomp_level=0, lhs_delta=0, name=None, orig_n=100, start_symbol=None)

Bases: SequenceEncodableProbabilityDistribution

VertexReplacementGrammarDistribution: a distribution over GRAPHS parameterised by a node-replacement grammar.

Observations are networkx graphs. log_density scores a graph by the product over its nodes of the model probability of each node’s ego pattern, sample emits graphs by derivation, and the estimator learns the model grammar from graphs – so all three share the graph sample space.

density(x)

Density of the grammar distribution at observation x.

See log_density() for details.

Parameters:

x – Observed graph (a networkx graph).

Returns:

Density at observation x.

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.

log_density(x, with_status=False)

Log-density of the grammar distribution at an observed GRAPH x – the marginal likelihood.

x is parsed (reduced back to the start symbol along the grammar’s productions) and the score is the log-sum over ALL derivations that yield it, log sum_D prod_i freq(r_i)/total(lhs_i), computed by the inside (sum-product) recursion (marginal_log_prob). A graph the grammar cannot generate scores -inf.

This is the true marginal, not the Viterbi (single best-derivation) lower bound. The parse search is budget-bounded; if the budget truncates the parse forest the result is a variational ELBO over the explored derivations – still >= the Viterbi value. best_derivation exposes the MAP parse.

Parameters:

x – Observed graph (a networkx graph).

Args (cont.):

with_status: if True, return (value, exact) where exact is False iff the parse

forest was truncated (so value may be a lower bound); if False, return just value.

Returns:

Log-density at observation x (<= 0, or -inf if the grammar cannot derive x).

seq_encode(x)

Encode a sequence of observed graphs for vectorized calls (identity encoding).

Parameters:

x – Sequence of observed graphs (networkx graphs).

Returns:

The input sequence unchanged.

seq_log_density(x, with_status=False)

Evaluate log_density() at each encoded observation.

Parameters:

• x – Sequence of observed graphs (from seq_encode).

• with_status – if True, also return a boolean mask that is True for rows whose marginal was computed exactly (the parse forest was not truncated) and False where it is a bound.

Returns:

A numpy array of log-densities, or (values, exact_mask) when with_status is True.

sampler(seed=None)

Create a VertexReplacementGrammarSampler object from the model grammar of this instance.

Parameters:

seed (Optional[int]) – Seed for the sampler random generator.

Returns:

VertexReplacementGrammarSampler object.

estimator(pseudo_count=None)

Create a VertexReplacementGrammarEstimator object.

Parameters:

pseudo_count (Optional[float]) – Added to rule frequencies when estimating.

Returns:

VertexReplacementGrammarEstimator object.

dist_to_encoder()

Returns a VertexReplacementGrammarDataEncoder object for encoding sequences of data.

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

Bases: DistributionSampler

VertexReplacementGrammarSampler object for sampling graphs generated from a node-replacement grammar.

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

Generate graphs from the grammar by NLC vertex-replacement derivation.

Parameters:

• size (Optional[int]) – Number of graphs to draw; None returns a single graph (honouring the DistributionSampler contract). Each graph uses the sampler’s orig_n node budget.

• batched (bool) – Accepted for interface compatibility; results are returned as a list.

Returns:

A single networkx graph when size is None, else a list of size graphs.

sample_seq(size_arr)

Generate one graph per entry of size_arr, each with that node budget.

Parameters:

size_arr – Sequence of node budgets.

Returns:

List of networkx graphs, one per requested budget.

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

Bases: SequenceEncodableStatisticAccumulator

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

This estimates rule FREQUENCIES only. The rule STRUCTURE (which right-hand sides / embeddings exist) is supplied via the estimator’s grammar argument; inducing the structure from graphs is a separate problem and out of scope here. Counting aligns rules by (symbol, index), which is stable because every model in the EM loop is built from the same structure.

update(x, weight, estimate)

Parse graph x with the current model and add weight to every rule its derivation fires.

initialize(x, weight, rng)

Initialize from one weighted observed graph (parse with the structure’s current frequencies).

seq_initialize(x, weights, rng)

Initialize from a sequence of weighted observed graphs.

seq_update(x, weights, estimate)

Parse-and-count a sequence of weighted observed graphs against the previous estimate.

combine(suff_stat)

Add another accumulator’s rule-firing counts (same structure) position-wise.

value()

Returns the accumulated rule-firing counts as a VertexReplacementGrammar.

from_value(x)

Set the accumulated counts from a VertexReplacementGrammar object.

key_merge(stats_dict)

Merge keyed sufficient statistics into stats_dict.

Parameters:

stats_dict (Dict[str, Any]) – Dictionary of keyed sufficient statistics.

Returns:

None.

key_replace(stats_dict)

Replace keyed sufficient statistics from stats_dict.

Parameters:

stats_dict (Dict[str, Any]) – Dictionary of keyed sufficient statistics.

Returns:

None.

acc_to_encoder()

Returns a VertexReplacementGrammarDataEncoder object for encoding sequences of data.

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

Bases: StatisticAccumulatorFactory

Creates VertexReplacementGrammarAccumulator objects carrying the rule structure to estimate frequencies for.

make()

Returns a new VertexReplacementGrammarAccumulator object.

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

Bases: ParameterEstimator

Estimate a VertexReplacementGrammarDistribution’s rule FREQUENCIES from graphs by Viterbi parse-counting.

The rule structure is supplied via grammar (e.g. from dist.estimator()): each training graph is parsed with the current model and the rules its best derivation fires are counted; frequencies are the accumulated counts. Inducing the structure (the right-hand sides / embeddings) from graphs is a separate problem and out of scope.

accumulator_factory()

Returns a VertexReplacementGrammarAccumulatorFactory carrying the rule structure.

accumulatorFactory()

Deprecated alias for accumulator_factory().

estimate(nobs, suff_stat)

Build a VertexReplacementGrammarDistribution from accumulated rule-firing counts (frequencies).

Parameters:

• nobs (Optional[float]) – Weighted number of observations (unused).

• suff_stat – VertexReplacementGrammar of accumulated rule-firing counts.

Returns:

VertexReplacementGrammarDistribution object.

class VertexReplacementGrammarDataEncoder

Bases: DataSequenceEncoder

VertexReplacementGrammarDataEncoder object for encoding sequences of observed graphs (identity encoding).

seq_encode(x)

Encode a sequence of observed graphs for vectorized calls (identity encoding).

Parameters:

x – Sequence of observed graphs (networkx graphs).

Returns:

The input sequence unchanged.