OpenRaiser/Intern-Atlas huggingface dataset:
Msdr: Multi-step dependency relation networks for spatial temporal forecasting
Authors: Dachuan Liu, Jin Wang 0007, Shuo Shang, Peng Han 0005
Venue: Conference KDD 2022
Year: 2022

Spatial temporal forecasting plays an important role in improving the quality and performance of Intelligent Transportation Systems. This task is rather challenging due to the complicated and long-range spatial temporal dependencies in traffic network. Existing studies typically employ different deep neural networks to learn the spatial and temporal representations so as to capture the complex and dynamic dependencies. In this paper, we argue that it is insufficient to capture the long-range spatial dependencies from the implicit representations learned by temporal extracting modules. To address this problem, we propose Multi-Step Dependency Relation (MSDR), a brand new variant of recurrent neural network. Instead of only looking at the hidden state from only one latest time step, MSDR explicitly takes those of multiple historical time steps as the input of each time unit. We also develop two strategies to incur the spatial information into the dependency relation embedding between multiple historical time steps and the current one in MSDR. On the basis of it, we propose the Graph-based MSDR (GMSDR) framework to support general spatial temporal forecasting applications by seamlessly integrating graph-based neural networks with MSDR. We evaluate our proposed approach on several popular datasets. The results show that the proposed GMSDR framework outperforms state-of-the-art methods by an obvious margin.
Unify graph learning with text: Unleashing llm potentials for session search
Authors: Songhao Wu, Quan Tu, Hong Liu, Jia Xu, Zhongyi Liu, Guannan Zhang, Ran Wang, Xiuying Chen, Rui Yan
Venue: Conference WWW 2024
Year: 2024

Session search involves a series of interactive queries and actions to fulfill user's complex information need. Current strategies typically prioritize sequential modeling for deep semantic understanding, overlooking the graph structure in interactions. While some approaches focus on capturing structural information, they use a generalized representation for documents, neglecting the word-level semantic modeling. In this paper, we propose Symbolic Graph Ranker (SGR), which aims to take advantage of both text-based and graph-based approaches by leveraging the power of recent Large Language Models (LLMs). Concretely, we first introduce a set of symbolic grammar rules to convert session graph into text. This allows integrating session history, interaction process, and task instruction seamlessly as inputs for the LLM. Moreover, given the natural discrepancy between LLMs pre-trained on textual corpora, and the symbolic language we produce using our graph-to-text grammar, our objective is to enhance LLMs' ability to capture graph structures within a textual format. To achieve this, we introduce a set of self-supervised symbolic learning tasks including link prediction, node content generation, and generative contrastive learning, to enable LLMs to capture the topological information from coarse-grained to fine-grained. Experiment results and comprehensive analysis on two benchmark datasets, AOL and Tiangong-ST, confirm the superiority of our approach. Our paradigm also offers a novel and effective methodology that bridges the gap between traditional search strategies and modern LLMs.
Transferable graph structure learning for graph-based traffic forecasting across cities
Authors: Yilun Jin, Kai Chen 0005, Qiang Yang 0001
Venue: Conference KDD 2023
Year: 2023

Graph-based deep learning models are powerful in modeling spatio-temporal graphs for traffic forecasting. In practice, accurate forecasting models rely on sufficient traffic data, which may not be accessible in real-world applications. To address this problem, transfer learning methods are designed to transfer knowledge from the source graph with abundant data to the target graph with limited data. However, existing methods adopt pre-defined graph structures for knowledge extraction and transfer, which may be noisy or biased and negatively impact the performance of knowledge transfer. To address the problem, we propose TransGTR, a transferable structure learning framework for traffic forecasting that jointly learns and transfers the graph structures and forecasting models across cities. TransGTR consists of a node feature network, a structure generator, and a forecasting model. We train the node feature network with knowledge distillation to extract city-agnostic node features, such that the structure generator, taking the node features as inputs, can be transferred across both cities. Furthermore, we train the structure generator via a temporal decoupled regularization, such that the spatial features learned with the generated graphs share similar distributions across cities and thus facilitate knowledge transfer for the forecasting model. We evaluate TransGTR on real-world traffic speed datasets, where under a fair comparison, TransGTR outperforms state-of-the-art baselines by up to 5.4%.
Fedstg: Breaking through spatio-temporal data silos with federated graph learning
Authors: Yudong Zhang, Xu Wang, Xuan Yu, Kuo Yang, Zhengyang Zhou, Yang Wang
Venue: Conference WWW 2025
Year: 2025

Spatio-temporal graph (STG) forecasting plays a crucial role in various urban computing applications driven by Web systems. However, conventional STG forecasting methods, which rely on centralized data processing, have posed obstacles to real-world applications in numerous data silo scenarios. Given this, some researchers have preliminarily explored incorporating federated learning into STG forecasting. Though promising, the existing methods encounter two critical issues, i.e., dynamics and heterogeneity in STGs. To this end, we propose a novel personalized Federated learning framework for Spatio-Temporal Graph forecasting (called FedSTG), along with an evolutionary graph learning module and a personalized federated aggregation algorithm based on evolving temporal patterns in the framework. Our approach enhances the STG learning capabilities in the federated paradigm, yield addressing the problem of STG forecasting in data silo scenarios. Extensive experiments on four real-world datasets in STG forecasting have been conducted to demonstrate the superiority of our approach.
ImputeFormer: Low rankness-induced transformers for generalizable spatiotemporal imputation
Authors: Tong Nie 0001, Guoyang Qin, Wei Ma 0016, Yuewen Mei, Jian Sun 0010
Venue: Conference KDD 2024
Year: 2024

Missing data is a pervasive issue in both scientific and engineering tasks, especially for the modeling of spatiotemporal data. This problem attracts many studies to contribute to data-driven solutions. Existing imputation solutions mainly include low-rank models and deep learning models. The former assumes general structural priors but has limited model capacity. The latter possesses salient features of expressivity but lacks prior knowledge of the underlying spatiotemporal structures. Leveraging the strengths of both two paradigms, we demonstrate a low rankness-induced Transformer to achieve a balance between strong inductive bias and high model expressivity. The exploitation of the inherent structures of spatiotemporal data enables our model to learn balanced signal-noise representations, making it generalizable for a variety of imputation problems. We demonstrate its superiority in terms of accuracy, efficiency, and versatility in heterogeneous datasets, including traffic flow, solar energy, smart meters, and air quality. Promising empirical results provide strong conviction that incorporating time series primitives, such as low-rankness, can substantially facilitate the development of a generalizable model to approach a wide range of spatiotemporal imputation problems.
Convtimenet: A deep hierarchical fully convolutional model for multivariate time series analysis
Authors: Mingyue Cheng, Jiqian Yang, Tingyue Pan, Qi Liu, Zhi Li, Shijin Wang
Venue: Conference WWW 2025
Year: 2025

Designing effective models for learning time series representations is foundational for time series analysis. Many previous works explore time series representation modeling approaches and make progress in this area. Despite their effectiveness, they lack adaptive perception of local patterns in temporally dependent basic units and fail to capture the multi-scale dependency among these units. Instead of relying on prevalent methods centered around self-attention mechanisms, we propose ConvTimeNet, a hierarchical pure convolutional model designed for time series analysis. ConvTimeNet introduces a deformable patch layer that adaptively perceives local patterns of temporally dependent basic units in a data-driven manner. Based on the extracted local patterns, hierarchical pure convolutional blocks are designed to capture dependency relationships among the representations of basic units at different scales. Moreover, a large kernel mechanism is employed to ensure that convolutional blocks can be deeply stacked, thereby achieving a larger receptive field. In this way, local patterns and their multi-scale dependencies can be effectively modeled within a single model. Extensive experiments comparing a wide range of different types of models demonstrate that pure convolutional models still exhibit strong viability, effectively addressing the aforementioned two challenges and showing superior performance across multiple tasks. The code is available for reproducibility. https://github.com/Mingyue-Cheng/ConvTimeNet
End-to-end balancing for causal continuous treatment-effect estimation
Authors: Mohammad Taha Bahadori, Eric Tchetgen Tchetgen, David Heckerman
Venue: Conference ICML 2022
Year: 2022

We study the problem of observational causal inference with continuous treatments in the framework of inverse propensity-score weighting. To obtain stable weights, we design a new algorithm based on entropy balancing that learns weights to directly maximize causal inference accuracy using end-to-end optimization. In the process of optimization, these weights are automatically tuned to the specific dataset and causal inference algorithm being used. We provide a theoretical analysis demonstrating consistency of our approach. Using synthetic and real-world data, we show that our algorithm estimates causal effect more accurately than baseline entropy balancing.
Accelerating personalized PageRank vector computation
Authors: Zhen Chen 0035, Xingzhi Guo, Baojian Zhou, Deqing Yang, Steven Skiena
Venue: Conference KDD 2023
Year: 2023

Personalized PageRank Vectors are widely used as fundamental graph-learning tools for detecting anomalous spammers, learning graph embeddings, and training graph neural networks. The well-known local FwdPush algorithm approximates PPVs and has a sublinear rate of $O\big(\frac{1}{αε}\big)$. A recent study found that when high precision is required, FwdPush is similar to the power iteration method, and its run time is pessimistically bounded by $O\big(\frac{m}α \log\frac{1}ε\big)$. This paper looks closely at calculating PPVs for both directed and undirected graphs. By leveraging the linear invariant property, we show that FwdPush is a variant of Gauss-Seidel and propose a Successive Over-Relaxation based method, FwdPushSOR to speed it up by slightly modifying FwdPush. Additionally, we prove FwdPush has local linear convergence rate $O\big(\tfrac{\text{vol}(S)}α \log\tfrac{1}ε\big)$ enjoying advantages of two existing bounds. We also design a new local heuristic push method that reduces the number of operations by 10-50 percent compared to FwdPush. For undirected graphs, we propose two momentum-based acceleration methods that can be expressed as one-line updates and speed up non-acceleration methods by$\mathcal{O}\big(\tfrac{1}{\sqrtα}\big)$. Our experiments on six real-world graph datasets confirm the efficiency of FwdPushSOR and the acceleration methods for directed and undirected graphs, respectively.
Graph contrastive learning via interventional view generation
Authors: Zengyi Wo, Minglai Shao, Wenjun Wang, Xuan Guo, Lu Lin
Venue: Conference WWW 2024
Year: 2024

Graph contrastive learning (GCL), as a popular self-supervised learning technique, has demonstrated promising capability in learning discriminative representations for diverse downstream tasks. A large body of GCL frameworks mainly work on graphs formed under homophily effect, i.e., similar nodes tend to connect with each other. In their design, the augmentation and aggregation are usually conducted indiscriminately on edges, ignoring the existence of heterophilic edges that connect dissimilar nodes. Therefore, the efficacy of GCL could greatly deteriorate on heterophilic graphs, verified by our analysis: GCL on a mixture of homophilic and heterophilic edges will generate representations that are indistinguishable across different classes in the embedding space. To address this challenge, we propose a novel GCL framework via interventional view generation. Specifically, we generate homophilic and heterophilic views through counterfactual intervention, which targets on disentangling homophilic and heterophilic structure from the original graph, such that we can capture their corresponding information using separate filters in the contrastive learning process. Since the homophilic view and the heterophilic view present different frequency signals, they are further encoded via a low-pass and a high-pass filter respectively. Extensive experiments on multiple benchmark datasets demonstrate the effectiveness of our design. Our proposed framework achieves a remarkably improved downstream performance on graphs with high heterophily while maintaining a comparable ability in learning homophilic graphs. A comprehensive study also verifies the necessity of individual designs in our framework.
DuARE: Automatic Road Extraction with Aerial Images and Trajectory Data at Baidu Maps
Authors: Jianzhong Yang, Xiaoqing Ye, Bin Wu, Yanlei Gu, Ziyu Wang, Deguo Xia, Jizhou Huang
Venue: Conference KDD 2022
Year: 2022

The task of road extraction has aroused remarkable attention due to its critical role in facilitating urban development and up-to-date map maintenance, which has widespread applications such as navigation and autonomous driving. Existing solutions either rely on a single source of data for road graph extraction or simply fuse the multimodal information in a sub-optimal way. In this paper, we present an automatic road extraction solution named DuARE, which is designed to exploit the multimodal knowledge for underlying road extraction in a fully automatic manner. Specifically, we collect a large-scale real-world dataset for paired aerial image and trajectory data, covering over 33,000 km2 in more than 80 cities. First, road extraction is performed on the abundant spatial-temporal trajectory data adaptively based on the density distribution. Then, a coarse-to-fine road graph learner from aerial images is proposed to take advantage of the local and global context. Finally, our cross-check-based fusion approach keeps the optimal state of each modality while revisiting the original trajectory map with the guidance of aerial predictions to further improve the performance. Extensive experiments conducted on large-scale real-world datasets demonstrate the superiority and effectiveness of DuARE. In addition, DuARE has been deployed in production at Baidu Maps since June 2021 and keeps updating the road network by 100,000 km per month. This confirms that DuARE is a practical and industrial-grade solution for large-scale cost-effective road extraction from multimodal data.
Time and sample efficient discovery of markov blankets and direct causal relations
Authors: Ioannis Tsamardinos, Constantin F. Aliferis, Alexander R. Statnikov
Venue: Conference KDD 2003
Year: 2003

Data Mining with Bayesian Network learning has two important characteristics: under conditions learned edges between variables correspond to casual influences, and second, for every variable T in the network a special subset (Markov Blanket) identifiable by the network is the minimal variable set required to predict T. However, all known algorithms learning a complete BN do not scale up beyond a few hundred variables. On the other hand, all known sound algorithms learning a local region of the network require an exponential number of training instances to the size of the learned region.The contribution of this paper is two-fold. We introduce a novel local algorithm that returns all variables with direct edges to and from a target variable T as well as a local algorithm that returns the Markov Blanket of T. Both algorithms (i) are sound, (ii) can be run efficiently in datasets with thousands of variables, and (iii) significantly outperform in terms of approximating the true neighborhood previous state-of-the-art algorithms using only a fraction of the training size required by the existing methods. A fundamental difference between our approach and existing ones is that the required sample depends on the generating graph connectivity and not the size of the local region; this yields up to exponential savings in sample relative to previously known algorithms. The results presented here are promising not only for discovery of local causal structure, and variable selection for classification, but also for the induction of complete BNs.
Solving cluster ensemble problems by bipartite graph partitioning
Authors: Xiaoli Zhang Fern, Carla E. Brodley
Venue: Conference ICML 2004
Year: 2004

A critical problem in cluster ensemble research is how to combine multiple clusterings to yield a final superior clustering result. Leveraging advanced graph partitioning techniques, we solve this problem by reducing it to a graph partitioning problem. We introduce a new reduction method that constructs a bipartite graph from a given cluster ensemble. The resulting graph models both instances and clusters of the ensemble simultaneously as vertices in the graph. Our approach retains all of the information provided by a given ensemble, allowing the similarity among instances and the similarity among clusters to be considered collectively in forming the final clustering. Further, the resulting graph partitioning problem can be solved efficiently. We empirically evaluate the proposed approach against two commonly used graph formulations and show that it is more robust and achieves comparable or better performance in comparison to its competitors.
Introducing problem schema with hierarchical exercise graph for knowledge tracing
Authors: Hanshuang Tong, Zhen Wang, Yun Zhou, Shiwei Tong, Wenyuan Han, Qi Liu
Venue: Conference SIGIR 2022
Year: 2022

Knowledge tracing (KT) which aims at predicting learner's knowledge mastery plays an important role in the computer-aided educational system. The goal of KT is to provide personalized learning paths for learners by diagnosing the mastery of each knowledge, thus improving the learning efficiency. In recent years, many deep learning models have been applied to tackle the KT task, which has shown promising results. However, most existing methods simplify the exercising records as knowledge sequences, which fail to explore the rich information that existed in exercises. Besides, the existing diagnosis results of knowledge tracing are not convincing enough since they neglect hierarchical relations between exercises. To solve the above problems, we propose a hierarchical graph knowledge tracing model called HGKT to explore the latent complex relations between exercises. Specifically, we introduce the concept of problem schema to construct a hierarchical exercise graph that could model the exercise learning dependencies. Moreover, we employ two attention mechanisms to highlight important historical states of learners. In the testing stage, we present a knowledge&schema diagnosis matrix that could trace the transition of mastery of knowledge and problem schema, which can be more easily applied to different applications. Extensive experiments show the effectiveness and interpretability of our proposed model.
Clsprec: Contrastive learning of long and short-term preferences for next poi recommendation
Authors: Chenghua Duan, Wei Fan, Wei Zhou, Hu Liu, Junhao Wen
Venue: Conference CIKM 2023
Year: 2023

Next point-of-interest (POI) recommendation optimizes user travel experiences and enhances platform revenues by providing users with potentially appealing next location choices. In recent research, scholars have successfully mined users' general tastes and varying interests by modeling long-term and short-term check-in sequences. However, conventional methods for long and short-term modeling predominantly employ distinct encoders to process long and short-term interaction data independently, with disparities in encoders and data limiting the ultimate performance of these models. Instead, we propose a shared trajectory encoder and a novel Contrastive learning of Long and Short-term Preferences for next POI Recommendation (CLSPRec) model to better utilize the preference similarity among the same users and distinguish different users' travel preferences for more accurate next POI prediction. CLSPRec adopts a masking strategy in long-term sequences to enhance model robustness and further strengthens user representation through short-term sequences. Extensive experiments on three real-world datasets validate the superiority of our model. Our code is publicly available at https://github.com/Wonderdch/CLSPRec.
Seed: Bridging sequence and diffusion models for road trajectory generation
Authors: Xuan Rao, Shuo Shang, Renhe Jiang, Peng Han, Lisi Chen
Venue: Conference WWW 2025
Year: 2025

Road trajectory generation creates synthetic yet realistic trajectories to tackle data collection costs and privacy concerns. Existing methods generate a trajectory either segment-by-segment using sequence models or holistically in one step using diffusion models. Sequence-based models have good regularity and consistency (i.e., resemble the input trajectories) but lack diversity, while diffusion-based models enhance diversity but sacrifice regularity and consistency. To combine the merits of existing methods, we propose Seed, by bridging sequence and diffusion models for trajectory generation. In particular, Seed adopts a conditional diffusion structure, where a Transformer models the movement of each trajectory along the road segments, and conditioned on the Transformer's output, a diffusion model recovers the next road segment from random noise. The rationale is that the Transformer captures sequential patterns for regularity and consistency, while the diffusion model introduces diversity by recovering from noise. We use a trajectory reconstruction task to train Seed, and design a curriculum learning strategy to accelerate convergence. We compare Seed with 8 state-of-the-art trajectory generation methods on 3 datasets, and the results show that Seed improves the best-performing baseline by over 50%.