Zekarias Tilahun

In recommender systems (RSs), predicting the next item that a user interacts with is critical for user retention. While the last decade has seen an explosion of RSs aimed at identifying relevant items that match user preferences, there is still a range of aspects that could be considered to further improve their performance. For example, often RSs are centered around the user, who is modeled using her recent sequence of activities. Recent studies, however, have shown the effectiveness of modeling the mutual interactions between users and items using separate user and item embeddings. Building on the success of these studies, we propose a novel method called DeePRed that addresses some of their limitations. In particular, we avoid recursive and costly interactions between consecutive short-term embeddings by using long-term (stationary) embeddings as a proxy. This enable us to train DeePRed using simple mini-batches without the overhead of specialized mini-batches proposed in previous studies. Moreover, DeePRed’s effectiveness comes from the aforementioned design and a multi-way attention mechanism that inspects user-item compatibility. Experiments show that DeePRed outperforms the best state-of-the-art approach by at least 14% of Mean Reciprocal Rank (MRR) on next item prediction task, while gaining more than an order of magnitude speedup over the best performing baselines. Although this study is mainly concerned with temporal interaction networks, we also show the power and flexibility of DeePRed by adapting it to the case of static interaction networks, substituting the short- and long-term aspects with local and global ones.

Real world data is mostly unlabeled or only few instances are labeled. Manually labeling data is a very expensive and daunting task. This calls for unsupervised learning techniques that are powerful enough to achieve comparable results as semi-supervised/supervised techniques. Contrastive self-supervised learning has emerged as a powerful direction, in some cases outperforming supervised techniques. In this study, we propose, SelfGNN, a novel contrastive self-supervised graph neural network (GNN) without relying on explicit contrastive terms. We leverage Batch Normalization, which introduces implicit contrastive terms, without sacrificing performance. Furthermore, as data augmentation is key in contrastive learning, we introduce four feature augmentation (FA) techniques for graphs. Though graph topological augmentation (TA) is commonly used, our empirical findings show that FA perform as good as TA. Moreover, FA incurs no computational overhead, unlike TA, which often has O(N^3) time complexity, N-number of nodes. Our empirical evaluation on seven publicly available real-world data shows that, SelfGNN is powerful and leads to a performance comparable with SOTA supervised GNNs and always better than SOTA semi-supervised and unsupervised GNNs.

Graph representation learning (GRL) is a powerful technique for learning low-dimensional vector representation of high-dimensional and often sparse graphs. Most studies explore the structure and metadata associated with the graph using random walks and employ an unsupervised or semi-supervised learning schemes. Learning in these methods is context-free, resulting in only a single representation per node. Recently studies have argued on the adequacy of a single representation and proposed context-sensitive approaches, which are capable of extracting multiple node representations for different contexts. This proved to be highly effective in applications such as link prediction and ranking. However, most of these methods rely on additional textual features that require complex and expensive RNNs or CNNs to capture high-level features or rely on a community detection algorithm to identify multiple contexts of a node. In this study we show that in-order to extract high-quality context-sensitive node representations it is not needed to rely on supplementary node features, nor to employ computationally heavy and complex models. We propose GOAT, a context-sensitive algorithm inspired by gossip communication and a mutual attention mechanism simply over the structure of the graph. We show the efficacy of GOAT using 6 real-world datasets on link prediction and node clustering tasks and compare it against 12 popular and state-of-the-art (SOTA) baselines. GOAT consistently outperforms them and achieves up to 12% and 19% gain over the best performing methods on link prediction and clustering tasks, respectively.

Network representation learning (NRL) is a powerful technique for learning low-dimensional vector representation of high-dimensional and sparse graphs. Most studies explore the structure and metadata associated with the graph using random walks and employ an unsupervised or semi-supervised learning schemes. Learning in these methods is context-free, because only a single representation per node is learned. Recently studies have argued on the sufficiency of a single representation and proposed a context-sensitive approach that proved to be highly effective in applications such as link prediction and ranking. However, most of these methods rely on additional textual features that require RNNs or CNNs to capture high-level features or rely on a community detection algorithm to identify multiple contexts of a node. In this study, without requiring additional features nor a community detection algorithm, we propose a novel context-sensitive algorithm called GAP that learns to attend on different parts of a node's neighborhood using attentive pooling networks. We show the efficacy of GAP using three real-world datasets on link prediction and node clustering tasks and compare it against 10 popular and state-of-the-art (SOTA) baselines. GAP consistently outperforms them and achieves up to ~9% and ~20% gain over the best performing methods on link prediction and clustering tasks, respectively.

Graph embedding algorithms are used to efficiently represent (encode) a graph in a low-dimensional continuous vector space that preserves the most important properties of the graph. One aspect that is often overlooked is whether the graph is directed or not. Most studies ignore the directionality, so as to learn high-quality representations optimized for node classification. On the other hand, studies that capture directionality are usually effective on link prediction but do not perform well on other tasks. This preliminary study presents a novel text-enriched, direction-aware algorithm called DIAGRAM , based on a carefully designed multi-objective model to learn embeddings that preserve the direction of edges, textual features and graph context of nodes. As a result, our algorithm does not have to trade one property for another and jointly learns high-quality representations for multiple network analysis tasks. We empirically show that DIAGRAM significantly outperforms six state-of-the-art baselines, both direction-aware and oblivious ones,on link prediction and network reconstruction experiments using two popular datasets. It also achieves a comparable performance on node classification experiments against these baselines using the same datasets.

Network representation learning (NRL) and cascade representation learning (CRL) are fundamental backbones of different kinds of network analysis problems. They are usually carried out in settings where the structure of the network under consideration is known. Motivated by real-world problems, this study presents several algorithms for scenarios where the network structure is partially or completely unknown. The objective of network representation learning is to identify a mapping function that projects sparse and high-dimensional network graphs into a dense latent representation, which preserves the original information about nodes and their neighborhoods. The notion of neighborhood, however, becomes illusive when the network structure is partially or completely hidden. Inspired by previous results, in our thesis work we have developed novel algorithms that are resilient to such lack of knowledge. These results establish a correlation between the properties of the network and different kind of node activities performed over it, information which is generally more available and can be easily observed. In particular, we focus on diffusion events – also called cascades – such as shares, retweets and hashtags. In the first of our contributions, we have developed a novel NRL algorithm called Mineral, a simple technique that combines the observed cascades with the partially accessible network structure by sampling artificial cascades. Node representation is then learned from the observed and sampled cascades by using the SkipGram model that is widely used for word representation learning in natural language documents. In our second contribution, called NetTensor, we assume that the network structure is completely hidden and we propose novel techniques that are capable to estimate both the hidden neighborhood (proximity) and the similarity of nodes. Such estimated values are then used to learn a unified embedding of nodes using a scalable truncated singular value decomposition and deep autoencoders. In addition to the NRL algorithms, we have also proposed a novel CRL algorithm called cas2vec for virality (popularity) prediction. Again, we pursue a network-agnostic approach following the above assumption that the network structure is completely unknown. Unlike prior studies that rely on manual feature extraction, cas2vec automatically learns cascade representations based on convolutional neural networks, that are effective in predicting virality of cascades. We have carried out extensive experiments using several real-world datasets for all of our methods and compared them against strong baselines from the state-of-the-art, achieving significantly better results than many of them.

Network representation learning (NRL) enables the application of machine learning tasks such as classification, prediction and recommendation to networks. Apart from their graph structure, networks are often associated with diverse information in the form of attributes. Most NRL methods have focused just on structural information, and separately apply a traditional representation learning on attributes. When multiple sources of information are available, using a combination of them may be beneficial as they complement each other in generating accurate contexts; moreover, their combined use may be fundamental when the information sources are sparse. The learning methods should thus preserve both the structural and attribute aspects. In this paper, we investigate how attributes can be modeled, and subsequently used along with structural information in learning the representation. We introduce the gat2vec framework that uses structural information to generate structural contexts, attributes to generate attribute contexts, and employs a shallow neural network model to learn a joint representation from them. We evaluate our proposed method against state-of-the-art baselines, using real-world datasets on vertex classification (multi-class and multi-label), link-prediction, and visualization tasks. The experiments show that gat2vec is effective in exploiting multiple sources of information, thus learning accurate representations and outperforming the state-of-the-art in the aforementioned tasks. Finally, we perform query tasks on learned representation and show how the qualitative analysis of results has better performance as well."

Effectively predicting whether a given post or tweet is going to become viral in online social networks is of paramount importance for several applications, such as trend and break-out forecasting. While several attempts towards this end exist, most of the current approaches rely on features extracted from the underlying network structure over which the content spreads. Recent studies have shown, however, that prediction can be effectively performed with very little structural information about the network, or even with no structural information at all. In this study we propose a novel network-agnostic approach called CAS2VEC, that models information cascades as time series and discretizes them using time slices. For the actual prediction task we have adopted a technique from the natural language processing community. The particular choice of the technique is mainly inspired by an empirical observation on the strong similarity between the distribution of discretized values occurrence in cascades and words occurrence in natural language documents. Thus, thanks to such a technique for sentence classification using convolutional neural networks, CAS2VEC can predict whether a cascade is going to become viral or not. We have performed extensive experiments on two widely used real-world datasets for cascade prediction, that demonstrate the effectiveness of our algorithm against strong baselines.

Network representation learning (NRL) is a task of learning an embedding of nodes in a low-dimensional space. Recent advances in this area have achieved interesting results; however, as there is no solution that fits all kind of networks, NRL algorithms need to be specialized to preserve specific aspects of the networks, such as topology, information content, and community structure. One aspect that has been neglected so far is how a network reacts to the diffusion of information. This aspect is particularly relevant in the context of social networks. Studies have found out that diffusion reveals complex patterns in the network structure that are otherwise difficult to be discovered by other means. In this work, we describe a novel algorithm that combines topology, information content and diffusion process, and jointly learns a high quality embedding of nodes. We performed several experiments using multiple datasets and demonstrate that our algorithm performs significantly better in many network analysis tasks over existing studies.

Network representation learning has recently attracted considerable interest, because of its effectiveness in performing important network analysis tasks such as link prediction and node classification. However, most of the existing studies rely on the knowledge of the complete network structure. Very often this is not the case, unfortunately the network is either partially or completely hidden. For example, due to privacy and competitive market advantage, the friendship and follower networks of Facebook and Twitter are hardly accessible. User activity logs (also known as cascades), instead, are usually available. In this study we propose Refine, a representation learning algorithm that does not require information about the network and simply utilizes cascades. Nodes embeddings learned through Refine are optimized for network reconstruction. Towards this end, it utilizes the global interaction patterns exposed by reaction times and co-occurrences. We present an extensive experimentation using two OSN datasets and show that our approach outperforms existing baselines. In addition, we empirically show that Refine can be used to predict cascades as well

The diffusion of a contagion (e.g. news, meme, virus) is a common event in online and onine social networks. Unfortunately, such networks, known as diffusion networks, are often unknown: that is, one can observe when subjects are infected by a given contagion (e.g., when a piece of information arrives, when a product is adopted, when a virus is caught), but does not know through which connection the infection has been transmitted. The goal of this study is to infer such networks based on nodes infection contexts associated to diffusion events (cascades). Previous studies mostly relied on delay patterns between infection events of nodes to infer edges. It has been argued, however, that delay-agnostic approaches are also efficient for such inference. Motivated by this finding, we present a novel delay-agnostic algorithm that is largely inspired by representation learning of words in documents and nodes in networks. Moreover, unlike some delay-agnostic methods, we only consider infection context of nodes in a restricted window. After empirically observing a similarity between the distribution of words in documents and nodes in cascades, we employ the Skip-Gram model to learn a representation of nodes from cascades. The learned representation is then used to compute the probability that an edge exists between a pair of nodes. Through extensive experiments we validate the effectiveness of our algorithm, showing that it is able to recover up to 95% of the hidden network in realistic datasets. We have also compared our algorithm to the state-of-the-art algorithm InfoPath, and achieved a large improvement on the quality of results.