Human learning of hierarchical graphs

Humans are exposed to sequences of events in the environment, and the interevent transition probabilities in these sequences can be modeled as a graph or network. Many real-world networks are organized hierarchically and while much is known about how humans learn basic transition graph topology, whether and to what degree humans can learn hierarchical structures in such graphs remains unknown. We probe the mental estimates of transition probabilities via the surprisal effect phenomenon: humans react more slowly to less expected transitions. Using mean-field predictions and numerical simulations, we show that surprisal effects are stronger for finer-level than coarser-level hierarchical transitions, and that surprisal effects at coarser levels are difficult to detect for limited learning times or in small samples. Using a serial response experiment with human participants ($n=100$), we replicate our predictions by detecting a surprisal effect at the finer level of the hierarchy but not at the coarser level of the hierarchy. We then evaluate the presence of a trade-off in learning, whereby humans who learned the finer level of the hierarchy better also tended to learn the coarser level worse, and vice versa. This study elucidates the processes by which humans learn sequential events in hierarchical contexts. More broadly, our work charts a road map for future investigation of the neural underpinnings and behavioral manifestations of graph learning.

Figure 1

Schematic of the task design. (a) Example sequence of visual stimuli; each row is shown to the participant one at a time. In this example, each row represents a unique color pattern of nine squares which corresponds to a unique node in a transition graph. For each participant, a sequence of 1500 stimuli was drawn via a random walk on the same three-level Sierpiński graph ${}^{3}S_p^n$ (Methods). (b) A part of the transition graph that involves the nodes in panel (a). The mapping between the color pattern in panel (a) and the node index in panel (b) was shuffled uniformly at random across participants so that any systematic biases of reactions to certain color patterns would be balanced across nodes. (c) Hand placement; each of the keys highlighted in green corresponds to a square in any row of panel (a). When the squares were highlighted in red in panel (a), the participants were asked to press the corresponding keyboard input combinations, which were drawn from a total of 27 possible combinations that did not require coordination between the two hands.

Figure 2

Predictions of human learning and its dependence on hierarchy in the structure of transition probabilities between stimuli. Here we use a validated model of human perception to predict how humans will respond to sequential information drawn from a graph topology [16]. A key indicator of human learning is a slowing of reaction time at the boundary between clusters in the graph. This slowing is referred to as the cross-cluster surprisal (CCS), which we show here for self-loop regularized level-3 Sierpiński graphs with different bases. (a) Visualizations of Sierpiński graphs of base three, four, and five with a power of three. Nodes are shown in pink and edges are shown in green, except for the self-loop edges that are shown in black, because they do not belong to any well-defined edge level. The saturation of the green indicates the level of the hierarchy at which the edge is defined; we refer to this level as the edge level in the color bar label. We use a bottom-up convention for levels, meaning that the finest level is level-1 and the level value increases as the scale increases. (b) The cross-cluster surprisal (CCS) for the corresponding Sierpiński graphs in panel (a) as a function of $\beta$: the rate of error in memory when updating the mental model of the transition graph. The $\beta$ value at which the cross-cluster surprisal peaks is marked for both levels of the graph's hierarchy.

Figure 3

Predictions of human learning and its dependence on hierarchy in self-loop regularized base-3 Sierpiński graphs that encode transition probabilities between stimuli. Here again we use a validated model of human perception to predict how humans will respond to sequential information drawn from a graph topology [16]. (a) Visualizations of Sierpiński graphs of power three, four, and five with a base of three. Nodes are shown in pink and edges are shown in green, except for the self-loop edges that are shown in black, because they do not belong to any well-defined edge level. The saturation of the green indicates the level of the hierarchy at which the edge exists; we refer to this level as the edge level in the color bar label. (b) The cross-cluster surprisal (CCS) for corresponding Sierpiński graphs in panel (a) as a function of $\beta$, which is the rate of error in memory when updating the mental model of the transition graph. The $\beta$ value at which the cross-cluster surprisal peaks is marked for all levels of the graph's hierarchy.

Figure 4

Using the maximum entropy model to estimate the cross-cluster surprisal for individual human participants. When fitting the maximum entropy model to the human reaction time ($rt$) data, we estimate three separate parameters as specified by the linear relation $rt=r_0+r_{1}a\left(\beta \right)$, where $r_0$ is intercept, $r_1$ is slope, and $\beta$ is the rate of error in memory when updating the mental model of the transition graph. (a) Histogram of the intercept $r_0$ in the linear model $rt=r_0+r_{1}a\left(\beta \right)$. (b) Histogram of the slope $r_1$ in the linear model $rt=r_0+r_{1}a\left(\beta \right)$. (c) Histogram of the $\beta$ values in the linear model $rt=r_0+r_{1}a\left(\beta \right)$. Note, here we only show data from participants whose $\beta$ satisfied $0<\beta <\infty$; those excluded were 11 participants whose $\beta =0$ and 2 participants whose $\beta \to \infty$. (d)–(e) Cross-cluster surprisal at level-1 (d) and level-2 (e), including the 87 participants whose $\beta$ satisfied $0<\beta <\infty$. The $p$ values were obtained from one-sample Wilcoxon signed-rank tests, where we subtracted 1 from the cross-cluster surprisal value and compared the resultant number to a null distribution centered at zero. An individual asterisk above a boxplot indicates a $p$ value less than 0.05; two asterisks indicate a $p$ value less than 0.01; three asterisks indicate a $p$ value less than 0.001; four asterisks indicate a $p$ value less than 0.0001. Each one-sample Wilcoxon signed-rank test was performed on the data from a single $\beta$ bin. The $\beta$ bins are evenly spaced in logarithmic space and the definition of bins is the same throughout the analysis, except there are more bins in the simulations due to the $\beta$ range being larger in the simulations than in the experiment. The number below each boxplot is the number of human participants with $\beta$ values in that $\beta$ bin. For each bin, the box delineates the interquartile range whereas the bottom whisker delineates the $2.5\%$ percentile and the top whisker delineates the $97.5\%$ percentile.

Figure 5

Dependence of learning estimates on sample size. Here we show boxplots of the cross-cluster surprisal for the Sierpiński graph ${}^{3}S_3^3$, across ten $\beta$ values and a walk length of 1500 steps. For each $\beta$ value, the box delineates the interquartile range, the bottom whisker indicates the $2.5\%$ percentile, and the top whisker indicates the $97.5\%$ percentile. The solid curves are mean-field predictions of the cross-cluster surprisal at an infinite-time horizon. We sampled 10, 100, and $10000$ agents per bin from the total of ten thousand available, as displayed on the left, middle, and right column of the figure, respectively. (a) The cross-cluster surprisal (CCS) at the finer level of the hierarchy as a function of $\beta$: the rate of error in memory when updating the mental model of the transition graph. (b) The cross-cluster surprisal (CCS) at the coarser level of the hierarchy as a function of $\beta$.

Figure 6

Dependence of learning estimates on learning time. Here we show boxplots of the cross-cluster surprisal for the Sierpiński graph ${}^{3}S_3^3$, across ten $\beta$ values and a sample size of 100 simulated participants per bin. For each $\beta$ value, the box delineates the interquartile range, the bottom whisker indicates the $2.5\%$ percentile, and the top whisker indicates the $97.5\%$ percentile. The solid curves are mean-field predictions of the cross-cluster surprisal at an infinite-time horizon. We sampled walk lengths of 1500, 4500, and 7500 steps, as displayed on the left, middle, and right column of the figure, respectively. (a) The cross-cluster surprisal (CCS) at the finer level of the hierarchy as a function of $\beta$: the rate of error in memory when updating the mental model of the transition graph. (b) The cross-cluster surprisal (CCS) at the coarser level of the hierarchy as a function of $\beta$.

Figure 7

A power analysis for estimating the surprisal effect in human experiments. Here we provide plots of powers of one-sided Wilcoxon signed-rank tests on simulated data obtained from the same Sierpiński graph used in the experiment (${}^{3}S_3^3$). To the leftmost $\beta$ bin in Figs. 4, 5, 6 we assign an index of one, and to the second leftmost bin we assign an index of two, and so on. Hence, the $\beta$ bin indices in the plots here refer to the corresponding $\beta$ bins in Figs. 4, 5, 6. Note that we only included $\beta$ bins whose empirical sample size (as shown in Fig. 4) is greater than two. To estimate the power of the one-sided Wilcoxon signed-rank test given a sample size $n=1,2,...,99$ for each $\beta$ bin, we uniformly sampled $n$ agents with replacement from the simulation data that had a total of $10000$ agents per beta bin. We then repeated this process 1000 times. Next, we approximated the statistical power by calculating the ratio of repetitions in which the one-sided Wilcoxon signed-rank test yielded a $p$ value that was less than 0.05. Because the surprisal effect can happen at two hierarchical levels in the Sierpiński graph ${}^{3}S_3^3$, here we show power estimates for both levels (shades of green), with different power baselines (95%, 90%, 80%; dashed lines) for reference.

Figure 8

Tradeoff in learning finer versus coarser scales of hierarchical graphs. Here we plot the Spearman correlation coefficient between the cross-cluster surprisal at the finer scale and the cross-cluster surprisal at the coarser scale, across all $\beta$ bins for both simulations (in gray) and the experiment (in red). To estimate the spread of Spearman correlation coefficients at different values of $N$ (the total sample size) for the numerical simulations, we uniformly sampled $N$ agents with replacement from the simulation data which had a total of $10000$ agents per beta bin. Then, we calculated the Spearman correlation coefficient between the cross-cluster surprisal at the finer scale and the cross-cluster surprisal at the coarser scale. Finally, we repeated this process 1000 times. From the 1000 resultant estimates of the Spearman correlation coefficients for each $N$, we calculated the median, $50\%$ interval, and $95\%$ interval. The red dot indicates the Spearman correlation coefficient ($r_s=-0.468$) for the empirical data in Fig. 4.

Figure 9

The cross-cluster surprisal on power-3 Sierpiński graphs with different bases and regularization types. (a) The CCS for an unregularized three-level Sierpiński graph across three bases. (b) The CCS for a one-node regularized three-level Sierpiński graph across three bases. (c) The CCS for a one-cluster regularized three-level Sierpiński graph across three bases. (d) The CCS for a self-loop regularized three-level Sierpiński graph across three bases.

Figure 10

The cross-cluster surprisal on base-3 Sierpiński graphs with different levels and regularization types. (a) The CCS for an unregularized base-3 Sierpiński graph across three levels. (b) The CCS for a one-node regularized base-3 Sierpiński graph across three levels. (c) The CCS for a one-cluster regularized base-3 Sierpiński graph across three levels. (d) The CCS for a self-loop regularized base-3 Sierpiński graph across three levels.

Figure 11

Dependence of learning estimates on learning time for the alternative model. Here we show boxplots of the cross-cluster surprisal for the Sierpiński graph ${}^{3}S_3^3$, across ten $w$ values and a sample size of 100 simulated participants per bin. For each $w$ value, the box delineates the interquartile range, the bottom whisker indicates the $2.5\%$ percentile, and the top whisker indicates the $97.5\%$ percentile. We sampled walk lengths of 1500, 4500, and 7500 steps, as displayed on the left, middle, and right column of the figure, respectively. (a) The cross-cluster surprisal (CCS) at the finer level of the hierarchy as a function of $w$: the window size in which the most visited node is defined when updating the mental model of the transition graph. (b) The cross-cluster surprisal (CCS) at the coarser level of the hierarchy as a function of $w$.