Learning Dynamic Graphs, Too Slow

Andrei A. Klishin, Nicolas H. Christianson, Cynthia S. Q. Siew, Dani S. BassettarXiv 2022 · DOI · arXiv

Abstract

Knowledge acquisition is often modeled as the navigation of a complex network of concepts. This paper investigates the efficiency of this process by modeling learners as random walkers on dynamic graphs derived from linear algebra textbooks. By introducing parameters for finite study effort (dilation) and mental imperfections—such as forgetting, shuffling, and reinforcement—the authors demonstrate that real-world learning is significantly slower and more biased than theoretical limits suggest. The findings highlight a fundamental trade-off between the ease of skimming a text and the eventual mastery of its entire conceptual network.

Introduction

Knowledge is rarely a linear list of facts; it is a complex network of concepts and their relationships. When reading a textbook, a student navigates a "semantic network" that expands as new material is introduced. However, most models of network learning assume either infinite time or static graphs. In reality, students face two major constraints: finite effort and mental imperfections. This study addresses the gap between the "taught" network (the information presented) and the "learned" mental model (the information internalized), focusing on how the temporal order of a textbook affects learning outcomes.

Modeling the Learner as a Random Walker

The authors represent textbooks as dynamic networks where nodes are key concepts (e.g., "matrix," "eigenvector") and edges represent their co-occurrences in sentences. The learner is modeled as a random walker moving through this graph.

Conceptual framework of the random walk model and mental model formation.

To capture the nuances of human cognition, the model introduces several key parameters:

  • Dilation ($D$): A measure of effort, defined as the number of random walk steps taken per sentence. High $D$ represents thorough study, while low $D$ represents skimming.
  • Mental Errors: The model accounts for forgetting ($\alpha$), where memories of edges are lost over time; shuffling ($\beta$), where the temporal order of concepts is confused; and reinforcement ($\gamma$), a path-dependence effect where learners prefer familiar concepts.

Datasets

The study utilizes a corpus of 10 popular linear algebra textbooks, including works by Strang, Axler, and Treil. These books contain between 146 and 453 nodes and 4,322 to 15,512 edges, with temporal scales ranging from 2,000 to 12,000 sentences.

Key Insights and Results

The research reveals that learning is naturally inefficient due to the heterogeneity of concept mentions. Textbooks often repeat core concepts like "matrix" far more frequently than specialized terms. This prioritization, while helpful for initial exposure, creates a "Jensen bound" that slows down the total exploration of the network.

Node and edge recall as a function of exposition time and dilation.

The "Too Slow" Factor and Precision Limits

At low effort (skimming), node and edge recall are often an order of magnitude lower than the theoretical maximum. Furthermore, mental shuffling ($\beta$) imposes a hard cap on the precision of a mental model. While shuffling can lead to "predicting" future edges by closing triangles prematurely, it primarily litters the mental map with spurious connections.

Data Collapse and Reinforcement

A significant finding is the "data collapse" between forgetting and dilation. The authors show that these can be combined into a single "effective dilation" variable ($D_\alpha$), meaning a fast learner who forgets easily is mathematically equivalent to a slow learner with perfect memory. Conversely, high reinforcement ($\gamma$) can trap learners in "echo chambers" of familiar concepts, breaking reciprocity and preventing the discovery of new material.

Discussion and Future Work

While the random walk is a simplified model of human curiosity, it provides a robust framework for analyzing educational materials. The authors suggest that this "exposure map" approach could serve as a design tool for educators. By identifying "bottleneck" concepts likely to be missed under finite study time, authors could reorder material to ensure more robust and efficient learning. Future research may incorporate more strategic navigation paths, such as "jumps" between distant but related chapters, to better reflect guided instruction.

Summary updated

BibTeX
@misc{klishin2022learning,
  author = {Andrei A. Klishin and Nicolas H. Christianson and Cynthia S. Q. Siew and Dani S. Bassett},
  title = {{Learning Dynamic Graphs, Too Slow}},
  year = {2022},
  eprint = {2207.02177},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2207.02177},
}
Figure