Ensemble-Averaged Sparse Graph Search

1. Integration point: modify the aggregation operation of a 2-4 layer message-passing GNN on a fixed candidate edge superset. Store one trainable logit a_uv^(l) per candidate directed edge and define P_uv^(l)=sigmoid(a_uv^(l)); during the relaxed phase, do not sample or materialize a binary adjacency. Replace the usual aggregation sum_v H_uv W_l h_v by m_u^(l)=sum_v P_uv^(l)W_l h_v. Add lambda times the sum of probabilities to the task loss, and optionally add a target-density penalty (sum P / number of candidates - rho)^2. 2. Pseudocode: initialize node states h; for each layer l, compute P=sigmoid(a_l), messages z_v=W_l h_v, aggregate m_u=sum_v P[u,v]*z_v, update h=phi(Wself_l*h+m); backpropagate J=L_task+lambda*sum(P). Every K steps, construct a discrete graph by top-k thresholding or Bernoulli sampling, run the same forward pass, and record validation accuracy and edge count. 3. Computed from the paper's mathematics: the Bernoulli ensemble interpretation, deterministic probability-weighted aggregation, and gradients through edge probabilities. Estimated empirically: the nonlinear ensemble loss, the threshold meeting the desired sparsity, and whether relaxed edge ranking predicts sampled-graph usefulness. At evaluation intervals, estimate the true ensemble loss with 8-32 sampled masks. 4. First experiment: use a 2-layer GCN on Cora or a synthetic stochastic block model, with all candidate edges available and a 10-25% target density. Compare dense GCN, post-training magnitude pruning, Gumbel/DARTS edge search, and this method at equal epochs and parameter budgets. Success means higher validation accuracy at the same edge budget, smoother loss descent than sampled-mask training, strong correlation between relaxed validation loss and thresholded-graph performance, and at least 4x fewer deployed edges with no more than a 1 percentage point accuracy loss. Measure sparse inference latency and memory after conversion.