1 グラフ表現の概念
グラフ表現とは、データ中の「関係」を、集合要素（頂点）とその結びつき（辺）として抽象化し、計算可能な形に整理するための概念および技法群である。情報科学では、ネットワーク構造の抽出、関係性の可視化、検索・推論、経路探索、推薦など多様な処理の基盤として用いられる。
グラフは現実世界の対象を直接写すのではなく、目的に応じて対象のどの特徴を頂点・辺・属性として扱うかを決めることで成立する。したがって同一の観測データでも、密度の高さ、方向性の有無、強さ（強調度）の表し方、識別子の設計などの選択により表現が変化する。さらに、行列表現や埋め込み表現のように、元の構造を別の形式へ変換して計算や学習に適した形へ落とし込むことも、グラフ表現の重要な領域に含まれる。
1.1 グラフの基本要素
1.1.1 頂点（ノード）
頂点（ノード）は、データの「主体」や「状態」を表す要素である。文脈により、個体、地点、文書、機器、クラスタなどとして扱われる。頂点は識別子を持ち、必要に応じて属性（例：カテゴリ、時刻、数値特徴）を関連付けることで、単なる結節点ではなく情報を担う要素となる。
頂点集合の定義は設計上の要点である。たとえば観測ログから人を表す場合、粒度（ユーザ単位かセッション単位か）でグラフの性質が変わる。適切な粒度は、後段の可視化や推論の妥当性に直結する。
1.1.2 辺（リンク）
辺（リンク）は、頂点間の関係を示す要素である。関係の有無を示すだけの無重みな辺から、結びつきの強さを表す重み付きの辺まで幅がある。また関係が一方向である場合は有向辺として表現する。辺はしばしば時刻、回数、種類、確信度といった属性を伴い、関係の多様性を反映できる。
辺の生成は典型的にはルールとデータに基づく。たとえば同時発生、共通属性、距離閾値、参照関係などの条件で接続を定める。条件の取り方により、同じ対象でも構造が大きく変化するため、分析目的との整合が求められる。
1.2 グラフの種類
1.2.1 有向・無向
無向グラフは、辺が両方向に同等の意味を持つ場合に用いる。たとえば「共著がある」「同じ商品を同時に購入した」といった対称的な関係は無向として扱いやすい。
有向グラフは、関係の向きが意味を持つ場合に適する。参照（AがBを指す）、流量（送信元から送信先へ）、依存関係（部品Aが部品Bに依存する）のように、方向が因果や伝播の流れを表す場合は有向で表す。方向性の有無は、到達可能性や経路探索の結果に影響する。
1.2.2 重み付き・無重み
無重みグラフでは、辺の存在のみが情報となる。探索では単純なステップ数が距離として扱われることが多い。一方、重み付きグラフでは辺に数値（コスト、距離、頻度、確率など）が付与され、最適化や確率的推定が可能になる。
重み付きでは、重みの意味（足すべきか、比較すべきか、正規化が必要か）を明確にする必要がある。特に、複数のデータ源を統合する場合、尺度の整合性が分析結果の信頼性を左右する。
1.2.3 単純グラフ・多重グラフ
単純グラフは、同一の頂点対の間に辺が高々1本しか存在しない形である。関係の種類が複数あっても、合成して1本にまとめる設計が可能だが、情報が失われることもある。
多重グラフは、同一の頂点対間に複数の辺（例えば異なる関係タイプや回数の別ソース）を許容する。これにより、関係の多様性を保持したまま学習や集計へ進められる。ただし計算量や実装の複雑性は増しやすい。
1.3 属性とメタデータ
1.3.1 頂点属性
頂点属性は、頂点が持つ特徴量やラベルである。カテゴリ型（職種、ジャンル）、連続値（年齢、位置座標、スコア）、テキストのような複雑な情報まで含み得る。属性は、グラフ構造だけでは識別できない違いを与えるため、学習や分類の精度に寄与する。
頂点属性の扱いには前処理が関わる。欠損値の扱い、正規化、カテゴリのエンコード、スケール統一などを設計段階で決める必要がある。さらに、属性の更新頻度が高い場合は、動的グラフの考え方へ拡張される。
1.3.2 辺属性
辺属性は、関係の特徴を補足する情報である。たとえば通信ログなら送信回数、平均遅延、暗号化の有無、イベント種別などを辺に付与できる。多重関係を一つの辺に集約する場合にも、辺属性として区別情報を格納することで表現の劣化を抑えられる。
辺属性は、重みとして解釈される場合も、別の特徴量として用いられる場合もある。設計では、辺属性をどの計算に投入するか（距離計算、確率モデル、学習器への入力）を想定して定義することが重要になる。
2 表現形式（データ構造としてのグラフ）
2.1 隣接行列
隣接行列は、頂点数を \(n\) としたとき、\(n \times n\) の行列で辺の有無（または重み）を表す方式である。一般に、行と列が頂点を対応付け、要素が辺の存在や重みを表す。実装が単純で、行列演算による表現・計算が可能になる点が利点である。
2.1.1 行列の意味づけ
隣接行列の要素の解釈は、グラフの種類に従う。無向グラフなら対称行列になり、有向グラフなら非対称となる。重み付きでは要素に数値を格納し、無重みなら 0/1 などで表すことが多い。辺属性を単一の数値に圧縮できない場合は、別の行列（例：特定属性用の行列）を併用する。
行列の対角要素を自己ループとして扱うかどうかも設計事項である。自己参照が情報として意味を持つ場合は保持し、そうでなければ除外することでノイズを抑えることができる。
2.1.2 計算特性
隣接行列は参照が高速になりやすい一方、メモリ使用量は頂点数の二乗に比例する。疎なグラフでは大部分がゼロとなり、無駄が増えやすい。計算では行列積やべき乗を用いて到達可能性や経路数に関する推定が可能になる場合がある。
また、行列として統一されることで、線形代数ライブラリを活用できる。これによりベクトル化された処理がしやすくなる反面、データ更新のたびに行列を再構築する必要が出ることもある。
2.2 隣接リスト
隣接リストは、各頂点について接続先の集合（またはリスト）を保持する表現である。疎なグラフでメモリ効率が高く、特定の頂点から出る辺の列挙が比較的容易である。重みがある場合は、接続先と重みを対として格納する設計が一般的である。
2.2.1 疎グラフでの効率
隣接リストの計算量は、典型的に「頂点数 \(n\)」だけでなく「辺数 \(m\)」に依存する。疎な状況では \(m\) が小さいため、実用上の効率が良くなる。特に、大規模ネットワークやイベントの共起によるグラフのように、全頂点対の多くが未接続である場合に適する。
また、更新に対しても部分的な変更で済むことがある。辺追加や削除が頻繁に起こる用途では、行列よりも扱いやすい場合が多い。
2.2.2 走査（トラバース）の実装
走査では、ある頂点から連結な領域を順に辿る。隣接リストでは、取り出し対象となる辺だけを順番に処理できるため、探索処理の実装が自然になる。例えば幅優先探索ではキューを用い、深さ優先探索ではスタックまたは再帰で管理する。
実装面では重複辺の扱いや、訪問済み管理（再探索の抑制）が重要である。訪問管理が適切でないと無限ループや計算量の増大につながる。
2.3 エッジリスト
エッジリストは、辺を（始点、終点、必要なら重みや属性）という形で一覧として保持する方式である。行列やリストに比べ、データの入出力や変換処理と相性が良い。特に、ストリーミングで辺データを受け取る場合には素直な形式である。
2.3.1 集計・変換に向く場面
エッジリストは、フィルタリング（特定タイプの辺のみ抽出）、重みの付け替え、集約（例：同一頂点対の辺をまとめる）といった操作に向く。分析前処理で、複数ソースからの辺を統合する場合も管理しやすい。
また、並列処理や分散環境で扱う際に、辺単位で処理を分割できるため実装が容易になることがある。計算の中心が「辺ごとの演算」である場合に利点が出る。
2.3.2 データ入力の考え方
データ入力では、辺がどの単位で生成されるかを定義する。ログから作る場合、1行が「イベント1件」に対応するのか、「集計済みの関係」に対応するのかで、後段の重み意味が変わる。入力時点の粒度は、集計と正規化の設計に影響する。
さらに、頂点の番号付け（圧縮ID化）や、未知の頂点の扱い（動的追加の是非）も事前に決める必要がある。これらの選択は、再現性とデバッグ容易性に関わる。
2.4 転置・補助構造
2.4.1 転置グラフ
転置グラフは、有向グラフの全ての辺の向きを反転させたものとして定義される。始点と終点を入れ替えることで、逆方向の到達性や逆参照の解析に役立つ。強連結成分の分解など、アルゴリズムの段階によって転置が有効になることがある。
無向グラフでは転置しても同一となるため、適用は有向の場合に限り意味が明確になる。転置による情報変換は、計算の都合でグラフ構造を作り直す代替としても利用される。
2.4.2 学習・分析用インデックス
補助構造とは、主表現（行列、隣接リスト、エッジリスト）に加えて、検索や学習で必要となる情報を高速化するために用意する仕組みである。たとえば頂点ごとの入次数・出次数の事前計算、近傍取得のためのキャッシュ、特定属性に基づくクラスタ索引などが含まれる。
機械学習では、ミニバッチ生成やサンプリングの効率が重要である。近傍をランダムに引く際のデータ構造や、辺の順序を安定させるための設計が学習の再現性や速度に影響する。
3 視覚化としてのグラフ表現
3.1 レイアウト（配置）手法
レイアウト手法は、頂点を平面や空間上の点として配置し、辺を線として表す際の座標決定プロセスである。目的は見た目の美しさだけでなく、クラスタの分離、経路の理解、重要な頂点の視認性など、情報の読み取りを助けることにある。
3.1.1 力学ベースの配置
力学ベースでは、頂点を粒子として扱い、辺はばね、反発は電荷のようにモデル化して位置を調整する。ばねによる引力が結合をまとめ、反発が重なりを避けるため、自然なクラスタ構造が現れやすい。代表的には、エネルギー最小化に基づく手法が多い。
計算コストは頂点数に影響されやすい。近似（遠くの反発をまとめる）や停止条件の工夫によって現実的な速度にすることが多い。初期配置により局所解へ収束することもあるため、繰り返し実行の設計が重要になる。
3.1.2 経路・クラスタを意識した配置
経路やコミュニティを読み取りやすくするため、分割統治やコミュニティ検出に基づいて段階的に配置する方法がある。クラスタを先に求め、その中心を配置してから各クラスタ内の細部を調整することで、全体像を把握しやすくできる。
また、目的に応じて制約条件を加えることもある。例えば層構造（時系列、依存関係の階層）を持つデータでは、頂点を段に配置することで理解が進む場合がある。こうした制約は、アルゴリズムの選択に直結する。
3.2 可読性の設計
可読性は、視覚要素の設計によって大きく左右される。頂点と辺の情報量が増えると、重なりや区別の困難さが発生するため、情報の階層化と強調の設計が求められる。
3.2.1 頂点サイズ・色・ラベル
頂点サイズは重要度（中心性やスコア）と連動させることで、注目対象を直感的に示せる。色はカテゴリ分類やグループ所属の表現に適し、ラベルは特定条件でのみ表示することで情報過多を避けられる。
ラベルは常時表示すると視認性を損ねやすい。閾値により重要なものだけ表示する、ズームに応じて出し分けるなどの工夫が一般的である。色覚多様性への配慮（識別しやすい配色の選択）も設計要件として重要になる。
3.2.2 辺の強調と見分け
辺の強調は、重みや関係のタイプに応じて線の太さ、透明度、色、線種を変えることで実現できる。強い関係や特定のパターンを見せたい場合は、弱い辺を薄くする、または非表示にする設計が有効である。
矢印の表示（有向の場合）や、重なりを軽減するためのカーブ配置なども読み取りに影響する。辺が多すぎる場合は、上位の関係のみ描画する「間引き」が理解を助ける。
3.3 インタラクション
3.3.1 拡大縮小・フィルタリング
インタラクティブ表示では、ズームにより局所の構造を詳細に確認できる。ズームレベルに応じて表示密度を変えることで、全体を見ながら局所へ掘り下げる動線が作れる。
フィルタリングでは、頂点属性や辺属性、重み閾値、距離範囲などの条件で表示対象を絞る。これにより「ノイズの多いグラフ」を目的に沿った部分集合として提示できる。動的な更新は利用者の認知負荷を下げる。
3.3.2 選択と詳細表示
選択は、特定の頂点や辺をユーザが指定したときに、関連情報を表示する仕組みである。クリックやホバーにより、属性値、説明文、周辺接続、履歴などの詳細へ遷移できる。
詳細表示では、関連する近傍を小さなサブグラフとして提示したり、時間推移や遷移確率のような二次情報を併せて表示したりする。重要なのは、全表示に頼らず必要な情報だけを段階的に見せることである。
4 計算・学習におけるグラフ表現
4.1 距離・中心性・構造指標
距離・中心性・構造指標は、グラフ上の位置づけや影響度を数値化するための手掛かりである。これらは可視化の補助としても、学習の入力特徴としても利用される。
4.1.1 最短経路に基づく指標
最短経路は、辺の重みをコストとして扱った場合に、到達に必要な最小値を求める概念である。これを基礎に、平均経路長、距離分布、到達可能性の広がりなどを特徴化できる。
中心性の一部も最短経路に基づく。たとえば特定の頂点が他頂点間の経路上にどれだけ頻出するかを評価する指標は、重要な中継役の検出に用いられることがある。計算には全点対探索が重くなる場合があり、近似や部分探索の工夫が必要になる。
4.1.2 中心性と重要度
中心性は、グラフ内での「重要さ」を捉えるための複数の尺度を含む。次数中心性のように局所情報だけで決まるものから、全体構造を反映する尺度まである。重要度の定義は用途依存であり、拡散の起点を探すのか、ボトルネックを探すのかで適切な指標は変わる。
また、中心性値の比較にはスケールへの注意が要る。頂点数の変化、重みの解釈、自己ループや多重辺の扱いにより値の分布が変わるため、同一条件での比較が望ましい。
4.2 埋め込み表現
4.2.1 次元削減としての考え方
埋め込み表現は、グラフ要素（頂点や辺、全体）を低次元の連続ベクトルに変換する考え方である。これにより、類似性計算や機械学習への入力が容易になる。次元削減としての側面があり、構造情報を失いすぎない範囲で圧縮することが目標となる。
埋め込みの品質は、保存される性質（近傍関係、距離、コミュニティ構造など）に依存する。目的に合わせて、学習損失やサンプリング戦略を設計する必要がある。
4.2.2 グラフ埋め込みの用途
埋め込みは、ノード分類やクラスタリング、類似検索、推薦、異常スコアの計算などに利用される。類似検索では、ベクトル間距離を用いて近いノードや辺を見つけることで、関係グラフの探索を高速化できる。
また、埋め込みを経由することで、グラフ構造に対する推論を標準的な分類器・回帰器に接続できる。さらに、埋め込みの学習により、属性と構造の両方を統合した特徴を得られる場合がある。
4.3 分類・回帰への適用
4.3.1 ノード予測
ノード予測は、特定の頂点に対するラベル推定や値予測を行う課題である。入力には、頂点属性に加えて近傍構造の情報を用いる設計が多い。学習器は、局所近傍の集約を通じて、遠い情報も間接的に反映するように構築される。
訓練・評価の分割では、情報漏洩を避けるための注意が必要である。特にリンク予測に近い形で学習するときは、切り離し方や負例生成の設計が結果に影響する。
4.3.2 エッジ予測
エッジ予測は、頂点対間に関係が成立するか、または関係の強さを推定する課題である。リンクの存在を分類問題として扱う方法と、重みを回帰として扱う方法がある。
特徴設計では、頂点埋め込みの組み合わせ（差分、内積、連結など）を用いることが多い。多重辺や方向性がある場合は、対象の種類を明確化し、出力もそれに対応させる必要がある。
4.3.3 グラフ全体の予測
グラフ全体の予測は、グラフを単位としてラベルや値を推定する課題である。たとえば各サンプルが独立したグラフであり、その全体的な性質を予測する場合に該当する。実装では、ノード表現を集約してグラフ表現へ変換する「読み出し」操作が中心になる。
この集約は平均や最大など単純なものから、注意機構による重み付けまで幅がある。どの情報を集めるかが性能を左右するため、ラベルの意味と整合させた設計が重要になる。
5 グラフ表現の実務的設計
5.1 モデル選択の基準
実務では、表現とモデルをセットで考える必要がある。同じグラフでも、可視化中心か、検索中心か、学習中心かで最適な形式が変わるためである。
5.1.1 データの性質（密度・規模）
密度は表現選択に強く影響する。疎なら隣接リストやエッジリストが有利になりやすく、密なら隣接行列が簡潔になることがある。規模が大きいと、メモリ量や計算時間の制約が設計を支配する。
さらに、更新頻度や欠損の多寡も重要である。リアルタイムに辺が増える場合は、行列の再計算がボトルネックになり得るため、更新しやすい表現を優先する判断が必要になる。
5.1.2 目的（可視化・分析・学習）
可視化では、描画の速度、重なりの管理、ユーザ操作との連携が主眼となる。分析では、指標計算や検索を効率化する表現が求められる。学習では、ミニバッチ生成や勾配計算に適したデータ形式が必要になる。
目的に応じて、どの表現（構造そのもの、行列化、埋め込み）がボトルネックになっているかを切り分ける。例えば可視化のために埋め込みを事前計算するなど、複数表現を併用する設計も一般的である。
5.2 前処理と正規化
5.2.1 欠損・重複の扱い
欠損は、頂点属性や辺属性の不足、または関係の観測漏れとして現れる。属性欠損は補完やマスクで扱い、関係欠損は負例生成の際に注意が必要になる。負例が「本当に無関係」か「未観測」かで意味が変わるためである。
重複は、多重辺の扱い方に直結する。入力がイベント単位で重複が多いなら集約して重みに変換するか、関係種別ごとに分離するなどの選択がある。重複をそのまま残すと過学習や過大な重み付けにつながる場合もある。
5.2.2 重みのスケーリング
重み付きグラフでは、重みの分布が偏ると学習が不安定になり得る。正規化（例：対数変換、上限クリッピング、確率化）によってスケールを整えることで、勾配の極端な発散を抑えることが期待できる。
また、重みが「コスト」なのか「類似度」なのかでも処理は変わる。距離として扱うなら最短経路で整合する変換が必要であり、確率として扱うなら和が1になる規約などを考慮する必要がある。重みの意味を文書化し、全工程で一貫させることが望ましい。
5.3 スケーラビリティ
5.3.1 分割・バッチ処理
スケールの大きいグラフでは、全体を一度に処理するのが難しい。そこでサブグラフに分割し、バッチ単位で処理する戦略が採用される。近傍サンプリングやクラスタ分解を利用して、局所的に学習できるよう設計する場合がある。
分割に伴う境界効果も考慮が必要である。学習対象の近傍が切れて情報が欠落すると性能低下につながるため、サンプリング範囲や境界の扱いを調整する。
5.3.2 計算資源の見積もり
計算資源の見積もりは、表現とモデルの選択に直結する。メモリ使用量は頂点数、辺数、属性次元に依存し、計算時間は探索回数や畳み込み・集約の回数に依存する。事前に推定し、バッチサイズや埋め込み次元の上限を決めることで破綻を防げる。
特に、隣接行列は二乗サイズになりやすいため大規模で危険になり得る。一方、隣接リストやエッジリストは辺数に比例しやすいが、サンプリングやバッチ化の設計が必要になる。制約に応じて表現を切り替える判断が実務上の要になる。
6 代表的な応用分野（非争点領域）
6.1 ソーシャルネットワーク分析（一般的手法）
ソーシャルネットワーク分析では、個人や組織を頂点、相互関係を辺として扱い、構造の特徴を定量化する。中心性やコミュニティ検出、影響の波及範囲の推定などが一般的な目的として挙げられる。
また、推薦や情報拡散のモデリングにもグラフ表現が応用される。ユーザの履歴を関係グラフとして構築し、近傍の傾向から候補を絞ることで、探索空間を縮小できる。評価指標は精度だけでなく、ユーザ体験や計算コストも含めて設計する。
6.2 物流・経路探索（最適化の考え方）
物流や経路探索では、地点を頂点、移動や輸送の可能性を辺としてモデル化し、コスト最小化や制約条件の満足を目指す。距離、時間、燃料、料金などの重みが辺に付与されることが多い。
ルート計画では、最短経路探索に加え、交通状況の更新や車両容量のような制約を組み込む必要がある。グラフ表現はこれらの制約を「重み」「可用性」「追加属性」として取り込むための共通基盤となる。結果として、計画の比較や改善サイクルを回しやすくする効果がある。
6.3 情報検索と推薦（関係グラフの活用）
情報検索では、文書やクエリに相当する対象を頂点として、類似や参照関係を辺で表すことで探索を補助する。多段の関連（近傍）を辿ることで、クエリに近い候補を効率よく見つけられる可能性がある。
推薦では、ユーザとアイテムの関係を二部グラフとして扱うことが多い。履歴から形成された接続を用いて、協調フィルタリング的な近傍探索や、埋め込みによる類似度計算を行う。異なる信号（内容、行動、属性）を統合する際にも、グラフの属性として表現できる。
6.4 異常検知（構造の逸脱）
異常検知では、通常時の構造から外れたパターンを見つけることが狙いとなる。グラフ表現は、統計的な逸脱や接続の不自然さを捉えるための枠組みを提供する。
具体的には、中心性や距離の分布の変化、サブグラフの出現頻度の低下、高頻度接続の局所的な崩れなどを特徴量化する。さらに、埋め込みの距離や予測誤差を用いて、周辺との整合性が低いノードや辺を異常候補として抽出できる。現場では、誤検知率と見逃し率のバランスに合わせて閾値調整と評価設計を行う。