METIS is a software package for graph partitioning that implements various multilevel algorithms.[1][2] METIS' multilevel approach has three phases and comes with several algorithms for each phase:
The final partition computed during the third phase (the refined partition projected onto G0) is a partition of the original graph.
According to Metis authors Karypis and Kumar, "Metis is the Greek word for wisdom. Metis was a titaness in Greek mythology. She was the consort of Zeus and the mother of Athena. She presided over all wisdom and knowledge".[3]