In previous work, we developed a deep neural network classifier that only relies on phase-space information to obtain a catalog of accreted stars based on the second data release of Gaia (DR2). In this paper, we apply two clustering algorithms to identify velocity substructure within this catalog. We focus on the subset of stars with line-of-sight velocity measurements that fall in the range of Galactocentric radii and vertical distances . Known structures such as Gaia Enceladus and the Helmi stream are identified. The largest previously unknown structure, Nyx, is a vast stream consisting of at least 200 stars in the region of interest. This study displays the power of the machine-learning approach by not only successfully identifying known features but also discovering new kinematic structures that may shed light on the merger history of the Milky Way.