A method and system for deleting a node of a knowledge graph may be provided. The method comprises receiving knowledge graph data comprising nodes and edges, determining a first relevance degree value for a node and a second relevance degree value for the node, combining the first and the second relevance degree value and marking the node as deletable if the final relevance degree value is above a predefined relevance threshold value. The method comprises further applying queries against the knowledge graph, wherein at least a certain number of such queries invokes accessing of a node, marked as deletable, revising at least one of the first and second relevance degree value based on the accessing of the node marked as deletable, and deleting the node, marked as deletable, if over a predetermined period of time queries against the knowledge graph invoke no access of the node marked as deletable.