Quá trình kết hợp một tập hợp các đối tượng vật lý hoặc trừu tượng thành các lớp của các đối tượng giống nhau được gọi là phân cụm. Một cụm là một tập hợp các đối tượng dữ liệu giống nhau trong cùng một cụm và khác biệt với các đối tượng trong các cụm khác. Một cụm đối tượng dữ liệu có thể được xem xét tập thể như một nhóm trong nhiều ứng dụng. Phân tích cụm là một hoạt động thiết yếu của con người.
Phân cụm hỗ trợ xác định các ngoại lai. Các giá trị giống nhau được tổ chức thành các cụm và những giá trị nằm ngoài cụm được gọi là ngoại lai. Các kỹ thuật phân cụm xem các bộ dữ liệu như đối tượng. Chúng phân hoạch các đối tượng thành các nhóm hoặc cụm sao cho các đối tượng trong một cụm "tương đồng" với nhau và "khác biệt" với đối tượng trong các cụm khác. Thường được định nghĩa theo cách các đối tượng "gần" nhau trong không gian, dựa trên hàm khoảng cách.
Có nhiều phương pháp phân cụm dựa trên đồ thị như sau:
Làm thưa đồ thị gần kề để chỉ giữ liên kết của đối tượng với các láng giềng gần nhất. Làm thưa này có lợi cho việc xử lý nhiễu và ngoại lai. Nó cũng cho phép sử dụng các thuật toán phân hoạch đồ thị cực kỳ hiệu quả đã được phát triển cho đồ thị thưa.
Có thể định nghĩa phép đo độ tương đồng giữa hai đối tượng dựa trên số láng giềng gần nhất mà họ chia sẻ. Phương pháp này dựa trên quan sát rằng một đối tượng và các láng giềng gần nhất của nó thường thuộc cùng một lớp, có lợi cho việc khắc phục vấn đề với số chiều cao và cụm mật độ thay đổi.
Có thể định nghĩa các đối tượng lõi (core objects) và xây dựng các cụm quanh chúng. Trong phân cụm dựa trên đồ thị, thiết yếu phải giới thiệu khái niệm mật độ dựa trên đồ thị gần kề hoặc đồ thị gần kề đã làm thưa. Giống như DBSCAN, xây dựng cụm quanh các đối tượng lõi dẫn đến phương pháp phân cụm có thể khám phá cụm hình dạng và kích thước khác nhau.
Có thể dùng thông tin trong đồ thị gần kề để hỗ trợ tính toán tinh vi hơn về việc hai cụm có nên được kết hợp hay không. Đặc biệt, hai cụm chỉ được kết hợp nếu cụm kết quả sẽ có đặc điểm giống với hai cụm ban đầu.
Có thể bắt đầu bằng thảo luận làm thưa đồ thị gần kề, hỗ trợ hai ví dụ kỹ thuật mà phương pháp phân cụm của chúng dựa trên phương pháp này như MST (tương tự thuật toán phân cụm single link), và Opossum.
Một thuật toán phân cụm phân cấp sử dụng khái niệm tự tương đồng (self-similarity) để xác định xem các cụm có nên được kết hợp. Có thể định nghĩa độ tương đồng Shared Nearest Neighbor (SNN) (phép đo độ tương đồng mới) và học thuật toán phân cụm Jarvis-Patrick, sử dụng độ tương đồng này.