必ずわからせます「カーネル辺密度推定法によるグラフ束化」

Hurter and Ersoy and Telea, Graph bundling by kernel density estimation, Computer Graphics Forum 31, pp. 865-874, 2012.

概要

グラフやネットワークを描画すると、しばしば辺が多いために詳細を観察することが困難になる。グラフ束化はグラフの辺を湾曲させて、束ねることでグラフの概要を見通しやすくする技術である。グラフ束化の研究分野が俄かに賑やかになったのは2006年にHoltenが階層的グラフ束化をきっかけにしている。今日では、Holten の仕事は第二世代のグラフ束化技術とされている。

この論文はカーネル辺密度を推定する新しい手法(KDEEB)を提案し、グラフ束化技術の第三世代を切り開いた記念碑的な論文である。カーネル推定の手法がやや形式的なためか、多くの研究者が難解だとしているようだが、数式の意味を理解すれば実は直感的なアルゴリズムだということがわかる。ここでは、数式の意味をわかりやすく解説することをめざす。

提案方法のあらまし

まずは、論文のことはひとまず忘れて、紙、鉛筆、そして薄墨用の筆ペンを取り出してほしい。まず、紙に鉛筆の細くて薄い線でグラフの辺を描いてみよう。グラフには、辺が集中した箇所があるとよい。

つぎに、今、描いた細い線を筆ペンでなぞろう。ぽつんと離れた辺の周辺は薄い墨の色がそのまま見える。一方、辺が集中する箇所は薄墨が重なりあい、濃い色になるだろう。すべての線を描き終えた紙に描かれたものが辺密度だ。鉛筆で描いた下書き線をより墨の色の濃い方に湾曲させればグラフ束化ができることがわかるだろう。

グラフ束化の目的はばらばらに散らかった辺を集約し、束ねることである。逆にいえば、ある辺に着目して、その周辺の辺が濃密に集った領域に向かってこの辺を湾曲させることで、グラフ束化を進展させるのである。

辺密度推定

辺密度推定のために重要な定式化は、論文の式(1)である。多くの人がこの式で挫折するようだが、筆ペンで描いた人であれば、その理解は難しくない。以下では式(1)を若干変形した定義を用いる。

$latex \rho(x) = \sum_{c \in C} \int_{y \in c} K(|x – y| / h) $

関数$latex \rho(x)$は画面上のピクセルの座標($latex x$)における辺の推定密度を表す。ここで用いた記号の意味は以下のとおりである：

記号	記号の意味	喩え話では？
$latex x$	画面上のピクセルの座標
$latex \rho(x)$	ピクセルの位置の辺密度	墨の濃さ
$latex c$	グラフの辺に対応する曲線	鉛筆で描いた下書き線
$latex C$	すべての曲線	鉛筆で描いた下書き全体
$latex y \in c$	曲線上の点	下書き線の一点
$latex K$	カーネル関数	筆ペンの滲み加減
$latex h$	カーネル半径	筆ペンの太さ

記号の意味がわかれば式の意味はさほど難しくない。簡単に言えば「紙上の点を塗った墨の濃さは、その点の上を塗ったストロークの墨の濃さの合計」ということだ。

筆ペンの滲み加減を表すカーネル関数($latex K$)は下書き線の上では大きな値となり、筆の太さ($latex h$)以上離れた紙面上の位置では0となる。このカーネル関数を積分($latex \int_{y \in c}$)しているのは、曲線$latex c$に沿って動く筆のストロークが生む墨を積算したいからだ。最後に、すべてのストロークについて総和($latex \sum_{c \in C}$)を取ることで、筆ペンの重ね塗りが表現されている。

論文の図1の左は米国の航空網に対してKDEEBを適用したときの辺密度を山の高さによって表現している。

辺密度勾配

前節で辺密度の推定ができたので、あとは辺を湾曲させるために辺密度勾配($latex \nabla\rho(t)$)を求め、それに応じた方向にむかって辺を湾曲すればよい：

$latex \frac{dx}{dt} = h(t) \frac {\nabla\rho(t)}{|\rho(t)|} $

論文の数式(2)よりも若干複雑になっているのは、分母が0になる可能性を嫌ったためである。

実装について

以上が理論だが、曲線上のすべての点についてカーネル関数を計算するのは非効率かもしれない。実装にあたっては、グラフの辺を表す曲線上からサンプリングした制御点のみを計算対象としている。

筆ペンの喩えを用いるならば、筆を下書き線に沿って描く代わりに、下書き線上を筆で点描することで代用していることになる。論文では、制御点の間隔を筆の太さ程度とすることを提唱している。具体的には OpenGL の point stripe 機能を用いている。

辺密度をさらに正確に予測するには、隣接する制御点を覆う長方形を描く方が望ましいが、この方法では計算コストが高いようだ。

制御点の位置における辺密度勾配の推定では、その位置の周辺の値を用いた数値微分をする。

主なアルゴリズムののほかに

KDEEB では、辺を湾曲させるにあたって障害物の内部にはいりこまないように調整できることや、グラフ束化効果を色によって表現する方法が示されている。