DEIM Forum 2021 A24-4

コミュニティ構造を制御する属性付きグラフ生成前川 政司†

佐々木勇和†

George Fletcher††鬼塚真†† 大阪大学大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1–5†† Eindhoven University of Technology, 5612 AZ Eindhoven, Netherlands
E-mail: †{maekawa.seiji,sasaki,onizuka}@ist.osaka-u.ac.jp, ††g.h.l.ﬂetcher@tue.nl
あらまし

実世界のグラフ持つ特徴を示す大規模な正解ラベル付きの人工グラフ生成は，グラフインデッ

クスやマイニングタスクの評価に必要とされている．本稿では，コミュニティ構造を制御する属性付きグ
ラフ生成器である acMark を提案する．acMark の利点は以下の三つである．(i) acMark はユーザが指定したグラフ特徴を持つグラフを生成する．(ii) ユーザはノードとクラスの間の接続割合を柔軟に制御することができる．(iii) グラフ生成はエッジ数に対して線形時間で実行可能である．acMark はこれらの利点を全て有する最初の生成器である．多様な実験を通して，acMark が効率的にユーザが制御可能なクラス構造を持つ属性付きグラフを生成できることを示した．
キーワード 属性付きグラフ, ベンチマーク, コミュニティ

1 はじめに実世界のグラフデータでは多くの場合, ノードが属性を持っている（e.g., ウェブグラフのノードはテキスト情報を保持している）. 属性付きグラフのための分析手法は広く研究されており，クラスタリング手法 [4], [21] やノード分類手法 [3], [12] などが挙げられる．
研究者たちは自身の設計した手法を評価するために, 大規模かつ多様なデータセットを必要としている. グラフ
データのアーカイブとして広く知られている SNAP [15]において多くの実データが利用可能であるが，多くの場
合コミュニティの正解（ノードのコミュニティへの割当，

図 1: ノードの色はそのノードの所属クラスを意味する．
各クラス内のノードは似た属性を持つ．赤枠，青枠はそ
れぞれ homophily プロパティを持つクラスに属するノードおよび heterophily プロパティを持つクラスに属するノードを示している．

本稿ではラベルと呼ぶ）は付与されていない上に小規模各ノードが複数のクラスにいくぶんかの割合で所属する 1

なデータである．そのため，手法の評価のために十分なと仮定し，その割合をノード-クラス所属プロポーショ量のデータを集めることは困難である．

ンと呼ぶ．Core ノードは所属するクラスに対して大きな以上の議論から，実グラフが持つ多様な特性を示し，値を持ち，border ノードは複数のクラスに対して大きな正解ラベルを持つ属性付きグラフを生成することは重要値を持つ．

である．ウェブグラフやソーシャルグラフが持つ主要な

Homophily/heterophily. 実グラフの現象として ho-構造の特徴として，スモールワールド性やべき乗則に従mophily はよく知られており，同じクラスに属するノー

うノード次数分布がある．構造と属性の両方に関しては，

ドが互いに接続する可能性が高い傾向がある現象である．

属性付きグラフの基礎的な現象である core/border とまた，homophily がコミュニティ構造に影響を与えている

homophily/heterophily に注目する．

ことが知られている [16]．コミュニティによっては似ていCore/border. 最初に属性の観点から，似た属性を持つない属性を持つノードを内包するものがあり，この現象はノードの集合としてクラスを導入する．クラスの中には，

heterophily と呼ばれている．それは homophily の反対のcore と border の二種類のノードが存在する [8]．Core

概念であり，異なる属性を持つノードに接続する傾向があ

ノードは所属するクラスのノードが持つ属性の平均と似ることを意味する．図 1 において homophily/heterophily

た属性の値を持つノードである．一方，border ノードはの直感的な説明を示す．homophily/heterophily プロパ

複数のクラスの属性を混ぜ合わせた属性の値を持つノー

ティの両方をサポートするために，ノードとクラスの接ドである．これらの core/border の現象を捉えるために，
1：クラスラベルは各ノードが最も強く所属しているクラスを表す．

続割合を表すノード-クラス接続プロポーションを導入す

X ∈ Rn×d ，クラスラベル C ∈ {1, . . . , k}n から構成さる．それは homophily プロパティを持つクラスでは，クれる．ここでの n, d, k はそれぞれノード数，属性数，ク

ラス内のノードは互いに接続する傾向があるため，ノーラス数を表す．

ド-クラス所属プロポーションと一致し，heterophily プ

この章では，グラフ生成器がサポートすべき特徴であロパティを持つクラスでは反転した値を持つ．これらるグラフ特徴とクラス特徴について述べる．その後，取のノードレベルでのプロポーションは，core/border やり組む問題の厳密な定義を与え，最後にグラフ生成のた

homophily/heterophily などの現象を掴み，クラスレベ

めに解く必要がある技術的な課題について説明する．

ルの接続割合よりも粒度の細かい表現を可能にする．
既存研究．グラフ生成器はノード-クラス所属プロポー
ションをサポートする必要があるが，多くの手法はクラス構造を考慮して設計されていない [1], [19]．コミュニ

2. 1 グラフ特徴
グラフ生成器がサポートするべき実グラフが持つ典型的な二つの特徴である構造特徴と属性特徴を導入する．

ティ推定のために設計された手法として LFR [13]，DC-

構造特徴．ソーシャルグラフが持つ広く知られた構造特

SBM [10]，ANC [2], [14] が提案されている．しかし，こ徴として，ノード次数分布がべき乗分布従うことが挙げ

れらの手法はクラス内のノードに対して全てが同じノーられる [17]．そのため，グラフ生成器はノード次数におド-クラス所属プロポーションを持つと仮定しているた

いて多様な分布を選択可能であるべきである．

め，クラス内のノードの多様性を考慮することができな

属性特徴．属性の値には離散値と連続値の二つのタイプ

い．近年，ディープラーニングベースの手法である GAEが考えられる．一般に連続値では，正規分布とべき乗分と GraphVAE [11], [20] や，GAN [9] ベース手法である

布に従うことが知られている．このことから，グラフ生

NetGAN [5] が提案されている．これらの手法は入力グ

成器は属性値の分布についても多様な分布を選択可能でラフからのグラフ再生成を目的とするため，ユーザが柔あるべきである．

軟にクラス構造を制御することができない．以上から，

2. 2 クラス特徴

ユーザが制御可能なノード-クラス所属プロポーションをサポートした既存手法は存在しない．

1 章で示したようにグラフ生成器は core/border および homophily/heterophily の現象を表現するためにノー取り組む課題．既存手法ではサポートできないノードレベ

ド-クラス所属/接続プロポーションをサポートするべきルの制御を可能にするために，私たちは新しいグラフ生

である．ノード-クラス所属/接続プロポーションを捉え成器，acMark を提案する．ノード-クラス所属プロポー

るために，入力パラメータとして三つの基本的な統計量

ションをサポートしたグラフ生成器の実現には技術的課であるクラス接続平均，クラス接続分散，クラスサイズ

題が二つある：1）生成されたグラフの質，2）グラフ生分布を導入する．これら三つの統計量は，潜在変数であ成の効率．さらに，これら二つの課題は相互に依存関係

るノード-クラス所属/接続プロポーションを生成するたがあるため，グラフ生成器はその関係をバランスするよめに利用される．

うに設計されなければならない．

クラス接続平均. homophily/heterophily の現象を表現

貢献点．acMark は上記の二つの課題を，属性付きグラフ

するために，クラス間の接続割合を表すクラス接続平均の多様な特性による制約を表現するための潜在変数（ノーM ∈ Rk×k を導入する．各要素 Ml1 ,l2 はクラス l1 のド-クラス所属/接続プロポーション）を導入することと，ヒューリスティックな効率的グラフ生成アプローチを取る

ノードからクラス l2 のノードへの接続割合の平均を表す．

M の定式化を以下に示す：ことで解決する．ノード-クラス所属/接続プロポーショ
ンは潜在変数で表すことができ，それらの潜在変数を用いて表現された制約を解くことによって，ユーザが指定

Ml1 l2 =

X
1 X X
(
Sij /
Sij ).
|Ωl1 | i∈Ω j∈Ω
j∈N
l1

(1)

l2

したクラス構造に従うエッジを生成可能にする．効率性

ク ラ ス 接 続 平 均 は ，バ イ ナ リ 表 現 で あ る ho-については，満たすべき制約の優先付けおよびサンプリ

mophily/heterophily のより一般的な表現である．対角ング手法の活用によって，エッジ数に対して線形で動作

要素はクラス内の接続割合を意味している．

することを可能にした．これらによって，acMark は高精度かつ効率的なグラフ生成を実現する．

に，クラス間の接続割合の分散を表すクラス接続分散

D ∈ Rk×k を導入する．クラス接続分散はクラス間の2 事前準備

ノード-クラス所属プロポーションの多様性を意味する．

クラスラベルを持つ属性付きグラフは G = (S, X, C)と表すことができ，隣接行列 S ∈ {0, 1}

クラス接続分散. core/border の現象を表現するため

n×n

，属性行列

各要素 Dl1 ,l2 はクラス l1 のノードからクラス l2 のノードへの接続割合の分散を表し，以下のように定式化される：

v
u 1 X XXu
Dl1 l2 = t(
Sij /Sij − Ml1 l2 )2 .
|Ωl1 | i∈Ω j∈Ω
j∈N
l1

l2

を表すロスであり，Lclass size はユーザが指定したクラス
サイズ分布と生成されたグラフのクラスサイズ分布の差を表すロスである.

(2)

二つ目の課題は，効率的に大規模なグラフを生成する

クラス接続分散は，バイナリ表現である core/border のことである．問題は二つあり，一つ目は所与のノード次

より一般的な表現である．

数分布を満たすようなグラフが存在するかどうかの決定

クラスサイズ分布. クラス接続平均および分散は詳細なは NP-complete であることである [1]．二つ目はノード-

クラスの特徴を捉えているが，クラスサイズの情報を含クラス所属/接続プロポーションから全てのノードペアにんでいないため，クラスサイズ分布を導入する．多くのついてのエッジの存在確率を推定するためには O(kn2 )実グラフでは，クラスサイズ分布はべき乗分布で近似での大きな計算量が必要であることである．一つ目の問題を解決するために，ヒューリスティックにノード次数を割きることが知られている [6], [18]．

り当てたのちにエッジを作成する効率的なアルゴリズム

2. 3 問 題 定 義を設計する．二つ目の問題については，エッジ数に対し

本稿では，二つの実践的なシナリオを提供する．一つ目はグラフ特徴とクラス特徴を入力として，柔軟に特性て線形でアルゴリズムが動作するための効果的なサンプリング手法を導入する．

が制御可能であるグラフを生成する．二つ目はグラフの隣接行列 S ′ とクラスラベル C ′ および属性特徴を入力として，所与のグラフと似た特性を持つグラフを生成する．
いずれのシナリオにおいても，acMark は入力された特性に類似した特性を持つ人工グラフを効率的に生成することを目的とする．

3 提案手法
この章では，acMark の設計について説明する．まず初めに 3. 1 において潜在変数を導入し，それらによって
式 (4) で示したロスを設計する．また acMark によるグ
ラフ生成の概要も示す（一つ目のシナリオ）．次に 2. 3 章
で示したグラフ生成の二つ目のシナリオについて 3. 2 章

2. 4 技術的な課題
上記の問題を解くために，二つの主要な課題に取り組で説明する．最後に acMark の時間および空間計算量をむ．一つ目の課題は，グラフ特徴とクラス特徴からくる

3. 3 章で分析する．

複数の構造的な制約を満たすようにエッジを生成しなけ

3. 1 生成モデル

ればならないことである．これらの制約とグラフ生成問
題の関係を明らかにするために，構造部分のロスを定義
する：

acMark の基本的なアイデアは，潜在変数と呼ばれるデータ構造を用いてノードレベルのクラス情報を掴み，潜在変数からグラフを生成することである (図 2 を参照)．

Ltopology = Lgraph feature + Lclass feature(3)

3. 1. 1 潜 在 変 数
acMark は三つの潜在変数：ノード-クラス所属プロ

ここでの Lgraph feature はグラフ特徴と生成グラフの間のポーション U ∈ Rn×k ，ノード-クラス接続プロポーロスであり，Lclass feature はクラス特徴と生成グラフの間

ション U ′ ∈ Rn×k および，属性-クラスプロポーションのロスである．ノード-クラス所属/接続プロポーションをV ∈ Rd×k を用いることでグラフを出力する．これらの表現する潜在変数を活用することによって，Lclass feature

潜在変数は実グラフのクラス特徴を捉えるための主要なは二つの部分に分けることができる：

構成要素である．
三つの潜在変数を以下のように定義する：

Lclass feature = Ledge precision|{z}［Deﬁnition 31］（ノード-クラス所属プロポーション U ）生成グラフ-潜在変数間U ∈ Rn×k はノードからクラスへの所属に関する射影を+ Lmean + Ldeviation + Lclass size|{z}

意味する．もし i 行目の j 列目の要素が 1 に近ければ，

潜在変数-クラス特徴間

ノード i がクラス j に所属する傾向を意味する．

(4)［Deﬁnition 32］（ノード-クラス接続プロポーション U ′ ）ここでの Ledge precision は潜在変数から計算されるエッジ

U ′ ∈ Rn×k はノードからクラスへの接続に関する射影をの存在確率に基づいて，正確にエッジが生成されている意味する．もし i 行目の j 列目の要素が 1 に近ければ，かを表すロスであり，Lmean はユーザが指定したクラス

ノード i がクラス j に含まれるノードに接続する傾向を接続平均と潜在変数から推定されるクラス接続平均の差意味する．

を表すロスであり，Ldeviation はユーザが指定したクラス［Deﬁnition 33］（属性-クラスプロポーション V ） V ∈接続分散と潜在変数から推定されるクラス接続分散の差

Rd×k は属性からクラスへの関係の強さの射影を意味す

Latent factors

Graph feature

Class feature

Topology statistic: class preferencemeannode degree(the number ofnodes and edges)
class preference
deviation
Attribute statistic:
distribution of
attribute values,
the number ofclass size
attributes
ditribution

positive
topology
type
negative
topology
type

OutputEdge
generation

S

U U’T

U’

fS : samplingU

Attribute
generation

V

X

U VT
fX : applying

attribute j

Input

distribution

attribute i

Cclass labels

図 2: 提案手法の概要図．acMark はまず潜在変数である U , U ′ , V を生成したのちに，隣接行列 S と属性行列 X を生成する．クラスラベル C はクラスサイズ分布に基づいて生成される．
る．もし i 行目の j 列目の要素が 1 に近ければ，属性 iがクラス j に対して強い相関があることを意味する．

inverse(Ui. ) = 1 − Uih(h = l)il (1 − Uih ) ∑k U
(1−U
j =l
|

3. 1. 2 クラス特徴に関するロスエッジ 生 成 に ク ラ ス 特 徴 を 組 み 込 む た め に ，ロ ス

Lclass feature (式 (4)) を設計する．Lclass feature は以下の二つのロスとして表現できる：1) 生成グラフ-潜在変数

ij )

(h =
| l)

(7)

ここでのクラス l はノード i が属するクラスである．また，所属するクラス以外の要素を正規化することで，U ′の各行の和を 1 にする．

間ロス，2) 潜在変数-クラス特徴間ロス．

潜在変数-クラス特徴間ロス．次に潜在変数が正確にクラ生成グラフ-潜在変数間ロス．私たちは潜在変数 U ，U ′ス特徴を捉えられるように潜在変数とクラス特徴の間のを用いることによってエッジを生成するように acMarkを設計する．U と U ′ の定義より，U と U ′

⊤

の乗算に

よってエッジの存在確率を計算することができる．その理由は，U U ′⊤はノードからクラスへの所属の強さ（U ）⊤とクラスからノードへの接続の傾向（U ′ ）の二つの射ロスを設計する．まず，ユーザが指定したクラス接続平均と潜在変数から推定するクラス接続平均の間の差を減らすために以下のようにロスを定式化する：

Lmean =kX

∥Ml. −

l

影の組み合わせであるためである．このエッジ確率を用いて，エッジ生成の正確性のロスを定式化する：⊤

Ledge precision = ∥S − U U ′ ∥2

1 X
Ui. ∗ Ui.′ ∥2F|Ωl | i∈Ω
l
|
{z
}

(8)

推定接続平均

ここでの ∗ は要素ごとの積を意味する．また Ui. ∗ Ui.′(5)は推定値の近似計算であり，近似を用いる理由は全てのノードペアの間の確率を計算するには O(kn2 ) の高コス1 章で述べたように，homophily は似た属性を持つノード

トを要するからである．次にユーザが指定したクラス接が互いに接続する現象であり，heterophily はその逆の現続分散と潜在変数から推定するクラス接続分散の間の差象である．homophily/heterophily の両方をサポートすを減らすために以下のようにロスを定式化する：

るために，U と U ′ を以下のように設計する．homophily
プロパティのクラスでは二つの潜在変数は同じ値を持ち，heterophily プロパティのクラスでは二つの潜在変数は反転した値を持つ．正確な定義のために homophily プロパ
ティのクラスをポジティブトポロジーと呼び，ランダム

Ldeviation =
(9)
s
k
X
1 X
∥Dl. −(Ui. ∗ Ui.′ − Ui. ∗ Ui.′ )2 ∥2F|Ωl | i∈Ω
l
l
|
{z
}
推定接続分散接続よりクラス l 内エッジが多いとき（Mll >= 1/k），そのクラスはポジティブトポロジークラスとする．その逆

ここでの Ui. ∗ Ui.′ は Ui. ∗ Ui.′ の平均を表していて，ノーの場合，すなわち heterophily プロパティのクラスをネで近似を用いて計算する．最後に推定クラスサイズと生ガティブトポロジーと呼ぶ．上記の議論から U ′ を定式化する：(

Ui.′ =

ド i は Ωl に含まれるノードである．式 (8) と同様の理由成されたグラフのクラスサイズの間のロス Lclass size を以下のように定式化する：

Ui.
inverse(Ui. )(i ∈ Ωl and l ∈ typep )(i ∈ Ωl and l ∈ typen )(6)

Lclass size =kX(class size[l] − |Ωl |/n)2

(10)

l=1

ここでの typep ，typen はそれぞれポジティブとネガティ

ここでの class size はユーザに指定されたクラスサイズ

ブトポロジークラスの集合である．また inverse 関数は分布を示し， |Ωl |/n はクラス l のクラスサイズ比率を

以下のように定式化できる：

表す．

probability of node iに注目する．グラフ生成器にはユーザが指定したノード
次数をサポートすることが求められるため，生成グラフの質はユーザが指定したノード次数と生成グラフのノー

=

0

…

…
1 2 3 4i-1 inode IDn-1 n⊤

図 3: 逆関数法の概念図．バーは U ′ .l の累積密度関数をド次数の差として以下のように計算される：

表し，ここでの l はクラスを表す．

1 X θi − θi′
|
|
n i=1
θi
n

Lgraph feature =1function of

グラフ特徴は構造特徴と属性特徴の二つで表されるが，属性については 3. 1. 5 で述べるため，ここでは構造部分

Cumulative density

3. 1. 3 グラフ特徴に関するロス(11)
ノード i に対して Ui. に基づいて，ノード次数分だけク

ここでの θ は期待されるノード次数を表し，θ ′ は実際に

ラス Z ⊂ {1, . . . , k}θi を選択する．その後，Target node

生成されたグラフのノード次数を表す．ロスの計算のた

selection from class ステップにおいて，各クラス l ∈ Z

めに Mean Absolute Percentage Error (MAPE) を採用に対して U.l′

した．MAPE を利用する理由は，高次数ノードも低次数れたノードとノード i の間にエッジを生成する 3 ．Target

ノードも同等に扱うことができるためにである．他の指node selection from class を各ソースノードに対して実標としては mean squared error なども使用可能である．

行するために，このアプローチは高コストである O(kn2 )に基づいて，ノードを選択する．選択さを必要としてしまう．

3. 1. 4 エッジ生成
acMark では隣接行列 S は U U⊤′⊤を用いて生成される逆関数法．アプローチの高速化のために単調増加な密(式 (5) 参照)．潜在変数によってユーザが指定したクラス

度のための逆関数法を組み込む．これによって，Target

特徴をエッジ生成に組み込む．隣接行列の生成には以下のnode selection from class ステップの時間計算量を O(1)

二つの課題がある：1) 所与のノード次数を持つグラフをにすることを実現する．まず各クラスごとに U ′存在するかを決定することは NP-complete な問題ある，

2) U U ′

⊤

⊤

の確率

′

密度関数（CDF）を計算する．図 3 は U のある列を正によるエッジ存在確率の計算コストは O(kn2 )規化することによる確率密度関数を可視化する．横軸はである．さらに，これらの問題はノード次数とエッジのノードを表し，縦軸はある列（クラス）の CDF を意味

存在を介して相互に依存している（式 (11)， (5)）．こし，fCDF はクラスからノードが選択される確率の CDFのことから，acMark はヒューリスティックにノード次数を表す．ノード i − 1 からノード i までの幅はノード i をを割り当ててエッジを生成する効率的なアルゴリズムを選択する確率を示し，fCDF (i) − fCDF (i − 1) で表現さ採用する．またエッジ確率の高計算量を克服するために，−1(x) を生成する．それはれる．次に CDF の逆関数 fCDF

逆関数法 [7] をアプローチに組み込む．

fCDF (i − 1) <= x < fCDF (i) であるときノード i のノー

エッジ生成のアプローチ．アプローチのアイデアは二つ

ド ID を返す関数である．つまり，この逆関数は 0 から 1あり，一つ目は高次数ノードから順にエッジを生成するの乱数値を選択することで確率に基づいたノード ID をことであり，二つ目は逆関数法を活用し，エッジの存在確返すことを意味する．高速アクセスのために，乱数の幅率の計算を高速化することである．一つ目について，高を小さなステップに分割することにより，CDF の逆関数

次数ノードからエッジ生成を始めることにより，エッジと似た結果を返すリストを生成する．このリストによっ

生成の終盤に高次数ノードが残ることを避けることがでて fCDF (i − 1) と fCDF (i) の間の値を得たときにノード

きる．これによって，高次数ノードが十分な数のエッジを

i のノード ID を得ることができ，その実行時間は O(1)持つことが可能になる．二つ目のアイデアは， Ui. ∗ Uj.′とすることができる．

によって計算されるノード i とノード j の間のエッジ確率

3. 1. 5 属 性 生 成を U に基づく Class selection from source node ステッ
プと U ′⊤に基づく Target node selection from class ス

属性行列 X は U V ⊤ に基づいて生成され，この行列積はノードからクラスへの所属の強さの射影（U ）とク

テップに分解して解釈することである 2 ．行列積の計算

ラスから属性への相関の強さの射影（V ⊤ ）の組合せとしを二つの確率的な選択ステップに変形する解釈によって，て考えることができる．クラス構造と属性値の分布であ逆関数法をこのアプローチに組み込むことができる．まる属性特徴の両方をサポートするために，1）同じクラス

ず，二つの選択ステップについて述べた後に，逆関数法に属するノードが似た属性を共有するように，U , V ⊤ のの利用について説明する．

積によって属性の基底ベクトルを得て，2）ユーザが指定

Class selection from source node ステップでは，各2：無向グラフを考えているが，説明を容易にするために source nodeと target node という表現を用いている．

した分布（ベルヌーイ，正規，べき乗分布）に属性値が3：ノード i とノード j の間のエッジ確率は算され，これは (U U′⊤

)ij に一致する．

∑kl=1 Uil Ujl によって計従うように，分布を属性の基底ベクトルに適用する．
以上によって，acMark はユーザが制御可能なクラス構造を持つ隣接行列 S と属性行列 X を生成可能である．
またノードのクラスラベル C はクラスサイズ分布から生表 1: 割当てノード次数と実際のノード次数との間の

MAPE．
m

216

217

218

219

220

Error 3.56e–3 7.20e–4 3.04e–4 2.17e–4 1.73e–4

成し，出力する．

3. 2 入力グラフからのパラメータ抽出
2. 3 章で述べたように，二つ目のシナリオではクラス
ラベル付きの入力グラフからパラメータを抽出し，似た特徴を持つグラフを再生成する．acMark はパラメータ抽出のための関数を用いて，構造特徴とクラス特徴（ノード次数，クラス接続平均，クラス接続分散，クラスサイ
ズ分布）を得る．抽出したパラメータを用いて，一つ目のシナリオと同じ方法でグラフを生成する．
このパラメータ抽出関数によって，acMark はユーザが入力したグラフと似たグラフを容易に生成できる．加えて，任意のグラフサイズにも対応が可能であり，ユー
ザは入力グラフによってクラス特徴を指定した上でノード数やエッジ数を変更することができる．

3. 3 計 算 量
提案手法の時間および空間計算量について議論する．
実グラフはほとんどの場合において，疎な隣接行列を持つ [17] . そのような場合，ノード次数の平均 θAvg を定数として考えることができ，m ∝ n とすることができる．
そのため，m は n2 に比べて非常に小さい値と考えることができる.
時間計算量. 計算量の大きい隣接行列，属性行列の生成について，それぞれの時間計算量を分析する．隣接行列の生成は Class selection from source node と Target node

selection from class からなる. 前者のステップでは，各ノードに対してノード次数分だけクラスを選択するため，O(knθAvg ) のコストを要する．後者のステップでは，乱数生成とリストアクセスなのでコストは O(1) である．
よって，隣接行列生成の計算量は O(mkr) と表すことができる．ここでは，m = nθAvg であり，r は隣接行列生
成での反復を表す定数である. 最後に，属性行列の生成においては，U V ⊤ の行列積の計算のために O(dkn) を要する．以上の議論から，合計の計算量は O(mkr + dkn)である．

能であることを示すために，以下の質問に答える実験を行う．Q1：生成されたグラフはユーザが指定したグラフ
特徴を満たすか？（4. 1 章），Q2：acMark はノードとクラス間の接続割合を柔軟に制御可能か？（4. 2 章），Q3：

acMark はどれだけよくスケールするか？（4. 3 章）．
本実験では，LFR 4 と DC-SBM 5 を主要な比較手法とす
る．その理由は，LFR と DC-SBM が生成するグラフはクラスラベルを持ち，かつクラスレベルの接続プロポー
ションは制御可能であり，構造の面で acMark が生成できるグラフと似ているからである．

acMark は Python3 によって実装されており，実験はIntel(R) Xeon(R) CPU E5-2640 v4 @ 2.40GHz with
1TB memory を用いた. また全ての実験は単一スレッドかつ単一コアで実施した．

4. 1 Q1：生成されたグラフはユーザが指定したグラフ
特徴を満たすか？
ここではユーザが入力したノード次数と属性の分布に従うように acMark がグラフを生成するかを検証する．最初に，式 (11) で示したグラフ特徴のロスである割り当て
ノード次数と実際に生成されたノード次数の間の MAPEを計算する．エッジ数 m を {216 , 217 , 218 , 219 , 220 } の範囲で変化させる．パラメータ k, r, n はそれぞれ 5, 50, m/32と設定し，M の対角要素を 0.4 とし，その他の要素は0.15 とし，5 回平均を結果として利用する．表 1 において，ノード次数の MAPE を示す．この結果から acMarkによって生成されたグラフはほとんど与えられたノード次数に従うことが確認できる．次に図 4 において，属性の分布とヒストグラムを示す．属性の分布には正規分布を設定する．図 4a は二つの属性の 2-D プロットであり，
図 4b は一つの属性のヒストグラムを示している．属性の分布が正規分布に従うので，与えられた分布に基づいて acMark が属性を生成できることが示された．まとめとして，この実験ではユーザが指定したグラフ特徴に従うグラフを acMark が生成できることを示した．

空間計算量. 隣接行列 S については，隣接リストを用いた表現によって空間計算量は O(m) である．また，逆関数法のためのリストのサイズは O(kn) である. 最後に，
属性行列 X のサイズは O(nd) である. したがって，空4. 2 Q2：acMark はノードとクラス間の接続割合を柔軟に制御可能か？
ノードとクラス間の接続プロポーションを acMark が間計算量は O(m + kn + dn) である.
4：https://networkx.github.io/documentation/networkx-2.1

4 実験

/reference/algorithms/generated/networkx.algorithms.community.
community_generators.LFR_benchmark_graph.html

本章では，acMark が高精度なグラフを効率的に生成可

5：https://networkx.org/documentation/stb/reference/generated/
networkx.generators.community.stochastic_block_model.html

0
1
2
3

0.5

2.5
2.0
1.5
1.0
0.5
0.0

count

attribute2

1.0

0.0

0.5
attribute1

1.0

0.0

0.2

0.4

0.6

0.8

attribute value

1.0(a) ネガティブトポロジーク (b) ポジティブとネガティブト(a) 生成された属性の分布．色(b) 生成された属性（attribute1）

はノードが属するクラスを意

ラス．M の全ての対角要素は ポロジークラスの両方を含むのヒストグラム．

0.05 に設定する．

味する．

グラフ．

図 4: 属性特徴．属性生成のパラメータである α，σ ，ω図 6: 隣 接 行 列 の 可 視 化 ．パ ラ メ ー タ は n = 3000,

はそれぞれ 0.1, 0.0, 0.2 となるように設定する．

m = 30000, k = 6 と設定する．
表 2: 実行時間とメモリ消費量．TO と OOM はそれぞれ 36 時間以内に終了しなかった場合とアウトオブメモリを意味する．
m(a) 各セルは生成グラフのクラス接続平均 M gen を表す．
対角要素は 0.6 および他の要
素は 0.08 に設定する．

(b) 各 セ ル は 生 成 グ ラ フ のク ラ ス 接 続 分 散 D gen を
表 す．対 角 要 素 は そ れ ぞ れ[0.2, 0.2, 0.25, 0.25, 0.3, 0.3] とし，他の要素は 0.05 に設定す
る．

221

224

227

230

time

acMark

1.52e2 1.24e3 1.16e4 1.12e5

[sec]

LFR

2.17e2 1.50e4

TO

TO

DC-SBM 9.60e3 OOM

OOM

OOM

memory acMark

1.00e3 7.80e3 5.33e4 4.88e5[MiB]

1.40e3 7.45e3

TO

TO

DC-SBM 6.37e5 OOM

OOM

OOM

LFR

いて，ノードとクラス間の接続プロポーションをサポートすることを示した．
次に，acMark がネガティブトポロジーと混合したトポ

図 5: クラス接続平均とクラス接続分散の可視化．パラ

ロジータイプをサポートすることをそれぞれ示す．図 6

メータは n = 10000, m = 100000, k = 6 とする．

は生成グラフの隣接行列を表す．隣接行列では縦軸と横軸にそれぞれ対応するノード ID の間にエッジがある場サポートすることを示すために，図 5 は生成グラフのク合を青いドットで示す．この実験ではクラス数は 6 とし，ラス接続平均とクラス接続分散のヒートマップを示す．こ

図中の対角線上にブロックとしてクラスが観測される．

こでは，M gen と D gen を生成グラフのクラス接続平均

図 6a は全てのクラスがネガティブトポロジーである場とクラス接続分散とする．まず，クラスレベル接続プロ合を示す．M の全ての対角要素をランダムのときより

ポーションを acMark が制御可能であることを示す．M

低い 0.05 に設定する．図より，ノードは明らかに他のクの全ての対角要素を 0.6 とする. 図 5a は，M gen の対角ラスに属するノードと接続する傾向があることがわかる．

要素が 0.6 に近い値であることを示す．M gen の対角要

さらに複雑な場合として，ポジティブとネガティブの両素が 0.6 に完全に一致しない理由は，エッジ生成ステップ

方のクラスを含む一つのグラフを図 6b に示す．クラス

が確率的な手続きに基づいているからである．この図か

0, 1, 2 はポジティブトポロジーなので，それらに属する

ら acMark がポジティブトポロジークラスをサポートすノードは内部で密に接続している．クラス 3, 4, 5 に属することを確認できる．図 5b は，ノードとクラスの間の接るノードは他のクラスに属するノードに接続する傾向が

続プロポーションの分散を acMark が制御可能かを示す．

あることが確認される．以上のことから，acMark がノーD の対角要素をそれぞれ [0.2, 0.2, 0.25, 0.25, 0.3, 0.3] とドとクラス間の接続プロポーションを柔軟に制御できる

gen
し， その他の要素は 0.05 と設定する. 図 5b から，D00

ことを確かめた．

gen
gen
gen
と D11
は D44
と D55
比べて小さい値であることがわかる．D gen の対角要素が設定した値に完全に一致し

4. 3 Q3：acMark はどれだけよくスケールするか？

ない理由は，acMark はノード次数やクラス接続平均の

acMark のスケーラビリティを調査するために，エッジ制約を優先的に満たすからである．この結果は，優先度数を変化させることで実行時間とメモリ消費量を示す．実が低いとはいえ acMark が接続プロポーションの分散を

験ではエッジ数を {221 , 224 , 227 , 230 } の範囲で変化させサポートすることを示している．まとめとして，この実る．パラメータ k, r, n はそれぞれ 5, 50, m/32 とし， M

験では acMark がクラス接続平均とクラス接続分散を用の対角要素は 0.6 とし，他の要素は 0.1 とする．acMark

との比較対象として，既存手法の中では最も acMark と似たグラフを生成する LFR と DC-SBM を用いる．
時間計算量. まず，acMark，LFR および DC-SBM の実[3]

行時間の比較を行う．表 2 において，エッジ生成に要す
る実行時間を示し，acMark がエッジ数に対して線形に[4]動作することと，10 億（230 ）エッジを 32 時間で生成可能であることを示している．LFR と DC-SBM と比較して，acMark が大幅に高速であることが確認できる．こ[5]

れは acMark が逆関数法によって効率的にエッジを生成している一方，LFR はグラフサイズの増加に伴いエッジ生成にしばしば失敗し，DC-SBM の時間計算量が O(n2 )[6]であるからである．これらの結果より，acMark がクラスラベルを持った大規模グラフを効率的に生成することを

[7]

確認した．
空間計算量．次にメモリ消費量について分析を行う．表 2[8]はグラフ生成に使用したメモリ消費量を示す．acMark がエッジ数に線形にスケールすることがわかる．acMark とLFR は似たメモリ消費量である．DC-SBM ではエッジ[9]数に対して 2 乗に比例してメモリ消費量が増加することを観測した．
まとめとして，これらの実験では acMark は時間およ[10]

び空間計算量の両方でエッジ数に対して線形にスケールすることを検証した．さらに最先端の既存手法を大幅に[11]上回ることを示し，他の手法では実践的には生成不可能な大規模グラフを生成することを示した．

[12]

5 おわりに本稿では，クラスラベルを持った属性付きグラフ生成[13]器である acMark を提案した．実験を通して acMark の
四つの主要な特性を検証した．1) 生成されたグラフは[14]

ユーザが指定したグラフ特徴（ノード次数分布と属性値の分布）に従う，2) acMark はユーザが指定したノード[15]とクラスの間の接続割合をサポートする，3) acMark はエッジ数に対して線形にスケールし，10 億エッジを持つ[16]

グラフが生成可能であることを示した，以上のことから，

acMark がユーザが指定したクラス構造を持つ大規模な[17]

属性付きグラフを生成できることを示した．
[18]

謝

辞

本研究は JSPS 科研費 JP20H00583 の助成を受けたも

[19]

のです。
文

献

[1] Guillaume Bagan, Angela Bonifati, Radu Ciucanu,
George Fletcher, Aurélien Lemay, and Nicky Advokaat. gMark: Schema-driven generation of graphs
and queries. IEEE TKDE, 2017.
[2] Oualid Benyahia, Christine Largeron, Baptiste Jeudy,and Osmar R Zaı̈ane. Dancer: Dynamic attributed

[20]

[21]

network with community structure generator. In Proceedings of ECML PKDD, 2016.
Smriti Bhagat, Graham Cormode, and S Muthukrishnan. Node classiﬁcation in social networks. In Social
network data analytics. Springer, 2011.
Aleksandar Bojchevski and Stephan Günnemann.
Bayesian Robust Attributed Graph Clustering: Joint
Learning of Partial Anomalies and Group Structure.
In Proceedings of AAAI, 2018.
Aleksandar Bojchevski, Oleksandr Shchur, DanielZügner, and Stephan Günnemann. Netgan: Generating graphs via random walks. arXiv preprint
arXiv:1803.00816, 2018.
Aaron Clauset, Mark EJ Newman, and Cristopher
Moore. Finding community structure in very large
networks. Physical review E, 2004.
Luc Devroye. Nonuniform random variate generation.
Handbooks in operations research and management
science, 2006.
Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu, et al. A density-based algorithm for discovering clusters in large spatial databases with noise.
In Proceedings of KDD, 1996.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza,
Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron
Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in NIPS, 2014.
Brian Karrer and Mark EJ Newman. Stochastic
blockmodels and community structure in networks.
Physical review E, 2011.
Thomas N Kipf and Max Welling. Variational graphauto-encoders.
arXiv preprint arXiv:1611.07308,
2016.
P Krishna Kumar, Paul Langton, and Wolfgang Gatterbauer. Factorized graph representations for semisupervised learning from sparse data. arXiv preprint,
2020.
Andrea Lancichinetti, Santo Fortunato, and Filippo
Radicchi. Benchmark graphs for testing community
detection algorithms. Physical review E, 2008.
Christine Largeron, Pierre-Nicolas Mougel, Reihaneh
Rabbany, and Osmar R Zaı̈ane. Generating attributed networks with communities. PloS one, 2015.
Jure Leskovec and Andrej Krevl. SNAP Datasets:
Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.
Miller McPherson, Lynn Smith-Lovin, and James M
Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 2001.
Mark EJ Newman. Networks: An Introduction. Oxford University Press, 2010.
Gergely Palla, Imre Derényi, Illés Farkas, and TamásVicsek. Uncovering the overlapping community structure of complex networks in nature and society. nature, 2005.
Himchan Park and Min-Soo Kim. TrillionG: A
trillion-scale synthetic graph generator using a recursive vector model. In Proceedings of SIGMOD, 2017.
Martin Simonovsky and Nikos Komodakis. Graphvae:
Towards generation of small graphs using variational
autoencoders. In Proceedings of ICANN. Springer,
2018.
Chun Wang, Shirui Pan, Ruiqi Hu, Guodong Long,
Jing Jiang, and Chengqi Zhang. Attributed graphclustering: A deep attentional embedding approach.
In Proceedings of IJCAI, 2019.