Node Copying: A Random Graph Model for Effective Graph Sampling
This work addresses graph uncertainty for applications like node classification and recommendation systems, offering a scalable and effective sampling method, though it is incremental as it builds on existing generative models.
The paper tackles the problem of graph uncertainty in machine learning by introducing the node copying model, a generative approach for sampling graphs that preserves structural properties and scales linearly with nodes, achieving higher accuracy in node classification with sparse data, mitigating adversarial attacks, and improving recall in recommendation systems.
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.