Relationship profiling over social networks: Reverse smoothness from similarity to closeness

On social networks, while nodes bear rich attributes, we often lack the ‘semantics’ of why each link is formed–and thus we are missing the ‘road signs’ to navigate and organize the complex social universe. How to identify relationship semantics without labeled links? Founded on the prevalent homophily principle, we propose the novel problem of Attribute-based Relationship Profiling (ARP), to profile the closeness w.r.t. the underlying relationships (e.g., schoolmate) between users based on their similarity in the corresponding attributes (e.g., schools) and, as output, learn a set of social affinity graphs, where each link is weighted by its probabilities of carrying the relationships. As requirements, ARP should be systematic and complete to profile every link for every relationship– our challenges lie in effectively modeling homophily. We propose a novel reverse smoothness principle by observing that the similarity-closeness duality of homophily is consistent with the well-known smoothness assumption in graph-based semi-supervised learning– only the direction of inference is reversed. To realize smoothness over noisy social graphs, we further propose a novel holistic closeness modeling approach to capture ‘high-order’ smoothness by extending closeness from edges to paths. Extensive experiments on three real-world datasets demonstrate the efficacy of our proposed algorithm for ARP.