オブジェクトに対する埋め込み（embedding）を持っています。グラフの類似度（similarity）に基づく「類似グラフ」を構築し、コミュニティを見つけたい――GraphRAGでも、レコメンドシステムでも、あるいはデータに潜む構造を探すだけでも構いません。そこで、各ペアの類似度を計算し、グラフを作って、Louvainを実行します。ところが今回は、エッジ数が O(n^2) になってしまい、ノードが約15Kを超えると処理がクラッシュします。
VLouvainはLouvainを言い換えて、埋め込み行列（embedding matrix）に対して直接動作するようにしています。次数（degrees）やモジュラリティの増分（modularity gains）は、コミュニティ単位のベクトル和から計算され、エッジは一切使いません。O(n^2) の代わりに O(n*d) の状態（state）を維持します。その結果は、標準的なLouvainと数学的に同一であり、近似ではありません。
Amazon Products（ノード数1.57M、d=200）では、VLouvainは約11,300秒で完了します。私たちがテストした他の手法（cuGraph、iGraph、GVE、NetworKit）は、いずれも同じスケールの半分に到達する前に失敗しました。
もう1つ、予想外だったことがあります。Top-Kの疎化（sparsification）では助けになりません。FAISSを使って、厳密版と近似版のTop-Kグラフを構築しましたが、K=256でも、フルグラフに対するNMI（Normalized Mutual Information）は約0.04でした。類似度グラフを切り詰めてLouvainを成立させようとしているなら、返ってくるのは本質的にランダムなコミュニティです。
GraphRAGにおけるグラフ構築の「ドロップイン代替（drop-in replacement）」として使うと、インデックス作成は3時間から5.3分へ短縮されました。MultiHopRAGでのリトリーバル（retrieval）リコールは、37.9%から48.8%へ改善しました。
論文（EDBT 2026）： https://openproceedings.org/2026/conf/edbt/paper-72.pdf
[link] [comments]
