Scaling up graph homomorphism for classification via sampling

• URL: http://arxiv.org/abs/2104.04040v1
• Date: Thu, 8 Apr 2021 20:25:37 GMT
• Title: Scaling up graph homomorphism for classification via sampling
• Authors: Paul Beaujean and Florian Sikora and Florian Yger
• Abstract summary: We study the use of graph homomorphism density features as a scalable alternative to homomorphism numbers. We propose a high-performance implementation of a simple sampling algorithm which computes additive approximations of homomorphism densities.
• Score: 1.662966122370634
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Feature generation is an open topic of investigation in graph machine learning. In this paper, we study the use of graph homomorphism density features as a scalable alternative to homomorphism numbers which retain similar theoretical properties and ability to take into account inductive bias. For this, we propose a high-performance implementation of a simple sampling algorithm which computes additive approximations of homomorphism densities. In the context of graph machine learning, we demonstrate in experiments that simple linear models trained on sample homomorphism densities can achieve performance comparable to graph neural networks on standard graph classification datasets. Finally, we show in experiments on synthetic data that this algorithm scales to very large graphs when implemented with Bloom filters.

Related papers

• Generation is better than Modification: Combating High Class Homophily Variance in Graph Anomaly Detection [51.11833609431406]
  Homophily distribution differences between different classes are significantly greater than those in homophilic and heterophilic graphs. We introduce a new metric called Class Homophily Variance, which quantitatively describes this phenomenon. To mitigate its impact, we propose a novel GNN model named Homophily Edge Generation Graph Neural Network (HedGe)
  arXiv  Detail & Related papers  (2024-03-15T14:26:53Z)
• PF-GNN: Differentiable particle filtering based approximation of universal graph representations [20.544160526945234]
  Graph Neural Networks (GNNs) are known to be limited in expressive power by the 1-WL color-refinement test for graph isomorphism. In this work, we propose to make GNNs universal by guiding the learning process with exact isomorphism solver techniques. Our algorithm is end-to-end differentiable, can be applied with any GNN as backbone and learns richer graph representations with only linear increase in runtime.
  arXiv  Detail & Related papers  (2024-01-31T11:26:03Z)
• Structural Node Embeddings with Homomorphism Counts [2.0131144893314232]
  homomorphism counts capture local structural information. We experimentally show the effectiveness of homomorphism count based node embeddings. Our approach capitalises on the efficient computability of graph homomorphism counts for bounded treewidth graph classes.
  arXiv  Detail & Related papers  (2023-08-29T13:14:53Z)
• Permutation Equivariant Graph Framelets for Heterophilous Graph Learning [6.679929638714752]
  We develop a new way to implement multi-scale extraction via constructing Haar-type graph framelets. We show that our model can achieve the best performance on certain datasets of heterophilous graphs.
  arXiv  Detail & Related papers  (2023-06-07T09:05:56Z)
• 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)
• Heterogeneous Graph Neural Networks using Self-supervised Reciprocally Contrastive Learning [102.9138736545956]
  Heterogeneous graph neural network (HGNN) is a very popular technique for the modeling and analysis of heterogeneous graphs. We develop for the first time a novel and robust heterogeneous graph contrastive learning approach, namely HGCL, which introduces two views on respective guidance of node attributes and graph topologies. In this new approach, we adopt distinct but most suitable attribute and topology fusion mechanisms in the two views, which are conducive to mining relevant information in attributes and topologies separately.
  arXiv  Detail & Related papers  (2022-04-30T12:57:02Z)
• Learning to Learn Graph Topologies [27.782971146122218]
  We learn a mapping from node data to the graph structure based on the idea of learning to optimise (L2O) The model is trained in an end-to-end fashion with pairs of node data and graph samples. Experiments on both synthetic and real-world data demonstrate that our model is more efficient than classic iterative algorithms in learning a graph with specific topological properties.
  arXiv  Detail & Related papers  (2021-10-19T08:42:38Z)
• 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)
• Geometric graphs from data to aid classification tasks with graph convolutional networks [0.0]
  We show that, even if additional relational information is not available in the data set, one can improve classification by constructing geometric graphs from the features themselves. The improvement in classification accuracy is maximized by graphs that capture sample similarity with relatively low edge density.
  arXiv  Detail & Related papers  (2020-05-08T15:00:45Z)
• Permutation Invariant Graph Generation via Score-Based Generative Modeling [114.12935776726606]
  We propose a permutation invariant approach to modeling graphs, using the recent framework of score-based generative modeling. In particular, we design a permutation equivariant, multi-channel graph neural network to model the gradient of the data distribution at the input graph. For graph generation, we find that our learning approach achieves better or comparable results to existing models on benchmark datasets.
  arXiv  Detail & Related papers  (2020-03-02T03:06:14Z)
• 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.