Threat detection in a multi-organizational environment. Attribute data corresponding to accesses to a multi-organizational environment and entity data corresponding to accesses to the multi-organizational environment are maintained. A graph based on the attribute data and the entity data where graph edges represent a relationship between an attribute and an entity is generated. Subsequent access are compared to the graph to determine if the subsequent access corresponds to a new relationship. The subsequent access is allowed if the subsequent access does not correspond to a new relationship. The subsequent access further analyzed if the subsequent access corresponds to a new, unexpected relationship.