Title: P 2 IR: UNIVERSAL DEEP NODE REPRESENTATION VIA PARTIAL PERMUTATION INVARIANT SET FUNCTIONS

Abstract: Graph node representation learning is a central problem in social network analysis, aiming to learn the vector representation for each node in a graph. The key problem is how to model the dependence of each node to its neighbor nodes since the neighborhood can uniquely characterize a graph. Most existing approaches rely on defining the specific neighborhood dependence as the computation mechanism of representations, which may exclude important subtle structures within the graph and dependence among neighbors. Instead, we propose a novel graph node embedding method (namely P 2 IR) via developing a novel notion, namely partial permutation invariant set function to learn those subtle structures. Our method can 1) learn an arbitrary form of the representation function from the neighborhood, without losing any potential dependence structures, 2) automatically decide the significance of neighbors at different distances, and 3) be applicable to both homogeneous and heterogeneous graph embedding, which may contain multiple types of nodes. Theoretical guarantee for the representation capability of our method has been proved for general homogeneous and heterogeneous graphs. Evaluation results on benchmark data sets show that the proposed P 2 IR outperforms the state-of-the-art approaches on producing node vectors for classification tasks.

1. INTRODUCTION:

Graph node representation learning (or graph embedding in some literature) is to learn the numerical representation of each node in a graph by vectors in a Euclidean space, where the geometric relationship reflects the structure of the original graph. Nodes that are "close" in the graph are embedded to have similar vector representations (Cai et al., 2017) . The learned node vectors benefit a number of graph analysis tasks, such as node classification (Bhagat et al., 2011) , link prediction (Liben-Nowell & Kleinberg, 2007) , community detection (Fortunato, 2010) , and many others (Hamilton et al., 2017b) . In order to preserve the node geometric relations in an embedded space, the similarity/proximity/distance of a node to its neighborhood is generally taken as input to different graph embedding approaches. For example, matrix-factorization approaches work on pre-defined pairwise similarity measures (e.g., different order of adjacency matrix) (Zhang et al., 2018) . Deepwalk (Perozzi et al., 2014) , node2vec (Grover & Leskovec, 2016) and other recent approaches (Dong et al., 2017) consider flexible, stochastic measure of node similarity by the node co-occurrence on short random walks over the graph (Goyal & Ferrara, 2017) . Neighborhood autoencoder methods compress the information about a node's local neighborhood that is described as a neighborhood vector containing the node's pairwise similarity to all other nodes in the graph (Wang et al., 2016; Cao et al., 2016; Bojchevski & Günnemann, 2018) . Neural network based approaches such as graph convolutional networks (GCN) and GraphSAGE apply convolution like functions on its surrounding neighborhood for aggregating neighborhood information (Kipf & Welling, 2016a; Hamilton et al., 2017a; Tu et al., 2018) .

However, most existing methods either explicitly or implicitly restrict the dependence form of each node to its neighbors and also the depth of neighbors. Therefore, some important topology structures within the graph and subtle dependence between neighbors may not be captured in the embedded space. For example, the methods in the family of stochastic walk lose the control of influence of further neighbors in a network since they usually utilize a fixed hyper-parameter as a window size, or need to specify the degree of neighborhood proximity; GCN losses the flexibility of neighborhood information since it fixes the two-layer aggregation function for the representation computation.

In this work, we propose a Partial Permutation Invariant Representation method (P 2 IR) by developing a new notion of partial permutation invariant set function, that can

• learn node representation via a universal graph embedding function f , without pre-defining pairwise similarity, specifying random walk parameters, or choosing aggregation functions among element-wise mean, a max-pooling neural network, or LSTMs; • capture the arbitrary relationship of each node to its neighbors;

• automatically decide the significance of nodes at different distances;

• be generally applied to any graphs from simple homogeneous graphs to heterogeneous graphs with complicated types of nodes.

Evaluation results on benchmark data sets show that the proposed P 2 IR outperforms the state-of-theart approaches on producing node vectors for classification tasks.

2. RELATED WORK:

The main difference among various graph embedding methods lies in how they define the "closeness" between two nodes (Cai et al., 2017) . First-order proximity, second-order proximity or even high-order proximity have been widely studied for capturing the structural relationship between nodes (Tang et al., 2015b; Yang et al., 2017; Zhu et al., 2018) . Comprehensive reviews of graph embedding have been done by Cai et al. (2017) ; Hamilton et al. (2017b) ; Goyal & Ferrara (2017) ; Yang et al. (2017) .

In this section, we discuss the relevant graph embedding approaches in terms of how node closeness to neighboring nodes is measured, for highlighting our contribution on utilizing neighboring nodes in a most general manner.

Matrix Analysis on Graph Embedding:

As early as 2011, a spectral clustering method (Tang & Liu, 2011) was proposed to take the eigenvalue decomposition of a normalized Laplacian matrix of a graph as an effective approach to obtain the embeddings of nodes. Other similar approaches choose different similar matrix (from Laplacian matrix) to make a trade-off between modeling the "first-order similarity" and "higher-order similarity" (Cao et al., 2015; Ou et al., 2016; Rossi et al., 2018) . Node content information can also be easily fused in the pairwise similarity measure, e.g., in TADW (Yang et al., 2015) , as well as node label information, which resulting in semi-supervised graph embedding methods, e.g., MMDW (Tu et al., 2016) . Recently, an arbitrary-order proximity preserved network embedding method is introduced in (Zhang et al., 2018) based on matrix eigen-decomposition, which is applied to a pre-defined high-order proximity matrix. For heterogeneous networks, Huang et al. (2017) proposed a label involved matrix analysis to learn the classification result of each vertex within a semi-supervised framework.

Random Walk on a Graph to Node Representation Learning Both deepwalk (Perozzi et al., 2014) and node2vec (Grover & Leskovec, 2016) are outstanding graph embedding methods to solve the node representation learning problem. They convert the graph structures into a sequential context format with random walk (Lovász, 1993) . Thanks to the invention of Mikolov et al. (2013) for word representation learning of sentences, deepwalk inherited the learning framework for words representation learning in paragraphs to generate the representation of nodes in random walk context. And then node2vec evolved such the idea with additional hyper-parameters tuning for the trade-off between DFS and WFS to control the direction of random walk. Struc2vec (Ribeiro et al., 2017) also utilizes the multilayer graph to construct the graph node representations. Gao & Huang (2018) propose a self-paced network embedding by introducing a dynamic negative sampling method to select difficult negative context nodes in the training process. Planetoid (Yang et al., 2016) proposed a semi-supervised learning framework by guiding random walk with available node label information. The heterogeneity of graph nodes is often handled by a heterogeneous random walk procedure (Dong et al., 2017) , or selected relation pairs (Chang et al., 2015) . Tang et al. (2015a) considered the predictive text embedding problem on a large-scale heterogeneous text network and the proposed method is also based on pre-defined heterogeneous random walks.

Neighborhood Encoders to Graph Embedding:

There are also methods focusing on aggregating or encoding the neighbors' information to generate node embeddings. DNGR (Cao et al., 2016) and SDNE (Wang et al., 2016) introduce the autoencoder to construct the similarity function between the neighborhood vectors and the embedding of the target node. DNGR defines neighborhood vectors based on random walks and SDNE introduces adjacency matrix and Laplacian eigenmaps to the definition of neighborhood vectors. GraphWave (Donnat et al., 2018) learns the representation of each node's neighborhood via leveraging heat wavelet diffusion patterns. Although the idea of autoencoder is a great improvement, these methods are painful when the scale of the graph is up to millions of nodes. Therefore, methods with neighborhood aggregation and convolutional encoders are involved to construct a local aggregation for node embedding, such as GCN (Kipf & Welling, 2016a; b; Schlichtkrull et al., 2018; van den Berg et al., 2017) , FastGCN (Chen et al., 2018) , column networks (Pham et al., 2017) , the GraphSAGE algorithm (Hamilton et al., 2017a) , GAT (Velickovic et al., 2017) and a recent DRNE (Tu et al., 2018) method using layer normalized LSTM to approximate the embedding of a target node by the aggregation of its neighbors' embeddings. The main idea of these methods is involving an iterative or recursive aggregation procedure e.g., convolutional kernels or pooling procedures to generate the embedding vectors for all nodes and such aggregation procedures are shared by all nodes in a graph.

The above-mentioned methods work differently on using neighboring nodes for node representation learning. They require on pre-defining pairwise similarity measure between nodes, or specifying random walk parameters, or choosing aggregation functions. In practice, it takes non-trivial effort to tune these parameters or try different measures, especially when graphs are complicated with nodes in multiple types, i.e., heterogeneous graphs. This work hence targets on making neighboring nodes play their roles in a most general manner such that their contributions are learned but not user-defined.

The resultant embedding method has the flexibility to work on any types of homogeneous and heterogeneous graph.

Our proposed method P 2 IR has a natural advantage on avoiding any manual manipulation of random walking strategies or designs for the relationships between different types of nodes. To the invention of set functions by Zaheer et al. (2017) , all existing valid mapping strategies from neighborhood to the target nodes can be represented by the set functions which are learnt by P 2 IR automatically.

3. THE PROPOSED P 2 IR METHOD:

In this section, we first formally define the problem, followed by introducing a new notion -partial permutation invariant function set function. This section ends up with the overall P 2 IR method.

3.1. PROBLEM SETUP:

We target on designing graph embedding models for the most general graph that may include K different types of nodes (k=1 for homogeneous graphs). Formally, a graph G = {V, E}, where the node set V = ∪ K k=1 V k , i.e., V is composed of K disjoint types of nodes. One instance of such a graph is the academic publication network, which includes different types of nodes for papers, publication venues, author names, author affiliations, research domains etc. Given such a graph G, our goal is to learn the embedding vector for each node in this graph.

3.2. THE PROPOSED UNIVERSAL GRAPH EMBEDDING MODEL:

As we know, the position of a node in the embedded space is collaboratively determined by its neighboring nodes. Therefore, the key issue to address for graph embedding is how to model the dependence of each node to its neighbors. Most existing approaches need to pre-specify the neighbors (usually via the distance on the graph), and either explicitly or implicitly define a specific form to characterize the dependence between each node and its neighbors.

We propose a universal graph embedding model that neither requires to pre-define neighbors nor to specify the dependence form between each node and its neighbors. The embedding vector x v of node v ∈ V k can be represented by its neighbors' embedding vectors via a function f

x v = f (X v 1 , X v 2 , • • • , X v K ), ∀v ∈ V k , ∀k ∈ {1, 2, . . . , K} where X v

k is a matrix with column vectors corresponding to the embedding of node v's neighbors in type k. Note that the neighbors can include step-1 (or immediate) neighbors, step-2 neighbors, and even further neighbors.

How to characterize an arbitrary dependence to neighbors?:

The key observation is that all neighboring nodes reachable from a target node at the same step are not distinguishable from the view of the target node. Therefore, function f (•) should be a partially permutation invariant function. That is, if we swap any elements in a X v k , the function value remains the same. Unfortunately, the set function is not simply learn-able because the permutation property is hard to guarantee directly.

One straightforward idea to represent the partially permutation invariant function is to define it in the following form

EQUATION

where P n denotes the set of n-dimensional permutation matrices. X v 1 P 1 is to permute the columns in X v 1 . It is easy to verify that the function defined in equation 1 is partially permutation invariant, but it is intractable because it involves

N k=1 (|V k | !) "sum" items.

Our solution of learning function f is based on the following important theorem, which gives a neat way to represent any partial permutation invariant function. The proof is provided in the Appendix. Theorem 3.1. [Partial permutation invariant function representation theorem] Let f be a continuous real-valued function defined on a compact set X with the following form

f   x1,1, x 1,2 , • • • , x 1,N1 G1 , x 2,1 , x 2,2 , • • • , x 2,N2 G2 , • • • , x K,1 , x K,2 , • • • , x K,N K G K    .

If function f is partially permutation invariant, that is, any permutations of the values within the group G k for any k does not change the function value, then there must exist functions h(•) and {g k (•)} K k=1 to approximate f with arbitrary precision in the following form

EQUATION

The rigorous proof is provided in Appendix. This result essentially suggests a neat but universal way to represent any partially permutation invariant function. For instance, a popular permutation invariant function widely used in deep learning max(•) can be approximated in an arbitrary precision by

max(x 1 , x 2 , • • • , x N ) ≈ h N i=1 g(x i ) with g(z) = [exp(kz)z, exp(kz)], and h([z, z ]) = z/z , as long as k is large enough. This is because max(x 1 , x 2 , • • • , x N ) = lim k→∞ N i=1 exp(kx i ) -1 N i=1 exp(kx i ) • x i .

Therefore, based on Theorem 3.1, we only need to parameterize h(•) and {g k (•)} K k=1 to learn the node embedding function, which makes the partial permutation function finally learn-able and tractable. To make equation 2 approximate an arbitrary partial permutation invariant function, we only need to ensure that functions h and all g's can represent (or approximate) arbitrary real functions. As we know, deep neural network provides an efficient way to approximate an arbitrary continuous real function, because 3-layer neural networks is able to approximate any function (Cybenko, 1989; Hornik, 1991; Haykin, 1994) . We next formulate the embedding model when considering different order of neighborhood.

How to automatically learn the importance of neighbors at different distances?:

(1-step neighbors) From Theorem 3.1, any mapping function of a node v ∈ V k can be characterized by appropriately defined functions ψ 1 , ψ 2 , • • • , ψ K , and φ k :

x v = φ k   u∈Ω v 1,1 ψ 1 (x u ) , u∈Ω v 1,2 ψ 2 (x u ) , • • • , u∈Ω v 1,K ψ K (x u )   ∀v ∈ V k , ∀k ∈ {1, . . . , K},

where Ω v n,k := Ω v n ∩ V k denotes the step-n neighbors of node v in node type k. (Multi-step neighbors) High order proximity has been shown to be beneficial on generating high quality embedding vectors (Yang et al., 2017) . Extending the 1-step neighbor model, we can have the more general model where the representation of each node could depend on immediate (1-step) neighbors, 2-step neighbors, 3-step neighbors, and even infinite-step neighbors.

x v = φ k   ∞ n=0 α n u∈Ω v n,1 ψ 1 (x u ) , ∞ n=0 α n u∈Ω v n,2 ψ 2 (x u ) , • • • , ∞ n=0 α n u∈Ω v n,K ψ K (x u )   (3) ∀v ∈ V k , ∀k ∈ {1, 2, . . . , K}.

where α 1 , α 2 , • • • , α ∞ are the weights for neighbors at different steps. Let A ∈ {0, 1} |V|×|V| be the adjacent matrix indicating all edges by 1. We involve the polynomial matrix function on the adjacency matrix A to represent the structures of various steps neighborhood with tuning the weight among 1-step to infinite-step neighbors automatically. If we define the polynomial matrix function B(•) on the adjacent matrix A as B(A) = ∞ n=0 α n A n , we can cast equation 3 into its matrix form

x v = φ k ψ1 (X 1 )[B(A)] V1,v , ψ2 (X 2 )[B(A)] V2,v , • • • , ψK (X K )[B(A)] V K ,v (4) ∀v ∈ V k , ∀k ∈ {1, 2, . . . , K},

where X k denotes the representation matrix for nodes in type k, [B(A)] V k ,v denotes the sub-matrix of B(A) indexed by column v and rows in V k , and function ψ (with • on the top of function ψ(•)) is defined as the function extension

ψ(X) := [ψ(x 1 ), ψ(x 2 ), • • • , ψ(x N )],

where ψ(•) takes the output column vectors from a function ψ(•) with each column of X to form a new matrix with N columns. For a specific node v, we apply the scale |V i,v | as N for the type i neighbors of node v in the equation above. Therefore, with the polynomial matrix function B(A), and multiple embedding vector mapping ψ(•)s, we integrate the subtle structural knowledge of various types and steps neighbors surrounding a node to compute the node representation. Note that the embedding vectors for different types of nodes may be with different dimensions. Homogeneous graph is a special case of the heterogeneous graph with K = 1. The above proposed model is thus naturally usable on a homogeneous graph.

To avoid optimizing infinite number of coefficients, we propose to use a 1-dimensional NN function ρ(•) : R → R to equivalently represent the function B(•) to reduce the number of parameters based on the following observations

B(A) = U diag ∞ n=0 α n σ n 1 , • • • , ∞ n=0 α n σ n N U = U diag (ρ(σ 1 ), • • • , ρ(σ N )) U , where A = U diag(σ 1 , • • • , σ N )U

is the singular value decomposition (SVD). We parameterize ρ : R → R using 1-dimensional NN function, which allows us easily controlling the number of variables to optimize in ρ by choosing the number of layers and the number of nodes in each layer.

Remark 3.2. Acute readers may worry about the computational complexity of SVD when the size of A is large. In general, the full SVD takes the cubic computational complexity O(N 3 ) where N is the total number of nodes in the network, which is pretty expensive if N is large. However, since our adjacency matrix of the network is typically a very sparse matrix (the number of edges is typically far less than O(N 2 )), the complexity of the matrix decomposition can be reduced from

O(N 3 ) to O(N × #e)

where #e is the number of edges in the network. Furthermore, we can use the low rank approximation approach (that is, top k eigenvalues and eigenvectors) to approximate the original large sparse matrix. Therefore, the approximated version of the matrix decomposition can be completed in O(k × #e) complexity. We apply the low rank approximation in our experiments.

In particular, such approximation has been used in large datasets including Pubmed, DBLP, and BlogCatalog. We also tested it on the small datasets including Cora, Citeseer, and Wiki by only using top eigenvalues in the range of top 15% to 50% and did not found obvious drop on the performance.

3.3. THE OVERALL P 2 IR MODEL:

For short, we denote the representation function for x v in equation 4 by

x v = R ρ,φ k ,{ψ k } K k=1 (v) ∀v ∈ V k , ∀k ∈ {1, 2, . . . , K}.

To fulfill the requirement of a specific learning task, we propose the complete P 2 IR model by involving a supervised component

min {x v } v∈V ,ρ, {φ k } K k=1 ,{ψ k } K k=1 K k=1 1 λ k |V k | u∈V k x u -R ρ,φ k ,{ψ k } K k=1 (u) 2 + 1 |V label | v∈Vlabel (x v , y v ) (5)

where V label ⊂ V denotes the set of labeled nodes, and λ k > 0 balances the representation error and prediction error. The first unsupervised learning component restricts the representation error between the target node and its neighbors with L 2 norm since it is allowed to have noise in a practical graph. And the supervised component is flexible to be replaced with any designed learning task on the nodes in a graph. For example, to a regression problem, a least square loss can be chosen to replace (x, y) and a cross entropy loss can be used to formulate a classification learning problem. To solve the problem in equation 5, we apply a stochastic gradient descent algorithm (SGD) to compute the effective solutions for the learning variables simultaneously.

4. EXPERIMENTS:

This section reports experimental results to validate the proposed method, comparing to state-of-theart algorithms on benchmark datasets including both homogeneous and heterogeneous graphs, for evaluating the applicability of our proposed method on embedding problem of general graphs.

4.1. COMPARISON ON HOMOGENEOUS GRAPHS:

We consider the multi-class classification problem over the homogeneous graphs. Given a graph with partially labeled nodes, the goal is to learn the representation for each node for predicting the class for unlabeled nodes.

Datasets We evaluate the performance of P 2 IR and methods for comparison on five datasets.

• Cora (McCallum et al., 2000) is a paper citation network. Each node is a paper. There are 2708 papers and 5429 citation links in total. Each paper is associated with one of 7 classes.

• CiteSeer (Giles et al., 1998) is another paper citation network. CiteSeer contains 3,312 papers and 4,732 citations in total. All these papers have been classified into 6 classes.

• Pubmed (Sen et al., 2008 ) is a larger and more complex citation networks compared to previous two datasets. There are 19,717 vertexes and 88,651 citation links. Papers are classified into 3 classes.

• Wikipedia (Sen et al., 2008) contains 2,405 online web-pages. The 17,981 links are undirected between pairs of them. All these pages are from 17 categories.

• Email-eu (Leskovec et al., 2007 ) is an Email communication network which illustrates the email communication relationships between researchers in a large European research institution. There are 1,005 researchers and 25,571 links between them. Department affiliations (42 in total) of the researchers are considered as labels to predict.

Baseline methods:

The compared baseline algorithms are listed below:

• Deepwalk (Perozzi et al., 2014) is an unsupervised graph embedding method which relies on the random walk and word2vec method. For each vertex, we take 80 random walks with length 40, and set window size as 10. Since deepwalk is unsupervised, we apply a logistic regression on the generated embeddings for node classification.

• Node2vec (Grover & Leskovec, 2016 ) is an improved graph embedding method based on deepwalk.

We set the window size as 10, the walk length as 80 and the number of walks for each node is set to 100. Similarly, the node2vec is unsupervised as well. We apply the same evaluation procedure on the embeddings of node2vec as what we did for deepwalk.

• Struc2vec (Ribeiro et al., 2017) chooses the window size as 10, the walking length as 80, the number of walks from each node as 10, and 5 iterations in total for SGD.

• GraphWave (Donnat et al., 2018) chooses the heat coefficient as 1000, the number of characteristic functions as 50, the number of Chebyshev approximations as 100, and the number of steps as 20.

• WYS (Watch-Your-Step) (Abu-El-Haija et al., 2017) chooses the learning rate as 0.2, the highest power of normalized adjacency matrix as 5, the regularization co-efficient as 0.1, and uses the "Log Graph Likelihood" as objective function.

• MMDW (Tu et al., 2016 ) is a semi-supervised learning framework of graph embedding which combines matrix decomposition and SVM classification. We tune the method multiple times and take 0.01 as the hyper-parameter η in the method which is recommended by the authors.

• Planetoid (Yang et al., 2016 ) is a semi-supervised learning framework. We set the batch size as 200, learning rate as 0.01, the batch size for label context loss as 200, and mute the node attributes as input while using softmax for the model output.

• GCN (Graph Convolutional Networks) (Kipf & Welling, 2016a) chooses the convolutional neural networks into the semi-supervised embedding learning of graph. We eliminate the node attributes for fairness as well.

• GAT (Graph Attention Networks) (Velickovic et al., 2017) chooses the learning rate as 0.005, the co-efficient of the regularization as 0.0005, and the number of hidden units as 64. To make the comparison fair, we mute the node attributes in the training of GAT as well.

Experiment setup and results For fair comparison, the dimension of representation vectors is chosen to be the same for all algorithms (the dimension is 64). The hyper-parameters are fine-tuned for all of them. The details of P 2 IR for multi-class case are as follows.

• Supervised Component: Softmax function is chosen to formulate our supervised component in equation 5 which is defined as σ :

R K → {z ∈ R K | K i=1 zi = 1, zi > 0}.

For an arbitrary embedding x ∈ R d , we have the probability term as P(y = j|x) = exp(w j x+b j ) K i exp(w i x+b i ) for such node to be predicted as class j, where (wj ∈ R d , bj ∈ R) is a classifier for class j. Therefore, the whole supervised component in equation 5 is -v∈V label K j yj log P(y = j|xv)+λwR(w), where R(w) is an L2 regularization for w and λw is chosen to be 10 -3 .

• Unsupervised embedding mapping Component: We design a two-layer NN with hidden dimension 64 to form the mapping from embeddings of neighbors to the target node and we also form a two-layer 1-to-1 NN with a 3 dimensional hidden layer to construct the matrix function for the adjacency matrix. We pre-process the matrix A with an eigenvalue decomposition where the procedure preserve the highest 1000 eigenvalues in default. The balance hyper-parameter λ1 is set to be 10 -3 . We take experiments on each data set and compare the performance among all baseline methods mentioned above. Since it is the multi-class classification scenario, we use Accuracy as the evaluation criterion. The percentage of labeled samples is chosen from 10% to 90% and the remaining samples are used for evaluation. All experiments are repeated for five times and we report the mean and standard deviation of their performance in the Table 1 . We highlight the best performance for each dataset with bold font style and the second best results with a "*". We can observe that in most cases, our method outperforms other methods.

4.2. COMPARISON ON HETEROGENEOUS GRAPHS:

We next conduct evaluation on heterogeneous graphs, where learned node embedding vectors are used for multi-label classification.

Datasets The used datasets include

• BlogCatalog (Wang et al., 2010) is a social media network with 55,814 users and according to the interests of users, they are classified into multiple overlapped groups. We take the five largest groups to evaluate the performance of methods. Users and tags are two types of nodes. The 5,413 tags are generated by users with their blogs as keywords. Therefore, tags are shared with different users and also have connections since some tags are generated from the same blogs. The number of edges between users, between tags and between users and tags are about 1.4M, 619K and 343K respectively. • DBLP (Ji et al., 2010) is an academic community network. Here we obtain a subset of the large network with two types of nodes, authors and key words from authors' publications. The generated subgraph includes 27K (authors) + 3.7K (key words) vertexes. The link between a pair of author indicates the coauthor relationships, the link between an author and a word means the word belongs to at least one publication of this author. There are 66,832 edges between pairs of authors and 338,210 edges between authors and words. Each node can have multiple labels out of four in total.

Baseline Methods To illustrate the validation of the performance of P 2 IR on heterogeneous graphs, we conduct the experiments on two stages: (1) comparing P 2 IR with Deepwalk (Perozzi et al., 2014) and node2vec (Grover & Leskovec, 2016) on the graphs by treating all nodes as the same type (P 2 IR with K = 1 in a homogeneous setting); (2) comparing P 2 IR with the state-of-the-art heterogeneous graph embedding method, metapath2vec (Dong et al., 2017) , in a heterogeneous setting. The hyper-parameters of the method are fine-tuned and metapath2vec++ is chosen as the option for the comparison.

Experiment Setup and Results:

For fair comparison, the dimension of representation vectors is chosen to be the same for all algorithms (the dimension is 64). We fine-tune the hyper-parameter for all of them. The details of P 2 IR for multi-label case are as follows.

• Supervised Component: Since it is a multi-label classification problem, each label can be treated as a binary classification problem. Therefore, we apply logistic regression for each label and for an arbitrary instance x and the i-th label yi, the supervised component is formulated as l(x, yi) = log(1 + exp(w i x + bi)) -yi(w i x + bi), where (wi ∈ R d , bi ∈ R) is the classifier for the i-th label. Therefore, the supervised component in equation 5 is defined as v∈V label i l(x, yi) + λwR(wi) and R(wi) is the regularization component for wi, where λw is chosen to be 10 -4 . • Unsupervised Embedding Mapping Component: We design a two-layes NN with a 64-dimensional hidden layer for each type of nodes with the types of nodes in its neighborhood to formulate the mapping from embedding of neighbors to the embedding of the target node. We also form a two-layer 1-to-1 NN wth a 3 dimensional hidden layer to construct the matrix function for the adjacency matrix A for the whole graph. We pre-process the matrix A with an eigenvalue decomposition by preserving the highest 1000 eigenvalues of magnitude in default. We denote the nodes to be classified as type 1 and the other type as type 2. The balance hyper-parameter [λ1, λ2] is set to be [0.2, 200] .

For the datasets DBLP and BlogCatalog, we carry out the experiments on each of them and compare the performance among all methods mentioned above. Since it is a multi-label classification task, we take f1-score(macro, micro) as the evaluation score for the comparison. The percentage of labeled samples is chosen from 10% to 90%, while the remaining samples are used for evaluation. We repeat all experiments for three times and report the mean and standard deviation of their performance in the Table 2 . We can observe that in most cases, P 2 IR in heterogeneous setting has the best performance. P 2 IR in homogeneous setting is better than deepwalk and node2vec in the same homogeneous setting, and is even better than metapath2vec++ in heterogeneous setting (achieving the second best results).

Overall, the superior performance of P 2 IR in Table 1 and 2 demonstrates the validity of our proposed universal graph embedding mechanism. 

5. CONCLUSION AND FUTURE WORK:

To summarize the whole work, we propose P 2 IR, a general graph embedding solution with the novel notion of partial permutation invariant set function, in principle that it can capture an arbitrary dependence between neighbors and automatically decide the significance of neighbor nodes at different distance for both homogeneous and heterogeneous graphs. We provide a theoretical guarantee for the effectiveness of the whole model. Through conducting extensive experimental evaluation, we show P 2 IR has better performance on both homogeneous and heterogeneous graphs, comparing to the stochastic trajectories based, matrix analytics based and graph neural network based state-of-the-art algorithms. For the future work, our model can be extended to more general cases, e.g., involving the rich content information out of graph neighborhood structures.

We let:

p(x 1 , x 2 , • • • , x K ) = 1 K k=1 (N k !) σ 1 ∈S 1 ,••• ,σ K ∈S K q([x 1 ] σ 1 , [x 2 ] σ 2 , • • • , [x K ] σ K )

and by the property of permutation invariant within each G k of the function f , we have that

sup |f (x1, x2, • • • , xK ) -p(x1, x2, • • • , xK )| = sup f (x1, x2, • • • , xK ) - 1 K k=1 (N k !) σ 1 ∈S 1 ,••• ,σ K ∈S K q([x1] σ 1 , [x2] σ 2 , • • • , [xK ] σ K ) = sup 1 K k=1 (N k !) σ 1 ∈S 1 ,••• ,σ K ∈S K f ([x1] σ 1 , • • • , [xK ] σ K ) - 1 K k=1 (N k !) σ 1 ∈S 1 ,••• ,σ K ∈S K q([x1] σ 1 , • • • , [xK ] σ K ) ≤ 1 K k=1 (N k !) σ 1 ∈S 1 ,••• ,σ K ∈S K sup f ([x1] σ 1 , [x2] σ 2 , • • • , [xK ] σ K ) -q([x1] σ 1 , [x2] σ 2 , • • • , [xK ] σ K ) ≤ 1 K k=1 (N k !) σ 1 ∈S 1 ,••• ,σ K ∈S K =

Therefore, we can see that the polynomial function p(x 1 , x 2 , • • • , x K ) is permutation invariant within each group and can closely approximate the function f

(x 1 , x 2 , • • • , x K ). Lemma 5.4. Suppose p : X → R is a real-valued polynomial in the form p(x 1,1 , x 1,2 , • • • , x 1,N1 G1 , • • • , x K,1 , x K,2 , • • • , x K,N K G K ),

which is permutation invariant within each group G k , k ∈ {1, 2, . . . , K}. Then, p can be represented as

p(x 1,1 , x 1,2 , • • • , x 1,N1 G1 , • • • , x K,1 , x K,2 , • • • , x K,N K G K ) = i=1 c i m λ i 1 1 m λ i 2 2 . . . m λ i K K

where c i is the rational coefficient, m

λ i K k denotes a monomial symmetric polynomial of variables x k,1 , x k,2 , • • • , x k,N k within group G k and λ i

K ∈ R n are some certain exponents for the monomial symmetric polynomial.

Proof. Suppose that the polynomial is expressed as a summation of monomials

p(x 1,1 , x 1,2 , • • • , x 1,N1 G1 , • • • , x K,1 , x K,2 , • • • , x K,N K G K ) = r c r N1 j=1 x α r 1,j 1,j N2 j=1 x α r 2,j 2,j , • • • , N K j=1 x α r K,j K,j

where α r k,j is the exponent of x k,j for the r-th monomial.

We consider the term c r

N1 j=1 x α r 1,j 1,j N2 j=1 x α r 2,j 2,j • • • N K j=1 x α r K,j

K,j for a certain r in the above summation. Since p(•) is partially symmetric within the group G 1 , then there must exist terms having exponents of permuted α r 1,j , ∀j ∈ {1, . . . , N 1 } on x 1,j while the other factors

c r N2 j=1 x α r 2,j 2,j • • • N K j=1 x α r K,j

K,j remain the same. (Otherwise, the polynomial is not permutationinvariant w.r.t. group G 1 .) By summing up those terms together, we get a term with a factor of monomial symmetric polynomial as c r m K . For all the remaining terms in the polynomial p(•), performing the same steps will lead to completion of our proof.

Example 5.5. p(x 1 1 , x 1 2 , x 2 1 , x 2 2 ) is a polynomial that is permutation invariant within each group, G 1 = {x 1 1 , x 1 2 } and G 2 = {x 2 1 , x 2 2 }. We let p(x 1,1 , x 1,2 , x 2,1 , x 2,2 ) =x 1,1 x 2 1,2 x 2,1 x 2 2,2 + x 2 1,1 x 1,2 x 2 2,1 x 2,2 + x 1,1 x 2 1,2 x 2 2,1 x 2,2 + x 2 1,1 x 1,2 x 2,1 x 2 2,2 + x 2 1,1 x 3 1,2 x 3 2,1 x 4 2,2 + x 3 1,1 x 2 1,2 x 4 2,1 x 3 2,2 + x 2 1,1 x 3 1,2 x 4 2,1 x 3 2,2 + x 3 1,1 x 2 1,2 x 3 2,1 x 4 2,2 .

It is easy to observe that p(x 1,1 , x 1,2 , x 2,1 , x 2,2 ) can be rewritten as p(x 1,1 , x 1,2 , x 2,1 , x 2,2 ) =(x 1,1 x 2 1,2 + x 2 1,1 x 1,2 )(x 2,1 x 2 2,2 + x 2 2,1 x 2,2 ) + (x 2 1,1 x 3 1,2 + x 3 1,1 x 2 1,2 )(x 3 2,1 x 4 2,2 + x 4 2,1 x 3 2,2 ) = m Lemma 5.6. For a symmetric polynomial p(x 1 , . . . , x n ) of n variables, it can be expressed by a polynomial in the power sum symmetric polynomials p k (x 1 , . . . , x n ) for 1 ≤ k ≤ n with rational coefficients.

Proof. This lemma is a direct result of the fact that p 1 , p 2 , . . . , p n are algebraically independent and the ring of symmetric polynomials with rational coefficients can be generated as a Q-algebra, i.e. Q[p 1 , p 2 , . . . , p n ]. (Macdonald, 1998; Stanley, 2001) This lemma can also be easily proved by the combination of the fundamental theorem of symmetric polynomials and newton's identities.

Proof of Theorem 3.1 Proof. By Corollary 5.3.1, for any function f : X → R that are permutation-invariant w.r.t. the variables within each group G k , ∀k ∈ {1, 2, . . . , K}, which is in the form

f (x 1,1 , x 1,2 , • • • , x 1,N1 G1 , x 2,1 , x 2,2 , • • • , x 2,N2 G2 , • • • , x K,1 , x K,2 , • • • , x K,N K G K ),

we can always find a polynomial function p : X → R that are also permutation-invariant w.r.t. the variables within each group G k to approximate f closely in a given small error tolerance .

Here we first define the function g k : R → R N k in the following form,

g k (x k,n ) =        x k,n x 2 k,n x 3 k,n . . . x N k k,n        which thus leads to N k n=1 g k (x k,n ) =         N k n=1 x k,n N k n=1 x 2 k,n N k n=1 x 3 k,n . . . N k n=1 x N k k,n         =       p 1 (x k,1 , • • • , x k,N k ) p 2 (x k,1 , • • • , x k,N k ) p 3 (x k,1 , • • • , x k,N k ) . . . p N k (x k,1 , • • • , x k,N k )      

Therefore, we generate a sequence of power sums basis by k is a symmetric polynomial, which thus can be rewritten as a polynomial expression of power sum basis,

p 1 (x k,1 , • • • , x k,N k ), p 2 (x k,1 , • • • , x k,N k ), • • • , p N k (x k,1 , • • • , x k,N k ).

which has been generated by

N k n=1 g k (x k,n ).

:



Figures and Tables:

. Based on this term, we consider that the polynomial p(•) is also permuted invariant within G 2 , which implies that there must exist terms having exponents of permuted α r 2,j , ∀j ∈ {1, . . . , N 2 } on x 2,j while the other factors c r m remain the same. Therefore, adding up all those terms together, we have c r m K,j . Carrying out the above procedures recursively, we can eventually have c r m

(x k,n ). By Lemma 5.4, the polynomial function p(x 1,1 , x 1,2 , • • • , x 1,N1 , • • • , x K,1 , x K,2 , • • • , x K,N K ) can be expressed as i=1 c i m



Table content: <table><tr><td/><td/><td colspan="7">: Accuracy (%) of multi-class classification experiments in homogeneous graphs</td><td/><td/></tr><tr><td/><td>training%</td><td>10.00%</td><td>20.00%</td><td>30.00%</td><td>40.00%</td><td>50.00%</td><td>60.00%</td><td>70.00%</td><td>80.00%</td><td>90.00%</td></tr><tr><td/><td>deepwalk</td><td>72.73 ±2.02</td><td>75.50 ±1.12</td><td>76.72 ±0.99</td><td>77.34 ±0.52</td><td>78.38 ±0.82</td><td>78.41 ±1.47</td><td>78.82 ±1.12</td><td>79.15 ±1.04</td><td>79.70 ±2.32</td></tr><tr><td>Cora</td><td>node2vec GraphWave</td><td>73.46 ±0.87 30.27 ±0.11</td><td>75.70 ±1.33 30.44 ±0.29</td><td>76.45 ±1.11 30.41 ±0.30</td><td>78.07 ±1.03 30.11 ±1.02</td><td>78.42 ±1.14 30.47 ±1.93</td><td>78.65 ±1.46 30.29 ±0.59</td><td>78.94 ±1.43 30.47 ±0.45</td><td>79.08 ±1.44 31.09 ±0.73</td><td>81.04 ±0.99 31.19 ±3.15</td></tr><tr><td/><td>struc2vec</td><td>26.89 ±0.71</td><td>28.47 ±0.32</td><td>29.69 ±0.39</td><td>29.53 ±1.02</td><td>30.06 ±2.01</td><td>30.01 ±0.88</td><td>30.34 ±0.59</td><td>31.09 ±0.66</td><td>31.19 ±3.09</td></tr><tr><td/><td>WYS</td><td>70.24 ±1.55</td><td>72.82 ±0.99</td><td>74.17 ±1.00</td><td>74.79 ±0.30</td><td>75.51 ±1.37</td><td>75.18 ±0.92</td><td>75.96 ±1.29</td><td>76.01 ±1.04</td><td>77.11 ±2.53</td></tr><tr><td/><td>MMDW</td><td>74.88 ±0.23 *</td><td>79.18 ±0.10 *</td><td>81.20 ±0.11 *</td><td>82.19 ±0.25 *</td><td>83.10 ±0.41 *</td><td>84.62 ±0.09 *</td><td>85.54 ±0.44 *</td><td>85.27 ±0.22 *</td><td>87.82 ±0.37 *</td></tr><tr><td/><td>planetoid</td><td>40.87 ±15.61</td><td>52.63 ±0.44</td><td>52.23 ±1.47</td><td>52.07 ±0.55</td><td>53.06 ±1.99</td><td>51.86 ±1.90</td><td>51.91 ±1.09</td><td>51.29 ±2.76</td><td>54.32 ±3.48</td></tr><tr><td/><td>GCN</td><td>59.10 ±1.48</td><td>67.08 ±1.98</td><td>73.06 ±1.07</td><td>75.61 ±1.02</td><td>79.08 ±1.23</td><td>80.11 ±1.15</td><td>82.61 ±1.00</td><td>84.29 ±1.88</td><td>85.18 ±1.66</td></tr><tr><td/><td>GAT</td><td>29.57 ±2.11</td><td>30.49 ±0.67</td><td>29.91 ±0.58</td><td>29.85 ±0.81</td><td>30.44 ±0.78</td><td>30.22 ±1.73</td><td>30.53 ±0.79</td><td>30.74 ±2.33</td><td>30.55 ±1.41</td></tr><tr><td/><td>P 2 IR</td><td>76.28 ±1.35</td><td>80.10 ±1.36</td><td>82.95 ±1.44</td><td>83.99 ±1.14</td><td>85.13 ±0.71</td><td>85.95 ±0.81</td><td>86.87 ±0.97</td><td>87.84 ±0.35</td><td>88.59 ±1.58</td></tr><tr><td/><td>deepwalk</td><td>46.52 ±1.45</td><td>49.18 ±0.49</td><td>49.28 ±0.72</td><td>50.41 ±0.87</td><td>50.43 ±1.27</td><td>50.79 ±0.99</td><td>49.63 ±0.75</td><td>50.06 ±1.89</td><td>52.33 ±0.89</td></tr><tr><td>Citeseer</td><td>node2vec GraphWave</td><td>46.38 ±1.32 18.03 ±0.30</td><td>47.65 ±0.88 18.03 ±0.28</td><td>48.68 ±0.71 17.96 ±0.17</td><td>48.12 ±0.64 18.40 ±0.46</td><td>48.37 ±1.14 18.14 ±0.70</td><td>48.13 ±0.98 17.67 ±1.06</td><td>47.67 ±1.38 17.76 ±0.35</td><td>48.55 ±1.11 18.13 ±1.91</td><td>48.82 ±2.46 19.58 ±1.92</td></tr></table>

F1-score (macro, micro) (%) of multi-label classification in heterogeneous graphs

Table content: <table><tr><td/><td>training%</td><td>10.00%</td><td>20.00%</td><td>30.00%</td><td>40.00%</td><td>50.00%</td><td>60.00%</td><td>70.00%</td><td>80.00%</td><td>90.00%</td></tr><tr><td>BlogCatalog (macro)</td><td>deepwalk node2vec metapath2vec++ P 2 IR (Homogeneous) P 2 IR</td><td>45.13 ±0.68 45.78 ±0.68 37.46 ±0.61 47.63 ±3.16 * 49.65</td><td>44.64 ±0.21 45.42 ±0.30 36.72 ±0.36 50.99 ±0.09 * 51.47</td><td>44.52 ±0.42 45.28 ±0.32 36.69 ±0.29 51.70 ±0.19 * 52.69</td><td>44.64 ±0.23 45.41 ±0.18 36.58 ±0.28 50.04 ±1.90 * 53.37</td><td>44.32 ±0.21 45.17 ±0.20 36.74 ±0.17 50.60 ±1.73 * 53.73</td><td>44.36 ±0.46 45.19 ±0.36 36.90 ±0.33 50.34 ±0.55 * 53.97</td><td>44.78 ±0.48 45.57 ±0.13 36.89 ±0.32 52.20 ±1.11 * 53.83</td><td>44.33 ±0.62 45.04 ±0.31 36.42 ±0.41 51.88 ±1.08 * 54.07</td><td>44.49 ±0.86 44.96 ±0.55 36.16 ±0.98 51.36 ±0.26 * 53.36</td></tr><tr><td/><td>(Heterogeneous)</td><td>±0.63</td><td>±0.40</td><td>±0.24</td><td>±0.45</td><td>±0.01</td><td>±0.43</td><td>±0.62</td><td>±0.40</td><td>±0.84</td></tr><tr><td>BlogCatalog (micro)</td><td>deepwalk node2vec metapath2vec++ P 2 IR (Homogeneous)</td><td>47.93 ±0.48 48.52 ±0.50 40.90 ±0.34 50.75 ±2.74 *</td><td>47.36 ±0.15 48.20 ±0.18 40.06 ±0.21 54.26 ±0.12 *</td><td>47.25 ±0.45 48.01 ±0.31 40.10 ±0.25 55.08 ±0.08 *</td><td>47.30 ±0.19 48.18 ±0.17 39.97 ±0.22 53.41 ±1.92 *</td><td>47.07 ±0.16 47.97 ±0.25 40.04 ±0.17 53.88 ±1.70 *</td><td>47.09 ±0.48 48.04 ±0.39 40.22 ±0.29 53.57 ±0.50 *</td><td>47.39 ±0.49 48.22 ±0.15 40.21 ±0.22 55.36 ±1.30 *</td><td>47.02 ±0.72 47.83 ±0.32 39.82 ±0.44 54.93 ±1.07 *</td><td>47.27 ±0.82 47.95 ±0.55 39.66 ±0.82 55.03 ±0.52 *</td></tr><tr><td/><td>P 2 IR</td><td>53.06</td><td>54.77</td><td>55.93</td><td>56.41</td><td>56.86</td><td>57.28</td><td>57.13</td><td>57.43</td><td>56.98</td></tr><tr><td/><td>(Heterogeneous)</td><td>±0.45</td><td>±0.21</td><td>±0.17</td><td>±0.31</td><td>±0.06</td><td>±0.38</td><td>±0.43</td><td>±0.14</td><td>±0.53</td></tr><tr><td>DBLP (macro)</td><td>Deepwalk Node2vec Metapath2vec++</td><td>74.48 ±0.34 * 73.37 ±0.24 74.82 ±0.30</td><td>74.87 ±0.14 73.94 ±0.11 75.27 ±0.08</td><td>74.95 ±0.15 74.00 ±0.18 75.55 ±0.12</td><td>75.10 ±0.22 74.25 ±0.23 75.63 ±0.27</td><td>75.07 ±0.22 74.06 ±0.31 75.53 ±0.22</td><td>75.44 ±0.22 74.52 ±0.21 75.92 ±0.24</td><td>75.33 ±0.33 74.52 ±0.35 75.92 ±0.42</td><td>74.75 ±0.31 74.32 ±0.26 75.56 ±0.36</td><td>75.36 ±0.73 74.55 ±0.57 76.09 ±0.46</td></tr><tr><td/><td>P 2 IR (Homogeneous)</td><td>72.51 ±0.91</td><td>76.89 ±0.06 *</td><td>79.91 ±0.09 *</td><td>82.14 ±0.26 *</td><td>84.60 ±0.42 *</td><td>86.34 ±0.52 *</td><td>87.49 ±0.31 *</td><td>88.21 ±0.25 *</td><td>89.61 ±0.58 *</td></tr><tr><td/><td>P 2 IR</td><td>74.06</td><td>78.43</td><td>81.00</td><td>83.18</td><td>84.95</td><td>86.91</td><td>88.30</td><td>89.18</td><td>90.37</td></tr><tr><td/><td>(Heterogeneous)</td><td>±0.37</td><td>±0.61</td><td>±0.19</td><td>±0.16</td><td>±0.22</td><td>±0.54</td><td>±0.29</td><td>±0.17</td><td>±0.38</td></tr><tr><td>DBLP (micro)</td><td>deepwalk node2vec metapath2vec++</td><td>76.65 ±0.25 75.65 ±0.16 76.98 ±0.21 *</td><td>77.03 ±0.19 76.21 ±0.12 77.38 ±0.10</td><td>77.15 ±0.15 76.30 ±0.16 77.66 ±0.08</td><td>77.21 ±0.15 76.48 ±0.18 77.70 ±0.21</td><td>77.20 ±0.17 76.33 ±0.25 77.61 ±0.18</td><td>77.60 ±0.20 76.82 ±0.22 78.04 ±0.18</td><td>77.44 ±0.31 76.76 ±0.33 77.95 ±0.39</td><td>76.87 ±0.35 76.44 ±0.34 77.54 ±0.36</td><td>77.54 ±0.72 76.73 ±0.55 78.02 ±0.47</td></tr><tr><td/><td>P 2 IR (Homogeneous)</td><td>74.37 ±0.88</td><td>78.52 ±0.09 *</td><td>81.47 ±0.11 *</td><td>83.56 ±0.28 *</td><td>85.81 ±0.42 *</td><td>87.51 ±0.54 *</td><td>88.44 ±0.27 *</td><td>89.16 ±0.22 *</td><td>90.54 ±0.50 *</td></tr><tr><td/><td>P 2 IR</td><td>77.06</td><td>80.67</td><td>82.87</td><td>84.75</td><td>86.29</td><td>88.09</td><td>89.27</td><td>90.11</td><td>91.22</td></tr><tr><td/><td>(Heterogeneous)</td><td>±0.29</td><td>±0.45</td><td>±0.13</td><td>±0.16</td><td>±0.22</td><td>±0.47</td><td>±0.25</td><td>±0.13</td><td>±0.43</td></tr></table>

Peer review (iclr2019):
 This paper proposed a heterogeneous graph embedding method P^2IR. The author(s) first argued that such an embedding should be invariant to partial permutations of nodes. Then the authors gave a general formulation of such an embedding in theorem 3.1. Then the authors instantiated this general formulation by a neural network parametrization, which can be optimized based on the L^2 loss and a supervised regularizer. The method is tested against graph embedding methods that do not need node attributes (in GCN the authors "eliminated" the node attributes) on semi-supervised node classification tasks, showing a significant improvement. My main criticism is that the authors did not clarify or put any efforts on solve the high computational complexity. The proposed method needs to perform a spectral decomposition of the adjacency matrix, which has cubic complexity. This is unacceptable, making the method less useful for real networks. Furthermore, to optimize the embedding using SGD requires graph Fourier transformations that have quadratic complexity. In section 3.3, the exact complexity should be given, without which the technique is incomplete. An important reference "Graph Attention Networks. P. Veličković et al. 2018." is missing, which has the similar idea to automatically learn the neighborhood proximities. It should be cited as this is a key idea to motivate the paper. The presentation quality is not satisfactory. For example, in page 3, f() has K matrix arguments, then in page 4 theorem 3.1, f() takes KN arguments. Please make it consistent. In page 5, the formulations from eq.(3) to eq.(5) can be further unified and simplified. From eq.(3) to eq.(4) is not straightforward and need more explanations. If you use .mathcal{R} as the embedding, it should appear in eq.(4) to be consistent. Table 1 has no contents. In the experimental results, the performance of GCN with node attributes should be given for completeness (although the comparison is less fair). A related question is how to incorporate node attributes in your framework? In the heterogeneous experiments, for completeness, the authors are suggested to compare against a heterogeneous version of GCN (again, with and without node attributes) such as "Modeling Relational Data with Graph Convolutional Networks. Schlichtkrull et al. 2017." The paper is longer than the recommended length.