HigherOrderGraph class

[vineetbansal]

This issue is to discuss how a new HigherOrderClass might build on TemporalGraph and EventGraph.

Using the same example we used for EventGraph - a->c always leads to d, and b->c always leads to e:

def data() -> pp.TemporalGraph:
    """

        a           d
          \        /
            c  (hub)
          /        \
        b           e

    """
    return pp.TemporalGraph.from_edge_list(
        [
            ("a", "c", 1), ("c", "d", 2),   # a -> c -> d
            ("b", "c", 3), ("c", "e", 4),   # b -> c -> e
            ("a", "c", 5), ("c", "d", 6),
            ("b", "c", 7), ("c", "e", 8),
        ]
    )

Usage might be:

t = data()
DELTA = 1
eg = EventGraph.from_temporal_graph(t, delta=DELTA)
h1 = HigherOrderGraph.from_temporal_graph(t, order: int = 1)
assert h1.order == 1

h2 = HigherOrderGraph.from_event_graph(eg)
assert h2.order == 2

h1b = HigherOrderGraph.from_path_data(pp, order: int = 1)
h1c = HigherOrderGraph.from_event_graph(eg, order: int = 2)

h5 = HigherOrderGraph.from_event_graph(eg, order=5)  # Create order 5 ho (but still has to go through 2->5 algorithmically)

print("\n=== HigherOrderGraph (order 2) ===")
print("order:", h2.order)                   # 2
print("nodes:", h2.nodes)                   # [('a','c'), ('b','c'), ('c','d'), ('c','e')]
print("edges:", h2.edges)                   # [(('a','c'),('c','d')), (('b','c'),('c','e'))]
print("weights:", h2.data.edge_weight)      # [2., 2.]

assert h2.order == 2
assert h2.n == 4                            # 8 events collapsed into 4 nodes
assert h2[0] == ("a", "c")                  # a node is a path, as an ID tuple
assert h2.n_first_order == 5
assert h2.first_order_mapping.to_id(0) == "a"

h3 = h2.lift()
assert isinstance(h3, HigherOrderGraph)
assert h3.order == 3
print("order-3 nodes:", h3.nodes)  # [('a', 'c', 'd'), ('b', 'c', 'e')]

MultiOrderModel would have HigherOrderModel in each of its layers:

MAX_ORDER = 2

# build MultiOrderModel from TemporalGraph
m = MultiOrderModel.from_temporal_graph(t, delta=DELTA, max_order=MAX_ORDER)

for k, layer in sorted(m.layers.items()):
    print(f"  layer {k}: order={layer.order}  n={layer.n}  m={layer.m}")
    #   layer 1: order=1  n=5  m=4
    #   layer 2: order=2  n=4  m=2
    assert isinstance(layer, HigherOrderGraph)
    assert layer.order == k
    assert layer.n_first_order == t.n

# build MultiOrderModel from EventGraph
m_via_eg = MultiOrderModel.from_event_graph(eg, max_order=MAX_ORDER)
assert m_via_eg.layers[2].edges == m.layers[2].edges

# build MultiOrderModel from PathData
paths = pp.PathData(pp.IndexMap(list("abcde")))
paths.append_walks(node_seqs=[("a", "c", "d"), ("b", "c", "e")], weights=[4, 4])
m_paths = MultiOrderModel.from_path_data(paths, max_order=MAX_ORDER)

[vineetbansal]

We need to save ho_index in the HigherOrderModel class, and create a gk when lifting, something that we do in MultiOrderModel already:

        if edge_weight is None:
            ho_index = lift_order_edge_index(edge_index, num_nodes=node_sequence.size(0))
        else:
            ho_index, edge_weight = lift_order_edge_index_weighted(
                edge_index, edge_weight=edge_weight, num_nodes=node_sequence.size(0), aggr=aggr
            )
        node_sequence = torch.cat([node_sequence[edge_index[0]], node_sequence[edge_index[1]][:, -1:]], dim=1)

        # Aggregate
        if save:
            gk = aggregate_edge_index(ho_index, node_sequence, edge_weight)
            gk.mapping = IndexMap([tuple(mapping.to_ids(v.cpu())) for v in gk.data.node_sequence])
        else:
            gk = None

[vineetbansal]

Pay special attention to current handling of node_sequence / edge_index