Predicting Institution Hierarchies with Set-based Models
Year: 2020

Abstract:
The hierarchical structure of research organizations plays a pivotal role in science of science research as well as in tools that track the research achievements and output. However, this structure is not consistently documented for all institutions in the world, motivating the need for automated construction methods. In this paper, we present a new task and model for predicting sub-institution/super-institution relationships based on their string names. The crux of our model is that it leverages learned, permutation invariant representations of various token subsets of institution name strings. Our model outperforms or matches non-set-based models and baselines. We also create a dataset for training and evaluating models for this task based on the publicly available relationships in the Global Research Identifier Database.

text: ence research as well as in tools that track the research achievements and output. However, this structure is not consistently documented for all institutions in the world, motivating the need for automated construction methods. In this paper, we present a new task and model for predicting sub-institution/super-institution relationships based on their string names. The crux of our model is that it leverages learned, permutation invariant representations of various token subsets of institution name strings. Our model outperforms or matches non-set-based models and baselines. We also create a dataset for training and evaluating models for this task based on the publicly available relationships in the Global Research Identifier Database.

heading: 1. Introduction
text: Academic, government and various industrial organizations are often hierarchically structured [Fan et al., 2012]. For example, the Canadian Institute for Theoretical Astrophysics is a sub-institution of University of Toronto and Harvard University is the super-institution of both Harvard Medical School and Harvard Divinity School.
Science of science research focuses on interactions among various scientific agents (researchers, academic institutions, etc.) with the goal of developing tools and policies for accelerating science [Fortunato et al., 2018]. Institution hierarchies are used in the analysis of the funding of institutions and, when accompanied with temporal information, organizational hierarchies can also provide insights into the evolution / growth of institutions as well as fine-grained information about the mobility of researchers, capturing department and career focus changes [Azoulay et al., 2011, Stephan, 2012]. Thus, correctly modeling organizational hierarchies is critical for tool development in science of science and other institutional research.
The Global Research Identifier Database (GRID) is a resource meant to support such efforts. GRID is carefully curated and contains detailed information about research institutions, includ-
ing their sub-institution/super-institution relationships. While the database is large and growing (containing almost 100k institutions at the time of writing), there are institutions and relationships that are missing. For example, Montreal Institute for Learning Algorithms is not present in GRID, and the public hospital, John Hunter Children’s Hospital, in New South Wales is not connected to the Government of New South Wales nor Australia’s Government / healthcare system. Similarly, fine grained information, such as particular research laboratories or smaller departments within universities’ colleges, are often absent.
Relation extraction methods are typically used to create knowledge-bases (KBs) containing facts such as which institutions are parents/children of one another. OpenIE [Etzioni et al., 2011, Fader et al., 2011, inter-alia] and Universal Schema [Riedel et al., 2013, Verga et al., 2016, Das et al., 2017, inter-alia], are able to extract complex relationship between entities from text. These methods are either based on link-prediction techniques or use rich contextual information to make accurate predictions. Unfortunately, such context is often unavailable. For example, funding agencies listed in research papers, assignees mentioned in patents, and author/inventor affiliations included in articles and BibTeX entries regularly appear as strings with little to no context relevant to making predictions about organization hierarchies. Access to a KB of institutions names and other features may be available, but these KBs often miss hierarchical relationships between those institutions.
In this paper, we explore methods for predicting hierarchical relationships between institutions based solely on the spelling of the institution names and knowledge-base features. While some sub-institution/super-institution relationships can be predicted using simple token overlap between institution strings (e.g., Harvard Medical School sub-institution-of Harvard University), others require methods which can perform richer semantic understanding beyond simple token matching (e.g., Centre d’Investigation Clinique Pierre Drouin,Vandœuvre-lès-Nancy, France sub-institution-of Centre Hospitalier Universitaire de Nancy,Nancy, France). Predicting sub-institution/super-institution relationships without additional context is important when trying to complete KBs such as GRID without intensive data gathering for contextual evidence.
We present a model that predicts sub-institution-of relationships using institution names, locations, and types. Inspired by the intuition that set-intersections and set-differences among the tokens of two institution names provide significant signal as to their relationship, our model learns to combine permutation invariant representations of token subets derived from institution names. Operating over embedded representations improves generalizability in comparison to techniques that operate on discrete tokens.
In this work, we make the following 3 contributions: (1) we present a new set-based model that outperforms non-set-based models on sub-institution/super-institution relationship prediction, (2) we examine the difficulty of the task and show when set-based models work well, and (3) we create and release a new dataset derived from GRID to support sub-/super-institution relationship prediction.

heading: 2. Background

heading: 2.1 Dataset & Preprocessing
text: The Global Research Identifier Database (GRID), contains information about 91,640 institutions from 217 countries1. The institutions include universities, government agencies, companies, health
1. We use the 2018-11-14 Release.
care organizations and other places of research. GRID stores the name, location, and type (university, hospital, government agency, etc), as well as the parent of each institution. The database includes 11,393 instances of the sub-institution relationship.
Our goal is to develop models that predict the hierarchical structure of institutions. We use GRID to derive a new dataset that contains pairs of institutions that participate in the sub-institution relationship (i.e., positive examples) and pairs of institutions that do not (i.e., negative examples). Constructing our dataset begins by building a graph where each node represents a GRID institution, and each edge represents a parent-child relationship among an institution pair. We partition the child-parent edges into a train/dev/test split by randomly assigning each connected component of institutions and all of its edges to either the train, development or test set (using a 0.6/0.2/0.2 split). We construct negative examples in three ways: (1) non-sub-institutions in the same connected component, (2) non-sub-institutions in the same city in a different connected component, and (3) randomly sampled pairs. Figure 1 visualizes a connected component from GRID. Due to its overwhelming size (2981 sub-institutions) with respect to other institutions in GRID, we exclude the connected component representing the United States Government from the dataset.

heading: 2.2 Institution Hierarchy Prediction
text: Let A and B be two institutions in GRID. Then, A sub-institution-of B, if A is a descendant of B according to GRID. In institution hierarchy prediction, we are given two GRID institutions, A and B, which includes their names, locations, and types, and asked to predict if the A sub-institution-of B.

heading: 3. Set-based Models for Predicting Institution Hierarchies
text: In this section, we present a model for predicting whether one institution is a sub-institution of another. Our model makes use of Set Transformers [Lee et al., 2019] to model the token overlap between the institution names.

heading: 3.1 Sets of Institution Tokens
text: When predicting whether one institution is a sub-institution of another, the collection of tokens that appear in both institution names constitutes a strong signal. For example, consider the pair of institutions University of Pennsylvania and The Wharton School of the University of Pennsylvania. In this case, one institution name is a substring of the other, suggesting that in such cases the substring-institution name is a super-institution of the other.
However, this heuristic is far too strict. For example, consider the institution pair The Ohio State University sub-institution-of University System of Ohio, where the substring relationship does not hold. In this example, we notice that the two strings share the tokens {Ohio, University}, though the tokens appear in different orders in the strings. This suggests treating institution names as unordered sets of tokens rather than ordered strings. Additionally, the most salient tokens appear in both institution names and less relevant tokens do not. This suggests that it is more likely for some tokens to appear in both names if two institutions participate in the sub-institution-of relationship than others.
We present a model inspired by these insights, which is designed to predict whether one institution is a sub-institution of another. The model takes an ordered pair of institution names as input, (s1, s2), and outputs a score: h(s1, s2), with larger scores corresponding to greater model confidence in s1 sub-institution-of s2. We use ts be the tokens of a string s. The model is a function of four sets, each of which can be built from the two institution names: (1) the first institution represented as a set of tokens (ts1), (2) the second institution represented as a set of tokens (ts2), (3) the intersection between the first and second institution (ts1 ∩ ts2), and (4) the set difference between the second institution and the first, (s2 \ s1).
Let f : 2V → Rd be a function that returns the embedded representation of a token set, where V is the vocabulary defined by our model. Define the model, h, evaluated on two string, s1 and s2, as
follows:
h(s1, s2) = 〈f(ts2), f(ts2 ∩ ts1)〉 − 〈f(ts1), f(ts2 ∩ ts1)〉 − 〈f(ts2), f(ts2 \ ts1〉) (1)
where 〈·, ·〉 is the inner product of the two vectors. The first term in Equation 1 computes the dot product between s2, the candidate super-institution, and the intersection of the two institutions strings. As previously discussed, if all tokens of s2 appear in ts1 ∩ ts2, then it is likely that s1 sub-institution-of s2. The second term encodes a dual effect: if the embedded representation of s2, i.e., f(t2) is similar to the embedding of the intersection of the tokens of s1 and s2, i.e., f(ts1 ∩ ts2), then s2 is likely a super-institution of s1 (captured in the subtraction of the second term from the first). Together, the first two terms encode the intuition that children institutions tend to exhibit a higher degree of specificity than their parents. Finally, the third term in the model compares the tokens in s2 (including tokens in the intersection) to the tokens which are unique to s2. If there is large overlap between these sets, it indicates that s2 is significantly different from s1, i.e., s1 is unlikely to be a sub-institution of s2. The third term in Equation 1 compares the tokens in s2 (and potentially in the intersection) to the tokens which are unique to s2. A large overlap between these sets indicates that s2 is sufficiently different from s1, i.e., s1 is unlikely to be a sub-institution of s2. Figure 2 visualizes our model. Any set encoder function may be used for f . Our choice of this function is discussed further in Section 3.2.

heading: 3.1.1 TRAINING OBJECTIVE
text: We train our model to optimize a ranking objective. Given a triple of institutions (D,Apos,Aneg) such that D sub-institution-of Apos is True and D sub-institution-of Aneg is False, we use the Bayesian Personalized Ranking objective as our loss function σ(h(D,Apos)− h(D,Aneg)) [Rendle et al., 2009].

heading: 3.2 Set Encoders
text: Our model relies on the function, f , to provide a meaningful representations of sets of institution name tokens. While many permutation invariant, set-based models haven been proposed in recent work, [Ravanbakhsh et al., 2016, Zaheer et al., 2017, Ilse et al., 2018, Hartford et al., 2018, Lee et al., 2019, Mena et al., 2018, Cotter et al., 2019, Bloem-Reddy and Teh, 2019], in this paper, we use a Set Transformer [Lee et al., 2019], which represents the state-of-the-art permutation invariant model based on transformers [Vaswani et al., 2017]. Given a set of tokens, the Set Transformer encodes the tokens without position embeddings. We take the set representation to be the average of the final representation after the last layer in the transformer for each token in the set. The size of the sets used are relatively small, and so we do not use the inducing point-based Set Transformers and instead use all pairwise self-attention [Lee et al., 2019].

heading: 3.3 Institution Features
text: In addition to the name, GRID contains the city, state, country, and type (i.e., Education, Government, Nonprofit) for each institution. To train our model, we apply h (Eq. 1) to each feature and get a score for each feature. Then, the final score is learned weighted sum of the scores for each feature. Note that each feature has its own parameters. Institution name and city have a token vocabulary while the
Model Ablation MAP Acc. at 1 Acc. at 10 Acc. at 50 Acc. at 100
TokSim Orig 0.060 0.037 0.161 0.332 0.384 O-LSTM Orig 0.166± 0.04 0.105± 0.05 0.331± 0.04 0.598± 0.07 0.728± 0.08 Unig 0.170± 0.02 0.116± 0.03 0.329± 0.05 0.624± 0.07 0.745± 0.07 O-Trans Orig 0.128± 0.05 0.086± 0.04 0.118± 0.08 0.484± 0.05 0.604± 0.06 Unig 0.103± 0.02 0.050± 0.02 0.225± 0.04 0.535± 0.08 0.643± 0.08 S-AvgEmb Orig 0.182± 0.03 0.133± 0.06 0.327± 0.03 0.610± 0.02 0.701± 0.02
LC 0.177± 0.02 0.11± 0.02 0.308± 0.03 0.598± 0.03 0.684± 0.04 MLP 0.146± 0.02 0.077± 0.02 0.280± 0.04 0.605± 0.01 0.708± 0.02 Unig 0.090± 0.01 0.022± 0.01 0.193± 0.21 0.559± 0.03 0.684± 0.02
S-Trans (Ours) Orig 0.262± 0.07 0.248± 0.11 0.407± 0.07 0.630± 0.09 0.714± 0.10 LC 0.128± 0.06 0.057± 0.04 0.281± 0.23 0.573± 0.10 0.696± 0.07 LCI 0.303± 0.03 0.318± 0.07 0.421± 0.05 0.665± 0.05 0.771± 0.03 MLP 0.170± 0.05 0.128± 0.09 0.321± 0.05 0.549± 0.09 0.655± 0.09 Unig 0.135± 0.01 0.061± 0.01 0.254± 0.02 0.601± 0.06 0.732± 0.05
Table 1: Score using Institution and Location (city, state, country) and Type features
state, country and type have a character vocabulary (for the sake of generalization to unseen location strings).

heading: 3.4 Learning Model Coefficients
text: Note that the model h (Eq. 1) can be rewritten as
h(s1, s2) = 〈f(ts2), f(ts2 ∩ ts1)〉 − 〈f(ts1), f(ts2 ∩ ts1)〉 − 〈f(ts2), f(ts2 \ ts1〉) = 〈[ 1 −1 −1 ] , [ 〈f(ts2), f(ts2 ∩ ts1)〉 〈f(ts1), f(ts2 ∩ ts1)〉 〈f(ts2), f(ts2 \ ts1〉 ]〉 .
To determine how important the specific combination of terms for our model h is, we replace the vector [ 1 −1 −1 ] with a learnable weight vector, a learnable weight vector initialized randomly, and a learnable weight vector initialized with our proposed model (which we call the default initialization). This only represents a linear combination of the values[
〈f(ts2), f(ts2 ∩ ts1)〉 〈f(ts1), f(ts2 ∩ ts1)〉 〈f(ts2), f(ts2 \ ts1〉 ] .

heading: 4. Experiments
text: We evaluate the ability of our model to predict sub-institution relationships between institutions in a retrieval-based task on our GRID dataset. Given the name of an institution (query), we rank the candidate super-institution name. We evaluate model performance in terms of mean average precision (MAP) and accuracy at K (Acc.) 2 for K = 1, 5, 50, and 100 . The descendant institutions are randomly assigned to be queries in a train/dev/test split. We compare the following models:
• SetTransformer (S-Trans) - The proposed approach of this paper, our set-based model with a set transformer [Lee et al., 2019] for the function f .
2. We use the following measurement: number of sub-institutions in top K / min(K, number of sub-institutions)
Model Ablation MAP Acc. at 1 Acc. at 10 Acc. at 50 Acc. at 100
TokSim Orig 0.062 0.149 0.218 0.325 0.401 O-LSTM Orig 0.087± 0.02 0.040± 0.02 0.198± 0.07 0.488± 0.07 0.601± 0.08 O-Trans Orig 0.067± 0.02 0.036± 0.01 0.144± 0.06 0.355± 0.08 0.471± 0.08 S-AvgEmb Orig 0.032± 0.00 0.011± 0.00 0.056± 0.01 0.235± 0.02 0.397± 0.02
LC 0.035± 0.00 0.015± 0.00 0.061± 0.01 0.225± 0.02 0.406± 0.02 MLP 0.034± 0.00 0.013± 0.00 0.013± 0.00 0.258± 0.01 0.410± 0.02
S-Trans (Ours) Orig 0.135± 0.02 0.077± 0.01 0.237± 0.06 0.478± 0.07 0.646± .07 LC 0.123± 0.03 0.071± 0.02 0.227± 0.05 0.379± 0.05 0.503± 0.07 LCI 0.115± 0.02 0.064± 0.02 0.214± 0.04 0.443± 0.16 0.587± 0.04 MLP 0.156± 0.01 0.099± 0.02 0.276± 0.02 0.427± 0.02 0.520± 0.04
We also experiment with several methods of combining the three terms of our set-based scoring function (Equation 1):
• Original (Orig) - the scoring function h described above.
• Linear Combination (LC) - a learned linear combination of the values.
• Linear Combination Initialized (LCI), a learned linear combination of the values initialized as the scoring function h.
• Multilayer Perceptron (MLP) - a one layer multi-layer perceptron.
We also experiment with using a token vocabulary (Unig) for every feature (including the state, country, and type), rather than just the institution name and city as in our model.
For each model, we report the mean performance metric and its standard deviation across 5 different random seeds. We bold the model with the highest mean score, and any model whose mean is within 1 standard deviation. Table 1 shows the result for this experiment. We also compare the models when given access to subsets of the additional GRID features (i.e., location, type). Table 2 contains the results when given access to institution name and location. Table 3 contains the results when given access to institution name only.
We provide the code and data to reproduce our experimental results3. Models are implemented in PyTorch. The models are trained using Adam [Kingma and Lei Ba, 2015]. We perform hyperparameter tuning (embedding dimension, feed-forward layer dimension, number of heads, number of layers) on a development set 4 and report performance on the test set for the model which performed highest in terms of MAP on the development set.
3. https://github.com/iesl/institution_hierarchies 4. Hyperparameter search and configurations released in the code
For MAP and Acc. at K for all k, we notice that our model (or a variant of it) has the highest mean across the different features used except for Acc. at 50 when using the institution name and location only. When using all the features, the S-Trans which learns a linear combination of the values 〈f(ts2), (ts2 ∩ ts1)〉, 〈f(ts1), f(ts2 ∩ ts1)〉, 〈f(ts2), f(ts2 \ ts1〉 with the the weights initialized to its default initialization is the top performing. Note that the S-Trans which uses the default initialization (our proposed model) outperforms the S-Trans which just learns a linear combination of the values. We hypothesize that randomly initializing the weights causes the model to get stuck in a bad local optima, while initializing the weights to its default initialization helps it find a better local optima. Lastly, we observe that in general using all the features (the institution name, location, and type) increases the performance of all the models.
To further evaluate our model, we perform 5-fold cross validation rather than using the proposed split (Table 4). Though the average MAP for O-LSTM is slightly higher than the average MAP for S-Trans, the standard deviation is 8 times as high. We note that S-Trans performs best in terms of Acc.@1.

heading: 4.1 Analysis
text: Performance By Token Overlap We hypothesize that predicting sub-institution-of between institution strings that share a large number of tokens is easier than when fewer tokens are shared between the strings. To analyze this hypothesis, we partition the test examples into buckets by percent token overlap between the query and the true positive (i.e., the first bucket contains pairs
with 0-5% overlap, the second 5%-15% overlap, etc.). Figure 3 contains the result. We observe that MAP scores for all models increase with token overlap. We observe that S-Trans has a larger margin of improvement over O-LSTM and TokSim when the amount of token overlap is smaller. We hypothesize that the set-difference-base term in S-Trans objective are useful in determining which non-overlapping tokens are meaningful when making sub-institution-of predictions.
Examples We provide qualitative examples of sub-institution-of predictions by our proposed model as well as by other baseline methods. These examples are given in Tables 5 and 6. In Table 5, we compare the predictions of S-Trans and of O-LSTM for two queries. In prediction of the super-institution of Northampton General Hospital we observe that O-LSTM selects a healthcare service at the lexically similar Northamptonshire. We hypothesisize that S-Trans is less likely to make such a mistake because it would consider Northamptonshire in the group of non-overlapping tokens in the two strings and could penalize not matching such a specific word. Table 6 provides a similar comparison between S-Trans and TokSim’s predictions.
Table 7 show examples that underscore the difficulty of institution hierarchy prediction. These examples are cases for which external data or contextual features are required to determine the correct relationships. For example, without knowledge that BASF is headquartered in Germany, it is difficult to predict that BASF(Canada), Mississauga, Ontario, Canada is sub-institution of BASF(Germany), Ludwigshafen am Rhein, Germany. Newswire, web data, or affiliation strings of authors could contain the required evidence.
Missing Sub-Institutions in GRID To determine the usefulness of our model and understand the quality of our labeled data, we look for false negatives, i.e, pairs of institutions that exhibit the sub-institution-of relationship, but are not labeled as such in GRID. We consider 50 institutions and consider the model’s highest ranked predictions for these super-institutions. Among these, we found two examples of false negatives that are shown in Table 8.

heading: 5. Related Work
text: The proposed task in this paper sits at the intersection of learned string similarity methods, relation prediction and extraction, and more generally set-based neural network models.
A fundamental component of the proposed approach is to use a parameterized method for comparing the spelling of two institution names. Parametric string similarity methods have a long history. Classic methods (Levenshtein, Longest Common Subsequence, Needleman-Wunsch [Needleman and Wunsch, 1970], and Smith-Waterman [Smith and Waterman, 1981]) measure similarity via insert, edit, and delete operations used to transform one string into another. Other work uses generative models [Dreyer et al., 2008, Andrews et al., 2012, 2014, Faruqui et al., 2016, Rastogi et al., 2016] or conditional random fields [McCallum et al., 2005] to model the string mutation sequences in an effort to learn a parameterized method for similarity within a domain. Recently, Gan et al. [2017] proposed a neural network model based on CNNs applied to character n-grams to model string similarity.
Relation extraction systems such as OpenIE, Universal Schema and others [Angeli et al., 2015, Verga et al., 2016, Das et al., 2017] are often interested in predicting relationships such as subsidiary or other similar relationships to that of this paper. However, these systems use natural language context such as sentences or paragraphs to make predictions rather than the strings themselves.
Set-based embedding models has also been well studied [Ravanbakhsh et al., 2016, Zaheer et al., 2017, Ilse et al., 2018, Hartford et al., 2018, Lee et al., 2019, Mena et al., 2018, Cotter et al., 2019, Bloem-Reddy and Teh, 2019]. Much of this work focuses on learning representations for sets that are order invariant. Our proposed approach models tokens in the intersection / set difference of the institution names, making set-based models a natural choice as our encoder’s architecture.

heading: 6. Conclusion
text: In this paper, we consider the task of predicting institution hierarchies using a model-based on set transformers using institution names and other metadata. We hope that our work, which includes a dataset built from GRID, spurs interest in this challenging and important problem and that future work explores both richer spelling-based, context-free models as well as models that make use of natural language text and other contextual resources. In addition, rather than constructing set intersections by finding overlapping tokens, we will consider model-based methods for constructing set intersections (i.e., functions of geometric representations, such as Box Embeddings [Vilnis et al., 2018] or Order Embeddings [Vendrov et al., 2015]).

Review summaries:
The paper shows how to infer the organisational structure of an institution. That is, it presents a model for predicting the is-ancestor relationships of institutions based on their string names. To this end, it makes use of Set-Transformers to model the token overlap between the institution names. This use is nice but also not highly original. The experimental evaluation is on a single dataset only. While the authors do present some examples, and overall hierarchy or something that provides some more insights into the learned model should be provided in order to show potential issues with transitivity and connected components. The evaluation only considers known pairs. But an organisational structure should also be consistent.  That is, the interesting motivation provided in the intro is not met in the experimental evaluation. Furthermore, the experimental protocol is  unclear. It seems to be a single training/test split, although one should consider several random splits or even some form of cross-validation, i.e., over the connected components given.

Paper is on modeling the prediction of ancestor relation between names of science institutions.  This is on the GRID dataset which already has some hierarchical information.  The proposed approach is set-based models (with neural encodings) where the overlap between two names is measured by set overlap at the unigram level.  In extended experiments additional metadata like address and type of institution are also incorporated into the model (which contribute a lot to the improvements).  A set of simple to intermediate baseline along with different thresholds of token overlap has been tested and the proposed model shows strong improvement in the MAP metric.