Graph Game Embedding

Authors

  • Xiaobin Hong Nanjing University of Science and Technology
  • Tong Zhang Nanjing University of Science and Technology
  • Zhen Cui Nanjing University of Science and Technology
  • Yuge Huang Tencent YouTu
  • Pengcheng Shen Tencent YouTu
  • Shaoxin Li Tencent YouTu
  • Jian Yang Nanjing University of Science and Technology

DOI:

https://doi.org/10.1609/aaai.v35i9.16942

Keywords:

Representation Learning, Graph Mining, Social Network Analysis & Community, Games, Graph-based Machine Learning

Abstract

Graph embedding aims to encode nodes/edges into low-dimensional continuous features, and has become a crucial tool for graph analysis including graph/node classification, link prediction, etc. In this paper we propose a novel graph learning framework, named graph game embedding, to learn discriminative node representation as well as encode graph structures. Inspired by the spirit of game learning, node embedding is converted to the selection/searching process of player strategies, where each node corresponds to one player and each edge corresponds to the interaction of two players. Then, a utility function, which theoretically satisfies the Nash Equilibrium, is defined to measure the benefit/loss of players during graph evolution. Furthermore, a collaboration and competition mechanism is introduced to increase the discriminant learning ability. Under this graph game embedding framework, considering different interaction manners of nodes, we propose two specific models, named paired game embedding for paired nodes and group game embedding for group interaction. Comparing with existing graph embedding methods, our algorithm possesses two advantages: (1) the designed utility function ensures the stable graph evolution with theoretical convergence and Nash Equilibrium satisfaction; (2) the introduced collaboration and competition mechanism endows the graph game embedding framework with discriminative feature leaning ability by guiding each node to learn an optimal strategy distinguished from others. We test the proposed method on three public datasets about citation networks, and the experimental results verify the effectiveness of our method.

Downloads

Published

2021-05-18

How to Cite

Hong, X., Zhang, T., Cui, Z., Huang, Y., Shen, P., Li, S., & Yang, J. (2021). Graph Game Embedding. Proceedings of the AAAI Conference on Artificial Intelligence, 35(9), 7711-7720. https://doi.org/10.1609/aaai.v35i9.16942

Issue

Section

AAAI Technical Track on Machine Learning II