Repository navigation
Should we implement a zeroth order layer in MultiOrderModel? #172
Description
Activity
Since we are currently working on a
HigherOrderGraphclass to represent higher-order graphs better in PathpyG (#329, #325), this question came up again. Specifically, we asked if the newHigherOrderGraphshould be able to represent a 0-th order graph or not and how it could look like. I investigated a few different ideas listed below and came to the following verdict:TL;DR: If we do not want the 0-th order graph for anything other than the model selection (where this question first came up), then it would be better to introduce a
node_weightattribute instead.In more detail
Background
In a multi-order model, layer k is a graph whose nodes are paths of k nodes and whose edge weights count how often each path of k+1 nodes was observed. Layer 0 is the model with no memory at all: it only knows how often each node was visited, so it has no transitions — mathematically its transition matrix is just the same probability vector repeated in every row. So the entire content of "layer 0" is one vector of node visit counts.
Node Visit Counts as Node Weights
The number of times a path of k nodes occurs, could be represented at the same time as:
- the node weight of that node in layer k, and
- the edge weight of the corresponding edge in layer k−1.
Applying this at k = 1: the counts we want to put into a "layer 0" are exactly the node weights of layer 1.
Cost
- Memory:
node_weightis one float per node — exactly 1/k the size ofnode_sequenceon the same layer (measured: +0.4% / 1.6% / 4.5% / 9.3% of layer 1–4 storage on a 48k-node path dataset). - Compute: For k ≥ 2, the required tensor is already a local variable in
iterate_lift_order. - It actually saves a little:
get_zeroth_order_log_likelihoodcurrently sorts the full path-node tensor on every likelihood evaluation, i.e. 2·(max_order−1) times perestimate_order(~11% of its runtime; 4–12 ms → 0.15 ms in a small benchmark).
Alternatives
Option What layers[0]isTrade-off Node weights only (recommended) nothing — layersstarts at 1No new semantics, no special cases. Answers the issue with "no". Lightweight zeroth-order object small non-graph class holding the counts, with transition_probabilities(),n,to()Keeps layers[k]uniform, and nothing that doesn't work for order 0 can be misusedSelf-loop graph one node per first-order node, one self-loop each, weight = visit count, node_sequenceof width 0Uses edge weights like every other layer, and order 0 comes out of the class for free. But transition_probabilities()returns all-ones unless we modify it.Single-node graph one node (the empty path) with n parallel self-loops, one per node Mathematically the correct De Bruijn graph of order 0, and transition_probabilities()is right out of the box. Needs a new edge attribute for the labels, andedge_to_indexcollapses the parallel edges.Open questions
- Temporal graphs.
from_temporal_graphbuilds layer 1 counting edges only — we would have to define what counts as a "visit" (both endpoints of every event? sources only?). estimate_ordercan never return 0 — its loop starts atk=2, so order 0 vs 1 is never tested. If we want that hypothesis tested, order 0 needs to be addressable and one of the last three options is required. Not sure if that is something we want.
Reacted by Vineet Bansal@M-Lampert - PR #329 does support order 0 for a
HigherOrderGraph, and there is now alayers[0]inMultiOrderModelthat has aHigherOrderModelof order 0.The implementation followed there is the fourth option in the table above (one node (the empty path) with n parallel self-loops, one per node).
estimate_ordercan now return order 0 as the estimated order.
The MultiOrderModel implementation is constructed with layers starting from 1. The model selection is currently implemented with some workarounds to account for the frequencies and probabilities of transitions in zeroth order.
Do we want to keep the current situation, or shall we add a zeroth order layer in the MultiOrderModel implementation?