グラフデータの分析と DSOC の取り組みを俯瞰する / Overview of graph data analysis and DSOC initiatives

■イベント 
：Sansan×atmaCup #6 solution発表会
https://sansan.connpass.com/event/193901/

■登壇概要
タイトル：グラフデータの分析と DSOC の取り組みを俯瞰する
発表者： 
DSOC R&D研究員 黒木 裕鷹

▼Twitter
https://twitter.com/SansanRandD

Transcript

1. グラフデータの分析と DSOC の取り組みを俯瞰する Sansan株式会社 DSOC R&D研究員 ⿊⽊裕鷹
2. Data Strategy and Operation Center ⾃⼰紹介 ⿊⽊ 裕鷹 オンライン名刺 • ೥݄ೖࣾ Yutaka Kuroki Sansan 株式会社 DSOC（Data Strategy & Operation Center） R&D Data Analysis Group 研究員 @kur0cky_y
3. Data Strategy and Operation Center アジェンダ DSOC R&D について • そもそも DSOC ってなに？ グラフデータの分析を俯瞰する • 古典的なネットワーク科学から GNN まで DSOC におけるグラフデータの活⽤ • どんなふうに利⽤されている？
6. Data Strategy and Operation Center 組織構成 名刺管理サービス Sansanの開発、提供 名刺アプリサービス Eightの開発、提供 R&D データ分析・研究開発 （画像処理／機械学習・AI） Sansan事業部 Eight事業部 DSOC Sansan株式会社 データ統括部⾨
7. Data Strategy and Operation Center 各グループの役割 Data Analysis Group SocSci Group Arc Group Automation Group これまでにない速度と限りなく100％に近い精度、 セキュリティーの確保を⽬指し、画像認識や機械学習などの 技術を⽤いて、名刺やビジネス⽂書といった⾮定型でアナロ グな情報のデータ化を効率化・⾃動化する技術の研究開発に 取り組む。 社会科学の各領域を専攻するメンバーで構成。「リアルと バーチャルのはざまで、社会理論を武器に名刺交換の価値を 拡張する」をミッションとして掲げ、研究を通して得られた 知⾒や成果を事業やサービス、社会へと還元することに取り 組む。また、外部有識者との共同研究も積極的に展開する。 機械学習、⾃然⾔語処理、画像処理といった技術を⽤いて、 あらゆるビジネスデータを収集・解析する。多様なビジネス データを組み合わせることで、レコメンデーションエンジン やニュース配信エンジンなどの構築に取り組む。 「研究開発部が提供するサービスに責任を持つ」「DSOCを データで⽀える・リードする」をミッションとして掲げ、 サービスの可⽤性、拡張性、保守性の担保に取り組む。また、 研究開発部の開発⽣産性に向き合いながら、データ基盤の整 備、データの品質、データの取り扱いにおける安全性の担保 にも取り組む。
8. グラフデータの分析を俯瞰する
9. 複雑ネットワークと古典的な解析
10. Data Strategy and Operation Center グラフデータ • グラフ：ノード エッジ ℰ により = , ℰ で表される数学的対象 • データ例： > WWW，共著ネットワーク，SNS，交通網，⾷物連鎖ネットワーク， タンパク質の相互作⽤ネットワーク (PPI)，etc… • グラフデータを取り巻く分野 > ことば：グラフ理論，物理学，統計学，CS > 道具 ：数理モデル，統計モデル，機械学習モデル > 現象 ：社会学，⽣物学，化学，経済学，etc … 図：業種「その他製品」の誘導部分グラフ
11. Data Strategy and Operation Center ネットワークの基礎統計量 • 局所的な量 • 次数，様々な中⼼性 (e.g. pagerank)，クラスター係数，モチーフ，etc… • ⼤局的な量 • 次数分布，平均経路⻑，直径，次数相関，密度，コミュニティー構造，etc … クラスター係数：近傍同⼠がつながっている割合 今回のatmaCupでも活躍！？ ノードやエッジ単位の記述統計量だけでなく， 構造に由来する様々な特徴量を考えることができる
12. Data Strategy and Operation Center 複雑ネットワーク ランダムネットワーク ↔ 複雑ネットワーク • 現実のネットワークの多くが，ランダムネットワークにないような 共通の性質をもつ • スモールワールド性 • ⼤きいクラスター係数と⼩さい平均距離を併せもつ (Itʼs a small world!!) • Watts-Strogatz (WS) モデル [22] など • スケールフリー性 • 次数分布がべき分布に従う（⾮常に裾が⻑い）．ハブの存在 • Barabasi-Albert (BA) モデル [2] など
13. 図：密度の同じランダムネットワーク（左），スモールワールドネットワーク（中央），スケールフリーネットワーク（右） ⾼いクラスター係数 ハブの存在
14. Data Strategy and Operation Center ランダムネットワーク • Erdos-Renyi モデル [5] • すべてのノード間で確率 でエッジが貼られる • 次数分布はポアソン分布で近似できる • ⼀般化ランダムグラフモデル • 任意の次数列を与え，ランダムグラフを⽣成（ポアソン分布じゃなくてもよい） • 例：Configuration モデル [14] • 指数ランダムグラフモデル [9, 21] • ノード , 間にエッジが存在する確率にロジスティック回帰を適⽤ P !" = 1 = exp 1 + exp .
15. Data Strategy and Operation Center 指数ランダムグラフモデル • 特定の構造をもつ観測グラフ = が得られる確率は次式 > は に含まれるエッジの数 > これは指数型分布族 = | = exp . • 各ノードの特性を考慮したり，2者関係間が独⽴でないことを許容する拡張 を⾏うことができる． > 「⼈気者とそうでない⼈がいる」： exp → exp + ! + " > 「友⼈の友⼈も友⼈である確率が⾼い」：スター構造の導⼊ [16]
16. Data Strategy and Operation Center その他の現象 • 感染 > 隣接ノードに確率的に感染することを仮定 > 免疫ができる à SIRモデル > 再感染する à SISモデル • コミュニティ > グラフ分割 > 各種クラスタリング > 確率的ブロックモデル • 次数相関 > 「⼈気者の友達も⼈気者」 > BAモデルの次数相関は負になる 図：確率的ブロックモデルによる⽣成ネットワークの例
17. 図：業種ごと誘導部分グラフ (train) の次数相関
18. グラフデータの深層学習
19. Data Strategy and Operation Center グラフデータと深層学習 • (Semi) supervised learning > ラベルがあるノードだけを教師にし分類問題 > グラフは所与： GNN [17] ，GCN (spectral, spatial) [3] ，Graph Attention Network [19] > 未知ノードへの対応：GraphSAGE [8] • unsupervised learning > Skipgram：DeepWalk [15] , node2vec [6], LINE [18] , unsupervised GraphSAGE > Autoencoder：SDNE(隣接⾏列の再構成) [20], DNGR (点相互情報量の再構成) [4] > GCN×Autoencoder：GAE, VGAE [10] , Graphite [7] 今回のatmaCupで⼤活躍！！
20. Data Strategy and Operation Center グラフデータと深層学習 • (Semi) supervised learning > ラベルがあるノードだけを教師にし分類問題 > グラフは所与： GNN [17] ，GCN (spectral, spatial) [3] ，Graph Attention Network [19] > 未知ノードへの対応：GraphSAGE [8] • unsupervised learning > Skipgram：DeepWalk [15] , node2vec [6], LINE [18] , unsupervised GraphSAGE > Autoencoder：SDNE(隣接⾏列の再構成) [20], DNGR (点相互情報量の再構成) [4] > GCN×Autoencoder：GAE, VGAE [10] , Graphite [7] 今回のatmaCupで⼤活躍！！ skipgramの作り⽅，何を再構成するか，どの空間で畳み込むのか などで個性が出る
21. Data Strategy and Operation Center 表現学習の後段タスク • Graph reconstruction： • 離散的なグラフを連続的な空間で低次元近似．要約 • Link prediction： • ⽋落したリンクの予測，怪しいリンク検知． • Node clustering： • GCNに利⽤することもできる • Visualization： • 埋め込み品質などを定性的解釈に有⽤（⾊づけして2次元プロットなど） • Node classification： • 未知ノードに対して，ネットワーク構造を利⽤しながら予想する．GCNやGraphSAGEで直接⾏うことが可能 • Graph classification： • グラフ単位でラベル付け．化合物に対してしばしば⾏われる． • プーリングを任意のグラフに⼀般化しなければならない（これは未解決）．分⼦は結合に制約がある．
22. DSOC におけるグラフデータの活⽤
23. 同業他社ニュース
24. Data Strategy and Operation Center 同業他社ニュースにおける node embedding の利⽤ • Sansan や Eight 上で，同業他社の最新動向を配信する • node embedding により，より実感に沿う同業他社の特定 近傍探索 + 同業判定 企業ニュース 収集 ⽣成 配信 ! ! 固有表現抽出 ニュース ソース
25. Eight Career Design
26. Data Strategy and Operation Center • 転職ネットワークの埋め込みによる候補者検索の改善 • その他探索的研究 &JHIUͰμΠϨΫτ࠾༻͕มΘΔɻ 転職ネットワークの分析
27. Data Strategy and Operation Center 転職市場の探索的研究 • εϙʔπͷϨʔςΟϯά<>を転⽤した企業・業界ごとの特性の把握 count ← = ڝ߹౓!,#× ࠾༻ྗ! − Ϧςϯγϣϯ# + !# • ࠾༻ྗͱϦςϯγϣϯྗ͸ෛͷ૬ؔ > ߴϦςϯγϣϯɿਓࡐͷྲྀಈ͕Ժ΍͔ > ߴ࠾༻ྗɿ࠾༻਺͕ଟ͍ > ӈ্ɿ੒௕தɾస৬ࢢ৔ʹ͓͚Δத৺ 採⽤⼒ 企業がどの程度競合しているかはわからない． 転職ネットワークの埋め込みを活⽤ ※社名・⽒名を匿名化したEightデータでの転職のネットワークを分析した リテンション⼒
28. Eight Company Score
29. Data Strategy and Operation Center Eight Company Score • 株主価値や企業業績，ESG 指標との関連が 明らかになりつつある [1, 12] > Environment, Social, Governance 企業に対するステークホルダーのエンゲージメントを定量測定 Eight Company Score
30. Data Strategy and Operation Center 数値のメリットと課題 • Eight 上でのアンケートに基づいた企業のブランド⼒調査 > ステークホルダーとのつながりを ブランド・モノ・ヒト で数値化 > 通常では⾒つけづらい BtoB 企業にたどり着きやすい（snowball sampling 的） • 各企業について誰に聞けば良い？ • 1⼈につき◦◦企業までしか聞けない • 1企業につき△△件の回答がほしい • 上記を満たしつつ，聞く⼈数減らしたい
31. Data Strategy and Operation Center ⼆部グラフからのサンプリング
32. Data Strategy and Operation Center 最⼤流問題の活⽤ S G
33. Data Strategy and Operation Center Dinic Algorithm の利⽤ 32 - Dinic アルゴリズムの利⽤（最⼤フロー問題） - 最⼤フロー問題： - 各辺 ∈ ℰ に容量 () がついており，!"#$%& ∈ から '"() ∈ へ流せる流 量を求める > BFSで各頂点までの距離を計算 > DFSからの容量が⼤きくなるようなパスを⾒つけ，フローを流す． > 流したら逆リンク⽣成 > 流しきるまで繰り返す
34. Data Visualization
35. Data Strategy and Operation Center Data Visualization
36. Nishida, T., Tokui, N., Dozono, S., JEMAPUR, Yamawaki, N. (2020). Dawn of Innovation, NetSci2020, https://qosmo.jp/projects/sansan-dsoc/
37. Data Strategy and Operation Center まとめ • グラフデータに対する分析⼿法を俯瞰的に紹介した． • DSOC におけるグラフデータの活⽤事例を紹介した． • コンペへのご参加ありがとうございました！！ オンライン名刺
38. Data Strategy and Operation Center 参考⽂献 1. 真鍋 友則, 中川 慧, B2B企業ブランド評価と株価の価値関連性の実証研究, 経営情報学会誌, 2020, 29 巻, 2 号, p. 87-104 2. Barabási, A. L., & Albert, R. (1999). Emergence of scaling in random networks. science, 286(5439), 509-512. 3. Bruna, J., Zaremba, W., Szlam, A., & Lecun, Y. (2014). Spectral networks and locally connected networks on graphs. In International Conference on Learning Representations (ICLR2014), CBLS, April 2014 [http://openreview.net/document/d332e77d- 459a-4af8-b3ed-55ba9662182c, http://arxiv.org/abs/1312.6203] 4. Cao, S., Lu, W., & Xu, Q. (2016, February). Deep neural networks for learning graph representations. In AAAI (Vol. 16, pp. 1145-1152). 5. Erdős, P., & Rényi, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1), 17-60. 6. Grover, A., & Leskovec, J. (2016, August). node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 855-864). 7. Grover, A., Zweig, A., & Ermon, S. (2019, May). Graphite: Iterative generative modeling of graphs. In International conference on machine learning (pp. 2434- 2444). PMLR. 8. Hamilton, W., Ying, Z., & Leskovec, J. (2017). Inductive representation learning on large graphs. In Advances in neural information processing systems (pp. 1024-1034). 9. Holland, P. W., & Leinhardt, S. (1981). An exponential family of probability distributions for directed graphs. Journal of the american Statistical association, 76(373), 33-50. 10. Kipf, T. N., & Welling, M. (2016). Variational graph auto-encoders. arXiv preprint arXiv:1611.07308. 11. Lerer, A., Wu, L., Shen, J., Lacroix, T., Wehrstedt, L., Bose, A., & Peysakhovich, A. (2019). Pytorch-biggraph: A large-scale graph embedding system. arXiv preprint arXiv:1903.12287.
39. Data Strategy and Operation Center 参考⽂献 12. Manabe, T. Nakagawa, K. (2020). Identification of B2B Brand Components and their Performanceʼs Relevance Using a Business Card Exchange Network, Pacific Rim Knowledge Acquisition Workshop, PKAW 2020. 13. Massey, K. (1997). Statistical models applied to the rating of sports teams. Bluefield College. 14. Newman, M. E., Strogatz, S. H., & Watts, D. J. (2001). Random graphs with arbitrary degree distributions and their applications. Physical review E, 64(2), 026118. 15. Perozzi, B., Al-Rfou, R., & Skiena, S. (2014, August). Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 701-710). 16. Robins, G., Pattison, P., Kalish, Y., & Lusher, D. (2007). An introduction to exponential random graph (p*) models for social networks. Social networks, 29(2), 173-191. 17. Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., & Monfardini, G. (2008). The graph neural network model. IEEE Transactions on Neural Networks, 20(1), 61-80. 18. Tang, J., Qu, M., Wang, M., Zhang, M., Yan, J., & Mei, Q. (2015, May). Line: Large-scale information network embedding. In Proceedings of the 24th international conference on world wide web (pp. 1067-1077). 19. Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., & Bengio, Y. (2017). Graph attention networks. arXiv preprint arXiv:1710.10903. 20. Wang, D., Cui, P., & Zhu, W. (2016, August). Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 1225-1234). 21. Wasserman, S., & Pattison, P. (1996). Logit models and logistic regressions for social networks: I. An introduction to Markov graphs andp. Psychometrika, 61(3), 401-425. 22. Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ʻsmall-worldʼnetworks. nature, 393(6684), 440-442.