Unveiling the Sampling Density in Non-Uniform Geometric Graphs

• URL: http://arxiv.org/abs/2210.08219v1
• Date: Sat, 15 Oct 2022 08:01:08 GMT
• Title: Unveiling the Sampling Density in Non-Uniform Geometric Graphs
• Authors: Raffaele Paolino, Aleksandar Bojchevski, Stephan G\"unnemann, Gitta Kutyniok, Ron Levie
• Abstract summary: We consider graphs as geometric graphs: nodes are randomly sampled from an underlying metric space, and any pair of nodes is connected if their distance is less than a specified neighborhood radius. In a social network communities can be modeled as densely sampled areas, and hubs as nodes with larger neighborhood radius. We develop methods to estimate the unknown sampling density in a self-supervised fashion.
• Score: 69.93864101024639
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A powerful framework for studying graphs is to consider them as geometric graphs: nodes are randomly sampled from an underlying metric space, and any pair of nodes is connected if their distance is less than a specified neighborhood radius. Currently, the literature mostly focuses on uniform sampling and constant neighborhood radius. However, real-world graphs are likely to be better represented by a model in which the sampling density and the neighborhood radius can both vary over the latent space. For instance, in a social network communities can be modeled as densely sampled areas, and hubs as nodes with larger neighborhood radius. In this work, we first perform a rigorous mathematical analysis of this (more general) class of models, including derivations of the resulting graph shift operators. The key insight is that graph shift operators should be corrected in order to avoid potential distortions introduced by the non-uniform sampling. Then, we develop methods to estimate the unknown sampling density in a self-supervised fashion. Finally, we present exemplary applications in which the learnt density is used to 1) correct the graph shift operator and improve performance on a variety of tasks, 2) improve pooling, and 3) extract knowledge from networks. Our experimental findings support our theory and provide strong evidence for our model.

Related papers

• Generalization of Geometric Graph Neural Networks [84.01980526069075]
  We study the generalization capabilities of geometric graph neural networks (GNNs) We prove a generalization gap between the optimal empirical risk and the optimal statistical risk of this GNN. The most important observation is that the generalization capability can be realized with one large graph instead of being limited to the size of the graph as in previous results.
  arXiv  Detail & Related papers  (2024-09-08T18:55:57Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure. We introduce a new class of manifold, named soft manifold, that can solve this situation. Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
  arXiv  Detail & Related papers  (2023-11-29T12:48:33Z)
• GRAPES: Learning to Sample Graphs for Scalable Graph Neural Networks [2.4175455407547015]
  Graph neural networks learn to represent nodes by aggregating information from their neighbors. Several existing methods address this by sampling a small subset of nodes, scaling GNNs to much larger graphs. We introduce GRAPES, an adaptive sampling method that learns to identify the set of nodes crucial for training a GNN.
  arXiv  Detail & Related papers  (2023-10-05T09:08:47Z)
• Graph Out-of-Distribution Generalization with Controllable Data Augmentation [51.17476258673232]
  Graph Neural Network (GNN) has demonstrated extraordinary performance in classifying graph properties. Due to the selection bias of training and testing data, distribution deviation is widespread. We propose OOD calibration to measure the distribution deviation of virtual samples.
  arXiv  Detail & Related papers  (2023-08-16T13:10:27Z)
• Node Copying: A Random Graph Model for Effective Graph Sampling [35.957719744856696]
  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.
  arXiv  Detail & Related papers  (2022-08-04T04:04:49Z)
• Template based Graph Neural Network with Optimal Transport Distances [11.56532171513328]
  Current Graph Neural Networks (GNN) architectures rely on two important components: node features embedding through message passing, and aggregation with a specialized form of pooling. We propose in this work a novel point of view, which places distances to some learnable graph templates at the core of the graph representation. This distance embedding is constructed thanks to an optimal transport distance: the Fused Gromov-Wasserstein (FGW) distance.
  arXiv  Detail & Related papers  (2022-05-31T12:24:01Z)
• Geometric Graph Representation Learning via Maximizing Rate Reduction [73.6044873825311]
  Learning node representations benefits various downstream tasks in graph analysis such as community detection and node classification. We propose Geometric Graph Representation Learning (G2R) to learn node representations in an unsupervised manner. G2R maps nodes in distinct groups into different subspaces, while each subspace is compact and different subspaces are dispersed.
  arXiv  Detail & Related papers  (2022-02-13T07:46:24Z)
• Graph Convolution with Low-rank Learnable Local Filters [32.00396411583352]
  This paper introduces a new type of graph convolution with learnable low-rank local filters. It is provably more expressive than previous spectral graph convolution methods. The representation against input graph data is theoretically proved, making use of the graph filter locality and the local graph regularization.
  arXiv  Detail & Related papers  (2020-08-04T20:34:59Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42: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.