Year: 2021

Abstract:
Embedding-based approaches find the semantic meaning of tokens in structured data such as natural language, graphs, and even images. To a great degree, these approaches have developed independently in different domains. However, we find a common principle underlying these formulations, and it is rooted in solutions to the stable coloring problem in graphs (Weisfeiler-Lehman isomorphism test). For instance, we find links between stable coloring, distribution hypothesis in natural language processing, and non-local-means denoising algorithm in image signal processing. We even find that stable coloring has strong connections to a broad class of unsupervised embedding models which is surprising at first since stable coloring is generally applied for combinatorial problems. To establish this connection concretely we define a mathematical framework that defines continuous stable coloring on graphs and develops optimization problems to search for them. Grounded on this framework, we show that many algorithms ranging across different domains are, in fact, searching for continuous stable coloring solutions of an underlying graph corresponding to the domain. We show that popular and widely used embedding models such as Word2Vec, AWE, BERT, Node2Vec, and Vis-Transformer can be understood as instantiations of our general algorithm that solves the problem of continuous stable coloring. These instantiations offer useful insights into the workings of state-of-the-art models like BERT stimulating new research directions.

heading: 1 INTRODUCTION
text: Embedding models are ubiquitous in wide range of real-world applications such as information retrieval (Zuccon et al., 2015), natural language processing (NLP) (Mikolov et al., 2013a;b), graph classification (Grover & Leskovec, 2016; Hamilton et al., 2017) and many more. These models map categorical entities to continuous dense representations (typically in Rd) which provide a continuous measure of semantic similarity across categorical entities. Nowadays, there is a heavy dependence on unsupervised pre-trained embedding models across domains like Transformers in NLP (Devlin et al., 2019), Visual Transformers (ViT) in Computer Vision (Dosovitskiy et al., 2020), Graph Neural Networks (Hamilton et al., 2017; Xu et al., 2019b) since they learn rich semantic representations of entities from massive amounts of unlabelled data. With little finetuning, these models achieve stateof-the-art results on most of the supervised downstream tasks like sentiment analysis (Xu et al., 2019a), object detection (Beal et al., 2020), and graph classification (Xu et al., 2019b).
Historically, embedding models were developed almost independently across structured domains such as NLP, graphs, images, and so on. These algorithms use the neighborhood structure around an entity to obtain the embedding for the entity. Interestingly, a popular hypothesis in NLP - Distributional Hypothesis states that the “meaning” of the word is determined by its context (neighbors) (Harris, 1954; Sahlgren, 2008). This hypothesis forms the basis of most unsupervised embedding learning models in NLP (Mikolov et al., 2013a;b; Pennington et al., 2014b; Bojanowski et al., 2017; Sonkar et al., 2020). Similarly, non-local-means, a denoising algorithm in signal processing, tries to find pixels that should be the same based on the similarity of its neighborhood structure (patch of the image around the pixel in this case) (Awate & Whitaker, 2006; Buades et al., 2005). Even Graph neural network (GNN) architectures ensure that information of the surrounding neighbors is systematically incorporated in the embedding of a node, even in supervised settings (Hamilton et al., 2017; Maron et al., 2019; Xu et al., 2019b). Thus somehow various communities working across
diverse domains have narrowed down on an entity’s neighborhood structure to define the entity’s meaning. In this paper, we try to establish this common principle on mathematically robust grounds.
Structured domains can be easily represented as graphs with relations between entities as edges in the graphs. For example in NLP words can be treated as nodes of some graph, and co-occurrence relation between words can be represented as an edge. As mentioned before that graph embedding architectures capture the topological structure around the node in the node embeddings, and if structured domains can be represented as graphs, this raises the question do embedding models from structured domains like NLP and Vision also operate on some domain induced graph and capture neighborhood structural properties in their entity embeddings since we have seen that embedding models across these domains tend to capture “neighborhood” information?
To answer this question, we dive into combinatorial graph theory to understand how to define the notion of structural equivalence a.k.a. isomorphic structures. Weisfeiler-Lehman (1-WL) algorithm (or color refinement algorithm) is the most popular heuristic used to identify graph isomorphism (Weisfeiler & Leman, 1968) and can distinguish a broad class of graphs (Babai & Kucera, 1979). The fixed point solution of 1-WL is called a stable-coloring and has the property that any two nodes with the same color have the same multi-set of colors in their neighborhood. In essence it means if two nodes have the same color, the graph looks structurally identical from these nodes.
Finally to answer the question if embedding models from structured domains capture the domain induced graph’s topological properties in their entity embeddings, one can find links between the mechanics of these models and stable coloring / 1-WL algorithm. In this paper, we establish this connection by providing a general framework linking existing algorithms to stable coloring. We propose a more flexible version of stable coloring (SC) called continuous stable coloring (CSC ) — a strict generalization of SC. CSC states that the similarity of their neighborhoods determines the similarity of two nodes. Based on this notion, we define a series of optimization problems to solve the problem of CSC . We show that various algorithms in NLP like word2vec, AWE, BERT (Devlin et al., 2019), images processing like Visual Transformer (Dosovitskiy et al., 2020), graphs like Node2Vec (Grover & Leskovec, 2016), etc. are essentially solving different instantiations of this common optimization problem.
Current research already establishes the link between the 1-WL algorithm (Grohe, 2020; Morris et al., 2021; Shervashidze et al., 2011; Morris et al., 2017) and GNN architectures, which has sparked a new line of research in improving GNN architectures (Hamilton et al., 2017; Xu et al., 2019b; Maron et al., 2019; Morris et al., 2020a;b). We hope that the new link we establish between stable coloring and unsupervised embedding algorithms will also stimulate new exciting research in embeddings for other structured domains of NLP and Vision.

heading: 2 BACKGROUND
text: In this section, we define a stable colored graph, provide an outline for 1-WL (Weisfeiler-Lehman) graph isomorphism test and General Aggregate and Update (GAU ) for Graph Neural Networks (GNNs). We also discuss how domains of NLP and images can be seen as graphs.

heading: 2.1 STABLE COLORING
text: Let a coloring function C be an overloaded function defined on the vertices as well on set of vertices of G = (V, E) , i.e., C : V → N and C : 2V → {{N}} where N is a set of natural numbers representing colors, and {{.}} is a multiset with overloading defined as C(A) = {{C(v)|v ∈ A ⊂ V}}. We denote neighborhood of a node u ∈ V as N (v) = {u|(v, u) ∈ E}.
Definition 2.1 (Stable Coloring). An undirected graph G = (V, E) is stable colored w.r.t coloring function C if it holds that C(u) = C(v) if and only if C(N (u)) = C(N (v)).
We can extend the above definition to directed graphs and graphs with labels. A directed graph G = (V, E) is stable colored w.r.t a coloring function C : V → N if it holds that C(u) = C(v) if and only if C(Nin(u)) = C(Nin(v)) and C(Nout(u)) = C(Nout(v)) where Nin(u) = {w|(w, u) ∈ E} and Nout(u) = {w|(u,w) ∈ E}. Likewise, an edge-labelled undirected graph G = (V, E) is stable colored w.r.t a coloring function C : V → N if it holds that C(u) = C(v) if and only if ∀l, C(Nl(u)) = C(Nl(v)) where Nl(u) = {w|(u,w) ∈ El} where El ⊂ E for an edge label l.
We also define a weak-stable coloring for a graph G = (V, E) . An undirected graph G = (V, E) is weak-stable colored w.r.t coloring function C if it holds that C(u) = C(v) if C(N (u)) = C(N (v)) where N (u) = {w|(u,w) ∈ E}.

heading: 2.2 1-WL ALGORITHM AND GENERAL AGGREGATE AND UPDATE FRAMEWORK (GAU )
text: 1-WL algorithm: 1-WL is an iterative algorithm to achieve a stable coloring C for G = (V, E) . Let Ci denote the coloring at iteration i. It starts with a coloring scheme C0 such that C0(v) is same for all v ∈ V . In each iteration, it assigns a different color to u and v if Ci(N (u)) 6= Ci(N (u)) until a stable coloring C is reached. General Aggregate and Update Framework (GAU ) For a general multi-layer GNN, the General Aggregate and Update framework to compute node/vertex embeddings (corresponding to colors) of G = (V, E) is given iteratively by:
Ek(u) = f (k) update ( Ek−1(u), f (k)agg ( Ek−1(v) : v ∈ {{N (u)}} )) , (1)
where f (k)agg(.) and f (k) update(.) map vertex multiset embeddings to a metric space such as R d.
In GraphSage (Hamilton et al., 2017), authors showed that the iterative procedure in 1-WL algorithm is analogous to General Aggregate and Update procedure in GNNs. This connection has lead to the research direction where 1-WL is being used as a standard to which GNN architectures are being compared to (Xu et al., 2019b; Maron et al., 2019; Morris et al., 2020b). Xu et al. (2019b) prove that GAU is as powerful as 1-WL if the functions fupdate and fagg are injective.
Various domains such as NLP, Images and Graphs can be viewed as a graph on their elementary tokens. How we construct graphs is explained in section 6.1 and examples are given in appendix B.

heading: 3 RELATED WORK
text: Word embeddings have been popular in NLP since decades (Deerwester et al., 1989; Morin & Bengio, 2005; Mikolov et al., 2013b; Bojanowski et al., 2017). A lot of work has been done to understand the mathematical underpinning of these models, for instance, relation of embedding models to co-occurrence statistics (Levy & Goldberg, 2014; Hashimoto et al., 2016; Allen et al., 2019). Study of empirical properties of these embedding models (e.g. analogies) has also attracted theoretical research (Allen & Hospedales, 2019; Ethayarajh et al., 2019).
Recently, graph community has also seen a surge in learning node and graph embeddings. The notion of capturing the structural neighborhood around a node inside the node embedding has been the driving principle of these semi-supervised node embedding algorithms like node2vec (Grover & Leskovec, 2016), and GraphSAGE (Hamilton et al., 2017). Hamilton et al. (2017) pointed out that their GraphSAGE node embedding algorithm mimics the aggregate and update procedure of 1-WL algorithm. Subsequently, these neighborhood informative node embeddings found their applications in constructing graph embeddings, and thereby used for classification of structurally equivalent or isomorphic graphs (Chen et al., 2019). Xu et al. (2019b) in their GIN (Graph Isomorphism Network) model modified the aggregate procedure of GraphSAGE to construct graph embedders which were provably as powerful as 1-WL algorithm in distinguishing non-isomorphic graphs. This redirected the research into designing more powerful variants of graph embedders like PPGN (Maron et al., 2019) and k-GNN (Morris et al., 2019) which were provably as powerful as 3-WL and k-WL test respectively. Grohe (2020) discusses about these phenomenal works in increasing the expressivity of graph embeddings for supervised graph classification and regression tasks. While this line of research focuses on improving expressivity and generalizability of Graph networks based on its connection to 1-WL, we explore and formalize the unsupervised algorithms under the light of stable coloring / 1-WL algorithm and show that all the current models stem from the common principle that a tokens meaning is derived from its neighbours.
The rest of the paper is organised as follows. We begin with a discussion of connections between discrete stable coloring and non-local means algorithm in Image processing and distributional hypothesis in NLP. We then define a continuous version of SC and develop optimization problems to solve for CSC in section 5. In section 6 we show how current state-of-the art embedding models are solving the CSC problem in disguise.

heading: 4 ALGORITHMS WITH ROOTS IN DISCRETE STABLE COLORING
text: Distributional hypothesis in NLP states that words that occur in similar contexts are semantically similar. Analogously, the non-local means image denoising algorithm in CV literature assigns similar intensity values to pixels that have similar patches surrounding them. The essence of both ideas is that the value of an entity is determined by its neighborhood. In this section, we connect these two ideas to the idea of stable coloring which states that if two nodes in a stable colored graph have same colored neighborhood, they have the same color. The proofs of the following theorems are provided in appendix.
Theorem 4.1. (Distributional Hypothesis(DH) in NLP encodes SC) Let {w1, w2, .., wn} be words in vocabulary, and M ∈ Rn×n is a co-occurrence matrix with entries eij ∈ N containing the number of times wi co-occurs with wj within a fixed context window. Let there be a function f : w → N which takes a word and maps it to a color c ∈ N (assigns meaning in accordance with Distributional Hypothesis), such that f(wi) = f(wj) only if row i is same as row j in matrix M. Construct a graph GDH with words as nodes and edge labels given by M. Then, function f defines a stable coloring on graph GDH .
DH defines words to be semantically same if they are substitutions of each other. In a true graph ( not the one created from samples) their co-occurrence frequencies with other words is exactly the same. Equating color assigned by f to represent meaning of a word as per DH, it is easy to see that words that end with same color are semantically same.
Theorem 4.2. Consider a discrete signal y(x) sampled at n points xi (i = 1, ..., n), and let the sequence p(xi) = (y(xi−t), .., y(xi−1), y(xi+1), .., y(xi+t)) be a patch of neighborhood values around each xi for some context window length t. NLM denoises the signal y(xi), i = 1, ..., n with iterative updates. The fixed point denoised version of the signal yd can be written as follows:
yd(xi) = 1
D(xi) n∑ j=1 K(pd(xi),pd(xj))yd(xj), (2)
where D(xi) = ∑n j=1K(yd(xi), yd(xj)) and K is an arbitrary kernel function. Let the graph Gnlm = (Vnlm, Enlm) where each xi is a node ui in Vnlm and each pair (ui, uj) with |i − j| ≤ t is represented as a directed edge in Enlm with label (i − j). Then the fixed point solution of NLM with Kronecker delta kernel Kδ , yd : N→ R defines a weak-stable coloring over the graph Gnlm.
An image is an example of a discrete signal with pixel intensities as signal values. With Kronecker delta kernel, NLM terminates with the intensity value of yd(xi) = yd(xj) only if pd(xi) = pd(xj). Assigning color to node ni as xi’s final denoised intensity value, one can observe that NLM only terminates when a weak-stable colored graph is defined over the final image. Note that if the pixel values have high variety, then the probability to get a stable-colored graph is high.
From the above two examples, it is interesting to observe that a stable colored graphG emerges from the underlying principles used by two different domains. Both in DH and NLM, the words/pixels that end up with the same color have same colored neighborhood around them. In order to find more connections to stable coloring, especially that of embedding models, we need a continuous representation of color and hence in next section we start building on a novel notion of color.

heading: 5 GENERAL AGGREGATE LEARNING FRAMEWORK FOR CSC
text: As shown in the earlier sections, even discrete stable coloring can be connected to various concepts in NLP and image processing. We find even more deep rooted links between stable coloring and unsupervised learning algorithms in structured domains. In fact, we can view embeddings of each node as a continuous ‘color’ assigned to each node. In order to show these links, we first need to generalize the idea of SC to a setting where we can talk about continuously comparable colors. This section is organised as follows. We first define a CSC problem analogous to SC . We show that this is a strict generalization of SC (discrete) problem. Then, inspired by the GAU for stable coloring, we propose a series of learning problems having GAU at their core (called General Aggregate Learning , GAL in short) . We end this section with a generalized algorithm whose parameters, as we show in section 6, can be initialized in various ways to obtain algorithms in varied domains that have been a de facto standard in those domains since a long time.

heading: 5.1 CONTINUOUS STABLE COLORING (CSC )
text: Let us consider graph G = (V, E) representing the structured domain under consideration. In SC , we assign categorical colors to the nodes of the graph. However, for most analytical tasks, including machine learning, we need to assign continuous labels (or embedding) to the nodes. Hence, we introduce the problem of CSC . Let the domain of colors assigned be a metric space L (eg. Rd) associated with a distance metric D. There are various ways to define similarity metrics in literature based on D. For the sake of discussion in this section, we would use a simple definition of S(x, y) = e−D(x,y). While the theorems with other definitions will change in appearance, they will still maintain the spirit of analysis. We denote the neighbourhood N (u) = {v|(u, v) ∈ E}. Let C : V → L denote the coloring of nodes. We overload the function C, C : 2V → NL, to operate on subset of nodes as given in the following equation. We use the notation NL to denote all multi-subsets of L. C(V ) = {{C(v)|v ∈ V ⊆ V}} (3) We define SN : NL ×NL → R as the similarity metric over the multi-subsets of L via the same similarity S over L and a permutation invariant and injective aggregator function fagg : NL → L as SN (A,B) = S(fagg(A), fagg(B)) where, A,B ∈ NL. (4) We refer to this embedding as the continuous color under CSC . We use this terminology interchangeably as is best for the context. We denote nodes by small case letters (u, v, ...) and the subset/multi-subsets of nodes by upper case letters (A,B, ..) etc. Let us now take a look at the continuous stable coloring formulation (CSC ). Definition 5.1. (Continuous Stable Coloring (L,S, fagg)). The coloring C : V → L of nodes in graph G = (V, E) is called continuous stable coloring parameterised by similarity kernel S : L × L → R for some metric space L and an injective aggregator function fagg : NL → L if the following holds:
S(C(u), C(v)) = SN (C(N (u)), C(N (v))), ∀u, v ∈ V. (5)
In most applications, we look at L = Rd for some d > 0. Essentially, CSC states that the similarity between embeddings of two nodes should be equal to the similarity between the neighborhoods of the two nodes. Thus CSC relaxes the Kronecker delta function of comparison over categories in SC to a general similarity metric over L. In fact CSC is a strict generalization of SC which we show in the next theorem. Theorem 5.1. (SC is a special case of CSC ). Stable coloring (discrete) problem is an instance of continuous stable coloring problem with L = N, S(i, j) = 1(i = j) and SN (s1, s2) = 1(s1 = s2) where i, j ∈ N and s1, s2 ∈ NN. In this case fagg : NN → N function is an injective hash function which maps multi-subsets of N to N.
It is easy to verify the validity of this theorem by using correct values for L,S and fagg as mentioned in the theorem. Next, we define a learning problem GAL which solves the CSC problem.

heading: 5.2 GENERAL AGGREGATE LEARNING (GAL )
text: Consider G = (V, E) representing the structured domain under consideration. In (Xu et al., 2019b), authors showed that GAU framework (equation 1) with an injective fmerge and fagg operations is equivalent to 1-WL which solves SC problem. We define a solution to the CSC problem that is similar in spirit of GAU . However, instead of providing an iterative algorithm like GAU , we pose an optimization objective which, in essence, learns the stable solution directly.
First, we define the notations. Recall that the task is to assign continuous labels to graph nodes in metric space L with distance metric D and the similarity metric is given as S(x, y) = e−D(x,y). Notation for the embedding matrix E is defined in the same way as that of a coloring function C, such that E : V → L and E : 2V → {{L}}:
E : Embedding matrix, E(u) : embedding of node u ∈ V, and E(V ) = {{E(v)|v ∈ V ⊆ V}}. (6)
E stores the color assignments of all nodes in V and is learned in our setting. Let us look at our first optimization objective which follows naturally from the definition of CSC .
Definition 5.2. (Global GAL formulation) Let matrix E ∈ R|V|×d store embeddings (or colors) of nodes in graph G = (V, E) . Then the optimization objective of Global GAL (G-GAL ) parameterized by an injective function fagg : NL → L (where L = Rd) is to learn an embedding matrix E that minimizes the following
E = argmin E ∑ u,v∈V abs ( − lnS ( E(u), E(v) ) + lnS ( fagg(E(N (u))), fagg(E(N (v))) )) (7)
The function fagg can be as simple as a sum operation or as complex as a neural network architecture with learnable parameters. The global formulation follows naturally from the definition of CSC (Rd,S, fagg) problem. Note that we project neighborhood embeddings( or coloring) into the same space as node embeddings. This will be important for subsequent formulations.
Research Question: Can an effective learning strategy be formulated for minimizing G-GAL loss? An effective algorithm for G-GAL formulation can stimulate further research. To the best of our knowledge, we do not know of an algorithm in any domain which uses this formulation. We think a possible reason why it is difficult to learn is that in most applications, we only have access to subgraph samples of the true underlying graph. Working with a sample of neighbourhood ˆN (u) instead of the complete neighborhood implies we are estimating f̂agg(E(N (u))). The errors in S(f̂agg(E(N (u))), f̂agg(E(N (v)))) increase super-linearly with error in f̂agg(E(N (u)). Nonetheless, this formulation can be of independent interest.
The above mentioned issue of multiplying noisy neighborhood estimates motivates us to find a simpler learning problem. We formulate a different learning problem and show in theorem 5.2 that this simpler problem, which we call Node-local GAL (L-GAL ) problem also solves G-GAL problem.
Definition 5.3. (L-GAL formulation). Let matrix E ∈ R|V|×d store embeddings (or colors) of nodes in graph G = (V, E) . Then the optimization objective of L-GAL parameterized by an injective function fagg : NL → L (where L = Rd) is to learn an embedding matrix E that minimizes the following
E = argmin E ∑ v∈V −lnS(E(v), fagg(E(N (v)))). (8)
In the above L-GAL formulation, we uncoupled the G-GAL formulation and thus eliminated the issue of multiplying noisy neighborhood estimates. However, we would like to emphasize that the solution to L-GAL is also a good solution to G-GAL . We quantify this relation in the next theorem.
Theorem 5.2. (L-GAL solves G-GAL ). Let the solution E to L-GAL upper-bounds each term in the summation of loss in equation 8 by some > 0; thus it upper-bounds total loss by |V| . Then the same solution matrix E is a solution to G-GAL with each term in summation upper-bounded by 2 and thus upper-bounding the total loss by |V|2 .
The proof of theorem 5.2 can be found in appendix. Uncoupling works because if you alternately bring E(u) and E(v) closer to fagg(E(N (u))) and fagg(E(N (v))) respectively, it forces the distances between (E(u), E(v)) and (fagg(E(N (u))), fagg(E(N (v)))) to be nearly equal.
5.3 L-GAL WITH SAMPLES FROM G = (V, E)
Often when trying to solve the L-GAL problem, one will be forced to work on sub-graph samples of the graph instead of the entire graph. This can happen for multiple practical reasons : (1) True graph is not known and we have access to the graph only through instances of sub-graphs. For example, true NLP graph is not known. But we have access to NLP text which hints at the graph. (2) Performing gradient descent on the entire graph is computationally prohibitive. For example social networking graphs are massive. In this case one need to sample nodes from V and then sample the neighborhood of these nodes to estimate fagg(N (u)) for all sampled nodes u. To account for this practical scenario, we propose an optimization objective for working with sub-graphs. Let X be the data available for a particular domain, Gx = Vx, Ex be the sub-graph corresponding to the example x ∈ X . Let the neighborhood function restricted to this sub-graph be Nx. We define the
optimization objective as,
E = argmin E ∑ x∈X ∑ v∈Vx −lnS(E(v), fagg(E(N̂x(v)))) (9)
where N̂(u) is neighborhood induced by the sub-graph. Essentially, we consider each node in the sub-graph and its induced neighbours N̂ from the sub-graph as an example and optimize the loss.

heading: 5.4 CSC WITH CONSTRAINTS
text: The problem of CSC , as are most other learning algorithms, is under-specified (particularly when fagg is a highly expressive function). Also, sometimes there is additional information that one wants to induct in the loss function which is not present in graph structure. For example, in commercial product search settings, “nike” and “adidas” get similar embeddings due to similar neighborhood graph structure but one might want that the embeddings learned distinguish between these entities. In such cases, a constraint needs to be imposed in CSC to minimize similarity between such pairs. This concept is generalized by using a negative sampling function NS : V → 2V which defines a set of nodes in 2V on which a constraint needs to be imposed for any given node in V . We write the problem of constrained CSC as follows:
C∗ = argmin C ∑ u∈V,v∈NS(u) − ln(1− S(C(u), C(v))) subject to the CSC condition:
S(C(u), C(v)) = SN (C(N (u)), C(N (v))) ∀u, v ∈ V. (10)
Using the Lagrangian multiplier we can re-write the constrained optimization objective of L-GAL as
E = argmin E λ ∑ v∈V −lnS(E(v), fagg(E(N (v)))) + ∑ v∈V,u∈NS(v) −ln(1− S(E(u), E(v)). (11)
In most applications, λ is set to 1. There are variants of inducing negative loss into a system, e.g., softmax (or sampled softmax) is one such popular variant.

heading: 5.5 OPTIMIZATION ALGORITHM TO SOLVE L-GAL AND ITS VARIANTS
text: We have developed a series of optimization objectives to solve the problem posed by CSC in the previous subsections. We close this section by discussing the algorithms used to solve these optimization objectives. We can use any of the standard optimization algorithms: first order algorithms like gradient descent (Courant et al., 1994), stochastic gradient descent (Kiefer & Wolfowitz, 1952) or second order algorithms like Adam (Kingma & Ba, 2015), Adagrad (Duchi et al., 2011), etc. When solving problem on complete graph, we denote the algorithm asA( G = (V, E) ,S, fagg,NS) which is parameterized by underlying graph G = (V, E) , similarity metric S, aggregation function fagg , and negative sampling function NS : V → 2V . Whenever working with sub-graph samples of the true graph G, we denote the algorithm as as As(X,S, fagg,NS) where X is the data, each element x of which, induces a sub-graph Gx ( The precise definition of this in provided in section 6.1)

heading: 6 INSTANTIATIONS OF L-GAL IN THE LITERATURE
text: Firstly, we describe the construction of the graph for a particular domain and sub-graph induction based on samples from the data. Secondly we summarize the graph construction and instantiations of L-GAL optimization objective for different embedding models in table 1 and discuss some aspects of it in section 6.2.

heading: 6.1 GRAPH CONSTRUCTION.
text: We provide a generic recipe of graph construction on structured domains. Consider for example a domain with token set T . Our graph will have these tokens as nodes. However, we can introduce even higher order tokens by combining tokens. For example, the set T 2 will denote a set of all bi-gram tokens in the domain. We can extend this idea to n-grams by considering the set T n. Thus, the set of all nodes in the graph of domain can be written as
V = ∪ki=1T i, (12)
where k is the gram-depth. The edges in this graph of gram-depth k depend on the application. This is illustrated in figure 1a. In most cases, including the models discussed in this paper, the edges are added on basis of co-occurrence statistics in the data. For example, let us consider the case of NLP. The sentence “The tree fell” in a graph with a gram-depth of 3 will include the nodes {the, tree, fell, {the, tree}, {the, fell}, {tree, fell}, {the, tree, fell}}. If the edges are added on the basis of cooccurrence, then based on the above sentence we add the edges between “The” and “fell,” “The tree” and “fell”, “The fell” and “tree,” and so on. Additionally, edges can have weights corresponding to the frequency of co-occurrence.
While the graph on tokens represents the true graph, the algorithm As which solves the sampled version of L-GAL problem uses the sub-graph of G = (V, E) which is induced by the sample. Considering the sample x ∈ X as a set of tokens x ⊆ T , the graph induced by this set of tokens, Gx = (Vx, Ex) with neighborhood function Nx where
Vx = {v|v ∈ ∪ki=1xi, v ∈ V}, Ex = {(u, v)|u, v ∈ ∪ki=1xi, (u, v) ∈ E}. (13)

heading: 6.2 CURRENT STATE-OF-THE-ART EMBEDDING MODELS ARE INSTANTIATIONS OF L-GAL
text: Now, we summarize the instantiations of As for variety of algorithms in domains of NLP, images, and graphs. For details on working of each algorithm, we direct the reader to the corresponding original papers. We want to point out the usage of exp〈x,y〉 ( or 11+exp (−〈x,y〉) ) as similarity metrics. Under the unit-norm assumption on x and y, a standard assumption for analysis of embeddings, exp 〈x,y〉 = exp (1−D2(x,y)/2) which is only a function of the l2 norm D and inversely proportional to it. Thus, exp〈x,y〉 ( or 11+exp (−〈x,y〉) ) is a valid similarity metric under unit-norm assumption.

heading: 6.2.1 WORD2VEC, NODE2VEC, AWE
text: Theorem 6.1. The algorithmAs for L-GAL initialized with parameters from table 1 for Word2Vec, Node2Vec and AWE leads to exactly the algorithms (with possibly minor variations) as proposed in the original papers of Word2Vec, Node2Vec and AWE
The proof of the above theorem is quite straightforward and is provided in the appendix. The formulation of sampled L-GAL problem provides a natural explanation of why AWE performs better than Word2Vec. Both Word2Vec and AWE operate on the same graph G = (V, E) . However, they compute their estimates of fagg(N̂ (u)) differently. While word2vec performs simple sum, AWE performs weighted sum. One can prove that the MSE error with simple sum is larger than with weighted sum when weights are equal to the co-occurrence frequency. AWE models these weights as these weights are not known apriori and the authors in the paper hint at the learned weights being representative of the these co-occurrence frequencies.
(a) Graph Construction : higher order tokens in a graph
(b) Illustration of how Bert/ ViT follows L-GAL framework

heading: 6.2.2 BERT AND VIT
text: Theorem 6.2. Considering BERT and ViT as stacks of attention layers without any non-linearity and initializing the algorithmAs with the parameters mentioned in the table 1 leads to the algorithms (with possibly minor variations) as proposed in the original papers of BERT and ViT.
The proof of the theorem is provided in the appendix. For this analysis, we will assume that BERT is a stack of attention layers without any non-linearity. BERT and ViT have similar architecture and hence we provide a single proof for them. Let us consider the sub-graph induced for BERT by a sample x, which means it essentially has the nodes ∪ki=1xi. The sub-graph will have every node connect with every other node. Thus when we look at the embedding of a particular masked word, according to definition of fagg for BERT we will get,
fagg(N (u)) = ∑
v∈N (u)
(w(u,v)E(v)), f̂agg(N (u)) = ∑
v∈N (u)∩(∪ki=1xi)
(α(u,v)E(v)). (14)
Now if this is exactly the computation that BERT (or ViT) performs then with softmax style negative sampling loss, BERT will follow the L-GAL optimization. We claim that BERT does indeed compute this f̂agg . Ideally, BERT should learn the embedding matrix for all the nodes including tokens and higher order tokens. However, this is computationally expensive. Hence, BERT actually models the higher order tokens in terms of its component tokens. It can be seen that if the modelling is a weighted linear sum of the components, then BERT essentially ends up computing equation 14. More details can be found in appendix. Also, as in AWE it models the weights in the summation of fagg (via the attention mechanism). The information propagated through BERT can be visualized as shown in figure 1b. At each layer i ∈ {1, .., k}, BERT computes the token embeddings of order i and this information from each layer flows to the masked word node and gets aggregated.

heading: 7 IMPLICATIONS AND CONCLUSIONS
text: In this paper, we define a notion of CSC to understand the internals of wide range of embedding models across diverse structured domains. Grounded on this notion, we propose a generalized LGAL optimization problem that solves for CSC on graphs induced by any structured domain. We thereby prove equivalence between loss functions of popular NLP, image, and graph embedding models and our proposed constrained L-GAL optimization loss operating on domain-specific graphs. The methodology of construction of these graphs is also presented for each structured domain.
Our proposed framework with its robust mathematical founding on CSC us graph theoretical perspective to these unsupervised embedding models. We have already seen great improvements in supervised models based on the connection between 1-WL and GNNs. We believe that our formulation will stimulate further research in embedding models. Insights from the underlying graph view of the computation in embedding models can give us new directions to improve quality and scalability and training efficiency of these models.

heading: A APPENDIX

heading: A.1 A WALK THROUGH POPULAR EMBEDDING MODELS AND UNDERSTANDING THEIR DESIGN PRINCIPLES AGAINST THE BACKDROP OF OUR FRAMEWORK
text: The proposed L-GAL formulation abstracts out different components of embedding models and thus enables design of better embedding models by focusing on these components. The components are as follows,
• Domain Graphs
• fagg Neighborhood aggregation function.
• NS : Negative Sampling set.
• Estimation of fagg(N (u)) via sampling.
One can think of the strategies focusing on these components as ,
1. Better sampling/ estimates of a node’s neighborhoods.
2. Better design of fagg function.
3. Construction of more expressive graphs that embed higher order tokens.
4. Importance based negative sampling to inject knowledge that best negates the neighbor information given by our proposed domain graph.
With these four strategies in place, next we understand the development of NLP models over time by choosing word2vec, one of the most widely-used embedding model, as our starting reference. We demonstrate how our proposed strategies have manifested in different embedding models that have improved over word2vec in last decade.
Recall from table 1, that word2vec uses
• G = (V,E) where V is the set of all single words as nodes and E is the edge between words, say u and v, with co-occurrence as the weight.
• fagg(N (u)) weighted sum of neighbour embeddings • NS(u): All words except u
• Sampling technique : sentences
Strategy 1 : Better estimation of fagg(N (u)) - Glove vs Word2vec Word2vec is an iterative algorithm over sentences. It uses sentence as a sample to guess word’s neighborhood which induces a lot of noise. Our framework would suggest to use the entire computation of fagg instead of sampling if possible for a given fagg and graph. Glove does exactly this. Glove (Pennington et al., 2014a) improves upon word2vec by using global co-occurrence statistics to eliminate noise in these neighborhood estimates. Glove’s optimization objective (given by equation 12 which is simplified to equation 15 in original paper) is as follows:
J = V∑ i=1 V∑ j=1 Xij logQij ,
where V is the vocabulary, Xij is the co-occurrence count of word i with word j in the corpus, and Qij = expwTi wj∑V
k=1 expw T i wk . Note that Glove simplifies Qij = expwTi wj which is identical to the similarity kernel we use in our analysis with unit norm assumption.
Strategy 1, thus, helps us to understand why Glove improves upon word2vec.
Strategy 2 : Better fagg - AWE vs Word2vec Let us now consider another word embedding model, AWE (Attention Word Embedding), that improves upon the CBOW model of word2vec. CBOW model weighs each word equally to compute the context embedding, however, AWE weighs
each context word differently as some context words are more important for prediction of the masked word than others. The context vector in AWE is given by:
cawe = ∑
i∈[−b,b]−{0}
awiuwi where awi = exp ( kTw0qwi ) ,
where where b is the size of the context window and wi is the index of each word (w0 is the index of the masked word; the rest are the indices of the context words), awi is the attention weight of each context word vector uwi calculated using the key matrix K and the query matrix Q. Note that in word2vec awi = 1.
Strategy 2 helps us understand why AWE outperforms Word2vec. AWE formulates a better fagg function as compared to Word2Vec.
Strategy 3 : More informative domain graphs - BERT vs Word2vec As discussed in section ??, BERT uses a graph with higher order tokens. In fact, the highest order of token can be interpreted as the number of layers in ther BERT. It also uses the AWE style weighting of the neighbours. Strategy 3 (along with strategy 2) can help us understand how BERT improves over Word2vec embedding model. Strategy 3 can also help us understand why (Le & Mikolov, 2014; Tang et al., 2015; Liu et al., 2015) can improve over Word2Vec.
Strategy 4 : Better NS - WSD-W2V vs Word2Vec Strategy 4 helps to understand yet another shortcoming of word2vec. Word2vec struggles with modeling antonyms and often brings antonyms close to each other (Thalenberg, 2016). This is not surprising since antonyms tend to occur in similar contexts, i.e., identical neighborhoods. With our proposed framework, one can arrive at this conclusion from a graph theoretic perspective. Antonym subgraphs are isomorphic, and thus antonyms get assigned similar continuous stable colors. To overcome this, one needs to introduce information into the setup using variants of negative sampling. Thus external datasets like wordnet (Orkphol & Yang, 2019) need to complement word2vec’s training strategy for efficient modeling of antonyms.
To conclude, the model design changes that our framework suggest (strategies 1-4) can be found in existing works.

heading: A.2 THEOREM 4.1
text: Let {w1, w2, .., wn} be words in vocabulary, and M ∈ Rn×n is a co-occurrence matrix with entries eij ∈ N containing the number of times wi co-occurs with wj within a fixed context window. Let there be a function f : w → N which takes a word and maps it to a color c ∈ N (assigns meaning in accordance with Distributional Hypothesis), such that f(wi) = f(wj) only if row i is same as row j in matrix M. Construct a graph GDH with words as nodes and its adjacency matrix given by M. Then, function f defines a stable coloring on graph GDH .
Proof: The proof follows trivially from the definition of f .

heading: A.3 THEOREM 4.2
text: Consider a discrete signal y(x) sampled at n points xi (i = 1, ..., n), and let the sequence p(xi) = (y(xi−t), .., y(xi−1), y(xi+1), .., y(xi+t)) be a patch of neighborhood values around each xi for some context window length t. NLM denoises the signal y(xi), i = 1, ..., n with iterative updates. The fixed point denoised version of the signal yd can be written as follows:
yd(xi) = 1
D(xi) n∑ j=1 K(pd(xi),pd(xj))yd(xj), (15)
where D(xi) = ∑n j=1K(yd(xi), yd(xj)) and K is an arbitrary kernel function. Let the graph Gnlm = (Vnlm, Enlm) where each xi is a node ui in Vnlm and each pair (ui, uj) with |i − j| ≤ t is represented as a directed edge in Enlm with label (i − j). Then the fixed point solution of NLM with Kronecker delta kernel Kδ , yd : N→ R defines a weak-stable coloring over the graph Gnlm

heading: Proof:
text: In order to prove a weak coloring, we need to prove that if the neighbourhoods of a pixel are equal then its value is equal. Consider any two pixels xi and xj with same neighbourhoods, Then Kδ(pd(xi), pd(xj) = 1. Let {xk1 , xk2 , xk3 , ...} be the set of size L of pixels whose neighbourhoods that match with neighbourhood of xi and xj . Thus, by equation of final stable solution, both the pixel values are equal to yd(xi) = yd(xj) = 1L ∑L l=1Kδ(pd(xi),pd(xkl))yd(xkl)

heading: A.4 THEOREM 5.1
text: (SC is a special case of CSC ). Stable coloring (discrete) problem is an instance of continuous stable coloring problem with L = N, S(i, j) = 1(i = j) and SN (s1, s2) = 1(s1 = s2) where i, j ∈ N and s1, s2 ∈ NN. In this case fagg : NN → N function is essentially an injective hash function which maps multi-subsets of N to N.
Proof: The proof of the theorem trivially follows by using the parameters of CSC as mentioned in the theorem.

heading: A.5 THEOREM 5.2
text: Let the solution E to L-GAL upper-bounds each term in the summation of loss in equation 8 by some > 0; thus it upper-bounds total loss by |V| . Then the same solution matrix E is a solution to G-GAL with each term in summation upper-bounded by 2 and thus upper-bounding the total loss by |V|2 . Proof:
Loss(G-GAL ) = ∑ u,v∈V abs(− lnS(E(u), E(v)) + lnS(fagg(E(N (u))), fagg(E(N (v)))))
(16) = ∑ u,v∈V abs(D(E(u), E(v))−D(fagg(E(N (u))), fagg(E(N (v))))) (17)
As D is a metric, we have
D(fagg(E(N (u))), fagg(E(N (v)))) ≤ D(fagg(E(N (u))), E(u))+D(E(u), E(v))+D(E(v), fagg(E(N (v)))) (18) D(fagg(E(N (u))), fagg(E(N (v))))−D(E(u), E(v)) ≤ D(fagg(E(N (u))), E(u))+D(E(v), fagg(E(N (v)))) (19)
By hypothesis, that the each term in the loss of L-GAL is bound by
D(fagg(E(N (u))), fagg(E(N (v))))−D(E(u), E(v)) ≤ 2 (20)
Thus ,
Loss(G-GAL ) ≤ ∑ u,v∈V 2 = |V|(|V| − 1) ≤ |V|2 (21)

heading: A.6 THEOREM 6.1
text: Theorem A.1. The algorithmAs for L-GAL initialized with parameters from table 1 for Word2Vec, Node2Vec and AWE leads to exactly the algorithms (with possibly minor variations) as proposed in the original papers of Word2Vec, Node2Vec and AWE
proof It is easy to check that the parameters specified in the table 1 exactly provides the algorithms of corresponding models. Some more details can be found in appendix B

heading: A.7 THEOREM 6.2
text: Considering BERT and ViT as stacks of attention layers without any non-linearity and initializing the algorithm As with the parameters mentioned in the table 1 leads to the algorithms (with possibly minor variations) as proposed in the original papers of BERT and ViT with the linear modelling on embedding of higher order tokens.
Proof: The parameters of BERT / ViT such as loss used, tokens can be verified from the table. It only remains to prove that BERT computation is same as that of fagg mentioned.
This is done under two assumptions, (1) BERT is just a stack of attention layers. (2) each higher order token’s embedding is modelled as a linear model of it constituent embeddings.
Let us consider the token (u, i) to be masked. Without loss of generality let the position in the token be last position. Let each path reaching the level k at masked word be denoted with the locations of the words the path takes at each level. So a path of (0,1,0,2) says that it takes the route of words w0, w1, w0, w2 to reach the masked word at the final level.
Then we can write the new computation of reaching BERT at level k as∑ p∈PATHS(k) k∑ i=1 αipE(w[p(i)]) (22)
This can be seen as the embedding of the path as BERT models it (linear model assumption). It is easy to see that each path of length k maps one-to-one to a higher order token in T k. Under this relation PATHS(k) is exactly the set of all nodes in Sk The information also flows from masked words which aggregates the embeddings of Si, i < k. Thus the final computation of bert at level K looks like
K∑ k=1 ∑ p∈PATHS(k) k∑ i=1 αipE(w[p(i)]) = ∑ v∈SK βvE(v) (23)
for some βs

heading: B EXAMPLES OF GRAPH CONSTRUCTION
text: B.1 VARIOUS DOMAINS AS GRAPHS
Any general set of tokens say T and associated relationR ⊆ T ×T can give us the graph G = (V, E) with V = T and (u, v) ∈ E iff R(u, v) = 1. While the underlying graph of NLP is not explicitly known some examples of relations that can be drawn from the sentence structure are as follows.
• Let V be the set of all words {w1, w2, ...w|V|}. (w1, w2) ∈ E iff the wordsw1 andw2 co-occur in a sentence. Additionally, we can assign a weight to the edge equal to the frequency of co-occurrence observed in some natural language corpus. • Let V be a set of all subsets of T of size less than or equal to k. Let t1, t2 ∈ V then the relation (t1, t2) ∈ E iff t1 ∪ t2 appear together in some sentence in natural language.
Similarly we can also view the entire image collection as a graph G = (V, E) where V is a set of all k × k patches observed in all images ( or alternatively images of a particular category ). Some examples of relations might be,
• R(p1, p2) = 1 iff p1 occurs in a larger patch K ×K around p2 in some images • R(p1, p2) = 1 iff p1 adjacent to p2 in four directions (left, right, top, down)
Graph domain naturally maps to the graph data structure. However, we can construct more informative graphs from the basic graph structure. For example, we can add hyper-edges to add hyper-graph structure to the same graph.

heading: B.2 WORD2VEC
text: Word2vec is one of the standard word embedding models (Mikolov et al., 2013a;b). The continuous bag-of-words (CBOW) model of word2vec predicts a masked word using its context. Let E = [v1, ...,vN ]
T ∈ RN×d be the word embedding matrix where N is the size of the vocabulary, and d is the size of the word vector. CBOW looks at the set of sentences drawn from NLP corpus X and uses it to learn E. For each sentence x of size n, CBOW creates n examples of (u, ctx(u) = {v|v ∈ x, v 6= u}) pairs by choosing one word and using rest of the words as context ctx. It uses the following formulation,
E = argmin E ∑ (u,ctx(u)∈x∈X)
( − ln 1
1 + exp (−〈E(u), E(ctx(u))〉) + (24)
∑ v∈NS(u) −ln ( 1− 1 1 + exp (−〈E(v), E(ctx(u))〉) )) (25)
where E(ctx(u)) = ∑ v∈ctx(u)E(v). Note that original formulation of CBOW uses softmax which is a variant of the negative sampling loss formulation.
We will show in theorem ?? that Word2Vec is indeed same as As using some specific initialization of its parameters. We first define the parameters.
• Graph Gw2v . Let {w1, w2, .., w|V |} be words in vocabulary V , and M ∈ R|V |×|V | is a cooccurrence matrix with entries eij ∈ N containing the number of times wi co-occurs with wj within a fixed context window. Construct a graph Gw2v with words as nodes and its adjacency matrix given by M
• Data Xw2v . Every example is a set of words (sentence) and the graph induced by these words is a sub-graph in Gw2v with every node connecting every other node.
• Aggregation function fw2v . Let fagg(ctx(u)) = ∑ v∈ctx(u)E(v).
• Similarity Metric Ssgm. Let S(x, y) be σ(x, y). Under unit-norm assumption, this is a valid similarity metric derived from l2 norm distance metric.

heading: B.3 ATTENTION WORD EMBEDDINGS (AWE)
text: As can be observed in fw2v , CBOW model equally weights the context words when making a prediction. To address this limitation of CBOW, AWE augments CBOW model with an attention mechanism to attend to context words that are most relevant for prediction of masked word. AWE also uses the same formulation as word2vec given by equation 25, except that context vector is a weighted sum of context word embeddings.
In AWE, E(ctx(u)) = ∑ v∈ctx(u) wuvE(v), where wuv = exp (< ku, qv >) models the importance of context word v for predicting the masked word u using key and query word embedding matrices given by K = [k1, ...,kN ]T ∈ RN×d and Q = [q1, ..., qN ]T ∈ RN×d respectively. As we did for word2vec, we will show in theorem ?? that AWE is indeed same as As using some specific initialization of its parameters. We first define the parameters.
• Graph Gawe. Gawe = Gw2v . • Data Xawe. Similar to word2vec, every example is a set of words (sentence) but unlike the case
of word2vec, the graph induced by these words is a weighted sub-graph in Gawe. • Aggregation function fawe. Let fagg(ctx(u)) = ∑ v∈ctx(u) wuvE(v).
• Similarity Metric Ssgm. Let S(x, y) be σ(x, y). Under unit-norm assumption, this is a valid similarity metric derived from l2 norm distance metric.

Review summaries:
In this paper the authors proposed continuous stable coloring (CSC) as a new framework to unify the understanding of several existing unsupervised learning algorithms, including Word2Vec, BERT, and Node2Vec. The authors show how the original stable coloring algorithm can be understood as optimizing the CSC objective function. The authors also show how to reduce the existing approaches to CSC.

In the paper the authors define a new problem called the continuous stable coloring (CSC). This is an extension of the traditional stable coloring problem, however, instead of having discrete color labels, you have continuous color labels. The authors then provide an objective function that could be minimized to obtain a CSC. They then show that if you tweak the similarity measure $S$ and the aggregator function $f_{agg}$, then the CSC problems various word embedding techniques such as word2vec, AWE, Bert (without non-linearity). 

In this paper, the authors investigate how the solution of the Weisfeiler-Lehman test of isomorphism (WL) is related to embedding algorithms from structured domains. The authors generalize the WL algorithm to the case where the colors assigned to the nodes correspond to feature vectors, and propose a series of optimization problems to solve this problem. Finally, they show that widely used algorithms in natural language processing, computer vision and graph representation learning such as word2vec, BERT, Visual Transformer and node2vec actually solve different instantiations of this common optimization problem.