On the Equivalence between Positional Node Embeddings and Structural Graph Representations
Authors: Balasubramaniam Srinivasan
Bruno Ribeiro
Venue:  (2020)
Keywords: Graph Neural Networks
Structural Graph Representations
Node Embeddings
Relational Learning
Invariant Theory
Theory
Deep Learning
Representational Power
Graph Isomorphism

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 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 further augments standard operating procedures used today.

Published as a conference paper at ICLR 2020
ON THE EQUIVALENCE BETWEEN POSITIONAL NODE EMBEDDINGS AND STRUCTURAL GRAPH REPRESEN- TATIONS
Balasubramaniam Srinivasan Department of Computer Science Purdue University bsrini veniiveuuuueeeee
Bruno Ribeiro
Department of Computer Science
Purdue University
ribe i roêcs purdue.
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 anal- ogous to that of distribution and its samples. We prove that all tasks that performed by node embeddings can also be performed by structural represen- tations and vere-versa. We also show that the concept of transductive and induc- tive learning is unrelated to node embeddings and graph representations, clearing another source of confusion in the literature. Finally, we introduce practi- cal guidelines to generating and using node embeddings, which fixes significant shortcomings of standard operating procedures used today.
INTRODUCTION
The theory of structural graph representations a recently emerging field. It creates a link between relational learning and invariant theory. Interestingly, or rather unfortunately, there is unified theory connecting node embeddings low-rank matrix approximations, factor analysis, latent se- mantic 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 struc- tural 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 al.) 2016]] Mikolov et al. 2013). Hence, can all (positional) node embeddings provide structural relationships akin to word analogies? We provide visual example Appendix (Section luiinn the food web of Figure I In the opposite direction, structural representations - node embeddings, graph neural networks (GNNs) are often optimized to predict edges even though their structural node represen- tations are provably incapable of performing the task. For instance, the node representations of the lynx and the orca in Figure [ are indistinguishable due to an isomorphic equivalence between the nodes, making any edge prediction task that distinguishes the edges of lynx and orea seemly futile exercise (see Appendix (Section [ for more details). Hence, are structural representations in gen- caariiculr--unddameenn
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 77 for concrete visual interpretation of the differences between positional node embeddings and structural representations over node classification and link prediction tasks).
GNNs
Confirmation bias has seemingly appeared to thwart recent efforts to bring node embeddings and structural representations into single overarching framework. Preconceived notions of the two being fundamentally different (see (Appendix (Section ?7) have been reinforced in the existing lit- erature, arguing they belong in different applications: (Positional) Node embeddings would find applications in multi-ary relationships such link prediction, clustering, and natural language pro- cessing 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-pole 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

---

Published as a conference paper at ICLR 2020
Coul
Droa
Weiie Sprace
Snowdhoo Play
Km
Dhige
Fied
Daleen Whale
Figure A food web example showing two disconnected components the borcal forest (Stenseth et al. 1997) and the antarctic fauna (Bates et al. 2015). The positional node embedding of the lynx and the orca can be different while their structural representation must be the same (due to the isomorphism).
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 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
2
PRELIMINARIES
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-Reedye & 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 altributed graph, denoted by G (V, E, E), where V is a set of matrix X E Raxk le > and 3-mode tensor E R "xnnk K > representing the node and edge features, respectively. The edge set has an associated adjacency matrix A E {0, 13nxn. In order to simplify notation. will compress E and A into a single tensor A R= +1), When explicit vertex and edge features and weights are unavailable, we will consider X = 11T and A = A, where 1 is a 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 Š and vector of the elements in E (V) sorted ascending order, where (V) is the power set of V without the empty set.
|V| verfices, E is the set of edges in V x V, with
vector of ones. We will abuse notation and denote the graph as G (A,
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 e.g., (Z,) and outputs an equivalent vector, matrix, or tensor with the order of the nodes permuted. We define II, as the set of all n! such permutation actions.
Definition 3 (Orbits). An orbit is the result of a group action 1I, acting on elements of a group cor- respond 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 I1, i.e., II, = [T(x))
E II,}.
Definition 4 (G-equivariant and G-invariant functions). Let En, be the set of all possible attributed graphs G of size n 2 1. More formally, En is the set of all tuples (A, X) with adjacency tensors A and corresponding node attributes X for n nodes. A function g Σn - Raxx- G-equivariant w.E.t. valid permutations of the nodes V, whenever any permutation action π E II, in the Σn space associated with the same permutation action of the nodes in the Rax: space. A functionn g E, + R is G-invariant whenever it is invariant to any permutation action π E II, in E.,.
Definition 5 (Graph orbits & graph isomorphism). Let G (A,X) be a graph with n nodes, and les (G) ((A', (x) (A', X') (A()), TX))) VT E [m)) be the set of all equivalent (isomorphic) graphs under the permutation action т. Two graphs G1 = =A,,,,) and G2 = (Ag, X2) are said isomorphic iff (G,) (G2).
Definition 6 (Node orbits & node isomorphism). The equivalence classes of the vertices of a graph G under the action of automorphisms are called veriex orbits. If two nodes are in the same node orbit, we say that they are isomorphic.
In Figure I the lynx and the orca are isomorphic (they have the same node orbits). We now gener- alize Definition 6 to subsets of nodes E PV*V), where P*(V) is the power set of V without the empty set.
2

---

Published as a conference paper at ICLR 2020
Definition 7 (Vertex subset orbits and joint isomorphism). The equivalence classes of k-sized sub- sets of vertices S E (V) of a graph under the action of automorphisms between the subsets called vertex subset orbits, k 2 2. If two proper subsets S2 (VVV are in the same vertex subset orbit, we say they are jointly isomorphic.
Next define the relationship between structural representations and node embeddings.
A UNIFYING THEORETICAL FRAMEWORK OF NODE EMBEDDINGS AND STRUCTURAL REPRESENTATIONS
How are node embeddings and structural representations related? This section starts with a famil- iar, albeit naive, view of the differences between node embeddings and structural representations, preparing the groundwork to later broadening and rectifying these into precise model-free mathe- matical statements using invariant theory. This broadening is needed since model-free node embed- dings need not be related to node closeness in the graph (or to lower dimensional projections for that matter), it is impossible have a model-free definition of closeness.
A familiar interpretation of node embeddings: Node embeddings are often seen as a lower- dimensional projection of the rows and columns of the adjacency matrix A from R" to R. d n, that preserves relative positions of the nodes in a graph (Graham & Winkler 1985 Linial et al.) [995]; for instance, in Figure [ 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 tightly-knit community, while the lynx and orca belong to distinct communities. The structural representation of 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 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 top predator.
The incompatibiliity of the familiar interpretation with the theory of structural graph representa- tions: The above interpretation of node embeddings must be tied to 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, introduce 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 projection into lower dimensional space).
3.1 ON STRUCTURAL REPRESENTATIONS
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 E V in graph G = (A, X) is the G iinvariant representation I'u, A, X), where I V x En + R d 2 1, such that Vu E V, T(u,A, X) = ((m(n), क (A), ) X for all permulation actions Vn I, Moreover, for any two isomorphic nodes u. E V, I(u, A, X) = =T(u, =(,,A, A)
Definition 9 (Most-expressive structural node representations r*). structural representation of node E V, (" A, X), is most-expressive iff. Vu E V, there exists a bijective measurable map between D (", A, X) and the orbit of node in G (A,X) (Definition) 7.
Trivially, by Definitions 6 and two graphs G = (A,))) and G2 = (A2,X2) are isomor- phic (Definition 5 iff the most-expressive structural node representations (T* AI, X, Xi))vev and (T*(v, Av, Xe)vev are the same up to valid permutation æ E II, of the nodes. In what follows p* is the power excluding the empty set.
We now describe the relationship between structural node representations and node isomorphism. Lemma 1. Two nodes v, E V, have the same most-expressive structural representations (* A, X) = (", iff and are isomorphic nodes in G = XA.
Having described representation of nodes, now generalize these representations subsets of V.
3

---

Published as a conference paper at ICLR 2020
Definition 10 (Joint structural representation I). A joint structural representation of graph with node set V is defined as I (P*(V) x Σn +R d 22 1. Furthermore, I is G inivariant over all node subsets, i.e., VS E (V) and ( X) E Ew it must be that I'(Š, A, X) = ['(T(S), π (A) T (X)) for all permutation actions VT E I.. Moreover, for any two isomorphic subsets S, S E PV))), I(S, A, x) = A,
We now mirror Definition Iin our generalization of
Definition 11 (Most-cxpressive joint structural representations 1* A structural representation
T* X) of a non-emn non-empty subset S E (V),,, of a graph (A, X) E Em, is most- most-expressive iff there exists a bijective measurable map between I (TŪ A, X) and the orbit of in G (Definition YU E PV) and V(A, X) E E...
Note, however, the failure to represent the link (lyxx, coyote) in Figure | using the most- expressive node representations of the lynx and the coyote. A link needs to be represented by joint representation of two nodes. For instance, we can easily verify from Defini- tion 11 that I ((((yx,..ooyot) A, X) f I* ((orc.cooyol) A, X), even though ('ymuxx, A, X) T* (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), straightforward result that we were unable to find in the literature.
Lemma (Causal modeling through noise outsourcing). Definition I oflles & Pearl (998) gives causal model as triplet
M = (U)
where U a set of exogenous variables, V a set of endogenous variables, and F is set of func- tions, such that in the causal model, vf [Mū u) is the realization of random variable V E V and sequence of random variables PA, with PA; C VVV as the endogenous variable parents of variable V as given by directed acyelic graph. Then, there exists a pure random noise e and a set of (measurable) functions {gubwet such that for V V', Vi can be equivalently defined as vi " f 9u(cu)), where cu has joins distribution (cu)vaEU g'(c) for some Borel mea- surable function g' and 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 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 C (V) be of non-empty subsets of the vertices V. Let Y A,)
(S, A, X)) 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 E S, such that Y(i,, A, X) 1 Y(S2, A, X) for any two jointly isomorphic subsets S2, S2 S (Definition 7. where á means equality in their marginal distributions. Then, there exists a measurable function ip such that, Y(S, A, X) az (s A. ()),s)))sss) where eg the random noise that defines the exogenous variables of Lemma with joint distribution p((es) Jysres) independent of A and X.
Theorem I extends Theorem 12 of Reodm & Teh 2019) in multiple ways: (a) to all sub- sets of nodes, E (V))), (b) to include causal language, and, most importantly, (c) to showing that any prediction task that can be defined over S, requires only 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 I' [(u v), A, X). Note that, in order to predict directed edges, we must use I ((u, v). A, X) to also predict the edge's direction: +, t, ++, but a detailed procedure showing how to predict directed edges is relegated to a future journal version of this paper. Theorem [ also includes node tasks for |S] = 1, hyperedge tasks for 2 < |S| < n, and graph-wide tasks for S V.
4

---

Published as a conference paper at ICLR 2020
Remark (GNNss 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 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.
3.2 ON (POSITIONAL) NODE EMBEDDINGS
Definition 12 (Node Embeddings). The node embeddings of a graph G = (A, are defined as
joint samples of random variables (Zi) A, X ~ A( X), Zi Rd d 2 1, where p(-1A X) is a G-equivariant probability distribution on and X, that is, π (p( A, X)) = P(-IT(()))) (A), π (X)
for any permatation क E II..
Essentially, Definition 12 says that the probability distribution pl AZ), X) of a node embedding Z must be G-equivariant on 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 wide range of embedding methods in the literature.
Corollary 1. The node embeddings in Desimition T2 encompuss embeddings given by matrix and tensor factorization methods- suchh 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 P Probabilistic Matrix Factorizations (PMFs) and variants-, vvari- ational autoencoder methods and graph neural networks that use random lighthouses to extract node embedddings.
The proof of Corollary is in the Appendix, along with the references of each of the methods men- tioned in the corollary. The output of some of the methods described in Corollary is deterministic, and for those, the probability density p( Z A, X) is Dirac delta. In practice, however, even deter- ministic methods use algorithms whose outputs depend on randomized initial conditions, which will also satisfy Corollary
We now show that permutation cquivariance implies two isomorphic nodes (or two subsets of nodes) must have the same marginal distributions over Z:
Lemma 3. The permutation equivariance of in Definition 12 implies that, if two proper subsets of nodes St, S2 E (VVV) are isomorphic, then their marginal node embedding distributions must be the same up to a permutation, i.e., p(()))ss X) = Tpp((Z))jes A, X)) for some appropriate permutation æ E II,,.
Hence, the critical difference between the structural node representation vector (T(v, X)) in Definition & and node embeddings Z in Definition 12] is that the vector (T(v, A, eevvv must be G-equivariant while Z need not be even though Zss distribution must be G-equivariant. This seemly trivial difference has tremendous consequences, which we explore in the reminder this section.
Next, we show that node embeddings cannot have any extra information about that is not already contained in most-cxpressive structural representation 1**
Theorem 2 (The statistical equivalence between node embeddings and structural representations), Let YSS, A. X) = (Y(5, (((S,A X)) be as in Theorem Consider a graph G = XA En, 2. Let T (S,A,X) X) be most-expressive structural representation of nodes S (V) in G. Then,
A(Š,A, X) -I. ZIA, X.
VS S,
for any node embedding matrix Z that satisfies Definition 12 where A 11 C means A is indepen- dent of C given B. Finally. v(A. X) E En, there exists a expressve node embedding Z* A X such that,
I ($ A, X Ez. (1 ((15)((()) ((Z)) ves))))s))) X), AS S,
5

---

Published as a conference paper at ICLR 2020
for some appropriate collection of functions (f
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. (0119) to more general procedure.
Theorem 2 implies for any graph prediction task, node embeddings carry information be- yond that of structural representations. A less attentive reader may think this creates an apparent paradox, since one cannot predict property Y (((Iyx,cooyoe) Afood web: Food web) in Figure from structural node embeddings, since [Iynx, A, X) = [(rca, A, X). The resolution the paradox is to note that Theorem describes the prediction of link through pairwise structural representation ((4ynx,,coyote) food web: food weh). 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 learn dis- tributions (representations) from (node embeddings) samples, extending (Kamath et al., 2015) to graph representations.
Other equally important consequences of Theorem are: (a) any sampling approach obtaining node embeddings Z is valid long as the distribution is G-equivariant (Definition 12 noting that iso- morphic nodes must have the same marginal distributions (per Lemma 3). (b) Interestingly, convex optimization methods for matrix factorization can be seen as puriance-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 predict graph relationships since they are
sensiiiive...
Remark 2 (Some GNN methods give node embeddings not structural representations), The random edges added by GraphSAGE (Hamilton el al.) (2017a) and GIN (Xu el al. (2088) random walks make these methods node embeddings rather than structural node representations, according to Definition [2] To transform them back structural node representations, 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, E V depends only on the most- expressive tuple representation [* v). A, X). Moreover, [" v), A, X) always exists for any graph (A, X) and rodes (u, v)). Finully, given most-expressive node embeddings Z", there exists function f such that ((u, v), X) = Ez [f ]3)], Vu,v. U.
generalization of Corollary is also possible, where Theorem iis used to allow us to create joint representations from simpler node embedding sampling methods.
Corollary 3. Sample Z according Definition [2 Then, we can learn k-node structural rep- resentation of a subset of k nodes S E (V),)), |ST= k, simply by learning function f(() whose average T(Š A, X) = (() ((Zo)oEs) can be used to predict Y(Š, A,).
The proof of Corollary is in the Appendix. Finally, we show that the concepts of transductive and inductive learning 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 clears confusion that, we believe, arises because traditional applications of node em- beddings 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 direct consequence of Theorem 2 with Murphy et al. (2019) showing RP-GNN as
concrete method to do so.
RESULTS
This section focuses applying the lessons leamndd 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 em- beddings can be used to create expressive structural embeddings of nodes, tuples, and triads. These

---

Published as a conference paper at ICLR 2020
representations are then subsequently used to make predictions 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 [ and the inability of node representations to capture joint structural repre- sentations, 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 multi- ple Monte Carlo samples of node embeddings are required 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 one graph and test 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 1ip
4.1 QUANTITATIVE RESULTS
In what follows, we evaluate structural representations estimated from four node embedding tech- niques, 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 tech- niques, 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 es- timating good structural representation for downstream task accuracy, We partition G (A. X into three non-overlapping induced subgraphs, namely Girain (Arain uumin), Gval = (Aval, X and Gies = (Arest: X.ea). which we use for training, validation and testing, respectively. In learning all four node embedding techniques, we only make use of the graphs Guain and Gval. All the four models used here have never seen the test graph Grest before test time -ie.. 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 proper upper bound loss, if the loss is the negative log- 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 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: (I) 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.
the empirical
Monte Carlo joint representations during a supervised learning phase: During the supervised phase, we first estimate a structural joint representation i(Š. X) as the average of m E {1. 5, 20) Monte Carlo samples of a permutation- invariian function (Murphy al. 2018 Zaheer et al. 2017) Ssum-pooling followed by an MLP) applied to a sampled node embedding (Z.)ves) A, X. Then, using f(š, 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 C V, have sizes [S] E (1, corresponding to node classifi- cation, link prediction, and triad prediction tasks, respectively.
Datasets: We consider four graph datasets used by Hamilton et al. (2117)). namely Cora, Citeseer, Pubmed (Namata et al. 2012] Sen et al., (008) 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-protedl in- teraction) 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.
7

---

Published as a conference paper at ICLR 2020
Table I: Micro Fl score on three distinct tasks averaged over runs with standard deviation in parenthesis. The number within the parenthesis beside the model name indicates the number of Monte Carlo samples used in the estimation of the structural representation. MC-SVD (1) denotes the SVD procedure run until convergence with one Monte Carlo sample for the representation. Bold values show maximum empirical average, and multiple bolds happen when its standard deviation overlaps with another average. Results for Citeseer are provided the Appendix in Table 2
Node Claseflcation
Link Prediction
Triad Prediction
Cora
Pubmed
PPI
Cura
Pobmed
PPI
Cora
Pubmed
PP1
Randowe
0.143
D.733
0,5121
0.500
0,500
0,500
0,250
0,250
0,250
GINCT
0.87810L086)
0
(E
0.2500000000
GIN(S)
06676000051
0.88010.003)
0.535/0.000
0.51R00028)
0.00910012)
0.284/0.017)
0.422(0024)
0.39720.004)
GIN200
067840.024
0.800)00002)
0.53600.00
(005
0 0.14000006
0.512/0.047)
0.28160.110)
444220
0.8990.004)
KFEGIN(T
0.879000012)
0.33400.0055
0.285000155
RP-GIN(S)
0.61100022)
0.881
0.534K0000 (34)
0.89
0.63700038)
0.02
0.28550.022 (.25)
0.429/0.0044
0.39900.009)
RP-GIN(20)
0.755000052)
0.879)0.005)
0.5350.0033
0. 0.518(0017)
0.619000832)
066010.0077
0.270X0.01 00XX00011 1)
0.418/0.011
0. 0.395/0.005)
(
0.41200055)
0.200000100
1-2-3 GNN(5)
0.521(0.008)
(.355(00655)
0.40500000)
0 0.50100.018)
0.50
0,50100.003
0.285(0.015)
0 (208)
0.251:0.005)
2NN
0.3244.0010)
0,46200
0.0000.007
0,4990.007)
0.5000.0088
0.11 0.265(0.014)
0.25400.085)
MC SVD
(
0810000009)
0.52X0.0055)
(.00000224)
0.755000100
0.33600:035)
0.13100171
0.352000100
MC-SVDLL
0.667(00017)
0.82510.007)
0.583 0.521(0.005)
0.815/0.032)
0.755(0.008)
0.30KC0.034)
0.5 0.518/0.065)
..92000006)
MC-VVD())
0.60900013)
0.4220.015
0.52200019) 0.5500.0009
0.845(0.033)
0.754(0.086)
0.30K0.037)
0.567:0.061)
0.544/0.005)
MC-SVD22)
085
(900000009
0. 0.58
(.86)))119)
0.762(0.010)
0. 50006-033)
0. 0.546(0.029)
0.550/0.007)
OGNND
(1
CGNNES)
0.637000114 000
0.70710.027)
070000012) 0.585(0057)
0.41700003) 0.4140.0455
0.63000266
CONNOI)
0.726.0024)
(..100
0.707(0.11))
0.712(0.01)
0.581(0.039)
0.73((0001)
0.40500034)
0.41900117)
0.490/00221
Node classification task: This task predicts node classes for each of the four datasets. In this task, structural node representations 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 single class, whereas in the PPI graph dataset, nodes could belong to multiple classes.
Link prediction lask: Here, we predict 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 I((u, v), A, X). for u, e E 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 E V, as prescribed by Theorem ? 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 T we present Micro-Fl 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, 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 -oNN-hased methods (close to random) showcases the little extra-power of GIN and RP- GIN 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 wimning on Pubmed and PPI, and CGNN being significantly more accurate on Cora. Although, the 1-2-3 GNN is based on the two- -vo-Weisfeiler- Lehman (2WWL) algorithm (pairwise Weisfeiler-Lehman algorithm (Fü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 task- specific approximation of 2- GNN's. Results for Citeseer, in the Appendix, show similar results.
4.2 QUALITATIVE RESULTS
We now investigate the transformation of node embedding into node and link structural representa- tions. Theorem 2 shows that the average of function over node embedding Monte Carlo samples gives node and Tink embedding. In this experiment, we empirically test Theorem 2 by creating structural representations from the node embedding random matrix Z. defined as the left eigenvec- tor matrix obtained through SVD (ran until convergence), with the sources of randomness being due to 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, g(m) (2() )
8

---

Published as a conference paper at ICLR 2020
2.0
(lam g01) 4.
0r00 coyoto
jitt
0.5
orcu-lynx
cyno-
0.0
Number Monto Garoo Bamples
Number Monte Carlo Samples
(a) Difference in avg. structural node representations.
(b) Average structural link representations
Figure 2: Structural Representations for nodes and links using multiple samples obtained using MC-SVD on the disconnected food web graph shown in Figure
Structural node representations from node embeddings: According Theorem
2 the average
Ei A] is valid structural representation of node e E V in the adjacency matrix A of Figure To test this empirically, we consider the unbiased estimator iu(v, 2(m) 1 E
E V.
m
where limm -+ jiv,, 2(m) -_.. E eZ A]. Figure 2a shows the Euclidean distance between the empirical structural representations ji(orc, ((m) and p(lynx, ((m)) as function of m E [1, 200). As expected, because these two nodes are isomorphic, []ā(orca, Z(m) ((llnxx Z Z(m) - 0 m grows, with m = 100 giving reasonably accurate results.
Structural link representations from node embeddings: According to Theorem 2 the average (( Zu.., Ze,) A] of a function f(2) is valid structural representation of link with nodes u E V in the adjacency matrix A of Figure [ As example, we use ((2) (a, b) = ||a bll, and define the unbiased estimator A(u, 0, Z (mm) 1 E [| 2 [1, Vu, E V. where limm-+so ju(u, U, (m)) 0_ Zil. Zu.|IIA], 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 con- verge to the same value, limm-+oo p(orca, ()) limm- p(lynx, (m)), their empirical joint representations with the coyote converge to different values, limm-+x f(lynx, coyote, Z(m) + litm- ji(orca, coyote, 2(m)), predicted by Theorem 2 for limm-+co (orca, lynx, Z(m)) of limm-+00 ji(oraa, coyote, ((m)), showing these three tuples to be structurally different.
Also note similar (but weaker) trend
5 RELATED WORK
Node Embeddings Structural Representations: Prior works have categorized themselves 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 SSpearman ss 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 myriad of methods, e.g., matrix factorization (Belkin & Niyogi 2002 Cao et al., 2015: Ahmed et al. [013 Ou et al., 2016), implicit matrix factorization (Mikolov al. 2013 Arora al. |209 Chen al. 2012 2 Perozzi et al. [0144] Grover & Leskoved) 2016). Bayesian factor models (Mnih & Salakhutdinov 2008, Gopalan et al. 2014a)), and some types of neural networks (You et al. [019 Liang et al. [018 Tang et al. 2019 Grover al. 2019)
Arguably, the most common interpretation of node embeddings borrows from definitions of graph (node) embeddings in metric spaces: measure of relative node closeness (Abraham et al. 2006
Bourgain 1985; Candès & Recht| 2009 Graham & Winkler
1985
Kleinberg [207]] Linial et al., Even non non-metric methods,
1995 Rabinovii Raz 1998 Recht al. 2010: [hha et al. 2011
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., (217)) Note that the definition of close varies from method to method, i.c., is modell-eepnndent. 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); b) structural representations became more strangely entangled.
Donnat et al. (2018), ), node embeddings and
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

---

Published as a conference paper at ICLR 2020
description of graphs (Bloem- Blodm-Reddy 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- Shawe-Taylor 1996). Graph neural networks (GNNs) (c.g., (Duvenaud et al. 2015 Gilmer et al. Kipf & Welling 2016a Hamilton et al. 2017a Xu et al.) 2018 2018|Scarsellli et al. (008) among others) exploit this approach in tasks such node and whole- graph classification. Morris et al. (2019) proposes a higher-order Weisteller-Lehman GNN (WL-k- GNN), 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 also perform link prediction tasks (Theorem (T]. 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. GNN- like 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, work is the first 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); WWu 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.. Hamiltonooo et al. (2017a); Yang et al. (2016)) In their original definitions, transductive learning (Gammerman et al. 1998). (Zhu et al., 2003). (Zhou et al. (004) and inductive learning [Michalski] (Belkin et 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 graph have been incorrectly qualified as transductive.
The confusion seems to be rooted in researchers trying to use a single sample of 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 repre- sentations. 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 this definition. Our work additionally provides the theoretical foundation behind the performance gains seen by EEpsto & Perozzi (2019) and Goyal et al. (219)) which employ an ensemble of node embeddings for node classification tasks.
6 CONCLUSIONS
This work provided an invaluable unifying theoretical framework for node embeddings and struc- tural graph representations, bridging methods like SVD and graph neural networks. Using invariant theory, we have shown (both theoretically and empirically) that relationship between structural rep- resentations 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 repre- sentations 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 's naïve direct use of node embeddings in graph tasks.
ACKNOWLEDGMENTS
This work was sponsored in part by the ARO, under the U.S. Army Research Laboratory contract number
the Purdue Integrative Data Science Initiative and the Purdue Research foundation, the DOD through SERC under contract number 1000034-13---000 RT # 206, and the National Science Foundation under contract number 191-88.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Ittai Abraham, Yair Bartal, and Ofer Neimany. Advances in metric embedding theory. In Proceed- ings of the ehihty- annual ACM symposium on Theory of computing, pp. 271-286 ACM, 2006.
Amr Ahmed, Nino Shervashidze, Shravan Narayanamurthy, Vanja Josifovski, and Alexander Smola. Distributed large-scale natural graph factorization. In Proceedings of the 22nd inter- national conference on World Wide Web, pp. 37-48. ACM, 2013.
Sanjeev Arora, Satish Rao, and Umesh Vazirani. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM (JACM), 56(2):5, 2009,
Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, and Andrej Risteski. A latent variable model approach to pmi-based word embeddings. Transactions of the Association for Computational Linguistics, 4:385-399 2016.
Tim Austin. On exchangeable random variables and the statistics of large graphs and hypergraphs. Probability Surveys, 145, 2008.
Michael L Bates, Susan M Bengtson Nash, Darryl W Hawker, John Norbury, Jonny S Stark, and Roger Cropp. Construction of trophically complex near-shore antarctic food web model using the conservative normal framework with structural coexistence. Journal of Marine Systems, 145: 1-14, 2015.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Lanchez-Gonzales Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv: 180.00//6,, 2018.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in neural information processing systems, pp. 585-591, 2002.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. Journal of machine learning research, 7 (Nov):2399 2434, 2006.
Rianne van den Berg, Thomas N Kipf, and Max Welling. Graph convolutional matrix completion. arXiv preprint arXiv: (tt1::/700002666 2017.
Benjamin Bloem-Redde and Yee Whye Teh. Probabilistic symmetry and invariant neural networks. arXiv preprint 1:X1::9901000022 2019.
Jean Bourgain. On lipschitz embedding of finite metric spaces in hilbert space. Israel Journal of Mathematics, 52(1-2):46-52, 1985.
Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foun- dations of Computational mathematics, 966):11, 2009.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. In Proceedings of the 24th ACM international on conference on informa- tion and knowledge management, pp. 891-900. ACM, 2015.
Shuo Chen, Josh L Moore, Douglas Turnbull, and Thorsten Joachims. Playlist prediction via metric embedding. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 714-722. ACM, 2012.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. NerulPS, 2019.
Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009.
11

---

Published as a conference paper at ICLR 2020
Claire Donnat, Marinka Zitnik, David Hallac, and Jure Leskovec. Learning structural node embed- dings via diffusion wavelets. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1320-13200 1329. ACM, 2018.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks graphs for learning molecular fingerprints. In Advances neural information processing systems, pp. 2224-2232, 2015.
Alessandro Epasto and Bryan Perozzi. Is a single embedding enough? learning node representations that capture multiple social contexts. In The World Wide Web Conference, pp. 4944404. ACM, 2019.
Shuangfei Fan and Bert Huang. arXiv: 2017.
Recurrent collective classification.
arXiv preprint
Martin Fürer. On the combinatorial power of the weisfeiler-lehman algorithm. In International Conference on Algorithms and Complexity, pp. 260-271, Springer, 2017.
David Galles and Judea Pearl. An axiomatic characterization of causal counterfactuals, Foundations of Science, 3(1):151-182, 1998.
Alexander Gammerman, Volodya Vovk, and Vladimir Vapnik. Learning by transduction. In Pro- ceedings of the Fourteenth conference on Uncertainty in artificial intelligence, pp. 148-155, Mor- gan Kaufmann Publishers Inc., 1998.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning- Learning-Volume 70, pp. 1263-1272. JMLR. org, 2017.
Joseph Gonzalez, Yucheng Low, Arthur Gretton, and Carlos Guestrin. Parallel gibbs sampling: From colored fields to thin junction trees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 324-332, 2011.
Prem Gopalan, Francisco Ruiz, Rajesh Ranganath, and David Blei. Bayesian nonparametric pois- son factorization for recommendation systems. In Artificial Intelligence and Statistics, pp. 275- 283, 2014a.
Prem K Gopalan, Laurent Charlin, and David Blei. Content-based recommendations with poisson factorization. In Advances in Neural Information Processing Systems, pp. 3176-3184, 2014b.
Palash Goyal, Di Huang, Sujit Rokka Chhetri, Arquimedes Canedo, Jaya Shree, and Evan Patterson.
Graph representation ensemble learning. arXiy preprint arXiv:1909 1, 2019.
Ronald L Graham and Peter M Winkler. On isometric embeddings of graphs. Transactions of the American mathematical Society, 288(2):527-538 1985.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDI international conference Knowledge discovery and data mining, pp. 855-864. ACM, 2016.
Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs ICML, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs.
In Advances Neural Information Processing Systems, pp. 1024-1034, 2017a
William L. Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. arXiv preprint arXiv:/709.05558 2017b.
Keith Henderson, Brian Gallagher, Tina Mitaassi-Rad, Hanghang Tong, Sugato Basu, Leman Akoglu, Danai Koutra, Christos Faloutsos, and Lei Li. Rolx: structural role extraction & mining in large graphs. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge dis- covery and data mining, pp. 1231-1239. ACM, 2012.
12

---

Published as a conference paper at ICLR 2020
Olav Kallenberg. Foundations of modern probability. Springer Science & Business Media, 2006.
Sudeep Kamath, Alon Orlitsky, Dheeraj Pichapati, and Ananda Theertha Suresh. On learning dis- tributions from their samples. In Conference on Learning Theory, pp. 1066-1100, 2015.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114, 2013.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1609.029777 2016a.
Thomas N Kipf and Max Welling.
Variational
graph auto-encoders.
arXiv
preprint
1,000330, 2016b.
Robert Kleinberg, Geographic routing using hyperbolic space. In IEEE INFOCOM 2007-26th IEEE International Conference on Computer Communications, pp. 1902-1909. IEEE, 2007.
Risi Kondor and Shubhendu Trivedi. On the generalization of equivariance and convolution neural networks the action of compact groups. ICML, 2018.
Daniel D Lee and Sebastian Seung. Algorithms for non-negative matrix factorization. In Advances in neural information processing systems, pp. 556-562, 2001.
Omer Levy and Yoav Goldberg. Neural word embedding implicit matrix factorization. In Ad- vances neural information processing systems, pp. 2177-2185, 2014.
Dawen Liang, Rahul G Krishman, Matthew D Hoffman, and Tony Jebara. Variational autoencoders for collaborative filtering. In Proceedings of the 2018 World Wide Web Conference, pp. 689-6999699999 International World Wide Web Conferences Steering Committee, 2018.
Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algo- rithmic applications. Combinatorica, 15(2):215 245, 1995.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. JCML, 2019.
Changping Meng, Jiasen Yang, Bruno Ribeiro, and Jennifer Neville. Hats: A hierarchical sequence- attention framework for inductive set-of-sets embeddings. In KDD, 2019.
Ryszard S Michalski. A theory and methodology of inductive learning. In Machine learning, pp. 83-134. Springer, 1983.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed represen- tations words and phrases and their compositionality. In Advances neural information pro- cessing systems, pp. 11111119,, 2013.
Andriy Mnih and Ruslan R Salakhutdinov. Probabilistic matrix factorization. In Advances in neural information processing systems, pp. 1257-1264, 2008.
Federico Monti, Michael Bronstein, and Xavier Bresson. Geometric matrix completion with recur- rent multi-grapp neural networks. In Advances in Neural Information Processing Systems, pp- 2697-3707,2011
Christopher Morris, Martin Ritzert, Matthis Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602-4609, 2019.
Ryan L Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Janossy pool- ing: Learning deep permutation-invaiiae functions for variable-size inputs. arXiv preprint arXiv: 1811:181 2018.
13

---

Published as a conference paper at ICLR 2020
Ryan L Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. arXiv preprint arXiv:1903.02544 2019.
Galileo Namata, Ben London, Lise Getoor, Bert Huang, and UMD EDU. Query-driven active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, pp. 8, 2012.
Aida Nematzadeh, Stephan C Meylan, and Thomas L. Griffiths. Evaluating vector-space models of word representation, or, the unreasonable effectiveness of counting words near other words. In CogSci, 2017.
Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity preserv- ing graph embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1105-1114. ACM, 2016.
Jeffrey Pennington, Richard Socher, and Christopher Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pp. 1532-1543, 2014.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 701-710. ACM, 2014.
Yuri Rabinovich and Ran Raz. Lower bounds on the distortion of embedding finite metric spaces in graphs. Discrete & Computational Geometry, 19(1):79-94 1998.
Benjamin Recht, Maryam Fazel, and Pablo Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):471-501 2010.
Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. struc2vec: Learning node representations from structural identity. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 395-394. ACM, 2017.
Ryan A Rossi, Di Jin, Sungchul Kim, Nesreen Ahmed, Danai Koutra, and John Boaz Lee. From community to role-based graph embeddings. arXiv preprint arXiv: 2019.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling, Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 593-607. Springer, 2018.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collective classification in network data. Al magazine, 29(3)933-93, 2008
Blake Shaw, Bert Huang, and Tony Jebara. Learning a distance metric from a network. In Advances in Neural Information Processing Systems, pp. 1899-1907, 2011.
Charles Spearman. general intelligence," objectively determined and measured. The American Journal of Psychology, 15(2):201-29) 1904.
Nils Chr Stenseth, Wilhelm Falck, Ottar N Bjørnstad, and Charles J Krebs. Population regulation in snowshoe hare and canadian lynx: asymmetric food web configurations between hare and lynx. Proceedings of the National Academy of Sciences, 94(10):5147-511 1997.
Da Tang, Dawen Liang, Tony Jebara, and Nicholas Ruozzi. Correlated variational auto-encoders. arXiv preprint 100.00005 2019.
Edward Wagstaff, Fabian B Fuchs, Martin Engeleke, Ingmar Posner, and Michael Osborne. On the limitations of representing functions on sets. arXiv preprint vrXiv:1901009006 2019.
Jeffrey Wood and John Shawe- Shawe-Taylor. A unifying framework for invariant pattern recognition. Par- tern Recognition Letters, 17(14):1413 115-11222 1996.
14

---

Published as a conference paper at ICLR 2020
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A comprehensive survey on graph neural networks. arXiv preprint arXiv:1901.00590 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00822 2018.
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? arXiv preprint arXiv: 1,
Zhilin Yang. William W Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. ICML, 2016.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. arXiv preprint MXXv::990..08//11 2019.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances in neural information processing systems, pp- 3391-3401, 2017.
Muhan Zhang and Yixin Chen, Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, 2018.
Dengyong Zhou, Olivier Bousquet, Thomas N Lal, Jason Weston, and Bernhard Schölkopf. Learn- ing with local and global consistency. In Advances in neural information processing systems, pp. 321-328, 2004.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Graph neural networks: A review of methods and applications. arXiv preprint arXiv: 2018.
Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-super learning using gaussian fields and harmonic functions. In Proceedings of the 20th International conference on Machine learning (ICML-03), pp. 912-919, 2003.
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, (3(14):190-i1198 2017.
15

---

Published as a conference paper at ICLR 2020
APPENDIX
7 A VISUAL INTERPRETATION OF NODE EMBEDDINGS AND STRUCTURAL REPRESENTATIONS
In what follows we showcase the difference between structural representations (Figure and po- sitional node embeddings (Figure 4 obtained by graph neural networks and SVD, respectively, on the same graph. The graph is the food web of Figure | and consists of two disconnected subgraphs.
Figure 3 shows a 2-dimensional (IR2) structural representation of nodes obtained by standard GNN (obtained by the 1-WL GNN offXu et al. (2018), optimized try to predict links without the addition of any random edges). Node colors represent the mapping of the learned structural repre- sentation in R² into the red and blue interval of RGB space [0. 255]². Note that isomorphic nodes are forcibly mapped into the same structural representations (have the same color), even though representation trained to predict links. Specifically, the lynx and the orca Figure get same color since they isomorphie, while the lynx and the coyote have different structural rep- resentations (different colors). The lynx, like the orca, a top predator in the food web while the coyote is not top predator. Hence, it is quite evident why GNN's s not traditionally used for link prediction: as the structural node representation is a color, using these representations is akin asking "is light pink node in [ question unless we also specify which light pink (i.e. coyote or seal) and which light blue (i.e. orca or lynx) 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 generalizes it to joint k-node structural representations for any f--odde joint prediction task.
to light blue node?" We cannot answer this
Red Squirel
Pelagic Fish
Coyena
Seel
* Lyrox
Orca
While Spruce
Snowshoe Have
Zooplankton
Kril
Ground Squiral
Penguin
Fox
Figure 3: (Best in color) Food web graph of Figure with node colors that map two dimensional representation from a 1-WL GNN (GIN- (Xu et al. 2018)) into the [0, 255] interval of blue and red intensity of RGB colors respectively. GIN is used representative of structural representation of nodes. Structurally isomorphic nodes, obtain the same representation and are hence end up being visualised with the same color. Consequently, is clear why structural node representations are used for node and graph classification, but not for link prediction.
Positional node embeddings, on the other hand, are often seen as 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 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 different. Node embeddings are often seen as encoding the fact that the lynx and the coyote are part of tightly-knit community, while the lynx and orca belong distinct communities.
significantly
evident from Figure g why positional node embeddings are not traditionally used to predict node classes: predicting that the lynx, like the orca, is top predator based their node colors is
16

---

Published as a conference paper at ICLR 2020
difficult, since the coyote's color is very similar to that of the lynx, while the orca obtains pletely different color to the lynx. Relying on color shades (light and dark) for node classification unreliable, since nodes with completely different structural positions in the food chain may have similar color shades. Our [heorem@]showe however, that any positional node emhedding (actually, any node embedding) must be sample of distribution given by the most-eppressive 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 Figure D 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 node obtains from random permutations of the adjacency matrix.
On the other hand, link prediction using the colors in Figure mean "closeness" the graph. For instance, we may easily predict that the baleen whale also eats zooplankton.
D is rather trivial, since similar colors
Red Squirel
Pelagic Feh
Cayors
Seef
Lyrxx
Orca
White Spruce
Snowshoe Hime
Zooplankton
Krill
Oround Squirel
Penguin
Red Fox
Baleen Whale
Figure 4: (Best in color) Food web graph of Figure with node colors that map the values of the two leading (SVD) eigenvectors over the undirected graph into the [o, 255] interval of blue and red intensity of RGB colors, respectively. SVD (run until convergence) used as a representative of positional node embedding methods. The graph is made undirected, otherwise the left and right eigenvectors will be different and harder to represent visually. Note that nodes which are a part of the same connected component, obtain embeddings which close in latent space, visually shown as similar colors. Consequently, it is clear that positional node embeddings can be used for link prediction and clustering.
PRELIMINARIES
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 push- forward measures.
A probability law Z) Theorem 6. 60) by pure random noise e Uniform(0, 1) independent of (A, X), passing through deterministic function Z f((A, X),e) -where f Σ,, [0, + L, where Ω in our task will be a matrix Ω = x defining node representations, 2 1. That is, the randomness in the conditional is deterministic.
(A, (A, Σn. can be described (Kallenbrrg 2006
p(2 A. X)) entirely outsourced to
Now, consider replacing the graph G = (A, by G-equivariant representation I'A, X) of its nodes, the output of neural network r E, Raim > 1, that gives representation each node in G. If representation (A X) is such that 3f' where = {A, X, = fT X), )),c), c). V(A, X) E, and Ve [0. then I' A. X) does not lose any information when comes predicting Z. Statistically (Kallenberg 2006 Proposition 6. 13). Z _LI-(A.x) (A, X). We call (A, X) a most-expressive representation of with respect to Z. A most-expressive representa- tion (without qualifications) is that is most-expressive for any target variable.
17

---

V; can be equivalently defined Published as a conference paper at ICLR 2020
Representation learning is powerful precisely because it can learn functions I that 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 I" that outputs Z is also Geequivariant, without loss of information.
PROOF OF THEOREMS, LEMMAS AND COROLLARIES
We restate and prove Lemma
Lemma 1. Two nodes V, u E V, have the same most-expressive structural representation and are isomorphic nodes in G (A, (Definition 6
T (M A, X) T A, X)
Proof. In this proof, consider both directions.
Consider two nodes v, u E which satisty the condition, ( but are not isomorphic in G = (A, X). By contradiction, suppose and v have different node orbits. This a contradiction, since the bijective mapping of Definition would have to take the same input and map them different outputs.
(=) By contradiction, consider the two nodes u, v E V which are isomorphic in G (A, X) but with different most expressive structural representations i.c. (0 X) * I A, X). This is contradiction, because as per Definition 6 two nodes should have the same structural representation, which would imply the most expressive structural representation is not structural representation. Hence, the two nodes should share the same most expressive structural representation.
Next, we restate and prove Lemma 2
Lemma (Causal modeling through noise outsourcing). Definition of Galles & Pearl 1998) gives causal model as triplet
= F).
where U a set of exogenous variables, is set of endogenous variables, and F is a set of func- tions, such that in the causal model, v; = f(ū, is the realization of random variable V, V and a sequence of random variables PA, with PA; VVV, as the endogenous variable parents of variable V, as given by a directed acyclic graph. Then, there exists a pure random noise e and a set of (measurable) functions (gu weu such that for V, as v, a- fjū, Iu(cu)). where cu has joins distribution (Cu)vuEU 0. (c(c) for some Borel mea- surable function o' and random variable Uniform(O, 1). The latter defines M via noise outsourcing (uustin 2008
Proof. By Definition Galles & Pearl 19988, the set of exogenous variables U are not affected by the set of endogeneous variables V. The noise outsourcing lemma (Lemma 3.1) offAusti (2008) (or its more complete version Theorem 6.10 1 of Kallenberg (2006)) shows that any samples of a joint distribution over a set of random variables U can be described as (u) = g(e), for some Borel measurable function g and random variable
Uniform(O, 1). As the composition of two Borel measurable functions is also Borel measurable, is trivial to show that there exists Borel measurable
functions {gu wee and g', such that u = gu(ew) and (Ew)vueu a.e. g(()). The latter is trivial since Iu can just be the identity function, Ia (I) œ.
Next, restate and prove Lemma
Lemma 3. The permutation equivariance of p in Definition 12 implies that, if two proper subsets of nodes S1, Ç. V are isomorphic, then their marginal node embedding distributions must be the same up permutation, i.e., p((Z))ies X) πT (p((Z) (Zz)) A, for some appropriate permutation π.
trivial to observe that two isomorphic nodes u, v E V in graph G = () have the same marginal node embedding distributions. In this proof we extend this to node sets S C V where |S] > We marginalize over (Zi)igs, to obtain p( p((Z,)ess A, X) and in the other over (7, ligs, to obtain p((,))is, A, X) respectively.
Proof. From Definition 12
18

---

Published as a conference paper at ICLR 2020
We consider 2 cases follows:
Case 1: S1 Sy: 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 A S2: Since S₁ and S2 are also given to be isomorphic, it clear to see that every node
in S1 has isomorphic equivalent in S2. In a graph G = (A, X), the above statement conveys that S2 can be written as a permutation क on S1, ie S = ((S)). Now, employing Definition 12 is clear to see that pl (Z) A, X) T(p(( Jes, A, X))
Next, we restate and prove Theorem
Theorem 1. Let S C P(V) ) be set of subsets V. Let Y)S,A,X) (Y A)))ssss be V. sequence of random variables defined over the sets E S of graph G (), such that we ((S,, X) for any 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 ip such that, Y X) = where es is pure source of random noise from joint distribution (es independent of and X.
define ( A, x) Y, A, X and A.
(p(I*(S A, (),
Proof. The case = V is given in Theorem 12 of BBooem-Redy & Teh (2019). The case S is trivial. The case S ç V. + 0, is described follows with constructive proof. First consider the case of two isomorphic sets of nodes Si, S2 E S. As by defini- tion (S,, A, X) - Y(S2, A, X), we must assume p(Ys, A x) = (A We can now use the transfer theorem (Kallenberg 2006 Theorem 6.10) to obtain joint description 22(52, A, X,),, where is common source of independent noise. As Si and S2 are joint isomorphic (Definition 7 there exists an isomor- phism S₁ = iS2). where Φi (iso(S) $2), A, A, = Φr AS,,A, X, Because the distribution given by dn (.)c must be isomorphic-ing invariant in (A, X)) and S1 and S2 are also isomorphie in cinnorphi--ivariannt
Yg, A (S1, A, x)) and Y5, A
(A, X) then, for all permutation actions π E II. there exists a new isomorphism iso' such that s (i (52)), T (A), ()), & Φ1 (oSo'(TT55)) (iso((T(S))) π ((A), (X), which allows us to create a function s that incorporates iso' into d1. Due the isomorphism between S1 and S2, we can do the same process for S2 to arrive at the same function yp. We can now apply Corollary 6.11 (Kallen- berg 2006) over (Yg, A X, Yg, A, X) along with measure-preserving mapping
show that
0'(5, A, X, E2), where (e1, = f(e). If Si and simply define ('(Ss,)) = (z(S,,)) ). Definition 11 allows us define function t from which we rewrite (S,, X, G,) as (PT A.)) Applying the same procedure to all 5 E S concludes our proof.
Ys. A, ('()), A, X, E1) and Yg, |A, S2 are not joint isomorphic,
Next, we restate and prove Theorem 2
Theorem 2 (The statistical equivalence between node embeddings and structural representationss, A.) be in Theorem | Consider graph G (A, Σn.
Let (S, X) Let I* (Š, A, X) be most-expressivee structural representation of nodes S E in (A, X). Then,
Y(Š.A. (...(A ZAA. X. YS
for any node embedding matrix Z that satisfies Definition 12 where A l1 C means is indepen- dent of C given B. Finally, V(A, X) E En, there exists a most-expresiiee node embedding Z A X such that,
r T* Ez- [F ((2))) A), AS VSES,
for some appropriate collection functions (f()
Proof. In the first part of the proof. for any embedding distribution pl Z (AA)), we note that by Theorem A, a.s. (S A, X), X))es) Hence, Y(Š, A, X) 1L L. ZIA X, VS E S, is direct consequence of Proposition 6.13 in (Kallenberg 2006).
19

---

Published as a conference paper at ICLR 2020
most-expressive representation of graph (A.X) of size n, with permutations that act only on unique node ids (node orderings) added as node features: II' A X)
In the second part of the proof, construct orbit
Vvev Vrre,,, where [A, bj concate- nates 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 X is most-expressive node embedding. Clearly, A, X is a node embedding, since the uniform measure over (A, X) is G-equivariant. All that left to show is that we can construct 1 of any-size subset S S from A, X via
{((T"(e, A, [X, T(L, ....,.). (TI....,
..) "
(* A, x) Ez- ( (2- (Z))EES) A, X],
for some function f((S)) This part of the proof has a constructive argument and comes in two parts.
Assume S E S has no other joint isomorphic set of nodes in S, i.e., DS2 E S such that S and S2 are joint isomorphic in (A, X). ). For any such subset nodes S E S, and any element Rg E II, X). there is bijective measurable map between the nodes in S and their positions in the representation vector R = (I A, [X, π (l...... ... D))ev,, since all node features are unique and there are no isomorphic nodes under such conditions. Consider the multiset
Os x)= == {(T (u, AX,, ((,,..,,................ Divess Ivenl,
of the representations restricted to the set S. We now show that there exists surjection be- tween Os (A, X) and (5, A, X). There is a surjection
for all S1. S2 E (V) that are non-isomorphic, it implies Os, (A, X) + Os2 (A, X). The condition is trivial if [S * S as [Os, (A, x * OOs (A, X).. If |S]| [S2), we prove by contradiction. Assume Os: A X = Os,y A, x). Because of the unique feature ids and because 1' is most-expressive, the representa- tion (e, A, (I......., n)']) of node u E V and permutation π E II, is unique. As S₁ is not isomorphic to S2, and both sets have the same size, there must be at least one node has no isomorphic equivalent in S2. Hence, there exists т E II, that gives a unique representa- tion [''(,. A, X (1, .I...... n) 77) that does not have a matching [' A, [X, (1,...,, (T) for any V E S2 and n E II, Therefore. 3a E Os, (A, X), where a & Os. (A, X), which is a contradiction since we assumed Os, (A. X) Os2 (A, X).
S1 that
Now that we know there is such a surjection, a possible surjective measurable map between Os(A.X) and (Š A, X) is multiset function that takes Os X) and outputs (S A, X). For finite multisets whose elements are real numbers R. Wagstaff et al. (2019) shows that most- expressive multiset function
be defined as the average of function f(s) over the multiset. The elements of Os (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 IR. Thus, by Wagstaff et al. 2019. there exists some surjective function ((S1) whose average over (A, give (S(SA,
Now assume S S2 C V are joint isomorphic in (A, X), Sr. S2 * 0. Then, we have concluded that Os, (A, X) Os, (A, X). Fortunately, by Definition 10 this non-uniqueness is required property of the structural representations of (S (S,,A A, X) and (S2, A, X), which must satisfy [* A, X)= I (S2, A, X) if 5₁ and S2 are joint isomorphic, which concludes our proof.
Next, we restate and prove Corollary !
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 fuctorization (a.k.a. word2vec)- latent embeddings given by Bayesian graph models such as Probabilistic Matrix Factorizations (PMFs) and variants-, vari- ational autoencoder methods and graph neural networks that use random lighthouses to extract node embedddings.
Proof. In Probabilistic Matrix Factorization (Mnih & Salakhutdinov 2008), we have A ~ N Zw, I where Z, ~N,, o²1). Z, o0). 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 the o² I matrix well to obtain Z. The proof for Poisson Matrix Factor- ization (Gopalan et al., 22014a b) follows a similar construction to the above, wherein the Normal assumption is replaced by the Poisson distribution.
20

---

Published as a conference paper at ICLR 2020
Moreover, any matrix factorization algorithm gives equivariant distribution of embeddings if the input matrices are randomly permuted upon input. Specifically, any Singular Value Decom- position (SVD) method satisfies Definition [22 the distribution of the eigenveetor solutions to degenerate singular values -which are invariant to unitary rotations in the corresponding degener- 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 (001) and implicit
matrix factorization (Levy Goldberg 2014 Mikolov al. 2013).
PGNN's (You et al. 2019) compute the shortest distances between every node of the graph with a "anchor' nodes to encode distance metric. By definition, using such distance metric would make the node embeddings learned by this technique G-equivariant. The shortest path between all pairs of nodes in graph can be seen equivalently as function of polynomial in A Alternatively, this can also be represented using the adjacency matrix and computed using the Floyd- Warshall 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 function of A, X and noise. The noise in this case is characterized by the randomized anchor set selection.
predetermined
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 are learned either via a mean field approximation
sampled independently of each other i.e. Z P(- X). We note that in the case of the mean field approximation, the probability distribution a Dirac Delta. It is clear to see that the Z learned in this case is G-equivariant with respect any permutation action of the nodes in the graph.
Next, we restate and prove Corollary 2
Corollary 2. The link prediction task between any nodes u, U V depends only on the most- expressive tuple representation (*, 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 function f such that I ((u, v), X) = Ez [f Z [, Vu, v.
Proof. It is consequence of Corollary 3 with |S = 2.
Next, restate and prove Corollary 3
Corollary 3. Sumple Z according to Desinition 12 Then, can learn k-node structural repre-
sentation of a subset of k nodes S V, [S] = k. simply by learning a function f(k] whose average
r(S, A, X) = ((2.)ves) can be used to accurately predict Y (5,A,
Proof. This proof is direct application of Theorem which shows the statistical equivalence be- tween node embeddings and strucutral representations.
Note that ((),)) can equivalently be represented as (<p((() A, X Jues: es)) using The- orem 2 and that the noise és is marginalized from the noise distribution Theorem [ still pre- serving equivariance. With an assumption of the most powerful f((),, which is able to capture dependencies within the node set (Murphy et al., 2018) and noise cs, replace the above with ('(h)) (SP(((S X.,))s) and subsequently compute an expectation over this function to eliminate the noise.
Next, 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 em- beddings, and we can get node embeddings from any-size most-expressive joint representations.
21

---

Published as a conference paper at ICLR 2020
Hence, given enough computational resources, node embeddings and graph representations 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
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 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 [2 using GNN's. By averaging over multiple such node embeddings gives us structural representations more powerful than that of standalone GNN's.
10 COLLIDING GRAPH NEURAL NETWORKS (CGNNS)
In this section we propose new variational auto-encoder procedure to obtain node embeddings using neural networks, denoted Colliding Graph Neural Networks (CGNNs). Our sole reason to propose auto-encoder method is because want to test the expressiveness of node embed- ding 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 X,,- R V i E V, we introduce latent variable Z, RR In addition, our graphical model also consists of observed vari- ables Arji E RRd 4 j V. These are related through the joint distribution p(A, X [)) Hyyvvvy p( (A Zi,,, (T.)[lev pl (X,,.IZa.>) which is summarized by the Bayesian network in Figure in the Appendix. Note that A.j. is a collider, since it is observed and influenced by two hidden variables, Zi.., Zj.. A neural network 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 Vi V, with each ( (O, I) independently, where 7 is the identity matrix. Subsequently time steps 2, in accordance with the graphical model, each variable z(!h is sequentially sam- pled from its true distribution conditioned on all observed edges of its corresponding node i, in addition 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 [ 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 al. 2011). Our unsupervised objective is reconstructing the noisy adjacency matrix.
11 CGNN ALGORITHMS
The procedure to generate node embeddings used by the CGNN is given by Algorithm Structural representations are computed as an unbiased estimate of the expected value a function the node embedding samples as given by Algorithm 2 via of sets function (Meng al. 2019)
22

---

Observed evidence variables in Published as a conference paper at ICLR 2020
input A, X, num-times
output: Z
initialization: Z (0 V
while num-times > 0 do
for u E V do
Ve E V such that A.. =
hidden f( Z. / / f is permutation invariant function
visible + ( [): // is a permutation invariant function
Zn MLP (hidden, visible, X.,) + Noise With Reparametrization Trick
// Equivalently, Zu P( { XAu)).
end
num-times f- num-times-
end
Algorithm Node Embeddings from the Unrolled Gibbs Sampler
Zi
X
[E().n)
Ai
4J eela)
Figure 5: Latent variable model for Colliding Neural Networks. gray
12
FURTHER RESULTS
In Table 2 we provide the results on node classification, link prediction and triad prediction on the Citeseer datasct.
13 DESCRIPTION OF DATASETS AND EXPERIMENTAL SETUP
detailed description the datasets and the splits are given in Table 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 had the best performance in tasks (we had tested with 2/3/4/5 convolutional layers). Also since perform tasks based on node representations rather than graph representations, we ignore the graph wide readout. For GIN and RP-GIN, the embedding dimension layers. All MIPS, 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 the code provided.
to 256 both convolutional
23

---

Published as a conference paper at ICLR 2020
input: : (Z 1i=1 k node embedding samples, node size
output: {{ (Si)vs.cV.js/)= //ttructura representations, S is a set of sets initialization: g{Z]s) {(}
for i 11, m do
for S do
0 Z, hues) t g( (uEs) - ((Za Jues) // f is permutation invariant function
end end
Algorithm 2: Structural Representations from the Node Embedding Samples
Table 2: Micro F1 score on three distinct tasks over the Citeseer dataset, averaged over 12 runs with standard deviation parenthesis. The number within the parenthesis heside the model name indicates the number Monte Carlo samples used in the estimation SVD procedure run until convergence with one Monte Carlo sample for the representation. Bold values show maximum empirical average, and multiple bolds happen when its standard deviation overlaps with another average.
structural representation. MC-SVD (1) denotes
Node Classification
Link Prediction
Triad Prediction
Random
0.167
0.500
0.250
GIN(1)
(0.038)
0.543(0.024)
0.309(0.009)
GIN(5)
0.706(0.044)
0.525(0.040)
0.311(0.022)
GIN(20)
0.718(0.034)
0.530(0.023)
0.306(0.012)
RP RP-GIN(1)
0.719(0.031)
0.541(0.034)
0.313(0.005)
RP-GIN(5)
0.703(0.026)
0.539(0.025)
0.307(0.013)
RP-GIN(20)
0.724(0.020)
0,551(0.030)
0.307(0.017)
1-2:3 GNN((
(.18(()))26)
0.499(0.002)
0.306(0.010)
1-2-3 GNN(S)
(..94))))
0,506(0.018)
0.310(0.112)
1-2-3 GNN(20)
0, (..090))
0,502(0.014)
03100000200
MC-SVD'
0.733(00007)
0.552(0.021)
0.304(0.011)
MC-SVD(I)
0.734(0.007)
0.562(0.017)
0.297(0.015)
MC-SVD(5)
(.739)0.006)
022))(
(.00
MC-SVD(20)
0.737(0.005)
0.565(0.000)
0.299(0.015)
CGNN()
0.681)
0.598(0.024)
0.305(0.009)
CGNN(S)
0.713(0.009)
0.627(0.048)
0.301(0.013)
CGNN(20)
(0.000
0.654(0.049)
0.296(0.008)
Table 3: Summary of the datasets
CHARACTERISTIC
CORA
CITESEER
PUBMED
PPI
Number of Vertices
2708
3327
19717
56944, 2373"
Number of Edges
10556
9104
88648
819994, 41000"
Number of Vertex Features
1433
3703
500
50
Number of Classes
7
121
Number of Training Vertices
1208
1827
18217
44906e
Number of Validation Vertices
500
500
500
6514c
Number of Test Vertices
1000
1000
1000
5524
The PPI dataset comprises several graphs, so the quantities marked with "a", represent the age characteristic all graphs.
For PPI, there are 121 targets, each taking values in {0, 1}.
All of the training nodes come from 20 graphs while the validation and test nodes come from two graphs each not utilized during training.
24


Reviews:
[{"review_id": "SkgAYSx2qr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nOverall, this paper tries to suggest a solution to a somewhat confusing and controversial problem that everyone recognises but hard to figure out a clear resolution. In that sense, this paper would serve as a good starting point by providing some theoretical baselines. I would like to see more discussion on this topic in future.\n\nIn many graph problems where each node is endowed with a certain feature set, we often observe the case where two subsets of nodes are isomorphic in terms of link structure but with different edge of node features. It would be good if there are some discussions on these cases.\n\nHere's a minor comment on the representation of the paper. Although the concept of node embedding and structural representations get clearer as reading, the introduction, where I couldn't find any reference of these, seems unlikely to clarify the difference between these two concepts. The familiar representation in Section 3 might be the first part where the readers could get some intuition about their differences.\n\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "S1ewogbg5r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors present mostly theoretical analysis indicating the equivalence of embeddings and structural graph representations. The authors argue that while most of the earlier work consider these to be different, they are actually the same and give theory and empirical results to back up this claim.\n\nThis is not an easy paper to read, as the authors immediately jump into heavy notation without much intuition or visual aid. It would be much better to include some figures to help the readers appreciate the work.\nThis continues throughout the experiments as well, where the authors are not very gentle when it comes to presentation.\n\nI gave a weak accept as I do not want my (unfortunately) weak review (due to the paper topic not being my strong point) to have a great effect on the final decision. However, it is clear that the paper can and should be better written, and the paper ideas made closer to the readers. At the moment this is definitely not the case.\n\n\n======= AFTER THE REBUTTAL ===========\n\nThank you for working on making the paper more accessible. I am perfectly fine with seeing this paper at the conference, and will change the vote to Accept simply to not block on my vote and to ensure the SPC makes sure to thoroughly consider this paper (in case they do some sort of ranking of paper reviews for deciding who gets accepted). However please note that my confidence remains as low as previously.\nIt is unfortunate that ICLR did not do any paper-reviewer matching like other conferences and that you are stuck with my weak review. But that is a different story that the organizers should make sure to address asap.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "HyeXHFGS9B", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a unifield theoretical framework for node embeddings and structural graph representations, which bridgs methods like matrix factorization and graph neural networks.\nThe theoretical analysis is sufficient and experimental results are good. The theory alo shown that the concept of transductive and inductive learning is unrelated to node embeddings and graph representations, which clears another source of confusion in the literature.\nIn my opinion, this is a theory paper and the proof are sufficient.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper shows the relationship between node embeddings and structural graph representations. By careful definition of what structural node representation means, and what node embedding means, using the permutation group, the authors show in Theorem 2 that node embeddings cannot represent any extra information that is not already in the structural representation. The paper then provide empirical experiments on three tasks, and show in a fourth task an illustration of the theoretical results.

The reviewers of the paper scored the paper highly, but with low confidence. I read the paper myself (unfortunately not with a lot of time), with the aim of increasing the confidence of the resulting decision. The main gap in the paper is between the phrases "structural node representation" and "node embedding", and their theoretical definitions. The analogy of distribution and its samples follows unsurprisingly from the definitions (8 and 12), but the interpretation of those definitions as the corresponding English phrases is not obvious by only looking at the definitions. There also seems to be a sleight of hand going on with the most expressive representations (Definitions 9 and 11), which is used to make the conditional independence statement of Theorem 2. The authors should clarify in the final version whether the existence of such a representation can be shown, or even better a constructive way to get it from data.

Given the significance of the theoretical results, the authors should improve the introduction of the two main concepts by:
- relating them to prior work (one way is to move Section 5 towards the front)
- explaining in greater detail why Definitions 8 and 12 correspond to the two concepts. For example expanding the part of the proof of Corollary 1 about SVD, to make clear what Definition 12 means.
- a corresponding simple example of Definition 8 to relate to a classical method.

The paper provides a nice connection between two disparate concepts. Unfortunately, the connection uses graph invariance and equivariance, which is unfamiliar to many of the ICLR audience. On balance, I believe that the authors can improve the presentation such that a reader can understand the implications of the connection without being an expert in graph isomorphism. As such, I am recommending an accept.


Decision: Accept (Poster)