Understanding and predicting urban dynamics is crucial for managing transportation systems, optimizing urban planning, and enhancing public services. While neural network-based approaches have achieved success, they often rely on task-specific architectures and large volumes of data, limiting their ability to generalize across diverse urban scenarios. Meanwhile, Large Language Models (LLMs) offer strong reasoning and generalization capabilities, yet their application to spatial-temporal urban dynamics remains underexplored. Existing LLM-based methods struggle to effectively integrate multifaceted spatial-temporal data and fail to address distributional shifts between training and testing data, limiting their predictive reliability in real-world applications. To bridge this gap, we propose UrbanMind, a novel spatial-temporal LLM framework for multifaceted urban dynamics prediction that ensures both accurate forecasting and robust generalization. At its core, UrbanMind introduces Muffin-MAE, a multifaceted fusion masked autoencoder with specialized masking strategies that capture intricate spatial-temporal dependencies and intercorrelations among multifaceted urban dynamics. Additionally, we design a semantic-aware prompting and fine-tuning strategy that encodes spatial-temporal contextual details into prompts, enhancing LLMs' ability to reason over spatial-temporal patterns. To further improve generalization, we introduce a test time adaptation mechanism with a test data reconstructor, enabling UrbanMind to dynamically adjust to unseen test data by reconstructing LLM-generated embeddings. Extensive experiments on real-world urban dynamics datasets from multiple cities demonstrate the effectiveness of UrbanMind. The results consistently show that UrbanMind outperforms state-of-the-art baselines, achieving superior accuracy and strong generalization, even in zero-shot scenarios with no prior data.
论文检索
输入标题、作者或关键词，从 2,893 篇学术成果中精准定位
Feature Reconstruction for Anomaly Detection on Directed Multigraphs: A Preprocessing Framework for GNNs
PDF ↗Graph Neural Networks (GNNs) have achieved significant success in anomaly detection across various domains. However, existing GNN approaches face notable challenges when applied to directed multigraphs where edge attributes serve as the sole source of information. This limitation complicates the learning of meaningful node representations and the accurate detection of anomalies, particularly in transaction networks. Moreover, existing methods typically suffer from dimensionality explosion and suboptimal use of structural and semantic information, leading to reduced detection performance. To address these challenges, we propose Feature Reconstruction for Anomaly Detection on Directed Multigraphs (FRAD-DM), a novel preprocessing framework tailored to enhance graph representations in node feature-absent scenarios. FRAD-DM employs advanced edge feature derivation techniques, temporal and structural subgraph analysis for node representation generation, and a reinforcement learning-based adaptive feature selection mechanism. This comprehensive framework optimizes feature spaces by balancing informativeness, task relevance, and computational efficiency, ensuring robust and scalable anomaly detection. Extensive experiments on real-world datasets under barely supervised settings demonstrate the effectiveness of FRAD-DM. By integrating it into various GNN architectures for node-level and edge-level anomaly detection tasks, negative-class F1-scores improve by 5.44% to 20.98%. These results highlight its capability to address the challenges of directed multigraphs in practical applications.
Recently, Graph Foundation Models (GFMs) have emerged as a significant research topic in graph machine learning. Compared with traditional graph neural networks, GFMs demonstrate impressive zero-shot generalization across different domains and tasks through large-scale pre-training on extensive and diverse graph data. Despite the initial success of pre-training, existing GFMs face challenges such as extreme time consumption and the presence of redundancy and noise in pre-training data. To alleviate these issues, we present the first exploration of data-centric GFM, which aims to optimize pre-training data (i.e., a set of subgraphs) to establish a more efficient GFM while maintaining robust performance across various downstream tasks. We propose DCGFM, a plug-and-play approach for Data-Centric GFM that incorporates the idea of data pruning to remove redundant and less informative subgraphs from the pre-training data, thereby improving both efficiency and effectiveness. Specifically, DCGFM consists of two components: (1) a model-agnostic hard pruning module that filters out subgraphs with lower informativity scores by considering both the semantics and structures of subgraphs; and (2) a model-aware soft pruning module that dynamically prunes subgraphs with lower loss values in each pre-training epoch with a gradient rescaling strategy. Extensive experiments on representative GFM backbones demonstrate DCGFM's efficiency and effectiveness. Remarkably, DCGFM achieves even better performance using only 30% of the pre-training data. Codes and data are available at https://github.com/Yuhan1i/DCGFM.
Graph neural architecture search (NAS) has emerged as a promising approach for autonomously designing graph neural network architectures by leveraging correlations between graphs and architectures. However, existing methods merely rely on correlations, which may be spurious and vary across distributions. This reliance, without considering causal graph-architecture relationships, limits their ability to generalize under distribution shifts that are ubiquitous in real-world graph scenarios. In this paper, we propose to handle the distribution shifts in NAS process by exploiting the causal graph-architecture relationship to search for optimal architectures that can generalize under distribution shifts. Key challenges remain unexplored: discovering causal graph-architecture relationships with stable cross-distribution predictive abilities, and leveraging them to handle distribution shifts. To address these challenges, we propose a novel approach, Causal-aware Graph Neural Architecture Search (CARNAS), which is capable of capturing causal graph-architecture relationship during NAS process and discovering optimal graph architecture under distribution shifts. We propose Disentangled Causal Subgraph Identification to extract causal subgraphs with stable predictive power across distributions, followed by Graph Embedding Intervention to intervene on these subgraphs in latent space by preserving essential features while filtering out non-causal elements, and Invariant Architecture Customization to enhance their causal invariance for optimizing graph architectures. Extensive experiments on synthetic and real-world datasets show that CARNAS enhances out-of-distribution generalization by uncovering causal graph-architecture relationships during NAS.
Lifelong Multi-Agent Path Finding (LMAPF) focuses on planning conflict-free paths for agents, like autonomous vehicles, that are continuously assigned new tasks. The synergy of search-based and learning-based methods holds promise for striking a balance in-between effectiveness and efficiency but still faces several challenges such as inferior initial paths, weak search-learning synergy and low sample utilization rate. To address these issues, this paper proposes a new synergized LMAPF approach, named Synergistic Multi-Agent Path Optimization (SMAPO), which consists of two tightly-coupled phases: Primordial Planning and Decision Refinement. In the Primordial Planning phase, we introduce a novel load-balanced A* algorithm that integrates planned and perceived congestion costs, which enhances initial solution quality by evenly distributing spatiotemporal traffic loads, thereby mitigating potential conflicts. In the Decision Refinement phase, we propose a novel Encoder-Decoder based neural network to learn a collaborative optimization policy through multi-agent reinforcement learning. In addition, we leverage dual transformations to augment trajectory samples during online learning, enhancing both the sample utilization rate and overall learning stability. Extensive experiments reveal that our SMAPO is superior to the state-of-the-art baselines in effectiveness, efficiency, and generalization capability. Source code is available at https://github.com/ByteUser-blues/SMAPO.
A fundamental challenge in understanding graph neural networks (GNNs) lies in characterizing their optimization dynamics and loss landscape geometry, critical for improving interpretability and robustness. While mode connectivity-a lens for analyzing geometric properties of loss landscapes-has proven insightful for other deep learning architectures, its implications for GNNs remain unexplored. This work presents the first investigation of mode connectivity in GNNs. We uncover that GNNs exhibit distinct non-linear mode connectivity, diverging from patterns observed in fully-connected networks or CNNs. Crucially, we demonstrate that graph structure, rather than model architecture, dominates this behavior, with graph properties like homophily correlating with mode connectivity patterns. We further establish a link between mode connectivity and generalization, proposing a generalization bound based on loss barriers and revealing its utility as a diagnostic tool. Our findings further bridge theoretical insights with practical implications: they rationalize domain alignment strategies in graph learning and provide a foundation for refining GNN training paradigms.
With the increasing computation of training graph neural networks (GNNs) on large-scale graphs, graph condensation (GC) has emerged as a promising solution to synthesize compact, substitute graphs of the large-scale original graphs for efficient GNN training. However, these condensed graphs are specifically designed for the node classification task, significantly limiting the versatility of the synthesized data across various downstream tasks. This limitation predominantly stems from the reliance of existing GC methods on classification as the surrogate task for optimization, which leads to an excessive dependence on node labels and restricts their utility in label-scarcity scenarios. More critically, this surrogate task tends to overfit class-specific information within the condensed graph, consequently restricting the generalization capabilities of GC for other downstream tasks. To address these challenges, we introduce Contrastive Graph Condensation (CTGC), which adopts a self-supervised surrogate task to extract critical, causal information from the original graph and enhance the cross-task generalizability of the condensed graph. Specifically, CTGC employs a dual-branch framework to disentangle the generation of the node attributes and graph structures, where a dedicated structural branch is designed to explicitly encode geometric information through nodes' positional embeddings. By implementing an alternating optimization scheme with contrastive loss terms, CTGC promotes the mutual enhancement of both branches and facilitates high-quality graph generation through the model inversion technique. Extensive experiments demonstrate that CTGC excels in handling various downstream tasks with a limited number of labels, consistently outperforming state-of-the-art GC methods.
Graph Neural Networks (GNNs) have gained traction in Graph-based Machine Learning as a Service (GMLaaS) platforms, yet they remain vulnerable to graph-based model extraction attacks (MEAs), where adversaries reconstruct surrogate models by querying the victim model. Existing defense mechanisms, such as watermarking and fingerprinting, suffer from poor real-time performance, susceptibility to evasion, or reliance on post-attack verification, making them inadequate for handling the dynamic characteristics of graph-based MEA variants. To address these limitations, we propose ATOM, a novel real-time MEA detection framework tailored for GNNs. ATOM integrates sequential modeling and reinforcement learning to dynamically detect evolving attack patterns, while leveraging k-core embedding to capture the structural properties, enhancing detection precision. Furthermore, we provide theoretical analysis to characterize query behaviors and optimize detection strategies. Extensive experiments on multiple real-world datasets demonstrate that ATOM outperforms existing approaches in detection performance, maintaining stable across different time steps, thereby offering a more effective defense mechanism for GMLaaS environments. Our source code is available at https://github.com/LabRAI/ATOM.
Recently, full-graph Graph Neural Networks (GNNs) have gained prominence by addressing complex problems such as weather forecasting and material discovery. Existing full-graph training methods do not fully manage intermediate data generated during training and rely on rigid inter-GPU communication, limiting both training speed and scale. We propose FlexGNN, which fully manages intermediate data and adaptively performs inter-GPU communication by generating and optimizing best-effort training execution plans. Extensive experiments demonstrate that FlexGNN significantly outperforms existing full-graph GNN methods in both training speed and scale. Specifically, it is up to 5.4X faster than HongTu and up to 95.5X faster than NeutronStar.
We present LinkSAGE, an innovative framework that integrates Graph Neural Networks (GNNs) into large-scale personalized job matching systems, designed to address the complex dynamics of LinkedIn's extensive professional network. Our approach capitalizes on a novel job marketplace graph, the largest and most intricate of its kind in industry, with billions of nodes and edges. This graph is not merely extensive but also richly detailed, encompassing member and job nodes along with key attributes, thus creating an expansive and interwoven network. A key innovation in LinkSAGE is its training and serving methodology, which effectively combines inductive graph learning on a heterogeneous, evolving graph with an encoder-decoder GNN model. This methodology decouples the training of the GNN model from that of existing Deep Neural Network (DNN) models, eliminating the need for frequent GNN retraining while maintaining up-to-date graph signals in near real-time, allowing for the effective integration of GNN insights through transfer learning. The subsequent nearline inference system serves the GNN encoder within a real-world setting, significantly reducing online latency and obviating the need for costly real-time GNN infrastructure. Validated across multiple online A/B tests in diverse product scenarios, LinkSAGE demonstrates marked improvements in member engagement, relevance matching, and member retention, confirming its generalizability and practical impact.
Today's top advertisers typically manage hundreds of campaigns simultaneously and consistently launch new ones throughout the year. A crucial challenge for marketing managers is determining the optimal allocation of limited budgets across various ad lines in each campaign to maximize cumulative returns, especially given the huge uncertainty in return outcomes. In this paper, we propose to formulate budget allocation as a multi-task combinatorial bandit problem and introduce a novel online budget allocation system. The proposed system: i) integrates a Bayesian hierarchical model to intelligently utilize the metadata of campaigns and ad lines and budget size, ensuring efficient information sharing; ii) provides the flexibility to incorporate diverse modeling techniques such as Linear Regression, Gaussian Processes, and Neural Networks, catering to diverse environmental complexities; and iii) employs the Thompson sampling technique to strike a balance between exploration and exploitation. Through extensive empirical evaluations with both synthetic data and real-world data from Amazon campaigns, our system demonstrates robustness and adaptability, effectively maximizing the overall cumulative returns. A Python implementation of the proposed procedure is available at https://anonymous.4open.science/r/MCMAB.
In this paper, we present a novel transformer architecture tailored for learning robust power system state representations, which strives to optimize power dispatch for the power flow adjustment across different transmission sections. Specifically, our proposed approach, named Powerformer, develops a dedicated section-adaptive attention mechanism, separating itself from the self-attention employed in conventional transformers. This mechanism effectively integrates power system states with transmission section information, which facilitates the development of robust state representations. Furthermore, by considering the graph topology of power system and the electrical attributes of bus nodes, we introduce two customized strategies to further enhance the expressiveness: graph neural network propagation and multi-factor attention mechanism. Extensive evaluations are conducted on three power system scenarios, including the IEEE 118-bus system, a realistic China 300-bus system, and a large-scale European system with 9241 buses, where Powerformer demonstrates its superior performance over several popular baseline methods. The code is available at: https://github.com/Cra2yDavid/Powerformer
The advent of the "pre-train, prompt'' paradigm has recently extended its generalization ability and data efficiency to graph representation learning, following its achievements in Natural Language Processing (NLP). Initial graph prompt tuning approaches tailored specialized prompting functions for Graph Neural Network (GNN) models pre-trained with specific strategies, such as edge prediction, thus limiting their applicability. In contrast, another pioneering line of research has explored universal prompting via adding prompts to the input graph's feature space, thereby removing the reliance on specific pre-training strategies. However, the necessity to add feature prompts to all nodes remains an open question. Motivated by findings from prompt tuning research in the NLP domain, which suggest that highly capable pre-trained models need less conditioning signal to achieve desired behaviors, we advocate for strategically incorporating necessary and lightweight feature prompts to certain graph nodes to enhance downstream task performance. This introduces a combinatorial optimization problem, requiring a policy to decide 1) which nodes to prompt and 2) what specific feature prompts to attach. We then address the problem by framing the prompt incorporation process as a sequential decision-making problem and propose our method, RELIEF, which employs Reinforcement Learning (RL) to optimize it. At each step, the RL agent selects a node (discrete action) and determines the prompt content (continuous action), aiming to maximize cumulative performance gain. Extensive experiments on graph and node-level tasks with various pre-training strategies in few-shot scenarios demonstrate that our RELIEF outperforms fine-tuning and other prompt-based approaches in classification performance and data efficiency. The code is available at https://github.com/JasonZhujp/RELIEF.
In real-world recommendation scenarios, users engage with items through various types of behaviors. Leveraging diversified user behavior information for learning can enhance the recommendation of target behaviors (e.g., buy), as demonstrated by recent multi-behavior methods. The mainstream multi-behavior recommendation framework consists of two steps: fusion and prediction. Recent approaches utilize graph neural networks for multi-behavior fusion and employ multi-task learning paradigms for joint optimization in the prediction step, achieving significant success. However, these methods have limited perspectives on multi-behavior fusion, which leads to inaccurate capture of user behavior patterns in the fusion step. Moreover, when using multi-task learning for prediction, the relationship between the target task and auxiliary tasks is not sufficiently coordinated, resulting in negative information transfer. To address these problems, we propose a novel multi-behavior recommendation framework based on the combinatorial optimization perspective, named COPF. Specifically, we treat multi-behavior fusion as a combinatorial optimization problem, imposing different constraints at various stages of each behavior to restrict the solution space, thus significantly enhancing fusion efficiency (COGCN). In the prediction step, we improve both forward and backward propagation during the generation and aggregation of multiple experts to mitigate negative transfer caused by differences in both feature and label distributions (DFME). Comprehensive experiments on three real-world datasets indicate the superiority of COPF. Further analyses also validate the effectiveness of the COGCN and DFME modules. Our code is available at https://github.com/1918190/COPF.
Graph Neural Networks (GNNs) have been proven effective in modeling graph data, mostly depending on the in-distribution assumption. While in the out-of-distribution (OOD) scenarios, especially for the more challenging node-level task, the feature and structure distribution shifts between training and test nodes lead to performance degradation. To improve node-level OOD generalization, typical approaches introduce graph augmentation to enrich the training environments and conduct invariant learning to learn stable representations across various augmented environments. However, their graph augmentations emphasize diversity but neglect the preservation of invariant patterns which are fundamental to invariant learning. Moreover, most of them simply conduct the classic invariant learning objective but lack the consideration of the graph-specific structure information. Therefore, to mitigate their weakness, we propose a Structure-aware Invariant learning framework for Node-level Graph OOD generalization (SING). Specifically, we develop the invariance constraint regularization terms during the optimization of augmentations. Additionally, we define the structure embedding to elucidate the structural property and design the structure embedding alignment loss to optimize the augmentations and the invariant representations. By introducing the structure information, we further integrate the unique structural property into invariant learning, thereby boosting the invariant message-passing GNNs. The extensive experiments on the transductive GOOD benchmark and the inductive datasets empirically validate our superior OOD generalization performance to baselines.
Domain generalization on graphs aims to develop models with robust generalization capabilities, ensuring effective performance on the testing set despite disparities between testing and training distributions. However, existing methods often rely on static encoders directly applied to the target domain, constraining its flexible adaptability. In contrast to conventional methodologies, which concentrate on developing specific generalized models, our framework, MLDGG, endeavors to achieve adaptable generalization across diverse domains by integrating cross-multi-domain meta-learning with structure learning and semantic identification.Initially, it introduces a generalized structure learner to mitigate the adverse effects of task-unrelated edges, enhancing the comprehensiveness of representations learned by Graph Neural Networks (GNNs) while capturing shared structural information across domains.Subsequently, a representation learner is designed to disentangle domain-invariant semantic and domain-specific variation information in node embedding by leveraging causal reasoning for semantic identification, further enhancing generalization. In the context of meta-learning, meta-parameters for both learners are optimized to facilitate knowledge transfer and enable effective adaptation to graphs through fine-tuning within the target domains, where target graphs are inaccessible during training.Our empirical results demonstrate that MLDGG surpasses baseline methods, showcasing the effectiveness in three different distribution shift settings.
Graph-based Cognitive Diagnosis (CD) has attracted much research interest due to its strong ability on inferring students' proficiency levels on knowledge concepts. While graph-based CD models have demonstrated remarkable performance, we contend that they still cannot achieve optimal performance due to the neglect of edge heterogeneity and uncertainty. Edges involve both correct and incorrect response logs, indicating heterogeneity. Meanwhile, a response log can have uncertain semantic meanings, e.g., a correct log can indicate true mastery or fortunate guessing, and a wrong log can indicate a lack of understanding or a careless mistake. In this paper, we propose an Informative Semantic-aware Graph-based Cognitive Diagnosis model (ISG-CD), which focuses on how to utilize the heterogeneous graph in CD and minimize effects of uncertain edges. Specifically, to explore heterogeneity, we propose a semantic-aware graph neural networks based CD model. To minimize effects of edge uncertainty, we propose an Informative Edge Differentiation layer from an information bottleneck perspective, which suggests keeping a minimal yet sufficient reliable graph for CD in an unsupervised way. We formulate this process as maximizing mutual information between the reliable graph and response logs, while minimizing mutual information between the reliable graph and the original graph. After that, we prove that mutual information maximization can be theoretically converted to the classic binary cross entropy loss function, while minimizing mutual information can be realized by the Hilbert-Schmidt Independence Criterion.Finally, we adopt an alternating training strategy for optimizing learnable parameters of both the semantic-aware graph neural networks based CD model and the edge differentiation layer. Extensive experiments on three real-world datasets have demonstrated the effectiveness of ISG-CD.
The two-tower model has become prevalent in recommender systems for its computational efficiency and robust predictive capabilities. The model usually employs two independent neural networks to encode user and item data separately, and predicts the similarity score with inner product or cosine functions, depending on which the Top-k ranked item list is generated. The optimization process typically involves a multi-label classification objective, often guided by surrogate loss functions like Softmax and One-vs-All (OvA), to enhance the recommendation performance. Despite both Softmax and OvA losses being Bayes-consistent, empirical observations reveal a significant performance gap in evaluation metrics, suggesting limitations in Bayes-consistency for analyzing loss effectiveness. To address this, we introduce ℋ-consistency into the discussion, which provides non-asymptotic and hypothesis-specific guarantees for Top-k classification within the two-tower model's hypothesis space. Through theoretical analysis, we demonstrate that Softmax and Cosine Contrastive Loss exhibit ℋ-consistency, while the OvA loss does not, explaining the observed performance discrepancies. Our findings bridge the gap between theoretical properties and practical outcomes, offering deeper insights into the optimization of two-tower models and contributing to the development of more effective recommendation systems.
Black-box attacks have emerged as a significant threat to deep neural networks. This challenge is particularly difficult in discrete sequential data compared to continuous data. Recently, the Blockwise Bayesian Attack (BBA) leveraging discrete Bayesian optimization with an adapted RBF kernel has gained prominence as a cutting-edge solution. However, it relies solely on alignment information (i.e., positional differences) within the RBF kernel, which may not fully capture the information (such as statistical, structural, and semantic information) inherent in discrete sequential data and potentially lacks the desired inductive bias necessary to approximate the target function accurately. To overcome this limitation, this paper proposes a novel bilevel Bayesian optimization approach to adaptively learn a hybrid space that better captures the similarity between discrete sequences. Specifically, we introduce a multi-kernel mechanism that incorporates multiple types of information, creating a more comprehensive similarity measure. Moreover, we develop a bilevel Bayesian optimization algorithm, where the outer-level objective determines the optimal weights of the multiple kernels, while the inner-level objective identifies the optimal adversarial sequence. Extensive experiments conducted on discrete sequential data demonstrate that our approach ensures secure multi-kernel selection and achieves a higher attack success rate with only a few additional queries, compared to BBA and other traditional optimization strategies.
Spatio-temporal forecasting is a critical component of various smart city applications, such as transportation optimization, energy management, and socio-economic analysis. Recently, several automated spatio-temporal forecasting methods have been proposed to automatically search the optimal neural network architecture for capturing complex spatio-temporal dependencies. However, the existing automated approaches suffer from expensive neural architecture search overhead, which hinders their practical use and the further exploration of diverse spatio-temporal operators in a finer granularity. In this paper, we propose AutoSTF, a decoupled automatic neural architecture search framework for cost-effective automated spatio-temporal forecasting. From the efficiency perspective, we first decouple the mixed search space into temporal space and spatial space and respectively devise representation compression and parameter-sharing schemes to mitigate the parameter explosion. The decoupled spatio-temporal search not only expedites the model optimization process but also leaves new room for more effective spatio-temporal dependency modeling. From the effectiveness perspective, we propose a multi-patch transfer module to jointly capture multi-granularity temporal dependencies and extend the spatial search space to enable finer-grained layer-wise spatial dependency search. Extensive experiments on eight datasets demonstrate the superiority of AutoSTF in terms of both accuracy and efficiency. Specifically, our proposed method achieves up to 13.48x speed-up compared to state-of-the-art automatic spatio-temporal forecasting methods while maintaining the best forecasting accuracy. The source code and data are available at https://github.com/usail-hkust/AutoSTF.