Cross-graph Relational Learning (CGRL) refers to the problem of predicting
the strengths or labels of multi-relational tuples of heterogeneous object
types, through the joint inference over multiple graphs which specify the
internal connections among each type of objects. CGRL is an open challenge in
machine learning due to the daunting number of all possible tuples to deal with
when the numbers of nodes in multiple graphs are large, and because the labeled
training instances are extremely sparse as typical. Existing methods such as
tensor factorization or tensor-kernel machines do not work well because of the
lack of convex formulation for the optimization of CGRL models, the poor
scalability of the algorithms in handling combinatorial numbers of tuples,
and/or the non-transductive nature of the learning methods which limits their
ability to leverage unlabeled data in training. This paper proposes a novel
framework which formulates CGRL as a convex optimization problem, enables
transductive learning using both labeled and unlabeled tuples, and offers a
scalable algorithm that guarantees the optimal solution and enjoys a linear
time complexity with respect to the sizes of input graphs. In our experiments
with a subset of DBLP publication records and an Enzyme multi-source dataset,
the proposed method successfully scaled to the large cross-graph inference
problem, and outperformed other representative approaches significantly.

该论文提出了一种新的跨图关系学习模型，将其建模为一个凸优化问题，通过使用标记和未标记元组进行传导学习，并提供了一个可扩展算法，保证了最优解，并且与输入图的规模成线性时间复杂度。