Multi-network association: Algorithms and applications

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2022

Author dc:creator

• Du, Boxin

Contributors dc:contributor

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

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

Statement dc:rights

• Copyright 2022 Boxin Du

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F116137