Using hypergraphs to improve product retrieval

Augmenting query-product graphs with hypergraphs describing product-product relationships improves recall score by more than 48%.

Information retrieval engines like the one that helps Amazon customers find products in the Amazon Store commonly rely on bipartite graphs that map queries to products. The graphs are typically based on customer behaviors: if enough customers executing the same query click the link to a product or buy that product, the graph will include an edge between query and product. A graph neural network (GNN) can then ingest the graph and predict edges corresponding to new queries.

This approach has two drawbacks. One is that most products in the Amazon Store belong to the long tail of items that are rarely searched for, which means that they don’t have enough associated data to make GNN training reliable. Conversely, when handling long-tail queries, a GNN will tend to match them to popular but probably unrelated products, simply because they have a high click and purchase rate overall. This phenomenon is known as disassortative mixing.

Related content
Dual embeddings of each node, as both source and target, and a novel loss function enable 30% to 160% improvements over predecessors.

In a paper we presented at the ACM Conference on Web Search and Data Mining (WSDM), we address both of these problems by augmenting the bipartite query-product graph with information about which products customers tend to look at during the same online shopping sessions. The idea is that knowing which types of products are related to each other can help the GNN generalize from high-frequency to low-frequency queries.

To capture the information about product relationships, we use a hypergraph, a generalization of the graph structure; where an edge in an ordinary graph links exactly two nodes, an edge in a hypergraph can link multiple nodes. Other information retrieval approaches have used product similarity to improve performance, but modeling product similarity with the hypergraph allows us to use GNNs for prediction, so we can exploit the added structure available in graph representations of data.

In tests, we compared our approach to one that uses GNNs on a bipartite graph only and found that the addition of the hypergraph improved the mean reciprocal rank of the results, which assigns a higher score the closer the correct answer is to the top of a ranked list, by almost 25% and the recall score, which measures the percentage of correct answers retrieved, by more than 48%.

Two-channel architecture

GNNs produce vector representations, or embeddings, of individual graph nodes that capture information about their neighbors. The process is iterative: the first embedding captures only information about the object associated with the node — in our case, product descriptions or query semantics. The second embedding combines the first embedding with those of the node’s immediate neighbors; the third embedding extends the node’s neighborhood by one hop; and so on. Most applications use one- or two-hop embeddings.

Related content
Using reinforcement learning improves candidate selection and ranking for search, ad platforms, and recommender systems.

The embedding of a hypergraph modifies this procedure slightly. The first iteration, as in the standard case, embeds each of the item nodes individually. The second iteration creates an embedding for the entirety of each hyperedge. The third iteration then produces an embedding for each node that factors in both its own content-level embedding and the embeddings of all the hyperedges it touches.

The architecture of our model has two channels, one for the query-item bipartite graph and one for the item-item hypergraph. Each passes to its own GNN (a graph convolution network), yielding an embedding for each node.

Hypergraph search.jpeg
An overview of the hypergraph-augmented product retrieval method.

During training, an attention mechanism learns how much weight to give the embedding produced by each channel. A common query with a few popular associated products, for instance, may be well represented by the standard GNN embedding of the bipartite graph. A rarely purchased item, by contrast, associated with a few diverse queries, may benefit from greater weighting of the hypergraph embedding.

Related content
Locality-sensitive hashing enables cache to hold more than three times as many query results.

To maximize the quality of our model’s predictions, we also experimented with two different unsupervised pretraining methods. One is a contrastive-learning approach in which the GNN is fed pairs of training examples. Some are positive pairs, whose embeddings should be as similar as possible, and some are negative pairs, whose embeddings should be as different as possible.

Following existing practice, we produce positive pairs by randomly deleting edges or nodes of a source graph, so the resulting graphs are similar but not identical. Negative pairs pair the source graph with a different, random graph. We extend this procedure to the hypergraph and ensure consistency between the two channels’ training data; e.g., a node deleted from one channel’s inputs will also be deleted from the other channel’s.

Related content
Information extraction, drug discovery, and software analysis are just a few applications of this versatile tool.

We also experiment with DropEdge, a procedure in which, in successive training epochs, slightly different versions of the same graph are used, with a few edges randomly dropped. This prevents overfitting and oversmoothing, as it encourages the GNN to learn more abstract representations of its inputs.

Pretraining dramatically improves the quality of both our two-channel model and the baseline GNN. But it also increases the discrepancy between the two. That is, our approach by itself sometimes yields only a modest improvement over the baseline model. But our approach with pretraining outperforms the baseline model with pretraining by a larger margin.

Related content

US, VA, Herndon
Do you love decomposing problems to develop machine learning (ML) products that impact millions of people around the world? Would you enjoy identifying, defining, and building ML software solutions that revolutionize how businesses operate? The Global Practice Organization in Professional Services at Amazon Web Services (AWS) is looking for a Software Development Engineer II to build, deliver, and maintain complex ML products that delight our customers and raise our performance bar. You’ll design fault-tolerant systems that run at massive scale as we continue to innovate best-in-class services and applications in the AWS Cloud. Key job responsibilities Our ML Engineers collaborate across diverse teams, projects, and environments to have a firsthand impact on our global customer base. You’ll bring a passion for the intersection of software development with generative AI and machine learning. You’ll also: - Solve complex technical problems, often ones not solved before, at every layer of the stack. - Design, implement, test, deploy and maintain innovative ML solutions to transform service performance, durability, cost, and security. - Build high-quality, highly available, always-on products. - Research implementations that deliver the best possible experiences for customers. A day in the life As you design and code solutions to help our team drive efficiencies in ML architecture, you’ll create metrics, implement automation and other improvements, and resolve the root cause of software defects. You’ll also: - Build high-impact ML solutions to deliver to our large customer base. - Participate in design discussions, code review, and communicate with internal and external stakeholders. - Work cross-functionally to help drive business solutions with your technical input. - Work in a startup-like development environment, where you’re always working on the most important stuff. About the team The Global Practice Organization for Analytics is a team inside the AWS Professional Services Organization. Our mission in the Global Practice Organization is to be at the forefront of defining machine learning domain strategy, and ensuring the scale of Professional Services' delivery. We define strategic initiatives, provide domain expertise, and oversee the development of high-quality, repeatable offerings that accelerate customer outcomes. Inclusive Team Culture Here at AWS, we embrace our differences. We are committed to furthering our culture of inclusion. We have thirteen employee-led affinity groups, reaching 85,000 employees in over 190 chapters globally. We have innovative benefit offerings, and host annual and ongoing learning experiences, including our Conversations on Race and Ethnicity (CORE) and AmazeCon (gender diversity) conferences. Amazon’s culture of inclusion is reinforced within our 16 Leadership Principles, which remind team members to seek diverse perspectives, learn and be curious, and earn trust. Work/Life Balance Our team puts a high value on work-life harmony. Striking a healthy balance between your personal and professional life is crucial to your happiness and success here. We are a customer-obsessed organization—leaders start with the customer and work backwards. They work vigorously to earn and keep customer trust. As such, this is a customer facing role in a hybrid delivery model. Project engagements include remote delivery methods and onsite engagement that will include travel to customer locations as needed. Mentorship & Career Growth Our team is dedicated to supporting new members. We have a broad mix of experience levels and tenures, and we’re building an environment that celebrates knowledge sharing and mentorship. We care about your career growth and strive to assign projects based on what will help each team member develop into a better-rounded professional and enable them to take on more complex tasks in the future. This is a customer-facing role and you will be required to travel to client locations and deliver professional services as needed. We are open to hiring candidates to work out of one of the following locations: Atlanta, GA, USA | Austin, TX, USA | Boston, MA, USA | Chicago, IL, USA | Herndon, VA, USA | Minneapolis, MN, USA | New York, NC, USA | San Diego, CA, USA | San Francisco, CA, USA | Seattle, WA, USA
US, MA, North Reading
Are you inspired by invention? Is problem solving through teamwork in your DNA? Do you like the idea of seeing how your work impacts the bigger picture? Answer yes to any of these and you’ll fit right in here at Amazon Robotics. We are a smart team of doers that work passionately to apply cutting edge advances in robotics and software to solve real-world challenges that will transform our customers’ experiences in ways we can’t even imagine yet. We invent new improvements every day. We are Amazon Robotics and we will give you the tools and support you need to invent with us in ways that are rewarding, fulfilling and fun. Amazon Robotics is seeking Applied Science Interns and Co-ops with a passion for robotic research to work on cutting edge algorithms for robotics. Our team works on challenging and high-impact projects within robotics. Examples of projects include allocating resources to complete a million orders a day, coordinating the motion of thousands of robots, autonomous navigation in warehouses, identifying objects and damage, and learning how to grasp all the products Amazon sells. As an Applied Science Intern/Co-op at Amazon Robotics, you will be working on one or more of our robotic technologies such as autonomous mobile robots, robot manipulators, and computer vision identification technologies. The intern/co-op project(s) and the internship/co-op location are determined by the team the student will be working on. Please note that by applying to this role you would be considered for Applied Scientist summer intern, spring co-op, and fall co-op roles on various Amazon Robotics teams. These teams work on robotics research within areas such as computer vision, machine learning, robotic manipulation, navigation, path planning, perception, optimization and more. Learn more about Amazon Robotics: https://amazon.jobs/en/teams/amazon-robotics We are open to hiring candidates to work out of one of the following locations: North Reading, MA, USA | Seattle, WA, USA | Westborough, MA, USA
CA, BC, Vancouver
Amazon Web Services (AWS) is building a world-class marketing organization that drives awareness and customer engagement with the goal of educating developers, IT and line-of-business professionals, startups, partners, and executive decision makers about AWS services and solutions, their benefits, and differentiation. As the central data and science organization in AWS Marketing, the Data: Science and Engineering (D:SE) team builds measurement products, AI/ML models for targeting, and self-service insights capabilities for AWS Marketing to drive better measurement and personalization, improve data access and analytical self-service, and empower strategic data-driven decisions. We work globally as a central team and establish standards, benchmarks, and best practices for use throughout AWS Marketing. We are looking for a Principal Data Scientist with deep expertise in scaling measurement science, content ranking and rapid experimentation at scale, with strong interest in building scalable solutions in partnership with our engineering organization. You will lead strategic measurement science initiatives across AWS Marketing & Sales ranging anywhere between recommender engines, scaling experimentation and measurement science, real-time inference, and cross-channel orchestration. You are an hands-on innovator who can contribute to advancing Marketing measurement technology in a B2B environment, and push the limits on what’s scientifically possible with a razor sharp focus on measurable customer and business impact. You will work with recognized B2B Marketing Science and AI/ML experts to develop large-scale, high-performing measurement science models and AI/ML capabilities. We are at a pivotal moment in our organization where AI/ML and measurement velocity has reached an unseen momentum, and we need to scale fast in order to maintain it. Your work will be a key input into a few of our key business goals. You will advance the state of the art in measurement at scale. We are open to hiring candidates to work out of one of the following locations: Vancouver, BC, CAN
US, WA, Seattle
Innovators wanted! Are you an entrepreneur? A builder? A dreamer? This role is part of an Amazon Special Projects team that takes the company’s Think Big leadership principle to the extreme. We focus on creating entirely new products and services with a goal of positively impacting the lives of our customers. No industries or subject areas are out of bounds. If you’re interested in innovating at scale to address big challenges in the world, this is the team for you. Here at Amazon, we embrace our differences. We are committed to furthering our culture of inclusion. We have thirteen employee-led affinity groups, reaching 40,000 employees in over 190 chapters globally. We are constantly learning through programs that are local, regional, and global. Amazon’s culture of inclusion is reinforced within our 16 Leadership Principles, which remind team members to seek diverse perspectives, learn and be curious, and earn trust. Our team highly values work-life balance, mentorship and career growth. We believe striking the right balance between your personal and professional life is critical to life-long happiness and fulfillment. We care about your career growth and strive to assign projects and offer training that will challenge you to become your best. Key job responsibilities • Develop automated laboratory workflows. • Perform data QC, document results, and communicate to stakeholders. • Maintain updated understanding and knowledge of methods. • Identify and escalate equipment malfunctions; troubleshoot common errors. • Participate in the updating of protocols and database to accurately reflect the current practices. • Maintain equipment and instruments in good operating condition • Adapt to unexpected schedule changes and respond to emergency situations, as needed. We are open to hiring candidates to work out of one of the following locations: Seattle, WA, USA
US, WA, Seattle
Are you excited about developing generative AI and foundation models to revolutionize automation, robotics and computer vision? Are you looking for opportunities to build and deploy them on real problems at truly vast scale? At Amazon Fulfillment Technologies and Robotics we are on a mission to build high-performance autonomous systems that perceive and act to further improve our world-class customer experience - at Amazon scale. We are looking for scientists, engineers and program managers for a variety of roles. The Amazon Robotics software team is seeking a Applied Scientist to focus on large vision and manipulation machine learning models. This includes building multi-viewpoint and time-series computer vision systems. It includes using machine learning to drive hardware movement. It includes building large-scale models using data from many different tasks and scenes. This work spans from basic research such as cross domain training, to experimenting on prototype in the lab, to running wide-scale A/B tests on robots in our facilities. Key job responsibilities * Research vision - Where should we be focusing our efforts * Research delivery – Proving/dis-proving strategies in offline data or in the lab * Production studies - Insights from production data or ad-hoc experimentation. About the team This team invents and runs robots focused on grasping and packing items. These are typically 6-dof style robotic arms. Our work ranges from the long-term-research on basic science to deploying/supporting large production fleets handling billions of items per year. We are open to hiring candidates to work out of one of the following locations: Seattle, WA, USA
US, VA, Arlington
Amazon launched the Generative AI (GenAI) Innovation Center (GAIIC) in Jun 2023 to help AWS customers accelerate enterprise innovation and success with Generative AI (https://press.aboutamazon.com/2023/6/aws-announces-generative-ai-innovation-center). Customers such as Highspot, Lonely Planet, Ryanair, and Twilio are engaging with the GAI Innovation Center to explore developing generative solutions. GAIIC provides opportunities to innovate in a fast-paced organization that contributes to game-changing projects and technologies that get deployed on devices and in the cloud. As a data scientist at GAIIC, you are proficient in designing and developing advanced Generative AI based solutions to solve diverse customer problems. You will be working with terabytes of text, images, and other types of data to solve real-world problems through Gen AI. You will be working closely with account teams and ML strategists to define the use case, and with other scientists and ML engineers on the team to design experiments, and find new ways to deliver value to the customer. The successful candidate will possess both technical and customer-facing skills that will allow you to be the technical “face” of AWS within our solution providers’ ecosystem/environment as well as directly to end customers. You will be able to drive discussions with senior technical and management personnel within customers and partners. This position requires that the candidate selected be a US Citizen and currently possess and maintain an active Top Secret security clearance. About the team Work/Life Balance Our team puts a high value on work-life balance. It isn’t about how many hours you spend at home or at work; it’s about the flow you establish that brings energy to both parts of your life. We believe striking the right balance between your personal and professional life is critical to life-long happiness and fulfillment. We offer flexibility in working hours and encourage you to find your own balance between your work and personal lives. Mentorship & Career Growth Our team is dedicated to supporting new members. We have a broad mix of experience levels and tenures, and we’re building an environment that celebrates knowledge sharing and mentorship. Our senior members enjoy one-on-one mentoring and thorough, but kind, code reviews. We care about your career growth and strive to assign projects based on what will help each team member develop into a better-rounded engineer and enable them to take on more complex tasks in the future. We are open to hiring candidates to work out of one of the following locations: Arlington, VA, USA | Denver, CO, USA
US, VA, Arlington
Amazon’s mission is to be the most customer centric company in the world. The Workforce Staffing (WFS) organization is on the front line of that mission by hiring the hourly fulfillment associates who make that mission a reality. To drive the necessary growth and continued scale of Amazon’s associate needs within a constrained employment environment, Amazon has created the Workforce Intelligence (WFI) team. This team will (re)invent how Amazon attracts, communicates with, and ultimately hires its hourly associates. This team owns multi-layered research and program implementation to drive deep learning, process improvements, and strategic recommendations to global leadership. Are you passionate about data? Do you enjoy questioning the status quo? Do complex and difficult challenges excite you? If yes, this may be the team for you. The Data Scientist will be responsible for creating cutting edge algorithms, predictive and prescriptive models as well as required data models to facilitate WFS at-scale warehouse associate hiring. This role acts as an internal consultant to the marketing, biz ops and candidate experience teams covering responsibilities such as at-scale hiring process improvement, analyzing large scale candidate/associate data and being strategic to providing best candidate hiring experience to WFS warehouse associate candidates. We are open to hiring candidates to work out of one of the following locations: Arlington, VA, USA
US, WA, Seattle
Innovators wanted! Are you an entrepreneur? A builder? A dreamer? This role is part of an Amazon Special Projects team that takes the company’s Think Big leadership principle to the extreme. We focus on creating entirely new products and services with a goal of positively impacting the lives of our customers. No industries or subject areas are out of bounds. If you’re interested in innovating at scale to address big challenges in the world, this is the team for you. Here at Amazon, we embrace our differences. We are committed to furthering our culture of inclusion. We have thirteen employee-led affinity groups, reaching 40,000 employees in over 190 chapters globally. We are constantly learning through programs that are local, regional, and global. Amazon’s culture of inclusion is reinforced within our 16 Leadership Principles, which remind team members to seek diverse perspectives, learn and be curious, and earn trust. Our team highly values work-life balance, mentorship and career growth. We believe striking the right balance between your personal and professional life is critical to life-long happiness and fulfillment. We care about your career growth and strive to assign projects and offer training that will challenge you to become your best. We are open to hiring candidates to work out of one of the following locations: Seattle, WA, USA
US, CA, Sunnyvale
Are you passionate about solving unique customer-facing problem at Amazon scale? Are you excited by developing and productionizing machine learning, deep learning algorithms and leveraging tons of Amazon data to learn and infer customer shopping patterns? Do you enjoy working with a diverse set of engineers, machine learning scientists, product managers and user-experience designers? If so, you have found the right match! Virtual Try On (VTO) at Amazon Fashion & Fitness is looking for an exceptional Applied Scientist to join us to build our next generation virtual try on experience. Our goal is to help customers evaluate how products will fit and flatter their unique self before they ship, transforming customers' shopping into a personalized journey of inspiration, discovery, and evaluation. In this role, you will be responsible for building scalable computer vision and machine learning (CVML) models, and automating their application and expansion to power customer-facing features. Key job responsibilities - Tackle ambiguous problems in Computer Vision and Machine Learning, and drive full life-cycle of CV/ML projects. - Build Computer Vision, Machine Learning and Generative AI models, perform proof-of-concept, experiment, optimize, and deploy your models into production. - Investigate and solve exciting and difficult challenges in Image Generation, 3D Computer Vision, Generative AI, Image Understanding and Deep Learning. - Run A/B experiments, gather data, and perform statistical tests. - Lead development and productionalization of CV, ML, and Gen AI models and algorithms by working across teams. Deliver end to end. - Act as a mentor to other scientists on the team. We are open to hiring candidates to work out of one of the following locations: Sunnyvale, CA, USA
US, CA, Sunnyvale
At Amazon Fashion, we are obsessed with making Amazon Fashion the most loved fashion destinations globally. We're searching for Computer Vision pioneers who are passionate about technology, innovation, and customer experience, and who are enthusiastic about making a lasting impact on the industry. You'll be working with talented scientists, engineers, and product managers to innovate on behalf of our customers. If you're fired up about being part of a dynamic, driven team, then this is your moment to join us on this exciting journey and change the world of eCommerce forever Key job responsibilities As a Applied Scientist, you will be at the forefront to define, own and drive the science that span multiple machine learning models and enabling multiple product/engineering teams and organizations. You will partner with product management and technical leadership to identify opportunities to innovate customer facing experiences. You will identify new areas of investment and work to align product roadmaps to deliver on these opportunities. As a science leader, you will not only develop unique scientific solutions, but more importantly influence strategy and outcomes across different Amazon organizations such as Search, Personalization and more. This role is inherently cross-functional and requires a strong ability to communicate, influence and earn the trust of software engineers, technical and business leadership. We are open to hiring candidates to work out of one of the following locations: Sunnyvale, CA, USA