Network alignment on big networks

Zhang, Si

Permalink

https://hdl.handle.net/2142/113885 Copy

Description

Title

Network alignment on big networks

Author(s)

Zhang, Si

Issue Date

2021-12-02

Director of Research (if dissertation) or Advisor (if thesis)

Tong, Hanghang

Doctoral Committee Chair(s)

Tong, Hanghang

Committee Member(s)

• Han, Jiawei
• Koutra, Danai
• Solomonik, Edgar

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• network alignment
• data mining
• machine learning
• graph neural networks

Abstract

In the age of big data, multiple networks naturally appear in a variety of domains, such as social network analysis, bioinformatics, finance, infrastructure and so on. Network alignment, which aims to find the node correspondences across different networks, can integrate multiple networks from different sources into a world-view network. By mining such a world-view network, one may gain considerable insights that are invisible if mining different networks separably. Networks as one common data type, share the well-known 4Vs characteristics of big data, including variety, veracity, velocity and volume, each of which brings unique challenges to the big network alignment task. Specifically, the variety characteristic of big networks depicts the rich information associated with multiple networks. Many prior network alignment methods find the node correspondences merely based on network structures while inevitably ignoring the rich node and/or edge attributes of networks. In the meanwhile, conventional methods often assume the alignment consistency among the neighboring node pairs, which could be easily violated due to the disparity among various networks. Despite the emergence of the sites and tools that enable to link entities, there still exist the bottlenecks of collecting the networked data, such as the privacy issues in social networks. Thus, real-world networks are often noisy and incomplete with missing edges. However, it still remains a daunting task on how to deal with the incompleteness and analyze the robustness of network alignment owing to the veracity characteristic. The velocity of big networks indicates that real-world networks are often dynamically changing. The dynamics behind multiple networks may benefit network alignment from the temporal information of nodes and edges in addition to the static structural information of networks. Yet, how to design the dynamic alignment model still remains an open problem. Given the sheer volume of large-scale networks but relatively limited computational resources, the at least quadratic complexity of many prior network alignment methods is not scalable especially when aligning networks with a large number of nodes and edges. In this way, the efficiency issue has become a fundamental challenge of big network alignment. The theme of my Ph.D. research is to address the above challenges associated with the 4Vs characteristics and align big networks. Note that we consider volume as an overarching goal so we can align big networks efficiently. First (for variety), to leverage attribute information of networks, we develop a family of algorithms FINAL that optimize the alignment consistency in terms of network structures and attributes and achieve an up to 30% improvement in terms of the alignment accuracy over the comparison methods without attributes. We also develop a novel alignment method that displace node representations to be more comparable through non-rigid point set registration. Moreover, to address network disparity issue, we design an encoder-decoder architecture NetTrans that learns network transformation functions in a hierarchical manner. Besides, we design a relational graph convolutional network based model with an adaptive negative sampling strategy to strike a balance between alignment consistency and disparity. This developed method named NextAlign achieves an at least 3% performance improvement over the best competitor. Second (for veracity), we hypothesize that network alignment and network completion mutually benefit each other and develop an effective algorithm based on multiplicative update that outperforms baseline methods on incomplete networks. In addition, we provide a robustness analysis of network alignment against structural noise. Last (for velocity), we design a representation learning model on dynamic network of networks which can leverage temporal information underlying networks and is applied for dynamic network alignment task.

Graduation Semester

2021-12

Type of Resource

Thesis

Permalink

http://hdl.handle.net/2142/113885

Copyright and License Information

Copyright 2021 Si Zhang

Owning Collections