Skip edges¶
parse_layered() ranks a directed acyclic graph
(DAG) into layers. An original edge whose endpoints are more than one
layer apart is a skip. This page is the
algorithm for that edge, how kpnn2 writes it as a
hop mask — a hop being everything entering one layer
— and one worked example. After it you can build a module for a graph
that has skips.
Algorithm¶
An adjacent edge, one between consecutive layers, is the easy case: compute each layer from the one below it. A skip still has to reach its target after the layers in between have been computed, so the source activation has to survive those hops.
That skip is an extra parent of the target, not a second
kind of node. The source is not copied through dummy units, and
kpnn2 never inserts identity neurons or generated names.
Figure 1. Store the source activation, hold it across the next hop, and pass it into the target together with the adjacent parent. Solid arrows are graph edges; dashed arrows are the forward pass. A, B, and C are a three-node toy. Figure 2 uses a larger graph.
The computational steps are store, hold, and pass forward. In symbols, for the toy:
C = f( w_{B→C} z_B + w_{A→C} z_A + b_C )
Both incoming terms have the same form: the skip weight is an ordinary incoming weight on C.
Packed hops¶
kpnn2 writes that algorithm as one packed hop per layer after the
inputs. A hop holds every edge entering its layer as packed index
pairs, two parallel lists with one entry
per edge, skips included, so adjacent and skip edges share one
PackedLinear. spec.skips is metadata for inspection; the forward
pass never reads it.
Figure 2. Figure 1 written as hops on the graph used in
the example below. hops[1] reads layers 0 and 1, and hops[2]
reads layers 0, 1 and 2. Solid and dashed edges are the same
linear map; the dashes only mark which edges jump a layer.
A hop with skip parents reads more than one layer, so its input is
those layers concatenated. gather_hop_inputs(saved, hop) builds
that tensor, in source-column order. Columns that carry no edge
into the target stay in it; PackedLinear never reads them. You
do not pick skip nodes by name.
Three properties follow, and they are the reason the design looks like this:
- No edge can be dropped silently. Applying a hop applies
every parent of its target at once. There is no second call to
remember, and
gather_hop_inputs()raisesKpnn2Errorif a layer that a hop reads was never stored. - The fan-in is right.
PackedLinearinitializes each output row from that row's packed degree. Because skip parents sit in the same hop, a unit with two adjacent and three skip parents is initialized with fan-in five, not two. - A skip weight is an ordinary weight. One weight per incoming
edge, all in one packed vector, all drawn from the same
degree-aware initialization. There is no skip bias: one bias per
unit stays on
PackedLinear.
In a larger graph the same three steps loop, keeping every layer
in saved for later hops:
saved = {0: x}
for hop in spec.hops:
sources = kpnn2.gather_hop_inputs(saved, hop)
hidden = layer(sources)
saved[hop.target_layer] = hidden
layer is PackedLinear on that hop's packed indices.
Feedforward example shows that loop on a graph without skips. The loop does not change here, because skips already sit inside those hops.
Example¶
The rest of this page unrolls Figure 2 so each hop is a named line: parse the edgelist, read the masks, write the module, and check the arithmetic.
Inputs A and B, hidden units H1 and H2, output C.
Adjacent edges are A -> H1, B -> H1, H1 -> H2, and
H2 -> C. Skips are A -> H2, H1 -> C, and A -> C.
import pandas as pd
import kpnn2
edgelist = pd.DataFrame(
{
"source": ["A", "B", "H1", "H2", "A", "H1", "A"],
"target": ["H1", "H1", "H2", "C", "H2", "C", "C"],
}
)
spec = kpnn2.parse_layered(edgelist)
print(spec.layer_nodes)
print([f"{s.source} -> {s.target}" for s in spec.skips])
(('A', 'B'), ('H1',), ('H2',), ('C',))
['A -> H2', 'H1 -> C', 'A -> C']
The masks¶
Packed index pairs are awkward to read. hop.to_mask() is the
dense rectangle a hop stands for: each row is the target unit,
each column is a parent, including skips. A 0 is an absent edge
(B never feeds H2 or C).
hop0, hop1, hop2 = spec.hops
mask0 = hop0.to_mask()
mask1 = hop1.to_mask()
mask2 = hop2.to_mask()
print(
pd.DataFrame(
mask0.numpy(),
columns=list(hop0.source_nodes),
index=["H1"],
)
)
print()
print(
pd.DataFrame(
mask1.numpy(),
columns=list(hop1.source_nodes),
index=["H2"],
)
)
print()
print(
pd.DataFrame(
mask2.numpy(),
columns=list(hop2.source_nodes),
index=["C"],
)
)
ones = int(mask0.sum() + mask1.sum() + mask2.sum())
print(ones, "ones in the masks,", len(edgelist), "edges")
A B
H1 1.0 1.0
A B H1
H2 1.0 0.0 1.0
A B H1 H2
C 1.0 0.0 1.0 1.0
7 ones in the masks, 7 edges
Each rectangle here is wider than the one before it, because each
target draws on more layers. hops[0] reads only (A, B), because
H1 can only have layer-0 parents. hops[1] also reads A, since
A -> H2 jumps a layer. hops[2] reads A, H1, and H2.
The pairs across all three hops add up to the number of rows in the edgelist, seven here. That equality is the guarantee: every prior-knowledge edge is in exactly one hop.
The module¶
Skips change nothing about how the module is written: __init__
builds one PackedLinear per hop, forward applies them in
order, and each hidden hop is followed by an nn.ReLU in
self.acts. The hop into H1 reads only the input, so it takes x
directly. The hops into H2 and C also need earlier
activations, so gather_hop_inputs() concatenates those layers
into one tensor whose columns match the hop's source axis.
No skip object is applied anywhere. Bias is off so the numbers below stay readable.
import torch
from torch import nn
class Net(nn.Module):
def __init__(self, spec: kpnn2.LayeredSpec):
super().__init__()
self.spec = spec
self.to_h1 = kpnn2.PackedLinear(
spec.hops[0].source_index,
spec.hops[0].target_index,
spec.hops[0].out_features,
spec.hops[0].in_features,
bias=False,
)
self.to_h2 = kpnn2.PackedLinear(
spec.hops[1].source_index,
spec.hops[1].target_index,
spec.hops[1].out_features,
spec.hops[1].in_features,
bias=False,
)
self.to_c = kpnn2.PackedLinear(
spec.hops[2].source_index,
spec.hops[2].target_index,
spec.hops[2].out_features,
spec.hops[2].in_features,
bias=False,
)
self.acts = nn.ModuleList([nn.ReLU() for _ in spec.hops])
def forward(self, x):
h1 = self.acts[0](self.to_h1(x))
h2_in = kpnn2.gather_hop_inputs({0: x, 1: h1}, self.spec.hops[1])
h2 = self.acts[1](self.to_h2(h2_in))
c_in = kpnn2.gather_hop_inputs({0: x, 1: h1, 2: h2}, self.spec.hops[2])
self.h1, self.h2 = h1, h2
return self.to_c(c_in)
model = Net(spec)
Numerical check¶
Fixed weights make each skip's contribution visible in the output.
Pin every adjacent weight to 1, and the skip weights to
w_{A→H2} = 0.3, w_{H1→C} = 0.2, w_{A→C} = 0.1, then check
the printed values against the arithmetic below.
PackedLinear.weight is one scalar per live
edge, an edge the graph actually has, in packed
order: (A, B) into H1, (A, H1) into H2, and (A, H1, H2) into C.
Absent parents are not entries, and copy_ writes those scalars into
the packed parameter. forward returns C; self.h1 and self.h2 are
stored only so this check can print the hidden units.
For input A = 2, B = 0:
H1 = relu(A + B) = 2
H2 = relu(0.3 A + H1) = relu(2.6) = 2.6
C = 0.1 A + 0.2 H1 + H2 = 3.2
For A = -1, B = 0, ReLU zeros the path through H1 and H2,
but the skip A -> C still contributes:
H1 = relu(-1) = 0
H2 = relu(0.3 (-1) + 0) = 0
C = 0.1 (-1) + 0.2 * 0 + 0 = -0.1
with torch.no_grad():
model.to_h1.weight.copy_(torch.tensor([1.0, 1.0]))
model.to_h2.weight.copy_(torch.tensor([0.3, 1.0]))
model.to_c.weight.copy_(torch.tensor([0.1, 0.2, 1.0]))
c = model(torch.tensor([[2.0, 0.0]]))
print(
f"A=2 H1, H2, C: {model.h1.item():.1f},"
f" {model.h2.item():.1f}, {c.item():.1f}"
)
c = model(torch.tensor([[-1.0, 0.0]]))
print(
f"A=-1 H1, H2, C: {model.h1.item():.1f},"
f" {model.h2.item():.1f}, {c.item():.1f}"
)
A=2 H1, H2, C: 2.0, 2.6, 3.2 A=-1 H1, H2, C: 0.0, 0.0, -0.1
Checks¶
The last cell checks both guarantees here. The fan-in that
PackedLinear initializes from is the packed row degree of the
hop, so it counts skip parents: C has three. A hop that reads a
layer you never stored is an error, not a silent omission.
print("H1 fan-in", len(spec.hops[0].source_index))
print("H2 fan-in", len(spec.hops[1].source_index))
print("C fan-in", len(spec.hops[2].source_index))
x = torch.tensor([[2.0, 0.0]])
try:
kpnn2.gather_hop_inputs({0: x}, spec.hops[2])
except kpnn2.Kpnn2Error as error:
print(error)
H1 fan-in 2 H2 fan-in 2 C fan-in 3 saved is missing layer 1. The hop into layer 3 reads layers [0, 1, 2].