Network Alignment: Recent Advances and Future Trends

CIKM 2020 Tutorial

Abstract

In the era of big data, networks are often from multiple sources such as the social networks of diverse platforms (e.g., Facebook, Twitter), protein-protein interaction (PPI) networks of different tissues, transaction networks at multiple financial institutes and knowledge graphs derived from a variety of knowledge bases (e.g., DBpedia, Freebase, etc.). The very first step before exploring insights from these multi-sourced networks is to integrate and unify different networks. In general, network alignment is such a task that aims to uncover the correspondences among nodes across different graphs. The challenges of network alignment include: (1) the heterogeneity of the multi-sourced networks, e.g., different structural patterns, (2) the variety of the real-world networks, e.g., how to leverage the rich contextual information, and (3) the computational complexity. The goal of this tutorial is to (1) provide a comprehensive overview of the recent advances in network alignment, and (2) identify the open challenges and future trends. We believe this can be beneficial to numerous application problems, and attract both researchers and practitioners from both data mining area and other interdisciplinary areas. In particular, we start with introducing the backgrounds, problem definition and key challenges of network alignment. Next, our emphases will be on (1) the recent techniques on addressing network alignment problem and other related problems with a careful balance between the algorithms and applications, and (2) the open challenges and future trends.

Descriptions

Detailed descriptions of this tutorial can be found here.

Tutorial Slides

Slides: [pdf]

Outline

  • Introduction (20 minutes)

    • Motivations

    • Problem definitions and related settings

    • Key challenges

    • Traditional solutions and limitations

  • Part I: Network Alignment Algorithms: Recent Advances (90 minutes)

    • Pairwise network alignment

    • Collective network alignment

    • High-order network alignment

    • Hierarchical network alignment

    • Knowledge graph alignment

    • Cross-layer dependency inference

  • Part II: Network Alignment Applications (40 minutes)

    • Applications in social analysis

    • Applications in bioinformatics

    • Applications in knowledge completion

    • Applications in security

  • Part III: Future Research Directions (30 minutes)

    • Big network alignment

    • Adversarial network alignment

    • Active network alignment

    • Integrated network alignment

Speakers' Bio

Si Zhang. He is currently a Ph.D student in the Department of Computer Science at University of Illinois at Urbana-Champaign. His current research interests lie in the large-scale data mining and machine learning, especially graph mining such as network alignment, dense subgraph detection and graph neural networks. He has been working on network alignment for 4 years, which results in several publications at major conferences and journals, such as KDD, WWW, ICDM, SDM, TKDE, etc. For more information, please refer to his personal website at sizhang2.web.illinois.edu/.

Hanghang Tong. He is an associate professor with the Department of Computer Science at University of Illinois at Urbana-Champaign. Before that he was an associate professor at School of Computing, Informatics, and Decision Systems Engineering (CIDSE), Arizona State University. He received his M.Sc. and Ph.D. degrees from Carnegie Mellon University in 2008 and 2009, both in Machine Learning. His research interest is in large scale data mining for graphs and multimedia. He has received several awards, including SDM/IBM Early Career Data Mining Research award (2018), NSF CAREER award (2017), ICDM 10-Year Highest Impact Paper award (2015) and four best paper awards (TUP'14, CIKM'12, SDM'08, ICDM'06). He is the Editor-in-Chief of SIGKDD Explorations (ACM), an action editor of Data Mining and Knowledge Discovery (Springer), and an associate editor of Knowledge and Information Systems (Springer) and Neurocomputing Journal (Elsevier); and has served as a program committee member in multiple data mining, database and artificial intelligence venues (e.g., SIGKDD, SIGMOD, AAAI, WWW, CIKM, etc.). For more information, please refer to his personal website at tonghanghang.org/. He has given several tutorials at top-tier conferences, such as IEEE Big Data 2015, SDM 2016, WSDM 2018, KDD 2018.

References

  • Chen, Chen, et al. "FASCINATE: fast cross-layer dependency inference on multi-layered networks." Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2016.

  • Heimann, Mark, et al. "Regal: Representation learning-based graph alignment." Proceedings of the 27th ACM International Conference on Information and Knowledge Management. ACM, 2018.

  • Koutra, Danai, Hanghang Tong, and David Lubensky. "Big-align: Fast bipartite graph alignment." 2013 IEEE 13th International Conference on Data Mining. IEEE, 2013.

  • Liu, Li, et al. "Aligning Users across Social Networks Using Network Embedding." IJCAI. 2016.

  • Mohammadi, Shahin, et al. "Triangular Alignment TAME: A Tensor-Based Approach for Higher-Order Network Alignment." IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) 14.6 (2017): 1446-1458.

  • Xu, Hongteng, et al. "Gromov-wasserstein learning for graph matching and node embedding." arXiv preprint arXiv:1901.06003 (2019).

  • Xu, Kun, et al. "Cross-lingual knowledge graph alignment via graph matching neural network." arXiv preprint arXiv:1905.11605 (2019).

  • Zafarani, Reza, and Huan Liu. "Connecting users across social media sites: a behavioral-modeling approach." Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2013.

  • Zhang, Jiawei, and S. Yu Philip. "Multiple anonymized social networks alignment." 2015 IEEE International Conference on Data Mining. IEEE, 2015.

  • Zhang, Si, and Hanghang Tong. "Final: Fast attributed network alignment." Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2016.

  • Zhang, Si, et al. "Multilevel Network Alignment." The World Wide Web Conference. ACM, 2019.