Random walk (RW)-based algorithms have long been popular in distributed systems due to low overheads and scalability, with recent growing applications in decentralized learning. However, their reliance on local interactions makes them inherently vulnerable to malicious behavior. In this work, we investigate an adversarial threat that we term the ``Pac-Man'' attack, in which a malicious node probabilistically terminates any RW that visits it. This stealthy behavior gradually eliminates active RWs from the network, effectively halting the learning process without triggering failure alarms. To counter this threat, we propose the Average Crossing (AC) algorithm--a fully decentralized mechanism for duplicating RWs to prevent RW extinction in the presence of Pac-Man. Our theoretical analysis establishes that (i) the RW population remains almost surely bounded under AC and (ii) RW-based stochastic gradient descent remains convergent under AC, even in the presence of Pac-Man, with a quantifiable deviation from the true optimum. Our extensive empirical results on both synthetic and real-world datasets corroborate our theoretical findings. Furthermore, they uncover a phase transition in the extinction probability as a function of the duplication threshold. We offer theoretical insights by analyzing a simplified variant of the AC, which sheds light on the observed phase transition.

With the rising demand for high-rate and timely communications, fog radio access networks (F-RANs) offer a promising solution. This work investigates age of information (AoI) performance in F-RANs, consisting of multiple content users (CUs), enhanced remote radio heads (eRRHs), and content providers (CPs). Time-critical CUs need rapid content updates from CPs but cannot communicate directly with them; instead, eRRHs act as intermediaries. CUs decide whether to request content from a CP and which eRRH to send the request to, while eRRHs decide whether to command CPs to update content or use cached content. We study two broad classes of policies: (i) oblivious policies, where decision-making is independent of historical information, and (ii) non-oblivious policies, where decisions are influenced by historical information. We first derive closed-form expressions for the average AoI of eRRHs under both policy types. Due to the complexity of calculating closed-form expressions for CUs, we then derive general upper bounds for their average AoI. Next, we identify optimal policies for both types. Under both optimal policies, each CU requests content from each CP at an equal rate. When demand is low or resources are limited, all requests are consolidated to a single eRRH; when demand is high and resources are ample, requests are evenly distributed among eRRHs. eRRHs command content from each CP at an equal rate under an optimal oblivious policy, while prioritize the CP with the highest age under an optimal non-oblivious policy. Our numerical results validate these theoretical findings. We further extend our analytical framework to two generalized scenarios, and simulations confirm the validity of our conclusions.

OBJECTIVES: To conduct a scoping review (ScR) of existing approaches for synthetic Electronic Health Records (EHR) data generation, to benchmark major methods, and to provide an open-source software and offer recommendations for practitioners. MATERIALS AND METHODS: We search three academic databases for our scoping review. Methods are benchmarked on open-source EHR datasets, Medical Information Mart for Intensive Care III and IV (MIMIC-III/IV). Seven existing methods covering major categories and two baseline methods are implemented and compared. Evaluation metrics concern data fidelity, downstream utility, privacy protection, and computational cost. RESULTS: Forty-eight studies are identified and classified into five categories. Seven open-source methods covering all categories are selected, trained on MIMIC-III, and evaluated on MIMIC-III or MIMIC-IV for transportability considerations. Among them, Generative Adversarial Network (GAN)-based methods demonstrate competitive performance in fidelity and utility on MIMIC-III, rule-based methods excel in privacy protection. Similar findings are observed on MIMIC-IV, except that GAN-based methods further outperform the baseline methods in preserving fidelity. DISCUSSION: Method choice is governed by the relative importance of the evaluation metrics in downstream use cases. We provide a decision tree to guide the choice among the benchmarked methods. An extensible Python package, "SynthEHRella", is provided to facilitate streamlined evaluations. CONCLUSION: GAN-based methods excel when distributional shifts exist between the training and testing populations. Otherwise, CorGAN and MedGAN are most suitable for association modeling and predictive modeling, respectively. Future research should prioritize enhancing fidelity of the synthetic data while controlling privacy exposure, and comprehensive benchmarking of longitudinal or conditional generation methods.

In communication and computation cooperative networks (3CNs), timely computation is crucial but not always guaranteed. There is a strong demand for a computational task to be completed within a given deadline. The time taken involves processing time, transmission time, and the impact of the deadline. However, a measure of such timeliness in 3CNs is lacking. To address this gap, we propose the novel concept of Age of Computing (AoC) to quantify computation freshness in 3CNs. Built on task timestamps, AoC serves as a practical metric for dynamic and complex real-world 3CNs. We evaluate AoC under two types of deadlines: (i) soft deadline, tasks can be fed back to the source if delayed beyond the deadline, but with additional latency; (ii) hard deadline, tasks delayed beyond the deadline are discarded. We investigate AoC in two distinct networks. In point-to-point, time-continuous networks, tasks are processed sequentially using a first-come, first-served discipline. We derive a general expression for the time-average AoC under both deadlines. Utilizing this expression, we obtain a closed-form solution for M/M/1-M/M/1 systems under soft deadlines and propose an accurate approximation for hard deadlines. These results are further extended to G/G/1-G/G/1 systems. Additionally, we introduce the concept of computation throughput, derive its general expression and an approximation, and explore the trade-off between freshness and throughput. In the multi-source, time-discrete networks, tasks are scheduled for offloading to a computational node. For this scenario, we develop AoC-based Max-Weight policies for real-time scheduling under both deadlines, leveraging a Lyapunov function to minimize its drift.

Recent studies have shown competitive performance in protein inverse folding, while most of them disregard the importance of predictive confidence, fail to cover the vast protein space, and do not incorporate common protein knowledge. Given the great success of pretrained models on diverse protein-related tasks and the fact that recovery is highly correlated with confidence, we wonder whether this knowledge can push the limits of protein design further. As a solution, we propose a knowledge-aware module that refines low-quality residues. We also introduce a memory-retrieval mechanism to save more than 50\% of the training time. We extensively evaluate our proposed method on the CATH, TS50, TS500, and PDB datasets and our results show that our KW-Design method outperforms the previous PiFold method by approximately 9\% on the CATH dataset. KW-Design is the first method that achieves 60+\% recovery on all these benchmarks. We also provide additional analysis to demonstrate the effectiveness of our proposed method. The code is publicly available via \href{https://github.com/A4Bio/ProteinInvBench}{GitHub}.

Self-supervised learning (SSL) has recently emerged as a promising paradigm for training generalisable models on large-scale data in the fields of vision, text, and speech. Although SSL has been proven effective in speech and audio, its application to music audio has yet to be thoroughly explored. This is partially due to the distinctive challenges associated with modelling musical knowledge, particularly tonal and pitched characteristics of music. To address this research gap, we propose an acoustic **M**usic und**ER**standing model with large-scale self-supervised **T**raining (**MERT**), which incorporates teacher models to provide pseudo labels in the masked language modelling (MLM) style acoustic pre-training. In our exploration, we identified an effective combination of teacher models, which outperforms conventional speech and audio approaches in terms of performance. This combination includes an acoustic teacher based on Residual Vector Quantization - Variational AutoEncoder (RVQ-VAE) and a musical teacher based on the Constant-Q Transform (CQT). Furthermore, we explore a wide range of settings to overcome the instability in acoustic language model pre-training, which allows our designed paradigm to scale from 95M to 330M parameters. Experimental results indicate that our model can generalise and perform well on 14 music understanding tasks and attain state-of-the-art (SOTA) overall scores.

The secondary structure of ribonucleic acid (RNA) is more stable and accessible in the cell than its tertiary structure, making it essential for functional prediction. Although deep learning has shown promising results in this field, current methods suffer from poor generalization and high complexity. In this work, we reformulate the RNA secondary structure prediction as a K-Rook problem, thereby simplifying the prediction process into probabilistic matching within a finite solution space. Building on this innovative perspective, we introduce RFold, a simple yet effective method that learns to predict the most matching K-Rook solution from the given sequence. RFold employs a bi-dimensional optimization strategy that decomposes the probabilistic matching problem into row-wise and column-wise components to reduce the matching complexity, simplifying the solving process while guaranteeing the validity of the output. Extensive experiments demonstrate that RFold achieves competitive performance and about eight times faster inference efficiency than the state-of-the-art approaches. The code is available at https://github.com/A4Bio/RFold.

In applications of group testing in networks, e.g. identifying individuals who are infected by a disease spread over a network, exploiting correlation among network nodes provides fundamental opportunities in reducing the number of tests needed. We model and analyze group testing on n correlated nodes whose interactions are specified by a graph G. We model correlation through an edge-faulty random graph formed from G in which each edge is dropped with probability$1-r$, and in the newly formed graph, all nodes in the same component have the same state. We consider three classes of graphs: cycles and trees, d-regular graphs and stochastic block models or SBM, and obtain lower and upper bounds on the number of tests needed to identify the defective nodes. Roughly speaking, we use correlation among the states of the nodes to transform the problem into that of a smaller graph with independent node states. This enhancement is quantified through the ratio of the diminished node count to the overall count of nodes, n; thus, a lower ratio signifies superior performance. The lower bounds are derived by illustrating a strong dependence of the number of tests needed on the expected number of components. In this regard, we establish a new approximation for the distribution of component sizes in “d-regular trees” which may be of independent interest and leads to a lower bound on the expected number of components in d-regular graphs. The upper bounds are found by forming dense subgraphs in which nodes are more likely to be in the same state. When G is a cycle or tree, we show an improvement by a factor of$\log (1/r)$. For grid, a graph with almost$2n$edges, the improvement is by a factor of$(1-r) \log (1/r)$, indicating drastic improvement compared to trees. When G has a larger number of edges, as in SBM, the improvement can scale in n.

Recent years have witnessed the emergence of textual commonsense knowledge bases, aimed at providing more nuanced and contextrich knowledge.The integration of external commonsense into language models has been shown to be a key enabler in advancing the state-of-the-art for a wide range of NLP tasks.However, incorporating textual commonsense descriptions is computationally expensive, as compared to encoding conventional symbolic knowledge.In this paper, we propose a method to improve its efficiency without modifying the model.We group training samples with similar commonsense descriptions into a single batch, thus reusing the encoded description across multiple samples.One key observation is that the upper bound of batch partitioning can be reduced to the classic graph k-cut problem.Consequently, we propose a spectral clusteringbased algorithm to solve this problem.Extensive experiments illustrate that the proposed batch partitioning approach effectively reduces the computational cost while preserving performance.The efficiency improvement is more pronounced on larger datasets and on devices with more memory capacity, attesting to its practical utility for large-scale applications.

Protein inverse folding has attracted increasing attention in recent years. However, we observe that current methods are usually limited to the CATH dataset and the recovery metric. The lack of a unified framework for ensembling and comparing different methods hinders the comprehensive investigation. In this paper, we propose ProteinBench, a new benchmark for protein design, which comprises extended protein design tasks, integrated models, and diverse evaluation metrics. We broaden the application of methods originally designed for single-chain protein design to new scenarios of multi-chain and \textit{de novo} protein design. Recent impressive methods, including GraphTrans, StructGNN, GVP, GCA, AlphaDesign, ProteinMPNN, PiFold and KWDesign are integrated into our framework. In addition to the recovery, we also evaluate the confidence, diversity, sc-TM, efficiency, and robustness to thoroughly revisit current protein design approaches and inspire future work. As a result, we establish the first comprehensive benchmark for protein design, which is publicly available at \url{https://github.com/A4Bio/OpenCPD}.

In the era of extensive intersection between art and Artificial Intelligence (AI), such as image generation and fiction co-creation, AI for music remains relatively nascent, particularly in music understanding. This is evident in the limited work on deep music representations, the scarcity of large-scale datasets, and the absence of a universal and community-driven benchmark. To address this issue, we introduce the Music Audio Representation Benchmark for universaL Evaluation, termed MARBLE. It aims to provide a benchmark for various Music Information Retrieval (MIR) tasks by defining a comprehensive taxonomy with four hierarchy levels, including acoustic, performance, score, and high-level description. We then establish a unified protocol based on 18 tasks on 12 public-available datasets, providing a fair and standard assessment of representations of all open-sourced pre-trained models developed on music recordings as baselines. Besides, MARBLE offers an easy-to-use, extendable, and reproducible suite for the community, with a clear statement on copyright issues on datasets. Results suggest recently proposed large-scale pre-trained musical language models perform the best in most tasks, with room for further improvement. The leaderboard and toolkit repository are published to promote future music AI research.

In applications of group testing in networks, e.g. identifying individuals who are infected by a disease spread over a network, exploiting correlation among network nodes provides fundamental opportunities in reducing the number of tests needed. We model and analyze group testing on n correlated nodes whose interactions are specified by a graph G. We model correlation through an edge-faulty random graph formed from G in which each edge is dropped with probability 1−r, and all nodes in the same component have the same state.We consider three classes of graphs: cycles and trees, d-regular graphs, and stochastic block models or SBM, and obtain lower and upper bounds on the number of tests needed to identify the defective nodes. Our results are expressed in terms of the number of tests needed when the nodes are independent and they are in terms of n, r, and the target error. In particular, we quantify the fundamental improvements that exploiting correlation offers by the ratio between the total number of nodes n and the equivalent number of independent nodes in a classic group testing algorithm.The lower bounds are derived by illustrating a strong dependence of the number of tests needed on the expected number of components. In this regard, we establish a new approximation for the distribution of component sizes in "d-regular trees" which may be of independent interest and leads to a lower bound on the expected number of components in d-regular graphs.The upper bounds are found by forming dense subgraphs in which nodes are more likely to be in the same state. When G is a cycle or tree, we show an improvement by a factor of log(1/r). For grid, a graph with almost 2n edges, the improvement is by a factor of (1 − r)log(1/r), indicating drastic improvement compared to trees. When G has a larger number of edges, as in SBM, the improvement can scale in n.

In this paper, we propose a new method for knowledge base completion (KBC): instance-based learning (IBL). For example, to answer (Jill Biden, lived city,? ), instead of going directly to Washington D.C., our goal is to find Joe Biden, who has the same lived city as Jill Biden. Through prototype entities, IBL provides interpretability. We develop theories for modeling prototypes and combining IBL with translational models. Experiments on various tasks confirmed the IBL model's effectiveness and interpretability.In addition, IBL shed light on the mechanism of rule-based KBC models. Previous research has generally agreed that rule-based models provide rules with semantically compatible premise and hypothesis. We challenge this view. We begin by demonstrating that some logical rules represent {\it instance-based equivalence} (i.e. prototypes) rather than semantic compatibility. These are denoted as {\it IBL rules}. Surprisingly, despite occupying only a small portion of the rule space, IBL rules outperform non-IBL rules in all four benchmarks. %KBC can be achieved using only IBL rules in two benchmarks without sacrificing effectiveness. We use a variety of experiments to demonstrate that rule-based models work because they have the ability to represent instance-based equivalence via IBL rules. The findings provide new insights of how rule-based models work and how to interpret their rules.

In applications of remote sensing, estimation, and control, timely communication is critical but not always ensured by high-rate communication. This work proposes decentralized age-efficient transmission policies for random access channels with$M$transmitters. We propose the notion ofage-gainof a packet to quantify how much the packet will reduce the instantaneous age of information at the receiver side upon successful delivery. We then utilize this notion to propose a transmission policy in which transmitters act in a decentralized manner based on the age-gain of their available packets. In particular, each transmitter sends its latest packet only if its corresponding age-gain is beyond a certain threshold which could be computed adaptively using the collision feedback or found as a fixed value analytically in advance. Both methods improve age of information significantly compared to the state of the art. In the limit of large$M$, we prove that when the arrival rate is small (below$\frac {1}{eM}$), slotted ALOHA-type algorithms are order optimal. As the arrival rate increases beyond$\frac {1}{eM}$, while age increases under slotted ALOHA, it decreases significantly under the proposed age-based policies. For arrival rates$\theta $,$\theta =\frac {1}{o(M)}$, the proposed algorithms provide a multiplicative gain of at least two compared to the minimum age under slotted ALOHA (minimum over all arrival rates). We conclude that it is beneficial to increase the sampling rate (and hence the arrival rate) and transmit packets selectively based on their age-gain. This is surprising and contrary to common practice where the arrival rate is optimized to attain the minimum AoI. We further extend our results to other random access technologies such as Carrier-sense multiple access (CSMA).

Real-time sampling and estimation of autoregressive Markov processes is considered in random access channels. Two classes of policies are studied: (i) oblivious policies in which decision making is independent of the source realizations, and (ii) non-oblivious policies in which sources are observed causally for decision making. In the first class, minimizing the expected time-average estimation error is equivalent to minimizing the expected age of information (AoI). Lower and upper bounds are provided for the achievable estimation error in this class and age-based threshold policies are shown to provide a two-fold improvement compared to the state-of-the-art. In the second class, an error-based threshold policy is proposed: a transmitter becomes active when its error exceeds a threshold in which case it transmits probabilistically following slotted ALOHA. A closed-form expression is derived for the estimation error as a function of the peak age, the transmission delay, a term which we call the silence delay, as well as the source realization. It is analyzed approximately by considering the underlying source as a discretized Wiener process. The proposed threshold policy provides a three-fold improvement compared to oblivious policies and its performance is close to that of centralized greedy scheduling.

The interplay between timeliness and rate efficiency is investigated in packet erasure broadcast channels with feedback. A scheduling framework is proposed in which coding actions, as opposed to users, are scheduled to attain desired tradeoffs between rate and age of information (AoI). This tradeoff is formalized by an upper bound on AoI as a function of the target rate constraints and two lower bounds: one as a function of the communication rate and one as a function of the arrival rate. Simulation results show that (i) surprisingly, coding can be beneficial in reducing AoI in the regime of moderate arrival rates even without rate constraints and the benefit increases with the number of users, and (ii) AoI increases with both the target rate constraint and the arrival rate when either is kept fixed, but decreases with them when they are set to be equal.

Rules have a number of desirable properties. It is easy to understand, infer new knowledge, and communicate with other inference systems. One weakness of the previous rule induction systems is that they only find rules within a knowledge base (KB) and therefore cannot generalize to more open and complex real-world rules. Recently, the language model (LM)-based rule generation are proposed to enhance the expressive power of the rules.In this paper, we revisit the differences between KB-based rule induction and LM-based rule generation. We argue that, while KB-based methods inducted rules by discovering data commonalitiess, the current LM-based methods are learning rules from rules''. This limits these methods to only producecanned'' rules whose patterns are constrained by the annotated rules, while discarding the rich expressive power of LMs for free text.Therefore, in this paper, we propose the open rule induction problem, which aims to induce open rules utilizing the knowledge in LMs. Besides, we propose the Orion (\underline{o}pen \underline{r}ule \underline{i}nducti\underline{on}) system to automatically mine open rules from LMs without supervision of annotated rules. We conducted extensive experiments to verify the quality and quantity of the inducted open rules. Surprisingly, when applying the open rules in downstream tasks (i.e. relation extraction), these automatically inducted rules even outperformed the manually annotated rules.

In applications of remote sensing, estimation, and control, timely communication is not always ensured by high-rate communication. Oftentimes, it is observed that as the capacity of a system is approached, delay increases significantly and so does age of information - a metric recently proposed to capture freshness and timeliness of information. This work proposes decentralized age-efficient transmission policies for random access channels with M transmitters and provides asymptotic results for the age of information as M → ∞. Slotted ALOHA-type algorithms are shown to be asymptotically age-optimal for arrival rates below 1/eM and far from optimal for larger arrival rates. For larger arrival rates, novel decentralized age-based policies are proposed that benefit from the availability of fresh packets to reduce age of information. For arrival rates θ, θ = 1/o(M)1, the proposed algorithms provide a multiplicative gain factor of at least two compared to the state-of-the-art schemes. We conclude that it is beneficial to increase the sampling rate (and hence the arrival rate) and transmit packets selectively based on their “age-gains”, a notion defined in the paper. This is surprising and contrary to common practice where the arrival rate is optimized to attain the minimum AoI.

Coding for random access communication is a key challenge in Internet of Things applications. In this paper, the well-known scheme of Coded Slotted Aloha (CSA) is considered and its performance is analyzed in the non-asymptotic regime where the frame length and the number of users are finite. A density evolution framework is provided to describe the dynamics of decoding, and fundamental limits are found on the maximum channel load (i.e., the number of active users per time slot) that allows reliable communication (successful decoding). Finally, scaling laws are established, describing the non-asymptotic relation between the probability of error, the number of users, and the channel load.

Age of Information (AoI) is studied in two-user broad-cast networks with feedback, and lower and upper bounds are derived on the expected weighted sum AoI of the users. In particular, a class of simple coding actions is considered and within this class, randomized and deterministic policies are devised. Explicit conditions are found for symmetric dependent channels under which coded randomized policies strictly outperform the corresponding uncoded policies. Similar behaviour is shown numerically for deterministic policies.