Efficient Training and Inference of Hypergraph Reasoning Networks
Authors: Guangxuan Xiao
Leslie Pack Kaelbling
Jiajun Wu
Jiayuan Mao
Venue: ICLR 2022 Submitted (2022)
Keywords: Relational Rule Induction
Hypergraph Network
Efficient Learning

Abstract: We study the problem of hypergraph reasoning in large domains, e.g., predicting the relationship between several entities based on the input facts. We observe that in logical reasoning, logical rules (e.g., my parent's parent is my grandparent) usually apply locally (e.g., only three people are involved in a grandparent rule), and sparsely (e.g., the grandparent relationship is sparse across all pairs of people in the world). Inspired by these observations, we propose Sparse and Local Neural Logic Machines (SpaLoc), a structured neural network for hypergraph reasoning. To leverage the sparsity in hypergraph neural networks, SpaLoc represents the grounding of relationships such as parent and grandparent as sparse tensors and uses neural networks and finite-domain quantification operations to infer new facts based on the input. We further introduce a sparsification loss to regularize the number of hyperedges in intermediate layers of a SpaLoc model. To enable training on large-scale graphs such as real-world knowledge graphs, SpaLoc makes training and inference-time sub-sampling of the input graphs. To remedy the information loss in sampled sub-graphs, we propose a novel sampling and label calibration paradigm based on an information-theoretic measure information sufficiency. Our SpaLoc shows superior accuracy and efficiency on synthetic datasets compared with prior art and achieves state-of-the-art performance on several real-world knowledge graph reasoning benchmarks.

Under review as a conference paper at ICLR 2022
EFFICIENT TRAINING AND INFERENCE OF HYPERGRAPH REASONING NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We study the problem of hypergraph reasoning in large domains, e.g., predicting the relationship between several entities based on the input facts. We observe that in logical reasoning, logical rules (c.g., my parent's parent is my grandparent) usually apply locally (e.g., only three people are involved in a grandparent rule), and sparsely (e-g., the grandparent relationship is sparse across all pairs of people in the world). Inspired by these observations, we propose Sparse and Local Neural Logic Machines (SpaLoc), structured neural network for hypergraph reasoning. To leverage the sparsity in hypergraph neural networks, SpaLoc represents the grounding of relationships such parent and grandparent as sparse tensors and uses neural networks and finite-domain quantification operations to infer new facts based on the input. We further introduce sparsification loss regularize the number of hyperedges in intermediate layers of a Spal Loc model. To enable training large-scale graphs such real-world knowledge graphs, Spal Loc makes training and inference-ting tineencee-imeeeeee sabbamnling of the input graphs. To remedy the information loss in sampled sub-grape uubgrrapss, we propose a novel sampling and label calibration paradigm based on an anformation-theoree SpaLoc shows superior accuracy and efficiency on synthetic datasets compared with prior art and achieves state-of-the-art performance on several real-world knowledge graph reasoning benchmarks.
measure information sufficiency. Our
INTRODUCTION
Performing graph reasoning in large domains, such as predicting the relationship between two entities based on the input facts, is an important practical problem that arises in reasoning about molecular modeling, knowledge networks, and collections of objects in the physical world (Schlichtkrull et al., 2018; Veličković et al., 2020; Battaglia et al., 2016). The necessary inference rules generally unknown and must be inferred from data, which in general are large. In this paper, we focus on learning neural networks for graph reasoning tasks. Consider the problem of learning rule that explains the grandparent relationship. Given a dataset of labeled family relationship graphs, we aim to build machine-learning algorithms that can learn predict specific relationship (e.g., grandparent) based on other relationships. such as father(I, 3) and mother(x, x. y).
Neural Logic Machines (NLM; Dong al., 2019) present method for solving graph reasoning tasks with a structured neural network. NLMs keep track of hyperedge representations for all tuples consisting of up to B entities. Thus, they can infer more complex finitel--quantffeed logical relations than standard graph neural networks that only consider binary relationships between entities (Morris al., 2019; Barceló al., 2020). However, there are two disadvantages of such dense hypergraph representation. First, the training and inference of NLMs requires simultaneously considering all entities domain, such as all of the N people in a family relationship database. Second, they scale polynomially with respect the number of entities considered in single inference. Even inferring single relation like grandparent requires O(N3) time and space complexity. In practice, for large graphs, these limitations make the training and inference intractable and hinder the application of NLMs in lcrge-scale real-world domains.
To address these two challenges, we present novel framework, called Sparse and Local Neural Logic Machines (SpaLoc). for inducing sparse relational rules from data in large domains. Our key idea is exploit locality and sparsity in data: determining relationship between entities

---

Under review as a conference paper at ICLR 2022
(iii) Sub-domain Training Information
(1) Sparse Neural
Sparsffication Through
Sufficnecy Based Calibration (Section 2.4)
Lugic Machine (Section 2.2)
Regularization (Section 2.3)
Imput Domain
Calibrated Sub-domains
Nollayy:
Deym
Global
Unars: p10)
NN
O0
NN
Object-Level Prodiction
Rinary: rfc y)
Spariity
NN
NN
Minary-Bubalien Prediction
Tesary: Jt.
NN
NN
Tenars-Rulaiie Rubatin
Prodiction
Breada
The overall pipeline of SpaL.oc a multi-layer neural network that applies to hypergraphs. / and V denote the index tensor and value tensor respectively. To facilitate training and inference in large domains, we employ sub-graph sampling procedure and sparsification.
Figure 1:
usually only requires consideration of a small number of additional entities, and the resulting relation usually only holds for small number of tuples of entities. Our contribution three-fold. First, we develop a sparse lensor-based representation for representing hyperedge relationships among entities and making inferences about them. Second, during both training and inference, SpaLoc employs a sub- sub-graph sampling technique based on an cotrmationnthhoorde measure, information sufficiency, which quantifies the amount of information contained in a sub-graph with respect to whether predicate is true for some tuple of entities. Since the sub-graph sampling may violate the closed-world assumption (i.e., the information in a sub-sampled graph may be insufficient in predicting the relationship between a pair of entities), we also the information sufficiency measure to calibrate training labels. Third, to further speed up inference on large graphs, we encourage neural networks recover sparse relationships among objects by using a regularization term based graph sparsity measurements.
We evaluate SpaLoc two benchmarks: relational reasoning in synthetic datasets (family trees and general graph reasoning) and real-world knowledge-graph reasoning. First, we show that, with our sparsity regularization, the computation complexity for inference be reduced the same order as the optimal complexity, which significantly outperforms the base model NLM. Second, we show that training via sub-graph sampling and label calibration enables us learn relational rules in real-world knowledge graphs with more than 10K nodes, whereas the original NLM can be barely applied to graphs with more than 100 nodes. Finally, SpaLoc achieves state-of-the of-the-art performance on several real-world knowledge graph reasoning benchmarks.
2 SPARSE AND LOCAL NEURAL LOGIC MACHINES
In this section, we develop a structured neural network that applies to hypergraphs. The fundamental structures used for both training and inference, will be hypergraphs H = (V, E), where V is set of vertices and a set of hyperedges. Each hyperedge = (æ1, Z2, ..... xry) is an ordered tuple of elements (r is called the arity of the edge), where 2; V. We use f E - S to denote hyperedge representation function, which maps each hyperedge e to a feature domain S. Domain S can in various forms: discrete labels, numbers, and vectors. For simplicity, with arity-1 edges as "node features" and features associated with the whole graph as "nullary" or "global" features.
describe features associated
graph-reasoning task can be formulated as follows: given H and the input hyperedge representation functions I associated with all hyperedges in ε,, such as node types and pairwise relationships (e.g.. parent), our goal is to infer target representation function f for one or more hyperedges, i.c. f'(e) for some E E, such predicting new relationship (e.g., grandparent).
2.1 PRELIMINARY: NEURAL LOGIC MACHINES
We provide informal overview of the global architecture of Neural Logic Machines (NLMs); for a formal description, see the original paper by Dong et al. (2019). In contrast to typical graph neural networks that only associate representations with input edges in E, NLMs operate on fully-
2

---

Under review as a conference paper at ICLR 2022
Unary:
Qu
Index
porent
Index
PhO
Binary: R₁
Expand
Index
parent
PAD
parent' Pho"
Index
PRDchald
(1,3)
[1, 3)
Binary: Ro
(2, 3)
0
[2, 3)
parent
Index
parent PAD
(2. 4)
0
[2,4]
0
(1.2)
0
(1.2)
0
(2.3)
(2.4)
Rediace
(2,3)
(1.3
Permute
(4, 1)
(1,4)
NN
(1,4)
1)
4)
0
(4,2)
(4,2)
Input Domain:
(1,2)
0
(4.3)
0
(4,3)
0
()
(3. 1)
1
[3, 1)
0
1)
(3.2)
1
(3,2)
0
(4.2)
(2, 13
[2, 1)
(4.3)
(4,
(4,3)
Figure 2: A running example of a single layer SpaLoc; inferring the binary relationship of PhD-child- of from the attribute Phl) and the binary relationship parent. Blue entries denote values that reduced from high-arity tensors, while green entries are expanded from low-arity tensors. Yellow entries created by the "permutation" operation. Gray entries are zero paddings.
connected hypergraph. Thus, NLMs use dense tensors to represent the input, output and intermediate representations of relations on nodes, edges, and hyperedges.
For example, the input relation parent(z,, zz y) in given hypergraph H can be represented as 2D tensor parenty н of size N where = =IV] is the number of entities in the hypergraph, and parentyll (i = if and only if person is parent of j. In general, vector representation of length D associated with hyperedges of arity r can be represented using a tensor of size N" x D.
An NLM is a multi-layer neural network that operates on this dense hypergraph representation. At each layer, it computes a new set of features associated with the hyperedges based on the input. To fuse the information across hyperedges of different arities, NLMs two special tensor operations, EXPAND and REDUCE, which add and reduce dimensions of the representation tensors.
Remark. Even when the inputs have only unary and binary relations, allowing intermediate tensor representations of higher arity to be associated with hyperedges increases the expressiveness of NLMs (Dong al., 2019). An intuitive example that, in order determine the grandparent relationship, we need to consider all 3-tuples of entities, even though the input relations are only binary. Despite their expressiveness, NLMs based on hyperedges cannot be directly applied to large-scale graphs. For graph with more than 10,000 nodes (e.g.. Freebase (Bollacker et al., 2008)), is almost impossible to store vector representations for all of the 8 tuples of arity 3. Our key observation to improve the training and inference efficiency of NLMs is that relational rules are usually applied sparsely (Section 2.3) and locally (Section 2.4).
2.2 ARCHITECTURE OF SPARSE AND LOCAL NEURAL LOGIC MACHINES
Fig. shows the overall architecture of SpaL.o, which be seen version of NLMs based on sparse tensors. A Spal.oc model composed of multiple relational reasoning layers (RRLS) that operate on hyperedge representations. It also shows the detailed computation graph a single layer in a NLM with 3-ary relations. The EXPAND operation propagates representations from lower-arity tensors a higher-arity form (e.g., from each node the edges connected it). The REDUCE operation aggregates higher-arity representations into a lower-arid form (e.g., aggregate the information from all edges connected node that node). The PERMUTE operation fuses the representations of hyperedges that share the same set of entities but in different order, such as (A, B) and (B, A). Finally,
a linear layer with nonlinear activation that computes the representation for the next layer. The neural network module NN is applied independently and identically to all tuples the same arity. This ensures that a NLM learned on a small universe can be applied to a larger universe of entities.
Our RRLS are based on sparse tensor representations. the following, we let N = | be the number of entities (nodes) in the hypergraph, V = {01, .2. be the entities, 21, Ø2, be variables, and f( 22, ... x,,) be a mapping from a tuple (æ) Xy. ... xx,) to a vector representation associated with that tuple. We will denote the maximum arity of tensors considered in Spal model as R.
3

---

Under review as a conference paper at ICLR 2022
Sparse tensor representation of hyperedge representations. In SpaLoc, the vector representa- tions f Z2; :.. ;., associated with all hyperedges of arity r are represented as a coordinate-list (COO) format sparse tensor. That is, each tensor is represented as two tensors F (I. V). each with M entries. The first tensor is an index tensor, of shape M x r, in which each row denotes a tuple (x1, "2, , J. The second tensor V is value tensor, of shape M D, where D is the length of f( -.. ; Fr). Each row V[i] denotes the vector representation associated with the tuple [[i]] For all tuples that are not recorded in I, their representations are treated as all-zero vectors. As an example, in Fig. 2, the input relationship parent(r, v, y) is represented as sparse tensor with three entries.
Sparse relational reasoning layers. Now, we show how each of the critical operations of an NLM can be performed on this sparse representation.
The EXPAND operation takes a sparse tensor F of arity and creates new sparse tensor F' with arity r + 1: propagates the representation from arity r to arity (r + 1), such from nodes to edges. This is implemented by duplicating each entry / ["1,,... (rr in F. by N times, creating the N new vector representations for (Iı, ,I,, 0i) for all (1,2, ................................ .N. Fig. gives an example.
The REDUCE operation takes sparse tensor F = (1, V) of arity and creates a new sparse tensor F with arity r 1: it aggregates all information associated with all r-tuples: (I1, I2, :.. Ir-1, ?) with the same 1 prefix. In SpaLoc, the aggregation function is chosen to be max. Thus,
f'(1 [r-1) 2:(21," 21)
max
[II, 1T)
Fig. 2 gives example.
The PERMUTE operation takes a sparse tensor F of arity r' and creates a new sparse tensor F' of the same arity. However, the length of the vector representation will grow from D to D' r! x D. It fuses the representation of hyperedges that share the same set of entities. Mathematically,
f' -. Ir)
Concat permutation (s1,) [f .. ,,,11
(0f (af))
If a permutation of (I1, xr) does not exist in F, it will be treated as an all-zero vector. Thus, the number of entries M may increase or remain unchanged. Fig. gives an example.
The i-th sparse relational reasoning layer has R + 1 linear layers (s.0), ( (i. with nonlinear activations (e.g.. ReLU) as submodules with arities O through R. For each arity r, we will concatenate the feature tensors expanded from arity 1, reduced from arity + 1, and the output from the previous layer, apply permutation, and apply ( the derived tensor. In the concatenation step, since tensors from different sources may have different sets of entries, we will match the entries for different tensors with the necessary all-zero tensors.
We have seen how a sparse representation for NLMs can support efficient inference. In the next sections, we show how to learn sparse NLMs from graphs, and then how to use subsampling to learn efficiently from very large training graphs.
2.3 SPARSIFICATION THROUGH HOYER REGULARIZATION
Spal achieves sparsity during training by adding regularization terms entries that are not useful in making the target prediction. At each layer, for each hyperedge (æ1, ,,y), our model jointly predicts vector representation f(r).... , xr,) well as a hyperedge gate g xx, ) E [0, 1] During training, we modulate the input representation f with the gate value g; during inference, we prune all hyperedges whose gate value is smaller than scalar hyperparameter the task loss with sparsity regularization loss that encourages the network to prune as many edges as possible.
5%. We augment
Gated hyperedge representation. Recall that each sparse relational reasoning layer is composed of R + linear layers. In SpaLoc, for each linear layer L (6.r), we add linear gating layer, ((r) which has sigmoid activation and outputs a scalar value in range [0, 1] that can be interpreted as the importance score for each hyperedge. During training, we modulate the output of L (6r) with this importance value. Specifically, the output of layer i arity is I. (((r)) 1.6.)) (F), where F is the
4

---

Under review as a conference paper at ICLR 2022
input sparse tensor, and @ is the element wise multiplication operation. During inference, prune out edges with a small importance score.
Hoyer-Square measure. We metric inspired by the Hoyer measure (2004) for quantifying the sparsity of the hyperedges and as the regularization loss to encourage hyperedge sparsity. is based on the L norm and the L2 norm of vector. Let x be an arbitrary vector of length n. Then
C E. vn
Hoyer(a)
The Hoyer measure takes values from to 1. The larger the Hoyer measure of tensor, the denser the tensor is. In order to assign weights to different tensors based on their size, we use the Hlyer-SSqare measure (Yang et al., 2020),
(2 1i 1. Σ 2
Hs(
which ranges from (sparsest) to (densest). Intuitively, the Hoyer-Square measure is more suitable than I.1 or L2 regularizers for graph sparsification since it encourages large values to be close to and others to be zero, i.e., extremity. It has been widely used in sparse neural network training and empirically proved to have better performance than other sparse measures Hurley Rickard (2009). We also empirically compare Hs with other sparsity measures in Appendix C.
The overall training objective of SpaLoc the task objective plus the sparsification loss, Lrask + d where dieesity is the sum of the Hs for all gate tensors across all layers, divided by the sum of the size of these tensors:
R ddneitt E.ER Hs(g(t)))
((rr) =
(F)
Σ. #g(ir)
where sums over all layers the Spaloc and sums over all arities and # counts the number of elements in tensor.
2.4 SUBGRAPH TRAINING
Sample sub-domain from a large domain.
Calibrate information sufliciency.
IS
Large Domain
parent (teput)
Calibrated Sub-Domain
grandparent (Target)
Figure 3: The subgraph training contains two steps. First, we sample subset of nodes from large input graph. Next, calibrate the labels for edges in the sub-sampled graph. Note that the edge with information sufficiency O will be labeled as a negative example this subgraph.
Regularization enables us learn sparse model that will be efficient at inference, but does address the problem of learning efficiently from large training graphs. In this section we describe novel strategy for substantially reducing training complexity, based on the observation that an inferred relation among set of entities generally depends only on small set of other entities that are "hetween" the target entities in the hypergraph, in the sense that they are connected via short paths of relevant relations. To exploit this observation, we employ sub-graph sampling procedure during both training and inference. the following, we first present information-theoret the sufficiency of information in sub-sampled graph for determining the relationship between two entities, namely, information sufficiency. Next, we present a sub- bub-graph sampling procedure that is designed to maximize the information sufficiency for training and inference. Finally, since it is inevitable that we will lose some information during the sampling procedure, we further propose a training paradigm that calibrates the labels for training examples based on the information sufficiency.
measure to quantify
5

---

Under review as a conference paper at ICLR 2022
Information sufficiency. Hes = (Vs, Es) be sub-hypergraph of hypergraph 7/ EV, and e* = (81..... yr) be a target hyperedge in Hs. where yi..... y/r E Vs C V. Intuitively, in order to determine the label for this hyperedge. we need to consider all "paths" that connect the nodes (yn....,Uu>) .e). More formally, we say a sequence of K hyperedges
(2) " (0).
K F.
is a hyperedge path for nodes fyr.-. yr if and only if (. for all j. In graph with only binary edges, this is equivalent to the existence of path from one node yı to another node y/. We define the information sufficiency measure for a hyperedge e in subgraph Hs as the fraction of the total number of paths connecting (y..... Ye that are retained in the subgraph:
yr
UJ=1 ej and e, Nej+1 # 0
#Paths connecting (y1, ..)) Hs. # Paths connecting (",..... -Br) in 7
((y1,-.. ; Ur) Hs. H))
In practice, we approximate IS by only counting the number of paths whose length is less than task-dependent threshold r for efficiency. The numher of paths in a large graph can be pre-computed and cached before training, and the overhead of counting paths in sampled graph is small, so this computation does not add much overhead to training and inference. In the case that the input graphs have maximum arity 2, paths can be counted efficiently by taking powers of the graph adjacency matrix.
Subgraph sampling. We use different sub-graph sampling strategies for training and inference.
During training, each data point is tuple f') where H is the input graph, f is the input representation, and f' is the desired output representation. We will sample a subgraph Ht' c H. and train models to predict the value of f' on H' given f. For example, we will train models to predict the grandpurent relationship between all pairs entities in H'' based on the parent relationship between entities in H'. Thus, our goal is to find subgraph that retains most of the paths connecting nodes in this subgraph. We achieve this using a neighbor expansion sampler that uniformly samples a few nodes from V the seed nodes. It then samples new nodes connected with one of the nodes in the graph into the sampled graph and runs this "expansion" procedure for multiple iterations to get Vs. Finally, we include all edges that connect nodes in Vss to form the final subsampled hypergraph.
During inference, usually our goal is to just infer the relationship between one pair of entities I'(y,, y2) on a graph H given the input representation f. In this case, we will use path sampler when dealing with large domains, which samples paths connecting y1 and 1/2 and induce a subgraph from these paths. We provide ablation studies comparing different sampling techniques in Section 3.4. The implementation details of our information sufficiency computation and subgraph samplers can be found in Appendix and Appendix B.
Training label calibration with IS. Due to the information loss caused by graph subsampling, the closed-world assumption (CWA) no longer holds in the subgraph. That is, the information contained in the subgraph may not be sufficient to make predictions about target relationship. For example, in a family relationship graph, removing a subset of nodes may cause the system unable to conclude whether specific person has sibling.
Thus, we propose to calibrate the model training by assigning each example f'(y1,'.. ".) with a soft label. Specifically, consider binary classification task f'. That is, function f is a mapping from hyperedge tuple of arity {0, 1}. Denote the model prediction f². Typicallyy
will train the SpeLoc model with a binary cross-entropy loss between f' and the groundtruth f'. In our subgraph training, we will instead compute a binary cross-entropy loss between f' and fre @ IS, where Hg is the sub-sampled graph. Mathematically,
(fx @ 18) (y.,... yr)) e fiy (v...... .y)) ((V1.... v.) H.s H.)
Fig. 3 shows concrete example of the label calibration process.
is defined 1.

---

Under review as a conference paper at ICLR 2022
Table I: Results (Per-class Accuracy) on family tree reasoning benchmarks. Models are tested on domains with 100 objects. Minus mark means the model cannot scale up in training datasets of corresponding sizes or cannot handle ternary predicates.
Family Tree
MemNN
0IL.
NLM
Grall. (R-GCN)
Spal.oc (Ours)
Niain
20
2,000
20
2,000
20
2,000
20
2,000
20
2,000
EasFather
65.24
100
100
100
100
100
100
HasSister ster
66.21
100
100
97.05
97.95
100
97.97
Grandparent.
64.57
100
100
99.95
98.08
100
100
Uncle
64.82
100
100
97.87
96.50
100
100
MGUncle
80.93
100
100
54.67
71.29
100
Pamily-of- Three
100
100
Three-generation.
100
100
100
3 EXPERIMENTS
In this section, we compare SpaLoc with other methods in two aspects: accuracy and efficiency on large domains. We compare SpaLoc with other approaches on relational reasoning and real-world knowledge graph reasoning benchmarks. All experiments are under the inductive, supervised learning setup, i.e., testing objects and relations have not been seen during training, and the sizes of domains used for training and evaluation are also very different.
3.1 BASELINES
For the family tree reasoning tasks, we compare SpaLoc against four baselines. The first three are Memory Networks (MemNN) (Sukhbaatar et al., 2015), ôILP (Evans & Grefenstette, 2018) and Neural Logic Machines (NLMs; Dong et al., 2019), which are state-of-the-art models for relational rule learning tasks. For these models, we follow the configuration and setup in Dong et al. (2019). The fourth baseline is inductive link prediction method based on graph neural networks, Grall (Teru et al., 2020). Since Grall. can be only used for link prediction, we use the full-batch R-GCN (Schlichtkrull al., 2018), 8), the backbone network of Grall., for node property predictions. For inductive knowledge graph reasoning datasets, we compare SpaLoc with state-of- the-art models, including Neural LP (Yang et al.), DRUM (Sadeghian al.), RuleN (Meilicke et al., 2018), GralL and TACT (Chen et al., 2021). 1). For transductive learning tasks, we compare SpaLoc with four representative knowledge graph embedding methods, including TransE (Bordes al., 2013), DistMult (Yang et al., 2015), ComplEx (Trouillon et al., 2017), and RotatE (Sun et al., 2019).
3.2
FAMILY TREE REASONING
HasSistar
Grandparent
Unole
2.5
6.76"
2.5
0.0n"
2.0
2.5
NNZ (x10-)
NNZ
1.5
NNZ
0.5
L.5
0.5
3.5
0.5
20
60
60
80
190
130
140
25
10
10
103
123
140
20
40
60
80
100
1300 180
Number of Objjects
Number of Objects
Number of Objects
Figure 4: Numbers of non-zero elements (NNZ) in the intermediate groundings of SpaLoc vs. the number of objects in the evaluation domains.
We evaluate SpaLoc on the family-tree reasoning benehmark, a synthetic benchmark for inductive logic programming. The goal of family-tree tasks is to induce target family relationships member properties given the following binary relations: Son, Daughter: Father, and Mother. We give concrete logical definitions of the family tree benchmark in the Appendix E.
Accuracy Efficiency. From Table I we observe the superiority of SpaLoc in terms of accuracy and efficiency. Spal.oo oc achieves perfect accuracy on test set. And when handling large input domains
7

---

Under review as a conference paper at ICLR 2022
Table 2: Results (AUC-PR) on real-world knowledge graph inductive reasoning datasets from GralL.
WNI8RR
FBI TB15k-237
NELL-995
Model
v1
v2
v3
v4
v1
v2
v.
v4
v1
v2
v3
v4
Neural-LP
86.02
83.78
62.90
82.06
69.64
76.55
73.95
75.74
64.66
83.61
87.58
85.69
DRUM
86.02
84.05
63.20
82.06
69.71
76.44
74.03
76.20
59.86
83.99
87.71
85.94
RuleN
90.26
76.46
85.75
75.24
88.70
91.24
91.79
84.99
88.40
87.20
80.52
GralL
94.32
94.18
85,80
92.72
84.69
90.57
91.68
94.46
86.05
92.62
93.34
87.50
TACT-buse
98.11
97.11
88.34
97.25
87.36
94.31
97.42
98.09
94,00
94,44
93.98
94.93
TACT
96.15
97.95
90.58
96.15
88.73
94.20
97.10
98.30
94.87
96.58
95.70
96.12
SpaLoc
98.18
99.83
96.66
99.30
99.73
99.38
99.53
99.39
100
98.27
96.19
97.37
(Numin 2000), SpaL.c works well because of the sampling techniques, while most baselines cause
out-of-memory errors.
Sparsity. In Fig. 4, we show the number of non-zero elements in SpaLoc's intermediate groundings versus the size of input domains on HasSi ster, Grandparent rent and Uncle. We fit cubic polynomial equation
the data points to illustrate the learned inference complexity of SpaLoc. The SpaLoc use in these three datasets has arity of 3 the maximum capacity of the model is ((N*). However, the memory complexity of SpaLoc converges to the optimal algorithm complexity of these tasks, which is O( In comparison, the memory complexity of original dense NLMs will be fixed to O(N3) when the model architecture is fixed.
3.3 REAL-WORLD KNOWLEDGE GRAPH REASONING
We evaluate SpaLoc on the real-world knowledge-gun gradge-graphhhoo inductive reasoning bench- marks proposed in GralL, whose training and evaluation sets are disjoint sub-graphs al.,
Table 3: Results (AUC-PR) of transductive link prediction real-world knowledge graphs.
WN18RR
NELL-995
FB FB15K-253 237
extracted from WNI8RR (Dettmers 2018), FB15k-237 (Toutanova et al., 2015), and NELL-995 (Xiong et al., 2017). For each knowledge graph, there are four versions of inductive datasets with increasing sizes.
TransE
93.73
98.73
98.
DistMult
93.08
97.73
97.63
ComplEx
92.45
97.66
97.99
RotatE
93.55
98.54
98.53
Grall.
90.91
97.79
92.06
SpaLoc 96.76
99.27
99.61
To further demonstrate the scalability of SpaLoc, we also apply SpaLoc to the complete real knowl- edge graphs. SpaLoc still uses the inductive learning setting. That is, it does not use any entity information learned from training, only using the structural information for inference. We use the standard WN18RR, FB15K-237, 237, and NELL-995 benchmarks. We follow the original data split.
Table 2 and Table 3 show the results. SpaLoc significantly outperforms all baselines on all datasets and achieves a new state-of-the-art. This demonstrates SpaLoc's 's excellent scalability and generalization ability on noisy large-scale real-world data.
3.4 ABLATION STUDY
Table 4: Comparison of different samplers. Table 5: Comparison (per-class accuracy) for different label calibration methods.
N./N
Mode
Walk
Neighbor
Ace
MIS
Acc
MIS
Acc
MIS
HasFaLher
HasSisler
Sampler
20/50
100
54.82
100
85.14
89.78
LS
IS
LS
IS
20/200
100
33.05
100
71.51
100
80.60
20/500
58.18
27.27
100
78.22
100
78.70
Node
50.00
50.00
50.00
50.00
50.00
80.72
20 1.000
1.84
24.49
100
77.18
100
78.38
Walk
50.00
52.41
100
59.90
75.13
93.16
20 2,000
0
19.66
100
79.69
100
78.53
Naighbor
50.00
51.63
100
75.29
78.06
97.97
Subgraph sampling. Beside the neighhor expansion sampler, there are also some intuitive and efficient sub- sub-graph samplers, such as the random node (Node) and random walk (Walk) samplers proposed by Zeng et al. (2020). We compare these samplers in two ways. Empirically, we test the models trained with the samplers. Theoretically, evaluate the overall information sufficiency of sub-graph by averaging the information sufficiency of all target edges, introducing a metric called Mean Information Sufficiency (MIS).
In Table 4, we show the results on the Gr Grandparent dataset. The Node sampler does not leverage locality, the performance of models and MIS drops with the size of whole graph increases. Spal.ocs
8

---

Under review as a conference paper at ICLR 2022
trained with Walk and Neighbor samplers achieve perfect accuracies, and the MIS of sub sub-graphs provided by these sampers are also comparable. Also, the MIS of Walk's 's and Neighbor aororsss 's sub- graphs do not drop significantly with the increasing size of the whole graph, which ensures the application of these samplers on arbitrarily large graphs.
Label calibration. We compare our information sufficiency based label calibration method against simple constant label smoothing. We show results in Table 5. In the table, "LS" means constant label smoothing by multiplying positive labels with a constant a = 0.9, and "IS" means label calibration with the information sufficiency. The impact of sampling and the failure of the closed- world assumption is particularly significant on the two datasets HasFather and HasSis ittir. Without label calibration, the performance of the model trained on the sub-graphs is close to random prediction. Our informattion-bsed calibration method improves the performance by a large margin, and is significantly superior to naive smoothing techniques.
4 RELATED WORK
(Hyper- GGarh representation learning. (Hyper-)Graph representation learning methods, includ- ing message passing neural networks (Shervashidze et al., 201 I; Kipf Welling, 2017; Velickovic et al., 2018; Hamilton et al., 2017) and embedding based methods (Dettmers et al., 2018; Toutanova et al., 2015), have been widely used for knowledge discovery. Since these methods treat relations (edges) as fixed indices for node feature propagation, their computational complexity is usually small (e.g., O)) and they can be applied to large datasets. However, the fixed relation representation and low complexity restrict the expressive power of these methods (Xu et al., 2019; 2020) they cannot be used to solve some general complex problems, such as inducing tenary relational rules. Moreover, some of the widely used methods such knowledge embeddings are inherently transduc- tive, and cannot learn lifted rules that generalize to unseen domains. By contrast, relations in Spal loc are evolving for reasoning, and the architecture of SpaLoc can be adjusted for problems of different complexities. Therefore, SpaLoc can learn lifted and complex rules.
Inductive rule learning. In addition to graph learning frameworks, many previous approaches have studied how to learn generalized rules from data (Muggleton, 1991; Friedman et al., 1999), i.c., inductive logie programming (ILP), with recent work integrating neural networks into ILP systems to combat noisy and ambiguous inputs (Dong et al., 2019; Evans & Grefenstette, 2018; 18 Sukhbaatar et al., 2015). However, due to the large search space of target rules, computational and memory complexities of these models are too high to scale up to many large real-world domains. SpaLoc addresses this scalability problem by leveraging the sparsity and locality of real-world rules, and thus can induce knowledge with local computations and optimal complexities.
Efficient training and inference methods. There is a rich literature on efficient training and inference of neural networks. Two directions that relevant to are model sparsification and sampling training. Han et al. (2016) propose to prune and compress the weights of neural networks for efficiency, and Yang al. (2020) adopt Hoyer-Square regularization to sparsify models. Spal loc extend this sparsification idea by adding regularization at intermediate sparse tensor groundings to encourage concise induction. Chiang al. (2019) and Zeng et al. (2020) propose to sample sub- graphs for GNN training, and Teru et al. (2020) propose to construct sub-graphs for link prediction. SpaLoc generalizes these sampling methods to hypergraphs, and proposes the information sufficiency based calibration method to remedy the information loss introduced by sammliiniin.
5 CONCLUSION
We present Loc,.oc, framework for efficient training and inference of hypergraph reasoning networks. SpaLoc uses sparse tensors to represent high-order relationships (hyperedges), and implements finite- domain quantification to infer new knowledge. SpaLoc leverages sparsity and locality to train and infer efficiently. Through regularizing intermediate representation by sparsification loss, SpaLoc's inference complexities on family tree tasks are the same as those of algorithms designed by human experts. To be applied to large datasets, SpaLoc sample aub-graphs for training and inference, and calibrate training labels with information sufficiency measure to alleviate information loss. SpaLoc generalizes well on large-scale relational reasoning benchmarks.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
To maximize reproducibility, we described our methodology in detail in Section 2 and our experi- mental setup in Section 3. All the data and codes in this paper will be released upon publication to facilitate future research.
REFERENCES
Pablo Barceló, Egor V Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations (ICIR), 2020. 1
Peter W Battaglia, Razvan Pascanu, Matthew Lai, Danilo Rezende, and Koray Kavukcuoglu. Interac- tion networks for learning about objects, relations and physics. Advances in Neural Information Processing Systems (NeurIPS), 2016.
Kurt D. Bollacker, Colin Evans, Praveen K. Paritosh, Tim Sturge, and Jamie Taylor. Freebase: collaboratively created graph database for structuring human knowledge, Jason Tsong-Li Wang (ed.), ACM SIGMOD Conference Management of Data (SIGMOD), 2008. 3
Antoine Bordes, Nicolas Usunier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems (NeurIPS), 2013.
Jiajun Chen, Huarui He, Feng Wu, and Jie Wang. Topology-aware correlations between relations for inductive link prediction in knowledge graphs. In AAAI Conference on Artificial Intelligence (AAAI), 2021. 7
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In ACM SIGKDD International Conference Knowledge Discovery and Data Mining (KDD), 2019. 9
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In Sheila A. Mcllraith and Kilian Q. Weinberger (eds.), AAAI Conference on Artificial Intelligence (AAAI), 2018. 9.
Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural logic machines. In International Conference on Learning Representations (ICLR), 2019. 2, 7, 14
Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. Journal of Artificial Intelligence Research, 61:1-64, 2018. 7,9
Nir Friedman, Lise Getoor, Daphne Koller, and Avi Pfeffer. Learning probabilistic relational models.
In International Joint Conference on Artificial Intelligence (IJCAI), 1999.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2017. 9
Song Han, Huizi Mao, and William J. Dally. Deep compression: Compressing deep neural network with pruning, trained quantization and huffman coding. In Yoshua Bengio and Yann LeCun (eds.), International Conference Learning Representations (ICLR), 2016. 9
Patrik O. Hoyer. Non-negative matrix factorization with sparseness constraints. J. Mach. Learn. Res., 5:1457-1469, 2004.
Niall P. Hurley and Scott T. Rickard. Comparing measures of sparsity. IEEE Trans. Inf. Theory, 55
(10):4723-4741, 2009. 5
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015. 13
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations (ICLR). OpenReview.net, 2017. 9
10

---

Under review as a conference paper at ICLR 2022
Christian Meilicke, Manuel Fink, Yanjie Wang, Daniel Ruffinelli, Rainer Gemulla, and Heiner Stuckenschmidt. Fine-grained evaluation of rule- and embedding- basedd systems for knowledge graph completion. In The Semantic Web ISWC 17th International Semantic Web Conference, Monterey, CA, USA, October 8-12, 2018, Proceedings, Part 1, 2018. 7
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI Conference on Artificial Intelligence (AAAI), 2019.
Stephen Muggleton. Inductive logic programming. New Gener. Comput., 844):295-318, 1991. 9
Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. DRUM: end-to-end differentiable rule mining knowledge graphs. In Advances in Neural Information Processing Systems (NeurIPS).
Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In The Semantic Web (ESWC), 2018. 7
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-lehman graph kemels.. J. Mach. Learn. Res., 12:2539-2585 22661, 2011. 9
Sainbayar Sukhbaatar, Arthur Szlam, Jason Weston, and Rob Fergus. End-to-end memory networks. In Advances Neural Information Processing Systems (NeurIPS), 2015. 7,9
Zhiqing Sun, Zhi-Hong Deng, Jian Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by
relational rotation in complex space. In International Conference on Learning Representations (ICLR), 2019. 7
Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. In International Conference on Machine Learning (ICML., 2020. 7, 9
Kristina Toutanova, Danqi Chen, Patrick Pantel, Hoifung Poon, Pallavi Choudhury, and Michael Gamon. Representing text for joint embedding of text and knowledge bases. In Lluís Mårquez, Chris Callison-Burch Jian Su, Daniele Pighin, and Yuval Marton (eds.), Empirical Methods in Natural Language Processing (EMNLP), 2015. 8,
Théo Trouillon, Christopher R. Dance, Éric Gaussier, Johannes Welbl, Sebastian Riedel, and Guil- laume Bouchard. Knowledge graph completion via complex tensor factorization. Journal of Machine Learning Research, 2017.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018.
Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. In International Conference Learning Representations (ICLR), 2020. 1
Wenhan Xiong, Thien Hoang, and William Yang Wang. Deeppath: A reinforcement learning method for knowledge graph reasoning. Martha Palmer, Rebecca Hwa, and Sebastian Riedel (eds.), Empirical Methods in Natural Language Processing (EMNLP), pp. 564-573. Association for Computational Linguistics, 2017.3 8
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? International Conference on Learning Representations (ICLR), 2019. 9
Keyulu Xu, Jingling Li. Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? International Conference Learning Representations (ICLR), 2020. 9
Bishan Yang. Wen-tau Yih, Xiaodong He, Jianfeng Gao. and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. International Conference on Learning Representations (ICIR), 2015.7
11

---

Under review as a conference paper at ICLR 2022
Fan Yang. Zhilin Yang, and William W. Cohen. Differentiable learning of logical rules for knowledge base reasoning. In Advances in Neural Information Processing Systems (NeurIPS).
Huanrui Yang. Wei Wen, and Hai Li. Deephoyer: Learning sparser neural network with differentiable scale-invariant sparsity measures. In International Conference on Learning Representations (ICLR), 2020. 5,9 9
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. In International Conference on Learning Representations (ICLR), 2020. 8,9
12

---

Under review as a conference paper at ICLR 2022
SUPPLEMENTARY MATERIAL
A EXPERIMENTAL CONFIGURATION
Table 6: Hyper-paramene for SpaLoc. The definition of depth and breadth are illustrated in Figure 1.
Tasks
Depth
Breadth
Hidden Dims
Batch size
Subgraph size
HasFather
5
8
20
HasSister
5
8
20
2
Family Tree
Grandparent
8
20
2
Uncle
5
8
20
2
MGUnccle
8
20
2
Fami -yml-yyofthhre
8
20
Three-generation..
8
20
2
WN18RR
128
Inductive
FB15K-237
64
KG
NELL-995
128
Transductive KG
NN_ 8RR
6
64
64
20
3
FB1 2B-5K-237
6
64
64
20
3
NRT.1.-9955
64
64
20
3
We optimize all models with Adam (Kingma & Ba, 2015) and use an initial learning rate of 0.005. All experiments are under the supervised learning setup, we use function.
-rross-Entrpyy as loss
Table A shows papeee-prrmeterss used by SpaLoc. For all MLP inside SpaLoc, we use no hidden layer and the sigmoid activation. Across all experiments in this paper, the maximum arity of intermediate predicates (i.c., the "breadth") is set to 3 as a hyperparameter, which allows SpaLoc to realize all first-order logic (FOL) formulas with at most three variables, such "transitive relation rule." We set the specification threshold e to 0.05 in all our experiments. This value is chosen based on the validation accuracy of our model. In practice, not significantly impact the performance of our method and the inference complexity. We also set the multiplier of the sparsification loss À to 0.01 in all SpaLoc's experiments.
observe that any values between 0.01 and 0.1 do
B IMPLEMENTATION OF SUBGRAPH SAMPLERS
Both the neighbor expansion and the path sampler sample subgraphs by inducing from selected node sets. To deal with input hypergraphs with any arities, the samplers simplify the input hypergraphs into binary graphs. We define two nodes in the hypergraph hyperedge. Therefore, the neighbor expansion and path finding algorithms used by the samplers can be applied to any hypergraphs for finding node sets. After enough nodes collected, the sampler will induce a sub-hypergraph from the original hypergraph by preserving all of the hyperedges lying in the set.
connected if they are covered by
C ABLATION STUDY SPARSIFICATION LOSS
Table 7: Comparison of different sparsification losses.
HasSister
Grandparent
Uncle
Accuracy
Density
Accuracy
Density
Accurcay
Density
T
91.81
0.48%
99.8% 100%
0.99%
74.69%
0.68%
T
100
0.75%
0.61% %
94.46%
2.44%
Hs
100
0.51%
100%
0.48%
100%
0.87%
13

---

Under review as a conference paper at ICLR 2022
We compare Kloyer-Square sparsification loss against the L1 and L2 regularizers the family tree datasets. In Table 7, we show the performance of SpaLoc trained with different sparsification losses. All models are tested domains with 100 objects.
"Density" is the percentage of non-zero elements (NNZ) in the intermediate groundings. The lower the density, the better the sparsification and the lower the memory complexity. We see that, compared with L and L2 regularizers, the Hoyer-Square loss yields a higher or comparable sparsity while maintaining the nearly perfect accuracy.
D CALCULATION OF THE INFORMATION SUFFICIENCY
The erucial part in the computation of the information sufficiency is count the number k-hop hyperpaths connecting a given set of nodes (V1,... UU,..... 6r) in hypergraph. We use the incidence matrix to calculate this. Firstly, we use a n x m incidence matrix B represent the hypergraph H (V,&), where = [ and = [&), such that Bij = if the vertex and edge e, are incident and 0 otherwise. Next, (*)) (BBT)*~1 k B is the k-hop incidence matrix of the hypergraph, i.e.,
((b) the number of k-hop paths that the vertex v and edge Ej are incident.
1)
For example, when r = 2, there are B((h BJ k-hop paths connecting vertex i and vy. When r there are Ej B(b)) k-hop paths connecting to vertex Us.
E DEFINITION OF RELATIONS IN FAMILY TREE
The inputs predicates are: Father Mother(r, y). Son Daughter(z,y).
The target predicates are:
HasFather(s) == 3a Father(z,
HasSister(1) Rohl Father(z,a) (a -(b
Grandpareen((r.p ia (z { pareettt) parent(s,y)
VM
Uncle(x, 3a (zandpareent(2. Son(a) A -Father(z,
MGUncle(r. y) Ea3b Crandmotther(2..))A
Son(b.y)
Grandmother(z..) = 3a Parent(a:.))
Famlly-of-three(r... = Fat==aaaheerrrree (
Three-generationti ,, Parent A Parent(y,
We follow the dataset generation algorithm presented Dong et al. (2019), In detail, we simulate the growth of families to generate examples. For each new member of the family, randomly assign gender and a pair of parents (can be none, which means it the oldest person in the family tree) for it. After the family tree is generated, we label the relationships according to the definitions above.
F EFFICIENCY ANALYSIS
We compare the time and memory complexity of SpaLoc against NLM the Has-Sister and Grandparent tasks. In Fig. 5, we plot the curve of memory consumption and inference time of each sample as a function of the number of objects in the evaluation domains. The experimental results show that our method can reduce the space complexity from the original ((n²) complexity of NLM the O(n²) complexity required solve the has-sister and grandparent task. In terms of the inference time, there is a constant level of optimization. On small graphs, adding sparsity does not necessarily improve the running time on GPUs because of the overhead of handling sparse tensors due to the implementation. More efficient implementation of sparse operations is interesting future work.
14

---

Under review as a conference paper at ICLR 2022
Bis Stater
His State
Grundprrast
tie-10
40
Spatas
Jenasste wase wette 544033
04
110 550
120
102
100
O2jects
Dojects
Number Objeeds
Figure 5: The memory consumption and the inference time of each sample vs. the number of objects in the evaluation domains.
15

---

Under review as a conference paper at ICLR 2022
G IMPLEMENTATION OF SPALOC IN PYTORCH
The following python code is a minimal implementation for a single layer SpaLoc with PyTorch and "torchsscatter. The syntax is highlighted and is best viewed in color.
from itertools import permutations
import SparseTensor import torch
from torch import nn
import scatter import math
from
def expand (input: SparseTensor) :
"#"xxands a new dimension in input by duplicating each entry for times "*"
coo (input. coo. unsqueeze (-1) input.n) +
torch.arange (input n) unsqueeze (0)
val input. wul.ueeeeeeee (1) expand (input length, input.n,
~ input.channed
(-1, val val.conti () vview (-1, input. return SparseTensor (val, input.n, input.arity 1,
14
input. channel, coo=coo. flatten ())
15
17
def reduce (input: SparseTensoz) "**Reduces max at the last dimension, except for elements whose coordinates contain duplicate objects.
21
val input. val. clone()
val [reduce_maeee (input)] = -math. inf flatten_indes
23
Input.coo // input.n coo, inverse_index torch.unique (flatten_index,
+ return_inverse-Trie sorted-True)
val scatter (val, inverse_inder dim=0, aeduce='max" return SparseTensor (val, input.n, input.dim - 1, input. channel, coo=cco)
36
27
29
def neural_logia (input, hidden_dim):
30
"""An MLP layer applied on permutations of the input. ""* return MLP (permute (input), hidden_dim, activation=nn. act.vattoonnnn.simoii(()) (igmoid
31
33
def baaloc_breatht (input0, inputl, input2, input3, hidden_dim) """А SpaLoc layer with breath
35
Args:
37
input0: SparseTensor of shape [hidden_dimg nullary predicates:
38
inputl: Teasse of shape [N, hidden_dim), unary predicates.
19
input2: SparseTensor of shape [N, N, hidden_dim). binary predicates.
hhtps//gitthhh.co///ayy//yyyyo scatter
16

---

Under review as a conference paper at ICLR 2022
1nput3: SparseTensor of shape (N, N, N, hidden_dim) tenary predicates.
hidden_die dim: int, hidden dimension.
42
Returns:
4 SparseTensors, output nullary, unary, binary tenary
predicates respectively.
agg0 concat ([inputo, reduce (input1)
46
aggl concat ([inputl, expand (input0), reduce (input2) ])
agg2 concat ([input2, expand (inputl), reduce (input3) agg3 concat ([input3, expand (input2)])
48
outputs [reural_logic hidden_dim) for in [agg0, aggi,
agg2, agg3]]
return outputs
51
53
def reduce_mask (input):
mask torch. zeros (input. length, dtype coo input. coo
56
for range (input (input.arity) arity):
for j in range (i+1, input input.dim):
return mask 58
mask torch. logical_oooo (mask, cool:, i] cool:, il)
60
62
def
permute (input): if input diim <= 1:
64
return input
index tuple (range (0, Input.dim)
66
coo = input. ()
67
weight torch. ten.or ([ .n for i in
reversed (range (input }]])
68
ts []
for in permutations (index)
70
new_coo (weight cool:, p]).sum (-1)
aa.append (SparseTensor (input. val, input. n,,
72
input. input.channei. channel, coo-new_co))
73
return input. cat (ts)
75
def concat (inputs)
nnzs It. length for in inputs]
77
= inputs [0].n
78
dim inputs [0] dim
channel = ([t channel for t in inputs])
sum([tccaanee
30
coo torch. cat (It.coo for t in inputs], dim=-1) coo, inverse_index torch.unique. sorted=True)
82
coo, return val torch. (len channel))
84
current_channell current_idx 0,
for idx, t in enumerate (inputs)
%6
next_channel, next_idx = current_channel t.channel, 4 current_idx Eelegth
87
ourrent_chaamellneetcccanneee current_channel, current_ixx next_channel, next_ide return SparseTensor (val, n, dim, channel, coo-c0o)
t.val
17


Reviews:
[{"review_id": "tPZWrIo2ERd", "reviewer": "Reviewer_QNYc", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths and weaknesses\nStrengths:\n- The experiments in section 3.3 show strong predictive performance improvements over previous works\n- Both the sparse tensor representation and the sub-sampling are interesting and sound methods for reducing the memory footprint of NLM during training\n- The information sufficiency term for two nodes is computed as the fraction of hypergraph-paths that are retained in the sampled hypergraph, where a hypergraph-path generalizes the notion of paths in graphs to hypergraphs. This is a reasonable way to quantify the amount of information that is lost during sampling and the ablation demonstrates the effectiveness of using this during training.\n- The paper is well written and legible for the most part.\n\nWeaknesses:\n- The premise of the paper is: training with many entities at once (20 vs 2000) is necessary or beneficial. This is not obvious, nor is it supported theoretically or empirically in the paper. For example, the experiment in section 3.2 compares against NLM by testing on 100 entities, when trained on 20 and 2000 entities. Since training with 20 entities already leads to perfect accuracy for NLM, it is not obvious why one would want to train with more. Furthermore, training the proposed model with more entities actually degrades the performance of the “HasSister” class.\n- Section 3.3 “Real-world knowledge graph reasoning” does not describe the experimental setup, so I assume the experiments were done using the same setup as described in [Teru et al., 2020]. According to their description, this task is inductive in the entities only (nodes) and not the relations (edge types), meaning that there are no new relations in the targets. This setting is markedly different from the experiment in 3.2 and requires explicit mention and discussion.\nFurthermore, it is not obvious why NLM would not work in section 3.3 by training on smaller input sizes and extrapolating to larger test sizes.\n- Section 2.3 presents a method that encourages sparsity in the intermediate and output hypergraphs. The paper claims that this speeds up inference on large graphs, without any further explanation or validation. An ablation and further discussions on the trade-offs are necessary to motivate the importance of the methods presented in this section.\n- The Hoyer-Square measure is presented as a better sparsification loss than the Hoyer, L1, and L2 alternatives, without any empirical support. An ablation would help convince the reader.\n- The information sufficiency (IS) term takes the hyperparameter tau that determines the maximum path length that is still considered in the computation of IS. This appears to be a crucial value to set correctly and warrants further discussion on how to pick it and mentions of the concrete values used in the experiments.\n\n## Additional Feedback and Questions\n- Much of the paper is written with the assumption that the reader is familiar with the NLM paper, making it less accessible to a broader audience. Some example points that should be explained in the paper: What are lifted rules? What are the hyperedge feature domains considered in this work? What are the S and D typically? What is the arity of considered relations and the intermediate layers.\n- There are many details on the method and the experimental setups missing that require explanation in the paper or appendix. For example: What is gF in “... in gF by N times, creating …”? How does M change with the PERMUTE operation? What are the f_hat’s in Figure 4?\n- The proposed method appears to beat previous methods on most benchmarks, but it is not clear why. One way to provide more clarity is to describe the most significant differences of the proposed approach with the baselines.\n- The introduction claims that the NLM scales exponentially with the number of entities and presents a cubic example O(N^3) (that is not exponential in N). The exponential scaling claim appears wrong and should be polynomial instead.\n- Miscellaneous: \n  - “Fig 1b”: there is no b\n  - “L_g^(i,k)”: k should be r\n  - “Let x be an arbitrary vector”: x_1, x_2, ... were already defined as the variables\n  - “g^(i,r)”: this variable wasn’t introduced anywhere\n  - “Sequence of k hyperedges”: mixing k and K here\n  - Different notations (H’ and S) for the sampled hypergraph\n  - “Label calibration..”: two dots \n", "summary_of_the_paper": "This paper considers the task of inductive relation prediction: given a set of entities and relations, predict new types of relations. A specific example is: given a collection of people and the “is parent of” relation, predict the “is grandparent of” relation. The main contribution is a memory-efficient training and inference method for the Neural Logic Machines (NLM) [Dong et al., 2019]. For this, the paper presents a sparse tensor representation for the relations and add a loss term that encourages sparsity in intermediate layers and the output. Training on hypergraphs with many entities becomes computationally tractable (presumably on memory-limited GPUs), by sub-sampling the hypergraph (that represents the entities as nodes and relations as hyperedges). To deal with the situation in which vital nodes or hyperedges are removed during sampling, the paper introduces information sufficiency, a quantity used to scale the ground-truth labels.", "summary_of_the_review": "I recommend rejecting the paper: It is currently not apparent why one would want to use many entities during training, when it’s possible to train with few entities and extrapolate to many at test time. Furthermore, the good results reported in section 3.3 seem irrelevant, since the experiment actually performs a different task from \"relational rule induction\".\n\nThe paper contributes to a specific line of research, by extending the NLM [Dong et al., 2019] to larger input sizes. In general, the paper would significantly benefit from more justifications and explanations for the proposed methods. More details on the experiments are also essential for the reader to understand the results. The technical contribution consists of a combination of different existing methods or variations thereof, and the information sufficiency value which appears to be new. \n\n---\n\nI thank the authors for the rebuttal and the additional ablation study and details on the hyperparameter tau. I keep my score at 3, because in my opinion the need of training with larger input graphs is insufficiently covered. In particular, the datasets reported in Table 2 are based on *sub-sampled* graphs, as described in Appendix F of [Teru et al., 2020]. This means that it is possible to train NLM on the KG datasets considered in this work, by simply applying the same sub-sampling strategy with fewer roots. The new results in Table 3 also do not support this point, since it looks like that training with the complete KG (instead of subgraphs v1, v2..) does not improve the performance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "pCem9WxrBtQ", "reviewer": "Reviewer_emhK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths:**\n1. Successfully able to scale NLM and demonstrate its effectiveness on 2 large-scale tasks.\n2. Employ heuristics to encourage sparseness and efficient training: demonstrated through ablation as well. \n3. Quantification of information content in a subgraph, and efficient subgraph sampling based on it.\n\n**Weaknesses:**\nMy main concern is with the experiments in the paper. Please see the ‘summary of the review’ for the details.\n", "summary_of_the_paper": "This paper presents a neural network, SpaLoc, which claims to improve the scalability of an existing architecture, Neural Logic Machines (NLM) (Dong et al). \nThe main idea of this paper is to exploit the sparseness of k-arity relationships that are represented as k dimensional dense tensors in Dong et al.  SpaLoc instead records the indices of non-zero entries and represents k-dim tensors as an (Index, Value) tuple (I,V) of 2 dimensional tensors, and redefines all the operations (Reduce, Expand and Permute) of NLM to suit the (I,V) representation. \nIt applies an auxiliary loss term to ensure sparseness of the intermediate as well as the final relationship learnt. \nFinally, for efficient training (and inference), it relies on subgraph sampling techniques that are based on preserving the information content required to make a prediction. While training, they calibrate the prediction target based on the information lost due to subsampling.\nThey experiment on 2 tasks: synthetic family tree reasoning task, and  Knowledge Graph (KG) reasoning tasks. On synthetic data, they show that the original NLM fails to scale on very large families and a GNN based baseline (R-GCN) performs worse than SpaLoc. On inductive KG reasoning, it beats the existing methods.\n", "summary_of_the_review": "It’s an incremental work, focused on scaling an existing method by converting a dense representation into a sparse representation. \n\nEven though the theory is for generic arity, the experiments involve only binary relations, and hence many complex GNN based methods can be used in addition to R-GCN. For example, Recurrent Relational Networks (RRN)  (Palm etal 2018) that work very well for multi-hop reasoning and scale well across the size of the graph.\n\n**Running time:**  For the sparse (I,V) representation, how are the three basic operations (Reduce, expand, permute) performed using fast tensor operations on GPU? In my understanding, one downside of sparsifying the tensors is: indexing now needs to be handled separately, and can’t be done using fast GPU tensor operations. All the three basic operations of NLM may require dictionary lookups done on CPU, instead of GPU. Hence, even though sparse tensors for very high arity may now fit in the GPU memory, performing basic NLM operations may require frequent interaction with CPU, and hence dramatically increasing the training / inference time.  Can you provide a comparison of the running times of different baselines with that of SpaLoc?\n\nExperimental details are missing. For example, what is the maximum arity used in the intermediate layers for KG experiments? How many layers for both tasks?\nMany baselines have not been cited or mentioned, except the acronym in the table (e.g. TACT in table 2). \n\n**Clarification Questions:**\n\n1. *Subgraph sampling:* The description for both sampling techniques (neighbor expansion and path sampler) focuses on 2 arity edges.\nSpecifically, in neighbor expansion, it appears that node set is expanded based on only binary relations? Are relations with higher arity used when expanding the node set? In path sampler, do you consider paths via edges of higher arity?\n\n2. On page 6, under **Subgraph Sampling**:  \"*During inference, usually our goal is to just infer the relationship between one pair of entities:*\" In its original form, NLM would predict the relationship between all pairs of nodes as it works with dense representations. In SpaLoc, don’t we get all the non-zero entries, in the tensor of the desired arity, all at once in the forward pass?\n\n3. *Section 2.3:*  How do you select hyperparameter \\epsilon = 5%?\n\n4. *Ablation study:* there is no ablation on ‘sparsification loss’. How important is it?\n\n\n**Typos**\n\n1. Page 2, Line 6: whether a predicate is true **for** some tuple of entities.\n\n2. Section 2, 2nd line: why is V a  tuple?\n\n3. Figure 2, Last row in the output of Permute and NN should be (3,4) and not (4,3)\n\n4. References to Figures say Fig1b, Fig2b, but there are no parts a and b of the figures. For example, in the 1st line of section 2.2.\n\n5. Section 2.2, page 4, in the 3rd line of the paragraph describing ‘EXPAND’, what is gF?\n\n6. Section 2.2, page 4, equation in the description of ‘REDUCE’: if output of f is a vector, then shouldn’t it be a max pool (max across each dimension), instead of just max?\n\n7. Page 4, last word: superscript should be (i,r) instead of (i,k)\n\n8. Page 6, Information Sufficiency: You have defined S = (V_S, E_S), but you refer to S as H_S subsequently. Also, in the hyper-edge path, the subscript on the last node of the 2nd edge should be r_2 and not r_1.\n\n9. Section 3.4: Ablation Study: it should be mentioned that all ablations are on synthetic family tree reasoning tasks.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "iRMQVwUQNi6", "reviewer": "Reviewer_joDw", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "strengths:\n1) The study is based on a very nice observation that in logical reasoning we don't usually consider all entities but rather a local set of them, and the authors developed a novel method motivated by this observation that could improve efficiency by a lot.\n2) the methods are sensible, from the sparse tensor representation to subgraph sampling to label calibration, all of which I can follow intuitively.\n3) the experimental results looked very strong, especially on the synthetic datasets, which solved a large amount of instances that could not be solved by other methods given a fixed amount of memory budgets.\n\nweakness:\nThe main problem I have for this paper is its presentation.  Specifically, the authors should improve on describing their methods and there is a lack of very important details in the experiments (even in the main part).\n1) In figure 1(i), it's hard for me to tell why I+V should have a fixed length..  the first dimension of V decreases when the first dimension of I increases?\n2) One of the most important claims in the paper is efficiency.  However, the authors are missing key details: for example, when the baseline methods hit OOM, what memory budgets did the authors put?  The authors also claim efficient inference time in various places, but not single empirical evidence is presented in the experiments section.\n3) The new method achieves such amazing results on the synthetic datasets, but no single details are presented on the dataset was generated.\n\nsmall comments:\n1) the authors refer to fig 1b and fig 2b, but in both the figures, there are no sub-labeling\n2) In fig 1, it's better add caption explaining what are I and V matrices", "summary_of_the_paper": "Motivated by an observation that in logical reasoning, rules only apply locally and sparsely to a small set of entities, the authors propose Sparse and Local Neural Logic Machines (SpaLoc), a structured neural network for hypergraph reasoning. In particular, this paper has three contributions:\n\n1) the authors developed a way to do sparse tensor representation to alleviate the computation burden in NLM\n2) use hyperedge gates to enforce sparsity and impose sparsity-related loss\n3) a novel strategy to do subgraph sampling that leverages a metric they invented called information sufficiency\n\nAlso showed positive experimental results compared to baseline methods and provided some ablation studies.", "summary_of_the_review": "The paper is strong overall in terms of novelty of the methods and good main experimental results.  However, I would really like the authors to improve on the presentation of this paper.  In general, I lean towards accepting this paper, but in order for me to improve the score I need to see more details on their new methods are efficient in terms of time and memory and how the synthetic dataset is generated.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "TlVmjue4Z2r", "reviewer": "Reviewer_GMNn", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "As stated in the summary, this work proposes an NLM variant that seeks to solve the scalability issue. The proposed techniques are: using sparse representation, applying sparsity regularization, and using sub-graph sampling. These techniques do not pose significant changes to the original NLM model nor extend the model's capability in learning new classes of patterns. Furthermore, the techniques are specifically designed for the NLM, limiting the scope of this work. With that being said, I consider this work more or less incremental whose contribution is minor and limited. Therefore, I'm inclined to reject. My detailed comments are as follows:\n\nThe paper is difficult to read if the reader is unfamiliar with the NLM model\n - While this paper proposes a direct variant of NLM, it omits too many details on the original model. Personally, I'm not hindered by the writing as I'm familiar with NLM, but this is generally not true for most of the audiences with general KG background knowledge.\n - For example, section 2.2 introduces the EXPAND, REDUCE and PERMUTE operations but does not point out these operations are from NLM and why they are needed for KG reasoning.\n\nHow is the sparsity threshold epsilon set? Do authors run a grid search and set it to 5%?\n\nWhat is N_train in section 3.2?\n\nAs the aim of SpaLoc is to address the scalability issue, the author should design the experiments around the scalability analysis. For example, besides Table 2, the author could provide the runtime comparison of each method. On the other hand, while I understand the authors choose to use the disjoint subset of FB15K and WN18 from (Teru et al., 2020) for inductive reasoning, the datasets are significantly smaller than the original benchmarks. For example, the largest dataset FB15K v5 only contains 5K nodes and 33K edges whereas the original FB15K contains 14K nodes and 272K edges. As the focus of this work is scalability rather than inductive capability, it is crucial to push the proposed method to its limit and evaluate it in a realistic setting.\n", "summary_of_the_paper": "This paper proposes SpaLoc a Neural Logic Machine variant that improves the model scalability on the graph completion tasks. To do this, the authors 1) replace the original dense representation into sparse tensors; 2) apply a sparsity regularization on the original loss function; 3) propose a sub-sampling strategy that reduces the training complexity. The proposed method is evaluated with a set of differentiable ILP methods and GNN methods. Ablation studies are conducted to analyze the effectiveness of the proposed techniques.\n", "summary_of_the_review": "In summary, SpaLoc is an incremental variant of the NLM model. The contribution is minor and limited to the specific NLM model. Therefore, I recommend rejection.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "8l8B5OJGwTF", "reviewer": "Reviewer_Rg6r", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. Developing models for hyperrelation is interesting and under explored. The main contribution of paper is to make neural logic machines practical and scalable which is important\n2. The method is well-motivated. For example, the use of Hoyer measure and subgraph sampling and training with information sufficiency is interesting and makes sense\n3. They achieve good results on a synthetic and few real world KG benchmarks\n\nQuestions for authors:\n\n1. The current experiments (relation extraction) and family tree are all finding a binary relation between a pair of entities. Since the method is developed for hyperedges, why is there not an experiment where the goal is to infer relations between more than a pair of entities?\n2. How is the arity set? For example, for the family tree experiemnts, how did you come up with value 3? Is it set as a hyperparameter. \n3. In table 1, why does not memory networks scaled to 2000 objects? Is this an implementation issue?\n4. In table 1, what does tested on 100 objects mean? I thought the number of objects are 20 and 2000?\n5. I think the writing of the paper needs to significantly improved. For example, Figure 1 is very hard to understand for a reader who is not familiar with NLMs. Also readability of Figure 2 can be improved by adding proper captions as that is the main figure explaining the mechanism of the model.", "summary_of_the_paper": "This paper proposes extensions of Neural Logic Machines (NLM, Dong et al 2019) to make them more scalable. NLMs operate on dense hypergraph representations. Since the space requirement is exponential in terms of number of entities, NLMs become quickly intractable as the number of entities increase. To remedy this, this paper proposes a sparse tensor based representation for hyoeredge. The expand, reduce and permute operations are also defined for sparse tensors. To achieve sparsity in training, they include a sparse regularization objective (based on Hoyer measure). Lastly, they also employ a subgraph sampling technique based on information sufficiency. \n\nOn synthetic family tree relationships, the proposed model solves the dataset and is the only model that scales to 2000 entities. Moreover they achieve the optimal sparsity (quadratic).", "summary_of_the_review": "This is definitely interesting work and I think efficiently modeling hyper-edges is important. However, currently, the paper is very dense to read and needs to be improved. I would also like to see an experiment on inferring relations that exists between more than a pair of entities. \n\n=====Update 11/26=======\n\nThank you for the rebuttal. I am keeping my score to weak accept. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper has conflicting reviews with no strong advocate.  One of the positive reviewers states the caveat that paper is "very dense to read and needs to be improved".  Having looked at the paper myself I would agree with this criticism.  One of the negative reviewers states that the paper gives "an incremental variant of the NLM model".  I am less confident in this judgement.  However, I find the density of the paper and the use of synthetic data to be significant drawbacks. With the lack of any real champions for the paper I do not see a path to acceptance.
Decision: Reject