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:
- Information Bias: Sequential inputs (random walks) often fail to represent the high-order, non-linear dependencies inherent in graphs.
- Sparsity: Matrix-based methods become inefficient as network size grows while edge density remains low.
- 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.
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.
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