The rise of high-dimensional data in cancer diagnosis necessitates identifying relevant features to enhance model performance and ensure accurate predictions. Feature selection simplifies this process by isolating informative features, improving accuracy, reducing complexity, and eliminating uninformative variables. This paper introduces a new approach that combines a mutual information filter with non-dominated maximal cliques for feature selection in three main steps: (a) applying the mutual information filter to rank variables, (b) modeling the feature selection problem using graph theory by constructing a graph that links variables and identifying maximal cliques, and (c) applying the non-dominance criterion to these maximal cliques based on edge connectivity and diameter. Extensive experiments on various cancer microarray datasets demonstrate the approach’s high classification accuracy and minimal feature selection, showcasing its robustness and generalizability in addressing challenges in cancer diagnosis and personalized medicine.