Abstract
Existing deep learning models encounter significant challenges when handling graph-structured data due to the inherent recursive dependencies. In this paper, we introduce the Deep Loopy Neural Network (DLNN), a model designed specifically for graph data. Unlike traditional feed-forward models, DLNN incorporates extensive intra-layer connections mirroring the input graph, creating numerous loops. To make learning feasible, we propose a novel algorithm that back-propagates errors through extracted spanning trees rather than the original loopy structure. Numerical experiments on real-world datasets demonstrate the effectiveness of this approach in representation learning.
Introduction: The Challenge of Loopy Graphs
Traditional deep learning architectures typically rely on directed acyclic flows, where information moves from input to output layers. However, real-world graph data—such as social networks or knowledge bases—is inherently "loopy." In these structures, nodes often have mutual dependencies (e.g., if node A is connected to node B, and B to A).
When applying standard gradient descent to such models, the chain rule for derivatives becomes infinitely recursive. Calculating the gradient for one node requires the gradients of its neighbors, which in turn depend back on the original node. This "loopy" dependency makes exact gradient computation mathematically intractable in a fully connected graph.
The Deep Loopy Neural Network Architecture
The DLNN architecture consists of an input layer, multiple hidden layers, and an output layer. Its defining feature is the inclusion of intra-layer connections that directly mirror the edges of the input graph. This allows the model to capture complex structural relationships directly within its hidden states.
As shown in the architecture above, the state of each node in a hidden layer is influenced not only by the layer below but also by its neighbors within the same layer. This design preserves the topological properties of the input graph throughout the deep representation process.
Methodology: Learning via Rooted Spanning Trees
To overcome the infinite recursion in backpropagation, we introduce a learning algorithm based on tree-based approximation. The process involves two key steps:
- g-Hop Subgraph Extraction: For each target node, we extract a local neighborhood (a $g$-hop subgraph) to constrain the scope of dependency.
- Rooted Spanning Tree ($g$-tree) Construction: We transform the loopy subgraph into an acyclic rooted spanning tree. By converting the graph into a tree, we break the recursive cycles while maintaining the most critical local structural context.
The model then performs error backpropagation through these extracted trees using a specific PROP operation. This ensures that gradients can flow from the output back to the input features without encountering infinite loops, effectively approximating the true gradient of the loopy system.
Experimental Results
The DLNN was evaluated against state-of-the-art baselines, including DeepWalk, LINE, and Matrix Factorization (MF), across four real-world datasets: Douban, IMDB, Foursquare, and Twitter.
The results consistently showed that DLNN outperforms existing methods in node classification tasks. For instance, on the Douban dataset, DLNN achieved a Mean Square Error (MSE) of 0.035, which is approximately 7.8% lower than the next best method (MF) and 30% lower than APP. Across all metrics—including MSE, Mean Absolute Error (MAE), and Label Ranking Loss—DLNN maintained the best average rank, proving its robustness as a general-purpose graph learner.
Conclusion and Future Work
The Deep Loopy Neural Network provides a mathematically sound framework for learning representations from complex, cyclic graph data. By approximating loopy structures with rooted spanning trees, it enables efficient deep learning where traditional methods fail. Future research will focus on addressing the computational overhead of tree extraction in massive graphs and exploring gating mechanisms to mitigate vanishing gradients in deeper $g$-hop structures.
Summary updated