OBJECTIVE: This paper presents the results from a competition challenging participants to develop entity linking models using a subset of annotated MIMIC-IV-Note data and the SNOMED CT Terminology. MATERIALS AND METHODS: As a basis for this work, a large set of 74 808 annotations was curated across 272 discharge notes spanning 6624 unique clinical concepts. Submissions were evaluated using the mean Intersection-over-Union metric, evaluated at the character level with the 3 best performing solutions awarded a cash prize. RESULTS: The winning solutions employed contrasting approaches: a dictionary-based method, an encoder-based method, and a decoder-based method. DISCUSSION: Our analysis reveals that concept frequency in training data significantly impacts model performance, with rare concepts proving particularly challenging. High concept entropy and annotation ambiguity were also associated with decreased performance. CONCLUSION: Findings from this work suggest that future projects should focus on improving entity linking for rare concepts and developing methods to better leverage contextual information when training examples are scarce.

One of the main tasks in argument mining is the retrieval of argumentative content pertaining to a given topic. Most previous work addressed this task by retrieving a relatively small number of relevant documents as the initial source for such content. This line of research yielded moderate success, which is of limited use in a real-world system. Furthermore, for such a system to yield a comprehensive set of relevant arguments, over a wide range of topics, it requires leveraging a large and diverse corpus in an appropriate manner. Here we present a first end-to-end high-precision, corpus-wide argument mining system. This is made possible by combining sentence-level queries over an appropriate indexing of a very large corpus of newspaper articles, with an iterative annotation scheme. This scheme addresses the inherent label bias in the data and pinpoints the regions of the sample space whose manual labeling is required to obtain high-precision among top-ranked candidates.

An educated and informed consumption of media content has become a challenge in modern times.With the shift from traditional news outlets to social media and similar venues, a major concern is that readers are becoming encapsulated in "echo chambers" and may fall prey to fake news and disinformation, lacking easy access to dissenting views.We suggest a novel task aiming to alleviate some of these concerns -that of detecting articles that most effectively counter the arguments -and not just the stance -made in a given text.We study this problem in the context of debate speeches.Given such a speech, we aim to identify, from among a set of speeches on the same topic and with an opposing stance, the ones that directly counter it.We provide a large dataset of 3685 such speeches (in English), annotated for this relation, which hopefully would be of general interest to the NLP community.We explore several algorithms addressing this task, and while some are successful, all fall short of expert human performance, suggesting room for further research.All data collected during this work is freely available for research 1 .

Roy Bar-Haim, Dalia Krieger, Orith Toledo-Ronen, Lilach Edelstein, Yonatan Bilu, Alon Halfon, Yoav Katz, Amir Menczel, Ranit Aharonov, Noam Slonim. Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics. 2019.

Yonatan Bilu, Ariel Gera, Daniel Hershcovich, Benjamin Sznajder, Dan Lahav, Guy Moshkowich, Anael Malet, Assaf Gavron, Noam Slonim. Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics. 2019.

Matan Orbach, Yonatan Bilu, Ariel Gera, Yoav Kantor, Lena Dankin, Tamar Lavee, Lili Kotlerman, Shachar Mirkin, Michal Jacovi, Ranit Aharonov, Noam Slonim. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.

Shachar Mirkin, Guy Moshkowich, Matan Orbach, Lili Kotlerman, Yoav Kantor, Tamar Lavee, Michal Jacovi, Yonatan Bilu, Ranit Aharonov, Noam Slonim. Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing. 2018.

Henning Wachsmuth, Nona Naderi, Yufang Hou, Yonatan Bilu, Vinodkumar Prabhakaran, Tim Alberdingk Thijm, Graeme Hirst, Benno Stein. Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers. 2017.

For many optimization problems, the instances of practical interest often occupy just a tiny part of the algorithm's space of instances. Following (Y. Bilu and N. Linial, 2010), we apply this perspective to MAXCUT, viewed as a clustering problem. Using a variety of techniques, we investigate practically interesting instances of this problem. Specifically, we show how to solve in polynomial time distinguished, metric, expanding and dense instances of MAXCUT under mild stability assumptions. In particular, (1 + epsilon)-stability (which is optimal) suffices for metric and dense MAXCUT. We also show how to solve in polynomial time Omega(sqrt(n))-stable instances of MAXCUT, substantially improving the best previously known result.

Variation in gene expression levels on a genomic scale has been detected among different strains, among closely related species, and within populations of genetically identical cells. What are the driving forces that lead to expression divergence in some genes and conserved expression in others? Here we employ flux balance analysis to address this question for metabolic genes. We consider the genome-scale metabolic model of Saccharomyces cerevisiae, and its entire space of optimal and near-optimal flux distributions. We show that this space reveals underlying evolutionary constraints on expression regulation, as well as on the conservation of the underlying gene sequences. Genes that have a high range of optimal flux levels tend to display divergent expression levels among different yeast strains and species. This suggests that gene regulation has diverged in those parts of the metabolic network that are less constrained. In addition, we show that genes that are active in a large fraction of the space of optimal solutions tend to have conserved sequences. This supports the possibility that there is less selective pressure to maintain genes that are relevant for only a small number of metabolic states.

Multiple Sequence Alignment (MSA) is one of the most fundamental problems in computational molecular biology. The running time of the best known scheme for finding an optimal alignment, based on dynamic programming, increases exponentially with the number of input sequences. Hence, many heuristics were suggested for the problem. We consider a version of the MSA problem where the goal is to find an optimal alignment in which matches are restricted to positions in predefined matching segments. We present several techniques for making the dynamic programming algorithm more efficient, while still finding an optimal solution under these restrictions. We prove that it suffices to find an optimal alignment of the predefined sequence segments, rather than single letters, thereby reducing the input size and thus improving the running time. We also identify "shortcuts" that expedite the dynamic programming scheme. Empirical study shows that, taken together, these observations lead to an improved running time over the basic dynamic programming algorithm by 4 to 12 orders of magnitude, while still obtaining an optimal solution. Under the additional assumption that matches between segments are transitive, we further improve the running time for finding the optimal solution by restricting the search space of the dynamic programming algorithm.

We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on a series of 2-lift operations. Let G be a graph on n vertices. A 2-lift of G is a graph H on 2n vertices, with a covering map /spl pi/ : H /spl rarr/ G. It is not hard to see that all eigenvalues of G are also eigenvalues of H. In addition, H has n "new" eigenvalues. We conjecture that every d-regular graph has a 2-lift such that all new eigenvalues are in the range [-2/spl radic/d-1, /spl radic/d-1] (If true, this is tight , e.g. by the Alon-Boppana bound). Here we show that every graph of maximal degree d has a 2-lift such that all "new" eigenvalues are in the range [-c/spl radic/d log/sup 3/d, c/spl radic/d log/sup 3/ d] for some constant c. This leads to a polynomial time algorithm for constructing arbitrarily large d-regular graphs, with second eigenvalue O(/spl radic/d log/sup 3/ d). The proof uses the following lemma (Lemma 3.6): Let A be a real symmetric matrix with zeros on the diagonal. Let d be such that the l/sub 1/ norm of each row in A is at most d. Suppose that (|xAy|)/(/spl par/x/spl par//spl par/y/spl par/) /spl les/ /spl alpha/ for every x,y /spl isin/ {0, l}/sup n/ with (x,y)= 0. Then the spectral radius of A is O(/spl alpha/(log(d//spl alpha/) + 1)). An interesting consequence of this lemma is a converse to the expander mixing lemma.

Perhaps the most direct way to infer functional linkage of proteins is through structural similarity. However, structure determination lags behind DNA sequencing. Here we show that sequence similarity based on nucleotide sequences alone between ORFs in yeast is indicative of the corresponding genes being of the same functional group, having a similar gene expression pattern or of being involved in a protein-protein interaction. In particular, we compare the nucleotide sequences corresponding to the 6280 yeast ORFs using BLAST, and then cluster them together using a simple neighbor-joining algorithm. This, in effect, gives us hierarchical clustering of 53 levels, where higher levels have bigger clusters. We compare the clustering to large databases that are not based a-priori on sequence information to get a notion of how well our clustering is correlated with this data. For functional annotation we use the SGD database that gives one of 540 annotations for about half the yeast genes. For all pairs that appear within a cluster, we test the hypothesis that almost all genes within the same cluster have the same function. We get very high percentage rates of correct annotation at the lower levels of the hierarchy, which decreases gradually at higher ones. From the results of the large scale gene expression experiments we generate a list of pairs of genes, whose expression is highly correlated (≱0.9). We then go over this list of pairs, and count how many of them are contained within a cluster as opposed to the expected number by a random model. We estimate the significance of our results using simulation, and get for all levels p-value≰≰0.001. The third type of data obtained from the protein-protein interaction database that is given as a list of airs of proteins involved in interaction.