Deep Loopy Neural Network Model for Graph Structured Data Representation Learning

Jiawei Zhang, Limeng Cui, Fisher B. GouzaarXiv 2018 · OpenReview

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.

The DLNN architecture mapping an input graph to a layered neural network with intra-layer connections.

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:

  1. g-Hop Subgraph Extraction: For each target node, we extract a local neighborhood (a $g$-hop subgraph) to constrain the scope of dependency.
  2. 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.
A 3-hop rooted tree extracted from a loopy graph to enable acyclic backpropagation.

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

Abstract

Existing deep learning models may encounter great challenges in handling graph structured data. In this paper, we introduce a new deep learning model for graph data specifically, namely the deep loopy neural network. Significantly different from the previous deep models, inside the deep loopy neural network, there exist a large number of loops created by the extensive connections among nodes in the input graph data, which makes model learning an infeasible task. To resolve such a problem, in this paper, we will introduce a new learning algorithm for the deep loopy neural network specifically. Instead of learning the model variables based on the original model, in the proposed learning algorithm, errors will be back-propagated through the edges in a group of extracted spanning trees. Extensive numerical experiments have been done on several real-world graph datasets, and the experimental results demonstrate the effectiveness of both the proposed model and the learning algorithm in handling graph data.
BibTeX
@misc{zhang2018deep,
  author = {Jiawei Zhang and Limeng Cui and Fisher B. Gouza},
  title = {{Deep Loopy Neural Network Model for Graph Structured Data Representation Learning}},
  year = {2018},
  eprint = {1805.07504},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1805.07504},
}
Figure