Year: 2020

Abstract:
This work provides the first unifying theoretical framework for node (positional) embeddings and structural graph representations, bridging methods like matrix factorization and graph neural networks. Using invariant theory, we show that the relationship between structural representations and node embeddings is analogous to that of a distribution and its samples. We prove that all tasks that can be performed by node embeddings can also be performed by structural representations and vice-versa. We also show that the concept of transductive and inductive learning is unrelated to node embeddings and graph representations, clearing another source of confusion in the literature. Finally, we introduce new practical guidelines to generating and using node embeddings, which fixes significant shortcomings of standard operating procedures used today.

heading: 1 INTRODUCTION
text: The theory of structural graph representations is a recently emerging field. It creates a link between relational learning and invariant theory. Interestingly, or rather unfortunately, there is no unified theory connecting node embeddings —low-rank matrix approximations, factor analysis, latent semantic analysis, etc.— with structural graph representations. Instead, conflicting interpretations have manifested over the last few years, that further confound practitioners and researchers alike.
For instance, consider the direction, word embeddings→ structural representations, where the structural equivalence between men→ king and women→ queen is described as being obtained by just adding or subtracting their node embeddings (positions in the embedding space) (Arora et al., 2016; Mikolov et al., 2013). Hence, can all (positional) node embeddings provide structural relationships akin to word analogies? We provide a visual example in Appendix (Section 7) using the food web of Figure 1. In the opposite direction, structural representations→ node embeddings, graph neural networks (GNNs) are often optimized to predict edges even though their structural node representations are provably incapable of performing the task. For instance, the node representations of the lynx and the orca in Figure 1 are indistinguishable due to an isomorphic equivalence between the nodes, making any edge prediction task that distinguishes the edges of lynx and orca a seemly futile exercise (see Appendix (Section 7) for more details). Hence, are structural representations in general —and GNNs in particular— fundamentally incapable of performing link (dyadic) and multi-ary (polyadic) predictions tasks? GNNs, however, can perform node classification tasks, which is a task not associated with positional node embeddings (see Appendix (Section 7) for a concrete visual interpretation of the differences between positional node embeddings and structural representations over node classification and link prediction tasks).
Confirmation bias has seemingly appeared to thwart recent efforts to bring node embeddings and structural representations into a single overarching framework. Preconceived notions of the two being fundamentally different (see Appendix (Section 7)) have been reinforced in the existing literature, arguing they belong in different applications: (Positional) Node embeddings would find applications in multi-ary relationships such as link prediction, clustering, and natural language processing and knowledge acquisition through word and entity embeddings. Structural representations would find applications in node classification, graph classification, and role discovery. A unified theory is required if we wish to eliminate these artificial boundaries, and better cross-pollinate, node embeddings and structural representations in novel techniques.
Contributions: In this work we use invariant theory and axiomatic counterfactuals (causality) to develop a unified theoretical framework that clarifies the differences between node embeddings and
structural representations and emphasizes their correspondence. More specifically, (a) we show that structural representations and node embeddings have the same relationship as distributions and their samples; (b) we prove that all tasks that can be performed by node embeddings can also be performed by structural representations and vice-versa. Moreover, (c) we introduce new guidelines to creating and using node embeddings, which we hope will replace the less-than-optimal standard operating procedures used today. Finally, (d) we show that the concepts of transductive and inductive learning —commonly used to describe relational methods— are unrelated to node embeddings and structural representations.s

heading: 2 PRELIMINARIES
text: This section introduces some basic definitions, attempting to keep the mathematical jargon in check as much as we can, sometimes even sacrificing generality for clarity. We recommend Bloem-Reddy & Teh (2019) for a more formal description of some of the definitions in this section. Definition 1 (Graph). We consider either a directed or an undirected attributed graph, denoted by G = (V,E,X,E), where V is a set of n = |V | vertices, E is the set of edges in V × V , with matrix X ∈ Rn×k, k > 0 and 3-mode tensor E ∈ Rn×n×k′ , k′ > 0 representing the node and edge features, respectively. The edge set has an associated adjacency matrix A ∈ {0, 1}n×n. In order to simplify notation, we will compress E and A into a single tensor A ∈ Rn×n×(k′+1). When explicit vertex and edge features and weights are unavailable, we will consider X = 11T and A = A, where 1 is a n × 1 vector of ones. We will abuse notation and denote the graph as G = (A,X). Without loss of generality, we define number the nodes in V = {1, . . . , n} following the same ordering as the adjacency tensor A and the rows in X . We denote ~S and a vector of the elements in S ∈ P?(V ) sorted in ascending order, where P?(V ) is the power set of V without the empty set.
One of the most important operators in our mathematical toolkit will be that of a permutation action, orbits, G-invariance, and G-equivariance: Definition 2 (Permutation action π). A permutation action π is a function that acts on any vector, matrix, or tensor defined over the nodes V , e.g., (Zi)i∈V , and outputs an equivalent vector, matrix, or tensor with the order of the nodes permuted. We define Πn as the set of all n! such permutation actions. Definition 3 (Orbits). An orbit is the result of a group action Πn acting on elements of a group correspond to bijective transformations of the space that preserve some structure of the space. The orbit of an element is the set of equivalent elements under action Πn, i.e., Πn(x) = {π(x) | π ∈ Πn} . Definition 4 (G-equivariant and G-invariant functions). Let Σn be the set of all possible attributed graphs G of size n ≥ 1. More formally, Σn is the set of all tuples (A,X) with adjacency tensors A and corresponding node attributes X for n nodes. A function g : Σn → Rn×· is G-equivariant w.r.t. valid permutations of the nodes V , whenever any permutation action π ∈ Πn in the Σn space associated with the same permutation action of the nodes in the Rn×· space. A function g : Σn → R· is G-invariant whenever it is invariant to any permutation action π ∈ Πn in Σn. Definition 5 (Graph orbits & graph isomorphism). Let G = (A,X) be a graph with n nodes, and let Πn(G) = {(A′,X ′) : (A′,X ′) = (π(A), π(X)),∀π ∈ Πn} be the set of all equivalent (isomorphic) graphs under the permutation action π. Two graphs G1 = (A1,X1) and G2 = (A2,X2) are said isomorphic iff Πn(G1) = Πn(G2). Definition 6 (Node orbits & node isomorphism). The equivalence classes of the vertices of a graph G under the action of automorphisms are called vertex orbits. If two nodes are in the same node orbit, we say that they are isomorphic.
In Figure 1, the lynx and the orca are isomorphic (they have the same node orbits). We now generalize Definition 6 to subsets of nodes S ∈ P?(V ), where P?(V ) is the power set of V without the empty set.
Definition 7 (Vertex subset orbits and joint isomorphism). The equivalence classes of k-sized subsets of vertices S ∈ P?(V ) of a graph G under the action of automorphisms between the subsets are called vertex subset orbits, k ≥ 2. If two proper subsets S1, S2 ∈ P?(V )\V are in the same vertex subset orbit, we say they are jointly isomorphic.
Next we define the relationship between structural representations and node embeddings.

heading: 3 A UNIFYING THEORETICAL FRAMEWORK OF NODE EMBEDDINGS AND STRUCTURAL REPRESENTATIONS
text: How are node embeddings and structural representations related? This section starts with a familiar, albeit naı̈ve, view of the differences between node embeddings and structural representations, preparing the groundwork to later broadening and rectifying these into precise model-free mathematical statements using invariant theory. This broadening is needed since model-free node embeddings need not be related to node closeness in the graph (or to lower dimensional projections for that matter), as it is impossible to have a model-free definition of closeness.
A familiar interpretation of node embeddings: Node embeddings are often seen as a lowerdimensional projection of the rows and columns of the adjacency matrix A from Rn to Rd, d < n, that preserves relative positions of the nodes in a graph (Graham & Winkler, 1985; Linial et al., 1995); for instance, in Figure 1, the lynx and the coyote would have close node embeddings, while the node embeddings of the lynx and the orca would be significantly different. Node embeddings are often seen as encoding the fact that the lynx and the coyote are part of a tightly-knit community, while the lynx and orca belong to distinct communities. The structural representation of a node, on the other hand, shows which nodes have similar roles (structural similarities) on a graph; for instance, the lynx and the orca in Figure 1 must have the same structural representation, while the lynx and the coyote likely have different structural representations. The lynx, like the orca, is a top predator in the food web while the coyote is not a top predator.
The incompatibility of the familiar interpretation with the theory of structural graph representations: The above interpretation of node embeddings must be tied to a model that defines closeness. Structural graph representations are model-free. Hence, we need a model-free definition of node embedding to connect it with structural representations. Unfortunately, one cannot define closeness without a model. Hence, in the remainder of this paper, we abandon this familiar interpretation in favor of a model-free definition.
Roadmap: In what follows, we restate some existing model-free definitions of structural graph representation and introduce some new ones. Then, we introduce a model-free definition of node embeddings. We will retain the terminology node embedding for historical reasons, even though our node embedding need not be an embedding (a projection into lower dimensional space).

heading: 3.1 ON STRUCTURAL REPRESENTATIONS
text: In what follows we use the terms link and edge interchangeably. Proofs are left to the Appendix. Definition 8 (Structural node representations). The structural representation of node v ∈ V in a graph G = (A,X) is the G-invariant representation Γ(v,A,X), where Γ : V × Σn → Rd, d ≥ 1, such that ∀u ∈ V , Γ(u,A,X) = Γ(π(u), π(A), π(X)) for all permutation actions ∀π ∈ Πn. Moreover, for any two isomorphic nodes u, v ∈ V , Γ(u,A,X) = Γ(v,A,X). Definition 9 (Most-expressive structural node representations Γ?). A structural representation of a node v ∈ V , Γ?(v,A,X), is most-expressive iff, ∀u ∈ V , there exists a bijective measurable map between Γ?(u,A,X) and the orbit of node u in G = (A,X) (Definition 7).
Trivially, by Definitions 6 and 9, two graphs G1 = (A1,X1) and G2 = (A2,X2) are isomorphic (Definition 5) iff the most-expressive structural node representations (Γ?(u,A1,X1))u∈V and (Γ?(v,A2,X2))v∈V are the same up to a valid permutation π ∈ Πn of the nodes. In what follows P? is the power set excluding the empty set. We now describe the relationship between structural node representations and node isomorphism. Lemma 1. Two nodes v, u ∈ V , have the same most-expressive structural representations Γ?(v,A,X) = Γ?(u,A,X) iff u and v are isomorphic nodes in G = (A,X).
Having described representation of nodes, we now generalize these representations to subsets of V .
Definition 10 (Joint structural representation Γ). A joint structural representation of a graph with node set V is defined as Γ : P?(V )×Σn → Rd, d ≥ 1. Furthermore, Γ is G-invariant over all node subsets, i.e., ∀S ∈ P?(V ) and ∀(A,X) ∈ Σn, it must be that Γ(~S,A,X) = Γ(π(~S), π(A), π(X)) for all permutation actions ∀π ∈ Πn. Moreover, for any two isomorphic subsets S, S′ ∈ P?(V ), Γ(~S,A,X) = Γ(~S′,A,X).
We now mirror Definition 9 in our generalization of Γ:
Definition 11 (Most-expressive joint structural representations Γ?). A structural representation Γ?(~S,A,X) of a non-empty subset S ∈ P?(V ), of a graph (A,X) ∈ Σn, is most-expressive iff, there exists a bijective measurable map between Γ?(~U,A,X) and the orbit of U inG (Definition 7), ∀U ∈ P?(V ) and ∀(A,X) ∈ Σn.
Note, however, the failure to represent the link (lynx, coyote) in Figure 1 using the mostexpressive node representations of the lynx and the coyote. A link needs to be represented by a joint representation of two nodes. For instance, we can easily verify from Definition 11 that Γ?((lynx,coyote),A,X) 6= Γ?((orca,coyote),A,X), even though Γ?(lynx,A,X) = Γ?(orca,A,X).
Next we show that joint prediction tasks only require joint structural representations. But first we need to show that any causal model defined through axiomatic counterfactuals (Galles & Pearl, 1998) can be equivalently defined through noise outsourcing (Austin, 2008), a straightforward result that we were unable to find in the literature.
Lemma 2 (Causal modeling through noise outsourcing). Definition 1 of Galles & Pearl (1998) gives a causal model as a triplet M = 〈U, V ′, F 〉, where U is a set of exogenous variables, V ′ is a set of endogenous variables, and F is a set of functions, such that in the causal model, v′i = f(~pai, u) is the realization of random variable V ′ i ∈ V ′ and a sequence of random variables ~PAi with PAi ⊆ V \V ′i as the endogenous variable parents of variable V ′i as given by a directed acyclic graph. Then, there exists a pure random noise and a set of (measurable) functions {gu}u∈U such that for Vi ∈ V ′, V ′i can be equivalently defined as v′i a.s. = f(~pai, gu( u)), where u has joint distribution ( u)∀u∈U a.s. = g′( ) for some Borel measurable function g′ and a random variable ∼ Uniform(0, 1). The latter defines M via noise outsourcing (Austin, 2008).
The proof of Lemma 2 is given in the Appendix. Lemma 2 defines the causal model entirely via endogenous variables, deterministic functions, and a pure random noise random variable.
We are now ready for our theorem showing that joint prediction tasks only require (most-expressive) joint structural representations.
Theorem 1. Let S ⊆ P?(V ) be a set of non-empty subsets of the vertices V . Let Y (S,A,X) = (Y (~S,A,X))S∈S be a sequence of random variables defined over the sets S ∈ S of a graph G = (A,X), that are invariant to the ordering of ~S, S ∈ S, such that Y ( ~S1,A,X) d = Y ( ~S2,A,X) for any two jointly isomorphic subsets S1, S2 ∈ S (Definition 7), where d = means equality in their marginal distributions. Then, there exists a measurable function ϕ such that, Y (S,A,X) a.s.= (ϕ(Γ?(~S,A,X), S))S∈S , where S is the random noise that defines the exogenous variables of Lemma 2, with joint distribution p(( S′)∀S′∈S) independent of A and X .
Theorem 1 extends Theorem 12 of Bloem-Reddy & Teh (2019) in multiple ways: (a) to all subsets of nodes, S ∈ P?(V ), (b) to include causal language, and, most importantly, (c) to showing that any prediction task that can be defined over S, requires only a most-expressive joint structural representation over S. For instance, any task with |S| = 2 predicting a missing link (u, v) on a graph G = (A,X), requires only the most-expressive structural representation Γ?((u, v),A,X). Note that, in order to predict directed edges, we must use Γ?((u, v),A,X) to also predict the edge’s direction: →,←,↔, but a detailed procedure showing how to predict directed edges is relegated to a future journal version of this paper. Theorem 1 also includes node tasks for |S| = 1, hyperedge tasks for 2 < |S| < n, and graph-wide tasks for S = V .
Remark 1 (GNNs and link prediction). Even though structural node representations of GNNs are not able to predict edges, GNNs are often still optimized to predict edges (e.g., (Hamilton et al., 2017a; Xu et al., 2018)) in transfer learning tasks. This optimization objective guarantees that any small topological differences between two nearly-isomorphic nodes without an edge will be amplified, while differences between nodes with an edge will be minimized. Hence, the topological differences in a close-knit community will be minimized in the representation. This procedure is an interesting way to introduce homophily in structural representations and should work well for node classification tasks in homophilic networks (where node classes tend to be clustered).
We now turn our attention to node embeddings and their relationship with joint representations.

heading: 3.2 ON (POSITIONAL) NODE EMBEDDINGS
text: Definition 12 (Node Embeddings). The node embeddings of a graph G = (A,X) are defined as joint samples of random variables (Zi)i∈V |A,X ∼ p(·|A,X), Zi ∈ Rd, d ≥ 1, where p(·|A,X) is a G-equivariant probability distribution on A and X , that is, π(p(·|A,X)) = p(·|π(A), π(X)) for any permutation π ∈ Πn.
Essentially, Definition 12 says that the probability distribution p(Z|A,X) of a node embedding Z must be G-equivariant on A and X . This is the only property we require to define a node embedding. Next, we show that the node embeddings given by Definition 12 cover a wide range of embedding methods in the literature. Corollary 1. The node embeddings in Definition 12 encompass embeddings given by matrix and tensor factorization methods —such as Singular Value Decomposition (SVD), Non-negative Matrix Factorization (NMF), implicit matrix factorization (a.k.a. word2vec)–, latent embeddings given by Bayesian graph models —such as Probabilistic Matrix Factorizations (PMFs) and variants—, variational autoencoder methods and graph neural networks that use random lighthouses to extract node embedddings.
The proof of Corollary 1 is in the Appendix, along with the references of each of the methods mentioned in the corollary. The output of some of the methods described in Corollary 1 is deterministic, and for those, the probability density p(Z|A,X) is a Dirac delta. In practice, however, even deterministic methods use algorithms whose outputs depend on randomized initial conditions, which will also satisfy Corollary 1.
We now show that permutation equivariance implies two isomorphic nodes (or two subsets of nodes) must have the same marginal distributions over Z: Lemma 3. The permutation equivariance of p in Definition 12 implies that, if two proper subsets of nodes S1, S2 ∈ P?(V )\V are isomorphic, then their marginal node embedding distributions must be the same up to a permutation, i.e., p((Zi)i∈S1 |A,X) = π(p((Zj)j∈S2 |A,X)) for some appropriate permutation π ∈ Πn.
Hence, the critical difference between the structural node representation vector (Γ(v,A,X))v∈V in Definition 8 and node embeddings Z in Definition 12, is that the vector (Γ(v,A,X))v∈V must be G-equivariant while Z need not be —even though Z’s distribution must be G-equivariant. This seemly trivial difference has tremendous consequences, which we explore in the reminder of this section.
Next, we show that node embeddings Z cannot have any extra information about G that is not already contained in a most-expressive structural representation Γ?. Theorem 2 (The statistical equivalence between node embeddings and structural representations). Let Y (S,A,X) = (Y (~S,A,X))S∈S be as in Theorem 1. Consider a graph G = (A,X) ∈ Σn, n ≥ 2. Let Γ?(~S,A,X) be a most-expressive structural representation of nodes S ∈ P?(V ) in G. Then, Y (~S,A,X) ⊥⊥Γ?(~S,A,X) Z|A,X, ∀S ∈ S, for any node embedding matrix Z that satisfies Definition 12, where A ⊥⊥B C means A is independent ofC givenB. Finally, ∀(A,X) ∈ Σn, there exists a most-expressive node embedding Z?|A,X such that,
Γ?(~S,A,X) = EZ? [f (|S|)((Z?v )v∈S)|A,X], ∀S ∈ S,
for some appropriate collection of functions {f (k)(·)}k=1,...,n.
The proof of Theorem 2 is given in the Appendix. Note that the most-expressive embedding Z?|A,X extends the insight used to make GNNs more expressive in Murphy et al. (2019) to a more general procedure.
Theorem 2 implies that, for any graph prediction task, node embeddings carry no information beyond that of structural representations. A less attentive reader may think this creates an apparent paradox, since one cannot predict a property Y ((lynx,coyote),Afood web,Xfood web) in Figure 1 from structural node embeddings, since Γ(lynx,A,X) = Γ(orca,A,X). The resolution of the paradox is to note that Theorem 2 describes the prediction of a link through a pairwise structural representation Γ((lynx,coyote),Afood web,Xfood web), and we may not be able to do the same task with structural node representations alone. An interesting question for future work is how well can we learn distributions (representations) from (node embeddings) samples, extending (Kamath et al., 2015) to graph representations.
Other equally important consequences of Theorem 2 are: (a) any sampling approach obtaining node embeddings Z is valid as long as the distribution is G-equivariant (Definition 12), noting that isomorphic nodes must have the same marginal distributions (per Lemma 3). (b) Interestingly, convex optimization methods for matrix factorization can be seen as variance-reduction techniques with no intrinsic value beyond reducing variance. (c) Methods that give unique node embeddings —if the embedding of any two isomorphic nodes are different— are provably incorrect when used to predict graph relationships since they are permutation-sensitive. Remark 2 (Some GNN methods give node embeddings not structural representations). The random edges added by GraphSAGE (Hamilton et al., 2017a) and GIN (Xu et al., 2018) random walks make these methods node embeddings rather than structural node representations, according to Definition 12. To transform them back to structural node representations, one must average over all such random walks.
The following corollaries describe other consequences of Theorem 2: Corollary 2. The link prediction task between any two nodes u, v ∈ V depends only on the mostexpressive tuple representation Γ?((u, v),A,X). Moreover, Γ?((u, v),A,X) always exists for any graph (A,X) and nodes (u, v). Finally, given most-expressive node embeddings Z?, there exists a function f such that Γ?((u, v),A,X) = EZ? [f(Z?u,Z?v )], ∀u, v.
A generalization of Corollary 2 is also possible, where Theorem 2 is used to allow us to create joint representations from simpler node embedding sampling methods. Corollary 3. Sample Z according to Definition 12. Then, we can learn a k-node structural representation of a subset of k nodes S ∈ P?(V ), |S| = k, simply by learning a function f (k) whose average Γ(~S,A,X) = E[f (k)((Zv)v∈S)] can be used to predict Y (~S,A,X).
The proof of Corollary 3 is in the Appendix. Finally, we show that the concepts of transductive and inductive learning are unrelated to the notions of node embeddings and structural representations. Corollary 4. Transductive and inductive learning are unrelated to the concepts of node embeddings and structural representations.
Corollary 4 clears a confusion that, we believe, arises because traditional applications of node embeddings use a single Monte Carlo sample of Z|A,X to produce a structural representation (e.g., (Mikolov et al., 2013)). Inherently, a classifier learned with such a poor structural representation may fail to generalize over the test data, and will be deemed transductive. Corollary 5. Merging a node embeddings sampling scheme with GNNs can increase the structural representation power of GNNs.
Corollary 5 is a direct consequence of Theorem 2, with Murphy et al. (2019) showing RP-GNN as a concrete method to do so.

heading: 4 RESULTS
text: This section focuses on applying the lessons learned in Section 3 in four tasks, divided into two common goals. The goal of the first three tasks is to show that, as described in Theorem 2, node embeddings can be used to create expressive structural embeddings of nodes, tuples, and triads. These
representations are then subsequently used to make predictions on downstream tasks with varied node set sizes. The tasks also showcase the added value of using multiple node embeddings (Monte Carlo) samples to estimate structural representations, both during training and testing. Moreover, showcasing Theorem 1 and the inability of node representations to capture joint structural representations, these tasks show that structural node representations are useless in prediction tasks over more than one node, such as links and triads. The goal of fourth task is to showcase how multiple Monte Carlo samples of node embeddings are required to observe the fundamental relationship between structural representations and node embeddings predicted by Theorem 2.
An important note: Our proposed theoretical framework is not limited to the way we generate node embeddings. For example, our theoretical framework can use SVD in an inductive setting, where we train a classifier in one graph and test in a different graph, which was thought not possible previously with SVD. SVD with our theoretical framework is denoted MC-SVD, to emphasize the importance of Monte Carlo sampling in building better structural representations. Alternatively, more expressive node embeddings can be obtained using Colliding Graph Neural Networks (CGNN), as we show in the Appendix (Section 10 and Section 11)

heading: 4.1 QUANTITATIVE RESULTS
text: In what follows, we evaluate structural representations estimated from four node embedding techniques, namely GIN (Xu et al., 2018), RP-GIN (Murphy et al., 2019), 1-2-3 GNN (Morris et al., 2019), MC-SVD and CGNN. We classify GIN, RP-GIN and 1-2-3 GNN as node embedding techniques, as they employ the unsupervised learning procedure of Hamilton et al. (2017a). These were chosen because of their potential extra link and triad representation power over traditional structural representation GNNs. All node embedding methods are evaluated by their effect in estimating good structural representation for downstream task accuracy. We partition G = (A,X) into three non-overlapping induced subgraphs, namely Gtrain = (Atrain,Xtrain), Gval = (Aval,Xval) and Gtest = (Atest,Xtest), which we use for training, validation and testing, respectively. In learning all four node embedding techniques, we only make use of the graphs Gtrain and Gval. All the four models used here have never seen the test graph Gtest before test time —i.e., all our node embedding methods, used in the framework of Theorem 2, behave like inductive methods.
Monte Carlo joint representations during an unsupervised learning phase: A key component of our optimization is learning joint representations from node embeddings —as per Theorem 2. For this, at each gradient step (in practice, we do at each epoch), we perform a Monte Carlo sample of the node embeddings Z|A,X . This, procedure optimizes a proper upper bound on the empirical loss, if the loss is the negative log-likelihood, cross-entropy, or a square loss. The proof is trivial by Jensen’s inequality. For GIN, RP-GIN and 1-2-3 GNN, we add random edges to the graph following a random walk at each epoch (Hamilton et al., 2017a). For the MC-SVD procedure, we use the left eigenvector matrix obtained by: (1) a random seed, (2) a random input permutation of the adjacency matrix, and (3) a single optimization step, rather than running SVD until it converges. We also have results with MC-SVD†, which is the same procedure as before, but runs SVD until convergence —noting that the latter is likely to give deterministic results in large real-world graphs.
Monte Carlo joint representations during a supervised learning phase: During the supervised phase, we first estimate a structural joint representation Γ̂(~S,A,X) as the average ofm ∈ {1, 5, 20} Monte Carlo samples of a permutation-invariant function (Murphy et al., 2018; Zaheer et al., 2017) (sum-pooling followed by an MLP) applied to a sampled node embedding (Zv)v∈S |A,X . Then, using Γ̂(~S,A,X), we predict the corresponding target variable Y (S,A,X) of each task using an MLP. The node sets of our tasks S ⊆ V , have sizes |S| ∈ {1, 2, 3}, corresponding to node classification, link prediction, and triad prediction tasks, respectively.
Datasets: We consider four graph datasets used by Hamilton et al. (2017a), namely Cora, Citeseer, Pubmed (Namata et al., 2012; Sen et al., 2008) and PPI (Zitnik & Leskovec, 2017). Cora, Citeseer and Pubmed are citation networks, where vertices represent papers, edges represent citations, and vertex features are bag-of-words representation of the document text. The PPI (protein-protein interaction) dataset is a collection of multiple graphs representing the human tissue, where vertices represent proteins, edges represent interactions across them, and node features include genetic and immunological information. Train, validation and test splits are used as proposed by Yang et al. (2016) (see Table 3 in the Appendix). Further dataset details can be found in the Appendix.
Node classification task: This task predicts node classes for each of the four datasets. In this task, structural node representations are enough. The structural node representation is used to classify nodes into different classes using an MLP, whose weights are trained in a supervised manner using the same splits as described above. In Cora, Citeseer and Pubmed, each vertex belongs only to a single class, whereas in the PPI graph dataset, nodes could belong to multiple classes.
Link prediction task: Here, we predict a small fraction of edges and non-edges in the test graph, as well as identify all false edges and non-edges (which were introduced as a corruption of the original graph) between different pairs of nodes in the graph. Specifically, we use joint tuple representations Γ((u, v),A,X), for u, v ∈ V , as prescribed by Theorem 2. Since, datasets are sparse in nature, and a trivial ‘non-edges’ predictor would result in a very high accuracy, we balance the train and validation and test splits to contain an equal number of edges and non-edges.
Triad prediction task: This task involves the prediction of triadic interaction as well as identification of possible fake interactions in the data between the three nodes under consideration. In this case, we use joint triadic representations Γ((u, v, h),A,X), for u, v, h ∈ V , as prescribed by Theorem 2. Here, we ensure that edge corruptions are dependent. We treat the graphs as being undirected in accordance with previous literature, and predict the number of true (uncorrupted) edges between the three nodes. Again, to handle the sparse nature of the graphs, we use a balanced dataset for train, validation, and test.
In Table 1 we present Micro-F1 scores for all four models over the three tasks. First, we note how more Monte Carlo samples at test time tend to increase test accuracy. In node classification tasks, we note that structural node representations from CGNN node embeddings significantly outperform other methods in two of the three datasets (the harder tasks). In link prediction tasks, the low accuracy of GNN-based methods (close to random) showcases the little extra-power of GIN and RPGIN sampling schemes have over the the inability of structural node representations to predict links. Surprisingly, in triads predictions, the accuracy of GNN-based methods is much above random in some datasets, but still far from other node embedding methods. In link and triad prediction tasks, MC-SVD and CGNN share the lead with MC-SVD winning on Pubmed and PPI, and CGNN being significantly more accurate on Cora. Although, the 1-2-3 GNN is based on the two-WeisfeilerLehman (2-WL) algorithm (pairwise Weisfeiler-Lehman algorithm (Fürer, 2017)), which provides tuple representations that can be exploited towards link prediction, it is however an approximation primarily designed for graph classification tasks. Unfortunately, the 1-2-3 GNN performs quite poorly on all our tasks (node classification, link and triad prediction), indicating the need for a taskspecific approximation of 2-WL GNN’s. Results for Citeseer, in the Appendix, show similar results.

heading: 4.2 QUALITATIVE RESULTS
text: We now investigate the transformation of node embedding into node and link structural representations. Theorem 2 shows that the average of a function over node embedding Monte Carlo samples gives node and link embedding. In this experiment, we empirically test Theorem 2, by creating structural representations from the node embedding random matrix Z, defined as the left eigenvector matrix obtained through SVD (ran until convergence), with the sources of randomness being due to a random permutation of the adjacency matrix given as input to the SVD method and the random seed it uses. Consider m such embedding matrices Monte Carlo samples, Z(m) = {Z(i)}mi=1.
Structural node representations from node embeddings: According to Theorem 2, the average E[Zv,·|A] is a valid structural representation of node v ∈ V in the adjacency matrix A of Figure 1. To test this empirically, we consider the unbiased estimator µ̂(v,Z(m)) = 1m ∑m i=1 Z (i) v,· , v ∈ V , where limm→∞ µ̂(v,Z(m)) a.s. = E[Zv,·|A]. Figure 2a shows the Euclidean distance between the empirical structural representations µ̂(orca,Z(m)) and µ̂(lynx,Z(m)) as a function of m ∈ [1, 200]. As expected, because these two nodes are isomorphic, ‖µ̂(orca,Z(m))− µ̂(lynx,Z(m))‖ → 0 as m grows, with m = 100 giving reasonably accurate results.
Structural link representations from node embeddings: According to Theorem 2, the average E[f (2)(Zu,·,Zv,·)|A] of a function f (2) is a valid structural representation of a link with nodes u, v ∈ V in the adjacency matrix A of Figure 1. As an example, we use f (2)(a, b) = ‖a − b‖, and define the unbiased estimator µ̂(u, v,Z(m)) = 1m ∑m i=1 ‖Z (i) u − Z(i)v ‖,∀u, v ∈ V , where limm→∞ µ̂(u, v,Z(m)) a.s. = E[‖Zu,· − Zv,·‖|A]. Figure 2b shows the impact of increasing the number of Monte Carlo samples m over the empirical structural representation of links. We observe that although the empirical node representations of the orca and the lynx seem to converge to the same value, limm→∞ µ̂(orca,Z(m)) = limm→∞ µ̂(lynx,Z(m)), their empirical joint representations with the coyote converge to different values, limm→∞ µ̂(lynx, coyote,Z(m)) 6= limm→∞ µ̂(orca, coyote,Z(m)), as predicted by Theorem 2. Also note a similar (but weaker) trend for limm→∞ µ̂(orca, lynx,Z(m)) 6= limm→∞ µ̂(orca, coyote,Z(m)), showing these three tuples to be structurally different.

heading: 5 RELATED WORK
text: Node Embeddings vs Structural Representations: Prior works have categorized themselves as one of either node embedding methods or methods which learn structural representations. This artificial separation, consequently led to little contemplation of the relation between the two, restricting each of these approaches to a certain subsets of downstream tasks on graphs. Node embeddings were arguably first defined in 1904, through Spearman’s common factors. Ever since, there has never been a universal definition of node embedding: node embeddings were simply the product of a particular method. This literature features a myriad of methods, e.g., matrix factorization (Belkin & Niyogi, 2002; Cao et al., 2015; Ahmed et al., 2013; Ou et al., 2016), implicit matrix factorization (Mikolov et al., 2013; Arora et al., 2009; Chen et al., 2012; Perozzi et al., 2014; Grover & Leskovec, 2016), Bayesian factor models (Mnih & Salakhutdinov, 2008; Gopalan et al., 2014a), and some types of neural networks (You et al., 2019; Liang et al., 2018; Tang et al., 2019; Grover et al., 2019).
Arguably, the most common interpretation of node embeddings borrows from definitions of graph (node) embeddings in metric spaces: a measure of relative node closeness (Abraham et al., 2006; Bourgain, 1985; Candès & Recht, 2009; Graham & Winkler, 1985; Kleinberg, 2007; Linial et al., 1995; Rabinovich & Raz, 1998; Recht et al., 2010; Shaw et al., 2011). Even in non-metric methods, such as word2vec (Mikolov et al., 2013) and Glove (Pennington et al., 2014), the embeddings have properties similar to those of metric spaces (Nematzadeh et al., 2017). Note that the definition of close varies from method to method, i.e., it is model-dependent. Still, this interpretation of closeness is the reason why their downstream tasks are often link prediction and clustering. However, once the literature started defining relative node closeness with respect to structural neighborhood similarities (e.g., Henderson et al. (2012); Ribeiro et al. (2017); Donnat et al. (2018)), node embeddings and structural representations became more strangely entangled.
Structural representations have an increasing body of literature focused on node and whole-graph classification tasks. Theoretically, these works abandon metric spaces in favor of a group-theoretic
description of graphs (Bloem-Reddy & Teh, 2019; Chen et al., 2019; Kondor & Trivedi, 2018; Maron et al., 2019; Murphy et al., 2019), with connections to finite exchangeability and prior work on multilayer perceptrons (Wood & Shawe-Taylor, 1996). Graph neural networks (GNNs) (e.g., (Duvenaud et al., 2015; Gilmer et al., 2017; Kipf & Welling, 2016a; Hamilton et al., 2017a; Xu et al., 2018; Scarselli et al., 2008) among others) exploit this approach in tasks such as node and wholegraph classification. Morris et al. (2019) proposes a higher-order Weisfeller-Lehman GNN (WL-kGNN), which is shown to get better accuracy in graph classification tasks than traditional (WL-1) GNNs. Unfortunately, Morris et al. (2019) focused only on graph-wide tasks, missing the fact that WL-2 GNN should be able to also perform link prediction tasks (Theorem 1), unlike WL-1 GNNs. More recently, graph neural networks have also been employed towards relational reasoning as well as matrix completion tasks (Schlichtkrull et al., 2018; Zhang & Chen, 2018; Battaglia et al., 2018; Berg et al., 2017; Monti et al., 2017). However, these GNN’s, in general, learn node embeddings rather than structural node representations, which are then exploited towards link prediction. GNNlike architectures have been used to simulate dynamic programming algorithms (Xu et al., 2019), which is unrelated to graphs and outside the scope of this work.
To the best of our knowledge, our work is the first to provide the theoretical foundations connecting node embeddings and structural representations. A few recent works have classified node embedding and graph representation methods arguing them to be fundamentally different (e.g., Hamilton et al. (2017b); Rossi et al. (2019); Wu et al. (2019); Zhou et al. (2018)). Rather, our work shows that these are actually equivalent for downstream classification tasks, with the difference being that one is a Monte Carlo method (embedding) and the other one is deterministic (representation).
Inductive vs Transductive Approaches: Another common misconception our work uncovers, is that of qualifying node embedding methods as transductive learning and graph representation ones as inductive (e.g., Hamilton et al. (2017a); Yang et al. (2016)). In their original definitions, transductive learning (Gammerman et al., 1998), (Zhu et al., 2003), (Zhou et al., 2004) and inductive learning (Michalski, 1983), (Belkin et al., 2006) are only to be distinguished on the basis of generalizability of the learned model to unobserved instances. However, this has commonly been misinterpreted as node embeddings methods being transductive and structural representations being inductive. Models which depend solely only on the input feature vectors and the immediate neighborhood structure have been classified as inductive, whereas methods which rely on positional node embeddings to classify relationships in a graph have been incorrectly qualified as transductive.
The confusion seems to be rooted in researchers trying to use a single sample of a node embedding method and failing to generalize. Corollary 4 resolves this confusion by showing that transductive and inductive learning are fundamentally unrelated to positional node embeddings and graph representations. Both node embeddings and structural representations can be inductive if they can detect interesting conceptual patterns or reveal structure in the data. The theory provided by our work strongly adheres to this definition. Our work additionally provides the theoretical foundation behind the performance gains seen by Epasto & Perozzi (2019) and Goyal et al. (2019), which employ an ensemble of node embeddings for node classification tasks.

heading: 6 CONCLUSIONS
text: This work provided an invaluable unifying theoretical framework for node embeddings and structural graph representations, bridging methods like SVD and graph neural networks. Using invariant theory, we have shown (both theoretically and empirically) that relationship between structural representations and node embeddings is analogous to that of a distribution and its samples. We proved that all tasks that can be performed by node embeddings can also be performed by structural representations and vice-versa. Our empirical results show that node embeddings can be successfully used as inductive learning methods using our framework, and that non-GNN node embedding methods can be significantly more accurate in most tasks than simple GNNs methods. Our work introduced new practical guidelines to the use of node embeddings, which we expect will replace today’s naı̈ve direct use of node embeddings in graph tasks.

heading: ACKNOWLEDGMENTS
text: This work was sponsored in part by the ARO, under the U.S. Army Research Laboratory contract number W911NF-09-2-0053, the Purdue Integrative Data Science Initiative and the Purdue Research foundation, the DOD through SERC under contract number HQ0034-13-D-0004 RT # 206, and the National Science Foundation under contract number CCF-1918483.

heading: 7 A VISUAL INTERPRETATION OF NODE EMBEDDINGS AND STRUCTURAL REPRESENTATIONS
text: In what follows we showcase the difference between structural representations (Figure 3) and positional node embeddings (Figure 4) obtained by graph neural networks and SVD, respectively, on the same graph. The graph is the food web of Figure 1 and consists of two disconnected subgraphs.
Figure 3 shows a 2-dimensional (R2) structural representation of nodes obtained by a standard GNN (obtained by the 1-WL GNN of Xu et al. (2018)), optimized to try to predict links without the addition of any random edges). Node colors represent the mapping of the learned structural representation in R2 into the red and blue interval of RGB space [0, 255]2. Note that isomorphic nodes are forcibly mapped into the same structural representations (have the same color), even though the representation is trained to predict links. Specifically, the lynx and the orca in Figure 3 get the same color since they are isomorphic, while the lynx and the coyote have different structural representations (different colors). The lynx, like the orca, is a top predator in the food web while the coyote is not a top predator. Hence, it is quite evident why GNN’s are not traditionally used for link prediction: as the structural node representation is a color, using these representations is akin to asking “is a light pink node in Figure 3 connected to a light blue node?” We cannot answer this question unless we also specify which light pink (i.e. coyote or seal) and which light blue (i.e. orca or lynx) we are talking about. Hence, the failure to predict links. Our Corollary 2 shows that joint 2-node structural representations are required for link prediction. Our Theorem 1 generalizes it to joint k-node structural representations for any k-node joint prediction task.
Positional node embeddings, on the other hand, are often seen as a lower-dimensional projection of the rows and columns of the adjacency matrix A from Rn to Rd, d < n, that preserves relative positions of the nodes in a graph. In Figure 4 we show the same food web graph, where now node colors map the values of the two leading (SVD) eigenvectors (of the undirected food web graph) into the [0, 255] interval of blue and red intensity of RGB colors, respectively. The graph is made undirected, otherwise the left and right eigenvectors will be different and harder to represent visually. SVD is used here as a representative of positional node embedding methods. Note the lynx and the coyote now have close positional node embeddings (represented by colors which are closer in the color spectrum), while the positional node embeddings of the lynx and the orca are significantly different. Node embeddings are often seen as encoding the fact that the lynx and the coyote are part of a tightly-knit community, while the lynx and orca belong to distinct communities.
It is evident from Figure 4 why positional node embeddings are not traditionally used to predict node classes: predicting that the lynx, like the orca, is a top predator based on their node colors is
difficult, since the coyote’s color is very similar to that of the lynx, while the orca obtains a completely different color to the lynx. Relying on color shades (light and dark) for node classification is unreliable, since nodes with completely different structural positions in the food chain may have similar color shades. Our Theorem 2 shows, however, that any positional node embedding (actually, any node embedding) must be a sample of a distribution given by the most-expressive structural representation of the node. That is, if SVD is ran again over different permutations of the vertices in the adjacency matrix (an isomorphic graph to Figure 1), the set of colors obtained by the lynx and the orca must be the same. Hence, node classification is possible if we look at the distribution of colors that a node obtains from random permutations of the adjacency matrix.
On the other hand, link prediction using the colors in Figure 4 is rather trivial, since similar colors mean “closeness” in the graph. For instance, we may easily predict that the baleen whale also eats zooplankton.

heading: 8 PRELIMINARIES
text: Noise outsourcing, representation learning, and graph representations: The description of our proofs starts with the equivalence between probability models of graphs and graph representations. We start with the concept of noise outsourcing (Austin, 2008, Lemma 3.1) applied to our task —a weaker version of the more general concept of transfer (Kallenberg, 2006, Theorem 6.10) in pushforward measures.
A probability law Z|(A,X) ∼ p(·|(A,X)), (A,X) ∈ Σn, can be described (Kallenberg, 2006, Theorem 6.10) by pure random noise ∼ Uniform(0, 1) independent of (A,X), passing through a deterministic function Z = f((A,X), ) —where f : Σn× [0, 1]→ Ω, where Ω in our task will be a matrix Ω = Rn×d defining node representations, d ≥ 1. That is, the randomness in the conditional p(z|(A,X)) is entirely outsourced to , as f is deterministic. Now, consider replacing the graph G = (A,X) by a G-equivariant representation Γ(A,X) of its nodes, the output of a neural network Γ : Σn → Rn×m, m ≥ 1, that gives an representation to each node inG. If a representation Γ?(A,X) is such that ∃f ′ where Z = f(A,X, ) = f ′(Γ?(A,X), ), ∀(A,X) ∈ Σn and ∀ ∈ [0, 1], then Γ?(A,X) does not lose any information when it comes to predicting Z. Statistically (Kallenberg, 2006, Proposition 6.13), Z ⊥⊥Γ?(A,X) (A,X). We call Γ?(A,X) a most-expressive representation of G with respect to Z. A most-expressive representation (without qualifications) is one that is most-expressive for any target variable.
Representation learning is powerful precisely because it can learn functions Γ that are compact and can encode most of the information available on the input. And because the most-expressive Γ? is G-equivariant, it also guarantees that any G-equivariant function over Γ? that outputs Z is also G-equivariant, without loss of information.

heading: 9 PROOF OF THEOREMS, LEMMAS AND COROLLARIES
text: We restate and prove Lemma 1 Lemma 1. Two nodes v, u ∈ V , have the same most-expressive structural representation Γ?(v,A,X) = Γ?(u,A,X) iff u and v are isomorphic nodes in G = (A,X) (Definition 6).
Proof. In this proof, we consider both directions.
(⇒) Consider two nodes v, u ∈ V which satisfy the condition, Γ?(v,A,X) = Γ?(u,A,X) but are not isomorphic in G = (A,X). By contradiction, suppose u and v have different node orbits. This is a contradiction, since the bijective mapping of Definition 9 would have to take the same input and map them to different outputs.
(⇐) By contradiction, consider the two nodes u, v ∈ V which are isomorphic in G = (A,X) but with different most expressive structural representations i.e. Γ?(v,A,X) 6= Γ?(u,A,X). This is a contradiction, because as per Definition 6 two nodes should have the same structural representation, which would imply the most expressive structural representation is not a structural representation. Hence, the two nodes should share the same most expressive structural representation.
Next, we restate and prove Lemma 2
Lemma 2 (Causal modeling through noise outsourcing). Definition 1 of Galles & Pearl (1998) gives a causal model as a triplet M = 〈U, V, F 〉, where U is a set of exogenous variables, V is a set of endogenous variables, and F is a set of functions, such that in the causal model, vi = f(~pai, u) is the realization of random variable Vi ∈ V and a sequence of random variables ~PAi with PAi ⊆ V \Vi as the endogenous variable parents of variable Vi as given by a directed acyclic graph. Then, there exists a pure random noise and a set of (measurable) functions {gu}u∈U such that for Vi ∈ V , Vi can be equivalently defined as vi a.s. = f(~pai, gu( u)), where u has joint distribution ( u)∀u∈U a.s. = g′( ) for some Borel measurable function g′ and a random variable ∼ Uniform(0, 1). The latter defines M via noise outsourcing (Austin, 2008).
Proof. By Definition 1 of Galles & Pearl (1998), the set of exogenous variables U are not affected by the set of endogeneous variables V . The noise outsourcing lemma (Lemma 3.1) of Austin (2008) (or its more complete version Theorem 6.10 of Kallenberg (2006)) shows that any samples of a joint distribution over a set of random variables U can be described as (u)∀u∈U a.s. = g( ), for some Borel measurable function g and a random variable ∼ Uniform(0, 1). As the composition of two Borel measurable functions is also Borel measurable, it is trivial to show that there exists Borel measurable functions {gu}u∈U and g′, such that u a.s. = gu( u) and ( u)∀u∈U a.s. = g′( ). The latter is trivial since gu can just be the identity function, gu(x) = x.
Next, we restate and prove Lemma 3 Lemma 3. The permutation equivariance of p in Definition 12 implies that, if two proper subsets of nodes S1, S2 ( V are isomorphic, then their marginal node embedding distributions must be the same up to a permutation, i.e., p((Zi)i∈S1 |A,X) = π(p((Zj)j∈S2 |A,X)) for some appropriate permutation π.
Proof. From Definition 12, it is trivial to observe that two isomorphic nodes u, v ∈ V in graph G = (A,X) have the same marginal node embedding distributions. In this proof we extend this to node sets S ⊂ V where |S| > 1. We marginalize over (Zi)i 6∈S1 to obtain p((Zi)i∈S1 |A,X) and in the other case over (Zi)i6∈S2 to obtain p((Zi)i∈S2 |A,X) respectively.
We consider 2 cases as follows:
Case 1: S1 = S2: This is the trivial where S1 and S2 are the exact same nodes, hence their marginal distributions are the identical as well by definition.
Case 2: S1 6= S2: Since S1 and S2 are also given to be isomorphic, it is clear to see that every node in S1 has an isomorphic equivalent in S2. In a graph G = (A,X), the above statement conveys that S2 can be written as a permutation π on S1, i.e S2 = π(S1). Now, employing Definition 12, it is clear to see that p((Zi)i∈S1 |A,X) = π(p((Zj)j∈S2 |A,X))
Next, we restate and prove Theorem 1
Theorem 1. Let S ⊆ P(V ) be a set of subsets of V . Let Y (S,A,X) = (Y (~S,A,X))S∈S be a sequence of random variables defined over the sets S ∈ S of a graph G = (A,X), such that we define Y (~S,A,X) := Y~S |A,X and Y (~S1,A,X) d = Y (~S2,A,X) for any two jointly isomorphic subsets S1, S2 ∈ S in (A,X) (Definition 7), where d = means equality in their marginal distributions. Then, there exists a deterministic function ϕ such that, Y (S,A,X) a.s.= (ϕ(Γ?(~S,A,X), S))S∈S , where S is a pure source of random noise from a joint distribution p(( S′)∀S′∈S) independent of A and X .
Proof. The case S = V is given in Theorem 12 of Bloem-Reddy & Teh (2019). The case S = ∅ is trivial. The case S ( V , S 6= ∅, is described as follows with a constructive proof. First consider the case of two isomorphic sets of nodes S1, S2 ∈ S. As by definition Y (~S1,A,X)
d = Y (~S2,A,X), we must assume p(Y~S1 |A,X) = p(Y~S2 |A,X). We can
now use the transfer theorem (Kallenberg, 2006, Theorem 6.10) to obtain a joint description Y~S1 |A,X a.s. = φ1(~S1,A,X, ) and Y~S2 |A,X a.s. = φ2(~S2,A,X, ), where is a common source of independent noise. As S1 and S2 are joint isomorphic (Definition 7), there exists an isomorphism S1 = iso(~S2), where φ1(iso(~S2),A,X, ) = φ1(~S1,A,X, ). Because the distribution given by φ1(·, ) must be isomorphic-invariant in (A,X) and S1 and S2 are also isomorphic in (A,X) then, for all permutation actions π ∈ Πn, there exists a new isomorphism iso′ such that φ1(π(iso(~S2)), π(A), π(X), ) d = φ1(iso′(π(~S1)), π(A), π(X), ), which allows us to create a function ϕ′ that incorporates iso′ into φ1. Due to the isomorphism between S1 and S2, we can do the same process for S2 to arrive at the same function ϕ′. We can now apply Corollary 6.11 (Kallenberg, 2006) over (Y~S1 |A,X, Y~S2 |A,X) along with a measure-preserving mapping f to show that Y~S1 |A,X a.s. = ϕ′(~S1,A,X, 1) and Y~S2 |A,X a.s. = ϕ′(~S2,A,X, 2), where ( 1, 2) = f( ). If S1 and S2 are not joint isomorphic, we can simply define ϕ′(Si, ·) := φi(Si, ·). Definition 11 allows us to define a function ϕ from which we rewrite ϕ′(~Si,A,X, i) as ϕ(Γ?(~Si,A,X), i). Applying the same procedure to all S ∈ S concludes our proof.
Next, we restate and prove Theorem 2 Theorem 2 (The statistical equivalence between node embeddings and structural representations). Let Y (S,A,X) = (Y (~S,A,X))S∈S be as in Theorem 1. Consider a graph G = (A,X) ∈ Σn. Let Γ?(~S,A,X) be a most-expressive structural representation of nodes S ∈ S in (A,X). Then,
Y (~S,A,X) ⊥⊥Γ?(~S,A,X) Z|A,X, ∀S ∈ S,
for any node embedding matrix Z that satisfies Definition 12, where A ⊥⊥B C means A is independent ofC givenB. Finally, ∀(A,X) ∈ Σn, there exists a most-expressive node embedding Z?|A,X such that, Γ?(~S,A,X) = EZ? [f (|S|)((Z?v )v∈S)|A,X], ∀S ∈ S, for some appropriate collection of functions {f (k)(·)}k=1,...,n.
Proof. In the first part of the proof, for any embedding distribution p(Z|A,X), we note that by Theorem 1, y(~S,A,X) a.s.= f ′(Γ?(~S,A,X), S). Hence, Y (~S,A,X) ⊥⊥Γ?(~S,A,X) Z|A,X, ∀S ∈ S, is a direct consequence of Proposition 6.13 in (Kallenberg, 2006).
In the second part of the proof, we construct an orbit over a most-expressive representation of a graph (A,X) of size n, with permutations that act only on unique node ids (node orderings) added as node features: Π′(A,X) = {((Γ?(v,A, [X, π(1, . . . , n)T ]))∀v∈V }∀π∈Πn , where [A, b] concatenates column vector b as a column of matrix A. Define Z?|A,X as the random variable with a uniform measure over the set Π′(A,X). We first prove that Z?|A,X is a most-expressive node embedding. Clearly, Z?|A,X is a node embedding, since the uniform measure over Π′(A,X) is G-equivariant. All that is left to show is that we can construct Γ? of any-size subset S ∈ S from Z?|A,X via Γ?(~S,A,X) = EZ? [f (|S|)((Z?v )v∈S)|A,X], for some function f (|S|). This part of the proof has a constructive argument and comes in two parts.
Assume S ∈ S has no other joint isomorphic set of nodes in S, i.e., @S2 ∈ S such that S and S2 are joint isomorphic in (A,X). For any such subset of nodes S ∈ S, and any element Rπ ∈ Π′(A,X), there is a bijective measurable map between the nodes in S and their positions in the representation vector Rπ = (Γ?(v,A, [X, π(1, . . . , n)T ]))∀v∈V , since all node features are unique and there are no isomorphic nodes under such conditions. Consider the multiset
OS(A,X) := {(Γ?(v,A, [X, π(1, . . . , n)T ]))∀v∈S}∀π∈Πn of the representations restricted to the set S. We now show that there exists an surjection between OS(A,X) and Γ?(~S,A,X). There is a surjection if for all S1, S2 ∈ P?(V ) that are non-isomorphic, it implies OS1(A,X) 6= OS2(A,X). The condition is trivial if |S1| 6= |S2| as |OS1(A,X)| 6= |OS2(A,X)|. If |S1| = |S2|, we prove by contradiction. Assume OS1(A,X) = OS2(A,X). Because of the unique feature ids and because Γ? is most-expressive, the representation Γ?(v,A, [X, π(1, . . . , n)T ]) of node v ∈ V and permutation π ∈ Πn is unique. As S1 is not isomorphic to S2, and both sets have the same size, there must be at least one node u ∈ S1 that has no isomorphic equivalent in S2. Hence, there exists π ∈ Πn that gives a unique representation Γ?(u,A, [X, π(1, . . . , n)T ]) that does not have a matching Γ?(v,A, [X, π(1, . . . , n)T ]) for any v ∈ S2 and π′ ∈ Πn. Therefore, ∃a ∈ OS1(A,X), where a 6∈ OS2(A,X), which is a contradiction since we assumed OS1(A,X) = OS2(A,X). Now that we know there is such a surjection, a possible surjective measurable map between OS(A,X) and Γ?(~S,A,X) is a multiset function that takes OS(A,X) and outputs Γ?(~S,A,X). For finite multisets whose elements are real numbers R, Wagstaff et al. (2019) shows that a mostexpressive multiset function can be defined as the average of a function f (|S|) over the multiset. The elements ofOS(A,X) are finite ordered sequences (ordered according to the permutation) and, thus, can be uniquely (bijectively) mapped to the real line with a measurable map, even when A and X have edge and node attributes defined over the real numbers R. Thus, by Wagstaff et al. (2019), there exists some surjective function f (|S|) whose average over OS(A,X) give Γ?(~S,A,X). Now assume S1, S2 ⊆ V are joint isomorphic in (A,X), S1, S2 6= ∅. Then, we have concluded that OS1(A,X) = OS2(A,X). Fortunately, by Definition 10, this non-uniqueness is a required property of the structural representations of Γ?(S1,A,X) and Γ?(S2,A,X), which must satisfy Γ?(S1,A,X) = Γ?(S2,A,X) if S1 and S2 are joint isomorphic, which concludes our proof.
Next, we restate and prove Corollary 1 Corollary 1. The node embeddings in Definition 12 encompass embeddings given by matrix and tensor factorization methods —such as Singular Value Decomposition (SVD), Non-negative Matrix Factorization (NMF), implicit matrix factorization (a.k.a. word2vec)–, latent embeddings given by Bayesian graph models —such as Probabilistic Matrix Factorizations (PMFs) and variants—, variational autoencoder methods and graph neural networks that use random lighthouses to extract node embedddings.
Proof. In Probabilistic Matrix Factorization (Mnih & Salakhutdinov, 2008), we have Auv ∼ N (ZTu Zv, σ2aI) where Zu ∼ N (0, σ2I), Zv ∼ N (0, σ2I). We note that the posterior of P (Z|A) is clearly equivariant, satisfying definition 12, as a permutation action on the nodes requires the same permutation on the σ2I matrix as well to obtain Z. The proof for Poisson Matrix Factorization (Gopalan et al., 2014a;b) follows a similar construction to the above, wherein the Normal assumption is replaced by the Poisson distribution.
Moreover, any matrix factorization algorithm gives an equivariant distribution of embeddings if the input matrices are randomly permuted upon input. Specifically, any Singular Value Decomposition (SVD) method satisfies Definition 12 as the distribution of the eigenvector solutions to degenerate singular values —which are invariant to unitary rotations in the corresponding degenerate eigenspace— will trivially be G-equivariant even if the algorithm itself outputs values dependent on the node ids. Same is true for non-negative matrix factorization (Lee & Seung, 2001) and implicit matrix factorization (Levy & Goldberg, 2014; Mikolov et al., 2013).
PGNN’s (You et al., 2019) compute the shortest distances between every node of the graph with a predetermined set of ‘anchor’ nodes to encode a distance metric. By definition, using such a distance metric would make the node embeddings learned by this technique G-equivariant. The shortest path between all pairs of nodes in a graph can be seen equivalently as a function of a polynomial in Ak. Alternatively, this can also be represented using the adjacency matrix and computed using the FloydWarshall algorithm (Cormen et al., 2009). The shortest distance is thus a function of A ignoring the node features X . Since the inputs to the GNN comprises of the distance metric, A and X , the node embeddings Z can equivalently seen as a function of A, X and noise. The noise in this case is characterized by the randomized anchor set selection.
In variational auto-encoder models such as CVAE’s, GVAE’s, Graphite (Tang et al., 2019; Kipf & Welling, 2016b; Grover et al., 2019) the latent representations Z are learned either via a mean field approximation or are sampled independently of each other i.e. Z ∼ P (·|A,X). We note that in the case of the mean field approximation, the probability distribution is a Dirac Delta. It is clear to see that the Z learned in this case is G-equivariant with respect to any permutation action of the nodes in the graph.
Next, we restate and prove Corollary 2 Corollary 2. The link prediction task between any two nodes u, v ∈ V depends only on the mostexpressive tuple representation Γ?((u, v),A,X). Moreover, Γ?((u, v),A,X) always exists for any graph (A,X) and nodes (u, v). Finally, given most-expressive node embeddings Z?, there exists a function f such that Γ?((u, v),A,X) = EZ? [f(Z?u,Z?v )], ∀u, v.
Proof. It is a consequence of Corollary 3 with |S| = 2.
Next, we restate and prove Corollary 3 Corollary 3. Sample Z according to Definition 12. Then, we can learn a k-node structural representation of a subset of k nodes S ⊆ V , |S| = k, simply by learning a function f (k) whose average Γ(~S,A,X) = E[f (k)((Zv)v∈S)] can be used to accurately predict Y (~S,A,X).
Proof. This proof is a direct application of Theorem 2 which shows the statistical equivalence between node embeddings and strucutral representations.
Note that f (k)((Zv)v∈S) can equivalently be represented as f (k)(ϕ(Γ(v,A,X)v∈S , S)) using Theorem 2 and that the noise S is marginalized from the noise distribution of Theorem 1, still preserving equivariance. With an assumption of the most powerful f ′(k), which is able to capture dependencies within the node set (Murphy et al., 2018) and noise S , we can replace the above with f ′(k)(ϕ(Γ(S,A,X), S)) and subsequently compute an expectation over this function to eliminate the noise.
Next, we restate and prove Corollary 4 Corollary 4. Transductive and inductive learning are unrelated to the concepts of node embeddings and structural representations.
Proof. By Theorem 2, we can build most-expressive any-size joint representations from node embeddings, and we can get node embeddings from any-size most-expressive joint representations.
Hence, given enough computational resources, node embeddings and graph representations can have the same generalization performance over any tasks. This shows they are unrelated with the concepts of transductive and inductive learning.
Next, we restate and prove Corollary 5 Corollary 5. A node embeddings sampling scheme can increase the structural representation power of GNNs.
Proof. The proof follows as a direct consequence of Theorem 2, along with Murphy et al. (2019) which demonstrates RP-GNN as a concrete method to do so. More specifically, appending unique node ids to node features uniformly at random, makes the nodes unique, and can be seen as a strategy to obtain node embeddings which satisfy Definition 12 using GNN’s. By averaging over multiple such node embeddings gives us structural representations more powerful than that of standalone GNN’s.

heading: 10 COLLIDING GRAPH NEURAL NETWORKS (CGNNS)
text: In this section we propose a new variational auto-encoder procedure to obtain node embeddings using neural networks, denoted Colliding Graph Neural Networks (CGNNs). Our sole reason to propose a new auto-encoder method is because we want to test the expressiveness of node embedding auto-encoders —and, unfortunately, existing auto-encoders, such as Grover et al. (2019), do not properly account for the dependencies introduced by the colliding variables in the graphical model. In our experiments, shown later, we aggregate multiple node embedding sampled from CGNN to obtain structural representations of the corresponding nodes and node sets.
Node Embedding Auto-encoder. In CGNN’s, we adopt a latent variable approach to learn node embeddings. Corresponding to each evidence feature vector Xi,· ∈ Rk ∀ i ∈ V , we introduce a latent variable Zi,· ∈ Rk. In addition, our graphical model also consists of observed variables Ai,j,· ∈ Rd ∀ i, j ∈ V . These are related through the joint distribution p(A,X|Z) =∏ i,j∈V×V p(Ai,j,·|Zi,·,Zj,·) ∏ h∈V p(Xh,·|Zh,·), which is summarized by the Bayesian network in Figure 5 in the Appendix. Note that Ai,j,· is a collider, since it is observed and influenced by two hidden variables, Zi,·,Zj,·. A neural network is used to learn the joint probability via MCMC, in an unsupervised fashion. The model learns the parameters of the MCMC transition kernel via an unrolled Gibbs Sampler, a templated recurrent model (an MLP with shared weights across Gibbs sampling steps), partially inspired by Fan & Huang (2017).
The unrolled Gibbs Sampler, starts with a normal distribution of the latent variables Z(0)i,· , ∀i ∈ V, with each Z(0)i,· ∼ N (0, I) independently, where I is the identity matrix. Subsequently at time steps t = 1, 2, . . ., in accordance with the graphical model, each variable Z(t)i,· is sequentially sampled from its true distribution conditioned on all observed edges of its corresponding node i, in addition to the most-up-to-date latent variables Z’s associated with its immediate neighbors. The reparametrization trick (Kingma & Welling, 2013) allows us to backpropogate through the unrolled Gibbs Sampler. Algorithm 1 in the Appendix details our method. Consequently, this procedure has an effect on the run-time of this technique, which we alleviate by performing Parallel Gibbs Sampling by constructing parallel splashes (Gonzalez et al., 2011). Our unsupervised objective is reconstructing the noisy adjacency matrix.

heading: 11 CGNN ALGORITHMS
text: The procedure to generate node embeddings used by the CGNN is given by Algorithm 1. Structural representations are computed as an unbiased estimate of the expected value of a function of the node embedding samples as given by Algorithm 2 via a set of sets function (Meng et al., 2019).
input : A, X , num-times output: Z initialization: Zu ∼ N (0, 1) ∀ u ∈ V while num-times > 0 do
for u ∈ V do ∀v ∈ V such that Auv = 1 hidden← f({Zv}); // f is a permutation invariant function visible← g({Xv}); // g is a permutation invariant function Zu ←MLP (hidden, visible, Xu) + Noise // With Reparametrization Trick // Equivalently, Zu ∼ P (·|{Zv}, {Xv}, {Auv}, Xu) end num-times← num-times - 1
end Algorithm 1: Node Embeddings from the Unrolled Gibbs Sampler

heading: 12 FURTHER RESULTS
text: In Table 2 we provide the results on node classification, link prediction and triad prediction on the Citeseer dataset.

heading: 13 DESCRIPTION OF DATASETS AND EXPERIMENTAL SETUP
text: A detailed description of the datasets and the splits are given in Table 3. Our implementation is in PyTorch using Python 3.6. The implementations for GIN and RP-GIN are done using the PyTorch Geometric Framework. We used two convolutional layers for GIN, RP-GIN since it had the best performance in our tasks (we had tested with 2/3/4/5 convolutional layers). Also since we perform tasks based on node representations rather than graph representations, we ignore the graph wide readout. For GIN and RP-GIN, the embedding dimension was set to 256 at both convolutional layers. All MLPS, across all models have 256 neurons. Optimization is performed with the Adam Optimizer (Kingma & Ba, 2014). For the GIN, RP-GIN the learning rate was tuned in {0.01, 0.001, 0.0001, 0.00001} whereas for CGNN’s the learning rate was set to 0.001. Training was performed on Titan V GPU’s. For more details refer to the code provided.
input : {Z(i)}mi=1, k ;// node embedding samples, node set size output: g({Z}S); S = {S1}∀S1⊂V :|S1|=k //structural representations, S is a set of sets initialization: g({Z}S) = {~0} for i ∈ [1,m] do
for S ∈ S do g({Zu}u∈S)← g({Zu}u∈S) + 1mf({Z (i) u }u∈S) // f is a permutation invariant function
end end
Algorithm 2: Structural Representations from the Node Embedding Samples

Review summaries:
This paper tries to clarify some confounding concepts around graph/node representation learning by providing a unifying theoretical framework based on invariant theory. The authors define node embedding and structural graph representation based on a minimal number of requirements, which is, in turn, used to derive some useful properties and unify two seemly different concepts. Based on these, a new graph neural network framework is proposed. The experiments on multiple tasks with multiple datasets validate the main claim that a single node embedding is insufficient to capture the structural representation of a graph.