Two types of graphene were used to make polylactic acid (PLA)–graphene nanocomposites with various concentrations of graphene through a solution casting method. Because of the differences in surface area, thickness, and aspect ratio between the two types of graphene, the graphene–graphene and graphene–polymer interactions were different in these two nanocomposites. As a result, the two types of graphene nanoplatelets assembled into different interconnected structures in the matrix. Steady-state shear, stepwise small-amplitude oscillatory shear (SAOS) and large-amplitude oscillatory shear (LAOS), and frequency sweep tests immediately after the stepwise shear were used to determine and study the two different graphene aggregate structures. The disruption (under LAOS) and recovery (under SAOS) of the structures were monitored and the great disparities between the two types of graphene were ascribed to their structural roots. The formation of a percolated graphene network structure in the matrix significantly altered the structural evolution under the stepwise shear. This multistep shear process was found to be a very sensitive tool to differentiate sample microstructures while traditional linear viscoelastic tests (i.e., SAOS) failed.