General description of the problem

I have a graph where some vertices are labeled with a type with 3 or 4 possible values. For the other vertices, the type is unknown. My goal is to use the graph to predict the type for vertices that are unlabeled.

Possible framework

I suspect this fits into the general framework of label propagation problems, based on my reading of the literature (e.g., see this paper and this paper)

Another method that is mentioned often is Frequent Subgraph Mining, which includes algorithms like SUBDUE,SLEUTH, and gSpan.

Found in R

The only label propagation implementation I managed to find in R is label.propagation.community() from the igraph library. However, as the name suggests, it is mostly used to find communities, not for classifying unlabeled vertices.

There also seems to be several references to a subgraphMining library (here for example), but it looks like it is missing from CRAN.


Do you know of a library or framework for the task described?


1 Answer 1


This is an old post, but there is a subgraph package and accompanying book/documentation for doing this in R: https://www.csc.ncsu.edu/faculty/samatova/practical-graph-mining-with-R/PracticalGraphMiningWithR.html

Although I personally don't get the connection between subgraph mining and label propagation in this case. SVD++ might be closer to what you're looking for (supported by GraphX of Spark, which I think also supports label propagation). http://spark.apache.org/graphx/


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.