In one embodiment, a method includes receiving a query from a user from a client system associated with the user, accessing a knowledge graph comprising a plurality of nodes and edges connecting the nodes, wherein each node corresponds to an entity and each edge corresponds to a relationship between the entities corresponding to the connected nodes, determining one or more initial entities associated with the query based on the query, selecting one or more candidate nodes by a conversational reasoning model from the knowledge graph corresponding to one or more candidate entities, respectively, wherein each candidate node is selected based on the nodes corresponding to the initial entities, dialog states associated with the query, and a context associated with the query, generating a response based on the initial entities and the candidate entities, and sending instructions for presenting the response to the client system in response to the query.