Search

While coreference resolution is traditionally used as a component in individual document understanding, in this work we take a more global view and explore what can we learn about a domain from the set of all document-level coreference relations that are present in a large corpus. We derive coreference chains from a corpus of 30 million biomedical abstracts and construct a graph based on the string phrases within these chains, establishing connections between phrases if they co-occur within the same coreference chain. We then use the graph structure and the betweeness centrality measure to distinguish between edges denoting hierarchy, identity and noise, assign directionality to edges denoting hierarchy, and split nodes (strings) that correspond to multiple distinct concepts. The result is a rich, data-driven ontology over concepts in the biomedical domain, parts of which overlaps significantly with human-authored ontologies. We release the coreference chains and resulting ontology under a creative-commons license, along with the code.

The alignment of two similar graphs from different domains is a well-studied problem. In many practical usages, there is no reliable information or labels over the vertices or edges, leaving structural similarity as the only information available to match such a graph. In such cases, one often assumes a small amount of already aligned vertices -- called a seed. Current state-of-the-art scalable seeded alignment algorithms are based on percolation. Namely, aligned vertices are used to align their neighbors and gradually percolate in parallel in both graphs. However, percolation-based graph alignment algorithms are still limited in scale-free degree distributions. We here propose `IRMA' -- Iterative Repair for graph MAtching to show that the accuracy of percolation-based algorithms can be improved in real-world graphs with a limited additional computational cost, and with lower run time when used in a parallel version. IRMA starts by creating a primary alignment using an existing percolation algorithm, then it iteratively repairs the mistakes in the previous alignment steps. We prove that IRMA improves on single-iteration algorithms. We then numerically show that it is significantly better than all state-of-the-art seeded graph alignment algorithms on the graphs that they tested. In scale-free networks, many vertices have a very low degree. Such vertices have a high probability of erroneous alignments. We show that combining iterations with high recall but low precision in the alignment leads in the long run to higher recall and precision for the entire alignment.

Recently, haplo-identical transplantation with multiple HLA mismatches has become a viable option for system cell transplants. Haplotype sharing detection requires imputation of donor and recipient. We show that even in high-resolution typing when all alleles are known, there is a 15% error rate in haplotype phasing, and even more in low resolution typings. Similarly, in related donors, parents haplotypes should be imputed to determine what haplotype each child inherited. We propose GRAMM (GRaph bAsed FaMilly iMputation) to phase alleles in family pedigree HLA typing data, and in mother-cord blood unit pairs. We show that GRAMM has practically no phasing errors when pedigree data are available. We apply GRAMM to simulations with different typing resolutions as well as paired cord-mother typings, and show very high phasing accuracy, and improved alleles imputation accuracy. We use GRAMM to detect recombination events and show that the rate of falsely detected recombination events (False Positive Rate) in simulations is very low. We then apply recombination detection to typed families to estimate the recombination rate in Israeli and Australian population datasets. The estimated recombination rate has an upper bound of 10-20% per family (1-4% per individual). GRAMM is available at: https://gramm.math.biu.ac.il/., Comment: 23 pages (20 + 3 of Supp. Mat.), 9 figures (6 + 3 of Supp. Mat.) Submitted to NAR (Nucleic Acids Research)

Estimating the frequency of sub-graphs is of importance for many tasks, including sub-graph isomorphism, kernel-based anomaly detection, and network structure analysis. While multiple algorithms were proposed for full enumeration or sampling-based estimates, these methods fail in very large graphs. Recent advances in parallelization allow for estimates of total sub-graphs counts in very large graphs. The task of counting the frequency of each sub-graph associated with each vertex also received excellent solutions for undirected graphs. However, there is currently no good solution for very large directed graphs. We here propose VDMC (Vertex specific Distributed Motif Counting) -- a fully distributed algorithm to optimally count all the 3 and 4 vertices connected directed graphs (sub-graph motifs) associated with each vertex of a graph. VDMC counts each motif only once and its efficacy is linear in the number of counted motifs. It is fully parallelized to be efficient in GPU-based computation. VDMC is based on three main elements: 1) Ordering the vertices and only counting motifs containing increasing order vertices, 2) sub-ordering motifs based on the average length of the BFS composing the motif, and 3) removing isomorphisms only once for the entire graph. We here compare VDMC to analytical estimates of the expected number of motifs and show its accuracy. VDMC is available as a highly efficient CPU and GPU code with a novel data structure for efficient graph manipulation. We show the efficacy of VDMC and real-world graphs. VDMC allows for the precise analysis of sub-graph frequency around each vertex in large graphs and opens the way for the extension of methods until now limited to graphs of thousands of edges to graphs with millions of edges and above. GIT: https://github.com/louzounlab/graph-measures

Multiple methods of finding the vertices belonging to a planted dense subgraph in a random dense $G(n, p)$ graph have been proposed, with an emphasis on planted cliques. Such methods can identify the planted subgraph in polynomial time, but are all limited to several subgraph structures. Here, we present PYGON, a graph neural network-based algorithm, which is insensitive to the structure of the planted subgraph. This is the first algorithm that uses advanced learning tools for recovering dense subgraphs. We show that PYGON can recover cliques of sizes $\Theta\left(\sqrt{n}\right)$, where $n$ is the size of the background graph, comparable with the state of the art. We also show that the same algorithm can recover multiple other planted subgraphs of size $\Theta\left(\sqrt{n}\right)$, in both directed and undirected graphs. We suggest a conjecture that no polynomial time PAC-learning algorithm can detect planted dense subgraphs with size smaller than $O\left(\sqrt{n}\right)$, even if in principle one could find dense subgraphs of logarithmic size.

Social animals, including humans, have a broad range of personality traits, which can be used to predict individual behavioral responses and decisions. Current methods to quantify individual personality traits in humans rely on self-report questionnaires, which require time and effort to collect, and rely on active cooperation. However, personality differences naturally manifest in social interactions such as online social networks. Here, we explored this option and found that the topology of an online social network can be used to characterize the personality traits of its members. We analyzed the directed social graph formed by the users of the LiveJournal (LJ) blogging platform. Individual user personality traits, inferred from their self-reported domains of interest (DOIs), were associated with their network measures. Empirical clustering of DOIs by topological similarity exposed two main self-emergent DOI groups that were in alignment with the personality meta-traits plasticity and stability. Closeness, a global topological measure of network centrality, was higher for bloggers associated with plasticity (vs. stability). A local network motif (a triad of 3 connected bloggers) also separated the personality meta-traits. Finally, topology-based classification of DOIs (without analyzing the blog content) attained > 70% accuracy (average AUC of the test-set). These results indicate that personality traits can be detected in social network topology. This has serious implications for user privacy. But, if used responsibly, network identification of personality traits could aid in early identification of health-related risks, at the population level.

A precise estimate of allele and haplotype polymorphism is of great interest in theoretical population genetics, but also has practical applications, such as bone marrow registries management. Allele polymorphism is driven mainly by point mutations, while haplotype polymorphism is also affected by recombination. Current estimates treat recombination as mutations in an infinite site model. We here show that even in the simple case of two loci in a haploid individual, for a finite population, most recombination events produce existing haplotypes, and as such are silent. Silent recombination considerably reduces the total number of haplotypes expected from the infinite site model for populations that are not much larger than one over the mutation rate. Moreover, in contrast with mutations, the number of haplotypes does not grow linearly with the population size. We hence propose a more accurate estimate of the total number of haplotypes that takes into account silent recombination. We study large-scale Human Leukocyte Antigen (HLA) haplotype frequencies from human populations to show that the current estimated recombination rate in the HLA region is underestimated., Comment: 12 pages, 7 figures

Graph Convolutional Networks (GCNs) have been extensively used to classify vertices in graphs and have been shown to outperform other vertex classification methods. GCNs have been extended to graph classification tasks (GCT). In GCT, graphs with different numbers of edges and vertices belong to different classes, and one attempts to predict the graph class. GCN based GCT have mostly used pooling and attention-based models. The accuracy of existing GCT methods is still limited. We here propose a novel solution combining GCN, methods from knowledge graphs, and a new self-regularized activation function to significantly improve the accuracy of the GCN based GCT. We present quadratic GCN (QGCN) - A GCN formalism with a quadratic layer. Such a layer produces an output with fixed dimensions, independent of the graph vertex number. We applied this method to a wide range of graph classification problems, and show that when using a self regularized activation function, QGCN outperforms the state of the art methods for all graph classification tasks tested with or without external input on each graph. The code for QGCN is available at: https://github.com/Unknown-Data/QGCN .

We present a generic epidemic model with stochastic parameters, in which the dynamics self-organize to a critical state with suppressed exponential growth. More precisely, the dynamics evolve into a quasi-steady-state, where the effective reproduction rate fluctuates close to the critical value one, as observed for different epidemics. The main assumptions underlying the model are that the rate at which each individual becomes infected changes stochastically in time with a heavy-tailed steady state. The critical regime is characterized by an extremely long duration of the epidemic. Its stability is analyzed both numerically and analytically.

Empirical studies show that epidemiological models based on an epidemic's initial spread rate often fail to predict the true scale of that epidemic. Most epidemics with a rapid early rise die out before affecting a significant fraction of the population, whereas the early pace of some pandemics is rather modest. Recent models suggest that this could be due to the heterogeneity of the target population's susceptibility. We study a computer malware ecosystem exhibiting spread mechanisms resembling those of biological systems while offering details unavailable for human epidemics. Rather than comparing models, we directly estimate reach from a new and vastly more complete data from a parallel domain, that offers superior details and insight as concerns biological outbreaks. We find a highly heterogeneous distribution of computer susceptibilities, with nearly all outbreaks initially over-affecting the tail of the distribution, then collapsing quickly once this tail is depleted. This mechanism restricts the correlation between an epidemic's initial growth rate and its total reach, thus preventing the majority of epidemics, including initially fast-growing outbreaks, from reaching a macroscopic fraction of the population. The few pervasive malwares distinguish themselves early on via the following key trait: they avoid infecting the tail, while preferentially targeting computers unaffected by typical malware.

Black-Box Optimization (BBO) methods can find optimal policies for systems that interact with complex environments with no analytical representation. As such, they are of interest in many Artificial Intelligence (AI) domains. Yet classical BBO methods fall short in high-dimensional non-convex problems. They are thus often overlooked in real-world AI tasks. Here we present a BBO method, termed Explicit Gradient Learning (EGL), that is designed to optimize high-dimensional ill-behaved functions. We derive EGL by finding weak-spots in methods that fit the objective function with a parametric Neural Network (NN) model and obtain the gradient signal by calculating the parametric gradient. Instead of fitting the function, EGL trains a NN to estimate the objective gradient directly. We prove the convergence of EGL in convex optimization and its robustness in the optimization of integrable functions. We evaluate EGL and achieve state-of-the-art results in two challenging problems: (1) the COCO test suite against an assortment of standard BBO methods; and (2) in a high-dimensional non-convex image generation task.

In times of outbreaks, an essential requirement for better monitoring is the evaluation of the number of undiagnosed infected individuals. An accurate estimate of this fraction is crucial for the assessment of the situation and the establishment of protective measures. In most current studies using epidemics models, the total number of infected is either approximated by the number of diagnosed individuals or is dependent on the model parameters and assumptions, which are often debated. We here study the relationship between the fraction of diagnosed infected out of all infected, and the fraction of infected with known contaminator out of all diagnosed infected. We show that those two are approximately the same in exponential models and across most models currently used in the study of epidemics, independently of the model parameters. As an application, we compute an estimate of the effective number of infected by the SARS-CoV-2 virus in various countries.

A key question in the current diversity crisis is how diversity has been maintained throughout evolution and how to preserve it. Modern coexistence theories suggest that a high invasion rate of rare new types is directly related to diversity. We show that adding almost any mechanism of catastrophes to a stochastic birth, death, and mutation process with limited carrying capacity induces a novel phase transition characterized by a positive invasion rate but a low diversity. In this phase, new types emerge and grow rapidly, but the resulting growth of very large types decreases diversity. This model also resolves two major drawbacks of neutral evolution models: their failure to explain balancing selection without resorting to fitness differences and the unrealistic time required for the creation of the observed large types. We test this model on a classical case of genetic polymorphism: the HLA locus., Comment: 5 pages, 4 figures

A method for estimating the Shannon differential entropy of multidimensional random variables using independent samples is described. The method is based on decomposing the distribution into a product of the marginal distributions and the joint dependency, also known as the copula. The entropy of marginals is estimated using one-dimensional methods. The entropy of the copula, which always has a compact support, is estimated recursively by splitting the data along statistically dependent dimensions. Numerical examples demonstrate that the method is accurate for distributions with compact and non-compact supports, which is imperative when the support is not known or of mixed type (in different dimensions). At high dimensions (larger than 20), our method is not only more accurate, but also significantly more efficient than existing approaches.

In colored graphs, node classes are often associated with either their neighbors class or with information not incorporated in the graph associated with each node. We here propose that node classes are also associated with topological features of the nodes. We use this association to improve Graph machine learning in general and specifically, Graph Convolutional Networks (GCN). First, we show that even in the absence of any external information on nodes, a good accuracy can be obtained on the prediction of the node class using either topological features, or using the neighbors class as an input to a GCN. This accuracy is slightly less than the one that can be obtained using content based GCN. Secondly, we show that explicitly adding the topology as an input to the GCN does not improve the accuracy when combined with external information on nodes. However, adding an additional adjacency matrix with edges between distant nodes with similar topology to the GCN does significantly improve its accuracy, leading to results better than all state of the art methods in multiple datasets., Comment: arXiv admin note: text overlap with arXiv:1904.07787

Graph convolution networks (GCN) have emerged as the leading method to classify node classes in networks, and have reached the highest accuracy in multiple node classification tasks. In the absence of available tagged samples, active learning methods have been developed to obtain the highest accuracy using the minimal number of queries to an oracle. The current best active learning methods use the sample class uncertainty as selection criteria. However, in graph based classification, the class of each node is often related to the class of its neighbors. As such, the uncertainty in the class of a node's neighbor may be a more appropriate selection criterion. We here propose two such criteria, one extending the classical uncertainty measure, and the other extending the page-rank algorithm. We show that the latter is optimal when the fraction of tagged nodes is low, and when this fraction grows to one over the average degree, the regional uncertainty performs better than all existing methods. While we have tested this methods on graphs, such methods can be extended to any classification problem, where a distance metrics can be defined between the input samples. All the code used can be accessed at : https://github.com/louzounlab/graph-al All the datasets used can be accessed at : https://github.com/louzounlab/DataSets, Comment: 9 pages, 7 figures

The main approaches for node classification in graphs are information propagation and the association of the class of the node with external information. State of the art methods merge these approaches through Graph Convolutional Networks. We here use the association of topological features of the nodes with their class to predict this class. Moreover, combining topological information with information propagation improves classification accuracy on the standard CiteSeer and Cora paper classification task. Topological features and information propagation produce results almost as good as text-based classification, without no textual or content information. We propose to represent the topology and information propagation through a GCN with the neighboring training node classification as an input and the current node classification as output. Such a formalism outperforms state of the art methods.

Sustainable financial markets play an important role in the functioning of human society. Still, the detection and prediction of risk in financial markets remain challenging and draw much attention from the scientific community. Here we develop a new approach based on combined network theory and machine learning to study the structure and operations of financial product markets. Our network links are based on the similarity of firms' products and are constructed using the Securities Exchange Commission (SEC) filings of US listed firms. We find that several features in our network can serve as good precursors of financial market risks. We then combine the network topology and machine learning methods to predict both successful and failed firms. We find that the forecasts made using our method are much better than other well-known regression techniques. The framework presented here not only facilitates the prediction of financial markets but also provides insight and demonstrate the power of combining network theory and machine learning.

Prenatal stress (PS) impacts early postnatal behavioural and cognitive development. This process of 'fetal programming' is mediated by the effects of the prenatal experience on the developing hypothalamic-pituitary-adrenal (HPA) axis and autonomic nervous system (ANS). The HPA axis is a dynamic system regulating homeostasis, especially the stress response, and is highly sensitive to adverse early life experiences. We review the evidence for the effects of PS on fetal programming of the HPA axis and the ANS. We derive a multi-scale multi-species approach to devising preclinical and clinical studies to identify early non-invasively available pre- and postnatal biomarkers of these programming effects. Such approach would identify adverse postnatal brain developmental trajectories, a prerequisite for designing therapeutic interventions. The multiple scales include the biomarkers reflecting changes in the brain epigenome, metabolome, microbiome and the ANS activity gauged via an array of advanced non-invasively obtainable properties of fetal heart rate fluctuations. The proposed framework has the potential to reveal mechanistic links between maternal stress during pregnancy and changes across these physiological scales. Such biomarkers may hence be useful as early and non-invasive predictors of neurodevelopmental trajectories influenced by the PS. We conclude that studies into PS effects must be conducted on multiple scales derived from concerted observations in multiple animal models and human cohorts performed in an interactive and iterative manner and deploying machine learning for data synthesis, identification and validation of the best non-invasive biomarkers., Comment: Focused review, 13 pages, 5 figures