Social Networks & Graphs 1

We propose a novel approach for learning node representations in directed graphs, which maintains separate views or embedding spaces for the two distinct node roles induced by the directionality of the edges.We argue that the previous approaches either fail to encode the edge directionality or their encodings cannot be generalized across tasks.With our simple alternating random walk strategy, we generate role specific vertex neighborhoods and train node embeddings in their corresponding source/target roles while fully exploiting the semantics of directed graphs. We also unearth the limitations of evaluations on directed graphs in previous works and propose a clear strategy for evaluating link prediction and graph reconstruction in directed graphs. We conduct extensive experiments to showcase our effectiveness on several real-world datasets on link prediction, node classification and graph reconstruction tasks. We show that the embeddings from our approach are indeed robust, generalizable and well performing across multiple kinds of tasks and graphs. We show that we consistently outperform all baselines for node classification task. In addition to providing a theoretical interpretation of our method we also show that we are considerably more robust than the other directed graph approaches.

Link prediction requires predicting which new links are likely to appear in a graph.In this paper, we present an approach for link prediction that relies on higher-order analysis of the graph topology, well beyond the typical approach which relies on common neighbors.We treat the link prediction problem as a supervised classification problem,and we propose a set of features that depend on the patterns or motifs that a pair of nodes occurs in.By using motifs of sizes 3, 4, and 5, our approach captures a high level of detail about the graph topology. In addition,we propose two optimizations to construct the classification dataset from the graph.First, we propose adding negative examples to the graph as an alternative to the common approach of removing positive ones.Second, we show that it is important to control for the shortest-path distance when sampling pairs of nodes to form negative examples, since the difficulty of prediction varies with the distance.We experimentally demonstrate that using our proposed motif features in off-the-shelf classifiers results in up to 10 percentage points increase in accuracy over prior topology-based and feature-learning methods.

Social recommendation systems typically combine extra information like a social network with the user-item interaction network in order to alleviate data sparsity issues. This also helps in making more accurate and personalized recommendations. However, most of the existing systems work under the assumption that all socially connected users have equal influence on each other in a social network, which is not true in practice. Further, estimating the quantum of influence that exists among entities in a user-item interaction network is essential when only implicit ratings are available. This has been ignored even in many recent state-of-the-art models such as SAMN (Social Attentional Memory Network) and DeepSoR (Deep neural network model on Social Relations). Many a time, capturing a complex relationship between the entities (users/items) is essential to boost the performance of a recommendation system. We address these limitations by proposing a novel neural network model, SoRecGAT, which employs multi-head and multi-layer graph attention mechanism. The attention mechanism helps the model learn the influence of entities on each other more accurately. The proposed model also takes care of heterogeneity among the entities seamlessly. SoRecGAT is a general approach and we also validate its suitability when information in the form of a network of co-purchased items is available. Empirical results on eight real-world datasets demonstrate that the proposed model outperforms state-of-the-art models.

Signed networks contain both positive and negative kinds of interactions like friendship and enmity. The task of node classification in non-signed graphs has proven to be beneficial in many real world applications, yet extensions to signed networks remain largely unexplored. In this paper we introduce the first analysis of node classification in signed social networks via diffuse interface methods based on the Ginzburg-Landau functional together with different extensions of the graph Laplacian to signed networks. We show that blending the information from both positive and negative interactions leads to performance improvement in real signed social networks, consistently outperforming the current state of the art.

A triangle is an important building block of social networks, so the study of triangleformation in a network is critical for better understanding of the dynamics of suchnetworks. Existing works in this area mainly focus on triangle counting, or generating synthetic networks by matching the prevalence of trianglesin real-life networks. While these efforts increase our understanding of triangle's role in a network, they have limited practical utility. In this work we undertake aninteresting problem relating to triangle formation in a network, which is, to predict the time by which the third link of a triangle appears in a network. Since the thirdlink completes a triangle, we name this task as Triangle CompletionTime Prediction (TCTP). Solution to TCTP problem is valuable forreal-life link recommendation in social/e-commerce networks, also it provides vital information for dynamic network analysis and community generation study.An efficient and robust framework (GraNiTE) is proposed for solving the TCTP problem.GraNiTE uses neural networks based approach for learning a representation vector of a trianglecompleting edge, which is a concatenation of two representation vectors: first one is learnt from graphlet based local topology around that edge and the second one islearnt from time-preserving embedding of the constituting vertices of that edge. A comparison of the proposed solution with several baselinemethods shows that the mean absolute error (MAE) of the proposed method is at least one-forth of that of the best baseline method.