The rapidly increasing number of data-driven applications in various fields like healthcare, finance, and smart governance has raised the issue of privacy and security of sensitive information when mining data. The present paper suggests a new combinatorial model of privacy-preserving data mining utilizing the mathematical tools graph theory, set systems, and combinatorial optimization. The main goal is to develop an effective anonymization model that has minimal information loss, as well as meets high privacy restrictions. The algorithms include building similarity graphs on input data sets, forming clusters based on combinatorial grouping schemes, and eliminating the best partitions based on k-anonymity, l -diversity and t -closeness criteria. A combination of privacy and utility is achieved using a multi-objective optimization technique that is backed up by entropy-based and distance-based privacy metrics. The benchmark datasets are used to perform experimental evaluation and the performance is evaluated based on measures such as re-identification risk, information loss, utility score and computational efficiency. The findings presented in the paper prove that the suggested structure leads to the considerable decrease in the risk of re-identification (up to 0.10) and loss of information (around 0.28) and increases utility scores (up to 0.82) in comparison to the traditional approaches to PPDM. Moreover, the method has better computational efficiency and less time to run and is more scalable.