Continuous Edge Prototypes

Integrate this as a prototype/codebook layer for a graph neural network or graph-based retrieval system. The graph has vertices with learned or pretrained embeddings z_i, edge lengths L_{pq} such as reciprocal similarity or shortest-path distances, and K prototypes; prototype k is represented by an edge index (p_k,q_k) and scalar coordinate t_k in [0,L_k], rather than by a free vector. First precompute shortest-path distances from candidate edge endpoints to minibatch vertices using truncated Dijkstra or a sparse distance oracle. For every data vertex i and prototype k, compute d(i,x_k)=min(d(i,p_k)+t_k,d(i,q_k)+L_k-t_k), then use soft assignments r_{ik}=softmax_k(-d(i,x_k)/tau) or squared distances. During an alternating prototype update, freeze r_{ik}, classify each i into branch A or B according to which term realizes the minimum, and calculate valid bottleneck coordinates t_i^b. Sort the bottlenecks on each prototype edge; on each interval, use the closed-form update above with A and B fixed, evaluate F at the candidate, and choose the lowest-cost candidate. For a cheaper MVP, use the current active branches, apply the clipped formula once, and recompute branches. Update neural parameters with ordinary backpropagation through the soft-assignment loss while treating the prototype step as an alternating optimizer. Compare against node-only k-means prototypes, graph medoids, and free Euclidean prototypes on Cora, CiteSeer, and a synthetic graph with data sampled along edges. Measure retrieval recall@k or classification accuracy at equal prototype count, quantization distortion, wall-clock cost, and outer-loop convergence. Success means lower distortion and higher recall at fixed K, particularly for between-vertex data, without a prohibitive increase in shortest-path computation.