Skip to content

get_intermediate_order_log_likelihood ignores edge weights when computing transition probabilities #340

Description

@M-Lampert

I found this while looking into #172. Below is a write up by Claude

What happens

When we compute the likelihood of observed paths under a multi-order model, every step of a path is
scored with the probability of taking that transition. That probability should be the observed
relative frequency: an edge's weight divided by the total weight of all edges leaving the same node.

For the intermediate orders we currently drop the weights:

# multi_order_model.py, in get_intermediate_order_log_likelihood
transition_probabilities = self.layers[order].transition_probabilities()[...]

Graph.transition_probabilities() falls back to counting each outgoing edge once when no edge
attribute is given, so every alternative at a node is treated as equally likely, regardless of how
often it was actually observed. The highest-order term in the same file already does it correctly:

# in get_mon_log_likelihood
transition_probabilities = self.layers[max_order].transition_probabilities(edge_attr="edge_weight")

How to reproduce

Two paths starting at the same node, observed a different number of times:

paths = PathData(IndexMap(list("abcde")))
for _ in range(3):
    paths.append_walk(("a", "b", "c"))
paths.append_walk(("a", "d", "e"))

m = MultiOrderModel.from_path_data(paths, max_order=2)
m.get_mon_log_likelihood(paths.data, max_order=2)

a → b was observed 3 times and a → d once, so the first-order probabilities are 3/4 and 1/4:

expected: 4*log(4/12) + 3*log(3/4) + 1*log(1/4) = -6.6438
actual:   4*log(4/12) + 3*log(1/2) + 1*log(1/2) = -7.1670

Why the existing tests do not catch it

Intermediate-order terms only exist for max_order >= 2, and they are only wrong when a node has
outgoing edges with different weights. In all current test fixtures the alternatives at a branching
node are observed equally often, so uniform and relative-frequency probabilities coincide.

Impact

get_mon_log_likelihood(max_order=k) is too low for every k >= 2, which propagates to
likelihood_ratio_test and estimate_order. Because only the higher-order side of each comparison
carries intermediate terms, the test statistic comes out too small — so the bias is towards
underestimating the optimal order on data with uneven branching.

Suggested fix

Pass edge_attr="edge_weight", matching the highest-order term. Worth checking at the same time
whether mode="diffusion" (where edge weights are probabilities rather than counts) needs different
handling here.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

bugSomething isn't working

Type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions