Multi-network association: Algorithms and applications

Du, Boxin

Permalink

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

Description

Title

Multi-network association: Algorithms and applications

Author(s)

Du, Boxin

Issue Date

2022-06-01

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

Tong, Hanghang

Doctoral Committee Chair(s)

Tong, Hanghang

Committee Member(s)

• Banerjee, Arindam
• Zhai, Chengxiang
• Tang, Jian

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)

• multi-network association
• graph mining
• machine learning
• algorithm
• application

Abstract

Networks extracted from multiple sources and platforms or from multiple instances of identical domains form the multi-network, such as large social networks collected from Facebook and Instagram, medium-scaled networks of chemical compound and proteins extracted from chemical/protein interaction, etc. Multi-network association refers to the node associations or proximities in a multi-network model, which goes beyond the boundary of node associations of a single simple network. Multi-network association offers a fundamental primitive for mining multi-networks, in the sense that it reveals the unique, collective relations among node sets, which can not be captured by mining individual networks separately. Although network mining has become a ubiquitous tool of knowledge discovery for researchers and practitioners in diverse application domains, research in the multi-network association is still relatively limited, owing to the following three major challenges. First ( Problem formulation), how do we explicitly formulate the multi-network association inference problem in various multi-network scenarios, such as multiple plain/attributed networks, multi-layered networks, hypergraphs, etc.? How do we implicitly preserve multi-network association in an embedding model which is targeted at multi-network mining tasks? Second (Computational complexity), how can we develop efficient algorithms for mitigating the high complexity of the problems defined on multi-networks, in terms of both time and space complexity? Third (Application), how will the multi-network association empower or enable novel applications on multi-network data? To what extent can the multi-network association based methods boost the classic multi-network mining tasks? In this Ph.D. thesis, an in-depth study of the multi-network association is formally discussed and analyzed to jointly tackle the aforementioned challenges. Specially, the research works from this thesis are organized based on the taxonomy of the network associations (i.e. pairwise vs. high-order association), and the taxonomy of the core algorithmic techniques (i.e. numerical vs. neural methods). First (pairwise association with numerical techniques), we develop a family of fast solvers (FASTEN) for the Sylvester equation, which lays the foundation of numerous multi-network mining tasks. We further introduce a novel application, namely interactive subgraph matching, empowered by the Sylvester equation. Second (pairwise association with neural techniques), we extend the boundary of the numerical techniques for pairwise association and design Sylvester Multi-Graph Neural Network model. As a generalization of traditional Sylvester equation, its flexible architecture could incorporate numerical features, and it is able to be adapted to various downstream tasks. We then show that how such technique could be successfully applied on the application of social recommendation, to achieve up to 30% improvement over baseline methods. Third (high-order association with numerical techniques), we design a family of algorithms (i.e., SyTE) for multi-way association problem on both plain and attributed networks. It shows applicability in a variety of multi-network mining tasks, such as multi-network alignment. Forth (high-order association with neural techniques), we develop an unsupervised multi-resolution multi-network embedding model to simultaneously embed network elements of different resolutions and different networks into the same embedding space. We also present a hypergraph representation learning model via pre-training strategy, with a real-world case study on the inconsistent variation family detection problem for Amazon selection and catalog system.

Graduation Semester

2022-08

Type of Resource

Thesis

Copyright and License Information

Copyright 2022 Boxin Du

Owning Collections