Most existing neural networks for learning graphs address permutationinvariance by conceiving of the network as a message passing scheme, where eachnode sums the feature vectors coming from its neighbors. We argue that thisimposes a limitation on their representation power, and instead propose a newgeneral architecture for representing objects consisting of a hierarchy ofparts, which we call Covariant Compositional Networks (CCNs). Here, covariancemeans that the activation of each neuron must transform in a specific way underpermutations, similarly to steerability in CNNs. We achieve covariance bymaking each activation transform according to a tensor representation of thepermutation group, and derive the corresponding tensor aggregation rules thateach neuron must implement. Experiments show that CCNs can outperform competingmethods on standard graph learning benchmarks.