# Holistic Prediction on a Time-Evolving Attributed Graph

山崎 翔平 $\dagger \cdot$ 佐々木勇和 $^{\dagger \dagger}$

## 1 はじめに

我々は自然言語処理を専門的に研究しているわけではない，そのため，自然言語処理の国際会議どころか，国内の会議にも一度も参加したことがない。ここでは，我々がなぜ ACL に投稿したのかを述べる。

まず，我々の論文はグラフ深層学習に関する技術を提案しており，特定の応用分野を想定はしていない，そのため，イントロや実験データを変更すれば，分野外と言われることはあまりない．実験で使っているグラフが自然言語から計算された特徴量を用いていたため実験の変更も必要なかった. ACLの査読では, 機械学習分野の方が適切なのでボーダーラインというコメントがあったが，そこまで強い主張ではなかった，次に，自然言語処理は知識グラフの活用が最も活発な分野の一つである。 そのため, グラフ深層学習が受け入れられる土墥は既にあった.母集団的には少ないかもしれないがグラフ分析が好きな査読者に当たる可能性が高く，好意的に見てくれることを期待していた，最後に，共著者の Panagiotis Karras 先生が ACLへの投稿を勧めたことが大きい．ACL ではなくIJCAI（時期的にどちらかしか投稿できない）に投稿しようとしていたが，論文の見た目（内容ではない）が ACLに合ってるとの助言に従い投稿した. この助言がなければ投稿していなかったので感謝しかない。見た目で決めるというのは斬新であったし，それが上手くはまったのは驚いた。まとめると，ACL に投稿した理由は，(1) イントロの変更のみで自然言語処理の論文っぽく変更できた, $(2)$ 自然言語処理もグラフ研究が盛んでありグラフ深層学習も範囲内，そして (3) 論文の見た目ということになる.

国内の自然言語処理分野においてもグラフ分析に関する研究がより増えればと思い，以降では我々が提案した技術のエッセンスを紹介する (Yamasaki et al. 2023).

## 2 論文概要

ブログ投稿やニュース記事，ユーザプロフィール等の実世界の言語データは，それぞれが相互に関連しており，引用関係やソーシャルネットワークとして表現することができる。このよ


うな相互関係は，一般にグラフとしてモデル化でき，ノードがオブジェクトを，リンクが関係性を表す (Zhu et al. 2019)，例えば，ソーシャルネットワークでは，登録ユーザはノードとして表現され，そのプロフィール情報はノード属性として，ユーザ同士の繋がりはリンクとして表現される。そして，登録ユーザや，そのプロフィール情報，ユーザ同士の繋がりは時間とともに変化する。このような時間的に変化しやすいグラフは，属性付き時間発展グラフと呼ばれる (Rossi et al. 2020)。様々な NLP アプリケーションにおいて, 属性付き時間発展グラフの将来を予測する技術は有益である。例えば，読者へニュース記事を推薦したい場合，ユーザプロフィールを予測することで，潜在的なニーズを引き出し，読者にとってより良いユーザ体験を提供することができるようになる (Wu et al. 2019; Hasanuzzaman et al. 2017).

## 2.1 問題定義

本論文では，実世界の言語データを用いて，属性付き時間発展グラフの将来予測タスクに取り組んでいる。本研究と既存研究で取り組まれてきたタスクの違いについて簡単に説明する.

グラフを $G=(V, E, X)$ と表記する. ここで， $V$ はノードの有限集合， $E \subseteq V \times V$ はリンクの有限集合， $X \in \mathbb{R}^{|V| \times d}$ はノード属性の有限集合である。 $X^{(v)}$ はノード $v$ の $d$ 次元の属性を表しており, 各属性はカテゴリ値, 数値, 分散表現のいずれも取り得る. 属性付き時間発展グラフは $\left.\langle G_{T-L+1}, G_{T-L+2}, \ldots, G_{T}\right.\rangle$ と表記する. ここで $T$ は現在のタイムステップを, $L$ は観測されたタイムステップ数を表しており， $G_{t}:=\left(V_{t}, E_{t}, X_{t}\right)$ はタイムステップ $t$ のグラフを表す. 属性付き時間発展グラフでは, $V, E, X$ がタイムステップによって変化する。すなわち，ノードとリンクの出現と消失，ノード属性の動的変化を含む。本論文で取り組む問題定義を以下に示す.

問題属性付き時間発展グラフ $\left.\langle G_{T-L+1}, G_{T-L+2}, \ldots, G_{T}\right.\rangle$ が与えられたとき，夕イムステップ $T+1$ におけるグラフ $G_{T+1}=\left(V_{T+1}, E_{T+1}, X_{T+1}\right)$ を予測する.

図 1 に本論文で取り組む問題の全体像を示す.この問題を解くには， $G_{T+1}$ の構成要素の一つではなく, 全てを同時に予測する必要がある。そのためには, 次に示す 6 つのサブ予測タスクの全てを同時に解かなければならない.
(1) 消失ノード予測
(4) 既知ノードの属性予測
(2) 出現リンク予測
(5) 出現ノードの属性予測
(3) 消失リンク予測
(6) 出現ノードに接続されるリンク予測

また，それぞれのサブ予測タスクは相互に影響し合うことを考慮する必要がある.ソーシャルネットワークの例で考えると, ユーザのプロフィール情報は動的に変化しており, つながりのある他のユーザに影響を受けているかもしれない．新規ユーザはアカウントを登録するし，アカウントを削除するユーザもいるだろう．新規登録されたアカウントはプロフィールが似ている既存のアカウントとつながり, 削除されたアカウントとつながっていたアカウントは他のア

$G_{T-L+1}, \cdots, G_{T}$

$G_{T+1}$

- : links connected to new nodes $E_{T+1}^{n}$

: appeared links $E_{T+1}^{a}$

図 1 属性付き時間発展グラフ予測の例 (Yamasaki et al. 2023)。ノードの色は属性を表す.

カウントとつながるかもしれない.このようにサブ予測タスク間には相互依存性が存在すると考えられる。我々の知る限り「「(5) 出現ノードの属性予測」や「 $G_{T+1}$ の全体を予測する」といった問題に取り組んでいる既存研究は存在しない。これらのサブ予測タスクは，メインタスクとして個別に，独立に解くのが既存研究の主流であり，影響し合うサブ予測タスク全てを同時に予測する試みは本論文が初である.

## 2.2 研究課題

上述の問題を解くにあたり，本論文では以下 2 つの研究課題を設定している.

## Q1 サブ予測タスク間の相互依存性を利用して予測精度を向上させることは可能か？

本論文では，消失ノード予測や出現ノードの属性予測等，複数のサブ予測タスクを含む問題に取り組んでいる。これらのサブ予測タスク間には相互依存性が存在し，これを捉えることで，それぞれのサブ予測タスクを独立に解く場合よりも，高い予測精度を達成できるのではないかという仮説である.

## Q2 出現ノードの属性予測は可能か？

出現ノードの属性予測では，過去に観測されていない，将来新たに出現するノード集合を予測すると共に，それらが持つ属性を同時に予測する必要がある。これはソーシャルネットワークの例で考えると，将来新規登録されるユーザアカウント群がそれぞれどのようなプロフィール情報を持っているかを予測することに対応している.

## 2.3 提案手法

属性付き時間発展グラフの全体を将来予測するというタスクを通して, 研究課題の 2 つの問いに対する解を提示する。本論文では，Q1に対して汎用予測フレームワーク AGATE と， Q2 に対して出現ノードの属性予測モデルである PROSERの 2 のの新手法を提案している。この寄稿記事では, AGATE についてのみ紹介する。

属性付き時間発展グラフ全体の将来予測タスクで，高い予測精度を達成するためには，サブ

図 2 AGATEのアーキテクチャ (Yamasaki et al. 2023). 観測された $L$ ステップのグラフを入力し, 夕イムステップ $T+1$ のグラフを予測する。ピンクのフレームはグラフデータを，緑のフレームは予測モデルを，青のフレームは予測結果を表す.

予測タスク間の相互依存性を捉える必要がある。単一の手法ですべての相互依存性を捉えることは困難であるため，複数の手法を効果的に組み合わせ，ある夕スクの結果を他のタスクでインタラクティブに再利用する。本論文では，観測された過去のグラフから，出現ノード，消失ノード，出現リンク，消失リンク，およびノードの属性を予測し，夕スク間の相互依存性を活用可能で汎用的な予測フレームワーク AGATE ( $\underline{A}$ General framework for predicting $\underline{\text { Attributed }}$ Time-Evolving graphs) を提案する.

図 2 に AGATEのアーキテクチャを示す.AGATE は以下の 3 つの主要なコンポーネントから構成される。

i. Graph size prediction: 属性付き時間発展グラフの将来のサイズを予測するコンポーネント

ii. Independent prediction: 既知ノード間のグラフ構造や属性, 出現ノードの属性とそれに接続されるリンクについて個別・独立に予測するコンポーネント

iii. Reuse prediction: サブ予測タスク間の相互依存性を捉えた予測を実現するために (ii) の結果を再利用するメカニズムを有した予測コンポーネント

AGATEはモジュール化されており,「ii. Independent prediction」および「iii. Reuse prediction」 の各コンポーネント（6～15 番) はそれぞれのサブ予測タスクに対応しており，任意の予測モデルを採用することが可能である. 出現ノードの属性予測（6 番）については, 既存手法が存在し

ないため，新たな予測モデルである PROSER を開発している.

実験では，3つの実世界のデータセットを用いて AGATE と PROSER を評価し，(1) 各サブ予

測タスクが互いに影響し合うこと，(2) AGATE の Reuse prediction が予測精度を向上させ，各サブ予測タスクを独立に解く場合よりも高精度で予測できること, (3) PROSER が出現ノードの属性を高精度で予測できることを示した。

## 3 おわりに

本稿で紹介した論文は，グラフ全体を将来予測するという一般的な問題に初めて取り組んたものであり，その第一歩として汎用的な方法を提案した．昨今の AI の研究がそうであるように，高効率性や高精度な予測方法の開発等，考えられる研究課題は山ほど存在しており，この論文はグラフ予測の新たな出発点を与えた研究に他ならない. 最後まで本稿を読んでくださった自然言語処理分野の研究者の皆様にも, グラフ分析に興味を持っていただければ幸いである.

## 参考文献

Hasanuzzaman, M., Kamila, S., Kaur, M., Saha, S., and Ekbal, A. (2017). "Temporal Orientation of Tweets for Predicting Income of Users." In $A C L$, pp. 659-665.

Rossi, E., Chamberlain, B., Frasca, F., Eynard, D., Monti, F., and Bronstein, M. (2020). "Temporal Graph Networks for Deep Learning on Dynamic Graphs." In ICML.

Wu, C., Wu, F., Ge, S., Qi, T., Huang, Y., and Xie, X. (2019). "Neural News Recommendation with Multi-head Self-attention." In EMNLP-IJCNLP, pp. 6389-6394.

Yamasaki, S., Sasaki, Y., Karras, P., and Onizuka, M. (2023). "Holistic Prediction on a TimeEvolving Attributed Graph." In $A C L$, pp. 13676-13694.

Zhu, H., Lin, Y., Liu, Z., Fu, J., Chua, T.-S., and Sun, M. (2019). "Graph Neural Networks with Generated Parameters for Relation Extraction." In $A C L$, pp. 1331-1339.

## 略歴

山崎翔平：2019 年大阪大学工学部電子情報工学科卒業. 2021 年大阪大学大学院情報科学研究科マルチメディア工学専攻博士前期課程修了. 現在, 株式会社野村総合研究所所属.

佐々木勇和：2014 年大阪大学大学院情報科学研究科マルチメディア工学専攻博士後期課程修了. 博士 (情報科学). 現在, 大阪大学大学院情報科学研究科又ルチメディア工学専攻助教.