メインページ

第2章 グラフ理論の基礎

はじめに

グラフ は，対象同士の関係を記述し，社会科学や言語学，化学，生物学，物理学など，様々な分野で得られるデータを表すのに不可欠である． 実際に社会科学の分野では，個人同士の関係を示すためにグラフが広く使われていたり，また，化学においては原子をノード，化学結合をエッジとみなすようなグラフが使われている(Bonchev, 1991)． さらに言語学でも，与えられた文章の構文・構造を把握するためにグラフが活用される． 例えば，文脈自由文法(context-free grammar)に沿った文章の構文構造の表現に「構文木」が用いられているほか，抽象意味表現(AMR; Abstract Meaning Representation)は「根(root)を持つ有向グラフ」として文章の意味を符号化している(Banarescu et al., 2013)． 以上からわかるように，グラフに関する研究は多分野にわたって大きな注目を集めている．

本章ではまず，グラフに関する基本的な概念を紹介し，グラフの行列表現である隣接行列やラプラシアン行列(Chung and Graham, 1997)について述べ，それらの基本的な性質を見ていく．次に，各ノードが属性を持った「属性付きグラフ」を導入する． この属性は，グラフ上の関数もしくは信号と解釈でき，グラフに新たな意味を与えることになる(Shuman et al., 2013)． そして，グラフ深層学習の重要な基盤となるグラフフーリエ解析とグラフ信号処理の概念を紹介する． その後，複雑グラフ(complex graph)という，実世界の応用において複雑な関係を持つ対象を表現するために利用されるグラフについて説明する． 本章の最後では，グラフ深層学習の下流タスクとして広く利用されている，「グラフ上の代表的な分析タスク」について説明する．

目次

• 2.1 はじめに
• 2.2 グラフの表現
• 2.3 グラフの性質と様々な指標
• 2.3.1 次数
• 2.3.2 連結性
• 2.3.3 中心性
• 2.3.3.1 次数中心性
• 2.3.3.2 固有ベクトル中心性
• 2.3.3.3 Katz中心性
• 2.3.3.4 媒介中心性
• 2.4 スペクトルグラフ理論
  • 2.4.1 ラプラシアン行列
  • 2.4.2 ラプラシアン行列の固有値と固有ベクトル
• 2.5 グラフ信号処理
  • 2.5.1 グラフフーリエ変換
• 2.6 複雑グラフ
  • 2.6.1 ヘテログラフ
  • 2.6.2 二部グラフ
  • 2.6.3 多次元グラフ
  • 2.6.4 符号付きグラフ
  • 2.6.5 ハイパーグラフ
  • 2.6.6 ダイナミックグラフ
• 2.7 グラフを使った分析タスク
  • 2.7.1 ノードを対象としたタスク
    • 2.7.1.1 ノード分類
    • 2.7.1.2 リンク予測
  • 2.7.2 グラフと対象としたタスク
    • 2.7.2.1 グラフ分類
• 2.8 本章のまとめ
• 2.9 参考文献

メインページ