The diversity and Zipfian frequency distribution of natural languagepredicates in corpora leads to sparsity when learning Entailment Graphs. Assymbolic models for natural language inference, an EG cannot recover if missinga novel premise or hypothesis at test-time. In this paper we approach theproblem of vertex sparsity by introducing a new method of graph smoothing,using a Language Model to find the nearest approximations of missingpredicates. We improve recall by 25.1 and 16.3 absolute percentage points ontwo difficult directional entailment datasets while exceeding averageprecision, and show a complementarity with other improvements to edge sparsity.We further analyze language model embeddings and discuss why they are naturallysuitable for premise-smoothing, but not hypothesis-smoothing. Finally, weformalize a theory for smoothing a symbolic inference method by constructingtransitive chains to smooth both the premise and hypothesis.