Technology is disclosed herein for enhanced similarity search. In an implementation, a search environment includes one or more computing hardware, software, and/or firmware components in support of enhanced similarity search. The one or more components identify a modality for a similarity search with respect to a query object. The components generate an embedding for the query object based on the modality and based on connections between the query object and neighboring nodes in a graph. The embedding for the query object provides the basis for the search for similar objects