Twitter のフォロー関係、Google のページランク、道路の交差点と道、有機分子の原子と結合、神経細胞のシナプス結合——一見まったく異なるこれらの対象は、すべて「点と点をつなぐ線」、すなわちグラフとして同じ枠組みでモデル化できます。グラフはデータ構造の中でも特に応用範囲が広く、SNS の友達推薦から配車アプリの最短経路計算、創薬におけるタンパク質相互作用解析、深層学習の Graph Neural Network まで、現代の情報技術のあらゆる層に染み込んでいます。
ところがグラフを計算機で扱おうとした瞬間、ひとつの素朴な問いが立ちはだかります。「絵に描いた丸と矢印を、どうやって数値の世界に翻訳するのか」。この問いに対する最も基本かつ強力な答えが、隣接行列 (adjacency matrix) です。$n$ 個の頂点を持つグラフを $n \times n$ の正方行列にぴったり閉じ込めることで、グラフの「構造」を線形代数の道具で操れるようになります。経路の数え上げは行列のべき乗、グループ分けは固有値分解、深層学習への組み込みはテンソル演算——すべてがこの 1 枚の行列を起点に展開します。
この記事では、隣接行列の最も基本的な定義から出発し、有向・無向・重み付きグラフでの違い、$A^k$ で $k$-step パス数が数えられる仕組み、ラプラシアン行列 $L = D – A$ とスペクトルグラフ理論、そして Graph Convolutional Network (GCN) や Graph Attention Network (GAT) といったグラフ深層学習までを一気通貫で解説します。NetworkX と scipy.sparse を使った Python 実装を随所に挟みつつ、「隣接行列の固有値が何を語るのか」「なぜ GCN は隣接行列の正規化を必要とするのか」という疑問にも踏み込みます。
本記事の内容
- グラフ・頂点・辺の基本用語と、有向・無向・重み付きの違い
- 隣接行列の定義、対称性、トレース、出次数・入次数との関係
- 行列のべき乗 $A^k$ が表す「$k$-step パスの数」とウォーク・閉路の数え上げ
- 次数行列 $D$ から導かれるラプラシアン行列 $L = D – A$ とその意味
- スペクトルグラフ理論の入り口 — 固有値とグラフの連結成分、フィードラーベクトル
- Graph Neural Network (GCN, GAT) における隣接行列の役割
- NetworkX, scipy.sparse, NumPy による実装と固有値計算
- 簡易な GCN レイヤを NumPy だけで実装し、隣接行列がどう作用するかを観察
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- 正方行列とは — 定義・性質・対称/直交/三角行列を具体例で完全解説
- スパース行列（疎行列）とは？わかりやすく解説して実装する
- 【Python】固有値と固有ベクトルの幾何学的特徴を可視化して理解する
- 【徹底解説】NetworkX の利用方法や可視化の方法をわかりやすく
グラフを行列で表現する直感
まずは「なぜ行列で表すのか」という素朴な疑問から始めましょう。グラフは紙の上では「丸と線」で気軽に描けますが、計算機の内部では「どの頂点とどの頂点がつながっているか」を何らかの形で記憶しなければなりません。可能な表現方法はいくつかあります。
- 辺リスト (edge list): $(0, 1), (1, 2), (2, 3), \dots$ のような「頂点ペアの集まり」を並べる
- 隣接リスト (adjacency list): 各頂点について「その頂点から辺が伸びている先の頂点」をリストで持つ
- 隣接行列 (adjacency matrix): $n \times n$ の行列の $(i, j)$ 成分に「頂点 $i$ から頂点 $j$ への辺の有無」を書き込む
辺リストは最も省メモリですが、「頂点 5 と頂点 7 はつながっているか？」と尋ねるたびに全リストを走査する必要があります。隣接リストは中庸の選択肢で、実装が単純な一方、行列演算の恩恵を受けられません。これに対して隣接行列は、メモリこそ $n^2$ を消費するものの、グラフ構造の問いを線形代数の問いに翻訳できるという決定的な利点を持ちます。
たとえば「頂点 $i$ から $j$ への 2 ステップの経路はいくつあるか」という問いは、隣接行列のべき乗 $(A^2)_{ij}$ を計算するだけで答えが出ます。これは行列演算の組み合わせ論的意味そのものであり、後ほど詳しく見ます。あるいは、グラフの「グループ分け」を考えたいとき、ラプラシアン行列の固有ベクトルが自動的にクラスタを浮かび上がらせてくれます——これがスペクトルクラスタリングの正体です。さらに、近年急速に発展しているグラフ深層学習 (Graph Neural Network) では、隣接行列とノード特徴量の積 $AX$ が「近傍からの情報集約」を意味する基本演算となっています。
つまり、隣接行列はグラフを線形代数の世界に持ち込むためのパスポートなのです。ここから先のあらゆる議論は、この行列をどう操るかに帰着します。それでは、肝心の定義に進みましょう。
グラフの基本用語をおさらい
定義に入る前に、用語を簡潔に整理しておきます。グラフ $G$ は、頂点 (vertex, node) の集合 $V$ と辺 (edge) の集合 $E$ の組として
$$ G = (V, E) $$
と書きます。たとえば $V = \{A, B, C, D, E, F\}$ で $E = \{(A,B), (B,C), (C,D), \dots\}$ のように具体化されます。頂点の数 $|V| = n$、辺の数 $|E| = m$ をそれぞれ「次数 (order)」「サイズ (size)」と呼ぶこともあります。
辺の性質に応じて、グラフはいくつかの種類に分かれます。
- 無向グラフ (undirected graph): 辺に向きがない。Facebook の友達関係のように「A と B がつながっている」事実だけが意味を持つ
- 有向グラフ (directed graph, digraph): 辺に向きがある。Twitter のフォロー関係のように「A → B」と「B → A」を区別する
- 重み付きグラフ (weighted graph): 各辺に実数値の重みが付く。道路網の距離、通信路の容量、相関の強さなど
二つの頂点 $u, v$ が辺で結ばれているとき、これらは互いに隣接 (adjacent) していると言います。頂点 $v$ に接続する辺の本数を $v$ の次数 (degree) と呼び、$\deg(v)$ と書きます。有向グラフでは、$v$ から出ていく辺の数を出次数 (out-degree) $\deg^{+}(v)$、入ってくる辺の数を入次数 (in-degree) $\deg^{-}(v)$ と区別します。
これだけの用語装備があれば、隣接行列の定義に進めます。
隣接行列の定義
無向グラフの場合
頂点を $v_0, v_1, \dots, v_{n-1}$ と番号付けます。隣接行列 $\bm{A} \in \mathbb{R}^{n \times n}$ の $(i, j)$ 成分を
$$ A_{ij} = \begin{cases} 1 & (v_i, v_j) \in E \\ 0 & (v_i, v_j) \notin E \end{cases} $$
と定義します。つまり「頂点 $i$ と頂点 $j$ の間に辺があれば $1$、なければ $0$」というだけの素朴な行列です。無向グラフでは「$i$ と $j$ がつながっている」=「$j$ と $i$ がつながっている」が同値なので、
$$ A_{ij} = A_{ji} \quad \Longleftrightarrow \quad \bm{A} = \bm{A}^{\top} $$
が成り立ちます。つまり無向グラフの隣接行列は対称行列です。対称性のおかげで、固有値はすべて実数になり、固有ベクトルは互いに直交します。この性質は後で見るスペクトルグラフ理論で本質的な役割を果たします。
有向グラフの場合
有向グラフでは辺 $(v_i, v_j)$ と $(v_j, v_i)$ を区別するため、
$$ A_{ij} = \begin{cases} 1 & v_i \to v_j \in E \\ 0 & v_i \to v_j \notin E \end{cases} $$
となります。これは一般に $A_{ij} \neq A_{ji}$ で、隣接行列は対称ではありません。慣習として「行が始点、列が終点」とすることが多いですが、文献によっては逆もあり得るので、コードや論文を読むときは要注意です。本記事では「行 → 列」の方向を採用します。
ここで、有向グラフ独特の次数の取り扱いを確認しておきましょう。
$$ \deg^{+}(v_i) = \sum_{j} A_{ij} \quad (\text{出次数} = 行和) $$
$$ \deg^{-}(v_j) = \sum_{i} A_{ij} \quad (\text{入次数} = 列和) $$
つまり行を足せば出次数、列を足せば入次数が得られます。すべての出次数の和と入次数の和は当然どちらも辺の総数に等しく、$\sum_{ij} A_{ij} = m$ となります。
重み付きグラフの場合
辺 $(v_i, v_j)$ に重み $w_{ij}$ が付いているなら、隣接行列の成分をその重みそのものにします。
$$ A_{ij} = \begin{cases} w_{ij} & (v_i, v_j) \in E \\ 0 & (v_i, v_j) \notin E \end{cases} $$
たとえば道路網であれば $w_{ij}$ は「頂点 $i$ と $j$ の間の距離」、ニューラルネットワークなら「シナプスの結合強度」、相関ネットワークなら「相関係数」といった具合です。重み付きの場合は二値ではなく実数値で構造を表現するため、より豊かなモデル化が可能になります。
自己ループと多重辺
頂点が自分自身に辺を持つ場合(自己ループ)、$A_{ii} = 1$(または重み)と書きます。慣習として、無向グラフの自己ループは「2 本分」として扱う($A_{ii} = 2$ と置く)流儀もあるので、データセットの規約は事前に確認するのが安全です。二つの頂点間に複数本の辺が許される多重グラフ (multigraph) では、$A_{ij}$ にその本数を書き込みます。
疎行列としての隣接行列
実世界のグラフは「頂点数の割に辺がスカスカ」という性質を持つことがほとんどです。Facebook の月間アクティブユーザーが約 30 億人、その全員が全員とつながっているわけではなく、平均的な友達数はせいぜい数百です。したがって、隣接行列の成分のほぼすべてが $0$ になります。このような行列をスパース行列 (sparse matrix) と呼び、CSR (Compressed Sparse Row)、CSC (Compressed Sparse Column)、COO (Coordinate) などの形式で「非ゼロ成分とその位置」だけを記録します。詳しくはスパース行列の解説記事を参照してください。
scipy.sparse モジュールは、こうしたスパース表現上で行列積や固有値計算を効率よく実行できるツールを提供しており、グラフが大規模になるほど不可欠な道具になります。本記事の Python 実装でも、後半でスパース表現に切り替えます。
ここまでで「グラフ → 行列」の翻訳ルールが整いました。次は、この行列の演算がグラフのどんな性質を引き出してくれるのかを見ていきます。
行列演算でグラフ性質を取り出す
行列のべき乗 $A^k$ と $k$-step パス
隣接行列の最も美しい性質の一つは、$A^k$ の $(i, j)$ 成分が、頂点 $i$ から頂点 $j$ への長さ $k$ のウォーク(歩道)の本数を表すことです。ここで「ウォーク」とは、同じ頂点や辺を何度通っても良い経路のことです。たとえば $i \to j \to i \to j$ も長さ 3 のウォークとして数えます。
なぜそうなるかは、行列積の定義をなぞるだけで分かります。$A^2$ の $(i, j)$ 成分は
$$ (A^2)_{ij} = \sum_{k=0}^{n-1} A_{ik} A_{kj} $$
です。$A_{ik}$ は「$i$ から $k$ への辺の有無」、$A_{kj}$ は「$k$ から $j$ への辺の有無」を表します。両方が $1$ になるのは「$i \to k \to j$ という長さ 2 の経路が存在する」場合に限られます。そして $k$ について和を取るので、中継地点を全通り尽くしてカウントしていることになります。つまり $(A^2)_{ij}$ は「$i$ から $j$ への 2-step ウォークの数」そのものです。
帰納法的に拡張すれば、$(A^k)_{ij}$ が「$i$ から $j$ への $k$-step ウォーク数」を与えることが分かります。この単純な事実が、PageRank、感染症シミュレーション、レコメンデーションシステムなど、極めて広い応用の基盤になっています。
トレースと閉路の数え上げ
$\bm{A}$ のトレース $\mathrm{tr}(A) = \sum_i A_{ii}$ は、自己ループの本数(無向では 2 倍)を表します。さらに $A^2$ のトレース $\mathrm{tr}(A^2) = \sum_i (A^2)_{ii}$ は「$i$ から出て 2 ステップで $i$ に戻る経路の数」の総和です。無向グラフでこれは「各辺を 2 方向に数えた本数の 2 倍」、つまり $2m$($m$ は辺数)に一致します。
一般化して、$\mathrm{tr}(A^k)$ は「長さ $k$ の閉ウォークの総数」を与えます。三角形(長さ 3 の閉路)の個数 $\Delta$ は
$$ \Delta = \frac{1}{6}\,\mathrm{tr}(A^3) $$
で計算できます($6 = 3! / 1$ は、各三角形を回り方と始点で 6 通りに数え重複するため)。これは社会ネットワーク分析で「クラスタリング係数」を計算するときの基本公式です。「友達の友達は友達になりやすいか」を定量化する指標は、こうして隣接行列のべき乗から自然に出てきます。
次数ベクトルと次数行列 $D$
無向グラフでは、頂点 $v_i$ の次数は
$$ \deg(v_i) = \sum_{j} A_{ij} = (A\bm{1})_i $$
と書けます。ここで $\bm{1} = (1, 1, \dots, 1)^{\top}$ は全成分が $1$ のベクトルです。つまり「隣接行列に全 1 ベクトルをかける = 次数ベクトル」が得られます。
この次数を対角に並べた行列を次数行列 (degree matrix) $\bm{D}$ と呼びます。
$$ D_{ij} = \begin{cases} \deg(v_i) & i = j \\ 0 & i \neq j \end{cases} $$
次数行列は対角行列なので、逆行列やべき乗が要素ごとに簡単に計算できます。後ほど登場する正規化隣接行列 $D^{-1/2} A D^{-1/2}$ や、ラプラシアン行列 $L = D – A$ の構成要素として、次数行列は中心的な役割を担います。
ここまでで隣接行列単体の代数的性質を見てきました。次は、隣接行列と次数行列を組み合わせて作られるラプラシアン行列に進みます。これがスペクトルグラフ理論の主役です。
ラプラシアン行列 $L = D – A$
定義と直感
無向グラフのグラフラプラシアン (graph Laplacian) は、次数行列 $\bm{D}$ と隣接行列 $\bm{A}$ の差として定義されます。
$$ \bm{L} = \bm{D} – \bm{A} $$
成分で書くと、
$$ L_{ij} = \begin{cases} \deg(v_i) & i = j \\ -1 & i \neq j,\ (v_i, v_j) \in E \\ 0 & \text{それ以外} \end{cases} $$
対角に「自分の次数」、非対角に「辺があれば $-1$、なければ $0$」が並ぶ行列です。一見ただの定義ですが、これは連続空間におけるラプラシアン演算子 $\nabla^2$ のグラフ版に対応しています。詳しくはグラフラプラシアンの解説記事を参照してください。
なぜ $D – A$ が「グラフ上の二階微分」になるのか、直感的に確認しましょう。連続空間でのラプラシアンは、点 $x$ における関数値とその周辺の平均値の差を測ります。グラフ上で同じことをやるなら、頂点 $v_i$ における関数値 $f(v_i)$ と、その近傍の関数値の和との差
$$ (Lf)_i = \deg(v_i) f(v_i) – \sum_{j: (v_i, v_j) \in E} f(v_j) $$
を考えるのが自然です。これはまさに $L = D – A$ をベクトル $f$ に適用した結果になっています。
正規化ラプラシアン
次数のばらつきが大きいグラフでは、生の $L$ より正規化ラプラシアンを使う方が解析しやすいことがあります。代表的なのは対称正規化ラプラシアン
$$ \bm{L}_{\mathrm{sym}} = \bm{D}^{-1/2} \bm{L} \bm{D}^{-1/2} = \bm{I} – \bm{D}^{-1/2} \bm{A} \bm{D}^{-1/2} $$
と、ランダムウォーク正規化ラプラシアン
$$ \bm{L}_{\mathrm{rw}} = \bm{D}^{-1} \bm{L} = \bm{I} – \bm{D}^{-1} \bm{A} $$
です。前者は対称性を保ち固有値解析に向き、後者はランダムウォーク(マルコフ連鎖)としての解釈と相性が良い。GCN(後述)では対称正規化に微修正を加えた $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ が使われます。
ラプラシアンの基本性質
ラプラシアン行列には、次のような際立った性質があります。
- 対称半正定値: $\bm{L} = \bm{L}^{\top}$ かつすべての固有値 $\lambda_i \geq 0$
- 最小固有値はゼロ: $\bm{L}\bm{1} = \bm{0}$、つまり全 1 ベクトル $\bm{1}$ が固有値 $0$ の固有ベクトル
- 固有値 $0$ の重複度 = 連結成分の数: グラフが $k$ 個の連結成分に分かれるとき、$\lambda = 0$ の固有ベクトルは $k$ 次元の空間を張る
特に 3 つ目は劇的な性質です。グラフの連結性という離散的な情報が、行列の固有値という連続的な指標で取り出せる——この事実こそがスペクトルグラフ理論の出発点です。
なぜ $\bm{L}\bm{1} = \bm{0}$ なのかは簡単に確認できます。$(L\bm{1})_i = \sum_j L_{ij} = D_{ii} – \sum_{j} A_{ij} = \deg(v_i) – \deg(v_i) = 0$ となるためです。直感的にも「すべての頂点で同じ値を取る関数(=定数関数)はラプラシアンを取ると消える」のはもっともです。連続空間でも定数関数の二階微分はゼロですから、グラフ上でも同じ振る舞いをしているわけです。
ラプラシアンの固有値・固有ベクトルがどれほど情報量を持っているか、次のセクションでより詳しく見ていきましょう。
スペクトルグラフ理論 — 固有値からグラフを読む
スペクトルとは
行列 $\bm{A}$ や $\bm{L}$ の固有値の集合を、その行列のスペクトルと呼びます。「グラフを行列で表したものの固有値を見れば、グラフ自体の構造が読める」という思想を体系化した分野がスペクトルグラフ理論 (spectral graph theory) です。
具体的には、ラプラシアン行列 $\bm{L}$ の固有値を小さい順に $0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$ と並べたとき、
- $\lambda_2$(第 2 小固有値) は代数的連結度 (algebraic connectivity) と呼ばれ、グラフがどれだけ「強くつながっているか」を測る
- $\lambda_2 = 0$ はグラフが非連結であることを意味する
- $\lambda_2$ に対応する固有ベクトルはフィードラーベクトル (Fiedler vector) と呼ばれ、グラフを 2 つに分割するスペクトラルカットの基礎になる
フィードラーベクトルによるグラフ分割
フィードラーベクトル $\bm{v}_2$ は、各頂点に実数値を割り当てるベクトルです。この値の符号で頂点を 2 グループに分けると、「辺をなるべく切らないように」自然にグラフを 2 分割できることが知られています。これはスペクトルクラスタリングの最も単純な形であり、画像セグメンテーション、コミュニティ検出、回路レイアウトなど多岐にわたる応用を持ちます。
なぜフィードラーベクトルが「自然な分割」を与えるのか、簡単な直感を述べておきます。ラプラシアンの二次形式
$$ \bm{x}^{\top} \bm{L} \bm{x} = \frac{1}{2} \sum_{(i, j) \in E} (x_i – x_j)^2 $$
は、ベクトル $\bm{x}$ を「頂点に割り振った値」と見たときの隣接頂点間の値の差の二乗和を表します。これを最小化するベクトルが、$\bm{1}$(自明解、すべての頂点で同じ値)に直交するという条件下では $\bm{v}_2$ になります。つまりフィードラーベクトルは「定数からの最小限のずれで頂点を区別する関数」であり、その符号でグラフを切れば、辺をまたぐ切断が最小限になるのです。
この二次形式の式自体、直接展開すれば確認できます。
$$ \bm{x}^{\top} L \bm{x} = \sum_{i} D_{ii} x_i^2 – \sum_{i,j} A_{ij} x_i x_j = \sum_{i} \deg(v_i) x_i^2 – \sum_{(i,j) \in E} 2 x_i x_j $$
ここで $\deg(v_i) = \sum_{j: (i,j)\in E} 1$ を使って $\sum_i \deg(v_i) x_i^2$ を辺ごとに展開すると、各辺 $(i, j)$ から $x_i^2 + x_j^2$ が現れます。これと交差項を合わせると $x_i^2 – 2x_i x_j + x_j^2 = (x_i – x_j)^2$ となり、最終的に上の二次形式が得られます。
隣接行列自身のスペクトル
隣接行列 $\bm{A}$ のスペクトルもまた豊かな情報を持っています。重要な事実をいくつか挙げると、
- 最大固有値 $\lambda_{\max}(A)$ は平均次数と最大次数の間に挟まれる: $\bar{d} \leq \lambda_{\max} \leq d_{\max}$
- 最大固有値に対応する固有ベクトルの成分は「中心性 (eigenvector centrality)」の指標になり、PageRank の原型を成す
- 隣接行列が 0 固有値を持つかどうかはグラフの構造に関係し、二部グラフでは固有値が $\pm$ に対称に並ぶ
特に固有ベクトル中心性は「自分の重要度は、つながっている相手の重要度の和に比例する」という定義から導かれます。これは $A\bm{v} = \lambda \bm{v}$ の方程式そのものであり、ペロン・フロベニウスの定理が「正の隣接行列に対しては最大固有値が単純で、対応する固有ベクトルの成分がすべて正である」ことを保証します。中心性指標は Google の PageRank へと発展し、現代の検索エンジンの根幹技術となりました。
ここまで、隣接行列とラプラシアンの理論的側面を深掘りしてきました。次は、これらの行列を活用した近年最大のホットトピック——グラフニューラルネットワークに進みます。
Graph Neural Network (GCN, GAT) への応用
グラフ深層学習の必要性
画像は格子状のピクセル、自然言語は系列としての単語列——どちらも「規則正しい構造」を持つため、CNN や RNN が驚異的な成果を挙げてきました。しかし、ソーシャルネット、分子、知識グラフのような「不規則な構造」を持つデータに対しては、CNN や RNN を直接適用できません。
そこで登場したのが、Graph Neural Network (GNN) です。GNN は「隣接頂点の特徴を集約してから非線形変換する」という単純なアイデアを軸に、グラフ構造そのものを深層学習の文脈に持ち込みました。詳しくはGNN の解説記事も参照してください。
GCN の基本形
最も基礎的な GNN モデルである Graph Convolutional Network (GCN) のレイヤは、次の単純な式で表されます。
$$ \bm{H}^{(l+1)} = \sigma\!\left( \tilde{\bm{D}}^{-1/2}\, \tilde{\bm{A}}\, \tilde{\bm{D}}^{-1/2}\, \bm{H}^{(l)}\, \bm{W}^{(l)} \right) $$
ここで
- $\bm{H}^{(l)} \in \mathbb{R}^{n \times d_l}$: 第 $l$ 層の各頂点の特徴ベクトル(行が頂点、列が特徴次元)
- $\tilde{\bm{A}} = \bm{A} + \bm{I}$: 自己ループを加えた隣接行列(自分自身の情報も集約に含める)
- $\tilde{\bm{D}}$: $\tilde{\bm{A}}$ の次数行列
- $\bm{W}^{(l)}$: 学習可能な重み行列
- $\sigma$: 活性化関数(ReLU など)
数式が長く見えますが、本質は「隣接行列で近傍から特徴を平均し、線形変換と非線形変換を施す」というだけです。隣接行列 $\bm{A}$ そのものを使うと次数の大きい頂点の影響が過剰になるため、$\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ でスケールを正規化します。これがラプラシアンと結びついていることに注目してください。実は
$$ \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} = \bm{I} – \tilde{L}_{\mathrm{sym}} $$
なので、GCN は「対称正規化ラプラシアンの 1 次近似」を畳み込みカーネルとして使っているとも解釈できます。詳しい導出と実装はGCN の解説記事に譲ります。
GAT — Attention でエッジ重みを学習する
GCN は「すべての近傍を平等に集約する」モデルでしたが、現実には「重要な近傍とそうでない近傍」を区別したいことが多々あります。Graph Attention Network (GAT) は、近傍ごとの集約重みを Attention 機構で学習することで、この問題に対処します。GAT の集約は
$$ \bm{h}_i^{(l+1)} = \sigma\!\left( \sum_{j \in \mathcal{N}(i) \cup \{i\}} \alpha_{ij}\, \bm{W}\, \bm{h}_j^{(l)} \right) $$
と書けます。ここで $\alpha_{ij}$ が学習される Attention 係数で、$\sum_j \alpha_{ij} = 1$ になるよう softmax で正規化されます。GAT の詳しい仕組みはGAT の解説記事を参照してください。
ここで重要なのは、どちらのモデルも隣接行列が「どの頂点と誰が情報をやり取りするか」を決める骨格になっているということです。隣接行列なしには、近傍 $\mathcal{N}(i)$ の定義そのものができません。隣接行列はグラフ深層学習の世界においても、計算の根幹に居座り続けています。
それでは理論を実装で裏付けていきましょう。次のセクションで、NetworkX、scipy.sparse、そして簡易 GCN まで Python で書き下します。
Python での実装
NetworkX で隣接行列を構築する
まず、グラフを定義して隣接行列を取り出すところから始めましょう。Python のグラフ操作ライブラリ NetworkX を使うのが最も手軽です。
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
# 無向グラフを作成
G = nx.Graph()
edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4), (4, 5), (4, 6)]
G.add_edges_from(edges)
# 隣接行列を NumPy 配列として取得
A = nx.to_numpy_array(G, nodelist=sorted(G.nodes()))
print("Adjacency matrix A:")
print(A.astype(int))
print(f"\nShape: {A.shape}, Symmetric: {np.allclose(A, A.T)}")
このコードは 7 頂点・8 辺の無向グラフを定義し、to_numpy_array で密な隣接行列を取り出します。出力された行列を見ると、各行の和が頂点の次数に一致しており、対角成分は自己ループがないので $0$ です。Symmetric: True の表示から、無向グラフの隣接行列が対称であることも確認できます。これはまさに $\bm{A} = \bm{A}^{\top}$ の数式上の主張を計算機で裏付けたものです。
続いて、グラフ自体を可視化してみましょう。
import networkx as nx
import matplotlib.pyplot as plt
fig, axes = plt.subplots(1, 2, figsize=(12, 5))
# 左: グラフ描画
pos = nx.spring_layout(G, seed=42)
nx.draw(G, pos, ax=axes[0], with_labels=True, node_color='lightblue',
node_size=600, font_size=14, font_weight='bold', edge_color='gray')
axes[0].set_title('Graph G')
# 右: 隣接行列のヒートマップ
im = axes[1].imshow(A, cmap='Blues', vmin=0, vmax=1)
axes[1].set_title('Adjacency matrix A')
axes[1].set_xlabel('column j')
axes[1].set_ylabel('row i')
axes[1].set_xticks(range(len(A)))
axes[1].set_yticks(range(len(A)))
for i in range(len(A)):
for j in range(len(A)):
if A[i, j] == 1:
axes[1].text(j, i, '1', ha='center', va='center', color='white')
plt.colorbar(im, ax=axes[1], fraction=0.046)
plt.tight_layout()
plt.savefig('adjacency_matrix.png', dpi=150, bbox_inches='tight')
plt.show()
左にグラフ、右に隣接行列をヒートマップで並べると、「辺の有無」と「行列の $1$ の位置」が一目で対応していることが視覚的に分かります。対角線を軸に行列が対称であることもはっきり確認でき、$\bm{A} = \bm{A}^{\top}$ という性質が「鏡映対称な行列パターン」として目に見える形になります。
有向グラフの場合
有向グラフでは行列が非対称になることを確認しましょう。
import numpy as np
import networkx as nx
# 有向グラフ
DG = nx.DiGraph()
directed_edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 2), (4, 5)]
DG.add_edges_from(directed_edges)
A_dir = nx.to_numpy_array(DG, nodelist=sorted(DG.nodes()))
print("Directed adjacency matrix:")
print(A_dir.astype(int))
print(f"Symmetric: {np.allclose(A_dir, A_dir.T)}")
# 出次数(行和)と入次数(列和)
out_deg = A_dir.sum(axis=1)
in_deg = A_dir.sum(axis=0)
print(f"\nOut-degrees: {out_deg.astype(int)}")
print(f"In-degrees : {in_deg.astype(int)}")
Symmetric: False という出力が、有向グラフでは $A_{ij}$ と $A_{ji}$ が一般に異なることを示しています。続く出力では、行和が各頂点の出次数、列和が入次数に対応していることが確認できます。たとえば頂点 2 の出次数は 2(頂点 0 と 3 へ出る)、入次数は 2(頂点 1 と 4 から入る)、といった具合に手で数えた結果と一致します。
行列のべき乗で $k$-step パスを数える
理論で導いた「$(A^k)_{ij}$ は $i$ から $j$ への $k$-step ウォーク数」を実際に確かめましょう。
import numpy as np
import networkx as nx
# 小さな無向グラフ
G_small = nx.Graph()
G_small.add_edges_from([(0, 1), (1, 2), (2, 3), (0, 2), (1, 3)])
A = nx.to_numpy_array(G_small).astype(int)
print("A =")
print(A)
# A^2 と A^3
A2 = A @ A
A3 = A @ A @ A
print("\nA^2 =")
print(A2)
print("\nA^3 =")
print(A3)
# トレースから閉ウォーク総数と三角形数を計算
n_triangles = np.trace(A3) // 6
print(f"\nTrace(A^3) = {np.trace(A3)}, 三角形の数 = {n_triangles}")
出力された $A^2$ を見ると、対角成分は各頂点の次数に一致します(2-step で戻ってこられる経路は隣接頂点を介した往復に対応するため)。$A^3$ のトレースを 6 で割ると三角形の個数になります。このグラフの場合、$\{0, 1, 2\}$ と $\{1, 2, 3\}$ の 2 つの三角形があるはずで、計算結果も確かに $2$ となります。理論で導いた公式 $\Delta = \mathrm{tr}(A^3) / 6$ がそのまま動く様子を確認できました。
ラプラシアンとその固有値
次は、ラプラシアン行列を構築し、その固有値を見てみます。
import numpy as np
import networkx as nx
# 7 頂点グラフ(冒頭と同じ)
G = nx.Graph()
G.add_edges_from([(0, 1), (0, 2), (1, 2), (1, 3), (2, 3),
(3, 4), (4, 5), (4, 6)])
A = nx.to_numpy_array(G)
D = np.diag(A.sum(axis=1))
L = D - A
print("Degree matrix D (diagonal):", np.diag(D).astype(int))
print("\nLaplacian L =")
print(L.astype(int))
# 固有値分解
eigvals, eigvecs = np.linalg.eigh(L)
print(f"\nLaplacian eigenvalues (sorted): {np.round(eigvals, 4)}")
print(f"Number of zero eigenvalues: {np.sum(np.isclose(eigvals, 0))}")
print(f"Algebraic connectivity (λ_2): {eigvals[1]:.4f}")
出力を見ると、ラプラシアン $L$ の対角は各頂点の次数、非対角は辺がある場所が $-1$ になっています。固有値はすべて非負で、最小固有値は厳密に $0$。「ゼロ固有値の個数 = 連結成分の数 = 1」となるはずで、結果もそうなっています。第 2 小固有値 $\lambda_2$(代数的連結度)が正なので、このグラフは連結であることが固有値だけから判定できました。
非連結グラフでどう変わるか、実験してみましょう。
import numpy as np
import networkx as nx
# 2 つの連結成分を持つグラフ
G_disconn = nx.Graph()
G_disconn.add_edges_from([(0, 1), (1, 2), (2, 0), # 三角形
(3, 4), (4, 5), (5, 3)]) # 別の三角形
A = nx.to_numpy_array(G_disconn)
L = np.diag(A.sum(axis=1)) - A
eigvals = np.linalg.eigvalsh(L)
print(f"Eigenvalues: {np.round(eigvals, 4)}")
print(f"Zero eigenvalues: {np.sum(np.isclose(eigvals, 0))} (= 連結成分数)")
2 つの三角形が独立に存在するグラフでは、固有値のうち $\lambda_1 = \lambda_2 = 0$ となるはずです。出力もこの予想と一致し、「ゼロ固有値の重複度 = 連結成分の数」というスペクトルグラフ理論の核心的事実が、たった数行のコードで確かめられます。
フィードラーベクトルでグラフを 2 分割
第 2 小固有値に対応するフィードラーベクトルを使って、グラフを 2 つに分割してみましょう。
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
# 2 つのコミュニティを橋渡し辺でつないだ「barbell 風」グラフ
G_two = nx.Graph()
# 左のクリーク
G_two.add_edges_from([(0, 1), (1, 2), (2, 0), (0, 3), (1, 3), (2, 3)])
# 右のクリーク
G_two.add_edges_from([(4, 5), (5, 6), (6, 4), (4, 7), (5, 7), (6, 7)])
# 橋渡し
G_two.add_edge(3, 4)
A = nx.to_numpy_array(G_two)
L = np.diag(A.sum(axis=1)) - A
eigvals, eigvecs = np.linalg.eigh(L)
fiedler = eigvecs[:, 1] # 第 2 小固有値の固有ベクトル
labels = (fiedler > 0).astype(int)
print(f"λ_2 = {eigvals[1]:.4f}")
print(f"Fiedler vector: {np.round(fiedler, 3)}")
print(f"Partition labels: {labels}")
# 可視化
pos = nx.spring_layout(G_two, seed=1)
colors = ['salmon' if l == 0 else 'skyblue' for l in labels]
plt.figure(figsize=(8, 5))
nx.draw(G_two, pos, with_labels=True, node_color=colors,
node_size=600, font_weight='bold', edge_color='gray')
plt.title('Spectral bisection via Fiedler vector')
plt.tight_layout()
plt.savefig('fiedler_partition.png', dpi=150, bbox_inches='tight')
plt.show()
実行結果のフィードラーベクトルを見ると、頂点 0〜3 と頂点 4〜7 で符号が反対になっており、橋渡し辺 (3, 4) を境にきっちり 2 つに分かれます。可視化すると、左右で色分けされた頂点群が見え、橋渡し辺がぴったり「切断線」上に来ていることが分かります。ラプラシアンの固有ベクトルから、なんのヒューリスティックも使わずに自然なグラフ分割が得られたわけです。これがスペクトルクラスタリングの威力です。
スパース行列で大規模グラフを扱う
実用上のグラフは数百万〜数十億頂点に達するため、密な NumPy 配列ではメモリが破綻します。scipy.sparse を使えば、非ゼロ成分だけを保持して効率的に扱えます。
import numpy as np
import networkx as nx
import scipy.sparse as sp
import scipy.sparse.linalg as spla
# ランダムなグラフ(Erdős–Rényi)
n = 1000
G = nx.erdos_renyi_graph(n, p=0.005, seed=42)
# scipy のスパース行列として取得
A_sparse = nx.to_scipy_sparse_array(G, format='csr')
print(f"Shape: {A_sparse.shape}")
print(f"Non-zeros: {A_sparse.nnz} ({A_sparse.nnz / n**2 * 100:.2f}%)")
# 次数とラプラシアン
deg = np.asarray(A_sparse.sum(axis=1)).flatten()
D = sp.diags(deg)
L = D - A_sparse
# 最小の 3 つの固有値だけを ARPACK で計算
eigvals, eigvecs = spla.eigsh(L.astype(float), k=3, sigma=0, which='LM')
print(f"Smallest 3 eigenvalues: {np.round(np.sort(eigvals), 4)}")
このコードでは 1000 頂点のランダムグラフを生成しますが、非ゼロ成分の比率はわずか 0.5% 程度です。scipy.sparse の CSR 形式は非ゼロ成分だけを格納するため、メモリ消費は $O(\text{nnz})$ にとどまります。さらに ARPACK ベースの eigsh を使えば、巨大行列でも「必要な少数の固有値」だけを部分計算でき、$O(n^3)$ かかるフル固有値分解を回避できます。実世界のグラフ解析はこうしたスパース計算が前提になります。
簡易 GCN レイヤを NumPy で実装
最後に、Graph Convolutional Network の 1 レイヤを NumPy だけで実装し、隣接行列が深層学習でどう作用するかを観察します。
import numpy as np
import networkx as nx
def gcn_layer(A, X, W, activation=np.tanh):
"""GCN の 1 レイヤ
A: 隣接行列 (n×n)
X: 各頂点の入力特徴 (n×d_in)
W: 学習重み (d_in×d_out)
"""
n = A.shape[0]
# 自己ループを追加: A_tilde = A + I
A_tilde = A + np.eye(n)
# 次数行列の対角と D^{-1/2}
deg_tilde = A_tilde.sum(axis=1)
D_inv_sqrt = np.diag(1.0 / np.sqrt(deg_tilde))
# 対称正規化: A_hat = D^{-1/2} A_tilde D^{-1/2}
A_hat = D_inv_sqrt @ A_tilde @ D_inv_sqrt
# 集約と線形変換
H = A_hat @ X @ W
return activation(H)
# テスト用グラフ
G = nx.karate_club_graph() # 有名な 34 頂点のソーシャルネット
A = nx.to_numpy_array(G)
n = A.shape[0]
# ランダムな初期特徴(d_in=8)と重み(8→4)
np.random.seed(0)
X = np.random.randn(n, 8)
W1 = np.random.randn(8, 4) * 0.5
W2 = np.random.randn(4, 2) * 0.5
# 2 層 GCN を通す
H1 = gcn_layer(A, X, W1)
H2 = gcn_layer(A, H1, W2, activation=lambda x: x) # 出力層は活性化なし
print(f"Input X shape: {X.shape}")
print(f"After layer 1: {H1.shape}")
print(f"After layer 2: {H2.shape}")
print(f"\n2D embedding (first 5 nodes):\n{np.round(H2[:5], 3)}")
このコードでは、Zachary’s Karate Club(空手クラブのメンバー間の交友関係)に対し、ランダム初期重みで 2 層の GCN を適用しています。出力 $H_2$ は各頂点の 2 次元埋め込みです。学習なし(重みはランダム)でも、隣接行列を通した集約のおかげで「近隣の頂点は似た埋め込みを持つ」傾向が現れます。これが GCN の根本的な振る舞いです。
埋め込みを可視化してみましょう。
import matplotlib.pyplot as plt
import networkx as nx
# ノードの「真のラベル」(空手クラブの分裂後の所属)
G_karate = nx.karate_club_graph()
true_labels = np.array([1 if G_karate.nodes[i]['club'] == 'Mr. Hi' else 0
for i in G_karate.nodes()])
plt.figure(figsize=(8, 6))
colors = ['red' if l == 0 else 'blue' for l in true_labels]
plt.scatter(H2[:, 0], H2[:, 1], c=colors, s=120, alpha=0.7,
edgecolors='black')
for i in range(len(H2)):
plt.annotate(str(i), (H2[i, 0], H2[i, 1]), fontsize=8,
xytext=(3, 3), textcoords='offset points')
plt.xlabel('Embedding dim 1')
plt.ylabel('Embedding dim 2')
plt.title('Random-init GCN embedding on Karate club')
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('gcn_embedding.png', dpi=150, bbox_inches='tight')
plt.show()
ランダム重みであっても、赤(Mr. Hi 派)と青(Officer 派)が大まかにクラスタとして分かれて散布される様子が見えます。学習を加えて損失を最小化すれば、もっと明確に二分される埋め込みが得られます。隣接行列を介して近傍情報を集約するだけで、グラフ構造が低次元空間に「写し取られる」——これが GCN の本質的な力であり、隣接行列がその根幹に座っていることを直に体感できます。
隣接行列のべき乗による情報伝搬の可視化
最後にもう一つだけ、$A^k$ がどのように「グラフ上の情報を伝搬するか」を見ておきましょう。
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
G = nx.karate_club_graph()
A = nx.to_numpy_array(G)
n = A.shape[0]
# 1 つの頂点(節点 0)から始めて、A^k v でどこに広がるか
v0 = np.zeros(n)
v0[0] = 1.0 # 頂点 0 にデルタを置く
fig, axes = plt.subplots(1, 4, figsize=(16, 4))
for ax, k in zip(axes, [0, 1, 2, 3]):
# 正規化隣接行列でべき乗(発散しないように)
D_inv = np.diag(1.0 / A.sum(axis=1))
P = D_inv @ A
vk = np.linalg.matrix_power(P, k) @ v0
pos = nx.spring_layout(G, seed=7)
nodes = nx.draw_networkx_nodes(G, pos, node_color=vk, cmap='hot',
node_size=200, ax=ax,
vmin=0, vmax=max(vk.max(), 1e-3))
nx.draw_networkx_edges(G, pos, ax=ax, edge_color='gray', alpha=0.3)
ax.set_title(f'k = {k}')
ax.axis('off')
plt.suptitle('Diffusion via $P^k v_0$ on Karate club graph')
plt.tight_layout()
plt.savefig('diffusion.png', dpi=150, bbox_inches='tight')
plt.show()
このコードでは、頂点 0 に「1」という値を置き、それが正規化隣接行列 $P = D^{-1}A$(ランダムウォークの遷移確率行列)を $k$ 回作用させると、どのようにグラフ全体に広がるかを可視化しています。$k = 0$ では頂点 0 だけが明るく、$k = 1$ で直接の隣接頂点に広がり、$k = 2, 3$ と進むにつれてより遠い頂点にも値が届いていきます。$A^k$(あるいは $P^k$)は文字通り「$k$-step の情報伝搬」を表現しており、これが GNN の各層が「より遠い近傍からの情報を取り込む」仕組みの源泉です。最終的には定常分布に収束し、頂点の次数に比例した値で安定します。
まとめ
本記事では、隣接行列を起点としてグラフ理論の主要な道具立てを線形代数の言葉で整理し、Python 実装で実感を伴って理解するところまでを駆け抜けました。
- 隣接行列の定義: $n$ 頂点グラフの構造を $n \times n$ 行列 $\bm{A}$ に格納する。無向グラフでは対称、有向グラフでは非対称、重み付きでは成分が実数値になる
- 行列演算と組み合わせ論: $(A^k)_{ij}$ は「$i$ から $j$ への $k$-step ウォーク数」、$\mathrm{tr}(A^3)/6$ は三角形の数、行和・列和は出次数・入次数を与える
- 次数行列とラプラシアン: $\bm{L} = \bm{D} – \bm{A}$ はグラフ上の二階微分演算子。対称半正定値で、ゼロ固有値の重複度がそのまま連結成分の数になる
- スペクトルグラフ理論: 第 2 小固有値 $\lambda_2$ は代数的連結度、対応するフィードラーベクトルがスペクトル分割を導く。隣接行列の最大固有値とその固有ベクトルは中心性指標と PageRank の基礎
- グラフ深層学習への接続: GCN レイヤは $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2} H W$ という形で隣接行列を畳み込みカーネルとして用いる。GAT は近傍重みを Attention で学習する。いずれも隣接行列が「誰から情報を集めるか」の骨格を決める
数値実験では、無向グラフの隣接行列が対称になること、$A^k$ のべき乗で経路数が数えられること、ラプラシアンの固有値の $0$ が連結成分数と一致すること、フィードラーベクトルでスペクトル分割が自然に得られること、そして簡易 GCN がランダム重みでもグラフ構造を低次元空間に写し取ることを確認しました。隣接行列は単なるデータ構造を超え、グラフ理論・線形代数・機械学習を一つに結ぶ結節点として機能しているのです。
次のステップとして、以下の記事も参考にしてください。