GatewayNet: a form of sequential rule mining

This hypothesis is controversial amongst substance abuse experts, as many studies with conflicting results have been released since intense interest beginning in the 1970s. For instance, Kandel originally predicted a chain of drug use progression from tobacco and alcohol to cannabis, then to LSD, amphetamines, or heroin. She posits that this association is bidirectional and that a similar sequence will occur for regression in drug use [1]. In 1984, a follow-up was performed to address the fact that detailed monitoring of adolescents into young adulthood, suggesting that initiation risk may be partially conditional on age and that risk progresses in stages [2]. At the height of the crack cocaine epidemic, Kandel and Yamaguchi reformed their model to account for its sudden appearance and found that a) cocaine precedes crack cocaine, and b) models using cocaine or crack cocaine exclusively had a poorer fit than those containing both [3].

O’Donnell and Clayton directly claimed a causal connection between marijuana and heroin use [4]. To support this, they note that marijuana and heroin are statistically associated, that marijuana precedes heroin use, and that this association is not spurious. O’Donnell and Clayton alleged that a large cohort of sociologists were skeptical of the gateway hypothesis at the time, and they argued that marijuana causes heroin use according to how sociologists understand causation [4].

Early criticism of causal predictions of the gateway hypothesis takes two major forms: that the evidence does not support the assertion or that the assertion is structurally flawed. In an attempt to replicate Kandel’s work, Baumrind obtained a different pathway which implicated that tobacco succeeded cannabis (though both found that the use of socially-accepted substances precedes that of the unacceptable), noting that drug initiation order may be influenced by sociocultural aspects [5].

An additional form of criticism arose in the way that the conclusion itself was being formulated. In an article warning against drawing false conclusions of causation, Baumrind cites O’Donnell and Clayton as an exemplar of this [6]; she later comments that Guttman scales cannot be extrapolated into a sequence of development stages as was done in Kandel’s work [5]. Vanyukov et al. argue that the gateway hypothesis may lack falsifiability and that the concept itself is vague [7].

Nonetheless, contemporary support of the gateway hypothesis is mixed. It is known that rats exposed to Δ9-tetrahydrocannabinol (THC, the primary active compound in cannabis) will increase self-administration of nicotine, heroin, and morphine [8‐10], showing that cannabis can operate as a gateway drug outside of any particular cultural context. Conversely, it has been argued that the apparent progression is one of several, and that common liability to addiction may be enough to explain patterns in substance use [7]. One longitudinal study of New Zealand children concluded that although there was strong association with a diverse use of other drugs and that this may support a causal model, the underlying causal mechanisms are not well understood [11].

There are two major approaches involving longitudinal data used to assess drug use in human subjects: through self-reporting and through urine drug screening (UDS). In self-reporting studies, subjects are asked to inform investigators about their drug history. This method frequently tracks subjects from adolescence into adulthood to determine both trends in usage and initiation. However, it may be influenced by response bias common to interviews and surveys [12, 13].

UDS detects metabolites associated with certain drugs use (usually via a panel assay). This offers a major advantage over self-reporting: it is possible to collect information that would otherwise be withheld in a self-reporting study. It also becomes possible to collect data from subjects who are unable to participate in interviews, such as infants (who are unlikely to consciously participate in drug use, but which may reveal drug use by parents).

The main disadvantage of this method is false positive results arising from misidentification of metabolites in urine. For instance, it is known that quinolone antimicrobials can create false positives for opiate presence [14, 15]. Several forms of medication (both prescribed and over-the-counter) are known to trigger false positives in drug tests; ibuprofen, a common analgesic, may trigger false positives for phencyclidine (PCP), cannabinoids, and barbiturates in some screening panels [15].

The goal of GatewayNet is to predict initiation events and select those relationships which may be causal; therefore, it is important to consider past approaches to this problem. It should be noted that the causation referred to here is not deterministic causation: observation does not support the idea that a gateway drug is always followed by its target. Instead, the idea of probabilistic causation (i.e., event a is likely to cause b) is considered [16].

Statistical treatment of this problem has been attempted in the literature. A simple method uses a linear probability model [11, 17], such as the one suggested by Beenstock and Rahav to predict how cigarettes influenced cannabis use Eq. 2, where S_nt and C_nt are indicators of cigarettes and cannabis respectively by sample n at time t, X is a vector of personality characteristics, D_y is the birth cohort for year y, and u_nt accounts for unobserved error. The gateway hypothesis predicts that if C is a gateway into S, then β>0 [17].

Hazard analysis has also been used to assess this problem [17]. In relation to the gateway hypothesis, hazard analysis attempts to ascertain the risk of initiating the use of another drug. Recently, latent transition analysis has been used to assess gateway relationships [18].

Bayesian inference is often used to assess claims of causation. For instance, a Bayesian method was applied to assess data from Norwegian young adults and yielded the conclusion that proneness and accessibility are important contributing factors to hard drug use [19]. Another potential avenue might be in the form of a Bayesian Belief Network (BBN), a directed acyclic graph describing the probability of condition b occurring given condition a [20]; however, the literature does not record such an application of BBNs to the gateway hypothesis.

Association Rule Mining (ARM) is a well-known method where a set of items called a transaction can be mined to produce association rules of the form a→b, which is a prediction that when a is present, b will co-occur. A related strategy, known as sequential rule mining (SRM), can be used to predict that a will precedeb in sequence. Algorithms which use SRM include the Co-occurrence Maps with Sequence PAttern Mining using Equivalent class (CM-SPADE) [21], Sequential PAttern Mining (SPAM) [22], and Closed Sequential Patterns (ClaSP) [23] algorithms.

Sequential rule mining is applicable to a problem such as the Gateway Hypothesis because the latter predicts a causal relationship; if a causes b, then it is necessary for a to precede b. Causation also implies that the first instance of b will not precede the first instance of a.

We claim three contributions to the literature: i) the application of sequential rule mining to the assessment of the Gateway hypothesis, ii) the use of these rules to construct a gateway network describing interaction between, and iii) the introduction of the certainty measure.

In the following paragraphs, the mathematical basis for GatewayNet (and in particular, initiation rule mining) are described. How this model is defined is critical to interpreting GatewayNet’s results, so it is described in detail here.

Precedence Relations Let E denote a set of events, \(S : t \in \mathbb {Z}^{+} \mapsto E\) denote a sequence of events called the history such that S_t⊆E is the set of events occurring at some time t, a⊆E, and b⊆e. The predicate a≺b means “a precedes b” and is defined in Eq. 3.

It should be noted that a≺a may yield true under this definition. The operand a is called the antecedent, while b is called the subsequent.

Initiation Relations Let \(S^{a}_{b} = S_{a} \cup... \cup S_{b}\). For brevity, \(S_{t}^{*} = S^{1}_{t}\) and \(S^{*} = S^{*}_{|S|}\). The predicate a⊆b means “a initiates b” (an instance thereof being called an initiation rule) and is defined in Eq. 4. An initiation rule a⊆b has a degree which is the maximum between the number of elements in a and the number of elements in b Eq. 5.

Note that (unlike precedence relations) the initiation relation a→a is universally false. This relation can be further generalize d into windowed initiation. Let \(z \in \mathbb {Z}+\), z^′=z−1, and \(a \overset {z}{\rightarrow } b\) denote an initiation rule within window z. In this generalization, only the most recent z time points are searched for the antecedent in every time-step. Because \(a \overset {0}{\rightarrow } b\) is trivially false according to Eq. 6, it has been redefined Eq. 7.

The purpose behind this generalization is to account for large gaps of time between two events. For instance, if an event occurs in S₁ and is not recorded thereafter, can it be said to be associated with an event a time τ? With windowed initiation \(a \overset {\tau -}{\rightarrow } b\), this question can be answered.

It is trivial to show that the set of initiation z-windowed rules is a subset of the set of all initiation rules: the set of rules \(a \overset {0}{\rightarrow } b\) are equivalent to a→b and is vacuously a subset, and because \(S^{t-z^{\prime }}_{t} \subseteq S^{*}_{t}\) by definition, all initiation rules for z>0 are also initiation rules. Thus, the rule \(a \overset {z}{\rightarrow } b\) implies a→b.

Let T represent a set of histories (the transaction database) and S∈T. One possible incarnation of T (the incarnation used by GatewayNet) is illustrated in Table 1. Each record within the table is a triple (i,t,S_t), such that T_i(t)=S_t.

Criteria must exist for candidate rules to be accepted or rejected, and several are traditionally used in ARM that apply here. Count Eq. 8 and support (Eqs. 9 and 10) are perhaps the most basic and may be used to filter out rules which run the risk of being statistically invalid [20, 24]; however, high limits may preclude many relationships from being discovered. Confidence is a measure of how likely the rule occurs when its antecedent occurs Eq. 11 and may be a more suitable measure for this purpose. Lift Eq. 12 is a measure of interest which considers the case where a and b are independent [20]. Finally, conviction is the frequency that the rule makes an incorrect prediction Eq. 13 [20]. Thresholds for inclusion are expressed as l_count, l_sup, l_conf, l_lift, l_conv, and h_conv respectively.

The subset of candidate initiation rules for which these criteria met are called the set of mined rules. A rule is an element of the mined rules if and only if:

As with ARM, the a priori principle may be used with IRM to reduce the number of candidates that must be considered when testing a proposed initiation rule for inclusion. An item set X is considered frequent if a) count(X)≥l_count and b) sup(X)≥l_sup. Let \(d_{max} \in \mathbb {Z}^{+}\) be the maximum degree for which to mine rules. Thus, rule proposal can be implemented as shown in Fig. 1, where X⊗Y is the outer product of X and Y.

Recall that the gateway hypothesis predicts that the probability that b will arise out of a is greater than the probability that it would happen due to some other circumstance. When when we say this, we say that a is a gateway into b and denote that relationship using \(a \rightsquigarrow b\).

An initiation rule is known as a gateway rule (denoted \(a \rightsquigarrow b\)) whenever the probability that a→b Eq. 14 is greater than the probability that any combination of the remaining antecedents will initiate b. This is equivalent to positing that a (either directly or indirectly) causes b.

A simple way of ensuring this condition is to calculate the proposed rule’s certainty Eq. 1. The condition cert(a→b)=1 means that the probability that the subsequent arose out of a is precisely 50%, or alternatively that 50% of the remaining instances arose out of \(a \nrightarrow b\). Therefore, by Eq. 1, we posit that a is the most likely cause of b when cert(a→b)>1. When the limit of p(a→b) approaches 1, cert a→b approaches ∞: absolute certainty means that we posit b arises only from a Fig. 2

This test is necessary (albeit not sufficient) for the assertion that a given event is the singular cause of another. Even in [1], this degree of causation is not predicted: cigarettes or alcohol leads to cannabis. This method could only be used to therefore test the idea that cannabis singularly leads to other illicit drugs.

To test the most general form of the gateway hypothesis, it must be the case that the association occurs by greater probability than chance alone. Thus, we suggest that that gateway rules can be established using the condition cert (a→b)>l_cert, which is the maximum certainty for which we will reject a→b as causal. To satisfy this hypothesis, the l_cert must be at least the threshold where we would admit chance occurrence Eq. 16.

Consider the transaction database in Table 1; if one calculates the count for all of the item sets and degree one rules in the transaction database, then the values provided in Table 2 can used to calculate support; for instance, I₁ has a support of 0.8 because it is involved in 4 or 5 histories. Initiation rule support can be calculated by finding all histories where Eq. 4 holds; because of this, I₁→I₃ has a support of 0.6 (Table 2).

Using this table, it is possible to derive the aforementioned metrics: for instance, lift (I₁→I₃)=(0.6)/(0.8×0.6)=1.25. To determine whether or not this I₁→I₃ is also a gateway rule, one calculates cert (I₁→I₃)=(0.6)/(0.6−0.6)=0.6/0. Although this value is undefined, it can be interpreted as approaching ∞; thus, \(I_{1} \rightsquigarrow I_{3}\) can be said to hold.

Likewise, cert (I₁→1₂)=(0.6)/(1−0.6)=1.5, so \(I_{1} \rightsquigarrow I_{2}\) in an unwindowed context. Let us now form initiation rules over window z=2 (Table 3). Because the history for ID 3 does not initiate I₂ within the window, the support for \(I_{1} \overset {2}{\rightarrow } I_{2}\) drops to 0.4 and cert\((I_{1}\overset {2}{\rightarrow } 1_{2}) = (0.4)/(1 - 0.4) = 0.\overline {6}\). Thus, \(I_{1} \rightsquigarrow I_{2}\) because the certainty of cert\((I_{1} \overset {2}{\rightarrow } I_{2}) \leq 1\) and therefore does not meet Eq. 1.

The final phase that GatewayNet performs is visualization. This produces a directed graph which depicts relationships between initiation rules. Let G be a weighted digraph G=<E^′,R>, where events E^′ constitute the graph’s vertices, and rules R constitute edges between events. Let r∈R be a quadruple such that r≡<e₁∈E^′,e₂∈E^′,w,c>. Then for rule a→b, vertices {a,b}∈E^′, edge r_a→b is defined by Eq. 17, and membership of a→b in G is defined by Eq. 18.

To better characterize GatewayNet’s behavior, we created a synthetic data set (Additional file 2) for which interaction is well characterized. This data set is explicitly constructed so that a complete history is available for each subject in the data set.

The synthetic data was generated according to a mathematical model described in the following paragraphs. This was done for the purposes of validation; although we also tested against empirical data, it is important that we verify that GatewayNet is well-behaved. The forthcoming model describes a population which is fixated on events it considers preferential, but allows for experimentation with other events.

Let E consist of events {I₁,I₂,...,I_n}, where \(n \in \mathbb {Z}^{+}\), E₀≡{ε}∪E, e₁∈E₀, and e₂∈E₀. A Markov chain of order 1 P (Additional file 1) is randomly constructed to represent transition probabilities from e₁ to e₂ (Table 4). Two real parameters are provided: the affinity f and interest s. Affinity represents the probability that a subject will be satisfied with e₁ and will ensure that the event occurs at time t+1. Interest is a weight that represents the likelihood that the subject would independently ensure e₂ will occur. A special event, ε, represents the null event, which represents a transition from no event.

Naturally, each row in P must add to exactly 1.0; however, care must be taken to ensure that this criterion is met. Let P^′ represent an |E₀|×|E₀| matrix. Each element of P^′ is populated using Eq. 19: an event’s self-transition e₁→e₁ is simply represented by its affinity, while any other transition is randomly distributed from the remaining probability. Because the row sum may not add up to exactly 1, each element is then normalized across the row Eq. 20.

Because the generated history is considered to be a complete one, the initial state is always ε. Thus, time-point t=1 is considered to be the first opportunity for which an initiation event can occur. At each time-point, between two and three initiations may occur. Each history may have up to 12 records in it; in total, we generated 56,578 simulated transactions over 8192 histories. Most of the events had support above 10% (Table 5). In total, 29,412 events were generated, corresponding to an average of 2.49 events per history.

We generated two gateway networks for the synthetic data: one for l_sup=0.20 (Fig. 3), and one for l_sup=0.025 (Fig. 4). In both instances, l_conf=0.5, and l_lift=1. Versions of the network without gateway rule highlighting, with gateway rule highlighting, and just the gateway rules were generated. Additionally, gateway networks were generated with window sizes of z=1, z=2, and z=3 (Fig. 5). This was done to determine whether windowing had an effect on the synthetic data.

Synthetic data is useful for evaluating the performance of GatewayNet since it is expected that some structures should arise within the output (therefore providing a method of validation). However, it should be noted that synthetic data does not necessarily model the real world; to test performance in that environment, an empirical data set was used.

UDS data obtained from 71,312 patient between August 1998 and June 2011 over nearly 111,359 emergency room visits at LSU Health Sciences Center (the hospital portion now belongs to University Health) in Shreveport, LA. This hospital is a Level I trauma center that serves the 7 parishes in LERN Region 7 (including the Shreveport/Bossier City area) [25]. Because Caddo Parish (where Shreveport resides) is adjacent to both the Texas and Arkansas borders, patients from east Texas and southern Arkansas are also frequently served.

During the screening interval, four screening panels were used, and during this time, some drugs were not tracked consistently. These drugs were: 3,4-methylenedioxymethamphetamine (MDMA or ecstasy) and methadone (tested during 2007–2011), methamphetamine and propoxyphene (1998–2000, 2002–2004), and barbiturates (1998–2007).

Prior to processing, we removed demographic data and then assigned each patient a random identifier (ID) by first shuffling the list of patients, then assigning each patient in the shuffled list a sequential ID. Additionally, screening dates were converted to their corresponding Lilian day number. The day number was then scaled by 1440 (the number of minutes in the day) and the time of screening in minutes was added to the date. Finally, each patient’s screening time was calibrated to the first by subtracting the first screening’s timestamp.

This was done for to ensure that the screening time is expressed as an integer. Additionally, because methamphetamine and MDMA are amphetamines and methadone is an opiate, any instance of either was converted to this category prior to any processing. Because many patients only visited once or did not test positive for any drugs, we restricted the list of histories to those with at least two time-points and at least one positive result. Finally, a history was only accepted if there was at least one more time-point following the time-point of the first positive result. In total, 11,364 histories over 42,745 time-points remained.

This data was first processed using unwindowed IRM (Fig. 6). We set the parameters l_count=30, l_sup=0, l_conf=0.25. Minimum count was used instead of support because of the relatively few number of histories involving drug use (Table 6).

In addition to performing unwindowed mining, we mined initiation rules within a window of 525,600 minutes (1 year) (Fig. 7). This was done to remove rules which were primarily supported by spurious positives. Opiates were sometimes administered to incoming patients or as a result of emergency surgery. Because of usage this arising from medical intervention rather than choice, we further removed rules of the form x→ OPIATES (Fig. 8).