Scaling R-GCN Training with Graph Summarization

Alessandro Generale, Till Blume, Michael Cochez

TL;DR

Training Relational Graph Convolutional Networks (R-GCNs) on massive knowledge graphs often hits a "memory wall" due to the massive amount of gradient information required. This paper proposes a clever workaround: compress the graph using summarization techniques, train the model on this condensed version, and then transfer the learned weights back to the original graph for a significant "jump-start" in performance and accuracy.

What Problem Does This Paper Address?

Knowledge Graphs (KGs) are the backbone of modern data representation, but they are notoriously difficult to process with deep learning. R-GCNs are powerful tools for learning from these graphs because they account for different types of relationships between entities. However, they are incredibly memory-intensive.

As a graph grows, the memory needed to store gradients during training quickly exceeds the capacity of even high-end GPUs. Researchers usually solve this by using more hardware or optimizing the implementation. This paper asks a different question: Can we make the data smaller without losing the structural "essence" that the model needs to learn?

Methods

The authors employ a two-step "summarize-then-transfer" approach:

  1. Graph Summarization: They use algorithms to group "equivalent" nodes into partitions, creating a smaller summary graph. They tested two main families:
  2. Approximate Summaries (e.g., Attributes Summary): Groups nodes that share the same set of outgoing edge labels (attributes).
  3. Precise Summaries (e.g., $k$-forward Bisimulation): A stricter method that groups nodes only if they share the same structural paths over multiple "hops" ($k$).
  4. Weighted Multi-label Training: Since a single summary node might represent original nodes with different labels, the authors created "weighted" labels based on the frequency of each class within that partition.
  5. Transfer Learning: An R-GCN is trained on the summary graph. Its weights are then transferred to a model for the original graph. This model can then be used for inference immediately or "fine-tuned" with further training.

Datasets

The researchers evaluated their approach on three standard RDF (Resource Description Framework) datasets:

  • AIFB: A smaller dataset (8,285 entities) used for initial validation.
  • MUTAG: A medium dataset (23,644 entities) with a high number of classes (113), making it a challenging classification task.
  • AM: The largest dataset tested (1.66 million entities), representing a real-world scaling scenario.

Key Insights and Ideas

  • The "Jump-Start" Effect: Transfer models consistently started at a much higher accuracy (often 70-80%) at Epoch 0 compared to the random initialization of baseline models.
  • Summarization as a Regularizer: Surprisingly, in some cases (like the AIFB dataset), training on the summary actually led to higher final accuracy than training on the full graph. This suggests that summarization might help the model ignore "noise" and focus on the core schema of the graph.
  • Literals are Load-Bearing: The authors found that including "literal" nodes (like strings or dates) in the summarization process was critical. When literals were stripped away, the performance of the transfer models dropped significantly.
  • Conciseness vs. Precision: There is a trade-off. Very concise summaries (like those produced for MUTAG) can be too small, losing vital information and allowing the baseline model to eventually catch up or outperform the transfer model.

Key Results

  • Accuracy Gains: On the AIFB dataset, the transfer model reached 92.5% accuracy, outperforming the baseline's 87.9%.
  • Efficiency on Large Graphs: On the AM dataset (1.6M+ edges), the transfer model achieved comparable results to the baseline but reached high accuracy much earlier in the training process.
  • Reduced Overhead: By training on a smaller representation, the computational cost per epoch is significantly reduced, provided the one-time cost of generating the summary is managed.

Limitations and Future Work

  • The Cost of Summarization: While training on the summary is fast, calculating the summary itself takes time. The authors note that if this pre-processing time is too high, it might negate the training speedup. Future work will focus on optimizing these algorithms.
  • Hyperparameter Sensitivity: The study primarily used a fixed $k=3$ for bisimulation. The relationship between the "depth" of the summary ($k$) and the number of layers in the R-GCN remains an open question.
  • Task Expansion: This paper focused on node classification. The authors suggest that future research should test if these summaries are equally effective for link prediction (predicting missing relationships).

Summary updated

Abstract

Training of Relational Graph Convolutional Networks (R-GCN) is a memory intense task. The amount of gradient information that needs to be stored during training for real-world graphs is often too large for the amount of memory available on most GPUs. In this work, we experiment with the use of graph summarization techniques to compress the graph and hence reduce the amount of memory needed. After training the R-GCN on the graph summary, we transfer the weights back to the original graph and attempt to perform inference on it. We obtain reasonable results on the AIFB, MUTAG and AM datasets. Our experiments show that training on the graph summary can yield a comparable or higher accuracy to training on the original graphs.Furthermore, if we take the time to compute the summary out of the equation, we observe that the smaller graph representations obtained with graph summarization methods reduces the computational overhead. However, further experiments are needed to evaluate additional graph summary models and whether our findings also holds true for very large graphs.
BibTeX
@inproceedings{generale2022scaling,
  author = {Alessandro Generale and Till Blume and Michael Cochez},
  title = {{Scaling R-GCN Training with Graph Summarization}},
  booktitle = {The Web Conference},
  year = {2022},
  doi = {10.1145/3487553.3524719},
}

Loading related content...

Figure