WISS 2021

階層型グラフ可視化数値評価基準に基づく評価結果とレイアウトの比較検討
村上 綾菜 ∗

伊藤 貴之 ∗

概要. 大規模なグラフの可視化において，グラフを構成するノードのレイアウトが可読性に大きく影響を与える．そこで我々は，深層学習を用いて階層型グラフのレイアウトを改善する研究を進めている．ここで深層学習モデル構築の過程において我々は，階層型グラフに特化した可視化結果の数値評価式を適用している．この評価式は，Sprawl(空間の浪費) と Clutter(配置の乱雑度) という 2 つの評価値の積で階層型グラフ可視化結果の品質を評価する．ここで問題となるのが，Clutter を評価する複数のペナルティの重みづけ(係数調整) である．本報告では，数値評価式の係数を詳細に探索することを目的とし，数値評価式を用いて算出した評価値と階層型グラフの可視化結果を一覧表示するインタラクティブなダッシュボードを開発した．本報告では，ダッシュボードの機能を述べたのち，それを用いて得られた知見について議論する．

1

はじめにグラフ可視化のためのグラフレイアウトは，可読性の高さを大きく左右する．特に，複数のノードの集合 (メタノード) で構成される階層型グラフの画面配置手法は，大規模なグラフの概要を効果的に可視化する手法として知られているが，グラフが大規模になるほどグラフレイアウトの良し悪しが可読性に大きく影響する．しかし，階層型グラフのレイアウトにおいては，複雑な接続構造の表現，メタ情報と接続構造の相関表現などの必要性の観点から，可読性の高いレイアウトの生成が非常に難しい．そこで我々は，深層学習を用いた階層型グラフのレイアウト改善に取り組んでいる．この研究において，「階層型グラフの良いレイアウト」を数値的な評価値を用いて定義する必要がある．
グラフ可視化の視認性の評価は長年の課題であり，数値評価と主観評価の両面にわたって多くの研究が発表されている．しかしその大半は非階層型グラフを対象としたものであり，階層型グラフの可視化結果に特化した評価手法の研究は非常に少なかった．
それに対して Liu ら [2] は，階層型グラフに特化した新しい数値評価基準である Sprawlter を提唱している. この数値評価基準では，Sprawl(空間の浪費)と Clutter(配置の乱雑度) という観点から階層型グラフ可視化結果の品質を評価する．
本報告では，ダッシュボードを用いた Sprawlterの係数調整インタフェースを提案する．まず階層型グラフレイアウトの従来手法を用いて多数の階層型グラフレイアウトを生成する．続いて各レイアウトに対して Sprawlter を適用して数値評価値を得る．
この結果を可視化ダッシュボードに載せることによ
Copyright is held by the author(s). This paper is nonrefereed and non-archival. Hence it may later appear
in any journals, conferences, symposia, etc.
∗お茶の水女子大学

り，係数変更により得られる新たな評価値とグラフレイアウトの関係を容易に比較できる．本報告では，このダッシュボードによる係数調整によって得られた知見についても議論する．

2関連研究：階層型グラフレイアウトの評価

階層型グラフに特化したグラフ可視化結果の数値評価手法の研究は非常に少ない．その中でも Liu ら[2] は，階層型グラフ可視化のための数値評価を「空間の浪費 (Sprawl)」と「配置の乱雑度 (Clutter)」の 2 つの観点から提唱し，Sprawl と Clutter という 2 つの評価値の積で可視化結果の品質を評価している．そのうち Clutter について，Sprawlter では以下の 3 つのペナルティを算出している．

1. メタノード間の重なり (メタノード間が重なる面積の合計値)
2. メタノードとエッジの重なり (メタノードを通過するエッジの長さの合計値)
3. エッジ間の重なり (エッジ間の内積の合計値)
これら 3 つのペナルティを上から順に NN，NE，EEと表記する．なおいずれのペナルティも，北川ら [3]に従い，数値が小さいほど好ましいグラフ可視化結果であるとする．そして本研究では Clutter の評価値を以下の式で算出する．

Clutter = αN N + βN E + γEE(1)

ここで，係数 α, β, γ の策定については十分に議論されていない．北川ら [3] の研究ではこれに対して一定の考察をしているが，著者らによる主観評価にもとづいて議論されている上，比較している係数の候補が少なく十分とはいえない．
本報告では，これらの係数の変更にともなう Clutter 値の算出結果と，階層型グラフ可視化結果を比較参照できるインタラクティブな可視化ダッシュボー

WISS 2021

ドを提案する．本手法を利用することで，Clutterの係数の細かい調整を支援できる．また，本ツールを用いて筆者以外の人が評価しても良いレイアウトと判断されるかを調査することによって，より詳細で信頼性ある形で係数を検討する．

3ダッシュボードの開発

我々は以下の 2 つの機能を有するダッシュボードを開発した．実装には Python の Web アプリケーション開発用フレームワーク Streamlit を用いた．

3.1

機能 1: 係数の調整

本機能では，3 つのペナルティを表示するとともに，係数を調節した後の新たな Clutter 値を表示する．ここでダッシュボード使用者は，係数を範囲 [0.0,1.0]の実数で入力できる．本機能は，入力値に沿って再算出した Clutter 値を表形式で表示する．ここで使用者が任意の表の列名をクリックすることで，Clutter値を昇順・降順にソートできる．また，各列の最小値はハイライトされる．

3.2

図 1. ペナルティの違いによる高評価グラフの違い
上 2 つのグラフは，ペナルティの係数を全て 1 とした際の評価上位 2 つのグラフ．下 2 つのグラフ
は，エッジ同士の位置関係に関するペナルティの係数のみを 0 とした際の評価上位 2 つのグラフ

機能 2: 階層型グラフの比較表示

本機能では図 1 に示すように，利用者が選択した任意の階層型グラフ可視化結果を並べて表示する．
現在の実装では，最大 4 個の可視化結果を独立に選択できる．利用者はこの機能により並べて表示した可視化結果を容易に比較できる．

4

実行例と考察我々は本研究で開発したダッシュボードを用いて，200 個の階層型グラフ群の数値評算出結果と各々の可視化結果を比較検討した．使用する階層型グラフ群の作成には伊藤ら [1] の手法を用いた．
まず，北川ら [3] が言及していた，「エッジ間の位置関係に関するペナルティは，残り 2 つのペナルティと比べて可視化結果の可読性に直結しているとは言えない」という知見が，ダッシュボードを用いても同様に観察されるかを検証した．
図 1 より，エッジ間の位置関係に関するペナルティに関しては，そのペナルティの値に関わらず高評価となる可視化結果が変わらないため，可読性に影響が少ないということを再確認できる．
一方で，図 2 に示す 2 つのグラフと，図 1 の上 2つのグラフと比較すると，図 2 の右側のグラフは上から 2 番目の評価のグラフにも関わらず，エッジが重なる部分が多く，良いレイアウトととは言い難い．
このことから，エッジの重なりの少ない階層型グラフを表現するには，ノードとエッジの位置関係に関するペナルティが必要である，と言える．

図 2. ノードとエッジの位置関係に関するペナルティの係数のみを 0 とした際の評価上位 2 つのグラフ

5

まとめと今後の課題本報告では，階層型グラフに特化した可視化結果の数値評価手法 Sprawlter に用いる係数の調整のために，可視化ダッシュボードを開発して一覧表示し，可視化結果を比較分析した．その上で，ペナルティの 3 つの係数をそれぞれ変えることによりグラフの可視化結果も変わることを確認した．発表の際には，ユーザ評価結果からグラフの評価値の適正さについて述べるとともに，他のペナルティの係数についても同様に調査を進めたい．
将来的には，本報告の内容を踏まえて Sprawlterの最適な係数を選択し，深層学習を用いたグラフレイアウトの改善に活用したい．

階層型グラフ可視化数値評価基準に基づく評価結果とレイアウトの比較検討

参考文献[1] T. Itoh and K. Klein. Key-node-Separated Graph
Clustering and Layout for Human Relationship
Graph Visualization. In IEEE Computer Graphics and Applications, pp. 30–40, 2015.
[2] Z. Liu, T. Itoh, J. Dawson, and T. Munzner. The

Sprawlter Graph Readability Metric: Combining
Sprawl and Area-Aware Clutter. In IEEE transactions on visualization and computer graphics.,
pp. 2180–2191, 2020.
[3] 北川, 伊藤. 階層型グラフ可視化の数値評価基準に関する検証実験. 映像情報メディア学会技術報告= ITE technical report, pp. 215–218, 2021.