Using ghost edges for classification in sparsely labeled networks

By Brian Gallagher, Hanghang Tong, Tina Eliassi-Rad, Christos Faloutsos. 2008

169 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

In Graph Learning

Citations in the corpus

DeepWalk: online learning of social representations (2014, background): “The most relevant relational classification algorithms to our work incorporate community information by learning clusters [33], by adding edges between nearby nodes [14], by using PageRank [24], or by extending relational classification to take additional features into account [43].”
Propagation kernels: efficient graph kernels from propagated information (2014, background): “Propagation kernels iteratively approximate node kernels k ( v i , v j ) comparing a node v i in graph G ( i ) with a node v j in graph G ( j ) .”
Leveraging Label-Independent Features for Classification in Sparsely Labeled Networks: An Empirical Study (2008, result): “[17] combines aspects of both SRL and SSL, and compares favorably with both wvRN+RL and GRF.”
Local Modeling of Attributed Graphs: Algorithms and Applications (2016, background): “The most relevant relational classification algorithms to our work incorporate community information by learning clusters [103], by adding edges between nearby nodes [49], by using PageRank [81], or by extending relational classification to take additional features into account [144].”
GOTCHA! Network-Based Fraud Detection for Social Security Fraud (2017, methodology): “Random Logistic Forests, as proposed by (Gallagher et al. 2008), is an ensemble of plain vanilla logistic regressions, where each classifier is fed with ||log(N)+1|| random features, with N the total number of features.”
Discriminative Deep Random Walk for Network Classification (2016, methodology): “(Gallagher et al., 2008) propose a method that learn sparsely labeled network data by adding ghost edges between neighbor vertices, and (Lin and Cohen, 2010) by using PageRank.”
RolX: structural role extraction & mining in large graphs (2012, methodology): “The logForest is a bagged model, composed of a set of logistic regression classifiers, where each is given a subset of log(f) + 1 of the f total features [13].”
Link prediction based on local random walk (2010, methodology): “In addition, the link prediction algorithms can be applied to solve the classification problem in partially labeled networks [6], such as to distinguish the research areas of scientific publications.”
It's who you know: graph mining using recursive structural features (2011, unknown): “[11], we found that the overall performance of logForest was superior to standard logistic regression.”
Link Prediction in Complex Networks: A Survey (2010, methodology): “To address these two difficulties, a simple but effective method is to add artificial connections between every pair of labeled and unlabeled nodes according to their similarity scores [131,155], with almost the same techniques used in similarity-based link prediction.”
Semi-Supervised Classification of Network Data Using Very Few Labels (2010, methodology): “In addition to its high classification accuracy, the method is simple to implement and is based on a family of well-studied algorithms (random graph walks), and it is also highly scalable, requiring time linear in the number of edges of the graph.”