Graph abstraction for closed pattern mining in attributed networksを読んだ

概要

Henry Soldano and Guillaume Santini, Graph abstraction for closed pattern mining in attributed networks, ECAI2014

  • 属性付きグラフ(Attributed Graphs)から構造特徴(topological features)よりリッチな特徴発見を行う手法を開発することが目的
  • データマイニングでよく利用される閉集合(閉パターン)/形式概念解析(FCA)を利用し、グラフ構造を抽象化する操作(Graph Abstraction)を被せたパターン抽出法を提案
  • データセット(Teenage Friends, DBLP)で組み合わせ手法を評価

2値のアイテム集合パターンが頂点に与えられているグラフを考える。頂点aからfに対応するアイテム集合が表の形で与えられるとする(これによって頂点を属性付きとみなす)。

f:id:takilog:20180507104338p:plain

グラフ構造を与える。

f:id:takilog:20180507104435p:plain

構造特徴ではない知識発見クエリとして「パターンt = xyに対して、グラフ属性: 次数≧2」を考える。パターンt = xyは頂点のうちe以外の5頂点によって支持される(supports)ので、次の部分グラフ構造が誘導される。

f:id:takilog:20180507104727p:plain

この構造特徴に対して「グラフ属性: 次数≧2」というグラフ上の操作に関するfix-pointとして、最初にfが、次にdが削除される(abstractされる)ことにより、次のグラフ構造を得る。

f:id:takilog:20180507104826p:plain

グラフ構造がfix-pointに到達したので、属性の世界に戻る。もう一度表を参照すると、頂点abcについて、それぞれ集合xykがサポートされることが分かる。xykによって抽出される条件を満たしたグラフ構造はabcによる完全部分グラフK3のみなので、この操作についてグラフ構造abcと属性xykがclosed patternと抽出されると考えられる。このとき

  • abcdfについてパターンxy(abstract操作により、サポート3になる)
  • abcfについてパターンxyk(abstract操作により、サポート3になるが、グラフabcfは非連結)

という対応関係が存在するので、グラフの属性情報(ここでは頂点の次数フィルタに対応)を導入することで、抽象的な頻度というデータ解析手法を構築することができる。例えばimplication ruleを構築する場合、x → yという自明なルールだけではなく、この操作のもとでx → yk というルールを発見できる。このような操作(閉集合×Graph Abstraction)の背景にはどのような構造が隠れているのか?に関する論文が本論文になる。

実験

  • 音楽データにラベルが付けられたグラフの解析
    • {rock}→{folk}, {jazz}→{rock, folk}, and {pop}→{rock, folk}が得られる(抽象化)

f:id:takilog:20180507111144p:plain

  • 比較的良く使われているTeenage Friendsグラフデータの解析
    • 抽象化操作を入れると、発見されるimplication ruleが減るけど、いい感じの知見を発見できるルールがちゃんと含まれている
    • ただし、抽象化操作を入れることで、大きく変化する例もある

f:id:takilog:20180507111628p:plain

  • 上がグラフ抽象化操作なし、下は操作あり
  • 左は{C1, D123, T1}というパターンに対するグラフ表現、右は{C1,D123,T1,S2}というパターンに対するグラフ表現
  • 抽象化操作を入れた場合、S2導入で何も出力されていないが、抽象化操作無しの場合はいくつかの頂点と辺が残っている

メモ

  • 抽象操作を束上のProjectionとして導入すると、元のガロア対応と併用して新しいガロア対応を構築でき、それを用いて新しい束(abstract concept lattice)を構築できる
  • グラフG = (O, E)を考え、その上でabstract concept latticeを構築する
  • 具体的なグラフ抽象化操作の例
    • 次数制約(上の例を参照)
    • k-clan制約: k-cliqueを緩和した制約
    • nearStar制約: nearStar(k, d) は頂点xが次数k以上を持つか、次数k以上の2頂点x, yをつなぐ長さdのパスの上に存在すること
    • 連結成分サイズ制約: サイズs以上の連結成分に属していること
    • k-cliqueGroupサイズ制約: サイズs以上のk-clique(の和)に属していること

論文から例題を引用。

f:id:takilog:20180507110942p:plain