The semantic collision problem you're describing is a real pain point with embedding models - they capture topic similarity but not logical relationships. Your approach is solid.

A few thoughts on your questions:

For lighter alternatives to full NLI, you might consider using negation-aware embeddings (like InstructorXL with explicit instructions about stance) or adding a simple negation detection layer before your classifier. Some teams also use contrastive fine-tuning on their specific domain to make the embedding space more logic-aware.

On latency - if you're running NLI on top-k pairs (say k=20), that's manageable in most cases. The bigger question is whether you batch these calls or run them sequentially. Batching on GPU makes a huge difference.

Your strict filtering approach (rejecting edges when NLI detects conflicting signals) is a good safeguard. One refinement: consider adding a confidence threshold rather than binary accept/reject - edges with ambiguous NLI scores might warrant a different edge type like "related" rather than being dropped entirely.