In cross-domain recommendation, the cold-start recommendation problem often arises in scenarios where users have interacted with items in a source domain but not in a target domain. A key challenge in this cross-domain recommendation setting is how to effectively transfer user preferences from the source domain to the target domain. Most existing transfer learning models address this challenge but typically require extensive computations and incremental operations, which limit their scalability and efficiency. To overcome these limitations, we propose a novel similarity-based framework, called Similarity-based Transfer Graph Convolution Network (SimTranGCN), designed specifically for cold-start users. Our approach combines item-KNN, deep learning, and graph convolutional models such as LightGCN. SimTranGCN first constructs a similarity matrix across domains, and then uses this matrix to infer user preferences in the target domain based on their interactions in the source domain. Empirical experiments demonstrate that SimTranGCN is highly competitive against existing methods, achieving state-of-the-art performance on two paired domain transfer tasks.

Reinforcement learning (RL) has demonstrated great potential to improve slate-based recommender systems by optimizing long-term user engagement. However, addressing the combinatorial action space in slate recommendations remains challenging. Recent work decomposes slate Q -values into item-wise Q -values, improving the tractability of value-based methods to learn the model. But in scenarios with a large item pool and a resource-intensive value function like deep neural networks, the action selection process still incurs substantial computational costs. Slow training might be tolerable, but high costs during action selection could hinder real-time deployment. To address this issue, this article introduces an actor method that reduces Q -function evaluations to a subset of items, significantly cutting inference time for practical deployment. The research suggests acquiring representations at both item and slate levels, strategically identifying a specific item subset for slate composition. The proposed methodologies are assessed over different simulated user engagement behaviors: users certain about preferences (“decisive” behavior) and those more exploratory or bored users, losing interest with repetitive content exposure (“explorative” behavior). Empirical evaluation shows that the proposed approach achieves comparable user engagement with a value-based policy across behaviors. Meanwhile, it notably enhances serving time while recommending diverse topic slates, thus demonstrating its potential effectiveness and efficiency in real-world applications.

Session-based slate recommendation systems curate ranked sets of items in real-time, adapting to evolving user interactions.Balancing relevance, diversity, and novelty remains challenging for reinforcement learning (RL) methods.Recent advances in large language models (LLMs) offer a new possibility to leverage their semantic reasoning capabilities to refine slate composition.In this work, we examine the impact of LLM-driven reasoning on slate generation by integrating LLMs with an RL-based slate recommender and evaluating in terms of accuracy, similarity, diversity, and novelty.We extend the RecSim framework with real-world interaction data and introduce a session-aware evaluation protocol that captures long-term engagement.Our analysis reveals that LLM reasoning enhances subcategory-level diversity while maintaining relevance, leading to increased user engagement.By visualizing category-level shifts in slate composition we uncover systematic patterns in how LLMs refine recommendation diversity.Although direct LLM use during inference may be hampered by computational demands and latency concerns, our experimental results demonstrate that integrating LLM modifications during training enables the model to internalize the nuanced characteristics of LLM reasoning without incurring inference overhead, thereby improving recommendation performance, serving time efficiency, and deployability.

Data privacy is a critical concern in today's data-driven world. To this end, Federated Learning (FL) has been researched extensively, as it allows sensitive data to be kept secure on local devices while training global Machine Learning (ML) models across multiple devices. Several FL topologies have been introduced to address different users' needs. FL fits well within the Recommender Systems (RS) domain, with decentralised large-scale datasets and user privacy issues, as it improves personalised recommendations and accuracy while keeping users' sensitive data secure.

SplitFed algorithm is a novel collaborative learning framework that enables decentralised learning of large deep architectures without the need to share sensitive raw data. However, this approach comes with a drawback of large communication overhead, as both the intermediate weights for forward propagation and gradients for backpropagation need to be regularly communicated with the server.This paper presents an empirical evaluation of methods that have the potential to address the communication inefficiency of the SplitFed algorithm. In particular, we study Early Exit (EE) algorithms and their application in the context of SplitFed. In our empirical evaluation, we insert the EE at the last layer of the local client model and train this smaller model locally in tandem with the large model. We show that the communication overhead can be reduced even further by randomly sampling smaller subsets from the training set. We evaluate this approach on several deep model architectures across various datasets and demonstrate that this approach can significantly save on communication while maintaining the accuracy of the base model.

News recommendations heavily rely on Natural Language Processing (NLP) methods to analyze, understand, and categorize content, enabling personalized suggestions based on user interests and reading behaviors. Large Language Models (LLMs) like GPT-4 have shown promising performance in understanding natural language. However, the extent of their applicability to news recommendation systems remains to be validated. This paper introduces RecPrompt, the first self-tuning prompting framework for news recommendation, leveraging the capabilities of LLMs to perform complex news recommendation tasks. This framework incorporates a news recommender and a prompt optimizer that applies an iterative bootstrapping process to enhance recommendations through automatic prompt engineering. Extensive experimental results with 400 users show that RecPrompt can achieve an improvement of 3.36% in AUC, 10.49% in MRR, 9.64% in nDCG@5, and 6.20% in nDCG@10 compared to deep neural models. Additionally, we introduce TopicScore, a novel metric to assess explainability by evaluating LLM's ability to summarize topics of interest for users. The results show LLM's effectiveness in accurately identifying topics of interest and delivering comprehensive topic-based explanations.

Recommender systems have achieved remarkable success in various web applications, such as e-commerce, online advertising, and social media, harnessing the power of big data. To attain optimal model performance, recommender systems are typically trained on very large datasets, with substantial numbers of users and items. However, large datasets often present challenges in terms of processing time and computational resources. Coreset selection offers a method for obtaining a reduced yet representative subset from vast datasets, thereby enhancing the efficiency of training machine learning algorithms. Nevertheless, little research has been conducted to explore the practical implications of different coreset selection approaches on the performance of recommender systems algorithms. In this paper, we systematically investigate the impact of various coreset selection techniques. We evaluate the performance of the resulting coresets using inductive recommendation models which allow for consistent evaluations to be performed. The experimental results demonstrate that coreset methods are a powerful and useful approach for obtaining reduced datasets which preserve the properties of the large original dataset and have competitive performance compared to the time required to train with the full dataset.

Recent years have seen a rise in smartphone applications promoting health and well being. We argue that there is a large and unexplored ground within the field of recommender systems (RS) for applications that promote good personal health. During the COVID-19 pandemic, with gyms being closed, the demand for at-home fitness apps increased as users wished to maintain their physical and mental health. However, maintaining long-term user engagement with fitness applications has proved a difficult task. Personalisation of the app recommendations that change over time can be a key factor for maintaining high user engagement. In this work we propose a reinforcement learning (RL) based framework for recommending sequences of body-weight exercises to home users over a mobile application interface. The framework employs a user simulator, tuned to feedback a weighted sum of realistic workout rewards, and trains a neural network model to maximise the expected reward over generated exercise sequences. We evaluate our framework within the context of a large 15 week live user trial, showing that an RL based approach leads to a significant increase in user engagement compared to a baseline recommendation algorithm.

Reinforcement learning (RL) has demonstrated great potential to improve slate-based recommender systems by optimizing recommendations for long-term user engagement. To handle the combinatorial action space in slate recommendation, recent works decompose the Q-value of a slate into item-wise Q-values, using an item-wise value-based policy. However, the common case where the value function is a parameterized function taking state and action as input results in a linearly increasing number of evaluations required to select an action, proportional to the number of candidate items. While slow training may be acceptable, this becomes intractable when considering the costly evaluation of the parameterized function, such as with deep neural networks, during model serving time. To address this issue, we propose an actor-based policy that reduces the evaluation of the Q-function to a subset of items, significantly reducing inference time and enabling practical deployment in real-world industrial settings. In our empirical evaluation, we demonstrate that our proposed approach achieves equivalent user session engagement to a value-based policy, while significantly reducing the slate serving time by at least 4 times.

A recommendation engine that relies solely on interactions between users and items will be limited in its ability to provide accurate, diverse and explanation-rich recommendations. Side information should be taken into account to improve performance. Methods like Factorisation Machines (FM) cast recommendation as a supervised learning problem, where each interaction is viewed as an independent instance with side information encapsulated. Previous studies in top-K recommendation have incorporated knowledge graphs (KG) into the recommender system to provide rich information about the relationships between users, items and entities. Nevertheless, these studies do not explicitly capture the preference of users for the side information. Furthermore, some studies explain the recommendation, but there is no unified method of measuring explanation quality.

Social Capital is considered as the value that an actor draws from the network. It is measured as an ability to bond with others (bonding capital) as well as an ability to form a bridge that connects otherwise disconnected actors or groups in the network (bridging capital). In order to model the social capital, the strategic nature of forming links needs to be considered and baked within the network formation models. In this paper, we develop a strategic network formation game named Structural Hole Connections Game (shc) and define an associated allocation function that distributes the total network value to the actors in the network in such a way that captures their bonding and bridging social capital. Our proposed shc game generalizes the utility function that models both the bonding and bridging capabilities of an actor with high social capital. We first analytically deduct the efficient and stable networks of the shc game. Finally, we analyse a real-world social network of employees of an IT company and identify individuals with binding and bridging social profiles.

In this paper, we propose a novel communication-efficient algorithm for distributed matrix factorisation. Our goal is to find a good trade-off between the communication overhead and the overall model training time. In our setting, the training data is distributed across multiple servers that aim to learn a joint machine learning model. In contrast to standard distributed computation, due to privacy concerns, the participating servers are not allowed to share raw data, however, sharing of the non-personal model parameters is allowed. We investigate the draw-backs of traditional strongly coordinated distributed techniques and compare them to weakly coordinated gossip approaches. The advantage of strongly coordinated approaches is that the learning process closely mimics that of a centralised algorithm and hence this approach can keep the overall training time at a minimum. However, this is at the expense of a large communication footprint of the algorithm. On the other hand, the weakly coordinated gossip approach offers a communication efficient solution that can take a large amount of training time to reach a good accuracy. As a solution, we develop a hybrid approach combining the above two approaches. We apply the hybrid approach on a latent factor model solving a top-N recommendation problem and we show that the hybrid approach achieves good accuracy in relatively short training time with minimal communication overhead particularly on very sparse data.

Hierarchical clustering has been shown to be valuable in many scenarios. Despite its usefulness to many situations, there is no agreed methodology on how to properly evaluate the hierarchies produced from different techniques, particularly in the case where ground-truth labels are unavailable. This motivates us to propose a framework for assessing the quality of hierarchical clustering allocations which covers the case of no ground-truth information. This measurement is useful, e.g., to assess the hierarchical structures used by online retailer websites to display their product catalogues. Our framework is one of the few attempts for the hierarchy evaluation from a decision theoretic perspective. We model the process as a bot searching stochastically for items in the hierarchy and establish a measure representing the degree to which the hierarchy supports this search. We employ Partially Observable Markov Decision Processes (POMDP) to model the uncertainty, the decision making, and the cognitive return for searchers in such a scenario.

The Soft Affiliation Graph model (S-AGM) is a Bayesian generative model of overlapping community structure in social networks. Inference on this model is challenging due to the complexity of both the underlying network structure and the presence of non-conjugacy in the model. Scalable MCMC on the model is possible through the use of Stochastic Gradient Riemannian Langevin Dynamics (SGRLD). In this paper, we develop a novel and scalable Stochastic Gradient Variational Inference (SG-VI) algorithm and compare it to SGRLD inference. Similarly to MCMC inference, handling non-conjugacy in the S-AGM is a significant challenge for developing an SG-VI and requires the application of stochastic Monte Carlo estimation. We carry out a thorough empirical comparison of the SG-VI and SGRLD approaches, and draw some general conclusions about scalable inference on the S-AGM.

Federated learning (FL) is quickly becoming the de facto standard for the distributed training of deep recommendation models, using on-device user data and reducing server costs. In a typical FL process, a central server tasks end-users to train a shared recommendation model using their local data. The local models are trained over several rounds on the users' devices and the server combines them into a global model, which is sent to the devices for the purpose of providing recommendations. Standard FL approaches use randomly selected users for training at each round, and simply average their local models to compute the global model. The resulting federated recommendation models require significant client effort to train and many communication rounds before they converge to a satisfactory accuracy. Users are left with poor quality recommendations until the late stages of training. We present a novel technique, FedFast, to accelerate distributed learning which achieves good accuracy for all users very early in the training process. We achieve this by sampling from a diverse set of participating clients in each training round and applying an active aggregation method that propagates the updated model to the other clients. Consequently, with FedFast the users benefit from far lower communication costs and more accurate models that can be consumed anytime during the training process even at the very early stages. We demonstrate the efficacy of our approach across a variety of benchmark datasets and in comparison to state-of-the-art recommendation techniques.

Nowadays we commonly have multiple sources of data associated with items. Users may provide numerical ratings, or implicit interactions, but may also provide textual reviews. Although many algorithms have been proposed to jointly learn a model over both interactions and textual data, there is room to improve the many factorization models that are proven to work well on interactions data, but are not designed to exploit textual information. Our focus in this work is to propose a simple, yet easily applicable and effective, method to incorporate review data into such factorization models. In particular, we propose to build the user and item embeddings within the topic space of a topic model learned from the review data. This has several advantages: we observe that initializing the user and item embeddings in topic space leads to faster convergence of the factorization algorithm to a model that out-performs models initialized randomly, or with other state-of-the-art initialization strategies. Moreover, constraining user and item factors to topic space allows for the learning of an interpretable model that users can visualise.

Computation of the single-source shortest path (SSSP) is a fundamental primitive in many network analytics tasks. With the increasing size of networks to be analysed, there is a need for efficient tools to compute shortest paths, especially on the widely adopted shared-memory multicore architectures. The Δ-stepping algorithm, that trades-off the work efficiency of Dijkstra's algorithm with the parallelism offered by the Bellman-Ford algorithm, has been found to be among the fastest implementations on various parallel architectures. Despite its widespread popularity, the different design choices in implementing the parallel Δ-stepping algorithm are not properly understood and these design choices can have a significant impact on the final performance. In this paper, we carefully compare two different implementations of the Δ-stepping algorithm for shared-memory multicore architectures: (i) a static workload assignment where the nodes are assigned to threads at the beginning of the algorithm and only the assigned thread can relax edges leading to a node and (ii) a dynamic workload assignment where the nodes are dynamically allocated to threads at the time of bucket relaxation. Based on an extensive empirical study on a range of graph classes, edge density and weight distributions, we show that while the more intuitive and widely used approach of dynamically balanced workload suits dense power-law graphs well, the static partitioning approach outperforms this more intuitive approach on a wide range of graph classes. Our findings can guide a network analyst in selecting the best parallel implementation of the Δ-stepping algorithm for a given analytics task and a given graph class.

Conventional approaches to matrix factorisation (MF) typically rely on a centralised collection of user data for building a MF model. This approach introduces an increased risk when it comes to user privacy. In this short paper we propose an alternative, user-centric, privacy enhanced, decentralised approach to MF. Our method pushes the computation of the recommendation model to the user's device, and eliminates the need to exchange sensitive personal information; instead only the loss gradients of local (device-based) MF models need to be shared. Moreover, users can select the amount and type of information to be shared, for enhanced privacy. We demonstrate the effectiveness of this approach by considering different levels of user privacy in comparison with state-of-the-art alternatives.

Recommender systems (RS) share many features and objectives with reinforcement learning (RL) systems. The former aim to maximise user satisfaction by recommending the right items to the right users at the right time, the latter maximise future rewards by selecting state-changing actions in some environment. The concept of an RL gym has become increasingly important when it comes to supporting the development of RL models. A gym provides a simulation environment in which to test and develop RL agents, providing a state model, actions, rewards/penalties etc. In this paper we describe and demonstrate the PyRecGym gym, which is specifically designed for the needs of recommender systems research, by supporting standard test datasets (MovieLens, Yelp etc.), common input types (text, numeric etc.), and thereby offering researchers a reproducible research environment to accelerate experimentation and development of RL in RS.

Novelty enhancement of recommendations is typically achieved through a post-filtering process applied on a candidate set of items. While it is an effective method, its performance heavily depends on the quality of a baseline algorithm, and many of the state-of-the-art algorithms generate recommendations that are relatively similar to what the user has interacted with in the past. In this paper we explore the use of sampling as a means of novelty enhancement in the Bayesian Personalized Ranking objective. We evaluate the proposed extensions on the MovieLens 20M dataset, and show that the proposed method can be successfully used instead of two-step reranking, as it offers comparable and better accuracy/novelty tradeoffs, and more unique recommendations.

Sociological theories of career success provide fundamental principles for the analysis of social links to identify patterns that facilitate career development. Some theories (e.g. Granovetter's Strength of Weak Ties Theory and Burt's Structural Hole Theory) have shown that certain types of social ties provide career advantage to individuals by facilitating them to access unique information and connecting them with a diverse range of others in different social cliques. The assessment of link types and prediction of new links in the external social networks such as Facebook and Twitter have been studied extensively. However, this has not been addressed in the enterprise social networks and especially the prediction of weak ties in the context of employee career development. In this paper, we address this problem by proposing an Enterprise Weak Ties Recommendation (EWTR) framework which leverages enterprise social networks, employee collaboration activity streams and the organizational chart. We formulate weak ties recommendation as a link prediction problem. However, unlike any generic link prediction work, we first validated explicit enterprise social network with a set of heterogeneous collaboration networks and show assessment improves the explicit network's effectiveness in predicting new links. Furthermore, we leverage assessed social network for the weak ties prediction by optimizing the link prediction methods using organizational chart information. We demonstrate that optimization improves prediction accuracy in terms of AUC and average precision and our characterization of weak ties to a certain extent aligns with Granovetter's and Burt's seminal studies.

Sociological theories of career success provide fundamental principles for the analysis of social networks to identify patterns that facilitate career development. Structural Hole Theory argues that certain network structures provide advantages to individuals by facilitating them to access unique information from parts of the network. The network structural advantages of social networks in workplace settings have not been studied enough for the purpose of employees career development. In this paper, we address this challenge by proposing a Social Capital-Driven Career Development framework which leverages enterprise collaboration activity streams to assess employees social capital across organizational hierarchy levels. We demonstrate that our framework can enable employees to reflect on their social network structure from the prospective of information benefits for progressing their career from one hierarchy level to the immediate next level in their respective business units.

We consider the loop less k-shortest path (KSP) problem. Although this problem has been studied in the sequential setting for at least the last two decades, no good parallel implementations are known. In this paper, we provide (i) a first systematic empirical comparison of various KSP algorithms and heuristic optimisations, (ii) carefully engineer various parallel implementations of these sequential algorithms and (iii) perform an extensive study of these parallel implementations on a range of graph classes and multicore architectures to determine the best algorithm and parallelization strategy for different graph classes.

Diversity has been identified as one of the key dimensions of recommendation utility that should be considered besides the overall accuracy of the system. A common diversification approach is to rerank results produced by a baseline recommendation engine according to a diversification criterion. The intent-aware framework is one of the frameworks that has been proposed for recommendations diversification. It assumes existence of a set of aspects associated with items, which also represent user intentions, and the framework promotes diversity across the aspects to address user expectations more accurately. In this paper we consider item-based collaborative filtering and suggest that the traditional view of item similarity is lacking a user perspective. We argue that user preferences towards different aspects should be reflected in recommendations produced by the system. We incorporate the intent-aware framework into the item-based recommendation algorithm by injecting personalised intent-aware covariance into the item similarity measure, and explore the impact of such change on the performance of the algorithm. Our experiments show that the proposed method improves both accuracy and diversity of recommendations, offering better accuracy/diversity tradeoff than existing solutions.

Many state-of-the-art recommender systems are known to suffer from popularity bias, which means that they have a tendency to recommend items that are already popular, making those items even more popular. This results in the item catalogue being not fully utilised, which is far from ideal from the business' perspective. Issues of item exposure are actually more complex than simply overexposure of popular items. In this paper we look at the exposure of individual items to different groups of consumers, the item's audience, and address the question of whether recommender systems reach each item's potential audience. Thus, we go beyond state-of-the-art analyses that have simply addressed the extent to which items are recommended, regardless of whether they are reaching their target audience. We conduct an empirical study on the MovieLens 20M dataset showing that recommender systems do not fully utilise items' audiences, and existing sales diversity optimisers do not improve their exposure.

This paper evaluates two algorithms, BLIP and JLT, for creating differentially private data sketches of user profiles, in terms of their ability to protect a kNN collaborative filtering algorithm from an inference attack by third-parties. The transformed user profiles are employed in a user-based top-N collaborative filtering system. For the first time, a theoretical analysis of the BLIP is carried out, to derive expressions that relate its parameters to its performance. This allows the two techniques to be fairly compared. The impact of deploying these approaches on the utility of the system---its ability to make good recommendations, and on its privacy level---the ability of third-parties to make inferences about the underlying user preferences, is examined. An active inference attack is evaluated, that consists of the injection of a number of tailored sybil profiles into the system database. User profile data of targeted users is then inferred from the recommendations made to the sybils. Although the differentially private sketches are designed to allow the transformed user profiles to be published without compromising privacy, the attack we examine does not use such information and depends only on some pre-existing knowledge of some user preferences as well as the neighbourhood size of the kNN algorithm. Our analysis therefore assesses in practical terms a relatively weak privacy attack, which is extremely simple to apply in systems that allow low-cost generation of sybils. We find that, for a given differential privacy level, the BLIP injects less noise into the system, but for a given level of noise, the JLT offers a more compact representation.

News and social media now play a synergistic role and neither domain can be grasped in isolation. On one hand, platforms such as Twitter have taken a central role in the dissemination and consumption of news. On the other hand, news editors rely on social media for following their audience's attention and for crowd-sourcing news stories. Twitter hashtags function as a key connection between Twitter crowds and the news media, by naturally naming and contextualizing stories, grouping the discussion of news and marking topic trends. In this work, we propose Hashtagger+, an efficient learning-to-rank framework for merging news and social streams in real-time, by recommending Twitter hashtags to news articles. We provide an extensive study of different approaches for streaming hashtag recommendation, and show that pointwise learning-to-rank is more effective than multi-class classification as well as more complex learning-to-rank approaches. We improve the efficiency and coverage of a state-of-the-art hashtag recommendation model by proposing new techniques for data collection and feature computation. In our comprehensive evaluation on real-data, we show that we drastically outperform the accuracy and efficiency of prior methods. Our prototype system delivers recommendations in under 1 minute, with a Precision@1 of 94 percent and article coverage of 80 percent. This is an order of magnitude faster than prior approaches, and brings improvements of 5 percent in precision and 20 percent in coverage. By effectively linking the news stream to the social stream via the recommended hashtags, we open the door to solving many challenging problems related to story detection and tracking. To showcase this potential, we present an application of our recommendations to automated news story tracking via social tags. Our recommendation framework is implemented in a real-time Web system available from insight4news.ucd.ie.

Blockmodelling is a technique whose aim is to identify meaningful structure in networks. Community finding is a type of blockmodelling in so far as it focuses on identifying dense subgraph structure. Generalised blockmodelling allows an analyst to explicitly control the type of extracted structure. When compared to the well studied community-finding problem, generalised blockmodelling algorithms lag well behind in terms of their scalability. In this paper we formulate and evaluate a generalised blockmodelling algorithm, based on the Infomap information-theoretic community-finding algorithm. We reformulate the optimisation objective of the Infomap algorithm, so that it is extended to identify specific types of meso-scale structure that are given as input by the analyst. We evaluate our method against other generalised blockmodelling algorithms.

The intent-aware diversification framework was introduced initially in information retrieval and adopted to the context of recommender systems in the work of Vargas et al. The framework considers a set of aspects associated with items to be recommended. For instance, aspects may correspond to genres in movie recommendations. The framework depends on input aspect model consisting of item selection or relevance probabilities, given an aspect, and user intents, in the form of probabilities that the user is interested in each aspect. In this paper, we examine a number of input aspect models and evaluate the impact that different models have on the framework. In particular, we propose a constrained PLSA model that allows for interpretable output, in terms of known aspects, while achieving greater performance that the explicit co-occurrence counting method used in previous work. We evaluate the proposed models using a well-known MovieLens dataset for which item genres are available.

We address the problem of real-time recommendation of streaming Twitter hashtags to an incoming stream of news articles. The technical challenge can be framed as large scale topic classification where the set of topics (i.e., hashtags) is huge and highly dynamic. Our main applications come from digital journalism, e.g., promoting original content to Twitter communities and social indexing of news to enable better retrieval and story tracking. In contrast to the state-of-the-art that focuses on topic modelling approaches, we propose a learning-to-rank approach for modelling hashtag relevance. This enables us to deal with the dynamic nature of the problem, since a relevance model is stable over time, while a topic model needs to be continuously retrained. We present the data collection and processing pipeline, as well as our methodology for achieving low latency, high precision recommendations. Our empirical results show that our method outperforms the state-of-the-art, delivering more than 80% precision. Our techniques are implemented in a real-time system that is currently under user trial with a big news organisation.

Among the many community-finding algorithms that have been proposed in the last decade and more, the Infomap algorithm of Rosvall and Bergstrom has proven among the best. The algorithm finds good community structure in directed as well as undirected networks by abstracting information flow in the network as a random walk. In this paper, we reformulate the objective in terms of the Kullback-Leibler distance between the distribution of the random walk transitions and that of a model walk. The choice of model can be used to constrain the type of partition that the method extracts. This generalisation makes the method suitable for extracting other types of meso-structure from the network, enabling the analyst to explicitly control the type of extracted structure.

Community finding in social network analysis is the task of identifying groups of people within a larger population who are more likely to connect to each other than connect to others in the population. Much existing research has focussed on non-overlapping clustering. However, communities in real-world social networks do overlap. This paper introduces a new community finding method based on overlapping clustering. A Bayesian statistical model is presented, and a Markov Chain Monte Carlo (MCMC) algorithm is presented and evaluated in comparison with two existing overlapping community finding methods that are applicable to large networks. We evaluate our algorithm on networks with thousands of nodes and tens of thousands of edges.

In this paper, we present ChurnVis, a system for visualizing components affected by mobile telecommunications churn and subscriber actions over time. We describe our experience of deploying this system in a network analytics company for use in data analysis and presentation tasks. As social influence seems to be a factor in mobile telecommunications churn (the decision of a subscriber to leave a particular service provider), the visualization is based on a social network inferred from calling data between subscribers. Using this network, churn components, or groups of churners who are connected in the social network, are segmented out and trends in their static and dynamic attributes are visualized. ChurnVis helps analysts understand trends in these components in a way that respects the data privacy constraints of the service provider. Through this two pipeline approach, we are able to visualize thousands of churn components filtered from a social network of hundreds of millions of edges.

In this paper we discuss a method to incorporate diversity into a personalised ranking objective, in the context of ranking-based recommendation using implicit feedback. The goal is to provide a ranking of items that respects user preferences while also tending to rank diverse items closely together. A prediction formula is learned as the product of user and item feature vectors, in order to minimise the mean squared error objective used previously in the RankALS and RankSGD methods, but modified to weight the difference in ratings between two items by the dissimilarity of those items. We report on preliminary experiments with this modified objective, in which the minimisation is carried out using stochastic gradient descent. We show that rankings based on the output of the minimisation succeed in producing recommendation lists with greater diversity, with just a small loss in relevance of the recommendation, as measured by the error rate.

K-clique percolation is an overlapping community finding algorithm which extracts particular structures, comprised of overlapping cliques, from complex networks. While it is conceptually straightforward, and can be elegantly expressed using clique graphs, certain aspects of k-clique percolation are computationally challenging in practice. In this paper we investigate aspects of empirical social networks, such as the large numbers of overlapping maximal cliques contained within them, that make clique percolation, and clique graph representations, computationally expensive. We motivate a simple algorithm to conduct clique percolation, and investigate its performance compared to current best-in-class algorithms. We present improvements to this algorithm, which allow us to perform k-clique percolation on much larger empirical datasets. Our approaches perform much better than existing algorithms on networks exhibiting pervasively overlapping community structure, especially for higher values of k. However, clique percolation remains a hard computational problem, current algorithms still scale worse than some other overlapping community finding algorithms.

EgoNav is a visual analytics system that characterizes egos based on the relationship structure of their egocentric networks and presents the results as a spatialization. An ego, or individual node in a network, is most closely related to its neighbors, and to a lesser degree, to its neighbor's neighbors. For example, in social networks, people are closely related to their friends and family. In financial networks, the affairs of borrowers and lenders are more closely tied to each other. In fact, the relationship structure surrounding an ego, or an egocentric network, can provide characteristic information about the ego itself. Using network motif analysis and dimensionality reduction techniques, the system places egos in similar areas of a spatialization if their egocentric networks are structurally similar. This view of a network discriminates between the various classes of typical and exceptional egos. We demonstrate its effectiveness using appropriate synthetic datasets, real-world mobile phone call and peer-to-peer lending datasets. We subsequently elicit user feedback from experts involved in the investigation of financial fraud to assess the tool's applicability in this domain.

In this paper we attempt to retrieve the items in the long-tail for top-N recommendation. That is, to recommend products that the end-user likes, but that are not generally popular, which has been getting more and more notice lately. By analysing the existing issue of current recommendation algorithms, a strategy is proposed that succeeds in maintaining recommendation accuracy while reducing the concentration of the recommendation on popular items in the system. Evaluating on the publicly available Movie lens and Yahoo! datasets, the results show the recommendation algorithm proposed in this work retrieves items in the users' relatively unpopular tastes without losing the performance in their popular tastes, which ultimately results in a better overall accuracy for the system.

A key problem for social network analysis is the lack of ground-truth data upon which to validate an analysis. Consider for example community-finding algorithms. The ``communities'' identified by such algorithms are typically justified on the basis of their structural properties, rather than on their ability to recover communities which can be independently verified. A ground truth of actual community data isn't always available and at best only partial ground-truth community information is. However, this problem isn't unique to community-finding algorithms. In previous publications, we introduced an automated Social Network Assembly Pipeline we refer to as SNAP. This is intended for the large scale actor identification, tie interference and strength measurement of social networks from non-relational data sets. In this paper we describe a validation study of SNAP through an intensive user-study of a portion of the individuals in the network. Individuals are asked to validate the network relationships uncovered by SNAP and where misclassified relationships are found, the individuals are interviewed in order to determine the underlying cause of the misclassification. The findings provide feedback on the rules through which relationships are inferred. For instance, it becomes clear that an error in actor identification can result in a propagation of this error though the network relations leading to follow-on relationship misclassifications. Also, we observe how outliers lead to a propagation of error in the inferred network. The results help us validate and invalidate different hypotheses we have about SNAP and suggests domain specific rule-sets for SNAP.

Considering a clique as a conservative definition of community structure, we examine how graph partitioning algorithms interact with cliques. Many popular community-finding algorithms partition the entire graph into non-overlapping communities. We show that on a wide range of empirical networks, from different domains, significant numbers of cliques are split across separate partitions, as produced by such algorithms. We examine the largest connected component of the sub graph formed by retaining only edges in cliques, and apply partitioning strategies that explicitly minimise the number of cliques split. We conclude that, due to the connectedness of many networks, any community finding algorithm that produces partitions must fail to find at least some significant structures. Moreover, contrary to traditional intuition, in some empirical networks, strong ties and cliques frequently do cross community boundaries.

When studying complex networks, we are often interested in identifying structures within the networks. Previous work has successfully used algorithmically identified network structures to predict functional groups; for example, where structures extracted from protein-protein interaction networks have been predictive of functional protein complexes. One way structures in complex networks have previously been described is as collections of nodes that maximise a local quality function.For a particular set of structures, we search the space of quality functions using Genetic Programming, to find a function that locally describes that set of structures. This technique allows us to investigate the common network properties of defined sets of structures. We also use this technique to classify and differentiate between different types of structure. We apply this method on several synthetic benchmarks, and on a protein-protein interaction network. Our results indicate this is a useful technique of investigating properties that sets of network structures have in common.

The possibility of designing user rating profiles to deliberately and maliciously manipulate the recommendation output of a collaborative filtering system was first raised in 2002. One scenario proposed was that an author, motivated to increase recommendations of his book, might create a set of false profiles that rate the book highly, in an effort to artificially promote the ratings given by the system to genuine users. Several attack models have been proposed and the performance of these attacks in terms of influencing the system predictions has been evaluated for a number of memory-based and model-based collaborative filtering algorithms. Moreover, strategies have been proposed to enhance the robustness of existing algorithms and new algorithms have been proposed with built-in attack resistance. This tutorial will review the work that has taken place in the last decade on robustness of recommendation algorithms and seek to examine the question of the importance of robustness in future research.

For recommender systems that base their product rankings primarily on a measure of similarity between items and the user query, it can often happen that products on the recommendation list are highly similar to each other and lack diversity. In this article we argue that the motivation of diversity research is to increase the probability of retrieving unusual or novel items which are relevant to the user and introduce a methodology to evaluate their performance in terms of novel item retrieval. Moreover, noting that the retrieval of a set of items matching a user query is a common problem across many applications of information retrieval, we formulate the trade-off between diversity and matching quality as a binary optimization problem, with an input control parameter allowing explicit tuning of this trade-off. We study solution strategies to the optimization problem and demonstrate the importance of the control parameter in obtaining desired system performance. The methods are evaluated for collaborative recommendation using two datasets and case-based recommendation using a synthetic dataset constructed from the public-domain Travel dataset.

As research into community finding in social networks progresses, there is a need for algorithms capable of detecting overlapping community structure. Many algorithms have been proposed in recent years that are capable of assigning each node to more than a single community. The performance of these algorithms tends to degrade when the ground-truth contains a more highly overlapping community structure, with nodes assigned to more than two communities. Such highly overlapping structure is likely to exist in many social networks, such as Facebook friendship networks. In this paper we present a scalable algorithm, MOSES, based on a statistical model of community structure, which is capable of detecting highly overlapping community structure, especially when there is variance in the number of communities each node is in. In evaluation on synthetic data MOSES is found to be superior to existing algorithms, especially at high levels of overlap. We demonstrate MOSES on real social network data by analyzing the networks of friendship links between students of five US universities.

Collaborative filtering (CF) recommender systems help people discover what they really need in a large set of alternatives by analyzing the preferences of other related users. Recent research has shown that the accuracy of recommendations can be improved significantly by using matrix factorization (MF) models. In particular, a mixed MF model was used by BellKor's Pragmatic Chaos to win the Netflix Prize. On the other hand, system designers must also be concerned about system robustness - the ability of the system to provide good recommendations when the system database is contaminated with some portion of noisy or erroneous data, perhaps maliciously entered by `profile injection' attackers intent on distorting system recommendations. In this paper, we focus on the robustness of MF based CF algorithms (MFCF), which usually transform the prediction of user preferences on items into a least squares problem, solved by gradient descent. As least squares is known to be sensitive to outliers, it is not surprising that MF algorithms are vulnerable to attack. Nevertheless a number of `robust statistics' have been proposed since the 1960's that provide alternative data fitting strategies that are less sensitive to outliers. In particular, in this paper, we propose a least trimmed squares based MF (LTSMF) to help improve the robustness of the least squares based MF (LSMF) models. Least trimmed squares is shown to be more robust than least squares and another popular robust method-M-estimator. Experiments also show that LTSMF outperforms previous robust CF models on both accuracy and robustness.

A challenge for personalised recommender systems is to target products in the long tail. That is, to recommend products that the end-user likes, but that are not generally popular. To achieve this goal, in this paper we propose two strategies to identify relevant but niche products. The first strategy computes an inverse item popularity and applies it during the steps of top-N recommendation. Given a prior probability distribution of relevance based on item popularity, and a user-specific relevance probability, the other strategy uses a number of scores based on distance measures between these two distributions. We emphasize that the problem is to recommend relevant items from the user's broader range of tastes. Hence, in evaluation a concentration index is calculated to measure the extent to which the recommendation is spread to the user's niche tastes in conjunction with the standard precision metric which measures the overall relevance of the recommended set. The methods are evaluated empirically using the Movielens dataset and show a strong performance in niche item retrieval at the cost of a small reduction in precision.

In this paper we examine the diversity of recommendation algorithms, that is, their ability to recommend a broad range of relevant choices to the end-user. We tackle the question of how to evaluate recommendation algorithm diversity, critiquing methodologies that have been used in the state-of-the-art and proposing an alternative methodology that examines the extent to which the recommendation is concentrated in a sub-set of the catalogue.

Robustness analysis research has shown that conventional memory-based recommender systems are very susceptible to malicious profile-injection attacks. A number of attack models have been proposed and studied and recent work has suggested that model-based collaborative filtering (CF) algorithms have greater robustness against these attacks. Moreover, to combat such attacks, several attack detection algorithms have been proposed. One that has shown high detection accuracy is based on using principal component analysis (PCA) to cluster attack profiles on the basis that such profiles are highly correlated. In this paper, we argue that the robustness observed in model-based algorithms is due to the fact that the proposed attacks have not targeted the specific vulnerabilities of these algorithms. We discuss how an effective attack targeting model-based algorithms that employ profile clustering can be designed. It transpires that the attack profiles employed in this attack, exhibit low rather than high pair-wise similarities and can easily be obfuscated to avoid PCA-based detection, while remaining effective.

It has been shown in recent years that effective profile injection or shilling attacks can be mounted on standard recommendation algorithms. These attacks consist of the insertion of bogus user profiles into the system database in order to manipulate the recommendation output, for example to promote or demote the predicted ratings for a particular product. A number of attack models have been proposed and some detection strategies to identify these attacks have been empirically evaluated. In this paper we show that the standard attack models can be readily detected using statistical detection techniques. We argue that insufficient consideration of the effectiveness of attacks under a constraint of statistical invariance has been taken in past research. In fact, it is possible to create effective attacks that are undetectable using the detection strategies proposed to date, including the PCA-based clustering strategy which has shown excellent performance against standard attacks. Nevertheless, these more advanced attacks can also be detected with careful design of a statistical detector. The question posed for future research is whether attack models that produce effective attack profiles that are statistically identical to genuine profiles are really possible.

This paper provides the first statistical analysis of recommendation diversity. We propose a model that allows diversity to be evaluated analytically using the concentration index, a statistical measure of diversity. While this model abstracts the recommendation process, it provides good overall agreement with real recommendation algorithms. Using the model we are able to analytically demonstrate the trade-off between diversity and overall system performance. Moreover, the model makes explicit the various choices that are available to the algorithm designer to improve recommendation diversity. Our exploration of these choices provides good insight into what can be achieved in practice by algorithms that attempt to provide greater recommendation diversity without significant degradation of system precision.

Standard top-N collaborative recommendation algorithms are very poor at recommending relevant products to a user that are more novel than her average tastes. Our study shows that novel recommendation is difficult because standard similarity metrics measure the aggregate similarity to multiple items in the user profile and the influence of more novel items is lost in the aggregation. To better capture the user's range of tastes, we propose to partition the user profile into clusters of similar items and compose the recommendation list of items that match well with each cluster, rather than with the entire user profile. In this paper we evaluate a number of partitioning strategies in combination with a dimension reduction strategy. A new evaluation methodology is introduced to capture the system ability to diversify its recommendations across relevant items regardless of their novelty. By plotting concentration curves of novelty against accuracy, we show that this strategy succeeds in reducing the system bias towards similar items at a small cost to overall accuracy.

Successful information retrieval with case-based reasoning (CBR) depends on a good similarity metric that can distinguish those cases that are most pertinent to a user's query in a potentially large case-base. Traditional CBR ranks cases according to their similarity value and returns a small number of top-ranked cases in response to the query. Since in general the retrieved cases are very well matched to the input user query, there is a high probability that they are also strongly similar to each other, and hence the range of choice offered in the retrieved list is limited. As a response to this issue, some recent research has considered methods to increase the intra-dissimilarity or diversity of the retrieved set. In this paper, we study this problem in detail. We argue that the motivation of diversity strategies is to increase the probability of retrieving unusual or novel cases and introduce a methodology that allows their performance in terms of novel case retrieval to be evaluated. Moreover, we formulate the trade-off between diversity and matching quality as a binary optimisation problem, with an input control parameter allowing explicit tuning of this trade-off. We study solution strategies to the optimisation problems and demonstrate the importance of the control parameter in obtaining desired system performance. The methods discussed are evaluated on synthetic data, based on the publicly available Travel case-based data-set.

The primary premise upon which top-N recommender systems operate is that similar users are likely to have similar tastes with regard to their product choices. For this reason, recommender algorithms depend deeply on similarity metrics to build the recommendation lists for end-users.However, it has been noted that the products offered on recommendation lists are often too similar to each other and attention has been paid towards the goal of improving diversity to avoid monotonous recommendations.Noting that the retrieval of a set of items matching a user query is a common problem across many applications of information retrieval, we model the competing goals of maximizing the diversity of the retrieved list while maintaining adequate similarity to the user query as a binary optimization problem. We explore a solution strategy to this optimization problem by relaxing it to a trust-region problem.This leads to a parameterized eigenvalue problem whose solution is finally quantized to the required binary solution. We apply this approach to the top-N prediction problem, evaluate the system performance on the Movielens dataset and compare it with a standard item-based top-N algorithm. A new evaluation metric ItemNovelty is proposed in this work. Improvements on both diversity and accuracy are obtained compared to the benchmark algorithm.

We present a theoretical analysis of the Philips audio fingerprinting method under Gaussian white noise distortion for correlated stationary Gaussian sources. Prior analyses were for white Gaussian sources, which do not model realistically real audio signals. Our approach relies on formulating the unquantized fingerprint as a quadratic form, which affords a systematic way to compute the model parameters. We provide closed-form analytical upper bounds for the probability of bit error of the hash, and we apply these expressions to real audio signals.

We present a system for policy-based autonomic replication of data. The system supports multiple distinct replication schemes for a single data item in order to exploit the range of consistency and quality of service requirements of clients. Based on traffic mix and client requirements, nodes in the system may make independent, integrated replica management decisions based on a partial view of the network. A policy based control mechanism is used to administer, manage, and control dynamic replication and access to resources.

We present a 2-D extension of a timing error detector (TED) originally developed by Mueller and Muller for timing recovery on multilevel pulse amplitude modulation (PAM) over 1-D channels. We provide accurate theoretical expressions of the performance of the proposed scheme, and we verify its applicability by studying a particular case. The 2-D TED thus obtained is used as the engine of a 2-D phase locked loop (PLL) for timing recovery.

We present a novel theoretical analysis of the Philips audio fingerprinting method proposed by Haitsma, Kalker, and Oostveen (2001). Although this robust hashing algorithm exhibits very good performance, the method has only been partially analyzed in the literature. Hence, there is a clear need for a more complete analysis which allows both performance prediction and systematic optimization. We examine here the theoretical performance of the method for Gaussian inputs by means of a statistical model. Our analysis relies on formulating the unquantized fingerprint as a quadratic form, which affords a systematic way to compute the model parameters. We provide closed-form analytical upperbounds for the probability of bit error of the hash for two relevant scenarios: noise addition and desynchronization. We show that these results are useful when applied to real audio signals

A new approach to synchronization recovery for signals watermarked using the dither modulation data hiding scheme is presented. The strategy followed involves the use of a digital phase-locked loop to track the offsets applied by an attacker to the sampling grid of the watermarked signal. The main element in this synchronization loop is the timing error detector which is responsible for generating an error signal, used to update the estimates of the applied offsets. It is shown how a timing error detector which has been used in digital communications may be easily adapted to extract timing information from DM watermarked signals. The performance of the proposed synchronizer is evaluated using the probability of decoding error under different models for the sampling grid offsets

In this paper, we propose a framework that enables the detection of noise in recommender system databases. We consider two classes of noise: natural and malicious noise. The issue of natural noise arises from imperfect user behaviour (e.g. erroneous/careless preference selection) and the various rating collection processes that are employed. Malicious noise concerns the deliberate attempt to bias system output in some particular manner. We argue that both classes of noise are important and can adversely effect recommendation performance. Our objective is to devise techniques that enable system administrators to identify and remove from the recommendation process any such noise that is present in the data. We provide an empirical evaluation of our approach and demonstrate that it is successful with respect to key performance indicators.

This paper describes work in progress whereby a dynamic data replication scheme, under market-based control is applied to a proposed autonomic distributed data layer for managing configuration management data. The scope of the proposed autonomic system is described and also some experimental work are presented. Analytic approximations of the performance achieved for management requests under various static data replication schemes are compared with event-based simulations of the same system under dynamic market-based replication control. The purpose of this comparison is to evaluate the performance and suitability of a market-based control approach for such autonomic replication systems

This paper presents software tools to simulate DSP algorithms on a wide variety of fixed point architectures including microprocessors, DSPs and FPGA devices. Existing solutions for evaluating the signal quality in fixed point algorithms are either unable to deal with non-linear systems, fail to consider the architectural details of the target device or do not produce a real output that can be used in subjective testing. Using example non-linear algorithms it is shown that architectural details must be considered when evaluating numerical performance.

The vulnerability of quantization-based data hiding methods to amplitude scaling requires the formulation of countermeasures to this relatively simple attack. Rational dither modulation (RDM) was recently proposed as a quantization-based data hiding scheme, which is scaling invariant. This is achieved by a simple modification of the well-known dither modulation (DM) data hiding method. The performance of RDM, asymptotically in the memory size of the system, can be made to approach that of DM on the Gaussian channel. In this work we examine the application of near-optimal channel coding to RDM. The channel model required to undertake iterative decoding is presented and the proposed method is applied to real image data.

This paper describes a model developed to assess data replication strategies employed in distributed operation support systems (OSSs) and network management systems (NMSs) for future public service networks. Maximum network throughput and optimum configuration is determined from network characteristics such as number of network and management nodes, connectivity, relative message processing rates and degree of replication. Practical illustration of the application of this model is demonstrated for a two-layer management network based on management functions for a 3G radio access network.

Soft hashing, also known as robust hashing or perceptual hashing, consists of summarising multimedia data, so as to obtain a concise representation called a hash value. There has been an increasing interest in the soft hashing problem recently. Techniques implementing soft hashing intend to mirror the behaviour of cryptographic hashing, when the information to be hashed can be subject to different kinds of distortion. Many heuristic techniques for undertaking soft hashing of images and other multimedia data have been devised. Except for some attempts, a framework giving solid guidelines to solve the problem is largely lacking. We provide one possible approach to undertake the modelling of robust soft hashing, detailing the basic problems involved. We show how some prior schemes partly fit into our model.

In this paper we propose novel neighbourhood formation and similarity weight transformation schemes for automated collaborative filtering systems. We demonstrate the benefits of our schemes from the point-of-view of the efficiency and robustness provided, while achieving the accuracy and coverage of a benchmark k-Nearest Neighbour (k-NN) model.

Collaborative recommendation has emerged as an effective technique for personalized information access. However, there has been relatively little theoretical analysis of the conditions under which the technique is effective. To explore this issue, we analyse the robustness of collaborative recommendation: the ability to make recommendations despite (possibly intentional) noisy product ratings. There are two aspects to robustness: recommendation accuracy and stability. We formalize recommendation accuracy in machine learning terms and develop theoretically justified models of accuracy. In addition, we present a framework to examine recommendation stability in the context of a widely-used collaborative filtering algorithm. For each case, we evaluate our analysis using several real-world data-sets. Our investigation is both practically relevant for enterprises wondering whether collaborative recommendation leaves their marketing operations open to attack, and theoretically interesting for the light it sheds on a comprehensive theory of collaborative recommendation.

Spread spectrum watermarking proceeds by extracting a feature vector from the cover contents and embedding a pseudo-random watermark signal in that feature vector. To detect the presence of the watermark, a correlation of the feature vector with the pseudorandom signal is performed and the result compared to a threshold. This correlation detection function is a first-order function of the feature vector components. In recent work, we have proposed that higher-order polynomial detection functions, combined with a side-informed watermark embedding strategy, can be used to increase the efficiency of the watermarking system. We have demonstrated this through a statistical analysis. In this paper, we apply our new family of detection functions to the watermarking of real audio signals. The schemes are tested on a database of over 300 different audio signals and a robustness analysis is performed on the experimental results.

Spread spectrum watermarking proceeds by extracting a feature vector from the cover contents and embedding a pseudo-random watermark signal in that feature vector. To detect the presence of the watermark, a correlation of the feature vector with the pseudo-random signal is performed and the result compared to a threshold. This correlation detection function is a first-order function of the feature vector components. In recent work, we have proposed that higher-order polynomial detection functions, combined with a side-informed watermark embedding strategy, can be used to increase the efficiency of the watermarking system. We have demonstrated this through a statistical analysis. In this paper, we apply our new family of detection functions to the watermarking of real audio signals. The schemes are tested on a database of over 300 different audio signals and a robustness analysis is performed on the experimental results.

This paper deals with some detection issues of watermark signals. We propose an easy way to implement an informed watermarking embedder whatever the detection function. This method shows that a linear detection function is not suitable for side information. This is the reason why we build a family of nonlinear functions named JANIS. Used with a side-informed embedder, its performance is much better than the classical spread spectrum method.

An informed audio watermarking scheme using chaotic waveforms is proposed. The watermark consists of an attenuated signal embedded in the original audio signal. A modulation scheme based on vector quantization is used to achieve blind detection of the watermark signal. A method for self-synchronization of the watermark detector is proposed using chaotic orthogonal waveforms. A perceptual model is employed to ensure inaudibility of the embedded signal that is shaped to the spectrum of the host signal. High robustness to external noise is achieved by spreading the watermark data over a period of time. The robustness of the scheme is assessed by computer simulations.