グラフの類似性を評価する - ryamadaの遺伝学・遺伝統計学メモ

はじめに
- 参考PDF
- グラフの同形性評価(graph isomorphism)と類似性評価
  - Graph isomorphismはグラフ構成要素であるノードの1対1対応とエッジの1対1対応によって定義されている。それに対して、類似性評価は同形性からのはずれの程度の評価であり、その尺度は定義に依存する
- グラフの類似度評価
  - 評価の指標(グラフ間距離)に求められるもの
    - Metric
      - 同一グラフ間距離は0
      - グラフＡからグラフＢへの距離とグラフＢからグラフＡへの距離は同一(対象性 Symmetry)
      - グラフＡからＢへの距離とグラフＢからＣへの距離の和はグラフＡからＣへの距離を越えない(Triangle inequality)
  - 評価方法
    - Graph edit distance法
      - ２つのグラフを比較し、グラフに操作(ノードおよびエッジの削除・挿入・置換)を加えることで、両グラフを同一にするときに、その最小操作によってグラフ間距離を定義する方法
    - Maximum common subgraph法→別項を立てる
Maximum common subgraph法
- Maximum common subgraphを用いて、グラフ間の距離を定義する方法
  - Maximum common subgraphとは
    - Isomorophism と　Subisomorphism
      - Isomorphismは「同形」、Subisomorphismは「部分同形：グラフのサブグラフがあるグラフの全体と同形であるとき、サブグラフを含むグラフが、比較したグラフと部分同形であるという」
    - Common subgraph
      - あるグラフが存在して、それに対して、２つのグラフがSubisomorphicであるとき、その２つのグラフのCommon subgrapであると言う
      - ある２グラフのCommon subgraphのうち、ノード数が最大のものをmaximum common subgraphという
- Maximum common subgraphを用いたグラフ間距離の定義
  - グラフG1とグラフG2とのmaximum common graphがG3であるとする
  - それぞれのノード数をVn(G1),Vn(G2),Vn(G3)とする
  - 距離は次式で定義される $￥Large{1-￥frac{Vn(G3)}{max(Vn(G1),Vn(G2))}}$
  - この定義がmetricであることの証明は、参考PDFより
Maximum common subgraphの検出
- Maximu common subgraphの検出は、NP-complete問題である
- 実用には、approximationが必要
  - 複数のapproximationアルゴリズムが提案されているが、適用グラフに応じてパフォーマンスが異なる
    - (1)全common subgraphを探索してmaximum common subgraphを見出すアルゴリズム
    - (2)Associationグラフを検出し、そのmaximum cliqueを検出するアルゴリズム

TFS (Toporogical Fragment Spectra)
- 参考PDF
- 化学構造式間の類似性指標
  - 化学構造式→部分構造候補を羅列
  - 部分構造候補の数値表現
  - 数値の出現頻度度数分布の生成
- TFS間の類似度評価関数
  - 個々の化学構造式は独自のTFSを持つ
  - 化学構造式ペアについてTFSを比較する
  - 例:Cosine係数*1
  - TFS比較係数をもとに化学構造式を順位付けする
- Non-terminal Vertex Graph (NTG)
  - 頂点次数が２以上の頂点のみのグラフ
  - 化学構造で言えば、「環を中心とした骨格」に相当

*1：構造式A、B間のCosine係数 $￥Large{S_{A,B}=￥frac{￥sum_{j=1}^{j=n}{x_{jA}x_{jB}}}{￥sqrt{￥sum_{j=1}^{j=n}(x_{jA})^2￥sum_{j=1}^{j=n}(x_{jB})^2}}}$ :化学分野ではスペクトルデータの評価指標の１つとして(一般的に)用いられるもののひとつ(のようだ)