arXiv (Cornell University) · 2012 · 30 citations · 24 references
ComputingComputer ScienceAlgorithmsMachine LearningPredictive AnalyticsGraph AlgorithmsGraph LabelingGraph MiningGraph TheoryGraph-based LearningSublinear AlgorithmsAmortized Running TimeBenchmark DatasetsLabel PropagationRandom GraphsRandomized Graph AlgorithmsWeighted Graph Representations
We investigate the problem of sequentially predicting the binary labels on the nodes of an arbitrary weighted graph. We show that, under a suitable parametrization of the problem, the optimal number of prediction mistakes can be characterized (up to logarithmic factors) by the cutsize of a random spanning tree of the graph. The cutsize is induced by the unknown adversarial labeling of the graph nodes. In deriving our characterization, we obtain a simple randomized algorithm achieving in expectation the optimal mistake bound on any polynomially connected weighted graph. Our algorithm draws a random spanning tree of the original graph and then predicts the nodes of this tree in constant expected amortized time and linear space. Experiments on real-world datasets show that our method compares well to both global (Perceptron) and local (label propagation) methods, while being generally faster in practice.
24
Functional organization of the yeast proteome by systematic analysis of protein complexes
Anne‐Claude Gavin, Markus Bösche, Roland Krause et al. · Nature · 2002 · 4.8K citations · Full text
A comprehensive analysis of protein–protein interactions in Saccharomyces cerevisiae
Peter Uetz, Loïc Giot, Gerard Cagney et al. · Nature · 2000 · 4.7K citations
Global landscape of protein complexes in the yeast Saccharomyces cerevisiae
Nevan J. Krogan, Gerard Cagney, Haiyuan Yu et al. · Nature · 2006 · 3K citations