Modeling Transitivity and Cyclicity in Directed Graphs via Binary Code Box Embeddings
Modeling Transitivity and Cyclicity in Directed Graphs via Binary Code Box Embeddings
复制标题
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Dongxu Zhang;Michael Boratko;Cameron Musco;A. McCallum
中科院分区：
文献类型：
--
作者：
Dongxu Zhang;Michael Boratko;Cameron Musco;A. McCallum
使用可微表示对有向图进行建模是对图结构数据执行机器学习的基本要求。几何嵌入模型（如双曲、锥和盒嵌入）在这方面表现出色，对有向图表现出有用的归纳偏差。然而，建模有向图，既包含循环和一些元素的传递性，这两个属性在现实世界中很常见，是具有挑战性的。盒嵌入，可以被认为是代表图作为一个交叉在一些学习的超图，有一个自然的归纳偏向建模传递性，但（如我们所证明的）不能模型循环。为此，我们提出了二进制代码盒嵌入，其中学习的二进制代码选择一个子集的图的交集。我们探索了几种变体，包括全局二进制代码（相当于交集上的并集）和逐顶点二进制代码（允许更大的灵活性）以及正则化方法。理论和实证结果表明，所提出的模型不仅保留了有用的归纳偏差的传递性，但也有足够的代表能力，以模拟任意图形，包括图的循环。
Modeling directed graphs with differentiable representations is a fundamental requirement for performing machine learning on graph-structured data. Geometric embedding models (e.g. hyperbolic, cone, and box embeddings) excel at this task, exhibiting useful inductive biases for directed graphs. However, modeling directed graphs that both contain cycles and some element of transitivity, two properties common in real-world settings, is challenging. Box embeddings, which can be thought of as representing the graph as an intersection over some learned super-graphs, have a natural inductive bias toward modeling transitivity, but (as we prove) cannot model cycles. To this end, we propose binary code box embeddings , where a learned binary code selects a subset of graphs for intersection. We explore several variants, including global binary codes (amounting to a union over intersections) and per-vertex binary codes (allowing greater flexibility) as well as methods of regularization. Theoretical and empirical results show that the proposed models not only preserve a useful inductive bias of transitivity but also have sufficient representational capacity to model arbitrary graphs, including graphs with cycles.