グラフ分割

数学において、グラフ分割とは、グラフのノード セットを相互に排他的なグループに分割することによって、グラフをより小さなグラフに縮小することです。グループ間を交差する元のグラフのエッジは、分割されたグラフのエッジを生成します。結果として得られるエッジの数が元のグラフに比べて少ない場合、分割されたグラフは元のグラフよりも分析や問題解決に適している可能性があります。グラフ分析を簡素化する分割を見つけることは難しい問題ですが、科学計算、VLSI回路設計、マルチプロセッサ コンピュータのタスク スケジューリングなどに応用されています。^[1]最近、グラフ分割問題は、社会的、病理学的、生物学的ネットワークにおけるクラスター化とクリークの検出への応用により重要性を増しています。計算方法とアプリケーションの最近の傾向に関する調査については、Buluc ら (2013) を参照してください。^{[2]グラフ分割の一般的な 2 つの例は、}最小カット問題と最大カット問題 です。

通常、グラフ分割問題はNP 困難問題のカテゴリに分類されます。これらの問題の解決策は、一般的にヒューリスティックと近似アルゴリズムを使用して導出されます。^[3]ただし、均一なグラフ分割またはバランスのとれたグラフ分割問題は、任意の有限係数内で近似するためにNP 完全であることが示されています。 ^[1]ツリーやグリッドなどの特殊なグラフクラスの場合でも、P = NPでない限り、合理的な近似アルゴリズムは存在しません。 ^{[4]グリッドは}、有限要素モデル (FEM)シミュレーションから得られるグラフをモデル化するため、特に興味深いケースです。コンポーネント間のエッジの数だけでなく、コンポーネントのサイズも近似すると、これらのグラフに対して合理的な完全多項式アルゴリズムが存在しないことがわかります。^[4]

グラフG = ( V , E ) を考えます。ここで、V はn個の頂点の集合、E は辺の集合を表します。 ( k , v ) バランス分割問題では、G を最大でもサイズv · ( n / k ) のk個の要素に分割し、個々の要素間の辺の容量を最小化することが目的です。^[1]また、Gと整数k > 1 が与えられた場合、V をk 個の部分 (サブセット) V ₁、V ₂、...、V _kに分割します。このとき、各部分は互いに素でサイズが等しく、異なる部分にエンドポイントを持つ辺の数は最小化されます。このような分割問題は、文献ではバイクライテリア近似法やリソース拡張アプローチとして議論されてきました。一般的な拡張はハイパーグラフへの拡張で、1 つの辺で 3 つ以上の頂点を接続できます。ハイパーエッジは、すべての頂点が 1 つのパーティション内にある場合はカットされず、それ以外の場合は各側​​にいくつ頂点があっても 1 回だけカットされます。この使用法は、電子設計オートメーションでよく使用されます。

特定の ( k , 1 +  ε ) バランス分割問題では、各コンポーネントが最大 (1 +  ε )·( n / k ) 個のノードを含むk 個のコンポーネントへのGの最小コスト分割を見つけようとします。この近似アルゴリズムのコストを、 k 個のコンポーネントのそれぞれが同じサイズの ( n / k ) 個のノードを持つ必要がある( k ,1) カットのコストと比較します。したがって、より制限された問題になります。

${\displaystyle \max _{i}|V_{i}|\leq (1+\varepsilon )\left\lceil {\frac {|V|}{k}}\right\rceil .}$

(2,1) カットが最小二分問題であり、NP 完全であることは既にわかっています。^[5]次に、 n  = 3 kである 3 分割問題を評価します。これは多項式時間で制限されます。^{[1]ここで、 (} k 、 1) バランス分割の有限近似アルゴリズムがあると仮定すると、3 分割インスタンスはGのバランスの取れた ( k、 1) 分割を使用して解決できるか、解決できないかのどちらかになります。 3 分割インスタンスが解決できる場合、Gの ( k、 1) バランス分割問題は、エッジをカットせずに解決できます。 3 分割インスタンスが解決できない場合は、Gの最適な ( k、 1) バランス分割では、少なくとも 1 つのエッジがカットされます。 有限近似係数を持つ近似アルゴリズムは、これら 2 つのケースを区別する必要があります。 したがって、 P  =  NPという仮定の下では矛盾する 3 分割問題を解決できます。したがって、( k ,1)バランス分割問題には、 P  =  NPでない限り、有限近似係数を持つ多項式時間近似アルゴリズムが存在しないことは明らかである。^[1]

平面セパレータ定理は、任意のn頂点平面グラフは、 O( √n )個の頂点を削除することでほぼ均等な部分に分割できることを示しています。分割セットは辺ではなく頂点で構成されているため、これは上記の意味での分割ではありません。ただし、同じ結果は、制限された次数の平面グラフはすべて、O( √n )個の辺を持つバランスの取れたカットを持つことも意味します。

グラフの分割は難しい問題なので、実用的なソリューションはヒューリスティックに基づいています。方法には、ローカルとグローバルという 2 つの大きなカテゴリがあります。よく知られているローカルな方法としては、Kernighan–Lin アルゴリズムとFiduccia-Mattheyses アルゴリズムがあり、これらはローカル検索戦略による最初の効果的な 2 方向カットでした。これらの主な欠点は、頂点セットの初期分割が任意であり、最終的なソリューションの品質に影響を与える可能性があることです。グローバルなアプローチは、グラフ全体の特性に依存し、任意の初期パーティションに依存しません。最も一般的な例は、隣接行列の近似固有ベクトルからパーティションを導出するスペクトル分割、またはグラフのラプラシアン行列の固有分解を使用してグラフの頂点をグループ化するスペクトル クラスタリングです。

マルチレベルグラフ分割アルゴリズムは、1 つ以上のステージを適用することによって機能します。各ステージでは、頂点とエッジを折りたたむことによってグラフのサイズを縮小し、小さいグラフを分割してから、元のグラフのこのパーティションをマップして改良します。^[6]全体的なマルチレベルスキーム内で、さまざまな分割および改良方法を適用できます。多くの場合、このアプローチは、実行時間が短く、結果の品質が非常に高くなります。このようなアプローチの広く使用されている例の 1 つに、グラフ パーティショナーのMETIS ^[7]と、ハイパーグラフ用の対応するパーティショナーの hMETIS があります。^{[8] [9]}に由来し 、たとえばscikit-learnに実装されている 別のアプローチは、マルチグリッド事前処理を使用したLOBPCGソルバーによって計算された元のグラフのグラフ ラプラシアンマトリックスの固有ベクトルから決定されるパーティションによるスペクトル クラスタリングです。

隣接行列を持つグラフが与えられ、ここで のエントリはノードと の間の辺を意味し、次数行列は対角行列であり、行 の各対角エントリ はノード のノード次数を表します。ラプラシアン行列は と定義されます。ここで、グラフ の比カット分割は、を互いに素な、および に分割し、比を最小化するよう に定義されます。${\displaystyle G=(V,E)}$ ${\displaystyle A}$${\displaystyle A_{ij}}$${\displaystyle i}$${\displaystyle j}$ ${\displaystyle D}$${\displaystyle i}$${\displaystyle d_{ii}}$${\displaystyle i}$ ${\displaystyle L}$${\displaystyle L=DA}$${\displaystyle G=(V,E)}$${\displaystyle V}$${\displaystyle U}$${\displaystyle W}$

${\displaystyle {\frac {|E(G)\cap (U\times W)|}{|U|\cdot |W|}}}$

実際にこのカットを横切る辺の数と、そのような辺をサポートできる頂点のペアの数の比。スペクトルグラフ分割は、振動する弦や質量バネシステムの分割との類推によって^[10]導かれ、同様にグラフの重みが負の場合にも拡張される。^[11]

このようなシナリオでは、の2 番目に小さい固有値( ) によって、を使用した比カット分割の最適コスト ( ) の下限値が得られます。に対応する固有ベクトル ( ) はフィードラーベクトルと呼ばれ、対応するベクトルエントリ の符号に基づいてグラフを 2 つのコミュニティにのみ二分します。 より多くのコミュニティに分割するには、二分を繰り返すか、最小の固有値に対応する複数の固有ベクトルを使用します。 ^[12]図 1、2 の例は、スペクトル二分アプローチを示しています。 ${\displaystyle \lambda_{2}}$${\displaystyle L}$${\displaystyle c}$${\displaystyle c\geq {\frac {\lambda _{2}}{n}}}$${\displaystyle V_{2}}$${\displaystyle \lambda_{2}}$

しかし、最小カット分割は、分割するコミュニティの数や分割サイズが不明な場合には失敗します。たとえば、フリーグループのサイズに合わせてカットサイズを最適化すると、すべての頂点が同じコミュニティに配置されます。さらに、コミュニティ間のエッジの数が少ない分割だけが適切とは限らないため、カットサイズを最小化するのは間違っている可能性があります。このため、バランスの取れたグラフ分割を最適化するためのメトリックとしてモジュラリティ(Q) ^[13]が使用されました。図 3 の例は、同じグラフの 2 つのインスタンスを示しています。(a)ではモジュラリティ (Q) が分割メトリックであり、(b)では比率カットが分割メトリックです。

グラフ分割に使用されるもう 1 つの目的関数は、カット エッジの数と最小部分の体積の比率であるコンダクタンスです。コンダクタンスは、電気の流れとランダム ウォークに関連しています。Cheeger境界により、スペクトル二分によってほぼ最適なコンダクタンスを持つパーティションが提供されるようになります。この近似の品質は、ラプラシアン λ ₂の 2 番目に小さい固有値によって決まります。

グラフパーティションは、流行を止めるために免疫化する必要があるノードまたはリンクの最小限のセットを識別するのに役立ちます。^[14]

スピンモデルは多変量データのクラスタリングに使用されており、類似性が結合強度に変換されます。^[15]基底状態のスピン構成の特性は、コミュニティとして直接解釈できます。したがって、グラフは分割され、分割されたグラフのハミルトニアンが最小化されます。ハミルトニアン( H) は、次の分割報酬とペナルティを割り当てることによって導出されます。

• 同じグループ（同じスピン）のノード間の内部エッジに報酬を与える
• 同じグループ内の欠落エッジにペナルティを課す
• 異なるグループ間の既存のエッジにペナルティを課す
• 異なるグループ間の非リンクに報酬を与えます。

さらに、カーネルPCAベースのスペクトルクラスタリングは最小二乗サポートベクターマシンフレームワークの形式を採用しているため、データエントリを最大分散を持つカーネル誘導特徴空間に投影することが可能になり、投影されたコミュニティ間の高い分離が示唆されます。^[16]

いくつかの手法では、グラフ分割を多基準最適化問題として表現し、各ノードが選択したパーティションを決定するゲーム理論的枠組みで表現されたローカルメソッドを使用して解決することができます。^[17]

非常に大規模な分散グラフの場合、従来のパーティション分割手法（スペクトル分割、Metis ^[7]など）は適用できない可能性があります。これは、グローバル操作を実行するためにグラフデータへの完全なアクセスが必要になるためです。このような大規模なシナリオでは、分散グラフ分割を使用して、非同期のローカル操作のみでパーティション分割を実行します。

scikit-learnは、 ARPACK、またはマルチグリッド前処理を備えたLOBPCGソルバーによって計算された元のグラフのグラフラプラシアン行列の固有ベクトルから決定される分割を使用してスペクトルクラスタリングを実装します。^[9]

METIS ^[7]はKarypisとKumarによるグラフ分割ファミリである。このファミリの中で、kMetisは分割速度の向上を目指し、hMetis ^[8]はハイパーグラフに適用され分割品質を目指し、ParMetis ^[7]はMetisグラフ分割アルゴリズムの並列実装である。

KaHyPar ^{[18] [19] [20]}は、直接k-wayおよび再帰二分法に基づく分割アルゴリズムを提供するマルチレベルハイパーグラフ分割フレームワークです。これは、階層の各レベルから1つの頂点のみを削除する、最も極端なバージョンのマルチレベルアプローチをインスタンス化します。この非常に細かいnレベルのアプローチと強力なローカル検索ヒューリスティックを組み合わせることで、非常に高品質のソリューションを計算します。

Scotch ^[21]はPellegriniによるグラフ分割フレームワークです。再帰的な多段階二分法を使用し、順次分割技術と並列分割技術の両方を備えています。

Jostle ^[22]はChris Walshawによって開発された順次並列グラフ分割ソルバーである。このパーティショナーの商用版はNetWorksとして知られている。

Party ^[23]は、Bubble/shape最適化フレームワークとHelpful Setsアルゴリズムを実装している。

MeyerhenkeによるソフトウェアパッケージDibaP ^[24]とそのMPI並列版PDibaP ^[25]は、拡散法を用いたBubbleフレームワークを実装しています。DibaPは、拡散アプローチで生じる線形システムの粗化と解決にAMGベースの手法も使用しています。

サンダースとシュルツは、フローベースの方法、より局所的な局所検索、いくつかの並列および順次メタヒューリスティックなどを実装した グラフ分割パッケージKaHIP ^{[26] (Karlsruhe High Quality Partitioning)をリリースしました。}

^{TrifunovicとKnottenbeltによるParkway [27]}やDevineらによる Zoltan ^[28]などのツールはハイパーグラフの分割に重点を置いています。

• ビショー、チャールズ・エドモンド、シアリー、パトリック（2011）。グラフ分割：最適化とアプリケーション。ISTE – Wiley。ISBN 978-1-84821-233-6。