Spectral Clustering with Side Information

In the graph clustering problem with a planted solution, the input is a graph on 𝑛 vertices partitioned into 𝑘 clusters, and the task is to infer the clusters from graph structure. A standard assumption is that clusters induce well-connected subgraphs (i.e. Ω⁡(1)-expanders), and connections between clusters are sparse (i.e. clusters form 𝜖-sparse cuts). Such a graph defines the clustering uniquely up to ≈𝜖 misclassification rate, and efficient algorithms for achieving this rate are known. While this vanilla version of graph clustering is extremely well studied, in the practice of graph analysis vertices of the graph are typically equipped with labels, or features, that provide additional information on cluster ids of the vertices. For example, each vertex could be equipped with a cluster label that is corrupted independently with probability 𝛿. Using either of the two sources of information separately leads to misclassification rate min⁡{𝜖,𝛿}, but can one combine the two to achieve misclassification rate ≈𝜖⁢𝛿? In this paper, we give an affirmative answer to this question, and furthermore show that such a misclassification rate can be achieved in sublinear time in the number of vertices 𝑛. Our key algorithmic insight is a new observation on “spectrally ambiguous” vertices in a well-clusterable graph. While our sublinear-time classifier achieves the nearly optimal ≈˜𝑂⁡(𝜖⁢𝛿) misclassification rate, the approximate clusters that it outputs do not necessarily induce expanders in the graph 𝐺. In our second result, we give a polynomial-time algorithm for reweighting edges of the input graph from the original (𝑘,𝜖,Ω⁡(1)-clusterable instance to a (𝑘,˜𝑂⁡(𝜖⁢𝛿),Ω⁡(1))-clusterable instance (for constant 𝑘), improving sparsity of cuts nearly optimally and preserving expansion properties of the communities – an algorithm for refining community structure of the input graph.