An example embodiment may involve performing a discovery process to identify configuration items representing computing devices and applications in a managed network and determining that the configuration items exceed a threshold payload size. The embodiment may then involve generating a graph that represents the configuration items as nodes interconnected by unidirectional edges. The edges may represent respective associations between pairs of configuration items to which they connect, and the respective associations are classified either as weak associations that represent non-dependency relationships between a respective pair of nodes or as strong associations that represent dependency relationships between the respective pair of nodes. The embodiment may involve dividing the graph into overlapping sub-graphs based on the respective associations represented by the edges and, for each sub-graph, separately transmitting the configuration items defined therein to one or more server devices.