Compositional Zero-Shot learning (CZSL) aims to recognize unseen compositionsof state and object visual primitives seen during training. A problem withstandard CZSL is the assumption of knowing which unseen compositions will beavailable at test time. In this work, we overcome this assumption operating onthe open world setting, where no limit is imposed on the compositional space attest time, and the search space contains a large number of unseen compositions.To address this problem, we propose a new approach, Compositional Cosine GraphEmbeddings (Co-CGE), based on two principles. First, Co-CGE models thedependency between states, objects and their compositions through a graphconvolutional neural network. The graph propagates information from seen tounseen concepts, improving their representations. Second, since not all unseencompositions are equally feasible, and less feasible ones may damage thelearned representations, Co-CGE estimates a feasibility score for each unseencomposition, using the scores as margins in a cosine similarity-based loss andas weights in the adjacency matrix of the graphs. Experiments show that ourapproach achieves state-of-the-art performances in standard CZSL whileoutperforming previous methods in the open world scenario.