1 Introduction
2 State-of-the-art
3 The intuitions
entity pair | (sociology, George Washington University) |
---|---|
relation | /education/field_of_study/students_majoring./education/education/institution |
relation paths | a: /education/field_of_study/students_majoring./education/education/student \(\rightarrow \) /people/person/education./education/education/institution |
b:/people/person/education./education/education/major_field_of_study\(^{-1}\rightarrow \)/education/educational_institution/students_graduates./education/education/student\(^{-1}\) | |
entity pair | (Planet of the Apes, art director) |
relation | /education/field_of_study/students_majoring./education/education/institution |
relation paths | a: /film/film/sequel \(\rightarrow \) /film/film_job/films_with_this_crew_job./film/film_crew_gig/film\(^{-1}\) |
b: /film/film/prequel\(^{-1}\)\(\rightarrow \) /film/film/other_crew./film/film_crew_gig/film_crew_role |
4 Relation path embedding
4.1 Path-specific projection
4.2 Path-specific type constraints
4.3 Training details
4.4 Complexity analysis
Model | #Parameters | #Time complexity |
---|---|---|
SE [3] |
\(O(N_{e}n+2N_{r}m^{2})\)
|
\(O(2n^{2}N_{t})\)
|
SME (linear) [4] |
\(O(N_{e}n+N_{r}m+4k(n+1))\)
|
\(O(4nkN_{t})\)
|
SME (bilinear) [4] |
\(O(N_{e}n+N_{r}m+4k(ns+1))\)
|
\(O(4nksN_{t})\)
|
TransE [5] |
\(O(N_{e}n+N_{r}m)\)
|
\(O(N_{t})\)
|
TransH [32] |
\(O(N_{e}n+2N_{r}m)\)
|
\(O(2nN_{t})\)
|
TransR [20] |
\(O(N_{e}n+N_{r}(n+1)m)\)
|
\(O(2mnN_{t})\)
|
PTransE (ADD, 2-hop) [19] |
\(O(N_{e}n+N_{r}m)\)
|
\(O(pN_{t})\)
|
PTransE (MUL, 2-hop) [19] |
\(O(N_{e}n+N_{r}m)\)
|
\(O(plN_{t})\)
|
RPE (PC) (this paper) |
\(O(N_{e}n+N_{r}m)\)
|
\(O(pN_{t})\)
|
RPE (ACOM) (this paper) |
\(O(N_{e}n+N_{r}(n+1)m)\)
|
\(O(2mnpN_{t})\)
|
RPE (PC + ACOM) (this paper) |
\(O(N_{e}n+N_{r}(n+1)m)\)
|
\(O(2mnpN_{t})\)
|
5 Experiments
Dataset | #Ent | #Rel | #Train | #Valid | #Test |
---|---|---|---|---|---|
FB15K | 14,591 | 1345 | 483,142 | 50,000 | 59,071 |
FB13 | 75,043 | 13 | 316,232 | 5908 | 23,733 |
WN11 | 38,696 | 11 | 112,581 | 2609 | 10,544 |
5.1 Link prediction
5.1.1 Evaluation protocol
5.1.2 Implementation
5.1.3 Analysis of results
Metric | Mean rank | Hits@10(%) | ||
---|---|---|---|---|
Raw | Filter | Raw | Filter | |
E [3] | 273 | 162 | 28.8 | 39.8 |
LFM [13] | 283 | 164 | 26.0 | 33.1 |
TransE [5] | 243 | 125 | 34.9 | 47.1 |
SME (linear) [4] | 274 | 154 | 30.7 | 40.8 |
SME (bilinear) [4] | 284 | 158 | 31.3 | 41.3 |
TransH (unif) [32] | 211 | 84 | 42.5 | 58.5 |
TransH (bern) [32] | 212 | 87 | 45.7 | 64.4 |
TransR (unif) [20] | 226 | 78 | 43.8 | 65.5 |
TransR (bern) [20] | 198 | 77 | 48.2 | 68.7 |
TransD (unif) [14] | 211 | 67 | 49.4 | 74.2 |
TransD (bern) [14] | 194 | 91 |
53.4
| 77.3 |
TranSparse (separate, S, unif) [15] | 211 | 63 | 50.1 | 77.9 |
TranSparse (separate, S, bern) [15] | 187 | 82 | 53.3 | 79.5 |
PTransE (ADD, 2-hop) [19] | 200 | 54 | 51.8 | 83.4 |
PTransE (MUL, 2-hop) [19] | 216 | 67 | 47.4 | 77.7 |
PTransE (ADD, 3-hop) [19] | 207 | 58 | 51.4 | 84.6 |
DKRL(CNN)+TransE [33] | 181 | 91 | 49.6 | 67.4 |
RPE (initial) | 207 | 58 | 50.8 | 82.2 |
RPE (PC) | 196 | 77 | 49.1 | 72.6 |
RPE (ACOM) |
171
|
41
| 52.0 |
85.5
|
RPE (MCOM) | 183 | 43 | 52.2 | 81.7 |
RPE (PC + ACOM) | 184 | 42 | 51.1 | 84.2 |
RPE (PC + MCOM) | 186 | 43 | 51.7 | 76.5 |
Tasks | Predicting head entities (Hits@10) | Predicting tail entities (Hits@10) | ||||||
---|---|---|---|---|---|---|---|---|
Relation category | 1-to-1 | 1-to-N | N-to-1 | N-to-N | 1-to-1 | 1-to-N | N-to-1 | N-to-N |
SE [3] | 35.6 | 62.6 | 17.2 | 37.5 | 34.9 | 14.6 | 68.3 | 41.3 |
SME (linear) [4] | 35.1 | 53.7 | 19.0 | 40.3 | 32.7 | 14.9 | 61.6 | 43.3 |
SME (bilinear) [4] | 30.9 | 69.6 | 19.9 | 38.6 | 28.2 | 13.1 | 76.0 | 41.8 |
TransE [5] | 43.7 | 65.7 | 18.2 | 47.2 | 43.7 | 19.7 | 66.7 | 50.0 |
TransH (unif) [32] | 66.7 | 81.7 | 30.2 | 57.4 | 63.7 | 30.1 | 83.2 | 60.8 |
TransH (bern) [32] | 66.8 | 87.6 | 28.7 | 64.5 | 65.5 | 39.8 | 83.3 | 67.2 |
TransR (unif) [20] | 76.9 | 77.9 | 38.1 | 66.9 | 76.2 | 38.4 | 76.2 | 69.1 |
TransR (bern) [20] | 78.8 | 89.2 | 34.1 | 69.2 | 79.2 | 37.4 | 90.4 | 72.1 |
TransD (unif) [14] | 80.7 | 85.8 | 47.1 | 75.6 | 80.0 | 54.5 | 80.7 | 77.9 |
TransD (bern) [14] | 86.1 | 95.5 | 39.8 | 78.5 | 85.4 | 50.6 | 94.4 | 81.2 |
PTransE (ADD, 2-hop) [19] | 91.0 | 92.8 | 60.9 | 83.8 | 91.2 | 74.0 | 88.9 | 86.4 |
PTransE (MUL, 2-hop) [19] | 89.0 | 86.8 | 57.6 | 79.8 | 87.8 | 71.4 | 72.2 | 80.4 |
PTransE (ADD, 3-hop) [19] | 90.1 | 92.0 | 58.7 | 86.1 | 90.7 | 70.7 | 87.5 | 88.7 |
TranSparse (separate, S, unif) [15] | 82.3 | 85.2 | 51.3 | 79.6 | 82.3 | 59.8 | 84.9 | 82.1 |
TranSparse (separate, S, bern) [15] | 86.8 | 95.5 | 44.3 | 80.9 | 86.6 | 56.6 | 94.4 | 83.3 |
RPE (initial) | 83.9 | 93.6 | 60.1 | 78.2 | 82.2 | 66.8 | 92.2 | 80.6 |
RPE (PC) | 82.6 | 92.7 | 44.0 | 71.2 | 82.6 | 64.6 | 81.2 | 75.8 |
RPE (ACOM) |
92.5
|
96.6
|
63.7
|
87.9
|
92.5
|
79.1
|
95.1
|
90.8
|
RPE (MCOM) | 91.2 | 95.8 | 55.4 | 87.2 | 91.2 | 66.3 | 94.2 | 89.9 |
RPE (PC + ACOM) | 89.5 | 94.3 | 63.2 | 84.2 | 89.1 | 77.0 | 89.7 | 87.6 |
RPE (PC + MCOM) | 89.3 | 95.6 | 45.2 | 84.2 | 89.7 | 62.8 | 94.1 | 87.7 |
5.2 Triple classification
5.2.1 Evaluation protocol
5.2.2 Implementation
Datasets | WN11 | FB13 | FB15K |
---|---|---|---|
TransE (unif) [5] | 75.9 | 70.9 | 77.8 |
TransE (bern) [5] | 75.9 | 81.5 | 85.3 |
TransH (unif) [32] | 77.7 | 76.5 | 78.4 |
TransH (bern) [32] | 78.8 | 83.3 | 85.8 |
TransR (unif) [20] | 85.5 | 74.7 | 79.2 |
TransR (bern) [20] | 85.9 | 82.5 | 87.0 |
PTransE (ADD, 2-hop) [19] | 80.9 | 73.5 | 83.4 |
PTransE (MUL, 2-hop) [19] | 79.4 | 73.6 | 79.3 |
PTransE (ADD, 3-hop) [19] | 80.7 | 73.3 | 82.9 |
RPE (initial) | 80.2 | 73.0 | 68.8 |
RPE (PC) | 83.8 | 77.4 | 77.9 |
RPE (ACOM) | 84.7 | 80.9 | 85.4 |
RPE (MCOM) | 83.6 | 76.2 | 85.1 |
RPE (PC + ACOM) |
86.8
|
84.3
|
89.8
|
RPE (PC + MCOM) | 85.7 | 83.0 | 87.5 |