TOWARDS ROBUST AND EFFICIENT GRAPH NEURAL NETWORKS

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "TOWARDS ROBUST AND EFFICIENT GRAPH NEURAL NETWORKS"

By

Mr. Haoyang LI


Abstract:

Graph Neural Networks (GNNs) have achieved great success in various graph
tasks, such as node classification and link prediction. Generally, they learn
node representations by recursively aggregating information from neighbors.
However, recent studies have revealed two significant issues associated with
the deployment of GNNs in real-world applications. First, GNNs are vulnerable
to adversarial attacks on graph data, including topology modifications and
feature perturbations. The attackers can slightly manipulate graph data to
mislead GNNs into misclassifying node labels or increasing the predicted link
probability of a user toward a target item for promotion. Second, in many
applications, such as Twitter and Facebook, graphs are dynamic and evolving
with continuous graph events, such as node feature changes and graph structure
updates. These events require the node representations to be updated
accordingly. Currently, due to the real-time requirement, how to efficiently
and reliably update node representations under continuous graph events is still
an open problem.

In this thesis, we first investigate the robustness of GNNs, focusing on node
classification and link prediction tasks. Specifically, in the node
classification task, we propose a pure black-box attacker PEEGA, which is
restricted to accessing node features and graph topology for practicability.
Furthermore, we reveal that effective attackers enable GNNs to misclassify the
labels of nodes by obscuring the neighbor distribution of nodes. As a result,
GNNs are unable to recognize nodes. Based on this observation, we propose a GNN
defender GNAT that incorporates three augmented graphs, i.e., a topology graph,
a feature graph, and an ego graph, to enhance the distinguishability of node
contexts. Besides, in the link prediction task, we propose an attacker DADA,
which incorporates difficulty-aware and diversity-aware objectives. These
objectives enable easy users from various communities, who have a higher
tendency to the target item, to contribute more weight when optimizing
attackers. By incorporating these two objectives, the attack behaviors of DADA
can increase the link probability of diverse easy users towards the target
item, thereby enabling platforms to promote the target item to more users.
Based on these observations, we propose two solutions (e.g., attack behavior
detection and adversarial training) to help GNNs resist attacks for link
prediction.

Second, we propose an efficient and reliable graph neural network framework,
namely EARLY, to update node representations for dynamic graphs. When graph
events arrive, we first identify the top-k influential nodes that are most
affected by the new graph events. Specifically, we theoretically analyze the
impact of graph events on node representations. Based on this, we formulate the
top-k node selection problem and prove that this problem is NP-hard. We then
propose a greedy algorithm with a theoretical guarantee. Also, we reveal that
existing GNNs may sample similar and redundant neighbors to update node
representations, which cannot reflect the distribution of all neighbors.
Consequently, node representations aggregated on these redundant neighbors are
not reliable, because they may differ from the node representations aggregated
on all neighbors. Thus, we propose a diversity-aware layer-wise sampling
approach to sample diverse neighbors for these selected nodes in a layer-wise
manner. We theoretically demonstrate that our algorithm can learn more reliable
node representations with lower expectation error.

We demonstrate the superior performance of the proposed approaches for the
above tasks against state-of-the-art techniques, through extensive experiments
on real-world datasets. In the end, we conclude this thesis with future
research directions of improving the robustness and efficiency of GNNs.


Date:                   Wednesday, 23 August 2023

Time:                   10:00am - 12:00noon

Venue:                  Room 5501
                        lifts 25/26

Chairperson:            Prof. Huai-Liang CHANG (MATH)

Committee Members:      Prof. Lei CHEN (Supervisor)
                        Prof. Qiong LUO
                        Prof. Dan XU
                        Prof. Can YANG (MATH)
                        Prof. Jianliang XU (HKBU)


**** ALL are Welcome ****