TL;DR
This paper introduces LowrankTLP, a novel algorithm that significantly scales up label propagation for multi-relational learning on tensor product graphs. By approximating the core transformation matrix with a low-rank representation, LowrankTLP achieves better scalability and accuracy in tasks like hyperlink prediction and graph alignment, outperforming existing methods.
What Problem Does This Paper Address?
Multi-relational learning aims to infer complex relationships among entities across multiple knowledge graphs. A powerful approach is to model these relationships as a tensor product graph (TPG) and apply label propagation. However, the computational cost of label propagation on TPGs grows exponentially with the number of graphs, making it intractable for more than a few graphs. This paper tackles this scalability bottleneck, enabling efficient and accurate multi-relational learning on a larger number of interconnected knowledge graphs.
Methods
The core of this work is the LowrankTLP algorithm. It builds upon the idea of label propagation on normalized TPGs, which can be expressed as a closed-form solution involving a transformation matrix. Instead of computing this full matrix, LowrankTLP proposes an optimization framework to find a low-rank approximation of this transformation matrix. This is achieved by selecting a subset of optimal eigen-pairs from the individual normalized graphs. The algorithm then uses these selected eigen-pairs to efficiently compute the approximated closed-form solution. For implementation, they leverage parallel tensor computation libraries like SPLATT to further boost efficiency.
Datasets
The paper evaluates LowrankTLP on:
- Simulated datasets: Synthetic graphs were generated to test performance and scalability by varying graph density and size.
- DBLP dataset: A real-world dataset of scientific publication records, used for hyperlink prediction. It involves three graphs representing authors, papers, and venues.
- CT scan images: A dataset of 134 CT scans used for multiple graph alignment, focusing on matching segmented regions across images.
- PPI networks: Protein-protein interaction networks from five species (H. sapiens, D. melanogaster, S. cerevisiae, C. elegans, M. musculus) used for multiple graph alignment.
Key Insights and Ideas
- Low-rank approximation for scalability: The key insight is that a low-rank approximation of the transformation matrix in label propagation on TPGs is sufficient to achieve good performance, drastically reducing computational cost.
- Principled eigen-pair selection: The paper introduces a principled method for selecting the most informative eigen-pairs from individual graphs, which guarantees optimality for the proposed low-rank approximation.
- Generalization of label propagation: LowrankTLP generalizes existing label propagation models to the normalized tensor product graph, offering a more robust framework.
- Practical applicability: The algorithm demonstrates strong performance on diverse real-world tasks, including predicting publication relationships and aligning complex biological and medical data.
Key Results
- Effectiveness: LowrankTLP consistently outperforms baseline methods like ApproxLink, CP, CP-W, GraphCP, and GraphCP-W in both hyperlink prediction and graph alignment tasks. For instance, in DBLP dataset experiments, LowrankTLP achieved AUC ≈ 0.76 and MAP ≈ 0.8 with only 0.1% of training data, significantly better than CP-based methods.
- Scalability: The parallel implementation of LowrankTLP shows a significant speedup (about an order of magnitude) compared to its sequential version, enabling it to handle up to 50 graphs efficiently. It can align up to 26 CT scan images, a task where other methods struggle.
- Accuracy: In CT scan alignment, LowrankTLP achieved much higher accuracy (e.g., 83% for 7 images) compared to GraphCP, especially with larger numbers of graphs.
Limitations and Future Work
- Hyperparameter tuning: While the paper provides a method for selecting eigen-pairs, the graph hyperparameter 'a' still requires tuning. The paper notes that for high-order tensors, 'a' often needs to be set very small.
- Future work: The authors suggest exploring automatic strategies for choosing the rank 'k' for more efficient applications of LowrankTLP. They also aim to analyze the spectral properties of tensor product graphs more deeply.
Summary updated