We study structural clustering on graphs in dynamic scenarios, where graphs can be updated by arbitrary insertions or deletions of edges/vertices. Our goal is to efficiently compute structural clustering results under three conditions: 1) for any clustering parameters ε and μ provided on the fly, 2) for arbitrary graph update patterns, and 3) for all typical similarity measurements. To achieve this, we propose an algorithm named VD-STAR that is much simpler yet more efficient than state of the art. With a theoretical guarantee on clustering result's quality, VD-STAR can produce clustering results with up to 99.9% accuracy. Moreover, VD-STAR is easy to implement as it just needs to maintain sorted linked lists and hash tables, making it highly deployable in practice. Most importantly, VD-STAR improves the expected per-update time bound from state-of-the-art O(log2 n), which relies on specific assumption on update pattern, to O(log n) amortized in expectation without any assumption on update pattern. We further design two variants of VD-STAR to enhance its empirical performance. Experimental results show that our algorithms consistently outperform state-of-the-art competitors by up to 9,315 times in update time across nine real datasets, while maintaining similar update time and memory usage.

We study the problem of interactive graph search (IGS). Given a query entity$\varphi$, the goal is to identify the target concept in a directed acyclic graph (DAG) concept hierarchy$H$, which best describes$\varphi$, through interactions with an oracle. In each interaction, a question in the form of “Does$\varphi$belong to concept$u?$” is asked and the oracle can only answer either YES or NO. The efficiency of an IGS algorithm is measured by the number of questions asked, to identify the target concept, which is referred to as query cost. In theory aspect, we propose the Target-Sensitive IGS (TS-IGS) algorithm that achieves a query cost complexity of$O(\log n. \log\frac{L}{\log n}+d\cdot\log_{d}n)$, where$L$is the length of the path from the root of$H$to the target concept. When$L\in O(\log n)$, our TS-IGS matches the known lower bound [1]. In practice aspect, we propose an algorithm called Example-Guided IGS (EG-IGS) that exploits the knowledge of entities and asks promising questions guided by examples similar to$\varphi$. We prove that EG-IGS achieves a finer-grained query cost bound than that of TS-IGS, and is extremely efficient in practice. Extensive experiments on six real-world datasets (including images, texts, and gene sequences) show that our EG-IGS outperforms all the existing competitors by up to two orders of magnitude in terms of query cost, and is robust in various settings. To further demonstrate the real feasibility of our EG-IGS technique, we develop a fully-automatic Amazon product categorization demo system with GPT-3.5 serving as the oracle.

Traffic prediction is an important and yet highly challenging problem due to the complexity and constantly changing nature of traffic systems. To address the challenges, we propose a graph and attentive multi-path convolutional network (GAMCN) model to predict traffic conditions such as traffic speed across a given road network into the future. Our model focuses on the spatial and temporal factors that impact traffic conditions. To model the spatial factors, we propose a variant of the graph convolutional network (GCN) named LPGCN to embed road network graph vertices into a latent space, where vertices with correlated traffic conditions are close to each other. To model the temporal factors, we use a multi-path convolutional neural network (CNN) to learn the joint impact of different combinations of past traffic conditions on the future traffic conditions. Such a joint impact is further modulated by an attention generated from an embedding of the prediction time, which encodes the periodic patterns of traffic conditions. We evaluate our model on real-world road networks and traffic data. The experimental results show that our model outperforms state-of-art traffic prediction models by up to 18.9% in terms of prediction errors and 23.4% in terms of prediction efficiency.

Shortest-path distances on road networks have many applications such as finding nearest places of interest (POI) for travel recommendations. To compute a shortest-path distance, traditional approaches traverse the road network to find the shortest path and return the path length. When the distances are needed first (e.g., to rank POIs) while the shortest paths may be computed later (e.g., after a POI is chosen), one may precompute and store the distances, and answer distance queries by simple lookups. This approach, however, falls short in the worst-cast space cost – O(n2) for n vertices even with various optimizations. To address these limitations, we propose to learn an embedding for every vertex that preserves its distances to the other vertices. We then train a multi-layer perceptron (MLP) to predict the distance between two vertices given their embeddings. We thus achieve fast distance predictions without a high space cost. Experimental results on real road networks confirm these advantages. Meanwhile, our approach is up to 97% more accurate than the state-of-the-art approaches for distance predictions.