Renormalized Graph Representations for Node Classification

• URL: http://arxiv.org/abs/2306.00707v2
• Date: Mon, 14 Apr 2025 14:40:09 GMT
• Title: Renormalized Graph Representations for Node Classification
• Authors: Francesco Caso, Giovanni Trappolini, Andrea Bacciu, Pietro Liò, Fabrizio Silvestri,
• Abstract summary: We analyze the effect of using different coarse-grained graph resolutions on node classification tasks.<n>We specifically experiment using representations at the characteristic scale of the graph's mesoscopic structures.<n>Our results showed that models with access to both the original graph and the characteristic scale graph can achieve statistically significant improvements in test accuracy.
• Score: 21.589472270424405
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph neural networks process information on graphs represented at a given resolution scale. We analyze the effect of using different coarse-grained graph resolutions, obtained through the Laplacian renormalization group theory, on node classification tasks. At the theory's core is grouping nodes connected by significant information flow at a given time scale. Representations of the graph at different scales encode interaction information at different ranges. We specifically experiment using representations at the characteristic scale of the graph's mesoscopic structures. We provide the models with the original graph and the graph represented at the characteristic resolution scale and compare them to models that can only access the original graph. Our results showed that models with access to both the original graph and the characteristic scale graph can achieve statistically significant improvements in test accuracy.

Related papers

• On the Topology Awareness and Generalization Performance of Graph Neural Networks [6.598758004828656]
  We introduce a comprehensive framework to characterize the topology awareness of GNNs across any topological feature. We conduct a case study using the intrinsic graph metric the shortest path distance on various benchmark datasets.
  arXiv  Detail & Related papers  (2024-03-07T13:33:30Z)
• Graph Neural Networks with a Distribution of Parametrized Graphs [27.40566674759208]
  We introduce latent variables to parameterize and generate multiple graphs. We obtain the maximum likelihood estimate of the network parameters in an Expectation-Maximization framework.
  arXiv  Detail & Related papers  (2023-10-25T06:38:24Z)
• Information Flow in Graph Neural Networks: A Clinical Triage Use Case [49.86931948849343]
  Graph Neural Networks (GNNs) have gained popularity in healthcare and other domains due to their ability to process multi-modal and multi-relational graphs. We investigate how the flow of embedding information within GNNs affects the prediction of links in Knowledge Graphs (KGs) Our results demonstrate that incorporating domain knowledge into the GNN connectivity leads to better performance than using the same connectivity as the KG or allowing unconstrained embedding propagation.
  arXiv  Detail & Related papers  (2023-09-12T09:18:12Z)
• The Evolution of Distributed Systems for Graph Neural Networks and their Origin in Graph Processing and Deep Learning: A Survey [17.746899445454048]
  Graph Neural Networks (GNNs) are an emerging research field. GNNs can be applied to various domains including recommendation systems, computer vision, natural language processing, biology and chemistry. We aim to fill this gap by summarizing and categorizing important methods and techniques for large-scale GNN solutions.
  arXiv  Detail & Related papers  (2023-05-23T09:22:33Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  We propose DEGREE to provide a faithful explanation for GNN predictions. By decomposing the information generation and aggregation mechanism of GNNs, DEGREE allows tracking the contributions of specific components of the input graph to the final prediction. We also design a subgraph level interpretation algorithm to reveal complex interactions between graph nodes that are overlooked by previous methods.
  arXiv  Detail & Related papers  (2023-05-22T10:29:52Z)
• GNN-Ensemble: Towards Random Decision Graph Neural Networks [3.7620848582312405]
  Graph Neural Networks (GNNs) have enjoyed wide spread applications in graph-structured data. GNNs are required to learn latent patterns from a limited amount of training data to perform inferences on a vast amount of test data. In this paper, we push one step forward on the ensemble learning of GNNs with improved accuracy, robustness, and adversarial attacks.
  arXiv  Detail & Related papers  (2023-03-20T18:24:01Z)
• Relation Embedding based Graph Neural Networks for Handling Heterogeneous Graph [58.99478502486377]
  We propose a simple yet efficient framework to make the homogeneous GNNs have adequate ability to handle heterogeneous graphs. Specifically, we propose Relation Embedding based Graph Neural Networks (RE-GNNs), which employ only one parameter per relation to embed the importance of edge type relations and self-loop connections.
  arXiv  Detail & Related papers  (2022-09-23T05:24:18Z)
• Demystifying Graph Convolution with a Simple Concatenation [6.542119695695405]
  We quantify the information overlap between graph topology, node features, and labels. We show that graph concatenation is a simple but more flexible alternative to graph convolution.
  arXiv  Detail & Related papers  (2022-07-18T16:39:33Z)
• 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)
• Graph Neural Networks for Graphs with Heterophily: A Survey [98.45621222357397]
  We provide a comprehensive review of graph neural networks (GNNs) for heterophilic graphs. Specifically, we propose a systematic taxonomy that essentially governs existing heterophilic GNN models. We discuss the correlation between graph heterophily and various graph research domains, aiming to facilitate the development of more effective GNNs.
  arXiv  Detail & Related papers  (2022-02-14T23:07:47Z)
• Accurate Learning of Graph Representations with Graph Multiset Pooling [45.72542969364438]
  We propose a Graph Multiset Transformer (GMT) that captures the interaction between nodes according to their structural dependencies. Our experimental results show that GMT significantly outperforms state-of-the-art graph pooling methods on graph classification benchmarks.
  arXiv  Detail & Related papers  (2021-02-23T07:45:58Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• 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)
• A Unified View on Graph Neural Networks as Graph Signal Denoising [49.980783124401555]
  Graph Neural Networks (GNNs) have risen to prominence in learning representations for graph structured data. In this work, we establish mathematically that the aggregation processes in a group of representative GNN models can be regarded as solving a graph denoising problem. We instantiate a novel GNN model, ADA-UGNN, derived from UGNN, to handle graphs with adaptive smoothness across nodes.
  arXiv  Detail & Related papers  (2020-10-05T04:57:18Z)
• Architectural Implications of Graph Neural Networks [17.01480604968118]
  Graph neural networks (GNN) represent an emerging line of deep learning models that operate on graph structures. GNN is not as well understood in the system and architecture community as its counterparts such as multi-layer perceptrons and convolutional neural networks.
  arXiv  Detail & Related papers  (2020-09-02T03:36:24Z)
• Multilevel Graph Matching Networks for Deep Graph Similarity Learning [79.3213351477689]
  We propose a multi-level graph matching network (MGMN) framework for computing the graph similarity between any pair of graph-structured objects. To compensate for the lack of standard benchmark datasets, we have created and collected a set of datasets for both the graph-graph classification and graph-graph regression tasks. Comprehensive experiments demonstrate that MGMN consistently outperforms state-of-the-art baseline models on both the graph-graph classification and graph-graph regression tasks.
  arXiv  Detail & Related papers  (2020-07-08T19:48:19Z)
• 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)
• Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs [95.63153473559865]
  Graph Neural Networks (GNNs) are emerging machine learning models on graphs. Most existing GNN models in practice are shallow and essentially feature-centric. We show empirically and analytically that the existing shallow GNNs cannot preserve graph structures well. We propose Eigen-GNN, a plug-in module to boost GNNs ability in preserving graph structures.
  arXiv  Detail & Related papers  (2020-06-08T02:47:38Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)
• The Power of Graph Convolutional Networks to Distinguish Random Graph Models: Short Version [27.544219236164764]
  Graph convolutional networks (GCNs) are a widely used method for graph representation learning. We investigate the power of GCNs to distinguish between different random graph models on the basis of the embeddings of their sample graphs.
  arXiv  Detail & Related papers  (2020-02-13T17:58:42Z)

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.