Heterogeneous information networks (HIN) have gained increasing popularity in recent years for capturing complex relations between diverse types of nodes. Meta-structures are proposed as a useful tool to identify the important patterns in HINs, but hand-crafted meta-structures pose significant challenges for scaling up, drawing wide research attention towards developing automatic search algorithms. Previous efforts primarily focused on searching for meta-structures with good empirical performance, overlooking the importance of human comprehensibility and generalizability. To address this challenge, we draw inspiration from the emergent reasoning abilities of large language models (LLMs). We propose ReStruct, a meta-structure search framework that integrates LLM reasoning into the evolutionary procedure. ReStruct uses a grammar translator to encode the meta-structures into natural language sentences, and leverages the reasoning power of LLMs to evaluate their semantic feasibility. Besides, ReStruct also employs performance-oriented evolutionary operations. These two competing forces allow ReStruct to jointly optimize the semantic explainability and empirical performance of meta-structures. Furthermore, ReStruct contains a differential LLM explainer to generate and refine natural language explanations for the discovered meta-structures by reasoning through the search history. Experiments on eight representative HIN datasets demonstrate that ReStruct achieves state-of-the-art performance in both recommendation and node classification tasks. Moreover, a survey study involving 73 graduate students shows that the discovered meta-structures and generated explanations by ReStruct are substantially more comprehensible. Our code and questionnaire are available at https://github.com/LinChen-65/ReStruct.

Understanding the impact of COVID-19 on urban life rhythms is crucial for accelerating the return-to-normal progress and envisioning more resilient and inclusive cities. While previous studies either depended on small-scale surveys or focused on the response to initial lockdowns, this paper uses large-scale location service data to systematically analyze the urban mobility behavior changes across three distinct phases of the pandemic, i.e., pre-pandemic, lockdown, and reopen. Our analyses reveal two typical patterns that govern the mobility behavior changes in most urban venues: daily life-centered urban venues go through smaller mobility drops during the lockdown and more rapid recovery after reopening, while work-centered urban venues suffer from more significant mobility drops that are likely to persist even after reopening. Such mobility behavior changes exert deeper impacts on the underlying social fabric, where the level of mobility reduction is positively correlated with the experienced segregation at that urban venue. Therefore, urban venues undergoing more mobility reduction are also more filled with people from homogeneous socio-demographic backgrounds. Moreover, mobility behavior changes display significant heterogeneity across geographical regions, which can be largely explained by the partisan inclination at the state level. Our study shows the vast potential of location service data in deriving a timely and comprehensive understanding of the social dynamic in urban space, which is valuable for informing the gradual transition back to the normal lifestyle in a “post-pandemic era”.

With the advent of the COVID-19 pandemic, the shortage in medical resources became increasingly more evident. Therefore, efficient strategies for medical resource allocation are urgently needed. However, conventional rule-based methods employed by public health experts have limited capability in dealing with the complex and dynamic pandemic-spreading situation. In addition, model-based optimization methods such as dynamic programming (DP) fail to work since we cannot obtain a precise model in real-world situations most of the time. Model-free reinforcement learning (RL) is a powerful tool for decision-making; however, three key challenges exist in solving this problem via RL: (1) complex situations and countless choices for decision-making in the real world; (2) imperfect information due to the latency of pandemic spreading; and (3) limitations on conducting experiments in the real world since we cannot set up pandemic outbreaks arbitrarily. In this article, we propose a hierarchical RL framework with several specially designed components. We design a decomposed action space with a corresponding training algorithm to deal with the countless choices, ensuring efficient and real-time strategies. We design a recurrent neural network–based framework to utilize the imperfect information obtained from the environment. We also design a multi-agent voting method, which modifies the decision-making process considering the randomness during model training and, thus, improves the performance. We build a pandemic-spreading simulator based on real-world data, serving as the experimental platform. We then conduct extensive experiments. The results show that our method outperforms all baselines, which reduces infections and deaths by 14.25% on average without the multi-agent voting method and up to 15.44% with it.

We investigate multiset membership lookup prob-lem, a pivotal functionality in many computing and networking paradigms. We devise compact data structures and lookup algorithms that are amendable for hardware implementation, while guaranteeing high lookup accuracy and supporting interactive query processing. We first propose multi-hash color table, a variant of Bloom filter, to encode subset IDs compactly and map the ID of an item to its subset ID. We further construct a more balanced data structure called balanced multi-hash color table to improve the compactness by integrating load balancing.

Given a dataset$\mathcal S$composed of$g$subsets with each data item belonging to one of them,multiset membership lookuptakes an item$e$as input and outputs a binary answer whether$e\in {\mathcal S}$and, in case of yes, the ID of the subset to which$e$belongs. Overlaid upon while more sophisticated than the canonical membership lookup, multiset membership lookup emerges as a pivotal functionality in many computing and networking paradigms. The quest to achieve high-speed, high-accuracy lookup with limited memory cost makes lookup algorithm design a challenging task, particularly when the data items arrive as a stream. In this paper, we devise compact data structures and lookup algorithms that are amendable for hardware implementation, while guaranteeing high lookup accuracy and supporting interactive query processing. We first proposemulti-hash color table, a variant of Bloom filter, to encode subset IDs compactly and map the ID of an item to its subset ID. We further construct a more balanced data structure calledbalanced multi-hash color tableto improve the compactness by integrating the state-of-the-art load balancing technique. We complete our work by addressing the case ofbatch arrivalsand design a batched recording algorithm optimizing the memory efficiency. We give both theoretical and empirical analysis to characterize and evaluate the performance of the proposed algorithms in terms of lookup accuracy, memory and access efficiency.

Facing the outbreak of COVID-19, shortage in medical resources becomes increasingly outstanding. Therefore, efficient strategies for medical resource allocation are urgently called for. Reinforcement learning (RL) is powerful for decision making, but three key challenges exist in solving this problem via RL: (1) complex situation and countless choices for decision making in the real world; (2) only imperfect information are available due to the latency of pandemic spreading; (3) limitations on conducting experiments in real world since we cannot set pandemic outbreaks arbitrarily. In this paper, we propose a hierarchical reinforcement learning method with a corresponding training algorithm. We design a decomposed action space to deal with the countless choices to ensure efficient and real time strategies. We also design a recurrent neural network based framework to utilize the imperfect information obtained from the environment. We build a pandemic spreading simulator based on real world data, serving as the experimental platform. We conduct extensive experiments and the results show that our method outperforms all the baselines, which reduces infections and deaths by 14.25% on average.

Facing the worldwide rapid spreading of COVID-19 pandemic, we need to understand its diffusion in the urban environments with heterogeneous population distribution and mobility. However, challenges exist in the choice of proper spatial resolution, integration of mobility data into epidemic modelling, as well as incorporation of unique characteristics of COVID-19.

Map matching is important in many trajectory based applications like route optimization and traffic schedule, etc. As the widely used methods, Hidden Markov Model and its variants are well studied to provide accurate and efficient map matching service. However, HMM based methods fail to utilize the value of enormous trajectory big data, which are useful for the map matching task. Furthermore, with many following-up works, they are still easily influenced by the noisy records, which are very common in the real system. To solve these problems, we revisit the map matching task from the data perspective, and propose to utilize the great power of data to help solve these problems. We build a deep learning based model to utilize all the trajectory data for joint training and knowledge sharing. With the help of embedding techniques and sequence learning model with attention enhancement, our system does the map matching in the latent space, which is tolerant to the noise in the physical space. Extensive experiments demonstrate that our model outperforms the widely used HMM based methods more than 10% (absolute accuracy) and works robustly in the noisy settings in the meantime.