Графо-ориентированые методы определяют кластеры в терминах теории графов, используя понятие близости. Все объекты представляются вершинами графа, соединенными ребрами, веса которых равны значениям близости. Часто, объекты считаются соединенными ребром, если значение близости превосходит некоторый заданный порог.