Intrinsically low lattice thermal conductivity ($kappa_l$) is a desired requirement in many crystalline solids such as thermal barrier coatings and thermoelectrics. Here, we design an advanced machine-learning (ML) model based on crystal graph convolutional neural network that is insensitive to volumes (i.e., scale) of the input crystal structures to discover novel quaternary chalcogenides, AMMQ$_3$ (A/M/M=alkali, alkaline-earth, post-transition metals, lanthanides, Q=chalcogens). Upon screening the thermodynamic stability of $sim$ 1 million compounds using the ML model iteratively and performing density functional theory (DFT) calculations for a small fraction of compounds, we discover 99 compounds that are validated to be stable in DFT. Taking several DFT-stable compounds, we calculate their $kappa_l$ using phonon-Boltzmann transport equation, which reveals ultralow-$kappa_l$ ($<$ 2 Wm$^{-1}$K$^{-1}$ at room-temperature) due to their soft elasticity and strong phonon anharmonicity. Our work demonstrates the high-efficiency of scale-invariant ML model in predicting novel compounds and presents experimental research opportunities with these new compounds.