Spread-gram: A spreading-activation schema of network structural learning

Jie Bai, Linjing Li, Daniel ZengarXiv 2019 · arXiv

Abstract

Network representation learning (NRL) often struggles with the non-linear, high-order structures of complex graphs. We present Spread-gram, a framework inspired by cognitive psychology’s "spreading-activation" theory. By mimicking the way human memory retrieves information, Spread-gram traverses networks through structured, parallel activation rather than sequential random walks. This approach captures hierarchical relationships more effectively and achieves state-of-the-art performance in link prediction and node classification while maintaining linear time complexity.

Introduction

Modern network embedding methods, such as DeepWalk or Graph Convolutional Networks (GCNs), frequently adapt techniques from natural language processing or computer vision. However, these adaptations introduce significant challenges:

  1. Information Bias: Sequential inputs (random walks) often fail to represent the high-order, non-linear dependencies inherent in graphs.
  2. Sparsity: Matrix-based methods become inefficient as network size grows while edge density remains low.
  3. Topological Uncertainty: The variable number of neighbors for any given node makes standard convolutional architectures difficult to apply without complex modifications.

Spread-gram addresses these issues by looking to cognitive science, specifically the Adaptive Control of Thought (ACT) spreading-activation theory, to create a more natural learning schema for relational data.

The Spread-gram Framework

Spreading Mechanism

The core of Spread-gram is its structured search process, which replaces stochastic random walks with a deterministic propagation model.

Figure 1: The spreading activation mechanism, showing how activation propagates from a source node through successive layers of the network.

The mechanism follows three key steps:

  • Source Activation: A random source node is selected and "activated," triggering its immediate neighbors.
  • Parallel Propagation: Activated neighbors serve as new sources, spreading activation to their own neighbors in parallel.
  • Ordered Updating: Nodes are updated along the actual paths of the network, ensuring the embedding captures the true topological structure without the bias of linear sequences.

Mathematical Framework and Efficiency

Spread-gram utilizes a Maximum Likelihood Estimation (MLE) objective function. For homogeneous networks, a log-linear model adjusts node proximity by comparing embedding inner products against the sigmoid-based likelihood of edge existence. In heterogeneous networks, a Benchmark Space is introduced, where mapping matrices ($W$) transform embeddings from different semantic spaces into a common domain for correlation calculation.

To maintain scalability, the model employs Negative Sampling, ensuring training time remains linear relative to the number of edges ($O(kd|E|)$). This allows Spread-gram to process massive datasets like Amazon (nearly 1 million nodes) efficiently.

Experimental Results and Insights

The authors evaluated Spread-gram across five diverse datasets, including WITS, Wiki, DIP, DBLP, and Amazon.

Performance Metrics

Spread-gram demonstrated significant improvements over baselines:

  • Link Prediction: On the DBLP dataset, Spread-gram achieved an AUC of 0.989, vastly outperforming DeepWalk (0.664) and GCN (0.696).
  • Node Classification: The model consistently matched or exceeded state-of-the-art performance (e.g., PTE, Metapath2vec++), showing particular stability as label density increased.

Structural Visualization

One of Spread-gram's primary strengths is its ability to discover and preserve hierarchical structures.

Figure 2: Visualizations of network structures. Spread-gram excels at revealing clear, tree-like taxonomic hierarchies compared to the "blobs" often produced by other methods.

Qualitative analysis using t-SNE shows that Spread-gram produces more balanced and discriminative clusters. In the Wiki dataset, for instance, it successfully grouped Southeast Asian cultural entries together, even when they spanned different high-level categories.

Conclusion

Spread-gram offers a cognitively-aligned alternative to traditional NRL methods. By leveraging spreading activation, it naturally handles topological uncertainty and discovers deep hierarchies that sequential methods miss. Future work will focus on incorporating weighted edges and extending the framework to dynamic, evolving networks.

Summary updated

Abstract

Network representation learning has exploded recently. However, existing studies usually reconstruct networks as sequences or matrices, which may cause information bias or sparsity problem during model training. Inspired by a cognitive model of human memory, we propose a network representation learning scheme. In this scheme, we learn node embeddings by adjusting the proximity of nodes traversing the spreading structure of the network. Our proposed method shows a significant improvement in multiple analysis tasks based on various real-world networks, ranging from semantic networks to protein interaction networks, international trade networks, human behavior networks, etc. In particular, our model can effectively discover the hierarchical structures in networks. The well-organized model training speeds up the convergence to only a small number of iterations, and the training time is linear with respect to the edge numbers.
BibTeX
@misc{bai2019spread,
  author = {Jie Bai and Linjing Li and Daniel Zeng},
  title = {{Spread-gram: A spreading-activation schema of network structural learning}},
  year = {2019},
  eprint = {1909.13581},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.13581},
}
Figure