概要
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に対応するアイテム集合が表の形で与えられるとする（これによって頂点を属性付きとみなす）。
グラフ構造を与える。
構造特徴ではない知識発見クエリとして「パターンt = xyに対して、グラフ属性: 次数≧2」を考える。パターンt = xyは頂点のうちe以外の5頂点によって支持される（supports）ので、次の部分グラフ構造が誘導される。
この構造特徴に対して「グラフ属性: 次数≧2」というグラフ上の操作に関するfix-pointとして、最初にfが、次にdが削除される（abstractされる）ことにより、次のグラフ構造を得る。
グラフ構造が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}が得られる（抽象化）
- 比較的良く使われているTeenage Friendsグラフデータの解析
- 抽象化操作を入れると、発見されるimplication ruleが減るけど、いい感じの知見を発見できるルールがちゃんと含まれている
- ただし、抽象化操作を入れることで、大きく変化する例もある
- 上がグラフ抽象化操作なし、下は操作あり
- 左は{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（の和）に属していること
論文から例題を引用。
- 実際のパターン生成はLCMに似た深さ優先探索
