I have a data set in graph format representing semantic connection between terms. The data set is divided into clusters, each with several labels (not unique, or mutually exclusive, no set number of labels per class). The data set is about 100k items in size, with approx 10k labels and 1k clusters. I need to classify new nodes into clusters and/or provide them with labels based on their links structure only. What tools and algorithms are best suited for my needs? I am using R for the rest of the work - are there any pre written libraries that can help with the task?
As far as I'm concerned, since the final output of such method is a k-means operation, which doesn't allow for multilabel assignments, spectral clustering is not suitable for multilabel clustering.
When there are multiple labels for each data point, I believe topic model algorithms are more suitable  . They represent data points as a mixture of topics (categories). For example: a text comprising words such as 'house', 'building', 'tree' and 'car' will have a high score in a 'buildings' topic and smaller scores in a 'nature' and 'vehicle' topics.
You could use a graph diffusion/heat kernel to score the new nodes in terms of existing clusters/labels and assign the top scoring label/cluster.
You could use affinity propagation to assign the new nodes to existing clusters and then label them with the labels of the top scoring cluster. I would run some cross-validation to select the best method or hyperparameter (such as the beta of graph diffusion, or cut-off for assigning a number of clusters).