Sharding provides an opportunity to overcome the inherent scalability challenges of the blockchain, which is the infrastructure for the next generation of the Web. In a sharding blockchain, the state is partitioned into smaller groups known as "shards." Since the states are placed on different shards, cross-shard transactions are inevitable, which is detrimental to the performance of the sharding blockchain. Existing solutions place states based on heuristic algorithms or redistribute states via graph-partitioning-based methods, which are either less effective or costly. In this paper, we present SPRING, the first deep-reinforcement-learning(DRL)-based sharding framework for state placement. SPRING formulates the state placement as a Markov Decision Process, which considers the cross-shard transaction ratio and workload balancing and employs DRL to learn the effective state placement policy. Experimental results based on real Ethereum transaction data demonstrate the superiority of SPRING compared to other state placement solutions. In particular, it decreases the cross-shard transaction ratio by up to 26.63% and boosts throughput by up to 36.03%, all without unduly sacrificing the workload balance among shards. Moreover, updating the training model and making decisions takes only 0.1s and 0.002s, respectively, which shows the overhead is acceptable.
论文检索
输入标题、作者或关键词，从 1,090 篇学术成果中精准定位
This paper proposes Meta Parallel Graph Neural Network (MPGNN) to establish a scalable Network Intrusion Detection System (NIDS) for large-scale Internet of Things (IoT) networks. MPGNN leverages a meta-learning framework to optimize the parallelism of GNN-based NIDS. The core of MPGNN is a coalition formation policy that generates meta-knowledge for partitioning a massive graph into multiple coalitions/subgraphs in a way that maximizes the performance and efficiency of parallel coalitional NIDSs. We propose an offline reinforcement learning algorithm, called Graph-Embedded Adversarially Trained Actor-Critic (G-ATAC), to learn a coalition formation policy that jointly optimizes intrusion detection accuracy, communication overheads, and computational complexities of coalitional NIDSs. In particular, G-ATAC learns to capture the temporal dependencies of network states and coalition formation decisions over offline data, eliminating the need for expensive online interactions with large IoT networks. Given generated coalitions, MPGNN employs E-GraphSAGE to establish coalitional NIDSs which then collaborate via ensemble prediction to accomplish intrusion detection for the entire network. We evaluate MPGNN on two real-world datasets. The experimental results demonstrate the superiority of our method with substantial improvements in F1 score, surpassing the state-of-the-art methods by 0.38 and 0.29 for the respective datasets. Compared to the centralized NIDS, MPGNN reduces the training time of NIDS by 41.63% and 22.11%, while maintaining an intrusion detection performance comparable to centralized NIDS.
Recent research has shown that transformer networks can be used as differentiable search indexes by representing each document as a sequence of document ID tokens. These generative retrieval models cast the retrieval problem to a document ID generation problem for each query. Despite their elegant design, existing generative retrieval models only perform well on artificially-constructed and small-scale collections. This paper represents an important milestone in generative retrieval research by showing that generative retrieval models can be trained to perform effectively on large-scale standard retrieval benchmarks. In more detail, we propose RIPOR- an optimization framework for generative retrieval that is designed based on two often-overlooked fundamental design considerations. First, RIPOR introduces a novel prefix-oriented ranking optimization algorithm for accurate estimation of relevance score during sequential document ID generation. Second, RIPOR constructs document IDs based on the relevance associations between queries and documents. Evaluation on MSMARCO and TREC Deep Learning Track reveals that RIPOR surpasses state-of-the-art generative retrieval models by a large margin (e.g., 30.5% MRR improvements on MS MARCO Dev Set).
The similarity matrix is at the core of similarity search problems. However, incomplete observations are ubiquitous in real scenarios leading to a less accurate similarity matrix. To alleviate this problem, in this paper, based on the key insight that the similarity matrix enjoys both the symmetric and positive semi-definiteness (PSD) properties, we propose a novel similarity matrix calibration method, which is scalable, effective, and sound. Specifically, we establish the PSD property as a constraint for the similarity matrix calibration problem and propose a novel similarity matrix calibration method to estimate the similarity matrix, which approximates the unknown complete ground-truth similarity matrix. To enable a fast optimization process, we further develop a general approximated algorithm that bypasses the computation of singular values. Theoretical analysis ensures stable calibration performance and convergence speed. Extensive experiments of similarity matrix calibration on real-world datasets demonstrate that our proposed method outperforms baseline methods in terms of both accuracy and speed.
The forest matrix of a graph, particularly its diagonal elements, has far-reaching implications in network science and machine learning. The state-of-the-art algorithms for the diagonal of forest matrix computation are based on the fast Laplacian solver. However, these algorithms encounter limitations when applied to digraphs due to the incapacity of the Laplacian solver. To overcome the issue, in this paper, we propose three novel sampling-based algorithms:SCF,SCFV,and SCFV+. Our first algorithm SCF leverages a probability interpretation of the diagonal of the forest matrix and utilizes an extension of Wilson's algorithm to sample spanning converging forests. To reduce the variance in the forest sampling, we develop two novel variance-reduced techniques. The first technique, leading to the proposal of the SCFV algorithm, is inspired by opinion dynamics in graphs and applies matrix-vector iteration to the spanning forest sampling. While SCFV achieves reduced variance compared to SCF, the cross-product term in its variance expression can be complex and potentially large in certain graphs. Therefore, we develop another technique, leading to a new iteration equation and the SCFV+ algorithm. SCFV+ achieves further reduced variance without the cross-product term in the variance of SCFV. We prove that SCFV+ can achieve a relative error guarantee with high probability and maintain a linear time complexity relative to the number of nodes in the graph, presenting a superior theoretical result compared to state-of-the-art algorithms. Finally, we conduct extensive experiments on various real-world networks, showing that our algorithms achieve better estimation accuracy and are more time-efficient than the state-of-the-art algorithms. Particularly, our algorithms are scalable to massive graphs with more than twenty million nodes in both undirected and directed graphs.
Centrality measures, quantifying the importance of vertices or edges, play a fundamental role in network analysis. To date, triggered by some positive approximability results, a large body of work has been devoted to studying centrality maximization, where the goal is to maximize the centrality score of a target vertex by manipulating the structure of a given network. On the other hand, due to the lack of such results, only very little attention has been paid to centrality minimization, despite its practical usefulness. In this study, we introduce a novel optimization model for local centrality minimization, where the manipulation is allowed only around the target vertex. We prove the NP-hardness of our model and that the most intuitive greedy algorithm has a quite limited performance in terms of approximation ratio. Then we design two effective approximation algorithms: The first algorithm is a highly-scalable algorithm that has an approximation ratio unachievable by the greedy algorithm, while the second algorithm is a bicriteria approximation algorithm that solves a continuous relaxation based on the Lovász extension, using a projected subgradient method. To the best of our knowledge, ours are the first polynomial-time algorithms with provable approximation guarantees for centrality minimization. Experiments using a variety of real-world networks demonstrate the effectiveness of our proposed algorithms: Our first algorithm is applicable to million-scale graphs and obtains much better solutions than those of scalable baselines, while our second algorithm is rather strong against adversarial instances.
Active learning (AL), that aims to label limited data samples to effectively train the model, stands as a very cost-effective data labelling strategy in machine learning. Given the state-of-the-art performance GNNs have achieved in graph-based tasks, it is critical to design proper AL methods for graph neural networks (GNNs). However, existing GNN-based AL methods require considerable supervised information to guide the AL process, such as the GNN model to use, and initially labelled nodes and labels of newly selected nodes. Such dependency on supervised information limits both flexibility and scalabilty. In this paper, we propose an unsupervised, scalable and flexible AL method - it incurs low memory footprints and time cost, is flexible to the choice of underlying GNNs, and operates without requiring GNN-model-specific knowledge or labels of selected nodes. Specifically, we leverage the commonality of existing GNNs to reformulate the unsupervised AL problem as the Aggregation Involvement Maximization (AIM) problem. The objective of AIM is to maximize the involvement or participation of all nodes during the feature aggregation process of GNNs for nodes to be labelled. In this way, the aggregated features of labelled nodes can be diversified to a large extent, thereby benefiting the training of feature transformation matrices which are major trainable components in GNNs. We prove that the AIM problem is NP-hard and propose an efficient solution with theoretical guarantees. Extensive experiments on public datasets demonstrate the effectiveness, scalability and flexibility of our method. Our study is highly relevant to the track "Graph Algorithms and Modeling for the Web" since we focus one of the major listed topics "Graph Embedding and GNNs for the Web" and AL for GNNs, as an important research problem, is faced by aforementioned challenges to be tackled in this paper.
Graph-theoretic algorithms and graph machine learning models are essential tools for addressing many real-life problems, such as social network analysis and bioinformatics. To support large-scale graph analytics, graph-parallel systems have been actively developed for over one decade, such as Google's Pregel and Spark's GraphX, which (i) promote a think-like-a-vertex computing model and target (ii) iterative algorithms and (iii) those problems that output a value for each vertex. However, this model is too restricted for supporting the rich set of heterogeneous operations for graph analytics and machine learning that many real applications demand. In recent years, two new trends emerge in graph-parallel systems research: (1) a novel think-like-a-task computing model that can efficiently support the various computationally expensive problems of subgraph search; and (2) scalable systems for learning graph neural networks. These systems effectively complement the diversity needs of graph-parallel tools that can flexibly work together in a comprehensive graph processing pipeline for real applications, with the capability of capturing structural features. This tutorial will provide an effective categorization of the recent systems in these two directions based on their computing models and adopted techniques, and will review the key design ideas of these systems.
This tutorial offers a comprehensive guide on using multi-armed bandit (MAB) algorithms to improve Large Language Models (LLMs). As Natural Language Processing (NLP) tasks grow, efficient and adaptive language generation systems are increasingly needed. MAB algorithms, which balance exploration and exploitation under uncertainty, are promising for enhancing LLMs. The tutorial covers foundational MAB concepts, including the exploration-exploitation trade-off and strategies like epsilon-greedy, UCB (Upper Confidence Bound), and Thompson Sampling. It then explores integrating MAB with LLMs, focusing on designing architectures that treat text generation options as arms in a bandit problem. Practical aspects like reward design, exploration policies, and scalability are discussed. Real-world case studies demonstrate the benefits of MAB-augmented LLMs in content recommendation, dialogue generation, and personalized content creation, showing how these techniques improve relevance, diversity, and user engagement.
Seasonal-trend decomposition (STD) is a crucial task in time series data analysis. Due to the challenges of scalability, there is a pressing need for an ultra-fast online algorithm. However, existing algorithms either fail to handle long-period time series (such as OnlineSTL), or need time-consuming iterative processes (such as OneShotSTL). Therefore, we propose BacktrackSTL, the first non-iterative online STD algorithm with period-independent O(1) update complexity. It is also robust to outlier, seasonality shift and trend jump because of the combination of outlier-resilient smoothing, non-local seasonal filtering and backtrack technique. Experimentally, BacktrackSTL decomposes a value within 1.6 μs, which is 15X faster than the state-of-the-art online algorithm OneShotSTL, while maintaining comparable accuracy to the best offline algorithm RobustSTL. We have also deployed BacktrackSTL on the top of Apache Flink to decompose monitoring metrics in Alibaba Cloud for over a year. Besides, we have open-sourced the artifact of this proposal on GitHub.
The learnware paradigm proposed by Zhou (2016) aims to enable users to leverage numerous existing high-performing models instead of building machine learning models from scratch. This paradigm envisions that: Any developer worldwide can submit their well-trained models spontaneously into a learnware dock system (formerly known as learnware market). The system uniformly generates a specification for each model to form a learnware and accommodates it. As the key component, a specification should represent the capabilities of the model while preserving developer's original data. Based on the specifications, the learnware dock system can identify and assemble existing learnwares for users to solve new machine learning tasks. Recently, based on reduced kernel mean embedding (RKME) specification, a series of studies have shown the effectiveness of the learnware paradigm theoretically and empirically. However, the realization of a learnware dock system is still missing and remains a big challenge. This paper proposes Beimingwu, the first open-source learnware dock system, providing foundational support for future research. The system provides implementations and extensibility for the entire process of learnware paradigm, including the submitting, usability testing, organization, identification, deployment, and reuse of learnwares. Utilizing Beimingwu, the model development for new user tasks can be significantly streamlined, thanks to integrated architecture and engine design, specifying unified learnware structure and scalable APIs, and the integration of various algorithms for learnware identification and reuse. Notably, this is possible even for users with limited data and minimal expertise in machine learning, without compromising the raw data's security. The system facilitates the future research implementations in learnware-related algorithms and systems, and lays the ground for hosting a vast array of learnwares and establishing a learnware ecosystem. The system is fully open-source and we expect the research community to benefit from the system. The system and research toolkit have been released on GitLink and GitHub.
In this paper we describe NudgeRankTM, an innovative digital algorithmic nudging system designed to foster positive health behaviors on a population-wide scale. Utilizing a novel combination of Graph Neural Networks augmented with an extensible Knowledge Graph, this Recommender System is operational in production, delivering personalized and context-aware nudges to over 1.1 million care recipients daily. This enterprise deployment marks one of the largest AI-driven health behavior change initiatives, accommodating diverse health conditions and wearable devices. Rigorous evaluation reveals statistically significant improvements in health outcomes, including a 6.17% increase in daily steps and 7.61% more exercise minutes. Moreover, user engagement and program enrollment surged, with a 13.1% open rate compared to baseline systems' 4%. Demonstrating scalability and reliability, NudgeRankTM operates efficiently on commodity compute resources while maintaining automation and observability standards essential for production systems.
In this paper, we tackle the complex task of analyzing televised debates, with a focus on a prime time news debate show from India. Previous methods, which often relied solely on text, fall short in capturing the multimodal essence of these debates [27]. To address this gap, we introduce a comprehensive automated toolkit that employs advanced computer vision and speech-to-text techniques for large-scale multimedia analysis. Utilizing state-of-the-art computer vision algorithms and speech-to-text methods, we transcribe, diarize, and analyze thousands of YouTube videos of a prime-time television debate show in India. These debates are a central part of Indian media but have been criticized for compromised journalistic integrity and excessive dramatization [18]. Our toolkit provides concrete metrics to assess bias and incivility, capturing a comprehensive multimedia perspective that includes text, audio utterances, and video frames. Our findings reveal significant biases in topic selection and panelist representation, along with alarming levels of incivility. This work offers a scalable, automated approach for future research in multimedia analysis, with profound implications for the quality of public discourse and democratic debate. To catalyze further research in this area, we also release the code, dataset collected and supplemental pdf.1
Dynamic Pricing for online retail has been discussed extensively in literature. However, past solutions fell short of addressing the unique challenges of independent multi-retailer platforms for grocery delivery. From limited visibility of retailers' inventories to diverse demand-side dynamics across retail brands and locations, the highly decentralized nature of multi-retailer platforms deviates from the classical framework of modeling price elasticity and cross-elasticity of demand. In this paper, we present a novel scheme to scalable and practical price adjustment in the highly dynamic multi-retailer context. First, we present a deep learning framework to distinctly model complex cross-elasticity relationships via additive neural networks augmented with adversarial data. Second, we present evolutionary optimization agents for adjusting itemized prices in a location-decentralized manner, while adhering to custom business constraints and objectives. The optimization utilizes the genetic algorithm structure, where we introduce a potential mechanism, inspired by bandit algorithms, in order to improve convergence speed by managing exploitation and exploration trade-offs. Our solution is deployed at Shipt and is extendable to other types of multi-retailer platforms, such as restaurant delivery. Finally, we empirically demonstrate performance using public and industry datasets of hundreds and thousands of diverse products across tens of stores, offering an optimization targets coverage scale in the tens of thousands, far larger than experimental setups in past research.
Graph Neural Networks (GNNs) have become pivotal tools for a range of graph-based learning tasks. Notably, most current GNN architectures operate under the assumption of homophily, whether explicitly or implicitly. While this underlying assumption is frequently adopted, it is not universally applicable, which can result in potential shortcomings in learning effectiveness. In this paper, or the first time, we transfer the prevailing concept of "one node one receptive field" to the heterophilic graph. By constructing a proxy label predictor, we enable each node to possess a latent prediction distribution, which assists connected nodes in determining whether they should aggregate their associated neighbors. Ultimately, every node can have its own unique aggregation hop and pattern, much like each snowflake is unique and possesses its own characteristics. Based on observations, we innovatively introduce the Heterophily Snowflake Hypothesis and provide an effective solution to guide and facilitate research on heterophilic graphs and beyond. We conduct comprehensive experiments including (1) main results on 10 graphs with varying heterophily ratios across 10 backbones; (2) scalability on various deep GNN backbones (SGC, JKNet, etc.) across various large number of layers (2,4,6,8,16,32 layers); (3) comparison with conventional snowflake hypothesis; (4) efficiency comparison with existing graph pruning algorithms. Our observations show that our framework acts as a versatile operator for diverse tasks. It can be integrated into various GNN frameworks, boosting performance in-depth and offering an explainable approach to choosing the optimal network depth. The source code is available at https://github.com/bingreeky/HeteroSnoH.
The forest matrix plays a crucial role in network science, opinion dynamics, and machine learning, offering deep insights into the structure of and dynamics on networks. In this paper, we study the problem of querying entries of the forest matrix in evolving graphs, which more accurately represent the dynamic nature of real-world networks compared to static graphs. To address the unique challenges posed by evolving graphs, we first introduce two approximation algorithms, SFQ and SFQPlus, for static graphs. SFQ employs a probabilistic interpretation of the forest matrix, while SFQPlus incorporates a novel variance reduction technique and is theoretically proven to offer enhanced accuracy. Based on these two algorithms, we further devise two dynamic algorithms centered around efficiently maintaining a list of spanning converging forests. This approach ensures O(1) runtime complexity for updates, including edge additions and deletions, as well as for querying matrix elements, and provides an unbiased estimation of forest matrix entries. Finally, through extensive experiments on various real-world networks, we demonstrate the efficiency and effectiveness of our algorithms. Particularly, our algorithms are scalable to massive graphs with more than forty million nodes.
Finding dense subnetworks, with density based on edges or more complex structures, such as subgraphs or k-cliques, is a fundamental algorithmic problem with many applications. While the problem has been studied extensively in static networks, much remains to be explored for temporal networks. In this work we introduce the novel problem of identifying the temporal motif densest subnetwork, i.e., the densest subnetwork with respect to temporal motifs, which are high-order patterns characterizing temporal networks. Identifying temporal motifs is an extremely challenging task, and thus, efficient methods are required. To address this challenge, we design two novel randomized approximation algorithms with rigorous probabilistic guarantees that provide high-quality solutions. We perform extensive experiments showing that our methods outperform baselines. Furthermore, our algorithms scale on networks with up to billions of temporal edges, while baselines cannot handle such large networks. We use our techniques to analyze a financial network and show that our formulation reveals important network structures, such as bursty temporal events and communities of users with similar interests.
Learning interpretable models has become a major focus of machine learning research, given the increasing prominence of machine learning in socially important decision-making. Among interpretable models, rule lists are among the best-known and easily interpretable ones. However, finding optimal rule lists is computationally challenging, and current approaches are impractical for large datasets. We present a novel and scalable approach to learn nearly optimal rule lists from large datasets. Our algorithm uses sampling to efficiently obtain an approximation of the optimal rule list with rigorous guarantees on the quality of the approximation. In particular, our algorithm guarantees to find a rule list with accuracy very close to the optimal rule list when a rule list with high accuracy exists. Our algorithm builds on the VC-dimension of rule lists, for which we prove novel upper and lower bounds. Our experimental evaluation on large datasets shows that our algorithm identifies nearly optimal rule lists with a speed-up up to two orders of magnitude over state-of-the-art exact approaches. Moreover, our algorithm is as fast as, and sometimes faster than, recent heuristic approaches, while reporting higher quality rule lists. In addition, the rules reported by our algorithm are more similar to the rules in the optimal rule list than the rules from heuristic approaches.
Differentiable causal discovery has made significant advancements in the learning of directed acyclic graphs. However, its application to real-world datasets remains restricted due to the ubiquity of latent confounders and the requirement to learn maximal ancestral graphs (MAGs). To date, existing differentiable MAG learning algorithms have been limited to small datasets and failed to scale to larger ones (e.g., with more than 50 variables). The key insight in this paper is that the causal skeleton, which is the undirected version of the causal graph, has potential for improving accuracy and reducing the search space of the optimization procedure, thereby enhancing the performance of differentiable causal discovery. Therefore, we seek to address a two-fold challenge to harness the potential of the causal skeleton for differentiable causal discovery in the presence of latent confounders: (1) scalable and accurate estimation of skeleton and (2) universal integration of skeleton estimation with differentiable causal discovery. To this end, we propose SPOT (Skeleton Posterior-guided OpTimization), a two-phase framework that harnesses skeleton posterior for differentiable causal discovery in the presence of latent confounders. On the contrary to a "point-estimation", SPOT seeks to estimate the posterior distribution of skeletons given the dataset. It first formulates the posterior inference as an instance of amortized inference problem and concretizes it with a supervised causal learning (SCL)-enabled solution to estimate the skeleton posterior. To incorporate the skeleton posterior with differentiable causal discovery, SPOT then features a skeleton posterior-guided stochastic optimization procedure to guide the optimization of MAGs. Extensive experiments on various datasets show that SPOT substantially outperforms SOTA methods for MAG learning. SPOT also demonstrates its effectiveness in the accuracy of skeleton posterior estimation in comparison with non-parametric bootstrap-based, or more recently, variational inference-based methods. Finally, we observe that the adoption of skeleton posterior exhibits strong promise in various causal discovery tasks.
High-Dimensional Distributed Sparse Classification with Scalable Communication-Efficient Global Updates
PDF ↗As the size of datasets used in statistical learning continues to grow, distributed training of models has attracted increasing attention. These methods partition the data and exploit parallelism to reduce memory and runtime, but suffer increasingly from communication costs as the data size or the number of iterations grows. Recent work on linear models has shown that a surrogate likelihood can be optimized locally to iteratively improve on an initial solution in a communication-efficient manner. However, existing versions of these methods experience multiple shortcomings as the data size becomes massive, including diverging updates and efficiently handling sparsity. In this work we develop solutions to these problems which enable us to learn a communication-efficient distributed logistic regression model even beyond millions of features. In our experiments we demonstrate a large improvement in accuracy over distributed algorithms with only a few distributed update steps needed, and similar or faster runtimes. Our code is available at https://github.com/FutureComputing4AI/ProxCSL.