DEIM2023 2b-4-1

経路相関ルールマイニング
佐々木勇和†† 大阪大学大学院情報科学研究科
E-mail: †sasaki@ist.osaka-u.ac.jp
あらましグラフ相関ルールマイニングはグラフデータ内の相関関係を抽出するデータマイニング技術である．本稿

では，新たな概念である経路相関ルールマイニングを提案する．経路相関ルールマイニングは大規模グラフ内に頻出する経路パターンの相関関係を発見を目的として，到達可能性経路を適用可能とすることで多様な規則を発見する．
経路相関ルールマイニングが NP 困難であることを証明し，非単調性性質を活用したアルゴリズムを開発する．加えて，近似化と並列処理技術を開発し，スケーラブルかつ高速なマイニングを実現とする．大規模な実グラフを用いて評価実験を行い，提案技術の有用性と高速性を示す．
キーワード グラフ分析，相関ルールマイニング
ある” というようなパターンにより，社会分析に活用できる．

1 はじめに相関ルールマイニングは大規模なアイテムセット間の関係性を発見するデータマイニング技術である [1, 2]．相関ルールはX ⇒ Y で表現され，X と Y はそれぞれ条件部と結論部と呼ばれ，非重複なセットになる．その有用性から多くの応用例が存在し，例えば，購買分析 [3] や，ウェブマイニング [4]，バイ
オインフォマティクス [5] に利用されてている．

動機と研究課題．大規模グラフにおけるグラフ相関ルールマイニングはグラフ分析において基礎的な技術であるが，既存技術は上記の応用例に適用できない（詳細は 2 章）． [6–9]．既存技
術は 4 つの観点から柔軟性が低い．まず，既存技術は結論部に含まれる節点集合が必ず条件部の節点集合のサブセットになっていることが求められる．つまり，条件部に含まれていない節点を含む結論部があるようなルールは対象外である．次に，条件部と結論部ともに制限があり，枝ラベルと属性を同時に考慮

グラフ相関ルールマイニング．グラフ相関ルールマイニングはするようなグラフパターンのルールを指定できない．さらに，単一の大規模グラフ内に存在する規則を発見することを目的と節点間の接続可能性のようなパターンは捉えることはできなしている [6–9]．グラフ相関ルールは GX ⇒ GY で表現され，い．最後に，それぞれのアルゴリズムはある単一のグラフタイ

GX と GY はグラフパターンを表す．グラフデータが広く活用

プ（ラベル無し枝など）を想定しており，より一般的なグラフ

されているため，グラフ相関ルールマイニングはグラフの分析

タイプを対象にできない．

や知識発見に広く利用されている．グラフ相関ルールマイニン

そのため，新たなグラフ相関ルールマイニング技術が必要でグは下記のような応用例がある．

ある．三つの研究課題を挙げる．まず，条件部と結合部に制約

ソーシャル分析: ソーシャル分析は我々の生活を理解し向上さがないかつ接続性をグラフパターンに含めることができる柔軟せるために不可欠なデータ分析である．ソーシャル関係はグラな技術が必要である．次に，一般的なプロパティグラフに対しフによりモデル化されるため，グラフ相関ルールマイニングがて全ての頻出集合を求めることが可能な効率的かつスケーラブ

人の状況や関係性のパターンの規則性の発見に活用できる．例

ルな技術が要求される．最後に，規則は知識抽出や分析のため

えば，健康 [10] や幸福 [11] がソーシャル関係により影響されに有用であり，既存のルールの評価尺度である相対支持度やリることが知られており，グラフ相関ルールマイニング活用できフトが利用できることが求められる．

る．例えば，“もし人が幸せなら，健康であり友人をもつ可能

貢献．新たなコンセプトである経路相関ルールマイニングを提性が高い” といったルールを発見できる．

案し，経路相関ルールを高速に発見する効率的かつスケーラブ

社会的差別チェック: データ内の社会的差別は公平な機械学習

ルなアルゴリズムを開発する．経路相関ルールマイニングは経モデルを構築するために解消すべき課題の一つである解決すべ路パターン間の規則の検出を目的とし，経路パターンは節点のき課題である [12]．グラフデータにおける機械学習モデルも差

属性と枝ラベルのシーケンスを表す．節点間のラベル制約付き

別的なバイアスに影響が及ぼされる [13]．グラフ相関ルールマ

接続性を経路パターンに含むことで接続性を規則性に含むこ

イニングは差別的なバイアスを含む規則の発見が可能なため，とが可能である．このマイニングでは，経路パターン pX およ

差別的なバイアスを評価および取り除くことが可能である．

び pY のソースとなる節点集合が支持度の閾値 θ より大きくる

知識抽出: 知識ベースは属性付きの節点とラベル付きの枝から

ルール pX ⇒ pY を検出する．経路相関ルールは，絶対および構成されるグラフで表現されることが多く，知識グラフ内のパターン抽出により様々な知見を発見できる．例えば，“ある人が特定の職をもつ祖先がいる場合，その人の職は祖先と同じで相対支持度や，確信度，リフトといった一般的な評価尺度を計算することができる．

v2

v1
e2
v4

e1
v3
e5

e3
v5
e9
v8

e6

v7
Art

e13

e4
e7

CS

e10

e11

Art

v12

＊

e12
v11

p1 p2

p3

p4

p5

MuseumUni

City

LocatedIn
Male

Female

p6

p7

CS

p8

CS

CS

p9

p10 p11

p13

p12

Rule
Art

BelongTo

Follows

CS

CS

CS

CS

CS

Art

v10
e15 ArtChem

e14

Kleene path

Art

Art

v6 e
8

v9
CS

Length 2 simple path

Length 1 simple path

Art

Art

Art

CS

CS

Likes
Chem

CS

CS
Art

CS

r1

CS

r2

CS

CS

r3

CS

r4

CS

r5

CS

r6

図 1: 経路相関ルールの例

例 1

図 1 に経路相関ルールマイニングの例を示す．与えられたグラフは 12 個の節点，15 個の枝，4 つのタイプの枝ラベ
ル，8 つのタイプの節点の属性を含む．このグラフにおいて θが 1 とした場合の経路相関ルールの例を示す．経路パターン⟨{Male}, Follows, {Art}⟩ は v8 と v9 が始点となるため頻出な経路パターンとなる．同様に，⟨{CS}, BelongTo, {Uni}⟩ も v8 と v9にマッチする．⟨{CS}, Follows, {Art}⟩ ⇒ ⟨{Male}, BelongTo,{Uni}⟩ は経路相関ルールとして検出される．条件部と結論部

2 関連研究本章では，経路相関ルールマイニングに関する関連研究として，ひとつの大規模グラフに対する支持度計算とグラフ相関
ルールマイニングについて述べる．
ひとつの大規模グラフに対する支持度計算. 一般的なアイテ
ムセットに対する支持度は一つのグラフに対して非単調性はに含まれる節点が非重複であり，既存研究では検出できないパ

保証できない．直感的には，経路は節点よりもパターンとしターンである．

て複雑であるが，経路は節点より多いことがありえる．非単調性を保持するために，様々な支持度が提案されている．例

経路相関ルールマイニングが NP 困難問題であることを証明

えば，maximum independent set based support (MIS) [14]し，効率的に頻出な経路パターンとルールを発見するアルゴリ

minimum-image-based support (MNI) [15], minimum clique

ズムを開発する．提案アルゴリズムは経路パターンにおける非partition (MCP) [16], minimum vertex cover (MVC) [17], お

単調性性質を活用し，頻出となりえない経路パターン候補を枝よび maximum independent edge set support (MIES) [17] が刈りする．経路パターンの枝刈りは，経路パターンを長くするあげられる．共通する思想は，グラフパターンに含まれる節点のを止める垂直枝刈りおよび経路パターン内の節点の属性を増が重複しないよう出現数を数えることである．これらの支持度

やすのを止める水平枝刈りの二つの種類を用いる．提案アルゴには 3 つの欠点がある．まず，相対支持度に適応できない点でリズムは支持度，確信度，およびリフトなどのルールの評価尺ある．これは，グラフ内に出現し得る最大のパターン数を求め度を厳密に計算できる．さらに，近似と並列化技術を開発し，るできなことに起因する．次に，時間計算量が大きい点である．

スケーラブルな相関ルールの発見を実現する．近似化では，経

例えば， MIS や MNI は NP 困難である．最後に，グラフパ路パターンの接尾の削減と節点のサンプリングにより計算コス

ターンに含まれる節点と含まれない節点の解釈が困難であり，トを削減する．並列化では，経路パターンを計算に必要な節点

直感的ではない点である．相対支持度を計算可能な技術が提案毎のコストを推定し，コストが均等になるようにスレッドに割されてはいるが，サブグラフマッチングが必要であるため計算

り当てることにより，スレッド間の計算コストを均等にする．

量は大きい [6]．

評価実験では，3 つのグラフにおいて提案アルゴリズムが高速であることを示す．提案技術は厳密解計算において最大で 151
倍高速，近似解計算において微小な精度低下で 485 倍高速可能であることを示す．さらに，経路相関ルールが知識抽出とソーシャル差別確認において有用であることを示す．
再現性．提案手法のコードベースを Github にて公開する 1 ．
我々の知る限り，大規模なグラフに対するグラフ相関ルールマ
イニングにおける初めての公開コードである．

グラフ相関ルールマイニング. グラフ相関ルールマイニングはグラフデータ集合と一つの大規模グラフに対する技術の二つに大別できる．グラフデータ集合に対するアルゴリズム（例えば，[18–21]）は θ 個より大きいグラフに含まれるグラフパター
ンを発見することを目的とするのに対し，一つのグラフデータ
に対するアルゴリズム [6, 7, 9, 22] は θ 回より大きい回数が一つのグラフに出現するグラフパターンを発見することを目的とす
る．非単調性は互いに適用することはできないため，それぞれに使われているアルゴリズムは他方に使用することはできない．
一つの大規模グラフに対するアルゴリズムは少数提案されて1：https://github.com/yuya-s/pathassociationrulemining

いる [6, 7, 9, 22]．我々の知る限り，経路に着目したものや接続表 1: 単一大規模グラフに対するグラフ相関ルールマイニングの比較．V.GX と V.GY はそれぞれ GX と GY に含まれる節点集合を表す．
グラフタイプ
ラベル付き枝GPAR [6]ラベル付き節点

Extending GPAR [7]

単一の枝
もしくは空

出力

V.GY ⊆ V.GX

トップ k 多様パターン

サブグラフ(少なくとも一つの枝を含む) (少なくとも一つの枝を含む) かつ枝の重複無し

ラベル付き枝属性付き節点

属性無しサブグラフ
経路

サブグラフ

GX と GY

属性付き節点
属性付き節点

提案

サブグラフ

GY

ラベル無し枝ラベル付き枝GAR [9]GX

接続している単一の枝
もしくは単一の属性
経路

可能性パターンに適応しているものは存在しない．表 1 に各手法の特徴をまとめる．

GPAR は初めて提案された一つの大規模グラフに対するグラ
フ相関ルールマイニングである [6]．Wang ら [7] は GPAR を拡張し，頻出パターンを取得可能なアルゴリズムを開発した．
その際，条件部や結論部，支持度の計算方法を変更し，検出パターン数が少なるようにしている．Fan らは [9] は節点属性に対応可能なように GPAR を拡張している．応用に着目して結論部を事前に指定し，機械学習を用いて不要な節点や枝をグラフから取り除くことで計算量が小さくなる工夫をしている．他にも時系列グラフ [23] や量的サブグラフ [8] に GPAR を拡張

頻出パターン

V.GX ⊆ V.GY

応用を指定した頻出パターン

始点が共通

頻出パターン

3. 2 経路相関ルール
経路パターンを定義した後に，経路相関ルールマイニングについて説明する．
経路パターン．単純経路パターンと到達可能性経路パターンの

2 つを定義する．
•

単純経路パターンは節点属性 Ai ⊆ A の集合枝ラベルℓi ∈ L のシーケンス ⟨A0 , ℓ0 , A1 , . . . , ℓn−1 , An ⟩ で表現される．
節点 v と単純経路パターン p が与えられたとき，もし v が全ての i に対して Ai⊆A(vi ) および ℓi=ℓei を満たす経路の始点であるならば，v は p に適合するとする．

•

接続可能性経路パターンは 2 つの属性集合 A0 , A1 ⊆ A

した技術も開発されている．

および枝ラベル ℓ∗ ∈ L のトリプルである ⟨A0 , ℓ∗ , A1 ⟩ で表現さ他のルール検出技術．グラフからルールを検出技術は多く開発される．節点 v と接続可能性経路パターン p が与えられたとき，れており，例えばグラフ関数従属性 [24] や Horn ルール [25,26]

もし v が A0 ⊆ A(v0 ), A1 ⊆ A(vn ) および ℓi =ℓei を満たす経が挙げられる．Horn ルールは RDF データにおいて，条件部

路の始点であるならば，v は p に適合するとする．

が経路で，結論部が条件部に含まれる節点間の単一の枝となる

V(p) および |V(p)| は経路パターン p に適合する節点集合おルールである．これらの技術は一般的なプロパティグラフではよびその数をそれぞれ表す．経路パターン内の A は少なくとも使用できない．

一つの要素が入っているものとする．全ての属性集合が一つのサブシーケンスマイニング [27–31] は，シーケンス内のサブ要素のみを含む経路パターンを単位経路パターンと呼ぶ．

シーケンスパターンの規則を発見する技術である．このマイニ
ングは，グラフが経路グラフの場合におけるグラフ相関ルール
であり，特殊例としていうことができるが，複雑なグラフには適用できない．

定義 1 (支配)二つの経路パターン p′⟨A′0 ,ℓ′0 , A′1 ,=⟨A0 , ℓ0 , A1 ,. . . , ℓ′m−1 , A′m ⟩ が与. . . , ℓn−1 , An ⟩ および p =えられたとき，m <= n, かつ 0 から m までの全て i においてℓ′i = ℓi と A′i ⊆ Ai が成り立つならば，p は p′ を支配している

3 経路相関ルールマイニング
本章では，経路相関ルールマイニングを提案する．経路相関という．p′ ⊂ p は p′ が p に支配されていることを表す．
直感的には，支配している経路パターンは支配されている経

ルールマイニングは効果的に節点属性と枝ラベルのシーケンス

路パターンより複雑であることを示す．

間の規則性を発見することができる．

経路相関ルール．経路相関ルールを以下と定義する．

3. 1 表定義 2

記

経路相関ルール r は pX ⇒ pY で定義され，pX と pYグラフを G = (V, E, L, A) とし，V は節点集合，E ⊂ V ×L×V

は経路パターンを表す．pX と pY をそれぞれ条件部と結論部

は枝ラベル ℓ ∈ L, L を伴う枝集合，および A は属性集合を表と呼ぶ．節点が pX と pY 両方に適合する場合，r に適合する

す．枝 e ∈ E は (v, ℓe , v ′ ) と表し，枝ラベル ℓe を伴う節点 v か

と呼ぶ．

′

ら節点 v とする．属性 a ∈ A はカテゴリカルな値とし，節点の特徴を表す．A ⊆ A は属性の集合とし，それぞれの節点 v ∈ V
は属性集合 A(v) をもつ．
経路は節点と枝のシーケンスとし，s ⟨v0 , e0 , v1 , . . . , en−1 , vn ⟩と表記する．n は経路長であり，v0 と vn をそれぞれ始点と終点とする．

経路相関ルールは頻出性や条件付確率を評価することができる．ここで，経路相関ルールにおいてはホモモフィズムとする
ため，一つの経路が pX と pY を共有していてもよい．

3. 3 相関ルールの指標
経路相関ルールは一般的な相関ルールの指標を計算可能である．支持度，確信度，リフトは既存の定義から自然に計算可能ルールよりも一般化されている．各節点と属性はトランザク

である．

ションとアイテム集合とそれぞれ見做すことができ，枝が存在

支持度: 支持度はどの程度の節点が経路相関ルールに適合してしないグラフでは経路相関ルールマイニングはアイテムセット

いるかを表す．絶対支持度と相対支持度の両方を下記で示す．

に対する相関ルールと等価である．

ここで，多くのグラフ相関ルールマイニングは相対支持度を計算できない．これは，適合し得る最大のグラフパターン数の計算が困難なためである．

4 アルゴリズム
本章では，経路相関ルールマイニングのための効率的なアル

絶対支持度は下記となる．

ゴリズムについて述べる．経路相関ルールマイニング問題を解くためには，頻出経路パターンとそれらに適合する節点集合を

ASupp(pX ⇒ pY ) = |V(pX ) ∩ V(pY )|.

列挙する必要がある．経路パターンの候補を削減するために，|V(p)| の最大となりうる値は節点数となるため，相対支持度は以下で計算できる．

がら複雑な経路パターンの候補を生成する．

|V(pX ) ∩ V(pY )|RSupp(pX ⇒ pY ) =.
|V|

4. 1 非単調性性質

確信度: 確信度は節点が pX に適合する場合に pY が適合する確率を表す．確信度は以下の式で計算できる．

Conf (pX ⇒ pY ) =|V(pX ) ∩ V(pY )|.
|V(pX )|

非単調性性質は経路パターンの候補の削減に効果的に活用できる．経路パターンの非単調性性質は下記となる．
定理 2

リフト: リフトは相対支持度と同様に多くのグラフ不相関ルー
ルマイニングで計算できない指標である．リフトは下記の式で計算できる．

Lift(pX ⇒ pY ) =頻出な単位経路パターンをはじめに列挙し，非単調性を用いなもし p′ ⊂ p ならば，V(p′ ) ⊇ V(p) である.

上記の定理から下記 2 つの補題を導出できる．
補題 1

経路パターンのプリフィックスが頻出ではないなら，

経路パターン全体も頻出ではない．

|V(pX ) ∩ V(pY )| · |V|.
|V(pX )| · |V(pY )|補題 2

もし p が頻出ではない，かつ p′ が全ての i に対して

その他: 上記と同様の方法で，他の指標も定義できる．

A′i ⊇ Ai と ℓ′i = ℓi を満たすならば，p′ は頻出ではない．

3. 4 問 題 定 義

これらの定理と補題は頻出になりえない経路パターンの枝刈りを可能とする．

本稿で解く問題を下記で定義する．
定義 3 (経路相関ルールマイニング問題)

グラフ G ，
（絶対もしくは相対）支持度の最小値 θ，最大経路長 k が与えられたとき，経路相関ルールマイニング問題は 3 つの条件 (1) supp(r)が θ より大きい， (2) 経路長の最大値が k, かつ (3) pX および pY はそれぞれ互いに支配されないを満たす全ての r と r の指標を計算する．|V(p)| > θ を満たす経路パターンを頻出経路パターンと呼ぶ．

4. 2 ベースラインアルゴリズム
ベースラインアルゴリズムは 4 つの処理手順 (1) 頻出属性集
合発見，(2) 頻出単純経路パターン発見，(3) 頻出接続可能性
経路パターン発見，および (4) ルール発見で構成される．それぞれの処理手順で補題 1 を活用し，候補の削減を行う．それぞれについて以下で説明する．
（ 1 ） 頻出属性集合発見. 頻出属性集合の集合 P0（長さ 0 の頻出経路パターン）を求める．この処理は，アプリオリ手法な

この問題定義や経路パターンは応用に合わせて柔軟に変更でど既存の相関ルールマイニング技術を活用する．

きる．例えば，(3) の支配関係の条件を外すことや，経路パター（ 2 ） 頻出単純経路パターン発見. この処理手順では，既にン内の節点が空集合であることを許可するなどがあげられる．

発見した頻出経路パターンを拡張することで頻出単純経路パターンを発見する．長さ i の単純経路パターンの候補を経路パ定理 1

経路相関ルールマイニング問題は NP 困難である．

ターン p ∈ Pi−1 ，枝ラベル，および A ⊆ A を組合わせるこ

簡易証明: 経路相関ルールマイニングを NP 困難問題のひとつである頻出サブシーケンス列挙問題 [32] に還元することで証明する．シーケンスおよびサブシーケンスは，それぞれグラフ
および経路パターンのサブクラスである．そのため，経路相関
ルールマイニングを解ければ，頻出サブシーケンス列挙問題も解くことができる．したがって，経路相関ルールマイニングはNP 困難である．

□

特徴. 経路相関ルールはアイテムセットに対する一般的な相関とで生成する．もし経路パターンが頻出であれば，その経路パターンを Pi に格納する．経路長が k となるまで繰り返す．
（ 3 ） 頻出接続可能性経路パターン発見. この処理手順では接続可能性経路パターンに適合する節点を探索する．頻出単純経路パターンの発見と異なる点は，各節点から ℓ∗ を伴う枝のみを通って到達可能な節点集合を求める必要がある点である．
枝ラベルが与えられたとき，各節点から到達可能な節点集合
を幅優先探索で列挙する．その後，頻出単純経路パターンの発見と同様に，経路パターン p ∈ P0 ，枝ラベル，および A ⊆ A

いる経路が頻出ではない経路パターン，および (3) 頻出経路パを組合わせることで候補を生成し，そのパターンが頻出であれターンに係らないサフィックスによって，経路パターン候補をば P ∗ に格納する．

削減できる．最適化された候補生成では，二つの方法により経（ 4 ） ルール発見. ルール発見の処理では，二つの頻出経路

路パターンを拡張する．垂直型拡張は，ベースラインと同様にパターンに適合する節点を探索する．手順 (2) と (3) で発見し経路パターンの経路長を長くする拡張であり，水平型拡張は経た頻出経路パターン p と p′ に対して，候補ルール p ⇒ p′ と路パターン内の属性集合を大きくする拡張である．候補から枝′p ⇒ p を生成し，両方に適合する節点数を数える．最後に，頻刈りされた経路パターンは頻出とはなりえないため，精度が劣出であるルールの指標を計算する．

化することは無い．

ベースラインアルゴリズムは補題 1 を用いて候補数を削減す提案アルゴリズムを候補生成の最適化に基づいて拡張する．

ることができる．しかし，経路パターンとルールの候補数は未頻出属性集合発見において，LF と AT を求める．LF と ATだ膨大であるため，さらなる候補の削減が必要とされる．

は，全ての枝ラベルに対して AT ，その後 LF ，最後に AT を

4. 3 最適化手法
ベースラインアルゴリズムをさらに経路パターンとルールの候補を削減することにより高速化する．サフィックス削減を導入し，さらに，候補生成を最適化する手法を開発する．
サフィックス削減．非単調性性質は頻出にならない経路パター
ンのプリフィックスを削減できるが，サフィックスを削減する
ことはできない．そこで，サフィックス削減を提案する．

LF により再計算することで求める．単純経路パターン発見では，長さ 1 の単位経路パターンを発見し，そこから LF と AFをサフィックスに追加することで垂直型拡張を行う．垂直型拡張では二つの頻出経路パターンを統合し，経路パターン内の属性を増やしていく．接続性経路パターンでも同様に，補題 2 を用いて水平型拡張を実施する．
ルール発見では，補題 1 と補題 2 を用いて単位経路パターンからなるルールをまず発見し，頻出ルール内の経路パターンを

枝ラベル ℓ と属性 a が与えられたとき，経路長 n − 1 の任意

垂直型および水平型拡張する．具体的には，p ⇒ p′ が頻出であの経路パターンに ℓ と A が結合した場合の最大適合節点数を計るならば，pv ⇒ p′ , ph ⇒ p′ , p ⇒ p′v , および p ⇒ p′h をルール

算する．加えて，枝ラベル ℓ と属性 a が与えられたとき，任意の候補として逐次生成していく．pv と ph はそれぞれ p から垂長の経路パターン ⟨A, ℓ, . . .⟩ に適合する最大の節点数を計算す

直型と水平型拡張したものを表す．

る．これらの最大節点数が θ 以下の場合，サフィックスを削減できる．

5 近似手法

二つの値を定義する．一つ目は，節点集合 A をもち枝ラベ
ル ℓ の出次枝をもつ節点の数を |V(A, ℓ)| = |{v|(v, ℓe , v ′ ) ∈E ∧ A(v) ⊇ A ∧ ℓe = ℓ}| ととする．二つ目は枝ラベル ℓ をもち属性集合 A をもつ節点に接続する枝の数を |E(A, ℓ)| =|{(v, ℓe , v ′ )|(v, ℓe , v ′ ) ∈ E ∧ A(v ′ ) ⊇ A ∧ ℓe = ℓ}| とする．最大の適合節点数は下記の補題となる．
補題 3

経路長 n, 枝ラベル ℓ, および属性集合 A が与えられたとき, 長さ n − 1 の経路パターンに ℓ と A を結合した経路パターンに適合する最大の節点数は |E(A, ℓ)| · (dm )n−1 である．

dm は全ての節点における最大入次数を表す．

提案アルゴリズムは候補集合を効果的に削減することができるためベースラインと比べて高速な実行が可能である．しかし，候補集合は未だ膨大となるため，大規模グラフに対してスケー
ラブルとはいえない．そこで，近似手法として，候補削減と節点サンプリングを開発する．

5. 1 候 補 削 減最適化手法は補題 3 に基づいた候補枝刈りにより候補集合を削減できる．サフィックス削減は精度の低下しないことを目的としてるため，頻出集合に入らないサフィックスも多く残ってしまう．スケーラブルなマイニングのために，頻出集合に含ま

枝ラベル ℓ および属性集合 A が与えられたとき，経れない可能性が高いサフィックスを削減する技術を提案する．

路パターン p = ⟨A, ℓ, . . .⟩ is |V(A, ℓ)| に適合する最大節点数は補題 3 に基づいたサフィックス候補を近似化する．候補削

補題 4|V(A, ℓ)| である．
上記の補題より，経路パターンの候補生成時の枝ラベルと節点集合を削除できる．初めに，|E(A, ℓ)|·dm n−1 > θ を満たす場合，(A, ℓ) のペアは経路長 n − 1 のサフィックス ⟨n, An ⟩ となりうる．
次に，ℓ が全ての A に対して min(|V(A, ℓ)|, |E(A, ℓ)|·dm k−1 ) <=θ を満たさない場合，ℓ は経路パターンにおける ℓ0 および ℓ∗になりうる．サフィックスとなりうる枝ラベル集合と属性集合をそれぞれ LF と AT する．サフィックス枝刈りは経路パター

減パラメータ ψ (0.0 <= ψ <= 1.0) が与えられたとき，もし|L(A, ℓ)| · (dm )ψ(n−1) が θ を超えないなら，サフィックス ⟨ℓ, A⟩を候補から削除する．多くの節点は最大次数より小さい次数であるため，精度への影響を小さく削減することができる．
定理 3 頻出経路集合 p が与えられたとき, p が欠損する確率()|V(p)|(dm )ψ(n−1)
はP θ>である．Pm は p が節点に適合す=
P (d )n−1mpる確率，dp は p に適合する経路における経路上の節点の平均
出次数を表す．

ン長を伸ばす際の候補生成削減に有効である．
候補生成の最適化．非単調性性質とサフィックス枝刈りにより，(1) プリフィックスが頻出ではない経路パターン，(2) 支配してこの定理により，|V(p)| が大きい，最大次数と実際に経路パターン上の節点との差が大きい場合に，欠損する確率が下がる．

大規模グラフはこのような特徴をもつことが多いため効果的で

表 2: データ統計ある．この近似は偽陽性なしの近似化であるため，非頻出な経路ルールがマイニング結果に入ることはない．

|V|

|E|

|L|

|A|

Avg. |A(v)|46,682

231,634 821

266

1.5

DBpedia 1,477,796

2,920,168 504

239

2.7

9 36302

1.1

Nell

5. 2 節点サンプリング

Pokec

1,666,426 34,817,514

サンプリングはデータマイニングの近似化に頻繁に使われる技術である [9, 33–35]．提案する近似化手法は，経路相関ルー
ルマイニングの特徴に合わせて，始点として計算する節点をサ

7. 1 実 験 設 定
データセット. 枝ラベルと節点属性を含む 3 つのグラフデー

ンプリングすることで，計算コストを削減する．
サンプリングとして，節点の属性集合に応じた層化サンプリ

タ Nell [37] 2 , DBpedia [38] 3 , および Pokec 4 を用いる．表 2 にングを用いる [36]．まず頻出属性をもたない節点は排除する．

データの統計を示す．

次に，節点を属性毎にグループ化し，サンプリング率 ρ でグ比較手法. Baseline は最適化手法を用いないアルゴリズム，

ループ毎に節点を選択する．経路パターン p は下記の式で推論

Ours は近似手法を用いない提案アルゴリズムを示す．Ours w/

する．

CR および Ours w/ SA は候補削減と節点サンプリングをそれ^ = |Vs (p)| .
|V(p)|
ρ(1)

ぞれの近似手法用いた提案手法，Ours w/ CR+SA は両方の近似手法を用いた提案手法を示す．全ての手法で並列化手法を用

Vs はサンプリングされた節点集合を表す．
候補削減と比べて，サンプリングは偽陽性を含む可能性がある．一方で，候補削減が機能しない場合でも計算コストを削減

いて並列実行する．ここで，既存手法は経路相関ルールマイニ
ングに適用できないため比較手法として用いない [6, 7, 9, 22]．
パラメータ. 評価実験におけるデフォルトパラメータを述べる．

することができる．

最小支持度として，絶対支持度を用いて Nell，DBpedia，および Pokec において，それぞれ 1,000，120,000，および 45,000

6 並 列 化とする．近似手法のパラメータである ψ と ρ を 0.4 とする．最提案アルゴリズムは並列化により高速化可能である．我々の並列化は，スレッド毎に計算コストが均等となるように節点を分配し，スレッド間の計算コストの均等化を目指す．各節点は大経路長 k は 2 とし，32 スレッドを用いて並列化する．絶対支持度，相対支持度，確信度，およびリフトを指標として計算する．

属集合と枝をもち，それぞれが頻出なものと頻出ではないものが存在する．もし多くの頻出な属性と枝をもつ節点が偏ったス
レッドに配置された場合，そのスレッドの計算コストが大きくなり，全体として実行時間が長くなってしまう．

7. 2 効 率 性
まず，パラメータを変化させ，提案手法の効率性を評価する．
最小支持度 θ の影響．最小支持度は発見するルールに影響する．

コストベースのパーティショニングとして，スレッド数 N が最小支持度が減少すると発見ルール数が増加し，結果として計与えられたときに，節点毎に計算コストを見積もり，計算コス算コストが大きくなる．図 2 にそれぞれのデータにおいて最小

トの合計値が等しくなるように N グループに節点を分割する．

支持度を変化させた場合の実行時間を示す．最小支持度が減少

コストの見積もりは下記の式で行う．

するにつれて，全ての手法で実行時間が長くなる．提案手法はC(v) = dF (v) · |AF (v)|(2)

ベースラインと比較して高速である．特に，Pokec において，属性数が多いためベースラインは支持度が大きくても実行が 24

dF (v) および |AF (v)| は節点 v のそれぞれ頻出な枝ラベルの出時間以内に終了しなかった．経路パターンの候補を効果的に削次数および頻出な属性数を表す．

減することにより，提案手法が効率化されていることがわかる．

節点の分割では貪欲法を用いて計算する．節点をコスト毎に近似手法はさらに計算コストを削減できる．近似手法におい降順で並び替え，順に割当てられた節点のコストが最も小さいて，候補削減は候補サイズの削減，節点サンプリングは計算対スレッドに割り当てていく．この並列化では，コストの見積も象となる節点数の削減という，時間計算量において異なる項目

りに O(|V|)，節点の分割に O(N |V| log |V|) 係る．計算コストを削減する．そのため，両方を用いた場合に片方を用いる場合が非常に小さいため，大規模グラフにおいて有効である．

よりも十分に計算コストを削減できる．それぞれの近似手法を比べると，候補削減の方が効果的である．これは，経路パター

7 評価実験
評価実験では，提案アルゴリズムの効率性，近似手法の精度，
および経路相関ルールマイニングの効果を検証する．全てのアルゴリズムは C++で実装し，512GB のメモリおよび Intel(R)ン候補の方が節点に比べて大きいためである．
スレッド数の影響．提案アルゴリズムは並列処理可能であるため，スレッド数が多くなればなるほど実行時間が減少する．表3 にスレッド数を変化させた場合の実行時間を示す．厳密およXeon(R) CPU E5-2699v3 を搭載する Linux 計算機にて実験

2：https://github.com/GemsLab/KGist/blob/master/data/nell.zipを行う．

3：https://github.com/GemsLab/KGist/blob/master/data/dbpedia.zip
4：https://snap.stanford.edu/data/soc-pokec.html

2000

Run time [sec]Run time [sec]100000Ours
Ours w/ CR.
Ours w/ SA .
Ours w/ CR+SA .
Baseline.

2500
1500
1000
500
0
1400

1200
1000
800
Minimum support

10000

Ours
Ours w/ CR.
Ours w/ SA .
Ours w/ CR+SA .
Baseline.

80000
60000

Run time [sec]

3000

40000
20000
0
160000 140000 120000 100000 80000
Minimum support

600(a) Nell(b) DBpedia

8000
6000

Ours
Ours w/ CR.
Ours w/ SA .
Ours w/ CR+SA .
Baseline.

4000
2000
0
55000

50000 45000 40000
Minimum support

45000(c) Pokec

図 2: 最小支持度 θ の実行時間への影響．24 時間以内に終了した点のみをプロットする．

合，効果的とはいえない．そこで，近似手法の精度を評価する．

表 3: スレッド数の実行時間への影響 [sec]DatasetNumber of threads

Method
Ours

Nell

8

16

32

表 5 にそれぞれのデータセットにおける近似手法の再現率と

754.6

496.2

348.7

適合率を示す．DBpedia と Pokec では，近似制度が非常に高

74.0

63.2

51.7

い一方で，Nell では候補削減の再現率が低い．Nell では，最大

Ours

59,603 29,971 15,028

次数と経路パターンに関連する次数の差が小さいため，候補削

Ours w/ CR+SA

6,037

3,042

1,529

減における欠損する確率が高い．提案する近似手法はグラフサ

Ours

10,039

6,197

4,038

イズが大きい場合において特に有効であることがわかる．

Ours w/ CR+SA

1,981

1,103

634

Ours w/ CR+SA

DBpedia
Pokec

精度の評価では，厳密解と比較して再現率と適合率を用いる．

7. 4 有 用 性
最後に，経路相関ルールの有用性について検証する．経路相

表 4: メモリ使用量 [GB]Nell DBpedia Pokec

関ルールは特定の応用タスクを想定しないため，定量的な評価

Ours

11.1

23.9

6.4

として Pokec のバイアス評価を示す．

Ours w/ CR

4.2

21.5

6.4

経 路 相 関 ル ー ル を 用 い て Pokec 内 の バ イ ア ス と し て 友

Ours w/ SA

5.6

23.8

6.1

人 の 学 歴 が 性 別 間 で 異 な る か を 検 証 す る ．具 体 的 に は ，Ours w/ CR+SA

2.4

21.5

6.1

⟨{gender}⟩ ⇒ ⟨{}, follows, {education:A}⟩ のルールにおいて，男性と女性間で検出される数が異なるかを調べる．gender

表 5: 精度
Nellと education:A は性別および学歴に関する節点属性を表す．こDBpedia

Pokecのテンプレートに関する経路相関ルールを 767 件検出した．男

再現率

適合率

再現率

適合率

再現率

適合率

CR

0.233

1.0

1.0

1.0

1.0

1.0

性/女性毎の絶対支持度の総和はそれぞれ 464,725 と 466,725

SA

0.9999

0.999

1.0

1.0

0.967

0.983

であり，確信度の総和はそれぞれ 2.445 と 2.064 である．男性

CR+SA

0.233

0.998

1.0

1.0

0.967

0.983

と女性のそれぞれの節点数はそれぞれ 464,725 と 466,725 であり，女性の方が多い．それにも関わらず，絶対支持度がほぼ同び近似アルゴリズムの両方で，線形に実行時間が減少している

等かつ確信度が男性の方が大きいため，男性の友人の方がよりことがわかる．これより，提案アルゴリズムはスケーラブルに学歴を登録していることが多いといえる．そのため，Pokec に

経路相関ルールを発見できることが確認できる．

は性別間で学歴に関するバイアスがあるといえる．

メモリ使用量. 表 4 に提案アルゴリズムのメモリ使用量を示す．

DBpedia が最大のメモリ使用量，Pokec が最小のメモリ使用量となっている．このことから，グラフサイズより候補集合のサイズや，発見した頻出経路パターン数とルール数がメモリ使用量に大きく影響することがわかる．近似手法はメモリ使用量も削減できている．候補削減では候補数を，サンプリングでは経路パターンを格納する節点数が削減している．Nell のように経路パターン数が大きいグラフにおいて，近似手法がメモリ使用量の観点で有効であることがわかる．

7. 3 精度

近似手法は実行時間が短くなるが，精度が低くなりすぎる場

8 ま と め
本稿では，新しいコンセプトとして経路相関ルールマイニン
グを提案した．経路相関ルールマイニングでは，ひとつの大規模グラフから経路間の規則の発見を可能とする．さらに，効率かつスケーラブルなアルゴリズムを開発した．評価実験において，3 つの実グラフを用いて経路相関ルールの有用であること，
および提案アルゴリズムが効率的かつ高精度であることを確認した．
本研究はいくつかの拡張の方向性を残している．まず一つ目
は，頻出なルール検出ではなく，経路パターンの特徴を捉えることができる新たな評価指標を定義し，上位 k 件のルールを発見するように拡張することである．次に，経路パターン自体を拡張し，例えば，属性が空の経路や終点節点が同一であるようなルールの発見が考えられる．最後に，提案アルゴリズムは非頻出な経路パターンの計算が必要な指標（例えば，χ2 ）を計算することができないため，後処理を追加することでより多様な指標に対応することが考えられる．

謝辞

本研究は JSPS 科学研究費 JP17H06099 および JP20H00584の支援によって行われた．
文

献[1] Rakesh Agrawal, Tomasz Imieliński, and Arun Swami.
Mining association rules between sets of items in large
databases. In SIGMOD, pp. 207–216, 1993.
[2] Qiankun Zhao and Sourav S Bhowmick. Association rulemining: A survey. Nanyang Technological University, 2003.
[3] Manpreet Kaur and Shivani Kang. Market basket analysis:
Identify the changing trends of market data using association rule mining. Procedia computer science, Vol. 85, pp.
78–85, 2016.
[4] C-H Lee, Y-H Kim, and P-K Rhee. Web personalization expert with combining collaborative ﬁltering and association
rule mining technique. Expert Systems with Applications,Vol. 21, No. 3, pp. 131–137, 2001.
[5] Saurav Mallik, Anirban Mukhopadhyay, and Ujjwal Maulik.
Ranwar: rank-based weighted association rule mining fromgene expression and methylation data. IEEE transactions
on nanobioscience, Vol. 14, No. 1, pp. 59–66, 2014.
[6] Wenfei Fan, Xin Wang, Yinghui Wu, and Jingbo Xu. Association rules with graph patterns. PVLDB, Vol. 8, No. 12,
pp. 1502–1513, 2015.
[7] Xin Wang, Yang Xu, and Huayi Zhan. Extending association rules with graph patterns. Expert Systems with Applications, Vol. 141, p. 112897, 2020.
[8] Wenfei Fan, Yinghui Wu, and Jingbo Xu. Adding counting
quantiﬁers to graph patterns. In SIGMOD, pp. 1215–1230,
2016.
[9] Wenfei Fan, Wenzhi Fu, Ruochun Jin, Ping Lu, andChao Tian. Discovering association rules from big graphs.
PVLDB, Vol. 15, No. 7, pp. 1479–1492, 2022.
[10] James S House, Karl R Landis, and Debra Umberson. Social relationships and health. Science, Vol. 241, No. 4865,
pp. 540–545, 1988.
[11] Max Haller and Markus Hadler. How social relations andstructures can produce happiness and unhappiness: An international comparative analysis. Social indicators research,
Vol. 75, No. 2, pp. 169–216, 2006.
[12] Jeﬀrey Dastin. Rpt-insight-amazon scraps secret ai recruiting tool that showed bias against women. Reuters, 2018.
[13] Joseph Fisher, Dave Palfrey, Christos Christodoulopoulos,
and Arpit Mittal. Measuring social bias in knowledge graphembeddings. arXiv preprint arXiv:1912.02761, 2019.
[14] Natalia Vanetik, Ehud Gudes, and Solomon Eyal Shimony.
Computing frequent graph patterns from semistructured
data. In ICDM, pp. 458–465, 2002.
[15] Björn Bringmann and Siegfried Nijssen. What is frequent
in a single graph? In PAKDD, pp. 858–863, 2008.
[16] Toon Calders, Jan Ramon, and Dries Van Dyck. Antimonotonic overlap-graph support measures. In ICDM, pp.
73–82, 2008.
[17] Jinghan Meng and Yi-cheng Tu. Flexible and feasible support measures for mining frequent patterns in large labeledgraphs. In SIGMOD, pp. 391–402, 2017.

[18] Akihiro Inokuchi, Takashi Washio, and Hiroshi Motoda. An
apriori-based algorithm for mining frequent substructuresfrom graph data. In PKDD, pp. 13–23.
[19] Yiping Ke, James Cheng, and Jeﬀrey Xu Yu. Eﬃcient discovery of frequent correlated subgraph pairs. In ICDM, pp.
239–248, 2009.
[20] Xifeng Yan and Jiawei Han. gspan: Graph-based substructure pattern mining. In ICDM, pp. 721–724, 2002.
[21] Md Samiullah, Chowdhury Farhan Ahmed, Anna Fariha,
Md Raﬁqul Islam, and Nicolas Lachiche. Mining frequentcorrelated graphs with a new measure. Expert systems withapplications, Vol. 41, No. 4, pp. 1847–1863, 2014.
[22] Wenfei Fan and Chunming Hu. Big graph analyses: Fromqueries to dependencies and association rules. Data Scienceand Engineering, Vol. 2, No. 1, pp. 36–55, 2017.
[23] Mohammad Hossein Namaki, Yinghui Wu, Qi Song, Peng
Lin, and Tingjian Ge. Discovering graph temporal association rules. In CIKM, pp. 1697–1706, 2017.
[24] Wenfei Fan, Chunming Hu, Xueli Liu, and Ping Lu. Discovering graph functional dependencies. TODS, Vol. 45, No. 3,
pp. 1–42, 2020.
[25] Frank Manola, Eric Miller, Brian McBride, et al. Rdf
primer. W3C recommendation, Vol. 10, No. 1-107, p. 6,
2004.
[26] Christoph Schmitz, Andreas Hotho, Robert Jäschke, andGerd Stumme. Mining association rules in folksonomies. In
Data science and classiﬁcation, pp. 261–270. 2006.
[27] Rakesh Agrawal and Ramakrishnan Srikant. Mining sequential patterns. In Proceedings of the eleventh international
conference on data engineering, pp. 3–14, 1995.
[28] Mohammed Javeed Zaki, Neal Lesh, and Mitsunori Ogihara.
Planmine: Sequence mining for plan failures. In KDD, pp.
369–373, 1998.
[29] Sebastian Nowozin, Gokhan Bakir, and Koji Tsuda. Discriminative subsequence mining for action classiﬁcation. In
ICCV, pp. 1–8, 2007.
[30] Philippe Fournier-Viger, Cheng-Wei Wu, Vincent S Tseng,Longbing Cao, and Roger Nkambou. Mining partiallyordered sequential rules common to multiple sequences.
TKDE, Vol. 27, No. 8, pp. 2203–2216, 2015.
[31] Philippe Fournier-Viger, Ted Gueniche, Souleymane Zida,
and Vincent S Tseng. Erminer: sequential rule mining using
equivalence classes. In International Symposium on Intelligent Data Analysis, pp. 108–119, 2014.
[32] Guizhen Yang. The complexity of mining maximal frequent
itemsets and maximal frequent patterns. In KDD, pp. 344–
353, 2004.
[33] Sau Dan Lee, David W Cheung, and Ben Kao. Is sampling useful in data mining? a case in the maintenance of
discovered association rules. Data Mining and Knowledge
Discovery, Vol. 2, No. 3, pp. 233–262, 1998.
[34] Hannu Toivonen, et al. Sampling large databases for association rules. In VLDB, Vol. 96, pp. 134–145, 1996.
[35] Wenfei Fan, Ziyan Han, Yaoshu Wang, and Min Xie. Parallel rule discovery from large datasets by sampling. In SIGMOD, pp. 384–398, 2022.
[36] S Thompson. Sampling. Wiley, 2002.
[37] Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Settles, Estevam R Hruschka, and Tom M Mitchell. Toward anarchitecture for never-ending language learning. In AAAI,
pp. 1306–1313, 2010.
[38] Sören Auer, Christian Bizer, Georgi Kobilarov, Jens
Lehmann, Richard Cyganiak, and Zachary Ives. Dbpedia:
A nucleus for a web of open data. In The semantic web, pp.
722–735. 2007.