GraphDCA -- a Framework for Node Distribution Comparison in Real and Synthetic Graphs

• URL: http://arxiv.org/abs/2202.03884v2
• Date: Wed, 9 Feb 2022 07:50:07 GMT
• Title: GraphDCA -- a Framework for Node Distribution Comparison in Real and Synthetic Graphs
• Authors: Ciwan Ceylan, Petra Poklukar, Hanna Hultin, Alexander Kravchenko, Anastasia Varava, Danica Kragic
• Abstract summary: We argue that when comparing two graphs, the distribution of node structural features is more informative than global graph statistics. We present GraphDCA - a framework for evaluating similarity between graphs based on the alignment of their respective node representation sets.
• Score: 72.51835626235368
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We argue that when comparing two graphs, the distribution of node structural features is more informative than global graph statistics which are often used in practice, especially to evaluate graph generative models. Thus, we present GraphDCA - a framework for evaluating similarity between graphs based on the alignment of their respective node representation sets. The sets are compared using a recently proposed method for comparing representation spaces, called Delaunay Component Analysis (DCA), which we extend to graph data. To evaluate our framework, we generate a benchmark dataset of graphs exhibiting different structural patterns and show, using three node structure feature extractors, that GraphDCA recognizes graphs with both similar and dissimilar local structure. We then apply our framework to evaluate three publicly available real-world graph datasets and demonstrate, using gradual edge perturbations, that GraphDCA satisfyingly captures gradually decreasing similarity, unlike global statistics. Finally, we use GraphDCA to evaluate two state-of-the-art graph generative models, NetGAN and CELL, and conclude that further improvements are needed for these models to adequately reproduce local structural features.

Related papers

• GDM: Dual Mixup for Graph Classification with Limited Supervision [27.8982897698616]
  Graph Neural Networks (GNNs) require a large number of labeled graph samples to obtain good performance on the graph classification task. The performance of GNNs degrades significantly as the number of labeled graph samples decreases. We propose a novel mixup-based graph augmentation method to generate new labeled graph samples.
  arXiv  Detail & Related papers  (2023-09-18T20:17:10Z)
• GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
  We consider the problem of modelling high-dimensional distributions and generating new examples of data with complex relational feature structure coherent with a graph skeleton. The model we propose tackles the problem of generating the data features constrained by the specific graph structure of each data point by splitting the task into two phases. In the first it models the distribution of features associated with the nodes of the given graph, in the second it complements the edge features conditionally on the node features.
  arXiv  Detail & Related papers  (2022-12-01T11:49:07Z)
• Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
  This paper focuses on creating a small graph to represent the original graph, so that GNNs trained on the size-reduced graph can make accurate predictions. We view the original graph as a distribution of receptive fields and aim to synthesize a small graph whose receptive fields share a similar distribution.
  arXiv  Detail & Related papers  (2022-06-28T02:10:05Z)
• CGMN: A Contrastive Graph Matching Network for Self-Supervised Graph Similarity Learning [65.1042892570989]
  We propose a contrastive graph matching network (CGMN) for self-supervised graph similarity learning. We employ two strategies, namely cross-view interaction and cross-graph interaction, for effective node representation learning. We transform node representations into graph-level representations via pooling operations for graph similarity computation.
  arXiv  Detail & Related papers  (2022-05-30T13:20:26Z)
• Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
  We propose a joint emphgraph learning and matching network, named GLAM, to explore reliable graph structures for boosting graph matching. The proposed method is evaluated on three popular visual matching benchmarks (Pascal VOC, Willow Object and SPair-71k) It outperforms previous state-of-the-art graph matching methods by significant margins on all benchmarks.
  arXiv  Detail & Related papers  (2021-09-01T08:24:02Z)
• Generating the Graph Gestalt: Kernel-Regularized Graph Representation Learning [47.506013386710954]
  A complete scientific understanding of graph data should address both global and local structure. We propose a joint model for both as complementary objectives in a graph VAE framework. Our experiments demonstrate a significant improvement in the realism of the generated graph structures, typically by 1-2 orders of magnitude of graph structure metrics.
  arXiv  Detail & Related papers  (2021-06-29T10:48:28Z)
• A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
  We propose a robust framework for adversarial graph embedding, named AGE. AGE generates the fake neighbor nodes as the enhanced negative samples from the implicit distribution. Based on this framework, we propose three models to handle three types of graph data.
  arXiv  Detail & Related papers  (2021-05-22T07:05:48Z)
• Graph Partitioning and Graph Neural Network based Hierarchical Graph Matching for Graph Similarity Computation [5.710312846460821]
  Graph similarity aims to predict a similarity score between one pair of graphs to facilitate downstream applications. We propose a graph partitioning and graph neural network-based model, called PSimGNN, to effectively resolve this issue. PSimGNN outperforms state-of-the-art methods in graph similarity computation tasks using approximate Graph Edit Distance (GED) as the graph similarity metric.
  arXiv  Detail & Related papers  (2020-05-16T15:01:58Z)

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.