Fast Local Graph Node Proximity Ranking
Restricted (Penn State Only)
- Author:
- Yan, Yaowei
- Graduate Program:
- Information Sciences and Technology
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- June 14, 2022
- Committee Members:
- Xiang Zhang, Chair & Dissertation Advisor
Suhang Wang, Major Field Member
Xiao Liu, Outside Unit & Field Member
Mary Beth Rosson, Program Head/Chair
Dongwon Lee, Major Field Member - Keywords:
- Random Walk
Graph Clustering
Community Detection
Link Prediction
Multi-network Analysis
Social Network
Social Recommendation
Adversarial Attack - Abstract:
- As a natural model to represent real-world relationships, graphs (or exchangeably, networks) are ubiquitous in this era of big data. Graph-based node ranking is a fundamental problem in graph analysis, serving as the basis of many applications, such as community detection (graph clustering), link prediction, and graph-based recommendation. Though some node ranking methods have been proposed in literature, they are either slow as global ranking methods, or do not fully use valuable heterogeneous information of interconnected different networks, or do not take advantage of personalized information from human users or domain experts. Also, state-of-the-art ranking methods are vulnerable to a small amount of injected adversarial fake information. This dissertation proposes fast node ranking algorithms and their applications based on rich information. In addition to a target network, we use information from additional associate networks which provide extra knowledge of connections between nodes, and thus increase node ranking accuracy. Moreover, human knowledge is enclosed to enhance the ranking performance, where seed nodes are labeled by users or domain experts. The labels of seed nodes are interpreted as colors, which leads to a novel colored random walk algorithm to largely increase the performance of random walks. Recently, graph-neural-network-based node ranking algorithms attract a lot of research interests. However, it shows in literature that graph neural networks are vulnerable towards adversarial attacks. In this dissertation, we also study the adversarial robustness of node ranking based on graph neural networks, which sheds light on how to build a robust ranking model toward adversarial fake information injection. The idea of the local proximity ranking can also be extended to general multi-query or multi-network local community detection problems, where the multiple query nodes are not known if they are from the same community or not. In this case, the membership of query nodes can be automatically learned from the network. Also, the importance of networks can also be learned from the network topology in multi-network node proximity ranking. Analyses indicate that the local proximity ranking also works for community detection in those scenarios. By both theoretical and empirical studies of the proposed ranking algorithms and their applications on node clustering, link prediction and recommendation, it shows that the proposed approaches are fast, accurate and robust in comparison with the state-of-the-art node ranking methods based on graph data.