This book constitutes the thoroughly refereed post-conference proceedings of the 4th International Workshop on Graph Structures for Knowledge Representation and Reasoning, GKR 2015, held in Buenos Aires, Argentina, in July 2015, associated with IJCAI 2015, the 24th International Joint Conference on Artificial Intelligence. The 9 revised full papers presented were carefully reviewed and selected from 10 submissions. The papers feature current research involved in the development and application of graph-based knowledge representation formalisms and reasoning techniques. They address the following topics: argumentation; conceptual graphs; RDF; and representations of constraint satisfaction problems.