Ego-based Entropy Measures for Structural Representations

• URL: http://arxiv.org/abs/2003.00553v1
• Date: Sun, 1 Mar 2020 18:58:00 GMT
• Title: Ego-based Entropy Measures for Structural Representations
• Authors: George Dasoulas, Giannis Nikolentzos, Kevin Scaman, Aladin Virmaux, Michalis Vazirgiannis
• Abstract summary: VNEstruct is a simple approach for generating low-dimensional structural node embeddings. The proposed approach focuses on the local neighborhood of each node and employs the Von Neumann entropy. On graph classification tasks, we suggest the utilization of the generated structural embeddings for the transformation of an attributed graph structure into a set of augmented node attributes.
• Score: 42.37368082564481
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In complex networks, nodes that share similar structural characteristics often exhibit similar roles (e.g type of users in a social network or the hierarchical position of employees in a company). In order to leverage this relationship, a growing literature proposed latent representations that identify structurally equivalent nodes. However, most of the existing methods require high time and space complexity. In this paper, we propose VNEstruct, a simple approach for generating low-dimensional structural node embeddings, that is both time efficient and robust to perturbations of the graph structure. The proposed approach focuses on the local neighborhood of each node and employs the Von Neumann entropy, an information-theoretic tool, to extract features that capture the neighborhood's topology. Moreover, on graph classification tasks, we suggest the utilization of the generated structural embeddings for the transformation of an attributed graph structure into a set of augmented node attributes. Empirically, we observe that the proposed approach exhibits robustness on structural role identification tasks and state-of-the-art performance on graph classification tasks, while maintaining very high computational speed.

Related papers

• Learning to Model Graph Structural Information on MLPs via Graph Structure Self-Contrasting [50.181824673039436]
  We propose a Graph Structure Self-Contrasting (GSSC) framework that learns graph structural information without message passing. The proposed framework is based purely on Multi-Layer Perceptrons (MLPs), where the structural information is only implicitly incorporated as prior knowledge. It first applies structural sparsification to remove potentially uninformative or noisy edges in the neighborhood, and then performs structural self-contrasting in the sparsified neighborhood to learn robust node representations.
  arXiv  Detail & Related papers  (2024-09-09T12:56:02Z)
• Graph Embedding with Hierarchical Attentive Membership [35.998704625736394]
  A latent hierarchical grouping of nodes exists in a global perspective, where each node manifests its membership to a specific group. Most prior works ignore such latent groups and nodes' membership to different groups, not to mention the hierarchy, when modeling the neighborhood structure. We propose a novel hierarchical attentive membership model for graph embedding, where the latent memberships for each node are dynamically discovered based on its neighboring context.
  arXiv  Detail & Related papers  (2021-10-31T22:00:48Z)
• Local, global and scale-dependent node roles [3.1473798197405944]
  This paper re-examines the concept of node equivalences like structural equivalence or automorphic equivalence. We show how already "shallow" roles of depth 3 or 4 carry sufficient information to perform node classification tasks with high accuracy.
  arXiv  Detail & Related papers  (2021-05-26T14:54:26Z)
• Ego-based Entropy Measures for Structural Representations on Graphs [35.55543331773255]
  VNEstruct is a simple approach, based on entropy measures of the neighborhood's topology, for generating low-dimensional structural representations. VNEstruct can achieve state-of-the-art performance on graph classification, without incorporating the graph structure information in the optimization.
  arXiv  Detail & Related papers  (2021-02-17T12:55:50Z)
• Hierarchical Graph Capsule Network [78.4325268572233]
  We propose hierarchical graph capsule network (HGCN) that can jointly learn node embeddings and extract graph hierarchies. To learn the hierarchical representation, HGCN characterizes the part-whole relationship between lower-level capsules (part) and higher-level capsules (whole)
  arXiv  Detail & Related papers  (2020-12-16T04:13:26Z)
• Node Similarity Preserving Graph Convolutional Networks [51.520749924844054]
  Graph Neural Networks (GNNs) explore the graph structure and node features by aggregating and transforming information within node neighborhoods. We propose SimP-GCN that can effectively and efficiently preserve node similarity while exploiting graph structure. We validate the effectiveness of SimP-GCN on seven benchmark datasets including three assortative and four disassorative graphs.
  arXiv  Detail & Related papers  (2020-11-19T04:18:01Z)
• GAGE: Geometry Preserving Attributed Graph Embeddings [34.25102483600248]
  This paper presents a novel approach for node embedding in attributed networks. It preserves the distances of both the connections and the attributes. An effective and lightweight algorithm is developed to tackle the learning task.
  arXiv  Detail & Related papers  (2020-11-03T02:07:02Z)
• Graph Structural-topic Neural Network [35.27112594356742]
  Graph Convolutional Networks (GCNs) achieved tremendous success by effectively gathering local features for nodes. In this paper, we propose Graph Structural-topic Neural Network, abbreviated GraphSTONE, a GCN model that utilizes topic models of graphs. We design multi-view GCNs to unify node features and structural topic features and utilize structural topics to guide the aggregation.
  arXiv  Detail & Related papers  (2020-06-25T09:47:21Z)
• Graph Neural Networks with Composite Kernels [60.81504431653264]
  We re-interpret node aggregation from the perspective of kernel weighting. We present a framework to consider feature similarity in an aggregation scheme. We propose feature aggregation as the composition of the original neighbor-based kernel and a learnable kernel to encode feature similarities in a feature space.
  arXiv  Detail & Related papers  (2020-05-16T04:44:29Z)
• Progressive Graph Convolutional Networks for Semi-Supervised Node Classification [97.14064057840089]
  Graph convolutional networks have been successful in addressing graph-based tasks such as semi-supervised node classification. We propose a method to automatically build compact and task-specific graph convolutional networks.
  arXiv  Detail & Related papers  (2020-03-27T08:32:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.