Graph Neural Networks (GNNs) have achieved significant success in various graph learning tasks. However, their success relies heavily on the availability of adequate high-quality labels, which requires high annotation costs. Recently, Large Language Models (LLMs) became known to the community for their strong zero-shot performance on diverse textual tasks. To utilize LLM's zero-shot abilities, existing work substitutes the oracle in the graph active learning setting with an LLM and achieves low-cost annotation compared to consulting human experts. However, annotations from LLMs inevitably contain noise, and we find through an empirical analysis that LLMs possess complex and dataset-specific annotation noise distributions. This intricacy of LLMs' annotation noise is neglected by existing work, leading to sub-optimal annotation data quality under the same budget. In this paper, we propose a Dataset- and LLM-Aware graph active learning framework called DMA that explicitly models LLM's annotation noise distributions on the given dataset. Concretely, DMA queries the oracle LLM with manually constructed prompts for each class's pseudo samples that are then used to measure the class-wise annotation noise rates. We then equip DMA with a new noise-aware graph active learning algorithm to utilize this fine-grained annotation noise distribution. Extensive performance optimizations are applied to the implementation to boost DMA's scalability and runtime efficiency on large-scale datasets. Evaluations on five text-attributed graph datasets show that DMA consistently outperforms all the baselines in terms of annotation data quality, which illustrates the importance of careful handling of LLM's intricate annotation noise.
论文检索
输入标题、作者或关键词，从 1,090 篇学术成果中精准定位
Despite the advancements in quantum convolution or quanvolution, challenges persist in making quanvolution scalable, efficient, and applicable to multi-dimensional data. Existing quanvolutional networks heavily rely on classical layers, with minimal quantum involvement due to inherent limitations in current quanvolution algorithms. Moreover, the application of quanvolution in the domain of 1D data remains largely unexplored. To address these limitations, we propose a new quanvolution algorithm-Quanv1D-capable of processing arbitrary-channel 1D data, handling variable kernel sizes, and generating a customizable number of feature maps, along with a classification network-fully quanvolutional network (FQN)-built solely using Quanv1D layers. Quanv1D is inspired by the classical Conv1D and stands out from the quanvolution literature by being fully trainable, modular, and freely scalable with a self-regularizing feature. To evaluate FQN, we tested it on 20 UEA and UCR time series datasets, both univariate and multivariate, and benchmarked its performance against state-of-the-art convolutional models (both quantum and classical). We found FQN to outperform all compared models in terms of average accuracy while using significantly fewer parameters. Additionally, to assess the viability of FQN on real hardware, we conducted a shot-based analysis across all the datasets to simulate statistical quantum noise and found our model robust and equally efficient.
Recently, we have been inundated with dynamic, time-evolving activity data streams generated by various individual IoT/sensor devices (e.g., healthcare devices and factory equipment). What would be the ideal mechanism for adaptively summarizing and modeling individual and local activities directly on small IoT devices with limited computing resources? In this paper, we present MicroAdapt, which comprises scalable and effective algorithms for modeling and forecasting time-evolving data streams. Our proposed method has the following advantages: (a) Adaptivity: it continuously monitors the latest time-series patterns in data streams, recognizes any sudden changes, updates model parameters, and enables real-time, long-range forecasting; (b) Any-time processing: it operates on a large collection of data streams, requiring a constant time (i.e., O(1)) for model updates and future predictions, at any point in time; (c) Lightweight computing: it does not require high-performance computing machines equipped with powerful GPUs, such as those used in deep learning, and can run on lightweight computers or even ''edge'' computing devices, such as Raspberry Pi. Intuitively, our method is inspired by the concept of an evolutionary adaptation mechanism of microorganisms, and thus it enables adaptive, any-time, lightweight model estimation and summarization of non-stationary data streams whose time-series patterns are constantly changing over time. We conduct extensive experiments on real datasets and demonstrate that MicroAdapt effectively captures important time-series patterns in the data streams, makes long-range forecasts, and consistently outperforms the existing state-of-the-art methods (e.g., TSMixer) as regards accuracy and execution speed. MicroAdapt improves accuracy by about 60% for MSE and 30% for MAE, while reducing computation time by up to six orders of magnitude (more than 100,000 times). We also applied our analytics to experiments implemented on Raspberry Pi with real IoT data streams, thus demonstrating the practicality and effectiveness of our approach. In fact, our proposed method required less than 1.95GB of memory and consumed less than 1.69W of power.
Bypassing Skip-Gram Negative Sampling: Dimension Regularization as a More Efficient Alternative for Graph Embeddings
PDF ↗A wide range of graph embedding objectives decompose into two components: one that enforces similarity, attracting the embeddings of nodes that are perceived as similar, and another that enforces dissimilarity, repelling the embeddings of nodes that are perceived as dissimilar. Without repulsion, the embeddings would collapse into trivial solutions. Skip-Gram Negative Sampling (SGNS) is a popular and efficient repulsion approach that prevents collapse by repelling each node from a sample of dissimilar nodes. In this work, we show that when repulsion is most needed and the embeddings approach collapse, SGNS node-wise repulsion is, in the aggregate, an approximate re-centering of the node embedding dimensions. Such dimension operations are more scalable than node operations and produce a simpler geometric interpretation of the repulsion. Our theoretical result establishes dimension regularization as an effective and more efficient, compared to skip-gram node contrast, approach to enforcing dissimilarity among embeddings of nodes. We use this result to propose a flexible algorithm augmentation framework that improves the scalability of any existing algorithm using SGNS. The framework prioritizes node attraction and replaces SGNS with dimension regularization. We instantiate this generic framework for LINE and node2vec and show that the augmented algorithms preserve downstream link-prediction performance while reducing GPU memory usage by up to 33.3% and training time by 23.4%. Moreover, we show that completely removing repulsion (a special case of our augmentation framework) in LINE reduces training time by 70.9% on average, while increasing link prediction performance, especially for graphs that are globally sparse but locally dense. Global sparsity slows down dimensional collapse, while local density ensures that node attraction brings the nodes near their neighbors. In general, however, repulsion is needed, and dimension regularization provides an efficient alternative to SGNS.
Time series anomaly detection (TSAD) is a central topic in data mining, with many algorithms proposed, including deep learning and LLM-based methods. However, these are often evaluated on flawed benchmarks with trivial anomalies, unrealistic densities, mislabeled ground truth, and run-to-failure biases. Recent studies using higher-quality datasets show that simpler distance-based methods, such as discords, can outperform deep learning; However, they typically rely on sliding windows with fixed lengths, limiting flexibility. We introduce GDFlex (Generalized Discords with Flexible Subsequence Length), a discord-based method that detects anomalies across multiple time scales using length-normalized Euclidean distance. It also incorporates bias-correction mechanisms to address limitations in Euclidean distance and z-normalization. GDFlex achieves notable accuracy gains over existing methods while remaining scalable, interpretable, and efficient.
Graph Alignment (GA) is an NP-hard combinatorial challenge. The existing methods usually work on small-scale graphs because their computational complexity grows as the square of the number of nodes. Recent techniques relied on alignment labels to divide the large source and target graphs into small ones respectively, which are then aligned separately. However, the alignment labels in expansive real-world graphs are often scarce, which makes GA even more challenging. To address these issues, we propose a novel self-supervised learning framework that is able to work on the graphs of million nodes without any alignment labels, where the existing methods usually fail to output an answer within a reasonable time. Our method also falls in the divide-and-conquer paradigm. We do not cluster the source and target graph separately by the existing graph clustering algorithms, because it is difficult to pair and then align the cluster-induced source and target subgraphs in the absence of alignment labels. We devise an Alignment-Aware Clustering (AAC) method to partition the source and target nodes jointly and keep the ought-to-be-aligned pairs of nodes within the same cluster as much as possible. Furthermore, we develop a Topology-Aware Repartition (TAR) that leverages pseudo-alignment labels as anchors for re-clustering, preserving detailed structural information within clusters. This enables graph neural networks to effectively enhance the graph representation learning for node alignments which are self-supervised by a graph-matching solver. Extensive experiments have demonstrated that our method greatly reduces computational demands and sustains high alignment accuracies in large-scale graph applications.
Despite the theoretical expressiveness of 2-dimensional Folklore Weisfeiler-Lehman (2-FWL) Graph Neural Networks (GNNs), a significant gap persists between their theoretical capacity and their practical performance. To bridge this gap, we identify a critical limitation in current Graph Structural Encodings (GSEs): insufficient sensitivity to subtle structural variations, particularly in local connectivity, spectral features, and distance-based patterns. We show that widely used GSEs-such as Relative Random Walk Probability (RRWP) and monomial-based methods-lack full sensitivity across spectral frequency bands and long-range distances. Moreover, they fail to capture fine-grained local connectivity, which is essential for identifying cut nodes, biconnected components, and other higher-order structures that 2-FWL GNNs theoretically encode. To address these limitations, we propose CSDGSE (Connectivity, Spectral, and Distance Graph Structural Encoding), a novel GSE framework that jointly enhances sensitivity to: (1) exact local connectivity via hierarchical graph decomposition(2) full-frequency spectral features using expressive graph polynomials (e.g., Chebyshev), and (3) full-range distance interactions. A key innovation is our scalable divide-and-conquer algorithm for computing exact local connectivity across all node pairs, enabling efficient integration into modern GSEs. Extensive experiments show that CSDGSE outperforms existing GSEs in capturing complex structural patterns, achieving state-of-the-art results on molecular property prediction benchmarks like ZINC. Our work sets a new standard for GSEs by aligning theoretical expressiveness with practical effectiveness through enhanced structural sensitivity.
Biomedical knowledge graphs (KGs) encode rich, structured information critical for drug discovery tasks, but extracting meaningful insights from large-scale KGs remains challenging due to their complex structure. Existing biomedical subgraph retrieval methods are tailored for graph neural networks (GNNs), limiting compatibility with other paradigms, including large language models (LLMs). We introduce K-Paths, a model-agnostic retrieval framework that extracts structured, diverse, and biologically meaningful multi-hop paths from dense biomedical KGs. These paths enable prediction of unobserved drug-drug and drug-disease interactions, including those involving entities not seen during training, thus supporting inductive reasoning. K-Paths is training-free and employs a diversity-aware adaptation of Yen's algorithm to extract the K shortest loopless paths between entities in a query, prioritizing biologically relevant and relationally diverse connections. These paths serve as concise, interpretable reasoning chains that can be directly integrated with LLMs or GNNs to improve generalization, accuracy, and enable explainable inference. Experiments on benchmark datasets show that K-Paths improves zero-shot reasoning across state-of-the-art LLMs. For instance, Tx-Gemma 27B improves by 19.8 and 4.0 F1 points on interaction severity prediction and drug repurposing tasks, respectively. Llama 70B achieves gains of 8.5 and 6.2 points on the same tasks. K-Paths also boosts the training efficiency of EmerGNN, a state-of-the-art GNN, by reducing the KG size by 90% while maintaining predictive performance. Beyond efficiency, K-Paths bridges the gap between KGs and LLMs, enabling scalable and explainable LLM-augmented scientific discovery. We release our code and the retrieved paths as a benchmark for inductive reasoning.
Extreme Classification (XC) aims to map a query to the most relevant documents from a very large document set. XC algorithms used in real-world applications typically learn this mapping from datasets curated from implicit feedback, such as user clicks. However, these datasets often suffer from missing labels. In this work, we observe that systematic missing labels lead to missing knowledge, which is critical for modelling relevance between queries and documents. We formally show that this absence of knowledge is hard to recover using existing methods such as propensity weighting and data imputation strategies that solely rely on the training dataset. While Large Language Models (LLMs) provide an attractive solution to augment the missing knowledge, leveraging them in applications with low latency requirements and large document sets is challenging. To mitigate missing knowledge at scale, we propose SKIM (Scalable Knowledge Infusion for Missing Labels), an algorithm that leverages a combination of Small Language Models or SLMs, e.g., Llama2-7b, and abundant unstructured meta-data to effectively address the missing label problem. We show the efficacy of our method on large-scale public datasets through a combination of unbiased evaluation strategies, such as exhaustive human annotations and simulation-based evaluation benchmarks. SKIM outperforms existing methods on Recall@100 by more than 10 absolute points. Additionally, SKIM scales to proprietary query-ad retrieval datasets containing 10 million documents, outperforming baseline methods by 12% in offline evaluations and increasing ad click-yield by 1.23% in an online A/B test conducted on Bing Search. We release the code and trained models at: github.com/bicycleman15/skim
State-of-the-art rule mining algorithms rely on summarizing the training set into efficient data structures which allow to quickly answer arbitrary conjunctive queries about the data. The key limitation of such techniques is their memory consumption. Pre-post code trees (PPC-trees) which are the basis of several efficient association and classification rule mining algorithms, are only constructed as an intermediate representation and subsequently converted into a much more efficient N-lists structure. In this paper, we introduce partial pre-post code trees (P3C-trees), which are based on the idea that partial trees are iteratively constructed, and immediately converted into N-lists. This tight integration of these phases allows to avoid the memory bottleneck of a full PPC-tree construction, and thus enables these algorithms to tackle the memory scalability problem posed by large-scale datasets. Our experiments with big datasets confirm that the memory used by P3C-tree is orders of magnitude smaller than the memory consumed by PPC-tree, and the generated N-lists are also more effective than alternative structures such as Tidset or Diffset. Moreover, the N-list construction can also be considerably sped up with the P3C-tree structure.
Given an extensive, semi-infinite collection of multivariate coevolving data sequences (e.g., sensor/web activity streams) whose observations influence each other, how can we discover the time-changing cause-and-effect relationships in co-evolving data streams? How efficiently can we reveal dynamical patterns that allow us to forecast future values? In this paper, we present a novel streaming method, ModePlait, which is designed for modeling such causal relationships (i.e., time-evolving causality) in multivariate co-evolving data streams and forecasting their future values. The solution relies on characteristics of the causal relationships that evolve over time in accordance with the dynamic changes of exogenous variables. ModePlait has the following properties: (a) Effective: it discovers the time-evolving causality in multivariate co-evolving data streams by detecting the transitions of distinct dynamical patterns adaptively. (b) Accurate: it enables both the discovery of time-evolving causality and the forecasting of future values in a streaming fashion. (c) Scalable: our algorithm does not depend on data stream length and thus is applicable to very large sequences. Extensive experiments on both synthetic and real-world datasets demonstrate that our proposed model outperforms state-of-the-art methods in terms of discovering the time-evolving causality as well as forecasting.
The rise of link recommendation systems in online social networks has sparked significant research interest in strategically adding links to enhance social influence. This paper delves into the influence maximization with augmentation (IMA) problem that aims to add k edges connecting seed nodes and ordinary nodes to boost the influence propagation of the given seed set. IMA is a monotone submodular maximization problem so that the greedy algorithm provides a (1-1/e-ε)-approximate solution, where ε is an error term caused by the intractable nature of influence spread computation. Previous work often utilizes an unbiased estimator that relies on the chosen edges for influence estimation, resulting in non-submodular estimate with respect to edge selection. To ensure the overall error being bounded by ε, such an estimator requires Θ(ε/k) multiplicative error for each estimation, incurring prohibitive overhead. Meanwhile, some other work approximates IMA via conventional influence maximization (IM) on an augmented graph by adding a new node for every edge candidate, leading to heavy extra sampling due to a significant increase in graph size. To address these challenges, we design a novel unbiased estimator on the original graph that is independent of the chosen edges by leveraging the tractability of one-hop influence computation. We show that the estimate via our estimator is submodular so that it enables the estimate of all k edges in a whole with a bounded estimation error of Θ(ε), saving O(k2) time compared to the chosen-edge-dependent estimator while retaining the same graph size. Moreover, we propose several techniques based on the properties of our estimator to further speed up the greedy selection. Putting it together, we develop a scalable algorithm for the IMA problem, namely ScaLIM. Finally, extensive experiments are conducted to validate the effectiveness and efficiency of our proposed approach, e.g., ScaLIM is faster than baselines by nearly two orders of magnitude.
Scalable Primal Heuristics Using Graph Neural Networks for Combinatorial Optimization (Abstract Reprint)
PDF ↗By examining the patterns of solutions obtained for various instances, one can gain insights into the structure and behavior of combinatorial optimization (CO) problems and develop efficient algorithms for solving them. Machine learning techniques, especially Graph Neural Networks (GNNs), have shown promise in parametrizing and automating this laborious design process. The inductive bias of GNNs allows for learning solutions to mixed-integer programming (MIP) formulations of constrained CO problems with a relational representation of decision variables and constraints. The trained GNNs can be leveraged with primal heuristics to construct high-quality feasible solutions to CO problems quickly. However, current GNN-based end-to-end learning approaches have limitations for scalable training and generalization on larger-scale instances; therefore, they have been mostly evaluated over small-scale instances. Addressing this issue, our study builds on supervised learning of optimal solutions to the downscaled instances of given large-scale CO problems. We introduce several improvements on a recent GNN model for CO to generalize on instances of a larger scale than those used in training. We also propose a two-stage primal heuristic strategy based on uncertainty-quantification to automatically configure how solution search relies on the predicted decision values. Our models can generalize on 16x upscaled instances of commonly benchmarked five CO problems. Unlike the regressive performance of existing GNN-based CO approaches as the scale of problems increases, the CO pipelines using our models offer an incremental performance improvement relative to CPLEX. The proposed uncertainty-based primal heuristics provide 6-75% better optimality gap values and 45-99% better primal gap values for the 16x upscaled instances and brings immense speedup to obtain high-quality solutions. All these gains are achieved through a computationally efficient modeling approach without sacrificing solution quality.
Different from single-objective evolutionary algorithms, where non-elitism is an established concept, multi-objective evolutionary algorithms almost always select the next population in a greedy fashion. In the only notable exception, a stochastic selection mechanism was recently proposed for the SMS-EMOA and was proven to speed up computing the Pareto front of the bi-objective jump benchmark with problem size n and gap parameter k by a factor of max{1,2^(k/4)/n}. While this constitutes the first proven speed-up from non-elitist selection, suggesting a very interesting research direction, it has to be noted that a true speed-up only occurs for k ≥ 4log(n), where the runtime is super-polynomial, and that the advantage reduces for larger numbers of objectives as shown in a later work. In this work, we propose a different non-elitist selection mechanism based on aging, which exempts individuals younger than a certain age from a possible removal. This remedies the two shortcomings of stochastic selection: We prove a speed-up by a factor of max{1,Θ(k)^(k-1)}, regardless of the number of objectives. In particular, a positive speed-up can already be observed for constant k, the only setting for which polynomial runtimes can be witnessed. Overall, this result supports the use of non-elitist selection schemes, but suggests that aging-based mechanisms can be considerably more powerful than stochastic selection mechanisms.
Qualitative Numerical Planning (QNP) extends classical planning with numerical variables that can be changed by arbitrary amounts. FOND+ extends Fully Observable Non-Deterministic (FOND) planning by introducing explicit fairness assumptions, resulting in a more expressive model that can also capture QNP as a special case. However, existing QNP and FOND+ solvers still face significant scalability challenges. To address this, we propose a novel framework for solving QNP and FOND+ by generating strong cyclic solutions of the associated FOND problem, testing their validity, and forbidding non-solutions in conducting further searches. For this, we propose a procedure called SIEVE*, which generalizes the QNP termination testing algorithm SIEVE to determine whether a strong cyclic solution is a FOND+ solution. Additionally, we propose several optimization techniques to further improve the performance of our basic framework. We implemented our approach based on the advanced FOND solver PRP; experimental results show that our solver shows superior scalability over the existing QNP and FOND+ solvers.
Automated Test Case Generation (ATCG) is crucial for evaluating software reliability, particularly in competitive programming where robust algorithm assessments depend on diverse and accurate test cases. However, existing ATCG methods often fail to meet complex specifications or generate effective corner cases, limiting their utility. In this work, we introduce Context-Free Grammars with Counters (CCFGs), a formalism that captures both syntactic and semantic structures in input specifications. Using a fine-tuned CodeT5 model, we translate natural language input specifications into CCFGs, enabling the systematic generation of high-quality test cases. Experiments on the CodeContests dataset demonstrate that CCFG-based test cases outperform baseline methods in identifying incorrect algorithms, achieving significant gains in validity and effectiveness. Our approach provides a scalable and reliable grammar-driven framework for enhancing automated competitive programming evaluations.
Security vulnerabilities in Windows Active Directory (AD) systems are typically modeled using an attack graph and hardening AD systems involves an iterative workflow: security teams propose an edge to remove, and IT operations teams manually review these fixes before implementing the removal. As verification requires significant manual effort, we formulate an Adaptive Path Removal Problem to minimize the number of steps in this iterative removal process. In our model, a wizard proposes an attack path in each step and presents it as a set of multiple-choice options to the IT admin. The IT admin then selects one edge from the proposed set to remove. This process continues until the target t is disconnected from source s or the number of proposed paths reaches B. The model aims to optimize the human effort by minimizing the expected number of interactions between the IT admin and the security wizard. We first prove that the problem is #P-hard. We then propose a set of solutions including an exact algorithm, an approximate algorithm, and several scalable heuristics. Our best heuristic, called DPR, can operate effectively on larger-scale graphs compared to the exact algorithm and consistently outperforms the approximate algorithm across all graphs. We verify the effectiveness of our algorithms on several synthetic AD graphs and an AD attack graph collected from a real organization.
Advancing Community Detection with Graph Convolutional Neural Networks: Bridging Topological and Attributive Cohesion
PDF ↗Community detection, a vital technology for real-world applications, uncovers cohesive node groups (communities) by leveraging both topological and attribute similarities in social networks. However, existing Graph Convolutional Networks (GCNs) trained to maximize modularity often converge to suboptimal solutions. Additionally, directly using human-labeled communities for training can undermine topological cohesiveness by grouping disconnected nodes based solely on node attributes. We address these issues by proposing a novel Topological and Attributive Similarity-based Community detection (TAS-Com) method. TAS-Com introduces a novel loss function that exploits the highly effective and scalable Leiden algorithm to detect community structures with global optimal modularity. Leiden is further utilized to refine human-labeled communities to ensure connectivity within each community, enabling TAS-Com to detect community structures with desirable trade-offs between modularity and compliance with human labels. Experimental results on multiple benchmark networks confirm that TAS-Com can significantly outperform several state-of-the-art algorithms.
The use of anchors often leads to better efficiency and scalability, making them highly favored. However, there is a challenge in anchor-based multi-view subspace learning. A unified anchor graph overly emphasize the commonality between views, failing to adequately capture the view-specific individuality. This has led some models to independently explore the individuality of each view before aligning and integrating them, often achieving better performance but making the process more cumbersome. Therefore, this paper proposes a new model, simultaneously capturing the individuality and commonality between anchor graphs for multi-view clustering. The model has three notable advantages: First, it allows view-specific anchor graphs to align in real-time with a common anchor graph as a reference, eliminating the need for post-alignment. Second, it enforces a cluster-wise structure among anchors and balances sample distribution among them, providing strong discriminative power. Lastly, it maintains linear complexity with respect to the numbers of samples and anchors, avoiding the significant time costs associated with their increase. Comprehensive experiments demonstrate the effectiveness and efficiency of our method compared to various state-of-the-art algorithms.
In this paper, we propose a simple faster accelerated gradient method called SIFAR for solving the finite-sum optimization problems. Concretely, we consider both general convex and strongly convex settings: i) For general convex finite-sum problems, SIFAR improves previous state-of-the-art result given by Varag. In particular, for large-scale problems or the convergence error is not very small, SIFAR obtains the first optimal result O(n), matching the lower bound. ii) For strongly convex finite-sum problems, we also show that SIFAR can achieve the optimal convergence rate matching the lower bound. Besides, SIFAR enjoys a simpler loopless algorithmic structure while previous algorithms use double-loop structures. Moreover, we provide a novel dynamic multi-stage convergence analysis, which is the key for improving previous results to the optimal rates. Our new theoretical rates and novel convergence analysis for the fundamental finite-sum problem can directly lead to key improvements for many other related problems, such as distributed/federated/decentralized optimization problems. Finally, the numerical experiments show that SIFAR converges faster than the previous state-of-the-art Varag, validating our theoretical results and confirming the practical superiority of SIFAR.