Language models and NLP EMNLP 2022
Bring e1 home with one rotation. Then look at e2.
The paper places two knowledge graphs in one low-dimensional hyperbolic space and matches each entity to its counterpart by a rotation whose angles are computed from that entity’s own embedding.
On three benchmarks of 15K entity pairs it reports the highest Hit@1, Hit@5 and MRR in its comparison table (Table 1).
Figure 1Illustration
Distances in toy units. e1 is nearest to root′, not to its twin. e2 is nearest to s′, not to its twin.
01 The problem
Knowledge graphs often exhibit hierarchical structures, the paper notes, and the number of nodes grows exponentially from one level to the next (Section 3.3). Earlier embedding methods for entity alignment work in Euclidean space (Section 1). In hyperbolic space the circumference and the area of a circle grow exponentially with its radius, which is what lets a hierarchy fit. Draw one tree both ways and count.
Figure 2Illustration
Flat page levels on evenly spaced rings
Poincaré disc every edge the same hyperbolic length
| Measure | Flat page | Disc |
|---|---|---|
| Closest pair that is not connected in lengths of the shortest edge | 0.70 | 1.61 |
| Worst-case distortion 1 would be a perfect map | 11.98 | 2.03 |
40 entities, branching factor 3. Select a node in the disc to re-centre on it.
Shown for 3 levels (40 entities) and an edge length of 1.6. With scripts on, sliders change both and any node can be moved to the centre.
| Measure | Flat page | Disc |
|---|---|---|
| Direct path between the two points as a share of the path through the centre | 71% | 85% |
On a flat page the share depends on the angle alone. In the disc it climbs toward 100% as the points near the rim, which the paper puts this way: “the shortest path from x to y is almost the same as the path through the origin”, like a tree, where “the shortest path between two sibling nodes is the path through their parent” (Section 3.3).
Shown for two points 90 degrees apart at 0.80 of the disc’s radius. With scripts on, two sliders move them.
IllustrationA made-up tree with branching factor 3, as in the toy tree of the paper’s Figure 2, drawn two ways by fixed rules. The distortion figure is this page’s own measure; the paper argues the point in its Section 3.3 and reports no distortion. The second tab recomputes the quantity of the paper’s Figure 2(a) from geometry; that figure prints no values and none is read off it. Its numbers are not results.
“In hyperbolic space, more generic/ambiguous nodes (e.g., root in a KG) tend to be placed closer to the origin while moving more specific objects [...] towards the boundary” (Section 1). Generic entities sit near the centre, specific ones near the rim.
Vector addition, matrix products and inner products “are defined in Euclidean space”, so the paper uses a hyperbolic version of neural networks (Section 1). Section 03 follows one entity through it.
Room solves how to store one graph. The paper’s subject is what happens when there are two: “One pivotal step for fusion is to align equivalent entities across different KGs” (Section 1).
02 The idea
Both graphs are placed in one hyperbolic space. Matching is then two moves: carry every entity of graph 1 through a mapping, and take the nearest entity of graph 2. “Existing works use a unified global map function to match entities”, the paper says, yet “the relations between two entities may vary from one pair to another”. Its mapping is a rotation whose angles each entity computes from its own embedding.
Figure 3Illustration
The paper’s Unified-R variant in miniature. Here one angle turns every entity of graph 1; in the paper it is one shared set of d/2 angles.
The button tries all 360 whole degrees and keeps the one that matches the most test entities.The button fits by least squares on the five ringed pairs: turn = b + w · (the entity’s flattened position).
We built the second graph so that the turn each entity needs drifts across the disc. Real graph pairs may or may not behave this way. The paper’s measured test is in Table 1, below.
The 7 test entities tick: its twin is the nearest triangle
Numbers run from the root outward: 0 is the root, 1 to 3 its branches, 4 to 12 the leaves. A prime marks graph 2, so 11′ is the twin of 11.
The paper’s model has 100 dimensions by default, so Eq. 13 gives each entity 50 angles computed. This disc has 2 dimensions and one angle, so that it can be drawn.
One rotation for all, at the best single angle: some entities miss their twins.
A rotation per entity, three shared numbers fitted on the five ringed pairs: they land. With scripts on, this figure is an instrument.
IllustrationTwo made-up graphs of 13 entities in a 2-d Poincaré disc, with fixed rules in place of a trained network. It shows what a per-entity rotation is and when one rotation is not enough. Its counts are not results.
Measured, Table 1The same question on real data: Hit@1, higher is better
| Row of Table 1 | EN-DE | EN-FR | D-Y |
|---|---|---|---|
| One rotation for all Unified-R | 0.727 | 0.664 | 0.802 |
| A rotation per entity GEA-H, the full model | 0.863 | 0.775 | 0.967 |
Whether real graph pairs need different turns is the paper’s hypothesis, and these two printed rows are its test, not the toy above. Take the model apart in section 05.
For each entity of graph 1 the paper takes the entity of graph 2 at the smallest hyperbolic distance from the mapped embedding (Section 4, Eq. 15). The ranked list in the panel is that search, on 13 candidates.
The paper calls it a “block-diagonal matrix specified by 2×2 matrices” (Eq. 11 and 12): each consecutive pair of coordinates is turned by its own angle, so the dimension is even. It acts on the coordinates of the hyperbolic embedding directly.
One more hyperbolic linear layer, shared by all entities, turns an embedding into its angles, “which makes the mapping adaptive to the entity” (Eq. 13). Shared weights, entity-specific input: an entity that was never labelled still gets a turn.
“Localized” does not mean that neighbours vote on the match: neighbours shape the embedding earlier, in the encoder, and “localized” describes the mapping. Nor is aligning entities in hyperbolic space new to this paper, which cites HyperKA and HMEA. Against HyperKA it lists a hyperbolic network with attention and dimension reduction, a localized geometric mapping where HyperKA “uses a unified linear transformation function”, and entity vectors that start from a pre-trained semantic embedding where HyperKA “randomly associates each entity with a vector” (Section 2).
03 Follow one entity
The example is the paper’s own: the English entity “New Orleans”, whose equivalent in the French graph is “La Nouvelle-Orléans”, and “Times Square”, which is spelled the same in both (Section 4). Follow New Orleans through Equations 4 to 15. The ball is entered and left through two maps, exp and log, and every box and every crossing opens.
Figure 4Illustration
Each entity begins as a pre-trained FastText word vector for its name: 300 numbers, an ordinary flat vector. The paper follows RNM here. If the name is null or not in the dictionary, a random vector is used (Section 5.1). The toy keeps 2 made-up numbers in place of 300.
Read the vector as a direction and a length at the centre, and walk along the curved space in that direction (Eq. 4 and 5). However long the vector, it lands inside the ball. In this toy’s disc coordinates the walk comes out at twice the flat length, because the disc’s ruler counts double at the centre; in the paper’s Eq. 5 it is exactly the length. Stretch it and watch the gap to the rim.
Attention weights come from a learned linear function of the flattened entity and the flattened neighbour, normalised by a softmax (Eq. 9). The weighted average is taken in the tangent space at the entity and mapped back (Eq. 8), then joined to the entity’s own point by Möbius addition (Eq. 6). The graph is treated as undirected.
Flatten at the centre, multiply by a learned matrix, map back, add a bias with Möbius addition (Eq. 10). In the experiments two such layers take 300 numbers to 200 and then to 100. The paper says this step “enables us to represent rich information with low dimensional vectors”. The toy stays in 2-d, so here the point only moves.
300200100
One more layer of the same kind, shared by all entities, turns the embedding into d/2 angles (Eq. 13), “which makes the mapping adaptive to the entity”. Same weights, different input: in this toy New Orleans and Times Square come out with different turns.
The embedding’s coordinates are taken two at a time and each pair is turned by its own angle (Eq. 11 and 12). Swap the rotation for a stretch, this page’s own counter-example, to see what a rotation keeps: the distance from the centre.
All entities of graph 2 are sorted by hyperbolic distance to the rotated point, and the first is the prediction (Eq. 15). Hit@1 and Hit@5 count how often the true counterpart is first or within the first five; MRR averages one over its rank (Section 5.1).
The toy’s five candidates, nearest first distance in toy units
Select any box or crossing in the drawing to read what it does. Arrow keys move between them.
The paper follows RNM and initialises each entity with a 300-d FastText word embedding, “which can represent the lingual information of entity names”. Out: one flat vector per entity. The paper does not say how names in different languages are brought together, or how many entities fell back to a random vector.
It “projects a tangent vector [...] into the hyperbolic space”. In: a flat vector at a base point. Out: a point of the ball. The toy uses the Poincaré disc form of the map; the paper prints the hyperboloid form.
The name vector after Eq. 4. In: exp of the name vector. Out: to the attention, flattened, and to the Möbius addition as it is. The paper names the Poincaré ball model (Section 3.2, Eq. 1) but prints Eq. 3, 5 and 7 in hyperboloid form and says it maps features “into the hyperboloid manifold” (Section 4), so the text does not settle which coordinates the trained model used. This toy draws a Poincaré disc.
The paper says “we consider the KG as an undirected graph”. In: the points of every entity linked to this one. Out: to the attention. Equations 6 to 10 run over neighbours only; the paper describes no use of relation labels.
Used “to map the hyperbolic vector into the tangent space at point u”. In: a point of the ball. Out: a flat vector that a learned matrix can act on.
A softmax over the neighbours of a learned linear function of the two flattened points, concatenated. “The attention mechanism enhances the important neighbors.” Out: one weight per neighbour. The paper does not mention attention heads or another non-linearity.
The neighbours are flattened at the entity’s own point, averaged with the attention weights, and the average is mapped back with an exponential map at the same point. Out: one summary point n.
The ball’s replacement for “+”: the result of adding two points stays in the ball. In: the entity’s point and the summary n. Out: the new state z. One of the two operations that act on points of the ball directly.
W and b are learnable parameters. The matrix acts on the flattened state; the bias is added back in the ball. This is where the dimension drops: 300 to 200 to 100 in the experiments. No activation between layers is printed.
“We consider the output of the hyperbolic neural network model as the final low-dimensional hyperbolic embeddings for entities.” 100 numbers by default. Out: to the angle layer and to the rotation.
One more hyperbolic linear layer, with weights shared by all entities, “which makes the mapping adaptive to the entity”. In: H. Out: d/2 angles, 50 at the default size computed. The paper does not discuss the range of the angles or report what was learned.
A “block-diagonal matrix specified by 2×2 matrices”: each consecutive pair of coordinates is turned by its own angle. It acts on the embedding’s coordinates with no exponential or logarithmic map around it. The paper argues for it in words and with the Linear-T variant; it proves nothing about rotations.
“For each entity, we find the aligned entity by searching for the nearest neighbor in terms of hyperbolic distance” (Section 1, page 2823); Eq. 15 is the rule. In: the rotated embedding and every embedding of graph 2. Out: the prediction.
The network learns embeddings “on two KGs respectively” (Section 1, page 2822). The paper does not say whether the two graphs share one set of weights. The mapping runs one way: “Now we have the mapping function from G1 to G2.”
IllustrationA diagram drawn for this page from Equations 4 to 15; the paper has no architecture figure. The values come from a 2-d toy with weights set by hand, one layer where the paper has two, and its numbers are not results. The entity names are the paper’s own example (Section 4); the numbers say nothing about those places.
Every learned matrix acts on a flat copy; the biases b and b′ are added inside the ball by Möbius addition (Eq. 10 and 13). The ball is entered with an exponential map and left with a logarithmic map. Two operations act on points of the ball directly: Möbius addition and the rotation. This summary is ours, not a sentence of the paper.
Training pulls each labelled pair together after the rotation and pushes sampled non-pairs apart, with a margin (Eq. 14); the abstract calls it a contrastive loss. It needs labelled one-to-one pairs: 20% of each dataset is used for training.
“We configure the negative constant curvature of hyperbolic space as a trainable parameter”, initialised as 1 (Sections 5.1 and 5.5). Every disc on this page fixes it at 1.
04 The evidence
Three benchmarks of 15K entity pairs: EN-DE and EN-FR (English to German and English to French DBpedia) and D-Y (DBpedia to Yago). 20% of the pairs are used for training, 10% for validation and 70% for test. Every number is the mean of 3 runs, and the paper reports no spread. Hit@1 and Hit@5 are proportions and MRR is a mean reciprocal rank; all three lie between 0 and 1 and higher is better.
Figure 5Measured, Table 1
With scripts on, a chart of any of the nine columns stands here, with a row by row comparison against the full model. Without them, the table below is the whole evidence: GEA-H prints 0.863, 0.775 and 0.967 on Hit@1, and RDGCN, the highest baseline in every column, prints 0.830, 0.755 and 0.931.
| EN-DE | EN-FR | D-Y | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Model | Hit@1 | Hit@5 | MRR | Hit@1 | Hit@5 | MRR | Hit@1 | Hit@5 | MRR |
| Triple-based | |||||||||
| MTransE | 0.307 | 0.518 | 0.407 | 0.247 | 0.467 | 0.351 | 0.463 | 0.675 | 0.559 |
| IPTransE | 0.350 | 0.515 | 0.430 | 0.169 | 0.320 | 0.243 | 0.313 | 0.456 | 0.378 |
| BootEA | 0.675 | 0.820 | 0.740 | 0.507 | 0.718 | 0.603 | 0.739 | 0.849 | 0.788 |
| RSNs | 0.587 | 0.752 | 0.662 | 0.393 | 0.595 | 0.487 | 0.514 | 0.655 | 0.580 |
| MultiKE | 0.756 | 0.809 | 0.782 | 0.749 | 0.819 | 0.782 | 0.903 | 0.939 | 0.920 |
| Attributes-based | |||||||||
| JAPE | 0.288 | 0.512 | 0.394 | 0.262 | 0.497 | 0.372 | 0.469 | 0.687 | 0.567 |
| AttrE | 0.517 | 0.687 | 0.597 | 0.481 | 0.671 | 0.569 | 0.668 | 0.803 | 0.731 |
| Graph-based | |||||||||
| GCNAlign | 0.481 | 0.679 | 0.571 | 0.338 | 0.589 | 0.451 | 0.465 | 0.626 | 0.536 |
| RDGCN | 0.830 | 0.895 | 0.859 | 0.755 | 0.854 | 0.800 | 0.931 | 0.969 | 0.949 |
| AliNet | 0.615 | 0.771 | 0.684 | 0.387 | 0.613 | 0.487 | 0.591 | 0.722 | 0.650 |
| RNM | 0.731 | 0.810 | 0.768 | 0.623 | 0.690 | 0.649 | 0.834 | 0.876 | 0.854 |
| HyperKA hyperbolic | 0.622 | 0.827 | 0.713 | 0.403 | 0.660 | 0.519 | 0.614 | 0.806 | 0.699 |
| Variants of GEA-H | |||||||||
| Xavier-I | 0.679 | 0.757 | 0.759 | 0.564 | 0.662 | 0.629 | 0.685 | 0.796 | 0.739 |
| Linear-T | 0.674 | 0.767 | 0.718 | 0.539 | 0.645 | 0.589 | 0.654 | 0.734 | 0.693 |
| Unified-R | 0.727 | 0.779 | 0.751 | 0.664 | 0.713 | 0.687 | 0.802 | 0.852 | 0.824 |
| Full-fledged model | |||||||||
| GEA-H | 0.863 | 0.924 | 0.891 | 0.775 | 0.857 | 0.812 | 0.967 | 0.981 | 0.973 |
Bold as in the paper, which bolds only the GEA-H row. “Highest” and every difference on this page are computed from these cells. The tag “hyperbolic” is ours: the paper calls HyperKA “the only baseline in hyperbolic space” (Section 5.2). The paper says all baselines use “the default parameters as described in the corresponding paper” and does not say whether it re-ran them. Every row of Table 1 prints a lower Hit@1 on EN-FR than on EN-DE computed.
05 One piece at a time
Table 1 also prints three variants of the full model, each with one ingredient swapped out (Section 5.1). All three still run in hyperbolic space. The last of them is the measured counterpart of the bench in section 02.
Figure 6Measured, Table 1
One at a time: the paper builds three variants, each with a single ingredient swapped out (Section 5.1). Switching a second one off puts the first back on.
With scripts on, four buttons and three switches load the four printed rows against two reference marks. The rows are in Table 1 above: Xavier-I, Linear-T, Unified-R and GEA-H.
Try the third switch yourself on the bench. For the second there is no toy: step 6 only shows, with a stretch of our own that is not the paper’s Linear-T, what a rotation keeps.
Figure 7Measured, Table 2
| Ratio | EN-DE Hit@1 | EN-DE MRR | EN-FR Hit@1 | EN-FR MRR | D-Y Hit@1 | D-Y MRR |
|---|---|---|---|---|---|---|
| 25 | 0.845 | 0.873 | 0.746 | 0.784 | 0.931 | 0.945 |
| 50 | 0.859 | 0.884 | 0.768 | 0.806 | 0.949 | 0.961 |
| 75 | 0.863 | 0.891 | 0.775 | 0.812 | 0.967 | 0.973 |
| 100 | 0.864 | 0.893 | 0.776 | 0.814 | 0.971 | 0.973 |
| 150 | 0.870 | 0.894 | 0.772 | 0.810 | 0.970 | 0.969 |
Nothing is bold in the paper’s Table 2, and Hit@5 is not in it. The row for 75 negatives per pair is the setting behind Table 1. It is not the highest row: EN-DE keeps rising to 150, while EN-FR Hit@1 and MRR and D-Y Hit@1 are highest at 100, D-Y MRR ties at 75 and 100, and all four are lower at 150 computed. The paper’s explanation: “there is trade-off between pushing negative samples away and minimizing the distance of positive samples” (Section 5.4).
From the paper, in words
Hit@1 against embedding size from 50 to 300 in steps of 50, for GEA-H and the baselines whose size can be set. “As the dimension approaches 50, we can observe that the performances of some baselines decrease drastically on all three datasets. Our model offers much better representation and achieves the best performance in low-dimensional space.”
The paper prints no values for this figure, so it is not charted here.
The paper says “the occupied GPU memory and running time increase drastically as the dimension increases. Therefore, there is a trade-off between accuracy and computational cost.” The paper names no GPU, no dataset for this figure and no cost for any baseline.
The paper prints no values for this figure, so it is not charted here.
The curvature is a trained parameter, initialised as 1. The paper says “the value of c converges in the training process” and that “the curvature learned by our model converges near the estimated optimal curvature”, found by fixing it instead.
The paper prints no values for this figure, so it is not charted here.
The default output size is 100, reached from 300 through 200. RDGCN and RNM are fixed at 300 and are not in the paper’s Figure 3, so the highest baseline of Table 1 is missing from the dimension comparison.
The takeaway
In the paper’s table it is the combination, not any single piece, that prints the highest values: each variant with one ingredient swapped out prints below the two highest baselines computed from Table 1.
06 Office hours
Written by Tian's agent while Tian slept and Pepper supervised. Pepper accepts no liability either.
Each answer says where in the paper it comes from, so you can check the agent's work.
By the paper’s own table, the whole recipe. The full model prints the highest value in all nine columns of Table 1. But each of its three variants, all of which still run in hyperbolic space, prints below the Euclidean baselines RDGCN and MultiKE in all nine columns, and HyperKA, the one hyperbolic baseline, ranks fifth, sixth and sixth of twelve on Hit@1. The paper has no variant that keeps everything and swaps the hyperbolic space for a flat one, so the geometry’s own share is not isolated. The authors’ explanation (hierarchy preserved in low dimension, rotation, per-entity parameters) is given in words.
Source: Table 1; Sections 5.2 and 5.3. Ranks and comparisons computed from the cells.The model outputs 100 numbers per entity by default, reached from 300-d name vectors through a 200-d hidden layer, and the paper sweeps 50 to 300. The discs on this page have 2 dimensions only so that they can be drawn; the paper uses 2-d for one visualisation and gives no accuracy for it. What low dimension buys is shown in the paper’s Figures 3 and 4, which print no values: the text says the performances of some baselines “decrease drastically” as the dimension approaches 50, that its own model “achieves the best performance in low-dimensional space”, and that GPU memory and running time rise with the dimension. RDGCN, the highest baseline in Table 1, has a fixed size of 300 and is not in that sweep. No hardware, memory or time figure is stated anywhere in the text.
Source: Sections 5.1, 5.4 and 5.6; the paper’s Figures 3, 4 and 6.The paper’s argument is that circumference and area grow exponentially with the radius, so “the linear transformation can not address the non-linear nature of distance ratio in hyperbolic space”, and its Figure 1 has each entity and its counterpart related by a rotation about the centre. Its measurement is the Linear-T variant, which swaps the rotation for a hyperbolic linear layer and is the lowest of the three variants in eight of nine columns (Hit@1 0.674, 0.539 and 0.654 against 0.863, 0.775 and 0.967). The paper proves nothing about rotations. What this page’s toys add is plain geometry, labelled as ours: a rotation about the centre cannot change an entity’s distance from the centre. The bench has no “linear map” mode, because a toy cannot honestly stand in for that argument.
Source: Sections 1, 5.1, 5.2 and 5.3; the paper’s Figure 1; Table 1.Labelled pairs and names. Training uses 20% of the known one-to-one pairs of each dataset, and the paper names this as its limitation: “it requires a set of 1-to-1 alignments for training purposes. These alignments are supposed to be labeled manually.” Entities start from pre-trained FastText vectors of their names; replacing those with random initial vectors (the Xavier-I variant) lowers Hit@1 from 0.863, 0.775 and 0.967 to 0.679, 0.564 and 0.685. The paper does not say how names in different languages are brought together, or how many entities had no usable name.
Source: Sections 4 and 5.1; Limitations; Table 1.The differences over RDGCN range from 0.003 (EN-FR Hit@5) to 0.036 (D-Y Hit@1). Every number is the mean of three runs and no spread is reported, so none of these differences can be weighed against run-to-run variation. The experiments cover three datasets of 15K pairs from one benchmark, in a one-to-one setting; larger graphs and entities with no counterpart are outside it. HMEA, another hyperbolic method the paper cites, is not among the baselines. The paper does not say whether the baselines were re-run. The negative sampling setting behind the headline numbers, 75, is not the highest row of Table 2. The paper lists no future work.
Source: Tables 1 and 2; Sections 2, 3.1 and 5.1; Limitations. Differences computed from the cells.