Customer Interaction Networks (CINs) are a natural framework for representing and mining customer interactions with E-Commerce search engines. Customer interactions begin with the submission of a query formulated based on an initial product intent, followed by a sequence of product engagement and query reformulation actions. Engagement with a product (e.g. clicks) indicates its relevance to the customer»s product intent. Reformulation to a new query indicates either dissatisfaction with current results, or an evolution in the customer»s product intent. Analyzing such interactions within and across sessions, enables us to discover various query-query and query-product relationships. In this work, we begin by studying the properties of CINs developed using Walmart.com»s product search logs. We observe that the properties exhibited by CINs make it possible to mine intent relationships between queries based purely on their structural information. We show how these relations can be exploited for a) clustering queries based on intents, b) significantly improve search quality for poorly performing queries, and c) identify the most influential (aka. »critical») queries whose performance have the highest impact on performance of other queries.