要約
本論文では、高次元データのクラスタリングに用いる単純かつ効果的なグラフベースの凝集型アルゴリズムを提案する。我々は、グラフ理論における2つの基本概念である入次数（indegree）と出次数（outdegree）がクラスタリングにおいて果たす異なる役割を探求する。平均入次数はサンプル近傍の密度を反映し、平均出次数はサンプル周辺の局所幾何学的特性を特徴づける。このような洞察に基づいて、我々はクラスター間の親和性測定値を平均入次数と平均出次数の積により定義する。積に基づく親和性測定値は、アルゴリズムに対してノイズに対する堅牢性をもたらす。このアルゴリズムには3つの主要な利点がある：優れた性能、簡単な実装、高い計算効率。我々はこのアルゴリズムを2つの基本的なコンピュータビジョン問題、すなわち画像クラスタリングとオブジェクトマッチングに適用し、広範な実験を通じて両方の応用で最先端技術を上回る性能を示していることを確認した。