PINE Universal Deep Embedding for Graph Nodes via Partial Permutation Invariant Set Functions
ABSTARCT :
Graph node embedding aims at learning a vector representation for all nodes given a graph. It is a central problem in many machine learning tasks (e.g., node classification, recommendation, community detection). The key problem in graph node embedding lies in how to define the dependence to neighbors. Existing approaches specify (either explicitly or implicitly) certain dependencies on neighbors, which may lead to loss of subtle but important structural information within the graph and other dependencies among neighbors. This intrigues us to ask the question: can we design a model to give the adaptive flexibility of dependencies to each node’s neighborhood. In this paper, we propose a novel graph node embedding method (named PINE) via a novel notion of partial permutation invariant set function, to capture any possible dependence. Our method 1) can learn an arbitrary form of the representation function from the neighborhood, without losing any potential dependence structures, and 2) is applicable to both homogeneous and heterogeneous graph embedding, the latter of which is challenged by the diversity of node types. Furthermore, we provide theoretical guarantee for the representation capability of our method for general homogeneous and heterogeneous graphs. Empirical evaluation results on benchmark data sets show that our proposed PINE method outperforms the state-of-the-art approaches on producing node vectors for various learning tasks of both homogeneous and heterogeneous graphs.
EXISTING SYSTEM :
? Network embedding aims to preserve vertex similarity in an embedding space.
? Existing approaches usually define the similarity by direct links or common neighborhoods between nodes, i.e. structural equivalence.
? Regular equivalence is defined in a recursive way that two regularly equivalent vertexes have network neighbors which are also regularly equivalent.
? Most of the existing network embedding methods are developed along the line of preserving observed pair-wise similarity and structural equivalence.
DISADVANTAGE :
? Both deepwalk and node2vec are graph embedding methods to solve the node embedding problem.
? They convert the graph structures into a sequential context format with random walk.
? Although both of PINE and GIN study the neighborhood’s embedding construction strategy, they are formulated in different problem settings. GIN focuses on solving the Isomorphism of graphs and obtaining the MLP formulation of the embedding generation.
? This is a joint optimization problem: both the embedding vectors x v ’s and the embedding functions are jointly optimized.
PROPOSED SYSTEM :
• A set of centralities have been proposed to study how to capture the structural information better. Since each of them only captures one aspect of structural information, a certain centrality cannot well support different networks and applications.
• In addition, the hand-crafted manner of designing centrality measures makes them less comprehensive to incorporate regular equivalence related information.
• Struc2vec learns latent representations for the structural identity of nodes. Due to its high computational complexity, we use the combination of all optimizations proposed in the paper for large networks.
ADVANTAGE :
? GIN learns the graph embedding by aggregating all the embedding vectors for all nodes in a graph.
? Therefore, GIN can be utilized to compute the node embedding as well although they emphasize the performance on graph classification empirically.
? We take the five largest groups to evaluate the performance of methods. Users and tags are two types of nodes.
? These heterogeneous graph datasets were introduced in Graph Transformer Networks (GTN) to show the performance on heterogeneous graph node classification performance. For the ACM, it is a citation network. The learning goal is to distinguish the categories of papers which are presented as nodes in the graph.
|