DeepWalk
Published 22 August 2014Open access
Bryan Perozzi, Rami Al-Rfou, Steven Skiena
Citations8,526
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
DeepWalk is an online learning algorithm which builds useful incremental results, and is trivially parallelizable, which make it suitable for a broad class of real world applications such as network classification, and anomaly detection.
Abstract
We present DeepWalk, a novel approach for learning latent representations of vertices in a network. These latent representations encode social relations in a continuous vector space, which is easily exploited by statistical models. DeepWalk generalizes recent advancements in language modeling and unsupervised feature learning (or deep learning) from sequences of words to graphs.
Keywords
Computer Science
Communications of the ACMImageNet classification with deep convolutional neural networks
75,709 Citations2017Alex Krizhevsky, Ilya Sutskever +1 more
A large, deep convolutional neural network was trained to classify the 1.2 million high-resolution images in the ImageNet LSVRC-2010 contest into the 1000 different classes and employed a recently developed regularization method called "dropout" that proved to be very effective.
arXiv (Cornell University)Distributed Representations of Words and Phrases and their Compositionality
18,086 Citations2013Tomáš Mikolov, Ilya Sutskever +3 more
This paper presents a simple method for finding phrases in text, and shows that learning good vector representations for millions of phrases is possible and describes a simple alternative to the hierarchical softmax called negative sampling.
arXiv (Cornell University)Efficient Estimation of Word Representations in Vector Space
18,050 Citations2013Tomáš Mikolov, Kai Chen +2 more
Two novel model architectures for computing continuous vector representations of words from very large data sets are proposed and it is shown that these vectors provide state-of-the-art performance on the authors' test set for measuring syntactic and semantic word similarities.
IEEE Transactions on Pattern Analysis and Machine IntelligenceStochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
17,980 Citations1984Stuart Geman, Donald Geman
The analogy between images and statistical mechanics systems is made and the analogous operation under the posterior distribution yields the maximum a posteriori (MAP) estimate of the image given the degraded observations, creating a highly parallel ``relaxation'' algorithm for MAP estimation.
IEEE Transactions on Pattern Analysis and Machine IntelligenceRepresentation Learning: A Review and New Perspectives
13,002 Citations2013Yoshua Bengio, Aaron Courville +1 more
Recent work in the area of unsupervised feature learning and deep learning is reviewed, covering advances in probabilistic models, autoencoders, manifold learning, and deep networks.
Proceedings of the National Academy of SciencesModularity and community structure in networks
12,281 Citations2006M. E. J. Newman
It is shown that the modularity of a network can be expressed in terms of the eigenvectors of a characteristic matrix for the network, which is called modularity matrix, and that this expression leads to a spectral algorithm for community detection that returns results of demonstrably higher quality than competing methods in shorter running times.
ACM Computing SurveysAnomaly detection
11,146 Citations2009Varun Chandola, Arindam Banerjee +1 more
This survey tries to provide a structured and comprehensive overview of the research on anomaly detection by grouping existing techniques into different categories based on the underlying approach adopted by each technique.
A unified architecture for natural language processing
5,204 Citations2008Ronan Collobert, Jason Weston
This work describes a single convolutional neural network architecture that, given a sentence, outputs a host of language processing predictions: part-of-speech tags, chunks, named entity tags, semantic roles, semantically similar words and the likelihood that the sentence makes sense using a language model.
Journal of Anthropological ResearchAn Information Flow Model for Conflict and Fission in Small Groups
4,661 Citations1977Wayne Zachary
AI MagazineCollective Classification in Network Data
3,287 Citations2008Prithviraj Sen, Galileo Namata +4 more
This article introduces four of the most widely used inference algorithms for classifying networked data and empirically compare them on both synthetic and real-world data.
IEEE Transactions on Audio Speech and Language ProcessingContext-Dependent Pre-Trained Deep Neural Networks for Large-Vocabulary Speech Recognition
3,052 Citations2011George E. Dahl, Dong Yu +2 more
A pre-trained deep neural network hidden Markov model (DNN-HMM) hybrid architecture that trains the DNN to produce a distribution over senones (tied triphone states) as its output that can significantly outperform the conventional context-dependent Gaussian mixture model (GMM)-HMMs.
Journal of Machine Learning ResearchA neural probabilistic language model
2,663 Citations2003BengioYoshua, DucharmeRéjean +2 more
This work reports on experiments using neural networks for the probability function, showing on two text corpora that the proposed approach very significantly improves on a state-of-the-art trigram model.
IEEE Transactions on Knowledge and Data EngineeringRandom-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation
1,261 Citations2007François Fouss, Alain Pirotte +2 more
The model, which nicely fits into the so-called "statistical relational learning" framework, could also be used to compute document or word similarities, and could be applied to machine-learning and pattern-recognition tasks involving a relational database.
Neural Information Processing SystemsHogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
1,101 Citations2011Benjamin Recht, Christopher Ré +2 more
This work aims to show using novel theoretical analysis, algorithms, and implementation that SGD can be implemented without any locking, and presents an update scheme called HOGWILD! which allows processors access to shared memory with the possibility of overwriting each other's work.
Local Graph Partitioning using PageRank Vectors
967 Citations2006Reid Andersen, Fan Chung +1 more
An improved algorithm for computing approximate PageRank vectors, which allows us to find a cut with conductance at most oslash and approximately optimal balance in time O(m log4 m/oslash) in time proportional to its size.
IEEE Transactions on Pattern Analysis and Machine IntelligenceOn the Foundations of Relaxation Labeling Processes
891 Citations1983Robert A. Hummel, Steven W. Zucker
It is shown that the problem of finding consistent labelings is equivalent to solving a variational inequality, and a procedure nearly identical to the relaxation operator derived under restricted circum-stances serves in the more general setting.
A Scalable Hierarchical Distributed Language Model
852 Citations2008Andriy Mnih, Geoffrey E. Hinton
A fast hierarchical language model along with a simple feature-based algorithm for automatic construction of word trees from the data are introduced and it is shown that the resulting models can outperform non-hierarchical neural models as well as the best n-gram models.
International Conference on Artificial Intelligence and StatisticsHierarchical Probabilistic Neural Network Language Model.
840 Citations2005Fréderic Morin, Yoshua Bengio
A point-of-care POC analyzer that can rapidly measure both medications used for treatment and illicit drugs in patient saliva and shows evidence of accuracy in measuring treatment medications and relapse to drug use is shown.
Learning distributed representations of concepts.
821 Citations1989Geoffrey E. Hinton
Relational learning via latent social dimensions
791 Citations2009Lei Tang, Huan Liu
This work proposes to extract latent social dimensions based on network information, and then utilize them as features for discriminative learning, and outperforms representative relational learning methods based on collective inference, especially when few labeled data are available.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
784 Citations2004Daniel A. Spielman, Shang‐Hua Teng
This paper presents algorithms for solving symmetric, diagonally-dominant linear systems to accuracy ε in time linear in their number of non-zeros and log (κf (A) ε), where ε is the condition number of the matrix defining the linear system.
Diffusion Kernels on Graphs and Other Discrete Input Spaces
732 Citations2002Risi Kondor, John Lafferty
This paper proposes a general method of constructing natural families of kernels over discrete structures, based on the matrix exponentiation idea, and focuses on generating kernels on graphs, for which a special class of exponential kernels called diffusion kernels are proposed.
Journal of Machine Learning ResearchClassification in Networked Data: A Toolkit and a Univariate Case Study
447 Citations2007Sofus A. Macskassy, Foster Provost
The results demonstrate that very simple network-classification models perform quite well---well enough that they should be used regularly as baseline classifiers for studies of learning with networked data.
Data Mining and Knowledge DiscoveryLeveraging social media networks for classification
367 Citations2011Lei Tang, Huan Liu
The proposed framework, SocioDim, first extracts social dimensions based on the network structure to accurately capture prominent interaction patterns between actors, then learns a discriminative classifier to select relevant social dimensions.
Journal of Machine Learning ResearchLIBLINEAR: A Library for Large Linear Classification
329 Citations2008FanRong-En, ChangKai-Wei +3 more
LIBLINEAR is an open source library for large-scale linear classification that supports logistic regression and linear support vector machines and provides easy-to-use command-line tools and library calls for users and developers.
arXiv (Cornell University)Polyglot: Distributed Word Representations for Multilingual NLP
307 Citations2013Rami Al‐Rfou, Bryan Perozzi +1 more
This work quantitatively demonstrates the utility of word embeddings by using them as the sole features for training a part of speech tagger for a subset of these languages and investigates the semantic features captured through the proximity of word groupings.
A Simple Relational Classifier
246 Citations2003Sofus A. Macskassy, Foster Provost
It is argued that a simple relational predictive model the predicts only based on class labels of related neighbors, using no learning and no inherent attributes should be used as a baseline to assess the performance of relational learners.
Scalable learning of collective behavior based on sparse social dimensions
242 Citations2009Lei Tang, Huan Liu
This work proposes an edge-centric clustering scheme to extract sparse social dimensions that can efficiently handle networks of millions of actors while demonstrating comparable prediction performance as other non-scalable methods.
It's who you know
222 Citations2011Keith Henderson, Brian Gallagher +5 more
ReFeX (Recursive Feature eXtraction), a novel algorithm, that recursively combines local features with neighborhood features; and outputs regional features -- capturing "behavioral" information in large graphs, is proposed.
Using ghost edges for classification in sparsely labeled networks
146 Citations2008Brian Gallagher, Hanghang Tong +2 more
This paper proposes a novel approach to within-network classification that combines aspects of statistical relational learning and semi-supervised learning to improve classification performance in sparse networks and demonstrates that this approach performs well across a range of conditions where existing approaches fail.
Fast Random Walk Graph Kernel
124 Citations2012U Kang, Hanghang Tong +1 more
Ark is a set of fast algorithms for random walk graph kernel computation based on the observation that real graphs have much lower intrinsic ranks, compared with the orders of the graphs, which exploits the low rank structure to quickly compute randomWalk graph kernels in O(n) or O(m) time.
Semi-Supervised Classification of Network Data Using Very Few Labels
93 Citations2010Frank Lin, William W. Cohen
Another simple and intuitive semi-supervised learning method based on random graph walk that outperforms wvRN by a large margin on several benchmark datasets when very few labels are available and dramatically reduces the amount of labeled data required to achieve the same classification accuracy.
Multi-label relational neighbor classification using social context features
64 Citations2013Xi Wang, Gita Sukthankar
This paper proposes a multi-label iterative relational neighbor classifier that employs social context features (SCRN), which incorporates a class propagation probability distribution obtained from instances' social features, which are in turn extracted from the network topology.
Journal of Machine Learning ResearchWhy Does Unsupervised Pre-training Help Deep Learning?
61 Citations2010ErhanDumitru, BengioYoshua +4 more
The results suggest that unsupervised pre-training guides the learning towards basins of attraction of minima that support better generalization from the training data set; the evidence from these results supports a regularization explanation for the effect of pre- training.
Machine LearningA bias/variance decomposition for models using collective inference
21 Citations2008Jennifer Neville, David Jensen
This work evaluates the performance of three relational models on both synthetic and real-world datasets and shows that (1) inference can be a significant source of error, and (2) the models exhibit different types of errors as data characteristics are varied.