Information overload on the Web has created enormous challenges to customers selecting products for online purchases and to online businesses attempting to identify customers' preferences efficiently. Various recommender systems employing different data representations and recommendation methods are currently used to address these challenges. In this research, we developed a graph model that provides a generic data representation and can support different recommendation methods. To demonstrate its usefulness and flexibility, we developed three recommendation methods: direct retrieval, association mining, and high-degree association retrieval. We used a data set from an online bookstore as our research test-bed. Evaluation results showed that combining product content information and historical customer transaction information achieved more accurate predictions and relevant recommendations than using only collaborative information. However, comparisons among different methods showed that high-degree association retrieval did not perform significantly better than the association mining method or the direct retrieval method in our test-bed. The large amount of product information on the Web presents great challenges to both customers and online businesses in the e-commerce environment. Customers frequently experience difficulty in searching for products on the Web, while online businesses are often overwhelmed by the rich data they have collected and find it difficult to promote products appropriate to specific customers. Overload of product and transaction information on the Web raises a practical question: How can the large amount of product and usage information available from online transactions be effectively utilized to support better decisionmaking by both buyers and sellers? To deal with this information overload problem, researchers have proposed recommender systems that automatically analyze users' usage data to filter Web page content, categorize newsgroup messages, and recommend good information resources (Resnick & Varian, 1997) . Typically, a recommender system analyzes data about items 1 or about interactions between users and items to find associations among items and users. The results obtained are presented as recommendations. Using this concept, some online businesses, such as Amazon.com and eBay.com, have used recommender systems as a business tool. Such systems are reported to have enhanced e-commerce sales by converting browsers to buyers, increasing cross-selling and building customer loyalty (Schafer, Konstan, & Riedl, 2001) . In this article, we review previous research in recommender systems to identify frequently used approaches and representations. Four recommendation approaches were examined: knowledge engineering, collaborative filtering, a content-based approach, and a hybrid approach. Different recommendation approaches can be implemented using different analytical methods. Commonly used methods are neighborhood formation, association rule mining, machine learning techniques, etc. Recommender system developers often face two challenges. One is how to represent diverse information about the users and items. The other is how to build a model that is flexible enough to incorporate different recommendation approaches. We propose a graph model to represent the user-product information. The graph model contains nodes (customers and products) and links (transactions and similarities) that capture various types of e-commerce information. The model also supports different recommendation approaches. To demonstrate its flexibility, we have developed three analysis methods that cover a wide range of commonly used and newly introduced recommendation methods: direct retrieval, association mining, and highdegree association retrieval. With three methods all developed using a common model, we were able to obtain direct comparisons of performances of different recommendation methods under the three approaches of the collaborative Received February 19, 2003; revised August 13, 2003 filtering, content-based, and hybrid approaches. We used a Chinese online bookstore as our test-bed to implement a recommender system based on the model and methods we developed. A systematic empirical evaluation was conducted and results were summarized. Initial results on the graph model and the high-degree association retrieval methods have been reported in a recent conference publication (Huang, Chung, Ong, & Chen, 2002) . Recommender systems assist users in choosing appropriate information items or products from a large set of alternatives. In such systems, personalized recommendations on items (information, products, or services) are generated by predicting preferences of users. While "recommender system" is viewed as a synonym of "retrieval system" by some researchers (Furner, 2002) , we argue that recommender systems are distinguished from typical retrieval systems by emphasizing the modeling of the user characteristics and user-item interactions in the system. In recommender systems, latent user preferences are assumed to be indicated by a wide range of observable data: features of the user, features of the items purchased by the user, behavior of users with (estimated) similar preferences, etc. The goal of recommender systems is to estimate such latent user preferences and provide predictions of appropriate items to specific users. Traditional retrieval systems typically focused on providing relevant information items that correspond to the explicit form of user preferences (i.e., queries) and did not emphasize the modeling of latent user preferences. Recommender systems can be implemented to enhance traditional retrieval systems, while also covering a wide range of new application areas, especially in the e-commerce environment. Since the first recommender system was developed a decade ago (Goldberg, Nichols, Oki, & Terry, 1992) , various techniques have been employed in various applicationspecific recommender systems. Early recommender systems helped users to sift through a large number of documents like Usenet news articles or Web pages. With the recent proliferation of e-commerce, recommender systems have become a powerful business tool to enhance customers' capability to overcome the product information overload problem. In this section, we summarize the literature and propose a taxonomy of recommender systems that characterizes a typical recommender system in three major dimensions: system input, data representation, and recommendation approach. The input of a recommender system can take three forms: (1) user factual data such as name, gender, and address; (2) transactional data captured through users' explicit ratings or implicit feedback observed from their behaviors; and (3) item factual data such as product brand and price. Many recommender systems have employed users' explicit feedback in the form of ratings (Balabanovic & Shoham, 1997; Basu, Hersh, & Cohen, 1998; Claypool et al., 1999; Condliff, Lewis, Madigan, & Posse, 1999; Mooney & Roy, 2000; Passani & Billsus, 1997; Sarwar et al., 1998; Terveen, Hill, Amento, Mcdonald, & Creter, 1997) . For example, Syskills and Webert used user ratings of a Web page as input data (Passani & Billsus, 1997). Basu et al. (1998) employed user ratings on movies as input to their system. This method suffers from the cold-start problem, in which newly released products may get only a few ratings and hence not be recommended even if they are relevant. To overcome this problem, some systems also have used implicit feedback obtained during the user's usage session. The system analyzes system logs to find users' preferences. Existing recommender systems use different kinds of data representations that usually capture three basic elements in a recommender system-user representation, item representation, and transaction representation. User information can be represented in four ways: (1) by user attributes (usually demographic data such as gender, birth date, salary, etc.), (2) by associated items (e.g., the products the user has expressed interest in, has given ratings to or actually purchased), (3) by transactions (attributes extracted from the user's transaction history such as time, frequency, and amount, can partially represent a user's behavior pattern), or (4) by item attributes (e.g., a user may be characterized as liking romantic stories and favoring low prices based on the attributes of the books she has purchased). Most recommender systems represent users as a set of associated items; Basu et al., 1998; Claypool et al., 1999; Condliff et al., Fu, Budzick, & Hammond, 2000; Lieberman, 1995; Mladenic, 1996; Pazzani, 1999; Passani & Billsus, 1997; Sarwar et al., 1998; Shwab, Phol, & Koychev, 2000). For example, systems like Fab (Balabanovic & Shoham, 1997), Personalized Tango (Claypool et al., 1999) , SurfLen (Fu et al., 2000), and Personalized WebWatcher (Mladenic, 1996) used Web pages the user had rated or previously visited to represent the user, whereas systems like GroupLens (Sarwar et al., 1998) used movies and books to represent the user interests. As another important element in recommender systems, items are usually represented by item attributes (such as price, content, brand, etc.) or by associated users (e.g., the customers who have purchased this item before). Some recommender systems also use transactions as a basic element, usually representing them by the transaction attributes (such as time, amount, etc.) or by items in the transactions. Researchers have also included some transaction attributes such as time and place as additional dimensions and support a different type of recommendation that may be based on different combinations of dimensions, such as the recommendation of Web content to a particular customer on weekends, or the recommendation of the best time to promote certain products to a particular customer (Adomavicius & Tuzhilin, 2001). However, most existing recommender systems focus on the analysis of the two dimensions of users and items. collaborative filtering, content-based, and hybrid approaches. The knowledge engineering approach seeks to discover the factors that affect users' preferences in choosing products. Significant human effort is needed to make this approach work. For example, Expertise Recommender (McDonald & Ackerman, 2000) recommends software engineering expertise to programmers using heuristics based on version change history and technical support records. The heuristics were created using the results obtained from a 5-month ethnographic study. Message filtering systems and document management systems have been using such a rule-based approach extensively. ISCREEN (Polloc, 1988) , an early work in this area, used user-defined rules to screen text messages. The rules were personalized for each user, and the rules were mainly based on content and attributes of text messages (such as sender, length, highlights, etc.). The knowledge engineering approach can generate user-specific rules for recommendation purposes based on a wide range of information including item features, user features, and other domain-specific information. The major difference between this approach and the following approaches is that the process of generating such rules is not automated and extensive human effort is typically required. The collaborative filtering approach obtains general collaborative information from users to form aggregate rules or trends as well as associations among users and/or items to predict the interest of individual users. An example is the movie recommendation, in which customer ratings on movies were used to recommend films to specific users. . User-based collaboration uses historical data to form user neighborhoods. For example, Pazzani (1999) formed a neighborhood of similar users based on their expressed preferences and recommended restaurants based on the neighborhood relationship. Itembased collaborative recommendation relies on associations among items to determine recommendations. These associations are based on historical interactions between items and users, such as copurchase or preference by the same customer. Existing e-commerce recommender systems usually use this technique in applications such as gift recommendation (Schafer et al., 2001 ). Other collaborative recommender systems have used the user-item pair as the basis of the analysis, rather than just one of them. In some systems where the identity of the user is not available, collaborative filtering also can be applied on the basis of transactions. Several analysis techniques, including neighborhood formation, association rule mining, and machine learning techniques, typically have been applied to generate recommendations. Neighborhoods were formed by using similarity functions such as cosine-based similarity and correlationbased similarity functions and clustering techniques (Mobasher et al., 2000; Nasraoui et al. 1999; Sarwar et al., 2001 ). Association rule mining was used to extract patterns of association among items and users from the transaction history (Fu et al., 2000) . Machine learning techniques were also applied to discover patterns from transactional data (Basu et al., 1998; Pazzani & Billsus, 1997) . However, collaborative filtering does not work well when a product is newly introduced or a user just starts to use the system, because the system does not have much rating information on either the product or the user (the "cold-start problem"). Also, when there are many items but relatively few users, collaborative filtering cannot provide a good recommendation simply because there are few ratings (the "sparsity problem"). Furthermore, some users with opinions consistently different from the group opinions do not benefit from collaborative filtering (the "gray sheep problem") (Claypool et al., 1999) . The content-based approach borrows techniques from information retrieval to analyze the content of items. Neighborhood functions (Claypool et al., 1999; Liberman, 1995; Mladenic, 1996) and classification techniques (Mooney & Roy, 2000; Mostafa, Mukhopadhyay, Lan, & Palakal, 1997) often have been applied to analyze and cluster the textual content of items and recommendations are generated based on matching between item characteristics and user profiles. Although some systems have explored very comprehensive item representations [for example, Watters and Wang (2000) proposed a news object representation that consisted of a rich set of header, content, and behavior attributes for online news article recommendation], the content-based approach has several fundamental limitations. It captures only partial information on item characteristics, usually textual information. Other content information such as audio or visual content is usually ignored. This approach tends to recommend only items with similar characteristics (also known as the "over-specification problem"). Only the target user's feedback is used in this approach, although that user's interest may also be influenced by other users' preferences (Balabanovic & Shoham, 1997) . To improve the quality of recommendation, many efforts have been made to combine content-based and collaborative approaches to implement a hybrid approach. Recommender systems using a hybrid approach can be loosely categorized into three classes. Systems in the first category try to integrate the two approaches by simply merging the two recommendation results separately generated by content-based and collaborative approaches (Claypool et al., 1999) . Systems in the second category combine the two approaches at the representation level, in which product information and transaction information are incorporated into a single representation. Some of these systems have been based on collaborative filtering and added content information of items into the user representation or added ratings based on content of the items (Pazzani, 1999; Sarwar et al., 1998; Singh, Yu, & Venkatraman, 2001 ). For example, Fab maintained user profiles based on content analysis of documents rated by users. It then compared user profiles to identify similar users to generate a collaborative recommendation Balabanovic & Shoham, 1997) . Others tried to apply content-based analysis and added user information into the item representation (Goldberg et al., 1992) . Some other systems have been built on a comprehensive model that incorporated different information sources (Basu et al., 1998; Condliff et al., 1999) . Recent work by Ansari, Essegaier, and Kohli (2000) has adopted the formal statistical approach to model the user ratings as a function of item attributes, user characteristics, and expert evaluations. Unobserved sources of heterogeneity in user preference and item appeal structures were accounted for using this approach. Systems in the third category of hybrid approach use knowledge engineering in addition to collaborative filtering. For example, Burke proposed a hybrid recommendation framework in which collaborative filtering was used to postfilter the recommendation results obtained by the knowledge-based filtering method (Burke, 2000) . Table 1 presents the taxonomy of recommender systems described above. We summarize in the table the types of system input, representation methods, and recommendation approaches used in existing recommender systems. Several systems in the literature are listed in Table 2 and are characterized in Table 3 under the dimensions introduced in the taxonomy. We found that most of the recommender systems used the collaborative filtering approach to generate recommendations. Also, the methods used in these systems were largely application-specific. This limited the data inputs and representations that could be used. We believe that a model not only needs to be comprehensive enough to support diverse inputs and representations but also flexible enough to support different recommendation approaches. To address the needs of comprehensive representation and to support flexible recommendation approaches, we propose a graph model for building e-commerce recommender systems. Two recent works on recommender systems propose graph-theoretic models or approaches. Aggarwal, Wolf, Wu, and Yu (1999) introduced a directed graph of users in recommender systems, where the directed edges correspond to the notion of predictability. Based on this graph, personalized recommendations can be generated via a few reasonably short (strongly predictable) directed paths joining multiple users. Mirza (2001) also proposed a graph-theoretic model for collaborative filtering, in which items and users are both represented as nodes and the edges represent the recommendation data set (interaction between user and items). A social network graph of users is then created based on the original graph, and recommendations are generated by navigating the combination of the original graph and user social network graph. While similar to these previous graphtheoretic models in some aspects, the model we are proposing focuses more on providing a unifying representation for the various types of system inputs summarized in the taxonomy presented previously. Flexible recommendation approaches are also to be explored using such a graph model. In the following section, we first describe the model and then analyze its properties and application. As we are focusing on e-commerce recommender systems, we will discuss products (instead of items) and customers (instead of users) in the following sections. Figure 1 shows a two-layer graph model, in which the two layers of nodes represent products and customers, respectively. Three types of links between nodes capture the input information: the product information, customer information, and transaction information. Each link between two products captures similarity between them. Different types of product information can be used to compute the similarity. For products like books and movies, content of the product description (book introductions, movie reviews) can also be used to compute product similarity. Similarly, each link between two customers captures the similarity between them. The large amount of customer demographic data available at e-commerce sites can be used to compute customer similarity. Other information about customers may also be added, such as customers' answers to questionnaires, query inputs, Web usage patterns and so on. Interlayer links are formed based on the transaction information that captures the associations between customers and products. Some commonly used transaction information includes purchase history, customers' rating, or browsing behavior that involves the product. Each purchase of a product by a customer is represented by an interlayer link in our model. Different types of transaction information may be combined in the model by assigning different weights to reflect different association strengths. For example, a high rating on a product may be weighted higher than a browsing activity, because the former reflects the customer's interest more directly. The literature review showed that the field of recommender systems calls for a comprehensive and generic model. This model should have the capability to represent different types of data inputs and to support different recommendation approaches using various techniques. Here we show how our two-layer graph model meets these requirements. We first analyze the properties of our model and introduce three recommendation methods we have developed to show the usefulness and flexibility of the model. The major difference between the representation in our model and other representations is that our model requires transformation of the original input data, such as product and customer attributes, into similarity measures. Others have used the original input data itself as
For example, two-layer graph model in the context of book recommendation is described in REF , where the authors propose a graph-based recommendation approach to integrate the CBF approach along with CF approach in the context of digital libraries by representing books and users as nodes.
A Graph Model for E-Commerce Recommender Systems
Journal of the American Society for Information Science and Technology
Computer Science