L2-Certified DAG Attention Ordering

1. Integration point: use a directed graph attention layer. For node features h_v, compute nonnegative edge weights w_uv=softplus((W_q h_u)^T(W_k h_v)/sqrt(d)) for every directed edge u->v. If both directions occur, retain only the larger direction or subtract the smaller weight so the working graph is oriented. Add an ordering head s_v=MLP(h_v).

2. During training, replace the hard condition s_u<s_v with p_uv=sigmoid((s_v-s_u)/tau). Compute forward_weight=sum_{u->v} w_uv p_uv and backward_weight=sum_{u->v} w_uv(1-p_uv). Use attention logits l_uv+log(p_uv+epsilon), and add the differentiable surplus loss -(forward_weight-backward_weight)/(sum_e w_e+epsilon). Compute w2_sum=sum_v sqrt(sum_{e incident to v} w_e^2), and add the hinge certificate loss [1/2-sqrt(2)w2_sum/(12(sum_e w_e+epsilon))]_+ with coefficient lambda. Anneal tau from 1.0 to 0.05; at inference, sort nodes by s_v and retain exactly edges whose source precedes their target.

3. Computed from the paper: the surplus identity, the coefficient sqrt(2)/12, and the incident l2 certificate. Estimated empirically: ordering scores, attention weights, and realized backward fraction. Normalize edge weights by total graph weight, clip logits before the sigmoid, and handle self-loops separately because they cannot be classified as forward or backward.

4. First experiment: train a four-layer graph transformer on Cora and ogbn-arxiv, comparing ordinary bidirectional attention, a random ordering mask, and the learned DAG mask at matched parameter count and FLOPs. Measure validation accuracy, realized backward weight, retained-edge count, gradient variance, and inference memory. A successful result is lower backward mass than random ordering, equal-or-better accuracy with fewer retained edges, and stable optimization while temperature is annealed.