近傍グラフ

近傍グラフの基本概念

近傍グラフは、ある対象集合 \(V=\{v_i\}\) に対し、「互いが近い」「関係が強い」とみなす基準にもとづいて辺 \(E\) を定めたグラフ \(G=(V,E)\) である。各頂点は対象を表し、辺は近傍関係（相互の近さ、あるいは一方向の近さ）を表す。データ点の幾何的位置、特徴量の類似度、統計量の関係など、対象に応じて「近さ」を測る規則を設計し、それによりグラフの構造が決まる。

近傍グラフは局所構造を抽出するための基盤となり、局所的な近接性を通じて大域的な性質（連結性、クラスタ境界、拡散の振る舞い等）を推測する方向で利用される。定義の選択（例えば距離ベースか、確率的相関ベースか）により、生成されるグラフの密度や次数の偏り、計算負荷、下流タスクの頑健性が変化する。

近傍関係の定義

近傍関係は、各頂点の周囲に「近い」と判定する相手集合を割り当てる規則として定義される。典型的には、対象が持つ距離あるいは類似度に関する関数を用い、閾値や順位に基づいて辺を張る。距離空間であれば「ある点から距離が一定以内」や「最も近い \(k\) 個」といった形が自然である。

近傍関係には対称性を含むかどうかという設計上の論点がある。たとえば「\(u\) から見て \(v\) が近い」ことと「\(v\) から見て \(u\) が近い」ことは一致しない場合があり、有向や半対称な規則が生じる。さらに、確率的な関係（推定された結びつきの強さ）により、重み付き辺として表現されることもある。

グラフとしての表現

近傍グラフは、グラフ理論の形式に合わせて頂点集合と辺集合を明確に与えればよい。実装や解析では、辺の向き、重み、自己ループの扱いなどを決めることが重要になる。

頂点と辺の対応

頂点 \(V\) は対象要素そのものに対応する。連続空間から得たサンプル点、観測されたデータベクトル、あるいは特徴選択後に残したエンティティなど、用途に応じて要素が決まる。辺 \(E\) は近傍関係を表す。距離に基づく場合、閾値条件や順位条件により「近い組」を列挙して辺にする。

重み付き表現では、辺の重みが距離反比例、類似度そのもの、あるいは距離を変換した核関数値などに対応する。重みなしの場合は、条件を満たすか否かだけを用い、解析上は次数や到達可能性が直接利用される。

有向・無向の違い

無向グラフは対称な近傍関係に対応する。つまり、\(u\) が \(v\) を近傍とみなすなら \(v\) も \(u\) を近傍とみなす、といった条件が成り立つ。半径近傍を距離で定め、対称性が自動的に得られるような場合には無向になりやすい。

有向グラフは、順位や確率の方向性が残る設計で生じる。典型例として、各点から見て上位 \(k\) 個を結ぶ形式では、片側だけが選ばれることがありうる。無向化（後述）を行うことで対称性を強制することも可能であり、解析結果に影響を及ぼす。

典型的な目的と役割

近傍グラフは、局所的な構造を全体の計算対象へ橋渡しする役を担う。たとえば計算幾何では、点群の近傍関係から空間を分割したり、近接探索の支援データ構造を構成したりする。機械学習では、学習済み表現の近さをグラフ化して拡散、埋め込み、半教師あり推論、近傍集約などへつなげる。

また、クラスタリングでは、連結成分やグラフカットの観点から「似ている点が同じ領域にまとまる」ことを近傍関係が支える。加えて、近傍探索の計算量を抑えるために、明示的な全結合を避けて疎な結線だけを扱うという実務上の利点もある。結果として、計算量と表現力のトレードオフを制御する手段として機能する。

代表的な近傍グラフの種類

近傍グラフの代表的な種類は、「近さ」の基準をどう線形化（閾値化・順位化）するかで分類できる。大きくは \(k\) で制御する方法、距離の半径で制御する方法、相互関係により厳格化する方法、最近傍の連鎖に基づく方法などがある。

k近傍グラフ

k近傍グラフは、各頂点から最も近い（距離が小さい、類似度が大きい）対象をちょうど \(k\) 個選んで結ぶことで定義される。選ばれる対象の順位により、距離スケールの影響を相対的な順位に変換できる点が特徴である。

kの選び方と効果

\(k\) は局所性と連結性のバランスを決めるパラメータである。小さい \(k\) はきめ細かな局所近接を反映しやすいが、データが疎な領域では連結性が崩れ、グラフが断片化しやすい。逆に大きい \(k\) は成分をつなぎやすくなる一方、遠めの関係まで混ざって局所性が薄れる。

選定の実務では、データ数、ノイズ量、密度のムラ、下流タスクが求める粒度に応じた調整が行われる。解析面では、次数分布の上限が制御されるため疎な構造を保ちやすいが、密度が一様でない場合には局所密度の違いが次数分布の偏りとして現れうる。

半径近傍グラフ

半径近傍グラフは、各頂点から距離がある閾値 \(r\) 以内にある点を近傍として結ぶ方式である。距離の絶対値に基づくため、密度の高い領域では多くの辺が生まれ、疎な領域では結線が少なくなる傾向を持つ。

半径パラメータの決定

閾値 \(r\) の決め方は、グラフの密度と到達性を大きく左右する。小さい \(r\) は局所的であるが、離散点間の間隔が大きい場合には孤立点が増える。大きい \(r\) は連結性を確保しやすいが、異なる群の境界をまたぐ辺が増え、分離性が低下する。

決定は、距離分布の統計（例：近傍距離の分位点）、目的関数（予測精度や安定性）、あるいは計算制約（許容できる辺数）などの観点から行われることが多い。結果として、半径近傍はデータの密度ムラに敏感であり、密度補正や局所スケール化が検討される場合もある。

相互近傍グラフ

相互近傍グラフは、片方向の近さではなく「双方が互いを近いとみなす」条件を要求することで、ノイズや偶然の近さを抑える狙いがある。具体的には、片側で選ばれた関係を交差させて、相互に選ばれているペアだけを辺とする。

この方式は、グラフの誤結合を減らし、クラスタ境界の保持に寄与しうる。一方で、厳格化により辺数は減少し、連結性は弱まりやすい。そのため、対称化や閾値調整と合わせた設計が必要になることがある。

極近傍（nearest neighbor）系

極近傍系は、各点から見て距離が最小の相手、あるいは最近傍に基づく連鎖構造を利用する系列として扱われることが多い。最小距離という強い局所条件のため、安定性の面ではデータのノイズや重複、同距離の扱いに影響される。

性質と理論的性質

近傍グラフの性質は、生成規則と対象集合の幾何（距離、分布密度）に強く依存する。ここでは、基本的な統計的性質（次数分布）、構造的性質（連結性）、対称化の影響、そして距離空間上の整合性を整理する。

次数分布と疎密構造

無向グラフでは次数は辺の数に対応し、各頂点の近接性の「多寡」を反映する。k近傍では理想的には各頂点の選択数が制限されるため、次数の上限が比較的狭い範囲に収まることが多い。一方、半径近傍では局所密度の変化がそのまま次数のばらつきに反映されやすい。

重み付きの近傍設計では、次数だけでなく重みの総和（強度）が分布指標として扱われる。疎密の程度は、計算コストやスペクトル的性質（ラプラシアン固有値など）に影響するため、パラメータ選定は必然的に理論解析と密接になる。

連結性・成分数

連結性は、グラフがどれだけ分断されているかを示す。極端に小さい近傍条件は孤立点を生みやすく、反対に条件を緩めると成分数が減り、最終的に全体が結ばれる可能性がある。成分数の振る舞いは、近傍半径や \(k\) の増加とともに変化し、データの密度構造と絡み合う。

また、半径方式と \(k\) 方式は、連結性への寄与が異なる。半径では密度ムラにより局所的に断絶が残る場合があるのに対し、\(k\) は各点が一定数だけ選ばれるため、相対的な密度の低い領域でも過度に断片化しにくいことがある。ただし、異なる群が近接している場合には意図しないつながりが増えるため、別の意味での分断ではなく誤結合が問題となり得る。

対称化による影響

有向に定義された近傍関係を無向として扱うための対称化は、グラフの性質に直接影響する。典型的には「どちらか片側が近傍としたペアを採用する（論理和）」や「両側が近傍としたペアのみ採用する（論理積）」のようなルールがある。

論理和は辺数を増やしやすく、到達性や連結性を強める傾向がある。論理積は辺を絞り、誤結合を減らす方向に働きやすい。解析では、どちらの対称化を採用したかで、次数分布の形やクラスタ境界の解像度が変わるため、用途に応じた整合性が求められる。

距離空間上での性質

距離空間（メトリック空間）上で近傍グラフを構成する場合、距離の性質がグラフ構造に反映される。ここではメトリックと近傍の整合性、つまり「近いと定義した結果が距離構造の性質と整合するか」を中心に扱う。

メトリックと近傍の整合性

距離がメトリック（非負性、対称性、三角不等式など）を満たすと、近傍間の幾何的な整合性が得やすい。たとえば三角不等式が成り立つ状況では、近傍連鎖が距離の増大と矛盾しない形で進むため、探索や近似の性質が説明しやすくなることがある。

一方で、距離に類似した指標（対称性を満たさない、あるいは三角不等式が崩れる）を用いる場合、近傍グラフは純粋な幾何に基づく直観から外れ、反復探索が想定外の経路を通る可能性がある。このため、定義した指標がどの程度の幾何性を持つかを踏まえて、得られるグラフの意味づけを確認する必要がある。

応用分野と計算上の観点

近傍グラフは多分野で利用されるが、共通する要点は「局所関係を疎なグラフとして表し、計算と推論を現実的にする」ことである。ここでは計算幾何、機械学習、クラスタリング、そして計算量の管理としての高速化を概観する。

計算幾何・空間分割

計算幾何では、点群に対する近接性を利用して空間を分割する。近傍探索や最近傍の決定を効率化するために、近傍グラフの構築途中で空間インデックスや領域分割が活用されることがある。点の密度に応じて辺が増減するため、分割戦略も密度適応を意識する必要がある。

また、幾何学的な構造推定（例えば局所形状の推定）において、近傍集合は微分幾何的な近似や局所座標系の作成に使われる場合がある。近傍関係の定義の違いは、結果として推定のバイアスに直結する。

機械学習・データ解析

機械学習では、データ点の特徴空間における近さをグラフに変換し、その構造を学習や推論の途中で用いる。たとえば、近傍間で情報を伝播させる拡散過程、近傍集合に基づく集約、グラフ正則化による滑らかさの誘導などが代表的である。

さらに、距離や類似度の設計は学習対象の性質を左右する。生データに基づく距離だけでは不十分な場合、表現学習によって距離が改善されることがあり、その結果、近傍グラフのトポロジーが変化して性能に影響する。

クラスタリングとグラフ分割

クラスタリングでは、近傍グラフが「似た点が近く、異なる群の間には疎な結線がある」という仮定を支える。無向グラフに変換した後、連結成分の抽出や、切断を最小化するグラフ分割、スぺクトル手法などが利用される。

相互近傍のような厳格な結線は、誤ったつながりを減らす可能性があるが、成分の分割が細かくなりすぎる場合もある。半径や \(k\) の選択は、クラスタ数の推定や境界の滑らかさに反映されるため、評価指標に応じて調整される。

アルゴリズムと計算量

近傍グラフの計算では、全点対の距離計算を避けることが最重要の課題になる。データ数を \(n\) とすると、素朴に全探索を行えば計算量は大きくなりやすい。実際の用途では、近傍探索の計算量を抑え、生成された辺数が扱える範囲に収まるように設計する。

近傍探索の高速化（空間インデックス等）

高速化では、距離計算を削減するために空間インデックスを導入する。代表例として、木構造（ボール木、k-d木など）や格子、近似最近傍探索のための手法がある。これらは、ある点に近い候補だけを絞り込むことで探索を効率化する。

近似探索を採用すると厳密な近傍グラフからずれることがあるが、計算時間と精度のバランスを取れる利点がある。用途によって許容される近似誤差が異なるため、グラフの性質（連結性、次数分布、スペクトル的特徴）への影響を確認しながら速度向上を選択することが多い。