This work presents a new matrix factorization recommender system approach, that takes repeated interaction into account. We analyze if and how users' repeated interaction behavior---such as repeat purchases---can be integrated into a recommender system. We develop a method that takes advantage of this additional data dimension that is studied in many other fields to derive useful conclusions. Furthermore, we empirically test our method on real-life retailer data and on the Last.fm dataset. We compare our algorithm with popular matrix factorization approaches. Results indicate that our method manages to slightly outperform the existing methods.

This work introduces a novel nonparametric density index defined on graphs, the Sum-over-Forests (SoF) density index. It is based on a clear and intuitive idea: high-density regions in a graph are characterized by the fact that they contain a large amount of low-cost trees with high outdegrees while low-density regions contain few ones. Therefore, a Boltzmann probability distribution on the countable set of forests in the graph is defined so that large (high-cost) forests occur with a low probability while short (low-cost) forests occur with a high probability. Then, the SoF density index of a node is defined as the expected outdegree of this node on the set of forests, thus providing a measure of density around that node. Following the matrix-forest theorem and a statistical physics framework, it is shown that the SoF density index can be easily computed in closed form through a simple matrix inversion. Experiments on artificial and real datasets show that the proposed index performs well on finding dense regions, for graphs of various origins.

This work introduces a link analysis procedure for discovering relationships in a relational database or a graph, generalizing both simple and multiple correspondence analysis. It is based on a random walk model through the database defining a Markov chain having as many states as elements in the database. Suppose we are interested in analyzing the relationships between some elements (or records) contained in two different tables of the relational database. To this end, in a first step, a reduced, much smaller, Markov chain containing only the elements of interest and preserving the main characteristics of the initial chain, is extracted by stochastic complementation. This reduced chain is then analyzed by projecting jointly the elements of interest in the diffusion map subspace and visualizing the results. This two-step procedure reduces to simple correspondence analysis when only two tables are defined, and to multiple correspondence analysis when the database takes the form of a simple star-schema. On the other hand, a kernel version of the diffusion map distance, generalizing the basic diffusion map distance to directed graphs, is also introduced and the links with spectral clustering are discussed. Several data sets are analyzed by using the proposed methodology, showing the usefulness of the technique for extracting relationships in relational databases or graphs.

In this paper, normalized SoP string-edit distances, taking into account all possible alignments between two sequences, are investigated. These normalized distances are variants of the Sum-over-Paths (SoP) distances which compute the expected cost on all sequence alignments by favoring low-cost ones - therefore favoring good alignment. Such distances consider two sequences tied by many optimal or nearly-optimal alignments as more similar than two sequences sharing only one, optimal, alignment. They depend on a parameter, θ, and reduce to the standard distances - the edit-distance or the longest common subsequence - when θ → 0, while having the same time complexity. This paper puts the emphasis on applying some type of normalization of the expectation of the cost. Experimental results for clustering and classification tasks performed on four OCR data sets show that (i) the applied normalization generally improves the existing results, and (ii) as for the SoP edit-distances, the normalized SoP edit-distances clearly outperform the non-randomized measures, i.e. the standard edit distance and longest common subsequence.

This letter addresses the problem of designing the transition probabilities of a finite Markov chain (the policy) in order to minimize the expected cost for reaching a destination node from a source node while maintaining a fixed level of entropy spread throughout the network (the exploration). It is motivated by the following scenario. Suppose you have to route agents through a network in some optimal way, for instance, by minimizing the total travel cost-nothing particular up to now-you could use a standard shortest-path algorithm. Suppose, however, that you want to avoid pure deterministic routing policies in order, for instance, to allow some continual exploration of the network, avoid congestion, or avoid complete predictability of your routing strategy. In other words, you want to introduce some randomness or unpredictability in the routing policy (i.e., the routing policy is randomized). This problem, which will be called the randomized shortest-path problem (RSP), is investigated in this work. The global level of randomness of the routing policy is quantified by the expected Shannon entropy spread throughout the network and is provided a priori by the designer. Then, necessary conditions to compute the optimal randomized policy-minimizing the expected routing cost-are derived. Iterating these necessary conditions, reminiscent of Bellman's value iteration equations, allows computing an optimal policy, that is, a set of transition probabilities in each node. Interestingly and surprisingly enough, this first model, while formulated in a totally different framework, is equivalent to Akamatsu's model ( 1996 ), appearing in transportation science, for a special choice of the entropy constraint. We therefore revisit Akamatsu's model by recasting it into a sum-over-paths statistical physics formalism allowing easy derivation of all the quantities of interest in an elegant, unified way. For instance, it is shown that the unique optimal policy can be obtained by solving a simple linear system of equations. This second model is therefore more convincing because of its computational efficiency and soundness. Finally, simulation results obtained on simple, illustrative examples show that the models behave as expected.

Much early evaluation work focused specifically on the "accuracy" of recommendation algorithms. Good recommendation (in terms of accuracy) has, however, to be coupled with other considerations. This work suggests measures aiming at evaluating other aspects than accuracy of recommendation algorithms. Other considerations include (1) coverage, which measures the percentage of a data set that a recommender system is able to provide recommendation for, (2) confidence metrics that can help users make more effective decisions, (3) computing time, which measures how quickly an algorithm can produce good recommendations, (4) novelty/serendipity, which measure whether a recommendation is original, and (5) robustness which measure the ability of the algorithm to make good predictions in the presence of noisy or sparse data. Six collaborative recommendation methods are investigated. Results on artificial data sets (for robustness) or on the real MovieLens data set (for accuracy, novelty, and computing time) are included and analyzed, showing that kernel-based algorithms provide the best results overall.

Open service-oriented systems which autonomously and continually satisfy users' service requests to optimal levels are an appropriate response to the need for increased automation of information systems. Given a service request, an open service-oriented system interprets the functional and nonfunctional requirements laid out in the request and identifies the optimal selection of services-that is, identifies services. These services' coordinated execution optimally satisfies the requirements in the request. When selecting services, it is relevant to: (1) revise selections as new services appear and others become unavailable; (2) use multiple criteria, including nonfunctional ones to choose among competing services; (3) base the comparisons of services on observed, instead of advertised performance; and (4) allow for uncertainty in the outcome of service executions. To address issues (1)-(4), we propose the multi-criteria randomized reinforcement learning (MCRRL) service selection approach. MCRRL learns and revises service selections using a novel multicriteria-driven (including quality of service parameters, deadline, reputation, cost, and preferences) reinforcement learning algorithm, which integrates the exploitation of data about individual services' past performance with optimal, undirected, continual exploration of new selections that involve services whose behavior has not been observed. The experiments indicate the algorithm behaves as expected and outperforms two standard approaches.

This work presents a new perspective on characterizing the similarity between elements of a database or, more generally, nodes of a weighted and undirected graph. It is based on a Markov-chain model of random walk through the database. More precisely, we compute quantities (the average commute time, the pseudoinverse of the Laplacian matrix of the graph, etc.) that provide similarities between any pair of nodes, having the nice property of increasing when the number of paths connecting those elements increases and when the "length" of paths decreases. It turns out that the square root of the average commute time is a Euclidean distance and that the pseudoinverse of the Laplacian matrix is a kernel matrix (its elements are inner products closely related to commute times). A principal component analysis (PCA) of the graph is introduced for computing the subspace projection of the node vectors in a manner that preserves as much variance as possible in terms of the Euclidean commute-time distance. This graph PCA provides a nice interpretation to the "Fiedler vector," widely used for graph partitioning. The model is evaluated on a collaborative-recommendation task where suggestions are made about which movies people should watch based upon what they watched in the past. Experimental results on the MovieLens database show that the Laplacian-based similarities perform well in comparison with other methods. The model, which nicely fits into the so-called "statistical relational learning" framework, could also be used to compute document or word similarities, and, more generally, it could be applied to machine-learning and pattern-recognition tasks involving a relational database

This work presents a systematic comparison between seven kernels (or similarity matrices) on a graph, namely the exponential diffusion kernel, the Laplacian diffusion kernel, the von Neumann kernel, the regularized Laplacian kernel, the commute time kernel, and finally the Markov diffusion kernel and the cross-entropy diffusion matrix - both introduced in this paper - on a collaborative recommendation task involving a database. The database is viewed as a graph where elements are represented as nodes and relations as links between nodes. From this graph, seven kernels are computed, leading to a set of meaningful proximity measures between nodes, allowing to answer questions about the structure of the graph under investigation; in particular, recommend items to users. Cross- validation results indicate that a simple nearest-neighbours rule based on the similarity measure provided by the regularized Laplacian, the Markov diffusion and the commute time kernels performs best. We therefore recommend the use of the commute time kernel for computing similarities between elements of a database, for two reasons: (1) it has a nice appealing interpretation in terms of random walks and (2) no parameter needs to be adjusted.

This work presents a new perspective on characterizing the similarity between elements of a database or, more generally, nodes of a weighted, undirected graph. It is based on a Markov-chain model of random walk through the database. The suggested quantities, representing dissimilarities (or similarities) between any two elements, have the nice property of decreasing (increasing) when the number of paths connecting those elements increases and when the "length" of any path decreases. The model is evaluated on a collaborative recommendation task where suggestions are made about which movies people should watch based upon what they watched in the past. The model, which nicely fits into the so-called "statistical relational learning" framework as well as the "link analysis" paradigm, could also be used to compute document or word similarities, and, more generally could be applied to other database or Web mining tasks.

In this work, we show that Kleinberg's hubs and authorities model (HITS) is simply principal components analysis (PCA; maybe the most widely used multivariate statistical analysis method), albeit without centering, applied to the adjacency matrix of the graph of Web pages. We further show that a variant of HITS, SALSA, is closely related to correspondence analysis, another standard multivariate statistical analysis method. In addition, to provide a clear statistical interpretation for HITS, this result suggests to rely on existing work already published in the multivariate statistical analysis literature (extensions of PCA or correspondence analysis) in order to analyse or design new Web pages scoring procedures.

We show that Kleinberg's hubs and authorities model is closely related to both correspondence analysis, a well-known multivariate statistical technique, and a particular Markov chain model of navigation through the Web. The only difference between correspondence analysis and Kleinberg's method is the use of the average value of the hubs (authorities) scores for computing the authorities (hubs) scores, instead of the sum for Kleinberg's method. We also show that correspondence analysis and our Markov model are related to SALSA, a variant of Kleinberg's model.