This paper presents a new graph-based approach that induces synsets using synonymy dictionaries and word embeddings. First, we build a weighted graph of synonyms extracted from commonly available resources, such as Wiktionary. Second, we apply word sense induction to deal with ambiguous words. Finally, we cluster the disambiguated version of the ambiguous input graph into synsets. Our meta-clustering approach lets us use an efficient hard clustering algorithm to perform a fuzzy clustering of the graph. Despite its simplicity, our approach shows excellent results, outperforming five competitive state-of-the-art methods in terms of F-score on three gold standard datasets for English and Russian derived from large-scale manually constructed lexical resources.
(CPM) @cite_19 is a clustering algorithm for unweighted graphs that builds up clusters from @math -cliques corresponding to fully connected sub-graphs of @math nodes. While this method is only commonly used in social network analysis, we decided to add it to the comparison as synsets are essentially cliques of synonyms, which makes it natural to apply an algorithm based on clique detection.
@cite_19
2164928285
Consider an Erdos---Renyi random graph in which each edge is present independently with probability @math 1 2, except for a subset @math CN of the vertices that form a clique (a completely connected subgraph). We consider the problem of identifying the clique, given a realization of such a random graph. The algorithm of (ANALCO. SIAM, pp 67---75, 2011) provably identifies the clique @math CN in linear time, provided @math |CN|?1.261N. Spectral methods can be shown to fail on cliques smaller than @math N. In this paper we describe a nearly linear-time algorithm that succeeds with high probability for @math |CN|?(1+?)N e for any @math ?>0. This is the first algorithm that provably improves over spectral methods. We further generalize the hidden clique problem to other background graphs (the standard case corresponding to the complete graph on @math N vertices). For large-girth regular graphs of degree @math (Δ+1) we prove that so-called local algorithms succeed if @math |CN|?(1+?)N eΔ and fail if @math |CN|≤(1-?)N eΔ. We study the broadcast version of the CONGEST CLIQUE model of distributed computing. In this model, in each round, any node in a network of size @math can send the same message (i.e. broadcast a message) of limited size to every other node in the network. Nanongkai presented in [STOC'14] a randomized @math -approximation algorithm to compute all pairs shortest paths (APSP) in time @math on weighted graphs, where we use the convention that @math is essentially @math polylog @math and @math is essentially @math polylog @math . We complement this result by proving that any randomized @math -approximation of APSP and @math -approximation of the diameter of a graph takes @math time in the worst case. This demonstrates that getting a negligible improvement in the approximation factor requires significantly more time. Furthermore this bound implies that already computing a @math -approximation of all pairs shortest paths is among the hardest graph-problems in the broadcast-version of the CONGEST CLIQUE model and contrasts a recent @math -approximation for APSP that runs in time @math in the unicast version of the CONGEST CLIQUE model. On the positive side we provide a deterministic version of Nanongkai's @math -approximation algorithm for APSP. To do so we present a fast deterministic construction of small hitting sets. We also show how to replace another randomized part within Nanongkai's algorithm with a deterministic source-detection algorithm designed for the CONGEST model presented by Lenzen and Peleg at PODC'13. Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of an @math vertex graph, and need to output a clique. We show that if the input graph is drawn at random from @math (and hence is likely to have a clique of size roughly @math ), then for every @math and constant @math , there is an @math (that may depend on @math and @math ) such that no algorithm that makes @math probes in @math rounds is likely (over the choice of the random graph) to output a clique of size larger than @math . The main results of this paper are (I) a simulation algorithm which, under quite general constraints, transforms algorithms running on the Congested Clique into algorithms running in the MapReduce model, and (II) a distributed @math -coloring algorithm running on the Congested Clique which has an expected running time of (i) @math rounds, if @math ; and (ii) @math rounds otherwise. Applying the simulation theorem to the Congested-Clique @math -coloring algorithm yields an @math -round @math -coloring algorithm in the MapReduce model. Our simulation algorithm illustrates a natural correspondence between per-node bandwidth in the Congested Clique model and memory per machine in the MapReduce model. In the Congested Clique (and more generally, any network in the @math model), the major impediment to constructing fast algorithms is the @math restriction on message sizes. Similarly, in the MapReduce model, the combined restrictions on memory per machine and total system memory have a dominant effect on algorithm design. In showing a fairly general simulation algorithm, we highlight the similarities and differences between these models.