The term 'relational dataset' refers generically to graphs, matrices, networks. I will review a number of examples coming from different communities (machine learning, statistics, computer science) in which it is desirable to find a small structure in such datasets. Some fundamental computational obstructions appear to emerge in each of these domains, and I will discuss their connections.