NO_WAIT

主にプログラミング

Cytoscape.js でインタラクティブなグラフ構造描画 - WordNet の可視化例

Cytoscape.js というオープンソースのグラフ構造可視化ライブラリがあります。 これはJavaScriptで実装され、ブラウザでのインタラクティブなグラフ構造描画を実現できます。 デモに感化され、実際に試してみて、その便利さ、使いやすいAPIに魅了されました。

実際に少し大きめのデータセットで何か動くものを作ってみたくなり、 最近興味を持ち始めたWordNetと絡めることを考えました。 WordNetには同義語を集めた集合 “synset” という概念があり、 synset間の上位下位関係などがデータベース化されています。 この関係をグラフとして表示してみました。

作成したサイト

WordNet Viewer (重いので、デバイスへの負荷が気になる場合はアクセスを控えてください。)

f:id:shinaisan:20170429001600p:plain

グラフ構造描画部

グラフの頂点はsynsetを、 辺はsynset間の関係を表しています。 synset間の関係は上位下位関係を表し、 矢印の先が上位語(hypernym)を指していますが、 それ以外の関係性(包含関係など)も含んでいます。表示上特に区別はしていません。

頂点や辺はドラッグして移動することもできます。 また、背景領域のドラッグやスクロールによって、パンとズームを変更できます。

単語の入力

上部の検索窓から何か単語を入れてみます。 猫が好きなので、「猫」…と入れたいところですが…

f:id:shinaisan:20170429001639p:plain

ここではあえて猫科の「サーバル」。特に深い意味はありません。

f:id:shinaisan:20170429001654p:plain

幼児語もしっかりカバーするWordNetねんねこ にゃんにゃん

(どうでもいいのですが、「ねんねこ」って調べた限り猫の意味はないと思います。 なぜか「猫」と同じsynsetに含まれています。謎です。)

プログラマなので、「プログラマ」を調べます。

f:id:shinaisan:20170429001711p:plain

実は上位語の他に、下位語もいくつかWordNetから拾ってそれも表示するようにしています。

synset詳細表示

各頂点はsynset(同意語を集めた集合)を表しており、クリックすると、 そのsynsetに含まれる単語がsynsetノードを中心に表示されるよう、 レイアウトが変更されます。

f:id:shinaisan:20170429001724p:plain

単語情報の検索

単語表示のレイアウトに切り替えると、各単語ノードのクリックにより、 Tooltipを出すことができます。Google検索ボタンなどを配置してみました。

f:id:shinaisan:20170429001735p:plain

この機能はcytoscape-qtipプラグインの導入により実現されています。

技術的詳細

下記3部構成で作成しました。

  • sequel Ruby Gem でWordNetSQLiteデータベースに対する検索機能を作成。
  • WordNet検索機能を呼び出し、グラフデータを返す簡易WebサーバーをSinatraで作成。
  • Webサーバーが返したグラフデータをCytoscape.jsで表示するスクリプトを作成。

Cytoscape.js

Cytoscape.jsは既に述べたように JavaScriptによるグラフ構造可視化ライブラリです。 「グラフ」は「ネットワーク」と呼ばれることもあります。

拙作のサイトで実現されている頂点選択、ドラッグ、パン・スームなどの機能は 標準搭載されており、 極端な話、グラフデータをJSONで準備してしまえば 即座に基本的なグラフ可視化機能をブラウザ上で実行できてしまいます。 便利です。

以下では設定例を紹介しますが、あくまで雰囲気を伝えるのみです。 詳細な情報はjs.cytoscape.orgのドキュメントで十分に得ることができます。

初期化

後述するグラフデータ(下記コード中graph)と 表示領域(下記コード中#cy)さえ準備すれば、 例えば下記のような記述で最低限の描画はできます。 用途によってはこれだけで十分かもしれません。

var cy = cytoscape({ // Cytoscape core オプジェクトの初期化。
  container: document.getElementById('cy'),
  elements: graph,
  style: [
    {
      selector: 'node',
      style: {
        label: 'data(label)'
      }
    }
  ]
});

selectorにはCSS風のセレクターを指定しますが、 このセレクターはDOM要素ではなく、Cytoscape.jsのグラフデータ (初期化時に与えたelements)に対して作用します。
下表は、selector指定と、それが選択する対象の例です。

selector 対象
node 頂点。
edge 辺。
#foo ele.data.id"foo"であるグラフの要素ele
.foo クラスfooを持つグラフの要素。addClass("foo")したノードなど。
[some_parameter = "some value"] ele.data.some_parameter == "some value"であるグラフの要素ele
[?some_parameter] ele.data.some_parametertrueと評価されるグラフ要素ele
:visible 可視要素。

要素のラベルはstylelabelで設定します。 上掲の例ではdata(label)が指定されています。 これはselectorに選択された要素eleについて ele.data.labelをラベルとして表示せよとの指示になります。

グラフデータ

elementsは以下に例示するようなデータの配列を指定します。
data.idは指定必須です。
groupは指定なしでもcytoscapeがnodesかedgesかを自動で推測します。
辺は始点のidと終点のidをそれぞれsourcetargetで指定します。

{
  elements: [
    // 頂点データの例
    {
      group: "nodes",
      data: {id: "node1", label: "label for node1"}
    },
    {
      group: "nodes",
      data: {id: "node2", label: "label for node2"}
    },
    // 上記2頂点を接続する辺データの例
    {
      group: "edges",
      data: {id: "node1-to-node2", source: "node1", target: "node2"}
    }
  ]
}

グラフ解析

cytoscape.jsにはグラフ解析や探索のための基本的な関数やアルゴリズムも実装されています。 例えば、ノードに対するdegree, indegree, outdegreeメソッド呼び出しにより、 それぞれ次数、入次数、出次数を得ることができます。

拙作サイトではdijkstraによる頂点間距離測定、 およびneighborhoodによる隣接頂点取得を利用しています。

以下はdijkstraを用いてdata.startがtrueと評価されるノードを始点として、 与えられた頂点nとの最短距離distを求めるコードです。 辺の重みは一律に1と指定しています。

var dijkstra = cy.elements().dijkstra('[?start]', function() {return 1});
var dist = dijkstra.distanceTo(n);

ある頂点nに隣接する頂点を得る場合

n.neighborhood(); // Or n.openNeighborhood();

で得ることができます。頂点n自身も得たい場合は

n.closedNeighborhood();

とします。

スタイルとレイアウト

スタイルとレイアウトは初期化時に与えることができますが、 初期化後に動的に変更することもできます。

下記はノードの大きさのスタイル指定例です。 mapDatadata.weightに指定された数値を線形変換してノードのwidthとしています。

      {
        selector: 'node',
        style: {
          'shape': 'circle',
          'width': 'mapData(weight, 0, 10, 20, 60)',
          'label': 'data(label)',
          /* ... */
        }
      }

レイアウトに関しては、ノードを同心円状に配置するconcentricレイアウトを使用しています。 以下、設定例です。 concentric関数は、中心により近く配置してほしいノードに対して、大きな値を返すよう設定します。 ここではdijkstraを利用して中心となるノードから距離が近いノードほど中心に配置されるよう設定しています。 levelWidthはその値の刻み幅と考えることができます。

  {
    name: 'concentric',
    concentric: function(n) {
      var d = dijkstra.distanceTo(n);
      return cy.nodes().length - d;
    },
    levelWidth: function(nodes) {return 1;}
  };

WordNet データベースファイルをRubyで検索

可視化対象のグラフデータは日本語WordNet から入手できるSQLite 3データベースファイルから作成しています。 データベースファイルはここ から入手できます。

Sequel

WordNetRubyから検索するにはwordnet Gemを利用するのが手っ取り早いと思いきや、 英語版WordNetと日本語WordNetとはデータベースのスキーマが違うのか使用できません。

そこで、sequel Gemを利用することにしました。 sequelにより、SQLをあたかもRubyのプログラムのように記述できます。

ダウンロードしたSQLite 3ファイルを./wnjpn.sqlite3とすると、 Sequelは例えば次のように初期化します。 (ここではラッパークラスを作り、そのメンバ変数に代入する流儀で書きました。)

require 'sequel'
# ...
  @db = Sequel.sqlite('./wnjpn.sqlite3')

この@dbを以後、クエリ発行に使用します。

単語からsynsetを検索

与えられた見出語lemmaを持つ単語をまずはwordテーブルから検索します。 それをwordidsenseテーブルと結合します。 以下は結果のテーブルからsynsetword.langword.lemmaの3列を返すクエリです。

  def get_word_synsets(lemma)
    words = @db[:word].where(:lemma => lemma)
    senses = words.join(:sense, :wordid => :wordid)
    senses.select(:synset, Sequel.qualify(:word, :lang), Sequel.qualify(:word, :lemma))
  end

Sequel.qualify(:word, :lemma)Sequel[:word][:lemma]とも書けるようです。

上記により次のようなSQLが発行されます。

SELECT "synset", "word"."lang", "word"."lemma" FROM "word"
  INNER JOIN "sense" ON ("sense"."wordid" = "word"."wordid")
  WHERE ("lemma" = lemma)

与えられたsynsetの上位synsetを検索

上で、検索語からsynsetを得ることはできます。 今度はその上位語などを求めてみます。 synlinkテーブルからlinkhype(上位語)である組(synset1, synset2)のうち、 synset1(下位語)が指定したsynsetとなるものを検索します。

  def synset_to_hypernyms(synset)
    @db[:synlink].where(:synset1 => synset).where(link: 'hype')
      .select(:synset1, :synset2)
  end

上記により次のようなSQLが発行されます。

SELECT "synset1", "synset2" FROM "synlink"
  WHERE (("synset1" = synset) AND ("link" = "hype"))

作成したサイトでは、この上位synsetを検索する操作を3レベルまで繰り返しています。

反省

パフォーマンス

アニメーションを伴う可視化なので、それなりにブラウザに負荷をかけます。

また、cytoscape.jsのファイルサイズも少し気になります。 2.7.16を使用していますが、minifyした状態で300KB近くあります。 無圧縮だと700KB以上となります。

筆者はというと、その種の検討は棚上げし、 とにかく動かして試して見るということを優先しました。 可視化のプログラミングはとにかく楽しいのですが、出来上がったブツが重い… WordNetをブラウザ上で検索するだけが目的であれば Extended Open Multilingual Wordnetsimple search interface を使用すれば十分です。

とはいうものの、 Cytoscape.js 、便利であることは間違いありません。 それほど大きくはないが、構造は複雑で、属性を多く含むグラフデータが手元にある場合、 それらの解析・可視化手段として利用価値は高いだろうと思います。

ラベル表示

現状、関係性のラベルを表示していないので、 各synsetが下位語なのか、包含関係にあるのか、 構成要素なのか曖昧になってしまっています。 実際に可視化してみてやはり必要かなと思いました(←じゃぁ作れよ)。

レイアウト

グラフを表示するだけなら簡単ですが、 レイアウトやアニメーションのチューニングは結構大変です。 拙作サイトではノードをクリックした時のレイアウト切替アニメーションが少し変です。 また、concentricレイアウトのみを使用していますが、他も検討してみたほうがいいかもしれません。 もっとも、効果的なグラフ可視化の追求は研究テーマになってしまうのでどこまで深入りすべきか悩みどころです。

参考