グラフン

グラフ理論と統計学において、グラフオン（グラフ極限とも呼ばれる）は対称 測定可能関数であり、密なグラフの研究で重要である。グラフオンは、密なグラフのシーケンスの極限の自然な概念として、また交換可能なランダム グラフ モデルの基本的な定義オブジェクトとしての両方で発生する。グラフオンは、次の 2 つの観察によって密なグラフに関連付けられている。グラフオンによって定義されたランダム グラフ モデルは、ほぼ確実に密なグラフを生成し、正則性補題によって、グラフオンは任意の大きな密なグラフの構造を捉える。 ${\displaystyle W:[0,1]^{2}\to [0,1]}$

グラフオンは対称測定関数です。通常、グラフオンは次のスキームに従って交換可能なランダム グラフ モデルを定義するものとして理解されます。 ${\displaystyle W:[0,1]^{2}\to [0,1]}$

1. グラフの各頂点には独立したランダムな値が割り当てられる${\displaystyle j}$${\displaystyle u_{j}\sim U[0,1]}$
2. エッジは確率 でグラフに独立して含まれます。${\displaystyle (i,j)}$${\displaystyle W(u_{i},u_{j})}$

ランダム グラフ モデルは、このように (ランダムな可能性のある) グラフオンで定義できる場合にのみ、交換可能なランダム グラフ モデルです。固定グラフオンに基づくモデルは、ランダム グラフのエルデシュ-レーニモデルとの類推により、 と表記されることがあります。このようにグラフオンから生成されたグラフは、 -ランダム グラフと呼ばれます。 ${\displaystyle W}$${\displaystyle \mathbb {G} (n,W)}$${\displaystyle W}$${\displaystyle W}$

この定義と大数の法則から、交換可能なランダムグラフモデルはほぼ確実に稠密であることがわかります。^[1]${\displaystyle W\neq 0}$

グラフオンの最も単純な例は、ある定数 の場合です。この場合、関連付けられる交換可能なランダム グラフ モデルは、各エッジを独立して確率 で含むエルデシュ-レーニモデルです。 ${\displaystyle W(x,y)\equiv p}$${\displaystyle p\in [0,1]}$${\displaystyle G(n,p)}$${\displaystyle p}$

代わりに、次のように区分的に定数であるグラフオンから始めるとします。

1. 単位正方形をブロックに分割し、${\displaystyle k\times k}$
2. ブロックに等しく設定し、${\displaystyle W}$${\displaystyle p_{lm}}$${\displaystyle (\ell ,m)^{\text{th}}}$

結果として得られる交換可能なランダム グラフ モデルは、エルデシュ-レーニ モデルの一般化である コミュニティ確率ブロック モデルです。これは、それぞれパラメータを持つ異なるエルデシュ-レーニ グラフと、それらの間にバイグラフが含まれるランダム グラフ モデルとして解釈できます。この場合、ブロックとブロック間の可能な各エッジは、確率 で独立して含まれます。 ${\displaystyle k}$${\displaystyle k}$${\displaystyle p_{\ell \ell }}$${\displaystyle (\ell ,\ell )}$${\displaystyle (m,m)}$${\displaystyle p_{\ell m}}$

他の多くの一般的なランダムグラフモデルは、何らかのグラフオンによって定義された交換可能なランダムグラフモデルとして理解することができ、詳細な調査はOrbanzとRoyに含まれています。^[1]

サイズのランダムグラフは、ランダム隣接行列として表すことができます。異なるサイズのランダムグラフ間に一貫性 (射影性の意味で) を持たせるためには、ランダム変数の無限配列の左上部分行列として生じる隣接行列のシーケンスを調べるのが自然です。これにより、 にノードを追加し、 のエッジをサンプリングすることでを生成できます。この観点から、ランダムグラフはランダムな無限対称配列 として定義されます。 ${\displaystyle n}$${\displaystyle n\times n}$ ${\displaystyle n\times n}$${\displaystyle G_{n}}$${\displaystyle G_{n-1}}$${\displaystyle (j,n)}$${\displaystyle j<n}$${\displaystyle (X_{ij})}$

古典的な確率における交換可能なシーケンスの基本的な重要性に従えば、ランダムグラフの設定で類似の概念を探すのは自然なことです。そのような概念の1つは、共同交換可能な行列、つまり、

${\displaystyle (X_{ij})\ {\overset {d}{=}}\,(X_{\sigma (i)\sigma (j)})}$

自然数のすべての順列に対して、 は分布 において等しいことを意味します。直感的には、この条件は、ランダム グラフの分布は頂点のラベル付けによって変化しないことを意味します。つまり、頂点のラベルには情報が含まれません。 ${\displaystyle \sigma }$${\displaystyle {\overset {d}{=}}}$

交換可能なシーケンスに対するde Finetti の表現定理に類似した、共有交換可能なランダム隣接行列に対する表現定理があります。これは、共有交換可能な配列に対する Aldous-Hoover 定理の特殊なケースであり、この設定では、ランダム行列は次のように生成されると主張します。 ${\displaystyle (X_{ij})}$

1. 個別にサンプル採取${\displaystyle u_{j}\sim U[0,1]}$
2. ${\displaystyle X_{ij}=X_{ji}=1}$確率的に独立してランダムに${\displaystyle W(u_{i},u_{j}),}$

ここで、 は(ランダムな可能性のある) グラフオンです。つまり、ランダム グラフ モデルは、それが何らかのグラフオンによって定義された共同交換可能なランダム グラフ モデルである場合にのみ、共同交換可能な隣接行列を持ちます。 ${\displaystyle W:[0,1]^{2}\to [0,1]}$

識別可能性の問題により、グラフオン関数またはノードの潜在位置のいずれかを推定することは不可能であり、グラフオン推定には2つの主な方向があります。1つの方向は、同値クラスまで推定することを目指しています。 ^{[2] [3]}またはによって誘導される確率行列を推定します。^{[4] [5]}${\displaystyle W}$${\displaystyle u_{i},}$${\displaystyle W}$${\displaystyle W}$

頂点上の任意のグラフは、その隣接行列で識別できます。この行列はステップ関数 に対応し、 を 各 について内部 と を持ち 、 を のエントリと等しく 設定するような区間に 分割することによって定義されます。この関数は、グラフ の関連グラフオンです。 ${\displaystyle n}$${\displaystyle \{1,2,\dots ,n\}}$ ${\displaystyle A_{G}}$${\displaystyle W_{G}:[0,1]^{2}\to [0,1]}$${\displaystyle [0,1]}$${\displaystyle I_{1},I_{2},\dots ,I_{n}}$${\displaystyle I_{j}}$$${\displaystyle \left({\frac {j-1}{n}},{\frac {j}{n}}\right)}$$${\displaystyle (x,y)\in I_{i}\times I_{j}}$${\displaystyle W_{G}(x,y)}$${\displaystyle (i,j)^{\text{th}}}$${\displaystyle A_{G}}$${\displaystyle W_{G}}$${\displaystyle G}$

一般に、の頂点の数が無限大になるグラフのシーケンスがある場合、関数 の極限動作を考慮することによってシーケンスの極限動作を分析できます。これらのグラフが収束する場合 (収束の適切な定義に従って)、これらのグラフの極限はこれらの関連関数の極限に対応することが期待されます。 ${\displaystyle (G_{n})}$${\displaystyle G_{n}}$${\displaystyle (W_{G_{n}})}$

このことから、グラフフォン（「グラフ関数」の略）は、グラフのシーケンスの極限の概念を捉える対称測定可能な関数として定義される。密なグラフのシーケンスでは、一見異なる収束の概念がいくつか同等であり、それらすべてにおいて自然な極限オブジェクトはグラフフォンであることがわかった。^[6]${\displaystyle W:[0,1]^{2}\to [0,1]}$

ある固定パラメータを持つエルデシュ・レーニランダムグラフのシーケンスを取ります。直感的には、 が無限大に近づくにつれて、このグラフシーケンスの極限はこれらのグラフのエッジ密度によってのみ決まります。グラフオンの空間では、このようなシーケンスはほぼ確実に定数 に収束することがわかり、これは上記の直感を捉えています。 ${\displaystyle (G_{n})}$${\displaystyle G_{n}=G(n,p)}$${\displaystyle p}$${\displaystyle n}$${\displaystyle W(x,y)\equiv p}$

半グラフのシーケンス を取ります。これは、が のときにちょうど に隣接する頂点および上の二部グラフであると定義されます。頂点が提示された順序でリストされている場合、隣接行列は、1 で埋められた「半正方形」ブロック行列の 2 つのコーナーを持ち、残りのエントリはゼロに等しくなります。たとえば、 の隣接行列は次のように与えられます。 ${\displaystyle (H_{n})}$${\displaystyle H_{n}}$${\displaystyle 2n}$${\displaystyle u_{1},u_{2},\dots ,u_{n}}$${\displaystyle v_{1},v_{2},\dots ,v_{n}}$${\displaystyle u_{i}}$${\displaystyle v_{j}}$${\displaystyle i\leq j}$${\displaystyle A_{H_{n}}}$${\displaystyle H_{3}}$

$${\displaystyle {\begin{bmatrix}0&0&0&1&1&1\\0&0&0&0&1&1\\0&0&0&0&0&1\\1&0&0&0&0&0\\1&1&0&0&0&0\\1&1&1&0&0&0\end{bmatrix}}.}$$

が大きくなるにつれて、これらの 1 の角は「滑らか」になります。この直感に一致して、シーケンスは のときは、それ以外のときはによって定義されるハーフグラフオンに収束します。 ${\displaystyle n}$${\displaystyle (H_{n})}$${\displaystyle W}$${\displaystyle W(x,y)=1}$${\displaystyle |x-y|\geq 1/2}$${\displaystyle W(x,y)=0}$

等しい大きさの部分を持つ完全な二部グラフのシーケンスを取ります。一方の部分のすべての頂点を先頭に配置し、もう一方の部分の頂点を末尾に配置するように頂点を並べると、の隣接行列は、1 のブロック 2 つと 0 のブロック 2 つを含むブロック非対角行列のように見えます。たとえば、の隣接行列は次のように表されます 。${\displaystyle (K_{n,n})}$${\displaystyle (K_{n,n})}$${\displaystyle K_{2,2}}$

$${\displaystyle {\begin{bmatrix}0&0&1&1\\0&0&1&1\\1&1&0&0\\1&1&0&0\end{bmatrix}}.}$$

が大きくなるにつれて、隣接行列のこのブロック構造は一定のままになり、およびの場合は常に で定義される「完全な二部」グラフオンに収束し、それ以外の場合は となります。 ${\displaystyle n}$${\displaystyle W}$${\displaystyle W(x,y)=1}$${\displaystyle \min(x,y)\leq 1/2}$${\displaystyle \max(x,y)>1/2}$${\displaystyle W(x,y)=0}$

の頂点を交互に並べると、隣接行列は0と1のチェス盤構造になります。たとえば、この順序では、の隣接行列は次のように表されます 。${\displaystyle K_{n,n}}$${\displaystyle K_{2,2}}$

$${\displaystyle {\begin{bmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{bmatrix}}.}$$

が大きくなるにつれて、隣接行列はますます細かいチェス盤になります。この動作にもかかわらず、 の極限は一意であり、例 3 のグラフオンが得られるようにする必要があります。つまり、グラフのシーケンスの収束を正式に定義する場合、極限の定義は頂点の再ラベル付けに依存しない必要があります。 ${\displaystyle n}$${\displaystyle (K_{n,n})}$

ある固定されたグラフオン を描いて、 W {\displaystyle W} -ランダムグラフのランダムなシーケンスを取ります。すると、このセクションの最初の例と同様に、 はほぼ確実に に収束することがわかります。 ${\displaystyle (G_{n})}$${\displaystyle G_{n}\sim \mathbb {G} (n,W)}$${\displaystyle W}$${\displaystyle (G_{n})}$${\displaystyle W}$

グラフとそれに関連するグラフオンが与えられている場合、の変換を積分することで のグラフ理論的特性とパラメータを復元できます。たとえば、 の辺密度 (つまり、平均次数を頂点の数で割ったもの) は、積分 で与えられます。 これは、が値であり、 の各辺がが に等しい 領域 に対応する ためです。 ${\displaystyle G}$${\displaystyle W=W_{G}}$${\displaystyle G}$${\displaystyle W}$${\displaystyle G}$$${\displaystyle \int _{0}^{1}\int _{0}^{1}W(x,y)\;\mathrm {d} x\,\mathrm {d} y.}$$${\displaystyle W}$${\displaystyle \{0,1\}}$${\displaystyle (i,j)}$${\displaystyle G}$${\displaystyle I_{i}\times I_{j}}$${\displaystyle 1/n^{2}}$${\displaystyle W}$${\displaystyle 1}$

同様の推論により、三角形の密度は ${\displaystyle G}$$${\displaystyle {\frac {1}{6}}\int _{0}^{1}\int _{0}^{1}\int _{0}^{1}W(x,y)W(y,z)W(z,x)\;\mathrm {d} x\,\mathrm {d} y\,\mathrm {d} z.}$$

2 つのグラフ間の距離を測定する方法は多数あります。グラフの極値特性を「保存する」測定基準に関心がある場合は、ランダム グラフを類似として識別する測定基準にのみ注意を向ける必要があります。たとえば、ある固定値に対してエルデシュ・レーニイ モデルとは独立して 2 つのグラフをランダムに描画した場合、「妥当な」測定基準の下では、これら 2 つのグラフ間の距離は、 が大きい場合、高い確率でゼロに近くなるはずです。 ${\displaystyle G(n,p)}$${\displaystyle p}$${\displaystyle n}$

単純に言えば、同じ頂点集合上の 2 つのグラフがある場合、その距離を、一方のグラフから他方のグラフに移動するために追加または削除する必要がある辺の数、つまり編集距離として定義できます。ただし、編集距離はランダム グラフを類似として識別するものではありません。実際、 から独立して描画された 2 つのグラフの予想される (正規化された) 編集距離は です。 ${\displaystyle G(n,{\tfrac {1}{2}})}$${\displaystyle {\tfrac {1}{2}}}$

密なランダム グラフ上で、私たちが望む意味で適切に動作する自然なメトリックが 2 つあります。1 つ目はサンプリング メトリックで、サブグラフの分布が近い場合、2 つのグラフは近いとみなされます。2 つ目はエッジ不一致メトリックで、2 つのグラフのエッジ密度が対応する頂点のサブセットすべてで近い場合、2 つのグラフは近いとみなされます。

不思議なことに、グラフの列は、あるメトリックに関して収束するとき、他のメトリックに関して収束する。さらに、両方のメトリックの下での極限オブジェクトはグラフオンであることが判明した。収束のこれら2つの概念の等価性は、準ランダムグラフのさまざまな概念が等価であることを反映します。^[7]

2 つのグラフとの間の距離を測定する 1 つの方法は、それらの相対的なサブグラフ数を比較することです。つまり、各グラフ について、と におけるのコピー数を比較できます。これらの数がすべてのグラフ について近い場合、直感的にと は似たグラフであることがわかります。ただし、サブグラフを直接処理するよりも、グラフ準同型性を扱う方が簡単であることがわかります。これは、大きくて密なグラフを処理する場合は問題ありません。このシナリオでは、固定グラフからのサブグラフの数とグラフ準同型の数は漸近的に等しいためです。 ${\displaystyle G}$${\displaystyle H}$${\displaystyle F}$${\displaystyle F}$${\displaystyle G}$${\displaystyle F}$${\displaystyle H}$${\displaystyle F}$${\displaystyle G}$${\displaystyle H}$

2 つのグラフとが与えられたとき、 におけるの準同型密度はからへのグラフ準同型性の個数として定義されます。言い換えると、 はの頂点から の頂点へのランダムに選択された写像がの隣接頂点を の隣接頂点に送る確率です。 ${\displaystyle F}$${\displaystyle G}$ ${\displaystyle t(F,G)}$${\displaystyle F}$${\displaystyle G}$${\displaystyle F}$${\displaystyle G}$${\displaystyle t(F,G)}$${\displaystyle F}$${\displaystyle G}$${\displaystyle F}$${\displaystyle G}$

グラフオンは準同型密度を計算する簡単な方法を提供します。実際、グラフオンと別のグラフが与えられた場合、 ${\displaystyle G}$${\displaystyle W_{G}}$${\displaystyle F}$

$${\displaystyle t(F,G)=\int \prod _{(i,j)\in E(F)}W_{G}(x_{i},x_{j})\;\left\{\mathrm {d} x_{i}\right\}_{i\in V(F)}}$$

ここで積分は多次元であり、単位超立方体 上でとられる。これは、上記の被積分関数が に等しい場合を考えることによって、関連するグラフオンの定義から導かれる。次に、同じ積分を使用して定義することにより、 準同型密度の定義を任意のグラフオン に拡張することができる。${\displaystyle [0,1]^{V(F)}}$${\displaystyle 1}$${\displaystyle W}$

$${\displaystyle t(F,W)=\int \prod _{(i,j)\in E(F)}W(x_{i},x_{j})\;\left\{\mathrm {d} x_{i}\right\}_{i\in V(F)}}$$

任意のグラフに対して。 ${\displaystyle F}$

この設定において、任意の固定グラフ に対して準同型密度のシーケンスが収束する場合、グラフのシーケンスは左収束するといいます。定義だけでは明らかではありませんが、 がこの意味で収束する場合、任意のグラフ に対して、同時に となる グラフオンが常に存在します 。 ${\displaystyle (G_{n})}$${\displaystyle F}$${\displaystyle \left(t(F,G_{n})\right)}$${\displaystyle (G_{n})}$${\displaystyle W}$${\displaystyle F}$$${\displaystyle \lim _{n\to \infty }t(F,G_{n})=t(F,W)}$$

同じ頂点セット上の2 つのグラフとを取ります。これらのグラフは同じ頂点を共有しているため、それらの距離を測定する 1 つの方法は、頂点セットのサブセットに制限し、そのような各ペアについて、サブセットはから へのエッジの数をとの間のエッジの数と比較します。これらの数がサブセットのすべてのペアで類似している場合 (頂点の総数に対して)、 と は類似のグラフであると考えられます。 ${\displaystyle G}$${\displaystyle H}$${\displaystyle X,Y}$${\displaystyle e_{G}(X,Y)}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle G}$${\displaystyle e_{H}(X,Y)}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle H}$${\displaystyle G}$${\displaystyle H}$

この距離の概念の予備的な定式化として、サイズ の同じ頂点集合上の任意のグラフのペアとに対して、との間のラベル付きカット距離を次のように 定義します。${\displaystyle G}$${\displaystyle H}$${\displaystyle V}$${\displaystyle |V|=n}$${\displaystyle G}$${\displaystyle H}$

$${\displaystyle d_{\square }(G,H)={\frac {1}{n^{2}}}\max _{X,Y\subseteq V}\left|e_{G}(X,Y)-e_{H}(X,Y)\right|.}$$

言い換えれば、ラベル付きカット距離は、と間のエッジ密度の最大差異をエンコードします。この概念をグラフオンに一般化するには、エッジ密度を関連するグラフオンで表し、次の式を与えます。 ${\displaystyle G}$${\displaystyle H}$${\displaystyle {\tfrac {1}{n^{2}}}e_{G}(X,Y)}$${\displaystyle W_{G}}$

$${\displaystyle d_{\square }(G,H)=\max _{X,Y\subseteq V}\left|\int _{I_{X}}\int _{I_{Y}}W_{G}(x,y)-W_{H}(x,y)\;\mathrm {d} x\,\mathrm {d} y\right|}$$

ここで、 は、および の頂点に対応する区間の和集合です。比較するグラフが頂点セットを共有していない場合でも、この定義を使用できることに注意してください。これにより、次のより一般的な定義が生まれます。 ${\displaystyle I_{X},I_{Y}\subseteq [0,1]}$${\displaystyle X}$${\displaystyle Y}$

定義1.任意の対称な測定可能な関数 に対して、のカットノルムを次の量と 定義する。${\displaystyle f:[0,1]^{2}\to \mathbb {R} }$${\displaystyle f}$

$${\displaystyle \lVert f\rVert _{\square }=\sup _{S,T\subseteq [0,1]}\left|\int _{S}\int _{T}f(x,y)\;\mathrm {d} x\,\mathrm {d} y\right|}$$単位区間の 測定可能な部分集合全てを対象にした。 ^[6]${\displaystyle S,T}$

これは、等式 が得られるため、以前のラベル付きカット距離の概念を捉えています。 ${\displaystyle \lVert W_{G}-W_{H}\rVert _{\square }=d_{\square }(G,H)}$

この距離測定には、依然として 1 つの大きな制限があります。それは、2 つの同型グラフに非ゼロの距離を割り当てることができることです。同型グラフの距離がゼロであることを確認するには、頂点のすべての可能な「再ラベル付け」にわたって最小カット ノルムを計算する必要があります。これが、カット距離の次の定義の理由です。

定義2.任意のグラフオンとに対して、カット距離を次のように 定義する。${\displaystyle U}$${\displaystyle W}$

$${\displaystyle \delta _{\square }(U,W)=\inf _{\varphi }\lVert U-W^{\varphi }\rVert _{\square }}$$ ここで は写像 との合成であり、最小値は単位区間からそれ自身への測度保存の全単射について取られる。 ^[8]${\displaystyle W^{\varphi }(x,y)=W(\varphi (x),\varphi (y))}$${\displaystyle W}$${\displaystyle \varphi }$

2 つのグラフ間のカット距離は、関連するグラフオン間のカット距離として定義されます。

グラフのシーケンスがカット距離 の下で収束するとは、それがカット距離 の下でコーシー シーケンスである場合を言います。定義から直接導かれる結果ではありませんが、そのようなグラフのシーケンスがコーシーである場合、それは常に何らかのグラフオン に収束します。 ${\displaystyle (G_{n})}$${\displaystyle \delta _{\square }}$${\displaystyle W}$

結局のところ、任意のグラフのシーケンスに対して、左収束はカット距離での収束と同等であり、さらに、極限グラフオンは同じです。同じ定義を使用してグラフオン自体の収束を考えることもできますが、同じ同値性が当てはまります。実際、収束の両方の概念は、計数補題と呼ばれるものを通じてより強く関連しています。^[6]${\displaystyle (G_{n})}$${\displaystyle W}$

計数補題。任意のグラフオンのペアとに対して、 ${\displaystyle U}$${\displaystyle W}$

$${\displaystyle |t(F,U)-t(F,W)|\leq e(F)\delta _{\square }(U,W)}$$ すべてのグラフに対して。 ${\displaystyle F}$

「計数補題」という名前は、グラフのサブグラフ数に類似した準同型密度にこの補題が与える境界に由来しています。この補題は、正則性分割の分野に現れるグラフ計数補題の一般化であり、カット距離での収束は左収束を意味することを直ちに示します。 ${\displaystyle t(F,W)}$

逆数え上げ補題。任意の実数に対して、任意のグラフオンのペアと に対して、${\displaystyle \varepsilon >0}$${\displaystyle \eta >0}$${\displaystyle k}$${\displaystyle U}$${\displaystyle W}$

$${\displaystyle |t(F,U)-t(F,W)|\leq \eta }$$を満たす すべてのグラフに対して、 が成り立つ必要があります。 ${\displaystyle F}$${\displaystyle v(F)\leq k}$${\displaystyle \delta _{\square }(U,W)<\varepsilon }$

この補題は、左収束はカット距離での収束を意味することを示しています。

すべてのグラフオンの集合を取り、のときはいつでも2 つのグラフオンを識別することによって、カット距離をメトリックにすることができます。結果として得られるグラフオンの空間は と表され、 とともにメトリック空間を形成します。 ${\displaystyle U\sim W}$${\displaystyle \delta _{\square }(U,W)=0}$${\displaystyle {\widetilde {\mathcal {W}}}_{0}}$${\displaystyle \delta _{\square }}$

この空間はコンパクトであることがわかります。さらに、この空間には、関連するグラフオンによって表されるすべての有限グラフの集合が稠密な部分集合として含まれています。これらの観察から、グラフオンの空間は、カット距離に関するグラフの空間の完備化であることが分かります。このことからすぐにわかる結論の 1 つは次のとおりです。

系 1.任意の実数 に対して、となる整数 が存在し、任意のグラフオン に対して、となる頂点が最大で 個あるグラフ が存在する。 ${\displaystyle \varepsilon >0}$${\displaystyle N}$${\displaystyle W}$${\displaystyle G}$${\displaystyle N}$${\displaystyle \delta _{\square }(W,W_{G})<\varepsilon }$

理由を理解するために、 をグラフの集合とします。各グラフについて、となるすべてのグラフオンを含む開球を考えます。すべてのグラフの開球の集合は を覆うので、コンパクト性は、ある有限部分集合 に対して有限部分被覆が存在することを意味します。これで、 のグラフの中で頂点の最大数を とすることができます。 ${\displaystyle {\mathcal {G}}}$${\displaystyle G\in {\mathcal {G}}}$${\displaystyle B_{\square }(G,\varepsilon )}$${\displaystyle W}$${\displaystyle \delta _{\square }(W,W_{G})<\varepsilon }$${\displaystyle {\widetilde {\mathcal {W}}}_{0}}$${\displaystyle \{B_{\square }(G,\varepsilon )\mid G\in {\mathcal {G}}_{0}\}}$${\displaystyle {\mathcal {G}}_{0}\subset {\mathcal {G}}}$${\displaystyle N}$${\displaystyle {\mathcal {G}}_{0}}$

グラフオンの空間のコンパクト性は、セメレディの正則性補題の解析的定式化として考えることができます。実際、元の補題よりも強い結果です。^[9] セメレディの正則性補題は、次のようにグラフオンの言語に翻訳できます。ステップ関数を、区分的に定数であるグラフオン、つまりのある分割に対して、すべての に対してで定数であるグラフオンとして定義します。グラフに正則性分割があるというステートメントは、それに関連付けられたグラフオンがステップ関数に近いと 言うことと同等です。${\displaystyle ({\widetilde {\mathcal {W}}}_{0},\delta _{\square })}$${\displaystyle W}$${\displaystyle {\mathcal {P}}}$${\displaystyle [0,1]}$${\displaystyle W}$${\displaystyle S\times T}$${\displaystyle S,T\in {\mathcal {P}}}$${\displaystyle G}$${\displaystyle W_{G}}$

コンパクト性の証明には、弱い正則性補題のみが必要です。

グラフオンの弱い正則性補題。すべてのグラフオンおよびに対して、最大でステップとなるステップ関数が存在します。 ${\displaystyle W}$${\displaystyle \varepsilon >0}$${\displaystyle W'}$${\displaystyle \lceil 4^{1/\varepsilon ^{2}}\rceil }$${\displaystyle \lVert W-W'\rVert _{\square }\leq \varepsilon }$

しかし、これは強い正則性補題のようなより強い正則性の結果を証明するために使用することができます。

グラフオンの強い正則性補題。任意の正の実数列に対して、任意のグラフオンに対して、グラフオンと、ステップ関数が存在し、そのステップは次のように表される。${\displaystyle \mathbf {\varepsilon } =(\varepsilon _{0},\varepsilon _{1},\dots )}$${\displaystyle S}$${\displaystyle W}$${\displaystyle W'}$${\displaystyle U}$${\displaystyle k<S}$${\displaystyle \lVert W-W'\rVert _{1}\leq \varepsilon _{0}}$${\displaystyle \lVert W'-U\rVert _{\square }\leq \varepsilon _{k}.}$

強い正則性の補題の証明は、概念的には上記の系 1 に似ています。すべてのグラフンはノルムのステップ関数で近似できることがわかり、ボールの集合がを覆うことが示されます。これらの集合は計量では開いていませんが、わずかに拡大して開くことができます。ここで、有限のサブカバーを取り、目的の条件が満たされることを示すことができます。 ${\displaystyle W}$${\displaystyle U}$ ${\displaystyle L_{1}}$${\displaystyle B_{1}(U,\varepsilon _{0})}$${\displaystyle {\widetilde {\mathcal {W}}}_{0}}$${\displaystyle \delta _{\square }}$

グラフンの解析的性質により、準同型性に関連する不等式を攻撃する際の柔軟性が向上します。

例えば、シドレンコ予想は極限グラフ理論における主要な未解決問題であり、平均次数（ある に対して）の頂点上の任意のグラフと、頂点および辺上の二部グラフに対して、からへの準同型の数は少なくとも であると主張している。^[10]この量はランダムグラフ における のラベル付きサブグラフの期待数であるため、この予想は、任意の二部グラフ に対して、ランダムグラフは（期待値として）ある固定された辺密度を持つすべてのグラフ上で のコピー数が最小になるという主張として解釈できる。 ${\displaystyle G}$${\displaystyle n}$${\displaystyle pn}$${\displaystyle p\in [0,1]}$${\displaystyle H}$${\displaystyle v}$${\displaystyle e}$${\displaystyle H}$${\displaystyle G}$${\displaystyle p^{e}n^{v}}$${\displaystyle H}$${\displaystyle G(n,p)}$${\displaystyle H}$${\displaystyle H}$

シドレンコ予想に対する多くのアプローチは、問題をグラフオン上の積分不等式として定式化し、他の解析的アプローチを使用して問題に取り組むことを可能にする。^[11]

グラフオンは、密な単純グラフと自然に結びついています。このモデルは、密な有向重み付きグラフに拡張されており、装飾グラフオンと呼ばれることもあります。^{[12]また、ランダムグラフモデル[13]}とグラフ極限理論[14]の両方の観点から、スパースグラフ領域への最近の拡張もあります。^{[15 ]}