Registration Is Not Enough: Online Relation Recommendation over Growing Schema Registries

Knowledge graphs underpin retrieval-augmented question answering and enterprise search. Building one from text means choosing, for each entity pair in a sentence, an edge type from a relation-schema registry-the set of unique relations the graph may express. That registry grows during operation while the verifier's candidate budget does not. This makes the shortlist a critical recall bottleneck: a relation omitted from the shortlist cannot be recovered by the downstream verifier. We treat each schema as a contextual-bandit arm: score all active arms, propose a fixed-size Top-K list, and update the exposed arms from verifier feedback. Under oracle feedback, our router reaches 90.69% Recall@5, but its margin over a tuned baseline narrows from 3.93 to 0.82pp under sparser feedback, and its Zipf-arrival interval includes zero. Post-registration adaptation remains consistently beneficial: a single update exposes a new arm but leaves known-relation Recall@5 at 61.56%, whereas continual feedback restores it to 92.78%. Uncertainty-gated semantic scoring improves cold-start Recall@5 by 12.6pp without reducing overall Recall@5. In an LLM-driven pilot, the resolver distinguishes recommendation misses from genuine schema gaps less accurately than an always-recover baseline and registers 66 schemas for 16 novel relations---exposing canonicalization and new-arm cold start as deployment bottlenecks.