Inferring the actual road segment purely based on one positioning point, known as single-point map matching (SMM), is vital for many urban applications, e.g., ride-hailing and geo-tagging. However, it is challenging due to inherent positioning errors and extrinsic heterogeneous environments. Existing methods either overlook the heterogeneity of different regions, or do not exploit the commonality of different matching tasks. In this paper, we treat each region as an individual SMM task to tackle the heterogeneity, and propose Spatial Hierarchical Meta-Learning for SMM (SHSMM) to learn the shared knowledge across tasks. SHSMM is equipped with a Dual-view Map Matcher to perform the matching, which can perceive the knowledge of road segments globally. To learn the task-specific model parameters, SHSMM modulates initial parameters and scales the local update learning rate based on hierarchical geographical and semantic knowledge about spatial tasks. A local update learning rate scheduling strategy is further proposed to facilitate the meta-training. Extensive experiments as well as case studies based on two real-world datasets demonstrate the effectiveness of the proposed method.
论文检索
输入标题、作者或关键词，从 844 篇学术成果中精准定位
Empowering Graph-based Approximate Nearest Neighbor Search with Adaptive Awareness Capabilities
PDF ↗Approximate Nearest Neighbor Search (ANNS) in high-dimensional spaces finds extensive applications in databases, information retrieval, recommender systems, etc. While graph-based methods have emerged as the leading solution for ANNS due to their superior query performance, they still face several challenges, such as struggling with local optima and redundant computations. These issues arise because existing methods (i) fail to fully exploit the topological information underlying the proximity graph G, and (ii) suffer from severe distribution mismatches between the base data and queries in practice. To this end, this paper proposes GATE, high-tier proximity Graph with Adaptive Topology and Query Awareness, as a lightweight and adaptive module atop the graph-based indexes to accelerate ANNS. Specifically, GATE formulates the critical problem to identify an optimal entry point in the proximity graph for a given query, facilitating faster online search. By leveraging the inherent clusterability of high-dimensional data, GATE first extracts a small set of hub nodes V as candidate entry points. Then, resorting to a contrastive learning-based two-tower model, GATE encodes both the structural semantics underlying G and the query-relevant features into the latent representations of these hub nodes V. A navigation graph index on V is further constructed to minimize the model inference overhead. Extensive experiments demonstrate that GATE achieves a 1.2-2.0X speed-up in query performance compared to state-of-the-art graph-based indexes.
Small-space frequency estimators play a crucial role in a multitude of settings related to both data science and machine learning in the context of big data processing. Many frequency estimators use internal randomness to compress the information about the frequencies of items to a small sketch that can be used to provide estimates. Historically, these types of estimators were designed without considering the danger of invalid estimates caused by their adaptive use. However, this kind of scenario naturally occurs when they are used as a subroutine in a more complicated algorithm or when an adversary maliciously attempts to corrupt estimates. The reason why the classic way of analyzing these types of algorithms does not provide satisfying guarantees is that it often assumes that the queries and updates are independent of the previously generated estimates. In the adaptive setting, each provided estimate has the potential of leaking information about the estimator's internal randomness, which can, in turn, be used to craft queries and updates on which the frequency estimator does not perform well. In this work, we consider one of the simplest such estimators, Count-Min Sketch, and demonstrate both positive and negative results. On the one hand, we show that Count-Min Sketch can be made resistant to adaptive attacks in both the random oracle model, which corresponds to cryptographically hard hash functions, and using universal hash functions if the domain size is in polynomial relationship with with the size of hash tables. On the other hand, we develop techniques for more efficient attacks on Count-Min Sketch than those known previously. First, we introduce value-based attack techniques. They leverage information from queries to Count-Min Sketch beyond whether a collision between different elements occurs. By inserting carefully selected values, we can more efficiently recover the elements that hash to the same bucket as the targeted element, for which we want to manipulate estimates. Second, for a very popular family of universal hash functions, we demonstrate that it is possible to generate simultaneous collisions between two elements in two hash tables at the rate which in general it is possible to generate collisions in one hash table. This allows for efficiently producing more skewed estimates than those proposed by previous works. This is achieved by developing methods that allow for narrowing the range of internal parameters of these hash functions.
In the literature, various graph embedding methods have been proposed. Although they have pioneered notable techniques in the field, we point out their four drawbacks as follows: (1) inability to consider global graph structure(2) undermining learning quality(3) impairing in/out-degree distributions in directed graphs, and (4) limited applicability. Inspired by these drawbacks, we first propose LINOW, a recursive LI nk-based similarity measure for graphs by utilizing NO des' Weights, which is applicable to both directed and undirected graphs. Then, we provide a matrix form that dramatically accelerates LINOW's computation without approximation. Furthermore, to enhance its scalability, we provide two variants, LINOW-sn and LINOW-bn, to compute similarity scores w.r.t. a single node and a batch of nodes, respectively. Finally, we propose SIGEM, a simple yet effective self-supervised and contrastive-free SI milarity based Graph EM bedding method that employs LINOW-bn to compute similarity scores of nodes in the graph, thereby ranking them. Then, it tries to preserve the original ranks of nodes in the graph within their corresponding vectors in the embedding space, by employing a single-layer neural network. The results of our extensive experiments with eight real-world datasets and thirteen state-of-the-art and conventional embedding methods demonstrate that (1) LINOW-sn and LINOW-bn successfully improve the scalability of naive LINOW(2) LINOW is beneficial to similarity based graph embedding, and (3) SIGEM consistently achieves the highest accuracy in both graph reconstruction and node classification tasks compared to other methods, while it significantly outperforms them in most cases of the link prediction task.
Determining conditional independence (CI) relationships between random variables is a fundamental yet challenging task in machine learning and statistics, especially in high-dimensional settings. Existing generative model-based CI testing methods, such as those utilizing generative adversarial networks (GANs), often struggle with undesirable modeling of conditional distributions and training instability, resulting in subpar performance. To address these issues, we propose a novel CI testing method via score-based generative modeling, which achieves precise Type I error control and strong testing power. Concretely, we first employ a sliced conditional score matching scheme to accurately estimate conditional score and use Langevin dynamics conditional sampling to generate null hypothesis samples, ensuring precise Type I error control. Then, we incorporate a goodness-of-fit stage into the method to verify generated samples and enhance interpretability in practice. We theoretically establish the error bound of conditional distributions modeled by score-based generative models and prove the validity of our CI tests. Extensive experiments on both synthetic and real-world datasets show that our method significantly outperforms existing state-of-the-art methods, providing a promising way to revitalize generative model-based CI testing.
Incorporating Retrieval-based Causal Learning with Information Bottlenecks for Interpretable Molecular Graph Learning
PDF ↗Graph Neural Networks (GNNs) have gained considerable traction for modeling molecular structures and predicting properties, but their interpretability remains a significant challenge in understanding chemical behaviors. Current interpretation methods often rely on post-hoc explanations, which aim to provide transparency in GNN decisions. However, these approaches struggle with interpreting complex subgraphs and fail to leverage explanations to enhance predictive capabilities. While transparent methods can enhance GNN predictions, they typically compromise on explanation precision. This limitation underscores the need for a new strategy that effectively integrates GNN explanations and predictions. In this study, we have developed a novel interpretable causal GNN framework that combines retrieval-based causal learning with Graph Information Bottleneck (GIB) theory. Our framework semi-parametrically identifies crucial subgraphs through GIB and compresses explanatory subgraphs using a causal module. The framework consistently outperformed state-of-the-art methods, achieving a 32.72% increase in precision for scientific explanation tasks involving diverse substructures. More importantly, the learned explanations were also shown to be able to improve GNN prediction performance. This advancement is particularly vital for molecular graph learning, as it addresses the critical need to interpret how molecular structures influence predicted properties, thereby aiding drug discovery and materials science by providing insights into chemical mechanisms.
We propose a computational framework for identifying approximate functional dependencies (AFDs) in a relation, leveraging the frequency distribution information of individual attributes. This framework operates without requiring access to the full database, processing records one at a time as necessary. Our approach generalizes existing measures for quantifying errors in perfect dependencies and formalizes two primary problems: finding top-k AFDs and identifying all AFDs within a specified error threshold, ε. Our pro posed framework provides anytime solutions, meaning it returns results after processing each record. A key innovation of our work lies in effectively estimating error bounds of the candidate AFDs, which allows to produce anytime solutions. We present an exact algorithm that delivers precise solutions when possible. We also develop an algorithm that always returns a solution albeit with some imprecision in the output. We demonstrate the applicability of these algorithms under various data organization strategies, such as indexing by key or key-like attributes. Our experimental results, based on both real-world and synthetic datasets, validate the effectiveness of our approach and show that it outperforms state-of-the-art solutions.
DarkDistill: Difficulty-Aligned Federated Early-Exit Network Training on Heterogeneous Devices
PDF ↗Early-exit networks (EENs), which adapt their computational depths based on input samples, are widely adopted to accelerate inference in edge computing applications. The effectiveness of EENs relies on difficulty-aware training, which tailors shallow exits for simple samples and deep exits for complex ones. However, existing difficulty-aware training schemes assume centralized environments with sufficient data, which become invalid with real-world edge devices. In this paper, we explore difficulty-aware training in a federated manner, where EENs are collaboratively trained on heterogeneous devices. We observe the cross-model exit unalignment phenomenon, a unique problem when aggregating local EENs into a cohesive global model. To address this problem, we design a novel Difficulty-Aligned Reverse Knowledge Distillation scheme named DarkDistill that preserves the difficulty-specific specialization for aggregating heterogeneous local models. Instead of direct parameter averaging, it trains difficulty-conditional data generators, and selectively transfers generated knowledge of specific difficulty among matched exits of heterogeneous EENs. Evaluations show that DarkDistill outperforms the state-of-the-arts in both full-parameter and parameter-efficient fine-tuning of EENs.
Counterfactual learning is emerging as an important paradigm, rooted in causality, which promises to alleviate common issues of graph neural networks (GNNs), such as fairness and interpretability. However, as in many real-world application domains where conducting randomized controlled trials is impractical, one has to rely on available observational (factual) data to detect counterfactuals. In this paper, we introduce and tackle the problem of searching for counterfactual evidences for the GNN-based node classification task. A counterfactual evidence is a pair of nodes such that, regardless they exhibit great similarity both in the features and in their neighborhood subgraph structures, they are classified differently by the GNN. We develop effective and efficient search algorithms and a novel indexing solution that leverages both node features and structural information to identify counterfactual evidences, and generalizes beyond any specific GNN. Through various downstream applications, we demonstrate the potential of counterfactual evidences to enhance fairness and accuracy of GNNs.
Graph neural networks (GNNs), which capture graph structures via a feature aggregation mechanism following the graph embedding framework, have demonstrated a powerful ability to support various tasks. According to the topology properties (e.g., structural roles or community memberships of nodes) to be preserved, graph embedding can be categorized into identity and position embedding. However, it is unclear for most GNN-based methods which property they can capture. Some of them may also suffer from low efficiency and scalability caused by several time- and space-consuming procedures (e.g., feature extraction and training). From a perspective of graph signal processing, we find that high- and low-frequency information in the graph spectral domain may characterize node identities and positions, respectively. Based on this investigation, we propose random feature aggregation (RFA) for efficient identity and position embedding, serving as an extreme ablation study regarding GNN feature aggregation. RFA (i) adopts a spectral-based GNN without learnable parameters as its backbone(ii) only uses random noises as inputs, and (iii) derives embeddings via just one feed-forward propagation (FFP). Inspired by degree-corrected spectral clustering, we further introduce a degree correction mechanism to the GNN backbone. Surprisingly, our experiments demonstrate that two variants of RFA with high- and low-pass filters can respectively derive informative identity and position embeddings via just one FFP (i.e., without any training). As a result, RFA can achieve a better trade-off between quality and efficiency for both identity and position embedding over various baselines. We have made our code public at https://github.com/KuroginQin/RFA
CellCLAT: Preserving Topology and Trimming Redundancy in Self-Supervised Cellular Contrastive Learning
PDF ↗Self-supervised topological deep learning (TDL) represents a nascent but underexplored area with significant potential for modeling higher-order interactions in simplicial complexes and cellular complexes to derive representations of unlabeled graphs. Compared to simplicial complexes, cellular complexes exhibit greater expressive power. However, the advancement in self-supervised learning for cellular TDL is largely hindered by two core challenges: extrinsic structural constraints inherent to cellular complexes, and intrinsic semantic redundancy in cellular representations. The first challenge highlights that traditional graph augmentation techniques may compromise the integrity of higher-order cellular interactions, while the second underscores that topological redundancy in cellular complexes potentially diminish task-relevant information. To address these issues, we introduce Cellular Complex Contrastive Learning with Adaptive Trimming (CellCLAT), a twofold framework designed to adhere to the combinatorial constraints of cellular complexes while mitigating informational redundancy. Specifically, we propose a parameter perturbation-based augmentation method that injects controlled noise into cellular interactions without altering the underlying cellular structures, thereby preserving cellular topology during contrastive learning. Additionally, a cellular trimming scheduler is employed to mask gradient contributions from task-irrelevant cells through a bi-level meta-learning approach, effectively removing redundant topological elements while maintaining critical higher-order semantics. We provide theoretical justification and empirical validation to demonstrate that CellCLAT achieves substantial improvements over existing self-supervised graph learning methods, marking a significant attempt in this domain.
Graph anomaly detection (GAD) aims to identify abnormal nodes that differ from the majority of the nodes in a graph, which has been attracting significant attention in recent years. Existing generalist graph models have achieved remarkable success in different graph tasks but struggle to generalize to the GAD task. This limitation arises from their difficulty in learning generalized knowledge for capturing the inherently infrequent, irregular and heterogeneous abnormality patterns in graphs from different domains. To address this challenge, we propose AnomalyGFM, a GAD-oriented graph foundation model that supports zero-shot inference and few-shot prompt tuning for GAD in diverse graph datasets. One key insight is that graph-agnostic representations for normal and abnormal classes are required to support effective zero/few-shot GAD across different graphs. Motivated by this, AnomalyGFM is pre-trained to align data-independent, learnable normal and abnormal class prototypes with node representation residuals (i.e., representation deviation of a node from its neighbors). The residual features es- sentially project the node information into a unified feature space where we can effectively measure the abnormality of nodes from different graphs in a consistent way. This provides a driving force for the learning of graph-agnostic, discriminative prototypes for the normal and abnormal classes, which can be used to enable zero-shot GAD on new graphs, including very large-scale graphs. If there are few-shot labeled normal nodes available in the new graphs, AnomalyGFM can further support prompt tuning to leverage these nodes for better adaptation. Comprehensive experiments on 11 widely-used GAD datasets with real anomalies, covering social networks, finance networks, and co-review networks, demonstrate that AnomalyGFM significantly outperforms state-of-the-art competing methods under both zero- and few-shot GAD settings. Code is available at https://github.com/mala-lab/AnomalyGFM.
Several applications call to align the nodes of two graphs in a way that minimizes a distance function. In practicality, the graphs to be aligned often have unequal orders (i.e., numbers of vertices) and no auxiliary labels or attributes; we refer to this problem as partial unlabeled graph alignment. Some proposals to address this problem add dummy nodes to the smaller graph to even the orders and align the ensuing graphs or employ embeddings such as GNNs, which yield ad hoc node representations. Unfortunately, as we show, an optimal solution to equal-order graph alignment using dummy nodes does not imply an optimal solution to partial graph alignment. To address this deficiency, in this paper, we propose Alpine, a Partial Unlabeled Graph Alignment algorithm that solely peruses the graphs' adjacency matrices, guided by a tailored objective function inspired by best-of-breed shape matching techniques and a state-of-the-art optimization method. Extensive experiments demonstrate that Alpine consistently surpasses state-of-the-art graph alignment methods in solution quality across all benchmark datasets.
Most self-supervised graph learning studies typically follow an offline training paradigm, assuming that all data are readily available. This assumption, however, is not always tenable in real-world scenarios as many graph data are generated continuously. Although several continual graph learning models have emerged and achieved empirical success, they almost all rely on external supervision, making it difficult to adapt to applications with a large amount of unlabeled data from the wild. To be honest, research on self-supervised continual graph learning is still surprisingly in its infancy. Therefore, we select several well-known self-supervised graph embedding models as representatives and explore whether they are resistant to catastrophic forgetting in a continual learning setting. Empirical studies find that self-supervised representation models may be potentially better continual learners than supervised counterparts. Driven by this advantage, we propose a self-supervised continual graph representation learning framework based on adaptive spaced replay on node proxies, named Trace. Inspired by the Complementary Learning System theory, Trace employs a dual-system architecture to simulate the functionality and cooperation of the hippocampus and neocortex in the brain. Among them, the fast-learning system efficiently encodes the current input graph to acquire new knowledge and adaptively extracts node proxies from it as important knowledge cached into the memory through progressive clustering. Drawing inspiration from the Ebbinghaus forgetting curve, the slow-learning system implements adaptive spaced replay based on the memory retention rate of each preceding task instead of the widely used consecutive replay scheme for promising flexibility and efficiency. Experiments under task-incremental and class-incremental learning settings on multiple datasets corroborate the superiority of our proposed Trace, even sometimes surpassing supervised graph continual learning solutions.
Making neural visual generative models controllable by logical reasoning systems is promising for improving faithfulness, transparency, and generalizability. We propose the Abductive visual Generation (AbdGen) approach to build such logic-integrated models. A vector-quantized symbol grounding mechanism and the corresponding disentanglement training method are introduced to enhance the controllability of logical symbols over generation. Furthermore, we propose two logical abduction methods to make our approach require few labeled training data and support the induction of latent logical generative rules from data. We experimentally show that our approach can be utilized to integrate various neural generative models with logical reasoning systems, by both learning from scratch or utilizing pre-trained models directly. The code is released at https://github.com/future-item/AbdGen.
Molecular docking plays a crucial role in predicting the binding mode of ligands to target proteins, and covalent interactions, which involve the formation of a covalent bond between the ligand and the target, are particularly valuable due to their strong, enduring binding nature. However, most existing docking methods and deep learning approaches hardly account for the formation of covalent bonds and the associated structural changes. To address this gap, we introduce a comprehensive benchmark for covalent docking, CovDocker, which is designed to better capture the complexities of covalent binding. We decompose the covalent docking process into three main tasks: reactive location prediction, covalent reaction prediction, and covalent docking. By adapting state-of-the-art models, such as Uni-Mol and Chemformer, we establish baseline performances and demonstrate the effectiveness of the benchmark in accurately predicting interaction sites and modeling the molecular transformations involved in covalent binding. These results confirm the role of the benchmark as a rigorous framework for advancing research in covalent drug design. It underscores the potential of data-driven approaches to accelerate the discovery of selective covalent inhibitors and addresses critical challenges in therapeutic development.
Semantics-Aware Patch Encoding and Hierarchical Dependency Modeling for Long-Term Time Series Forecasting
PDF ↗Time series forecasting is a vital task with widespread applications. While recent advancements have adopted patching to enrich short-term context, existing encoding methods often struggle to capture the diverse semantics within patches, resulting in semantic information loss and limited model performance. Moreover, most long-term dynamics modeling approaches rely on homogeneous architectures with fixed receptive fields, inevitably sacrificing either performance or efficiency. To address these challenges, we propose Mixture of Universals (MoU), a novel framework designed to prevent semantic loss during patch encoding and efficiently enhance long-term dynamics through a hybrid approach. Specifically, MoU is consist of two novel designs: Mixture of Feature Extractors (MoF) and Mixture of Architectures (MoA). MoF introduces a semantics-aware encoding mechanism that selectively activates the corresponding sub-extractor based on the semantic context of input patches, preserving diverse temporal patterns and mitigating information loss. MoA, on the other hand, hierarchically captures long-term dependency with progressively expanded receptive field, improving model performance while maintaining relatively low computational costs. We conducted extensive experiments on seven real-world datasets, and the results demonstrate the superiority of our model. Our Code is available at https://github.com/lunaaa95/mou/.
Despite significant advancements in Large Language Models (LLMs), developing advanced reasoning capabilities in LLMs remains a key challenge. Process Reward Models (PRMs) have demonstrated exceptional promise in enhancing reasoning by providing step-wise feedback, particularly in the context of mathematical reasoning. However, their application to broader reasoning domains remains understudied, largely due to the high costs associated with manually creating step-level supervision. In this work, we explore the potential of PRMs in graph reasoning problems - a domain that demands sophisticated multi-step reasoning and offers opportunities for automated step-level data generation using established graph algorithms. We introduce GraphSilo, the largest dataset for graph reasoning problems with fine-grained step-wise label, built using automated Task-oriented Trajectories and Monte Carlo Tree Search (MCTS) to generate detailed reasoning steps with step-wise labels. Building upon this dataset, we train GraphPRM, the first PRM designed for graph reasoning problems, and evaluate its effectiveness in two key settings: inference-time scaling and reinforcement learning via Direct Preference Optimization (DPO). Experimental results show that GraphPRM significantly improves LLM performance across 13 graph reasoning tasks, delivering a 9% gain for Qwen2.5-7B and demonstrating transferability to new graph reasoning datasets and new reasoning domains like mathematical problem-solving. Notably, GraphPRM enhances LLM performance on GSM8K and MATH500, underscoring the cross-domain applicability of graph-based reasoning rewards. Our findings highlight the potential of PRMs in advancing reasoning across diverse domains, paving the way for more versatile and effective LLMs.
TIDFormer: Exploiting Temporal and Interactive Dynamics Makes A Great Dynamic Graph Transformer
PDF ↗Due to the proficiency of self-attention mechanisms (SAMs) in capturing dependencies in sequence modeling, several existing dynamic graph neural networks (DGNNs) utilize Transformer architectures with various encoding designs to capture sequential evolutions of dynamic graphs. However, the effectiveness and efficiency of these Transformer-based DGNNs vary significantly, highlighting the importance of properly defining the SAM on dynamic graphs and comprehensively encoding temporal and interactive dynamics without extra complex modules. In this work, we propose TIDFormer, a dynamic graph TransFormer that fully exploits Temporal and Interactive Dynamics in an efficient manner. We clarify and verify the interpretability of our proposed SAM, addressing the open problem of its uninterpretable definitions on dynamic graphs in previous works. To model the temporal and interactive dynamics, respectively, we utilize the calendar-based time partitioning information and extract informative interaction embeddings for both bipartite and non-bipartite graphs using merely the sampled first-order neighbors. In addition, we jointly model temporal and interactive features by capturing potential changes in historical interaction patterns through a simple decomposition. We conduct extensive experiments on several dynamic graph datasets to verify the effectiveness and efficiency of TIDFormer. The experimental results demonstrate that TIDFormer excels, outperforming state-of-the-art models across most datasets and experimental settings. Furthermore, TIDFormer exhibits significant efficiency advantages compared to previous Transformer-based methods.
How can we achieve compact tensor representations without sacrificing reconstruction accuracy? Tensor decomposition is a cornerstone of modern data mining and machine learning, enabling efficient representations of multi-dimensional data through fundamental algorithms such as CP, Tucker, and Tensor-Train decompositions. However, directly applying these methods to raw data often results in high target ranks, poor reconstruction accuracy, and computational inefficiencies, as the data may not naturally conform to the low-rank structures these methods assume. In this paper, we propose PuzzleTensor, a method-agnostic data transformation technique for compact tensor factorization. Given a data tensor, PuzzleTensor ''solves the puzzle'' by shifting each hyperslice of the tensor to achieve accurate decompositions with significantly lower target ranks. PuzzleTensor offers three key advantages: (1) it is independent of specific decomposition methods, making it seamlessly compatible with various algorithms, such as CP, Tucker, and Tensor-Train decompositions; (2) it works under weak data assumptions, showing robust performance across both sparse and dense data, regardless of the rank; (3) it is inherently explainable, allowing clear interpretation of its learnable parameters and layer-wise operations. Extensive experiments show that PuzzleTensor consistently outperforms direct tensor decomposition approaches by achieving lower reconstruction errors and reducing the required target rank, making it a versatile and practical tool for compact tensor factorization in real-world applications.