University of Illinois Urbana-Champaign

Multi-network association: Algorithms and applications

Du, Boxin

Content Files
DU-DISSERTATION-2022.pdf

Permalink

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

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
Handle URL
https://hdl.handle.net/2142/116137
Copyright and License Information
Copyright 2022 Boxin Du

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois