Node Copying: A Random Graph Model for Effective Graph Sampling
- URL: http://arxiv.org/abs/2208.02435v1
- Date: Thu, 4 Aug 2022 04:04:49 GMT
- Title: Node Copying: A Random Graph Model for Effective Graph Sampling
- Authors: Florence Regol, Soumyasundar Pal, Jianing Sun, Yingxue Zhang, Yanhui
Geng, Mark Coates
- Abstract summary: We introduce the node copying model for constructing a distribution over graphs.
We show the usefulness of the copying model in three tasks.
We employ our proposed model to mitigate the effect of adversarial attacks on the graph topology.
- Score: 35.957719744856696
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: There has been an increased interest in applying machine learning techniques
on relational structured-data based on an observed graph. Often, this graph is
not fully representative of the true relationship amongst nodes. In these
settings, building a generative model conditioned on the observed graph allows
to take the graph uncertainty into account. Various existing techniques either
rely on restrictive assumptions, fail to preserve topological properties within
the samples or are prohibitively expensive for larger graphs. In this work, we
introduce the node copying model for constructing a distribution over graphs.
Sampling of a random graph is carried out by replacing each node's neighbors by
those of a randomly sampled similar node. The sampled graphs preserve key
characteristics of the graph structure without explicitly targeting them.
Additionally, sampling from this model is extremely simple and scales linearly
with the nodes. We show the usefulness of the copying model in three tasks.
First, in node classification, a Bayesian formulation based on node copying
achieves higher accuracy in sparse data settings. Second, we employ our
proposed model to mitigate the effect of adversarial attacks on the graph
topology. Last, incorporation of the model in a recommendation system setting
improves recall over state-of-the-art methods.
Related papers
- Deep Generative Models for Subgraph Prediction [10.56335881963895]
This paper introduces subgraph queries as a new task for deep graph learning.
Subgraph queries jointly predict the components of a target subgraph based on evidence that is represented by an observed subgraph.
We utilize a probabilistic deep Graph Generative Model to answer subgraph queries.
arXiv Detail & Related papers (2024-08-07T19:24:02Z) - Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data.
The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
arXiv Detail & Related papers (2024-01-12T17:57:07Z) - 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) - DiGress: Discrete Denoising diffusion for graph generation [79.13904438217592]
DiGress is a discrete denoising diffusion model for generating graphs with categorical node and edge attributes.
It achieves state-of-the-art performance on molecular and non-molecular datasets, with up to 3x validity improvement.
It is also the first model to scale to the large GuacaMol dataset containing 1.3M drug-like molecules.
arXiv Detail & Related papers (2022-09-29T12:55:03Z) - Similarity-aware Positive Instance Sampling for Graph Contrastive
Pre-training [82.68805025636165]
We propose to select positive graph instances directly from existing graphs in the training set.
Our selection is based on certain domain-specific pair-wise similarity measurements.
Besides, we develop an adaptive node-level pre-training method to dynamically mask nodes to distribute them evenly in the graph.
arXiv Detail & Related papers (2022-06-23T20:12:51Z) - Neighborhood Random Walk Graph Sampling for Regularized Bayesian Graph
Convolutional Neural Networks [0.6236890292833384]
In this paper, we propose a novel algorithm called Bayesian Graph Convolutional Network using Neighborhood Random Walk Sampling (BGCN-NRWS)
BGCN-NRWS uses a Markov Chain Monte Carlo (MCMC) based graph sampling algorithm utilizing graph structure, reduces overfitting by using a variational inference layer, and yields consistently competitive classification results compared to the state-of-the-art in semi-supervised node classification.
arXiv Detail & Related papers (2021-12-14T20:58:27Z) - Order Matters: Probabilistic Modeling of Node Sequence for Graph
Generation [18.03898476141173]
A graph generative model defines a distribution over graphs.
We derive the exact joint probability over the graph and the node ordering of the sequential process.
We train graph generative models by maximizing this bound, without using the ad-hoc node orderings of previous methods.
arXiv Detail & Related papers (2021-06-11T06:37:52Z) - Line Graph Neural Networks for Link Prediction [71.00689542259052]
We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications.
In this formalism, a link prediction problem is converted to a graph classification task.
We propose to seek a radically different and novel path by making use of the line graphs in graph theory.
In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
arXiv Detail & Related papers (2020-10-20T05:54:31Z) - Non-Parametric Graph Learning for Bayesian Graph Neural Networks [35.88239188555398]
We propose a novel non-parametric graph model for constructing the posterior distribution of graph adjacency matrices.
We demonstrate the advantages of this model in three different problem settings: node classification, link prediction and recommendation.
arXiv Detail & Related papers (2020-06-23T21:10:55Z) - Graph Pooling with Node Proximity for Hierarchical Representation
Learning [80.62181998314547]
We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology.
Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
arXiv Detail & Related papers (2020-06-19T13:09:44Z)
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.