Why do embedding spaces look as they do?
Authors: Xingzhi Guo
Baojian Zhou
Haochen Chen
Sergiy Verstyuk
Steven Skiena
Venue: ICLR 2022 Submitted (2022)

Abstract: The power of embedding representations is a curious phenomenon.   For embeddings to work effectively as feature representations, there must exist substantial latent structure inherent in the domain to be encoded.  Language vocabularies and Wikipedia topics are human-generated structures that reflect how people organize their world, and what they find important. The structure of the resulting embedding spaces reflects the human evolution of language formation and the cultural processes shaping our world.

This paper studies what the observed structure of embeddings can tell us about the natural processes that generate new knowledge or concepts.   We demonstrate that word and graph embeddings trained on standard datasets using several popular algorithms consistently share two distinct properties: (1) a decreasing neighbor frequency concentration with rank, and (2) specific clustering velocities and power-law based community structures.
We then assess a variety of generative models of embedding spaces by these criteria, and conclude that incremental insertion processes based on the Barabási-Albert network generation process best model the observed phenomenon on language and network data.


Under review as a conference paper at ICLR 2022
WHY DO EMBEDDING SPACES LOOK AS THEY DO?
Anonymous authors Paper under double-blind review
ABSTRACT
The power embedding representations curious phenomenon, For embed- dings to function effectively as feature representations, there must exist substantial latent structure inherent the domain to be encoded. Language vocabularies and Wikipedia topics are their world, and what they find important. The structure of the embedding spaces should thus reflect the human evolution of language formation and the cultural processes shaping our world.
structures that reflect how people organize
This paper studies what the observed structure of embeddings can tell us about the natural processes that generate new knowledge or concepts. We demonstrate that word and graph embeddings trained standard datasets using several popular algorithms consistently share two properties: (1) a decreasing neighbor frequency concentration with rank that parallels the Matthew effect in spatial dimension, and (2) particular clustering velocities and power law-based community structures. We then assess variety of generative models of embedding spaces according to these criteria, and conclude that incremental insertion processes based on the preferential attachment-type mechanisms dependent on spatial context best model the phenomena observed in language and network data.
INTRODUCTION
Vector representations (Mikolov et al., 2013a;b; Pennington et al., 2014; Perozzi et al., 2014) of feature spaces (embeddings) have proven amazingly effective capturing the properties of discrete entities such as vocabulary words and the vertices of networks capturing human interactions, such as citation graphs or Wikipedia pages. Such embeddings are a foundational tool in machine learning, providing natural data representation easily applied for classification and regression models.
The power of embedding representations is a curious phenomenon. That embeddings function so effectively as feature representations implies there must exist substantial latent structure inherent in each domain to be effectively encoded. Language vocabularies and Wikipedia topics are represen- tative gunan-generated structures that reflect how people organize their world, and what they find important. The structure of the resulting embedding spaces thus must reflect the human evolution of language formation and the cultural processes shaping our world.
This paper addresses a big picture question: what does the observed structure of embeddings tell us about the processes by which people generate new knowledge or concepts? Word and graph embeddings provide reduced-dimensiioall "geometric" representation of the meaning of words and conceptual entities. The widespread success of predictive models trained on top of embeddings suggest that they accurately capture the underlying semantics of each entity. The question we study in this paper concerns which wwwwledge-generattee models best explain properties observed in real- world embeddings.
The vocabulary of every language evolves through a series of processes: new words get created to identify new concepts objects, while old words get repurposed with new senses and meanings. But how/where does this creation happen? Word usage frequencies are governed by a power law distribution, namely Zipf's law (Zipf, 1936; 1949). Do new words tend to be closely associated with high frequency words, perhaps adding shades of meaning to popular terms? Do they tend to fill large empty regions of embedding space, or add to dense clusters of points? If embeddings do indeed capture the meaning words, then studying the shape of embedding spaces should inform on the processes underlying the evolution of language.

---

Under review as a conference paper at ICLR 2022
A similar set of questions can be asked about the evolution of cultural, historical and scientific knowledge, as reflected by the contents of Wikipedia. Each entity page in Wikipedia links to other entities, creating network well represented by its graph embedding. Do high-degree historical en- tities disproportionnaely associate with other high-degree entities? Do new historical figures emerge in the context of clusters of earlier entities, do they fill empty niches in the cultural landscape?
A variety of generative models can be proposed to build embedding- spaces by incrementally inserting new points positioned through a specific algorithmic process. We seek to compare the properties of such generated spaces against those of observed embedding spaces, to gain insight into the processes underlying human knowledge generation activities. This is complicated by several factors: (I) we cannot directly observe or reconstruct the historical processes that created the entities of observed data sets, (2) there is no direct correspondence between the labels of generated and observed points, and (3) the scale and range of real/synthetic embeddings over different models, algorithms, and datasets are not directly comparable. Thus assessments must be done through non- parametric statistics quantifying similarities of unlabeled point sets. Our contributions here include:
Generative processes for embedding spaces. We define and explore the space of sev- eral plausible processes for the evolution of knowledge embedding spaces, incorporating into our models the mechanisms of preferential attachment as well as the effects of attrac- tive and/or repulsive forces. Certain processes generate networks to embed using standard graph representation learning methods, while others directly generate geometric point sets. Particularly novel is our class of preferential placement models.
Mon-parametric properties of embedding spaces. Meaningful comparisons of the prop- erties of observed and generated embedding spaces requires statistics which are robust to transformations as well as being independent of node labels. We have identified two novel and distinct properties of interest which can be rigorously measured on embedding spaces:
Frequency concentration How the importance of entities in the local neighborhood of æ is related to the importance of itself? This statistic captures the non-uniform spatial distribution of frequencies observed in an embedding.
Clustering velocity How rapidly do clustering procedures advance towards full con- nectivity? This statistic captures the predominance of cluster structure inherent in an embedding.
As a check, we also compare these statistics to measures of spatial correlation popular in geographic analysis. Our tools allow to uncover novel regularities in the natural embedding spaces: elements of embeddings are not only characterized by power-law distributions of their frequencies/degrees, but they also exhibit positive assortative sorting in spatial di- mension and a power law manifestation in relational space. Moreover, we show that these observed properties of English language vocabularies and Wikipedia network embeddings consistently hold for variety of distinct data sources and embedding algorithms, includ- ing fastText (Bojanowski et al., 2017). GloVe (Pennington et al., 2014), word2vee (Mikolov et al., 2013a), and BERT (Devlin et al., 2018). Thus they are not mere algorithmic artifacts data collection or analysis, but inherent properties of language and aulturally-generatee networks: phenomena in need of explanation through models of language/Knowledge cre- ation.
Evaluation of generative processes for word and graph embedding spaces. We com- pare embeddings generated by several different processes real data-driven embeddings from several datasets by these criteria. Several models can easily be eliminated based on these observations, leaving few that remain plausible. We conclude that specific incre- mental insertion processes based on the spatial context-dependent preferential attachment mechanisms best model the observed phenomenon on language and network data.
Paper outline. The rest of this paper is organized as follows. Section defines and presents the collection of seven different models we consider potential generative processes. Section 3 proposes our frequency concentration statistic and evaluates embeddings from both models and real-world ones. We present our clustering velocity statistics and model evaluations in Section 4. Finally, we discuss the implications of this research and future work in Section Our code and datasets accessible at https://shortur at /dyyT
2

---

Under review as a conference paper at ICLR 2022
1.1 RELATED WORK
Explanations of embedding spaces. Levy & Goldberg (2014) find that word embedding model such as word2vec essentially factorizes shifted pointwise mutual information matrix. To further understand the linear relationship of embeddings, Allen & Hospedales (2019); Allen et al. (2019) mathematically define the meaning of statement * word vector wy is to word vector "y and provide proof of the linearity among embeddings of word analogies. This linear property has also been explained in knowledge graph embeddings (Allen et al., 2021). However, this line of work is more focusing on the linear property between embedding vectors instead of the processes of generation.
Generative models of embeddings. There are many graph/network generative models (see the survey Hamilton (2020) and references therein). Traditional processes include the Erdós-Rényi model (Erdos et al., 1960), stochastic block model (Holland et al., 1983), and preferential attachment models (Simon (1955), Barabási Albert (1999), also see Albert Barabási (2002) for a review). .. Arora et al. (2016) study generative model where each word vector captures its correlations with the discourse vector. Instead, our generative models employ simple heuristics to generate embedding vectors that exhibit empirically realistic properties. There also works on generating models by using deep graph neural networks (You et al., 2018). Xiao et al. (2016) propose a model based on Dirichlet Process generate embeddings of knowledge graph. Li al. (2016) propose a graphical model for generating embeddings of documents. Most of these models are heavily based on probabilistic framework.
Notation. For set of n entities (e.g. words or nodes) := associated with V is {Wi, w....., w. where each location or whereabouts w, E Rd Throughout this paper, each entity is also associated with a importance or prominence (e.g. the frequency of specific words, or the degree of graph node) and denoted p;- Therefore, each entity can be represented as pair of importance and location (P:, wi). We collect them in an embedding matrix W Rexd and an importance vector p E R"
the set of embeddings
GENERATIVE MODELS FOR EMBEDDING SPACES
generative model of an n-element embedding space starts with an initial entity embedding pair (Po. wo)- At each time = 1,2,..... the model then repeatedly generates a new pair (Pr, w.)- During this generating process, updates p and W. We first present simple baseline models to generate points before considering network-generation processes based on preferential attachment. Motivated by empirical facts presented later, we seek to generate an embedding space such that entities with similar properties will be closer with each other compared with more distant points."
A) Generating nodes of a network
A1) Gaussian model. A simple way to generate an embedding- like space creates each point (pi, we) where w, is from standard Gaussian distribution (0 Ia) and the prominence p is drawn uni- formly from random permutation of (1, n) so that each entity i has random rank p.. The right figure illustrates generated embed- ding points that are from 3-dimensional Gaussian distribution, i.e., (O I.). We color each point by its normalized prominence, i.e., pa/ maxiev P;- As expected, these data points form a single cluster without any finer substructure within it.
0.8
0,6
Nomaalzaad
0.4
0.2
0.0
A2) Preferential Placement (PP) model. This model presumes that new entities emerge around the older, relatively more prominent ones. This PP model builds on the preferential attach- ment mechanism driving the development of real-world networks and graphs, where the fre- quency of generated entities exhibit the power law distribution, and it is closest to Simon (1955).
describe experimental details of generating points Appendix A.I.
Thh idea can be traced hack to Eggenberger & Polya (1923) and Yule (1925), with accepted modem formulations due Simon (1955), Price (1976) and Barabási & Albert (1999).
3

---

Under review as a conference paper at ICLR 2022
PP is parameterized by the total frequencies of data points n, the proba- bility of increasing the frequency of an old entity q, and an exponential distribution" with scale parameter 3 driving the distance of from the old one per-iteration t. The PP model randomly selects entity from existing ones with a probability proportional their frequencies and with a probability g, it increases the frequency of w; by 1. Other- wise, it generates new entity w, within small ball around wi; w. wi + Tt 2t with Pt 1, where the radius cxp( and its direction follows uniform distribution on unit sphere.* Different from the above Gaussian model, the left figure shows generated points where more promi- nent points in the small core cluster are surrounded by less prominent ones.
entity
A3) Directional Preferential Placement (DPP) model. The previous PP model generates new points in uniformly distributed random directions, producing homogeneous scattering of embed- ding entities. To bring about more heterogeneous landscape with cluster structure, we use the von Misex-Fisher distribution (yMF) that allows more control over the directions where new entities generated, in particular making this process more spatial context-aware. Specifically, random unit vector æ R2 2, follows the d-dimensional vMF distribution its probability density function is given by
K 4/2-11
SVMp(æll K) (2 (5rr)/21//22111 exp (xppa))
where μ with |||||| = 1, is the mean direction parameter specifying the orientation relatively to the origin; K 2 is concentration parameter controlling the dispersion about the mean (higher produces higher concentration); and Ia/2-1 (#) is the modified Bessel function of the first kind. For example, mean direction may represent the force attracting to some local point, or, say, repelling from global center. vMF distribution has been applied for high-dimensional directional data analysis, particularly in applications textual data and with a focus clustering (Banerjee et al. (2005) and Gopal & Yang (2014), also see Sra (2018) for a recent overview). However, to the best of our knowledge, prior work considered some given fixed parameters of interest (usually focusing on estimating them, sometimes on using them for generating exercises); while this paper is inter- ested exclusively in data- gentragnnn models, and treats at least some of these parameters (e.g., mean direction μ1) as endogenously defined within the model itself.
In the DPP model, the first entity (Po, Wo) is initialized with pu = 1 and |woll| = 1. Given the total frequencies of entities n. the exponential dis- tribution exp(3) with parameter B, and the probability of increasing the frequency of an old entity g, the DPP model involves (1) selection as origin of an existing entity w, randomly with a probability proportional to its frequeney; and then (2) at each iteration with probability ei- ther (2a) an increase of the frequency of the chosen w, by 1; or (2b) creation of new entity around the origin w;, i.e., w; w; + I2. In
contrast to the previous model, however, now the direction is distributed 8t (MF (a)),, Rs., with mean direction vector ft pointing away from the global center of mass wf." The generated points of this model is illustrated on figure to the right where higher weight nodes are close to each other.
B) Generating edges of graph.
B1) BA-Embedded model. The BA model uses a preferential attachment process (Barabási & Albert, 1999) generate networks of edges, as opposed to the previously described preferential placement models for points. We use the BA model to generate a random graph and then apply standard graph representation learning algorithm to obtain an embedding.
RRecall that the exponential distribution with scale parameter /3 is denoted as exp(3) and its probability density function is given by (x; () = 1/8 exp(-eppee - /2)B when 2 0, 0 otherwise.
'That is. | || = 1. || is the normm i..., ||>||| V x?- For example, when d' = 2, the offset term [rx cos(@: ( r. sin(O:) with angle 0e (4(0, 2nT).
'We define the center mass as the weighted average all points, that is E p,W, This center of mass moves each iteration t.
4

---

Under review as a conference paper at ICLR 2022
Denote the number of nodes at time as ny. Each new node is added the network and connected to node n, with probability 9e = p:/ Σ, Pj. where weight Pj is the degree of node j.
Our BA-Embedded model starts by creating star graph with m + nodes where node 0 connects all other nodes, that is, 1/m equals to the probability of generating new nodes. Let L < {(0, 1), (0, 2), ..... ation f, the model generates a new node and randomly select m targets from current graph, where each edge connects the node and node from selected m targets. After creating m new edges, the model adds these edges into L, f.e., f L ((i,4), f2), -........ (m)). We peat until n. nodes are generated and obtain the final edge list L. For generating embeddings, we use DeepWalk (Perozzi et al., 2014) generate the corresponding em- bedding vectors with L as an input graph. As shown in figure left, these generated 3- 3-dimensional points form a cluster where points smaller weights (less prominent nodes) spread out of the clus- ters while higher degree nodes are densely correlated. Compared with PP model, lower prominence points BA-Embedded model are smoother located around the cluster.
................... (0, m)} be the initial list of edges. At each iter-
B2) BA model with gravitational movement (BA-Gravity).. Instead of directly using DeepWalk to generate embeddings, we treat the graph generation process sequence edge generation, and then update the embeddings by their weights. Effectively, we extend the BA model with a more sophisticated mechanism dependence on neighboring spatial context. Algorithm presents the BA-Grrvvity model. It first obtains sequence of edges the simulated graph and then initializes each new entity either from (O( Ia) from [[_-5, 5) (Line 4-9). After list of edges are generated by BA-model, for node u, updates embedding wa by moving 1/(p. 1) away of itself but in the direction to w i.e., p.+1 w + pa w. We call this update step "gravitational movement" since its neighbor node v attracts to itself and away from its original location. The generated 3-dimensional points by Algorithm are shown in figure right. Clearly, higher degree nodes are closely located.
Denote by as the time of node v being the neighbor of u. During the whole process of BA-Gravity, any time one can verify that is given by wi P. w +
Algorithm BBA-Gravity model
I: L list of edges by the BA model
2: / {), 0,
1 " -. w/ + W Σ ΣjEN()) 1 w Therefore, P-
3: for e' u) E C do
p. one can treat Algorithm I as the first-order approxima- tion of U = (aol + ai a2 +.... at, A9) R, where A is the normalized adjacency matrix, I is the identity matrix, and R random matrix. This em- bedding approximation has been explored in fast graph embedding algorithms (Zhang et al., 2018: 8; Chen et al., 2019).
4: If u Vr then
5:
w. ~ Ao,
Ia) or (
6:
y V U
If v 4 then
w N/ La) (aru((1,,,, 5)/d
9:
yt+1_ Ue
10:
= 1.
+
11:
w Py w +
w
Putl
Pu
12:
w P w Pu
To fur- ther extend the BA-Gravity model, instead updat- ing two nodes, update the node itself whenever the model creates new node. That is, at each iteration, only updates the embedding of the node by taking average of its neighbors' embeddings. Let w; be the current embedding to be updated. There are two options of taking this average: 1) simply taking average of all neighbors, i.c., w, [a()]] EveN()) w. and we refer this model as
B3) BA- EA-CeenruiddNNoee---vrgggeee
13:
1=141
14:
end for
15:
Return W
BA-Centroid-Na: and 2) taking weighted average, i.c., w, EE EvEN(Y) Pe w. We refer to it as BA-Centroid-NW.
Bi-Centmiid-WW
BA-Cemokk-tW
B4) Ba-Ceettoidddddeee-vvvaaggggggg BA-Centroid-NA and BA-Cen EA-Centroid-NNW edge-based models update embeddings both new node and its neighbors by tak- ing average of their neighbors. We call these two methods
Compared to
5

---

Under review as a conference paper at ICLR 2022
CENTROID- EA and CENTROID- EW respectively based the two average strategies above. We illustrate the points of BA-Centroid-NW: and BA-Centroid-ED model.
FREQUENCY CONCENTRATION
New entities emerge in the shadow of older, more prominent entities, creating cluster structures which should be apparent in both model and real-world embeddings such as GloVe (Pennington et al., 2014), word2vec (Mikolov et al., 2013b), and DeepWalk (Perozzi et al., 2014).
Study of relationships between spatially in geography. Similar methods are also relevant for quasi-spatial data in other domains: what is sometimes called the "first law" of geography states that "Everything is related to everything else, but near things are more related than distant things" (Tobler, 1970). Popular measures of spatial autocorrelations include (1) Moran's s I, which may be thought of spatial analog of Pearson's correlation coefficient and is sensitive to extreme values of the variable (Moran, 1948); as well as (2) Geary's 's C, which is sensitive to differences in small neighborhoods (Geary, 1954). A very accessible textbook treatment is available in O' Suulivan & Unwin (2010); also see Anselin (1995). For examples of usage see: in epidemiology Ganegoda et al. (2021), 1), in linguisties Grieve (2011).
entities have naturally been an important focus
We design our own statistical metric capturing the geometric properties of the embeddings intro- duced earlier in non-parametric manner. 6 The key idea of the proposed index measure frequency concentration has three parts. First, we build a k-nearest neighbor similarity graph G(V, E) based on d-dimensional node/word embeddings, i.c., W E Raxd The potential measure function could be either Gaussian Kernel function or a cosine similarity. The frequencies of the one-hop neighbors of each data point this graph (e.g., a node or word) can be interpreted as frequency rank (from 1 to n), and these sum of ranks normalized to get a value from 0) to 1. We define an index from the area under the cumulative distribution function (CDF) of the neighbors' rank as a measure of spatial autocorrelation. More formally, we assume the set of entities considered is V = 21,2,..... n.. Each v E V has a prominence associated with it, denoted as Pu (e.g. node degree or word frequency).
Definition (Frequency concentration index). Denote the prominence Pv for all nodes in V. Let the ranking function r(p) R" + T(V) where π is a permutation of V where vu the ranking of node o taking a value [1, Given k and any embed- ding matrix W E [guxd we define N (v; k, W) as set of one-hop k-nearest neighbors of v based on some chosen similarity function on W. Then the Index of U can be defined as the following:
vector p
PI.P2...... P.. PT.
Index (w; k W)
1 Σ TI
[ru (i E (W)ss =1
Σ
T2-
(1)
k
Intuitively, if most of neighbors have high rankings, then the index is close to 1 while if neighbors have low rankings, it is close to O. Each term in the summation of Equation (1) can be viewed as reflecting the effects of preferential attachment.
Frequency concentration of word embeddings: We present the frequency concentration plots for different embeddings including Fasttext (Mikolov et al., 2018), word2vec (Mikolov et al., 2013b), and GloVe (Pennington et al., 2014) in Figure 1, comparing the frequency correlations of English words embedding that are from eight diffferent models and data sources. Figure shows that the frequency concentration is remarkably consistent across different data sources and algorithms, that is: the higher frequency words tend to have high frequency words as their close neighbors, while low-frequency words live in poorer neighborhoods. It is tempting to view this as a manifestation of relational, spatial Matthew effect.? Results in the appendix show similar frequency concentration across a broad range of non-English languages. We also investigate how the frequency correlations change with respect to the parameter and d. More detailed results can be found in Appendix B.
F Frequency concentrations of graph embeddings Table 1 shows that the slopes of the best lin- ear fit are consistently negative across four diverse graph datasets (detailed in Table 3 and Figure
II the interest of completeness, we also provide results for the classical Moran's 7 and Geary's C statisties. Oriiinally christened by Merton (1968), and in our case implying that not only "the rich get richer", hut also that "they befriend other riches".

---

Under review as a conference paper at ICLR 2022
Feg Concettatinn
fasti oxt Wiki
Text Wili-Sub
fastl ext CC
fast CC
word vec- News
Glove 68
Glove 420
Glove 8400
33K 70k. Ranking
30C
30x 70K
30C 10K
fanking
Ranking
Ranking
Randing
Parking
Kanking
Ranking
Figure 1: Frequency concentration of eight distinct English word embeddings. The observed frequency concentration is similar even though trained on different data sources (e.g.. Wikipedia (Wiki), Common Crawl (CC/42B/840B/Sub), and Google News (News)) and different embedding algorithms including GloVe, fastText, and word2vec. Each dashed red curve linearly fitted where linear coefficient is presented on each legend.
in the appendix) for four distinct algorithmic approaches to graph embeddings. As with language vocabularies, the frequency concentration plot decreases consistently with rank across diverse em- bedding models for the all graphs. The consistency of these results across domain and algorithm mark negatively-sloping frequency concentration as a property to preserved in any meaningful generative model of embeddings.
LLE
FastRP
DeepWalk
LINE
Coauthor
-0.1582
-0.4932
-0.3780
-0.2088
Wikipeople
-0.3498
-0.1730
-0,2708
-0.1760
Patent
-0.5619
-0.7356
-0.6705
-0.5832
PPI
-0,2739
-0,5144
-0.3459
-0,4092
Table I: The frequency concentration slope of graph embeddings are consistently negative across four algorithms/datasets.
Model validation. We evaluate the frequency concentration of proposed generative embedding models in Figure 2, with proximity measured by cosine similarity. Clearly, embeddings of models with fitted negative coefficient are more likely close real-world embeddings shown in Figure 1. Only the context-aware variations of preferential placement and BA models match the data. Figure demonstrates that the observed properties of such representations consistent across four different graph embedding algorithms.
100
1300
1300
150
200
100
180
100
13:0
n0o
1300
Ni L86
Figure 2: Frequency concentration plots for all nine different models where each model generates 2000 points with d = 128. The parameter i of the Index for each node set to 10.
4 CLUSTERING VELOCITY
The spatial-frequency concentration presented above provides one dimension to compare real-world embeddings to models. We now analyze the spatial characteristics of embeddings for clustering structures independent of frequency, and propose two distinct indices to measure the cluster velocity of the n-eeahost-neighhor (k-nn) graph induced from the vector representation space.
Since embeddings W E Raxd are optimized to preserve the natural clusters of the real-world knowledge its metric space, its pair-wise similarity graph Ginttric E RR=x encodes the embed- ding spatial characteristics vertex connectivity. We hypothesize that the k-NV graph G induced from real-world Gmetric should share common connectivity patterns, particularly in the number of connected components when perform agglomerative clustering.
For example, consider point set drawn from independent, well- sell-separated Gaussian distributions, and hence containing natural clusters. We anticipate that any single-link agglomerative clustering procedure from shortest to longest edge will quickly identify these clusters, but many short edges must be evaluated as potential merges before the separate components unified by long inserted
7

---

Under review as a conference paper at ICLR 2022
Word Embeddings
Graph Embed dinns
Models Generated
Connected Compooing
8
Insected Edges (%)
Inserted Edges (%)
Inserted Béges
Connecced Compenents
203
00
Leauthoncag Coantionn Fastip
Wikepuppee 1ip
Beet CC
Willeweeeee INE
CC 428
Fastz?
Singlo Grassiaa-
BA Centroid EA
Glawwe-Thiite BERT
Patani Paten--reeeia Progwail Pater FuScRP
STL-Daoown. PastRP
JPP
BA BA-Contteod NAV
10'
Gravity
10a Gamma
Gamaa
Gamma
Figure 3: Top: The number of connected components as a function of inserted edges. Each col- umn shares legend. Bottom: The number of connected components
function of y in graph partitioning methods Clauset et al. (2004) in log-scale. We sampled top 30K and 10K vectors from embeddings visualize clustering velocities, except for smaller PPI graph which has only 3,980 nodes. All real-world embeddings share similar clustering velocity pattern, while model generated space have distinct shapes.
edges. The number of connected components will decrease at a slow velocity until eventually all vertices are merged into single integrate component. This merging process will happen more quickly for p than p = 2.
Empirical clustering velocity from real-world and model generated embeddings. Figure (top) presents the clustering velocity for the word, graph, and model embeddings we have described. As expected the multiple Gaussian model (upper right, curve muulti-Gaussian in Figure 3 clusters slower than a single Gaussian. While point set of uniform distribution may not have such hicrar- chical cluster formation process, thus, yielding distinct characteristics in term of clustering velocity as shown in the same subfigure. Furthermore, second columns of the top row) have similar curve shape, reflecting non-trin non-trivial ubiquitous geometric characteristics in the original embedding space.
observed all word and graph embeddings (first and
Agglomerative clustering velocity index: We define the following Clustering Velocity-AUC in- dex (CV-AUC) measure the cluster formation characteristic of agglomerative clustering as fol- lows. We construct the neighor graph using cosine distance as G (V,E). | n, E (eiyle eue = (w..eooe w.); + U; u, E V) Then, given empty edge set E = 0, we construct the graphs by inserting [g] edges in ascending order. We denote fa(t) = |( St .... $ as the number of connected components, where S is the 5thh connected component in graph G after gth insertion. The Clustering Velocity is defined as the normalized AUC of ft(t):
Indexev-AUC (9) = L.
Sonn
|8 dt E (0,
(2)
Clauset-Newnin -ew-ee--ma-nrrre Clustering Velocity (CV-CNM) In addition, similar entities tend to have closer proximity in the embedding space, yielding graph clusters having stronger/denser intra- group ties/edges. We are interested in finding how inter/intra-clustrss take shape, specifically, how fast the big components branch into sub-clusters as we cut the edges. Therefore, we use a modularity- based graph partitioning algorithm Clauset et al. (2004) as another way to inspect the clustering velocity as we tune resolution parameter from small to large. As shown in the bottom row of Figure (in log-scale), likewise, all real-world embeddings share the velocity pattern which is similar to power law, while various models (subfigure on the bottom right) have distinct shapes.
Given W and & as described in Definition 2, we use modality-based graph partition method to cut G into sub-graphs S E (87, Sy,.., S.... S?)
with varying resolution parameter I' E (74/7k 2 A E
distcco (1 calcullttes cosine distance
8

---

Under review as a conference paper at ICLR 2022
Σ}, where Sg is the htth component. We define the index as the error of power-law fitting:
IT
CV-CNM = [ E (yk fo(xx)), Ia = log(?), Us = log(15")), fG( = wg * x bg.
where wgg and by are the fitted parameters associated with KNN-graph
Model Evaluation: We visualize these proposed indices, including Frequency concentration, for each embedding in Figure (left, middle). On left, the horizontal and vertical axis represents CV- AUC and CV-CNM, respectively. All the word and graph embeddings of various methods (shown with red and blue markers on left) have similar range, demonstrating the existence of invariant clustering velocity patterns among real- ceal-world embeddings. Although the model generated spaces have distinct values, the BA-Cen -BA-Centriid-i (oooldddwwWWWWWWW (WW,EW) and DPP-family 9 models are demonstrably closer the real ones.
0.0
0.0
0.
Frequency Concentration
Prequency Concentration
.0.2
-02
CV-CNM
24
.0.4
-4
2.6
0.2
0.
0.0
4.0
0.5
0.2
0.00
0.25
1.00
CV-AUC
CV-AUC
Moran-1
BA Centroid-EW RM-Centroid-MM
Embedded RA-Crwiity
Multi
Graph
Cgll-Caussoon
Figure 4: The visualization of weal-world and model generated embeddings (dim 300) in the plane of two proposed clustering velocity indices, frequency concentration, and spatial autocorrelation indices. Real-world embeddings share similar pattern as several model generated embeddings (BA- Centroid-[NW.Ze) and DPP ), while other models do not. Each model is represented with five distinct hyper-parameter configurations. On right, frequency concentration correlates well with the spatial autocorrelation statistic Moran's [-0.810] (and with 1-Geary's C [-0.450] in Figure 9 in
Appendix).
CONCLUSION AND FUTURE WORK
In this paper, explore invariant spatial characteristics of embeddings and propose several models that reconstruct the observed properties of frequency concentration and clustering velocities of real- world embedding spaces. Our computational tools document consistent empirical phenomenon (not an artifact) across many word and graph data sets as well as embedding algorithms that requires explanation. Especially interesting findings are the positive association between entities of similar importance, suggesting a spatial kind of Matthew effect, as well as a particular connectivity of the clustering structures that is characterized by power law in relational sense; which, turn, seem to be the fundamental processes underlying the formation of clusters in an embedding network.
We present an evolving collection of instructive generating models, starting from simple processes that are agnostic about their local and global neighborhoods and progressing to more complex al- gorithms that account for spatial interdependence between generated entities. The latter behave like what is observed in typical language/graph datasets, and, we have shown, position points naturally correlated patterns and into cluster structures akin to those observed in the wild.
Our work raises several interesting questions. Our experiments were not of sufficient resolution to identify a single dominant model for reasoning about the origins and structure natural embed- ding spaces but they start. We believe well-supported natural model will be a substantial contribution to understanding the evolution of knowledge structures in several domains.
An interesting direction of research would be to study the effects of spatial dependencies within the generating process, the contribution of different attractive and repulsive forces, the importance of defining the context of their sensitivities being global as opposed purely local. There is also need for better nonpparamttric statistics to define over embedding spaces that capture properties of frequency association and cluster structures.
PP models do generate significant frequency concentration Figure (middle) shows.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Rami Al-Rfou, Bryan Perozzi, and Steven Skiena. Polyglot: Distributed word representations for multilingual nlp. In Proceedings of the Seventeenth Conference on Computational Natural Lan- guage Learning, pp. 183-192, 2013.
Réka Albert and Alsert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
Carl Allen and Timothy Hospedales. Analogies explained: Towards understanding word embed-
dings. In International Conference on Machine Learning, pp. 223-231. PMLR, 2019.
Carl Allen, Ivana Balazevie, and Timothy Hospedales. What the vec? towards probabilistically grounded embeddings. Advances in Neural Information Processing Systems, 32:7467-7477, 2019.
Carl Allen, Ivana Balazevic, and Timothy Hospedales. Interpreting knowlege graph relation repre- sentation from word embeddings. In Ninth International Conference on Learning Representations 2021.
L. Anselin. Local indicators of spatial association- lisa. Geographical Analysis, 27:93-1155 1995.
Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, and Andrej Risteski, latent variable model approach to pmi-hased word embeddings. Transactions of the Association for Computational Linguistics, 4:385-399, 2016.
Arindam Banerjee. Inderjit S Dhillon, Joydeep Ghosh, Suvrit Sra, and Greg Ridgeway. Clustering on the unit hypersphere using von mises-fisher distributions. Journal of Machine Learning Research, 6(9), 2005.
Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-512, 1999.
Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. Enriching word vectors with subword information. Transactions of the Association for Computational Linguistics, 5:135-146, 2017.
Haochen Chen, Syed Fahad Sultan, Yingtao Tian, Muhao Chen, and Steven Skiena. Fast and ac- curate network embeddings via very sparse random projection. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pp. 399-408, 2019.
Aaron Clauset, Mark EJ Newman, and Cristopher Moore. Finding community structure in very
large networks. Physical review E, 70(6):06611) 11, 2004.
Jacob Devlin, Ming- bidirectional transformers for language understanding. arXiv preprint 1xXiv1180004480 2018.
Meng Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep
F. Eggenberger and G. Pólya. über die statistik verketteter vorgänge. 7AMM Journal of Applied Mathematics and Mechanics /Zitschhiif fürr Angewandte Mathematik und Mechanik, 3(4):279- 289, 1923.
Paul Erdos, Alfréd Rényi, et al. On the evolution of random graphs. Publ, Math. Inst. Hung. Acad. Sci, 571):17-60, 1960.
Naleen Chaminda Ganegoda, Karunia Putra Wijaya, Miracle Amadi, K. K. W. Hasitha Erandi, and Dipo Aldila. Interrelationship between daily covid-19 19 cases and average temperature as well as relative humidity germany. Scientific Reports, 11(11302) 2021.
Robert C Geary. The contiguity ratio and statistical mapping. The incorporated statistician, 5(3): 115-146, 1954.
Siddharth Gopal and Yiming Yang. Von mises-fisher clustering models. In International Conference Machine Learning, pp. 155-162, PMLR, 2014.
10

---

Under review as a conference paper at ICLR 2022
Edouard Grave, Piotr Bojanowski, Prakhar Gupta, Armand Joulin, and Tomáš Mikolov. Learning word vectors for 157 languages. In Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018), 2018.
Jack Grieve. A regional analysis of contraction rate in written standard american english. Interna- tional Journal of Corpus Linguistics, 16(4):514-554 554, 2011.
Xingzhi Guo, Baojian Zhou, and Steven Skiena. Subset node representation learning over large dynamic graphs. arXiv preprint arXiv:2/06.01570, 2021.
William L Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning, 14(3):1-159, 2020.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983.
Armand Joulin, Piotr Bojanowski, Tomá' Mikolov, Hervé Jégou, and Édouard Grave. Loss in trans- lation: Learning bilingual word mapping with retrieval criterion. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 2979-2988 2018.
Omer Levy and Yoav Goldberg. Neural word embedding as implicit matrix factorization. Advances in neural information processing systems, 27:2177-2185, 2014.
Shaohua Li, Tat-Seng Chua. Jun Zhu, and Chunyan Miao. Generative topic embedding: a continuous representation of documents. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 666-675 2016.
Robert K. Merton. The matthew effect in science. Science, 159(3810):56 1968.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word represen- tations in vector space. arXiv preprint arXiv:1301.378. 2013a.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. Distributed representa- tions of words and phrases and their compositionality. In Proceedings of the 26th International Conference on Neural Information Processing Systems- Volume 2, pp. 3111-3119, 2013b.
Tomáš Mikolov, Edouard Grave, Piotr Bojanowski, Christian Puhrsch, and Armand Joulin. Ad- vances in pre-training distributed word representations. In Proceedings of the Eleventh Interna- tional Conference on Language Resources and Evaluation (LREC 2018), 2018
Patrick AP Moran. The interpretation of statistical maps. Journal of the Royal Statistical Society. Series (Methodological), 10(2):243-251, 1948.
David Sullivan and David Unwin Geographic Information Analysis. John Wiley & Sons, Inc., 2010.
Kyubyong Park. word2vee MultiLanguages, 2016. Available at https://githhb: com/
Kyubyong/ hatpoyyoggwwovvetttoooo www.wwwwodo......ooo
Jeffrey Pennington, Richard Socher, and Christopher D Manning. Glove:
Global vectors for word representation. In Proceedings of the 2014 conference empirical methods in natural language processing (EMNLP), pp. 1532-1543, 2014.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 701-710, 2014.
D.J. de Solla Price. general theory of bibliometric and other cumulative advantage processes. Journal of the American Society for Information Science, 27(5):292-33) 206-20 1976.
Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embed- ding. science, 290(5500):2323-22222
2000.
Herbert A. Simon. On A Class Skew Distribution Functions. Biometrika, 1955.
12
11

---

Under review as a conference paper at ICLR 2022
Steven Skiena and Charles B Ward. Who's 's bigger?: Where historical figures realty rank. Cambridge University Press, 2014.
Suvrit Sra. Directional statistics in machine learning: A brief review. In Thomas Verdebout Christophe Ley (ed.), Applied Directional Statistics, pp. 275-292. Chapman and Hall/CRC, 2018.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In Proceedings of the 24th international conference on world wide web, pp. 1067-1077, 2015.
W. R. Tobler. A computer movie simulating urban growth in the detroit region. Economic Geogra- phy, 46:234 -240, 1970.
Andrew TA Wood. Simulation of the von mises fisher distribution. Communications in statistics- simulation and computation, 23(1):157-164, 1994.
Han Xiao, Minlie Huang, and Xiaoyan Zhu. Transg: A generative model for knowledge graph embedding. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 2316-2325, 2016.
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrmn: Generat- ing realistic graphs with deep auto-regressive models. In International conference on machine learning, pp. 5708-5711 PMLR, 2018.
Xiang Yue, Zhen Wang, Jingong Huang, Srinivasan Parthasarathy, Soheil Moosavinasab, Yungui Huang, Simon M Lin, Wen Zhang, Ping Zhang, and Huan Sun. Graph embedding on biomedical networks: methods, applications and evaluations. Bioinformatics, 36(4):1241-125) 2020.
George Udny Yule. li.-a mathematical theory of evolution, based on the conclusions of dr. j. c. willis, f. r. Philosophical Transactions of the Royal Society of London. Series B, Containing Papers of Biological Character, 213(402-410)21--37, 1925.
Ziwei Zhang, Peng Cui, Haoyang Li, Xiao Wang, and Wenwu Zhu. Billion-scale network embed- ding with iterative random projection. In 2018 IEEE International Conference on Data Mining (ICDM), pp. 787-796. IEEE, 2018.
Kaitlyn Zhou, Kawin Ethayarajh, and Dan Jurafsky. Frequency-based distortions in contextualized word embeddings. arXiv preprint arXiv:2104.080 1040260 2021.
George Kingsley Zipf. The psycho-biology of language: An introduction to dynamic philology. Houghton, Mifflin, 1936.
George Kingsley Zipf. Human behavior and the principle of least effort: An introduction human ecology. Addison-Wesley Press, 1949.
12

---

Under review as a conference paper at ICLR 2022
A EXPERIMENTAL DETAILS AND DATASETS
A.1 EXPERIMENTAL DETAILS
This subsection presents the experimental details figures shown Section 2. For each of the model, we generate 2000 points in d = 3 dimension space. All models use random seed 17, which is implemented by numpy.random. (aanddmmRandomSstc((1]]].. Other parameter settings of seven models follows.
Gaussian model. Each data point is from (0, Iz).
Preferential Placement (PP) model. The probability of updating the frequency of ex- isting nodes is set 4 = 0.85. The parameter of exponential distribution of radius 3 1.0.
Directional PP (DPP) model. The parameter is set to 1.0. The parameter of expo- nential distribution of radius is 3 = 2.8 and the probability updating the frequency of existing nodes g where set 0.85.
BA-Gravity. The parameter of generating are all from dimensional Gaussian distribution.
edges is set to 20. The initial points
BA-Centroid-NWW BA--Centroid-EW. We share the same parameter setting as BA- Gravity: the parameter of generating m edges is set 20. The initial points all from 3 dimensional Gaussian distribution.
A.2 DATASETS
Table 2 lists word embedding datasets used in this paper, including corpus and dimensions. More specifically, Ve-Ce has versions where one is trained from 840B tokens of English Common Crawl dataset while the other one is trained from 42B.
from different
Embedding Fastlext-Wii Wiki
Source
Corpus
# Embedding
Dim. (d)
(Bojanowski
al.,
Wikipedia
294 (Languages)
300
2017)
Fasttext-CC
(Grave et al., 2018)
Common Crawl, Wikipedia
157 (Languages)
300
Fasttext-
(Joulin al., 2018)
Wikipedia
44 (Languages)
Aligned
Polyglot
(Al-Rfou et al., 2013)
Wikipedia
137 (Languages)
64
GloVe-Twitter
(Pennington al., 2014)
Twitter
1 (English)
25, 20, 200
GloVe-CC
(Pennington et al., 2014)
Common Crawl
2 (English)
300
Glo Wi-i
(Pennington 2014)
al., Wikipedia, gaword
Gi-
(English)
50,
100,
200,
300
word2vec
(Mikolov et al., 2013b)
Google News
(English)
300
word2vec-Poly
(Park, 2016)
Wikipedia Wikipedia
29 (Languages)
100,
200, 300
BERT
(Devlin et al., 2018)
I (English)
786
Table 2: Word embedding datasets.
Source
Nodes / Edges
Description
Coauthor
(Guo et al., 2021)
49,755 755,444
Citation network
Wikipeople
(Skiena & Ward, 2014)
214,010 622,255
Wiki hyper-link network
Patent
(Guo et al., 2021)
46.753 151,464
Citation network
PPI
(Yue et al., 2020)
3,8907 76,584
Biology network for protein interaction
Table 3: Graph datasets
13

---

Under review as a conference paper at ICLR 2022
For each graph, applied graph embedding algorithms (dim 64) following:
Random walk based DeepWalk Perozzi et al. (2014),
Random projection based FastRP Chen et al. (2019),
First-order and second-order proximity based LINE Tang et al. (2015)
Locally linear embedding LLE Roweis & Saul (2000).
Deep
LIME
FaxiRP
Liniz: 1.5.5
3A
LiVE 17022
0.0
0.6
04
02
3.00
1000
2000
1003
2000
3050
2000
7000
7600
Mode met (ongres)
Mode cusc Edegri))
Bode OVTE (degress
Wode rant (fagre))
Figure 5: Frequency concentration of four distinct embeddings of the Wikipeople graph. The ob- served frequency concentration is similar even though trained different graph embedding algo- rithms (LLE, DeepWalk, Line, FastRP).
B
MORE DETAILS IN LANGUAGE FREQUENCY CONCENTRATION
B. FREQUENCY CONCENTRATION WITH RESPECT TO k AND d
Frequency concentration of different i and d. The embedding dimension d and number of neighbors & will affect the linear and exponential fit of frequency correlation. To see this, we study how the parameter k and affect the frequency correlation embeddings of Glote-Twitter and GloVe- Wiki-6B. The comparison of frequency correlation w.r.f different dimensionality (d) and dif- ferent size of neighbors (k). The GloVe embeddings considered in this figure trained on Twitter datasets. d is from 255, 50, 100, 200} and is from {5, 10, 15). We present the results in Table 4-5. When & increases, the linear coefficient of Lin fit also increase.
50
= 100
200
d = 300
d= 25
d = 50
d = 100
d = 200
k
-753
-907
-822
-802
1:
5
-533
-537
-.548
-615
k = 10
-734
-890
-800
-782
k:
10
-510
-515
-52
-596
7: = 15
-721
-879
-790
-770
h:
15
-,996
-501
-51
-.583
Table 5: Coefficients of Linear fit for GloVe Wiki Embedding.
Table 4: Coefficients of Linear fit for GloVe Twitter Embedding.
B.2 FREQUENCY CORRELATION WITH RESPECT TO DIFFERENT LANGUAGES
We consider the frequency correlation learned from different languages in Figure 6.
English
Spanish
French
German
Chinase
Russian
Portuguese
Italian
2.0
Feo Coreatioon
30k Ranking
70W
30x banking
sdk rking
J0k
30c Sansiing
35K Rencing
J0K
30k
7ók
10c Eanking
75k
32K Randing
Parking
Figure 6: Frequency correlation of Polyglot embedding (AI-Rfou al., 2013) function of
ranking of words frequency. Each embedding dimension is d = 64 and k = 10.
14

---

Under review as a conference paper at ICLR 2022
B.3 FREQUENCY CONCENTRATION FOR BERT CONTEXTUAL WORD EMBEDDING
We sample 30K unique words from the most frequent words in GLoVe (English) embeddings, and obtain their contextual embeddings from 250K sentences in Wikipedia's text 10 Specifically, we extract the last layer of BERT output as the intermediate word embeddings. Since one word may appear multiple times in different sentences, intermediate embedding may vary. So we average all the collected intermediate embeddings for each word as its final word representation, then feed them to our frequency concentration and cluster velocity analysis.
For example, the word "embeddings" is tokenized to be [ 'em', '##bbed,, "##dding, '#ts' in BERT's tokenizer. We extract the embeddings of the first sub-token ('em²) as word-level intermediate representation in different contexts (We adopt this practice from Zhou et al. (2021)), ). Then average them up as the final contextual word embeddings for the word "embeddings'. Figure shows the BERT embedding also shares consistent frequency concentration other static embeddings do.
of -rbeddigg
04
07-
06
06
Figure 7: Frequency Concentration was also obseved in contextual word embeddings
C PREFERENTIAL PLACEMENT (PP) MODEL
Algorithm presents the generating process of PP model.
Algorithm 2 Preferential Placement (PP) model
1: Input: the total frequencies of data points, 3 the parameter for Exp distribution, and the probability of increasing the frequency of an old word
2: r Exp(3, n) generate samples of radius from distribution Exp( (3)
3: 0 ~ U(0, 2T, n) b generate n samples of angle from distribution U(0, 2T) a dictionary
4: W {wo 1} where wo
nord-frequency pairs
5: for E {1, 111,,....71 n) do
6: randomly select word w, from W with a prob. proportional to its frequency.
7: if Bin(1, g) = 1 then
8:
W [w
[w,] +1 increase the frequency of an existing word un by
9:
else
10:
w, w; + [r, (0,), r, sin) D create a new word based on w;
11:
W [w,]
add this new word into word-frequency pairs.
12: end
13:
end for
14:
Return W
D DIRECTIONAL PREFERENTIAL PLACEMENT (DPP) MODEL
The exponential distribution is used like before. The von Mises-Fisher distribution, which general- izes the uniform distribution used earlier, for (d dimeession sphere is given by
K 4/2-1
fvMp R)) (2T d/2 14//21//2116
exp (KE xx)..
(3)
Wikipedia text is from Huggingface Wikipedia-Fngghi Dataset
15

---

Under review as a conference paper at ICLR 2022
where random variable R ||=||| = μa, |||||| 1, is the mean direction parameter; 2 is a concentration parameter; 2 2; and La/2-1 1 (x) is the modified Bessel function of the first kind at order d/2 1. Algorithm presents the DPP model.
Algorithm 3 Directional Preferential Placement (DPP) model
I: Input: n. the total frequencies of data points,
3 the parameter for Exp distribution,
q the probability of increasing the frequency of an old word
2: X ~ f(x μ4i x) //X is the direction matrix from one vMF model where æ; is i-th
row of X and specific direction randomly generated from Wood (1994)
3: W +(wo where wa = w/ll > a dictionary of word-frequency pairs n do
for f1.2.....11)
5:
randomly select an word from W with prob. proportional to its frequency.
if (1in(1,9) = then
increase the frequency of existing word w, by 1 W W(w,] W Ww,,] + else
w. w, + T2 2; create new word based w,
10:
W[w]] =
b add this new word into word- ford-frequency pairs.
11: end if
12:
end for
13:
Return W
DETAILS IN MODEL PARAMETER SENSITIVITY
Figure shows the histogram results of each run. We repeat the experiments for 5 times with dif- ferent random seed for each model configuration, where take the combination of The ranges of
are listed below:
2000: 300;
[0.1.2.3.4]
I" mandel-uiiforu"" - () 1" m"model-single gaassssaa"nnn"""
i" model-multi gaussion") ("aum cluster". 12.4.81. "eluter std 000.000..1.11.1011
probability seale parameter
frequency
exp-lambda:
coatral
m: the parameter of generating m new edges
[" model-pref monel--pref-lleeemeen placementt"
"q":10_1, 0.3. 0.5. 0.7. 0.8. 0.9]. "amp-lamhda"
11..2448.66332... 62,66222888
model-dir- miodl-ddr--pef-peee -iit--pef-pllccmmmet"
00.1 ( 0.3. 0.5. 0.7.
0.91. "exp_lnmbaa "111
"Kappa" 1228).
"pp""!"" postivi" -weighted "negative-weighte"""
I" mmdde-ba-grrvitt""
('m':10,, 20, 30. 40, 30. 60]]
[" mndel--a--centridd weieeweideddee
['m":110. 10. 20. 30. 40. s0, 601)
model-lb "model-ba-centron -tt------cnoodddt---------
['m'
maddl-ba--centrod -
-I'm [1m'-100
30.
50, 60])
I" model-ba-centtooke -ecentroiddndde-weeleee weie--e -'m":11 10. 20. 30. 40. 50. 601)
[" monbll-ba-mmheddedd "m':[10]
walks [335]. wall len 1: [5.10]. "window 1 [5]}
F MORAN'S / AND GEARY'S C
We start with the definitions. Each unit y; is characterized by its importance (e.g.. frequency) and d-dimensional location. Another important ingredient is spatial weights matrix with elements Wiy. It is either an adjacency matrix (binary, in {0, 1)). similarity matrix (continuous, in [0, 1)).
Now, Moran's s is defined as:
N
Σ,E, Wiy (J: () - 3))
ΣE Wij
Ex 7)
Then, / E [1; ; means negative autocorrelation (a checkerboard pattern), > means positive autocorrelation (same-color squares one side).
Geary's defined as:
N -
Σ,E, Wig Vigh1 - 43
C
2 Σ E, Wiy))
16

---

Under review as a conference paper at ICLR 2022
20
30
15
20
20
5-
0
0
-0.75 -0.50
0:25
1.00
Frequency Concentration
Moran's
1- Geray's C
BA Ceatroid EA
60
60
GN-Cestroid-B DW
BACCsttzol
BA Embedded
BA-Gravity
20
DPP
PP
0.3
0.4
0.3 0.4
0.5
CV-AUC
CV-CNM
Figure 8: The PDF of discussed statistics for each model running with 5 random seeds and distinct model
combinations as listed above. (n 2000, d 300)
For more intuitive interpretation, may be easier to use == C. Then, C' [-1, C' means negative autocorrelation (checkerboard), C" >> 0 means positive autocorrelation (same-color squares on one side).
We present the correlation between proposed Frequency Concentration (FC) and Moran's / as well as with Geary's 's C in Table 6 and Figure 9.
Spearman corr.
FC
Moran-I
I-Geary's
FC
1,000
-0.810
-0,450
Moran-I
-0.810
1.000
0.662
I-Geary's
-0.450
0.662
1.000
Table Our proposed Frequency Concentration (FC) index is well correlated with classic Moran's I and Geary's C.
1.0
0.0
0.0
Praquenccy Concentration
Proquency Concentration
0.8
202
222
Moran's 1
0.6
-
24
0.
.088
.666
022
-1.8
-888
0.0
-10
1.0
-1.0
-0.5
0.5
1.0
0.00
0.25
0.50
0.75
1.00
-0.5
0.0
0.5
1- Ceary's
C
Moran's I
1-
Geary's
Word
BA-Dentrodd-WW
Rd-bmbdddd GraGrrrity
Malli-Caussion
Graph
BA Centroid NA
Centroid
Single
Figure 9: Moran's 7 and Geary's C are well correlated, and so does our proposed Frequency Con- centration.
17


Reviews:
[{"review_id": "xJ4AQyrsma4", "reviewer": "Reviewer_6Hzd", "summary": "", "questions": "", "limitations": "", "rating": 5, "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)\nThis paper proposes interesting approaches to review popular static word embeddings. The authors try to reconstruct a number of different embeddings based on different node generation models, edge generating models, and their combinations.\n\n1) It is exciting to read the authors’ endeavor on revisiting the old successful embeddings that brought a wide range of breakthrough in NLP.\n\n2) Their approach of viewing embeddings purely as a result of node-only generations vs a product of graph that has both node and edge generations continued by graph embeddings\n seems to be thorough instrument to investigate the embedding spaces.\n\n3) Their findings of frequency concentration (not only highly frequency terms getting richer) and clustering velocity (but also they tend to be together) is useful to support an important observation: there are significant amount of frequency information in learned embeddings.\n\n4) The authors revisit many interesting concepts and ideas in different fields like geography that covers spatial relationships and corresponding philosophy. \n\n\n(Weaknesses)\n1) The primary concern is that reading this paper may not add useful intuitions in the era of contextual embeddings and large-scale language models. If the paper suggests any type of treatment that may alleviate too much dependency on the frequency information; or that can improve the performance of state-of-the-art language models by feeding better initial embeddings, the research will become a gold. But the current draft itself is less likely to impact on our community.\n\n2) All the models and experiments are designed and operated rather passively by tuning the hyperparameters and parameters then comparing the results with the popular learned embeddings. It is of course useful to have such models analyses. However it is more natural for Machine Learning community to fit each model into the training portion of data and validate it on the hold-out set before making comparisons. Otherwise, we cannot say whether each suggested model actually has some degree of generalizability of the phenomena of interests.\n\n3) Indeed, we already understood in both high-level and low-level that these static embeddings largely encode frequency information though they were often argued to encapsulate semantic information. Usual definition of the context in computational linguistics is a set of words in the sliding window of each word, which inevitably connects to learning frequential/distributional similarities rather than precisely semantic and syntactic similarities. It was also studied that frequent words are more frequently updated in SGD framework, sharing the large norms. If we use Gaussian like kernel, it will be not surprising to see these are grouped.\n\n\n", "summary_of_the_paper": "This paper tries to demystify the power of embedding and embedding space, trying to connect the structure of learned embeddings and knowledge generation process. The authors tested Gaussian model, Preferential Placement (PP) model, and Directional Preferential Placement (DPP) model for node generations. The authors also tried to learn embeddings by graph representation learning algorithms after running BA models with several variances with gravitational movement and centroid node/edge weighting.\n\n\n(Main Contributions)\n1) Propose reasonable processes that can explain the evolution of knowledge embeddings in terms of preferential attachment and attractive-repulsive force.\n\n2) Compare observed and generated embedding spaces via non-parametric statistics, identifying frequency concentration and clustering velocity properties.\n\n3) Evaluate and find the best generative process: incremental insertion process with spatial context-dependent preferential attachment.\n", "summary_of_the_review": "(Questions)\n1) Why do you believe that embeddings are optimized to preserve the natural clusters of the real-world knowledge in its metric space? At least the three embeddings used in the paper never explicitly optimize any clustering objectives. They want the words closely in the raw texts locate closely in the Euclidean space. \n\n2) Geometry often means the characteristics of the manifold or topological essence defined by a collection of open sets (that will indeed define suitable metric for metric spaces). Some expressions about geometry or invariance would be too subjectively used.\n\n3) It is interesting to see how clustering velocity is defined as area under the curve in the graph of increasing number of connected components. Different types of graphs (maybe different scale-freeness and degree distributions) naturally differs in this clustering velocity, but it is a bit doubtful that this metric can be drastically different even for two graphs with similar degree distributions by adversarially tweaking couple of local connections. As both models and new metrics are proposed, there must be a natural question about the stability and sensitivity of this metric.\n\n4) More active form of contributions that can impact modern representation learning and transfer-based language modeling will benefit the audiences in the community.\n\n\n(Minor Comments)\nA2) left figure  attach the figure reference as the actual figure is located in the previous page.\n\nA3) figure 5 not in the main draft.\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": "h0SdsrbNSH4", "reviewer": "Reviewer_XDaN", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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. This paper studies data generation processes with the help of embedding spaces. It is an interesting problem, and I think the idea of bridging embedding spaces and data generation processes is worth further exploration.\n2. The authors give a detailed illustration of several data generation methods.\n\n\n\nWeakness\n1. The title is a bit confusing. The authors ask a question \"why do embedding spaces look as they do\" in the title. However, it seems that they did not answer it throughout this submission.\n2. The submission is not self-contained. For example, at the bottom of Page 6, the authors put an important figure in the appendix. However, as noted by the ICLR committee, reviewers are not required to read appendices.\n3. The linear correlations in the experiments seem to be weak, especially in Figure 2. The authors may want to calculate the Pearson's correlation between Freq. Concentration and ranking.\n4. As described in the conclusion section, experiments in this work are not sufficient to identify a single dominant model for reasoning about the origins and structures of natural embedding spaces. I agree that this work gives a good start for an interesting problem. However, since the authors did not give a clear conclusion, the technical contribution of this submission seems to be weak.\n", "summary_of_the_paper": "This paper tries to explore the natural processes that generate new knowledge or concepts. Specifically, the authors propose two metrics to characterize embeddings trained on different datasets. Then, they compare some synthetic data generated by models and real-world data according to the aforementioned metrics. Finally, they conclude that the real-world data can be well simulated by a certain generative model.", "summary_of_the_review": "This paper studies an important and interesting problem. However, it does not provide a good enough solution to the problem to meet the bar of ICLR.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "citGcoJ7Cpm", "reviewer": "Reviewer_bApa", "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": "The strengths:\nS1: This paper studies an interesting problem, to analyze structure evolution from the geometry in embedding space.\nS2: Two novel measures are proposed.\nS3: This paper is well-written.\n\nThe weaknesses:\nW1: There is no problem formulation. It's hard to know what is the computational problem studied in this paper.\nW2: It's not clear how do the proposed measures answer the raised problem.\nW3: There is a lack of discussion of the rationale of the proposed measures.\nW4: There is a lack of empirical validation for the proposed measure.\n\nI have some concerns about this paper. There is no problem formulation. It's hard to know what is the computational problem studied in this paper. It seems that the goal of this paper is only to reveal and explain preferential attachment. It's not clear how do the proposed measures answer the raised problem. What is the intuition of the proposed measure in terms of analyzing structure evolution?  There is a lack of discussion of the rationale of the proposed measures. There is a lack of empirical validation for the proposed measure.", "summary_of_the_paper": "This paper proposes two measures of word/graph embedding to character the evolution of word/graph, i.e., frequency concentration and clustering velocity. Many existing graph generation models are surveyed. The proposed measures are calculated on many real-world datasets.", "summary_of_the_review": "This paper studies an interesting problem and proposes two novel measures. This paper lacks some key elements, such as problem formulation, rationale discussion, and empirical validation. As its too many weaknesses, I have to recommend a reject.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "XnV1tmVg9BY", "reviewer": "Reviewer_rVxQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "\nStrengths.\n\nIn general, I find the question the authors try to address is interesting. The author's methodology of approaching this problem seems fine.\n\nWeaknesses.\n\n- One concern I have is the embedding the authors use. Now NLP community is adapting to embeddings from pre-trained models, e.g., BERT. It seems to me that analyzing these contextual embeddings would be better to understand the question the authors propose.\n\n- Somehow I feel like the evaluation between the embeddings from the generative model and from the real-world is rather weak. I guess another more straightforward way is to show the performance on downstream tasks using the generated embeddings.", "summary_of_the_paper": "\nIn this paper,  the authors try to study if we can learn about the human's process of generating new ideas or concepts from embeddings. The authors first define a set of models for generating embeddings. Then the authors observe two properties: (1) frequency concentration, and (2) cluster velocity. The authors finally compare the embeddings from generative models with the embeddings from real-world data driven methods.", "summary_of_the_review": "\nIn sum, I think the authors look at an important problem. But there are some limitations of this study, e.g., not looking at contextual embeddings.", "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: The authors of this work introduced new metrics for node embedding that can measure the evolution of the embeddings, and compare them with existing graph embedding approaches, and experimented on real datasets.

All reviewers agreed that the work addresses interesting problem and that the proposed measures are nove, but there are too many flaws in the initial version of the paper, and despite the thorough responses of the authors, it is believed that there are still too many open questions for this paper to be accepted this year ICLR.
Decision: Reject