こんにちは． 研究開発部の黒木裕鷹です． ついに初めてフルマラソン（長野マラソン）に出場しました． タイムはネットで 3:58:25 で，サブ4を達成することができました！ 次の目標はサブ3.5（3時間半切り）でしょうか．道のりは遠いです．
さて先日，LINE株式会社主催の「NeurIPS'21 読み会」，そして「AAAI'22 読会」で発表する機会をいただきました． このシリーズの論文読み会も ICML'21, KDD'21 に続き早くも3, 4回目で，ありがたいことに毎度発表の機会をいただいています．
発表形式はどちらも 10分間の LT形式 で，9本 の論文が紹介されました． また，発表は LINE株式会社，ボストン コンサルティング グループ (BCG Japan)，株式会社ユーザベース，株式会社リクルート，Beatrust株式会社，Sansan株式会社 の有志 9名により行われました． 運営・発表者のみなさま，あらためて感謝申し上げます．
さて，この記事では，私が取り上げた論文を改めて紹介しようと思います． その他の情報や発表資料はこの記事では紹介しきれないため，以下の勉強会 URL よりご覧ください．
そして，なんとこの6社で，機械学習エンジニアやデータサイエンティストの採用説明会を開催するはこびとなりました！ 各社ともにユニークで魅力的な組織があり．中途・新卒の方問わずその魅力を知っていただく良い機会となっていますので，是非ご参加ください！！
それではやっていきます．
私が紹介した論文
いずれの勉強会でも，グラフ上のランダムウォークを基にした node embedding に関連する論文を紹介しました． node embedding とは，離散構造をもつグラフのノードを，より低次元（隣接行列やラプラシアンに比べて）な密ベクトルとして表現する技術です． アプローチには様々なものがありますが，グラフ上のランダムウォークによりノードの系列を得て，word2vec などのアルゴリズムで学習する DeepWalk などが有名です． 毎度毎度，なんだか芸がないようで恐縮ですがどうぞお付き合いください．
Residual2Vec: Debiasing graph embedding with random graphs (Kojaku et al., 2021)
こちらの論文 (Kojaku et al., 2021) では， node embedding が，グラフ構造から受けるバイアスを補正する手法 "residual2vec" を提案しています． ランダムウォーク系の node embedding はグラフ上のランダムウォークでノードの系列をサンプリングするのでしたが，特に工夫がなければ大きな次数（つながりの数）をもつ一部のノードにたどり着きやすく，偏ってサンプリングされてしまいます．
Kojaku et al. (2021) は，このようなグラフ構造に由来するバイアスを除去するため，"null model" とよばれる任意のグラフ生成モデルを仮定し，null model にない構造の特徴を埋め込もうとします． null model には，たとえば任意のふたつのノード間にランダムでエッジが張られるERモデルなどを考えることができます． reidual2vec では，与えられたグラフデータと 仮定した "null model" についてそれぞれ PMI (Pointwise Mutual Information) 行列を算出し，その差分を行列因子分解により低ランク近似します． つまり，null model では表現しきれないような構造を埋め込むことになるため，たとえばハブの存在を許容するようなモデル（Configuration model など）を null model にすることで，前述の次数に由来する偏りは取り除けることになります．
ランダムウォークではハブとなるようなノードは偏ってサンプリングされますが，ハブの存在を許容するようなモデルを null model に仮定することで，バイアスを補正できる，ということになります．
CrossWalk: Fairness-Enhanced Node Representation Learning (Khajehnejad et al., 2022)
こちらの論文 (Khajehnejad et al., 2022) では，タイトルにもあるように，Fairness（公平性）を高める node embedding の手法 CrossWalk を提案しています． node embedding によって得られるノードの埋め込み表現は，ノード分類やリンク予測など，様々な後段タスクに利用することができます． この状況において，Fairness を高めるとはいったいどういうことでしょうか．
まずは，Khajehnejad et al. (2022) で議論されている Fairness を導入します． 年齢や性別，思想など，倫理的な観点から保護すべき属性があります． ここでは，そのような属性を sensitive 特徴とよびます． また，年齢であれば10代，20代，... といった年代があるように，sensitive 特徴には複数の水準があります． Khajehnejad et al. (2022) では，sensitive 特徴の水準間で後段タスクのパフォーマンス（精度など）に差があってはいけない，という立場から，次式で与えられる disparity を Fairness の指標として導入しています．
ここで， は後段のグラフタスク
によるパフォーマンス，
は sensitive 特徴の水準です．
つまり，水準間でのパフォーマンスのばらつきを不公平さとみなし，評価していることになります．
この Fairness の考えは直感的にやや理解しにくいかもしれません． しかし，たとえば求人やローンの情報をユーザに推薦する例を考えてみると，sensitive 特徴にかかわらず適切な情報が配信されている，という状態は非常に重要でしょう． 特定の水準（年齢では "若者" など）に対してのみマッチした情報が配信されている，という状況は適切ではありません． sensitive 属性に依存した情報格差が生まれてしまうためです．
Khajehnejad et al. (2022) で提案されている CrossWalk は，FairWalk (Rahman et al., 2019) の改良です． Fairwalkのアイデアは，sensitive 特徴の水準が異なるノードが近くにあればパフォーマンスの差はうまれないだろう，というもので，水準の異なるノード間を遷移し，境界を跨ぎやすいようランダムウォークにバイアスをかけるアルゴリズムです． しかし，水準グループ間の接続が希薄で，大半のノードがグループの内側にきてしまっている場合にバイアスが機能しないことなど，欠点がいくつかあります． そこで，異なる水準間を繋ぐエッジの遷移の重みをかけるだけでなく，グループの内側にいても境界に近づいていくようにするように改良したアルゴリズムがCrossWalkになります． アルゴリズムの詳細については発表資料や元の論文をご覧ください．
おわりに
今回の記事では，外部の勉強会への登壇をきっかけに，node embedding をテーマにした論文2本を，改めて紹介しました． それではまた，ごきげんよう．
参考文献
- Kojaku, S., Yoon, J., Constantino, I., & Ahn, Y. Y. (2021). Residual2Vec: Debiasing graph embedding with random graphs. Advances in Neural Information Processing Systems, 34.
- Khajehnejad, A., Khajehnejad, M., Babaei, M., Gummadi, K. P., Weller, A., & Mirzasoleiman, B. (2021). CrossWalk: Fairness-enhanced Node Representation Learning. arXiv preprint arXiv:2105.02725.
- Rahman, T., Surma, B., Backes, M., & Zhang, Y. (2019). Fairwalk: Towards fair graph embedding.
