将一组物理或抽象对象组合成相同对象的类的过程称为聚类。集群是一组数据对象，它们在同一集群中彼此相同，但与其他集群中的对象不同。在多个应用程序中，可以将一组数据对象统称为一个组。聚类分析是一项必不可少的人类活动。
聚类支持识别异常值。相同的值被组织成集群，那些落在集群之外的值被称为异常值。聚类技术将数据元组视为对象。它们将对象划分为组或集群，以便集群内的对象彼此“相似”，而与其他集群中的对象“不相似”。它通常根据距离函数定义为对象在空间中的“接近”程度。
基于图的聚类有多种方法如下 -
稀疏邻近图以仅维护对象与其最近邻居的链接。这种稀疏化有利于管理噪声和异常值。它还可以使用为稀疏图生成的非常有效的图分割算法。
它可以基于两个对象发送的几个最近邻居来表示两个对象之间的相似性度量。这种方法依赖于观察对象及其最近的邻居通常属于同一类，有利于克服高维和密度变化集群的问题。
它可以表示核心对象并围绕它们发展集群。在基于图的聚类中，有必要引入基于邻近图或稀疏邻近图的密度概念。与 DBSCAN 一样，围绕核心对象开发集群会产生一种可以发现不同形状和大小的集群的集群方法。
它可以使用邻近图中的数据来支持更复杂的计算是否应该组合两个集群。特别是，只有当结果集群与最初的两个集群具有相同的特征时，才会合并两个集群。
它可以从讨论邻近图的稀疏化开始，支持两种技术实例，其聚类方法基于这种方法，例如与单连接聚类算法相同的 MST 和 Opossum。
一种层次聚类算法，需要自相似性的概念来确定是否应组合聚类。它可以定义共享最近邻(SNN)相似度，一种新的相似度度量）并学习需要这种相似度的 Jarvis-Patrick 聚类算法。