We analyse the formation of large-scale patterns in a turbulent convection flow in a horizontally extended square convection cell by Lagrangian particle trajectories in three-dimensional direct numerical simulations. These large-scale patterns, which are termed turbulent superstructures of convection, are detected by the spectrum of the graph Laplacian matrix. The corresponding graph is built from the Lagrangian particle tracks. We demonstrate that the resulting trajectory clusters, which are obtained by a subsequent k-means clustering, agree with the superstructures in the Eulerian frame of reference. Furthermore, the characteristic times τ L and lengths λUL of the superstructures are found to agree well with their Eulerian complements, τ and λU, respectively. The clustering works well for times t < τ. Longer times t > τ require density-based trajectory clustering using time-averaged Lagrangian pseudo-trajectories. A coherent subset of these trajectories is obtained which consists of those particles tracks that are trapped for long times in the core of the superstructure rolls and thus not subject to ongoing turbulent dispersion.