Generative modeling is one of the most promising applications of quantum machine learning, yet training and deploying Quantum Generative Models (QGMs) on near-term hardware remains effectively intractable due to prohibitive gradient estimation and implementation costs. We propose a resource-efficient approach based on shallow Instantaneous Quantum Polynomial-time (IQP) circuits that circumvents these bottlenecks by leveraging efficient classical training while retaining the guarantee of sampling hardness. To validate this approach, we formalize graph generation as a hierarchy of physical correlations, allowing us to map abstract data features---such as edge density and bipartiteness---directly to the quantum observables required to learn them. We validate our protocol through demonstrations both on real hardware (from $28$ to $153$ qubits) and simulations ($28$ qubits). Results show that while global structural features exhibit significant degradation beyond $91$ qubits, our models achieve high-precision reproduction of local correlations, even up to $153$ qubits. These findings establish shallow IQP circuits as a robust, scalable candidate for generative tasks on current Noisy Intermediate-Scale Quantum (NISQ) devices.