Due to regulations like the Right to be Forgotten, there is growing demand for removing training data and its influence from models. Since full retraining is costly, various machine unlearning methods have been proposed. In this paper, we firstly present an efficient knowledge graph (KG) unlearning algorithm. We remark that KG unlearning is nontrivial due to the distinctive structure of KG and the semantic relations between entities. Also, unlearning by estimating the influence of removed components incurs significant computational overhead when applied to large-scale knowledge graphs. To this end, we define an influence function for KG unlearning and propose to approximate the model's sensitivity without expensive computation of first-order and second-order derivatives for parameter updates. Specifically, we use Taylor expansion to estimate the parameter changes caused by data removal. Given that the first-order gradients and second-order derivatives dominate the computational load, we use the Fisher matrices and zeroth-order optimization to approximate the inverse-Hessian vector product without constructing the computational graphs. Our experimental results demonstrate that the proposed method outperforms other state-of-the-art graph unlearning baselines significantly in terms of unlearning efficiency and unlearning quality. Our code is released at https://github.com/NKUShaw/ZOWFKGIF.

Road traffic forecasting is crucial in real-world intelligent transportation scenarios like traffic dispatching and path planning in city management and personal traveling. Spatio-temporal graph neural networks (STGNNs) stand out as the mainstream solution in this task. Nevertheless, the quadratic complexity of remarkable dynamic spatial modeling-based STGNNs has become the bottleneck over large-scale traffic data. From the spatial data management perspective, we present a novel Transformer framework called PatchSTG to efficiently and dynamically model spatial dependencies for large-scale traffic forecasting with interpretability and fidelity. Specifically, we design a novel irregular spatial patching to reduce the number of points involved in the dynamic calculation of Transformer. The irregular spatial patching first utilizes the leaf K-dimensional tree (KDTree) to recursively partition irregularly distributed traffic points into leaf nodes with a small capacity, and then merges leaf nodes belonging to the same subtree into occupancy-equaled and non-overlapped patches through padding and backtracking. Based on the patched data, depth and breadth attention are used interchangeably in the encoder to dynamically learn local and global spatial knowledge from points in a patch and points with the same index of patches. Experimental results on four real world large-scale traffic datasets show that our PatchSTG achieves train speed and memory utilization improvements up to 10x and 4x with the state-of-the-art performance.

Explaining black-box models is fundamental to gaining trust and deploying these models in real applications. As existing explanation methods have been shown to lack robustness against adversarial perturbations, there has been a growing interest in generating robust explanations. However, existing works resort to empirical defense strategies and these heuristic methods fail against powerful adversaries. In this paper, we certify the robustness of explanations motivated by the success of randomized smoothing. Specifically, we compute a tight radius in which the robustness of the explanation is certified. While a challenge is how to formulate the robustness of the explanation mathematically, we quantize the explanation into discrete spaces to mimic classification in randomized smoothing. To address the high computational cost of randomized smoothing, we introduce randomized gradient smoothing. Also, we explore the robustness of the semantic explanation by certifying the robustness of capsules. In the experiment, we demonstrate the effectiveness of our method on benchmark datasets from the perspectives of post-hoc explanation and semantic explanation respectively. Our work is a promising step towards filling the gap between the theoretical robustness bound and empirical explanations. Our code has been released at https://github.com/NKUShaw/CertifiedExplanation.

Predicting traffic accident hotspots is crucial for ensuring public safety, improving transport planning, and reducing transportation costs. Traditional deep learning models, such as Transformers and LSTMs, have been successful in this field but fail to integrate critical attributes essential for accurate prediction. To address these limitations, we propose utilizing a Temporal Convolutional Network (TCN), which efficiently learns spatial, temporal, and other external factors integral to accident hotspot prediction. Our proposed TCN architecture 1 demonstrate superior performance over state-of-the-art methods, offering valuable insights for proactive accident mitigation.

Graph Neural Networks (GNNs) have shown promising performance in many applications, yet remain extremely difficult to train over large-scale graph datasets. Existing weight pruning techniques can prune out the layer weights; however, they cannot fully address the high computation complexity of GNN inference, caused by large graph size and complicated node connections. In this paper, we propose an Iterative Gradient Rank Pruning (IGRP) algorithm to find graph lottery tickets (GLT) of GNNs where each GLT includes a pruned adjacency matrix and a sub-network. Our IGRP can avoid layer collapse and the winning ticket achieves Maximal critical compression. We evaluate the proposed method on small-scale (Cora and Citeseer), medium-scale (PubMed and Wiki-CS), and large-scale (Ogbn-ArXiv and Ogbn-Products) graph datasets. We demonstrate that both Single-shot and Multi-shot of IGRP outperform the state-of-the-art unified GNN sparsification (UGS) framework on node classification. The source code can be found in https://github.com/poweiharn/IGRP_GNN.

The study of protein-ligand interaction is critical for gaining a thorough understanding of biological processes and uncovering disease mechanisms. This exciting topic has attracted much interest. Accurate and reliable prediction of the protein-ligand interactions can be challenging because the model requires successful transformation and creation of the computer interpretable representations of both protein and ligand information. Despite the recent successes in the application of the convolution neural network and graph neural network-based approaches, they remain largely under-explored due to the significant challenges in modeling the complex representations and capturing the inherent correlation between protein and ligand from low-level representations. Several challenges include: 1) Structural-free protein representation learning model is needed to successfully discover the inner correlation between protein and ligand. 2) Limited open literature to date has focused on the generalizability and interpretability for the protein-ligand interface prediction. 3) The length of the protein sequences and the complexity of the protein-ligand binding complex make the problem hard to handle. To address these problems, we propose an end-to-end model framework APIP that could learn effective representations across compound atoms and protein residues for protein-ligand interface prediction. Our experimental results show that APIP makes more accurate predictions than the state-of-the-art method in this task and demonstrate the potential of the attention-based method for drug discovery.

Context has been recognized as an important factor to consider in personalized recommender systems. Particularly in location-based services (LBSs), a fundamental task is to recommend to a mobile user where he/she could be interested to visit next at the right time. Additionally, location-based social networks (LBSNs) allow users to share location-embedded information with friends who often co-occur in the same or nearby points-of-interest (POIs) or share similar POI visiting histories, due to the social homophily theory and Tobler's first law of geography. So, both the time information and LBSN friendship relations should be utilized for POI recommendation. Tensor completion has recently gained some attention in time-aware recommender systems. The problem decomposes a user-item-time tensor into low-rank embedding matrices of users, items and times using its observed entries, so that the underlying low-rank subspace structure can be tracked to fill the missing entries for time-aware recommendation. However, these tensor completion methods ignore the social-spatial context information available in LBSNs, which is important for POI recommendation since people tend to share their preferences with their friends, and near things are more related than distant things. In this paper, we utilize the side information of social networks and POI locations to enhance the tensor completion model paradigm for more effective time-aware POI recommendation. Specifically, we propose a regularization loss head based on a novel social Hausdorff distance function to optimize the reconstructed tensor. We also quantify the popularity of different POIs with location entropy to prevent very popular POIs from being over-represented hence suppressing the appearance of other more diverse POIs. To address the sensitivity of negative sampling, we train the model on the whole data by treating all unlabeled entries in the observed tensor as negative, and rewriting the loss function in a smart way to reduce the computational cost. Through extensive experiments on real datasets, we demonstrate the superiority of our model over state-of-the-art tensor completion methods.

Tensor decomposition aims to factorize an input tensor into a number of latent factors. Due to the low-rank nature of tensor in real applications, the latent factors can be used to perform tensor completion in numerous tasks, such as knowledge graph completion and timely recommendation. However, existing works solve the problem in Euclidean space, where the tensor is decomposed into Euclidean vectors. Recent studies show that hyperbolic space is roomier than Euclidean space. With the same dimension, a hyperbolic vector can represent richer information (e.g., hierarchical structure) than a Euclidean vector. In this paper, we propose to decompose tensor in hyperbolic space. Considering that the most popular optimization tools (e.g, SGD, Adam) have not been generalized in hyperbolic space, we design an adaptive optimization algorithm according to the distinctive property of hyperbolic manifold. To address the non-convex property of the problem, we adopt gradient ascent in our optimization algorithm to avoid getting trapped in local optimal landscapes. We conduct experiments on various tensor completion tasks and the result validates the superiority of our method over these baselines that solve the problem in Euclidean space.

Matrix completion is a well-known approach for recommender systems. It predicts the values of the missing entries in a sparse user-item interaction matrix, based on the low-rank structure of the rating matrix. However, existing matrix completion methods do not take node polysemy and side information of social relationships into consideration, which can otherwise further improve the performance. In this paper, we propose a novel matrix completion method that employs both users’ friendships and rating entries to predict the missing values in a user-item matrix. Our approach adopts a graph-based modeling where nodes are users and items, and two types of edges are considered: user friendships and user-item interactions. Polysemy-aware node features are extracted from this heterogeneous graph through a graph convolution network by considering the multifaceted factors for edge formation, which are then connected to a hybrid loss function with two heads: (1) a social-homophily head to address node polysemy, and (2) an error head for user-item rating regression. The latter is formulated on all matrix entries to combat the sensitivity of negative sampling of the vast majority of missing entries during training, with a smart technique to reduce the time complexity. Extensive experiments over real datasets verify that our model outperforms the state-of-the-art matrix completion methods by a significant margin.

Knowing the locations of tweets can benefit a wide variety of applications such as venue recommendation, event detection, and monitoring disaster outbreaks. However, the problem of fine-grained tweet geolocation prediction is challenging since tweets are short and therefore may not contain any geo-indicative words or may contain ambiguous, noisy information. Existing solutions either yield an unsatisfactory accuracy in practical applications or make predictions that even experts struggle to interpret, failing to engender sufficient trust and actionability for real-world deployment. Our paper presents a tweet geolocation prediction framework, EDGE (Entity-Diffusion Gaussian Ensemble), which delivers predictions that are both accurate and highly interpretable without requiring any additional contextual information such as user profile and location history. In EDGE, we cast the geolocation problem as a neutral network optimization problem by learning probabilistic generative models. Compared with existing works, EDGE has two distinctive features: (1) the inference builds on mining the correlation between non geo-indicative entities and geo-indicative entities by diffusing their semantic embeddings over the constructed graph neural network (Entity Diffusion) and (2) each prediction result is represented as a Gaussian mixture instead of specific geographical coordinates (Gaussian Ensemble). Extensive experiments using real-world tweet datasets validate the superiority of EDGE over the state of the art in terms of all distance-based and POI-based metrics.

Real-time traffic prediction is essential for mitigating traffic congestion and reducing travel time. Recent advancement in graph convolutional network (GCN) has motivated a series of GCN-based models for traffic forecasting on an urban road network. However, these graph-based methods cannot capture the intricate dependencies of consecutive road segments such as no left turn, and dynamic spatial dependency. In this paper, we propose Trajectory WaveNet, or T-wave in short, a traffic forecasting model that utilizes the actual vehicle trajectories to capture the above intricate dependencies to improve prediction performance. Both trajectories and traffic data are obtained from the floating car data collected by ridesharing companies such as DiDi. T-wave treats vehicle trajectories as first-class citizens, and applies dilated causal convolutions along both the temporal dimension (i.e., recent, daily-periodic and weekly-periodic historical traffic data) and the spatial dimension (i.e., trajectories). For effective training, a trajectory mini-batch sampling technique is devised considering both spatial and temporal proximity. Extensive experiments on real datasets show that T-wave consistently bests the state-of-the-art models.

Ridesharing companies such as Ube and DiDi provide ride-hailing services where passengers and drivers are matched via mobile apps. As a result, large amounts of vehicle trajectories and vehicle speed data are collected that can be used for traffic prediction. The recent popularity of graph convolutional networks (GCNs) has opened up new possibilities for real-time traffic prediction and many GCN-based models have been proposed to capture the spatial correlation on the urban road network. However, the graph-based approaches fail to capture the intricate dependencies of consecutive road segments that are well captured by trajectories.

With the rapid progress of global urbanization and function division among different geographical regions, it is of urgent need to develop methods that can find regions of desired future function distributions in applications. For example, a company tends to open a new branch in a region where the growth trend of industrial sectors fits its strategic goals, or is similar to that of an existing company location; while a job hunter tends to search regions where his/her expertise aligns with the industrial growth trend providing sufficient job opportunities to sustain future employment and job-hopping.