We present a novel information-preserving Chaos Game Representation (CGR) method, also called Reverse-CGR (R-CGR), for biological sequence analysis that addresses the fundamental limitation of traditional CGR approaches - the loss of sequence information during geometric mapping. Our method introduces complete sequence recovery through explicit path encoding combined with rational arithmetic precision control, enabling perfect sequence reconstruction from stored geometric traces. Unlike purely geometric approaches, our reversibility is achieved through comprehensive path storage that maintains both positional and character information at each step. We demonstrate the effectiveness of R-CGR on biological sequence classification tasks, achieving competitive performance compared to traditional sequence-based methods while providing interpretable geometric visualizations. The approach generates feature-rich images suitable for deep learning while maintaining complete sequence information through explicit encoding, opening new avenues for interpretable bioinformatics analysis where both accuracy and sequence recovery are essential.

Graph summarization has become integral for managing and analyzing large-scale graphs in diverse real-world applications, including social networks, biological networks, and communication networks. Existing methods for graph summarization often face challenges, being either computationally expensive, limiting their applicability to large graphs, or lacking the incorporation of node attributes. In response, we introduce SsAG , an efficient and scalable lossy graph summarization method designed to preserve the essential structure of the original graph. SsAG computes a sparse representation (summary) of the input graph, accommodating graphs with node attributes. The summary is structured as a graph on supernodes (subsets of vertices of G ), where weighted superedges connect pairs of supernodes. The methodology focuses on constructing a summary graph with k supernodes, aiming to minimize the reconstruction error (the difference between the original graph and the graph reconstructed from the summary) while maximizing homogeneity with respect to the node attributes. The construction process involves iteratively merging pairs of nodes. To enhance computational efficiency, we derive a closed-form expression for efficiently computing the reconstruction error (RE) after merging a pair, enabling constant-time approximation of this score. We assign a weight to each supernode, quantifying their contribution to the score of pairs, and utilize a weighted sampling strategy to select the best pair for merging. Notably, a logarithmic-sized sample achieves a summary comparable in quality based on various measures. Additionally, we propose a sparsification step for the constructed summary, aiming to reduce storage costs to a specified target size with a marginal increase in RE. Empirical evaluations across diverse real-world graphs demonstrate that SsAG exhibits superior speed, being up to 17 × faster, while generating summaries of comparable quality. This work represents a significant advancement in the field, addressing computational challenges and showcasing the effectiveness of SsAG in graph summarization.

Biological sequence analysis is crucial in understanding the sequence structure, function, and evolutionary relationships. In traditional methods, using Euclidean distance metrics is common in measuring the similarity between sequence embeddings. However, they fail to capture sequence space’s inherent curvature and spherical nature. Therefore, we explore the application of spherical geometry and distance metric, circular arc length (CAL) based distance for comparing biological sequence embeddings. Spherical geometry is a non-Euclidean geometry that models the surface of a sphere, accounting for its curvature. By leveraging CAL, we can more accurately measure the pairwise distances between bio-sequence embeddings. In this study, we propose the utilization of CAL for comparing bio-sequence embeddings. We develop a function to compute the CAL distance between two sequence embeddings, enabling researchers to accurately measure the similarity between sequences while considering the underlying spherical geometry. Incorporating spherical geometry enables a more comprehensive understanding of the relationships and similarities between biological sequences, improving various downstream tasks such as classification, clustering, and evolutionary analysis. Our experimental evaluation demonstrates the advantages of using a spherical distance metric over Euclidean metrics for bio-sequence analysis. Our proposed CAL-based approach outperforms the Euclidean geometry-based baselines by depicting a huge performance improvement for the protein subcellular location classification task. In our experiments, accuracy is improved by 52.5% and 60. 3% compared to the PWM2Vec and Autoencoder methods, respectively, corresponding to the DT classifier.

Feature extraction is an essential task in graph analytics. These feature vectors, called graph descriptors, are used in downstream vector-space-based graph analysis models. This idea has proved fruitful in the past, with spectral-based graph descriptors providing state-of-the-art classification accuracy. However, known algorithms to compute meaningful descriptors do not scale to large graphs since: (1) they require storing the entire graph in memory, and (2) the end-user has no control over the algorithm’s runtime. In this article, we present streaming algorithms to approximately compute three different graph descriptors capturing the essential structure of graphs. Operating on edge streams allows us to avoid storing the entire graph in memory, and controlling the sample size enables us to keep the runtime of our algorithms within desired bounds. We demonstrate the efficacy of the proposed descriptors by analyzing the approximation error and classification accuracy. Our scalable algorithms compute descriptors of graphs with millions of edges within minutes. Moreover, these descriptors yield predictive accuracy comparable to the state-of-the-art methods but can be computed using only 25% as much memory.

The SARS-CoV-2 coronavirus is the cause of the COVID-19 disease in humans. Like many coronaviruses, it can adapt to different hosts and evolve into different lineages. It is well-known that the major SARS-CoV-2 lineages are characterized by mutations that happen predominantly in the spike protein. Understanding the spike protein structure and how it can be perturbed is vital for understanding and determining if a lineage is of concern. These are crucial to identifying and controlling current outbreaks and preventing future pandemics. Machine learning (ML) methods are a viable solution to this effort, given the volume of available sequencing data, much of which is unaligned or even unassembled. However, such ML methods require fixed-length numerical feature vectors in Euclidean space to be applicable. Similarly, euclidean space is not considered the best choice when working with the classification and clustering tasks for biological sequences. For this purpose, we design a method that converts the protein (spike) sequences into the sequence similarity network (SSN). We can then use SSN as an input for the classical algorithms from the graph mining domain for the typical tasks such as classification and clustering to understand the data. We show that the proposed alignment-free method is able to outperform the current SOTA method in terms of clustering results. Similarly, we are able to achieve higher classification accuracy using well-known Node2Vec-based embedding compared to other baseline embedding approaches.

Data analysis requires a pairwise proximity measure over objects. Recent work has extended this to situations where the distance information between objects is given as comparison results of distances between three objects (triplets). Humans find comparison tasks much easier than the exact distance computation, and such data can be easily obtained in big quantities via crowdsourcing. In this work, we propose triplets augmentation, an efficient method to extend the triplets data by inferring the hidden implicit information from the existing data. Triplets augmentation improves the quality of kernel-based and kernel-free data analytics. We also propose a novel set of algorithms for common data analysis tasks based on triplets. These methods work directly with triplets and avoid kernel evaluations, thus are scalable to big data. We demonstrate that our methods outperform the current best-known techniques and are robust to noisy data.

The t-distributed stochastic neighbor embedding (t-SNE) is a method for interpreting high dimensional (HD) data by mapping each point to a low dimensional (LD) space (usually two-dimensional). It seeks to retain the structure of the data. An important component of the t-SNE algorithm is the initialization procedure, which begins with the random initialization of an LD vector. Points in this initial vector are then updated to minimize the loss function (the KL divergence) iteratively using gradient descent. This leads comparable points to attract one another while pushing dissimilar points apart. We believe that, by default, these algorithms should employ some form of informative initialization. Another essential component of the t-SNE is using a kernel matrix, a similarity matrix comprising the pairwise distances among the sequences. For t-SNE-based visualization, the Gaussian kernel is employed by default in the literature. However, we show that kernel selection can also play a crucial role in the performance of t-SNE.In this work, we assess the performance of t-SNE with various alternative initialization methods and kernels, using four different sets, out of which three are biological sequences (nucleotide, protein, etc.) datasets obtained from various sources, such as the well-known GISAID database for sequences of the SARS-CoV-2 virus. We perform subjective and objective assessments of these alternatives. We use the resulting t-SNE plots and k-ary neighborhood agreement (k-ANA) to evaluate and compare the proposed methods with the baselines. We show that by using different techniques, such as informed initialization and kernel matrix selection, that t-SNE performs significantly better. Moreover, we show that t-SNE also takes fewer iterations to converge faster with more intelligent initialization.

Analysis of the fairness of machine learning (ML) algorithms has attracted many researchers’ interest. Several studies have shown that ML methods produce a bias toward different groups, which limits the applicability of ML models in many applications, such as crime rate prediction. The data used for ML may have missing values, which, if not appropriately handled, are known to further harmfully affect fairness. To address this issue, many imputation methods have been proposed to deal with missing data. However, research on the effect of missing data imputation on fairness is still rather limited. In this paper, we analyze the impact of imputation on fairness in the context of graph data (node attributes) using different embedding and neural network methods. Extensive experiments on six datasets demonstrate several issues of fairness in graph node classification when dealing with missing data and various imputation techniques. We find that the choice of the imputation method affects both fairness and accuracy. Our results provide valuable insights into fairness ML over graph data and how to handle missingness in graphs efficiently.

With the rapid global spread of COVID-19, more and more data related to this virus is becoming available, including genomic sequence data. The total number of genomic sequences that are publicly available on platforms such as GISAID is currently several million, and is increasing with every day. The availability of such Big Data creates a new opportunity for researchers to study this virus in detail. This is particularly important with all of the dynamics of the COVID-19 variants which emerge and circulate. This rich data source will give us insights on the best ways to perform genomic surveillance for this and future pandemic threats, with the ultimate goal of mitigating or eliminating such threats. Analyzing and processing the several million genomic sequences is a challenging task. Although traditional methods for sequence classification are proven to be effective, they are not designed to deal with these specific types of genomic sequences. Moreover, most of the existing methods also face the issue of scalability. Previous studies which were tailored to coronavirus genomic data proposed to use spike sequences (corresponding to a subsequence of the genome), rather than using the complete genomic sequence, to perform different machine learning (ML) tasks such as classification and clustering. However, those methods suffer from scalability issues.In this paper, we propose an approach called Spike2Vec, an efficient and scalable feature vector representation for each spike sequence that can be used for downstream ML tasks. Through experiments, we show that Spike2Vec is not only scalable on several million spike sequences, but also outperforms the baseline models in terms of prediction accuracy, F1 score, etc. Since this type of study on such huge numbers of spike sequences has not been done before (to the best of our knowledge), we believe that it will open new doors for researchers to use this data and perform different tasks to unfold new information that was not available before. We also use information gain (IG) to compute the importance of each amino acid in the spike sequence. The amino acids with higher IG values tend to be the same as many reported by the USA based Centers for Disease Control and Prevention (CDC) for different variants.

In many graphs such as social networks, nodes have associated attributes representing their behavior. Predicting node attributes in such graphs is an important task with applications in many domains like recommendation systems, privacy preservation, and targeted advertisement. Attribute values can be predicted by treating each node as a data point described by attributes and employing classification/regression algorithms. However, in social networks, there is complex interdependence between node attributes and pairwise interaction. For instance, attributes of nodes are influenced by their neighbors (social influence), and neighborhoods (friendships) between nodes are established based on pairwise (dis)similarity between their attributes (social selection). In this article, we establish that information in network topology is extremely useful in determining node attributes. In particular, we use self- and cross-proclivity measures (quantitative measures of how much a node attribute depends on the same and other attributes of its neighbors) to predict node attributes. We propose a feature map to represent a node with respect to a specific attribute a , using all attributes of its h -hop neighbors. Different classifiers are then learned on these feature vectors to predict the value of attribute a . We perform extensive experimentation on 10 real-world datasets and show that the proposed method significantly outperforms known approaches in terms of prediction accuracy.